Scope-Dependent Branch Behavior: An Overlooked Dimension in Branch Analysis

Read full text Summarise with VIRAT
Authors: Mark Newton
Cited by: 0

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

Abstract

Branch behavior (the tendency to be taken or not taken, and the degree to which that tendency persists across executions) is widely treated as a property of individual branches independent of their structural context. We show that this view is incomplete. Branch outcome distributions vary systematically with lexical scope depth: branches at greater nesting depth behave differently, in a statistically significant and predictable way, from branches at shallow nesting. We introduce ScopeProf, an LLVM-based instrumentation framework that records branch outcomes stratified by scope depth (decomposed into loop nesting depth and conditional nesting depth). Applied to the MiBench benchmark suite (1,087 source files, 11,442 branch sites, 9.1M dynamic executions), ScopeProf reveals that scope depth accounts for 39.4% of branch outcome entropy, independent of branch history (I(D;O) = 0.366 bits against H(O) = 0.929 bits). We formalize this as a mutual-information bound, prove scope depth is conditionally independent of branch history, and show how scope-stratified !prof metadata injection improves static prediction accuracy from 71.2% to 84.7%, closing 67% of the gap to full PGO, with 1.019× geomean execution-time improvement across five MiBench benchmarks, requiring no profiling run.

Fields of Study & Subjects

Parallel Computing and Optimization Techniques Logic programming and type systems Embedded Systems Design Techniques

Publication details

Journal / source
Zenodo (CERN European Organization for Nuclear Research)
Publication date
25 March 2026
Language
EN
Document type
Preprint