Let CorrelatedValuePropagation preserve LazyValueInfo

[aqjune]

Summary

This patch makes CorrelatedValuePropagation preserve LazyValueInfo by adding LazyValueInfo::eraseValue & calling it whenever an instruction is erased.

Passes make check , test-suite, and SPECrate 2017.

Patch by aqjune (Juneyoung Lee)

[reames]

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

122

I'm confused why we need this. LVI uses ValueHandles, which should delete the entry from the cache once it's destroyed. Do you have a test case where that is not happening?

815

Have you checked the history? I believe that CVP used to preserve LVI. Why was that removed?

[reames]

Marking to remove from review queue. When replying to questions, please mark as ready for review.

[aqjune]

Removes eraseValue() calls

[aqjune]

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

122

You were right, I checked that these items were automatically removed from LazyValueInfoCache. I removed eraseValue() calls.

815

I checked that LazyValueAnalysis had not been added in the past. DominatorTreeAnalysis was added at https://reviews.llvm.org/D48059 , GlobalsAA was added at https://llvm.org/svn/llvm-project/llvm/trunk@274705 .

[aqjune]

I couldn't find ready for review option from anywhere :( 'Add Action...' dropdown menu contains Plan Changes and Abandon Revision only.

[reames]

LGTM. This may be slightly imprecise - for instance, when we fold an operand which allows further LVI analysis - but the preservation is conservatively correct.

p.s. Updating a review resets the status.

[aqjune]

Thanks! :)
I don't have commit access; if you don't mind, could you commit this patch instead please?

[xbolva00]

Please rebase

[aqjune]

Sorry, I was pretty busy last week.
@xbolva00 Rebased

[xbolva00]

In D59349#1595877, @aqjune wrote:

Sorry, I was pretty busy last week.
@xbolva00 Rebased

Commited, r366942.

include/llvm/Analysis/LazyValueInfo.h

public:
   ConstantRange getConstantRangeOnEdge(Value *V, BasicBlock *FromBB,
                                        BasicBlock *ToBB,
                                        Instruction *CxtI = nullptr);
 
   /// Inform the analysis cache that we have threaded an edge from
   /// PredBB to OldSucc to be from PredBB to NewSucc instead.
   void threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc, BasicBlock *NewSucc);
 
+  /// Inform the analysis cache that we have erased a value.
+  void eraseValue(Value *V);
+
   /// Inform the analysis cache that we have erased a block.
   void eraseBlock(BasicBlock *BB);
 
   /// Print the \LazyValueInfo Analysis.
   /// We pass in the DTree that is required for identifying which basic blocks
   /// we can solve/print for, in the LVIPrinter. The DT is optional
   /// in LVI, so we need to pass it here as an argument.
   void printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS);

lib/Analysis/LazyValueInfo.cpp

public:
     }
 
     /// This is part of the update interface to inform the cache
     /// that a block has been deleted.
     void eraseBlock(BasicBlock *BB) {
       TheCache.eraseBlock(BB);
     }
 
+    /// Inform the cache that a value has been deleted.
+    void eraseValue(Value *V) {
+      TheCache.eraseValue(V);
+    }
+
     /// Disables use of the DominatorTree within LVI.
     void disableDT() {
       if (DT) {
         assert(!DisabledDT && "Both DT and DisabledDT are not nullptr!");
         std::swap(DT, DisabledDT);
       }
     }
 

 void LazyValueInfo::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
                                BasicBlock *NewSucc) {
   if (PImpl) {
     const DataLayout &DL = PredBB->getModule()->getDataLayout();
     getImpl(PImpl, AC, &DL, DT).threadEdge(PredBB, OldSucc, NewSucc);
   }
 }
 
+void LazyValueInfo::eraseValue(Value *V) {
+  if (PImpl) {
+    getImpl(PImpl, AC, DL, DT).eraseValue(V);
+  }
+}
+
 void LazyValueInfo::eraseBlock(BasicBlock *BB) {
   if (PImpl) {
     const DataLayout &DL = BB->getModule()->getDataLayout();
     getImpl(PImpl, AC, &DL, DT).eraseBlock(BB);
   }
 }
 
 

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

public:
 
     bool runOnFunction(Function &F) override;
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.addRequired<DominatorTreeWrapperPass>();
       AU.addRequired<LazyValueInfoWrapperPass>();
       AU.addPreserved<GlobalsAAWrapperPass>();
       AU.addPreserved<DominatorTreeWrapperPass>();
