This is an archive of the discontinued LLVM Phabricator instance.

[LICM] Avoid duplicate work during building AliasSetTracker
ClosedPublic

Authored by skatkov on Sep 5 2018, 8:49 PM.

Details

Summary

Currently we re-use cached info from sub loops or traverse them
to populate AliasSetTracker. But after that we traverse all basic blocks
from the current loop. This is redundant work.

All what we need is traversing the all basic blocks from the loop except
those which are used to get the data from the cache.

This should improve compile time only.

Diff Detail

Event Timeline

skatkov created this revision.Sep 5 2018, 8:49 PM
reames added a comment.Sep 6 2018, 4:28 PM

This looks correct to me, but this is so glaringly bad I'd like a second set of eyes to make sure I'm not missing something. Can someone else confirm?

lib/Transforms/Scalar/LICM.cpp
1545

I'm fine with this implementation, but if you wanted, you could structure this one of two ways:

  1. Use a SmallVector<BasicBlock> since the sets of BBs are distinct by assumption.
  2. Keep track of which loops are handle, then check the containing loop for each BB using LoopInfo (it has a map from BB to innermost containing loop).
reames added inline comments.Sep 6 2018, 4:37 PM
lib/Transforms/Scalar/LICM.cpp
1545

Or just inline mergeLoop and restore the check removed by cce6712519 for the parent loop. That's the change which appears to have introduced this compile time regression. :)

Yeah for compile time problems which go unfound for 20 months...

skatkov added inline comments.Sep 6 2018, 6:43 PM
lib/Transforms/Scalar/LICM.cpp
1545
  1. The main operation for HandledBBs we need is to find whether some BB is in this set. I do not think that SmallVector is a good candidate for that.
  2. I do not think it is a right solution. When we go over all basic blocks of the loop L we can take a BB which is a part of inner inner loop (with depth = depth(L) + 2 or more. When we traversed inner loops we considered only immediate sub loops. So if we collect all used sub loops (AllSL) and now we consider BB then it is not enough to check that Loop(BB) is in ALLSL set. We must ensure that some element of ALLSL contains BB. This does not look like a less complexity than just collect all BBs and check whether it is already handled like I did in the patch.
skatkov added inline comments.Sep 6 2018, 7:16 PM
lib/Transforms/Scalar/LICM.cpp
1559

Actually this comment worries me most. What if another loop pass executing in the same LoopPassManager modifies the inner loop in the way that AST is changed?
If it is possible then removing the caching entirely is most safe thing to do probably.

skatkov updated this revision to Diff 164356.Sep 6 2018, 11:25 PM

is it better?

reames accepted this revision.Sep 7 2018, 10:30 AM

Looked at the history in more detail, and decided I'm comfortable with this fix. So, LGTM.

Serguei, the invalidation question is a separate one. Let's see what falls out from this, and then revisit as needed.

This revision is now accepted and ready to land.Sep 7 2018, 10:30 AM
This revision was automatically updated to reflect the committed changes.