[LLVMdev] [Propose] Add address-taken bit to GlobalVariable for disambiguation purpose

[Shuxin Yang]

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