contrib/gcc/tree-if-conv.c

27      o Decide if a loop is if-convertible or not.
28      o Walk all loop basic blocks in breadth first order (BFS order).
106 static tree tree_if_convert_stmt (struct loop *loop, tree, tree,
108 static void tree_if_convert_cond_expr (struct loop *, tree, tree,
110 static bool if_convertible_phi_p (struct loop *, basic_block, tree);
111 static bool if_convertible_modify_expr_p (struct loop *, basic_block, tree);
112 static bool if_convertible_stmt_p (struct loop *, basic_block, tree);
113 static bool if_convertible_bb_p (struct loop *, basic_block, basic_block);
114 static bool if_convertible_loop_p (struct loop *, bool);
116 static tree add_to_dst_predicate_list (struct loop * loop, edge,
119 static void clean_predicate_lists (struct loop *loop);
120 static basic_block find_phi_replacement_condition (struct loop *loop,
125 static void process_phi_nodes (struct loop *);
126 static void combine_blocks (struct loop *);
129 static basic_block * get_loop_body_in_if_conv_order (const struct loop *loop);
130 static bool bb_with_exit_edge_p (struct loop *, basic_block);
137    false. If false is returned then loop remains unchanged.
143 tree_if_conversion (struct loop *loop, bool for_vectorizer)
151   /* if-conversion is not appropriate for all loops. First, check if loop  is
153   if (!if_convertible_loop_p (loop, for_vectorizer))
167   for (i = 0; i < loop->num_nodes; i++)
182 	  cond = tree_if_convert_stmt (loop, t, cond, &itr);
200   combine_blocks (loop);
203   clean_predicate_lists (loop);
215    loop. It is used here when it is required to delete current statement.  */
218 tree_if_convert_stmt (struct loop *  loop, tree t, tree cond,
245       tree_if_convert_cond_expr (loop, t, cond, bsi);
256    Remove COND_EXPR, if it is not the loop exit condition. Otherwise
257    update loop exit condition appropriately.  BSI is the iterator
258    used to traverse statement list. STMT is part of loop LOOP.  */
261 tree_if_convert_cond_expr (struct loop *loop, tree stmt, tree cond,
277   add_to_dst_predicate_list (loop, true_edge, cond,
282   add_to_dst_predicate_list (loop, false_edge, cond, c2, bsi);
287   if (!bb_with_exit_edge_p (loop, bb_for_stmt (stmt)))
295 /* Return true, iff PHI is if-convertible. PHI is part of loop LOOP
302 if_convertible_phi_p (struct loop *loop, basic_block bb, tree phi)
310   if (bb != loop->header && PHI_NUM_ARGS (phi) != 2)
340   MODIFY_EXPR is part of block BB, which is inside loop LOOP.
344 if_convertible_modify_expr_p (struct loop *loop, basic_block bb, tree m_expr)
361   if (bb != loop->header
377       && bb != loop->header
378       && !bb_with_exit_edge_p (loop, bb))
396    STMT is inside block BB, which is inside loop LOOP.  */
399 if_convertible_stmt_p (struct loop *loop, basic_block bb, tree stmt)
408       if (!if_convertible_modify_expr_p (loop, bb, stmt))
436    BB is inside loop LOOP.  */
439 if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb)
449       if (bb != loop->latch)
461       else if (bb == loop->latch
496 if_convertible_loop_p (struct loop *loop, bool for_vectorizer ATTRIBUTE_UNUSED)
506   /* Handle only inner most loop.  */
507   if (!loop || loop->inner)
510 	fprintf (dump_file, "not inner most loop\n");
515   if (loop->num_nodes <= 2)
522   /* More than one loop exit is too much to handle.  */
523   if (!loop->single_exit)
532   /* If one of the loop header's edge is exit edge then do not apply
534   FOR_EACH_EDGE (e, ei, loop->header->succs)
536       if (loop_exit_edge_p (loop, e))
544   ifc_bbs = get_loop_body_in_if_conv_order (loop);
548 	fprintf (dump_file,"Irreducible loop\n");
553   for (i = 0; i < loop->num_nodes; i++)
557       if (!if_convertible_bb_p (loop, bb, exit_bb))
562 	if (!if_convertible_stmt_p (loop, bb, bsi_stmt (itr)))
576 	if (!if_convertible_phi_p (loop, bb, phi))
579       if (bb_with_exit_edge_p (loop, bb))
584      this loop. Now there is no looking back.  */
612 add_to_dst_predicate_list (struct loop * loop, edge e,
618   if (!flow_bb_inside_loop_p (loop, e->dest))
661 clean_predicate_lists (struct loop *loop)
668   bb = get_loop_body (loop);
669   for (i = 0; i < loop->num_nodes; i++)
683 find_phi_replacement_condition (struct loop *loop,
702      2) Do not make loop header first_bb.
729   /* Check if FIRST_BB is loop header or not and make sure that
731   if (first_edge->src == loop->header
748 	/* Select non loop header bb.  */
753       /* FIRST_BB is not loop header */
853 process_phi_nodes (struct loop *loop)
856   unsigned int orig_loop_num_nodes = loop->num_nodes;
867       if (bb == loop->header)
876 	true_bb = find_phi_replacement_condition (loop, bb, &cond, &bsi);
894 combine_blocks (struct loop *loop)
897   unsigned int orig_loop_num_nodes = loop->num_nodes;
903   process_phi_nodes (loop);
905   /* Merge basic blocks.  First remove all the edges in the loop, except
911       if (bb_with_exit_edge_p (loop, bb))
917   gcc_assert (exit_bb != loop->latch);
934       if (exit_bb != loop->header)
936 	  /* Connect this node with loop header.  */
937 	  make_edge (loop->header, exit_bb, EDGE_FALLTHRU);
938 	  set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header);
941       /* Redirect non-exit edges to loop->latch.  */
944 	  if (!loop_exit_edge_p (loop, e))
945 	    redirect_edge_and_branch (e, loop->latch);
947       set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb);
951       /* If the loop does not have exit then reconnect header and latch.  */
952       make_edge (loop->header, loop->latch, EDGE_FALLTHRU);
953       set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header);
956   merge_target_bb = loop->header;
964       if (bb == exit_bb || bb == loop->latch)
967       /* Remove labels and make stmts member of loop->header.  */
995   /* Now if possible, merge loop header and block with exit edge.
999       && exit_bb != loop->header
1000       && can_merge_blocks_p (loop->header, exit_bb))
1003       merge_blocks (loop->header, exit_bb);
1058 get_loop_body_in_if_conv_order (const struct loop *loop)
1066   gcc_assert (loop->num_nodes);
1067   gcc_assert (loop->latch != EXIT_BLOCK_PTR);
1069   blocks = XCNEWVEC (basic_block, loop->num_nodes);
1072   blocks_in_bfs_order = get_loop_body_in_bfs_order (loop);
1075   while (index < loop->num_nodes)
1089 	      || bb == loop->header)
1097       if (index == loop->num_nodes
1098 	  && visited_count != loop->num_nodes)
1112 bb_with_exit_edge_p (struct loop *loop, basic_block bb)
1119     if (loop_exit_edge_p (loop, e))
1134   struct loop *loop;
1142       loop =  current_loops->parray[i];
1143       if (!loop)
1146       tree_if_conversion (loop, true);