7/24/2010 8:05:31 PM
We define basic induction variables of a loop as those names whose only assignments within the loop are of the form I = IC, where C is a constant or a name whose value does not change within the loop. A basic induction variable may or may not form an arithmetic progression at the loop header.

For example, consider the flow graph shown in Figure 1. In the loop formed by B2, I is a basic induction variable.

Click To expand
Figure 1: Flow graph where I is a basic induction variable.

We then define an induction variable of loop L as either a basic induction variable or a name J for which there is a basic induction variable I, such that each time J is assigned in L, J's value is some linear function or value of I. That is, the value of J in L should be C1I + C2, where C1 and C2 could be functions of both constants and loop invariant names. For example, in loop L, I is a basic induction variable; and T1 is also an induction variable, because the only assignment of T1 in the loop assigns a value to T1 that is a linear function of I, computed as 4 * I.

Algorithm for Detecting and Eliminating Induction Variables

An algorithm exists that will detect and eliminate induction variables. Its method is as follows:

  1. Find all of the basic induction variables by scanning the statements of loop L.

  2. Find any additional induction variables, and for each such additional induction variable A, find the family of some basic induction B to which A belongs. (If the value of A at the point of assignment is expressed as C1B + C2, then A is said to belong to the family of basic induction variable B). Specifically, we search for names A with single assignments to A within loop L, and which have one of the following forms:

    where C is a loop constant, and B is an induction variable, basic or otherwise. If B is basic, then A is in the family of B. If B is not basic, let B be in the family of D, then the additional requirements to be satisfied are:

    1. There must be no assignment to D between the lone point of assignment to B in L and the assignment to A.

    2. There must be no definition of B outside of L reaches A.

  3. Consider each basic induction variable B in turn. For every induction variable A in the family of B:

    1. Create a new name, temp.

    2. Replace the assignment to A in the loop with A = temp.

    3. Set temp to C1B + C2 at the end of the preheader by adding the statements:

    4. Immediately after each assignment B = B + D, where D is a loop invariant, append:

      If D is a loop invariant name, and if C1 1, create a new loop invariant name for C1 * D, and add the statements:

    5. For each basic induction variable B whose only uses are to compute other induction variables in its family and in conditional branches, take some A in B's family, preferably one whose function expresses its value simply, and replace each test of the form B reloop X goto Y by:

      Delete all assignments to B from the loop, as they will now be useless.

    6. If there is no assignment to temp between the introduced statement A = temp (step 1) and the only use of A, then replace all uses of A by temp and delete the statement A = temp.

      In the flow graph shown in Figure 1, we see that I is a basic induction variable, and T1 is the additional induction variable in the family of I, because the value of T1 at the point of assignment in the loop is expressed as T1 = 4 * I. Therefore, according to step 3b, we replace T1 = 4 * I by T1 = temp. And according to step 3c, we add temp = 4 * I to the preheader. We then append the statement temp = temp + 4 after Figure 1 statement (10), as per step 3d. And according to step 3e, we replace the statement if I 20 goto B2 by:

      The results of these modifications are shown in Figure 2.

Click To expand
Figure 2: Modified flow graph.

By step 3f, replace T1 by temp. And by copy propagation, temp = 4 * I, in the preheader, can be replaced by temp = 4, and the statement I = 1 can be eliminated. In B1, the statement if temp temp2 goto B2 can be replaced by if temp 80 goto B2, and we can eliminate temp2 = 80, as shown in Figure 3.

Click To expand
Figure 3: Flow graph preheader modifications.

  •  Algorithms for Compiler Design:
  •  Algorithms for Compiler Design
  •  Algorithms for Compiler Design: THE MACHINE MODEL
  •  Algorithms for Compiler Design: STRAIGHTFORWARD CODE GENERATION
  •  Algorithms for Compiler Design: USING DAG FOR CODE GENERATION
  •  Algorithms for Compiler Design: PEEPHOLE OPTIMIZATION
  •  Algorithms for Compiler Design: L-ATTRIBUTED DEFINITIONS
  •  Algorithms for Compiler Design: SYNTAX-DIRECTED TRANSLATION SCHEMES
  •  Algorithms for Compiler Design: INTERMEDIATE CODE GENERATION
  •  Algorithms for Compiler Design: REPRESENTING THREE-ADDRESS STATEMENTS
  •  Algorithms for Compiler Design: THE ARRAY REFERENCE
  •  Algorithms for Compiler Design: SWITCH/CASE
  •  EXAMPLES for Syntax-Directed Definitions and Translations
  •  What is a cross-compiler?
  •  What is compilation?
  •  Regular Expression Notation/Finite Automata Definitions
    Top 10
    Sony STR-DN1030 – Home Cinema Amplifier
    Spotflux - Enjoy The Privilege Of A US Based IP Address
    Sony KDL-26EX553 – LCD Television
    Protecting Me
    Do Top Twitter Tips
    Canon PowerShot SX240 HS - A Powerful Perfection
    Fujifilm X-Pro1 : Mechanical dials are everywhere
    Sony NEX-F3 Review (Part 3)
    Sony NEX-F3 Review (Part 2)
    Sony NEX-F3 Review (Part 1)
    Most View
    How to beat 2012’s web threats (Part 1)
    Magix Photo Story On DVD MX Deluxe
    2012 Make It Worth ( Part 1)
    Ultrabook vs MacBook (Part 2)
    Programming .NET Security : Asymmetric Encryption Explained (part 1) - Creating Asymmetric Keys
    Windows 7 : Managing and Applying LGPOs (part 3) - Using Local Policies
    Exchange Server 2010 server roles (part 3) - Edge Transport Server role
    Olympus Launches OM-D E-M5
    Microsoft SQL Server 2005 : Report Definition and Design (part 3)
    Will Apple Be The Next Big Name in Gaming? (Part 3)
    IIS 7.0 : Managing Application Pools (part 3) - Advanced Application Pool Configuration, Monitoring Application Pool Recycling Events
    Cloud Application Architectures : Database Management
    Web Security : Seeking Design Flaws - Bypassing Required Navigation, Attempting Privileged Operations
    The best browser hacks (part 1) - Mozilla Firefox
    SharePoint 2010 : Operations Management with the SharePoint Central Administration Tool (part 4) - Reviewing Backup and Restore Settings in SPCA
    SQL Server 2008 : Using the CLR - CLR and Managed Code Explained
    Rollout Strategy in Group Policy of Windows Vista
    Reporting Services with SQL Azure : Deploying the Report & Creating a Subreport
    Vigor 2850n
    The Best Computers You're (Probably) Never Heard Of (Part 2) - Tatung Einstein, Camputers Lynx