This is an archive of the discontinued LLVM Phabricator instance.

[CFG] Add LoopExit information to CFG

Authored by szepet on Jul 20 2017, 2:34 AM.



This patch introduces a new CFG element CFGLoopExit that indicate when a loop ends. It does not deal with returnStmts yet (left it as a TODO).
It hidden behind a new analyzer-config flag called cfg-loopexit (false by default).
Test cases added.

The main purpose of this patch right know is to make loop unrolling and loop widening easier and more efficient. However, this information can be useful for future improvements in the StaticAnalyzer core too.

Diff Detail


Event Timeline

szepet created this revision.Jul 20 2017, 2:34 AM
szepet updated this revision to Diff 107585.Jul 20 2017, 2:25 PM
szepet added a reviewer: rsmith.

Adding new block when the loop successor is the ExitBlock.
Test cases updated.

szepet updated this revision to Diff 108297.Jul 26 2017, 9:05 AM

Updated test cases to fit on trunk.

szepet updated this revision to Diff 108307.Jul 26 2017, 9:38 AM

Accidentally left debug print removed.

szepet updated this revision to Diff 108309.Jul 26 2017, 9:40 AM

Wrong diff updated last time, fixed it.

NoQ edited edge metadata.Jul 27 2017, 5:17 AM

CFG construction tests seem to have accidentally disappeared from the recent revisions.

581–583 ↗(On Diff #108309)

Can these two actually be call sites, ever? If we don't intend that, maybe give them their own llvm_unreachable with a different comment?

szepet updated this revision to Diff 108568.Jul 27 2017, 6:55 PM
szepet marked an inline comment as done.

Test file re-added.
CFGElement::LoopExit and LifetimeEnds separated into their own caseStmt.

szepet added inline comments.Jul 27 2017, 6:57 PM
581–583 ↗(On Diff #108309)

Not sure about the comment string so if you have a better idea or just don't like this one, please let me know!

dcoughlin edited edge metadata.Aug 7 2017, 10:09 PM

This is incomplete, but seems like it is moving in the direction of where we want to ultimately end up. I have some minor comments inline, but otherwise this seems reasonable. I think it is very important to document the new element clearly and indicate that it is currently incomplete and intended only for consumption by the static analyzer.

173 ↗(On Diff #108568)

Can you add a comment indicating that this is only produced when the cfg-loopexit analyzer config flag is true and also say that it is only produced when building the CFG for the static analyzer. This way other consumers of the CFG will know they don't need to handle it.

It would also be good to document that a loop exit element can be reached even when the loop body was never entered. Please add a test for while (false) { ... }.

750 ↗(On Diff #108568)

Can you add a comment explaining that S should be a looping statement and also change the name from S to something more evocative. This will make it more clear how the method is intended to be called.

605 ↗(On Diff #108568)

The '*' here doesn't match the style of the surrounding code.

656 ↗(On Diff #108568)

Can you rename 'S' to something more evocative ('LoopStmt', perhaps).

1263 ↗(On Diff #108568)

You should also mention 'throw' and 'goto'. Do you handle 'break' correctly? If so, please add tests. If not, add it to this list of unhandled constructs in this comment.

And (super nit) add a space before "TODO".

szepet updated this revision to Diff 110980.Aug 14 2017, 8:35 AM
szepet marked 5 inline comments as done.

Updates based on comments.

dcoughlin accepted this revision.Aug 14 2017, 11:06 AM

Looks good to me me. Thanks!

This revision is now accepted and ready to land.Aug 14 2017, 11:06 AM
This revision was automatically updated to reflect the committed changes.