[SCEVExpander] Be more conservative about poison flags when reusing instructions

[reames]

Summary

Noticed while reviewing D112389. Unfortunately, I don't have a good test case, just noticed during code review.

The basic problem we have is that we're trying to reuse an instruction which is mapped to some SCEV. Since we can have multiple such instructions (potentially with different flags), this is analogous to our need to drop flags when performing CSE. A trivial implementation would simply drop flags on any instruction we decided to reuse, and that would be correct.

However, we tackle the problem a bit differently. If we can prove that *all* instructions which map to the SCEV could validly have the flags on the instruction, then we can simply reuse I with those flags in place. The proof of all instructions depends on the defining scope notion and how we define what flags are valid on a SCEV to start with.

In practice, this fixes two conceptual problems with the previous code: 1) a binop could have been canonicalized into a form where there was no binop left, or 2) the inbounds GEP case which was simply unhandled.

[reames]

Don't bother to review just yet. In the process of doing a rebase over a landed change, and noticed a bug in the inbounds handling here (swapped conditional).

[nikic]

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

1855

This comment confuses me. We cannot have used the flags on the binop unless they always hold (via poison UB reasoning). The conclusion is still correct in that we simply don't know whether the flags are always valid or not.

However, the problem goes beyond this. Just because you have some OBO and some SCEV with nowrap flags, does not mean that these flags have the same meaning. For example, consider

%a = add %x, 2
%b = add nuw %a, -1

in a context where %b is unused and %x has known range [0,-2]. The SCEV for %b is going to be %x +<nuw> 1 after folding the adds together and using range-based flag strengthening. However, the add nuw %a, -1 is clearly going to unsigned wrap for all values of %x other than -2. The problem here is that while both the IR instruction and the SCEV have the nuw flag, they also have different operands. One is %a - 1, the other is %x + 1.

The "proper" way to determine that the wrap flags really hold is to do the ext(x + y) == ext(x) + ext(y) dance, but that's really expensive and I'm not sure it's desirable to created these kinds of expression in the expander (especially as they have side-effects on nowrap flags).

[reames]

Realized after some further thought, that the entire approach here is potentially unsound.

Counter example:
%x = add nsw nuw %a, %b
call maythrow()
%y = mul nuw 32 %x, 1

Both the current code and my proposed fix would use the flags inferred from %x, to allow reuse of ^y. In this particular case, that happens to be a valid result, but the reasoning is highly suspect. The basic problem is that the flags on the SCEV may apply to a different operation type than the instruction. Mapping e.g. mul to add or vice versa is not obviously correct.

I'm going to give this one a bit more thought to see if there's a better approach.

Edit: I'd missed Nikita's comment, this basically just says the same thing less well explained than his.

[reames]

Abandoning in favor of https://reviews.llvm.org/D112734

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

Value *SCEVExpander::expandCodeForImpl(const SCEV *SH, Type *Ty, bool Root) {
   if (Ty) {
     assert(SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(SH->getType()) &&
            "non-trivial casts should be done with the SCEVs directly!");
     V = InsertNoopCastOfTo(V, Ty);
   }
   return V;
 }
 
