/* AE program profiling system.
   Code for GNU gcc compiler.
   Copyright (C) 1989, 1990 by James R. Larus (larus@cs.wisc.edu)

   AE and AEC are 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 1, or (at your option) any
   later version.

   AE and AEC are 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 GNU CC; see the file COPYING.  If not, write to James R.
   Larus, Computer Sciences Department, University of Wisconsin--Madison,
   1210 West Dayton Street, Madison, WI 53706, USA or to the Free
   Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */


/* $Header: /var/home/larus/AE/AE/RCS/ae.c,v 2.3 90/02/14 15:44:28 larus Exp Locker: larus $ */


/* AE profiling code is inserted into a function in two stages.  In
   the first stage, the function is analyzed to find which pseudo
   registers contain values used in address computations and which
   instructions mark the beginning of interesting events (e.g., loops,
   basic blocks).  This stage occurs after gcc has done most of its
   optimization, but before pseudo register references are transformed
   into hard registers.

   The second stage occurs just before instructions are written to the
   assembler output file.  At each interesting instruction, we invoke a
   routine that can output a schema event or add code to the function to
   record a runtime event. */


#include <stdio.h>
#include "config.h"
#include "rtl.h"
#include "basic-block.h"
#include "flags.h"
#include "tree.h"
#include "ae.h"
#include "ae-machine.h"
#include "schema.h"


void ae_after_block_end ();
void ae_before_block_end ();
void ae_block_start ();
void ae_function_end ();
void ae_function_start ();
void analyze_func_for_ae ();
void analyze_loops ();
void check_for_mem_refs ();
int condjump_p ();
list defns_reaching_insn ();
int difficulty_of_insn ();
int difficulty_of_pattern ();
void ensure_value_is_known ();
void find_defns_reaching_uses ();
void find_insn_dependences ();
void find_mem_refs ();
rtx gen_rtx ();
int get_max_uid ();
int implicit_last_block ();
int insn_marked_p ();
rtx insn_or_label ();
void jump_optimize ();
rtx jump_target ();
void mark_insn ();
int multiway_jump_p ();
rtx next_insn_or_label ();
void reaching_defn_analysis ();
void record_insn_effects ();
int simplejump_p ();


void abort ();
void bzero ();
void error ();
void fflush ();
void free ();
char *malloc ();


rtx *basic_block_end;
rtx *basic_block_head;
FILE *flow_dump_file;
int max_regno;
FILE *schema_out_file;



/* Entry N is information about instruction N. */

aux_insn_info *insn_info;


/* Function's name. */

char *fun_name;


/* Non-zero means write register value upon function entry. */

char record_reg_on_entry [FIRST_PSEUDO_REGISTER];



/* Initialize ae profiling of a function by collecting information
   about the instructions and basic blocks. */

void
ae_function (insns, asm_out_file, write_symbols, optimize, decl)
     rtx insns;
     FILE *asm_out_file;
     enum debugger write_symbols;
     int optimize;
     tree decl;
{
  /* Get the function's name, as described by its rtl.
     This may be different from the decl_name name used in the source file.
     Derived from: ASSEMBLE_FUNCTION. */
  rtx x = DECL_RTL (decl);
  rtx n;
  register int i;

  if (GET_CODE (x) != MEM)
    abort ();
  n = XEXP (x, 0);
  if (GET_CODE (n) != SYMBOL_REF)
    abort ();
  fun_name = XSTR (n, 0);

  /* Initialize data structures. */
  insn_info =
    (aux_insn_info *) malloc (get_max_uid () * sizeof (aux_insn_info));
  bzero (insn_info, get_max_uid () * sizeof (aux_insn_info));
  initialize_look_ahead_buffer ();
  bzero (record_reg_on_entry, FIRST_PSEUDO_REGISTER * sizeof (char));

  analyze_func_for_ae (insns, optimize);
}


/* Invoked after profiling a function. */

void
ae_end_function ()
{
  if (n_basic_blocks == 0)
    ae_function_start ();	/* Did not see any instructions */
  record_insn_effects (NULL, NULL); /* Flush buffer */
  if (implicit_last_block ())
    {
      /* Last instruction is cjump w/ fall-thru to implicit block. */
      ae_block_start (NULL, n_basic_blocks, 1);
      ae_before_block_end (NULL, n_basic_blocks);
      ae_after_block_end (NULL, n_basic_blocks);
    }
  ae_function_end ();
  free (insn_info);
  fflush (schema_out_file);
}


/* Make a pass over the code for a function and find all which
   instructions mark the beginning of interesting events. */

