summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--llvm/include/llvm/Transforms/Utils/PredicateInfo.h8
-rw-r--r--llvm/lib/Transforms/Utils/PredicateInfo.cpp78
2 files changed, 31 insertions, 55 deletions
diff --git a/llvm/include/llvm/Transforms/Utils/PredicateInfo.h b/llvm/include/llvm/Transforms/Utils/PredicateInfo.h
index 1322c686eb9..fc6f2c2118e 100644
--- a/llvm/include/llvm/Transforms/Utils/PredicateInfo.h
+++ b/llvm/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 <algorithm>
#include <cassert>
#include <cstddef>
@@ -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<Value *, unsigned int> ValueInfoNums;
- // OrderedBasicBlocks used during sorting uses
- DenseMap<const BasicBlock *, std::unique_ptr<OrderedBasicBlock>> OBBMap;
// The set of edges along which we can only handle phi uses, due to critical
// edges.
DenseSet<std::pair<BasicBlock *, BasicBlock *>> EdgeUsesOnly;
diff --git a/llvm/lib/Transforms/Utils/PredicateInfo.cpp b/llvm/lib/Transforms/Utils/PredicateInfo.cpp
index 1260e35e934..da4a2cb0a1b 100644
--- a/llvm/lib/Transforms/Utils/PredicateInfo.cpp
+++ b/llvm/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 <algorithm>
#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<Argument>(A);
+ auto *ArgB = dyn_cast_or_null<Argument>(B);
+ if (ArgA && !ArgB)
+ return true;
+ if (ArgB && !ArgA)
+ return false;
+ if (ArgA && ArgB)
+ return ArgA->getArgNo() < ArgB->getArgNo();
+ return OI.dominates(cast<Instruction>(A), cast<Instruction>(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<const BasicBlock *, std::unique_ptr<OrderedBasicBlock>> &OBBMap;
- ValueDFS_Compare(
- DenseMap<const BasicBlock *, std::unique_ptr<OrderedBasicBlock>> &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<Argument>(ADef);
auto *ArgB = dyn_cast_or_null<Argument>(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<OrderedBasicBlock>(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<Value *> &OpSet) {
// Sort OpsToRename since we are going to iterate it.
SmallVector<Value *, 8> OpsToRename(OpSet.begin(), OpSet.end());
- std::sort(OpsToRename.begin(), OpsToRename.end(), [&](const Value *A,
- const Value *B) {
- auto *ArgA = dyn_cast_or_null<Argument>(A);
- auto *ArgB = dyn_cast_or_null<Argument>(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<Instruction>(A);
- auto *BInst = cast<Instruction>(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<OrderedBasicBlock>(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();
OpenPOWER on IntegriCloud