<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Dec 9, 2015 at 11:16 AM, Preston Briggs via llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</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">A GEP can represent a potentially large tree of instructions. </div></blockquote><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>Seems like all the sub-trees are hidden from optimization;</div><div>that is, I never see licm or value numbering doing anything with them.</div></div></blockquote><div><br></div><div>Without arguing about the broader point of "we can't eliminate the *lowered* operations these turn into", the higher level issue of not really doing much with them  are often just deficiencies in those passes.</div><div>There are plenty of those kinds of deficiencies</div><div>value numbering also doesn't really value number loads or stores, so would never discover that a load and an add have the same value, etc.</div><div>Smart enough value numbering would understand the equivalence between various forms of geps.<br></div><div><br></div><div>This won't address the issue of optimizing the lowered form of course.</div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>If I rewrite the GEPs as lots of little adds and multiplies,</div><div>then opt will do a better job (I speculate this happens during lowering).</div></div></blockquote><div><br></div><div>For some definition of better job. For example,  this has a cost of making things like AA significant more difficult  </div><div><br></div><div>Thus it is likely you want the traditional answer, where the high level form is optimized as well as it can, they are lowered, and then more optimization is done.</div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><br></div><div>One of the computations that's hidden in the GEP in my example</div><div>is the non-zero effort required to get the value of a label into a register.</div><div>I'd like to expose that effort to the optimizer; instead, it seems</div><div>hidden, papered over with the GEP.</div><div><br></div><div>Your point about putting labels in global variables seems to work</div><div>if I do it by hand. Kind of embarassing though, don't you think,</div><div>introducing an indirection to achieve better code?</div><div><br></div><div>Thanks,</div><div>Preston</div><div><br></div><div><br></div><div><br></div><div><br></div></div><div class="HOEnZb"><div class="h5"><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Dec 9, 2015 at 9:17 AM, Mehdi Amini <span dir="ltr"><<a href="mailto:mehdi.amini@apple.com" target="_blank">mehdi.amini@apple.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word"><br><div><span><blockquote type="cite"><div>On Dec 9, 2015, at 9:00 AM, Preston Briggs <<a href="mailto:briggs@reservoir.com" target="_blank">briggs@reservoir.com</a>> wrote:</div><br><div><div dir="ltr">I suppose your view is reasonable, and perhaps common.<div>My own "taste" has always preferred machine-independent code</div><div>that is as simple as possible, so GEPs reduced to nothing more than an</div><div>add, etc, i.e., quite risc-like. Then optimize it to reduce the total number</div><div>of operations (as best we can), then raise the level during instruction</div><div>selection, taking advantage of available instructions.</div></div></div></blockquote><div><br></div></span><div>I’m not sure I see something related to risc-like here, it seems to me that  your problem is not GEP vs ADD but rather that you want to expose a mode where global addresses need to be loaded and can’t be referenced directly.</div><div>(Unless I misunderstood the problem which is very possible as well)</div><div><br></div><div>Maybe you could do this with a transformation that would put all the global variable addresses in a global array and reference them through the array. That’s the only workaround I could see.</div><div><br></div><div>— </div><span><font color="#888888"><div>Mehdi</div></font></span><div><div><div><br></div><div><br></div><br><blockquote type="cite"><div><div dir="ltr"><div><br></div><div>I guess my whole scheme of using opt in this context is probably wrong headed.</div><div><br></div><div>Thanks</div><div><br></div><div><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Dec 9, 2015 at 8:45 AM, Mehdi Amini <span dir="ltr"><<a href="mailto:mehdi.amini@apple.com" target="_blank">mehdi.amini@apple.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word"><br><div><span><blockquote type="cite"><div>On Dec 9, 2015, at 7:58 AM, Preston Briggs <<a href="mailto:briggs@reservoir.com" target="_blank">briggs@reservoir.com</a>> wrote:</div><br><div><div dir="ltr">I'm trying to make the IR "better", in a machine-independent fashion,<div>without having to do any lowering.</div></div></div></blockquote><div><br></div></span><div><div>The question is “would the IR be more canonical” with the representation you suggest? Why would the optimizer benefit from this representation instead of the current one in general?</div></div><div>Right now this GEP reads as an offset from a constant global, which seems pretty optimal to me.</div><div><br></div><div><div><div>My impression is that when you reach a point where the “better” is target specific, this is part of the lowering (I’m using lowering in the sense that you go away from the canonical representation the optimizer expects). I believe it is pretty common that targets need to do this kind of lowering.</div><div><br></div></div></div><div>— </div><span><font color="#888888"><div>Mehdi</div></font></span><div><div><div><br></div><br><blockquote type="cite"><div><div dir="ltr"><div><br></div><div>I've written code that rewrites GEPs as simple adds and multiplies,</div><div>which helps a lot, but there's still some sort of re-canonicalization</div><div>that's getting in my way. Is there perhaps a way to suppress it?</div></div></div></blockquote><blockquote type="cite"><div><div dir="ltr"><div><br></div><div>Thanks,</div><div>Preston</div><div><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Dec 9, 2015 at 7:47 AM, Mehdi Amini <span dir="ltr"><<a href="mailto:mehdi.amini@apple.com" target="_blank">mehdi.amini@apple.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word">I guess is has to be done as part of the lowering for such a target, either during CodegenPrepare or during something like MachineLICM.<div><br></div><div>— </div><span><font color="#888888"><div>Mehdi</div></font></span><div><div><div><br></div><div><div><br></div><div><br><div><blockquote type="cite"><div>On Dec 9, 2015, at 7:13 AM, Preston Briggs <<a href="mailto:briggs@reservoir.com" target="_blank">briggs@reservoir.com</a>> wrote:</div><br><div><div dir="ltr">On some targets with limited addressing modes,<div>getting that 64-bit relocatable but loop-invariant value into a register</div><div>requires several instructions. I'd like those several instruction outside</div><div>the loop, where they belong.</div><div><br></div><div>Yes, my experience is that something (I assume instcombine) recanonicalizes.</div><div><br></div><div>Thanks,</div><div>Preston</div><div><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Dec 8, 2015 at 11:21 PM, Mehdi Amini <span dir="ltr"><<a href="mailto:mehdi.amini@apple.com" target="_blank">mehdi.amini@apple.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word">Hi Preston,<div><div><div><br><div><blockquote type="cite"><div>On Dec 8, 2015, at 10:56 PM, Preston Briggs via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:</div><br><div><div dir="ltr">When I compile two different modules using<div><br></div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div><font face="monospace, monospace">clang -O -S -emit-llvm</font></div></blockquote><div><br></div><div>I get different .ll files, no surprise.</div><div><br></div><div>The first looks like</div><div><br></div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div><div><font face="monospace, monospace">double *v;</font></div></div><div><div><font face="monospace, monospace"><br></font></div></div><div><div><font face="monospace, monospace">double zap(long n) {</font></div></div><div><div><font face="monospace, monospace">  double sum = 0;</font></div></div><div><div><font face="monospace, monospace">  for (long i = 0; i < n; i++)</font></div></div><div><div><font face="monospace, monospace">    sum += v[i];</font></div></div><div><div><font face="monospace, monospace">  return sum;</font></div></div><div><div><font face="monospace, monospace">}</font></div></div></blockquote><div><br></div><div>yielding</div><div><br></div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div><div><font face="monospace, monospace">@v = common global double* null, align 8</font></div></div><div><div><font face="monospace, monospace"><br></font></div></div><div><div><font face="monospace, monospace">; Function Attrs: nounwind readonly uwtable</font></div></div><div><div><font face="monospace, monospace">define double @zap(i64 %n) #0 {</font></div></div><div><div><font face="monospace, monospace">entry:</font></div></div><div><div><font face="monospace, monospace">  %cmp4 = icmp sgt i64 %n, 0</font></div></div><div><div><font face="monospace, monospace">  br i1 %cmp4, label %<a href="http://for.body.lr.ph/" target="_blank">for.body.lr.ph</a>, label %for.end</font></div></div><div><div><font face="monospace, monospace"><br></font></div></div><div><div><font face="monospace, monospace"><a href="http://for.body.lr.ph/" target="_blank">for.body.lr.ph</a>:                                   ; preds = %entry</font></div></div><div><div><font face="monospace, monospace">  %0 = load double** @v, align 8, !tbaa !1</font></div></div><div><div><font face="monospace, monospace">  br label %for.body</font></div></div><div><div><font face="monospace, monospace"><br></font></div></div><div><div><font face="monospace, monospace">for.body:                                         ; preds = %for.body, %<a href="http://for.body.lr.ph/" target="_blank">for.body.lr.ph</a></font></div></div><div><div><font face="monospace, monospace">  %i.06 = phi i64 [ 0, %<a href="http://for.body.lr.ph/" target="_blank">for.body.lr.ph</a> ], [ %inc, %for.body ]</font></div></div><div><div><font face="monospace, monospace">  %sum.05 = phi double [ 0.000000e+00, %<a href="http://for.body.lr.ph/" target="_blank">for.body.lr.ph</a> ], [ %add, %for.body ]</font></div></div><div><div><font face="monospace, monospace">  %arrayidx = getelementptr inbounds double* %0, i64 %i.06</font></div></div><div><div><font face="monospace, monospace">  %1 = load double* %arrayidx, align 8, !tbaa !5</font></div></div><div><div><font face="monospace, monospace">  %add = fadd double %sum.05, %1</font></div></div><div><div><font face="monospace, monospace">  %inc = add nsw i64 %i.06, 1</font></div></div><div><div><font face="monospace, monospace">  </font></div></div><div><div><font face="monospace, monospace">%exitcond = icmp eq i64 %inc, %n</font></div></div><div><div><font face="monospace, monospace">  br i1 %exitcond, label %for.end, label %for.body</font></div></div><div><div><font face="monospace, monospace"><br></font></div></div><div><div><font face="monospace, monospace">for.end:                                          ; preds = %for.body, %entry</font></div></div><div><div><font face="monospace, monospace">  %sum.0.lcssa = phi double [ 0.000000e+00, %entry ], [ %add, %for.body ]</font></div></div><div><div><font face="monospace, monospace">  ret double %sum.0.lcssa</font></div></div><div><div><font face="monospace, monospace">}</font></div></div></blockquote><div><br></div><div>and the second looks like</div><div><br></div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div><div><font face="monospace, monospace">double v[10000];</font></div></div><div><div><br></div></div></blockquote><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div><div><font face="monospace, monospace">double zap(long n) {</font></div></div><div><div><font face="monospace, monospace">  double sum = 0;</font></div></div><div><div><font face="monospace, monospace">  for (long i = 0; i < n; i++)</font></div></div><div><div><font face="monospace, monospace">    sum += v[i];</font></div></div><div><div><font face="monospace, monospace">  return sum;</font></div></div><div><div><font face="monospace, monospace">}</font></div></div></blockquote><div><br></div><div>yielding</div><div><br></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div><div><font face="monospace, monospace">; ModuleID = 'z.c'</font></div></div><div><div><font face="monospace, monospace">target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-f128:128:128-n8:16:32:64-S128"</font></div></div><div><div><font face="monospace, monospace">target triple = "x86_64-unknown-linux-gnu"</font></div></div><div><div><font face="monospace, monospace"><br></font></div></div><div><div><font face="monospace, monospace">@v = common global [10000 x double] zeroinitializer, align 16</font></div></div><div><div><font face="monospace, monospace"><br></font></div></div><div><div><font face="monospace, monospace">; Function Attrs: nounwind readonly uwtable</font></div></div><div><div><font face="monospace, monospace">define double @zap(i64 %n) #0 {</font></div></div><div><div><font face="monospace, monospace">entry:</font></div></div><div><div><font face="monospace, monospace">  %cmp4 = icmp sgt i64 %n, 0</font></div></div><div><div><font face="monospace, monospace">  br i1 %cmp4, label %for.body, label %for.end</font></div></div><div><div><font face="monospace, monospace"><br></font></div></div><div><div><font face="monospace, monospace">for.body:                                         ; preds = %entry, %for.body</font></div></div><div><div><font face="monospace, monospace">  %i.06 = phi i64 [ %inc, %for.body ], [ 0, %entry ]</font></div></div><div><div><font face="monospace, monospace">  %sum.05 = phi double [ %add, %for.body ], [ 0.000000e+00, %entry ]</font></div></div><div><div><font face="monospace, monospace">  %arrayidx = getelementptr inbounds [10000 x double]* @v, i64 0, i64 %i.06</font></div></div><div><div><font face="monospace, monospace">  %0 = load double* %arrayidx, align 8, !tbaa !1</font></div></div><div><div><font face="monospace, monospace">  %add = fadd double %sum.05, %0</font></div></div><div><div><font face="monospace, monospace">  %inc = add nsw i64 %i.06, 1</font></div></div><div><div><font face="monospace, monospace">  %exitcond = icmp eq i64 %inc, %n</font></div></div><div><div><font face="monospace, monospace">  br i1 %exitcond, label %for.end, label %for.body</font></div></div><div><div><font face="monospace, monospace"><br></font></div></div><div><div><font face="monospace, monospace">for.end:                                          ; preds = %for.body, %entry</font></div></div><div><div><font face="monospace, monospace">  %sum.0.lcssa = phi double [ 0.000000e+00, %entry ], [ %add, %for.body ]</font></div></div><div><div><font face="monospace, monospace">  ret double %sum.0.lcssa</font></div></div><div><div><font face="monospace, monospace">}</font></div></div><div><div><font face="monospace, monospace"><br></font></div></div><div><div><font face="monospace, monospace">attributes #0 = { nounwind readonly uwtable "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }</font></div></div><div><div><font face="monospace, monospace"><br></font></div></div><div><div><font face="monospace, monospace">!llvm.ident = !{!0}</font></div></div><div><div><font face="monospace, monospace"><br></font></div></div><div><div><font face="monospace, monospace">!0 = metadata !{metadata !"Clang Front-End version 3.4.1 (tags/RELEASE_34/final)"}</font></div></div><div><div><font face="monospace, monospace">!1 = metadata !{metadata !2, metadata !2, i64 0}</font></div></div><div><div><font face="monospace, monospace">!2 = metadata !{metadata !"double", metadata !3, i64 0}</font></div></div><div><div><font face="monospace, monospace">!3 = metadata !{metadata !"omnipotent char", metadata !4, i64 0}</font></div></div><div><div><font face="monospace, monospace">!4 = metadata !{metadata !"Simple C/C++ TBAA"}</font></div></div></blockquote><div><br></div><div>(I included all the metadata and such for the 2nd case, on the off chance it matters.)</div><div><br></div><div>Is there any way I can convince licm (or something) to rip open the GEP and hoist the reference to @v outside the loop, similar to the first example?</div></div></div></blockquote><div><br></div></div><br></div></div><div>I believe that in the second case, there is no need to load the address of v as it is constant. However you have a constant address to an array, which is represented by [10000 x double]* @v in the IR, which requires to use the two-level GEP. </div></div><div><br></div><div>You “could” manage to represent it this way:</div><div><br></div><div><span>define double @zap(i64 %n) #0 {<br>entry:<br></span>  %cmp6 = icmp sgt i64 %n, 0<br>  %hoisted = bitcast [10000 x double]* @v to double*<br>  br i1 %cmp6, label %for.body.preheader, label %for.cond.cleanup<br><br>for.body.preheader:                               ; preds = %entry<br>  br label %for.body<br><br>for.cond.cleanup.loopexit:                        ; preds = %for.body<br>  %add.lcssa = phi double [ %add, %for.body ]<br>  br label %for.cond.cleanup<br><br>for.cond.cleanup:                                 ; preds = %for.cond.cleanup.loopexit, %entry<br>  %sum.0.lcssa = phi double [ 0.000000e+00, %entry ], [ %add.lcssa, %for.cond.cleanup.loopexit ]<br>  ret double %sum.0.lcssa<br><br>for.body:                                         ; preds = %for.body.preheader, %for.body<br>  %i.08 = phi i64 [ %inc, %for.body ], [ 0, %for.body.preheader ]<br>  %sum.07 = phi double [ %add, %for.body ], [ 0.000000e+00, %for.body.preheader ]<br>  %arrayidx = getelementptr double, double* %hoisted, i64 %i.08<br>  %0 = load double, double* %arrayidx, align 8, !tbaa !2<br>  %add = fadd double %sum.07, %0<br>  %inc = add nuw nsw i64 %i.08, 1<span><br>  %exitcond = icmp eq i64 %inc, %n<br></span>  br i1 %exitcond, label %for.cond.cleanup.loopexit, label %for.body<br>}</div><div><br></div><div><br></div><div>However instcombine will recanonicalize it like it was originally.</div><div><br></div><div>Since it is a GEP that operate on a constant address, this shouldn’t matter, why would you want to split this? </div><div><br></div><div>Best,</div><div><br></div><div>— </div><span><font color="#888888"><div>Mehdi</div><div><br></div></font></span></div></blockquote></div><br></div>
</div></blockquote></div><br></div></div></div></div></div></blockquote></div><br></div>
</div></blockquote></div></div></div><br></div></blockquote></div><br></div>
</div></blockquote></div></div></div><br></div></blockquote></div><br></div>
</div></div><br>_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
<br></blockquote></div><br></div></div>