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 @@ -104,11 +104,6 @@ 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)")); @@ -674,10 +669,9 @@ Avaliable = 1, /// We do not know whether the block is fully available or not, /// but we are currently speculating that it will be. + /// If it would have turned out that the block was, in fact, not fully + /// avaliable, this would have been cleaned up into an Unavaliable. SpeculativelyAvaliable = 2, - /// We are speculating for this block and have used that - /// to speculate for other blocks. - SpeculativelyAvaliableAndUsedForSpeculation = 3, }; /// Return true if we can prove that the value @@ -688,80 +682,101 @@ /// 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; + BasicBlock *RootBB, + DenseMap &FixpointBlocks) { + SmallVector Worklist; + Optional UnavaliableBB; - // 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)); +#ifndef NDEBUG + SmallSet NewSpeculativelyAvaliableBBs; + SmallVector AvaliableBBs; +#endif - // 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; + Worklist.emplace_back(RootBB); + 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 = + FixpointBlocks.insert( + std::make_pair(CurrBB, AvaliabilityState::SpeculativelyAvaliable)); + AvaliabilityState &State = IV.first->second; + + // Did the entry already exist for this block? + if (!IV.second) { + if (State == AvaliabilityState::Unavaliable) { + UnavaliableBB = CurrBB; + break; // Backpropagate unavaliability info. + } + +#ifndef NDEBUG + AvaliableBBs.emplace_back(CurrBB); +#endif + continue; // Don't recurse further, but continue processing worklist. + } + + // No fixpoint entry found. + + // If this block has no predecessors, the value isn't live-in here. + if (pred_empty(CurrBB)) { + State = AvaliabilityState::Unavaliable; + UnavaliableBB = CurrBB; + break; // Backpropagate unavaliability info. + } + + // Tentatively consider this block as speculatively avaliable. +#ifndef NDEBUG + NewSpeculativelyAvaliableBBs.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 the block isn't marked as fixpoint yet, do so and enqueue successors + auto MarkAsFixpointAndEnqueueSuccessors = + [&](BasicBlock *BB, AvaliabilityState FixpointState) { + auto It = FixpointBlocks.find(BB); + if (It == FixpointBlocks.end()) + return; // Never queried this block, leave as-is. + switch (AvaliabilityState &State = It->second) { + case AvaliabilityState::Unavaliable: + case AvaliabilityState::Avaliable: + return; // Don't backpropagate further, continue processing worklist. + case AvaliabilityState::SpeculativelyAvaliable: // Fix it! + State = FixpointState; +#ifndef NDEBUG + assert(NewSpeculativelyAvaliableBBs.erase(BB) && + "Found a speculatively avaliable successor leftover?"); +#endif + Worklist.append(succ_begin(BB), succ_end(BB)); + return; // *DO* backpropagate further, continue processing worklist. + } + }; - // If this block has no predecessors, it isn't live-in here. - if (PI == PE) - goto SpeculationFailure; - - 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 (UnavaliableBB) { + // Okay, we have encountered an "unavaliable" block. + // Backpropagate that information to the each non-fixpoint successor. + Worklist.clear(); + Worklist.append(succ_begin(*UnavaliableBB), succ_end(*UnavaliableBB)); + while (!Worklist.empty()) + MarkAsFixpointAndEnqueueSuccessors(Worklist.pop_back_val(), + AvaliabilityState::Unavaliable); } - // 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 *AvaliableBB : AvaliableBBs) + Worklist.append(succ_begin(AvaliableBB), succ_end(AvaliableBB)); + while (!Worklist.empty()) + MarkAsFixpointAndEnqueueSuccessors(Worklist.pop_back_val(), + AvaliabilityState::Avaliable); - 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(NewSpeculativelyAvaliableBBs.empty() && + "Must have fixed all the new speculatively avaliable blocks."); +#endif - // Mark as unavailable. - EntryVal = AvaliabilityState::Unavaliable; - - BBWorklist.append(succ_begin(Entry), succ_end(Entry)); - } while (!BBWorklist.empty()); - - return false; + return !UnavaliableBB.hasValue(); } /// Given a set of loads specified by ValuesPerBlock, @@ -1141,7 +1156,7 @@ return false; } - if (IsValueFullyAvailableInBlock(Pred, FullyAvailableBlocks, 0)) { + if (IsValueFullyAvailableInBlock(Pred, FullyAvailableBlocks)) { continue; }