Const propagatin after hitting assume bugfix

[vsk]

A few inline comments --

include/llvm/Transforms/Utils/Local.h

291

"the given edge" is now a bit vague. Could you update the docstring?

lib/IR/Dominators.cpp

153

IMO this is fine as a comment.

If you think it's a good idea to lift this explanation into the assert, I suggest shortening it a bit.

205

Same comment as above.

[• dberlin]

I assume you are hitting this in switch statements or something similar. I triggered the same in NewGVN.

Note that the comment in dominates is simply wrong.
I discussed with this Rafael (who added this). The callers can, in fact, do *nothing* different than what the function would have to do, and in fact, would have to duplicate a ton of complicated critical edge logic that Dominates handles. That seems really bad to me.

Nowhere else in LLVM do we *assert* because a very dumb caller may cause a performance problem.
The right fix here is to simply remove the assert, and make sure your caller is smart about not calling this unnecessarily.

(IE cache the value of edge domination in cases like this).

[nicholas]

This seems to be missing a test?

[Prazek]

Hmm, yep, my bad, I forgot to add test to check this bug.

[nlewycky]

LGTM

[Prazek]

Small test change before pushing

include/llvm/Transforms/Utils/Local.h

 bool removeUnreachableBlocks(Function &F);
 
 /// \brief Combine the metadata of two instructions so that K can replace J
 ///
 /// Metadata not listed as known via KnownIDs is removed
 void combineMetadata(Instruction *K, const Instruction *J, ArrayRef<unsigned> KnownIDs);
 
 /// \brief Replace each use of 'From' with 'To' if that use is dominated by 
 /// the given edge.  Returns the number of replacements made.
 unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT,
                                   const BasicBlockEdge &Edge);
+/// \brief Replace each use of 'From' with 'To' if that use is dominated by
+/// the given BasicBlock. Returns the number of replacements made.
+unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT,
+                                  const BasicBlock *BB);
 } // End llvm namespace
 
 #endif

lib/IR/Dominators.cpp

bool DominatorTree::dominates(const Instruction *Def,
 
   return dominates(DefBB, UseBB);
 }
 
 bool DominatorTree::dominates(const BasicBlockEdge &BBE,
                               const BasicBlock *UseBB) const {
   // Assert that we have a single edge. We could handle them by simply
   // returning false, but since isSingleEdge is linear on the number of
-  // edges, the callers can normally handle them more efficiently.
-  assert(BBE.isSingleEdge());
+  // edges, the callers can normally handle them more efficientl
+  assert(BBE.isSingleEdge() &&
+         "This function is not efficient in handling multiple edges");
 
   // If the BB the edge ends in doesn't dominate the use BB, then the
   // edge also doesn't.
   const BasicBlock *Start = BBE.getStart();
   const BasicBlock *End = BBE.getEnd();
   if (!dominates(End, UseBB))
     return false;
 
   // Simple case: if the end BB has a single predecessor, the fact that it
   // dominates the use block implies that the edge also does.
bool DominatorTree::dominates(const BasicBlockEdge &BBE,
   }
   return true;
 }
 
 bool DominatorTree::dominates(const BasicBlockEdge &BBE, const Use &U) const {
   // Assert that we have a single edge. We could handle them by simply
   // returning false, but since isSingleEdge is linear on the number of
   // edges, the callers can normally handle them more efficiently.
-  assert(BBE.isSingleEdge());
+  assert(BBE.isSingleEdge() &&
+         "This function is not efficient in handling multiple edges");
 
   Instruction *UserInst = cast<Instruction>(U.getUser());
   // A PHI in the end of the edge is dominated by it.
   PHINode *PN = dyn_cast<PHINode>(UserInst);
   if (PN && PN->getParent() == BBE.getEnd() &&
       PN->getIncomingBlock(U) == BBE.getStart())
     return true;
 
   // Otherwise use the edge-dominates-block query, which
   // handles the crazy critical edge cases properly.
   const BasicBlock *UseBB;

lib/Transforms/Scalar/GVN.cpp

private:
     bool performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred,
                                    unsigned int ValNo);
     Value *findLeader(const BasicBlock *BB, uint32_t num);
     void cleanupGlobalSets();
     void verifyRemoved(const Instruction *I) const;
     bool splitCriticalEdges();
     BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ);
     bool replaceOperandsWithConsts(Instruction *I) const;
-    bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root);
+    bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root,
+                           bool DominatesByEdge);
     bool processFoldableCondBr(BranchInst *BI);
     void addDeadBlock(BasicBlock *BB);
     void assignValNumForDeadCode();
   };
 
   char GVN::ID = 0;
 }
 
bool GVN::processAssumeIntrinsic(IntrinsicInst *IntrinsicI) {
   Value *V = IntrinsicI->getArgOperand(0);
   Constant *True = ConstantInt::getTrue(V->getContext());
   bool Changed = false;
   for (BasicBlock *Successor : successors(IntrinsicI->getParent())) {
     BasicBlockEdge Edge(IntrinsicI->getParent(), Successor);
 
     // This property is only true in dominated successors, propagateEquality
     // will check dominance for us.
-    Changed |= propagateEquality(V, True, Edge);
+    Changed |= propagateEquality(V, True, Edge, false);
   }
 
   if (auto *CmpI = dyn_cast<CmpInst>(V)) {
     if (CmpI->getPredicate() == CmpInst::Predicate::ICMP_EQ ||
         CmpI->getPredicate() == CmpInst::Predicate::FCMP_OEQ ||
         (CmpI->getPredicate() == CmpInst::Predicate::FCMP_UEQ &&
          CmpI->getFastMathFlags().noNaNs())) {
       Value *CmpLHS = CmpI->getOperand(0);
for (unsigned OpNum = 0; OpNum < Instr->getNumOperands(); ++OpNum) {
     }
   }
   return Changed;
 }
 
 /// The given values are known to be equal in every block
 /// dominated by 'Root'.  Exploit this, for example by replacing 'LHS' with
 /// 'RHS' everywhere in the scope.  Returns whether a change was made.
-bool GVN::propagateEquality(Value *LHS, Value *RHS,
-                            const BasicBlockEdge &Root) {
+/// If DominatesByEdge is false, then it means that it is dominated by Root.End.
+bool GVN::propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root,
+                            bool DominatesByEdge) {
   SmallVector<std::pair<Value*, Value*>, 4> Worklist;
   Worklist.push_back(std::make_pair(LHS, RHS));
   bool Changed = false;
   // For speed, compute a conservative fast approximation to
   // DT->dominates(Root, Root.getEnd());
   bool RootDominatesEnd = isOnlyReachableViaThisEdge(Root, DT);
 
   while (!Worklist.empty()) {
while (!Worklist.empty()) {
     // have the simple case where the edge dominates the end.
     if (RootDominatesEnd && !isa<Instruction>(RHS))
       addToLeaderTable(LVN, RHS, Root.getEnd());
 
     // Replace all occurrences of 'LHS' with 'RHS' everywhere in the scope.  As
     // LHS always has at least one use that is not dominated by Root, this will
     // never do anything if LHS has only one use.
     if (!LHS->hasOneUse()) {
-      unsigned NumReplacements = replaceDominatedUsesWith(LHS, RHS, *DT, Root);
+      unsigned NumReplacements = DominatesByEdge ?
+          replaceDominatedUsesWith(LHS, RHS, *DT, Root) :
+          replaceDominatedUsesWith(LHS, RHS, *DT, Root.getEnd());
+
       Changed |= NumReplacements > 0;
       NumGVNEqProp += NumReplacements;
     }
 
     // Now try to deduce additional equalities from this one. For example, if
     // the known equality was "(A != B)" == "false" then it follows that A and B
     // are equal in the scope. Only boolean equalities with an explicit true or
     // false RHS are currently supported.
if (CmpInst *Cmp = dyn_cast<CmpInst>(LHS)) {
       // appropriate instruction (if any).
       uint32_t NextNum = VN.getNextUnusedValueNumber();
       uint32_t Num = VN.lookup_or_add_cmp(Cmp->getOpcode(), NotPred, Op0, Op1);
       // If the number we were assigned was brand new then there is no point in
       // looking for an instruction realizing it: there cannot be one!
       if (Num < NextNum) {
         Value *NotCmp = findLeader(Root.getEnd(), Num);
         if (NotCmp && isa<Instruction>(NotCmp)) {
-          unsigned NumReplacements =
-            replaceDominatedUsesWith(NotCmp, NotVal, *DT, Root);
+          unsigned NumReplacements = DominatesByEdge ?
+                    replaceDominatedUsesWith(LHS, RHS, *DT, Root) :
+                    replaceDominatedUsesWith(LHS, RHS, *DT, Root.getEnd());
           Changed |= NumReplacements > 0;
           NumGVNEqProp += NumReplacements;
         }
       }
       // Ensure that any instruction in scope that gets the "A < B" value number
       // is replaced with false.
       // The leader table only tracks basic blocks, not edges. Only add to if we
       // have the simple case where the edge dominates the end.
if (BranchInst *BI = dyn_cast<BranchInst>(I)) {
     if (TrueSucc == FalseSucc)
       return false;
 
     BasicBlock *Parent = BI->getParent();
     bool Changed = false;
 
     Value *TrueVal = ConstantInt::getTrue(TrueSucc->getContext());
     BasicBlockEdge TrueE(Parent, TrueSucc);
-    Changed |= propagateEquality(BranchCond, TrueVal, TrueE);
+    Changed |= propagateEquality(BranchCond, TrueVal, TrueE, true);
 
     Value *FalseVal = ConstantInt::getFalse(FalseSucc->getContext());
     BasicBlockEdge FalseE(Parent, FalseSucc);
-    Changed |= propagateEquality(BranchCond, FalseVal, FalseE);
+    Changed |= propagateEquality(BranchCond, FalseVal, FalseE, true);
 
     return Changed;
   }
 
   // For switches, propagate the case values into the case destinations.
   if (SwitchInst *SI = dyn_cast<SwitchInst>(I)) {
     Value *SwitchCond = SI->getCondition();
     BasicBlock *Parent = SI->getParent();
     bool Changed = false;
 
     // Remember how many outgoing edges there are to every successor.
     SmallDenseMap<BasicBlock *, unsigned, 16> SwitchEdges;
     for (unsigned i = 0, n = SI->getNumSuccessors(); i != n; ++i)
       ++SwitchEdges[SI->getSuccessor(i)];
 
     for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
          i != e; ++i) {
       BasicBlock *Dst = i.getCaseSuccessor();
       // If there is only a single edge, propagate the case value into it.
       if (SwitchEdges.lookup(Dst) == 1) {
         BasicBlockEdge E(Parent, Dst);
-        Changed |= propagateEquality(SwitchCond, i.getCaseValue(), E);
+        Changed |= propagateEquality(SwitchCond, i.getCaseValue(), E, true);
       }
     }
     return Changed;
   }
 
   // Instructions with void type don't return a value, so there's
   // no point in trying to find redundancies in them.
   if (I->getType()->isVoidTy())

lib/Transforms/Utils/Local.cpp

if (DT.dominates(Root, U)) {
       DEBUG(dbgs() << "Replace dominated use of '"
             << From->getName() << "' as "
             << *To << " in " << *U << "\n");
       ++Count;
     }
   }
   return Count;
 }
+
+unsigned llvm::replaceDominatedUsesWith(Value *From, Value *To,
+                                        DominatorTree &DT,
+                                        const BasicBlock *BB) {
+  assert(From->getType() == To->getType());
+
+  unsigned Count = 0;
+  for (Value::use_iterator UI = From->use_begin(), UE = From->use_end();
+       UI != UE;) {
+    Use &U = *UI++;
+    auto *I = cast<Instruction>(U.getUser());
+    if (DT.dominates(BB, I->getParent())) {
+      U.set(To);
+      DEBUG(dbgs() << "Replace dominated use of '" << From->getName() << "' as "
+                   << *To << " in " << *U << "\n");
+      ++Count;
+    }
+  }
+  return Count;
+}