-- $Revision: 9.57 $
(--
   This file defines a dead assignment elimination optimization.

   The general algorithm is to make a reverse traversal of the graph.
   At each node of the graph we check to see if the rtl_symbol which 
   represents the result of the RTL statement is in our set of symbols
   we have seen so far. If it is not & the RTL node has no side effects,
   we eliminate the RTL node.  If the node can not be eliminated, then we 
   must add all symbols which appear on the right hand side to the set of
   symbols we have seen. 

--)

------------
-- Driver routine
------------

method dead_assign_elim(g@:CFG_context):void {
    traverse(g, reverse_traversal, iterative, new_dead_assign_info(g.scope),
	     &(n:RTL, info:dead_assign_info) {
		 n.do_dead_assign_elim(info)
	     });
    cond_msg(options.cse_msgs, 3,
	     { "\n***After dead assign elim:\n" || g.print_string });
}


method do_dead_assign_elim(n@:RTL, info:dead_assign_info):analysis_result {
    if(n.can_elim(info), { 
	new_delete_CFG_straight(info) 
    }, { 
	info.change_info(n);
	new_continue_single_info(info) 
    }) }

---------------
-- Analysis Info
---------------

template object dead_assign_info isa iterative_analysis_info;
  var field cur_scope(@:dead_assign_info):scope;
  field seen(@:dead_assign_info):m_set[rtl_symbol];

  method merge(t1@:dead_assign_info, t2@:dead_assign_info):dead_assign_info { 
      assert(t1.cur_scope = t2.cur_scope, "scopes should be the same");
      t1.seen.add_all(t2.seen);
      t1 }
  method copy(t@:dead_assign_info):dead_assign_info {
      new_dead_assign_info(t.cur_scope, t.seen.copy) }
  method compatible(new@:dead_assign_info, old@:dead_assign_info):bool {
      old.seen.includes_all(new.seen) }
  method set_scope(t@:dead_assign_info, s:scope):void { t.cur_scope := s; }

  method print_string(t@:dead_assign_info):string {
      ["seen: {", t.seen.print_string, "}",
       ", current: ", t.cur_scope.print_string].flatten }

  method new_dead_assign_info(s:scope):dead_assign_info {
      new_dead_assign_info(s, new_symbol_bit_set()) }
  method new_dead_assign_info(s:scope, sn:m_set[rtl_symbol]):dead_assign_info {
      concrete object isa dead_assign_info { cur_scope := s, seen := sn } }


------------
-- define which RTL statements could possibly be eliminated
-----------

-- default this to false
method can_elim(@:RTL, @:dead_assign_info):bool { false }

method can_elim(t@:rtl_assign, s@:dead_assign_info):bool {
    t.result.can_elim(s) }

method can_elim(t@:rtl_address, s@:dead_assign_info):bool {
    t.result.can_elim(s) }

method can_elim(t@:rtl_alu, s@:dead_assign_info):bool {
    t.result.can_elim(s) }

method can_elim(t@:rtl_load, s@:dead_assign_info):bool {
    t.result.can_elim(s) }

method can_elim(t@:rtl_allocation, s@:dead_assign_info):bool {
    t.result.can_elim(s) }


-- if we havent seen it & its either defined & used solely within this 
-- CFG then we can kill it
method can_elim(name@:rtl_symbol, s@:dead_assign_info):bool {
    not(s.seen.includes(name)) & { not(name.is_nonlocal_access(s.cur_scope)) }}

----------------
-- we're not going to eliminate the statement, so add stuff to set
-- or otherwise muck around with the traversal state
----------------

method change_info(s@:dead_assign_info, t@:RTL):void {

    t.direct_defs.do(&(n:rtl_symbol){
	s.seen.remove(n, { (-- ok if not there --) });
    });
    t.uses.do(&(n:rtl_symbol){
	if_false(n.is_literal, {
	    s.seen.add(n);
	});
    });
}

method change_info(s@:dead_assign_info, t@:rtl_enter_scope):void {
    s.cur_scope := t.scope.get_cont_scope;
}

method change_info(s@:dead_assign_info, t@:rtl_exit_scope):void {
    s.cur_scope := t.scope;
}

method change_info(s@:dead_assign_info, t@:rtl_some_fatal):void {
    s.cur_scope := t.scope;
}



-- Here's an example from another pass of how to build a little CFG &
-- replace the current node with the constructed graph.
method expand_node_1(t@:rtl_cone_test,
		     state:expansion_1_state):analysis_result {
    if(t.expanded, { ^ no_op_continue_result });

    -- Create an empty CFG to build the replacement graph in.
    -- NOTE: pass the node to be replaced as an argument to
    -- new_virtual_CFG_context to get the right # of hooks!
    let new:virtual_CFG_context := t.new_virtual_CFG_context;

    -- calling new_rtl_temp on the current scope is the right way to
    -- get a new temporary name.  2nd arg is the representation.
    let map_temp:rtl_symbol := 
      state.cur_scope.new_rtl_temp(rtl_CecilMap_ptr_rep); 

    -- create an rtl_unop & insert it into the replacement graph
    let map :=
      new_rtl_unop(if(t.ptr_expected, 
		      { rtl_op_get_map_ptr_expected },
		      { rtl_op_get_map }),
		   map_temp, t.arg);
    new.insert(map);

    -- If you want the node itself to be in the replacement graph,
    -- then YOU MUST COPY IT (because changes are tenative)
    let new_test:rtl_cone_test := t.copy;
    new_test.arg := map_temp;
    new_test.expanded := true;
    
    -- The last node must be 'fully_inserted' instead of just 'inserted'
    -- This ties off some dangling internal pointers used during construction
    new.fully_insert(new_test);

    -- Request the replacement
    new_replace_graph(new, state) }