Diff 397220

llvm/include/llvm/Transforms/Utils/Evaluator.h

Show All 30 Lines
class Function;		class Function;
class TargetLibraryInfo;		class TargetLibraryInfo;

/// This class evaluates LLVM IR, producing the Constant representing each SSA		/// This class evaluates LLVM IR, producing the Constant representing each SSA
/// instruction. Changes to global variables are stored in a mapping that can		/// instruction. Changes to global variables are stored in a mapping that can
/// be iterated over after the evaluation is complete. Once an evaluation call		/// be iterated over after the evaluation is complete. Once an evaluation call
/// fails, the evaluation object should not be reused.		/// fails, the evaluation object should not be reused.
class Evaluator {		class Evaluator {
		class MutableAggregate;

		/// The evaluator represents values either as a Constant*, or as a
		/// MutableAggregate, which allows changing individual aggregate elements
		/// without creating a new interned Constant.
		class MutableValue {
		PointerUnion<Constant , MutableAggregate > Val;
		void clear();
		bool makeMutable();

		public:
		MutableValue(Constant *C) { Val = C; }
		MutableValue(const MutableValue &) = delete;
		MutableValue(MutableValue &&Other) {
		Val = Other.Val;
		Other.Val = nullptr;
		}
		~MutableValue() { clear(); }

		Type *getType() const {
		if (auto C = Val.dyn_cast<Constant >())
		return C->getType();
		return Val.get<MutableAggregate *>()->Ty;
		}

		Constant *toConstant() const {
		if (auto C = Val.dyn_cast<Constant >())
		return C;
		return Val.get<MutableAggregate *>()->toConstant();
		}

		Constant read(Type Ty, APInt Offset, const DataLayout &DL) const;
		bool write(Constant *V, APInt Offset, const DataLayout &DL);
		};

		struct MutableAggregate {
		Type *Ty;
		SmallVector<MutableValue> Elements;

		MutableAggregate(Type *Ty) : Ty(Ty) {}
		Constant *toConstant() const;
		};

public:		public:
Evaluator(const DataLayout &DL, const TargetLibraryInfo *TLI)		Evaluator(const DataLayout &DL, const TargetLibraryInfo *TLI)
: DL(DL), TLI(TLI) {		: DL(DL), TLI(TLI) {
ValueStack.emplace_back();		ValueStack.emplace_back();
}		}

~Evaluator() {		~Evaluator() {
for (auto &Tmp : AllocaTmps)		for (auto &Tmp : AllocaTmps)
// If there are still users of the alloca, the program is doing something		// If there are still users of the alloca, the program is doing something
// silly, e.g. storing the address of the alloca somewhere and using it		// silly, e.g. storing the address of the alloca somewhere and using it
// later. Since this is undefined, we'll just make it be null.		// later. Since this is undefined, we'll just make it be null.
if (!Tmp->use_empty())		if (!Tmp->use_empty())
Tmp->replaceAllUsesWith(Constant::getNullValue(Tmp->getType()));		Tmp->replaceAllUsesWith(Constant::getNullValue(Tmp->getType()));
}		}

/// Evaluate a call to function F, returning true if successful, false if we		/// Evaluate a call to function F, returning true if successful, false if we
/// can't evaluate it. ActualArgs contains the formal arguments for the		/// can't evaluate it. ActualArgs contains the formal arguments for the
/// function.		/// function.
bool EvaluateFunction(Function F, Constant &RetVal,		bool EvaluateFunction(Function F, Constant &RetVal,
const SmallVectorImpl<Constant*> &ActualArgs);		const SmallVectorImpl<Constant*> &ActualArgs);

const DenseMap<Constant , Constant > &getMutatedMemory() const {		DenseMap<GlobalVariable , Constant > getMutatedInitializers() const {
return MutatedMemory;		DenseMap<GlobalVariable , Constant > Result;
		for (auto &Pair : MutatedMemory)
		Result[Pair.first] = Pair.second.toConstant();
		return Result;
}		}

const SmallPtrSetImpl<GlobalVariable *> &getInvariants() const {		const SmallPtrSetImpl<GlobalVariable *> &getInvariants() const {
return Invariants;		return Invariants;
}		}

private:		private:
bool EvaluateBlock(BasicBlock::iterator CurInst, BasicBlock *&NextBB,		bool EvaluateBlock(BasicBlock::iterator CurInst, BasicBlock *&NextBB,
Show All 31 Lines	private:

/// This is used to detect recursion. In pathological situations we could hit		/// This is used to detect recursion. In pathological situations we could hit
/// exponential behavior, but at least there is nothing unbounded.		/// exponential behavior, but at least there is nothing unbounded.
SmallVector<Function*, 4> CallStack;		SmallVector<Function*, 4> CallStack;

/// For each store we execute, we update this map. Loads check this to get		/// For each store we execute, we update this map. Loads check this to get
/// the most up-to-date value. If evaluation is successful, this state is		/// the most up-to-date value. If evaluation is successful, this state is
/// committed to the process.		/// committed to the process.
DenseMap<Constant, Constant> MutatedMemory;		DenseMap<GlobalVariable *, MutableValue> MutatedMemory;

/// To 'execute' an alloca, we create a temporary global variable to represent		/// To 'execute' an alloca, we create a temporary global variable to represent
/// its body. This vector is needed so we can delete the temporary globals		/// its body. This vector is needed so we can delete the temporary globals
/// when we are done.		/// when we are done.
SmallVector<std::unique_ptr<GlobalVariable>, 32> AllocaTmps;		SmallVector<std::unique_ptr<GlobalVariable>, 32> AllocaTmps;

/// These global variables have been marked invariant by the static		/// These global variables have been marked invariant by the static
/// constructor.		/// constructor.
Show All 13 Lines

llvm/lib/Transforms/IPO/GlobalOpt.cpp

Show First 20 Lines • Show All 2,060 Lines • ▼ Show 20 Lines	if (deleteIfDead(GV, NotDiscardableComdats)) {
continue;		continue;
}		}

Changed \|= processGlobal(GV, GetTTI, GetTLI, LookupDomTree);		Changed \|= processGlobal(GV, GetTTI, GetTLI, LookupDomTree);
}		}
return Changed;		return Changed;
}		}

