Tail Duplication: Don't denormalize loops when duplicating early.

[iteratee]

Summary

Duplicating loop latches, headers, or pre-headers prevents certain loop based
optimizations. Now that we have tail-duplication during placement, it makes
sense to wait to duplicate these blocks until later, to allow other
optimizations to proceed.

[davidxl]

can you write test cases that demonstrate potentially blocked loop optimizations due to early taildup of those loop blocks?

[iteratee]

I'm going to put this change on hold and improve the loop rotation code. If I find another slowdown due to this, I'll revive this patch.

include/llvm/CodeGen/TailDuplicator.h

 
 extern cl::opt<unsigned> TailDupIndirectBranchSize;
 
 /// Utility class to perform tail duplication.
 class TailDuplicator {
   const TargetInstrInfo *TII;
   const TargetRegisterInfo *TRI;
   const MachineBranchProbabilityInfo *MBPI;
+  MachineLoopInfo *MLI;
   const MachineModuleInfo *MMI;
   MachineRegisterInfo *MRI;
   MachineFunction *MF;
   bool PreRegAlloc;
   bool LayoutMode;
   unsigned TailDupSize;
 
   // A list of virtual registers for which to update SSA form.
   SmallVector<unsigned, 16> SSAUpdateVRs;
 
   // For each virtual register in SSAUpdateVals keep a list of source virtual
   // registers.
   typedef std::vector<std::pair<MachineBasicBlock *, unsigned>> AvailableValsTy;
 
   DenseMap<unsigned, AvailableValsTy> SSAUpdateVals;
 
 public:
   /// Prepare to run on a specific machine function.
   /// @param MF - Function that will be processed
+  /// @param MLI - Machine Loop Info. Used to not duplicate latches, headers,
+  ///     or preheaders when duplicating early.
   /// @param MBPI - Branch Probability Info. Used to propagate correct
   ///     probabilities when modifying the CFG.
   /// @param LayoutMode - When true, don't use the existing layout to make
   ///     decisions.
   /// @param TailDupSize - Maxmimum size of blocks to tail-duplicate. Zero
   ///     default implies using the command line value TailDupSize.
   void initMF(MachineFunction &MF,
               const MachineBranchProbabilityInfo *MBPI,
-              bool LayoutMode, unsigned TailDupSize = 0);
+              MachineLoopInfo *MLI, bool LayoutMode, unsigned TailDupSize = 0);
   bool tailDuplicateBlocks();
   static bool isSimpleBB(MachineBasicBlock *TailBB);
   bool shouldTailDuplicate(bool IsSimple, MachineBasicBlock &TailBB);
   /// Returns true if TailBB can successfully be duplicated into PredBB
   bool canTailDuplicate(MachineBasicBlock *TailBB, MachineBasicBlock *PredBB);
   /// Tail duplicate a single basic block into its predecessors, and then clean
   /// up.
   /// If \p DuplicatePreds is not null, it will be updated to contain the list

lib/CodeGen/MachineBlockPlacement.cpp

