[SCCP] Use conditional info with AND/OR branch conditions.

[fhahn]

Summary

Currently SCCP does not combine the information of conditions joined by
AND in the true branch or OR in the false branch.

For branches on AND, 2 copies will be inserted for the true branch, with
one being the operand of the other as in the code below. We can combine
the information using intersection. Note that for the OR case, the
copies are inserted in the false branch, where using intersection is
safe as well.

define void @foo(i32 %a) {
entry:
  %lt = icmp ult i32 %a, 100
  %gt = icmp ugt i32 %a, 20
  %and = and i1 %lt, %gt
; Has predicate info
; branch predicate info { TrueEdge: 1 Comparison:  %lt = icmp ult i32 %a, 100 Edge: [label %entry,label %true] }
  %a.0 = call i32 @llvm.ssa.copy.140247425954880(i32 %a)
; Has predicate info
; branch predicate info { TrueEdge: 1 Comparison:  %gt = icmp ugt i32 %a, 20 Edge: [label %entry,label %false] }
  %a.1 = call i32 @llvm.ssa.copy.140247425954880(i32 %a.0)
  br i1 %and, label %true, label %false

true:                                             ; preds = %entry
  call void @use(i32 %a.1)
  %true.1 = icmp ne i32 %a.1, 20
  call void @use.i1(i1 %true.1)
  ret void

false:                                            ; preds = %entry
  call void @use(i32 %a.1)
  ret void
}

[fhahn]

With this change, the example in http://lists.llvm.org/pipermail/llvm-dev/2020-April/140641.html is optimized as expected.

[efriedma]

llvm/lib/Transforms/Scalar/SCCP.cpp

1262

I don't understand what OriginalVal is when it isn't equal to CopyOf. The example in the commit message isn't helpful here; it looks like the predicate info refers to the same value as the ssa copy.

[fhahn]

llvm/lib/Transforms/Scalar/SCCP.cpp

1262

We need 1 more renaming step to run into the issue:

entry:
  %lt = icmp ult i32 %a, 100
  %a.0 = call i32 @llvm.ssa.copy.140247425954880(i32 %a) ; OriginalOp = %a
  br i1 %lt, label %true.1, label %false

true: 
   %gt = icmp ugt i32 %a.0, 20
   %a.1 = call i32 @llvm.ssa.copy.140247425954880(i32 %a.0) ; OriginalOp = %a
   br i1 %gt, label %true.2, %label %false

The OriginalOp for the info attached to %a.1 refers to %a as OriginalOp, but the actual use in %gt has been renamed due to the first copy. For most cases, using the operand is fine (as we did before), but for ANDs the operand of the second copy will be the first copy, which is not part of the Cmp instruction.

Ideally we would have OriginalOp (or another member) refer to the name of the value in the condition. Otherwise we have to walk backwards here and try to find the right value to use. I tried just checking if we have 2 chained ssa_copies, but there were some cases where this failed. I will take a closer look to check whether this should be handled here or directly in PredicateInfo. It only means that we miss out on some cases, but are able to still cover more cases as before.