static void
analyze_func_for_ae (insns, optimize)
     rtx insns;
     int optimize;
{
  register rtx insn, x;
  register int i;

  if (!optimize)
    /* We need the jump links, even if optimizations isn't turned on. */
    jump_optimize (insns, 0, 0);

  /* Reanalysis the function's control flow (which may have changed since
     flow analysis) and compute reaching definitions. */
  reaching_defn_analysis (insns, max_regno, flow_dump_file);

  for (insn = insns; insn != NULL; insn = NEXT_INSN (insn))
    if (REAL_INSN_P (insn))
      check_for_mem_refs (insn);

  /* Mark the control flow graphs on the instructions. */
  for (i = 0; i < n_basic_blocks; i++)
    {
      /* Mark first and last instruction or label in each basic block. */
      mark_insn (basic_block_head [i], BLOCK_START_FLAG);
      insn_info [INSN_UID (basic_block_head [i])].in_block = i;

      x = basic_block_end [i];
      if (x != NULL)
	{
	  mark_insn (x, BLOCK_END_FLAG);
	  if (GET_CODE (x) == CODE_LABEL)
	    ;
	  else if (GET_CODE (x) == JUMP_INSN && simplejump_p (x))
	    mark_insn (jump_target (x), JUMP_TARGET_FLAG);
	  else if (GET_CODE (x) == JUMP_INSN && condjump_p (x))
	    {
	      /* Record targets of conditional branch. */
	      mark_insn (jump_target (x), CJUMP_TARGET_FLAG);
	      /* Fall-thru block is target also. */
	      mark_insn (next_insn_or_label (x, 1), CJUMP_TARGET_FLAG);
	    }
	  else if (multiway_jump_p (x))
	    {
	      rtx body =  PATTERN (x);
	      register int vlen, j;

	      vlen = XVECLEN (body, 0);
	      for (j = 0; j < vlen; j++)
		mark_insn (XEXP (XVECEXP (body, 0, j), 0), CJUMP_TARGET_FLAG);
	    }
	}
    }

  /* Mark first and last instruction in function. */
  if (n_basic_blocks > 0)
    {
      mark_insn (insn_or_label (basic_block_head [0], 1), FUNCTION_START_FLAG);
      mark_insn (basic_block_end [n_basic_blocks - 1], FUNCTION_END_FLAG);
    }

  analyze_loops (insns);
}


void
mark_insn (insn, flag)
     rtx insn;
     int flag;
{
  if (insn != NULL)
    insn_info [INSN_UID (insn)].flags |= flag;
}


int
insn_marked_p (insn, flag)
     rtx insn;
     int flag;
{
  if (insn != NULL)
    return (insn_info [INSN_UID (insn)].flags & flag);
  else
    return 0;
}


static rtx check_insn;		/* Too bad C doesn't have closures */


/* Check whether an instruction accesses memory, and if so, mark the
   instructions that produce operands for the load/store. */

static void
check_for_mem_refs (insn)
     rtx insn;
{
  void thunk_for_check_expr ();

  check_insn = insn;
  APPLY_TO_EXP_IN_INSN (PATTERN (insn), e,
			find_mem_refs (e, thunk_for_check_expr));
}


static void
thunk_for_check_expr (exp, base, offset)
     rtx exp, base, offset;
{
  if (REG_P (base))
    ensure_value_is_known (check_insn, base);
  if (offset && REG_P (offset))
    ensure_value_is_known (check_insn, offset);
}


/* Traverse an rtx expression X and invoke FUN on each MEM reference.
   Pass the expression, base, and offset as arguments. */

void
find_mem_refs (x, fun)
     register rtx x;
     void (*fun) ();
{
  if (GET_CODE (x) == MEM)
    {
      register rtx em = XEXP (x, 0);

      if (REG_P (em))
	fun (x, em, NULL);
      else if (GET_CODE (em) == PLUS)
	fun (x, XEXP (em, 0), XEXP (em, 1));
      else if (GET_CODE (em) == MINUS)
	fun (x, XEXP (em, 0),
	     gen_rtx (CONST_INT, VOIDmode, - XINT (XEXP (em, 1), 0)));
      else if (CONSTANT_P (em))
	fun (x, em, NULL);
    }
  else
    APPLY_TO_EXP_IN_INSN (x, e, find_mem_refs (e, fun));
}



/* Return the nth instruction or label *following* a given instruction.
   Return NULL if there is no such object. */

rtx
next_insn_or_label (insn, n)
     register rtx insn;
     register int n;
{
  for (insn = NEXT_INSN (insn) ; insn != NULL; insn = NEXT_INSN (insn))
    if (!INSN_DELETED_P (insn)
	&& (REAL_INSN_P (insn) || GET_CODE (insn) == CODE_LABEL))
      if (--n == 0)
	return insn;

  return NULL;
}


