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.controlflow;
014
015 import static org.jikesrvm.compilers.opt.ir.Operators.GOTO;
016 import static org.jikesrvm.compilers.opt.ir.Operators.GUARD_MOVE;
017 import static org.jikesrvm.compilers.opt.ir.Operators.INT_IFCMP;
018
019 import org.jikesrvm.compilers.opt.DefUse;
020 import org.jikesrvm.compilers.opt.ir.BasicBlock;
021 import org.jikesrvm.compilers.opt.ir.Goto;
022 import org.jikesrvm.compilers.opt.ir.GuardResultCarrier;
023 import org.jikesrvm.compilers.opt.ir.IR;
024 import org.jikesrvm.compilers.opt.ir.IREnumeration;
025 import org.jikesrvm.compilers.opt.ir.IfCmp;
026 import org.jikesrvm.compilers.opt.ir.IfCmp2;
027 import org.jikesrvm.compilers.opt.ir.InlineGuard;
028 import org.jikesrvm.compilers.opt.ir.Instruction;
029 import org.jikesrvm.compilers.opt.ir.InstructionEnumeration;
030 import org.jikesrvm.compilers.opt.ir.LookupSwitch;
031 import org.jikesrvm.compilers.opt.ir.Move;
032 import org.jikesrvm.compilers.opt.ir.TableSwitch;
033 import org.jikesrvm.compilers.opt.ir.operand.BranchOperand;
034 import org.jikesrvm.compilers.opt.ir.operand.ConditionOperand;
035 import org.jikesrvm.compilers.opt.ir.operand.IntConstantOperand;
036 import org.jikesrvm.compilers.opt.ir.operand.Operand;
037 import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand;
038 import org.jikesrvm.compilers.opt.ir.operand.TrueGuardOperand;
039
040 /**
041 * Simplify and canonicalize conditional branches with constant operands.
042 *
043 * <p> This module performs no analysis, it simply attempts to
044 * simplify any branching instructions of a basic block that have constant
045 * operands. The intent is that analysis modules can call this
046 * transformation engine, allowing us to share the
047 * simplification code among multiple analysis modules.
048 */
049 public abstract class BranchSimplifier {
050
051 /**
052 * Given a basic block, attempt to simplify any conditional branch
053 * instructions with constant operands.
054 * The instruction will be mutated in place.
055 * The control flow graph will be updated, but the caller is responsible
056 * for calling BranchOptmizations after simplify has been called on
057 * all basic blocks in the IR to remove unreachable code.
058 *
059 * @param bb the basic block to simplify
060 * @return true if we do something, false otherwise.
061 */
062 public static boolean simplify(BasicBlock bb, IR ir) {
063 boolean didSomething = false;
064
065 for (InstructionEnumeration branches = bb.enumerateBranchInstructions(); branches.hasMoreElements();) {
066 Instruction s = branches.next();
067 if (Goto.conforms(s)) {
068 // nothing to do, but a common case so test first
069 } else if (IfCmp.conforms(s)) {
070 if (processIfCmp(ir, bb, s)) {
071 // hack. Just start over since Enumeration has changed.
072 branches = bb.enumerateBranchInstructions();
073 bb.recomputeNormalOut(ir);
074 didSomething = true;
075 }
076 } else if (IfCmp2.conforms(s)) {
077 if (processIfCmp2(ir, bb, s)) {
078 // hack. Just start over since Enumeration has changed.
079 branches = bb.enumerateBranchInstructions();
080 bb.recomputeNormalOut(ir);
081 didSomething = true;
082 }
083 } else if (LookupSwitch.conforms(s)) {
084 if (processLookupSwitch(ir, bb, s)) {
085 // hack. Just start over since Enumeration has changed.
086 branches = bb.enumerateBranchInstructions();
087 bb.recomputeNormalOut(ir);
088 didSomething = true;
089 }
090 } else if (TableSwitch.conforms(s)) {
091 if (processTableSwitch(ir, bb, s)) {
092 // hack. Just start over since Enumeration has changed.
093 branches = bb.enumerateBranchInstructions();
094 bb.recomputeNormalOut(ir);
095 didSomething = true;
096 }
097 } else if (InlineGuard.conforms(s)) {
098 if (processInlineGuard(ir, bb, s)) {
099 // hack. Just start over since Enumeration has changed.
100 branches = bb.enumerateBranchInstructions();
101 bb.recomputeNormalOut(ir);
102 didSomething = true;
103 }
104 }
105 }
106 return didSomething;
107 }
108
109 /** Process IfCmp branch instruction */
110 static boolean processIfCmp(IR ir, BasicBlock bb, Instruction s) {
111 RegisterOperand guard = IfCmp.getGuardResult(s);
112 Operand val1 = IfCmp.getVal1(s);
113 Operand val2 = IfCmp.getVal2(s);
114 {
115 int cond = IfCmp.getCond(s).evaluate(val1, val2);
116 if (cond != ConditionOperand.UNKNOWN) {
117 // constant fold
118 if (cond == ConditionOperand.TRUE) { // branch taken
119 insertTrueGuard(s, guard);
120 Goto.mutate(s, GOTO, IfCmp.getTarget(s));
121 removeBranchesAfterGotos(bb);
122 } else {
123 // branch not taken
124 insertTrueGuard(s, guard);
125 s.remove();
126 }
127 return true;
128 }
129 }
130 if (val1.isConstant() && !val2.isConstant()) {
131 // Canonicalize by making second argument the constant
132 IfCmp.setVal1(s, val2);
133 IfCmp.setVal2(s, val1);
134 IfCmp.setCond(s, IfCmp.getCond(s).flipOperands());
135 }
136
137 if (val2.isIntConstant()) {
138 // Tricks to get compare against zero.
139 int value = ((IntConstantOperand) val2).value;
140 ConditionOperand cond = IfCmp.getCond(s);
141 if (value == 1) {
142 if (cond.isLESS()) {
143 IfCmp.setCond(s, ConditionOperand.LESS_EQUAL());
144 IfCmp.setVal2(s, new IntConstantOperand(0));
145 } else if (cond.isGREATER_EQUAL()) {
146 IfCmp.setCond(s, ConditionOperand.GREATER());
147 IfCmp.setVal2(s, new IntConstantOperand(0));
148 }
149 } else if (value == -1) {
150 if (cond.isGREATER()) {
151 IfCmp.setCond(s, ConditionOperand.GREATER_EQUAL());
152 IfCmp.setVal2(s, new IntConstantOperand(0));
153 } else if (cond.isLESS_EQUAL()) {
154 IfCmp.setCond(s, ConditionOperand.LESS());
155 IfCmp.setVal2(s, new IntConstantOperand(0));
156 }
157 }
158 }
159 return false;
160 }
161
162 /** Process IfCmp2 branch instruction */
163 static boolean processIfCmp2(IR ir, BasicBlock bb, Instruction s) {
164 RegisterOperand guard = IfCmp2.getGuardResult(s);
165 Operand val1 = IfCmp2.getVal1(s);
166 Operand val2 = IfCmp2.getVal2(s);
167 int cond1 = IfCmp2.getCond1(s).evaluate(val1, val2);
168 int cond2 = IfCmp2.getCond2(s).evaluate(val1, val2);
169 if (cond1 == ConditionOperand.TRUE) {
170 // target 1 taken
171 insertTrueGuard(s, guard);
172 Goto.mutate(s, GOTO, IfCmp2.getTarget1(s));
173 removeBranchesAfterGotos(bb);
174 } else if ((cond1 == ConditionOperand.FALSE) && (cond2 == ConditionOperand.TRUE)) {
175 // target 2 taken
176 insertTrueGuard(s, guard);
177 Goto.mutate(s, GOTO, IfCmp2.getTarget2(s));
178 removeBranchesAfterGotos(bb);
179 } else if ((cond1 == ConditionOperand.FALSE) && (cond2 == ConditionOperand.FALSE)) {
180 // not taken
181 insertTrueGuard(s, guard);
182 s.remove();
183 } else if ((cond1 == ConditionOperand.FALSE) && (cond2 == ConditionOperand.UNKNOWN)) {
184 // target 1 not taken, simplify test to ifcmp
185 IfCmp.mutate(s,
186 INT_IFCMP,
187 guard,
188 val1,
189 val2,
190 IfCmp2.getCond2(s),
191 IfCmp2.getTarget2(s),
192 IfCmp2.getBranchProfile2(s));
193 } else if ((cond1 == ConditionOperand.UNKNOWN) && (cond2 == ConditionOperand.FALSE)) {
194 // target 1 taken possibly, simplify test to ifcmp
195 IfCmp.mutate(s,
196 INT_IFCMP,
197 guard,
198 val1,
199 val2,
200 IfCmp2.getCond1(s),
201 IfCmp2.getTarget1(s),
202 IfCmp2.getBranchProfile1(s));
203 } else if ((cond1 == ConditionOperand.UNKNOWN) && (cond2 == ConditionOperand.TRUE)) {
204 // target 1 taken possibly, simplify first test to ifcmp and
205 // insert goto after
206 s.insertAfter(Goto.create(GOTO, IfCmp2.getTarget2(s)));
207 IfCmp.mutate(s,
208 INT_IFCMP,
209 guard,
210 val1,
211 val2,
212 IfCmp2.getCond1(s),
213 IfCmp2.getTarget1(s),
214 IfCmp2.getBranchProfile1(s));
215 removeBranchesAfterGotos(bb);
216 } else {
217 if (val1.isConstant() && !val2.isConstant()) {
218 // Canonicalize by making second argument the constant
219 IfCmp2.setVal1(s, val2);
220 IfCmp2.setVal2(s, val1);
221 IfCmp2.setCond1(s, IfCmp2.getCond1(s).flipOperands());
222 IfCmp2.setCond2(s, IfCmp2.getCond2(s).flipOperands());
223 }
224 // we did no optimisation, return false
225 return false;
226 }
227 return true;
228 }
229
230 /** Process LookupSwitch branch instruction */
231 static boolean processLookupSwitch(IR ir, BasicBlock bb, Instruction s) {
232 Operand val = LookupSwitch.getValue(s);
233 int numMatches = LookupSwitch.getNumberOfMatches(s);
234 if (numMatches == 0) {
235 // Can only goto default
236 Goto.mutate(s, GOTO, LookupSwitch.getDefault(s));
237 } else if (val.isConstant()) {
238 // lookup value is constant
239 int value = ((IntConstantOperand) val).value;
240 BranchOperand target = LookupSwitch.getDefault(s);
241 for (int i = 0; i < numMatches; i++) {
242 if (value == LookupSwitch.getMatch(s, i).value) {
243 target = LookupSwitch.getTarget(s, i);
244 break;
245 }
246 }
247 Goto.mutate(s, GOTO, target);
248 } else if (numMatches == 1) {
249 // only 1 match, simplify to ifcmp
250 BranchOperand defaultTarget = LookupSwitch.getDefault(s);
251 IfCmp.mutate(s,
252 INT_IFCMP,
253 ir.regpool.makeTempValidation(),
254 val,
255 LookupSwitch.getMatch(s, 0),
256 ConditionOperand.EQUAL(),
257 LookupSwitch.getTarget(s, 0),
258 LookupSwitch.getBranchProfile(s, 0));
259 s.insertAfter(Goto.create(GOTO, defaultTarget));
260 } else {
261 // no optimisation, just continue
262 return false;
263 }
264 return true;
265 }
266
267 /** Process TableSwitch branch instruction */
268 static boolean processTableSwitch(IR ir, BasicBlock bb, Instruction s) {
269 Operand val = TableSwitch.getValue(s);
270 int low = TableSwitch.getLow(s).value;
271 int high = TableSwitch.getHigh(s).value;
272 if (val.isConstant()) {
273 int value = ((IntConstantOperand) val).value;
274 BranchOperand target = TableSwitch.getDefault(s);
275 if (value >= low && value <= high) {
276 target = TableSwitch.getTarget(s, value - low);
277 }
278 Goto.mutate(s, GOTO, target);
279 } else if (low == high) {
280 // only 1 match, simplify to ifcmp
281 BranchOperand defaultTarget = TableSwitch.getDefault(s);
282 IfCmp.mutate(s,
283 INT_IFCMP,
284 ir.regpool.makeTempValidation(),
285 val,
286 new IntConstantOperand(low),
287 ConditionOperand.EQUAL(),
288 TableSwitch.getTarget(s, 0),
289 TableSwitch.getBranchProfile(s, 0));
290 s.insertAfter(Goto.create(GOTO, defaultTarget));
291 } else {
292 // no optimisation, just continue
293 return false;
294 }
295 return true;
296 }
297
298 /** Process InlineGuard branch instruction */
299 static boolean processInlineGuard(IR ir, BasicBlock bb, Instruction s) {
300 Operand val = InlineGuard.getValue(s);
301 if (val.isNullConstant()) {
302 // branch not taken
303 s.remove();
304 return true;
305 } else if (val.isObjectConstant()) {
306 // TODO:
307 // VM.sysWrite("TODO: should constant fold MethodIfCmp on ObjectConstant");
308 }
309 return false;
310 }
311
312 /**
313 * To maintain IR integrity, remove any branches that are after the
314 * first GOTO in the basic block.
315 */
316 private static void removeBranchesAfterGotos(BasicBlock bb) {
317 // identify the first GOTO instruction in the basic block
318 Instruction firstGoto = null;
319 Instruction end = bb.lastRealInstruction();
320 for (InstructionEnumeration branches = bb.enumerateBranchInstructions(); branches.hasMoreElements();) {
321 Instruction s = branches.next();
322 if (Goto.conforms(s)) {
323 firstGoto = s;
324 break;
325 }
326 }
327 // remove all instructions after the first GOTO instruction
328 if (firstGoto != null) {
329 InstructionEnumeration ie = IREnumeration.forwardIntraBlockIE(firstGoto, end);
330 ie.next();
331 while (ie.hasMoreElements()) {
332 Instruction s = ie.next();
333 if (GuardResultCarrier.conforms(s)) {
334 insertTrueGuard(s, GuardResultCarrier.getGuardResult(s));
335 }
336 s.remove();
337 }
338 }
339 }
340
341 private static void insertTrueGuard(Instruction inst, RegisterOperand guard) {
342 if (guard == null) return; // Probably bad style but correct IR
343 Instruction trueGuard = Move.create(GUARD_MOVE, guard.copyD2D(), new TrueGuardOperand());
344 trueGuard.position = inst.position;
345 trueGuard.bcIndex = inst.bcIndex;
346 inst.insertBefore(trueGuard);
347 DefUse.updateDUForNewInstruction(trueGuard);
348 }
349 }