[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

 //===- ValueLattice.h - Value constraint analysis ---------------*- C++ -*-===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
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;
+    }
   };
 
   // Const and Range are initialized on-demand.
   ValueLatticeElement() : Tag(unknown) {}
 
   /// Custom destructor to ensure Range is properly destroyed, when the object
   /// is deallocated.
   ~ValueLatticeElement() {
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

 //===- 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) {
 
       if (!PBranch->TrueEdge)
         Pred = CmpInst::getInversePredicate(Pred);
 
       ValueLatticeElement CondVal = getValueState(CmpOp1);
       ValueLatticeElement &IV = ValueState[I];
       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, 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));
+            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, I);
         mergeInValue(IV, I, 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
 

 ; IPSCCP-NEXT:    [[TMP32:%.*]] = phi i8* [ [[TMP17]], [[BB23]] ], [ [[TMP17]], [[BB25]] ], [ [[TMP9]], [[BB8]] ]
 ; IPSCCP-NEXT:    [[TMP33:%.*]] = phi i16* [ [[TMP18]], [[BB23]] ], [ [[TMP18]], [[BB25]] ], [ [[TMP10]], [[BB8]] ]
 ; IPSCCP-NEXT:    [[TMP34:%.*]] = icmp eq i32 [[TMP11]], 0
 ; IPSCCP-NEXT:    br i1 [[TMP34]], label [[BB35:%.*]], label [[BB37:%.*]]
 ; IPSCCP:       bb35:
 ; IPSCCP-NEXT:    [[TMP36:%.*]] = getelementptr inbounds i8, i8* [[TMP32]], i64 1
 ; IPSCCP-NEXT:    br label [[BB66:%.*]]
 ; IPSCCP:       bb37:
-; IPSCCP-NEXT:    [[C_2:%.*]] = icmp eq i32 [[TMP11]], 8
-; IPSCCP-NEXT:    br i1 [[C_2]], label [[BB39:%.*]], label [[BB58:%.*]]
-; IPSCCP:       bb39:
-; IPSCCP-NEXT:    [[TMP40:%.*]] = add nsw i32 [[TMP11]], -1
-; IPSCCP-NEXT:    [[TMP41:%.*]] = trunc i32 [[TMP3]] to i16
-; IPSCCP-NEXT:    store i16 [[TMP41]], i16* bitcast ([4 x i8]* @global.11 to i16*), align 1
-; IPSCCP-NEXT:    [[TMP42:%.*]] = getelementptr inbounds [[STRUCT_BLAM_2]], %struct.blam.2* [[ARG]], i32 0, i32 0
-; IPSCCP-NEXT:    [[TMP43:%.*]] = add i32 [[TMP7]], [[TMP40]]
-; IPSCCP-NEXT:    [[TMP44:%.*]] = mul i32 [[TMP43]], 4
-; IPSCCP-NEXT:    [[TMP45:%.*]] = add i32 [[TMP44]], 2
-; IPSCCP-NEXT:    [[TMP46:%.*]] = call dereferenceable(1) i8* @spam(%struct.baz.1* [[TMP42]], i32 [[TMP45]])
-; IPSCCP-NEXT:    [[TMP47:%.*]] = load i8, i8* [[TMP46]], align 1
-; IPSCCP-NEXT:    [[TMP48:%.*]] = zext i8 [[TMP47]] to i32
-; IPSCCP-NEXT:    [[TMP49:%.*]] = sub i32 [[TMP43]], 1
-; IPSCCP-NEXT:    [[TMP50:%.*]] = mul i32 [[TMP49]], 4
-; IPSCCP-NEXT:    [[TMP51:%.*]] = add i32 [[TMP50]], 2
-; IPSCCP-NEXT:    [[TMP52:%.*]] = call dereferenceable(1) i8* @spam(%struct.baz.1* [[TMP42]], i32 [[TMP51]])
-; IPSCCP-NEXT:    [[TMP53:%.*]] = load i8, i8* [[TMP52]], align 1
-; IPSCCP-NEXT:    [[TMP54:%.*]] = zext i8 [[TMP53]] to i32
-; IPSCCP-NEXT:    [[TMP55:%.*]] = icmp sgt i32 [[TMP48]], [[TMP54]]
-; IPSCCP-NEXT:    br i1 [[TMP55]], label [[BB56:%.*]], label [[BB60:%.*]]
-; IPSCCP:       bb56:
-; IPSCCP-NEXT:    [[TMP57:%.*]] = add nsw i32 [[TMP40]], -1
-; IPSCCP-NEXT:    br label [[BB60]]
+; IPSCCP-NEXT:    br label [[BB58:%.*]]
 ; IPSCCP:       bb58:
 ; IPSCCP-NEXT:    [[TMP59:%.*]] = bitcast i16* [[TMP33]] to i8*
 ; IPSCCP-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 1 getelementptr inbounds ([4 x i8], [4 x i8]* @global.11, i64 0, i64 0), i8* align 2 [[TMP59]], i64 4, i1 false)
-; IPSCCP-NEXT:    br label [[BB60]]
+; IPSCCP-NEXT:    br label [[BB60:%.*]]
 ; IPSCCP:       bb60:
-; IPSCCP-NEXT:    [[TMP61:%.*]] = phi i32 [ [[TMP57]], [[BB56]] ], [ [[TMP40]], [[BB39]] ], [ [[TMP11]], [[BB58]] ]
 ; IPSCCP-NEXT:    [[TMP62:%.*]] = getelementptr inbounds [[STRUCT_BLAM_2]], %struct.blam.2* [[ARG]], i32 0, i32 0
 ; IPSCCP-NEXT:    [[TMP63:%.*]] = add i32 [[TMP7]], 1
 ; IPSCCP-NEXT:    [[TMP64:%.*]] = mul i32 [[TMP63]], 4
 ; IPSCCP-NEXT:    [[TMP65:%.*]] = call dereferenceable(1) i8* @spam(%struct.baz.1* [[TMP62]], i32 [[TMP64]])
 ; IPSCCP-NEXT:    br label [[BB66]]
 ; IPSCCP:       bb66:
 ; IPSCCP-NEXT:    [[TMP67:%.*]] = phi i8* [ [[TMP36]], [[BB35]] ], [ null, [[BB60]] ]
 ; IPSCCP-NEXT:    ret i8* [[TMP67]]