//
// The LLVM Compiler Infrastructure
//
-// This file was developed by Nick Lewycky and is distributed under the
-// University of Illinois Open Source License. See LICENSE.TXT for details.
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
//
// The ValueRanges class stores the known integer bounds of a Value. When we
// encounter i8 %a u< %b, the ValueRanges stores that %a = [1, 255] and
-// %b = [0, 254]. Because we store these by Value*, you should always
-// canonicalize through the InequalityGraph first.
+// %b = [0, 254].
//
// It never stores an empty range, because that means that the code is
// unreachable. It never stores a single-element range since that's an equality
}
}
+ /// getRootNode - This returns the entry node for the CFG of the function.
Node *getRootNode() const { return Entry; }
+ /// getNodeForBlock - return the node for the specified basic block.
Node *getNodeForBlock(BasicBlock *BB) const {
if (!NodeMap.count(BB)) return 0;
return const_cast<DomTreeDFS*>(this)->NodeMap[BB];
}
+ /// dominates - returns true if the basic block for I1 dominates that of
+ /// the basic block for I2. If the instructions belong to the same basic
+ /// block, the instruction first instruction sequentially in the block is
+ /// considered dominating.
bool dominates(Instruction *I1, Instruction *I2) {
BasicBlock *BB1 = I1->getParent(),
*BB2 = I2->getParent();
return Node1 && Node2 && Node1->dominates(Node2);
}
}
+
private:
+ /// renumber - calculates the depth first search numberings and applies
+ /// them onto the nodes.
void renumber() {
std::stack<std::pair<Node *, Node::iterator> > S;
unsigned n = 0;
UGE = UGT | EQ_BIT
};
+ /// validPredicate - determines whether a given value is actually a lattice
+ /// value. Only used in assertions or debugging.
static bool validPredicate(LatticeVal LV) {
switch (LV) {
case GT: case GE: case LT: case LE: case NE:
/// ValueNumbering stores the scope-specific value numbers for a given Value.
class VISIBILITY_HIDDEN ValueNumbering {
+
+ /// VNPair is a tuple of {Value, index number, DomTreeDFS::Node}. It
+ /// includes the comparison operators necessary to allow you to store it
+ /// in a sorted vector.
class VISIBILITY_HIDDEN VNPair {
public:
Value *V;
bool operator<(Value *RHS) const {
return V < RHS;
}
+
+ bool operator>(Value *RHS) const {
+ return V > RHS;
+ }
+
+ friend bool operator<(Value *RHS, const VNPair &pair) {
+ return pair.operator>(RHS);
+ }
};
typedef std::vector<VNPair> VNMapType;
VNMapType VNMap;
+ /// The canonical choice for value number at index.
std::vector<Value *> Values;
DomTreeDFS *DTDFS;
return E;
}
- /// Updates the lattice value for a given node. Create a new entry if
- /// one doesn't exist, otherwise it merges the values. The new lattice
- /// value must not be inconsistent with any previously existing value.
+ /// update - updates the lattice value for a given node, creating a new
+ /// entry if one doesn't exist. The new lattice value must not be
+ /// inconsistent with any previously existing value.
void update(unsigned n, LatticeVal R, DomTreeDFS::Node *Subtree) {
assert(validPredicate(R) && "Invalid predicate.");
- iterator I = find(n, Subtree);
- if (I == end()) {
- Edge edge(n, R, Subtree);
- iterator Insert = std::lower_bound(begin(), end(), edge);
- Relations.insert(Insert, edge);
- } else {
- LatticeVal LV = static_cast<LatticeVal>(I->LV & R);
- assert(validPredicate(LV) && "Invalid union of lattice values.");
- if (LV != I->LV) {
- if (Subtree != I->Subtree) {
- assert(Subtree->DominatedBy(I->Subtree) &&
- "Find returned subtree that doesn't apply.");
-
- Edge edge(n, R, Subtree);
- iterator Insert = std::lower_bound(begin(), end(), edge);
- Relations.insert(Insert, edge); // invalidates I
- I = find(n, Subtree);
- }
- // Also, we have to tighten any edge that Subtree dominates.
- for (iterator B = begin(); I->To == n; --I) {
- if (I->Subtree->DominatedBy(Subtree)) {
- LatticeVal LV = static_cast<LatticeVal>(I->LV & R);
- assert(validPredicate(LV) && "Invalid union of lattice values");
- I->LV = LV;
- }
- if (I == B) break;
+ Edge edge(n, R, Subtree);
+ iterator B = begin(), E = end();
+ iterator I = std::lower_bound(B, E, edge);
+
+ iterator J = I;
+ while (J != E && J->To == n) {
+ if (Subtree->DominatedBy(J->Subtree))
+ break;
+ ++J;
+ }
+
+ if (J != E && J->To == n) {
+ edge.LV = static_cast<LatticeVal>(J->LV & R);
+ assert(validPredicate(edge.LV) && "Invalid union of lattice values.");
+
+ if (edge.LV == J->LV)
+ return; // This update adds nothing new.
+ }
+
+ if (I != B) {
+ // We also have to tighten any edge beneath our update.
+ for (iterator K = I - 1; K->To == n; --K) {
+ if (K->Subtree->DominatedBy(Subtree)) {
+ LatticeVal LV = static_cast<LatticeVal>(K->LV & edge.LV);
+ assert(validPredicate(LV) && "Invalid union of lattice values");
+ K->LV = LV;
}
+ if (K == B) break;
}
- }
+ }
+
+ // Insert new edge at Subtree if it isn't already there.
+ if (I == E || I->To != n || Subtree != I->Subtree)
+ Relations.insert(I, edge);
}
};
void update(const ConstantRange &CR, DomTreeDFS::Node *Subtree) {
assert(!CR.isEmptySet() && "Empty ConstantRange.");
- assert(!CR.isSingleElement() && "Won't store single element.");
+ assert(!CR.isSingleElement() && "Refusing to store single element.");
static ConstantRange empty(1, false);
iterator E = end();
uint32_t typeToWidth(const Type *Ty) const {
if (TD)
return TD->getTypeSizeInBits(Ty);
-
- if (const IntegerType *ITy = dyn_cast<IntegerType>(Ty))
- return ITy->getBitWidth();
-
- return 0;
+ else
+ return Ty->getPrimitiveSizeInBits();
}
static bool isRelatedBy(const ConstantRange &CR1, const ConstantRange &CR2,
if (!isRelatedBy(Known, Zero, ICmpInst::ICMP_NE)) break;
// otherwise, fall-through.
case Instruction::Sub:
- if (Unknown == Op1) break;
+ if (Unknown == Op0) break;
// otherwise, fall-through.
case Instruction::Xor:
case Instruction::Add:
}
private:
- /// Forwards - Adds new properties into PropertySet and uses them to
+ /// Forwards - Adds new properties to VRPSolver and uses them to
/// simplify instructions. Because new properties sometimes apply to
/// a transition from one BasicBlock to another, this will use the
/// PredicateSimplifier::proceedToSuccessor(s) interface to enter the
- /// basic block with the new PropertySet.
+ /// basic block.
/// @brief Performs abstract execution of the program.
class VISIBILITY_HIDDEN Forwards : public InstVisitor<Forwards> {
friend class InstVisitor<Forwards>;
}
}
- // Tries to simplify each Instruction and add new properties to
- // the PropertySet.
+ // Tries to simplify each Instruction and add new properties.
void visitInstruction(Instruction *I, DomTreeDFS::Node *DT) {
DOUT << "Considering instruction " << *I << "\n";
DEBUG(VN->dump());
projects / oota-llvm.git / blobdiff