-- $Revision: 9.30 $

(--
   Defines the interfaces to the various traversal routines defined on CFG's

   NOTE: Clients are not allowed to change the structure of the graph directly.
         They must make any requests for changes to the graph indirectly
	 by returning the appropriate analysis result.  Clients may request
	 to continue the traversal leaving the node unchanged, to continue
	 the traversal deleting the node from the graph, and to 
	 replace the node with either another node or a graph.  When
	 replacing the node, clients have the choice of analyzing the 
	 new nodes/graphs or of skipping over then and continuing the analysis
	 at the nodes following the original node in the traversal order.


   abstract object analysis_info;
     concrete object trivial_analysis_info isa analysis_info;
     abstract object iterative_analysis_info
	
   abstract object analysis_result;
     abstract object continue_result isa analysis_result;
       concrete object no_op_continue_result isa continue_result;
       abstract object commit_result isa continue_result;
         template object commit_info isa commit_result;
         template object commit_two_infos isa commit_result;
       template object continue_single_info isa continue_result;
       template object continue_two_infos isa continue_result;
       template object continue_at isa continue_result;
       template object backup_to_given_paths isa continue_result;
     abstract object delete_result isa analysis_result;
       template object delete_CFG_straight isa analysis_result;
       template object delete_CFG_split isa analysis_result;
     abstract object replace_result isa analysis_result;
       template object replace_node isa replace_result;
         template object replace_node_and_continue isa replace_node;
       template object replace_graph isa replace_result;
         template object replace_graph_and_continue isa replace_graph

   abstract object traversal_mode isa comparable;
     concrete representation iterative isa traversal_mode;
     concrete representation noniterative isa traversal_mode;
   
   abstract object traversal_direction isa comparable;
     concrete representation forward_traversal isa traversal_direction;
     concrete representation reverse_traversal isa traversal_direction;
--)


------------------------------------------------------------------------------
--
-- Interface to general purpose traversal routines.
--
------------------------------------------------------------------------------

-- Traverses the graph evaluating cls at the nodes.  
signature traverse(g:CFG_context,
                   dir:traversal_direction,
                   mode:traversal_mode,
		   initial_info:analysis_info,
		   cls: &(RTL, analysis_info):analysis_result):void;


-- returns true if the traversal has reached a fixed-point, false otherwise
signature reached_fixedpoint(iterative_analysis_info):bool;


-- returns the merge-descriptor (incoming analysis infos) for the node, if 
-- a merge descriptor can''t be found, then returns result of if_absent closure
signature incoming_states(CFG_node):merge_descriptor;
signature incoming_states(CFG_node, &():none):merge_descriptor;


------------------------------------------------------------------------------
--
-- Analysis Info
--
------------------------------------------------------------------------------

abstract object analysis_info;
  -- merge takes 2 analysis_info's and combines them to produce a single 
  -- analysis_info in some way that makes sense with respect to the semantics
  -- of the pass.  It is free to side effect its first argument, but may not
  -- change the value of its second argument
  signature merge(analysis_info, analysis_info):analysis_info;
  -- a more general interface that identifies the merge node;
  -- defaults to the simpler interface
  method merge(a1@:analysis_info, a2@:analysis_info,
	       node:rtl_merge):analysis_info { merge(a1,a2) }

  -- copy should create a copy & return it.
  signature copy(analysis_info):analysis_info;

  signature print_string(analysis_info):string;

  -- is invoked to allow the client to set the scope at loop-tails during
  -- reverse passes.  Needs to be defined by reverse traversals that want to
  -- track the scope.  Defaults to doing nothing
  method set_scope(@:analysis_info, :scope):void { (-- do nothing --) }

-- analysis infos which are intended to be used for iterative 
-- passes need to define some additional methods
abstract object iterative_analysis_info isa analysis_info;
  -- the generalizing_merge method is invoked to merge a previous guessed 
  -- fixed point with the incoming info when the two states aren't compatibale
  -- and thus fixed point has not been reached.  It should do things to make
  -- sure that a fixed point will be reached eventually (like replacing
  -- constants with a more general represenation).  Like merge it is free to
  -- side effect its first argument. We default this to just call merge, 
  -- clients can provide an implementation of generalizing_merge as needed.
  method generalizing_merge(new@:analysis_info, 
			    old@:analysis_info):analysis_info{
      merge(new, old) }
  -- a more general interface that also passes the loop head merge node;
  -- defaults to the simpler interface
  method generalizing_merge(new@:analysis_info, 
			    old@:analysis_info,
			    node:rtl_loophead):analysis_info{
      generalizing_merge(new, old) }

  -- compatible is used to determine whether or not an iterative analysis has
  -- reached a fixed point.  It will be called with new being the new fixed
  -- point and old being the old fixed point.  It should return true if a
  -- fixed point has been reached (i.e. new = old, for the right definition of
  -- =), false otherwise.  Note that compatible is called after invoking
  -- generalizing_merge on the loop predecessor's info and the loop back edge's
  -- info.
  method compatible(new@:analysis_info, old@:analysis_info):bool { true }

  -- entering_loop is an advisor notice to the dataflow analysis that we're
  -- now entering the body of loop 'node'.
  method entering_loop(x@:analysis_info, node:rtl_loophead):void {}