/// Evaluate a piece of a constantexpr store into a global initializer. This
/// returns 'Init' modified to reflect 'Val' stored into it. At this point, the
/// GEP operands of Addr [0, OpNo) have been stepped into.
static Constant EvaluateStoreInto(Constant Init, Constant *Val,
ConstantExpr *Addr, unsigned OpNo) {
// Base case of the recursion.
if (OpNo == Addr->getNumOperands()) {
assert(Val->getType() == Init->getType() && "Type mismatch!");
return Val;
}

SmallVector<Constant*, 32> Elts;
if (StructType *STy = dyn_cast<StructType>(Init->getType())) {
// Break up the constant into its elements.
for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
Elts.push_back(Init->getAggregateElement(i));

// Replace the element that we are supposed to.
ConstantInt *CU = cast<ConstantInt>(Addr->getOperand(OpNo));
unsigned Idx = CU->getZExtValue();
assert(Idx < STy->getNumElements() && "Struct index out of range!");
Elts[Idx] = EvaluateStoreInto(Elts[Idx], Val, Addr, OpNo+1);

// Return the modified struct.
return ConstantStruct::get(STy, Elts);
}

ConstantInt *CI = cast<ConstantInt>(Addr->getOperand(OpNo));
uint64_t NumElts;
if (ArrayType *ATy = dyn_cast<ArrayType>(Init->getType()))
NumElts = ATy->getNumElements();
else
NumElts = cast<FixedVectorType>(Init->getType())->getNumElements();

// Break up the array into elements.
for (uint64_t i = 0, e = NumElts; i != e; ++i)
Elts.push_back(Init->getAggregateElement(i));

assert(CI->getZExtValue() < NumElts);
Elts[CI->getZExtValue()] =
EvaluateStoreInto(Elts[CI->getZExtValue()], Val, Addr, OpNo+1);

if (Init->getType()->isArrayTy())
return ConstantArray::get(cast<ArrayType>(Init->getType()), Elts);
return ConstantVector::get(Elts);
}

/// We have decided that Addr (which satisfies the predicate
/// isSimpleEnoughPointerToCommit) should get Val as its value. Make it happen.
static void CommitValueTo(Constant Val, Constant Addr) {
if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Addr)) {
assert(GV->hasInitializer());
GV->setInitializer(Val);
return;
}

ConstantExpr *CE = cast<ConstantExpr>(Addr);
GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0));
GV->setInitializer(EvaluateStoreInto(GV->getInitializer(), Val, CE, 2));
}

