llvm dev - Jul 2019 - Efficient way to identify an instruction

Hi Alberto,

I have not used this myself, but I think you should be able to visit your
Instruction ‘users()’. I think the name this function was given is a bit
confusing, but this returns an iterator range you can iterate through to find
instructions that depend on a given one.

Similarly, you have the function ‘uses()’ that can be used to traverse down the
DAG when instructions are still on SSA form.

Look also at the related functions 'user_end()’, 'user_begin()’,
'use_end()' and 'use_begin()

I hope this helps.

Joan



> On 28 Jul 2019, at 08:29, Alberto Barbaro via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> Hi,
> I was thinking that maybe there is always some sort of dependency analysis
that would allow me to visit a tree from the AllocaInst to the IcmpInst. Is it
already possible?
> 
> Thanks
> 
> Il giorno dom 28 lug 2019 alle ore 07:21 Alberto Barbaro
<barbaro.alberto at gmail.com <mailto:barbaro.alberto at gmail.com>>
ha scritto:
> Hi Tim,
> as always thanks for your help. Unfortunately I made a mistake in my email
but apart from that I still have problems.
> 
> Il giorno sab 27 lug 2019 alle ore 11:53 Tim Northover <t.p.northover at
gmail.com <mailto:t.p.northover at gmail.com>> ha scritto:
> Hi Alberto,
> 
> On Sat, 27 Jul 2019 at 10:09, Alberto Barbaro via llvm-dev
> <llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>> wrote:
> > Having the reference I to the instruction in bold.Can i efficiently
know that the variable %11 was "created" by the %3 = alloca [40 x i8],
align 16.
> 
> Yes, I.getOperand(0) *is* the AllocaInst in this case. So for example
> isa<AllocaInst>(I.getOperand(0)) will return true. And if you care
> about more details you can dyn_cast<AllocaInst> it and check any
other
> properties you want.
> 
> 
> I would like to use the approach you described considering I to be a
reference to the icmp instruction ( %13 = icmp eq i32 %12, 66 ). From what I
understood i should do something like:
> 
> Instruction* source;
> 
> if(source = dyn_cast<AllocaInst>(I.getOperand(0))) {
>     cout << "Alloca Inst" << endl;
>    	I.dump();
>    	getchar();
> }
> 
> I thought I.getOperand(0) was a reference to the instruction that have
created %12. What am I missing?
>  
> Cheers.
> 
> Tim.
> 
> Thanks again
> Alberto
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190729/e6cbb4a2/attachment.html>

Hi Alberto,

It seems to me that what you are trying to achieve falls into a bucket of
Points-To Analysis. Given a pointer (or a pointer + memory instruction),
PTA identifies its allocation sites -- all places that could have created
the pointed-to object [1, 2].

In this simplest case, you can take a value, strip casts, and get to load.
Once you have the load, you can strip pointer casts of the pointer operand
until you either reach an allocation site or an instruction you won't know
how to look through. I implemented something similar here [3], while
BasicAA should (internally) have something more robust [4]. If you are
interested in cross-function cases (interprocedural), you may be interested
in external PTAs for LLVM like SVF [5] or SeaDsa [6]. Note that in the
interprocedural case, you have to be careful what you consider an
allocation site, especially with external functions that return pointers.

Sincerely,
Jakub

----------

[1] Michael Hind, "Pointer Analysis: Haven’t We Solved This Problem
Yet?",
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.91.9469&rep=rep1&type=pdf
[2] Yannis Smaragdakis, George Balatsouras, "Pointer Analysis",
https://yanniss.github.io/points-to-tutorial15.pdf
[3]
https://github.com/seahorn/seahorn/blob/7c160d113c57b650bca28920e8670b56a9e1262f/lib/Transforms/Instrumentation/SimpleMemoryCheck.cc#L328
[4]
https://github.com/llvm/llvm-project/blob/89fb9e8ce151d48b56a6bc25de62e93743e0d6c1/llvm/lib/Analysis/BasicAliasAnalysis.cpp#L633
[5] https://github.com/SVF-tools/SVF
[6] https://github.com/seahorn/sea-dsa