-- an object to be used as an analysis info by clients that actually don''t 
-- need any state for their traversal but want to use the idfa framework.
concrete object trivial_analysis_info isa analysis_info;
  method merge(t@:trivial_analysis_info,
	       @:trivial_analysis_info):trivial_analysis_info { t }
  method copy(t@:trivial_analysis_info):trivial_analysis_info { t }
  method compatible(@:trivial_analysis_info, @:trivial_analysis_info):bool {
      true }
  method print_string(@:trivial_analysis_info):string {"trivial_analysis_info"}


------------------------------------------------------------------------------
--
-- Traversal control
--
------------------------------------------------------------------------------

abstract object traversal_mode isa comparable;
  method =(t1@:traversal_mode, t2@:traversal_mode):bool { t1 == t2 }
concrete representation iterative isa traversal_mode;
concrete representation noniterative isa traversal_mode;
   
abstract object traversal_direction isa comparable;
  method =(t1@:traversal_direction, t2@:traversal_direction):bool { t1 == t2 }
concrete representation forward_traversal isa traversal_direction;
concrete representation reverse_traversal isa traversal_direction;



------------------------------------------------------------------------------
--
-- Analysis Results
--
------------------------------------------------------------------------------

-- analysis_result's are the things returned by the closures evaluated at each
-- node of the graph.  Depending on the specific type of result returned, 
-- different actions are taken to continue the traversal.
abstract object analysis_result;
  signature print_string(analysis_result):string;
  method is_delete(@:analysis_result):bool { false }
  method is_replace(@:analysis_result):bool { false }
  method is_backup(@:analysis_result):bool { false }


-- Results of this type mean to leave the node unchanged and continue with
-- the next nodes in the traversal order.
abstract object continue_result isa analysis_result;

-- no_op_continue_result means to continue along any outgoing paths with
-- the same info (properly replicated for multiple outgoing paths, of course)
-- This is the common case.
  concrete object no_op_continue_result isa continue_result;
  method print_string(t@:no_op_continue_result):string { 
      "no_op_continue_result" }

-- A return of this type will cause the traversal to continue
-- along all possible paths from this node with the given information.
-- The analysis info will be duplicated as needed.
template object continue_single_info isa continue_result;
  field info(@:continue_single_info):analysis_info;
  method print_string(t@:continue_single_info):string {
      "Single continue with info: " || t.info.print_string }
  method new_continue_single_info(i@:analysis_info):continue_single_info {
      concrete object isa continue_single_info { info := i } }


-- A return of this type will casue 
-- the traversal to continue along the true path with the true state and the
-- false path with the false state.  This analysis_result is only valid in 
-- forward traversals when the current node is a CFG_2_succ.  
-- In other cases, returning this result will be trapped as an error.
template object continue_two_infos isa continue_result;
  field true_info(@:continue_two_infos):analysis_info;
  field false_info(@:continue_two_infos):analysis_info;
  method print_string(t@:continue_two_infos):string {
      ["T/F continue:  T info: ", t.true_info.print_string, "\nF info: ",
	t.false_info.print_string].flatten }
  method new_continue_two_infos(ts:analysis_info,
				fs:analysis_info):continue_two_infos {
      concrete object isa continue_two_infos {
	  true_info := ts, false_info := fs } }


-- This result will cause the traversal routine to continue at the 
-- specified node with the given analysis info.  The specified node is assumed
-- to have a single predecessor (successor) for a forward (resp. reverse)
-- traversal.  Iterative traversals are not supported.
template object continue_at isa continue_result;
  field info(@:continue_at):analysis_info;
  field from(@:continue_at):CFG;
  field to(@:continue_at):CFG;
  method print_string(t@:continue_at):string {
      "Continue at arc between " || t.from.print_string || " and " ||
	t.to.print_string || " with info: " || t.info.print_string }
  -- this interface only applies to forward traversals!
  method new_continue_at(n:CFG, i:analysis_info):continue_at {
      new_continue_at(n.prev, n, i) }
  method new_continue_at(from:CFG, to:CFG, i:analysis_info):continue_at {
      concrete object isa continue_at { from := from, to := to, info := i } }


abstract object commit_result isa continue_result;
  field commit_cl(@:commit_result):&(analysis_info):void;
  signature commit_cl_false(commit_result):&(analysis_info):analysis_info;

template object commit_info isa commit_result;
  method print_string(t@:commit_info):string {
      "Commit single info" }
  method commit_cl_false(t@:commit_info):&(analysis_info):analysis_info {
      t.commit_cl }
  method new_commit_info(cl:&(analysis_info):analysis_info):commit_info {
      concrete object isa commit_info { commit_cl := cl } }

template object commit_two_infos isa commit_result;
  field commit_cl_false(@:commit_two_infos):&(analysis_info):void;
  method print_string(t@:commit_two_infos):string {
      "Commit two infos" }
  method 
  new_commit_two_infos(cl:&(analysis_info):analysis_info,
		       cl_f:&(analysis_info):analysis_info):commit_two_infos {
      concrete object isa commit_two_infos { commit_cl := cl, 
					       commit_cl_false := cl_f } }


