[NFC] Split logic of ImplicitControlFlowTracking to allow generalization

[mkazantsev]

Summary

We have a class ImplicitControlFlowTracking which allows us to keep track of
instructions that can abnormally exit and answer queries like "whether or not
there is side-exiting instruction above this instruction in its block".

We may want to have the similar tracking for other types of "special" instructions,
for example instructions that write memory.

This patch separates ImplicitControlFlowTracking into two classes, isolating all
general logic not related to implicit control flow into its parent class. We can
later make another child of this class to keep track of instructions that write
memory.

The motivation for that is that we want to make these checks efficiently in the
patch https://reviews.llvm.org/D50891.

[fedor.sergeev]

'Precedence' seems to be a rather overloaded term. "Instruction precedence" seems to be sufficiently close to "operator precedence", so I would select a different term here.
Say, "InstructionFlowTracking".

Otherwise, LGTM.

include/llvm/Transforms/Utils/InstructionPrecedenceTracking.h

17

This comment makes an impression that invalidation happens automatically.
Rephrase to something like "and to *manually* invalidate the cached data *after* the block's content has been changed".

[mkazantsev]

I don't really like the name InstructionPrecedenceTracking, but other options don't sound good to mee too. I'm going to merge it as is (with comment fix) and just rename it in future when/if we find a better word for this.

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/ImplicitControlFlowTracking.h"
+#include "llvm/Transforms/Utils/InstructionPrecedenceTracking.h"
 #include <cstdint>
 #include <utility>
 #include <vector>
 
 namespace llvm {
 
 class AssumptionCache;
 class BasicBlock;

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

include/llvm/Transforms/Utils/InstructionPrecedenceTracking.h

+//===-- InstructionPrecedenceTracking.h -------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// Implements a class that is able to define some instructions as "special"
+// (e.g. as having implicit control flow, or writing memory, or having another
+// interesting property) and then efficiently answers queries of the types:
+// 1. Are there any special instructions in the block of interest?
+// 2. Return first of the special instructions in the given block;
+// 3. Check if the given instruction is preceeded by the first special
+//    instruction in the same block.
+// The class provides caching that allows to answer these queries quickly and
+// invalidate the cached data whenever the block's content has been changed.
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_UTILS_INSTRUCTIONPRECEDENCETRACKING_H
+#define LLVM_TRANSFORMS_UTILS_INSTRUCTIONPRECEDENCETRACKING_H
+
+#include "llvm/IR/Dominators.h"
+#include "llvm/Transforms/Utils/OrderedInstructions.h"
+
+namespace llvm {
+
+class InstructionPrecedenceTracking {
+  // Maps a block to the topmost special instruction in it.
+  DenseMap<const BasicBlock *, const Instruction *>
+      FirstImplicitControlFlowInsts;
+  // Allows to answer queries about precedence of instructions within one block.
+  OrderedInstructions OI;
+  // Blocks for which we have the up-to-date cached information.
+  SmallPtrSet<const BasicBlock *, 8> KnownBlocks;
+
+  // Fills information about the given block's special instructions.
+  void fill(const BasicBlock *BB);
+
+protected:
+  InstructionPrecedenceTracking(DominatorTree *DT)
+      : OI(OrderedInstructions(DT)) {}
+
+  /// Returns the topmost special instruction from the block \p BB. Returns
+  /// nullptr if there is no special instructions in the block.
+  const Instruction *getFirstSpecialInstruction(const BasicBlock *BB);
+
+  /// Returns true iff at least one instruction from the basic block \p BB is
+  /// special.
+  bool hasSpecialInstructions(const BasicBlock *BB);
+
+  /// Returns true iff the first special instruction of \p Insn's block exists
+  /// and dominates \p Insn.
+  bool isPreceededBySpecialInstruction(const Instruction *Insn);
+
+  /// A predicate that defines whether or not the instruction \p Insn is
+  /// considered special and needs to be tracked. Implementing this method in
+  /// children classes allows to implement tracking of implicit control flow,
+  /// memory writing instructions or any other kinds of instructions we might
+  /// be interested in.
+  virtual bool isSpecialInstruction(const Instruction *Insn) const = 0;
+
+public:
+  /// Clears cached information about this particular block.
+  void invalidateBlock(const BasicBlock *BB);
+
+  /// Invalidates all information from this tracking.
+  void clear();
+};
+
+/// 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.
+class ImplicitControlFlowTracking : public InstructionPrecedenceTracking {
+public:
+  ImplicitControlFlowTracking(DominatorTree *DT)
+      : InstructionPrecedenceTracking(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) {
+    return getFirstSpecialInstruction(BB);
+  }
+
+  /// Returns true if at least one instruction from the given basic block has
+  /// implicit control flow.
+  bool hasICF(const BasicBlock *BB) {
+    return hasSpecialInstructions(BB);
+  }
+
+  /// Returns true if the first ICFI of Insn's block exists and dominates Insn.
+  bool isDominatedByICFIFromSameBlock(const Instruction *Insn) {
+    return isPreceededBySpecialInstruction(Insn);
+  }
+
+  virtual bool isSpecialInstruction(const Instruction *Insn) const;
+};
+
+} // llvm
+
+#endif // LLVM_TRANSFORMS_UTILS_INSTRUCTIONPRECEDENCETRACKING_H

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
+  InstructionPrecedenceTracking.cpp
   IntegerDivision.cpp
   LCSSA.cpp
   LibCallsShrinkWrap.cpp
   Local.cpp
   LoopRotationUtils.cpp
   LoopSimplify.cpp
   LoopUnroll.cpp
   LoopUnrollAndJam.cpp

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);
-  auto *FirstICF = FirstImplicitControlFlowInsts.lookup(BB);
-  assert((!FirstICF || FirstICF->getParent() == BB) && "Inconsistent cache!");
-  return FirstICF;
-}
-
-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();
-}

