float placedWeight = 0f;
  private void doPettisHansenAlgo2(OPT_IR ir) {    // (1) Setup:    //     (a) Count the blocks    //     (b) Create a sorted set of CFG edges    //     (c) Create a set of blocks    //     (d) Make fallthroughs explict by adding GOTOs    int numBlocks = 0;    SortedSet edges = new TreeSet();    Set chainHeads = new HashSet();    OPT_BasicBlock entry = ir.cfg.entry();    if (VM.VerifyAssertions) VM._assert(ir.cfg.entry() == ir.cfg.firstInCodeOrder());    for (OPT_BasicBlock bb = entry;         bb != null;          bb = bb.nextBasicBlockInCodeOrder()) {      numBlocks++;      chainHeads.add(bb);      bb.scratchObject = bb;      OPT_BasicBlock ft = bb.getFallThroughBlock();      if (ft != null) {         bb.appendInstruction(Goto.create(GOTO, ft.makeJumpTarget()));      }      float bw = bb.getExecutionFrequency();      for (OPT_WeightedBranchTargets wbt = new OPT_WeightedBranchTargets(bb);           wbt.hasMoreElements(); wbt.advance()) {        edges.add(new Edge(bb, wbt.curBlock(), wbt.curWeight() * bw));      }    }    if (DEBUG) VM.sysWriteln("Edges = "+edges);    // (2) Build chains    ir.cfg.clearCodeOrder();    for (Iterator edgesI = edges.iterator(); edgesI.hasNext();) {      Edge e = (Edge)edgesI.next();      // If the source of the edge is the last block in its chain      // and the target of the edge is the first block in its chain      // then merge the chains.      if (DEBUG) VM.sysWriteln("Processing edge "+e);      if (e.target == entry) {        if (DEBUG) VM.sysWriteln("\tCan't put entry block in interior of chain");        continue;       }      if (e.source.nextBasicBlockInCodeOrder() != null) {        if (DEBUG) VM.sysWriteln("\tSource is not at end of a chain");        continue;       }      if (e.target.prevBasicBlockInCodeOrder() != null) {        if (DEBUG) VM.sysWriteln("\tTarget is not at start of a chain");        continue;      }      if (e.source.scratchObject == e.target.scratchObject) {        if (DEBUG) VM.sysWriteln("\tSource and target are in same chain");        continue;      }      if (DEBUG) VM.sysWriteln("\tMerging chains");      chainHeads.remove(e.target);      ir.cfg.linkInCodeOrder(e.source, e.target);      // Yuck....we should really use near-linear time union find here      // Doing this crappy thing makes us O(N^2) in the worst case.      OPT_BasicBlock newChain = (OPT_BasicBlock)e.source.scratchObject;      for (OPT_BasicBlock ptr = e.target;           ptr != null;           ptr = ptr.nextBasicBlockInCodeOrder()) {        ptr.scratchObject = newChain;      }    }    if (DEBUG) VM.sysWriteln("Chains constructed ");    Map chainInfo = new HashMap();    for (Iterator chainI = chainHeads.iterator(); chainI.hasNext();) {      OPT_BasicBlock head = (OPT_BasicBlock)chainI.next();      if (DEBUG) dumpChain(head);      chainInfo.put(head, new ChainInfo(head));    }          // (3) Summarize inter-chain edges.    for (Iterator edgesI = edges.iterator(); edgesI.hasNext();) {      Edge e = (Edge)edgesI.next();      if (e.source.scratchObject != e.target.scratchObject) {        Object sourceChain = e.source.scratchObject;        Object targetChain = e.target.scratchObject;        ChainInfo sourceInfo = (ChainInfo)chainInfo.get(sourceChain);        ChainInfo targetInfo = (ChainInfo)chainInfo.get(targetChain);        if (DEBUG) VM.sysWriteln("Inter-chain edge "+sourceChain+"->"+targetChain+" ("+e.weight+")");        Object value = sourceInfo.outWeights.get(targetInfo);        float weight = e.weight;        if (value != null) {          weight += ((Float)value).floatValue();        }        sourceInfo.outWeights.put(targetInfo, new Float(weight));        targetInfo.inWeight += e.weight;        if (DEBUG) VM.sysWriteln("\t"+targetInfo + ","+sourceInfo.outWeights.get(targetInfo));      }    }    if (DEBUG) VM.sysWriteln("Chain Info "+chainInfo);    // (4) Construct a total order of the chains, guided by the interchain edge weights.    //     Constructing an optimal order is NP-Hard, so we apply the following heuristic.    //     The chain that starts with the entry node is placed first.    //     At each step, pick the chain with the maximal placedWeight (incoming edges from chains    //     that are already placed) and minimal inWeight (incoming edges from chains that are not     //     already placed). Prefer a node with non-zero placedWeight and inWeight to one that has    //     zeros for both. (A node with both zero placedWeight and zero inWeight is something that    //     the profile data predicts is not reachable via normal control flow from the entry node).    OPT_BasicBlock lastNode = null;    ChainInfo nextChoice = (ChainInfo)chainInfo.get(entry);    int numPlaced = 0;    ir.cfg._firstNode = entry;    while (true) {      if (DEBUG) VM.sysWriteln("Placing chain "+nextChoice);      // Append nextChoice to the previous chain      if (lastNode != null) ir.cfg.linkInCodeOrder(lastNode, nextChoice.head);      for (OPT_BasicBlock ptr = nextChoice.head;            ptr != null;            ptr = ptr.nextBasicBlockInCodeOrder()) {        numPlaced++;        lastNode = ptr;      }      // update ChainInfo      chainInfo.remove(nextChoice.head);      if (chainInfo.isEmpty()) break; // no chains left to place.      for (Iterator i = nextChoice.outWeights.keySet().iterator(); i.hasNext();) {        ChainInfo target = (ChainInfo)i.next();        if (DEBUG) VM.sysWrite("\toutedge "+target);        float weight = ((Float)nextChoice.outWeights.get(target)).floatValue();        if (DEBUG) VM.sysWriteln(" = "+weight);        target.placedWeight += weight;        target.inWeight -= weight;      }      if (DEBUG) VM.sysWriteln("Chain Info "+chainInfo);      // Find the next chain to append.      nextChoice = null;      float placedWeight = 0f;      for (Iterator i = chainInfo.values().iterator(); i.hasNext();) {        ChainInfo cand = (ChainInfo)i.next();        if (cand.placedWeight > 0f) {          if (nextChoice == null) {            if (DEBUG) VM.sysWriteln("First reachable candidate "+cand);            nextChoice = cand;          } else if (cand.inWeight > nextChoice.inWeight ||                     (cand.inWeight == nextChoice.inWeight &&                       cand.placedWeight > nextChoice.placedWeight)) {            if (DEBUG) VM.sysWriteln(cand + " is a better choice than "+nextChoice);            nextChoice = cand;          }        }      }      if (nextChoice != null) continue;      // All remaining chains are fluff (not reachable from entry).      // Pick one with minimal inWeight and continue.      for (Iterator i = chainInfo.values().iterator(); i.hasNext();) {        ChainInfo cand = (ChainInfo)i.next();        if (nextChoice == null) {          if (DEBUG) VM.sysWriteln("First candidate "+cand);          nextChoice = cand;        } else if (cand.inWeight < nextChoice.inWeight) {          if (DEBUG) VM.sysWriteln(cand + " is a better choice than "+nextChoice);          nextChoice = cand;        }      }    }    if (VM.VerifyAssertions) VM._assert(numPlaced == numBlocks); // Don't lose blocks!!    ir.cfg._lastNode = lastNode;  }