• parallelizing compilter ⇒ seq input, output parallel intrucstion
• vector compiler
• GCC 3.3.1
• make bootstrap
  • 3 stage, do the same thing.
    • Stage 1: old gcc → new gcc(1)
    • Stage 2: new gcc(1) → new gcc(2)
    • Stage 3: new gcc(2) → new gcc(3)
    • Only if 2 & 3 same, do make all
  • Generate machine-dependent files: gen*.o, feed *.md, output insn-*.[ch]
  • cpp
  • libbackend
  • cc1, language frontend
  • xgcc → (gcc)
  • cpp0
• Internals
  • C → tree → RTL → assembly (Chap 7,8)
  • flow of parser in Chap6
• trace

  # TO tag         FROM line  in file/text
  1  1 toplev_main        35  main.c
  2  1 do_compile       5414  toplev.c
  3  1 compile_file     5384  toplev.c
  4  1 lang_hooks       2130  toplev.c
  5  1 c_common_parse_file    57  c-lang.c
  6  1 yyparse           159  c-lex.c
  7  1 fndef             357  c-parse.y
  8  1 finish_function   403  c-parse.y

• requirement
  • clchen teaches half
  • other half, report one part of gcc (include binutils…)
  • no exam, grades from in class report / indivisual
• homework
  • modify main() in main.c XD

• cd gcc-3.3.1
• mkdir build && cd build (the ports way)
• ../configure –prefix=/home/rafan/tmp/gcc –disable-nls –with-system-zlib –enable-languages=c
• make bootstrap (native compiler)
• make install

It's very fast (about 10mins) on my X31 (1.4G). To define a compile-time variable, I modified the CFLAGS, {BOOT,STAGE1}_CFLAGS. (The 3-stage bootstrap is very complicated, normal make -DBLAH doesn't work.)

• gcc.c
  • use gccspec to read args
  • fork cpp (gccmain.c)
  • fork cc1 (main.c)
• frontend
  • machine-independent, also language-dependent
• backend
  • machine-dependent
  • main.c:5380 backend_init()
• get token path

  # TO tag         FROM line  in file/text
  1  1 toplev_main        43  gcc/main.c
  2  1 do_compile       5414  gcc/toplev.c
  3  1 compile_file     5384  gcc/toplev.c
  4  1 yyparse           162  yyparse ();
  5  1 yyparse           162  yyparse ();
  6  1 YYLEX            4658  gcc/c-parse.c
  7  1 yylex            2102  gcc/c-parse.c
  8  1 _yylex           5918  gcc/c-parse.c
  9  1 c_lex            5810  gcc/c-parse.c
   9  1 last_token       5810  gcc/c-parse.c
   10  1 cpp_ttype        5425  gcc/c-parse.c
   11  1 TTYPE_TABLE       148  TTYPE_TABLE
   12  1 TTYPE_TABLE       148  TTYPE_TABLE
  10  1 cpp_get_token     680  tok = cpp_get_token (parse_in);

• -fdump-transition-unit
  • finish_function: tree fndecl = current_function_decl;
  • finish_fname_decls, finish_stmt_tree modify tree
  • nested! in finish_function
  • c_expand_body generates rtl from tree
    • history: flag_inline_trees (tree_inline.c), good point to modify tree here
• homework
  • trace yyparse(), not an easy task

• tree (Internal Chap 7)
  • tree.def
    • DEFTREECODE, macro (tree.h)

  #define DEFTREECODE(SYM, STRING, TYPE, NARGS)   SYM,
  enum tree_code {
  #include "tree.def"
    LAST_AND_UNUSED_TREE_CODE     /* A convenient way to get a value for
                                     NUM_TREE_CODE.  */
  };
  #undef DEFTREECODE

• • • c-lang.c

  #define DEFTREECODE(SYM, NAME, TYPE, LENGTH) TYPE,
  const char tree_code_type[] = {
  #include "tree.def"
    'x',
  #include "c-common.def"
  };                                                              
  #undef DEFTREECODE

• • • statement is NOT handled by tree.def (language-indepenent), it's in c-common.def

  enum c_tree_code {
   C_DUMMY_TREE_CODE = LAST_AND_UNUSED_TREE_CODE,  // "link" to tree_node !!
   #include "c-common.def"
   LAST_C_TREE_CODE
 };

• • tree_node (tree.h), union of 13 kinds of struct
    • array is put in the bottom in a structure. If we want more than 1, just allocate enough space.

 struct tree_exp GTY(())
 {             
   struct tree_common common; 
   int complexity;
   tree GTY ((special ("tree_exp"), 
              desc ("TREE_CODE ((tree) &%0)")))
     operands[1];
 };

• • tree.c
    • make_node
• homeowork
  • precedence in yacc

• tree op0 is the right one, op1 is the left one
• build_stmt → make_node → ggc_alloc_tree build 'if' node
  • c_expand_start_cond puts 'cond' body by IF_COND (if_stmt) = cond;
