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 */
013package org.jikesrvm.compilers.opt.controlflow;
014
015import static org.jikesrvm.compilers.opt.ir.Operators.GOTO;
016import static org.jikesrvm.compilers.opt.ir.Operators.GUARD_MOVE;
017import static org.jikesrvm.compilers.opt.ir.Operators.INT_IFCMP;
018
019import java.util.Enumeration;
020
021import org.jikesrvm.compilers.opt.DefUse;
022import org.jikesrvm.compilers.opt.ir.BasicBlock;
023import org.jikesrvm.compilers.opt.ir.Goto;
024import org.jikesrvm.compilers.opt.ir.GuardResultCarrier;
025import org.jikesrvm.compilers.opt.ir.IR;
026import org.jikesrvm.compilers.opt.ir.IREnumeration;
027import org.jikesrvm.compilers.opt.ir.IfCmp;
028import org.jikesrvm.compilers.opt.ir.IfCmp2;
029import org.jikesrvm.compilers.opt.ir.InlineGuard;
030import org.jikesrvm.compilers.opt.ir.Instruction;
031import org.jikesrvm.compilers.opt.ir.LookupSwitch;
032import org.jikesrvm.compilers.opt.ir.Move;
033import org.jikesrvm.compilers.opt.ir.TableSwitch;
034import org.jikesrvm.compilers.opt.ir.operand.BranchOperand;
035import org.jikesrvm.compilers.opt.ir.operand.ConditionOperand;
036import org.jikesrvm.compilers.opt.ir.operand.IntConstantOperand;
037import org.jikesrvm.compilers.opt.ir.operand.Operand;
038import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand;
039import 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 */
050public 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   * @param ir the governing IR
062   * @return {@code true} if we do something, {@code false} otherwise.
063   */
064  public static boolean simplify(BasicBlock bb, IR ir) {
065    boolean didSomething = false;
066
067    for (Enumeration<Instruction> branches = bb.enumerateBranchInstructions(); branches.hasMoreElements();) {
068      Instruction s = branches.nextElement();
069      if (Goto.conforms(s)) {
070        // nothing to do, but a common case so test first
071      } else if (IfCmp.conforms(s)) {
072        if (processIfCmp(ir, bb, s)) {
073          // hack. Just start over since Enumeration has changed.
074          branches = bb.enumerateBranchInstructions();
075          bb.recomputeNormalOut(ir);
076          didSomething = true;
077        }
078      } else if (IfCmp2.conforms(s)) {
079        if (processIfCmp2(ir, bb, s)) {
080          // hack. Just start over since Enumeration has changed.
081          branches = bb.enumerateBranchInstructions();
082          bb.recomputeNormalOut(ir);
083          didSomething = true;
084        }
085      } else if (LookupSwitch.conforms(s)) {
086        if (processLookupSwitch(ir, bb, s)) {
087          // hack. Just start over since Enumeration has changed.
088          branches = bb.enumerateBranchInstructions();
089          bb.recomputeNormalOut(ir);
090          didSomething = true;
091        }
092      } else if (TableSwitch.conforms(s)) {
093        if (processTableSwitch(ir, bb, s)) {
094          // hack. Just start over since Enumeration has changed.
095          branches = bb.enumerateBranchInstructions();
096          bb.recomputeNormalOut(ir);
097          didSomething = true;
098        }
099      } else if (InlineGuard.conforms(s)) {
100        if (processInlineGuard(ir, bb, s)) {
101          // hack. Just start over since Enumeration has changed.
102          branches = bb.enumerateBranchInstructions();
103          bb.recomputeNormalOut(ir);
104          didSomething = true;
105        }
106      }
107    }
108    return didSomething;
109  }
110
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  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  static boolean processLookupSwitch(IR ir, BasicBlock bb, Instruction s) {
231    Operand val = LookupSwitch.getValue(s);
232    int numMatches = LookupSwitch.getNumberOfMatches(s);
233    if (numMatches == 0) {
234      // Can only goto default
235      Goto.mutate(s, GOTO, LookupSwitch.getDefault(s));
236    } else if (val.isConstant()) {
237      // lookup value is constant
238      int value = ((IntConstantOperand) val).value;
239      BranchOperand target = LookupSwitch.getDefault(s);
240      for (int i = 0; i < numMatches; i++) {
241        if (value == LookupSwitch.getMatch(s, i).value) {
242          target = LookupSwitch.getTarget(s, i);
243          break;
244        }
245      }
246      Goto.mutate(s, GOTO, target);
247    } else if (numMatches == 1) {
248      // only 1 match, simplify to ifcmp
249      BranchOperand defaultTarget = LookupSwitch.getDefault(s);
250      IfCmp.mutate(s,
251                   INT_IFCMP,
252                   ir.regpool.makeTempValidation(),
253                   val,
254                   LookupSwitch.getMatch(s, 0),
255                   ConditionOperand.EQUAL(),
256                   LookupSwitch.getTarget(s, 0),
257                   LookupSwitch.getBranchProfile(s, 0));
258      s.insertAfter(Goto.create(GOTO, defaultTarget));
259    } else {
260      // no optimisation, just continue
261      return false;
262    }
263    return true;
264  }
265
266  static boolean processTableSwitch(IR ir, BasicBlock bb, Instruction s) {
267    Operand val = TableSwitch.getValue(s);
268    int low = TableSwitch.getLow(s).value;
269    int high = TableSwitch.getHigh(s).value;
270    if (val.isConstant()) {
271      int value = ((IntConstantOperand) val).value;
272      BranchOperand target = TableSwitch.getDefault(s);
273      if (value >= low && value <= high) {
274        target = TableSwitch.getTarget(s, value - low);
275      }
276      Goto.mutate(s, GOTO, target);
277    } else if (low == high) {
278      // only 1 match, simplify to ifcmp
279      BranchOperand defaultTarget = TableSwitch.getDefault(s);
280      IfCmp.mutate(s,
281                   INT_IFCMP,
282                   ir.regpool.makeTempValidation(),
283                   val,
284                   new IntConstantOperand(low),
285                   ConditionOperand.EQUAL(),
286                   TableSwitch.getTarget(s, 0),
287                   TableSwitch.getBranchProfile(s, 0));
288      s.insertAfter(Goto.create(GOTO, defaultTarget));
289    } else {
290      // no optimisation, just continue
291      return false;
292    }
293    return true;
294  }
295
296  static boolean processInlineGuard(IR ir, BasicBlock bb, Instruction s) {
297    Operand val = InlineGuard.getValue(s);
298    if (val.isNullConstant()) {
299      // branch not taken
300      s.remove();
301      return true;
302    } else if (val.isObjectConstant()) {
303      // TODO:
304      // VM.sysWrite("TODO: should constant fold MethodIfCmp on ObjectConstant");
305    }
306    return false;
307  }
308
309  /**
310   * To maintain IR integrity, remove any branches that are after the
311   * first GOTO in the basic block.
312   *
313   * @param bb the block to search for gotos
314   */
315  private static void removeBranchesAfterGotos(BasicBlock bb) {
316    // identify the first GOTO instruction in the basic block
317    Instruction firstGoto = null;
318    Instruction end = bb.lastRealInstruction();
319    for (Enumeration<Instruction> branches = bb.enumerateBranchInstructions(); branches.hasMoreElements();) {
320      Instruction s = branches.nextElement();
321      if (Goto.conforms(s)) {
322        firstGoto = s;
323        break;
324      }
325    }
326    // remove all instructions after the first GOTO instruction
327    if (firstGoto != null) {
328      Enumeration<Instruction> ie = IREnumeration.forwardIntraBlockIE(firstGoto, end);
329      ie.nextElement();
330      while (ie.hasMoreElements()) {
331        Instruction s = ie.nextElement();
332        if (GuardResultCarrier.conforms(s)) {
333          insertTrueGuard(s, GuardResultCarrier.getGuardResult(s));
334        }
335        s.remove();
336      }
337    }
338  }
339
340  private static void insertTrueGuard(Instruction inst, RegisterOperand guard) {
341    if (guard == null) return;  // Probably bad style but correct IR
342    Instruction trueGuard = Move.create(GUARD_MOVE, guard.copyD2D(), new TrueGuardOperand());
343    trueGuard.position = inst.position;
344    trueGuard.bcIndex = inst.bcIndex;
345    inst.insertBefore(trueGuard);
346    DefUse.updateDUForNewInstruction(trueGuard);
347  }
348}