• No results found

CS 715: The Design and Implementation of Gnu Compiler Generation Framework

N/A
N/A
Protected

Academic year: 2022

Share "CS 715: The Design and Implementation of Gnu Compiler Generation Framework"

Copied!
195
0
0

Loading.... (view fulltext now)

Full text

(1)

CS 715: The Design and Implementation of Gnu Compiler Generation Framework

Uday Khedker

GCC Resource Center,

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

January 2011

(2)

CS 715 Gnu Compiler Collection: Outline 1/55

Outline

An Overview of Compilation

Introduction, compilation sequence, compilation models

GCC: The Great Compiler Challenge Difficulties in understanding GCC

Meeting the GCC Challenge: CS 715

The course plan

(3)

Part 1

Introduction to Compilation

(4)

CS 715 Gnu Compiler Collection: Introduction to Compilation 2/55

Binding

Time No.of

unbound objects

Nothing is known except the problem

(5)

CS 715 Gnu Compiler Collection: Introduction to Compilation 2/55

Binding

Time No.of

unbound objects

Conceptualisation

Overall strategy, algorithm, data structures etc.

Uday Khedker GRC, IIT Bombay

(6)

CS 715 Gnu Compiler Collection: Introduction to Compilation 2/55

Binding

Time No.of

unbound objects

Conceptualisation Coding

Functions, variables, their types etc.

(7)

CS 715 Gnu Compiler Collection: Introduction to Compilation 2/55

Binding

Time No.of

unbound objects

Conceptualisation Coding Compiling

Machine instructions, registers etc.

Uday Khedker GRC, IIT Bombay

(8)

CS 715 Gnu Compiler Collection: Introduction to Compilation 2/55

Binding

Time No.of

unbound objects

Conceptualisation Coding Compiling Linking

Addresses of functions, external data etc.

(9)

CS 715 Gnu Compiler Collection: Introduction to Compilation 2/55

Binding

Time No.of

unbound objects

Conceptualisation Coding Compiling Linking Loading

Actual addresses of code and data

Uday Khedker GRC, IIT Bombay

(10)

CS 715 Gnu Compiler Collection: Introduction to Compilation 2/55

Binding

Time No.of

unbound objects

Conceptualisation Coding Compiling Linking Loading Execution Values of variables

(11)

CS 715 Gnu Compiler Collection: Introduction to Compilation 3/55

Implementation Mechanisms

Source Program

Translator Target Program

Machine

Uday Khedker GRC, IIT Bombay

(12)

CS 715 Gnu Compiler Collection: Introduction to Compilation 3/55

Implementation Mechanisms

Source Program

Translator Target Program

Machine

Input Data

(13)

CS 715 Gnu Compiler Collection: Introduction to Compilation 3/55

Implementation Mechanisms

Source Program

Translator Target Program

Machine

Input Data

Source Program

Interpreter Machine

Uday Khedker GRC, IIT Bombay

(14)

CS 715 Gnu Compiler Collection: Introduction to Compilation 4/55

Implementation Mechanisms as “Bridges”

“Gap” between the “levels” of program specification and execution

Program Specification

Machine

(15)

CS 715 Gnu Compiler Collection: Introduction to Compilation 4/55

Implementation Mechanisms as “Bridges”

“Gap” between the “levels” of program specification and execution

Program Specification

Machine Translation

Uday Khedker GRC, IIT Bombay

(16)

CS 715 Gnu Compiler Collection: Introduction to Compilation 4/55

Implementation Mechanisms as “Bridges”

“Gap” between the “levels” of program specification and execution

Program Specification

Machine

Translation Interpretation

(17)

CS 715 Gnu Compiler Collection: Introduction to Compilation 4/55

Implementation Mechanisms as “Bridges”

“Gap” between the “levels” of program specification and execution

Program Specification

Machine

Translation Interpretation

State : Variables Operations: Expressions,

Control Flow

State : Memory, Registers Operations: Machine

Instructions

Uday Khedker GRC, IIT Bombay

(18)

CS 715 Gnu Compiler Collection: Introduction to Compilation 5/55

High and Low Level Abstractions

Input C statement a = b<10?b:c;

Spim Assembly Equivalent

lw $t0, 4($fp) ; t0 <- b # Is b smaller slti $t0, $t0, 10 ; t0 <- t0 < 10 # than 10?

not $t0, $t0 ; t0 <- !t0

bgtz $t0, L0: ; if t0>=0 goto L0 lw $t0, 4($fp) ; t0 <- b # YES

b L1: ; goto L1

L0: lw $t0, 8($fp) ;L0: t0 <- c # NO L1: sw 0($fp), $t0 ;L1: a <- t0

(19)

CS 715 Gnu Compiler Collection: Introduction to Compilation 5/55

High and Low Level Abstractions

Input C statement a = b<10?b:c;

Spim Assembly Equivalent

lw $t0, 4($fp) ; t0 <- b # Is b smaller slti $t0, $t0, 10 ; t0 <- t0 < 10 # than 10?

not $t0, $t0 ; t0 <- !t0

bgtz $t0, L0: ; if t0>=0 goto L0 lw $t0, 4($fp) ; t0 <- b # YES

b L1: ; goto L1

L0: lw $t0, 8($fp) ;L0: t0 <- c # NO L1: sw 0($fp), $t0 ;L1: a <- t0

Condition False Part True Part

Fall through Conditional jump

Uday Khedker GRC, IIT Bombay

(20)

CS 715 Gnu Compiler Collection: Introduction to Compilation 5/55

High and Low Level Abstractions

Input C statement a = b<10?b:c;

Spim Assembly Equivalent

lw $t0, 4($fp) ; t0 <- b # Is b smaller slti $t0, $t0, 10 ; t0 <- t0 < 10 # than 10?

not $t0, $t0 ; t0 <- !t0

bgtz $t0, L0: ; if t0>=0 goto L0 lw $t0, 4($fp) ; t0 <- b # YES

b L1: ; goto L1

L0: lw $t0, 8($fp) ;L0: t0 <- c # NO L1: sw 0($fp), $t0 ;L1: a <- t0

NOT Condition True Part False Part

(21)

CS 715 Gnu Compiler Collection: Introduction to Compilation 5/55

High and Low Level Abstractions

Input C statement a = b<10?b:c;

