Workshop on Essential Abstractions in GCC

(1)

Workshop on Essential Abstractions in GCC

Gray Box Probing of GCC

GCC Resource Center

(www.cse.iitb.ac.in/grc)

Department of Computer Science and Engineering, Indian Institute of Technology, Bombay

1 July 2012

1 July 2012 Graybox Probing: Outline 1/56

Outline

• Introduction to Graybox Probing of GCC

• Examining AST

• Examining GIMPLE Dumps

◮ Translation of data accesses

◮ Translation of intraprocedural control flow

◮ Translation of interprocedural control flow

• Examining RTL Dumps

• Examining Assembly Dumps

• Examining GIMPLE Optimizations

• Conclusions

Essential Abstractions in GCC GCC Resource Center, IIT Bombay

Part 1

Preliminaries

1 July 2012 Graybox Probing: Preliminaries 2/56

What is Gray Box Probing of GCC?

• Black Box probing:

Examining only the input and output relationship of a system

• White Box probing:

Examining internals of a system for a given set of inputs

• Gray Box probing:

Examining input and output of various components/modules

◮ Overview of translation sequence in GCC

◮ Overview of intermediate representations

◮ Intermediate representations of programs across important phases

(2)

Basic Transformations in GCC

Tranformation from a language to adifferent language

Target Independent Target Dependent

Parse Gimplify Tree SSA Optimize

Generate

RTL Optimize RTL Generate

ASM

GIMPLE → RTL RTL→ ASM

RTL Passes GIMPLE Passes

Transformation Passes in GCC 4.6.2

• A total of 207 unique pass names initialized in${SOURCE}/gcc/passes.c Total number of passes is 241.

◮ Some passes are called multiple times in different contexts Conditional constant propagation and dead code elimination are called thrice

◮ Some passes are enabled for specific architectures

◮ Some passes have many variations (eg. special cases for loops) Common subexpression elimination, dead code elimination

• The pass sequence can be divided broadly in two parts

◮ Passes on GIMPLE

◮ Passes on RTL

• Some passes are organizational passes to group related passes

Passes On GIMPLE in GCC 4.6.2

Pass Group Examples Number

of passes

Lowering GIMPLE IR, CFG Construction 10

Simple Interprocedural Passes (Non-LTO)

Conditional Constant Propagation, Inlining, SSA Construction

38 Regular Interprocedural

Passes (LTO)

Constant Propagation, Inlining, Pointer Analysis

10

LTO generation passes 02

Other Intraprocedural Optimizations

Constant Propagation, Dead Code Elimination, PRE Value Range Propagation, Rename SSA

65

Loop Optimizations Vectorization, Parallelization, Copy Propagation, Dead Code Elimination

28

Generating RTL 01

Total number of passes on GIMPLE 154

Passes On RTL in GCC 4.6.2

Pass Group Examples Number

of passes Intraprocedural

Optimizations

CSE, Jump Optimization, Dead Code Elimination, Jump Optimization

27 Loop Optimizations Loop Invariant Movement, Peeling,

Unswitching

07 Machine Dependent

Optimizations

Register Allocation, Instruction Scheduling, Peephole Optimizations

50 Assembly Emission

and Finishing

03

Total number of passes on RTL 87

(3)

Finding Out List of Optimizations

Along with the associated flags

• A complete list of optimizations with a brief description gcc -c --help=optimizers

• Optimizations enabled at level 2 (other levels are 0, 1, 3, and s) gcc -c -O2 --help=optimizers -Q

Producing the Output of GCC Passes

• Use the option-fdump-<ir>-<passname>

<ir>could be

◮ tree: Intraprocedural passes on GIMPLE

◮ ipa: Interprocedural passes on GIMPLE

◮ rtl: Intraprocedural passes on RTL

• Use allin place of<pass>to see all dumps

Example: gcc -fdump-tree-all -fdump-rtl-all test.c

• Dumping more details:

Suffixrawfor tree passes anddetailsorslimfor RTL passes Individual passes may have more verbosity options (e.g.

-fsched-verbose=5)

• Use -Sto stop the compilation with assembly generation

• Use --verbose-asmto see more detailed assembly dump

Total Number of Dumps

Optimization

Level Number of

Dumps Goals

Default 47 Fast compilation

O1 138

O2 164

O3 174

Os 175 Optimize for space

Selected Dumps for Our Example Program

GIMPLE dumps (t) 001t.tu

003t.original

004t.gimple

006t.vcg 009t.omplower 010t.lower 012t.eh

013t.cfg

017t.ssa 018t.veclower 019t.inline param1 020t.einline 037t.release ssa 038t.inline param2 044i.whole-program 048i.inline

138t.cplxlower0 143t.optimized 224t.statistics

ipa dumps (i)

000i.cgraph

014i.visibility

015i.early local cleanups 044i.whole-program 048i.inline

rtl dumps (r)

144r.expand

145r.sibling 147r.initvals 148r.unshare 149r.vregs

150r.into cfglayout 151r.jump

163r.reginfo

183r.outof cfglayout 184r.split1

186r.dfinit 187r.mode sw 188r.asmcons

191r.ira

194r.split2

198r.pro and epilogue 211r.stack

212r.alignments 215r.mach 216r.barriers 220r.shorten 221r.nothrow 222r.final 223r.dfinish

assembly

(4)

Passes for First Level Graybox Probing of GCC

Parser C Source Code

AST Gimplifier GIMPLE

CFG Generator

RTL Generator

Reg Allocator

pro epilogue generation

Pattern Matcher

ASM Program CFG

RTL expand

ira

prologue-epilogue

Lowering of abstraction!

Part 2

Examining AST Dump

1 July 2012 Graybox Probing: Examining AST Dump 12/56

