global.c

GUN开源阻止下的编译器GCC

  bzero ((char *) local_reg_n_refs, sizeof local_reg_n_refs);
  for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
    if (reg_allocno[i] < 0 && reg_renumber[i] >= 0)
      {
	int regno = reg_renumber[i];
	int endregno = regno + HARD_REGNO_NREGS (regno, PSEUDO_REGNO_MODE (i));
	int j;

	for (j = regno; j < endregno; j++)
	  {
	    local_reg_n_refs[j] += reg_n_refs[i];
	    local_reg_live_length[j] += reg_live_length[i];
	  }
      }

  /* We can't override local-alloc for a reg used not just by local-alloc.  */
  for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
    if (regs_ever_live[i])
      local_reg_n_refs[i] = 0;

  /* Likewise for regs used in a SCRATCH.  */
  for (i = 0; i < scratch_list_length; i++)
    if (scratch_list[i])
      {
	int regno = REGNO (scratch_list[i]);
	int lim = regno + HARD_REGNO_NREGS (regno, GET_MODE (scratch_list[i]));
	int j;

	for (j = regno; j < lim; j++)
	  local_reg_n_refs[j] = 0;
      }
	
  /* Allocate the space for the conflict and preference tables and
     initialize them.  */

  hard_reg_conflicts
    = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
  bzero ((char *) hard_reg_conflicts, max_allocno * sizeof (HARD_REG_SET));

  hard_reg_preferences
    = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
  bzero ((char *) hard_reg_preferences, max_allocno * sizeof (HARD_REG_SET));
  
  hard_reg_copy_preferences
    = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
  bzero ((char *) hard_reg_copy_preferences,
	 max_allocno * sizeof (HARD_REG_SET));
  
  hard_reg_full_preferences
    = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
  bzero ((char *) hard_reg_full_preferences,
	 max_allocno * sizeof (HARD_REG_SET));
  
  regs_someone_prefers
    = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
  bzero ((char *) regs_someone_prefers, max_allocno * sizeof (HARD_REG_SET));

  allocno_row_words = (max_allocno + INT_BITS - 1) / INT_BITS;

  conflicts = (INT_TYPE *) alloca (max_allocno * allocno_row_words
				   * sizeof (INT_TYPE));
  bzero ((char *) conflicts,
	 max_allocno * allocno_row_words * sizeof (INT_TYPE));

  allocnos_live = (INT_TYPE *) alloca (allocno_row_words * sizeof (INT_TYPE));

  /* If there is work to be done (at least one reg to allocate),
     perform global conflict analysis and allocate the regs.  */

  if (max_allocno > 0)
    {
      /* Scan all the insns and compute the conflicts among allocnos
	 and between allocnos and hard regs.  */

      global_conflicts ();

      /* Eliminate conflicts between pseudos and eliminable registers.  If
	 the register is not eliminated, the pseudo won't really be able to
	 live in the eliminable register, so the conflict doesn't matter.
	 If we do eliminate the register, the conflict will no longer exist.
	 So in either case, we can ignore the conflict.  Likewise for
	 preferences.  */

      for (i = 0; i < max_allocno; i++)
	{
	  AND_COMPL_HARD_REG_SET (hard_reg_conflicts[i], eliminable_regset);
	  AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences[i],
				  eliminable_regset);
	  AND_COMPL_HARD_REG_SET (hard_reg_preferences[i], eliminable_regset);
	}

      /* Try to expand the preferences by merging them between allocnos.  */

      expand_preferences ();

      /* Determine the order to allocate the remaining pseudo registers.  */

      allocno_order = (int *) alloca (max_allocno * sizeof (int));
      for (i = 0; i < max_allocno; i++)
	allocno_order[i] = i;

      /* Default the size to 1, since allocno_compare uses it to divide by.
	 Also convert allocno_live_length of zero to -1.  A length of zero
	 can occur when all the registers for that allocno have reg_live_length
	 equal to -2.  In this case, we want to make an allocno, but not
	 allocate it.  So avoid the divide-by-zero and set it to a low
	 priority.  */

      for (i = 0; i < max_allocno; i++)
	{
	  if (allocno_size[i] == 0)
	    allocno_size[i] = 1;
	  if (allocno_live_length[i] == 0)
	    allocno_live_length[i] = -1;
	}

      qsort (allocno_order, max_allocno, sizeof (int), allocno_compare);
      
      prune_preferences ();

      if (file)
	dump_conflicts (file);

      /* Try allocating them, one by one, in that order,
	 except for parameters marked with reg_live_length[regno] == -2.  */

      for (i = 0; i < max_allocno; i++)
	if (reg_live_length[allocno_reg[allocno_order[i]]] >= 0)
	  {
	    /* If we have more than one register class,
	       first try allocating in the class that is cheapest
	       for this pseudo-reg.  If that fails, try any reg.  */
	    if (N_REG_CLASSES > 1)
	      {
		find_reg (allocno_order[i], HARD_CONST (0), 0, 0, 0);
		if (reg_renumber[allocno_reg[allocno_order[i]]] >= 0)
		  continue;
	      }
	    if (reg_alternate_class (allocno_reg[allocno_order[i]]) != NO_REGS)
	      find_reg (allocno_order[i], HARD_CONST (0), 1, 0, 0);
	  }
    }

  /* Do the reloads now while the allocno data still exist, so that we can
     try to assign new hard regs to any pseudo regs that are spilled.  */

