diff --git a/llvm/lib/Transforms/Scalar/GVN.cpp b/llvm/lib/Transforms/Scalar/GVN.cpp --- a/llvm/lib/Transforms/Scalar/GVN.cpp +++ b/llvm/lib/Transforms/Scalar/GVN.cpp @@ -98,21 +98,30 @@ STATISTIC(NumGVNEqProp, "Number of equalities propagated"); STATISTIC(NumPRELoad, "Number of loads PRE'd"); +STATISTIC(IsValueFullyAvailableInBlockNumSpeculationsMax, + "How many blocks have we speculated as avaliable in " + "IsValueFullyAvailableInBlock(), max?"); +STATISTIC(MaxBBSpeculationCutoffReachedTimes, + "How many did we reach a gvn-max-block-speculations cut-off " + "preventing further exploration?"); + static cl::opt GVNEnablePRE("enable-pre", cl::init(true), cl::Hidden); static cl::opt GVNEnableLoadPRE("enable-load-pre", cl::init(true)); static cl::opt GVNEnableLoadInLoopPRE("enable-load-in-loop-pre", cl::init(true)); static cl::opt GVNEnableMemDep("enable-gvn-memdep", cl::init(true)); -// Maximum allowed recursion depth. -static cl::opt -MaxRecurseDepth("gvn-max-recurse-depth", cl::Hidden, cl::init(1000), cl::ZeroOrMore, - cl::desc("Max recurse depth in GVN (default = 1000)")); - static cl::opt MaxNumDeps( "gvn-max-num-deps", cl::Hidden, cl::init(100), cl::ZeroOrMore, cl::desc("Max number of dependences to attempt Load PRE (default = 100)")); +// This is based on IsValueFullyAvailableInBlockNumSpeculationsMax stat. +static cl::opt MaxBBSpeculations( + "gvn-max-block-speculations", cl::Hidden, cl::init(600), cl::ZeroOrMore, + cl::desc("Max number of blocks we're willing to speculate on (and recurse " + "into) when deducing if a value is fully avaliable or not in GVN " + "(default = unlimited)")); + struct llvm::GVN::Expression { uint32_t opcode; bool commutative = false; @@ -669,15 +678,14 @@ enum class AvaliabilityState : char { /// We know the block *is not* fully available. This is a fixpoint. - Unavaliable = 0, + Unavailable = 0, /// We know the block *is* fully available. This is a fixpoint. - Avaliable = 1, + Available = 1, /// We do not know whether the block is fully available or not, /// but we are currently speculating that it will be. - SpeculativelyAvaliable = 2, - /// We are speculating for this block and have used that - /// to speculate for other blocks. - SpeculativelyAvaliableAndUsedForSpeculation = 3, + /// If it would have turned out that the block was, in fact, not fully + /// available, this would have been cleaned up into an Unavailable. + SpeculativelyAvailable = 2, }; /// Return true if we can prove that the value @@ -688,80 +696,117 @@ /// 1) we know the block *is* fully available. /// 2) we do not know whether the block is fully available or not, but we are /// currently speculating that it will be. -/// 3) we are speculating for this block and have used that to speculate for -/// other blocks. static bool IsValueFullyAvailableInBlock( BasicBlock *BB, - DenseMap &FullyAvailableBlocks, - uint32_t RecurseDepth) { - if (RecurseDepth > MaxRecurseDepth) - return false; + DenseMap &FullyAvailableBlocks) { + SmallVector Worklist; + Optional UnavailableBB; - // Optimistically assume that the block is speculatively available and check - // to see if we already know about this block in one lookup. - std::pair::iterator, bool> IV = - FullyAvailableBlocks.insert( - std::make_pair(BB, AvaliabilityState::SpeculativelyAvaliable)); + // The number of times we didn't find an entry for a block in a map and + // optimistically inserted an entry marking block as speculatively avaliable. + unsigned NumNewNewSpeculativelyAvailableBBs = 0; - // If the entry already existed for this block, return the precomputed value. - if (!IV.second) { - // If this is a speculative "available" value, mark it as being used for - // speculation of other blocks. - if (IV.first->second == AvaliabilityState::SpeculativelyAvaliable) - IV.first->second = - AvaliabilityState::SpeculativelyAvaliableAndUsedForSpeculation; - return IV.first->second != AvaliabilityState::Unavaliable; +#ifndef NDEBUG + SmallSet NewSpeculativelyAvailableBBs; + SmallVector AvailableBBs; +#endif + + Worklist.emplace_back(BB); + while (!Worklist.empty()) { + BasicBlock *CurrBB = Worklist.pop_back_val(); // LIFO - depth-first! + // Optimistically assume that the block is Speculatively Available and check + // to see if we already know about this block in one lookup. + std::pair::iterator, bool> IV = + FullyAvailableBlocks.insert( + std::make_pair(CurrBB, AvaliabilityState::SpeculativelyAvailable)); + AvaliabilityState &State = IV.first->second; + + // Did the entry already exist for this block? + if (!IV.second) { + if (State == AvaliabilityState::Unavailable) { + UnavailableBB = CurrBB; + break; // Backpropagate unavaliability info. + } + +#ifndef NDEBUG + AvailableBBs.emplace_back(CurrBB); +#endif + continue; // Don't recurse further, but continue processing worklist. + } + + // No entry found for block. + ++NumNewNewSpeculativelyAvailableBBs; + bool OutOfBudget = NumNewNewSpeculativelyAvailableBBs > MaxBBSpeculations; + + // If we have exhausted our budget, mark this block as unavailable. + // Also, if this block has no predecessors, the value isn't live-in here. + if (OutOfBudget || pred_empty(CurrBB)) { + MaxBBSpeculationCutoffReachedTimes += (int)OutOfBudget; + State = AvaliabilityState::Unavailable; + UnavailableBB = CurrBB; + break; // Backpropagate unavaliability info. + } + + // Tentatively consider this block as speculatively available. +#ifndef NDEBUG + NewSpeculativelyAvailableBBs.insert(CurrBB); +#endif + // And further recurse into block's predecessors, in depth-first order! + Worklist.append(pred_begin(CurrBB), pred_end(CurrBB)); } - // Otherwise, see if it is fully available in all predecessors. - pred_iterator PI = pred_begin(BB), PE = pred_end(BB); +#if LLVM_ENABLE_STATS + IsValueFullyAvailableInBlockNumSpeculationsMax.updateMax( + NumNewNewSpeculativelyAvailableBBs); +#endif - // If this block has no predecessors, it isn't live-in here. - if (PI == PE) - goto SpeculationFailure; + // If the block isn't marked as fixpoint yet, do so and enqueue successors + auto MarkAsFixpointAndEnqueueSuccessors = + [&](BasicBlock *BB, AvaliabilityState FixpointState) { + auto It = FullyAvailableBlocks.find(BB); + if (It == FullyAvailableBlocks.end()) + return; // Never queried this block, leave as-is. + switch (AvaliabilityState &State = It->second) { + case AvaliabilityState::Unavailable: + case AvaliabilityState::Available: + return; // Don't backpropagate further, continue processing worklist. + case AvaliabilityState::SpeculativelyAvailable: // Fix it! + State = FixpointState; +#ifndef NDEBUG + assert(NewSpeculativelyAvailableBBs.erase(BB) && + "Found a speculatively available successor leftover?"); +#endif + // *DO* backpropagate further, continue processing worklist. + Worklist.append(succ_begin(BB), succ_end(BB)); + return; + } + }; - for (; PI != PE; ++PI) - // If the value isn't fully available in one of our predecessors, then it - // isn't fully available in this block either. Undo our previous - // optimistic assumption and bail out. - if (!IsValueFullyAvailableInBlock(*PI, FullyAvailableBlocks,RecurseDepth+1)) - goto SpeculationFailure; - - return true; - -// If we get here, we found out that this is not, after -// all, a fully-available block. We have a problem if we speculated on this and -// used the speculation to mark other blocks as available. -SpeculationFailure: - AvaliabilityState &BBVal = FullyAvailableBlocks[BB]; - - // If we didn't speculate on this, just return with it set to unavaliable. - if (BBVal == AvaliabilityState::SpeculativelyAvaliable) { - BBVal = AvaliabilityState::Unavaliable; - return false; + if (UnavailableBB) { + // Okay, we have encountered an unavailable block. + // Mark speculatively available blocks reachable from UnavailableBB as + // unavailable as well. Paths are terminated when they reach blocks not in + // FullyAvailableBlocks or they are not marked as speculatively available. + Worklist.clear(); + Worklist.append(succ_begin(*UnavailableBB), succ_end(*UnavailableBB)); + while (!Worklist.empty()) + MarkAsFixpointAndEnqueueSuccessors(Worklist.pop_back_val(), + AvaliabilityState::Unavailable); } - // If we did speculate on this value, we could have blocks set to - // speculatively avaliable that are incorrect. Walk the (transitive) - // successors of this block and mark them as unavaliable instead. - SmallVector BBWorklist; - BBWorklist.push_back(BB); +#ifndef NDEBUG + Worklist.clear(); + for (BasicBlock *AvailableBB : AvailableBBs) + Worklist.append(succ_begin(AvailableBB), succ_end(AvailableBB)); + while (!Worklist.empty()) + MarkAsFixpointAndEnqueueSuccessors(Worklist.pop_back_val(), + AvaliabilityState::Available); - do { - BasicBlock *Entry = BBWorklist.pop_back_val(); - // Note that this sets blocks to unavailable if they happen to not - // already be in FullyAvailableBlocks. This is safe. - AvaliabilityState &EntryVal = FullyAvailableBlocks[Entry]; - if (EntryVal == AvaliabilityState::Unavaliable) - continue; // Already unavailable. + assert(NewSpeculativelyAvailableBBs.empty() && + "Must have fixed all the new speculatively available blocks."); +#endif - // Mark as unavailable. - EntryVal = AvaliabilityState::Unavaliable; - - BBWorklist.append(succ_begin(Entry), succ_end(Entry)); - } while (!BBWorklist.empty()); - - return false; + return !UnavailableBB; } /// Given a set of loads specified by ValuesPerBlock, @@ -1126,9 +1171,9 @@ MapVector PredLoads; DenseMap FullyAvailableBlocks; for (const AvailableValueInBlock &AV : ValuesPerBlock) - FullyAvailableBlocks[AV.BB] = AvaliabilityState::Avaliable; + FullyAvailableBlocks[AV.BB] = AvaliabilityState::Available; for (BasicBlock *UnavailableBB : UnavailableBlocks) - FullyAvailableBlocks[UnavailableBB] = AvaliabilityState::Unavaliable; + FullyAvailableBlocks[UnavailableBB] = AvaliabilityState::Unavailable; SmallVector CriticalEdgePred; for (BasicBlock *Pred : predecessors(LoadBB)) { @@ -1141,7 +1186,7 @@ return false; } - if (IsValueFullyAvailableInBlock(Pred, FullyAvailableBlocks, 0)) { + if (IsValueFullyAvailableInBlock(Pred, FullyAvailableBlocks)) { continue; } diff --git a/llvm/test/Transforms/GVN/loadpre-missed-opportunity.ll b/llvm/test/Transforms/GVN/loadpre-missed-opportunity.ll --- a/llvm/test/Transforms/GVN/loadpre-missed-opportunity.ll +++ b/llvm/test/Transforms/GVN/loadpre-missed-opportunity.ll @@ -9,14 +9,17 @@ define dso_local void @_Z2axv(i32** %arg, i1 %arg1, i1 %arg2, i1 %arg3) local_unnamed_addr { ; CHECK-LABEL: @_Z2axv( ; CHECK-NEXT: bb: +; CHECK-NEXT: [[I:%.*]] = load i32*, i32** [[ARG:%.*]], align 8 ; CHECK-NEXT: br label [[BB9:%.*]] ; CHECK: bb6: +; CHECK-NEXT: [[I7:%.*]] = phi i32* [ [[I7_PRE:%.*]], [[BB15:%.*]] ], [ [[I71:%.*]], [[BB9]] ] ; CHECK-NEXT: br label [[BB9]] ; CHECK: bb9: -; CHECK-NEXT: br i1 [[ARG1:%.*]], label [[BB6:%.*]], label [[BB10:%.*]] +; CHECK-NEXT: [[I71]] = phi i32* [ [[I7]], [[BB6:%.*]] ], [ [[I]], [[BB:%.*]] ] +; CHECK-NEXT: br i1 [[ARG1:%.*]], label [[BB6]], label [[BB10:%.*]] ; CHECK: bb10: ; CHECK-NEXT: [[I11:%.*]] = tail call i32* @zzz() -; CHECK-NEXT: br i1 [[ARG2:%.*]], label [[BB12:%.*]], label [[BB15:%.*]] +; CHECK-NEXT: br i1 [[ARG2:%.*]], label [[BB12:%.*]], label [[BB15]] ; CHECK: bb12: ; CHECK-NEXT: br label [[BB13:%.*]] ; CHECK: bb13: @@ -24,6 +27,7 @@ ; CHECK: bb14: ; CHECK-NEXT: br label [[BB15]] ; CHECK: bb15: +; CHECK-NEXT: [[I7_PRE]] = load i32*, i32** [[ARG]], align 8 ; CHECK-NEXT: br label [[BB6]] ; bb: