Potential incorrect simplification

Potential incorrect simplification

[Dibyendu Majumdar]

I am getting a failure in following test when simplifications are enabled:

extern int printf(const char *, ...);

int main(void)
{
   struct{
     int twobit:2;
     int       :1;
     int threebit:3;
     unsigned int onebit:1;
   } s3;

   s3.onebit = 1;
   if(s3.onebit != 1){
      printf("Be especially careful with 1-bit fields! %d\n", (int) s3.onebit);
      return 1;
   }
   return 0;
}

The output (truncated) from linearizer without simplications is this:

main:
.L0:
        <entry-point>
        load.32     %r1 <- 0[s3]
        shl.32      %r2 <- $1, $6
        and.32      %r3 <- %r1, $-65
        or.32       %r4 <- %r3, %r2
        store.32    %r4 -> 0[s3]
        load.32     %r5 <- 0[s3]
        lsr.32      %r6 <- %r5, $6
        cast.32     %r7 <- (1) %r6
        setne.32    %r8 <- %r7, $1
        br          %r8, .L1, .L2

But if simplifications are on then we get:

main:
.L0:
        <entry-point>
        and.32      %r3 <- %r4, $-65
        or.32       %r4 <- %r3, $64
        lsr.32      %r6 <- %r4, $6
        cast.32     %r7 <- (1) %r6
        setne.32    %r8 <- %r7, $1
        br          %r8, .L1, .L3

Regards
Dibyendu

Re: Potential incorrect simplification

[Luc Van Oostenryck]

On Tue, Mar 28, 2017 at 2:40 PM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
> I am getting a failure in following test when simplifications are enabled:
>
> extern int printf(const char *, ...);
>
> int main(void)
> {
>    struct{
>      int twobit:2;
>      int       :1;
>      int threebit:3;
>      unsigned int onebit:1;
>    } s3;
>
>    s3.onebit = 1;
>    if(s3.onebit != 1){
>       printf("Be especially careful with 1-bit fields! %d\n", (int) s3.onebit);
>       return 1;
>    }
>    return 0;
> }
>
> The output (truncated) from linearizer without simplications is this:
>
> main:
> .L0:
>         <entry-point>
>         load.32     %r1 <- 0[s3]
>         shl.32      %r2 <- $1, $6
>         and.32      %r3 <- %r1, $-65
>         or.32       %r4 <- %r3, %r2
>         store.32    %r4 -> 0[s3]
>         load.32     %r5 <- 0[s3]
>         lsr.32      %r6 <- %r5, $6
>         cast.32     %r7 <- (1) %r6
>         setne.32    %r8 <- %r7, $1
>         br          %r8, .L1, .L2
>
> But if simplifications are on then we get:
>
> main:
> .L0:
>         <entry-point>
>         and.32      %r3 <- %r4, $-65
>         or.32       %r4 <- %r3, $64
>         lsr.32      %r6 <- %r4, $6
>         cast.32     %r7 <- (1) %r6
>         setne.32    %r8 <- %r7, $1
>         br          %r8, .L1, .L3

Are you worried about the load of s3 (wich is not initialized)?
Or the store of s3 (wich is local and never used but for .onebit)?
Or the size of %r6 (which is created as 32bit but used as 1bit)?

If the later, you're missing the patch
    https://git.kernel.org/pub/scm/devel/sparse/sparse.git/commit/?h=sparse-next&id=522773d089700cce5551860aea3cb93f40b5f3a4

-- Luc

Re: Potential incorrect simplification

[Dibyendu Majumdar]

Hi Luc,

On 28 March 2017 at 14:34, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> On Tue, Mar 28, 2017 at 2:40 PM, Dibyendu Majumdar
> <mobile@majumdar.org.uk> wrote:
>> I am getting a failure in following test when simplifications are enabled:
>>
>> extern int printf(const char *, ...);
>>
>> int main(void)
>> {
>>    struct{
>>      int twobit:2;
>>      int       :1;
>>      int threebit:3;
>>      unsigned int onebit:1;
>>    } s3;
>>
>>    s3.onebit = 1;
>>    if(s3.onebit != 1){
>>       printf("Be especially careful with 1-bit fields! %d\n", (int) s3.onebit);
>>       return 1;
>>    }
>>    return 0;
>> }
>>
>> The output (truncated) from linearizer without simplications is this:
>>
>> main:
>> .L0:
>>         <entry-point>
>>         load.32     %r1 <- 0[s3]
>>         shl.32      %r2 <- $1, $6
>>         and.32      %r3 <- %r1, $-65
>>         or.32       %r4 <- %r3, %r2
>>         store.32    %r4 -> 0[s3]
>>         load.32     %r5 <- 0[s3]
>>         lsr.32      %r6 <- %r5, $6
>>         cast.32     %r7 <- (1) %r6
>>         setne.32    %r8 <- %r7, $1
>>         br          %r8, .L1, .L2
>>
>> But if simplifications are on then we get:
>>
>> main:
>> .L0:
>>         <entry-point>
>>         and.32      %r3 <- %r4, $-65
>>         or.32       %r4 <- %r3, $64
>>         lsr.32      %r6 <- %r4, $6
>>         cast.32     %r7 <- (1) %r6
>>         setne.32    %r8 <- %r7, $1
>>         br          %r8, .L1, .L3
>
> Are you worried about the load of s3 (wich is not initialized)?
> Or the store of s3 (wich is local and never used but for .onebit)?
> Or the size of %r6 (which is created as 32bit but used as 1bit)?
>
> If the later, you're missing the patch
>     https://git.kernel.org/pub/scm/devel/sparse/sparse.git/commit/?h=sparse-next&id=522773d089700cce5551860aea3cb93f40b5f3a4
>


The first instruction and.32 refers to %r4 which is undefined.

Regards
Dibyendu

Re: Potential incorrect simplification

[Luc Van Oostenryck]

On Tue, Mar 28, 2017 at 02:58:57PM +0100, Dibyendu Majumdar wrote:
> Hi Luc,
> 
> 
> The first instruction and.32 refers to %r4 which is undefined.

Yes, I saw.
This %r4 corresponds (somehow) to s3 which isn't initialized.

But yes, there is two problems here:
*) we should use something explicit, like VOID
*) there is a circulary dependence between %r3 & %r4, the first %r4
   being obviously wrong.

I suspect there is a lot of problems present once there is some
undefined variables.

Thanks for the repoort.

-- Luc

Re: Potential incorrect simplification

[Dibyendu Majumdar]

Hi Luc,

On 28 March 2017 at 15:11, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>> The first instruction and.32 refers to %r4 which is undefined.
>
> Yes, I saw.
> This %r4 corresponds (somehow) to s3 which isn't initialized.
>
> But yes, there is two problems here:
> *) we should use something explicit, like VOID
> *) there is a circulary dependence between %r3 & %r4, the first %r4
>    being obviously wrong.
>
> I suspect there is a lot of problems present once there is some
> undefined variables.
>

Well the unsimplified output is correct. The problem appears after
simplification.

Regards
Dibyendu

Re: Potential incorrect simplification

[Linus Torvalds]

On Tue, Mar 28, 2017 at 7:19 AM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
>
> Well the unsimplified output is correct. The problem appears after
> simplification.

No. The unsimplified output has the exact same bug:

  main:
  .L0:
        <entry-point>
        load.32     %r1 <- 0[s3]
        shl.32      %r2 <- $1, $6
        and.32      %r3 <- %r1, $-65

That "load.32" loads an uninitialized value from the stack.

The simplification then just simplifies the uninitialized load to just
be an uninitialized pseudo instead. Exact same code.

And arguably both unsimplified and simplified code is "correct" in the
sense that it's exactly what the original source code does:

   s3.onebit = 1;

becomes

        and.32      %r3 <- %r4, $-65
        or.32       %r4 <- %r3, $64

where that "and" is obviously pointless (well, "obviously" to a human,
not so sparse ;), but it's basically the code sequence "leave the
uninitialized bits alone, set bit 6 to 1". And then comes the *truly*
stupid code that does

        lsr.32      %r6 <- %r4, $6
        cast.32     %r7 <- (1) %r6

which is "shift bit 6 down to bit zero, and cast (aka sign-extend) the
one-bit value to 32 bits" and then

        setne.32    %r8 <- %r7, $1
        br          %r8, .L1, .L3

test if the result is 1, do a conditional branch on the result.

So the code is "correct". It may be confusing, because simplification
turns a uninitialized load into just an uninitialized variable, and
what also happens is that since SSA means that (by definition) every
initialization dominates every use, we have this situation where the
first assignment to the pseudo becomes the dominator of even the
uninitialized *previous* use of the pseudo, which is why you see that
odd sequence

        and.32      %r3 <- %r4, $-65
        or.32       %r4 <- %r3, $64

which *initializes* the pseudo %r4 in the second instruction, but uses
it in the first one. That's a classic pattern of uninitialized pseudos
in sparse exactly because of the SSA logic.

But it is all internally consistent, and the simplification is
"correct". The simplification phase very much has a "garbage in,
garbage out" model.

                  Linus

Re: Potential incorrect simplification

[Luc Van Oostenryck]

On Tue, Mar 28, 2017 at 09:20:58AM -0700, Linus Torvalds wrote:
> On Tue, Mar 28, 2017 at 7:19 AM, Dibyendu Majumdar
> <mobile@majumdar.org.uk> wrote:
> >
> > Well the unsimplified output is correct. The problem appears after
> > simplification.
> 
> No. The unsimplified output has the exact same bug:
> 
>   main:
>   .L0:
>         <entry-point>
>         load.32     %r1 <- 0[s3]
>         shl.32      %r2 <- $1, $6
>         and.32      %r3 <- %r1, $-65
> 
> That "load.32" loads an uninitialized value from the stack.
> 
> The simplification then just simplifies the uninitialized load to just
> be an uninitialized pseudo instead. Exact same code.
> 
> And arguably both unsimplified and simplified code is "correct" in the
> sense that it's exactly what the original source code does:
> 
>    s3.onebit = 1;
> 
> becomes
> 
>         and.32      %r3 <- %r4, $-65
>         or.32       %r4 <- %r3, $64
> 
> where that "and" is obviously pointless (well, "obviously" to a human,
> not so sparse ;), but it's basically the code sequence "leave the
> uninitialized bits alone, set bit 6 to 1". And then comes the *truly*
> stupid code that does
> 
>         lsr.32      %r6 <- %r4, $6
>         cast.32     %r7 <- (1) %r6
> 
> which is "shift bit 6 down to bit zero, and cast (aka sign-extend) the
> one-bit value to 32 bits" and then
> 
>         setne.32    %r8 <- %r7, $1
>         br          %r8, .L1, .L3
> 
> test if the result is 1, do a conditional branch on the result.
> 
> So the code is "correct". It may be confusing, because simplification
> turns a uninitialized load into just an uninitialized variable, and
> what also happens is that since SSA means that (by definition) every
> initialization dominates every use, we have this situation where the
> first assignment to the pseudo becomes the dominator of even the
> uninitialized *previous* use of the pseudo, which is why you see that
> odd sequence
> 
>         and.32      %r3 <- %r4, $-65
>         or.32       %r4 <- %r3, $64
> 
> which *initializes* the pseudo %r4 in the second instruction, but uses
> it in the first one. That's a classic pattern of uninitialized pseudos
> in sparse exactly because of the SSA logic.
> 
> But it is all internally consistent, and the simplification is
> "correct". The simplification phase very much has a "garbage in,
> garbage out" model.

I agree, of course, but I think there is a problem anyway.
The problem here with this %r4 is created by the single-store
shortcut which replace all loads with the same value as the one
used for the unique store (even loads that are not dominated
by the store). Fair enough, don't use uninitialized vars.

Now, if you remove this single-store shortcut and just let the normal
find_dominating_stores() do its job, the resulting code become
the expected:
	ret.32      $0

Not just by coincidence (I checked the intermediate steps):
sparse deduces then correctly that the value in the conditional
is always true and everything become dead after that.

But what annoys me really is that:
-) once you remove the single-store shortcut, it seems there is
   other problems (I just saw it by doing some code comparison,
   I need to create a few clear examples).
-) here the variable is always undefined, but once you have a var
   undefined in one path and defined in another one path and
   always used when defined then things become really messed up
   (misplaced phi-nodes). It happen for example with code like:
	int foo(int a, int b)
	{
		int var = 0;
		int r;
	
		if (a)
			var = 1;
		if (b)
			r = var;
	
		return r;		// undef if !b
	}
   Wich is perfectly defined when called with a non-zero b.
   I have reasons to believe it's totally unrelated issues though.

-- Luc Van Oostenryck

Re: Potential incorrect simplification

[Linus Torvalds]

On Tue, Mar 28, 2017 at 10:00 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> I agree, of course, but I think there is a problem anyway.

Yes. I just wanted to point out that it's not the simplification phase
that is the problem, and that sparse is technically correct (for some
definition of "technically" ;)

> The problem here with this %r4 is created by the single-store
> shortcut which replace all loads with the same value as the one
> used for the unique store (even loads that are not dominated
> by the store). Fair enough, don't use uninitialized vars.

Yeah.

Personally, I absolutely detest a lot of the undefined C corner cases.
I'm a huge fan of the language, but almost all of the the "undefined
behavior" in C is a huge mistake.

Pretty much every "undefined behavior" in the standard should have
been "implementation defined", or at least have the option to be so.
For example, it would have been much nicer if all variables were
implicitly initialized to zero, not just static variables. In 99% of
all cases the compiler won't even care, since it will see the actual
real initialization anyway, and the "initialize automatic variables to
zero" wouldn't matter - except from a repeatability, security and
simplicity standpoint.

Obviously, that particular choice made more sense in legacy C (when
optimizations weren't nearly as smart as what people take for granted
today, and CPU cycles were more expensive).

> Now, if you remove this single-store shortcut and just let the normal
> find_dominating_stores() do its job, the resulting code become
> the expected:
>         ret.32      $0
>
> Not just by coincidence (I checked the intermediate steps):
> sparse deduces then correctly that the value in the conditional
> is always true and everything become dead after that.

Nice.

> But what annoys me really is that:
> -) once you remove the single-store shortcut, it seems there is
>    other problems (I just saw it by doing some code comparison,
>    I need to create a few clear examples).