-/// Check whether value has nuw/nsw/exact set but SCEV does not.
-/// TODO: In reality it is better to check the poison recursively
-/// but this is better than nothing.
-static bool SCEVLostPoisonFlags(const SCEV *S, const Instruction *I) {
+/// Return true if we can reuse instruction 'I' for all users of 'S' without
+/// introducing uses of 'I' which propagate poison in more cases.
+static bool canReuseInstructionForAllUsers(const SCEV *S,
+                                           const Instruction *I) {
   if (isa<OverflowingBinaryOperator>(I)) {
+    if (!I->hasNoSignedWrap() && !I->hasNoUnsignedWrap())
+      // 'I' never introduces new poison
+      return true;
     if (auto *NS = dyn_cast<SCEVNAryExpr>(S)) {
+      // We have a SCEV with flags we can check, are the instructions
+      // flags strictly weaker than the SCEVs?
       if (I->hasNoSignedWrap() && !NS->hasNoSignedWrap())
-        return true;
+        return false;
       if (I->hasNoUnsignedWrap() && !NS->hasNoUnsignedWrap())
-        return true;
+        return false;
     }
+    // In general, we may have used flags to optimize a binop into an
+    // alternate form.  Thus, we must conclude that S conceptually has
+    // some unknown set of flags and thus that I must contradict them.
+    return false;
   } else if (isa<PossiblyExactOperator>(I) && I->isExact())
-    return true;
     return false;
+  else if (const auto *GEP = dyn_cast<GEPOperator>(I)) {
+    if (!GEP->isInBounds())
+      return false;
+    // TODO: SCEV models as an add in most cases, we could duplicate
+    // logic from above for this.
+    return true;
+  }
+
+  // We have enumerated the instructions which have poison generating flags
+  // while also being SCEVable.  Thus, if we get here, we can reuse.
+  return true;
 }
 
 ScalarEvolution::ValueOffsetPair
 SCEVExpander::FindValueInExprValueMap(const SCEV *S,
                                       const Instruction *InsertPt) {
   auto *Set = SE.getSCEVValues(S);
   // If the expansion is not in CanonicalMode, and the SCEV contains any
   // sub scAddRecExpr type SCEV, it is required to expand the SCEV literally.
if (S->getSCEVType() != scConstant && Set) {
         if (!EntInst)
           continue;
 
         assert(EntInst->getFunction() == InsertPt->getFunction());
         if (S->getType() == V->getType() &&
             SE.DT.dominates(EntInst, InsertPt) &&
             (SE.LI.getLoopFor(EntInst->getParent()) == nullptr ||
              SE.LI.getLoopFor(EntInst->getParent())->contains(InsertPt)) &&
-            !SCEVLostPoisonFlags(S, EntInst))
+            canReuseInstructionForAllUsers(S, EntInst))
           return {V, Offset};
       }
     }
   }
   return {nullptr, nullptr};
 }
 
 // The expansion of SCEV will either reuse a previous Value in ExprValueMap,

llvm/test/CodeGen/PowerPC/common-chain.ll

 ; CHECK-NEXT:    mr r12, r10
 ; CHECK-NEXT:    cmpdi r6, 1
 ; CHECK-NEXT:    iselgt r7, r6, r7
 ; CHECK-NEXT:    addi r8, r7, -1
 ; CHECK-NEXT:    clrldi r6, r7, 63
 ; CHECK-NEXT:    cmpldi r8, 3
 ; CHECK-NEXT:    blt cr0, .LBB7_4
 ; CHECK-NEXT:  # %bb.2: # %for.body.preheader.new
+; CHECK-NEXT:    ld r17, -176(r1) # 8-byte Folded Reload
+; CHECK-NEXT:    ld r18, -168(r1) # 8-byte Folded Reload
+; CHECK-NEXT:    ld r19, -160(r1) # 8-byte Folded Reload
+; CHECK-NEXT:    sldi r11, r12, 1
+; CHECK-NEXT:    add r0, r12, r11
 ; CHECK-NEXT:    rldicl r7, r7, 62, 2
 ; CHECK-NEXT:    sldi r10, r12, 2
