# Trace Case Study: QuickSort on x86-64  
**Benchmark:** `cBench/qsort`  
**Platform:** Intel Core i9-11900K (`x86-64`)  

---

## 1. Why this case is representative

This trace documents a complete optimization lifecycle for **QuickSort** on x86-64. It is a useful representative case because it shows all key stages of the AutoPass workflow:

- **Analysis Agent** extracts semantic and compiler-side evidence from LLVM IR and optimization remarks.
- **Reasoning Agent** synthesizes a pass-pipeline edit with explicit parameter changes.
- **Evaluation Agent** measures the actual runtime effect and diagnoses the causes of regression or improvement.
- **Later rounds** use that diagnosis to revise the optimization strategy.

In this example, AutoPass first makes an aggressive but explainable decision, incurs a small regression in Round 1, and then recovers to a final **1.028× speedup** by Round 2. This trace therefore demonstrates both **interpretability** and **self-correction**. 

---

## 2. Baseline diagnosis from the Analysis Agent

The Analysis Agent is responsible for bridging the gap between raw LLVM IR and optimization reasoning. It combines:

- a natural-language summary of the IR,
- static structural features,
- and compiler optimization remarks.

### 2.1 Natural-language IR summary

For QuickSort, the Analysis Agent summarizes the program as a sorting workload with important optimization opportunities in:

- **small sorting cases**,
- **quicksort partitioning**,
- and **pointer-heavy computation**.

An excerpt of the generated summary is:

> *“This LLVM IR implements a 3D vector sorting program... Key bottlenecks include the distance calculation loop using `pow` and `sqrt`, and quicksort partitioning with extensive pointer arithmetic. Optimization opportunities include loop unrolling for the small sorting cases...”* 

### 2.2 Static feature evidence

The tool-augmented feature extraction reveals why the system focuses on `qsortx`:

- `qsortx` has **198 basic blocks**
- `qsortx` contains **16 loops**
- `qsortx` contains **12 calls**

This makes it the most structurally complex and optimization-sensitive part of the benchmark. The compiler remarks further show repeated missed vectorization opportunities, including:

- **13 `slp-vectorizer` failures**
- marked as **`NotBeneficial`**

At the same time, some loop vectorization already succeeds, which means the problem is not simply “vectorize more,” but to decide **where** and **how aggressively** to apply loop and vector passes. \
### 2.3 Initial optimization hypothesis

From this evidence, AutoPass infers that:

- the benchmark is loop-intensive,
- there may be benefit from stronger unrolling,
- and there may be room to make SLP vectorization more permissive.

This diagnosis directly informs the first-round reasoning step.

---

## 3. Round 1 — Aggressive optimization and regression

###  3.1 Reasoning Agent decision

In Round 1, the Reasoning Agent generates an aggressive policy:

- `unroll_count = 12`
- `unroll_threshold = 800`
- `inline_threshold = 600`
- `slp_threshold = -5`
- `mcpu = skylake`
- `mtriple = x86_64-unknown-linux-gnu`

Its rationale is to prioritize:

- loop and memory optimizations,
- stronger unrolling for the sorting kernel,
- and more aggressive SLP vectorization in response to the observed missed opportunities. 

This decision is important because it is **not arbitrary**. The pass changes are clearly tied to:

- the loop-heavy structure of `qsortx`,
- the `NotBeneficial` SLP remarks,
- and the target platform metadata.

###  3.2 Quantitative outcome

However, the measured outcome shows that the first-round strategy is **too aggressive**.

| Metric | Baseline (-O3) | Round 1 |
|---|---:|---:|
| Execution Time | 1.5355 s | 1.5474 s |
| Speedup | 1.000× | 0.992× |
| Cycles | 7,826 M | 7,886 M |
| Instructions | 28,691 M | 28,032 M |
| Micro-operations | 30,213 M | 29,412 M |

Key observations:

- **Execution time regresses by 0.77%**
- **Instruction count decreases by 2.3%**
- **Micro-operations decrease by 2.7%**

This is a useful failure mode:

> Fewer instructions do not necessarily imply faster execution.

The detailed evaluation report explains why. Round 1 causes:

- a **176.4% binary size explosion**
- a **133.1% increase in L1 cache misses**
- a **15.45% increase in memory-related stall cycles**
- and a **3.04% IPC decrease**

So the first-round policy succeeds in reducing dynamic work, but fails to preserve front-end and cache efficiency. The likely mechanism is that aggressive unrolling and inlining increase code size enough to hurt instruction locality on the Rocket Lake / x86-64 front end. 

---

## 4. Evaluation Agent diagnosis after Round 1

The Evaluation Agent does more than check whether the candidate is faster. It produces a diagnosis and a corrective summary.

### 4.1 Main diagnosis

The Evaluation Agent identifies three major causes of the regression:

1. **Code bloat**
   - binary size grows from **20.9 KB** to **57.8 KB**
2. **Instruction-cache pressure**
   - L1 misses rise sharply
3. **Over-aggressive loop expansion**
   - the combination of unrolling and inlining is too strong for this target

