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/SSA/ssa.sml
ViewVC logotype

Diff of /sml/trunk/src/MLRISC/SSA/ssa.sml

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

revision 695, Mon Aug 7 23:57:38 2000 UTC revision 744, Fri Dec 8 04:11:42 2000 UTC
# Line 12  Line 12 
12     structure DJ         : DJ_GRAPH     structure DJ         : DJ_GRAPH
13     structure GCMap      : GC_MAP     structure GCMap      : GC_MAP
14       sharing SSAProps.I = InsnProps.I = CFG.I = FormatInsn.I = MLTreeComp.I       sharing SSAProps.I = InsnProps.I = CFG.I = FormatInsn.I = MLTreeComp.I
15       sharing MLTreeComp.T.Basis = SSAProps.RTL.T.Basis       sharing MLTreeComp.T = SSAProps.RTL.T
16    ) : SSA =    ) : SSA =
17  struct  struct
18     structure CFG        = CFG     structure CFG        = CFG
# Line 61  Line 61 
61     type pos    = int             (* position within a block *)     type pos    = int             (* position within a block *)
62     type block  = Graph.node_id   (* block id *)     type block  = Graph.node_id   (* block id *)
63     type ssa_id = Graph.node_id   (* ssa id *)     type ssa_id = Graph.node_id   (* ssa id *)
64     type rtl    = SP.RTL.rtl      (* RTL *)     type rtl    = RTL.rtl         (* RTL *)
65     type const  = SP.OT.const     (* constants *)     type const  = OT.const        (* constants *)
66     type cfg = CFG.cfg            (* control flow graph *)     type cfg = CFG.cfg            (* control flow graph *)
67     type dom = (CFG.block,CFG.edge_info,CFG.info) Dom.dominator_tree     type dom = (CFG.block,CFG.edge_info,CFG.info) Dom.dominator_tree
68     type nameTbl = {oldName:C.cell, index:int} Intmap.intmap     type nameTbl = {oldName:C.cell, index:int} IntHashTable.hash_table
69    
70     (*------------------------------------------------------------------------     (*------------------------------------------------------------------------
71      * An SSA op is an instruction      * An SSA op is an instruction
# Line 87  Line 87 
87         defsTbl         : value list DA.array,         defsTbl         : value list DA.array,
88         succTbl         : value Graph.edge list DA.array,         succTbl         : value Graph.edge list DA.array,
89         ssaOpTbl        : ssa_op DA.array,         ssaOpTbl        : ssa_op DA.array,
90         cellKindTbl     : C.cellkind Intmap.intmap,         cellKindTbl     : C.cellkind IntHashTable.hash_table,
91         operandTbl      : OT.operandTable,         operandTbl      : OT.operandTable,
92         nameTbl         : nameTbl option,         nameTbl         : nameTbl option,
93         gcmap           : GCMap.gcmap option,         gcmap           : GCMap.gcmap option,
# Line 140  Line 140 
140         val defSiteTbl  = DA.array(13, ~1)         val defSiteTbl  = DA.array(13, ~1)
141         val blockTbl    = DA.array(13, ~1)         val blockTbl    = DA.array(13, ~1)
142         val posTbl      = DA.array(13, ~1)         val posTbl      = DA.array(13, ~1)
143         val rtlTbl      = DA.array(13, RTL.COPY)         val rtlTbl      = DA.array(13, T.SEQ [])
144         val usesTbl     = DA.array(13, [])         val usesTbl     = DA.array(13, [])
145         val defsTbl     = DA.array(13, [])         val defsTbl     = DA.array(13, [])
146         val succTbl     = DA.array(13, [])         val succTbl     = DA.array(13, [])
147         val ssaOpTbl    = DA.array(13, InsnProps.nop())         val ssaOpTbl    = DA.array(13, InsnProps.nop())
148         val cellKindTbl = Intmap.new(13, NoCellKind)         val cellKindTbl = IntHashTable.mkTable(13, NoCellKind)
149         val operandTbl  = OT.create nextImmed         val operandTbl  = OT.create nextImmed
150         val nodeCount   = ref 0         val nodeCount   = ref 0
151         val edgeCount   = ref 0         val edgeCount   = ref 0
# Line 338  Line 338 
338     let val {cfg, dom, ...} = info SSA   (* extracts the dominator *)     let val {cfg, dom, ...} = info SSA   (* extracts the dominator *)
339     in  dom cfg end     in  dom cfg end
340     fun cfg SSA = #cfg(info SSA)   (* extracts the CFG *)     fun cfg SSA = #cfg(info SSA)   (* extracts the CFG *)
341     fun immed SSA = OT.immed(#operandTbl(info SSA)) (* create a new operand *)     fun immed SSA = OT.int(#operandTbl(info SSA)) (* create a new operand *)
342     (*fun label SSA = OT.label(#operandTbl(info SSA))*) (* create a new label *)     (*fun label SSA = OT.label(#operandTbl(info SSA))*) (* create a new label *)
343     fun const SSA = OT.const(#operandTbl(info SSA)) (* lookup const values *)     fun const SSA = OT.const(#operandTbl(info SSA)) (* lookup const values *)
344     fun operand SSA = OT.operand(#operandTbl(info SSA))     fun operand SSA = OT.operand(#operandTbl(info SSA))
# Line 410  Line 410 
410      * Pretty printing a value      * Pretty printing a value
411      *------------------------------------------------------------------------*)      *------------------------------------------------------------------------*)
412     fun prInt i = if i < 0 then "-"^i2s(~i) else i2s i     fun prInt i = if i < 0 then "-"^i2s(~i) else i2s i
413       fun prIntInf i = if IntInf.sign i < 0 then
414                           "-"^IntInf.toString(IntInf.~ i)
415                        else IntInf.toString i
416     fun showVal SSA =     fun showVal SSA =
417     let val {nameTbl, cellKindTbl, gcmap, ...} = info SSA     let val {nameTbl, cellKindTbl, gcmap, ...} = info SSA
418         val const = const SSA         val const = const SSA
419         val cellKind = Intmap.mapWithDefault(cellKindTbl, C.GP)         val cellKind = IntHashTable.find cellKindTbl
420           val cellKind = fn r => case cellKind r of SOME k => k | NONE => C.GP
421    
422         (* Display gc type if a gc map is present *)         (* Display gc type if a gc map is present *)
423         val showGC =         val showGC =
424             case gcmap of             case gcmap of
425               NONE => (fn r => "")               NONE => (fn r => "")
426             | SOME gcmap =>             | SOME gcmap =>
427               let val look = Intmap.map gcmap               let val look = IntHashTable.lookup gcmap
428               in  fn r => ":"^GCMap.GC.toString(look r) handle _ => ":?" end               in  fn r => ":"^GCMap.GC.toString(look r) handle _ => ":?" end
429    
430         (* Display fancy name if a name table is present *)         (* Display fancy name if a name table is present *)
# Line 428  Line 432 
432             case nameTbl of             case nameTbl of
433               NONE =>     (fn (k,v) => C.toString k v)               NONE =>     (fn (k,v) => C.toString k v)
434             | SOME tbl =>             | SOME tbl =>
435               let val look = Intmap.map tbl               let val look = IntHashTable.lookup tbl
436               in  fn (k,v) =>               in  fn (k,v) =>
437                      let val {oldName,index} = look v                      let val {oldName,index} = look v
438                      in  C.toString k oldName^"."^i2s index end                      in  C.toString k oldName^"."^i2s index end
# Line 445  Line 449 
449         fun show v =         fun show v =
450             if v >= 0 then lookupName v             if v >= 0 then lookupName v
451             else (case const v of             else (case const v of
452                    SP.OT.IMMED i => prInt i                    SP.OT.INT i => prInt i
453                    | SP.OT.INTINF i => prIntInf i
454                  | SP.OT.OPERAND opnd => "v"^i2s(~v)                  | SP.OT.OPERAND opnd => "v"^i2s(~v)
455                  (*| SP.OT.LABEL l => Label.nameOf l*)                  (*| SP.OT.LABEL l => Label.nameOf l*)
456                  ) handle SP.OT.NoConst => "?"^i2s(~v)                  ) handle SP.OT.NoConst => "?"^i2s(~v)
# Line 465  Line 470 
470                                           (C.lookup regmap)                                           (C.lookup regmap)
471         fun block b = "b"^i2s b         fun block b = "b"^i2s b
472         fun blockOf ssa_id = block(DA.sub(blockTbl,ssa_id))         fun blockOf ssa_id = block(DA.sub(blockTbl,ssa_id))
473         val cellKindOf = Intmap.mapWithDefault(cellKindTbl, C.GP)         val cellKindOf = IntHashTable.find cellKindTbl
474           val cellKindOf =
475               fn r => case cellKindOf r of SOME k => k | NONE => C.GP
476    
477         fun listify(vs, rs) =         fun listify(vs, rs) =
478         let fun h r = C.toString (cellKindOf r) r         let fun h r = C.toString (cellKindOf r) r
# Line 505  Line 512 
512             | _ =>             | _ =>
513                let fun def v = showVal(List.nth(defs, v))                let fun def v = showVal(List.nth(defs, v))
514                    fun use v = showVal(List.nth(uses, v))                    fun use v = showVal(List.nth(uses, v))
515                    val ssa = #stm (RTL.showRTL{def=def, use=use,                    val ssa = RTL.rtlToString rtl
516                      (* val ssa = #stm
517                                   (RTL.showRTL{def=def, use=use,
518                                                regionDef=def, regionUse=use}) rtl                                                regionDef=def, regionUse=use}) rtl
519                       *)
520    
521                    val ssa = if !showPos then                    val ssa = if !showPos then
522                                 ssa^" #"^prInt(DA.sub(posTbl, ssa_id))                                 ssa^" #"^prInt(DA.sub(posTbl, ssa_id))
523                              else ssa                              else ssa
# Line 525  Line 536 
536      *------------------------------------------------------------------------*)      *------------------------------------------------------------------------*)
537     fun newRenamedVar SSA =     fun newRenamedVar SSA =
538     let val {nameTbl, cellKindTbl, gcmap, ...} = info SSA     let val {nameTbl, cellKindTbl, gcmap, ...} = info SSA
539         val lookupCellKind = Intmap.map cellKindTbl         val lookupCellKind = IntHashTable.lookup cellKindTbl
540         val addCellKind    = Intmap.add cellKindTbl         val addCellKind    = IntHashTable.insert cellKindTbl
541         val updateGC =         val updateGC =
542             case gcmap of             case gcmap of
543               NONE   => (fn (r, r') => r')               NONE   => (fn (r, r') => r')
544             | SOME m =>             | SOME m =>
545               let val lookup = Intmap.map m               let val lookup = IntHashTable.lookup m
546                   val add    = Intmap.add m                   val add    = IntHashTable.insert m
547               in  fn (r,r') => (add(r', lookup r) handle _ => (); r')               in  fn (r,r') => (add(r', lookup r) handle _ => (); r')
548               end               end
549         fun newVar r =         fun newVar r =
# Line 544  Line 555 
555     in  case nameTbl of     in  case nameTbl of
556           NONE => newVar           NONE => newVar
557         | SOME nameTbl =>         | SOME nameTbl =>
558           let val enterName = Intmap.add nameTbl           let val enterName = IntHashTable.insert nameTbl
559               exception NoIndex               exception NoIndex
560               val indexTbl  = Intmap.new(31, NoIndex)               val indexTbl  = IntHashTable.mkTable(31, NoIndex)
561               val addIndex  = Intmap.add indexTbl               val addIndex  = IntHashTable.insert indexTbl
562               val findIndex = Intmap.mapWithDefault(indexTbl,0)               val findIndex = IntHashTable.find indexTbl
563                 val findIndex =
564                     fn r => case findIndex r of SOME i => i | NONE => 0
565               fun newVarKeepName r =               fun newVarKeepName r =
566               let val r' = newVar r               let val r' = newVar r
567                   val i  = findIndex r                   val i  = findIndex r
# Line 568  Line 581 
581     in  case gcmap of     in  case gcmap of
582            NONE => C.newVar            NONE => C.newVar
583          | SOME m =>          | SOME m =>
584            let val lookup = Intmap.map m            let val lookup = IntHashTable.lookup m
585                val add    = Intmap.add m                val add    = IntHashTable.insert m
586            in  fn r => let val r' = C.newVar r            in  fn r => let val r' = C.newVar r
587                        in  add(r', lookup r) handle _ => (); r' end                        in  add(r', lookup r) handle _ => (); r' end
588            end            end
# Line 790  Line 803 
803         val rtlTbl     = rtlTbl SSA         val rtlTbl     = rtlTbl SSA
804         val {edgeCount, ...} = info SSA         val {edgeCount, ...} = info SSA
805    
806         val cellKind = Intmap.mapWithDefault(cellKindTbl SSA,C.GP)         val cellKind = IntHashTable.find(cellKindTbl SSA)
807           val cellKind = fn r => case cellKind r of SOME k => k | NONE => C.GP
808    
809         fun isReplaceable k = k = C.GP orelse k = C.FP         fun isReplaceable k = k = C.GP orelse k = C.FP
810    
# Line 860  Line 874 
874             let val i    = DA.sub(defSiteTbl, value)             let val i    = DA.sub(defSiteTbl, value)
875                 val defs = DA.sub(defsTbl, i)                 val defs = DA.sub(defsTbl, i)
876             in  case (defs, constOf const) of             in  case (defs, constOf const) of
877                   ([_], SP.OT.IMMED imm) => (* only one value defined; okay *)                   ([_], SP.OT.INT imm) => (* only one value defined; okay *)
878                    if (case DA.sub(usesTbl, i) of                    if (case DA.sub(usesTbl, i) of
879                          [v] => v < 0  (* already a constant! don't fold *)                          [v] => v < 0  (* already a constant! don't fold *)
880                        | _   => false) then false                        | _   => false) then false

Legend:
Removed from v.695  
changed lines
  Added in v.744

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