/// Given a map of address -> value, where addresses are expected to be some form
/// of either a global or a constant GEP, set the initializer for the address to
/// be the value. This performs mostly the same function as CommitValueTo()
/// and EvaluateStoreInto() but is optimized to be more efficient for the common
/// case where the set of addresses are GEPs sharing the same underlying global,
/// processing the GEPs in batches rather than individually.
///
/// To give an example, consider the following C++ code adapted from the clang
/// regression tests:
/// struct S {
/// int n = 10;
/// int m = 2 * n;
/// S(int a) : n(a) {}
/// };
///
/// template<typename T>
/// struct U {
/// T *r = &q;
/// T q = 42;
/// U *p = this;
/// };
///
/// U<S> e;
///
/// The global static constructor for 'e' will need to initialize 'r' and 'p' of
/// the outer struct, while also initializing the inner 'q' structs 'n' and 'm'
/// members. This batch algorithm will simply use general CommitValueTo() method
/// to handle the complex nested S struct initialization of 'q', before
/// processing the outermost members in a single batch. Using CommitValueTo() to
/// handle member in the outer struct is inefficient when the struct/array is
/// very large as we end up creating and destroy constant arrays for each
/// initialization.
/// For the above case, we expect the following IR to be generated:
///
/// %struct.U = type { %struct.S, %struct.S, %struct.U }
/// %struct.S = type { i32, i32 }
/// @e = global %struct.U { %struct.S* gep inbounds (%struct.U, %struct.U* @e,
/// i64 0, i32 1),
/// %struct.S { i32 42, i32 84 }, %struct.U* @e }
/// The %struct.S { i32 42, i32 84 } inner initializer is treated as a complex
/// constant expression, while the other two elements of @e are "simple".
static void BatchCommitValueTo(const DenseMap<Constant, Constant> &Mem) {
SmallVector<std::pair<GlobalVariable, Constant>, 32> GVs;
SmallVector<std::pair<ConstantExpr, Constant>, 32> ComplexCEs;
SmallVector<std::pair<ConstantExpr, Constant>, 32> SimpleCEs;
SimpleCEs.reserve(Mem.size());

for (const auto &I : Mem) {
if (auto *GV = dyn_cast<GlobalVariable>(I.first)) {
GVs.push_back(std::make_pair(GV, I.second));
} else {
ConstantExpr *GEP = cast<ConstantExpr>(I.first);
// We don't handle the deeply recursive case using the batch method.
if (GEP->getNumOperands() > 3)
ComplexCEs.push_back(std::make_pair(GEP, I.second));
else
SimpleCEs.push_back(std::make_pair(GEP, I.second));
}
}

// The algorithm below doesn't handle cases like nested structs, so use the
// slower fully general method if we have to.
for (auto ComplexCE : ComplexCEs)
CommitValueTo(ComplexCE.second, ComplexCE.first);

for (auto GVPair : GVs) {
assert(GVPair.first->hasInitializer());
GVPair.first->setInitializer(GVPair.second);
}

if (SimpleCEs.empty())
return;

// We cache a single global's initializer elements in the case where the
// subsequent address/val pair uses the same one. This avoids throwing away and
// rebuilding the constant struct/vector/array just because one element is
// modified at a time.
SmallVector<Constant *, 32> Elts;
Elts.reserve(SimpleCEs.size());
GlobalVariable *CurrentGV = nullptr;

auto commitAndSetupCache = [&](GlobalVariable *GV, bool Update) {
Constant *Init = GV->getInitializer();
Type *Ty = Init->getType();
if (Update) {
if (CurrentGV) {
assert(CurrentGV && "Expected a GV to commit to!");
Type *CurrentInitTy = CurrentGV->getInitializer()->getType();
// We have a valid cache that needs to be committed.
if (StructType *STy = dyn_cast<StructType>(CurrentInitTy))
CurrentGV->setInitializer(ConstantStruct::get(STy, Elts));
else if (ArrayType *ArrTy = dyn_cast<ArrayType>(CurrentInitTy))
CurrentGV->setInitializer(ConstantArray::get(ArrTy, Elts));
else
CurrentGV->setInitializer(ConstantVector::get(Elts));
}
if (CurrentGV == GV)
return;
// Need to clear and set up cache for new initializer.
CurrentGV = GV;
Elts.clear();
unsigned NumElts;
if (auto *STy = dyn_cast<StructType>(Ty))
NumElts = STy->getNumElements();
else if (auto *ATy = dyn_cast<ArrayType>(Ty))
NumElts = ATy->getNumElements();
else
NumElts = cast<FixedVectorType>(Ty)->getNumElements();
for (unsigned i = 0, e = NumElts; i != e; ++i)
Elts.push_back(Init->getAggregateElement(i));
}
};

for (auto CEPair : SimpleCEs) {
ConstantExpr *GEP = CEPair.first;
Constant *Val = CEPair.second;

GlobalVariable *GV = cast<GlobalVariable>(GEP->getOperand(0));
commitAndSetupCache(GV, GV != CurrentGV);
ConstantInt *CI = cast<ConstantInt>(GEP->getOperand(2));
Elts[CI->getZExtValue()] = Val;
}
// The last initializer in the list needs to be committed, others
// will be committed on a new initializer being processed.
commitAndSetupCache(CurrentGV, true);
}

