<div dir="ltr"><div>Hi Adam,</div><div><br></div>Jingyue is right. We need to keep things in 32 bits because 64 bit arithmetic is more expensive and because one 64 bit register consumes two 32 bit registers.<div><div><br></div><div>To add a bit more background: we would often emit worse code if we widened in indvars and then narrowed in the NVPTX backend later because we often would not be able to narrow AFAICT. Consider this general pattern where everything is 32 bit:<div><br></div><div> for (int i = a; i < b; i += s) {</div><div> // ...<br> }</div><div><br></div><div>Suppose we widen i to be 64 bit:</div><div><br></div><div><div> for (int64 i = a; i < b; i += s) {</div><div> // ...<br> }</div></div><div><br></div><div>As an example, suppose a = 0, b = INT_MAX, s = 2. The final value of i that makes the loop terminate would then be INT_MAX+1, so we cannot narrow i to 32 bits. To narrow in general, we have to prove that a, b and s take on only values where narrowing is sound. That's often not possible. I suppose an alternative would be to issue an assume intrinsic restricting the range of i, though I prefer making scalar evolution more powerful since that should be more generally useful.</div><div><br></div><div>Bjarke<br></div><div><br></div></div></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Jun 29, 2015 at 8:57 PM, Jingyue Wu <span dir="ltr"><<a href="mailto:jingyue@google.com" target="_blank">jingyue@google.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Hi Adam, <div><br></div><div>Indvar widening can sometimes be harmful for architectures (e.g. NVPTX and AMDGPU) where wider integer operations are more expensive (<a href="https://urldefense.proofpoint.com/v2/url?u=https-3A__llvm.org_bugs_show-5Fbug.cgi-3Fid-3D21148&d=AwMFaQ&c=8hUWFZcy2Z-Za5rBPlktOQ&r=Mfk2qtn1LTDThVkh6-oGglNfMADXfJdty4_bhmuhMHA&m=cJO7ekBW4iH96UxthtdL4pE3_6LtTUML2l3wmpoMGlU&s=Q6RmrzzFh1ncggu3phWtk0nUkwfACNO74GtoSfjVgiY&e=" target="_blank">https://llvm.org/bugs/show_bug.cgi?id=21148</a>). <span style="line-height:1.5;font-size:13.1999998092651px">For this reason, we disabled indvar widening in NVPTX in </span><span style="line-height:1.5;font-size:13.1999998092651px"><a href="https://urldefense.proofpoint.com/v2/url?u=http-3A__reviews.llvm.org_D6196&d=AwMFaQ&c=8hUWFZcy2Z-Za5rBPlktOQ&r=Mfk2qtn1LTDThVkh6-oGglNfMADXfJdty4_bhmuhMHA&m=cJO7ekBW4iH96UxthtdL4pE3_6LtTUML2l3wmpoMGlU&s=7d41CwhlYB1qiWvUE0ixcSSaqcvozdxYYDqUdYi6Y24&e=" target="_blank">http://reviews.llvm.org/D6196</a>. </span><div><span style="font-size:13.1999998092651px;line-height:1.5"><br></span></div><div><span style="font-size:13.1999998092651px;line-height:1.5">Hope it helps. </span></div></div><span class="HOEnZb"><font color="#888888"><div><span style="font-size:13.1999998092651px;line-height:1.5"><br></span></div><div><span style="font-size:13.1999998092651px;line-height:1.5">Jingyue</span></div></font></span></div><div class="HOEnZb"><div class="h5"><br><div class="gmail_quote"><div dir="ltr">On Mon, Jun 29, 2015 at 11:59 AM Adam Nemet <<a href="mailto:anemet@apple.com" target="_blank">anemet@apple.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><br>
> On Jun 26, 2015, at 4:01 PM, Bjarke Roune <<a href="mailto:broune@google.com" target="_blank">broune@google.com</a>> wrote:<br>
><br>
> *** Summary<br>
> I'd like to propose (and implement) functionality in LLVM to determine when a poison value from an instruction is guaranteed to produce undefined behavior. I want to use that to improve handling of nsw, inbounds etc. flags in scalar evolution and LSR. I imagine that there would be other uses for it. I'd like feedback on this idea before I proceed with it.<br>
><br>
><br>
> *** Details<br>
> Poison values do produce undefined behavior if the poison becomes externally observable. A load or store to a poison address value is externally observable and I'd like to use that in a simple analysis pass to derive guarantees that certain overflows would produce undefined behavior, not just poison.<br>
><br>
> Scalar evolution (and hence LSR) cannot currently make much use of the nsw and similar flags on instructions. That is because two instructions can map to the same scev even if one instruction has the nsw flag and the other one does not. If we applied the nsw flag to the scev, the scev for the instruction without the nsw flag would then incorrectly have the nsw flag.<br>
><br>
> Scalar evolution would be able to use the nsw flag from an instruction for recurrences when the loop header dominates the entire loop, the instruction with nsw post-dominates the loop header and undefined behavior is guaranteed on wrap via the poison value analysis pass that I'd like to write.<br>
><br>
> What do you think? Do we already have something similar to this?<br>
><br>
> Bjarke<br>
><br>
><br>
><br>
> *** PS: What got me thinking about this:<br>
> My immediate motivation is that I'd like LSR to be able to create induction variables for expressions like &ptr[i + offset] where i and offset are 32 bit integers, ptr is a loop-invariant 64 bit pointer, i is an induction variable and offset is loop-invariant. For that to happen, scalar evolution needs to propagate the nsw flag from i + offset to the scev so that it can transform<br>
><br>
> ((4 * (sext i32 {%offset,+,1}<nw><%loop> to i64))<nsw> + %ptr)<nsw><br>
><br>
> to<br>
><br>
> {((4 * (sext i32 %offset to i64)) + %ptr),+,4}<nsw><%loop><br>
<br>
I guess what I am missing here why indvars does not create an i64 induction variable for this?<br>
<br>
Adam<br>
<br>
<br>
><br>
> Currently the inner <nsw> is actually <nw>, which blocks the transformation (the outer two nsw's shouldn't currently be there either, as it's the same issue for inbounds on GEP: see llvm bug 23527)<br>
> _______________________________________________<br>
> LLVM Developers mailing list<br>
> <a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu" rel="noreferrer" target="_blank">http://llvm.cs.uiuc.edu</a><br>
> <a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" rel="noreferrer" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
<br>
<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu" rel="noreferrer" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" rel="noreferrer" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
</blockquote></div>
</div></div></blockquote></div><br></div>