bool MachineBlockPlacement::runOnMachineFunction(MachineFunction &MF) {
   MLI = &getAnalysis<MachineLoopInfo>();
   TII = MF.getSubtarget().getInstrInfo();
   TLI = MF.getSubtarget().getTargetLowering();
   MDT = &getAnalysis<MachineDominatorTree>();
   if (TailDupPlacement) {
     unsigned TailDupSize = TailDuplicatePlacementThreshold;
     if (MF.getFunction()->optForSize())
       TailDupSize = 1;
-    TailDup.initMF(MF, MBPI, /* LayoutMode */ true, TailDupSize);
+    TailDup.initMF(MF, MBPI, MLI, /* LayoutMode */ true, TailDupSize);
   }
 
   assert(BlockToChain.empty());
 
   buildCFGChains();
 
   // Changing the layout can create new tail merging opportunities.
   TargetPassConfig *PassConfig = &getAnalysis<TargetPassConfig>();

lib/CodeGen/TailDuplication.cpp

 //===-- TailDuplication.cpp - Duplicate blocks into predecessors' tails ---===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This pass duplicates basic blocks ending in unconditional branches into
 // the tails of their predecessors, using the TailDuplicator utility class.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/CodeGen/TailDuplicator.h"
 #include "llvm/IR/Function.h"
 #include "llvm/Support/Debug.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "tailduplication"
 

 INITIALIZE_PASS(TailDuplicatePass, "tailduplication", "Tail Duplication", false,
                 false)
 
 bool TailDuplicatePass::runOnMachineFunction(MachineFunction &MF) {
   if (skipFunction(*MF.getFunction()))
     return false;
 
   auto MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
+  auto MLI = &getAnalysis<MachineLoopInfo>();
 
-  Duplicator.initMF(MF, MBPI, /* LayoutMode */ false);
+  Duplicator.initMF(MF, MBPI, MLI, /* LayoutMode */ false);
 
   bool MadeChange = false;
   while (Duplicator.tailDuplicateBlocks())
     MadeChange = true;
 
   return MadeChange;
 }
 
 void TailDuplicatePass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequired<MachineBranchProbabilityInfo>();
+  AU.addRequired<MachineLoopInfo>();
   MachineFunctionPass::getAnalysisUsage(AU);
 }

lib/CodeGen/TailDuplicator.cpp

