#include "llvm/BasicBlock.h"
#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
+#include "llvm/GlobalVariable.h"
#include "llvm/Function.h"
#include "llvm/IntrinsicInst.h"
#include "llvm/LLVMContext.h"
#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; };
+
}
//===----------------------------------------------------------------------===//
"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) {
// FIXME: Study to see if/when this happens.
if (LoadOffset == StoreOffset) {
#if 0
- errs() << "STORE/LOAD DEP WITH COMMON POINTER MISSED:\n"
+ dbgs() << "STORE/LOAD DEP WITH COMMON POINTER MISSED:\n"
<< "Base = " << *StoreBase << "\n"
<< "Store Ptr = " << *WritePtr << "\n"
<< "Store Offs = " << StoreOffset << "\n"
- << "Load Ptr = " << *LoadPtr << "\n"
- << "Load Offs = " << LoadOffset << " - " << *L << "\n\n";
+ << "Load Ptr = " << *LoadPtr << "\n";
abort();
#endif
return -1;
}
if (isAAFailure) {
#if 0
- errs() << "STORE LOAD DEP WITH COMMON BASE:\n"
+ dbgs() << "STORE LOAD DEP WITH COMMON BASE:\n"
<< "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->getType(), L->getPointerOperand(),
+ 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->getType(), L->getPointerOperand(),
- 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->getType(), L->getPointerOperand(),
- 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);
}
assert(!isSimpleValue() && "Wrong accessor");
return cast<MemIntrinsic>(Val.getPointer());
}
+
+ /// MaterializeAdjustedValue - Emit code into this block to adjust the value
+ /// defined here to the specified type. This handles various coercion cases.
+ Value *MaterializeAdjustedValue(const Type *LoadTy,
+ const TargetData *TD) const {
+ Value *Res;
+ if (isSimpleValue()) {
+ Res = getSimpleValue();
+ if (Res->getType() != LoadTy) {
+ assert(TD && "Need target data to handle type mismatch case");
+ Res = GetStoreValueForLoad(Res, Offset, LoadTy, BB->getTerminator(),
+ *TD);
+
+ DEBUG(errs() << "GVN COERCED NONLOCAL VAL:\nOffset: " << Offset << " "
+ << *getSimpleValue() << '\n'
+ << *Res << '\n' << "\n\n\n");
+ }
+ } else {
+ Res = GetMemInstValueForLoad(getMemIntrinValue(), Offset,
+ LoadTy, BB->getTerminator(), *TD);
+ DEBUG(errs() << "GVN COERCED NONLOCAL MEM INTRIN:\nOffset: " << Offset
+ << " " << *getMemIntrinValue() << '\n'
+ << *Res << '\n' << "\n\n\n");
+ }
+ return Res;
+ }
};
/// ConstructSSAForLoadSet - Given a set of loads specified by ValuesPerBlock,
static Value *ConstructSSAForLoadSet(LoadInst *LI,
SmallVectorImpl<AvailableValueInBlock> &ValuesPerBlock,
const TargetData *TD,
+ const DominatorTree &DT,
AliasAnalysis *AA) {
+ // Check for the fully redundant, dominating load case. In this case, we can
+ // just use the dominating value directly.
+ if (ValuesPerBlock.size() == 1 &&
+ DT.properlyDominates(ValuesPerBlock[0].BB, LI->getParent()))
+ return ValuesPerBlock[0].MaterializeAdjustedValue(LI->getType(), TD);
+
+ // Otherwise, we have to construct SSA form.
SmallVector<PHINode*, 8> NewPHIs;
SSAUpdater SSAUpdate(&NewPHIs);
SSAUpdate.Initialize(LI);
if (SSAUpdate.HasValueForBlock(BB))
continue;
- unsigned Offset = AV.Offset;
-
- Value *AvailableVal;
- if (AV.isSimpleValue()) {
- AvailableVal = AV.getSimpleValue();
- if (AvailableVal->getType() != LoadTy) {
- assert(TD && "Need target data to handle type mismatch case");
- AvailableVal = GetStoreValueForLoad(AvailableVal, Offset, LoadTy,
- BB->getTerminator(), *TD);
-
- DEBUG(errs() << "GVN COERCED NONLOCAL VAL:\nOffset: " << Offset << " "
- << *AV.getSimpleValue() << '\n'
- << *AvailableVal << '\n' << "\n\n\n");
- }
- } else {
- AvailableVal = GetMemInstValueForLoad(AV.getMemIntrinValue(), Offset,
- LoadTy, BB->getTerminator(), *TD);
- DEBUG(errs() << "GVN COERCED NONLOCAL MEM INTRIN:\nOffset: " << Offset
- << " " << *AV.getMemIntrinValue() << '\n'
- << *AvailableVal << '\n' << "\n\n\n");
- }
- SSAUpdate.AddAvailableValue(BB, AvailableVal);
+ SSAUpdate.AddAvailableValue(BB, AV.MaterializeAdjustedValue(LoadTy, TD));
}
// Perform PHI construction.
bool GVN::processNonLocalLoad(LoadInst *LI,
SmallVectorImpl<Instruction*> &toErase) {
// Find the non-local dependencies of the load.
- SmallVector<NonLocalDepEntry, 64> Deps;
+ SmallVector<NonLocalDepResult, 64> Deps;
MD->getNonLocalPointerDependency(LI->getOperand(0), true, LI->getParent(),
Deps);
- //DEBUG(errs() << "INVESTIGATING NONLOCAL LOAD: "
+ //DEBUG(dbgs() << "INVESTIGATING NONLOCAL LOAD: "
// << Deps.size() << *LI << '\n');
// If we had to process more than one hundred blocks to find the
// clobber in the current block. Reject this early.
if (Deps.size() == 1 && Deps[0].getResult().isClobber()) {
DEBUG(
- errs() << "GVN: non-local load ";
- WriteAsOperand(errs(), LI);
- errs() << " is clobbered by " << *Deps[0].getResult().getInst() << '\n';
+ dbgs() << "GVN: non-local load ";
+ WriteAsOperand(dbgs(), LI);
+ dbgs() << " is clobbered by " << *Deps[0].getResult().getInst() << '\n';
);
return false;
}
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));
// load, then it is fully redundant and we can use PHI insertion to compute
// its value. Insert PHIs and remove the fully redundant value now.
if (UnavailableBlocks.empty()) {
- DEBUG(errs() << "GVN REMOVING NONLOCAL LOAD: " << *LI << '\n');
+ DEBUG(dbgs() << "GVN REMOVING NONLOCAL LOAD: " << *LI << '\n');
// Perform PHI construction.
- Value *V = ConstructSSAForLoadSet(LI, ValuesPerBlock, TD,
+ Value *V = ConstructSSAForLoadSet(LI, ValuesPerBlock, TD, *DT,
VN.getAliasAnalysis());
LI->replaceAllUsesWith(V);
// We don't currently handle critical edges :(
if (UnavailablePred->getTerminator()->getNumSuccessors() != 1) {
- DEBUG(errs() << "COULD NOT PRE LOAD BECAUSE OF CRITICAL EDGE '"
+ DEBUG(dbgs() << "COULD NOT PRE LOAD BECAUSE OF CRITICAL EDGE '"
<< UnavailablePred->getName() << "': " << *LI << '\n');
return false;
}
// we fail PRE.
if (LoadPtr == 0) {
assert(NewInsts.empty() && "Shouldn't insert insts on failure");
- DEBUG(errs() << "COULDN'T INSERT PHI TRANSLATED VALUE OF: "
+ DEBUG(dbgs() << "COULDN'T INSERT PHI TRANSLATED VALUE OF: "
<< *LI->getOperand(0) << "\n");
return false;
}
// Okay, we can eliminate this load by inserting a reload in the predecessor
// and using PHI construction to get the value in the other predecessors, do
// it.
- DEBUG(errs() << "GVN REMOVING PRE LOAD: " << *LI << '\n');
+ DEBUG(dbgs() << "GVN REMOVING PRE LOAD: " << *LI << '\n');
DEBUG(if (!NewInsts.empty())
- errs() << "INSERTED " << NewInsts.size() << " INSTS: "
+ dbgs() << "INSERTED " << NewInsts.size() << " INSTS: "
<< *NewInsts.back() << '\n');
Value *NewLoad = new LoadInst(LoadPtr, LI->getName()+".pre", false,
ValuesPerBlock.push_back(AvailableValueInBlock::get(UnavailablePred,NewLoad));
// Perform PHI construction.
- Value *V = ConstructSSAForLoadSet(LI, ValuesPerBlock, TD,
+ Value *V = ConstructSSAForLoadSet(LI, ValuesPerBlock, TD, *DT,
VN.getAliasAnalysis());
LI->replaceAllUsesWith(V);
if (isa<PHINode>(V))
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);
}
}
if (AvailVal) {
- DEBUG(errs() << "GVN COERCED INST:\n" << *Dep.getInst() << '\n'
+ DEBUG(dbgs() << "GVN COERCED INST:\n" << *Dep.getInst() << '\n'
<< *AvailVal << '\n' << *L << "\n\n\n");
// Replace the load!
DEBUG(
// fast print dep, using operator<< on instruction would be too slow
- errs() << "GVN: load ";
- WriteAsOperand(errs(), L);
+ dbgs() << "GVN: load ";
+ WriteAsOperand(dbgs(), L);
Instruction *I = Dep.getInst();
- errs() << " is clobbered by " << *I << '\n';
+ dbgs() << " is clobbered by " << *I << '\n';
);
return false;
}
if (StoredVal == 0)
return false;
- DEBUG(errs() << "GVN COERCED STORE:\n" << *DepSI << '\n' << *StoredVal
+ DEBUG(dbgs() << "GVN COERCED STORE:\n" << *DepSI << '\n' << *StoredVal
<< '\n' << *L << "\n\n\n");
}
else
if (AvailableVal == 0)
return false;
- DEBUG(errs() << "GVN COERCED LOAD:\n" << *DepLI << "\n" << *AvailableVal
+ DEBUG(dbgs() << "GVN COERCED LOAD:\n" << *DepLI << "\n" << *AvailableVal
<< "\n" << *L << "\n\n\n");
}
else
unsigned Iteration = 0;
while (ShouldContinue) {
- DEBUG(errs() << "GVN iteration: " << Iteration << "\n");
+ DEBUG(dbgs() << "GVN iteration: " << Iteration << "\n");
ShouldContinue = iterateOnFunction(F);
Changed |= ShouldContinue;
++Iteration;
for (SmallVector<Instruction*, 4>::iterator I = toErase.begin(),
E = toErase.end(); I != E; ++I) {
- DEBUG(errs() << "GVN removed: " << **I << '\n');
+ DEBUG(dbgs() << "GVN removed: " << **I << '\n');
if (MD) MD->removeInstruction(*I);
(*I)->eraseFromParent();
DEBUG(verifyRemoved(*I));
MD->invalidateCachedPointerInfo(Phi);
VN.erase(CurInst);
- DEBUG(errs() << "GVN PRE removed: " << *CurInst << '\n');
+ DEBUG(dbgs() << "GVN PRE removed: " << *CurInst << '\n');
if (MD) MD->removeInstruction(CurInst);
CurInst->eraseFromParent();
DEBUG(verifyRemoved(CurInst));
projects / oota-llvm.git / blobdiff