working/0.1/regAllocation.sml

159 fun mk_edge ((n0:G.node,n1:G.node,lab:edgeLab), gr:('a,edgeLab) G.graph) =
160     if n0 = n1 then gr
161     else if (List.find (fn m => #2 m = n0) (#1(G.context(n1,gr)))) <> NONE then gr
163        let val ((p1,m1,l1,s1), del_n1) = G.match(n1,gr)
167 fun rm_edge ((n0:G.node,n1:G.node), gr:('a,edgeLab) G.graph) =
168     if n0 = n1 then gr
169     else if (List.find (fn m => #2 m = n0) (#1(G.context(n1,gr)))) = NONE then raise G.Edge
171        let val ((p1,m1,l1,s1), del_n1) = G.match(n1,gr)
172        in G.embed((List.filter (fn el => #2 el <> n0) (#1(G.context(n1,gr))),
188 fun computeUseDef (gr : ({instr:Assem.instr, use:int list, def:int list}, edgeLab) Graph.graph) =
195                 (T.empty,T.empty) gr;
586         val newCfg = List.foldl (fn (p,gr) => rm_edge((p,n),gr)) cfg (List.map (fn (lab,n) => n) preN);
596         val newCfg = List.foldl (fn (s,gr) => rm_edge((n,s),gr)) cfg (List.map (fn (lab,n) => n) sucN);
603 (* t : TmpTable,  gr : control-flow graph       *)
622      fun update_node gr nodeNo (varNo,newVarNo) (for_lhs,for_rhs) =
624               val {instr = curInst, def = df, use = us} = #3 (G.context(nodeNo,gr))
626               updateNode(gr, nodeNo,
642      fun insertLoadInst gr nodeNo varNo =
644                val {instr = curInst, def = df, use = us} = #3 (G.context(nodeNo,gr));
650                val gr1 = update_node gr nodeNo (varNo,newVarNo) (false,true)
657      fun insertStoreInst gr nodeNo varNo =
659                val {instr = curInst, def = df, use = us} = #3 (G.context(nodeNo,gr));
665                val gr1 = update_node gr nodeNo (varNo,newVarNo) (true,false)
672     fun process_one_variable gr varNo =
678             G.ufold (fn ((predL,nodeNo,inst,sucL),gr) =>
684                                             updateNode(gr,nodeNo,
690                                         insertLoadInst gr nodeNo varNo
692                               else gr
697                 gr gr
701         List.foldl (fn (varNo, gr) => process_one_variable gr varNo) old_cfg (S.listItems (spilled))
774         G.ufold (fn ((predL,nodeNo,nd,sucL),gr) =>
776                         updateNode (gr, nodeNo, {use = us, def = df, instr = substituteVars stm})
785 fun RegisterAllocation (gr, tmpT, preC) =
791     cfg := gr;
798     init (gr, tmpT);
834     val ((fun_name, fun_type, args, gr, outs), t) = CFG.convert_to_CFG prog;
836     val (gr',t) = RegisterAllocation (gr, t, argL);
839     val stms = CFG.linearizeCFG gr';
843     (fun_name, fun_type, args, gr', outs, rs)