Make OrderedInstructions able to handle queries that Dominators could do, but faster (OrderedInstructions is O(N) once, O(1) after that, Dominators is O(N) all the time)

[• dberlin]

Summary

This adds the necessary support to OrderedInstructions to be able to start replacing the O(N) dominates(instruction, {use, instruction}) queries.

This is going to be a long slog because we'll have to pass it along to
a bunch of stuff to keep it up to date in utilities

I'll likely convert it to an analysis along the way, it's currently a utility.

Convert NaryReassociate to OrderedInstructions
Make PredicateInfo use it as well.
These will be committed as separate patches, they are just examples.

[• dberlin]

Note: I don't claim i believe the answers to be 100% correct from a theory perspective, they just match what dominators gives :)

[• dberlin]

(Sorry, this is a work in progress, as you can see from the OldResult stuff that i'm using for verification)

include/llvm/IR/Dominators.h

public:
 
   // Ensure base-class overloads are visible.
   using Base::dominates;
 
   /// \brief Return true if Def dominates a use in User.
   ///
   /// This performs the special checks necessary if Def and User are in the same
   /// basic block. Note that Def doesn't dominate a use in Def itself!
+
+  /// Note: These functions are deprecated and will be removed, please use the
+  /// versions in OrderedInstructions instead.
   bool dominates(const Instruction *Def, const Use &U) const;
   bool dominates(const Instruction *Def, const Instruction *User) const;
   bool dominates(const Instruction *Def, const BasicBlock *BB) const;
 
   /// Return true if an edge dominates a use.
   ///
   /// If BBE is not a unique edge between start and end of the edge, it can
   /// never dominate the use.

include/llvm/Transforms/Scalar/NaryReassociate.h

 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/PassManager.h"
+#include "llvm/Transforms/Utils/OrderedInstructions.h"
 
 namespace llvm {
 class NaryReassociatePass : public PassInfoMixin<NaryReassociatePass> {
 public:
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 
   // Glue for old PM.
   bool runImpl(Function &F, AssumptionCache *AC_, DominatorTree *DT_,
private:
   // than the pointer size. This function returns whether Index is shorter than
   // GEP's pointer size, i.e., whether Index needs to be sign-extended in order
   // to be an index of GEP.
   bool requiresSignExtension(Value *Index, GetElementPtrInst *GEP);
 
   AssumptionCache *AC;
   const DataLayout *DL;
   DominatorTree *DT;
+  std::unique_ptr<OrderedInstructions> OI;
   ScalarEvolution *SE;
   TargetLibraryInfo *TLI;
   TargetTransformInfo *TTI;
   // A lookup table quickly telling which instructions compute the given SCEV.
   // Note that there can be multiple instructions at different locations
   // computing to the same SCEV, so we map a SCEV to an instruction list.  For
   // example,
   //

include/llvm/Transforms/Utils/OrderedInstructions.h

class OrderedInstructions {
 
   /// The dominator tree of the parent function.
   DominatorTree *DT;
 
 public:
   /// Constructor.
   OrderedInstructions(DominatorTree *DT) : DT(DT) {}
 
-  /// Return true if first instruction dominates the second.
+  /// Return true if first instruction dominates the second instruction/use.
   bool dominates(const Instruction *, const Instruction *) const;
+  bool dominates(const Instruction *, const Use &) const;
 
   /// Invalidate the OrderedBasicBlock cache when its basic block changes.
   /// i.e. If an instruction is deleted or added to the basic block, the user
   /// should call this function to invalidate the OrderedBasicBlock cache for
   /// this basic block.
   void invalidateBlock(const BasicBlock *BB) { OBBMap.erase(BB); }
 };
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_UTILS_ORDEREDINSTRUCTIONS_H

lib/Transforms/Scalar/NaryReassociate.cpp

bool NaryReassociatePass::runImpl(Function &F, AssumptionCache *AC_,
                                   TargetLibraryInfo *TLI_,
                                   TargetTransformInfo *TTI_) {
   AC = AC_;
   DT = DT_;
   SE = SE_;
   TLI = TLI_;
   TTI = TTI_;
   DL = &F.getParent()->getDataLayout();
-
+  OI.reset(new OrderedInstructions(DT));
   bool Changed = false, ChangedInThisIteration;
   do {
     ChangedInThisIteration = doOneIteration(F);
     Changed |= ChangedInThisIteration;
   } while (ChangedInThisIteration);
   return Changed;
 }
 
NaryReassociatePass::findClosestMatchingDominator(const SCEV *CandidateExpr,
   // future instruction either. Therefore, we pop it out of the stack. This
   // optimization makes the algorithm O(n).
   while (!Candidates.empty()) {
     // Candidates stores WeakTrackingVHs, so a candidate can be nullptr if it's
     // removed
     // during rewriting.
     if (Value *Candidate = Candidates.back()) {
       Instruction *CandidateInstruction = cast<Instruction>(Candidate);
-      if (DT->dominates(CandidateInstruction, Dominatee))
+      if (OI->dominates(CandidateInstruction, Dominatee))
         return CandidateInstruction;
     }
     Candidates.pop_back();
   }
   return nullptr;
 }

lib/Transforms/Utils/OrderedInstructions.cpp

 //===-- OrderedInstructions.cpp - Instruction dominance function ---------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file defines utility to check dominance relation of 2 instructions.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Utils/OrderedInstructions.h"
+#include "llvm/IR/Instructions.h"
 using namespace llvm;
 
 /// Given 2 instructions, use OrderedBasicBlock to check for dominance relation
 /// if the instructions are in the same basic block, Otherwise, use dominator
-/// tree.
-bool OrderedInstructions::dominates(const Instruction *InstA,
-                                    const Instruction *InstB) const {
-  const BasicBlock *IBB = InstA->getParent();
+/// tree dominate routines.
+bool OrderedInstructions::dominates(const Instruction *Def,
+                                    const Instruction *User) const {
+  bool OldResult = DT->dominates(Def, User);
+  const auto *DefBB = Def->getParent();
+  const auto *UseBB = User->getParent();
+  assert(DefBB && UseBB);
+  // Any unreachable use is dominated, even if Def == User.
+  if (!DT->isReachableFromEntry(UseBB)) {
+    assert(OldResult == true);
+    return true;
+  }
+
+  // Unreachable definitions don't dominate anything.
+  if (!DT->isReachableFromEntry(DefBB)) {
+    assert(OldResult == false);
+    return false;
+  }
+
+  // An instruction doesn't dominate a use in itself.
+  if (Def == User) {
+    assert(OldResult == false);
+    return false;
+  }
+
+  if (isa<InvokeInst>(Def)) {
+    assert(OldResult == DT->dominates(Def, UseBB));
+    return DT->dominates(Def, UseBB);
+  }
+
+  if (DefBB != UseBB) {
+    assert(OldResult == DT->dominates(Def->getParent(), User->getParent()));
+    return DT->dominates(Def->getParent(), User->getParent());
+  }
+
   // Use ordered basic block to do dominance check in case the 2 instructions
   // are in the same basic block.
-  if (IBB == InstB->getParent()) {
-    auto OBB = OBBMap.find(IBB);
-    if (OBB == OBBMap.end())
-      OBB = OBBMap.insert({IBB, make_unique<OrderedBasicBlock>(IBB)}).first;
-    return OBB->second->dominates(InstA, InstB);
+  auto OBB = OBBMap.find(DefBB);
+    OBB = OBBMap.insert({DefBB, make_unique<OrderedBasicBlock>(DefBB)}).first;
+  assert(OldResult == OBB->second->dominates(Def, User));
+  return OBB->second->dominates(Def, User);
+}
+
+bool OrderedInstructions::dominates(const Instruction *Def,
+                                    const Use &U) const {
+  bool OldResult = DT->dominates(Def, U);
+  if (Def == U.getUser()) {
+    assert(OldResult == false);
+    return false;
+  }
+
+  // PHI node uses appear at the end of the block they come from.
+  if (auto *PN = dyn_cast<PHINode>(U.getUser())) {
+    auto *DefBB = Def->getParent();
+    auto *UseBB = PN->getIncomingBlock(U);
+    assert(DefBB && UseBB);
+    if (DefBB != UseBB) {
+      assert(OldResult == DT->dominates(DefBB, UseBB));
+      return DT->dominates(DefBB, UseBB);
+    }
+    // This mirrors the behavior of DominatorTree, which assumed no ordering
+    // among existing phi nodes.
+    if (isa<PHINode>(U.getUser())) {
+      assert(OldResult == true);
+      return true;
+    }
   }
-  return DT->dominates(InstA->getParent(), InstB->getParent());
+  assert(OldResult == dominates(Def, cast<Instruction>(U.getUser())));
+  return dominates(Def, cast<Instruction>(U.getUser()));
 }

lib/Transforms/Utils/PredicateInfo.cpp

auto *Op =
         RenameIter == RenameStack.begin() ? OrigOp : (RenameIter - 1)->Def;
     ValueDFS &Result = *RenameIter;
     auto *ValInfo = Result.PInfo;
     // For edge predicates, we can just place the operand in the block before
     // the terminator.  For assume, we have to place it right before the assume
     // to ensure we dominate all of our uses.  Always insert right before the
     // relevant instruction (terminator, assume), so that we insert in proper
     // order in the case of multiple predicateinfo in the same block.
+    CallInst *PIC = nullptr;
     if (isa<PredicateWithEdge>(ValInfo)) {
       IRBuilder<> B(getBranchTerminator(ValInfo));
       Function *IF = Intrinsic::getDeclaration(
           F.getParent(), Intrinsic::ssa_copy, Op->getType());
-      CallInst *PIC =
+      PIC =
           B.CreateCall(IF, Op, Op->getName() + "." + Twine(Counter++));
       PredicateMap.insert({PIC, ValInfo});
       Result.Def = PIC;
     } else {
       auto *PAssume = dyn_cast<PredicateAssume>(ValInfo);
       assert(PAssume &&
              "Should not have gotten here without it being an assume");
       IRBuilder<> B(PAssume->AssumeInst);
       Function *IF = Intrinsic::getDeclaration(
           F.getParent(), Intrinsic::ssa_copy, Op->getType());
-      CallInst *PIC = B.CreateCall(IF, Op);
+      PIC = B.CreateCall(IF, Op);
       PredicateMap.insert({PIC, ValInfo});
       Result.Def = PIC;
     }
+    OI.invalidateBlock(PIC->getParent());
   }
   return RenameStack.back().Def;
 }
 
 // Instead of the standard SSA renaming algorithm, which is O(Number of
 // instructions), and walks the entire dominator tree, we walk only the defs +
 // uses.  The standard SSA renaming algorithm does not really rely on the
 // dominator tree except to order the stack push/pops of the renaming stacks, so
for (auto &VD : OrderedUses) {
       // If the possible copy dominates something, materialize our stack up to
       // this point. This ensures every comparison that affects our operation
       // ends up with predicateinfo.
       if (!Result.Def)
         Result.Def = materializeStack(Counter, RenameStack, Op);
 
       DEBUG(dbgs() << "Found replacement " << *Result.Def << " for "
                    << *VD.U->get() << " in " << *(VD.U->getUser()) << "\n");
-      assert(DT.dominates(cast<Instruction>(Result.Def), *VD.U) &&
+      assert(OI.dominates(cast<Instruction>(Result.Def), *VD.U) &&
              "Predicateinfo def should have dominated this use");
       VD.U->set(Result.Def);
     }
   }
 }
 
 PredicateInfo::ValueInfo &PredicateInfo::getOrCreateValueInfo(Value *Operand) {
   auto OIN = ValueInfoNums.find(Operand);