<div dir="ltr">Hello,<div><br></div><div>I was wondering if we had a way to strength reduce getelementptr today.</div><div><br></div><div>For the following code:</div><div><br></div><div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><font face="monospace, monospace">void func(float (&A)[132][140]) {<br> for (int i = 0; i < 132; ++i)<br> for (int j = 0; j < 140; ++j)<br> A[i][j] += 1;<br>}</font></blockquote><div><br></div><div>We will generate: (annotated with SCEV)</div><div><br></div><div><div><font face="monospace, monospace">define void @func([132 x [140 x float]]* nocapture dereferenceable(73920)) local_unnamed_addr #0 {</font></div><div><font face="monospace, monospace"> br label %2</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">; <label>:2: ; preds = %11, %1</font></div><div><font face="monospace, monospace">; loop<%2> at depth 1 with exact backedge-taken count of 131</font></div><div><font face="monospace, monospace">; %12 = {1,+,1}<nuw><nsw><%2></font></div><div><font face="monospace, monospace">; %3 = {0,+,1}<nuw><nsw><%2></font></div><div><font face="monospace, monospace"> %3 = phi i64 [ 0, %1 ], [ %12, %11 ]</font></div><div><font face="monospace, monospace"> br label %4</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">; <label>:4: ; preds = %4, %2</font></div><div><font face="monospace, monospace">; loop<%4> at depth 2 with exact backedge-taken count of 139</font></div><div><font face="monospace, monospace">; %5 = {0,+,1}<nuw><nsw><%4></font></div><div><font face="monospace, monospace"> %5 = phi i64 [ 0, %2 ], [ %9, %4 ]</font></div><div><font face="monospace, monospace">; %3 = {0,+,1}<nuw><nsw><%2></font></div><div><font face="monospace, monospace">; %6 = {{%0,+,560}<nsw><%2>,+,4}<nw><%4></font></div><div><font face="monospace, monospace" color="#ff0000"> %6 = getelementptr inbounds [132 x [140 x float]], [132 x [140 x float]]* %0, i64 0, <b>i64 %3, i64 %5</b></font></div><div><font face="monospace, monospace"> %7 = load float, float* %6, align 4, !tbaa !2</font></div><div><font face="monospace, monospace"> %8 = fadd float %7, 1.000000e+00</font></div><div><font face="monospace, monospace"> store float %8, float* %6, align 4, !tbaa !2</font></div><div><font face="monospace, monospace">; %9 = {1,+,1}<nuw><nsw><%4></font></div><div><font face="monospace, monospace"> %9 = add nuw nsw i64 %5, 1</font></div><div><font face="monospace, monospace"> %10 = icmp eq i64 %9, 140</font></div><div><font face="monospace, monospace"> br i1 %10, label %11, label %4</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">; <label>:11: ; preds = %4</font></div><div><font face="monospace, monospace">; loop<%2> at depth 1 with exact backedge-taken count of 131</font></div><div><font face="monospace, monospace">; %3 = {0,+,1}<nuw><nsw><%2></font></div><div><font face="monospace, monospace">; %12 = {1,+,1}<nuw><nsw><%2></font></div><div><font face="monospace, monospace"> %12 = add nuw nsw i64 %3, 1</font></div><div><font face="monospace, monospace"> %13 = icmp eq i64 %12, 132</font></div><div><font face="monospace, monospace"> br i1 %13, label %14, label %2</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">; <label>:14: ; preds = %11</font></div><div><font face="monospace, monospace"> ret void</font></div><div><font face="monospace, monospace">}</font></div></div><div><br></div><div>And we see clearly that the gep is "complicated" in the sense that it does two addition and two multiplication.</div><div><br></div><div>Instead we could produce the following code:</div><div><br></div><div><div><font face="monospace, monospace">define void @func([132 x [140 x float]]* nocapture dereferenceable(73920)) local_unnamed_addr #0 {</font></div><div><font face="monospace, monospace"> br label %2</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">; <label>:2: ; preds = %12, %1</font></div><div><font face="monospace, monospace">; loop<%2> at depth 1 with exact backedge-taken count of 131</font></div><div><font face="monospace, monospace">; %13 = {1,+,1}<nuw><nsw><%2></font></div><div><font face="monospace, monospace">; %3 = {0,+,1}<nuw><nsw><%2></font></div><div><font face="monospace, monospace"> %3 = phi i64 [ 0, %1 ], [ %13, %12 ]</font></div><div><font face="monospace, monospace">; %4 = {%0,+,560}<nsw><%2></font></div><div><font face="monospace, monospace" color="#ff0000"> %4 = getelementptr inbounds [132 x [140 x float]], [132 x [140 x float]]* %0, i64 0, <b>i64 %3</b></font></div><div><font face="monospace, monospace"> br label %5</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">; <label>:5: ; preds = %5, %2</font></div><div><font face="monospace, monospace">; loop<%5> at depth 2 with exact backedge-taken count of 139</font></div><div><font face="monospace, monospace">; %6 = {0,+,1}<nuw><nsw><%5></font></div><div><font face="monospace, monospace"> %6 = phi i64 [ 0, %2 ], [ %10, %5 ]</font></div><div><font face="monospace, monospace">; %4 = {%0,+,560}<nsw><%2></font></div><div><font face="monospace, monospace">; %7 = {{%0,+,560}<nsw><%2>,+,4}<nsw><%5></font></div><div><font face="monospace, monospace" color="#ff0000"> %7 = getelementptr inbounds [140 x float], [140 x float]* %4, i64 0, <b>i64 %6</b></font></div><div><font face="monospace, monospace"> %8 = load float, float* %7, align 4, !tbaa !2</font></div><div><font face="monospace, monospace"> %9 = fadd float %8, 1.000000e+00</font></div><div><font face="monospace, monospace"> store float %9, float* %7, align 4, !tbaa !2</font></div><div><font face="monospace, monospace">; %10 = {1,+,1}<nuw><nsw><%5></font></div><div><font face="monospace, monospace"> %10 = add nuw nsw i64 %6, 1</font></div><div><font face="monospace, monospace"> %11 = icmp eq i64 %10, 140</font></div><div><font face="monospace, monospace"> br i1 %11, label %12, label %5</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">; <label>:12: ; preds = %5</font></div><div><font face="monospace, monospace">; loop<%2> at depth 1 with exact backedge-taken count of 131</font></div><div><font face="monospace, monospace">; %3 = {0,+,1}<nuw><nsw><%2></font></div><div><font face="monospace, monospace">; %13 = {1,+,1}<nuw><nsw><%2></font></div><div><font face="monospace, monospace"> %13 = add nuw nsw i64 %3, 1</font></div><div><font face="monospace, monospace"> %14 = icmp eq i64 %13, 132</font></div><div><font face="monospace, monospace"> br i1 %14, label %15, label %2</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">; <label>:15: ; preds = %12</font></div><div><font face="monospace, monospace"> ret void</font></div><div><font face="monospace, monospace">}</font></div></div><div><br></div><div>Where the gep has been strength reduced to one addition one multiplication.</div><div><br></div><div>Or even better (at least on the architecture I'm targeting):</div><div><br></div><div><div><font face="monospace, monospace">define void @func([132 x [140 x float]]* nocapture dereferenceable(73920)) local_unnamed_addr #0 {</font></div><div><font face="monospace, monospace">; %2 = %0</font></div><div><font face="monospace, monospace" color="#ff0000"> %2 = getelementptr inbounds [132 x [140 x float]], [132 x [140 x float]]* %0, i64 0, i64 0</font></div><div><font face="monospace, monospace" color="#000000">; %3 = (73920 + %0)<nsw></font></div><div><font face="monospace, monospace" color="#000000"> %3 = getelementptr inbounds [132 x [140 x float]], [132 x [140 x float]]* %0, i64 1, i64 0</font></div><div><font face="monospace, monospace" color="#000000"> br label %4</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">; <label>:4: ; preds = %14, %1</font></div><div><font face="monospace, monospace">; loop<%4> at depth 1 with exact backedge-taken count of 131</font></div><div><font face="monospace, monospace">; %2 = %0</font></div><div><font face="monospace, monospace">; %15 = {(560 + %0)<nsw>,+,560}<nuw><%4></font></div><div><font face="monospace, monospace">; %5 = {%0,+,560}<nuw><%4></font></div><div><font face="monospace, monospace" color="#ff0000"> %5 = phi [140 x float]* [ %2, %1 ], [ %15, %14 ]</font></div><div><font face="monospace, monospace">; %6 = {%0,+,560}<nuw><%4></font></div><div><font face="monospace, monospace" color="#ff0000"> %6 = getelementptr inbounds [140 x float], [140 x float]* %5, i64 0, i64 0</font></div><div><font face="monospace, monospace">; %7 = {(560 + %0)<nsw>,+,560}<nuw><%4></font></div><div><font face="monospace, monospace"> %7 = getelementptr inbounds [140 x float], [140 x float]* %5, i64 1, i64 0</font></div><div><font face="monospace, monospace"> br label %8</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">; <label>:8: ; preds = %8, %4</font></div><div><font face="monospace, monospace">; loop<%8> at depth 2 with exact backedge-taken count of 139</font></div><div><font face="monospace, monospace">; %6 = {%0,+,560}<nuw><%4></font></div><div><font face="monospace, monospace">; %9 = {{%0,+,560}<nuw><%4>,+,4}<nuw><%8></font></div><div><font face="monospace, monospace" color="#ff0000"> %9 = phi float* [ %6, %4 ], [ %12, %8 ]</font></div><div><font face="monospace, monospace"> %10 = load float, float* %9, align 4, !tbaa !2</font></div><div><font face="monospace, monospace"> %11 = fadd float %10, 1.000000e+00</font></div><div><font face="monospace, monospace"> store float %11, float* %9, align 4, !tbaa !2</font></div><div><font face="monospace, monospace">; %12 = {{(4 + %0)<nsw>,+,560}<nw><%4>,+,4}<nuw><%8></font></div><div><font face="monospace, monospace" color="#ff0000"> %12 = getelementptr inbounds float, float* %9, i64 1</font></div><div><font face="monospace, monospace">; %7 = {(560 + %0)<nsw>,+,560}<nuw><%4></font></div><div><font face="monospace, monospace"> %13 = icmp eq float* %12, %7</font></div><div><font face="monospace, monospace"> br i1 %13, label %14, label %8</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">; <label>:14: ; preds = %8</font></div><div><font face="monospace, monospace">; loop<%4> at depth 1 with exact backedge-taken count of 131</font></div><div><font face="monospace, monospace">; %5 = {%0,+,560}<nuw><%4></font></div><div><font face="monospace, monospace">; %15 = {(560 + %0)<nsw>,+,560}<nuw><%4></font></div><div><font face="monospace, monospace" color="#ff0000"> %15 = getelementptr inbounds [140 x float], [140 x float]* %5, i64 1</font></div><div><font face="monospace, monospace">; %3 = (73920 + %0)<nsw></font></div><div><font face="monospace, monospace"> %16 = icmp eq [140 x float]* %15, %3</font></div><div><font face="monospace, monospace"> br i1 %16, label %17, label %4</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">; <label>:17: ; preds = %14</font></div><div><font face="monospace, monospace"> ret void</font></div><div><font face="monospace, monospace">}</font></div></div><div><br></div><div>Where we only have addition by a constant (I also got rid of the induction variables, but that's just being fancy). Do we have a way to do that automatically?</div><div><br></div><div>Why don't we? (I'm guessing because that's negligible on X86)</div><div><br></div>-- <br><div class="gmail_signature"><div dir="ltr"><b>Alexandre Isoard</b><br></div></div>
</div></div>