[basicaa] Recurse through a single phi input
authorPhilip Reames <listmail@philipreames.com>
Thu, 4 Mar 2021 21:03:54 +0000 (13:03 -0800)
committerPhilip Reames <listmail@philipreames.com>
Thu, 4 Mar 2021 21:07:06 +0000 (13:07 -0800)
commit83ae49671dea76ded19e6c35eaafbe6c495d0e50
tree4daf1c799716ed232df43c10e6661ebad40366ab
parent2f37cdd5699f65cf6b9da615337cad6fdb012304
[basicaa] Recurse through a single phi input

BasicAA knows how to analyze phis, but to control compile time, we're fairly limited in doing so. This patch loosens that restriction just slightly 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.
* This is deliberately extremely restrictive about recursing through at most one input of the phi.  There's a known general problem with BasicAA sometimes hitting exponential compile time already, and this patch makes every effort not to compound the problem.  Once the root issue is fixed, we can probably loosen the restrictions here a bit.
* 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.
* 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.

Differential Revision: https://reviews.llvm.org/D97401
llvm/lib/Analysis/BasicAliasAnalysis.cpp
llvm/test/Analysis/BasicAA/recphi.ll