On Mon, Jul 29, 2019 at 1:45 AM Joan Lluch via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Hi Alberto,
>
> I have not used this myself, but I think you should be able to visit your
> Instruction ‘users()’. I think the name this function was given is a bit
> confusing, but this returns an iterator range you can iterate through to
> find instructions that depend on a given one.
>
> Similarly, you have the function ‘uses()’ that can be used to traverse
> down the DAG when instructions are still on SSA form.
>
> Look also at the related functions 'user_end()’, 'user_begin()’,
> 'use_end()' and 'use_begin()
>
> I hope this helps.
>
> Joan
>
>
>
>
> On 28 Jul 2019, at 08:29, Alberto Barbaro via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
> Hi,
> I was thinking that maybe there is always some sort of dependency analysis
> that would allow me to visit a tree from the AllocaInst to the IcmpInst. Is
> it already possible?
>
> Thanks
>
> Il giorno dom 28 lug 2019 alle ore 07:21 Alberto Barbaro <
> barbaro.alberto at gmail.com> ha scritto:
>
>> Hi Tim,
>> as always thanks for your help. Unfortunately I made a mistake in my
>> email but apart from that I still have problems.
>>
>> Il giorno sab 27 lug 2019 alle ore 11:53 Tim Northover <
>> t.p.northover at gmail.com> ha scritto:
>>
>>> Hi Alberto,
>>>
>>> On Sat, 27 Jul 2019 at 10:09, Alberto Barbaro via llvm-dev
>>> <llvm-dev at lists.llvm.org> wrote:
>>> > Having the reference I to the instruction in bold.Can i
efficiently
>>> know that the variable %11 was "created" by the %3 =
alloca [40 x i8],
>>> align 16.
>>>
>>> Yes, I.getOperand(0) *is* the AllocaInst in this case. So for
example
>>> isa<AllocaInst>(I.getOperand(0)) will return true. And if you
care
>>> about more details you can dyn_cast<AllocaInst> it and check
any other
>>> properties you want.
>>>
>>>
>> I would like to use the approach you described considering I to be a
>> reference to the icmp instruction ( %13 = icmp eq i32 %12, 66 ). From
what
>> I understood i should do something like:
>>
>> Instruction* source;
>>
>> if(source = dyn_cast<AllocaInst>(I.getOperand(0))) {
>>     cout << "Alloca Inst" << endl;
>>     I.dump();
>>     getchar();
>> }
>>
>> I thought I.getOperand(0) was a reference to the instruction that have
>> created %12. What am I missing?
>>
>>
>>> Cheers.
>>>
>>> Tim.
>>>
>>
>> Thanks again
>> Alberto
>>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>

-- 
Jakub Kuderski
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190729/e8566b29/attachment.html>

Hi all,
Thanks for the great answers you gave me. Yes it sounds like an
interprocedural PTA. I'll try to understand how other projects did it and
go from there.

Thanks again
Alberto


