[lno] [patch] if-then guards for unknown loop bound

[lno] [patch] if-then guards for unknown loop bound

[Olga Golovanevsky]

[-- Attachment #1: Type: text/plain, Size: 851 bytes --]

This patch adds two if-then guards to implementation of
unknown loop bound for vectorizer.

First if-then statement prevents entering the loop to be vectorized
in case the number of iteration loop executes is less then vectorization
factor.
Second if-then statement skips the scalar (epilog) loop in case
the number of iteration it executes is divisible by vectorization factor.


ChangeLog

             * tree-vectorizer.c (vect_generate_tmps_on_preheader):
             (vect_gen_if_guard): New functions.
             (vect_update_initial_conditions_of_duplicated_loop):
             Update also phis of bb at the exit of epilog loop.
             (vect_transform_loop): Remove code that now belongs to
             vect_generate_tmps_on_preheader () function. Use
             vect_gen_if_guard function twice.

(See attached file: diffJ11_2.txt)

[-- Attachment #2: diffJ11_2.txt --]
[-- Type: text/plain, Size: 18896 bytes --]

Index: tree-vectorizer.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-vectorizer.c,v
retrieving revision 1.1.2.36
diff -c -3 -p -r1.1.2.36 tree-vectorizer.c
*** tree-vectorizer.c	10 Jun 2004 06:57:04 -0000	1.1.2.36
--- tree-vectorizer.c	11 Jun 2004 13:17:03 -0000
*************** static tree get_vectype_for_scalar_type 
*** 204,213 ****
  static tree vect_get_new_vect_var (tree, enum vect_var_kind, const char *);
  static tree vect_get_vec_def_for_operand (tree, tree);
  static tree vect_init_vector (tree, tree);
  
  /* Utility functions for loop duplication.  */
  static basic_block vect_tree_split_edge (edge);
! static void vect_update_initial_conditions_of_duplicated_loop (loop_vec_info, tree);
  
  /* General utility functions (CHECKME: where do they belong).  */
  static tree get_array_base (tree);
--- 204,216 ----
  static tree vect_get_new_vect_var (tree, enum vect_var_kind, const char *);
  static tree vect_get_vec_def_for_operand (tree, tree);
  static tree vect_init_vector (tree, tree);
+ static tree vect_build_symbl_bound (tree n, int vf, struct loop * loop);
+ static basic_block vect_gen_if_guard (edge, tree, basic_block, edge);
  
  /* Utility functions for loop duplication.  */
  static basic_block vect_tree_split_edge (edge);
! static void vect_update_initial_conditions_of_duplicated_loop (loop_vec_info, 
! 						   tree, basic_block, edge, edge);
  
  /* General utility functions (CHECKME: where do they belong).  */
  static tree get_array_base (tree);
*************** vect_transform_stmt (tree stmt, block_st
*** 1282,1287 ****
--- 1285,1483 ----
    return is_store;
  }
  
+ /* This function generate the following statements:
+ 
+  ni_name = number of iterations loop executes
+  ratio = ni_name / vf
+  ratio_mult_vf_name = ratio * vf
+ 
+  and locate them at the loop preheder edge.  */
+ 
+ static void 
+ vect_generate_tmps_on_preheader (loop_vec_info loop_vinfo, tree *ni_name_p,
+ 				 tree *ratio_mult_vf_name_p, tree *ratio_p)
+ {
+ 
+   edge pe;
+   basic_block new_bb;
+   tree stmt, var, ni, ni_name;
+   tree ratio;
+   tree ratio_mult_vf_name, ratio_mult_vf;
+   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
+   
+   int vf, i = -1;
+ 
+   /* Generate temporary variable that contains 
+      number of iterations loop executes.  */
+ 
+   ni = LOOP_VINFO_SYMB_NUM_OF_ITERS(loop_vinfo);
+   var = create_tmp_var (TREE_TYPE (ni), "niters");
+   add_referenced_tmp_var (var);
+ 
+   ni_name = force_gimple_operand (ni, &stmt, false, var);
+   pe = loop_preheader_edge (loop);
+   new_bb = bsi_insert_on_edge_immediate (pe, stmt);
+   if (new_bb)
+     add_bb_to_loop (new_bb, new_bb->pred->src->loop_father);
+       
+   /* ratio = ni / vf  */
+ 
+   vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
+   ratio = vect_build_symbl_bound (ni_name, vf, loop);
+        
+   /* Update initial conditions of loop copy.  */
+        
+   /* ratio_mult_vf = ration * vf;  */
+ 
+   /* vf is power of 2; thus if vf = 2^k, then n/vf = n >> k.   */
+   while (vf)
+     {
+       vf = vf >> 1;
+       i++;
+     }
+ 
+   ratio_mult_vf = create_tmp_var (TREE_TYPE (ni), "ratio_mult_vf");
+   add_referenced_tmp_var (ratio_mult_vf);
+ 
+   ratio_mult_vf_name = make_ssa_name (ratio_mult_vf, NULL_TREE);
+ 
+   stmt = build (MODIFY_EXPR, void_type_node, ratio_mult_vf_name,
+ 		build (LSHIFT_EXPR, TREE_TYPE (ratio),
+ 		       ratio, build_int_2(i,0)));
+ 
+   SSA_NAME_DEF_STMT (ratio_mult_vf_name) = stmt;
+ 
+   pe = loop_preheader_edge (loop);
+   new_bb = bsi_insert_on_edge_immediate (pe, stmt);
+   if (new_bb)
+     add_bb_to_loop (new_bb, new_bb->pred->src->loop_father);
+ 
+   *ni_name_p = ni_name;
+   *ratio_mult_vf_name_p = ratio_mult_vf_name;
+   *ratio_p = ratio;
+     
+   return;  
+ }
+ 
+ /* This function:
+         
+         1. splits EE edge generating new bb
+ 	2. locates the following statement as last statement of new bb:
+ 
+ 	    if ( COND ) 
+ 	      goto EXIT_BB.
+ 	    else 
+ 	      goto EE->dest (as it was before split).
+ 	
+ 	3. updates phis of EXIT_BB with 
+ 	   values comming from false edge
+ 
+    The function also updates phis of EXIT_BB. 
+    
+    We suppose that  E->dest == EXIT_BB and 
+    that EE is preheader edge of loop.  */
+ 
+ 
+ static basic_block 
+ vect_gen_if_guard (edge ee, tree cond, basic_block exit_bb, edge e)
+ {
+   tree cond_expr;
+   tree then_clause,else_clause;
+   basic_block new_bb; 
+   edge true_edge, false_edge;
+   tree phi, phi1;
+   basic_block header_of_loop;
+   int num_elem1, num_elem2;
+   edge e0;
+ 
+   block_stmt_iterator interm_bb_last_bsi;
+ 
+   new_bb = vect_tree_split_edge (ee); 
+   if(!new_bb)
+     {
+       if (dump_file && (dump_flags & TDF_DETAILS))
+ 	{
+ 	  fprintf (dump_file, "\nFailed to generate new_bb.\n");
+ 	}
+       abort ();
+     }
+ 
+  
+   header_of_loop = new_bb->succ->dest;
+ 
+   then_clause = build1 (GOTO_EXPR, void_type_node, tree_block_label (exit_bb));
+   else_clause = build1 (GOTO_EXPR, void_type_node, 
+ 			tree_block_label (header_of_loop)); 
+   cond_expr = build (COND_EXPR, void_type_node, cond, then_clause, else_clause);
+ 
+   /* Insert condition as a last statement in new bb. */
+   interm_bb_last_bsi = bsi_last (new_bb);
+   bsi_insert_after (&interm_bb_last_bsi, cond_expr, BSI_NEW_STMT);   
+ 
+   /* Remember old edge to update phis.  */
+   e0 = new_bb->succ;
+ 
+   /* Remove edge from new bb to header of loop.  */  
+   remove_edge (e0); 
+ 
+   /* Generate new edges according to condition.  */
+   true_edge = make_edge (new_bb, exit_bb, EDGE_TRUE_VALUE);
+   set_immediate_dominator (CDI_DOMINATORS, exit_bb, new_bb);
+   false_edge = make_edge (new_bb, header_of_loop, EDGE_FALSE_VALUE);
+   set_immediate_dominator (CDI_DOMINATORS, header_of_loop, new_bb);
+ 
+   /* Update phis in loop header as coming from false edge.  */
+   for (phi = phi_nodes (header_of_loop); phi; phi = TREE_CHAIN (phi))
+     {
+       int i;
+       num_elem1 = PHI_NUM_ARGS (phi);
+       for (i = 0; i < num_elem1; i++)
+ 	if (PHI_ARG_EDGE (phi, i) == e0)
+ 	  {
+ 	    PHI_ARG_EDGE (phi, i) = false_edge;
+ 	    break;
+ 	  }
+     }
+ 
+   /* Update phis of exit bb as coming from true_edge.  */
+   for (phi = phi_nodes (exit_bb); phi; phi = TREE_CHAIN (phi))
+     {
+       int i;
+       num_elem1 = PHI_NUM_ARGS (phi);
+       for (i = 0; i < num_elem1; i++)
+ 	{
+ 	  if (PHI_ARG_EDGE (phi, i) == e)
+ 	    {
+ 	      tree def = PHI_ARG_DEF (phi, i);
+ 	      for (phi1 = phi_nodes (header_of_loop); phi1; phi1 = TREE_CHAIN (phi1))
+ 		{
+ 		  int k;
+ 		  num_elem2 = PHI_NUM_ARGS (phi1);
+ 		  for (k = 0; k < num_elem2; k++)
+ 		    {
+ 		      if (PHI_ARG_DEF (phi1, k) == def)
+ 			{
+ 			  int j;
+ 			  for (j = 0; j < num_elem2; j++)
+ 			    {
+ 			      if (PHI_ARG_EDGE (phi1, j) == false_edge)
+ 				{
+ 				  tree def1 = PHI_ARG_DEF (phi1, j);
+ 				  add_phi_arg (&phi, def1, true_edge);
+ 				  break;
+ 				}
+ 			    }
+ 			  break;
+ 			}
+ 		    }
+ 		}		
+ 	    }
+ 	}
+     }  
+ 
+   return new_bb;
+ }
+ 
  /* This function generates stmt 
     
     tmp = n / vf;
*************** vect_build_symbl_bound (tree n, int vf, 
*** 1335,1356 ****
     When loop is vectorized, its IVs not always preserved so 
     that to be used for initialization of loop copy (second loop). 
     Here we use access functions of IVs and number of iteration 
!    loop executes in order to bring IVs to correct position.  */
  
  static void 
  vect_update_initial_conditions_of_duplicated_loop (loop_vec_info loop_vinfo, 
! 						   tree niters)
  {
    struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo); 
    /* Preheader edge of duplicated loop.  */
    edge pe;
    edge latch = loop_latch_edge (loop);
-   basic_block dloop_header;
    tree phi;
    
-   pe = loop->exit_edges[0]->dest->succ;
-   dloop_header = pe->dest;
- 
    for (phi = phi_nodes (loop->header); phi; phi = TREE_CHAIN (phi))
      {
        tree access_fn = NULL;
--- 1531,1562 ----
     When loop is vectorized, its IVs not always preserved so 
     that to be used for initialization of loop copy (second loop). 
     Here we use access functions of IVs and number of iteration 
!    loop executes in order to bring IVs to correct position.  
! 
!    Function also update phis of epilog loop header and NEW_LOOP_EXIT->dest.  */
  
  static void 
  vect_update_initial_conditions_of_duplicated_loop (loop_vec_info loop_vinfo, 
! 						   tree niters, 
! 						   basic_block new_loop_header,
! 						   edge new_loop_latch, 
! 						   edge new_loop_exit)
  {
    struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo); 
    /* Preheader edge of duplicated loop.  */
    edge pe;
    edge latch = loop_latch_edge (loop);
    tree phi;
+   block_stmt_iterator interm_bb_last_bsi;
+   basic_block intermediate_bb = loop->exit_edges[0]->dest;
+   edge inter_bb_true_edge;
+   basic_block exit_bb;
+ 
+   /* Find edge from intermediate bb to new loop header.  */
+   pe = find_edge (loop->exit_edges[0]->dest, new_loop_header);
+   inter_bb_true_edge = find_edge (intermediate_bb, new_loop_exit->dest);
+   exit_bb = new_loop_exit->dest;
    
    for (phi = phi_nodes (loop->header); phi; phi = TREE_CHAIN (phi))
      {
        tree access_fn = NULL;
*************** vect_update_initial_conditions_of_duplic
*** 1358,1366 ****
        tree init_expr;
        tree step_expr;
        tree var, stmt, ni, ni_name;
!       basic_block new_bb;
!       int i, num_elem1, num_elem2;
!       tree phi1;
  
  
        /* Skip virtual phi's. The data dependences that are associated with
--- 1564,1571 ----
        tree init_expr;
        tree step_expr;
        tree var, stmt, ni, ni_name;
!       int i, j, k, m, num_elem1, num_elem2, num_elem3;
!       tree phi1, phi2;
  
  
        /* Skip virtual phi's. The data dependences that are associated with
*************** vect_update_initial_conditions_of_duplic
*** 1394,1404 ****
        add_referenced_tmp_var (var);
  
        ni_name = force_gimple_operand (ni, &stmt, false, var);
!       new_bb = bsi_insert_on_edge_immediate (pe, stmt);
! 
!       /* We should not generate new bb here, only use already existing one.  */
!       if (new_bb)
! 	abort ();            
  
        /* Fix phi expressions in duplicated loop.   */
        num_elem1 = PHI_NUM_ARGS (phi);
--- 1599,1608 ----
        add_referenced_tmp_var (var);
  
        ni_name = force_gimple_operand (ni, &stmt, false, var);
!       
!       /* Insert stmt into intermediate bb before condition.  */
!       interm_bb_last_bsi = bsi_last (intermediate_bb);
!       bsi_insert_before (&interm_bb_last_bsi, stmt, BSI_NEW_STMT);   
  
        /* Fix phi expressions in duplicated loop.   */
        num_elem1 = PHI_NUM_ARGS (phi);
*************** vect_update_initial_conditions_of_duplic
*** 1408,1421 ****
  	    tree def;
  	    
  	    def = PHI_ARG_DEF (phi, i);
! 	    for (phi1 = phi_nodes (dloop_header); phi1; phi1 = TREE_CHAIN (phi1))
  	      {
  		num_elem2 = PHI_NUM_ARGS (phi1);
! 		for (i = 0; i < num_elem2; i++)
  		  if (PHI_ARG_DEF (phi1, i) == def)
  		    {
! 		      PHI_ARG_DEF (phi1, i) = ni_name;
! 		      PHI_ARG_EDGE (phi1, i) = pe;
  		      break;
   		    }		    
  	      }
--- 1612,1645 ----
  	    tree def;
  	    
  	    def = PHI_ARG_DEF (phi, i);
! 	    for (phi1 = phi_nodes (new_loop_header); phi1; phi1 = TREE_CHAIN (phi1))
  	      {
  		num_elem2 = PHI_NUM_ARGS (phi1);
! 		for (j = 0; j < num_elem2; j++)
  		  if (PHI_ARG_DEF (phi1, i) == def)
  		    {
! 		      for (k = 0; k < num_elem2; k++)
! 			if (PHI_ARG_EDGE (phi1, k) == new_loop_latch)
! 			  {
! 			    tree def1 = PHI_ARG_DEF (phi1, k);
! 			    for (phi2 = phi_nodes (exit_bb); phi2; phi2 = TREE_CHAIN (phi2))
! 			      {
! 				num_elem3 = PHI_NUM_ARGS (phi2);
! 				for (m = 0; m < num_elem3; m++)
! 				  {
! 				    if (PHI_ARG_DEF (phi2, m) == def1 && 
! 					PHI_ARG_EDGE (phi2, m) == new_loop_exit)
! 				      {
! 					add_phi_arg (&phi2, ni_name, inter_bb_true_edge);
! 					break;
! 				      }
! 				  }
! 			      }
! 			  }
! 
! 		      PHI_ARG_DEF (phi1, j) = ni_name;
! 		      PHI_ARG_EDGE (phi1, j) = pe;
! 		      
  		      break;
   		    }		    
  	      }
*************** vect_transform_loop (loop_vec_info loop_
*** 1560,1566 ****
    int vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
    block_stmt_iterator si;
    int i;
!   tree var = NULL, ratio = NULL;
    
    if (dump_file && (dump_flags & TDF_DETAILS))
      fprintf (dump_file, "\n<<vec_transform_loop>>\n");
--- 1784,1790 ----
    int vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
    block_stmt_iterator si;
    int i;
!   tree ratio = NULL;
    
    if (dump_file && (dump_flags & TDF_DETAILS))
      fprintf (dump_file, "\n<<vec_transform_loop>>\n");
*************** vect_transform_loop (loop_vec_info loop_
*** 1576,1644 ****
         LOOP_VINFO_SYMB_NUM_OF_ITERS (loop_vinfo) != NULL )
      {
  
!       edge ee,pe;
!       basic_block new_bb;
!       tree stmt, ni, ni_name;
!       tree ratio_mult_vf, ratio_mult_vf_name;
!       int vf, i = -1;
  
!       tree_duplicate_loop_to_exit (loop, loops);
  
!       /* FORNOW: Only loops with one exit are handled. */
!       ee = loop->exit_edges[0];
!       new_bb = vect_tree_split_edge(ee);
!       if (new_bb)
! 	loop->exit_edges[0] = new_bb->pred;
!       else
!       if (dump_file && (dump_flags & TDF_DETAILS))
! 	{
! 	  fprintf (dump_file, "\nFailed to generate empty bb after loop.\n");
! 	  abort ();
! 	}
!       /* Generate temporary variable that contains 
!          number of iterations loop executes.  */
!       ni = LOOP_VINFO_SYMB_NUM_OF_ITERS(loop_vinfo);
!       var = create_tmp_var (TREE_TYPE (ni), "niters");
!       add_referenced_tmp_var (var);
  
!       ni_name = force_gimple_operand (ni, &stmt, false, var);
!       pe = loop_preheader_edge (loop);
!       new_bb = bsi_insert_on_edge_immediate (pe, stmt);
!       if (new_bb)
! 	add_bb_to_loop (new_bb, new_bb->pred->src->loop_father);
        
!       /* ratio = ni / vf  */
  
        vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
!       ratio = vect_build_symbl_bound (ni_name, vf, loop);
!        
!       /* Update initial conditions of loop copy.  */
!        
!       /* ratio_mult_vf = ration * vf;  */
  
!       /* vf is power of 2; thus if vf = 2^k, then n/vf = n >> k.   */
!       while (vf)
! 	{
! 	  vf = vf >> 1;
! 	  i++;
! 	}
  
-       ratio_mult_vf = create_tmp_var (TREE_TYPE (ni), "ratio_mult_vf");
-       add_referenced_tmp_var (ratio_mult_vf);
  
!       ratio_mult_vf_name = make_ssa_name (ratio_mult_vf, NULL_TREE);
  
!       stmt = build (MODIFY_EXPR, void_type_node, ratio_mult_vf_name,
! 		build (LSHIFT_EXPR, TREE_TYPE (ratio),
! 		       ratio, build_int_2(i,0)));
  
-       SSA_NAME_DEF_STMT (ratio_mult_vf_name) = stmt;
  
!       new_bb = bsi_insert_on_edge_immediate (pe, stmt);
!       if (new_bb)
! 	add_bb_to_loop (new_bb, new_bb->pred->src->loop_father);
  
!       vect_update_initial_conditions_of_duplicated_loop (loop_vinfo, ratio_mult_vf_name);
      }
  
    /* CHECKME: FORNOW the vectorizer supports only loops which body consist
--- 1800,1889 ----
         LOOP_VINFO_SYMB_NUM_OF_ITERS (loop_vinfo) != NULL )
      {
  
!       basic_block inter_bb, exit_bb, prolog_bb;
!       tree ni_name, ratio_mult_vf_name;
!       basic_block new_loop_header;
!       tree cond;
!       int vf;
!       edge e, exit_ep, phead_epilog, ee;
  
!       /* Remember exit bb before duplication.  */
!       exit_bb = loop->exit_edges[0]->dest;
  
!       /* Duplicate loop. 
! 	 New (epilog) loop is concatenated to the exit of original loop.  */
!       tree_duplicate_loop_to_exit (loop, loops);
  
!       new_loop_header = loop->exit_edges[0]->dest;
        
!       /* Generate the following variables on the preheader of original loop:
! 	 
! 	 ni_name = number of iteration the original loop executes
! 	 ratio = ni_name / vf
! 	 ration_mult_vf_name = ration * vf
!       */
!       vect_generate_tmps_on_preheader (loop_vinfo, &ni_name,
! 				       &ratio_mult_vf_name, &ratio);
! 
!       /* Update loop info.  */
!       loop->pre_header = loop_preheader_edge (loop)->src;
!       loop->pre_header_edges[0] = loop_preheader_edge (loop);
! 
!       /* Build conditional expr before epilog loop.  */
!       cond = build (EQ_EXPR, boolean_type_node, ratio_mult_vf_name, ni_name);
! 
!       /* Find exit edge of epilog loop.  */
!       exit_ep = find_edge (new_loop_header, exit_bb);
! 
!       /* Generate intermediate bb between original loop and epilog loop 
! 	 with guard if statement: 
! 	 
! 	 if ( ni_name == ratio_mult_vf_name ) skip epilog loop.  */
!       inter_bb = vect_gen_if_guard (loop->exit_edges[0], cond, exit_bb, exit_ep);
! 
!       loop->exit_edges[0] = inter_bb->pred;
  
+       /* Build conditional expr before loop to be vectorized.  */
        vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
!       cond = build (LT_EXPR, boolean_type_node, ni_name, build_int_2 (vf,0));
  
!       /* Find preheader edge of epilog loop.  */
!       phead_epilog = find_edge (inter_bb, new_loop_header);
  
  
!       /* Generate new bb before original loop  
! 	 with guard if statement: 
! 	 
! 	 if ( ni_name < vf) goto epilog loop.  */
!       prolog_bb = vect_gen_if_guard (loop->pre_header_edges[0], cond, 
! 				     new_loop_header, phead_epilog);
  
!       loop->pre_header = prolog_bb;
!       
!       /* Find loop preheader edge of original loop.  */
!       loop->pre_header_edges[0] = find_edge (prolog_bb, loop->header);
  
  
!       /* Find true edge of first if stmt.  */
!       for (ee = prolog_bb->succ; ee; ee = ee->succ_next)
! 	if(ee->dest != loop->header)
! 	  break;
  
!       if (!ee)
! 	abort ();
! 
!       /* Find new loop latch edge. */      
!       for (e = new_loop_header->pred; e; e = e->pred_next)
! 	if(e != ee && e != phead_epilog)
! 	  break;
! 
!       if (!e)
! 	abort ();
! 
!       /* Update IVs of original loop as if they were advanced 
! 	 by ratio_mult_vf_name steps. Locate them in intermediate bb befroe if stmt.  */
!       vect_update_initial_conditions_of_duplicated_loop (loop_vinfo, ratio_mult_vf_name, 
! 							 new_loop_header, e, exit_ep);
      }
  
    /* CHECKME: FORNOW the vectorizer supports only loops which body consist