Successive hoisting and AVAIL_OUT in at least one successor heuristic

[Richard Biener]

On Thu, 6 May 2021, Prathamesh Kulkarni wrote:

> Hi Richard,
> I was just wondering if second (and higher) order hoistings may defeat
> the "AVAIL_OUT in at least one successor heuristic" ?
> 
> For eg:
> bb2:
> if (cond1) goto bb3 else goto bb4;
> 
> bb3:
> if (cond2) goto bb5 else goto bb6;
> 
> bb5:
> return x + y;
> 
> bb6:
> return x + y;
> 
> bb4:
> if (cond3) goto bb7 else goto bb8;
> 
> bb7:
> return x + y;
> 
> bb8:
> return x + y;
> 
> In above CFG, IIUC, we will end up hoisting x + y in bb2 even if bb3
> or bb4 don't originally
> contain x + y since during first hoisting pass x + y will be hoisted
> from bb5, bb6 into bb3,
> and likewise from bb7, bb8 into bb4 and during second hoisting pass it
> will hoist x + y into bb2, since x + y is now available in bb3 and
> bb4.

But that's intended - the logic is _supposed_ to do "everything
at once", thus repeated runs of hoisting should not hoist more.
Which is also why we no longer iterate hoist insertion.

> This might become an issue if successive hoistings will end up
> hoisting the expression "too far" resulting in long range hoisting ?

I think this "long range hoisting" argument is a red herring...

> Also if we're hoisting from post-dom block in which case the
> expression may not be truly ANTIC, and eventually end up being
> inserted into a successor block by successive hoisting passes.

But this shouldn't happen - can you show a testcase where it does?

> I was wondering if we should check that the expression is "originally"
> in AVAIL_OUT in at least one successor of block to avoid considering
> expressions inserted by hoisting / PRE ?

No, why should we?

Richard.