From fe0d5f970c77600e023aea44ae8b7d70b45faed2 Mon Sep 17 00:00:00 2001 From: Daniel Berlin Date: Thu, 29 Jun 2017 17:01:14 +0000 Subject: [PATCH] PredicateInfo: Use OrderedInstructions instead of our homemade version. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@306703 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Transforms/Utils/PredicateInfo.h | 8 +- lib/Transforms/Utils/PredicateInfo.cpp | 78 +++++++------------ 2 files changed, 31 insertions(+), 55 deletions(-) diff --git a/include/llvm/Transforms/Utils/PredicateInfo.h b/include/llvm/Transforms/Utils/PredicateInfo.h index 1322c686eb9..fc6f2c2118e 100644 --- a/include/llvm/Transforms/Utils/PredicateInfo.h +++ b/include/llvm/Transforms/Utils/PredicateInfo.h @@ -74,6 +74,7 @@ #include "llvm/Support/Casting.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/ErrorHandling.h" +#include "llvm/Transforms/Utils/OrderedInstructions.h" #include #include #include @@ -89,7 +90,6 @@ class Instruction; class MemoryAccess; class LLVMContext; class raw_ostream; -class OrderedBasicBlock; enum PredicateType { PT_Branch, PT_Assume, PT_Switch }; @@ -115,7 +115,8 @@ class PredicateWithCondition : public PredicateBase { public: Value *Condition; static inline bool classof(const PredicateBase *PB) { - return PB->Type == PT_Assume || PB->Type == PT_Branch || PB->Type == PT_Switch; + return PB->Type == PT_Assume || PB->Type == PT_Branch || + PB->Type == PT_Switch; } protected: @@ -244,6 +245,7 @@ private: Function &F; DominatorTree &DT; AssumptionCache &AC; + OrderedInstructions OI; // This maps from copy operands to Predicate Info. Note that it does not own // the Predicate Info, they belong to the ValueInfo structs in the ValueInfos // vector. @@ -256,8 +258,6 @@ private: // 0 is not a valid Value Info index, you can use DenseMap::lookup and tell // whether it returned a valid result. DenseMap ValueInfoNums; - // OrderedBasicBlocks used during sorting uses - DenseMap> OBBMap; // The set of edges along which we can only handle phi uses, due to critical // edges. DenseSet> EdgeUsesOnly; diff --git a/lib/Transforms/Utils/PredicateInfo.cpp b/lib/Transforms/Utils/PredicateInfo.cpp index 1260e35e934..da4a2cb0a1b 100644 --- a/lib/Transforms/Utils/PredicateInfo.cpp +++ b/lib/Transforms/Utils/PredicateInfo.cpp @@ -34,6 +34,7 @@ #include "llvm/Support/DebugCounter.h" #include "llvm/Support/FormattedStream.h" #include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/Utils/OrderedInstructions.h" #include #define DEBUG_TYPE "predicateinfo" using namespace llvm; @@ -106,14 +107,27 @@ struct ValueDFS { bool EdgeOnly = false; }; +// Perform a strict weak ordering on instructions and arguments. +static bool valueComesBefore(OrderedInstructions &OI, const Value *A, + const Value *B) { + auto *ArgA = dyn_cast_or_null(A); + auto *ArgB = dyn_cast_or_null(B); + if (ArgA && !ArgB) + return true; + if (ArgB && !ArgA) + return false; + if (ArgA && ArgB) + return ArgA->getArgNo() < ArgB->getArgNo(); + return OI.dominates(cast(A), cast(B)); +} + // This compares ValueDFS structures, creating OrderedBasicBlocks where // necessary to compare uses/defs in the same block. Doing so allows us to walk // the minimum number of instructions necessary to compute our def/use ordering. struct ValueDFS_Compare { - DenseMap> &OBBMap; - ValueDFS_Compare( - DenseMap> &OBBMap) - : OBBMap(OBBMap) {} + OrderedInstructions &OI; + ValueDFS_Compare(OrderedInstructions &OI) : OI(OI) {} + bool operator()(const ValueDFS &A, const ValueDFS &B) const { if (&A == &B) return false; @@ -196,23 +210,12 @@ struct ValueDFS_Compare { auto *ArgA = dyn_cast_or_null(ADef); auto *ArgB = dyn_cast_or_null(BDef); - if (ArgA && !ArgB) - return true; - if (ArgB && !ArgA) - return false; - if (ArgA && ArgB) - return ArgA->getArgNo() < ArgB->getArgNo(); + if (ArgA || ArgB) + return valueComesBefore(OI, ArgA, ArgB); auto *AInst = getDefOrUser(ADef, A.U); auto *BInst = getDefOrUser(BDef, B.U); - - auto *BB = AInst->getParent(); - auto LookupResult = OBBMap.find(BB); - if (LookupResult != OBBMap.end()) - return LookupResult->second->dominates(AInst, BInst); - - auto Result = OBBMap.insert({BB, make_unique(BB)}); - return Result.first->second->dominates(AInst, BInst); + return valueComesBefore(OI, AInst, BInst); } }; @@ -547,38 +550,11 @@ Value *PredicateInfo::materializeStack(unsigned int &Counter, void PredicateInfo::renameUses(SmallPtrSetImpl &OpSet) { // Sort OpsToRename since we are going to iterate it. SmallVector OpsToRename(OpSet.begin(), OpSet.end()); - std::sort(OpsToRename.begin(), OpsToRename.end(), [&](const Value *A, - const Value *B) { - auto *ArgA = dyn_cast_or_null(A); - auto *ArgB = dyn_cast_or_null(B); - - // If A and B are args, order them based on their arg no. - if (ArgA && !ArgB) - return true; - if (ArgB && !ArgA) - return false; - if (ArgA && ArgB) - return ArgA->getArgNo() < ArgB->getArgNo(); - - // Else, A are B are instructions. - // If they belong to different BBs, order them by the dominance of BBs. - auto *AInst = cast(A); - auto *BInst = cast(B); - if (AInst->getParent() != BInst->getParent()) - return DT.dominates(AInst->getParent(), BInst->getParent()); - - // Else, A and B belong to the same BB. - // Order A and B by their dominance. - auto *BB = AInst->getParent(); - auto LookupResult = OBBMap.find(BB); - if (LookupResult != OBBMap.end()) - return LookupResult->second->dominates(AInst, BInst); - - auto Result = OBBMap.insert({BB, make_unique(BB)}); - return Result.first->second->dominates(AInst, BInst); - }); - - ValueDFS_Compare Compare(OBBMap); + auto Comparator = [&](const Value *A, const Value *B) { + return valueComesBefore(OI, A, B); + }; + std::sort(OpsToRename.begin(), OpsToRename.end(), Comparator); + ValueDFS_Compare Compare(OI); // Compute liveness, and rename in O(uses) per Op. for (auto *Op : OpsToRename) { unsigned Counter = 0; @@ -715,7 +691,7 @@ PredicateInfo::getValueInfo(Value *Operand) const { PredicateInfo::PredicateInfo(Function &F, DominatorTree &DT, AssumptionCache &AC) - : F(F), DT(DT), AC(AC) { + : F(F), DT(DT), AC(AC), OI(&DT) { // Push an empty operand info so that we can detect 0 as not finding one ValueInfos.resize(1); buildPredicateInfo(); -- 2.40.0