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;
016
017import java.util.Enumeration;
018import java.util.HashMap;
019import java.util.LinkedHashMap;
020import java.util.LinkedHashSet;
021import java.util.TreeSet;
022
023import org.jikesrvm.VM;
024import org.jikesrvm.compilers.opt.OptOptions;
025import org.jikesrvm.compilers.opt.driver.CompilerPhase;
026import org.jikesrvm.compilers.opt.ir.BasicBlock;
027import org.jikesrvm.compilers.opt.ir.Goto;
028import org.jikesrvm.compilers.opt.ir.IR;
029import org.jikesrvm.compilers.opt.ir.Instruction;
030import org.jikesrvm.compilers.opt.ir.WeightedBranchTargets;
031import org.jikesrvm.compilers.opt.ir.operand.BranchOperand;
032
033/**
034 * Reorder code layout of basic blocks for improved I-cache locality and
035 * branch prediction. This code assumes that basic block frequencies have
036 * been computed and blocks have been marked infrequent.
037 * This pass actually implements two code placement algorithms:
038 * <ul>
039 *  <li>(1) A simple 'fluff' removal pass that moves all infrequent basic blocks
040 *     to the end of the code order.
041 *  <li>(2) Pettis and Hansen Algo2.
042 * </ul>
043 */
044public final class ReorderingPhase extends CompilerPhase {
045
046  private static final boolean DEBUG = false;
047
048  /**
049   * Return this instance of this phase. This phase contains no
050   * per-compilation instance fields.
051   * @param ir not used
052   * @return this
053   */
054  @Override
055  public CompilerPhase newExecution(IR ir) {
056    return this;
057  }
058
059  @Override
060  public boolean shouldPerform(OptOptions options) {
061    return options.REORDER_CODE;
062  }
063
064  @Override
065  public boolean printingEnabled(OptOptions options, boolean before) {
066    return DEBUG;
067  }
068
069  @Override
070  public String getName() {
071    return "Code Reordering";
072  }
073
074  /**
075   * Reorder basic blocks either by trivially moving infrequent blocks
076   * to the end of the code order or by applying Pettis and Hansen Algo2.
077   *
078   * We will rearrange basic blocks and insert/remove
079   * unconditional GOTO's if needed.  It does not clean up branches,
080   * by reversing the branch condition, however.  That is saved for
081   * BranchOptimizations.
082   */
083  @Override
084  public void perform(IR ir) {
085    ir.cfg.entry().clearInfrequent();
086    if (ir.options.REORDER_CODE_PH) {
087      // Do Pettis and Hansen PLDI'90 Algo2
088      doPettisHansenAlgo2(ir);
089    } else {
090      // Simple algorithm: just move infrequent code to the end
091      exileInfrequentBlocks(ir);
092    }
093  }
094
095  /////////////////////////
096  // Code for trivial algorithm
097  /////////////////////////
098
099  /**
100   * Select a new basic block ordering via a simple heuristic
101   * that moves all infrequent basic blocks to the end.
102   * @param ir the IR object to reorder
103   */
104  private void exileInfrequentBlocks(IR ir) {
105    // (1) Look to see if there are infrequent blocks
106    //     Also count how many blocks there are.
107    int numBlocks = 0;
108    boolean foundSome = false;
109    for (Enumeration<BasicBlock> e = ir.getBasicBlocks(); e.hasMoreElements();) {
110      BasicBlock bb = e.nextElement();
111      numBlocks++;
112      foundSome |= bb.getInfrequent();
113    }
114    if (!foundSome) return; // Nothing to do
115
116    // Reorder the blocks to exile the infrequent blocks.
117    // Relative order within the set of frequent and infrequent is unchanged.
118    BasicBlock[] newOrdering = new BasicBlock[numBlocks];
119    int idx = 0;
120    // First append frequent blocks to newOrdering
121    for (BasicBlock bb = ir.cfg.firstInCodeOrder(); bb != null; bb = bb.nextBasicBlockInCodeOrder()) {
122      if (!bb.getInfrequent()) {
123        newOrdering[idx++] = bb;
124      }
125    }
126    // Next append infrequent blocks to newOrdering
127    for (BasicBlock bb = ir.cfg.firstInCodeOrder(); bb != null; bb = bb.nextBasicBlockInCodeOrder()) {
128      if (bb.getInfrequent()) {
129        newOrdering[idx++] = bb;
130      }
131    }
132
133    if (VM.VerifyAssertions) VM._assert(idx == numBlocks); // don't lose blocks!
134    if (VM.VerifyAssertions) VM._assert(ir.cfg.entry() == newOrdering[0]);
135
136    // Add/remove unconditional goto's as needed.
137    for (int i = 0; i < newOrdering.length; i++) {
138      Instruction lastInstr = newOrdering[i].lastRealInstruction();
139      // Append a GOTO if needed to maintain old fallthrough semantics.
140      BasicBlock fallthroughBlock = newOrdering[i].getFallThroughBlock();
141      if (fallthroughBlock != null) {
142        if (i == newOrdering.length - 1 || fallthroughBlock != newOrdering[i + 1]) {
143          // Add unconditional goto to preserve old fallthrough semantics
144          newOrdering[i].appendInstruction(fallthroughBlock.makeGOTO());
145        }
146      }
147      // Remove last instruction if it is a redundant GOTO that
148      // can be implemented by a fallthrough edge in the new ordering.
149      // (Only possible if newOrdering[i] is not the last basic block.)
150      if (i < newOrdering.length - 1 && lastInstr != null && lastInstr.operator() == GOTO) {
151        BranchOperand op = Goto.getTarget(lastInstr);
152        if (op.target.getBasicBlock() == newOrdering[i + 1]) {
153          // unconditional goto is redundant in new ordering
154          lastInstr.remove();
155        }
156      }
157    }
158
159    // Re-insert all basic blocks according to new ordering
160    ir.cfg.clearCodeOrder();
161    for (BasicBlock bb : newOrdering) {
162      ir.cfg.addLastInCodeOrder(bb);
163    }
164  }
165
166  /////////////////////////
167  // Code for P&H Algo2
168  /////////////////////////
169
170  /**
171   * Reorder code using Algo2 (Bottom-Up Positioning) from
172   * Pettis and Hansen PLDI'90.
173   * @param ir the IR to reorder.
174   */
175  private void doPettisHansenAlgo2(IR ir) {
176    // (1) Setup:
177    //     (a) Count the blocks
178    //     (b) Create a sorted set of CFG edges
179    //     (c) Create a set of blocks
180    //     (d) Make fallthroughs explict by adding GOTOs
181    int numBlocks = 0;
182    TreeSet<Edge> edges = new TreeSet<Edge>();
183    LinkedHashSet<BasicBlock> chainHeads = new LinkedHashSet<BasicBlock>();
184    HashMap<BasicBlock, BasicBlock> associatedChain = new HashMap<BasicBlock, BasicBlock>();
185    BasicBlock entry = ir.cfg.entry();
186    if (VM.VerifyAssertions) VM._assert(ir.cfg.entry() == ir.cfg.firstInCodeOrder());
187
188    for (BasicBlock bb = entry; bb != null; bb = bb.nextBasicBlockInCodeOrder()) {
189      numBlocks++;
190      chainHeads.add(bb);
191      associatedChain.put(bb, bb);
192      BasicBlock ft = bb.getFallThroughBlock();
193      if (ft != null) {
194        bb.appendInstruction(Goto.create(GOTO, ft.makeJumpTarget()));
195      }
196      float bw = bb.getExecutionFrequency();
197      for (WeightedBranchTargets wbt = new WeightedBranchTargets(bb); wbt.hasMoreElements(); wbt.advance()) {
198        edges.add(new Edge(bb, wbt.curBlock(), wbt.curWeight() * bw));
199      }
200    }
201
202    if (DEBUG) VM.sysWriteln("Edges = " + edges);
203
204    // (2) Build chains
205    ir.cfg.clearCodeOrder();
206    for (Edge e : edges) {
207      // If the source of the edge is the last block in its chain
208      // and the target of the edge is the first block in its chain
209      // then merge the chains.
210      if (DEBUG) VM.sysWriteln("Processing edge " + e);
211      if (e.target == entry) {
212        if (DEBUG) VM.sysWriteln("\tCan't put entry block in interior of chain");
213        continue;
214      }
215      if (e.source.nextBasicBlockInCodeOrder() != null) {
216        if (DEBUG) VM.sysWriteln("\tSource is not at end of a chain");
217        continue;
218      }
219      if (e.target.prevBasicBlockInCodeOrder() != null) {
220        if (DEBUG) VM.sysWriteln("\tTarget is not at start of a chain");
221        continue;
222      }
223      BasicBlock sourceChain = associatedChain.get(e.source);
224      BasicBlock targetChain = associatedChain.get(e.target);
225      if (sourceChain == targetChain) {
226        if (DEBUG) VM.sysWriteln("\tSource and target are in same chain");
227        continue;
228      }
229      if (DEBUG) VM.sysWriteln("\tMerging chains");
230      chainHeads.remove(e.target);
231      ir.cfg.linkInCodeOrder(e.source, e.target);
232      // Yuck....we should really use near-linear time union find here
233      // Doing this crappy thing makes us O(N^2) in the worst case.
234      BasicBlock newChain = sourceChain;
235      for (BasicBlock ptr = e.target; ptr != null; ptr = ptr.nextBasicBlockInCodeOrder()) {
236        associatedChain.put(ptr, newChain);
237      }
238    }
239
240    if (DEBUG) VM.sysWriteln("Chains constructed ");
241    LinkedHashMap<BasicBlock, ChainInfo> chainInfo = new LinkedHashMap<BasicBlock, ChainInfo>();
242    for (BasicBlock head : chainHeads) {
243      if (DEBUG) dumpChain(head);
244      chainInfo.put(head, new ChainInfo(head));
245    }
246
247    // (3) Summarize inter-chain edges.
248    for (Edge e : edges) {
249      BasicBlock sourceChain = associatedChain.get(e.source);
250      BasicBlock targetChain = associatedChain.get(e.target);
251      if (sourceChain != targetChain) {
252        ChainInfo sourceInfo = chainInfo.get(sourceChain);
253        ChainInfo targetInfo = chainInfo.get(targetChain);
254        if (DEBUG) VM.sysWriteln("Inter-chain edge " + sourceChain + "->" + targetChain + " (" + e.weight + ")");
255        Float value = sourceInfo.outWeights.get(targetInfo);
256        float weight = e.weight;
257        if (value != null) {
258          weight += value;
259        }
260        sourceInfo.outWeights.put(targetInfo, weight);
261        targetInfo.inWeight += e.weight;
262        if (DEBUG) VM.sysWriteln("\t" + targetInfo + "," + sourceInfo.outWeights.get(targetInfo));
263      }
264    }
265
266    if (DEBUG) VM.sysWriteln("Chain Info " + chainInfo);
267
268    // (4) Construct a total order of the chains, guided by the interchain edge weights.
269    //     Constructing an optimal order is NP-Hard, so we apply the following heuristic.
270    //     The chain that starts with the entry node is placed first.
271    //     At each step, pick the chain with the maximal placedWeight (incoming edges from chains
272    //     that are already placed) and minimal inWeight (incoming edges from chains that are not
273    //     already placed). Prefer a node with non-zero placedWeight and inWeight to one that has
274    //     zeros for both. (A node with both zero placedWeight and zero inWeight is something that
275    //     the profile data predicts is not reachable via normal control flow from the entry node).
276    BasicBlock lastNode = null;
277    ChainInfo nextChoice = chainInfo.get(entry);
278    int numPlaced = 0;
279    ir.cfg.setFirstNode(entry);
280    while (true) {
281      if (DEBUG) VM.sysWriteln("Placing chain " + nextChoice);
282      // Append nextChoice to the previous chain
283      if (lastNode != null) ir.cfg.linkInCodeOrder(lastNode, nextChoice.head);
284      for (BasicBlock ptr = nextChoice.head; ptr != null; ptr = ptr.nextBasicBlockInCodeOrder()) {
285        numPlaced++;
286        lastNode = ptr;
287      }
288      // update ChainInfo
289      chainInfo.remove(nextChoice.head);
290      if (chainInfo.isEmpty()) break; // no chains left to place.
291      for (ChainInfo target : nextChoice.outWeights.keySet()) {
292        if (DEBUG) VM.sysWrite("\toutedge " + target);
293        float weight = nextChoice.outWeights.get(target);
294        if (DEBUG) VM.sysWriteln(" = " + weight);
295        target.placedWeight += weight;
296        target.inWeight -= weight;
297      }
298
299      if (DEBUG) VM.sysWriteln("Chain Info " + chainInfo);
300
301      // Find the next chain to append.
302      nextChoice = null;
303      for (ChainInfo cand : chainInfo.values()) {
304        if (cand.placedWeight > 0f) {
305          if (nextChoice == null) {
306            if (DEBUG) VM.sysWriteln("First reachable candidate " + cand);
307            nextChoice = cand;
308          } else if (cand.inWeight > nextChoice.inWeight ||
309                     (cand.inWeight == nextChoice.inWeight && cand.placedWeight > nextChoice.placedWeight)) {
310            if (DEBUG) VM.sysWriteln(cand + " is a better choice than " + nextChoice);
311            nextChoice = cand;
312          }
313        }
314      }
315      if (nextChoice != null) continue;
316
317      // All remaining chains are fluff (not reachable from entry).
318      // Pick one with minimal inWeight and continue.
319      for (ChainInfo cand : chainInfo.values()) {
320        if (nextChoice == null) {
321          if (DEBUG) VM.sysWriteln("First candidate " + cand);
322          nextChoice = cand;
323        } else if (cand.inWeight < nextChoice.inWeight) {
324          if (DEBUG) VM.sysWriteln(cand + " is a better choice than " + nextChoice);
325          nextChoice = cand;
326        }
327      }
328    }
329
330    if (VM.VerifyAssertions) VM._assert(numPlaced == numBlocks); // Don't lose blocks!!
331    ir.cfg.setLastNode(lastNode);
332  }
333
334  private void dumpChain(BasicBlock head) {
335    VM.sysWrite("{" + head);
336    for (BasicBlock next = head.nextBasicBlockInCodeOrder(); next != null; next = next.nextBasicBlockInCodeOrder()) {
337      VM.sysWrite(", " + next);
338    }
339    VM.sysWriteln("}");
340  }
341
342  private static class ChainInfo {
343    final BasicBlock head;
344    float placedWeight;
345    float inWeight;
346    final HashMap<ChainInfo, Float> outWeights = new HashMap<ChainInfo, Float>();
347
348    ChainInfo(BasicBlock h) {
349      head = h;
350    }
351
352    @Override
353    public String toString() {
354      return "[" + head + "," + placedWeight + "," + inWeight + "] " + outWeights.size();
355    }
356  }
357
358  private static final class Edge implements Comparable<Edge> {
359
360    final BasicBlock source;
361    final BasicBlock target;
362    final float weight;
363
364    Edge(BasicBlock s, BasicBlock t, float w) {
365      source = s;
366      target = t;
367      weight = w;
368    }
369
370    @Override
371    public String toString() {
372      return weight + ": " + source + " -> " + target;
373    }
374
375    @Override
376    public int hashCode() {
377      final int prime = 31;
378      int result = 1;
379      result = prime * result + ((source == null) ? 0 : source.hashCode());
380      result = prime * result + ((target == null) ? 0 : target.hashCode());
381      result = prime * result + Float.floatToIntBits(weight);
382      return result;
383    }
384
385    @Override
386    public boolean equals(Object obj) {
387      if (this == obj)
388        return true;
389      if (obj == null)
390        return false;
391      if (getClass() != obj.getClass())
392        return false;
393      Edge other = (Edge) obj;
394      if (source == null) {
395        if (other.source != null)
396          return false;
397      } else if (!source.equals(other.source))
398        return false;
399      if (target == null) {
400        if (other.target != null)
401          return false;
402      } else if (!target.equals(other.target))
403        return false;
404      if (Float.floatToIntBits(weight) != Float.floatToIntBits(other.weight))
405        return false;
406      return true;
407    }
408
409    @Override
410    public int compareTo(Edge that) {
411      if (weight < that.weight) {
412        return 1;
413      } else if (weight > that.weight) {
414        return -1;
415      } else {
416        // Equal weights.
417        // Sort based on original code ordering, which is implied by block number
418        if (source.getNumber() < that.source.getNumber()) {
419          return 1;
420        } else if (source.getNumber() > that.source.getNumber()) {
421          return -1;
422        } else {
423          if (target.getNumber() > that.target.getNumber()) {
424            return 1;
425          } else if (source.getNumber() < that.target.getNumber()) {
426            return -1;
427          } else {
428            return 0;
429          }
430        }
431      }
432    }
433  }
434}