This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[patch] Local factoring algorithms
- From: Gábor Lóki <loki at inf dot u-szeged dot hu>
- To: gcc-patches at gcc dot gnu dot org
- Date: Tue, 23 Mar 2004 10:20:22 +0100
- Subject: [patch] Local factoring algorithms
Hi,
in my last mail I described some algorithms which we can use to save
some code size:
http://gcc.gnu.org/ml/gcc/2004-02/msg00981.html
The attached patch is a local factoring algorithm. This patch tries to
merge identical rtl insns by moving them to a point that pre- or
post-dominates all occurrences.
For example:
- "move rtl up":
***
if (A) {B; C; D; E; F;}
else {G; D; B; H;}
*** becomes ***
B; D;
if (A) {C; E; F;}
else {G; H;}
***
If and only if B and D insns can be moved from their original
blocks before the jump.
The same method is used for "move rtl down".
The algorithm is not restricted to 'if' cases, it works on any type of
cfg.
I have the following results with CSiBE:
-Os: arm-elf:0.15%, i386-elf:0.70%, i686-linux:0.69%, ppc-elf:0.17%
-O2: arm-elf:0.10%, i386-elf:0.81%, i686-linux:0.72%, ppc-elf:0.20%
The patch was bootstraped on i686-pc-linux-gnu. It was regtested on
{arm,i386,mips,ppc}-elf with no new failures.
On i686-linux I have some execution fail, because life_analysis deletes
some floating-point store. I don't know why. I just have noop moves for
that fstp insns. I will check this.
Although this patch is about code size it is also acceptable for
performance. Because it only moves and deletes insns.
What do you think about it?
Regards,
Gábor Lóki
PS:
We will soon send a more powerful factoring patch. It saves more than
2% when optimizing size!
2004-03-23 Gábor Lóki <loki@inf.u-szeged.hu>
* factoring.c: New file for local factoring
* factoring.h: Same
* Makefile.in: Add it
* flags.h: Declare factoring flag
* common.opt: Same
* opts.c: Same
* timevar.def: Same
* toplev.c: Same
* passes.c (rest_of_compilation, rest_of_factoring,
dump_file_info, dump_file_index): Registring
local factoring for dump files, add rest_of_factoring
function decl. and call
Index: gcc/gcc/common.opt
===================================================================
RCS file: /cvs/gcc/gcc/gcc/common.opt,v
retrieving revision 1.30
diff -u -r1.30 common.opt
--- gcc/gcc/common.opt 10 Mar 2004 06:02:50 -0000 1.30
+++ gcc/gcc/common.opt 22 Mar 2004 15:23:17 -0000
@@ -330,6 +330,10 @@
Common
Perform a number of minor, expensive optimizations
+ffactoring
+Common
+Perform factoring
+
ffast-math
Common
Index: gcc/gcc/opts.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/opts.c,v
retrieving revision 1.61
diff -u -r1.61 opts.c
--- gcc/gcc/opts.c 10 Mar 2004 06:02:53 -0000 1.61
+++ gcc/gcc/opts.c 22 Mar 2004 15:23:37 -0000
@@ -971,6 +974,10 @@
case OPT_fdump_unnumbered:
flag_dump_unnumbered = value;
+ break;
+
+ case OPT_ffactoring:
+ flag_factoring = value;
break;
case OPT_feliminate_dwarf2_dups:
Index: gcc/gcc/flags.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/flags.h,v
retrieving revision 1.134
diff -u -r1.134 flags.h
--- gcc/gcc/flags.h 10 Mar 2004 06:02:51 -0000 1.134
+++ gcc/gcc/flags.h 22 Mar 2004 15:24:46 -0000
@@ -727,9 +727,11 @@
/* Nonzero if we should track variables. */
extern int flag_var_tracking;
+/* Nonzero means enable all factoring algorithms. */
+extern int flag_factoring;
+
/* A string that's used when a random name is required. NULL means
to make it really random. */
-
extern const char *flag_random_seed;
/* The version of the C++ ABI in use. The following values are
Index: gcc/gcc/Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.1261
diff -u -r1.1261 Makefile.in
--- gcc/gcc/Makefile.in 9 Mar 2004 01:53:24 -0000 1.1261
+++ gcc/gcc/Makefile.in 23 Mar 2004 08:53:48 -0000
@@ -857,7 +857,7 @@
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 optabs.o options.o opts.o params.o postreload.o predict.o \
- print-rtl.o print-tree.o value-prof.o var-tracking.o \
+ print-rtl.o print-tree.o value-prof.o var-tracking.o factoring.o \
profile.o ra.o ra-build.o ra-colorize.o ra-debug.o ra-rewrite.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 \
@@ -1550,7 +1550,7 @@
graph.h $(LOOP_H) except.h $(REGS_H) $(TIMEVAR_H) value-prof.h \
$(PARAMS_H) $(TM_P_H) reload.h dwarf2asm.h $(TARGET_H) \
langhooks.h insn-flags.h cfglayout.h real.h cfgloop.h \
- hosthooks.h $(LANGHOOKS_DEF_H) cgraph.h $(COVERAGE_H) alloc-pool.h
+ hosthooks.h $(LANGHOOKS_DEF_H) cgraph.h $(COVERAGE_H) alloc-pool.h factoring.h
main.o : main.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) toplev.h
@@ -1691,6 +1691,8 @@
$(BASIC_BLOCK_H) output.h sbitmap.h alloc-pool.h $(FIBHEAP_H) $(HASHTAB_H)
conflict.o : conflict.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(OBSTACK_H) \
$(HASHTAB_H) $(RTL_H) hard-reg-set.h $(BASIC_BLOCK_H)
+factoring.o : factoring.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) coretypes.h $(TM_H) \
+ $(BASIC_BLOCK_H) flags.h
profile.o : profile.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
$(TREE_H) flags.h output.h $(REGS_H) $(EXPR_H) function.h \
toplev.h $(BASIC_BLOCK_H) $(COVERAGE_H) $(TREE_H) value-prof.h
Index: gcc/gcc/timevar.def
===================================================================
RCS file: /cvs/gcc/gcc/gcc/timevar.def,v
retrieving revision 1.25
diff -u -r1.25 timevar.def
--- gcc/gcc/timevar.def 6 Feb 2004 20:03:43 -0000 1.25
+++ gcc/gcc/timevar.def 22 Mar 2004 15:25:28 -0000
@@ -93,6 +93,7 @@
DEFTIMEVAR (TV_REORDER_BLOCKS , "reorder blocks")
DEFTIMEVAR (TV_SHORTEN_BRANCH , "shorten branches")
DEFTIMEVAR (TV_REG_STACK , "reg stack")
+DEFTIMEVAR (TV_FACTORING , "factoring")
DEFTIMEVAR (TV_FINAL , "final")
DEFTIMEVAR (TV_SYMOUT , "symout")
DEFTIMEVAR (TV_VAR_TRACKING , "variable tracking")
Index: gcc/gcc/passes.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/passes.c,v
retrieving revision 2.3
diff -u -r2.3 passes.c
--- gcc/gcc/passes.c 3 Mar 2004 16:32:38 -0000 2.3
+++ gcc/gcc/passes.c 22 Mar 2004 15:25:46 -0000
@@ -80,6 +80,7 @@
#include "coverage.h"
#include "value-prof.h"
#include "alloc-pool.h"
+#include "factoring.h"
#if defined (DWARF2_UNWIND_INFO) || defined (DWARF2_DEBUGGING_INFO)
#include "dwarf2out.h"
@@ -167,6 +168,7 @@
DFI_branch_target_load,
DFI_sched2,
DFI_stack,
+ DFI_factoring,
DFI_vartrack,
DFI_mach,
DFI_dbr,
@@ -178,7 +180,7 @@
Remaining -d letters:
- " e m q "
+ " e m "
" K O Q WXY "
*/
@@ -220,6 +222,7 @@
{ "btl", 'd', 1, 0, 0 }, /* Yes, duplicate enable switch. */
{ "sched2", 'R', 1, 0, 0 },
{ "stack", 'k', 1, 0, 0 },
+ { "factoring", 'q', 1, 0, 0 },
{ "vartrack", 'V', 1, 0, 0 }, /* Yes, duplicate enable switch. */
{ "mach", 'M', 1, 0, 0 },
{ "dbr", 'd', 0, 0, 0 },
@@ -475,6 +478,26 @@
ggc_collect ();
}
+/* Run the local factoring optimization. */
+static void
+rest_of_factoring (tree decl, rtx insns)
+{
+ timevar_push (TV_FACTORING);
+ open_dump_file (DFI_factoring, decl);
+
+ factoring (0, down);
+ factoring (0, up);
+
+ life_analysis (insns, dump_file, PROP_FINAL);
+
+ cleanup_cfg (CLEANUP_EXPENSIVE | CLEANUP_UPDATE_LIFE);
+
+ close_dump_file (DFI_factoring, print_rtl_with_bb, insns);
+ timevar_pop (TV_FACTORING);
+
+ ggc_collect ();
+}
+
#ifdef DELAY_SLOTS
/* Run delay slot optimization. */
static void
@@ -1991,6 +2014,10 @@
#ifdef STACK_REGS
rest_of_handle_stack_regs (decl, insns);
#endif
+
+ /* Local factoring algorithms. */
+ if (flag_factoring)
+ rest_of_factoring (decl, insns);
compute_alignments ();
Index: gcc/gcc/toplev.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/toplev.c,v
retrieving revision 1.887
diff -u -r1.887 toplev.c
--- gcc/gcc/toplev.c 3 Mar 2004 16:32:38 -0000 1.887
+++ gcc/gcc/toplev.c 22 Mar 2004 15:25:57 -0000
@@ -856,6 +857,9 @@
the ABI become the default version of the ABI. */
int flag_abi_version = 2;
+
+/* Nonzero means enable all factoring algorithms. */
+int flag_factoring = 0;
/* The user symbol prefix after having resolved same. */
const char *user_label_prefix;
Index: gcc/gcc/factoring.c
===================================================================
RCS file: /cvs/gcc/gcc/factoring.c
diff -N gcc/gcc/factoring.c
*** /dev/null 1970-01-01 01:00:00.000000000 +0100
--- gcc/gcc/factoring.c 2004-03-22 16:05:24.000000000 +0100
***************
*** 0 ****
--- 1,1265 ----
+ /* Local factoring algorithms in RTL.
+ Copyright (C) 2004 Free Software Foundation, Inc.
+
+ This file is part of GCC.
+
+ GCC is free software; you can redistribute it and/or modify it under the
+ terms of the GNU General Public License as published by the Free Software
+ Foundation; either version 2, or (at your option) any later version.
+
+ GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+ WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
+ details.
+
+ You should have received a copy of the GNU General Public License along
+ with GCC; see the file COPYING. If not, write to the Free Software
+ Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
+
+ #include "config.h"
+ #include "system.h"
+ #include "coretypes.h"
+ #include "tm.h"
+ #include "rtl.h"
+ #include "basic-block.h"
+ #include "resource.h"
+ #include "flags.h"
+ #include "factoring.h"
+
+ static int gain;
+
+ typedef struct bbDecorator_def
+ {
+ struct bbDecorator_def *next_brother;
+ struct bbDecorator_def *prev_brother;
+ basic_block curr; /* the decorated basic block */
+ struct bbDecorator_def *next_analogous;
+ struct bbDecorator_def *prev_analogous;
+ struct bbDecorator_def *prev_decorator, *next_decorator;
+ rtx moveable_insn;
+ int last_depth;
+ } *bbDecorator;
+
+ #define CLEAR_DEFUSE_INFO(RES) \
+ do { (RES)->def_memory = (RES)->memory = (RES)->unch_memory = (RES)->volatil = (RES)->def_cc = (RES)->cc = 0; \
+ CLEAR_REG_SET ((RES)->regs); CLEAR_REG_SET ((RES)->def_regs); (RES)->pc = (RES)->def_pc = 0;} while (0)
+
+ struct defuse_info
+ {
+ char memory; /* Insn sets or needs a memory location. */
+ char def_memory; /* Insn sets a memory location. */
+ char unch_memory; /* Insn sets of needs a "unchanging" MEM. */
+ char volatil; /* Insn sets or needs a volatile memory loc. */
+ char cc; /* Insn sets or needs the condition codes. */
+ char def_cc; /* Insn sets the condition codes. */
+ char pc; /* Insn sets or needs pc. */
+ char def_pc; /* Insn sets pc. */
+ regset regs; /* Which registers are set or needed. */
+ regset def_regs; /* Which registers are set. */
+ };
+
+ /* Local factoring functions in direction 'up' */
+ static int find_bb_in_pred_blocks (basic_block, basic_block);
+ static void insert_insn_end_of_basic_block (rtx, basic_block);
+ static int compare_pred_blocks (basic_block, basic_block);
+ static void collect_full_pred_brother (bbDecorator);
+ static int factoring_up (int, bbDecorator);
+ static rtx find_first_from_begin (bbDecorator decorator, int);
+ static int moveable_from_begin (rtx);
+ static int find_insn_from_begin (rtx, bbDecorator, int);
+ static int find_set_cc (rtx);
+
+ /* Local factoring functions in direction 'down' */
+ static int find_bb_in_succ_blocks (basic_block, basic_block);
+ static int compare_succ_blocks (basic_block, basic_block);
+ static int factoring_up (int, bbDecorator);
+ static void insert_insn_begin_of_basic_block (rtx, basic_block);
+ static int find_insn_from_end (rtx, bbDecorator, int);
+ static int moveable_from_end (rtx);
+ static rtx find_first_from_end (bbDecorator decorator, int);
+ static void modifying_concatenation (bbDecorator, bbDecorator);
+ static void modify_jump_labels (basic_block, bbDecorator, rtx);
+ static basic_block create_basic_block_by_factoring (bbDecorator);
+ static bbDecorator insert_new_bbDecorator (bbDecorator, basic_block);
+
+ /* Common functions */
+ static int num_of_succ_blocks (basic_block);
+ static int num_of_pred_blocks (basic_block);
+ static bbDecorator init (bbDecorator);
+ static void free_bbDecorator_list (bbDecorator);
+ static void delete_brothers (bbDecorator);
+ static void delete_analogous (bbDecorator);
+ static void collect_brother (bbDecorator,
+ int (*f) (basic_block, basic_block));
+ static int commutable_insns (rtx, rtx);
+ static void cost_analyzer (bbDecorator, int (*f) (basic_block));
+ static void cost_analyzer_1 (bbDecorator, int (*f) (basic_block));
+ static void find_defuse_info (rtx, int, struct defuse_info *);
+ static int find_ABNORMAL_EDGE (bbDecorator);
+
+ /* The number of the succ basic blocks of bb. */
+ static int
+ num_of_succ_blocks (basic_block bb)
+ {
+ int num = 0;
+ edge e;
+ for (e = bb->succ; e; e = e->succ_next)
+ num++;
+ return num;
+ }
+
+ /* The number of the pred basic blocks of bb. */
+ static int
+ num_of_pred_blocks (basic_block bb)
+ {
+ int num = 0;
+ edge e;
+ for (e = bb->pred; e; e = e->pred_next)
+ num++;
+ return num;
+ }
+
+ /* Find the basic block 'what' between the pred blocks of 'where'. */
+ static int
+ find_bb_in_pred_blocks (basic_block what, basic_block where)
+ {
+ edge e;
+ for (e = where->pred; e; e = e->pred_next)
+ if (what == e->src)
+ return 1;
+ return 0;
+ }
+
+ /* Compare the set of pred blocks of bb1 and bb2. If it isn't different
+ return 1. */
+ static int
+ compare_pred_blocks (basic_block bb1, basic_block bb2)
+ {
+ edge e;
+ if (num_of_pred_blocks (bb1) != num_of_pred_blocks (bb2))
+ return 0;
+ for (e = bb1->pred; e; e = e->pred_next)
+ if (!find_bb_in_pred_blocks (e->src, bb2))
+ return 0;
+ return 1;
+ }
+
+ /*Insert insn into bb. If bb's last instruction is jump, insn will be before
+ the jump instruction. */
+ static void
+ insert_insn_end_of_basic_block (rtx insn, basic_block bb)
+ {
+ rtx last = BB_END (bb);
+
+ if (JUMP_P (last))
+ {
+ if (find_set_cc (PREV_INSN (last)))
+ add_insn_before (insn, PREV_INSN (last));
+ else
+ add_insn_before (insn, last);
+ }
+ else
+ add_insn_after (insn, last);
+ }
+
+ /* Insert insn into bb to the first possible place.*/
+ static void
+ insert_insn_begin_of_basic_block (rtx insn, basic_block bb)
+ {
+ rtx first = BB_HEAD (bb);
+ while (!INSN_P (first))
+ first = NEXT_INSN (first);
+
+ add_insn_before (insn, first);
+ }
+
+ /* Find the basic block 'what' between the succ blocks of 'where'. */
+ static int
+ find_bb_in_succ_blocks (basic_block what, basic_block where)
+ {
+ edge e;
+ for (e = where->succ; e; e = e->succ_next)
+ if (what == e->dest)
+ return 1;
+ return 0;
+ }
+
+ /* Compare the set of succ blocks of bb1 and bb2. If it isn't different
+ return 1 */
+ static int
+ compare_succ_blocks (basic_block bb1, basic_block bb2)
+ {
+ edge e;
+ if (num_of_succ_blocks (bb1) != num_of_succ_blocks (bb2))
+ return 0;
+ for (e = bb1->succ; e; e = e->succ_next)
+ if (!find_bb_in_succ_blocks (e->dest, bb2))
+ return 0;
+ return 1;
+ }
+
+ /* Initialization of the chain of bbDecorator! For each bb there is a
+ bbDecorator in the chain. */
+ static bbDecorator
+ init (bbDecorator decorator)
+ {
+ basic_block bb;
+ int out_of_mem = 0;
+
+ bbDecorator last = NULL;
+ FOR_EACH_BB (bb)
+ {
+ bbDecorator temp;
+
+ temp =
+ (struct bbDecorator_def *) xmalloc (sizeof (struct bbDecorator_def));
+ if (!temp)
+ {
+ out_of_mem = 1;
+ break;
+ }
+ memset (temp, 0, sizeof (*temp));
+ temp->curr = bb;
+ if (!decorator)
+ {
+ decorator = temp;
+ last = temp;
+ }
+ else
+ {
+ last->next_decorator = temp;
+ temp->prev_decorator = last;
+ last = temp;
+ }
+ }
+ if (out_of_mem)
+ {
+ free_bbDecorator_list (decorator);
+ return NULL;
+ }
+ return decorator;
+ }
+
+ /* Collection of the blocks which have same pred/succ set. */
+ static void
+ collect_brother (bbDecorator decorator, int (*f) (basic_block, basic_block))
+ {
+ bbDecorator first, second;
+ for (first = decorator; first; first = first->next_decorator)
+ {
+ for (second = first->next_decorator; second;
+ second = second->next_decorator)
+ {
+ if ((*f) (first->curr, second->curr))
+ {
+ first->next_brother = second;
+ second->prev_brother = first;
+ break;
+ }
+ }
+ }
+ }
+
+ /*Deletion of the 'brother' relations from first*/
+ static void
+ delete_brothers (bbDecorator first)
+ {
+ bbDecorator last = NULL;
+ bbDecorator temp;
+ for (temp = first; temp; temp = temp->next_brother)
+ {
+ if (last)
+ last->next_brother = NULL;
+ last = temp;
+ temp->prev_brother = NULL;
+ }
+ }
+
+ /*Deletion of the 'analogous' relations from first*/
+ static void
+ delete_analogous (bbDecorator first)
+ {
+ bbDecorator last = NULL;
+ bbDecorator temp;
+ for (temp = first; temp; temp = temp->next_analogous)
+ {
+ if (last)
+ last->next_analogous = NULL;
+ last = temp;
+ temp->prev_analogous = NULL;
+ }
+ }
+
+ /*Free allocated memory*/
+ static void
+ free_bbDecorator_list (bbDecorator decorator)
+ {
+ bbDecorator temp;
+ for (temp = decorator; temp;)
+ {
+ bbDecorator last = temp;
+ temp = temp->next_decorator;
+ free (last);
+ }
+ }
+
+ /*Selection of the 'brothers'. */
+ static void
+ collect_full_pred_brother (bbDecorator decorator)
+ {
+ bbDecorator temp;
+
+ collect_brother (decorator, compare_pred_blocks);
+
+ for (temp = decorator; temp; temp = temp->next_decorator)
+ {
+ if ((!temp->prev_brother) && temp->next_brother)
+ {
+ int num_of_brother = 0;
+ bbDecorator temp2;
+ edge f;
+
+ for (temp2 = temp; temp2; temp2 = temp2->next_brother)
+ num_of_brother++;
+
+ for (f = (temp->curr)->pred; f; f = f->pred_next)
+ if (num_of_succ_blocks (f->src) != num_of_brother)
+ {
+ delete_brothers (temp);
+ break;
+ }
+ }
+ }
+ }
+
+ /* Selection of the 'brothers' by cost info. */
+ static void
+ cost_analyzer_1 (bbDecorator temp, int (*f) (basic_block))
+ {
+ int num_of_brother = 0;
+ bbDecorator temp2;
+
+ for (temp2 = temp; temp2; temp2 = temp2->next_brother)
+ num_of_brother++;
+
+ if ((*f) (temp->curr) >= num_of_brother)
+ delete_brothers (temp);
+ }
+
+ /*Selection of the 'brothers' by cost info*/
+ static void
+ cost_analyzer (bbDecorator decorator, int (*f) (basic_block))
+ {
+ bbDecorator temp;
+ for (temp = decorator; temp; temp = temp->next_decorator)
+ {
+ if ((!temp->prev_brother) && temp->next_brother)
+ cost_analyzer_1 (temp, f);
+ }
+ }
+
+
+ /* Local factoring 'up' function: it returns with 1, if the insn is moveable
+ from the block. */
+ static int
+ moveable_from_begin (rtx insn)
+ {
+ basic_block bb = BLOCK_FOR_INSN (insn);
+ rtx head = BB_HEAD (bb);
+ rtx prev;
+
+ if (insn == head)
+ return 1;
+
+ prev = PREV_INSN (insn);
+
+ while (prev)
+ {
+ if (INSN_P (prev))
+ if (!commutable_insns (insn, prev))
+ return 0;
+ if (prev == head)
+ prev = NULL;
+ else
+ prev = PREV_INSN (prev);
+ }
+ return 1;
+ }
+
+ /* Local factoring 'down' function: it returns with 1, if the insn is moveable
+ from the block. */
+ static int
+ moveable_from_end (rtx insn)
+ {
+ basic_block bb = BLOCK_FOR_INSN (insn);
+ rtx end = BB_END (bb);
+ rtx next;
+
+ if (insn == end)
+ return 1;
+
+ next = NEXT_INSN (insn);
+
+ while (next)
+ {
+ if (INSN_P (next) && (!commutable_insns (insn, next)))
+ return 0;
+ if (next == end)
+ next = NULL;
+ else
+ next = NEXT_INSN (next);
+ }
+ return 1;
+ }
+
+ /*Finding of the first not examined insn in the block, which would be good to
+ move into the pred bb. If we find a jump or call insn, this function return
+ with NULL_RTX, and there is no more investigation in this block to try
+ moving an other insn. */
+ static rtx
+ find_first_from_begin (bbDecorator decorator, int max_depth)
+ {
+ basic_block bb = decorator->curr;
+ rtx insn;
+ int depth = 0;
+ decorator->moveable_insn = NULL_RTX;
+ for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
+ {
+ if (!INSN_P (insn))
+ continue;
+ if (GET_CODE (insn) == CALL_INSN)
+ return NULL_RTX;
+ if (find_set_cc (insn))
+ depth++;
+ else if (moveable_from_begin (insn))
+ {
+ if (depth == decorator->last_depth)
+ {
+ decorator->moveable_insn = insn;
+ return (insn);
+ }
+ else
+ depth++;
+ }
+ if (depth == max_depth)
+ break;
+ }
+ return NULL_RTX;
+ }
+
+ /* Like find_first_from_begin in case of direction 'down'. */
+ static rtx
+ find_first_from_end (bbDecorator decorator, int max_depth)
+ {
+ basic_block bb = decorator->curr;
+ rtx insn;
+ int depth = 0;
+ decorator->moveable_insn = NULL_RTX;
+ for (insn = BB_END (bb); insn != BB_HEAD (bb); insn = PREV_INSN (insn))
+ {
+ if (!INSN_P (insn) || JUMP_P (insn))
+ continue;
+ if (GET_CODE (insn) == CALL_INSN)
+ return NULL_RTX;
+
+ if (moveable_from_end (insn))
+ {
+ if (depth == decorator->last_depth)
+ {
+ decorator->moveable_insn = insn;
+ return (insn);
+ }
+ else
+ depth++;
+ }
+ if (depth == max_depth)
+ break;
+ }
+ return NULL_RTX;
+ }
+
+ /* Finding of an instruction in the basic block decorator->curr, which is
+ equal with 'insn' and which is outsourcable from the bb. Direction 'up'. */
+ static int
+ find_insn_from_begin (rtx insn, bbDecorator decorator, int max_depth)
+ {
+ basic_block bb = decorator->curr;
+ rtx tmp;
+ int depth = 0;
+
+ for (tmp = BB_HEAD (bb); tmp != BB_END (bb); tmp = NEXT_INSN (tmp))
+ {
+ if (!(INSN_P (tmp)))
+ continue;
+ if (GET_CODE (tmp) == CALL_INSN)
+ return 0;
+ if (rtx_equal_p (PATTERN (tmp), PATTERN (insn)))
+ {
+ decorator->moveable_insn = tmp;
+ return 1;
+ }
+ depth++;
+ if (depth == max_depth)
+ return 0;
+
+ if (!commutable_insns (insn, tmp))
+ return 0;
+ }
+ return 0;
+ }
+
+ /* Like find_insn_from_begin just in the case of direction 'down'. */
+ static int
+ find_insn_from_end (rtx insn, bbDecorator decorator, int max_depth)
+ {
+ basic_block bb = decorator->curr;
+ rtx tmp;
+ int depth = 0;
+
+ for (tmp = BB_END (bb); tmp != BB_HEAD (bb); tmp = PREV_INSN (tmp))
+ {
+ if ((!(INSN_P (tmp))) || JUMP_P (tmp))
+ continue;
+ if (GET_CODE (tmp) == CALL_INSN)
+ return 0;
+ if (rtx_equal_p (PATTERN (tmp), PATTERN (insn)))
+ {
+ decorator->moveable_insn = tmp;
+ return (1);
+ }
+ depth++;
+ if (depth == max_depth)
+ return 0;
+ if (!commutable_insns (insn, tmp))
+ return 0;
+ }
+ return 0;
+ }
+
+ /* If insn and insn2 are commutable, return 1. */
+ static int
+ commutable_insns (rtx insn, rtx insn2)
+ {
+ int result = 1;
+ int i;
+ struct defuse_info res_insn;
+ struct defuse_info res_insn2;
+ regset_head regsh, regs_insn_h;
+ regset_head regsh2, regs_insn_h2;
+
+ if ((CALL_INSN == GET_CODE (insn)) || (CALL_INSN == GET_CODE (insn2)))
+ return 0;
+
+ res_insn.regs = INITIALIZE_REG_SET (regsh);
+ res_insn.def_regs = INITIALIZE_REG_SET (regs_insn_h);
+ res_insn2.regs = INITIALIZE_REG_SET (regsh2);
+ res_insn2.def_regs = INITIALIZE_REG_SET (regs_insn_h2);
+
+ CLEAR_DEFUSE_INFO (&res_insn);
+ CLEAR_DEFUSE_INFO (&res_insn2);
+ find_defuse_info (insn, 0, &res_insn);
+ find_defuse_info (insn2, 0, &res_insn2);
+ if ((res_insn.cc && res_insn2.def_cc) || (res_insn.def_cc && res_insn2.cc)
+ || (res_insn.memory && res_insn2.def_memory) || (res_insn.def_memory
+ && res_insn2.memory)
+ || res_insn.volatil || res_insn2.volatil || res_insn.unch_memory
+ || res_insn2.unch_memory || (res_insn.pc && (!JUMP_P (insn)))
+ || (res_insn2.pc && (!JUMP_P (insn2))))
+ result = 0;
+
+ for (i = 0; i < max_reg_num (); i++)
+ {
+ if (REGNO_REG_SET_P (res_insn.regs, i)
+ && REGNO_REG_SET_P (res_insn2.def_regs, i))
+ {
+ result = 0;
+ break;
+ }
+ if (REGNO_REG_SET_P (res_insn2.regs, i)
+ && REGNO_REG_SET_P (res_insn.def_regs, i))
+ {
+ result = 0;
+ break;
+ }
+ }
+
+
+ FREE_REG_SET (res_insn.regs);
+ FREE_REG_SET (res_insn.def_regs);
+ FREE_REG_SET (res_insn2.regs);
+ FREE_REG_SET (res_insn2.def_regs);
+ return (result);
+ }
+
+ /* If we create a new basic block, we must complement it with a bbDecorator. */
+ static bbDecorator
+ insert_new_bbDecorator (bbDecorator decorator, basic_block new_bb)
+ {
+ bbDecorator temp;
+ bbDecorator temp2 = NULL;
+
+ temp = decorator;
+ while (temp->next_decorator)
+ {
+ temp = temp->next_decorator;
+ }
+
+ temp2 =
+ (struct bbDecorator_def *) xmalloc (sizeof (struct bbDecorator_def));
+
+ memset (temp2, 0, sizeof (*temp2));
+ temp2->curr = new_bb;
+ temp2->prev_decorator = temp;
+ temp->next_decorator = temp2;
+ return (temp2);
+ }
+
+ /* If we insert a new basic block, the relations between the basic blocks will
+ be changed, so we must modifying some concatenation */
+ static void
+ modifying_concatenation (bbDecorator first, bbDecorator new_bb)
+ {
+ bbDecorator last_brother = first->prev_brother;
+ bbDecorator first_brother = NULL;
+ bbDecorator last_analogous = first;
+ bbDecorator temp;
+
+ if (first->prev_brother)
+ {
+ (first->prev_brother)->next_brother = NULL;
+ first->prev_brother = NULL;
+ }
+ for (temp = first->next_brother; temp; temp = temp->next_brother)
+ {
+ if (temp->prev_brother == last_analogous)
+ {
+ if (last_analogous->next_analogous != temp)
+ {
+ (temp->prev_brother)->next_brother = NULL;
+ temp->prev_brother = last_brother;
+ if (last_brother)
+ {
+ if (last_brother->next_brother)
+ (last_brother->next_brother)->prev_brother = NULL;
+ last_brother->next_brother = temp;
+ }
+ last_brother = temp;
+ if (!first_brother)
+ first_brother = temp;
+ }
+ else
+ {
+ last_analogous = temp;
+ }
+ }
+ else if (temp->prev_brother == last_brother)
+ {
+ if (last_analogous->next_analogous != temp)
+ {
+ last_brother = temp;
+ if (!first_brother)
+ first_brother = temp;
+ }
+ else
+ {
+ last_analogous = temp;
+ }
+ }
+ }
+ if (last_brother)
+ {
+ last_brother->next_brother = new_bb;
+ new_bb->prev_brother = last_brother;
+ }
+
+ delete_brothers (first);
+ for (temp = first; temp; temp = temp->next_analogous)
+ {
+ temp->prev_brother = temp->prev_analogous;
+ temp->next_brother = temp->next_analogous;
+ }
+ delete_analogous (first);
+ }
+
+ /* Main function of local factoring in direction 'up'. */
+ static int
+ factoring_up (int depth, bbDecorator decorator)
+ {
+ bbDecorator temp;
+ int change = 0;
+ for (temp = decorator; temp; temp = temp->next_decorator)
+ {
+
+ if ((!temp->prev_brother) && (temp->next_brother))
+ {
+ bbDecorator temp2;
+ rtx insn = NULL;
+ int error = 0;
+ edge e;
+ insn = find_first_from_begin (temp, depth);
+
+ if (!insn)
+ {
+ delete_brothers (temp);
+ continue;
+ }
+ /* Finding equal instruction in the concatenated basic blocks */
+ for (temp2 = temp->next_brother; temp2; temp2 = temp2->next_brother)
+ if (!find_insn_from_begin (insn, temp2, depth))
+ {
+ error = 1;
+ temp->last_depth++;
+ break;
+ }
+
+ if (error)
+ continue;
+
+ /* Verifying the insn if it is insertable after the end of pred
+ functions */
+ for (e = (temp->curr)->pred; e; e = e->pred_next)
+ {
+ if (!JUMP_P (BB_END (e->src)))
+ continue;
+ if (!commutable_insns (insn, BB_END (e->src)))
+ {
+ error = 1;
+ break;
+ }
+ if (find_set_cc (PREV_INSN (BB_END (e->src))))
+ if (!commutable_insns (insn, PREV_INSN (BB_END (e->src))))
+ {
+ error = 1;
+ break;
+ }
+ }
+
+ if (error)
+ continue;
+
+ if (!error)
+ {
+ /* moving the insn */
+ edge e;
+
+ for (e = (temp->curr)->pred; e; e = e->pred_next)
+ {
+ rtx new_insn =
+ make_insn_raw (PATTERN (temp->moveable_insn));
+ insert_insn_end_of_basic_block (new_insn, e->src);
+ gain--;
+ }
+
+ for (temp2 = temp; temp2; temp2 = temp2->next_brother)
+ {
+ rtx rinsn = temp2->moveable_insn;
+ temp2->moveable_insn = NULL;
+
+ remove_insn (rinsn);
+ gain++;
+ }
+
+ change = 1;
+ }
+ }
+ }
+ return (change);
+ }
+
+ /*Main function of local factoring in direction 'down'*/
+ static int
+ factoring_down (int depth, bbDecorator decorator)
+ {
+ int change = 0;
+
+ bbDecorator temp;
+ for (temp = decorator; temp; temp = temp->next_decorator)
+ {
+ if (temp->next_brother)
+ {
+ bbDecorator temp2;
+ rtx insn = NULL;
+
+ int insert_bb = 0;
+ int num_of_next_bb = num_of_succ_blocks (temp->curr);
+ int num_of_good_bb = 0;
+ bbDecorator last_brother;
+
+ if (temp->prev_brother)
+ insert_bb = 1;
+ insn = find_first_from_end (temp, depth);
+
+ if (!insn)
+ continue;
+
+ last_brother = temp;
+
+ /* Finding equal instruction in the concatenated basic blocks */
+ for (temp2 = temp->next_brother; temp2; temp2 = temp2->next_brother)
+ {
+ if (find_insn_from_end (insn, temp2, depth))
+ {
+ last_brother->next_analogous = temp2;
+ temp2->prev_analogous = last_brother;
+ last_brother = temp2;
+ num_of_good_bb++;
+ }
+ else
+ insert_bb = 1;
+ }
+
+ /* Cost analizing */
+ if (num_of_good_bb <= num_of_next_bb)
+ {
+ temp->last_depth++;
+ continue;
+ }
+
+ if (!insert_bb && temp->curr->succ)
+ {
+ if (num_of_good_bb <
+ num_of_pred_blocks (temp->curr->succ->dest))
+ insert_bb = 1;
+ }
+
+ if (!insert_bb)
+ {
+ edge e;
+
+ for (e = (temp->curr)->succ; e; e = e->succ_next)
+ {
+ rtx new_insn =
+ make_insn_raw (PATTERN (temp->moveable_insn));
+ insert_insn_begin_of_basic_block (new_insn, e->dest);
+ gain--;
+ }
+
+ for (temp2 = temp; temp2; temp2 = temp2->next_analogous)
+ {
+ rtx rinsn = temp2->moveable_insn;
+ temp2->moveable_insn = NULL;
+ remove_insn (rinsn);
+ gain++;
+ }
+
+ delete_analogous (temp);
+ change = 1;
+ }
+ else if ((num_of_succ_blocks (temp->curr) == 1)
+ && ((temp->curr->succ)->dest != EXIT_BLOCK_PTR))
+ {
+ basic_block new_bb;
+ bbDecorator new_bb_decorator;
+
+
+ if (find_ABNORMAL_EDGE (temp) && optimize_size
+ &&
+ !any_condjump_p (BB_END (temp->curr->succ->dest->prev_bb)))
+ {
+ new_bb = create_basic_block_by_factoring (temp);
+ new_bb_decorator =
+ insert_new_bbDecorator (decorator, new_bb);
+ modifying_concatenation (temp, new_bb_decorator);
+ change = 1;
+ }
+ }
+ delete_analogous (temp);
+ }
+ }
+ return (change);
+ }
+
+ /* Modification of the edges and jump labels of basic blocks, if it's necessary
+ after the insertion of the new basic block.*/
+ static void
+ modify_jump_labels (basic_block new_bb, bbDecorator first, rtx label)
+ {
+ bbDecorator temp;
+ for (temp = first; temp; temp = temp->next_analogous)
+ {
+ rtx jump = BB_END (temp->curr);
+ if (JUMP_P (jump))
+ {
+ redirect_jump (jump, label, 0);
+ redirect_edge_succ_nodup (temp->curr->succ, new_bb);
+ }
+ else
+ redirect_edge_succ_nodup (temp->curr->succ, new_bb);
+ }
+ }
+
+ /*It is not safe to modify the destination of edge of a bb, if this edge is
+ ABNORMAL. */
+ static int
+ find_ABNORMAL_EDGE (bbDecorator first)
+ {
+ int num_of_not_abnormal_succ = 0;
+ bbDecorator temp;
+ for (temp = first; temp; temp = temp->next_analogous)
+ {
+ if (temp->curr->succ->flags & EDGE_ABNORMAL)
+ {
+ if (temp->prev_analogous)
+ (temp->prev_analogous)->next_analogous = temp->next_analogous;
+ if (temp->next_analogous)
+ (temp->next_analogous)->prev_analogous = temp->prev_analogous;
+ temp->prev_analogous = temp->next_analogous = NULL;
+ }
+ else
+ num_of_not_abnormal_succ++;
+ }
+ return ((num_of_not_abnormal_succ > 1) ? 1 : 0);
+ }
+
+ /* Creation of new basic block. */
+ static basic_block
+ create_basic_block_by_factoring (bbDecorator first)
+ {
+ bbDecorator temp2;
+ basic_block next_bb = ((first->curr)->succ)->dest;
+ basic_block prev = next_bb->prev_bb;
+ basic_block new_bb;
+ rtx next;
+ rtx new_insn;
+ rtx label = gen_label_rtx ();
+ edge f, new_edge;
+ rtx insn = first->moveable_insn;
+ int find = 0;
+ edge e = NULL;
+ int find2 = 0;
+ rtx last = get_last_insn ();
+
+ next = BB_END (next_bb->prev_bb);
+ while (BARRIER_P (NEXT_INSN (next)))
+ next = NEXT_INSN (next);
+
+ new_bb = create_basic_block (NULL, NULL, prev);
+ PREV_INSN (BB_HEAD (new_bb)) = next;
+ NEXT_INSN (BB_HEAD (new_bb)) = NEXT_INSN (next);
+ PREV_INSN (NEXT_INSN (next)) = BB_HEAD (new_bb);
+ NEXT_INSN (next) = BB_HEAD (new_bb);
+ NEXT_INSN (last) = NULL;
+ set_last_insn (last);
+
+ /* Creation of the new instructions for the new bb. */
+ new_insn = make_insn_raw (PATTERN (insn));
+ gain--;
+ PUT_MODE (new_insn, GET_MODE (insn));
+ INSN_LOCATOR (new_insn) = INSN_LOCATOR (insn);
+
+ emit_label_before (label, BB_HEAD (new_bb));
+ BB_HEAD (new_bb) = label;
+ set_block_for_insn (label, new_bb);
+ add_insn_after (new_insn, BB_END (new_bb));
+ set_block_for_insn (new_insn, new_bb);
+ BB_END (new_bb) = new_insn;
+
+ /* Creation of the edge of the new bb. */
+ new_edge = make_edge (new_bb, next_bb, EDGE_FALLTHRU);
+ if (new_edge)
+ new_edge->probability = REG_BR_PROB_BASE;
+
+ for (f = prev->succ; f; f = f->succ_next)
+ {
+ if (f->dest == next_bb)
+ {
+ e = f;
+ for (temp2 = first; temp2; temp2 = temp2->next_analogous)
+ if (prev == temp2->curr)
+ {
+ find = 1;
+ break;
+ }
+ find2 = 1;
+ break;
+ }
+ }
+
+ /* Modifications in the environment. */
+ if (JUMP_P (BB_END (prev)) && (!find) && (find2) && e)
+ {
+ e->flags &= ~EDGE_FALLTHRU;
+ emit_barrier_after (BB_END (prev));
+ }
+ if (!JUMP_P (BB_END (prev)) && (!find) && (find2) && e)
+ {
+ edge new_edge_;
+ remove_edge (e);
+ emit_jump_insn_after (gen_jump (BB_HEAD (next_bb)), BB_END (prev));
+ gain--;
+ emit_barrier_after (BB_END (prev));
+ new_edge_ = make_edge (prev, next_bb, 0);
+ if (new_edge_)
+ new_edge_->probability = REG_BR_PROB_BASE;
+ JUMP_LABEL (BB_END (prev)) = block_label (next_bb);
+ LABEL_NUSES (block_label (next_bb))++;
+ }
+
+ for (temp2 = first; temp2; temp2 = temp2->next_analogous)
+ {
+ rtx rinsn = temp2->moveable_insn;
+ temp2->moveable_insn = NULL;
+ remove_insn (rinsn);
+ gain++;
+ }
+
+ modify_jump_labels (new_bb, first, label);
+ return (new_bb);
+ }
+
+
+ /* The main entry point of factoring algorithms! */
+ int
+ factoring (int depth, algorithm alg)
+ {
+ bbDecorator decorator = NULL;
+ int result = 0;
+
+ decorator = init (decorator);
+ gain = 0;
+ if (alg == up)
+ {
+ collect_full_pred_brother (decorator);
+ cost_analyzer (decorator, num_of_pred_blocks);
+ while (factoring_up (depth, decorator))
+ {
+ result = 1;
+ }
+ }
+ else
+ {
+ collect_brother (decorator, compare_succ_blocks);
+ cost_analyzer (decorator, num_of_succ_blocks);
+ while (factoring_down (depth, decorator))
+ {
+ result = 1;
+ };
+ }
+
+ free_bbDecorator_list (decorator);
+ return (result);
+ }
+
+
+ /* Collecting the defuse info about x. If in_dest is not 0, we are in a SET. */
+ static void
+ find_defuse_info (rtx x, int in_dest, struct defuse_info *res)
+ {
+ enum rtx_code code = GET_CODE (x);
+ int i, j;
+ unsigned int r;
+ const char *format_ptr;
+
+ /* Handle leaf items for which we set resource flags. Also, special-case
+ CALL, SET and CLOBBER operators. */
+ switch (code)
+ {
+ case CONST:
+ case CONST_INT:
+ case CONST_DOUBLE:
+ case CONST_VECTOR:
+ case SYMBOL_REF:
+ case LABEL_REF:
+ return;
+
+ case PC:
+ res->pc = 1;
+ return;
+ case SUBREG:
+ if (GET_CODE (SUBREG_REG (x)) != REG)
+ find_defuse_info (SUBREG_REG (x), in_dest, res);
+ else
+ {
+ unsigned int regno = REGNO (x);
+ unsigned int last_regno =
+ regno + HARD_REGNO_NREGS (regno, GET_MODE (x));
+
+ for (r = regno; r < last_regno; r++)
+ {
+ SET_REGNO_REG_SET (res->regs, r);
+ if (in_dest)
+ SET_REGNO_REG_SET (res->def_regs, r);
+ }
+ }
+ return;
+
+ case REG:
+ {
+ unsigned int regno = REGNO (x);
+ unsigned int last_regno =
+ regno + HARD_REGNO_NREGS (regno, GET_MODE (x));
+
+ for (r = regno; r < last_regno; r++)
+ {
+ SET_REGNO_REG_SET (res->regs, r);
+ if (in_dest)
+ SET_REGNO_REG_SET (res->def_regs, r);
+ }
+ }
+ return;
+
+ case MEM:
+ /* If this memory shouldn't change, it really isn't referencing
+ memory. */
+ if (RTX_UNCHANGING_P (x))
+ res->unch_memory = 1;
+ else
+ res->memory = 1;
+ res->volatil |= MEM_VOLATILE_P (x);
+
+ /* Mark registers used to access memory. */
+ find_defuse_info (XEXP (x, 0), in_dest, res);
+
+ if (in_dest)
+ res->def_memory = 1;
+ return;
+
+ case CC0:
+ res->cc = 1;
+ if (in_dest)
+ res->def_cc = 1;
+ return;
+
+ case UNSPEC_VOLATILE:
+ case ASM_INPUT:
+ /* Traditional asm's are always volatile. */
+ res->volatil = 1;
+ return;
+
+ case TRAP_IF:
+ res->volatil = 1;
+ break;
+
+ case ASM_OPERANDS:
+ res->volatil |= MEM_VOLATILE_P (x);
+
+ /* For all ASM_OPERANDS, we must traverse the vector of input operands.
+ We can not just fall through here since then we would be confused by
+ the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
+ traditional asms unlike their normal usage. */
+
+ for (i = 0; i < ASM_OPERANDS_INPUT_LENGTH (x); i++)
+ find_defuse_info (ASM_OPERANDS_INPUT (x, i), in_dest, res);
+ return;
+
+ case CALL:
+ /* The first operand will be a (MEM (xxx)) but doesn't really reference
+ memory. The second operand may be referenced, though. */
+ find_defuse_info (XEXP (XEXP (x, 0), 0), in_dest, res);
+ find_defuse_info (XEXP (x, 1), 0, res);
+ return;
+
+ case SET:
+ /* Usually, the first operand of SET is set, not referenced. But
+ registers used to access memory are referenced. SET_DEST is also
+ referenced if it is a ZERO_EXTRACT or SIGN_EXTRACT. */
+ find_defuse_info (SET_SRC (x), 0, res);
+ find_defuse_info (SET_DEST (x), 1, res);
+
+ x = SET_DEST (x);
+ if (GET_CODE (x) == CC0)
+ res->def_cc = 1;
+ if (GET_CODE (x) == PC)
+ res->def_pc = 1;
+ if (GET_CODE (x) == REG)
+ {
+ unsigned int regno = REGNO (x);
+ unsigned int last_regno =
+ regno + HARD_REGNO_NREGS (regno, GET_MODE (x));
+
+ for (r = regno; r < last_regno; r++)
+ {
+ SET_REGNO_REG_SET (res->regs, r);
+ SET_REGNO_REG_SET (res->def_regs, r);
+ }
+ }
+
+ if (GET_CODE (x) == SIGN_EXTRACT
+ || GET_CODE (x) == ZERO_EXTRACT || GET_CODE (x) == STRICT_LOW_PART)
+ find_defuse_info (x, 1, res);
+ else if (GET_CODE (x) == SUBREG)
+ x = SUBREG_REG (x);
+ if (GET_CODE (x) == MEM)
+ {
+ res->def_memory = 1;
+ find_defuse_info (XEXP (x, 0), 1, res);
+ }
+ return;
+
+ case CLOBBER:
+ return;
+
+ case CALL_INSN:
+ return;
+ /* ... fall through to other INSN processing ... */
+
+ case INSN:
+ case JUMP_INSN:
+
+ /* No special processing, just speed up. */
+ find_defuse_info (PATTERN (x), in_dest, res);
+ return;
+
+ default:
+ break;
+ }
+
+ /* Process each sub-expression and flag what it needs. */
+ format_ptr = GET_RTX_FORMAT (code);
+ for (i = 0; i < GET_RTX_LENGTH (code); i++)
+ switch (*format_ptr++)
+ {
+ case 'e':
+ find_defuse_info (XEXP (x, i), in_dest, res);
+ break;
+
+ case 'E':
+ for (j = 0; j < XVECLEN (x, i); j++)
+ find_defuse_info (XVECEXP (x, i, j), in_dest, res);
+ break;
+ }
+ }
+
+ /* If the insn sets the cc, this function returns with 1. In some target it is
+ no felicitous to move this insn. */
+ static int
+ find_set_cc (rtx insn)
+ {
+ int length;
+ const char *format;
+ int i;
+ int result = 0;
+
+ length = GET_RTX_LENGTH (GET_CODE (insn));
+ format = GET_RTX_FORMAT (GET_CODE (insn));
+
+ if (GET_CODE (insn) == SET)
+ if (GET_CODE (SET_DEST (insn)) == CC0)
+ return (1);
+
+ for (i = 0; i < length; ++i)
+ {
+ switch (format[i])
+ {
+ case 'e':
+ if (XEXP (insn, i))
+ result |= find_set_cc (XEXP (insn, i));
+ break;
+
+ case 'V':
+ case 'E':
+ if (XVEC (insn, i) != 0)
+ {
+ int j;
+ for (j = 0; j < XVECLEN (insn, i); ++j)
+ if (XVECEXP (insn, i, j))
+ result |= find_set_cc (XVECEXP (insn, i, j));
+ }
+ break;
+
+ default:
+ break;
+ }
+ }
+ return result;
+ }
Index: gcc/gcc/factoring.h
===================================================================
RCS file: /cvs/gcc/gcc/factoring.h
diff -N gcc/gcc/factoring.h
*** /dev/null 1970-01-01 01:00:00.000000000 +0100
--- gcc/gcc/factoring.h 2004-03-22 16:01:11.000000000 +0100
***************
*** 0 ****
--- 1,23 ----
+ /* Local factoring algorithms' header in RTL.
+ Copyright (C) 2004 Free Software Foundation, Inc.
+
+ This file is part of GCC.
+
+ GCC is free software; you can redistribute it and/or modify it under the
+ terms of the GNU General Public License as published by the Free Software
+ Foundation; either version 2, or (at your option) any later version.
+
+ GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+ WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
+ details.
+
+ You should have received a copy of the GNU General Public License along
+ with GCC; see the file COPYING. If not, write to the Free Software
+ Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
+
+ typedef enum
+ { up, down } algorithm;
+
+ /* Main factoring functions */
+ int factoring (int, algorithm);