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 : Code Generation

Flow Insensitivity


Introduction: We start by showing a very simple example to illustrate the effect of ignoring control flow in points-to analysis.

Example: In Fig. 12.20, three objects, h, i, and j, are created and assigned to variables a, b, and c, respectively. Thus, surely a points to h, b points to i, and c points to j by the end of line (3). If you follow the statements (4) through (6), you discover that after line (4) a points only to i. After line (5), b points only to j, and after line (6), c points only to i.

The above analysis is flow sensitive because we follow the control flow and compute what each variable can point to after each statement. In other words, in addition to considering what points-to information each statement "generates," we also account for what points-to information each statement "kills."

For instance, the statement b = c; kills the previous fact "6 points to f and generates the new relationship "6 points to what c points to." A flow-insensitive analysis ignores the control flow, which essentially assumes that every statement in the program can be executed in any order. It computes only one global point-to map indicating what each variable can possibly point to at any point of the program execution. If a variable can point to two different objects after two different statements in a program, we simply record that it can point to both objects. In other words, in flow-insensitive analysis, an assignment does not "kill" any points-to relations but can only "generate" more points-to relations. To compute the flow-insensitive results, we repeatedly add the points to effects of each statement on the points-to relationships until no new relations are found. Clearly, lack of flow sensitivity weakens the analysis results greatly, but it tends to reduce the size of the representation of the results and make the algorithm converge faster.

The Formulation in Datalog: Let us now formalize a flow-insensitive pointer-alias analysis based on the discussion above. We shall ignore procedure calls for now and concentrate on the four kinds of statements that can affect pointers:

1.       Object creation, h: T v = new T ( ) ; This statement creates a new heap object, and variable v can point to it.

2.       Copy statement, v = w; Here, v and w are variables. The statement makes v point to whatever heap object w currently points to; i.e., w is copied into v.

3.       Field store, v.f = w; the type of object that v points to must have a field /, and this field must be of some reference type. Let v point to heap object h, and let w point to g. This statement makes the field /, in h now point to g. Note that the variable v is unchanged.

4.       Field load, v = w. f; Here, if is a variable pointing to some heap object that has a field /, and / points to some heap object h. The statement makes variable v point to h.

Note that compound field accesses in the source code such as v = w. f. g will be broken down into two primitive field-load statements:

vl = w. f;

v = vl.g;

Let us now express the analysis formally in Datalog rules. First, there are only two IDB predicates we need to compute:

1.       pts(V,H) means that variable V can point to heap object H.

2.       hpts(H, F, G) means that field F of heap object H can point to heap object G.

The EDB relations are constructed from the program itself. Since the location of statements in a program is irrelevant when the analysis is flow insensitive, we only have to assert in the EDB the existence of statements that have certain forms. In what follows, we shall make a convenient simplification. Instead of defining EDB relations to hold the information garnered from the
program, we shall use a quoted statement form to suggest the EDB relation or relations that represent the existence of such a statement. For example, "H : TV = new T" is an EDB fact asserting that at statement H there is an assignment that makes variable V point to a new object of type T. We assume that in practice, there would be a corresponding EDB relation that would be populated with ground atoms, one for each statement of this form in the program. With this convention, all we need to write the Datalog program is one rule for each of the four types of statements. The program is shown in Fig, 12.21. Rule (1) says that variable V can point to heap object H if statement H is an assignment of a new object to V. Rule (2) says that if there is a copy statement V = W, and W can point to H, then V can point to H.

Rule (3) says that if there is a statement of the form V.F = W,W can point to C7, and V can point to H, then the F field of H can point to G. Finally, rule (4) says that if there is a statement of the form V = W.F, W can point to G, and the F field of G can point to H, then V can point to H. Notice that pts and hpts are mutually recursive, but this Datalog program can be evaluated by either of the iterative algorithms discussed in Section 12.3.4.

Questions of this topic


Ask your question

<
>