Refactor replaceDominatedUsesWith to have a flag to control whether to replace uses in BB itself.

[danielcdh]

Summary

This is in preparation for LoopSink pass which calls replaceDominatedUsesWith to update after sinking.

[danielcdh]

This is also an obvious change, commit without review.

[chandlerc]

include/llvm/Transforms/Utils/Local.h

330–334

This was also landed without review, but I actually think this API isn't the right one.

The first problem is that boolean flags to change state tend to make call sites really hard to read. All the reader sees is "false". Even if you add a comment with the name of the parameter, it doesn't help much because the parameter is pretty subtle. "IncludeSelf" is misleading as this isn't talking about instructions which use themselves, but rather users that happen to be in the same basic block.

This overall seems like a confusing way to describe the operation, because dominance is no longer a very precise term. I wonder if it would make more sense to just have the client do two separate operations where it first replaces uses dominated by the basic block and then has dedicated logic to handle the uses within the basic block with clear comments explaining why this works?

As one example of something that I'd want explanations around: what does it mean to replace an operand to a *phi node* in BB?

Anyways, not sure if the idea above has a really bad impact on the call sites (looots of code or something), or if you see other ways to structure the API that would be more clear?

[danielcdh]

reverted in r280949

[danielcdh]

Updated the callsite in https://reviews.llvm.org/D22778 to invoke the other API with a loop so that the API change is not required.

PTAL

[danielcdh]

In D24170#537323, @danielcdh wrote:

Updated the callsite in https://reviews.llvm.org/D22778 to invoke the other API with a loop so that the API change is not required.

PTAL

Turns out the other API (dominate by edge) does not work for this purpose. I still need to use the original API (dominate by block). I've added code at the callsite to handle this. It does not look very elegant, but it's the only way I can think of that does not require API change (nor can I think of a better way to change API to make it more reasonable). Let me know if you have any suggestions.

include/llvm/Transforms/Utils/Local.h

 ///
 /// Unknown metadata is removed.
 void combineMetadataForCSE(Instruction *K, const Instruction *J);
 
 /// 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);
+
 /// Replace each use of 'From' with 'To' if that use is dominated by
-/// the end of the given BasicBlock. Returns the number of replacements made.
+/// the end of 'BB'. Returns the number of replacements made.
+/// Replace use of 'From' with 'To' in 'BB' if 'IncludeSelf' is true.
 unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT,
-                                  const BasicBlock *BB);
+                                  const BasicBlock *BB, bool IncludeSelf);
 
 
 /// Return true if the CallSite CS calls a gc leaf function.
 ///
 /// A leaf function is a function that does not safepoint the thread during its
 /// execution.  During a call or invoke to such a function, the callers stack
 /// does not have to be made parseable.
 ///

lib/Transforms/Scalar/GVN.cpp

while (!Worklist.empty()) {
 
     // 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 =
           DominatesByEdge
               ? replaceDominatedUsesWith(LHS, RHS, *DT, Root)
-              : replaceDominatedUsesWith(LHS, RHS, *DT, Root.getStart());
+              : replaceDominatedUsesWith(LHS, RHS, *DT, Root.getStart(), false);
 
       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
if (CmpInst *Cmp = dyn_cast<CmpInst>(LHS)) {
       // 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 =
               DominatesByEdge
                   ? replaceDominatedUsesWith(NotCmp, NotVal, *DT, Root)
                   : replaceDominatedUsesWith(NotCmp, NotVal, *DT,
-                                             Root.getStart());
+                                             Root.getStart(), false);
           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.

lib/Transforms/Utils/Local.cpp

if (DT.dominates(Root, U)) {
       ++Count;
     }
   }
   return Count;
 }
 
 unsigned llvm::replaceDominatedUsesWith(Value *From, Value *To,
                                         DominatorTree &DT,
-                                        const BasicBlock *BB) {
+                                        const BasicBlock *BB,
+                                        bool IncludeSelf) {
   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.properlyDominates(BB, I->getParent())) {
+    if ((IncludeSelf && BB == I->getParent()) ||
+        DT.properlyDominates(BB, I->getParent())) {
       U.set(To);
       DEBUG(dbgs() << "Replace dominated use of '" << From->getName() << "' as "
                    << *To << " in " << *U << "\n");
       ++Count;
     }
   }
   return Count;
 }