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

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
    3). Compiler need to see all the references of the variables.

   The address-not-taken can be used to disambiguate memory operations 
between:
     o. direct load/store to a global variable which does not have its 
address taken, and
     o. any arbitrary indirect memory operations.

   The 2) is to ensure compiler will not set a volatile variable 
"addr-not-taken", even
if all its reference are direct accesses.

   The 3) does not necessarily imply the global variable has internal 
linkage type, see
following scenario S2 and S3.

   Since llvm::GlobalVariable has plenty of vacant bits (for flags), 
this bit will
not increase its size.


2. Scenarios where llvm::GlobalVariable::addr_not_taken is useful
================================================================  NOTE: As you
can see from the S2 and S3, addr_not_taken can serve as
additional info
     of the input IR. In that sense, we should view "addr_not_taken"
as
an attribute of
     a variable (akin to GNU's function-attribute).

  S1) C-thinking programs likely have lots of global variables, and most 
of them
      are directly referenced.

      It would be more useful in LTO mode as in this mode more global 
variables
      will be recognized as "address-not-taken".

  S2) Compiler may generate some global variables for some special 
purpose or for some
      special languages. These global variables are normally directly 
accessed. Compiler
      can mark the variable "addr-not-taken" to avoid uncessary alias.
We would otherwise
      need to introduce a special meta-data for this purpose.

      Go back to semantic 3). At the moment a compiler generate such 
variables,
      it does not physically "see" all the reference of these vars, 
however it
      is pretty sure how these these variable will be accessed.

      Note that in this scenario, the references of these 
compiler-created global
    variables may occur in multiple modules. Therefore, they don't have 
"internal"
    linkage.

   S3) Consider this snippet:
   S3) Consider this snippet:
      ---------------------
      static int xyz; // address-not-taken
      foo() {
         access xyz;
      }

      bar() { access xyz; }
      ----------------------

      For some reasons (say, triage problematic functions), we many 
separate foo()
      and bar() into different source files. For this purpose, we have 
to get
      rid of "static" from "xyz", which may bring new
problem once in a
while,
      for instance, bug disappear, performance degrade.

      Introducing address-not-taken will alleviate such troubles.

3. Q&A
=====   Q1: If we have nice points-to analysis, do we still need what you 
propose today.
--------------------------------------------------------------------------------
   A1: For scenario S2 and S3, points-to analysis will not help. I agree 
S2 and S3
are not very important.

   For S1, sure, it does not need to be a "nice" analyzer, even a 
"stupid" anlayzer
should work for this end. The problem is that points-to analyses are 
normally very
expensive. They are normally invoked once the in the entire compiler 
pipeline,
before that point, we cannot disambiguate global-variable and indirection
mem-ops.

   On the other hand, compiler can afford re-analyzing address-taken for
particular global variable or all global variables again and again after
some optimizations (say, DCE). We certainly cannot affording to invoke
the prohibitively expensive points-to analysis for so many times.


   Q2: Does addr-not-taken imply "unnamed_addr" (Nick asked this 
question the other day)
-------------------------------------------------------------------------------------
   A2: No. Consider S2 and S3.

     For S1, I don't know for sure if variable name matter or not if 
debug-info is
   turned on.

   Q3: Can we save the not-addr-taken to meta-data?
   -------------------------------------------------
   A3: Meta-data, by its very nature, is part of IR. It is pretty slow 
to access.
       We can view addr-not-taken as an attribute of the globalvar (just 
like
       function as attributes like readonly/malloc/....).

         I'm aware of other compilers whose symbol-tables have imilar bits
       for all kind of symbols (funcitons and data at level).

   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.

   Q5: How difficult is it to maintain this flag
   -----------------------------------------------------
   A5: It is almost maintenance free, in the sense that we almost never
     come across a situation when an optimizer take the address of
       the globalvar which is marked addr-not-taken.

       It would be nice if we can afford re-analyze addr-taken over and
      over again to make sure the information is precise. However,
    we don't have to do that --- while the information is imprecise,
    it is conservatively correct.

    Q6: Analyzing addr-taken is inexpensive. Why not just disambiguate by
        analyzing addr-taken on the fly during AA phase (Nick asked the 
question
        other day)?
    -----------------------------------------------------
    A6: While analyzing addr-taken for data is more expensive
        than analyzing addr-takne for funciton, I think it is still 
relatively
        inexpensive.

        That said, I don't think it is still inexpensive if we 
