[BlockPlacement] Disable block placement tail duplciation in structured CFG.

[timshen]

Summary

Tail duplication easily breaks the structure of CFG, e.g. duplicating on
a region entry. If the structure is intended to be preserved, then we
may want to configure tail duplication, or disable it for structured
CFG. From our benchmark results disabling it doesn't cause performance
regression.

Notice that this currently affects AMDGPU backend. In the next patch, I
also plan to turn on requiresStructuredCFG for NVPTX.

All unit tests still pass.

[jlebar]

Can we split out the NVPTX changes from the tail-duplication changes? This will make it easier to roll back &c.

Other than that, LGTM.

llvm/lib/Target/NVPTX/NVPTXTargetMachine.cpp

50 ↗

(On Diff #140164)

ofo

[timshen]

Splitted the patch.

[jlebar]

Would like arsenm or someone else from AMDGPU to sign off on this, but lgtm.

[arsenm]

Don't really care because amdgcn doesn't use this anymore

[jlebar]

In D45008#1052948, @arsenm wrote:

Don't really care because amdgcn doesn't use this anymore

Thanks, Matt!

llvm/trunk/lib/CodeGen/MachineBlockPlacement.cpp

public:
   static char ID; // Pass identification, replacement for typeid
 
   MachineBlockPlacement() : MachineFunctionPass(ID) {
     initializeMachineBlockPlacementPass(*PassRegistry::getPassRegistry());
   }
 
   bool runOnMachineFunction(MachineFunction &F) override;
 
+  bool allowTailDupPlacement() const {
+    assert(F);
+    return TailDupPlacement && !F->getTarget().requiresStructuredCFG();
+  }
+
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<MachineBranchProbabilityInfo>();
     AU.addRequired<MachineBlockFrequencyInfo>();
     if (TailDupPlacement)
       AU.addRequired<MachinePostDominatorTree>();
     AU.addRequired<MachineLoopInfo>();
     AU.addRequired<TargetPassConfig>();
     MachineFunctionPass::getAnalysisUsage(AU);
MachineBlockPlacement::getBestTrellisSuccessor(
   // that instead. Otherwise merge the triangle edge now while we know it is
   // optimal.
   if (BestA.Dest == BestB.Src) {
     // The edges are BB->Succ1->Succ2, and we're looking to see if BB->Succ2
     // would be better.
     MachineBasicBlock *Succ1 = BestA.Dest;
     MachineBasicBlock *Succ2 = BestB.Dest;
     // Check to see if tail-duplication would be profitable.
-    if (TailDupPlacement && shouldTailDuplicate(Succ2) &&
+    if (allowTailDupPlacement() && shouldTailDuplicate(Succ2) &&
         canTailDuplicateUnplacedPreds(BB, Succ2, Chain, BlockFilter) &&
         isProfitableToTailDup(BB, Succ2, MBPI->getEdgeProbability(BB, Succ1),
                               Chain, BlockFilter)) {
       DEBUG(BranchProbability Succ2Prob = getAdjustedProbability(
                 MBPI->getEdgeProbability(BB, Succ2), AdjustedSumProb);
             dbgs() << "    Selected: " << getBlockName(Succ2)
                    << ", probability: " << Succ2Prob << " (Tail Duplicate)\n");
       Result.BB = Succ2;
MachineBlockPlacement::getBestTrellisSuccessor(
   DEBUG(BranchProbability SuccProb = getAdjustedProbability(
             MBPI->getEdgeProbability(BB, TrellisSucc), AdjustedSumProb);
         dbgs() << "    Selected: " << getBlockName(TrellisSucc)
                << ", probability: " << SuccProb << " (Trellis)\n");
   Result.BB = TrellisSucc;
   return Result;
 }
 
-/// When the option TailDupPlacement is on, this method checks if the
+/// When the option allowTailDupPlacement() is on, this method checks if the
 /// fallthrough candidate block \p Succ (of block \p BB) can be tail-duplicated
 /// into all of its unplaced, unfiltered predecessors, that are not BB.
 bool MachineBlockPlacement::canTailDuplicateUnplacedPreds(
     const MachineBasicBlock *BB, MachineBasicBlock *Succ,
     const BlockChain &Chain, const BlockFilterSet *BlockFilter) {
   if (!shouldTailDuplicate(Succ))
     return false;
 
BranchProbability SuccProb =
         getAdjustedProbability(RealSuccProb, AdjustedSumProb);
 
     BlockChain &SuccChain = *BlockToChain[Succ];
     // Skip the edge \c BB->Succ if block \c Succ has a better layout
     // predecessor that yields lower global cost.
     if (hasBetterLayoutPredecessor(BB, Succ, SuccChain, SuccProb, RealSuccProb,
                                    Chain, BlockFilter)) {
       // If tail duplication would make Succ profitable, place it.
-      if (TailDupPlacement && shouldTailDuplicate(Succ))
+      if (allowTailDupPlacement() && shouldTailDuplicate(Succ))
         DupCandidates.push_back(std::make_tuple(SuccProb, Succ));
       continue;
     }
 
     DEBUG(
         dbgs() << "    Candidate: " << getBlockName(Succ) << ", probability: "
                << SuccProb
                << (SuccChain.UnscheduledPredecessors != 0 ? " (CFG break)" : "")
while (true) {
     assert(*std::prev(Chain.end()) == BB && "BB Not found at end of chain.");
 
 
     // Look for the best viable successor if there is one to place immediately
     // after this block.
     auto Result = selectBestSuccessor(BB, Chain, BlockFilter);
     MachineBasicBlock* BestSucc = Result.BB;
     bool ShouldTailDup = Result.ShouldTailDup;
-    if (TailDupPlacement)
+    if (allowTailDupPlacement())
       ShouldTailDup |= (BestSucc && shouldTailDuplicate(BestSucc));
 
     // If an immediate successor isn't available, look for the best viable
     // block among those we've identified as not violating the loop's CFG at
     // this point. This won't be a fallthrough, but it will increase locality.
     if (!BestSucc)
       BestSucc = selectBestCandidateBlock(Chain, BlockWorkList);
     if (!BestSucc)
       BestSucc = selectBestCandidateBlock(Chain, EHPadWorkList);
 
     if (!BestSucc) {
       BestSucc = getFirstUnplacedBlock(Chain, PrevUnplacedBlockIt, BlockFilter);
       if (!BestSucc)
         break;
 
       DEBUG(dbgs() << "Unnatural loop CFG detected, forcibly merging the "
                       "layout successor until the CFG reduces\n");
     }
 
     // Placement may have changed tail duplication opportunities.
     // Check for that now.
-    if (TailDupPlacement && BestSucc && ShouldTailDup) {
+    if (allowTailDupPlacement() && BestSucc && ShouldTailDup) {
       // If the chosen successor was duplicated into all its predecessors,
       // don't bother laying it out, just go round the loop again with BB as
       // the chain end.
       if (repeatedlyTailDuplicateBlock(BestSucc, BB, LoopHeaderBB, Chain,
                                        BlockFilter, PrevUnplacedBlockIt))
         continue;
     }
 
if (PassConfig->getOptLevel() >= CodeGenOpt::Aggressive) {
     // At O3 we should be more willing to copy blocks for tail duplication. This
     // increases size pressure, so we only do it at O3
     // Do this unless only the regular threshold is explicitly set.
     if (TailDupPlacementThreshold.getNumOccurrences() == 0 ||
         TailDupPlacementAggressiveThreshold.getNumOccurrences() != 0)
       TailDupSize = TailDupPlacementAggressiveThreshold;
   }
 
-  if (TailDupPlacement) {
+  if (allowTailDupPlacement()) {
     MPDT = &getAnalysis<MachinePostDominatorTree>();
     if (MF.getFunction().optForSize())
       TailDupSize = 1;
     bool PreRegAlloc = false;
     TailDup.initMF(MF, PreRegAlloc, MBPI, /* LayoutMode */ true, TailDupSize);
     precomputeTriangleChains();
   }