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

Hi, all:

    Per Chris and Nadav's request, I begin to write the code about 
analyzing address-taken
lazily.  I realize the alias query could be initiated from any context 
(*function* pass, loop pass etc),
however, the analysis for global-variable-address-taken is conducted in 
*module* scope.
Is there any potential problem over here? (For instance,  function foo() 
and bar() comprise module m,
however, at time optimizer is working on foo(), bar() is not physically 
in that module. In this case,
analyze global-variable on the fly doesn't make sense.)

Thanks in advance!
Shuxin

On 10/30/13 2:08 PM, Chris Lattner wrote:
> On Oct 30, 2013, at 10:37 AM, Shuxin Yang <shuxin.llvm at gmail.com 
> <mailto:shuxin.llvm at gmail.com>> wrote:
>> 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.
>
> This logic doesn't make sense to me.  You can implement it both ways 
> and get empirical results on *programs we have today* and *in our 
> compiler*.  This is not a theoretical exercise.
>
> In practice, walking the use list of a global variable is very fast. 
>  As you've noticed, we already use this approach (in an admittedly 
> ad-hoc and decentralized way) throughout the compiler.
>
>>    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"!
>
> This is just FUD and completely unrelated to the discussion.
>
>>    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.
>
> You don't have to be convinced.  The burden of proof is on you - not 
> on us to convince you.
>
> Here's the deal: there are tons of "potentially useful"
things that
> could be encoded in the IR.  Each thing added to IR has a complexity 
> increase on the entire compiler.  Passes that work on global variables 
> will have to reason about this bit, and transformations that could 
> invalidate it (e.g. global merging) will have to have code added to 
> update/preserve it.
>
> We are very conservative about changing IR for good reason.  We don't 
> add caches to IR unless there is pretty much no other way to achieve 
> the result.  In a perfect world, we would have nothing redundant in 
> the IR at all.
>
> That said, I'm open to this attribute, because I think the semantics 
> can be nailed down tightly (though your "volatile" discussion
doesn't
> make any sense to me) it is widely useful, and I don't think the 
> burden of maintaining it will be that high.  However, before we do it, 
> you need to demonstrate that lazily computing it from use-def chains 
> is *empirically worse*.
>
> -Chris
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20131104/c4a1d7a1/attachment.html>

----- Original Message -----
> 
> Hi, all:
> 
> Per Chris and Nadav's request, I begin to write the code about
> analyzing address-taken
> lazily. I realize the alias query could be initiated from any context
> (*function* pass, loop pass etc),
> however, the analysis for global-variable-address-taken is conducted
> in *module* scope.
> Is there any potential problem over here? (For instance, function
> foo() and bar() comprise module m,
> however, at time optimizer is working on foo(), bar() is not
> physically in that module. In this case,
> analyze global-variable on the fly doesn't make sense.)
Shuxin,

I don't see how this can work, without either a) breaking apart the current
pass structure by inserting a module-level pass or b) violating the implied pass
scope boundaries.

FWIW, I asked Chandler last month on IRC for this thoughts about whether the new
pass manager will support running different (function, basic block, etc.) passes
in parallel. There is obviously a lot of work yet before this is possible, but
he said that is the eventual goal. I don't yet understand what kind of
locking scheme we'd need for this in practice, but it seems that something
like this might get in the way.

On the other hand, if we're okay with this, I'd like to do something
similar so that static functions can determine aliasing information from their
callers.

 -Hal
