[LoopInterchange] PerInstrOrderCost can misclassify access order when address computation is split across multiple GEPs
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
**Description**
The current implementation of the `PerInstrOrderCost` profitability heuristic in LoopInterchange can make incorrect profitability decisions when the address computation for a memory access is distributed across multiple `getelementptr` (GEP) instructions.
The issue is that the heuristic classifies memory order by scanning the direct operands of each GEP in the inner loop and looking for `SCEVAddRecExprs` associated with `OuterLoop` and `InnerLoop`. As a result, the classification depends on the local shape of a particular GEP rather than on the full memory access being performed.
Because of this, after canonicalization, or hoisting, a source access that is semantically bad-order can be incorrectly classified as good-order by the heuristic.
**Reproducer:**
https://godbolt.org/z/M87arj7nE
**Problem**
This heuristic assumes that the direct operands of a single inner-loop GEP faithfully represent the true multidimensional access order, i.e. If the first operand of GEP belongs to outer Loop, then the heuristic considers it as Good-Order
For example
```
for(int i=0; i<32; i++){
for(int j=0; j<64; j++){
// Memory instruction
}
}
```
If Memory Instruction is: `%addr = getelementptr ..., %A, %i, %j`, the heuristic assumes that `i` is outer index of memory access and `j` is the inner index of memory access.
However, that assumption does not hold after IR transformations that split address calculation across multiple instructions. In such cases:
- one part of the address may be materialized in an outer-loop GEP
- the final inner-loop GEP may expose only the remaining index computation
- the heuristic still classifies using the local operand order of that final GEP
**Example**
```
for(int i=0; i<32; i++){
for(int j=0; j<64; j++){
// Access A[j][i]
}
}
```
A source access like `A[j][i]` may be split into two steps.
Outer-loop GEP: `%invariant.gep = getelementptr ..., ptr %A, i64 %indvars.iv16`
Inner-loop GEP: `%gep = getelementptr ..., ptr %invariant.gep, i64 %indvars.iv`
The direct operands of the inner-loop GEP are `%invariant.gep`, `%indvars.iv`
Their corresponding SCEVs are:
```
Operand-1:
%invariant.gep = getelementptr inbounds nuw [4 x i8], ptr %A, i64 %indvars.iv16
Operand-1 SCEV:
{%A,+,4}<%for.cond1.preheader(Outer Loop)>
Operand-2:
%indvars.iv = phi i64 [ 0, %for.cond1.preheader ], [ %indvars.iv.next, %for.body3 ]
Operand-2 SCEV:
{0,+,1}<%for.body3(Inner Loop)>
```
So, the heuristic sees the first operand is coming from the outer loop and hence it is a Good-Order, but the original access was `A[j][i]` which is semantically Bad-order.
**Root Cause**
In effect, the heuristic is currently reasoning about:
> the order in which loop-dependent recurrences appear among the operands of one GEP
instead of reasoning about:
> the order of dimensions in the actual memory access
This makes the result sensitive to IR restructuring rather than to the true access pattern.
Contributor guide
Assessment
This issue has not been assessed yet.