(I also realized that I copied a wrong version of the example in the description. I will update it shortly.

[efriedma]

llvm/lib/Transforms/Scalar/SCCP.cpp

1262

I'm afraid this sort of "defensive" check is hiding some real bug. I'd rather try to figure out some more consistent way to figure out the necessary information. If we're still missing some cases, that indicates to me the algorithm for converting the information in PredicateBranches into a ConstantRange is still shaky. And it's not obvious to me that the shakiness only manifests in the form of a missed optimization.

[fhahn]

Updated on top of D78133.

Unfortunately it seems like this change is not strictly beneficial in some cases and the additional information might destroy some useful information. For example, consider the code below

  %c.ne = icmp ne i32 %x, 0
  %c.slt = icmp slt i32 %x, 255
  %and= and i1 %c.ne, c.slt%
  br i1 %and, label %true, label %false

true:
  %c.ne.2 = icmp eq i32 %x, 0
  call void @use(i1 %c.ne.2)

With the change, we won't be able to simplify %c.ne.2 to false, because we combine the range from %x != 0 with %x < 255, which results in a range %x < 255 and we cannot represent that the range also excludes 0.

It seems like the change is overall neutral on the test-suite, but there are a few cases where fewer constants are replaced unfortunately.

[fhahn]

llvm/lib/Transforms/Scalar/SCCP.cpp

1262

Agreed! I've put up a WIP patch D78133 that updates PredicateInfo to set OriginalOp for branches to refer to the original value that is used in the condition after renaming. With that, the logic can be simplified, but I still need to double-check if that has any impact on NewGVN.

[efriedma]

Much cleaner now.

In terms of merging information, hmm, that's a downside. No good ideas off the top of my head; I mean, you could store a vector of constant ranges instead of just one, but that gets complicated fast.

[fhahn]

In D77808#1981709, @efriedma wrote:

Much cleaner now.

In terms of merging information, hmm, that's a downside. No good ideas off the top of my head; I mean, you could store a vector of constant ranges instead of just one, but that gets complicated fast.

yes, I am not sure if we really want to go there. I'll try and see if there are any reasonable alternatives

[fhahn]

In D77808#1984593, @fhahn wrote:

In D77808#1981709, @efriedma wrote:

Much cleaner now.

In terms of merging information, hmm, that's a downside. No good ideas off the top of my head; I mean, you could store a vector of constant ranges instead of just one, but that gets complicated fast.

yes, I am not sure if we really want to go there. I'll try and see if there are any reasonable alternatives

I've updated the patch to not use the information from chained predicates, if the original info is != constant. That gets rid of the regressions and keeps things simple. What do you think?

[fhahn]

Ping :)

Rebased after latest changes. The latest version preserves ranges containing information from !=, eliminating the regressions.

[fhahn]

Rebased and ping :)

[nikic]

llvm/lib/Transforms/Scalar/SCCP.cpp

1309

I'd write this as:

NewCR = NewCR.intersectWith(CopyOfCR);
if (!CopyOfCR.contains(NewCR) &&
    CopyOfCR.getSingleMissingElement() &&
    CopyOf != OriginalVal)
  NewCR = CopyOfCR;

There is no need to discard the intersection if it is smaller than the original range. E.g. if you had information for ne 0 before, then intersecting it with ugt 42 will always be beneficial.

I'm also not clear on why the CopyOf != OriginalVal comparison is there. If we think that inequality information is more valuable, shouldn't that hold regardless of how we arrived at the inequality?

[fhahn]

Simplify code as suggested, remove dedicated CopyOf != OriginalVal check.

[fhahn]

llvm/lib/Transforms/Scalar/SCCP.cpp

1309

Thanks, that's simpler indeed. I think the impact in practice is relatively low, but it is definitely more straight-forward:)

I'm also not clear on why the CopyOf != OriginalVal comparison is there

It was mainly there to guard against specific potential regressions caused by this patch. But it is probably not worth special casing here. I've remove the check.

[nikic]

LGTM modulo some naming.

llvm/lib/Transforms/Scalar/SCCP.cpp

1259

The "or CopyOf" is too much now. (You might want to convert this into an assertion, to make sure there are no more surprises here.)

1287

You already fetched this above under the name of OriginalValState.

I think the naming here got a bit messed up due to the back and forth refactoring. You might want to rename OriginalValState above to CopyOfVal, to avoid confusing with OriginalVal. I'd also s/OriginalVal/OriginalOp to keep with the name from PredicateInfo, and because you're using Val to indicate lattice values rather than Value*s.

[fhahn]

Rebased after updating D78133. Adjust comment/naming.

