Reverts wrong modification to MachineBlockPlacement & BranchFolding; uses a new strat...
authorPeizhao Ou <peizhaoo@uci.edu>
Mon, 20 Nov 2017 22:55:11 +0000 (14:55 -0800)
committerPeizhao Ou <peizhaoo@uci.edu>
Mon, 20 Nov 2017 22:55:11 +0000 (14:55 -0800)
include/llvm/CodeGen/MachineBasicBlock.h
include/llvm/CodeGen/MachineInstr.h
lib/CodeGen/BranchFolding.cpp
lib/CodeGen/CodeGenPrepare.cpp
lib/CodeGen/MachineBasicBlock.cpp
lib/CodeGen/MachineBlockPlacement.cpp
lib/CodeGen/MachineInstr.cpp
lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
lib/IR/BasicBlock.cpp
lib/Target/AArch64/AArch64InstrInfo.cpp

index 3d58c499823e86725e9263a79d29830acd4eae26..9585b29a5dc30ce145b6bc63c45019a145471e30 100644 (file)
@@ -81,6 +81,10 @@ public:
   };
 
 private:
   };
 
 private:
+  // XXX-update: A flag that checks whether we can eliminate this machine basic
+  // block.
+  bool canEliminateMachineBB;
+
   typedef ilist<MachineInstr> Instructions;
   Instructions Insts;
   const BasicBlock *BB;
   typedef ilist<MachineInstr> Instructions;
   Instructions Insts;
   const BasicBlock *BB;
@@ -135,6 +139,15 @@ private:
   friend class MachineFunction;
 
 public:
   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.
   /// 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.
index 05c9a9e0b07961a7afdb47980332da1fa0b3494d..3e76ea9c31dd7f5e082962855a7338b1d9441686 100644 (file)
@@ -71,6 +71,9 @@ public:
     BundledSucc  = 1 << 3               // Instruction has bundled successors.
   };
 private:
     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.
 
   const MCInstrDesc *MCID;              // Instruction descriptor.
   MachineBasicBlock *Parent;            // Pointer to the owning basic block.
 
@@ -126,6 +129,15 @@ private:
   friend class MachineFunction;
 
 public:
   friend class MachineFunction;
 
 public:
+  // XXX-update:
+  void disableCanEliminateMachineInstr() {
+    canEliminateMachineInstr = false;
+  }
+
+  bool getCanEliminateMachineInstr() {
+    return canEliminateMachineInstr;
+  }
+
   const MachineBasicBlock* getParent() const { return Parent; }
   MachineBasicBlock* getParent() { return Parent; }
 
   const MachineBasicBlock* getParent() const { return Parent; }
   MachineBasicBlock* getParent() { return Parent; }
 
index bd89ee366962f30dbd72c1c4050bcc9e3eeaa21f..a56fec468cc94cd282e56543663cecaf565e41ad 100644 (file)
@@ -493,15 +493,6 @@ static void FixTail(MachineBasicBlock *CurMBB, MachineBasicBlock *SuccBB,
     MachineBasicBlock *NextBB = &*I;
     if (TBB == NextBB && !Cond.empty() && !FBB) {
       if (!TII->ReverseBranchCondition(Cond)) {
     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;
         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++;
   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.
     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) {
     // 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;
       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) {
     // 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);
       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) {
     // 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<MachineOperand, 4> NewPriorCond(PriorCond);
       if (!TII->ReverseBranchCondition(NewPriorCond)) {
         DebugLoc dl = getBranchDebugLoc(PrevBB);
       SmallVector<MachineOperand, 4> NewPriorCond(PriorCond);
       if (!TII->ReverseBranchCondition(NewPriorCond)) {
         DebugLoc dl = getBranchDebugLoc(PrevBB);
index 9ada111eaa92e683b1b40db7883fc116115880b2..1a07bfc0c3577f71585153b63635d87173c47479 100644 (file)
@@ -729,10 +729,16 @@ void AddFakeConditionalBranch(Instruction* SplitInst, Value* Condition) {
   TerminatorInst* ThenTerm = nullptr;
   TerminatorInst* ElseTerm = nullptr;
   SplitBlockAndInsertIfThenElse(Condition, SplitInst, &ThenTerm, &ElseTerm);
   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* 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();
   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"
   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.
 }
 
 // XXX-comment: Returns whether the code has been changed.
-bool AddsFakeConditionalBranchAfterMonotonicLoads(
+bool AddFakeConditionalBranchAfterMonotonicLoads(
     const SmallVector<LoadInst*, 1>& MonotonicLoadInsts) {
   bool Changed = false;
   for (auto* LI : MonotonicLoadInsts) {
     const SmallVector<LoadInst*, 1>& MonotonicLoadInsts) {
   bool Changed = false;
   for (auto* LI : MonotonicLoadInsts) {
@@ -1032,29 +1038,7 @@ bool StoreDependOnValue(StoreInst* SI, Value* Dep) {
 
 
 bool CodeGenPrepare::runOnFunction(Function &F) {
 
 
 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<LoadInst*, 1> 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<LoadInst>(&*I);
-          if (LI->getOrdering() == Monotonic) {
-            MonotonicLoadInsts.push_back(LI);
-          }
-          break;
-        }
-        default: {
-          break;
-        }
-      }
-    }
-  }
-  bool EverMadeChange =
-      AddsFakeConditionalBranchAfterMonotonicLoads(MonotonicLoadInsts);
+  bool EverMadeChange = false;
 
   if (skipOptnoneFunction(F))
     return false;
 
   if (skipOptnoneFunction(F))
     return false;
@@ -1169,6 +1153,29 @@ bool CodeGenPrepare::runOnFunction(Function &F) {
       EverMadeChange |= simplifyOffsetableRelocate(*I);
   }
 
       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<LoadInst*, 1> 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<LoadInst>(&*I);
+          if (LI->getOrdering() == Monotonic) {
+            MonotonicLoadInsts.push_back(LI);
+          }
+          break;
+        }
+        default: {
+          break;
+        }
+      }
+    }
+  }
+  EverMadeChange |=
+      AddFakeConditionalBranchAfterMonotonicLoads(MonotonicLoadInsts);
+
   return EverMadeChange;
 }
 
   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++;
   // 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<BranchInst>(BB->getTerminator());
     if (!BI || !BI->isUnconditional())
     // If this block doesn't end with an uncond branch, ignore it.
     BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
     if (!BI || !BI->isUnconditional())
index 85d544d94984cdf3bcfb21a7e087c6fa87ee621f..4219016874296873120e8e8e67d08e602bf0d7fd 100644 (file)
@@ -40,7 +40,7 @@ using namespace llvm;
 #define DEBUG_TYPE "codegen"
 
 MachineBasicBlock::MachineBasicBlock(MachineFunction &MF, const BasicBlock *B)
 #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;
 }
 
   Insts.Parent = this;
 }
 
