[CodeGen] Remove redundent instructions generated by combineAddrModes.

[Peter]

Summary

CodeGenPare may optimize memory access modes.
During such optimization, it might create a new instruction representing combined value.
Later, If the optimization failed, the generated value is not removed and remains a dead instruction.

Normally this won't be a problem as dead code will be eliminated later.
However, in this case (Issue 58538), the generated instruction may trigger an infinite loop.
The infinite loop involves sinkCmpExpression, where it tries to optimize the placeholder generated by us.
(See the test case detailed in the issue)

To fix this, we remove the unnecessary placeholder immediately when we abort the optimization.
AddressingModeCombiner will keep track of the placeholder, and remove it if it is an inserted placeholder and has no uses.
This patch fixes https://github.com/llvm/llvm-project/issues/58538, a test is also included.

[skatkov]

I'm a bit confused. In the description you talk about new instructions introduced in AddressingModeCombiner::InsertPlaceholders.
The patch itself does not do anything with then. So the patch deals with the value which is used in combined addressing mode.

Another question, why did you decide to erase this instruction only one place instead of erasing it in all early bail-outs?
Don't you want to add this erasing into destructor of AddressingModeCombiner?

[skatkov]

In parallel, don't you want to update sinkCmpExpression to ignore dead instructions?
Additionally, In the code I see

// If we have already inserted a cmp into this block, use it.
CmpInst *&InsertedCmp = InsertedCmps[UserBB];

why we continue sinking icmp while we have already have on in that BB from the bug?

[Peter]

My apology. I am not an expert in these piece of code, so some places are confusing to me as well. If you have a better way to fix the issue, I am more than happy to follow.

I'm a bit confused. In the description you talk about new instructions introduced in AddressingModeCombiner::InsertPlaceholders.
The patch itself does not do anything with then. So the patch deals with the value which is used in combined addressing mode.

The dead instruction is introduced in findCommon, which returns that instruction as CommonValue.

Another question, why did you decide to erase this instruction only one place instead of erasing it in all early bail-outs?
Don't you want to add this erasing into destructor of AddressingModeCombiner?

I think we can erase such dead instruction on all early bail-outs, but I couldn't find any test cases where leaving them there will cause problems (like hangs we had in the issue).

why we continue sinking icmp while we have already have on in that BB from the bug?

Because AddressingModeCombiner::InsertPlaceholders keeps inserting placeholders (A select instruction) that happens to satisfy sinkCmpExpression's conditions

[Peter]

why we continue sinking icmp while we have already have on in that BB from the bug?

Because AddressingModeCombiner::InsertPlaceholders keeps inserting placeholders (A select instruction) that happens to satisfy sinkCmpExpression's conditions

Another fix that may work is to ask this pass to not optimize dead instructions. For example, add the following:

bool CodeGenPrepare::optimizeInst(Instruction *I, ModifyDT &ModifiedDT) {
...
   if (auto *Cmp = dyn_cast<CmpInst>(I))
-   if (optimizeCmp(Cmp, ModifiedDT))
+   if (Cmp->getNumUses() != 0 && optimizeCmp(Cmp, ModifiedDT))
       return true;

[skatkov]

ok, the algorithm working with combined address is a bit complex, so it seems that more or less safe way (at least as I see) to remove dead instruction in case of bail out would be:

1. Add a destructor to AddressingModeCombiner
2. Remember CommonValue as you did it
3. Erase CommonValue as you did it in eraseCommonValue()

otherwise your fix is very narrow.

While you can restrict other optimization as @Peter wrote, but removing dead introduced instruction makes sense anyway.

Thank you for doing it.

[skatkov]

Additionally, what I worry about is that the function CodeGenPrepare::optimizeMemoryInst itself remove original instruction.

if (Repl->use_empty()) {
  resetIteratorIfInvalidatedWhileCalling(CurInstIterator->getParent(), [&]() {
    RecursivelyDeleteTriviallyDeadInstructions(
        Repl, TLInfo, nullptr,
        [&](Value *V) { removeAllAssertingVHReferences(V); });
  });
}

I guess it will not be able to remove combineValue but it should be checked by full inspection of algorithm or you can use WeakTrackingVH to keep common value.

[Peter]

Use destructor to remove possibly dead CommonValue

[skatkov]

lgtm, please update summary. It does not corresponds to problem and fix.

llvm/lib/CodeGen/CodeGenPrepare.cpp

3661

make it private for a while.

[Peter]

move eraseCommonValueIfDead() as private, add comments for it.

[Peter]

update

[skatkov]

Please consider re-phrase the description to something like:

CodeGenPare may optimize memory access modes.
During such optimization, it might create new instruction representing combined value.
Later, If the optimization failed, the generated value is not removed and remains a dead instruction.

Normally this won't be a problem as dead code will be eliminated later.
However, in this case (Issue 58538), the generated instruction may trigger an infinite loop.
The infinite loop involves sinkCmpExpression, where it tries to optimize the placeholder generated by us.
(See the test case detailed in the issue)

To fix this, we remove the unnecessary placeholder immediately when we abort the optimization.
AddressingModeCombiner will keep track of the placeholder, and remove it if it is an inserted placeholder and has no uses.
This patch fixes https://github.com/llvm/llvm-project/issues/58538, a test is also included.

lgtm.

llvm/lib/CodeGen/CodeGenPrepare.cpp

private:
   Type *CommonType = nullptr;
 
   /// SimplifyQuery for simplifyInstruction utility.
   const SimplifyQuery &SQ;
 
   /// Original Address.
   Value *Original;
 
+  /// Common value among addresses
+  Value *CommonValue = nullptr;
+
 public:
   AddressingModeCombiner(const SimplifyQuery &_SQ, Value *OriginalValue)
       : SQ(_SQ), Original(OriginalValue) {}
 
+  ~AddressingModeCombiner() { eraseCommonValueIfDead(); }
+
   /// Get the combined AddrMode
   const ExtAddrMode &getAddrMode() const { return AddrModes[0]; }
 
   /// Add a new AddrMode if it's compatible with the AddrModes we already
   /// have.
   /// \return True iff we succeeded in doing so.
   bool addNewAddrMode(ExtAddrMode &NewAddrMode) {
     // Take note of if we have any non-trivial AddrModes, as we need to detect
bool combineAddrModes() {
 
     // Build a map between <original value, basic block where we saw it> to
     // value of base register.
     // Bail out if there is no common type.
     FoldAddrToValueMapping Map;
     if (!initializeMap(Map))
       return false;
 
-    Value *CommonValue = findCommon(Map);
+    CommonValue = findCommon(Map);
     if (CommonValue)
       AddrModes[0].SetCombinedField(DifferentField, CommonValue, AddrModes);
     return CommonValue != nullptr;
   }
 
 private:
+  /// `CommonValue` may be a placeholder inserted by us. 
+  /// If the placeholder is not used, we should remove this dead instruction.
+  void eraseCommonValueIfDead() {
+    if (CommonValue && CommonValue->getNumUses() == 0)
+      if (Instruction *CommonInst = dyn_cast<Instruction>(CommonValue))
+        CommonInst->eraseFromParent();
+  }
+
   /// Initialize Map with anchor values. For address seen
   /// we set the value of different field saw in this address.
   /// At the same time we find a common type for different field we will
   /// use to create new Phi/Select nodes. Keep it in CommonType field.
   /// Return false if there is no common type found.
   bool initializeMap(FoldAddrToValueMapping &Map) {
     // Keep track of keys where the value is null. We will need to replace it
     // with constant null when we know the common type.
if (SunkAddr) {
     // the original IR value was tossed in favor of a constant back when
     // the AddrMode was created we need to bail out gracefully if widths
     // do not match instead of extending it.
     //
     // (See below for code to add the scale.)
     if (AddrMode.Scale) {
       Type *ScaledRegTy = AddrMode.ScaledReg->getType();
       if (cast<IntegerType>(IntPtrTy)->getBitWidth() >
-          cast<IntegerType>(ScaledRegTy)->getBitWidth())
+          cast<IntegerType>(ScaledRegTy)->getBitWidth()) {
         return Modified;
       }
+    }
 
     if (AddrMode.BaseGV) {
       if (ResultPtr)
         return Modified;
 
       ResultPtr = AddrMode.BaseGV;
     }
 

llvm/test/CodeGen/X86/pr58538.ll

+; RUN: opt -codegenprepare -mtriple=x86_64 %s -S -o - | FileCheck %s
+; RUN: opt -codegenprepare -mtriple=i386 %s -S -o - | FileCheck %s
+
+define i32 @f(i32 %0) {
+; CHECK-LABEL: @f
+; CHECK: BB:
+; CHECK:   %P0 = alloca i32, i32 8, align 4
+; CHECK:   %P1 = getelementptr i32, ptr %P0, i32 1
+; CHECK:   %1 = icmp eq i32 %0, 0
+; CHECK:   %P2 = getelementptr i1, ptr %P1, i1 %1
+; CHECK:   %2 = icmp eq i32 %0, 0
+; CHECK:   %P3 = select i1 %2, ptr %P1, ptr %P2
+; CHECK:   %L1 = load i32, ptr %P3, align 4
+; CHECK:   ret i32 %L1
+BB:
+  %P0 = alloca i32, i32 8
+  %P1 = getelementptr i32, ptr %P0, i32 1
+  %B0 = icmp eq i32 %0, 0
+  br label %BB1
+
+BB1:                                              ; preds = %BB1, %BB
+  %P2 = getelementptr i1, ptr %P1, i1 %B0
+  br i1 false, label %BB1, label %BB2
+
+BB2:                                              ; preds = %BB1
+  %P3 = select i1 %B0, ptr %P1, ptr %P2
+  %L1 = load i32, ptr %P3
+  ret i32 %L1
+}