[IPSCCP] Use PredicateInfo to propagate facts from cmp instructions.

[fhahn]

Summary

This patch updates IPSCCP to use PredicateInfo to propagate
facts to true branches predicated by EQ and to false branches
predicated by NE.

As a follow up, we should be able to extend it to also propagate additional facts about nonnull.

[efriedma]

This is interesting.

One of the weaknesses of the SCCP algorithm is that it's not path-sensitive; a value is only "constant" if it has the same value on all possible paths. The use of ssa_copy provides a way around this restriction, to some extent: the result of an ssa_copy can be a constant even if the operand is overdefined. That said, this is adding substantial complexity to IPSCCP, and I'm not sure how much benefit you'll get in practice; the example @test2 isn't really compelling.

Building the PredicateInfo up-front is probably fine; I would guess it's not that expensive compared to the other work IPSCCP is doing (but you should measure to quantify that).

We should be able to extend it to also propagate additional facts about floats

We need to be very cautious about propagating facts about floats... things which are "obviously" true might not actually be true due to fast-math.

[fhahn]

Thanks for having a look!

In D45330#1058762, @efriedma wrote:

This is interesting.

One of the weaknesses of the SCCP algorithm is that it's not path-sensitive; a value is only "constant" if it has the same value on all possible paths. The use of ssa_copy provides a way around this restriction, to some extent: the result of an ssa_copy can be a constant even if the operand is overdefined. That said, this is adding substantial complexity to IPSCCP, and I'm not sure how much benefit you'll get in practice; the example @test2 isn't really compelling.

The test cases at the moment are just very simple to briefly illustrate what is going on. One case in particular I think this could be helpful with is propagating null/nonnull to callsites. I will make the patch slightly more powerful and try to gather some numbers in the next few days.

[• dberlin]

So, predicateinfo is one of the fastest passes (or was) that we had. I'm not horribly worried about speed (i could make it faster, too).
It was faster than anything else we do that isn't lazy (IE it's faster than computing dominators, etc).
It wasn't even really measurable except on hundreds of thousands or millions of blocks.

I did have plans to try to turn it back into a virtual form at some point (which would make it faster), i think i found an not horrible way of doing it.

The one overall comment i'd have here is that SCCP is fairly limited in how it can use this, because of how limited the lattice is.
IPVRP would be a better bet, IMHO.

That said,

[fhahn]

In D45330#1062304, @dberlin wrote:

So, predicateinfo is one of the fastest passes (or was) that we had. I'm not horribly worried about speed (i could make it faster, too).
It was faster than anything else we do that isn't lazy (IE it's faster than computing dominators, etc).
It wasn't even really measurable except on hundreds of thousands or millions of blocks.

I did have plans to try to turn it back into a virtual form at some point (which would make it faster), i think i found an not horrible way of doing it.

The one overall comment i'd have here is that SCCP is fairly limited in how it can use this, because of how limited the lattice is.
IPVRP would be a better bet, IMHO.

Yep. One of the slightly longer-term things I want to do is either make IPSCCP use a lattice including (integer) ranges or have a separate pass doing value range propagation. Do you think having it as a separate pass would be beneficial?

That said,

Looks like the comment got cut off here?

[• dberlin]

whoops, hit send early.
That said, if you find this actually generates gains (papers on it basically say it should be a few percent improvement in found constants), i don't have any intrinsic reason not to do it just make sure we get the cost vs gain tradeoff right.

[fhahn]

Fix some problems, SingleSource, MultiSource, SPEC2006 now pass with this patch and LTO. Still needs some cleanup and a few more tests.

[fhahn]

In D45330#1058762, @efriedma wrote:

This is interesting.

One of the weaknesses of the SCCP algorithm is that it's not path-sensitive; a value is only "constant" if it has the same value on all possible paths. The use of ssa_copy provides a way around this restriction, to some extent: the result of an ssa_copy can be a constant even if the operand is overdefined. That said, this is adding substantial complexity to IPSCCP, and I'm not sure how much benefit you'll get in practice; the example @test2 isn't really compelling.

I collected some stats for SPEC2006, MultiSource and SingleSource with -O3 -flto.

For sccp.IPNumInstRemoved I get 88490 with this patch instead of 81585 without it (~ +8% eliminated instructions).
For sccp.IPNumArgsElimed, I get 5084 with this patch instead of 5081 without it (hardly any change).

I think number of instructions eliminated looks quite promising. What do you think?

[efriedma]

I think number of instructions eliminated looks quite promising

That's much better than I expected. Although, I'm not sure how much I would trust that number; IPSCCP runs before CorrelatedValuePropagation, so you might be optimizing sequences which would be optimized later anyway.

[fhahn]

In D45330#1066015, @efriedma wrote:

I think number of instructions eliminated looks quite promising

That's much better than I expected. Although, I'm not sure how much I would trust that number; IPSCCP runs before CorrelatedValuePropagation, so you might be optimizing sequences which would be optimized later anyway.