• c_common_truthvalue_conversion # convert true/false value here!
• optimization, -d x, generates file.\d\d.xxxx (dump RTL) or -d a

• RTL
  • c_expand_body
  • init_function_start
  • expand_function_start
  • walk_tree
  • expand_main_function
  • expand_stmt
  • *lang_expand_function_end
  • expand_function_end
• RTX (type # ptr_prev# ptr_next#

 #define RTX_CODE        enum rtx_code
 enum rtx_code  {
 
 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS)   ENUM ,
 #include "rtl.def"              /* rtl expressions are documented here */ 
 #undef DEF_RTL_EXPR
 
   LAST_AND_UNUSED_RTX_CODE};    /* A convenient way to get a value for
                                    NUM_RTX_CODE.
                                    Assumes default enum value assignment.  */

• rtl.c: rtx_format, rtl.h: rtl_def, macro, rtl.def
• homework
  • precedence (yacc)

Each state contains a action * which is a linked list. In remove_conflict() called by make_parser() utilizes the precdence and association information which comes from symbol to determime whethere this action is applied first (SHIFT action)

In details, it uses a (action *) pref to record preferred action and (action *) p for current action. The loop is 2 level, first level is for each states, second is for each actions in that state. When it found an action with higher precedence, it modifies oldaction→suppressed to 2, i.e., the new action is dominated. (suppressed is used to indicated if this action is suppressed.)

yydefred, defreds()→ sole_reduction(), in this function, this handles '.' reduction, as the name ``sole'' implies.

• • precedence (bison)

Oh, bison's source is more clear than yacc.

In main(), it calls conflicts_solve() → set_conflicts(state), it calls resolve_sr_conflict(state) (only if the action has prec) to solve shift/reduce conflicts by precedence and associcatively. Inside it, it first finds the current reduction action for this state then if a shift has higher prec. Once the solution is out, it calls log_resolution(cur_reduction, which action, shift/reduce/right/left/…) to record the solution and records curresponding things.

• • read rtx

• c_expand_body → expand_stmt(), tree travesel, linked list
• expand_expr enters machine dependent routines here: (there is a op table in assembly)

      this_optab = ! unsignedp && flag_trapv
                   && (GET_MODE_CLASS(mode) == MODE_INT)
                   ? subv_optab : sub_optab;
  goto binop2;
  expand_binop()

• i386.md
  • define_insn, a tree node → a RTL expr (one rtx), also describes RTL → assembly
  • define_expand, a tree node → RTL exprs (many rtx)
  • define_split, rtx → many rtx (optimization)
  • deinfe_peephole2, many rtx → many rtx (optimization)
  • define_insn_and_split, tree → one rtx, rtx → assembly (many rtx)
• homework
  • i386.md (20K lines!!)

• gensupport.c, readctl.c support for common routines for gen*
• gencodes.c:
• pattern matters!
• c_expand_body; rest_of_compilation() to do optimize timevar_push/pop to measure elapsed time in each optimization

• Topics
  • yacc? XD
  • profiling?

• 1st level RTX
  • INSN
  • JUMP_INSN
  • CALL_INSN
  • BARRIER
  • CODE_LABEL
  • NOTE
• Basic block
  • data structure is the key
  • node, edge, traverse
  • no branch inside!

 (define_expand "addsi3"
   [(parallel [(set (match_operand:SI 0 "nonimmediate_operand" "")
                    (plus:SI (match_operand:SI 1 "nonimmediate_operand" "")
                             (match_operand:SI 2 "general_operand" "")))
               (clobber (reg:CC 17))])]

• peephole optimization
  • modify particular pattern in a small window (2-3 instructions)
  • constant folding, multiple → shift, null op
  • use decision tree to match all patterns (i386 has 64 peephole2)
  • use basic block as the small window
  • recog.c, insn-recog.c, insn-emit.c

• rtx → asm
• md describs how to convert a rtx pattern to a output asm pattern

• When?
  • one of then or else part is empty
  • condition can be decided in compile time
  • same condition in nested if
• How?
  • control dependency → data dependency
• Implemetation
  • use ce_if_block struct to store then, else part
  • convert until convengence
  • find if → can convert? → do convert

• tail call / tail recursion
• different to inline is that you don't do return ( return ( return … ) ) )
• use call_placeholder to decide to use sibiling call or tail recursion optimization
• parameter # is matter (since caller's frame size have to be larger than callee's)
• RTFS: toplev.c: static const lang_independent_options f_options[] =

• terms
  • basic induction variable, X = X + c or X = X - c
  • induction variable A = a * B + b, B is basic induction variable.
  • strength-reduction
  • loop unrolling

• copy loop header, we can save one bb
• no new DS, lots of condition (no pattern, dirty code)

• about 60mins
• topics (tentative)
  • what's profiling
  • how to use / example
  • Chapter 9, implementation (rtx?)
• import point
  • data structure
  • before/after rtx !!

• porting to .Net
  • generate CIL code (intermediate language)