[CodeGenPrepare] Fix ModifiedDT flag in optimizeSelectInst

[xur]

Summary

r344412 fixed a huge compile time regression but it needs ModifiedDT flag
to be maintained correctly in optimizations in optimizeBlock() and optimizeInst().

optimizeSelectInst() does not updated the flag ( it updates a different ModifiedDT in CodeGenPrepare class).

This patche propagates the flag in optimizeSelectInst() back to optimizeBlock().

I also change the name of ModifiedDT in CodeGenPrepare class to avoid confusion. It seems ModifiedDT in CodeGenPrepare class is not being used anywhere. We may want to delete it.

[tejohnson]

Thanks for the fix. A couple comments below.

lib/CodeGen/CodeGenPrepare.cpp

293–294

I'd either remove this completely, since it isn't used, or migrate to using this instead of passing around a flag parameter.

7248

I think this should still set ModifiedDT so that the caller handles it appropriately (see callsite in optimizeBlock).

The comment doesn't make sense to me...might be stale?

[xur]

lib/CodeGen/CodeGenPrepare.cpp

293–294

I think remove this field is better. The existing uses of this field will be kept in a ref parameter.

7248

We can remove all this.

[xur]

Integrated Teresa's comments.

Also using spatel's test in Bug 41004 which is much cleaner.
My test was using produced by bugpoint (reduced from clang PGO bootstrap) and needs branchweight.

[tejohnson]

Just got a report of an internal test failure from my commit, let me see if your patch fixes it.

lib/CodeGen/CodeGenPrepare.cpp

2045

Should this set the new ModifiedDT?

[tejohnson]

In D59139#1422924, @tejohnson wrote:

Just got a report of an internal test failure from my commit, let me see if your patch fixes it.

This patch fixes the test failure.

[xur]

lib/CodeGen/CodeGenPrepare.cpp

2045

Sorry for missing this one. We should.
I will update the patch.

[xur]

add one missing updates in last version of the patch.

[tejohnson]

LGTM

[spatel]

Minor: it would be better to make the test in IR (opt -codegenprepare), so it would live under test/Transforms/CodeGenPrepare/X86/. That's because this isn't really an x86 bug. It could affect any target, and the bug is really one of an IR transform. Along those lines, I would include auto-generated FileCheck output too even if the IR for this example is semi-useless, just so we know exactly what is coming out of CGP.

[xur]

changed test case based on spatel's comments.

[spatel]

test/Transforms/CodeGenPrepare/X86/optimizeSelect-DT.ll

24

typo - CEECK
You could avoid this kind of bug by using the script at utils/update_test_checks.py.

[xur]

using utils/update_test_checks.py to generate the test checks.

thanks the tip from spatel!

[tejohnson]

This change caused a compile time regression (that I referenced at the end of my summary in D59696). In this case, there are huge numbers of select instructions. After this change, since we now update the ModifiedDT correctly, the loop over the function in CodeGenPrepare::runOnFunction will break after each select is optimized, due to ModifiedDT being set. As mentioned in D59696, even after making the DT build lazy, there is still a large regression because of the number of times we re-walk the function.

I have a couple possible solutions, and am looking for guidance on what is preferable.

1. Reset the DT instead of existing the function walk. Now that D59696 is in and the DT is built lazily, instead of setting ModifiedDT true and breaking out of the function walk in runOnFunction() (which was previously required due to the DT being built for each function walk), we can simply reset the DT unique_ptr, which will force a rebuild of DT when it is next needed:

diff --git a/lib/CodeGen/CodeGenPrepare.cpp b/lib/CodeGen/CodeGenPrepare.cpp
index 9d642ba245c..bd9cc5e4158 100644

• a/lib/CodeGen/CodeGenPrepare.cpp

+++ b/lib/CodeGen/CodeGenPrepare.cpp
@@ -5962,7 +5962,7 @@ bool CodeGenPrepare::optimizeSelectInst(SelectInst *SI, bool &ModifiedDT) {

  !isFormingBranchFromSelectProfitable(TTI, TLI, SI))
return false;

• ModifiedDT = true;

