Re: [PATCH 1/2] sparse, llvm: group PHI nodes at the top of each BB

["Jonathan Neuschäfer" <j.neuschaefer@gmx.net>]

On Wed, Oct 10, 2012 at 09:31:31AM +0300, Pekka Enberg wrote:
> On Wed, Oct 10, 2012 at 3:12 AM, Jeff Garzik <jgarzik@pobox.com> wrote:
> > On 10/09/2012 07:34 PM, Jonathan Neuschäfer wrote:
> >>
> >> This is required for producing valid LLVM bitcode.
> >>
> >> Cc: Pekka Enberg <penberg@kernel.org>
> >> Cc: Christopher Li <sparse@chrisli.org>
> >> Cc: Jeff Garzik <jgarzik@redhat.com>
> >> Cc: Linus Torvalds <torvalds@linux-foundation.org>
> >> Signed-off-by: Jonathan Neuschäfer <j.neuschaefer@gmx.net>
> >> ---
> >>   sparse-llvm.c              |   17 ++++++++++++++++-
> >>   validation/backend/loop2.c |   13 +++++++++++++
> >>   2 files changed, 29 insertions(+), 1 deletion(-)
> >>   create mode 100644 validation/backend/loop2.c
> >
> > Looks sane... but I did not verify whether or not this reordering is safe
> 
> Ditto. Jonathan, care to explain why you think it is safe? I still
> don't know Sparse's linearized IR well enough to convince myself this
> is OK.

I can't say with certainty that it's safe either, so I probably should
have marked the patch with "request for comments".

AFAICT there are three reasons an instruction cannot be moved up or down
within a basic block:
 1. If it takes previous SSA values as arguments, it can't be moved
    above the corresponding intructions.
 2. If its value is used as an argument of an instruction further down
    in the BB, it can't be moved below that instruction.
 3. Swapping two instructions that influence or are influenced by the
    "global state" (sorry for the loose wording), e.g. by doing memory
    accesses, performing I/O, or calling functions (which in turn can
    do about anything in general), is generally unsafe.

Case 1 doesn't apply because PHI nodes don't use values computed in the
same invocation of their basic block. Case 2 doesn't apply as I'm not
moving the PHI nodes down. Case 3 doesn't seem to apply either.

That's how I think this patch is safe.


HTH,
Jonathan
--
To unsubscribe from this list: send the line "unsubscribe linux-sparse" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html