diff options
author | Chris Lattner <sabre@nondot.org> | 2010-08-28 03:51:24 +0000 |
---|---|---|
committer | Chris Lattner <sabre@nondot.org> | 2010-08-28 03:51:24 +0000 |
commit | 5f88af537637831451ff9ffa08c597e05e7dc9fb (patch) | |
tree | e9c250c2119d44eff4be2827c1a6e6da1a4302b8 /lib | |
parent | 5f8a87dd766196a259d3f670d928641ca3b00e95 (diff) | |
download | external_llvm-5f88af537637831451ff9ffa08c597e05e7dc9fb.zip external_llvm-5f88af537637831451ff9ffa08c597e05e7dc9fb.tar.gz external_llvm-5f88af537637831451ff9ffa08c597e05e7dc9fb.tar.bz2 |
remove the ABCD and SSI passes. They don't have any clients that
I'm aware of, aren't maintained, and LVI will be replacing their value.
nlewycky approved this on irc.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@112355 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib')
-rw-r--r-- | lib/Transforms/Scalar/ABCD.cpp | 1103 | ||||
-rw-r--r-- | lib/Transforms/Scalar/CMakeLists.txt | 1 | ||||
-rw-r--r-- | lib/Transforms/Utils/CMakeLists.txt | 1 | ||||
-rw-r--r-- | lib/Transforms/Utils/SSI.cpp | 433 |
4 files changed, 0 insertions, 1538 deletions
diff --git a/lib/Transforms/Scalar/ABCD.cpp b/lib/Transforms/Scalar/ABCD.cpp deleted file mode 100644 index 2abc074..0000000 --- a/lib/Transforms/Scalar/ABCD.cpp +++ /dev/null @@ -1,1103 +0,0 @@ -//===------- ABCD.cpp - Removes redundant conditional branches ------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This pass removes redundant branch instructions. This algorithm was -// described by Rastislav Bodik, Rajiv Gupta and Vivek Sarkar in their paper -// "ABCD: Eliminating Array Bounds Checks on Demand (2000)". The original -// Algorithm was created to remove array bound checks for strongly typed -// languages. This implementation expands the idea and removes any conditional -// branches that can be proved redundant, not only those used in array bound -// checks. With the SSI representation, each variable has a -// constraint. By analyzing these constraints we can prove that a branch is -// redundant. When a branch is proved redundant it means that -// one direction will always be taken; thus, we can change this branch into an -// unconditional jump. -// It is advisable to run SimplifyCFG and Aggressive Dead Code Elimination -// after ABCD to clean up the code. -// This implementation was created based on the implementation of the ABCD -// algorithm implemented for the compiler Jitrino. -// -//===----------------------------------------------------------------------===// - -#define DEBUG_TYPE "abcd" -#include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/OwningPtr.h" -#include "llvm/ADT/SmallPtrSet.h" -#include "llvm/ADT/Statistic.h" -#include "llvm/Constants.h" -#include "llvm/Function.h" -#include "llvm/Instructions.h" -#include "llvm/Pass.h" -#include "llvm/Support/raw_ostream.h" -#include "llvm/Support/Debug.h" -#include "llvm/Transforms/Scalar.h" -#include "llvm/Transforms/Utils/SSI.h" - -using namespace llvm; - -STATISTIC(NumBranchTested, "Number of conditional branches analyzed"); -STATISTIC(NumBranchRemoved, "Number of conditional branches removed"); - -namespace { - -class ABCD : public FunctionPass { - public: - static char ID; // Pass identification, replacement for typeid. - ABCD() : FunctionPass(ID) {} - - void getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequired<SSI>(); - } - - bool runOnFunction(Function &F); - - private: - /// Keep track of whether we've modified the program yet. - bool modified; - - enum ProveResult { - False = 0, - Reduced = 1, - True = 2 - }; - - typedef ProveResult (*meet_function)(ProveResult, ProveResult); - static ProveResult max(ProveResult res1, ProveResult res2) { - return (ProveResult) std::max(res1, res2); - } - static ProveResult min(ProveResult res1, ProveResult res2) { - return (ProveResult) std::min(res1, res2); - } - - class Bound { - public: - Bound(APInt v, bool upper) : value(v), upper_bound(upper) {} - Bound(const Bound &b, const APInt &cnst) - : value(b.value - cnst), upper_bound(b.upper_bound) {} - - /// Test if Bound is an upper bound - bool isUpperBound() const { return upper_bound; } - - /// Get the bitwidth of this bound - int32_t getBitWidth() const { return value.getBitWidth(); } - - /// Creates a Bound incrementing the one received - static Bound createIncrement(const Bound &b) { - return Bound(b.isUpperBound() ? b.value+1 : b.value-1, - b.upper_bound); - } - - /// Creates a Bound decrementing the one received - static Bound createDecrement(const Bound &b) { - return Bound(b.isUpperBound() ? b.value-1 : b.value+1, - b.upper_bound); - } - - /// Test if two bounds are equal - static bool eq(const Bound *a, const Bound *b) { - if (!a || !b) return false; - - assert(a->isUpperBound() == b->isUpperBound()); - return a->value == b->value; - } - - /// Test if val is less than or equal to Bound b - static bool leq(APInt val, const Bound &b) { - return b.isUpperBound() ? val.sle(b.value) : val.sge(b.value); - } - - /// Test if Bound a is less then or equal to Bound - static bool leq(const Bound &a, const Bound &b) { - assert(a.isUpperBound() == b.isUpperBound()); - return a.isUpperBound() ? a.value.sle(b.value) : - a.value.sge(b.value); - } - - /// Test if Bound a is less then Bound b - static bool lt(const Bound &a, const Bound &b) { - assert(a.isUpperBound() == b.isUpperBound()); - return a.isUpperBound() ? a.value.slt(b.value) : - a.value.sgt(b.value); - } - - /// Test if Bound b is greater then or equal val - static bool geq(const Bound &b, const APInt &val) { - return leq(val, b); - } - - private: - APInt value; - bool upper_bound; - }; - - /// This class is used to store results some parts of the graph, - /// so information does not need to be recalculated. The maximum false, - /// minimum true and minimum reduced results are stored - class MemoizedResultChart { - public: - MemoizedResultChart() {} - MemoizedResultChart(const MemoizedResultChart &other) { - if (other.max_false) - max_false.reset(new Bound(*other.max_false)); - if (other.min_true) - min_true.reset(new Bound(*other.min_true)); - if (other.min_reduced) - min_reduced.reset(new Bound(*other.min_reduced)); - } - - /// Returns the max false - const Bound *getFalse() const { return max_false.get(); } - - /// Returns the min true - const Bound *getTrue() const { return min_true.get(); } - - /// Returns the min reduced - const Bound *getReduced() const { return min_reduced.get(); } - - /// Return the stored result for this bound - ProveResult getResult(const Bound &bound) const; - - /// Stores a false found - void addFalse(const Bound &bound); - - /// Stores a true found - void addTrue(const Bound &bound); - - /// Stores a Reduced found - void addReduced(const Bound &bound); - - /// Clears redundant reduced - /// If a min_true is smaller than a min_reduced then the min_reduced - /// is unnecessary and then removed. It also works for min_reduced - /// begin smaller than max_false. - void clearRedundantReduced(); - - void clear() { - max_false.reset(); - min_true.reset(); - min_reduced.reset(); - } - - private: - OwningPtr<Bound> max_false, min_true, min_reduced; - }; - - /// This class stores the result found for a node of the graph, - /// so these results do not need to be recalculated, only searched for. - class MemoizedResult { - public: - /// Test if there is true result stored from b to a - /// that is less then the bound - bool hasTrue(Value *b, const Bound &bound) const { - const Bound *trueBound = map.lookup(b).getTrue(); - return trueBound && Bound::leq(*trueBound, bound); - } - - /// Test if there is false result stored from b to a - /// that is less then the bound - bool hasFalse(Value *b, const Bound &bound) const { - const Bound *falseBound = map.lookup(b).getFalse(); - return falseBound && Bound::leq(*falseBound, bound); - } - - /// Test if there is reduced result stored from b to a - /// that is less then the bound - bool hasReduced(Value *b, const Bound &bound) const { - const Bound *reducedBound = map.lookup(b).getReduced(); - return reducedBound && Bound::leq(*reducedBound, bound); - } - - /// Returns the stored bound for b - ProveResult getBoundResult(Value *b, const Bound &bound) { - return map[b].getResult(bound); - } - - /// Clears the map - void clear() { - DenseMapIterator<Value*, MemoizedResultChart> begin = map.begin(); - DenseMapIterator<Value*, MemoizedResultChart> end = map.end(); - for (; begin != end; ++begin) { - begin->second.clear(); - } - map.clear(); - } - - /// Stores the bound found - void updateBound(Value *b, const Bound &bound, const ProveResult res); - - private: - // Maps a nod in the graph with its results found. - DenseMap<Value*, MemoizedResultChart> map; - }; - - /// This class represents an edge in the inequality graph used by the - /// ABCD algorithm. An edge connects node v to node u with a value c if - /// we could infer a constraint v <= u + c in the source program. - class Edge { - public: - Edge(Value *V, APInt val, bool upper) - : vertex(V), value(val), upper_bound(upper) {} - - Value *getVertex() const { return vertex; } - const APInt &getValue() const { return value; } - bool isUpperBound() const { return upper_bound; } - - private: - Value *vertex; - APInt value; - bool upper_bound; - }; - - /// Weighted and Directed graph to represent constraints. - /// There is one type of constraint, a <= b + X, which will generate an - /// edge from b to a with weight X. - class InequalityGraph { - public: - - /// Adds an edge from V_from to V_to with weight value - void addEdge(Value *V_from, Value *V_to, APInt value, bool upper); - - /// Test if there is any edge from V in the upper direction - bool hasEdge(Value *V, bool upper) const; - - /// Returns all edges pointed by vertex V - SmallVector<Edge, 16> getEdges(Value *V) const { - return graph.lookup(V); - } - - /// Prints the graph in dot format. - /// Blue edges represent upper bound and Red lower bound. - void printGraph(raw_ostream &OS, Function &F) const { - printHeader(OS, F); - printBody(OS); - printFooter(OS); - } - - /// Clear the graph - void clear() { - graph.clear(); - } - - private: - DenseMap<Value *, SmallVector<Edge, 16> > graph; - - /// Prints the header of the dot file - void printHeader(raw_ostream &OS, Function &F) const; - - /// Prints the footer of the dot file - void printFooter(raw_ostream &OS) const { - OS << "}\n"; - } - - /// Prints the body of the dot file - void printBody(raw_ostream &OS) const; - - /// Prints vertex source to the dot file - void printVertex(raw_ostream &OS, Value *source) const; - - /// Prints the edge to the dot file - void printEdge(raw_ostream &OS, Value *source, const Edge &edge) const; - - void printName(raw_ostream &OS, Value *info) const; - }; - - /// Iterates through all BasicBlocks, if the Terminator Instruction - /// uses an Comparator Instruction, all operands of this comparator - /// are sent to be transformed to SSI. Only Instruction operands are - /// transformed. - void createSSI(Function &F); - - /// Creates the graphs for this function. - /// It will look for all comparators used in branches, and create them. - /// These comparators will create constraints for any instruction as an - /// operand. - void executeABCD(Function &F); - - /// Seeks redundancies in the comparator instruction CI. - /// If the ABCD algorithm can prove that the comparator CI always - /// takes one way, then the Terminator Instruction TI is substituted from - /// a conditional branch to a unconditional one. - /// This code basically receives a comparator, and verifies which kind of - /// instruction it is. Depending on the kind of instruction, we use different - /// strategies to prove its redundancy. - void seekRedundancy(ICmpInst *ICI, TerminatorInst *TI); - - /// Substitutes Terminator Instruction TI, that is a conditional branch, - /// with one unconditional branch. Succ_edge determines if the new - /// unconditional edge will be the first or second edge of the former TI - /// instruction. - void removeRedundancy(TerminatorInst *TI, bool Succ_edge); - - /// When an conditional branch is removed, the BasicBlock that is no longer - /// reachable will have problems in phi functions. This method fixes these - /// phis removing the former BasicBlock from the list of incoming BasicBlocks - /// of all phis. In case the phi remains with no predecessor it will be - /// marked to be removed later. - void fixPhi(BasicBlock *BB, BasicBlock *Succ); - - /// Removes phis that have no predecessor - void removePhis(); - - /// Creates constraints for Instructions. - /// If the constraint for this instruction has already been created - /// nothing is done. - void createConstraintInstruction(Instruction *I); - - /// Creates constraints for Binary Operators. - /// It will create constraints only for addition and subtraction, - /// the other binary operations are not treated by ABCD. - /// For additions in the form a = b + X and a = X + b, where X is a constant, - /// the constraint a <= b + X can be obtained. For this constraint, an edge - /// a->b with weight X is added to the lower bound graph, and an edge - /// b->a with weight -X is added to the upper bound graph. - /// Only subtractions in the format a = b - X is used by ABCD. - /// Edges are created using the same semantic as addition. - void createConstraintBinaryOperator(BinaryOperator *BO); - - /// Creates constraints for Comparator Instructions. - /// Only comparators that have any of the following operators - /// are used to create constraints: >=, >, <=, <. And only if - /// at least one operand is an Instruction. In a Comparator Instruction - /// a op b, there will be 4 sigma functions a_t, a_f, b_t and b_f. Where - /// t and f represent sigma for operands in true and false branches. The - /// following constraints can be obtained. a_t <= a, a_f <= a, b_t <= b and - /// b_f <= b. There are two more constraints that depend on the operator. - /// For the operator <= : a_t <= b_t and b_f <= a_f-1 - /// For the operator < : a_t <= b_t-1 and b_f <= a_f - /// For the operator >= : b_t <= a_t and a_f <= b_f-1 - /// For the operator > : b_t <= a_t-1 and a_f <= b_f - void createConstraintCmpInst(ICmpInst *ICI, TerminatorInst *TI); - - /// Creates constraints for PHI nodes. - /// In a PHI node a = phi(b,c) we can create the constraint - /// a<= max(b,c). With this constraint there will be the edges, - /// b->a and c->a with weight 0 in the lower bound graph, and the edges - /// a->b and a->c with weight 0 in the upper bound graph. - void createConstraintPHINode(PHINode *PN); - - /// Given a binary operator, we are only interest in the case - /// that one operand is an Instruction and the other is a ConstantInt. In - /// this case the method returns true, otherwise false. It also obtains the - /// Instruction and ConstantInt from the BinaryOperator and returns it. - bool createBinaryOperatorInfo(BinaryOperator *BO, Instruction **I1, - Instruction **I2, ConstantInt **C1, - ConstantInt **C2); - - /// This method creates a constraint between a Sigma and an Instruction. - /// These constraints are created as soon as we find a comparator that uses a - /// SSI variable. - void createConstraintSigInst(Instruction *I_op, BasicBlock *BB_succ_t, - BasicBlock *BB_succ_f, PHINode **SIG_op_t, - PHINode **SIG_op_f); - - /// If PN_op1 and PN_o2 are different from NULL, create a constraint - /// PN_op2 -> PN_op1 with value. In case any of them is NULL, replace - /// with the respective V_op#, if V_op# is a ConstantInt. - void createConstraintSigSig(PHINode *SIG_op1, PHINode *SIG_op2, - ConstantInt *V_op1, ConstantInt *V_op2, - APInt value); - - /// Returns the sigma representing the Instruction I in BasicBlock BB. - /// Returns NULL in case there is no sigma for this Instruction in this - /// Basic Block. This methods assume that sigmas are the first instructions - /// in a block, and that there can be only two sigmas in a block. So it will - /// only look on the first two instructions of BasicBlock BB. - PHINode *findSigma(BasicBlock *BB, Instruction *I); - - /// Original ABCD algorithm to prove redundant checks. - /// This implementation works on any kind of inequality branch. - bool demandProve(Value *a, Value *b, int c, bool upper_bound); - - /// Prove that distance between b and a is <= bound - ProveResult prove(Value *a, Value *b, const Bound &bound, unsigned level); - - /// Updates the distance value for a and b - void updateMemDistance(Value *a, Value *b, const Bound &bound, unsigned level, - meet_function meet); - - InequalityGraph inequality_graph; - MemoizedResult mem_result; - DenseMap<Value*, const Bound*> active; - SmallPtrSet<Value*, 16> created; - SmallVector<PHINode *, 16> phis_to_remove; -}; - -} // end anonymous namespace. - -char ABCD::ID = 0; -INITIALIZE_PASS(ABCD, "abcd", - "ABCD: Eliminating Array Bounds Checks on Demand", - false, false); - -bool ABCD::runOnFunction(Function &F) { - modified = false; - createSSI(F); - executeABCD(F); - DEBUG(inequality_graph.printGraph(dbgs(), F)); - removePhis(); - - inequality_graph.clear(); - mem_result.clear(); - active.clear(); - created.clear(); - phis_to_remove.clear(); - return modified; -} - -/// Iterates through all BasicBlocks, if the Terminator Instruction -/// uses an Comparator Instruction, all operands of this comparator -/// are sent to be transformed to SSI. Only Instruction operands are -/// transformed. -void ABCD::createSSI(Function &F) { - SSI *ssi = &getAnalysis<SSI>(); - - SmallVector<Instruction *, 16> Insts; - - for (Function::iterator begin = F.begin(), end = F.end(); - begin != end; ++begin) { - BasicBlock *BB = begin; - TerminatorInst *TI = BB->getTerminator(); - if (TI->getNumOperands() == 0) - continue; - - if (ICmpInst *ICI = dyn_cast<ICmpInst>(TI->getOperand(0))) { - if (Instruction *I = dyn_cast<Instruction>(ICI->getOperand(0))) { - modified = true; // XXX: but yet createSSI might do nothing - Insts.push_back(I); - } - if (Instruction *I = dyn_cast<Instruction>(ICI->getOperand(1))) { - modified = true; - Insts.push_back(I); - } - } - } - ssi->createSSI(Insts); -} - -/// Creates the graphs for this function. -/// It will look for all comparators used in branches, and create them. -/// These comparators will create constraints for any instruction as an -/// operand. -void ABCD::executeABCD(Function &F) { - for (Function::iterator begin = F.begin(), end = F.end(); - begin != end; ++begin) { - BasicBlock *BB = begin; - TerminatorInst *TI = BB->getTerminator(); - if (TI->getNumOperands() == 0) - continue; - - ICmpInst *ICI = dyn_cast<ICmpInst>(TI->getOperand(0)); - if (!ICI || !ICI->getOperand(0)->getType()->isIntegerTy()) - continue; - - createConstraintCmpInst(ICI, TI); - seekRedundancy(ICI, TI); - } -} - -/// Seeks redundancies in the comparator instruction CI. -/// If the ABCD algorithm can prove that the comparator CI always -/// takes one way, then the Terminator Instruction TI is substituted from -/// a conditional branch to a unconditional one. -/// This code basically receives a comparator, and verifies which kind of -/// instruction it is. Depending on the kind of instruction, we use different -/// strategies to prove its redundancy. -void ABCD::seekRedundancy(ICmpInst *ICI, TerminatorInst *TI) { - CmpInst::Predicate Pred = ICI->getPredicate(); - - Value *source, *dest; - int distance1, distance2; - bool upper; - - switch(Pred) { - case CmpInst::ICMP_SGT: // signed greater than - upper = false; - distance1 = 1; - distance2 = 0; - break; - - case CmpInst::ICMP_SGE: // signed greater or equal - upper = false; - distance1 = 0; - distance2 = -1; - break; - - case CmpInst::ICMP_SLT: // signed less than - upper = true; - distance1 = -1; - distance2 = 0; - break; - - case CmpInst::ICMP_SLE: // signed less or equal - upper = true; - distance1 = 0; - distance2 = 1; - break; - - default: - return; - } - - ++NumBranchTested; - source = ICI->getOperand(0); - dest = ICI->getOperand(1); - if (demandProve(dest, source, distance1, upper)) { - removeRedundancy(TI, true); - } else if (demandProve(dest, source, distance2, !upper)) { - removeRedundancy(TI, false); - } -} - -/// Substitutes Terminator Instruction TI, that is a conditional branch, -/// with one unconditional branch. Succ_edge determines if the new -/// unconditional edge will be the first or second edge of the former TI -/// instruction. -void ABCD::removeRedundancy(TerminatorInst *TI, bool Succ_edge) { - BasicBlock *Succ; - if (Succ_edge) { - Succ = TI->getSuccessor(0); - fixPhi(TI->getParent(), TI->getSuccessor(1)); - } else { - Succ = TI->getSuccessor(1); - fixPhi(TI->getParent(), TI->getSuccessor(0)); - } - - BranchInst::Create(Succ, TI); - TI->eraseFromParent(); // XXX: invoke - ++NumBranchRemoved; - modified = true; -} - -/// When an conditional branch is removed, the BasicBlock that is no longer -/// reachable will have problems in phi functions. This method fixes these -/// phis removing the former BasicBlock from the list of incoming BasicBlocks -/// of all phis. In case the phi remains with no predecessor it will be -/// marked to be removed later. -void ABCD::fixPhi(BasicBlock *BB, BasicBlock *Succ) { - BasicBlock::iterator begin = Succ->begin(); - while (PHINode *PN = dyn_cast<PHINode>(begin++)) { - PN->removeIncomingValue(BB, false); - if (PN->getNumIncomingValues() == 0) - phis_to_remove.push_back(PN); - } -} - -/// Removes phis that have no predecessor -void ABCD::removePhis() { - for (unsigned i = 0, e = phis_to_remove.size(); i != e; ++i) { - PHINode *PN = phis_to_remove[i]; - PN->replaceAllUsesWith(UndefValue::get(PN->getType())); - PN->eraseFromParent(); - } -} - -/// Creates constraints for Instructions. -/// If the constraint for this instruction has already been created -/// nothing is done. -void ABCD::createConstraintInstruction(Instruction *I) { - // Test if this instruction has not been created before - if (created.insert(I)) { - if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) { - createConstraintBinaryOperator(BO); - } else if (PHINode *PN = dyn_cast<PHINode>(I)) { - createConstraintPHINode(PN); - } - } -} - -/// Creates constraints for Binary Operators. -/// It will create constraints only for addition and subtraction, -/// the other binary operations are not treated by ABCD. -/// For additions in the form a = b + X and a = X + b, where X is a constant, -/// the constraint a <= b + X can be obtained. For this constraint, an edge -/// a->b with weight X is added to the lower bound graph, and an edge -/// b->a with weight -X is added to the upper bound graph. -/// Only subtractions in the format a = b - X is used by ABCD. -/// Edges are created using the same semantic as addition. -void ABCD::createConstraintBinaryOperator(BinaryOperator *BO) { - Instruction *I1 = NULL, *I2 = NULL; - ConstantInt *CI1 = NULL, *CI2 = NULL; - - // Test if an operand is an Instruction and the other is a Constant - if (!createBinaryOperatorInfo(BO, &I1, &I2, &CI1, &CI2)) - return; - - Instruction *I = 0; - APInt value; - - switch (BO->getOpcode()) { - case Instruction::Add: - if (I1) { - I = I1; - value = CI2->getValue(); - } else if (I2) { - I = I2; - value = CI1->getValue(); - } - break; - - case Instruction::Sub: - // Instructions like a = X-b, where X is a constant are not represented - // in the graph. - if (!I1) - return; - - I = I1; - value = -CI2->getValue(); - break; - - default: - return; - } - - inequality_graph.addEdge(I, BO, value, true); - inequality_graph.addEdge(BO, I, -value, false); - createConstraintInstruction(I); -} - -/// Given a binary operator, we are only interest in the case -/// that one operand is an Instruction and the other is a ConstantInt. In -/// this case the method returns true, otherwise false. It also obtains the -/// Instruction and ConstantInt from the BinaryOperator and returns it. -bool ABCD::createBinaryOperatorInfo(BinaryOperator *BO, Instruction **I1, - Instruction **I2, ConstantInt **C1, - ConstantInt **C2) { - Value *op1 = BO->getOperand(0); - Value *op2 = BO->getOperand(1); - - if ((*I1 = dyn_cast<Instruction>(op1))) { - if ((*C2 = dyn_cast<ConstantInt>(op2))) - return true; // First is Instruction and second ConstantInt - - return false; // Both are Instruction - } else { - if ((*C1 = dyn_cast<ConstantInt>(op1)) && - (*I2 = dyn_cast<Instruction>(op2))) - return true; // First is ConstantInt and second Instruction - - return false; // Both are not Instruction - } -} - -/// Creates constraints for Comparator Instructions. -/// Only comparators that have any of the following operators -/// are used to create constraints: >=, >, <=, <. And only if -/// at least one operand is an Instruction. In a Comparator Instruction -/// a op b, there will be 4 sigma functions a_t, a_f, b_t and b_f. Where -/// t and f represent sigma for operands in true and false branches. The -/// following constraints can be obtained. a_t <= a, a_f <= a, b_t <= b and -/// b_f <= b. There are two more constraints that depend on the operator. -/// For the operator <= : a_t <= b_t and b_f <= a_f-1 -/// For the operator < : a_t <= b_t-1 and b_f <= a_f -/// For the operator >= : b_t <= a_t and a_f <= b_f-1 -/// For the operator > : b_t <= a_t-1 and a_f <= b_f -void ABCD::createConstraintCmpInst(ICmpInst *ICI, TerminatorInst *TI) { - Value *V_op1 = ICI->getOperand(0); - Value *V_op2 = ICI->getOperand(1); - - if (!V_op1->getType()->isIntegerTy()) - return; - - Instruction *I_op1 = dyn_cast<Instruction>(V_op1); - Instruction *I_op2 = dyn_cast<Instruction>(V_op2); - - // Test if at least one operand is an Instruction - if (!I_op1 && !I_op2) - return; - - BasicBlock *BB_succ_t = TI->getSuccessor(0); - BasicBlock *BB_succ_f = TI->getSuccessor(1); - - PHINode *SIG_op1_t = NULL, *SIG_op1_f = NULL, - *SIG_op2_t = NULL, *SIG_op2_f = NULL; - - createConstraintSigInst(I_op1, BB_succ_t, BB_succ_f, &SIG_op1_t, &SIG_op1_f); - createConstraintSigInst(I_op2, BB_succ_t, BB_succ_f, &SIG_op2_t, &SIG_op2_f); - - int32_t width = cast<IntegerType>(V_op1->getType())->getBitWidth(); - APInt MinusOne = APInt::getAllOnesValue(width); - APInt Zero = APInt::getNullValue(width); - - CmpInst::Predicate Pred = ICI->getPredicate(); - ConstantInt *CI1 = dyn_cast<ConstantInt>(V_op1); - ConstantInt *CI2 = dyn_cast<ConstantInt>(V_op2); - switch (Pred) { - case CmpInst::ICMP_SGT: // signed greater than - createConstraintSigSig(SIG_op2_t, SIG_op1_t, CI2, CI1, MinusOne); - createConstraintSigSig(SIG_op1_f, SIG_op2_f, CI1, CI2, Zero); - break; - - case CmpInst::ICMP_SGE: // signed greater or equal - createConstraintSigSig(SIG_op2_t, SIG_op1_t, CI2, CI1, Zero); - createConstraintSigSig(SIG_op1_f, SIG_op2_f, CI1, CI2, MinusOne); - break; - - case CmpInst::ICMP_SLT: // signed less than - createConstraintSigSig(SIG_op1_t, SIG_op2_t, CI1, CI2, MinusOne); - createConstraintSigSig(SIG_op2_f, SIG_op1_f, CI2, CI1, Zero); - break; - - case CmpInst::ICMP_SLE: // signed less or equal - createConstraintSigSig(SIG_op1_t, SIG_op2_t, CI1, CI2, Zero); - createConstraintSigSig(SIG_op2_f, SIG_op1_f, CI2, CI1, MinusOne); - break; - - default: - break; - } - - if (I_op1) - createConstraintInstruction(I_op1); - if (I_op2) - createConstraintInstruction(I_op2); -} - -/// Creates constraints for PHI nodes. -/// In a PHI node a = phi(b,c) we can create the constraint -/// a<= max(b,c). With this constraint there will be the edges, -/// b->a and c->a with weight 0 in the lower bound graph, and the edges -/// a->b and a->c with weight 0 in the upper bound graph. -void ABCD::createConstraintPHINode(PHINode *PN) { - // FIXME: We really want to disallow sigma nodes, but I don't know the best - // way to detect the other than this. - if (PN->getNumOperands() == 2) return; - - int32_t width = cast<IntegerType>(PN->getType())->getBitWidth(); - for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { - Value *V = PN->getIncomingValue(i); - if (Instruction *I = dyn_cast<Instruction>(V)) { - createConstraintInstruction(I); - } - inequality_graph.addEdge(V, PN, APInt(width, 0), true); - inequality_graph.addEdge(V, PN, APInt(width, 0), false); - } -} - -/// This method creates a constraint between a Sigma and an Instruction. -/// These constraints are created as soon as we find a comparator that uses a -/// SSI variable. -void ABCD::createConstraintSigInst(Instruction *I_op, BasicBlock *BB_succ_t, - BasicBlock *BB_succ_f, PHINode **SIG_op_t, - PHINode **SIG_op_f) { - *SIG_op_t = findSigma(BB_succ_t, I_op); - *SIG_op_f = findSigma(BB_succ_f, I_op); - - if (*SIG_op_t) { - int32_t width = cast<IntegerType>((*SIG_op_t)->getType())->getBitWidth(); - inequality_graph.addEdge(I_op, *SIG_op_t, APInt(width, 0), true); - inequality_graph.addEdge(*SIG_op_t, I_op, APInt(width, 0), false); - } - if (*SIG_op_f) { - int32_t width = cast<IntegerType>((*SIG_op_f)->getType())->getBitWidth(); - inequality_graph.addEdge(I_op, *SIG_op_f, APInt(width, 0), true); - inequality_graph.addEdge(*SIG_op_f, I_op, APInt(width, 0), false); - } -} - -/// If PN_op1 and PN_o2 are different from NULL, create a constraint -/// PN_op2 -> PN_op1 with value. In case any of them is NULL, replace -/// with the respective V_op#, if V_op# is a ConstantInt. -void ABCD::createConstraintSigSig(PHINode *SIG_op1, PHINode *SIG_op2, - ConstantInt *V_op1, ConstantInt *V_op2, - APInt value) { - if (SIG_op1 && SIG_op2) { - inequality_graph.addEdge(SIG_op2, SIG_op1, value, true); - inequality_graph.addEdge(SIG_op1, SIG_op2, -value, false); - } else if (SIG_op1 && V_op2) { - inequality_graph.addEdge(V_op2, SIG_op1, value, true); - inequality_graph.addEdge(SIG_op1, V_op2, -value, false); - } else if (SIG_op2 && V_op1) { - inequality_graph.addEdge(SIG_op2, V_op1, value, true); - inequality_graph.addEdge(V_op1, SIG_op2, -value, false); - } -} - -/// Returns the sigma representing the Instruction I in BasicBlock BB. -/// Returns NULL in case there is no sigma for this Instruction in this -/// Basic Block. This methods assume that sigmas are the first instructions -/// in a block, and that there can be only two sigmas in a block. So it will -/// only look on the first two instructions of BasicBlock BB. -PHINode *ABCD::findSigma(BasicBlock *BB, Instruction *I) { - // BB has more than one predecessor, BB cannot have sigmas. - if (I == NULL || BB->getSinglePredecessor() == NULL) - return NULL; - - BasicBlock::iterator begin = BB->begin(); - BasicBlock::iterator end = BB->end(); - - for (unsigned i = 0; i < 2 && begin != end; ++i, ++begin) { - Instruction *I_succ = begin; - if (PHINode *PN = dyn_cast<PHINode>(I_succ)) - if (PN->getIncomingValue(0) == I) - return PN; - } - - return NULL; -} - -/// Original ABCD algorithm to prove redundant checks. -/// This implementation works on any kind of inequality branch. -bool ABCD::demandProve(Value *a, Value *b, int c, bool upper_bound) { - int32_t width = cast<IntegerType>(a->getType())->getBitWidth(); - Bound bound(APInt(width, c), upper_bound); - - mem_result.clear(); - active.clear(); - - ProveResult res = prove(a, b, bound, 0); - return res != False; -} - -/// Prove that distance between b and a is <= bound -ABCD::ProveResult ABCD::prove(Value *a, Value *b, const Bound &bound, - unsigned level) { - // if (C[b-a<=e] == True for some e <= bound - // Same or stronger difference was already proven - if (mem_result.hasTrue(b, bound)) - return True; - - // if (C[b-a<=e] == False for some e >= bound - // Same or weaker difference was already disproved - if (mem_result.hasFalse(b, bound)) - return False; - - // if (C[b-a<=e] == Reduced for some e <= bound - // b is on a cycle that was reduced for same or stronger difference - if (mem_result.hasReduced(b, bound)) - return Reduced; - - // traversal reached the source vertex - if (a == b && Bound::geq(bound, APInt(bound.getBitWidth(), 0, true))) - return True; - - // if b has no predecessor then fail - if (!inequality_graph.hasEdge(b, bound.isUpperBound())) - return False; - - // a cycle was encountered - if (active.count(b)) { - if (Bound::leq(*active.lookup(b), bound)) - return Reduced; // a "harmless" cycle - - return False; // an amplifying cycle - } - - active[b] = &bound; - PHINode *PN = dyn_cast<PHINode>(b); - - // Test if a Value is a Phi. If it is a PHINode with more than 1 incoming - // value, then it is a phi, if it has 1 incoming value it is a sigma. - if (PN && PN->getNumIncomingValues() > 1) - updateMemDistance(a, b, bound, level, min); - else - updateMemDistance(a, b, bound, level, max); - - active.erase(b); - - ABCD::ProveResult res = mem_result.getBoundResult(b, bound); - return res; -} - -/// Updates the distance value for a and b -void ABCD::updateMemDistance(Value *a, Value *b, const Bound &bound, - unsigned level, meet_function meet) { - ABCD::ProveResult res = (meet == max) ? False : True; - - SmallVector<Edge, 16> Edges = inequality_graph.getEdges(b); - SmallVector<Edge, 16>::iterator begin = Edges.begin(), end = Edges.end(); - - for (; begin != end ; ++begin) { - if (((res >= Reduced) && (meet == max)) || - ((res == False) && (meet == min))) { - break; - } - const Edge &in = *begin; - if (in.isUpperBound() == bound.isUpperBound()) { - Value *succ = in.getVertex(); - res = meet(res, prove(a, succ, Bound(bound, in.getValue()), - level+1)); - } - } - - mem_result.updateBound(b, bound, res); -} - -/// Return the stored result for this bound -ABCD::ProveResult ABCD::MemoizedResultChart::getResult(const Bound &bound)const{ - if (max_false && Bound::leq(bound, *max_false)) - return False; - if (min_true && Bound::leq(*min_true, bound)) - return True; - if (min_reduced && Bound::leq(*min_reduced, bound)) - return Reduced; - return False; -} - -/// Stores a false found -void ABCD::MemoizedResultChart::addFalse(const Bound &bound) { - if (!max_false || Bound::leq(*max_false, bound)) - max_false.reset(new Bound(bound)); - - if (Bound::eq(max_false.get(), min_reduced.get())) - min_reduced.reset(new Bound(Bound::createIncrement(*min_reduced))); - if (Bound::eq(max_false.get(), min_true.get())) - min_true.reset(new Bound(Bound::createIncrement(*min_true))); - if (Bound::eq(min_reduced.get(), min_true.get())) - min_reduced.reset(); - clearRedundantReduced(); -} - -/// Stores a true found -void ABCD::MemoizedResultChart::addTrue(const Bound &bound) { - if (!min_true || Bound::leq(bound, *min_true)) - min_true.reset(new Bound(bound)); - - if (Bound::eq(min_true.get(), min_reduced.get())) - min_reduced.reset(new Bound(Bound::createDecrement(*min_reduced))); - if (Bound::eq(min_true.get(), max_false.get())) - max_false.reset(new Bound(Bound::createDecrement(*max_false))); - if (Bound::eq(max_false.get(), min_reduced.get())) - min_reduced.reset(); - clearRedundantReduced(); -} - -/// Stores a Reduced found -void ABCD::MemoizedResultChart::addReduced(const Bound &bound) { - if (!min_reduced || Bound::leq(bound, *min_reduced)) - min_reduced.reset(new Bound(bound)); - - if (Bound::eq(min_reduced.get(), min_true.get())) - min_true.reset(new Bound(Bound::createIncrement(*min_true))); - if (Bound::eq(min_reduced.get(), max_false.get())) - max_false.reset(new Bound(Bound::createDecrement(*max_false))); -} - -/// Clears redundant reduced -/// If a min_true is smaller than a min_reduced then the min_reduced -/// is unnecessary and then removed. It also works for min_reduced -/// begin smaller than max_false. -void ABCD::MemoizedResultChart::clearRedundantReduced() { - if (min_true && min_reduced && Bound::lt(*min_true, *min_reduced)) - min_reduced.reset(); - if (max_false && min_reduced && Bound::lt(*min_reduced, *max_false)) - min_reduced.reset(); -} - -/// Stores the bound found -void ABCD::MemoizedResult::updateBound(Value *b, const Bound &bound, - const ProveResult res) { - if (res == False) { - map[b].addFalse(bound); - } else if (res == True) { - map[b].addTrue(bound); - } else { - map[b].addReduced(bound); - } -} - -/// Adds an edge from V_from to V_to with weight value -void ABCD::InequalityGraph::addEdge(Value *V_to, Value *V_from, - APInt value, bool upper) { - assert(V_from->getType() == V_to->getType()); - assert(cast<IntegerType>(V_from->getType())->getBitWidth() == - value.getBitWidth()); - - graph[V_from].push_back(Edge(V_to, value, upper)); -} - -/// Test if there is any edge from V in the upper direction -bool ABCD::InequalityGraph::hasEdge(Value *V, bool upper) const { - SmallVector<Edge, 16> it = graph.lookup(V); - - SmallVector<Edge, 16>::iterator begin = it.begin(); - SmallVector<Edge, 16>::iterator end = it.end(); - for (; begin != end; ++begin) { - if (begin->isUpperBound() == upper) { - return true; - } - } - return false; -} - -/// Prints the header of the dot file -void ABCD::InequalityGraph::printHeader(raw_ostream &OS, Function &F) const { - OS << "digraph dotgraph {\n"; - OS << "label=\"Inequality Graph for \'"; - OS << F.getNameStr() << "\' function\";\n"; - OS << "node [shape=record,fontname=\"Times-Roman\",fontsize=14];\n"; -} - -/// Prints the body of the dot file -void ABCD::InequalityGraph::printBody(raw_ostream &OS) const { - DenseMap<Value *, SmallVector<Edge, 16> >::const_iterator begin = - graph.begin(), end = graph.end(); - - for (; begin != end ; ++begin) { - SmallVector<Edge, 16>::const_iterator begin_par = - begin->second.begin(), end_par = begin->second.end(); - Value *source = begin->first; - - printVertex(OS, source); - - for (; begin_par != end_par ; ++begin_par) { - const Edge &edge = *begin_par; - printEdge(OS, source, edge); - } - } -} - -/// Prints vertex source to the dot file -/// -void ABCD::InequalityGraph::printVertex(raw_ostream &OS, Value *source) const { - OS << "\""; - printName(OS, source); - OS << "\""; - OS << " [label=\"{"; - printName(OS, source); - OS << "}\"];\n"; -} - -/// Prints the edge to the dot file -void ABCD::InequalityGraph::printEdge(raw_ostream &OS, Value *source, - const Edge &edge) const { - Value *dest = edge.getVertex(); - APInt value = edge.getValue(); - bool upper = edge.isUpperBound(); - - OS << "\""; - printName(OS, source); - OS << "\""; - OS << " -> "; - OS << "\""; - printName(OS, dest); - OS << "\""; - OS << " [label=\"" << value << "\""; - if (upper) { - OS << "color=\"blue\""; - } else { - OS << "color=\"red\""; - } - OS << "];\n"; -} - -void ABCD::InequalityGraph::printName(raw_ostream &OS, Value *info) const { - if (ConstantInt *CI = dyn_cast<ConstantInt>(info)) { - OS << *CI; - } else { - if (!info->hasName()) { - info->setName("V"); - } - OS << info->getNameStr(); - } -} - -/// createABCDPass - The public interface to this file... -FunctionPass *llvm::createABCDPass() { - return new ABCD(); -} diff --git a/lib/Transforms/Scalar/CMakeLists.txt b/lib/Transforms/Scalar/CMakeLists.txt index c39e859..69b4c34 100644 --- a/lib/Transforms/Scalar/CMakeLists.txt +++ b/lib/Transforms/Scalar/CMakeLists.txt @@ -1,5 +1,4 @@ add_llvm_library(LLVMScalarOpts - ABCD.cpp ADCE.cpp BasicBlockPlacement.cpp CodeGenPrepare.cpp diff --git a/lib/Transforms/Utils/CMakeLists.txt b/lib/Transforms/Utils/CMakeLists.txt index dec227a..61cbeb2 100644 --- a/lib/Transforms/Utils/CMakeLists.txt +++ b/lib/Transforms/Utils/CMakeLists.txt @@ -20,7 +20,6 @@ add_llvm_library(LLVMTransformUtils Mem2Reg.cpp PromoteMemoryToRegister.cpp SSAUpdater.cpp - SSI.cpp SimplifyCFG.cpp UnifyFunctionExitNodes.cpp ValueMapper.cpp diff --git a/lib/Transforms/Utils/SSI.cpp b/lib/Transforms/Utils/SSI.cpp deleted file mode 100644 index 81523d3..0000000 --- a/lib/Transforms/Utils/SSI.cpp +++ /dev/null @@ -1,433 +0,0 @@ -//===------------------- SSI.cpp - Creates SSI Representation -------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This pass converts a list of variables to the Static Single Information -// form. This is a program representation described by Scott Ananian in his -// Master Thesis: "The Static Single Information Form (1999)". -// We are building an on-demand representation, that is, we do not convert -// every single variable in the target function to SSI form. Rather, we receive -// a list of target variables that must be converted. We also do not -// completely convert a target variable to the SSI format. Instead, we only -// change the variable in the points where new information can be attached -// to its live range, that is, at branch points. -// -//===----------------------------------------------------------------------===// - -#define DEBUG_TYPE "ssi" - -#include "llvm/Transforms/Scalar.h" -#include "llvm/Transforms/Utils/SSI.h" -#include "llvm/ADT/Statistic.h" -#include "llvm/Analysis/Dominators.h" - -using namespace llvm; - -static const std::string SSI_PHI = "SSI_phi"; -static const std::string SSI_SIG = "SSI_sigma"; - -STATISTIC(NumSigmaInserted, "Number of sigma functions inserted"); -STATISTIC(NumPhiInserted, "Number of phi functions inserted"); - -void SSI::getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequiredTransitive<DominanceFrontier>(); - AU.addRequiredTransitive<DominatorTree>(); - AU.setPreservesAll(); -} - -bool SSI::runOnFunction(Function &F) { - DT_ = &getAnalysis<DominatorTree>(); - return false; -} - -/// This methods creates the SSI representation for the list of values -/// received. It will only create SSI representation if a value is used -/// to decide a branch. Repeated values are created only once. -/// -void SSI::createSSI(SmallVectorImpl<Instruction *> &value) { - init(value); - - SmallPtrSet<Instruction*, 4> needConstruction; - for (SmallVectorImpl<Instruction*>::iterator I = value.begin(), - E = value.end(); I != E; ++I) - if (created.insert(*I)) - needConstruction.insert(*I); - - insertSigmaFunctions(needConstruction); - - // Test if there is a need to transform to SSI - if (!needConstruction.empty()) { - insertPhiFunctions(needConstruction); - renameInit(needConstruction); - rename(DT_->getRoot()); - fixPhis(); - } - - clean(); -} - -/// Insert sigma functions (a sigma function is a phi function with one -/// operator) -/// -void SSI::insertSigmaFunctions(SmallPtrSet<Instruction*, 4> &value) { - for (SmallPtrSet<Instruction*, 4>::iterator I = value.begin(), - E = value.end(); I != E; ++I) { - for (Value::use_iterator begin = (*I)->use_begin(), - end = (*I)->use_end(); begin != end; ++begin) { - // Test if the Use of the Value is in a comparator - if (CmpInst *CI = dyn_cast<CmpInst>(*begin)) { - // Iterates through all uses of CmpInst - for (Value::use_iterator begin_ci = CI->use_begin(), - end_ci = CI->use_end(); begin_ci != end_ci; ++begin_ci) { - // Test if any use of CmpInst is in a Terminator - if (TerminatorInst *TI = dyn_cast<TerminatorInst>(*begin_ci)) { - insertSigma(TI, *I); - } - } - } - } - } -} - -/// Inserts Sigma Functions in every BasicBlock successor to Terminator -/// Instruction TI. All inserted Sigma Function are related to Instruction I. -/// -void SSI::insertSigma(TerminatorInst *TI, Instruction *I) { - // Basic Block of the Terminator Instruction - BasicBlock *BB = TI->getParent(); - for (unsigned i = 0, e = TI->getNumSuccessors(); i < e; ++i) { - // Next Basic Block - BasicBlock *BB_next = TI->getSuccessor(i); - if (BB_next != BB && - BB_next->getSinglePredecessor() != NULL && - dominateAny(BB_next, I)) { - PHINode *PN = PHINode::Create(I->getType(), SSI_SIG, BB_next->begin()); - PN->addIncoming(I, BB); - sigmas[PN] = I; - created.insert(PN); - defsites[I].push_back(BB_next); - ++NumSigmaInserted; - } - } -} - -/// Insert phi functions when necessary -/// -void SSI::insertPhiFunctions(SmallPtrSet<Instruction*, 4> &value) { - DominanceFrontier *DF = &getAnalysis<DominanceFrontier>(); - for (SmallPtrSet<Instruction*, 4>::iterator I = value.begin(), - E = value.end(); I != E; ++I) { - // Test if there were any sigmas for this variable - SmallPtrSet<BasicBlock *, 16> BB_visited; - - // Insert phi functions if there is any sigma function - while (!defsites[*I].empty()) { - - BasicBlock *BB = defsites[*I].back(); - - defsites[*I].pop_back(); - DominanceFrontier::iterator DF_BB = DF->find(BB); - - // The BB is unreachable. Skip it. - if (DF_BB == DF->end()) - continue; - - // Iterates through all the dominance frontier of BB - for (std::set<BasicBlock *>::iterator DF_BB_begin = - DF_BB->second.begin(), DF_BB_end = DF_BB->second.end(); - DF_BB_begin != DF_BB_end; ++DF_BB_begin) { - BasicBlock *BB_dominated = *DF_BB_begin; - - // Test if has not yet visited this node and if the - // original definition dominates this node - if (BB_visited.insert(BB_dominated) && - DT_->properlyDominates(value_original[*I], BB_dominated) && - dominateAny(BB_dominated, *I)) { - PHINode *PN = PHINode::Create( - (*I)->getType(), SSI_PHI, BB_dominated->begin()); - phis.insert(std::make_pair(PN, *I)); - created.insert(PN); - - defsites[*I].push_back(BB_dominated); - ++NumPhiInserted; - } - } - } - BB_visited.clear(); - } -} - -/// Some initialization for the rename part -/// -void SSI::renameInit(SmallPtrSet<Instruction*, 4> &value) { - for (SmallPtrSet<Instruction*, 4>::iterator I = value.begin(), - E = value.end(); I != E; ++I) - value_stack[*I].push_back(*I); -} - -/// Renames all variables in the specified BasicBlock. -/// Only variables that need to be rename will be. -/// -void SSI::rename(BasicBlock *BB) { - SmallPtrSet<Instruction*, 8> defined; - - // Iterate through instructions and make appropriate renaming. - // For SSI_PHI (b = PHI()), store b at value_stack as a new - // definition of the variable it represents. - // For SSI_SIG (b = PHI(a)), substitute a with the current - // value of a, present in the value_stack. - // Then store bin the value_stack as the new definition of a. - // For all other instructions (b = OP(a, c, d, ...)), we need to substitute - // all operands with its current value, present in value_stack. - for (BasicBlock::iterator begin = BB->begin(), end = BB->end(); - begin != end; ++begin) { - Instruction *I = begin; - if (PHINode *PN = dyn_cast<PHINode>(I)) { // Treat PHI functions - Instruction* position; - - // Treat SSI_PHI - if ((position = getPositionPhi(PN))) { - value_stack[position].push_back(PN); - defined.insert(position); - // Treat SSI_SIG - } else if ((position = getPositionSigma(PN))) { - substituteUse(I); - value_stack[position].push_back(PN); - defined.insert(position); - } - - // Treat all other PHI functions - else { - substituteUse(I); - } - } - - // Treat all other functions - else { - substituteUse(I); - } - } - - // This loop iterates in all BasicBlocks that are successors of the current - // BasicBlock. For each SSI_PHI instruction found, insert an operand. - // This operand is the current operand in value_stack for the variable - // in "position". And the BasicBlock this operand represents is the current - // BasicBlock. - for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) { - BasicBlock *BB_succ = *SI; - - for (BasicBlock::iterator begin = BB_succ->begin(), - notPhi = BB_succ->getFirstNonPHI(); begin != *notPhi; ++begin) { - Instruction *I = begin; - PHINode *PN = dyn_cast<PHINode>(I); - Instruction* position; - if (PN && ((position = getPositionPhi(PN)))) { - PN->addIncoming(value_stack[position].back(), BB); - } - } - } - - // This loop calls rename on all children from this block. This time children - // refers to a successor block in the dominance tree. - DomTreeNode *DTN = DT_->getNode(BB); - for (DomTreeNode::iterator begin = DTN->begin(), end = DTN->end(); - begin != end; ++begin) { - DomTreeNodeBase<BasicBlock> *DTN_children = *begin; - BasicBlock *BB_children = DTN_children->getBlock(); - rename(BB_children); - } - - // Now we remove all inserted definitions of a variable from the top of - // the stack leaving the previous one as the top. - for (SmallPtrSet<Instruction*, 8>::iterator DI = defined.begin(), - DE = defined.end(); DI != DE; ++DI) - value_stack[*DI].pop_back(); -} - -/// Substitute any use in this instruction for the last definition of -/// the variable -/// -void SSI::substituteUse(Instruction *I) { - for (unsigned i = 0, e = I->getNumOperands(); i < e; ++i) { - Value *operand = I->getOperand(i); - for (DenseMap<Instruction*, SmallVector<Instruction*, 1> >::iterator - VI = value_stack.begin(), VE = value_stack.end(); VI != VE; ++VI) { - if (operand == VI->second.front() && - I != VI->second.back()) { - PHINode *PN_I = dyn_cast<PHINode>(I); - PHINode *PN_vs = dyn_cast<PHINode>(VI->second.back()); - - // If a phi created in a BasicBlock is used as an operand of another - // created in the same BasicBlock, this step marks this second phi, - // to fix this issue later. It cannot be fixed now, because the - // operands of the first phi are not final yet. - if (PN_I && PN_vs && - VI->second.back()->getParent() == I->getParent()) { - - phisToFix.insert(PN_I); - } - - I->setOperand(i, VI->second.back()); - break; - } - } - } -} - -/// Test if the BasicBlock BB dominates any use or definition of value. -/// If it dominates a phi instruction that is on the same BasicBlock, -/// that does not count. -/// -bool SSI::dominateAny(BasicBlock *BB, Instruction *value) { - for (Value::use_iterator begin = value->use_begin(), - end = value->use_end(); begin != end; ++begin) { - Instruction *I = cast<Instruction>(*begin); - BasicBlock *BB_father = I->getParent(); - if (BB == BB_father && isa<PHINode>(I)) - continue; - if (DT_->dominates(BB, BB_father)) { - return true; - } - } - return false; -} - -/// When there is a phi node that is created in a BasicBlock and it is used -/// as an operand of another phi function used in the same BasicBlock, -/// LLVM looks this as an error. So on the second phi, the first phi is called -/// P and the BasicBlock it incomes is B. This P will be replaced by the value -/// it has for BasicBlock B. It also includes undef values for predecessors -/// that were not included in the phi. -/// -void SSI::fixPhis() { - for (SmallPtrSet<PHINode *, 1>::iterator begin = phisToFix.begin(), - end = phisToFix.end(); begin != end; ++begin) { - PHINode *PN = *begin; - for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i) { - PHINode *PN_father = dyn_cast<PHINode>(PN->getIncomingValue(i)); - if (PN_father && PN->getParent() == PN_father->getParent() && - !DT_->dominates(PN->getParent(), PN->getIncomingBlock(i))) { - BasicBlock *BB = PN->getIncomingBlock(i); - int pos = PN_father->getBasicBlockIndex(BB); - PN->setIncomingValue(i, PN_father->getIncomingValue(pos)); - } - } - } - - for (DenseMapIterator<PHINode *, Instruction*> begin = phis.begin(), - end = phis.end(); begin != end; ++begin) { - PHINode *PN = begin->first; - BasicBlock *BB = PN->getParent(); - pred_iterator PI = pred_begin(BB), PE = pred_end(BB); - SmallVector<BasicBlock*, 8> Preds(PI, PE); - for (unsigned size = Preds.size(); - PI != PE && PN->getNumIncomingValues() != size; ++PI) { - bool found = false; - for (unsigned i = 0, pn_end = PN->getNumIncomingValues(); - i < pn_end; ++i) { - if (PN->getIncomingBlock(i) == *PI) { - found = true; - break; - } - } - if (!found) { - PN->addIncoming(UndefValue::get(PN->getType()), *PI); - } - } - } -} - -/// Return which variable (position on the vector of variables) this phi -/// represents on the phis list. -/// -Instruction* SSI::getPositionPhi(PHINode *PN) { - DenseMap<PHINode *, Instruction*>::iterator val = phis.find(PN); - if (val == phis.end()) - return 0; - else - return val->second; -} - -/// Return which variable (position on the vector of variables) this phi -/// represents on the sigmas list. -/// -Instruction* SSI::getPositionSigma(PHINode *PN) { - DenseMap<PHINode *, Instruction*>::iterator val = sigmas.find(PN); - if (val == sigmas.end()) - return 0; - else - return val->second; -} - -/// Initializes -/// -void SSI::init(SmallVectorImpl<Instruction *> &value) { - for (SmallVectorImpl<Instruction *>::iterator I = value.begin(), - E = value.end(); I != E; ++I) { - value_original[*I] = (*I)->getParent(); - defsites[*I].push_back((*I)->getParent()); - } -} - -/// Clean all used resources in this creation of SSI -/// -void SSI::clean() { - phis.clear(); - sigmas.clear(); - phisToFix.clear(); - - defsites.clear(); - value_stack.clear(); - value_original.clear(); -} - -/// createSSIPass - The public interface to this file... -/// -FunctionPass *llvm::createSSIPass() { return new SSI(); } - -char SSI::ID = 0; -INITIALIZE_PASS(SSI, "ssi", - "Static Single Information Construction", false, false); - -/// SSIEverything - A pass that runs createSSI on every non-void variable, -/// intended for debugging. -namespace { - struct SSIEverything : public FunctionPass { - static char ID; // Pass identification, replacement for typeid - SSIEverything() : FunctionPass(ID) {} - - bool runOnFunction(Function &F); - - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequired<SSI>(); - } - }; -} - -bool SSIEverything::runOnFunction(Function &F) { - SmallVector<Instruction *, 16> Insts; - SSI &ssi = getAnalysis<SSI>(); - - if (F.isDeclaration() || F.isIntrinsic()) return false; - - for (Function::iterator B = F.begin(), BE = F.end(); B != BE; ++B) - for (BasicBlock::iterator I = B->begin(), E = B->end(); I != E; ++I) - if (!I->getType()->isVoidTy()) - Insts.push_back(I); - - ssi.createSSI(Insts); - return true; -} - -/// createSSIEverythingPass - The public interface to this file... -/// -FunctionPass *llvm::createSSIEverythingPass() { return new SSIEverything(); } - -char SSIEverything::ID = 0; -INITIALIZE_PASS(SSIEverything, "ssi-everything", - "Static Single Information Construction", false, false); |