-- This result will cause the traversal routine to continue at the 
-- specified paths with the given analysis infos.  All of the given nodes must
-- have been already visited during the traversal.  They may be in different
-- basic blocks than each other or than the current node.  
-- This result is currently only supported for forward,
-- non-iterative traversals.  
template object backup_to_given_paths isa continue_result;
  field infos(@:backup_to_given_paths):
    table[pair[CFG_node,CFG_node],analysis_info];
  field enhanced_merges(@:backup_to_given_paths):set[RTL];
  method print_string(t@:backup_to_given_paths):string {
      "Backup to: " || t.infos.print_string || ", enhanced merges = " ||
       t.enhanced_merges.print_string }
  method is_backup(@:backup_to_given_paths):bool { true }
  method new_backup_to_given_paths(paths:table[pair[CFG_node,CFG_node], 
					       analysis_info],
				   em:set[RTL]):continue_result {
      concrete object isa backup_to_given_paths { 
	  infos := paths, enhanced_merges := em } }



-- Delete the current node from the graph and continue at all of its 
-- sucessors with the specified info.
abstract object delete_result isa analysis_result;
  var field info(@:delete_result):analysis_info; -- Var field for composer
  method is_delete(@:delete_result):bool { true }


-- delete a CFG_straight node from the graph
template object delete_CFG_straight isa delete_result;
  method print_string(t@:delete_CFG_straight):string {
      "Delete: " || t.info.print_string }
  method new_delete_CFG_straight(i:analysis_info):delete_result {
      concrete object isa delete_CFG_straight { info := i } }


-- delete a CFG_split from the graph, the second parameter tells us which of 
-- the nodes 2 successors we should keep.  A value of 'true' means keep the
-- true branch & recursively remove the false one.  A value of 'false' means
-- keep the false branch and recursively remove the true one.
-- This result is currently only supported during forward traversals.
template object delete_CFG_split isa delete_result;
  field branch_to_keep(@:delete_CFG_split):bool;
  method print_string(t@:delete_CFG_split):string {
      ["Delete, keeping ", t.branch_to_keep.print_string, " branch: ",
       t.info.print_string].flatten }
  method new_delete_CFG_split(i:analysis_info, keep:bool):delete_result {
      concrete object isa delete_CFG_split {
	  info := i, branch_to_keep := keep } }



-- Replace the current node by the node/graph specified in the result.  
-- The default is to restart at the new node or at the head of the new graph
-- with the specified info.  It is also possible to restart after the new
-- node or graph by returning the replace_{node,graph}_and_continue result.
-- Note that graph replacements must "make sense."  Nodes may
-- only be replaced by nodes/graphs that have the same kind of connections.
-- Once exception to this rule is that it is fine to replace a node
-- with a graph that has fewer tails than the node has successors.  
-- This will automatically hook up the whatever branches are there and
-- recursively remove the dead ones.
abstract object replace_result isa analysis_result;
  var field info(@:replace_result):analysis_info;  -- Var field for composer
  method is_replace(@:replace_result):bool { true }


-- replace the current node by the new node & restart analysis with the new
-- node and the given info.  (This is a shortcut for creating a graph with a
-- single node.  It seems like its worth it, 'cause this is fairly common)
template object replace_node isa replace_result;
  field node(@:replace_node):CFG_node;
  method print_string(t@:replace_node):string {
      ["Replace:  Node: ", t.node.print_string, "Info: ", 
	t.info.print_string].flatten } 
  method new_replace_node(n:CFG_node, i:analysis_info):replace_node {
      concrete object isa replace_node {
	  node := n, info := i } }


-- replace, but don''t reanalyize
template object replace_node_and_continue isa replace_node;
  method print_string(t@:replace_node_and_continue):string {
      ["Replace and continue:  Node: ", t.node.print_string, "Info: ", 
	t.info.print_string].flatten } 
  method new_replace_node_and_continue(n:CFG_node, 
				       i:analysis_info):replace_node {
      concrete object isa replace_node_and_continue {
	  node := n, info := i } }


-- replace the current node with the graph & continue at head of graph
template object replace_graph isa replace_result;
  field graph(@:replace_graph):virtual_CFG_context;
  method print_string(t@:replace_graph):string {
      "Replace with graph.  Info: " || t.info.print_string }
  method new_replace_graph(g:virtual_CFG_context, 
			   i:analysis_info):replace_graph {
      concrete object isa replace_graph {
	  graph := g, info := i } }


-- replace, but don''t reanalyze graph.  
template object replace_graph_and_continue isa replace_graph;
  method print_string(t@:replace_graph_and_continue):string {
      "Replace with graph and continue. Info: " || t.info.print_string }
  method new_replace_graph_and_continue(g:virtual_CFG_context,
				    i:analysis_info):replace_graph {
      concrete object isa replace_graph_and_continue {
	  graph := g, info := i } }