#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/CFG.h"
#include "llvm/Analysis/ConstantFolding.h"
+#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/Loads.h"
#include "llvm/Analysis/MemoryBuiltins.h"
uint32_t lookup(Value *V) const;
uint32_t lookup_or_add_cmp(unsigned Opcode, CmpInst::Predicate Pred,
Value *LHS, Value *RHS);
+ bool exists(Value *V) const;
void add(Value *V, uint32_t num);
void clear();
void erase(Value *v);
}
}
+/// Returns true if a value number exists for the specified value.
+bool ValueTable::exists(Value *V) const { return valueNumbering.count(V) != 0; }
+
/// lookup_or_add - Returns the value number for the specified value, assigning
/// it a new number if it did not have one before.
uint32_t ValueTable::lookup_or_add(Value *V) {
AU.addRequired<TargetLibraryInfoWrapperPass>();
if (!NoLoads)
AU.addRequired<MemoryDependenceAnalysis>();
- AU.addRequired<AliasAnalysis>();
+ AU.addRequired<AAResultsWrapperPass>();
AU.addPreserved<DominatorTreeWrapperPass>();
- AU.addPreserved<AliasAnalysis>();
+ AU.addPreserved<GlobalsAAWrapperPass>();
}
INITIALIZE_PASS_DEPENDENCY(MemoryDependenceAnalysis)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
-INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
+INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
INITIALIZE_PASS_END(GVN, "gvn", "Global Value Numbering", false, false)
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
SSAUpdater SSAUpdate(&NewPHIs);
SSAUpdate.Initialize(LI->getType(), LI->getName());
- for (unsigned i = 0, e = ValuesPerBlock.size(); i != e; ++i) {
- const AvailableValueInBlock &AV = ValuesPerBlock[i];
+ for (const AvailableValueInBlock &AV : ValuesPerBlock) {
BasicBlock *BB = AV.BB;
if (SSAUpdate.HasValueForBlock(BB))
// that we only have to insert *one* load (which means we're basically moving
// the load, not inserting a new one).
- SmallPtrSet<BasicBlock *, 4> Blockers;
- for (unsigned i = 0, e = UnavailableBlocks.size(); i != e; ++i)
- Blockers.insert(UnavailableBlocks[i]);
+ SmallPtrSet<BasicBlock *, 4> Blockers(UnavailableBlocks.begin(),
+ UnavailableBlocks.end());
// Let's find the first basic block with more than one predecessor. Walk
// backwards through predecessors if needed.
// available.
MapVector<BasicBlock *, Value *> PredLoads;
DenseMap<BasicBlock*, char> FullyAvailableBlocks;
- for (unsigned i = 0, e = ValuesPerBlock.size(); i != e; ++i)
- FullyAvailableBlocks[ValuesPerBlock[i].BB] = true;
- for (unsigned i = 0, e = UnavailableBlocks.size(); i != e; ++i)
- FullyAvailableBlocks[UnavailableBlocks[i]] = false;
+ for (const AvailableValueInBlock &AV : ValuesPerBlock)
+ FullyAvailableBlocks[AV.BB] = true;
+ for (BasicBlock *UnavailableBB : UnavailableBlocks)
+ FullyAvailableBlocks[UnavailableBB] = false;
SmallVector<BasicBlock *, 4> CriticalEdgePred;
- for (pred_iterator PI = pred_begin(LoadBB), E = pred_end(LoadBB);
- PI != E; ++PI) {
- BasicBlock *Pred = *PI;
+ for (BasicBlock *Pred : predecessors(LoadBB)) {
+ // If any predecessor block is an EH pad that does not allow non-PHI
+ // instructions before the terminator, we can't PRE the load.
+ if (Pred->getTerminator()->isEHPad()) {
+ DEBUG(dbgs()
+ << "COULD NOT PRE LOAD BECAUSE OF AN EH PAD PREDECESSOR '"
+ << Pred->getName() << "': " << *LI << '\n');
+ return false;
+ }
+
if (IsValueFullyAvailableInBlock(Pred, FullyAvailableBlocks, 0)) {
continue;
}
<< *NewInsts.back() << '\n');
// Assign value numbers to the new instructions.
- for (unsigned i = 0, e = NewInsts.size(); i != e; ++i) {
+ for (Instruction *I : NewInsts) {
// FIXME: We really _ought_ to insert these value numbers into their
// parent's availability map. However, in doing so, we risk getting into
// ordering issues. If a block hasn't been processed yet, we would be
// marking a value as AVAIL-IN, which isn't what we intend.
- VN.lookup_or_add(NewInsts[i]);
+ VN.lookup_or_add(I);
}
for (const auto &PredLoad : PredLoads) {
if (Tags)
NewLoad->setAAMetadata(Tags);
+ if (auto *MD = LI->getMetadata(LLVMContext::MD_invariant_load))
+ NewLoad->setMetadata(LLVMContext::MD_invariant_load, MD);
+ if (auto *InvGroupMD = LI->getMetadata(LLVMContext::MD_invariant_group))
+ NewLoad->setMetadata(LLVMContext::MD_invariant_group, InvGroupMD);
+
// Transfer DebugLoc.
NewLoad->setDebugLoc(LI->getDebugLoc());
/// Attempt to eliminate a load whose dependencies are
/// non-local by performing PHI construction.
bool GVN::processNonLocalLoad(LoadInst *LI) {
+ // non-local speculations are not allowed under asan.
+ if (LI->getParent()->getParent()->hasFnAttribute(Attribute::SanitizeAddress))
+ return false;
+
// Step 1: Find the non-local dependencies of the load.
LoadDepVect Deps;
MD->getNonLocalPointerDependency(LI, Deps);
assert(IntrinsicI->getIntrinsicID() == Intrinsic::assume &&
"This function can only be called with llvm.assume intrinsic");
Value *V = IntrinsicI->getArgOperand(0);
+
+ if (ConstantInt *Cond = dyn_cast<ConstantInt>(V)) {
+ if (Cond->isZero()) {
+ Type *Int8Ty = Type::getInt8Ty(V->getContext());
+ // Insert a new store to null instruction before the load to indicate that
+ // this code is not reachable. FIXME: We could insert unreachable
+ // instruction directly because we can modify the CFG.
+ new StoreInst(UndefValue::get(Int8Ty),
+ Constant::getNullValue(Int8Ty->getPointerTo()),
+ IntrinsicI);
+ }
+ markInstructionForDeletion(IntrinsicI);
+ return false;
+ }
+
Constant *True = ConstantInt::getTrue(V->getContext());
bool Changed = false;
+
for (BasicBlock *Successor : successors(IntrinsicI->getParent())) {
BasicBlockEdge Edge(IntrinsicI->getParent(), Successor);
// will check dominance for us.
Changed |= propagateEquality(V, True, Edge, false);
}
+
// We can replace assume value with true, which covers cases like this:
// call void @llvm.assume(i1 %cmp)
// br i1 %cmp, label %bb1, label %bb2 ; will change %cmp to true
// regions, and so we need a conservative combination of the noalias
// scopes.
static const unsigned KnownIDs[] = {
- LLVMContext::MD_tbaa,
- LLVMContext::MD_alias_scope,
- LLVMContext::MD_noalias,
- LLVMContext::MD_range,
- LLVMContext::MD_fpmath,
- LLVMContext::MD_invariant_load,
- };
+ LLVMContext::MD_tbaa, LLVMContext::MD_alias_scope,
+ LLVMContext::MD_noalias, LLVMContext::MD_range,
+ LLVMContext::MD_fpmath, LLVMContext::MD_invariant_load,
+ LLVMContext::MD_invariant_group};
combineMetadata(ReplInst, I, KnownIDs);
}
}
++NumGVNLoad;
return true;
}
- }
- // If the value isn't available, don't do anything!
- if (Dep.isClobber()) {
+ // If the value isn't available, don't do anything!
DEBUG(
// fast print dep, using operator<< on instruction is too slow.
dbgs() << "GVN: load ";
Value *Operand = Instr->getOperand(OpNum);
auto it = ReplaceWithConstMap.find(Operand);
if (it != ReplaceWithConstMap.end()) {
+ assert(!isa<Constant>(Operand) &&
+ "Replacing constants with constants is invalid");
+ DEBUG(dbgs() << "GVN replacing: " << *Operand << " with " << *it->second
+ << " in instruction " << *Instr << '\n');
Instr->setOperand(OpNum, it->second);
Changed = true;
}
// Perform fast-path value-number based elimination of values inherited from
// dominators.
- Value *repl = findLeader(I->getParent(), Num);
- if (!repl) {
+ Value *Repl = findLeader(I->getParent(), Num);
+ if (!Repl) {
// Failure, just remember this instance for future use.
addToLeaderTable(Num, I, I->getParent());
return false;
+ } else if (Repl == I) {
+ // If I was the result of a shortcut PRE, it might already be in the table
+ // and the best replacement for itself. Nothing to do.
+ return false;
}
// Remove it!
- patchAndReplaceAllUsesWith(I, repl);
- if (MD && repl->getType()->getScalarType()->isPointerTy())
- MD->invalidateCachedPointerInfo(repl);
+ patchAndReplaceAllUsesWith(I, Repl);
+ if (MD && Repl->getType()->getScalarType()->isPointerTy())
+ MD->invalidateCachedPointerInfo(Repl);
markInstructionForDeletion(I);
return true;
}
DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
- VN.setAliasAnalysis(&getAnalysis<AliasAnalysis>());
+ VN.setAliasAnalysis(&getAnalysis<AAResultsWrapperPass>().getAAResults());
VN.setMemDep(MD);
VN.setDomTree(DT);
// Merge unconditional branches, allowing PRE to catch more
// optimization opportunities.
for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ) {
- BasicBlock *BB = FI++;
+ BasicBlock *BB = &*FI++;
bool removedBlock =
MergeBlockIntoPredecessor(BB, DT, /* LoopInfo */ nullptr, MD);
return Changed;
}
-
bool GVN::processBlock(BasicBlock *BB) {
// FIXME: Kill off InstrsToErase by doing erasing eagerly in a helper function
// (and incrementing BI before processing an instruction).
for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
BI != BE;) {
if (!ReplaceWithConstMap.empty())
- ChangedFunction |= replaceOperandsWithConsts(BI);
+ ChangedFunction |= replaceOperandsWithConsts(&*BI);
+ ChangedFunction |= processInstruction(&*BI);
- ChangedFunction |= processInstruction(BI);
if (InstrsToErase.empty()) {
++BI;
continue;
Value *Op = Instr->getOperand(i);
if (isa<Argument>(Op) || isa<Constant>(Op) || isa<GlobalValue>(Op))
continue;
-
+ // This could be a newly inserted instruction, in which case, we won't
+ // find a value number, and should give up before we hurt ourselves.
+ // FIXME: Rewrite the infrastructure to let it easier to value number
+ // and process newly inserted instructions.
+ if (!VN.exists(Op)) {
+ success = false;
+ break;
+ }
if (Value *V = findLeader(Pred, VN.lookup(Op))) {
Instr->setOperand(i, V);
} else {
BasicBlock *CurrentBlock = CurInst->getParent();
predMap.clear();
- for (pred_iterator PI = pred_begin(CurrentBlock), PE = pred_end(CurrentBlock);
- PI != PE; ++PI) {
- BasicBlock *P = *PI;
+ for (BasicBlock *P : predecessors(CurrentBlock)) {
// We're not interested in PRE where the block is its
// own predecessor, or in blocks with predecessors
// that are not reachable.
// Create a PHI to make the value available in this block.
PHINode *Phi =
PHINode::Create(CurInst->getType(), predMap.size(),
- CurInst->getName() + ".pre-phi", CurrentBlock->begin());
+ CurInst->getName() + ".pre-phi", &CurrentBlock->front());
for (unsigned i = 0, e = predMap.size(); i != e; ++i) {
if (Value *V = predMap[i].first)
Phi->addIncoming(V, predMap[i].second);
for (BasicBlock::iterator BI = CurrentBlock->begin(),
BE = CurrentBlock->end();
BI != BE;) {
- Instruction *CurInst = BI++;
- Changed = performScalarPRE(CurInst);
+ Instruction *CurInst = &*BI++;
+ Changed |= performScalarPRE(CurInst);
}
}
DeadBlocks.insert(Dom.begin(), Dom.end());
// Figure out the dominance-frontier(D).
- for (SmallVectorImpl<BasicBlock *>::iterator I = Dom.begin(),
- E = Dom.end(); I != E; I++) {
- BasicBlock *B = *I;
- for (succ_iterator SI = succ_begin(B), SE = succ_end(B); SI != SE; SI++) {
- BasicBlock *S = *SI;
+ for (BasicBlock *B : Dom) {
+ for (BasicBlock *S : successors(B)) {
if (DeadBlocks.count(S))
continue;
bool AllPredDead = true;
- for (pred_iterator PI = pred_begin(S), PE = pred_end(S); PI != PE; PI++)
- if (!DeadBlocks.count(*PI)) {
+ for (BasicBlock *P : predecessors(S))
+ if (!DeadBlocks.count(P)) {
AllPredDead = false;
break;
}
continue;
SmallVector<BasicBlock *, 4> Preds(pred_begin(B), pred_end(B));
- for (SmallVectorImpl<BasicBlock *>::iterator PI = Preds.begin(),
- PE = Preds.end(); PI != PE; PI++) {
- BasicBlock *P = *PI;
-
+ for (BasicBlock *P : Preds) {
if (!DeadBlocks.count(P))
continue;
// instructions, it makes more sense just to "fabricate" a val-number for the
// dead code than checking if instruction involved is dead or not.
void GVN::assignValNumForDeadCode() {
- for (SetVector<BasicBlock *>::iterator I = DeadBlocks.begin(),
- E = DeadBlocks.end(); I != E; I++) {
- BasicBlock *BB = *I;
- for (BasicBlock::iterator II = BB->begin(), EE = BB->end();
- II != EE; II++) {
- Instruction *Inst = &*II;
- unsigned ValNum = VN.lookup_or_add(Inst);
- addToLeaderTable(ValNum, Inst, BB);
+ for (BasicBlock *BB : DeadBlocks) {
+ for (Instruction &Inst : *BB) {
+ unsigned ValNum = VN.lookup_or_add(&Inst);
+ addToLeaderTable(ValNum, &Inst, BB);
}
}
}
projects / oota-llvm.git / blobdiff