path: root/gcc/ipa-str-reorg-instance-interleave.c

/* Interprocedural scalar replacement of aggregates
   Copyright (C) 2019-2020 Free Software Foundation, Inc.

  Contributed by Gary Oblock <goblock@marvell.com>

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 3, or (at your option) any later
version.

GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.

You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3.  If not see
<http://www.gnu.org/licenses/>.  */

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "tree.h"
#include "gimple.h"
#include "tree-pass.h"
#include "cgraph.h"
#include "gimple-iterator.h"
#include "pretty-print.h"
#include <vector>
#include <map>
#include <set>
#include "ipa-structure-reorg.h"
#include "dumpfile.h"
#include "tree-pretty-print.h"
#include "gimple-pretty-print.h"
#include "langhooks.h"
#include "stringpool.h"
#include "stor-layout.h"
#include "diagnostic-core.h"

static void str_reorg_instance_interleave_qual_part ( Info *);
static void str_reorg_instance_interleave_type_part ( Info *);
static void create_new_types ( Info_t *);
static void create_a_new_type ( Info_t *, tree);
static unsigned int reorg_perf_qual ( Info *);
  
#if USE_NEW_INTERFACE
int
str_reorg_instance_interleave_qual ( Info *info)
{
  // this is the qualification code for instance interleaving
  //
  str_reorg_instance_interleave_qual_part ( info);

  // this modifiies the qualified types.
  //
  str_reorg_instance_interleave_type_part ( info);
  return 0;
}

