llvm / llvm/llvm-project

[Clang] Missed optimization (flatten array access)

Open
#161,389 2 comments 2 reactions 0 assignees View on GitHub
llvm:instcombine llvm:optimizations missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

```
extern int (*fns[8][8])(int);

int dispatch(unsigned int state, int param) {
return fns[state / 8][state % 8](param);
}

int dispatch2(unsigned int state, int param) {
// cast to 1d flattened array
return (*(int (*(*)[64])(int))&fns)[state](param);
}
```
https://godbolt.org/z/oqjP1Pvsc

In `dispatch()`. the optimizer ought to notice that the `state` index can map directly to the flattened array in memory., and emit code like `dispatch2()`. Instead it emits more complicated, redundant code:

```
dispatch:
mov eax, edi
mov ecx, edi
shr ecx, 3
and eax, 7
shl rcx, 6
add rcx, qword ptr [rip + fns@GOTPCREL]
mov edi, esi
jmp qword ptr [rcx + 8*rax]

dispatch2:
mov eax, edi
mov rcx, qword ptr [rip + fns@GOTPCREL]
mov edi, esi
jmp qword ptr [rcx + 8*rax]
```

GCC and MSVC both generate the simpler code in each case.

Contributor guide

Open the contributing guide

Research direction

Start with the C reproducer in the issue and compare the generated assembly for dispatch() and dispatch2() using the linked Compiler Explorer example. Trace the relevant optimization behavior in Clang, then add or update a regression test showing that the two-dimensional access can be flattened without redundant index calculations.

Written by the indexing model from the issue text.

Assessment

Tech stack
c
Domain
compilers
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.