diff --git a/llvm/include/llvm/Analysis/OrderedInstructions.h b/llvm/include/llvm/Analysis/OrderedInstructions.h deleted file mode 100644 --- a/llvm/include/llvm/Analysis/OrderedInstructions.h +++ /dev/null @@ -1,58 +0,0 @@ -//===- llvm/Transforms/Utils/OrderedInstructions.h -------------*- C++ -*-===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// -// -// This file defines an efficient way to check for dominance relation between 2 -// instructions. -// -// FIXME: This is really just a convenience wrapper to check dominance between -// two arbitrary instructions in different basic blocks. We should fold it into -// DominatorTree, which is the more widely used interface. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_ANALYSIS_ORDEREDINSTRUCTIONS_H -#define LLVM_ANALYSIS_ORDEREDINSTRUCTIONS_H - -#include "llvm/ADT/DenseMap.h" -#include "llvm/IR/Dominators.h" -#include "llvm/IR/Operator.h" - -namespace llvm { - -class OrderedInstructions { - /// The dominator tree of the parent function. - DominatorTree *DT; - - /// Return true if the first instruction comes before the second in the - /// same basic block. It will create an ordered basic block, if it does - /// not yet exist in OBBMap. - bool localDominates(const Instruction *, const Instruction *) const; - -public: - /// Constructor. - OrderedInstructions(DominatorTree *DT) : DT(DT) {} - - /// Return true if first instruction dominates the second. - bool dominates(const Instruction *, const Instruction *) const; - - /// Return true if the first instruction comes before the second in the - /// dominator tree DFS traversal if they are in different basic blocks, - /// or if the first instruction comes before the second in the same basic - /// block. - bool dfsBefore(const Instruction *, const Instruction *) const; - - // Return true if the first instruction comes before the second in the - // dominator tree BFS traversal based on the level number of nodes in - // dominator tree if they are in different basic blocks else if the first - // instruction comes before the second in the same basic block - bool bfsLevelBefore(const Instruction *, const Instruction *) const; -}; - -} // end namespace llvm - -#endif // LLVM_ANALYSIS_ORDEREDINSTRUCTIONS_H diff --git a/llvm/include/llvm/Transforms/Utils/CodeMoverUtils.h b/llvm/include/llvm/Transforms/Utils/CodeMoverUtils.h --- a/llvm/include/llvm/Transforms/Utils/CodeMoverUtils.h +++ b/llvm/include/llvm/Transforms/Utils/CodeMoverUtils.h @@ -22,6 +22,16 @@ class Instruction; class PostDominatorTree; +class OrderedInstructions { + DominatorTree *DT; + bool localDominates(const Instruction *, const Instruction *) const; + +public: + OrderedInstructions(DominatorTree *DT) : DT(DT) {} + bool dominates(const Instruction *, const Instruction *) const; + bool domTreeLevelBefore(const Instruction *, const Instruction *) const; +}; + /// Return true if \p I0 and \p I1 are control flow equivalent. /// Two instructions are control flow equivalent if their basic blocks are /// control flow equivalent. diff --git a/llvm/lib/Analysis/CMakeLists.txt b/llvm/lib/Analysis/CMakeLists.txt --- a/llvm/lib/Analysis/CMakeLists.txt +++ b/llvm/lib/Analysis/CMakeLists.txt @@ -74,7 +74,6 @@ ObjCARCAnalysisUtils.cpp ObjCARCInstKind.cpp OptimizationRemarkEmitter.cpp - OrderedInstructions.cpp PHITransAddr.cpp PhiValues.cpp PostDominators.cpp diff --git a/llvm/lib/Analysis/OrderedInstructions.cpp b/llvm/lib/Analysis/OrderedInstructions.cpp deleted file mode 100644 --- a/llvm/lib/Analysis/OrderedInstructions.cpp +++ /dev/null @@ -1,57 +0,0 @@ -//===-- OrderedInstructions.cpp - Instruction dominance function ---------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// -// -// 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"); - - return InstA->comesBefore(InstB); -} - -/// Given 2 instructions, 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(); -} - -bool OrderedInstructions::bfsLevelBefore(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->getLevel() < DB->getLevel(); -} diff --git a/llvm/lib/Transforms/Utils/CodeMoverUtils.cpp b/llvm/lib/Transforms/Utils/CodeMoverUtils.cpp --- a/llvm/lib/Transforms/Utils/CodeMoverUtils.cpp +++ b/llvm/lib/Transforms/Utils/CodeMoverUtils.cpp @@ -15,7 +15,6 @@ #include "llvm/ADT/Optional.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/DependenceAnalysis.h" -#include "llvm/Analysis/OrderedInstructions.h" #include "llvm/Analysis/PostDominators.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/Dominators.h" @@ -94,6 +93,32 @@ }; } // namespace +bool OrderedInstructions::localDominates(const Instruction *InstA, + const Instruction *InstB) const { + assert(InstA->getParent() == InstB->getParent() && + "Instructions must be in the same basic block"); + + return InstA->comesBefore(InstB); +} +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::domTreeLevelBefore(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()); +} + const Optional ControlConditions::collectControlConditions( const BasicBlock &BB, const BasicBlock &Dominator, const DominatorTree &DT, const PostDominatorTree &PDT, unsigned MaxLookup) { @@ -330,7 +355,7 @@ OrderedInstructions OI(&DT); DT.updateDFSNumbers(); - const bool MoveForward = OI.bfsLevelBefore(&I, &InsertPoint); + const bool MoveForward = OI.domTreeLevelBefore(&I, &InsertPoint); Instruction &StartInst = (MoveForward ? I : InsertPoint); Instruction &EndInst = (MoveForward ? InsertPoint : I); SmallPtrSet InstsToCheck; diff --git a/llvm/unittests/Analysis/CMakeLists.txt b/llvm/unittests/Analysis/CMakeLists.txt --- a/llvm/unittests/Analysis/CMakeLists.txt +++ b/llvm/unittests/Analysis/CMakeLists.txt @@ -27,7 +27,6 @@ LoopNestTest.cpp MemoryBuiltinsTest.cpp MemorySSATest.cpp - OrderedInstructionsTest.cpp PhiValuesTest.cpp ProfileSummaryInfoTest.cpp ScalarEvolutionTest.cpp diff --git a/llvm/unittests/Analysis/OrderedInstructionsTest.cpp b/llvm/unittests/Analysis/OrderedInstructionsTest.cpp deleted file mode 100644 --- a/llvm/unittests/Analysis/OrderedInstructionsTest.cpp +++ /dev/null @@ -1,64 +0,0 @@ -//===- OrderedInstructions.cpp - Unit tests for OrderedInstructions ------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -#include "llvm/Analysis/OrderedInstructions.h" -#include "llvm/IR/BasicBlock.h" -#include "llvm/IR/Dominators.h" -#include "llvm/IR/IRBuilder.h" -#include "llvm/IR/Instructions.h" -#include "llvm/IR/LLVMContext.h" -#include "llvm/IR/Module.h" -#include "gtest/gtest.h" - -using namespace llvm; - -/// Check intra-basicblock and inter-basicblock dominance using -/// OrderedInstruction. -TEST(OrderedInstructionsTest, DominanceTest) { - LLVMContext Ctx; - Module M("test", Ctx); - IRBuilder<> B(Ctx); - FunctionType *FTy = - FunctionType::get(Type::getVoidTy(Ctx), {B.getInt8PtrTy()}, false); - Function *F = Function::Create(FTy, Function::ExternalLinkage, "f", M); - - // Create the function as follow and check for dominance relation. - // - // test(): - // bbx: - // loadx; - // loady; - // bby: - // loadz; - // return; - // - // More specifically, check for loadx -> (dominates) loady, - // loady -> loadx and loady -> loadz. - // - // Create BBX with 2 loads. - BasicBlock *BBX = BasicBlock::Create(Ctx, "bbx", F); - B.SetInsertPoint(BBX); - Argument *PointerArg = &*F->arg_begin(); - LoadInst *LoadInstX = B.CreateLoad(B.getInt8Ty(), PointerArg); - LoadInst *LoadInstY = B.CreateLoad(B.getInt8Ty(), PointerArg); - - // Create BBY with 1 load. - BasicBlock *BBY = BasicBlock::Create(Ctx, "bby", F); - B.SetInsertPoint(BBY); - LoadInst *LoadInstZ = B.CreateLoad(B.getInt8Ty(), PointerArg); - B.CreateRet(LoadInstZ); - std::unique_ptr DT(new DominatorTree(*F)); - OrderedInstructions OI(&*DT); - - // Intra-BB dominance test. - EXPECT_TRUE(OI.dominates(LoadInstX, LoadInstY)); - EXPECT_FALSE(OI.dominates(LoadInstY, LoadInstX)); - - // Inter-BB dominance test. - EXPECT_TRUE(OI.dominates(LoadInstY, LoadInstZ)); -} diff --git a/llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp b/llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp --- a/llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp +++ b/llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp @@ -649,3 +649,46 @@ EXPECT_FALSE(isSafeToMoveBefore(*SubInst, *AddInst, DT, PDT, DI)); }); } +TEST(CodeMoverUtils, DominanceTest) { + LLVMContext Ctx; + Module M("test", Ctx); + IRBuilder<> B(Ctx); + FunctionType *FTy = + FunctionType::get(Type::getVoidTy(Ctx), {B.getInt8PtrTy()}, false); + Function *F = Function::Create(FTy, Function::ExternalLinkage, "f", M); + + // Create the function as follow and check for dominance relation. + // + // test(): + // bbx: + // loadx; + // loady; + // bby: + // loadz; + // return; + // + // More specifically, check for loadx -> (dominates) loady, + // loady -> loadx and loady -> loadz. + // + // Create BBX with 2 loads. + BasicBlock *BBX = BasicBlock::Create(Ctx, "bbx", F); + B.SetInsertPoint(BBX); + Argument *PointerArg = &*F->arg_begin(); + LoadInst *LoadInstX = B.CreateLoad(B.getInt8Ty(), PointerArg); + LoadInst *LoadInstY = B.CreateLoad(B.getInt8Ty(), PointerArg); + + // Create BBY with 1 load. + BasicBlock *BBY = BasicBlock::Create(Ctx, "bby", F); + B.SetInsertPoint(BBY); + LoadInst *LoadInstZ = B.CreateLoad(B.getInt8Ty(), PointerArg); + B.CreateRet(LoadInstZ); + std::unique_ptr DT(new DominatorTree(*F)); + OrderedInstructions OI(&*DT); + + // Intra-BB dominance test. + EXPECT_TRUE(OI.dominates(LoadInstX, LoadInstY)); + EXPECT_FALSE(OI.dominates(LoadInstY, LoadInstX)); + + // Inter-BB dominance test. + EXPECT_TRUE(OI.dominates(LoadInstY, LoadInstZ)); +} diff --git a/llvm/utils/gn/secondary/llvm/lib/Analysis/BUILD.gn b/llvm/utils/gn/secondary/llvm/lib/Analysis/BUILD.gn --- a/llvm/utils/gn/secondary/llvm/lib/Analysis/BUILD.gn +++ b/llvm/utils/gn/secondary/llvm/lib/Analysis/BUILD.gn @@ -87,7 +87,6 @@ "ObjCARCAnalysisUtils.cpp", "ObjCARCInstKind.cpp", "OptimizationRemarkEmitter.cpp", - "OrderedInstructions.cpp", "PHITransAddr.cpp", "PhiValues.cpp", "PostDominators.cpp", diff --git a/llvm/utils/gn/secondary/llvm/unittests/Analysis/BUILD.gn b/llvm/utils/gn/secondary/llvm/unittests/Analysis/BUILD.gn --- a/llvm/utils/gn/secondary/llvm/unittests/Analysis/BUILD.gn +++ b/llvm/utils/gn/secondary/llvm/unittests/Analysis/BUILD.gn @@ -29,7 +29,6 @@ "LoopNestTest.cpp", "MemoryBuiltinsTest.cpp", "MemorySSATest.cpp", - "OrderedInstructionsTest.cpp", "PhiValuesTest.cpp", "ProfileSummaryInfoTest.cpp", "ScalarEvolutionTest.cpp",