#include "llvm/Instructions.h"
#include "llvm/IntrinsicInst.h"
#include "llvm/Module.h"
+#include "llvm/ParameterAttributes.h"
#include "llvm/Pass.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Target/TargetData.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.
}
} 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;
+}
+
+
+/// 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 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;
+
+ 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));
+
+ // 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;
+
+ // 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();
+
+ ConstantInt *IdxVal = dyn_cast<ConstantInt>(GEPI.getOperand());
+ if (!IdxVal || IdxVal->getZExtValue() >= NumElements)
+ 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
/// behavior of the program in a more fine-grained way. We have determined that
/// this transformation is safe already. We return the first global variable we
/// 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 (!GlobalUsersSafeToSRA(GV))
+ return 0;
+
assert(GV->hasInternalLinkage() && !GV->isConstant());
Constant *Init = GV->getInitializer();
const Type *Ty = Init->getType();
return false;
}
-/// ShrinkGlobalToBoolean - At this point, we have learned that the only two
-/// values ever stored into GV are its initializer and OtherVal.
-static void ShrinkGlobalToBoolean(GlobalVariable *GV, Constant *OtherVal) {
+/// TryToShrinkGlobalToBoolean - At this point, we have learned that the only
+/// two values ever stored into GV are its initializer and OtherVal. See if we
+/// can shrink the global into a boolean and select between the two values
+/// whenever it is used. This exposes the values to other scalar optimizations.
+static bool TryToShrinkGlobalToBoolean(GlobalVariable *GV, Constant *OtherVal) {
+ const Type *GVElType = GV->getType()->getElementType();
+
+ // If GVElType is already i1, it is already shrunk. If the type of the GV is
+ // an FP value or vector, don't do this optimization because a select between
+ // them is very expensive and unlikely to lead to later simplification.
+ if (GVElType == Type::Int1Ty || GVElType->isFloatingPoint() ||
+ isa<VectorType>(GVElType))
+ return false;
+
+ // Walk the use list of the global seeing if all the uses are load or store.
+ // If there is anything else, bail out.
+ for (Value::use_iterator I = GV->use_begin(), E = GV->use_end(); I != E; ++I)
+ if (!isa<LoadInst>(I) && !isa<StoreInst>(I))
+ return false;
+
+ DOUT << " *** SHRINKING TO BOOL: " << *GV;
+
// Create the new global, initializing it to false.
GlobalVariable *NewGV = new GlobalVariable(Type::Int1Ty, false,
GlobalValue::InternalLinkage, ConstantInt::getFalse(),
}
}
new StoreInst(StoreVal, NewGV, SI);
- } else if (!UI->use_empty()) {
+ } else {
// Change the load into a load of bool then a select.
LoadInst *LI = cast<LoadInst>(UI);
LoadInst *NLI = new LoadInst(NewGV, LI->getName()+".b", LI);
}
GV->eraseFromParent();
+ return true;
}
cerr << " HasMultipleAccessingFunctions = "
<< GS.HasMultipleAccessingFunctions << "\n";
cerr << " HasNonInstructionUser = " << GS.HasNonInstructionUser<<"\n";
- cerr << " isNotSuitableForSRA = " << GS.isNotSuitableForSRA << "\n";
cerr << "\n";
#endif
++NumMarked;
return true;
- } else if (!GS.isNotSuitableForSRA &&
- !GV->getInitializer()->getType()->isFirstClassType()) {
+ } else if (!GV->getInitializer()->getType()->isFirstClassType()) {
if (GlobalVariable *FirstNewGV = SRAGlobal(GV)) {
GVI = FirstNewGV; // Don't skip the newly produced globals!
return true;
// Otherwise, if the global was not a boolean, we can shrink it to be a
// boolean.
if (Constant *SOVConstant = dyn_cast<Constant>(GS.StoredOnceValue))
- if (GV->getType()->getElementType() != Type::Int1Ty &&
- !GV->getType()->getElementType()->isFloatingPoint() &&
- !isa<VectorType>(GV->getType()->getElementType()) &&
- !GS.HasPHIUser && !GS.isNotSuitableForSRA) {
- DOUT << " *** SHRINKING TO BOOL: " << *GV;
- ShrinkGlobalToBoolean(GV, SOVConstant);
+ if (TryToShrinkGlobalToBoolean(GV, SOVConstant)) {
++NumShrunkToBool;
return true;
}
}
}
+static const ParamAttrsList *StripNest(const ParamAttrsList *Attrs) {
+ if (Attrs) {
+ for (unsigned i = 0, e = Attrs->size(); i != e; ++i) {
+ uint16_t A = Attrs->getParamAttrsAtIndex(i);
+ if (A & ParamAttr::Nest) {
+ 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){
+ Instruction *User = cast<Instruction>(*UI);
+ if (CallInst *CI = dyn_cast<CallInst>(User)) {
+ CI->setParamAttrs(StripNest(CI->getParamAttrs()));
+ } else {
+ InvokeInst *II = cast<InvokeInst>(User);
+ II->setParamAttrs(StripNest(II->getParamAttrs()));
+ }
+ }
+}
+
bool GlobalOpt::OptimizeFunctions(Module &M) {
bool Changed = false;
// Optimize functions.
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;
projects / oota-llvm.git / blobdiff