[SCCP] Turn sext into zext for positive ranges.

[fhahn]

Summary

This patch updates SCCP/IPSCCP to use the computed range info to turn
sexts into zexts, if the value is known to be non-negative. We already
to a similar transform in CorrelatedValuePropagation, but it seems like
we can catch a lot of additional cases by doing it in SCCP/IPSCCP as
well.

The transform is limited to ranges that are known to not include undef.
For it to be effective, we have to flip the MayIncludeUndef flag when
constructing ranges from predicates. That should be in line with the
recent LangRef updates, but may expose problems in other passes not
expecting branches on undef to be UB. But it might be good to start
making more aggressive use of the LangRef update and fix issues
uncovered. Alternatively we could wait until the 11.0 release branch is
taken.

Without this patch, CorrelatedValuePropagation turns ~6400 sexts into
zexts on MultiSource, SPEC2000 & SPEC2006. With this patch, CVP
transforms around 4000, while IPSCCP transforms around 10000.

This change impacts 90 binaries (147 unchanged). One interesting impact
is that this leads to a few more loops getting vectorized, probably
because reasoning about zexts is easier than about sexts in SCEV & co:

Program base patch3 diff
test-suite...T2000/256.bzip2/256.bzip2.test 20.00 21.00 5.0%
test-suite...T2006/401.bzip2/401.bzip2.test 22.00 23.00 4.5%
test-suite...0.perlbench/400.perlbench.test 84.00 87.00 3.6%
test-suite.../CINT2000/176.gcc/176.gcc.test 90.00 93.00 3.3%
test-suite...lications/ClamAV/clamscan.test 91.00 92.00 1.1%
test-suite.../CINT2006/403.gcc/403.gcc.test 220.00 222.00 0.9%
test-suite...pplications/oggenc/oggenc.test 126.00 127.00 0.8%
test-suite...arks/mafft/pairlocalalign.test 319.00 321.00 0.6%
test-suite...marks/7zip/7zip-benchmark.test 374.00 375.00 0.3%

[fhahn]

Ping. Rebased after updates to tests.

[efriedma]

llvm/lib/Transforms/Scalar/SCCP.cpp

1317

I'm a little uncomfortable that flipping this from true to false impacted zero testcases...

I'm not sure how to judge exactly how risky it is to land this without fixes to various passes we know have issues. I'm particularly worried about loop unswitch, since we saw a real miscompile involving it in the past.

1641

Are we keeping around stale pointers in the Solver? That's technically UB, I think, even if the code works otherwise, and the compiler is unlikely to take advantage.

[fhahn]

Strip change flipping MayIncludeUndef and add removeLatticeValueFor helper, to remove stale pointers from ValueState.

[fhahn]

llvm/lib/Transforms/Scalar/SCCP.cpp

1317

I'm a little uncomfortable that flipping this from true to false impacted zero testcases...

I'm not sure how to judge exactly how risky it is to land this without fixes to various passes we know have issues. I'm particularly worried about loop unswitch, since we saw a real miscompile involving it in the past.

Yeah, it's probably best to wait at least until the next release. I'll mention it in https://bugs.llvm.org/show_bug.cgi?id=46144. For now, I removed the change to MayIncludeUndef. That limits the cases we can catch, but there still are some.

I think the reason for why there are no changes to other test cases is because we currently only use ranges to replace compares with constants. When replacing with a constant I think we concluded that it does not matter whether the ranges include undef or not.

When it comes to replacing with other instructions based on range info like in this patch, we need to check for undef I think.

1641

Yes it does currently. I don't think it would cause in problems in practice, but it is better to properly remove it. I've added a removeLatticeValueFor and used that. We don't remove the entries when removing other instructions, but I guess if we create new instructions we could in theory re-use existing pointers or something.

[efriedma]

LGTM

llvm/lib/Transforms/Scalar/SCCP.cpp

1317

I think the reason for why there are no changes to other test cases is because we currently only use ranges to replace compares with constants.

