Index: llvm/trunk/include/llvm/Transforms/Scalar/GVN.h =================================================================== --- llvm/trunk/include/llvm/Transforms/Scalar/GVN.h +++ llvm/trunk/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/OrderedInstructions.h" +#include "llvm/Transforms/Utils/ImplicitControlFlowTracking.h" #include #include #include @@ -158,11 +158,8 @@ AssumptionCache *AC; SetVector DeadBlocks; OptimizationRemarkEmitter *ORE; - // Maps a block to the topmost instruction with implicit control flow in it. - DenseMap - FirstImplicitControlFlowInsts; + ImplicitControlFlowTracking *ICF; - OrderedInstructions *OI; ValueTable VN; /// A mapping from value numbers to lists of Value*'s that Index: llvm/trunk/include/llvm/Transforms/Utils/ImplicitControlFlowTracking.h =================================================================== --- llvm/trunk/include/llvm/Transforms/Utils/ImplicitControlFlowTracking.h +++ llvm/trunk/include/llvm/Transforms/Utils/ImplicitControlFlowTracking.h @@ -0,0 +1,62 @@ +//===-- 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: llvm/trunk/lib/Transforms/Scalar/GVN.cpp =================================================================== --- llvm/trunk/lib/Transforms/Scalar/GVN.cpp +++ llvm/trunk/lib/Transforms/Scalar/GVN.cpp @@ -1075,15 +1075,8 @@ // 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)) + return false; while (TmpBB->getSinglePredecessor()) { TmpBB = TmpBB->getSinglePredecessor(); if (TmpBB == LoadBB) // Infinite (unreachable) loop. @@ -1100,8 +1093,7 @@ 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; } @@ -2021,8 +2013,8 @@ TLI = &RunTLI; VN.setAliasAnalysis(&RunAA); MD = RunMD; - OrderedInstructions OrderedInstrs(DT); - OI = &OrderedInstrs; + ImplicitControlFlowTracking ImplicitCFT(DT); + ICF = &ImplicitCFT; VN.setMemDep(MD); ORE = RunORE; @@ -2106,8 +2098,7 @@ 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'); @@ -2116,17 +2107,14 @@ 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(); @@ -2270,13 +2258,8 @@ // 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)) + return false; } // Don't do PRE across indirect branch. @@ -2337,14 +2320,10 @@ 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; @@ -2413,8 +2392,6 @@ ReversePostOrderTraversal RPOT(&F); for (BasicBlock *BB : RPOT) - fillImplicitControlFlowInfo(BB); - for (BasicBlock *BB : RPOT) Changed |= processBlock(BB); return Changed; @@ -2425,48 +2402,7 @@ 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(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; - } + ICF->clear(); } /// Verify that the specified instruction does not occur in our Index: llvm/trunk/lib/Transforms/Utils/CMakeLists.txt =================================================================== --- llvm/trunk/lib/Transforms/Utils/CMakeLists.txt +++ llvm/trunk/lib/Transforms/Utils/CMakeLists.txt @@ -18,6 +18,7 @@ FunctionComparator.cpp FunctionImportUtils.cpp GlobalStatus.cpp + ImplicitControlFlowTracking.cpp InlineFunction.cpp ImportedFunctionsInliningStatistics.cpp InstructionNamer.cpp Index: llvm/trunk/lib/Transforms/Utils/ImplicitControlFlowTracking.cpp =================================================================== --- llvm/trunk/lib/Transforms/Utils/ImplicitControlFlowTracking.cpp +++ llvm/trunk/lib/Transforms/Utils/ImplicitControlFlowTracking.cpp @@ -0,0 +1,91 @@ +//===-- 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(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(); +}