Spim Assembly Equivalent

lw $t0, 4($fp) ; t0 <- b # Is b smaller slti $t0, $t0, 10 ; t0 <- t0 < 10 # than 10?

not $t0, $t0 ; t0 <- !t0

bgtz $t0, L0: ; if t0>=0 goto L0 lw $t0, 4($fp) ; t0 <- b # YES

b L1: ; goto L1

L0: lw $t0, 8($fp) ;L0: t0 <- c # NO L1: sw 0($fp), $t0 ;L1: a <- t0

NOT Condition True Part False Part

Fall through Conditional jump

Uday Khedker GRC, IIT Bombay

(22)

CS 715 Gnu Compiler Collection: Introduction to Compilation 6/55

Implementation Mechanisms

Translation = Analysis + Synthesis

Interpretation = Analysis + Execution

(23)

CS 715 Gnu Compiler Collection: Introduction to Compilation 6/55

Implementation Mechanisms

Translation = Analysis + Synthesis Interpretation = Analysis + Execution

Translation Instructions Equivalent Instructions

Uday Khedker GRC, IIT Bombay

(24)

CS 715 Gnu Compiler Collection: Introduction to Compilation 6/55

Implementation Mechanisms

Translation = Analysis + Synthesis Interpretation = Analysis + Execution

Translation Instructions Equivalent Instructions

Interpretation Instructions Actions Implied

by Instructions

(25)

CS 715 Gnu Compiler Collection: Introduction to Compilation 7/55

Language Implementation Models

Analysis

Synthesis

Execution

Compilation

Interpretation

Uday Khedker GRC, IIT Bombay

(26)

CS 715 Gnu Compiler Collection: Introduction to Compilation 8/55

Language Processor Models

C,C

++

Java, C#

Front

End Optimizer

Back End

Virtual

Machine

(27)

CS 715 Gnu Compiler Collection: Introduction to Compilation 9/55

Typical Front Ends

Parser

Uday Khedker GRC, IIT Bombay

(28)

CS 715 Gnu Compiler Collection: Introduction to Compilation 9/55

Typical Front Ends

Parser Source

Program

Scanner

Tokens

(29)

CS 715 Gnu Compiler Collection: Introduction to Compilation 9/55

Typical Front Ends

Parser Source

Program

Scanner

Tokens

Semantic Analyzer AST

Parse Tree

AST or Linear IR Symbol Table+

Uday Khedker GRC, IIT Bombay

(30)

CS 715 Gnu Compiler Collection: Introduction to Compilation 9/55

Typical Front Ends

Parser Source

Program

Scanner

Tokens

Semantic Analyzer AST

Parse Tree

AST or Linear IR Symbol Table+

Error Handler Symtab

Handler

(31)

CS 715 Gnu Compiler Collection: Introduction to Compilation 10/55

Typical Back Ends

m/c Ind.

IR

m/c Ind.

Optimizer

Compile time evaluations

Eliminating redundant computations

m/c Ind.

IR

Uday Khedker GRC, IIT Bombay

(32)

CS 715 Gnu Compiler Collection: Introduction to Compilation 10/55

Typical Back Ends

m/c Ind.

IR

m/c Ind.

Optimizer

Compile time evaluations

Eliminating redundant computations

m/c Ind.

IR

Code Generator

Dep. m/c IR

Instruction Selection

Local Reg Allocation

Choice of Order of

Evaluation

(33)

CS 715 Gnu Compiler Collection: Introduction to Compilation 10/55

Typical Back Ends

m/c Ind.

IR

m/c Ind.

Optimizer

Compile time evaluations

Eliminating redundant computations

m/c Ind.

IR

Code Generator

Dep. m/c IR

Instruction Selection

Local Reg Allocation

Choice of Order of Evaluation

m/c Dep.

Optimizer

Assembly Code

Uday Khedker GRC, IIT Bombay

(34)

CS 715 Gnu Compiler Collection: Introduction to Compilation 10/55

Typical Back Ends

m/c Ind.

IR

m/c Ind.

Optimizer

Compile time evaluations

Eliminating redundant computations

m/c Ind.

IR

Code Generator

Dep. m/c IR

Instruction Selection

Local Reg Allocation

Choice of Order of Evaluation

Assembly Code Register

Allocator

Instruction Scheduler Peephole

Optimizer

(35)

Part 2

An Overview of Compilation Phases

(36)

CS 715 Gnu Compiler Collection: An Overview of Compilation Phases 11/55

The Structure of a Simple Compiler

Parser

Scanner Semantic Analyser

Symtab Handler Source Program

(37)

CS 715 Gnu Compiler Collection: An Overview of Compilation Phases 11/55

The Structure of a Simple Compiler

Parser

Scanner Semantic Analyser

Symtab Handler Source Program

Instruction Selector AST

Register Allocator

Assembly Emitter Insn

Assembly Program

Uday Khedker GRC, IIT Bombay

(38)

CS 715 Gnu Compiler Collection: An Overview of Compilation Phases 11/55

The Structure of a Simple Compiler

Parser

Scanner Semantic Analyser

Symtab Handler Source Program

Instruction Selector AST

Register Allocator

Assembly Emitter Insn

Assembly Program

Front End Back End

(39)

CS 715 Gnu Compiler Collection: An Overview of Compilation Phases 12/55

Translation Sequence in Our Compiler: Parsing

a=b<10?b:c;

Input

Uday Khedker GRC, IIT Bombay

(40)

CS 715 Gnu Compiler Collection: An Overview of Compilation Phases 12/55

Translation Sequence in Our Compiler: Parsing

a=b<10?b:c;

Input

AsgnStmnt

Lhs = E ;

E ? E : E

E < E name

name name

name num

Parse Tree Issues:

• Grammar rules, terminals, non-terminals

• Order of application of grammar rules eg. is it(a = b<10?) followed by(b:c)?

• Values of terminal symbols

eg. string “10” vs. integer number 10.

(41)

CS 715 Gnu Compiler Collection: An Overview of Compilation Phases 13/55

Translation Sequence in Our Compiler: Semantic Analysis

a=b<10?b:c;

Input

AsgnStmnt

Lhs = E ;

E ? E : E

E < E name

name name

name num

Parse Tree

Uday Khedker GRC, IIT Bombay

(42)

CS 715 Gnu Compiler Collection: An Overview of Compilation Phases 13/55

Translation Sequence in Our Compiler: Semantic Analysis

a=b<10?b:c;

Input

AsgnStmnt

Lhs = E ;

E ? E : E

E < E name

name name

name num

Parse Tree

= name

(a,int) ?: (int)

<

(bool) name (b,int)

name (c,int) name

(b,int) num (10,int) Abstract Syntax Tree

(with attributes) Issues:

• Symbol tables

Have variables been declared? What are their types?

What is their scope?

• Type consistency of operators and operands The result of computing b<10?is bool and not int

(43)

CS 715 Gnu Compiler Collection: An Overview of Compilation Phases 14/55

Translation Sequence in Our Compiler: IR Generation

a=b<10?b:c;

Input

AsgnStmnt

Lhs = E ;

E ? E : E

E < E name

name name

name num

Parse Tree

= name

(a,int) ?: (int)

<

(bool) name (b,int)

name (c,int) name

(b,int) num (10,int) Abstract Syntax Tree

(with attributes)

Uday Khedker GRC, IIT Bombay

(44)

CS 715 Gnu Compiler Collection: An Overview of Compilation Phases 14/55

Translation Sequence in Our Compiler: IR Generation

a=b<10?b:c;

Input

AsgnStmnt

Lhs = E ;

E ? E : E

E < E name

name name

name num

Parse Tree

= name

(a,int) ?: (int)

<

(bool) name (b,int)

name (c,int) name

(b,int) num (10,int) Abstract Syntax Tree

(with attributes)

= T0 <

b 10

IfGoto

Not L0:

T0

=

T1 b

Goto L1:

=

T1 c

L0:

= T1 a

L1:

Tree List

Issues:

• Convert to maximal trees which can be implemented without altering control flow Simplifies instruction selection and scheduling, register allocation etc.

• Linearise control flow by flattening nested control constructs

(45)

CS 715 Gnu Compiler Collection: An Overview of Compilation Phases 15/55

Translation Sequence in Our Compiler: Instruction Selection

a=b<10?b:c;

Input

AsgnStmnt

Lhs = E ;

E ? E : E

E < E name

name name

name num

Parse Tree

= name

(a,int) ?: (int)

<

(bool) name (b,int)

name (c,int) name

(b,int) num (10,int) Abstract Syntax Tree

(with attributes)

= T0 <

b 10

IfGoto

Not L0:

T0

=

T1 b

Goto L1:

=

T1 c

L0:

= T1 a

L1:

Tree List

Uday Khedker GRC, IIT Bombay

(46)

CS 715 Gnu Compiler Collection: An Overview of Compilation Phases 15/55

Translation Sequence in Our Compiler: Instruction Selection

a=b<10?b:c;

Input

AsgnStmnt

Lhs = E ;

E ? E : E

E < E name

name name

name num

Parse Tree

= name

(a,int) ?: (int)

<

(bool) name (b,int)

name (c,int) name

(b,int) num (10,int) Abstract Syntax Tree

(with attributes)

= T0 <

b 10

IfGoto

Not L0:

T0

=

T1 b

Goto L1:

=

T1 c

L0:

= T1 a

L1:

Tree List

T0 ←b T0 ← T0 <10 T0 ←!T0 ifT0 > 0 goto L0:

T1 ←b goto L1:

L0:T1 ←c L1: a← T1

Instruction List Issues:

• Cover trees with as few machine instructions as possible

• Use temporaries and local registers

(47)

CS 715 Gnu Compiler Collection: An Overview of Compilation Phases 16/55

Translation Sequence in Our Compiler: Emitting Instructions

a=b<10?b:c;

Input

AsgnStmnt

Lhs = E ;

E ? E : E

E < E name

name name

name num

Parse Tree

= name

(a,int) ?: (int)

<

(bool) name (b,int)

name (c,int) name

(b,int) num (10,int) Abstract Syntax Tree

(with attributes)

= T0 <

b 10

IfGoto

Not L0:

T0

=

T1 b

Goto L1:

=

T1 c

L0:

= T1 a

L1:

Tree List

T0 ←b T0 ← T0 <10 T0 ←!T0 ifT0 > 0 goto L0:

T1 ←b goto L1:

L0:T1 ←c L1: a← T1

Instruction List

Uday Khedker GRC, IIT Bombay

(48)

CS 715 Gnu Compiler Collection: An Overview of Compilation Phases 16/55

Translation Sequence in Our Compiler: Emitting Instructions

a=b<10?b:c;

Input

AsgnStmnt

Lhs = E ;

E ? E : E

E < E name

name name

name num

Parse Tree

= name

(a,int) ?: (int)

<

(bool) name (b,int)

name (c,int) name

(b,int) num (10,int) Abstract Syntax Tree

(with attributes)

= T0 <

b 10

IfGoto

Not L0:

T0

=

T1 b

Goto L1:

=

T1 c

L0:

= T1 a

L1:

Tree List

T0 ←b T0 ← T0 <10 T0 ←!T0 ifT0 > 0 goto L0:

T1 ←b goto L1:

L0:T1 ←c L1: a← T1

Instruction List

lw $t0, 4($fp) slti $t0, $t0, 10 not $t0, $t0 bgtz $t0, L0:

lw $t0, 4($fp) b L1:

L0: lw $t0, 8($fp) L1: sw 0($fp), $t0 Assembly Code Issues:

• Offsets of variables in the stack frame

• Actual register numbers and assembly mnemonics

• Code to construct and discard activation records

(49)

Part 3

Compilation Models, Instruction Selection, and

Retargetability

(50)

CS 715Gnu Compiler Collection: Compilation Models, Instruction Selection, and Retargetability 17/55

Compilation Models

Aho Ullman Model

Davidson Fraser Model

(51)

CS 715Gnu Compiler Collection: Compilation Models, Instruction Selection, and Retargetability 17/55

Compilation Models

Aho Ullman Model

Davidson Fraser Model Input Source Program

Front End AST

Uday Khedker GRC, IIT Bombay

(52)

CS 715Gnu Compiler Collection: Compilation Models, Instruction Selection, and Retargetability 17/55

Compilation Models

Aho Ullman Model

Davidson Fraser Model Input Source Program

