#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/SSAUpdater.h"
-#include <cstdio>
using namespace llvm;
STATISTIC(NumGVNInstr, "Number of instructions deleted");
static bool isEqual(const Expression &LHS, const Expression &RHS) {
return LHS == RHS;
}
- static bool isPod() { return true; }
};
+
+template <>
+struct isPodLike<Expression> { static const bool value = true; };
+
}
//===----------------------------------------------------------------------===//
// Check to see if we have a single dominating call instruction that is
// identical to C.
for (unsigned i = 0, e = deps.size(); i != e; ++i) {
- const MemoryDependenceAnalysis::NonLocalDepEntry *I = &deps[i];
+ const NonLocalDepEntry *I = &deps[i];
// Ignore non-local dependencies.
- if (I->second.isNonLocal())
+ if (I->getResult().isNonLocal())
continue;
// We don't handle non-depedencies. If we already have a call, reject
// instruction dependencies.
- if (I->second.isClobber() || cdep != 0) {
+ if (I->getResult().isClobber() || cdep != 0) {
cdep = 0;
break;
}
- CallInst *NonLocalDepCall = dyn_cast<CallInst>(I->second.getInst());
+ CallInst *NonLocalDepCall = dyn_cast<CallInst>(I->getResult().getInst());
// FIXME: All duplicated with non-local case.
- if (NonLocalDepCall && DT->properlyDominates(I->first, C->getParent())){
+ if (NonLocalDepCall && DT->properlyDominates(I->getBB(), C->getParent())){
cdep = NonLocalDepCall;
continue;
}
"Global Value Numbering");
void GVN::dump(DenseMap<uint32_t, Value*>& d) {
- printf("{\n");
+ errs() << "{\n";
for (DenseMap<uint32_t, Value*>::iterator I = d.begin(),
E = d.end(); I != E; ++I) {
- printf("%d\n", I->first);
+ errs() << I->first << "\n";
I->second->dump();
}
- printf("}\n");
+ errs() << "}\n";
}
static bool isSafeReplacement(PHINode* p, Instruction *inst) {
/// Check this case to see if there is anything more we can do before we give
/// up. This returns -1 if we have to give up, or a byte number in the stored
/// value of the piece that feeds the load.
-static int AnalyzeLoadFromClobberingWrite(LoadInst *L, Value *WritePtr,
+static int AnalyzeLoadFromClobberingWrite(const Type *LoadTy, Value *LoadPtr,
+ Value *WritePtr,
uint64_t WriteSizeInBits,
const TargetData &TD) {
// If the loaded or stored value is an first class array or struct, don't try
// to transform them. We need to be able to bitcast to integer.
- if (isa<StructType>(L->getType()) || isa<ArrayType>(L->getType()))
+ if (isa<StructType>(LoadTy) || isa<ArrayType>(LoadTy))
return -1;
int64_t StoreOffset = 0, LoadOffset = 0;
Value *StoreBase = GetBaseWithConstantOffset(WritePtr, StoreOffset, TD);
Value *LoadBase =
- GetBaseWithConstantOffset(L->getPointerOperand(), LoadOffset, TD);
+ GetBaseWithConstantOffset(LoadPtr, LoadOffset, TD);
if (StoreBase != LoadBase)
return -1;
<< "Base = " << *StoreBase << "\n"
<< "Store Ptr = " << *WritePtr << "\n"
<< "Store Offs = " << StoreOffset << "\n"
- << "Load Ptr = " << *L->getPointerOperand() << "\n"
- << "Load Offs = " << LoadOffset << " - " << *L << "\n\n";
- errs() << "'" << L->getParent()->getParent()->getName() << "'"
- << *L->getParent();
+ << "Load Ptr = " << *LoadPtr << "\n";
+ abort();
#endif
return -1;
}
// must have gotten confused.
// FIXME: Investigate cases where this bails out, e.g. rdar://7238614. Then
// remove this check, as it is duplicated with what we have below.
- uint64_t LoadSize = TD.getTypeSizeInBits(L->getType());
+ uint64_t LoadSize = TD.getTypeSizeInBits(LoadTy);
if ((WriteSizeInBits & 7) | (LoadSize & 7))
return -1;
<< "Base = " << *StoreBase << "\n"
<< "Store Ptr = " << *WritePtr << "\n"
<< "Store Offs = " << StoreOffset << "\n"
- << "Load Ptr = " << *L->getPointerOperand() << "\n"
- << "Load Offs = " << LoadOffset << " - " << *L << "\n\n";
- errs() << "'" << L->getParent()->getParent()->getName() << "'"
- << *L->getParent();
+ << "Load Ptr = " << *LoadPtr << "\n";
+ abort();
#endif
return -1;
}
/// AnalyzeLoadFromClobberingStore - This function is called when we have a
/// memdep query of a load that ends up being a clobbering store.
-static int AnalyzeLoadFromClobberingStore(LoadInst *L, StoreInst *DepSI,
+static int AnalyzeLoadFromClobberingStore(const Type *LoadTy, Value *LoadPtr,
+ StoreInst *DepSI,
const TargetData &TD) {
// Cannot handle reading from store of first-class aggregate yet.
if (isa<StructType>(DepSI->getOperand(0)->getType()) ||
return -1;
Value *StorePtr = DepSI->getPointerOperand();
- uint64_t StoreSize = TD.getTypeSizeInBits(StorePtr->getType());
- return AnalyzeLoadFromClobberingWrite(L, StorePtr, StoreSize, TD);
+ uint64_t StoreSize = TD.getTypeSizeInBits(DepSI->getOperand(0)->getType());
+ return AnalyzeLoadFromClobberingWrite(LoadTy, LoadPtr,
+ StorePtr, StoreSize, TD);
}
-static int AnalyzeLoadFromClobberingMemInst(LoadInst *L, MemIntrinsic *MI,
+static int AnalyzeLoadFromClobberingMemInst(const Type *LoadTy, Value *LoadPtr,
+ MemIntrinsic *MI,
const TargetData &TD) {
// If the mem operation is a non-constant size, we can't handle it.
ConstantInt *SizeCst = dyn_cast<ConstantInt>(MI->getLength());
// If this is memset, we just need to see if the offset is valid in the size
// of the memset..
if (MI->getIntrinsicID() == Intrinsic::memset)
- return AnalyzeLoadFromClobberingWrite(L, MI->getDest(), MemSizeInBits, TD);
+ return AnalyzeLoadFromClobberingWrite(LoadTy, LoadPtr, MI->getDest(),
+ MemSizeInBits, TD);
// If we have a memcpy/memmove, the only case we can handle is if this is a
// copy from constant memory. In that case, we can read directly from the
if (GV == 0 || !GV->isConstant()) return -1;
// See if the access is within the bounds of the transfer.
- int Offset =
- AnalyzeLoadFromClobberingWrite(L, MI->getDest(), MemSizeInBits, TD);
+ int Offset = AnalyzeLoadFromClobberingWrite(LoadTy, LoadPtr,
+ MI->getDest(), MemSizeInBits, TD);
if (Offset == -1)
return Offset;
Constant *OffsetCst =
ConstantInt::get(Type::getInt64Ty(Src->getContext()), (unsigned)Offset);
Src = ConstantExpr::getGetElementPtr(Src, &OffsetCst, 1);
- Src = ConstantExpr::getBitCast(Src, PointerType::getUnqual(L->getType()));
+ Src = ConstantExpr::getBitCast(Src, PointerType::getUnqual(LoadTy));
if (ConstantFoldLoadFromConstPtr(Src, &TD))
return Offset;
return -1;
uint64_t StoreSize = TD.getTypeSizeInBits(SrcVal->getType())/8;
uint64_t LoadSize = TD.getTypeSizeInBits(LoadTy)/8;
+ IRBuilder<> Builder(InsertPt->getParent(), InsertPt);
// Compute which bits of the stored value are being used by the load. Convert
// to an integer type to start with.
if (isa<PointerType>(SrcVal->getType()))
- SrcVal = new PtrToIntInst(SrcVal, TD.getIntPtrType(Ctx), "tmp", InsertPt);
+ SrcVal = Builder.CreatePtrToInt(SrcVal, TD.getIntPtrType(Ctx), "tmp");
if (!isa<IntegerType>(SrcVal->getType()))
- SrcVal = new BitCastInst(SrcVal, IntegerType::get(Ctx, StoreSize*8),
- "tmp", InsertPt);
+ SrcVal = Builder.CreateBitCast(SrcVal, IntegerType::get(Ctx, StoreSize*8),
+ "tmp");
// Shift the bits to the least significant depending on endianness.
unsigned ShiftAmt;
ShiftAmt = (StoreSize-LoadSize-Offset)*8;
if (ShiftAmt)
- SrcVal = BinaryOperator::CreateLShr(SrcVal,
- ConstantInt::get(SrcVal->getType(), ShiftAmt), "tmp", InsertPt);
+ SrcVal = Builder.CreateLShr(SrcVal, ShiftAmt, "tmp");
if (LoadSize != StoreSize)
- SrcVal = new TruncInst(SrcVal, IntegerType::get(Ctx, LoadSize*8),
- "tmp", InsertPt);
+ SrcVal = Builder.CreateTrunc(SrcVal, IntegerType::get(Ctx, LoadSize*8),
+ "tmp");
return CoerceAvailableValueToLoadType(SrcVal, LoadTy, InsertPt, TD);
}
bool GVN::processNonLocalLoad(LoadInst *LI,
SmallVectorImpl<Instruction*> &toErase) {
// Find the non-local dependencies of the load.
- SmallVector<MemoryDependenceAnalysis::NonLocalDepEntry, 64> Deps;
+ SmallVector<NonLocalDepEntry, 64> Deps;
MD->getNonLocalPointerDependency(LI->getOperand(0), true, LI->getParent(),
Deps);
//DEBUG(errs() << "INVESTIGATING NONLOCAL LOAD: "
// If we had a phi translation failure, we'll have a single entry which is a
// clobber in the current block. Reject this early.
- if (Deps.size() == 1 && Deps[0].second.isClobber()) {
+ if (Deps.size() == 1 && Deps[0].getResult().isClobber()) {
DEBUG(
errs() << "GVN: non-local load ";
WriteAsOperand(errs(), LI);
- errs() << " is clobbered by " << *Deps[0].second.getInst() << '\n';
+ errs() << " is clobbered by " << *Deps[0].getResult().getInst() << '\n';
);
return false;
}
const TargetData *TD = 0;
for (unsigned i = 0, e = Deps.size(); i != e; ++i) {
- BasicBlock *DepBB = Deps[i].first;
- MemDepResult DepInfo = Deps[i].second;
+ BasicBlock *DepBB = Deps[i].getBB();
+ MemDepResult DepInfo = Deps[i].getResult();
if (DepInfo.isClobber()) {
+ // The address being loaded in this non-local block may not be the same as
+ // the pointer operand of the load if PHI translation occurs. Make sure
+ // to consider the right address.
+ Value *Address = Deps[i].getAddress();
+
// If the dependence is to a store that writes to a superset of the bits
// read by the load, we can extract the bits we need for the load from the
// stored value.
if (StoreInst *DepSI = dyn_cast<StoreInst>(DepInfo.getInst())) {
if (TD == 0)
TD = getAnalysisIfAvailable<TargetData>();
- if (TD) {
- int Offset = AnalyzeLoadFromClobberingStore(LI, DepSI, *TD);
+ if (TD && Address) {
+ int Offset = AnalyzeLoadFromClobberingStore(LI->getType(), Address,
+ DepSI, *TD);
if (Offset != -1) {
ValuesPerBlock.push_back(AvailableValueInBlock::get(DepBB,
DepSI->getOperand(0),
if (MemIntrinsic *DepMI = dyn_cast<MemIntrinsic>(DepInfo.getInst())) {
if (TD == 0)
TD = getAnalysisIfAvailable<TargetData>();
- if (TD) {
- int Offset = AnalyzeLoadFromClobberingMemInst(LI, DepMI, *TD);
+ if (TD && Address) {
+ int Offset = AnalyzeLoadFromClobberingMemInst(LI->getType(), Address,
+ DepMI, *TD);
if (Offset != -1) {
ValuesPerBlock.push_back(AvailableValueInBlock::getMI(DepBB, DepMI,
Offset));
Value *AvailVal = 0;
if (StoreInst *DepSI = dyn_cast<StoreInst>(Dep.getInst()))
if (const TargetData *TD = getAnalysisIfAvailable<TargetData>()) {
- int Offset = AnalyzeLoadFromClobberingStore(L, DepSI, *TD);
+ int Offset = AnalyzeLoadFromClobberingStore(L->getType(),
+ L->getPointerOperand(),
+ DepSI, *TD);
if (Offset != -1)
AvailVal = GetStoreValueForLoad(DepSI->getOperand(0), Offset,
L->getType(), L, *TD);
// a value on from it.
if (MemIntrinsic *DepMI = dyn_cast<MemIntrinsic>(Dep.getInst())) {
if (const TargetData *TD = getAnalysisIfAvailable<TargetData>()) {
- int Offset = AnalyzeLoadFromClobberingMemInst(L, DepMI, *TD);
+ int Offset = AnalyzeLoadFromClobberingMemInst(L->getType(),
+ L->getPointerOperand(),
+ DepMI, *TD);
if (Offset != -1)
AvailVal = GetMemInstValueForLoad(DepMI, Offset, L->getType(), L,*TD);
}