Nullstone Logo

COMPANY
Home
Contacts
Customers
Testimonials

PRODUCTS
Overview
NULLSTONE for C
NULLSTONE for Java
Technical Overview

SUPPORT
Release Notes
Download
PGP Information
Service Report
Write Us

INFORMATION
Performance Results
Glossary of Terms

RELATED LINKS
Compiler Connection
Compiler Jobs

Previous Up Next
Block Merging

Some compilers limit optimizations to basic blocks, and benefit if the program graph can be transformed into a smaller number of larger basic blocks. Even compilers that optimize an entire function or program graph generally benefit from this transformation.

Example:

In the code fragment below, the basic blocks can be re-arranged to create one larger basic block.

    int a;
    int b;
    
    void f (int x, int y)
    {
      goto L1;                   /* basic block 1 */
    
    L2:                          /* basic block 2 */
      b = x + y;
      goto L3;
    
    L1:                          /* basic block 3 */
      a = x + y;
      goto L2;
    
    L3:                          /* basic block 4 */
      return;
    }
    

The code fragment below shows the function after the basic blocks have been rearranged and combined into one large basic block. Note that the CSE (x + y) is much easier to identify, particularly for compilers that limit CSE Elimination to basic blocks.

    int a;
    int b;
    
    void f (int x, int y)
    {
      a = x + y;                 /* basic block 1 */
      b = x + y;
      return;
    }
    

Below is the same code fragment after CSE Elimination.

    int a;
    int b;
    
    void f (int x, int y)
    {
      register int __t;          /* compiler generated temp */
    
      __t = x + y;               /* assign CSE to temp */
      a = __t;
      b = __t;
      return;
    }
    

Notes:

The source code in the example above is not representative of programs at the source level, but the structure is not uncommon in the Intermediate Language (IL) representation after other transformations.

Some compilers perform this transformation several times during optimization, between phases that tend to generate these graphs and phases that tend to benefit from simple graphs.

© 1990-2012 Nullstone Corporation. All Rights Reserved.