On Mon, Jul 29, 2019, 16:19 Jakub (Kuba) Kuderski <kubakuderski at
gmail.com>
wrote:
> Hi Alberto,
>
> It seems to me that what you are trying to achieve falls into a bucket of
> Points-To Analysis. Given a pointer (or a pointer + memory instruction),
> PTA identifies its allocation sites -- all places that could have created
> the pointed-to object [1, 2].
>
> In this simplest case, you can take a value, strip casts, and get to load.
> Once you have the load, you can strip pointer casts of the pointer operand
> until you either reach an allocation site or an instruction you won't
know
> how to look through. I implemented something similar here [3], while
> BasicAA should (internally) have something more robust [4]. If you are
> interested in cross-function cases (interprocedural), you may be interested
> in external PTAs for LLVM like SVF [5] or SeaDsa [6]. Note that in the
> interprocedural case, you have to be careful what you consider an
> allocation site, especially with external functions that return pointers.
>
> Sincerely,
> Jakub
>
> ----------
>
> [1] Michael Hind, "Pointer Analysis: Haven’t We Solved This Problem
Yet?",
>
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.91.9469&rep=rep1&type=pdf
> [2] Yannis Smaragdakis, George Balatsouras, "Pointer Analysis",
> https://yanniss.github.io/points-to-tutorial15.pdf
> [3]
>
https://github.com/seahorn/seahorn/blob/7c160d113c57b650bca28920e8670b56a9e1262f/lib/Transforms/Instrumentation/SimpleMemoryCheck.cc#L328
> [4]
>
https://github.com/llvm/llvm-project/blob/89fb9e8ce151d48b56a6bc25de62e93743e0d6c1/llvm/lib/Analysis/BasicAliasAnalysis.cpp#L633
> [5] https://github.com/SVF-tools/SVF
> [6] https://github.com/seahorn/sea-dsa
>
> On Mon, Jul 29, 2019 at 1:45 AM Joan Lluch via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
>> Hi Alberto,
>>
>> I have not used this myself, but I think you should be able to visit
your
>> Instruction ‘users()’. I think the name this function was given is a
bit
>> confusing, but this returns an iterator range you can iterate through
to
>> find instructions that depend on a given one.
>>
>> Similarly, you have the function ‘uses()’ that can be used to traverse
>> down the DAG when instructions are still on SSA form.
>>
>> Look also at the related functions 'user_end()’,
'user_begin()’,
>> 'use_end()' and 'use_begin()
>>
>> I hope this helps.
>>
>> Joan
>>
>>
>>
>>
>> On 28 Jul 2019, at 08:29, Alberto Barbaro via llvm-dev <
>> llvm-dev at lists.llvm.org> wrote:
>>
>> Hi,
>> I was thinking that maybe there is always some sort of dependency
>> analysis that would allow me to visit a tree from the AllocaInst to the
>> IcmpInst. Is it already possible?
>>
>> Thanks
>>
>> Il giorno dom 28 lug 2019 alle ore 07:21 Alberto Barbaro <
>> barbaro.alberto at gmail.com> ha scritto:
>>
>>> Hi Tim,
>>> as always thanks for your help. Unfortunately I made a mistake in
my
>>> email but apart from that I still have problems.
>>>
>>> Il giorno sab 27 lug 2019 alle ore 11:53 Tim Northover <
>>> t.p.northover at gmail.com> ha scritto:
>>>
>>>> Hi Alberto,
>>>>
>>>> On Sat, 27 Jul 2019 at 10:09, Alberto Barbaro via llvm-dev
>>>> <llvm-dev at lists.llvm.org> wrote:
>>>> > Having the reference I to the instruction in bold.Can i
efficiently
>>>> know that the variable %11 was "created" by the %3 =
alloca [40 x i8],
>>>> align 16.
>>>>
>>>> Yes, I.getOperand(0) *is* the AllocaInst in this case. So for
example
>>>> isa<AllocaInst>(I.getOperand(0)) will return true. And if
you care
>>>> about more details you can dyn_cast<AllocaInst> it and
check any other
>>>> properties you want.
>>>>
>>>>
>>> I would like to use the approach you described considering I to be
a
>>> reference to the icmp instruction ( %13 = icmp eq i32 %12, 66 ).
From what
>>> I understood i should do something like:
>>>
>>> Instruction* source;
>>>
>>> if(source = dyn_cast<AllocaInst>(I.getOperand(0))) {
>>>     cout << "Alloca Inst" << endl;
>>>     I.dump();
>>>     getchar();
>>> }
>>>
>>> I thought I.getOperand(0) was a reference to the instruction that
have
>>> created %12. What am I missing?
>>>
>>>
>>>> Cheers.
>>>>
>>>> Tim.
>>>>
>>>
>>> Thanks again
>>> Alberto
>>>
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>
>
> --
> Jakub Kuderski
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190730/7016fb2d/attachment.html>