The single-store shortcut is actually pretty important, because it is
what turns a *lot* of local variables from stack memory things into
pseudos. That's partly because the sparse optimizations aren't all
that smart.

Sparse code gen sometimes looks really good, but it's really largely
due to SSA really being a wonderful model. It makes some "complex"
optimizations magically trivial.  But outside of those things, sparse
really is pretty damn stupid.

I actually would whole-heartedly support a "all local variables are
initialized to zero" mode, which would get rid of a lot of these
undefined cases.

But it would also be good to just warn about it - the problem is that
sparse doesn't even necessarily *understand* when it generates garbage
from garbage input, because the transformations are so mindless, and
the SSA code works without ever understanding the notion of truly
"dominating" operations.

                   Linus

Re: Potential incorrect simplification

[Luc Van Oostenryck]

On Tue, Mar 28, 2017 at 11:02:32AM -0700, Linus Torvalds wrote:
> On Tue, Mar 28, 2017 at 10:00 AM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> >
> > I agree, of course, but I think there is a problem anyway.
> 
> Yes. I just wanted to point out that it's not the simplification phase
> that is the problem, and that sparse is technically correct (for some
> definition of "technically" ;)

Ok :)
 
> > The problem here with this %r4 is created by the single-store
> > shortcut which replace all loads with the same value as the one
> > used for the unique store (even loads that are not dominated
> > by the store). Fair enough, don't use uninitialized vars.
> 
> Yeah.
> 
> Personally, I absolutely detest a lot of the undefined C corner cases.
> I'm a huge fan of the language, but almost all of the the "undefined
> behavior" in C is a huge mistake.

And things become even more fun once you try to understand the standard.
 
> ...
>
> > But what annoys me really is that:
> > -) once you remove the single-store shortcut, it seems there is
> >    other problems (I just saw it by doing some code comparison,
> >    I need to create a few clear examples).
> 
> The single-store shortcut is actually pretty important, because it is
> what turns a *lot* of local variables from stack memory things into
> pseudos. That's partly because the sparse optimizations aren't all
> that smart.

Everytime I look at this part of the code, I think the same:
  why turn all vars into stack memory to have to turn them later
  into pseudos?
 
> Sparse code gen sometimes looks really good, but it's really largely
> due to SSA really being a wonderful model. It makes some "complex"
> optimizations magically trivial.  But outside of those things, sparse
> really is pretty damn stupid.
> 
> I actually would whole-heartedly support a "all local variables are
> initialized to zero" mode, which would get rid of a lot of these
> undefined cases.

It shouldn't be hard but then things like single-store shortcut then
become useless.

> But it would also be good to just warn about it

I have a trivial patch for that (just look at ep->entry->bb->needs)
but for the moment it's not yet useful because there is too much
problems there (but maybe I should look at it again).

> - the problem is that
> sparse doesn't even necessarily *understand* when it generates garbage
> from garbage input, because the transformations are so mindless, and
> the SSA code works without ever understanding the notion of truly
> "dominating" operations.
> 
>                    Linus

Re: Potential incorrect simplification

[Linus Torvalds]

On Tue, Mar 28, 2017 at 1:27 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> On Tue, Mar 28, 2017 at 11:02:32AM -0700, Linus Torvalds wrote:
>>
>> The single-store shortcut is actually pretty important, because it is
>> what turns a *lot* of local variables from stack memory things into
>> pseudos. That's partly because the sparse optimizations aren't all
>> that smart.
>
> Everytime I look at this part of the code, I think the same:
>   why turn all vars into stack memory to have to turn them later
>   into pseudos?

Oh, you absolutely *cannot* turn them into pseudo's directly.

A pseudo is a "register", and in SSA format. Local variables are not
registers, and do not honor SSA.

So local variables are very much *not* pseudos at any time. Local
variables can have their address taken, local variables can be
assigned multiple times, local variables can have complex types, none
of which is pseudo-like behavior.

Now, some *very* limited cases of local variables end up being
trivially very similar to pseudos, and those simple cases get turned
into pseudos. But that only happens for the simple cases - when their
address is not taken or used, and when they only have a single
assignment to them.

But local variables do not start out as pseudos, exactly because the
pseudo case is a very very very limited case of the full local
variable case.

                        Linus

Re: Potential incorrect simplification

[Dibyendu Majumdar]

Hi Linus,

On 28 March 2017 at 17:20, Linus Torvalds <torvalds@linux-foundation.org> wrote:
> On Tue, Mar 28, 2017 at 7:19 AM, Dibyendu Majumdar
> <mobile@majumdar.org.uk> wrote:
>>
>> Well the unsimplified output is correct. The problem appears after
>> simplification.
>
> No. The unsimplified output has the exact same bug:
>
>   main:
>   .L0:
>         <entry-point>
>         load.32     %r1 <- 0[s3]
>         shl.32      %r2 <- $1, $6
>         and.32      %r3 <- %r1, $-65
>
> That "load.32" loads an uninitialized value from the stack.
>
> The simplification then just simplifies the uninitialized load to just
> be an uninitialized pseudo instead. Exact same code.
>
> And arguably both unsimplified and simplified code is "correct" in the
> sense that it's exactly what the original source code does:
>
>    s3.onebit = 1;
>

I think that the unsimplified output is correct in that it is doing
what the C code says. Because if you look at the C code, the code is
only accessing a field that has been initialized prior to access - so
I do not think this counts as undefined behaviour. I am unable to find
the wording in the C standard that would make this clear one way or
another, but my reading of the standard is that the C code is legal.

I understand that to the simplification phase the first load looks
like load of undefined value - but that is not the semantic of the C
code that led to it.

I checked that clang generates the same sequence of instructions as
sparse when optimization is switched off - but turning on optimization
gets rid of all the code except for the return.

Thanks and Regards
Dibyendu

Re: Potential incorrect simplification

[Luc Van Oostenryck]

On Tue, Mar 28, 2017 at 02:57:01PM -0700, Linus Torvalds wrote:
> On Tue, Mar 28, 2017 at 1:27 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> > On Tue, Mar 28, 2017 at 11:02:32AM -0700, Linus Torvalds wrote:
> >>
> >> The single-store shortcut is actually pretty important, because it is
> >> what turns a *lot* of local variables from stack memory things into
> >> pseudos. That's partly because the sparse optimizations aren't all
> >> that smart.
> >
> > Everytime I look at this part of the code, I think the same:
> >   why turn all vars into stack memory to have to turn them later
> >   into pseudos?
> 
> Oh, you absolutely *cannot* turn them into pseudo's directly.

No no, of course. I was just thinking loud about how easy it would
be to simplify the case of simple local variables whose address is
not taken.
 
> A pseudo is a "register", and in SSA format. Local variables are not
> registers, and do not honor SSA.
> 
> So local variables are very much *not* pseudos at any time. Local
> variables can have their address taken, local variables can be
> assigned multiple times, local variables can have complex types, none
> of which is pseudo-like behavior.
> 
> Now, some *very* limited cases of local variables end up being
> trivially very similar to pseudos, and those simple cases get turned
> into pseudos. But that only happens for the simple cases - when their
> address is not taken or used, and when they only have a single
> assignment to them.
> 
> But local variables do not start out as pseudos, exactly because the
> pseudo case is a very very very limited case of the full local
> variable case.

I was not thinking to turn them directly into pseudos, just to recognize 
that they will turn into pseudo and this is useless to turn them into
stack memory. So multiple assignmement would be OK, but having its 
address taken would not and being an array would also not be OK.
I have no idea if it would simplify or speedup things though.

-- Luc

Re: Potential incorrect simplification

[Christopher Li]

On Tue, Mar 28, 2017 at 12:20 PM, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
> On Tue, Mar 28, 2017 at 7:19 AM, Dibyendu Majumdar
> <mobile@majumdar.org.uk> wrote:
>>
>> Well the unsimplified output is correct. The problem appears after
>> simplification.
>
> No. The unsimplified output has the exact same bug:
>
>   main:
>   .L0:
>         <entry-point>
>         load.32     %r1 <- 0[s3]
>         shl.32      %r2 <- $1, $6
>         and.32      %r3 <- %r1, $-65
>
> That "load.32" loads an uninitialized value from the stack.
>
> The simplification then just simplifies the uninitialized load to just
> be an uninitialized pseudo instead. Exact same code.
>
> And arguably both unsimplified and simplified code is "correct" in the
> sense that it's exactly what the original source code does:
>
>    s3.onebit = 1;
>
> becomes
>
>         and.32      %r3 <- %r4, $-65
>         or.32       %r4 <- %r3, $64

Sorry I wasn't able to participate this discussion earlier. I am catching
up at the important sparse mailing list discussion. This is one of them.

This has puzzle me for a long time. From the looks it seems %4 was
used before it was define. Is that legal SSA form?

To answer my own question I have done some research myself and
ask some local expert who point me to more literature on the topic. I
would like to share my findings.

My conclusion so far is that, that is *not* valid SSA form regarding the
usage of %r4. Basically the %r4 on the RHS and the %r4 on the LHS
are *not* the same %r4. It has the problem of %r4 was use before
define.

It comes down to, in proper SSA form, the default value from the
uninitialized value is count as one (implicit) define as well.

This implicit define is *required* duo to the placement of phi function
and the dominance property of SSA.

BTW, the beginning of the loop is likely the DF because it
has one back incoming edge on top of the loop entrance.

There is online links for the above two statement so I don't need to
quote books
http://marcusdenker.de/talks/08CC/08IntroSSA.pdf
=====================================
Φ-Functions are placed in all basic blocks of the
Dominance Frontier.

Dominance Property of SSA:
1. If x is used in a Phi-function in block N,
then the definition of x dominates *every* <==== notice "every"
predecessor of N.
2. If x is used in a non-Phi statement in N,
then the definition of x dominates N
======================================

There is actually not many books explicit discuss handle
of uninitialized variables. The best explicit description I can
find is in this book
"modern compiler implementation in java" by Andrew W. Appel
Chapter 19.1 page 402. After 6 list item of Path-convergence
criterion (of phi function).

Quote: =================
We consider the start node to contain an implicit definition of
*every* variable., either because the variable may be a formal
parameter or to represent the notion of a <-- uninitialized with
special cases.
====================

Also, it was mention in the book, the CFG transformation need
to make sure the dominance property of SSA can not be broken.
If one transformation broke the dominance property of SSA, that
transformation can't be done safely.

That lead to our infamous "crazy programmer" warning.
In the crazy programmer warning we have "add %r1 <- %r1, 4"
That already means, we have done some transformation
breaking the dominance property of SSA, that transformation
shouldn't be done.

Again, I am *not* an expert on compilers. I am still learning
compilers so that I want sparse do the right things. If I make a
mistake, I am very happy that some one please point it out to
me.

Chris

Re: Potential incorrect simplification

[Luc Van Oostenryck]

On Sun, Aug 06, 2017 at 08:46:10AM -0400, Christopher Li wrote:
> On Tue, Mar 28, 2017 at 12:20 PM, Linus Torvalds
> > becomes
> >
> >         and.32      %r3 <- %r4, $-65
> >         or.32       %r4 <- %r3, $64
> 
> Sorry I wasn't able to participate this discussion earlier. I am catching
> up at the important sparse mailing list discussion. This is one of them.
> 
> This has puzzle me for a long time. From the looks it seems %4 was
> used before it was define. Is that legal SSA form?

What do you mean exactly by "legal SSA form"?

As I've already tried to explain you several times:
	it's a *symptom* that something have been wrong, either:
	- the initial code had some undefined variables
	- it's an internal bug.

In both cases you can't do anymore 'normal' processing on it.
In this sense it's "illegal".

The other way to see it is something like: "ok, this means that the
pseudo was not initialized" (and ignore the internal bug aspect) and
then process it as such (for example choose any value you like for it).
You can call this "a new/legal SSA form" if you like but it will only
confuse discussion and won't change it's nature.

-- Luc

Re: Potential incorrect simplification

[Christopher Li]

On Sun, Aug 6, 2017 at 10:00 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>> Sorry I wasn't able to participate this discussion earlier. I am catching
>> up at the important sparse mailing list discussion. This is one of them.
>>
>> This has puzzle me for a long time. From the looks it seems %4 was
>> used before it was define. Is that legal SSA form?
>
> What do you mean exactly by "legal SSA form"?

Legal SSA form means it preserve the normal SSA
properties. E.g. the dominance property of SSA.

> As I've already tried to explain you several times:
>         it's a *symptom* that something have been wrong, either:
>         - the initial code had some undefined variables

The source code has some variable uninitialized is still valid
C source code. In such condition the compiler produce transformation
that break the dominance property of SSA is wrong IMHO.

>         - it's an internal bug.
>
> In both cases you can't do anymore 'normal' processing on it.
> In this sense it's "illegal".

I mean the transformation that break the SSA dominance property
is illegal. The source code is legal to have uninitialized values. When
we convert the memory variable to pseudo, we should take into account
that uninitialized variable has one implicit initial define value
"uninitialized".

In other words, we shouldn't produce the IR that use before define like
this:
         and.32      %r3 <- %r4, $-65
         or.32       %r4 <- %r3, $64

> The other way to see it is something like: "ok, this means that the
> pseudo was not initialized" (and ignore the internal bug aspect) and

No, in SSA world, there is no pseudo is not initialized. Please refer back
Dominance Property of SSA:
1. If x is used in a Phi-function in block N,
then the definition of x dominates *every* <==== notice "every"
predecessor of N.

It has incoming edge to the phi node, it need to be defined.
It means that you can't just do what ever you want with that
edge. You can pick a what ever initial value for the uninitialized
value, you can't just pretend that uninitialized edge does not exist
and do whatever you want with it.

> then process it as such (for example choose any value you like for it).
> You can call this "a new/legal SSA form" if you like but it will only
> confuse discussion and won't change it's nature.

OK, points taken. Replace "illegal SSA from" with "SSA form that violate
the SSA dominance property" so that we are clear what we are talking
about here.

Chris

Re: Potential incorrect simplification

[Christopher Li]

