This is the mail archive of the gcc@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]

Factoring algorithms on rtl ?


Hi,
at this moment gcc generates many similar or identical rtl instructions
when optimizing for size. I think some code factoring algorithms could
help in this problem. Specifically we are working on:
- local prefix/suffix factoring
- local common insns sequences abtraction
- function abstraction
For the first method, I'm working on a very simple algorithm to
eliminate identical local prefix insns of a basic blocks on rtl.

The attached patch finds those basic blocks of which the first insns
are indentical, and factor out them into the end of parent basic blocks.
This is done only if it has no side effects and the count of original
insns - marked for factoring - is greater than the count of parent basic
blocks.

This version of the patch only contains the local prefix factoring
algorithms, but I hope the suffix version of this algorithms will be
finished very soon.

I measured the size with CSiBE, and found about 0,1%/0,66% code size
save for arm/i386 targets with -Os. Bootstrapped on i386-linux and
regtested on arm-elf, i386-linux with no new failures.

This patch is only in a very experimental phase. I think it is not ready
for commit, but I would be happy to get some comments about it.

Is it acceptable for 3.5.x? Is this work useful at all?

Regards,
    Gábor Lóki



Index: gcc/gcc/common.opt
===================================================================
RCS file: /cvs/gcc/gcc/gcc/common.opt,v
retrieving revision 1.25
diff -c -p -a -d -3 -r1.25 common.opt
*** gcc/gcc/common.opt	27 Jan 2004 12:49:30 -0000	1.25
--- gcc/gcc/common.opt	17 Feb 2004 11:36:55 -0000
*************** fdump-unnumbered
*** 303,308 ****
--- 303,312 ----
  Common
  Suppress output of instruction numbers and line number notes in debugging dumps
  
+ ffactoring
+ Common
+ Perform factoring
+ 
  feliminate-dwarf2-dups
  Common
  Perform DWARF2 duplicate elimination
Index: gcc/gcc/flags.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/flags.h,v
retrieving revision 1.128
diff -c -p -a -d -3 -r1.128 flags.h
*** gcc/gcc/flags.h	27 Jan 2004 12:49:30 -0000	1.128
--- gcc/gcc/flags.h	17 Feb 2004 11:37:14 -0000
*************** extern int flag_web;
*** 723,731 ****
     used.  */
  extern int flag_remove_unreachable_functions;
  
  /* A string that's used when a random name is required.  NULL means
     to make it really random.  */
- 
  extern const char *flag_random_seed;
  
  /* True if the given mode has a NaN representation and the treatment of
--- 723,733 ----
     used.  */
  extern int flag_remove_unreachable_functions;
  
+ /* 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;
  
  /* True if the given mode has a NaN representation and the treatment of
Index: gcc/gcc/Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.1239
diff -c -p -a -d -3 -r1.1239 Makefile.in
*** gcc/gcc/Makefile.in	31 Jan 2004 00:49:53 -0000	1.1239
--- gcc/gcc/Makefile.in	17 Feb 2004 11:37:25 -0000
*************** OBJS-common = \
*** 862,868 ****
   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					   \
   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	   \
--- 862,868 ----
   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 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	   \
*************** profile.o : profile.c $(CONFIG_H) $(SYST
*** 1671,1676 ****
--- 1671,1678 ----
  value-prof.o : value-prof.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
     $(BASIC_BLOCK_H) hard-reg-set.h value-prof.h $(EXPR_H) output.h flags.h \
     $(RECOG_H) insn-config.h $(OPTABS_H) $(REGS_H)
+ factoring.o : factoring.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) coretypes.h $(TM_H) \
+    $(BASIC_BLOCK_H) flags.h
  loop.o : loop.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) flags.h $(LOOP_H) \
     insn-config.h $(REGS_H) hard-reg-set.h $(RECOG_H) $(EXPR_H) \
     real.h $(PREDICT_H) $(BASIC_BLOCK_H) function.h cfgloop.h \
Index: gcc/gcc/opts.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/opts.c,v
retrieving revision 1.52
diff -c -p -a -d -3 -r1.52 opts.c
*** gcc/gcc/opts.c	27 Jan 2004 12:49:30 -0000	1.52
--- gcc/gcc/opts.c	17 Feb 2004 11:37:39 -0000
*************** decode_options (unsigned int argc, const
*** 589,594 ****
--- 589,595 ----
  	 or less automatically remove extra jumps, but would also try to
  	 use more short jumps instead of long jumps.  */
        flag_reorder_blocks = 0;
+       flag_factoring = 1;
      }
  
    /* Initialize whether `char' is signed.  */
