This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.
| Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
|---|---|---|
| Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |
| Other format: | [Raw text] | |
On Thursday 29 September 2005 20:48, Kenneth Zadeck wrote:
regions3.diff
? gcc/regions.c
This file is missing...
This means you have to attach regions.c separately, or you have to "cvs add" the file and add "-N" to your "cvs diff" options.
Index: gcc/Makefile.in
Gr. Steven
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.1543
diff -u -p -r1.1543 Makefile.in
--- Makefile.in 28 Sep 2005 23:49:58 -0000 1.1543
+++ Makefile.in 29 Sep 2005 22:15:42 -0000
@@ -960,8 +960,8 @@ OBJS-common = \
insn-extract.o insn-opinit.o insn-output.o insn-peep.o insn-recog.o \
integrate.o intl.o jump.o langhooks.o lcm.o lists.o local-alloc.o \
loop.o mode-switching.o modulo-sched.o optabs.o options.o opts.o \
- params.o postreload.o postreload-gcse.o predict.o \
- insn-preds.o pointer-set.o \
+ params.o postreload.o postreload-gcse.o predict.o regions.o \
+ insn-preds.o pointer-set.o \
print-rtl.o print-tree.o profile.o value-prof.o var-tracking.o \
real.o recog.o reg-stack.o regclass.o regmove.o regrename.o \
reload.o reload1.o reorg.o resource.o rtl.o rtlanal.o rtl-error.o \
@@ -2339,6 +2339,9 @@ local-alloc.o : local-alloc.c $(CONFIG_H
$(RTL_H) $(FLAGS_H) $(REGS_H) hard-reg-set.h insn-config.h $(RECOG_H) \
output.h function.h $(INSN_ATTR_H) toplev.h except.h reload.h $(TM_P_H) \
$(GGC_H) $(INTEGRATE_H) timevar.h tree-pass.h
+regions.o : regions.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
+ $(CFGLOOP_H) $(BASIC_BLOCK_H) $(REGS_H) $(TM_H) $(RTL_H) \
+ bitmap.h $(DF_H)
bitmap.o : bitmap.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
$(FLAGS_H) $(GGC_H) gt-bitmap.h bitmap.h $(OBSTACK_H)
global.o : global.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/basic-block.h,v
retrieving revision 1.269
diff -u -p -r1.269 basic-block.h
--- basic-block.h 11 Jul 2005 13:31:41 -0000 1.269
+++ basic-block.h 29 Sep 2005 22:15:42 -0000
@@ -185,6 +185,165 @@ struct loops;
struct edge_prediction;
struct rtl_bb_info;
+/* Control flow analysis information. */
+
+enum region_type {
+ SINGLE_NODE_REGION, /* Regular basic block. */
+ ROOT_REGION, /* Entry region. */
+
+ IMPROPER_REGION, /* Various loops. */
+ REDUCED_LOOP_REGION, /* Generic reducible loop. */
+
+ BLOCK_REGION, /* Sequence of blocks. */
+
+ IF_EXIT_ELSE_REGION, /* Condition where one branch exits */
+ IF_THEN_EXIT_REGION, /* enclosing loop or root. */
+ BRANCH2_EXIT_REGION,
+
+ IF_THEN_ELSE_REGION, /* Standard conditional branch diamonds. */
+ DIAMOND_REGION,
+
+ COMPLEX_CASE_REGION, /* Complex cases for switch. */
+ SWITCH_REGION /* Switch region. */
+};
+
+/* IMPROPER_REGION has a set of entry and exit nodes. */
+struct improper_region_s {
+ /* The real entries to the region. */
+ int entry_count;
+ struct basic_block_def **entries;
+};
+
+/* For the IF_* regions, one of the arms corresponds EDGE_TRUE_VALUE
+ and the other to the edge with EDGE_FALSE_VALUE. BRANCH2 and
+ DIAMOND are used when we do not have that kind of information.
+ For the next 5 types, the conditional is the entry node of the region.
+ */
+
+/* The next three regions are for conditional branches where one of
+ the arms exits the current loop or returns and the other arm
+ remains within the loop. */
+struct if_exit_else_region_s {
+ struct basic_block_def *exit_region;
+ struct basic_block_def *else_region;
+ int num_loops_exited;
+};
+
+struct if_then_exit_region_s {
+ struct basic_block_def *then_region;
+ struct basic_block_def *exit_region;
+ int num_loops_exited;
+};
+
+struct branch2_exit_region_s {
+ struct basic_block_def *local_region;
+ struct basic_block_def *exit_region;
+ int num_loops_exited;
+};
+
+/* The next two regions are diamond shaped. */
+
+struct if_then_else_region_s {
+ struct basic_block_def *then_region;
+ struct basic_block_def *else_region;
+};
+
+/* This is the same as an IF_THEN_ELSE region but is created when the
+ cfg edges are not marked (as in the rtl part of the
+ compiler). There are other cases that will also not have a marking.
+ A common example will be if the condition is not a simple node, but
+ a two exit loop. If the two exits happen to join back together, a
+ diamond region will be formed.
+ */
+
+struct diamond_region_s {
+ struct basic_block_def *first_region;
+ struct basic_block_def *second_region;
+};
+
+/* The COMPLEX_CASE_REGION is generated when the case has been broken
+ into two pieces. There are three reasons why this might happen:
+
+ 1) This case has the previous case drop into it. When this
+ happens, critical edge splitting will insert a empty block between
+ the conditional and the code for the case. The empty block will be
+ the only entry in the vector ENTRY_CASES the FIRST_REGION and the
+ original case will be the CASE_REGION. The PREVIOUS_CASE is set to
+ point to the region that falls into this case.
+
+ 2) This case has a group of labels that point to it. In this case,
+ the critical edge splitting will also insert extra empty blocks
+ between the conditional and the CASE_REGION. All of those empty
+ blocks are gathered into a ENTRY_CASES vector. The PREVIOUS_CASE
+ will be NULL if there is no drop in.
+
+ 3) Both (1) and (2) happen for this case. When that happens, the
+ ENTRY_CASES will have more than one element and the PREVIOUS_CASE
+ will be not NULL. */
+struct complex_case_region_s {
+ struct basic_block_def *previous_region;
+ unsigned int entry_case_count;
+ struct basic_block_def ** entry_cases;
+ struct basic_block_def *case_region;
+};
+
+struct switch_region_s {
+ struct basic_block_def *condition;
+ unsigned int case_count;
+
+ /* The regular and return cases are vectors of vectors of arms.
+ Each inner vector contain one list of cases that all drop thru to
+ the next. The last one being the one with the break. To support
+ this, there is a vector of ints that say how many arms are in the
+ vec.*/
+ unsigned int regular_case_count_count;
+ unsigned int *regular_case_counts;
+ struct basic_block_def *** regular_cases;
+
+ unsigned int return_case_count_count;
+ unsigned int *return_case_counts;
+ struct basic_block_def *** return_cases;
+
+ /* For cases that loop exit, there is not enough structure to see if
+ any of them dropped down since all of these are technically
+ outside of the loop being analyzed. */
+ unsigned int exit_case_count;
+ struct basic_block_def ** exit_cases;
+};
+
+typedef union region_details_u_a {
+ struct improper_region_s improper_region;
+
+ struct if_exit_else_region_s if_exit_else_region;
+ struct if_then_exit_region_s if_then_exit_region;
+ struct branch2_exit_region_s branch2_exit_region;
+
+ struct if_then_else_region_s if_then_else_region;
+ struct diamond_region_s diamond_region;
+
+ struct complex_case_region_s complex_case_region;
+ struct switch_region_s switch_region;
+} region_details_u;
+
+/* This structure is allocated for all non regular basic blocks. */
+struct basic_block_region_def GTY(())
+{
+ enum region_type type;
+ struct basic_block_def *region_head;
+ struct basic_block_def *first_bb_in_region;
+ struct basic_block_def *last_bb_in_region;
+
+ /* The set of basic blocks in this region AND in all of the regions
+ with this region. */
+ bitmap basic_blocks_in_region;
+ /* The set of regions in this region AND in all of the regions with
+ this region. */
+ bitmap regions_in_region;
+ union region_details_u_a *GTY ((skip)) region_details;
+};
+
+typedef struct basic_block_region_def *basic_block_region;
+
/* A basic block is a sequence of instructions with only entry and
only one exit. If any one of the instructions are executed, they
will all be executed, and in sequence from first to last.
@@ -211,7 +370,7 @@ struct rtl_bb_info;
basic blocks. */
/* Basic block information indexed by block number. */
-struct basic_block_def GTY((chain_next ("%h.next_bb"), chain_prev ("%h.prev_bb")))
+struct basic_block_def GTY(())
{
/* Pointers to the first and last trees of the block. */
tree stmt_list;
@@ -233,6 +392,22 @@ struct basic_block_def GTY((chain_next (
struct basic_block_def *prev_bb;
struct basic_block_def *next_bb;
+ /* Parent, previous and next blocks in the current region chain. */
+ struct basic_block_def *parent_region;
+ struct basic_block_def *prev_bb_in_region;
+ struct basic_block_def *next_bb_in_region;
+
+ /* Preds and succs in the region graph. */
+ int num_region_preds;
+ int num_region_succs;
+ struct basic_block_def ** GTY ((skip (""))) region_preds;
+ struct basic_block_def ** GTY ((skip (""))) region_succs;
+
+ /* This field is null if this is a regular basic block. If this
+ basic_block is a region node, then this is a pointer to the
+ region information. */
+ struct basic_block_region_def *region_info;
+
union basic_block_il_dependent {
struct rtl_bb_info * GTY ((tag ("1"))) rtl;
} GTY ((desc ("((%1.flags & BB_RTL) != 0)"))) il;
@@ -246,7 +421,8 @@ struct basic_block_def GTY((chain_next (
/* Expected number of executions: calculated in profile.c. */
gcov_type count;
- /* The index of this block. */
+ /* The index of this block. ENTRY_BLOCK=0, EXIT_BLOCK=1, all other
+ regular blocks >1, all regions nodes <0. */
int index;
/* The loop depth of this block. */
@@ -362,9 +538,15 @@ struct control_flow_graph GTY(())
basic_block x_entry_block_ptr;
basic_block x_exit_block_ptr;
+ /* The entry node of the structure graph if it exists. */
+ basic_block x_root_block_ptr;
+
/* Index by basic block number, get basic block struct info. */
varray_type x_basic_block_info;
+ /* Number of region nodes in the structure graph. */
+ int x_n_region_blocks;
+
/* Number of basic blocks in this flow graph. */
int x_n_basic_blocks;
@@ -388,8 +570,10 @@ struct control_flow_graph GTY(())
/* Defines for accessing the fields of the CFG structure for function FN. */
#define ENTRY_BLOCK_PTR_FOR_FUNCTION(FN) ((FN)->cfg->x_entry_block_ptr)
#define EXIT_BLOCK_PTR_FOR_FUNCTION(FN) ((FN)->cfg->x_exit_block_ptr)
+#define ROOT_BLOCK_PTR_FOR_FUNCTION(FN) ((FN)->cfg->x_root_block_ptr)
#define basic_block_info_for_function(FN) ((FN)->cfg->x_basic_block_info)
#define n_basic_blocks_for_function(FN) ((FN)->cfg->x_n_basic_blocks)
+#define n_region_blocks_for_function(FN) ((FN)->cfg->x_n_region_blocks)
#define n_edges_for_function(FN) ((FN)->cfg->x_n_edges)
#define last_basic_block_for_function(FN) ((FN)->cfg->x_last_basic_block)
#define label_to_block_map_for_function(FN) ((FN)->cfg->x_label_to_block_map)
@@ -400,8 +584,10 @@ struct control_flow_graph GTY(())
/* Defines for textual backward source compatibility. */
#define ENTRY_BLOCK_PTR (cfun->cfg->x_entry_block_ptr)
#define EXIT_BLOCK_PTR (cfun->cfg->x_exit_block_ptr)
+#define ROOT_BLOCK_PTR (cfun->cfg->x_root_block_ptr)
#define basic_block_info (cfun->cfg->x_basic_block_info)
#define n_basic_blocks (cfun->cfg->x_n_basic_blocks)
+#define n_region_blocks (cfun->cfg->x_n_region_blocks)
#define n_edges (cfun->cfg->x_n_edges)
#define last_basic_block (cfun->cfg->x_last_basic_block)
#define label_to_block_map (cfun->cfg->x_label_to_block_map)
@@ -427,17 +613,36 @@ extern bool rediscover_loops_after_threa
#define FOR_EACH_BB_REVERSE(BB) FOR_EACH_BB_REVERSE_FN(BB, cfun)
+#define FOR_EACH_BB_IN_REGION(BB, REGION) \
+ for (BB= (REGION)->region_info->first_bb_in_region; BB; BB = BB->next_bb_in_region)
+
+#define FOR_EACH_BB_REVERSE_IN_REGION(BB, REGION) \
+ for (BB= (REGION)->region_info->last_bb_in_region; BB; BB = BB->prev_bb_in_region)
+
/* For iterating over insns in basic block. */
#define FOR_BB_INSNS(BB, INSN) \
for ((INSN) = BB_HEAD (BB); \
- (INSN) != NEXT_INSN (BB_END (BB)); \
+ (INSN) && (INSN) != NEXT_INSN (BB_END (BB)); \
(INSN) = NEXT_INSN (INSN))
+/* For iterating over insns in basic block when we might remove the
+ current insn. */
+#define FOR_BB_INSNS_SAFE(BB, INSN, CURR) \
+ for ((INSN) = BB_HEAD (BB), (CURR)=(INSN) ? NEXT_INSN ((INSN)): NULL; \
+ (INSN) && (INSN) != NEXT_INSN (BB_END (BB)); \
+ (INSN) = (CURR), (CURR) = (INSN) ? NEXT_INSN ((INSN)) : NULL)
+
+
#define FOR_BB_INSNS_REVERSE(BB, INSN) \
for ((INSN) = BB_END (BB); \
- (INSN) != PREV_INSN (BB_HEAD (BB)); \
+ (INSN) && (INSN) != PREV_INSN (BB_HEAD (BB)); \
(INSN) = PREV_INSN (INSN))
+#define FOR_BB_INSNS_REVERSE_SAFE(BB, INSN, CURR) \
+ for ((INSN) = BB_END (BB),(CURR)=(INSN) ? PREV_INSN ((INSN)) : NULL; \
+ (INSN) && (INSN) != PREV_INSN (BB_HEAD (BB)); \
+ (INSN) = (CURR), (CURR) = (INSN) ? PREV_INSN ((INSN)) : NULL)
+
/* Cycles through _all_ basic blocks, even the fake ones (entry and
exit block). */
@@ -467,11 +672,12 @@ extern bitmap_obstack reg_obstack;
#define BB_END(B) (B)->il.rtl->end_
/* Special block numbers [markers] for entry and exit. */
-#define ENTRY_BLOCK (-1)
-#define EXIT_BLOCK (-2)
+#define ENTRY_BLOCK (0)
+#define EXIT_BLOCK (1)
+
+/* The two blocks that are always in the cfg. */
+#define NUM_FIXED_BLOCKS (2)
-/* Special block number not valid for any block. */
-#define INVALID_BLOCK (-3)
#define BLOCK_NUM(INSN) (BLOCK_FOR_INSN (INSN)->index + 0)
#define set_block_for_insn(INSN, BB) (BLOCK_FOR_INSN (INSN) = BB)
@@ -989,6 +1195,24 @@ extern basic_block get_bb_original (basi
extern void set_bb_copy (basic_block, basic_block);
extern basic_block get_bb_copy (basic_block);
+
+/* In regions.c. */
+extern void create_regions (bool);
+extern void delete_regions (void);
+extern int split_blocks_for_regions (void);
+extern enum region_type get_region_type (basic_block);
+extern const char * get_region_type_name (enum region_type);
+extern void dump_structure_graph (void);
+extern void debug_region_bb (basic_block);
+extern bool single_block_region_p (basic_block);
+extern bool loop_region_p (basic_block);
+extern bool single_entry_region_p (basic_block);
+extern bool single_exit_region_p (basic_block);
+extern bool get_real_entry_blocks (basic_block, bitmap, bitmap);
+extern bool get_real_exit_blocks (basic_block, bitmap, bitmap);
+extern void get_real_blocks (basic_block, bitmap);
+
+
#include "cfghooks.h"
#endif /* GCC_BASIC_BLOCK_H */
Index: bb-reorder.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/bb-reorder.c,v
retrieving revision 1.113
diff -u -p -r1.113 bb-reorder.c
--- bb-reorder.c 20 Sep 2005 21:48:34 -0000 1.113
+++ bb-reorder.c 29 Sep 2005 22:15:42 -0000
@@ -1893,7 +1893,7 @@ reorder_basic_blocks (unsigned int flags
int i;
struct trace *traces;
- if (n_basic_blocks <= 1)
+ if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1)
return;
if (targetm.cannot_modify_jumps_p ())
@@ -1985,7 +1985,7 @@ duplicate_computed_gotos (void)
bitmap candidates;
int max_size;
- if (n_basic_blocks <= 1)
+ if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1)
return;
if (targetm.cannot_modify_jumps_p ())
@@ -2168,7 +2168,7 @@ partition_hot_cold_basic_blocks (void)
int n_crossing_edges;
int max_edges = 2 * last_basic_block;
- if (n_basic_blocks <= 1)
+ if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1)
return;
crossing_edges = xcalloc (max_edges, sizeof (edge));
@@ -2176,8 +2176,8 @@ partition_hot_cold_basic_blocks (void)
cfg_layout_initialize (0);
FOR_EACH_BB (cur_bb)
- if (cur_bb->index >= 0
- && cur_bb->next_bb->index >= 0)
+ if (cur_bb->index >= NUM_FIXED_BLOCKS
+ && cur_bb->next_bb->index >= NUM_FIXED_BLOCKS)
cur_bb->aux = cur_bb->next_bb;
find_rarely_executed_basic_blocks_and_crossing_edges (crossing_edges,
Index: bitmap.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/bitmap.c,v
retrieving revision 1.72
diff -u -p -r1.72 bitmap.c
--- bitmap.c 16 Aug 2005 00:13:16 -0000 1.72
+++ bitmap.c 29 Sep 2005 22:15:43 -0000
@@ -40,7 +40,7 @@ static void bitmap_element_free (bitmap,
static bitmap_element *bitmap_element_allocate (bitmap);
static int bitmap_element_zerop (bitmap_element *);
static void bitmap_element_link (bitmap, bitmap_element *);
-static bitmap_element *bitmap_elt_insert_after (bitmap, bitmap_element *);
+static bitmap_element *bitmap_elt_insert_after (bitmap, bitmap_element *, unsigned int);
static void bitmap_elt_clear_from (bitmap, bitmap_element *);
static bitmap_element *bitmap_find_bit (bitmap, unsigned int);
@@ -89,6 +89,8 @@ bitmap_element_free (bitmap head, bitmap
head->current = next != 0 ? next : prev;
if (head->current)
head->indx = head->current->indx;
+ else
+ head->indx = 0;
}
bitmap_elem_to_freelist (head, elt);
}
@@ -351,14 +353,18 @@ bitmap_element_link (bitmap head, bitmap
new element. */
static bitmap_element *
-bitmap_elt_insert_after (bitmap head, bitmap_element *elt)
+bitmap_elt_insert_after (bitmap head, bitmap_element *elt, unsigned int indx)
{
bitmap_element *node = bitmap_element_allocate (head);
+ node->indx = indx;
if (!elt)
{
if (!head->current)
- head->current = node;
+ {
+ head->current = node;
+ head->indx = indx;
+ }
node->next = head->first;
if (node->next)
node->next->prev = node;
@@ -521,6 +527,62 @@ bitmap_bit_p (bitmap head, int bit)
return (ptr->bits[word_num] >> bit_num) & 1;
}
+#if GCC_VERSION < 3400
+/* Table of number of set bits in a character, indexed by value of char. */
+static unsigned char popcount_table[] =
+{
+ 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
+ 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
+ 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
+ 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
+ 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
+ 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
+ 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
+ 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
+};
+
+static unsigned long
+bitmap_popcount (BITMAP_WORD a)
+{
+ unsigned long ret = 0;
+ unsigned i;
+
+ /* Just do this the table way for now */
+ for (i = 0; i < BITMAP_WORD_BITS; i+= 8)
+ ret += popcount_table[(a >> i) & 0xff];
+ return ret;
+}
+#endif
+/* Count the number of bits set in the bitmap, and return it. */
+
+unsigned long
+bitmap_count_bits (bitmap a)
+{
+ unsigned long count = 0;
+ bitmap_element *elt;
+ unsigned ix;
+
+ if (!a->first)
+ return 0;
+
+ for (elt = a->first; elt; elt = elt->next)
+ {
+ for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
+ {
+#if GCC_VERSION >= 3400
+ /* Note that popcountl matches BITMAP_WORD in type, so the actual size
+ of BITMAP_WORD is not material. */
+ count += __builtin_popcountl (elt->bits[ix]);
+#else
+ count += bitmap_popcount (elt->bits[ix]);
+#endif
+ }
+ }
+ return count;
+}
+
+
+
/* Return the bit number of the first set bit in the bitmap. The
bitmap must be non-empty. */
@@ -604,9 +666,9 @@ bitmap_and (bitmap dst, bitmap a, bitmap
BITMAP_WORD ior = 0;
if (!dst_elt)
- dst_elt = bitmap_elt_insert_after (dst, dst_prev);
-
- dst_elt->indx = a_elt->indx;
+ dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
+ else
+ dst_elt->indx = a_elt->indx;
for (ix = BITMAP_ELEMENT_WORDS; ix--;)
{
BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix];
@@ -700,9 +762,9 @@ bitmap_and_compl (bitmap dst, bitmap a,
{
/* Copy a_elt. */
if (!dst_elt)
- dst_elt = bitmap_elt_insert_after (dst, dst_prev);
-
- dst_elt->indx = a_elt->indx;
+ dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
+ else
+ dst_elt->indx = a_elt->indx;
memcpy (dst_elt->bits, a_elt->bits, sizeof (dst_elt->bits));
dst_prev = dst_elt;
dst_elt = dst_elt->next;
@@ -717,9 +779,9 @@ bitmap_and_compl (bitmap dst, bitmap a,
BITMAP_WORD ior = 0;
if (!dst_elt)
- dst_elt = bitmap_elt_insert_after (dst, dst_prev);
-
- dst_elt->indx = a_elt->indx;
+ dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
+ else
+ dst_elt->indx = a_elt->indx;
for (ix = BITMAP_ELEMENT_WORDS; ix--;)
{
BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
@@ -796,6 +858,75 @@ bitmap_and_compl_into (bitmap a, bitmap
return changed != 0;
}
+/* A = ~A & B. */
+
+void
+bitmap_compl_and_into (bitmap a, bitmap b)
+{
+ bitmap_element *a_elt = a->first;
+ bitmap_element *b_elt = b->first;
+ bitmap_element *a_prev = NULL;
+ bitmap_element *next;
+
+ gcc_assert (a != b);
+
+ if (bitmap_empty_p (a))
+ {
+ bitmap_copy (a, b);
+ return;
+ }
+ if (bitmap_empty_p (b))
+ {
+ bitmap_clear (a);
+ return;
+ }
+
+ while (a_elt || b_elt)
+ {
+ if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
+ {
+ /* A is before B. Remove A */
+ next = a_elt->next;
+ a_prev = a_elt->prev;
+ bitmap_element_free (a, a_elt);
+ a_elt = next;
+ }
+ else if (!a_elt || b_elt->indx < a_elt->indx)
+ {
+ /* B is before A. Copy B. */
+ next = bitmap_elt_insert_after (a, a_prev, b_elt->indx);
+ memcpy (next->bits, b_elt->bits, sizeof (next->bits));
+ a_prev = next;
+ b_elt = b_elt->next;
+ }
+ else
+ {
+ /* Matching elts, generate A = ~A & B. */
+ unsigned ix;
+ BITMAP_WORD ior = 0;
+
+ for (ix = BITMAP_ELEMENT_WORDS; ix--;)
+ {
+ BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix];
+ BITMAP_WORD r = b_elt->bits[ix] ^ cleared;
+
+ a_elt->bits[ix] = r;
+ ior |= r;
+ }
+ next = a_elt->next;
+ if (!ior)
+ bitmap_element_free (a, a_elt);
+ else
+ a_prev = a_elt;
+ a_elt = next;
+ b_elt = b_elt->next;
+ }
+ }
+ gcc_assert (!a->current == !a->first);
+ gcc_assert (!a->current || a->indx == a->current->indx);
+ return;
+}
+
/* DST = A | B. Return true if DST changes. */
bool
@@ -833,8 +964,9 @@ bitmap_ior (bitmap dst, bitmap a, bitmap
{
changed = true;
if (!dst_elt)
- dst_elt = bitmap_elt_insert_after (dst, dst_prev);
- dst_elt->indx = a_elt->indx;
+ dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
+ else
+ dst_elt->indx = a_elt->indx;
for (ix = BITMAP_ELEMENT_WORDS; ix--;)
{
BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
@@ -878,8 +1010,9 @@ bitmap_ior (bitmap dst, bitmap a, bitmap
{
changed = true;
if (!dst_elt)
- dst_elt = bitmap_elt_insert_after (dst, dst_prev);
- dst_elt->indx = src->indx;
+ dst_elt = bitmap_elt_insert_after (dst, dst_prev, src->indx);
+ else
+ dst_elt->indx = src->indx;
memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits));
}
@@ -917,9 +1050,7 @@ bitmap_ior_into (bitmap a, bitmap b)
if (!a_elt || b_elt->indx < a_elt->indx)
{
/* Copy b_elt. */
- bitmap_element *dst = bitmap_elt_insert_after (a, a_prev);
-
- dst->indx = b_elt->indx;
+ bitmap_element *dst = bitmap_elt_insert_after (a, a_prev, b_elt->indx);
memcpy (dst->bits, b_elt->bits, sizeof (dst->bits));
a_prev = dst;
b_elt = b_elt->next;
@@ -990,9 +1121,9 @@ bitmap_xor (bitmap dst, bitmap a, bitmap
BITMAP_WORD ior = 0;
if (!dst_elt)
- dst_elt = bitmap_elt_insert_after (dst, dst_prev);
-
- dst_elt->indx = a_elt->indx;
+ dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
+ else
+ dst_elt->indx = a_elt->indx;
for (ix = BITMAP_ELEMENT_WORDS; ix--;)
{
BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix];
@@ -1025,9 +1156,9 @@ bitmap_xor (bitmap dst, bitmap a, bitmap
}
if (!dst_elt)
- dst_elt = bitmap_elt_insert_after (dst, dst_prev);
-
- dst_elt->indx = src->indx;
+ dst_elt = bitmap_elt_insert_after (dst, dst_prev, src->indx);
+ else
+ dst_elt->indx = src->indx;
memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits));
dst_prev = dst_elt;
dst_elt = dst_elt->next;
@@ -1059,9 +1190,7 @@ bitmap_xor_into (bitmap a, bitmap b)
if (!a_elt || b_elt->indx < a_elt->indx)
{
/* Copy b_elt. */
- bitmap_element *dst = bitmap_elt_insert_after (a, a_prev);
-
- dst->indx = b_elt->indx;
+ bitmap_element *dst = bitmap_elt_insert_after (a, a_prev, b_elt->indx);
memcpy (dst->bits, b_elt->bits, sizeof (dst->bits));
a_prev = dst;
b_elt = b_elt->next;
Index: bitmap.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/bitmap.h,v
retrieving revision 1.58
diff -u -p -r1.58 bitmap.h
--- bitmap.h 25 Jun 2005 01:59:10 -0000 1.58
+++ bitmap.h 29 Sep 2005 22:15:43 -0000
@@ -102,6 +102,9 @@ extern bool bitmap_intersect_compl_p (bi
/* True if MAP is an empty bitmap. */
#define bitmap_empty_p(MAP) (!(MAP)->first)
+/* Count the number of bits set in the bitmap. */
+extern unsigned long bitmap_count_bits (bitmap);
+
/* Boolean operations on bitmaps. The _into variants are two operand
versions that modify the first source operand. The other variants
are three operand versions that to not destroy the source bitmaps.
@@ -110,6 +113,8 @@ extern void bitmap_and (bitmap, bitmap,
extern void bitmap_and_into (bitmap, bitmap);
extern void bitmap_and_compl (bitmap, bitmap, bitmap);
extern bool bitmap_and_compl_into (bitmap, bitmap);
+#define bitmap_compl_and(DST, A, B) bitmap_and_compl (DST, B, A)
+extern void bitmap_compl_and_into (bitmap, bitmap);
extern bool bitmap_ior (bitmap, bitmap, bitmap);
extern bool bitmap_ior_into (bitmap, bitmap);
extern void bitmap_xor (bitmap, bitmap, bitmap);
Index: bt-load.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/bt-load.c,v
retrieving revision 2.39
diff -u -p -r2.39 bt-load.c
--- bt-load.c 19 Jul 2005 04:08:27 -0000 2.39
+++ bt-load.c 29 Sep 2005 22:15:43 -0000
@@ -461,7 +461,7 @@ compute_defs_uses_and_gen (fibheap_t all
defs_uses_info info;
sbitmap_vector_zero (bb_gen, n_basic_blocks);
- for (i = 0; i < n_basic_blocks; i++)
+ for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++)
{
basic_block bb = BASIC_BLOCK (i);
int reg;
@@ -622,7 +622,7 @@ compute_kill (sbitmap *bb_kill, sbitmap
/* For each basic block, form the set BB_KILL - the set
of definitions that the block kills. */
sbitmap_vector_zero (bb_kill, n_basic_blocks);
- for (i = 0; i < n_basic_blocks; i++)
+ for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++)
{
for (regno = first_btr; regno <= last_btr; regno++)
if (TEST_HARD_REG_BIT (all_btrs, regno)
@@ -645,14 +645,14 @@ compute_out (sbitmap *bb_out, sbitmap *b
int changed;
sbitmap bb_in = sbitmap_alloc (max_uid);
- for (i = 0; i < n_basic_blocks; i++)
+ for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++)
sbitmap_copy (bb_out[i], bb_gen[i]);
changed = 1;
while (changed)
{
changed = 0;
- for (i = 0; i < n_basic_blocks; i++)
+ for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++)
{
sbitmap_union_of_preds (bb_in, bb_out, i);
changed |= sbitmap_union_of_diff_cg (bb_out[i], bb_gen[i],
@@ -671,7 +671,7 @@ link_btr_uses (btr_def *def_array, btr_u
/* Link uses to the uses lists of all of their reaching defs.
Count up the number of reaching defs of each use. */
- for (i = 0; i < n_basic_blocks; i++)
+ for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++)
{
basic_block bb = BASIC_BLOCK (i);
rtx insn;
@@ -1397,7 +1397,7 @@ migrate_btr_defs (enum reg_class btr_cla
{
int i;
- for (i = 0; i < n_basic_blocks; i++)
+ for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++)
{
basic_block bb = BASIC_BLOCK (i);
fprintf(dump_file,
Index: cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfg.c,v
retrieving revision 1.103
diff -u -p -r1.103 cfg.c
--- cfg.c 29 Jul 2005 14:51:57 -0000 1.103
+++ cfg.c 29 Sep 2005 22:15:43 -0000
@@ -163,8 +163,11 @@ compact_blocks (void)
int i;
basic_block bb;
- i = 0;
- FOR_EACH_BB (bb)
+ BASIC_BLOCK(ENTRY_BLOCK) = ENTRY_BLOCK_PTR;
+ BASIC_BLOCK(EXIT_BLOCK) = EXIT_BLOCK_PTR;
+
+ i = NUM_FIXED_BLOCKS;
+ FOR_EACH_BB (bb)
{
BASIC_BLOCK (i) = bb;
bb->index = i;
Index: cfganal.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfganal.c,v
retrieving revision 1.65
diff -u -p -r1.65 cfganal.c
--- cfganal.c 19 Jul 2005 04:08:27 -0000 1.65
+++ cfganal.c 29 Sep 2005 22:15:44 -0000
@@ -345,7 +345,7 @@ create_edge_list (void)
basic_block bb;
edge_iterator ei;
- block_count = n_basic_blocks + 2; /* Include the entry and exit blocks. */
+ block_count = n_basic_blocks; /* Include the entry and exit blocks. */
num_edges = 0;
@@ -391,7 +391,7 @@ print_edge_list (FILE *f, struct edge_li
int x;
fprintf (f, "Compressed edge list, %d BBs + entry & exit, and %d edges\n",
- elist->num_blocks - 2, elist->num_edges);
+ elist->num_blocks, elist->num_edges);
for (x = 0; x < elist->num_edges; x++)
{
@@ -721,7 +721,7 @@ flow_depth_first_order_compute (int *dfs
edge_iterator *stack;
int sp;
int dfsnum = 0;
- int rcnum = n_basic_blocks - 1;
+ int rcnum = n_basic_blocks - 1 - NUM_FIXED_BLOCKS;
sbitmap visited;
/* Allocate stack for back-tracking up CFG. */
@@ -786,8 +786,9 @@ flow_depth_first_order_compute (int *dfs
free (stack);
sbitmap_free (visited);
- /* The number of nodes visited should be the number of blocks. */
- gcc_assert (dfsnum == n_basic_blocks);
+ /* The number of nodes visited should be the number of blocks minus
+ the entry and exit blocks which are not visited here. */
+ gcc_assert (dfsnum == n_basic_blocks - NUM_FIXED_BLOCKS);
return dfsnum;
}
@@ -826,12 +827,11 @@ static void
flow_dfs_compute_reverse_init (depth_first_search_ds data)
{
/* Allocate stack for back-tracking up CFG. */
- data->stack = xmalloc ((n_basic_blocks - (INVALID_BLOCK + 1))
- * sizeof (basic_block));
+ data->stack = xmalloc (n_basic_blocks * sizeof (basic_block));
data->sp = 0;
/* Allocate bitmap to track nodes that have been visited. */
- data->visited_blocks = sbitmap_alloc (last_basic_block - (INVALID_BLOCK + 1));
+ data->visited_blocks = sbitmap_alloc (last_basic_block);
/* None of the nodes in the CFG have been visited yet. */
sbitmap_zero (data->visited_blocks);
@@ -847,7 +847,7 @@ static void
flow_dfs_compute_reverse_add_bb (depth_first_search_ds data, basic_block bb)
{
data->stack[data->sp++] = bb;
- SET_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK + 1));
+ SET_BIT (data->visited_blocks, bb->index);
}
/* Continue the depth-first search through the reverse graph starting with the
@@ -869,14 +869,13 @@ flow_dfs_compute_reverse_execute (depth_
/* Perform depth-first search on adjacent vertices. */
FOR_EACH_EDGE (e, ei, bb->preds)
- if (!TEST_BIT (data->visited_blocks,
- e->src->index - (INVALID_BLOCK + 1)))
+ if (!TEST_BIT (data->visited_blocks, e->src->index))
flow_dfs_compute_reverse_add_bb (data, e->src);
}
/* Determine if there are unvisited basic blocks. */
FOR_BB_BETWEEN (bb, last_unvisited, NULL, prev_bb)
- if (!TEST_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK + 1)))
+ if (!TEST_BIT (data->visited_blocks, bb->index))
return bb;
return NULL;
@@ -912,12 +911,12 @@ dfs_enumerate_from (basic_block bb, int
static sbitmap visited;
static unsigned v_size;
-#define MARK_VISITED(BB) (SET_BIT (visited, (BB)->index + 2))
-#define UNMARK_VISITED(BB) (RESET_BIT (visited, (BB)->index + 2))
-#define VISITED_P(BB) (TEST_BIT (visited, (BB)->index + 2))
+#define MARK_VISITED(BB) (SET_BIT (visited, (BB)->index))
+#define UNMARK_VISITED(BB) (RESET_BIT (visited, (BB)->index))
+#define VISITED_P(BB) (TEST_BIT (visited, (BB)->index))
/* Resize the VISITED sbitmap if necessary. */
- size = last_basic_block + 2;
+ size = last_basic_block;
if (size < 10)
size = 10;
Index: cfgbuild.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgbuild.c,v
retrieving revision 1.68
diff -u -p -r1.68 cfgbuild.c
--- cfgbuild.c 25 Jun 2005 01:59:28 -0000 1.68
+++ cfgbuild.c 29 Sep 2005 22:15:44 -0000
@@ -138,7 +138,7 @@ control_flow_insn_p (rtx insn)
static int
count_basic_blocks (rtx f)
{
- int count = 0;
+ int count = NUM_FIXED_BLOCKS;
bool saw_insn = false;
rtx insn;
@@ -164,10 +164,10 @@ count_basic_blocks (rtx f)
/* The rest of the compiler works a bit smoother when we don't have to
check for the edge case of do-nothing functions with no basic blocks. */
- if (count == 0)
+ if (count == NUM_FIXED_BLOCKS)
{
emit_insn (gen_rtx_USE (VOIDmode, const0_rtx));
- count = 1;
+ count = NUM_FIXED_BLOCKS + 1;
}
return count;
@@ -529,10 +529,11 @@ find_basic_blocks (rtx f)
}
n_basic_blocks = count_basic_blocks (f);
- last_basic_block = 0;
+ last_basic_block = NUM_FIXED_BLOCKS;
ENTRY_BLOCK_PTR->next_bb = EXIT_BLOCK_PTR;
EXIT_BLOCK_PTR->prev_bb = ENTRY_BLOCK_PTR;
+
/* Size the basic block table. The actual structures will be allocated
by find_basic_blocks_1, since we want to keep the structure pointers
stable across calls to find_basic_blocks. */
@@ -542,6 +543,8 @@ find_basic_blocks (rtx f)
actually lay them out. */
VARRAY_BB_INIT (basic_block_info, n_basic_blocks, "basic_block_info");
+ BASIC_BLOCK(ENTRY_BLOCK) = ENTRY_BLOCK_PTR;
+ BASIC_BLOCK(EXIT_BLOCK) = EXIT_BLOCK_PTR;
find_basic_blocks_1 (f);
Index: cfgcleanup.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgcleanup.c,v
retrieving revision 1.151
diff -u -p -r1.151 cfgcleanup.c
--- cfgcleanup.c 29 Jul 2005 00:45:57 -0000 1.151
+++ cfgcleanup.c 29 Sep 2005 22:15:44 -0000
@@ -444,7 +444,7 @@ try_forward_edges (int mode, basic_block
}
target = first = e->dest;
- counter = 0;
+ counter = NUM_FIXED_BLOCKS;
/* If we are partitioning hot/cold basic_blocks, we don't want to mess
up jumps that cross between hot/cold sections.
@@ -506,7 +506,7 @@ try_forward_edges (int mode, basic_block
if (t->dest == b)
break;
- gcc_assert (nthreaded_edges < n_basic_blocks);
+ gcc_assert (nthreaded_edges < n_basic_blocks - NUM_FIXED_BLOCKS);
threaded_edges[nthreaded_edges++] = t;
new_target = t->dest;
@@ -1905,7 +1905,7 @@ try_optimize_cfg (int mode)
/* Note that forwarder_block_p true ensures that
there is a successor for this block. */
&& (single_succ_edge (b)->flags & EDGE_FALLTHRU)
- && n_basic_blocks > 1)
+ && n_basic_blocks > NUM_FIXED_BLOCKS + 1)
{
if (dump_file)
fprintf (dump_file,
Index: cfghooks.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfghooks.c,v
retrieving revision 1.32
diff -u -p -r1.32 cfghooks.c
--- cfghooks.c 24 Aug 2005 07:56:51 -0000 1.32
+++ cfghooks.c 29 Sep 2005 22:15:45 -0000
@@ -77,8 +77,8 @@ verify_flow_info (void)
basic_block *last_visited;
timevar_push (TV_CFG_VERIFY);
- last_visited = xcalloc (last_basic_block + 2, sizeof (basic_block));
- edge_checksum = xcalloc (last_basic_block + 2, sizeof (size_t));
+ last_visited = xcalloc (last_basic_block, sizeof (basic_block));
+ edge_checksum = xcalloc (last_basic_block, sizeof (size_t));
/* Check bb chain & numbers. */
last_bb_seen = ENTRY_BLOCK_PTR;
@@ -122,7 +122,7 @@ verify_flow_info (void)
}
FOR_EACH_EDGE (e, ei, bb->succs)
{
- if (last_visited [e->dest->index + 2] == bb)
+ if (last_visited [e->dest->index] == bb)
{
error ("verify_flow_info: Duplicate edge %i->%i",
e->src->index, e->dest->index);
@@ -141,7 +141,7 @@ verify_flow_info (void)
err = 1;
}
- last_visited [e->dest->index + 2] = bb;
+ last_visited [e->dest->index] = bb;
if (e->flags & EDGE_FALLTHRU)
n_fallthru++;
@@ -158,7 +158,7 @@ verify_flow_info (void)
err = 1;
}
- edge_checksum[e->dest->index + 2] += (size_t) e;
+ edge_checksum[e->dest->index] += (size_t) e;
}
if (n_fallthru > 1)
{
@@ -192,7 +192,7 @@ verify_flow_info (void)
err = 1;
}
- edge_checksum[e->dest->index + 2] -= (size_t) e;
+ edge_checksum[e->dest->index] -= (size_t) e;
}
}
@@ -202,14 +202,14 @@ verify_flow_info (void)
edge_iterator ei;
FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
- edge_checksum[e->dest->index + 2] += (size_t) e;
+ edge_checksum[e->dest->index] += (size_t) e;
FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
- edge_checksum[e->dest->index + 2] -= (size_t) e;
+ edge_checksum[e->dest->index] -= (size_t) e;
}
FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
- if (edge_checksum[bb->index + 2])
+ if (edge_checksum[bb->index])
{
error ("basic block %i edge lists are corrupted", bb->index);
err = 1;
@@ -888,3 +888,22 @@ lv_add_condition_to_bb (basic_block firs
gcc_assert (cfg_hooks->lv_add_condition_to_bb);
cfg_hooks->lv_add_condition_to_bb (first, second, new, cond);
}
+
+
+/* Return true if BB contains only labels or non-executable
+ instructions */
+bool
+block_empty_p (basic_block bb)
+{
+ gcc_assert (cfg_hooks->block_empty_p);
+ return cfg_hooks->block_empty_p (bb);
+}
+
+/* Split a basic block if it ends with a conditional branch and if
+ the other part of the block is not empty. */
+basic_block
+split_block_before_cond_jump (basic_block bb)
+{
+ gcc_assert (cfg_hooks->split_block_before_cond_jump);
+ return cfg_hooks->split_block_before_cond_jump (bb);
+}
Index: cfghooks.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfghooks.h,v
retrieving revision 1.18
diff -u -p -r1.18 cfghooks.h
--- cfghooks.h 24 Aug 2005 07:56:52 -0000 1.18
+++ cfghooks.h 29 Sep 2005 22:15:45 -0000
@@ -135,6 +135,13 @@ struct cfg_hooks
/* Add PHI arguments queued in PENDINT_STMT list on edge E to edge
E->dest (only in tree-ssa loop versioning. */
void (*flush_pending_stmts) (edge);
+
+ /* True if a block contains no executable instructions. */
+ bool (*block_empty_p) (basic_block);
+
+ /* Split a basic block if it ends with a conditional branch and if
+ the other part of the block is not empty. */
+ basic_block (*split_block_before_cond_jump) (basic_block);
};
extern void verify_flow_info (void);
@@ -160,6 +167,8 @@ extern bool can_duplicate_block_p (basic
extern basic_block duplicate_block (basic_block, edge, basic_block);
extern bool block_ends_with_call_p (basic_block bb);
extern bool block_ends_with_condjump_p (basic_block bb);
+extern bool block_empty_p (basic_block);
+extern basic_block split_block_before_cond_jump (basic_block);
extern int flow_call_edges_add (sbitmap);
extern void execute_on_growing_pred (edge);
extern void execute_on_shrinking_pred (edge);
Index: cfglayout.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfglayout.c,v
retrieving revision 1.95
diff -u -p -r1.95 cfglayout.c
--- cfglayout.c 24 Aug 2005 07:56:53 -0000 1.95
+++ cfglayout.c 29 Sep 2005 22:15:45 -0000
@@ -601,7 +601,7 @@ fixup_reorder_chain (void)
/* First do the bulk reordering -- rechain the blocks without regard to
the needed changes to jumps and labels. */
- for (bb = ENTRY_BLOCK_PTR->next_bb, index = 0;
+ for (bb = ENTRY_BLOCK_PTR->next_bb, index = NUM_FIXED_BLOCKS;
bb != 0;
bb = bb->aux, index++)
{
@@ -818,7 +818,7 @@ fixup_reorder_chain (void)
if (dump_file)
{
fprintf (dump_file, "Reordered sequence:\n");
- for (bb = ENTRY_BLOCK_PTR->next_bb, index = 0;
+ for (bb = ENTRY_BLOCK_PTR->next_bb, index = NUM_FIXED_BLOCKS;
bb;
bb = bb->aux, index++)
{
@@ -837,7 +837,7 @@ fixup_reorder_chain (void)
prev_bb = ENTRY_BLOCK_PTR;
bb = ENTRY_BLOCK_PTR->next_bb;
- index = 0;
+ index = NUM_FIXED_BLOCKS;
for (; bb; prev_bb = bb, bb = bb->aux, index ++)
{
Index: cfgloop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloop.c,v
retrieving revision 1.54
diff -u -p -r1.54 cfgloop.c
--- cfgloop.c 3 Jul 2005 21:07:47 -0000 1.54
+++ cfgloop.c 29 Sep 2005 22:15:45 -0000
@@ -73,7 +73,7 @@ flow_loops_cfg_dump (const struct loops
if (loops->cfg.dfs_order)
{
fputs (";; DFS order: ", file);
- for (i = 0; i < n_basic_blocks; i++)
+ for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++)
fprintf (file, "%d ", loops->cfg.dfs_order[i]);
fputs ("\n", file);
@@ -83,7 +83,7 @@ flow_loops_cfg_dump (const struct loops
if (loops->cfg.rc_order)
{
fputs (";; RC order: ", file);
- for (i = 0; i < n_basic_blocks; i++)
+ for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++)
fprintf (file, "%d ", loops->cfg.rc_order[i]);
fputs ("\n", file);
@@ -610,7 +610,7 @@ flow_loops_find (struct loops *loops)
/* Taking care of this degenerate case makes the rest of
this code simpler. */
- if (n_basic_blocks == 0)
+ if (n_basic_blocks == NUM_FIXED_BLOCKS)
return 0;
dfs_order = NULL;
@@ -676,7 +676,7 @@ flow_loops_find (struct loops *loops)
loops->parray[0]->outer = NULL;
loops->parray[0]->depth = 0;
loops->parray[0]->pred = NULL;
- loops->parray[0]->num_nodes = n_basic_blocks + 2;
+ loops->parray[0]->num_nodes = n_basic_blocks;
loops->parray[0]->latch = EXIT_BLOCK_PTR;
loops->parray[0]->header = ENTRY_BLOCK_PTR;
ENTRY_BLOCK_PTR->loop_father = loops->parray[0];
@@ -704,7 +704,7 @@ flow_loops_find (struct loops *loops)
num_loops = 1;
- for (b = 0; b < n_basic_blocks; b++)
+ for (b = 0; b < n_basic_blocks - NUM_FIXED_BLOCKS; b++)
{
struct loop *loop;
edge_iterator ei;
@@ -804,7 +804,7 @@ get_loop_body (const struct loop *loop)
if (loop->latch == EXIT_BLOCK_PTR)
{
/* There may be blocks unreachable from EXIT_BLOCK. */
- gcc_assert (loop->num_nodes == (unsigned) n_basic_blocks + 2);
+ gcc_assert (loop->num_nodes == (unsigned) n_basic_blocks);
FOR_EACH_BB (bb)
tovisit[tv++] = bb;
tovisit[tv++] = EXIT_BLOCK_PTR;
Index: cfgloopmanip.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloopmanip.c,v
retrieving revision 1.53
diff -u -p -r1.53 cfgloopmanip.c
--- cfgloopmanip.c 24 Aug 2005 07:56:53 -0000 1.53
+++ cfgloopmanip.c 29 Sep 2005 22:15:46 -0000
@@ -1563,7 +1563,7 @@ fix_loop_structure (struct loops *loops,
}
/* Remove the dead loops from structures. */
- loops->tree_root->num_nodes = n_basic_blocks + 2;
+ loops->tree_root->num_nodes = n_basic_blocks;
for (i = 1; i < loops->num; i++)
{
loop = loops->parray[i];
Index: cfgrtl.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgrtl.c,v
retrieving revision 1.181
diff -u -p -r1.181 cfgrtl.c
--- cfgrtl.c 28 Jul 2005 21:11:30 -0000 1.181
+++ cfgrtl.c 29 Sep 2005 22:15:46 -0000
@@ -82,6 +82,51 @@ static int rtl_verify_flow_info_1 (void)
static void mark_killed_regs (rtx, rtx, void *);
static void rtl_make_forwarder_block (edge);
+
+/* Return true if BB contains only labels or non-executable
+ instructions */
+
+static bool
+rtl_block_empty_p (basic_block bb)
+{
+ rtx insn;
+ if (BB_HEAD (bb))
+ FOR_BB_INSNS (bb, insn)
+ {
+ if (!NOTE_P (insn) && !any_uncondjump_p (insn))
+ return false;
+ }
+ return true;
+}
+
+/* Split a basic block if it ends with a conditional branch and if
+ the other part of the block is not empty. */
+
+static basic_block
+rtl_split_block_before_cond_jump (basic_block bb)
+{
+ rtx insn;
+ rtx split_point = NULL;
+ rtx last = NULL;
+ bool found_code = false;
+
+ if (BB_HEAD (bb))
+ FOR_BB_INSNS (bb, insn)
+ {
+ if (any_condjump_p (insn))
+ split_point = last;
+ else if (!NOTE_P (insn) && !LABEL_P (insn))
+ found_code = true;
+ last = insn;
+ }
+
+ /* Did not find everything. */
+ if (found_code && split_point)
+ return split_block (bb, split_point)->dest;
+ else
+ return NULL;
+}
+
/* Return true if NOTE is not one of the ones that must be kept paired,
so that we may simply delete it. */
@@ -440,7 +485,8 @@ struct tree_opt_pass pass_free_cfg =
rtx
entry_of_function (void)
{
- return (n_basic_blocks ? BB_HEAD (ENTRY_BLOCK_PTR->next_bb) : get_insns ());
+ return (n_basic_blocks - NUM_FIXED_BLOCKS ?
+ BB_HEAD (ENTRY_BLOCK_PTR->next_bb) : get_insns ());
}
/* Update insns block within BB. */
@@ -522,6 +568,29 @@ rtl_split_block (basic_block bb, void *i
}
#endif
}
+ else if (bb == ENTRY_BLOCK_PTR)
+ {
+ /* If we are splitting the entry block, we may need to create
+ the bitmaps if the bitmaps are attached to other nodes.
+ However, the entry and exit blocks do not have bitmaps so we
+ must look elsewhere. */
+ basic_block b = EXIT_BLOCK_PTR->prev_bb;
+ if (b->il.rtl->global_live_at_start)
+ {
+ /* We can leave the blocks empty because there is nothing in
+ the entry block to copy anyway. */
+ new_bb->il.rtl->global_live_at_start = ALLOC_REG_SET (®_obstack);
+ new_bb->il.rtl->global_live_at_end = ALLOC_REG_SET (®_obstack);
+ }
+
+
+#ifdef HAVE_conditional_execution
+ /* In the presence of conditional execution we are not able to update
+ liveness precisely. */
+ if (reload_completed)
+ new_bb->flags |= BB_DIRTY;
+#endif
+ }
return new_bb;
}
@@ -1065,6 +1134,17 @@ force_nonfallthru_and_redirect (edge e,
bool found = false;
basic_block bb = create_basic_block (BB_HEAD (e->dest), NULL, ENTRY_BLOCK_PTR);
+ /* We may need to create the bitmaps if the bitmaps are
+ attached to other nodes. However, the entry and exit
+ blocks do not have bitmaps so we must look elsewhere. */
+ basic_block b = EXIT_BLOCK_PTR->prev_bb;
+ if (b->il.rtl->global_live_at_start)
+ {
+ /* We can leave the blocks empty because there is nothing in
+ the entry block to copy anyway. */
+ bb->il.rtl->global_live_at_start = ALLOC_REG_SET (®_obstack);
+ bb->il.rtl->global_live_at_end = ALLOC_REG_SET (®_obstack);
+ }
/* Change the existing edge's source to be the new block, and add
a new edge from the entry block to the new block. */
@@ -1116,6 +1196,21 @@ force_nonfallthru_and_redirect (edge e,
COPY_REG_SET (jump_block->il.rtl->global_live_at_end,
target->il.rtl->global_live_at_start);
}
+ else if (target == EXIT_BLOCK_PTR)
+ {
+ /* If we are splitting the edge whose dest is the exit block, we
+ may need to create the bitmaps if the bitmaps are attached to
+ other nodes. However, the entry and exit blocks do not have
+ bitmaps so we must look elsewhere. */
+ basic_block b = ENTRY_BLOCK_PTR->next_bb;
+ if (b->il.rtl->global_live_at_start)
+ {
+ /* We can leave the blocks empty because there is nothing in
+ the entry block to copy anyway. */
+ jump_block->il.rtl->global_live_at_start = ALLOC_REG_SET (®_obstack);
+ jump_block->il.rtl->global_live_at_end = ALLOC_REG_SET (®_obstack);
+ }
+ }
/* Make sure new block ends up in correct hot/cold section. */
@@ -1384,6 +1479,21 @@ rtl_split_edge (edge edge_in)
COPY_REG_SET (bb->il.rtl->global_live_at_end,
edge_in->dest->il.rtl->global_live_at_start);
}
+ else if (edge_in->dest == EXIT_BLOCK_PTR)
+ {
+ /* If we are splitting the edge whose dest is the exit block, we
+ may need to create the bitmaps if the bitmaps are attached to
+ other nodes. However, the entry and exit blocks do not have
+ bitmaps so we must look elsewhere. */
+ basic_block b = ENTRY_BLOCK_PTR->next_bb;
+ if (b->il.rtl->global_live_at_start)
+ {
+ /* We can leave the blocks empty because there is nothing in
+ the entry block to copy anyway. */
+ bb->il.rtl->global_live_at_start = ALLOC_REG_SET (®_obstack);
+ bb->il.rtl->global_live_at_end = ALLOC_REG_SET (®_obstack);
+ }
+ }
make_single_succ_edge (bb, edge_in->dest, EDGE_FALLTHRU);
@@ -1787,9 +1897,12 @@ rtl_dump_bb (basic_block bb, FILE *outf,
dump_regset (bb->il.rtl->global_live_at_start, outf);
putc ('\n', outf);
- for (insn = BB_HEAD (bb), last = NEXT_INSN (BB_END (bb)); insn != last;
- insn = NEXT_INSN (insn))
- print_rtl_single (outf, insn);
+ insn = BB_HEAD (bb);
+ if (insn)
+ for (last = NEXT_INSN (BB_END (bb));
+ insn && (insn != last);
+ insn = NEXT_INSN (insn))
+ print_rtl_single_with_indent (outf, insn, indent);
fprintf (outf, ";;%s Registers live at end: ", s_indent);
dump_regset (bb->il.rtl->global_live_at_end, outf);
@@ -2264,7 +2377,7 @@ rtl_verify_flow_info (void)
curr_bb = NULL;
}
- if (num_bb_notes != n_basic_blocks)
+ if (num_bb_notes != n_basic_blocks - NUM_FIXED_BLOCKS)
internal_error
("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
num_bb_notes, n_basic_blocks);
@@ -2837,6 +2950,18 @@ cfg_layout_split_edge (edge e)
COPY_REG_SET (new_bb->il.rtl->global_live_at_end,
e->dest->il.rtl->global_live_at_start);
}
+ else if (e->dest == EXIT_BLOCK_PTR)
+ {
+ basic_block b = ENTRY_BLOCK_PTR->next_bb;
+ if (b->il.rtl->global_live_at_start)
+ {
+ /* We can leave the blocks empty because there is nothing in
+ the entry block to copy anyway. */
+ new_bb->il.rtl->global_live_at_start = ALLOC_REG_SET (®_obstack);
+ new_bb->il.rtl->global_live_at_end = ALLOC_REG_SET (®_obstack);
+ }
+ }
+
make_edge (new_bb, e->dest, EDGE_FALLTHRU);
redirect_edge_and_branch_force (e, new_bb);
@@ -2913,7 +3038,7 @@ rtl_flow_call_edges_add (sbitmap blocks)
int last_bb = last_basic_block;
bool check_last_block = false;
- if (n_basic_blocks == 0)
+ if (n_basic_blocks == NUM_FIXED_BLOCKS)
return 0;
if (! blocks)
@@ -2960,7 +3085,7 @@ rtl_flow_call_edges_add (sbitmap blocks)
calls since there is no way that we can determine if they will
return or not... */
- for (i = 0; i < last_bb; i++)
+ for (i = NUM_FIXED_BLOCKS; i < last_bb; i++)
{
basic_block bb = BASIC_BLOCK (i);
rtx insn;
@@ -3119,7 +3244,9 @@ struct cfg_hooks rtl_cfg_hooks = {
NULL, /* lv_add_condition_to_bb */
NULL, /* lv_adjust_loop_header_phi*/
NULL, /* extract_cond_bb_edges */
- NULL /* flush_pending_stmts */
+ NULL, /* flush_pending_stmts */
+ rtl_block_empty_p, /* block_empty_p */
+ rtl_split_block_before_cond_jump, /* split_block_before_cond_jump */
};
/* Implementation of CFG manipulation for cfg layout RTL, where
@@ -3162,6 +3289,8 @@ struct cfg_hooks cfg_layout_rtl_cfg_hook
rtl_lv_add_condition_to_bb, /* lv_add_condition_to_bb */
NULL, /* lv_adjust_loop_header_phi*/
rtl_extract_cond_bb_edges, /* extract_cond_bb_edges */
- NULL /* flush_pending_stmts */
+ NULL, /* flush_pending_stmts */
+ rtl_block_empty_p, /* block_empty_p */
+ rtl_split_block_before_cond_jump, /* split_block_before_cond_jump */
};
Index: cselib.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cselib.c,v
retrieving revision 1.63
diff -u -p -r1.63 cselib.c
--- cselib.c 29 Jul 2005 05:57:40 -0000 1.63
+++ cselib.c 29 Sep 2005 22:15:47 -0000
@@ -1089,7 +1089,7 @@ cselib_rtx_varies_p (rtx x ATTRIBUTE_UNU
invariant. */
return 0;
}
-
+static bool print_me_next_time = false;
/* Invalidate any locations in the table which are changed because of a
store to MEM_RTX. If this is called because of a non-const call
instruction, MEM_RTX is (mem:BLK const0_rtx). */
@@ -1103,14 +1103,22 @@ cselib_invalidate_mem (rtx mem_rtx)
mem_addr = canon_rtx (get_addr (XEXP (mem_rtx, 0)));
mem_rtx = canon_rtx (mem_rtx);
-
+ if (print_me_next_time)
+ fprintf (stderr, "Calling cselib_invalidate_mem!\n");
vp = &first_containing_mem;
for (v = *vp; v != &dummy_val; v = next)
{
bool has_mem = false;
struct elt_loc_list **p = &v->locs;
int had_locs = v->locs != 0;
-
+#if 0
+ if (num_mems > 400)
+ print_me_next_time = true;
+#endif
+ if (print_me_next_time)
+ {
+ fprintf (stderr, "RTL for value number %d\n", v->value);
+ }
while (*p)
{
rtx x = (*p)->loc;
@@ -1124,6 +1132,14 @@ cselib_invalidate_mem (rtx mem_rtx)
p = &(*p)->next;
continue;
}
+ if (print_me_next_time)
+ {
+ fprintf (stderr, "loc is ");
+ print_rtl_single (stderr, x);
+ fprintf (stderr, " setting insn is ");
+ print_rtl_single (stderr, (*p)->setting_insn);
+ fprintf (stderr, "\n");
+ }
if (num_mems < PARAM_VALUE (PARAM_MAX_CSELIB_MEMORY_LOCATIONS)
&& ! canon_true_dependence (mem_rtx, GET_MODE (mem_rtx), mem_addr,
x, cselib_rtx_varies_p))
@@ -1436,7 +1452,6 @@ cselib_process_insn (rtx insn)
if (find_reg_note (insn, REG_RETVAL, NULL))
cselib_current_insn_in_libcall = false;
cselib_current_insn = 0;
-
if (n_useless_values > MAX_USELESS_VALUES)
remove_useless_values ();
}
Index: df.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/df.c,v
retrieving revision 1.87
diff -u -p -r1.87 df.c
--- df.c 28 Jul 2005 01:47:06 -0000 1.87
+++ df.c 29 Sep 2005 22:15:48 -0000
@@ -3939,7 +3939,7 @@ iterative_dataflow (struct dataflow *dat
sbitmap_zero (visited);
sbitmap_zero (considered);
- for (i = 0; i < dataflow->n_blocks; i++)
+ for (i = 0; i < dataflow->n_blocks - NUM_FIXED_BLOCKS; i++)
{
idx = dataflow->order[i];
SET_BIT (pending, idx);
@@ -3954,7 +3954,7 @@ iterative_dataflow (struct dataflow *dat
while (1)
{
- for (i = 0; i < dataflow->n_blocks; i++)
+ for (i = 0; i < dataflow->n_blocks - NUM_FIXED_BLOCKS ; i++)
{
idx = dataflow->order[i];
Index: dominance.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/dominance.c,v
retrieving revision 1.42
diff -u -p -r1.42 dominance.c
--- dominance.c 25 Jun 2005 01:59:42 -0000 1.42
+++ dominance.c 29 Sep 2005 22:15:48 -0000
@@ -51,8 +51,7 @@ enum dom_state dom_computed[2];
'undefined' or 'end of list'. The name of each node is given by the dfs
number of the corresponding basic block. Please note, that we include the
artificial ENTRY_BLOCK (or EXIT_BLOCK in the post-dom case) in our lists to
- support multiple entry points. As it has no real basic block index we use
- 'last_basic_block' for that. Its dfs number is of course 1. */
+ support multiple entry points. Its dfs number is of course 1. */
/* Type of Basic Block aka. TBB */
typedef unsigned int TBB;
@@ -149,9 +148,8 @@ static unsigned n_bbs_in_dom_tree[2];
static void
init_dom_info (struct dom_info *di, enum cdi_direction dir)
{
- /* We need memory for n_basic_blocks nodes and the ENTRY_BLOCK or
- EXIT_BLOCK. */
- unsigned int num = n_basic_blocks + 1 + 1;
+ /* We need memory for n_basic_blocks nodes. */
+ unsigned int num = n_basic_blocks;
init_ar (di->dfs_parent, TBB, num, 0);
init_ar (di->path_min, TBB, num, i);
init_ar (di->key, TBB, num, i);
@@ -216,7 +214,7 @@ calc_dfs_tree_nonrec (struct dom_info *d
/* Ending block. */
basic_block ex_block;
- stack = xmalloc ((n_basic_blocks + 3) * sizeof (edge_iterator));
+ stack = xmalloc ((n_basic_blocks + 1) * sizeof (edge_iterator));
sp = 0;
/* Initialize our border blocks, and the first edge. */
@@ -372,8 +370,8 @@ calc_dfs_tree (struct dom_info *di, enum
di->nodes = di->dfsnum - 1;
- /* Make sure there is a path from ENTRY to EXIT at all. */
- gcc_assert (di->nodes == (unsigned int) n_basic_blocks + 1);
+ /* This aborts e.g. when there is _no_ path from ENTRY to EXIT at all. */
+ gcc_assert (di->nodes == (unsigned int) n_basic_blocks - 1);
}
/* Compress the path from V to the root of its set and update path_min at the
@@ -627,7 +625,7 @@ calculate_dominance_info (enum cdi_direc
{
b->dom[dir] = et_new_tree (b);
}
- n_bbs_in_dom_tree[dir] = n_basic_blocks + 2;
+ n_bbs_in_dom_tree[dir] = n_basic_blocks;
init_dom_info (&di, dir);
calc_dfs_tree (&di, dir);
Index: flow.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/flow.c,v
retrieving revision 1.635
diff -u -p -r1.635 flow.c
--- flow.c 22 Aug 2005 16:58:46 -0000 1.635
+++ flow.c 29 Sep 2005 22:15:49 -0000
@@ -1056,17 +1056,14 @@ calculate_global_regs_live (sbitmap bloc
SET_REGNO_REG_SET (invalidated_by_call, i);
/* Allocate space for the sets of local properties. */
- local_sets = xcalloc (last_basic_block - (INVALID_BLOCK + 1),
- sizeof (regset));
- cond_local_sets = xcalloc (last_basic_block - (INVALID_BLOCK + 1),
- sizeof (regset));
-
- /* Create a worklist. Allocate an extra slot for ENTRY_BLOCK, and one
- because the `head == tail' style test for an empty queue doesn't
- work with a full queue. */
- queue = xmalloc ((n_basic_blocks - (INVALID_BLOCK + 1)) * sizeof (*queue));
+ local_sets = xcalloc (last_basic_block, sizeof (regset));
+ cond_local_sets = xcalloc (last_basic_block, sizeof (regset));
+
+ /* Create a worklist. Allocate an extra slot for the `head == tail'
+ style test for an empty queue doesn't work with a full queue. */
+ queue = xmalloc ((n_basic_blocks + 1) * sizeof (*queue));
qtail = queue;
- qhead = qend = queue + n_basic_blocks - (INVALID_BLOCK + 1);
+ qhead = qend = queue + n_basic_blocks;
/* Queue the blocks set in the initial mask. Do this in reverse block
number order so that we are more likely for the first round to do
@@ -1247,12 +1244,10 @@ calculate_global_regs_live (sbitmap bloc
basic block. On subsequent passes, we get to skip out early if
live_at_end wouldn't have changed. */
- if (local_sets[bb->index - (INVALID_BLOCK + 1)] == NULL)
+ if (local_sets[bb->index] == NULL)
{
- local_sets[bb->index - (INVALID_BLOCK + 1)]
- = ALLOC_REG_SET (®_obstack);
- cond_local_sets[bb->index - (INVALID_BLOCK + 1)]
- = ALLOC_REG_SET (®_obstack);
+ local_sets[bb->index] = ALLOC_REG_SET (®_obstack);
+ cond_local_sets[bb->index] = ALLOC_REG_SET (®_obstack);
rescan = 1;
}
else
@@ -1276,7 +1271,7 @@ calculate_global_regs_live (sbitmap bloc
successor block. We can miss changes in those sets if
we only compare the new live_at_end against the
previous one. */
- cond_local_set = cond_local_sets[bb->index - (INVALID_BLOCK + 1)];
+ cond_local_set = cond_local_sets[bb->index];
rescan = bitmap_intersect_p (new_live_at_end, cond_local_set);
}
@@ -1292,7 +1287,7 @@ calculate_global_regs_live (sbitmap bloc
/* If any of the changed bits overlap with local_sets[bb],
we'll have to rescan the block. */
- local_set = local_sets[bb->index - (INVALID_BLOCK + 1)];
+ local_set = local_sets[bb->index];
rescan = bitmap_intersect_p (tmp, local_set);
}
}
@@ -1321,8 +1316,8 @@ calculate_global_regs_live (sbitmap bloc
/* Rescan the block insn by insn to turn (a copy of) live_at_end
into live_at_start. */
propagate_block (bb, new_live_at_end,
- local_sets[bb->index - (INVALID_BLOCK + 1)],
- cond_local_sets[bb->index - (INVALID_BLOCK + 1)],
+ local_sets[bb->index],
+ cond_local_sets[bb->index],
flags);
/* If live_at start didn't change, no need to go farther. */
@@ -1368,11 +1363,11 @@ calculate_global_regs_live (sbitmap bloc
SET_BIT (blocks_out, pbb->index);
/* Makes sure to really rescan the block. */
- if (local_sets[pbb->index - (INVALID_BLOCK + 1)])
+ if (local_sets[pbb->index])
{
- FREE_REG_SET (local_sets[pbb->index - (INVALID_BLOCK + 1)]);
- FREE_REG_SET (cond_local_sets[pbb->index - (INVALID_BLOCK + 1)]);
- local_sets[pbb->index - (INVALID_BLOCK + 1)] = 0;
+ FREE_REG_SET (local_sets[pbb->index]);
+ FREE_REG_SET (cond_local_sets[pbb->index]);
+ local_sets[pbb->index] = 0;
}
/* Add it to the queue. */
@@ -1418,16 +1413,16 @@ calculate_global_regs_live (sbitmap bloc
EXECUTE_IF_SET_IN_SBITMAP (blocks_out, 0, i, sbi)
{
basic_block bb = BASIC_BLOCK (i);
- FREE_REG_SET (local_sets[bb->index - (INVALID_BLOCK + 1)]);
- FREE_REG_SET (cond_local_sets[bb->index - (INVALID_BLOCK + 1)]);
+ FREE_REG_SET (local_sets[bb->index]);
+ FREE_REG_SET (cond_local_sets[bb->index]);
};
}
else
{
FOR_EACH_BB (bb)
{
- FREE_REG_SET (local_sets[bb->index - (INVALID_BLOCK + 1)]);
- FREE_REG_SET (cond_local_sets[bb->index - (INVALID_BLOCK + 1)]);
+ FREE_REG_SET (local_sets[bb->index]);
+ FREE_REG_SET (cond_local_sets[bb->index]);
}
}
@@ -2474,7 +2469,7 @@ libcall_dead_p (struct propagate_block_i
int
regno_clobbered_at_setjmp (int regno)
{
- if (n_basic_blocks == 0)
+ if (n_basic_blocks == NUM_FIXED_BLOCKS)
return 0;
return ((REG_N_SETS (regno) > 1
Index: function.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/function.c,v
retrieving revision 1.645
diff -u -p -r1.645 function.c
--- function.c 17 Sep 2005 18:38:36 -0000 1.645
+++ function.c 29 Sep 2005 22:15:51 -0000
@@ -5276,7 +5276,8 @@ thread_prologue_and_epilogue_insns (rtx
fixup_fallthru_exit_predecessor. */
cfg_layout_initialize (0);
FOR_EACH_BB (cur_bb)
- if (cur_bb->index >= 0 && cur_bb->next_bb->index >= 0)
+ if (cur_bb->index >= NUM_FIXED_BLOCKS
+ && cur_bb->next_bb->index >= NUM_FIXED_BLOCKS)
cur_bb->aux = cur_bb->next_bb;
cfg_layout_finalize ();
}
Index: global.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/global.c,v
retrieving revision 1.132
diff -u -p -r1.132 global.c
--- global.c 1 Sep 2005 05:29:02 -0000 1.132
+++ global.c 29 Sep 2005 22:15:51 -0000
@@ -621,7 +621,7 @@ global_alloc (FILE *file)
#if 0 /* We need to eliminate regs even if there is no rtl code,
for the sake of debugging information. */
- if (n_basic_blocks > 0)
+ if (n_basic_blocks > NUM_FIXED_BLOCKS)
#endif
{
build_insn_chain (get_insns ());
@@ -2281,9 +2281,9 @@ set_up_bb_rts_numbers (void)
int i;
int *rts_order;
- rts_order = xmalloc (sizeof (int) * n_basic_blocks);
+ rts_order = xmalloc (sizeof (int) * (n_basic_blocks - NUM_FIXED_BLOCKS));
flow_reverse_top_sort_order_compute (rts_order);
- for (i = 0; i < n_basic_blocks; i++)
+ for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; i++)
BB_INFO_BY_INDEX (rts_order [i])->rts_number = i;
free (rts_order);
}
Index: ifcvt.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/ifcvt.c,v
retrieving revision 1.194
diff -u -p -r1.194 ifcvt.c
--- ifcvt.c 22 Jul 2005 12:25:20 -0000 1.194
+++ ifcvt.c 29 Sep 2005 22:15:53 -0000
@@ -3149,14 +3149,14 @@ find_if_case_2 (basic_block test_bb, edg
return FALSE;
/* THEN is not EXIT. */
- if (then_bb->index < 0)
+ if (then_bb->index < NUM_FIXED_BLOCKS)
return FALSE;
/* ELSE is predicted or SUCC(ELSE) postdominates THEN. */
note = find_reg_note (BB_END (test_bb), REG_BR_PROB, NULL_RTX);
if (note && INTVAL (XEXP (note, 0)) >= REG_BR_PROB_BASE / 2)
;
- else if (else_succ->dest->index < 0
+ else if (else_succ->dest->index < NUM_FIXED_BLOCKS
|| dominated_by_p (CDI_POST_DOMINATORS, then_bb,
else_succ->dest))
;
Index: lcm.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/lcm.c,v
retrieving revision 1.76
diff -u -p -r1.76 lcm.c
--- lcm.c 25 Jun 2005 02:00:29 -0000 1.76
+++ lcm.c 29 Sep 2005 22:15:53 -0000
@@ -107,7 +107,8 @@ compute_antinout_edge (sbitmap *antloc,
/* Allocate a worklist array/queue. Entries are only added to the
list if they were not already on the list. So the size is
bounded by the number of basic blocks. */
- qin = qout = worklist = xmalloc (sizeof (basic_block) * n_basic_blocks);
+ qin = qout = worklist = xmalloc (sizeof (basic_block) *
+ (n_basic_blocks - NUM_FIXED_BLOCKS));
/* We want a maximal solution, so make an optimistic initialization of
ANTIN. */
@@ -122,8 +123,8 @@ compute_antinout_edge (sbitmap *antloc,
}
qin = worklist;
- qend = &worklist[n_basic_blocks];
- qlen = n_basic_blocks;
+ qend = &worklist[n_basic_blocks - NUM_FIXED_BLOCKS];
+ qlen = n_basic_blocks - NUM_FIXED_BLOCKS;
/* Mark blocks which are predecessors of the exit block so that we
can easily identify them below. */
@@ -260,7 +261,7 @@ compute_laterin (struct edge_list *edge_
list if they were not already on the list. So the size is
bounded by the number of basic blocks. */
qin = qout = worklist
- = xmalloc (sizeof (basic_block) * (n_basic_blocks + 1));
+ = xmalloc (sizeof (basic_block) * (n_basic_blocks - NUM_FIXED_BLOCKS));
/* Initialize a mapping from each edge to its index. */
for (i = 0; i < num_edges; i++)
@@ -294,11 +295,10 @@ compute_laterin (struct edge_list *edge_
}
/* Note that we do not use the last allocated element for our queue,
- as EXIT_BLOCK is never inserted into it. In fact the above allocation
- of n_basic_blocks + 1 elements is not necessary. */
+ as EXIT_BLOCK is never inserted into it. */
qin = worklist;
- qend = &worklist[n_basic_blocks];
- qlen = n_basic_blocks;
+ qend = &worklist[n_basic_blocks - NUM_FIXED_BLOCKS];
+ qlen = n_basic_blocks - NUM_FIXED_BLOCKS;
/* Iterate until the worklist is empty. */
while (qlen)
@@ -485,7 +485,8 @@ compute_available (sbitmap *avloc, sbitm
/* Allocate a worklist array/queue. Entries are only added to the
list if they were not already on the list. So the size is
bounded by the number of basic blocks. */
- qin = qout = worklist = xmalloc (sizeof (basic_block) * n_basic_blocks);
+ qin = qout = worklist =
+ xmalloc (sizeof (basic_block) * (n_basic_blocks - NUM_FIXED_BLOCKS));
/* We want a maximal solution. */
sbitmap_vector_ones (avout, last_basic_block);
@@ -499,8 +500,8 @@ compute_available (sbitmap *avloc, sbitm
}
qin = worklist;
- qend = &worklist[n_basic_blocks];
- qlen = n_basic_blocks;
+ qend = &worklist[n_basic_blocks - NUM_FIXED_BLOCKS];
+ qlen = n_basic_blocks - NUM_FIXED_BLOCKS;
/* Mark blocks which are successors of the entry block so that we
can easily identify them below. */
Index: modulo-sched.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/modulo-sched.c,v
retrieving revision 1.38
diff -u -p -r1.38 modulo-sched.c
--- modulo-sched.c 24 Aug 2005 07:56:54 -0000 1.38
+++ modulo-sched.c 29 Sep 2005 22:15:53 -0000
@@ -2536,7 +2536,6 @@ rest_of_handle_sms (void)
{
#ifdef INSN_SCHEDULING
basic_block bb;
- sbitmap blocks;
/* We want to be able to create new pseudos. */
no_new_pseudos = 0;
@@ -2547,9 +2546,7 @@ rest_of_handle_sms (void)
/* Update the life information, because we add pseudos. */
max_regno = max_reg_num ();
allocate_reg_info (max_regno, FALSE, FALSE);
- blocks = sbitmap_alloc (last_basic_block);
- sbitmap_ones (blocks);
- update_life_info (blocks, UPDATE_LIFE_GLOBAL_RM_NOTES,
+ update_life_info (NULL, UPDATE_LIFE_GLOBAL_RM_NOTES,
(PROP_DEATH_NOTES
| PROP_REG_INFO
| PROP_KILL_DEAD_CODE
Index: predict.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/predict.c,v
retrieving revision 1.155
diff -u -p -r1.155 predict.c
--- predict.c 1 Aug 2005 03:54:46 -0000 1.155
+++ predict.c 29 Sep 2005 22:15:54 -0000
@@ -703,7 +703,7 @@ predict_loops (struct loops *loops_info,
conditional has no loop header successors as not taken. */
if (!header_found)
FOR_EACH_EDGE (e, ei, bb->succs)
- if (e->dest->index < 0
+ if (e->dest->index < NUM_FIXED_BLOCKS
|| !flow_bb_inside_loop_p (loop, e->dest))
predict_edge
(e, PRED_LOOP_EXIT,
@@ -1267,7 +1267,7 @@ tree_bb_level_predictions (void)
int *heads;
heads = xmalloc (sizeof (int) * last_basic_block);
- memset (heads, -1, sizeof (int) * last_basic_block);
+ memset (heads, ENTRY_BLOCK, sizeof (int) * last_basic_block);
heads[ENTRY_BLOCK_PTR->next_bb->index] = last_basic_block;
apply_return_prediction (heads);
@@ -1520,10 +1520,7 @@ predict_paths_leading_to (basic_block bb
while (next_ai != bb)
{
next_ai = ai;
- if (heads[ai->index] == ENTRY_BLOCK)
- ai = ENTRY_BLOCK_PTR;
- else
- ai = BASIC_BLOCK (heads[ai->index]);
+ ai = BASIC_BLOCK (heads[ai->index]);
heads[next_ai->index] = head;
}
}
@@ -1534,7 +1531,7 @@ predict_paths_leading_to (basic_block bb
if (y == last_basic_block)
return;
FOR_EACH_EDGE (e, ei, BASIC_BLOCK (y)->succs)
- if (e->dest->index >= 0
+ if (e->dest->index >= NUM_FIXED_BLOCKS
&& dominated_by_p (CDI_POST_DOMINATORS, e->dest, bb))
predict_edge_def (e, pred, taken);
}
@@ -1592,12 +1589,7 @@ propagate_freq (struct loop *loop, bitma
/* The outermost "loop" includes the exit block, which we can not
look up via BASIC_BLOCK. Detect this and use EXIT_BLOCK_PTR
directly. Do the same for the entry block. */
- if (i == (unsigned)ENTRY_BLOCK)
- bb = ENTRY_BLOCK_PTR;
- else if (i == (unsigned)EXIT_BLOCK)
- bb = EXIT_BLOCK_PTR;
- else
- bb = BASIC_BLOCK (i);
+ bb = BASIC_BLOCK (i);
FOR_EACH_EDGE (e, ei, bb->preds)
{
Index: print-rtl.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/print-rtl.c,v
retrieving revision 1.125
diff -u -p -r1.125 print-rtl.c
--- print-rtl.c 16 Aug 2005 00:13:21 -0000 1.125
+++ print-rtl.c 29 Sep 2005 22:15:54 -0000
@@ -774,16 +774,34 @@ print_rtl (FILE *outf, rtx rtx_first)
int
print_rtl_single (FILE *outf, rtx x)
{
+ return print_rtl_single_with_indent (outf, x, 0);
+}
+
+/* Like print_rtx, except specify a file. */
+/* Return nonzero if we actually printed anything. */
+
+int
+print_rtl_single_with_indent (FILE *outf, rtx x, int ind)
+{
+ int old_indent = indent;
+ char *s_indent = (char *) alloca ((size_t) ind + 1);
+ memset ((void *) s_indent, ' ', (size_t) ind);
+ s_indent[ind] = '\0';
+
+ indent = ind;
outfile = outf;
sawclose = 0;
if (! flag_dump_unnumbered
|| !NOTE_P (x) || NOTE_LINE_NUMBER (x) < 0)
{
+ fputs (s_indent, outfile);
fputs (print_rtx_head, outfile);
print_rtx (x);
putc ('\n', outf);
+ indent = old_indent;
return 1;
}
+ indent = old_indent;
return 0;
}
Index: profile.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/profile.c,v
retrieving revision 1.164
diff -u -p -r1.164 profile.c
--- profile.c 3 Aug 2005 22:10:41 -0000 1.164
+++ profile.c 29 Sep 2005 22:15:54 -0000
@@ -531,7 +531,7 @@ compute_branch_probabilities (void)
{
FOR_EACH_EDGE (e, ei, bb->succs)
e->probability = (e->count * REG_BR_PROB_BASE + bb->count / 2) / bb->count;
- if (bb->index >= 0
+ if (bb->index >= NUM_FIXED_BLOCKS
&& block_ends_with_condjump_p (bb)
&& EDGE_COUNT (bb->succs) >= 2)
{
@@ -609,7 +609,7 @@ compute_branch_probabilities (void)
FOR_EACH_EDGE (e, ei, bb->succs)
e->probability = REG_BR_PROB_BASE / total;
}
- if (bb->index >= 0
+ if (bb->index >= NUM_FIXED_BLOCKS
&& block_ends_with_condjump_p (bb)
&& EDGE_COUNT (bb->succs) >= 2)
num_branches++, num_never_executed;
@@ -704,7 +704,9 @@ compute_value_histograms (histogram_valu
free (histogram_counts[t]);
}
-#define BB_TO_GCOV_INDEX(bb) ((bb)->index + 1)
+/* The entry basic block will be moved around so that it has index=1,
+ there is noting at index 0 and the exit is at n_basic_block. */
+#define BB_TO_GCOV_INDEX(bb) ((bb)->index - 1)
/* When passed NULL as file_name, initialize.
When passed something else, output the necessary commands to change
line to LINE and offset to FILE_NAME. */
@@ -904,7 +906,7 @@ branch_prob (void)
num_instrumented++;
}
- total_num_blocks += n_basic_blocks + 2;
+ total_num_blocks += n_basic_blocks;
if (dump_file)
fprintf (dump_file, "%d basic blocks\n", n_basic_blocks);
@@ -925,7 +927,7 @@ branch_prob (void)
gcov_position_t offset;
offset = gcov_write_tag (GCOV_TAG_BLOCKS);
- for (i = 0; i != (unsigned) (n_basic_blocks + 2); i++)
+ for (i = 0; i != (unsigned) (n_basic_blocks); i++)
gcov_write_unsigned (0);
gcov_write_length (offset);
}
@@ -933,7 +935,7 @@ branch_prob (void)
/* Keep all basic block indexes nonnegative in the gcov output.
Index 0 is used for entry block, last index is for exit block.
*/
- ENTRY_BLOCK_PTR->index = -1;
+ ENTRY_BLOCK_PTR->index = 1;
EXIT_BLOCK_PTR->index = last_basic_block;
/* Arcs */
Index: regions.c
===================================================================
RCS file: regions.c
diff -N regions.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ regions.c 29 Sep 2005 22:15:55 -0000
@@ -0,0 +1,3651 @@
+/* Structural analysis of the control flow graph.
+ Copyright (C) 2005 Free Software Foundation, Inc.
+ Contributed by Kenneth Zadeck <zadeck@naturalbridge.com>
+
+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 "rtl.h"
+#include "tm_p.h"
+#include "insn-config.h"
+#include "recog.h"
+#include "function.h"
+#include "regs.h"
+#include "alloc-pool.h"
+#include "hard-reg-set.h"
+#include "bitmap.h"
+#include "basic-block.h"
+#include "output.h"
+#include "tree.h"
+#include "langhooks.h"
+#include "ggc.h"
+
+static bitmap_obstack transient_region_obstack;
+static bitmap_obstack persistent_region_obstack;
+static void minimize_improper_regions (basic_block);
+static basic_block new_improper_region (basic_block);
+static struct bb_temp * create_info (basic_block);
+static void analyze_loops (void);
+static void build_recursive_info (basic_block);
+static void analyze_structures (basic_block, int);
+static void dump_case_list (basic_block *, int, int, const char*);
+static void dump_recursive (basic_block, int);
+static void print_region_bb (FILE*, basic_block, const char*);
+static bool get_real_entry_blocks_1 (bitmap, bitmap, basic_block, bitmap, bitmap);
+static bool get_real_exit_blocks_1 (bitmap, bitmap, basic_block, bitmap, bitmap);
+
+
+/* This array serves two purposes, it first holds all of the original
+ basic blocks in postorder. It also holds all of the region nodes
+ that are added at the end. */
+static basic_block *nodes_in_postord;
+static unsigned int nodes_in_postord_size;
+
+static int region_stats[(int)SWITCH_REGION+1];
+
+/*
+This module builds a structure graph on top of the control flow
+graph. Various types of single entry structured region types are
+identified and "reduced" to single nodes. (The exception to this are
+multiple entry loops for which a special entry nodes are created to
+funnel all of the entries thru.) The region nodes are special basic
+blocks that do not contain any instructions but do contain information
+the encapsulates the region.
+
+This module has been implemented so that it can be run at either the
+tree level or the rtl level. In both cases it assumes that the
+control flow graph has been built and is in good working order.
+
+A call to create_regions() will analyze the cfg and construct the
+region tree. The root of that tree can be accessed by ROOT_BLOCK_PTR
+or (ROOT_BLOCK_PTR_FOR_FUNCTION(FN)).
+
+When the region tree is not needed anymore, a call delete_regions()
+will clean up everything.
+
+There are several design choices that have been made in order to make
+this analysis work within the limitations of the gcc data structures.
+Even though region nodes are basic blocks, they are not linked into
+the standard list of basic blocks for the function. This has been
+done to minimize the amount of code that must be changed. A great
+deal of the compiler would not know how to handle the region nodes.
+
+Likewise, the original set of preds and succs are not touched. There
+are special region_preds and region_succs that are used here.
+
+The iteration thru the control tree is best done recursively, start at
+the root region node which is stored in the ROOT_BLOCK_PTR and iterate
+with FOR_EACH_BB_IN_REGION, recurse for every node that is not a
+SINGLE_NODE_REGION.
+
+For many of the region types, there are fields in the region node that
+allow the region to be processed in a structured manner. This is
+subject to change in is expected to be enhanced as uses develop.
+
+Two way conditional are generally matched to the basic_blocks at the
+tree level and only sometimes matched at the rtl level. This is
+because EDGE_TRUE_VALUE and EDGE_FALSE_VALUE are only occasionally set
+at the rtl level. Any one who thinks they can do better is welcome to
+try. Likewise, there is no matching between the label and the arms of
+a case statement. These are problems that should be addressed.
+
+The definition of a case statement is rather liberal. Returns and
+loop exits are allowed as well as drop thru's from one case to the
+next. There is a lot of complex code to make this work and it should
+not be tampered with by the casual user.
+
+It is also possible that more region types could be added. These can
+be tricky, but it quite useful to have as much of the control flow
+covered by high level regions as possible. Anyone who has a region
+that they feel would be useful to add, should contact
+zadeck@naturalbridge.com for help.
+
+Another place where this will be extended is to track changes in the
+cfg. For a large number of changes this should not be hard, and it
+will be generally more useful than reparsing the graph. Suggestions
+on a api for this would be appreciated.
+
+The liberal definition of regions has the advantage that a large
+amount of a function can be completely covered by regions. The
+downside is that many of the regions may not be single entry or single
+exit. There are two functions, SINGLE_ENTRY_REGION_P and
+SINGLE_EXIT_REGION_P that can be used to determine this. The sets of
+entry nodes and exit nodes can be found by GET_REAL_ENTRY_REGIONS and
+GET_REAL_EXIT_REGIONS. For single entry or exit regions these return
+simple answers. For multiple entry and exit regions, these return a
+set of blocks and a set of bits to say weather to use the end of that
+block or the beginning as the logical boundary of the block. For many
+algorithms, just doing something for the single entry or exits may be
+good enough.
+
+*/
+
+/*
+This implementation is based loosely on control flow analysis by an
+algorithm by Sharir and Schwartz that appeared in the journal
+"Computer Languages" (1980 vol 5, pgs 141-153). The handling of
+irreducible regions is based on unpublished (and unpatented)
+techniques developed at HP. The combined algorithm was then
+generalized by Barry Rosen of IBM, Carol Thompson of HP and Kenneth
+Zadeck of IBM in preparation for a book that was never and will never
+be published. The comments in this module are taken from the text of
+that chapter and the code was translated from the pseudocode examples
+of that chapter all with permission of the authors.
+*/
+
+/*
+NESTED SINGLE-ENTRY REGIONS
+
+Many transformation techniques assume that the control flow graph CFG
+has been analyzed as a hierarchy of regions. Each REGION is a
+subgraph with a distinguished node h (sometimes called the HEAD or
+HEADER) such that h is the only node in the subgraph that may have
+inedges from outside. The REGION_HEAD field is used for this. The
+qualifier "single-entry" is logically redundant but is sometimes added
+for emphasis or to contrast with other possible uses of "Region" as a
+technical term. For historical reasons, regions are often called
+INTERVALS. The name INTERVAL ANALYSIS has been applied to several
+distinct ways to define and build hierarchies of regions.
+
+For a given region R, any edge (x,y) with x in R but y not in R is an
+EXIT EDGE. Any node in R with at least one exit edge among its
+outedges is an EXIT NODE.
+
+A CONTROL TREE is a tree whose nodes are regions. The root of the
+tree is a huge region consisting of the entire control-flow graph CFG,
+with ENTRY as the header. The leaves are tiny regions consisting of
+single basic blocks. At intermediate levels in the tree are regions
+of intermediate size. These regions are NESTED: for any regions R and
+S in the tree, the following conditions hold:
+
+* If R is a descendant of S in the control tree, then R is a subset of S.
+
+* If R and S are independent in the control tree, then R union S =
+ EMPTYSET.
+
+If CFG has n nodes, then it has a trivial control tree with n+1
+regions. Several nontrivial kinds of control tree used in compiling
+are explained later in this chapter. Nontrivial control trees support
+divide-and-conquer strategies in optimization. When a region R is
+processed, each child region S is treated LIKE a single node, with an
+inedge for each inedge of the header of S and an outedge for each exit
+edge of S. (The actual complexity of control flow within S is
+temporarily ignored.) Thus a region with K children in the control
+tree defines a graph with K+1 nodes. Several kinds of analysis and
+optimization benefit from replacing one large and complex graph CFG by
+a family of smaller and simpler graphs, organized by the control tree.
+Indeed, it is often convenient to think of the control tree as a tree
+of graphs. Because each of these graphs abstracts away the internal
+complexity of child regions, they are called ABSTRACT graphs here.
+
+The control tree is yet another tree structure, not to be confused
+with the parse tree. Control-flow analysis is concerned with the
+actual control-flow relations among basic blocks. For procedures that
+contain RETURN, BREAK, or GOTO statements, these relations differ from
+those suggested by the syntactic nesting of explicit control
+structures like WHILE and IF-THEN in the parse tree.
+
+Loops
+
+A LOOP is a strongly connected (single-entry) region. Given a control
+tree, a REDUCED LOOP is a loop that appears in the tree and has an
+abstract graph that becomes acyclic when all inedges of the header are
+ignored. In particular, code that loops over the elements of an array
+of dimension d can be described by a control tree that has d reduced
+loops.
+
+Loops are so important in optimization that some kinds of control tree
+are constructed with very few regions other than loops. The
+control-flow graph is said to be REDUCIBLE if the abstract graph at
+each node of its control tree is EITHER acyclic OR a reduced loop.
+
+Some optimization techniques presuppose reducibility, so it is
+fortunate that most of the control-flow graphs encountered in practice
+are indeed reducible. Other techniques are still feasible, but more
+complex, when CFG is irreducible. If the exceptional abstract graphs
+caused by improper regions are few and small, then the extra work they
+require may be modest.
+
+If CFG is reducible, then the control tree actually built is indeed
+one where each of the abstract graphs is well-behaved (either acyclic
+or a reduced loop). If CFG is irreducible, then most of the abstract
+graphs are still well-behaved.
+
+Structural analysis builds a more elaborate tree whose regions display
+control structures (like the IF-THEN-ELSE) as well as loops.
+
+Building Control Trees
+
+Various ways to define and build control trees have been proposed.
+This section considers some issues common to the two techniques
+explained in detail in the following two sections. Both techniques
+assume that basic blocks have been identified, the control-flow graph
+CFG has been built, depth-first search has assigned preorder and
+postorder numbers to the nodes. In the case of irreducibility, the
+dominator tree, with its associated preorder and postorder numbers,
+must also be built.
+
+Whenever we decide that a node x heads a nontrivial region R, we call
+a routine new_region(x,R,rt,info) that creates a new node u to
+represent R and marks u as representing a region of type rt, where rt
+is one of a fixed set of descriptive strings like "ReducedLoop."
+During the rest of the analysis, x and the other nodes in R are
+invisible, but u is treated like any other node in CFG, with preorder
+numbers, postorder numbers, and to handle irreducibility, dominator
+tree preorder numbers, dominator tree postorder numbers, and immediate
+dominator inherited from x. The call new_region(x,R,rt,info) also creates
+new inedges for u in CFG (to represent the inedges of x from outside
+R) and new outedges for u in CFG (to represent the exit edges of R).
+
+The graph CFG seen by the analysis is constantly changing, as regions
+are recognized and new nodes are created to encapsulate them. To
+manage these changes and to manage the dynamic collection of nodes in
+the control-tree, it is helpful to add more attributes to the nodes
+and to consider CFG nodes and control-tree nodes as the same kind of
+object, simply called a NODE hereafter. When NewRegion creates a new
+node, it initializes the attributes as discussed below.
+
+The set VisibleNodes of currently visible nodes is maintained by
+new_region after being initialized by initialize_from.
+
+The shared variable visible_nodes persists across calls on new_region,
+and initialize_from defined below.
+*/
+
+static bitmap visible_nodes;
+
+/*
+The last call on new_region is the one from ROOT_REGION which is
+called at the end of analysis to put visible_nodes into a single
+region at the root of the control tree.
+
+There are three groups of fields associated with the structural
+analysis:
+
+1) Fields that are associated with every regular block and will
+ remain after the analysis. These are part of the regular basic
+ block structure.
+
+ * The parent_region field points to a node h != x that corresponds
+ to a region containing x. When x is created, we set
+ parent_region of x to NULL. When x joins h->blocks_in_region,
+ we set x->parent_region to h.
+
+ * x->in_region points to a node that corresponds to a region
+ containing $x$. When x is created, we set in_region of x to
+ NULL. When x joins h->blocks_in_region, we set x->in_region to
+ h. Unlike parent_region, x->in_region may later be updated, so
+ as to point to a proper ancestor of h in the control tree and
+ thus a larger region in cfg that contains x.
+
+2) Fields that are associated with the region nodes and will
+ remain after the analysis. These are allocated into a struct
+ basic_basic_region_def defined in basic_block.h and are assigned to
+ the region_info field of the basic block. They are only allocated
+ for region nodes. For regular blocks this field is NULL.
+
+ * The field region_type telling what type of region the block
+ represents. If the region_info is NULL, the block is assumed to
+ be a SINGLE_NODE_REGION.
+
+3) Fields that are necessary for the analysis of the function but
+ can be discarded after the analysis is complete. These are defined
+ in the bb_temp structure that is assigned to the basic_block's aux
+ field and then cleaned up at the end of analysis.
+
+ * The bitmap blocks_in_region contains the set of nodes
+ in the regions just below the region represented by the node.
+
+ * The preds and succs of the basic block as a bitmap.
+
+ * The visible_preds of each basic block x holds the set of
+ currently visible predecessors, which is not to be confused with
+ the original set preds if x was originally in CFG. Similarly,
+ the field visible_succs holds the set of currently visible
+ successors.
+
+ * In order to take irreducibility into account, two additional
+ fields are requirred. At each basic block x we store a bitmap,
+ improper_nodes, of blocks y that will eventually be included in
+ an improper region headed by x. Because, in the usual case of a
+ reducible graph, this set remains empty throughout the analysis,
+ this bitmap is not allocated until necessary.
+
+ * At each block x we store a pointer improper_head to a node h that
+ will head an improper region containing x. When x is created, we
+ set ImproperHead[x] to NULL. In the usual case of a reducible
+ graph, this field remains NULL throughout the analysis.
+
+*/
+
+struct bb_temp
+{
+ basic_block improper_head;
+ /* IN_REGION is used as a temp structure to find the entries to an
+ improper region. */
+ basic_block in_region;
+ basic_block same_dominator_as;
+ bool visited;
+ /* Fields used to find the merge point in a case statement. */
+ int num_path;
+ int num_pred_in_set;
+ int preord;
+ int postord;
+ /* For regular blocks, this is the postorder number, region nodes
+ are just sequentially numbered after the last block. */
+ unsigned int index;
+ bitmap preds;
+ bitmap succs;
+ bitmap visible_preds;
+ bitmap visible_succs;
+ bitmap improper_nodes;
+ bitmap blocks_in_region;
+};
+
+/* The region nodes get a positive NEXT_BITMAP_INDEX that is kept in
+ the info field. This is used as an index into bitmaps. The
+ NEXT_REGION_INDEX is an arbitrary negative number used for
+ identification. This is stored in the basic_block index field. It
+ should not be postitive since these nodes are not put in the list
+ and vectors of all blocks.*/
+static unsigned int next_bitmap_index;
+static int next_region_index;
+
+/* Remove y from it's current parent region. */
+static void
+remove_from_current_region (basic_block y)
+{
+ struct bb_temp *y_info = (struct bb_temp *)y->aux;
+ basic_block z = y->parent_region;
+ struct bb_temp *z_info = (struct bb_temp *)z->aux;
+ bitmap_clear_bit (z_info->blocks_in_region, y_info->index);
+ y->parent_region = NULL;
+}
+
+/* Build the specialized region basic_block of type RT for a region
+ with the entry block entry block X, containing
+ BLOCKS_IN_REGION. */
+static basic_block
+new_region (basic_block x,
+ bitmap blocks_in_region,
+ enum region_type rt,
+ region_details_u * region_details)
+{
+ struct bb_temp *x_info = (struct bb_temp *)x->aux;
+ unsigned int x_index = x_info->index;
+ unsigned int y_index, z_index;
+ bitmap_iterator bi, bi2;
+ basic_block u = alloc_block ();
+ unsigned int u_index = next_bitmap_index++;
+ struct bb_temp *u_info = create_info (u);
+ u->parent_region = NULL;
+ u->prev_bb_in_region = NULL;
+ u->next_bb_in_region = NULL;
+ u->next_bb = NULL;
+ u->prev_bb = NULL;
+ u->index = --next_region_index;
+
+ u->region_info = ggc_alloc_cleared (sizeof (struct basic_block_region_def));
+ u->region_info->type = rt;
+ u->region_info->region_head = x;
+ u->region_info->region_details = region_details;
+
+ u_info->in_region = NULL;
+ u_info->preord = x_info->preord;
+ u_info->postord = x_info->postord;
+ u_info->index = u_index;
+
+ region_stats[(int)rt]++;
+
+ gcc_assert(u_index < nodes_in_postord_size);
+ nodes_in_postord[u_index] = u;
+ u_info->blocks_in_region = blocks_in_region;
+ u_info->same_dominator_as = x;
+
+ /* For every node z outside the region that points to the region
+ node...
+
+ For every z in (x.visible_preds intersect ~region) :
+ add z to u.preds
+ remove x from z.visible_succs
+ add u to z.visible_succs.
+ */
+
+ EXECUTE_IF_SET_IN_BITMAP(x_info->visible_preds, 0, z_index, bi)
+ {
+ if (!bitmap_bit_p (blocks_in_region, z_index))
+ {
+ basic_block z = nodes_in_postord[z_index];
+ struct bb_temp *z_info = (struct bb_temp *)z->aux;
+
+ bitmap_set_bit (u_info->preds, z_index);
+ bitmap_clear_bit (z_info->visible_succs, x_index);
+ bitmap_set_bit (z_info->visible_succs, u_index);
+ }
+ }
+
+ /* For every node z outside the region with a pred that points back
+ into the region...
+
+ For every y in region :
+ for every z in (y.visible_succs intersect ~region) :
+ add z to u.succs
+ remove y from z.visible_succs
+ add u to z.visible_succs.
+ */
+ EXECUTE_IF_SET_IN_BITMAP(blocks_in_region, 0, y_index, bi)
+ {
+ basic_block y = nodes_in_postord[y_index];
+ struct bb_temp *y_info = (struct bb_temp *)y->aux;
+
+ if (y->parent_region)
+ remove_from_current_region (y);
+ y->parent_region = u;
+ y_info->in_region = u;
+
+ EXECUTE_IF_SET_IN_BITMAP(y_info->visible_succs, 0, z_index, bi2)
+ {
+ if (!bitmap_bit_p (blocks_in_region, z_index))
+ {
+ basic_block z = nodes_in_postord[z_index];
+ struct bb_temp *z_info = (struct bb_temp *)z->aux;
+
+ bitmap_set_bit (u_info->succs, z_index);
+ bitmap_clear_bit (z_info->visible_preds, y_index);
+ bitmap_set_bit (z_info->visible_preds, u_index);
+ }
+ }
+ }
+
+ bitmap_copy (u_info->visible_succs, u_info->succs);
+ bitmap_copy (u_info->visible_preds, u_info->preds);
+ bitmap_and_compl_into (visible_nodes, blocks_in_region);
+ bitmap_set_bit (visible_nodes, u_index);
+
+ /* Since irreducibility is rare, delay creating the bitmap for
+ improper_nodes until it is necessary. */
+ u_info->improper_head = NULL;
+ u_info->improper_nodes = NULL;
+
+ return u;
+}
+
+/* Just your basic depth first search to set the pre and post order
+ numbers and build the array of blocks in postord. */
+
+static int r_count, s_count, original_node_count;
+
+static void
+dfs_forward (basic_block x)
+{
+ struct bb_temp *x_info = (struct bb_temp *)x->aux;
+ edge_iterator ei;
+ edge e;
+ x_info->preord = r_count++;
+
+ FOR_EACH_EDGE (e, ei, x->succs)
+ {
+ basic_block y = e->dest;
+ struct bb_temp *y_info = (struct bb_temp *)y->aux;
+ if (y_info->preord == -1)
+ dfs_forward(y);
+ }
+ x_info->postord = s_count;
+ x_info->index = s_count;
+ nodes_in_postord[s_count] = x;
+ s_count++;
+}
+
+/* Create and attach the info structure to the aux field of U. */
+static struct bb_temp *
+create_info (basic_block u)
+{
+ struct bb_temp *u_info = (struct bb_temp *)xmalloc (sizeof(struct bb_temp));
+
+ u->aux = u_info;
+ u->parent_region = NULL;
+
+ u_info->in_region = NULL;
+ u_info->preds = BITMAP_ALLOC (&transient_region_obstack);
+ u_info->succs = BITMAP_ALLOC (&transient_region_obstack);
+ u_info->visible_preds = BITMAP_ALLOC (&transient_region_obstack);
+ u_info->visible_succs = BITMAP_ALLOC (&transient_region_obstack);
+ u_info->improper_nodes = NULL;
+ u_info->improper_head = NULL;
+ u_info->blocks_in_region = NULL;
+ u_info->same_dominator_as = NULL;
+ u_info->num_path = 0;
+ u_info->num_pred_in_set = 0;
+
+ return u_info;
+}
+
+int
+split_blocks_for_regions (void)
+{
+ basic_block bb;
+ edge e;
+ edge_iterator ei;
+ int old_max = n_basic_blocks;
+
+ /* Split all of the critical edges and split basic blocks that have
+ interesting code before a conditional branch. The latter is
+ necessary because the condition part of the block will need to be
+ reduced into the diamond, or looping region and the other part is
+ part of the set up. This makes a big difference to code
+ placement algorithms that want to drop code before a diamond. */
+
+ FOR_ALL_BB (bb)
+ {
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (EDGE_CRITICAL_P (e))
+ {
+ if (e->flags & EDGE_ABNORMAL)
+ {
+ if (dump_file)
+ fprintf (dump_file, "not splitting abnormal edge %d->%d\n",
+ e->src->index, e->dest->index);
+ }
+ else
+ split_edge (e);
+ }
+
+ if (!single_succ_p (bb))
+ split_block_before_cond_jump (bb);
+ }
+ FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
+ {
+ if (e->flags & EDGE_ABNORMAL)
+ {
+ if (dump_file)
+ fprintf (dump_file, "not splitting abnormal edge %d->%d\n",
+ e->src->index, e->dest->index);
+ }
+ else
+ split_edge (e);
+ }
+
+ FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
+ {
+ if (e->flags & EDGE_ABNORMAL)
+ {
+ if (dump_file)
+ fprintf (dump_file, "not splitting abnormal edge %d->%d\n",
+ e->src->index, e->dest->index);
+ }
+ else
+ split_edge (e);
+ }
+
+ add_noreturn_fake_exit_edges ();
+ connect_infinite_loops_to_exit ();
+
+ return n_basic_blocks - old_max;
+}
+
+static void
+initialize (bool split_blocks)
+{
+ basic_block bb;
+ int i;
+
+/* fprintf(stderr, "*****structure tree for %s\n", */
+/* lang_hooks.decl_printable_name (current_function_decl, 2)); */
+
+ /* Get rid of any previous analysis. */
+ delete_regions ();
+
+ for (i=0; i<((int)SWITCH_REGION)+1; i++)
+ region_stats[i] = 0;
+
+ if (split_blocks)
+ split_blocks_for_regions ();
+
+ /* Now that the edges have been split, recreate the dominator
+ information. */
+ calculate_dominance_info (CDI_DOMINATORS);
+ bitmap_obstack_initialize (&transient_region_obstack);
+ bitmap_obstack_initialize (&persistent_region_obstack);
+
+ visible_nodes = BITMAP_ALLOC (&transient_region_obstack);
+
+ /* Initialized the pass specific basic block information. */
+ FOR_ALL_BB (bb)
+ {
+ struct bb_temp *bb_info = create_info (bb);
+ bb->parent_region = NULL;
+ bb->prev_bb_in_region = NULL;
+ bb->next_bb_in_region = NULL;
+ bb->region_info = NULL;
+ bb_info->preord = -1;
+ bb_info->postord = -1;
+ }
+
+ /* We need enough spots to hold all of the original basic blocks +
+ the region nodes added. */
+ nodes_in_postord_size = ((n_basic_blocks) * 3) + 1;
+ nodes_in_postord = xcalloc (nodes_in_postord_size, sizeof (basic_block));
+
+ r_count = 0;
+ s_count = 0;
+ dfs_forward (ENTRY_BLOCK_PTR);
+ next_bitmap_index = s_count;
+ original_node_count = s_count;
+ next_region_index = 0;
+
+ /* This may not touch all of the blocks in the region. It will miss
+ those that are not reachable from the ENTEY_BLOCK_PTR. This is
+ deliberate, this is the set of blocks we are interested in. */
+ for (i=0; i<s_count; i++)
+ {
+ edge_iterator ei;
+ edge e;
+ struct bb_temp *bb_info;
+ bb = nodes_in_postord[i];
+ bb_info = (struct bb_temp *)bb->aux;
+
+ /* Build a bit vector representation of the preds and succs. */
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ {
+ struct bb_temp *d_info = (struct bb_temp *)e->dest->aux;
+ bitmap_set_bit (bb_info->succs, d_info->index);
+ }
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ {
+ struct bb_temp *s_info = (struct bb_temp *)e->src->aux;
+ bitmap_set_bit (bb_info->preds, s_info->index);
+ }
+ bitmap_copy (bb_info->visible_succs, bb_info->succs);
+ bitmap_copy (bb_info->visible_preds, bb_info->preds);
+
+ bitmap_set_bit (visible_nodes, bb_info->index);
+ }
+}
+
+/* Cleanup all of the transient data structures. */
+static void
+cleanup (void)
+{
+ basic_block * a_map =
+ (basic_block*)alloca ((size_t)(original_node_count *sizeof (basic_block)));
+ unsigned int i, j;
+ bitmap b_map = BITMAP_ALLOC (&transient_region_obstack);
+ basic_block bb;
+
+ for (i=0; i < next_bitmap_index; i++)
+ {
+ basic_block bb = nodes_in_postord[i];
+ struct bb_temp *bb_info = (struct bb_temp *)bb->aux;
+ unsigned int x_index;
+ bitmap_iterator bi;
+
+ if (get_region_type (bb) != ROOT_REGION)
+ {
+ basic_block p = bb->parent_region;
+ struct bb_temp *p_info;
+ gcc_assert (p);
+ p_info = (struct bb_temp *)p->aux;
+ gcc_assert (bitmap_bit_p (p_info->blocks_in_region, bb_info->index));
+ }
+
+ if (!single_block_region_p (bb))
+ {
+ /* The nodes in the bitmap are stored in an odd order
+ (mostly postord with the region nodes at the end).
+ However, we want to link them in preorder. The trick is
+ to radix sort the basic blocks. Note that there are
+ several nodes with the same preorder number (since the
+ entry block of the region shares its preorder number with
+ the region node), however, the nodes in a particular
+ region have unique preorder numbers. */
+
+ basic_block_region bb_region = bb->region_info;
+ bitmap_clear (b_map);
+ EXECUTE_IF_SET_IN_BITMAP(bb_info->blocks_in_region, 0, x_index, bi)
+ {
+ basic_block x = nodes_in_postord[x_index];
+ struct bb_temp *x_info = (struct bb_temp *)x->aux;
+ a_map [x_info->preord] = x;
+ bitmap_set_bit (b_map, x_info->preord);
+ }
+
+ EXECUTE_IF_SET_IN_BITMAP(b_map, 0, x_index, bi)
+ {
+ basic_block x = a_map[x_index];
+ gcc_assert (x->parent_region == bb);
+
+ if (bb_region->first_bb_in_region)
+ {
+ /* Add node at end. */
+ basic_block old_last_node = bb_region->last_bb_in_region;
+ old_last_node->next_bb_in_region = x;
+ bb_region->last_bb_in_region = x;
+ x->prev_bb_in_region = old_last_node;
+ x->next_bb_in_region = NULL;
+ }
+ else
+ {
+ /* First node in. */
+ bb_region->first_bb_in_region = x;
+ bb_region->last_bb_in_region = x;
+ x->prev_bb_in_region = NULL;
+ x->next_bb_in_region = NULL;
+ }
+ }
+ }
+
+ /* Move the edges to persistent storage. */
+ bb->num_region_preds = bitmap_count_bits (bb_info->visible_preds);
+ bb->region_preds = xcalloc (bb->num_region_preds, sizeof (basic_block));
+ j = 0;
+ EXECUTE_IF_SET_IN_BITMAP(bb_info->visible_preds, 0, x_index, bi)
+ {
+ bb->region_preds[j++] = nodes_in_postord[x_index];
+ }
+ bb->num_region_succs = bitmap_count_bits (bb_info->visible_succs);
+ bb->region_succs = xcalloc (bb->num_region_succs, sizeof (basic_block));
+ j = 0;
+ EXECUTE_IF_SET_IN_BITMAP(bb_info->visible_succs, 0, x_index, bi)
+ {
+ bb->region_succs[j++] = nodes_in_postord[x_index];
+ }
+ }
+
+ if (dump_file)
+ {
+ dump_structure_graph ();
+ for (i=0; i<=(int)SWITCH_REGION; i++)
+ fprintf (dump_file, "%s = %d\n",
+ get_region_type_name ((enum region_type)i),
+ region_stats[i]);
+ }
+
+ for (i=0; i < next_bitmap_index; i++)
+ {
+ basic_block bb = nodes_in_postord[i];
+ free(bb->aux);
+ bb->aux = NULL;
+ }
+
+ /* FIXME: It is silly to have to do this, but there are nodes that
+ are not reachable and they also need their aux field cleared. If
+ there were an easy way to get rid of these, any block with an aux
+ field at this point is unnecessary. */
+ FOR_ALL_BB (bb)
+ {
+ if (bb->aux)
+ {
+ gcc_assert (!bb->parent_region);
+ free(bb->aux);
+ bb->aux = NULL;
+ }
+ }
+
+ /* All region blocks are number with negative numbers. */
+ n_region_blocks = -(next_region_index - 1);
+
+ free_dominance_info (CDI_DOMINATORS);
+ free (nodes_in_postord);
+ visible_nodes = NULL;
+ bitmap_obstack_release (&transient_region_obstack);
+}
+
+static bool
+is_ancestor (basic_block x, basic_block y)
+{
+ struct bb_temp *x_info = (struct bb_temp *)x->aux;
+ struct bb_temp *y_info = (struct bb_temp *)y->aux;
+
+ return (x_info->preord <= y_info->preord)
+ && (x_info->postord >= y_info->postord);
+}
+
+/* Recurse down the set of region nodes to find an orignal basic block
+ that has the same dominance information as X. */
+
+static basic_block
+get_same_dominator_as (basic_block x)
+{
+ struct bb_temp *x_info = (struct bb_temp *)x->aux;
+ if (x_info->same_dominator_as)
+ return get_same_dominator_as (x_info->same_dominator_as);
+ else return x;
+}
+
+/*
+ CREATE_REGIONS is the main entry point for creating the structure graph.
+
+ Unlike the original algorithm, create_regions has 5 phases:
+ initialize, analyze_loops, analyze_structures,
+ build_recursive_info,and cleanup.
+
+ The analyze_loops, and analyze_structures are done in separate
+ passes so that latter can handle loop_exits as a structure type.
+ This can only be done after the loop is reduced.
+*/
+
+void
+create_regions (bool split_blocks)
+{
+ initialize (split_blocks);
+
+ analyze_loops ();
+
+ analyze_structures (ROOT_BLOCK_PTR, 0);
+
+ build_recursive_info (ROOT_BLOCK_PTR);
+
+ cleanup ();
+}
+
+/* Walk the region graph starting at X to build the
+ basic_blocks_in_region info. */
+
+static void
+build_recursive_info (basic_block x)
+{
+ struct bb_temp *x_info = (struct bb_temp *)x->aux;
+ bitmap_iterator bi;
+ unsigned int y_index;
+ bitmap basic_blocks_in_region = BITMAP_ALLOC (&persistent_region_obstack);
+ bitmap regions_in_region = BITMAP_ALLOC (&persistent_region_obstack);
+ x->region_info->basic_blocks_in_region = basic_blocks_in_region;
+ x->region_info->regions_in_region = regions_in_region;
+
+ EXECUTE_IF_SET_IN_BITMAP(x_info->blocks_in_region, 0, y_index, bi)
+ {
+ basic_block y = nodes_in_postord [y_index];
+ enum region_type rt = get_region_type (y);
+
+ if (rt == SINGLE_NODE_REGION)
+ bitmap_set_bit (basic_blocks_in_region, y->index);
+ else
+ {
+ build_recursive_info (y);
+ bitmap_ior_into (basic_blocks_in_region,
+ y->region_info->basic_blocks_in_region);
+
+ bitmap_set_bit (regions_in_region, -(y->index));
+ bitmap_ior_into (regions_in_region,
+ y->region_info->regions_in_region);
+ }
+ }
+}
+
+
+/* Helper function to new_improper_region. */
+
+static basic_block
+largest_region (basic_block x)
+{
+ struct bb_temp *x_info = (struct bb_temp *)x->aux;
+ if (x_info->in_region == NULL)
+ return x;
+ else
+ {
+ x_info->in_region = largest_region (x_info->in_region);
+ return x_info->in_region;
+ }
+}
+
+/*
+ If x->improper_nodes is nonempty at the top of create_regions, then
+ we must hide it in an improper region before continuing. Nodes
+ that were visible at the time they joined x->improper_nodes may
+ subsequently have been hidden in smaller improper regions, so
+ new__mproper_region applies the largest_region function to
+ construct the argument it passes to new_region.
+*/
+
+static basic_block
+new_improper_region (basic_block x)
+{
+ struct bb_temp *x_info = (struct bb_temp *)x->aux;
+ unsigned int x_index = x_info->index;
+
+ unsigned int y_index;
+ bitmap_iterator bi;
+ unsigned int entry_node_count = 0;
+
+ bitmap region = BITMAP_ALLOC (&transient_region_obstack);
+ basic_block * a_map =
+ (basic_block*)alloca ((size_t)(next_bitmap_index *sizeof (basic_block)));
+
+ region_details_u * block_info =
+ xmalloc (sizeof (struct improper_region_s));
+
+ bitmap_set_bit (region, x_index);
+
+ /* Build the region set. */
+ EXECUTE_IF_SET_IN_BITMAP(x_info->improper_nodes, 0, y_index, bi)
+ {
+ basic_block y = largest_region (nodes_in_postord[y_index]);
+ struct bb_temp *y_info = (struct bb_temp *)y->aux;
+ bitmap_set_bit (region, y_info->index);
+ }
+
+ /* Discover the entry nodes to the region. */
+ EXECUTE_IF_SET_IN_BITMAP(region, 0, y_index, bi)
+ {
+ basic_block y = nodes_in_postord[y_index];
+ struct bb_temp *y_info = (struct bb_temp *)y->aux;
+
+ if (bitmap_intersect_compl_p (y_info->visible_preds, region))
+ a_map[entry_node_count++] = y;
+ }
+
+ block_info->improper_region.entry_count = entry_node_count;
+ block_info->improper_region.entries =
+ xcalloc (entry_node_count, sizeof (basic_block));
+
+ memcpy (block_info->improper_region.entries,
+ a_map,
+ entry_node_count * sizeof (basic_block));
+
+ return new_region(x, region, IMPROPER_REGION, block_info);
+}
+
+/* Improper regions may be unavoidable, but we can keep them small by
+ calling minimize_improper_regions(x). When
+ minimize_improper_regions(x) begins, most of the successors of x
+ are earlier than x in postorder and have already been processed.
+ However, if y is a successor of x that has not already been
+ processed, then (x,y) is a back edge and receives special attention
+ later, when y is processed.
+
+ Several successors y of x may have y->improper_head != NULL. The
+ smallest postord of y->ImproperHead represents the smallest
+ improper region that must contain x if (x,y) is to be within the
+ region headed by y->improper_head. Once x has been put into this
+ region, it is automatically in larger regions and so need not be in
+ any other improper_nodes sets. Each y->improper_head dominates y
+ and is not x, so each y->improper_head dominates x. The various
+ y->improper_head are thus ancestor-comparable in the dominator
+ tree. Among such nodes, comparing postorder numbers is enough to
+ compute ancestry.
+*/
+
+static void
+minimize_improper_regions (basic_block x)
+{
+ struct bb_temp *x_info = (struct bb_temp *)x->aux;
+ basic_block h = x_info->improper_head;
+ unsigned int y_index;
+ bitmap_iterator bi;
+ int min_postord_seen;
+
+ if (h == NULL)
+ min_postord_seen = n_basic_blocks + 1;
+ else
+ {
+ struct bb_temp *h_info = (struct bb_temp *)h->aux;
+ min_postord_seen = h_info->postord;
+ }
+
+ EXECUTE_IF_SET_IN_BITMAP(x_info->visible_succs, 0, y_index, bi)
+ {
+ basic_block y = nodes_in_postord[y_index];
+ struct bb_temp *y_info = (struct bb_temp *)y->aux;
+ basic_block z = y_info->improper_head;
+
+ if (z != NULL)
+ {
+ struct bb_temp *z_info = (struct bb_temp *)z->aux;
+ if (min_postord_seen > z_info->postord)
+ {
+ min_postord_seen = z_info->postord;
+ h = z;
+ }
+ }
+ }
+
+ if (min_postord_seen != n_basic_blocks + 1)
+ {
+ struct bb_temp *h_info = (struct bb_temp *)h->aux;
+ x_info->improper_head = h;
+
+ /* Doing this to x after h is determined saves work and removes
+ a confusing dependence of intermediate results on order of
+ traversing succ. */
+
+ if (h_info->improper_nodes == NULL)
+ h_info->improper_nodes = BITMAP_ALLOC (&transient_region_obstack);
+ bitmap_set_bit (h_info->improper_nodes, x_info->index);
+ }
+}
+
+/* Find the loop structure of the function.
+ Loop Analysis
+
+ The algorithm is easier to understand if we begin by pretending
+ that CFG is already known to be reducible.
+
+ If only reducible graphs were to be considered, we could decide
+ whether each node x in a postorder traversal of the set NodesInCFG
+ of nodes of CFG is the head of a loop. If it is, then we call
+ NewRegion for the region type "ReducedLoop" before continuing the
+ traversal.
+
+ If x is indeed the head of a loop, then the (currently visible)
+ predecessors y of x include some descendants of x in the tree built
+ by depth-first search.
+
+ These are put into the initial set loop_body by the while loop
+ marked REDUCIBLE. The final set loop_body contains these
+ predecessors, any of their predecessors that are also descendants
+ of x, and so on.
+
+ Because irreducible control flow does arise in practice, we must
+ deal with it. If improper_nodes of x has become nonempty by the
+ time we visit x, then the step below marked IMPROPER resets x to
+ the new node returned by new_improper(x) which is just the result
+ of calling new_region for the set of nodes:
+
+ R = x union largest_region(y) for all y in x->improper_nodes
+
+ where the call largest_region(y) returns the node corresponding to
+ the largest region (among those found so far) that contains y.
+*/
+
+static void
+analyze_loops (void)
+{
+ int i;
+ int num_blocks = next_bitmap_index;
+ bitmap loop_body = BITMAP_ALLOC (&transient_region_obstack);
+ bitmap new_in_loop_body;
+ basic_block last_x = NULL;
+ unsigned int yy;
+ bitmap_iterator bi;
+
+ new_in_loop_body = BITMAP_ALLOC (&transient_region_obstack);
+
+ for (i=0; i<num_blocks; i++)
+ {
+ basic_block x = nodes_in_postord[i];
+ bool reduce = true;
+ unsigned int x_index, y_index, z_index;
+
+ struct bb_temp *x_info = (struct bb_temp *)x->aux;
+
+ /* IMPROPER Since improper regions are rare, this is null until
+ one is found. */
+ if (x_info->improper_nodes)
+ if (!bitmap_empty_p (x_info->improper_nodes))
+ x = new_improper_region (x);
+
+ x_info = (struct bb_temp *)x->aux;
+ x_index = x_info->index;
+
+ /* See if we can find a loop with header at x. */
+ bitmap_clear (loop_body);
+
+ EXECUTE_IF_SET_IN_BITMAP(x_info->visible_preds, 0, y_index, bi)
+ {
+ basic_block y = nodes_in_postord[y_index];
+ struct bb_temp *y_info = (struct bb_temp *)y->aux;
+
+ if (is_ancestor (x, y))
+ bitmap_set_bit (loop_body, y_info->index);
+ }
+
+ bitmap_copy (new_in_loop_body, loop_body);
+
+ /* At this point we have a loop but we have not follow all the
+ preds backwards to find all of the nodes in the loop. */
+ while (!bitmap_empty_p (new_in_loop_body))
+ {
+ y_index = bitmap_first_set_bit (new_in_loop_body);
+ bitmap_clear_bit (new_in_loop_body, y_index);
+
+ if (y_index != x_index)
+
+ /* In the usual case of a reducible graph, every node z
+ visited in the loop over the bitmap below is a
+ descendant of x and is added to LoopBody. If z != x,
+ then the predecessors of z are visited when a later
+ iteration of the outer loop sets y to z.
+ */
+ {
+ basic_block y = nodes_in_postord[y_index];
+ struct bb_temp *y_info = (struct bb_temp *)y->aux;
+ EXECUTE_IF_SET_IN_BITMAP(y_info->visible_preds, 0, z_index, bi)
+ {
+ if (!bitmap_bit_p (loop_body, z_index))
+ {
+ if (is_ancestor (x, nodes_in_postord[z_index]))
+ {
+ bitmap_set_bit(loop_body, z_index);
+ bitmap_set_bit(new_in_loop_body, z_index);
+ }
+ else
+ /* We still have a loop but it is an
+ irreducable loop. */
+ reduce = false;
+ }
+ }
+ }
+ }
+
+ if (!bitmap_empty_p (loop_body))
+ {
+ /* Suppose the loop_body computation visits a node z in
+ visible_preds[y] that is NOT a descendant of x. Because
+ y in loop_body with y != x, there is a cycle x --> y -->
+ x in CFG. The edge (z,y) enters this cycle at y rather
+ than at x, so we clear the flag reduce in this situation.
+ The combination of loop_body != EMPTYSET and reduce ==
+ true, on the other hand, tells us that a reduced loop has
+ been found.
+ */
+ if (reduce)
+ {
+ bitmap_set_bit (loop_body, x_info->index);
+ x = new_region(x, loop_body, REDUCED_LOOP_REGION, NULL);
+
+ /* The region node gets the bitmap. */
+ loop_body = BITMAP_ALLOC (&transient_region_obstack);
+ }
+ else
+ {
+ unsigned int h_index;
+ basic_block h = NULL;
+ struct bb_temp *h_info;
+
+ /* Nearest common ancestor in dominator tree. */
+ EXECUTE_IF_SET_IN_BITMAP(loop_body, 0, y_index, bi)
+ {
+ if (h == NULL)
+ {
+ h_index = bitmap_first_set_bit (loop_body);
+ h = nodes_in_postord[h_index];
+ }
+ else
+ /* The region nodes are not in the dominator
+ tree. However, each region node has the same
+ dominator information as the entry node of
+ it's region. We can find that node by looking
+ in the same_dominator_as field of the node.
+ However, if the nearest_common_ancestor comes
+ back with the other node, we want to go back
+ the other way. */
+ {
+ basic_block h_base = get_same_dominator_as (h);
+ basic_block y = nodes_in_postord[y_index];
+ basic_block y_base = get_same_dominator_as (y);
+ basic_block new_h
+ = nearest_common_dominator (CDI_DOMINATORS,
+ h_base, y_base);
+ if (new_h == h_base)
+ new_h = h;
+ else if (new_h == y_base)
+ new_h = y;
+ h = new_h;
+ }
+ }
+
+ h_info = (struct bb_temp *)h->aux;
+ if (h_info->improper_nodes == NULL)
+ h_info->improper_nodes = BITMAP_ALLOC (&transient_region_obstack);
+ bitmap_ior_into (h_info->improper_nodes, loop_body);
+
+ EXECUTE_IF_SET_IN_BITMAP(loop_body, 0, y_index, bi)
+ {
+ basic_block y = nodes_in_postord[y_index];
+ struct bb_temp *y_info = (struct bb_temp *)y->aux;
+ y_info->improper_head = h;
+ }
+ }
+ }
+
+ minimize_improper_regions (x);
+ last_x = x;
+ }
+
+ /* Make a copy of visible nodes because this will be associated with
+ the root node. */
+ bitmap_copy (loop_body, visible_nodes);
+
+ /* Find the node with the smallest preord number. This will be the
+ entry node for the region. */
+ i = next_bitmap_index;
+ EXECUTE_IF_SET_IN_BITMAP(loop_body, 0, yy, bi)
+ {
+ basic_block y = nodes_in_postord[yy];
+ struct bb_temp *y_info = (struct bb_temp *)y->aux;
+ if (y_info->preord < i)
+ {
+ i = y_info->preord;
+ last_x = y;
+ }
+ }
+
+ ROOT_BLOCK_PTR = new_region (last_x, loop_body, ROOT_REGION, NULL);
+
+ BITMAP_FREE (new_in_loop_body);
+}
+
+/* Structural Analysis
+
+ Structural analysis builds a control tree that recognizes common
+ structures like IF--THEN as well as loops. Compared with the tree
+ built by loop analysis, the structural control tree has more nodes,
+ but the nodes have simpler abstract graphs that tend to resemble
+ each other. For example, every recognized IF-THEN structure in
+ every program looks like every other IF-THEN structure. Many of
+ the abstract graphs are so very simple that much of the work of
+ analysis can be done in advance, when the compiler is written
+ rather than when the compiler is running.
+*/
+
+/* Blocks are strings of single-entry single-exit regions. New_block
+ may add x to an existing BLOCK region rather than start a new one.
+ We want to describe a block of four nodes as a plain sequence [x_0,
+ x_1, x_2, x_3], not as a right-branching binary tree [ x_0, [ x_1,
+ [ x_2, x_3 ] ] ]. If y already heads a BLOCK region R, then we add
+ x to R and return y rather than a new node.
+*/
+
+static basic_block
+new_block (basic_block x)
+{
+ struct bb_temp *x_info = (struct bb_temp *)x->aux;
+ unsigned int x_index = x_info->index;
+ unsigned int y_index = bitmap_first_set_bit (x_info->visible_succs);
+ basic_block y = nodes_in_postord[y_index];
+ struct bb_temp *y_info = (struct bb_temp *)y->aux;
+ unsigned int z_index;
+ bitmap_iterator bi;
+
+ /* Do not collapse the loop header, this was done in the loop
+ pass. */
+ if (bitmap_bit_p (y_info->visible_succs, x_index))
+ return NULL;
+ else return NULL;
+
+ /* Only branches into blocks are thru x. */
+ if (bitmap_count_bits (y_info->visible_preds) != 1)
+ return NULL;
+
+ if (get_region_type(y) == BLOCK_REGION)
+ {
+ /* If y is already a block region, incorporate x as the new
+ first node in region y rather than allocating a new
+ region. */
+ basic_block h = y->region_info->region_head;
+ struct bb_temp *h_info = (struct bb_temp *)h->aux;
+ unsigned int h_index = h_info->index;
+
+ if (x->parent_region)
+ remove_from_current_region (x);
+ x->parent_region = y;
+ bitmap_clear_bit (y_info->visible_preds, x_index);
+ bitmap_clear_bit (visible_nodes, x_index);
+
+ EXECUTE_IF_SET_IN_BITMAP(x_info->visible_preds, 0, z_index, bi)
+ {
+ basic_block z = nodes_in_postord[z_index];
+ struct bb_temp *z_info = (struct bb_temp *)z->aux;
+
+ bitmap_set_bit (y_info->visible_preds, z_index);
+ bitmap_clear_bit (z_info->visible_succs, x_index);
+ bitmap_set_bit (z_info->visible_succs, y_index);
+ }
+
+ bitmap_clear (x_info->visible_succs);
+ bitmap_set_bit (x_info->visible_succs, h_index);
+
+ bitmap_clear (h_info->visible_preds);
+ bitmap_set_bit (x_info->visible_preds, x_index);
+
+ bitmap_set_bit (y_info->blocks_in_region, x_index);
+ y->region_info->region_head = x;
+ return y;
+ }
+ else
+ {
+ bitmap region = BITMAP_ALLOC (&transient_region_obstack);
+ /* Build a new region that is the concatination of the two
+ blocks. */
+ bitmap_set_bit (region, x_index);
+ bitmap_set_bit (region, y_index);
+
+ return new_region (x, region, BLOCK_REGION, NULL);
+ }
+}
+
+/* Determine if the branch to T is marked as the TRUE edge. T should
+ only have one pred. */
+static bool
+true_branch_p (basic_block t)
+{
+ struct bb_temp *t_info = (struct bb_temp *)t->aux;
+ basic_block orig_t = nodes_in_postord[t_info->postord];
+ edge_iterator ei;
+ edge e;
+ FOR_EACH_EDGE (e, ei, orig_t->preds)
+ if (e->flags & EDGE_TRUE_VALUE)
+ return true;
+ return false;
+}
+
+/* Determine if the branch to T is marked as the FALSE edge. T should
+ only have one pred. */
+static bool
+false_branch_p (basic_block t)
+{
+ struct bb_temp *t_info = (struct bb_temp *)t->aux;
+ basic_block orig_t = nodes_in_postord[t_info->postord];
+ edge_iterator ei;
+ edge e;
+ FOR_EACH_EDGE (e, ei, orig_t->preds)
+ if (e->flags & EDGE_FALSE_VALUE)
+ return true;
+ return false;
+}
+
+/* At the top level there are two types of branches that are
+ considered here:
+
+ 1) branches where one edge exits the enclosing region. There are
+ three cases: branch2-exit, if-then-exit, and if-exit-else.
+
+ 2) branches where both edges stay in the region. There are two
+ cases: diamond if-then-else
+*/
+
+static basic_block
+new_branch (basic_block x, bitmap blocks_in_parent)
+{
+ struct bb_temp *x_info = (struct bb_temp *)x->aux;
+ bitmap_iterator bi;
+ unsigned int i = 0;
+
+ basic_block * targets = alloca (2 * sizeof (basic_block));
+ int exit_edge = -1;
+ unsigned int y_index;
+ unsigned int returns_found = 0;
+
+ /* Either 0 or 1 of the succs will be in the parent region. If it
+ is 1, this is a loop exit. The case where both edges exit cannot
+ occur or else the conditional itself would be outside the
+ loop. */
+
+ EXECUTE_IF_SET_IN_BITMAP(x_info->visible_succs, 0, y_index, bi)
+ {
+ basic_block y = nodes_in_postord[y_index];
+ struct bb_temp *y_info = (struct bb_temp *)y->aux;
+ targets[i] = y;
+ if (!bitmap_bit_p (blocks_in_parent, y_index))
+ exit_edge = i;
+
+ /* While critical edges have been split in the cfg, we could
+ still have this be true. This could happen if x has already
+ been reduced to an IF_THEN_EXIT or an IF-EXIT_ELSE
+ region. */
+ if (bitmap_count_bits (y_info->visible_preds) != 1)
+ return NULL;
+
+ /* Count a conditional return as an IF_EXIT like region. */
+ if (bitmap_count_bits (y_info->visible_succs))
+ {
+ unsigned int z_index =
+ bitmap_first_set_bit (y_info->visible_succs);
+ if (nodes_in_postord[z_index] == EXIT_BLOCK_PTR)
+ {