TailDupVerify("tail-dup-verify",
                   cl::desc("Verify sanity of PHI instructions during taildup"),
                   cl::init(false), cl::Hidden);
 
 static cl::opt<unsigned> TailDupLimit("tail-dup-limit", cl::init(~0U),
                                       cl::Hidden);
 
 void TailDuplicator::initMF(MachineFunction &MFin,
                             const MachineBranchProbabilityInfo *MBPIin,
+                            MachineLoopInfo *MLIin,
                             bool LayoutModeIn, unsigned TailDupSizeIn) {
   MF = &MFin;
   TII = MF->getSubtarget().getInstrInfo();
   TRI = MF->getSubtarget().getRegisterInfo();
   MRI = &MF->getRegInfo();
   MMI = &MF->getMMI();
   MBPI = MBPIin;
+  MLI = MLIin;
   TailDupSize = TailDupSizeIn;
 
   assert(MBPI != nullptr && "Machine Branch Probability Info required");
+  assert((LayoutModeIn || MLI != nullptr) &&
+         "Machine Loop Info required in non-layout mode.");
 
   LayoutMode = LayoutModeIn;
   PreRegAlloc = MRI->isSSA();
 }
 
 static void VerifyPHIs(MachineFunction &MF, bool CheckExtra) {
   for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ++I) {
     MachineBasicBlock *MBB = &*I;
bool TailDuplicator::shouldTailDuplicate(bool IsSimple,
   // A similar check is necessary in MachineBlockPlacement to make sure pairs of
   // blocks with unanalyzable fallthrough get layed out contiguously.
   MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
   SmallVector<MachineOperand, 4> PredCond;
   if (TII->analyzeBranch(TailBB, PredTBB, PredFBB, PredCond, true)
       && TailBB.canFallThrough())
     return false;
 
+  // When tail-duplicating relatively early, we shouldn't de-normalize loops by
+  // duplicating latches, headers, or loop-predecessors. This interferes with
+  // later optimizations. During layout this is fine.
+  if (!LayoutMode) {
+    MachineLoop *ML = MLI->getLoopFor(&TailBB);
+    if (ML && (&TailBB == ML->getHeader() ||
+               &TailBB == ML->getLoopLatch()))
+      return false;
+    for (auto SB : TailBB.successors()) {
+      MachineLoop *SML = MLI->getLoopFor(SB);
+      if (SML && (&TailBB == SML->getLoopPredecessor()))
+        return false;
+    }
+  }
+
   // If the target has hardware branch prediction that can handle indirect
   // branches, duplicating them can often make them predictable when there
   // are common paths through the code.  The limit needs to be high enough
   // to allow undoing the effects of tail merging and other optimizations
   // that rearrange the predecessors of the indirect branch.
 
   bool HasLocalIndirectbr = false;
   if (!TailBB.empty()) {

 void TailDuplicator::removeDeadBlock(
     MachineBasicBlock *MBB,
     llvm::function_ref<void(MachineBasicBlock *)> *RemovalCallback) {
   assert(MBB->pred_empty() && "MBB must be dead!");
   DEBUG(dbgs() << "\nRemoving MBB: " << *MBB);
 
   if (RemovalCallback)
     (*RemovalCallback)(MBB);
+  if (MLI)
+    MLI->removeBlock(MBB);
 
   // Remove all successors.
   while (!MBB->succ_empty())
     MBB->removeSuccessor(MBB->succ_end() - 1);
 
   // Remove the block.
   MBB->eraseFromParent();
 }
 
 } // End llvm namespace

test/CodeGen/WebAssembly/cfg-stackify.ll

exit:
   store volatile i32 4, i32* %p
   ret i32 0
 }
 
 ; CHECK-LABEL: doublediamond_in_a_loop:
 ; CHECK: .LBB11_1:
 ; CHECK: loop{{$}}
 ; CHECK: block{{$}}
+; CHECK: block{{$}}
 ; CHECK: br_if           0, $0{{$}}
 ; CHECK: br              1{{$}}
 ; CHECK: .LBB11_3:
-; CHECK: end_block{{$}}
+; CHECK-NEXT: end_block{{$}}
 ; CHECK: block{{$}}
 ; CHECK: br_if           0, $1{{$}}
 ; CHECK: br              1{{$}}
 ; CHECK: .LBB11_5:
-; CHECK: br              0{{$}}
+; CHECK-NEXT: end_block{{$}}
 ; CHECK: .LBB11_6:
+; CHECK-NEXT: end_block{{$}}
+; CHECK: br              0{{$}}
+; CHECK: .LBB11_7:
 ; CHECK-NEXT: end_loop{{$}}
 ; OPT-LABEL: doublediamond_in_a_loop:
 ; OPT:      .LBB11_1:
 ; OPT:      loop{{$}}
 ; OPT:      block{{$}}
-; OPT:      br_if           0, {{[^,]+}}{{$}}
+; OPT:      block{{$}}
 ; OPT:      block{{$}}
 ; OPT:      br_if           0, {{[^,]+}}{{$}}
+; OPT:      br_if           1, {{[^,]+}}{{$}}
 ; OPT:      br              2{{$}}
 ; OPT-NEXT: .LBB11_4:
 ; OPT-NEXT: end_block{{$}}
 ; OPT:      br              1{{$}}
 ; OPT:      .LBB11_5:
 ; OPT-NEXT: end_block{{$}}
-; OPT:      br              0{{$}}
 ; OPT:      .LBB11_6:
+; OPT-NEXT: end_block{{$}}
+; OPT:      br              0{{$}}
+; OPT:      .LBB11_7:
 ; OPT-NEXT: end_loop{{$}}
 define i32 @doublediamond_in_a_loop(i32 %a, i32 %b, i32* %p) {
 entry:
   br label %header
 header:
   %c = icmp eq i32 %a, 0
   %d = icmp eq i32 %b, 0
   store volatile i32 0, i32* %p

test/CodeGen/X86/avx512-i1test.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
-; RUN: llc < %s -mtriple=x86_64-apple-darwin -mcpu=knl | FileCheck %s
+; RUN: llc -O2 < %s -mtriple=x86_64-apple-darwin -mcpu=knl | FileCheck %s
 
 ; ModuleID = 'bugpoint-reduced-simplified.bc'
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 define void @func() {
 ; CHECK-LABEL: func:
 ; CHECK:       ## BB#0: ## %L_10
 ; CHECK-NEXT:    kortestw %k0, %k0
 ; CHECK-NEXT:    je LBB0_1
 ; CHECK-NEXT:  ## BB#3: ## %L_30
 ; CHECK-NEXT:    retq
 ; CHECK-NEXT:    .p2align 4, 0x90
 ; CHECK-NEXT:  LBB0_2: ## %bb35
 ; CHECK-NEXT:    ## in Loop: Header=BB0_1 Depth=1
 ; CHECK-NEXT:    kortestw %k0, %k0
+; CHECK-NEXT:    kortestw %k0, %k0
 ; CHECK-NEXT:  LBB0_1: ## %bb33
 ; CHECK-NEXT:    ## =>This Inner Loop Header: Depth=1
 ; CHECK-NEXT:    kortestw %k0, %k0
 ; CHECK-NEXT:    jne LBB0_1
 ; CHECK-NEXT:    jmp LBB0_2
 bb1:
   br i1 undef, label %L_10, label %L_10
 

test/CodeGen/X86/tail-dup-no-denormalize-loops.ll

+; RUN: llc -O2 %s -o - | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+%struct.binaryTree = type { i32, %struct.binaryTree*, %struct.binaryTree* }
+
+; Function Attrs: norecurse nounwind readonly uwtable
+define i32 @memberOfSortedBinaryTree(%struct.binaryTree* readonly %tree, i32 %searchedValue) local_unnamed_addr #4 {
+entry:
+  %tobool122 = icmp eq %struct.binaryTree* %tree, null
+  br i1 %tobool122, label %while.end, label %while.cond.us.preheader.preheader
+
+while.cond.us.preheader.preheader:                ; preds = %entry
+  br label %while.cond.us.preheader
+
+while.cond.us.preheader:                          ; preds = %while.cond.outer.backedge, %while.cond.us.preheader.preheader
+  %tree.pn = phi %struct.binaryTree* [ %1, %while.cond.outer.backedge ], [ %tree, %while.cond.us.preheader.preheader ]
+  %value25 = getelementptr inbounds %struct.binaryTree, %struct.binaryTree* %tree.pn, i64 0, i32 0
+  %0 = load i32, i32* %value25, align 8
+  %cmp.us = icmp sgt i32 %0, %searchedValue
+  br i1 %cmp.us, label %if.then, label %if.else.us
+
+if.else.us:                                       ; preds = %while.cond.us.preheader
+  %cmp3.us = icmp slt i32 %0, %searchedValue
+  br i1 %cmp3.us, label %if.then4, label %while.end.loopexit
+
+; Make sure that %while.cond.outer.backedge is not duplicated into %if.then
+; CHECK: # %if.then{{$}}
+; CHECK-NEXT: # in Loop:
+; CHECK-NEXT: addq $8
+; CHECK-NEXT: jmp
+if.then:                                          ; preds = %while.cond.us.preheader
+  %left = getelementptr inbounds %struct.binaryTree, %struct.binaryTree* %tree.pn, i64 0, i32 1
+  br label %while.cond.outer.backedge
+
+while.cond.outer.backedge:                        ; preds = %if.then4, %if.then
+  %left.sink = phi %struct.binaryTree** [ %left, %if.then ], [ %right, %if.then4 ]
+  %1 = load %struct.binaryTree*, %struct.binaryTree** %left.sink, align 8
+  %tobool1 = icmp eq %struct.binaryTree* %1, null
+  br i1 %tobool1, label %while.end.loopexit, label %while.cond.us.preheader
+
+; Make sure that %while.cond.outer.backedge is not duplicated into %if.then4
+; CHECK: # %if.then4{{$}}
+; CHECK-NEXT: # in Loop:
+; CHECK-NEXT: addq $16
+; CHECK-NEXT: jmp
+if.then4:                                         ; preds = %if.else.us
+  %right = getelementptr inbounds %struct.binaryTree, %struct.binaryTree* %tree.pn, i64 0, i32 2
+  br label %while.cond.outer.backedge
+
+while.end.loopexit:                               ; preds = %while.cond.outer.backedge, %if.else.us
+  %found.0.lcssa.ph = phi i32 [ 0, %while.cond.outer.backedge ], [ 1, %if.else.us ]
+  br label %while.end
+
+while.end:                                        ; preds = %while.end.loopexit, %entry
+  %found.0.lcssa = phi i32 [ 0, %entry ], [ %found.0.lcssa.ph, %while.end.loopexit ]
+  ret i32 %found.0.lcssa
+}
+
+
+attributes #4 = { norecurse nounwind readonly uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }