llvm / llvm/llvm-project

Missed optimization for switches using getelementptr

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

Description

This example is a simplified version from a case we encountered:
https://godbolt.org/z/af5oWYMzj

We can optimize the switch away by replacing the getelementptrs with the `merge.gep`s in the merge blocks (since https://github.com/llvm/llvm-project/pull/156477 and https://github.com/llvm/llvm-project/pull/158242):
https://godbolt.org/z/MoMnbhM5d

InstCombinePHI can do just that with `foldPHIArgGEPIntoPHI` https://github.com/llvm/llvm-project/blob/06c8ee61ab80305be88380e6aa2f1b2fe32f859d/llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp#L535.
However, in this case the transform fails because:

1. There are multiple users
2. The offsets are constant

Both cases prevent the transform due to pessimization. Aborting on constant indices ensures phis into structs do not introduce invalid getelementptrs. Maybe we could relax this restriction on non-struct phis but the multiple users restriction still blocks optimizing our case.

What is the best way to optimize this case? Can we extend `foldPHIArgGEPIntoPHi` in InstCombine or should we implement this in SimplifyCFG?

*Edit 12-01:* Further simplified example to have the same switch condition in both switches.

Contributor guide

Open the contributing guide

Research direction

Reproduce the missed optimization using the two Compiler Explorer examples linked in the issue, then read llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp at foldPHIArgGEPIntoPHI. Compare whether extending InstCombinePHI or handling the case in SimplifyCFG fits the existing restrictions; done means the switch pattern is optimized without invalid GEPs.

Written by the indexing model from the issue text.

Assessment

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.