X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FGVN.cpp;h=a028b8c444baed70aeabec6978c908663e65c98b;hp=17b4bb2629a990f9f85a49dccdf45a5653f0318b;hb=697498bd8e5e2637150b9ee64a2c22809413a252;hpb=881c8e0c9ac3eb8d9d20d34b2354ac413f8146b4 diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp index 17b4bb2629a..a028b8c444b 100644 --- a/lib/Transforms/Scalar/GVN.cpp +++ b/lib/Transforms/Scalar/GVN.cpp @@ -28,6 +28,7 @@ #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" @@ -128,6 +129,7 @@ namespace { 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); @@ -388,6 +390,9 @@ uint32_t ValueTable::lookup_or_add_call(CallInst *C) { } } +/// 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) { @@ -608,6 +613,10 @@ namespace { DenseMap LeaderTable; BumpPtrAllocator TableAllocator; + // Block-local map of equivalent values to their leader, does not + // propagate to any successors. Entries added mid-block are applied + // to the remaining instructions in the block. + SmallMapVector ReplaceWithConstMap; SmallVector InstrsToErase; typedef SmallVector LoadDepVect; @@ -656,11 +665,14 @@ namespace { LeaderTableEntry* Prev = nullptr; LeaderTableEntry* Curr = &LeaderTable[N]; - while (Curr->Val != I || Curr->BB != BB) { + while (Curr && (Curr->Val != I || Curr->BB != BB)) { Prev = Curr; Curr = Curr->Next; } + if (!Curr) + return; + if (Prev) { Prev->Next = Curr->Next; } else { @@ -686,16 +698,17 @@ namespace { AU.addRequired(); if (!NoLoads) AU.addRequired(); - AU.addRequired(); + AU.addRequired(); AU.addPreserved(); - AU.addPreserved(); + AU.addPreserved(); } - // Helper fuctions of redundant load elimination + // Helper functions of redundant load elimination bool processLoad(LoadInst *L); bool processNonLocalLoad(LoadInst *L); + bool processAssumeIntrinsic(IntrinsicInst *II); void AnalyzeLoadAvailability(LoadInst *LI, LoadDepVect &Deps, AvailValInBlkVect &ValuesPerBlock, UnavailBlkVect &UnavailableBlocks); @@ -716,7 +729,9 @@ namespace { void verifyRemoved(const Instruction *I) const; bool splitCriticalEdges(); BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ); - bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root); + bool replaceOperandsWithConsts(Instruction *I) const; + bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root, + bool DominatesByEdge); bool processFoldableCondBr(BranchInst *BI); void addDeadBlock(BasicBlock *BB); void assignValNumForDeadCode(); @@ -735,7 +750,8 @@ INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) 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) @@ -852,13 +868,12 @@ static bool CanCoerceMustAliasedValueToLoad(Value *StoredVal, /// If we saw a store of a value to memory, and /// then a load from a must-aliased pointer of a different type, try to coerce -/// the stored value. LoadedTy is the type of the load we want to replace and -/// InsertPt is the place to insert new instructions. +/// the stored value. LoadedTy is the type of the load we want to replace. +/// IRB is IRBuilder used to insert new instructions. /// /// If we can't do it, return null. -static Value *CoerceAvailableValueToLoadType(Value *StoredVal, - Type *LoadedTy, - Instruction *InsertPt, +static Value *CoerceAvailableValueToLoadType(Value *StoredVal, Type *LoadedTy, + IRBuilder<> &IRB, const DataLayout &DL) { if (!CanCoerceMustAliasedValueToLoad(StoredVal, LoadedTy, DL)) return nullptr; @@ -874,12 +889,12 @@ static Value *CoerceAvailableValueToLoadType(Value *StoredVal, // Pointer to Pointer -> use bitcast. if (StoredValTy->getScalarType()->isPointerTy() && LoadedTy->getScalarType()->isPointerTy()) - return new BitCastInst(StoredVal, LoadedTy, "", InsertPt); + return IRB.CreateBitCast(StoredVal, LoadedTy); // Convert source pointers to integers, which can be bitcast. if (StoredValTy->getScalarType()->isPointerTy()) { StoredValTy = DL.getIntPtrType(StoredValTy); - StoredVal = new PtrToIntInst(StoredVal, StoredValTy, "", InsertPt); + StoredVal = IRB.CreatePtrToInt(StoredVal, StoredValTy); } Type *TypeToCastTo = LoadedTy; @@ -887,11 +902,11 @@ static Value *CoerceAvailableValueToLoadType(Value *StoredVal, TypeToCastTo = DL.getIntPtrType(TypeToCastTo); if (StoredValTy != TypeToCastTo) - StoredVal = new BitCastInst(StoredVal, TypeToCastTo, "", InsertPt); + StoredVal = IRB.CreateBitCast(StoredVal, TypeToCastTo); // Cast to pointer if the load needs a pointer type. if (LoadedTy->getScalarType()->isPointerTy()) - StoredVal = new IntToPtrInst(StoredVal, LoadedTy, "", InsertPt); + StoredVal = IRB.CreateIntToPtr(StoredVal, LoadedTy); return StoredVal; } @@ -904,35 +919,34 @@ static Value *CoerceAvailableValueToLoadType(Value *StoredVal, // Convert source pointers to integers, which can be manipulated. if (StoredValTy->getScalarType()->isPointerTy()) { StoredValTy = DL.getIntPtrType(StoredValTy); - StoredVal = new PtrToIntInst(StoredVal, StoredValTy, "", InsertPt); + StoredVal = IRB.CreatePtrToInt(StoredVal, StoredValTy); } // Convert vectors and fp to integer, which can be manipulated. if (!StoredValTy->isIntegerTy()) { StoredValTy = IntegerType::get(StoredValTy->getContext(), StoreSize); - StoredVal = new BitCastInst(StoredVal, StoredValTy, "", InsertPt); + StoredVal = IRB.CreateBitCast(StoredVal, StoredValTy); } // If this is a big-endian system, we need to shift the value down to the low // bits so that a truncate will work. if (DL.isBigEndian()) { - Constant *Val = ConstantInt::get(StoredVal->getType(), StoreSize-LoadSize); - StoredVal = BinaryOperator::CreateLShr(StoredVal, Val, "tmp", InsertPt); + StoredVal = IRB.CreateLShr(StoredVal, StoreSize - LoadSize, "tmp"); } // Truncate the integer to the right size now. Type *NewIntTy = IntegerType::get(StoredValTy->getContext(), LoadSize); - StoredVal = new TruncInst(StoredVal, NewIntTy, "trunc", InsertPt); + StoredVal = IRB.CreateTrunc(StoredVal, NewIntTy, "trunc"); if (LoadedTy == NewIntTy) return StoredVal; // If the result is a pointer, inttoptr. if (LoadedTy->getScalarType()->isPointerTy()) - return new IntToPtrInst(StoredVal, LoadedTy, "inttoptr", InsertPt); + return IRB.CreateIntToPtr(StoredVal, LoadedTy, "inttoptr"); // Otherwise, bitcast. - return new BitCastInst(StoredVal, LoadedTy, "bitcast", InsertPt); + return IRB.CreateBitCast(StoredVal, LoadedTy, "bitcast"); } /// This function is called when we have a @@ -1122,7 +1136,7 @@ static Value *GetStoreValueForLoad(Value *SrcVal, unsigned Offset, uint64_t StoreSize = (DL.getTypeSizeInBits(SrcVal->getType()) + 7) / 8; uint64_t LoadSize = (DL.getTypeSizeInBits(LoadTy) + 7) / 8; - IRBuilder<> Builder(InsertPt->getParent(), InsertPt); + IRBuilder<> Builder(InsertPt); // Compute which bits of the stored value are being used by the load. Convert // to an integer type to start with. @@ -1145,7 +1159,7 @@ static Value *GetStoreValueForLoad(Value *SrcVal, unsigned Offset, if (LoadSize != StoreSize) SrcVal = Builder.CreateTrunc(SrcVal, IntegerType::get(Ctx, LoadSize*8)); - return CoerceAvailableValueToLoadType(SrcVal, LoadTy, InsertPt, DL); + return CoerceAvailableValueToLoadType(SrcVal, LoadTy, Builder, DL); } /// This function is called when we have a @@ -1219,7 +1233,7 @@ static Value *GetMemInstValueForLoad(MemIntrinsic *SrcInst, unsigned Offset, LLVMContext &Ctx = LoadTy->getContext(); uint64_t LoadSize = DL.getTypeSizeInBits(LoadTy)/8; - IRBuilder<> Builder(InsertPt->getParent(), InsertPt); + IRBuilder<> Builder(InsertPt); // We know that this method is only called when the mem transfer fully // provides the bits for the load. @@ -1248,7 +1262,7 @@ static Value *GetMemInstValueForLoad(MemIntrinsic *SrcInst, unsigned Offset, ++NumBytesSet; } - return CoerceAvailableValueToLoadType(Val, LoadTy, InsertPt, DL); + return CoerceAvailableValueToLoadType(Val, LoadTy, Builder, DL); } // Otherwise, this is a memcpy/memmove from a constant global. @@ -1289,8 +1303,7 @@ static Value *ConstructSSAForLoadSet(LoadInst *LI, 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)) @@ -1300,28 +1313,7 @@ static Value *ConstructSSAForLoadSet(LoadInst *LI, } // Perform PHI construction. - Value *V = SSAUpdate.GetValueInMiddleOfBlock(LI->getParent()); - - // If new PHI nodes were created, notify alias analysis. - if (V->getType()->getScalarType()->isPointerTy()) { - AliasAnalysis *AA = gvn.getAliasAnalysis(); - - for (unsigned i = 0, e = NewPHIs.size(); i != e; ++i) - AA->copyValue(LI, NewPHIs[i]); - - // Now that we've copied information to the new PHIs, scan through - // them again and inform alias analysis that we've added potentially - // escaping uses to any values that are operands to these PHIs. - for (unsigned i = 0, e = NewPHIs.size(); i != e; ++i) { - PHINode *P = NewPHIs[i]; - for (unsigned ii = 0, ee = P->getNumIncomingValues(); ii != ee; ++ii) { - unsigned jj = PHINode::getOperandNumForIncomingValue(ii); - AA->addEscapingUse(P->getOperandUse(jj)); - } - } - } - - return V; + return SSAUpdate.GetValueInMiddleOfBlock(LI->getParent()); } Value *AvailableValueInBlock::MaterializeAdjustedValue(LoadInst *LI, @@ -1521,9 +1513,8 @@ bool GVN::PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock, // that we only have to insert *one* load (which means we're basically moving // the load, not inserting a new one). - SmallPtrSet Blockers; - for (unsigned i = 0, e = UnavailableBlocks.size(); i != e; ++i) - Blockers.insert(UnavailableBlocks[i]); + SmallPtrSet Blockers(UnavailableBlocks.begin(), + UnavailableBlocks.end()); // Let's find the first basic block with more than one predecessor. Walk // backwards through predecessors if needed. @@ -1553,15 +1544,22 @@ bool GVN::PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock, // available. MapVector PredLoads; DenseMap 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 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; } @@ -1573,9 +1571,9 @@ bool GVN::PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock, return false; } - if (LoadBB->isLandingPad()) { + if (LoadBB->isEHPad()) { DEBUG(dbgs() - << "COULD NOT PRE LOAD BECAUSE OF LANDING PAD CRITICAL EDGE '" + << "COULD NOT PRE LOAD BECAUSE OF AN EH PAD CRITICAL EDGE '" << Pred->getName() << "': " << *LI << '\n'); return false; } @@ -1658,12 +1656,12 @@ bool GVN::PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock, << *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) { @@ -1680,6 +1678,11 @@ bool GVN::PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock, 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()); @@ -1707,6 +1710,10 @@ bool GVN::PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock, /// 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); @@ -1764,7 +1771,8 @@ bool GVN::processNonLocalLoad(LoadInst *LI) { if (isa(V)) V->takeName(LI); if (Instruction *I = dyn_cast(V)) - I->setDebugLoc(LI->getDebugLoc()); + if (LI->getDebugLoc()) + I->setDebugLoc(LI->getDebugLoc()); if (V->getType()->getScalarType()->isPointerTy()) MD->invalidateCachedPointerInfo(V); markInstructionForDeletion(LI); @@ -1779,37 +1787,87 @@ bool GVN::processNonLocalLoad(LoadInst *LI) { return PerformLoadPRE(LI, ValuesPerBlock, UnavailableBlocks); } +bool GVN::processAssumeIntrinsic(IntrinsicInst *IntrinsicI) { + 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(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); + + // This property is only true in dominated successors, propagateEquality + // 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 + ReplaceWithConstMap[V] = True; + + // If one of *cmp *eq operand is const, adding it to map will cover this: + // %cmp = fcmp oeq float 3.000000e+00, %0 ; const on lhs could happen + // call void @llvm.assume(i1 %cmp) + // ret float %0 ; will change it to ret float 3.000000e+00 + if (auto *CmpI = dyn_cast(V)) { + if (CmpI->getPredicate() == CmpInst::Predicate::ICMP_EQ || + CmpI->getPredicate() == CmpInst::Predicate::FCMP_OEQ || + (CmpI->getPredicate() == CmpInst::Predicate::FCMP_UEQ && + CmpI->getFastMathFlags().noNaNs())) { + Value *CmpLHS = CmpI->getOperand(0); + Value *CmpRHS = CmpI->getOperand(1); + if (isa(CmpLHS)) + std::swap(CmpLHS, CmpRHS); + auto *RHSConst = dyn_cast(CmpRHS); + + // If only one operand is constant. + if (RHSConst != nullptr && !isa(CmpLHS)) + ReplaceWithConstMap[CmpLHS] = RHSConst; + } + } + return Changed; +} static void patchReplacementInstruction(Instruction *I, Value *Repl) { // Patch the replacement so that it is not more restrictive than the value // being replaced. BinaryOperator *Op = dyn_cast(I); BinaryOperator *ReplOp = dyn_cast(Repl); - if (Op && ReplOp && isa(Op) && - isa(ReplOp)) { - if (ReplOp->hasNoSignedWrap() && !Op->hasNoSignedWrap()) - ReplOp->setHasNoSignedWrap(false); - if (ReplOp->hasNoUnsignedWrap() && !Op->hasNoUnsignedWrap()) - ReplOp->setHasNoUnsignedWrap(false); - } + if (Op && ReplOp) + ReplOp->andIRFlags(Op); + if (Instruction *ReplInst = dyn_cast(Repl)) { // FIXME: If both the original and replacement value are part of the // same control-flow region (meaning that the execution of one - // guarentees the executation of the other), then we can combine the + // guarantees the execution of the other), then we can combine the // noalias scopes here and do better than the general conservative // answer used in combineMetadata(). // In general, GVN unifies expressions over different control-flow // regions, and so we need a conservative combination of the noalias // scopes. - unsigned KnownIDs[] = { - LLVMContext::MD_tbaa, - LLVMContext::MD_alias_scope, - LLVMContext::MD_noalias, - LLVMContext::MD_range, - LLVMContext::MD_fpmath, - LLVMContext::MD_invariant_load, - }; + 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_invariant_group}; combineMetadata(ReplInst, I, KnownIDs); } } @@ -1896,10 +1954,8 @@ bool GVN::processLoad(LoadInst *L) { ++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 "; @@ -1932,8 +1988,9 @@ bool GVN::processLoad(LoadInst *L) { // actually have the same type. See if we know how to reuse the stored // value (depending on its type). if (StoredVal->getType() != L->getType()) { + IRBuilder<> Builder(L); StoredVal = - CoerceAvailableValueToLoadType(StoredVal, L->getType(), L, DL); + CoerceAvailableValueToLoadType(StoredVal, L->getType(), Builder, DL); if (!StoredVal) return false; @@ -1957,7 +2014,9 @@ bool GVN::processLoad(LoadInst *L) { // the same type. See if we know how to reuse the previously loaded value // (depending on its type). if (DepLI->getType() != L->getType()) { - AvailableVal = CoerceAvailableValueToLoadType(DepLI, L->getType(), L, DL); + IRBuilder<> Builder(L); + AvailableVal = + CoerceAvailableValueToLoadType(DepLI, L->getType(), Builder, DL); if (!AvailableVal) return false; @@ -2052,11 +2111,31 @@ static bool isOnlyReachableViaThisEdge(const BasicBlockEdge &E, return Pred != nullptr; } +// Tries to replace instruction with const, using information from +// ReplaceWithConstMap. +bool GVN::replaceOperandsWithConsts(Instruction *Instr) const { + bool Changed = false; + for (unsigned OpNum = 0; OpNum < Instr->getNumOperands(); ++OpNum) { + Value *Operand = Instr->getOperand(OpNum); + auto it = ReplaceWithConstMap.find(Operand); + if (it != ReplaceWithConstMap.end()) { + assert(!isa(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; + } + } + return Changed; +} + /// The given values are known to be equal in every block /// dominated by 'Root'. Exploit this, for example by replacing 'LHS' with /// 'RHS' everywhere in the scope. Returns whether a change was made. -bool GVN::propagateEquality(Value *LHS, Value *RHS, - const BasicBlockEdge &Root) { +/// If DominatesByEdge is false, then it means that it is dominated by Root.End. +bool GVN::propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root, + bool DominatesByEdge) { SmallVector, 4> Worklist; Worklist.push_back(std::make_pair(LHS, RHS)); bool Changed = false; @@ -2068,11 +2147,13 @@ bool GVN::propagateEquality(Value *LHS, Value *RHS, std::pair Item = Worklist.pop_back_val(); LHS = Item.first; RHS = Item.second; - if (LHS == RHS) continue; + if (LHS == RHS) + continue; assert(LHS->getType() == RHS->getType() && "Equality but unequal types!"); // Don't try to propagate equalities between constants. - if (isa(LHS) && isa(RHS)) continue; + if (isa(LHS) && isa(RHS)) + continue; // Prefer a constant on the right-hand side, or an Argument if no constants. if (isa(LHS) || (isa(LHS) && !isa(RHS))) @@ -2111,7 +2192,11 @@ bool GVN::propagateEquality(Value *LHS, Value *RHS, // LHS always has at least one use that is not dominated by Root, this will // never do anything if LHS has only one use. if (!LHS->hasOneUse()) { - unsigned NumReplacements = replaceDominatedUsesWith(LHS, RHS, *DT, Root); + unsigned NumReplacements = + DominatesByEdge + ? replaceDominatedUsesWith(LHS, RHS, *DT, Root) + : replaceDominatedUsesWith(LHS, RHS, *DT, Root.getEnd()); + Changed |= NumReplacements > 0; NumGVNEqProp += NumReplacements; } @@ -2183,7 +2268,10 @@ bool GVN::propagateEquality(Value *LHS, Value *RHS, Value *NotCmp = findLeader(Root.getEnd(), Num); if (NotCmp && isa(NotCmp)) { unsigned NumReplacements = - replaceDominatedUsesWith(NotCmp, NotVal, *DT, Root); + DominatesByEdge + ? replaceDominatedUsesWith(NotCmp, NotVal, *DT, Root) + : replaceDominatedUsesWith(NotCmp, NotVal, *DT, + Root.getEnd()); Changed |= NumReplacements > 0; NumGVNEqProp += NumReplacements; } @@ -2223,6 +2311,10 @@ bool GVN::processInstruction(Instruction *I) { return true; } + if (IntrinsicInst *IntrinsicI = dyn_cast(I)) + if (IntrinsicI->getIntrinsicID() == Intrinsic::assume) + return processAssumeIntrinsic(IntrinsicI); + if (LoadInst *LI = dyn_cast(I)) { if (processLoad(LI)) return true; @@ -2253,11 +2345,11 @@ bool GVN::processInstruction(Instruction *I) { Value *TrueVal = ConstantInt::getTrue(TrueSucc->getContext()); BasicBlockEdge TrueE(Parent, TrueSucc); - Changed |= propagateEquality(BranchCond, TrueVal, TrueE); + Changed |= propagateEquality(BranchCond, TrueVal, TrueE, true); Value *FalseVal = ConstantInt::getFalse(FalseSucc->getContext()); BasicBlockEdge FalseE(Parent, FalseSucc); - Changed |= propagateEquality(BranchCond, FalseVal, FalseE); + Changed |= propagateEquality(BranchCond, FalseVal, FalseE, true); return Changed; } @@ -2279,7 +2371,7 @@ bool GVN::processInstruction(Instruction *I) { // If there is only a single edge, propagate the case value into it. if (SwitchEdges.lookup(Dst) == 1) { BasicBlockEdge E(Parent, Dst); - Changed |= propagateEquality(SwitchCond, i.getCaseValue(), E); + Changed |= propagateEquality(SwitchCond, i.getCaseValue(), E, true); } } return Changed; @@ -2287,7 +2379,8 @@ bool GVN::processInstruction(Instruction *I) { // Instructions with void type don't return a value, so there's // no point in trying to find redundancies in them. - if (I->getType()->isVoidTy()) return false; + if (I->getType()->isVoidTy()) + return false; uint32_t NextNum = VN.getNextUnusedValueNumber(); unsigned Num = VN.lookup_or_add(I); @@ -2309,17 +2402,21 @@ bool GVN::processInstruction(Instruction *I) { // 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; } @@ -2334,7 +2431,7 @@ bool GVN::runOnFunction(Function& F) { DT = &getAnalysis().getDomTree(); AC = &getAnalysis().getAssumptionCache(F); TLI = &getAnalysis().getTLI(); - VN.setAliasAnalysis(&getAnalysis()); + VN.setAliasAnalysis(&getAnalysis().getAAResults()); VN.setMemDep(MD); VN.setDomTree(DT); @@ -2344,10 +2441,10 @@ bool GVN::runOnFunction(Function& F) { // 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, VN.getAliasAnalysis(), MD); + bool removedBlock = + MergeBlockIntoPredecessor(BB, DT, /* LoopInfo */ nullptr, MD); if (removedBlock) ++NumGVNBlocks; Changed |= removedBlock; @@ -2385,7 +2482,6 @@ bool GVN::runOnFunction(Function& F) { 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). @@ -2394,11 +2490,16 @@ bool GVN::processBlock(BasicBlock *BB) { if (DeadBlocks.count(BB)) return false; + // Clearing map before every BB because it can be used only for single BB. + ReplaceWithConstMap.clear(); bool ChangedFunction = false; for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) { - ChangedFunction |= processInstruction(BI); + if (!ReplaceWithConstMap.empty()) + ChangedFunction |= replaceOperandsWithConsts(&*BI); + ChangedFunction |= processInstruction(&*BI); + if (InstrsToErase.empty()) { ++BI; continue; @@ -2442,7 +2543,14 @@ bool GVN::performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred, Value *Op = Instr->getOperand(i); if (isa(Op) || isa(Op) || isa(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 { @@ -2502,9 +2610,7 @@ bool GVN::performScalarPRE(Instruction *CurInst) { 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. @@ -2573,7 +2679,7 @@ bool GVN::performScalarPRE(Instruction *CurInst) { // 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); @@ -2585,18 +2691,8 @@ bool GVN::performScalarPRE(Instruction *CurInst) { addToLeaderTable(ValNo, Phi, CurrentBlock); Phi->setDebugLoc(CurInst->getDebugLoc()); CurInst->replaceAllUsesWith(Phi); - if (Phi->getType()->getScalarType()->isPointerTy()) { - // Because we have added a PHI-use of the pointer value, it has now - // "escaped" from alias analysis' perspective. We need to inform - // AA of this. - for (unsigned ii = 0, ee = Phi->getNumIncomingValues(); ii != ee; ++ii) { - unsigned jj = PHINode::getOperandNumForIncomingValue(ii); - VN.getAliasAnalysis()->addEscapingUse(Phi->getOperandUse(jj)); - } - - if (MD) - MD->invalidateCachedPointerInfo(Phi); - } + if (MD && Phi->getType()->getScalarType()->isPointerTy()) + MD->invalidateCachedPointerInfo(Phi); VN.erase(CurInst); removeFromLeaderTable(ValNo, CurInst, CurrentBlock); @@ -2619,15 +2715,15 @@ bool GVN::performPRE(Function &F) { if (CurrentBlock == &F.getEntryBlock()) continue; - // Don't perform PRE on a landing pad. - if (CurrentBlock->isLandingPad()) + // Don't perform PRE on an EH pad. + if (CurrentBlock->isEHPad()) continue; for (BasicBlock::iterator BI = CurrentBlock->begin(), BE = CurrentBlock->end(); BI != BE;) { - Instruction *CurInst = BI++; - Changed = performScalarPRE(CurInst); + Instruction *CurInst = &*BI++; + Changed |= performScalarPRE(CurInst); } } @@ -2640,8 +2736,8 @@ bool GVN::performPRE(Function &F) { /// Split the critical edge connecting the given two blocks, and return /// the block inserted to the critical edge. BasicBlock *GVN::splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ) { - BasicBlock *BB = SplitCriticalEdge( - Pred, Succ, CriticalEdgeSplittingOptions(getAliasAnalysis(), DT)); + BasicBlock *BB = + SplitCriticalEdge(Pred, Succ, CriticalEdgeSplittingOptions(DT)); if (MD) MD->invalidateCachedPredecessors(); return BB; @@ -2655,7 +2751,7 @@ bool GVN::splitCriticalEdges() { do { std::pair Edge = toSplit.pop_back_val(); SplitCriticalEdge(Edge.first, Edge.second, - CriticalEdgeSplittingOptions(getAliasAnalysis(), DT)); + CriticalEdgeSplittingOptions(DT)); } while (!toSplit.empty()); if (MD) MD->invalidateCachedPredecessors(); return true; @@ -2731,17 +2827,14 @@ void GVN::addDeadBlock(BasicBlock *BB) { DeadBlocks.insert(Dom.begin(), Dom.end()); // Figure out the dominance-frontier(D). - for (SmallVectorImpl::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; } @@ -2769,10 +2862,7 @@ void GVN::addDeadBlock(BasicBlock *BB) { continue; SmallVector Preds(pred_begin(B), pred_end(B)); - for (SmallVectorImpl::iterator PI = Preds.begin(), - PE = Preds.end(); PI != PE; PI++) { - BasicBlock *P = *PI; - + for (BasicBlock *P : Preds) { if (!DeadBlocks.count(P)) continue; @@ -2797,7 +2887,7 @@ void GVN::addDeadBlock(BasicBlock *BB) { // R be the target of the dead out-coming edge. // 1) Identify the set of dead blocks implied by the branch's dead outcoming // edge. The result of this step will be {X| X is dominated by R} -// 2) Identify those blocks which haves at least one dead prodecessor. The +// 2) Identify those blocks which haves at least one dead predecessor. The // result of this step will be dominance-frontier(R). // 3) Update the PHIs in DF(R) by replacing the operands corresponding to // dead blocks with "UndefVal" in an hope these PHIs will optimized away. @@ -2807,6 +2897,10 @@ bool GVN::processFoldableCondBr(BranchInst *BI) { if (!BI || BI->isUnconditional()) return false; + // If a branch has two identical successors, we cannot declare either dead. + if (BI->getSuccessor(0) == BI->getSuccessor(1)) + return false; + ConstantInt *Cond = dyn_cast(BI->getCondition()); if (!Cond) return false; @@ -2828,14 +2922,10 @@ bool GVN::processFoldableCondBr(BranchInst *BI) { // 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::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); } } }