This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[patch] Lno branch merge part 10 -- various utility functions
- From: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- To: gcc-patches at gcc dot gnu dot org
- Date: Thu, 5 Aug 2004 20:43:36 +0200
- Subject: [patch] Lno branch merge part 10 -- various utility functions
Hello,
this patch brings in various utility functions used by loop optimizers:
-- tree_duplicate_loop_to_header_edge for unrolling and peeling loops
-- tree_ssa_loop_version for unswitching and preconditioning loops
-- tree_split_loop_iterations to split loop into two, switching from
the first to the second one after some condition is satisfied
-- tree_align_loop_iterations that uses tree_split_loop_iterations
to ensure that the number of iterations of a loop is divisible
by a given number
-- create_iv to create a new induction variable in a loop
Some of these functions share large parts of code with the
tree-ssa-loop-ch.c rewrite (lno branch merge part 9) patch; for
this reason, the patch includes the "part 9" patch.
The patch also includes the loop closed ssa form creation patch,
since the loop duplication functions are dependent on it.
Bootstrapped & regtested on i686.
Btw. could someone please review this patch soon? I would like
to send the rest of lno branch merge patches before I leave for
a vacation, but all of them are dependent on this patch or its parts.
Zdenek
* tree-ssa-loop-manip.c: New file.
* basic-block.h (struct reorder_block_def): New field copy_number.
* cfgloop.c (mark_single_exit_loops): New.
(verify_loop_structure): Verify single_exit information.
* cfgloop.h (struct loop): Add single_exit field.
(LOOPS_HAVE_MARKED_SINGLE_EXITS): New constant.
(mark_single_exit_loops, update_single_exits_after_duplication,
duplicate_loop): Declare.
(loopify, split_loop_bb): Declaration changed.
* cfgloopmanip.c (duplicate_loop): Export.
(split_loop_bb): Take void * as an argument instead of rtx.
(loopify): Added redirect_all_edges argument.
(update_single_exits_after_duplication): New function.
(duplicate_loop_to_header_edge): Use
update_single_exits_after_duplication. Set copy_number.
* gimplify.c (struct idx_fs_data): New type.
(idx_force_simple, update_addressable_flag, force_gimple_operand): New
functions.
* loop-unswitch.c (unswitch_loop): Changed due to loopify change.
* tree-cfg.c (tree_find_edge_insert_loc): Return newly created block.
(bsi_insert_on_edge_immediate): Resurrect.
* tree-flow.h (bsi_insert_on_edge_immediate,
tree_duplicate_loop_to_header_edge, tree_split_loop_iterations,
tree_align_loop_iterations, tree_ssa_loop_version,
split_loop_exit_edge, bsi_insert_on_edge_immediate_loop, create_iv,
standard_iv_increment_position, force_gimple_operand): Declare.
* tree.c (build_int_cst): New function.
* tree.h (build_int_cst): Declare.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.1337
diff -c -3 -p -r1.1337 Makefile.in
*** Makefile.in 4 Aug 2004 20:55:04 -0000 1.1337
--- Makefile.in 5 Aug 2004 12:37:05 -0000
*************** OBJS-common = \
*** 898,904 ****
tree-ssa-phiopt.o tree-ssa-forwprop.o tree-nested.o tree-ssa-dse.o \
tree-ssa-dom.o domwalk.o tree-tailcall.o gimple-low.o tree-iterator.o \
tree-phinodes.o tree-ssanames.o tree-sra.o tree-complex.o tree-ssa-loop.o \
! tree-ssa-loop-niter.o \
alias.o bb-reorder.o bitmap.o builtins.o caller-save.o calls.o \
cfg.o cfganal.o cfgbuild.o cfgcleanup.o cfglayout.o cfgloop.o \
cfgloopanal.o cfgloopmanip.o loop-init.o loop-unswitch.o loop-unroll.o \
--- 898,904 ----
tree-ssa-phiopt.o tree-ssa-forwprop.o tree-nested.o tree-ssa-dse.o \
tree-ssa-dom.o domwalk.o tree-tailcall.o gimple-low.o tree-iterator.o \
tree-phinodes.o tree-ssanames.o tree-sra.o tree-complex.o tree-ssa-loop.o \
! tree-ssa-loop-niter.o tree-ssa-loop-manip.o \
alias.o bb-reorder.o bitmap.o builtins.o caller-save.o calls.o \
cfg.o cfganal.o cfgbuild.o cfgcleanup.o cfglayout.o cfgloop.o \
cfgloopanal.o cfgloopmanip.o loop-init.o loop-unswitch.o loop-unroll.o \
*************** tree-vn.o : tree-vn.c $(CONFIG_H) $(SYST
*** 1657,1663 ****
tree-cfg.o : tree-cfg.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
$(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) $(GGC_H) $(FLAGS_H) output.h \
diagnostic.h errors.h function.h $(TIMEVAR_H) $(TM_H) coretypes.h \
! $(TREE_DUMP_H) except.h langhooks.h $(CFGLOOP_H) gt-tree-cfg.h tree-pass.h
tree-tailcall.o : tree-tailcall.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
$(RTL_H) $(TREE_H) $(TM_P_H) function.h $(TM_H) coretypes.h \
$(TREE_DUMP_H) diagnostic.h except.h tree-pass.h $(FLAGS_H) langhooks.h
--- 1657,1664 ----
tree-cfg.o : tree-cfg.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
$(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) $(GGC_H) $(FLAGS_H) output.h \
diagnostic.h errors.h function.h $(TIMEVAR_H) $(TM_H) coretypes.h \
! $(TREE_DUMP_H) except.h langhooks.h $(CFGLOOP_H) gt-tree-cfg.h tree-pass.h \
! $(CFGLAYOUT_H)
tree-tailcall.o : tree-tailcall.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
$(RTL_H) $(TREE_H) $(TM_P_H) function.h $(TM_H) coretypes.h \
$(TREE_DUMP_H) diagnostic.h except.h tree-pass.h $(FLAGS_H) langhooks.h
*************** tree-ssa-loop.o : tree-ssa-loop.c $(TREE
*** 1681,1686 ****
--- 1682,1691 ----
$(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(CFGLOOP_H) \
output.h diagnostic.h $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
tree-pass.h $(FLAGS_H) tree-inline.h
+ tree-ssa-loop-manip.o : tree-ssa-loop-manip.c $(TREE_FLOW_H) $(CONFIG_H) \
+ $(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(CFGLOOP_H) \
+ output.h diagnostic.h $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
+ tree-pass.h $(FLAGS_H) cfglayout.h tree-scalar-evolution.h
tree-ssa-loop-niter.o : tree-ssa-loop-niter.c $(TREE_FLOW_H) $(CONFIG_H) \
$(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) cfgloop.h $(PARAMS_H) tree-inline.h \
output.h diagnostic.h $(TM_H) coretypes.h $(TREE_DUMP_H) flags.h \
Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/basic-block.h,v
retrieving revision 1.205
diff -c -3 -p -r1.205 basic-block.h
*** basic-block.h 4 Aug 2004 21:37:03 -0000 1.205
--- basic-block.h 5 Aug 2004 12:37:05 -0000
*************** typedef struct reorder_block_def
*** 297,302 ****
--- 297,303 ----
/* Used by loop copying. */
basic_block copy;
int duplicated;
+ int copy_number;
/* These fields are used by bb-reorder pass. */
int visited;
*************** extern void set_immediate_dominator (enu
*** 720,725 ****
--- 721,728 ----
extern basic_block get_immediate_dominator (enum cdi_direction, basic_block);
extern bool dominated_by_p (enum cdi_direction, basic_block, basic_block);
extern int get_dominated_by (enum cdi_direction, basic_block, basic_block **);
+ extern unsigned get_dominated_by_region (enum cdi_direction, basic_block *,
+ unsigned, basic_block *);
extern void add_to_dominance_info (enum cdi_direction, basic_block);
extern void delete_from_dominance_info (enum cdi_direction, basic_block);
basic_block recount_dominator (enum cdi_direction, basic_block);
Index: cfgloop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloop.c,v
retrieving revision 1.36
diff -c -3 -p -r1.36 cfgloop.c
*** cfgloop.c 29 Jul 2004 17:47:31 -0000 1.36
--- cfgloop.c 5 Aug 2004 12:37:05 -0000
*************** flow_loop_nodes_find (basic_block header
*** 370,375 ****
--- 370,432 ----
return num_nodes;
}
+ /* For each loop in the lOOPS tree that has just a single exit
+ record the exit edge. */
+
+ void
+ mark_single_exit_loops (struct loops *loops)
+ {
+ basic_block bb;
+ edge e;
+ struct loop *loop;
+ unsigned i;
+
+ for (i = 1; i < loops->num; i++)
+ {
+ loop = loops->parray[i];
+ if (loop)
+ loop->single_exit = NULL;
+ }
+
+ FOR_EACH_BB (bb)
+ {
+ if (bb->loop_father == loops->tree_root)
+ continue;
+ for (e = bb->succ; e; e = e->succ_next)
+ {
+ if (e->dest == EXIT_BLOCK_PTR)
+ continue;
+
+ if (flow_bb_inside_loop_p (bb->loop_father, e->dest))
+ continue;
+
+ for (loop = bb->loop_father;
+ loop != e->dest->loop_father;
+ loop = loop->outer)
+ {
+ /* If we have already seen an exit, mark this by the edge that
+ surely does not occur as any exit. */
+ if (loop->single_exit)
+ loop->single_exit = ENTRY_BLOCK_PTR->succ;
+ else
+ loop->single_exit = e;
+ }
+ }
+ }
+
+ for (i = 1; i < loops->num; i++)
+ {
+ loop = loops->parray[i];
+ if (!loop)
+ continue;
+
+ if (loop->single_exit == ENTRY_BLOCK_PTR->succ)
+ loop->single_exit = NULL;
+ }
+
+ loops->state |= LOOPS_HAVE_MARKED_SINGLE_EXITS;
+ }
+
/* Find the root node of the loop pre-header extended basic block and
the edges along the trace from the root node to the loop header. */
*************** glb_enum_p (basic_block bb, void *glb_he
*** 939,944 ****
--- 996,1002 ----
/* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
order against direction of edges from latch. Specially, if
header != latch, latch is the 1-st block. */
+
basic_block *
get_loop_body (const struct loop *loop)
{
*************** fill_sons_in_loop (const struct loop *lo
*** 1003,1009 ****
/* Gets body of a LOOP (that must be different from the outermost loop)
sorted by dominance relation. Additionally, if a basic block s dominates
! the latch, then only blocks dominated by s are be after it. */
basic_block *
get_loop_body_in_dom_order (const struct loop *loop)
--- 1061,1067 ----
/* Gets body of a LOOP (that must be different from the outermost loop)
sorted by dominance relation. Additionally, if a basic block s dominates
! the latch, then only blocks dominated by s are after it. */
basic_block *
get_loop_body_in_dom_order (const struct loop *loop)
*************** verify_loop_structure (struct loops *loo
*** 1197,1204 ****
}
}
- free (sizes);
-
/* Check get_loop_body. */
for (i = 1; i < loops->num; i++)
{
--- 1255,1260 ----
*************** verify_loop_structure (struct loops *loo
*** 1319,1326 ****
--- 1375,1445 ----
free (irreds);
}
+ /* Check the single_exit. */
+ if (loops->state & LOOPS_HAVE_MARKED_SINGLE_EXITS)
+ {
+ memset (sizes, 0, sizeof (unsigned) * loops->num);
+ FOR_EACH_BB (bb)
+ {
+ if (bb->loop_father == loops->tree_root)
+ continue;
+ for (e = bb->succ; e; e = e->succ_next)
+ {
+ if (e->dest == EXIT_BLOCK_PTR)
+ continue;
+
+ if (flow_bb_inside_loop_p (bb->loop_father, e->dest))
+ continue;
+
+ for (loop = bb->loop_father;
+ loop != e->dest->loop_father;
+ loop = loop->outer)
+ {
+ sizes[loop->num]++;
+ if (loop->single_exit
+ && loop->single_exit != e)
+ {
+ error ("Wrong single exit %d->%d recorded for loop %d.",
+ loop->single_exit->src->index,
+ loop->single_exit->dest->index,
+ loop->num);
+ error ("Right exit is %d->%d.",
+ e->src->index, e->dest->index);
+ err = 1;
+ }
+ }
+ }
+ }
+
+ for (i = 1; i < loops->num; i++)
+ {
+ loop = loops->parray[i];
+ if (!loop)
+ continue;
+
+ if (sizes[i] == 1
+ && !loop->single_exit)
+ {
+ error ("Single exit not recorded for loop %d.", loop->num);
+ err = 1;
+ }
+
+ if (sizes[i] != 1
+ && loop->single_exit)
+ {
+ error ("Loop %d should not have single exit (%d -> %d).",
+ loop->num,
+ loop->single_exit->src->index,
+ loop->single_exit->dest->index);
+ err = 1;
+ }
+ }
+ }
+
if (err)
abort ();
+
+ free (sizes);
}
/* Returns latch edge of LOOP. */
Index: cfgloop.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloop.h,v
retrieving revision 1.23
diff -c -3 -p -r1.23 cfgloop.h
*** cfgloop.h 12 Jul 2004 19:31:16 -0000 1.23
--- cfgloop.h 5 Aug 2004 12:37:05 -0000
*************** struct loop
*** 185,190 ****
--- 185,194 ----
/* Upper bound on number of iterations of a loop. */
struct nb_iter_bound *bounds;
+
+ /* If not NULL, loop has just single exit edge stored here (edges to the
+ EXIT_BLOCK_PTR do not count. */
+ edge single_exit;
};
/* Flags for state of loop structure. */
*************** enum
*** 192,198 ****
{
LOOPS_HAVE_PREHEADERS = 1,
LOOPS_HAVE_SIMPLE_LATCHES = 2,
! LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS = 4
};
/* Structure to hold CFG information about natural loops within a function. */
--- 196,203 ----
{
LOOPS_HAVE_PREHEADERS = 1,
LOOPS_HAVE_SIMPLE_LATCHES = 2,
! LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS = 4,
! LOOPS_HAVE_MARKED_SINGLE_EXITS = 8
};
/* Structure to hold CFG information about natural loops within a function. */
*************** extern void flow_loop_dump (const struct
*** 258,263 ****
--- 263,270 ----
extern int flow_loop_scan (struct loop *, int);
extern void flow_loop_free (struct loop *);
void mark_irreducible_loops (struct loops *);
+ void mark_single_exit_loops (struct loops *);
+ void update_single_exits_after_duplication (basic_block *, unsigned, struct loop *);
extern void create_loop_notes (void);
/* Loop data structure manipulation/querying. */
*************** extern unsigned expected_loop_iterations
*** 306,311 ****
--- 313,320 ----
/* Loop manipulation. */
extern bool can_duplicate_loop_p (struct loop *loop);
+ extern struct loop * duplicate_loop (struct loops *,
+ struct loop *, struct loop *);
#define DLTHE_FLAG_UPDATE_FREQ 1 /* Update frequencies in
duplicate_loop_to_header_edge. */
*************** extern bool can_duplicate_loop_p (struct
*** 313,322 ****
extern int duplicate_loop_to_header_edge (struct loop *, edge, struct loops *,
unsigned, sbitmap, edge, edge *,
unsigned *, int);
! extern struct loop *loopify (struct loops *, edge, edge, basic_block);
extern void unloop (struct loops *, struct loop *);
extern bool remove_path (struct loops *, edge);
! extern edge split_loop_bb (basic_block, rtx);
/* Induction variable analysis. */
--- 322,331 ----
extern int duplicate_loop_to_header_edge (struct loop *, edge, struct loops *,
unsigned, sbitmap, edge, edge *,
unsigned *, int);
! extern struct loop *loopify (struct loops *, edge, edge, basic_block, bool);
extern void unloop (struct loops *, struct loop *);
extern bool remove_path (struct loops *, edge);
! extern edge split_loop_bb (basic_block, void *);
/* Induction variable analysis. */
Index: cfgloopmanip.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloopmanip.c,v
retrieving revision 1.27
diff -c -3 -p -r1.27 cfgloopmanip.c
*** cfgloopmanip.c 9 Jul 2004 03:29:26 -0000 1.27
--- cfgloopmanip.c 5 Aug 2004 12:37:05 -0000
*************** Software Foundation, 59 Temple Place - S
*** 29,36 ****
#include "cfglayout.h"
#include "output.h"
- static struct loop * duplicate_loop (struct loops *, struct loop *,
- struct loop *);
static void duplicate_subloops (struct loops *, struct loop *, struct loop *);
static void copy_loops_to (struct loops *, struct loop **, int,
struct loop *);
--- 29,34 ----
*************** static void fix_irreducible_loops (basic
*** 55,61 ****
/* Splits basic block BB after INSN, returns created edge. Updates loops
and dominators. */
edge
! split_loop_bb (basic_block bb, rtx insn)
{
edge e;
--- 53,59 ----
/* Splits basic block BB after INSN, returns created edge. Updates loops
and dominators. */
edge
! split_loop_bb (basic_block bb, void *insn)
{
edge e;
*************** scale_loop_frequencies (struct loop *loo
*** 488,494 ****
struct loop *
loopify (struct loops *loops, edge latch_edge, edge header_edge,
! basic_block switch_bb)
{
basic_block succ_bb = latch_edge->dest;
basic_block pred_bb = header_edge->src;
--- 486,492 ----
struct loop *
loopify (struct loops *loops, edge latch_edge, edge header_edge,
! basic_block switch_bb, bool redirect_all_edges)
{
basic_block succ_bb = latch_edge->dest;
basic_block pred_bb = header_edge->src;
*************** loopify (struct loops *loops, edge latch
*** 515,526 ****
loop_redirect_edge (latch_edge, loop->header);
loop_redirect_edge (BRANCH_EDGE (switch_bb), succ_bb);
! loop_redirect_edge (header_edge, switch_bb);
! loop_redirect_edge (FALLTHRU_EDGE (switch_bb), loop->header);
!
! /* Update dominators. */
! set_immediate_dominator (CDI_DOMINATORS, switch_bb, pred_bb);
! set_immediate_dominator (CDI_DOMINATORS, loop->header, switch_bb);
set_immediate_dominator (CDI_DOMINATORS, succ_bb, switch_bb);
--- 513,529 ----
loop_redirect_edge (latch_edge, loop->header);
loop_redirect_edge (BRANCH_EDGE (switch_bb), succ_bb);
! /* During loop versioning, one of the switch_bb edge is already properly
! set. Do not redirect it again unless redirect_all_edges is true. */
! if (redirect_all_edges)
! {
! loop_redirect_edge (header_edge, switch_bb);
! loop_redirect_edge (FALLTHRU_EDGE (switch_bb), loop->header);
!
! /* Update dominators. */
! set_immediate_dominator (CDI_DOMINATORS, switch_bb, pred_bb);
! set_immediate_dominator (CDI_DOMINATORS, loop->header, switch_bb);
! }
set_immediate_dominator (CDI_DOMINATORS, succ_bb, switch_bb);
*************** place_new_loop (struct loops *loops, str
*** 701,707 ****
/* Copies copy of LOOP as subloop of TARGET loop, placing newly
created loop into LOOPS structure. */
! static struct loop *
duplicate_loop (struct loops *loops, struct loop *loop, struct loop *target)
{
struct loop *cloop;
--- 704,710 ----
/* Copies copy of LOOP as subloop of TARGET loop, placing newly
created loop into LOOPS structure. */
! struct loop *
duplicate_loop (struct loops *loops, struct loop *loop, struct loop *target)
{
struct loop *cloop;
*************** can_duplicate_loop_p (struct loop *loop)
*** 821,826 ****
--- 824,854 ----
return ret;
}
+ /* The NBBS blocks in BBS will get duplicated and the copies will be placed
+ to LOOP. Update the single_exit information in superloops of LOOP. */
+
+ void
+ update_single_exits_after_duplication (basic_block *bbs, unsigned nbbs,
+ struct loop *loop)
+ {
+ unsigned i;
+
+ for (i = 0; i < nbbs; i++)
+ bbs[i]->rbi->duplicated = 1;
+
+ for (; loop->outer; loop = loop->outer)
+ {
+ if (!loop->single_exit)
+ continue;
+
+ if (loop->single_exit->src->rbi->duplicated)
+ loop->single_exit = NULL;
+ }
+
+ for (i = 0; i < nbbs; i++)
+ bbs[i]->rbi->duplicated = 0;
+ }
+
/* Duplicates body of LOOP to given edge E NDUPL times. Takes care of updating
LOOPS structure and dominators. E's destination must be LOOP header for
*************** duplicate_loop_to_header_edge (struct lo
*** 964,969 ****
--- 992,1001 ----
first_active_latch = latch;
}
+ /* Update the information about single exits. */
+ if (loops->state & LOOPS_HAVE_MARKED_SINGLE_EXITS)
+ update_single_exits_after_duplication (bbs, n, target);
+
/* Record exit edge in original loop body. */
if (orig && TEST_BIT (wont_exit, 0))
to_remove[(*n_to_remove)++] = orig;
*************** duplicate_loop_to_header_edge (struct lo
*** 979,984 ****
--- 1011,1019 ----
/* Copy bbs. */
copy_bbs (bbs, n, new_bbs, spec_edges, 2, new_spec_edges, loop);
+ for (i = 0; i < n; i++)
+ new_bbs[i]->rbi->copy_number = j + 1;
+
/* Note whether the blocks and edges belong to an irreducible loop. */
if (add_irreducible_flag)
{
*************** duplicate_loop_to_header_edge (struct lo
*** 1057,1062 ****
--- 1092,1099 ----
int n_dom_bbs,j;
bb = bbs[i];
+ bb->rbi->copy_number = 0;
+
n_dom_bbs = get_dominated_by (CDI_DOMINATORS, bb, &dom_bbs);
for (j = 0; j < n_dom_bbs; j++)
{
Index: dominance.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/dominance.c,v
retrieving revision 1.26
diff -c -3 -p -r1.26 dominance.c
*** dominance.c 29 Jul 2004 17:47:31 -0000 1.26
--- dominance.c 5 Aug 2004 12:37:05 -0000
*************** get_dominated_by (enum cdi_direction dir
*** 746,751 ****
--- 746,777 ----
return n;
}
+ /* Find all basic blocks that are immediately dominated (in direction DIR)
+ by some block between N_REGION ones stored in REGION, except for blocks
+ in the REGION itself. The found blocks are stored to DOMS and their number
+ is returned. */
+
+ unsigned
+ get_dominated_by_region (enum cdi_direction dir, basic_block *region,
+ unsigned n_region, basic_block *doms)
+ {
+ unsigned n_doms = 0, i;
+ basic_block dom;
+
+ for (i = 0; i < n_region; i++)
+ region[i]->rbi->duplicated = 1;
+ for (i = 0; i < n_region; i++)
+ for (dom = first_dom_son (dir, region[i]);
+ dom;
+ dom = next_dom_son (dir, dom))
+ if (!dom->rbi->duplicated)
+ doms[n_doms++] = dom;
+ for (i = 0; i < n_region; i++)
+ region[i]->rbi->duplicated = 0;
+
+ return n_doms;
+ }
+
/* Redirect all edges pointing to BB to TO. */
void
redirect_immediate_dominators (enum cdi_direction dir, basic_block bb,
Index: gimplify.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/gimplify.c,v
retrieving revision 2.57
diff -c -3 -p -r2.57 gimplify.c
*** gimplify.c 30 Jul 2004 22:55:22 -0000 2.57
--- gimplify.c 5 Aug 2004 12:37:05 -0000
*************** gimplify_function_tree (tree fndecl)
*** 4237,4240 ****
--- 4237,4418 ----
current_function_decl = oldfn;
}
+ /* Forces IDX to be either constant or ssa name. Callback for
+ for_each_index. */
+
+ struct idx_fs_data
+ {
+ tree stmts;
+ };
+
+ static bool
+ idx_force_simple (tree base ATTRIBUTE_UNUSED, tree *idx, void *data)
+ {
+ struct idx_fs_data *d = data;
+ tree stmts;
+
+ *idx = force_gimple_operand (*idx, &stmts, true, NULL_TREE);
+
+ if (stmts)
+ {
+ tree_stmt_iterator tsi = tsi_start (d->stmts);
+ tsi_link_before (&tsi, stmts, TSI_SAME_STMT);
+ }
+
+ return true;
+ }
+
+ /* Updates TREE_ADDRESSABLE flag for the base variable of EXPR. */
+
+ static void
+ update_addressable_flag (tree expr)
+ {
+ if (TREE_CODE (expr) != ADDR_EXPR)
+ abort ();
+
+ expr = TREE_OPERAND (expr, 0);
+ while (TREE_CODE (expr) == ARRAY_REF
+ || TREE_CODE (expr) == COMPONENT_REF
+ || TREE_CODE (expr) == REALPART_EXPR
+ || TREE_CODE (expr) == IMAGPART_EXPR)
+ expr = TREE_OPERAND (expr, 0);
+ if (TREE_CODE (expr) != VAR_DECL
+ && TREE_CODE (expr) != PARM_DECL)
+ return;
+
+ TREE_ADDRESSABLE (expr) = 1;
+ }
+
+ /* Expands EXPR to list of gimple statements STMTS, forcing it to become
+ a gimple operand that is returned. If SIMPLE is true, force the operand
+ to be either ssa_name or integer constant. If VAR is not NULL, make the
+ base variable of the final destination be VAR if possible. */
+
+ tree
+ force_gimple_operand (tree expr, tree *stmts, bool simple, tree var)
+ {
+ enum tree_code code;
+ char class;
+ tree op0, op1, stmts0, stmts1, stmt, rhs, name;
+ tree_stmt_iterator tsi;
+ struct idx_fs_data d;
+ tree atmp;
+
+ /* Throw away the useless type conversions, so that we do not create
+ unnecessary junk. */
+ STRIP_TYPE_NOPS (expr);
+ STRIP_USELESS_TYPE_CONVERSION (expr);
+
+ code = TREE_CODE (expr);
+ class = TREE_CODE_CLASS (code);
+
+ if (is_gimple_val (expr)
+ && (!simple
+ || TREE_CODE (expr) == SSA_NAME
+ || TREE_CODE (expr) == INTEGER_CST))
+ {
+ if (code == ADDR_EXPR)
+ update_addressable_flag (expr);
+
+ *stmts = NULL_TREE;
+ return expr;
+ }
+
+ if (code == ADDR_EXPR)
+ {
+ op0 = TREE_OPERAND (expr, 0);
+ if (TREE_CODE (op0) == INDIRECT_REF)
+ return force_gimple_operand (TREE_OPERAND (op0, 0), stmts, simple,
+ NULL_TREE);
+ }
+
+ if (var)
+ atmp = var;
+ else
+ {
+ atmp = create_tmp_var (TREE_TYPE (expr), "fgotmp");
+ add_referenced_tmp_var (atmp);
+ }
+
+ switch (class)
+ {
+ case '1':
+ case '2':
+ op0 = force_gimple_operand (TREE_OPERAND (expr, 0), &stmts0, false,
+ NULL_TREE);
+ if (class == '2')
+ {
+ op1 = force_gimple_operand (TREE_OPERAND (expr, 1), &stmts1, false,
+ NULL_TREE);
+ rhs = build (code, TREE_TYPE (expr), op0, op1);
+ }
+ else
+ {
+ rhs = build1 (code, TREE_TYPE (expr), op0);
+ stmts1 = NULL_TREE;
+ }
+
+ stmt = build (MODIFY_EXPR, void_type_node, atmp, rhs);
+ name = make_ssa_name (atmp, stmt);
+ TREE_OPERAND (stmt, 0) = name;
+
+ if (stmts0)
+ {
+ *stmts = stmts0;
+ if (stmts1)
+ {
+ tsi = tsi_last (*stmts);
+ tsi_link_after (&tsi, stmts1, TSI_CONTINUE_LINKING);
+ }
+ }
+ else if (stmts1)
+ *stmts = stmts1;
+ else
+ *stmts = alloc_stmt_list ();
+
+ tsi = tsi_last (*stmts);
+ tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
+ return name;
+
+ default:
+ break;
+ }
+
+ /* Some specially handled codes: */
+ switch (TREE_CODE (expr))
+ {
+ case ADDR_EXPR:
+ stmt = build (MODIFY_EXPR, void_type_node, atmp, expr);
+ name = make_ssa_name (atmp, stmt);
+ TREE_OPERAND (stmt, 0) = name;
+
+ *stmts = alloc_stmt_list ();
+ tsi = tsi_last (*stmts);
+ tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
+
+ d.stmts = *stmts;
+ for_each_index (&TREE_OPERAND (expr, 0), idx_force_simple, &d);
+
+ update_addressable_flag (TREE_OPERAND (stmt, 1));
+
+ return name;
+
+ case INTEGER_CST:
+ if (!TREE_OVERFLOW (expr))
+ abort ();
+
+ stmt = build (MODIFY_EXPR, void_type_node, atmp, expr);
+ name = make_ssa_name (atmp, stmt);
+ TREE_OPERAND (stmt, 0) = name;
+
+ *stmts = alloc_stmt_list ();
+ tsi = tsi_last (*stmts);
+ tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
+ return name;
+
+ default:
+ abort ();
+ }
+ }
+
#include "gt-gimplify.h"
Index: loop-unswitch.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop-unswitch.c,v
retrieving revision 1.19
diff -c -3 -p -r1.19 loop-unswitch.c
*** loop-unswitch.c 27 Jul 2004 07:27:12 -0000 1.19
--- loop-unswitch.c 5 Aug 2004 12:37:05 -0000
*************** unswitch_loop (struct loops *loops, stru
*** 475,481 ****
/* Loopify from the copy of LOOP body, constructing the new loop. */
nloop = loopify (loops, latch_edge,
! loop->header->rbi->copy->pred, switch_bb);
/* Remove branches that are now unreachable in new loops. */
remove_path (loops, true_edge);
--- 475,481 ----
/* Loopify from the copy of LOOP body, constructing the new loop. */
nloop = loopify (loops, latch_edge,
! loop->header->rbi->copy->pred, switch_bb, true);
/* Remove branches that are now unreachable in new loops. */
remove_path (loops, true_edge);
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-cfg.c,v
retrieving revision 2.38
diff -c -3 -p -r2.38 tree-cfg.c
*** tree-cfg.c 4 Aug 2004 21:37:06 -0000 2.38
--- tree-cfg.c 5 Aug 2004 12:37:05 -0000
*************** Boston, MA 02111-1307, USA. */
*** 43,48 ****
--- 43,49 ----
#include "toplev.h"
#include "except.h"
#include "cfgloop.h"
+ #include "cfglayout.h"
/* This file contains functions for building the Control Flow Graph (CFG)
for a function tree. */
*************** bsi_replace (const block_stmt_iterator *
*** 2913,2922 ****
In all cases, the returned *BSI points to the correct location. The
return value is true if insertion should be done after the location,
! or false if it should be done before the location. */
static bool
! tree_find_edge_insert_loc (edge e, block_stmt_iterator *bsi)
{
basic_block dest, src;
tree tmp;
--- 2914,2925 ----
In all cases, the returned *BSI points to the correct location. The
return value is true if insertion should be done after the location,
! or false if it should be done before the location. If new basic block
! has to be created, it is stored in *NEW_BB. */
static bool
! tree_find_edge_insert_loc (edge e, block_stmt_iterator *bsi,
! basic_block *new_bb)
{
basic_block dest, src;
tree tmp;
*************** tree_find_edge_insert_loc (edge e, block
*** 2993,2998 ****
--- 2996,3003 ----
/* Otherwise, create a new basic block, and split this edge. */
dest = split_edge (e);
+ if (new_bb)
+ *new_bb = dest;
e = dest->pred;
goto restart;
}
*************** bsi_commit_edge_inserts_1 (edge e)
*** 3036,3042 ****
PENDING_STMT (e) = NULL_TREE;
! if (tree_find_edge_insert_loc (e, &bsi))
bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
else
bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
--- 3041,3047 ----
PENDING_STMT (e) = NULL_TREE;
! if (tree_find_edge_insert_loc (e, &bsi, NULL))
bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
else
bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
*************** bsi_insert_on_edge (edge e, tree stmt)
*** 3053,3058 ****
--- 3058,3083 ----
append_to_statement_list (stmt, &PENDING_STMT (e));
}
+ /* Similar to bsi_insert_on_edge+bsi_commit_edge_inserts. If new block has to
+ be created, it is returned. */
+
+ basic_block
+ bsi_insert_on_edge_immediate (edge e, tree stmt)
+ {
+ block_stmt_iterator bsi;
+ basic_block new_bb = NULL;
+
+ if (PENDING_STMT (e))
+ abort ();
+
+ if (tree_find_edge_insert_loc (e, &bsi, &new_bb))
+ bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
+ else
+ bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
+
+ return new_bb;
+ }
+
/*---------------------------------------------------------------------------
Tree specific functions for CFG manipulation
*************** tree_can_duplicate_bb_p (basic_block bb
*** 4289,4295 ****
return true;
}
-
/* Create a duplicate of the basic block BB. NOTE: This does not
preserve SSA form. */
--- 4314,4319 ----
*************** tree_duplicate_bb (basic_block bb)
*** 4306,4315 ****
--- 4330,4344 ----
new_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
+ /* First copy the phi nodes. We do not copy phi node arguments here,
+ since the edges are not ready yet. Keep the chain of phi nodes in
+ the same order, so that we can add them later. */
for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
{
mark_for_rewrite (PHI_RESULT (phi));
+ create_phi_node (PHI_RESULT (phi), new_bb);
}
+ set_phi_nodes (new_bb, nreverse (phi_nodes (new_bb)));
bsi_tgt = bsi_start (new_bb);
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
*************** tree_duplicate_bb (basic_block bb)
*** 4347,4352 ****
--- 4376,4772 ----
return new_bb;
}
+ /* Basic block BB_COPY was created by code duplication. Add phi node
+ arguments for edges going out of BB_COPY. The blocks that were
+ duplicated have rbi->duplicated set to one. */
+
+ void
+ add_phi_args_after_copy_bb (basic_block bb_copy)
+ {
+ basic_block bb, dest;
+ edge e, e_copy;
+ tree phi, phi_copy, phi_next, def;
+
+ bb = bb_copy->rbi->original;
+
+ for (e_copy = bb_copy->succ; e_copy; e_copy = e_copy->succ_next)
+ {
+ if (!phi_nodes (e_copy->dest))
+ continue;
+
+ if (e_copy->dest->rbi->duplicated)
+ dest = e_copy->dest->rbi->original;
+ else
+ dest = e_copy->dest;
+
+ e = find_edge (bb, dest);
+ if (!e)
+ {
+ /* During loop unrolling the target of the latch edge is copied.
+ In this case we are not looking for edge to dest, but to
+ duplicated block whose original was dest. */
+ for (e = bb->succ; e; e = e->succ_next)
+ if (e->dest->rbi->duplicated
+ && e->dest->rbi->original == dest)
+ break;
+
+ if (!e)
+ abort ();
+ }
+
+ for (phi = phi_nodes (e->dest), phi_copy = phi_nodes (e_copy->dest);
+ phi;
+ phi = phi_next, phi_copy = TREE_CHAIN (phi_copy))
+ {
+ phi_next = TREE_CHAIN (phi);
+
+ if (PHI_RESULT (phi) != PHI_RESULT (phi_copy))
+ abort ();
+ def = PHI_ARG_DEF_FROM_EDGE (phi, e);
+ add_phi_arg (&phi_copy, def, e_copy);
+ }
+ }
+ }
+
+ /* Blocks in REGION_COPY array of length N_REGION were created by
+ duplication of basic blocks. Add phi node arguments for edges
+ going from these blocks. */
+
+ void
+ add_phi_args_after_copy (basic_block *region_copy, unsigned n_region)
+ {
+ unsigned i;
+
+ for (i = 0; i < n_region; i++)
+ region_copy[i]->rbi->duplicated = 1;
+
+ for (i = 0; i < n_region; i++)
+ add_phi_args_after_copy_bb (region_copy[i]);
+
+ for (i = 0; i < n_region; i++)
+ region_copy[i]->rbi->duplicated = 0;
+ }
+
+ /* Maps the old ssa name FROM_NAME to TO_NAME. */
+
+ struct ssa_name_map_entry
+ {
+ tree from_name;
+ tree to_name;
+ };
+
+ /* Hash function for ssa_name_map_entry. */
+
+ static hashval_t
+ ssa_name_map_entry_hash (const void *entry)
+ {
+ const struct ssa_name_map_entry *en = entry;
+ return SSA_NAME_VERSION (en->from_name);
+ }
+
+ /* Equality function for ssa_name_map_entry. */
+
+ static int
+ ssa_name_map_entry_eq (const void *in_table, const void *ssa_name)
+ {
+ const struct ssa_name_map_entry *en = in_table;
+
+ return en->from_name == ssa_name;
+ }
+
+ /* Allocate duplicates of ssa names in list DEFINITIONS and store the mapping
+ to MAP. */
+
+ void
+ allocate_ssa_names (bitmap definitions, htab_t *map)
+ {
+ tree name;
+ struct ssa_name_map_entry *entry;
+ PTR *slot;
+ unsigned ver;
+
+ if (!*map)
+ *map = htab_create (10, ssa_name_map_entry_hash,
+ ssa_name_map_entry_eq, free);
+ EXECUTE_IF_SET_IN_BITMAP (definitions, 0, ver,
+ {
+ name = ssa_name (ver);
+ slot = htab_find_slot_with_hash (*map, name, SSA_NAME_VERSION (name),
+ INSERT);
+ if (*slot)
+ entry = *slot;
+ else
+ {
+ entry = xmalloc (sizeof (struct ssa_name_map_entry));
+ entry->from_name = name;
+ *slot = entry;
+ }
+ entry->to_name = duplicate_ssa_name (name, SSA_NAME_DEF_STMT (name));
+ });
+ }
+
+ /* Rewrite the definition DEF in statement STMT to new ssa name as specified
+ by the mapping MAP. */
+
+ static void
+ rewrite_to_new_ssa_names_def (def_operand_p def, tree stmt, htab_t map)
+ {
+ tree name = DEF_FROM_PTR (def);
+ struct ssa_name_map_entry *entry;
+
+ if (TREE_CODE (name) != SSA_NAME)
+ abort ();
+
+ entry = htab_find_with_hash (map, name, SSA_NAME_VERSION (name));
+ if (!entry)
+ return;
+
+ SET_DEF (def, entry->to_name);
+ SSA_NAME_DEF_STMT (entry->to_name) = stmt;
+ }
+
+ /* Rewrite the USE to new ssa name as specified by the mapping MAP. */
+
+ static void
+ rewrite_to_new_ssa_names_use (use_operand_p use, htab_t map)
+ {
+ tree name = USE_FROM_PTR (use);
+ struct ssa_name_map_entry *entry;
+
+ if (TREE_CODE (name) != SSA_NAME)
+ return;
+
+ entry = htab_find_with_hash (map, name, SSA_NAME_VERSION (name));
+ if (!entry)
+ return;
+
+ SET_USE (use, entry->to_name);
+ }
+
+ /* Rewrite the ssa names in basic block BB to new ones as specified by the
+ mapping MAP. */
+
+ void
+ rewrite_to_new_ssa_names_bb (basic_block bb, htab_t map)
+ {
+ unsigned i;
+ edge e;
+ tree phi, stmt;
+ block_stmt_iterator bsi;
+ use_optype uses;
+ vuse_optype vuses;
+ def_optype defs;
+ v_may_def_optype v_may_defs;
+ v_must_def_optype v_must_defs;
+ stmt_ann_t ann;
+
+ for (e = bb->pred; e; e = e->pred_next)
+ if (e->flags & EDGE_ABNORMAL)
+ break;
+
+ for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
+ {
+ rewrite_to_new_ssa_names_def (PHI_RESULT_PTR (phi), phi, map);
+ if (e)
+ SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)) = 1;
+ }
+
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ stmt = bsi_stmt (bsi);
+ get_stmt_operands (stmt);
+ ann = stmt_ann (stmt);
+
+ uses = USE_OPS (ann);
+ for (i = 0; i < NUM_USES (uses); i++)
+ rewrite_to_new_ssa_names_use (USE_OP_PTR (uses, i), map);
+
+ defs = DEF_OPS (ann);
+ for (i = 0; i < NUM_DEFS (defs); i++)
+ rewrite_to_new_ssa_names_def (DEF_OP_PTR (defs, i), stmt, map);
+
+ vuses = VUSE_OPS (ann);
+ for (i = 0; i < NUM_VUSES (vuses); i++)
+ rewrite_to_new_ssa_names_use (VUSE_OP_PTR (vuses, i), map);
+
+ v_may_defs = V_MAY_DEF_OPS (ann);
+ for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
+ {
+ rewrite_to_new_ssa_names_use
+ (V_MAY_DEF_OP_PTR (v_may_defs, i), map);
+ rewrite_to_new_ssa_names_def
+ (V_MAY_DEF_RESULT_PTR (v_may_defs, i), stmt, map);
+ }
+
+ v_must_defs = V_MUST_DEF_OPS (ann);
+ for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++)
+ rewrite_to_new_ssa_names_def
+ (V_MUST_DEF_OP_PTR (v_must_defs, i), stmt, map);
+ }
+
+ for (e = bb->succ; e; e = e->succ_next)
+ for (phi = phi_nodes (e->dest); phi; phi = TREE_CHAIN (phi))
+ {
+ rewrite_to_new_ssa_names_use
+ (PHI_ARG_DEF_PTR_FROM_EDGE (phi, e), map);
+
+ if (e->flags & EDGE_ABNORMAL)
+ {
+ tree op = PHI_ARG_DEF_FROM_EDGE (phi, e);
+ SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op) = 1;
+ }
+ }
+ }
+
+ /* Rewrite the ssa names in N_REGION blocks REGION to the new ones as specified
+ by the mapping MAP. */
+
+ void
+ rewrite_to_new_ssa_names (basic_block *region, unsigned n_region, htab_t map)
+ {
+ unsigned r;
+
+ for (r = 0; r < n_region; r++)
+ rewrite_to_new_ssa_names_bb (region[r], map);
+ }
+
+ /* Duplicates a REGION (set of N_REGION basic blocks) with just a single
+ important exit edge EXIT. By important we mean that no SSA name defined
+ inside region is live over the other exit edges of the region. All entry
+ edges to the region must go to ENTRY->dest. The edge ENTRY is redirected
+ to the duplicate of the region. SSA form, dominance and loop information
+ is updated. The new basic blocks are stored to REGION_COPY in the same
+ order as they had in REGION, provided that REGION_COPY is not NULL.
+ The function returns false if it is unable to copy the region,
+ true otherwise. */
+
+ bool
+ tree_duplicate_sese_region (edge entry, edge exit,
+ basic_block *region, unsigned n_region,
+ basic_block *region_copy)
+ {
+ unsigned i, n_doms, ver;
+ bool free_region_copy = false, copying_header = false;
+ struct loop *loop = entry->dest->loop_father;
+ edge exit_copy;
+ bitmap definitions;
+ tree phi, var;
+ basic_block *doms;
+ htab_t ssa_name_map = NULL;
+
+ if (!can_copy_bbs_p (region, n_region))
+ return false;
+
+ /* Some sanity checking. Note that we do not check for all possible
+ missuses of the functions. I.e. if you ask to copy something weird,
+ it will work, but the state of structures probably will not be
+ correct. */
+
+ for (i = 0; i < n_region; i++)
+ {
+ /* We do not handle subloops, i.e. all the blocks must belong to the
+ same loop. */
+ if (region[i]->loop_father != loop)
+ return false;
+
+ if (region[i] != entry->dest
+ && region[i] == loop->header)
+ return false;
+ }
+
+ loop->copy = loop;
+
+ /* In case the function is used for loop header copying (which is the primary
+ use), ensure that EXIT and its copy will be new latch and entry edges. */
+ if (loop->header == entry->dest)
+ {
+ copying_header = true;
+ loop->copy = loop->outer;
+
+ if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
+ return false;
+
+ for (i = 0; i < n_region; i++)
+ if (region[i] != exit->src
+ && dominated_by_p (CDI_DOMINATORS, region[i], exit->src))
+ return false;
+ }
+
+ if (!region_copy)
+ {
+ region_copy = xmalloc (sizeof (basic_block) * n_region);
+ free_region_copy = true;
+ }
+
+ if (any_marked_for_rewrite_p ())
+ abort ();
+
+ /* Record blocks outside the region that are duplicated by something
+ inside. */
+ doms = xmalloc (sizeof (basic_block) * n_basic_blocks);
+ n_doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region, doms);
+
+ copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop);
+ definitions = marked_ssa_names ();
+
+ if (copying_header)
+ {
+ loop->header = exit->dest;
+ loop->latch = exit->src;
+ }
+
+ /* Redirect the entry and add the phi node arguments. */
+ if (!redirect_edge_and_branch (entry, entry->dest->rbi->copy))
+ abort ();
+ for (phi = phi_nodes (entry->dest), var = PENDING_STMT (entry);
+ phi;
+ phi = TREE_CHAIN (phi), var = TREE_CHAIN (var))
+ add_phi_arg (&phi, TREE_VALUE (var), entry);
+ PENDING_STMT (entry) = NULL;
+
+ /* Concerning updating of dominators: We must recount dominators
+ for entry block and its copy. Anything that is outside of the region, but
+ was dominated by something inside needs recounting as well. */
+ set_immediate_dominator (CDI_DOMINATORS, entry->dest, entry->src);
+ doms[n_doms++] = entry->dest->rbi->original;
+ iterate_fix_dominators (CDI_DOMINATORS, doms, n_doms);
+ free (doms);
+
+ /* Add the other phi node arguments. */
+ add_phi_args_after_copy (region_copy, n_region);
+
+ /* Add phi nodes for definitions at exit. TODO -- once we have immediate
+ uses, it should be possible to emit phi nodes just for definitions that
+ are used outside region. */
+ EXECUTE_IF_SET_IN_BITMAP (definitions, 0, ver,
+ {
+ tree name = ssa_name (ver);
+
+ phi = create_phi_node (name, exit->dest);
+ add_phi_arg (&phi, name, exit);
+ add_phi_arg (&phi, name, exit_copy);
+
+ SSA_NAME_DEF_STMT (name) = phi;
+ });
+
+ /* And create new definitions inside region and its copy. TODO -- once we
+ have immediate uses, it might be better to leave definitions in region
+ unchanged, create new ssa names for phi nodes on exit, and rewrite
+ the uses, to avoid changing the copied region. */
+ allocate_ssa_names (definitions, &ssa_name_map);
+ rewrite_to_new_ssa_names (region, n_region, ssa_name_map);
+ allocate_ssa_names (definitions, &ssa_name_map);
+ rewrite_to_new_ssa_names (region_copy, n_region, ssa_name_map);
+ htab_delete (ssa_name_map);
+
+ if (free_region_copy)
+ free (region_copy);
+
+ unmark_all_for_rewrite ();
+ BITMAP_XFREE (definitions);
+
+ return true;
+ }
/* Dump FUNCTION_DECL FN to file FILE using FLAGS (see TDF_* in tree.h) */
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.30
diff -c -3 -p -r2.30 tree-flow.h
*** tree-flow.h 4 Aug 2004 20:37:38 -0000 2.30
--- tree-flow.h 5 Aug 2004 12:37:05 -0000
*************** extern void tree_optimize_tail_calls (bo
*** 487,498 ****
--- 487,506 ----
extern edge tree_block_forwards_to (basic_block bb);
extern void bsi_insert_on_edge (edge, tree);
extern void bsi_commit_edge_inserts (int *);
+ extern basic_block bsi_insert_on_edge_immediate (edge, tree);
extern void notice_special_calls (tree);
extern void clear_special_calls (void);
extern void compute_dominance_frontiers (bitmap *);
extern void verify_stmts (void);
extern tree tree_block_label (basic_block bb);
extern void extract_true_false_edges_from_block (basic_block, edge *, edge *);
+ extern bool tree_duplicate_sese_region (edge, edge, basic_block *, unsigned,
+ basic_block *);
+ extern void add_phi_args_after_copy_bb (basic_block);
+ extern void add_phi_args_after_copy (basic_block *, unsigned);
+ extern void rewrite_to_new_ssa_names_bb (basic_block, struct htab *);
+ extern void rewrite_to_new_ssa_names (basic_block *, unsigned, htab_t);
+ extern void allocate_ssa_names (bitmap, struct htab **);
extern bool tree_purge_dead_eh_edges (basic_block);
extern bool tree_purge_all_dead_eh_edges (bitmap);
extern tree gimplify_val (block_stmt_iterator *, tree, tree);
*************** tree can_count_iv_in_wider_type (struct
*** 647,652 ****
--- 655,677 ----
void free_numbers_of_iterations_estimates (struct loops *);
void loop_commit_inserts (void);
bool for_each_index (tree *, bool (*) (tree, tree *, void *), void *);
+ void rewrite_into_loop_closed_ssa (void);
+ void verify_loop_closed_ssa (void);
+ bool tree_duplicate_loop_to_header_edge (struct loop *, edge, struct loops *,
+ unsigned int, sbitmap,
+ edge, edge *,
+ unsigned int *, int);
+ struct loop *tree_split_loop_iterations (struct loop *, edge, tree, struct loops *);
+ struct loop *tree_align_loop_iterations (struct loop *, edge, tree, unsigned,
+ struct loops *);
+ struct loop *tree_ssa_loop_version (struct loops *, struct loop *, tree,
+ basic_block *);
+ void split_loop_exit_edge (edge);
+ basic_block bsi_insert_on_edge_immediate_loop (edge, tree);
+ void create_iv (tree, tree, tree, struct loop *, block_stmt_iterator *, bool,
+ tree *, tree *);
+ void standard_iv_increment_position (struct loop *, block_stmt_iterator *,
+ bool *);
/* In tree-flow-inline.h */
static inline int phi_arg_from_edge (tree, edge);
*************** void vn_delete (void);
*** 685,690 ****
--- 710,719 ----
/* In tree-sra.c */
void insert_edge_copies (tree stmt, basic_block bb);
+ /* In gimplify.c */
+
+ tree force_gimple_operand (tree, tree *, bool, tree);
+
#include "tree-flow-inline.h"
#endif /* _TREE_FLOW_H */
Index: tree-ssa-loop-ch.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-ch.c,v
retrieving revision 2.3
diff -c -3 -p -r2.3 tree-ssa-loop-ch.c
*** tree-ssa-loop-ch.c 4 Aug 2004 20:37:38 -0000 2.3
--- tree-ssa-loop-ch.c 5 Aug 2004 12:37:05 -0000
*************** should_duplicate_loop_header_p (basic_bl
*** 99,158 ****
return true;
}
- /* Duplicates destinations of edges in BBS_TO_DUPLICATE. */
-
- static void
- duplicate_blocks (varray_type bbs_to_duplicate)
- {
- unsigned i;
- edge preheader_edge, e, e1;
- basic_block header, new_header;
- tree phi, new_phi, var;
-
- /* TODO: It should be quite easy to keep the dominance information
- up-to-date. */
- free_dominance_info (CDI_DOMINATORS);
-
- for (i = 0; i < VARRAY_ACTIVE_SIZE (bbs_to_duplicate); i++)
- {
- preheader_edge = VARRAY_GENERIC_PTR_NOGC (bbs_to_duplicate, i);
- header = preheader_edge->dest;
-
- if (!header->aux)
- abort ();
- header->aux = NULL;
-
- new_header = duplicate_block (header, preheader_edge);
-
- /* Create the phi nodes on on entry to new_header. */
- for (phi = phi_nodes (header), var = PENDING_STMT (preheader_edge);
- phi;
- phi = TREE_CHAIN (phi), var = TREE_CHAIN (var))
- {
- new_phi = create_phi_node (PHI_RESULT (phi), new_header);
- add_phi_arg (&new_phi, TREE_VALUE (var), preheader_edge);
- }
- PENDING_STMT (preheader_edge) = NULL;
-
- /* Add the phi arguments to the outgoing edges. */
- for (e = header->succ; e; e = e->succ_next)
- {
- for (e1 = new_header->succ; e1->dest != e->dest; e1 = e1->succ_next)
- continue;
-
- for (phi = phi_nodes (e->dest); phi; phi = TREE_CHAIN (phi))
- {
- tree def = PHI_ARG_DEF_FROM_EDGE (phi, e);
- add_phi_arg (&phi, def, e1);
- }
- }
- }
-
- calculate_dominance_info (CDI_DOMINATORS);
-
- rewrite_ssa_into_ssa ();
- }
-
/* Checks whether LOOP is a do-while style loop. */
static bool
--- 99,104 ----
*************** copy_loop_headers (void)
*** 185,196 ****
unsigned i;
struct loop *loop;
basic_block header;
! edge preheader_edge;
! varray_type bbs_to_duplicate = NULL;
loops = loop_optimizer_init (dump_file);
if (!loops)
return;
/* We do not try to keep the information about irreducible regions
up-to-date. */
--- 131,144 ----
unsigned i;
struct loop *loop;
basic_block header;
! edge exit;
! basic_block *bbs;
! unsigned n_bbs;
loops = loop_optimizer_init (dump_file);
if (!loops)
return;
+ rewrite_into_loop_closed_ssa ();
/* We do not try to keep the information about irreducible regions
up-to-date. */
*************** copy_loop_headers (void)
*** 200,213 ****
verify_loop_structure (loops);
#endif
for (i = 1; i < loops->num; i++)
{
/* Copy at most 20 insns. */
int limit = 20;
loop = loops->parray[i];
! preheader_edge = loop_preheader_edge (loop);
! header = preheader_edge->dest;
/* If the loop is already a do-while style one (either because it was
written as such, or because jump threading transformed it into one),
--- 148,162 ----
verify_loop_structure (loops);
#endif
+ bbs = xmalloc (sizeof (basic_block) * n_basic_blocks);
+
for (i = 1; i < loops->num; i++)
{
/* Copy at most 20 insns. */
int limit = 20;
loop = loops->parray[i];
! header = loop->header;
/* If the loop is already a do-while style one (either because it was
written as such, or because jump threading transformed it into one),
*************** copy_loop_headers (void)
*** 220,263 ****
like while (a && b) {...}, where we want to have both of the conditions
copied. TODO -- handle while (a || b) - like cases, by not requiring
the header to have just a single successor and copying up to
! postdominator.
!
! We do not really copy the blocks immediately, so that we do not have
! to worry about updating loop structures, and also so that we do not
! have to rewrite variables out of and into ssa form for each block.
! Instead we just record the block into worklist and duplicate all of
! them at once. */
while (should_duplicate_loop_header_p (header, loop, &limit))
{
- if (!bbs_to_duplicate)
- VARRAY_GENERIC_PTR_NOGC_INIT (bbs_to_duplicate, 10,
- "bbs_to_duplicate");
- VARRAY_PUSH_GENERIC_PTR_NOGC (bbs_to_duplicate, preheader_edge);
- header->aux = &header->aux;
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file,
- "Scheduled basic block %d for duplication.\n",
- header->index);
-
/* Find a successor of header that is inside a loop; i.e. the new
header after the condition is copied. */
if (flow_bb_inside_loop_p (loop, header->succ->dest))
! preheader_edge = header->succ;
else
! preheader_edge = header->succ->succ_next;
! header = preheader_edge->dest;
}
- }
! loop_optimizer_finalize (loops, NULL);
! if (bbs_to_duplicate)
! {
! duplicate_blocks (bbs_to_duplicate);
! VARRAY_FREE (bbs_to_duplicate);
}
/* Run cleanup_tree_cfg here regardless of whether we have done anything, so
that we cleanup the blocks created in order to get the loops into a
canonical shape. */
--- 169,224 ----
like while (a && b) {...}, where we want to have both of the conditions
copied. TODO -- handle while (a || b) - like cases, by not requiring
the header to have just a single successor and copying up to
! postdominator. */
!
! exit = NULL;
! n_bbs = 0;
while (should_duplicate_loop_header_p (header, loop, &limit))
{
/* Find a successor of header that is inside a loop; i.e. the new
header after the condition is copied. */
if (flow_bb_inside_loop_p (loop, header->succ->dest))
! exit = header->succ;
else
! exit = header->succ->succ_next;
! bbs[n_bbs++] = header;
! header = exit->dest;
}
! if (!exit)
! continue;
! if (dump_file && (dump_flags & TDF_DETAILS))
! fprintf (dump_file,
! "Duplicating header of the loop %d up to edge %d->%d.\n",
! loop->num, exit->src->index, exit->dest->index);
!
! /* Ensure that the header will have just the latch as a predecessor
! inside the loop. */
! if (exit->dest->pred->pred_next)
! exit = loop_split_edge_with (exit, NULL)->succ;
!
! if (!tree_duplicate_sese_region (loop_preheader_edge (loop), exit,
! bbs, n_bbs, NULL))
! {
! fprintf (dump_file, "Duplication failed.\n");
! continue;
! }
!
! /* Ensure that the latch and the preheader is simple (we know that they
! are not now, since there was the loop exit condition. */
! loop_split_edge_with (loop_preheader_edge (loop), NULL);
! loop_split_edge_with (loop_latch_edge (loop), NULL);
}
+ free (bbs);
+
+ #ifdef ENABLE_CHECKING
+ verify_loop_closed_ssa ();
+ #endif
+
+ loop_optimizer_finalize (loops, NULL);
+
/* Run cleanup_tree_cfg here regardless of whether we have done anything, so
that we cleanup the blocks created in order to get the loops into a
canonical shape. */
*************** struct tree_opt_pass pass_ch =
*** 279,285 ****
NULL, /* next */
0, /* static_pass_number */
TV_TREE_CH, /* tv_id */
! PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
--- 240,246 ----
NULL, /* next */
0, /* static_pass_number */
TV_TREE_CH, /* tv_id */
! PROP_cfg | PROP_ssa, /* properties_required */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
Index: tree-ssa-loop-manip.c
===================================================================
RCS file: tree-ssa-loop-manip.c
diff -N tree-ssa-loop-manip.c
*** /dev/null 1 Jan 1970 00:00:00 -0000
--- tree-ssa-loop-manip.c 5 Aug 2004 12:37:05 -0000
***************
*** 0 ****
--- 1,1155 ----
+ /* High-level loop manipulation functions.
+ Copyright (C) 2004 Free Software Foundation, Inc.
+
+ This file is part of GCC.
+
+ GCC is free software; you can redistribute it and/or modify it
+ under the terms of the GNU General Public License as published by the
+ Free Software Foundation; either version 2, or (at your option) any
+ later version.
+
+ GCC is distributed in the hope that it will be useful, but WITHOUT
+ ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with GCC; see the file COPYING. If not, write to the Free
+ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+ 02111-1307, USA. */
+
+ #include "config.h"
+ #include "system.h"
+ #include "coretypes.h"
+ #include "tm.h"
+ #include "tree.h"
+ #include "rtl.h"
+ #include "tm_p.h"
+ #include "hard-reg-set.h"
+ #include "basic-block.h"
+ #include "output.h"
+ #include "diagnostic.h"
+ #include "tree-flow.h"
+ #include "tree-dump.h"
+ #include "timevar.h"
+ #include "cfgloop.h"
+ #include "tree-pass.h"
+ #include "cfglayout.h"
+ #include "tree-scalar-evolution.h"
+
+ /* Add exit phis for the USE on EXIT. */
+
+ static void
+ add_exit_phis_edge (basic_block exit, tree use)
+ {
+ tree phi, def_stmt = SSA_NAME_DEF_STMT (use);
+ basic_block def_bb = bb_for_stmt (def_stmt);
+ struct loop *def_loop;
+ edge e;
+
+ /* Check that some of the edges entering the EXIT block exits a loop in
+ that USE is defined. */
+ for (e = exit->pred; e; e = e->pred_next)
+ {
+ def_loop = find_common_loop (def_bb->loop_father, e->src->loop_father);
+ if (!flow_bb_inside_loop_p (def_loop, e->dest))
+ break;
+ }
+
+ if (!e)
+ return;
+
+ phi = create_phi_node (use, exit);
+
+ for (e = exit->pred; e; e = e->pred_next)
+ add_phi_arg (&phi, use, e);
+
+ SSA_NAME_DEF_STMT (use) = def_stmt;
+ }
+
+ /* Add exit phis for VAR that is used in LIVEIN.
+ Exits of the loops are stored in EXITS. */
+
+ static void
+ add_exit_phis_var (tree var, bitmap livein, bitmap exits)
+ {
+ bitmap def;
+ int index;
+ basic_block def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
+
+ bitmap_clear_bit (livein, def_bb->index);
+
+ def = BITMAP_XMALLOC ();
+ bitmap_set_bit (def, def_bb->index);
+ compute_global_livein (livein, def);
+ BITMAP_XFREE (def);
+
+ EXECUTE_IF_AND_IN_BITMAP (exits, livein, 0, index,
+ add_exit_phis_edge (BASIC_BLOCK (index), var));
+ }
+
+ /* Add exit phis for the names marked in NAMES_TO_RENAME.
+ Exits of the loops are stored in EXITS. Sets of blocks where the ssa
+ names are used are stored in USE_BLOCKS. */
+
+ static void
+ add_exit_phis (bitmap names_to_rename, bitmap *use_blocks, bitmap loop_exits)
+ {
+ unsigned i;
+
+ EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i,
+ {
+ add_exit_phis_var (ssa_name (i), use_blocks[i], loop_exits);
+ });
+ }
+
+ /* Returns a bitmap of all loop exit edge targets. */
+
+ static bitmap
+ get_loops_exits (void)
+ {
+ bitmap exits = BITMAP_XMALLOC ();
+ basic_block bb;
+ edge e;
+
+ FOR_EACH_BB (bb)
+ {
+ for (e = bb->pred; e; e = e->pred_next)
+ if (e->src != ENTRY_BLOCK_PTR
+ && !flow_bb_inside_loop_p (e->src->loop_father, bb))
+ {
+ bitmap_set_bit (exits, bb->index);
+ break;
+ }
+ }
+
+ return exits;
+ }
+
+ /* For USE in BB, if it is used outside of the loop it is defined in,
+ mark it for rewrite. Record basic block BB where it is used
+ to USE_BLOCKS. */
+
+ static void
+ find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks)
+ {
+ unsigned ver;
+ basic_block def_bb;
+ struct loop *def_loop;
+
+ if (TREE_CODE (use) != SSA_NAME)
+ return;
+
+ ver = SSA_NAME_VERSION (use);
+ def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (use));
+ if (!def_bb)
+ return;
+ def_loop = def_bb->loop_father;
+
+ /* If the definition is not inside loop, it is not interesting. */
+ if (!def_loop->outer)
+ return;
+
+ if (!use_blocks[ver])
+ use_blocks[ver] = BITMAP_XMALLOC ();
+ bitmap_set_bit (use_blocks[ver], bb->index);
+
+ if (!flow_bb_inside_loop_p (def_loop, bb))
+ mark_for_rewrite (use);
+ }
+
+ /* For uses in STMT, mark names that are used outside of the loop they are
+ defined to rewrite. Record the set of blocks in that the ssa
+ names are defined to USE_BLOCKS. */
+
+ static void
+ find_uses_to_rename_stmt (tree stmt, bitmap *use_blocks)
+ {
+ use_optype uses;
+ vuse_optype vuses;
+ v_may_def_optype v_may_defs;
+ stmt_ann_t ann;
+ unsigned i;
+ basic_block bb = bb_for_stmt (stmt);
+
+ get_stmt_operands (stmt);
+ ann = stmt_ann (stmt);
+
+ uses = USE_OPS (ann);
+ for (i = 0; i < NUM_USES (uses); i++)
+ find_uses_to_rename_use (bb, USE_OP (uses, i), use_blocks);
+
+ vuses = VUSE_OPS (ann);
+ for (i = 0; i < NUM_VUSES (vuses); i++)
+ find_uses_to_rename_use (bb, VUSE_OP (vuses, i),use_blocks);
+
+ v_may_defs = V_MAY_DEF_OPS (ann);
+ for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
+ find_uses_to_rename_use (bb, V_MAY_DEF_OP (v_may_defs, i), use_blocks);
+ }
+
+ /* Marks names that are used outside of the loop they are defined in
+ for rewrite. Records the set of blocks in that the ssa
+ names are defined to USE_BLOCKS. */
+
+ static void
+ find_uses_to_rename (bitmap *use_blocks)
+ {
+ basic_block bb;
+ block_stmt_iterator bsi;
+ tree phi;
+ unsigned i;
+
+ FOR_EACH_BB (bb)
+ {
+ for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
+ for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
+ find_uses_to_rename_use (PHI_ARG_EDGE (phi, i)->src,
+ PHI_ARG_DEF (phi, i), use_blocks);
+
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ find_uses_to_rename_stmt (bsi_stmt (bsi), use_blocks);
+ }
+ }
+
+ /* Rewrites the program into a loop closed ssa form -- i.e. inserts extra
+ phi nodes to ensure that no variable is used outside the loop it is
+ defined in.
+
+ This strengthening of the basic ssa form has several advantages:
+
+ 1) Updating it during unrolling/peeling/versioning is trivial, since
+ we do not need to care about the uses outside of the loop.
+ 2) The behavior of all uses of an induction variable is the same.
+ Without this, you need to distinguish the case when the variable
+ is used outside of the loop it is defined in, for example
+
+ for (i = 0; i < 100; i++)
+ {
+ for (j = 0; j < 100; j++)
+ {
+ k = i + j;
+ use1 (k);
+ }
+ use2 (k);
+ }
+
+ Looking from the outer loop with the normal SSA form, the first use of k
+ is not well-behaved, while the second one is an induction variable with
+ base 99 and step 1. */
+
+ void
+ rewrite_into_loop_closed_ssa (void)
+ {
+ bitmap loop_exits = get_loops_exits ();
+ bitmap *use_blocks;
+ unsigned i;
+ bitmap names_to_rename;
+
+ if (any_marked_for_rewrite_p ())
+ abort ();
+
+ use_blocks = xcalloc (num_ssa_names, sizeof (bitmap));
+
+ /* Find the uses outside loops. */
+ find_uses_to_rename (use_blocks);
+
+ /* Add the phi nodes on exits of the loops for the names we need to
+ rewrite. */
+ names_to_rename = marked_ssa_names ();
+ add_exit_phis (names_to_rename, use_blocks, loop_exits);
+
+ for (i = 0; i < num_ssa_names; i++)
+ BITMAP_XFREE (use_blocks[i]);
+ free (use_blocks);
+ BITMAP_XFREE (loop_exits);
+ BITMAP_XFREE (names_to_rename);
+
+ /* Do the rewriting. */
+ rewrite_ssa_into_ssa ();
+ }
+
+ /* Check invariants of the loop closed ssa form for the USE in BB. */
+
+ static void
+ check_loop_closed_ssa_use (basic_block bb, tree use)
+ {
+ tree def;
+ basic_block def_bb;
+
+ if (TREE_CODE (use) != SSA_NAME)
+ return;
+
+ def = SSA_NAME_DEF_STMT (use);
+ def_bb = bb_for_stmt (def);
+ if (def_bb
+ && !flow_bb_inside_loop_p (def_bb->loop_father, bb))
+ abort ();
+ }
+
+ /* Checks invariants of loop closed ssa form in statement STMT in BB. */
+
+ static void
+ check_loop_closed_ssa_stmt (basic_block bb, tree stmt)
+ {
+ use_optype uses;
+ vuse_optype vuses;
+ v_may_def_optype v_may_defs;
+ stmt_ann_t ann;
+ unsigned i;
+
+ get_stmt_operands (stmt);
+ ann = stmt_ann (stmt);
+
+ uses = USE_OPS (ann);
+ for (i = 0; i < NUM_USES (uses); i++)
+ check_loop_closed_ssa_use (bb, USE_OP (uses, i));
+
+ vuses = VUSE_OPS (ann);
+ for (i = 0; i < NUM_VUSES (vuses); i++)
+ check_loop_closed_ssa_use (bb, VUSE_OP (vuses, i));
+
+ v_may_defs = V_MAY_DEF_OPS (ann);
+ for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
+ check_loop_closed_ssa_use (bb, V_MAY_DEF_OP (v_may_defs, i));
+ }
+
+ /* Checks that invariants of the loop closed ssa form are preserved. */
+
+ void
+ verify_loop_closed_ssa (void)
+ {
+ basic_block bb;
+ block_stmt_iterator bsi;
+ tree phi;
+ unsigned i;
+
+ verify_ssa ();
+
+ FOR_EACH_BB (bb)
+ {
+ for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
+ for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
+ check_loop_closed_ssa_use (PHI_ARG_EDGE (phi, i)->src,
+ PHI_ARG_DEF (phi, i));
+
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ check_loop_closed_ssa_stmt (bb, bsi_stmt (bsi));
+ }
+ }
+
+ /* Copies phi node arguments for duplicated blocks. The index of the first
+ duplicated block is FIRST_NEW_BLOCK. */
+
+ static void
+ copy_phi_node_args (unsigned first_new_block)
+ {
+ unsigned i;
+
+ for (i = first_new_block; i < (unsigned) last_basic_block; i++)
+ BASIC_BLOCK (i)->rbi->duplicated = 1;
+
+ for (i = first_new_block; i < (unsigned) last_basic_block; i++)
+ add_phi_args_after_copy_bb (BASIC_BLOCK (i));
+
+ for (i = first_new_block; i < (unsigned) last_basic_block; i++)
+ BASIC_BLOCK (i)->rbi->duplicated = 0;
+ }
+
+ /* Renames variables in the area copied by tree_duplicate_loop_to_header_edge.
+ FIRST_NEW_BLOCK is the first block in the copied area. DEFINITIONS is
+ a bitmap of all ssa names defined inside the loop. */
+
+ static void
+ rename_variables (unsigned first_new_block, bitmap definitions)
+ {
+ unsigned i, copy_number = 0;
+ basic_block bb;
+ htab_t ssa_name_map = NULL;
+
+ for (i = first_new_block; i < (unsigned) last_basic_block; i++)
+ {
+ bb = BASIC_BLOCK (i);
+
+ /* We assume that first come all blocks from the first copy, then all
+ blocks from the second copy, etc. */
+ if (copy_number != (unsigned) bb->rbi->copy_number)
+ {
+ allocate_ssa_names (definitions, &ssa_name_map);
+ copy_number = bb->rbi->copy_number;
+ }
+
+ rewrite_to_new_ssa_names_bb (bb, ssa_name_map);
+ }
+
+ htab_delete (ssa_name_map);
+ }
+
+ /* Sets SSA_NAME_DEF_STMT for results of all phi nodes in BB. */
+
+ static void
+ set_phi_def_stmts (basic_block bb)
+ {
+ tree phi;
+
+ for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
+ SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = phi;
+ }
+
+ /* The same ad cfgloopmanip.c:duplicate_loop_to_header_edge, but also updates
+ ssa. In order to achieve this, only loops whose exits all lead to the same
+ location are handled.
+
+ FIXME: we create some degenerate phi nodes that could be avoided by copy
+ propagating them instead. Unfortunately this is not completely
+ straightforward due to problems with constant folding. */
+
+ bool
+ tree_duplicate_loop_to_header_edge (struct loop *loop, edge e,
+ struct loops *loops,
+ unsigned int ndupl, sbitmap wont_exit,
+ edge orig, edge *to_remove,
+ unsigned int *n_to_remove, int flags)
+ {
+ unsigned first_new_block;
+ basic_block bb;
+ unsigned i;
+ tree phi, arg, map, def;
+ bitmap definitions;
+
+ if (!(loops->state & LOOPS_HAVE_SIMPLE_LATCHES))
+ return false;
+ if (!(loops->state & LOOPS_HAVE_PREHEADERS))
+ return false;
+
+ #ifdef ENABLE_CHECKING
+ verify_loop_closed_ssa ();
+ #endif
+
+ if (any_marked_for_rewrite_p ())
+ abort ();
+
+ first_new_block = last_basic_block;
+ if (!duplicate_loop_to_header_edge (loop, e, loops, ndupl, wont_exit,
+ orig, to_remove, n_to_remove, flags))
+ return false;
+
+ /* Readd the removed phi args for e. */
+ map = PENDING_STMT (e);
+ PENDING_STMT (e) = NULL;
+
+ for (phi = phi_nodes (e->dest), arg = map;
+ phi;
+ phi = TREE_CHAIN (phi), arg = TREE_CHAIN (arg))
+ {
+ def = TREE_VALUE (arg);
+ add_phi_arg (&phi, def, e);
+ }
+ if (arg)
+ abort ();
+
+ /* Copy the phi node arguments. */
+ copy_phi_node_args (first_new_block);
+
+ /* Rename the variables. */
+ definitions = marked_ssa_names ();
+ rename_variables (first_new_block, definitions);
+ unmark_all_for_rewrite ();
+ BITMAP_XFREE (definitions);
+
+ /* For some time we have the identical ssa names as results in multiple phi
+ nodes. When phi node is resized, it sets SSA_NAME_DEF_STMT of its result
+ to the new copy. This means that we cannot easily ensure that the ssa
+ names defined in those phis are pointing to the right one -- so just
+ recompute SSA_NAME_DEF_STMT for them. */
+
+ for (i = first_new_block; i < (unsigned) last_basic_block; i++)
+ {
+ bb = BASIC_BLOCK (i);
+ set_phi_def_stmts (bb);
+ if (bb->rbi->copy_number == 1)
+ set_phi_def_stmts (bb->rbi->original);
+ }
+
+ scev_reset ();
+ #ifdef ENABLE_CHECKING
+ verify_loop_closed_ssa ();
+ #endif
+
+ return true;
+ }
+
+ /*---------------------------------------------------------------------------
+ Loop versioning
+ ---------------------------------------------------------------------------*/
+
+ /* Adjust phi nodes for 'first' basic block. 'second' basic block is a copy
+ of 'first'. Both of them are dominated by 'new_head' basic block. When
+ 'new_head' was created by 'second's incoming edge it received phi arguments
+ on the edge by split_edge(). Later, additional edge 'e' was created to
+ connect 'new_head' and 'first'. Now this routine adds phi args on this
+ additional edge 'e' that new_head to second edge received as part of edge
+ splitting.
+ */
+
+ static void
+ lv_adjust_loop_header_phi (basic_block first, basic_block second,
+ basic_block new_head, edge e)
+ {
+ tree phi1, phi2;
+
+ /* Browse all 'second' basic block phi nodes and add phi args to
+ edge 'e' for 'first' head. PHI args are always in correct order. */
+
+ for (phi2 = phi_nodes (second), phi1 = phi_nodes (first);
+ phi2 && phi1;
+ phi2 = TREE_CHAIN (phi2), phi1 = TREE_CHAIN (phi1))
+ {
+ int i;
+ for (i = 0; i < PHI_NUM_ARGS (phi2); i++)
+ {
+ if (PHI_ARG_EDGE (phi2, i)->src == new_head)
+ {
+ tree def = PHI_ARG_DEF (phi2, i);
+ add_phi_arg (&phi1, def, e);
+ }
+ }
+ }
+ }
+
+ /* Adjust entry edge for lv.
+
+ e is a incoming edge.
+
+ --- edge e ---- > [second_head]
+
+ Split it and insert new conditional expression and adjust edges.
+
+ --- edge e ---> [cond expr] ---> [first_head]
+ |
+ +---------> [second_head]
+
+ */
+
+ static basic_block
+ lv_adjust_loop_entry_edge (basic_block first_head,
+ basic_block second_head,
+ edge e,
+ tree cond_expr)
+ {
+ block_stmt_iterator bsi;
+ basic_block orig_head = e->src;
+ basic_block new_head = NULL;
+ tree goto1 = NULL_TREE;
+ tree goto2 = NULL_TREE;
+ tree new_cond_expr = NULL_TREE;
+ edge e0, e1;
+
+ /* Split edge 'e'. This will create a new basic block, where we can
+ insert conditional expr. */
+ new_head = split_edge (e);
+ set_immediate_dominator (CDI_DOMINATORS, new_head, orig_head);
+
+ /* Build new conditional expr */
+ goto1 = build1 (GOTO_EXPR, void_type_node, tree_block_label (first_head));
+ goto2 = build1 (GOTO_EXPR, void_type_node, tree_block_label (second_head));
+ new_cond_expr = build (COND_EXPR, void_type_node, cond_expr, goto1, goto2);
+
+ /* Add new cond. in new head. */
+ bsi = bsi_start (new_head);
+ bsi_insert_after (&bsi, new_cond_expr, BSI_NEW_STMT);
+
+ /* Adjust edges appropriately to connect new head with first head
+ as well as second head. */
+ e1 = make_edge (new_head, first_head, EDGE_TRUE_VALUE);
+ set_immediate_dominator (CDI_DOMINATORS, first_head, new_head);
+ make_edge (new_head, second_head, EDGE_FALSE_VALUE);
+ set_immediate_dominator (CDI_DOMINATORS, second_head, new_head);
+
+ /* Adjust loop header phi nodes. */
+ lv_adjust_loop_header_phi (first_head, second_head, new_head, e1);
+
+ /* When edge 'e' was split, it created a fall through edge
+ from new head to second head. Above created FALSE edge
+ from new head to second head and now we do not need the
+ fall through edge. */
+ for (e0 = new_head->succ; e0; e0 = e0->succ_next)
+ if (e0->dest == second_head)
+ e0->flags &= ~EDGE_FALLTHRU;
+
+ return new_head;
+ }
+
+ /* Add phi args using PENDINT_STMT list. */
+
+ static void
+ lv_update_pending_stmts (edge e)
+ {
+ basic_block dest;
+ tree phi, arg, def;
+
+ if (!PENDING_STMT (e))
+ return;
+
+ dest = e->dest;
+
+ for (phi = phi_nodes (dest), arg = PENDING_STMT (e);
+ phi;
+ phi = TREE_CHAIN (phi), arg = TREE_CHAIN (arg))
+ {
+ def = TREE_VALUE (arg);
+ add_phi_arg (&phi, def, e);
+ }
+
+ PENDING_STMT (e) = NULL;
+ }
+
+
+ /* Main entry point for Loop Versioning transformation.
+
+ This transformation given a condition and a loop, creates
+ -if (condition) { loop_copy1 } else { loop_copy2 },
+ where loop_copy1 is the loop transformed in one way, and loop_copy2
+ is the loop transformed in another way (or unchanged). 'condition'
+ may be a run time test for things that were not resolved by static
+ analysis (overlapping ranges (anti-aliasing), alignment, etc.). */
+
+ struct loop *
+ tree_ssa_loop_version (struct loops *loops, struct loop * loop,
+ tree cond_expr, basic_block *condition_bb)
+ {
+ edge entry, latch_edge, exit;
+ basic_block first_head, second_head;
+ int irred_flag;
+ struct loop *nloop;
+
+ /* CHECKME: Loop versioning does not handle nested loop at this point. */
+ if (loop->inner)
+ return NULL;
+
+ /* Record entry and latch edges for the loop */
+ entry = loop_preheader_edge (loop);
+
+ /* Note down head of loop as first_head. */
+ first_head = entry->dest;
+
+ /* Duplicate loop. */
+ irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP;
+ entry->flags &= ~EDGE_IRREDUCIBLE_LOOP;
+ if (!tree_duplicate_loop_to_header_edge (loop, entry, loops, 1,
+ NULL, NULL, NULL, NULL, 0))
+ {
+ entry->flags |= irred_flag;
+ return NULL;
+ }
+
+ /* After duplication entry edge now points to new loop head block.
+ Note down new head as second_head. */
+ second_head = entry->dest;
+
+ /* Split loop entry edge and insert new block with cond expr. */
+ *condition_bb = lv_adjust_loop_entry_edge (first_head, second_head, entry,
+ cond_expr);
+
+ latch_edge = loop->latch->rbi->copy->succ;
+ nloop = loopify (loops,
+ latch_edge,
+ loop->header->rbi->copy->pred,
+ *condition_bb,
+ false /* Do not redirect all edges. */);
+
+ exit = loop->single_exit;
+ if (exit)
+ nloop->single_exit = find_edge (exit->src->rbi->copy, exit->dest);
+
+ /* loopify redirected latch_edge. Update its PENDING_STMTS. */
+ lv_update_pending_stmts (latch_edge);
+
+ /* loopify redirected condition_bb's succ edge. Update its PENDING_STMTS. */
+ lv_update_pending_stmts (FALLTHRU_EDGE (*condition_bb));
+
+ /* Adjust irreducible flag. */
+ if (irred_flag)
+ {
+ (*condition_bb)->flags |= BB_IRREDUCIBLE_LOOP;
+ loop_preheader_edge (loop)->flags |= EDGE_IRREDUCIBLE_LOOP;
+ loop_preheader_edge (nloop)->flags |= EDGE_IRREDUCIBLE_LOOP;
+ (*condition_bb)->pred->flags |= EDGE_IRREDUCIBLE_LOOP;
+ }
+
+ /* At this point condition_bb is loop predheader with two successors,
+ first_head and second_head. Make sure that loop predheader has only
+ one successor. */
+ loop_split_edge_with (loop_preheader_edge (loop), NULL);
+ loop_split_edge_with (loop_preheader_edge (nloop), NULL);
+
+ return nloop;
+ }
+
+ /* Duplicates LOOP to the exit edge EXIT. The original loops exit condition
+ is changed to EXIT_ON. The newly created loop is returned. In case
+ duplication fails, NULL is returned instead.
+
+ This function preserves the semantics of the program iff
+ the original exit condition implies EXIT_ON.
+
+ For example
+
+ while (1)
+ {
+ before;
+ if (cond)
+ break;
+ after;
+ }
+
+ is transformed into
+
+ while (1)
+ {
+ before;
+ if (exit_on)
+ break;
+ after;
+ }
+
+ while (!cond)
+ {
+ after;
+ before;
+ } */
+
+ struct loop *
+ tree_split_loop_iterations (struct loop *loop, edge exit, tree exit_on,
+ struct loops *loops)
+ {
+ basic_block *bbs, *new_bbs, *doms, new_latch_orig;
+ struct loop *new_loop, *aloop;
+ block_stmt_iterator bsi;
+ tree stmt;
+ edge new_exit, e;
+ unsigned n_bbs, n_doms, i;
+ tree phi;
+ bitmap definitions_before, all_definitions;
+ unsigned exit_bb_index;
+ htab_t ssa_name_map = NULL;
+
+ if (any_marked_for_rewrite_p ())
+ abort ();
+
+ /* Check whether duplication is possible. */
+
+ if (!just_once_each_iteration_p (loop, exit->src))
+ return NULL;
+
+ if (loop->inner)
+ return NULL;
+
+ if (!can_duplicate_loop_p (loop))
+ return NULL;
+
+ /* Ensure that the exit is in a separate basic block. */
+ bsi = bsi_last (exit->src);
+ if (bsi_end_p (bsi))
+ return NULL;
+ stmt = bsi_stmt (bsi);
+ if (TREE_CODE (stmt) != COND_EXPR)
+ return NULL;
+ bsi_prev (&bsi);
+ if (!bsi_end_p (bsi))
+ {
+ stmt = bsi_stmt (bsi);
+ split_loop_bb (exit->src, stmt);
+ }
+
+ /* And that it has just a single predecessor that has just a single
+ successor, and that it contains no phi nodes. */
+ if (exit->src->pred->pred_next
+ || exit->src->pred->src->succ->succ_next
+ || phi_nodes (exit->src))
+ split_loop_bb (exit->src, NULL);
+ new_latch_orig = exit->src->pred->src;
+
+ /* The duplication itself. */
+ n_bbs = loop->num_nodes;
+ bbs = get_loop_body_in_dom_order (loop);
+ for (exit_bb_index = 0; bbs[exit_bb_index] != exit->src; exit_bb_index++)
+ continue;
+
+ if (loops->state & LOOPS_HAVE_MARKED_SINGLE_EXITS)
+ {
+ /* Exclude the EXIT from consideration for now, since it is not going to
+ be really duplicated. */
+ update_single_exits_after_duplication (bbs, exit_bb_index,
+ loop->outer);
+ update_single_exits_after_duplication (bbs + exit_bb_index + 1,
+ n_bbs - exit_bb_index - 1,
+ loop->outer);
+ }
+
+ new_loop = duplicate_loop (loops, loop, loop->outer);
+ new_bbs = xmalloc (sizeof (basic_block) * n_bbs);
+
+ copy_bbs (bbs, exit_bb_index, new_bbs, NULL, 0, NULL, loop->outer);
+ definitions_before = marked_ssa_names ();
+ copy_bbs (bbs + exit_bb_index, n_bbs - exit_bb_index, new_bbs + exit_bb_index,
+ &exit, 1, &new_exit, loop->outer);
+ all_definitions = marked_ssa_names ();
+
+ /* Due to copying the loop in two parts some edges were not redirected. */
+ redirect_edge_and_branch_force (new_latch_orig->rbi->copy->succ,
+ new_exit->src);
+ redirect_edge_and_branch_force (loop->latch->rbi->copy->succ,
+ loop->header->rbi->copy);
+
+ add_phi_args_after_copy (new_bbs, n_bbs);
+
+ set_immediate_dominator (CDI_DOMINATORS, new_exit->src, exit->src);
+ set_immediate_dominator (CDI_DOMINATORS, new_loop->header, new_loop->latch);
+ new_loop->header = new_exit->src;
+ new_loop->latch = new_latch_orig->rbi->copy;
+
+ if (loops->state & LOOPS_HAVE_MARKED_SINGLE_EXITS)
+ {
+ if (loop->single_exit == exit)
+ new_loop->single_exit = new_exit;
+
+ for (aloop = loop->outer;
+ !flow_bb_inside_loop_p (aloop, exit->dest);
+ aloop = aloop->outer)
+ if (aloop->single_exit == exit)
+ aloop->single_exit = new_exit;
+ }
+
+ redirect_edge_and_branch_force (exit, new_exit->src);
+ /* Forget the phi nodes on the exit of the original loop, since they are no
+ longer used. */
+ PENDING_STMT (exit) = NULL;
+
+ stmt = last_stmt (exit->src);
+ COND_EXPR_COND (stmt) = exit_on;
+ if (exit->flags & EDGE_FALSE_VALUE)
+ {
+ exit->flags &= ~EDGE_FALSE_VALUE;
+ exit->flags |= EDGE_TRUE_VALUE;
+
+ e = exit->src->succ;
+ if (e == exit)
+ e = e->succ_next;
+
+ exit->flags &= ~EDGE_TRUE_VALUE;
+ exit->flags |= EDGE_FALSE_VALUE;
+ }
+
+ /* Update the dominators. */
+ doms = xmalloc (sizeof (basic_block) * n_basic_blocks);
+ n_doms = get_dominated_by_region (CDI_DOMINATORS, bbs, n_bbs, doms);
+ iterate_fix_dominators (CDI_DOMINATORS, doms, n_doms);
+ free (doms);
+
+ /* Rewrite the ssa names in the copy of the loop. But first create the phi
+ nodes that transfer values from LOOP to NEW_LOOP. TODO -- for now we
+ transfer all values defined before the exit, it is sufficient to transfer
+ those that are used after the exit. */
+ EXECUTE_IF_SET_IN_BITMAP (definitions_before, 0, i,
+ {
+ phi = create_phi_node (ssa_name (i), new_loop->header);
+ add_phi_arg (&phi, ssa_name (i), new_loop->header->pred);
+ add_phi_arg (&phi, ssa_name (i), new_loop->header->pred->pred_next);
+ });
+ allocate_ssa_names (all_definitions, &ssa_name_map);
+ rewrite_to_new_ssa_names (new_bbs, exit_bb_index, ssa_name_map);
+ allocate_ssa_names (definitions_before, &ssa_name_map);
+ rewrite_to_new_ssa_names (new_bbs + exit_bb_index, n_bbs - exit_bb_index,
+ ssa_name_map);
+
+ /* Ensure that NEW_LOOP has a simple preheader. */
+ split_loop_exit_edge (exit);
+
+ #ifdef ENABLE_CHECKING
+ verify_dominators (CDI_DOMINATORS);
+ verify_loop_structure (loops);
+ verify_loop_closed_ssa ();
+ #endif
+
+ free (new_bbs);
+ free (bbs);
+
+ unmark_all_for_rewrite ();
+ BITMAP_XFREE (definitions_before);
+ BITMAP_XFREE (all_definitions);
+ htab_delete (ssa_name_map);
+
+ return new_loop;
+ }
+
+ /* Split loop exit edge EXIT. The things are a bit complicated by a need to
+ preserve the loop closed ssa form. */
+
+ void
+ split_loop_exit_edge (edge exit)
+ {
+ basic_block dest = exit->dest;
+ basic_block bb = loop_split_edge_with (exit, NULL);
+ tree phi, new_phi, new_name;
+ use_operand_p op_p;
+
+ for (phi = phi_nodes (dest); phi; phi = TREE_CHAIN (phi))
+ {
+ op_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, bb->succ);
+
+ new_name = duplicate_ssa_name (USE_FROM_PTR (op_p), NULL);
+ new_phi = create_phi_node (new_name, bb);
+ SSA_NAME_DEF_STMT (new_name) = new_phi;
+ add_phi_arg (&new_phi, USE_FROM_PTR (op_p), exit);
+ SET_USE (op_p, new_name);
+ }
+ }
+
+ /* Insert statement STMT to the edge E and update the loop structures.
+ Returns the newly created block (if any). */
+
+ basic_block
+ bsi_insert_on_edge_immediate_loop (edge e, tree stmt)
+ {
+ basic_block src, dest, new_bb;
+ struct loop *loop_c;
+
+ src = e->src;
+ dest = e->dest;
+
+ loop_c = find_common_loop (src->loop_father, dest->loop_father);
+
+ new_bb = bsi_insert_on_edge_immediate (e, stmt);
+
+ if (!new_bb)
+ return NULL;
+
+ add_bb_to_loop (new_bb, loop_c);
+ if (dest->loop_father->latch == src)
+ dest->loop_father->latch = new_bb;
+
+ return new_bb;
+ }
+
+ /* Ensure that the number of iterations of LOOP is divisible by MOD,
+ by moving a few last iterations to the new loop. EXIT is the exit edge
+ on that the new loop is created. NITER is the number of iterations
+ of the LOOP before it exits through EXIT. LOOPS is the loop tree.
+ MOD must be a power of two.
+
+ For example
+
+ while (1)
+ {
+ before;
+ if (cond)
+ break;
+ after;
+ }
+
+ is transformed into
+
+ niter1 = (niter + 1) & ~(mod - 1);
+ if (niter < mod - 1)
+ before;
+ else
+ {
+ while (1)
+ {
+ before;
+ if (--niter1 == 0)
+ break;
+ after;
+ }
+ }
+ while (!cond)
+ {
+ after;
+ before;
+ }
+ */
+
+ struct loop *
+ tree_align_loop_iterations (struct loop *loop, edge exit, tree niter,
+ unsigned mod, struct loops *loops)
+ {
+ tree niter1, stmts, type, tmod, niter_count, exit_cond_stmt;
+ tree var_base, exit_cond, init_cond, always_exit;
+ struct loop *new_loop;
+ block_stmt_iterator bsi;
+ bool after;
+ basic_block init_cond_bb;
+
+ /* MOD must be a power of two. */
+ if (mod & (mod - 1))
+ abort ();
+
+ /* Prepare the expression for # of iterations. */
+ type = TREE_TYPE (niter);
+ var_base = create_tmp_var (type, "unaligned_niter_tmp");
+ add_referenced_tmp_var (var_base);
+
+ niter = force_gimple_operand (unshare_expr (niter), &stmts, false, var_base);
+ if (stmts)
+ bsi_insert_on_edge_immediate_loop (loop_preheader_edge (loop),
+ stmts);
+
+ niter1 = build2 (PLUS_EXPR, type,
+ unshare_expr (niter), build_int_cst (type, 1));
+ tmod = fold (build1 (BIT_NOT_EXPR, type, build_int_cst (type, mod - 1)));
+ niter1 = build2 (BIT_AND_EXPR, type, niter1, tmod);
+ niter1 = fold (niter1);
+
+ var_base = create_tmp_var (type, "aligned_niter_tmp");
+ add_referenced_tmp_var (var_base);
+ niter1 = force_gimple_operand (niter1, &stmts, false, var_base);
+ if (stmts)
+ bsi_insert_on_edge_immediate_loop (loop_preheader_edge (loop),
+ stmts);
+
+ /* Prepare the counter of iterations of the loop. */
+ var_base = create_tmp_var (type, "align_niter_iv");
+ add_referenced_tmp_var (var_base);
+ standard_iv_increment_position (loop, &bsi, &after);
+ create_iv (niter1, build_int_cst (type, (HOST_WIDE_INT) -1),
+ var_base, loop, &bsi, after, &niter_count, NULL);
+
+ /* Split out the new loop and insert the niter1 != 1 exit condition to
+ the original loop. */
+ exit_cond = build2 (EQ_EXPR, boolean_type_node,
+ niter_count, build_int_cst (type, 1));
+ new_loop = tree_split_loop_iterations (loop, exit, exit_cond, loops);
+ if (!new_loop)
+ return NULL;
+
+ /* Use loop versioning to create the niter < mod - 1 guard. */
+ init_cond = build2 (GE_EXPR, boolean_type_node,
+ niter, build_int_cst (type, mod - 1));
+ tree_ssa_loop_version (loops, loop, init_cond, &init_cond_bb);
+
+ /* Make the "after" part of the second version of the loop
+ unreachable. */
+ if (exit->flags & EDGE_TRUE_VALUE)
+ always_exit = boolean_true_node;
+ else
+ always_exit = boolean_false_node;
+ exit_cond_stmt = last_stmt (exit->src->rbi->copy);
+ COND_EXPR_COND (exit_cond_stmt) = always_exit;
+
+ return new_loop;
+ }
+
+ /* Returns the basic block in that statements should be emitted for induction
+ variables incremented at the end of the LOOP. */
+
+ static basic_block
+ ip_end_pos (struct loop *loop)
+ {
+ return loop->latch;
+ }
+
+ /* Returns the basic block in that statements should be emitted for induction
+ variables incremented just before exit condition of a LOOP. */
+
+ static basic_block
+ ip_normal_pos (struct loop *loop)
+ {
+ tree last;
+ basic_block bb;
+ edge exit;
+
+ if (loop->latch->pred->pred_next)
+ return NULL;
+
+ bb = loop->latch->pred->src;
+ last = last_stmt (bb);
+ if (TREE_CODE (last) != COND_EXPR)
+ return NULL;
+
+ exit = bb->succ;
+ if (exit->dest == loop->latch)
+ exit = exit->succ_next;
+
+ if (flow_bb_inside_loop_p (loop, exit->dest))
+ return NULL;
+
+ return bb;
+ }
+
+ /* Stores the standard position for induction variable increment in LOOP
+ (just before the exit condition if it is available and latch block is empty,
+ end of the latch block otherwise) to BSI. INSERT_AFTER is set to true if
+ the increment should be inserted after *BSI. */
+
+ void
+ standard_iv_increment_position (struct loop *loop, block_stmt_iterator *bsi,
+ bool *insert_after)
+ {
+ basic_block bb = ip_normal_pos (loop), latch = ip_end_pos (loop);
+ tree last = last_stmt (latch);
+
+ if (!bb
+ || (last && TREE_CODE (last) != LABEL_EXPR))
+ {
+ *bsi = bsi_last (latch);
+ *insert_after = true;
+ }
+ else
+ {
+ *bsi = bsi_last (bb);
+ *insert_after = false;
+ }
+ }
+
+ /* Creates an induction variable with value BASE + STEP * iteration in LOOP.
+ It is expected that neither BASE nor STEP are shared with other expressions
+ (unless the sharing rules allow this). Use VAR as a base var_decl for it
+ (if NULL, a new temporary will be created). The increment will occur at
+ INCR_POS (after it if AFTER is true, before it otherwise). The ssa versions
+ of the variable before and after increment will be stored in VAR_BEFORE and
+ VAR_AFTER (unless they are NULL). */
+
+ void
+ create_iv (tree base, tree step, tree var, struct loop *loop,
+ block_stmt_iterator *incr_pos, bool after,
+ tree *var_before, tree *var_after)
+ {
+ tree stmt, stmts, initial;
+ tree vb, va;
+
+ if (!var)
+ {
+ var = create_tmp_var (TREE_TYPE (base), "ivtmp");
+ add_referenced_tmp_var (var);
+ }
+
+ vb = make_ssa_name (var, NULL_TREE);
+ if (var_before)
+ *var_before = vb;
+ va = make_ssa_name (var, NULL_TREE);
+ if (var_after)
+ *var_after = va;
+
+ stmt = build (MODIFY_EXPR, void_type_node, va,
+ build (PLUS_EXPR, TREE_TYPE (base),
+ vb, step));
+ SSA_NAME_DEF_STMT (va) = stmt;
+ if (after)
+ bsi_insert_after (incr_pos, stmt, BSI_NEW_STMT);
+ else
+ bsi_insert_before (incr_pos, stmt, BSI_NEW_STMT);
+
+ initial = force_gimple_operand (base, &stmts, false, var);
+ if (stmts)
+ {
+ edge pe = loop_preheader_edge (loop);
+
+ bsi_insert_on_edge_immediate_loop (pe, stmts);
+ }
+
+ stmt = create_phi_node (vb, loop->header);
+ SSA_NAME_DEF_STMT (vb) = stmt;
+ add_phi_arg (&stmt, initial, loop_preheader_edge (loop));
+ add_phi_arg (&stmt, va, loop_latch_edge (loop));
+ }
Index: tree.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.c,v
retrieving revision 1.407
diff -c -3 -p -r1.407 tree.c
*** tree.c 5 Aug 2004 09:03:29 -0000 1.407
--- tree.c 5 Aug 2004 12:37:05 -0000
*************** build_int_2 (unsigned HOST_WIDE_INT low,
*** 435,440 ****
--- 435,467 ----
return t;
}
+ /* Builds integer constant of type TYPE and value VAL. */
+
+ tree
+ build_int_cst (tree type, unsigned HOST_WIDE_INT val)
+ {
+ unsigned bits = TYPE_PRECISION (type);
+ bool signed_p = !TYPE_UNSIGNED (type);
+ bool negative = ((val >> (bits - 1)) & 1) != 0;
+ tree ival;
+
+ if (bits > HOST_BITS_PER_WIDE_INT)
+ abort ();
+
+ if (signed_p && negative)
+ {
+ val = val | (~(unsigned HOST_WIDE_INT) 0 << (bits - 1) << 1);
+ ival = build_int_2 (val, -1);
+ }
+ else
+ {
+ val = val & ~(~(unsigned HOST_WIDE_INT) 0 << (bits - 1) << 1);
+ ival = build_int_2 (val, 0);
+ }
+
+ return fold_convert (type, ival);
+ }
+
/* Return a new VECTOR_CST node whose type is TYPE and whose values
are in a list pointed by VALS. */
Index: tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.h,v
retrieving revision 1.582
diff -c -3 -p -r1.582 tree.h
*** tree.h 5 Aug 2004 09:03:31 -0000 1.582
--- tree.h 5 Aug 2004 12:37:05 -0000
*************** extern tree build_nonstandard_integer_ty
*** 3492,3497 ****
--- 3492,3498 ----
extern tree build_range_type (tree, tree, tree);
extern HOST_WIDE_INT int_cst_value (tree);
extern tree tree_fold_gcd (tree, tree);
+ extern tree build_int_cst (tree, unsigned HOST_WIDE_INT);
extern bool fields_compatible_p (tree, tree);
extern tree find_compatible_field (tree, tree);