[SCCP] Use range imposed by condition as upper bound for widening.

[fhahn]

Summary

In some cases we can do better than going to overdefined when widening.
The range imposed by a condition for example provides an upper bound on
the range of a value. Instead of widening to overdefined we can widen to
that range.

We have to ensure that the upper bound contains the merge result,
otherwise the merge step would not be monotone any longer.

This improves the number of instructions removed for some programs

Tests: 237
Same hash: 219 (filtered out)
Remaining: 18
Metric: sccp.IPNumInstRemoved

Program base p1 diff
test-suite...ks/Prolangs-C/agrep/agrep.test 40.00 57.00 42.5%
test-suite...cations/hexxagon/hexxagon.test 30.00 36.00 20.0%
test-suite...langs-C/football/football.test 85.00 96.00 12.9%
test-suite...rks/FreeBench/pifft/pifft.test 26.00 28.00 7.7%
test-suite...CFP2000/188.ammp/188.ammp.test 67.00 71.00 6.0%
test-suite...000/197.parser/197.parser.test 59.00 61.00 3.4%
test-suite.../CINT2000/254.gap/254.gap.test 158.00 162.00 2.5%
test-suite...pplications/treecc/treecc.test 66.00 67.00 1.5%
test-suite...TimberWolfMC/timberwolfmc.test 67.00 68.00 1.5%
test-suite...CFP2000/177.mesa/177.mesa.test 202.00 204.00 1.0%
test-suite...lications/ClamAV/clamscan.test 902.00 910.00 0.9%
test-suite...6/482.sphinx3/482.sphinx3.test 137.00 138.00 0.7%
test-suite.../CINT2000/176.gcc/176.gcc.test 1118.00 1123.00 0.4%
test-suite.../CINT2006/403.gcc/403.gcc.test 3831.00 3847.00 0.4%
test-suite.../Benchmarks/Bullet/bullet.test 320.00 321.00 0.3%
test-suite...000/255.vortex/255.vortex.test 3805.00 3809.00 0.1%
test-suite...:: External/Povray/povray.test 1537.00 1538.00 0.1%
test-suite...006/453.povray/453.povray.test 1772.00 1773.00 0.1%

[fhahn]

Strip invalid test changes.

[fhahn]

rebased

[fhahn]

After extensive discussions, it seems like the alternative approach D79036 is slightly beneficial in terms of compile time. Abandoning the patch for now.

llvm/include/llvm/Analysis/ValueLattice.h

