This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Patch to mark pure & constant functions with loops
- From: John Wehle <john at feith dot com>
- To: gcc-patches at gcc dot gnu dot org
- Date: Mon, 25 Mar 2002 13:42:01 -0500 (EST)
- Subject: Patch to mark pure & constant functions with loops
This patch allows mark_constant_function to mark functions
containing loops which are known to always terminate.
This patch passes make bootstrap and make check
on Dec Alpha 4.0f, i386-unknown-freebsd4.5, and Solaris 7 SPARC.
ChangeLog:
Sun Mar 24 18:11:40 EST 2002 John Wehle (john@feith.com)
* basic-block.h (mark_dfs_back_edges): Update prototype.
* cfganal.c (mark_dfs_back_edges): Return the total number
of back edges.
* rtl.h (loop_optimize): Update prototype.
* loop.c (loop_optimize): Return the total number of remaining
loops which are known to terminate.
* function.h (struction function): Add has_no_endless_loops.
(current_function_has_no_endless_loops): New.
* function.c (prepare_function_start): Initialize it.
* toplev.c (rest_of_compilation): Set it.
* alias.c (mark_constant_function): Use it instead of
mark_dfs_mark_edges. Attempt to mark functions which
always resolve to the module being compiled.
Enjoy!
-- John Wehle
------------------8<------------------------8<------------------------
*** gcc/basic-block.h.ORIGINAL Mon Mar 11 23:11:52 2002
--- gcc/basic-block.h Sun Mar 24 18:05:57 2002
*************** extern void conflict_graph_print
*** 695,701 ****
extern conflict_graph conflict_graph_compute
PARAMS ((regset,
partition));
! extern bool mark_dfs_back_edges PARAMS ((void));
extern void update_br_prob_note PARAMS ((basic_block));
extern void fixup_abnormal_edges PARAMS ((void));
--- 695,701 ----
extern conflict_graph conflict_graph_compute
PARAMS ((regset,
partition));
! extern unsigned int mark_dfs_back_edges PARAMS ((void));
extern void update_br_prob_note PARAMS ((basic_block));
extern void fixup_abnormal_edges PARAMS ((void));
*** gcc/cfganal.c.ORIGINAL Mon Mar 11 23:12:00 2002
--- gcc/cfganal.c Sun Mar 24 18:06:30 2002
*************** can_fallthru (src, target)
*** 94,101 ****
return next_active_insn (insn) == insn2;
}
! /* Mark the back edges in DFS traversal.
! Return non-zero if a loop (natural or otherwise) is present.
Inspired by Depth_First_Search_PP described in:
Advanced Compiler Design and Implementation
--- 94,100 ----
return next_active_insn (insn) == insn2;
}
! /* Mark the back edges in DFS traversal and return the total number.
Inspired by Depth_First_Search_PP described in:
Advanced Compiler Design and Implementation
*************** can_fallthru (src, target)
*** 104,110 ****
and heavily borrowed from flow_depth_first_order_compute. */
! bool
mark_dfs_back_edges ()
{
edge *stack;
--- 103,109 ----
and heavily borrowed from flow_depth_first_order_compute. */
! unsigned int
mark_dfs_back_edges ()
{
edge *stack;
*************** mark_dfs_back_edges ()
*** 114,120 ****
int prenum = 1;
int postnum = 1;
sbitmap visited;
! bool found = false;
/* Allocate the preorder and postorder number arrays. */
pre = (int *) xcalloc (n_basic_blocks, sizeof (int));
--- 113,119 ----
int prenum = 1;
int postnum = 1;
sbitmap visited;
! unsigned int nback_edges = 0;
/* Allocate the preorder and postorder number arrays. */
pre = (int *) xcalloc (n_basic_blocks, sizeof (int));
*************** mark_dfs_back_edges ()
*** 166,172 ****
if (dest != EXIT_BLOCK_PTR && src != ENTRY_BLOCK_PTR
&& pre[src->index] >= pre[dest->index]
&& post[dest->index] == 0)
! e->flags |= EDGE_DFS_BACK, found = true;
if (! e->succ_next && src != ENTRY_BLOCK_PTR)
post[src->index] = postnum++;
--- 165,171 ----
if (dest != EXIT_BLOCK_PTR && src != ENTRY_BLOCK_PTR
&& pre[src->index] >= pre[dest->index]
&& post[dest->index] == 0)
! e->flags |= EDGE_DFS_BACK, nback_edges++;
if (! e->succ_next && src != ENTRY_BLOCK_PTR)
post[src->index] = postnum++;
*************** mark_dfs_back_edges ()
*** 183,189 ****
free (stack);
sbitmap_free (visited);
! return found;
}
/* Return true if we need to add fake edge to exit.
--- 182,188 ----
free (stack);
sbitmap_free (visited);
! return nback_edges;
}
/* Return true if we need to add fake edge to exit.
*** gcc/rtl.h.ORIGINAL Thu Mar 14 23:33:41 2002
--- gcc/rtl.h Sun Mar 24 18:06:58 2002
*************** extern void print_inline_rtx PARAMS ((F
*** 1912,1918 ****
extern void init_loop PARAMS ((void));
extern rtx libcall_other_reg PARAMS ((rtx, rtx));
#ifdef BUFSIZ
! extern void loop_optimize PARAMS ((rtx, FILE *, int));
#endif
extern void record_excess_regs PARAMS ((rtx, rtx, rtx *));
--- 1912,1918 ----
extern void init_loop PARAMS ((void));
extern rtx libcall_other_reg PARAMS ((rtx, rtx));
#ifdef BUFSIZ
! extern unsigned int loop_optimize PARAMS ((rtx, FILE *, int));
#endif
extern void record_excess_regs PARAMS ((rtx, rtx, rtx *));
*** gcc/loop.c.ORIGINAL Sat Mar 16 18:35:52 2002
--- gcc/loop.c Sun Mar 24 18:07:20 2002
*************** compute_luids (start, end, prev_luid)
*** 438,446 ****
/* Entry point of this file. Perform loop optimization
on the current function. F is the first insn of the function
and DUMPFILE is a stream for output of a trace of actions taken
! (or 0 if none should be output). */
! void
loop_optimize (f, dumpfile, flags)
/* f is the first instruction of a chain of insns for one function */
rtx f;
--- 438,447 ----
/* Entry point of this file. Perform loop optimization
on the current function. F is the first insn of the function
and DUMPFILE is a stream for output of a trace of actions taken
! (or 0 if none should be output). Returns the number of remaining
! loops which are known to terminate. */
! unsigned int
loop_optimize (f, dumpfile, flags)
/* f is the first instruction of a chain of insns for one function */
rtx f;
*************** loop_optimize (f, dumpfile, flags)
*** 452,457 ****
--- 453,459 ----
struct loops loops_data;
struct loops *loops = &loops_data;
struct loop_info *loops_info;
+ unsigned int nloops_known_to_terminate;
loop_dump_stream = dumpfile;
*************** loop_optimize (f, dumpfile, flags)
*** 474,480 ****
/* Don't waste time if no loops. */
if (max_loop_num == 0)
! return;
loops->num = max_loop_num;
--- 476,482 ----
/* Don't waste time if no loops. */
if (max_loop_num == 0)
! return 0;
loops->num = max_loop_num;
*************** loop_optimize (f, dumpfile, flags)
*** 561,571 ****
--- 563,590 ----
end_alias_analysis ();
+ /* Count the number of remaining loops which are known to terminate. */
+
+ nloops_known_to_terminate = 0;
+ for (i = 0; i < loops->num; i++)
+ {
+ struct loop *loop = &loops->array[i];
+
+ if (loop->invalid
+ || ! LOOP_INFO (loop)->n_iterations
+ || LOOP_INFO (loop)->n_iterations == LOOP_INFO (loop)->unroll_number)
+ continue;
+
+ nloops_known_to_terminate++;
+ }
+
/* Clean up. */
free (uid_luid);
free (uid_loop);
free (loops_info);
free (loops->array);
+
+ return nloops_known_to_terminate;
}
/* Returns the next insn, in execution order, after INSN. START and
*** gcc/function.h.ORIGINAL Sat Mar 16 18:35:52 2002
--- gcc/function.h Thu Mar 21 23:22:01 2002
*************** struct function
*** 425,430 ****
--- 425,434 ----
/* Nonzero if the function being compiled issues a computed jump. */
unsigned int has_computed_jump : 1;
+ /* Nonzero if the function being compiled doesn't contain any loops
+ which might not terminate. This is set before mark_constant_function. */
+ unsigned int has_no_endless_loops : 1;
+
/* Nonzero if the current function is a thunk (a lightweight function that
just adjusts one of its arguments and forwards to another function), so
we should try to cut corners where we can. */
*************** extern int virtuals_instantiated;
*** 495,500 ****
--- 499,505 ----
#define current_function_calls_longjmp (cfun->calls_longjmp)
#define current_function_calls_eh_return (cfun->calls_eh_return)
#define current_function_has_computed_jump (cfun->has_computed_jump)
+ #define current_function_has_no_endless_loops (cfun->has_no_endless_loops)
#define current_function_contains_functions (cfun->contains_functions)
#define current_function_is_thunk (cfun->is_thunk)
#define current_function_args_info (cfun->args_info)
*** gcc/function.c.ORIGINAL Sat Mar 16 18:35:52 2002
--- gcc/function.c Thu Mar 21 23:23:02 2002
*************** prepare_function_start ()
*** 6180,6185 ****
--- 6180,6186 ----
current_function_sp_is_unchanging = 0;
current_function_uses_only_leaf_regs = 0;
current_function_has_computed_jump = 0;
+ current_function_has_no_endless_loops = 0;
current_function_is_thunk = 0;
current_function_returns_pcc_struct = 0;
*** gcc/toplev.c.ORIGINAL Sat Mar 16 18:35:55 2002
--- gcc/toplev.c Sat Mar 23 20:54:22 2002
*************** rest_of_compilation (decl)
*** 2352,2357 ****
--- 2352,2358 ----
rtx insns;
int tem;
int failure = 0;
+ unsigned int nloops_known_to_terminate;
int rebuild_label_notes_after_reload;
int register_life_up_to_date;
*************** rest_of_compilation (decl)
*** 2865,2870 ****
--- 2866,2873 ----
/* Move constant computations out of loops. */
+ nloops_known_to_terminate = 0;
+
if (optimize > 0)
{
timevar_push (TV_LOOP);
*************** rest_of_compilation (decl)
*** 2880,2886 ****
/* We only want to perform unrolling once. */
! loop_optimize (insns, rtl_dump_file, 0);
/* The first call to loop_optimize makes some instructions
trivially dead. We delete those instructions now in the
--- 2883,2889 ----
/* We only want to perform unrolling once. */
! (void)loop_optimize (insns, rtl_dump_file, 0);
/* The first call to loop_optimize makes some instructions
trivially dead. We delete those instructions now in the
*************** rest_of_compilation (decl)
*** 2893,2901 ****
reg_scan (insns, max_reg_num (), 1);
}
cleanup_barriers ();
! loop_optimize (insns, rtl_dump_file,
! (flag_unroll_loops ? LOOP_UNROLL : 0) | LOOP_BCT
! | (flag_prefetch_loop_arrays ? LOOP_PREFETCH : 0));
/* Loop can create trivially dead instructions. */
delete_trivially_dead_insns (insns, max_reg_num ());
--- 2896,2905 ----
reg_scan (insns, max_reg_num (), 1);
}
cleanup_barriers ();
! nloops_known_to_terminate
! = loop_optimize (insns, rtl_dump_file,
! (flag_unroll_loops ? LOOP_UNROLL : 0) | LOOP_BCT
! | (flag_prefetch_loop_arrays ? LOOP_PREFETCH : 0));
/* Loop can create trivially dead instructions. */
delete_trivially_dead_insns (insns, max_reg_num ());
*************** rest_of_compilation (decl)
*** 2916,2921 ****
--- 2920,2930 ----
dump_flow_info (rtl_dump_file);
cleanup_cfg ((optimize ? CLEANUP_EXPENSIVE : 0)
| (flag_thread_jumps ? CLEANUP_THREADING : 0));
+
+ /* If all the back edges are part of loops known to terminate,
+ then the function doesn't have any endless loops. */
+ current_function_has_no_endless_loops
+ = mark_dfs_back_edges () == nloops_known_to_terminate;
/* It may make more sense to mark constant functions after dead code is
eliminated by life_analyzis, but we need to do it early, as -fprofile-arcs
*** gcc/alias.c.ORIGINAL Sun Mar 17 00:16:46 2002
--- gcc/alias.c Sat Mar 23 21:09:41 2002
*************** mark_constant_function ()
*** 2551,2557 ****
rtx insn;
int nonlocal_memory_referenced;
! if (TREE_PUBLIC (current_function_decl)
|| TREE_READONLY (current_function_decl)
|| DECL_IS_PURE (current_function_decl)
|| TREE_THIS_VOLATILE (current_function_decl)
--- 2551,2558 ----
rtx insn;
int nonlocal_memory_referenced;
! if ((TREE_PUBLIC (current_function_decl)
! && ! MODULE_LOCAL_P (current_function_decl))
|| TREE_READONLY (current_function_decl)
|| DECL_IS_PURE (current_function_decl)
|| TREE_THIS_VOLATILE (current_function_decl)
*************** mark_constant_function ()
*** 2560,2566 ****
return;
/* A loop might not return which counts as a side effect. */
! if (mark_dfs_back_edges ())
return;
nonlocal_memory_referenced = 0;
--- 2561,2567 ----
return;
/* A loop might not return which counts as a side effect. */
! if (! current_function_has_no_endless_loops)
return;
nonlocal_memory_referenced = 0;
-------------------------------------------------------------------------
| Feith Systems | Voice: 1-215-646-8000 | Email: john@feith.com |
| John Wehle | Fax: 1-215-540-5495 | |
-------------------------------------------------------------------------