/// Evaluate static constructors in the function, if we can. Return true if we		/// Evaluate static constructors in the function, if we can. Return true if we
/// can, false otherwise.		/// can, false otherwise.
static bool EvaluateStaticConstructor(Function *F, const DataLayout &DL,		static bool EvaluateStaticConstructor(Function *F, const DataLayout &DL,
TargetLibraryInfo *TLI) {		TargetLibraryInfo *TLI) {
// Call the function.		// Call the function.
Evaluator Eval(DL, TLI);		Evaluator Eval(DL, TLI);
Constant *RetValDummy;		Constant *RetValDummy;
bool EvalSuccess = Eval.EvaluateFunction(F, RetValDummy,		bool EvalSuccess = Eval.EvaluateFunction(F, RetValDummy,
SmallVector<Constant*, 0>());		SmallVector<Constant*, 0>());

if (EvalSuccess) {		if (EvalSuccess) {
++NumCtorsEvaluated;		++NumCtorsEvaluated;

// We succeeded at evaluation: commit the result.		// We succeeded at evaluation: commit the result.
		auto NewInitializers = Eval.getMutatedInitializers();
LLVM_DEBUG(dbgs() << "FULLY EVALUATED GLOBAL CTOR FUNCTION '"		LLVM_DEBUG(dbgs() << "FULLY EVALUATED GLOBAL CTOR FUNCTION '"
<< F->getName() << "' to "		<< F->getName() << "' to " << NewInitializers.size()
<< Eval.getMutatedMemory().size() << " stores.\n");		<< " stores.\n");
BatchCommitValueTo(Eval.getMutatedMemory());		for (const auto &Pair : NewInitializers)
		Pair.first->setInitializer(Pair.second);
for (GlobalVariable *GV : Eval.getInvariants())		for (GlobalVariable *GV : Eval.getInvariants())
GV->setConstant(true);		GV->setConstant(true);
}		}

return EvalSuccess;		return EvalSuccess;
}		}

static int compareNames(Constant const A, Constant const B) {		static int compareNames(Constant const A, Constant const B) {
▲ Show 20 Lines • Show All 455 Lines • Show Last 20 Lines

llvm/lib/Transforms/Utils/Evaluator.cpp

Show First 20 Lines • Show All 116 Lines • ▼ Show 20 Lines	isSimpleEnoughValueToCommit(Constant *C,
const DataLayout &DL) {		const DataLayout &DL) {
// If we already checked this constant, we win.		// If we already checked this constant, we win.
if (!SimpleConstants.insert(C).second)		if (!SimpleConstants.insert(C).second)
return true;		return true;
// Check the constant.		// Check the constant.
return isSimpleEnoughValueToCommitHelper(C, SimpleConstants, DL);		return isSimpleEnoughValueToCommitHelper(C, SimpleConstants, DL);
}		}

/// Return true if this constant is simple enough for us to understand. In		void Evaluator::MutableValue::clear() {
/// particular, if it is a cast to anything other than from one pointer type to		if (auto Agg = Val.dyn_cast<MutableAggregate >())
/// another pointer type, we punt. We basically just support direct accesses to		delete Agg;
/// globals and GEP's of globals. This should be kept up to date with		Val = nullptr;
/// CommitValueTo.
static bool isSimpleEnoughPointerToCommit(Constant *C, const DataLayout &DL) {
if (GlobalVariable *GV = dyn_cast<GlobalVariable>(C))
// Do not allow weak/*_odr/linkonce linkage or external globals.
return GV->hasUniqueInitializer();

if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
// Handle a constantexpr gep.
if (CE->getOpcode() == Instruction::GetElementPtr &&
isa<GlobalVariable>(CE->getOperand(0)) &&
cast<GEPOperator>(CE)->isInBounds()) {
GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0));
// Do not allow weak/*_odr/linkonce/dllimport/dllexport linkage or
// external globals.
if (!GV->hasUniqueInitializer())
return false;

// The first index must be zero.
ConstantInt CI = dyn_cast<ConstantInt>(std::next(CE->op_begin()));
if (!CI \|\| !CI->isZero()) return false;

// The remaining indices must be compile-time known integers within the
// notional bounds of the corresponding static array types.
if (!CE->isGEPWithNoNotionalOverIndexing())
return false;

return ConstantFoldLoadThroughGEPConstantExpr(
GV->getInitializer(), CE,
cast<GEPOperator>(CE)->getResultElementType(), DL);
} else if (CE->getOpcode() == Instruction::BitCast &&
isa<GlobalVariable>(CE->getOperand(0))) {
// A constantexpr bitcast from a pointer to another pointer is a no-op,
// and we know how to evaluate it by moving the bitcast from the pointer
// operand to the value operand.
// Do not allow weak/*_odr/linkonce/dllimport/dllexport linkage or
// external globals.
return cast<GlobalVariable>(CE->getOperand(0))->hasUniqueInitializer();
}		}

		Constant Evaluator::MutableValue::read(Type Ty, APInt Offset,
		const DataLayout &DL) const {
		TypeSize TySize = DL.getTypeStoreSize(Ty);
		const MutableValue *V = this;
		while (const auto Agg = V->Val.dyn_cast<MutableAggregate >()) {
		Type *AggTy = Agg->Ty;
		Optional<APInt> Index = DL.getGEPIndexForOffset(AggTy, Offset);
		if (!Index \|\| Index->ugt(Agg->Elements.size()) \|\|
		!TypeSize::isKnownLE(TySize, DL.getTypeStoreSize(AggTy)))
		return nullptr;

		V = &Agg->Elements[Index->getZExtValue()];
		}

		return ConstantFoldLoadFromConst(V->Val.get<Constant *>(), Ty, Offset, DL);
}		}

		bool Evaluator::MutableValue::makeMutable() {
		Constant C = Val.get<Constant >();
		Type *Ty = C->getType();
		unsigned NumElements;
		if (auto *VT = dyn_cast<FixedVectorType>(Ty)) {
		NumElements = VT->getNumElements();
		} else if (auto *AT = dyn_cast<ArrayType>(Ty))
		NumElements = AT->getNumElements();
		else if (auto *ST = dyn_cast<StructType>(Ty))
		NumElements = ST->getNumElements();
		else
return false;		return false;

		MutableAggregate *MA = new MutableAggregate(Ty);
		MA->Elements.reserve(NumElements);
		for (unsigned I = 0; I < NumElements; ++I)
		MA->Elements.push_back(C->getAggregateElement(I));
		Val = MA;
		return true;
}		}

