[AVR] Add the branch selection pass from the GitHub repository

We should rewrite this using the generic branch relaxation pass, but for
the moment having this pass is better than hitting an assertion error.

llvm-svn: 307109

6 files changed, 276 insertions, 7 deletions

diff --git a/llvm/lib/Target/AVR/AVRBranchSelector.cpp b/llvm/lib/Target/AVR/AVRBranchSelector.cpp
new file mode 100644
index 00000000000..bbc15916963
--- /dev/null
+++ b/llvm/lib/Target/AVR/AVRBranchSelector.cpp
@@ -0,0 +1,262 @@
+//===-- AVRBranchSelector.cpp - Emit long conditional branches ------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains a pass that scans a machine function to determine which
+// conditional branches need more than 8 bits of displacement to reach their
+// target basic block.  It does this in two passes; a calculation of basic block
+// positions pass, and a branch pseudo op to machine branch opcode pass.  This
+// pass should be run last, just before the assembly printer.
+//
+//===----------------------------------------------------------------------===//
+
+#include "AVR.h"
+
+#include "llvm/ADT/Statistic.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineInstrBuilder.h"
+
+#include "AVRInstrInfo.h"
+#include "AVRTargetMachine.h"
+#include "MCTargetDesc/AVRMCTargetDesc.h"
+
+#define DEBUG_TYPE "avr-branch-select"
+
+STATISTIC(NumExpanded, "Number of branches expanded to long format");
+
+namespace llvm {
+
+/// Ensures branch targets can fit inside the instruction
+/// they reside in.
+///
+/// If a branch target is too large for the instruction it
+/// is being used with, this pass replaces it with a larger,
+/// equivalent instruction which can fit the target.
+class AVRBSel : public MachineFunctionPass {
+public:
+  static char ID;
+
+  explicit AVRBSel() : MachineFunctionPass(ID) {}
+
+  bool runOnMachineFunction(MachineFunction &MF) override;
+
+  StringRef getPassName() const override { return "AVR Branch Selector"; }
+
+protected:
+
+  /// Measure and sum the size of all basic blocks in a function.
+  unsigned calculateFunctionSize(const MachineFunction &MF);
+
+private:
+  /// The sizes of the basic blocks in the function.
+  std::vector<unsigned> BlockSizes;
+};
+
+char AVRBSel::ID = 0;
+
+/// Checks whether the passed opcode is a conditional branch.
+static bool isConditionalBranch(int Opcode) {
+  switch (Opcode) {
+  default:
+    return false;
+  case AVR::BREQk:
+  case AVR::BRNEk:
+  case AVR::BRSHk:
+  case AVR::BRLOk:
+  case AVR::BRMIk:
+  case AVR::BRPLk:
+  case AVR::BRGEk:
+  case AVR::BRLTk:
+    return true;
+  }
+}
+
+unsigned AVRBSel::calculateFunctionSize(const MachineFunction &MF) {
+  const AVRSubtarget &STI = MF.getSubtarget<AVRSubtarget>();
+  const AVRInstrInfo &TII = *STI.getInstrInfo();
+
+  unsigned FuncSize = 0;
+
+  for (const MachineBasicBlock &MBB : MF) {
+    unsigned BlockSize = 0;
+
+    for (const MachineInstr &MI : MBB) {
+      BlockSize += TII.getInstSizeInBytes(MI);
+    }
+
+    BlockSizes[MBB.getNumber()] = BlockSize;
+    FuncSize += BlockSize;
+  }
+
+  assert(FuncSize % 2 == 0 && "function should have an even number of bytes");
+
+  return FuncSize;
+}
+
+bool AVRBSel::runOnMachineFunction(MachineFunction &MF) {
+  const AVRSubtarget &STI = MF.getSubtarget<AVRSubtarget>();
+  const AVRInstrInfo &TII = *STI.getInstrInfo();
+
+  // Give the blocks of the function a dense, in-order, numbering.
+  MF.RenumberBlocks();
+  BlockSizes.resize(MF.getNumBlockIDs());
+
+  unsigned FuncSize = calculateFunctionSize(MF);
+
+  // 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 (isUInt<7>(FuncSize)) {
+    BlockSizes.clear();
+    return false;
+  }
+
+  // For each conditional branch, if the offset to its destination is larger
+  // than the offset field allows, transform it into a long or a huge branch
+  // sequence like this:
+  //  -short branch:
+  //     brCC MBB
+  //  -long branch:
+  //     br!CC $PC+2
+  //     rjmp MBB
+  //  -huge branch:
+  //     br!CC $PC+4
+  //     jmp MBB
+  bool MadeChange = true;
+  while (MadeChange) {
+    // Iteratively expand branches until we reach a fixed point.
+    MadeChange = false;
+
+    for (MachineBasicBlock &MBB : MF) {
+      unsigned MBBStartOffset = 0;
+
+      for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E;
+           ++I) {
+        int Opc = I->getOpcode();
+        if ((!isConditionalBranch(Opc) || I->getOperand(0).isImm()) &&
+            (Opc != AVR::RJMPk)) {
+          MBBStartOffset += TII.getInstSizeInBytes(*I);
+          continue;
+        }
+
+        // Determine the offset from the current branch to the destination
+        // block.
+        MachineBasicBlock &Dest = *I->getOperand(0).getMBB();
+
+        assert(Dest.getNumber() >= 0 &&
+            "Destination basic block isn't in a function");
+
+        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];
+          }
+
+          // Set the size of backwards branches to a negative value.
+          BranchSize = -BranchSize;
+        } 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];
+          }
+        }
+
+        if (isConditionalBranch(Opc))
+          BranchSize -= 2; // take the size of the current instruction.
+
+        assert(BranchSize % 2 == 0 &&
+               "BranchSize should have an even number of bytes");
+
+        // If this branch is in range, ignore it.
+        if ((isConditionalBranch(Opc) && isInt<8>(BranchSize)) ||
+            (Opc == AVR::RJMPk && isInt<13>(BranchSize))) {
+          MBBStartOffset += 2;
+          continue;
+        }
+
+        // Otherwise, we have to expand it to a long branch.
+        unsigned NewSize;
+        int UncondOpc;
+        MachineInstr &OldBranch = *I;
+        DebugLoc DL = OldBranch.getDebugLoc();
+
+        if (Opc == AVR::RJMPk) {
+          // Replace this instruction with a jmp which has a size of 4 bytes.
+          NewSize = 4;
+          UncondOpc = AVR::JMPk;
+
+          // We may be converting a conditional long jump to a huge one, if this
+          // is the case, update the $PC+2 operand in brCC to $PC+4.
+          // Skip the check when this instruction is the first inside the BB.
+          if (I != MBB.begin()) {
+            MachineInstr &PI = *std::prev(I);
+
+            if (isConditionalBranch(PI.getOpcode()) &&
+                PI.getOperand(0).isImm() &&
+                PI.getOperand(0).getImm() == 2) {
+              PI.getOperand(0).setImm(4);
+            }
+          }
+        } else {
+          assert(isConditionalBranch(Opc) &&
+              "opcode should be a conditional branch");
+
+          unsigned BrCCOffs;
+          // Determine if we can reach the destination block with a rjmp,
+          // otherwise a jmp instruction is needed.
+          if (isInt<13>(BranchSize)) {
+            NewSize = 4;
+            BrCCOffs = 2;
+            UncondOpc = AVR::RJMPk;
+          } else {
+            NewSize = 6;
+            BrCCOffs = 4;
+            UncondOpc = AVR::JMPk;
+          }
+
+          AVRCC::CondCodes OCC =
+              TII.getOppositeCondition(TII.getCondFromBranchOpc(Opc));
+          // Jump over the uncond branch inst (i.e. $+2) on opposite condition.
+          BuildMI(MBB, I, DL, TII.getBrCond(OCC)).addImm(BrCCOffs);
+        }
+
+        // Uncond branch to the real destination.
+        I = BuildMI(MBB, I, DL, TII.get(UncondOpc)).addMBB(&Dest);
+
+        // Remove the old branch from the function.
+        OldBranch.eraseFromParent();
+
+        // Remember that this instruction is NewSize bytes, increase the size of
+        // the block by NewSize-2, remember to iterate.
+        BlockSizes[MBB.getNumber()] += NewSize - 2;
+        MBBStartOffset += NewSize;
+
+        ++NumExpanded;
+        MadeChange = true;
+      }
+    }
+  }
+
+  BlockSizes.clear();
+  return true;
+}
+
+FunctionPass *createAVRBranchSelectionPass() { return new AVRBSel(); }
+
+} // end of namespace llvm
+
diff --git a/llvm/lib/Target/AVR/AVRTargetMachine.cpp b/llvm/lib/Target/AVR/AVRTargetMachine.cpp
index 91d2a8737b8..f620668215a 100644
--- a/llvm/lib/Target/AVR/AVRTargetMachine.cpp
+++ b/llvm/lib/Target/AVR/AVRTargetMachine.cpp
@@ -67,6 +67,7 @@ public:
   bool addInstSelector() override;
   void addPreSched2() override;
   void addPreRegAlloc() override;