On Sun, Aug 6, 2017 at 10:24 AM, Christopher Li <sparse@chrisli.org> wrote:
> The source code has some variable uninitialized is still valid
> C source code. In such condition the compiler produce transformation
> that break the dominance property of SSA is wrong IMHO.

Clarify, I mean the compiler is wrong. The source code has
uninitialized variable is still legal in the C stander.

>> The other way to see it is something like: "ok, this means that the
>> pseudo was not initialized" (and ignore the internal bug aspect) and
>
> No, in SSA world, there is no pseudo is not initialized. Please refer back

Let me rephrase, because I notice the I use the word "initialized" is not
precise here.

In SSA word, there is no pseudo is not *defined*.

Chris

> Dominance Property of SSA:
> 1. If x is used in a Phi-function in block N,
> then the definition of x dominates *every* <==== notice "every"
> predecessor of N.
>
> It has incoming edge to the phi node, it need to be defined.
> It means that you can't just do what ever you want with that
> edge. You can pick a what ever initial value for the uninitialized
> value, you can't just pretend that uninitialized edge does not exist
> and do whatever you want with it.
>
>> then process it as such (for example choose any value you like for it).
>> You can call this "a new/legal SSA form" if you like but it will only
>> confuse discussion and won't change it's nature.
>
> OK, points taken. Replace "illegal SSA from" with "SSA form that violate
> the SSA dominance property" so that we are clear what we are talking
> about here.
>
> Chris

Re: Potential incorrect simplification

[Luc Van Oostenryck]

On Sun, Aug 06, 2017 at 10:24:30AM -0400, Christopher Li wrote:
> On Sun, Aug 6, 2017 at 10:00 AM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> >> Sorry I wasn't able to participate this discussion earlier. I am catching
> >> up at the important sparse mailing list discussion. This is one of them.
> >>
> >> This has puzzle me for a long time. From the looks it seems %4 was
> >> used before it was define. Is that legal SSA form?
> >
> > What do you mean exactly by "legal SSA form"?
> 
> Legal SSA form means it preserve the normal SSA
> properties. E.g. the dominance property of SSA.

And under which conditions are SSA properties *defined*?
 
> > As I've already tried to explain you several times:
> >         it's a *symptom* that something have been wrong, either:
> >         - the initial code had some undefined variables
> 
> The source code has some variable uninitialized is still valid
> C source code.

It's valid in the sense that code is written like this and
compilers (and checkers!) should better try to process it
in a usefull manner.

But accessing such variable is *undefined behaviour*.

> In such condition the compiler produce transformation
> that break the dominance property of SSA is wrong IMHO.

The SSA properties are not defined for this kind of input.
It's not that the compiler that produce a transformation
that break the property, the property wasn't there/defined
since the beginning. The compiler only (maybe) made it obvious
that the input is wrong.

> >         - it's an internal bug.
> >
> > In both cases you can't do anymore 'normal' processing on it.
> > In this sense it's "illegal".
> 
> I mean the transformation that break the SSA dominance property
> is illegal. The source code is legal to have uninitialized values.

Your use of 'legal/illegal' only create dramatic black/white
situations which doesn't help you to understand the situation.
You can call it 'legal' but its semantic is undefined.
If its semantic is not defined, it means that all those nice
discussions about breaking SSA property is meaningless.

> When
> we convert the memory variable to pseudo, we should take into account
> that uninitialized variable has one implicit initial define value
> "uninitialized".
> 
> In other words, we shouldn't produce the IR that use before define like
> this:
>          and.32      %r3 <- %r4, $-65
>          or.32       %r4 <- %r3, $64

Good.
You can avoid to produce such IR if you first detect uninitialized
variables (and emit a diagnostic and stop things there).
Do you a good plan to detect uninitialized variables?

> > The other way to see it is something like: "ok, this means that the
> > pseudo was not initialized" (and ignore the internal bug aspect) and
> 
> No, in SSA world, there is no pseudo is not initialized.

In textbook and articles, yes, they suppose that the input is well
defined and leave others input as an exercise for the reader.

> Please refer back
> Dominance Property of SSA:
> 1. If x is used in a Phi-function in block N,
> then the definition of x dominates *every* <==== notice "every"
> predecessor of N.

For input without undefined behaviour, yes surely.

> It has incoming edge to the phi node, it need to be defined.

And what happen if it is in fact undefined?

> It means that you can't just do what ever you want with that
> edge. You can pick a what ever initial value for the uninitialized
> value, you can't just pretend that uninitialized edge does not exist
> and do whatever you want with it.
> 
> > then process it as such (for example choose any value you like for it).
> > You can call this "a new/legal SSA form" if you like but it will only
> > confuse discussion and won't change it's nature.
> 
> OK, points taken. Replace "illegal SSA from" with "SSA form that violate
> the SSA dominance property" so that we are clear what we are talking
> about here.

No.
The only interesting things are:
  "what do we do when we have an input that is not well formed, undefined"
and even more interesting:
  "how do we *detect* this and how do we emit a diagnostic that is useful".

Also, let's not forget that the (primary) goal of a compiler is to
produce (good) code (for well defined inputs). But most significant
ones doesn't stop there and try hard to produce usefull diagnostic for
the other inputs. And sparse, as a semantic *checker*, should be even
more concerned by this aspect.

-- Luc

Re: Potential incorrect simplification

[Christopher Li]

On Sun, Aug 6, 2017 at 11:07 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>> Legal SSA form means it preserve the normal SSA
>> properties. E.g. the dominance property of SSA.
>
> And under which conditions are SSA properties *defined*?

Not sure I understand what you are asking:
Quote from previous email about the definition of the properties.

http://marcusdenker.de/talks/08CC/08IntroSSA.pdf
=====================================
Φ-Functions are placed in all basic blocks of the
Dominance Frontier.

Dominance Property of SSA:
1. If x is used in a Phi-function in block N,
then the definition of x dominates *every* <==== notice "every"
predecessor of N.
2. If x is used in a non-Phi statement in N,
then the definition of x dominates N
======================================

If we are asking when should we follow those properties.
I think *always*.


>
>> > As I've already tried to explain you several times:
>> >         it's a *symptom* that something have been wrong, either:
>> >         - the initial code had some undefined variables
>>
>> The source code has some variable uninitialized is still valid
>> C source code.
>
> It's valid in the sense that code is written like this and
> compilers (and checkers!) should better try to process it
> in a usefull manner.
>
> But accessing such variable is *undefined behaviour*.

That is true but not relevant. I am pointing out sparse does
incorrect transformation produce "usage before define"
IR, which break the SSA dominance property. Which
can be avoided.

>
>> In such condition the compiler produce transformation
>> that break the dominance property of SSA is wrong IMHO.
>
> The SSA properties are not defined for this kind of input.

That is just your view. It is clearly not the view in academia.

I think that is precise what is wrong here. Let's put away us
vs academia who is more correct. We can still discuss the
consequence of choose to breaking the property or not.

Given the condition input C code can have uninitialized variable

We have two design choice here.
1. Break the SSA dominance property. That is the current garbage
    in garbage out model.

    Let that face the consequence here:

    Because we choice to break the SSA dominance property.
    All those classic SSA based algorithm that relied on the
    SSA dominance property might break. Pretty much guarantee
    you can find the case to make it break.

   In is very annoying that I can't use classic SSA algorithm safely.

2. Do not break the SSA dominance property. Give the uninitialized
    variable an implicit defined as "uninitialized". That is the method
    describe in Appel's book. It is also the model gcc and llvm use as
    well as far as I can tell.

   The consequence is that , I can use the class SSA algorithm
   without worry about what consequence it might have breaking
   the SSA dominance property.


> It's not that the compiler that produce a transformation
> that break the property, the property wasn't there/defined
> since the beginning. The compiler only (maybe) made it obvious
> that the input is wrong.

That is just you view. See my analyse above.

> Your use of 'legal/illegal' only create dramatic black/white
> situations which doesn't help you to understand the situation.
> You can call it 'legal' but its semantic is undefined.
> If its semantic is not defined, it means that all those nice
> discussions about breaking SSA property is meaningless.

No, my definition is clearly defined. "add %r1 <- %r1, 4"
breaking the SSA dominance property as define above has
a clear answer yes or not. It is black and white.

The consequence is also black and white. Don't break it
we can safely use the classic ssa algorithm. Break it there
is no theory guarantee.

> Good.
> You can avoid to produce such IR if you first detect uninitialized
> variables (and emit a diagnostic and stop things there).
> Do you a good plan to detect uninitialized variables?

All variable start with a define value "uninitialized" unless clear
specified otherwise.
This method is already describe in the book I quote.

>
> In textbook and articles, yes, they suppose that the input is well
> defined and leave others input as an exercise for the reader.

It is not about textbook and etc.
It is about the consequence weather we can use the classic ssa
algorithm safely.

>> Please refer back
>> Dominance Property of SSA:
>> 1. If x is used in a Phi-function in block N,
>> then the definition of x dominates *every* <==== notice "every"
>> predecessor of N.
>
> For input without undefined behaviour, yes surely.

Please the analyse above. If you choice to break it, there is not
even a question you break it or not. It is very clearly defined.
You need to face the consequence.


>
>> It has incoming edge to the phi node, it need to be defined.
>
> And what happen if it is in fact undefined?

I am getting tired of repeat my self here. There is no undefined
here if we start every variable in the entry node with define to
uninitialized, unless specify otherwise.

Refer to the book for more detail description of the algorithm
how to convert to SSA. We don't need to reinvent the wheel.


> No.
> The only interesting things are:
>   "what do we do when we have an input that is not well formed, undefined"

See the above consequence reasoning.

> and even more interesting:
>   "how do we *detect* this and how do we emit a diagnostic that is useful".

We don't need to detect it. Every variable start with defined to uninitialized
unless specify otherwise.

> Also, let's not forget that the (primary) goal of a compiler is to
> produce (good) code (for well defined inputs). But most significant
> ones doesn't stop there and try hard to produce usefull diagnostic for
> the other inputs. And sparse, as a semantic *checker*, should be even
> more concerned by this aspect.

True but irrelevant to my discussion. My point is you make the choice,
you face the consequence. Our garbage in garbage out choice is not
a good one because I can't use classic ssa algorithms safely.


Chris

Re: Potential incorrect simplification

[Dibyendu Majumdar]

Hi,

I would like to assert that in the C code there was no attempt to
access uninitialized value. If you have a look at the original report
here:

http://marc.info/?l=linux-sparse&m=149070715427276&w=2

You will see that the C code assigns a value to the field before
attempting to access it as shown below.

s3.onebit = 1;
if(s3.onebit != 1){
}

It might be useful to step back and explore how should code be
generated for this such that it is not treated as uninitialized value.

Regards
Dibyendu

Re: Potential incorrect simplification

[Luc Van Oostenryck]

On Sun, Aug 06, 2017 at 11:51:24AM -0400, Christopher Li wrote:
> On Sun, Aug 6, 2017 at 11:07 AM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> >> Legal SSA form means it preserve the normal SSA
> >> properties. E.g. the dominance property of SSA.
> >
> > And under which conditions are SSA properties *defined*?
> 
> Not sure I understand what you are asking:
> Quote from previous email about the definition of the properties.
> 
> http://marcusdenker.de/talks/08CC/08IntroSSA.pdf
> =====================================
> Φ-Functions are placed in all basic blocks of the
> Dominance Frontier.
> 
> Dominance Property of SSA:
> 1. If x is used in a Phi-function in block N,
> then the definition of x dominates *every* <==== notice "every"
> predecessor of N.
> 2. If x is used in a non-Phi statement in N,
> then the definition of x dominates N
> ======================================
> 
> If we are asking when should we follow those properties.
> I think *always*.

It's typically things that are not discussed about in papers.
They assume proper, well defined inputs (or even simplified
situation only) or that it is easy enough to force it to be
well defined that it's not useful to talk about it.
 
> >> > As I've already tried to explain you several times:
> >> >         it's a *symptom* that something have been wrong, either:
> >> >         - the initial code had some undefined variables
> >>
> >> The source code has some variable uninitialized is still valid
> >> C source code.
> >
> > It's valid in the sense that code is written like this and
> > compilers (and checkers!) should better try to process it
> > in a usefull manner.
> >
> > But accessing such variable is *undefined behaviour*.
> 
> That is true but not relevant.

It's very relevant because its semantic is not defined.
In other words, you can do anything you like (for the
standard point of view).
It's also relevant because you will then probably want 
to avoid to (generate code which) access such vars *and*
want to detect them.

> >> In such condition the compiler produce transformation
> >> that break the dominance property of SSA is wrong IMHO.
> >
> > The SSA properties are not defined for this kind of input.
> 
> That is just your view. It is clearly not the view in academia.

Really?
 

> 2. Do not break the SSA dominance property. Give the uninitialized
>     variable an implicit defined as "uninitialized". That is the method
>     describe in Appel's book. It is also the model gcc and llvm use as
>     well as far as I can tell.

This is also what I'm doing for various reasons.
But once you initialize it with a special value, by definition,
it's not uninitialized anymore.
 
> >> It has incoming edge to the phi node, it need to be defined.
> >
> > And what happen if it is in fact undefined?
> 
> I am getting tired of repeat my self here. There is no undefined
> here if we start every variable in the entry node with define to
> uninitialized, unless specify otherwise.

I was referring to the 'internal bug' case.
The current "crazy programmer" warning is as much a kind of
assert on the internal consistency of the SSA form than a detection
of uninitialized variables.
 
> Refer to the book for more detail description of the algorithm
> how to convert to SSA. We don't need to reinvent the wheel.

Who's talking about reinventing the wheel?
Your question was about "is it legal SSA form" (in the current sparse code)
and I explained to you that it was the symptom of a problem.

Nobody is claiming that the current situation is a good one.

> > No.
> > The only interesting things are:
> >   "what do we do when we have an input that is not well formed, undefined"
> 
> See the above consequence reasoning.
> 
> > and even more interesting:
> >   "how do we *detect* this and how do we emit a diagnostic that is useful".
> 
> We don't need to detect it. Every variable start with defined to uninitialized
> unless specify otherwise.

If you give a special distinguished value to uninitialized vars (or
to every until they receive a real one or the same to pseudos) then
you can detect them when you got this special distinguished value.
It's one method.

The *current* method is to check these self-definition cycles.
It's an inferior method IMO (and apparently you too) but it has
the advantage to be simple *and* to do an internal self-consistency
check at the same time.

Do I mean that we should keep the current method?
Not at all.
Do I mean that we should keep thsi check for the self-consistency
check? Yes, probably, at least as an option.
Is there some better way to do this sort of check?
Maybe and it will also depends on the details of the implementation.
 
> > Also, let's not forget that the (primary) goal of a compiler is to
> > produce (good) code (for well defined inputs). But most significant
> > ones doesn't stop there and try hard to produce usefull diagnostic for
> > the other inputs. And sparse, as a semantic *checker*, should be even
> > more concerned by this aspect.
> 
> True but irrelevant to my discussion. My point is you make the choice,
> you face the consequence. Our garbage in garbage out choice is not
> a good one because I can't use classic ssa algorithms safely.

But if there is an internal bug, this algo will also not be safe,
so the utility for some self-consistency/validity checks.

Next time, instead of asking a question like "is it legal ..."
simply state something like:
 "the current situation with this and that is annoying because
  this and that. I'm planning to change it by this so that ..."
and it will be much more easier for everybody to understand what
you're really asking for.

-- Luc 

Re: Potential incorrect simplification

[Luc Van Oostenryck]

On Sun, Aug 6, 2017 at 5:52 PM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
> Hi,
>
> I would like to assert that in the C code there was no attempt to
> access uninitialized value. If you have a look at the original report
> here:
>
> http://marc.info/?l=linux-sparse&m=149070715427276&w=2
>
> You will see that the C code assigns a value to the field before
> attempting to access it as shown below.
>
> s3.onebit = 1;
> if(s3.onebit != 1){
> }

True but this should be solved by patch b1672eab399fdce2c050e8aa07767489a2071981
available since -rc1.
Isn't it the case?

-- Luc

Re: Potential incorrect simplification

[Dibyendu Majumdar]

On 6 August 2017 at 17:56, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> On Sun, Aug 6, 2017 at 5:52 PM, Dibyendu Majumdar
> <mobile@majumdar.org.uk> wrote:
>> Hi,
>>
>> I would like to assert that in the C code there was no attempt to
>> access uninitialized value. If you have a look at the original report
>> here:
>>
>> http://marc.info/?l=linux-sparse&m=149070715427276&w=2
>>
>> You will see that the C code assigns a value to the field before
>> attempting to access it as shown below.
>>
>> s3.onebit = 1;
>> if(s3.onebit != 1){
>> }
>
> True but this should be solved by patch b1672eab399fdce2c050e8aa07767489a2071981
> available since -rc1.
> Isn't it the case?
>

Wouldn't have thought so - as the variable is not initialized at the
point of declaration. The assignment occurs after declaring the struct
variable s3.

I haven't tried that patch though.

Regards
Dibyendu

Re: Potential incorrect simplification

[Luc Van Oostenryck]

On Sun, Aug 6, 2017 at 7:04 PM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
> Wouldn't have thought so - as the variable is not initialized at the
> point of declaration. The assignment occurs after declaring the struct
> variable s3.

IIRC, this patch was written specifically for the case you reported here.

> I haven't tried that patch though.

You'll need the full series:
https://github.com/lucvoo/sparse/tree/fix-bitfield-init-v3

-- Luc

Re: Potential incorrect simplification

[Dibyendu Majumdar]

On 6 August 2017 at 18:45, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> On Sun, Aug 6, 2017 at 7:04 PM, Dibyendu Majumdar
> <mobile@majumdar.org.uk> wrote:
>> Wouldn't have thought so - as the variable is not initialized at the
>> point of declaration. The assignment occurs after declaring the struct
>> variable s3.
>
> IIRC, this patch was written specifically for the case you reported here.
>
>> I haven't tried that patch though.
>
> You'll need the full series:
> https://github.com/lucvoo/sparse/tree/fix-bitfield-init-v3
>

I will have a look at it. I did report separately the issue of not
zeroing out structs when they are initialized and the change you
mentioned earlier looks more for addressing that issue.

Regards
Dibyendu

Re: Potential incorrect simplification

[Luc Van Oostenryck]

On Sun, Aug 6, 2017 at 7:58 PM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
> On 6 August 2017 at 18:45, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
>> On Sun, Aug 6, 2017 at 7:04 PM, Dibyendu Majumdar
>> <mobile@majumdar.org.uk> wrote:
>>> Wouldn't have thought so - as the variable is not initialized at the
>>> point of declaration. The assignment occurs after declaring the struct
>>> variable s3.
>>
>> IIRC, this patch was written specifically for the case you reported here.
>>
>>> I haven't tried that patch though.
>>
>> You'll need the full series:
>> https://github.com/lucvoo/sparse/tree/fix-bitfield-init-v3
>>
>
> I will have a look at it. I did report separately the issue of not
> zeroing out structs when they are initialized and the change you
> mentioned earlier looks more for addressing that issue.

Indeed.
I mixed up both (or more exactly, I thought it solved both).

-- Luc

Re: Potential incorrect simplification

[Dibyendu Majumdar]

On 6 August 2017 at 19:15, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> On Sun, Aug 6, 2017 at 7:58 PM, Dibyendu Majumdar
> <mobile@majumdar.org.uk> wrote:
>> On 6 August 2017 at 18:45, Luc Van Oostenryck
>> <luc.vanoostenryck@gmail.com> wrote:
>>> On Sun, Aug 6, 2017 at 7:04 PM, Dibyendu Majumdar
>>> <mobile@majumdar.org.uk> wrote:
>>>> Wouldn't have thought so - as the variable is not initialized at the
>>>> point of declaration. The assignment occurs after declaring the struct
>>>> variable s3.
>>>
>>> IIRC, this patch was written specifically for the case you reported here.
>>>
>>>> I haven't tried that patch though.
>>>
>>> You'll need the full series:
>>> https://github.com/lucvoo/sparse/tree/fix-bitfield-init-v3
>>>
>>
>> I will have a look at it. I did report separately the issue of not
>> zeroing out structs when they are initialized and the change you
>> mentioned earlier looks more for addressing that issue.
>
> Indeed.
> I mixed up both (or more exactly, I thought it solved both).
>

The tests in your tree all are for initialization scenario - are you
sure you fixed the issue mentioned in this thread? I will check later
tonight and report back.

Regards
Dibyendu

Re: Potential incorrect simplification

[Luc Van Oostenryck]

On Sun, Aug 06, 2017 at 07:18:20PM +0100, Dibyendu Majumdar wrote:
> On 6 August 2017 at 19:15, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> > On Sun, Aug 6, 2017 at 7:58 PM, Dibyendu Majumdar
> > <mobile@majumdar.org.uk> wrote:
> >> On 6 August 2017 at 18:45, Luc Van Oostenryck
> >> <luc.vanoostenryck@gmail.com> wrote:
> >>> On Sun, Aug 6, 2017 at 7:04 PM, Dibyendu Majumdar
> >>> <mobile@majumdar.org.uk> wrote:
> >>>> Wouldn't have thought so - as the variable is not initialized at the
> >>>> point of declaration. The assignment occurs after declaring the struct
> >>>> variable s3.
> >>>
> >>> IIRC, this patch was written specifically for the case you reported here.
> >>>
> >>>> I haven't tried that patch though.
> >>>
> >>> You'll need the full series:
> >>> https://github.com/lucvoo/sparse/tree/fix-bitfield-init-v3
> >>>
> >>
> >> I will have a look at it. I did report separately the issue of not
> >> zeroing out structs when they are initialized and the change you
> >> mentioned earlier looks more for addressing that issue.
> >
> > Indeed.
> > I mixed up both (or more exactly, I thought it solved both).
> >
> 
> The tests in your tree all are for initialization scenario - are you
> sure you fixed the issue mentioned in this thread? I will check later
> tonight and report back.

No no.
By "Indeed, I mixed up both" I meant that you're right and that this patch
doesn't solve your issue here.

The issue here is a problem of (partially)-uninitialized var (only
s3.onebit is initialized but the whole s3 is first read) coupled
by some missing simplification of masking operation.
When using a version that handle more correctly uninitialized vars,
we get the following:
	foo:
	.L0:
		<entry-point>
		and.32      %r2 <- UNDEF, $-65
		or.32       %r3 <- %r2, $64
		lsr.32      %r4 <- %r3, $6
		cast.1      %r5 <- (32) %r4
		cast.32     %r6 <- (1) %r5
		setne.32    %r7 <- %r6, $1
		ret.32      %r7 

The UNDEF is for the load of s3 and the masking should get rid of it
but doesn't (yet).

-- Luc

Re: Potential incorrect simplification

[Christopher Li]

On Sun, Aug 6, 2017 at 12:51 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> On Sun, Aug 06, 2017 at 11:51:24AM -0400, Christopher Li wrote:
>> On Sun, Aug 6, 2017 at 11:07 AM, Luc Van Oostenryck
>> <luc.vanoostenryck@gmail.com> wrote:
>> >> Legal SSA form means it preserve the normal SSA
>> >> properties. E.g. the dominance property of SSA.
>> >
>> > And under which conditions are SSA properties *defined*?
>>
>> Not sure I understand what you are asking:
>> Quote from previous email about the definition of the properties.
>>
>> http://marcusdenker.de/talks/08CC/08IntroSSA.pdf
>> =====================================
>> Φ-Functions are placed in all basic blocks of the
>> Dominance Frontier.
>>
>> Dominance Property of SSA:
>> 1. If x is used in a Phi-function in block N,
>> then the definition of x dominates *every* <==== notice "every"
>> predecessor of N.
>> 2. If x is used in a non-Phi statement in N,
>> then the definition of x dominates N
>> ======================================
>>
>> If we are asking when should we follow those properties.
>> I think *always*.
>
> It's typically things that are not discussed about in papers.
> They assume proper, well defined inputs (or even simplified
> situation only) or that it is easy enough to force it to be
> well defined that it's not useful to talk about it.

Your understanding is wrong. The book I quote already clearly
discuss how to handle uninitialized variable in SSA form. I quote
it in the email before and I will quote it again here:

quote my email :----------------
There is actually not many books explicit discuss handle
of uninitialized variables. The best explicit description I can
find is in this book
"modern compiler implementation in java" by Andrew W. Appel
Chapter 19.1 page 402. After 6 list item of Path-convergence
criterion (of phi function).

Quote: =================
We consider the start node to contain an implicit definition of
*every* variable., either because the variable may be a formal
parameter or to represent the notion of a <-- *uninitialized* with
special cases.
====================
----------------------------



>> That is true but not relevant.
>
> It's very relevant because its semantic is not defined.
> In other words, you can do anything you like (for the
> standard point of view).

You can keep on arguing semantic is not defined.
When you have "usage before define" like the following:
          and.32      %r3 <- %r4, $-65
          or.32       %r4 <- %r3, $64

It has direct consequence classic SSA algorithm can
not be done safely on later stage.

> It's also relevant because you will then probably want
> to avoid to (generate code which) access such vars *and*
> want to detect them.

Do you know that your request is unreasonable?

Detecting the usage of uninitialized variable in a program
is equivalent of the Turing halting problem. It is not Turing
commutable, there is no easy way to do it correctly in all
the situation.

It is also irreverent if I want to give warning to uninitialized variable
usage or not. I want sparse don't generate code like:
          and.32      %r3 <- %r4, $-65
          or.32       %r4 <- %r3, $64

Do it more like the gcc or llvm does. Don't break the dominance
property of SSA for no good reason.

>
>> >> In such condition the compiler produce transformation
>> >> that break the dominance property of SSA is wrong IMHO.
>> >
>> > The SSA properties are not defined for this kind of input.
>>
>> That is just your view. It is clearly not the view in academia.
>
> Really?

Of course. There is already books rewritten about how to handle
uninitialized variable. You keep on arguing this thing is not
defined. Those people on the academia does not know what they
are doing, they haven't discuss how to handle uninitialized variable.
It is clearly not the case. The book is the prove.

If you follow the definition I quote, one for phi node,  two for SSA.
You can actually deduce the same conclusion yourself. If you
have the patient for it, I can deduce it step by step for you.


>> 2. Do not break the SSA dominance property. Give the uninitialized
>>     variable an implicit defined as "uninitialized". That is the method
>>     describe in Appel's book. It is also the model gcc and llvm use as
>>     well as far as I can tell.
>
> This is also what I'm doing for various reasons.
> But once you initialize it with a special value, by definition,
> it's not uninitialized anymore.

That is useless argument. You can call it what you want.
It  does not change the fact that:
          and.32      %r3 <- %r4, $-65
          or.32       %r4 <- %r3, $64

Break the SSA dominance property. We shouldn't generate code
like that. We do have a choice not to do it this way.

> I was referring to the 'internal bug' case.
> The current "crazy programmer" warning is as much a kind of
> assert on the internal consistency of the SSA form than a detection
> of uninitialized variables.

In my book, we shouldn't get into that case at all. When we have
          add %r1 <- %r1, 4
We already screw up the SSA form. We should look into what
transformation produce that illegal SSA form and make sure it does
not produce the IR violate the SSA property.


>
>> Refer to the book for more detail description of the algorithm
>> how to convert to SSA. We don't need to reinvent the wheel.
>
> Who's talking about reinventing the wheel?
> Your question was about "is it legal SSA form" (in the current sparse code)
> and I explained to you that it was the symptom of a problem.

Yes, you keep on arguing this is the result of uninitialized variable.
Nothing to worry about.

My point about not reinventing the wheel is that, there is clearly
SSA conversion algorithms clearly take into the account that variable
can be uninitialized, how to do the SSA conversion in that case.
If we use those algorithms, it will get us closer to the gcc and llvm
IR in terms of uninitialized variables.

There is no reason to break the SSA property for no good reason.
It is no like we don't have a choice and we have to break it. We are
willingly break it because we don't know better about SSA.

> Nobody is claiming that the current situation is a good one.

Great, that is some step towards consensus.

If we agree sparse shouldn't generate the following.

          and.32      %r3 <- %r4, $-65
          or.32       %r4 <- %r3, $64

Let's fix it then.

