llvm/llvm-project

Missed Optimization: max(max(x, c1) << c2, c3) —> max(x << c2, c3) when c3 >= c1 * 2 ^ c2

Open

#139.786 aperta il 13 mag 2025

Vedi su GitHub
 (11 commenti) (0 reazioni) (2 assegnatari)C++ (10.782 fork)batch import
good first issuellvm:instcombinemissed-optimization

Metriche repository

Star
 (26.378 star)
Metriche merge PR
 (Merge medio 1g 2h) (1000 PR mergiate in 30 g)

Descrizione

define i8 @src(i8 %arg0) {
  %1 = call i8 @llvm.umax.i8(i8 %arg0, i8 1)
  %2 = shl nuw i8 %1, 1
  %3 = call i8 @llvm.umax.i8(i8 %2, i8 16)
  %4 = icmp sgt i8 %1, -1
  %5 = select i1 %4, i8 %3, i8 -1
  ret i8 %3
}

define i8 @tgt(i8 %arg0) {
  %1 = shl nuw i8 %arg0, 1
  %2 = call i8 @llvm.umax.i8(i8 %1, i8 16)
  %3 = icmp sgt i8 %2, -1
  %4 = select i1 %3, i8 %2, i8 -1
  ret i8 %2
}

Alive2: https://alive2.llvm.org/ce/z/on2tJE

Found this pattern at: https://github.com/dtcxzyw/llvm-opt-benchmark/blob/94dab89f901fdfae3e47dc6696c06d591fdd7993/bench/openssl/optimized/packet.ll#L1086-L1094

I think this transformation can be generalized to operations other than shift and also to min().

Guida contributor

Direzione di ricerca
Studia i pass di combinazione delle istruzioni di LLVM, in particolare InstCombine e DAGCombine, per comprendere come sono implementate le ottimizzazioni esistenti di max/min e shift. Cerca modelli nel codebase che gestiscono semplificazioni simili e traccia la logica nella dimostrazione di Alive2 per capire la condizione. Considera la generalizzazione ad altre operazioni come min e altri shift.
Tech stack
cpp
Dominio
backend
Tipo issue
Performance
DifficoltàQuanto dovrebbe essere impegnativa per un nuovo contributor.
4
Tempo stimatoTempo stimato per completare e verificare uno scope piccolo.
1-2 giorni
Stato attivitàQuanto è probabile che la issue sia ancora attiva e reviewable.
Attiva
ChiarezzaQuanto chiaramente la issue descrive problema, scope e risultato atteso.
Chiara
Prerequisiti
C++LLVM internalscompiler optimization
Adatta ai principiantiQuanto la issue è adatta a contributor alla prima esperienza.
30