public:
   struct MergeOptions {
     /// The merge value may include undef.
     bool MayIncludeUndef;
 
     /// Handle repeatedly extending a range by going to overdefined after a
     /// number of steps.
     bool CheckWiden;
 
+    /// Provides a known upper bound for the merge result. Use this range
+    /// instead of going to overdefined for widening, if WidenCR contains the
+    /// merge result.
+    ConstantRange WidenCR;
+
     MergeOptions() : MergeOptions(false, false) {}
 
     MergeOptions(bool MayIncludeUndef, bool CheckWiden)
-        : MayIncludeUndef(MayIncludeUndef), CheckWiden(CheckWiden) {}
+        : MayIncludeUndef(MayIncludeUndef), CheckWiden(CheckWiden),
+          WidenCR(1, true) {}
 
     MergeOptions &setMayIncludeUndef(bool V = true) {
       MayIncludeUndef = V;
       return *this;
     }
 
     MergeOptions &setCheckWiden(bool V = true) {
       CheckWiden = V;
       return *this;
     }
+
+    MergeOptions &setWidenCR(ConstantRange CR) {
+      WidenCR = CR;
+      return *this;
+    }
   };
 
   // ConstVal and Range are initialized on-demand.
   ValueLatticeElement() : Tag(unknown) {}
 
   ~ValueLatticeElement() { destroy(); }
 
   ValueLatticeElement(const ValueLatticeElement &Other) : Tag(Other.Tag) {
bool markConstantRange(ConstantRange NewR,
     if (isConstantRange()) {
       if (NewR.isEmptySet())
         return markOverdefined();
 
       Tag = NewTag;
       if (getConstantRange() == NewR)
         return Tag != OldTag;
 
-      // Simple form of widening. If a range is extended multiple times, go to
-      // overdefined.
-      if (Opts.CheckWiden && ++NumRangeExtensions == 1)
+      // Simple form of widening. If a range is extended multiple times, use the
+      // provided WidenCR upper bound if it contains NewR or overdefined
+      // otherwise.
+      if (Opts.CheckWiden && ++NumRangeExtensions >= 1) {
+        // Make sure WidenCR is only used if it contains the merge result.
+        if (!Opts.WidenCR.isFullSet() &&
+            (NewR == Opts.WidenCR || Opts.WidenCR.contains(NewR))) {
+          assert(NewR.contains(getConstantRange()));
+          bool Changed = Opts.WidenCR != getConstantRange();
+          Range = std::move(Opts.WidenCR);
+          NumRangeExtensions = 1;
+          return Changed || Tag != OldTag;
+        }
         return markOverdefined();
+      }
 
       assert(NewR.contains(getConstantRange()) &&
              "Existing range must be a subset of NewR");
       Range = std::move(NewR);
       return true;
     }
 
     assert(isUnknown() || isUndef());

llvm/lib/Transforms/Scalar/SCCP.cpp

if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
 
       if (!PBranch->TrueEdge)
         Pred = CmpInst::getInversePredicate(Pred);
 
       ValueLatticeElement CondVal = getValueState(CmpOp1);
       ValueLatticeElement &IV = ValueState[&CB];
       ValueLatticeElement OriginalVal = getValueState(CopyOf);
       if (CondVal.isConstantRange() || OriginalVal.isConstantRange()) {
-        auto NewCR =
+        auto ImposedCR =
             ConstantRange::getFull(DL.getTypeSizeInBits(CopyOf->getType()));
 
         // Get the range imposed by the condition.
         if (CondVal.isConstantRange())
-          NewCR = ConstantRange::makeAllowedICmpRegion(
+          ImposedCR = 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 NewCR = ImposedCR.intersectWith(OriginalCR);
 
         addAdditionalUser(CmpOp1, &CB);
         // 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, &CB,
-            ValueLatticeElement::getRange(NewCR, /*MayIncludeUndef=*/true));
+            ValueLatticeElement::getRange(NewCR, /*MayIncludeUndef=*/true),
+            ValueLatticeElement::MergeOptions().setCheckWiden().setWidenCR(
+                ImposedCR));
         return;
       } else if (Pred == CmpInst::ICMP_EQ && CondVal.isConstant()) {
         // For non-integer values or integer constant expressions, only
         // propagate equal constants.
         addAdditionalUser(CmpOp1, &CB);
         mergeInValue(IV, &CB, CondVal);
         return;
       }

llvm/test/Transforms/SCCP/widening.ll

 ; IPSCCP-LABEL: @loop_with_header_1(
 ; IPSCCP-NEXT:  entry:
 ; IPSCCP-NEXT:    br label [[LOOP_HEADER:%.*]]
 ; IPSCCP:       loop.header:
 ; IPSCCP-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP_BODY:%.*]] ]
 ; IPSCCP-NEXT:    [[C_1:%.*]] = icmp slt i32 [[IV]], 2
 ; IPSCCP-NEXT:    br i1 [[C_1]], label [[LOOP_BODY]], label [[EXIT:%.*]]
 ; IPSCCP:       loop.body:
-; IPSCCP-NEXT:    [[T_1:%.*]] = icmp slt i32 [[IV]], 2
-; IPSCCP-NEXT:    call void @use(i1 [[T_1]])
+; IPSCCP-NEXT:    call void @use(i1 true)
 ; IPSCCP-NEXT:    [[IV_NEXT]] = add nsw i32 [[IV]], 1
 ; IPSCCP-NEXT:    br label [[LOOP_HEADER]]
 ; IPSCCP:       exit:
 ; IPSCCP-NEXT:    ret void
 ;
 entry:
   br label %loop.header
 

 ; IPSCCP-LABEL: @loop_with_header_2(
 ; IPSCCP-NEXT:  entry:
 ; IPSCCP-NEXT:    br label [[LOOP_HEADER:%.*]]
 ; IPSCCP:       loop.header:
 ; IPSCCP-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP_BODY:%.*]] ]
 ; IPSCCP-NEXT:    [[C_1:%.*]] = icmp slt i32 [[IV]], 200
 ; IPSCCP-NEXT:    br i1 [[C_1]], label [[LOOP_BODY]], label [[EXIT:%.*]]
 ; IPSCCP:       loop.body:
-; IPSCCP-NEXT:    [[T_1:%.*]] = icmp slt i32 [[IV]], 200
-; IPSCCP-NEXT:    call void @use(i1 [[T_1]])
+; IPSCCP-NEXT:    call void @use(i1 true)
 ; IPSCCP-NEXT:    [[IV_NEXT]] = add nsw i32 [[IV]], 1
 ; IPSCCP-NEXT:    br label [[LOOP_HEADER]]
 ; IPSCCP:       exit:
 ; IPSCCP-NEXT:    ret void
 ;
 entry:
   br label %loop.header