Oh, right.

1641

Reusing existing pointers would only be if we tried to query the solver for an instruction we created after the solver runs; I don't think we do that.

[fhahn]

Thank you very much, Eli!

llvm/lib/Transforms/Scalar/SCCP.cpp

1641

Yep. The latest version does clear them up now, so we don't have to worry about it in the future :)

llvm/lib/Transforms/Scalar/SCCP.cpp

 #include <vector>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "sccp"
 
 STATISTIC(NumInstRemoved, "Number of instructions removed");
 STATISTIC(NumDeadBlocks , "Number of basic blocks unreachable");
+STATISTIC(NumInstReplaced,
+          "Number of instructions replaced with (simpler) instruction");
 
 STATISTIC(IPNumInstRemoved, "Number of instructions removed by IPSCCP");
 STATISTIC(IPNumArgsElimed ,"Number of arguments constant propagated by IPSCCP");
 STATISTIC(IPNumGlobalConst, "Number of globals found to be constant by IPSCCP");
+STATISTIC(
+    IPNumInstReplaced,
+    "Number of instructions replaced with (simpler) instruction by IPSCCP");
 
 // The maximum number of range extensions allowed for operations requiring
 // widening.
 static const unsigned MaxNumRangeExtensions = 10;
 
 /// Returns MergeOptions with MaxWidenSteps set to MaxNumRangeExtensions.
 static ValueLatticeElement::MergeOptions getMaxWidenStepsOpts() {
   return ValueLatticeElement::MergeOptions().setMaxWidenSteps(
std::vector<ValueLatticeElement> getStructLatticeValueFor(Value *V) const {
     for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
       auto I = StructValueState.find(std::make_pair(V, i));
       assert(I != StructValueState.end() && "Value not in valuemap!");
       StructValues.push_back(I->second);
     }
     return StructValues;
   }
 
+  void removeLatticeValueFor(Value *V) { ValueState.erase(V); }
+
   const ValueLatticeElement &getLatticeValueFor(Value *V) const {
     assert(!V->getType()->isStructTy() &&
            "Should use getStructLatticeValueFor");
     DenseMap<Value *, ValueLatticeElement>::const_iterator I =
         ValueState.find(V);
     assert(I != ValueState.end() &&
            "V not found in ValueState nor Paramstate map!");
     return I->second;
if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
         // 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));
         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;
       }
static bool tryToReplaceWithConstant(SCCPSolver &Solver, Value *V) {
   LLVM_DEBUG(dbgs() << "  Constant: " << *Const << " = " << *V << '\n');
 
   // Replaces all of the uses of a variable with uses of the constant.
   V->replaceAllUsesWith(Const);
   return true;
 }
 
 static bool simplifyInstsInBlock(SCCPSolver &Solver, BasicBlock &BB,
-                                 Statistic &InstRemovedStat) {
+                                 SmallPtrSetImpl<Value *> &InsertedValues,
+                                 Statistic &InstRemovedStat,
+                                 Statistic &InstReplacedStat) {
   bool MadeChanges = false;
   for (Instruction &Inst : make_early_inc_range(BB)) {
     if (Inst.getType()->isVoidTy())
       continue;
     if (tryToReplaceWithConstant(Solver, &Inst)) {
       if (Inst.isSafeToRemove())
         Inst.eraseFromParent();
       // Hey, we just changed something!
       MadeChanges = true;
       ++InstRemovedStat;
+    } else if (isa<SExtInst>(&Inst)) {
+      Value *ExtOp = Inst.getOperand(0);
+      if (isa<Constant>(ExtOp) || InsertedValues.count(ExtOp))
+        continue;
+      const ValueLatticeElement &IV = Solver.getLatticeValueFor(ExtOp);
+      if (!IV.isConstantRange(/*UndefAllowed=*/false))
+        continue;
+      if (IV.getConstantRange().isAllNonNegative()) {
+        auto *ZExt = new ZExtInst(ExtOp, Inst.getType(), "", &Inst);
+        InsertedValues.insert(ZExt);
+        Inst.replaceAllUsesWith(ZExt);
+        Solver.removeLatticeValueFor(&Inst);
+        Inst.eraseFromParent();
+        InstReplacedStat++;
+        MadeChanges = true;
+      }
     }
   }
   return MadeChanges;
 }
 
 // runSCCP() - Run the Sparse Conditional Constant Propagation algorithm,
 // and return true if the function was modified.
 static bool runSCCP(Function &F, const DataLayout &DL,
static bool runSCCP(Function &F, const DataLayout &DL,
   }
 
   bool MadeChanges = false;
 
   // If we decided that there are basic blocks that are dead in this function,
   // delete their contents now.  Note that we cannot actually delete the blocks,
   // as we cannot modify the CFG of the function.
 
+  SmallPtrSet<Value *, 32> InsertedValues;
   for (BasicBlock &BB : F) {
     if (!Solver.isBlockExecutable(&BB)) {
       LLVM_DEBUG(dbgs() << "  BasicBlock Dead:" << BB);
 
       ++NumDeadBlocks;
       NumInstRemoved += removeAllNonTerminatorAndEHPadInstructions(&BB);
 
       MadeChanges = true;
       continue;
     }
 
-    MadeChanges |= simplifyInstsInBlock(Solver, BB, NumInstRemoved);
+    MadeChanges |= simplifyInstsInBlock(Solver, BB, InsertedValues,
+                                        NumInstRemoved, NumInstReplaced);
   }
 
   return MadeChanges;
 }
 
 PreservedAnalyses SCCPPass::run(Function &F, FunctionAnalysisManager &AM) {
   const DataLayout &DL = F.getParent()->getDataLayout();
   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
if (Solver.isBlockExecutable(&F.front()))
       for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); AI != E;
            ++AI) {
         if (!AI->use_empty() && tryToReplaceWithConstant(Solver, &*AI)) {
           ++IPNumArgsElimed;
           continue;
         }
       }
 
