llvm dev - Oct 2013 - [LLVMdev] [Propose] Add address-taken bit to GlobalVariable for disambiguation purpose

Hi, Hal:

  Thank you for your feedback, see following inline comment

Thanks

On 10/29/13 5:02 PM, Hal Finkel wrote:
> ----- Original Message -----
>> Hi, There:
>>
>>     I'd like to add bit, called "addr_not_taken", to
GlobalVariable in
>> order to
>> indicate if a GlobalVariable doesn't has its address taken or not.
>>
>> 1.The motivation
>> ==============>>      The motivation can be explained by the
following example. In this
>> example,
>> variable x does not have its address taken, therefore, it cannot be
>> indirectly
>> access. So, we can prove "x" and "*p" don't
overlap.
>>     -----------------
>>     static int x;
>>     foo(int *p) {
>>       x = 1;
>>       *p = 2;   // do not modify x
>>       x = x + 1;
>>     }
>>     ---------------
>>
>>     The semantic of llvm::GlobalVariable::addr_not_taken is:
>>      1). Of course, the global variable in question doesn't have
its
>> address taken, and
>>      2). the global variable is not volatile, and
> Why are you also imposing this restriction? I'm also not quite sure
what it means, in the context of LLVM, where only loads and stores can be
volatile.
2) is just for being pedantic :-)

One might otherwise argue in this snippet, x apparently does not have 
its addr taken,
however, it's illegal to say  that "x" and "*p"
don't alias.


  volatile static int x;
    foo(int *p) {
      x = 1;
      *p = 2;   // do not modify x
      x = x + 1;
    }


  >  Q4: Can we save the not-addr-taken to an analysis pass
  >  -----------------------------------------------------
  >  A4: If we implement this way:
  >      o. we have add a statement to most, if not all, passes to
  >      claim it
  >         preserve this addr-taken analysis result, which is bit
  >         anonying.
  >
  >      o. The address-taken information collected before LTO (aka
  >      pre-IPO),
  >         cannot be fed to LTO, unless we re-analyze them from ground
  >         up.
> So is the idea that lib/Analysis/IPA/GlobalsModRef.cpp will set this bit
when it runs?
>
>
I'm not quire sure your question. Let me try to answer.

In my implementation, I set address_no_taken in 
lib/Transformation/IPO/GlobalOpt.cpp.
In this pass, it tries to see if a global var has its address taken 
before it tries to optimize
the global variable.

ModRef is immaterial in this regard.

What I'm try to say in "A4"  is that it is really *troublesome* if
we
save the
addr-taken-analysis result to a analysis-pass (rather than cache the 
result to
GlobalVariable::addr_not_taken).  If we really have to implement this way,
we need to at very least implement following two steps:

    --------------------------

        o. we have add a statement to most, if not all, passes to
        claim it preserve this addr-taken analysis result, which is bit
           anonying.

        o. In LTO mode, re-run the address-taken-analysis right after all input
IR are linked
           together. I need to to do so because the addr-taken information we
collected
           before LTO is missing.

----------------------

>2) is just for being pedantic :-)
>
> One might otherwise argue in this snippet, x apparently does not have 
> its addr taken,
> however, it's illegal to say  that "x" and "*p"
don't alias.
>
>
>  volatile static int x;
>    foo(int *p) {
>      x = 1;
>      *p = 2;   // do not modify x
>      x = x + 1;
>    }
>
Oops, lame examples,  change the example bellow. The reasons remain 
unchanged : for pedantic reasons,
you can ignore it:-)

volatile static int x;
    foo(volatile int *p) {
      x = 1;
      *p = 2;   // do not modify x
      x = x + 1;
    }