I also aggregated all stats by CorrelatedValuePropagation for the same set of benchmarks: With this patch, CVP triggered in 23754 cases, without this patch it triggered in 24904 cases. I guess this suggests some of the cases eliminated with this patch would also be handled by CVP. But the majority would not be.

One additional thing we could do by using PredicateInfo is propagate non-null constraints to call sites, which might help the inliner.

[fhahn]

I still need to look into a compilation issue with CINT2006/403.gcc.

[fhahn]

Rebased and fixed a few problems. This now passes the test-suite, SPEC2000 & SPEC2006 with LTO. I've now also done a benchmarking run with the suites mentioned earlier on a cortex-a57 with LTO. Overall the geomean runtime improvement is 0.65 percent. The biggest improvements were

         SingleSource/Benchmarks/BenchmarkGame/recursive    -13.16%
	SingleSource/Benchmarks/Stanford/RealMM	         -9.89%
	MultiSource/Benchmarks/McCat/08-main/main      -7.90%
	MultiSource/Benchmarks/MiBench/telecomm-CRC32/telecomm-CRC32 -6.64%
	MultiSource/Benchmarks/Prolangs-C++/ocean/ocean        -6.26%
	MultiSource/Benchmarks/ASC_Sequoia/IRSmk/IRSmk       -6.13%
	MultiSource/Benchmarks/Olden/mst/mst                            -6.08%
	MultiSource/Benchmarks/mediabench/adpcm/rawcaudio/rawcaudio      -5.21%
	SingleSource/Benchmarks/Shootout-C++/Shootout-C++-objinst             -5.19%
	SingleSource/Benchmarks/Polybench/stencils/jacobi-1d-imper/jacobi-1d-imper     -4.48%
	MultiSource/Benchmarks/Prolangs-C++/simul/simul               -4.26%
	SingleSource/Benchmarks/Shootout/Shootout-objinst            -3.72%

There are a few regression ranging from 0 to up 4% worse execution time

The sum of all SCCP stats for all benchmarks is 401732 over 374020 without this patch (+7%).

[fhahn]

Ping. Do you think that the results for this patch are convincing enough on it's own?

[• dberlin]

I think the numbers are good enough to be worth it perf wise.
Did you post compile time numbers?

If they look good, i'd say let's commit it.
(if not, please take a look at them before committing)

[fhahn]

In D45330#1098349, @dberlin wrote:

I think the numbers are good enough to be worth it perf wise.
Did you post compile time numbers?

Thanks for having a look!

I did not post them, but for the tests I run (test-suite, spec2000, spec2006) on AArch64, there were no compile time regressions. One change is that we now compute the dominator trees before IPSCCP. I suppose we should try and preserve them in IPSCCP. I'll try to put a patch together before I submit this change.

[davide]

Sorry Florian, I completely missed this one. LGTM as well.

[fhahn]

Thanks for having a look. Updated diff to include changes to pipeline tests. I plan to commit this tomorrow, unless there are any more concerns.

[fhahn]

test/Other/opt-O2-pipeline.ll

280 ↗