+      AU.addPreserved<LazyValueInfoWrapperPass>();
     }
   };
 
 } // end anonymous namespace
 
 char CorrelatedValuePropagation::ID = 0;
 
 INITIALIZE_PASS_BEGIN(CorrelatedValuePropagation, "correlated-propagation",
static bool processSelect(SelectInst *S, LazyValueInfo *LVI) {
   if (!CI) return false;
 
   Value *ReplaceWith = S->getTrueValue();
   Value *Other = S->getFalseValue();
   if (!CI->isOne()) std::swap(ReplaceWith, Other);
   if (ReplaceWith == S) ReplaceWith = UndefValue::get(S->getType());
 
   S->replaceAllUsesWith(ReplaceWith);
+  LVI->eraseValue(S);
   S->eraseFromParent();
 
   ++NumSelects;
 
   return true;
 }
 
 /// Try to simplify a phi with constant incoming values that match the edge
for (auto &IncomingConstant : IncomingConstants) {
     BasicBlock *IncomingBB = P->getIncomingBlock(IncomingConstant.second);
     if (C != LVI->getConstantOnEdge(CommonValue, IncomingBB, ToBB, P))
       return false;
   }
 
   // All constant incoming values map to the same variable along the incoming
   // edges of the phi. The phi is unnecessary.
   P->replaceAllUsesWith(CommonValue);
+  LVI->eraseValue(P);
   P->eraseFromParent();
   ++NumPhiCommon;
   return true;
 }
 
 static bool processPHI(PHINode *P, LazyValueInfo *LVI, DominatorTree *DT,
                        const SimplifyQuery &SQ) {
   bool Changed = false;
for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) {
     }
 
     P->setIncomingValue(i, V);
     Changed = true;
   }
 
   if (Value *V = SimplifyInstruction(P, SQ)) {
     P->replaceAllUsesWith(V);
+    LVI->eraseValue(P);
     P->eraseFromParent();
     Changed = true;
   }
 
   if (!Changed)
     Changed = simplifyCommonValuePhi(P, LVI, DT);
 
   if (Changed)
static bool processCmp(CmpInst *Cmp, LazyValueInfo *LVI) {
   LazyValueInfo::Tristate Result =
       LVI->getPredicateAt(Cmp->getPredicate(), Op0, C, Cmp);
   if (Result == LazyValueInfo::Unknown)
     return false;
 
   ++NumCmps;
   Constant *TorF = ConstantInt::get(Type::getInt1Ty(Cmp->getContext()), Result);
   Cmp->replaceAllUsesWith(TorF);
+  LVI->eraseValue(Cmp);
   Cmp->eraseFromParent();
   return true;
 }
 
 /// Simplify a switch instruction by removing cases which can never fire. If the
 /// uselessness of a case could be determined locally then constant propagation
 /// would already have figured it out. Instead, walk the predecessors and
 /// statically evaluate cases based on information available on that edge. Cases
static bool willNotOverflow(IntrinsicInst *II, LazyValueInfo *LVI) {
   case Intrinsic::usub_with_overflow:
     return NoWrap(Instruction::Sub, OBO::NoUnsignedWrap);
   case Intrinsic::ssub_with_overflow:
     return NoWrap(Instruction::Sub, OBO::NoSignedWrap);
   }
   return false;
 }
 
