unroll.c

GCC编译器源代码

	    temp = temp / factors[i].factor;
	  }

      /* Start with the larger factors first so that we generally
	 get lots of unrolling.  */

      unroll_number = 1;
      temp = insn_count;
      for (i = 3; i >= 0; i--)
	while (factors[i].count--)
	  {
	    if (temp * factors[i].factor < MAX_UNROLLED_INSNS)
	      {
		unroll_number *= factors[i].factor;
		temp *= factors[i].factor;
	      }
	    else
	      break;
	  }

      /* If we couldn't find any factors, then unroll as in the normal
	 case.  */
      if (unroll_number == 1)
	{
	  if (loop_dump_stream)
	    fprintf (loop_dump_stream,
		     "Loop unrolling: No factors found.\n");
	}
      else
	unroll_type = UNROLL_MODULO;
    }


  /* Default case, calculate number of times to unroll loop based on its
     size.  */
  if (unroll_number == 1)
    {
      if (8 * insn_count < MAX_UNROLLED_INSNS)
	unroll_number = 8;
      else if (4 * insn_count < MAX_UNROLLED_INSNS)
	unroll_number = 4;
      else
	unroll_number = 2;

      unroll_type = UNROLL_NAIVE;
    }

  /* Now we know how many times to unroll the loop.  */

  if (loop_dump_stream)
    fprintf (loop_dump_stream,
	     "Unrolling loop %d times.\n", unroll_number);


  if (unroll_type == UNROLL_COMPLETELY || unroll_type == UNROLL_MODULO)
    {
      /* Loops of these types should never start with a jump down to
	 the exit condition test.  For now, check for this case just to
	 be sure.  UNROLL_NAIVE loops can be of this form, this case is
	 handled below.  */
      insn = loop_start;
      while (GET_CODE (insn) != CODE_LABEL && GET_CODE (insn) != JUMP_INSN)
	insn = NEXT_INSN (insn);
      if (GET_CODE (insn) == JUMP_INSN)
	abort ();
    }

  if (unroll_type == UNROLL_COMPLETELY)
    {
      /* Completely unrolling the loop:  Delete the compare and branch at
	 the end (the last two instructions).   This delete must done at the
	 very end of loop unrolling, to avoid problems with calls to
	 back_branch_in_range_p, which is called by find_splittable_regs.
	 All increments of splittable bivs/givs are changed to load constant
	 instructions.  */

      copy_start = loop_start;

      /* Set insert_before to the instruction immediately after the JUMP_INSN
	 (or BARRIER), so that any NOTEs between the JUMP_INSN and the end of
	 the loop will be correctly handled by copy_loop_body.  */
      insert_before = NEXT_INSN (last_loop_insn);

      /* Set copy_end to the insn before the jump at the end of the loop.  */
      if (GET_CODE (last_loop_insn) == BARRIER)
	copy_end = PREV_INSN (PREV_INSN (last_loop_insn));
      else if (GET_CODE (last_loop_insn) == JUMP_INSN)
	{
#ifdef HAVE_cc0
	  /* The instruction immediately before the JUMP_INSN is a compare
	     instruction which we do not want to copy.  */
	  copy_end = PREV_INSN (PREV_INSN (last_loop_insn));
#else
	  /* The instruction immediately before the JUMP_INSN may not be the
	     compare, so we must copy it.  */
	  copy_end = PREV_INSN (last_loop_insn);
#endif
	}
      else
	{
	  /* We currently can't unroll a loop if it doesn't end with a
	     JUMP_INSN.  There would need to be a mechanism that recognizes
	     this case, and then inserts a jump after each loop body, which
	     jumps to after the last loop body.  */
	  if (loop_dump_stream)
	    fprintf (loop_dump_stream,
		     "Unrolling failure: loop does not end with a JUMP_INSN.\n");
	  return;
	}
    }
  else if (unroll_type == UNROLL_MODULO)
    {
      /* Partially unrolling the loop:  The compare and branch at the end
	 (the last two instructions) must remain.  Don't copy the compare
	 and branch instructions at the end of the loop.  Insert the unrolled
	 code immediately before the compare/branch at the end so that the
	 code will fall through to them as before.  */

      copy_start = loop_start;

      /* Set insert_before to the jump insn at the end of the loop.
	 Set copy_end to before the jump insn at the end of the loop.  */
      if (GET_CODE (last_loop_insn) == BARRIER)
	{
	  insert_before = PREV_INSN (last_loop_insn);
	  copy_end = PREV_INSN (insert_before);
	}
      else if (GET_CODE (last_loop_insn) == JUMP_INSN)
	{
#ifdef HAVE_cc0
	  /* The instruction immediately before the JUMP_INSN is a compare
	     instruction which we do not want to copy or delete.  */
	  insert_before = PREV_INSN (last_loop_insn);
	  copy_end = PREV_INSN (insert_before);
#else
	  /* The instruction immediately before the JUMP_INSN may not be the
	     compare, so we must copy it.  */
	  insert_before = last_loop_insn;
	  copy_end = PREV_INSN (last_loop_insn);
#endif
	}
      else
	{
	  /* We currently can't unroll a loop if it doesn't end with a
	     JUMP_INSN.  There would need to be a mechanism that recognizes
	     this case, and then inserts a jump after each loop body, which
	     jumps to after the last loop body.  */
	  if (loop_dump_stream)
	    fprintf (loop_dump_stream,
		     "Unrolling failure: loop does not end with a JUMP_INSN.\n");
	  return;
	}
    }
  else
    {
      /* Normal case: Must copy the compare and branch instructions at the
	 end of the loop.  */

      if (GET_CODE (last_loop_insn) == BARRIER)
	{
	  /* Loop ends with an unconditional jump and a barrier.
	     Handle this like above, don't copy jump and barrier.
	     This is not strictly necessary, but doing so prevents generating
	     unconditional jumps to an immediately following label.

	     This will be corrected below if the target of this jump is
	     not the start_label.  */

	  insert_before = PREV_INSN (last_loop_insn);
	  copy_end = PREV_INSN (insert_before);
	}
      else if (GET_CODE (last_loop_insn) == JUMP_INSN)
	{
	  /* Set insert_before to immediately after the JUMP_INSN, so that
	     NOTEs at the end of the loop will be correctly handled by
	     copy_loop_body.  */
	  insert_before = NEXT_INSN (last_loop_insn);
	  copy_end = last_loop_insn;
	}
      else
	{
	  /* We currently can't unroll a loop if it doesn't end with a
	     JUMP_INSN.  There would need to be a mechanism that recognizes
	     this case, and then inserts a jump after each loop body, which
	     jumps to after the last loop body.  */
	  if (loop_dump_stream)
	    fprintf (loop_dump_stream,
		     "Unrolling failure: loop does not end with a JUMP_INSN.\n");
	  return;
	}

      /* If copying exit test branches because they can not be eliminated,
	 then must convert the fall through case of the branch to a jump past
	 the end of the loop.  Create a label to emit after the loop and save
	 it for later use.  Do not use the label after the loop, if any, since
	 it might be used by insns outside the loop, or there might be insns
	 added before it later by final_[bg]iv_value which must be after
	 the real exit label.  */
      exit_label = gen_label_rtx ();

      insn = loop_start;
      while (GET_CODE (insn) != CODE_LABEL && GET_CODE (insn) != JUMP_INSN)
	insn = NEXT_INSN (insn);

      if (GET_CODE (insn) == JUMP_INSN)
	{
	  /* The loop starts with a jump down to the exit condition test.
	     Start copying the loop after the barrier following this
	     jump insn.  */
	  copy_start = NEXT_INSN (insn);

	  /* Splitting induction variables doesn't work when the loop is
	     entered via a jump to the bottom, because then we end up doing
	     a comparison against a new register for a split variable, but
	     we did not execute the set insn for the new register because
	     it was skipped over.  */
	  splitting_not_safe = 1;
	  if (loop_dump_stream)
	    fprintf (loop_dump_stream,
		     "Splitting not safe, because loop not entered at top.\n");
	}
      else
	copy_start = loop_start;
    }

  /* This should always be the first label in the loop.  */
  start_label = NEXT_INSN (copy_start);
  /* There may be a line number note and/or a loop continue note here.  */
  while (GET_CODE (start_label) == NOTE)
    start_label = NEXT_INSN (start_label);
  if (GET_CODE (start_label) != CODE_LABEL)
    {
      /* This can happen as a result of jump threading.  If the first insns in
	 the loop test the same condition as the loop's backward jump, or the
	 opposite condition, then the backward jump will be modified to point
	 to elsewhere, and the loop's start label is deleted.

	 This case currently can not be handled by the loop unrolling code.  */

      if (loop_dump_stream)
	fprintf (loop_dump_stream,
		 "Unrolling failure: unknown insns between BEG note and loop label.\n");
      return;
    }
  if (LABEL_NAME (start_label))
    {
      /* The jump optimization pass must have combined the original start label
	 with a named label for a goto.  We can't unroll this case because
	 jumps which go to the named label must be handled differently than
	 jumps to the loop start, and it is impossible to differentiate them
	 in this case.  */
      if (loop_dump_stream)
	fprintf (loop_dump_stream,
		 "Unrolling failure: loop start label is gone\n");
      return;
    }

  if (unroll_type == UNROLL_NAIVE
      && GET_CODE (last_loop_insn) == BARRIER
      && start_label != JUMP_LABEL (PREV_INSN (last_loop_insn)))
    {
      /* In this case, we must copy the jump and barrier, because they will
	 not be converted to jumps to an immediately following label.  */

      insert_before = NEXT_INSN (last_loop_insn);
      copy_end = last_loop_insn;
    }

  if (unroll_type == UNROLL_NAIVE
      && GET_CODE (last_loop_insn) == JUMP_INSN
      && start_label != JUMP_LABEL (last_loop_insn))
    {
      /* ??? The loop ends with a conditional branch that does not branch back
	 to the loop start label.  In this case, we must emit an unconditional
	 branch to the loop exit after emitting the final branch.
	 copy_loop_body does not have support for this currently, so we
	 give up.  It doesn't seem worthwhile to unroll anyways since
	 unrolling would increase the number of branch instructions
	 executed.  */
      if (loop_dump_stream)
	fprintf (loop_dump_stream,
		 "Unrolling failure: final conditional branch not to loop start\n");
      return;
    }

  /* Allocate a translation table for the labels and insn numbers.
     They will be filled in as we copy the insns in the loop.  */

  max_labelno = max_label_num ();
  max_insnno = get_max_uid ();

  map = (struct inline_remap *) alloca (sizeof (struct inline_remap));

  map->integrating = 0;

  /* Allocate the label map.  */

  if (max_labelno > 0)
    {
      map->label_map = (rtx *) alloca (max_labelno * sizeof (rtx));

      local_label = (char *) alloca (max_labelno);
      bzero (local_label, max_labelno);
    }
  else
    map->label_map = 0;

  /* Search the loop and mark all local labels, i.e. the ones which have to
     be distinct labels when copied.  For all labels which might be
     non-local, set their label_map entries to point to themselves.
     If they happen to be local their label_map entries will be overwritten
     before the loop body is copied.  The label_map entries for local labels
     will be set to a different value each time the loop body is copied.  */

  for (insn = copy_start; insn != loop_end; insn = NEXT_INSN (insn))
    {
      if (GET_CODE (insn) == CODE_LABEL)
	local_label[CODE_LABEL_NUMBER (insn)] = 1;
      else if (GET_CODE (insn) == JUMP_INSN)
	{
	  if (JUMP_LABEL (insn))
	    map->label_map[CODE_LABEL_NUMBER (JUMP_LABEL (insn))]
	      = JUMP_LABEL (insn);
	  else if (GET_CODE (PATTERN (insn)) == ADDR_VEC
		   || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
	    {
	      rtx pat = PATTERN (insn);
	      int diff_vec_p = GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC;
	      int len = XVECLEN (pat, diff_vec_p);
	      rtx label;

	      for (i = 0; i < len; i++)
		{
		  label = XEXP (XVECEXP (pat, diff_vec_p, i), 0);
		  map->label_map[CODE_LABEL_NUMBER (label)] = label;
		}
	    }
	}
    }

  /* Allocate space for the insn map.  */

  map->insn_map = (rtx *) alloca (max_insnno * sizeof (rtx));

  /* Set this to zero, to indicate that we are doing loop unrolling,
     not function inlining.  */
  map->inline_target = 0;

  /* The register and constant maps depend on the number of registers
     present, so the final maps can't be created until after
     find_splittable_regs is called.  However, they are needed for
     preconditioning, so we create temporary maps when preconditioning
     is performed.  */

  /* The preconditioning code may allocate two new pseudo registers.  */
  maxregnum = max_reg_num ();

  /* Allocate and zero out the splittable_regs and addr_combined_regs
     arrays.  These must be zeroed here because they will be used if
     loop preconditioning is performed, and must be zero for that case.

     It is safe to do this here, since the extra registers created by the
     preconditioning code and find_splittable_regs will never be used
     to access the splittable_regs[] and addr_combined_regs[] arrays.  */

  splittable_regs = (rtx *) alloca (maxregnum * sizeof (rtx));
  bzero ((char *) splittable_regs, maxregnum * sizeof (rtx));
  splittable_regs_updates = (int *) alloca (maxregnum * sizeof (int));
  bzero ((char *) splittable_regs_updates, maxregnum * sizeof (int));
  addr_combined_regs
    = (struct induction **) alloca (maxregnum * sizeof (struct induction *));
  bzero ((char *) addr_combined_regs, maxregnum * sizeof (struct induction *));