summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--llvm/lib/Target/AVR/AVRBranchSelector.cpp262
-rw-r--r--llvm/lib/Target/AVR/AVRTargetMachine.cpp6
-rw-r--r--llvm/lib/Target/AVR/CMakeLists.txt1
-rw-r--r--llvm/test/CodeGen/AVR/ctlz.ll4
-rw-r--r--llvm/test/CodeGen/AVR/cttz.ll4
-rw-r--r--llvm/test/CodeGen/AVR/select-mbb-placement-bug.ll6
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
OpenPOWER on IntegriCloud