#if 0 /* We need to eliminate regs even if there is no rtl code,
	 for the sake of debugging information.  */
  if (n_basic_blocks > 0)
#endif
    return reload (get_insns (), 1, file);
}

/* Sort predicate for ordering the allocnos.
   Returns -1 (1) if *v1 should be allocated before (after) *v2.  */

static int
allocno_compare (v1, v2)
     int *v1, *v2;
{
  /* Note that the quotient will never be bigger than
     the value of floor_log2 times the maximum number of
     times a register can occur in one insn (surely less than 100).
     Multiplying this by 10000 can't overflow.  */
  register int pri1
    = (((double) (floor_log2 (allocno_n_refs[*v1]) * allocno_n_refs[*v1])
	/ allocno_live_length[*v1])
       * 10000 * allocno_size[*v1]);
  register int pri2
    = (((double) (floor_log2 (allocno_n_refs[*v2]) * allocno_n_refs[*v2])
	/ allocno_live_length[*v2])
       * 10000 * allocno_size[*v2]);
  if (pri2 - pri1)
    return pri2 - pri1;

  /* If regs are equally good, sort by allocno,
     so that the results of qsort leave nothing to chance.  */
  return *v1 - *v2;
}

/* Scan the rtl code and record all conflicts and register preferences in the
   conflict matrices and preference tables.  */

static void
global_conflicts ()
{
  register int b, i;
  register rtx insn;
  short *block_start_allocnos;

  /* Make a vector that mark_reg_{store,clobber} will store in.  */
  regs_set = (rtx *) alloca (max_parallel * sizeof (rtx) * 2);

  block_start_allocnos = (short *) alloca (max_allocno * sizeof (short));

  for (b = 0; b < n_basic_blocks; b++)
    {
      bzero ((char *) allocnos_live, allocno_row_words * sizeof (INT_TYPE));

      /* Initialize table of registers currently live
	 to the state at the beginning of this basic block.
	 This also marks the conflicts among them.

	 For pseudo-regs, there is only one bit for each one
	 no matter how many hard regs it occupies.
	 This is ok; we know the size from PSEUDO_REGNO_SIZE.
	 For explicit hard regs, we cannot know the size that way
	 since one hard reg can be used with various sizes.
	 Therefore, we must require that all the hard regs
	 implicitly live as part of a multi-word hard reg
	 are explicitly marked in basic_block_live_at_start.  */

      {
	register int offset;
	REGSET_ELT_TYPE bit;
	register regset old = basic_block_live_at_start[b];
	int ax = 0;

#ifdef HARD_REG_SET
	hard_regs_live = old[0];
#else
	COPY_HARD_REG_SET (hard_regs_live, old);
#endif
	for (offset = 0, i = 0; offset < regset_size; offset++)
	  if (old[offset] == 0)
	    i += REGSET_ELT_BITS;
	  else
	    for (bit = 1; bit; bit <<= 1, i++)
	      {
		if (i >= max_regno)
		  break;
		if (old[offset] & bit)
		  {
		    register int a = reg_allocno[i];
		    if (a >= 0)
		      {
			SET_ALLOCNO_LIVE (a);
			block_start_allocnos[ax++] = a;
		      }
		    else if ((a = reg_renumber[i]) >= 0)
		      mark_reg_live_nc (a, PSEUDO_REGNO_MODE (i));
		  }
	      }

	/* Record that each allocno now live conflicts with each other
	   allocno now live, and with each hard reg now live.  */

	record_conflicts (block_start_allocnos, ax);
      }

      insn = basic_block_head[b];

      /* Scan the code of this basic block, noting which allocnos
	 and hard regs are born or die.  When one is born,
	 record a conflict with all others currently live.  */

      while (1)
	{
	  register RTX_CODE code = GET_CODE (insn);
	  register rtx link;

	  /* Make regs_set an empty set.  */

	  n_regs_set = 0;

	  if (code == INSN || code == CALL_INSN || code == JUMP_INSN)
	    {

#if 0
	      int i = 0;
	      for (link = REG_NOTES (insn);
		   link && i < NUM_NO_CONFLICT_PAIRS;
		   link = XEXP (link, 1))
		if (REG_NOTE_KIND (link) == REG_NO_CONFLICT)
		  {
		    no_conflict_pairs[i].allocno1
		      = reg_allocno[REGNO (SET_DEST (PATTERN (insn)))];
		    no_conflict_pairs[i].allocno2
		      = reg_allocno[REGNO (XEXP (link, 0))];
		    i++;
		  }
#endif /* 0 */

	      /* Mark any registers clobbered by INSN as live,
		 so they conflict with the inputs.  */

	      note_stores (PATTERN (insn), mark_reg_clobber);

	      /* Mark any registers dead after INSN as dead now.  */

	      for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
		if (REG_NOTE_KIND (link) == REG_DEAD)
		  mark_reg_death (XEXP (link, 0));

	      /* Mark any registers set in INSN as live,
		 and mark them as conflicting with all other live regs.
		 Clobbers are processed again, so they conflict with
		 the registers that are set.  */

	      note_stores (PATTERN (insn), mark_reg_store);

#ifdef AUTO_INC_DEC
	      for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
		if (REG_NOTE_KIND (link) == REG_INC)
		  mark_reg_store (XEXP (link, 0), NULL_RTX);
#endif

	      /* If INSN has multiple outputs, then any reg that dies here
		 and is used inside of an output
		 must conflict with the other outputs.  */

	      if (GET_CODE (PATTERN (insn)) == PARALLEL && !single_set (insn))
		for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
		  if (REG_NOTE_KIND (link) == REG_DEAD)
		    {
		      int used_in_output = 0;
		      int i;
		      rtx reg = XEXP (link, 0);

		      for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
			{
			  rtx set = XVECEXP (PATTERN (insn), 0, i);
			  if (GET_CODE (set) == SET
			      && GET_CODE (SET_DEST (set)) != REG
			      && !rtx_equal_p (reg, SET_DEST (set))
			      && reg_overlap_mentioned_p (reg, SET_DEST (set)))
			    used_in_output = 1;
			}
		      if (used_in_output)
			mark_reg_conflicts (reg);
		    }

	      /* Mark any registers set in INSN and then never used.  */

	      while (n_regs_set > 0)
		if (find_regno_note (insn, REG_UNUSED,
				     REGNO (regs_set[--n_regs_set])))
		  mark_reg_death (regs_set[n_regs_set]);
	    }

	  if (insn == basic_block_end[b])
	    break;
	  insn = NEXT_INSN (insn);
	}
    }
}
/* Expand the preference information by looking for cases where one allocno
   dies in an insn that sets an allocno.  If those two allocnos don't conflict,
   merge any preferences between those allocnos.  */