/* Return the nth instruction or label *from* a given instruction
   (0th => insn). Return NULL if there is no such object. */

rtx
insn_or_label (insn, n)
     register rtx insn;
     int n;
{
  for ( ; insn != NULL; insn = NEXT_INSN (insn))
    if (!INSN_DELETED_P (insn)
	&& (REAL_INSN_P (insn) || GET_CODE (insn) == CODE_LABEL))
      if (--n <= 0)
	return insn;

  return NULL;
}


/* Given an instruction, return the instruction at the head of its
   block.  Return NULL if there is no such instruction. */

rtx
find_block_head (insn)
     rtx insn;
{

  for ( ; insn != NULL; insn = PREV_INSN (insn))
    if (insn_marked_p (insn, BLOCK_START_FLAG))
      return insn;

  return NULL;
}


/* Return the instruction that is the target of a jump instruction. */

rtx
jump_target (insn)
     rtx insn;
{
  rtx p = PATTERN (insn);
  rtx e = SET_SRC (p);

  if (GET_CODE (e) == LABEL_REF)
    return XEXP (e, 0);
  else if (GET_CODE (XEXP (e, 1)) == LABEL_REF)
    return XEXP (XEXP (e, 1), 0);
  else
    return XEXP (XEXP (e, 2), 0);
}


/* Return non-zero if instruction is a multiway (not just conditional)
   branch. */

int
multiway_jump_p (insn)
     rtx insn;
{
  if (GET_CODE (insn) == JUMP_INSN)
    {
      rtx body =  PATTERN (insn);
      return (GET_CODE (body) == ADDR_VEC || GET_CODE (body) == ADDR_DIFF_VEC);
    }
  else
    return 0;
}


/* Return non-zero if block in which INSN is the first instruction is
   the target of a conditional jump. */

int
cjump_target_p (insn)
     rtx insn;
{
  rtx block_head = insn;

  if (block_head != NULL)
    return (insn_marked_p (block_head, CJUMP_TARGET_FLAG));
  else
    return 0;
}


/* Given the first instruction of a block, return the block's number. */

int
head_to_block_number (target_head)
     register rtx target_head;
{
  return insn_info [INSN_UID (target_head)].in_block;
}



/* Given an INSN that uses register REG, mark all instructions that
   produce a value for REG so that we know its contents when executing
   the schema.

   Instructions fall into three catagories:

   Easy.  Rx <- constant or Rx <- address

   Hard.  Rx <- Ry op Rz

   Impossible.  Rx <- mem [...]
		Rx <- call (...)

   Easy instructions can obviously be calculated by the schema.
   Impossible instructions require an event to record the value loaded
   from memory.

   Hard instructions appear to require some effort.  If we know their
   operands, we can obviously calculate their result in the schema.
   Hence, we need to know Ry and Rz in the schema--which we ensure by
   applying the process recursively.

   A cycle of hard instructions presents no problems since the initial
   values must come from instructions outside of the cycle. */


/* Ensure that the value of REG is known for instruction INSN. */

static void
ensure_value_is_known (insn, reg)
     rtx insn, reg;
{
  list defns = defns_reaching_insn (insn, reg);

  if (defns != NULL)
    DOLIST (d, rtx, defns, find_insn_dependences (d))
  else
    find_defns_reaching_uses (insn, insn);
}


/* Find the dependences between `hard' instructions starting with the
   given instruction. */

static void
find_insn_dependences (insn)
     register rtx insn;
{
  if (insn_marked_p (insn,
		     EASY_INSN_FLAG | HARD_INSN_FLAG | IMPOSSIBLE_INSN_FLAG))
    /* Have already seen this instruction. */
    return;

  switch (difficulty_of_insn (insn))
    {
    case EASY_INSN_FLAG:
      mark_insn (insn, EASY_INSN_FLAG);
      break;

    case HARD_INSN_FLAG:
      mark_insn (insn, HARD_INSN_FLAG);
      find_defns_reaching_uses (insn, insn);
      break;

    case IMPOSSIBLE_INSN_FLAG:
      mark_insn (insn, IMPOSSIBLE_INSN_FLAG);
      break;

    default:
      error ("Unknown instruction difficulty."); /*NOTREACHED*/
    }
}


/* Return a value indicating the whether INSN is easy, hard, or impossible. */

static int
difficulty_of_insn (insn)
     rtx insn;
{
  return difficulty_of_pattern (PATTERN (insn));
}