Front End AST Optimizer m/c indep. IR

(53)

CS 715Gnu Compiler Collection: Compilation Models, Instruction Selection, and Retargetability 17/55

Compilation Models

Aho Ullman Model

Davidson Fraser Model Input Source Program

Front End AST Optimizer m/c indep. IR

Code Generator Target Program

Uday Khedker GRC, IIT Bombay

(54)

CS 715Gnu Compiler Collection: Compilation Models, Instruction Selection, and Retargetability 17/55

Compilation Models

Aho Ullman Model

Davidson Fraser Model Input Source Program

Front End AST Optimizer m/c indep. IR

Code Generator Target Program

Front End AST

(55)

CS 715Gnu Compiler Collection: Compilation Models, Instruction Selection, and Retargetability 17/55

Compilation Models

Aho Ullman Model

Davidson Fraser Model Input Source Program

Front End AST Optimizer m/c indep. IR

Code Generator Target Program

Front End AST Expander register transfers

Uday Khedker GRC, IIT Bombay

(56)

CS 715Gnu Compiler Collection: Compilation Models, Instruction Selection, and Retargetability 17/55

Compilation Models

Aho Ullman Model

Davidson Fraser Model Input Source Program

Front End AST Optimizer m/c indep. IR

Code Generator Target Program

Front End AST Expander register transfers

Optimizer register transfers

(57)

CS 715Gnu Compiler Collection: Compilation Models, Instruction Selection, and Retargetability 17/55

Compilation Models

Aho Ullman Model

Davidson Fraser Model Input Source Program

Front End AST Optimizer m/c indep. IR

Code Generator Target Program

Front End AST Expander register transfers

Optimizer register transfers

Recognizer Target Program

Uday Khedker GRC, IIT Bombay

(58)

CS 715Gnu Compiler Collection: Compilation Models, Instruction Selection, and Retargetability 17/55

Compilation Models

Aho Ullman Model

Davidson Fraser Model

Front End AST Optimizer m/c indep. IR

Code Generator Target Program

Front End AST Expander register transfers

Optimizer register transfers

Recognizer Target Program Aho Ullman: Instruction selection

• over optimized IR using

• intelligent tree tiling based algorithms

Davidson Fraser: Instruction selection

• over AST using

• simple full tree matching based algorithms that generate

• naive code which is

machine dependent, and is

optimized subsequently

(59)

CS 715Gnu Compiler Collection: Compilation Models, Instruction Selection, and Retargetability 18/55

Retargetability in Aho Ullman Model

Front End AST Optimizer m/c indep. IR

Code Generator Target Program

Instruction selection

over optimized IR using

intelligent tree tiling based algorithms Key idea in retargetability:

Machine independent IR is expressed in the form of trees

Machine instructions are described in the form of trees

Trees in the IR are tiled using the instruction trees

Uday Khedker GRC, IIT Bombay

(60)

CS 715Gnu Compiler Collection: Compilation Models, Instruction Selection, and Retargetability 19/55

Retargetability in Davidson Fraser Model

Front End AST Expander register transfers

Optimizer register transfers

Recognizer Target Program

Instruction selection

over AST using

simple full tree matching based algorithms that generate

naive code which is

machine dependent, and is

optimized subsequently

Key idea in retargetability:

Register transfers are machine specific but

their form is machine independent

(61)

CS 715Gnu Compiler Collection: Compilation Models, Instruction Selection, and Retargetability 20/55

Full Tree Matching (Davidson Fraser Model)

Instructions are viewed as independent non-composable rules

Machine Instructions Subject Tree (IR) Modified Trees

=

reg +

reg reg

=

reg

reg reg

Uday Khedker GRC, IIT Bombay

(62)

CS 715Gnu Compiler Collection: Compilation Models, Instruction Selection, and Retargetability 20/55

Full Tree Matching (Davidson Fraser Model)

Instructions are viewed as independent non-composable rules

Machine Instructions Subject Tree (IR) Modified Trees

=

reg +

reg reg

=

reg

reg reg

=

a

+

a ∗

b c

(63)

CS 715Gnu Compiler Collection: Compilation Models, Instruction Selection, and Retargetability 20/55

Full Tree Matching (Davidson Fraser Model)

Instructions are viewed as independent non-composable rules

Machine Instructions Subject Tree (IR) Modified Trees

=

reg +

reg reg

=

reg

reg reg

=

a

+

a ∗

b c

Uday Khedker GRC, IIT Bombay

(64)

CS 715Gnu Compiler Collection: Compilation Models, Instruction Selection, and Retargetability 20/55

Full Tree Matching (Davidson Fraser Model)

Instructions are viewed as independent non-composable rules

Machine Instructions Subject Tree (IR) Modified Trees

=

reg +

reg reg

=

reg

reg reg

=

a

+

a ∗

b c

=

t ∗

b c

=

a

+

a t

(65)

CS 715Gnu Compiler Collection: Compilation Models, Instruction Selection, and Retargetability 20/55

Full Tree Matching (Davidson Fraser Model)

Instructions are viewed as independent non-composable rules

Machine Instructions Subject Tree (IR) Modified Trees

=

reg +

reg reg

=

reg

reg reg

=

a

+

a ∗

b c

=

t ∗

b c

=

a

+

a t

Uday Khedker GRC, IIT Bombay

(66)

CS 715Gnu Compiler Collection: Compilation Models, Instruction Selection, and Retargetability 20/55

Full Tree Matching (Davidson Fraser Model)

Instructions are viewed as independent non-composable rules

Machine Instructions Subject Tree (IR) Modified Trees

=

reg +

reg reg

=

reg

reg reg

=

a

+

a ∗

b c

=

t ∗

b c

=

a

+

a t

(67)

CS 715Gnu Compiler Collection: Compilation Models, Instruction Selection, and Retargetability 21/55

Tree Tiling (Aho Ullman Model) Instructions are viewed as composable rules

Machine Instructions Subject Tree (IR)

=

reg Reg

reg +

Reg Reg

Reg Reg

Uday Khedker GRC, IIT Bombay

(68)

CS 715Gnu Compiler Collection: Compilation Models, Instruction Selection, and Retargetability 21/55

Tree Tiling (Aho Ullman Model) Instructions are viewed as composable rules

Machine Instructions Subject Tree (IR)