-; CHECK-NEXT:    ld r2, -168(r1) # 8-byte Folded Reload
-; CHECK-NEXT:    ld r31, -160(r1) # 8-byte Folded Reload
-; CHECK-NEXT:    std r7, -184(r1) # 8-byte Folded Spill
-; CHECK-NEXT:    mr r7, r4
-; CHECK-NEXT:    ld r4, -176(r1) # 8-byte Folded Reload
-; CHECK-NEXT:    add r8, r4, r10
-; CHECK-NEXT:    sldi r8, r8, 3
-; CHECK-NEXT:    add r9, r5, r8
-; CHECK-NEXT:    add r8, r2, r10
-; CHECK-NEXT:    add r10, r31, r10
-; CHECK-NEXT:    sldi r10, r10, 3
+; CHECK-NEXT:    rldicl r7, r7, 2, 1
+; CHECK-NEXT:    add r29, r17, r0
+; CHECK-NEXT:    add r28, r18, r0
+; CHECK-NEXT:    add r0, r19, r0
+; CHECK-NEXT:    addi r7, r7, -4
+; CHECK-NEXT:    add r8, r17, r10
+; CHECK-NEXT:    sldi r31, r0, 3
+; CHECK-NEXT:    add r0, r17, r11
 ; CHECK-NEXT:    sldi r8, r8, 3
-; CHECK-NEXT:    add r30, r5, r10
-; CHECK-NEXT:    add r29, r7, r10
-; CHECK-NEXT:    add r28, r3, r10
-; CHECK-NEXT:    sldi r10, r12, 1
-; CHECK-NEXT:    add r8, r5, r8
-; CHECK-NEXT:    add r11, r12, r10
-; CHECK-NEXT:    add r0, r4, r11
-; CHECK-NEXT:    sldi r0, r0, 3
-; CHECK-NEXT:    add r27, r5, r0
-; CHECK-NEXT:    add r0, r2, r11
-; CHECK-NEXT:    add r11, r31, r11
-; CHECK-NEXT:    sldi r11, r11, 3
+; CHECK-NEXT:    rldicl r7, r7, 62, 2
+; CHECK-NEXT:    sldi r29, r29, 3
+; CHECK-NEXT:    sldi r28, r28, 3
 ; CHECK-NEXT:    sldi r0, r0, 3
-; CHECK-NEXT:    add r25, r5, r11
-; CHECK-NEXT:    add r24, r7, r11
-; CHECK-NEXT:    add r23, r3, r11
-; CHECK-NEXT:    add r11, r4, r10
+; CHECK-NEXT:    addi r7, r7, 1
+; CHECK-NEXT:    add r9, r5, r8
+; CHECK-NEXT:    add r8, r18, r10
+; CHECK-NEXT:    add r10, r19, r10
+; CHECK-NEXT:    add r29, r5, r29
+; CHECK-NEXT:    add r28, r5, r28
+; CHECK-NEXT:    add r27, r5, r31
 ; CHECK-NEXT:    add r26, r5, r0
-; CHECK-NEXT:    sldi r11, r11, 3
-; CHECK-NEXT:    add r22, r5, r11
-; CHECK-NEXT:    add r11, r2, r10
-; CHECK-NEXT:    add r10, r31, r10
+; CHECK-NEXT:    add r0, r18, r11
+; CHECK-NEXT:    add r11, r19, r11
+; CHECK-NEXT:    sldi r8, r8, 3
 ; CHECK-NEXT:    sldi r10, r10, 3
+; CHECK-NEXT:    mtctr r7
+; CHECK-NEXT:    sldi r7, r12, 5
+; CHECK-NEXT:    sldi r0, r0, 3
 ; CHECK-NEXT:    sldi r11, r11, 3
-; CHECK-NEXT:    add r20, r5, r10
-; CHECK-NEXT:    add r19, r7, r10
-; CHECK-NEXT:    add r18, r3, r10
-; CHECK-NEXT:    add r10, r12, r4
-; CHECK-NEXT:    add r21, r5, r11
-; CHECK-NEXT:    sldi r11, r2, 3
-; CHECK-NEXT:    sldi r10, r10, 3
-; CHECK-NEXT:    add r17, r5, r10
-; CHECK-NEXT:    add r10, r12, r2
-; CHECK-NEXT:    sldi r10, r10, 3
-; CHECK-NEXT:    add r16, r5, r10
-; CHECK-NEXT:    add r10, r12, r31
-; CHECK-NEXT:    sldi r31, r31, 3
-; CHECK-NEXT:    sub r0, r11, r31
-; CHECK-NEXT:    sldi r11, r4, 3
-; CHECK-NEXT:    mr r4, r7
-; CHECK-NEXT:    ld r7, -184(r1) # 8-byte Folded Reload
-; CHECK-NEXT:    sldi r10, r10, 3
-; CHECK-NEXT:    add r15, r5, r10
-; CHECK-NEXT:    add r14, r3, r10
-; CHECK-NEXT:    sub r31, r11, r31
+; CHECK-NEXT:    add r8, r5, r8
+; CHECK-NEXT:    add r30, r5, r10
+; CHECK-NEXT:    add r16, r3, r10
 ; CHECK-NEXT:    add r2, r4, r10
