* Integrate Haifa instruction scheduler.

        * Integrate regmove pass.
See ChangeLog for deatils.

From-SVN: r14770

1 files changed, 752 insertions, 0 deletions

diff --git a/gcc/loop.c b/gcc/loop.c
index b54e677b928..2c4092d0c85 100644
--- a/gcc/loop.c
+++ b/gcc/loop.c
@@ -81,6 +81,42 @@ static rtx *loop_number_loop_starts, *loop_number_loop_ends;
 
 int *loop_outer_loop;
 
+#ifdef HAIFA
+/* The main output of analyze_loop_iterations is placed here */
+
+int *loop_can_insert_bct;
+
+/* For each loop, determines whether some of its inner loops has used
+   count register */
+
+int *loop_used_count_register;
+
+/* For each loop, remember its unrolling factor (if at all).
+   contents of the array:
+   0/1: not unrolled.
+   -1: completely unrolled - no further instrumentation is needed.
+   >1: holds the exact amount of unrolling.  */
+
+int *loop_unroll_factor;
+int *loop_unroll_iter;
+
+/* loop parameters for arithmetic loops. These loops have a loop variable
+   which is initialized to loop_start_value, incremented in each iteration
+   by "loop_increment".  At the end of the iteration the loop variable is
+   compared to the loop_comparison_value (using loop_comparison_code).  */
+
+rtx *loop_increment;
+rtx *loop_comparison_value;
+rtx *loop_start_value;
+enum rtx_code *loop_comparison_code;
+
+/* for debugging: selects sub-range of loops for which the bct optimization
+   is invoked.  The numbering is per compilation-unit.  */
+int dbg_bct_min = -1;
+int dbg_bct_max = -1;
+#endif  /* HAIFA */
+
+
 /* Indexed by loop number, contains a nonzero value if the "loop" isn't
    really a loop (an insn outside the loop branches into it).  */
 
@@ -286,6 +322,32 @@ static int maybe_eliminate_biv_1 ();
 static int last_use_this_basic_block ();
 static void record_initial ();
 static void update_reg_last_use ();
+
+#ifdef HAIFA
+/* This is extern from unroll.c */
+void iteration_info ();
+
+/* Two main functions for implementing bct:
+   first - to be called before loop unrolling, and the second - after */
+static void analyze_loop_iterations ();
+static void insert_bct ();
+
+/* Auxiliary function that inserts the bct pattern into the loop */
+static void instrument_loop_bct ();
+
+/* Indirect_jump_in_function is computed once per function.  */
+int indirect_jump_in_function = 0;
+static int indirect_jump_in_function_p ();
+
+int loop_number ();
+static int is_power_of_2();
+static int is_conditional_branch ();
+
+/* Debugging functions.  */
+int fix_bct_param ();
+static int check_bct_param ();
+#endif  /* HAIFA */
+
 
 /* Relative gain of eliminating various kinds of operations.  */
 int add_cost;
@@ -379,6 +441,32 @@ loop_optimize (f, dumpfile)
   loop_number_exit_labels = (rtx *) alloca (max_loop_num * sizeof (rtx));
   loop_number_exit_count = (int *) alloca (max_loop_num * sizeof (int));
 