+    SmallPtrSet<Value *, 32> InsertedValues;
     for (BasicBlock &BB : F) {
       if (!Solver.isBlockExecutable(&BB)) {
         LLVM_DEBUG(dbgs() << "  BasicBlock Dead:" << BB);
         ++NumDeadBlocks;
 
         MadeChanges = true;
 
         if (&BB != &F.front())
           BlocksToErase.push_back(&BB);
         continue;
       }
 
-      MadeChanges |= simplifyInstsInBlock(Solver, BB, IPNumInstRemoved);
+      MadeChanges |= simplifyInstsInBlock(Solver, BB, InsertedValues,
+                                          IPNumInstRemoved, IPNumInstReplaced);
     }
 
     DomTreeUpdater DTU = Solver.getDTU(F);
     // Change dead blocks to unreachable. We do it after replacing constants
     // in all executable blocks, because changeToUnreachable may remove PHI
     // nodes in executable blocks we found values for. The function's entry
     // block is not part of BlocksToErase, so we have to handle it separately.
     for (BasicBlock *BB : BlocksToErase) {

llvm/test/Transforms/SCCP/ip-ranges-casts.ll

;
   %call.2 = tail call i1 @f.zext(i32 300, i32 900)
   %res = and i1 %call.1, %call.2
   ret i1 %res
 }
 
 ; x = [100, 301)
 define internal i1 @f.sext(i32 %x, i32 %y) {
 ; CHECK-LABEL: define internal i1 @f.sext(i32 %x, i32 %y) {
-; CHECK-NEXT:    %t.1 = sext i32 %x to i64
-; CHECK-NEXT:    %c.2 = icmp sgt i64 %t.1, 299
-; CHECK-NEXT:    %c.4 = icmp slt i64 %t.1, 101
+; CHECK-NEXT:    [[T_1:%.*]] = zext i32 %x to i64
+; CHECK-NEXT:    %c.2 = icmp sgt i64 [[T_1]], 299
+; CHECK-NEXT:    %c.4 = icmp slt i64 [[T_1]], 101
 ; CHECK-NEXT:    %res.1 = add i1 false, %c.2
 ; CHECK-NEXT:    %res.2 = add i1 %res.1, false
 ; CHECK-NEXT:    %res.3 = add i1 %res.2, %c.4
 ; CHECK-NEXT:    %t.2 = sext i32 %y to i64
 ; CHECK-NEXT:    %c.6 = icmp sgt i64 %t.2, 899
 ; CHECK-NEXT:    %c.8 = icmp slt i64 %t.2, -119
 ; CHECK-NEXT:    %res.4 = add i1 %res.3, false
 ; CHECK-NEXT:    %res.5 = add i1 %res.4, %c.6

llvm/test/Transforms/SCCP/ip-ranges-sext.ll

exit:
   %p = phi i32 [ 0, %true.1 ], [ 1, %true.2], [ undef, %false ]
   %ext = sext i32 %p to i64
   ret i64 %ext
 }
 
 define i64 @test5(i32 %x) {
 ; CHECK-LABEL: @test5(
 ; CHECK-NEXT:    [[P:%.*]] = and i32 [[X:%.*]], 15
-; CHECK-NEXT:    [[EXT:%.*]] = sext i32 [[P]] to i64
-; CHECK-NEXT:    ret i64 [[EXT]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i32 [[P]] to i64
+; CHECK-NEXT:    ret i64 [[TMP1]]
 ;
   %p = and i32 %x, 15
   %ext = sext i32 %p to i64
   ret i64 %ext
 }
 
 ; sext is constant folded before sext -> zext conversion.
 define i64 @test6(i32 %x) {
 ; CHECK-LABEL: @test6(
 ; CHECK-NEXT:    ret i64 10
 ;
   %ext = sext i32 10 to i64
   ret i64 %ext
 }
 
 ; sext that can be converted to zext feeds another sext.
 define i64 @test7(i16 %x) {
 ; CHECK-LABEL: @test7(
 ; CHECK-NEXT:    [[P:%.*]] = and i16 [[X:%.*]], 15
-; CHECK-NEXT:    [[EXT_1:%.*]] = sext i16 [[P]] to i32
-; CHECK-NEXT:    [[EXT_2:%.*]] = sext i32 [[EXT_1]] to i64
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i16 [[P]] to i32
+; CHECK-NEXT:    [[EXT_2:%.*]] = sext i32 [[TMP1]] to i64
 ; CHECK-NEXT:    ret i64 [[EXT_2]]
 ;
   %p = and i16 %x, 15
   %ext.1 = sext i16 %p to i32
   %ext.2 = sext i32 %ext.1 to i64
   ret i64 %ext.2
 }

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

exit:
   %p = phi i32 [ 0, %true.1 ], [ 1, %true.2], [ undef, %false ]
   %ext = sext i32 %p to i64
   ret i64 %ext
 }
 
 define i64 @test2(i32 %x) {
 ; CHECK-LABEL: @test2(
 ; CHECK-NEXT:    [[P:%.*]] = and i32 [[X:%.*]], 15
-; CHECK-NEXT:    [[EXT:%.*]] = sext i32 [[P]] to i64
-; CHECK-NEXT:    ret i64 [[EXT]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i32 [[P]] to i64
+; CHECK-NEXT:    ret i64 [[TMP1]]
 ;
   %p = and i32 %x, 15
   %ext = sext i32 %p to i64
   ret i64 %ext
 }
 
 define i64 @test3(i1 %c.1, i1 %c.2) {
 ; CHECK-LABEL: @test3(
 ; CHECK-NEXT:    br i1 [[C_1:%.*]], label [[TRUE_1:%.*]], label [[FALSE:%.*]]
 ; CHECK:       true.1:
 ; CHECK-NEXT:    br i1 [[C_2:%.*]], label [[TRUE_2:%.*]], label [[EXIT:%.*]]
 ; CHECK:       true.2:
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       false:
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[P:%.*]] = phi i32 [ 0, [[TRUE_1]] ], [ 1, [[TRUE_2]] ], [ 3, [[FALSE]] ]
-; CHECK-NEXT:    [[EXT:%.*]] = sext i32 [[P]] to i64
-; CHECK-NEXT:    ret i64 [[EXT]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i32 [[P]] to i64
+; CHECK-NEXT:    ret i64 [[TMP1]]
 ;
   br i1 %c.1, label %true.1, label %false
 
 true.1:
   br i1 %c.2, label %true.2, label %exit
 
 true.2:
   br label %exit

llvm/test/Transforms/SCCP/widening.ll

 ; SCCP:       bb3:
 ; SCCP-NEXT:    unreachable
 ; SCCP:       bb4:
 ; SCCP-NEXT:    [[TMP5:%.*]] = add i64 [[TMP2]], 3
 ; SCCP-NEXT:    [[TMP6:%.*]] = and i64 [[TMP5]], 3
 ; SCCP-NEXT:    [[TMP7:%.*]] = sub i64 3, [[TMP6]]
 ; SCCP-NEXT:    [[TMP8:%.*]] = shl i64 [[TMP7]], 1
 ; SCCP-NEXT:    [[TMP9:%.*]] = trunc i64 [[TMP8]] to i32
-; SCCP-NEXT:    [[TMP10:%.*]] = sext i32 [[TMP9]] to i64
+; SCCP-NEXT:    [[TMP10:%.*]] = zext i32 [[TMP9]] to i64
 ; SCCP-NEXT:    br label [[BB11:%.*]]
 ; SCCP:       bb11:
 ; SCCP-NEXT:    [[TMP12:%.*]] = phi i64 [ [[TMP10]], [[BB4]] ], [ [[TMP17:%.*]], [[BB18:%.*]] ]
 ; SCCP-NEXT:    br label [[BB13:%.*]]
 ; SCCP:       bb13:
 ; SCCP-NEXT:    [[C_1:%.*]] = icmp eq i64 [[TMP12]], 6
 ; SCCP-NEXT:    br i1 [[C_1]], label [[BB15:%.*]], label [[BB16:%.*]]
 ; SCCP:       bb15:

 ; IPSCCP:       bb3:
 ; IPSCCP-NEXT:    unreachable
 ; IPSCCP:       bb4:
 ; IPSCCP-NEXT:    [[TMP5:%.*]] = add i64 [[TMP2]], 3
 ; IPSCCP-NEXT:    [[TMP6:%.*]] = and i64 [[TMP5]], 3
 ; IPSCCP-NEXT:    [[TMP7:%.*]] = sub i64 3, [[TMP6]]
 ; IPSCCP-NEXT:    [[TMP8:%.*]] = shl i64 [[TMP7]], 1
 ; IPSCCP-NEXT:    [[TMP9:%.*]] = trunc i64 [[TMP8]] to i32
-; IPSCCP-NEXT:    [[TMP10:%.*]] = sext i32 [[TMP9]] to i64
+; IPSCCP-NEXT:    [[TMP10:%.*]] = zext i32 [[TMP9]] to i64
 ; IPSCCP-NEXT:    br label [[BB11:%.*]]
 ; IPSCCP:       bb11:
 ; IPSCCP-NEXT:    [[TMP12:%.*]] = phi i64 [ [[TMP10]], [[BB4]] ], [ [[TMP17:%.*]], [[BB18:%.*]] ]
 ; IPSCCP-NEXT:    br label [[BB13:%.*]]
 ; IPSCCP:       bb13:
 ; IPSCCP-NEXT:    [[C_1:%.*]] = icmp eq i64 [[TMP12]], 6
 ; IPSCCP-NEXT:    br i1 [[C_1]], label [[BB15:%.*]], label [[BB16:%.*]]
 ; IPSCCP:       bb15: