Program order in inst_iterator?

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

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.

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?

Anirudh

Anirudh Sivaraman 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.

Anirudh Sivaraman 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).

Regards,

John Criswell

Anirudh Sivaraman 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.

Anirudh

Anirudh Sivaraman 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

There's also scc_iterator which lets you do a postorder traversal of
SCCs in the CFG.

Check out Eli's blog post about this:

http://eli.thegreenplace.net/2013/09/16/analyzing-function-cfgs-with-llvm

Tobias