re-analyze the
     addr-taken again and again *ON THE FLY".  It is really difficult to
     predict compile-time impact. You never know how many global variables
     in a program, and you never know how extensive they are used.
     Poorly-written program tends to have lots of global-vars.


Thanks
Shuxin

----- 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.
>     3). Compiler need to see all the references of the variables.
> 
>    The address-not-taken can be used to disambiguate memory
>    operations
> between:
>      o. direct load/store to a global variable which does not have
>      its
> address taken, and
>      o. any arbitrary indirect memory operations.
> 
>    The 2) is to ensure compiler will not set a volatile variable
> "addr-not-taken", even
> if all its reference are direct accesses.
> 
>    The 3) does not necessarily imply the global variable has internal
> linkage type, see
> following scenario S2 and S3.
> 
>    Since llvm::GlobalVariable has plenty of vacant bits (for flags),
> this bit will
> not increase its size.
> 
> 
> 2. Scenarios where llvm::GlobalVariable::addr_not_taken is useful
> ================================================================>  
NOTE: As you can see from the S2 and S3, addr_not_taken can serve
>   as
> additional info
>      of the input IR. In that sense, we should view
"addr_not_taken"
>      as
> an attribute of
>      a variable (akin to GNU's function-attribute).
> 
>   S1) C-thinking programs likely have lots of global variables, and
>   most
> of them
>       are directly referenced.
> 
>       It would be more useful in LTO mode as in this mode more global
> variables
>       will be recognized as "address-not-taken".
> 
>   S2) Compiler may generate some global variables for some special
> purpose or for some
>       special languages. These global variables are normally directly
> accessed. Compiler
>       can mark the variable "addr-not-taken" to avoid uncessary
>       alias.
> We would otherwise
>       need to introduce a special meta-data for this purpose.
> 
>       Go back to semantic 3). At the moment a compiler generate such
> variables,
>       it does not physically "see" all the reference of these
vars,
> however it
>       is pretty sure how these these variable will be accessed.
> 
>       Note that in this scenario, the references of these
> compiler-created global
>     variables may occur in multiple modules. Therefore, they don't
>     have
> "internal"
>     linkage.
> 
>    S3) Consider this snippet:
>    S3) Consider this snippet:
>       ---------------------
>       static int xyz; // address-not-taken
>       foo() {
>          access xyz;
>       }
> 
>       bar() { access xyz; }
>       ----------------------
> 
>       For some reasons (say, triage problematic functions), we many
> separate foo()
>       and bar() into different source files. For this purpose, we
>       have
> to get
>       rid of "static" from "xyz", which may bring new
problem once in
>       a
> while,
>       for instance, bug disappear, performance degrade.
> 
>       Introducing address-not-taken will alleviate such troubles.
> 
> 3. Q&A
> =====>    Q1: If we have nice points-to analysis, do we still need what
you
> propose today.
>
--------------------------------------------------------------------------------
>    A1: For scenario S2 and S3, points-to analysis will not help. I
>    agree
> S2 and S3
> are not very important.
> 
>    For S1, sure, it does not need to be a "nice" analyzer, even a
> "stupid" anlayzer
> should work for this end. The problem is that points-to analyses are
> normally very
> expensive. They are normally invoked once the in the entire compiler
> pipeline,
> before that point, we cannot disambiguate global-variable and
> indirection
> mem-ops.
> 
>    On the other hand, compiler can afford re-analyzing address-taken
>    for
> particular global variable or all global variables again and again
> after
> some optimizations (say, DCE). We certainly cannot affording to
> invoke
> the prohibitively expensive points-to analysis for so many times.
> 
> 
>    Q2: Does addr-not-taken imply "unnamed_addr" (Nick asked this
> question the other day)
>
-------------------------------------------------------------------------------------
>    A2: No. Consider S2 and S3.
> 
>      For S1, I don't know for sure if variable name matter or not if
> debug-info is
>    turned on.
> 
>    Q3: Can we save the not-addr-taken to meta-data?
>    -------------------------------------------------
>    A3: Meta-data, by its very nature, is part of IR. It is pretty
>    slow
> to access.
>        We can view addr-not-taken as an attribute of the globalvar
>        (just
> like
>        function as attributes like readonly/malloc/....).
> 
>          I'm aware of other compilers whose symbol-tables have imilar
>          bits
>        for all kind of symbols (funcitons and data at level).
> 
>    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?

 -Hal
