[NFC] Move OrderedInstructions and InstructionPrecedenceTracking to Analysis

These classes don't make any changes to IR and have no reason to be in
Transform/Utils. This patch moves them to Analysis folder. This will allow
us reusing these classes in some analyzes, like MustExecute.

llvm-svn: 341015

3 files changed, 152 insertions, 0 deletions

diff --git a/llvm/lib/Analysis/CMakeLists.txt b/llvm/lib/Analysis/CMakeLists.txt
index eb0526c5dce..6a228e85aa8 100644
--- a/llvm/lib/Analysis/CMakeLists.txt
+++ b/llvm/lib/Analysis/CMakeLists.txt
@@ -35,6 +35,7 @@ add_llvm_library(LLVMAnalysis
   IndirectCallPromotionAnalysis.cpp
   InlineCost.cpp
   InstCount.cpp
+  InstructionPrecedenceTracking.cpp
   InstructionSimplify.cpp
   Interval.cpp
   IntervalPartition.cpp
@@ -65,6 +66,7 @@ add_llvm_library(LLVMAnalysis
   ObjCARCInstKind.cpp
   OptimizationRemarkEmitter.cpp
   OrderedBasicBlock.cpp
+  OrderedInstructions.cpp
   PHITransAddr.cpp
   PhiValues.cpp
   PostDominators.cpp
diff --git a/llvm/lib/Analysis/InstructionPrecedenceTracking.cpp b/llvm/lib/Analysis/InstructionPrecedenceTracking.cpp
new file mode 100644
index 00000000000..7294e121507
--- /dev/null
+++ b/llvm/lib/Analysis/InstructionPrecedenceTracking.cpp
@@ -0,0 +1,99 @@
+//===-- 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. The
+// user must make sure that the cached data is invalidated properly whenever
+// a content of some tracked block is changed.
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/InstructionPrecedenceTracking.h"
+#include "llvm/Analysis/ValueTracking.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;
+}
diff --git a/llvm/lib/Analysis/OrderedInstructions.cpp b/llvm/lib/Analysis/OrderedInstructions.cpp
new file mode 100644
index 00000000000..7b155208c02
--- /dev/null
+++ b/llvm/lib/Analysis/OrderedInstructions.cpp
@@ -0,0 +1,51 @@
+//===-- 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/Analysis/OrderedInstructions.h"
+using namespace llvm;
+
+bool OrderedInstructions::localDominates(const Instruction *InstA,
+                                         const Instruction *InstB) const {
+  assert(InstA->getParent() == InstB->getParent() &&
+         "Instructions must be in the same basic block");
+
+  const BasicBlock *IBB = InstA->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);
+}
+
+/// 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 {
+  // Use ordered basic block to do dominance check in case the 2 instructions
+  // are in the same basic block.
+  if (InstA->getParent() == InstB->getParent())
+    return localDominates(InstA, InstB);
+  return DT->dominates(InstA->getParent(), InstB->getParent());
+}
+
+bool OrderedInstructions::dfsBefore(const Instruction *InstA,
+                                    const Instruction *InstB) const {
+  // Use ordered basic block in case the 2 instructions are in the same basic
+  // block.
+  if (InstA->getParent() == InstB->getParent())
+    return localDominates(InstA, InstB);
+
+  DomTreeNode *DA = DT->getNode(InstA->getParent());
+  DomTreeNode *DB = DT->getNode(InstB->getParent());
+  return DA->getDFSNumIn() < DB->getDFSNumIn();
+}