Is there any chance of replacing/extending the GEP instruction?<div><br></div><div>As noted in the GEP FAQ, GEPs don't support variable-length arrays; when the front ends have to support VLAs, they linearize the subscript expressions, throwing away information. The FAQ suggests that folks interested in writing an analysis that understands array indices (I'm thinking of dependence analysis) should be prepared to reverse-engineer the linearization, but I don't believe it's possible to recover all the possible subscripts, including some common and useful situations.</div>
<div><br></div><div>The FAQ suggests that one way to solve this problem is to use the SCEV library which always represents the VLA and non-VLA index in the same manner. I don't see it. Here's some code I wrote to explore how various array references are compiled:</div>
<div><br></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div><div><font face="'courier new', monospace"><b>bool preston::runOnFunction(Function &F) {</b></font></div></div><div><div><font face="'courier new', monospace"><b> errs() << "\nFunction: ";</b></font></div>
</div><div><div><font face="'courier new', monospace"><b> errs().write_escaped(F.getName()) << '\n';</b></font></div></div><div><div><font face="'courier new', monospace"><b> SE = &getAnalysis<ScalarEvolution>();</b></font></div>
</div><div><div><font face="'courier new', monospace"><b> for (inst_iterator ii = inst_begin(F), ie = inst_end(F); ii != ie; ++ii) {</b></font></div></div><div><div><font face="'courier new', monospace"><b> Instruction *inst = &*ii;</b></font></div>
</div><div><div><font face="'courier new', monospace"><b> errs() << *inst << "\n";</b></font></div></div><div><div><font face="'courier new', monospace"><b> if (StoreInst *SI = dyn_cast<StoreInst>(inst)) {</b></font></div>
</div><div><div><font face="'courier new', monospace"><b> Value *operand = SI->getPointerOperand();</b></font></div></div><div><div><font face="'courier new', monospace"><b> if (const GEPOperator *GEP = dyn_cast<GEPOperator>(operand)) {</b></font></div>
</div><div><font face="'courier new', monospace"><b> for (GEPOperator::const_op_iterator idx = GEP->idx_begin(),</b></font></div><div><font face="'courier new', monospace"><b> end = GEP->idx_end();</b></font></div>
<div><font face="'courier new', monospace"><b> idx != end;</b></font><b style="font-family:'courier new',monospace"> idx += 1) {</b></div><div><font face="'courier new', monospace"><b> const SCEV *scev = SE->getSCEV(*idx);</b></font></div>
<div><font face="'courier new', monospace"><b> errs() << *scev << "\n";</b></font></div><div><font face="'courier new', monospace"><b> }</b></font></div><div><div><font face="'courier new', monospace"><b> }</b></font></div>
</div><div><div><font face="'courier new', monospace"><b> }</b></font></div></div><div><div><font face="'courier new', monospace"><b> }</b></font></div></div><div><div><font face="'courier new', monospace"><b> return false;</b></font></div>
</div><div><div>}</div></div></blockquote><div><br></div>
<div>Basically, it zips though the instructions in a routine, dumping them out. When it finds a store, it recovers the associated GEP and dumps its operand SCEVs. To make it easy to understand, I typically write very simple test cases, e.g.,</div>
<div><br></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div><font face="'courier new', monospace"><b>void zap(long int n, long int A[]) {</b></font></div><div><font face="'courier new', monospace"><b> for (unsigned int i = 0; i < n; i++)</b></font></div>
<div><font face="'courier new', monospace"><b> A[1 + 2*i] = 0;</b></font></div><div><font face="'courier new', monospace"><b>}</b></font></div></blockquote><div><br></div><div>In this case, we see</div>
<div><br></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div><div><font face="'courier new', monospace"><b>%arrayidx = getelementptr inbounds i64* %A, i64 %add3</b></font></div></div><div><div>
<font face="'courier new', monospace"><b>store i64 0, i64* %arrayidx, align 8</b></font></div></div><div><div><font face="'courier new', monospace"><b>{1,+,2}<%for.body></b></font></div></div></blockquote>
<div><br></div><div>which is easy enough. If we have something more complex, like this</div>
<div><br></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><b style="font-family:'courier new',monospace">void z1(long int n, long int A[][100][100]) {<br></b><b style="font-family:'courier new',monospace"> for (long int i = 0; i < n; i++)<br>
</b><b style="font-family:'courier new',monospace"> for (long int j = 0; j < n; j++)<br></b><b style="font-family:'courier new',monospace"> for (long int k = 0; k < n; k++)<br></b><b style="font-family:'courier new',monospace;white-space:pre-wrap"> </b><b style="font-family:'courier new',monospace">A[1 + 2*i][3 + 4*j][5 + 6*k] = 0;</b><div>
<div>}</div></div></blockquote><div><br></div><div>we'll see</div><div><br></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div><div><font face="'courier new', monospace"><b>%arrayidx12 = getelementptr inbounds [100 x [100 x i64]]* %A, i64 %add109, i64 %add88, i64 %add</b></font></div>
</div><div><div><font face="'courier new', monospace"><b>store i64 0, i64* %arrayidx12, align 8</b></font></div></div><div><div><font face="'courier new', monospace"><b>{1,+,2}<%for.cond1.preheader></b></font></div>
</div><div><div><font face="'courier new', monospace"><b>{3,+,4}<%for.cond4.preheader></b></font></div></div><div><div><font face="'courier new', monospace"><b>{5,+,6}<%for.body6></b></font></div>
</div></blockquote><div><br></div><div>which looks great; 3 simple indices, no problem.</div>
<div>But consider this:</div><div><br></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div><div><b><font face="'courier new', monospace">void z2(long int n, long int A[][n][n][100][100]) {</font></b></div>
</div><div><div><b><font face="'courier new', monospace"> for (long int i = 0; i < n; i++)</font></b></div></div><div><div><b><font face="'courier new', monospace"> for (long int j = 0; j < n; j++)</font></b></div>
</div><div><div><b><font face="'courier new', monospace"> for (long int k = 0; k < n; k++)</font></b></div></div><div><div><span style="white-space:pre-wrap"><b><font face="'courier new', monospace"> </font></b></span><b><font face="'courier new', monospace">for (long int l = 0; l < n; l++)</font></b></div>
</div><div><div><span style="white-space:pre-wrap"><b><font face="'courier new', monospace"> </font></b></span><b><font face="'courier new', monospace">for (long int m = 0; m < n; m++)</font></b></div>
</div><div><div><span style="white-space:pre-wrap"><b><font face="'courier new', monospace"> </font></b></span><b><font face="'courier new', monospace">A[1 + 2*i][3 + 4*j][5 + 6*k][7 + 8*l][9 + 10*m] = 0;</font></b></div>
</div><div><div>}</div></div></blockquote><div><br></div><div>which produces</div><div><br></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div><div><font face="'courier new', monospace"><b>%arrayidx24 = getelementptr inbounds [100 x [100 x i64]]* %A, i64 %arrayidx21.sum, i64 %add1411, i64 %add</b></font></div>
</div><div><div><font face="'courier new', monospace"><b>store i64 0, i64* %arrayidx24, align 8</b></font></div></div><div><div><font face="'courier new', monospace"><b>{{{(5 + ((3 + %n) * %n)),+,(2 * %n * %n)}<%for.cond1.preheader>,+,(4 * %n)}<%for.cond4.preheader>,+,6}<%for.cond7.preheader></b></font></div>
</div><div><div><font face="'courier new', monospace"><b>{7,+,8}<%for.cond10.preheader></b></font></div></div><div><div><font face="'courier new', monospace"><b>{9,+,10}<%for.body12></b></font></div>
</div></blockquote><div><br></div><div>This is more tedious. There are 2 easy indices hanging from the GEP, but the rest are compressed into one SCEV. The upshot is: Whenever I look at a memory reference, I need to attempt to delinearize the first SCEV (in the order I've printed them) to look for other implied indices. (As a bonus, delinearization would sometimes be able to untangle examples where humans have linearized their own references, perhaps in antique C code, written before VLAs.) Some, like the examples above can be handled; others seem impossible, which is too bad.</div>
<div><br></div><div>Here are some examples that are hard to delinearize:</div><div><ul><li>Coupled subscripts, where an index appears in multiple subscript positions, e.g., <font face="'courier new', monospace"><b>A[i][i + j]</b></font>. Sad because the Delta test is designed to handle exactly these cases.</li>
<li>Non-linear subscripts, like <b><font face="'courier new', monospace">A[i][j*j]</font></b>. While the <b><font face="'courier new', monospace">[j*j]</font></b> subscript is hard to analyze, we might be able to disprove the dependence using the simple <b><font face="'courier new', monospace">[i]</font></b> subscript.</li>
<li>Non-linear subscripts, like <b><font face="'courier new', monospace">A[i][B[j]]</font></b>. Again, it's tough to analyze the <font face="'courier new', monospace"><b>[B[j]]</b></font> part, but we might be able to disprove the dependence using the simple <b><font face="'courier new', monospace">[i]</font></b> subscript.</li>
</ul><div>It's also plausible to analyze pairs of non-linear subscripts, like <font face="'courier new', monospace"><b>[1 + 2*B[i]]</b></font> and [<b><font face="'courier new', monospace">2*B[i]]</font></b>, easily proving there's no dependence despite our lack of knowledge about <b><font face="'courier new', monospace">B[i]</font></b>.</div>
</div><div><br></div><div>So, ...</div><div>Perhaps we could consider a new variant of the GEP instruction that lets us recover all the subscripts, without any loss of info, regardless of how absurd they might appear. The current GEP allows many subscripts, but the strides are encoded in the type. An alternative might support many subscripts, each with an explicit stride, maybe constant, maybe a parameter, maybe even the result of a computation. If we're clever, we could even handle complex accesses resulting from structs of vectors of structs of ...</div>
<div><br></div><div>I think such a change might have a fair amount of impact all through the optimizer (thinking especially of strength reduction and common-subexpression elimination), but we could also introduce a phase that explicitly linearizes a complex GEP, yielding the current, simpler forms. As long as such a linearization occurs after dependence analysis, no information would be lost and the impact to the rest of the infrastructure would be minimized.</div>
<div><br></div><div>Is such an idea completely out of the question?</div><div><br></div><div>Thanks,</div><div>
Preston</div><div><br></div>