(On Diff #148047)

Arg, the order, in which the additional function pass managers for the analysis required by IPSCCP and GlobalOpt are added, is not deterministic.

A quick look at the legacy pass manager suggests that it uses a bunch of maps and sets to register discovered new passes. So those legacy pass manager tests sometimes fail on some systems.... I am not sure how to best sort out that out. Any ideas?

[efriedma]

test/Other/opt-O2-pipeline.ll

280 ↗

(On Diff #148047)

This is specifically the AvailableAnalysis map? You can switch to http://llvm.org/docs/ProgrammersManual.html#llvm-adt-mapvector-h, I guess...

[fhahn]

test/Other/opt-O2-pipeline.ll

280 ↗

(On Diff #148047)

Thank you very much, it's enough to use MapVector for OnTheFlyManagers : D47317

[fhahn]

I had to revert this patch in rL333323 because it caused a mismatch in the stage3 and stage4 binaries built by the clang-with-thin-lto-ubuntu bot. I will investigate.

[fhahn]

So it looks like the codegen differences come from PredicateInfo, rather than from the propagation. With only the parts of this patch to build and remove PredicateInfo, I get a small difference in the strtab section between a stage3 and stage4 build of clang with thin LTO, there's no difference in the .text section.

I also had a look at the IR after IPSCCP for both stages, the only differences are some variable names/labels. I am not entirely sure yet, but I think that might be caused by small differences in the order the ssa_copy intrinsics for the predicates are emitted. Any ideas or pointers would be greatly appreciated :)

[efriedma]

My first guess would be some sort of non-determinism.

If you're trying to determine whether to IR modules in memory are identical, make sure to include the use-list order in the dump.

[fhahn]

Thanks for you suggestions. With D48230, there is no difference in the stage3 and 4 clang binaries with thinlto for me locally.

[fhahn]

This is now committed as rL335206 and the LTO/Thin LTO bots are happy now. I will follow this up with a change to propagate non-null info.

[fhahn]

@thegameg reported another problem with PredicateInfo from a internal test related to mangling. I've put up D48541 to address it and will recommit this again once this is resolved.

[xbolva00]

Ping, still some issues? Since it was reverted again recently :(

I am especially interested in the follow up - nonnull info propagation.

llvm/trunk/test/Other/opt-Os-pipeline.ll

31

Set name?

[fhahn]

In D45330#1189015, @xbolva00 wrote:

Ping, still some issues? Since it was reverted again recently :(

Yep, there was one bot left that was failing because of this. I still have to reproduce the problem. Hope to have some time for that soon.

[xbolva00]

In D45330#1189421, @fhahn wrote:

In D45330#1189015, @xbolva00 wrote:

Ping, still some issues? Since it was reverted again recently :(

Yep, there was one bot left that was failing because of this. I still have to reproduce the problem. Hope to have some time for that soon.

Thanks for info, Florian.

[fhahn]

I finally had time to track down the last buildbot failure and it is committed now.

llvm/trunk/include/llvm/Transforms/Scalar/SCCP.h

 //   * Proves values to be constant, and replaces them with constants
 //   * Proves conditional branches to be unconditional
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_SCALAR_SCCP_H
 #define LLVM_TRANSFORMS_SCALAR_SCCP_H
 
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/PassManager.h"
+#include "llvm/Transforms/Utils/PredicateInfo.h"
 
 namespace llvm {
 
 class Function;
 
 /// This pass performs function-level constant propagation and merging.
 class SCCPPass : public PassInfoMixin<SCCPPass> {
 public:
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 };
 
-bool runIPSCCP(Module &M, const DataLayout &DL, const TargetLibraryInfo *TLI);
+bool runIPSCCP(
+    Module &M, const DataLayout &DL, const TargetLibraryInfo *TLI,
+    function_ref<std::unique_ptr<PredicateInfo>(Function &)> getPredicateInfo);
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_SCALAR_SCCP_H

llvm/trunk/lib/Transforms/IPO/SCCP.cpp

 #include "llvm/Transforms/IPO/SCCP.h"
+#include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Transforms/IPO.h"
 #include "llvm/Transforms/Scalar/SCCP.h"
 
 using namespace llvm;
 
 PreservedAnalyses IPSCCPPass::run(Module &M, ModuleAnalysisManager &AM) {
   const DataLayout &DL = M.getDataLayout();
   auto &TLI = AM.getResult<TargetLibraryAnalysis>(M);
-  if (!runIPSCCP(M, DL, &TLI))
+  auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
+  auto getPredicateInfo =
+      [&FAM](Function &F) -> std::unique_ptr<PredicateInfo> {
+    return make_unique<PredicateInfo>(F,
+                                      FAM.getResult<DominatorTreeAnalysis>(F),
+                                      FAM.getResult<AssumptionAnalysis>(F));
+  };
+
+  if (!runIPSCCP(M, DL, &TLI, getPredicateInfo))
     return PreservedAnalyses::all();
   return PreservedAnalyses::none();
 }
 
 namespace {
 
 //===--------------------------------------------------------------------===//
 //
public:
   }
 
   bool runOnModule(Module &M) override {
     if (skipModule(M))
       return false;
     const DataLayout &DL = M.getDataLayout();
     const TargetLibraryInfo *TLI =
         &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
-    return runIPSCCP(M, DL, TLI);
+
+    auto getPredicateInfo =
+        [this](Function &F) -> std::unique_ptr<PredicateInfo> {
+      return make_unique<PredicateInfo>(
+          F, this->getAnalysis<DominatorTreeWrapperPass>(F).getDomTree(),
+          this->getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F));
+    };
+
+    return runIPSCCP(M, DL, TLI, getPredicateInfo);
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.addRequired<AssumptionCacheTracker>();
+    AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<TargetLibraryInfoWrapperPass>();
   }
 };
 
 } // end anonymous namespace
 
 char IPSCCPLegacyPass::ID = 0;
 
 INITIALIZE_PASS_BEGIN(IPSCCPLegacyPass, "ipsccp",
                       "Interprocedural Sparse Conditional Constant Propagation",
                       false, false)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
 INITIALIZE_PASS_END(IPSCCPLegacyPass, "ipsccp",
                     "Interprocedural Sparse Conditional Constant Propagation",
                     false, false)
 
 // createIPSCCPPass - This is the public interface to this file.
 ModulePass *llvm::createIPSCCPPass() { return new IPSCCPLegacyPass(); }

llvm/trunk/lib/Transforms/Scalar/SCCP.cpp

 #include "llvm/IR/User.h"
 #include "llvm/IR/Value.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Scalar.h"
+#include "llvm/Transforms/Utils/PredicateInfo.h"
 #include <cassert>
 #include <utility>
 #include <vector>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "sccp"
 
class SCCPSolver : public InstVisitor<SCCPSolver> {
   // The BasicBlock work list
   SmallVector<BasicBlock *, 64>  BBWorkList;
 
   /// KnownFeasibleEdges - Entries in this set are edges which have already had
   /// PHI nodes retriggered.
   using Edge = std::pair<BasicBlock *, BasicBlock *>;
   DenseSet<Edge> KnownFeasibleEdges;
 
+  DenseMap<Function *, std::unique_ptr<PredicateInfo>> PredInfos;
+  DenseMap<Value *, SmallPtrSet<User *, 2>> AdditionalUsers;
+
 public:
+  void addPredInfo(Function &F, std::unique_ptr<PredicateInfo> PI) {
+    PredInfos[&F] = std::move(PI);
+  }
+
+  const PredicateBase *getPredicateInfoFor(Instruction *I) {
+    auto PI = PredInfos.find(I->getParent()->getParent());
+    if (PI == PredInfos.end())
+      return nullptr;
+    return PI->second->getPredicateInfoFor(I);
+  }
+
   SCCPSolver(const DataLayout &DL, const TargetLibraryInfo *tli)
       : DL(DL), TLI(tli) {}
 
   /// MarkBlockExecutable - This method can be used by clients to mark all of
   /// the blocks that are known to be intrinsically live in the processed unit.
   ///
   /// This returns true if the block was not considered live before.
   bool MarkBlockExecutable(BasicBlock *BB) {
private:
   // OperandChangedState - This method is invoked on all of the users of an
   // instruction that was just changed state somehow.  Based on this
   // information, we need to update the specified user of this instruction.
   void OperandChangedState(Instruction *I) {
     if (BBExecutable.count(I->getParent()))   // Inst is executable?
       visit(*I);
   }
 
+  // Add U as additional user of V.
+  void addAdditionalUser(Value *V, User *U) {
+    auto Iter = AdditionalUsers.insert({V, {}});
+    Iter.first->second.insert(U);
+  }
+
+  // Mark I's users as changed, including AdditionalUsers.
+  void markUsersAsChanged(Value *I) {
+    for (User *U : I->users())
+      if (auto *UI = dyn_cast<Instruction>(U))
+        OperandChangedState(UI);
+
+    auto Iter = AdditionalUsers.find(I);
+    if (Iter != AdditionalUsers.end()) {
+      for (User *U : Iter->second)
+        if (auto *UI = dyn_cast<Instruction>(U))
+          OperandChangedState(UI);
+    }
+  }
+
 private:
   friend class InstVisitor<SCCPSolver>;
 
   // visit implementations - Something changed in this instruction.  Either an
   // operand made a transition, or the instruction is newly executable.  Change
   // the value type of I to reflect these changes if appropriate.
   void visitPHINode(PHINode &I);
 
void SCCPSolver::visitLoadInst(LoadInst &I) {
   // Bail out.
   markOverdefined(IV, &I);
 }
 
 void SCCPSolver::visitCallSite(CallSite CS) {
   Function *F = CS.getCalledFunction();
   Instruction *I = CS.getInstruction();
 
+  if (auto *II = dyn_cast<IntrinsicInst>(I)) {
+    if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
+      if (ValueState[I].isOverdefined())
+        return;
+
+      auto *PI = getPredicateInfoFor(I);
+      if (!PI)
+        return;
+
+      auto *PBranch = dyn_cast<PredicateBranch>(getPredicateInfoFor(I));
+      if (!PBranch)
+        return mergeInValue(ValueState[I], I, getValueState(PI->OriginalOp));
+
+      Value *CopyOf = I->getOperand(0);
+      Value *Cond = PBranch->Condition;
+
+      // Everything below relies on the condition being a comparison.
+      auto *Cmp = dyn_cast<CmpInst>(Cond);
+      if (!Cmp)
+        return mergeInValue(ValueState[I], I, getValueState(PI->OriginalOp));
+
+      Value *CmpOp0 = Cmp->getOperand(0);
+      Value *CmpOp1 = Cmp->getOperand(1);
+      if (CopyOf != CmpOp0 && CopyOf != CmpOp1)
+        return mergeInValue(ValueState[I], I, getValueState(PI->OriginalOp));
+
+      if (CmpOp0 != CopyOf)
+        std::swap(CmpOp0, CmpOp1);
+
+      LatticeVal OriginalVal = getValueState(CopyOf);
+      LatticeVal EqVal = getValueState(CmpOp1);
+      LatticeVal &IV = ValueState[I];
+      if (PBranch->TrueEdge && Cmp->getPredicate() == CmpInst::ICMP_EQ) {
+        addAdditionalUser(CmpOp1, I);
+        if (OriginalVal.isConstant())
+          mergeInValue(IV, I, OriginalVal);
+        else
+          mergeInValue(IV, I, EqVal);
+        return;
+      }
+      if (!PBranch->TrueEdge && Cmp->getPredicate() == CmpInst::ICMP_NE) {
+        addAdditionalUser(CmpOp1, I);
+        if (OriginalVal.isConstant())
+          mergeInValue(IV, I, OriginalVal);
+        else
+          mergeInValue(IV, I, EqVal);
+        return;
+      }
+
+      return mergeInValue(IV, I, getValueState(PBranch->OriginalOp));
+    }
+  }
+
   // The common case is that we aren't tracking the callee, either because we
   // are not doing interprocedural analysis or the callee is indirect, or is
   // external.  Handle these cases first.
   if (!F || F->isDeclaration()) {
 CallOverdefined:
     // Void return and not tracking callee, just bail.
     if (I->getType()->isVoidTy()) return;
 
while (!OverdefinedInstWorkList.empty()) {
 
       // "I" got into the work list because it either made the transition from
       // bottom to constant, or to overdefined.
       //
       // Anything on this worklist that is overdefined need not be visited
       // since all of its users will have already been marked as overdefined
       // Update all of the users of this instruction's value.
       //
-      for (User *U : I->users())
-        if (auto *UI = dyn_cast<Instruction>(U))
-          OperandChangedState(UI);
+      markUsersAsChanged(I);
     }
 
     // Process the instruction work list.
     while (!InstWorkList.empty()) {
       Value *I = InstWorkList.pop_back_val();
 
       LLVM_DEBUG(dbgs() << "\nPopped off I-WL: " << *I << '\n');
 
       // "I" got into the work list because it made the transition from undef to
       // constant.
       //
       // Anything on this worklist that is overdefined need not be visited
       // since all of its users will have already been marked as overdefined.
       // Update all of the users of this instruction's value.
       //
       if (I->getType()->isStructTy() || !getValueState(I).isOverdefined())
-        for (User *U : I->users())
-          if (auto *UI = dyn_cast<Instruction>(U))
-            OperandChangedState(UI);
+        markUsersAsChanged(I);
     }
 
     // Process the basic block work list.
     while (!BBWorkList.empty()) {
       BasicBlock *BB = BBWorkList.back();
       BBWorkList.pop_back();
 
       LLVM_DEBUG(dbgs() << "\nPopped off BBWL: " << *BB << '\n');
for (BasicBlock &BB : F) {
     }
 
     if (auto *RI = dyn_cast<ReturnInst>(BB.getTerminator()))
       if (!isa<UndefValue>(RI->getOperand(0)))
         ReturnsToZap.push_back(RI);
   }
 }
 
-bool llvm::runIPSCCP(Module &M, const DataLayout &DL,
-                     const TargetLibraryInfo *TLI) {
+bool llvm::runIPSCCP(
+    Module &M, const DataLayout &DL, const TargetLibraryInfo *TLI,
+    function_ref<std::unique_ptr<PredicateInfo>(Function &)> getPredicateInfo) {
   SCCPSolver Solver(DL, TLI);
 
   // Loop over all functions, marking arguments to those with their addresses
   // taken or that are external as overdefined.
   for (Function &F : M) {
     if (F.isDeclaration())
       continue;
 
+    Solver.addPredInfo(F, getPredicateInfo(F));
     // Determine if we can track the function's return values. If so, add the
     // function to the solver's set of return-tracked functions.
     if (canTrackReturnsInterprocedurally(&F))
       Solver.AddTrackedFunction(&F);
 
     // Determine if we can track the function's arguments. If so, add the
     // function to the solver's set of argument-tracked functions.
     if (canTrackArgumentsInterprocedurally(&F)) {
for (unsigned i = 0, e = BlocksToErase.size(); i != e; ++i) {
               "Expect TermInst on constantint or blockaddress to be folded");
         (void) Folded;
       }
 
       // Finally, delete the basic block.
       F.getBasicBlockList().erase(DeadBB);
     }
     BlocksToErase.clear();
+
+    for (BasicBlock &BB : F) {
+      for (BasicBlock::iterator BI = BB.begin(), E = BB.end(); BI != E;) {
+        Instruction *Inst = &*BI++;
+        if (const PredicateBase *PI = Solver.getPredicateInfoFor(Inst)) {
+          if (auto *II = dyn_cast<IntrinsicInst>(Inst)) {
+            if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
+              Value *Op = II->getOperand(0);
+              Inst->replaceAllUsesWith(Op);
+              Inst->eraseFromParent();
+              continue;
+            }
+          }
+          Inst->replaceAllUsesWith(PI->OriginalOp);
+          Inst->eraseFromParent();
+        }
+      }
+    }
   }
 
   // If we inferred constant or undef return values for a function, we replaced
   // all call uses with the inferred value.  This means we don't need to bother
   // actually returning anything from the function.  Replace all return
   // instructions with return undef.
   //
   // Do this in two stages: first identify the functions we should process, then

llvm/trunk/test/Other/new-pm-lto-defaults.ll

 ; CHECK-O2-NEXT: Running pass: CallSiteSplittingPass on foo
 ; CHECK-O2-NEXT: Running analysis: TargetLibraryAnalysis on foo
 ; CHECK-O2-NEXT: Running analysis: TargetIRAnalysis on foo
 ; CHECK-O2-NEXT: Finished llvm::Function pass manager run.
 ; CHECK-O2-NEXT: PGOIndirectCallPromotion
 ; CHECK-O2-NEXT: Running analysis: ProfileSummaryAnalysis
 ; CHECK-O2-NEXT: Running analysis: OptimizationRemarkEmitterAnalysis
 ; CHECK-O2-NEXT: Running pass: IPSCCPPass
+; CHECK-O2-DAG: Running analysis: AssumptionAnalysis on foo
+; CHECK-O2-DAG: Running analysis: DominatorTreeAnalysis on foo
 ; CHECK-O2-NEXT: Running pass: CalledValuePropagationPass
 ; CHECK-O-NEXT: Running pass: ModuleToPostOrderCGSCCPassAdaptor<{{.*}}PostOrderFunctionAttrsPass>
 ; CHECK-O-NEXT: Running analysis: InnerAnalysisManagerProxy<{{.*}}SCC
 ; CHECK-O1-NEXT: Running analysis: InnerAnalysisManagerProxy<{{.*}}Function
 ; CHECK-O-NEXT: Running analysis: LazyCallGraphAnalysis
 ; CHECK-O-NEXT: Running analysis: FunctionAnalysisManagerCGSCCProxy
 ; CHECK-O-NEXT: Running analysis: OuterAnalysisManagerProxy<{{.*}}LazyCallGraph{{.*}}>
 ; CHECK-O-NEXT: Running analysis: AAManager
 ; CHECK-O1-NEXT: Running analysis: TargetLibraryAnalysis
 ; CHECK-O-NEXT: Running pass: ReversePostOrderFunctionAttrsPass
 ; CHECK-O-NEXT: Running analysis: CallGraphAnalysis
 ; CHECK-O-NEXT: Running pass: GlobalSplitPass
 ; CHECK-O-NEXT: Running pass: WholeProgramDevirtPass
 ; CHECK-O2-NEXT: Running pass: GlobalOptPass
 ; CHECK-O2-NEXT: Running pass: ModuleToFunctionPassAdaptor<{{.*}}PromotePass>
-; CHECK-O2-NEXT: Running analysis: DominatorTreeAnalysis
-; CHECK-O2-NEXT: Running analysis: AssumptionAnalysis
 ; CHECK-O2-NEXT: Running pass: ConstantMergePass
 ; CHECK-O2-NEXT: Running pass: DeadArgumentEliminationPass
 ; CHECK-O2-NEXT: Running pass: ModuleToFunctionPassAdaptor<{{.*}}PassManager{{.*}}>
 ; CHECK-O2-NEXT: Starting llvm::Function pass manager run.
 ; CHECK-O3-NEXT: Running pass: AggressiveInstCombinePass
 ; CHECK-O2-NEXT: Running pass: InstCombinePass
 ; CHECK-EP-Peephole-NEXT: Running pass: NoOpFunctionPass
 ; CHECK-O2-NEXT: Finished llvm::Function pass manager run.

llvm/trunk/test/Other/opt-O2-pipeline.ll

 ; CHECK:      Type-Based Alias Analysis
 ; CHECK-NEXT: Scoped NoAlias Alias Analysis
 ; CHECK-NEXT: Assumption Cache Tracker
 ; CHECK-NEXT: Profile summary info
 ; CHECK-NEXT:   ModulePass Manager
 ; CHECK-NEXT:     Force set function attributes
 ; CHECK-NEXT:     Infer set function attributes
 ; CHECK-NEXT:     Interprocedural Sparse Conditional Constant Propagation
+; CHECK-NEXT:       Unnamed pass: implement Pass::getPassName()
 ; CHECK-NEXT:     Called Value Propagation
 ; CHECK-NEXT:     Global Variable Optimizer
 ; CHECK-NEXT:       Unnamed pass: implement Pass::getPassName()
 ; CHECK-NEXT:     FunctionPass Manager
 ; CHECK-NEXT:       Dominator Tree Construction
 ; CHECK-NEXT:       Promote Memory to Register
 ; CHECK-NEXT:     Dead Argument Elimination
 ; CHECK-NEXT:     FunctionPass Manager

 ; CHECK-NEXT:       Lazy Block Frequency Analysis
 ; CHECK-NEXT:       Optimization Remark Emitter
 ; CHECK-NEXT:       Remove redundant instructions
 ; CHECK-NEXT:       Hoist/decompose integer division and remainder
 ; CHECK-NEXT:       Simplify the CFG
 ; CHECK-NEXT:       Module Verifier
 ; CHECK-NEXT:     Bitcode Writer
 ; CHECK-NEXT: Pass Arguments:
+; CHECK-NEXT:  FunctionPass Manager
+; CHECK-NEXT:     Dominator Tree Construction
+; CHECK-NEXT: Pass Arguments:
 ; CHECK-NEXT: Target Library Information
 ; CHECK-NEXT:   FunctionPass Manager
 ; CHECK-NEXT:     Dominator Tree Construction
 ; CHECK-NEXT:     Natural Loop Information
 ; CHECK-NEXT:     Branch Probability Analysis
 ; CHECK-NEXT:     Block Frequency Analysis
 ; CHECK-NEXT: Pass Arguments:
 ; CHECK-NEXT: Target Library Information

llvm/trunk/test/Other/opt-O3-pipeline.ll

 ; CHECK-NEXT: Assumption Cache Tracker
 ; CHECK-NEXT: Profile summary info
 ; CHECK-NEXT:   ModulePass Manager
 ; CHECK-NEXT:     Force set function attributes
 ; CHECK-NEXT:     Infer set function attributes
 ; CHECK-NEXT:     FunctionPass Manager
 ; CHECK-NEXT:       Call-site splitting
 ; CHECK-NEXT:     Interprocedural Sparse Conditional Constant Propagation
+; CHECK-NEXT:       Unnamed pass: implement Pass::getPassName()
 ; CHECK-NEXT:     Called Value Propagation
 ; CHECK-NEXT:     Global Variable Optimizer
 ; CHECK-NEXT:       Unnamed pass: implement Pass::getPassName()
 ; CHECK-NEXT:     FunctionPass Manager
 ; CHECK-NEXT:       Dominator Tree Construction
 ; CHECK-NEXT:       Promote Memory to Register
 ; CHECK-NEXT:     Dead Argument Elimination
 ; CHECK-NEXT:     FunctionPass Manager

 ; CHECK-NEXT:       Lazy Block Frequency Analysis
 ; CHECK-NEXT:       Optimization Remark Emitter
 ; CHECK-NEXT:       Remove redundant instructions
 ; CHECK-NEXT:       Hoist/decompose integer division and remainder
 ; CHECK-NEXT:       Simplify the CFG
 ; CHECK-NEXT:       Module Verifier
 ; CHECK-NEXT:     Bitcode Writer
 ; CHECK-NEXT: Pass Arguments:
+; CHECK-NEXT:  FunctionPass Manager
+; CHECK-NEXT:     Dominator Tree Construction
+; CHECK-NEXT: Pass Arguments:
 ; CHECK-NEXT: Target Library Information
 ; CHECK-NEXT:   FunctionPass Manager
 ; CHECK-NEXT:     Dominator Tree Construction
 ; CHECK-NEXT:     Natural Loop Information
 ; CHECK-NEXT:     Branch Probability Analysis
 ; CHECK-NEXT:     Block Frequency Analysis
 ; CHECK-NEXT: Pass Arguments:
 ; CHECK-NEXT: Target Library Information

llvm/trunk/test/Other/opt-Os-pipeline.ll

 ; CHECK:      Type-Based Alias Analysis
 ; CHECK-NEXT: Scoped NoAlias Alias Analysis
 ; CHECK-NEXT: Assumption Cache Tracker
 ; CHECK-NEXT: Profile summary info
 ; CHECK-NEXT:   ModulePass Manager
 ; CHECK-NEXT:     Force set function attributes
 ; CHECK-NEXT:     Infer set function attributes
 ; CHECK-NEXT:     Interprocedural Sparse Conditional Constant Propagation
+; CHECK-NEXT:       Unnamed pass: implement Pass::getPassName()
 ; CHECK-NEXT:     Called Value Propagation
 ; CHECK-NEXT:     Global Variable Optimizer
 ; CHECK-NEXT:       Unnamed pass: implement Pass::getPassName()
 ; CHECK-NEXT:     FunctionPass Manager
 ; CHECK-NEXT:       Dominator Tree Construction
 ; CHECK-NEXT:       Promote Memory to Register
 ; CHECK-NEXT:     Dead Argument Elimination
 ; CHECK-NEXT:     FunctionPass Manager

 ; CHECK-NEXT:       Lazy Block Frequency Analysis
 ; CHECK-NEXT:       Optimization Remark Emitter
 ; CHECK-NEXT:       Remove redundant instructions
 ; CHECK-NEXT:       Hoist/decompose integer division and remainder
 ; CHECK-NEXT:       Simplify the CFG
 ; CHECK-NEXT:       Module Verifier
 ; CHECK-NEXT:     Bitcode Writer
 ; CHECK-NEXT: Pass Arguments:
+; CHECK-NEXT:  FunctionPass Manager
+; CHECK-NEXT:     Dominator Tree Construction
+; CHECK-NEXT: Pass Arguments:
 ; CHECK-NEXT: Target Library Information
 ; CHECK-NEXT:   FunctionPass Manager
 ; CHECK-NEXT:     Dominator Tree Construction
 ; CHECK-NEXT:     Natural Loop Information
 ; CHECK-NEXT:     Branch Probability Analysis
 ; CHECK-NEXT:     Block Frequency Analysis
 ; CHECK-NEXT: Pass Arguments:
 ; CHECK-NEXT: Target Library Information

llvm/trunk/test/Transforms/IPConstantProp/musttail-call.ll

 ; RUN: opt < %s -ipsccp -S | FileCheck %s
 ; PR36485
 ; musttail call result can\'t be replaced with a constant, unless the call
 ; can be removed
 
 declare i32 @external()
 
 define i8* @start(i8 %v) {
   %c1 = icmp eq i8 %v, 0
   br i1 %c1, label %true, label %false
 true:
-  ; CHECK: %ca = musttail call i8* @side_effects(i8 %v)
+  ; CHECK: %ca = musttail call i8* @side_effects(i8 0)
   ; CHECK: ret i8* %ca
   %ca = musttail call i8* @side_effects(i8 %v)
   ret i8* %ca
 false:
   %c2 = icmp eq i8 %v, 1
   br i1 %c2, label %c2_true, label %c2_false
 c2_true:
   %ca1 = musttail call i8* @no_side_effects(i8 %v)
   ; CHECK: ret i8* null
   ret i8* %ca1
 c2_false:
   ; CHECK: %ca2 = musttail call i8* @dont_zap_me(i8 %v)
   ; CHECK: ret i8* %ca2
   %ca2 = musttail call i8* @dont_zap_me(i8 %v)
   ret i8* %ca2
 }
 
 define internal i8* @side_effects(i8 %v) {
   %i1 = call i32 @external()
 
   ; since this goes back to `start` the SCPP should be see that the return value
   ; is always `null`.
   ; The call can't be removed due to `external` call above, though.
 
-  ; CHECK: %ca = musttail call i8* @start(i8 %v)
+  ; CHECK: %ca = musttail call i8* @start(i8 0)
   %ca = musttail call i8* @start(i8 %v)
 
   ; Thus the result must be returned anyway
   ; CHECK: ret i8* %ca
   ret i8* %ca
 }
 
 define internal i8* @no_side_effects(i8 %v) readonly nounwind {

llvm/trunk/test/Transforms/SCCP/ipsccp-predicated.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -ipsccp -S | FileCheck %s
+
+define i32 @test1(i32 %v) {
+; CHECK-LABEL: @test1(
+; CHECK-NEXT:  Entry:
+; CHECK-NEXT:    [[TOBOOL1:%.*]] = icmp eq i32 [[V:%.*]], 10
+; CHECK-NEXT:    br i1 [[TOBOOL1]], label [[T:%.*]], label [[F:%.*]]
+; CHECK:       T:
+; CHECK-NEXT:    [[R:%.*]] = call i32 @callee(i32 20)
+; CHECK-NEXT:    ret i32 [[R]]
+; CHECK:       F:
+; CHECK-NEXT:    [[X:%.*]] = call i32 @callee(i32 [[V]])
+; CHECK-NEXT:    ret i32 [[X]]
+;
+Entry:
+  %tobool1 = icmp eq i32 %v, 10
+  br i1 %tobool1, label %T, label %F
+
+T:
+  %a = add i32 %v, 10
+  %r = call i32 @callee(i32 %a)
+  ret i32 %r
+
+F:
+  %x = call i32 @callee(i32 %v)
+  ret i32 %x
+}
+
+
+define internal i32 @test2(i32 %v, i32 %c) {
+; CHECK-LABEL: @test2(
+; CHECK-NEXT:  Entry:
+; CHECK-NEXT:    [[TOBOOL1:%.*]] = icmp eq i32 [[V:%.*]], 99
+; CHECK-NEXT:    br i1 [[TOBOOL1]], label [[T:%.*]], label [[F:%.*]]
+; CHECK:       T:
+; CHECK-NEXT:    [[R:%.*]] = call i32 @callee(i32 109)
+; CHECK-NEXT:    ret i32 [[R]]
+; CHECK:       F:
+; CHECK-NEXT:    [[X:%.*]] = call i32 @callee(i32 [[V]])
+; CHECK-NEXT:    ret i32 [[X]]
+;
+Entry:
+  %tobool1 = icmp eq i32 %v, %c
+  br i1 %tobool1, label %T, label %F
+
+T:
+  %a = add i32 %v, 10
+  %r = call i32 @callee(i32 %a)
+  ret i32 %r
+
+F:
+  %x = call i32 @callee(i32 %v)
+  ret i32 %x
+}
+
+define i32 @caller_test2(i32 %v) {
+; CHECK-LABEL: @caller_test2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[R:%.*]] = call i32 @test2(i32 [[V:%.*]], i32 99)
+; CHECK-NEXT:    ret i32 [[R]]
+;
+entry:
+  %r = call i32 @test2(i32 %v, i32 99)
+  ret i32 %r
+}
+
+declare i32 @callee(i32)