=

reg Reg

Reg reg

+

Reg Reg

Reg

Reg Reg

Reg

(69)

CS 715Gnu Compiler Collection: Compilation Models, Instruction Selection, and Retargetability 21/55

Tree Tiling (Aho Ullman Model) Instructions are viewed as composable rules

Machine Instructions Subject Tree (IR)

=

reg Reg

Reg reg

+

Reg Reg

Reg

Reg Reg

Reg

=

a

+

a ∗

b c

Uday Khedker GRC, IIT Bombay

(70)

CS 715Gnu Compiler Collection: Compilation Models, Instruction Selection, and Retargetability 21/55

Tree Tiling (Aho Ullman Model) Instructions are viewed as composable rules

Machine Instructions Subject Tree (IR)

=

reg Reg

Reg reg

+

Reg Reg

Reg

Reg Reg

Reg

=

a

+

a ∗

b c

(71)

CS 715Gnu Compiler Collection: Compilation Models, Instruction Selection, and Retargetability 21/55

Tree Tiling (Aho Ullman Model) Instructions are viewed as composable rules

Machine Instructions Subject Tree (IR)

=

reg Reg

Reg reg

+

Reg Reg

Reg

Reg Reg

Reg

=

a

+

Reg

Reg Reg

Uday Khedker GRC, IIT Bombay

(72)

CS 715Gnu Compiler Collection: Compilation Models, Instruction Selection, and Retargetability 21/55

Tree Tiling (Aho Ullman Model) Instructions are viewed as composable rules

Machine Instructions Subject Tree (IR)

=

reg Reg

Reg reg

+

Reg Reg

Reg

Reg Reg

Reg

=

a

+

Reg

Reg Reg

(73)

CS 715Gnu Compiler Collection: Compilation Models, Instruction Selection, and Retargetability 21/55

Tree Tiling (Aho Ullman Model) Instructions are viewed as composable rules

Machine Instructions Subject Tree (IR)

=

reg Reg

Reg reg

+

Reg Reg

Reg

Reg Reg

Reg

=

a

+

Reg Reg

Uday Khedker GRC, IIT Bombay

(74)

CS 715Gnu Compiler Collection: Compilation Models, Instruction Selection, and Retargetability 21/55

Tree Tiling (Aho Ullman Model) Instructions are viewed as composable rules

Machine Instructions Subject Tree (IR)

=

reg Reg

Reg reg

+

Reg Reg

Reg

Reg Reg

Reg

=

a

+

Reg Reg

(75)

CS 715Gnu Compiler Collection: Compilation Models, Instruction Selection, and Retargetability 21/55

Tree Tiling (Aho Ullman Model) Instructions are viewed as composable rules

Machine Instructions Subject Tree (IR)

=

reg Reg

Reg reg

+

Reg Reg

Reg

Reg Reg

Reg

=

a

Reg

Uday Khedker GRC, IIT Bombay

(76)

CS 715Gnu Compiler Collection: Compilation Models, Instruction Selection, and Retargetability 21/55

Tree Tiling (Aho Ullman Model) Instructions are viewed as composable rules

Machine Instructions Subject Tree (IR)

=

reg Reg

Reg reg

+

Reg Reg

Reg

Reg Reg

Reg

=

a

Reg

(77)

Part 4

GCC ≡ The Great Compiler Challenge

(78)

CS 715 Gnu Compiler Collection: GCCThe Great Compiler Challenge 22/55

The Gnu Tool Chain

gcc Source Program

Target Program

(79)

CS 715 Gnu Compiler Collection: GCCThe Great Compiler Challenge 22/55

The Gnu Tool Chain

gcc Source Program

Target Program

cc1

cpp

Uday Khedker GRC, IIT Bombay

(80)

CS 715 Gnu Compiler Collection: GCCThe Great Compiler Challenge 22/55

The Gnu Tool Chain

gcc Source Program

Target Program

cc1 cpp

(81)

CS 715 Gnu Compiler Collection: GCCThe Great Compiler Challenge 22/55

The Gnu Tool Chain

gcc Source Program

Target Program

cc1 cpp

as

Uday Khedker GRC, IIT Bombay

(82)

CS 715 Gnu Compiler Collection: GCCThe Great Compiler Challenge 22/55

The Gnu Tool Chain

gcc Source Program

Target Program

cc1 cpp

as

ld

(83)

CS 715 Gnu Compiler Collection: GCCThe Great Compiler Challenge 22/55

The Gnu Tool Chain

gcc Source Program

Target Program

cc1 cpp

as

ld

glibc/newlib

Uday Khedker GRC, IIT Bombay

(84)

CS 715 Gnu Compiler Collection: GCCThe Great Compiler Challenge 22/55

The Gnu Tool Chain

gcc Source Program

Target Program

cc1 cpp

as

ld

glibc/newlib

GCC

(85)

CS 715 Gnu Compiler Collection: GCCThe Great Compiler Challenge 23/55

Why is Understanding GCC Difficult?

Some of the obvious reasons:

Comprehensiveness

GCC is a production quality framework in terms of completeness and practical usefulness

Open development model

Could lead to heterogeneity. Design flaws may be difficult to correct

Rapid versioning

GCC maintenance is a race against time. Disruptive corrections are difficult

Uday Khedker GRC, IIT Bombay

(86)

CS 715 Gnu Compiler Collection: GCCThe Great Compiler Challenge 24/55

Why is Understanding GCC Difficult?

Deeper technical reasons:

GCC is not a compiler but acompiler generation framework Two distinct gaps that need to be bridged:

Input-output of the generation framework

Input-output of the generated compiler

GCC generated compiler uses a derivative of the Davidson-Fraser model of compilation

Early instruction selection

Machine dependent intermediate representation

Simplistic instruction selection and retargatibility mechanism

(87)

CS 715 Gnu Compiler Collection: GCCThe Great Compiler Challenge 25/55

Comprehensiveness of GCC: Wide Applicability

Input languages supported:

C, C++, Objective-C, Objective-C++, Java, Fortran, and Ada

Processors supported in standard releases:

Uday Khedker GRC, IIT Bombay

(88)

CS 715 Gnu Compiler Collection: GCCThe Great Compiler Challenge 25/55

Comprehensiveness of GCC: Wide Applicability

