Overview: How the CPU records producer-consumer register relationships as instructions enter the pipeline, why backward tracking avoids broadcast overhead, and how proactive PC tagging speeds up critical loads.
| Data Structure / Component | Where It Lives | What It Stores | Systems Benefit |
|---|---|---|---|
last_writer[] |
inc/ooo_cpu.h |
Array mapping each register to the instruction ID that last wrote it. | Enables instant $O(1)$ lookup of producer instructions without scanning previous code. |
pred_instr_ids[] |
inc/instruction.h |
Array inside each instruction storing up to 2 predecessor instruction IDs. | Records backward dependency links for later slice construction. |
recent_instrs |
inc/ooo_cpu.h |
Hash map linking instruction IDs to active ROB pointers. | Allows fast BFS traversal across in-flight instructions during slice extraction. |
critical_pc_table |
inc/ooo_cpu.h |
Hash set storing Program Counters of known delinquent loads. | Enables proactive tagging: marks instructions critical immediately at dispatch. |
"To prioritize the instructions that feed a slow load, the processor has to know which earlier instructions produced its input registers.
I implemented this dependency tracking in the dispatch stage (dispatch_instruction()). Dispatch is the ideal place because this is where physical registers are renamed, unique instruction IDs are assigned, and register dependencies are fully known.
Instead of building a complex forward dependency graph—which would require broadcasting updates to all future instructions—I used backward dependency tracking. I maintain a simple table called last_writer[]. Whenever an instruction writes to a destination register, we record that instruction's unique ID in the table.
When a new instruction passes through dispatch, it checks last_writer[] for its source registers. It records up to two predecessor IDs directly into its own metadata. This creates a lightweight chain of backward pointers using only $O(1)$ constant-time lookups per instruction.
At the same time, we check our critical_pc_table. If this instruction's Program Counter was identified as critical during a previous execution, we proactively mark it as critical right away. This means we don't have to wait for the load to become slow again—the processor prioritizes it immediately."
There are two theoretical ways to track instruction dependencies in hardware:
Forward Tracking (Expensive):
Instruction A writes R1 ──► Must broadcast to ALL future instructions: "Listen to me!"
Requires complex listener queues or associative search.
Backward Tracking in CRISP (Lightweight & O(1)):
Instruction B reads R1 ──► Looks up last_writer[R1] in 1 step!
Finds Instruction A immediately. No broadcast needed.
last_writer[] Builds the ChainConsider a simple pointer-chasing sequence where a load computes an offset from an earlier base pointer:
Instruction 101: ADD R1, R2 -> R3 (last_writer[R3] = 101)
Instruction 102: MOV R4, 16 -> R5 (last_writer[R5] = 102)
Instruction 103: LOAD [R3 + R5] -> R7
│
├── Reads source R3: last_writer[R3] == 101 -> pred_instr_ids[0] = 101
└── Reads source R5: last_writer[R5] == 102 -> pred_instr_ids[1] = 102
With just two array lookups, Instruction 103 now has direct backward pointers to the exact instructions that calculated its memory address.
critical_pc_tableThe first time a delinquent load executes, it is discovered reactively after taking 200+ cycles to access DRAM. But once that load's Program Counter (PC) is known, repeating the same delay in the future is wasteful.
At dispatch, every incoming instruction checks:
if (critical_pc_table.count(instr.ip)) {
instr.is_critical = true;
}
This allows the processor to prioritize recurring delinquent loads and their slices before they experience a cache miss, cutting latency proactively.
Answer: "On modern architectures like x86 and ARM, virtually all ALU and memory instructions use at most two source registers (for example, base + index in address calculation: [R1 + R2*4]). Capping predecessor storage at 2 covers nearly 100% of practical address-generation instructions while keeping per-instruction metadata fixed in size and avoiding dynamic memory allocation."
Answer: "Tracking memory dependencies at runtime requires dynamic store-to-load forwarding tracking in the Load-Store Queue (LSQ). Stores often compute their addresses late, which can introduce false dependencies or ambiguity. Register dependencies, by contrast, are 100% deterministic at dispatch after register renaming. Register tracking captured the dominant address-computation chains in our workloads with minimal overhead."
recent_instrs?Answer: "Instructions are removed from recent_instrs strictly at retirement. They must remain in the map while in-flight so that any backward BFS can reach them. Once an instruction retires from the ROB, its execution has finished and its resources are freed, so its pointer in recent_instrs is erased to prevent dangling references."