#include "llvm/Instructions.h"
#include "llvm/IntrinsicInst.h"
#include "llvm/Module.h"
+#include "llvm/ParamAttrsList.h"
#include "llvm/Pass.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Target/TargetData.h"
+#include "llvm/Support/CallSite.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
+#include "llvm/Support/GetElementPtrTypeIterator.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
STATISTIC(NumShrunkToBool , "Number of global vars shrunk to booleans");
STATISTIC(NumFastCallFns , "Number of functions converted to fastcc");
STATISTIC(NumCtorsEvaluated, "Number of static ctors evaluated");
+STATISTIC(NumNestRemoved , "Number of nest attributes removed");
namespace {
struct VISIBILITY_HIDDEN GlobalOpt : public ModulePass {
/// HasPHIUser - Set to true if this global has a user that is a PHI node.
bool HasPHIUser;
- /// isNotSuitableForSRA - Keep track of whether any SRA preventing users of
- /// the global exist. Such users include GEP instruction with variable
- /// indexes, and non-gep/load/store users like constant expr casts.
- bool isNotSuitableForSRA;
-
GlobalStatus() : isLoaded(false), StoredType(NotStored), StoredOnceValue(0),
AccessingFunction(0), HasMultipleAccessingFunctions(false),
- HasNonInstructionUser(false), HasPHIUser(false),
- isNotSuitableForSRA(false) {}
+ HasNonInstructionUser(false), HasPHIUser(false) {}
};
GS.HasNonInstructionUser = true;
if (AnalyzeGlobal(CE, GS, PHIUsers)) return true;
- if (CE->getOpcode() != Instruction::GetElementPtr)
- GS.isNotSuitableForSRA = true;
- else if (!GS.isNotSuitableForSRA) {
- // Check to see if this ConstantExpr GEP is SRA'able. In particular, we
- // don't like < 3 operand CE's, and we don't like non-constant integer
- // indices.
- if (CE->getNumOperands() < 3 || !CE->getOperand(1)->isNullValue())
- GS.isNotSuitableForSRA = true;
- else {
- for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i)
- if (!isa<ConstantInt>(CE->getOperand(i))) {
- GS.isNotSuitableForSRA = true;
- break;
- }
- }
- }
} else if (Instruction *I = dyn_cast<Instruction>(*UI)) {
if (!GS.HasMultipleAccessingFunctions) {
else if (GS.AccessingFunction != F)
GS.HasMultipleAccessingFunctions = true;
}
- if (isa<LoadInst>(I)) {
+ if (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)) {
// Don't allow a store OF the address, only stores TO the address.
if (SI->getOperand(0) == V) return true;
+ if (SI->isVolatile()) return true; // Don't hack on volatile stores.
+
// If this is a direct store to the global (i.e., the global is a scalar
// value, not an aggregate), keep more specific information about
// stores.
- if (GS.StoredType != GlobalStatus::isStored)
+ if (GS.StoredType != GlobalStatus::isStored) {
if (GlobalVariable *GV = dyn_cast<GlobalVariable>(SI->getOperand(1))){
Value *StoredVal = SI->getOperand(0);
if (StoredVal == GV->getInitializer()) {
} else {
GS.StoredType = GlobalStatus::isStored;
}
+ }
} else if (isa<GetElementPtrInst>(I)) {
if (AnalyzeGlobal(I, GS, PHIUsers)) return true;
-
- // If the first two indices are constants, this can be SRA'd.
- if (isa<GlobalVariable>(I->getOperand(0))) {
- if (I->getNumOperands() < 3 || !isa<Constant>(I->getOperand(1)) ||
- !cast<Constant>(I->getOperand(1))->isNullValue() ||
- !isa<ConstantInt>(I->getOperand(2)))
- GS.isNotSuitableForSRA = true;
- } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(I->getOperand(0))){
- if (CE->getOpcode() != Instruction::GetElementPtr ||
- CE->getNumOperands() < 3 || I->getNumOperands() < 2 ||
- !isa<Constant>(I->getOperand(0)) ||
- !cast<Constant>(I->getOperand(0))->isNullValue())
- GS.isNotSuitableForSRA = true;
- } else {
- GS.isNotSuitableForSRA = true;
- }
} else if (isa<SelectInst>(I)) {
if (AnalyzeGlobal(I, GS, PHIUsers)) return true;
- GS.isNotSuitableForSRA = true;
} else if (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).second) // Not already visited.
if (AnalyzeGlobal(I, GS, PHIUsers)) return true;
- GS.isNotSuitableForSRA = true;
GS.HasPHIUser = true;
} else if (isa<CmpInst>(I)) {
- GS.isNotSuitableForSRA = true;
} else if (isa<MemCpyInst>(I) || isa<MemMoveInst>(I)) {
if (I->getOperand(1) == V)
GS.StoredType = GlobalStatus::isStored;
if (I->getOperand(2) == V)
GS.isLoaded = true;
- GS.isNotSuitableForSRA = true;
} else if (isa<MemSetInst>(I)) {
assert(I->getOperand(1) == V && "Memset only takes one pointer!");
GS.StoredType = GlobalStatus::isStored;
- GS.isNotSuitableForSRA = true;
} else {
return true; // Any other non-load instruction might take address!
}
return Changed;
}
+/// isSafeSROAElementUse - Return true if the specified instruction is a safe
+/// user of a derived expression from a global that we want to SROA.
+static bool isSafeSROAElementUse(Value *V) {
+ // We might have a dead and dangling constant hanging off of here.
+ if (Constant *C = dyn_cast<Constant>(V))
+ return ConstantIsDead(C);
+
+ Instruction *I = dyn_cast<Instruction>(V);
+ if (!I) return false;
+
+ // Loads are ok.
+ if (isa<LoadInst>(I)) return true;
+
+ // Stores *to* the pointer are ok.
+ if (StoreInst *SI = dyn_cast<StoreInst>(I))
+ return SI->getOperand(0) != V;
+
+ // Otherwise, it must be a GEP.
+ GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I);
+ if (GEPI == 0) return false;
+
+ if (GEPI->getNumOperands() < 3 || !isa<Constant>(GEPI->getOperand(1)) ||
+ !cast<Constant>(GEPI->getOperand(1))->isNullValue())
+ return false;
+
+ for (Value::use_iterator I = GEPI->use_begin(), E = GEPI->use_end();
+ I != E; ++I)
+ if (!isSafeSROAElementUse(*I))
+ return false;
+ return true;
+}
+
-/// UsersSafeToSRA - Look at all uses of the global and decide whether it is
-/// safe for us to perform this transformation.
+/// IsUserOfGlobalSafeForSRA - U is a direct user of the specified global value.
+/// Look at it and its uses and decide whether it is safe to SROA this global.
///
-static bool UsersSafeToSRA(Value *V) {
- for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E;++UI){
- if (ConstantExpr *CE = dyn_cast<ConstantExpr>(*UI)) {
- if (CE->getOpcode() != Instruction::GetElementPtr)
- return false;
+static bool IsUserOfGlobalSafeForSRA(User *U, GlobalValue *GV) {
+ // The user of the global must be a GEP Inst or a ConstantExpr GEP.
+ if (!isa<GetElementPtrInst>(U) &&
+ (!isa<ConstantExpr>(U) ||
+ cast<ConstantExpr>(U)->getOpcode() != Instruction::GetElementPtr))
+ return false;
+
+ // Check to see if this ConstantExpr GEP is SRA'able. In particular, we
+ // don't like < 3 operand CE's, and we don't like non-constant integer
+ // indices. This enforces that all uses are 'gep GV, 0, C, ...' for some
+ // value of C.
+ if (U->getNumOperands() < 3 || !isa<Constant>(U->getOperand(1)) ||
+ !cast<Constant>(U->getOperand(1))->isNullValue() ||
+ !isa<ConstantInt>(U->getOperand(2)))
+ return false;
- // Check to see if this ConstantExpr GEP is SRA'able. In particular, we
- // don't like < 3 operand CE's, and we don't like non-constant integer
- // indices.
- if (CE->getNumOperands() < 3 || !CE->getOperand(1)->isNullValue())
- return false;
-
- for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i)
- if (!isa<ConstantInt>(CE->getOperand(i)))
- return false;
-
- if (!UsersSafeToSRA(CE)) return false;
- continue;
- }
+ gep_type_iterator GEPI = gep_type_begin(U), E = gep_type_end(U);
+ ++GEPI; // Skip over the pointer index.
+
+ // If this is a use of an array allocation, do a bit more checking for sanity.
+ if (const ArrayType *AT = dyn_cast<ArrayType>(*GEPI)) {
+ uint64_t NumElements = AT->getNumElements();
+ ConstantInt *Idx = cast<ConstantInt>(U->getOperand(2));
- if (Instruction *I = dyn_cast<Instruction>(*UI)) {
- if (isa<LoadInst>(I)) continue;
+ // Check to make sure that index falls within the array. If not,
+ // something funny is going on, so we won't do the optimization.
+ //
+ if (Idx->getZExtValue() >= NumElements)
+ return false;
- if (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 false;
- continue;
- }
+ // We cannot scalar repl this level of the array unless any array
+ // sub-indices are in-range constants. In particular, consider:
+ // A[0][i]. We cannot know that the user isn't doing invalid things like
+ // allowing i to index an out-of-range subscript that accesses A[1].
+ //
+ // Scalar replacing *just* the outer index of the array is probably not
+ // going to be a win anyway, so just give up.
+ for (++GEPI; // Skip array index.
+ GEPI != E && (isa<ArrayType>(*GEPI) || isa<VectorType>(*GEPI));
+ ++GEPI) {
+ uint64_t NumElements;
+ if (const ArrayType *SubArrayTy = dyn_cast<ArrayType>(*GEPI))
+ NumElements = SubArrayTy->getNumElements();
+ else
+ NumElements = cast<VectorType>(*GEPI)->getNumElements();
- if (isa<GetElementPtrInst>(I)) {
- if (!UsersSafeToSRA(I)) return false;
-
- // If the first two indices are constants, this can be SRA'd.
- if (isa<GlobalVariable>(I->getOperand(0))) {
- if (I->getNumOperands() < 3 || !isa<Constant>(I->getOperand(1)) ||
- !cast<Constant>(I->getOperand(1))->isNullValue() ||
- !isa<ConstantInt>(I->getOperand(2)))
- return false;
- continue;
- }
-
- if (ConstantExpr *CE = dyn_cast<ConstantExpr>(I->getOperand(0))){
- if (CE->getOpcode() != Instruction::GetElementPtr ||
- CE->getNumOperands() < 3 || I->getNumOperands() < 2 ||
- !isa<Constant>(I->getOperand(0)) ||
- !cast<Constant>(I->getOperand(0))->isNullValue())
- return false;
- continue;
- }
+ ConstantInt *IdxVal = dyn_cast<ConstantInt>(GEPI.getOperand());
+ if (!IdxVal || IdxVal->getZExtValue() >= NumElements)
return false;
- }
- return false; // Any other instruction is not safe.
}
- if (Constant *C = dyn_cast<Constant>(*UI)) {
- // We might have a dead and dangling constant hanging off of here.
- if (!ConstantIsDead(C))
- return false;
- continue;
- }
- // Otherwise must be some other user.
- return false;
}
-
+
+ for (Value::use_iterator I = U->use_begin(), E = U->use_end(); I != E; ++I)
+ if (!isSafeSROAElementUse(*I))
+ return false;
+ return true;
+}
+
+/// GlobalUsersSafeToSRA - Look at all uses of the global and decide whether it
+/// is safe for us to perform this transformation.
+///
+static bool GlobalUsersSafeToSRA(GlobalValue *GV) {
+ for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end();
+ UI != E; ++UI) {
+ if (!IsUserOfGlobalSafeForSRA(*UI, GV))
+ return false;
+ }
return true;
}
+
/// SRAGlobal - Perform scalar replacement of aggregates on the specified global
/// variable. This opens the door for other optimizations by exposing the
/// insert so that the caller can reprocess it.
static GlobalVariable *SRAGlobal(GlobalVariable *GV) {
// Make sure this global only has simple uses that we can SRA.
- if (!UsersSafeToSRA(GV))
+ if (!GlobalUsersSafeToSRA(GV))
return 0;
assert(GV->hasInternalLinkage() && !GV->isConstant());
Value *NewPtr = NewGlobals[Val];
// Form a shorter GEP if needed.
- if (GEP->getNumOperands() > 3)
+ if (GEP->getNumOperands() > 3) {
if (ConstantExpr *CE = dyn_cast<ConstantExpr>(GEP)) {
SmallVector<Constant*, 8> Idxs;
Idxs.push_back(NullInt);
NewPtr = new GetElementPtrInst(NewPtr, Idxs.begin(), Idxs.end(),
GEPI->getName()+"."+utostr(Val), GEPI);
}
+ }
GEP->replaceAllUsesWith(NewPtr);
if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(GEP))
cerr << " HasMultipleAccessingFunctions = "
<< GS.HasMultipleAccessingFunctions << "\n";
cerr << " HasNonInstructionUser = " << GS.HasNonInstructionUser<<"\n";
- cerr << " isNotSuitableForSRA = " << GS.isNotSuitableForSRA << "\n";
cerr << "\n";
#endif
/// function, changing them to FastCC.
static void ChangeCalleesToFastCall(Function *F) {
for (Value::use_iterator UI = F->use_begin(), E = F->use_end(); UI != E;++UI){
- Instruction *User = cast<Instruction>(*UI);
- if (CallInst *CI = dyn_cast<CallInst>(User))
- CI->setCallingConv(CallingConv::Fast);
- else
- cast<InvokeInst>(User)->setCallingConv(CallingConv::Fast);
+ CallSite User(cast<Instruction>(*UI));
+ User.setCallingConv(CallingConv::Fast);
+ }
+}
+
+static const ParamAttrsList *StripNest(const ParamAttrsList *Attrs) {
+ if (!Attrs)
+ return NULL;
+
+ for (unsigned i = 0, e = Attrs->size(); i != e; ++i) {
+ if ((Attrs->getParamAttrsAtIndex(i) & ParamAttr::Nest) == 0)
+ continue;
+
+ Attrs = ParamAttrsList::excludeAttrs(Attrs, Attrs->getParamIndex(i),
+ ParamAttr::Nest);
+ // There can be only one.
+ break;
+ }
+
+ return Attrs;
+}
+
+static void RemoveNestAttribute(Function *F) {
+ F->setParamAttrs(StripNest(F->getParamAttrs()));
+ for (Value::use_iterator UI = F->use_begin(), E = F->use_end(); UI != E;++UI){
+ CallSite User(cast<Instruction>(*UI));
+ User.setParamAttrs(StripNest(User.getParamAttrs()));
}
}
M.getFunctionList().erase(F);
Changed = true;
++NumFnDeleted;
- } else if (F->hasInternalLinkage() &&
- F->getCallingConv() == CallingConv::C && !F->isVarArg() &&
- OnlyCalledDirectly(F)) {
- // If this function has C calling conventions, is not a varargs
- // function, and is only called directly, promote it to use the Fast
- // calling convention.
- F->setCallingConv(CallingConv::Fast);
- ChangeCalleesToFastCall(F);
- ++NumFastCallFns;
- Changed = true;
+ } else if (F->hasInternalLinkage()) {
+ if (F->getCallingConv() == CallingConv::C && !F->isVarArg() &&
+ OnlyCalledDirectly(F)) {
+ // If this function has C calling conventions, is not a varargs
+ // function, and is only called directly, promote it to use the Fast
+ // calling convention.
+ F->setCallingConv(CallingConv::Fast);
+ ChangeCalleesToFastCall(F);
+ ++NumFastCallFns;
+ Changed = true;
+ }
+
+ if (F->getParamAttrs() &&
+ F->getParamAttrs()->hasAttrSomewhere(ParamAttr::Nest) &&
+ OnlyCalledDirectly(F)) {
+ // The function is not used by a trampoline intrinsic, so it is safe
+ // to remove the 'nest' attribute.
+ RemoveNestAttribute(F);
+ ++NumNestRemoved;
+ Changed = true;
+ }
}
}
return Changed;