Input languages supported:

C, C++, Objective-C, Objective-C++, Java, Fortran, and Ada

Processors supported in standard releases:

Common processors:

Lesser-known target processors:

Additional processors independently supported:

(89)

CS 715 Gnu Compiler Collection: GCCThe Great Compiler Challenge 25/55

Comprehensiveness of GCC: Wide Applicability

Input languages supported:

C, C++, Objective-C, Objective-C++, Java, Fortran, and Ada

Processors supported in standard releases:

Common processors:

Alpha,

Lesser-known target processors:

Additional processors independently supported:

Uday Khedker GRC, IIT Bombay

(90)

CS 715 Gnu Compiler Collection: GCCThe Great Compiler Challenge 25/55

Comprehensiveness of GCC: Wide Applicability

Input languages supported:

C, C++, Objective-C, Objective-C++, Java, Fortran, and Ada

Processors supported in standard releases:

Common processors:

Alpha, ARM,

Lesser-known target processors:

Additional processors independently supported:

(91)

CS 715 Gnu Compiler Collection: GCCThe Great Compiler Challenge 25/55

Comprehensiveness of GCC: Wide Applicability

Input languages supported:

C, C++, Objective-C, Objective-C++, Java, Fortran, and Ada

Processors supported in standard releases:

Common processors:

Alpha, ARM, Atmel AVR,

Lesser-known target processors:

Additional processors independently supported:

Uday Khedker GRC, IIT Bombay

(92)

CS 715 Gnu Compiler Collection: GCCThe Great Compiler Challenge 25/55

Comprehensiveness of GCC: Wide Applicability

Input languages supported:

C, C++, Objective-C, Objective-C++, Java, Fortran, and Ada

Processors supported in standard releases:

Common processors:

Alpha, ARM, Atmel AVR, Blackfin,

Lesser-known target processors:

Additional processors independently supported:

(93)

CS 715 Gnu Compiler Collection: GCCThe Great Compiler Challenge 25/55

Comprehensiveness of GCC: Wide Applicability

Input languages supported:

C, C++, Objective-C, Objective-C++, Java, Fortran, and Ada

Processors supported in standard releases:

Common processors:

Alpha, ARM, Atmel AVR, Blackfin, HC12,

Lesser-known target processors:

Additional processors independently supported:

Uday Khedker GRC, IIT Bombay

(94)

CS 715 Gnu Compiler Collection: GCCThe Great Compiler Challenge 25/55

Comprehensiveness of GCC: Wide Applicability

Input languages supported:

C, C++, Objective-C, Objective-C++, Java, Fortran, and Ada

Processors supported in standard releases:

Common processors:

Alpha, ARM, Atmel AVR, Blackfin, HC12, H8/300,

Lesser-known target processors:

Additional processors independently supported:

(95)

CS 715 Gnu Compiler Collection: GCCThe Great Compiler Challenge 25/55

Comprehensiveness of GCC: Wide Applicability

Input languages supported:

C, C++, Objective-C, Objective-C++, Java, Fortran, and Ada

Processors supported in standard releases:

Common processors:

Alpha, ARM, Atmel AVR, Blackfin, HC12, H8/300, IA-32 (x86),

Lesser-known target processors:

Additional processors independently supported:

Uday Khedker GRC, IIT Bombay

(96)

CS 715 Gnu Compiler Collection: GCCThe Great Compiler Challenge 25/55

Comprehensiveness of GCC: Wide Applicability

Input languages supported:

C, C++, Objective-C, Objective-C++, Java, Fortran, and Ada

Processors supported in standard releases:

Common processors:

Alpha, ARM, Atmel AVR, Blackfin, HC12, H8/300, IA-32 (x86), x86-64,

Lesser-known target processors:

Additional processors independently supported:

(97)

CS 715 Gnu Compiler Collection: GCCThe Great Compiler Challenge 25/55

Comprehensiveness of GCC: Wide Applicability

Input languages supported:

C, C++, Objective-C, Objective-C++, Java, Fortran, and Ada

Processors supported in standard releases:

Common processors:

Alpha, ARM, Atmel AVR, Blackfin, HC12, H8/300, IA-32 (x86), x86-64, IA-64,

Lesser-known target processors:

Additional processors independently supported:

Uday Khedker GRC, IIT Bombay

(98)

CS 715 Gnu Compiler Collection: GCCThe Great Compiler Challenge 25/55

Comprehensiveness of GCC: Wide Applicability

Input languages supported:

C, C++, Objective-C, Objective-C++, Java, Fortran, and Ada

Processors supported in standard releases:

Common processors:

Alpha, ARM, Atmel AVR, Blackfin, HC12, H8/300, IA-32 (x86), x86-64, IA-64, Motorola 68000,

Lesser-known target processors:

Additional processors independently supported:

(99)

CS 715 Gnu Compiler Collection: GCCThe Great Compiler Challenge 25/55

Comprehensiveness of GCC: Wide Applicability

Input languages supported:

C, C++, Objective-C, Objective-C++, Java, Fortran, and Ada

Processors supported in standard releases:

Common processors:

Alpha, ARM, Atmel AVR, Blackfin, HC12, H8/300, IA-32 (x86), x86-64, IA-64, Motorola 68000, MIPS,

Lesser-known target processors:

Additional processors independently supported:

Uday Khedker GRC, IIT Bombay

(100)

CS 715 Gnu Compiler Collection: GCCThe Great Compiler Challenge 25/55

Comprehensiveness of GCC: Wide Applicability

Input languages supported:

C, C++, Objective-C, Objective-C++, Java, Fortran, and Ada

Processors supported in standard releases:

Common processors:

Alpha, ARM, Atmel AVR, Blackfin, HC12, H8/300, IA-32 (x86), x86-64, IA-64, Motorola 68000, MIPS, PA-RISC,

Lesser-known target processors:

Additional processors independently supported:

(101)

CS 715 Gnu Compiler Collection: GCCThe Great Compiler Challenge 25/55

Comprehensiveness of GCC: Wide Applicability

Input languages supported:

C, C++, Objective-C, Objective-C++, Java, Fortran, and Ada

Processors supported in standard releases:

Common processors:

Alpha, ARM, Atmel AVR, Blackfin, HC12, H8/300, IA-32 (x86), x86-64, IA-64, Motorola 68000, MIPS, PA-RISC, PDP-11,

