Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Diff of /sml/trunk/src/MLRISC/flowgraph/cfg.sml
ViewVC logotype

Diff of /sml/trunk/src/MLRISC/flowgraph/cfg.sml

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 1118, Wed Mar 6 15:30:25 2002 UTC revision 1192, Wed May 15 14:02:06 2002 UTC
# Line 18  Line 18 
18      structure I = I      structure I = I
19      structure P = Asm.S.P      structure P = Asm.S.P
20      structure C = I.C      structure C = I.C
     structure W = Freq  
21      structure G = Graph      structure G = Graph
     structure A = Annotations  
22      structure S = Asm.S      structure S = Asm.S
23        structure A = Array
24        structure H = IntHashTable
25    
26      type weight = W.freq      type weight = real
27    
28      datatype block_kind =      datatype block_kind =
29          START          (* entry node *)          START          (* entry node *)
# Line 63  Line 63 
63          INFO of { annotations : Annotations.annotations ref,          INFO of { annotations : Annotations.annotations ref,
64                    firstBlock  : int ref,                    firstBlock  : int ref,
65                    reorder     : bool ref,                    reorder     : bool ref,
66                    data        : P.pseudo_op list ref                    data        : P.pseudo_op list ref,
67                      decls       : P.pseudo_op list ref
68                  }                  }
69    
70      type cfg = (block,edge_info,info) Graph.graph      type cfg = (block,edge_info,info) Graph.graph
# Line 101  Line 102 
102            end            end
103      fun insns(BLOCK{insns, ...}) = insns      fun insns(BLOCK{insns, ...}) = insns
104      fun freq(BLOCK{freq, ...}) = freq      fun freq(BLOCK{freq, ...}) = freq
105        fun edgeFreq(_,_,EDGE{w, ...}) = w
106        fun sumEdgeFreqs es = foldr (fn (e,w) => !(edgeFreq e) + w) 0.0 es
107    
108      fun newBlock'(id,kind,insns,freq) =      fun newBlock'(id,kind,insns,freq) =
109          BLOCK{ id          = id,          BLOCK{ id          = id,
# Line 126  Line 129 
129      fun newStart(id,freq) = newBlock'(id,START,[],freq)      fun newStart(id,freq) = newBlock'(id,START,[],freq)
130      fun newStop(id,freq) = newBlock'(id,STOP,[],freq)      fun newStop(id,freq) = newBlock'(id,STOP,[],freq)
131    
132        fun newNode (G.GRAPH graph) wt = let
133              val id = #new_id graph ()
134              val nd = (id, newBlock (id, ref wt))
135              in
136                #add_node graph nd;
137                nd
138              end
139    
140      fun branchOf(EDGE{k=BRANCH b,...}) = SOME b      fun branchOf(EDGE{k=BRANCH b,...}) = SOME b
141        | branchOf _ = NONE        | branchOf _ = NONE
142      fun edgeDir(_,_,e) = branchOf e      fun edgeDir(_,_,e) = branchOf e
# Line 144  Line 155 
155      fun emitHeader (S.STREAM{comment,annotation,...})      fun emitHeader (S.STREAM{comment,annotation,...})
156                     (BLOCK{id,kind,freq,annotations,...}) =                     (BLOCK{id,kind,freq,annotations,...}) =
157         (comment(kindName kind ^"["^Int.toString id^         (comment(kindName kind ^"["^Int.toString id^
158                      "] ("^W.toString (!freq)^")");                      "] ("^Real.toString (!freq)^")");
159          nl();          nl();
160          app annotation (!annotations)          app annotation (!annotations)
161         )         )
# Line 187  Line 198 
198          let val info = INFO{ annotations = ref [],          let val info = INFO{ annotations = ref [],
199                               firstBlock  = ref 0,                               firstBlock  = ref 0,
200                               reorder     = ref false,                               reorder     = ref false,
201                               data        = ref []                               data        = ref [],
202                                 decls       = ref []
203                             }                             }
204          in  cfg info end          in  cfg info end
205    
# Line 195  Line 207 
207          let val info = INFO{ annotations = ref [],          let val info = INFO{ annotations = ref [],
208                               firstBlock  = #firstBlock graph_info,                               firstBlock  = #firstBlock graph_info,
209                               reorder     = #reorder graph_info,                               reorder     = #reorder graph_info,
210                               data        = #data graph_info                               data        = #data graph_info,
211                                 decls       = #decls graph_info
212                             }                             }
213          in  UpdateGraphInfo.update CFG info end          in  UpdateGraphInfo.update CFG info end
214    
# Line 203  Line 216 
216          (case #entries cfg () of          (case #entries cfg () of
217             [] =>             [] =>
218             let val i     = #new_id cfg ()             let val i     = #new_id cfg ()
219                 val start = newStart(i,ref 0)                 val start = newStart(i,ref 0.0)
220                 val _     = #add_node cfg (i,start)                 val _     = #add_node cfg (i,start)
221                 val j     = #new_id cfg ()                 val j     = #new_id cfg ()
222                 val stop  = newStop(j,ref 0)                 val stop  = newStop(j,ref 0.0)
223                 val _     = #add_node cfg (j,stop)                 val _     = #add_node cfg (j,stop)
224             in (*  #add_edge cfg (i,j,EDGE{k=ENTRY,w=ref 0,a=ref []}); *)             in (*  #add_edge cfg (i,j,EDGE{k=ENTRY,w=ref 0,a=ref []}); *)
225                 #set_entries cfg [i];                 #set_entries cfg [i];
# Line 270  Line 283 
283          jmp          jmp
284      end      end
285    
286       local
287         fun getNode (G.GRAPH{node_info, ...}, id) = (id, node_info id)
288       in
289       fun entryId (G.GRAPH{entries, ...}) = (case entries()
290               of [id] => id
291                | _ => error "no unique entry block"
292              (* end case *))
293       fun entry cfg = getNode(cfg, entryId cfg)
294       fun exitId (G.GRAPH{exits, node_info, ...}) = (case exits()
295               of [id] => id
296                | _ => error "no unique exit block"
297              (* end case *))
298       fun exit cfg = getNode(cfg, exitId cfg)
299       end
300    
301       exception Can'tMerge
302       exception NotFound
303    
304       fun labelOf(G.GRAPH cfg) node = defineLabel(#node_info cfg node)
305    
306       fun copyEdge(EDGE{a,w,k}) = EDGE{a=ref(!a),w=ref(!w),k=k}
307    
308       (*=====================================================================
309        *
310        *  Check whether block i must preceed block j in any linear layout.
311        *  This may be true if i falls through to j (transitively)
312        *
313        *=====================================================================*)
314       fun mustPreceed (G.GRAPH cfg) (i,j) =
315       let val visited = H.mkTable(23,NotFound)
316           fun chase [] = false
317             | chase((u,v,EDGE{k=(FALLSTHRU|BRANCH false),...})::_) =
318               if H.inDomain visited u then false
319               else u = i orelse (H.insert visited (u,true); chase(#in_edges cfg u))
320             | chase(_::es) = chase es
321       in  i = j orelse chase(#in_edges cfg j)
322       end
323    
324       (*=====================================================================
325        *
326        *  Predicates on nodes and edges
327        *
328        *=====================================================================*)
329       fun isMerge (G.GRAPH cfg) node = length(#in_edges cfg node) > 1
330       fun isSplit (G.GRAPH cfg) node = length(#out_edges cfg node) > 1
331    (*
332       fun hasSideExits (G.GRAPH cfg) node =
333             List.exists (fn (_,_,EDGE{k=SIDEEXIT _,...}) => true
334                           | _ => false) (#out_edges cfg node)
335    *)
336       fun hasSideExits _ _ = false
337       fun isCriticalEdge CFG (_,_,EDGE{k=ENTRY,...}) = false
338         | isCriticalEdge CFG (_,_,EDGE{k=EXIT,...}) = false
339         | isCriticalEdge CFG (i,j,_) = isSplit CFG i andalso isMerge CFG j
340    
341       (*=====================================================================
342        *
343        *  Update the label of the branch instruction in a certain block
344        *  to be consistent with the control flow edges.  This doesn't work
345        *  on hyperblocks!!!
346        *
347        *=====================================================================*)
348       fun updateJumpLabel(CFG as G.GRAPH cfg) =
349       let val labelOf = labelOf CFG
350           fun update node =
351           case #node_info cfg node of
352              BLOCK{insns=ref [],...} => ()
353           |  BLOCK{kind=START,...} => ()
354           |  BLOCK{kind=STOP,...} => ()
355           |  BLOCK{insns=insns as ref(jmp::rest),...} =>
356                 (case #out_edges cfg node of
357                    [] => ()
358                 |  [(_,_,EDGE{k=(ENTRY | EXIT),...})] => ()
359                 |  [(i,j,_)] =>
360                      if InsnProps.instrKind jmp = InsnProps.IK_JUMP then
361                           insns := InsnProps.setJumpTarget(jmp,labelOf j)::rest
362                      else ()
363                 |  [(_,i,EDGE{k=BRANCH x,...}),
364                     (_,j,EDGE{k=BRANCH y,...})] =>
365                      let val (no,yes) = if x then (j,i) else (i,j)
366                      in  insns :=
367                            InsnProps.setBranchTargets{i=jmp,
368                                    f=labelOf no,t=labelOf yes}::rest
369                      end
370                 |  es =>
371                      let fun gt ((_,_,EDGE{k=SWITCH i,...}),
372                                  (_,_,EDGE{k=SWITCH j,...})) = i > j
373                            | gt _ = error "gt"
374                          val es = ListMergeSort.sort gt es
375                          val labels = map (fn (_,j,_) => labelOf j) es
376                      in  error "updateJumpLabel"
377                      end
378                 )
379       in  update
380       end
381    
382       (*=====================================================================
383        *
384        *  Merge a control flow edge i -> j.
385        *  Raise Can't Merge if it is illegal.
386        *  After merging blocks i and j will become block i.
387        *
388        *=====================================================================*)
389       fun mergeEdge (CFG as G.GRAPH cfg) (i,j,e as EDGE{w,k,...}) =
390       let val _ = case k of
391                      (ENTRY | EXIT) => raise Can'tMerge
392                   |  _ => ()
393           val _ = case (#out_edges cfg i,#in_edges cfg j) of
394                      ([(_,j',_)],[(i',_,_)]) =>
395                         if j' <> j orelse i' <> i then raise Can'tMerge
396                         else ()
397                   |  _ => raise Can'tMerge
398           val _ = if mustPreceed CFG (i,j) then raise Can'tMerge else ()
399           val BLOCK{align=d2,insns=i2,annotations=a2,...} = #node_info cfg j
400           val _  = case !d2 of SOME _ => () | _ => raise Can'tMerge
401           val BLOCK{align=d1,insns=i1,annotations=a1,...} = #node_info cfg i
402              (* If both blocks have annotations then don't merge them.
403               * But instead, just try to removed the jump instruction instead.
404               *)
405           val canMerge = case (!a1, !a2) of
406                     (_::_, _::_) => false
407                   | _ => true
408           val insns1 = case !i1 of
409                          [] => []
410                        | insns as jmp::rest =>
411                            if InsnProps.instrKind jmp = InsnProps.IK_JUMP
412                            then rest else insns
413       in  if canMerge then
414            (i1 := !i2 @ insns1;
415             a1 := !a1 @ !a2;
416             #set_out_edges cfg
417               (i,map (fn (_,j',e) => (i,j',e)) (#out_edges cfg j));
418             #remove_node cfg j;
419             updateJumpLabel CFG i
420            )
421           else (* Just eliminate the jump instruction at the end *)
422             (i1 := insns1;
423              #set_out_edges cfg
424                (i,map (fn (i,j,EDGE{w,a,...}) =>
425                      (i,j,EDGE{k=FALLSTHRU,w=w,a=a}))
426                         (#out_edges cfg i))
427             );
428           true
429       end handle Can'tMerge => false
430    
431       (*=====================================================================
432        *
433        *  Eliminate the jump at the end of a basic block if feasible
434        *
435        *=====================================================================*)
436       fun eliminateJump (CFG as G.GRAPH cfg) i =
437           (case #out_edges cfg i of
438              [e as (i,j,EDGE{k,w,a})] =>
439                (case fallsThruFrom(CFG,j) of
440                    SOME _ => false
441                 |  NONE =>
442                    if mustPreceed CFG (j,i) then false
443                    else
444                    let val BLOCK{insns,...} = #node_info cfg i
445                        val BLOCK{align,...}  = #node_info cfg j
446                    in  case (!align,!insns) of
447                          (NONE,jmp::rest) =>
448                           if InsnProps.instrKind jmp = InsnProps.IK_JUMP then
449                            (insns := rest;
450                             removeEdge CFG e;
451                             #add_edge cfg (i,j,EDGE{k=FALLSTHRU,w=w,a=a});
452                             true
453                            )
454                           else false
455                        |  _ => false
456                    end
457                )
458           |  _ => false
459           )
460    
461       (*=====================================================================
462        *
463        *  Insert a jump at the end of a basic block if feasible
464        *
465        *=====================================================================*)
466       fun insertJump (CFG as G.GRAPH cfg) i =
467           (case #out_edges cfg i of
468               [e as (i,j,EDGE{k=FALLSTHRU,w,a,...})] =>
469                  let val BLOCK{insns,...} = #node_info cfg i
470                  in  insns := InsnProps.jump(labelOf CFG j) :: !insns;
471                      removeEdge CFG e;
472                      #add_edge cfg (i,j,EDGE{k=JUMP,w=w,a=a});
473                      true
474                  end
475            |  _ => false
476           )
477    
478    
479       (*=====================================================================
480        *
481        *  Split a group of control flow edge.
482        *
483        *  Split n groups of control flow edges, all initially entering block j,
484        *
485        *     i_11 -> j,  i_12 -> j, ...         group 1
486        *     i_21 -> j,  i_22 -> j, ...         group 2
487        *             ....
488        *     i_n1 -> j,  i_n2 -> j, ...         group n
489        *
490        *  into
491        *
492        *     i_11 -> k_1
493        *     i_12 -> k_1
494        *        ...
495        *     i_21 -> k_2
496        *     i_22 -> k_2
497        *        ...
498        *     i_n1 -> k_n
499        *     i_n2 -> k_n
500        *        ...
501        *
502        *  and k_1 -> k_2
503        *      k_2 -> k_3
504        *        ...
505        *      k_n -> j
506        *
507        *  Return the new edges
508        *       k_1->j,...,k_n -> j
509        *
510        *  and the new blocks
511        *       k_1, ..., k_n.
512        *
513        *  Each block k_1, ..., k_n can have instructions placed in them.
514        *
515        *  If the jump flag is true, then a jump is always placed in the
516        *  new block k_n; otherwise, we try to eliminate the jump when feasible.
517        *
518        *=====================================================================*)
519       fun splitEdges (CFG as G.GRAPH cfg) {groups=[], jump} = []
520         | splitEdges (CFG as G.GRAPH cfg) {groups as ((first,_)::_), jump} =
521       let (* target of all the edges *)
522           val j = let val (_,j,_) = hd first in j end
523    
524           (* Insert an edge i->j with frequency freq.
525            * It is a jump edge iff jump flag is true or
526            * some other block is already falling into j
527            *)
528           fun insertEdge(i,j,node_i,freq,jump) =
529           let val kind =
530                   if jump orelse isSome(fallsThruFrom(CFG,j)) then
531                      let val insns_i = insns node_i
532                      in  insns_i := InsnProps.jump(labelOf CFG j) :: !insns_i;
533                          JUMP
534                      end
535                   else
536                      FALLSTHRU
537               val edge_info = EDGE{k=kind, w=ref freq, a=ref []}
538               val edge = (i,j,edge_info)
539           in  #add_edge cfg edge;
540               edge
541           end
542    
543           (* Redirect all edges *)
544           fun redirect([], freq, new) = new
545             | redirect((edges, insns)::groups, freq, new) =
546           let
547               val freq = sumEdgeFreqs edges + freq (* freq of new block *)
548    
549               (*  Sanity check
550                *)
551               fun check [] = ()
552                 | check((u,v,_)::es) =
553                   (if v <> j then error "splitEdge: bad edge" else ();
554                    check es
555                   )
556    
557               val () = check edges
558    
559               val k = #new_id cfg () (* new block id *)
560               val node_k =
561                   BLOCK{id=k, kind=NORMAL,
562                         freq= ref freq, align=ref NONE, labels = ref [],
563                         insns=ref insns, annotations=ref []}
564    
565           in  app (removeEdge CFG) edges;
566               app (fn (i,_,e) => #add_edge cfg (i,k,e)) edges;
567               #add_node cfg (k,node_k);
568               redirect(groups, freq, (k, node_k, edges, freq)::new)
569           end
570    
571           val new = redirect(groups, 0.0, [])
572    
573           (* Add the edges on the chain *)
574           fun postprocess([], next, new) = new
575             | postprocess((k, node_k, edges, freq)::rest, next, new) =
576               let val jump = next = j andalso jump
577                   val edge = insertEdge(k, next, node_k, freq, jump)
578               in  postprocess(rest, k, ((k,node_k),edge)::new)
579               end
580    
581           val new = postprocess(new, j, [])
582    
583       in  (* Update the labels on the groups *)
584           app (fn (es, _) => app (fn (i,_,_) => updateJumpLabel CFG i) es) groups;
585           new
586       end
587    
588       (*=====================================================================
589        *
590        *  Split all critical edges in the CFG
591        *
592        *=====================================================================*)
593       fun splitAllCriticalEdges (CFG as G.GRAPH cfg) =
594       let val hasChanged = ref false
595       in  #forall_edges cfg
596             (fn e => if isCriticalEdge CFG e then
597               (splitEdges CFG {groups=[([e],[])],jump=false};
598                hasChanged := true)
599                else ());
600           if !hasChanged then changed CFG else ()
601       end
602    
603       (*=====================================================================
604        *
605        *  Tail duplicate a region until there are no side entry edges
606        *  entering into the region.  Return the set of new edges and nodes
607        *
608        *=====================================================================*)
609       fun tailDuplicate (CFG as G.GRAPH cfg : cfg)
610                         {subgraph=G.GRAPH subgraph : cfg,root} =
611       let
612           val blockMap = H.mkTable(10,NotFound)
613           val _ = print("[root "^Int.toString root^"]\n")
614    
615           fun duplicate v =
616               H.lookup blockMap v handle NotFound =>
617               let val w  = #new_id cfg ()
618                   val w' = copyBlock(w,#node_info cfg v)
619               in  #add_node cfg (w,w');
620                   H.insert blockMap (v,(w,w'));
621                   app (#add_edge cfg)
622                       (map (fn (i,j,e) => (w,j,copyEdge e)) (#out_edges cfg v));
623                   updateJumpLabel CFG w;
624                   (w,w')
625               end
626    
627           fun process((n,_)::rest,ns,Ns,Es) =
628                process(rest,collect(#entry_edges subgraph n,ns),Ns,Es)
629             | process([],ns,Ns,Es) = dupl(ns,Ns,Es,false)
630    
631           and collect([],ns) = ns
632             | collect((i,_,_)::es,ns) = collect(es,if i = root then ns else i::ns)
633    
634           and dupl([],Ns,Es,changed) = (Ns,Es,changed)
635             | dupl(n::ns,Ns,Es,changed) =
636                  redirect(#out_edges cfg n,ns,Ns,Es,changed)
637    
638           and redirect([],ns,Ns,Es,changed) = dupl(ns,Ns,Es,changed)
639             | redirect((u,v,e)::es,ns,Ns,Es,changed) =
640                if v <> root andalso
641                   #has_edge cfg (u,v) andalso
642                   #has_node subgraph v andalso
643                   not(#has_edge subgraph (u,v)) then
644                   (*
645                    * u -> v is a side entry edge, duplicate v
646                    *)
647                let val _ = print("[tail duplicating "^Int.toString u^" -> "^
648                                  Int.toString v^"]\n")
649                    val (w,w') = duplicate v
650                in  removeEdge CFG (u,v,e);
651                    #add_edge cfg (u,w,e);
652                    updateJumpLabel CFG u;
653                    redirect(es,w::ns,(w,w')::Ns,(u,w,e)::Es,true)
654                end
655                else redirect(es,ns,Ns,Es,changed)
656    
657           fun iter(Ns,Es) =
658               let val (Ns,Es,hasChanged) = process(#nodes subgraph (),[],Ns,Es)
659               in  if hasChanged then (changed CFG; iter(Ns,Es))
660                   else {nodes=Ns,edges=Es}
661               end
662    
663       in  iter([],[])
664       end
665    
666    
667       (*=====================================================================
668        *
669        *  Remove unreachable code in the CFG
670        *
671        *=====================================================================*)
672       fun removeUnreachableCode(CFG as G.GRAPH cfg) =
673       let val N = #capacity cfg ()
674           val visited = A.array(N,false)
675           fun mark n = if A.sub(visited,n) then ()
676                        else (A.update(visited,n,true); app mark (#succ cfg n))
677           val hasChanged = ref false
678           fun remove(b,BLOCK{align,insns,...}) =
679               if A.sub(visited,b) then ()
680               else
681               (hasChanged :=true;
682                case #in_edges cfg b of
683                  [] => #remove_node cfg b
684                |  _  => (insns := []; #set_out_edges cfg (b,[]))
685               )
686       in  app mark (#entries cfg ());
687           #forall_nodes cfg remove;
688           if !hasChanged then changed CFG else ()
689       end
690    
691    
692       (*=====================================================================
693        *
694        *  Merge all edges in the CFG.
695        *  Merge higher frequency edges first
696        *
697        *=====================================================================*)
698       fun mergeAllEdges(CFG as G.GRAPH cfg) =
699       let val mergeEdge = mergeEdge CFG
700           fun higherFreq((_,_,EDGE{w=x,...}),(_,_,EDGE{w=y,...}))= !x < !y
701           fun mergeAll([],changed) = changed
702             | mergeAll(e::es,changed) = mergeAll(es,mergeEdge e orelse changed)
703           (* note: sort expects the gt operator and sorts in ascending order *)
704           val hasChanged = mergeAll(ListMergeSort.sort higherFreq (#edges cfg ()),
705                                     false)
706       in  if hasChanged then changed CFG else ()
707       end
708    
709     (*========================================================================     (*========================================================================
710      *      *
711      *  Miscellaneous      *  Miscellaneous
# Line 299  Line 735 
735                    | FLOWSTO     => "flowsto"                    | FLOWSTO     => "flowsto"
736                  (* end case *))                  (* end case *))
737            in            in
738              F.format "%s(%d)" [F.STR kind, F.INT(!w)]              F.format "%s[%f]" [F.STR kind, F.REAL(!w)]
739            end            end
740    
741      fun getString f x = let      fun getString f x = let
# Line 324  Line 760 
760              | prList (h::t) = (pr (h ^ ", "); prList t)              | prList (h::t) = (pr (h ^ ", "); prList t)
761            val Asm.S.STREAM{emit,defineLabel,annotation,...} =            val Asm.S.STREAM{emit,defineLabel,annotation,...} =
762                  AsmStream.withStream outS Asm.makeStream []                  AsmStream.withStream outS Asm.makeStream []
763            fun showFreq (ref w) = F.format "[%s]" [F.STR(W.toString w)]            fun showFreq (ref w) = F.format "[%f]" [F.REAL w]
764            fun showEdge (blknum,e) =            fun showEdge (blknum,e) =
765                  F.format "%d:%s" [F.INT blknum, F.STR(show_edge e)]                  F.format "%d:%s" [F.INT blknum, F.STR(show_edge e)]
766            fun showSucc (_, x, e) = showEdge(x,e)            fun showSucc (_, x, e) = showEdge(x,e)

Legend:
Removed from v.1118  
changed lines
  Added in v.1192

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0