llvm/lib/Transforms/Scalar/SCCP.cpp

 //===- SCCP.cpp - Sparse Conditional Constant Propagation -----------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
 
       // Everything below relies on the condition being a comparison.
       auto *Cmp = dyn_cast<CmpInst>(PBranch->Condition);
       if (!Cmp) {
         mergeInValue(ValueState[I], I, getValueState(CopyOf));
         return;
       }
 
+      Value *OriginalVal = PBranch->OriginalOp;
       Value *CmpOp0 = Cmp->getOperand(0);
       Value *CmpOp1 = Cmp->getOperand(1);
-      if (CopyOf != CmpOp0 && CopyOf != CmpOp1) {
+
+      // Bail out if neither of the operands matches the OriginalVal or CopyOf.
+      if (CmpOp0 != OriginalVal && CmpOp1 != OriginalVal) {
         mergeInValue(ValueState[I], I, getValueState(CopyOf));
         return;
       }
 
       auto Pred = Cmp->getPredicate();
-      if (CmpOp0 != CopyOf) {
+      if (CmpOp1 == OriginalVal) {
         std::swap(CmpOp0, CmpOp1);
         Pred = Cmp->getSwappedPredicate();
       }
 
       // Wait until CmpOp1 is resolved.
       if (getValueState(CmpOp1).isUnknown()) {
         addAdditionalUser(CmpOp1, I);
         return;
       }
 
+      // The code below relies on PredicateInfo only inserting copies for the
+      // true branch when the branch condition is an AND and only inserting
+      // copies for the false branch when the branch condition is an OR. This
+      // ensures we can intersect the range from the condition with the range of
+      // CopyOf.
       if (!PBranch->TrueEdge)
         Pred = CmpInst::getInversePredicate(Pred);
 
       ValueLatticeElement CondVal = getValueState(CmpOp1);
       ValueLatticeElement &IV = ValueState[I];
-      ValueLatticeElement OriginalVal = getValueState(CopyOf);
-      if (CondVal.isConstantRange() || OriginalVal.isConstantRange()) {
+      ValueLatticeElement CopyOfVal = getValueState(CopyOf);
+      if (CondVal.isConstantRange() || CopyOfVal.isConstantRange()) {
         auto NewCR =
             ConstantRange::getFull(DL.getTypeSizeInBits(CopyOf->getType()));
 
         // Get the range imposed by the condition.
         if (CondVal.isConstantRange())
           NewCR = ConstantRange::makeAllowedICmpRegion(
               Pred, CondVal.getConstantRange());
 
         // Combine range info for the original value with the new range from the
         // condition.
-        auto OriginalCR = OriginalVal.isConstantRange()
-                              ? OriginalVal.getConstantRange()
-                              : ConstantRange::getFull(
-                                    DL.getTypeSizeInBits(CopyOf->getType()));
-        NewCR = NewCR.intersectWith(OriginalCR);
+        auto CopyOfCR = CopyOfVal.isConstantRange()
+                            ? CopyOfVal.getConstantRange()
+        NewCR = NewCR.intersectWith(CopyOfCR);
 
         addAdditionalUser(CmpOp1, I);
         // TODO: Actually filp MayIncludeUndef for the created range to false,
         // once most places in the optimizer respect the branches on
         // undef/poison are UB rule. The reason why the new range cannot be
         // undef is as follows below:
         // The new range is based on a branch condition. That guarantees that
         // neither of the compare operands can be undef in the branch targets,
         // unless we have conditions that are always true/false (e.g. icmp ule
         // i32, %a, i32_max). For the latter overdefined/empty range will be
         // inferred, but the branch will get folded accordingly anyways.
         mergeInValue(
             IV, I,
             ValueLatticeElement::getRange(NewCR, /*MayIncludeUndef=*/true));
         return;
       } else if (Pred == CmpInst::ICMP_EQ && CondVal.isConstant()) {

llvm/test/Transforms/SCCP/conditions-ranges.ll

 define void @f16_conditions_and(i32 %a, i32 %b) {
 ; CHECK-LABEL: @f16_conditions_and(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[LT:%.*]] = icmp ult i32 [[A:%.*]], 100
 ; CHECK-NEXT:    [[GT:%.*]] = icmp ugt i32 [[A]], 20
 ; CHECK-NEXT:    [[BC:%.*]] = and i1 [[LT]], [[GT]]
 ; CHECK-NEXT:    br i1 [[BC]], label [[TRUE:%.*]], label [[FALSE:%.*]]
 ; CHECK:       true:
-; CHECK-NEXT:    [[F_1:%.*]] = icmp eq i32 [[A]], 0
-; CHECK-NEXT:    call void @use(i1 [[F_1]])
-; CHECK-NEXT:    [[F_2:%.*]] = icmp eq i32 [[A]], 20
-; CHECK-NEXT:    call void @use(i1 [[F_2]])
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    call void @use(i1 true)
-; CHECK-NEXT:    [[T_2:%.*]] = icmp ne i32 [[A]], 20
-; CHECK-NEXT:    call void @use(i1 [[T_2]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp eq i32 [[A]], 21
 ; CHECK-NEXT:    call void @use(i1 [[C_1]])
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp ugt i32 [[A]], 21
 ; CHECK-NEXT:    call void @use(i1 [[C_2]])
 ; CHECK-NEXT:    [[C_3:%.*]] = icmp ugt i32 [[A]], 50
 ; CHECK-NEXT:    call void @use(i1 [[C_3]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       false:

 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[GT:%.*]] = icmp uge i32 [[A:%.*]], 100
 ; CHECK-NEXT:    [[LT:%.*]] = icmp ule i32 [[A]], 20
 ; CHECK-NEXT:    [[BC:%.*]] = or i1 [[LT]], [[GT]]
 ; CHECK-NEXT:    br i1 [[BC]], label [[TRUE:%.*]], label [[FALSE:%.*]]
 ; CHECK:       false:
 ; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    call void @use(i1 false)
-; CHECK-NEXT:    [[F_3:%.*]] = icmp ugt i32 [[A]], 100
-; CHECK-NEXT:    call void @use(i1 [[F_3]])
-; CHECK-NEXT:    [[T_1:%.*]] = icmp ult i32 [[A]], 100
-; CHECK-NEXT:    call void @use(i1 [[T_1]])
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp eq i32 [[A]], 21
 ; CHECK-NEXT:    call void @use(i1 [[C_1]])
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp ugt i32 [[A]], 21
 ; CHECK-NEXT:    call void @use(i1 [[C_2]])
 ; CHECK-NEXT:    [[C_3:%.*]] = icmp ugt i32 [[A]], 50
 ; CHECK-NEXT:    call void @use(i1 [[C_3]])
 ; CHECK-NEXT:    ret void

 ; CHECK-NEXT:    br i1 [[TMP133]], label [[BB134:%.*]], label [[BB135]]
 ; CHECK:       bb134:
 ; CHECK-NEXT:    br label [[BB135]]
 ; CHECK:       bb135:
 ; CHECK-NEXT:    [[TMP136]] = phi i32 [ [[TMP123]], [[BB122]] ], [ [[TMP128]], [[BB134]] ]
 ; CHECK-NEXT:    [[BC:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[BC]], label [[BB139:%.*]], label [[BB122]]
 ; CHECK:       bb139:
-; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    [[TMP140:%.*]] = icmp eq i32 [[TMP136]], 0
+; CHECK-NEXT:    call void @use(i1 [[TMP140]])
 ; CHECK-NEXT:    ret void
 ;
 bb11:                                             ; preds = %bb1
   br label %bb122
 
 bb122:                                            ; preds = %bb135, %bb120
   %tmp123 = phi i32 [ 256, %bb11 ], [ %tmp136, %bb135 ]
   %tmp127 = call i64 @get_i64()