+#ifdef HAIFA
+  /* Allocate for BCT optimization */
+  loop_can_insert_bct = (int *) alloca (max_loop_num * sizeof (int));
+  bzero ((char *) loop_can_insert_bct, max_loop_num * sizeof (int));
+
+  loop_used_count_register = (int *) alloca (max_loop_num * sizeof (int));
+  bzero ((char *) loop_used_count_register, max_loop_num * sizeof (int));
+
+  loop_unroll_factor = (int *) alloca (max_loop_num *sizeof (int));
+  bzero ((char *) loop_unroll_factor, max_loop_num * sizeof (int));
+
+  loop_unroll_iter = (int *) alloca (max_loop_num *sizeof (int));
+  bzero ((char *) loop_unroll_iter, max_loop_num * sizeof (int));
+
+  loop_increment = (rtx *) alloca (max_loop_num * sizeof (rtx));
+  loop_comparison_value = (rtx *) alloca (max_loop_num * sizeof (rtx));
+  loop_start_value = (rtx *) alloca (max_loop_num * sizeof (rtx));
+  bzero ((char *) loop_increment, max_loop_num * sizeof (rtx));
+  bzero ((char *) loop_comparison_value, max_loop_num * sizeof (rtx));
+  bzero ((char *) loop_start_value, max_loop_num * sizeof (rtx));
+
+  loop_comparison_code 
+    = (enum rtx_code *) alloca (max_loop_num * sizeof (enum rtx_code));
+  bzero ((char *) loop_comparison_code, max_loop_num * sizeof (enum rtx_code));
+#endif  /* HAIFA */
+
   /* Find and process each loop.
      First, find them, and record them in order of their beginnings.  */
   find_and_verify_loops (f);
@@ -430,6 +518,12 @@ loop_optimize (f, dumpfile)
   if (flag_unroll_loops && write_symbols != NO_DEBUG)
     find_loop_tree_blocks ();
 
+#ifdef HAIFA
+  /* determine if the function has indirect jump. If it does,
+     we cannot instrument loops in this function with bct */
+  indirect_jump_in_function = indirect_jump_in_function_p (f);
+#endif  /* HAIFA */
+
   /* Now scan the loops, last ones first, since this means inner ones are done
      before outer ones.  */
   for (i = max_loop_num-1; i >= 0; i--)
