Index: include/llvm/Transforms/Scalar/GVN.h =================================================================== --- include/llvm/Transforms/Scalar/GVN.h +++ include/llvm/Transforms/Scalar/GVN.h @@ -28,7 +28,7 @@ #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 #include #include Index: include/llvm/Transforms/Utils/ImplicitControlFlowTracking.h =================================================================== --- include/llvm/Transforms/Utils/ImplicitControlFlowTracking.h +++ /dev/null @@ -1,62 +0,0 @@ -//===-- 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 - FirstImplicitControlFlowInsts; - OrderedInstructions OI; - // Blocks for which we have the actual information. - SmallPtrSet KnownBlocks; -}; - -} // llvm - -#endif // LLVM_TRANSFORMS_UTILS_IMPLICITCONTROLFLOWTRACKING_H Index: include/llvm/Transforms/Utils/InstructionPrecedenceTracking.h =================================================================== --- /dev/null +++ include/llvm/Transforms/Utils/InstructionPrecedenceTracking.h @@ -0,0 +1,105 @@ +//===-- 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 + 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 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 Index: lib/Transforms/Utils/CMakeLists.txt =================================================================== --- lib/Transforms/Utils/CMakeLists.txt +++ lib/Transforms/Utils/CMakeLists.txt @@ -18,10 +18,10 @@ FunctionComparator.cpp FunctionImportUtils.cpp GlobalStatus.cpp - ImplicitControlFlowTracking.cpp InlineFunction.cpp ImportedFunctionsInliningStatistics.cpp InstructionNamer.cpp + InstructionPrecedenceTracking.cpp IntegerDivision.cpp LCSSA.cpp LibCallsShrinkWrap.cpp Index: lib/Transforms/Utils/ImplicitControlFlowTracking.cpp =================================================================== --- lib/Transforms/Utils/ImplicitControlFlowTracking.cpp +++ /dev/null @@ -1,93 +0,0 @@ -//===-- 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(I)) { - assert(cast(I)->isVolatile() && - "Non-volatile load should transfer execution to successor!"); - return false; - } - if (isa(I)) { - assert(cast(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(); -} Index: lib/Transforms/Utils/InstructionPrecedenceTracking.cpp =================================================================== --- /dev/null +++ lib/Transforms/Utils/InstructionPrecedenceTracking.cpp @@ -0,0 +1,98 @@ +//===-- 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(Insn)) { + assert(cast(Insn)->isVolatile() && + "Non-volatile load should transfer execution to successor!"); + return false; + } + if (isa(Insn)) { + assert(cast(Insn)->isVolatile() && + "Non-volatile store should transfer execution to successor!"); + return false; + } + return true; +}