Generating Abstract Syntax Tree

$ gcc -fdump-tree-original-raw test.c

1 July 2012 Graybox Probing: Examining AST Dump 13/56

Abstract Syntax Tree

test.c test.c.003t.original

int a;

int main() {

a = 55;

}

;; Functionmain(null)

;; enabled by -tree-original

@1 bind expr type: @2 body:@3

@2 void type name: @4 algn: 8

@3 modify expr type: @5 op 0:@6 op 1:@7

@4 type decl name: @8 type: @2

@5 integer type name: @9 size: @10 algn: 32 prec: 32 sign: signed min : @11 max : @12

@6 var decl name: @13 type: @5 srcp: t1.c:1

size: @10 algn: 32 used: 1

@7 integer cst type: @5 low :55

@8 identifier node strg: void lngt: 4

@9 type decl name: @14 type: @5

@10 integer cst type: @15 low : 32

@11 integer cst type: @5 high: -1 low : -2147483648

@13 identifier node strg: a lngt: 1

@14 identifier node strg: int lngt: 3

@15 integer type name: @16 size: @17 algn: 64 prec: 64 sign: unsigned min : @18 max : @19

@16 identifier node strg: bit size type lngt: 13

@19 integer cst type: @15 low : -1

(5)

Part 3

Examining GIMPLE Dumps

1 July 2012 Graybox Probing: Examining GIMPLE Dumps 14/56

Gimplifier

• About GIMPLE

◮ Three-address representation derived from GENERIC Computation represented as a sequence of basic operations Temporaries introduced to hold intermediate values

◮ Control construct are explicated into conditional jumps

• Examining GIMPLE Dumps

◮ Examining translation of data accesses

◮ Examining translation of control flow

◮ Examining translation of function calls

GIMPLE: Composite Expressions Involving Local and Global Variables

test.c test.c.004t.gimple

int a;

int main() {

int x = 10;

int y = 5;

x = a + x * y;

y = y - a * x;

}

x = 10;

y = 5;

D.1954 = x * y;

a.0 = a;

x = D.1954 + a.0;

a.1 = a;

D.1957 = a.1 * x;

y = y - D.1957;

Global variables are treated as “memory locations” and local variables are treated as “registers”

GIMPLE: 1-D Array Accesses

int main() {

int a[3], x;

a[1] = a[2] = 10;

x = a[1] + a[2];

a[0] = a[1] + a[1]*x;

}

a[2] = 10;

D.1952 = a[2];

a[1] = D.1952;

D.1953 = a[1];

D.1954 = a[2];

x = D.1953 + D.1954;

D.1955 = x + 1;

D.1956 = a[1];

D.1957 = D.1955 * D.1956;

a[0] = D.1957;

(6)

GIMPLE: 2-D Array Accesses

int main() {

int a[3][3], x, y;

a[0][0] = 7;

a[1][1] = 8;

a[2][2] = 9;

x = a[0][0] / a[1][1];

y = a[1][1] % a[2][2];

}

a[0][0] = 7;

a[1][1] = 8;

a[2][2] = 9;

D.1953 = a[0][0];

D.1954 = a[1][1];

x = D.1953 / D.1954;

D.1955 = a[1][1];

D.1956 = a[2][2];

y = D.1955 % D.1956;

• No notion of “addressable memory” in GIMPLE.

• Array reference is a single operation in GIMPLE and is linearized in RTL during expansion

GIMPLE: Use of Pointers

int main() {

int **a,*b,c;

b = &c;

a = &b;

**a = 10; /* c = 10 */

}

~

main () {

int * D.1953;

int * * a;

int * b;

int c;

b = &c;

a = &b;

D.1953 = *a;

*D.1953 = 10;

}

GIMPLE: Use of Structures

typedef struct address { char *name;

} ad;

typedef struct student { int roll;

ad *ct;

} st;

int main() { st *s;

s = malloc(sizeof(st));

s->roll = 1;

s->ct=malloc(sizeof(ad));

s->ct->name = "Mumbai";

}

main () {

void * D.1957;

struct ad * D.1958;

struct st * s;

extern void * malloc (unsigned int);

s = malloc (8);

s->roll = 1;

D.1957 = malloc (4);

s->ct = D.1957;

D.1958 = s->ct;

D.1958->name = "Mumbai";

}

GIMPLE: Pointer to Array

int main() {

int *p a, a[3];

p a = &a[0];

*p a = 10;

*(p a+1) = 20;

*(p a+2) = 30;

}

main () {

int * D.2048;

int * D.2049;

int * p a;

int a[3];

p a = &a[0];

*p a = 10;

D.2048 = p a + 4;

*D.2048 = 20;

D.2049 = p a + 8;

*D.2049 = 30;

}

(7)

GIMPLE: Translation of Conditional Statements

int main() {

int a=2, b=3, c=4;

while (a<=7) {

a = a+1;

}

if (a<=12) a = a+b+c;

}

if (a <= 12) goto <D.1200>;

else goto <D.1201>;

<D.1200>:

D.1199 = a + b;

a = D.1199 + c;

<D.1201>:

GIMPLE: Translation of Loops

int main() {

int a=2, b=3, c=4;

while (a<=7) {

a = a+1;

}

if (a<=12) a = a+b+c;

}

goto <D.1197>;

<D.1196>:

a = a + 1;

<D.1197>:

if (a <= 7) goto <D.1196>;

else goto <D.1198>;

<D.1198>:

Control Flow Graph: Textual View

test.c.004t.gimple test.c.013t.cfg

if (a <= 12) goto <D.1200>;

else goto <D.1201>;

<D.1200>:

D.1199 = a + b;

a = D.1199 + c;

<D.1201>:

<bb 5>:

if (a <= 12) goto <bb 6>;

else

goto <bb 7>;

<bb 6>:

D.1199 = a + b;

a = D.1199 + c;

<bb 7>:

return;

Control Flow Graph: Pictorial View

test.c.013t.cfg

Block 4:

if(a<=7)

Block 5:

if(a<=12)

Block 3:

a = a +1;

Block 6:

D.1199= a + b;

a= D.1199 + c;

Block 7:

return;

False True

True

False

(8)

Control Flow Graph: Pictorial View

test.c.013t.cfg

Block 4:

if(a<=7)

Block 5:

if(a<=12)

Block 3:

a = a +1;

Block 6:

D.1199= a + b;

a= D.1199 + c;

Block 7:

return;

False True

True

False while(a<= 7)

a = a + 1;

Control Flow Graph: Pictorial View

test.c.013t.cfg

Block 4:

if(a<=7)

Block 5:

if(a<=12)

Block 3:

a = a +1;

Block 6:

D.1199= a + b;

a= D.1199 + c;

Block 7:

return;

False True

True

False if(a<= 12)

a = a + b + c;

GIMPLE: Function Calls and Call Graph

test.c test.c.000i.cgraph

extern int divide(int, int);

int multiply(int a, int b) {

return a*b;

}

int main() { int x,y;

x = divide(20,5);

y = multiply(x,2);

printf("%d\n", y);

}

printf/3(-1) @0xb73c7ac8 availability:not available reachable called by: main/1 (1.00 per call)

calls:

divide/2(-1) @0xb73c7a10 availability:not available reachable called by: main/1 (1.00 per call)

calls:

main/1(1) @0xb73c7958 availability:available 38 time, 11 benefit 11 size, 2 benefit needed reachable body externally visible called by:

calls: printf/3 (1.00 per call) multiply/0 (1.00 per call) divide/2 (1.00 per call)

multiply/0(0) @0xb73c78a0 vailability:available 1 time, 13 benefit 1 size, 4 benefit needed reachable body externally visible called by: main/1 (1.00 per call)

calls:

GIMPLE: Function Calls and Call Graph

test.c test.c.000i.cgraph call graph

extern int divide(int, int);

int multiply(int a, int b) {

return a*b;

}

int main() { int x,y;

x = divide(20,5);

y = multiply(x,2);

printf("%d\n", y);

}

printf/3(-1)

called by: main/1 calls:

divide/2(-1)

main/1(1) called by:

calls: printf/3 multiply/0 divide/2 multiply/0(0)

main printf divide

multiply

(9)

GIMPLE: Call Graphs for Recursive Functions

test.c call graph

int even(int n)

{ if (n == 0) return 1;

else return (!odd(n-1));

}

int odd(int n)

{ if (n == 1) return 1;

else return (!even(n-1));

} main() { int n;

n = abs(readNumber());

if (even(n))

printf ("n is even\n");

else printf ("n is odd\n");

}

main

readNumber abs even printf

odd

Inspect GIMPLE When in Doubt (1)

int x=2,y=3;

x = y++ + ++x + ++y;

What are the values of x and y?

x = 10 , y =5

x 3

y 3

(y+x) 6 (y+x) +y

Inspect GIMPLE When in Doubt (1)

int x=2,y=3;

x = y++ + ++x + ++y;

x = 10 , y =5

x 3

y 4

(y+x) 6 (y+x) +y

Inspect GIMPLE When in Doubt (1)

int x=2,y=3;

x = y++ + ++x + ++y;

x = 10 , y =5

x 3

y 5

(y+x) 6 (y+x) +y

(10)

Inspect GIMPLE When in Doubt (1)

int x=2,y=3;

x = y++ + ++x + ++y;

x = 10 , y =5

x 3

y 5

(y+x) 6 (y+x) +y 11

Inspect GIMPLE When in Doubt (1)

int x=2,y=3;

x = y++ + ++x + ++y;

x = 10 , y =5

x 3

y 5

(y+x) 6 (y+x) +y 11

x = 2;

y = 3;

x = x + 1; /* 3 */

D.1572 = y + x; /* 6 */

y = y + 1; /* 4 */

x = D.1572 + y; /* 10 */

y = y + 1; /* 5 */

Inspect GIMPLE When in Doubt (2)

• How isa[i] = i++handled?

This is an undefined behaviour as per C standards.

• What is the order of parameter evaluation?

For a callf(getX(),getY()), is the order left to right? arbitrary?

Is the evaluation order in GCC consistent?

• Understanding complicated declarations in C can be difficult What does the following declaration mean :

int * (* (*MYVAR) (int) ) [10];

Hint: Use-fdump-tree-original-raw-verboseoption. The dump to see is003t.original

Part 4

Examining RTL Dumps

(11)

1 July 2012 Graybox Probing: Examining RTL Dumps 30/56

RTL for i386: Arithmetic Operations (1)

Translation ofa=a+ 1

Dump file: test.c.144r.expand

(insn 12 11 13 4 (parallel [ ( set (mem/c/i:SI

(plus:SI

(reg/f:SI 54 virtual-stack-vars)

(const_int -4 [0xfffffffc])) [0 a+0 S4 A32]) (plus:SI

(mem/c/i:SI (plus:SI

(const_int -4 [0xfffffffc])) [0 a+0 S4 A32]) (const_int 1 [0x1])))

(clobber (reg:CC 17 flags)) ]) t.c:24 -1 (nil))

RTL for i386: Arithmetic Operations (1)

