Page MenuHomePhabricator

[basicaa] Recurse through a single phi input
ClosedPublic

Authored by reames on Feb 24 2021, 10:24 AM.

Details

Summary

BasicAA knows how to analyze phis, but to control compile time, we're fairly limited in doing so. This patch looses that restriction when there is exactly one phi input (after discounting induction variable increments). The result of this is that we can handle more cases around nested and sibling loops with pointer induction variables.

A few points to note.

  1. I could be even more restrictive here and restrict this to exactly one incoming value. (Right now, I allow one phi, and an arbitrary number of other values.) I don't have a strong preference here, reviewer comments welcome.
  1. As seen in the test file, we're still missing cases which aren't *directly* based on phis (e.g. using the indvar increment). I believe this to be a separate problem and am going to explore this in another patch once this one lands.
  1. As seen in the test file, this results in the unfortunate fact that using phivalues sometimes results in worse quality results. I believe this comes down to an oversight in how recursive phi detection was implemented for phivalues. I'm happy to tackle this in a follow up change.

Diff Detail

Event Timeline

reames created this revision.Feb 24 2021, 10:24 AM
reames requested review of this revision.Feb 24 2021, 10:24 AM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 24 2021, 10:24 AM
nikic added a comment.Feb 24 2021, 1:20 PM

I'm rather leery of relaxing this until we have a reliably complexity limit for BasicAA (D96647 or similar). From past experience, it's very easy to open up new pathological compile-time cases in BasicAA, because it walks a really thin line to avoid exponential queries in the absence of complexity cutoffs.

Worth noting that D92401 handles the PhiValues case, as well as @sibling_loop, but that's another change that has pathological compile-time cases.

reames updated this revision to Diff 326555.Feb 25 2021, 4:51 PM

Update to most restrictive form.

I'm rather leery of relaxing this until we have a reliably complexity limit for BasicAA (D96647 or similar). From past experience, it's very easy to open up new pathological compile-time cases in BasicAA, because it walks a really thin line to avoid exponential queries in the absence of complexity cutoffs.

I understand your hesitancy here, but let me explain why I think this should go forward regardless. Specifically, with the most restricted form of the patch as updated.

  1. With the updated patch, we specifically only continue analysis when there's a single phi value being recursed on. Given that, this patch definitely can not create an exponential number of queries. It can still expose potential exponential that already exist by reaching deeper into the graph, but that's a separate issue.
  1. This is a really critical case. Specifically, it's the case of a pointer induction variable in a loop nest. It seems really embarrassing to have LLVM miss this.
  1. I'm general hesitant to block on progress on fixing an exponential issue. This isn't the only one we have and it isn't the first time we've hit one. In general, different contributors will be working on different corpus, and what shows in one place doesn't in another. We certainly don't want to take changes which make a problem markedly worse on anyone's corpus, but something that is orthogonal in practice (if not in theory) seems good to move forward with.
fhahn accepted this revision.Mar 2 2021, 2:48 PM

I'm rather leery of relaxing this until we have a reliably complexity limit for BasicAA (D96647 or similar). From past experience, it's very easy to open up new pathological compile-time cases in BasicAA, because it walks a really thin line to avoid exponential queries in the absence of complexity cutoffs.

I understand your hesitancy here, but let me explain why I think this should go forward regardless. Specifically, with the most restricted form of the patch as updated.

  1. With the updated patch, we specifically only continue analysis when there's a single phi value being recursed on. Given that, this patch definitely can not create an exponential number of queries. It can still expose potential exponential that already exist by reaching deeper into the graph, but that's a separate issue.
  1. This is a really critical case. Specifically, it's the case of a pointer induction variable in a loop nest. It seems really embarrassing to have LLVM miss this.
  1. I'm general hesitant to block on progress on fixing an exponential issue. This isn't the only one we have and it isn't the first time we've hit one. In general, different contributors will be working on different corpus, and what shows in one place doesn't in another. We certainly don't want to take changes which make a problem markedly worse on anyone's corpus, but something that is orthogonal in practice (if not in theory) seems good to move forward with.

This approach seems like a relatively safe extensions of the PHI handling (in terms of introducing additional queries) to me, while giving some nice improvements. I tried this with -O3 & LTO on X86 and there's positive changes in a couple of benchmarks in terms of additional noalias results, improvements to removed stores, unrolling & additional vectorization.

With respect to 3., I would be cautious of introducing new exponential issues. But as you mentioned, I don't see how this patch would introduce new exponential behavior. If it exposes existing exponential behavior, we can revert & focus on fixing the behavior.

LGTM, but it would be good to wait a bit in case @nikic has concerns with the latest version.

This revision is now accepted and ready to land.Mar 2 2021, 2:48 PM
nikic accepted this revision.Mar 4 2021, 9:44 AM

Yes, this looks like a safe extension, as we're recursing down exactly one value. I think it's okay to apply this until we can come up with a more general solution to this problem space.

This revision was automatically updated to reflect the committed changes.