summaryrefslogtreecommitdiff
path: root/lib/Transforms
diff options
context:
space:
mode:
authorRoman Divacky <rdivacky@FreeBSD.org>2010-04-02 08:54:30 +0000
committerRoman Divacky <rdivacky@FreeBSD.org>2010-04-02 08:54:30 +0000
commit104bd8179fb5f6551c65c94ebcd0a4918b060189 (patch)
treecf5763d092b81cecc168fa28032247ee495d06e2 /lib/Transforms
parent2f12f10af369d468b14617276446166383d692ed (diff)
Notes
Diffstat (limited to 'lib/Transforms')
-rw-r--r--lib/Transforms/IPO/ArgumentPromotion.cpp15
-rw-r--r--lib/Transforms/IPO/DeadArgumentElimination.cpp97
-rw-r--r--lib/Transforms/IPO/GlobalOpt.cpp74
-rw-r--r--lib/Transforms/IPO/PruneEH.cpp2
-rw-r--r--lib/Transforms/InstCombine/InstCombineCalls.cpp2
-rw-r--r--lib/Transforms/Scalar/ABCD.cpp253
-rw-r--r--lib/Transforms/Scalar/CodeGenPrepare.cpp8
-rw-r--r--lib/Transforms/Scalar/GVN.cpp14
-rw-r--r--lib/Transforms/Scalar/IndVarSimplify.cpp34
-rw-r--r--lib/Transforms/Scalar/LoopStrengthReduce.cpp7
-rw-r--r--lib/Transforms/Scalar/Reg2Mem.cpp2
-rw-r--r--lib/Transforms/Scalar/SCCP.cpp19
-rw-r--r--lib/Transforms/Scalar/SimplifyCFGPass.cpp2
-rw-r--r--lib/Transforms/Scalar/SimplifyLibCalls.cpp26
-rw-r--r--lib/Transforms/Utils/AddrModeMatcher.cpp5
-rw-r--r--lib/Transforms/Utils/BreakCriticalEdges.cpp2
-rw-r--r--lib/Transforms/Utils/BuildLibCalls.cpp28
-rw-r--r--lib/Transforms/Utils/LowerInvoke.cpp4
-rw-r--r--lib/Transforms/Utils/PromoteMemoryToRegister.cpp2
-rw-r--r--lib/Transforms/Utils/SSAUpdater.cpp497
-rw-r--r--lib/Transforms/Utils/SimplifyCFG.cpp8
21 files changed, 648 insertions, 453 deletions
diff --git a/lib/Transforms/IPO/ArgumentPromotion.cpp b/lib/Transforms/IPO/ArgumentPromotion.cpp
index 7cb13671bca57..40a87e880d7bf 100644
--- a/lib/Transforms/IPO/ArgumentPromotion.cpp
+++ b/lib/Transforms/IPO/ArgumentPromotion.cpp
@@ -623,6 +623,7 @@ CallGraphNode *ArgPromotion::DoPromotion(Function *F,
SmallVector<Value*, 16> Args;
while (!F->use_empty()) {
CallSite CS = CallSite::get(F->use_back());
+ assert(CS.getCalledFunction() == F);
Instruction *Call = CS.getInstruction();
const AttrListPtr &CallPAL = CS.getAttributes();
@@ -660,7 +661,7 @@ CallGraphNode *ArgPromotion::DoPromotion(Function *F,
// Non-dead argument: insert GEPs and loads as appropriate.
ScalarizeTable &ArgIndices = ScalarizedElements[I];
// Store the Value* version of the indices in here, but declare it now
- // for reuse
+ // for reuse.
std::vector<Value*> Ops;
for (ScalarizeTable::iterator SI = ArgIndices.begin(),
E = ArgIndices.end(); SI != E; ++SI) {
@@ -677,16 +678,20 @@ CallGraphNode *ArgPromotion::DoPromotion(Function *F,
Type::getInt32Ty(F->getContext()) :
Type::getInt64Ty(F->getContext()));
Ops.push_back(ConstantInt::get(IdxTy, *II));
- // Keep track of the type we're currently indexing
+ // Keep track of the type we're currently indexing.
ElTy = cast<CompositeType>(ElTy)->getTypeAtIndex(*II);
}
- // And create a GEP to extract those indices
+ // And create a GEP to extract those indices.
V = GetElementPtrInst::Create(V, Ops.begin(), Ops.end(),
V->getName()+".idx", Call);
Ops.clear();
AA.copyValue(OrigLoad->getOperand(0), V);
}
- Args.push_back(new LoadInst(V, V->getName()+".val", Call));
+ // Since we're replacing a load make sure we take the alignment
+ // of the previous load.
+ LoadInst *newLoad = new LoadInst(V, V->getName()+".val", Call);
+ newLoad->setAlignment(OrigLoad->getAlignment());
+ Args.push_back(newLoad);
AA.copyValue(OrigLoad, Args.back());
}
}
@@ -694,7 +699,7 @@ CallGraphNode *ArgPromotion::DoPromotion(Function *F,
if (ExtraArgHack)
Args.push_back(Constant::getNullValue(Type::getInt32Ty(F->getContext())));
- // Push any varargs arguments on the list
+ // Push any varargs arguments on the list.
for (; AI != CS.arg_end(); ++AI, ++ArgIndex) {
Args.push_back(*AI);
if (Attributes Attrs = CallPAL.getParamAttributes(ArgIndex))
diff --git a/lib/Transforms/IPO/DeadArgumentElimination.cpp b/lib/Transforms/IPO/DeadArgumentElimination.cpp
index f386ed78b5f54..227602d19f568 100644
--- a/lib/Transforms/IPO/DeadArgumentElimination.cpp
+++ b/lib/Transforms/IPO/DeadArgumentElimination.cpp
@@ -50,7 +50,7 @@ namespace {
/// argument. Used so that arguments and return values can be used
/// interchangably.
struct RetOrArg {
- RetOrArg(const Function* F, unsigned Idx, bool IsArg) : F(F), Idx(Idx),
+ RetOrArg(const Function *F, unsigned Idx, bool IsArg) : F(F), Idx(Idx),
IsArg(IsArg) {}
const Function *F;
unsigned Idx;
@@ -72,7 +72,7 @@ namespace {
}
std::string getDescription() const {
- return std::string((IsArg ? "Argument #" : "Return value #"))
+ return std::string((IsArg ? "Argument #" : "Return value #"))
+ utostr(Idx) + " of function " + F->getNameStr();
}
};
@@ -129,11 +129,11 @@ namespace {
private:
Liveness MarkIfNotLive(RetOrArg Use, UseVector &MaybeLiveUses);
- Liveness SurveyUse(Value::use_iterator U, UseVector &MaybeLiveUses,
+ Liveness SurveyUse(Value::const_use_iterator U, UseVector &MaybeLiveUses,
unsigned RetValNum = 0);
- Liveness SurveyUses(Value *V, UseVector &MaybeLiveUses);
+ Liveness SurveyUses(const Value *V, UseVector &MaybeLiveUses);
- void SurveyFunction(Function &F);
+ void SurveyFunction(const Function &F);
void MarkValue(const RetOrArg &RA, Liveness L,
const UseVector &MaybeLiveUses);
void MarkLive(const RetOrArg &RA);
@@ -196,7 +196,7 @@ bool DAE::DeleteDeadVarargs(Function &Fn) {
// Start by computing a new prototype for the function, which is the same as
// the old function, but doesn't have isVarArg set.
const FunctionType *FTy = Fn.getFunctionType();
-
+
std::vector<const Type*> Params(FTy->param_begin(), FTy->param_end());
FunctionType *NFTy = FunctionType::get(FTy->getReturnType(),
Params, false);
@@ -225,7 +225,7 @@ bool DAE::DeleteDeadVarargs(Function &Fn) {
SmallVector<AttributeWithIndex, 8> AttributesVec;
for (unsigned i = 0; PAL.getSlot(i).Index <= NumArgs; ++i)
AttributesVec.push_back(PAL.getSlot(i));
- if (Attributes FnAttrs = PAL.getFnAttributes())
+ if (Attributes FnAttrs = PAL.getFnAttributes())
AttributesVec.push_back(AttributeWithIndex::get(~0, FnAttrs));
PAL = AttrListPtr::get(AttributesVec.begin(), AttributesVec.end());
}
@@ -280,7 +280,7 @@ bool DAE::DeleteDeadVarargs(Function &Fn) {
/// for void functions and 1 for functions not returning a struct. It returns
/// the number of struct elements for functions returning a struct.
static unsigned NumRetVals(const Function *F) {
- if (F->getReturnType() == Type::getVoidTy(F->getContext()))
+ if (F->getReturnType()->isVoidTy())
return 0;
else if (const StructType *STy = dyn_cast<StructType>(F->getReturnType()))
return STy->getNumElements();
@@ -305,15 +305,15 @@ DAE::Liveness DAE::MarkIfNotLive(RetOrArg Use, UseVector &MaybeLiveUses) {
/// SurveyUse - This looks at a single use of an argument or return value
/// and determines if it should be alive or not. Adds this use to MaybeLiveUses
-/// if it causes the used value to become MaybeAlive.
+/// if it causes the used value to become MaybeLive.
///
/// RetValNum is the return value number to use when this use is used in a
/// return instruction. This is used in the recursion, you should always leave
/// it at 0.
-DAE::Liveness DAE::SurveyUse(Value::use_iterator U, UseVector &MaybeLiveUses,
- unsigned RetValNum) {
- Value *V = *U;
- if (ReturnInst *RI = dyn_cast<ReturnInst>(V)) {
+DAE::Liveness DAE::SurveyUse(Value::const_use_iterator U,
+ UseVector &MaybeLiveUses, unsigned RetValNum) {
+ const User *V = *U;
+ if (const ReturnInst *RI = dyn_cast<ReturnInst>(V)) {
// The value is returned from a function. It's only live when the
// function's return value is live. We use RetValNum here, for the case
// that U is really a use of an insertvalue instruction that uses the
@@ -322,7 +322,7 @@ DAE::Liveness DAE::SurveyUse(Value::use_iterator U, UseVector &MaybeLiveUses,
// We might be live, depending on the liveness of Use.
return MarkIfNotLive(Use, MaybeLiveUses);
}
- if (InsertValueInst *IV = dyn_cast<InsertValueInst>(V)) {
+ if (const InsertValueInst *IV = dyn_cast<InsertValueInst>(V)) {
if (U.getOperandNo() != InsertValueInst::getAggregateOperandIndex()
&& IV->hasIndices())
// The use we are examining is inserted into an aggregate. Our liveness
@@ -334,7 +334,7 @@ DAE::Liveness DAE::SurveyUse(Value::use_iterator U, UseVector &MaybeLiveUses,
// we don't change RetValNum, but do survey all our uses.
Liveness Result = MaybeLive;
- for (Value::use_iterator I = IV->use_begin(),
+ for (Value::const_use_iterator I = IV->use_begin(),
E = V->use_end(); I != E; ++I) {
Result = SurveyUse(I, MaybeLiveUses, RetValNum);
if (Result == Live)
@@ -342,24 +342,24 @@ DAE::Liveness DAE::SurveyUse(Value::use_iterator U, UseVector &MaybeLiveUses,
}
return Result;
}
- CallSite CS = CallSite::get(V);
- if (CS.getInstruction()) {
- Function *F = CS.getCalledFunction();
+
+ if (ImmutableCallSite CS = V) {
+ const Function *F = CS.getCalledFunction();
if (F) {
// Used in a direct call.
-
+
// Find the argument number. We know for sure that this use is an
// argument, since if it was the function argument this would be an
// indirect call and the we know can't be looking at a value of the
// label type (for the invoke instruction).
- unsigned ArgNo = CS.getArgumentNo(U.getOperandNo());
+ unsigned ArgNo = CS.getArgumentNo(U);
if (ArgNo >= F->getFunctionType()->getNumParams())
// The value is passed in through a vararg! Must be live.
return Live;
- assert(CS.getArgument(ArgNo)
- == CS.getInstruction()->getOperand(U.getOperandNo())
+ assert(CS.getArgument(ArgNo)
+ == CS->getOperand(U.getOperandNo())
&& "Argument is not where we expected it");
// Value passed to a normal call. It's only live when the corresponding
@@ -378,11 +378,11 @@ DAE::Liveness DAE::SurveyUse(Value::use_iterator U, UseVector &MaybeLiveUses,
/// Adds all uses that cause the result to be MaybeLive to MaybeLiveRetUses. If
/// the result is Live, MaybeLiveUses might be modified but its content should
/// be ignored (since it might not be complete).
-DAE::Liveness DAE::SurveyUses(Value *V, UseVector &MaybeLiveUses) {
+DAE::Liveness DAE::SurveyUses(const Value *V, UseVector &MaybeLiveUses) {
// Assume it's dead (which will only hold if there are no uses at all..).
Liveness Result = MaybeLive;
// Check each use.
- for (Value::use_iterator I = V->use_begin(),
+ for (Value::const_use_iterator I = V->use_begin(),
E = V->use_end(); I != E; ++I) {
Result = SurveyUse(I, MaybeLiveUses);
if (Result == Live)
@@ -399,7 +399,7 @@ DAE::Liveness DAE::SurveyUses(Value *V, UseVector &MaybeLiveUses) {
// We consider arguments of non-internal functions to be intrinsically alive as
// well as arguments to functions which have their "address taken".
//
-void DAE::SurveyFunction(Function &F) {
+void DAE::SurveyFunction(const Function &F) {
unsigned RetCount = NumRetVals(&F);
// Assume all return values are dead
typedef SmallVector<Liveness, 5> RetVals;
@@ -411,8 +411,8 @@ void DAE::SurveyFunction(Function &F) {
// MaybeLive. Initialized to a list of RetCount empty lists.
RetUses MaybeLiveRetUses(RetCount);
- for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
- if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator()))
+ for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
+ if (const ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator()))
if (RI->getNumOperands() != 0 && RI->getOperand(0)->getType()
!= F.getFunctionType()->getReturnType()) {
// We don't support old style multiple return values.
@@ -431,17 +431,18 @@ void DAE::SurveyFunction(Function &F) {
unsigned NumLiveRetVals = 0;
const Type *STy = dyn_cast<StructType>(F.getReturnType());
// Loop all uses of the function.
- for (Value::use_iterator I = F.use_begin(), E = F.use_end(); I != E; ++I) {
+ for (Value::const_use_iterator I = F.use_begin(), E = F.use_end();
+ I != E; ++I) {
// If the function is PASSED IN as an argument, its address has been
// taken.
- CallSite CS = CallSite::get(*I);
- if (!CS.getInstruction() || !CS.isCallee(I)) {
+ ImmutableCallSite CS(*I);
+ if (!CS || !CS.isCallee(I)) {
MarkLive(F);
return;
}
// If this use is anything other than a call site, the function is alive.
- Instruction *TheCall = CS.getInstruction();
+ const Instruction *TheCall = CS.getInstruction();
if (!TheCall) { // Not a direct call site?
MarkLive(F);
return;
@@ -454,9 +455,9 @@ void DAE::SurveyFunction(Function &F) {
if (NumLiveRetVals != RetCount) {
if (STy) {
// Check all uses of the return value.
- for (Value::use_iterator I = TheCall->use_begin(),
+ for (Value::const_use_iterator I = TheCall->use_begin(),
E = TheCall->use_end(); I != E; ++I) {
- ExtractValueInst *Ext = dyn_cast<ExtractValueInst>(*I);
+ const ExtractValueInst *Ext = dyn_cast<ExtractValueInst>(*I);
if (Ext && Ext->hasIndices()) {
// This use uses a part of our return value, survey the uses of
// that part and store the results for this index only.
@@ -493,7 +494,7 @@ void DAE::SurveyFunction(Function &F) {
// Now, check all of our arguments.
unsigned i = 0;
UseVector MaybeLiveArgUses;
- for (Function::arg_iterator AI = F.arg_begin(),
+ for (Function::const_arg_iterator AI = F.arg_begin(),
E = F.arg_end(); AI != E; ++AI, ++i) {
// See what the effect of this use is (recording any uses that cause
// MaybeLive in MaybeLiveArgUses).
@@ -599,12 +600,12 @@ bool DAE::RemoveDeadStuffFromFunction(Function *F) {
const Type *RetTy = FTy->getReturnType();
const Type *NRetTy = NULL;
unsigned RetCount = NumRetVals(F);
-
+
// -1 means unused, other numbers are the new index
SmallVector<int, 5> NewRetIdxs(RetCount, -1);
std::vector<const Type*> RetTypes;
- if (RetTy == Type::getVoidTy(F->getContext())) {
- NRetTy = Type::getVoidTy(F->getContext());
+ if (RetTy->isVoidTy()) {
+ NRetTy = RetTy;
} else {
const StructType *STy = dyn_cast<StructType>(RetTy);
if (STy)
@@ -653,10 +654,10 @@ bool DAE::RemoveDeadStuffFromFunction(Function *F) {
// values. Otherwise, ensure that we don't have any conflicting attributes
// here. Currently, this should not be possible, but special handling might be
// required when new return value attributes are added.
- if (NRetTy == Type::getVoidTy(F->getContext()))
+ if (NRetTy->isVoidTy())
RAttrs &= ~Attribute::typeIncompatible(NRetTy);
else
- assert((RAttrs & Attribute::typeIncompatible(NRetTy)) == 0
+ assert((RAttrs & Attribute::typeIncompatible(NRetTy)) == 0
&& "Return attributes no longer compatible?");
if (RAttrs)
@@ -686,11 +687,12 @@ bool DAE::RemoveDeadStuffFromFunction(Function *F) {
}
}
- if (FnAttrs != Attribute::None)
+ if (FnAttrs != Attribute::None)
AttributesVec.push_back(AttributeWithIndex::get(~0, FnAttrs));
// Reconstruct the AttributesList based on the vector we constructed.
- AttrListPtr NewPAL = AttrListPtr::get(AttributesVec.begin(), AttributesVec.end());
+ AttrListPtr NewPAL = AttrListPtr::get(AttributesVec.begin(),
+ AttributesVec.end());
// Work around LLVM bug PR56: the CWriter cannot emit varargs functions which
// have zero fixed arguments.
@@ -705,8 +707,7 @@ bool DAE::RemoveDeadStuffFromFunction(Function *F) {
}
// Create the new function type based on the recomputed parameters.
- FunctionType *NFTy = FunctionType::get(NRetTy, Params,
- FTy->isVarArg());
+ FunctionType *NFTy = FunctionType::get(NRetTy, Params, FTy->isVarArg());
// No change?
if (NFTy == FTy)
@@ -791,7 +792,7 @@ bool DAE::RemoveDeadStuffFromFunction(Function *F) {
// Return type not changed? Just replace users then.
Call->replaceAllUsesWith(New);
New->takeName(Call);
- } else if (New->getType() == Type::getVoidTy(F->getContext())) {
+ } else if (New->getType()->isVoidTy()) {
// Our return value has uses, but they will get removed later on.
// Replace by null for now.
Call->replaceAllUsesWith(Constant::getNullValue(Call->getType()));
@@ -805,7 +806,7 @@ bool DAE::RemoveDeadStuffFromFunction(Function *F) {
while (isa<PHINode>(IP)) ++IP;
InsertPt = IP;
}
-
+
// We used to return a struct. Instead of doing smart stuff with all the
// uses of this struct, we will just rebuild it using
// extract/insertvalue chaining and let instcombine clean that up.
@@ -929,11 +930,11 @@ bool DAE::runOnModule(Module &M) {
DEBUG(dbgs() << "DAE - Determining liveness\n");
for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
SurveyFunction(*I);
-
+
// Now, remove all dead arguments and return values from each function in
- // turn
+ // turn.
for (Module::iterator I = M.begin(), E = M.end(); I != E; ) {
- // Increment now, because the function will probably get removed (ie
+ // Increment now, because the function will probably get removed (ie.
// replaced by a new one).
Function *F = I++;
Changed |= RemoveDeadStuffFromFunction(F);
diff --git a/lib/Transforms/IPO/GlobalOpt.cpp b/lib/Transforms/IPO/GlobalOpt.cpp
index d8e97a26ada83..ddff5ef8b36c8 100644
--- a/lib/Transforms/IPO/GlobalOpt.cpp
+++ b/lib/Transforms/IPO/GlobalOpt.cpp
@@ -119,7 +119,7 @@ struct GlobalStatus {
/// null/false. When the first accessing function is noticed, it is recorded.
/// When a second different accessing function is noticed,
/// HasMultipleAccessingFunctions is set to true.
- Function *AccessingFunction;
+ const Function *AccessingFunction;
bool HasMultipleAccessingFunctions;
/// HasNonInstructionUser - Set to true if this global has a user that is not
@@ -140,11 +140,11 @@ struct GlobalStatus {
// by constants itself. Note that constants cannot be cyclic, so this test is
// pretty easy to implement recursively.
//
-static bool SafeToDestroyConstant(Constant *C) {
+static bool SafeToDestroyConstant(const Constant *C) {
if (isa<GlobalValue>(C)) return false;
- for (Value::use_iterator UI = C->use_begin(), E = C->use_end(); UI != E; ++UI)
- if (Constant *CU = dyn_cast<Constant>(*UI)) {
+ for (Value::const_use_iterator UI = C->use_begin(), E = C->use_end(); UI != E; ++UI)
+ if (const Constant *CU = dyn_cast<Constant>(*UI)) {
if (!SafeToDestroyConstant(CU)) return false;
} else
return false;
@@ -156,26 +156,26 @@ static bool SafeToDestroyConstant(Constant *C) {
/// structure. If the global has its address taken, return true to indicate we
/// can't do anything with it.
///
-static bool AnalyzeGlobal(Value *V, GlobalStatus &GS,
- SmallPtrSet<PHINode*, 16> &PHIUsers) {
- for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ++UI)
- if (ConstantExpr *CE = dyn_cast<ConstantExpr>(*UI)) {
+static bool AnalyzeGlobal(const Value *V, GlobalStatus &GS,
+ SmallPtrSet<const PHINode*, 16> &PHIUsers) {
+ for (Value::const_use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ++UI)
+ if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(*UI)) {
GS.HasNonInstructionUser = true;
if (AnalyzeGlobal(CE, GS, PHIUsers)) return true;
- } else if (Instruction *I = dyn_cast<Instruction>(*UI)) {
+ } else if (const Instruction *I = dyn_cast<Instruction>(*UI)) {
if (!GS.HasMultipleAccessingFunctions) {
- Function *F = I->getParent()->getParent();
+ const Function *F = I->getParent()->getParent();
if (GS.AccessingFunction == 0)
GS.AccessingFunction = F;
else if (GS.AccessingFunction != F)
GS.HasMultipleAccessingFunctions = true;
}
- if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
+ if (const LoadInst *LI = dyn_cast<LoadInst>(I)) {
GS.isLoaded = true;
if (LI->isVolatile()) return true; // Don't hack on volatile loads.
- } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
+ } else if (const StoreInst *SI = dyn_cast<StoreInst>(I)) {
// Don't allow a store OF the address, only stores TO the address.
if (SI->getOperand(0) == V) return true;
@@ -185,14 +185,13 @@ static bool AnalyzeGlobal(Value *V, GlobalStatus &GS,
// value, not an aggregate), keep more specific information about
// stores.
if (GS.StoredType != GlobalStatus::isStored) {
- if (GlobalVariable *GV = dyn_cast<GlobalVariable>(SI->getOperand(1))){
+ if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(SI->getOperand(1))){
Value *StoredVal = SI->getOperand(0);
if (StoredVal == GV->getInitializer()) {
if (GS.StoredType < GlobalStatus::isInitializerStored)
GS.StoredType = GlobalStatus::isInitializerStored;
} else if (isa<LoadInst>(StoredVal) &&
cast<LoadInst>(StoredVal)->getOperand(0) == GV) {
- // G = G
if (GS.StoredType < GlobalStatus::isInitializerStored)
GS.StoredType = GlobalStatus::isInitializerStored;
} else if (GS.StoredType < GlobalStatus::isStoredOnce) {
@@ -212,7 +211,7 @@ static bool AnalyzeGlobal(Value *V, GlobalStatus &GS,
if (AnalyzeGlobal(I, GS, PHIUsers)) return true;
} else if (isa<SelectInst>(I)) {
if (AnalyzeGlobal(I, GS, PHIUsers)) return true;
- } else if (PHINode *PN = dyn_cast<PHINode>(I)) {
+ } else if (const PHINode *PN = dyn_cast<PHINode>(I)) {
// PHI nodes we can check just like select or GEP instructions, but we
// have to be careful about infinite recursion.
if (PHIUsers.insert(PN)) // Not already visited.
@@ -230,7 +229,7 @@ static bool AnalyzeGlobal(Value *V, GlobalStatus &GS,
} else {
return true; // Any other non-load instruction might take address!
}
- } else if (Constant *C = dyn_cast<Constant>(*UI)) {
+ } else if (const Constant *C = dyn_cast<Constant>(*UI)) {
GS.HasNonInstructionUser = true;
// We might have a dead and dangling constant hanging off of here.
if (!SafeToDestroyConstant(C))
@@ -1029,23 +1028,23 @@ static void ReplaceUsesOfMallocWithGlobal(Instruction *Alloc,
/// LoadUsesSimpleEnoughForHeapSRA - Verify that all uses of V (a load, or a phi
/// of a load) are simple enough to perform heap SRA on. This permits GEP's
/// that index through the array and struct field, icmps of null, and PHIs.
-static bool LoadUsesSimpleEnoughForHeapSRA(Value *V,
- SmallPtrSet<PHINode*, 32> &LoadUsingPHIs,
- SmallPtrSet<PHINode*, 32> &LoadUsingPHIsPerLoad) {
+static bool LoadUsesSimpleEnoughForHeapSRA(const Value *V,
+ SmallPtrSet<const PHINode*, 32> &LoadUsingPHIs,
+ SmallPtrSet<const PHINode*, 32> &LoadUsingPHIsPerLoad) {
// We permit two users of the load: setcc comparing against the null
// pointer, and a getelementptr of a specific form.
- for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E;++UI){
- Instruction *User = cast<Instruction>(*UI);
+ for (Value::const_use_iterator UI = V->use_begin(), E = V->use_end(); UI != E;++UI){
+ const Instruction *User = cast<Instruction>(*UI);
// Comparison against null is ok.
- if (ICmpInst *ICI = dyn_cast<ICmpInst>(User)) {
+ if (const ICmpInst *ICI = dyn_cast<ICmpInst>(User)) {
if (!isa<ConstantPointerNull>(ICI->getOperand(1)))
return false;
continue;
}
// getelementptr is also ok, but only a simple form.
- if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User)) {
+ if (const GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User)) {
// Must index into the array and into the struct.
if (GEPI->getNumOperands() < 3)
return false;
@@ -1054,7 +1053,7 @@ static bool LoadUsesSimpleEnoughForHeapSRA(Value *V,
continue;
}
- if (PHINode *PN = dyn_cast<PHINode>(User)) {
+ if (const PHINode *PN = dyn_cast<PHINode>(User)) {
if (!LoadUsingPHIsPerLoad.insert(PN))
// This means some phi nodes are dependent on each other.
// Avoid infinite looping!
@@ -1081,13 +1080,13 @@ static bool LoadUsesSimpleEnoughForHeapSRA(Value *V,
/// AllGlobalLoadUsesSimpleEnoughForHeapSRA - If all users of values loaded from
/// GV are simple enough to perform HeapSRA, return true.
-static bool AllGlobalLoadUsesSimpleEnoughForHeapSRA(GlobalVariable *GV,
+static bool AllGlobalLoadUsesSimpleEnoughForHeapSRA(const GlobalVariable *GV,
Instruction *StoredVal) {
- SmallPtrSet<PHINode*, 32> LoadUsingPHIs;
- SmallPtrSet<PHINode*, 32> LoadUsingPHIsPerLoad;
- for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end(); UI != E;
+ SmallPtrSet<const PHINode*, 32> LoadUsingPHIs;
+ SmallPtrSet<const PHINode*, 32> LoadUsingPHIsPerLoad;
+ for (Value::const_use_iterator UI = GV->use_begin(), E = GV->use_end(); UI != E;
++UI)
- if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) {
+ if (const LoadInst *LI = dyn_cast<LoadInst>(*UI)) {
if (!LoadUsesSimpleEnoughForHeapSRA(LI, LoadUsingPHIs,
LoadUsingPHIsPerLoad))
return false;
@@ -1099,16 +1098,16 @@ static bool AllGlobalLoadUsesSimpleEnoughForHeapSRA(GlobalVariable *GV,
// that all inputs the to the PHI nodes are in the same equivalence sets.
// Check to verify that all operands of the PHIs are either PHIS that can be
// transformed, loads from GV, or MI itself.
- for (SmallPtrSet<PHINode*, 32>::iterator I = LoadUsingPHIs.begin(),
+ for (SmallPtrSet<const PHINode*, 32>::const_iterator I = LoadUsingPHIs.begin(),
E = LoadUsingPHIs.end(); I != E; ++I) {
- PHINode *PN = *I;
+ const PHINode *PN = *I;
for (unsigned op = 0, e = PN->getNumIncomingValues(); op != e; ++op) {
Value *InVal = PN->getIncomingValue(op);
// PHI of the stored value itself is ok.
if (InVal == StoredVal) continue;
- if (PHINode *InPN = dyn_cast<PHINode>(InVal)) {
+ if (const PHINode *InPN = dyn_cast<PHINode>(InVal)) {
// One of the PHIs in our set is (optimistically) ok.
if (LoadUsingPHIs.count(InPN))
continue;
@@ -1116,7 +1115,7 @@ static bool AllGlobalLoadUsesSimpleEnoughForHeapSRA(GlobalVariable *GV,
}
// Load from GV is ok.
- if (LoadInst *LI = dyn_cast<LoadInst>(InVal))
+ if (const LoadInst *LI = dyn_cast<LoadInst>(InVal))
if (LI->getOperand(0) == GV)
continue;
@@ -1664,7 +1663,7 @@ static bool TryToShrinkGlobalToBoolean(GlobalVariable *GV, Constant *OtherVal) {
/// it if possible. If we make a change, return true.
bool GlobalOpt::ProcessInternalGlobal(GlobalVariable *GV,
Module::global_iterator &GVI) {
- SmallPtrSet<PHINode*, 16> PHIUsers;
+ SmallPtrSet<const PHINode*, 16> PHIUsers;
GlobalStatus GS;
GV->removeDeadConstantUsers();
@@ -1715,12 +1714,13 @@ bool GlobalOpt::ProcessInternalGlobal(GlobalVariable *GV,
GS.AccessingFunction->hasExternalLinkage() &&
GV->getType()->getAddressSpace() == 0) {
DEBUG(dbgs() << "LOCALIZING GLOBAL: " << *GV);
- Instruction* FirstI = GS.AccessingFunction->getEntryBlock().begin();
+ Instruction& FirstI = const_cast<Instruction&>(*GS.AccessingFunction
+ ->getEntryBlock().begin());
const Type* ElemTy = GV->getType()->getElementType();
// FIXME: Pass Global's alignment when globals have alignment
- AllocaInst* Alloca = new AllocaInst(ElemTy, NULL, GV->getName(), FirstI);
+ AllocaInst* Alloca = new AllocaInst(ElemTy, NULL, GV->getName(), &FirstI);
if (!isa<UndefValue>(GV->getInitializer()))
- new StoreInst(GV->getInitializer(), Alloca, FirstI);
+ new StoreInst(GV->getInitializer(), Alloca, &FirstI);
GV->replaceAllUsesWith(Alloca);
GV->eraseFromParent();
diff --git a/lib/Transforms/IPO/PruneEH.cpp b/lib/Transforms/IPO/PruneEH.cpp
index 3ae771c55f021..161246bc2598a 100644
--- a/lib/Transforms/IPO/PruneEH.cpp
+++ b/lib/Transforms/IPO/PruneEH.cpp
@@ -168,7 +168,7 @@ bool PruneEH::SimplifyFunction(Function *F) {
for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator()))
if (II->doesNotThrow()) {
- SmallVector<Value*, 8> Args(II->op_begin()+3, II->op_end());
+ SmallVector<Value*, 8> Args(II->op_begin(), II->op_end() - 3);
// Insert a call instruction before the invoke.
CallInst *Call = CallInst::Create(II->getCalledValue(),
Args.begin(), Args.end(), "", II);
diff --git a/lib/Transforms/InstCombine/InstCombineCalls.cpp b/lib/Transforms/InstCombine/InstCombineCalls.cpp
index 65f2e15d2780b..76c815da86288 100644
--- a/lib/Transforms/InstCombine/InstCombineCalls.cpp
+++ b/lib/Transforms/InstCombine/InstCombineCalls.cpp
@@ -766,7 +766,7 @@ protected:
return SizeCI->getZExtValue() >=
GetStringLength(CI->getOperand(SizeArgOp));
if (ConstantInt *Arg = dyn_cast<ConstantInt>(CI->getOperand(SizeArgOp)))
- return SizeCI->getZExtValue() <= Arg->getZExtValue();
+ return SizeCI->getZExtValue() >= Arg->getZExtValue();
}
return false;
}
diff --git a/lib/Transforms/Scalar/ABCD.cpp b/lib/Transforms/Scalar/ABCD.cpp
index ea8e5c3e53f2d..6135992a2f88c 100644
--- a/lib/Transforms/Scalar/ABCD.cpp
+++ b/lib/Transforms/Scalar/ABCD.cpp
@@ -27,6 +27,7 @@
#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"
@@ -77,10 +78,10 @@ class ABCD : public FunctionPass {
class Bound {
public:
Bound(APInt v, bool upper) : value(v), upper_bound(upper) {}
- Bound(const Bound *b, int cnst)
- : value(b->value - cnst), upper_bound(b->upper_bound) {}
- Bound(const Bound *b, const APInt &cnst)
- : value(b->value - cnst), upper_bound(b->upper_bound) {}
+ Bound(const Bound &b, int cnst)
+ : value(b.value - cnst), upper_bound(b.upper_bound) {}
+ 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; }
@@ -89,15 +90,15 @@ class ABCD : public FunctionPass {
int32_t getBitWidth() const { return value.getBitWidth(); }
/// Creates a Bound incrementing the one received
- static Bound *createIncrement(const Bound *b) {
- return new Bound(b->isUpperBound() ? b->value+1 : b->value-1,
- b->upper_bound);
+ 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 new Bound(b->isUpperBound() ? b->value-1 : b->value+1,
- b->upper_bound);
+ 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
@@ -109,36 +110,31 @@ class ABCD : public FunctionPass {
}
/// Test if val is less than or equal to Bound b
- static bool leq(APInt val, const Bound *b) {
- if (!b) return false;
- return b->isUpperBound() ? val.sle(b->value) : val.sge(b->value);
+ 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) {
- if (!a || !b) return false;
-
- assert(a->isUpperBound() == b->isUpperBound());
- return a->isUpperBound() ? a->value.sle(b->value) :
- a->value.sge(b->value);
+ 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) {
- if (!a || !b) return false;
-
- assert(a->isUpperBound() == b->isUpperBound());
- return a->isUpperBound() ? a->value.slt(b->value) :
- a->value.sgt(b->value);
+ 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, APInt val) {
+ static bool geq(const Bound &b, APInt val) {
return leq(val, b);
}
/// Test if Bound a is greater then or equal Bound b
- static bool geq(const Bound *a, const Bound *b) {
+ static bool geq(const Bound &a, const Bound &b) {
return leq(b, a);
}
@@ -152,29 +148,36 @@ class ABCD : public FunctionPass {
/// minimum true and minimum reduced results are stored
class MemoizedResultChart {
public:
- MemoizedResultChart()
- : max_false(NULL), min_true(NULL), min_reduced(NULL) {}
+ 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
- Bound *getFalse() const { return max_false; }
+ const Bound *getFalse() const { return max_false.get(); }
/// Returns the min true
- Bound *getTrue() const { return min_true; }
+ const Bound *getTrue() const { return min_true.get(); }
/// Returns the min reduced
- Bound *getReduced() const { return min_reduced; }
+ const Bound *getReduced() const { return min_reduced.get(); }
/// Return the stored result for this bound
- ProveResult getResult(const Bound *bound) const;
+ ProveResult getResult(const Bound &bound) const;
/// Stores a false found
- void addFalse(Bound *bound);
+ void addFalse(const Bound &bound);
/// Stores a true found
- void addTrue(Bound *bound);
+ void addTrue(const Bound &bound);
/// Stores a Reduced found
- void addReduced(Bound *bound);
+ void addReduced(const Bound &bound);
/// Clears redundant reduced
/// If a min_true is smaller than a min_reduced then the min_reduced
@@ -183,13 +186,13 @@ class ABCD : public FunctionPass {
void clearRedundantReduced();
void clear() {
- delete max_false;
- delete min_true;
- delete min_reduced;
+ max_false.reset();
+ min_true.reset();
+ min_reduced.reset();
}
private:
- Bound *max_false, *min_true, *min_reduced;
+ OwningPtr<Bound> max_false, min_true, min_reduced;
};
/// This class stores the result found for a node of the graph,
@@ -198,27 +201,27 @@ class ABCD : public FunctionPass {
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 {
- Bound *trueBound = map.lookup(b).getTrue();
- return trueBound && Bound::leq(trueBound, 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 {
- Bound *falseBound = map.lookup(b).getFalse();
- return falseBound && Bound::leq(falseBound, 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 {
- Bound *reducedBound = map.lookup(b).getReduced();
- return reducedBound && Bound::leq(reducedBound, 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, Bound *bound) {
+ ProveResult getBoundResult(Value *b, const Bound &bound) {
return map[b].getResult(bound);
}
@@ -233,7 +236,7 @@ class ABCD : public FunctionPass {
}
/// Stores the bound found
- void updateBound(Value *b, Bound *bound, const ProveResult res);
+ void updateBound(Value *b, const Bound &bound, const ProveResult res);
private:
// Maps a nod in the graph with its results found.
@@ -274,7 +277,7 @@ class ABCD : public FunctionPass {
bool hasEdge(Value *V, bool upper) const;
/// Returns all edges pointed by vertex V
- SmallPtrSet<Edge *, 16> getEdges(Value *V) const {
+ SmallVector<Edge, 16> getEdges(Value *V) const {
return graph.lookup(V);
}
@@ -292,13 +295,7 @@ class ABCD : public FunctionPass {
}
private:
- DenseMap<Value *, SmallPtrSet<Edge *, 16> > graph;
-
- /// Adds a Node to the graph.
- DenseMap<Value *, SmallPtrSet<Edge *, 16> >::iterator addNode(Value *V) {
- SmallPtrSet<Edge *, 16> p;
- return graph.insert(std::make_pair(V, p)).first;
- }
+ DenseMap<Value *, SmallVector<Edge, 16> > graph;
/// Prints the header of the dot file
void printHeader(raw_ostream &OS, Function &F) const;
@@ -315,7 +312,7 @@ class ABCD : public FunctionPass {
void printVertex(raw_ostream &OS, Value *source) const;
/// Prints the edge to the dot file
- void printEdge(raw_ostream &OS, Value *source, Edge *edge) const;
+ void printEdge(raw_ostream &OS, Value *source, const Edge &edge) const;
void printName(raw_ostream &OS, Value *info) const;
};
@@ -428,15 +425,15 @@ class ABCD : public FunctionPass {
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, Bound *bound, unsigned level);
+ 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, Bound *bound, unsigned level,
+ void updateMemDistance(Value *a, Value *b, const Bound &bound, unsigned level,
meet_function meet);
InequalityGraph inequality_graph;
MemoizedResult mem_result;
- DenseMap<Value*, Bound*> active;
+ DenseMap<Value*, const Bound*> active;
SmallPtrSet<Value*, 16> created;
SmallVector<PHINode *, 16> phis_to_remove;
};
@@ -857,7 +854,7 @@ PHINode *ABCD::findSigma(BasicBlock *BB, Instruction *I) {
/// 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 = new Bound(APInt(width, c), upper_bound);
+ Bound bound(APInt(width, c), upper_bound);
mem_result.clear();
active.clear();
@@ -867,7 +864,7 @@ bool ABCD::demandProve(Value *a, Value *b, int c, bool upper_bound) {
}
/// Prove that distance between b and a is <= bound
-ABCD::ProveResult ABCD::prove(Value *a, Value *b, Bound *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
@@ -885,22 +882,22 @@ ABCD::ProveResult ABCD::prove(Value *a, Value *b, Bound *bound,
return Reduced;
// traversal reached the source vertex
- if (a == b && Bound::geq(bound, APInt(bound->getBitWidth(), 0, true)))
+ 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()))
+ if (!inequality_graph.hasEdge(b, bound.isUpperBound()))
return False;
// a cycle was encountered
if (active.count(b)) {
- if (Bound::leq(active.lookup(b), bound))
+ if (Bound::leq(*active.lookup(b), bound))
return Reduced; // a "harmless" cycle
return False; // an amplifying cycle
}
- active[b] = bound;
+ 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
@@ -917,23 +914,23 @@ ABCD::ProveResult ABCD::prove(Value *a, Value *b, Bound *bound,
}
/// Updates the distance value for a and b
-void ABCD::updateMemDistance(Value *a, Value *b, Bound *bound, unsigned level,
- meet_function meet) {
+void ABCD::updateMemDistance(Value *a, Value *b, const Bound &bound,
+ unsigned level, meet_function meet) {
ABCD::ProveResult res = (meet == max) ? False : True;
- SmallPtrSet<Edge *, 16> Edges = inequality_graph.getEdges(b);
- SmallPtrSet<Edge *, 16>::iterator begin = Edges.begin(), end = Edges.end();
+ 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;
}
- Edge *in = *begin;
- if (in->isUpperBound() == bound->isUpperBound()) {
- Value *succ = in->getVertex();
- res = meet(res, prove(a, succ, new Bound(bound, in->getValue()),
- level+1));
+ 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));
}
}
@@ -941,53 +938,53 @@ void ABCD::updateMemDistance(Value *a, Value *b, Bound *bound, unsigned level,
}
/// Return the stored result for this bound
-ABCD::ProveResult ABCD::MemoizedResultChart::getResult(const Bound *bound)const{
- if (max_false && Bound::leq(bound, max_false))
+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))
+ if (min_true && Bound::leq(*min_true, bound))
return True;
- if (min_reduced && Bound::leq(min_reduced, bound))
+ if (min_reduced && Bound::leq(*min_reduced, bound))
return Reduced;
return False;
}
/// Stores a false found
-void ABCD::MemoizedResultChart::addFalse(Bound *bound) {
- if (!max_false || Bound::leq(max_false, bound))
- max_false = bound;
-
- if (Bound::eq(max_false, min_reduced))
- min_reduced = Bound::createIncrement(min_reduced);
- if (Bound::eq(max_false, min_true))
- min_true = Bound::createIncrement(min_true);
- if (Bound::eq(min_reduced, min_true))
- min_reduced = NULL;
+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(Bound *bound) {
- if (!min_true || Bound::leq(bound, min_true))
- min_true = bound;
-
- if (Bound::eq(min_true, min_reduced))
- min_reduced = Bound::createDecrement(min_reduced);
- if (Bound::eq(min_true, max_false))
- max_false = Bound::createDecrement(max_false);
- if (Bound::eq(max_false, min_reduced))
- min_reduced = NULL;
+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(Bound *bound) {
- if (!min_reduced || Bound::leq(bound, min_reduced))
- min_reduced = bound;
-
- if (Bound::eq(min_reduced, min_true))
- min_true = Bound::createIncrement(min_true);
- if (Bound::eq(min_reduced, max_false))
- max_false = Bound::createDecrement(max_false);
+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
@@ -995,14 +992,14 @@ void ABCD::MemoizedResultChart::addReduced(Bound *bound) {
/// 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 = NULL;
- if (max_false && min_reduced && Bound::lt(min_reduced, max_false))
- min_reduced = NULL;
+ 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, Bound *bound,
+void ABCD::MemoizedResult::updateBound(Value *b, const Bound &bound,
const ProveResult res) {
if (res == False) {
map[b].addFalse(bound);
@@ -1020,19 +1017,17 @@ void ABCD::InequalityGraph::addEdge(Value *V_to, Value *V_from,
assert(cast<IntegerType>(V_from->getType())->getBitWidth() ==
value.getBitWidth());
- DenseMap<Value *, SmallPtrSet<Edge *, 16> >::iterator from;
- from = addNode(V_from);
- from->second.insert(new Edge(V_to, value, upper));
+ 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 {
- SmallPtrSet<Edge *, 16> it = graph.lookup(V);
+ SmallVector<Edge, 16> it = graph.lookup(V);
- SmallPtrSet<Edge *, 16>::iterator begin = it.begin();
- SmallPtrSet<Edge *, 16>::iterator end = it.end();
+ SmallVector<Edge, 16>::iterator begin = it.begin();
+ SmallVector<Edge, 16>::iterator end = it.end();
for (; begin != end; ++begin) {
- if ((*begin)->isUpperBound() == upper) {
+ if (begin->isUpperBound() == upper) {
return true;
}
}
@@ -1049,18 +1044,18 @@ void ABCD::InequalityGraph::printHeader(raw_ostream &OS, Function &F) const {
/// Prints the body of the dot file
void ABCD::InequalityGraph::printBody(raw_ostream &OS) const {
- DenseMap<Value *, SmallPtrSet<Edge *, 16> >::const_iterator begin =
+ DenseMap<Value *, SmallVector<Edge, 16> >::const_iterator begin =
graph.begin(), end = graph.end();
for (; begin != end ; ++begin) {
- SmallPtrSet<Edge *, 16>::iterator begin_par =
+ 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) {
- Edge *edge = *begin_par;
+ const Edge &edge = *begin_par;
printEdge(OS, source, edge);
}
}
@@ -1079,10 +1074,10 @@ void ABCD::InequalityGraph::printVertex(raw_ostream &OS, Value *source) const {
/// Prints the edge to the dot file
void ABCD::InequalityGraph::printEdge(raw_ostream &OS, Value *source,
- Edge *edge) const {
- Value *dest = edge->getVertex();
- APInt value = edge->getValue();
- bool upper = edge->isUpperBound();
+ const Edge &edge) const {
+ Value *dest = edge.getVertex();
+ APInt value = edge.getValue();
+ bool upper = edge.isUpperBound();
OS << "\"";
printName(OS, source);
diff --git a/lib/Transforms/Scalar/CodeGenPrepare.cpp b/lib/Transforms/Scalar/CodeGenPrepare.cpp
index 50c96304db095..93e9bfbe35ac7 100644
--- a/lib/Transforms/Scalar/CodeGenPrepare.cpp
+++ b/lib/Transforms/Scalar/CodeGenPrepare.cpp
@@ -174,7 +174,7 @@ bool CodeGenPrepare::CanMergeBlocks(const BasicBlock *BB,
// don't mess around with them.
BasicBlock::const_iterator BBI = BB->begin();
while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) {
- for (Value::use_const_iterator UI = PN->use_begin(), E = PN->use_end();
+ for (Value::const_use_iterator UI = PN->use_begin(), E = PN->use_end();
UI != E; ++UI) {
const Instruction *User = cast<Instruction>(*UI);
if (User->getParent() != DestBB || !isa<PHINode>(User))
@@ -714,8 +714,12 @@ bool CodeGenPrepare::OptimizeMemoryInst(Instruction *MemoryInst, Value *Addr,
MemoryInst->replaceUsesOfWith(Addr, SunkAddr);
- if (Addr->use_empty())
+ if (Addr->use_empty()) {
RecursivelyDeleteTriviallyDeadInstructions(Addr);
+ // This address is now available for reassignment, so erase the table entry;
+ // we don't want to match some completely different instruction.
+ SunkAddrs[Addr] = 0;
+ }
return true;
}
diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp
index fcb802a72ae08..642d59da044f7 100644
--- a/lib/Transforms/Scalar/GVN.cpp
+++ b/lib/Transforms/Scalar/GVN.cpp
@@ -1004,18 +1004,18 @@ static int AnalyzeLoadFromClobberingWrite(const Type *LoadTy, Value *LoadPtr,
// If the load and store are to the exact same address, they should have been
// a must alias. AA must have gotten confused.
- // FIXME: Study to see if/when this happens.
- if (LoadOffset == StoreOffset) {
+ // FIXME: Study to see if/when this happens. One case is forwarding a memset
+ // to a load from the base of the memset.
#if 0
+ if (LoadOffset == StoreOffset) {
dbgs() << "STORE/LOAD DEP WITH COMMON POINTER MISSED:\n"
<< "Base = " << *StoreBase << "\n"
<< "Store Ptr = " << *WritePtr << "\n"
<< "Store Offs = " << StoreOffset << "\n"
<< "Load Ptr = " << *LoadPtr << "\n";
abort();
-#endif
- return -1;
}
+#endif
// If the load and store don't overlap at all, the store doesn't provide
// anything to the load. In this case, they really don't alias at all, AA
@@ -1031,11 +1031,11 @@ static int AnalyzeLoadFromClobberingWrite(const Type *LoadTy, Value *LoadPtr,
bool isAAFailure = false;
- if (StoreOffset < LoadOffset) {
+ if (StoreOffset < LoadOffset)
isAAFailure = StoreOffset+int64_t(StoreSize) <= LoadOffset;
- } else {
+ else
isAAFailure = LoadOffset+int64_t(LoadSize) <= StoreOffset;
- }
+
if (isAAFailure) {
#if 0
dbgs() << "STORE LOAD DEP WITH COMMON BASE:\n"
diff --git a/lib/Transforms/Scalar/IndVarSimplify.cpp b/lib/Transforms/Scalar/IndVarSimplify.cpp
index eb04d9401fbb6..988a4cb3f2a2d 100644
--- a/lib/Transforms/Scalar/IndVarSimplify.cpp
+++ b/lib/Transforms/Scalar/IndVarSimplify.cpp
@@ -553,22 +553,26 @@ void IndVarSimplify::SinkUnusedInvariants(Loop *L) {
// New instructions were inserted at the end of the preheader.
if (isa<PHINode>(I))
break;
+
// Don't move instructions which might have side effects, since the side
- // effects need to complete before instructions inside the loop. Also
- // don't move instructions which might read memory, since the loop may
- // modify memory. Note that it's okay if the instruction might have
- // undefined behavior: LoopSimplify guarantees that the preheader
- // dominates the exit block.
+ // effects need to complete before instructions inside the loop. Also don't
+ // move instructions which might read memory, since the loop may modify
+ // memory. Note that it's okay if the instruction might have undefined
+ // behavior: LoopSimplify guarantees that the preheader dominates the exit
+ // block.
if (I->mayHaveSideEffects() || I->mayReadFromMemory())
continue;
+
// Skip debug info intrinsics.
if (isa<DbgInfoIntrinsic>(I))
continue;
+
// Don't sink static AllocaInsts out of the entry block, which would
// turn them into dynamic allocas!
if (AllocaInst *AI = dyn_cast<AllocaInst>(I))
if (AI->isStaticAlloca())
continue;
+
// Determine if there is a use in or before the loop (direct or
// otherwise).
bool UsedInLoop = false;
@@ -585,19 +589,29 @@ void IndVarSimplify::SinkUnusedInvariants(Loop *L) {
break;
}
}
+
// If there is, the def must remain in the preheader.
if (UsedInLoop)
continue;
+
// Otherwise, sink it to the exit block.
Instruction *ToMove = I;
bool Done = false;
- if (I != Preheader->begin())
- --I;
- else
+
+ if (I != Preheader->begin()) {
+ // Skip debug info intrinsics.
+ do {
+ --I;
+ } while (isa<DbgInfoIntrinsic>(I) && I != Preheader->begin());
+
+ if (isa<DbgInfoIntrinsic>(I) && I == Preheader->begin())
+ Done = true;
+ } else {
Done = true;
+ }
+
ToMove->moveBefore(InsertPt);
- if (Done)
- break;
+ if (Done) break;
InsertPt = ToMove;
}
}
diff --git a/lib/Transforms/Scalar/LoopStrengthReduce.cpp b/lib/Transforms/Scalar/LoopStrengthReduce.cpp
index f920dcab25dfa..625a75d6cca98 100644
--- a/lib/Transforms/Scalar/LoopStrengthReduce.cpp
+++ b/lib/Transforms/Scalar/LoopStrengthReduce.cpp
@@ -1899,7 +1899,7 @@ LSRInstance::CollectLoopInvariantFixupsAndFormulae() {
const Value *V = U->getValue();
if (const Instruction *Inst = dyn_cast<Instruction>(V))
if (L->contains(Inst)) continue;
- for (Value::use_const_iterator UI = V->use_begin(), UE = V->use_end();
+ for (Value::const_use_iterator UI = V->use_begin(), UE = V->use_end();
UI != UE; ++UI) {
const Instruction *UserInst = dyn_cast<Instruction>(*UI);
// Ignore non-instructions.
@@ -2827,6 +2827,7 @@ Value *LSRInstance::Expand(const LSRFixup &LF,
IP = Tentative;
}
while (isa<PHINode>(IP)) ++IP;
+ while (isa<DbgInfoIntrinsic>(IP)) ++IP;
// Inform the Rewriter if we have a post-increment use, so that it can
// perform an advantageous expansion.
@@ -2864,8 +2865,10 @@ Value *LSRInstance::Expand(const LSRFixup &LF,
// so that it is dominated by its operand. If the original insert point
// was already dominated by the increment, keep it, because there may
// be loop-variant operands that need to be respected also.
- if (L->contains(LF.UserInst) && !DT.dominates(IVIncInsertPos, IP))
+ if (L->contains(LF.UserInst) && !DT.dominates(IVIncInsertPos, IP)) {
IP = IVIncInsertPos;
+ while (isa<DbgInfoIntrinsic>(IP)) ++IP;
+ }
break;
}
Start = AR->getStart();
diff --git a/lib/Transforms/Scalar/Reg2Mem.cpp b/lib/Transforms/Scalar/Reg2Mem.cpp
index 99e12522ce0c7..7a6eec3d46b45 100644
--- a/lib/Transforms/Scalar/Reg2Mem.cpp
+++ b/lib/Transforms/Scalar/Reg2Mem.cpp
@@ -45,7 +45,7 @@ namespace {
bool valueEscapes(const Instruction *Inst) const {
const BasicBlock *BB = Inst->getParent();
- for (Value::use_const_iterator UI = Inst->use_begin(),E = Inst->use_end();
+ for (Value::const_use_iterator UI = Inst->use_begin(),E = Inst->use_end();
UI != E; ++UI)
if (cast<Instruction>(*UI)->getParent() != BB ||
isa<PHINode>(*UI))
diff --git a/lib/Transforms/Scalar/SCCP.cpp b/lib/Transforms/Scalar/SCCP.cpp
index 7e37938868d68..546b7b6cc2920 100644
--- a/lib/Transforms/Scalar/SCCP.cpp
+++ b/lib/Transforms/Scalar/SCCP.cpp
@@ -1705,28 +1705,31 @@ ModulePass *llvm::createIPSCCPPass() {
}
-static bool AddressIsTaken(GlobalValue *GV) {
+static bool AddressIsTaken(const GlobalValue *GV) {
// Delete any dead constantexpr klingons.
GV->removeDeadConstantUsers();
- for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end();
- UI != E; ++UI)
- if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) {
+ for (Value::const_use_iterator UI = GV->use_begin(), E = GV->use_end();
+ UI != E; ++UI) {
+ const User *U = *UI;
+ if (const StoreInst *SI = dyn_cast<StoreInst>(U)) {
if (SI->getOperand(0) == GV || SI->isVolatile())
return true; // Storing addr of GV.
- } else if (isa<InvokeInst>(*UI) || isa<CallInst>(*UI)) {
+ } else if (isa<InvokeInst>(U) || isa<CallInst>(U)) {
// Make sure we are calling the function, not passing the address.
- if (UI.getOperandNo() != 0)
+ ImmutableCallSite CS(cast<Instruction>(U));
+ if (!CS.isCallee(UI))
return true;
- } else if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) {
+ } else if (const LoadInst *LI = dyn_cast<LoadInst>(U)) {
if (LI->isVolatile())
return true;
- } else if (isa<BlockAddress>(*UI)) {
+ } else if (isa<BlockAddress>(U)) {
// blockaddress doesn't take the address of the function, it takes addr
// of label.
} else {
return true;
}
+ }
return false;
}
diff --git a/lib/Transforms/Scalar/SimplifyCFGPass.cpp b/lib/Transforms/Scalar/SimplifyCFGPass.cpp
index 738c5e8d13d1d..b621e8d8aa6f6 100644
--- a/lib/Transforms/Scalar/SimplifyCFGPass.cpp
+++ b/lib/Transforms/Scalar/SimplifyCFGPass.cpp
@@ -79,7 +79,7 @@ static void ChangeToUnreachable(Instruction *I) {
/// ChangeToCall - Convert the specified invoke into a normal call.
static void ChangeToCall(InvokeInst *II) {
BasicBlock *BB = II->getParent();
- SmallVector<Value*, 8> Args(II->op_begin()+3, II->op_end());
+ SmallVector<Value*, 8> Args(II->op_begin(), II->op_end() - 3);
CallInst *NewCall = CallInst::Create(II->getCalledValue(), Args.begin(),
Args.end(), "", II);
NewCall->takeName(II);
diff --git a/lib/Transforms/Scalar/SimplifyLibCalls.cpp b/lib/Transforms/Scalar/SimplifyLibCalls.cpp
index 22f3628cf7c06..5941ea6571b76 100644
--- a/lib/Transforms/Scalar/SimplifyLibCalls.cpp
+++ b/lib/Transforms/Scalar/SimplifyLibCalls.cpp
@@ -350,10 +350,16 @@ struct StrNCmpOpt : public LibCallOptimization {
// 'strcpy' Optimizations
struct StrCpyOpt : public LibCallOptimization {
+ bool OptChkCall; // True if it's optimizing a __strcpy_chk libcall.
+
+ StrCpyOpt(bool c) : OptChkCall(c) {}
+
virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
// Verify the "strcpy" function prototype.
+ unsigned NumParams = OptChkCall ? 3 : 2;
const FunctionType *FT = Callee->getFunctionType();
- if (FT->getNumParams() != 2 || FT->getReturnType() != FT->getParamType(0) ||
+ if (FT->getNumParams() != NumParams ||
+ FT->getReturnType() != FT->getParamType(0) ||
FT->getParamType(0) != FT->getParamType(1) ||
FT->getParamType(0) != Type::getInt8PtrTy(*Context))
return 0;
@@ -371,8 +377,13 @@ struct StrCpyOpt : public LibCallOptimization {
// We have enough information to now generate the memcpy call to do the
// concatenation for us. Make a memcpy to copy the nul byte with align = 1.
- EmitMemCpy(Dst, Src,
- ConstantInt::get(TD->getIntPtrType(*Context), Len), 1, B, TD);
+ if (OptChkCall)
+ EmitMemCpyChk(Dst, Src,
+ ConstantInt::get(TD->getIntPtrType(*Context), Len),
+ CI->getOperand(3), B, TD);
+ else
+ EmitMemCpy(Dst, Src,
+ ConstantInt::get(TD->getIntPtrType(*Context), Len), 1, B, TD);
return Dst;
}
};
@@ -1162,7 +1173,8 @@ namespace {
StringMap<LibCallOptimization*> Optimizations;
// String and Memory LibCall Optimizations
StrCatOpt StrCat; StrNCatOpt StrNCat; StrChrOpt StrChr; StrCmpOpt StrCmp;
- StrNCmpOpt StrNCmp; StrCpyOpt StrCpy; StrNCpyOpt StrNCpy; StrLenOpt StrLen;
+ StrNCmpOpt StrNCmp; StrCpyOpt StrCpy; StrCpyOpt StrCpyChk;
+ StrNCpyOpt StrNCpy; StrLenOpt StrLen;
StrToOpt StrTo; StrStrOpt StrStr;
MemCmpOpt MemCmp; MemCpyOpt MemCpy; MemMoveOpt MemMove; MemSetOpt MemSet;
// Math Library Optimizations
@@ -1177,8 +1189,7 @@ namespace {
bool Modified; // This is only used by doInitialization.
public:
static char ID; // Pass identification
- SimplifyLibCalls() : FunctionPass(&ID) {}
-
+ SimplifyLibCalls() : FunctionPass(&ID), StrCpy(false), StrCpyChk(true) {}
void InitOptimizations();
bool runOnFunction(Function &F);
@@ -1228,6 +1239,9 @@ void SimplifyLibCalls::InitOptimizations() {
Optimizations["memmove"] = &MemMove;
Optimizations["memset"] = &MemSet;
+ // _chk variants of String and Memory LibCall Optimizations.
+ Optimizations["__strcpy_chk"] = &StrCpyChk;
+
// Math Library Optimizations
Optimizations["powf"] = &Pow;
Optimizations["pow"] = &Pow;
diff --git a/lib/Transforms/Utils/AddrModeMatcher.cpp b/lib/Transforms/Utils/AddrModeMatcher.cpp
index be6b3834f2739..c70bab5492ef6 100644
--- a/lib/Transforms/Utils/AddrModeMatcher.cpp
+++ b/lib/Transforms/Utils/AddrModeMatcher.cpp
@@ -440,8 +440,9 @@ static bool FindAllMemoryUses(Instruction *I,
}
if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) {
- if (UI.getOperandNo() == 0) return true; // Storing addr, not into addr.
- MemoryUses.push_back(std::make_pair(SI, UI.getOperandNo()));
+ unsigned opNo = UI.getOperandNo();
+ if (opNo == 0) return true; // Storing addr, not into addr.
+ MemoryUses.push_back(std::make_pair(SI, opNo));
continue;
}
diff --git a/lib/Transforms/Utils/BreakCriticalEdges.cpp b/lib/Transforms/Utils/BreakCriticalEdges.cpp
index 36573906224d5..8c25ad139b94e 100644
--- a/lib/Transforms/Utils/BreakCriticalEdges.cpp
+++ b/lib/Transforms/Utils/BreakCriticalEdges.cpp
@@ -94,7 +94,7 @@ bool llvm::isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum,
if (TI->getNumSuccessors() == 1) return false;
const BasicBlock *Dest = TI->getSuccessor(SuccNum);
- pred_const_iterator I = pred_begin(Dest), E = pred_end(Dest);
+ const_pred_iterator I = pred_begin(Dest), E = pred_end(Dest);
// If there is more than one predecessor, this is a critical edge...
assert(I != E && "No preds, but we have an edge to the block?");
diff --git a/lib/Transforms/Utils/BuildLibCalls.cpp b/lib/Transforms/Utils/BuildLibCalls.cpp
index b44f019760448..0afccf42f6374 100644
--- a/lib/Transforms/Utils/BuildLibCalls.cpp
+++ b/lib/Transforms/Utils/BuildLibCalls.cpp
@@ -108,7 +108,7 @@ Value *llvm::EmitStrNCpy(Value *Dst, Value *Src, Value *Len,
/// EmitMemCpy - Emit a call to the memcpy function to the builder. This always
-/// expects that the size has type 'intptr_t' and Dst/Src are pointers.
+/// expects that Len has type 'intptr_t' and Dst/Src are pointers.
Value *llvm::EmitMemCpy(Value *Dst, Value *Src, Value *Len,
unsigned Align, IRBuilder<> &B, const TargetData *TD) {
Module *M = B.GetInsertBlock()->getParent()->getParent();
@@ -120,10 +120,34 @@ Value *llvm::EmitMemCpy(Value *Dst, Value *Src, Value *Len,
ConstantInt::get(B.getInt32Ty(), Align));
}
+/// EmitMemCpyChk - Emit a call to the __memcpy_chk function to the builder.
+/// This expects that the Len and ObjSize have type 'intptr_t' and Dst/Src
+/// are pointers.
+Value *llvm::EmitMemCpyChk(Value *Dst, Value *Src, Value *Len, Value *ObjSize,
+ IRBuilder<> &B, const TargetData *TD) {
+ Module *M = B.GetInsertBlock()->getParent()->getParent();
+ AttributeWithIndex AWI;
+ AWI = AttributeWithIndex::get(~0u, Attribute::NoUnwind);
+ LLVMContext &Context = B.GetInsertBlock()->getContext();
+ Value *MemCpy = M->getOrInsertFunction("__memcpy_chk",
+ AttrListPtr::get(&AWI, 1),
+ B.getInt8PtrTy(),
+ B.getInt8PtrTy(),
+ B.getInt8PtrTy(),
+ TD->getIntPtrType(Context),
+ TD->getIntPtrType(Context), NULL);
+ Dst = CastToCStr(Dst, B);
+ Src = CastToCStr(Src, B);
+ CallInst *CI = B.CreateCall4(MemCpy, Dst, Src, Len, ObjSize);
+ if (const Function *F = dyn_cast<Function>(MemCpy->stripPointerCasts()))
+ CI->setCallingConv(F->getCallingConv());
+ return CI;
+}
+
/// EmitMemMove - Emit a call to the memmove function to the builder. This
/// always expects that the size has type 'intptr_t' and Dst/Src are pointers.
Value *llvm::EmitMemMove(Value *Dst, Value *Src, Value *Len,
- unsigned Align, IRBuilder<> &B, const TargetData *TD) {
+ unsigned Align, IRBuilder<> &B, const TargetData *TD) {
Module *M = B.GetInsertBlock()->getParent()->getParent();
LLVMContext &Context = B.GetInsertBlock()->getContext();
const Type *Ty = TD->getIntPtrType(Context);
diff --git a/lib/Transforms/Utils/LowerInvoke.cpp b/lib/Transforms/Utils/LowerInvoke.cpp
index 766c4d99a8f91..bbbcc1adae744 100644
--- a/lib/Transforms/Utils/LowerInvoke.cpp
+++ b/lib/Transforms/Utils/LowerInvoke.cpp
@@ -226,7 +226,7 @@ bool LowerInvoke::insertCheapEHSupport(Function &F) {
bool Changed = false;
for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator())) {
- std::vector<Value*> CallArgs(II->op_begin()+3, II->op_end());
+ std::vector<Value*> CallArgs(II->op_begin(), II->op_end() - 3);
// Insert a normal call instruction...
CallInst *NewCall = CallInst::Create(II->getCalledValue(),
CallArgs.begin(), CallArgs.end(), "",II);
@@ -298,7 +298,7 @@ void LowerInvoke::rewriteExpensiveInvoke(InvokeInst *II, unsigned InvokeNo,
CatchSwitch->addCase(InvokeNoC, II->getUnwindDest());
// Insert a normal call instruction.
- std::vector<Value*> CallArgs(II->op_begin()+3, II->op_end());
+ std::vector<Value*> CallArgs(II->op_begin(), II->op_end() - 3);
CallInst *NewCall = CallInst::Create(II->getCalledValue(),
CallArgs.begin(), CallArgs.end(), "",
II);
diff --git a/lib/Transforms/Utils/PromoteMemoryToRegister.cpp b/lib/Transforms/Utils/PromoteMemoryToRegister.cpp
index 4f5a70b3b2582..f181f3a0a46fd 100644
--- a/lib/Transforms/Utils/PromoteMemoryToRegister.cpp
+++ b/lib/Transforms/Utils/PromoteMemoryToRegister.cpp
@@ -68,7 +68,7 @@ bool llvm::isAllocaPromotable(const AllocaInst *AI) {
// assignments to subsections of the memory unit.
// Only allow direct and non-volatile loads and stores...
- for (Value::use_const_iterator UI = AI->use_begin(), UE = AI->use_end();
+ for (Value::const_use_iterator UI = AI->use_begin(), UE = AI->use_end();
UI != UE; ++UI) // Loop over all of the uses of the alloca
if (const LoadInst *LI = dyn_cast<LoadInst>(*UI)) {
if (LI->isVolatile())
diff --git a/lib/Transforms/Utils/SSAUpdater.cpp b/lib/Transforms/Utils/SSAUpdater.cpp
index a31235a1f5cb3..292332e4f8a60 100644
--- a/lib/Transforms/Utils/SSAUpdater.cpp
+++ b/lib/Transforms/Utils/SSAUpdater.cpp
@@ -14,31 +14,82 @@
#include "llvm/Transforms/Utils/SSAUpdater.h"
#include "llvm/Instructions.h"
#include "llvm/ADT/DenseMap.h"
+#include "llvm/Support/AlignOf.h"
+#include "llvm/Support/Allocator.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/Debug.h"
-#include "llvm/Support/ValueHandle.h"
#include "llvm/Support/raw_ostream.h"
using namespace llvm;
-typedef DenseMap<BasicBlock*, TrackingVH<Value> > AvailableValsTy;
-typedef std::vector<std::pair<BasicBlock*, TrackingVH<Value> > >
- IncomingPredInfoTy;
+/// BBInfo - Per-basic block information used internally by SSAUpdater.
+/// The predecessors of each block are cached here since pred_iterator is
+/// slow and we need to iterate over the blocks at least a few times.
+class SSAUpdater::BBInfo {
+public:
+ Value *AvailableVal; // Value to use in this block.
+ BasicBlock *DefBB; // Block that defines the available value.
+ unsigned NumPreds; // Number of predecessor blocks.
+ BasicBlock **Preds; // Array[NumPreds] of predecessor blocks.
+ unsigned Counter; // Marker to identify blocks already visited.
+ PHINode *PHITag; // Marker for existing PHIs that match.
+
+ BBInfo(BasicBlock *BB, Value *V, BumpPtrAllocator *Allocator);
+};
+typedef DenseMap<BasicBlock*, SSAUpdater::BBInfo*> BBMapTy;
+
+SSAUpdater::BBInfo::BBInfo(BasicBlock *BB, Value *V,
+ BumpPtrAllocator *Allocator)
+ : AvailableVal(V), DefBB(0), NumPreds(0), Preds(0), Counter(0), PHITag(0) {
+ // If this block has a known value, don't bother finding its predecessors.
+ if (V) {
+ DefBB = BB;
+ return;
+ }
+
+ // We can get our predecessor info by walking the pred_iterator list, but it
+ // is relatively slow. If we already have PHI nodes in this block, walk one
+ // of them to get the predecessor list instead.
+ if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin())) {
+ NumPreds = SomePhi->getNumIncomingValues();
+ Preds = static_cast<BasicBlock**>
+ (Allocator->Allocate(NumPreds * sizeof(BasicBlock*),
+ AlignOf<BasicBlock*>::Alignment));
+ for (unsigned pi = 0; pi != NumPreds; ++pi)
+ Preds[pi] = SomePhi->getIncomingBlock(pi);
+ return;
+ }
+
+ // Stash the predecessors in a temporary vector until we know how much space
+ // to allocate for them.
+ SmallVector<BasicBlock*, 10> TmpPreds;
+ for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
+ TmpPreds.push_back(*PI);
+ ++NumPreds;
+ }
+ Preds = static_cast<BasicBlock**>
+ (Allocator->Allocate(NumPreds * sizeof(BasicBlock*),
+ AlignOf<BasicBlock*>::Alignment));
+ memcpy(Preds, TmpPreds.data(), NumPreds * sizeof(BasicBlock*));
+}
+typedef DenseMap<BasicBlock*, Value*> AvailableValsTy;
static AvailableValsTy &getAvailableVals(void *AV) {
return *static_cast<AvailableValsTy*>(AV);
}
-static IncomingPredInfoTy &getIncomingPredInfo(void *IPI) {
- return *static_cast<IncomingPredInfoTy*>(IPI);
+static BBMapTy *getBBMap(void *BM) {
+ return static_cast<BBMapTy*>(BM);
}
+static BumpPtrAllocator *getAllocator(void *BPA) {
+ return static_cast<BumpPtrAllocator*>(BPA);
+}
SSAUpdater::SSAUpdater(SmallVectorImpl<PHINode*> *NewPHI)
- : AV(0), PrototypeValue(0), IPI(0), InsertedPHIs(NewPHI) {}
+ : AV(0), PrototypeValue(0), BM(0), BPA(0), InsertedPHIs(NewPHI) {}
SSAUpdater::~SSAUpdater() {
delete &getAvailableVals(AV);
- delete &getIncomingPredInfo(IPI);
}
/// Initialize - Reset this object to get ready for a new set of SSA
@@ -48,11 +99,6 @@ void SSAUpdater::Initialize(Value *ProtoValue) {
AV = new AvailableValsTy();
else
getAvailableVals(AV).clear();
-
- if (IPI == 0)
- IPI = new IncomingPredInfoTy();
- else
- getIncomingPredInfo(IPI).clear();
PrototypeValue = ProtoValue;
}
@@ -73,7 +119,7 @@ void SSAUpdater::AddAvailableValue(BasicBlock *BB, Value *V) {
/// IsEquivalentPHI - Check if PHI has the same incoming value as specified
/// in ValueMapping for each predecessor block.
-static bool IsEquivalentPHI(PHINode *PHI,
+static bool IsEquivalentPHI(PHINode *PHI,
DenseMap<BasicBlock*, Value*> &ValueMapping) {
unsigned PHINumValues = PHI->getNumIncomingValues();
if (PHINumValues != ValueMapping.size())
@@ -89,38 +135,12 @@ static bool IsEquivalentPHI(PHINode *PHI,
return true;
}
-/// GetExistingPHI - Check if BB already contains a phi node that is equivalent
-/// to the specified mapping from predecessor blocks to incoming values.
-static Value *GetExistingPHI(BasicBlock *BB,
- DenseMap<BasicBlock*, Value*> &ValueMapping) {
- PHINode *SomePHI;
- for (BasicBlock::iterator It = BB->begin();
- (SomePHI = dyn_cast<PHINode>(It)); ++It) {
- if (IsEquivalentPHI(SomePHI, ValueMapping))
- return SomePHI;
- }
- return 0;
-}
-
-/// GetExistingPHI - Check if BB already contains an equivalent phi node.
-/// The InputIt type must be an iterator over std::pair<BasicBlock*, Value*>
-/// objects that specify the mapping from predecessor blocks to incoming values.
-template<typename InputIt>
-static Value *GetExistingPHI(BasicBlock *BB, const InputIt &I,
- const InputIt &E) {
- // Avoid create the mapping if BB has no phi nodes at all.
- if (!isa<PHINode>(BB->begin()))
- return 0;
- DenseMap<BasicBlock*, Value*> ValueMapping(I, E);
- return GetExistingPHI(BB, ValueMapping);
-}
-
/// GetValueAtEndOfBlock - Construct SSA form, materializing a value that is
/// live at the end of the specified block.
Value *SSAUpdater::GetValueAtEndOfBlock(BasicBlock *BB) {
- assert(getIncomingPredInfo(IPI).empty() && "Unexpected Internal State");
+ assert(BM == 0 && BPA == 0 && "Unexpected Internal State");
Value *Res = GetValueAtEndOfBlockInternal(BB);
- assert(getIncomingPredInfo(IPI).empty() && "Unexpected Internal State");
+ assert(BM == 0 && BPA == 0 && "Unexpected Internal State");
return Res;
}
@@ -146,7 +166,7 @@ Value *SSAUpdater::GetValueAtEndOfBlock(BasicBlock *BB) {
Value *SSAUpdater::GetValueInMiddleOfBlock(BasicBlock *BB) {
// If there is no definition of the renamed variable in this block, just use
// GetValueAtEndOfBlock to do our work.
- if (!getAvailableVals(AV).count(BB))
+ if (!HasValueForBlock(BB))
return GetValueAtEndOfBlock(BB);
// Otherwise, we have the hard case. Get the live-in values for each
@@ -193,10 +213,18 @@ Value *SSAUpdater::GetValueInMiddleOfBlock(BasicBlock *BB) {
if (SingularValue != 0)
return SingularValue;
- // Otherwise, we do need a PHI.
- if (Value *ExistingPHI = GetExistingPHI(BB, PredValues.begin(),
- PredValues.end()))
- return ExistingPHI;
+ // Otherwise, we do need a PHI: check to see if we already have one available
+ // in this block that produces the right value.
+ if (isa<PHINode>(BB->begin())) {
+ DenseMap<BasicBlock*, Value*> ValueMapping(PredValues.begin(),
+ PredValues.end());
+ PHINode *SomePHI;
+ for (BasicBlock::iterator It = BB->begin();
+ (SomePHI = dyn_cast<PHINode>(It)); ++It) {
+ if (IsEquivalentPHI(SomePHI, ValueMapping))
+ return SomePHI;
+ }
+ }
// Ok, we have no way out, insert a new one now.
PHINode *InsertedPHI = PHINode::Create(PrototypeValue->getType(),
@@ -226,7 +254,7 @@ Value *SSAUpdater::GetValueInMiddleOfBlock(BasicBlock *BB) {
/// which use their value in the corresponding predecessor.
void SSAUpdater::RewriteUse(Use &U) {
Instruction *User = cast<Instruction>(U.getUser());
-
+
Value *V;
if (PHINode *UserPN = dyn_cast<PHINode>(User))
V = GetValueAtEndOfBlock(UserPN->getIncomingBlock(U));
@@ -236,161 +264,264 @@ void SSAUpdater::RewriteUse(Use &U) {
U.set(V);
}
-
/// GetValueAtEndOfBlockInternal - Check to see if AvailableVals has an entry
/// for the specified BB and if so, return it. If not, construct SSA form by
-/// walking predecessors inserting PHI nodes as needed until we get to a block
-/// where the value is available.
-///
+/// first calculating the required placement of PHIs and then inserting new
+/// PHIs where needed.
Value *SSAUpdater::GetValueAtEndOfBlockInternal(BasicBlock *BB) {
AvailableValsTy &AvailableVals = getAvailableVals(AV);
+ if (Value *V = AvailableVals[BB])
+ return V;
+
+ // Pool allocation used internally by GetValueAtEndOfBlock.
+ BumpPtrAllocator AllocatorObj;
+ BBMapTy BBMapObj;
+ BPA = &AllocatorObj;
+ BM = &BBMapObj;
+
+ BBInfo *Info = new (AllocatorObj) BBInfo(BB, 0, &AllocatorObj);
+ BBMapObj[BB] = Info;
+
+ bool Changed;
+ unsigned Counter = 1;
+ do {
+ Changed = false;
+ FindPHIPlacement(BB, Info, Changed, Counter);
+ ++Counter;
+ } while (Changed);
+
+ FindAvailableVal(BB, Info, Counter);
+
+ BPA = 0;
+ BM = 0;
+ return Info->AvailableVal;
+}
- // Query AvailableVals by doing an insertion of null.
- std::pair<AvailableValsTy::iterator, bool> InsertRes =
- AvailableVals.insert(std::make_pair(BB, TrackingVH<Value>()));
-
- // Handle the case when the insertion fails because we have already seen BB.
- if (!InsertRes.second) {
- // If the insertion failed, there are two cases. The first case is that the
- // value is already available for the specified block. If we get this, just
- // return the value.
- if (InsertRes.first->second != 0)
- return InsertRes.first->second;
-
- // Otherwise, if the value we find is null, then this is the value is not
- // known but it is being computed elsewhere in our recursion. This means
- // that we have a cycle. Handle this by inserting a PHI node and returning
- // it. When we get back to the first instance of the recursion we will fill
- // in the PHI node.
- return InsertRes.first->second =
- PHINode::Create(PrototypeValue->getType(), PrototypeValue->getName(),
- &BB->front());
+/// FindPHIPlacement - Recursively visit the predecessors of a block to find
+/// the reaching definition for each predecessor and then determine whether
+/// a PHI is needed in this block.
+void SSAUpdater::FindPHIPlacement(BasicBlock *BB, BBInfo *Info, bool &Changed,
+ unsigned Counter) {
+ AvailableValsTy &AvailableVals = getAvailableVals(AV);
+ BBMapTy *BBMap = getBBMap(BM);
+ BumpPtrAllocator *Allocator = getAllocator(BPA);
+ bool BBNeedsPHI = false;
+ BasicBlock *SamePredDefBB = 0;
+
+ // If there are no predecessors, then we must have found an unreachable
+ // block. Treat it as a definition with 'undef'.
+ if (Info->NumPreds == 0) {
+ Info->AvailableVal = UndefValue::get(PrototypeValue->getType());
+ Info->DefBB = BB;
+ return;
}
- // Okay, the value isn't in the map and we just inserted a null in the entry
- // to indicate that we're processing the block. Since we have no idea what
- // value is in this block, we have to recurse through our predecessors.
- //
- // While we're walking our predecessors, we keep track of them in a vector,
- // then insert a PHI node in the end if we actually need one. We could use a
- // smallvector here, but that would take a lot of stack space for every level
- // of the recursion, just use IncomingPredInfo as an explicit stack.
- IncomingPredInfoTy &IncomingPredInfo = getIncomingPredInfo(IPI);
- unsigned FirstPredInfoEntry = IncomingPredInfo.size();
-
- // As we're walking the predecessors, keep track of whether they are all
- // producing the same value. If so, this value will capture it, if not, it
- // will get reset to null. We distinguish the no-predecessor case explicitly
- // below.
- TrackingVH<Value> ExistingValue;
-
- // We can get our predecessor info by walking the pred_iterator list, but it
- // is relatively slow. If we already have PHI nodes in this block, walk one
- // of them to get the predecessor list instead.
- if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin())) {
- for (unsigned i = 0, e = SomePhi->getNumIncomingValues(); i != e; ++i) {
- BasicBlock *PredBB = SomePhi->getIncomingBlock(i);
- Value *PredVal = GetValueAtEndOfBlockInternal(PredBB);
- IncomingPredInfo.push_back(std::make_pair(PredBB, PredVal));
-
- // Set ExistingValue to singular value from all predecessors so far.
- if (i == 0)
- ExistingValue = PredVal;
- else if (PredVal != ExistingValue)
- ExistingValue = 0;
+ Info->Counter = Counter;
+ for (unsigned pi = 0; pi != Info->NumPreds; ++pi) {
+ BasicBlock *Pred = Info->Preds[pi];
+ BBMapTy::value_type &BBMapBucket = BBMap->FindAndConstruct(Pred);
+ if (!BBMapBucket.second) {
+ Value *PredVal = AvailableVals.lookup(Pred);
+ BBMapBucket.second = new (*Allocator) BBInfo(Pred, PredVal, Allocator);
}
- } else {
- bool isFirstPred = true;
- for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
- BasicBlock *PredBB = *PI;
- Value *PredVal = GetValueAtEndOfBlockInternal(PredBB);
- IncomingPredInfo.push_back(std::make_pair(PredBB, PredVal));
-
- // Set ExistingValue to singular value from all predecessors so far.
- if (isFirstPred) {
- ExistingValue = PredVal;
- isFirstPred = false;
- } else if (PredVal != ExistingValue)
- ExistingValue = 0;
+ BBInfo *PredInfo = BBMapBucket.second;
+ BasicBlock *DefBB = 0;
+ if (!PredInfo->AvailableVal) {
+ if (PredInfo->Counter != Counter)
+ FindPHIPlacement(Pred, PredInfo, Changed, Counter);
+
+ // Ignore back edges where the value is not yet known.
+ if (!PredInfo->DefBB)
+ continue;
}
+ DefBB = PredInfo->DefBB;
+
+ if (!SamePredDefBB)
+ SamePredDefBB = DefBB;
+ else if (DefBB != SamePredDefBB)
+ BBNeedsPHI = true;
}
- // If there are no predecessors, then we must have found an unreachable block
- // just return 'undef'. Since there are no predecessors, InsertRes must not
- // be invalidated.
- if (IncomingPredInfo.size() == FirstPredInfoEntry)
- return InsertRes.first->second = UndefValue::get(PrototypeValue->getType());
-
- /// Look up BB's entry in AvailableVals. 'InsertRes' may be invalidated. If
- /// this block is involved in a loop, a no-entry PHI node will have been
- /// inserted as InsertedVal. Otherwise, we'll still have the null we inserted
- /// above.
- TrackingVH<Value> &InsertedVal = AvailableVals[BB];
-
- // If the predecessor values are not all the same, then check to see if there
- // is an existing PHI that can be used.
- if (!ExistingValue)
- ExistingValue = GetExistingPHI(BB,
- IncomingPredInfo.begin()+FirstPredInfoEntry,
- IncomingPredInfo.end());
-
- // If there is an existing value we can use, then we don't need to insert a
- // PHI. This is the simple and common case.
- if (ExistingValue) {
- // If a PHI node got inserted, replace it with the existing value and delete
- // it.
- if (InsertedVal) {
- PHINode *OldVal = cast<PHINode>(InsertedVal);
- // Be careful about dead loops. These RAUW's also update InsertedVal.
- if (InsertedVal != ExistingValue)
- OldVal->replaceAllUsesWith(ExistingValue);
- else
- OldVal->replaceAllUsesWith(UndefValue::get(InsertedVal->getType()));
- OldVal->eraseFromParent();
- } else {
- InsertedVal = ExistingValue;
- }
+ BasicBlock *NewDefBB = (BBNeedsPHI ? BB : SamePredDefBB);
+ if (Info->DefBB != NewDefBB) {
+ Changed = true;
+ Info->DefBB = NewDefBB;
+ }
+}
- // Either path through the 'if' should have set InsertedVal -> ExistingVal.
- assert((InsertedVal == ExistingValue || isa<UndefValue>(InsertedVal)) &&
- "RAUW didn't change InsertedVal to be ExistingValue");
+/// FindAvailableVal - If this block requires a PHI, first check if an existing
+/// PHI matches the PHI placement and reaching definitions computed earlier,
+/// and if not, create a new PHI. Visit all the block's predecessors to
+/// calculate the available value for each one and fill in the incoming values
+/// for a new PHI.
+void SSAUpdater::FindAvailableVal(BasicBlock *BB, BBInfo *Info,
+ unsigned Counter) {
+ if (Info->AvailableVal || Info->Counter == Counter)
+ return;
- // Drop the entries we added in IncomingPredInfo to restore the stack.
- IncomingPredInfo.erase(IncomingPredInfo.begin()+FirstPredInfoEntry,
- IncomingPredInfo.end());
- return ExistingValue;
+ AvailableValsTy &AvailableVals = getAvailableVals(AV);
+ BBMapTy *BBMap = getBBMap(BM);
+
+ // Check if there needs to be a PHI in BB.
+ PHINode *NewPHI = 0;
+ if (Info->DefBB == BB) {
+ // Look for an existing PHI.
+ FindExistingPHI(BB);
+ if (!Info->AvailableVal) {
+ NewPHI = PHINode::Create(PrototypeValue->getType(),
+ PrototypeValue->getName(), &BB->front());
+ NewPHI->reserveOperandSpace(Info->NumPreds);
+ Info->AvailableVal = NewPHI;
+ AvailableVals[BB] = NewPHI;
+ }
}
- // Otherwise, we do need a PHI: insert one now if we don't already have one.
- if (InsertedVal == 0)
- InsertedVal = PHINode::Create(PrototypeValue->getType(),
- PrototypeValue->getName(), &BB->front());
+ // Iterate through the block's predecessors.
+ Info->Counter = Counter;
+ for (unsigned pi = 0; pi != Info->NumPreds; ++pi) {
+ BasicBlock *Pred = Info->Preds[pi];
+ BBInfo *PredInfo = (*BBMap)[Pred];
+ FindAvailableVal(Pred, PredInfo, Counter);
+ if (NewPHI) {
+ // Skip to the nearest preceding definition.
+ if (PredInfo->DefBB != Pred)
+ PredInfo = (*BBMap)[PredInfo->DefBB];
+ NewPHI->addIncoming(PredInfo->AvailableVal, Pred);
+ } else if (!Info->AvailableVal)
+ Info->AvailableVal = PredInfo->AvailableVal;
+ }
- PHINode *InsertedPHI = cast<PHINode>(InsertedVal);
- InsertedPHI->reserveOperandSpace(IncomingPredInfo.size()-FirstPredInfoEntry);
+ if (NewPHI) {
+ DEBUG(dbgs() << " Inserted PHI: " << *NewPHI << "\n");
- // Fill in all the predecessors of the PHI.
- for (IncomingPredInfoTy::iterator I =
- IncomingPredInfo.begin()+FirstPredInfoEntry,
- E = IncomingPredInfo.end(); I != E; ++I)
- InsertedPHI->addIncoming(I->second, I->first);
+ // If the client wants to know about all new instructions, tell it.
+ if (InsertedPHIs) InsertedPHIs->push_back(NewPHI);
+ }
+}
- // Drop the entries we added in IncomingPredInfo to restore the stack.
- IncomingPredInfo.erase(IncomingPredInfo.begin()+FirstPredInfoEntry,
- IncomingPredInfo.end());
+/// FindExistingPHI - Look through the PHI nodes in a block to see if any of
+/// them match what is needed.
+void SSAUpdater::FindExistingPHI(BasicBlock *BB) {
+ PHINode *SomePHI;
+ for (BasicBlock::iterator It = BB->begin();
+ (SomePHI = dyn_cast<PHINode>(It)); ++It) {
+ if (CheckIfPHIMatches(SomePHI)) {
+ RecordMatchingPHI(SomePHI);
+ break;
+ }
+ ClearPHITags(SomePHI);
+ }
+}
- // See if the PHI node can be merged to a single value. This can happen in
- // loop cases when we get a PHI of itself and one other value.
- if (Value *ConstVal = InsertedPHI->hasConstantValue()) {
- InsertedPHI->replaceAllUsesWith(ConstVal);
- InsertedPHI->eraseFromParent();
- InsertedVal = ConstVal;
- } else {
- DEBUG(dbgs() << " Inserted PHI: " << *InsertedPHI << "\n");
+/// CheckIfPHIMatches - Check if a PHI node matches the placement and values
+/// in the BBMap.
+bool SSAUpdater::CheckIfPHIMatches(PHINode *PHI) {
+ BBMapTy *BBMap = getBBMap(BM);
+ SmallVector<PHINode*, 20> WorkList;
+ WorkList.push_back(PHI);
+
+ // Mark that the block containing this PHI has been visited.
+ (*BBMap)[PHI->getParent()]->PHITag = PHI;
+
+ while (!WorkList.empty()) {
+ PHI = WorkList.pop_back_val();
+
+ // Iterate through the PHI's incoming values.
+ for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) {
+ Value *IncomingVal = PHI->getIncomingValue(i);
+ BasicBlock *Pred = PHI->getIncomingBlock(i);
+ BBInfo *PredInfo = (*BBMap)[Pred];
+ // Skip to the nearest preceding definition.
+ if (PredInfo->DefBB != Pred) {
+ Pred = PredInfo->DefBB;
+ PredInfo = (*BBMap)[Pred];
+ }
+
+ // Check if it matches the expected value.
+ if (PredInfo->AvailableVal) {
+ if (IncomingVal == PredInfo->AvailableVal)
+ continue;
+ return false;
+ }
+
+ // Check if the value is a PHI in the correct block.
+ PHINode *IncomingPHIVal = dyn_cast<PHINode>(IncomingVal);
+ if (!IncomingPHIVal || IncomingPHIVal->getParent() != Pred)
+ return false;
+
+ // If this block has already been visited, check if this PHI matches.
+ if (PredInfo->PHITag) {
+ if (IncomingPHIVal == PredInfo->PHITag)
+ continue;
+ return false;
+ }
+ PredInfo->PHITag = IncomingPHIVal;
+
+ WorkList.push_back(IncomingPHIVal);
+ }
+ }
+ return true;
+}
- // If the client wants to know about all new instructions, tell it.
- if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI);
+/// RecordMatchingPHI - For a PHI node that matches, record it and its input
+/// PHIs in both the BBMap and the AvailableVals mapping.
+void SSAUpdater::RecordMatchingPHI(PHINode *PHI) {
+ BBMapTy *BBMap = getBBMap(BM);
+ AvailableValsTy &AvailableVals = getAvailableVals(AV);
+ SmallVector<PHINode*, 20> WorkList;
+ WorkList.push_back(PHI);
+
+ // Record this PHI.
+ BasicBlock *BB = PHI->getParent();
+ AvailableVals[BB] = PHI;
+ (*BBMap)[BB]->AvailableVal = PHI;
+
+ while (!WorkList.empty()) {
+ PHI = WorkList.pop_back_val();
+
+ // Iterate through the PHI's incoming values.
+ for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) {
+ PHINode *IncomingPHIVal = dyn_cast<PHINode>(PHI->getIncomingValue(i));
+ if (!IncomingPHIVal) continue;
+ BB = IncomingPHIVal->getParent();
+ BBInfo *Info = (*BBMap)[BB];
+ if (!Info || Info->AvailableVal)
+ continue;
+
+ // Record the PHI and add it to the worklist.
+ AvailableVals[BB] = IncomingPHIVal;
+ Info->AvailableVal = IncomingPHIVal;
+ WorkList.push_back(IncomingPHIVal);
+ }
}
+}
- return InsertedVal;
+/// ClearPHITags - When one of the existing PHI nodes fails to match, clear
+/// the PHITag values that were stored in the BBMap when checking to see if
+/// it matched.
+void SSAUpdater::ClearPHITags(PHINode *PHI) {
+ BBMapTy *BBMap = getBBMap(BM);
+ SmallVector<PHINode*, 20> WorkList;
+ WorkList.push_back(PHI);
+
+ // Clear the tag for this PHI.
+ (*BBMap)[PHI->getParent()]->PHITag = 0;
+
+ while (!WorkList.empty()) {
+ PHI = WorkList.pop_back_val();
+
+ // Iterate through the PHI's incoming values.
+ for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) {
+ PHINode *IncomingPHIVal = dyn_cast<PHINode>(PHI->getIncomingValue(i));
+ if (!IncomingPHIVal) continue;
+ BasicBlock *BB = IncomingPHIVal->getParent();
+ BBInfo *Info = (*BBMap)[BB];
+ if (!Info || Info->AvailableVal || !Info->PHITag)
+ continue;
+
+ // Clear the tag and add the PHI to the worklist.
+ Info->PHITag = 0;
+ WorkList.push_back(IncomingPHIVal);
+ }
+ }
}
diff --git a/lib/Transforms/Utils/SimplifyCFG.cpp b/lib/Transforms/Utils/SimplifyCFG.cpp
index 2ce5bdcd61d43..9f2209dfcfc06 100644
--- a/lib/Transforms/Utils/SimplifyCFG.cpp
+++ b/lib/Transforms/Utils/SimplifyCFG.cpp
@@ -224,7 +224,7 @@ static bool DominatesMergePoint(Value *V, BasicBlock *BB,
if (BI->isUnconditional() && BI->getSuccessor(0) == BB) {
if (!AggressiveInsts) return false;
// Okay, it looks like the instruction IS in the "condition". Check to
- // see if its a cheap instruction to unconditionally compute, and if it
+ // see if it's a cheap instruction to unconditionally compute, and if it
// only uses stuff defined outside of the condition. If so, hoist it out.
if (!I->isSafeToSpeculativelyExecute())
return false;
@@ -1768,7 +1768,7 @@ bool SimplifyCFGOpt::run(BasicBlock *BB) {
Pred->getInstList().remove(II); // Take out of symbol table
// Insert the call now.
- SmallVector<Value*,8> Args(II->op_begin()+3, II->op_end());
+ SmallVector<Value*,8> Args(II->op_begin(), II->op_end()-3);
CallInst *CI = CallInst::Create(II->getCalledValue(),
Args.begin(), Args.end(),
II->getName(), BI);
@@ -1970,13 +1970,13 @@ bool SimplifyCFGOpt::run(BasicBlock *BB) {
II->removeFromParent(); // Take out of symbol table
// Insert the call now...
- SmallVector<Value*, 8> Args(II->op_begin()+3, II->op_end());
+ SmallVector<Value*, 8> Args(II->op_begin(), II->op_end()-3);
CallInst *CI = CallInst::Create(II->getCalledValue(),
Args.begin(), Args.end(),
II->getName(), BI);
CI->setCallingConv(II->getCallingConv());
CI->setAttributes(II->getAttributes());
- // If the invoke produced a value, the Call does now instead.
+ // If the invoke produced a value, the call does now instead.
II->replaceAllUsesWith(CI);
delete II;
Changed = true;