Differential D34135
[JumpThreading] Use DT to avoid processing dead blocks Authored by uabelho on Jun 13 2017, 1:19 AM.
Details This fixes PR33357 where LVI recursed infinitely when used on dead blocks. Now instead of the previous simple check where we just deemed a block dead
Diff Detail Event TimelineComment Actions I don't know this code at all, but the change at least seems to solve PR33357. Opinions?
Comment Actions Is there a reason the caller can't avoid making calls on unreachable blocks?
Comment Actions I can only refer to what Eli said in the PR: "The alternative is that specifically disallow calling into LazyValueInfo on dead code... but it would be much harder to handle in JumpThreading given the way the pass works." (Myself I don't know JumpThreading and I don't know LazyValueInfo.) Comment Actions I would like to understand more about this from Eli. The problem is that: It happens that LVI is not optimal, fixpointing, etc. But at the same time, if you let jumpthreading ask LVI about unbounded craziness, you are now condemning everything LVI ever uses (simplifiers, other analysis) to try to handle it as well. Which is not really going to happen, it's just going to cause more bugs over time :P If the issue in JumpThreading is determining reachability at all times, that we can solve in the next few weeks with the dynamic dominators stuff (it will always, at all times, have correct reachability from entry block, as long as you tell it what edges you changed) Comment Actions
Yes, that's the primary issue. If we had some cheap way to make JumpThreading avoid visiting unreachable blocks, that would be fine. JumpThreading already has code to kill off unreachable blocks, but it only runs once per iteration of the pass (because it takes O(N) time, where N is the number of CFG edges in the function). If the dynamic DomTree work solves that, that fine, but I'm not sure it makes sense to block this patch indefinitely on that. Comment Actions Can't you just tell LVI the blocks are dead without them being dead?
FWIW: I expect that code to start being submitted in the next week :P Comment Actions (and to be clear, if you want to hack LVI a bit, i don't think it's the worst thing in the world compared to how LVI already is, just wanted to make sure we at least explored the options) Comment Actions
I'm not following your question. The sequence here is that we constant-fold a terminator (deleting an edge), then continue iterating through all the blocks in the function, and eventually crash when LVI discovers a cycle in a loop which was made unreachable. Which blocks is JumpThreading supposed to tell LVI about? Comment Actions Sorry, yes, my question didn't make sense. I also stared at the unreachable code removal (which as you say, is O(cfg edges)). Sigh, oh well. Comment Actions So, the main problem here is that in each iteration of Jump threading, we can find the trivially dead blocks, but not the complete set of unreachable blocks. Also, I'm assuming transitively detecting dead blocks after the call to processBlock does not help in this case? Comment Actions The set of blocks it will find will depend on input order of basic blocks currently. The "detection of dead blocks" is really a quick DCE algorithm that walks the actual instructions of blocks, etc. So repeated transitive detection would be kind of a band-aid. It may even be made to work. Comment Actions Agreed. Also, there was even a discussion on changing the ordering for JumpThreading because of how the current ordering can cause certain blocks to be dead, and AA chokes on the PHIs in those blocks: https://bugs.llvm.org/show_bug.cgi?id=33142#c14 Comment Actions This is pretty much what i'm afraid of - patching around this won't fix the fact that it uses a bunch of analysis, and will likely use more over time. Comment Actions Yes. As the person who did the analysis on that bug I decided to not go that direction (i.e. use a stack worklist) because I wasn't able to prove myself it was correct. i.e. IMHO the long term solution is to rewrite JT but nobody seems to have the bandwidth to do it for now. Comment Actions Great discussion guys! So if I try to summarize:
Did I get it right? Another question: My choice of "overdefined" was simply because there existed a LVILatticeVal::getOverdefined() Comment Actions Ping! Any more comments on this? What about "overdefined" vs "undefined"? Anyone wants to accept it or should we let it be broken? Comment Actions Update: https://reviews.llvm.org/rL314435 has now landed, so we can use domtree to detect dead blocks. Comment Actions I saw it was reverted in r314589 but if it makes it into tree again, will that then mean that we can pred_empty(BB) in JumpThreadingPass::ProcessBlock and JumpThreadingPass::runImpl with !DT->isReachableFromEntry(BB) and problem is solved? Comment Actions
Hello @uabelho , I am working to re-submit the patch. I have already fixed the assert reported by @eli.friedman . I am working to enable preservation under flag at the request of @mzolotukhin . I hope to have it re-submitted this week for review. Comment Actions Ok, so now when Can we replace the "trivially dead" checks pred_empty(BB) in JumpThreadingPass::ProcessBlock and JumpThreadingPass::runImpl with !DT->isReachableFromEntry(BB) and problem is solved? Do we need something more to preserve DT while JumpThreading is running so we can use it? Hopefully something that isn't very costly? If someone explains how it can be used I'll try to find the time to update the patch. Comment Actions
Hi @uabelho, in order to actually use the DT you have to perform a flush on DDT like so: DominatorTree *DT = DDT->flush(); !DT->isReachableFromEntry(BB); ... This flush() call should only happen when you're absolutely sure you need the DT because it's potentially expensive. But the whole point of the deferred nature is to flush when you need it, and in this case you need it.
I haven't tested flushing() in arbitrary locations in the code. It should just work but it might cause an assert inside DT. If you see one let me know, I'd be interested to understand why. Comment Actions Great, I'll try this out then.
Ok, I'll let you know if I find something odd. Thanks! Comment Actions I've done something like this in ProcessBlock which prevents LVI from crashing anymore. In JumpThreadingPass::runImpl then there is also this code that I haven't done anything with: while (ProcessBlock(BB))
Changed = true;
++I;
// Don't thread branches over a block that's slated for deletion.
if (DDT->pendingDeletedBB(BB))
continue;
// If the block is trivially dead, zap it. This eliminates the successor
// edges which simplifies the CFG.
if (pred_empty(BB) &&
BB != &BB->getParent()->getEntryBlock()) {
DEBUG(dbgs() << " JT: Deleting dead block '" << BB->getName()
<< "' with terminator: " << *BB->getTerminator() << '\n');
LoopHeaders.erase(BB);
LVI->eraseBlock(BB);
DeleteDeadBlock(BB, DDT);
Changed = true;
continue;
}Should we use DT here as well in some way? I did a quick attempt changing the pred_empty(BB) stuff above Or should we add if (!DDT->flush().isReachableFromEntry(BB)) continue; ? Comment Actions Hi @uabelho.
Doing this outside of ProcessBlock is preferred. The Jumpthreading pass is very expensive in that it iterates over F until no changes are made and every iteration of F it iterates multiple times over every BB until each block stabilizes. If there is a way to gate the flush() with a simple check I recommend doing so too. Comment Actions Added inline comment.
Comment Actions
Comment Actions I've just submitted https://llvm.org/PR36133 containing a testcase that show how JumpThreadings miscompiles (without crashes) the code due to DomTree not being updated between the iterations of JumpThreading itself. I think the miscompilation is worse than a crash so it might be possible to pay the increase in compile time to avoid it. Or maybe someone has a better mitigation? Comment Actions Err, looking at that bug, it looks like it occurs in release versions before the dominance update patch was ever submitted :) Past that, the right way to go about this is actually figure out at what point and conditions it needs to be updated and do it there . Use the smallest hammer, not the biggest one Comment Actions I think PR36133 could be considered a different issue. LVI currently uses a domtree for certain queries involving llvm.assume; to make that work, the domtree would have to be up-to-date every time we call into LVI. But we could solve that separately from the problem of dead code in LVI. Comment Actions Or it needs to know that it must flush updates before using it (not sure how incestuous you want to make this. This would basically be making LazyDomTree that flushes the deferred updater when you called dominates on it :P) Comment Actions (also, the DT was not updated at all prior during JT prior to all of these patches, so i guess it all worked because LVI didn't use DT when called from JumpThreading or something)? Comment Actions I've created D42717 in response to PR 36133. As to your assumption I believe you are correct. LVI will perform more expensive checks if DT isn't available and I think that's what happened in the past. I'm still confused why I see the same regression for the addition of AA to JumpThreading last March but I'm more concerned about making tip not miscompile. Comment Actions I have a patch (that relies on my fix from D42717) to also fix this issue with little additional overhead. Because we must flush all pending DT transactions before using LVI analysis we can also check if the block is unreachable from entry. If that's the case we can immediately pessimize threads across the block. Here's the patch along with a modified version of D42717: diff --git a/llvm/lib/Transforms/Scalar/JumpThreading.cpp b/llvm/lib/Transforms/Scalar/JumpThreading.cpp index 87a1d5e487e..51c9923ff83 100644 --- a/llvm/lib/Transforms/Scalar/JumpThreading.cpp +++ b/llvm/lib/Transforms/Scalar/JumpThreading.cpp @@ -617,6 +617,10 @@ bool JumpThreadingPass::ComputeValueKnownInPredecessors( // "X < 4" and "X < 3" is known true but "X < 4" itself is not available. // Perhaps getConstantOnEdge should be smart enough to do this? + auto &DT = + DDT->flush(); // LVI analysis relies on an up-to-date DominatorTree. + if (!DT.isReachableFromEntry(BB)) + return false; // Don't jumpthread blocks that will soon be dead. for (BasicBlock *P : predecessors(BB)) { // If the value is known by LazyValueInfo to be a constant in a // predecessor, use that information to try to thread this block. @@ -630,6 +634,10 @@ bool JumpThreadingPass::ComputeValueKnownInPredecessors( /// If I is a PHI node, then we know the incoming values for any constants. if (PHINode *PN = dyn_cast<PHINode>(I)) { + auto &DT = + DDT->flush(); // LVI analysis relies on an up-to-date DominatorTree. + if (!DT.isReachableFromEntry(BB)) + return false; // Don't jumpthread blocks that will soon be dead. for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { Value *InVal = PN->getIncomingValue(i); if (Constant *KC = getKnownConstant(InVal, Preference)) { @@ -769,6 +777,10 @@ bool JumpThreadingPass::ComputeValueKnownInPredecessors( if (!isa<Constant>(RHS)) continue; + auto &DT = DDT->flush(); // LVI analysis relies on an up-to-date + // DominatorTree. + if (!DT.isReachableFromEntry(BB)) + return false; // Don't jumpthread blocks that will soon be dead. LazyValueInfo::Tristate ResT = LVI->getPredicateOnEdge(Pred, LHS, cast<Constant>(RHS), PredBB, BB, @@ -792,6 +804,10 @@ bool JumpThreadingPass::ComputeValueKnownInPredecessors( if (!isa<Instruction>(CmpLHS) || cast<Instruction>(CmpLHS)->getParent() != BB) { + auto &DT = + DDT->flush(); // LVI analysis relies on an up-to-date DominatorTree. + if (!DT.isReachableFromEntry(BB)) + return false; // Don't jumpthread blocks that will soon be dead. for (BasicBlock *P : predecessors(BB)) { // If the value is known by LazyValueInfo to be a constant in a // predecessor, use that information to try to thread this block. @@ -820,6 +836,10 @@ bool JumpThreadingPass::ComputeValueKnownInPredecessors( match(CmpLHS, m_Add(m_Value(AddLHS), m_ConstantInt(AddConst)))) { if (!isa<Instruction>(AddLHS) || cast<Instruction>(AddLHS)->getParent() != BB) { + auto &DT = DDT->flush(); // LVI analysis relies on an up-to-date + // DominatorTree. + if (!DT.isReachableFromEntry(BB)) + return false; // Don't jumpthread blocks that will soon be dead. for (BasicBlock *P : predecessors(BB)) { // If the value is known by LazyValueInfo to be a ConstantRange in // a predecessor, use that information to try to thread this @@ -900,6 +920,10 @@ bool JumpThreadingPass::ComputeValueKnownInPredecessors( } } + auto &DT = + DDT->flush(); // LVI analysis relies on an up-to-date DominatorTree. + if (!DT.isReachableFromEntry(BB)) + return false; // Don't jumpthread blocks that will soon be dead. // If all else fails, see if LVI can figure out a constant value for us. Constant *CI = LVI->getConstant(V, BB, CxtI); if (Constant *KC = getKnownConstant(CI, Preference)) { @@ -1101,7 +1125,10 @@ bool JumpThreadingPass::ProcessBlock(BasicBlock *BB) { // unconditional. Because its no longer interesting as far as jump // threading is concerned. assert(CondBr->isConditional() && "Threading on unconditional terminator"); - + auto &DT = + DDT->flush(); // LVI analysis relies on an up-to-date DominatorTree. + if (!DT.isReachableFromEntry(BB)) + return false; // Don't jumpthread blocks that will soon be dead. LazyValueInfo::Tristate Ret = LVI->getPredicateAt(CondCmp->getPredicate(), CondCmp->getOperand(0), CondConst, CondBr); @@ -2371,6 +2398,10 @@ bool JumpThreadingPass::TryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB) { // Now check if one of the select values would allow us to constant fold the // terminator in BB. We don't do the transform if both sides fold, those // cases will be threaded in any case. + auto &DT = + DDT->flush(); // LVI analysis relies on an up-to-date DominatorTree. + if (!DT.isReachableFromEntry(BB)) + return false; // Don't jumpthread blocks that will soon be dead. LazyValueInfo::Tristate LHSFolds = LVI->getPredicateOnEdge(CondCmp->getPredicate(), SI->getOperand(1), CondRHS, Pred, BB, CondCmp); I have verified it does not crash on PR33357-lvi-recursion.ll, passes check-all and test-suite runs. Comment Actions I have analyzed this failure and have what I believe (in @dberlin 's words) to be the smallest hammer fix: $ git diff lib/Analysis/LazyValueInfo.cpp diff --git a/llvm/lib/Analysis/LazyValueInfo.cpp b/llvm/lib/Analysis/LazyValueInfo.cpp index 65fd007dc0b..36e66f7f6ef 100644 --- a/llvm/lib/Analysis/LazyValueInfo.cpp +++ b/llvm/lib/Analysis/LazyValueInfo.cpp @@ -1145,9 +1145,17 @@ getValueFromConditionImpl(Value *Val, Value *Cond, bool isTrueDest, (!isTrueDest && BO->getOpcode() != BinaryOperator::Or)) return ValueLatticeElement::getOverdefined(); - auto RHS = getValueFromCondition(Val, BO->getOperand(0), isTrueDest, Visited); - auto LHS = getValueFromCondition(Val, BO->getOperand(1), isTrueDest, Visited); - return intersect(RHS, LHS); + // Prevent infinite recursion if Cond references itself as in this example: + // Cond: "%tmp4 = and i1 %tmp4, undef" + // BL: "%tmp4 = and i1 %tmp4, undef" + // BR: "i1 undef" + Value *BL = BO->getOperand(0); + Value *BR = BO->getOperand(1); + if (BL == Cond || BR == Cond) + return ValueLatticeElement::getOverdefined(); + + return intersect(getValueFromCondition(Val, BL, isTrueDest, Visited), + getValueFromCondition(Val, BR, isTrueDest, Visited)); } The infinite recursion happens because Visited is not altered or updated until getValueFromConditionImpl() returns a value. In this case getValueFromConditionImpl() calls getValueFromCondition() which calls back to getValueFromConditionImpl() in an attempt to resolve the LHS and RHS of a valid BinaryOperator. In our case this specific instruction we have %tmp4 = and i1 %tmp4, undef which I don't quite understand. Shouldn't this be invalid SSA form? This patch passes ninja check-all and test-suite builds on x86_64. @uabelho , the test case needs one small change to the FileCheck verification block: ; The
; br i1 undef, label %bb6, label %bb1
; is replaced by
; br label %bb6
; and the rest of the function is unreachable from entry and jump-threading
; shouldn't even ask LazyValueInfo about things in the dead blocks.
; CHECK: define void @f(i32 %p1) {
; CHECK-NEXT: bb6:
; CHECK-NEXT: ret voidFor whatever reason JumpThreading now removes %0 = icmp eq i32 %p1, 0 from bb6:. Comment Actions Gentle ping. Are there any objections to this patch? Should I open another Differential for this patch in preparation to commiting it? Comment Actions I'm a little worried about the duplicated code here. I feel like you are having to patch way too many points in the same function, and it will be easy to miss one in the future if someone changes the logicc slightly. Is there really no better place to put this/way to refactor it? If not, i'll approve, but just wanted to check. Comment Actions Hi @dberlin, thank you for the comment. I'm a bit confused by your remarks however. I suspect you may be confusing my older suggested patch with my newer one. The older patch won't work as it requires far too many flushes of DDT. And I agree, it's also too brittle. Here is my most recent patch I believe to properly address the LVI infinite recursion: $ git diff lib/Analysis/LazyValueInfo.cpp diff --git a/llvm/lib/Analysis/LazyValueInfo.cpp b/llvm/lib/Analysis/LazyValueInfo.cpp index 65fd007dc0b..36e66f7f6ef 100644 --- a/llvm/lib/Analysis/LazyValueInfo.cpp +++ b/llvm/lib/Analysis/LazyValueInfo.cpp @@ -1145,9 +1145,17 @@ getValueFromConditionImpl(Value *Val, Value *Cond, bool isTrueDest, (!isTrueDest && BO->getOpcode() != BinaryOperator::Or)) return ValueLatticeElement::getOverdefined(); - auto RHS = getValueFromCondition(Val, BO->getOperand(0), isTrueDest, Visited); - auto LHS = getValueFromCondition(Val, BO->getOperand(1), isTrueDest, Visited); - return intersect(RHS, LHS); + // Prevent infinite recursion if Cond references itself as in this example: + // Cond: "%tmp4 = and i1 %tmp4, undef" + // BL: "%tmp4 = and i1 %tmp4, undef" + // BR: "i1 undef" + Value *BL = BO->getOperand(0); + Value *BR = BO->getOperand(1); + if (BL == Cond || BR == Cond) + return ValueLatticeElement::getOverdefined(); + + return intersect(getValueFromCondition(Val, BL, isTrueDest, Visited), + getValueFromCondition(Val, BR, isTrueDest, Visited)); } | ||||||||||||||||||
I do not think this will be accepted by the community. The performance implications are non-trivial (around 1-4%) when this is called on almost every basic block. It's the primary reason I had to write the DeferredDominance class.