Page MenuHomePhabricator

[StaticAnalyzer] LoopUnrolling: Track a LoopStack in order to completely unroll specific loops
ClosedPublic

Authored by szepet on Jul 20 2017, 7:55 AM.

Details

Summary

The LoopExit CFG information provides the opportunity to not mark the loops but having a stack which tracks if a loop is unrolled or not. So in case of simulating a loop we just add it and the information if it meets the requirements to be unrolled to the top of the stack.

Diff Detail

Repository
rL LLVM

Event Timeline

szepet created this revision.Jul 20 2017, 7:55 AM
szepet updated this revision to Diff 108337.Jul 26 2017, 11:51 AM

Update to fit to the trunk.
All tests passed. Only marking loops as unrolled (1) and not unrolled (0). Keep track of 2 stack in the ProgramState (1 for the loopstmt, 1 for the mark if its unrolled or not).

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

Woohoo, looks much nicer and cleaner :3

lib/StaticAnalyzer/Core/LoopUnrolling.cpp
10–12 ↗(On Diff #108337)

This is already getting a bit outdated (we're no longer marking blocks). But generally having these comments is great, we need to make a new one.

30 ↗(On Diff #108337)

Hmm, what was wrong with the regular unsigned int?

142 ↗(On Diff #108337)

Is this the only reason why we need UnrolledLoopStack? How does this interact with possible recursion?

dcoughlin edited edge metadata.Aug 7 2017, 7:11 PM

This looks a lot more clean and is likely to be a lot faster! I think it is really important to document this new functionality. I realize we haven't always done a good job of this, but I'd like to document everything we add to Core so that folks who are new to the project can get up to speed by reading the source code.

include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h
27 ↗(On Diff #108337)

Since these are designed to be exposed to other translation units, I think it would be a good idea to add doxygen comments describing what they do.

lib/StaticAnalyzer/Core/LoopUnrolling.cpp
30 ↗(On Diff #108337)

Can you add comments describing what these program state elements track? This will help future maintainers understand their purpose.

31 ↗(On Diff #108337)

Also, it would be good to add a TODO indicating that the unrolled loop stack should not need to be in the program state since it is lexical in nature. Instead, the stack of loops should be tracked in the location context.

145 ↗(On Diff #108337)

Super tiny nit: Missing space here.

szepet updated this revision to Diff 110985.Aug 14 2017, 8:47 AM
szepet marked 7 inline comments as done.
  • Descriptions updated.
  • The structure of LoopStack made more clear and recursion bug fixed by storing LocationContext.
  • other updates and TODOs added based on comments.
szepet retitled this revision from [StaticAnalyzer] LoopUnrolling: Change the maxVisitOnPath dynamically in order to unroll loops to [StaticAnalyzer] LoopUnrolling: Track a LoopStack in order to completely unroll specific loops.Aug 14 2017, 8:50 AM
szepet edited the summary of this revision. (Show Details)
dcoughlin accepted this revision.Aug 14 2017, 2:22 PM

Looks good to me. I requested an additional comment (sorry for not doing that before!) and I think you need to extend Profile() to handle the LocationContext.

lib/StaticAnalyzer/Core/LoopUnrolling.cpp
35 ↗(On Diff #110985)

I don't see a way around it without additional core work, but it is not ideal that this checker keeps a stack of LoopStates each of which contains a LocationContext (which is itself a stack).

53 ↗(On Diff #110985)

Should the Profile be updated to include the LCtx?

215 ↗(On Diff #110985)

Can you add a comment here stating that updateLoopStack() is called on every basic block and so needs to be fast?

This revision is now accepted and ready to land.Aug 14 2017, 2:22 PM
This revision was automatically updated to reflect the committed changes.