+ DT.reset();

// Transform a sequence like this:
//    start:

In my test case, since apparently there are many more select instructions (which don't use the DT to optimize) than the type of instructions that need the DT, this fixes the regression. It may not always have an effect, say if selects were interspersed with instructions that need the DT to optimize, but it won't make matters worse than the current status quo (which would cause the function iteration to exit and the DT to be reset there). It's possible that other places that set ModifiedDT could get the same treatment, I just tried in optimizeSelectInst since that was the place affected by this patch and that caused my regression.

2. Optimize select insts before iterative function walk. Similar to how some of the other instructions are optimized before this iterative walk (e.g. splitBranchCondition()), since select instructions don't need the DT, and presumably don't need iterative optimization, we could do the select optimizations earlier:

diff --git a/lib/CodeGen/CodeGenPrepare.cpp b/lib/CodeGen/CodeGenPrepare.cpp
index 9d642ba245c..b2a0c8a9570 100644

• a/lib/CodeGen/CodeGenPrepare.cpp

+++ b/lib/CodeGen/CodeGenPrepare.cpp
@@ -465,6 +465,15 @@ bool CodeGenPrepare::runOnFunction(Function &F) {

// to help generate sane code for PHIs involving such edges.
EverMadeChange |= SplitIndirectBrCriticalEdges(F);

+ for (Function::iterator I = F.begin(); I != F.end(); ) {
+ BasicBlock *BB = &*I++;
+ CurInstIterator = BB->begin();
+ while (CurInstIterator != BB->end()) {
+ if (SelectInst *SI = dyn_cast<SelectInst>(&*CurInstIterator++))
+ EverMadeChange |= optimizeSelectInst(SI, ModifiedDT);
+ }
+ }
+

bool MadeChange = true;
while (MadeChange) {
  MadeChange = false;

Presumably this would be refactored into a separate function, similar to splitBranchCondition, the above was just a quick hack to test. The advantage of this second approach is that it will improve compile time in any other cases involving select instructions interspersed with instructions that need the DT to optimize.

However - this only eliminates 2/3 of the additional CGP overhead. Since I didn't remove the call to optimizeSelectInst from optimizeInst in this case, we may be finding additional selects to optimize during the iterative function optimization stage.

3. Similar to 2 but do the select optimization once per function walk:

diff --git a/lib/CodeGen/CodeGenPrepare.cpp b/lib/CodeGen/CodeGenPrepare.cpp
index 9d642ba245c..2241d4af206 100644

• a/lib/CodeGen/CodeGenPrepare.cpp

+++ b/lib/CodeGen/CodeGenPrepare.cpp
@@ -468,6 +468,14 @@ bool CodeGenPrepare::runOnFunction(Function &F) {

bool MadeChange = true;
while (MadeChange) {
  MadeChange = false;

+ for (Function::iterator I = F.begin(); I != F.end(); ) {
+ BasicBlock *BB = &*I++;
+ CurInstIterator = BB->begin();
+ while (CurInstIterator != BB->end()) {
+ if (SelectInst *SI = dyn_cast<SelectInst>(&*CurInstIterator++))
+ MadeChange |= optimizeSelectInst(SI, ModifiedDT);
+ }
+ }

DT.reset();
for (Function::iterator I = F.begin(); I != F.end(); ) {
  BasicBlock *BB = &*I++;

This removes the remaining overhead.

[spatel]

If #1 is a one-liner that doesn't change any existing tests, that sounds like a good choice.
#2 / #3 also sound like good options. IMO, the fact that we have or need to make that kind of structural change points out that CGP itself has gotten too big. According to its lead comment, this is supposed to be temporary spot for hacks prohibited by SDAG (ie, once we switch to global-isel, CGP should go away)...but CGP has become several independent passes in 1 file. The bigger change to correct these kinds of problems would be to split things into multiple passes.

[tejohnson]

In D59139#1444332, @spatel wrote:

If #1 is a one-liner that doesn't change any existing tests, that sounds like a good choice.

Basically, yes (I'd also remove the ModifiedDT parameter to that routine).

#2 / #3 also sound like good options. IMO, the fact that we have or need to make that kind of structural change points out that CGP itself has gotten too big. According to its lead comment, this is supposed to be temporary spot for hacks prohibited by SDAG (ie, once we switch to global-isel, CGP should go away)...but CGP has become several independent passes in 1 file. The bigger change to correct these kinds of problems would be to split things into multiple passes.

Yeah it seems that the structure is has gotten really unwieldy and haphazard (i.e. when the function walk needs to be completely restarted and which parts need to be iterative isn't clear to me).

I will go ahead and send a patch for #1 for now since it is very simple and addresses this regression specifically, by undoing the iteration change provoked by this fix.

lib/CodeGen/CodeGenPrepare.cpp

class CodeGenPrepare : public FunctionPass {
     /// Keep track of new GEP base after splitting the GEPs having large offset.
     SmallSet<AssertingVH<Value>, 2> NewGEPBases;
 
     /// Map serial numbers to Large offset GEPs.
     DenseMap<AssertingVH<GetElementPtrInst>, int> LargeOffsetGEPID;
 
     /// Keep track of SExt promoted.
     ValueToSExts ValToSExtendedUses;
 
-    /// True if CFG is modified in any way.
-    bool ModifiedDT;
-
     /// True if optimizing for size.
     bool OptSize;
 
     /// DataLayout for the Function being processed.
     const DataLayout *DL = nullptr;
 
   public:
     static char ID; // Pass identification, replacement for typeid
 
private:
     bool optimizeInst(Instruction *I, DominatorTree &DT, bool &ModifiedDT);
     bool optimizeMemoryInst(Instruction *MemoryInst, Value *Addr,
                             Type *AccessTy, unsigned AddrSpace);
     bool optimizeInlineAsmInst(CallInst *CS);
     bool optimizeCallInst(CallInst *CI, bool &ModifiedDT);
     bool optimizeExt(Instruction *&I);
     bool optimizeExtUses(Instruction *I);
     bool optimizeLoadExt(LoadInst *Load);
-    bool optimizeSelectInst(SelectInst *SI);
+    bool optimizeSelectInst(SelectInst *SI, bool &ModifiedDT);
     bool optimizeShuffleVectorInst(ShuffleVectorInst *SVI);
     bool optimizeSwitchInst(SwitchInst *SI);
     bool optimizeExtractElementInst(Instruction *Inst);
-    bool dupRetToEnableTailCallOpts(BasicBlock *BB);
+    bool dupRetToEnableTailCallOpts(BasicBlock *BB, bool &ModifiedDT);
     bool placeDbgValues(Function &F);
     bool canFormExtLd(const SmallVectorImpl<Instruction *> &MovedExts,
                       LoadInst *&LI, Instruction *&Inst, bool HasPromoted);
     bool tryToPromoteExts(TypePromotionTransaction &TPT,
                           const SmallVectorImpl<Instruction *> &Exts,
                           SmallVectorImpl<Instruction *> &ProfitablyMovedExts,
                           unsigned CreatedInstsCost = 0);
     bool mergeSExts(Function &F, DominatorTree &DT);
     bool splitLargeGEPOffsets();
     bool performAddressTypePromotion(
         Instruction *&Inst,
         bool AllowPromotionWithoutCommonHeader,
         bool HasPromoted, TypePromotionTransaction &TPT,
         SmallVectorImpl<Instruction *> &SpeculativelyMovedExts);
-    bool splitBranchCondition(Function &F);
+    bool splitBranchCondition(Function &F, bool &ModifiedDT);
     bool simplifyOffsetableRelocate(Instruction &I);
 
     bool tryToSinkFreeOperands(Instruction *I);
   };
 
 } // end anonymous namespace
 
 char CodeGenPrepare::ID = 0;
bool CodeGenPrepare::runOnFunction(Function &F) {
 
   DL = &F.getParent()->getDataLayout();
 
   bool EverMadeChange = false;
   // Clear per function information.
   InsertedInsts.clear();
   PromotedInsts.clear();
 
-  ModifiedDT = false;
   if (auto *TPC = getAnalysisIfAvailable<TargetPassConfig>()) {
     TM = &TPC->getTM<TargetMachine>();
     SubtargetInfo = TM->getSubtargetImpl(F);
     TLI = SubtargetInfo->getTargetLowering();
     TRI = SubtargetInfo->getRegisterInfo();
   }
   TLInfo = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
   TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
while (BB != nullptr) {
       BB = Next;
     }
   }
 
   // Eliminate blocks that contain only PHI nodes and an
   // unconditional branch.
   EverMadeChange |= eliminateMostlyEmptyBlocks(F);
 
+  bool ModifiedDT = false;
   if (!DisableBranchOpts)
-    EverMadeChange |= splitBranchCondition(F);
+    EverMadeChange |= splitBranchCondition(F, ModifiedDT);
 
   // Split some critical edges where one of the sources is an indirect branch,
   // to help generate sane code for PHIs involving such edges.
   EverMadeChange |= SplitIndirectBrCriticalEdges(F);
 
   bool MadeChange = true;
   while (MadeChange) {
     MadeChange = false;

 ///   ret i32 %tmp0
 /// bb1:
 ///   %tmp1 = tail call i32 @f1()
 ///   ret i32 %tmp1
 /// bb2:
 ///   %tmp2 = tail call i32 @f2()
 ///   ret i32 %tmp2
 /// @endcode
-bool CodeGenPrepare::dupRetToEnableTailCallOpts(BasicBlock *BB) {
+bool CodeGenPrepare::dupRetToEnableTailCallOpts(BasicBlock *BB, bool &ModifiedDT) {
   if (!TLI)
     return false;
 
   ReturnInst *RetI = dyn_cast<ReturnInst>(BB->getTerminator());
   if (!RetI)
     return false;
 
   PHINode *PN = nullptr;
for (unsigned i = 0, e = TailCalls.size(); i != e; ++i) {
     // the return block.
     BasicBlock *CallBB = CI->getParent();
     BranchInst *BI = dyn_cast<BranchInst>(CallBB->getTerminator());
     if (!BI || !BI->isUnconditional() || BI->getSuccessor(0) != BB)
       continue;
 
     // Duplicate the return into CallBB.
     (void)FoldReturnIntoUncondBranch(RetI, BB, CallBB);
     ModifiedDT = Changed = true;
     ++NumRetsDup;
   }
 
   // If we eliminated all predecessors of the block, delete the block now.
   if (Changed && !BB->hasAddressTaken() && pred_begin(BB) == pred_end(BB))
     BB->eraseFromParent();
 
   return Changed;
assert(DefSI->getCondition() == SI->getCondition() &&
            "The condition of DefSI does not match with SI");
     V = (isTrue ? DefSI->getTrueValue() : DefSI->getFalseValue());
   }
   return V;
 }
 
 /// If we have a SelectInst that will likely profit from branch prediction,
 /// turn it into a branch.
-bool CodeGenPrepare::optimizeSelectInst(SelectInst *SI) {
+bool CodeGenPrepare::optimizeSelectInst(SelectInst *SI, bool &ModifiedDT) {
   // If branch conversion isn't desirable, exit early.
   if (DisableSelectToBranch || OptSize || !TLI)
     return false;
 
   // Find all consecutive select instructions that share the same condition.
   SmallVector<SelectInst *, 2> ASI;
   ASI.push_back(SI);
   for (BasicBlock::iterator It = ++BasicBlock::iterator(SI);
bool CodeGenPrepare::optimizeInst(Instruction *I, DominatorTree &DT,
 
   if (tryToSinkFreeOperands(I))
     return true;
 
   if (CallInst *CI = dyn_cast<CallInst>(I))
     return optimizeCallInst(CI, ModifiedDT);
 
   if (SelectInst *SI = dyn_cast<SelectInst>(I))
-    return optimizeSelectInst(SI);
+    return optimizeSelectInst(SI, ModifiedDT);
 
   if (ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(I))
     return optimizeShuffleVectorInst(SVI);
 
   if (auto *Switch = dyn_cast<SwitchInst>(I))
     return optimizeSwitchInst(Switch);
 
   if (isa<ExtractElementInst>(I))
while (TLI && MadeBitReverse) {
     for (auto &I : reverse(BB)) {
       if (makeBitReverse(I, *DL, *TLI)) {
         MadeBitReverse = MadeChange = true;
         ModifiedDT = true;
         break;
       }
     }
   }
-  MadeChange |= dupRetToEnableTailCallOpts(&BB);
+  MadeChange |= dupRetToEnableTailCallOpts(&BB, ModifiedDT);
 
   return MadeChange;
 }
 
 // llvm.dbg.value is far away from the value then iSel may not be able
 // handle it properly. iSel will drop llvm.dbg.value if it can not
 // find a node corresponding to the value.
 bool CodeGenPrepare::placeDbgValues(Function &F) {

 ///     br i1 %1, label %TrueBB, label %FalseBB
 /// \endcode
 /// This usually allows instruction selection to do even further optimizations
 /// and combine the compare with the branch instruction. Currently this is
 /// applied for targets which have "cheap" jump instructions.
 ///
 /// FIXME: Remove the (equivalent?) implementation in SelectionDAG.
 ///
-bool CodeGenPrepare::splitBranchCondition(Function &F) {
+bool CodeGenPrepare::splitBranchCondition(Function &F, bool &ModifiedDT) {
   if (!TM || !TM->Options.EnableFastISel || !TLI || TLI->isJumpExpensive())
     return false;
 
   bool MadeChange = false;
   for (auto &BB : F) {
     // Does this BB end with the following?
     //   %cond1 = icmp|fcmp|binary instruction ...
     //   %cond2 = icmp|fcmp|binary instruction ...
if (Opc == Instruction::Or) {
         NewTrueWeight = 2 * TrueWeight;
         NewFalseWeight = FalseWeight;
         scaleWeights(NewTrueWeight, NewFalseWeight);
         Br2->setMetadata(LLVMContext::MD_prof, MDBuilder(Br2->getContext())
                          .createBranchWeights(TrueWeight, FalseWeight));
       }
     }
 
-    // Note: No point in getting fancy here, since the DT info is never
-    // available to CodeGenPrepare.
     ModifiedDT = true;
-
     MadeChange = true;
 
     LLVM_DEBUG(dbgs() << "After branch condition splitting\n"; BB.dump();
                TmpBB->dump());
   }
   return MadeChange;
 }

test/Transforms/CodeGenPrepare/X86/optimizeSelect-DT.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -codegenprepare < %s | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define i1 @PR41004(i32 %x, i32 %y, i32 %t1) {
+; CHECK-LABEL: @PR41004(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[T0:%.*]] = icmp eq i32 [[Y:%.*]], 1
+; CHECK-NEXT:    br i1 [[T0]], label [[SELECT_TRUE_SINK:%.*]], label [[SELECT_END:%.*]]
+; CHECK:       select.true.sink:
+; CHECK-NEXT:    [[REM:%.*]] = srem i32 [[X:%.*]], 2
+; CHECK-NEXT:    br label [[SELECT_END]]
+; CHECK:       select.end:
+; CHECK-NEXT:    [[MUL:%.*]] = phi i32 [ [[REM]], [[SELECT_TRUE_SINK]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[TMP0:%.*]] = call { i32, i1 } @llvm.usub.with.overflow.i32(i32 [[T1:%.*]], i32 1)
+; CHECK-NEXT:    [[MATH:%.*]] = extractvalue { i32, i1 } [[TMP0]], 0
+; CHECK-NEXT:    [[OV:%.*]] = extractvalue { i32, i1 } [[TMP0]], 1
+; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[MATH]], [[MUL]]
+; CHECK-NEXT:    ret i1 [[OV]]
+;
+entry:
+  %rem = srem i32 %x, 2
+  %t0 = icmp eq i32 %y, 1
+  %mul = select i1 %t0, i32 %rem, i32 0
+  %neg = add i32 %t1, -1
+  %add = add i32 %neg, %mul
+  br label %if
+
+if:
+  %tobool = icmp eq i32 %t1, 0
+  ret i1 %tobool
+}