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