We can start with the proper placement of the phi node and use
the algorithm in the Appel book for example. That is a good starting
point.

>> We don't need to detect it. Every variable start with defined to uninitialized
>> unless specify otherwise.
>
> If you give a special distinguished value to uninitialized vars (or
> to every until they receive a real one or the same to pseudos) then
> you can detect them when you got this special distinguished value.
> It's one method.
>
> The *current* method is to check these self-definition cycles.
> It's an inferior method IMO (and apparently you too) but it has
> the advantage to be simple *and* to do an internal self-consistency
> check at the same time.
>
> Do I mean that we should keep the current method?
> Not at all.
> Do I mean that we should keep thsi check for the self-consistency
> check? Yes, probably, at least as an option.

Well, let's agree on we shouldn't produce
          and.32      %r3 <- %r4, $-65
          or.32       %r4 <- %r3, $64

first at principle level.

Then how to fix it is just technical details.
I care less about warning uninitialized variable warning, which
we can't do a perfect job any way. I am more worry about those
screw up SSA forms.

> Is there some better way to do this sort of check?
> Maybe and it will also depends on the details of the implementation.

As I said the algorithm in Appel's books is a good starting point.
It clearly already consider the uninitialized variable situation and
give a solution for it.


>> True but irrelevant to my discussion. My point is you make the choice,
>> you face the consequence. Our garbage in garbage out choice is not
>> a good one because I can't use classic ssa algorithms safely.
>
> But if there is an internal bug, this algo will also not be safe,
> so the utility for some self-consistency/validity checks.

The impression I get from the previous discussion is that, we kind of
willfully do it and blame the source has uninitialized variable, without
realized that our internal IR transformation has serious problem of
breaking SSA property as well.

Now that RC5 is almost out of the door.  It is my intention to start this
discussion to clarify things and point out things I believe is wrong.
I know it is going to be a controversial topic :-)

> Next time, instead of asking a question like "is it legal ..."
> simply state something like:
>  "the current situation with this and that is annoying because
>   this and that. I'm planning to change it by this so that ..."
> and it will be much more easier for everybody to understand what
> you're really asking for.

Sure. I am just describing my mental model, how I come to that
conclusion. Previously I sense some thing is wrong, but I could
not articulate it clearly. It clearly shows in my our email discussion
as well.

Now I did more search and thing it very well through. I can point out
exactly what is wrong and why it is wrong. I already layout all my
necessarily material to support my argument in my first email.
I just keep referring back to it.

Chris

Re: Potential incorrect simplification

[Dibyendu Majumdar]

Hi Chris,

On 6 August 2017 at 19:35, Christopher Li <sparse@chrisli.org> wrote:
> If we agree sparse shouldn't generate the following.
>
>           and.32      %r3 <- %r4, $-65
>           or.32       %r4 <- %r3, $64
>
> Let's fix it then.
>

I agree that simplifications must not result in incorrect code (in my
case correct code is more valuable than efficient code) - and in this
particular example, the C code is legal and correct and this is not an
instance of an uninitialized variable because in the C code the
variable is assigned a value prior to it being accessed.

I am not sure that this is easy to fix though - as the original IR
does not capture the intent of the C program. Maybe you could have a
separate IR instruction to assign value to a bit field - rather than
using load/and/or sequence. This will enable the original IR to
reflect the intent of the C program more accurately and hopefully
enable the simplification phase can handle it correctly.

Regards
Dibyendu

Re: Potential incorrect simplification

[Luc Van Oostenryck]

On Sun, Aug 6, 2017 at 8:35 PM, Christopher Li <sparse@chrisli.org> wrote:
>>> That is true but not relevant.
>>
>> It's very relevant because its semantic is not defined.
>> In other words, you can do anything you like (for the
>> standard point of view).
>
> You can keep on arguing semantic is not defined.
> When you have "usage before define" like the following:
>           and.32      %r3 <- %r4, $-65
>           or.32       %r4 <- %r3, $64
>
> It has direct consequence classic SSA algorithm can
> not be done safely on later stage.

Who has said the contrary? me?

>> It's also relevant because you will then probably want
>> to avoid to (generate code which) access such vars *and*
>> want to detect them.
>
> Do you know that your request is unreasonable?

Uh? It's what all compilers do and what the current sparse *try* to do.

> Detecting the usage of uninitialized variable in a program
> is equivalent of the Turing halting problem. It is not Turing
> commutable, there is no easy way to do it correctly in all
> the situation.

"want to avoid" doesn't mean "will avoid in all such cases and only such cases".


>> This is also what I'm doing for various reasons.
>> But once you initialize it with a special value, by definition,
>> it's not uninitialized anymore.
>
> That is useless argument. You can call it what you want.

It's not an argument.

> It  does not change the fact that:
>           and.32      %r3 <- %r4, $-65
>           or.32       %r4 <- %r3, $64
>
> Break the SSA dominance property. We shouldn't generate code
> like that. We do have a choice not to do it this way.

Again, who said the contrary?

>> I was referring to the 'internal bug' case.
>> The current "crazy programmer" warning is as much a kind of
>> assert on the internal consistency of the SSA form than a detection
>> of uninitialized variables.
>
> In my book, we shouldn't get into that case at all. When we have
>           add %r1 <- %r1, 4
> We already screw up the SSA form.

Yes, it's called a 'bug'.

>>> Refer to the book for more detail description of the algorithm
>>> how to convert to SSA. We don't need to reinvent the wheel.
>>
>> Who's talking about reinventing the wheel?
>> Your question was about "is it legal SSA form" (in the current sparse code)
>> and I explained to you that it was the symptom of a problem.
>
> Yes, you keep on arguing this is the result of uninitialized variable.
> Nothing to worry about.

You asked a question about the *current* behaviour of sparse
and I explained the reason of this behaviour.
It's not because explain this that I'm also saying
"that is the correct behaviour and nothing must be changed about".

And you know that I don't think so because we already talked about it.
And I already said you that I have code that redo the SSA construction
and that this code doesn't have the issues with undef vars because
I used a special value for them.

And you know that it is already written and working relatively well
like passing all the tests from the testsuite because I told you so
only a few days ago.

> Then how to fix it is just technical details.
> I care less about warning uninitialized variable warning, which
> we can't do a perfect job any way. I am more worry about those
> screw up SSA forms.

It's where we disagree.
You're talking about this SSA thing as if you're busy writing a
compiler but currently and since its creation sparse is a
*semantic checker* used in *complement* of a real compiler
to give warnings that the compiler doesn't bother with.

My opinion is that it is *very* valuable to given the best possible
warnings and yes it sucks that so many things relative to
compiler technology are undecidable or NP-hard & friends.
But this only means that it is impossible to do a *perfect* job,
not that it is impossible to do a *good* job.

Writting a toy compiler is very easy, every student who had some
"compiler 101" course had to write one. It's maybe fun but is it useful?
What's the point of a compiler giving no or bad warnings?
What's the point of a non-optimizing compiler?
And you need decent optimizations to give decent warnings.

> The impression I get from the previous discussion is that, we kind of
> willfully do it and blame the source has uninitialized variable, without
> realized that our internal IR transformation has serious problem of
> breaking SSA property as well.

It's not my impression at all.
At best it's "sorry but for the moment we can't deal with this".
And again, you know very well that I'm very aware that our SSA
has serious problems, I told you about it.

> Now that RC5 is almost out of the door.  It is my intention to start this
> discussion to clarify things and point out things I believe is wrong.
> I know it is going to be a controversial topic :-)

I have a feeling that the 150+ patches that are pending since
January-March will have to wait even more.
Same for a series that is waiting since more than 2 years now.
Am I wrong?

-- Luc

Re: Potential incorrect simplification

[Luc Van Oostenryck]

On Sun, Aug 6, 2017 at 9:51 PM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
> Hi Chris,
>
> I agree that simplifications must not result in incorrect code (in my
> case correct code is more valuable than efficient code) - and in this
> particular example, the C code is legal and correct and this is not an
> instance of an uninitialized variable because in the C code the
> variable is assigned a value prior to it being accessed.

Just for the sake of completeness, it's not exactly simplification
that produce incorrect code. Like often, it's the interaction of
several things, here related to uninitialized vars (s3 is not
initialized, it shouldn't matter but it currently does).

> I am not sure that this is easy to fix though - as the original IR
> does not capture the intent of the C program.

It shouldn't be too hard.

> Maybe you could have a
> separate IR instruction to assign value to a bit field - rather than
> using load/and/or sequence. This will enable the original IR to
> reflect the intent of the C program more accurately and hopefully
> enable the simplification phase can handle it correctly.

Yes. I already thought about it several times but I never was able
to convince myself that it would be worth.
For dealing correctly with the case here we need *more*, *smarter*
simplifications. With specific instructions, it would be a bit easier
(but probably only a little bit) and will want these kind of simplifications
anyway so the new instructions will only add more code, need to deal
with similar situation in two different places, ...
This is related to the fact that sparse IR is quite low-level, as we already
talked about.

Maybe it would be good to first linearize to less low-level IR and then
lower the IR. I think something like this will be needed soon or later.

-- Luc

Re: Potential incorrect simplification

[Christopher Li]

On Sun, Aug 6, 2017 at 3:52 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> On Sun, Aug 6, 2017 at 8:35 PM, Christopher Li <sparse@chrisli.org> wrote:
>>>> That is true but not relevant.
>>>
>>> It's very relevant because its semantic is not defined.
>>> In other words, you can do anything you like (for the
>>> standard point of view).
>>
>> You can keep on arguing semantic is not defined.
>> When you have "usage before define" like the following:
>>           and.32      %r3 <- %r4, $-65
>>           or.32       %r4 <- %r3, $64
>>
>> It has direct consequence classic SSA algorithm can
>> not be done safely on later stage.
>
> Who has said the contrary? me?

If you have no problem with getting avoid producing the
offending IR. The we are in agreement. No problem there.
For a second I think you are going to defend why it should
do that way, as if that is the more correct way.



>>>> It's also relevant because you will then probably want
>>> to avoid to (generate code which) access such vars *and*
>>> want to detect them.
>>
>> Do you know that your request is unreasonable?
>
> Uh? It's what all compilers do and what the current sparse *try* to do.

Keep trying. We can try all right. I just give the upper bound that
this thing can be done correctly in every aspect easily. But that
is getting off topic here.

The topic really want to focus on is those SSA form that violate the
SSA dominance property. Let's agree on not producing those.


>> Detecting the usage of uninitialized variable in a program
>> is equivalent of the Turing halting problem. It is not Turing
>> commutable, there is no easy way to do it correctly in all
>> the situation.
>
> "want to avoid" doesn't mean "will avoid in all such cases and only such cases".

Sure, do what you can. Again, that is not the topic I want to discuss.
It is a different topic than the one I want to focus on, the "usage before
define" kind of the SSA form.

>>> This is also what I'm doing for various reasons.
>>> But once you initialize it with a special value, by definition,
>>> it's not uninitialized anymore.
>>
>> That is useless argument. You can call it what you want.
>
> It's not an argument.
>
>> It  does not change the fact that:
>>           and.32      %r3 <- %r4, $-65
>>           or.32       %r4 <- %r3, $64
>>
>> Break the SSA dominance property. We shouldn't generate code
>> like that. We do have a choice not to do it this way.
>
> Again, who said the contrary?

So we are in agreement. Great.

>
>>> I was referring to the 'internal bug' case.
>>> The current "crazy programmer" warning is as much a kind of
>>> assert on the internal consistency of the SSA form than a detection
>>> of uninitialized variables.
>>
>> In my book, we shouldn't get into that case at all. When we have
>>           add %r1 <- %r1, 4
>> We already screw up the SSA form.
>
> Yes, it's called a 'bug'.

Glad to heard that.


>
>>>> Refer to the book for more detail description of the algorithm
>>>> how to convert to SSA. We don't need to reinvent the wheel.
>>>
>>> Who's talking about reinventing the wheel?
>>> Your question was about "is it legal SSA form" (in the current sparse code)
>>> and I explained to you that it was the symptom of a problem.
>>
>> Yes, you keep on arguing this is the result of uninitialized variable.
>> Nothing to worry about.
>
> You asked a question about the *current* behaviour of sparse
> and I explained the reason of this behaviour.

I ask the question weather this SSA form is legal (in the sense
that preserving SSA property if you want to be more specific.)

You are saying you did not answer my question directly. You did not
pass judgement on weather this thing is legal or not. You just say why
it was done this way.

> It's not because explain this that I'm also saying
> "that is the correct behaviour and nothing must be changed about".
>
> And you know that I don't think so because we already talked about it.
> And I already said you that I have code that redo the SSA construction
> and that this code doesn't have the issues with undef vars because
> I used a special value for them.

That is what I want to find out, if your new SSA form have the similar
problem violating the SSA property or not.

>
> And you know that it is already written and working relatively well
> like passing all the tests from the testsuite because I told you so
> only a few days ago.

Good. I really hope it does not violate the SSA dominance property.
I don't want yet another SSA construction that violate the SSA dominance
property. Which means I still need to get ones that doesn't violating the
property so I can use classic SSA algorithms.


>
>> Then how to fix it is just technical details.
>> I care less about warning uninitialized variable warning, which
>> we can't do a perfect job any way. I am more worry about those
>> screw up SSA forms.
>
> It's where we disagree.
> You're talking about this SSA thing as if you're busy writing a
> compiler but currently and since its creation sparse is a
> *semantic checker* used in *complement* of a real compiler
> to give warnings that the compiler doesn't bother with.

That is actually the case. I am serious considering introduce
the classic SSA algorithms like dead code eliminate using ssa.
constant propagation using ssa. etc. It is going to work a lot better
than the current simplification process as far as I can tell.

Please don't mix the raising warning thing as if do proper SSA
hinder you raise warning about uninitialized value. It is actually
the reverse, do proper SSA will help you find out using uninitialized
value better.

But as I said, we can't get the warning perfect right due to nature
of the problem.

> My opinion is that it is *very* valuable to given the best possible
> warnings and yes it sucks that so many things relative to
> compiler technology are undecidable or NP-hard & friends.
> But this only means that it is impossible to do a *perfect* job,
> not that it is impossible to do a *good* job.

No disagreement here. Warning and proper SSA form is two different
thing.

> Writting a toy compiler is very easy, every student who had some
> "compiler 101" course had to write one. It's maybe fun but is it useful?
> What's the point of a compiler giving no or bad warnings?
> What's the point of a non-optimizing compiler?
> And you need decent optimizations to give decent warnings.

Agree. No disagreement there. I just point out we can't do
perfect job there. I am more concern about the proper SSA form.
It is two different topic.

>> The impression I get from the previous discussion is that, we kind of
>> willfully do it and blame the source has uninitialized variable, without
>> realized that our internal IR transformation has serious problem of
>> breaking SSA property as well.
>
> It's not my impression at all.
> At best it's "sorry but for the moment we can't deal with this".
> And again, you know very well that I'm very aware that our SSA
> has serious problems, I told you about it.

You told me about the placement of phi node. I look it up. Yes
it is a big problem. But that "usage before define" and violating the
SSA dominance property you never told me about. I found it out
myself with some help from the experts. You does not seem to
understand what property SSA should have in the first few response
to my email, questioning how to define "illegal SSA".  That is my
impression, I can be wrong.

If you are saying sorry we don't know how to do proper SSA.
The algorithm I point out from the book can already handle uninitialized
value. It can serve as a starting point if we don't know how to do it.

>> Now that RC5 is almost out of the door.  It is my intention to start this
>> discussion to clarify things and point out things I believe is wrong.
>> I know it is going to be a controversial topic :-)
>
> I have a feeling that the 150+ patches that are pending since
> January-March will have to wait even more.
> Same for a series that is waiting since more than 2 years now.
> Am I wrong?

