[LLVMdev] Program order in inst_iterator?

[John Criswell]

On 6/16/15 1:00 PM, Anirudh Sivaraman wrote:
> On Tue, Jun 16, 2015 at 6:30 AM, John Criswell <jtcriswel at gmail.com> wrote:
>> On 6/16/15 1:09 AM, Nick Lewycky wrote:
>>> Anirudh Sivaraman wrote:
>>>> On Mon, Jun 15, 2015 at 10:50 AM, mats petersson<mats at planetcatfish.com>
>>>> wrote:
>>>>> It will iterate over the instructions in the order that they are stored
>>>>> in
>>>>> the module/function/basicblock that they belong to. And that SHOULD,
>>>>> assuming llvm-dis does what it is expected to do, be the same order.
>>>>>
>>>> Thanks for the reply. What about instruction ordering across basic
>>>> blocks? Let's say instructions IA and IB belong to basic blocks BBa
>>>> and BBb, where BBa is before BBb in program order. Then, will IA be
>>>> printed before IB?
>>>
>>> Yes, llvm-dis does print in the same order that inst_iterator visits. The
>>> llvm::Function has a linked list of llvm::BasicBlock objects. Both llvm-dis
>>> and the inst_iterator will iterate over that list, and then for each basic
>>> block iterate over the linked list of llvm::Instruction objects. Both of
>>> these lists are ordered, and their order is preserved through .ll and .bc
>>> files.
>>>
>>> However, I wouldn't call that program order, though I couldn't find a
>>> definition of the term easily. The only guarantee on the order is that the
>>> first block visited/printed is the entry block. It's entirely possible to
>>> have a three block program where A branches to C branches to B, but will be
>>> visited/printed in order A B C.
>>
>> More importantly, there's no guarantee that inst_iterator and llvm-dis will
>> iterate over blocks in the same order.  It's possible (though unlikely) that
>> llvm-dis could change to print instructions in a different order.
>>
>> If you need to examine instructions in a certain order in LLVM IR, you
>> probably want to visit definitions before uses (for data flow) or visit
>> basic blocks in an order consistent with the control-flow graph (for control
>> flow).
>>
> Thanks for these responses. So, in summary, if I need a particular
> order when visiting instructions or basic blocks, I need to do it
> myself, without relying on the LLVM API to guarantee it.

Existing LLVM passes may help (e.g., DominatorTree can help iterate over 
basic blocks so that you see definitions before uses, phi-nodes 
notwithstanding), but generally speaking, yes.

Regards,

John Criswell

>
> Anirudh
>
>> Regards,
>>
>> John Criswell
>>
>>
>>>> Anirudh
>>>>
>>>>> --
>>>>> Mats
>>>>>
>>>>> On 15 June 2015 at 18:10, Anirudh Sivaraman<sk.anirudh at gmail.com>
>>>>> wrote:
>>>>>>
>>>>>> Does inst_iterator
>>>>>>
>>>>>>
>>>>>> (http://llvm.org/docs/ProgrammersManual.html#iterating-over-the-instruction-in-a-function)
>>>>>> guarantee that the iterated instructions are in program order: the
>>>>>> order of instructions printed by llvm-dis?
>>>>>>
>>>>>> Thanks in advance,
>>>>>> Anirudh
>>>>>> _______________________________________________
>>>>>> 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
>>>>
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>
>>
>> --
>> John Criswell
>> Assistant Professor
>> Department of Computer Science, University of Rochester
>> http://www.cs.rochester.edu/u/criswell
>>


-- 
John Criswell
Assistant Professor
Department of Computer Science, University of Rochester
http://www.cs.rochester.edu/u/criswell