From: James Y Knight Date: Wed, 13 Jan 2016 04:44:14 +0000 (+0000) Subject: [SPARC] Revamp AnalyzeBranch and add ReverseBranchCondition. X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=commitdiff_plain;h=732b4fd71a24d3cc2845413469bc937865e7595d;hp=561f3680a12638e8290ff3473bec4f0e9cb18bac [SPARC] Revamp AnalyzeBranch and add ReverseBranchCondition. AnalyzeBranch on X86 (and, previously, SPARC, which implementation was copied from X86) tries to modify the branches based on block layout (e.g. checking isLayoutSuccessor), when AllowModify is true. The rest of the architectures leave that up to the caller, which can call InsertBranch, RemoveBranch, and ReverseBranchCondition as appropriate. That appears to be the preferred way to do it nowadays. This commit makes SPARC like the rest: replaces AnalyzeBranch with an implementation cribbed from AArch64, and adds a ReverseBranchCondition implementation. Additionally, a test-case has been added (also cribbed from AArch64) demonstrating that redundant branch sequences no longer get emitted. E.g., it used to emit code like this: bne .LBB1_2 nop ba .LBB1_1 nop .LBB1_2: And now emits: cmp %i0, 42 be .LBB1_1 nop git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@257572 91177308-0d34-0410-b5e6-96231b3b80d8 --- diff --git a/lib/Target/Sparc/SparcInstrInfo.cpp b/lib/Target/Sparc/SparcInstrInfo.cpp index 733027a5d2b..05006ac5772 100644 --- a/lib/Target/Sparc/SparcInstrInfo.cpp +++ b/lib/Target/Sparc/SparcInstrInfo.cpp @@ -83,7 +83,6 @@ static bool IsIntegerCC(unsigned CC) return (CC <= SPCC::ICC_VC); } - static SPCC::CondCodes GetOppositeBranchCondition(SPCC::CondCodes CC) { switch(CC) { @@ -124,106 +123,103 @@ static SPCC::CondCodes GetOppositeBranchCondition(SPCC::CondCodes CC) llvm_unreachable("Invalid cond code"); } -bool SparcInstrInfo::AnalyzeBranch(MachineBasicBlock &MBB, - MachineBasicBlock *&TBB, - MachineBasicBlock *&FBB, - SmallVectorImpl &Cond, - bool AllowModify) const -{ - - MachineBasicBlock::iterator I = MBB.end(); - MachineBasicBlock::iterator UnCondBrIter = MBB.end(); - while (I != MBB.begin()) { - --I; +static bool isUncondBranchOpcode(int Opc) { return Opc == SP::BA; } - if (I->isDebugValue()) - continue; +static bool isCondBranchOpcode(int Opc) { + return Opc == SP::FBCOND || Opc == SP::BCOND; +} - // When we see a non-terminator, we are done. - if (!isUnpredicatedTerminator(I)) - break; +static bool isIndirectBranchOpcode(int Opc) { + return Opc == SP::BINDrr || Opc == SP::BINDri; +} - // Terminator is not a branch. - if (!I->isBranch()) - return true; +static void parseCondBranch(MachineInstr *LastInst, MachineBasicBlock *&Target, + SmallVectorImpl &Cond) { + Cond.push_back(MachineOperand::CreateImm(LastInst->getOperand(1).getImm())); + Target = LastInst->getOperand(0).getMBB(); +} - // Handle Unconditional branches. - if (I->getOpcode() == SP::BA) { - UnCondBrIter = I; +bool SparcInstrInfo::AnalyzeBranch(MachineBasicBlock &MBB, + MachineBasicBlock *&TBB, + MachineBasicBlock *&FBB, + SmallVectorImpl &Cond, + bool AllowModify) const { + MachineBasicBlock::iterator I = MBB.getLastNonDebugInstr(); + if (I == MBB.end()) + return false; + + if (!isUnpredicatedTerminator(I)) + return false; + + // Get the last instruction in the block. + MachineInstr *LastInst = I; + unsigned LastOpc = LastInst->getOpcode(); + + // If there is only one terminator instruction, process it. + if (I == MBB.begin() || !isUnpredicatedTerminator(--I)) { + if (isUncondBranchOpcode(LastOpc)) { + TBB = LastInst->getOperand(0).getMBB(); + return false; + } + if (isCondBranchOpcode(LastOpc)) { + // Block ends with fall-through condbranch. + parseCondBranch(LastInst, TBB, Cond); + return false; + } + return true; // Can't handle indirect branch. + } - if (!AllowModify) { - TBB = I->getOperand(0).getMBB(); - continue; + // Get the instruction before it if it is a terminator. + MachineInstr *SecondLastInst = I; + unsigned SecondLastOpc = SecondLastInst->getOpcode(); + + // If AllowModify is true and the block ends with two or more unconditional + // branches, delete all but the first unconditional branch. + if (AllowModify && isUncondBranchOpcode(LastOpc)) { + while (isUncondBranchOpcode(SecondLastOpc)) { + LastInst->eraseFromParent(); + LastInst = SecondLastInst; + LastOpc = LastInst->getOpcode(); + if (I == MBB.begin() || !isUnpredicatedTerminator(--I)) { + // Return now the only terminator is an unconditional branch. + TBB = LastInst->getOperand(0).getMBB(); + return false; + } else { + SecondLastInst = I; + SecondLastOpc = SecondLastInst->getOpcode(); } + } + } - while (std::next(I) != MBB.end()) - std::next(I)->eraseFromParent(); - - Cond.clear(); - FBB = nullptr; + // If there are three terminators, we don't know what sort of block this is. + if (SecondLastInst && I != MBB.begin() && isUnpredicatedTerminator(--I)) + return true; - if (MBB.isLayoutSuccessor(I->getOperand(0).getMBB())) { - TBB = nullptr; - I->eraseFromParent(); - I = MBB.end(); - UnCondBrIter = MBB.end(); - continue; - } + // If the block ends with a B and a Bcc, handle it. + if (isCondBranchOpcode(SecondLastOpc) && isUncondBranchOpcode(LastOpc)) { + parseCondBranch(SecondLastInst, TBB, Cond); + FBB = LastInst->getOperand(0).getMBB(); + return false; + } - TBB = I->getOperand(0).getMBB(); - continue; - } + // If the block ends with two unconditional branches, handle it. The second + // one is not executed. + if (isUncondBranchOpcode(SecondLastOpc) && isUncondBranchOpcode(LastOpc)) { + TBB = SecondLastInst->getOperand(0).getMBB(); + return false; + } - unsigned Opcode = I->getOpcode(); - if (Opcode != SP::BCOND && Opcode != SP::FBCOND) - return true; // Unknown Opcode. - - SPCC::CondCodes BranchCode = (SPCC::CondCodes)I->getOperand(1).getImm(); - - if (Cond.empty()) { - MachineBasicBlock *TargetBB = I->getOperand(0).getMBB(); - if (AllowModify && UnCondBrIter != MBB.end() && - MBB.isLayoutSuccessor(TargetBB)) { - - // Transform the code - // - // brCC L1 - // ba L2 - // L1: - // .. - // L2: - // - // into - // - // brnCC L2 - // L1: - // ... - // L2: - // - BranchCode = GetOppositeBranchCondition(BranchCode); - MachineBasicBlock::iterator OldInst = I; - BuildMI(MBB, UnCondBrIter, MBB.findDebugLoc(I), get(Opcode)) - .addMBB(UnCondBrIter->getOperand(0).getMBB()).addImm(BranchCode); - BuildMI(MBB, UnCondBrIter, MBB.findDebugLoc(I), get(SP::BA)) - .addMBB(TargetBB); - - OldInst->eraseFromParent(); - UnCondBrIter->eraseFromParent(); - - UnCondBrIter = MBB.end(); - I = MBB.end(); - continue; - } - FBB = TBB; - TBB = I->getOperand(0).getMBB(); - Cond.push_back(MachineOperand::CreateImm(BranchCode)); - continue; - } - // FIXME: Handle subsequent conditional branches. - // For now, we can't handle multiple conditional branches. + // ...likewise if it ends with an indirect branch followed by an unconditional + // branch. + if (isIndirectBranchOpcode(SecondLastOpc) && isUncondBranchOpcode(LastOpc)) { + I = LastInst; + if (AllowModify) + I->eraseFromParent(); return true; } - return false; + + // Otherwise, can't handle this. + return true; } unsigned @@ -277,6 +273,14 @@ unsigned SparcInstrInfo::RemoveBranch(MachineBasicBlock &MBB) const return Count; } +bool SparcInstrInfo::ReverseBranchCondition( + SmallVectorImpl &Cond) const { + assert(Cond.size() == 1); + SPCC::CondCodes CC = static_cast(Cond[0].getImm()); + Cond[0].setImm(GetOppositeBranchCondition(CC)); + return false; +} + void SparcInstrInfo::copyPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator I, DebugLoc DL, unsigned DestReg, unsigned SrcReg, diff --git a/lib/Target/Sparc/SparcInstrInfo.h b/lib/Target/Sparc/SparcInstrInfo.h index 15673f134d8..9de624cc958 100644 --- a/lib/Target/Sparc/SparcInstrInfo.h +++ b/lib/Target/Sparc/SparcInstrInfo.h @@ -76,6 +76,9 @@ public: MachineBasicBlock *FBB, ArrayRef Cond, DebugLoc DL) const override; + bool + ReverseBranchCondition(SmallVectorImpl &Cond) const override; + void copyPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator I, DebugLoc DL, unsigned DestReg, unsigned SrcReg, diff --git a/test/CodeGen/SPARC/2011-01-19-DelaySlot.ll b/test/CodeGen/SPARC/2011-01-19-DelaySlot.ll index 29bca67e2d2..b38c955e1f6 100644 --- a/test/CodeGen/SPARC/2011-01-19-DelaySlot.ll +++ b/test/CodeGen/SPARC/2011-01-19-DelaySlot.ll @@ -59,7 +59,7 @@ entry: ;CHECK: sethi ;CHECK: !NO_APP ;CHECK-NEXT: cmp -;CHECK-NEXT: bg +;CHECK-NEXT: ble ;CHECK-NEXT: mov tail call void asm sideeffect "sethi 0, %g0", ""() nounwind %0 = icmp slt i32 %a, 0 diff --git a/test/CodeGen/SPARC/analyze-branch.ll b/test/CodeGen/SPARC/analyze-branch.ll new file mode 100644 index 00000000000..7d2096033a0 --- /dev/null +++ b/test/CodeGen/SPARC/analyze-branch.ll @@ -0,0 +1,58 @@ +; RUN: llc -mtriple=sparc-none-linux-gnu < %s | FileCheck %s + +; This test checks that LLVM can do basic stripping and reapplying of branches +; to basic blocks. + +declare void @test_true() +declare void @test_false() + +; !0 corresponds to a branch being taken, !1 to not being takne. +!0 = !{!"branch_weights", i32 64, i32 4} +!1 = !{!"branch_weights", i32 4, i32 64} + +define void @test_Bcc_fallthrough_taken(i32 %in) nounwind { +; CHECK-LABEL: test_Bcc_fallthrough_taken: + %tst = icmp eq i32 %in, 42 + br i1 %tst, label %true, label %false, !prof !0 + +; CHECK: cmp {{%[goli][0-9]+}}, 42 +; CHECK: bne [[FALSE:.LBB[0-9]+_[0-9]+]] +; CHECK-NEXT: nop +; CHECK-NEXT: ! BB# +; CHECK-NEXT: call test_true + +; CHECK: [[FALSE]]: +; CHECK: call test_false + +true: + call void @test_true() + ret void + +false: + call void @test_false() + ret void +} + +define void @test_Bcc_fallthrough_nottaken(i32 %in) nounwind { +; CHECK-LABEL: test_Bcc_fallthrough_nottaken: + %tst = icmp eq i32 %in, 42 + br i1 %tst, label %true, label %false, !prof !1 + +; CHECK: cmp {{%[goli][0-9]+}}, 42 + +; CHECK: be [[TRUE:.LBB[0-9]+_[0-9]+]] +; CHECK-NEXT: nop +; CHECK-NEXT: ! BB# +; CHECK-NEXT: call test_false + +; CHECK: [[TRUE]]: +; CHECK: call test_true + +true: + call void @test_true() + ret void + +false: + call void @test_false() + ret void +}