-; CHECK-NEXT:    li r11, 0
 ; CHECK-NEXT:    mr r10, r12
-; CHECK-NEXT:    rldicl r7, r7, 2, 1
-; CHECK-NEXT:    addi r7, r7, -4
-; CHECK-NEXT:    rldicl r7, r7, 62, 2
-; CHECK-NEXT:    addi r7, r7, 1
-; CHECK-NEXT:    mtctr r7
-; CHECK-NEXT:    sldi r7, r12, 5
+; CHECK-NEXT:    add r25, r5, r0
+; CHECK-NEXT:    add r0, r12, r17
+; CHECK-NEXT:    add r24, r5, r11
+; CHECK-NEXT:    add r14, r4, r11
+; CHECK-NEXT:    sldi r0, r0, 3
+; CHECK-NEXT:    add r23, r5, r0
+; CHECK-NEXT:    add r0, r12, r18
+; CHECK-NEXT:    sldi r0, r0, 3
+; CHECK-NEXT:    add r22, r5, r0
+; CHECK-NEXT:    add r0, r12, r19
+; CHECK-NEXT:    sldi r19, r19, 3
+; CHECK-NEXT:    sldi r15, r0, 3
+; CHECK-NEXT:    sldi r0, r18, 3
+; CHECK-NEXT:    sldi r18, r17, 3
+; CHECK-NEXT:    add r17, r3, r31
+; CHECK-NEXT:    add r31, r4, r31
+; CHECK-NEXT:    add r21, r5, r15
+; CHECK-NEXT:    add r20, r3, r15
+; CHECK-NEXT:    sub r0, r0, r19
+; CHECK-NEXT:    sub r19, r18, r19
+; CHECK-NEXT:    add r18, r3, r11
+; CHECK-NEXT:    add r15, r4, r15
+; CHECK-NEXT:    li r11, 0
 ; CHECK-NEXT:    .p2align 4
 ; CHECK-NEXT:  .LBB7_3: # %for.body
 ; CHECK-NEXT:    #
-; CHECK-NEXT:    lfd f0, 0(r14)
-; CHECK-NEXT:    lfd f1, 0(r2)
+; CHECK-NEXT:    lfd f0, 0(r20)
+; CHECK-NEXT:    lfd f1, 0(r15)
 ; CHECK-NEXT:    add r10, r10, r12
 ; CHECK-NEXT:    add r10, r10, r12
 ; CHECK-NEXT:    xsmuldp f0, f0, f1
-; CHECK-NEXT:    lfd f1, 0(r15)
+; CHECK-NEXT:    lfd f1, 0(r21)
 ; CHECK-NEXT:    add r10, r10, r12
 ; CHECK-NEXT:    add r10, r10, r12
 ; CHECK-NEXT:    xsadddp f0, f1, f0
-; CHECK-NEXT:    stfd f0, 0(r15)
-; CHECK-NEXT:    add r15, r15, r7
-; CHECK-NEXT:    lfdx f0, r14, r0
-; CHECK-NEXT:    lfdx f1, r2, r0
+; CHECK-NEXT:    stfd f0, 0(r21)
+; CHECK-NEXT:    add r21, r21, r7
+; CHECK-NEXT:    lfdx f0, r20, r0
+; CHECK-NEXT:    lfdx f1, r15, r0
 ; CHECK-NEXT:    xsmuldp f0, f0, f1
