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