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