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/x86/mltree/x86-fp.sml
ViewVC logotype

Diff of /sml/trunk/src/MLRISC/x86/mltree/x86-fp.sml

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

revision 909, Fri Aug 24 17:48:53 2001 UTC revision 925, Fri Sep 14 15:26:29 2001 UTC
# Line 1  Line 1 
1  (*  (* x86-fp.sml
2     *
3     * COPYRIGHT (c) 2001 Bell Labs, Lucent Technologies
4     *
5   * This phase takes a cluster with pseudo x86 fp instructions, performs   * This phase takes a cluster with pseudo x86 fp instructions, performs
6   * liveness analysis to determine their live ranges, and rewrite the   * liveness analysis to determine their live ranges, and rewrite the
7   * program into the correct stack based code.   * program into the correct stack based code.
# Line 56  Line 59 
59     val debug = false        (* set this to true to debug this module     val debug = false        (* set this to true to debug this module
60                                * set this to false for production use.                                * set this to false for production use.
61                                *)                                *)
62     val debugLiveness = false (* debug liveness analysis *)     val debugLiveness = true (* debug liveness analysis *)
63     val debugDead = false     (* debug dead code removal *)     val debugDead = false     (* debug dead code removal *)
64     val sanityCheck = false     val sanityCheck = true
65  in  in
66  functor X86FP  functor X86FP
67     (structure X86Instr  : X86INSTR     (structure X86Instr  : X86INSTR
68      structure X86Props  : INSN_PROPERTIES where I = X86Instr      structure X86Props  : INSN_PROPERTIES where I = X86Instr
69      structure Flowgraph : CONTROL_FLOW_GRAPH where I = X86Instr      structure Flowgraph : CONTROL_FLOW_GRAPH where I = X86Instr
70      structure Liveness  : LIVENESS where CFG.I = X86Instr      structure Liveness  : LIVENESS where CFG = Flowgraph
71      structure Asm       : INSTRUCTION_EMITTER where I = X86Instr and P = Flowgraph.P      structure Asm       : INSTRUCTION_EMITTER where I = X86Instr and P = Flowgraph.P
72     ) : CFG_OPTIMIZATION =     ) : CFG_OPTIMIZATION =
73  struct  struct
74     structure CFG = Flowgraph     structure CFG = Flowgraph
75       structure G  = Graph
76     structure I  = X86Instr     structure I  = X86Instr
77     structure T  = I.T     structure T  = I.T
78     structure P  = X86Props     structure P  = X86Props
# Line 79  Line 83 
83     structure An = Annotations     structure An = Annotations
84     structure CB = CellsBasis     structure CB = CellsBasis
85     structure SL = CB.SortedCells     structure SL = CB.SortedCells
86       structure HT = IntHashTable
87    
88     type flowgraph = CFG.cfg     type flowgraph = CFG.cfg
89     type an = An.annotations     type an = An.annotations
# Line 99  Line 104 
104     fun x + y = Word.toIntX(Word.+(Word.fromInt x, Word.fromInt y))     fun x + y = Word.toIntX(Word.+(Word.fromInt x, Word.fromInt y))
105     fun x - y = Word.toIntX(Word.-(Word.fromInt x, Word.fromInt y))     fun x - y = Word.toIntX(Word.-(Word.fromInt x, Word.fromInt y))
106    
107       fun celllistToCellset l = List.foldr CB.CellSet.add CB.CellSet.empty l
108       fun celllistToString l = CB.CellSet.toString(celllistToCellset l)
109    
110       (* Annotation to mark split edges *)
111       exception TargetMovedTo of G.node_id
112    
113     (*-----------------------------------------------------------------------     (*-----------------------------------------------------------------------
114      * Primitive instruction handling routines      * Primitive instruction handling routines
115      *-----------------------------------------------------------------------*)      *-----------------------------------------------------------------------*)
# Line 154  Line 165 
165          List.foldr (fn (r,"") => fregToString r |          List.foldr (fn (r,"") => fregToString r |
166                         (r,s) => fregToString r^" "^s) "" s                         (r,s) => fregToString r^" "^s) "" s
167    
168  (*   fun blknumOf(F.BBLOCK{blknum, ...}) = blknum *)     fun blknumOf(CFG.BLOCK{id, ...}) = id
169    
170     (*-----------------------------------------------------------------------     (*-----------------------------------------------------------------------
171      * A stack datatype that mimics the x86 floating point stack      * A stack datatype that mimics the x86 floating point stack
# Line 390  Line 401 
401      *     When necessary, split critical edges.      *     When necessary, split critical edges.
402      *  5. Sacrifice a goat to make sure things don't go wrong.      *  5. Sacrifice a goat to make sure things don't go wrong.
403      *-----------------------------------------------------------------------*)      *-----------------------------------------------------------------------*)
404     fun run _ = error "not implemented "     fun run(Cfg as G.GRAPH cfg) =
405  (*     let
406     fun run(cluster as F.CLUSTER{blocks, blkCounter, ...}) =         val numberOfBlks = #capacity cfg ()
407     let val getCell = C.getCellsByKind CB.FP (*extract the fp component of cellset*)         val ENTRY        = List.hd (#entries cfg ())
408           val EXIT         = List.hd (#exits cfg ())
409    
410           val getCell = C.getCellsByKind CB.FP
411                     (*extract the fp component of cellset*)
412    
413         val stTable = A.tabulate(8, fn n => I.ST(C.ST n))         val stTable = A.tabulate(8, fn n => I.ST(C.ST n))
414    
# Line 434  Line 449 
449          * P.S. I'm glad I didn't throw away the code liveness code.          * P.S. I'm glad I didn't throw away the code liveness code.
450          *------------------------------------------------------------------*)          *------------------------------------------------------------------*)
451         val defUse = P.defUse CB.FP   (* def/use properties *)         val defUse = P.defUse CB.FP   (* def/use properties *)
452         val _ = Liveness.liveness{defUse=defUse,         val {liveIn=liveInTable, liveOut=liveOutTable} = Liveness.liveness {
453                                   updateCell=C.updateCellsByKind CB.FP,                  defUse=defUse,
454                                   getCell=getCell,                  (* updateCell=C.updateCellsByKind CB.FP, *)
455                                   blocks=blocks                  getCell=getCell
456                                  }                } Cfg
457         (*------------------------------------------------------------------         (*------------------------------------------------------------------
458          * Scan the instructions compute the last uses and dead definitions          * Scan the instructions compute the last uses and dead definitions
459          * at each program point.  Ideally we can do this during the code          * at each program point.  Ideally we can do this during the code
# Line 464  Line 479 
479                        else ()                        else ()
480                 in  scan(instrs, live, (last,dead)::lastUse)                 in  scan(instrs, live, (last,dead)::lastUse)
481                 end                 end
482             val liveOutSet = SL.uniq(getCell (!liveOut))             val liveOutSet = SL.uniq liveOut
483             val _ =             val _ =
484                 if debug andalso debugLiveness then                 if debug andalso debugLiveness then
485                    print("LiveOut("^i2s blknum^") = "^                    print("LiveOut("^i2s blknum^") = "^
# Line 482  Line 497 
497         val useTbl      = A.array(n,~1) (* table for marking uses *)         val useTbl      = A.array(n,~1) (* table for marking uses *)
498    
499         (* %fp register bindings before and after a basic block *)         (* %fp register bindings before and after a basic block *)
500         val bindingsIn   = A.array(!blkCounter, NONE)         val bindingsIn   = A.array(numberOfBlks, NONE)
501         val bindingsOut  = A.array(!blkCounter, NONE)         val bindingsOut  = A.array(numberOfBlks, NONE)
502         val stampCounter = ref ~4096         val stampCounter = ref ~4096
503    
504         (* Edges that need splitting *)         (* Edges that need splitting *)
# Line 497  Line 512 
512          * Code for handling bindings between basic block          * Code for handling bindings between basic block
513          *------------------------------------------------------------------*)          *------------------------------------------------------------------*)
514    
515         fun splitEdge(targetId, source, target) =         fun splitEdge(title, source, target, e) =
516            (if debug andalso !traceOn then            (if debug andalso !traceOn then
517                pr("SPLITTING "^i2s(blknumOf source)^"->"^                pr(title^" SPLITTING "^i2s source^"->"^ i2s target^"\n")
                               i2s(blknumOf target)^"\n")  
518             else ();             else ();
519             addEdgesToSplit(targetId,             addEdgesToSplit(target,(source,target,e)::lookupEdgesToSplit target)
                            (source,target)::lookupEdgesToSplit targetId)  
520            )            )
521    
522         (* Given a cellset, return a sorted and unique         (* Given a cellset, return a sorted and unique
523          * list of elements with all non-physical registers removed          * list of elements with all non-physical registers removed
524          *)          *)
525         fun removeNonPhysical cellSet =         fun removeNonPhysical celllist =
526         let fun loop([], S) = SL.return(SL.uniq S)         let fun loop([], S) = SL.return(SL.uniq S)
527               | loop(f::fs, S) =               | loop(f::fs, S) =
528                 let val fx = CB.registerNum f                 let val fx = CB.registerNum f
529                 in  loop(fs,if fx <= 7 then f::S else S)                 in  loop(fs,if fx <= 7 then f::S else S)
530                 end                 end
531         in  loop(getCell(!cellSet), [])         in  loop(celllist, [])
532         end         end
533    
534         (* Given a sorted and unique list of registers,         (* Given a sorted and unique list of registers,
# Line 681  Line 694 
694         (*------------------------------------------------------------------         (*------------------------------------------------------------------
695          * Magic for inserting shuffle code at the end of a basic block          * Magic for inserting shuffle code at the end of a basic block
696          *------------------------------------------------------------------*)          *------------------------------------------------------------------*)
697         fun shuffleOut(stackOut, insns, b, block, succ, liveOut) =         fun shuffleOut(stackOut, insns, b, block, liveOut) =
698         let val liveOut = removeNonPhysical liveOut         let
699               val liveOut = removeNonPhysical(liveOut)
700    
701             (* Generate code that remove unnecessary values *)             (* Generate code that remove unnecessary values *)
702             val code = removeDeadValues(stackOut, liveOut, [])             val code = removeDeadValues(stackOut, liveOut, [])
# Line 708  Line 722 
722              * from the edge with the highest frequency.              * from the edge with the highest frequency.
723              *)              *)
724             fun find([], _, id, best) = (id, best)             fun find([], _, id, best) = (id, best)
725               | find((F.BBLOCK{blknum, insns, ...},freq)::edges,               | find((_, target, _)::edges, highestFreq, id, best) =
726                      highestFreq, id, best) =                 let val CFG.BLOCK{freq, ...} = #node_info cfg target
727                 if blknum = b+1 then (blknum, A.sub(bindingsIn, blknum))                 in  if target = b+1 then (target, A.sub(bindingsIn, target))
728                 else (case A.sub(bindingsIn, blknum) of                      else (case A.sub(bindingsIn, target) of
729                        NONE => find(edges, highestFreq, id, best)                        NONE => find(edges, highestFreq, id, best)
730                      | this as SOME stack =>                      | this as SOME stack =>
731                        if highestFreq < !freq then                        if highestFreq < !freq then
732                           find(edges, !freq, blknum, this)                                 find(edges, !freq, target, this)
733                        else                        else
734                           find(edges, highestFreq, id, best)                           find(edges, highestFreq, id, best)
735                      )                      )
736               | find(_::edges, highestFreq, id, best) =                 end
                   find(edges, highestFreq, id, best)  
737    
738             fun splitAllEdgesExcept([], succBlock) = ()             (*
739               | splitAllEdgesExcept((next as F.BBLOCK{blknum, ...},_)::edges,              * Split all edges source->target except omitThis.
740                                      succBlock) =              *)
741                 (if blknum <> succBlock andalso blknum <= b             fun splitAllEdgesExcept([], omitThis) = ()
742                  then splitEdge(blknum,block,next) else ();               | splitAllEdgesExcept((source,target,e)::edges, omitThis) =
743                  splitAllEdgesExcept(edges, succBlock)                 if target = EXIT then error "can't split exit edge!"
744                 )                 else
745               | splitAllEdgesExcept((F.EXIT _,_)::_, _) =                 (if target <> omitThis andalso
746                    error "can't split exit edge!"                     target <= b andalso          (* XXX *)
747               | splitAllEdgesExcept(_::edges, succBlock) =                     target <> ENTRY
748                  splitAllEdgesExcept(edges, succBlock)                  then splitEdge("ShuffleOut",source,target,e) else ();
749                    splitAllEdgesExcept(edges, omitThis)
750                   )
751    
        in  case !succ of  
              []             => matchLiveOut()  
            | [(F.EXIT _,_)] => matchLiveOut()  
            | succ =>  
752                (* Just one successor;                (* Just one successor;
753                 * try to match the bindings of the successor if it exist.                 * try to match the bindings of the successor if it exist.
754                 *)                 *)
755               fun matchIt succ =
756               let val (succBlock, target) = find(succ, ~1, ~1, NONE)               let val (succBlock, target) = find(succ, ~1, ~1, NONE)
757               in  splitAllEdgesExcept(succ, succBlock);               in  splitAllEdgesExcept(succ, succBlock);
758                   case target of                   case target of
759                     SOME stackIn => match(stackOut, stackIn)                     SOME stackIn => match(stackOut, stackIn)
760                   | NONE => done(stackOut,insns,code)                   | NONE => done(stackOut,insns,code)
761               end               end
762    
763           in  case #out_edges cfg b of
764                 [] => matchLiveOut()
765               | succ as [(_,target,_)] =>
766                    if target = EXIT then matchLiveOut()
767                    else matchIt succ
768               | succ => matchIt succ
769         end (* shuffleOut *)         end (* shuffleOut *)
770    
771         (*------------------------------------------------------------------         (*------------------------------------------------------------------
772          * Compute the initial fp stack bindings for basic block b.          * Compute the initial fp stack bindings for basic block b.
773          *------------------------------------------------------------------*)          *------------------------------------------------------------------*)
774         fun shuffleIn(b, block, pred, liveIn) =         fun shuffleIn(b, block, liveIn) =
775         let val liveInSet = removeNonPhysical liveIn         let
776               val liveInSet = removeNonPhysical liveIn
777    
778             (* With multiple predecessors, find out which one we             (* With multiple predecessors, find out which one we
779              * should connect to.   Choose the one from the block that              * should connect to.   Choose the one from the block that
# Line 761  Line 781 
781              * from the edge with the highest frequency.              * from the edge with the highest frequency.
782              *)              *)
783             fun find([], _, best) = best             fun find([], _, best) = best
784               | find((F.BBLOCK{blknum, insns, ...},freq)::edges,               | find((source, _, _)::edges, highestFreq, best) =
785                      highestFreq, best) =                 let val CFG.BLOCK{freq, data, ...} = #node_info cfg source
786                 (case A.sub(bindingsOut, blknum) of                 in  case A.sub(bindingsOut, source) of
787                   NONE => find(edges, highestFreq, best)                   NONE => find(edges, highestFreq, best)
788                 | this as SOME stack =>                 | this as SOME stack =>
789                      if blknum = b-1 then (* falls into b *)                        if source = b-1 andalso List.null(!data)
790                          then (* falls into b *)
791                         this                         this
792                      else if highestFreq < !freq then                      else if highestFreq < !freq then
793                         find(edges, !freq, this)                         find(edges, !freq, this)
794                      else                      else
795                         find(edges, highestFreq, best)                         find(edges, highestFreq, best)
796                 )                 end
              | find(_::edges, highestFreq, best) =  
                   find(edges, highestFreq, best)  
797    
798             fun splitAllDoneEdges [] = ()             fun splitAllDoneEdges [] = ()
799               | splitAllDoneEdges               | splitAllDoneEdges ((source, target, e)::edges) =
800                    ((prev as F.BBLOCK{blknum, ...},_)::edges) =                 (if source < b andalso
801                 (if blknum < b                     source <> ENTRY andalso
802                  then splitEdge(b,prev,block) else ();                     source <> EXIT
803                    then splitEdge("ShuffleIn", source, target, e) else ();
804                  splitAllDoneEdges edges                  splitAllDoneEdges edges
805                 )                 )
              | splitAllDoneEdges(_::edges) = splitAllDoneEdges edges  
806    
807             (* The initial stack bindings are determined by the live set.             (* The initial stack bindings are determined by the live set.
808              * No compensation code is needed.              * No compensation code is needed.
# Line 793  Line 812 
812                     case liveInSet of                     case liveInSet of
813                       [] => ST.stack0                       [] => ST.stack0
814                     | _  =>                     | _  =>
815                       (pr("liveIn="^CB.CellSet.toString (!liveIn)^"\n");                       (pr("liveIn="^celllistToString liveIn^"\n");
816                        newStack liveInSet                        newStack liveInSet
817                       )                       )
818                 val stackOut = ST.copy stackIn                 val stackOut = ST.copy stackIn
819             in  (stackIn, stackOut, [])             in  (stackIn, stackOut, [])
820             end             end
821    
822               val pred = #in_edges cfg b
823    
824             val (stackIn, stackOut, code) =             val (stackIn, stackOut, code) =
825                 case find(!pred, ~1, NONE) of                 case find(pred, ~1, NONE) of
826                   NONE => (splitAllDoneEdges(!pred); fromLiveIn())                   NONE => (splitAllDoneEdges(pred); fromLiveIn())
827                 | SOME stackIn' =>                 | SOME stackIn' =>
828                   (case !pred of                   (case pred of
829                      [_] => (* one predecessor *)                      [_] => (* one predecessor *)
830                      (* Use the bindings as from the previous block                      (* Use the bindings as from the previous block
831                       * We first have to deallocate all unused values.                       * We first have to deallocate all unused values.
# Line 813  Line 834 
834                             (* Clean the stack of unused entries *)                             (* Clean the stack of unused entries *)
835                          val code = removeDeadValues(stackOut, liveInSet, [])                          val code = removeDeadValues(stackOut, liveInSet, [])
836                      in  (stackIn', stackOut, code) end                      in  (stackIn', stackOut, code) end
837                   |  _ => (* more than one predecessors *)                   |  pred => (* more than one predecessors *)
838                      let val stackIn = ST.copy stackIn'                      let val stackIn = ST.copy stackIn'
839                          val code = removeDeadValues(stackIn, liveInSet, [])                          val code = removeDeadValues(stackIn, liveInSet, [])
840                          val stackOut = ST.copy stackIn                          val stackOut = ST.copy stackIn
# Line 822  Line 843 
843                           *)                           *)
844                          case code of                          case code of
845                             [] => ()                             [] => ()
846                          |  _  => splitAllDoneEdges(!pred);                          |  _  => splitAllDoneEdges(pred);
847                          (stackIn, stackOut, [])                          (stackIn, stackOut, [])
848                      end                      end
849                   )                   )
# Line 834  Line 855 
855         (*------------------------------------------------------------------         (*------------------------------------------------------------------
856          * Code for patching up critical edges.          * Code for patching up critical edges.
857          * The trick is finding a good place to insert the critical edges.          * The trick is finding a good place to insert the critical edges.
858          * The cluster representation is very hard to work with.          * Let's call an edge x->y that requires compensation
859            * code c to be inserted an candidate edge.  We write this as x->y(c)
860            *
861            * Here are the heuristics that we use to improve the final code:
862            *
863            *    1. Given two candidate edges a->x(c1) and b->x(c2) where c1=c2
864            *       then we can merge the two copies of compensation code.
865            *       This is quite common.  This generalizes to any number of edges.
866            *
867            *    2. Given two candidate edges a->x(c1) and b->x(c2) and where
868            *       c1 and c2 are pops, we can partially share c1 and c2.
869            *       Currently, I think I only recognize this case when
870            *       x has no fp registers live-in.
871            *
872            *    3. Given two candidate edges a->x(c1) and b->x(c2),
873            *       if a->x has a higher frequency then put the compensation
874            *       code in front of x (so that it falls through into x)
875            *       whenever possible.
876            *
877            * As you can see, the voodoo is strong here.
878            *
879            * The routine has two main phases:
880            *    1. Determine the compensation code by applying the heuristics
881            *       above.
882            *    2. Then insert them and rebuild the cfg by renaming all block
883            *       ids.  This is currently necessary to keep the layout order
884            *       consistent with the order of the id.
885          *------------------------------------------------------------------*)          *------------------------------------------------------------------*)
886         fun repairCriticalEdges         fun repairCriticalEdges(Cfg as G.GRAPH cfg) =
            (cluster as F.CLUSTER{blocks, entry, exit, annotations,  
                                  blkCounter}) =  
887         let (* Data structure for recording critical edge splitting info *)         let (* Data structure for recording critical edge splitting info *)
888             datatype compensationCode =             datatype compensationCode =
889               NEWEDGE of               NEWEDGE of
890                  {label:L.label,          (* label of new block *)                  {label:L.label,          (* label of new block *)
891                   preds:F.block list ref, (* predecessors *)                   entries:CFG.edge list ref,   (* edges going into this code *)
892                   code:I.instruction list,(* code *)                   code:I.instruction list,(* code *)
893                   comment:an                   comment:an
894                  }                  }
# Line 867  Line 912 
912             fun lookupRepairCode' b =             fun lookupRepairCode' b =
913                  getOpt(IntHashTable.find repairCodeTable' b,[])                  getOpt(IntHashTable.find repairCodeTable' b,[])
914    
915             (* Mapping from block id -> labels *)             (* Does the given block falls thru from the previous block?
916             val labelTable  = IntHashTable.mkTable(32, Nothing)              * If the previous block is ENTRY then also consider this to be true
917             val addLabel    = IntHashTable.insert labelTable              *)
918             fun lookupLabel b = getOpt(IntHashTable.find labelTable b, [])             fun isFallsThru b =
919                   case #in_edges cfg b of
920             (* Scan code and insert labels *)                    [(b',_,_)] => (case CFG.fallsThruTo(Cfg,b') of
921             fun insertLabels([], []) = ()                                     SOME b'' => b'' = b
922               | insertLabels(labels, []) = error "orphan labels"                                   | NONE => b' = ENTRY
923               | insertLabels(labels, F.LABEL l::blocks) =                                  )
924                   insertLabels(l::labels, blocks)                 | _ => false
              | insertLabels(labels, (b as F.BBLOCK{blknum,...})::blocks) =  
                  (addLabel(blknum, labels); insertLabels([], blocks))  
              | insertLabels(_, _::blocks) = insertLabels([], blocks)  
                   (* skip labels to pseudo ops *)  
   
            val _ = insertLabels([], blocks)  
   
            (* Does the block falls thru from the previous block? *)  
            fun isFallsThru(F.BBLOCK{pred, blknum=j, ...}) =  
                let fun loop((F.BBLOCK{blknum=i,...},_)::rest) =  
                           i+1 = j orelse loop rest  
                      | loop((F.ENTRY _,_)::_) = true  
                      | loop(_) = false  
                in  loop(!pred)  
                end  
              | isFallsThru _ = false  
925    
926             (* Create jump instruction to a block *)             (* Create jump instruction to a block *)
927             fun jump(F.BBLOCK{blknum,...}) =             fun jump(CFG.BLOCK{labels, ...}) =
928                 (case lookupLabel blknum of                 (case !labels of
929                   []   => error "no label to target of critical edge!"                   []   => error "no label to target of critical edge!"
930                 | l::_ => P.jump l                 | l::_ => P.jump l
931                 )                 )
              | jump _ = error "jump"  
932    
933             (*             (*
934              * Special case: target block has stack depth of 0.              * Special case: target block has stack depth of 0.
# Line 909  Line 937 
937              * all the critical edges.              * all the critical edges.
938              *)              *)
939             fun genPoppingCode(_, []) = ()             fun genPoppingCode(_, []) = ()
940               | genPoppingCode(targetId, edges as (_,target)::_) =               | genPoppingCode(targetBlk, edges as (_,target,_)::_) =
941             let val preds =             let val entries =
942                    map (fn (source, _) =>                    map (fn edge as (source, _, _) =>
943                        let val sourceId = blknumOf source                        let val n  = ST.depth(valOf(A.sub(bindingsOut,source)))
944                            val SOME stackOut = A.sub(bindingsOut,sourceId)                        in  (n, edge) end
                           val n  = ST.depth stackOut  
                       in  (n, source) end  
945                        ) edges                        ) edges
946    
947                 (* Ordered by increasing stack height *)                 (* Ordered by increasing stack height *)
948                 val preds =                 val entries =
949                     ListMergeSort.sort (fn ((n,_),(m,_)) => n > m) preds                     ListMergeSort.sort (fn ((n,_),(m,_)) => n > m) entries
950    
951                 val relocate = isFallsThru target                 val relocate = isFallsThru target
952    
# Line 929  Line 956 
956                 fun makeCode(popCount, rest) =                 fun makeCode(popCount, rest) =
957                     let val code = pop(popCount, [])                     let val code = pop(popCount, [])
958                     in  case rest of                     in  case rest of
959                           [] => if relocate then jump target::code                           [] => if relocate then
960                                      jump(#node_info cfg target)::code
961                                 else code                                 else code
962                         | _  => code                         | _  => code
963                     end                     end
# Line 938  Line 966 
966                  * have to pop the same number of elements                  * have to pop the same number of elements
967                  *)                  *)
968                 fun gen([], h, code) = code                 fun gen([], h, code) = code
969                   | gen((n,b)::rest, _, []) =                   | gen((n,e)::rest, _, []) =
970                       gen(rest, n,                       gen(rest, n,
971                          [NEWEDGE{label=L.newLabel "",preds=ref [b],                          [NEWEDGE{label=L.anon(),
972                                   code=makeCode(n,rest), comment=cleanup}])                                   entries=ref [e],
973                   | gen((n,b)::rest, h, all as (NEWEDGE{preds, ...}::_)) =                                   code=makeCode(n,rest),
974                                     comment=cleanup
975                                    }
976                            ])
977                     | gen((n,e)::rest, h, all as (NEWEDGE{entries, ...}::_)) =
978                       gen(rest,h,                       gen(rest,h,
979                           if n = h then                           if n = h then
980                             (preds := b :: !preds; all)                             (entries := e :: !entries; all)
981                           else                           else
982                             NEWEDGE{label=L.newLabel "", preds=ref [b],                             NEWEDGE{label=L.anon(),
983                                       entries=ref [e],
984                                     code=makeCode(n-h,rest),                                     code=makeCode(n-h,rest),
985                                     comment=cleanup}::all                                     comment=cleanup
986                                      }::all
987                          )                          )
988                 val repairCode = gen(preds, 0, [])                 val repairCode = gen(entries, 0, [])
989             in  (if relocate then addRepairCode' else addRepairCode)             in  (if relocate then addRepairCode' else addRepairCode)
990                   (targetId, repairCode)                   (target, repairCode)
991             end             end
992    
993             (* The general case:             (* The general case:
994              *   Remove dead values, then              *   Remove dead values, then
995              *   Shuffle.              *   Shuffle.
996              *)              *)
997             fun genRepairCode(targetId, stackIn, edges) =             fun genRepairCode(target, targetBlk, stackIn, edges) =
998             let val repairList = ref []             let val repairList = ref []
999                 val repairCount = ref 0                 val repairCount = ref 0
1000                 val SOME stackIn = A.sub(bindingsIn, targetId)                 val SOME stackIn = A.sub(bindingsIn, target)
1001                 fun repair(source, target) =                 fun repair(edge as (source, _, _)) =
1002                 let val F.BBLOCK{blknum=sourceId, ...} = source                 let val SOME stackOut' = A.sub(bindingsOut, source)
                    val SOME stackOut' = A.sub(bindingsOut, sourceId)  
1003                     fun createNewRepairEdge() =                     fun createNewRepairEdge() =
1004                     let val stackOut = ST.copy stackOut'                     let val stackOut = ST.copy stackOut'
1005                         val F.BBLOCK{liveIn, ...} = target                         val liveIn = IntHashTable.lookup liveInTable target
1006                         val liveInSet = removeNonPhysical liveIn                         val liveInSet = removeNonPhysical liveIn
1007                         val _ =                         val _ =
1008                            if debug then                            if debug then
1009                                pr("LiveIn = "^                                pr("LiveIn = "^celllistToString liveIn^"\n")
                                 CB.CellSet.toString (!liveIn)^  
                                  "\n")  
1010                            else ()                            else ()
1011    
1012                         (* deallocate unused values *)                         (* deallocate unused values *)
# Line 985  Line 1016 
1016                         fun addNewEdge() =                         fun addNewEdge() =
1017                         let (* Do we need to relocate this block? *)                         let (* Do we need to relocate this block? *)
1018                             val relocate = !repairCount > 0 orelse                             val relocate = !repairCount > 0 orelse
1019                                            isFallsThru target andalso                                            isFallsThru target
1020                                            sourceId + 1 <> targetId                                            andalso source + 1 <> target
1021    
1022                             (* add a jump to the target block *)                             (* add a jump to the target block *)
1023                             val code = if relocate then jump target::code                             val code = if relocate then jump targetBlk::code
1024                                        else code                                        else code
1025    
1026                             val repairCode =                             val repairCode =
1027                                 NEWEDGE{label=L.newLabel "",                                 NEWEDGE{label=L.anon(),
1028                                         preds=ref [source],                                         entries=ref [edge],
1029                                         code=code, comment=critical}                                         code=code,
1030                                           comment=critical
1031                                          }
1032                         in  repairCount := !repairCount + 1;                         in  repairCount := !repairCount + 1;
1033                             repairList := (repairCode, stackOut')                             repairList := (repairCode, stackOut')
1034                                              :: !repairList;                                              :: !repairList;
1035                             if relocate then                             if relocate then
1036                                addRepairCode'(targetId,                                addRepairCode'(target,
1037                                    repairCode::lookupRepairCode' targetId)                                    repairCode::lookupRepairCode' target)
1038                             else                             else
1039                                addRepairCode(targetId,                                addRepairCode(target,
1040                                   repairCode::lookupRepairCode targetId)                                   repairCode::lookupRepairCode target)
1041                           end
1042                       in  case #out_edges cfg source of
1043                             [(_,j,_)] =>
1044                             if j = target then (*insert code at predecessor*)
1045                                let val CFG.BLOCK{insns,...} =
1046                                      #node_info cfg source
1047                                in  insns := insertAtEnd(!insns, code)
1048                         end                         end
                    in  case source of  
                           F.BBLOCK{succ=ref [(F.BBLOCK{blknum=j,...},_)],  
                                    insns, ...} =>  
                           if j = targetId then (*insert code at predecessor*)  
                              insns := insertAtEnd(!insns, code)  
1049                            else                            else
1050                               addNewEdge()                               addNewEdge()
1051                         | _ => addNewEdge()                         | _ => addNewEdge()
1052                     end                     end
1053    
1054                     fun shareRepairEdge [] = false                     fun shareRepairEdge [] = false
1055                       | shareRepairEdge((NEWEDGE{preds,...},stackOut'')::rest) =                       | shareRepairEdge
1056                            ((NEWEDGE{entries,...},stackOut'')::rest) =
1057                          if ST.equal(stackOut'', stackOut') then                          if ST.equal(stackOut'', stackOut') then
1058                              (preds := source :: !preds; true)                              (entries := edge :: !entries; true)
1059                          else shareRepairEdge rest                          else shareRepairEdge rest
1060    
1061                 in  if shareRepairEdge(!repairList) then ()                 in  if shareRepairEdge(!repairList) then ()
# Line 1029  Line 1065 
1065             end             end
1066    
1067             (*             (*
1068              * Code to split critical edges entering block targetId              * Code to split critical edges entering block target
1069              *)              *)
1070             fun split(targetId, edges) =             fun split(target, edges) =
1071                 let val SOME stackIn = A.sub(bindingsIn,targetId)                 let val SOME stackIn = A.sub(bindingsIn,target)
1072                     fun log(source, target) =                     fun log(s, t, e) =
1073                     let val s = blknumOf source                     let val SOME stackOut = A.sub(bindingsOut,s)
                        val t = blknumOf target  
                        val SOME stackOut = A.sub(bindingsOut,s)  
1074                     in  pr("SPLIT "^i2s s^"->"^i2s t^" "^                     in  pr("SPLIT "^i2s s^"->"^i2s t^" "^
1075                            ST.stackToString stackOut^"->"^                            ST.stackToString stackOut^"->"^
1076                            ST.stackToString stackIn^"\n")                            ST.stackToString stackIn^"\n")
1077                     end                     end
1078                     val _ = if debug andalso !traceOn then app log edges else ()                     val _ = if debug andalso !traceOn then app log edges else ()
1079                 in  if ST.depth stackIn = 0 then genPoppingCode(targetId, edges)                     val targetBlk = #node_info cfg target
1080                     else genRepairCode(targetId, stackIn, edges)                 in  if ST.depth stackIn = 0 then genPoppingCode(targetBlk,edges)
1081                       else genRepairCode(target, targetBlk, stackIn, edges)
1082                 end                 end
1083    
1084             (* Renumber all the blocks and insert compensation code at the  
1085               (*
1086                * Create a new empty cfg with the same graph info as the old one.
1087                *)
1088               val Cfg' as G.GRAPH cfg' = CFG.cfg (#graph_info cfg)
1089    
1090               (*
1091                * Renumber all the blocks and insert compensation code at the
1092              * right places.              * right places.
1093              *)              *)
1094             fun renumberBlocks() =             fun renumberBlocks() =
1095             let val labelTbl = IntHashTable.mkTable(32, Nothing)             let (* Mapping from label to new node ids *)
1096                 val addLabel = IntHashTable.insert labelTbl                 val labelMap = HashTable.mkTable (L.hash,L.same) (32, Nothing)
1097                 fun insertLabel(L.Label{id, ...},block) = addLabel(id, block)                 val mapLabelToId = HashTable.insert labelMap
1098    
1099                 val entries = ref []                 (* Mapping from old id to new id *)
1100                 val exits   = ref []                 val idMap = IntHashTable.mkTable (32, Nothing)
1101                   val mapOldIdToNewId = IntHashTable.insert idMap
1102                 (* retarget the branch of block *)                 val oldIdToNewId = IntHashTable.lookup idMap
1103                 fun retarget(I.JMP(I.ImmedLabel(T.LABEL _), [_])::rest, l) =  
1104                       I.JMP(I.ImmedLabel(T.LABEL l), [l])::rest                 (* Retarget a jump instruction to label l *)
1105                   | retarget(I.JCC{cond,opnd=I.ImmedLabel(T.LABEL _)}::rest,l)=                 fun retargetJump(I.JMP(I.ImmedLabel(T.LABEL _), [_]), l) =
1106                       I.JCC{cond=cond,opnd=I.ImmedLabel(T.LABEL l)}::rest                       I.JMP(I.ImmedLabel(T.LABEL l), [l])
1107                   | retarget(_,l) = error "retarget"                   | retargetJump(I.JCC{cond,opnd=I.ImmedLabel(T.LABEL _)},l)=
1108                         I.JCC{cond=cond,opnd=I.ImmedLabel(T.LABEL l)}
1109                 (* Translate repair code to actual block *)                   | retargetJump(I.ANNOTATION{i,a},l) =
1110                 fun transRepair(n, [], blocks) = (n, blocks)                       I.ANNOTATION{i=retargetJump(i,l),a=a}
1111                   | transRepair(n, NEWEDGE{label, preds, code, comment}::rest,                   | retargetJump(_,l) = error "retargetJump"
1112                                    blocks) =  
1113                     let val blocks = F.LABEL label::blocks                 (*
1114                         val this = F.BBLOCK{blknum=n, freq=ref 0,                  * Given a candidate edge, generate compensation code.
1115                                             pred=ref [],                  *)
1116                                             succ=ref [],                 fun transRepair(n, []) = n
1117                                             annotations=ref comment,                   | transRepair(n, NEWEDGE{label,entries,code,comment}::rest) =
1118                                             liveIn=ref C.empty,                     let val this =
1119                                             liveOut=ref C.empty,                             CFG.BLOCK{id=n,
1120                                             insns=ref code}                                       kind=CFG.NORMAL,
1121                         fun retargetBlock(F.BBLOCK{insns, ...}) =                                       freq=ref 0, (* XXX Wrong frequency! *)
1122                              insns := retarget(!insns, label)                                       data=ref [],
1123                           | retargetBlock _ = ()                                       labels=ref [label],
1124                                         insns=ref code,
1125                                         annotations=ref comment
1126                                        }
1127    
1128                           (*
1129                            * Update the instructions to predecessors of this edge.
1130                            *)
1131                           fun retarget(CFG.BLOCK{kind=CFG.START,...}) = ()
1132                             | retarget(CFG.BLOCK{insns as ref(jmp::rest), ...}) =
1133                                insns := retargetJump(jmp, label)::rest
1134                             | retarget _ = error "retarget"
1135    
1136                           fun retargetEntries(pred,_,CFG.EDGE{a,...}) =
1137                                 (retarget(#node_info cfg pred);
1138                                  a := TargetMovedTo n :: !a
1139                                 )
1140    
1141                     in  if debug andalso !traceOn then                     in  if debug andalso !traceOn then
1142                             pr("Inserting critical edge at block "^i2s n^" "^                             pr("Inserting critical edge at block "^i2s n^" "^
1143                                 L.nameOf label^"\n")                                 L.toString label^"\n")
1144                         else ();                         else ();
1145                         insertLabel(label, this);                         #add_node cfg' (n, this);  (* insert block *)
1146                         app retargetBlock (!preds);                         mapLabelToId(label, n);
1147                         transRepair(n+1, rest, this::blocks)                         app retargetEntries (!entries);
1148                           transRepair(n+1, rest)
1149                     end                     end
1150    
1151                 fun renumber(n, [], pseudoOps, repairCode', blocks) =                 (*
1152                     let val (n, blocks) = transRepair(n, repairCode', blocks)                  * Renumber all the blocks and insert repair code.
1153                         val blocks      = pseudoOps @ blocks                  *)
1154                     in  (n, rev blocks)                 fun renumber(n, [], repairCode') =  transRepair(n, repairCode')
1155                     end                   | renumber(n, (blknum, block as
1156                   | renumber(n, (block as                                   CFG.BLOCK{kind,annotations,insns,freq,
1157                                 F.BBLOCK{blknum,annotations,insns,freq,                                             data, labels, ...})::rest,
1158                                          pred,succ,liveIn,liveOut,...})::rest,                             repairCode') =
                             pseudoOps, repairCode', blocks) =  
1159                     let (* If we have outstanding repair code and this is                     let (* If we have outstanding repair code and this is
1160                          * NOT a fallsthru entry, then insert them here.                          * NOT a fallsthru entry, then insert them here.
1161                          *)                          *)
1162                         val (n, blocks, repairCode') =                         val (n, repairCode') =
1163                            case repairCode' of                            case repairCode' of
1164                              [] => (n, blocks, [])                              [] => (n, [])
1165                            | _  => if isFallsThru block then                            | _  => if isFallsThru blknum then
1166                                      (n, blocks, repairCode')                                      (n, repairCode')
1167                                    else                                    else
1168                                      let val (n, blocks) =                                      (transRepair(n, repairCode'), [])
                                        transRepair(n, repairCode', blocks)  
                                     in (n, blocks, [])  
                                     end  
1169    
1170                         (*  Insert non-relocatable repair code *)                         (*  Insert non-relocatable repair code *)
1171                         val repairCode = lookupRepairCode blknum                         val repairCode = lookupRepairCode blknum
1172                         val (n, blocks) = transRepair(n, repairCode, blocks)                         val n = transRepair(n, repairCode)
1173    
1174                         (*  Create this block *)                         (*  Create this block *)
1175                         val this = F.BBLOCK{blknum=n,annotations=annotations,                         val this = CFG.BLOCK{id=n,
1176                                             freq=freq, insns=insns,                                              kind=kind,
1177                                             pred=ref [], succ=ref [],                                              freq=freq,
1178                                             liveIn=liveIn,liveOut=liveOut                                              data=data,
1179                                                labels=labels,
1180                                                insns=insns,
1181                                                annotations=annotations
1182                                            }                                            }
1183    
1184                         (*  Insert new relocatable repair code *)                         (*  Insert new relocatable repair code *)
1185                         val repairCode' = repairCode' @                         val repairCode' = repairCode' @
1186                                             lookupRepairCode' blknum                                             lookupRepairCode' blknum
1187    
1188                         (*  Insert labels *)                         (*  Insert labels that map to this block *)
1189                         fun insertLabels((p as F.LABEL l)::ps) =                         val _ = app (fn l => mapLabelToId(l, n)) (!labels)
1190                              (insertLabel(l, this); insertLabels ps)  
1191                           | insertLabels(p::ps) = insertLabels ps                         (*  Insert block *)
1192                           | insertLabels [] = blocks                         val _ = #add_node cfg' (n, this)
1193                           val _ = mapOldIdToNewId(blknum, n)
1194                         val _ = insertLabels pseudoOps  
1195                       in  case kind of
1196                         val blocks = this::pseudoOps @ blocks                            CFG.START => #set_entries cfg' [n]
1197                           |  CFG.STOP  => #set_exits cfg' [n]
1198                         fun addEntry((F.ENTRY _,w)::_) =                         |  _         => ();
1199                               entries := (this,w):: !entries                         renumber(n+1, rest, repairCode')
1200                           | addEntry(_::es) = addEntry es                     end
1201                           | addEntry [] = ()  
1202                         fun addExit((F.EXIT _,w)::_) =                 (* Do all the blocks *)
1203                               exits := (this,w) :: !exits                 val n = renumber(0, #nodes cfg (), [])
1204                           | addExit(_::es) = addExit es  
1205                           | addExit [] = ()                 val [newExit] = #exits cfg' ()
1206    
1207                     in  addEntry(!pred); (* check if this is an entry *)                 (*
1208                         addExit(!succ);  (* check if this ia an exit *)                  * Given a label, finds out which block it targets.
1209                         renumber(n+1, rest, [], repairCode', blocks)                  * If not found then it means the block is escaping.
1210                     end                  *)
1211                   | renumber(n, p::rest, pseudoOps, repairCode', blocks) =                 val findLabel = HashTable.find labelMap
1212                       renumber(n, rest, p::pseudoOps, repairCode', blocks)                 fun labelToBlockId l = getOpt(findLabel l, newExit)
1213    
1214                 val (n, blocks) = renumber(0, blocks, [], [], [])                 fun hasJump x =
1215                   let val CFG.BLOCK{insns, ...} = #node_info cfg' x
                (* New entry and exits *)  
                val F.ENTRY{freq=entryFreq, ...} = entry  
                val newEntry = F.ENTRY{blknum=n, freq=entryFreq, succ=entries}  
                val n        = n+1  
                val F.EXIT{freq=exitFreq, ...} = exit  
                val newExit  = F.EXIT{blknum=n, freq=exitFreq, pred=exits}  
                val n        = n+1  
   
                val lookupLabel = IntHashTable.find labelTbl  
                val lookupLabel =  
                    fn l => case lookupLabel l of  
                              SOME b => b  
                            | NONE   => newExit  
   
                fun addPred b (F.BBLOCK{pred, ...},w) = pred := (b,w) :: !pred  
                  | addPred b (F.EXIT{pred, ...},w) = pred := (b,w) :: !pred  
                  | addPred _ _ = error "addPred"  
   
                fun adjustSucc(  
                       (blk as F.BBLOCK{blknum,insns,succ,pred,...})::rest) =  
                    let fun follows(F.LABEL _::rest) = follows rest  
                          | follows((b as F.BBLOCK _)::rest) = (b, ref 0)  
                          | follows [] = (newExit, ref 0)  
                        fun succBlocks([], succ) = succ  
                          | succBlocks(P.ESCAPES::targets, succ) =  
                             succBlocks(targets, (newExit, ref 0)::succ)  
                          | succBlocks(P.FALLTHROUGH::targets, succ) =  
                             succBlocks(targets, follows rest::succ)  
                          | succBlocks(P.LABELLED(L.Label{id,...})::targets,  
                                       succ) =  
                             succBlocks(targets, (lookupLabel id, ref 0)::succ)  
                        fun fallsThru rest = [follows rest]  
1216                     in  case !insns of                     in  case !insns of
1217                           [] => succ := fallsThru rest                       [] => false
1218                       | jmp::_ => P.instrKind jmp = P.IK_JUMP
1219                   end
1220    
1221                   (*
1222                    * Now rebuild all the old edges.
1223                    * For each edge, makes sure the target hasn't been moved.
1224                    *)
1225                   fun renameEdge(x, y, e as CFG.EDGE{a,k,w,...}) =
1226                   let val x = oldIdToNewId x
1227                       val (z, e) =
1228                       case !a of
1229                          TargetMovedTo z::an =>
1230                          let val e =
1231                              case k of
1232                                 (CFG.FALLSTHRU | CFG.BRANCH false) =>
1233                                    if hasJump x then
1234                                      CFG.EDGE{a=a, w=w, k=CFG.JUMP}
1235                                    else e
1236                              | _ => e
1237                          in  a := an;   (* remove the marker *)
1238                              (z, e)
1239                          end
1240                       |   _ => (oldIdToNewId y, e)
1241                   in  #add_edge cfg' (x,z,e)
1242                   end
1243    
1244                   val _ = #forall_edges cfg renameEdge
1245    
1246                   (*
1247                    * Now add new edges x->y where x is a new compensation block
1248                    *)
1249                   fun addNewEdge(NEWEDGE{label, code, entries, ...}) =
1250                   let val x = labelToBlockId label
1251                       val (y, k) =
1252                          case code of
1253                            [] => (x + 1, CFG.FALLSTHRU) (* next block *)
1254                         | jmp::_ =>                         | jmp::_ =>
1255                           case P.instrKind jmp of                           if P.instrKind jmp = P.IK_JUMP then
1256                             P.IK_JUMP =>                              (case P.branchTargets jmp of
1257                                succ := succBlocks(P.branchTargets jmp,[])                                [P.LABELLED l] => (labelToBlockId l, CFG.JUMP)
1258                           | _ => succ := fallsThru rest;                              | _ => error "addNewEdge where is the target?"
1259                         app (addPred blk) (!succ);                              )
1260                         adjustSucc rest                           else
1261                    end                              (x + 1, CFG.FALLSTHRU)
1262                  | adjustSucc(_::rest) = adjustSucc rest                     (* compute weight *)
1263                  | adjustSucc [] = ()                     val w = List.foldr (fn ((_,_,CFG.EDGE{w,...}),n) => !w+n)
1264                                  0 (!entries)
1265                 val _ = adjustSucc blocks                 in  #add_edge cfg' (x, y, CFG.EDGE{a=ref [], w=ref w, k=k})
                val _ = app (addPred entry) (!entries)  
   
            in  F.CLUSTER{blkCounter=ref n,  
                          annotations=annotations,  
                          blocks=blocks,  
                          entry=newEntry,  
                          exit=newExit  
                         }  
1266             end             end
1267    
1268         in  insertLabels([], blocks);                 val addNewEdges = app addNewEdge
1269             IntHashTable.appi split edgesToSplit;                 val _ = IntHashTable.app addNewEdges repairCodeTable
1270             renumberBlocks()                 val _ = IntHashTable.app addNewEdges repairCodeTable'
1271    
1272               in  Cfg'
1273         end         end
1274    
1275           in  IntHashTable.appi split edgesToSplit;
1276               renumberBlocks()
1277           end
1278    
1279         (*------------------------------------------------------------------         (*------------------------------------------------------------------
1280          * Process all blocks          * Process all blocks which are not the entry or the exit
1281          *------------------------------------------------------------------*)          *------------------------------------------------------------------*)
1282         fun rewriteAllBlocks         val stamp = ref 0
1283              (stamp,         fun rewriteAllBlocks (_, CFG.BLOCK{kind=CFG.START, ...}) = ()
1284               (block as F.BBLOCK{blknum, insns, liveIn, liveOut,           | rewriteAllBlocks (_, CFG.BLOCK{kind=CFG.STOP, ...}) = ()
1285                                  annotations, pred, succ, ...})::rest) =           | rewriteAllBlocks
1286              let val stamp = rewrite(stamp, blknum, block,              (blknum, block as CFG.BLOCK{insns, labels, annotations, ...}) =
1287                let val _ =
1288                      if debug andalso !debugOn then
1289                          app (fn l => pr(L.toString l^":\n")) (!labels)
1290                      else ();
1291                    val liveIn  = HT.lookup liveInTable blknum
1292                    val liveOut = HT.lookup liveOutTable blknum
1293                    val st = rewrite(!stamp, blknum, block,
1294                                      insns, liveIn, liveOut,                                      insns, liveIn, liveOut,
1295                                      pred, succ, annotations)                                      annotations)
1296              in  rewriteAllBlocks(stamp+1, rest)              in  stamp := st (* update stamp *)
1297              end              end
          | rewriteAllBlocks(stamp, F.LABEL l::rest) =  
             (if debug andalso !debugOn then pr(Label.nameOf l^":\n") else ();  
              rewriteAllBlocks(stamp, rest)  
             )  
          | rewriteAllBlocks(stamp, _::rest) = rewriteAllBlocks(stamp, rest)  
          | rewriteAllBlocks(stamp, []) = ()  
1298    
1299         (*------------------------------------------------------------------         (*------------------------------------------------------------------
1300          * Translate code within a basic block.          * Translate code within a basic block.
# Line 1241  Line 1302 
1302          * uses.          * uses.
1303          *------------------------------------------------------------------*)          *------------------------------------------------------------------*)
1304         and rewrite(stamp, blknum, block, insns, liveIn, liveOut,         and rewrite(stamp, blknum, block, insns, liveIn, liveOut,
1305                     pred, succ, annotations) =                     annotations) =
1306         let val (stackIn, stack, code) = shuffleIn(blknum, block, pred, liveIn)         let val (stackIn, stack, code) = shuffleIn(blknum, block, liveIn)
1307    
1308             (* Dump instructions when encountering a bug *)             (* Dump instructions when encountering a bug *)
1309             fun bug msg =             fun bug msg =
# Line 1823  Line 1884 
1884             (* Dump the initial code *)             (* Dump the initial code *)
1885             val _ = if debug andalso !debugOn then             val _ = if debug andalso !debugOn then
1886                      (pr("-------- block "^i2s blknum^" ----"^                      (pr("-------- block "^i2s blknum^" ----"^
1887                           CB.CellSet.toString (!liveIn)^" "^                           celllistToString liveIn^" "^
1888                           ST.stackToString stackIn^"\n");                           ST.stackToString stackIn^"\n");
1889                       dump (!insns)                       dump (!insns);
1890                         pr("succ=");
1891                         app (fn b => pr(i2s b^" ")) (#succ cfg blknum);
1892                         pr("\n")
1893                      )                      )
1894                     else ()                     else ()
1895    
# Line 1836  Line 1900 
1900             val (stamp, insns') = loop(stamp, rev(!insns), lastUse, code)             val (stamp, insns') = loop(stamp, rev(!insns), lastUse, code)
1901    
1902             (* Insert shuffle code at the end if necessary *)             (* Insert shuffle code at the end if necessary *)
1903             val insns' = shuffleOut(stack, insns', blknum, block, succ, liveOut)             val insns' = shuffleOut(stack, insns', blknum, block, liveOut)
1904    
1905             (* Dump translation *)             (* Dump translation *)
1906             val _ = if debug andalso !debugOn then             val _ = if debug andalso !debugOn then
1907                       (pr("-------- translation "^i2s blknum^"----"^                       (pr("-------- translation "^i2s blknum^"----"^
1908                           CB.CellSet.toString (!liveIn)^" "^                           celllistToString liveIn^" "^
1909                           ST.stackToString stackIn^"\n");                           ST.stackToString stackIn^"\n");
1910                        dump insns';                        dump insns';
1911                        pr("-------- done "^i2s blknum^"----"^                        pr("-------- done "^i2s blknum^"----"^
1912                           CB.CellSet.toString (!liveOut)^" "^                           celllistToString liveOut^" "^
1913                           ST.stackToString stack^"\n")                           ST.stackToString stack^"\n")
1914                       )                       )
1915                    else ()                    else ()
# Line 1860  Line 1924 
1924         end (* process *)         end (* process *)
1925    
1926     in  (* Translate all blocks *)     in  (* Translate all blocks *)
1927         rewriteAllBlocks(C.firstPseudo, blocks);         stamp := C.firstPseudo;
1928           #forall_nodes cfg rewriteAllBlocks;
1929         (* If we found critical edges, then we have to split them... *)         (* If we found critical edges, then we have to split them... *)
1930         if IntHashTable.numItems edgesToSplit = 0 then cluster         if IntHashTable.numItems edgesToSplit = 0 then Cfg
1931         else repairCriticalEdges(cluster)         else repairCriticalEdges(Cfg)
1932     end     end
 *)  
1933  end (* functor *)  end (* functor *)
1934    
1935  end (* local *)  end (* local *)

Legend:
Removed from v.909  
changed lines
  Added in v.925

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