[CodeGenPrepare] limit overflow intrinsic matching to a single basic block

[spatel]

Summary

Using/updating a dominator tree to match math overflow patterns may be very expensive in compile-time, so just handle the single-block case.

Also, we were restarting the iterator loops when doing the overflow intrinsic transforms by marking the dominator tree for update. That was done to prevent iterating over a removed instruction. But we can postpone the deletion using the existing "RemovedInsts" structure, and that means we don't need to update the DT.

See post-commit thread for rL354298 for more details:
http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20190422/646276.html

[reames]

I think I'm missing something basic here. CGP will iterate until done, including trivial DCE. Given that, why not just leave the instructions in the IR and let the next iteration remove them? It would trigger an extra iteration, which might be undesirable, but would it be incorrect? That would seem better than invalidating the DomTree, which just forces a new iteration anyways...

Actually, it doesn't look like it includes trivial DCE. Maybe it should?

Assuming the answer is that yet, that would be correct, then this patch becomes a smallish optimization over an extra iteration right?

Thinking through the logic, we don't need to worry about the cmp instruction since the caller advanced the iterator beyond it. So, the only concern is the binary operator. But correct me if I'm wrong, don't you require the BO to dominate the Cmp? If so, then haven't we already iterated past that instruction? How do we have an iterator invalidation problem at all?

[spatel]

In D61075#1478122, @reames wrote:

I think I'm missing something basic here. CGP will iterate until done, including trivial DCE. Given that, why not just leave the instructions in the IR and let the next iteration remove them? It would trigger an extra iteration, which might be undesirable, but would it be incorrect? That would seem better than invalidating the DomTree, which just forces a new iteration anyways...

Actually, it doesn't look like it includes trivial DCE. Maybe it should?

Assuming the answer is that yet, that would be correct, then this patch becomes a smallish optimization over an extra iteration right?

Yes, that sounds right. If CGP included DCE, then it would be easier to just rely on that for cleanup. Unfortunately, it doesn't. I don't know the full history here, but I suspect that since CGP was intended to be a temporary hack (see opening comment in the source file), nobody has bothered to invest in doing better.

But since this patch didn't solve the compile-time problem anyway, I'm going to propose a bigger fix anyway...

Thinking through the logic, we don't need to worry about the cmp instruction since the caller advanced the iterator beyond it. So, the only concern is the binary operator. But correct me if I'm wrong, don't you require the BO to dominate the Cmp? If so, then haven't we already iterated past that instruction? How do we have an iterator invalidation problem at all?

No, the binop does not necessarily dominate the compare if they are within a single block. If they are independent ops (no def-use relationship), then we don't know which order they are in within that block. We have regression tests with those patterns.

The history of these overflow transforms is that we wanted to do these as canonicalizations in instcombine, but that caused perf regressions. So then the add overflow transform got dumped here in CGP with a TLI hook to allow it. Then, I noticed that we weren't getting that transform consistently with some constant operands or the subtract overflow sibling. So I improved the pattern matching, and idealistically/naively tried to allow the transforms in all cross-block cases as long as the target said it was legal.

But that still caused perf regressions, so the transform was limited in 2 ways: (1) avoid hoisting the binop into a dominating cmp block and (2) avoid hoisting either op unless we had a direct predecessor/successor relationship.

At this point, I'm going to propose that we just give up on any cross-block attempts. I don't have any perf data to show that we got any wins from that, and I don't think anyone has the will to fix the backend problems and compile-time issues.

[spatel]

Patch updated:
Don't try to match this pattern across blocks. That means we are not using a dominator tree at all, so if this doesn't restore compile-time perf, I'm not sure what would. :)

Limiting this transform to a single block means it really shouldn't be in CGP anymore. It could be implemented in SDAG. But I'd prefer to leave that to a follow-up patch once we confirm that this (1) restores compile-time and (2) does not cause perf regressions.

[spatel]

Ping.

[hfinkel]

llvm/lib/CodeGen/CodeGenPrepare.cpp

1191

I'm actually not sure why this would be true, at least in the multiple-blocks case. If they're in the same block, then the dominance check can be expensive, but that's because of the scanning involved. And, if that's true, then an OBB cache might address the problem. In any case, I don't think that having point (3) here is useful, could be misleading, and isn't necessary given the first two points.

1220

If the DT was expensive, I'd actually suspect it was this scanning that made it so on large blocks. Does this happen multiple times such that a OBB cache would help?

[spatel]

llvm/lib/CodeGen/CodeGenPrepare.cpp

1220

