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 static org.jikesrvm.compilers.opt.ir.Operators.*;
016
017 import java.lang.reflect.Constructor;
018 import java.util.Enumeration;
019 import java.util.HashMap;
020
021 import org.jikesrvm.VM;
022 import org.jikesrvm.compilers.opt.DefUse;
023 import org.jikesrvm.compilers.opt.OptOptions;
024 import org.jikesrvm.compilers.opt.Simple;
025 import org.jikesrvm.compilers.opt.controlflow.DominatorTree;
026 import org.jikesrvm.compilers.opt.controlflow.DominatorTreeNode;
027 import org.jikesrvm.compilers.opt.driver.CompilerPhase;
028 import org.jikesrvm.compilers.opt.ir.BBend;
029 import org.jikesrvm.compilers.opt.ir.BasicBlock;
030 import org.jikesrvm.compilers.opt.ir.GuardResultCarrier;
031 import org.jikesrvm.compilers.opt.ir.IR;
032 import org.jikesrvm.compilers.opt.ir.Instruction;
033 import org.jikesrvm.compilers.opt.ir.Register;
034 import org.jikesrvm.compilers.opt.ir.RegisterOperandEnumeration;
035 import org.jikesrvm.compilers.opt.ir.ResultCarrier;
036 import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand;
037 import org.jikesrvm.compilers.opt.util.TreeNode;
038
039 /**
040 * This class provides global common sub expression elimination.
041 */
042 public final class GlobalCSE extends CompilerPhase {
043
044 /** Output debug messages */
045 public boolean verbose = true;
046 /** Cache of IR being processed by this phase */
047 private IR ir;
048 /** Cache of the value numbers from the IR */
049 private GlobalValueNumberState valueNumbers;
050 /**
051 * Cache of dominator tree that should be computed prior to this
052 * phase
053 */
054 private DominatorTree dominator;
055 /**
056 * Available expressions. From Muchnick, "an expression
057 * <em>exp</em>is said to be </em>available</em> at the entry to a
058 * basic block if along every control-flow path from the entry block
059 * to this block there is an evaluation of exp that is not
060 * subsequently killed by having one or more of its operands
061 * assigned a new value." Our available expressions are a mapping
062 * from a value number to the first instruction to define it as we
063 * traverse the dominator tree.
064 */
065 private final HashMap<Integer, Instruction> avail;
066
067 /**
068 * Constructor
069 */
070 public GlobalCSE() {
071 avail = new HashMap<Integer, Instruction>();
072 }
073
074 /**
075 * Redefine shouldPerform so that none of the subphases will occur
076 * unless we pass through this test.
077 */
078 public boolean shouldPerform(OptOptions options) {
079 return options.SSA_GCSE;
080 }
081
082 /**
083 * Constructor for this compiler phase
084 */
085 private static final Constructor<CompilerPhase> constructor = getCompilerPhaseConstructor(GlobalCSE.class);
086
087 /**
088 * Get a constructor object for this compiler phase
089 * @return compiler phase constructor
090 */
091 public Constructor<CompilerPhase> getClassConstructor() {
092 return constructor;
093 }
094
095 /**
096 * Returns the name of the phase
097 */
098 public String getName() {
099 return "Global CSE";
100 }
101
102 /**
103 * Perform the GlobalCSE compiler phase
104 */
105 public void perform(IR ir) {
106 // conditions to leave early
107 if (ir.hasReachableExceptionHandlers() || GCP.tooBig(ir)) {
108 return;
109 }
110 // cache useful values
111 verbose = ir.options.DEBUG_GCP;
112 this.ir = ir;
113 dominator = ir.HIRInfo.dominatorTree;
114
115 // perform GVN
116 (new GlobalValueNumber()).perform(ir);
117 valueNumbers = ir.HIRInfo.valueNumbers;
118
119 if (verbose) VM.sysWrite("in GCSE for " + ir.method + "\n");
120
121 // compute DU and perform copy propagation
122 DefUse.computeDU(ir);
123 Simple.copyPropagation(ir);
124 DefUse.computeDU(ir);
125
126 // perform GCSE starting at the entry block
127 globalCSE(ir.firstBasicBlockInCodeOrder());
128
129 if (VM.VerifyAssertions) {
130 VM._assert(avail.isEmpty(), avail.toString());
131 }
132 ir.actualSSAOptions.setScalarValid(false);
133 }
134
135 /**
136 * Recursively descend over all blocks dominated by b. For each
137 * instruction in the block, if it defines a GVN then record it in
138 * the available expressions. If the GVN already exists in the
139 * available expressions then eliminate the instruction and change
140 * all uses of the result of the instruction to be uses of the first
141 * instruction to define the result of this expression.
142 * @param b the current block to process
143 */
144 private void globalCSE(BasicBlock b) {
145 Instruction next, inst;
146 // Iterate over instructions in b
147 inst = b.firstInstruction();
148 while (!BBend.conforms(inst)) {
149 next = inst.nextInstructionInCodeOrder();
150 // check instruction is safe for GCSE, {@see shouldCSE}
151 if (!shouldCSE(inst)) {
152 inst = next;
153 continue;
154 }
155 // check the instruction defines a result
156 RegisterOperand result = getResult(inst);
157 if (result == null) {
158 inst = next;
159 continue;
160 }
161 // get the value number for this result. The value number for
162 // the same sub-expression is shared by all results showing they
163 // can be eliminated. If the value number is UNKNOWN the result
164 // is negative.
165 int vn = valueNumbers.getValueNumber(result);
166 if (vn < 0) {
167 inst = next;
168 continue;
169 }
170 // was this the first definition of the value number?
171 Integer Vn = vn;
172 Instruction former = avail.get(Vn);
173 if (former == null) {
174 // first occurance of value number, record it in the available
175 // expressions
176 avail.put(Vn, inst);
177 } else {
178 // this value number has been seen before so we can use the
179 // earlier version
180 // NB instead of trying to repair Heap SSA, we rebuild it
181 // after CSE
182
183 // relink scalar dependencies - make all uses of the current
184 // instructions result use the first definition of the result
185 // by the earlier expression
186 RegisterOperand formerDef = getResult(former);
187 Register reg = result.getRegister();
188 formerDef.getRegister().setSpansBasicBlock();
189 RegisterOperandEnumeration uses = DefUse.uses(reg);
190 while (uses.hasMoreElements()) {
191 RegisterOperand use = uses.next();
192 DefUse.transferUse(use, formerDef);
193 }
194 if (verbose) {
195 VM.sysWrite("using " + former + "\n" + "instead of " + inst + "\n");
196 }
197 // remove the redundant instruction
198 inst.remove();
199 }
200 inst = next;
201 } // end of instruction iteration
202 // Recurse over all blocks that this block dominates
203 Enumeration<TreeNode> e = dominator.getChildren(b);
204 while (e.hasMoreElements()) {
205 DominatorTreeNode n = (DominatorTreeNode) e.nextElement();
206 BasicBlock bl = n.getBlock();
207 // don't process infrequently executed basic blocks
208 if (ir.options.FREQ_FOCUS_EFFORT && bl.getInfrequent()) continue;
209 globalCSE(bl);
210 }
211 // Iterate over instructions in this basic block removing
212 // available expressions that had been created for this block
213 inst = b.firstInstruction();
214 while (!BBend.conforms(inst)) {
215 next = inst.nextInstructionInCodeOrder();
216 if (!shouldCSE(inst)) {
217 inst = next;
218 continue;
219 }
220 RegisterOperand result = getResult(inst);
221 if (result == null) {
222 inst = next;
223 continue;
224 }
225 int vn = valueNumbers.getValueNumber(result);
226 if (vn < 0) {
227 inst = next;
228 continue;
229 }
230 Integer Vn = vn;
231 Instruction former = avail.get(Vn);
232 if (former == inst) {
233 avail.remove(Vn);
234 }
235 inst = next;
236 }
237 }
238
239 /**
240 * Get the result operand of the instruction
241 * @param inst
242 */
243 private RegisterOperand getResult(Instruction inst) {
244 if (ResultCarrier.conforms(inst)) {
245 return ResultCarrier.getResult(inst);
246 }
247 if (GuardResultCarrier.conforms(inst)) {
248 return GuardResultCarrier.getGuardResult(inst);
249 }
250 return null;
251 }
252
253 /**
254 * should this instruction be cse'd ?
255 * @param inst
256 */
257 private boolean shouldCSE(Instruction inst) {
258
259 if ((inst.isAllocation()) ||
260 inst.isDynamicLinkingPoint() ||
261 inst.isImplicitLoad() ||
262 inst.isImplicitStore() ||
263 inst.operator.opcode >= ARCH_INDEPENDENT_END_opcode) {
264 return false;
265 }
266
267 switch (inst.operator.opcode) {
268 case INT_MOVE_opcode:
269 case LONG_MOVE_opcode:
270 case CHECKCAST_opcode:
271 case CHECKCAST_NOTNULL_opcode:
272 case CHECKCAST_UNRESOLVED_opcode:
273 case MUST_IMPLEMENT_INTERFACE_opcode:
274 case INSTANCEOF_opcode:
275 case INSTANCEOF_NOTNULL_opcode:
276 case INSTANCEOF_UNRESOLVED_opcode:
277 case PI_opcode:
278 case FLOAT_MOVE_opcode:
279 case DOUBLE_MOVE_opcode:
280 case REF_MOVE_opcode:
281 case GUARD_MOVE_opcode:
282 case GUARD_COMBINE_opcode:
283 case TRAP_IF_opcode:
284 case REF_ADD_opcode:
285 case INT_ADD_opcode:
286 case LONG_ADD_opcode:
287 case FLOAT_ADD_opcode:
288 case DOUBLE_ADD_opcode:
289 case REF_SUB_opcode:
290 case INT_SUB_opcode:
291 case LONG_SUB_opcode:
292 case FLOAT_SUB_opcode:
293 case DOUBLE_SUB_opcode:
294 case INT_MUL_opcode:
295 case LONG_MUL_opcode:
296 case FLOAT_MUL_opcode:
297 case DOUBLE_MUL_opcode:
298 case INT_DIV_opcode:
299 case LONG_DIV_opcode:
300 case FLOAT_DIV_opcode:
301 case DOUBLE_DIV_opcode:
302 case INT_REM_opcode:
303 case LONG_REM_opcode:
304 case FLOAT_REM_opcode:
305 case DOUBLE_REM_opcode:
306 case INT_NEG_opcode:
307 case LONG_NEG_opcode:
308 case FLOAT_NEG_opcode:
309 case DOUBLE_NEG_opcode:
310 case REF_SHL_opcode:
311 case INT_SHL_opcode:
312 case LONG_SHL_opcode:
313 case REF_SHR_opcode:
314 case INT_SHR_opcode:
315 case LONG_SHR_opcode:
316 case REF_USHR_opcode:
317 case INT_USHR_opcode:
318 case LONG_USHR_opcode:
319 case REF_AND_opcode:
320 case INT_AND_opcode:
321 case LONG_AND_opcode:
322 case REF_OR_opcode:
323 case INT_OR_opcode:
324 case LONG_OR_opcode:
325 case REF_XOR_opcode:
326 case INT_XOR_opcode:
327 case REF_NOT_opcode:
328 case INT_NOT_opcode:
329 case LONG_NOT_opcode:
330 case LONG_XOR_opcode:
331 case INT_2LONG_opcode:
332 case INT_2FLOAT_opcode:
333 case INT_2DOUBLE_opcode:
334 case INT_2ADDRSigExt_opcode:
335 case INT_2ADDRZerExt_opcode:
336 case LONG_2ADDR_opcode:
337 case ADDR_2INT_opcode:
338 case ADDR_2LONG_opcode:
339 case LONG_2INT_opcode:
340 case LONG_2FLOAT_opcode:
341 case LONG_2DOUBLE_opcode:
342 case FLOAT_2INT_opcode:
343 case FLOAT_2LONG_opcode:
344 case FLOAT_2DOUBLE_opcode:
345 case DOUBLE_2INT_opcode:
346 case DOUBLE_2LONG_opcode:
347 case DOUBLE_2FLOAT_opcode:
348 case INT_2BYTE_opcode:
349 case INT_2USHORT_opcode:
350 case INT_2SHORT_opcode:
351 case LONG_CMP_opcode:
352 case FLOAT_CMPL_opcode:
353 case FLOAT_CMPG_opcode:
354 case DOUBLE_CMPL_opcode:
355 case DOUBLE_CMPG_opcode:
356 case NULL_CHECK_opcode:
357 case BOUNDS_CHECK_opcode:
358 case INT_ZERO_CHECK_opcode:
359 case LONG_ZERO_CHECK_opcode:
360 case OBJARRAY_STORE_CHECK_opcode:
361 case OBJARRAY_STORE_CHECK_NOTNULL_opcode:
362 case BOOLEAN_NOT_opcode:
363 case BOOLEAN_CMP_INT_opcode:
364 case BOOLEAN_CMP_ADDR_opcode:
365 case FLOAT_AS_INT_BITS_opcode:
366 case INT_BITS_AS_FLOAT_opcode:
367 case DOUBLE_AS_LONG_BITS_opcode:
368 case LONG_BITS_AS_DOUBLE_opcode:
369 case ARRAYLENGTH_opcode:
370 case GET_OBJ_TIB_opcode:
371 case GET_CLASS_TIB_opcode:
372 case GET_TYPE_FROM_TIB_opcode:
373 case GET_SUPERCLASS_IDS_FROM_TIB_opcode:
374 case GET_DOES_IMPLEMENT_FROM_TIB_opcode:
375 case GET_ARRAY_ELEMENT_TIB_FROM_TIB_opcode:
376 return !(GCP.usesOrDefsPhysicalRegisterOrAddressType(inst));
377 }
378 return false;
379 }
380 }