[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

4 files changed, 0 insertions, 153 deletions

diff --git a/llvm/lib/Transforms/Utils/CMakeLists.txt b/llvm/lib/Transforms/Utils/CMakeLists.txt
index 3dd5fe81166..eb3bad79129 100644
--- a/llvm/lib/Transforms/Utils/CMakeLists.txt
+++ b/llvm/lib/Transforms/Utils/CMakeLists.txt
@@ -22,7 +22,6 @@ add_llvm_library(LLVMTransformUtils
   InlineFunction.cpp
   ImportedFunctionsInliningStatistics.cpp
   InstructionNamer.cpp
-  InstructionPrecedenceTracking.cpp
   IntegerDivision.cpp
   LCSSA.cpp
   LibCallsShrinkWrap.cpp
@@ -42,7 +41,6 @@ add_llvm_library(LLVMTransformUtils
   MetaRenamer.cpp
   ModuleUtils.cpp
   NameAnonGlobals.cpp
-  OrderedInstructions.cpp
   PredicateInfo.cpp
   PromoteMemoryToRegister.cpp
   StripGCRelocates.cpp
diff --git a/llvm/lib/Transforms/Utils/InstructionPrecedenceTracking.cpp b/llvm/lib/Transforms/Utils/InstructionPrecedenceTracking.cpp
deleted file mode 100644
index a3817c29551..00000000000
--- a/llvm/lib/Transforms/Utils/InstructionPrecedenceTracking.cpp
+++ /dev/null
@@ -1,99 +0,0 @@
-//===-- 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/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;
-}
diff --git a/llvm/lib/Transforms/Utils/OrderedInstructions.cpp b/llvm/lib/Transforms/Utils/OrderedInstructions.cpp
deleted file mode 100644
index 6d0b96f6aa8..00000000000
--- a/llvm/lib/Transforms/Utils/OrderedInstructions.cpp
+++ /dev/null
@@ -1,51 +0,0 @@
-//===-- 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"
-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();
-}
diff --git a/llvm/lib/Transforms/Utils/PredicateInfo.cpp b/llvm/lib/Transforms/Utils/PredicateInfo.cpp
index 2923977b791..e56ccef1289 100644
--- a/llvm/lib/Transforms/Utils/PredicateInfo.cpp
+++ b/llvm/lib/Transforms/Utils/PredicateInfo.cpp
@@ -35,7 +35,6 @@
 #include "llvm/Support/DebugCounter.h"
 #include "llvm/Support/FormattedStream.h"
 #include "llvm/Transforms/Utils.h"
-#include "llvm/Transforms/Utils/OrderedInstructions.h"
 #include <algorithm>
 #define DEBUG_TYPE "predicateinfo"
 using namespace llvm;