> 
> Thanks in advance!
> Shuxin
> 
> 
> On 10/30/13 2:08 PM, Chris Lattner wrote:
> 
> 
> 
> 
> On Oct 30, 2013, at 10:37 AM, Shuxin Yang < shuxin.llvm at gmail.com
>
> wrote:
> 
> 
> 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.
> 
> 
> This logic doesn't make sense to me. You can implement it both ways
> and get empirical results on *programs we have today* and *in our
> compiler*. This is not a theoretical exercise.
> 
> 
> In practice, walking the use list of a global variable is very fast.
> As you've noticed, we already use this approach (in an admittedly
> ad-hoc and decentralized way) throughout the compiler.
> 
> 
> 
> 
> 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"!
> 
> 
> 
> This is just FUD and completely unrelated to the discussion.
> 
> 
> 
> 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.
> 
> 
> You don't have to be convinced. The burden of proof is on you - not
> on us to convince you.
> 
> 
> Here's the deal: there are tons of "potentially useful"
things that
> could be encoded in the IR. Each thing added to IR has a complexity
> increase on the entire compiler. Passes that work on global
> variables will have to reason about this bit, and transformations
> that could invalidate it (e.g. global merging) will have to have
> code added to update/preserve it.
> 
> 
> We are very conservative about changing IR for good reason. We don't
> add caches to IR unless there is pretty much no other way to achieve
> the result. In a perfect world, we would have nothing redundant in
> the IR at all.
> 
> 
> That said, I'm open to this attribute, because I think the semantics
> can be nailed down tightly (though your "volatile" discussion
> doesn't make any sense to me) it is widely useful, and I don't
think
> the burden of maintaining it will be that high. However, before we
> do it, you need to demonstrate that lazily computing it from use-def
> chains is *empirically worse*.
> 
> 
> -Chris
> 
> _______________________________________________
> 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 so much for the informative reply and your expertise!

Shuxin

On 11/4/13 2:14 PM, Hal Finkel wrote:
> ----- Original Message -----
>> Hi, all:
>>
>> Per Chris and Nadav's request, I begin to write the code about
>> analyzing address-taken
>> lazily. I realize the alias query could be initiated from any context
>> (*function* pass, loop pass etc),
>> however, the analysis for global-variable-address-taken is conducted
>> in *module* scope.
>> Is there any potential problem over here? (For instance, function
>> foo() and bar() comprise module m,
>> however, at time optimizer is working on foo(), bar() is not
>> physically in that module. In this case,
>> analyze global-variable on the fly doesn't make sense.)
> Shuxin,
>
> I don't see how this can work, without either a) breaking apart the
current pass structure by inserting a module-level pass or b) violating the
implied pass scope boundaries.
>
> FWIW, I asked Chandler last month on IRC for this thoughts about whether
the new pass manager will support running different (function, basic block,
etc.) passes in parallel. There is obviously a lot of work yet before this is
possible, but he said that is the eventual goal. I don't yet understand what
kind of locking scheme we'd need for this in practice, but it seems that
something like this might get in the way.
>
> On the other hand, if we're okay with this, I'd like to do
something similar so that static functions can determine aliasing information
from their callers.
>
>   -Hal
>
>> Thanks in advance!
>> Shuxin
>>
>>
>> On 10/30/13 2:08 PM, Chris Lattner wrote:
>>
>>
>>
>>
>> On Oct 30, 2013, at 10:37 AM, Shuxin Yang < shuxin.llvm at gmail.com
>
>> wrote:
>>
>>
>> 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.
>>
>>
>> This logic doesn't make sense to me. You can implement it both ways
>> and get empirical results on *programs we have today* and *in our
>> compiler*. This is not a theoretical exercise.
>>
>>
>> In practice, walking the use list of a global variable is very fast.
>> As you've noticed, we already use this approach (in an admittedly
>> ad-hoc and decentralized way) throughout the compiler.
>>
>>
>>
>>
>> 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"!
>>
>>
>>
>> This is just FUD and completely unrelated to the discussion.
>>
>>
>>
>> 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.
>>
>>
>> You don't have to be convinced. The burden of proof is on you - not
>> on us to convince you.
>>
>>
>> Here's the deal: there are tons of "potentially useful"
things that
>> could be encoded in the IR. Each thing added to IR has a complexity
>> increase on the entire compiler. Passes that work on global
>> variables will have to reason about this bit, and transformations
>> that could invalidate it (e.g. global merging) will have to have
>> code added to update/preserve it.
>>
>>
>> We are very conservative about changing IR for good reason. We
don't
>> add caches to IR unless there is pretty much no other way to achieve
>> the result. In a perfect world, we would have nothing redundant in
>> the IR at all.
>>
>>
>> That said, I'm open to this attribute, because I think the
semantics
>> can be nailed down tightly (though your "volatile" discussion
>> doesn't make any sense to me) it is widely useful, and I don't
think
>> the burden of maintaining it will be that high. However, before we
>> do it, you need to demonstrate that lazily computing it from use-def
>> chains is *empirically worse*.
>>
>>
>> -Chris
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>