/// Apply \p TryLoad to Ptr. If this returns \p nullptr, introspect the		bool Evaluator::MutableValue::write(Constant *V, APInt Offset,
/// pointer's type and walk down through the initial elements to obtain		const DataLayout &DL) {
/// additional pointers to try. Returns the first non-null return value from		Type *Ty = V->getType();
/// \p TryLoad, or \p nullptr if the type can't be introspected further.		TypeSize TySize = DL.getTypeStoreSize(Ty);
static Constant *		MutableValue *MV = this;
evaluateBitcastFromPtr(Constant *Ptr, const DataLayout &DL,		while (Offset != 0 \|\|
const TargetLibraryInfo *TLI,		!CastInst::isBitOrNoopPointerCastable(Ty, MV->getType(), DL)) {
std::function<Constant (Constant )> TryLoad) {		if (MV->Val.is<Constant *>() && !MV->makeMutable())
Constant *Val;		return false;
while (!(Val = TryLoad(Ptr))) {
// If Ty is a non-opaque struct, we can convert the pointer to the struct		MutableAggregate Agg = MV->Val.get<MutableAggregate >();
// into a pointer to its first member.		Type *AggTy = Agg->Ty;
// FIXME: This could be extended to support arrays as well.		Optional<APInt> Index = DL.getGEPIndexForOffset(AggTy, Offset);
Type *Ty = cast<PointerType>(Ptr->getType())->getElementType();		if (!Index \|\| Index->ugt(Agg->Elements.size()) \|\|
if (!isa<StructType>(Ty) \|\| cast<StructType>(Ty)->isOpaque())		!TypeSize::isKnownLE(TySize, DL.getTypeStoreSize(AggTy)))
break;		return false;

IntegerType *IdxTy = IntegerType::get(Ty->getContext(), 32);		MV = &Agg->Elements[Index->getZExtValue()];
Constant *IdxZero = ConstantInt::get(IdxTy, 0, false);		}
Constant *const IdxList[] = {IdxZero, IdxZero};
		Type *MVType = MV->getType();
Ptr = ConstantExpr::getGetElementPtr(Ty, Ptr, IdxList);		MV->clear();
		jroelofsUnsubmitted Done Reply Inline Actions The lifetime of `MV` (or even possibly `this`) ends here, and I think that makes it UB to write to `Val` below. Maybe the dtor's body needs to be outlined & called here explicitly instead of the dtor itself? jroelofs: The lifetime of `MV` (or even possibly `this`) ends here, and I think that makes it UB to write…
		nikicAuthorUnsubmitted Done Reply Inline Actions Not sure what the exact rules here are, but it was definitely dubious... I've added a clear() method now, which is called here and in the dtor. nikic: Not sure what the exact rules here are, but it was definitely dubious... I've added a clear()…
Ptr = ConstantFoldConstant(Ptr, DL, TLI);		if (Ty->isIntegerTy() && MVType->isPointerTy())
}		MV->Val = ConstantExpr::getIntToPtr(V, MVType);
return Val;		else if (Ty->isPointerTy() && MVType->isIntegerTy())
}		MV->Val = ConstantExpr::getPtrToInt(V, MVType);
		else
