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 1155, Wed Mar 20 20:52:51 2002 UTC revision 1156, Thu Mar 21 22:01:11 2002 UTC
# Line 86  Line 86 
86     structure CB = CellsBasis     structure CB = CellsBasis
87     structure SL = CB.SortedCells     structure SL = CB.SortedCells
88     structure HT = IntHashTable     structure HT = IntHashTable
89       structure IM = IntRedBlackMap
90    
91     type flowgraph = CFG.cfg     type flowgraph = CFG.cfg
92     type an = An.annotations     type an = An.annotations
# Line 883  Line 884 
884          *       consistent with the order of the id.          *       consistent with the order of the id.
885          *------------------------------------------------------------------*)          *------------------------------------------------------------------*)
886         fun repairCriticalEdges(Cfg as G.GRAPH cfg) =         fun repairCriticalEdges(Cfg as G.GRAPH cfg) =
887         let (* Data structure for recording critical edge splitting info *)         let
            datatype compensationCode =  
              NEWEDGE of  
                 {label:L.label,               (* label of new block *)  
                  entries:CFG.edge list ref,   (* edges going into this code *)  
                  code:I.instruction list,     (* code *)  
                  freq:CFG.weight ref,  
                  comment:an  
                 }  
   
888             val cleanup = [#create MLRiscAnnotations.COMMENT "cleanup edge"]             val cleanup = [#create MLRiscAnnotations.COMMENT "cleanup edge"]
889             val critical = [#create MLRiscAnnotations.COMMENT "critical edge"]             val critical = [#create MLRiscAnnotations.COMMENT "critical edge"]
890    
891             exception Nothing             fun annotate(gen, an) =
892                 app (fn ((_,CFG.BLOCK{annotations, ...}),_) => annotations := an)
893             (* Repair code table; mapping from block id -> compensation code *)                   gen
            val repairCodeTable  = IntHashTable.mkTable(32, Nothing)  
            val addRepairCode    = IntHashTable.insert repairCodeTable  
            fun lookupRepairCode b =  
                 getOpt(IntHashTable.find repairCodeTable b,[])  
   
            (* Repair code table; mapping from block id -> compensation code  
             * These must be relocated ...  
             *)  
            val repairCodeTable'  = IntHashTable.mkTable(32, Nothing)  
            val addRepairCode'    = IntHashTable.insert repairCodeTable'  
            fun lookupRepairCode' b =  
                 getOpt(IntHashTable.find repairCodeTable' b,[])  
   
            (* Does the given block falls thru from the previous block?  
             * If the previous block is ENTRY then also consider this to be true  
             *)  
            fun isFallsThru b =  
                case #in_edges cfg b of  
                   [(b',_,_)] => (case CFG.fallsThruTo(Cfg,b') of  
                                    SOME b'' => b'' = b  
                                  | NONE => b' = ENTRY  
                                 )  
                | _ => false  
   
            (* Create jump instruction to a block *)  
            fun jump(CFG.BLOCK{labels, ...}) =  
                (case !labels of  
                  []   => error "no label to target of critical edge!"  
                | l::_ => P.jump l  
                )  
894    
895             (*             (*
896              * Special case: target block has stack depth of 0.              * Special case: target block has stack depth of 0.
# Line 937  Line 899 
899              * all the critical edges.              * all the critical edges.
900              *)              *)
901             fun genPoppingCode(_, []) = ()             fun genPoppingCode(_, []) = ()
902               | genPoppingCode(targetBlk, edges as (_,target,_)::_) =               | genPoppingCode(targetId, edges) =
903             let val entries =             let (* Edges annotated with the source stack depth
904                    map (fn edge as (source, _, _) =>                  * Ordered by increasing stack height
905                        let val n  = ST.depth(valOf(A.sub(bindingsOut,source)))                  *)
906                        in  (n, edge) end                 val edges =
907                        ) edges                   IM.listItemsi
908                      (foldr (fn (edge as (sourceId, _, _), M) =>
909                 (* Ordered by increasing stack height *)                      let val n = ST.depth(valOf(A.sub(bindingsOut,sourceId)))
910                 val entries =                      in  IM.insert(M, n, edge :: getOpt(IM.find(M, n), []))
911                     ListMergeSort.sort (fn ((n,_),(m,_)) => n > m) entries                      end) IM.empty edges)
912    
913                 val relocate = isFallsThru target                 (* Generate n pops *)
914                   fun pops(0, code) = code
915                 fun pop(0, code) = code                   | pops(n, code) = pops(n-1, POP_ST::code)
916                   | pop(n, code) = pop(n-1,POP_ST::code)  
917                   (* Create the chain of blocks *)
918                 fun makeCode(popCount, rest) =                 fun makeChain(depth, [], chain) = chain
919                     let val code = pop(popCount, [])                   | makeChain(depth, (d, es)::es', chain) =
920                     in  case rest of                     let val code = pops(d - depth, [])
921                           [] => if relocate then                     in  makeChain(d, es', (es, code)::chain)
                                   jump(#node_info cfg target)::code  
                                else code  
                        | _  => code  
922                     end                     end
923    
924                 (* Generate code, share code between edges that                 val chain = makeChain(0, edges, [])
925                  * have to pop the same number of elements  
926                  *)             in  annotate(CFG.splitEdges Cfg {groups=chain, jump=false}, cleanup)
                fun gen([], h, code) = code  
                  | gen((n,e)::rest, _, []) =  
                    let val w = computeFreq e  
                    in  gen(rest, n,  
                         [NEWEDGE{label=L.anon(),  
                                  entries=ref [e],  
                                  code=makeCode(n,rest),  
                                  freq=ref w,  
                                  comment=cleanup  
                                 }  
                         ])  
927                     end                     end
928                   | gen((n,e)::rest, h,  
929                          all as (NEWEDGE{entries, freq, ...}::_)) =             (*
930                     let val w = computeFreq e              * Generate repair code.
931                     in  gen(rest,n,              *)
932                           if n = h then             fun genRepairCode(targetId, stackIn, edges) =
933                             (entries := e :: !entries;             let val liveIn = IntHashTable.lookup liveInTable targetId
                             freq := !freq + w;  
                             all)  
                          else  
                            NEWEDGE{label=L.anon(),  
                                    entries=ref [e],  
                                    code=makeCode(n-h,rest),  
                                    freq=ref w,  
                                    comment=cleanup  
                                   }::all  
                         )  
                     end  
                val repairCode = gen(entries, 0, [])  
   
                (* Add frequencies of fallsthru block *)  
                fun updateFreq(w, NEWEDGE{freq=w1, ...}::es) =  
                    let val w = w + !w1  
                    in  w1 := w; updateFreq(w, es)  
                    end  
                  | updateFreq(w, []) = ()  
   
                val () = updateFreq(0.0, repairCode)  
            in  (if relocate then addRepairCode' else addRepairCode)  
                  (target, repairCode)  
            end  
   
            (* The general case:  
             *   Remove dead values, then  
             *   Shuffle.  
             *)  
            fun genRepairCode(target, targetBlk, stackIn, edges) =  
            let val repairList = ref []  
                val repairCount = ref 0  
                val SOME stackIn = A.sub(bindingsIn, target)  
                fun repair(edge as (source, _, _)) =  
                let val SOME stackOut' = A.sub(bindingsOut, source)  
                    fun createNewRepairEdge() =  
                    let val stackOut = ST.copy stackOut'  
                        val liveIn = IntHashTable.lookup liveInTable target  
934                         val liveInSet = removeNonPhysical liveIn                         val liveInSet = removeNonPhysical liveIn
935                         val _ =                 val _ = if debug then
                           if debug then  
936                                pr("LiveIn = "^celllistToString liveIn^"\n")                                pr("LiveIn = "^celllistToString liveIn^"\n")
937                            else ()                            else ()
938    
939                         (* deallocate unused values *)                 (* Group all edges whose output stack configurations
940                         val code = removeDeadValues(stackOut, liveInSet, [])                  * are the same.  Each group is merged together into
941                         (* shuffle values  *)                  * a single compensation block
942                         val code = shuffle(stackOut, stackIn, code)                  *)
943                         fun addNewEdge() =                 fun partition([], S) = S
944                         let (* Do we need to relocate this block? *)                   | partition((e as (src,_,_))::es, S) =
945                             val relocate = !repairCount > 0 orelse                     let val stackOut = ST.copy(valOf(A.sub(bindingsOut,src)))
946                                            isFallsThru target                         fun find([], S) = partition(es, ([e],stackOut)::S)
947                                            andalso source + 1 <> target                           | find((x as (es',st'))::S', S) =
948                               if ST.equal(stackOut,st') then
949                             (* add a jump to the target block *)                                partition(es, (e::es',st')::S' @ S)
                            val code = if relocate then jump targetBlk::code  
                                       else code  
   
                            val repairCode =  
                                NEWEDGE{label=L.anon(),  
                                        entries=ref [edge],  
                                        code=code,  
                                        freq=ref(computeFreq edge),  
                                        comment=critical  
                                       }  
                        in  repairCount := !repairCount + 1;  
                            repairList := (repairCode, stackOut')  
                                             :: !repairList;  
                            if relocate then  
                               addRepairCode'(target,  
                                   repairCode::lookupRepairCode' target)  
950                             else                             else
951                                addRepairCode(target,                                find(S', x::S)
952                                   repairCode::lookupRepairCode target)                     in  find(S, [])
                        end  
                    in  case #out_edges cfg source of  
                          [(_,j,_)] =>  
                          if j = target then (*insert code at predecessor*)  
                             let val CFG.BLOCK{insns,...} =  
                                   #node_info cfg source  
                             in  insns := insertAtEnd(!insns, code)  
                             end  
                          else  
                             addNewEdge()  
                        | _ => addNewEdge()  
953                     end                     end
954    
955                     fun shareRepairEdge [] = false                 (* Partition by the source bindings *)
956                       | shareRepairEdge                 val S = partition(edges, [])
957                          ((NEWEDGE{entries,...},stackOut'')::rest) =  
958                          if ST.equal(stackOut'', stackOut') then                 (* Compute frequencies *)
959                              (entries := edge :: !entries; true)                 val S = map (fn (es,st) => (CFG.sumEdgeFreqs es,es,st)) S
                         else shareRepairEdge rest  
960    
961                 in  if shareRepairEdge(!repairList) then ()                 (* Ordered by non-increasing frequencies *)
962                     else createNewRepairEdge()                 val S = ListMergeSort.sort (fn ((x,_,_),(y,_,_)) => x < y) S
963    
964                   (* Generate code *)
965                   fun gen(freq, edges, stackOut) =
966                   let     (* deallocate unused values *)
967                       val code = removeDeadValues(stackOut,liveInSet,[])
968                           (* shuffle values  *)
969                       val code = shuffle(stackOut, stackIn, code)
970                   in  annotate(
971                          CFG.splitEdges Cfg {groups=[(edges,code)], jump=false},
972                                critical)
973                 end                 end
974             in  app repair edges  
975               in  app gen S
976             end             end
977    
978             (*             (* Split all edges entering targetId *)
979              * Code to split critical edges entering block target             fun split(targetId, edges) =
980              *)             let val stackIn = valOf(A.sub(bindingsIn,targetId))
            fun split(target, edges) =  
                let val SOME stackIn = A.sub(bindingsIn,target)  
981                     fun log(s, t, e) =                     fun log(s, t, e) =
982                     let val SOME stackOut = A.sub(bindingsOut,s)                     let val SOME stackOut = A.sub(bindingsOut,s)
983                     in  pr("SPLIT "^i2s s^"->"^i2s t^" "^                     in  pr("SPLIT "^i2s s^"->"^i2s t^" "^
# Line 1095  Line 985 
985                            ST.stackToString stackIn^"\n")                            ST.stackToString stackIn^"\n")
986                     end                     end
987                     val _ = if debug andalso !traceOn then app log edges else ()                     val _ = if debug andalso !traceOn then app log edges else ()
988                     val targetBlk = #node_info cfg target             in  if ST.depth stackIn = 0 then genPoppingCode(targetId, edges)
989                 in  if ST.depth stackIn = 0 then genPoppingCode(targetBlk,edges)                 else genRepairCode(targetId, stackIn, edges)
                    else genRepairCode(target, targetBlk, stackIn, edges)  
                end  
   
   
            (*  
             * Create a new empty cfg with the same graph info as the old one.  
             *)  
            val Cfg' as G.GRAPH cfg' = CFG.cfg (#graph_info cfg)  
   
            (*  
             * Renumber all the blocks and insert compensation code at the  
             * right places.  
             *)  
            fun renumberBlocks() =  
            let (* Mapping from label to new node ids *)  
                val labelMap = HashTable.mkTable (L.hash,L.same) (32, Nothing)  
                val mapLabelToId = HashTable.insert labelMap  
   
                (* Mapping from old id to new id *)  
                val idMap = IntHashTable.mkTable (32, Nothing)  
                val mapOldIdToNewId = IntHashTable.insert idMap  
                val oldIdToNewId = IntHashTable.lookup idMap  
   
                (* Retarget a jump instruction to label l *)  
                fun retargetJump(I.INSTR(I.JMP(I.ImmedLabel(T.LABEL _), [_])), l) =  
                      I.jmp(I.ImmedLabel(T.LABEL l), [l])  
                  | retargetJump(I.INSTR(I.JCC{cond,opnd=I.ImmedLabel(T.LABEL _)}),l)=  
                      I.jcc{cond=cond,opnd=I.ImmedLabel(T.LABEL l)}  
                  | retargetJump(I.ANNOTATION{i,a},l) =  
                      I.ANNOTATION{i=retargetJump(i,l),a=a}  
                  | retargetJump(_,l) = error "retargetJump"  
   
                (*  
                 * Given a candidate edge, generate compensation code.  
                 *)  
                fun transRepair(n, []) = n  
                  | transRepair(n,  
                         NEWEDGE{label,entries,code,freq,comment}::rest) =  
                    let val this =  
                            CFG.BLOCK{id=n,  
                                      kind=CFG.NORMAL,  
                                      freq=ref(!freq),  
                                      labels=ref [label],  
                                      insns=ref code,  
                                      annotations=ref comment,  
                                      align=ref NONE  
                                     }  
   
                        (*  
                         * Update the instructions to predecessors of this edge.  
                         *)  
                        fun retarget(CFG.BLOCK{kind=CFG.START,...}) = ()  
                          | retarget(CFG.BLOCK{insns as ref(jmp::rest), ...}) =  
                             insns := retargetJump(jmp, label)::rest  
                          | retarget _ = error "retarget"  
   
                        fun retargetEntries(pred,_,CFG.EDGE{a,...}) =  
                              (retarget(#node_info cfg pred);  
                               a := TargetMovedTo n :: !a  
                              )  
   
                    in  if debug andalso !traceOn then  
                            pr("Inserting critical edge at block "^i2s n^" "^  
                                L.toString label^"\n")  
                        else ();  
                        #add_node cfg' (n, this);  (* insert block *)  
                        mapLabelToId(label, n);  
                        app retargetEntries (!entries);  
                        transRepair(n+1, rest)  
                    end  
   
                (*  
                 * Renumber all the blocks and insert repair code.  
                 *)  
                fun renumber(n, [], repairCode') =  transRepair(n, repairCode')  
                  | renumber(n, (blknum, block as  
                                  CFG.BLOCK{kind,annotations,insns,freq,align,labels, ...})::rest,  
                            repairCode') =  
                    let (* If we have outstanding repair code and this is  
                         * NOT a fallsthru entry, then insert them here.  
                         *)  
                        val (n, repairCode') =  
                           case repairCode' of  
                             [] => (n, [])  
                           | _  => if isFallsThru blknum then  
                                     (n, repairCode')  
                                   else  
                                     (transRepair(n, repairCode'), [])  
   
                        (*  Insert non-relocatable repair code *)  
                        val repairCode = lookupRepairCode blknum  
                        val n = transRepair(n, repairCode)  
   
                        (*  Create this block *)  
                        val this = CFG.BLOCK{id=n,  
                                             kind=kind,  
                                             freq=freq,  
                                             align=align,  
                                             labels=labels,  
                                             insns=insns,  
                                             annotations=annotations  
                                            }  
   
                        (*  Insert new relocatable repair code *)  
                        val repairCode' = repairCode' @  
                                            lookupRepairCode' blknum  
   
                        (*  Insert labels that map to this block *)  
                        val _ = app (fn l => mapLabelToId(l, n)) (!labels)  
   
                        (*  Insert block *)  
                        val _ = #add_node cfg' (n, this)  
                        val _ = mapOldIdToNewId(blknum, n)  
   
                    in  case kind of  
                           CFG.START => #set_entries cfg' [n]  
                        |  CFG.STOP  => #set_exits cfg' [n]  
                        |  _         => ();  
                        renumber(n+1, rest, repairCode')  
                    end  
   
                (* Do all the blocks *)  
                val n = renumber(0, #nodes cfg (), [])  
   
                val [newExit] = #exits cfg' ()  
   
                (*  
                 * Given a label, finds out which block it targets.  
                 * If not found then it means the block is escaping.  
                 *)  
                val findLabel = HashTable.find labelMap  
                fun labelToBlockId l = getOpt(findLabel l, newExit)  
   
                fun hasJump x =  
                let val CFG.BLOCK{insns, ...} = #node_info cfg' x  
                in  case !insns of  
                      [] => false  
                    | jmp::_ => P.instrKind jmp = P.IK_JUMP  
                end  
   
                (*  
                 * Now rebuild all the old edges.  
                 * For each edge, makes sure the target hasn't been moved.  
                 *)  
                fun renameEdge(x, y, e as CFG.EDGE{a,k,w,...}) =  
                let val x = oldIdToNewId x  
                    val (z, e) =  
                    case !a of  
                       TargetMovedTo z::an =>  
                       let val e =  
                           case k of  
                              (CFG.FALLSTHRU | CFG.BRANCH false) =>  
                                 if hasJump x then  
                                   CFG.EDGE{a=a, w=w, k=CFG.JUMP}  
                                 else e  
                           | _ => e  
                       in  a := an;   (* remove the marker *)  
                           (z, e)  
                       end  
                    |   _ => (oldIdToNewId y, e)  
                in  #add_edge cfg' (x,z,e)  
                end  
   
                val _ = #forall_edges cfg renameEdge  
   
                (*  
                 * Now add new edges x->y where x is a new compensation block  
                 *)  
                fun addNewEdge(NEWEDGE{label, code, freq, entries, ...}) =  
                let val x = labelToBlockId label  
                    val (y, k) =  
                       case code of  
                         [] => (x + 1, CFG.FALLSTHRU) (* next block *)  
                       | jmp::_ =>  
                          if P.instrKind jmp = P.IK_JUMP then  
                             (case P.branchTargets jmp of  
                               [P.LABELLED l] => (labelToBlockId l, CFG.JUMP)  
                             | _ => error "addNewEdge where is the target?"  
                             )  
                          else  
                             (x + 1, CFG.FALLSTHRU)  
                    (* compute weight *)  
                    val w = !freq  
                in  #add_edge cfg' (x, y, CFG.EDGE{a=ref [], w=ref w, k=k})  
                end  
   
                val addNewEdges = app addNewEdge  
                val _ = IntHashTable.app addNewEdges repairCodeTable  
                val _ = IntHashTable.app addNewEdges repairCodeTable'  
   
            in  Cfg'  
990             end             end
991    
992         in  IntHashTable.appi split edgesToSplit;         in  IntHashTable.appi split edgesToSplit;
993             renumberBlocks()             CFG.changed Cfg;
994               Cfg
995         end         end
996    
997         (*------------------------------------------------------------------         (*------------------------------------------------------------------
# Line 1649  Line 1349 
1349                  * So we can always use it as temporary space if we                  * So we can always use it as temporary space if we
1350                  * have run out.                  * have run out.
1351                  *)                  *)
1352                 fun fcmp{fsize,lsrc,rsrc} =                 fun fcmp{i,fsize,lsrc,rsrc} =
1353                 let fun fucompp() =                 let fun fucompp code =
1354                         (ST.pop stack; ST.pop stack; mark(I.fucompp,an))                        (ST.pop stack; ST.pop stack;
1355                           if i then
1356                              POP_ST ::  mark(I.fucomip(ST 1), an) :: code
1357                            else
1358                              mark(I.fucompp,an) :: code
1359                          )
1360                     fun fucomp(n) =                     fun fucomp(n) =
1361                         (ST.pop stack; mark(I.fucomp(ST n),an))                         (ST.pop stack;
1362                     fun fucom(n) = mark(I.fucom(ST n),an)                          mark((if i then I.fucomip else I.fucomp)(ST n),an))
1363                       fun fucom(n) =
1364                            mark((if i then I.fucomi else I.fucom)(ST n),an)
1365    
1366                     fun genmemcmp() =                     fun genmemcmp() =
1367                         let val code = movememtotop(fsize, rsrc, code)                         let val code = movememtotop(fsize, rsrc, code)
1368                             val code = movememtotop(fsize, lsrc, code)                             val code = movememtotop(fsize, lsrc, code)
1369                         in  FINISH(fucompp()::code)                         in  FINISH(fucompp(code))
1370                         end                         end
1371    
1372                     fun genmemregcmp(lsrc, fy) =                     fun genmemregcmp(lsrc, fy) =
# Line 1670  Line 1377 
1377                         | (true, n) =>                         | (true, n) =>
1378                           let val code = if n = 0 then code else xch n::code                           let val code = if n = 0 then code else xch n::code
1379                               val code = movememtotop(fsize, lsrc, code)                               val code = movememtotop(fsize, lsrc, code)
1380                           in  FINISH(fucompp()::code)                           in  FINISH(fucompp(code))
1381                           end                           end
1382    
1383                     fun genregmemcmp(fx, rsrc) =                     fun genregmemcmp(fx, rsrc) =
# Line 1685  Line 1392 
1392                                 let val code = movememtotop(fsize, rsrc, code)                                 let val code = movememtotop(fsize, rsrc, code)
1393                                 in  push(n+1)::code                                 in  push(n+1)::code
1394                                 end                                 end
1395                     in  FINISH(fucompp()::code)                     in  FINISH(fucompp(code))
1396                     end                     end
1397    
1398                     (* Deal with the special case when both sources are                     (* Deal with the special case when both sources are
# Line 1717  Line 1424 
1424                                       xch sx::code)                                       xch sx::code)
1425    
1426                                 (* Generate the appropriate comparison op *)                                 (* Generate the appropriate comparison op *)
1427                                 val (sy, cmp, popY) =                                 val (sy, code, popY) =
1428                                     case (dx, dy, sy) of                                     case (dx, dy, sy) of
1429                                       (true, true, 0) => (~1, fucompp(), false)                                       (true, true, 0) => (~1,fucompp code, false)
1430                                     | (true, _, _)    => (sy-1, fucomp sy, dy)                                     | (true, _, _)  => (sy-1,fucomp sy::code,dy)
1431                                     | (false, _, _)   => (sy, fucom sy, dy)                                     | (false, _, _) => (sy, fucom sy::code, dy)
   
                                val code = cmp::code  
1432    
1433                                 (* Pop fy if it is dead and hasn't already                                 (* Pop fy if it is dead and hasn't already
1434                                  * been popped.                                  * been popped.
# Line 1841  Line 1546 
1546                        I.FILD _ | I.FILDL _ | I.FILDLL _ |                        I.FILD _ | I.FILDL _ | I.FILDLL _ |
1547                        I.FENV _ | I.FBINARY _ | I.FIBINARY _ | I.FUNARY _ |                        I.FENV _ | I.FBINARY _ | I.FIBINARY _ | I.FUNARY _ |
1548                        I.FUCOMPP | I.FUCOM _ | I.FUCOMP _ | I.FCOMPP | I.FXCH _ |                        I.FUCOMPP | I.FUCOM _ | I.FUCOMP _ | I.FCOMPP | I.FXCH _ |
1549                          I.FCOMI _ | I.FCOMIP _ | I.FUCOMI _ | I.FUCOMIP _ |
1550                        I.FSTPL _ | I.FSTPS _ | I.FSTPT _ | I.FSTL _ | I.FSTS _                        I.FSTPL _ | I.FSTPS _ | I.FSTPT _ | I.FSTL _ | I.FSTS _
1551                       ) => bug("Illegal FP instructions")                       ) => bug("Illegal FP instructions")
1552    

Legend:
Removed from v.1155  
changed lines
  Added in v.1156

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