@@ -2639,6 +2733,11 @@ mark_loop_jump (x, loop_num)
 
       if (loop_num != -1)
 	{
+#ifdef HAIFA
+	  LABEL_OUTSIDE_LOOP_P (x) = 1;
+	  LABEL_NEXTREF (x) = loop_number_exit_labels[loop_num];
+#endif  /* HAIFA */
+
 	  loop_number_exit_labels[loop_num] = x;
 
 	  for (outer_loop = loop_num; outer_loop != -1;
@@ -3755,6 +3854,16 @@ strength_reduce (scan_start, end, loop_top, insn_count,
      so that "decrement and branch until zero" insn can be used.  */
   check_dbra_loop (loop_end, insn_count, loop_start);
 
+#ifdef HAIFA
+  /* record loop-variables relevant for BCT optimization before unrolling
+     the loop.  Unrolling may update part of this information, and the
+     correct data will be used for generating the BCT.  */
+#ifdef HAVE_decrement_and_branch_on_count
+  if (HAVE_decrement_and_branch_on_count)
+    analyze_loop_iterations (loop_start, loop_end);
+#endif
+#endif  /* HAIFA */
+
   /* Create reg_map to hold substitutions for replaceable giv regs.  */
   reg_map = (rtx *) alloca (max_reg_before_loop * sizeof (rtx));
   bzero ((char *) reg_map, max_reg_before_loop * sizeof (rtx));
@@ -4247,6 +4356,14 @@ strength_reduce (scan_start, end, loop_top, insn_count,
   if (flag_unroll_loops)
     unroll_loop (loop_end, insn_count, loop_start, end_insert_before, 1);
 
+#ifdef HAIFA
+  /* instrument the loop with bct insn */
+#ifdef HAVE_decrement_and_branch_on_count
+  if (HAVE_decrement_and_branch_on_count)
+    insert_bct (loop_start, loop_end);
+#endif
+#endif  /* HAIFA */
+
   if (loop_dump_stream)
     fprintf (loop_dump_stream, "\n");
 }
@@ -6932,3 +7049,638 @@ get_condition_for_loop (x)
   return gen_rtx (swap_condition (GET_CODE (comparison)), VOIDmode,
 		  XEXP (comparison, 1), XEXP (comparison, 0));
 }
+
+#ifdef HAIFA
+/* Analyze a loop in order to instrument it with the use of count register.
+   loop_start and loop_end are the first and last insns of the loop.
+   This function works in cooperation with insert_bct ().
+   loop_can_insert_bct[loop_num] is set according to whether the optimization
+   is applicable to the loop.  When it is applicable, the following variables
+   are also set:
+    loop_start_value[loop_num]
+    loop_comparison_value[loop_num]
+    loop_increment[loop_num]
+    loop_comparison_code[loop_num] */
+
+static
+void analyze_loop_iterations (loop_start, loop_end)
+  rtx loop_start, loop_end;
+{
+  rtx comparison, comparison_value;
+  rtx iteration_var, initial_value, increment;
+  enum rtx_code comparison_code;
+
+  rtx last_loop_insn;
+  rtx insn;
+  int i;
+
+  /* loop_variable mode */
+  enum machine_mode original_mode;
+
+  /* find the number of the loop */
+  int loop_num = loop_number (loop_start, loop_end);
+
+  /* we change our mind only when we are sure that loop will be instrumented */
+  loop_can_insert_bct[loop_num] = 0;
+
+  /* debugging: do we wish to instrument this loop? */
+  if ( !check_bct_param () )
+    return;
+
+  /* is the optimization suppressed.  */
+  if ( !flag_branch_on_count_reg )
+    return;
+
+  /* make sure that count-reg is not in use */
+  if (loop_used_count_register[loop_num]){
+    if (loop_dump_stream)
+      fprintf (loop_dump_stream,
+	      "analyze_loop_iterations %d: BCT instrumentation failed: count register already in use\n",
+	      loop_num);
+    return;
+  }
+
+  /* make sure that the function has no indirect jumps.  */
+  if (indirect_jump_in_function){
+    if (loop_dump_stream)
+      fprintf (loop_dump_stream,
+              "analyze_loop_iterations %d: BCT instrumentation failed: indirect jump in function\n",
+	      loop_num);
+    return;
+  }
+
+  /* make sure that the last loop insn is a conditional jump */
+  last_loop_insn = PREV_INSN (loop_end);
+  if (!is_conditional_branch (last_loop_insn)) {
+    if (loop_dump_stream)
+      fprintf (loop_dump_stream,
+              "analyze_loop_iterations %d: BCT instrumentation failed: invalid jump at loop end\n",
+	      loop_num);
+    return;
+  }
+
+  /* First find the iteration variable.  If the last insn is a conditional
+     branch, and the insn preceding it tests a register value, make that
+     register the iteration variable.  */
+
+  /* We used to use prev_nonnote_insn here, but that fails because it might
+     accidentally get the branch for a contained loop if the branch for this
+     loop was deleted.  We can only trust branches immediately before the
+     loop_end.  */
+
+  comparison = get_condition_for_loop (last_loop_insn);
+  /* ??? Get_condition may switch position of induction variable and
+     invariant register when it canonicalizes the comparison.  */
+
+  if (comparison == 0) {
+    if (loop_dump_stream)
+      fprintf (loop_dump_stream,
+	      "analyze_loop_iterations %d: BCT instrumentation failed: comparison not found\n",
+	      loop_num);
+    return;
+  }
+
+  comparison_code = GET_CODE (comparison);
+  iteration_var = XEXP (comparison, 0);
+  comparison_value = XEXP (comparison, 1);
+
+  original_mode = GET_MODE (iteration_var);
+  if (GET_MODE_CLASS (original_mode) != MODE_INT
+      || GET_MODE_SIZE (original_mode) != UNITS_PER_WORD) {
+    if (loop_dump_stream)
+      fprintf (loop_dump_stream,
+	      "analyze_loop_iterations %d: BCT Instrumentation failed: loop variable not integer\n",
+	      loop_num);
+    return;
+  }
+
+  /* get info about loop bounds and increment */
+  iteration_info (iteration_var, &initial_value, &increment,
+		  loop_start, loop_end);
+
+  /* make sure that all required loop data were found */
+  if (!(initial_value && increment && comparison_value
+	&& invariant_p (comparison_value) && invariant_p (increment)
+	&& ! indirect_jump_in_function))
+    {
+      if (loop_dump_stream) {
+	fprintf (loop_dump_stream,
+                "analyze_loop_iterations %d: BCT instrumentation failed because of wrong loop: ", loop_num);
+	if (!(initial_value && increment && comparison_value)) {
+	  fprintf (loop_dump_stream, "\tbounds not available: ");
+	  if ( ! initial_value )
+	    fprintf (loop_dump_stream, "initial ");
+	  if ( ! increment )
+	    fprintf (loop_dump_stream, "increment ");
+	  if ( ! comparison_value )
+	    fprintf (loop_dump_stream, "comparison ");
+	  fprintf (loop_dump_stream, "\n");
+	}
+	if (!invariant_p (comparison_value) || !invariant_p (increment))
+	  fprintf (loop_dump_stream, "\tloop bounds not invariant\n");
+      }
+      return;
+    }
+
+  /* make sure that the increment is constant */
+  if (GET_CODE (increment) != CONST_INT) {
+    if (loop_dump_stream)
+      fprintf (loop_dump_stream,
+              "analyze_loop_iterations %d: instrumentation failed: not arithmetic loop\n",
+	      loop_num);
+    return;
+  }
+
+  /* make sure that the loop contains neither function call, nor jump on table.
+     (the count register might be altered by the called function, and might
+     be used for a branch on table).  */
+  for (insn = loop_start; insn && insn != loop_end; insn = NEXT_INSN (insn)) {
+    if (GET_CODE (insn) == CALL_INSN){
+      if (loop_dump_stream)
+	fprintf (loop_dump_stream,
+                "analyze_loop_iterations %d: BCT instrumentation failed: function call in the loop\n",
+		loop_num);
+      return;
+    }
+
+    if (GET_CODE (insn) == JUMP_INSN
+       && (GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC
+	   || GET_CODE (PATTERN (insn)) == ADDR_VEC)){
+      if (loop_dump_stream)
+	fprintf (loop_dump_stream,
+                "analyze_loop_iterations %d: BCT instrumentation failed: computed branch in the loop\n",
+		loop_num);
+      return;
+    }
+  }
+
+  /* At this point, we are sure that the loop can be instrumented with BCT.
+     Some of the loops, however, will not be instrumented - the final decision
+     is taken by insert_bct () */
+  if (loop_dump_stream)
+    fprintf (loop_dump_stream,
+            "analyze_loop_iterations: loop (luid =%d) can be BCT instrumented.\n",
+	    loop_num);
+
+  /* mark all enclosing loops that they cannot use count register */
+  /* ???: In fact, since insert_bct may decide not to instrument this loop,
+     marking here may prevent instrumenting an enclosing loop that could
+    actually be instrumented.  But since this is rare, it is safer to mark
+    here in case the order of calling  (analyze/insert)_bct would be changed.  */
+  for (i=loop_num; i != -1; i = loop_outer_loop[i])
+    loop_used_count_register[i] = 1;
+
+  /* Set data structures which will be used by the instrumentation phase */
+  loop_start_value[loop_num] = initial_value;
+  loop_comparison_value[loop_num] = comparison_value;
+  loop_increment[loop_num] = increment;
+  loop_comparison_code[loop_num] = comparison_code;
+  loop_can_insert_bct[loop_num] = 1;
+}
+
+
+/* instrument loop for insertion of bct instruction.  We distinguish between
+ loops with compile-time bounds, to those with run-time bounds.  The loop
+ behaviour is analized according to the following characteristics/variables:
+ ; Input variables:
+ ;   comparison-value: the value to which the iteration counter is compared.
+ ;   initial-value: iteration-counter initial value.
+ ;   increment: iteration-counter increment.
+ ; Computed variables:
+ ;   increment-direction: the sign of the increment.
+ ;   compare-direction: '1' for GT, GTE, '-1' for LT, LTE, '0' for NE.
+ ;   range-direction: sign (comparison-value - initial-value)
+ We give up on the following cases:
+ ; loop variable overflow.
+ ; run-time loop bounds with comparison code NE.
+ */
+
+static void
+insert_bct (loop_start, loop_end)
+     rtx loop_start, loop_end;
+{
+  rtx initial_value, comparison_value, increment;
+  enum rtx_code comparison_code;
+
+  int increment_direction, compare_direction;
+  int unsigned_p = 0;
+
+  /* if the loop condition is <= or >=, the number of iteration
+      is 1 more than the range of the bounds of the loop */
+  int add_iteration = 0;
+
+  /* the only machine mode we work with - is the integer of the size that the
+     machine has */
+  enum machine_mode loop_var_mode = SImode;
+
+  int loop_num = loop_number (loop_start, loop_end);
+
+  /* get loop-variables. No need to check that these are valid - already
+     checked in analyze_loop_iterations ().  */
+  comparison_code = loop_comparison_code[loop_num];
+  initial_value = loop_start_value[loop_num];
+  comparison_value = loop_comparison_value[loop_num];
+  increment = loop_increment[loop_num];
+
+  /* check analyze_loop_iterations decision for this loop.  */
+  if (! loop_can_insert_bct[loop_num]){
+    if (loop_dump_stream)
+      fprintf (loop_dump_stream,
+	      "insert_bct: [%d] - was decided not to instrument by analyze_loop_iterations ()\n",
+	      loop_num);
+    return;
+  }
+
+  /* make sure that the loop was not fully unrolled.  */
+  if (loop_unroll_factor[loop_num] == -1){
+    if (loop_dump_stream)
+      fprintf (loop_dump_stream, "insert_bct %d: was completely unrolled\n", loop_num);
+    return;
+  }
+
+  /* make sure that the last loop insn is a conditional jump .
+     This check is repeated from analyze_loop_iterations (),
+     because unrolling might have changed that.  */
+  if (!is_conditional_branch (PREV_INSN (loop_end))){
+    if (loop_dump_stream)
+      fprintf (loop_dump_stream,
+	      "insert_bct: not instrumenting BCT because of invalid branch\n");
+    return;
+  }
+
+  /* fix increment in case loop was unrolled.  */
+  if (loop_unroll_factor[loop_num] > 1)
+    increment = GEN_INT ( INTVAL (increment) * loop_unroll_factor[loop_num] );
+
+  /* determine properties and directions of the loop */
+  increment_direction = (INTVAL (increment) > 0) ? 1:-1;
+  switch ( comparison_code ) {
+  case LEU:
+    unsigned_p = 1;
+    /* fallthrough */
+  case LE:
+    compare_direction = 1;
+    add_iteration = 1;
+    break;
+  case GEU:
+    unsigned_p = 1;
+    /* fallthrough */
+  case GE:
+    compare_direction = -1;
+    add_iteration = 1;
+    break;
+  case EQ:
+    /* in this case we cannot know the number of iterations */
+    if (loop_dump_stream)
+      fprintf (loop_dump_stream,
+              "insert_bct: %d: loop cannot be instrumented: == in condition\n",
+	      loop_num);
+    return;
+  case LTU:
+    unsigned_p = 1;
+    /* fallthrough */
+  case LT:
+    compare_direction = 1;
+    break;
+  case GTU:
+    unsigned_p = 1;
+    /* fallthrough */
+  case GT:
+    compare_direction = -1;
+    break;
+  case NE:
+    compare_direction = 0;
+    break;
+  default:
+    abort ();
+  }
+
+
+  /* make sure that the loop does not end by an overflow */
+  if (compare_direction != increment_direction) {
+    if (loop_dump_stream)
+      fprintf (loop_dump_stream,
+              "insert_bct: %d: loop cannot be instrumented: terminated by overflow\n",
+	      loop_num);
+    return;
+  }
+
+  /* try to instrument the loop.  */
+
+  /* Handle the simpler case, where the bounds are known at compile time.  */
+  if (GET_CODE (initial_value) == CONST_INT && GET_CODE (comparison_value) == CONST_INT)
+    {
+      int n_iterations;
+      int increment_value_abs = INTVAL (increment) * increment_direction;
+
+      /* check the relation between compare-val and initial-val */
+      int difference = INTVAL (comparison_value) - INTVAL (initial_value);
+      int range_direction = (difference > 0) ? 1 : -1;
+
+      /* make sure the loop executes enough iterations to gain from BCT */
+      if (difference > -3 && difference < 3) {
+	if (loop_dump_stream)
+	  fprintf (loop_dump_stream,
+		  "insert_bct: loop %d not BCT instrumented: too small iteration count.\n",
+		  loop_num);
+	return;
+      }
+
+      /* make sure that the loop executes at least once */
+      if ((range_direction ==  1 && compare_direction == -1)
+	  || (range_direction == -1 && compare_direction ==  1))
+	{
+	  if (loop_dump_stream)
+	    fprintf (loop_dump_stream,
+		    "insert_bct: loop %d: does not iterate even once. Not instrumenting.\n",
+		    loop_num);
+	  return;
+	}
+
+      /* make sure that the loop does not end by an overflow (in compile time
+         bounds we must have an additional check for overflow, because here
+         we also support the compare code of 'NE'.  */
+      if (comparison_code == NE
+	  && increment_direction != range_direction) {
+	if (loop_dump_stream)
+	  fprintf (loop_dump_stream,
+		  "insert_bct (compile time bounds): %d: loop not instrumented: terminated by overflow\n",
+		  loop_num);
+	return;
+      }
+
+      /* Determine the number of iterations by:
+	 ;
+         ;                  compare-val - initial-val + (increment -1) + additional-iteration
+         ; num_iterations = -----------------------------------------------------------------
+         ;                                           increment
+	 */
+      difference = (range_direction > 0) ? difference : -difference;
+#if 0
+      fprintf (stderr, "difference is: %d\n", difference); /* @*/
+      fprintf (stderr, "increment_value_abs is: %d\n", increment_value_abs); /* @*/
+      fprintf (stderr, "add_iteration is: %d\n", add_iteration); /* @*/
+      fprintf (stderr, "INTVAL (comparison_value) is: %d\n", INTVAL (comparison_value)); /* @*/
+      fprintf (stderr, "INTVAL (initial_value) is: %d\n", INTVAL (initial_value)); /* @*/
+#endif
+
+      if (increment_value_abs == 0) {
+	fprintf (stderr, "insert_bct: error: increment == 0 !!!\n");
+	abort ();
+      }
+      n_iterations = (difference + increment_value_abs - 1 + add_iteration)
+	/ increment_value_abs;
+
+#if 0
+      fprintf (stderr, "number of iterations is: %d\n", n_iterations); /* @*/
+#endif
+      instrument_loop_bct (loop_start, loop_end, GEN_INT (n_iterations));
+
+      /* Done with this loop.  */
+      return;
+    }
+
+  /* Handle the more complex case, that the bounds are NOT known at compile time.  */
+  /* In this case we generate run_time calculation of the number of iterations */
+
+  /* With runtime bounds, if the compare is of the form '!=' we give up */
+  if (comparison_code == NE) {
+    if (loop_dump_stream)
+      fprintf (loop_dump_stream,
+	      "insert_bct: fail for loop %d: runtime bounds with != comparison\n",
+	      loop_num);
+    return;
+  }
+
+  else {
+    /* We rely on the existence of run-time guard to ensure that the
+       loop executes at least once.  */
+    rtx sequence;
+    rtx iterations_num_reg;
+
+    int increment_value_abs = INTVAL (increment) * increment_direction;
+
+    /* make sure that the increment is a power of two, otherwise (an
+       expensive) divide is needed.  */
+    if ( !is_power_of_2(increment_value_abs) )
+      {
+	if (loop_dump_stream)
+	  fprintf (loop_dump_stream,
+		  "insert_bct: not instrumenting BCT because the increment is not power of 2\n");
+	return;
+      }
+
+    /* compute the number of iterations */
+    start_sequence ();
+    {
+      /* CYGNUS LOCAL: HAIFA bug fix */
+      rtx temp_reg;
+
+      /* Again, the number of iterations is calculated by:
+	 ;
+         ;                  compare-val - initial-val + (increment -1) + additional-iteration
+         ; num_iterations = -----------------------------------------------------------------
+         ;                                           increment
+	 */
+      /* ??? Do we have to call copy_rtx here before passing rtx to
+	 expand_binop?  */
+      if (compare_direction > 0) {
+	/* <, <= :the loop variable is increasing */
+	temp_reg = expand_binop (loop_var_mode, sub_optab, comparison_value,
+				 initial_value, NULL_RTX, 0, OPTAB_LIB_WIDEN);
+      }
+      else {
+	temp_reg = expand_binop (loop_var_mode, sub_optab, initial_value,
+				 comparison_value, NULL_RTX, 0, OPTAB_LIB_WIDEN);
+      }
+
+      if (increment_value_abs - 1 + add_iteration != 0)
+	temp_reg = expand_binop (loop_var_mode, add_optab, temp_reg,
+				 GEN_INT (increment_value_abs - 1 + add_iteration),
+				 NULL_RTX, 0, OPTAB_LIB_WIDEN);
+
+      if (increment_value_abs != 1)
+	{
+	  /* ??? This will generate an expensive divide instruction for
+	     most targets.  The original authors apparently expected this
+	     to be a shift, since they test for power-of-2 divisors above,
+	     but just naively generating a divide instruction will not give 
+	     a shift.  It happens to work for the PowerPC target because
+	     the rs6000.md file has a divide pattern that emits shifts.
+	     It will probably not work for any other target.  */
+	  iterations_num_reg = expand_binop (loop_var_mode, sdiv_optab,
+					     temp_reg,
+					     GEN_INT (increment_value_abs),
+					     NULL_RTX, 0, OPTAB_LIB_WIDEN);
+	}
+      else
+	iterations_num_reg = temp_reg;
+      /* END CYGNUS LOCAL: HAIFA bug fix */
+    }
+    sequence = gen_sequence ();
+    end_sequence ();
+    emit_insn_before (sequence, loop_start);
+    instrument_loop_bct (loop_start, loop_end, iterations_num_reg);
+  }
+}
+
+/* instrument loop by inserting a bct in it. This is done in the following way:
+   1. A new register is created and assigned the hard register number of the count
+    register.
+   2. In the head of the loop the new variable is initialized by the value passed in the
+    loop_num_iterations parameter.
+   3. At the end of the loop, comparison of the register with 0 is generated.
+    The created comparison follows the pattern defined for the
+    decrement_and_branch_on_count insn, so this insn will be generated in assembly
+    generation phase.
+   4. The compare&branch on the old variable is deleted. So, if the loop-variable was
+    not used elsewhere, it will be eliminated by data-flow analisys.  */
+
+static void
+instrument_loop_bct (loop_start, loop_end, loop_num_iterations)
+     rtx loop_start, loop_end;
+     rtx loop_num_iterations;
+{
+  rtx temp_reg1, temp_reg2;
+  rtx start_label;
+
+  rtx sequence;
+  enum machine_mode loop_var_mode = SImode;
+
+#ifdef HAVE_decrement_and_branch_on_count
+  if (HAVE_decrement_and_branch_on_count)
+    {
+      if (loop_dump_stream)
+	fprintf (loop_dump_stream, "Loop: Inserting BCT\n");
+
+      /* eliminate the check on the old variable */
+      delete_insn (PREV_INSN (loop_end));
+      delete_insn (PREV_INSN (loop_end));
+
+      /* insert the label which will delimit the start of the loop */
+      start_label = gen_label_rtx ();
+      emit_label_after (start_label, loop_start);
+
+      /* insert initialization of the count register into the loop header */
+      start_sequence ();
+      temp_reg1 = gen_reg_rtx (loop_var_mode);
+      emit_insn (gen_move_insn (temp_reg1, loop_num_iterations));
+
+      /* this will be count register */
+      temp_reg2 = gen_rtx (REG, loop_var_mode, COUNT_REGISTER_REGNUM);
+      /* we have to move the value to the count register from an GPR
+	 because rtx pointed to by loop_num_iterations could contain
+	 expression which cannot be moved into count register */
+      emit_insn (gen_move_insn (temp_reg2, temp_reg1));
+
+      sequence = gen_sequence ();
+      end_sequence ();
+      emit_insn_after (sequence, loop_start);
+
+      /* insert new comparison on the count register instead of the
+	 old one, generating the needed BCT pattern (that will be
+	 later recognized by assembly generation phase).  */
+      emit_jump_insn_before (gen_decrement_and_branch_on_count (temp_reg2, start_label),
+			     loop_end);
+      LABEL_NUSES (start_label)++;
+    }
+
+#endif /* HAVE_decrement_and_branch_on_count */
+}
+
+/* calculate the uid of the given loop */
+int
+loop_number (loop_start, loop_end)
+     rtx loop_start, loop_end;
+{
+  int loop_num = -1;
+
+  /* assume that this insn contains the LOOP_START
+     note, so it will not be changed by the loop unrolling */
+  loop_num = uid_loop_num[INSN_UID (loop_start)];
+  /* sanity check - should never happen */
+  if (loop_num == -1)
+    abort ();
+
+  return loop_num;
+}
+
+/* scan the function and determine whether it has indirect (computed) jump */
+static int
+indirect_jump_in_function_p (start)
+     rtx start;
+{
+  rtx insn;
+  int is_indirect_jump = 0;
+
+  for (insn = start; insn; insn = NEXT_INSN (insn)) {
+    if (GET_CODE (insn) == JUMP_INSN) {
+      if (GET_CODE (PATTERN (insn)) == SET) {
+	rtx insn_work_code = XEXP (PATTERN (insn), 1);
+
+	if (GET_CODE (insn_work_code) == LABEL_REF)
+	  continue;
+	if (GET_CODE (insn_work_code) == IF_THEN_ELSE) {
+	  rtx jump_target = XEXP (insn_work_code, 1);
+
+	  if (jump_target == pc_rtx
+	     || (GET_CODE (jump_target) == (enum rtx_code)LABEL_REF))
+	    continue;
+	}
+      }
+      is_indirect_jump = 1;
+    }
+  }
+  return is_indirect_jump;
+}
+
+/* return 1 iff n is a power of 2 */
+static int
+is_power_of_2(n)
+     int n;
+{
+  return (n & (n-1)) == 0;
+}
+
+/* return 1 iff insn is a conditional jump */
+is_conditional_branch (insn)
+     rtx insn;
+{
+  rtx work_code;
+  if (GET_CODE (insn) != JUMP_INSN)
+    return 0;
+  work_code = PATTERN (insn);
+  if (GET_CODE (work_code) != SET)
+    return 0;
+  if (GET_CODE (XEXP (work_code, 1)) != IF_THEN_ELSE)
+    return 0;
+  return 1;
+}
+
+/* debugging: fix_bct_param () is called from toplev.c upon detection
+   of the -fbct-***-N options.  */
+int
+fix_bct_param (param, val)
+     char *param, *val;
+{
+  if ( !strcmp (param, "max") )
+    dbg_bct_max = atoi (val);
+  else if ( !strcmp (param, "min") )
+    dbg_bct_min = atoi (val);
+}
+
+/* debugging: return 1 if the loop should be instrumented,
+   according to bct-min/max.  */
+static int
+check_bct_param ()
+{
+  static int dbg_bct_num = 0;
+
+  dbg_bct_num++;
+  if (dbg_bct_num > dbg_bct_min || dbg_bct_min == -1)
+    if (dbg_bct_num <= dbg_bct_max || dbg_bct_max == -1)
+      return 1;
+  return 0;
+}
+#endif	/* HAIFA */
+/* END CYGNUS LOCAL haifa */