llvm / llvm/llvm-project

[LoopInterchange] PerInstrOrderCost can misclassify access order when address computation is split across multiple GEPs

Open
#198,261 2 comments 0 reactions 0 assignees View on GitHub
new issue
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.