index 4beaa7f396436b47825b08499c522cba4fb1a802..f5e3056450116514c2960b7c7794a248257bef1b 100644 (file)
@@ -1271,10 +1271,7 @@ void MachineBlockPlacement::buildCFGChains(MachineFunction &F) {
       //
       bool needUpdateBr = true;
       if (!Cond.empty() && (!FBB || FBB == ChainBB)) {
       //
       bool needUpdateBr = true;
       if (!Cond.empty() && (!FBB || FBB == ChainBB)) {
-        // XXX-disabled: Don't bother with added fake conditional branches.
-        /*
         PrevBB->updateTerminator();
         PrevBB->updateTerminator();
-        */
         needUpdateBr = false;
         Cond.clear();
         TBB = FBB = nullptr;
         needUpdateBr = false;
         Cond.clear();
         TBB = FBB = nullptr;
index 6dca74d60026ff2044bb50a497f1a42d99e7c57e..5e542757b6383fce92373cc3cb29580d571720c6 100644 (file)
@@ -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 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.
   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),
   : 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());
   assert(debugLoc.hasTrivialDestructor() && "Expected trivial destructor");
 
   CapOperands = OperandCapacity::get(MI.getNumOperands());
index c075da4738ad6e012b0b6ced51cb88385957d47f..1676e2dfe08fb477b6cb01df9bec642449a880d7 100644 (file)
@@ -645,6 +645,47 @@ bool SelectionDAGISel::runOnMachineFunction(MachineFunction &mf) {
   // at this point.
   FuncInfo->clear();
 
   // 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()));
 
   DEBUG(dbgs() << "*** MachineFunction at end of ISel ***\n");
   DEBUG(MF->print(dbgs()));
 
index f61276fd436b49bb739e3489ea3686022f87ab5a..8e3cac27f4860c7e71dca4f8333be4f4cf8cccbd 100644 (file)
@@ -40,7 +40,8 @@ template class llvm::SymbolTableListTraits<Instruction>;
 
 BasicBlock::BasicBlock(LLVMContext &C, const Twine &Name, Function *NewParent,
                        BasicBlock *InsertBefore)
 
 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);
 
   if (NewParent)
     insertInto(NewParent, InsertBefore);
index c9c982ed7b5949bd8d1d897450d708146b2bbfc5..f398117de953b2f2d9a55673cfbaa0ca7c11ecab 100644 (file)
@@ -217,25 +217,6 @@ bool AArch64InstrInfo::ReverseBranchCondition(
   return false;
 }
 
   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())
 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;
 
       !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();
 
   // Remove the branch.
   I->eraseFromParent();
 
@@ -261,11 +237,6 @@ unsigned AArch64InstrInfo::RemoveBranch(MachineBasicBlock &MBB) const {
   if (!isCondBranchOpcode(I->getOpcode()))
     return 1;
 
   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;
   // Remove the branch.
   I->eraseFromParent();
   return 2;