COINS..

Size: px

Start display at page:

Download "COINS.."

きのこひきぎ
7 years ago
Views:

1 ( ) 18

2 COINS LIR COINS CoVis trace2html html javascript COINS LIR Appel

3 COINS XML

4 2.1 COINS Module FlowGraph instrlist SSA CoVis trace2html Appel Appel

5 1 1.1 COINS [4] 1.2 COINS COINS 1 COINS CoVis trace2html 2 CoVis LIR trace2html LIR trace2html COINS LIR SSA LIR SSA LIR 2 SSA LIR COINS 1 LIR 4

6 1.3 COINS SSA trace2html LIR lir2c 2 LIR lir2c 3 COINS LIR lir2c lir2c COINS DOT Graphviz [2] trace2html trace2html html javascript 2 LIR C 5

7 2 COINS SSA 2.1 COINS (compiler infra structure, COINS) COINS 2000 [4] COINS SSA SSA [6, 7, 9, 15] COINS COINS COINS (front end) (back end) (source program) (intermediate code) (machine code) (lexical analyzer) (syntax analyzer) (semantic analyzer) (optimizer) (code generator) COINS 2 ( 2.1) (high-level intermediate representation, HIR) 1 (low-level intermediate representation, LIR) 2 1 HIR 2 LIR 6

2.1: COINS 2.1.3 LIR LIR [10, 13] LIR Module Module 2.2 2.

8 2.1: COINS LIR LIR [10, 13] LIR Module Module Module globalsymtab Function Function localsymtab FlowGraph FlowGraph FlowGraph BasicBlk BasicBlk predlist succlist instrlist instrlist instrlist LirNode LIR LirNode LirNode 7

9 2.2: Module 8

10 2.3: FlowGraph 9

11 2.4: instrlist 10

12 LirIconst: int LirFconst: double LirSymRef: LirLabelRef: LirUnaOp: LirBinOp: LirNaryOp:

13 0: 1: a=1 b=1 c=1 if(...) 2: c=c+1 if(...) 3: b=b+3 4: b=b+2 5: a=b 6: a=b+c 7: b=1 if(...) 8: b=b+2 c=c+1 9: if(...) 10: a=a+3 if(...) 11: 2.5: 12

14 2.1 ( ) (statement) (basic block) 2.2 ( ) (control flow graph) (basic block) (node) (directed edge) 2.3 ( ) X Y X Y (edge) 2.4 ( ) X 0, X 1,..., X i (i 0) e 1 : X 0 X 1, e 2 : X 1 X 2,..., e i : X i 1 X i (i 0) X 0 X i (path) 2.5 ( ) X Y X Y (predecessor block) X pred(x) pred(7) = {5, 6, 9} 2.6 ( ) X Y Y X (successor block) X succ(x) succ(7) = {8, 9} 2.7 ( ) (join block) ( ) (branch block) ( ) (entry block) ( ) (exit block) ( ) X X (predecessor path) 2.12 ( ) X X (successor path) 2.13 ( ) Y X Y X (back edge)

15 2.3 SSA (static single assignment form) (a) a 2 1 (b) phi a1 a2 SSA [1, 11] a=1 a=2 a1=1 a2=2 =a a3=phi(a1,a2) =a3 (a) (b) 2.6: SSA : 14

16 2.4.2 x = y x y x y y y 2.8: : : 15

17 2.4.5 COINS [5] [14] 16

18 3 COINS COINS 3.1 CoVis CoVis HIR HIR LIR LIR 3.1 matmult.c HIR CoVis HIR HIR HIR LIR LIR trace2html trace2html html 3.2 LIR LIR [<<] [>>] trace2html Perl 1 clickable 17

19 3.1: CoVis 3.2: trace2html 18

20 4 4.1 trace2html LIR LIR C lir2c CoVis clickable LIR lir2c clickable 4.2 html javascript LIR trace2html trace2html Perl [12] Java LIR lir2c html javascript quicksort.c 19

21 4.1 ( index ) LIR LIR ( ) ( LIR ) LIR ( lir2c ) LIR lir2c C ( ) LIR [>>] LIR LIR [<<] [>>] LIR lir2c [display] lir2c lir2c [source] lir2c 3 lir2c [display] [source] LIR LIR lir2c 20

22 4.1: 21

23 4.3 COINS LIR html 4.2: COINS LIR COINS LIR Before/After : Function " ": Local Symbol table:... Control Flow Graph: #1 Basic Block(.L1): DFN=(1,1), <-() ->(#2,#3)... (JUMP (LABEL I32 ".L5" $2))... End Function 22

24 4.3.2 Graphviz DOT GIF DOT # Basic Block... Java LIR Basic Block # Basic Block(.L )... Basic Block.L JUMP JUMPC JUMP LIR (JUMP....L... ) JUMPC (JUMPC....L....L... ) #1 Basic Block (.L1): DFN=(1,1), <-() ->(#2,#3)... (JUMP (LABEL I32 ".L3" $3)) L1 -> L3 DOT Graphviz chapter LIR Before After 1 html chapter=1 Before After chapter 1 lir2c chapter html LIR #L.L - lir2c #L.L - html javascript chapter=12 After CommonSubexpressionElimination LIR html 23