----- Original Message -----
> Hi, Hal:
> 
>   Thank you for your feedback, see following inline comment
> 
> Thanks
> 
> On 10/29/13 5:02 PM, Hal Finkel wrote:
> > ----- Original Message -----
> >> Hi, There:
> >>
> >>     I'd like to add bit, called "addr_not_taken", to
> >>     GlobalVariable in
> >> order to
> >> indicate if a GlobalVariable doesn't has its address taken or
not.
> >>
> >> 1.The motivation
> >> ==============> >>      The motivation can be explained
by the following example. In
> >>      this
> >> example,
> >> variable x does not have its address taken, therefore, it cannot
> >> be
> >> indirectly
> >> access. So, we can prove "x" and "*p"
don't overlap.
> >>     -----------------
> >>     static int x;
> >>     foo(int *p) {
> >>       x = 1;
> >>       *p = 2;   // do not modify x
> >>       x = x + 1;
> >>     }
> >>     ---------------
> >>
> >>     The semantic of llvm::GlobalVariable::addr_not_taken is:
> >>      1). Of course, the global variable in question doesn't
have
> >>      its
> >> address taken, and
> >>      2). the global variable is not volatile, and
> > Why are you also imposing this restriction? I'm also not quite
sure
> > what it means, in the context of LLVM, where only loads and stores
> > can be volatile.
> 2) is just for being pedantic :-)
> 
> One might otherwise argue in this snippet, x apparently does not have
> its addr taken,
> however, it's illegal to say  that "x" and "*p"
don't alias.
Wait, really? I thought that "volatile static int x" just meant that
the value of x was volatile; not that 'x' might spontaneously start
referring to some other memory location.
> 
> 
>   volatile static int x;
>     foo(int *p) {
>       x = 1;
>       *p = 2;   // do not modify x
>       x = x + 1;
>     }
> 
> 
>   >  Q4: Can we save the not-addr-taken to an analysis pass
>   >  -----------------------------------------------------
>   >  A4: If we implement this way:
>   >      o. we have add a statement to most, if not all, passes to
>   >      claim it
>   >         preserve this addr-taken analysis result, which is bit
>   >         anonying.
>   >
>   >      o. The address-taken information collected before LTO (aka
>   >      pre-IPO),
>   >         cannot be fed to LTO, unless we re-analyze them from
>   >         ground
>   >         up.
> 
> > So is the idea that lib/Analysis/IPA/GlobalsModRef.cpp will set
> > this bit when it runs?
> >
> >
> I'm not quire sure your question. Let me try to answer.
> 
> In my implementation, I set address_no_taken in
> lib/Transformation/IPO/GlobalOpt.cpp.
> In this pass, it tries to see if a global var has its address taken
> before it tries to optimize
> the global variable.
> 
> ModRef is immaterial in this regard.
> 
> What I'm try to say in "A4"  is that it is really
*troublesome* if we
> save the
> addr-taken-analysis result to a analysis-pass (rather than cache the
> result to
> GlobalVariable::addr_not_taken).  If we really have to implement this
> way,
> we need to at very least implement following two steps:
Okay, sounds good. IIRC, GlobalsModRef currently (also) determines whether or
not a global has its address taken. It might make sense to unify that logic with
what you're proposing for GlobalOpt, and it seems like it would definitely
make sense to let GlobalsModRef take advantage of the address_not_taken bit.

Also, as a general note, I don't see why any of this should be LTO-specific.
For variables with local (internal) linkage, we can do the analysis on a
per-module basis, and I don't understand why we currently don't.

Thanks again,
Hal
> 
>     --------------------------
> 
>         o. we have add a statement to most, if not all, passes to
>         claim it preserve this addr-taken analysis result, which is
>         bit
>            anonying.
> 
>         o. In LTO mode, re-run the address-taken-analysis right after
>         all input IR are linked
>            together. I need to to do so because the addr-taken
>            information we collected
>            before LTO is missing.
> 
> ----------------------
> 
> 
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

>> 2) is just for being pedantic :-)
>>
>> One might otherwise argue in this snippet, x apparently does not have
>> its addr taken,
>> however, it's illegal to say  that "x" and "*p"
don't alias.
> Wait, really? I thought that "volatile static int x" just meant
that the value of x was volatile; not that 'x' might spontaneously start
referring to some other memory location.
You are right. I mixed this proposal with a project I did before.
In that project the interface is asymmetric and the return value take 
into account
of concurrent access.

Sorry for being sloppy. Please ignore 2) completely.
>> I'm not quire sure your question. Let me try to answer.
>>
>> In my implementation, I set address_no_taken in
>> lib/Transformation/IPO/GlobalOpt.cpp.
>> In this pass, it tries to see if a global var has its address taken
>> before it tries to optimize
>> the global variable.
>>
>> ModRef is immaterial in this regard.
>>
>> What I'm try to say in "A4"  is that it is really
*troublesome* if we
>> save the
>> addr-taken-analysis result to a analysis-pass (rather than cache the
>> result to
>> GlobalVariable::addr_not_taken).  If we really have to implement this
>> way,
>> we need to at very least implement following two steps:
> Okay, sounds good. IIRC, GlobalsModRef currently (also) determines whether
or not a global has its address taken. It might make sense to unify that logic
with what you're proposing for GlobalOpt, and it seems like it would
definitely make sense to let GlobalsModRef take advantage of the
address_not_taken bit.
I don't read ModRef carefully. I think it make some sense to factor out 
the addr-taken analysis. Such that
other pass can take advantage of it.
>
> Also, as a general note, I don't see why any of this should be
LTO-specific. For variables with local (internal) linkage, we can do the
analysis on a per-module basis, and I don't understand why we currently
don't.
>
> Thanks again,
> Hal
>
>
You can understand from this example: Suppose the a.c b.c comprise the 
program where a.c has some static variable whose address
are not taken.  The addr-taken information collected during stage 
time-stamp-0 cannot be found at time-stamp-1.2.

If we were saving the addr-not-taken info in 
GlobalVariable::not_addr_taken, optimizations in 1.2 will automatically 
benefit from
cached information.

-------------------------------------
time-stamp-0:
    clang *.c -flto -c -o a.o

time stamp 1:
    clang *.o -flto -o a.out

time stamp 1.1):  link a.o b.o into merged.o
time stamp 1.2):  do some optimizations
time stamp 1.3): addr-taken is re-analyzed.
-------------------------------------