[llvm-dev] Efficient way to identify an instruction

Mon Jul 29 08:19:16 PDT 2019

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>