[NFC] Factor out implicit control flow logic from GVN

[mkazantsev]

Summary

Logic for tracking implicit control flow instructions was added to GVN to
perform PRE optimizations correctly. It appears that GVN is not the only
optimization that sometimes does PRE, so this logic is required in other
places (such as Jump Threading).

This is an NFC patch that encapsulates all ICF-related logic in a dedicated
utility class separated from GVN.

[mkazantsev]

Need to rebase on top of latest changes in GVN.

[mkazantsev]

Rebased. We need to reanimate this.

[mkazantsev]

Moved fill to private API, added lazy calculations, overall it is now more user-friendly.

[mkazantsev]

If nobody objects I will have it merged early next week.

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

 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/Compiler.h"
-#include "llvm/Transforms/Utils/OrderedInstructions.h"
+#include "llvm/Transforms/Utils/ImplicitControlFlowTracking.h"
 #include <cstdint>
 #include <utility>
 #include <vector>
 
 namespace llvm {
 
 class AssumptionCache;
 class BasicBlock;
private:
   friend struct DenseMapInfo<Expression>;
 
   MemoryDependenceResults *MD;
   DominatorTree *DT;
   const TargetLibraryInfo *TLI;
   AssumptionCache *AC;
   SetVector<BasicBlock *> DeadBlocks;
   OptimizationRemarkEmitter *ORE;
-  // Maps a block to the topmost instruction with implicit control flow in it.
-  DenseMap<const BasicBlock *, const Instruction *>
-      FirstImplicitControlFlowInsts;
+  ImplicitControlFlowTracking *ICF;
 
-  OrderedInstructions *OI;
   ValueTable VN;
 
   /// A mapping from value numbers to lists of Value*'s that
   /// have that value number.  Use findLeader to query it.
   struct LeaderTableEntry {
     Value *Val;
     const BasicBlock *BB;
     LeaderTableEntry *Next;

llvm/trunk/include/llvm/Transforms/Utils/ImplicitControlFlowTracking.h

+//===-- ImplicitControlFlowTracking.h ---------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// This class allows to keep track on instructions with implicit control flow.
+// These are instructions that may not pass execution to their successors. For
+// example, throwing calls and guards do not always do this. If we need to know
+// for sure that some instruction is guaranteed to execute if the given block
+// is reached, then we need to make sure that there is no implicit control flow
+// instruction (ICFI) preceeding it. For example, this check is required if we
+// perform PRE moving non-speculable instruction to other place.
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_UTILS_IMPLICITCONTROLFLOWTRACKING_H
+#define LLVM_TRANSFORMS_UTILS_IMPLICITCONTROLFLOWTRACKING_H
+
+#include "llvm/IR/Dominators.h"
+#include "llvm/Transforms/Utils/OrderedInstructions.h"
+
+namespace llvm {
+
+class ImplicitControlFlowTracking {
+public:
+  ImplicitControlFlowTracking(DominatorTree *DT)
+      : OI(OrderedInstructions(DT)) {}
+
+  // Returns the topmost instruction with implicit control flow from the given
+  // basic block. Returns nullptr if there is no such instructions in the block.
+  const Instruction *getFirstICFI(const BasicBlock *BB);
+
+  // Returns true if at least one instruction from the given basic block has
+  // implicit control flow.
+  bool hasICF(const BasicBlock *BB);
+
+  // Returns true if the first ICFI of Insn's block exists and dominates Insn.
+  bool isDominatedByICFIFromSameBlock(const Instruction *Insn);
+
+  // Clears information about this particular block.
+  void invalidateBlock(const BasicBlock *BB);
+
+  // Invalidates all information from this tracking.
+  void clear();
+
+private:
+  // Fills information about the given block's implicit control flow.
+  void fill(const BasicBlock *BB);
+
+  // Maps a block to the topmost instruction with implicit control flow in it.
+  DenseMap<const BasicBlock *, const Instruction *>
+      FirstImplicitControlFlowInsts;
+  OrderedInstructions OI;
+  // Blocks for which we have the actual information.
+  SmallPtrSet<const BasicBlock *, 8> KnownBlocks;
+};
+
+} // llvm
+
+#endif // LLVM_TRANSFORMS_UTILS_IMPLICITCONTROLFLOWTRACKING_H

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

bool GVN::PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock,
   // ...
   // guard(0 <= index && index < LEN);
   // use(arr[index]);
   //
   // It is illegal to move the array access to any point above the guard,
   // because if the index is out of bounds we should deoptimize rather than
   // access the array.
   // Check that there is no guard in this block above our instruction.
-  if (!IsSafeToSpeculativelyExecute) {
-    auto It = FirstImplicitControlFlowInsts.find(TmpBB);
-    if (It != FirstImplicitControlFlowInsts.end()) {
-      assert(It->second->getParent() == TmpBB &&
-             "Implicit control flow map broken?");
-      if (OI->dominates(It->second, LI))
-        return false;
-    }
-  }
+  if (!IsSafeToSpeculativelyExecute && ICF->isDominatedByICFIFromSameBlock(LI))
   while (TmpBB->getSinglePredecessor()) {
     TmpBB = TmpBB->getSinglePredecessor();
     if (TmpBB == LoadBB) // Infinite (unreachable) loop.
       return false;
     if (Blockers.count(TmpBB))
       return false;
 
     // If any of these blocks has more than one successor (i.e. if the edge we
     // just traversed was critical), then there are other paths through this
     // block along which the load may not be anticipated.  Hoisting the load
     // above this block would be adding the load to execution paths along
     // which it was not previously executed.
     if (TmpBB->getTerminator()->getNumSuccessors() != 1)
       return false;
 
     // Check that there is no implicit control flow in a block above.
-    if (!IsSafeToSpeculativelyExecute &&
-        FirstImplicitControlFlowInsts.count(TmpBB))
+    if (!IsSafeToSpeculativelyExecute && ICF->hasICF(TmpBB))
       return false;
   }
 
   assert(TmpBB);
   LoadBB = TmpBB;
 
   // Check to see how many predecessors have the loaded value fully
   // available.
bool GVN::runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
                   MemoryDependenceResults *RunMD, LoopInfo *LI,
                   OptimizationRemarkEmitter *RunORE) {
   AC = &RunAC;
   DT = &RunDT;
   VN.setDomTree(DT);
   TLI = &RunTLI;
   VN.setAliasAnalysis(&RunAA);
   MD = RunMD;
-  OrderedInstructions OrderedInstrs(DT);
-  OI = &OrderedInstrs;
+  ImplicitControlFlowTracking ImplicitCFT(DT);
+  ICF = &ImplicitCFT;
   VN.setMemDep(MD);
   ORE = RunORE;
 
   bool Changed = false;
   bool ShouldContinue = true;
 
   DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
   // Merge unconditional branches, allowing PRE to catch more
for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
     // If we need some instructions deleted, do it now.
     NumGVNInstr += InstrsToErase.size();
 
     // Avoid iterator invalidation.
     bool AtStart = BI == BB->begin();
     if (!AtStart)
       --BI;
 
-    bool InvalidateImplicitCF = false;
-    const Instruction *MaybeFirstICF = FirstImplicitControlFlowInsts.lookup(BB);
+    const Instruction *MaybeFirstICF = ICF->getFirstICFI(BB);
     for (auto *I : InstrsToErase) {
       assert(I->getParent() == BB && "Removing instruction from wrong block?");
       LLVM_DEBUG(dbgs() << "GVN removed: " << *I << '\n');
       salvageDebugInfo(*I);
       if (MD) MD->removeInstruction(I);
       LLVM_DEBUG(verifyRemoved(I));
       if (MaybeFirstICF == I) {
         // We have erased the first ICF in block. The map needs to be updated.
-        InvalidateImplicitCF = true;
         // Do not keep dangling pointer on the erased instruction.
         MaybeFirstICF = nullptr;
       }
       I->eraseFromParent();
     }
 
-    OI->invalidateBlock(BB);
+    ICF->invalidateBlock(BB);
     InstrsToErase.clear();
-    if (InvalidateImplicitCF)
-      fillImplicitControlFlowInfo(BB);
 
     if (AtStart)
       BI = BB->begin();
     else
       ++BI;
   }
 
   return ChangedFunction;
bool GVN::performScalarPRE(Instruction *CurInst) {
   Instruction *PREInstr = nullptr;
 
   if (NumWithout != 0) {
     if (!isSafeToSpeculativelyExecute(CurInst)) {
       // It is only valid to insert a new instruction if the current instruction
       // is always executed. An instruction with implicit control flow could
       // prevent us from doing it. If we cannot speculate the execution, then
       // PRE should be prohibited.
-      auto It = FirstImplicitControlFlowInsts.find(CurrentBlock);
-      if (It != FirstImplicitControlFlowInsts.end()) {
-        assert(It->second->getParent() == CurrentBlock &&
-               "Implicit control flow map broken?");
-        if (OI->dominates(It->second, CurInst))
-          return false;
-      }
-    }
+      if (ICF->isDominatedByICFIFromSameBlock(CurInst))
 
     // Don't do PRE across indirect branch.
     if (isa<IndirectBrInst>(PREPred->getTerminator()))
       return false;
 
     // We can't do PRE safely on a critical edge, so instead we schedule
     // the edge to be split and perform the PRE the next time we iterate
     // on the function.
if (MD && Phi->getType()->isPtrOrPtrVectorTy())
     MD->invalidateCachedPointerInfo(Phi);
   VN.erase(CurInst);
   removeFromLeaderTable(ValNo, CurInst, CurrentBlock);
 
   LLVM_DEBUG(dbgs() << "GVN PRE removed: " << *CurInst << '\n');
   if (MD)
     MD->removeInstruction(CurInst);
   LLVM_DEBUG(verifyRemoved(CurInst));
-  bool InvalidateImplicitCF =
-      FirstImplicitControlFlowInsts.lookup(CurInst->getParent()) == CurInst;
   // FIXME: Intended to be markInstructionForDeletion(CurInst), but it causes
   // some assertion failures.
-  OI->invalidateBlock(CurrentBlock);
+  ICF->invalidateBlock(CurrentBlock);
   CurInst->eraseFromParent();
-  if (InvalidateImplicitCF)
-    fillImplicitControlFlowInfo(CurrentBlock);
   ++NumGVNInstr;
 
   return true;
 }
 
 /// Perform a purely local form of PRE that looks for diamond
 /// control flow patterns and attempts to perform simple PRE at the join point.
 bool GVN::performPRE(Function &F) {
bool GVN::iterateOnFunction(Function &F) {
   // Top-down walk of the dominator tree
   bool Changed = false;
   // Needed for value numbering with phi construction to work.
   // RPOT walks the graph in its constructor and will not be invalidated during
   // processBlock.
   ReversePostOrderTraversal<Function *> RPOT(&F);
 
   for (BasicBlock *BB : RPOT)
-    fillImplicitControlFlowInfo(BB);
-  for (BasicBlock *BB : RPOT)
     Changed |= processBlock(BB);
 
   return Changed;
 }
 
 void GVN::cleanupGlobalSets() {
   VN.clear();
   LeaderTable.clear();
   BlockRPONumber.clear();
   TableAllocator.Reset();
-  FirstImplicitControlFlowInsts.clear();
-}
-
-void
-GVN::fillImplicitControlFlowInfo(BasicBlock *BB) {
-  // Make sure that all marked instructions are actually deleted by this point,
-  // so that we don't need to care about omitting them.
-  assert(InstrsToErase.empty() && "Filling before removed all marked insns?");
-  auto MayNotTransferExecutionToSuccessor = [&](const Instruction *I) {
-    // If a block's instruction doesn't always pass the control to its successor
-    // instruction, mark the block as having implicit control flow. We use them
-    // to avoid wrong assumptions of sort "if A is executed and B post-dominates
-    // A, then B is also executed". This is not true is there is an implicit
-    // control flow instruction (e.g. a guard) between them.
-    //
-    // TODO: Currently, isGuaranteedToTransferExecutionToSuccessor returns false
-    // for volatile stores and loads because they can trap. The discussion on
-    // whether or not it is correct is still ongoing. We might want to get rid
-    // of this logic in the future. Anyways, trapping instructions shouldn't
-    // introduce implicit control flow, so we explicitly allow them here. This
-    // must be removed once isGuaranteedToTransferExecutionToSuccessor is fixed.
-    if (isGuaranteedToTransferExecutionToSuccessor(I))
-      return false;
-    if (isa<LoadInst>(I)) {
-      assert(cast<LoadInst>(I)->isVolatile() &&
-             "Non-volatile load should transfer execution to successor!");
-      return false;
-    }
-    if (isa<StoreInst>(I)) {
-      assert(cast<StoreInst>(I)->isVolatile() &&
-             "Non-volatile store should transfer execution to successor!");
-      return false;
-    }
-    return true;
-  };
-  FirstImplicitControlFlowInsts.erase(BB);
-
-  for (auto &I : *BB)
-    if (MayNotTransferExecutionToSuccessor(&I)) {
-      FirstImplicitControlFlowInsts[BB] = &I;
-      break;
-    }
+  ICF->clear();
 }
 
 /// Verify that the specified instruction does not occur in our
 /// internal data structures.
 void GVN::verifyRemoved(const Instruction *Inst) const {
   VN.verifyRemoved(Inst);
 
   // Walk through the value number scope to make sure the instruction isn't

llvm/trunk/lib/Transforms/Utils/CMakeLists.txt

add_llvm_library(LLVMTransformUtils
   DemoteRegToStack.cpp
   EntryExitInstrumenter.cpp
   EscapeEnumerator.cpp
   Evaluator.cpp
   FlattenCFG.cpp
   FunctionComparator.cpp
   FunctionImportUtils.cpp
   GlobalStatus.cpp
+  ImplicitControlFlowTracking.cpp
   InlineFunction.cpp
   ImportedFunctionsInliningStatistics.cpp
   InstructionNamer.cpp
   IntegerDivision.cpp
   LCSSA.cpp
   LibCallsShrinkWrap.cpp
   Local.cpp
   LoopRotationUtils.cpp

llvm/trunk/lib/Transforms/Utils/ImplicitControlFlowTracking.cpp

+//===-- ImplicitControlFlowTracking.cpp -------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// This class allows to keep track on instructions with implicit control flow.
+// These are instructions that may not pass execution to their successors. For
+// example, throwing calls and guards do not always do this. If we need to know
+// for sure that some instruction is guaranteed to execute if the given block
+// is reached, then we need to make sure that there is no implicit control flow
+// instruction (ICFI) preceeding it. For example, this check is required if we
+// perform PRE moving non-speculable instruction to other place.
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/ValueTracking.h"
+#include "llvm/Transforms/Utils/ImplicitControlFlowTracking.h"
+
+using namespace llvm;
+
+const Instruction *
+ImplicitControlFlowTracking::getFirstICFI(const BasicBlock *BB) {
+  if (!KnownBlocks.count(BB))
+    fill(BB);
+  return FirstImplicitControlFlowInsts.lookup(BB);
+}
+
+bool ImplicitControlFlowTracking::hasICF(const BasicBlock *BB) {
+  return getFirstICFI(BB) != nullptr;
+}
+
+bool ImplicitControlFlowTracking::isDominatedByICFIFromSameBlock(
+    const Instruction *Insn) {
+  const Instruction *MaybeFirstICF = getFirstICFI(Insn->getParent());
+  return MaybeFirstICF && OI.dominates(MaybeFirstICF, Insn);
+}
+
+void ImplicitControlFlowTracking::fill(const BasicBlock *BB) {
+  auto MayNotTransferExecutionToSuccessor = [&](const Instruction *I) {
+    // If a block's instruction doesn't always pass the control to its successor
+    // instruction, mark the block as having implicit control flow. We use them
+    // to avoid wrong assumptions of sort "if A is executed and B post-dominates
+    // A, then B is also executed". This is not true is there is an implicit
+    // control flow instruction (e.g. a guard) between them.
+    //
+    // TODO: Currently, isGuaranteedToTransferExecutionToSuccessor returns false
+    // for volatile stores and loads because they can trap. The discussion on
+    // whether or not it is correct is still ongoing. We might want to get rid
+    // of this logic in the future. Anyways, trapping instructions shouldn't
+    // introduce implicit control flow, so we explicitly allow them here. This
+    // must be removed once isGuaranteedToTransferExecutionToSuccessor is fixed.
+    if (isGuaranteedToTransferExecutionToSuccessor(I))
+      return false;
+    if (isa<LoadInst>(I)) {
+      assert(cast<LoadInst>(I)->isVolatile() &&
+             "Non-volatile load should transfer execution to successor!");
+      return false;
+    }
+    if (isa<StoreInst>(I)) {
+      assert(cast<StoreInst>(I)->isVolatile() &&
+             "Non-volatile store should transfer execution to successor!");
+      return false;
+    }
+    return true;
+  };
+  FirstImplicitControlFlowInsts.erase(BB);
+
+  for (auto &I : *BB)
+    if (MayNotTransferExecutionToSuccessor(&I)) {
+      FirstImplicitControlFlowInsts[BB] = &I;
+      break;
+    }
+
+  // Mark this block as having a known result.
+  KnownBlocks.insert(BB);
+}
+
+void ImplicitControlFlowTracking::invalidateBlock(const BasicBlock *BB) {
+  OI.invalidateBlock(BB);
+  FirstImplicitControlFlowInsts.erase(BB);
+  KnownBlocks.erase(BB);
+}
+
+void ImplicitControlFlowTracking::clear() {
+  for (auto It : FirstImplicitControlFlowInsts)
+    OI.invalidateBlock(It.first);
+  FirstImplicitControlFlowInsts.clear();
+  KnownBlocks.clear();
+}