The evaluation report explicitly states that the aggressive unroll and inline settings are the main reason performance got worse. 

### 4.2 Feedback passed to the next round

The feedback to the Reasoning Agent is highly actionable:

- **lower `unroll-count`**
- **lower `unroll-threshold`**
- **reduce `inline-threshold`**
- make vectorization more conservative

This shows the central value of the evaluation loop:

> the system does not simply reject bad results; it converts the failure into structured guidance for the next optimization round.

---

## 5. Round 2 — Recovery through conservative re-tuning

###  5.1 Reasoning update

After the Round-1 diagnosis, the Reasoning Agent pivots to a more balanced strategy.

Main changes:

- `unroll-count` reduced from **8** to **2**
- `unroll-threshold` reduced to **250**
- `slp-threshold` raised from **-5** to **-1**

The updated reasoning explicitly aims to control code bloat while retaining the useful loop-level benefits of the first-round pipeline. 

###  5.2 Quantitative recovery

Round 2 successfully reverses the regression and surpasses the baseline.

| Metric | Round 1 | Round 2 |
|---|---:|---:|
| Execution Time | 1.5474 s | **1.4941 s** |
| Speedup | 0.992× | **1.028×** |
| Cycles | 7,886 M | **7,615 M** |
| Instructions | 28,032 M | **27,420 M** |
| Micro-operations | 29,412 M | **28,519 M** |

Compared with Round 1:

- cycles fall by about **3.4%**
- instructions decrease further
- micro-operations decrease further
- the runtime improves from a regression to a **2.8% speedup**

This is the key proof that the feedback loop contributes beyond one-shot optimization. Round 1 alone would leave the benchmark slower than `-O3`; iterative feedback enables the system to recover and outperform the baseline. 

---

## 6. Round 3 — Fine tuning and convergence

###  6.1 Reasoning update

The third round continues the correction process with a more conservative policy:

- `unroll-count = 4`
- `slp-threshold = 8`

The intent is to keep the useful parts of the earlier changes while further reducing the overhead of failed vectorization checks and unnecessary structural expansion. 

###  6.2 Quantitative outcome

| Metric | Round 2 | Round 3 |
|---|---:|---:|
| Execution Time | **1.4941 s** | 1.5012 s |
| Speedup | **1.028×** | 1.023× |
| Instructions | 27,420 M | 27,815 M |
| Micro-operations | 28,519 M | 29,020 M |

Round 3 remains better than the baseline, but it is slightly worse than Round 2. This indicates that the search has effectively **converged by Round 2**, and that the extra fine-tuning in Round 3 provides little additional benefit. The trace therefore supports the broader paper conclusion that most of the useful improvement appears within the first few refinement rounds. 
---

## 7. Full optimization trajectory

| Metric | Baseline (-O3) | Round 1 (Aggressive) | Round 2 (Recovery) | Round 3 (Refinement) |
|---|---:|---:|---:|---:|
| **Execution Time** | 1.5355 s | 1.5474 s (+0.8%) | **1.4941 s (-2.7%)** | 1.5012 s (-2.2%) |
| **Speedup** | 1.000× | 0.992× | **1.028×** | 1.023× |
| **Cycles** | 7,826 M | 7,886 M | 7,615 M | 7,651 M |
| **Instructions** | 28,691 M | 28,032 M | 27,420 M | 27,815 M |
| **Micro-operations** | 30,213 M | 29,412 M | 28,519 M | 29,020 M |
| **Unroll Count** | Default | 8 | **2** | 2 |
| **SLP Threshold** | Default | -5 | **-1** | -4 |

The trajectory shows a clear pattern:

1. **Round 1** reduces dynamic work but harms performance due to code growth and cache pressure.
2. **Round 2** corrects the harmful aggressiveness and delivers the best runtime.
3. **Round 3** remains better than baseline but confirms diminishing returns.

---

## 8. What this trace teaches about AutoPass

This case study highlights four important properties of AutoPass.

### 8.1 It makes evidence-based decisions
The first-round policy can be traced directly to:

- loop complexity in `qsortx`
- missed SLP opportunities
- target-specific platform data

### 8.2 It is explainable
When the first-round decision fails, the Evaluation Agent provides a concrete explanation:

- too much unrolling
- too much inlining
- code-size blowup
- increased memory-related stalls

### 8.3 It is self-correcting
Round 2 demonstrates that the agent loop is constructive, not merely evaluative. The feedback is used to reduce aggressiveness and recover performance.

### 8.4 It converges quickly
The best result is already reached by Round 2, and Round 3 offers little extra gain. This supports the design choice of a small iterative budget.

---

## 9. Key takeaway

This QuickSort trace shows that AutoPass does not optimize by blind search or text-only intuition. Instead, it links:

- **compiler evidence** → to decide what to change,
- **runtime measurements** → to judge whether the change worked,
- and **feedback summaries** → to revise later rounds.

The result is an optimization process that is both **interpretable** and **correctable**. Even when the first policy is too aggressive, the later rounds can use concrete compiler and runtime evidence to recover a stronger pipeline. That is the central mechanism behind AutoPass.