[LLVMdev] How to describe a pointer that points to All memory(include global memory, heap, stack)?

[Daniel Berlin]

On Wed, Mar 20, 2013 at 7:33 PM, Steven Su <steven_known at yahoo.com.cn> wrote:
> Hi, John
>         I am building a flow sensitive intra-procedural alias analysis(without interprocedural info).
>         So, the first thing I have to consider is where a parameter-pointer or a global-pointer might point to.
>         Then I defined several special Virtual Memory Locations: ALL_MEMORY, GLOBAL_MEMORY, STACK_MEMORY, HEAP_MEMORY. ALL_MEMORY contains GLOBAL_MEMORY, STACK_MEMORY, HEAP_MEMORY.


Contains or points to?

ALL_MEMORY should point to ALL_MEMORY, otherwise *ALL_MEMORY !=
ALL_MEMORY, which will break things like linked lists.


In any case, the final representation in GCC of points to anything is
a single bit flag.
We don't keep sparse bit vectors around just to have a single bit set in them.


>
>         e.g1:
>         extern int * q;
>         void f(int * p)
>         {
>             int a;
>             *p = 0; //STMT1
>             *q = a; //STMT2
>         }
>         For above case, both p and q pointed to ALL_MEMORY: p->ALL_MEMORY, q->ALL_MEMORY.
>         And each STMT has two BitVectors to describe MayDef, MayUse.
>         (I think the BitVector must be sparse, otherwise the alias-analysis module need too much memory to allocate for all BitVectors.)

Well, actually, this is what led to bdd representations.

GCC uses sparse bitmaps, which work fine for intraprocedural use.
We do a large amount of presolving to discover equivalences before
ever filling in points-to sets.

I'm not sure your mechanism of solving, but if you are constraint
solving, you should special case ALL_MEMORY (and a few others).
There is never a reason to add anything to a points-to set that
contains ALL_MEMORY.


>         For STMT1, the MayDef={ALL_MEMORY}, MayUse={}
>         For STMT2, the MayDef={ALL_MEMORY}, MayUse={'a'}
>         ---------------------
>         e.g2:
>         extern int A[100];
>         int * q;
>         void f2(int * p)
>         {
>             *p = 0; //STMT1
>             p = &A; //STMT2
>             p[0] = *q; //STMT3
>             bar(); //STMT4
>         }
>         In e.g2,
>         for STMT1, the MayDef={ALL_MEMORY}, MayUse={}
>         for STMT2, p->A, so the MayDef={'p'}, MayUse={}
>         for STMT3, the MayDef={'A'}, MayUse={ALL_MEMORY}
>         for STMT4, the MayDef={ALL_MEMORY}, MayUse={ALL_MEMORY}
>
> Is that right? Or there are another better methods. :)
>
>
>
> --- 13年3月14日，周四, John Criswell <criswell at illinois.edu> 写道：
>
>> 发件人: John Criswell <criswell at illinois.edu>
>> 主题: Re: [LLVMdev] How to describe a pointer that points to All memory(include global memory, heap, stack)?
>> 收件人: "Steven Su" <steven_known at yahoo.com.cn>
>> 抄送: llvmdev at cs.uiuc.edu
>> 日期: 2013年3月14日,周四,上午12:14
>> On 3/13/13 4:06 AM, Steven Su wrote:
>> > Hello, could any one point me following question.
>>
>> Without any context, your question is difficult to
>> answer.  Are you
>> building a points-to analysis and wanting to know how an
>> alias analysis
>> might encode the fact that a pointer could alias any other
>> pointer?
>>
>> -- John T.
>>
>> >
>> > e.g:
>> >     void foo(int * p)
>> >     {
>> >            *p =
>> 0;
>> >     }
>> >          Here 'p' may point to
>> all memory location.
>> >          Could you tell me how
>> to represent the POINT TO set of 'p'?
>> >
>>
>> >          Here is my solution:
>> >          Introduce a
>> memory-class named: Global_Mem, then p pointed to
>> global_mem.
>> >          And the MOD set of
>> '*p=0' is Global_Mem.
>> >
>> > But how to present the overlapping alias set:
>> > e.g2:
>> >          extern A[100];
>> >     void foo(int * p, int i)
>> >     {
>> >             *p
>> = 0;
>> >
>>    A[i] = 10;
>> >     }
>> >
>> > 'p' may point to anywhere. So p may point to A. How to
>> describe the relation?
>> >
>> >
>> >
>> > _______________________________________________
>> > LLVM Developers mailing list
>> > LLVMdev at cs.uiuc.edu
>>        http://llvm.cs.uiuc.edu
>> > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>
>>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev