This is an archive of the discontinued LLVM Phabricator instance.

[PM/Unswitch] Teach the new simple loop unswitch to handle loop invariant PHI inputs and to rewrite PHI nodes during the actual unswitching.
ClosedPublic

Authored by chandlerc on May 1 2017, 3:59 AM.

Details

Summary

The checking is quite easy, but rewriting the PHI nodes is somewhat
surprisingly challenging. This should handle both branches and switches.

I think this is now a full featured trivial unswitcher, and more full
featured than the trivial cases in the old pass while still being (IMO)
somewhat simpler in how it works.

Next up is to verify its correctness in more widespread testing, and
then to add non-trivial unswitching.

Event Timeline

chandlerc created this revision.May 1 2017, 3:59 AM
sanjoy accepted this revision.May 6 2017, 3:39 PM

lgtm

I have some minor comments, but they're of the form "if *I* wrote this, this is what I'd do", and don't necessarily need to be addressed.

lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
58

JFYI: clang format is needed here too.

142

Make this static? Same for rewritePHINodesForUnswitchedExitBlock and rewritePHINodesForExitAndUnswitchedBlocks.

I'd also call this areLoopExitPHIsLoopInvariant, since nothing in this is specific to lcssa PHIs.

165

I'd have used a slightly different interface. Instead of rewritePHINodesForUnswitchedExitBlock and rewritePHINodesForExitAndUnswitchedBlocks, I'd have a single function rewriteExitPHIs with the signature of rewritePHINodesForExitAndUnswitchedBlocks that did different things based on whether ExitBB and UnswitchedBB were equal. Right now the PHI handling logic is effectively split between the caller (that decides whether we need a split PHI) and the callee rewritePHINodesForUnswitchedExitBlock or rewritePHINodesForExitAndUnswitchedBlocks that does the rewrite.

167

FYI: indent seems off here, but clang-format is the hammer.

194

I'd s/ExitingBB/OldExitingBB/

Same for rewritePHINodesForUnswitchedExitBlock.

217

Why int64_t ?

302

Nit: s/is't/isn't/

491

Instead of adding a new UnswitchedExitBBs, I'd re-use SplitExitBBMap for this -- for unswitched block BB that doesn't need splitting, I'd have SplitExitBBMap[BB] = BB. For instance, if you go with the unified rewriteExitPHIs routine above, the the code will look like:

if (!SplitExitBB) {
  // If this is the first time we see this, do the split and remember it.
  SplitExitBB = pred_empty(ExitBB) ? ExitBB : SplitBlock(ExitBB, &ExitBB->front(), &DT, &LI);
  rewriteExitPHIs(*ExitBB, *SplitExitBB, *ParentBB, *OldPH);
  updateLoopExitIDom(ExitBB, L, DT);
}

with an appropriate relaxation in updateLoopExitIDom.

507

This looked fine initially, but this time around I scratched my head a bit -- do you mind making this explicitly an assignment into CasePair.second?

This revision is now accepted and ready to land.May 6 2017, 3:39 PM
davide accepted this revision.May 8 2017, 11:50 AM
davide added a subscriber: dberlin.

LGTM. I'd really appreciate if @dberlin could take a look at the rewriter (even post-commit).

chandlerc marked 6 inline comments as done.May 11 2017, 7:32 PM

Thanks both for the review. Landing with some fixes, but further discussion below and I'll follow-up with anything else.

I'd really appreciate if @dberlin could take a look at the rewriter (even post-commit).

Me too! (But I think this can be post-commit too.)

lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
165

It's funny, I had that exact thing originally.

I removed it for two reasons. One, it made the code here (IMO) substantially harder to read than either of the ones here because you end up with essentially two independent halves of the loop body for the two cases. This made the commenting and other aspects pretty confusing IMO.

Second, some of the callers already had distinguished between these two cases and it seemed nice to not revisit that decision, but instead make the precise rewrite locally where we have already tested this.

I also think that this could be improved by having a dedicated ExitBB->phis() method that produces the requisite range. I'll look at adding that. Then this whole thing becomes much cleaner IMO.

217

I have no idea. Switched to int.

491

IMO, this is somewhat tied up in the other issue.

I actually wrote this version as well before writing the one you see here. The thing that bugged me about it was that splitting the exit blocks doesn't seem likely to be the common case. And so it seems weird to end up with a map that will often just be a set.

That, plus, we have a local and easy way to distinguish between the two and so it seemed like we should keep the data structures separate.

However, it does result in a lot more code. More efficient code, but more code all the same.

I'm somewhat divided on this. If my explanation convinces you to like this approach, I'll keep it. But if after hearing why I wasn't fond of the approach you still think its worth simplifying, let me know, and I'll do a follow-up patch to simplify everything.

This revision was automatically updated to reflect the committed changes.
chandlerc marked an inline comment as done.
sanjoy added inline comments.May 12 2017, 1:42 PM
lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
491

As long as you tried the approach I mentioned and didn't like it, I'm okay with what you ultimately settled on.