-; CHECK-NEXT:    lfdx f1, r16, r11
+; CHECK-NEXT:    lfdx f1, r22, r11
 ; CHECK-NEXT:    xsadddp f0, f1, f0
-; CHECK-NEXT:    stfdx f0, r16, r11
-; CHECK-NEXT:    lfdx f0, r14, r31
-; CHECK-NEXT:    lfdx f1, r2, r31
-; CHECK-NEXT:    add r14, r14, r7
-; CHECK-NEXT:    add r2, r2, r7
+; CHECK-NEXT:    stfdx f0, r22, r11
+; CHECK-NEXT:    lfdx f0, r20, r19
+; CHECK-NEXT:    lfdx f1, r15, r19
+; CHECK-NEXT:    add r20, r20, r7
+; CHECK-NEXT:    add r15, r15, r7
 ; CHECK-NEXT:    xsmuldp f0, f0, f1
-; CHECK-NEXT:    lfdx f1, r17, r11
+; CHECK-NEXT:    lfdx f1, r23, r11
 ; CHECK-NEXT:    xsadddp f0, f1, f0
-; CHECK-NEXT:    stfdx f0, r17, r11
+; CHECK-NEXT:    stfdx f0, r23, r11
 ; CHECK-NEXT:    lfd f0, 0(r18)
-; CHECK-NEXT:    lfd f1, 0(r19)
+; CHECK-NEXT:    lfd f1, 0(r14)
 ; CHECK-NEXT:    xsmuldp f0, f0, f1
-; CHECK-NEXT:    lfdx f1, r20, r11
+; CHECK-NEXT:    lfdx f1, r24, r11
 ; CHECK-NEXT:    xsadddp f0, f1, f0
-; CHECK-NEXT:    stfdx f0, r20, r11
+; CHECK-NEXT:    stfdx f0, r24, r11
 ; CHECK-NEXT:    lfdx f0, r18, r0
-; CHECK-NEXT:    lfdx f1, r19, r0
-; CHECK-NEXT:    xsmuldp f0, f0, f1
-; CHECK-NEXT:    lfdx f1, r21, r11
-; CHECK-NEXT:    xsadddp f0, f1, f0
-; CHECK-NEXT:    stfdx f0, r21, r11
-; CHECK-NEXT:    lfdx f0, r18, r31
-; CHECK-NEXT:    lfdx f1, r19, r31
-; CHECK-NEXT:    add r18, r18, r7
-; CHECK-NEXT:    add r19, r19, r7
-; CHECK-NEXT:    xsmuldp f0, f0, f1
-; CHECK-NEXT:    lfdx f1, r22, r11
-; CHECK-NEXT:    xsadddp f0, f1, f0
-; CHECK-NEXT:    stfdx f0, r22, r11
-; CHECK-NEXT:    lfd f0, 0(r23)
-; CHECK-NEXT:    lfd f1, 0(r24)
+; CHECK-NEXT:    lfdx f1, r14, r0
 ; CHECK-NEXT:    xsmuldp f0, f0, f1
 ; CHECK-NEXT:    lfdx f1, r25, r11
 ; CHECK-NEXT:    xsadddp f0, f1, f0
 ; CHECK-NEXT:    stfdx f0, r25, r11
-; CHECK-NEXT:    lfdx f0, r23, r0
-; CHECK-NEXT:    lfdx f1, r24, r0
+; CHECK-NEXT:    lfdx f0, r18, r19
+; CHECK-NEXT:    lfdx f1, r14, r19
+; CHECK-NEXT:    add r18, r18, r7
+; CHECK-NEXT:    add r14, r14, r7
 ; CHECK-NEXT:    xsmuldp f0, f0, f1
 ; CHECK-NEXT:    lfdx f1, r26, r11
 ; CHECK-NEXT:    xsadddp f0, f1, f0
 ; CHECK-NEXT:    stfdx f0, r26, r11
