From 5666fc71f0e2ed2c0400d8bca079a1dd3f33fe53 Mon Sep 17 00:00:00 2001 From: Peizhao Ou Date: Mon, 20 Nov 2017 14:55:11 -0800 Subject: [PATCH 1/1] Reverts wrong modification to MachineBlockPlacement & BranchFolding; uses a new strategy to mark intentionally added fake conditional branch --- include/llvm/CodeGen/MachineBasicBlock.h | 13 ++++ include/llvm/CodeGen/MachineInstr.h | 12 ++++ lib/CodeGen/BranchFolding.cpp | 42 ++----------- lib/CodeGen/CodeGenPrepare.cpp | 60 ++++++++++--------- lib/CodeGen/MachineBasicBlock.cpp | 2 +- lib/CodeGen/MachineBlockPlacement.cpp | 3 - lib/CodeGen/MachineInstr.cpp | 4 +- lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp | 41 +++++++++++++ lib/IR/BasicBlock.cpp | 3 +- lib/Target/AArch64/AArch64InstrInfo.cpp | 29 --------- 10 files changed, 108 insertions(+), 101 deletions(-) diff --git a/include/llvm/CodeGen/MachineBasicBlock.h b/include/llvm/CodeGen/MachineBasicBlock.h index 3d58c499823..9585b29a5dc 100644 --- a/include/llvm/CodeGen/MachineBasicBlock.h +++ b/include/llvm/CodeGen/MachineBasicBlock.h @@ -81,6 +81,10 @@ public: }; private: + // XXX-update: A flag that checks whether we can eliminate this machine basic + // block. + bool canEliminateMachineBB; + typedef ilist Instructions; Instructions Insts; const BasicBlock *BB; @@ -135,6 +139,15 @@ private: friend class MachineFunction; public: + // XXX-update: + void disableCanEliminateMachineBB() { + canEliminateMachineBB = false; + } + + bool getCanEliminateMachineBB() { + return canEliminateMachineBB; + } + /// Return the LLVM basic block that this instance corresponded to originally. /// Note that this may be NULL if this instance does not correspond directly /// to an LLVM basic block. diff --git a/include/llvm/CodeGen/MachineInstr.h b/include/llvm/CodeGen/MachineInstr.h index 05c9a9e0b07..3e76ea9c31d 100644 --- a/include/llvm/CodeGen/MachineInstr.h +++ b/include/llvm/CodeGen/MachineInstr.h @@ -71,6 +71,9 @@ public: BundledSucc = 1 << 3 // Instruction has bundled successors. }; private: + // XXX-update: A flag that checks whether we can eliminate this instruction. + bool canEliminateMachineInstr; + const MCInstrDesc *MCID; // Instruction descriptor. MachineBasicBlock *Parent; // Pointer to the owning basic block. @@ -126,6 +129,15 @@ private: friend class MachineFunction; public: + // XXX-update: + void disableCanEliminateMachineInstr() { + canEliminateMachineInstr = false; + } + + bool getCanEliminateMachineInstr() { + return canEliminateMachineInstr; + } + const MachineBasicBlock* getParent() const { return Parent; } MachineBasicBlock* getParent() { return Parent; } diff --git a/lib/CodeGen/BranchFolding.cpp b/lib/CodeGen/BranchFolding.cpp index bd89ee36696..a56fec468cc 100644 --- a/lib/CodeGen/BranchFolding.cpp +++ b/lib/CodeGen/BranchFolding.cpp @@ -493,15 +493,6 @@ static void FixTail(MachineBasicBlock *CurMBB, MachineBasicBlock *SuccBB, MachineBasicBlock *NextBB = &*I; if (TBB == NextBB && !Cond.empty() && !FBB) { if (!TII->ReverseBranchCondition(Cond)) { - // XXX-disabled: Don't fold conditional branches that we added - // intentionally. - MachineBasicBlock::iterator I = CurMBB->getLastNonDebugInstr(); - if (I != CurMBB->end()) { - if (I->isConditionalBranch()) { - return; - } - } - TII->RemoveBranch(*CurMBB); TII->InsertBranch(*CurMBB, SuccBB, nullptr, Cond, dl); return; @@ -1125,6 +1116,12 @@ bool BranchFolder::OptimizeBranches(MachineFunction &MF) { for (MachineFunction::iterator I = std::next(MF.begin()), E = MF.end(); I != E; ) { MachineBasicBlock *MBB = &*I++; + // XXX-disabled: Don't optimize blocks that contain intentionally added fake + // conditional branch. + if (!MBB->getCanEliminateMachineBB()) { + continue; + } + MadeChange |= OptimizeBlock(MBB); // If it is dead, remove it. @@ -1302,15 +1299,6 @@ ReoptimizeBlock: // If the previous branch *only* branches to *this* block (conditional or // not) remove the branch. if (PriorTBB == MBB && !PriorFBB) { - // XXX-disabled: Don't fold conditional branches that we added - // intentionally. - MachineBasicBlock::iterator I = PrevBB.getLastNonDebugInstr(); - if (I != PrevBB.end()) { - if (I->isConditionalBranch()) { - return MadeChange ; - } - } - TII->RemoveBranch(PrevBB); MadeChange = true; ++NumBranchOpts; @@ -1320,15 +1308,6 @@ ReoptimizeBlock: // If the prior block branches somewhere else on the condition and here if // the condition is false, remove the uncond second branch. if (PriorFBB == MBB) { - // XXX-disabled: Don't fold conditional branches that we added - // intentionally. - MachineBasicBlock::iterator I = PrevBB.getLastNonDebugInstr(); - if (I != PrevBB.end()) { - if (I->isConditionalBranch()) { - return MadeChange ; - } - } - DebugLoc dl = getBranchDebugLoc(PrevBB); TII->RemoveBranch(PrevBB); TII->InsertBranch(PrevBB, PriorTBB, nullptr, PriorCond, dl); @@ -1341,15 +1320,6 @@ ReoptimizeBlock: // if the branch condition is reversible, reverse the branch to create a // fall-through. if (PriorTBB == MBB) { - // XXX-disabled: Don't fold conditional branches that we added - // intentionally. - MachineBasicBlock::iterator I = PrevBB.getLastNonDebugInstr(); - if (I != PrevBB.end()) { - if (I->isConditionalBranch()) { - return MadeChange ; - } - } - SmallVector NewPriorCond(PriorCond); if (!TII->ReverseBranchCondition(NewPriorCond)) { DebugLoc dl = getBranchDebugLoc(PrevBB); diff --git a/lib/CodeGen/CodeGenPrepare.cpp b/lib/CodeGen/CodeGenPrepare.cpp index 9ada111eaa9..1a07bfc0c35 100644 --- a/lib/CodeGen/CodeGenPrepare.cpp +++ b/lib/CodeGen/CodeGenPrepare.cpp @@ -729,10 +729,16 @@ void AddFakeConditionalBranch(Instruction* SplitInst, Value* Condition) { TerminatorInst* ThenTerm = nullptr; TerminatorInst* ElseTerm = nullptr; SplitBlockAndInsertIfThenElse(Condition, SplitInst, &ThenTerm, &ElseTerm); + assert(ThenTerm && ElseTerm && + "Then/Else terminators cannot be empty after basic block spliting"); auto* ThenBB = ThenTerm->getParent(); auto* ElseBB = ElseTerm->getParent(); + auto* TailBB = ThenBB->getSingleSuccessor(); + assert(TailBB && "Tail block cannot be empty after basic block spliting"); + ThenBB->disableCanEliminateBlock(); ThenBB->disableCanEliminateBlock(); + TailBB->disableCanEliminateBlock(); ThenBB->setName(BB->getName() + "Then.Fake"); ElseBB->setName(BB->getName() + "Else.Fake"); DEBUG(dbgs() << "Add fake conditional branch:\n" @@ -750,7 +756,7 @@ void TaintRelaxedLoads(LoadInst* LI) { } // XXX-comment: Returns whether the code has been changed. -bool AddsFakeConditionalBranchAfterMonotonicLoads( +bool AddFakeConditionalBranchAfterMonotonicLoads( const SmallVector& MonotonicLoadInsts) { bool Changed = false; for (auto* LI : MonotonicLoadInsts) { @@ -1032,29 +1038,7 @@ bool StoreDependOnValue(StoreInst* SI, Value* Dep) { bool CodeGenPrepare::runOnFunction(Function &F) { - // XXX-comment: Delay dealing with relaxed loads in this function to avoid - // further changes done by other passes (e.g., SimplifyCFG). - - // Collect all the relaxed loads. - SmallVector MonotonicLoadInsts; - for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) { - if (I->isAtomic()) { - switch (I->getOpcode()) { - case Instruction::Load: { - auto* LI = dyn_cast(&*I); - if (LI->getOrdering() == Monotonic) { - MonotonicLoadInsts.push_back(LI); - } - break; - } - default: { - break; - } - } - } - } - bool EverMadeChange = - AddsFakeConditionalBranchAfterMonotonicLoads(MonotonicLoadInsts); + bool EverMadeChange = false; if (skipOptnoneFunction(F)) return false; @@ -1169,6 +1153,29 @@ bool CodeGenPrepare::runOnFunction(Function &F) { EverMadeChange |= simplifyOffsetableRelocate(*I); } + // XXX-comment: Delay dealing with relaxed loads in this function to avoid + // further changes done by other passes (e.g., SimplifyCFG). + // Collect all the relaxed loads. + SmallVector MonotonicLoadInsts; + for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) { + if (I->isAtomic()) { + switch (I->getOpcode()) { + case Instruction::Load: { + auto* LI = dyn_cast(&*I); + if (LI->getOrdering() == Monotonic) { + MonotonicLoadInsts.push_back(LI); + } + break; + } + default: { + break; + } + } + } + } + EverMadeChange |= + AddFakeConditionalBranchAfterMonotonicLoads(MonotonicLoadInsts); + return EverMadeChange; } @@ -1215,11 +1222,6 @@ bool CodeGenPrepare::eliminateMostlyEmptyBlocks(Function &F) { // Note that this intentionally skips the entry block. for (Function::iterator I = std::next(F.begin()), E = F.end(); I != E;) { BasicBlock *BB = &*I++; - // XXX-disabled: Do not eliminate the added fake basic block. - if (!BB->getCanEliminateBlock()) { - continue; - } - // If this block doesn't end with an uncond branch, ignore it. BranchInst *BI = dyn_cast(BB->getTerminator()); if (!BI || !BI->isUnconditional()) diff --git a/lib/CodeGen/MachineBasicBlock.cpp b/lib/CodeGen/MachineBasicBlock.cpp index 85d544d9498..42190168742 100644 --- a/lib/CodeGen/MachineBasicBlock.cpp +++ b/lib/CodeGen/MachineBasicBlock.cpp @@ -40,7 +40,7 @@ using namespace llvm; #define DEBUG_TYPE "codegen" MachineBasicBlock::MachineBasicBlock(MachineFunction &MF, const BasicBlock *B) - : BB(B), Number(-1), xParent(&MF) { + : BB(B), Number(-1), xParent(&MF), canEliminateMachineBB(true) { Insts.Parent = this; } diff --git a/lib/CodeGen/MachineBlockPlacement.cpp b/lib/CodeGen/MachineBlockPlacement.cpp index 4beaa7f3964..f5e30564501 100644 --- a/lib/CodeGen/MachineBlockPlacement.cpp +++ b/lib/CodeGen/MachineBlockPlacement.cpp @@ -1271,10 +1271,7 @@ void MachineBlockPlacement::buildCFGChains(MachineFunction &F) { // bool needUpdateBr = true; if (!Cond.empty() && (!FBB || FBB == ChainBB)) { - // XXX-disabled: Don't bother with added fake conditional branches. - /* PrevBB->updateTerminator(); - */ needUpdateBr = false; Cond.clear(); TBB = FBB = nullptr; diff --git a/lib/CodeGen/MachineInstr.cpp b/lib/CodeGen/MachineInstr.cpp index 6dca74d6002..5e542757b63 100644 --- a/lib/CodeGen/MachineInstr.cpp +++ b/lib/CodeGen/MachineInstr.cpp @@ -647,7 +647,7 @@ MachineInstr::MachineInstr(MachineFunction &MF, const MCInstrDesc &tid, DebugLoc dl, bool NoImp) : MCID(&tid), Parent(nullptr), Operands(nullptr), NumOperands(0), Flags(0), AsmPrinterFlags(0), NumMemRefs(0), MemRefs(nullptr), - debugLoc(std::move(dl)) { + debugLoc(std::move(dl)), canEliminateMachineInstr(true) { assert(debugLoc.hasTrivialDestructor() && "Expected trivial destructor"); // Reserve space for the expected number of operands. @@ -667,7 +667,7 @@ MachineInstr::MachineInstr(MachineFunction &MF, const MachineInstr &MI) : MCID(&MI.getDesc()), Parent(nullptr), Operands(nullptr), NumOperands(0), Flags(0), AsmPrinterFlags(0), NumMemRefs(MI.NumMemRefs), MemRefs(MI.MemRefs), - debugLoc(MI.getDebugLoc()) { + debugLoc(MI.getDebugLoc()), canEliminateMachineInstr(true) { assert(debugLoc.hasTrivialDestructor() && "Expected trivial destructor"); CapOperands = OperandCapacity::get(MI.getNumOperands()); diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp index c075da4738a..1676e2dfe08 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp @@ -645,6 +645,47 @@ bool SelectionDAGISel::runOnMachineFunction(MachineFunction &mf) { // at this point. FuncInfo->clear(); + // XXX-update: Right after instruction selection, check through the + // intentionally added fake conditional branches and mark them as unremovable. + for (auto& MBB : *MF) { + // Check whether MBB has two successors which only contains an unconditional + // branch to the same destination. + if (MBB.succ_size() != 2 || + !MBB.getLastNonDebugInstr()->isUnconditionalBranch()) { + continue; + } + auto MBBSuccIter = MBB.succ_begin(); + auto* Succ1 = *MBBSuccIter; + MBBSuccIter++; + auto* Succ2 = *MBBSuccIter; + + MachineBasicBlock* Succ1Succ = nullptr; + MachineBasicBlock* Succ2Succ = nullptr; + if ((Succ1->size() == 1 && Succ1->begin()->isUnconditionalBranch()) || + (Succ1->size() == 0)) { + Succ1Succ = *Succ1->succ_begin(); + } + if ((Succ2->size() == 1 && Succ2->begin()->isUnconditionalBranch()) || + (Succ2->size() == 0)) { + Succ2Succ = *Succ2->succ_begin(); + } + + bool HasCommonDest = Succ1Succ && Succ1Succ == Succ2Succ; + if (HasCommonDest) { + auto MBBIter = MBB.end(); + std::advance(MBBIter, -2); + assert(MBBIter->isConditionalBranch()); + MBBIter->disableCanEliminateMachineInstr(); + MBB.disableCanEliminateMachineBB(); + Succ1->disableCanEliminateMachineBB(); + Succ2->disableCanEliminateMachineBB(); + Succ1Succ->disableCanEliminateMachineBB(); + DEBUG(dbgs() << "Mark as unremovable machine basic block: " << MBB + << "\nMark as unremovable branch instruction: " << *MBBIter + << "\n"); + } + } + DEBUG(dbgs() << "*** MachineFunction at end of ISel ***\n"); DEBUG(MF->print(dbgs())); diff --git a/lib/IR/BasicBlock.cpp b/lib/IR/BasicBlock.cpp index f61276fd436..8e3cac27f48 100644 --- a/lib/IR/BasicBlock.cpp +++ b/lib/IR/BasicBlock.cpp @@ -40,7 +40,8 @@ template class llvm::SymbolTableListTraits; BasicBlock::BasicBlock(LLVMContext &C, const Twine &Name, Function *NewParent, BasicBlock *InsertBefore) - : Value(Type::getLabelTy(C), Value::BasicBlockVal), Parent(nullptr) { + : Value(Type::getLabelTy(C), Value::BasicBlockVal), Parent(nullptr), + canEliminateBlock(true) { if (NewParent) insertInto(NewParent, InsertBefore); diff --git a/lib/Target/AArch64/AArch64InstrInfo.cpp b/lib/Target/AArch64/AArch64InstrInfo.cpp index c9c982ed7b5..f398117de95 100644 --- a/lib/Target/AArch64/AArch64InstrInfo.cpp +++ b/lib/Target/AArch64/AArch64InstrInfo.cpp @@ -217,25 +217,6 @@ bool AArch64InstrInfo::ReverseBranchCondition( return false; } -// XXX-update: Returns whether we can remove a conditional branch instruction. -// If it's one that is mannually added by us, then don't remove it (return -// false). All their successors are the same. -static bool shouldRemoveConditionalBranch(MachineInstr* I) { - auto* MBB = I->getParent(); - assert(isCondBranchOpcode(I->getOpcode())); - bool SameSuccessor = true; - MachineBasicBlock* BB = nullptr; - for (auto* Succ : MBB->successors()) { - if (!BB) { - BB = Succ; - } - if (BB != Succ) { - SameSuccessor = false; - } - } - return !SameSuccessor; -} - unsigned AArch64InstrInfo::RemoveBranch(MachineBasicBlock &MBB) const { MachineBasicBlock::iterator I = MBB.getLastNonDebugInstr(); if (I == MBB.end()) @@ -245,11 +226,6 @@ unsigned AArch64InstrInfo::RemoveBranch(MachineBasicBlock &MBB) const { !isCondBranchOpcode(I->getOpcode())) return 0; - // XXX-update: Don't remove fake conditional branches. - if (isCondBranchOpcode(I->getOpcode()) && !shouldRemoveConditionalBranch(I)) { - return 0; - } - // Remove the branch. I->eraseFromParent(); @@ -261,11 +237,6 @@ unsigned AArch64InstrInfo::RemoveBranch(MachineBasicBlock &MBB) const { if (!isCondBranchOpcode(I->getOpcode())) return 1; - // XXX-update: Don't remove fake conditional branches. - if (!shouldRemoveConditionalBranch(I)) { - return 1; - } - // Remove the branch. I->eraseFromParent(); return 2; -- 2.34.1