FE-Logo
  • Home
  • Study Material
  • Non-Deterministic Finite Automation
    • Introduction to Compiler
    • The Structure of a Compiler
    • Intermediate Code Generation
    • Building a Compiler
    • Applications of Compiler
    • Optimizations for Computer Architectures
    • Design of New Computer Architectures
    • Program Translations
    • Software Productivity Tools
    • Programming Language Basics
    • Minimisation of DFAs
    • Explicit Access Control
    • Parameter Passing Mechanisms
    • Introduction to Lexical Analysis
    • Regular expressions
    • Short hands
    • Nondeterministic finite automata
    • Converting a regular expression to an NFA
    • Deterministic finite automata
    • Converting an NFA to a DFA
    • The subset construction
    • Dead states
    • Lexers and lexer generators
    • Splitting the input stream
    • Lexical errors
    • Properties of regular languages
    • Limits to expressive power
    • The Role of the Lexical Analyzer
    • Input Buffering
    • Specification of Tokens
    • Operations on Languages
    • Regular Definitions and Extensions
    • Recognition of Tokens
    • The Lexical-Analyzer Generator Lex
    • Finite Automata
    • Construction of an NFA from a Regular Expression
    • Efficiency of String-Processing Algorithms
    • The Structure of the Generated Analyzer
    • Optimization of DFA-Based Pattern Matchers

  • Basic Parsing Techniques
    • Introduction to Syntax analysis
    • Context-free grammars
    • Writing context free grammars
    • Derivation
    • Syntax trees and ambiguity
    • Operator precedence
    • Writing ambiguous expression grammars
    • Other sources of ambiguity
    • Syntax analysis and Predictive parsing
    • Nullable and FIRST
    • Predictive parsing revisited
    • FOLLOW
    • LL(1) parsing
    • Methods for rewriting grammars for LL(1) parsing
    • SLR parsing
    • Constructions of SLR parse tables
    • Conflicts in SLR parse-tables
    • Using precedence rules in LR parse tables
    • Using LR-parser generators
    • Properties of context-free languages
    • Introduction to Syntax-Directed Translator
    • Evaluating an SDD at the Nodes of a Parse Tree
    • Evaluation Orders for SDD\'s
    • Ordering the Evaluation of Attributes
    • A larger example of calculating FIRST and FOLLOW
    • Syntax Definition
    • Associativity of Operators
    • Parse Trees
    • Ambiguity
    • Syntax-Directed Translation
    • Synthesized Attributes
    • Tree Traversals
    • Parsing
    • Predictive Parsing
    • Use e-Productions
    • Translator for Simple Expressions
    • Semantic Rules with Controlled Side Effects
    • Applications of Syntax-Directed Translation
    • The Structure of a Type of syntax
    • Switch-Statements
    • Syntax-Directed Translation Schemes
    • Postfix Translation Schemes
    • SDT\'s With Actions Inside Productions
    • Eliminating Left Recursion from SDT\'s
    • SDT\'s for L-Attributed Definitions
    • Implementing L-Attributed SDD\'s
    • On-The-Fly Code Generation
    • L-Attributed SDD\'s and LL Parsing
    • Bottom-Up Parsing of L-Attributed SDD\'s

  • Syntax-directed Translation
    • Register Allocation and Assignment
    • Semantic Analysis
    • Introduction to Intermediate Code Generation
    • Variants of Syntax Trees
    • Variants of Syntax Trees
    • The Value-Number Method for Constructing DAG\'s
    • Three-Address Code
    • Quadruples
    • Triples
    • Static Single-Assignment Form
    • Types and Declarations
    • Type Equivalence
    • Sequences of Declarations
    • Translation of Expressions
    • Incremental Translation
    • Addressing Array Elements
    • Translation of Array References
    • Type Checking
    • Type Conversions
    • Overloading of Functions and Operators
    • Type Inference and Polymorphic Functions
    • Algorithm for Unification
    • Control Flow
    • Flow-of-Control Statements
    • Control-Flow Translation of Boolean Expressions
    • Boolean Values and Jumping Code
    • Back patching
    • Backpatching for Boolean Expressions
    • Flow-of-Control Statements
    • Break-, Continue-, and Goto-Statements
    • Introduction to Run-Time Environments
    • Stack Allocation of Space
    • Activation Records
    • Calling Sequences
    • Variable-Length Data on the Stack
    • Access to Nonlocal Data on the Stack
    • Displays
    • Heap Management
    • Locality in Programs
    • Reducing Fragmentation
    • Managing and Coalescing Free Space
    • Manual Deallocation Requests
    • Reachability
    • Introduction to Garbage Collection
    • Reference Counting Garbage Collectors
    • Introduction to Trace-Based Collection
    • Basic Abstraction
    • Optimizing Mark-and-Sweep
    • Mark-and-Compact Garbage Collectors
    • Copying collectors
    • Short-Pause Garbage Collection
    • Incremental Reachability Analysis
    • Partial-Collection Basics
    • The Train Algorithm
    • Parallel and Concurrent Garbage Collection
    • Partial Object Relocation
    • Introduction Code Generation
    • Issues in the Design of a Code Generator
    • Instruction Selection
    • Register Allocation
    • The Target Language
    • Addresses in the Target Code
    • Stack Allocation
    • Run-Time Addresses for Names
    • Basic Blocks and Flow Graphs
    • Basic Blocks
    • Next-Use Information
    • Representation of Flow Graphs
    • Optimization of Basic Blocks
    • Dead Code Elimination
    • Representation of Array References
    • Pointer Assignments and Procedure Calls
    • A Simple Code Generator
    • The Code-Generation Algorithm
    • Design of the Function getReg
    • Peephole Optimization
    • Algebraic Simplification and Reduction in Strength
    • Register Assignment for Outer Loops
    • Instruction Selection by Tree Rewriting
    • Code Generation by Tiling an Input Tree
    • Pattern Matching by Parsing
    • General Tree Matching
    • Optimal Code Generation for Expressions
    • Evaluating Expressions with an Insufficient Supply of Registers
    • Dynamic Programming Code-Generation

  • Data Flow Analysis
    • The Lazy-Code-Motion Algorithm
    • Introduction to Machine-Independent Optimizations
    • The Dynamic Programming Algorithm
    • The Principal Sources of Optimization
    • Semantics-Preserving Transformations
    • Copy Propagation
    • Induction Variables and Reduction in Strength
    • Introduction to Data-Flow Analysis
    • The Data-Flow Analysis Schema
    • Reaching Definitions
    • Live-Variable Analysis
    • Available Expressions
    • Foundations of Data-Flow Analysis
    • Transfer Functions
    • The Iterative Algorithm for General Frameworks
    • Meaning of a Data-Flow Solution
    • Constant Propagation
    • Transfer Functions for the Constant-Propagation Framework
    • Partial-Redundancy Elimination
    • The Lazy-Code-Motion Problem
    • Loops in Flow Graphs
    • Depth-First Ordering
    • Back Edges and Reducibility
    • Natural Loops
    • Speed of Convergence of Iterative Data-Flow Algorithms
    • Region-Based Analysis
    • Necessary Assumptions About Transfer Functions
    • An Algorithm for Region-Based Analysis
    • Handling Non-reducible Flow Graphs
    • Symbolic Analysis
    • Data-Flow Problem Formulation
    • Region-Based Symbolic Analysis

  • Code Generation
    • Introduction to Software Pipelining of Loops
    • Matrix Multiply: An In-Depth Example
    • Software Pipelining of Loops
    • Introduction Instruction-Level Parallelism
    • Multiple Instruction Issue
    • A Basic Machine Model
    • Code-Scheduling Constraints
    • Finding Dependences Among Memory Accesses
    • Phase Ordering Between Register Allocation and Code Scheduling
    • Speculative Execution Support
    • Basic-Block Scheduling
    • List Scheduling of Basic Blocks
    • Global Code Scheduling
    • Upward Code Motion
    • Updating Data Dependences
    • Advanced Code Motion Techniques
    • Software Pipelining
    • Register Allocation and Code Generation
    • A Software-Pipelining Algorithm
    • Scheduling Cyclic Dependence Graphs
    • Improvements to the Pipelining Algorithms
    • Conditional Statements and Hardware Support for Software Pipelining
    • Basic Concepts of Parallelism and Locality
    • Parallelism in Applications
    • Loop-Level Parallelism
    • Introduction to Affine Transform Theory
    • Optimizations
    • Iteration Spaces
    • Affine Array Indexes
    • Controlling the Order of Execution
    • Changing Axes
    • Intermediate Code for Procedures
    • Data Reuse
    • Self Reuse
    • Self-Spatial Reuse
    • Array Data-Dependence Analysis
    • Integer Linear Programming
    • Heuristics for Solving Integer Linear Programs
    • Solving General Integer Linear Programs
    • Finding Synchronization-Free Parallelism
    • Affine Space Partitions
    • Space-Partition Constraints
    • Solving Space-Partition Constraints
    • A Simple Code-Generation Algorithm
    • Eliminating Empty Iterations
    • Synchronization Between Parallel Loops
    • The Parallelization Algorithm and Hierarchical Time
    • Pipelining
    • Solving Time-Partition Constraints by Farkas' Lemma
    • Code Transformations
    • Parallelism With Minimum Synchronization
    • Locality Optimizations
    • Partition Interleaving
    • Putting it All Together
    • Uses of Affine Transforms
    • Interprocedural Analysis
    • Context Sensitivity
    • Cloning-Based Context-Sensitive Analysis
    • Importance of Interprocedural Analysis
    • SQL Injection
    • A Logical Representation of Data Flow
    • Execution of Datalog Programs
    • Problematic Datalog Rules
    • A Simple Pointer-Analysis Algorithm
    • Flow Insensitivity
    • Context-Insensitive Interprocedural Analysis
    • Context-Sensitive Pointer Analysis
    • Adding Context to Datalog Rules
    • Datalog Implementation by BDD's
    • Relational Operations as BDD Operations

