Page MenuHomePhabricator

During PHI elimination, split critical edges that move copies out of loops
ClosedPublic

Authored by djasper on Mar 2 2015, 2:10 PM.

Details

Summary

This prevents the behavior observed in llvm.org/PR22369. I am not sure whether I am reading the code correctly, but the early exit based on isLiveOutPastPHIs() seems like a bug as it prevents the nice loop-splitting logic below.

This is still work in progress as it currently breaks a few tests. Mainly, it seems to influence which copies are local and which are non-local, which influences the order in which the RegisterCoalescer visits copies. Coalescing the wrong registers first has unwanted side-effects.

Diff Detail

Event Timeline

djasper updated this revision to Diff 21037.Mar 2 2015, 2:10 PM
djasper retitled this revision from to During PHI elimination, split critical edges that move copies out of loops.
djasper updated this object.
djasper edited the test plan for this revision. (Show Details)
djasper added reviewers: chandlerc, qcolombet.
djasper added a subscriber: Unknown Object (MLST).
qcolombet edited edge metadata.Mar 2 2015, 2:37 PM

Hi Daniel,

This is still work in progress as it currently breaks a few tests. Mainly, it seems to influence which copies are local and which are non-local, which influences the order in which the RegisterCoalescer visits copies. Coalescing the wrong registers first has unwanted side-effects.

What does this mean for the livability of this patch?

Thanks,
-Quentin

Not sure what that means. I think the changes here by itself are good, but they lead to worse behavior in later passes, specifically register coalescing. I'll take a look at whether the register coalescer heuristic can be tweaked in a simple way to avoid this regression.

My concern was this:

it currently breaks a few tests

What do you mean by "break"?

From your last comment, I believe we generate worse code.
If that the case, then just put a flag to preserve the previous behavior and file PR for the regression you find so that we can work on fixing them.
Other than that, the change itself looks good to me.

Thanks,
-Quentin

djasper updated this revision to Diff 21064.Mar 2 2015, 4:36 PM
djasper edited edge metadata.
  • Hide new behavior behind flag.
  • Add test.

I have hidden the new behavior behind a flag and added a test.

With the flag enabled by default, these four tests break:

LLVM :: CodeGen/Hexagon/hwloop-cleanup.ll

triggers an assertion.

LLVM :: CodeGen/X86/coalescer-commute4.ll
LLVM :: CodeGen/X86/phys_subreg_coalesce-2.ll
LLVM :: CodeGen/X86/zlib-longest-match.ll

generate worse code. Likely these need to be solved by improving the register allocator.

MatzeB added a subscriber: MatzeB.Mar 2 2015, 4:44 PM

The change itself LGTM (but nitpick below).

As mentioned in by you on IRC we perform some unlucky choices in the coalescing order in test/CodeGen/X86/coalescer-commute4.ll with this patch. Are there more? If it's just some tests like this failing but benchmarks generally improving, then it's okay to XFAIL the tests, or trying to rewrite them in a way that we are lucky with the heuristic. If benchmarks generally regress with the changes, then we need further research on how to avoid that...

lib/CodeGen/PHIElimination.cpp
583–588

No need to keep the old code in a comment, it can always be found in the subversion log.

MatzeB added a comment.Mar 2 2015, 4:47 PM

The change itself LGTM (but nitpick below).

As mentioned in by you on IRC we perform some unlucky choices in the coalescing order in test/CodeGen/X86/coalescer-commute4.ll with this patch. Are there more? If it's just some tests like this failing but benchmarks generally improving, then it's okay to XFAIL the tests, or trying to rewrite them in a way that we are lucky with the heuristic. If benchmarks generally regress with the changes, then we need further research on how to avoid that...

You answered to most of my remarks while I was writing this :)

The old code is already removed in the latest version of the patch.

I think the "unlucky" ordering happens in three tests as per my previous comment and it also regresses benchmarks in our internal suite, although I haven't looked closely at which ones. Thus, I have guarded the new behavior by a flag now as Quentin suggested. I'll then try to fix the unlucky behavior and see whether that also improves benchmarks.

qcolombet accepted this revision.Mar 2 2015, 4:49 PM
qcolombet edited edge metadata.

Thanks Daniel for the flag.

We could switch the default value as soon as we fix the assertion. In the meantime, please file PRs for the regressions so that we can help resolving those.

LGTM.

Cheers,
-Quentin

This revision is now accepted and ready to land.Mar 2 2015, 4:49 PM
djasper closed this revision.Mar 3 2015, 2:27 AM

Submitted as r231064.

Also filed:

llvm.org/PR22767
llvm.org/PR22768