static Constant getInitializer(Constant C) {		MV->Val = ConstantExpr::getBitCast(V, MVType);
auto *GV = dyn_cast<GlobalVariable>(C);		return true;
return GV && GV->hasDefinitiveInitializer() ? GV->getInitializer() : nullptr;		}

		Constant *Evaluator::MutableAggregate::toConstant() const {
		SmallVector<Constant *, 32> Consts;
		for (const MutableValue &MV : Elements)
		Consts.push_back(MV.toConstant());

		if (auto *ST = dyn_cast<StructType>(Ty))
		return ConstantStruct::get(ST, Consts);
		if (auto *AT = dyn_cast<ArrayType>(Ty))
		return ConstantArray::get(AT, Consts);
		assert(isa<FixedVectorType>(Ty) && "Must be vector");
		return ConstantVector::get(Consts);
}		}

/// Return the value that would be computed by a load from P after the stores		/// Return the value that would be computed by a load from P after the stores
/// reflected by 'memory' have been performed. If we can't decide, return null.		/// reflected by 'memory' have been performed. If we can't decide, return null.
Constant Evaluator::ComputeLoadResult(Constant P, Type *Ty) {		Constant Evaluator::ComputeLoadResult(Constant P, Type *Ty) {
// If this memory location has been recently stored, use the stored value: it		APInt Offset(DL.getIndexTypeSizeInBits(P->getType()), 0);
// is the most up-to-date.		P = cast<Constant>(P->stripAndAccumulateConstantOffsets(
auto TryFindMemLoc = [this](Constant *Ptr) {		DL, Offset, /* AllowNonInbounds */ true));
return MutatedMemory.lookup(Ptr);		Offset = Offset.sextOrTrunc(DL.getIndexTypeSizeInBits(P->getType()));
};		auto *GV = dyn_cast<GlobalVariable>(P);
		if (!GV)
if (Constant *Val = TryFindMemLoc(P))
return Val;

// Access it.
if (GlobalVariable *GV = dyn_cast<GlobalVariable>(P)) {
if (GV->hasDefinitiveInitializer())
return GV->getInitializer();
return nullptr;		return nullptr;
}

if (ConstantExpr *CE = dyn_cast<ConstantExpr>(P)) {		auto It = MutatedMemory.find(GV);
switch (CE->getOpcode()) {		if (It != MutatedMemory.end())
// Handle a constantexpr getelementptr.		return It->second.read(Ty, Offset, DL);
case Instruction::GetElementPtr:
if (auto *I = getInitializer(CE->getOperand(0)))
return ConstantFoldLoadThroughGEPConstantExpr(I, CE, Ty, DL);
break;
// Handle a constantexpr bitcast.
case Instruction::BitCast:
// We're evaluating a load through a pointer that was bitcast to a
// different type. See if the "from" pointer has recently been stored.
// If it hasn't, we may still be able to find a stored pointer by
// introspecting the type.
Constant *Val =
evaluateBitcastFromPtr(CE->getOperand(0), DL, TLI, TryFindMemLoc);
if (!Val)
Val = getInitializer(CE->getOperand(0));
if (Val)
return ConstantFoldLoadThroughBitcast(
Val, P->getType()->getPointerElementType(), DL);
break;
}
}

return nullptr; // don't know how to evaluate.		if (!GV->hasDefinitiveInitializer())
		return nullptr;
		return ConstantFoldLoadFromConst(GV->getInitializer(), Ty, Offset, DL);
}		}