Lesser-known target processors:

Additional processors independently supported:

Uday Khedker GRC, IIT Bombay

(102)

CS 715 Gnu Compiler Collection: GCCThe Great Compiler Challenge 25/55

Comprehensiveness of GCC: Wide Applicability

Input languages supported:

C, C++, Objective-C, Objective-C++, Java, Fortran, and Ada

Processors supported in standard releases:

Common processors:

Alpha, ARM, Atmel AVR, Blackfin, HC12, H8/300, IA-32 (x86), x86-64, IA-64, Motorola 68000, MIPS, PA-RISC, PDP-11, PowerPC,

Lesser-known target processors:

Additional processors independently supported:

(103)

CS 715 Gnu Compiler Collection: GCCThe Great Compiler Challenge 25/55

Comprehensiveness of GCC: Wide Applicability

Input languages supported:

C, C++, Objective-C, Objective-C++, Java, Fortran, and Ada

Processors supported in standard releases:

Common processors:

Alpha, ARM, Atmel AVR, Blackfin, HC12, H8/300, IA-32 (x86), x86-64, IA-64, Motorola 68000, MIPS, PA-RISC, PDP-11, PowerPC, R8C/M16C/M32C,

Lesser-known target processors:

Additional processors independently supported:

Uday Khedker GRC, IIT Bombay

(104)

CS 715 Gnu Compiler Collection: GCCThe Great Compiler Challenge 25/55

Comprehensiveness of GCC: Wide Applicability

Input languages supported:

C, C++, Objective-C, Objective-C++, Java, Fortran, and Ada

Processors supported in standard releases:

Common processors:

Alpha, ARM, Atmel AVR, Blackfin, HC12, H8/300, IA-32 (x86), x86-64, IA-64, Motorola 68000, MIPS, PA-RISC, PDP-11, PowerPC, R8C/M16C/M32C, SPU,

Lesser-known target processors:

Additional processors independently supported:

(105)

CS 715 Gnu Compiler Collection: GCCThe Great Compiler Challenge 25/55

Comprehensiveness of GCC: Wide Applicability

Input languages supported:

C, C++, Objective-C, Objective-C++, Java, Fortran, and Ada

Processors supported in standard releases:

Common processors:

Alpha, ARM, Atmel AVR, Blackfin, HC12, H8/300, IA-32 (x86), x86-64, IA-64, Motorola 68000, MIPS, PA-RISC, PDP-11, PowerPC, R8C/M16C/M32C, SPU,

System/390/zSeries,

Lesser-known target processors:

Additional processors independently supported:

Uday Khedker GRC, IIT Bombay

(106)

CS 715 Gnu Compiler Collection: GCCThe Great Compiler Challenge 25/55

Comprehensiveness of GCC: Wide Applicability

Input languages supported:

C, C++, Objective-C, Objective-C++, Java, Fortran, and Ada

Processors supported in standard releases:

Common processors:

Alpha, ARM, Atmel AVR, Blackfin, HC12, H8/300, IA-32 (x86), x86-64, IA-64, Motorola 68000, MIPS, PA-RISC, PDP-11, PowerPC, R8C/M16C/M32C, SPU,

System/390/zSeries, SuperH,

Lesser-known target processors:

Additional processors independently supported:

(107)

CS 715 Gnu Compiler Collection: GCCThe Great Compiler Challenge 25/55

Comprehensiveness of GCC: Wide Applicability

Input languages supported:

C, C++, Objective-C, Objective-C++, Java, Fortran, and Ada

Processors supported in standard releases:

Common processors:

Alpha, ARM, Atmel AVR, Blackfin, HC12, H8/300, IA-32 (x86), x86-64, IA-64, Motorola 68000, MIPS, PA-RISC, PDP-11, PowerPC, R8C/M16C/M32C, SPU,

System/390/zSeries, SuperH, SPARC,

Lesser-known target processors:

Additional processors independently supported:

Uday Khedker GRC, IIT Bombay

(108)

CS 715 Gnu Compiler Collection: GCCThe Great Compiler Challenge 25/55

Comprehensiveness of GCC: Wide Applicability

Input languages supported:

C, C++, Objective-C, Objective-C++, Java, Fortran, and Ada

Processors supported in standard releases:

Common processors:

Alpha, ARM, Atmel AVR, Blackfin, HC12, H8/300, IA-32 (x86), x86-64, IA-64, Motorola 68000, MIPS, PA-RISC, PDP-11, PowerPC, R8C/M16C/M32C, SPU,

System/390/zSeries, SuperH, SPARC, VAX

Lesser-known target processors:

Additional processors independently supported:

(109)

CS 715 Gnu Compiler Collection: GCCThe Great Compiler Challenge 25/55

Comprehensiveness of GCC: Wide Applicability

Input languages supported:

C, C++, Objective-C, Objective-C++, Java, Fortran, and Ada

Processors supported in standard releases:

Common processors:

Alpha, ARM, Atmel AVR, Blackfin, HC12, H8/300, IA-32 (x86), x86-64, IA-64, Motorola 68000, MIPS, PA-RISC, PDP-11, PowerPC, R8C/M16C/M32C, SPU,

System/390/zSeries, SuperH, SPARC, VAX

Lesser-known target processors:

A29K,

Additional processors independently supported:

Uday Khedker GRC, IIT Bombay

(110)

CS 715 Gnu Compiler Collection: GCCThe Great Compiler Challenge 25/55

Comprehensiveness of GCC: Wide Applicability

Input languages supported:

C, C++, Objective-C, Objective-C++, Java, Fortran, and Ada

Processors supported in standard releases:

Common processors:

Alpha, ARM, Atmel AVR, Blackfin, HC12, H8/300, IA-32 (x86), x86-64, IA-64, Motorola 68000, MIPS, PA-RISC, PDP-11, PowerPC, R8C/M16C/M32C, SPU,

System/390/zSeries, SuperH, SPARC, VAX

Lesser-known target processors:

A29K, ARC,

Additional processors independently supported:

(111)

CS 715 Gnu Compiler Collection: GCCThe Great Compiler Challenge 25/55

Comprehensiveness of GCC: Wide Applicability

Input languages supported:

C, C++, Objective-C, Objective-C++, Java, Fortran, and Ada

Processors supported in standard releases:

Common processors:

Alpha, ARM, Atmel AVR, Blackfin, HC12, H8/300, IA-32 (x86), x86-64, IA-64, Motorola 68000, MIPS, PA-RISC, PDP-11, PowerPC, R8C/M16C/M32C, SPU,

System/390/zSeries, SuperH, SPARC, VAX

Lesser-known target processors:

A29K, ARC, ETRAX CRIS,

Additional processors independently supported:

Uday Khedker GRC, IIT Bombay

(112)

CS 715 Gnu Compiler Collection: GCCThe Great Compiler Challenge 25/55

Comprehensiveness of GCC: Wide Applicability

Input languages supported:

C, C++, Objective-C, Objective-C++, Java, Fortran, and Ada

Processors supported in standard releases:

Common processors:

Alpha, ARM, Atmel AVR, Blackfin, HC12, H8/300, IA-32 (x86), x86-64, IA-64, Motorola 68000, MIPS, PA-RISC, PDP-11, PowerPC, R8C/M16C/M32C, SPU,

System/390/zSeries, SuperH, SPARC, VAX

Lesser-known target processors:

A29K, ARC, ETRAX CRIS, D30V,

Additional processors independently supported:

(113)

CS 715 Gnu Compiler Collection: GCCThe Great Compiler Challenge 25/55

Comprehensiveness of GCC: Wide Applicability

Input languages supported:

C, C++, Objective-C, Objective-C++, Java, Fortran, and Ada

Processors supported in standard releases:

Common processors:

Alpha, ARM, Atmel AVR, Blackfin, HC12, H8/300, IA-32 (x86), x86-64, IA-64, Motorola 68000, MIPS, PA-RISC, PDP-11, PowerPC, R8C/M16C/M32C, SPU,

System/390/zSeries, SuperH, SPARC, VAX

Lesser-known target processors:

A29K, ARC, ETRAX CRIS, D30V, DSP16xx,

Additional processors independently supported:

Uday Khedker GRC, IIT Bombay

(114)

CS 715 Gnu Compiler Collection: GCCThe Great Compiler Challenge 25/55

Comprehensiveness of GCC: Wide Applicability

Input languages supported:

C, C++, Objective-C, Objective-C++, Java, Fortran, and Ada

Processors supported in standard releases:

Common processors:

Alpha, ARM, Atmel AVR, Blackfin, HC12, H8/300, IA-32 (x86), x86-64, IA-64, Motorola 68000, MIPS, PA-RISC, PDP-11, PowerPC, R8C/M16C/M32C, SPU,

System/390/zSeries, SuperH, SPARC, VAX

Lesser-known target processors:

A29K, ARC, ETRAX CRIS, D30V, DSP16xx, FR-30,

Additional processors independently supported:

(115)

CS 715 Gnu Compiler Collection: GCCThe Great Compiler Challenge 25/55

Comprehensiveness of GCC: Wide Applicability

Input languages supported:

C, C++, Objective-C, Objective-C++, Java, Fortran, and Ada

Processors supported in standard releases:

Common processors:

Alpha, ARM, Atmel AVR, Blackfin, HC12, H8/300, IA-32 (x86), x86-64, IA-64, Motorola 68000, MIPS, PA-RISC, PDP-11, PowerPC, R8C/M16C/M32C, SPU,

System/390/zSeries, SuperH, SPARC, VAX

Lesser-known target processors:

A29K, ARC, ETRAX CRIS, D30V, DSP16xx, FR-30, FR-V,

Additional processors independently supported:

Uday Khedker GRC, IIT Bombay

(116)

CS 715 Gnu Compiler Collection: GCCThe Great Compiler Challenge 25/55

Comprehensiveness of GCC: Wide Applicability

Input languages supported:

C, C++, Objective-C, Objective-C++, Java, Fortran, and Ada

Processors supported in standard releases:

Common processors:

Alpha, ARM, Atmel AVR, Blackfin, HC12, H8/300, IA-32 (x86), x86-64, IA-64, Motorola 68000, MIPS, PA-RISC, PDP-11, PowerPC, R8C/M16C/M32C, SPU,

System/390/zSeries, SuperH, SPARC, VAX

Lesser-known target processors:

A29K, ARC, ETRAX CRIS, D30V, DSP16xx, FR-30, FR-V, Intel i960,

Additional processors independently supported:

(117)

CS 715 Gnu Compiler Collection: GCCThe Great Compiler Challenge 25/55

Comprehensiveness of GCC: Wide Applicability

Input languages supported:

C, C++, Objective-C, Objective-C++, Java, Fortran, and Ada

Processors supported in standard releases:

Common processors:

Alpha, ARM, Atmel AVR, Blackfin, HC12, H8/300, IA-32 (x86), x86-64, IA-64, Motorola 68000, MIPS, PA-RISC, PDP-11, PowerPC, R8C/M16C/M32C, SPU,

System/390/zSeries, SuperH, SPARC, VAX

Lesser-known target processors:

A29K, ARC, ETRAX CRIS, D30V, DSP16xx, FR-30, FR-V, Intel i960, IP2000,

Additional processors independently supported:

Uday Khedker GRC, IIT Bombay

References

Related documents

IITKgp Improving GCC: Improving Machine Descriptions and Instruction Selection 47/54. Tree Tiling Instructions are viewed as

Optimizer Expander Optimizer Recognizer Generated Compiler (cc1). Source Program

15. On 13 October 2008 CEHRD issued a press statement calling upon the Defendant to mobilise its counter spill personnel to the Bodo creek as a matter of urgency. The

This chap- ter’s original analysis of the drivers of foreign military interventions in intrastate conflicts finds that geopolitical considerations (for example, sup- port on

Failing to address climate change impacts can undermine progress towards most SDGs (Le Blanc 2015). Many activities not only declare mitigation targets but also cite the importance

The necessary set of data includes a panel of country-level exports from Sub-Saharan African countries to the United States; a set of macroeconomic variables that would

Percentage of countries with DRR integrated in climate change adaptation frameworks, mechanisms and processes Disaster risk reduction is an integral objective of

The Congo has ratified CITES and other international conventions relevant to shark conservation and management, notably the Convention on the Conservation of Migratory