int
str_reorg_instance_interleave_trans ( Info *info)
{
  struct cgraph_node *node;
  FOR_EACH_FUNCTION_WITH_GIMPLE_BODY ( node)
  {
    struct function *func = DECL_STRUCT_FUNCTION ( node->decl);
    if ( info->show_transforms )
      {
        fprintf( dump_file, "Function \"%s\":\n",
		 //IDENTIFIER_POINTER( DECL_NAME( func)));
		 //IDENTIFIER_POINTER( DECL_NAME( func->decl)));
		 lang_hooks.decl_printable_name ( node->decl, 2));
      }

    basic_block bb;
    FOR_EACH_BB_FN ( bb, func)
      {

	if( info->show_transforms )
	  {
	    fprintf( dump_file, "  Transforming BB%i:\n",
		     bb->index);
	  }

	gimple_stmt_iterator gsi;
	for ( gsi = gsi_start_bb ( bb);
	      !gsi_end_p ( gsi);
	      gsi_next ( &gsi) )
	  {
	    // Every statement that uses a reorg type needs to
	    // be examined. Some are harmless and are skipped
	    // whereas others are transformed. However, anything
	    // else is an error.
	    gimple *stmt = gsi_stmt ( gsi);
	    ReorgType_t *ri = contains_a_reorgtype( stmt, info);
	    if ( ri != NULL )
	      {
		enum ReorgTransformation trans = 
		  reorg_recognize ( stmt, info);
		// print out trans and stmt if dumping
		if ( info->show_transforms )
		  {
		    print_gimple_expr( dump_file, stmt, 4, TDF_SLIM);
		  }
	    
		switch( trans)
		  {
		  case ReorgT_StrAssign:
		    DEBUG_L("ReorgT_StrAssign\n");
		    // TBD
		    /*
	      tree lhs = gimple_assign_lhs( stmt);
	      tree rhs = gimple_assign_rhs( stmt);
	      ReorgOpTrans lope = recognize_op( lhs, info);
	      ReorgOpTrans rope = recognize_op( rhs, info);
	      for each field in ri {
	        // lhs: ReorgT_Array & rhs ReorgT_Struct, ReorgT_Deref, ReorgT_Array
		// lhs: ReorgT_Struct & rhs ReorgT_Deref, ReorgT_Array
		// lhs ReorgT_Deref & rhs ReorgT_Struct, ReorgT_Array, ReorgT_Deref
		A is new ssa
		// Gimple for loading this element
		// Question? What if the element is large? Answer is it's OK.
		switch( rope) {
		// Not implemented in single pool
		//case ReorgT_Array:
		case ReorgT_Struct:
		  generate A <- rhs.field  
		  break;
		case ReorgT_Deref:
		  B,C is new SSA
		  // Note simplification with type_name( rhs)
		  generate B <- concat( REORG_SP_PREFIX, type_name( rhs))
		    and insert before stmt
		  generate C <- B->"f"
		    and insert before stmt
		  generate A <- C[rhs]
		    and insert before stmt
		  break
		default:
		  internal_error(
		    "Reached operand default in RHS enum ReorgOpTrans");
		}
		// Gimple for storing this element
		switch( lope)
		// Not implemented in single pool
		//case ReorgT_Array:
		case ReorgT_Deref:
		  B,C is new SSA
		  // Note simplification with type_name( lhs)
		  generate B <- concat( REORG_SP_PREFIX, type_name( lhs))
		    and insert before stmt
		  generate C <- B->"f"
		    and insert before stmt
		  // lhs here is a simplification
		  generate A <- C[lhs]
		    and insert before stmt
		  break;
		case ReorgT_Struct:
		  generate lhs.field <- A
		  break;
		default:
		  internal_error(
		    "Reached operand default in LHS enum ReorgOpTrans");
		}
	      }
		    */
		    break;
		  case ReorgT_ElemAssign:
		    DEBUG_L("ReorgT_ElemAssign\n");
		    /*
	      tree lhs = gimple_assign_lhs( stmt);
	      tree rhs = gimple_assign_rhs( stmt);
	      switch( recognize_op( rhs, info) {
	      case ReorgT_Indirect:  // "a->f"
	        // Note, there are lot's of missing low level details here
	        A,B are new SSA
		// type_name( rhs) is a little sloppy because it's the type
		// name if the "a" that matters and not the type name of
		// "a->f."
		generate A <- concat( REORG_SP_PREFIX, type_name( rhs))
		  and insert before stmt
		generate B <- A->"f"
		  and insert before stmt
		generate lhs <- B
		  and insert before stmt
		delete stmt
		break;
	      // Not implemented in single pool
	      //case ReorgT_AryDir:  // "x[i].f"
	      default:
		internal_error(
		    "Reached operand default for ReorgT_Indirect");
	      }
	      delete stmt
		    */
		    break;
		  case ReorgT_If_Null:
		  case ReorgT_If_NotNull:
		    DEBUG_L("ReorgT_If_(Not)Null\n");
		    /*
	      gimple_cond_set_rhs( stmt, 
	        TYPE_MIN_VALUE( pointer_sized_int_node));
		    */
		    break;
		  case ReorgT_IfPtrEQ:
		  case ReorgT_IfPtrNE:
		  case ReorgT_IfPtrLT:
		  case ReorgT_IfPtrGT:
		  case ReorgT_IfPtrLE:
		  case ReorgT_IfPtrGE:
		    DEBUG_L("ReorgT_IfPtr*\n");
		    // Not needed for single pool.
		    break;
		  case ReorgT_PtrPlusInt:   // "a = b + i"
		    DEBUG_L("ReorgT_PtrPlusInt\n");
		    /*
	      // Does the type of stmt need to be adjusted? I assume so.
	      // The ReorgType contains the type of the pointer
	      // if so that should probably be used. Note, the variables
	      // should all be of the correct type (but maybe that's
	      // not reflected here. Punting and assigning the types to
	      // the type of pointer_sized_int_node is probably not correct
	      // even though that's the representation.
	      tree type = TREE_TYPE( gimple_assign_lhs( stmt));
	      tree tmp = 
	        make_temp_ssa_name( type, NULL, "PtrPlusInt")
	      gimple *adjust_stmt = 
	        gimple_build_assign( 
        	  tmp, 
		  TRUNC_DIV_EXPR, 
		  gimple_assign_rhs2( stmt), 
		  build_int_cst( type, TYPE_SIZE_UNIT( ri->gcc_type)),
		  NULL_TREE, NULL_TREE);
	      // Note, gimple_set_op is used in limited places so using it
	      // to modify existed code might be problematic.
              gimple_set_op( stmt, 2, tmp);
              gsi = gsi_for_stmt( stmt);
              gsi_insert_before( gsi, adjust_stmt, GSI_SAME_STMT);
		    */
		    break;
		  case ReorgT_Ptr2Zero:   //  "a = 0"
		    DEBUG_L("ReorgT_Ptr2Zero\n");
		    /*
	      // Note, this is way too simple... just saying.
	      gimple_set_op( stmt, 1, 
	      		     TYPE_MIN_VALUE( pointer_sized_int_node));
		    */
		    break;
		  case ReorgT_PtrDiff:    //  "i = a - b"
		    DEBUG_L("ReorgT_PtrDiff\n");
		    // Do nothing in the single pool case.
		    break;
		  case ReorgT_Adr2Ptr:    //  "a = &x[i]"
		    DEBUG_L("ReorgT_Adr2Ptr\n");
		    /*
	      tree *add_stmt = 
	        gimple_build_assign( 
        	  gimple_assign_lhs( stmt);, 
		  PLUS_EXPR, 
		  gimple_assign_rhs1( stmt), 
		  gimple_assign_rhs2( stmt), 
		  NULL_TREE, NULL_TREE);
	      gimple_stmt_iterator *gsi = gsi_for_stmt( stmt);
	      gsi_insert_before( gsi, add_stmt, GSI_SAME_STMT);
	      // delete stmt
	      gsi_remove( gsi, true);
		    */
		    break;
		  case ReorgT_PtrNull:     //  "x = a == 0"
		  case ReorgT_PtrNotNull:  //  "x = a != 0"
		    DEBUG_L("ReorgT_Ptr(Not)Null\n");
		    /*
	      gimple_set_op( stmt, 2, 
	      		     TYPE_MIN_VALUE( pointer_sized_int_node));
		    */
		    break;
		  case ReorgT_PtrEQ:       //  "i = a == b"
		  case ReorgT_PtrNE:       //  "i = a != b"
		  case ReorgT_PtrLT:       //  "i = a < b"
		  case ReorgT_PtrLE:       //  "i = a <= b"
		  case ReorgT_PtrGT:       //  "i = a > b"
		  case ReorgT_PtrGE:       //  "i = a >= b"
		    DEBUG_L("ReorgT_Ptr*\n");
		    // Not needed for single pool.
		    break;
		  case ReorgT_Malloc:
		    DEBUG_L("ReorgT_Malloc\n");
		    /*
	      // Note, unlike other simpler transformations,
	      // this must build new basic blocks to add new
	      // gimple to and use a phi for the final result.
	      // See appendix on malloc transformation for
	      // each comment starting with "FROM."
	      ReorgType_t *ri = contains_a_reorgtype( stmt, info);
	      // FROM len = val/size
	      tree arg = gimple_call_arg( stmt, 0);
	      len is new SSA
	      tree val = gimple_call_lhs( stmt);
	      gcc_assert( TREE_CODE( TREE_TYPE(val)) == INDIRECT_REF);
	      tree size = TYPE_SIZE_UNIT( TREE_TYPE( TREE_TYPE( val)));
	      // FROM len = val/size (insert before stmt)
	      gimple_stmt_iterator *gsi = gsi_for_stmt( stmt);
	      gimple *glen = 
	        gimple_build_assign( 
        	  len, 
		  TRUNC_DIV_EXPR, 
		  val, 
		  size,
		  NULL_TREE, NULL_TREE);
              gsi_insert_before( gsi, glen, GSI_SAME_STMT);
              // Note in other places in this doc this would
	      // be "insert glen before stmt" instead of this but
	      // here we need to create new basic blocks.
	      // FROM edge = split this block after stmt
	      edge new_edge = split_edge( bb, stmt);
	      // FROM before_bb = edge->src // same as this bb
	      before_bb = edge->src;
	      // FROM after_bb = edge->dest
	      after_bb = edge->dest;
	      // FROM delete edge
	      remove_edge( e);
	      // FROM prev_bb = before_bb
	      prev_bb = before_bb;
	      // FROM prev_ok_field is new label
	      tree prev_ok_field_L =
	      	create_artificial_label( UNKNOWN_LOCATION);
	      // FROM after_label is new label
	      tree after_label_L =
	        create_artificial_label( UNKNOWN_LOCATION);
	      // FROM add goto for prev_ok_field to end of before_bb
	      gimple *goto_pof = gimple_build_goto( prev_ok_field_L);
	      gsi_insert_before( gsi, *goto_pof, GSI_SAME_STMT);
	      // FROM failure_bb = create_empty_block(prev_bb)
	      basic_block failure_bb = create_empty_block( prev_bb);
	      // FROM make_edge( failure_bb, after_bb, EDGE_FALLTHRU);
	      edge failure_edge = make_edge( failure_bb,
	      	   		  	     after_bb, EDGE_FALLTHRU);
	      // FROM bad_field is new label
	      tree bad_field_L =
	      	create_artificial_label( UNKNOWN_LOCATION);
	      // FROM delete stmt
	      gsi_remove( gsi, true);

	      // code in failure_bb
	      //
	      // FROM fail_val is new SSA
	      tree return_type = TREE_TYPE( arg);
	      tree fail_val = 
	        make_temp_ssa_name( return_type, NULL, "fail_val")
	      // FROM gsi = gsi_start_bb( failure_bb)
	      gsi = gsi_start_bb( failure_bb);
	      // FROM gsi_insert_after( &gsi, "goto after_label")
	      gimple *goto_al = gimple_build_goto( after_label_L);
	      gsi_insert_after( &gsi, goto_al);
	      // (per field) {
	      tree field;
	      tree reorg_type = ri->gcc_type;
	      tree fndecl_free = builtin_decl_explicit( BUILT_IN_FREE);
	      tree base = ri->clone;
   	      for( field = TYPE_FIELDS( reorg_type); 
              	   field; 
	 	   field = DECL_CHAIN( field)) {
		// FROM gsi_insert_after( &gsi, "base.field = 0")
		tree lhs_ass =
		  build3( COMPONENT_REF, ptr_type_node, base, field, NULL_TREE);
	        gimple *gzero = gimple_build_assign( lhs_ass, null_pointer_node);
		gsi_insert_after( &gsi, gzero);
		
		// FROM gsi_insert_after( &gsi, "free(field)")
		tree to_free = 
	          make_temp_ssa_name( type, NULL, "to_free")
		gcall *free_call = gimple_build_call( fndecl_free, 1, to_free);
		gsi_insert_after( &gsi, free_call);
		tree rhs_ass =
		  build3( COMPONENT_REF, ptr_type_node, base, field, NULL_TREE);
		gimple *gaddr2free = gimple_build_assign( to_free, rhs_ass);
		gsi_insert_after( &gsi, gaddr2free);
	      }
	      // FROM gsi_insert_after( &gsi, "fail_val = minint")
	      gimple *gretnull =
	        gimple_build_assign( fail_val,
				     build_int_cst(
				       TYPE_MIN_VALUE( TREE_TYPE(fail_val))));
              gsi_insert_after( &gsi, gretnull);
	      // FROM gsi_insert_after( &gsi, bad_field )
	      gimple gbad_field = gimple_build_label( bad_field_L);
	      gsi_insert_after( &gsi, gbad_field );

	      // loop setup trickery for gimple idioms
	      //
	      // FROM prev_order = failure_bb
	      prev_order = failure_bb;
	      // FROM prev_bb = before_bb
	      prev_bb = before_bb;

	      // Generate all the real allocation code
	      tree fndecl_malloc = builtin_decl_explicit( BUILT_IN_MALLOC);
	      tree base = ri->clone;
	      // FROM (for fields) {
	      for( field = TYPE_FIELDS( reorg_type); 
              	   field; 
	 	   field = DECL_CHAIN( field)) {
	        // FROM res is new SSA
		// Note, alternative code would substitute ptr_type_node
		// for null_pointer_node. 
	        tree res = 
	          make_temp_ssa_name( null_pointer_node, NULL, "res")
	        // FROM new_bb = create_empty_block(prev_order);
		basic_block new_bb = create_empty_block( prev_order);
		// FROM gsi = gsi_start_bb( new_bb)
		gimple_stmt_iterator gsi = gsi_start_bb( new_bb);
		// FROM set imm dom new_bb as prev_bb
		set_immediate_dominator( CDI_DOMINATORS, new_bb, prev_bb);	
		// FROM make_edge( prev_bb, new_bb, EDGE_TRUE_VALUE);
		make_edge( prev_bb, new_bb, EDGE_TRUE_VALUE);
		// FROM make_edge( new_bb, failure_bb, EDGE_FALSE_VALUE);
  		make_edge( new_bb, failure_bb, EDGE_FALSE_VALUE);
		// FROM new_ok_field is new label
		tree new_ok_field_L =
	      	  create_artificial_label( UNKNOWN_LOCATION);
		// FROM gsi_insert_after( &gsi, "if( res NE NULL ) 
  		//    	            goto new_ok_field; 
		//		    goto bad_field")
		tree res = 
	          make_temp_ssa_name( pointer_type_node, NULL, "res")
		gimple *gcond =
		  gimple_build_cond( NE_EXPR, res, null_pointer_node,
		  		     new_ok_field_L, bad_field_L);
		gsi_insert_after( &gsi, gcond);		
		// FROM gsi_insert_after( &gsi, "base.field = res")
		tree lhs_ass =
		  build3( COMPONENT_REF, ptr_type_node, base, field, NULL_TREE);
	        gimple *gset_field = gimple_build_assign( lhs_ass, res);
		gsi_insert_after( &gsi, gset_field);
		
		// FROM gsi_insert_after( &gsi, "res = malloc( mem_size)")
		// The alternative to sizetype are long_integer_type_node
		// and integer_type_node.
		tree mem_size = 
	          make_temp_ssa_name( sizetype, NULL, "mem_size");
		gcall *malloc_call = gimple_build_call( fndecl_malloc, 1, mem_size);
		gimple_call_set_lhs( malloc_call, res);
		gsi_insert_after( &gsi, malloc_call);
		// FROM gsi_insert_after( &gsi, "mem_size = len * field_size")
		gimple *gsize = 
	          gimple_build_assign( mem_size, MULT_EXPR, TYPE_SIZE(field), 
		    		       len, NULL_TREE, NULL_TREE);
		gsi_insert_after( &gsi, gsize);
		// FROM gsi_insert_after( &gsi, prev_ok_field)
		gimple gprev_ok_field = gimple_build_label( prev_ok_field_L);
	      	gsi_insert_after( &gsi, gprev_ok_field_L );
		// FROM prev_bb = new_bb
		prev_bb = new_bb;
		// FROM prev_order = new_bb
		prev_order = new_bb;
		// FROM prev_ok_field = new_ok_field
		prev_ok_field_L = new_ok_field_L;
              }

	      // create basic block for success
	      //
	      // FROM success_bb = create_empty_block(prev_bb_order);
	      success_bb = create_empty_block(prev_bb_order);
	      // FROM set imm dom success_bb as prev_bb
	      set_immediate_dominator( CDI_DOMINATORS, success_bb, prev_bb);
	      // FROM make_edge( prev_bb, success_bb, EDGE_TRUE_VALUE);
	      make_edge( prev_bb, success_bb, EDGE_TRUE_VALUE);
	      // FROM make_edge( success_bb, after_bb, EDGE_TRUE_VALUE);
	      edge success_edge = make_edge( success_bb, after_bb, EDGE_TRUE_VALUE);

	      // code in success_bb
	      //
	      // FROM success_val is new SSA
	      tree success_val = 
	          make_temp_ssa_name( int_ptrsize_type, NULL, "success_val");
	      // FROM gsi = gsi_start_bb( failure_bb)
	      gimple_stmt_iterator gsi = gsi_start_bb( failure_bb);
	      // FROM gsi_insert_after( &gsi, "goto after_label")
	      gimple *goto_al = gimple_build_goto( after_label_L);
	      gsi_insert_after( &gsi, goto_al);
	      // FROM gsi_insert_after( &gsi, "success_val = 0")
	      gimple *set_succ =
	        gimple_build_assign( success_val, build_int_cst( 0));
	      gsi_insert_after( &gsi, set_succ);
	      // FROM gsi_insert_after( &gsi, new_ok_field )
	      gimple gnew_ok_field = gimple_build_label( new_ok_field_L);
	      gsi_insert_after( &gsi, gnew_ok_field );

	      // add code to after_bb
	      //
	      // FROM gsi = gsi_start_bb( after_bb)
	      gimple_stmt_iterator gsi = gsi_start_bb( after_bb);
	      // FROM gsi_insert_after( &gsi, "lhs = "phi(success_val, fail_val)
	      gphi *der_phi = create_phi_node( lhs, after_bb);
	      add_phi_arg( der_phi, success_val, success_edge, UNKNOWN_LOCATION);
	      add_phi_arg( der_phi, fail_val, failure_edge, UNKNOWN_LOCATION);
	      
	      // FROM gsi_insert_after( &gsi, after_label)
	      gimple gafter_label = gimple_build_label( after_L);
	      gsi_insert_after( &gsi, gafter_label );
		    */
		    break;
		  case ReorgT_Calloc:
		    DEBUG_L("ReorgT_Calloc\n");
		    /*
	      // This used to be almost a clone of the old version of
	      // the malloc code above and needs to transformed just like
	      // what was done above to malloc.
	      tree arg = gimple_call_arg( stmt, 0);
	      len is new SSA
	      tree val = gimple_call_lhs( stmt);
	      gcc_assert( TREE_CODE( TREE_TYPE(val)) == INDIRECT_REF);
	      tree size = TYPE_SIZE_UNIT( TREE_TYPE( TREE_TYPE( val)));
	      gimple *glen = 
	        gimple_build_assign( 
        	  len, 
		  TRUNC_DIV_EXPR, 
		  val, 
		  size,
		  NULL_TREE, NULL_TREE);
	      insert glen before stmt
	      tree lfial = create_artificial_label( UNKNOWN_LOCATION);
	      gimple *gfail = gimple_build_label( lfail);
	      tree lnotfial = create_artificial_label( UNKNOWN_LOCATION);
	      gimple *gnotfail = gimple_build_label( lnotfail);
	      tree base = ri->clone;
	      for each element of base {
	      	// call malloc
		tree lok = create_artificial_label( UNKNOWN_LOCATION);
		gimple *glok = gimple_build_label( lok);
		tree *fndecl = builtin_decl_explicit( BUILT_IN_MALLOC);
		mem_size is new SSA
		gimple *gsize = 
	          gimple_build_assign( 
        	    mem_size, 
		    MULT_EXPR, 
		    TYPE_SIZE(element), 
		    len,
		    NULL_TREE, NULL_TREE);
		insert gsize before stmt
	        gcall *call = gimple_build_call( fndecl, 1, mem_size);
		mres is new SSA
		gimple_call_set_lhs( call, mres)
		insert call before stmt
		// Set element to return value of malloc.
		// Note, the devil is in the details here.
		gen concat( REORG_SP_PREFIX,
		            type_name( lhs)  ).element <- mres
		  and insert before stmt
		// gen test of return
		gimple *gcond =
		  gimple_build_cond( EQ_EXPR, mres,
		  null_pointer_node, lfail, lok);
		insert gcond before stmt
		insert glok before stmt
		// call memset
		fndecl = builtin_decl_explicit( BUILT_IN_MEMSET);
		call =
		  gimple_build_call( fndecl, 3, mres, int_node_zero, mem_size);
		insert call before stmt
	      }
	      
	      // fake return value of zero
	      gimple *gretzero =
	        gimple_build_assign( lhs,
				     build_int_cst(
				       TYPE_MIN_VALUE( TREE_TYPE(lhs)), 0));
	      insert gretzero before stmt
	      gimple *ggoto = gimple_build_goto( lnotfail);
	      insert ggoto before stmt
	      insert glab1 before stmt
	      for each element of base {
	      	tree fndecl = builtin_decl_explicit( BUILT_IN_FREE);
	        gcall *call = gimple_build_call( fndecl, 1, element);
		insert call before stmt
		set element to null
	      }
	      // fake return value of null
	      gimple *gretnull =
	        gimple_build_assign( lhs,
				     build_int_cst(
				       TYPE_MIN_VALUE( TREE_TYPE(lhs))));
	      insert gretnull before stmt
	      insert gnotfail before stmt
	      delete stmt
		    */
		    break;
		  case ReorgT_Realloc:
		    DEBUG_L("ReorgT_Realloc\n");
		    /*
		// This used to be closely related to the old version of
		// the malloc code above and needs to transformed just like
		// what was done above to malloc.
		tree arg = gimple_call_arg( stmt, 0);
		len is new SSA
		tree val = gimple_call_lhs( stmt);
		gcc_assert( TREE_CODE( TREE_TYPE(val)) == INDIRECT_REF);
		tree size = TYPE_SIZE_UNIT( TREE_TYPE( TREE_TYPE( val)));
		gimple *glen = 
	        gimple_build_assign( 
		  len, 
		  TRUNC_DIV_EXPR, 
		  val, 
		  size,
		  NULL_TREE, NULL_TREE);
		insert glen before stmt
		tree lfial = create_artificial_label( UNKNOWN_LOCATION);
		gimple *gfail = gimple_build_label( lfail);
		tree lnotfial = create_artificial_label( UNKNOWN_LOCATION);
		gimple *gnotfail = gimple_build_label( lnotfail);
		for each field of base {
	      	  // call malloc
		  tree lok = create_artificial_label( UNKNOWN_LOCATION);
		  gimple *gok = gimple_build_label( lok);
		  tree fndecl = builtin_decl_explicit( BUILT_IN_REALLOC);
		  // but first compute how much to malloc
		  mem_size, var, ptr are new SSA
		  gimple *gsize = 
	          gimple_build_assign( 
        	    mem_size, 
		    MULT_EXPR, 
		    TYPE_SIZE(field), 
		    len,
		    NULL_TREE, NULL_TREE);
		  insert gsize before stmt
		  generate ptr = base.field & insert before stmt
		  gcall *call
		    = gimple_build_call( fndecl, 3, ptr,
		    		         len, TYPE_SIZE( field));
		  gimple_call_set_lhs( call, var);
		  insert call before stmt
		  // gen test of return
		  gimple *gcond =
		  gimple_build_cond( EQ_EXPR, var,
		  null_pointer_node, lfail, lok);
		  insert gcond before stmt
		  insert gok before stmt
		  generate base.field = var & insert before stmt
		}
		// fake return value of starting address (an index of zero)
		gimple *gretzero =
	          gimple_build_assign( lhs, //
		    build_int_cst(
		    TYPE_MIN_VALUE( TREE_TYPE(lhs)), 0));
		insert gretzero before stmt
		gimple *ggoto = gimple_build_goto( lnotfail);
		insert ggoto before stmt
		insert glab1 before stmt
		for each element of base {
	      	tree fndecl = builtin_decl_explicit( BUILT_IN_FREE);
	        gcall *call = gimple_build_call( fndecl, 1, element);
		insert call before stmt
		set element to null
	      }
	      // fake return value of null (minimum value under this scheme)
	      gimple *gretnull =
	        gimple_build_assign( lhs,
				     build_int_cst(
				       TYPE_MIN_VALUE( TREE_TYPE(lhs))));
	      insert gretnull before stmt
	      insert gnotfail before stmt
	      delete stmt
		    */
		    break;
		  case ReorgT_Free:
		    DEBUG_L("ReorgT_Free\n");
		    // We won't free the base because it a global.
		    /*
		  for each element of base {
		    tree fndecl = builtin_decl_explicit( BUILT_IN_FREE);
		    gcall *call = gimple_build_call( fndecl, 1, element);
		    insert call before stmt
		  }
		  delete stmt
		    */
		    break;
		  case ReorgT_UserFunc:
		    // TBD The type must be adjusted (maybe.)
		    DEBUG_L("ReorgT_UserFunc\n");
		    break;
		  case ReorgT_Return:
		    // TBD The type must be adjusted (maybe.)
		    DEBUG_L("ReorgT_Return\n");
		    break;
		  default:
		    internal_error( "Invalid transformation");
		  }
	      }
	  }
      }
  }
}

