001 /*
002 * This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 * This file is licensed to You under the Eclipse Public License (EPL);
005 * You may not use this file except in compliance with the License. You
006 * may obtain a copy of the License at
007 *
008 * http://www.opensource.org/licenses/eclipse-1.0.php
009 *
010 * See the COPYRIGHT.txt file distributed with this work for information
011 * regarding copyright ownership.
012 */
013 package org.jikesrvm.compilers.opt.ssa;
014
015 import org.jikesrvm.compilers.opt.OptOptions;
016 import org.jikesrvm.compilers.opt.driver.CompilerPhase;
017 import org.jikesrvm.compilers.opt.driver.OptimizationPlanAtomicElement;
018 import org.jikesrvm.compilers.opt.driver.OptimizationPlanCompositeElement;
019 import org.jikesrvm.compilers.opt.driver.OptimizationPlanElement;
020 import org.jikesrvm.compilers.opt.ir.IR;
021 import org.jikesrvm.compilers.opt.ir.Instruction;
022 import org.jikesrvm.compilers.opt.ir.operand.Operand;
023 import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand;
024
025 /**
026 * Global code placement comes in two flavours. The first is loop
027 * invariant code motion (LICM), the second is global common sub
028 * expression elimination (GCSE).<p>
029 *
030 * LICM is applied to HIR and LIR, GCSE only to LIR and before
031 * LICM.<p>
032 *
033 * Both algorithms run on SSA and use the dominator tree to determine
034 * positions for operations. That's why these operations are called
035 * code placement instead of code motion. <p>
036 *
037 * There is no code yet to deal with partial redundancies.
038 */
039 public final class GCP extends OptimizationPlanCompositeElement {
040
041 /**
042 * Makes sure we are in SSA and have global value numbers at hand.
043 * Then execute the transformations.
044 */
045 public GCP() {
046 super("Global Code Placement", new OptimizationPlanElement[]{
047 // 1. Set up IR state to control SSA translation as needed
048 new OptimizationPlanAtomicElement(new GCPPreparation()),
049 // 2. Get the desired SSA form
050 new OptimizationPlanAtomicElement(new EnterSSA()),
051 // 3. Perform global CSE
052 new OptimizationPlanAtomicElement(new GlobalCSE()),
053 // 4. Repair SSA
054 new OptimizationPlanAtomicElement(new EnterSSA()),
055 // 5. Perform Loop Invariant Code Motion
056 new OptimizationPlanAtomicElement(new LICM()),
057 // 6. Finalize GCP
058 new OptimizationPlanAtomicElement(new GCPFinalization())});
059 }
060
061 /**
062 * Redefine shouldPerform so that none of the subphases will occur
063 * unless we pass through this test.
064 */
065 @Override
066 public boolean shouldPerform(OptOptions options) {
067 if (options.getOptLevel() < 2) {
068 return false;
069 }
070 return options.SSA_GCP || options.SSA_GCSE;
071 }
072
073 static boolean tooBig(IR ir) {
074 boolean res = false;
075 if (ir.getMaxBasicBlockNumber() > 1000) {
076 //VM.sysWrite (ir.method.toString() + " is too large\n");
077 res = true;
078 }
079 return res;
080 }
081
082 /**
083 * This class sets up the IR state prior to entering SSA for GCP
084 */
085 private static class GCPPreparation extends CompilerPhase {
086 /**
087 * Return this instance of this phase. This phase contains no
088 * per-compilation instance fields.
089 * @param ir not used
090 * @return this
091 */
092 @Override
093 public CompilerPhase newExecution(IR ir) {
094 return this;
095 }
096
097 /**
098 * Should this phase perform?
099 * <p>
100 * @return <code>true</code> if SSA-based global code placement
101 * or SSA-based global common subexpression elimination are
102 * enabled
103 */
104 @Override
105 public final boolean shouldPerform(OptOptions options) {
106 return options.SSA_GCP || options.SSA_GCSE;
107 }
108
109 /**
110 * Return the name of the phase
111 */
112 @Override
113 public final String getName() {
114 return "GCP Preparation";
115 }
116
117 @Override
118 public final void perform(IR ir) {
119 boolean dont = false;
120 //VM.sysWrite("> " + ir.method + "\n");
121
122 if (ir.hasReachableExceptionHandlers()) {
123 //VM.sysWrite("has exceptionhandlers\n");
124 dont = true;
125 }
126 if (GCP.tooBig(ir)) {
127 dont = true;
128 }
129 if (dont) {
130 ir.options.SSA = false;
131 return;
132 }
133 ir.desiredSSAOptions = new SSAOptions();
134 // register in the IR the SSA properties we need for GCP
135 if (ir.IRStage == IR.LIR) {
136 ir.desiredSSAOptions.setScalarsOnly(true);
137 ir.desiredSSAOptions.setBackwards(false);
138 ir.desiredSSAOptions.setInsertUsePhis(false);
139 ir.desiredSSAOptions.setInsertPEIDeps(false);
140 ir.desiredSSAOptions.setHeapTypes(null);
141 } else {
142 // HIR options
143 ir.desiredSSAOptions.setScalarsOnly(false);
144 ir.desiredSSAOptions.setBackwards(true);
145 ir.desiredSSAOptions.setInsertUsePhis(true);
146 ir.desiredSSAOptions.setInsertPEIDeps(!ir.options.SSA_LICM_IGNORE_PEI);
147 ir.desiredSSAOptions.setHeapTypes(null);
148 }
149 }
150 }
151
152 /**
153 * This class sets up the IR state prior to entering SSA for GCP
154 */
155 private static class GCPFinalization extends CompilerPhase {
156 /**
157 * Return this instance of this phase. This phase contains no
158 * per-compilation instance fields.
159 * @param ir not used
160 * @return this
161 */
162 @Override
163 public CompilerPhase newExecution(IR ir) {
164 return this;
165 }
166
167 /**
168 * Should this phase perform?
169 * <p>
170 * Perform only if global code placement
171 * or global common subexpression elimination are performed.
172 */
173 @Override
174 public final boolean shouldPerform(OptOptions options) {
175 return options.SSA_GCP || options.SSA_GCSE;
176 }
177
178 /**
179 * Return the name of the phase
180 */
181 @Override
182 public final String getName() {
183 return "GCP Finalization";
184 }
185
186 @Override
187 public final void perform(IR ir) {
188 ir.options.SSA = true;
189 //VM.sysWrite("< " + ir.method + "\n");
190 // register in the IR the SSA properties GCP preserves
191 if (!GCP.tooBig(ir) && !ir.hasReachableExceptionHandlers() && ir.actualSSAOptions != null) {
192 if (ir.IRStage == IR.LIR) {
193 ir.actualSSAOptions.setScalarsOnly(true);
194 ir.actualSSAOptions.setBackwards(false);
195 ir.actualSSAOptions.setInsertUsePhis(false);
196 ir.actualSSAOptions.setInsertPEIDeps(false);
197 ir.actualSSAOptions.setHeapTypes(null);
198 } else {
199 // HIR options
200 ir.actualSSAOptions.setScalarsOnly(false);
201 ir.actualSSAOptions.setBackwards(true);
202 ir.actualSSAOptions.setInsertUsePhis(true);
203 ir.actualSSAOptions.setInsertPEIDeps(true);
204 ir.actualSSAOptions.setHeapTypes(null);
205 }
206 }
207 }
208 }
209
210 public static boolean usesOrDefsPhysicalRegisterOrAddressType(Instruction inst) {
211
212 for (int i = inst.getNumberOfOperands() - 1; i >= 0; --i) {
213 Operand op = inst.getOperand(i);
214 if (op instanceof RegisterOperand) {
215 if (op.asRegister().getType().isWordLikeType() || op.asRegister().getRegister().isPhysical()) {
216 return true;
217 }
218 }
219 }
220 return false;
221 }
222 }