1 files changed, 101 insertions, 84 deletions

diff --git a/lib/Target/PowerPC/PPCBranchSelector.cpp b/lib/Target/PowerPC/PPCBranchSelector.cpp
index db85738ccc..f3d3124358 100644
--- a/lib/Target/PowerPC/PPCBranchSelector.cpp
+++ b/lib/Target/PowerPC/PPCBranchSelector.cpp
@@ -24,6 +24,7 @@
 #include "llvm/Target/TargetAsmInfo.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Support/Compiler.h"
+#include "llvm/Support/MathExtras.h"
 using namespace llvm;
 
 static Statistic<> NumExpanded("ppc-branch-select",
@@ -31,13 +32,13 @@ static Statistic<> NumExpanded("ppc-branch-select",
 
 namespace {
   struct VISIBILITY_HIDDEN PPCBSel : public MachineFunctionPass {
-    /// OffsetMap - Mapping between BB # and byte offset from start of function.
-    std::vector<unsigned> OffsetMap;
+    /// BlockSizes - The sizes of the basic blocks in the function.
+    std::vector<unsigned> BlockSizes;
 
     virtual bool runOnMachineFunction(MachineFunction &Fn);
 
     virtual const char *getPassName() const {
-      return "PowerPC Branch Selection";
+      return "PowerPC Branch Selector";
     }
   };
 }
@@ -54,11 +55,6 @@ FunctionPass *llvm::createPPCBranchSelectionPass() {
 ///
 static unsigned getNumBytesForInstruction(MachineInstr *MI) {
   switch (MI->getOpcode()) {
-  case PPC::BCC:
-    // while this will be 4 most of the time, if we emit 8 it is just a
-    // minor pessimization that saves us from having to worry about
-    // keeping the offsets up to date later when we emit long branch glue.
-    return 8;
   case PPC::IMPLICIT_DEF_GPRC: // no asm emitted
   case PPC::IMPLICIT_DEF_G8RC: // no asm emitted
   case PPC::IMPLICIT_DEF_F4:   // no asm emitted
@@ -77,98 +73,119 @@ static unsigned getNumBytesForInstruction(MachineInstr *MI) {
 
 
 bool PPCBSel::runOnMachineFunction(MachineFunction &Fn) {
-  // Running total of instructions encountered since beginning of function
-  unsigned ByteCount = 0;
-  
-  OffsetMap.resize(Fn.getNumBlockIDs());
-  
-  // For each MBB, add its offset to the offset map, and count up its
-  // instructions
+  // Give the blocks of the function a dense, in-order, numbering.
+  Fn.RenumberBlocks();
+  BlockSizes.resize(Fn.getNumBlockIDs());
+
+  // Measure each MBB and compute a size for the entire function.
+  unsigned FuncSize = 0;
   for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E;
        ++MFI) {
     MachineBasicBlock *MBB = MFI;
-    OffsetMap[MBB->getNumber()] = ByteCount;
-    
+
+    unsigned BlockSize = 0;
     for (MachineBasicBlock::iterator MBBI = MBB->begin(), EE = MBB->end();
          MBBI != EE; ++MBBI)
-      ByteCount += getNumBytesForInstruction(MBBI);
+      BlockSize += getNumBytesForInstruction(MBBI);
+    
+    BlockSizes[MBB->getNumber()] = BlockSize;
+    FuncSize += BlockSize;
   }
   
-  // We're about to run over the MBB's again, so reset the ByteCount
-  ByteCount = 0;
+  // If the entire function is smaller than the displacement of a branch field,
+  // we know we don't need to shrink any branches in this function.  This is a
+  // common case.
+  if (FuncSize < (1 << 15)) {
+    BlockSizes.clear();
+    return false;
+  }
   
-  // For each MBB, find the conditional branch pseudo instructions, and
-  // calculate the difference between the target MBB and the current ICount
-  // to decide whether or not to emit a short or long branch.
-  //
-  // short branch:
-  // bCC .L_TARGET_MBB
+  // For each conditional branch, if the offset to its destination is larger
+  // than the offset field allows, transform it into a long branch sequence
+  // like this:
+  //   short branch:
+  //     bCC MBB
+  //   long branch:
+  //     b!CC $PC+8
+  //     b MBB
   //
-  // long branch:
-  // bInverseCC $PC+8
-  // b .L_TARGET_MBB
-  for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E;
-       ++MFI) {
-    MachineBasicBlock *MBB = MFI;
-    
-    for (MachineBasicBlock::iterator MBBI = MBB->begin(), EE = MBB->end();
-         MBBI != EE; ++MBBI) {
-      // We may end up deleting the MachineInstr that MBBI points to, so
-      // remember its opcode now so we can refer to it after calling erase()
-      unsigned ByteSize = getNumBytesForInstruction(MBBI);
-      if (MBBI->getOpcode() != PPC::BCC) {
-        ByteCount += ByteSize;
-        continue;
-      }
-      
-      // condbranch operands:
-      // 0. CR register
-      // 1. PPC branch opcode
-      // 2. Target MBB
-      MachineBasicBlock *DestMBB = MBBI->getOperand(2).getMachineBasicBlock();
-      PPC::Predicate Pred = (PPC::Predicate)MBBI->getOperand(0).getImm();
-      unsigned CRReg = MBBI->getOperand(1).getReg();
-      int Displacement = OffsetMap[DestMBB->getNumber()] - ByteCount;
+  bool MadeChange = true;
+  bool EverMadeChange = false;
+  while (MadeChange) {
+    // Iteratively expand branches until we reach a fixed point.
+    MadeChange = false;
+  
+    for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E;
+         ++MFI) {
+      MachineBasicBlock &MBB = *MFI;
+      unsigned MBBStartOffset = 0;
+      for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end();
+           I != E; ++I) {
+        if (I->getOpcode() != PPC::BCC || I->getOperand(2).isImm()) {
+          MBBStartOffset += getNumBytesForInstruction(I);
+          continue;
+        }
+        
+        // Determine the offset from the current branch to the destination
+        // block.
+        MachineBasicBlock *Dest = I->getOperand(2).getMachineBasicBlock();
+        
+        int BranchSize;
+        if (Dest->getNumber() <= MBB.getNumber()) {
+          // If this is a backwards branch, the delta is the offset from the
+          // start of this block to this branch, plus the sizes of all blocks
+          // from this block to the dest.
+          BranchSize = MBBStartOffset;
+          
+          for (unsigned i = Dest->getNumber(), e = MBB.getNumber(); i != e; ++i)
+            BranchSize += BlockSizes[i];
+        } else {
+          // Otherwise, add the size of the blocks between this block and the
+          // dest to the number of bytes left in this block.
+          BranchSize = -MBBStartOffset;
+
+          for (unsigned i = MBB.getNumber(), e = Dest->getNumber(); i != e; ++i)
+            BranchSize += BlockSizes[i];
+        }
 
-      bool ShortBranchOk = Displacement >= -32768 && Displacement <= 32767;
-      
-      // Branch on opposite condition if a short branch isn't ok.
-      if (!ShortBranchOk)
-        Pred = PPC::InvertPredicate(Pred);
+        // If this branch is in range, ignore it.
+        if (isInt16(BranchSize)) {
+          MBBStartOffset += 4;
+          continue;
+        }
         
-      unsigned Opcode;
-      switch (Pred) {
-      default: assert(0 && "Unknown cond branch predicate!");
-      case PPC::PRED_LT: Opcode = PPC::BLT; break;
-      case PPC::PRED_LE: Opcode = PPC::BLE; break;
-      case PPC::PRED_EQ: Opcode = PPC::BEQ; break;
-      case PPC::PRED_GE: Opcode = PPC::BGE; break;
-      case PPC::PRED_GT: Opcode = PPC::BGT; break;
-      case PPC::PRED_NE: Opcode = PPC::BNE; break;
-      case PPC::PRED_UN: Opcode = PPC::BUN; break;
-      case PPC::PRED_NU: Opcode = PPC::BNU; break;
-      }
-      
-      MachineBasicBlock::iterator MBBJ;
-      if (ShortBranchOk) {
-        MBBJ = BuildMI(*MBB, MBBI, Opcode, 2).addReg(CRReg).addMBB(DestMBB);
-      } else {
-        // Long branch, skip next branch instruction (i.e. $PC+8).
+        // Otherwise, we have to expand it to a long branch.
+        // The BCC operands are:
+        // 0. PPC branch predicate
+        // 1. CR register
+        // 2. Target MBB
+        PPC::Predicate Pred = (PPC::Predicate)I->getOperand(0).getImm();
+        unsigned CRReg = I->getOperand(1).getReg();
+        
+        MachineInstr *OldBranch = I;
+        
+        // Jump over the uncond branch inst (i.e. $PC+8) on opposite condition.
+        BuildMI(MBB, I, PPC::BCC, 3)
+          .addImm(PPC::InvertPredicate(Pred)).addReg(CRReg).addImm(2);
+        
+        // Uncond branch to the real destination.
+        I = BuildMI(MBB, I, PPC::B, 1).addMBB(Dest);
+
+        // Remove the old branch from the function.
+        OldBranch->eraseFromParent();
+        
+        // Remember that this instruction is 8-bytes, increase the size of the
+        // block by 4, remember to iterate.
+        BlockSizes[MBB.getNumber()] += 4;
+        MBBStartOffset += 8;
         ++NumExpanded;
-        BuildMI(*MBB, MBBI, Opcode, 2).addReg(CRReg).addImm(2);
-        MBBJ = BuildMI(*MBB, MBBI, PPC::B, 1).addMBB(DestMBB);
+        MadeChange = true;
       }
-      
-      // Erase the psuedo BCC instruction, and then back up the
-      // iterator so that when the for loop increments it, we end up in
-      // the correct place rather than iterating off the end.
-      MBB->erase(MBBI);
-      MBBI = MBBJ;
-      ByteCount += ByteSize;
     }
+    EverMadeChange |= MadeChange;
   }
   
-  OffsetMap.clear();
+  BlockSizes.clear();
   return true;
 }