#else
int
// Returns one if something was done and zero otherwise.
str_reorg_instance_interleave ( Info *info)
{
  // TBD
  // DEBUG ( "Running str_reorg_instance_interleave\n");
  return 0;
}
#endif

static void
str_reorg_instance_interleave_qual_part ( Info *info)
{
  // TBD save the return value so we can bypass further
  // instance interleaving if none of it is profitable.
  reorg_perf_qual ( info);
}

static void
str_reorg_instance_interleave_type_part ( Info *info)
{
  create_new_types ( info);
}

static unsigned int
reorg_perf_qual ( Info *info)
{
  // TBD use design in doc but mark ReorgTypes
  // (do_instance_interleave) that qualify instead of deleting them
  // unless both dead field elimination and field reorderig are not
  // viable (use do_dead_field_elim and do_field_reorder in
  // Reorg_type_t.)

  // For the mean time assume if a ReorgType made it here then it's qualified.
  for ( int i = 0; i < info->reorg_type->size (); i++ )
    {
      (*(info->reorg_type))[i].do_instance_interleave = true;
    }
}

// create_new_types has to crawl "all" the
// types, create new types and transform
// other types that must be changed.
// A type will change when it's a
// a pointer to a ReorgType or it contains
// an interior pointer to one. 
static void
create_new_types ( Info_t *info)
{
  std::map < tree, BoolPair_t>::iterator tmi; // TBD what is 
  for( tmi = info->struct_types->begin ();
       tmi != info->struct_types->end ();
       tmi++ ) {
    if ( !tmi->second.processed ) create_a_new_type ( info, tmi->first);
  }    
}

