sample compiler flow

寫了個 sample compiler flow,不過這裡面還有很多議題可以討論,就等小弟我慢慢的研究吧.

CFG *cfg = Parser(['file','code','temp_IR']);

# Blocks[BB(basicblock)]; 
# Edges [forward,backward,cross,tree,fallthrough(without branch condition)];
# SubGraph(DFG): data flow graph ex: c = a + b; 
#
# @ ex: if ( a==1 ) { c = a+b; } else { c = a-b; }
#
# cfg_BB(0);                          # condition 
# cfg_BB(0)->dfg_BB(0)                 # a==1
#            dfg_BB(0)->instruction_ii(0)     # a==1
#                       instruction_ii(0)->operator(0)[label,type,operand] # int(a) eq 1
# cfg_BB(1): #If(true)  
# ...
# cfg_BB(2): #If(false)
# ...
# cfg_EE(0){cfg_BB(0),cfg_BB(1),'E0',0};     # edge 'E0' weighted 0 cfg_BB(0)->cfg_BB(1)
# ...
# linklist gen

list<>cfg_order = cfg->search_methods([deep_first_search(),
                                       breadth_first_search(),
                                       post_order_search(),
                                       pre_order_search(),
                                       topology_sequence_search(),
                                       reverse_topology_sequence_search()]);

# cfg_order = [ cfg_BB(0), cfg_BB(1), cfg_BB(2) ];




# find domin path, check dependence for each BasicBlock
Dom *dom_tree = Dom(cfg);

list<>dom_order = dom_tree->search_methods([post_order_domin(),
                                            pre_order_domin(),
                                            imm_domin()]);

# dom_order = { Dom(cfg_BB(0):{cfg_BB(0)}),
                Dom(cfg_BB(1):{cfg_BB(0),cfg_BB(1)}),
                Dom(cfg_BB(2):{cfg_BB(0),cfg_BB(2)}) };

Dom_Graph *dom_graph = dom_tree->gen_graph();

#      cfg_BB(0)   @ dom_graph(directed graph)
#          |
#     -----------
#     |         |
#     V         V
# cfg_BB(1) cfg_BB(2)





# find the correlation for each instruction
Reg *reg = Reg(cfg);

list<>reg_bb_order = reg->search_SSA();     

# reg_bb_order = { BB0:[ cfg_BB(0)->dfg_BB(0)->(a:0), cfg_BB(0)->dfg_BB(0)->(eq:0),  cfg_BB(0)->dfg_BB(0)->(1:0) ],
#                  BB1:[ cfg_BB(1)->dfg_BB(1)->(c:1), cfg_BB(1)->dfg_BB(1)->(add:1), cfg_BB(1)->dfg_BB(1)->(a:1), cfg_BB(1)->dfg_BB(1)->(b:1) ],
#                  BB2:[ cfg_BB(2)->dfg_BB(2)->(c:2), cfg_BB(2)->dfg_BB(2)->(sub:2), cdg_BB(2)->dfg_BB(2)->(a:2), cfg_BB(2)->dfg_BB(2)->(b:2) ] }

SSA_Graph *ssa_graph = reg->toSSA(); 

#              (a:0) eq (1:0)
#                     |
#        --------------------------
#        |                        |                 
#        V                        V
# (c:1) add (a:1) (b:1)    (c:2) sub (a:2) (b:2) 

list<> phi_order = ssa_graph->search_PHI(c);

# phi_order = [ BB1:c:1, BB2:c:2 ] @ node c

#CFG *nw_cfg = ssa_graph->toCFG();




# static analysis for BasicBlock such as if else, while, ...

Strc *strc_tree = Strc(cfg);

strc_tree->search_methods([Block(),
                           IfThen(),
                           IfThenElse(),
                           SelfLoop(),
                           NaturalLoop(),
                           Unreachable()]);

strc_tree->analysis([DeadCodeCut(),
                     LoadStroeMerge(),
                     ParallelMerge(),
                     SerialMerge()])

# DeadcodeCut    ex: for(i=0; i<10; i++) { a=1; } unreachable @ a=1;  
# LoadStoreMerge ex: c     = a[10];           c = a[10];
#                    a[10] = c+1;       =     d = c+1;
#                    d     = a[10];           
# SerialMerge    ex: BB(0) goto BB(1) @ if and only if BB(0)->BB(1) has one directed edge and BB(1) has only one sink edge.
#                    merge BB(0) and BB(1) to BB(0-1)
# ParallelMerge  ex: BB(0) and BB(1) are dependent @ if and only if Dom(BB(0)) != Dom(BB(1)), path(BB(0)) != path(BB(1))
#                    BB(0) BB(1) can be parallel

cfg = str_tree->update_cfg();





# find Branck location, and predict it happened or not,
Div_Graph *div_graph = Div_Graph(cfg);

div_graph->analysis([BranchPredict(),
                     BranchCut()]);

# ex: if ( a==1 ) { if( b==1 ) { c=a+b; } }
#                |  
#     if( a==1 && b==1 ) { c=a+b; } 

cfg = div_graph->update_cfg();





# platform Assignment
# X86/Arm/Mips...
X86 *x86 = X86(cfg);

# x86 SIMD analysis, ex: MAC d = (a*b)+c merge a = a*b and d = a+c
x86->analysis_SIMD();
...

ref: Muchnick book