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 public boolean shouldPerform(OptOptions options) {
066 if (options.getOptLevel() < 2) {
067 return false;
068 }
069 return options.SSA_GCP || options.SSA_GCSE;
070 }
071
072 static boolean tooBig(IR ir) {
073 boolean res = false;
074 if (ir.getMaxBasicBlockNumber() > 1000) {
075 //VM.sysWrite (ir.method.toString() + " is too large\n");
076 res = true;
077 }
078 return res;
079 }
080
081 /**
082 * This class sets up the IR state prior to entering SSA for GCP
083 */
084 private static class GCPPreparation extends CompilerPhase {
085 /**
086 * Return this instance of this phase. This phase contains no
087 * per-compilation instance fields.
088 * @param ir not used
089 * @return this
090 */
091 public CompilerPhase newExecution(IR ir) {
092 return this;
093 }
094
095 /**
096 * Should this phase perform?
097 * @param options
098 */
099 public final boolean shouldPerform(OptOptions options) {
100 return options.SSA_GCP || options.SSA_GCSE;
101 }
102
103 /**
104 * Return the name of the phase
105 */
106 public final String getName() {
107 return "GCP Preparation";
108 }
109
110 /**
111 * perform the phase
112 * @param ir
113 */
114 public final void perform(IR ir) {
115 boolean dont = false;
116 //VM.sysWrite("> " + ir.method + "\n");
117
118 if (ir.hasReachableExceptionHandlers()) {
119 //VM.sysWrite("has exceptionhandlers\n");
120 dont = true;
121 }
122 if (GCP.tooBig(ir)) {
123 dont = true;
124 }
125 if (dont) {
126 ir.options.SSA = false;
127 return;
128 }
129 ir.desiredSSAOptions = new SSAOptions();
130 // register in the IR the SSA properties we need for GCP
131 if (ir.IRStage == IR.LIR) {
132 ir.desiredSSAOptions.setScalarsOnly(true);
133 ir.desiredSSAOptions.setBackwards(false);
134 ir.desiredSSAOptions.setInsertUsePhis(false);
135 ir.desiredSSAOptions.setInsertPEIDeps(false);
136 ir.desiredSSAOptions.setHeapTypes(null);
137 } else {
138 // HIR options
139 ir.desiredSSAOptions.setScalarsOnly(false);
140 ir.desiredSSAOptions.setBackwards(true);
141 ir.desiredSSAOptions.setInsertUsePhis(true);
142 ir.desiredSSAOptions.setInsertPEIDeps(!ir.options.SSA_LICM_IGNORE_PEI);
143 ir.desiredSSAOptions.setHeapTypes(null);
144 }
145 }
146 }
147
148 /**
149 * This class sets up the IR state prior to entering SSA for GCP
150 */
151 private static class GCPFinalization extends CompilerPhase {
152 /**
153 * Return this instance of this phase. This phase contains no
154 * per-compilation instance fields.
155 * @param ir not used
156 * @return this
157 */
158 public CompilerPhase newExecution(IR ir) {
159 return this;
160 }
161
162 /**
163 * Should this phase perform?
164 * @param options
165 */
166 public final boolean shouldPerform(OptOptions options) {
167 return options.SSA_GCP || options.SSA_GCSE;
168 }
169
170 /**
171 * Return the name of the phase
172 */
173 public final String getName() {
174 return "GCP Finalization";
175 }
176
177 /**
178 * perform the phase
179 * @param ir
180 */
181 public final void perform(IR ir) {
182 ir.options.SSA = true;
183 //VM.sysWrite("< " + ir.method + "\n");
184 // register in the IR the SSA properties GCP preserves
185 if (!GCP.tooBig(ir) && !ir.hasReachableExceptionHandlers() && ir.actualSSAOptions != null) {
186 if (ir.IRStage == IR.LIR) {
187 ir.actualSSAOptions.setScalarsOnly(true);
188 ir.actualSSAOptions.setBackwards(false);
189 ir.actualSSAOptions.setInsertUsePhis(false);
190 ir.actualSSAOptions.setInsertPEIDeps(false);
191 ir.actualSSAOptions.setHeapTypes(null);
192 } else {
193 // HIR options
194 ir.actualSSAOptions.setScalarsOnly(false);
195 ir.actualSSAOptions.setBackwards(true);
196 ir.actualSSAOptions.setInsertUsePhis(true);
197 ir.actualSSAOptions.setInsertPEIDeps(true);
198 ir.actualSSAOptions.setHeapTypes(null);
199 }
200 }
201 }
202 }
203
204 public static boolean usesOrDefsPhysicalRegisterOrAddressType(Instruction inst) {
205
206 for (int i = inst.getNumberOfOperands() - 1; i >= 0; --i) {
207 Operand op = inst.getOperand(i);
208 if (op instanceof RegisterOperand) {
209 if (op.asRegister().getType().isWordLikeType() || op.asRegister().getRegister().isPhysical()) {
210 return true;
211 }
212 }
213 }
214 return false;
215 }
216 }