//
// The LLVM Compiler Infrastructure
//
-// This file was developed by the LLVM research group 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.
//
//===----------------------------------------------------------------------===//
//
#include "llvm/Function.h"
#include "llvm/Instructions.h"
#include "llvm/Type.h"
+#include "llvm/DerivedTypes.h"
+#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Assembly/Writer.h"
-#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
-#include "llvm/Support/ConstantRange.h"
#include "llvm/Support/CFG.h"
+#include "llvm/Support/Compiler.h"
+#include "llvm/Support/ConstantRange.h"
#include "llvm/Support/Debug.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/Statistic.h"
namespace {
class ValueInfo;
- class Relation {
+ class VISIBILITY_HIDDEN Relation {
Value *Val; // Relation to what value?
unsigned Rel; // SetCC or ICmp relation, or Add if no information
public:
- Relation(Value *V) : Val(V), Rel(Instruction::Add) {}
+ explicit Relation(Value *V) : Val(V), Rel(Instruction::Add) {}
bool operator<(const Relation &R) const { return Val < R.Val; }
Value *getValue() const { return Val; }
unsigned getRelation() const { return Rel; }
// relationships to other values in the program (specified with Relation) that
// are known to be valid in a region.
//
- class ValueInfo {
+ class VISIBILITY_HIDDEN ValueInfo {
// RelationShips - this value is know to have the specified relationships to
// other values. There can only be one entry per value, and this list is
// kept sorted by the Val field.
//
Value *Replacement;
public:
- ValueInfo(const Type *Ty)
- : Bounds(Ty->isIntegral() ? Ty : Type::Int32Ty), Replacement(0) {}
+ explicit ValueInfo(const Type *Ty)
+ : Bounds(Ty->isInteger() ? cast<IntegerType>(Ty)->getBitWidth() : 32),
+ Replacement(0) {}
// getBounds() - Return the constant bounds of the value...
const ConstantRange &getBounds() const { return Bounds; }
return *I;
// Insert and return the new relationship...
- return *Relationships.insert(I, V);
+ return *Relationships.insert(I, Relation(V));
}
const Relation *requestRelation(Value *V) const {
// the RegionInfo for their dominator, because anything known in a dominator
// is known to be true in a dominated block as well.
//
- class RegionInfo {
+ class VISIBILITY_HIDDEN RegionInfo {
BasicBlock *BB;
// ValueMap - Tracks the ValueInformation known for this region
typedef std::map<Value*, ValueInfo> ValueMapTy;
ValueMapTy ValueMap;
public:
- RegionInfo(BasicBlock *bb) : BB(bb) {}
+ explicit RegionInfo(BasicBlock *bb) : BB(bb) {}
// getEntryBlock - Return the block that dominates all of the members of
// this region.
};
/// CEE - Correlated Expression Elimination
- class CEE : public FunctionPass {
+ class VISIBILITY_HIDDEN CEE : public FunctionPass {
std::map<Value*, unsigned> RankMap;
std::map<BasicBlock*, RegionInfo> RegionInfoMap;
- ETForest *EF;
DominatorTree *DT;
public:
+ static char ID; // Pass identification, replacement for typeid
+ CEE() : FunctionPass((intptr_t)&ID) {}
+
virtual bool runOnFunction(Function &F);
// We don't modify the program, so we preserve all analyses
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
- AU.addRequired<ETForest>();
AU.addRequired<DominatorTree>();
AU.addRequiredID(BreakCriticalEdgesID);
};
bool SimplifyBasicBlock(BasicBlock &BB, const RegionInfo &RI);
bool SimplifyInstruction(Instruction *Inst, const RegionInfo &RI);
};
+
+ char CEE::ID = 0;
RegisterPass<CEE> X("cee", "Correlated Expression Elimination");
}
// Traverse the dominator tree, computing information for each node in the
// tree. Note that our traversal will not even touch unreachable basic
// blocks.
- EF = &getAnalysis<ETForest>();
DT = &getAnalysis<DominatorTree>();
std::set<BasicBlock*> VisitedBlocks;
// blocks that are dominated by this one, we can safely propagate the
// information down now.
//
- DominatorTree::Node *BBN = (*DT)[BB];
- if (!RI.empty()) // Time opt: only propagate if we can change something
- for (unsigned i = 0, e = BBN->getChildren().size(); i != e; ++i) {
- BasicBlock *Dominated = BBN->getChildren()[i]->getBlock();
- assert(RegionInfoMap.find(Dominated) == RegionInfoMap.end() &&
+ DomTreeNode *BBDom = DT->getNode(BB);
+ if (!RI.empty()) { // Time opt: only propagate if we can change something
+ for (std::vector<DomTreeNode*>::iterator DI = BBDom->begin(),
+ E = BBDom->end(); DI != E; ++DI) {
+ BasicBlock *ChildBB = (*DI)->getBlock();
+ assert(RegionInfoMap.find(ChildBB) == RegionInfoMap.end() &&
"RegionInfo should be calculated in dominanace order!");
- getRegionInfo(Dominated) = RI;
+ getRegionInfo(ChildBB) = RI;
}
+ }
// Now that all of our successors have information if they deserve it,
// propagate any information our terminator instruction finds to our
}
// Now that all of our successors have information, recursively process them.
- for (unsigned i = 0, e = BBN->getChildren().size(); i != e; ++i)
- Changed |= TransformRegion(BBN->getChildren()[i]->getBlock(),VisitedBlocks);
+ for (std::vector<DomTreeNode*>::iterator DI = BBDom->begin(),
+ E = BBDom->end(); DI != E; ++DI) {
+ BasicBlock *ChildBB = (*DI)->getBlock();
+ Changed |= TransformRegion(ChildBB, VisitedBlocks);
+ }
return Changed;
}
} else if (CmpInst *CI = dyn_cast<CmpInst>(I)) {
Relation::KnownResult Res = getCmpResult(CI, NewRI);
if (Res == Relation::Unknown) return false;
- PropagateEquality(CI, ConstantInt::get(Res), NewRI);
+ PropagateEquality(CI, ConstantInt::get(Type::Int1Ty, Res), NewRI);
} else {
assert(isa<BranchInst>(*I) && "Unexpected instruction type!");
}
// Forward to the successor that corresponds to the branch we will take.
ForwardSuccessorTo(TI, SuccNo,
- BI->getSuccessor(!CB->getBoolValue()), NewRI);
+ BI->getSuccessor(!CB->getZExtValue()), NewRI);
return true;
}
// insert dead phi nodes, but it is more trouble to see if they are used than
// to just blindly insert them.
//
- if (EF->dominates(OldSucc, Dest)) {
+ if (DT->dominates(OldSucc, Dest)) {
// RegionExitBlocks - Find all of the blocks that are not dominated by Dest,
// but have predecessors that are. Additionally, prune down the set to only
// include blocks that are dominated by OldSucc as well.
for (Value::use_iterator I = Orig->use_begin(), E = Orig->use_end();
I != E; ++I)
if (Instruction *User = dyn_cast<Instruction>(*I))
- if (EF->dominates(RegionDominator, User->getParent()))
+ if (DT->dominates(RegionDominator, User->getParent()))
InstsToChange.push_back(User);
else if (PHINode *PN = dyn_cast<PHINode>(User)) {
PHIsToChange.push_back(PN);
PHINode *PN = PHIsToChange[i];
for (unsigned j = 0, e = PN->getNumIncomingValues(); j != e; ++j)
if (PN->getIncomingValue(j) == Orig &&
- EF->dominates(RegionDominator, PN->getIncomingBlock(j)))
+ DT->dominates(RegionDominator, PN->getIncomingBlock(j)))
PN->setIncomingValue(j, New);
}
// values that correspond to basic blocks in the region.
for (unsigned j = 0, e = PN->getNumIncomingValues(); j != e; ++j)
if (PN->getIncomingValue(j) == Orig &&
- EF->dominates(RegionDominator, PN->getIncomingBlock(j)))
+ DT->dominates(RegionDominator, PN->getIncomingBlock(j)))
PN->setIncomingValue(j, New);
} else {
static void CalcRegionExitBlocks(BasicBlock *Header, BasicBlock *BB,
std::set<BasicBlock*> &Visited,
- ETForest &EF,
+ DominatorTree &DT,
std::vector<BasicBlock*> &RegionExitBlocks) {
if (Visited.count(BB)) return;
Visited.insert(BB);
- if (EF.dominates(Header, BB)) { // Block in the region, recursively traverse
+ if (DT.dominates(Header, BB)) { // Block in the region, recursively traverse
for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I)
- CalcRegionExitBlocks(Header, *I, Visited, EF, RegionExitBlocks);
+ CalcRegionExitBlocks(Header, *I, Visited, DT, RegionExitBlocks);
} else {
// Header does not dominate this block, but we have a predecessor that does
// dominate us. Add ourself to the list.
std::set<BasicBlock*> Visited; // Don't infinite loop
// Recursively calculate blocks we are interested in...
- CalcRegionExitBlocks(BB, BB, Visited, *EF, RegionExitBlocks);
+ CalcRegionExitBlocks(BB, BB, Visited, *DT, RegionExitBlocks);
// Filter out blocks that are not dominated by OldSucc...
for (unsigned i = 0; i != RegionExitBlocks.size(); ) {
- if (EF->dominates(OldSucc, RegionExitBlocks[i]))
+ if (DT->dominates(OldSucc, RegionExitBlocks[i]))
++i; // Block is ok, keep it.
else {
// Move to end of list...
PI != PE; ++PI) {
// If the incoming edge is from the region dominated by BB, use BBVal,
// otherwise use OldVal.
- NewPN->addIncoming(EF->dominates(BB, *PI) ? BBVal : OldVal, *PI);
+ NewPN->addIncoming(DT->dominates(BB, *PI) ? BBVal : OldVal, *PI);
}
// Now make everyone dominated by this block use this new value!
// it's a constant, then see if the other one is one of a setcc instruction,
// an AND, OR, or XOR instruction.
//
- if (Op1->getType() == Type::Int1Ty)
- if (ConstantInt *CB = dyn_cast<ConstantInt>(Op1)) {
-
- if (Instruction *Inst = dyn_cast<Instruction>(Op0)) {
- // If we know that this instruction is an AND instruction, and the result
- // is true, this means that both operands to the OR are known to be true
- // as well.
- //
- if (CB->getBoolValue() && Inst->getOpcode() == Instruction::And) {
- PropagateEquality(Inst->getOperand(0), CB, RI);
- PropagateEquality(Inst->getOperand(1), CB, RI);
- }
-
- // If we know that this instruction is an OR instruction, and the result
- // is false, this means that both operands to the OR are know to be false
- // as well.
- //
- if (!CB->getBoolValue() && Inst->getOpcode() == Instruction::Or) {
- PropagateEquality(Inst->getOperand(0), CB, RI);
- PropagateEquality(Inst->getOperand(1), CB, RI);
- }
+ ConstantInt *CB = dyn_cast<ConstantInt>(Op1);
+ if (CB && Op1->getType() == Type::Int1Ty) {
+ if (Instruction *Inst = dyn_cast<Instruction>(Op0)) {
+ // If we know that this instruction is an AND instruction, and the
+ // result is true, this means that both operands to the OR are known
+ // to be true as well.
+ //
+ if (CB->getZExtValue() && Inst->getOpcode() == Instruction::And) {
+ PropagateEquality(Inst->getOperand(0), CB, RI);
+ PropagateEquality(Inst->getOperand(1), CB, RI);
+ }
- // If we know that this instruction is a NOT instruction, we know that the
- // operand is known to be the inverse of whatever the current value is.
- //
- if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(Inst))
- if (BinaryOperator::isNot(BOp))
- PropagateEquality(BinaryOperator::getNotArgument(BOp),
- ConstantInt::get(!CB->getBoolValue()), RI);
-
- // If we know the value of a FCmp instruction, propagate the information
- // about the relation into this region as well.
- //
- if (FCmpInst *FCI = dyn_cast<FCmpInst>(Inst)) {
- if (CB->getBoolValue()) { // If we know the condition is true...
- // Propagate info about the LHS to the RHS & RHS to LHS
- PropagateRelation(FCI->getPredicate(), FCI->getOperand(0),
- FCI->getOperand(1), RI);
- PropagateRelation(FCI->getSwappedPredicate(),
- FCI->getOperand(1), FCI->getOperand(0), RI);
-
- } else { // If we know the condition is false...
- // We know the opposite of the condition is true...
- FCmpInst::Predicate C = FCI->getInversePredicate();
-
- PropagateRelation(C, FCI->getOperand(0), FCI->getOperand(1), RI);
- PropagateRelation(FCmpInst::getSwappedPredicate(C),
- FCI->getOperand(1), FCI->getOperand(0), RI);
- }
+ // If we know that this instruction is an OR instruction, and the result
+ // is false, this means that both operands to the OR are know to be
+ // false as well.
+ //
+ if (!CB->getZExtValue() && Inst->getOpcode() == Instruction::Or) {
+ PropagateEquality(Inst->getOperand(0), CB, RI);
+ PropagateEquality(Inst->getOperand(1), CB, RI);
+ }
+
+ // If we know that this instruction is a NOT instruction, we know that
+ // the operand is known to be the inverse of whatever the current
+ // value is.
+ //
+ if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(Inst))
+ if (BinaryOperator::isNot(BOp))
+ PropagateEquality(BinaryOperator::getNotArgument(BOp),
+ ConstantInt::get(Type::Int1Ty,
+ !CB->getZExtValue()), RI);
+
+ // If we know the value of a FCmp instruction, propagate the information
+ // about the relation into this region as well.
+ //
+ if (FCmpInst *FCI = dyn_cast<FCmpInst>(Inst)) {
+ if (CB->getZExtValue()) { // If we know the condition is true...
+ // Propagate info about the LHS to the RHS & RHS to LHS
+ PropagateRelation(FCI->getPredicate(), FCI->getOperand(0),
+ FCI->getOperand(1), RI);
+ PropagateRelation(FCI->getSwappedPredicate(),
+ FCI->getOperand(1), FCI->getOperand(0), RI);
+
+ } else { // If we know the condition is false...
+ // We know the opposite of the condition is true...
+ FCmpInst::Predicate C = FCI->getInversePredicate();
+
+ PropagateRelation(C, FCI->getOperand(0), FCI->getOperand(1), RI);
+ PropagateRelation(FCmpInst::getSwappedPredicate(C),
+ FCI->getOperand(1), FCI->getOperand(0), RI);
}
-
- // If we know the value of a ICmp instruction, propagate the information
- // about the relation into this region as well.
- //
- if (ICmpInst *ICI = dyn_cast<ICmpInst>(Inst)) {
- if (CB->getBoolValue()) { // If we know the condition is true...
- // Propagate info about the LHS to the RHS & RHS to LHS
- PropagateRelation(ICI->getPredicate(), ICI->getOperand(0),
- ICI->getOperand(1), RI);
- PropagateRelation(ICI->getSwappedPredicate(), ICI->getOperand(1),
- ICI->getOperand(1), RI);
-
- } else { // If we know the condition is false ...
- // We know the opposite of the condition is true...
- ICmpInst::Predicate C = ICI->getInversePredicate();
-
- PropagateRelation(C, ICI->getOperand(0), ICI->getOperand(1), RI);
- PropagateRelation(ICmpInst::getSwappedPredicate(C),
- ICI->getOperand(1), ICI->getOperand(0), RI);
- }
+ }
+
+ // If we know the value of a ICmp instruction, propagate the information
+ // about the relation into this region as well.
+ //
+ if (ICmpInst *ICI = dyn_cast<ICmpInst>(Inst)) {
+ if (CB->getZExtValue()) { // If we know the condition is true...
+ // Propagate info about the LHS to the RHS & RHS to LHS
+ PropagateRelation(ICI->getPredicate(), ICI->getOperand(0),
+ ICI->getOperand(1), RI);
+ PropagateRelation(ICI->getSwappedPredicate(), ICI->getOperand(1),
+ ICI->getOperand(1), RI);
+
+ } else { // If we know the condition is false ...
+ // We know the opposite of the condition is true...
+ ICmpInst::Predicate C = ICI->getInversePredicate();
+
+ PropagateRelation(C, ICI->getOperand(0), ICI->getOperand(1), RI);
+ PropagateRelation(ICmpInst::getSwappedPredicate(C),
+ ICI->getOperand(1), ICI->getOperand(0), RI);
}
}
}
+ }
// Propagate information about Op0 to Op1 & visa versa
PropagateRelation(ICmpInst::ICMP_EQ, Op0, Op1, RI);
// here. This check is also effectively checking to make sure that Inst
// is in the same function as our region (in case V is a global f.e.).
//
- if (EF->properlyDominates(Inst->getParent(), RI.getEntryBlock()))
+ if (DT->properlyDominates(Inst->getParent(), RI.getEntryBlock()))
IncorporateInstruction(Inst, RI);
}
}
// See if we can figure out a result for this instruction...
Relation::KnownResult Result = getCmpResult(CI, RI);
if (Result != Relation::Unknown) {
- PropagateEquality(CI, ConstantInt::get(Result != 0), RI);
+ PropagateEquality(CI, ConstantInt::get(Type::Int1Ty, Result != 0), RI);
}
}
}
// If we know that this value is a particular constant, set Replacement to
// the constant...
- Value *Replacement = VI.getBounds().getSingleElement();
+ Value *Replacement = 0;
+ const APInt * Rplcmnt = VI.getBounds().getSingleElement();
+ if (Rplcmnt)
+ Replacement = ConstantInt::get(*Rplcmnt);
// If this value is not known to be some constant, figure out the lowest
// rank value that it is known to be equal to (if anything).
DEBUG(cerr << "Replacing icmp with " << Result
<< " constant: " << *CI);
- CI->replaceAllUsesWith(ConstantInt::get((bool)Result));
+ CI->replaceAllUsesWith(ConstantInt::get(Type::Int1Ty, (bool)Result));
// The instruction is now dead, remove it from the program.
CI->getParent()->getInstList().erase(CI);
++NumCmpRemoved;
if (Constant *Result = ConstantFoldInstruction(CI)) {
// Wow, this is easy, directly eliminate the ICmpInst.
DEBUG(cerr << "Replacing cmp with constant fold: " << *CI);
- return cast<ConstantInt>(Result)->getBoolValue()
+ return cast<ConstantInt>(Result)->getZExtValue()
? Relation::KnownTrue : Relation::KnownFalse;
}
} else {
//
if (ConstantInt *C = dyn_cast<ConstantInt>(Op1)) {
// Check to see if we already know the result of this comparison...
- ConstantRange R = ConstantRange(predicate, C);
- ConstantRange Int = R.intersectWith(Op0VI->getBounds(),
- ICmpInst::isSignedPredicate(ICmpInst::Predicate(predicate)));
+ ICmpInst::Predicate ipred = ICmpInst::Predicate(predicate);
+ ConstantRange R = ICmpInst::makeConstantRange(ipred, C->getValue());
+ ConstantRange Int = R.intersectWith(Op0VI->getBounds());
// If the intersection of the two ranges is empty, then the condition
// could never be true!
//
if (ConstantInt *C = dyn_cast<ConstantInt>(Val))
if (Op >= ICmpInst::FIRST_ICMP_PREDICATE &&
- Op <= ICmpInst::LAST_ICMP_PREDICATE)
- if (ConstantRange(Op, C).intersectWith(VI.getBounds(),
- ICmpInst::isSignedPredicate(ICmpInst::Predicate(Op))).isEmptySet())
+ Op <= ICmpInst::LAST_ICMP_PREDICATE) {
+ ICmpInst::Predicate ipred = ICmpInst::Predicate(Op);
+ if (ICmpInst::makeConstantRange(ipred, C->getValue())
+ .intersectWith(VI.getBounds()).isEmptySet())
return true;
+ }
switch (Rel) {
default: assert(0 && "Unknown Relationship code!");
//
if (ConstantInt *C = dyn_cast<ConstantInt>(Val))
if (Op >= ICmpInst::FIRST_ICMP_PREDICATE &&
- Op <= ICmpInst::LAST_ICMP_PREDICATE)
- VI.getBounds() = ConstantRange(Op, C).intersectWith(VI.getBounds(),
- ICmpInst::isSignedPredicate(ICmpInst::Predicate(Op)));
+ Op <= ICmpInst::LAST_ICMP_PREDICATE) {
+ ICmpInst::Predicate ipred = ICmpInst::Predicate(Op);
+ VI.getBounds() =
+ ICmpInst::makeConstantRange(ipred, C->getValue())
+ .intersectWith(VI.getBounds());
+ }
switch (Rel) {
default: assert(0 && "Unknown prior value!");
}
return false;
case FCmpInst::FCMP_OGE:
- return Op == FCmpInst::FCMP_OLT;
if (Op == FCmpInst::FCMP_OEQ || Op == FCmpInst::FCMP_OGT) {
Rel = Op;
return true;
projects / oota-llvm.git / blobdiff