(plus:SI

set mem

plus reg 54 -4

plus mem

plus reg 54 -4

1

RTL for i386: Arithmetic Operations (1)

(plus:SI

set

mem plus reg 54 -4

plus mem

plus reg 54 -4

1

RTL for i386: Arithmetic Operations (1)

(plus:SI

set mem

plus reg 54 -4

plus mem

plus reg 54 -4

1 a is a local variable

allocated on stack

(12)

RTL for i386: Arithmetic Operations (1)

(plus:SI

set mem

plus reg 54 -4

plus mem

plus reg 54 -4

1 a is a local variable

allocated on stack

RTL for i386: Arithmetic Operations (1)

(plus:SI

parallel

clobber

reg:CC set

. . . .

side-effect of plus may modify condition code register

non-deterministically

RTL for i386: Arithmetic Operations (1)

(plus:SI

Output withslimsuffix

{[r54:SI-0x4]=[r54:SI-0x4]+0x1;

clobber flags:CC;

}

Additional Information in RTL

(insn 12 11 13 4 (parallel [ (set (mem/c/i:SI

(plus:SI

Current Instruction

(13)

Additional Information in RTL

(plus:SI

Previous Instruction

Additional Information in RTL

(plus:SI

Next Instruction

Additional Information in RTL

(plus:SI

Basic Block

Additional Information in RTL

(plus:SI

File name: Line number

(14)

Additional Information in RTL

(plus:SI

memory reference that does not trap

Additional Information in RTL

(plus:SI

scalar that is not a part of an aggregate

Additional Information in RTL

(plus:SI

register that holds a pointer

Additional Information in RTL

(plus:SI

single integer

(15)

RTL for i386: Arithmetic Operations (2)

Translation ofa=a+ 1 whena is a global variable Dump file: test.c.144r.expand

(insn 11 10 12 4 (set (reg:SI 64 [ a.0 ])

(mem/c/i:SI (symbol_ref:SI ("a")

<var_decl 0xb7d8d000 a>) [0 a+0 S4 A32])) t.c:26 -1 (nil)) (insn 12 11 13 4 (parallel [

(set (reg:SI 63 [ a.1 ])

(plus:SI (reg:SI 64 [ a.0 ]) (const_int 1 [0x1]))) (clobber (reg:CC 17 flags)) ]) t.c:26 -1 (nil))

(insn 13 12 14 4 (set

<var_decl 0xb7d8d000 a>) [0 a+0 S4 A32]) (reg:SI 63 [ a.1 ])) t.c:26 -1 (nil))

RTL for i386: Arithmetic Operations (2)

(insn 11 10 12 4 (set (reg:SI 64 [ a.0 ])

(set (reg:SI 63 [ a.1 ])

(insn 13 12 14 4 (set

Load a into reg64

RTL for i386: Arithmetic Operations (2)

(insn 11 10 12 4 (set (reg:SI 64 [ a.0 ])

(set (reg:SI 63 [ a.1 ])

(insn 13 12 14 4 (set

Load a into reg64 reg63 = reg64 + 1

RTL for i386: Arithmetic Operations (2)

(insn 11 10 12 4 (set (reg:SI 64 [ a.0 ])

(set (reg:SI 63 [ a.1 ])

(insn 13 12 14 4 (set

Load a into reg64 reg63 = reg64 + 1 store reg63 into a

(16)

RTL for i386: Arithmetic Operations (2)

(insn 11 10 12 4 (set (reg:SI 64 [ a.0 ])

(set (reg:SI 63 [ a.1 ])

(insn 13 12 14 4 (set

Load a into reg64 reg63 = reg64 + 1 store reg63 into a Output withslimsuffix r64:SI=[‘a’]

{r63:SI=r64:SI+0x1;

clobber flags:CC;

}

[‘a’]=r63:SI

RTL for i386: Arithmetic Operations (3)

Translation ofa=a+ 1 whena is a formal parameter Dump file: test.c.144r.expand

(insn 10 9 11 4 (parallel [ (set

(mem/c/i:SI

(reg/f:SI 53 virtual-incoming-args) [0 a+0 S4 A32]) (plus:SI

(mem/c/i:SI

(reg/f:SI 53 virtual-incoming-args) [0 a+0 S4 A32]) (const_int 1 [0x1])))

(clobber (reg:CC 17 flags)) ]) t1.c:25 -1 (nil))

RTL for i386: Arithmetic Operations (3)

(mem/c/i:SI

Access through argument pointer register instead of frame pointer register No offset required?

RTL for i386: Arithmetic Operations (3)

(mem/c/i:SI

Access through argument pointer register instead of frame pointer register No offset required?

Output withslimsuffix {[r53:SI]=[r53:SI]+0x1;

clobber flags:CC;

}

(17)

RTL for i386: Arithmetic Operation (4)

Translation ofa=a+ 1 whena is the second formal parameter Dump file: test.c.144r.expand

(reg/f:SI 53 virtual-incoming-args) (const_int 4 [0x4])) [0 a+0 S4 A32]) (plus:SI

(reg/f:SI 53 virtual-incoming-args) (const_int 4 [0x4])) [0 a+0 S4 A32]) (const_int 1 [0x1])))

RTL for i386: Arithmetic Operation (4)

Translation ofa=a+ 1 whena is the second formal parameter Dump file: test.c.144r.expand

(reg/f:SI 53 virtual-incoming-args) (const_int 4 [0x4])) [0 a+0 S4 A32]) (plus:SI

(reg/f:SI 53 virtual-incoming-args) (const_int 4 [0x4])) [0 a+0 S4 A32]) (const_int 1 [0x1])))

Offset 4 added to the argument pointer register

When a is the first parameter, its offset is 0!

Output withslimsuffix

{[r53:SI+0x4]=[r53:SI+0x4]+0x1;

clobber flags:CC;

}

RTL for spim: Arithmetic Operations

Translation ofa=a+ 1 whena is a local variable Dump file: test.c.144r.expand

(insn 7 6 8 4 (set (reg:SI 39)

(mem/c/i:SI (plus:SI (reg/f:SI 33 virtual-stack-vars) (const_int -4 [...])) [...])) -1 (nil))

(insn 8 7 9 4 test.c:6 (set (reg:SI 40) (plus:SI (reg:SI 39)

(const_int 1 [...]))) -1 (nil)) (insn 9 8 10 4 test.c:6 (set

(mem/c/i:SI (plus:SI (reg/f:SI 33 virtual-stack-vars) (const_int -4 [...])) [...])

(reg:SI 40)) test.c:6 -1 (nil))

r39=stack($fp - 4) r40=r39+1 stack($fp - 4)=r40

In spim, a variable is loaded into register to perform any instruction, hence three instructions are generated

RTL for i386: Control Flow

What does this represent?

(jump insn 15 14 16 4 (set (pc)

(if then else (lt (reg:CCGC 17 flags) (const int 0 [0x0]))

(label ref 12)

(pc))) p1.c:6 -1 (nil) (nil)

-> 12)

pc = r17<0 ? label(12) : pc

(18)

RTL for i386: Control Flow

Translation ofif (a > b) { /* something */ } Dump file: test.c.144r.expand

(insn 8 7 9 (set (reg:SI 61)

(mem/c/i:SI (plus:SI (reg/f:SI 54 virtual-stack-vars)

(const int -8 [0xfffffff8])) [0 a+0 S4 A32])) test.c:7 -1 (nil)) (insn 9 8 10 (set (reg:CCGC 17 flags)

(compare:CCGC (reg:SI 61)

(mem/c/i:SI (plus:SI (reg/f:SI 54 virtual-stack-vars)

(const int -4 [0xfffffffc])) [0 b+0 S4 A32]))) test.c:7 -1 (nil)) (jump insn 10 9 0 (set (pc)

(if then else (le (reg:CCGC 17 flags) (const int 0 [0x0]))

(label ref 13)

(pc))) test.c:7 -1 (nil) -> 13)

Part 5

Examining Assembly Dumps

1 July 2012 Graybox Probing: Examining Assembly Dumps 38/56

i386 Assembly

Dump file: test.s

jmp .L2 .L3:

addl $1, -4(%ebp) .L2:

cmpl $7, -4(%ebp) jle .L3

cmpl $12, -4(%ebp) jg .L6

movl -8(%ebp), %edx movl -4(%ebp), %eax addl %edx, %eax addl -12(%ebp), %eax movl %eax, -4(%ebp) .L6:

while (a <= 7) {

a = a+1;

}

if (a <= 12) {

a = a+b+c;

}

i386 Assembly

Dump file: test.s

jmp .L2 .L3:

addl $1, -4(%ebp) .L2:

while (a <= 7) {

a = a+1;

}

if (a <= 12) {

a = a+b+c;

}

(19)

i386 Assembly

Dump file: test.s

jmp .L2 .L3:

addl $1, -4(%ebp) .L2:

while (a <= 7) {

a = a+1;

}

if (a <= 12) {

a = a+b+c;

}

i386 Assembly

Dump file: test.s

jmp .L2 .L3:

addl $1, -4(%ebp) .L2:

while (a <= 7) {

a = a+1;

}

if (a <= 12) {

a = a+b+c;

}

Part 6

Examining GIMPLE Optimization

1 July 2012 Graybox Probing: Examining GIMPLE Optimization 39/56

Example Program for Observing Optimizations

int main()

{ int a, b, c, n;

a = 1;

b = 2;

c = 3;

n = c*2;

while (a <= n) {

a = a+1;

}

if (a < 12) a = a+b+c;

return a;

}

• What does this program return?

• 12

• We use this program to illustrate various shades of the following optimizations:

Constant propagation, Copy propagation, Loop unrolling, Dead code elimination

(20)

Compilation Command

$gcc -fdump-tree-all -O2 ccp.c

Example Program 1

Programccp.c Control flow graph

int main()

{ int a, b, c, n;

a = 1;

b = 2;

c = 3;

n = c*2;

while (a <= n) {

a = a+1;

}

if (a < 12) a = a+b+c;

return a;

}

B2 a = 1 b = 2 c = 3 n = c∗ 2

B2

B4 if a≤ n B4

B3 a = a + 1 B3 B5 if a≤ 11

B6 D.1200 = a + b a = D.1200 + c B6 B7 D.1201 = a

return D.1201 F T

T F

Control Flow Graph: Pictorial and Textual View

Control flow graph Dump file ccp.c.013t.cfg

B2 a = 1 b = 2 c = 3 n = c∗2

B2

B4 if a≤n B4

B3 a = a + 1 B3 B5 if a≤11

B6 D.1200 = a + b a = D.1200 + c B6

B7 D.1201 = a return D.1201

F T

T F

Control Flow Graph: Pictorial and Textual View

B2 a = 1 b = 2 c = 3 n = c∗2

B2

B4 if a≤n B4

B3 a = a + 1 B3 B5 if a≤11

B6 D.1200 = a + b a = D.1200 + c B6

B7 D.1201 = a return D.1201

F T

T F

<bb 2>:

a = 1;

b = 2;

c = 3;

n = c * 2;

goto <bb 4>;

(21)

Control Flow Graph: Pictorial and Textual View

B2 a = 1 b = 2 c = 3 n = c∗2

B2

B4 if a≤n B4

B3 a = a + 1 B3 B5 if a≤11

B6 D.1200 = a + b a = D.1200 + c B6

B7 D.1201 = a return D.1201

F T

T F

<bb 3>:

a = a + 1;

<bb 4>:

if (a <= n) goto <bb 3>;

else

goto <bb 5>;

Control Flow Graph: Pictorial and Textual View

B2 a = 1 b = 2 c = 3 n = c∗2

B2

B4 if a≤n B4

B3 a = a + 1 B3 B5 if a≤11

B6 D.1200 = a + b a = D.1200 + c B6

B7 D.1201 = a return D.1201

F T

T F

<bb 5>:

if (a <= 11) goto <bb 6>;

else

goto <bb 7>;

<bb 6>:

D.1200 = a + b;

a = D.1200 + c;

Control Flow Graph: Pictorial and Textual View

B2 a = 1 b = 2 c = 3 n = c∗2

B2

B4 if a≤n B4

B3 a = a + 1 B3 B5 if a≤11

B6 D.1200 = a + b a = D.1200 + c B6

B7 D.1201 = a return D.1201

F T

T F

<bb 7>:

D.1201 = a;

return D.1201;

Single Static Assignment (SSA) Form

Control flow graph SSA Form

B2 a = 1; b = 2 c = 3; n = c∗2 B2

B4 if a≤n B4 B3 a = a + 1 B3 B5 if a≤11

B6 D.1200 = a + b a = D.1200 + c B6

B7 D.1201 = a return D.1201

T F

B2 a 3 = 1; b 4 = 2

c 5 = 3; n 6 = c 5∗2 B2

B4 a 1 =φ(a 3, a 7) if a 1≤n 6 B4

B3 a 7 = a 1 + 1 B5 if a 1≤11

B6 D.1200 8 = a 1 + b 4 a 9 = D.1200 8 + c 5 B6

B7

a 2 =φ(a 1, a 9) D.1201 10 = a 2 return D.1201 10

T F

(22)

Single Static Assignment (SSA) Form

B2 a = 1; b = 2 c = 3; n = c∗2 B2

B4 if a≤n B4 B3 a = a + 1 B3 B5 if a≤11

B6 D.1200 = a + b a = D.1200 + c B6

B7 D.1201 = a return D.1201

T F

B2 a 3 = 1; b 4 = 2

c 5 = 3; n 6 = c 5∗2 B2

B4 a 1 =φ(a 3, a 7) if a 1≤n 6 B4

B3 a 7 = a 1 + 1 B5 if a 1≤11

B6 D.1200 8 = a 1 + b 4 a 9 = D.1200 8 + c 5 B6

B7

a 2 =φ(a 1, a 9) D.1201 10 = a 2 return D.1201 10

T F

Single Static Assignment (SSA) Form

B2 a = 1; b = 2 c = 3; n = c∗2 B2

B4 if a≤n B4 B3 a = a + 1 B3 B5 if a≤11

B6 D.1200 = a + b a = D.1200 + c B6

B7 D.1201 = a return D.1201

T F

B2 a 3 = 1; b 4 = 2

c 5 = 3; n 6 = c 5∗2 B2

B4 a 1 =φ(a 3, a 7) if a 1≤n 6 B4

B3 a 7 = a 1 + 1 B5 if a 1≤11

B6 D.1200 8 = a 1 + b 4 a 9 = D.1200 8 + c 5 B6

B7

a 2 =φ(a 1, a 9) D.1201 10 = a 2 return D.1201 10

T F

Single Static Assignment (SSA) Form

B2 a = 1; b = 2 c = 3; n = c∗2 B2

B4 if a≤n B4 B3 a = a + 1 B3 B5 if a≤11

B6 D.1200 = a + b a = D.1200 + c B6

B7 D.1201 = a return D.1201

T F

B2 a 3 = 1; b 4 = 2

c 5 = 3; n 6 = c 5∗2 B2

B4 a 1 =φ(a 3, a 7) if a 1≤n 6 B4

B3 a 7 = a 1 + 1 B5 if a 1≤11

B6 D.1200 8 = a 1 + b 4 a 9 = D.1200 8 + c 5 B6

B7

a 2 =φ(a 1, a 9) D.1201 10 = a 2 return D.1201 10

T F

Single Static Assignment (SSA) Form

B2 a = 1; b = 2 c = 3; n = c∗2 B2

B4 if a≤n B4 B3 a = a + 1 B3 B5 if a≤11

B6 D.1200 = a + b a = D.1200 + c B6

B7 D.1201 = a return D.1201

T F

B2 a 3 = 1; b 4 = 2

c 5 = 3; n 6 = c 5∗2 B2

B4 a 1 =φ(a 3, a 7) if a 1≤n 6 B4

B3 a 7 = a 1 + 1 B5 if a 1≤11

B6 D.1200 8 = a 1 + b 4 a 9 = D.1200 8 + c 5 B6

B7

a 2 =φ(a 1, a 9) D.1201 10 = a 2 return D.1201 10

T F

(23)

Single Static Assignment (SSA) Form

B2 a = 1; b = 2 c = 3; n = c∗2 B2

B4 if a≤n B4 B3 a = a + 1 B3 B5 if a≤11

B6 D.1200 = a + b a = D.1200 + c B6

B7 D.1201 = a return D.1201

T F

B2 a 3 = 1; b 4 = 2

c 5 = 3; n 6 = c 5∗2 B2

B4 a 1 =φ(a 3, a 7) if a 1≤n 6 B4

B3 a 7 = a 1 + 1 B5 if a 1≤11

B6 D.1200 8 = a 1 + b 4 a 9 = D.1200 8 + c 5 B6

B7

a 2 =φ(a 1, a 9) D.1201 10 = a 2 return D.1201 10

T F

Properties of SSA Form

B2 a 3 = 1; b 4 = 2

c 5 = 3; n 6 = c 5∗2 B2

B4 a 1 =φ(a 3, a 7) if a 1≤n 6 B4

B3 a 7 = a 1 + 1 B5 if a 1≤11

B6 D.1200 8 = a 1 + b 4 a 9 = D.1200 8 + c 5 B6

B7

a 2 =φ(a 1, a 9) D.1201 10 = a 2 return D.1201 10

T F

• Aφfunction is a multiplexer or a selection function

• Every use of a variable corresponds to a unique definition of the variable

• For every use, the definition is guaranteed to appear on every path leading to the use

SSA construction algorithm is ex- pected to insert as fewφfunctions as possible to ensure the above properties

SSA Form: Pictorial and Textual View

CFG in SSA form Dump file ccp.c.017t.ssa B2 a 3 = 1; b 4 = 2

c 5 = 3; n 6 = c 5∗2 B2

B4 a 1 =φ(a 3, a 7) if a 1≤n 6 B4

B3 a 7 = a 1 + 1 B5 if a 1≤11

B6 D.1200 8 = a 1 + b 4 a 9 = D.1200 8 + c 5 B6

B7

a 2 =φ(a 1, a 9) D.1201 10 = a 2 return D.1201 10

T F

SSA Form: Pictorial and Textual View

c 5 = 3; n 6 = c 5∗2 B2

B4 a 1 =φ(a 3, a 7) if a 1≤n 6 B4

B3 a 7 = a 1 + 1 B5 if a 1≤11

B6 D.1200 8 = a 1 + b 4 a 9 = D.1200 8 + c 5 B6

B7

a 2 =φ(a 1, a 9) D.1201 10 = a 2 return D.1201 10

T F

<bb 2>:

a 3 = 1;

b 4 = 2;

c 5 = 3;

n 6 = c 5 * 2;

goto <bb 4>;

<bb 3>:

a 7 = a 1 + 1;

(24)

SSA Form: Pictorial and Textual View

c 5 = 3; n 6 = c 5∗2 B2

B4 a 1 =φ(a 3, a 7) if a 1≤n 6 B4

B3 a 7 = a 1 + 1 B5 if a 1≤11

B6 D.1200 8 = a 1 + b 4 a 9 = D.1200 8 + c 5 B6

B7

a 2 =φ(a 1, a 9) D.1201 10 = a 2 return D.1201 10

T F

<bb 4>:

# a 1 = PHI <a 3(2), a 7(3)>

if (a 1 <= n 6) goto <bb 3>;

else

goto <bb 5>;

<bb 5>:

if (a 1 <= 11) goto <bb 6>;

else

goto <bb 7>;

SSA Form: Pictorial and Textual View

c 5 = 3; n 6 = c 5∗2 B2

B4 a 1 =φ(a 3, a 7) if a 1≤n 6 B4

B3 a 7 = a 1 + 1 B5 if a 1≤11

B6 D.1200 8 = a 1 + b 4 a 9 = D.1200 8 + c 5 B6

B7

a 2 =φ(a 1, a 9) D.1201 10 = a 2 return D.1201 10

T F

<bb 6>:

D.1200 8 = a 1 + b 4;

a 9 = D.1200 8 + c 5;

<bb 7>:

# a 2 = PHI <a 1(5), a 9(6)>

D.1201 10 = a 2;

return D.1201 10;

A Comparison of CFG and SSA Dumps

Dump file ccp.c.013t.cfg Dump file ccp.c.017t.ssa

<bb 2>:

a = 1;

b = 2;

c = 3;

n = c * 2;

goto <bb 4>;

<bb 3>:

a = a + 1;

<bb 2>:

a 3 = 1;

b 4 = 2;

c 5 = 3;

n 6 = c 5 * 2;

goto <bb 4>;

<bb 3>:

a 7 = a 1 + 1;

A Comparison of CFG and SSA Dumps

<bb 4>:

if (a <= n) goto <bb 3>;

else

goto <bb 5>;

<bb 5>:

if (a <= 11) goto <bb 6>;

else

goto <bb 7>;

<bb 4>:

# a 1 = PHI <a 3(2), a 7(3)>

if (a 1 <= n 6) goto <bb 3>;

else

goto <bb 5>;

<bb 5>:

if (a 1 <= 11) goto <bb 6>;

else

goto <bb 7>;

(25)

A Comparison of CFG and SSA Dumps

<bb 6>:

D.1200 = a + b;

a = D.1200 + c;

<bb 7>:

D.1201 = a;

return D.1201;

<bb 6>:

D.1200 8 = a 1 + b 4;

a 9 = D.1200 8 + c 5;

<bb 7>:

# a 2 = PHI <a 1(5), a 9(6)>

D.1201 10 = a 2;

return D.1201 10;

Copy Renamimg

Input dump: ccp.c.017t.ssa Output dump: ccp.c.022t.copyrename1

<bb 7>:

# a 2 = PHI <a 1(5), a 9(6)>

D.1201 10 = a 2;

return D.1201 10;

<bb 7>:

# a 2 = PHI <a 1(5), a 9(6)>

a 10 = a 2;

return a 10;

First Level Constant and Copy Propagation

Input dump: ccp.c.022t.copyrename1 Output dump: ccp.c.023t.ccp1

<bb 2>:

a 3 = 1;

b 4 = 2;

c 5 = 3;

n 6 = c 5 * 2;

goto <bb 4>;

<bb 3>:

a 7 = a 1 + 1;

<bb 4>:

# a 1 = PHI < a 3(2), a 7(3)>

if (a 1 <= n 6) goto <bb 3>;

else

goto <bb 5>;

<bb 2>:

a 3 = 1;

b 4 = 2;

c 5 = 3;

n 6 = 6;

goto <bb 4>;

<bb 3>:

a 7 = a 1 + 1;

<bb 4>:

# a 1 = PHI < 1(2), a 7(3)>

if (a 1 <= 6) goto <bb 3>;

else

goto <bb 5>;

First Level Constant and Copy Propagation

Input dump: ccp.c.022t.copyrename1 Output dump: ccp.c.023t.ccp1

<bb 2>:

a 3 = 1;

b 4 = 2;

c 5 = 3;

n 6 = 6;

goto <bb 4>;

...

<bb 6>:

D.1200 8 = a 1 + b 4;

a 9 = D.1200 8 + c 5;

<bb 2>:

a 3 = 1;

b 4 = 2;

c 5 = 3;

n 6 = 6;

goto <bb 4>;

...

<bb 6>:

D.1200 8 = a 1 + 2;

a 9 = D.1200 8 + 3;

(26)

Second Level Copy Propagation

Input dump: ccp.c.023t.ccp1 Output dump: ccp.c.027t.copyprop1

<bb 6>:

D.1200 8 = a 1 + 2;

a 9 = D.1200 8 + 3;

<bb 7>:

# a 2 = PHI <a 1(5), a 9(6)>

a 10 = a 2;

return a 10;

<bb 6>:

a 9 = a 1 + 5;

<bb 7>:

# a 2 = PHI <a 1(5), a 9(6)>

return a 2;

The Result of Copy Propagation and Renaming

B2 a 3 = 1; b 4 = 2

c 5 = 3; n 6 = c 5∗2 B2

B4 a 1 =φ(a 3, a 7) if a 1≤n 6 B4

B3 a 7 = a 1 + 1 B5 if a 1≤11

B6 D.1200 8 = a 1 + b 4 a 9 = D.1200 8 + c 5 B6

B7

a 2 =φ(a 1, a 9) D.1201 10 = a 2 return D.1201 10

T F

B2 a 3 = 1; b 4 = 2 c 5 = 3; n 6 =6 B2

B4 a 1 =φ(1, a 7) if a 1≤6 B4

B3 a 7 = a 1 + 1 B5 if a 1≤11

B6 a 9 = a 1 +5 B6

B7 a 2 =φ(a 1, a 9) returna 2

T F

The Result of Copy Propagation and Renaming

B2 a 3 = 1; b 4 = 2 c 5 = 3; n 6 = 6 B2

B4 a 1 =φ(1, a 7) if a 1≤6 B4

B3 a 7 = a 1 + 1 B5 if a 1≤11

B6 a 9 = a 1 + 5 B6

B7 a 2 =φ(a 1, a 9) return a 2

T F

• No uses for variablesa 3,b 4, c 5, andn 6

• Assignments to these variables can be deleted

Dead Code Elimination Using Control Dependence

Dump file ccp.c.029t.cddce1 B2 a 3 = 1; b 4 = 2

c 5 = 3; n 6 = 6 B2

B4 a 1 =φ(1, a 7) if a 1≤6 B4

B3 a 7 = a 1 + 1 B5 if a 1≤11

B6 a 9 = a 1 + 5 B6

T F

<bb 2>:

goto <bb 4>;

<bb 3>:

a 7 = a 1 + 1;

<bb 4>:

# a 1 = PHI <1(2), a 7(3)>

if (a 1 <= 6) goto <bb 3>;

else goto <bb 5>;

<bb 5>:

if (a 1 <= 11) goto <bb 6>;

else goto <bb 7>;

<bb 6>:

a 9 = a 1 + 5;

<bb 7>:

# a 2 = PHI <a 1(5), a 9(6)>

return a 2;

(27)

Loop Unrolling

B2 a 3 = 1; b 4 = 2 c 5 = 3; n 6 = 6 B2

B4 a 1 =φ(1, a 7) if a 1≤6 B4

B3 a 7 = a 1 + 1 B5 if a 1≤11

B6 a 9 = a 1 + 5 B6

T F

B4 a = 2 a = a + 1 a = a + 1 a = a + 1 a = a + 1 a = a + 1

B4

B5 if a 1 ≤11

B6 a 9 = a 1 + 5 B6

T F

Complete Unrolling of Inner Loops

Dump file: ccp.c.058t.cunrolli

<bb 2>:

a_12 = 2;

a_14 = a_12 + 1;

a_16 = a_14 + 1;

a_18 = a_16 + 1;

a_20 = a_18 + 1;

a_22 = a_20 + 1;

if (a_22 <= 11) goto <bb 3>;

else goto <bb 4>;

<bb 3>:

a_9 = a_22 + 5;

<bb 4>:

# a_2 = PHI <a_22(2), a_9(3)>

return a_2;

B2

a 12 = 2 a 14 = a 12 + 1 a 16 = a 14 + 1 a 18 = a 16 + 1 a 20 = a 18 + 1 a 22 = a 20 + 1 if a 22≤11

B3 a 9 = a 22 + 5 B3

B4 a 2 =φ(a 22, a 9) return a 2

T F

Another Round of Constant Propagation

Input Dump file: ccp.c.059t.ccp2

B2

a 12 = 2 a 14 = a 12 + 1 a 16 = a 14 + 1 a 18 = a 16 + 1 a 20 = a 18 + 1 a 22 = a 20 + 1 if a 22≤11

B3 a 9 = a 22 + 5 B3

B4 a 2 =φ(a 22, a 9) return a 2

T F

main () {

<bb 2>:

return 12;

}

Part 7

Conclusions

(28)

1 July 2012 Graybox Probing: Conclusions 56/56

Gray Box Probing of GCC: Conclusions

• Source code is transformed into assembly by lowering the abstraction level step by step to bring it close to the machine

• This transformation can be understood to a large extent by observing inputs and output of the different steps in the transformation

• It is easy to prepare interesting test cases and observe the effect of transformations

• One optimization often leads to another

Hence GCC performs many optimizations repeatedly (eg. copy propagation, dead code elimination)