Saat kompiler membuat Anda terkejut

• Contoh pengamatan perbedaan optimisasi GCC dan Clang saat mengompilasi fungsi penjumlahan bilangan bulat sederhana
• GCC melakukan optimisasi loop dalam bentuk x*2 + 1 untuk menjumlahkan dua angka sekaligus di dalam loop
• Clang menghapus loop sepenuhnya dan menggantinya dengan rumus bentuk tertutup v(v - 1)/2
• Transformasi ini mengubah kode dari O(n) menjadi O(1), dengan penyederhanaan matematis yang dilakukan secara otomatis
• Bahkan bagi penulis yang sudah lebih dari 20 tahun bekerja dengan kompiler, ini menjadi contoh yang menunjukkan tingkat optimisasi cerdas dari kompiler

---

Optimisasi loop di GCC

• Saat menulis fungsi penjumlahan bilangan bulat sederhana, GCC menghasilkan kode penjumlahan efisien berbasis loop
  • Di dalam loop, digunakan instruksi lea edx, [rdx+1+rax*2] untuk menjumlahkan dua angka sekaligus
  • Ini adalah bentuk transformasi operasi penjumlahan x dan x+1 menjadi x*2 + 1
• Jika level optimisasi dinaikkan ke -O3, loop diproses lebih cepat melalui penjumlahan paralel (vectorization)
• Pendekatan seperti ini merupakan bentuk optimisasi tradisional yang mempertahankan loop sambil memaksimalkan efisiensi operasi

Optimisasi matematis di Clang

• Saat kode yang sama dikompilasi dengan Clang, loop menghilang sepenuhnya
  • Setelah memeriksa apakah nilai input positif, Clang melakukan perhitungan melalui rangkaian instruksi lea, imul, dan shr
  • Hasilnya ditransformasikan menjadi (v² - v)/2, yaitu rumus bentuk tertutup untuk jumlah bilangan bulat
• Transformasi ini menghapus loop dan menggantinya dengan perhitungan waktu konstan (O(1))
• Penulis menggambarkan hasil ini sebagai “menemukan sendiri solusi matematis untuk penjumlahan bilangan bulat”

Proses penguraian rumus

• Jika kode assembly yang dihasilkan Clang ditelusuri balik secara matematis, transformasi berikut terjadi
  • v + ((v - 1)(v - 2) / 2) - 1
  • Jika dikembangkan dan disederhanakan, hasilnya menjadi (v² - v)/2
• Pada akhirnya bentuknya menjadi v(v - 1)/2, yang cocok dengan rumus jumlah dari 1 sampai v
• Proses ini ditunjukkan sebagai contoh kompiler mengenali pola matematis dan mengoptimalkannya

Perilaku cerdas kompiler

• Alasan Clang menggunakan rangkaian instruksi spesifik ini dijelaskan berkaitan dengan pencegahan overflow dan cara pelacakan induction variable
• Penyebab pasti dari cara kerja internalnya tidak sepenuhnya jelas, tetapi disebut sebagai hasil dari kombinasi logika optimisasi internal Clang
• Penulis menyebut hasil ini sebagai “pengalaman yang merendahkan hati dan memberi inspirasi”

Penutup dan konteks seri

• Artikel ini adalah tulisan ke-24 dalam seri ‘Advent of Compiler Optimisations 2025’
• Artikel ini mengeksplorasi bagaimana kompiler mencapai penyederhanaan matematis dan peningkatan performa melalui transformasi kode
• Penulis menekankan bahwa “kompiler masih terus mengejutkan saya”, menyoroti rasa takjub teknis yang tetap ada meski sudah berpengalaman lama

[GN⁺]

Komentar Hacker News

• Kode yang mengimplementasikan fitur ini ada di ScalarEvolution.cpp dan IndVarSimplify.cpp

  • Mengejutkan sekaligus sedikit bikin waswas bahwa satu file berisi hampir 16.000 baris kode

• Optimisasi jenis ini benar-benar menarik
  Optimisasi compiler secara besar terbagi dua — analisis aliran data dan pengenalan pola serta penggantian
  Yang pertama efektif untuk sebagian besar program, sedangkan yang kedua adalah pekerjaan menumpuk pola dengan hasil yang makin lama makin kecil
  Contoh yang ditautkan ini cerdas dan menyenangkan, tetapi dalam praktiknya tidak punya nilai besar. Selama 45 tahun saya belum pernah menulis loop seperti itu
  Tentu saja, substitusi pola seperti ini tetap penting karena bisa dihasilkan otomatis dari kode tingkat tinggi
  Jujur saja, mungkin saya hanya sedikit menggerutu karena optimizer saya tidak bisa melakukan optimisasi seperti ini

  • Sebenarnya mungkin lebih bernilai daripada yang terlihat. SCEV (Scalar Evolution) di LLVM terutama dipakai untuk analisis, dan juga memungkinkan optimisasi lain di luar loop matematis
  • Tidak jelas optimisasi apa yang dilakukan. Dulu saat membuat compiler untuk kebutuhan khusus, saya ingat pernah terkejut melihat compiler menangani sesuatu dengan lebih cerdas daripada optimisasi yang saya tulis sendiri

• Ini adalah fitur yang disebut Scalar Evolution (SCEV), dan implementasinya di LLVM cukup kompleks

• Contoh optimisasi serupa ada di artikel “Do not optimize away”

  • Penjelasan di awal artikel itu agak keliru. Kodenya menjumlahkan dari 0 sampai N tetapi tidak termasuk N, jadi yang benar sebenarnya N(N-1)/2. Secara matematis, jumlah 1 sampai N adalah N(N+1)/2, jadi untuk mengecualikan batas atas, N harus diganti dengan (N-1)
  • Saya rasa compiler mungkin masih bisa mengoptimalkan ini. Sepertinya bisa dengan membuat versi constant folding dan versi non-konstan lalu bercabang saat runtime

• Hal yang benar-benar keren dari optimisasi ini adalah sifatnya yang generik
  Yang mengesankan bukan sekadar mengenali pola “jumlah deret bilangan bulat hingga”, tetapi bahwa ini diterapkan secara umum

• Sepertinya compiler bisa menambahkan lebih banyak closed form. Saya penasaran apakah itu sepadan
  Ada konsep terkait yaitu Wilf–Zeilberger pair

• Sekali lagi saya terkejut melihat hasil GCC lebih lambat daripada Clang
  Meski GCC unggul 20 tahun lebih dulu, masih ada kasus di mana Clang menghasilkan kode yang lebih cepat
  Dulu saat mengekstrak bit, Clang selesai hanya dengan dua shift, sedangkan GCC sampai tiga kali

  • Ada kesenjangan generasi dalam teknologi compiler antara GCC dan LLVM/Clang. GCC tetap proyek yang luar biasa, tetapi saya dengar secara struktural lebih sulit menerapkan teknik optimisasi modern di sana
  • Performa nyata keduanya mirip. Mereka punya pass optimisasi yang berbeda, jadi hasilnya berubah tergantung situasi
  • Pada awalnya GCC punya desain idealistis yang berpusat pada lisensi, sehingga kurang mudah diperluas. Sekarang sudah jauh lebih longgar, tetapi code generator-nya masih kompleks. Sebaliknya, Clang punya struktur yang lebih sederhana sehingga implementasi optimisasi lebih mudah. Secara pribadi saya juga merasa keluaran MSVC atau ICC cukup bagus
  • Apakah ini kebetulan kode terkait bitfield? GCC memang sangat lemah dalam optimisasi bagian itu

• Saya penasaran apakah pernah ada yang mencoba optimisasi yang mengganti masalah pewarnaan graf (graph coloring) dengan konstanta

  • Pewarnaan graf adalah masalah NP-hard, jadi sulit diubah menjadi O(1). Untuk graf planar memang ada teorema empat warna, tetapi jawabannya tidak selalu sama. Saya cuma ingin bicara soal teori graf

• Ini contoh yang mengaburkan batas antara implementasi dan spesifikasi
  Kita merasa sedang menulis implementasi, tetapi sebenarnya kita menulis proksi dari spesifikasi
  Artinya, compiler menciptakan ilusi mesin imperatif

• Awalnya saya terkejut Matt tidak mengetahui perilaku seperti ini
  Saat kuliah saya juga pernah bermain-main dengan LLVM IR dan kaget melihat rekursi disederhanakan menjadi perkalian
  Jika Matt tidak tahu, mungkin artinya optimisasi ini hanya diterapkan pada kasus-kasus sederhana yang tidak ia tangani

  • Sebenarnya dia sudah tahu. Dalam presentasi tahun 2017 dia sendiri menyebut contoh yang sama
    Tautan video YouTube