static void
expand_preferences ()
{
  rtx insn;
  rtx link;
  rtx set;

  /* We only try to handle the most common cases here.  Most of the cases
     where this wins are reg-reg copies.  */

  for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
    if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
	&& (set = single_set (insn)) != 0
	&& GET_CODE (SET_DEST (set)) == REG
	&& reg_allocno[REGNO (SET_DEST (set))] >= 0)
      for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
	if (REG_NOTE_KIND (link) == REG_DEAD
	    && GET_CODE (XEXP (link, 0)) == REG
	    && reg_allocno[REGNO (XEXP (link, 0))] >= 0
	    && ! CONFLICTP (reg_allocno[REGNO (SET_DEST (set))],
			    reg_allocno[REGNO (XEXP (link, 0))])
	    && ! CONFLICTP (reg_allocno[REGNO (XEXP (link, 0))],
			    reg_allocno[REGNO (SET_DEST (set))]))
	  {
	    int a1 = reg_allocno[REGNO (SET_DEST (set))];
	    int a2 = reg_allocno[REGNO (XEXP (link, 0))];

	    if (XEXP (link, 0) == SET_SRC (set))
	      {
		IOR_HARD_REG_SET (hard_reg_copy_preferences[a1],
				  hard_reg_copy_preferences[a2]);
		IOR_HARD_REG_SET (hard_reg_copy_preferences[a2],
				  hard_reg_copy_preferences[a1]);
	      }

	    IOR_HARD_REG_SET (hard_reg_preferences[a1],
			      hard_reg_preferences[a2]);
	    IOR_HARD_REG_SET (hard_reg_preferences[a2],
			      hard_reg_preferences[a1]);
	    IOR_HARD_REG_SET (hard_reg_full_preferences[a1],
			      hard_reg_full_preferences[a2]);
	    IOR_HARD_REG_SET (hard_reg_full_preferences[a2],
			      hard_reg_full_preferences[a1]);
	  }
}

/* Prune the preferences for global registers to exclude registers that cannot
   be used.
   
   Compute `regs_someone_prefers', which is a bitmask of the hard registers
   that are preferred by conflicting registers of lower priority.  If possible,
   we will avoid using these registers.  */
   
static void
prune_preferences ()
{
  int i, j;
  int allocno;
  
  /* Scan least most important to most important.
     For each allocno, remove from preferences registers that cannot be used,
     either because of conflicts or register type.  Then compute all registers
     preferred by each lower-priority register that conflicts.  */

  for (i = max_allocno - 1; i >= 0; i--)
    {
      HARD_REG_SET temp;

      allocno = allocno_order[i];
      COPY_HARD_REG_SET (temp, hard_reg_conflicts[allocno]);

      if (allocno_calls_crossed[allocno] == 0)
	IOR_HARD_REG_SET (temp, fixed_reg_set);
      else
	IOR_HARD_REG_SET (temp,	call_used_reg_set);

      IOR_COMPL_HARD_REG_SET
	(temp,
	 reg_class_contents[(int) reg_preferred_class (allocno_reg[allocno])]);