Path Sensitive Code Optimizations
Optimization Approaches
Optimizations
Path Sensitive Optimizations
Analysis
Why Demand Driven Analysis ?
Why Path Profiles?
Transformations
Conditional Branch Elimination
Data Flow Facts
Demand Driven Analysis
Restructuring Transformation
Interprocedural Branch Elimination
% Conditionals with Redundancy: Dynamic Count
Code Growth vs Inter. Branch Elimination
Safe Code Motion based Partial Redundancy Elimination (PRE)
Speculative PRE
Effect of Speculation on Paths
Enabling Speculation
Controlling Analysis Costs
Restructuring PRE
Code Growth
Partial Redundancy Removed: % of Dynamically Executed Expressions
Value Prediction - Last value predictor
Safe Code Motion based Partial Deadcode Elimination (PDE)
Predication and PDE
Restructuring PDE
The Transformation Steps
Load Speculation
Performance of Simple Schemes
Store-set Memory Disambiguator (Chrysos & Emer - 1998)
Scalability of Store Set
False Dependences - Loss of Parallelism
False Memory Violations - Inefficient Use of Table Space
Value based Store Set
Scalability of Memory Disambiguation
Value Checks - 124.m88ksim
Occasional Dependence - 110.applu
Other Solutions
Summary of Results
Email: gupta@cs.arizona.edu
Home Page: http://www.cs.arizona.edu/people/gupta