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

SCM Repository

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

View of /sml/trunk/src/MLRISC/flowgraph/cfg.sig

Parent Directory Parent Directory | Revision Log Revision Log


Revision 984 - (download) (as text) (annotate)
Wed Nov 21 19:00:08 2001 UTC (17 years, 9 months ago) by george
File size: 5958 byte(s)
  Implemented a complete redesign of MLRISC pseudo-ops. Now there
  ought to never be any question of incompatabilities with
  pseudo-op syntax expected by host assemblers.

  For now, only modules supporting GAS syntax are implemented
  but more should follow, such as MASM, and vendor assembler
  syntax, e.g. IBM as, Sun as, etc.
(* cfg.sig
 *
 * COPYRIGHT (c) 2001 Bell Labs, Lucent Technologies
 *
 * Control flow graph data structure used by the MLRISC IR.
 * All basic optimizations are based on this representation.
 *
 * -- Allen
 *)

signature CONTROL_FLOW_GRAPH =
sig

   structure P : PSEUDO_OPS 
   structure I : INSTRUCTIONS 

   structure W : FREQ
   
   type weight = W.freq

   datatype block_kind = 
       START          (* entry node *)
     | STOP           (* exit node *)
     | NORMAL         (* normal node *)
     | HYPERBLOCK     (* hyperblock *)

   (*
    * NOTE 1: the instructions are listed in reverse order.
    * This choice is for a few reasons:
    *
    * i)  Clusters represent instructions in reverse order, so keeping this
    *     the same avoid having to do conversions.
    *
    * ii) This makes it easier to add instructions at the end of the block,
    *     which is more common than adding instructions to the front.
    *
    * iii) This also makes it easier to manipulate the branch/jump instruction
    *      at the end of the block.
    *
    * NOTE 2: 
    *  Alignment always appear before labels in a block.
    *)
   
   and block = 
      BLOCK of
      {  id          : int,                        (* block id *)
         kind        : block_kind,                 (* block kind *)
         freq        : weight ref,                 (* execution frequency *) 
         labels      : Label.label list ref,       (* labels on blocks *) 
         insns       : I.instruction list ref,     (* in rev order *)
	 align	     : P.pseudo_op option ref,	   (* alignment only *)
         annotations : Annotations.annotations ref (* annotations *)
      }


   and edge_kind = ENTRY           (* entry edge *) 
                 | EXIT            (* exit edge *)
                 | JUMP            (* unconditional jump *)
                 | FALLSTHRU       (* falls through to next block *)  
                 | BRANCH of bool  (* branch *) 
                 | SWITCH of int   (* computed goto *)   
                 | SIDEEXIT of int (* the ith side exit in a hyperblock *)

   and edge_info = EDGE of { k : edge_kind,                  (* edge kind *)
                             w : weight ref,                 (* edge freq *)
                             a : Annotations.annotations ref (* annotations *)
                           }

   type edge = edge_info Graph.edge
   type node = block Graph.node

   datatype info = 
       INFO of { annotations : Annotations.annotations ref,
                 firstBlock  : int ref, (* id of first block *)
                 reorder     : bool ref, (* has the CFG been reordered? *)
		 data        : P.pseudo_op list ref (* reverse order of generation *)
               }

   type cfg = (block,edge_info,info) Graph.graph

  (*========================================================================
   *
   *  Various kinds of annotations on basic blocks
   *
   *========================================================================*)
   val LIVEOUT : I.C.cellset Annotations.property
                  (* escaping live out information *)
   val CHANGED : (string * (unit -> unit)) Annotations.property

  (*========================================================================
   *
   *  Methods for manipulating basic blocks
   *
   *========================================================================*)
   val newBlock          : int * W.freq ref -> block (* empty *)
   val newStart          : int * W.freq ref -> block          (* start node *)
   val newStop           : int * W.freq ref -> block          (* stop node *)
   val copyBlock         : int * block -> block       (* copy a block *)
   val defineLabel       : block -> Label.label       (* define a label *)
   val insns             : block -> I.instruction list ref
   val freq              : block -> W.freq ref
   val branchOf          : edge_info -> bool option

               (* emit assembly *)
   val emit       : Annotations.annotations -> block -> unit

  (*========================================================================
   *
   *  Methods for manipulating CFG
   *
   *========================================================================*)
   val cfg      : info -> cfg      (* create a new cfg *) 
   val new      : unit -> cfg      (* create a new cfg *)
   val subgraph : cfg -> cfg       (* mark as subgraph *)
   val init     : cfg -> unit      (* add start/stop nodes *)
   val changed  : cfg -> unit      (* mark cfg as changed *)  

   val annotations    : cfg -> Annotations.annotations ref
   val liveOut        : block -> I.C.cellset
   val fallsThruFrom  : cfg * Graph.node_id -> Graph.node_id option
   val fallsThruTo    : cfg * Graph.node_id -> Graph.node_id option
   val removeEdge     : cfg -> edge -> unit
   val setBranch      : cfg * Graph.node_id * bool -> I.instruction
   val edgeDir        : edge_info Graph.edge -> bool option

  (*========================================================================
   *
   *  For viewing
   *
   *========================================================================*)
(*****
   val viewStyle      : cfg -> (block,edge_info,info) GraphLayout.style
   val viewLayout     : cfg -> GraphLayout.layout
   val headerText     : block -> string
   val footerText     : block -> string
   val subgraphLayout : { cfg : cfg, subgraph : cfg } -> GraphLayout.layout
*****)

  (*========================================================================
   *
   *  Miscellaneous stuff
   *
   *========================================================================*)
   val cdgEdge : edge_info -> bool (* for building a CDG *)

  (*========================================================================
   *
   *  Methods for printing CFGs
   *
   *========================================================================*)
   val show_block : Annotations.annotations -> block -> string 
   val show_edge  : edge_info -> string 

end


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