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.