+  void addPreEmitPass() override;
 };
 } // namespace
 
@@ -115,4 +116,9 @@ void AVRPassConfig::addPreSched2() {
   addPass(createAVRExpandPseudoPass());
 }
 
+void AVRPassConfig::addPreEmitPass() {
+  // Must run branch selection immediately preceding the asm printer.
+  addPass(createAVRBranchSelectionPass());
+}
+
 } // end of namespace llvm
diff --git a/llvm/lib/Target/AVR/CMakeLists.txt b/llvm/lib/Target/AVR/CMakeLists.txt
index e103a60fa6f..2e335509804 100644
--- a/llvm/lib/Target/AVR/CMakeLists.txt
+++ b/llvm/lib/Target/AVR/CMakeLists.txt
@@ -18,6 +18,7 @@ add_public_tablegen_target(AVRCommonTableGen)
 
 add_llvm_target(AVRCodeGen
   AVRAsmPrinter.cpp
+  AVRBranchSelector.cpp
   AVRExpandPseudoInsts.cpp
   AVRFrameLowering.cpp
   AVRInstrInfo.cpp
diff --git a/llvm/test/CodeGen/AVR/ctlz.ll b/llvm/test/CodeGen/AVR/ctlz.ll
index 4f73e846b1f..a49e80bd7ab 100644
--- a/llvm/test/CodeGen/AVR/ctlz.ll
+++ b/llvm/test/CodeGen/AVR/ctlz.ll
@@ -10,7 +10,7 @@ declare i8 @llvm.ctlz.i8(i8)
 
 ; CHECK-LABEL: count_leading_zeros:
 ; CHECK: cpi    [[RESULT:r[0-9]+]], 0
-; CHECK: breq   LBB0_1
+; CHECK: breq   LBB0_2
 ; CHECK: mov    [[SCRATCH:r[0-9]+]], {{.*}}[[RESULT]]
 ; CHECK: lsr    {{.*}}[[SCRATCH]]
 ; CHECK: or     {{.*}}[[SCRATCH]], {{.*}}[[RESULT]]
@@ -43,6 +43,6 @@ declare i8 @llvm.ctlz.i8(i8)
 ; CHECK: add    {{.*}}[[RESULT]], {{.*}}[[SCRATCH]]
 ; CHECK: andi   {{.*}}[[RESULT]], 15
 ; CHECK: ret
-; CHECK: LBB0_1:
+; CHECK: LBB0_2:
 ; CHECK: ldi    {{.*}}[[RESULT]], 8
 ; CHECK: ret
diff --git a/llvm/test/CodeGen/AVR/cttz.ll b/llvm/test/CodeGen/AVR/cttz.ll
index 2501566275e..61f2e69d241 100644
--- a/llvm/test/CodeGen/AVR/cttz.ll
+++ b/llvm/test/CodeGen/AVR/cttz.ll
@@ -10,7 +10,7 @@ declare i8 @llvm.cttz.i8(i8)
 
 ; CHECK-LABEL: count_trailing_zeros:
 ; CHECK: cpi    [[RESULT:r[0-9]+]], 0
-; CHECK: breq   LBB0_1
+; CHECK: breq   LBB0_2
 ; CHECK: mov    [[SCRATCH:r[0-9]+]], {{.*}}[[RESULT]]
 ; CHECK: dec    {{.*}}[[SCRATCH]]
 ; CHECK: com    {{.*}}[[RESULT]]
@@ -34,7 +34,7 @@ declare i8 @llvm.cttz.i8(i8)
 ; CHECK: andi   {{.*}}[[SCRATCH]], 15
 ; CHECK: mov    {{.*}}[[RESULT]], {{.*}}[[SCRATCH]]
 ; CHECK: ret
-; CHECK: LBB0_1:
+; CHECK: LBB0_2:
 ; CHECK: ldi    {{.*}}[[SCRATCH]], 8
 ; CHECK: mov    {{.*}}[[RESULT]], {{.*}}[[SCRATCH]]
 ; CHECK: ret
diff --git a/llvm/test/CodeGen/AVR/select-mbb-placement-bug.ll b/llvm/test/CodeGen/AVR/select-mbb-placement-bug.ll
index ca7ec1ab831..aca9502b5df 100644
--- a/llvm/test/CodeGen/AVR/select-mbb-placement-bug.ll
+++ b/llvm/test/CodeGen/AVR/select-mbb-placement-bug.ll
@@ -8,9 +8,9 @@ define internal fastcc void @loopy() {
 ;
 ; https://github.com/avr-rust/rust/issues/49
 
-; CHECK: LBB0_1:
-; CHECK: LBB0_2:
-; CHECK-NOT: LBB0_3:
+; CHECK: LBB0_{{[0-9]+}}:
+; CHECK: LBB0_{{[0-9]+}}:
+; CHECK-NOT: LBB0_{{[0-9]+}}:
 start:
   br label %bb7.preheader