Duplicating loops and virtual phis

[Richard Biener]

On May 12, 2017 10:42:34 PM GMT+02:00, Steve Ellcey <sellcey@cavium.com> wrote:
>(Short version of this email, is there a way to recalculate/rebuild
>virtual
>phi nodes after modifying the CFG.)
>
>I have a question about duplicating loops and virtual phi nodes.
>I am trying to implement the following optimization as a pass:
>
>Transform:
>
>   for (i = 0; i < n; i++) {
>	A[i] = A[i] + B[i];
>	C[i] = C[i-1] + D[i];
>   }
>
>Into:
>
>   if (noalias between A&B, A&C, A&D)
>	for (i = 0; i < 100; i++)
>		A[i] = A[i] + B[i];
>	for (i = 0; i < 100; i++)
>		C[i] = C[i-1] + D[i];
>   else
>	for (i = 0; i < 100; i++) {
>		A[i] = A[i] + B[i];
>		C[i] = C[i-1] + D[i];
>	}
>
>Right now the vectorizer sees that 'C[i] = C[i-1] + D[i];' cannot be
>vectorized so it gives up and does not vectorize the loop.  If we split
>up the loop into two loops then the vector add with A[i] could be
>vectorized
>even if the one with C[i] could not.

Loop distribution does this transform but it doesn't know about versioning for unknown dependences.

>Currently I can introduce the first 'if' that checks for aliasing by
>using loop_version() and that seems to work OK.  (My actual compare
>for aliasing is actually just an approximation for now.)
>
>Where I am running into problems is with splitting up the single loop
>under the noalias if condition into two sequential loops (which I then
>intend to 'thin out' by removing one or the other set of instructions.
>I am using slpeel_tree_duplicate_loop_to_edge_cfg() for that loop
>duplication
>and while I get the CFG I want, the pass ends with verify_ssa failing
>due
>to bad virtual/MEM PHI nodes.  Perhaps there is a different function
>that
>I should use duplicate the loop.

>a.c: In function ���foo���:
>a.c:2:5: error: PHI node with wrong VUSE on edge from BB 13
> int foo(int *a, int *b, int *c, int *d, int n)
>     ^~~
>.MEM_40 = PHI <.MEM_15(D)(13), .MEM_34(9)>
>expected .MEM_58
>a.c:2:5: internal compiler error: verify_ssa failed
>
>I have tried to fix up the PHI node by hand using SET_PHI_ARG_DEF but
>have not had any luck.  I was wondering if there was any kind of
>'update all the phi nodes' function or just a 'update the virtual phi
>nodes' function.  The non-virtual PHI nodes seem to be OK, it is just
>the virtual ones that seem wrong after I duplicate the loop into two
>consecutive loops.
>
>Steve Ellcey
>sellcey@cavium.com