<html><head></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div>Further to my earlier question, I'm perhaps a bit confused about memory serialisation. The following example, compiled using clang for the MSP430:</div><div><br></div><div>target datalayout = "e-p:16:16:16-i8:8:8-i16:16:16-i32:16:32-n8:16"</div><div>target triple = "msp430-??-??"</div><div><br></div><div>@y = common global i16 0, align 2</div><div>@x = common global i16 0, align 2</div><div><br></div><div>define void @f() nounwind {</div><div>entry:</div><div> %0 = load i16* @y, align 2, !tbaa !0</div><div> %1 = load volatile i16* @x, align 2, !tbaa !0</div><div> %add = add i16 %1, %0</div><div> store i16 %add, i16* @y, align 2, !tbaa !0</div><div> ret void</div><div>}</div><div><br></div><div>has a chain store->load volatile->load. I thought this meant that the load volatile had to occur _after_ the load but the MSP430 backend selects the ADD16mm instruction for which I suspect the order of operand access isn't specified. So, does the chain mean "no earlier than" rather than "later than"?</div><div> </div><div><div>On 14 Aug 2012, at 16:43, Steve Montgomery wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">I looked into those patches but I don't think they will help in my situation because my problems occur during instruction selection rather than scheduling.<div><div><br></div><div>A simple and concrete example is a pattern like:</div><div><br></div><div> [(set GR:$dst (add GR:$src (nvload addr:$mem)))]</div><div><br></div><div>where nvload matches a load provided that isVolatile() is false.</div><div><br></div><div>If the selection DAG looks like:</div><div><br></div><div><font class="Apple-style-span" face="'Courier New'"> | |</font></div><div><font class="Apple-style-span" face="'Courier New'"> LD1 LD2</font></div><div><font class="Apple-style-span" face="'Courier New'"> ^ ^</font></div><div><font class="Apple-style-span" face="'Courier New'"> | |</font></div><div><font class="Apple-style-span" face="'Courier New'"> \ /</font></div><div><font class="Apple-style-span" face="'Courier New'"> add</font></div><div><font class="Apple-style-span" face="'Courier New'"> ^</font></div><div><font class="Apple-style-span" face="'Courier New'"> |</font></div><div><font class="Apple-style-span" face="'Courier New'"> \ /</font></div><div><font class="Apple-style-span" face="'Courier New'"> ST</font></div><div> </div><div>and the chain like:</div><div><br></div><div><font class="Apple-style-span" face="'Courier New'"> LD1 LD2</font></div><div><font class="Apple-style-span" face="'Courier New'"> ^ ^</font></div><div><font class="Apple-style-span" face="'Courier New'"> | |</font></div><div><font class="Apple-style-span" face="'Courier New'"> \ /</font></div><div><font class="Apple-style-span" face="'Courier New'"> TokenFactor</font></div><div><font class="Apple-style-span" face="'Courier New'"> ^</font></div><div><font class="Apple-style-span" face="'Courier New'"> |</font></div><div><span class="Apple-style-span" style="font-family: 'Courier New'; "> ST</span></div><div> </div><div>then the add instruction is selected. However, if operand 1 of the add is a volatile load, then the chain looks like:</div><div><br></div><div><div><font class="Apple-style-span" face="'Courier New'"> LD1</font></div><div><font class="Apple-style-span" face="'Courier New'"> ^ </font></div><div><font class="Apple-style-span" face="'Courier New'"> |</font></div><div><span class="Apple-style-span" style="font-family: 'Courier New'; "> </span><span class="Apple-style-span" style="font-family: 'Courier New'; "> LD2Volatile</span></div><div><font class="Apple-style-span" face="'Courier New'"> |</font></div><div><span class="Apple-style-span" style="font-family: 'Courier New'; "> ST</span></div></div><div><span class="Apple-style-span" style="font-family: 'Courier New'; "><br></span></div><div>In this case the add instruction cannot be selected. The operator is commutative, so instruction selection matches the non-volatile load against the operand 1 but then fails because to select this instruction would mean that the volatile load into a register (to match operand 0) would occur before the non-volatile load that's folded into the instruction.</div><div><br></div><div>I can get this instruction to be selected by changing the way loads are built into the selection DAG, i.e. making the chain:</div><div><div><font class="Apple-style-span" face="'Courier New'"><br></font></div><div><font class="Apple-style-span" face="'Courier New'"> LD1 LD2Volatile</font></div><div><font class="Apple-style-span" face="'Courier New'"> ^ ^</font></div><div><font class="Apple-style-span" face="'Courier New'"> | |</font></div><div><font class="Apple-style-span" face="'Courier New'"> \ /</font></div><div><font class="Apple-style-span" face="'Courier New'"> TokenFactor</font></div><div><font class="Apple-style-span" face="'Courier New'"> ^</font></div><div><font class="Apple-style-span" face="'Courier New'"> |</font></div><div><span class="Apple-style-span" style="font-family: 'Courier New'; "> ST</span></div></div><div><span class="Apple-style-span" style="font-family: 'Courier New'; "><br></span></div><div>Given what the LRM says about volatile accesses, this seems valid but I take Hal's point about there being code that might not be expecting such a chain.</div><div><br></div><div>It's a matter of changing a few lines in SelectionDAGBuilder.cpp to achieve what I want so I think I'll go ahead and see what happens.</div><div><br></div><div>If Hal or anyone else has any further thoughts on the potential problems with doing so then I'd be glad to know.</div><div><br></div><div>Thanks</div><div><br></div><div>Steve Montgomery</div><div><br></div><div>On 13 Aug 2012, at 20:09, Hal Finkel wrote:</div><div><div><br class="Apple-interchange-newline"><blockquote type="cite"><div>Steve,<br><br>I had created a patch last year that does something similar to what you<br>describe for regular loads and stores using aliasing information. I<br>think that the last message in the thread was:<br><a href="http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20120402/140299.html">http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20120402/140299.html</a><br><br>This approach has worked for me, but it is not the preferred solution<br>going forward. The preferred solution is to keep the "critical<br>chain" as is (partly because there are places in some of the backend<br>lowering code that assume it exists in its current form), and just<br>update the scheduler to be more intelligent about how it forms the<br>dependency graph. This has since been developed for the new MI<br>scheduling framework by Sergei Larin, and was committed in r156842<br>(last message in the discussion thread was<br><a href="http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20120507/142659.html">http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20120507/142659.html</a>)<br><br>I would recommend trying something like Sergei's solution first, and<br>fall back to trying to play with the critical chain only if that can't<br>or won't work.<br><br> -Hal<br><br>On Mon, 13 Aug 2012 11:29:18 +0100<br>Steve Montgomery <<a href="mailto:stephen.montgomery3@btinternet.com">stephen.montgomery3@btinternet.com</a>> wrote:<br><br><blockquote type="cite">I've got a question about how SelectionDAGBuilder treats loads.<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">The LLVM Language Reference Manual explicitly states that the order<br></blockquote><blockquote type="cite">of volatile operations may be changed relative to non-volatile<br></blockquote><blockquote type="cite">operations. However, when the SelectionDAGBuilder in LLVM 3.1<br></blockquote><blockquote type="cite">encounters a volatile load, it flushes all pending loads and then<br></blockquote><blockquote type="cite">chains the volatile load onto them meaning that the volatile load<br></blockquote><blockquote type="cite">must be scheduled after those loads. While this behaviour isn't<br></blockquote><blockquote type="cite">wrong, it seems to reduce the scope for efficient instruction<br></blockquote><blockquote type="cite">selection.<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">Is there any reason not to modify the behaviour of<br></blockquote><blockquote type="cite">SelectionDAGBuilder::visitLoad() so that volatile loads don't cause<br></blockquote><blockquote type="cite">SelectionDAGBuilder::getRoot() to be called. Instead, they can be<br></blockquote><blockquote type="cite">chained together with the head of the chain being stored in<br></blockquote><blockquote type="cite">PendingLoads. Then when something else calls<br></blockquote><blockquote type="cite">SelectionDAGBuilder::getRoot(), the chain of volatile loads is<br></blockquote><blockquote type="cite">TokenFactored together with the non-volatile loads. I've tried this<br></blockquote><blockquote type="cite">out and it seems to do what I want but as I'm fairly inexperienced<br></blockquote><blockquote type="cite">with LLVM, I'm not sure whether there's something else preventing<br></blockquote><blockquote type="cite">this strategy from working.<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">The reason I noticed this is because I have been developing a<br></blockquote><blockquote type="cite">back-end for a target in which some instructions are implemented as<br></blockquote><blockquote type="cite">pseudos which will be expanded into a pair of instructions. Each of<br></blockquote><blockquote type="cite">the two operands of the pseudo can be a load but as the expansion<br></blockquote><blockquote type="cite">accesses the right operand twice, I don't want to match a volatile<br></blockquote><blockquote type="cite">load for this operand. For example, in:<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite"> %0 = load i16* @y, align 2, !tbaa !0<br></blockquote><blockquote type="cite"> %1 = load volatile i16* @x, align 2, !tbaa !0<br></blockquote><blockquote type="cite"> %add = add i16 %0, %1 <br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">the volatile load is sequenced after the non-volatile load which<br></blockquote><blockquote type="cite">means that the non-volatile load can't match the left operand of the<br></blockquote><blockquote type="cite">add because this would create a scheduling cycle. This means both<br></blockquote><blockquote type="cite">loads are selected as load instructions, resulting in use of an extra<br></blockquote><blockquote type="cite">register and an extra instruction. If I change the behaviour of<br></blockquote><blockquote type="cite">SelectionDAGBuilder::visitLoad() as described then I get just two<br></blockquote><blockquote type="cite">instructions. _______________________________________________ LLVM<br></blockquote><blockquote type="cite">Developers mailing list <a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a><br></blockquote><blockquote type="cite"><a href="http://llvm.cs.uiuc.edu">http://llvm.cs.uiuc.edu</a><br></blockquote><blockquote type="cite"><a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br></blockquote><br><br><br>-- <br>Hal Finkel<br>Postdoctoral Appointee<br>Leadership Computing Facility<br>Argonne National Laboratory<br></div></blockquote></div><br></div></div></div>_______________________________________________<br>LLVM Developers mailing list<br><a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu">http://llvm.cs.uiuc.edu</a><br><a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br></blockquote></div><br></body></html>