25 <a name="link12">after CommonSubexpressionElimination</a> lir2c <a name="chapter12">after CommonSubexpressionElimination</a> <a name="graph12"></a>...<img src="...gif">... index javascript After CommonSubexpressionElimination index javascript <a href="javascript:pagechangewithgraph( trace_quicksort-body.html#link12, trace_quicksort-likec.html#chapter12, trace_quicksort-graph.html#graph12 );"> Before CommonSubexpressionElimination (Common subexpression elimination on SSA form.): </a> LIR javascript <a href="javascript:pagechangewithgraph ( #L.L16-10, trace_quicksort-likec.html#lc.l16-10, trace_quicksort-graph.html#graph12 );"> [<<] </a> lir2c <a href="javascript:showlirandgraph ( trace_quicksort-body.html#l.l1-10, trace_quicksort-graph.html#graph12 );"> [display] </a> <a href="javascript:pagechangewithgraph ( trace_quicksort-body.html#link12, trace_quicksort-likec.html#chapter12, trace_quicksort-graph.html#graph12 );"> <img src=".\graph_img/after_commonsubexpressionelimination sgetc_r_1.gif"> </a> 24

26 Appel Appel [1] Fig.19.4 #include <stdio.h> int main () { int i; int j; int k; i = 1; j = 1; k = 0; while (k < 100) { if (j < 20) { j = i; k = k + 1; } else { j = k; k = k + 2; } } } printf("%d\n",j); 25

27 SSA (Constant Propagation with Conditional Branch) void main(void) { while ( k2 = phi(0,k4); // k2 < 100) { k4 = k2 + 1; } printf("%d\n",1); } LIR lir2c 26

28 5.1: Appel 27

29 5.2: Appel 28

30 COINS #include <stdio.h> void f(int x, int y); main() { f(1, 0); } void f(int x, int y) { int i, t; for (i = 0; i < 10; i++) { if (y <= i && y == 0) return; t = x / y; } printf("x / y = %d\n", t); } return; divex/esplt/hli 1 SSA 1 3 / / 29

31 #include <stdio.h> void f(int x, int y); main() { f(1, 0); } void f(int x, int y) { int i_1 = 0, t = 0; if (i_1 < 10) { t = x / y; while (i_2 = phi(i_3, i_1), // i_2 < 10 ) { if (y <= i_2) if (y == 0) return; i_3 = i_2 + 1; } } printf("x / y = %d\n", t); } return; y 0 y 13 (t = x / y) y LIR L35 (SET I32 (REG I32 "_hlii32_0") (DIVS I32 (REG I32 "x.9%_1") (REG I32 "y.10%_1"))) lir2c _hlii32_0 = x.9%_1/y.10%_1; 30

32 5.3: 31

33 5.4: 32

34 6 6.1 trace2html COINS SSA LIR LIR lir2c LIR lir2c 3 CoVis COINS COINS CoVis HIR HIR LIR LIR CoVis trace2html 33

35 6.2.2 Graphical Visualization Of Compiler Optimizations [3] VPO [18] XML XML Performance Visualizations using XML Representations [17] SUIF [16] IMPACT [8] XML

36 7 COINS SSA LIR LIR lir2c LIR lir2c 3 COINS html Java 35

37 36

38 [1] Andrew W. Appel. Modern compiler implementation in Java. Cambridge University Press, 2nd edition, [2] AT&T. Graphviz homepage. [3] M. Boyd and D. Whalley. Graphical visualization of compiler optimization, [4] COINS-Project. Coins homepage. [5].. sassa/coins-www-ssa/japanese/ ssa-external-japanese.pdf. [6] Robert Fitzgerald, Todd B. Knoblock, Erik Ruf, Bjarne Steensgaard, and David Tarditi. Marmot: an optimizing compiler for Java. Software - Practice and Experience, Vol. 30, No. 3, pp , [7] GNU-Project. Gcc homepage. [8] IMPACT Research Group. [9] IBM. Jikes research virtual machine. [10]. COINS LIR, base/backend/newlir.html. [11].., [12] Larry Wall, Tom Cbristiansen, and Jon Orwant. Perl. 3. [13] COINS Project. COINS LIR, org/spec/lir.pdf. [14].., [15] Scale Compiler Group. Scale homepage. [16] The SUIF Group. The stanford suif compiler group. [17] Yijun Yu, Kristof Beyls, and Erik H. D Hollander. Performance visualizations using XML representations. Proceedings of the Eighth International Conference on Information Visualisation( 04),

39 [18] Zephyr. Zephyr very portable optimizer. vpo/. 38

COINS 5 2.1

COINS (0501699) 20 21 2 5 1 3 1.1....................................... 3 1.2..................................... 4 1.3....................................... 4 2 COINS 5 2.1 COINS..................................