static int
difficulty_of_pattern (p)
     rtx p;
{
  if (GET_CODE (p) == SET)
    {
      register rtx e = SET_SRC (p);

      while (1)
	switch (GET_CODE (e))
	  {
	  case PLUS:
	  case MINUS:
	  case MULT:
	  case DIV:
	  case MOD:
	  case AND:
	  case IOR:
	  case LSHIFT:
	  case ASHIFT:
	  case LSHIFTRT:
	    return HARD_INSN_FLAG;

	  case NEG:
	  case NOT:
	    return HARD_INSN_FLAG;

	  case SYMBOL_REF:
	    return EASY_INSN_FLAG;

	  case SIGN_EXTEND:
	    e = XEXP (e, 0);
	    break;

	  case CONST:
	    {
	      /* Instruction is: rx <- @sym or rx <- @sym + c. */
	      rtx t = XEXP (e, 0);
	      rtx base, offset;

	      if (GET_CODE (t) == PLUS)
		{
		  base = XEXP (t, 0), offset = XEXP (t, 1);
		  if (GET_CODE (base) == SYMBOL_REF
		      && GET_CODE (offset) == CONST_INT)
		    return EASY_INSN_FLAG;
		  else
		    return IMPOSSIBLE_INSN_FLAG;
		}
	      else if (GET_CODE (t) == SYMBOL_REF)
		return EASY_INSN_FLAG;
	      else
		return IMPOSSIBLE_INSN_FLAG;
	    }

	  case CONST_INT:
	    return EASY_INSN_FLAG;

	  case REG:
	  case SUBREG:
	    return HARD_INSN_FLAG;

	  case LABEL_REF:
	    return EASY_INSN_FLAG;

	  case CALL:
	    return IMPOSSIBLE_INSN_FLAG;

	  default:
	    return IMPOSSIBLE_INSN_FLAG;
	  }
    }
  else if (GET_CODE (p) == PARALLEL)
    {
      register int i;
      int difficulty = 0;

      /* Instruction is as difficult as the hardest piece. */
      for (i = 0; i < XVECLEN (p, 0); i ++)
	{
	  int d = difficulty_of_pattern (XVECEXP (p, 0, i));
	  if (d > difficulty)
	    difficulty = d;
	}
      return difficulty;
    }
  else
    return IMPOSSIBLE_INSN_FLAG;
}


/* Given an INSN, find all *uses* of values contained in registers in the
   instruction and ensure that their values is known. */

static void
find_defns_reaching_uses (insn, x)
     rtx insn, x;
{
  register int regno;

  switch (GET_CODE (x))
    {
    case LABEL_REF:
    case SYMBOL_REF:
    case CONST_INT:
    case CONST:
    case CONST_DOUBLE:
    case CC0:
    case PC:
    case CLOBBER:
    case ADDR_VEC:
    case ADDR_DIFF_VEC:
    case ASM_INPUT:
      return;

    case SUBREG:
      x = SUBREG_REG (x);
      /* This isn't supposed to happen, but it does... */
      if (GET_CODE (x) == MEM) goto default_case;
      /* Fall through */

    case REG:
      regno = REGNO (x);
      {
	list defns = defns_reaching_insn (insn, x);

	if (defns == NULL || REGISTER_DEFINED_IN_CALL (regno))
	  record_reg_on_entry [regno] = 1; /* Need value upon function entry */
	DOLIST (d, rtx, defns, {find_insn_dependences (d);});
      }
      return;

    case INSN:
    case CALL_INSN:
    case JUMP_INSN:
      find_defns_reaching_uses (insn, PATTERN (x));
      return;

    case SET:
      if (GET_CODE (SET_DEST (x)) == MEM)
	/* If a store instruction, then get address of store */
	find_defns_reaching_uses (insn, SET_DEST (x));
      else
	/* Otherwise, want the inputs to the computation */
	find_defns_reaching_uses (insn, SET_SRC (x));
      return;

    default:
    default_case:
      APPLY_TO_EXP_IN_INSN (x, e, find_defns_reaching_uses (insn, e));
      return;
    }
}



/* List operations: */

list
cons (head, tail)
     int head;
     list tail;
{
  register list x = (list) malloc (sizeof (list_cell));

  CAR (x) = head;
  CDR (x) = tail;
  return (x);
}


/* Pop and deallocate the first element in a list and return the tail
   of the list. */

list
cdr_n_free (lst)
     list lst;
{
  list n;

  if (lst == NULL)
    error ("Pop null list?");

  n = CDR (lst);
  free (lst);
  return n;
}


void
free_list (lst)
     register list lst;
{
  register list n;

  while (lst != NULL)
    {
      n = CDR (lst);
      free (lst);
      lst = n;
    }
}
