Page MenuHomePhabricator

[LCSSA] Use linear algorithm for isRecursivelyLCSSAForm
ClosedPublic

Authored by igor-laevsky on Oct 7 2016, 4:58 AM.

Details

Summary

Currently 'isRecursivelyLCSSAForm' has quadratic complexity on the number of
loop basic blocks. This caused by the fact that in each recursion level we will
visit all blocks from the current loop and all of it's sub-loops. On the next
recursive call we will step into one of the sub-loops and revisit same basic blocks.
We can address that by limiting iteration only on the blocks which are located
directly in the current loop. We know that all sub-loops will be checked by the
following recursive process.

This change is motivated by the 10x slow-down on one of our internal loop
intensive tests (Release+Asserts build). It started to happen after introduction
of the additional lcssa verification - https://github.com/llvm-mirror/llvm/commit/79e702086510fa7b52de178354eab34a7f641025

Unfortunately even with this change we are still experiencing huge slow down. I think
this may be the result of calling LCSSAWrapperPass::verifyAnalysis for the whole
function for each loop. Maybe there is a way we can more efficiently structure this code?

Diff Detail

Repository
rL LLVM

Event Timeline

igor-laevsky retitled this revision from to [LCSSA] Use linear algorithm for isRecursivelyLCSSAForm.
igor-laevsky updated this object.
igor-laevsky added a subscriber: llvm-commits.
mzolotukhin edited edge metadata.Oct 7 2016, 9:52 AM

Hi Igor,

Thanks for working on this! I have two concerns/thoughts:

  1. Is it actually equivalent to the original implementation? It looks so, but we need to check the corner cases and be 100% sure that it's the case. Usually the bugs we detect with such verifiers are in corner cases.
  2. If it's equivalent to the original, why do we need to be recursive at all? We can go through all blocks of the given loop but for each block find the innermost loop containing it and check if the value isn't used outside of it. What do you think?

As for the slowdown, we can put it under some flag, but I'm a bit reluctant to it - we've found quite a few bugs when we started to verify LCSSA, and it's good to have it turned on by default. And unfortunately checking only the current loop is not sufficient, because transformations can change outer loops.

Thanks,
Michael

reames added a subscriber: reames.Oct 7 2016, 2:23 PM
  1. If it's equivalent to the original, why do we need to be recursive at all? We can go through all blocks of the given loop but for each block find the innermost loop containing it and check if the value isn't used outside of it. What do you think?

I really like this framing. Rather than asking whether each sub-loop is in LCSSA, we would essentially ask whether each BB is in LCSSA w.r.t. it's inner most containing loop. Because we know all of the blocks within a sub-loop are also contained within an outer loop, this gives us the transitive property we need.

However, it does look like we don't currently verify the contains relation for sub-loops. This may be covered by the off by default LoopInfo.verify(), but it's not directly enforced. Not sure we need to block this patch on that fact, but the lack of verification makes me a bit nervous.

reames added a comment.Oct 7 2016, 2:49 PM

However, it does look like we don't currently verify the contains relation for sub-loops.

Correction: This is checked by verifyLoop

igor-laevsky edited edge metadata.

Thanks for the comments!

Michael, your second point seems very reasonable. Please take a look at the updated diff. I kept the original name "isRecursivelyLCSSAForm", despite that function is no longer recursive. I think it still describes the process fairly well.

I agree that putting LCSSAWrapperPass::verifyAnalysis under a flag isn't a good way to deal with the slowdown. Can't we apply same technique as was used for the verifyLoop (https://github.com/llvm-mirror/llvm/blob/93e6e5414ded14bcbb233baaaa5567132fee9a0c/lib/Analysis/LoopPass.cpp#L219)? I.e add explicit verification inside LPPassManager for each of the top-level loops.

mzolotukhin accepted this revision.Oct 10 2016, 11:51 AM
mzolotukhin edited edge metadata.

Hi Igor,

The patch looks good to me, thank you for doing this!

I agree that putting LCSSAWrapperPass::verifyAnalysis under a flag isn't a good way to deal with the slowdown. Can't we apply same technique as was used for the verifyLoop (https://github.com/llvm-mirror/llvm/blob/93e6e5414ded14bcbb233baaaa5567132fee9a0c/lib/Analysis/LoopPass.cpp#L219)? I.e add explicit verification inside LPPassManager for each of the top-level loops.

Do I understand it correctly, that we'll be checking LCSSA only for the current loop after each loop-pass? I think it should be sufficient, because if a pass breaks LCSSA, we should fail when LPM proceeds to the parent loop. However, for the sake of easier debugging I would prefer to allow full verification as we have it right now too, probably under -verify-loop-info as well (or under another flag). It really helps to find the broken pass faster.

Thanks,
Michael

This revision was automatically updated to reflect the committed changes.

Hi Michael,

Do I understand it correctly, that we'll be checking LCSSA only for the current loop after each loop-pass? I think it should be sufficient, because if a pass breaks LCSSA, we should fail when LPM proceeds to the parent loop. However, for the sake of easier debugging I would prefer to allow full verification as we have it right now too, probably under -verify-loop-info as well (or under another flag). It really helps to find the broken pass faster.

Yes, this is the plan. I will send patch up for review in a nearest future.