lib/Transforms/Utils/InstructionPrecedenceTracking.cpp

+//===-- InstructionPrecedenceTracking.cpp -----------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// Implements a class that is able to define some instructions as "special"
+// (e.g. as having implicit control flow, or writing memory, or having another
+// interesting property) and then efficiently answers queries of the types:
+// 1. Are there any special instructions in the block of interest?
+// 2. Return first of the special instructions in the given block;
+// 3. Check if the given instruction is preceeded by the first special
+//    instruction in the same block.
+// The class provides caching that allows to answer these queries quickly and
+// invalidate the cached data whenever the block's content has been changed.
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/ValueTracking.h"
+#include "llvm/Transforms/Utils/InstructionPrecedenceTracking.h"
+
+using namespace llvm;
+
+const Instruction *InstructionPrecedenceTracking::getFirstSpecialInstruction(
+    const BasicBlock *BB) {
+  if (!KnownBlocks.count(BB))
+    fill(BB);
+  auto *FirstICF = FirstImplicitControlFlowInsts.lookup(BB);
+  assert((!FirstICF || FirstICF->getParent() == BB) && "Inconsistent cache!");
+  return FirstICF;
+}
+
+bool InstructionPrecedenceTracking::hasSpecialInstructions(
+    const BasicBlock *BB) {
+  return getFirstSpecialInstruction(BB) != nullptr;
+}
+
+bool InstructionPrecedenceTracking::isPreceededBySpecialInstruction(
+    const Instruction *Insn) {
+  const Instruction *MaybeFirstICF =
+      getFirstSpecialInstruction(Insn->getParent());
+  return MaybeFirstICF && OI.dominates(MaybeFirstICF, Insn);
+}
+
+void InstructionPrecedenceTracking::fill(const BasicBlock *BB) {
+  FirstImplicitControlFlowInsts.erase(BB);
+  for (auto &I : *BB)
+    if (isSpecialInstruction(&I)) {
+      FirstImplicitControlFlowInsts[BB] = &I;
+      break;
+    }
+
+  // Mark this block as having a known result.
+  KnownBlocks.insert(BB);
+}
+
+void InstructionPrecedenceTracking::invalidateBlock(const BasicBlock *BB) {
+  OI.invalidateBlock(BB);
+  FirstImplicitControlFlowInsts.erase(BB);
+  KnownBlocks.erase(BB);
+}
+
+void InstructionPrecedenceTracking::clear() {
+  for (auto It : FirstImplicitControlFlowInsts)
+    OI.invalidateBlock(It.first);
+  FirstImplicitControlFlowInsts.clear();
+  KnownBlocks.clear();
+}
+
+bool ImplicitControlFlowTracking::isSpecialInstruction(
+    const Instruction *Insn) const {
+  // 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(Insn))
+    return false;
+  if (isa<LoadInst>(Insn)) {
+    assert(cast<LoadInst>(Insn)->isVolatile() &&
+           "Non-volatile load should transfer execution to successor!");
+    return false;
+  }
+  if (isa<StoreInst>(Insn)) {
+    assert(cast<StoreInst>(Insn)->isVolatile() &&
+           "Non-volatile store should transfer execution to successor!");
+    return false;
+  }
+  return true;
+}