static Function getFunction(Constant C) {		static Function getFunction(Constant C) {
if (auto *Fn = dyn_cast<Function>(C))		if (auto *Fn = dyn_cast<Function>(C))
return Fn;		return Fn;

if (auto *Alias = dyn_cast<GlobalAlias>(C))		if (auto *Alias = dyn_cast<GlobalAlias>(C))
if (auto *Fn = dyn_cast<Function>(Alias->getAliasee()))		if (auto *Fn = dyn_cast<Function>(Alias->getAliasee()))
▲ Show 20 Lines • Show All 76 Lines • ▼ Show 20 Lines	if (StoreInst *SI = dyn_cast<StoreInst>(CurInst)) {
}		}
Constant *Ptr = getVal(SI->getOperand(1));		Constant *Ptr = getVal(SI->getOperand(1));
Constant *FoldedPtr = ConstantFoldConstant(Ptr, DL, TLI);		Constant *FoldedPtr = ConstantFoldConstant(Ptr, DL, TLI);
if (Ptr != FoldedPtr) {		if (Ptr != FoldedPtr) {
LLVM_DEBUG(dbgs() << "Folding constant ptr expression: " << *Ptr);		LLVM_DEBUG(dbgs() << "Folding constant ptr expression: " << *Ptr);
Ptr = FoldedPtr;		Ptr = FoldedPtr;
LLVM_DEBUG(dbgs() << "; To: " << *Ptr << "\n");		LLVM_DEBUG(dbgs() << "; To: " << *Ptr << "\n");
}		}
// Conservatively, avoid aggregate types. This is because we don't
// want to worry about them partially overlapping other stores.		APInt Offset(DL.getIndexTypeSizeInBits(Ptr->getType()), 0);
if (!SI->getValueOperand()->getType()->isSingleValueType() \|\|		Ptr = cast<Constant>(Ptr->stripAndAccumulateConstantOffsets(
!isSimpleEnoughPointerToCommit(Ptr, DL)) {		DL, Offset, /* AllowNonInbounds */ true));
// If this is too complex for us to commit, reject it.		Offset = Offset.sextOrTrunc(DL.getIndexTypeSizeInBits(Ptr->getType()));
LLVM_DEBUG(		auto *GV = dyn_cast<GlobalVariable>(Ptr);
dbgs() << "Pointer is too complex for us to evaluate store.");		if (!GV \|\| !GV->hasUniqueInitializer()) {
		LLVM_DEBUG(dbgs() << "Store is not to global with unique initializer: "
		<< *Ptr << "\n");
return false;		return false;
}		}

Constant *Val = getVal(SI->getOperand(0));

// If this might be too difficult for the backend to handle (e.g. the addr		// If this might be too difficult for the backend to handle (e.g. the addr
// of one global variable divided by another) then we can't commit it.		// of one global variable divided by another) then we can't commit it.
		Constant *Val = getVal(SI->getOperand(0));
if (!isSimpleEnoughValueToCommit(Val, SimpleConstants, DL)) {		if (!isSimpleEnoughValueToCommit(Val, SimpleConstants, DL)) {
LLVM_DEBUG(dbgs() << "Store value is too complex to evaluate store. "		LLVM_DEBUG(dbgs() << "Store value is too complex to evaluate store. "
<< *Val << "\n");		<< *Val << "\n");
return false;		return false;
}		}

if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr)) {		auto Res = MutatedMemory.try_emplace(GV, GV->getInitializer());
if (CE->getOpcode() == Instruction::BitCast) {		if (!Res.first->second.write(Val, Offset, DL))
LLVM_DEBUG(dbgs()
<< "Attempting to resolve bitcast on constant ptr.\n");
// If we're evaluating a store through a bitcast, then we need
// to pull the bitcast off the pointer type and push it onto the
// stored value. In order to push the bitcast onto the stored value,
// a bitcast from the pointer's element type to Val's type must be
// legal. If it's not, we can try introspecting the type to find a
// legal conversion.

auto TryCastValTy = [&](Constant P) -> Constant {
// The conversion is illegal if the store is wider than the
// pointee proposed by `evaluateBitcastFromPtr`, since that would
// drop stores to other struct elements when the caller attempts to
// look through a struct's 0th element.
Type *NewTy = cast<PointerType>(P->getType())->getElementType();
Type *STy = Val->getType();
if (DL.getTypeSizeInBits(NewTy) < DL.getTypeSizeInBits(STy))
return nullptr;

if (Constant *FV = ConstantFoldLoadThroughBitcast(Val, NewTy, DL)) {
Ptr = P;
return FV;
}
return nullptr;
};

Constant *NewVal =
evaluateBitcastFromPtr(CE->getOperand(0), DL, TLI, TryCastValTy);
if (!NewVal) {
LLVM_DEBUG(dbgs() << "Failed to bitcast constant ptr, can not "
"evaluate.\n");
return false;		return false;
}

Val = NewVal;
LLVM_DEBUG(dbgs() << "Evaluated bitcast: " << *Val << "\n");
}
}