-; CHECK-NEXT:    lfdx f0, r23, r31
-; CHECK-NEXT:    lfdx f1, r24, r31
-; CHECK-NEXT:    add r23, r23, r7
-; CHECK-NEXT:    add r24, r24, r7
+; CHECK-NEXT:    lfd f0, 0(r17)
+; CHECK-NEXT:    lfd f1, 0(r31)
 ; CHECK-NEXT:    xsmuldp f0, f0, f1
 ; CHECK-NEXT:    lfdx f1, r27, r11
 ; CHECK-NEXT:    xsadddp f0, f1, f0
 ; CHECK-NEXT:    stfdx f0, r27, r11
-; CHECK-NEXT:    lfd f0, 0(r28)
-; CHECK-NEXT:    lfd f1, 0(r29)
+; CHECK-NEXT:    lfdx f0, r17, r0
+; CHECK-NEXT:    lfdx f1, r31, r0
+; CHECK-NEXT:    xsmuldp f0, f0, f1
+; CHECK-NEXT:    lfdx f1, r28, r11
+; CHECK-NEXT:    xsadddp f0, f1, f0
+; CHECK-NEXT:    stfdx f0, r28, r11
+; CHECK-NEXT:    lfdx f0, r17, r19
+; CHECK-NEXT:    lfdx f1, r31, r19
+; CHECK-NEXT:    add r17, r17, r7
+; CHECK-NEXT:    add r31, r31, r7
+; CHECK-NEXT:    xsmuldp f0, f0, f1
+; CHECK-NEXT:    lfdx f1, r29, r11
+; CHECK-NEXT:    xsadddp f0, f1, f0
+; CHECK-NEXT:    stfdx f0, r29, r11
+; CHECK-NEXT:    lfd f0, 0(r16)
+; CHECK-NEXT:    lfd f1, 0(r2)
 ; CHECK-NEXT:    xsmuldp f0, f0, f1
 ; CHECK-NEXT:    lfdx f1, r30, r11
 ; CHECK-NEXT:    xsadddp f0, f1, f0
 ; CHECK-NEXT:    stfdx f0, r30, r11
-; CHECK-NEXT:    lfdx f0, r28, r0
-; CHECK-NEXT:    lfdx f1, r29, r0
+; CHECK-NEXT:    lfdx f0, r16, r0
+; CHECK-NEXT:    lfdx f1, r2, r0
 ; CHECK-NEXT:    xsmuldp f0, f0, f1
 ; CHECK-NEXT:    lfdx f1, r8, r11
 ; CHECK-NEXT:    xsadddp f0, f1, f0
 ; CHECK-NEXT:    stfdx f0, r8, r11
-; CHECK-NEXT:    lfdx f0, r28, r31
-; CHECK-NEXT:    lfdx f1, r29, r31
-; CHECK-NEXT:    add r28, r28, r7
-; CHECK-NEXT:    add r29, r29, r7
+; CHECK-NEXT:    lfdx f0, r16, r19
+; CHECK-NEXT:    lfdx f1, r2, r19
+; CHECK-NEXT:    add r16, r16, r7
+; CHECK-NEXT:    add r2, r2, r7
 ; CHECK-NEXT:    xsmuldp f0, f0, f1
 ; CHECK-NEXT:    lfdx f1, r9, r11
 ; CHECK-NEXT:    xsadddp f0, f1, f0
 ; CHECK-NEXT:    stfdx f0, r9, r11
 ; CHECK-NEXT:    add r11, r11, r7
 ; CHECK-NEXT:    bdnz .LBB7_3
 ; CHECK-NEXT:  .LBB7_4: # %for.cond.cleanup.loopexit.unr-lcssa
 ; CHECK-NEXT:    cmpldi r6, 0