static void
create_a_new_type ( Info_t *info, tree type)
{
  bool layout_changed = false;
  // skip if already processed  		   
  if ( ( *( info->struct_types))[type].processed ) return;

  // Implementation note: Check this for infinite recursion.
  // I don't think it's possible in a sane universe but
  // pointers to reorganized types can occur, so does that
  // an issue (not necessarily here.)
  // Also, is this even necessary? Singletons don't expand
  // and static arrays are not allowed "yet."
  tree field;
  tree new_fields = NULL;
  for ( field = TYPE_FIELDS ( type); // WHF, I speced reorg_type_prime here???
        field; 
        field = DECL_CHAIN ( field))
    {
      // make sure all the interior types are processed
      // before processing this type
      if ( TREE_CODE ( field) == RECORD_TYPE )
	{
	  create_a_new_type ( info, field);
	}
    }
	 
  ReorgType_t *ri = get_reorgtype_info ( type, info);
  if ( ri != NULL ) {
    tree reorg_type_prime = 
      build_variant_type_copy ( type MEM_STAT_DECL);
    ri->clone = reorg_type_prime;
    
    /* Multi-pool only
    // Create pointer_rep
    // this will be a long and a pointer to the 
    // reorg_type_prime
    tree pointer_rep = 
    lang_hooks.types.make_type( RECORD_TYPE);
    
    tree index_name = get_identifier("index");
    tree index_field = build_decl( BUILTINS_LOCATION, 
    FIELD_DECL, 
    index_name, 
    long_integer_type_node);
    tree base_name = get_identifier("base");
    tree base_field = build_decl( BUILTINS_LOCATION, 
    FIELD_DECL, 
    base_name, 
    reorg_type_prime);
    insert_field_into_struct( pointer_rep, index_field);
    insert_field_into_struct( pointer_rep, base);
    
    reorg_type->pointer_rep = pointer_rep;
    */

    tree pointer_rep = make_node ( INTEGER_TYPE);
    TYPE_PRECISION ( pointer_rep) =
      TYPE_PRECISION ( pointer_sized_int_node);
    #define REORG_SP_PTR_PREFIX "_reorg_SP_ptr_type_"
    //DEBUG("Issue with gcc_ of reorg\n");
    //DEBUG_F(print_reorg, stderr, 2, ri);
    const char *gcc_name =
      identifier_to_locale ( IDENTIFIER_POINTER ( TYPE_NAME ( ri->gcc_type)));
    size_t len =
      strlen ( REORG_SP_PTR_PREFIX) + strlen ( gcc_name);
    char *name = ( char *)alloca(len + 1);
    strcpy ( name, REORG_SP_PTR_PREFIX);
    strcat ( name, gcc_name);
    TYPE_NAME ( pointer_rep) = get_identifier ( name);
    ri->pointer_rep = pointer_rep;
    
    // Set name of reorg_type_prime
    #define REORG_SP_PREFIX "_reorg_base_type_"
    // TBD shouldn't base_type_name be different from gcc_name above
    const char *base_type_name =
      identifier_to_locale ( IDENTIFIER_POINTER ( TYPE_NAME ( ri->gcc_type)));
    len = strlen ( REORG_SP_PREFIX) + strlen ( base_type_name);
    char *rec_name = ( char*)alloca ( len + 1);
    strcpy ( rec_name, REORG_SP_PREFIX);
    strcat ( rec_name, base_type_name);
    
    // Build the new pointer type fields
    TYPE_NAME ( reorg_type_prime) = get_identifier ( rec_name);
    tree field;
    tree new_fields = NULL;
    for ( field = TYPE_FIELDS ( reorg_type_prime); 
	 field; 
	 field = DECL_CHAIN ( field))
      {
	//DEBUG_F( print_generic_decl, stderr, field, TDF_DETAILS); // example
	tree tree_type = TREE_TYPE ( field);
	tree new_fld_type = build_pointer_type ( tree_type);
	tree new_decl =
	  build_decl ( DECL_SOURCE_LOCATION (field),
		       VAR_DECL, DECL_NAME (field), new_fld_type);
	// Missing a bunch of attributes (see tree-nested.c:899)
	// Let us seee what happens without them!
	DECL_CHAIN ( new_decl) = new_fields; // <- bug: need decl, not type
	new_fields = new_decl;
	//DEBUG( "built new pointer type field:");
	//DEBUG_F( print_generic_decl, stderr, new_decl, TDF_DETAILS);
	//DEBUG( "\n");
      }
    // store reversed fields back into reorg_type_prime
    TYPE_FIELDS ( reorg_type_prime) = NULL;
    tree next_fld;
    for ( field = new_fields;
	  field; 
	  field = next_fld    )
      {
	next_fld = DECL_CHAIN ( field);
	DECL_CHAIN ( field) = TYPE_FIELDS ( reorg_type_prime);
	TYPE_FIELDS ( reorg_type_prime) = field;
      }
    // Fix-up the layout
    layout_type ( reorg_type_prime);
  }

  // Mess with the original type too because it might
  // have base_type_fldinterior elements that are modified.
  for ( field = TYPE_FIELDS ( type); 
       field; 
       field = DECL_CHAIN ( field))
    {
      if ( TREE_CODE ( field) == RECORD_TYPE )
	{
	  layout_changed =
	    layout_changed || ( *( info->struct_types)) [ field].layout_changed;
	}
      else
	{
	  // process pointers to reorg types
	  if ( POINTER_TYPE_P ( field) )
	    {
	      tree field_type = TREE_TYPE ( field);
	      if ( is_reorg_type ( field_type, info) )
		{
		  // Change field type.
		  
		  // If multi-pool then set layout_changed to true.
		  
		  // The type pointed to changes for single-pool.
		  ReorgType_t *ri =
		    get_reorgtype_info ( field_type, info);
		  TREE_TYPE ( field) = ri->pointer_rep;
		}
	      tree base = base_type_of ( field);
	      if ( is_reorg_type ( base, info) )
		{
		  // strip off a layer of pointers
		  TREE_TYPE ( field) = TREE_TYPE ( TREE_TYPE( field));
		}
	    }
	}
    }

  // Mark the type as processed
  ( *( info->struct_types)) [ type] = { true, layout_changed};
}