*************** common_handle_option (size_t scode, cons
*** 967,972 ****
--- 968,977 ----
        flag_dump_unnumbered = value;
        break;
  
+     case OPT_ffactoring:
+       flag_factoring = value;
+       break;
+ 
      case OPT_feliminate_dwarf2_dups:
        flag_eliminate_dwarf2_dups = value;
        break;
Index: gcc/gcc/timevar.def
===================================================================
RCS file: /cvs/gcc/gcc/gcc/timevar.def,v
retrieving revision 1.24
diff -c -p -a -d -3 -r1.24 timevar.def
*** gcc/gcc/timevar.def	31 Jan 2004 02:06:48 -0000	1.24
--- gcc/gcc/timevar.def	17 Feb 2004 11:37:50 -0000
*************** DEFTIMEVAR (TV_DBR_SCHED             , "
*** 93,98 ****
--- 93,99 ----
  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")
  
Index: gcc/gcc/toplev.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/toplev.c,v
retrieving revision 1.873
diff -c -p -a -d -3 -r1.873 toplev.c
*** gcc/gcc/toplev.c	30 Jan 2004 17:43:23 -0000	1.873
--- gcc/gcc/toplev.c	17 Feb 2004 11:38:02 -0000
*************** Software Foundation, 59 Temple Place - S
*** 79,84 ****
--- 79,85 ----
  #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"
*************** static void rest_of_handle_machine_reorg
*** 163,168 ****
--- 164,170 ----
  static void rest_of_handle_delay_slots (tree, rtx);
  #endif
  static void rest_of_handle_final (tree, rtx);
+ static void rest_of_factoring (tree, rtx);
  
  /* Nonzero to dump debug info whilst parsing (-dy option).  */
  static int set_yydebug;
*************** enum dump_file_index
*** 289,294 ****
--- 291,297 ----
    DFI_branch_target_load,
    DFI_sched2,
    DFI_stack,
+   DFI_factoring,
    DFI_mach,
    DFI_dbr,
    DFI_MAX
*************** static struct dump_file_info dump_file[D
*** 340,345 ****
--- 343,349 ----
    { "btl",	'd', 1, 0, 0 }, /* Yes, duplicate enable switch.  */
    { "sched2",	'R', 1, 0, 0 },
    { "stack",	'k', 1, 0, 0 },
+   { "factoring",	'q', 1, 0, 0 },
    { "mach",	'M', 1, 0, 0 },
    { "dbr",	'd', 0, 0, 0 },
  };
*************** int flag_evaluation_order = 0;
*** 1006,1011 ****
--- 1010,1018 ----
  /* Add or remove a leading underscore from user symbols.  */
  int flag_leading_underscore = -1;
  
+ /* Nonzero means enable all factoring algorithms.  */
+ int flag_factoring = 0;
+ 
  /* The user symbol prefix after having resolved same.  */
  const char *user_label_prefix;
  
*************** rest_of_handle_final (tree decl, rtx ins
*** 2087,2092 ****
--- 2094,2118 ----
    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, prefix); 
+ 
+   life_analysis (insns, rtl_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
*************** rest_of_compilation (tree decl)
*** 3508,3514 ****
      /* Last attempt to optimize CFG, as scheduling, peepholing and insn
         splitting possibly introduced more crossjumping opportunities.  */
      cleanup_cfg (CLEANUP_EXPENSIVE
! 		 | CLEANUP_UPDATE_LIFE 
  		 | (flag_crossjumping ? CLEANUP_CROSSJUMP : 0));
    if (flag_if_conversion2)
      {
--- 3534,3540 ----
      /* Last attempt to optimize CFG, as scheduling, peepholing and insn
         splitting possibly introduced more crossjumping opportunities.  */
      cleanup_cfg (CLEANUP_EXPENSIVE
! 		 | CLEANUP_UPDATE_LIFE
  		 | (flag_crossjumping ? CLEANUP_CROSSJUMP : 0));
    if (flag_if_conversion2)
      {
*************** rest_of_compilation (tree decl)
*** 3559,3564 ****
--- 3585,3594 ----
  #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/factoring.c
===================================================================
diff -N -c -p -a -d -3 factoring.c
*** gcc/gcc/factoring.c	27 Jan 2004 12:49:30 -0000	1.128
--- gcc/gcc/factoring.c	17 Feb 2004 11:37:14 -0000
***************
*** 0 ****
--- 1,715 ----
+ #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"
+ 
+ typedef struct bbDecorator_def
+ {
+   struct bbDecorator_def *next_brother;
+   struct bbDecorator_def *prev_brother;
+   basic_block curr;
+   basic_block next_analogous;
+   basic_block 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;
+   regset regs;                  /* Which registers are set or needed.  */
+   regset def_regs;              /* Which registers are set. */
+ };
+ 
+ /* Prefix factoring functions */
+ static int find_bb_in_pred_blocks (basic_block, basic_block);
+ static void insert_insn_after_basic_block (rtx, basic_block);
+ static int compare_pred_blocks (basic_block, basic_block);
+ static void collectFullPrefixBrother (bbDecorator);
+ static int prefix_optimization (int, bbDecorator);
+ static rtx find_first_from_begin (bbDecorator decorator, int);
+ static int moveable_from_begin (rtx);
+ static int find_insn_in_bb_prefix (rtx, bbDecorator, int);
+ 
+ 
+ /* Suffix factoring functions */
+ static int find_bb_in_succ_blocks (basic_block, basic_block);
+ static int compare_succ_blocks (basic_block, basic_block);
+ 
+ /* Common functions */
+ static int num_of_bb (void);
+ static int num_of_succ_blocks (basic_block);
+ static int num_of_prev_blocks (basic_block);
+ static bbDecorator init (bbDecorator);
+ static void free_bbDecorator_list (bbDecorator);
+ static void delete_brothers (bbDecorator);
+ static void collectBrother (bbDecorator, int (*f) (basic_block, basic_block));
+ static int commutable_insns (rtx, rtx);
+ static void costAnalyzer (bbDecorator, int (*f) (basic_block));
+ static void find_defuse_info (rtx, int, struct defuse_info *);
+ 
+ /* The number of basic blocks of the function. */
+ static int
+ num_of_bb (void)
+ {
+   int i = 0;
+   basic_block bb;
+   FOR_EACH_BB (bb) i++;
+   return i;
+ }
+ 
+ /* 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_prev_blocks (basic_block bb)
+ {
+   int num = 0;
+   edge e;
+   for (e = bb->pred; e; e = e->pred_next)
+     num++;
+   return num;
+ }
+ 
+ 
+ /* Prefix factoring functions */
+ /* 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_prev_blocks (bb1) != num_of_prev_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_after_basic_block (rtx insn, basic_block bb)
+ {
+   rtx last = BB_END (bb);
+ 
+   if (JUMP_P (last))
+     add_insn_before (insn, last);
+   else
+     add_insn_after (insn, last);
+ }
+ 
+ /* 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 (num_of_bb () *
+                                           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
+ collectBrother (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;
+             }
+         }
+     }
+ }
+ 
+ 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;
+     }
+ }
+ 
+ 
+ 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
+ collectFullPrefixBrother (bbDecorator decorator)
+ {
+   bbDecorator temp;
+ 
+   collectBrother (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
+ costAnalyzer (bbDecorator decorator, int (*f) (basic_block))
+ {
+   bbDecorator temp;
+   for (temp = decorator; temp; temp = temp->next_decorator)
+     {
+       if ((!temp->prev_brother) && temp->next_brother)
+         {
+           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);
+         }
+     }
+ }
+ 
+ /* Prefix functions: it's return 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;
+ }
+ 
+ static rtx
+ find_first_from_begin (bbDecorator decorator, int max_depth)
+ {
+   basic_block bb = decorator->curr;
+   rtx insn;
+   int depth = 0;
+   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 (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;
+ }
+ 
+ static int
+ find_insn_in_bb_prefix (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;
+ }
+ 
+ /* 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.def_pc && (!JUMP_P (insn)))
+       || (res_insn2.def_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);
+ }
+ 
+ static int
+ prefix_optimization (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;
+             }
+ 
+           for (temp2 = temp->next_brother; temp2; temp2 = temp2->next_brother)
+             if (!find_insn_in_bb_prefix (insn, temp2, depth))
+               {
+                 error = 1;
+                 temp->last_depth++;
+                 break;
+               }
+ 
+           if (error)
+             continue;
+ 
+           /* Verifying the insn that 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 (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_after_basic_block (new_insn, e->src);
+                 }
+ 
+               for (temp2 = temp; temp2; temp2 = temp2->next_brother)
+                 {
+                   rtx rinsn = temp2->moveable_insn;
+                   temp2->moveable_insn = NULL;
+                   remove_insn (rinsn);
+                 }
+               change = 1;
+             }
+         }
+     }
+   return (change);
+ }
+ 
+ /* The main entry point of factoring! */
+ void
+ factoring (int depth, algorithm alg)
+ {
+   bbDecorator decorator = NULL;
+   decorator = init (decorator);
+ 
+   if (alg == prefix)
+     {
+       collectFullPrefixBrother (decorator);
+       costAnalyzer (decorator, &num_of_prev_blocks);
+       while (prefix_optimization (depth, decorator));
+     }
+   else
+     {
+       collectBrother (decorator, &compare_succ_blocks);
+       costAnalyzer (decorator, &num_of_succ_blocks);
+     }
+ 
+   free_bbDecorator_list (decorator);
+ }
+ 
+ /* 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), 1, res);
+ 
+       x = SET_DEST (x);
+       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;
+       }
+ }
Index: gcc/gcc/factoring.h
===================================================================
diff -N -c -p -a -d -3 factoring.h
*** gcc/gcc/factoring.h	27 1970-01-01 01:00:00.000000000 +0100
--- gcc/gcc/factoring.h	17 2004-02-17 10:43:56.000000000 +0100
***************
*** 0 ****
--- 1,6 ----
+ typedef enum {prefix, suffix} algorithm;
+ 
+ /* Main factoring functions */
+ void factoring (int, algorithm);
+ 
+ 



Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]