> 
>    Q5: How difficult is it to maintain this flag
>    -----------------------------------------------------
>    A5: It is almost maintenance free, in the sense that we almost
>    never
>      come across a situation when an optimizer take the address of
>        the globalvar which is marked addr-not-taken.
> 
>        It would be nice if we can afford re-analyze addr-taken over
>        and
>       over again to make sure the information is precise. However,
>     we don't have to do that --- while the information is imprecise,
>     it is conservatively correct.
> 
>     Q6: Analyzing addr-taken is inexpensive. Why not just
>     disambiguate by
>         analyzing addr-taken on the fly during AA phase (Nick asked
>         the
> question
>         other day)?
>     -----------------------------------------------------
>     A6: While analyzing addr-taken for data is more expensive
>         than analyzing addr-takne for funciton, I think it is still
> relatively
>         inexpensive.
> 
>         That said, I don't think it is still inexpensive if we
> re-analyze the
>      addr-taken again and again *ON THE FLY".  It is really difficult
>      to
>      predict compile-time impact. You never know how many global
>      variables
>      in a program, and you never know how extensive they are used.
>      Poorly-written program tends to have lots of global-vars.
> 
> 
> Thanks
> Shuxin
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> 
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

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.

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

On Oct 29, 2013, at 4:39 PM, Shuxin Yang <shuxin.llvm at gmail.com> wrote:
>   That said, I don't think it is still inexpensive if we re-analyze the
>    addr-taken again and again *ON THE FLY".  It is really difficult to
>    predict compile-time impact. You never know how many global variables
>    in a program, and you never know how extensive they are used.
>    Poorly-written program tends to have lots of global-vars.
Actually, it is not that difficult to predict the effect on compile time.  All
you need to do is implement the analysis “on the fly” and measure the compile
time.  Can you provide this data ?  Compile time measurements can help us make a
decision.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20131030/7a4d90c4/attachment.html>

Nadav:

    I don't think this is right approach for engineering.
The time-complexity of re-analyzing addr_taken for each single alias 
query depends on
    1. how many global variable
    2. how many occurrence of these global variables.
    3. how many queries the compiler have.

   3) depends on compiler.  You never know what we will have in the 
following few years.
1 and 2 depends on the program.  You never know what kind of program you 
will run into.
How can we use what we have today the extrapolate the future ignoring 
the highly
unpredictable complexity.

    It's interesting that recently, many EE magazine (circuit cellar, 
Elector, EE times) are
discussing buggy SW kill people.  I remember some posts complaining that 
some buggy program
have amazingly large # of global variables. I can find one post in 
Chinese website:

    http://forum.xitek.com/thread-1226816-5-1-1.html

    The 1st post says,  "a program has 11000 global variables"!

    As to "Can you provide this data"?  My answer is no, and I will
not
to implement the analysis
which perform on-the-fly analysis unless I'm convinced that saving 
addr_taken bit to llvm::GlobalVariable
is fundamentally flawed.

Shuxin





On 10/30/13 9:20 AM, Nadav Rotem wrote:
>
> On Oct 29, 2013, at 4:39 PM, Shuxin Yang <shuxin.llvm at gmail.com 
> <mailto:shuxin.llvm at gmail.com>> wrote:
>
>>   That said, I don't think it is still inexpensive if we re-analyze
the
>>    addr-taken again and again *ON THE FLY".  It is really
difficult to
>>    predict compile-time impact. You never know how many global
variables
>>    in a program, and you never know how extensive they are used.
>>    Poorly-written program tends to have lots of global-vars.
>
> Actually, it is not that difficult to predict the effect on compile 
> time.  All you need to do is implement the analysis “on the fly” and 
> measure the compile time.  Can you provide this data ?  Compile time 
> measurements can help us make a decision.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20131030/292a7d20/attachment.html>

>       o. The address-taken information collected before LTO (aka pre-IPO),
>          cannot be fed to LTO, unless we re-analyze them from ground up.
This is the one case I can think an attribute similar to this could
make a reasonable difference. Not because we get variables with too
many uses, but because we have to read in all the IL to find the uses.

I say similar because the semantics would have to be a bit different.
What we would want is basically a conservative cache of
GlobalStatus.IsCompared:

* If a GlobalValue has its address used in this TU, this flag must be clear.
* If a GlobalValue's address is not used in this TU, this flag may be set.

Note in particular that this is a per TU property. This means that its
users have to check the linkage (as they do when using GlobalStatus)
and the linker has to learn how merge them.

In summary, it is strictly just a compile time optimization.

Cheers,
Rafael