No, and sorry about that. I was too busy at that time. But now I have
allocate some time for sparse. Let's do the review process again
after the release.

Topic like this which will have impact on the patches, also define the
direction sparse will be handing. I give it more priority.

Chris

Re: Potential incorrect simplification

[Luc Van Oostenryck]

On Sun, Aug 06, 2017 at 07:34:50PM -0400, Christopher Li wrote:
> >> Yes, you keep on arguing this is the result of uninitialized variable.
> >> Nothing to worry about.
> >
> > You asked a question about the *current* behaviour of sparse
> > and I explained the reason of this behaviour.
> 
> I ask the question weather this SSA form is legal (in the sense
> that preserving SSA property if you want to be more specific.)
> 
> You are saying you did not answer my question directly. You did not
> pass judgement on weather this thing is legal or not. You just say why
> it was done this way.

Because answering this question with an 'yes' or a 'no' is pointless.
Imagine that some authority on compiler would have answered to you
'yes' I consider that as legal because this or that. Would it have
helped you? I don't think so. Same with 'no'.

> > It's not because explain this that I'm also saying
> > "that is the correct behaviour and nothing must be changed about".
> >
> > And you know that I don't think so because we already talked about it.
> > And I already said you that I have code that redo the SSA construction
> > and that this code doesn't have the issues with undef vars because
> > I used a special value for them.
> 
> That is what I want to find out, if your new SSA form have the similar
> problem violating the SSA property or not.

It would have been easier to simply ask it.
 
> >> Then how to fix it is just technical details.
> >> I care less about warning uninitialized variable warning, which
> >> we can't do a perfect job any way. I am more worry about those
> >> screw up SSA forms.
> >
> > It's where we disagree.
> > You're talking about this SSA thing as if you're busy writing a
> > compiler but currently and since its creation sparse is a
> > *semantic checker* used in *complement* of a real compiler
> > to give warnings that the compiler doesn't bother with.
> 
> Please don't mix the raising warning thing as if do proper SSA
> hinder you raise warning about uninitialized value.

Have I said that or even suggest it?

> It is actually
> the reverse, do proper SSA will help you find out using uninitialized
> value better.
> 
> But as I said, we can't get the warning perfect right due to nature
> of the problem.

Yes, it's pretty well known about uninitialized vars.

> > My opinion is that it is *very* valuable to given the best possible
> > warnings and yes it sucks that so many things relative to
> > compiler technology are undecidable or NP-hard & friends.
> > But this only means that it is impossible to do a *perfect* job,
> > not that it is impossible to do a *good* job.
> 
> No disagreement here. Warning and proper SSA form is two different
> thing.

Good.
 
> You told me about the placement of phi node. I look it up. Yes
> it is a big problem. But that "usage before define" and violating the
> SSA dominance property you never told me about.

I certainly not said something like "usage before define" since it's
just a symptom. I told you about solving problmes with the handling
of undefined vars.

> You does not seem to
> understand what property SSA should have in the first few response
> to my email, questioning how to define "illegal SSA".  That is my
> impression, I can be wrong.

Your impression is very wrong.
Otherwise I wouldn't have bothered to write code to redo the SSA
construction thing and told you that there is a lot of problems
with the current SSA.

> >> Now that RC5 is almost out of the door.  It is my intention to start this
> >> discussion to clarify things and point out things I believe is wrong.
> >> I know it is going to be a controversial topic :-)
> >
> > I have a feeling that the 150+ patches that are pending since
> > January-March will have to wait even more.
> > Same for a series that is waiting since more than 2 years now.
> > Am I wrong?
> 
> No, and sorry about that. I was too busy at that time. But now I have
> allocate some time for sparse. Let's do the review process again
> after the release.

OK good to hear that.
I insist very heavily that I would like those to be handled *before*
moving further witht the SSA thing. Especially for Nicolai's series
which is waiting since a scandalous amount of time.

-- Luc

Re: Potential incorrect simplification

[Christopher Li]

On Sun, Aug 6, 2017 at 8:31 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>> You are saying you did not answer my question directly. You did not
>> pass judgement on weather this thing is legal or not. You just say why
>> it was done this way.
>
> Because answering this question with an 'yes' or a 'no' is pointless.
> Imagine that some authority on compiler would have answered to you
> 'yes' I consider that as legal because this or that. Would it have
> helped you? I don't think so. Same with 'no'.

It is not pointless if sparse don't produce the "usage before define"
code.

>
>> > It's not because explain this that I'm also saying
>> > "that is the correct behaviour and nothing must be changed about".
>> >
>> > And you know that I don't think so because we already talked about it.
>> > And I already said you that I have code that redo the SSA construction
>> > and that this code doesn't have the issues with undef vars because
>> > I used a special value for them.
>>
>> That is what I want to find out, if your new SSA form have the similar
>> problem violating the SSA property or not.
>
> It would have been easier to simply ask it.

I did in another email.

>> It is actually
>> the reverse, do proper SSA will help you find out using uninitialized
>> value better.
>>
>> But as I said, we can't get the warning perfect right due to nature
>> of the problem.
>
> Yes, it's pretty well known about uninitialized vars.
>
>> > My opinion is that it is *very* valuable to given the best possible
>> > warnings and yes it sucks that so many things relative to
>> > compiler technology are undecidable or NP-hard & friends.
>> > But this only means that it is impossible to do a *perfect* job,
>> > not that it is impossible to do a *good* job.
>>
>> No disagreement here. Warning and proper SSA form is two different
>> thing.
>
> Good.
>
>> You told me about the placement of phi node. I look it up. Yes
>> it is a big problem. But that "usage before define" and violating the
>> SSA dominance property you never told me about.
>
> I certainly not said something like "usage before define" since it's
> just a symptom. I told you about solving problmes with the handling
> of undefined vars.

OK. I don't know what is the detail of handle undefined vars
from you description.

>
>> You does not seem to
>> understand what property SSA should have in the first few response
>> to my email, questioning how to define "illegal SSA".  That is my
>> impression, I can be wrong.
>
> Your impression is very wrong.
> Otherwise I wouldn't have bothered to write code to redo the SSA
> construction thing and told you that there is a lot of problems
> with the current SSA.

All good then.

>> >> Now that RC5 is almost out of the door.  It is my intention to start this
>> >> discussion to clarify things and point out things I believe is wrong.
>> >> I know it is going to be a controversial topic :-)
>> >
>> > I have a feeling that the 150+ patches that are pending since
>> > January-March will have to wait even more.
>> > Same for a series that is waiting since more than 2 years now.
>> > Am I wrong?
>>
>> No, and sorry about that. I was too busy at that time. But now I have
>> allocate some time for sparse. Let's do the review process again
>> after the release.
>
> OK good to hear that.
> I insist very heavily that I would like those to be handled *before*
> moving further witht the SSA thing. Especially for Nicolai's series
> which is waiting since a scandalous amount of time.

No problem. One at a time.

Chris

[PATCH v2 0/8] fix loading of partially defined bitfield

[Luc Van Oostenryck]

The goal of this series is to fix the problem present in sparse
when a bitfield in an uninitialized automatic variable is first
set then read-back.

In this case the bitfield itself is initialized but not the
remaining of the structure/word and sparse was not smart
enough to handle it.

This is for testing only as it still requires some verifications.

Dibyendu,
This should now really solve your test case with:
	s3.onebit = 1;
	if (s3.onebit != 1)
		...


Changes since v1:
- use the hack from March to work-around the problem 
  with undefined vars.
- add the missing simplifications to make the
  store-and-load-back of a bitfield almost a no-op
  as it should be.


The series is available in the git repository at:

  git://github.com/lucvoo/sparse.git fix-loading-partialy-defined-bitfields-v2