MutatedMemory[Ptr] = Val;
} else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(CurInst)) {		} else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(CurInst)) {
InstResult = ConstantExpr::get(BO->getOpcode(),		InstResult = ConstantExpr::get(BO->getOpcode(),
getVal(BO->getOperand(0)),		getVal(BO->getOperand(0)),
getVal(BO->getOperand(1)));		getVal(BO->getOperand(1)));
LLVM_DEBUG(dbgs() << "Found a BinaryOperator! Simplifying: "		LLVM_DEBUG(dbgs() << "Found a BinaryOperator! Simplifying: "
<< *InstResult << "\n");		<< *InstResult << "\n");
} else if (CmpInst *CI = dyn_cast<CmpInst>(CurInst)) {		} else if (CmpInst *CI = dyn_cast<CmpInst>(CurInst)) {
InstResult = ConstantExpr::getCompare(CI->getPredicate(),		InstResult = ConstantExpr::getCompare(CI->getPredicate(),
▲ Show 20 Lines • Show All 358 Lines • Show Last 20 Lines

llvm/test/Transforms/GlobalOpt/pr51879.ll

	; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --check-globals			; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --check-globals
	; RUN: opt -S -globalopt < %s \| FileCheck %s			; RUN: opt -S -globalopt < %s \| FileCheck %s

	; TODO: This currently computes an incorrect initializer value.

	%type = type { { i8** } }			%type = type { { i8** } }

	@g = internal global %type zeroinitializer			@g = internal global %type zeroinitializer
	@g2 = external global i8*			@g2 = external global i8*

	@llvm.global_ctors = appending global [1 x { i32, void (), i8 }] [{ i32, void (), i8 } { i32 65535, void ()* @ctor, i8* null }]			@llvm.global_ctors = appending global [1 x { i32, void (), i8 }] [{ i32, void (), i8 } { i32 65535, void ()* @ctor, i8* null }]

	;.			;.
	; CHECK: @[[G:[a-zA-Z0-9_$"\\.-]+]] = internal global [[TYPE:%.*]] zeroinitializer			; CHECK: @[[G:[a-zA-Z0-9_$"\\.-]+]] = internal global [[TYPE:%.]] { { i8* } { i8** @g2 } }
				; CHECK: @[[G2:[a-zA-Z0-9_$"\\.-]+]] = external global i8*
	; CHECK: @[[LLVM_GLOBAL_CTORS:[a-zA-Z0-9_$"\\.-]+]] = appending global [0 x { i32, void (), i8 }] zeroinitializer			; CHECK: @[[LLVM_GLOBAL_CTORS:[a-zA-Z0-9_$"\\.-]+]] = appending global [0 x { i32, void (), i8 }] zeroinitializer
	;.			;.
	define internal void @ctor() {			define internal void @ctor() {
	store i64 0, i64* bitcast (%type* @g to i64*), align 8			store i64 0, i64* bitcast (%type* @g to i64*), align 8
	store i8 @g2, i8* getelementptr inbounds (%type, %type* @g, i64 0, i32 0, i32 0), align 8			store i8 @g2, i8* getelementptr inbounds (%type, %type* @g, i64 0, i32 0, i32 0), align 8
	ret void			ret void
	}			}

	define %type* @test() {			define %type* @test() {
	; CHECK-LABEL: @test(			; CHECK-LABEL: @test(
	; CHECK-NEXT: ret %type* @g			; CHECK-NEXT: ret %type* @g
	;			;
	ret %type* @g			ret %type* @g
	}			}

This is an archive of the discontinued LLVM Phabricator instance.

[GlobalOpt][Evaluator] Rewrite global ctor evaluation (fixes PR51879)
ClosedPublic

Details

Diff Detail

Event Timeline

Revision Contents

Diff 397220

llvm/include/llvm/Transforms/Utils/Evaluator.h

llvm/lib/Transforms/IPO/GlobalOpt.cpp

llvm/lib/Transforms/Utils/Evaluator.cpp

llvm/test/Transforms/GlobalOpt/pr51879.ll

This is an archive of the discontinued LLVM Phabricator instance.

[GlobalOpt][Evaluator] Rewrite global ctor evaluation (fixes PR51879)ClosedPublic

Details

Diff Detail

Event Timeline

Revision Contents

Diff 397220

llvm/include/llvm/Transforms/Utils/Evaluator.h

llvm/lib/Transforms/IPO/GlobalOpt.cpp

llvm/lib/Transforms/Utils/Evaluator.cpp

llvm/test/Transforms/GlobalOpt/pr51879.ll

[GlobalOpt][Evaluator] Rewrite global ctor evaluation (fixes PR51879)
ClosedPublic