Branch : Computer Science and Engineering
Subject : Compiler design
Unit : Data Flow Analysis

Speed of Convergence of Iterative Data-Flow Algorithms


Introduction: We are now ready to discuss the speed of convergence of iterative algorithms. As discussed in Section 9.3.3, the maximum number of iterations the algorithm may take is the product of the height of the lattice and the number of nodes in the flow graph. For many data-flow analyses, it is possible to order the evaluation such that the algorithm converges in a much smaller number of iterations. The property of interest is whether all events of significance at a node will be propagated to that node along some acyclic path. Among the data-flow analyses discussed so far, reaching definitions, available expressions and live variables have this property, but constant propagation does not. More specifically:

  • If a definition d is in IN[.£?], then there is some acyclic path from the block containing d to B such that d is in the iN's and OUT's all along that path.
  • If an expression x y is not available at the entrance to block B, then there is some acyclic path that demonstrates that either the path is from the entry node and includes no statement that kills or generates x y, or the path is from a block that kills x y and along the path there is no subsequent generation of x y.
  • If x is live on exit from block B, then there is an acyclic path from B to a use of x, along which there are no definitions of x.

We should check that in each of these cases, paths with cycles add nothing. For example, if a use of x is reached from the end of block B along a path with a cycle, we can eliminate that cycle to find a shorter path along which the use of x is still reached from B. In contrast, constant propagation does not have this property. Consider a simple program that has one loop containing a basic block with statements