----------------------------------------------------------------
Luc Van Oostenryck (8):
      Remove single-store shortcut
      new helper: def_opcode()
      reuse nbr_pseudo_users()
      change the masking when loading bitfields
      simplify ((A & M') | B ) & M when M' & M == 0
      transform (A & M) >> S to (A >> S) & (M >> S)
      transform (A << S) >> S into A & (-1 >> S)
      fix: cast of OP_AND only valid if it's an OP_CAST

 flow.c                                 |  39 +-----------
 linearize.c                            |  15 +++--
 linearize.h                            |   5 ++
 simplify.c                             | 107 ++++++++++++++++++++++++++++++---
 unssa.c                                |   5 --
 validation/bitfield-size.c             |   4 +-
 validation/optim/store-load-bitfield.c |  66 ++++++++++++++++++++
 7 files changed, 181 insertions(+), 60 deletions(-)
 create mode 100644 validation/optim/store-load-bitfield.c

[PATCH v2 1/8] Remove single-store shortcut

[Luc Van Oostenryck]

Current sparse code doesn't handle very gracefully
code with undefined pseudos. These can occurs,
of course because the dev has forgot (or choose) to
initialize them but they can also occurs when they
are only set (and used) in a single path and not others
or even worse when initilaizing a bitfield.

The origin of the problme is the single store shortcut
in simplify_one_symbol() which doesn't take in account
the (absence of) dominance when loads exist without
stores.

Fix this by removing this single-store shortcut and leave
all the work for the general case which handle this
situation quite well (and/but set those variables to 0).

Warning: this change impact the performance.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 flow.c | 39 ++-------------------------------------
 1 file changed, 2 insertions(+), 37 deletions(-)

diff --git a/flow.c b/flow.c
index 6cac21b24..6b2c879a8 100644
--- a/flow.c
+++ b/flow.c
@@ -650,11 +650,10 @@ void check_access(struct instruction *insn)
 
 static void simplify_one_symbol(struct entrypoint *ep, struct symbol *sym)
 {
-	pseudo_t pseudo, src;
+	pseudo_t pseudo;
 	struct pseudo_user *pu;
-	struct instruction *def;
 	unsigned long mod;
-	int all, stores, complex;
+	int all;
 
 	/* Never used as a symbol? */
 	pseudo = sym->pseudo;
@@ -670,17 +669,12 @@ static void simplify_one_symbol(struct entrypoint *ep, struct symbol *sym)
 	if (mod)
 		goto external_visibility;
 
-	def = NULL;
-	stores = 0;
-	complex = 0;
 	FOR_EACH_PTR(pseudo->users, pu) {
 		/* We know that the symbol-pseudo use is the "src" in the instruction */
 		struct instruction *insn = pu->insn;
 
 		switch (insn->opcode) {
 		case OP_STORE:
-			stores++;
-			def = insn;
 			break;
 		case OP_LOAD:
 			break;
@@ -697,37 +691,8 @@ static void simplify_one_symbol(struct entrypoint *ep, struct symbol *sym)
 		default:
 			warning(sym->pos, "symbol '%s' pseudo used in unexpected way", show_ident(sym->ident));
 		}
-		complex |= insn->offset;
 	} END_FOR_EACH_PTR(pu);
 
-	if (complex)
-		goto complex_def;
-	if (stores > 1)
-		goto multi_def;
-
-	/*
-	 * Goodie, we have a single store (if even that) in the whole
-	 * thing. Replace all loads with moves from the pseudo,
-	 * replace the store with a def.
-	 */
-	src = VOID;
-	if (def)
-		src = def->target;
-
-	FOR_EACH_PTR(pseudo->users, pu) {
-		struct instruction *insn = pu->insn;
-		if (insn->opcode == OP_LOAD) {
-			check_access(insn);
-			convert_load_instruction(insn, src);
-		}
-	} END_FOR_EACH_PTR(pu);
-
-	/* Turn the store into a no-op */
-	kill_store(def);
-	return;

[PATCH v2 2/8] new helper: def_opcode()

[Luc Van Oostenryck]

Getting the opcode corresponding to the instruction defining
a pseudo if the psedudo has such and instruction (PSEUDO_REG)
is an common operation in the simplification phase.

Use an helper to make the code a bit easier to read.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c | 19 ++++++++++++-------
 1 file changed, 12 insertions(+), 7 deletions(-)

diff --git a/simplify.c b/simplify.c
index 2bc86f53e..d9528de43 100644
--- a/simplify.c
+++ b/simplify.c
@@ -352,6 +352,13 @@ static int replace_with_pseudo(struct instruction *insn, pseudo_t pseudo)
 	return REPEAT_CSE;
 }
 
+static inline int def_opcode(pseudo_t p)
+{
+	if (p->type != PSEUDO_REG)
+		return -1;
+	return p->def->opcode;
+}
+
 static unsigned int value_size(long long value)
 {
 	value >>= 8;
@@ -376,9 +383,9 @@ static unsigned int operand_size(struct instruction *insn, pseudo_t pseudo)
 {
 	unsigned int size = insn->size;
 
-	if (pseudo->type == PSEUDO_REG) {
+	if (def_opcode(pseudo) == OP_CAST) {
 		struct instruction *src = pseudo->def;
-		if (src && src->opcode == OP_CAST && src->orig_type) {
+		if (src->orig_type) {
 			unsigned int orig_size = src->orig_type->bit_size;
 			if (orig_size < size)
 				size = orig_size;
@@ -786,13 +793,11 @@ static int simplify_associative_binop(struct instruction *insn)
 
 	if (!simple_pseudo(insn->src2))
 		return 0;
-	if (pseudo->type != PSEUDO_REG)
+	if (def_opcode(pseudo) != insn->opcode)
 		return 0;
 	def = pseudo->def;
 	if (def == insn)
 		return 0;
-	if (def->opcode != insn->opcode)
-		return 0;
 	if (!simple_pseudo(def->src2))
 		return 0;
 	if (ptr_list_size((struct ptr_list *)def->target->users) != 1)
@@ -957,9 +962,9 @@ static int simplify_cast(struct instruction *insn)
 	}
 
 	/* A cast of a "and" might be a no-op.. */
-	if (src->type == PSEUDO_REG) {
+	if (def_opcode(src) == OP_AND) {
 		struct instruction *def = src->def;
-		if (def->opcode == OP_AND && def->size >= size) {
+		if (def->size >= size) {
 			pseudo_t val = def->src2;
 			if (val->type == PSEUDO_VAL) {
 				unsigned long long value = val->value;
-- 
2.13.2

[PATCH v2 3/8] reuse nbr_pseudo_users()

[Luc Van Oostenryck]

This small helper was used in unssa.c but is helpfull elsewhere too.

Change it to an inline function and move it to one of the header.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.h | 5 +++++
 simplify.c  | 2 +-
 unssa.c     | 5 -----
 3 files changed, 6 insertions(+), 6 deletions(-)

diff --git a/linearize.h b/linearize.h
index bac82d7ff..7f2e976e7 100644
--- a/linearize.h
+++ b/linearize.h
@@ -301,6 +301,11 @@ static inline struct pseudo_user *alloc_pseudo_user(struct instruction *insn, ps
 	return user;
 }
 
+static inline int nbr_pseudo_users(pseudo_t p)
+{
+	return ptr_list_size((struct ptr_list *)p->users);
+}
+
 static inline void use_pseudo(struct instruction *insn, pseudo_t p, pseudo_t *pp)
 {
 	*pp = p;
diff --git a/simplify.c b/simplify.c
index d9528de43..8b63bcaff 100644
--- a/simplify.c
+++ b/simplify.c
@@ -800,7 +800,7 @@ static int simplify_associative_binop(struct instruction *insn)
 		return 0;
 	if (!simple_pseudo(def->src2))
 		return 0;
-	if (ptr_list_size((struct ptr_list *)def->target->users) != 1)
+	if (nbr_pseudo_users(def->target) != 1)
 		return 0;
 	switch_pseudo(def, &def->src1, insn, &insn->src2);
 	return REPEAT_CSE;
diff --git a/unssa.c b/unssa.c
index e7c9154d5..736474b90 100644
--- a/unssa.c
+++ b/unssa.c
@@ -34,11 +34,6 @@
 #include <assert.h>
 
 
-static inline int nbr_pseudo_users(pseudo_t p)
-{
-	return ptr_list_size((struct ptr_list *)p->users);
-}

[PATCH v2 4/8] change the masking when loading bitfields

[Luc Van Oostenryck]

To make some simplification easier, change the way the masking
is done when loading bitfields.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.c                | 15 +++++++++------
 validation/bitfield-size.c |  6 ++++--
 2 files changed, 13 insertions(+), 8 deletions(-)

diff --git a/linearize.c b/linearize.c
index ba76397ea..f833fd8d9 100644
--- a/linearize.c
+++ b/linearize.c
@@ -1000,14 +1000,17 @@ static pseudo_t linearize_load_gen(struct entrypoint *ep, struct access_data *ad
 {
 	struct symbol *ctype = ad->result_type;
 	pseudo_t new = add_load(ep, ad);
+	unsigned int off = ctype->bit_offset;
+	unsigned int siz = ctype->bit_size;
 
-	if (ctype->bit_offset) {
-		pseudo_t shift = value_pseudo(ctype->bit_offset);
-		pseudo_t newval = add_binary_op(ep, ad->source_type, OP_LSR, new, shift);
-		new = newval;
+	if (siz != type_size(ad->source_type)) {
+		pseudo_t mask = value_pseudo(((1ULL << siz) - 1) << off);
+		new = add_binary_op(ep, ad->source_type, OP_AND, new, mask);
+	}
+	if (off) {
+		pseudo_t shift = value_pseudo(off);
+		new = add_binary_op(ep, ad->source_type, OP_LSR, new, shift);
 	}
-	if (ctype->bit_size != type_size(ad->source_type))
-		new = cast_pseudo(ep, new, ad->source_type, ad->result_type);
 	return new;
 }
 
diff --git a/validation/bitfield-size.c b/validation/bitfield-size.c
index ce78ecf21..c8c94bb15 100644
--- a/validation/bitfield-size.c
+++ b/validation/bitfield-size.c
@@ -35,7 +35,9 @@ unsigned int get_pbfi_b(struct bfi *bf) { return bf->b; }
  * check-command: test-linearize -Wno-decl $file
  * check-output-ignore
  *
- * check-output-pattern-24-times: cast\\.
- * check-output-pattern-12-times: cast\\.4
+ * check-output-excludes: cast\\.4
+ * check-output-pattern-6-times: cast\\.
  * check-output-pattern-6-times: lsr\\..*\\$6
+ * check-output-pattern-6-times: and\\..*\\$15
+ * check-output-pattern-6-times: and\\..*\\$960
  */
-- 
2.13.2

[PATCH v2 5/8] simplify ((A & M') | B ) & M when M' & M == 0

[Luc Van Oostenryck]

This is specially usefull when A is in fact undefined.

Reported-by: Dibyendu Majumdar <mobile@majumdar.org.uk>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                             | 42 +++++++++++++++++++++-
 validation/optim/store-load-bitfield.c | 66 ++++++++++++++++++++++++++++++++++
 2 files changed, 107 insertions(+), 1 deletion(-)
 create mode 100644 validation/optim/store-load-bitfield.c

diff --git a/simplify.c b/simplify.c
index 8b63bcaff..9893613da 100644
--- a/simplify.c
+++ b/simplify.c
@@ -502,6 +502,46 @@ static int simplify_seteq_setne(struct instruction *insn, long long value)
 	}
 }
 
+static int simplify_and_or_mask(struct instruction *insn, pseudo_t and, pseudo_t other, unsigned long long mask)
+{
+	struct instruction *def = and->def;
+	pseudo_t old;
+
+	if (!constant(def->src2))
+		return 0;
+	if (def->src2->value & mask)
+		return 0;
+	old = insn->src1;
+	use_pseudo(insn, other, &insn->src1);
+	remove_usage(old, &insn->src1);
+	return REPEAT_CSE;
+}
+
+static int simplify_constant_mask(struct instruction *insn, unsigned long long mask)
+{
+	struct instruction *left;
+	pseudo_t src1, src2;
+
+	switch (def_opcode(insn->src1)) {
+	case OP_OR:
+		// Let's handle ((A & M') | B ) & M
+		// or           (B | (A & M')) & M
+		// when M' & M == 0
+		left = insn->src1->def;
+		src1 = left->src1;
+		src2 = left->src2;
+		if (def_opcode(src1) == OP_AND)
+			return simplify_and_or_mask(insn, src1, src2, mask);
+		if (def_opcode(src2) == OP_AND)
+			return simplify_and_or_mask(insn, src2, src1, mask);
+		break;
+
+	default:
+		break;
+	}
+	return 0;
+}
+
 static int simplify_constant_rightside(struct instruction *insn)
 {
 	long long value = insn->src2->value;
@@ -546,7 +586,7 @@ static int simplify_constant_rightside(struct instruction *insn)
 	case OP_AND:
 		if (!value)
 			return replace_with_pseudo(insn, insn->src2);
-		return 0;
+		return simplify_constant_mask(insn, value);
 
 	case OP_SET_NE:
 	case OP_SET_EQ:
diff --git a/validation/optim/store-load-bitfield.c b/validation/optim/store-load-bitfield.c
new file mode 100644
index 000000000..b74022602
--- /dev/null
+++ b/validation/optim/store-load-bitfield.c
@@ -0,0 +1,66 @@
+int ufoo(int a)
+{
+	struct u {
+		unsigned int :2;
+		unsigned int a:3;
+	} bf;
+
+	bf.a = a;
+	return bf.a;
+}
+
+int sfoo(int a)
+{
+	struct s {
+		signed int :2;
+		signed int a:3;
+	} bf;
+
+	bf.a = a;
+	return bf.a;
+}
+
+int xfoo(int a)
+{
+	struct x {
+		int :2;
+		int a:3;	// unsigned !
+	} bf;
+
+	bf.a = a;
+	return bf.a;
+}
+
+
+/*
+ * check-name: optim store/load bitfields
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-start
+ufoo:
+.L0:
+	<entry-point>
+	scast.3     %r2 <- (32) %arg1
+	and.32      %r9 <- %r2, $7
+	ret.32      %r9
+
+
+sfoo:
+.L2:
+	<entry-point>
+	scast.3     %r13 <- (32) %arg1
+	and.32      %r20 <- %r13, $7
+	scast.32    %r21 <- (3) %r20
+	ret.32      %r21
+
+
+xfoo:
+.L4:
+	<entry-point>
+	scast.3     %r24 <- (32) %arg1
+	and.32      %r31 <- %r24, $7
+	ret.32      %r31
+
+
+ * check-output-end
+ */
-- 
2.13.2

[PATCH v2 6/8] transform (A & M) >> S to (A >> S) & (M >> S)

[Luc Van Oostenryck]

This is especially usefull when simplifying code
accessing bitfields.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                 | 29 ++++++++++++++++++++++++++++-
 validation/bitfield-size.c |  4 +---
 2 files changed, 29 insertions(+), 4 deletions(-)

diff --git a/simplify.c b/simplify.c
index 9893613da..f1a898700 100644
--- a/simplify.c
+++ b/simplify.c
@@ -412,6 +412,32 @@ static int simplify_asr(struct instruction *insn, pseudo_t pseudo, long long val
 	return 0;
 }
 
+static int simplify_lsr(struct instruction *insn, pseudo_t pseudo, long long value)
+{
+	struct instruction *def;
+	unsigned long long mask;
+
+	if (!value)
+		return replace_with_pseudo(insn, pseudo);
+	switch (def_opcode(insn->src1)) {
+	case OP_AND:
+		// replace (A & M) >> S
+		// by      (A >> S) & (M >> S)
+		def = insn->src1->def;
+		if (!constant(def->src2))
+			break;
+		if (nbr_pseudo_users(insn->src1) > 1)
+			break;
+		mask = def->src2->value;
+		def->opcode = OP_LSR;
+		def->src2 = value_pseudo(value);
+		insn->opcode = OP_AND;
+		insn->src2 = value_pseudo(mask >> value);
+		return REPEAT_CSE;
+	}
+	return 0;
+}
+
 static int simplify_mul_div(struct instruction *insn, long long value)
 {
 	unsigned long long sbit = 1ULL << (insn->size - 1);
@@ -562,13 +588,14 @@ static int simplify_constant_rightside(struct instruction *insn)
 	case OP_ADD:
 	case OP_OR: case OP_XOR:
 	case OP_SHL:
-	case OP_LSR:
 	case_neutral_zero:
 		if (!value)
 			return replace_with_pseudo(insn, insn->src1);
 		return 0;
 	case OP_ASR:
 		return simplify_asr(insn, insn->src1, value);
+	case OP_LSR:
+		return simplify_lsr(insn, insn->src1, value);
 
 	case OP_MODU: case OP_MODS:
 		if (value == 1)
diff --git a/validation/bitfield-size.c b/validation/bitfield-size.c
index c8c94bb15..34400479a 100644
--- a/validation/bitfield-size.c
+++ b/validation/bitfield-size.c
@@ -36,8 +36,6 @@ unsigned int get_pbfi_b(struct bfi *bf) { return bf->b; }
  * check-output-ignore
  *
  * check-output-excludes: cast\\.4
- * check-output-pattern-6-times: cast\\.
  * check-output-pattern-6-times: lsr\\..*\\$6
- * check-output-pattern-6-times: and\\..*\\$15
- * check-output-pattern-6-times: and\\..*\\$960
+ * check-output-pattern-12-times: and\\..*\\$15
  */
-- 
2.13.2

[PATCH v2 7/8] transform (A << S) >> S into A & (-1 >> S)

[Luc Van Oostenryck]

This is especially usefull when simplifying code
accessing bitfields.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c | 15 +++++++++++++++
 1 file changed, 15 insertions(+)

diff --git a/simplify.c b/simplify.c
index f1a898700..cdc244c17 100644
--- a/simplify.c
+++ b/simplify.c
@@ -416,6 +416,7 @@ static int simplify_lsr(struct instruction *insn, pseudo_t pseudo, long long val
 {
 	struct instruction *def;
 	unsigned long long mask;
+	pseudo_t old;
 
 	if (!value)
 		return replace_with_pseudo(insn, pseudo);
@@ -434,6 +435,20 @@ static int simplify_lsr(struct instruction *insn, pseudo_t pseudo, long long val
 		insn->opcode = OP_AND;
 		insn->src2 = value_pseudo(mask >> value);
 		return REPEAT_CSE;
+	case OP_SHL:
+		// replace (A << S) >> S
+		// by      A & (-1 >> S)
+		def = insn->src1->def;
+		if (!constant(def->src2))
+			break;
+		if (def->src2->value != value)
+			break;
+		insn->opcode = OP_AND;
+		insn->src2 = value_pseudo(-1ULL >> value);
+		old = insn->src1;
+		use_pseudo(insn, def->src1, &insn->src1);
+		remove_usage(old, &insn->src1);
+		return REPEAT_CSE;
 	}
 	return 0;
 }
-- 
2.13.2

[PATCH v2 8/8] fix: cast of OP_AND only valid if it's an OP_CAST

[Luc Van Oostenryck]

A cast of an OP_AND can be simplified away if the mask
already 'cover' the value.
However this cannot be done if the cast is in fact
a sign-extension.

Fix this by adding the appropriate check of OP_CAST vs. OP_SCAST

Fixes: caeaf72d34d1e91aaea7340241232d1d877907b7
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/simplify.c b/simplify.c
index cdc244c17..4da8edfde 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1044,7 +1044,7 @@ static int simplify_cast(struct instruction *insn)
 	}
 
 	/* A cast of a "and" might be a no-op.. */
-	if (def_opcode(src) == OP_AND) {
+	if (insn->opcode == OP_CAST && def_opcode(src) == OP_AND) {
 		struct instruction *def = src->def;
 		if (def->size >= size) {
 			pseudo_t val = def->src2;
-- 
2.13.2

Re: [PATCH v2 1/8] Remove single-store shortcut

[Linus Torvalds]

On Mon, Aug 7, 2017 at 12:11 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> Fix this by removing this single-store shortcut and leave
> all the work for the general case which handle this
> situation quite well (and/but set those variables to 0).

Ack.  The single-store case really was always a hack to make simple
things look simple.

Doing proper optimization is the right approach, no question about it.

                   Linus

Re: [PATCH v2 7/8] transform (A << S) >> S into A & (-1 >> S)

[Linus Torvalds]

On Mon, Aug 7, 2017 at 12:12 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> +               // replace (A << S) >> S
> +               // by      A & (-1 >> S)

Umm. This seems misleading.

Don't you mean "value of all ones of the same size as A, shifted right by S"

> +               insn->src2 = value_pseudo(-1ULL >> value);

..and this seems buggy. There's a lot of bits in -1ULL, but what if
the size of 'S' is only 32-bit?

So I think you should take the size of A into account?

Or am I missing something?

             Linus

Re: [PATCH v2 7/8] transform (A << S) >> S into A & (-1 >> S)

[Luc Van Oostenryck]

On Mon, Aug 7, 2017 at 11:54 PM, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
> On Mon, Aug 7, 2017 at 12:12 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
>> +               // replace (A << S) >> S
>> +               // by      A & (-1 >> S)
>
> Umm. This seems misleading.
>
> Don't you mean "value of all ones of the same size as A, shifted right by S"
>
>> +               insn->src2 = value_pseudo(-1ULL >> value);
>
> ..and this seems buggy. There's a lot of bits in -1ULL, but what if
> the size of 'S' is only 32-bit?
>
> So I think you should take the size of A into account?
>
> Or am I missing something?

I don't think you're missing something and this code have only been
very lightly tested (and maybe developed too fastly too).
OTOH, it shouldn't matter much since it's only used for a mask
(subsequent steps will drop the superfluous high bits) and I think
that it's done so at some other place too.
But it certainly wouldn't be bad to use the right size for the mask.

-- Luc

Re: [PATCH v2 7/8] transform (A << S) >> S into A & (-1 >> S)

[Luc Van Oostenryck]

On Tue, Aug 8, 2017 at 12:08 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> On Mon, Aug 7, 2017 at 11:54 PM, Linus Torvalds
> <torvalds@linux-foundation.org> wrote:
>> On Mon, Aug 7, 2017 at 12:12 PM, Luc Van Oostenryck
>> <luc.vanoostenryck@gmail.com> wrote:
>>> +               // replace (A << S) >> S
>>> +               // by      A & (-1 >> S)
>>
>> Umm. This seems misleading.
>>
>> Don't you mean "value of all ones of the same size as A, shifted right by S"
>>
>>> +               insn->src2 = value_pseudo(-1ULL >> value);
>>
>> ..and this seems buggy. There's a lot of bits in -1ULL, but what if
>> the size of 'S' is only 32-bit?
>>
>> So I think you should take the size of A into account?
>>
>> Or am I missing something?

You're right. It must be wrong.
I think it's working but only because in the tests I've used
it's optimized away.

-- Luc

Re: [PATCH v2 6/8] transform (A & M) >> S to (A >> S) & (M >> S)

[Christopher Li]

On Mon, Aug 7, 2017 at 3:12 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> This is especially usefull when simplifying code
> accessing bitfields.
>
>
> +static int simplify_lsr(struct instruction *insn, pseudo_t pseudo, long long value)
> +{
> +       struct instruction *def;
> +       unsigned long long mask;
> +
> +       if (!value)
> +               return replace_with_pseudo(insn, pseudo);
> +       switch (def_opcode(insn->src1)) {
> +       case OP_AND:
> +               // replace (A & M) >> S
> +               // by      (A >> S) & (M >> S)

Why (A>>S) & (M >>S) is easier to simplify?

The original has two instruction but the result has three.

Is that that because A>>S is more likely to find match in
the CSE?

What if there is no match found, does that mean it is
not useful to do this transformation?

Chris

Re: [PATCH v2 6/8] transform (A & M) >> S to (A >> S) & (M >> S)

[Luc Van Oostenryck]

On Tue, Aug 8, 2017 at 2:22 AM, Christopher Li <sparse@chrisli.org> wrote:

> Why (A>>S) & (M >>S) is easier to simplify?
>
> The original has two instruction but the result has three.

Only 2 because M & S are constants and so (M >> S) is already evaluated.

As described succinctly in the patch description, even with 2 instructions
the real motivation is only because it's one of the three patterns that arise
when storing a bitfield and reloading it later.

But isolating a AND (smaller) mask is always a good thing because there
is a lot of other opportunities for more simplifications that can be
done on them.

-- Luc

Re: [PATCH v2 6/8] transform (A & M) >> S to (A >> S) & (M >> S)

[Linus Torvalds]

On Mon, Aug 7, 2017 at 5:22 PM, Christopher Li <sparse@chrisli.org> wrote:
>
> Why (A>>S) & (M >>S) is easier to simplify?
>
> The original has two instruction but the result has three.

No, M and S are constants, so the end result also has just two ("lsr"
and "and").

And the simplified form has a smaller constant.

So I think that optimization makes a lot of sense.

It *might* result in further simplifications just because the final
'and' might be simpler, and even the "A >> S" might now be something
you can simplify (for example "A >> 16" could be turned into a 16-bit
load if the source of A is a 32-bit load).

But even in the absence of such further simplification, the smaller
constant thing likely makes it worth it. Almost all architectures have
an easier time with smaller constants, and doing

   (a >> 24) & 255;

is often noticeably more efficient than

   (a & 0xff000000) >> 24;

just because of the constant issue.

                Linus

Re: [PATCH v2 6/8] transform (A & M) >> S to (A >> S) & (M >> S)

[Luc Van Oostenryck]

On Tue, Aug 8, 2017 at 3:00 AM, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
> It *might* result in further simplifications just because the final
> 'and' might be simpler, and even the "A >> S" might now be something
> you can simplify (for example "A >> 16" could be turned into a 16-bit
> load if the source of A is a 32-bit load).
>
> But even in the absence of such further simplification, the smaller
> constant thing likely makes it worth it. Almost all architectures have
> an easier time with smaller constants, and doing
>
>    (a >> 24) & 255;
>
> is often noticeably more efficient than
>
>    (a & 0xff000000) >> 24;
>
> just because of the constant issue.

In truth, my real motivation is only apparent when looking at this patch
and the following. The original complete pattern was:
   ((X << S) & (M' << S)) >> S
with A = (X << S) and M = (M' << S)
which now give:
   ((X << S) >> S) & M'
and with the next patch will give
   (X & M'') & M'
which will simplify to
   X & M'''

But yes, these optimizations are worthwhile by themselves too
because they create small(er) masks.

-- Luc

(A & M) >> S to

(A >> S) & (M >> S)

Re: [PATCH v2 6/8] transform (A & M) >> S to (A >> S) & (M >> S)

[Christopher Li]

On Mon, Aug 7, 2017 at 8:29 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> On Tue, Aug 8, 2017 at 2:22 AM, Christopher Li <sparse@chrisli.org> wrote:
>
>> Why (A>>S) & (M >>S) is easier to simplify?
>>
>> The original has two instruction but the result has three.
>
> Only 2 because M & S are constants and so (M >> S) is already evaluated.

Ah, thanks for point it out the obvious. Your M means Mask.
I did not catch that.

Chris

Re: [PATCH v2 6/8] transform (A & M) >> S to (A >> S) & (M >> S)

[Christopher Li]

On Mon, Aug 7, 2017 at 9:00 PM, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
> But even in the absence of such further simplification, the smaller
> constant thing likely makes it worth it. Almost all architectures have
> an easier time with smaller constants, and doing
>
>    (a >> 24) & 255;
>
> is often noticeably more efficient than
>
>    (a & 0xff000000) >> 24;
>
> just because of the constant issue.

That totally make sense.

Thanks

Chris

Re: [PATCH v2 1/8] Remove single-store shortcut

[Christopher Li]

On Mon, Aug 7, 2017 at 5:42 PM, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
>
> Ack.  The single-store case really was always a hack to make simple
> things look simple.
>
> Doing proper optimization is the right approach, no question about it.
>

Totally agree.

Chris

Re: [PATCH v2 1/8] Remove single-store shortcut

[Luc Van Oostenryck]

On Thu, Aug 10, 2017 at 2:29 AM, Christopher Li <sparse@chrisli.org> wrote:
> On Mon, Aug 7, 2017 at 5:42 PM, Linus Torvalds wrote:
>>
>> Ack.  The single-store case really was always a hack to make simple
>> things look simple.
>>
>> Doing proper optimization is the right approach, no question about it.
>>
>
> Totally agree.

This patch (and the preceding one but not the ones that follow) is totally
worth to add to the release. I've tested it (my normal tests + kernel
allyesconfig)
and all is OK :
- lots of changes in test-linearize, of course, but only good changes
- zero changes in kernel check

Are you fine with this?

-- Luc

Re: [PATCH v2 1/8] Remove single-store shortcut

[Christopher Li]

On Wed, Aug 9, 2017 at 8:41 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> Are you fine with this?

Sure. I am still writing the documents for RC5.

Do you want me to merge this V4 version as it is?

I will start to switch to master to do the merge. Giving up the
rebase thing on sparse-next. At the same time I also want to give
you patch a bit more test.

Thanks

Chris

Re: [PATCH v2 1/8] Remove single-store shortcut

[Christopher Li]

On Mon, Aug 7, 2017 at 3:11 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> Current sparse code doesn't handle very gracefully
> code with undefined pseudos. These can occurs,
> of course because the dev has forgot (or choose) to
> initialize them but they can also occurs when they
> are only set (and used) in a single path and not others
> or even worse when initilaizing a bitfield.
>
> The origin of the problme is the single store shortcut
> in simplify_one_symbol() which doesn't take in account
> the (absence of) dominance when loads exist without
> stores.

I have give it a bit more thinking. The right metal model is actually
consider the every uninitialized variable has an implicit
define at the entry block.

The reason this short cut is wrong is that, it is not  about
how many store we have (single vs multiple).  It is about
weather all the usage(load) has one single store
immediate dominates it. If it does, even exist of other stores,
this optimization can still be done.

The question would be if we have easy and quick way to
detect that all the load are immediate dominated by the
one single store. If that condition holds, we can still do the
"short-cut".

BTW, I consider this patch can separate out from the other
patch in this series meaning wise. The other patches are about
constant related transformations. This one is about proper SSA.
It can still be merge as one series. That part is fine.

Please let me know if you want to include this in the RC5.
Give me a proper git pull address. Topic branch is fine.

Thanks

Chris

Re: [PATCH v2 1/8] Remove single-store shortcut

[Luc Van Oostenryck]

On Thu, Aug 10, 2017 at 1:01 PM, Christopher Li <sparse@chrisli.org> wrote:
>
> The reason this short cut is wrong is that, it is not  about
> how many store we have (single vs multiple).  It is about
> weather all the usage(load) has one single store
> immediate dominates it. If it does, even exist of other stores,
> this optimization can still be done.

More exactly, this shortcut is wrong because it is based on
the assumption that if there is a single store, then this store
must necessary dominates all the loads.
This assumption is, of course, wrong when the var is not
explicitly defined.

> The question would be if we have easy and quick way to
> detect that all the load are immediate dominated by the
> one single store.

That's what the general case does.

> If that condition holds, we can still do the "short-cut".

Only for limited special cases. It's not worth, forget about it.

Anyway, it's very temporary because the code still put the
phi-nodes at wrong places.
This simplify_one_symbol() is replaced by the new SSA construction
branch.

Believe it or not but this placement of phi-nodes is a much bigger
issue than those undefined vars. For example, on the kernel,
this patch has exactly zero (visible) effect. But every non-trivial
piece of code is plainly very wrong because of those bad phi-nodes.

> BTW, I consider this patch can separate out from the other
> patch in this series meaning wise.

Yes, it's what I said :"this patch and the preceding one
(because it's needed for the test case)".

> Please let me know if you want to include this in the RC5.
> Give me a proper git pull address. Topic branch is fine.

Yes, I'll do later.
(if you want just for testing, please take the ref in the cover letter
and drop the top patches. Unless comments from you, I don't
have the intention to change something to these two patches)

Regards,
-- Luc

Re: [PATCH v2 1/8] Remove single-store shortcut

[Christopher Li]

On Thu, Aug 10, 2017 at 8:26 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> Anyway, it's very temporary because the code still put the
> phi-nodes at wrong places.
> This simplify_one_symbol() is replaced by the new SSA construction
> branch.
>
> Believe it or not but this placement of phi-nodes is a much bigger
> issue than those undefined vars. For example, on the kernel,
> this patch has exactly zero (visible) effect. But every non-trivial
> piece of code is plainly very wrong because of those bad phi-nodes.

I can totally see that.

My way to explain to myself is that, it is all about the SSA
dominance property. Violate the properly == bad things can
happen.

I can use the property to reason about phi node placements,
Also reason this patch as well.

> Yes, I'll do later.
> (if you want just for testing, please take the ref in the cover letter
> and drop the top patches. Unless comments from you, I don't
> have the intention to change something to these two patches)

I can do more testing too.

Thanks!

Chris