#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallPtrSet.h"
-#include "llvm/ADT/SmallVector.h"
#include <vector>
#include <set>
namespace llvm {
class Value;
class Constant;
+ class Argument;
class Instruction;
class PHINode;
class TerminatorInst;
class BasicBlock;
class Function;
class SparseSolver;
+ class LLVMContext;
+ class raw_ostream;
+
+ template<typename T> class SmallVectorImpl;
/// AbstractLatticeFunction - This class is implemented by the dataflow instance
-/// to specify what the lattice values are and what how they handle merges etc.
+/// to specify what the lattice values are and how they handle merges etc.
/// This gives the client the power to compute lattice values from instructions,
/// constants, etc. The requirement is that lattice values must all fit into
/// a void*. If a void* is not sufficient, the implementation should use this
virtual LatticeVal ComputeConstant(Constant *C) {
return getOverdefinedVal(); // always safe
}
+
+ /// IsSpecialCasedPHI - Given a PHI node, determine whether this PHI node is
+ /// one that the we want to handle through ComputeInstructionState.
+ virtual bool IsSpecialCasedPHI(PHINode *PN) {
+ return false;
+ }
/// GetConstant - If the specified lattice value is representable as an LLVM
/// constant value, return it. Otherwise return null. The returned value
virtual Constant *GetConstant(LatticeVal LV, Value *Val, SparseSolver &SS) {
return 0;
}
+
+ /// ComputeArgument - Given a formal argument value, compute and return a
+ /// lattice value corresponding to the specified argument.
+ virtual LatticeVal ComputeArgument(Argument *I) {
+ return getOverdefinedVal(); // always safe
+ }
/// MergeValues - Compute and return the merge of the two specified lattice
/// values. Merging should only move one direction down the lattice to
}
/// PrintValue - Render the specified lattice value to the specified stream.
- virtual void PrintValue(LatticeVal V, std::ostream &OS);
+ virtual void PrintValue(LatticeVal V, raw_ostream &OS);
};
/// compute transfer functions.
AbstractLatticeFunction *LatticeFunc;
+ LLVMContext *Context;
+
DenseMap<Value*, LatticeVal> ValueState; // The state each value is in.
SmallPtrSet<BasicBlock*, 16> BBExecutable; // The bbs that are executable.
SparseSolver(const SparseSolver&); // DO NOT IMPLEMENT
void operator=(const SparseSolver&); // DO NOT IMPLEMENT
public:
- SparseSolver(AbstractLatticeFunction *Lattice) : LatticeFunc(Lattice) {}
+ explicit SparseSolver(AbstractLatticeFunction *Lattice, LLVMContext *C)
+ : LatticeFunc(Lattice), Context(C) {}
~SparseSolver() {
delete LatticeFunc;
}
///
void Solve(Function &F);
- void Print(Function &F, std::ostream &OS);
+ void Print(Function &F, raw_ostream &OS) const;
/// getLatticeState - Return the LatticeVal object that corresponds to the
/// value. If an value is not in the map, it is returned as untracked,
/// unlike the getOrInitValueState method.
LatticeVal getLatticeState(Value *V) const {
- DenseMap<Value*, LatticeVal>::iterator I = ValueState.find(V);
+ DenseMap<Value*, LatticeVal>::const_iterator I = ValueState.find(V);
return I != ValueState.end() ? I->second : LatticeFunc->getUntrackedVal();
}
LatticeVal getOrInitValueState(Value *V);
/// isEdgeFeasible - Return true if the control flow edge from the 'From'
- /// basic block to the 'To' basic block is currently feasible...
- bool isEdgeFeasible(BasicBlock *From, BasicBlock *To);
+ /// basic block to the 'To' basic block is currently feasible. If
+ /// AggressiveUndef is true, then this treats values with unknown lattice
+ /// values as undefined. This is generally only useful when solving the
+ /// lattice, not when querying it.
+ bool isEdgeFeasible(BasicBlock *From, BasicBlock *To,
+ bool AggressiveUndef = false);
+
+ /// isBlockExecutable - Return true if there are any known feasible
+ /// edges into the basic block. This is generally only useful when
+ /// querying the lattice.
+ bool isBlockExecutable(BasicBlock *BB) const {
+ return BBExecutable.count(BB);
+ }
private:
/// UpdateState - When the state for some instruction is potentially updated,
/// getFeasibleSuccessors - Return a vector of booleans to indicate which
/// successors are reachable from a given terminator instruction.
- void getFeasibleSuccessors(TerminatorInst &TI, SmallVectorImpl<bool> &Succs);
+ void getFeasibleSuccessors(TerminatorInst &TI, SmallVectorImpl<bool> &Succs,
+ bool AggressiveUndef);
void visitInst(Instruction &I);
void visitPHINode(PHINode &I);