I don't want to get into the debate w.r.t. which IR style is better - ask me over beer if you care about my opinions - but as an FYI, there are serious proposals being worked on to introduce some notion of memory def-use edges to help in analysing memory operations. I don't think we've settled on a concrete proposal yet, but I wouldn't be surprised to see something in the form of an analysis pass which produces 'def-use' information for memory operations. Philip On 02/22/2015 07:47 PM, Jeehoon Kang wrote:> Thank you David and Jeremy! > > I am quite convinced that LLVM IR in SSA form already expresses data > dependence quite well, as said David and Jeremy. Expressing IR in DAG > may enable more optimizations on memory operations, but the benefit > seems to be not so much. > > Furthermore, I strongly agree with Jeremy in that instruction orders > should be preserved for -O1 for debugging purposes. > > Thank you, > Jeehoon > > > 2015-02-21 21:41 GMT+09:00 Jeremy Lakeman <Jeremy.Lakeman at gmail.com > <mailto:Jeremy.Lakeman at gmail.com>>: > > > > On Sat, Feb 21, 2015 at 6:38 PM, David Chisnall > <David.Chisnall at cl.cam.ac.uk <mailto:David.Chisnall at cl.cam.ac.uk>> > wrote: > > > > On 21 Feb 2015, at 05:59, Jeehoon Kang > <jeehoon.kang at sf.snu.ac.kr <mailto:jeehoon.kang at sf.snu.ac.kr>> > wrote: > > > > this is Jeehoon Kang, a CS PhD student and a newbie to LLVM. > > > > I am wondering why LLVM IR's basic block consists of a list > of instructions, > > rather than a DAG of instruction as in the low level > (ISelectionDAG). > > SSA form is implicitly a DAG, defined by the uses relation > (registers in LLVM can be thought of as edges between > instructions). It is not *solely* a DAG, however. For > example, in some places the order of two loads matters - > particularly when they are atomic operations - it's only > side-effect-free operations that can be represented entirely > as a DAG. In general, optimisations that work best with a DAG > representation deal with use-def chains and are not explicitly > aware of the sequence of instructions in the basic blocks > unless they need to be. > > The order of loads is still essentially a directed graph. > Currently that information is implicit in the basic block order, > and optimisations need to know if it is safe to screw around with > them. Perhaps these relationships would be better represented > explicitly instead, in which case the order of instructions in a > block would be less relevant. > > Though of course machine instructions need to be ordered, -O0 > shouldn't mess with the order of operations for debugging > purposes, and you do need some deterministic way to iterate over > instructions. So I'm not certain there'd be much benefit in trying > to remove the current ordering of instructions. If you want to > walk the instructions as a DAG you can, if you want to walk them > in execution order you can do that too. > > David > > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu <mailto:LLVMdev at cs.uiuc.edu> > http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > > > > > > -- > Jeehoon Kang (Ph.D. student) <http://sf.snu.ac.kr/jeehoon.kang> > Software Foundations Laboratory <http://sf.snu.ac.kr> > Seoul National University <http://www.snu.ac.kr> > > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150223/1663dc8f/attachment.html>
I've noticed this subtle issue before as well when building a frontend language that takes DAGs of function calls rather than lists. While an optimizer would be able to make good use of this information from the frontend, I have to topo-sort flatten this information out when outputting IR or build my own optimization pass concepts. In the frontend we add the idea of nested-but-not-passed function arguments. This allows something like "store (i32 a, i32* b, sequenced (store(i32c, i32*d)))" Where things inside "sequenced" are performed in a nested format but the return values are discarded and not passed to the enclosing expression. Perhaps something like this could spawn some ideas. From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at cs.uiuc.edu] On Behalf Of Philip Reames Sent: Monday, February 23, 2015 1:48 PM To: Jeehoon Kang; Jeremy Lakeman Cc: LLVM Developers Mailing List Subject: Re: [LLVMdev] LLVM IR in DAG form I don't want to get into the debate w.r.t. which IR style is better - ask me over beer if you care about my opinions - but as an FYI, there are serious proposals being worked on to introduce some notion of memory def-use edges to help in analysing memory operations. I don't think we've settled on a concrete proposal yet, but I wouldn't be surprised to see something in the form of an analysis pass which produces 'def-use' information for memory operations. Philip On 02/22/2015 07:47 PM, Jeehoon Kang wrote: Thank you David and Jeremy! I am quite convinced that LLVM IR in SSA form already expresses data dependence quite well, as said David and Jeremy. Expressing IR in DAG may enable more optimizations on memory operations, but the benefit seems to be not so much. Furthermore, I strongly agree with Jeremy in that instruction orders should be preserved for -O1 for debugging purposes. Thank you, Jeehoon 2015-02-21 21:41 GMT+09:00 Jeremy Lakeman <Jeremy.Lakeman at gmail.com <mailto:Jeremy.Lakeman at gmail.com> >: On Sat, Feb 21, 2015 at 6:38 PM, David Chisnall <David.Chisnall at cl.cam.ac.uk <mailto:David.Chisnall at cl.cam.ac.uk> > wrote:> On 21 Feb 2015, at 05:59, Jeehoon Kang <jeehoon.kang at sf.snu.ac.kr<mailto:jeehoon.kang at sf.snu.ac.kr> > wrote:> > this is Jeehoon Kang, a CS PhD student and a newbie to LLVM. > > I am wondering why LLVM IR's basic block consists of a list ofinstructions,> rather than a DAG of instruction as in the low level (ISelectionDAG).SSA form is implicitly a DAG, defined by the uses relation (registers in LLVM can be thought of as edges between instructions). It is not *solely* a DAG, however. For example, in some places the order of two loads matters - particularly when they are atomic operations - it's only side-effect-free operations that can be represented entirely as a DAG. In general, optimisations that work best with a DAG representation deal with use-def chains and are not explicitly aware of the sequence of instructions in the basic blocks unless they need to be. The order of loads is still essentially a directed graph. Currently that information is implicit in the basic block order, and optimisations need to know if it is safe to screw around with them. Perhaps these relationships would be better represented explicitly instead, in which case the order of instructions in a block would be less relevant. Though of course machine instructions need to be ordered, -O0 shouldn't mess with the order of operations for debugging purposes, and you do need some deterministic way to iterate over instructions. So I'm not certain there'd be much benefit in trying to remove the current ordering of instructions. If you want to walk the instructions as a DAG you can, if you want to walk them in execution order you can do that too. David _______________________________________________ LLVM Developers mailing list LLVMdev at cs.uiuc.edu <mailto:LLVMdev at cs.uiuc.edu> http://llvm.cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev -- Jeehoon Kang (Ph.D. student) <http://sf.snu.ac.kr/jeehoon.kang> Software Foundations Laboratory <http://sf.snu.ac.kr> Seoul National University <http://www.snu.ac.kr> _______________________________________________ LLVM Developers mailing list LLVMdev at cs.uiuc.edu <mailto:LLVMdev at cs.uiuc.edu> http://llvm.cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150223/600c7aea/attachment.html>
I'd suggest you start a new thread with this question. It's unlikely to get much attention here. Its gone from being a very abstract question to a "how do I represent X" question. You'll probably also need to provide more information about the sequencing rules for your source language. Are there aliasing guarantees? Restrictions on the functions called? etc... On 02/23/2015 01:14 PM, Colin LeMahieu wrote:> > I’ve noticed this subtle issue before as well when building a frontend > language that takes DAGs of function calls rather than lists. While > an optimizer would be able to make good use of this information from > the frontend, I have to topo-sort flatten this information out when > outputting IR or build my own optimization pass concepts. > > In the frontend we add the idea of nested-but-not-passed function > arguments. This allows something like “store (i32 a, i32* b, > sequenced (store(i32c, i32*d)))” > > Where things inside “sequenced” are performed in a nested format but > the return values are discarded and not passed to the enclosing > expression. > > Perhaps something like this could spawn some ideas. > > *From:*llvmdev-bounces at cs.uiuc.edu > [mailto:llvmdev-bounces at cs.uiuc.edu] *On Behalf Of *Philip Reames > *Sent:* Monday, February 23, 2015 1:48 PM > *To:* Jeehoon Kang; Jeremy Lakeman > *Cc:* LLVM Developers Mailing List > *Subject:* Re: [LLVMdev] LLVM IR in DAG form > > I don't want to get into the debate w.r.t. which IR style is better - > ask me over beer if you care about my opinions - but as an FYI, there > are serious proposals being worked on to introduce some notion of > memory def-use edges to help in analysing memory operations. I don't > think we've settled on a concrete proposal yet, but I wouldn't be > surprised to see something in the form of an analysis pass which > produces 'def-use' information for memory operations. > > Philip > > On 02/22/2015 07:47 PM, Jeehoon Kang wrote: > > Thank you David and Jeremy! > > I am quite convinced that LLVM IR in SSA form already expresses > data dependence quite well, as said David and Jeremy. Expressing > IR in DAG may enable more optimizations on memory operations, but > the benefit seems to be not so much. > > Furthermore, I strongly agree with Jeremy in that instruction > orders should be preserved for -O1 for debugging purposes. > > Thank you, > > Jeehoon > > 2015-02-21 21:41 GMT+09:00 Jeremy Lakeman > <Jeremy.Lakeman at gmail.com <mailto:Jeremy.Lakeman at gmail.com>>: > > On Sat, Feb 21, 2015 at 6:38 PM, David Chisnall > <David.Chisnall at cl.cam.ac.uk > <mailto:David.Chisnall at cl.cam.ac.uk>> wrote: > > > > On 21 Feb 2015, at 05:59, Jeehoon Kang > <jeehoon.kang at sf.snu.ac.kr > <mailto:jeehoon.kang at sf.snu.ac.kr>> wrote: > > > > this is Jeehoon Kang, a CS PhD student and a newbie to LLVM. > > > > I am wondering why LLVM IR's basic block consists of a > list of instructions, > > rather than a DAG of instruction as in the low level > (ISelectionDAG). > > SSA form is implicitly a DAG, defined by the uses relation > (registers in LLVM can be thought of as edges between > instructions). It is not *solely* a DAG, however. For > example, in some places the order of two loads matters - > particularly when they are atomic operations - it's only > side-effect-free operations that can be represented > entirely as a DAG. In general, optimisations that work > best with a DAG representation deal with use-def chains > and are not explicitly aware of the sequence of > instructions in the basic blocks unless they need to be. > > The order of loads is still essentially a directed graph. > Currently that information is implicit in the basic block > order, and optimisations need to know if it is safe to screw > around with them. Perhaps these relationships would be better > represented explicitly instead, in which case the order of > instructions in a block would be less relevant. > > Though of course machine instructions need to be ordered, -O0 > shouldn't mess with the order of operations for debugging > purposes, and you do need some deterministic way to iterate > over instructions. So I'm not certain there'd be much benefit > in trying to remove the current ordering of instructions. If > you want to walk the instructions as a DAG you can, if you > want to walk them in execution order you can do that too. > > David > > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu <mailto:LLVMdev at cs.uiuc.edu> > http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > > > > -- > > Jeehoon Kang (Ph.D. student) <http://sf.snu.ac.kr/jeehoon.kang> > > Software Foundations Laboratory <http://sf.snu.ac.kr> > > Seoul National University <http://www.snu.ac.kr> > > > > > _______________________________________________ > > LLVM Developers mailing list > > LLVMdev at cs.uiuc.edu <mailto:LLVMdev at cs.uiuc.edu> http://llvm.cs.uiuc.edu > > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150223/73e8e402/attachment.html>