This is an archive of the discontinued LLVM Phabricator instance.

SafepointIRVerifier should ignore dead blocks and dead edges
ClosedPublic

Authored by yrouban on May 28 2018, 12:33 AM.

Details

Summary

Not only should SafepointIRVerifier ignore unreachable blocks
(as suggested in https://reviews.llvm.org/D47011) but it also
has to ignore dead blocks.

In @test2 (see the new tests):

  br i1 true, label %right, label %left
left:
  ...
right:
  ...
merge:
  %val = phi i8 addrspace(1)* [ ..., %left ], [ ..., %right ]
  use %val

both left and right branches are reachable.
If they collide then SafepointIRVerifier reports an error.

Because of the foldable branch condition GVN finds the left
branch dead and removes the phi node entry that merges values
from right and left. Then the use comes from the right branch.
This results in no collision.

So, SafepointIRVerifier ends up in different results depending
on either GVN is run or not.

To solve this issue this patch adds Dead Block detection to
SafepointIRVerifier which can ignore dead blocks while
validating IR. The Dead Block detection algorithm is taken
from GVN but modified to not split critical edges. That is
needed to keep CFG unchanged by SafepointIRVerifier.

Diff Detail

Event Timeline

yrouban created this revision.May 28 2018, 12:33 AM
yrouban edited the summary of this revision. (Show Details)May 28 2018, 12:35 AM

I realized that there is a case with a dead edge but without dead blocks. I will improve the patch and add a testcase.

yrouban planned changes to this revision.May 28 2018, 9:11 PM
yrouban updated this revision to Diff 148914.May 29 2018, 8:20 AM
yrouban retitled this revision from SafepointIRVerifier should ignore dead blocks to SafepointIRVerifier should ignore dead blocks and dead edges.

Added test cases with a dead edge but without dead blocks.
Fixed the algorithm to ignore such dead edges.

Please review.

anna added inline comments.May 29 2018, 10:58 AM
lib/IR/SafepointIRVerifier.cpp
381

This seems like a generally useful analysis to have outside of the safepoint IR Verifier. We should think of moving the code into Analysis.

You mentioned it's taken from the GVN but modified to avoid splitting the critical edges. Could you please state that as a comment here: modified version from GVN::addDeadBlock.

421

comment here that block maybe already dead if it's dominated by NewDead blocks processed earlier.

441

Change to assert instead of check.

yrouban updated this revision to Diff 149405.Jun 1 2018, 12:51 AM

Addressed Anna's comments: extracted a separate analysis pass called CFG Deadness.

DaniilSuchkov added inline comments.Jun 1 2018, 2:03 AM
include/llvm/IR/CFGDeadness.h
47 ↗(On Diff #149405)

Please add a comment that explains what kind of uses this method expects, it isn't obvious.

50 ↗(On Diff #149405)

Could you please add here an assertion that U->getUser() is block terminator?

lib/IR/CFGDeadness.cpp
87 ↗(On Diff #149405)

As Anna said before, this should be an assertion.

yrouban updated this revision to Diff 149770.Jun 4 2018, 7:57 AM

Added dead edge definition and appropriate assertions to the method isDeadEdge().
Inlined the method processFoldableCondBr() into processInstruction().

Please review the patch.
Anna, Daniil, you are the best candidates for reviewing the patch.

This revision is now accepted and ready to land.Jun 5 2018, 5:07 AM
anna added a comment.Jun 5 2018, 12:07 PM

Hi Yevgeny, this looks close to commit. Comments inline.

lib/IR/CFGDeadness.cpp
127 ↗(On Diff #149770)

I think the assert and the corresponding ifdef compilation with break isn't very useful. It's just testing a property of the IRVerifier for phi nodes.
Also, conditional compilation with behaviour change is not very preferable. Could we get rid of this?

160 ↗(On Diff #149770)

it doesn't modify CFG, so the cfg arg should be false.

163 ↗(On Diff #149770)

ditto here.

yrouban marked 4 inline comments as done.Jun 5 2018, 10:11 PM
yrouban added inline comments.
lib/IR/CFGDeadness.cpp
127 ↗(On Diff #149770)

In debug mode these two assertions (1) and (2) check that for this phi node and the specified basic block there is at leats one edge (2) and no more than one edge (1). To check (1) we need to iterate through the whole set of predecessors, that is why we should not break at the first found edge. Any other way to express this more elegantly?
This assertion seems obvious, but I did not find a place in LLVM (other than the LL parser) that prevents phis with duplicate pairs like phi [%value1, %block1], [%value1, %block1]. In this case, how many incoming edges do we have, 1 or 2?

160 ↗(On Diff #149770)

Hm, it is not obvious from the sources.
But why DominatorTreeWrapperPass has its set to true then?

INITIALIZE_PASS(DominatorTreeWrapperPass, "domtree", "Dominator Tree Construction", true, true)
anna added inline comments.Jun 7 2018, 8:28 AM
lib/IR/CFGDeadness.cpp
127 ↗(On Diff #149770)

Yes, I got what you were doing :)
I incorrectly thought this exact case is handled in the IR verifier (i.e. it fails with dup blocks), so we don't need to do this here. But this is infact valid IR (having duplicate pairs will be 2 edges, i.e. 2 preds for that basic block).
So, now that I think of it since the verifier allows it, the IR is valid - so why should we have this assert in the first place?

anna added inline comments.Jun 7 2018, 8:31 AM
lib/IR/CFGDeadness.cpp
160 ↗(On Diff #149770)

not sure about the dom tree case - might be a bug, but pretty much all other analysis pass have the CFG arg as false, because, we don't modify the CFG (and I believe that's true in this pass as well, right?).

yrouban marked an inline comment as done.Jun 7 2018, 8:22 PM
yrouban updated this revision to Diff 150605.Jun 8 2018, 10:00 PM

Addressed Anna's comments:

  1. changed INITIALIZE_PASS CFGDeadness CFG flag to false.
  2. The new method CFGDeadness::hasLiveIncomingEdge(Phi, Block) replaces CFGDeadness::getIncomingEdge(Phi, Block) that could not work with phi containing duplicate pairs of (value,block).

Can you describe what is the difference you observe in the verifier behavior with and without simplifications before? There will always be cases when some simplifications before the verifier change the CFG. You won't be able to handle everything in this analysis.

lib/IR/CFGDeadness.cpp
115–116 ↗(On Diff #150605)

You only look at branches in processInstruction, right? You don't need to iterate all instructions then, just check the terminator of the BB.

yrouban updated this revision to Diff 150620.Jun 9 2018, 4:59 AM

Removed CFGDeadness::processInstruction() and changed to iterate over the block terminators.

yrouban updated this revision to Diff 150621.Jun 9 2018, 5:04 AM

previous diff was incorrect, please ignore it.
In this diff I removed CFGDeadness::processInstruction() and changed to iterate over the block terminators.

apilipenko added inline comments.Jun 14 2018, 3:07 AM
lib/IR/SafepointIRVerifier.cpp
381

@anna, I think this is not of much use outside of SafepointIRVerifier. Most passes don't need to worry about this patterns as it's reasonable to expect simplifycfg to have cleaned things up.

Verifiers is a different story as you don't want you verification logic depend on the optimizations performed on the code. You also don't want to modify the code to clean up the mess.

I would suggest keeping this logic in SafepointIRVerifier. If we want to extract it as a separate analysis I'd suggest making a clear comment that it has very specific purpose.

anna added inline comments.Jun 14 2018, 7:13 AM
lib/IR/SafepointIRVerifier.cpp
381

There's one specific use for this pass outside of the SafepointIRVerifier and that's for loopSimplifyCFG - we cannot rely on SimplifyCFG to cleanup dead/unreachable blocks that are dead *because* of LoopSimplifyCFG. So, I suspect this will be useful for loop optimizations that are run as a group in a pipeline without the need for a function pass like SimplifyCFG.

Perhaps we can add a clear comment stating where it's usage is expected and that right now it's used in the SafepointIRVerifier.

anna added a comment.Jun 14 2018, 7:33 AM

Generally LGTM. pls wait for Artur's comments (if any).

apilipenko accepted this revision.Jun 18 2018, 3:04 AM
apilipenko added inline comments.
lib/IR/CFGDeadness.cpp
12 ↗(On Diff #150621)

I don't think that GVN reference is important here. It just happened to be the detail of the current implementation. I think the higher level interface/comment should be that the analysis tracks trivially dead edges without modifying the CFG.

Could you please add a comment that in most cases passes rely on SimplifyCFG to clean up such blocks, but in some cases, like verification or loop passes it's not possible.

lib/IR/SafepointIRVerifier.cpp
381

Makes sense.

yrouban updated this revision to Diff 151703.Jun 18 2018, 6:30 AM
yrouban marked 2 inline comments as done.

Added Artur's comment.

LLVM committers, this patch seems to be ready for landing, please.

yrouban updated this revision to Diff 152439.Jun 22 2018, 1:55 AM

Removed a separate analysis pass - CFGDeadness is made internal.

anna accepted this revision.Jun 22 2018, 10:10 AM

LGTM. Artur, could you please land the patch? My llvm repo seems to be having issues. Thanks.

This revision was automatically updated to reflect the committed changes.

Spasibo, Artur.