I only have 1 test case to play with (I'll try to attach it to this review for reference), and it doesn't have large blocks. It's a ~66K line function with ~6K blocks.

From what I can tell, the problem is that we reset the DT on any made change up at line 472. That seems like overkill, but I don't have the motivation to sort out which of the transforms in the loop could bypass that reset.

[spatel]

code-gen-prepare-test.ll5 MBDownload

- this is the test file provided by @yrouban that showed the compile-time regression and would improve by avoiding DT altogether as proposed in this patch.

[hfinkel]

llvm/lib/CodeGen/CodeGenPrepare.cpp

1220

Okay. If you're going to mention that DT is slow, please put in the comment something about the fact that it's slow because we need to recompute it a lot (and, perhaps, why).

[spatel]

Patch updated:
Added more details to the code comment about using the dominator tree. Ie, if anyone wants to use it for this transform (or possibly others), they are probably going to have to alter the function-level CGP loop to avoid resetting the DT on every change.

[hfinkel]

LGTM

[spatel]

Reopening because the commit was reverted at rL359908. Must've missed some detail about using the RemovedInsts structure.

llvm/lib/CodeGen/CodeGenPrepare.cpp

bool performAddressTypePromotion(
         bool HasPromoted, TypePromotionTransaction &TPT,
         SmallVectorImpl<Instruction *> &SpeculativelyMovedExts);
     bool splitBranchCondition(Function &F, bool &ModifiedDT);
     bool simplifyOffsetableRelocate(Instruction &I);
 
     bool tryToSinkFreeOperands(Instruction *I);
     bool replaceMathCmpWithIntrinsic(BinaryOperator *BO, CmpInst *Cmp,
                                      Intrinsic::ID IID);
-    bool optimizeCmp(CmpInst *Cmp, bool &ModifiedDT);
-    bool combineToUSubWithOverflow(CmpInst *Cmp, bool &ModifiedDT);
-    bool combineToUAddWithOverflow(CmpInst *Cmp, bool &ModifiedDT);
+    bool optimizeCmp(CmpInst *Cmp);
+    bool combineToUSubWithOverflow(CmpInst *Cmp);
+    bool combineToUAddWithOverflow(CmpInst *Cmp);
   };
 
 } // end anonymous namespace
 
 char CodeGenPrepare::ID = 0;
 
 INITIALIZE_PASS_BEGIN(CodeGenPrepare, DEBUG_TYPE,
                       "Optimize for code generation", false, false)
for (Function::iterator I = F.begin(); I != F.end(); ) {
       if (ModifiedDTOnIteration)
         break;
     }
     if (EnableTypePromotionMerge && !ValToSExtendedUses.empty())
       MadeChange |= mergeSExts(F);
     if (!LargeOffsetGEPMap.empty())
       MadeChange |= splitLargeGEPOffsets();
 
-    // Really free removed instructions during promotion.
-    for (Instruction *I : RemovedInsts)
+    // Really free instructions removed during promotion or kept around to
+    // improve efficiency (see comments in overflow intrinsic transforms).
+    for (Instruction *I : RemovedInsts) {
+      if (I->getParent())
+        I->removeFromParent();
       I->deleteValue();
+    }
 
     EverMadeChange |= MadeChange;
     SeenChainsForSExt.clear();
     ValToSExtendedUses.clear();
     RemovedInsts.clear();
     LargeOffsetGEPMap.clear();
     LargeOffsetGEPID.clear();
   }
bool CodeGenPrepare::replaceMathCmpWithIntrinsic(BinaryOperator *BO,
                                                  Intrinsic::ID IID) {
   // We allow matching the canonical IR (add X, C) back to (usubo X, -C).
   Value *Arg0 = BO->getOperand(0);
   Value *Arg1 = BO->getOperand(1);
   if (BO->getOpcode() == Instruction::Add &&
       IID == Intrinsic::usub_with_overflow) {
     assert(isa<Constant>(Arg1) && "Unexpected input for usubo");
     Arg1 = ConstantExpr::getNeg(cast<Constant>(Arg1));
   }
 
   Instruction *InsertPt;
   if (BO->hasOneUse() && BO->user_back() == Cmp) {
     // If the math is only used by the compare, insert at the compare to keep
     // the condition in the same block as its users. (CGP aggressively sinks
     // compares to help out SDAG.)
     InsertPt = Cmp;
   } else {
if (MathBB != CmpBB) {
       // Check that the insertion doesn't create a value that is live across
       // more than two blocks, so to minimise the increase in register pressure.
       BasicBlock *Dominator = MathDominates ? MathBB : CmpBB;
       BasicBlock *Dominated = MathDominates ? CmpBB : MathBB;
       auto Successors = successors(Dominator);
       if (llvm::find(Successors, Dominated) == Successors.end())
         return false;
     }
 
     InsertPt = MathDominates ? cast<Instruction>(BO) : cast<Instruction>(Cmp);
   }
 
   IRBuilder<> Builder(InsertPt);
   Value *MathOV = Builder.CreateBinaryIntrinsic(IID, Arg0, Arg1);
   Value *Math = Builder.CreateExtractValue(MathOV, 0, "math");
   Value *OV = Builder.CreateExtractValue(MathOV, 1, "ov");
+
+  // Delay the actual removal/deletion of the binop and compare for efficiency.
+  // If we delete those now, we would invalidate the instruction iterator and
+  // trigger dominator tree updates.
   BO->replaceAllUsesWith(Math);
   Cmp->replaceAllUsesWith(OV);
-  BO->eraseFromParent();
-  Cmp->eraseFromParent();
+  RemovedInsts.insert(BO);
+  RemovedInsts.insert(Cmp);
   return true;
 }
 
 /// Match special-case patterns that check for unsigned add overflow.
 static bool matchUAddWithOverflowConstantEdgeCases(CmpInst *Cmp,
                                                    BinaryOperator *&Add) {
   // Add = add A, 1; Cmp = icmp eq A,-1 (overflow if A is max val)
   // Add = add A,-1; Cmp = icmp ne A, 0 (overflow if A is non-zero)
if (match(U, m_Add(m_Specific(A), m_Specific(B)))) {
       return true;
     }
   }
   return false;
 }
 
 /// Try to combine the compare into a call to the llvm.uadd.with.overflow
 /// intrinsic. Return true if any changes were made.
-bool CodeGenPrepare::combineToUAddWithOverflow(CmpInst *Cmp,
-                                               bool &ModifiedDT) {
+bool CodeGenPrepare::combineToUAddWithOverflow(CmpInst *Cmp) {
   Value *A, *B;
   BinaryOperator *Add;
   if (!match(Cmp, m_UAddWithOverflow(m_Value(A), m_Value(B), m_BinOp(Add))))
     if (!matchUAddWithOverflowConstantEdgeCases(Cmp, Add))
       return false;
 
   if (!TLI->shouldFormOverflowOp(ISD::UADDO,
                                  TLI->getValueType(*DL, Add->getType())))
     return false;
 
   // We don't want to move around uses of condition values this late, so we
   // check if it is legal to create the call to the intrinsic in the basic
   // block containing the icmp.
   if (Add->getParent() != Cmp->getParent() && !Add->hasOneUse())
     return false;
 
   if (!replaceMathCmpWithIntrinsic(Add, Cmp, Intrinsic::uadd_with_overflow))
     return false;
 
-  // Reset callers - do not crash by iterating over a dead instruction.
-  ModifiedDT = true;
   return true;
 }
 
-bool CodeGenPrepare::combineToUSubWithOverflow(CmpInst *Cmp,
-                                               bool &ModifiedDT) {
+bool CodeGenPrepare::combineToUSubWithOverflow(CmpInst *Cmp) {
   // We are not expecting non-canonical/degenerate code. Just bail out.
   Value *A = Cmp->getOperand(0), *B = Cmp->getOperand(1);
   if (isa<Constant>(A) && isa<Constant>(B))
     return false;
 
   // Convert (A u> B) to (A u< B) to simplify pattern matching.
   ICmpInst::Predicate Pred = Cmp->getPredicate();
   if (Pred == ICmpInst::ICMP_UGT) {
bool CodeGenPrepare::combineToUSubWithOverflow(CmpInst *Cmp) {
 
   if (!TLI->shouldFormOverflowOp(ISD::USUBO,
                                  TLI->getValueType(*DL, Sub->getType())))
     return false;
 
   if (!replaceMathCmpWithIntrinsic(Sub, Cmp, Intrinsic::usub_with_overflow))
     return false;
 
-  // Reset callers - do not crash by iterating over a dead instruction.
-  ModifiedDT = true;
   return true;
 }
 
 /// Sink the given CmpInst into user blocks to reduce the number of virtual
 /// registers that must be created and coalesced. This is a clear win except on
 /// targets with multiple condition code registers (PowerPC), where it might
 /// lose; some adjustment may be wanted there.
 ///
static bool sinkCmpExpression(CmpInst *Cmp, const TargetLowering &TLI) {
   if (Cmp->use_empty()) {
     Cmp->eraseFromParent();
     MadeChange = true;
   }
 
   return MadeChange;
 }
 
-bool CodeGenPrepare::optimizeCmp(CmpInst *Cmp, bool &ModifiedDT) {
+bool CodeGenPrepare::optimizeCmp(CmpInst *Cmp) {
   if (sinkCmpExpression(Cmp, *TLI))
     return true;
 
-  if (combineToUAddWithOverflow(Cmp, ModifiedDT))
+  if (combineToUAddWithOverflow(Cmp))
     return true;
 
-  if (combineToUSubWithOverflow(Cmp, ModifiedDT))
+  if (combineToUSubWithOverflow(Cmp))
     return true;
 
   return false;
 }
 
 /// Duplicate and sink the given 'and' instruction into user blocks where it is
 /// used in a compare to allow isel to generate better code for targets where
 /// this operation can be combined.
if (isa<ZExtInst>(I) || isa<SExtInst>(I)) {
         bool MadeChange = optimizeExt(I);
         return MadeChange | optimizeExtUses(I);
       }
     }
     return false;
   }
 
   if (auto *Cmp = dyn_cast<CmpInst>(I))
-    if (TLI && optimizeCmp(Cmp, ModifiedDT))
+    if (TLI && optimizeCmp(Cmp))
       return true;
 
   if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
     LI->setMetadata(LLVMContext::MD_invariant_group, nullptr);
     if (TLI) {
       bool Modified = optimizeLoadExt(LI);
       unsigned AS = LI->getPointerAddressSpace();
       Modified |= optimizeMemoryInst(I, I->getOperand(0), LI->getType(), AS);