-static void processOverflowIntrinsic(IntrinsicInst *II) {
+static void processOverflowIntrinsic(IntrinsicInst *II, LazyValueInfo *LVI) {
   IRBuilder<> B(II);
   Value *NewOp = nullptr;
   switch (II->getIntrinsicID()) {
   default:
     llvm_unreachable("Unexpected instruction.");
   case Intrinsic::uadd_with_overflow:
   case Intrinsic::sadd_with_overflow:
     NewOp = B.CreateAdd(II->getOperand(0), II->getOperand(1), II->getName());
     break;
   case Intrinsic::usub_with_overflow:
   case Intrinsic::ssub_with_overflow:
     NewOp = B.CreateSub(II->getOperand(0), II->getOperand(1), II->getName());
     break;
   }
   ++NumOverflows;
   Value *NewI = B.CreateInsertValue(UndefValue::get(II->getType()), NewOp, 0);
   NewI = B.CreateInsertValue(NewI, ConstantInt::getFalse(II->getContext()), 1);
   II->replaceAllUsesWith(NewI);
+  LVI->eraseValue(II);
   II->eraseFromParent();
 }
 
 /// Infer nonnull attributes for the arguments at the specified callsite.
 static bool processCallSite(CallSite CS, LazyValueInfo *LVI) {
   SmallVector<unsigned, 4> ArgNos;
   unsigned ArgNo = 0;
 
   if (auto *II = dyn_cast<IntrinsicInst>(CS.getInstruction())) {
     if (willNotOverflow(II, LVI)) {
-      processOverflowIntrinsic(II);
+      processOverflowIntrinsic(II, LVI);
       return true;
     }
   }
 
   // Deopt bundle operands are intended to capture state with minimal
   // perturbance of the code otherwise.  If we can find a constant value for
   // any such operand and remove a use of the original value, that's
   // desireable since it may allow further optimization of that value (e.g. via
auto *RHS = B.CreateTruncOrBitCast(Instr->getOperand(1), TruncTy,
                                      Instr->getName() + ".rhs.trunc");
   auto *BO = B.CreateBinOp(Instr->getOpcode(), LHS, RHS, Instr->getName());
   auto *Zext = B.CreateZExt(BO, Instr->getType(), Instr->getName() + ".zext");
   if (auto *BinOp = dyn_cast<BinaryOperator>(BO))
     if (BinOp->getOpcode() == Instruction::UDiv)
       BinOp->setIsExact(Instr->isExact());
 
   Instr->replaceAllUsesWith(Zext);
+  LVI->eraseValue(Instr);
   Instr->eraseFromParent();
   return true;
 }
 
 static bool processSRem(BinaryOperator *SDI, LazyValueInfo *LVI) {
   if (SDI->getType()->isVectorTy() || !hasPositiveOperands(SDI, LVI))
     return false;
 
   ++NumSRems;
   auto *BO = BinaryOperator::CreateURem(SDI->getOperand(0), SDI->getOperand(1),
                                         SDI->getName(), SDI);
   BO->setDebugLoc(SDI->getDebugLoc());
   SDI->replaceAllUsesWith(BO);
+  LVI->eraseValue(SDI);
   SDI->eraseFromParent();
 
   // Try to process our new urem.
   processUDivOrURem(BO, LVI);
 
   return true;
 }
 
 /// See if LazyValueInfo's ability to exploit edge conditions or range
 /// information is sufficient to prove the both operands of this SDiv are
 /// positive.  If this is the case, replace the SDiv with a UDiv. Even for local
 /// conditions, this can sometimes prove conditions instcombine can't by
 /// exploiting range information.
 static bool processSDiv(BinaryOperator *SDI, LazyValueInfo *LVI) {
   if (SDI->getType()->isVectorTy() || !hasPositiveOperands(SDI, LVI))
     return false;
 
   ++NumSDivs;
   auto *BO = BinaryOperator::CreateUDiv(SDI->getOperand(0), SDI->getOperand(1),
                                         SDI->getName(), SDI);
   BO->setDebugLoc(SDI->getDebugLoc());
   BO->setIsExact(SDI->isExact());
   SDI->replaceAllUsesWith(BO);
+  LVI->eraseValue(SDI);
   SDI->eraseFromParent();
 
   // Try to simplify our new udiv.
   processUDivOrURem(BO, LVI);
 
   return true;
 }
 
 static bool processAShr(BinaryOperator *SDI, LazyValueInfo *LVI) {
   if (SDI->getType()->isVectorTy())
     return false;
 
   Constant *Zero = ConstantInt::get(SDI->getType(), 0);
   if (LVI->getPredicateAt(ICmpInst::ICMP_SGE, SDI->getOperand(0), Zero, SDI) !=
       LazyValueInfo::True)
     return false;
 
   ++NumAShrs;
   auto *BO = BinaryOperator::CreateLShr(SDI->getOperand(0), SDI->getOperand(1),
                                         SDI->getName(), SDI);
   BO->setDebugLoc(SDI->getDebugLoc());
   BO->setIsExact(SDI->isExact());
   SDI->replaceAllUsesWith(BO);
+  LVI->eraseValue(SDI);
   SDI->eraseFromParent();
 
   return true;
 }
 
 static bool processAdd(BinaryOperator *AddOp, LazyValueInfo *LVI) {
   using OBO = OverflowingBinaryOperator;
 
CorrelatedValuePropagationPass::run(Function &F, FunctionAnalysisManager &AM) {
 
   bool Changed = runImpl(F, LVI, DT, getBestSimplifyQuery(AM, F));
 
   if (!Changed)
     return PreservedAnalyses::all();
   PreservedAnalyses PA;
   PA.preserve<GlobalsAA>();
   PA.preserve<DominatorTreeAnalysis>();
+  PA.preserve<LazyValueAnalysis>();
   return PA;
 }