L: a = b

b = c

c = 1

goto L

The first time the basic block is visited, c is found to have constant value 1, but both a and b are undefined. Visiting the basic block the second time, we find that b and c have constant values 1. It takes three visits of the basic block for the constant value 1 assigned to c to reach a.

If all useful information propagates along acyclic paths, we have an opportunity to tailor the order in which we visit nodes in iterative data-flow algorithms, so that after relatively few passes through the nodes we can be sure information has passed along all the acyclic paths.

Recall from Section 9.6.3 that if a ->• b is an edge, then the depth-first number of b is less than that of a only when the edge is a retreating edge. For forward data-flow problems, it is desirable to visit the nodes according to the depth-first ordering. Specifically, we modify the algorithm in Fig. 9.23(a) by replacing line (4), which visits the basic blocks in the flow graph with for (each block B other than ENTRY, in depth-first order) {

Example: Suppose we have a path along which a definition d propagates, such as

3 5 -)> 19 -» 35 -> 16 - 23 - 45 - 4 -> 10

where integers represent the depth-first numbers of the blocks along the path.

Then the first time through the loop of lines (4) through (6) in the algorithm in Fig. 9.23(a), d will propagate from OUT[3] to IN[5] to OUT[5], and so on, up to OUT[35]. It will not reach IN[16] on that round, because as 16 precedes 35, we had already computed IN[16] by the time d was put in OUT[35]. However, the next time we run through the loop of lines (4) through (6), when we compute IN[16], d will be included because it is in OUT[35]. Definition d will also propagate to OUT[16], IN[23], and so on, up to OUT[45], where it must wait because IN[4] was already computed on this round. On the third pass, d travels to IN[4], OUT[4], IN[10], OUT[10], and IN[17], so after three passes we establish that d reaches block 17.

It should not be hard to extract the general principle from this example. If we use depth-first order in Fig. 9.23(a), then the number of passes needed to propagate any reaching definition along any acyclic path is no more than one greater than the number of edges along that path that go from a higher numbered block to a lower numbered block. Those edges are exactly the retreating edges, so the number of passes needed is one plus the depth. Of course Algorithm 9.11 does not detect the fact that all definitions have reached wherever they can reach, until one more pass has yielded no changes. Therefore, the upper bound on the number of passes taken by that algorithm with depth-first block ordering is actually two plus the depth. A study1 0 has shown that typical flow graphs have an average depth around 2.75. Thus, the algorithm converges very quickly.

In the case of backward-flow problems, like live variables, we visit the nodes in the reverse of the depth-first order. Thus, we may propagate a use of a variable in block 17 backwards along the path

3 -> 5 19 ->• 35 16 23 -> 45 4 -> 10

in one pass to IN [4], where we must wait for the next pass in order to reach OUT[45]. On the second pass it reaches IN[16], and on the third pass it goes from OUT[35] to OUT[3].

In general, one-plus-the-depth passes suffice to carry the use of a variable backward, along any acyclic path. However, we must choose the reverse of depth-first order to visit the nodes in a pass, because then, uses propagate along any decreasing sequence in a single pass.

The bound described so far is an upper bound on all problems where cyclic paths add no information to the analysis. In special problems such as dominators, the algorithm converges even faster. In the case where the input flow graph is reducible, the correct set of dominators for each node is obtained in the first iteration of a data-flow algorithm that visits the nodes in depth-first ordering. If we do not know that the input is reducible ahead of time, it takes an extra iteration to determine that convergence has occurred.

Questions of this topic


Ask your question

<
>