/*
- * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
+ * Copyright (C) 1995-2011 University of Karlsruhe. All right reserved.
*
* This file is part of libFirm.
*
*
* @version $Id$
*/
-
#include "config.h"
#include "iroptimize.h"
#include "opt_init.h"
#include "irnode.h"
#include "debug.h"
-
+#include "error.h"
#include "ircons.h"
#include "irgopt.h"
#include "irpass.h"
#include "irdom.h"
+#include <math.h>
#include "irbackedge_t.h"
#include "irphase_t.h"
#include "irloop_t.h"
DEBUG_ONLY(static firm_dbg_module_t *dbg);
+/* DBG print stats for every procedure. */
+#define LOOP_OPT_STATS 1
+
+/* DBG: Ignore node limits and process every possible loop. */
+#define LOOP_IGNORE_NODE_LIMITS 0
+
/**
* Convenience macro for iterating over every phi node of the given block.
* Requires phi list per block.
for ((phi) = (head), (next) = (head) ? get_Phi_next((head)) : NULL; \
(phi) ; (phi) = (next), (next) = (next) ? get_Phi_next((next)) : NULL)
-/* currently processed loop */
+/* Currently processed loop. */
static ir_loop *cur_loop;
-/* Condition for performing copy_walk. */
+/* Flag for kind of unrolling. */
+typedef enum {
+ constant,
+ invariant
+} unrolling_kind_flag;
+
+/* Condition for performing visiting a node during copy_walk. */
typedef unsigned walker_condition(ir_node *);
-/* Node and position of a predecessor */
-typedef struct out_edge {
+/* Node and position of a predecessor. */
+typedef struct entry_edge {
ir_node *node;
int pos;
-} out_edge;
-
-/**/
-typedef struct inversion_node_info {
- ir_node *copy;
- ir_node **ins;
- struct inversion_node_info *free_list_next; /* linked list to free all node_infos */
-} inversion_node_info;
-
-/* */
-typedef struct node_info {
- ir_node **copy;
- ir_node **ins;
- struct ir_node *free_list_next; /* linked list to free all node_infos */
-} node_info;
-
-/* Head of the list for freeing node_infos */
-static ir_node *free_list;
+ ir_node *pred;
+} entry_edge;
-/* A walker may start visiting the current loop with these nodes. */
-static out_edge *cur_loop_outs;
+/* Node info for unrolling. */
+typedef struct unrolling_node_info {
+ ir_node **copies;
+} unrolling_node_info;
/* Outs of the nodes head. */
-static out_edge *cur_head_outs;
+static entry_edge *cur_head_outs;
/* Information about the loop head */
static ir_node *loop_head = NULL;
/* List of all inner loops, that are processed. */
static ir_loop **loops;
-/* Inverted head */
-static ir_node *loop_inv_head = NULL;
-/* Peeled head */
-static ir_node *loop_peeled_head = NULL;
-
-/* Loop analysis informations */
-typedef struct loop_info_t {
- unsigned blocks; /* number of blocks in the loop */
- unsigned calls; /* number of calls */
- unsigned cf_outs;
- out_edge cf_out;
- ir_node *new_loop_head;
-} loop_info_t;
-
-/* Information about the current loop */
-static loop_info_t loop_info;
-
-/* Outs of the condition chain (loop inversion). */
-static out_edge *cond_chain_entries;
-
-/* Arity of the unrolled loop heads. */
-static int unroll_arity;
-
-static ir_phase *phase;
+#if LOOP_OPT_STATS
+#define count_stats(val) (++val)
+#define print_stats() (do_print_stats())
+#define reset_stats() (do_reset_stats())
+/* Stats */
+typedef struct loop_stats_t {
+ unsigned loops;
+ unsigned inverted;
+ unsigned too_large;
+ unsigned too_large_adapted;
+ unsigned cc_limit_reached;
+ unsigned calls_limit;
-/* TODO */
-static unsigned head_inversion_node_count;
-static unsigned inversion_head_node_limit;
-static unsigned head_inversion_block_count;
+ unsigned u_simple_counting_loop;
+ unsigned constant_unroll;
+ unsigned invariant_unroll;
-static unsigned enable_peeling;
-static unsigned enable_inversion;
-static unsigned enable_unrolling;
+ unsigned unhandled;
+} loop_stats_t;
+static loop_stats_t stats;
-/* Creates node_info. A linked list keeps all node_infos to free them again. */
-static node_info *new_node_info(ir_node *node)
+/* Set stats to sero */
+static void do_reset_stats(void)
{
- node_info *l = XMALLOCZ(node_info);
- l->free_list_next = free_list;
- free_list = node;
- l->copy = NULL;
- return l;
+ memset(&stats, 0, sizeof(loop_stats_t));
}
-/* Returns linked node_info for given node. */
-static node_info *get_node_info(ir_node *n)
+/* Print stats */
+static void do_print_stats(void)
{
- return ((node_info *)get_irn_link(n));
+ DB((dbg, LEVEL_2, "---------------------------------------\n"));
+ DB((dbg, LEVEL_2, "loops : %d\n",stats.loops));
+ DB((dbg, LEVEL_2, "inverted : %d\n",stats.inverted));
+ DB((dbg, LEVEL_2, "too_large : %d\n",stats.too_large));
+ DB((dbg, LEVEL_2, "too_large_adapted : %d\n",stats.too_large_adapted));
+ DB((dbg, LEVEL_2, "cc_limit_reached : %d\n",stats.cc_limit_reached));
+ DB((dbg, LEVEL_2, "calls_limit : %d\n",stats.calls_limit));
+ DB((dbg, LEVEL_2, "u_simple_counting : %d\n",stats.u_simple_counting_loop));
+ DB((dbg, LEVEL_2, "constant_unroll : %d\n",stats.constant_unroll));
+ DB((dbg, LEVEL_2, "invariant_unroll : %d\n",stats.invariant_unroll));
+ DB((dbg, LEVEL_2, "=======================================\n"));
}
+#else
+/* No stats */
+#define count_stats(val) ((void)0)
+#define print_stats() ((void)0)
+#define reset_stats() ((void)0)
-/* Allocates a node_info struct for the given node */
-static void alloc_node_info(ir_node *node)
-{
- node_info *state;
- state = new_node_info(node);
- set_irn_link(node, (void *)state);
-}
+#endif
-/* Frees node info and copy array for given node. Returns next node of free_list. */
-static ir_node *free_info(ir_node *node)
-{
- node_info *info = get_node_info(node);
- ir_node *next = info->free_list_next;
- /*DB((dbg, LEVEL_1, "FREE %N\n", node));*/
- DEL_ARR_F(info->copy);
- xfree(info);
- set_irn_link(node, NULL);
- return next;
-}
+/* Commandline parameters */
+typedef struct loop_opt_params_t {
+unsigned max_loop_size; /* Maximum number of nodes [nodes]*/
+int depth_adaption; /* Loop nest depth adaption [percent] */
+unsigned allowed_calls; /* Number of calls allowed [number] */
+unsigned count_phi:1; /* Count phi nodes */
+unsigned count_proj:1; /* Count projections */
-/* Free all created node_infos, including the copy arrays. */
-static void free_node_info(void)
-{
- ir_node *node = free_list;
- while (node) {
- node = free_info(node);
- }
- free_list = NULL;
-}
+unsigned max_cc_size; /* Maximum condition chain size [nodes] */
+unsigned max_branches;
-/* Free node_infos of blocks only, including the copy arrays. */
-static void free_node_info_blocks(void)
-{
- ir_node *node = free_list;
- ir_node *new_freelist = NULL;
- while (node) {
- ir_node *next;
- if (is_Block(node)) {
- next = free_info(node);
- } else {
- next = get_node_info(node)->free_list_next;
- get_node_info(node)->free_list_next = new_freelist;
- new_freelist = node;
- }
- node = next;
- }
- free_list = new_freelist;
-}
+unsigned max_unrolled_loop_size; /* [nodes] */
+unsigned allow_const_unrolling:1;
+unsigned allow_invar_unrolling:1;
+unsigned invar_unrolling_min_size; /* [nodes] */
-/* Reset nodes link. For use with a walker. */
-static void reset_link(ir_node *node, void *env)
-{
- (void)env;
- set_irn_link(node, NULL);
-}
+} loop_opt_params_t;
-static void set_inversion_copy(ir_node *n, ir_node *cp)
-{
- phase_set_irn_data(phase, n, cp);
-}
+static loop_opt_params_t opt_params;
-/* Returns a nodes copy. */
-static ir_node *get_copy(ir_node *n, int index)
-{
- ir_node *cp = ((node_info *)get_irn_link(n))->copy[index];
- return cp;
-}
+/* Loop analysis informations */
+typedef struct loop_info_t {
+ unsigned nodes; /* node count */
+ unsigned ld_st; /* load and store nodes */
+ unsigned branches; /* number of conditions */
+ unsigned calls; /* number of calls */
+ unsigned cf_outs; /* number of cf edges which leave the loop */
+ entry_edge cf_out; /* single loop leaving cf edge */
+ int be_src_pos; /* position of the single own backedge in the head */
+
+ /* for inversion */
+ unsigned cc_size; /* nodes in the condition chain */
+
+ /* for unrolling */
+ unsigned max_unroll; /* Number of unrolls satisfying max_loop_size */
+ unsigned exit_cond; /* 1 if condition==true exits the loop. */
+ unsigned latest_value:1; /* 1 if condition is checked against latest counter value */
+ unsigned needs_backedge:1; /* 0 if loop is completely unrolled */
+ unsigned decreasing:1; /* Step operation is_Sub, or step is<0 */
+
+ /* IV informations of a simple loop */
+ ir_node *start_val;
+ ir_node *step;
+ ir_node *end_val;
+ ir_node *iteration_phi;
+ ir_node *add;
+
+ ir_tarval *count_tar; /* Number of loop iterations */
+
+ ir_node *duff_cond; /* Duff mod */
+ unrolling_kind_flag unroll_kind; /* constant or invariant unrolling */
+} loop_info_t;
-/* Returns a nodes copy if it exists, or else the node. */
-static ir_node *get_inversion_copy(ir_node *n)
-{
- ir_node *cp = (ir_node *)phase_get_irn_data(phase, n);
- return cp;
-}
+/* Information about the current loop */
+static loop_info_t loop_info;
-/* Returns a nodes copy, or node if there is no node info linked. */
-static ir_node *get_copy_safe(ir_node *node, int index)
-{
- node_info *info = (node_info *)get_irn_link(node);
- if (info != NULL)
- return get_copy(node, index);
- else
- return node;
-}
+/* Outs of the condition chain (loop inversion). */
+static ir_node **cc_blocks;
+/* df/cf edges with def in the condition chain */
+static entry_edge *cond_chain_entries;
+/* Array of df loops found in the condition chain. */
+static entry_edge *head_df_loop;
+/* Number of blocks in cc */
+static unsigned inversion_blocks_in_cc;
+
+
+/* Cf/df edges leaving the loop.
+ * Called entries here, as they are used to enter the loop with walkers. */
+static entry_edge *loop_entries;
+/* Number of unrolls to perform */
+static int unroll_nr;
+/* Phase is used to keep copies of nodes. */
+static ir_phase *phase;
+
+/* Loop operations. */
+typedef enum loop_op_t {
+ loop_op_inversion,
+ loop_op_unrolling,
+ loop_op_peeling
+} loop_op_t;
-/* Assigns the given array to a nodes node_info */
-static void set_copy_arr(ir_node *n, ir_node **arr)
+/* Saves which loop operation to do until after basic tests. */
+static loop_op_t loop_op;
+
+/* Returns the maximum nodes for the given nest depth */
+static unsigned get_max_nodes_adapted(unsigned depth)
{
- ((node_info *)get_irn_link(n))->copy = arr;
+ double perc = 100.0 + (double)opt_params.depth_adaption;
+ double factor = pow(perc / 100.0, depth);
+
+ return (int)((double)opt_params.max_loop_size * factor);
}
-/* Assigns a copy with given index to a node.
- * Prerequirements are existing node_info and copy array. */
-static void set_copy(ir_node *n, int index, ir_node *copy)
+/* Reset nodes link. For use with a walker. */
+static void reset_link(ir_node *node, void *env)
{
- ((node_info *)get_irn_link(n))->copy[index] = copy;
+ (void)env;
+ set_irn_link(node, NULL);
}
/* Returns 0 if the node or block is not in cur_loop. */
return (get_irn_loop(get_block(node)) == cur_loop);
}
-/* Returns if the given be is an alien edge.
- * This is the case when the pred is not in the loop. */
-static unsigned is_alien_edge(ir_node *n, int i)
-{
- return(!is_in_loop(get_irn_n(n, i)));
-}
-
+/* Returns 0 if the given edge is not a backedge
+ * with its pred in the cur_loop. */
static unsigned is_own_backedge(ir_node *n, int pos)
{
return (is_backedge(n, pos) && is_in_loop(get_irn_n(n, pos)));
}
-/* Resets block mark for given node. For use with walker */
-static void reset_block_mark(ir_node *node, void * env)
-{
- (void) env;
-
- if (is_Block(node))
- set_Block_mark(node, 0);
-}
-
-static unsigned is_nodes_block_marked(ir_node* node)
-{
- if (is_Block(node))
- return get_Block_mark(node);
- else
- return get_Block_mark(get_block(node));
-}
-
-/* Returns the number of blocks in a loop. */
-static int get_loop_n_blocks(ir_loop *loop)
-{
- int elements, e;
- int blocks = 0;
- elements = get_loop_n_elements(loop);
-
- for (e=0; e<elements; e++) {
- loop_element elem = get_loop_element(loop, e);
- if (is_ir_node(elem.kind) && is_Block(elem.node))
- ++blocks;
- }
- return blocks;
-}
-
-/* */
-static void extend_ins_by_copy(ir_node *block, int pos)
-{
- ir_node **ins;
- ir_node *phi;
- int i;
- int arity = get_irn_arity(block);
- int new_arity = arity + 1;
- assert(is_Block(block));
-
- NEW_ARR_A(ir_node *, ins, new_arity);
-
- /* Extend block by copy of definition at pos */
- for(i = 0; i < arity; ++i) {
- ins[i] = get_irn_n(block, i);
- }
- ins[i] = get_inversion_copy(get_irn_n(block, pos));
-
- DB((dbg, LEVEL_5, "Extend block %N by %N\n", block, ins[i]));
-
- /* Fixes backedges. We rely on correct backedges. */
- set_irn_in(block, new_arity, ins);
-
- /* Extend block phis by copy of definition at pos */
- for_each_phi(block, phi) {
- ir_node *cp, *pred;
- for(i = 0; i < arity; ++i)
- ins[i] = get_irn_n(phi, i);
- pred = get_irn_n(phi, pos);
- cp = get_inversion_copy(pred);
- /* If the phis in is not in the condition chain (eg. a constant),
- * there is no copy. */
- if (cp == NULL)
- ins[i] = pred;
- else
- ins[i] = cp;
-
- DB((dbg, LEVEL_5, "Extend phi %N by %N\n", phi, ins[i]));
- set_irn_in(phi, new_arity, ins);
- }
-}
-
-/*
- * Extends all blocks which succeed the loop with the copied loops outs.
- * Also extends the blocks phis. Requires block phi list.
- * Returns an updated list of loop outs of the original loop outs.
- */
-static out_edge *extend_ins(out_edge *outs, int copies)
-{
- ir_node **ins;
- ir_node **phi_ins;
- int *bes, *phi_bes;
- ir_node *phi, *next_phi, *new_phi, *head, *new_block;
- int old_arity, new_arity;
- int i, c, p;
- out_edge *new_outs;
-
- inc_irg_visited(current_ir_graph);
-
- new_outs = NEW_ARR_F(out_edge, 0);
-
-#if 0
- for (i = 0; i < ARR_LEN(outs); ++i) {
- out_edge edge = outs[i];
- ir_node *node = edge.node;
- DB((dbg, LEVEL_5, "outs %N %d\n", node, edge.pos));
- }
-#endif
-
- for (i = 0; i < ARR_LEN(outs); ++i) {
- out_edge edge = outs[i];
- ir_node *node = edge.node;
- int in_c, positions_n;
- int *positions;
-
- if (!is_Block(node) && !is_Bad(node)) {
-#if 0
- if (is_Phi(node)) {
- int c;
- unsigned b = 0;
- ir_node *p = get_nodes_block(node);
- for(c = 0; c < get_irn_arity(p); ++c) {
- if (is_in_loop(get_irn_n(p, c))) {
- b=1;
- break;
- }
- }
- if (!b) {
- ARR_APP1(out_edge, new_outs, edge);
- DB((dbg, LEVEL_5, "new out %N\n", node));
- }
-
- } else {
-#endif
- ARR_APP1(out_edge, new_outs, edge);
- DB((dbg, LEVEL_5, "new out %N\n", node));
-
- }
-
- /* CONTINUE if node already processed. */
- if (irn_visited(node))
- continue;
-
- if (!is_Block(node))
- continue;
-
- positions = NEW_ARR_F(int, 0);
- positions_n = 0;
-
- /* Search for all occurences of the current node, and save the in positions. */
- for (p = 0; p < ARR_LEN(outs); ++p) {
- ir_node *cur = outs[p].node;
- int d_pos = outs[p].pos;
-
- if (node==cur) {
- DB((dbg, LEVEL_5, "Loop successor %N with pred @%d in loop\n",
- node, d_pos));
- ARR_APP1(int, positions, d_pos);
- mark_irn_visited(cur);
- ++positions_n;
- }
- }
-
- old_arity = get_irn_arity(node);
- new_arity = old_arity + (positions_n * copies);
-
- ins = NEW_ARR_F(ir_node*, new_arity);
- bes = NEW_ARR_F(int, new_arity);
-
- /* extend block ins */
- for (in_c = 0; in_c < old_arity; ++in_c) {
- ins[in_c] = get_irn_n(node, in_c);
- bes[in_c] = is_backedge(node, in_c);
- }
- for (p = 0; p < positions_n; ++p) {
- for (c = 0; c < copies; ++c) {
- ir_node *cp = get_copy_safe(get_irn_n(node, positions[p]), c);
- DB((dbg, LEVEL_5, "%N (new_arity %d) @%d = %N\n",
- node, new_arity, in_c, cp));
- ins[in_c] = cp;
- bes[in_c] = is_backedge(node, positions[p]);
- ++in_c;
- }
- }
-
- assert(new_arity == in_c);
-
- head = get_Block_phis(node);
- new_block = new_r_Block(get_irn_irg(node), new_arity, ins);
- set_irn_loop(new_block, get_irn_loop(node));
-
- for (in_c = 0; in_c < new_arity; ++in_c) {
- if (bes[in_c])
- set_backedge(new_block, in_c);
- }
- DEL_ARR_F(ins);
- DEL_ARR_F(bes);
-
-#if 1
- set_Block_phis(node, NULL);
-
- phi_ins = NEW_ARR_F(ir_node *, new_arity);
- phi_bes = NEW_ARR_F(int, new_arity);
-
- for_each_phi_safe(head, phi, next_phi) {
- for (in_c = 0; in_c < old_arity; ++in_c) {
- phi_ins[in_c] = get_irn_n(phi, in_c);
- phi_bes[in_c] = is_backedge(phi, in_c);
- }
-
- for (p = 0; p < positions_n; ++p) {
- for(c = 0; c < copies; ++c) {
- ir_node *cp, *pred;
- pred = get_irn_n(phi, positions[p]);
- DB((dbg, LEVEL_5, "Phi %N pred @%d is %N\n",
- phi, positions[p], pred));
- cp = get_copy_safe(pred, c);
- phi_ins[in_c] = cp;
- DB((dbg, LEVEL_5, "Phi %N in %d is %N\n",
- phi, in_c, cp));
- phi_bes[in_c] = is_backedge(phi, positions[p]);
- ++in_c;
- }
- }
-
- new_phi = new_r_Phi(new_block, new_arity, phi_ins, get_irn_mode(phi));
-
- for (in_c = 0; in_c < new_arity; ++in_c) {
- if (phi_bes[in_c])
- set_backedge(new_phi, in_c);
- }
- exchange(phi, new_phi);
- DB((dbg, LEVEL_5, "exch Phi %N %N\n",phi, new_phi));
-
- add_Block_phi(new_block, new_phi);
- }
-
- DEL_ARR_F(phi_ins);
- DEL_ARR_F(phi_bes);
-#endif
- exchange(node, new_block);
- set_Block_MacroBlock(new_block, new_block);
- DB((dbg, LEVEL_5, "exch block %N %N\n", node, new_block));
-
- DEL_ARR_F(positions);
- }
- return new_outs;
-}
-
-/**
- * Finds loop head and loop_info.
- */
+/* Finds loop head and some loop_info as calls or else if necessary. */
static void get_loop_info(ir_node *node, void *env)
{
unsigned node_in_loop, pred_in_loop;
pred_in_loop = is_in_loop(pred);
node_in_loop = is_in_loop(node);
+ if (!node_in_loop && pred_in_loop && is_Block(node))
+ {
+ entry_edge entry;
+ entry.node = node;
+ entry.pos = i;
+ entry.pred = pred;
+ /* Count cf outs */
+ ++loop_info.cf_outs;
+ loop_info.cf_out = entry;
+ }
+
/* collect some loop information */
if (node_in_loop) {
+ if (is_Phi(node) && opt_params.count_phi)
+ ++loop_info.nodes;
+ else if (is_Proj(node) && opt_params.count_proj)
+ ++loop_info.nodes;
+ else if (!is_Confirm(node) && !is_Const(node) && !is_SymConst(node))
+ ++loop_info.nodes;
+
+ if (is_Load(node) || is_Store(node))
+ ++loop_info.ld_st;
+
if (is_Call(node))
++loop_info.calls;
+
}
/* Find the loops head/the blocks with cfpred outside of the loop */
- if (is_Block(node) && node_in_loop && !pred_in_loop && loop_head_valid) {
- ir_node *cfgpred = get_Block_cfgpred(node, i);
-
- if (!is_in_loop(cfgpred)) {
- DB((dbg, LEVEL_5, "potential head %+F because inloop and pred %+F not inloop\n",
- node, pred));
- /* another head? We do not touch this. */
- if (loop_head && loop_head != node) {
- loop_head_valid = 0;
- } else {
- loop_head = node;
+ if (is_Block(node)) {
+ const ir_edge_t *edge;
+ unsigned outs_n = 0;
+
+ /* Count innerloop branches */
+ foreach_out_edge_kind(node, edge, EDGE_KIND_NORMAL) {
+ if (is_Block(get_edge_src_irn(edge)) && is_in_loop(get_edge_src_irn(edge)))
+ ++outs_n;
+ }
+ if (outs_n > 1)
+ ++loop_info.branches;
+
+ if (node_in_loop && !pred_in_loop && loop_head_valid) {
+ ir_node *cfgpred = get_Block_cfgpred(node, i);
+
+ if (!is_in_loop(cfgpred)) {
+ DB((dbg, LEVEL_5, "potential head %+F because inloop and pred %+F not inloop\n",
+ node, pred));
+ /* another head? We do not touch this. */
+ if (loop_head && loop_head != node) {
+ loop_head_valid = 0;
+ } else {
+ loop_head = node;
+ }
}
}
}
}
}
-/**/
-static void correct_phis(ir_node *node, void *env)
-{
- (void)env;
-
- if (is_Phi(node) && get_irn_arity(node) == 1) {
- ir_node *exch;
- ir_node *in[1];
- in[0] = get_irn_n(node, 0);
-
- exch = new_rd_Phi(get_irn_dbg_info(node),
- get_nodes_block(node), 1, in,
- get_irn_mode(node));
-
- exchange(node, exch);
- /* TODO make sure visited is copied */
- }
-
-
-}
-/* Adds all nodes pointing into the loop to loop_entries and also finds the loops head */
-static void get_loop_outs(ir_node *node, void *env)
+/* Finds all edges with users outside of the loop
+ * and definition inside the loop. */
+static void get_loop_entries(ir_node *node, void *env)
{
unsigned node_in_loop, pred_in_loop;
int i, arity;
node_in_loop = is_in_loop(node);
if (pred_in_loop && !node_in_loop) {
- out_edge entry;
+ entry_edge entry;
entry.node = node;
entry.pos = i;
- ARR_APP1(out_edge, cur_loop_outs, entry);
- if (is_Block(node)) {
- ++loop_info.cf_outs;
- loop_info.cf_out = entry;
- }
- DB((dbg, LEVEL_5, "loop outs %N\n", node));
+ entry.pred = pred;
+ ARR_APP1(entry_edge, loop_entries, entry);
}
}
}
+/* ssa */
static ir_node *ssa_second_def;
static ir_node *ssa_second_def_block;
/**
* Walks the graph bottom up, searching for definitions and creates phis.
*/
-static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode)
+static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode, int first)
{
int i;
int n_cfgpreds;
- ir_graph *irg;
+ ir_graph *irg = get_irn_irg(block);
ir_node *phi;
ir_node **in;
* Dead and bad blocks. */
if (get_irn_arity(block) < 1 || is_Bad(block)) {
DB((dbg, LEVEL_5, "ssa bad %N\n", block));
- return new_Bad();
+ return new_r_Bad(irg, mode);
}
- if (block == ssa_second_def_block) {
+ if (block == ssa_second_def_block && !first) {
DB((dbg, LEVEL_5, "ssa found second definition: use second def %N\n", ssa_second_def));
return ssa_second_def;
}
/* already processed this block? */
if (irn_visited(block)) {
- ir_node *value = get_irn_link(block);
+ ir_node *value = (ir_node *) get_irn_link(block);
DB((dbg, LEVEL_5, "ssa already visited: use linked %N\n", value));
return value;
}
- irg = get_irn_irg(block);
assert(block != get_irg_start_block(irg));
/* a Block with only 1 predecessor needs no Phi */
DB((dbg, LEVEL_5, "ssa 1 pred: walk pred %N\n", pred_block));
- value = search_def_and_create_phis(pred_block, mode);
+ value = search_def_and_create_phis(pred_block, mode, 0);
set_irn_link(block, value);
mark_irn_visited(block);
/* create a new Phi */
NEW_ARR_A(ir_node*, in, n_cfgpreds);
for (i = 0; i < n_cfgpreds; ++i)
- in[i] = new_Unknown(mode);
+ in[i] = new_r_Dummy(irg, mode);
phi = new_r_Phi(block, n_cfgpreds, in, mode);
-
-
/* Important: always keep block phi list up to date. */
add_Block_phi(block, phi);
-
DB((dbg, LEVEL_5, "ssa phi creation: link new phi %N to block %N\n", phi, block));
-
set_irn_link(block, phi);
mark_irn_visited(block);
ir_node *pred_val;
ir_node *pred_block = get_Block_cfgpred_block(block, i);
assert(pred_block != NULL);
- pred_val = search_def_and_create_phis(pred_block, mode);
+ pred_val = search_def_and_create_phis(pred_block, mode, 0);
+
assert(pred_val != NULL);
DB((dbg, LEVEL_5, "ssa phi pred:phi %N, pred %N\n", phi, pred_val));
set_irn_n(phi, i, pred_val);
}
+
return phi;
}
+
/**
* Given a set of values this function constructs SSA-form for the users of the
* first value (the users are determined through the out-edges of the value).
assert(orig_block && orig_val && second_block && second_val &&
"no parameter of construct_ssa may be NULL");
- /* no need to do anything */
if (orig_val == second_val)
return;
if (is_Phi(user)) {
ir_node *pred_block = get_Block_cfgpred_block(user_block, j);
- newval = search_def_and_create_phis(pred_block, mode);
+ newval = search_def_and_create_phis(pred_block, mode, 1);
} else {
- newval = search_def_and_create_phis(user_block, mode);
+ newval = search_def_and_create_phis(user_block, mode, 1);
}
-
- /* If we get a bad node the user keeps the original in. No second definition needed. */
if (newval != user && !is_Bad(newval))
set_irn_n(user, j, newval);
}
}
-/* Construct ssa for def and all of its copies.
- * NOTE: Overwrites links of blocks.
-*/
-static ir_node *construct_ssa_n(ir_node *def, ir_node *user, int copies)
-{
- ir_graph *irg;
- ir_mode *mode;
- irg = get_irn_irg(def);
- int i, user_arity;
- ir_node *newval;
+/***** Unrolling Helper Functions *****/
- ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
- inc_irg_visited(current_ir_graph);
- mode = get_irn_mode(def);
+/* Assign the copy with index nr to node n */
+static void set_unroll_copy(ir_node *n, int nr, ir_node *cp)
+{
+ unrolling_node_info *info;
+ assert(nr != 0 && "0 reserved");
- set_irn_link(get_nodes_block(def), def);
- mark_irn_visited(get_nodes_block(def));
+ info = (unrolling_node_info *)phase_get_irn_data(phase, n);
+ if (! info) {
+ ir_node **arr;
- for (i = 0; i < copies; ++i) {
- ir_node *cp = get_copy(def, i);
- ir_node *block = get_nodes_block(cp);
- set_irn_link(block, cp);
- mark_irn_visited(block);
+ info = XMALLOCZ(unrolling_node_info);
+ arr = NEW_ARR_F(ir_node *, unroll_nr);
+ info->copies = arr;
+ memset(info->copies, 0, (unroll_nr) * sizeof(ir_node *));
- DB((dbg, LEVEL_5, "ssa mark cp %N of def %N usr %N\n", cp, def, user));
+ phase_set_irn_data(phase, n, info);
}
+ /* Original node */
+ info->copies[0] = n;
- /* TODO BUG BUG */
- newval = user;
- user_arity = get_irn_arity(user);
- for (i = 0; i < user_arity; ++i) {
- ir_node *user_block = get_nodes_block(user);
- if (get_irn_n(user, i) != def)
- continue;
+ info->copies[nr] = cp;
+}
- DB((dbg, LEVEL_5, "ssa_n found edge of user %N\n", user));
+/* Returns a nodes copy if it exists, else NULL. */
+static ir_node *get_unroll_copy(ir_node *n, int nr)
+{
+ ir_node *cp;
+ unrolling_node_info *info = (unrolling_node_info *)phase_get_irn_data(phase, n);
+ if (! info)
+ return NULL;
- if (is_Phi(user)) {
- ir_node *pred_block = get_Block_cfgpred_block(user_block, i);
- newval = search_def_and_create_phis(pred_block, mode);
- } else {
- newval = search_def_and_create_phis(user_block, mode);
- }
- /*TODO bads should not happen! */
- if (newval != user) {
- DB((dbg, LEVEL_5, "=> ssa_n new in is %N\n", newval));
- set_irn_n(user, i, newval);
- /*if (is_Phi(newval) && get_nodes_block(newval)== user_block) {
- ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
- return newval;
- }*/
- }
+ cp = info->copies[nr];
+ return cp;
+}
- /* BREAK, as we found and handled the definition */
- break;
-#if 0
- if (is_Bad(newval)) {
- DB((dbg, LEVEL_5, "=> ssa_n new in is BAD %N in graph %N\n", newval, current_ir_graph));
- add_End_keepalive(get_irg_end(current_ir_graph), newval);
- dump_ir_block_graph(current_ir_graph, "-bad");
- assert(0);
+/***** Inversion Helper Functions *****/
- }
-#endif
- }
+/* Sets copy cp of node n. */
+static void set_inversion_copy(ir_node *n, ir_node *cp)
+{
+ phase_set_irn_data(phase, n, cp);
+}
- ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
- return NULL;
+/* Getter of copy of n for inversion */
+static ir_node *get_inversion_copy(ir_node *n)
+{
+ ir_node *cp = (ir_node *)phase_get_irn_data(phase, n);
+ return cp;
}
-/* Returns the number of backedges with or without alien bes. */
-static int get_backedge_n(ir_node *loophead, unsigned with_alien)
+/* Resets block mark for given node. For use with walker */
+static void reset_block_mark(ir_node *node, void * env)
{
- int i;
- int be_n = 0;
- int arity = get_irn_arity(loophead);
+ (void) env;
+
+ if (is_Block(node))
+ set_Block_mark(node, 0);
+}
+
+/* Returns mark of node, or its block if node is not a block.
+ * Used in this context to determine if node is in the condition chain. */
+static unsigned is_nodes_block_marked(ir_node* node)
+{
+ if (is_Block(node))
+ return get_Block_mark(node);
+ else
+ return get_Block_mark(get_block(node));
+}
+
+/* Extends a nodes ins by node new.
+ * NOTE: This is slow if a node n needs to be extended more than once. */
+static void extend_irn(ir_node *n, ir_node *newnode, int new_is_backedge)
+{
+ ir_node **ins;
+ int i;
+ int arity = get_irn_arity(n);
+ int new_arity = arity + 1;
+ int *bes;
+
+ NEW_ARR_A(int, bes, new_arity);
+ NEW_ARR_A(ir_node *, ins, new_arity);
+
+ /* save bes */
+ /* Bes are important!
+ * Another way would be recreating the looptree,
+ * but after that we cannot distinguish already processed loops
+ * from not yet processed ones. */
+ if (is_Block(n)) {
+ for(i = 0; i < arity; ++i) {
+ bes[i] = is_backedge(n, i);
+ }
+ bes[i] = new_is_backedge;
+ }
+
+ for(i = 0; i < arity; ++i) {
+ ins[i] = get_irn_n(n, i);
+ }
+ ins[i] = newnode;
+
+ set_irn_in(n, new_arity, ins);
+
+ /* restore bes */
+ if (is_Block(n)) {
+ for(i = 0; i < new_arity; ++i) {
+ if (bes[i])
+ set_backedge(n, i);
+ }
+ }
+}
+
+/* Extends a block by a copy of its pred at pos,
+ * fixing also the phis in the same way. */
+static void extend_ins_by_copy(ir_node *block, int pos)
+{
+ ir_node *new_in;
+ ir_node *phi;
+ ir_node *pred;
+ assert(is_Block(block));
+
+ /* Extend block by copy of definition at pos */
+ pred = get_irn_n(block, pos);
+ new_in = get_inversion_copy(pred);
+ DB((dbg, LEVEL_5, "Extend block %N by %N cp of %N\n", block, new_in, pred));
+ extend_irn(block, new_in, 0);
+
+ /* Extend block phis by copy of definition at pos */
+ for_each_phi(block, phi) {
+ ir_node *pred, *cp;
+
+ pred = get_irn_n(phi, pos);
+ cp = get_inversion_copy(pred);
+ /* If the phis in is not in the condition chain (eg. a constant),
+ * there is no copy. */
+ if (cp == NULL)
+ new_in = pred;
+ else
+ new_in = cp;
+
+ DB((dbg, LEVEL_5, "Extend phi %N by %N cp of %N\n", phi, new_in, pred));
+ extend_irn(phi, new_in, 0);
+ }
+}
+
+/* Returns the number of blocks backedges. With or without alien bes. */
+static int get_backedge_n(ir_node *block, unsigned with_alien)
+{
+ int i;
+ int be_n = 0;
+ int arity = get_irn_arity(block);
+
+ assert(is_Block(block));
+
for (i = 0; i < arity; ++i) {
- ir_node *pred = get_irn_n(loophead, i);
- if (is_backedge(loophead, i) && (with_alien || is_in_loop(pred)))
+ ir_node *pred = get_irn_n(block, i);
+ if (is_backedge(block, i) && (with_alien || is_in_loop(pred)))
++be_n;
}
return be_n;
}
-/**
- * Returns a raw copy of the given node.
- * Attributes are kept/set according to the needs of loop inversion.
- */
-static ir_node *copy_node_inversion(ir_node *node)
+/* Returns a raw copy of the given node.
+ * Attributes are kept/set according to the needs of loop inversion. */
+static ir_node *copy_node(ir_node *node)
{
int i, arity;
ir_node *cp;
cp = exact_copy(node);
arity = get_irn_arity(node);
+ /* Keep backedge info */
for (i = 0; i < arity; ++i) {
if (is_backedge(node, i))
set_backedge(cp, i);
}
- set_inversion_copy(node, cp);
- DB((dbg, LEVEL_5, "set copy of %N to cp %N \n", node, cp));
-
if (is_Block(cp)) {
- /* We may not keep the old macroblock. */
- set_Block_MacroBlock(cp, cp);
set_Block_mark(cp, 0);
}
+
return cp;
}
/**
* This walker copies all walked nodes.
* If the walk_condition is true for a node, it is copied.
- * All nodes node_info copy attributes have to be NULL prior to every walk.
+ * All nodes node_info->copy have to be NULL prior to every walk.
+ * Order of ins is important for later usage.
*/
static void copy_walk(ir_node *node, walker_condition *walk_condition,
- ir_loop *set_loop)
+ ir_loop *set_loop)
{
int i;
int arity;
/* Here we rely on nodestate's copy being initialized with NULL */
DB((dbg, LEVEL_5, "copy_walk: We have already visited %N\n", node));
if (get_inversion_copy(node) == NULL) {
- cp = copy_node_inversion(node);
+ cp = copy_node(node);
+ set_inversion_copy(node, cp);
+
DB((dbg, LEVEL_5, "The TEMP copy of %N is created %N\n", node, cp));
}
return;
/* copy node / finalize temp node */
if (get_inversion_copy(node) == NULL) {
/* No temporary copy existent */
- cp = copy_node_inversion(node);
+ cp = copy_node(node);
+ set_inversion_copy(node, cp);
DB((dbg, LEVEL_5, "The FINAL copy of %N is CREATED %N\n", node, cp));
} else {
/* temporary copy is existent but without correct ins */
add_Block_phi(cpblock, cp);
}
- set_irn_loop(cp, set_loop);
-
/* Keeps phi list of temporary node. */
set_irn_in(cp, ARR_LEN(cpin), cpin);
}
-/* Creates a new node from a given one, but with custom ins. */
-static ir_node *copy_node_changed(
- ir_node *node, ir_node *block, int arity, ir_node **ins, ir_loop *loop)
+/**
+ * This walker copies all walked nodes.
+ * If the walk_condition is true for a node, it is copied.
+ * All nodes node_info->copy have to be NULL prior to every walk.
+ * Order of ins is important for later usage.
+ * Takes copy_index, to phase-link copy at specific index.
+ */
+static void copy_walk_n(ir_node *node, walker_condition *walk_condition,
+ int copy_index)
{
+ int i;
+ int arity;
ir_node *cp;
- DB((dbg, LEVEL_5, "New node from %N in %N block %N arity %d\n",
- node, get_irn_irg(node), block, arity));
-#if 0
- if (is_Phi(node)) {
- cp = new_rd_Phi(get_irn_dbg_info(node),
- block,
- arity,
- ins,
- get_irn_mode(node));
+ ir_node **cpin;
- } else {
-#endif
- /* We want to keep phi nodes with arity 1, as it makes rewiring a lot easier. */
- cp = new_ir_node(get_irn_dbg_info(node),
- get_irn_irg(node),
- block,
- get_irn_op(node),
- get_irn_mode(node),
- arity,
- ins);
-
- /* By any means, keep the blocks phi list up-to-date,
- because regaining it would destroy the links. */
- if (is_Phi(cp))
- add_Block_phi(block, cp);
-/* TODO */
- if (get_irn_op(node) == get_irn_op(cp))
- copy_node_attr(get_irn_irg(node), node, cp);
-
- /*new_backedge_info(cp); function removed */
- if (is_Block(cp))
- set_Block_MacroBlock(cp, cp);
-
- set_irn_loop(cp, loop);
-
- /* Blocks are copied first, so that future phi nodes populate the phi list. */
- if (is_Block(cp))
- set_Block_phis(cp, NULL);
-
- DB((dbg, LEVEL_5, "New node %N in %N block %N arity %d\n",
- cp, get_irn_irg(cp), block, arity));
- return cp;
-}
+ /**
+ * break condition and cycle resolver, creating temporary node copies
+ */
+ if (irn_visited(node)) {
+ /* Here we rely on nodestate's copy being initialized with NULL */
+ DB((dbg, LEVEL_5, "copy_walk: We have already visited %N\n", node));
+ if (get_unroll_copy(node, copy_index) == NULL) {
+ ir_node *u;
+ u = copy_node(node);
+ set_unroll_copy(node, copy_index, u);
+ DB((dbg, LEVEL_5, "The TEMP unknown of %N is created %N\n", node, u));
+ }
+ return;
+ }
-/* To be exchangeable, the unknown needs to have proper graph set. */
-static ir_node *new_node_unknown(ir_node *block, ir_mode *mode)
-{
- ir_node *new = new_ir_node(NULL, get_irn_irg(block), block, op_Unknown, mode, 0, NULL);
- return new;
-}
+ /* Walk */
+ mark_irn_visited(node);
-/**
- * Walker, to copy alle nodes that meet the walk_condition.
- * Blocks are copied first, which is important for the creation of the phi lists.
- *
- */
-static ir_node *copy_walk_n(ir_node *node, walker_condition *walk_condition, int copy_index, int alloc_cp_arr)
-{
- int i;
- int arity;
- unsigned headblock = 0;
- ir_node *block, *cp, *new_cp;
- ir_node **ins = NULL;
+ if (!is_Block(node)) {
+ ir_node *block = get_nodes_block(node);
+ if (walk_condition(block))
+ DB((dbg, LEVEL_5, "walk block %N\n", block));
+ copy_walk_n(block, walk_condition, copy_index);
+ }
- if (irn_visited(node)) {
- cp = get_copy(node, copy_index);
+ arity = get_irn_arity(node);
+ NEW_ARR_A(ir_node *, cpin, arity);
- DB((dbg, LEVEL_5, "Visited %N\n", node));
+ for (i = 0; i < arity; ++i) {
+ ir_node *pred = get_irn_n(node, i);
- if (cp != NULL) {
- DB((dbg, LEVEL_5, "Visited. Return copy %N\n", cp));
- return cp;
+ if (walk_condition(pred)) {
+ DB((dbg, LEVEL_5, "walk node %N\n", pred));
+ copy_walk_n(pred, walk_condition, copy_index);
+ cpin[i] = get_unroll_copy(pred, copy_index);
+ } else {
+ cpin[i] = pred;
}
+ }
- if (!is_Block(node)) {
- ir_node *unknown = new_node_unknown(
- get_nodes_block(node),
- get_irn_mode(node));
- DB((dbg, LEVEL_5, " #### Create Unknown %N for %N\n", unknown, node));
- set_copy(node, copy_index, unknown);
- return unknown;
- }
+ /* copy node / finalize temp node */
+ cp = get_unroll_copy(node, copy_index);
+ if (cp == NULL || is_Unknown(cp)) {
+ cp = copy_node(node);
+ set_unroll_copy(node, copy_index, cp);
+ DB((dbg, LEVEL_5, "The FINAL copy of %N is CREATED %N\n", node, cp));
} else {
- DB((dbg, LEVEL_5, "Walk %N\n", node));
- mark_irn_visited(node);
-
- /* Allocate array of copies */
- if (alloc_cp_arr > 0) {
- ir_node **arr = NEW_ARR_F(ir_node *, alloc_cp_arr);
- alloc_node_info(node);
- for (i = 0; i < alloc_cp_arr; ++i)
- arr[i] = NULL;
- set_copy_arr(node, arr);
- }
+ /* temporary copy is existent but without correct ins */
+ cp = get_unroll_copy(node, copy_index);
+ DB((dbg, LEVEL_5, "The FINAL copy of %N is EXISTENT %N\n", node, cp));
}
- block = NULL;
if (!is_Block(node)) {
- ir_node *orig_block = get_nodes_block(node);
- DB((dbg, LEVEL_5, "current node: %N about to walk block %N\n", node, orig_block));
- /* Check walk_condition for blocks not necessary */
-
- if (orig_block == loop_head && is_Phi(node))
- headblock = 1;
+ ir_node *cpblock = get_unroll_copy(get_nodes_block(node), copy_index);
- block = copy_walk_n(orig_block, walk_condition, copy_index, alloc_cp_arr);
- DB((dbg, LEVEL_5, "current node: %N block %N blocks copy %N\n",
- node, orig_block, block));
- } else {
- if (node == loop_head)
- headblock = 1;
+ set_nodes_block(cp, cpblock );
+ if (is_Phi(cp))
+ add_Block_phi(cpblock, cp);
}
+ /* Keeps phi list of temporary node. */
+ set_irn_in(cp, ARR_LEN(cpin), cpin);
+}
- arity = get_irn_arity(node);
+/* Removes alle Blocks with non marked predecessors from the condition chain. */
+static void unmark_not_allowed_cc_blocks(void)
+{
+ size_t blocks = ARR_LEN(cc_blocks);
+ size_t i;
- if (headblock) {
- /* Headblock and headblock-phi case */
- int in_c = 0;
- DB((dbg, LEVEL_5, "Headblock/Phi from headblock\n"));
- NEW_ARR_A(ir_node *, ins, unroll_arity);
+ for(i = 0; i < blocks; ++i) {
+ ir_node *block = cc_blocks[i];
+ int a;
+ int arity = get_irn_arity(block);
- for (i = 0; i < arity; ++i) {
- ir_node *ret;
- ir_node *pred = get_irn_n(node, i);
- if (is_backedge(loop_head, i)) {
- if (walk_condition(pred)) {
- ret = copy_walk_n(pred, walk_condition, copy_index, alloc_cp_arr);
- DB((dbg, LEVEL_5, "in %d = %N walked\n", i, ret));
- } else {
- ret = pred;
- DB((dbg, LEVEL_5, "in %d = %N not walked\n", i, ret));
- }
- ins[in_c++] = ret;
- }
- }
- arity = unroll_arity;
- } else {
- /* Normal case */
- NEW_ARR_A(ir_node *, ins, arity);
+ /* Head is an exception. */
+ if (block == loop_head)
+ continue;
- for (i = 0; i < arity; ++i) {
- ir_node *ret;
- ir_node *pred = get_irn_n(node, i);
- if (walk_condition(pred)) {
- ret = copy_walk_n(pred, walk_condition, copy_index, alloc_cp_arr);
- DB((dbg, LEVEL_5, "in %d = %N walked\n", i, ret));
- } else {
- ret = pred;
- DB((dbg, LEVEL_5, "in %d = %N not walked\n", i, ret));
+ for(a = 0; a < arity; ++a) {
+ if (! is_nodes_block_marked(get_irn_n(block, a))) {
+ set_Block_mark(block, 0);
+ --inversion_blocks_in_cc;
+ DB((dbg, LEVEL_5, "Removed %N from cc (blocks in cc %d)\n",
+ block, inversion_blocks_in_cc));
+
+ break;
}
- ins[i] = ret;
}
}
+}
- /* NOW, after the walk, we may check if the blocks copy is already present. */
- cp = get_copy(node, copy_index);
- if (cp != NULL && !is_Unknown(cp)) {
- DB((dbg, LEVEL_5, "Must be Block %N copy is already present\n", node, cp));
- assert(is_Block(cp) &&
- "sanity: The copy should have been a block.");
- return cp;
- }
+/* Unmarks all cc blocks using cc_blocks except head.
+ * TODO: invert head for unrolling? */
+static void unmark_cc_blocks(void)
+{
+ size_t blocks = ARR_LEN(cc_blocks);
+ size_t i;
- new_cp = copy_node_changed(node, block, arity, ins, cur_loop);
- set_copy(node, copy_index, new_cp);
+ for(i = 0; i < blocks; ++i) {
+ ir_node *block = cc_blocks[i];
- if (cp != NULL && is_Unknown(cp)) {
- DB((dbg, LEVEL_5, "Found unknown %N in %N now exchanged by %N in %N\n",
- cp, get_irn_irg(cp), new_cp, get_irn_irg(new_cp)));
- exchange(cp, new_cp);
+ /* TODO Head is an exception. */
+ /*if (block != loop_head)*/
+ set_Block_mark(block, 0);
}
- return new_cp;
+ /*inversion_blocks_in_cc = 1;*/
+ inversion_blocks_in_cc = 0;
+
+ /* invalidate */
+ loop_info.cc_size = 0;
}
/**
* Populates head_entries with (node, pred_pos) tuple
- * whereas the node's pred at pred_pos is in the head but not the node itself.
- * Head and condition chain blocks must be marked.
+ * whereas the node's pred at pred_pos is in the cc but not the node itself.
+ * Also finds df loops inside the cc.
+ * Head and condition chain blocks have been marked previously.
*/
static void get_head_outs(ir_node *node, void *env)
{
int arity = get_irn_arity(node);
(void) env;
- DB((dbg, LEVEL_5, "get head entries %N \n", node));
-
for (i = 0; i < arity; ++i) {
- /* node is not in the head, but the predecessor is.
- * (head or loop chain nodes are marked) */
-
- DB((dbg, LEVEL_5, "... "));
- DB((dbg, LEVEL_5, "node %N marked %d (0) pred %d marked %d (1) \n",
- node, is_nodes_block_marked(node), i,
- is_nodes_block_marked(get_irn_n(node, i))));
-
if (!is_nodes_block_marked(node) && is_nodes_block_marked(get_irn_n(node, i))) {
- out_edge entry;
+ entry_edge entry;
entry.node = node;
entry.pos = i;
- ARR_APP1(out_edge, cur_head_outs, entry);
+ /* Saving also predecessor seems redundant, but becomes
+ * necessary when changing position of it, before
+ * dereferencing it.*/
+ entry.pred = get_irn_n(node, i);
+ ARR_APP1(entry_edge, cur_head_outs, entry);
+ }
+ }
- if (is_in_loop(node) && is_Block(node)) {
- loop_info.new_loop_head = node;
- DB((dbg, LEVEL_5, " SET NEW LOOPHEAD to %N\n", node));
+ arity = get_irn_arity(loop_head);
+
+ /* Find df loops inside the cc */
+ if (is_Phi(node) && get_nodes_block(node) == loop_head) {
+ for (i = 0; i < arity; ++i) {
+ if (is_own_backedge(loop_head, i)) {
+ if (is_nodes_block_marked(get_irn_n(node, i))) {
+ entry_edge entry;
+ entry.node = node;
+ entry.pos = i;
+ entry.pred = get_irn_n(node, i);
+ ARR_APP1(entry_edge, head_df_loop, entry);
+ DB((dbg, LEVEL_5, "Found incc assignment node %N @%d is pred %N, graph %N %N\n",
+ node, i, entry.pred, current_ir_graph, get_irg_start_block(current_ir_graph)));
+ }
}
}
}
}
/**
- * Find condition chains, and add them to be inverted
+ * Find condition chains, and add them to be inverted.
* A block belongs to the chain if a condition branches out of the loop.
+ * (Some blocks need to be removed once again.)
* Returns 1 if the given block belongs to the condition chain.
*/
-static unsigned find_condition_chains(ir_node *block)
+static unsigned find_condition_chain(ir_node *block)
{
- const ir_edge_t *edge;
+ const ir_edge_t *edge;
unsigned mark = 0;
- int nodes_n = 0;
+ unsigned has_be = 0;
+ unsigned jmp_only;
+ unsigned nodes_n = 0;
+
+ mark_irn_visited(block);
DB((dbg, LEVEL_5, "condition_chains for block %N\n", block));
- /* Collect all outs, including keeps. */
+ /* Get node count */
foreach_out_edge_kind(block, edge, EDGE_KIND_NORMAL) {
++nodes_n;
}
- /* Leave at least one block as body. */
- if (head_inversion_node_count + nodes_n > inversion_head_node_limit
- || head_inversion_block_count + 1 == loop_info.blocks) {
+ /* Check if node count would exceed maximum cc size.
+ * TODO
+ * This is not optimal, as we search depth-first and break here,
+ * continuing with another subtree. */
+ if (loop_info.cc_size + nodes_n > opt_params.max_cc_size) {
set_Block_mark(block, 0);
-
return 0;
}
- /* First: check our successors,
- * and add all of them, which are outside of the loop, to the list */
- foreach_block_succ(block, edge) {
- ir_node *src = get_edge_src_irn( edge );
- int pos = get_edge_src_pos( edge );
+ /* Check if block only has a jmp instruction. */
+ jmp_only = 1;
+ foreach_out_edge(block, edge) {
+ ir_node *src = get_edge_src_irn(edge);
- if (!is_in_loop(src)) {
- out_edge entry;
+ if (! is_Block(src) && ! is_Jmp(src)) {
+ jmp_only = 0;
+ }
+ }
+
+ /* Check cf outs if one is leaving the loop,
+ * or if this node has a backedge. */
+ foreach_block_succ(block, edge) {
+ ir_node *src = get_edge_src_irn(edge);
+ int pos = get_edge_src_pos(edge);
+ if (! is_in_loop(src))
mark = 1;
- entry.node = src;
- entry.pos = pos;
- ARR_APP1(out_edge, cond_chain_entries, entry);
- mark_irn_visited(src);
+
+ /* Inverting blocks with backedge outs leads to a cf edge
+ * from the inverted head, into the inverted head (skipping the body).
+ * As the body becomes the new loop head,
+ * this would introduce another loop in the existing loop.
+ * This loop inversion cannot cope with this case. */
+ if (is_backedge(src, pos)) {
+ has_be = 1;
+ break;
}
}
- if (mark == 0) {
- set_Block_mark(block, 0);
- return 0;
- } else {
+ /* We need all predecessors to already belong to the condition chain.
+ * Example of wrong case: * == in cc
+ *
+ * Head* ,--.
+ * /| \ B |
+ * / A* B / |
+ * / /\ / ? |
+ * / C* => D |
+ * / D Head |
+ * / A \_|
+ * C
+ */
+ /* Collect blocks containing only a Jmp.
+ * Do not collect blocks with backedge outs. */
+ if ((jmp_only == 1 || mark == 1) && has_be == 0) {
set_Block_mark(block, 1);
- ++head_inversion_block_count;
+ ++inversion_blocks_in_cc;
+ loop_info.cc_size += nodes_n;
DB((dbg, LEVEL_5, "block %N is part of condition chain\n", block));
- head_inversion_node_count += nodes_n;
+ ARR_APP1(ir_node *, cc_blocks, block);
+ } else {
+ set_Block_mark(block, 0);
}
- /* Second: walk all successors,
- * and add them to the list if they are not part of the chain */
foreach_block_succ(block, edge) {
- unsigned inchain;
ir_node *src = get_edge_src_irn( edge );
- int pos = get_edge_src_pos( edge );
-
- /* already done */
- if (!is_in_loop( src ) || irn_visited(src)) {
- continue;
- }
- mark_irn_visited(src);
- DB((dbg, LEVEL_5, "condition chain walk %N\n", src));
- inchain = find_condition_chains(src);
-
- /* if successor is not part of chain we need to collect its outs */
- if (!inchain) {
- out_edge entry;
- entry.node = src;
- entry.pos = pos;
- ARR_APP1(out_edge, cond_chain_entries, entry);
- }
+ if (is_in_loop(src) && ! irn_visited(src))
+ find_condition_chain(src);
}
+
return mark;
}
/**
- * Rewires the copied condition chain. Removes backedges.
+ * Rewires the copied condition chain. Removes backedges
* as this condition chain is prior to the loop.
* Copy of loop_head must have phi list and old (unfixed) backedge info of the loop head.
* (loop_head is already fixed, we cannot rely on it.)
ir_node **ins;
ir_node **phis;
ir_node *phi, *next;
- ir_node *head_cp = get_inversion_copy(loop_head);
- int arity = get_irn_arity(head_cp);
- int backedges = get_backedge_n(head_cp, 0);
- int new_arity = arity - backedges;
+ ir_node *head_cp = get_inversion_copy(loop_head);
+ ir_graph *irg = get_irn_irg(head_cp);
+ int arity = get_irn_arity(head_cp);
+ int backedges = get_backedge_n(head_cp, 0);
+ int new_arity = arity - backedges;
int pos;
int i;
ins[pos++] = get_irn_n(head_cp, i);
}
- new_head = new_Block(new_arity, ins);
+ new_head = new_r_Block(irg, new_arity, ins);
phis = NEW_ARR_F(ir_node *, 0);
DEL_ARR_F(phis);
}
-/**/
-static ir_node *fix_inner_cc_definitions(ir_node *phi, ir_node *pred)
-{
- int i;
- ir_node *head_phi;
- ir_node **head_phi_ins;
- ir_node *new_loop_head = loop_info.new_loop_head;
- int new_loop_head_arity = get_irn_arity(new_loop_head);
- DB((dbg, LEVEL_5, "NEW HEAD %N arity %d\n", new_loop_head, new_loop_head_arity));
-
- NEW_ARR_A(ir_node *, head_phi_ins, new_loop_head_arity);
-
- for(i = 0; i < new_loop_head_arity; ++i) {
- /* Rely on correct backedge info for the new loop head
- * is set by extend_ins_by_copy. */
- if(is_nodes_block_marked(get_irn_n(new_loop_head, i))) {
- head_phi_ins[i] = pred;
- } else {
- head_phi_ins[i] = get_inversion_copy(pred);
- }
- DB((dbg, LEVEL_5, "NEW HEAD %N in %N %N\n", new_loop_head, head_phi_ins[i], current_ir_graph));
- }
-
- head_phi= new_r_Phi(new_loop_head,
- new_loop_head_arity,
- head_phi_ins,
- get_irn_mode(phi));
-
- add_Block_phi(new_loop_head, head_phi);
-
- DB((dbg, LEVEL_5, "fix inner cc definitions: new head %N has new phi %N from cc phi %N @%N\n",
- new_loop_head, head_phi, phi, pred));
-
- return head_phi;
-}
-
-/* Puts the original condition chain at the end of the loop, subsequently to the body.
+/* Puts the original condition chain at the end of the loop,
+ * subsequently to the body.
* Relies on block phi list and correct backedges.
*/
static void fix_head_inversion(void)
ir_node **ins;
ir_node *phi, *next;
ir_node **phis;
- int arity = get_irn_arity(loop_head);
- int backedges = get_backedge_n(loop_head, 0);
- int new_arity = backedges;
+ ir_graph *irg = get_irn_irg(loop_head);
+ int arity = get_irn_arity(loop_head);
+ int backedges = get_backedge_n(loop_head, 0);
+ int new_arity = backedges;
int pos;
int i;
ins[pos++] = get_irn_n(loop_head, i);
}
- new_head = new_Block(new_arity, ins);
+ new_head = new_r_Block(irg, new_arity, ins);
phis = NEW_ARR_F(ir_node *, 0);
for_each_phi(loop_head, phi) {
ir_node *new_phi;
+ DB((dbg, LEVEL_5, "Fixing phi %N of loop head\n", phi));
NEW_ARR_A(ir_node *, ins, new_arity);
pos = 0;
- for(i = 0; i < arity; ++i) {
+ for (i = 0; i < arity; ++i) {
ir_node *pred = get_irn_n(phi, i);
if (is_own_backedge(loop_head, i)) {
- DB((dbg, LEVEL_5, " !!! PHI not useful %N\n", phi));
-
- /* If definition is in the condition chain,
- * we need to create a phi in the new loop head */
- if (is_nodes_block_marked(pred))
- ins[pos++] = fix_inner_cc_definitions(phi, pred);
- else
+ /* If assignment is in the condition chain,
+ * we need to create a phi in the new loop head.
+ * This can only happen for df, not cf. See find_condition_chains. */
+ /*if (is_nodes_block_marked(pred)) {
ins[pos++] = pred;
+ } else {*/
+ ins[pos++] = pred;
+
}
}
+
new_phi = new_rd_Phi(get_irn_dbg_info(phi),
new_head, new_arity, ins,
get_irn_mode(phi));
ARR_APP1(ir_node *, phis, new_phi);
- DB((dbg, LEVEL_5, "fix inverted head should exch %N by %N\n", phi, new_phi));
+ DB((dbg, LEVEL_5, "fix inverted head should exch %N by %N (pos %d)\n", phi, new_phi, pos ));
}
pos = 0;
}
/* Does the loop inversion. */
-static void inversion_walk(out_edge *head_entries)
+static void inversion_walk(entry_edge *head_entries)
{
- int i;
+ size_t i;
/*
* The order of rewiring bottom-up is crucial.
inc_irg_visited(current_ir_graph);
for (i = 0; i < ARR_LEN(head_entries); ++i) {
- out_edge entry = head_entries[i];
+ entry_edge entry = head_entries[i];
ir_node *pred = get_irn_n(entry.node, entry.pos);
DB((dbg, LEVEL_5, "\nInit walk block %N\n", pred));
ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED);
/* 2. Extends the head control flow successors ins
- * by the definitions of the copied head node. */
+ * with the definitions of the copied head node. */
for (i = 0; i < ARR_LEN(head_entries); ++i) {
- out_edge head_out = head_entries[i];
+ entry_edge head_out = head_entries[i];
if (is_Block(head_out.node))
extend_ins_by_copy(head_out.node, head_out.pos);
/* 3. construct_ssa for users of definitions in the condition chain,
* as there is now a second definition. */
for (i = 0; i < ARR_LEN(head_entries); ++i) {
- out_edge head_out = head_entries[i];
+ entry_edge head_out = head_entries[i];
+
/* Ignore keepalives */
if (is_End(head_out.node))
continue;
- ir_node *is_in_cc = get_nodes_block(get_irn_n(head_out.node, head_out.pos));
- /* Construct ssa for definitions in the condition chain. */
- /* TODO Why do we need the check for is_in_cc? All definitions should be there... */
- if (!is_Block(head_out.node) && is_nodes_block_marked(is_in_cc)) {
+ /* Construct ssa for assignments in the condition chain. */
+ if (!is_Block(head_out.node)) {
ir_node *pred, *cppred, *block, *cpblock;
- pred = get_irn_n(head_out.node, head_out.pos);
+ pred = head_out.pred;
cppred = get_inversion_copy(pred);
block = get_nodes_block(pred);
cpblock = get_nodes_block(cppred);
}
}
- /* 4. Remove the ins which are no backedges from the original condition chain,
- * as the cc is now subsequently to the body. */
+ /*
+ * If there is an assignment in the condition chain
+ * with a user also in the condition chain,
+ * the dominance frontier is in the new loop head.
+ * The dataflow loop is completely in the condition chain.
+ * Goal:
+ * To be wired: >|
+ *
+ * | ,--. |
+ * Phi_cp | | copied condition chain
+ * >| | | |
+ * >| ?__/ |
+ * >| ,-.
+ * Phi* | | new loop head with newly created phi.
+ * | |
+ * Phi | | original, inverted condition chain
+ * | | |
+ * ?__/ |
+ *
+ */
+ for (i = 0; i < ARR_LEN(head_df_loop); ++i) {
+ entry_edge head_out = head_df_loop[i];
+
+ /* Construct ssa for assignments in the condition chain. */
+ ir_node *pred, *cppred, *block, *cpblock;
+
+ pred = head_out.pred;
+ cppred = get_inversion_copy(pred);
+ assert(cppred && pred);
+ block = get_nodes_block(pred);
+ cpblock = get_nodes_block(cppred);
+ construct_ssa(block, pred, cpblock, cppred);
+ }
+
+ /* 4. Remove the ins which are no backedges from the original condition chain
+ * as the cc is now subsequent to the body. */
fix_head_inversion();
/* 5. Remove the backedges of the copied condition chain,
- * because it is going to be the new 'head' in advance to the loop */
+ * because it is going to be the new 'head' in advance to the loop. */
fix_copy_inversion();
+
}
-/* Analyse loop, if inversion is possible or reasonable. Then do the inversion. */
+/* Performs loop inversion of cur_loop if possible and reasonable. */
static void loop_inversion(void)
{
+ int loop_depth;
+ unsigned max_loop_nodes = opt_params.max_loop_size;
+ unsigned max_loop_nodes_adapted;
+ int depth_adaption = opt_params.depth_adaption;
+
unsigned do_inversion = 1;
+ unsigned has_cc = 0;
+
+ /* Depth of 0 is the procedure and 1 a topmost loop. */
+ loop_depth = get_loop_depth(cur_loop) - 1;
+
+ /* Calculating in per mil. */
+ max_loop_nodes_adapted = get_max_nodes_adapted(loop_depth);
+
+ DB((dbg, LEVEL_1, "max_nodes: %d\nmax_nodes_adapted %d at depth of %d (adaption %d)\n",
+ max_loop_nodes, max_loop_nodes_adapted, loop_depth, depth_adaption));
+
+ if (! (loop_info.nodes > 0))
+ return;
+
+#if LOOP_IGNORE_NODE_LIMITS
+ DB((dbg, LEVEL_1, "WARNING: Loop node limitations ignored."));
+#else
+ if (loop_info.nodes > max_loop_nodes) {
+ /* Only for stats */
+ DB((dbg, LEVEL_1, "Nodes %d > allowed nodes %d\n",
+ loop_info.nodes, loop_depth, max_loop_nodes));
+ count_stats(stats.too_large);
+ /* no RETURN */
+ /* Adaption might change it */
+ }
+
+ /* Limit processing to loops smaller than given parameter. */
+ if (loop_info.nodes > max_loop_nodes_adapted) {
+ DB((dbg, LEVEL_1, "Nodes %d > allowed nodes (depth %d adapted) %d\n",
+ loop_info.nodes, loop_depth, max_loop_nodes_adapted));
+ count_stats(stats.too_large_adapted);
+ return;
+ }
+
+ if (loop_info.calls > opt_params.allowed_calls) {
+ DB((dbg, LEVEL_1, "Calls %d > allowed calls %d\n",
+ loop_info.calls, opt_params.allowed_calls));
+ count_stats(stats.calls_limit);
+ return;
+ }
+#endif
- inversion_head_node_limit = INT_MAX;
+ /*inversion_head_node_limit = INT_MAX;*/
ir_reserve_resources(current_ir_graph, IR_RESOURCE_BLOCK_MARK);
/* Reset block marks.
* We use block marks to flag blocks of the original condition chain. */
irg_walk_graph(current_ir_graph, reset_block_mark, NULL, NULL);
- loop_info.blocks = get_loop_n_blocks(cur_loop);
- cond_chain_entries = NEW_ARR_F(out_edge, 0);
-
- head_inversion_node_count = 0;
- head_inversion_block_count = 0;
+ /*loop_info.blocks = get_loop_n_blocks(cur_loop);*/
+ cond_chain_entries = NEW_ARR_F(entry_edge, 0);
+ head_df_loop = NEW_ARR_F(entry_edge, 0);
- set_Block_mark(loop_head, 1);
- mark_irn_visited(loop_head);
+ /*head_inversion_node_count = 0;*/
+ inversion_blocks_in_cc = 0;
/* Use phase to keep copy of nodes from the condition chain. */
phase = new_phase(current_ir_graph, phase_irn_init_default);
+ /* Search for condition chains and temporarily save the blocks in an array. */
+ cc_blocks = NEW_ARR_F(ir_node *, 0);
inc_irg_visited(current_ir_graph);
+ has_cc = find_condition_chain(loop_head);
- /* Search for condition chains. */
- find_condition_chains(loop_head);
+ unmark_not_allowed_cc_blocks();
+ DEL_ARR_F(cc_blocks);
- DB((dbg, LEVEL_3, "Loop contains %d blocks.\n", loop_info.blocks));
+#if LOOP_IGNORE_NODE_LIMITS
+ (void) unmark_cc_blocks;
+#else
+ /* Condition chain too large.
+ * Loop should better be small enough to fit into the cache. */
+ /* TODO Of course, we should take a small enough cc in the first place,
+ * which is not that simple. (bin packing) */
+ if (loop_info.cc_size > opt_params.max_cc_size) {
+ count_stats(stats.cc_limit_reached);
- if (loop_info.blocks < 2) {
do_inversion = 0;
- DB((dbg, LEVEL_3,
- "Loop contains %d (less than 2) blocks => No Inversion done.\n",
- loop_info.blocks));
+
+ /* Unmark cc blocks except the head.
+ * Invert head only for possible unrolling. */
+ unmark_cc_blocks();
+
}
+#endif
/* We also catch endless loops here,
* because they do not have a condition chain. */
- if (head_inversion_block_count < 1) {
+ if (inversion_blocks_in_cc < 1) {
do_inversion = 0;
DB((dbg, LEVEL_3,
"Loop contains %d (less than 1) invertible blocks => No Inversion done.\n",
- head_inversion_block_count));
+ inversion_blocks_in_cc));
}
if (do_inversion) {
- cur_head_outs = NEW_ARR_F(out_edge, 0);
+ cur_head_outs = NEW_ARR_F(entry_edge, 0);
/* Get all edges pointing into the condition chain. */
irg_walk_graph(current_ir_graph, get_head_outs, NULL, NULL);
inversion_walk(cur_head_outs);
DEL_ARR_F(cur_head_outs);
+
/* Duplicated blocks changed doms */
set_irg_doms_inconsistent(current_ir_graph);
/* Loop content changed */
set_irg_loopinfo_inconsistent(current_ir_graph);
- /* TODO are they? */
+ /* TODO are they? Depends on set_irn_in and set_irn_n exchange and new_node. */
set_irg_outs_inconsistent(current_ir_graph);
+
+ count_stats(stats.inverted);
}
/* free */
phase_free(phase);
DEL_ARR_F(cond_chain_entries);
+ DEL_ARR_F(head_df_loop);
+
ir_free_resources(current_ir_graph, IR_RESOURCE_BLOCK_MARK);
}
-/**
- * Rewire floating copies of the current loop.
- */
-static void place_copies(int copies)
+/* Fix the original loop_heads ins for invariant unrolling case. */
+static void unrolling_fix_loop_head_inv(void)
{
- ir_node *loophead = loop_head;
- int headarity = get_irn_arity(loophead);
+ ir_node *ins[2];
ir_node *phi;
- int i, pos, c;
-
- pos = 0;
- /* Append the copies to the existing loop. */
- for (i = 0; i < headarity; ++i) {
- /* Build unrolled loop top down */
- if (is_backedge(loophead, i) && !is_alien_edge(loophead, i)) {
- for (c = 0; c < copies; ++c) {
- ir_node *upper_head;
- ir_node *lower_head = get_copy(loophead, c);
- ir_node *upper_pred;
-
- if (c == 0) {
- upper_head = loophead;
- upper_pred = get_irn_n(loophead, i);
- } else {
- upper_head = get_copy(loophead, c - 1);
- upper_pred = get_copy_safe(get_irn_n(loophead, i), c - 1);
- }
- set_irn_n(lower_head, pos, upper_pred);
- for_each_phi(loophead, phi) {
- ir_node *lower_phi, *upper_phi, *upper_pred_phi;
- lower_phi = get_copy(phi, c);
- if (c == 0) {
- upper_phi = phi;
- upper_pred_phi = get_irn_n(phi, i);
- } else {
- upper_phi = get_copy(phi, c - 1);
- upper_pred_phi = get_copy_safe(get_irn_n(phi, i), c - 1);
- }
-
- DB((dbg, LEVEL_5, "Rewire %N @%d to %N\n",
- lower_phi, pos, upper_pred_phi));
+ ir_node *proj = new_Proj(loop_info.duff_cond, mode_X, 0);
+ ir_node *head_pred = get_irn_n(loop_head, loop_info.be_src_pos);
+ ir_node *loop_condition = get_unroll_copy(head_pred, unroll_nr - 1);
- /* Relying on phi nodes with 1 in to be present. */
- assert(is_Phi(lower_phi));
+ /* Original loop_heads ins are:
+ * duff block and the own backedge */
-/* Do not fix phis here. Chained phis will cause a defective copy array. */
-#if 0
- if (get_irn_arity(lower_phi) == 1) {
- ir_node *single_in[1];
- ir_node *cp;
- single_in[0] = upper_pred_phi;
+ ins[0] = loop_condition;
+ ins[1] = proj;
+ set_irn_in(loop_head, 2, ins);
+ DB((dbg, LEVEL_4, "Rewire ins of block loophead %N to pred %N and duffs entry %N \n" , loop_head, ins[0], ins[1]));
- cp = new_rd_Phi(get_irn_dbg_info(lower_phi),
- get_nodes_block(lower_phi), 1, single_in,
- get_irn_mode(lower_phi));
+ for_each_phi(loop_head, phi) {
+ ir_node *pred = get_irn_n(phi, loop_info.be_src_pos);
+ /* TODO we think it is a phi, but for Mergesort it is not the case.*/
- set_copy(phi, c, cp);
- exchange(lower_phi, cp);
- } else
-#endif
- set_irn_n(lower_phi, pos, upper_pred_phi);
+ ir_node *last_pred = get_unroll_copy(pred, unroll_nr - 1);
- }
- }
- ++pos;
- /* Fix the topmost loop heads backedges. */
- set_irn_n(loophead, i, get_copy(get_irn_n(loophead, i), copies - 1));
- for_each_phi(loophead, phi) {
- ir_node *last_cp = get_copy_safe(get_irn_n(phi, i), copies - 1);
- set_irn_n(phi, i, last_cp);
- }
- }
+ ins[0] = last_pred;
+ ins[1] = (ir_node*)get_irn_link(phi);
+ set_irn_in(phi, 2, ins);
+ DB((dbg, LEVEL_4, "Rewire ins of loophead phi %N to pred %N and duffs entry %N \n" , phi, ins[0], ins[1]));
}
}
-/* Copies the cur_loop */
-static void copy_loop(out_edge *cur_loop_outs, int copies)
+/* Removes previously created phis with only 1 in. */
+static void correct_phis(ir_node *node, void *env)
{
- int i, c;
- unroll_arity = get_backedge_n(loop_head, 0);
-
- ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED);
+ (void)env;
- /* copy loop */
- for (c = 0; c < copies; ++c) {
+ if (is_Phi(node) && get_irn_arity(node) == 1) {
+ ir_node *exch;
+ ir_node *in[1];
- inc_irg_visited(current_ir_graph);
+ in[0] = get_irn_n(node, 0);
- DB((dbg, LEVEL_5, " ### Copy_loop copy n: %d ###\n", c));
- for (i = 0; i < ARR_LEN(cur_loop_outs); ++i) {
- out_edge entry = cur_loop_outs[i];
- ir_node *pred = get_irn_n(entry.node, entry.pos);
+ exch = new_rd_Phi(get_irn_dbg_info(node),
+ get_nodes_block(node), 1, in,
+ get_irn_mode(node));
- copy_walk_n(pred, is_in_loop, c, c ? 0 : copies);
- }
+ exchange(node, exch);
}
-
- ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED);
}
-/**/
-static void create_duffs_device(int unroll_number)
+/* Unrolling: Rewire floating copies. */
+static void place_copies(int copies)
{
- (void)unroll_number;
-}
+ ir_node *loophead = loop_head;
+ size_t i;
+ int c;
+ int be_src_pos = loop_info.be_src_pos;
-#if 1
+ /* Serialize loops by fixing their head ins.
+ * Processed are the copies.
+ * The original loop is done after that, to keep backedge infos. */
+ for (c = 0; c < copies; ++c) {
+ ir_node *upper = get_unroll_copy(loophead, c);
+ ir_node *lower = get_unroll_copy(loophead, c + 1);
+ ir_node *phi;
+ ir_node *topmost_be_block = get_nodes_block(get_irn_n(loophead, be_src_pos));
-static unsigned is_loop_invariant_val(ir_node *node)
+ /* Important: get the preds first and then their copy. */
+ ir_node *upper_be_block = get_unroll_copy(topmost_be_block, c);
+ ir_node *new_jmp = new_r_Jmp(upper_be_block);
+ DB((dbg, LEVEL_5, " place_copies upper %N lower %N\n", upper, lower));
+
+ DB((dbg, LEVEL_5, "topmost be block %N \n", topmost_be_block));
+
+ if (loop_info.unroll_kind == constant) {
+ ir_node *ins[1];
+ ins[0] = new_jmp;
+ set_irn_in(lower, 1, ins);
+
+ for_each_phi(loophead, phi) {
+ ir_node *topmost_def = get_irn_n(phi, be_src_pos);
+ ir_node *upper_def = get_unroll_copy(topmost_def, c);
+ ir_node *lower_phi = get_unroll_copy(phi, c + 1);
+
+ /* It is possible, that the value used
+ * in the OWN backedge path is NOT defined in this loop. */
+ if (is_in_loop(topmost_def))
+ ins[0] = upper_def;
+ else
+ ins[0] = topmost_def;
+
+ set_irn_in(lower_phi, 1, ins);
+ /* Need to replace phis with 1 in later. */
+ }
+ } else {
+ /* Invariant case */
+ /* Every node has 2 ins. One from the duff blocks
+ * and one from the previously unrolled loop. */
+ ir_node *ins[2];
+ /* Calculate corresponding projection of mod result for this copy c */
+ ir_node *proj = new_Proj(loop_info.duff_cond, mode_X, unroll_nr - c - 1);
+ DB((dbg, LEVEL_4, "New duff proj %N\n" , proj));
+
+ ins[0] = new_jmp;
+ ins[1] = proj;
+ set_irn_in(lower, 2, ins);
+ DB((dbg, LEVEL_4, "Rewire ins of Block %N to pred %N and duffs entry %N \n" , lower, ins[0], ins[1]));
+
+ for_each_phi(loophead, phi) {
+ ir_node *topmost_phi_pred = get_irn_n(phi, be_src_pos);
+ ir_node *upper_phi_pred;
+ ir_node *lower_phi;
+ ir_node *duff_phi;
+
+ lower_phi = get_unroll_copy(phi, c + 1);
+ duff_phi = (ir_node*)get_irn_link(phi);
+ DB((dbg, LEVEL_4, "DD Link of %N is %N\n" , phi, duff_phi));
+
+ /* */
+ if (is_in_loop(topmost_phi_pred)) {
+ upper_phi_pred = get_unroll_copy(topmost_phi_pred, c);
+ } else {
+ upper_phi_pred = topmost_phi_pred;
+ }
+
+ ins[0] = upper_phi_pred;
+ ins[1] = duff_phi;
+ set_irn_in(lower_phi, 2, ins);
+ DB((dbg, LEVEL_4, "Rewire ins of %N to pred %N and duffs entry %N \n" , lower_phi, ins[0], ins[1]));
+ }
+ }
+ }
+
+ /* Reconnect last copy. */
+ for (i = 0; i < ARR_LEN(loop_entries); ++i) {
+ entry_edge edge = loop_entries[i];
+ /* Last copy is at the bottom */
+ ir_node *new_pred = get_unroll_copy(edge.pred, copies);
+ set_irn_n(edge.node, edge.pos, new_pred);
+ }
+
+ /* Fix original loops head.
+ * Done in the end, as ins and be info were needed before. */
+ if (loop_info.unroll_kind == constant) {
+ ir_node *phi;
+ ir_node *head_pred = get_irn_n(loop_head, be_src_pos);
+ ir_node *loop_condition = get_unroll_copy(head_pred, unroll_nr - 1);
+
+ set_irn_n(loop_head, loop_info.be_src_pos, loop_condition);
+
+ for_each_phi(loop_head, phi) {
+ ir_node *pred = get_irn_n(phi, be_src_pos);
+ ir_node *last_pred;
+
+ /* It is possible, that the value used
+ * in the OWN backedge path is NOT assigned in this loop. */
+ if (is_in_loop(pred))
+ last_pred = get_unroll_copy(pred, copies);
+ else
+ last_pred = pred;
+ set_irn_n(phi, be_src_pos, last_pred);
+ }
+
+ } else {
+ unrolling_fix_loop_head_inv();
+ }
+}
+
+/* Copies the cur_loop several times. */
+static void copy_loop(entry_edge *cur_loop_outs, int copies)
+{
+ int c;
+
+ ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED);
+
+ for (c = 0; c < copies; ++c) {
+ size_t i;
+
+ inc_irg_visited(current_ir_graph);
+
+ DB((dbg, LEVEL_5, " ### Copy_loop copy nr: %d ###\n", c));
+ for (i = 0; i < ARR_LEN(cur_loop_outs); ++i) {
+ entry_edge entry = cur_loop_outs[i];
+ ir_node *pred = get_irn_n(entry.node, entry.pos);
+
+ copy_walk_n(pred, is_in_loop, c + 1);
+ }
+ }
+
+ ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED);
+}
+
+
+/* Creates a new phi from the given phi node omitting own bes,
+ * using be_block as supplier of backedge informations. */
+static ir_node *clone_phis_sans_bes(ir_node *phi, ir_node *be_block, ir_node *dest_block)
+{
+ ir_node **ins;
+ int arity = get_irn_arity(phi);
+ int i, c = 0;
+ ir_node *newphi;
+
+ assert(get_irn_arity(phi) == get_irn_arity(be_block));
+ assert(is_Phi(phi));
+
+ ins = NEW_ARR_F(ir_node *, arity);
+ for (i = 0; i < arity; ++i) {
+ if (! is_own_backedge(be_block, i)) {
+ ins[c] = get_irn_n(phi, i);
+ ++c;
+ }
+ }
+
+ newphi = new_r_Phi(dest_block, c, ins, get_irn_mode(phi));
+
+ set_irn_link(phi, newphi);
+ DB((dbg, LEVEL_4, "Linking for duffs device %N to %N\n", phi, newphi));
+
+ return newphi;
+}
+
+/* Creates a new block from the given block node omitting own bes,
+ * using be_block as supplier of backedge informations. */
+static ir_node *clone_block_sans_bes(ir_node *node, ir_node *be_block)
+{
+ ir_node **ins;
+ int arity = get_irn_arity(node);
+ int i, c = 0;
+
+ assert(get_irn_arity(node) == get_irn_arity(be_block));
+ assert(is_Block(node));
+
+ NEW_ARR_A(ir_node *, ins, arity);
+ for (i = 0; i < arity; ++i) {
+ if (! is_own_backedge(be_block, i)) {
+ ins[c] = get_irn_n(node, i);
+ ++c;
+ }
+ }
+
+ return new_Block(c, ins);
+}
+
+/* Creates a structure to calculate absolute value of node op.
+ * Returns mux node with absolute value. */
+static ir_node *new_Abs(ir_node *op, ir_mode *mode)
+{
+ ir_graph *irg = get_irn_irg(op);
+ ir_node *block = get_nodes_block(op);
+ ir_node *zero = new_r_Const(irg, get_mode_null(mode));
+ ir_node *cmp = new_r_Cmp(block, op, zero, ir_relation_less);
+ ir_node *minus_op = new_r_Minus(block, op, mode);
+ ir_node *mux = new_r_Mux(block, cmp, op, minus_op, mode);
+
+ return mux;
+}
+
+
+/* Creates blocks for duffs device, using previously obtained
+ * informations about the iv.
+ * TODO split */
+static void create_duffs_block(void)
+{
+ ir_mode *mode;
+
+ ir_node *block1, *count_block, *duff_block;
+ ir_node *ems, *ems_mod, *ems_div, *ems_mod_proj, *cmp_null,
+ *ems_mode_cond, *x_true, *x_false, *const_null;
+ ir_node *true_val, *false_val;
+ ir_node *ins[2];
+
+ ir_node *duff_mod, *proj, *cond;
+
+ ir_node *count, *correction, *unroll_c;
+ ir_node *cmp_bad_count, *good_count, *bad_count, *count_phi, *bad_count_neg;
+ ir_node *phi;
+
+ mode = get_irn_mode(loop_info.end_val);
+ const_null = new_Const(get_mode_null(mode));
+
+ /* TODO naming
+ * 1. Calculate first approach to count.
+ * Condition: (end - start) % step == 0 */
+ block1 = clone_block_sans_bes(loop_head, loop_head);
+ DB((dbg, LEVEL_4, "Duff block 1 %N\n", block1));
+
+ /* Create loop entry phis in first duff block
+ * as it becomes the loops preheader */
+ for_each_phi(loop_head, phi) {
+ /* Returns phis pred if phi would have arity 1*/
+ ir_node *new_phi = clone_phis_sans_bes(phi, loop_head, block1);
+
+ DB((dbg, LEVEL_4, "HEAD %N phi %N\n", loop_head, phi));
+ DB((dbg, LEVEL_4, "BLOCK1 %N phi %N\n", block1, new_phi));
+ }
+
+ ems = new_r_Sub(block1, loop_info.end_val, loop_info.start_val,
+ get_irn_mode(loop_info.end_val));
+ DB((dbg, LEVEL_4, "BLOCK1 sub %N\n", ems));
+
+
+ ems = new_Sub(loop_info.end_val, loop_info.start_val,
+ get_irn_mode(loop_info.end_val));
+
+ DB((dbg, LEVEL_4, "mod ins %N %N\n", ems, loop_info.step));
+ ems_mod = new_r_Mod(block1,
+ new_NoMem(),
+ ems,
+ loop_info.step,
+ mode,
+ op_pin_state_pinned);
+ ems_div = new_r_Div(block1,
+ new_NoMem(),
+ ems,
+ loop_info.step,
+ mode,
+ op_pin_state_pinned);
+
+ DB((dbg, LEVEL_4, "New module node %N\n", ems_mod));
+
+ ems_mod_proj = new_r_Proj(ems_mod, mode_Iu, pn_Mod_res);
+ cmp_null = new_r_Cmp(block1, ems_mod_proj, const_null, ir_relation_less);
+ ems_mode_cond = new_r_Cond(block1, cmp_null);
+
+ /* ems % step == 0 */
+ x_true = new_r_Proj(ems_mode_cond, mode_X, pn_Cond_true);
+ /* ems % step != 0 */
+ x_false = new_r_Proj(ems_mode_cond, mode_X, pn_Cond_false);
+
+ /* 2. Second block.
+ * Assures, duffs device receives a valid count.
+ * Condition:
+ * decreasing: count < 0
+ * increasing: count > 0
+ */
+ ins[0] = x_true;
+ ins[1] = x_false;
+
+ count_block = new_Block(2, ins);
+ DB((dbg, LEVEL_4, "Duff block 2 %N\n", count_block));
+
+
+ /* Increase loop-taken-count depending on the loop condition
+ * uses the latest iv to compare to. */
+ if (loop_info.latest_value == 1) {
+ /* ems % step == 0 : +0 */
+ true_val = new_Const(get_mode_null(mode));
+ /* ems % step != 0 : +1 */
+ false_val = new_Const(get_mode_one(mode));
+ } else {
+ ir_tarval *tv_two = new_tarval_from_long(2, mode);
+ /* ems % step == 0 : +1 */
+ true_val = new_Const(get_mode_one(mode));
+ /* ems % step != 0 : +2 */
+ false_val = new_Const(tv_two);
+ }
+
+ ins[0] = true_val;
+ ins[1] = false_val;
+
+ correction = new_r_Phi(count_block, 2, ins, mode);
+
+ count = new_r_Proj(ems_div, mode, pn_Div_res);
+
+ /* (end - start) / step + correction */
+ count = new_Add(count, correction, mode);
+
+ /* We preconditioned the loop to be tail-controlled.
+ * So, if count is something 'wrong' like 0,
+ * negative/positive (depending on step direction),
+ * we may take the loop once (tail-contr.) and leave it
+ * to the existing condition, to break; */
+
+ /* Depending on step direction, we have to check for > or < 0 */
+ if (loop_info.decreasing == 1) {
+ cmp_bad_count = new_r_Cmp(count_block, count, const_null,
+ ir_relation_less);
+ } else {
+ cmp_bad_count = new_r_Cmp(count_block, count, const_null,
+ ir_relation_greater);
+ }
+
+ bad_count_neg = new_r_Cond(count_block, cmp_bad_count);
+ good_count = new_Proj(bad_count_neg, mode_X, pn_Cond_true);
+ bad_count = new_Proj(ems_mode_cond, mode_X, pn_Cond_false);
+
+ /* 3. Duff Block
+ * Contains module to decide which loop to start from. */
+
+ ins[0] = good_count;
+ ins[1] = bad_count;
+ duff_block = new_Block(2, ins);
+ DB((dbg, LEVEL_4, "Duff block 3 %N\n", duff_block));
+
+ /* Get absolute value */
+ ins[0] = new_Abs(count, mode);
+ /* Manually feed the aforementioned count = 1 (bad case)*/
+ ins[1] = new_Const(get_mode_one(mode));
+ count_phi = new_r_Phi(duff_block, 2, ins, mode);
+
+ unroll_c = new_Const(new_tarval_from_long((long)unroll_nr, mode));
+
+ /* count % unroll_nr */
+ duff_mod = new_r_Mod(duff_block,
+ new_NoMem(),
+ count_phi,
+ unroll_c,
+ mode,
+ op_pin_state_pinned);
+
+
+ proj = new_Proj(duff_mod, mode, pn_Mod_res);
+ /* condition does NOT create itself in the block of the proj! */
+ cond = new_r_Cond(duff_block, proj);
+
+ loop_info.duff_cond = cond;
+}
+
+/* Returns 1 if given node is not in loop,
+ * or if it is a phi of the loop head with only loop invariant defs.
+ */
+static unsigned is_loop_invariant_def(ir_node *node)
{
int i;
- if (! is_in_loop(node))
+ if (! is_in_loop(node)) {
+ DB((dbg, LEVEL_4, "Not in loop %N\n", node));
+ /* || is_Const(node) || is_SymConst(node)) {*/
return 1;
+ }
- /* TODO all cases? and how to use the dom tree for that. */
-
+ /* If this is a phi of the loophead shared by more than 1 loop,
+ * we need to check if all defs are not in the loop. */
if (is_Phi(node)) {
+ ir_node *block;
+ block = get_nodes_block(node);
+
+ /* To prevent unexpected situations. */
+ if (block != loop_head) {
+ return 0;
+ }
+
for (i = 0; i < get_irn_arity(node); ++i) {
- if (is_own_backedge(get_nodes_block(node), i) && get_irn_n(node, i) != node)
+ /* Check if all bes are just loopbacks. */
+ if (is_own_backedge(block, i) && get_irn_n(node, i) != node)
return 0;
}
+ DB((dbg, LEVEL_4, "invar %N\n", node));
+ return 1;
}
- return 1;
+ DB((dbg, LEVEL_4, "Not invar %N\n", node));
+
+ return 0;
}
-/* TODO name */
-static ir_node *is_loop_iteration(ir_node *node)
+/* Returns 1 if one pred of node is invariant and the other is not.
+ * invar_pred and other are set analogously. */
+static unsigned get_invariant_pred(ir_node *node, ir_node **invar_pred, ir_node **other)
+{
+ ir_node *pred0 = get_irn_n(node, 0);
+ ir_node *pred1 = get_irn_n(node, 1);
+
+ *invar_pred = NULL;
+ *other = NULL;
+
+ if (is_loop_invariant_def(pred0)) {
+ DB((dbg, LEVEL_4, "pred0 invar %N\n", pred0));
+ *invar_pred = pred0;
+ *other = pred1;
+ }
+
+ if (is_loop_invariant_def(pred1)) {
+ DB((dbg, LEVEL_4, "pred1 invar %N\n", pred1));
+
+ if (*invar_pred != NULL) {
+ /* RETURN. We do not want both preds to be invariant. */
+ return 0;
+ }
+
+ *other = pred0;
+ *invar_pred = pred1;
+ return 1;
+ } else {
+ DB((dbg, LEVEL_4, "pred1 not invar %N\n", pred1));
+
+ if (*invar_pred != NULL)
+ return 1;
+ else
+ return 0;
+ }
+}
+
+/* Starts from a phi that may belong to an iv.
+ * If an add forms a loop with iteration_phi,
+ * and add uses a constant, 1 is returned
+ * and 'start' as well as 'add' are sane. */
+static unsigned get_start_and_add(ir_node *iteration_phi, unrolling_kind_flag role)
{
int i;
- ir_node *found_add = NULL;
+ ir_node *found_add = loop_info.add;
+ int arity = get_irn_arity(iteration_phi);
- if (!is_in_loop(node))
- return NULL;
+ DB((dbg, LEVEL_4, "Find start and add from %N\n", iteration_phi));
- if (is_Add(node))
- return node;
+ for (i = 0; i < arity; ++i) {
- /*TODO all cases? and how do i use the dom tree for that.*/
+ /* Find start_val which needs to be pred of the iteration_phi.
+ * If start_val already known, sanity check. */
+ if (!is_backedge(get_nodes_block(loop_info.iteration_phi), i)) {
+ ir_node *found_start_val = get_irn_n(loop_info.iteration_phi, i);
- if (is_Phi(node)) {
- for (i = 0; i < get_irn_arity(node); ++i) {
- ir_node *new_found;
- if (! is_own_backedge(get_nodes_block(node), i))
- continue;
- new_found = get_irn_n(node,i);
+ DB((dbg, LEVEL_4, "found_start_val %N\n", found_start_val));
- if (found_add && found_add != new_found)
- return NULL;
+ /* We already found a start_val it has to be always the same. */
+ if (loop_info.start_val && found_start_val != loop_info.start_val)
+ return 0;
- found_add = new_found;
+ if ((role == constant) && !(is_SymConst(found_start_val) || is_Const(found_start_val)))
+ return 0;
+ else if((role == constant) && !(is_loop_invariant_def(found_start_val)))
+ return 0;
+
+ loop_info.start_val = found_start_val;
+ }
+
+ /* The phi has to be in the loop head.
+ * Follow all own backedges. Every value supplied from these preds of the phi
+ * needs to origin from the same add. */
+ if (is_own_backedge(get_nodes_block(loop_info.iteration_phi), i)) {
+ ir_node *new_found = get_irn_n(loop_info.iteration_phi,i);
+
+ DB((dbg, LEVEL_4, "is add? %N\n", new_found));
+
+ if (! (is_Add(new_found) || is_Sub(new_found)) || (found_add && found_add != new_found))
+ return 0;
+ else
+ found_add = new_found;
}
}
- return found_add;
+
+ loop_info.add = found_add;
+
+ return 1;
}
-/* counting loop */
-static unsigned get_unroll_decision(out_edge *cur_loop_outs)
+
+/* Returns 1 if one pred of node is a const value and the other is not.
+ * const_pred and other are set analogously. */
+static unsigned get_const_pred(ir_node *node, ir_node **const_pred, ir_node **other)
{
- int i;
- ir_node *pred0, *pred1, *projx, *cond, *projres, *loop_condition;
- ir_node *iteration, *add, *iteration_phi, *end_val, *step, *add_in0, *add_in1;
+ ir_node *pred0 = get_irn_n(node, 0);
+ ir_node *pred1 = get_irn_n(node, 1);
- (void) cur_loop_outs;
- (void) i;
+ DB((dbg, LEVEL_4, "Checking for constant pred of %N\n", node));
+ *const_pred = NULL;
+ *other = NULL;
- /* There is more than 1 condition for the loop exit. We cannot cope this with duffs device. */
- if (loop_info.cf_outs != 1)
+ /*DB((dbg, LEVEL_4, "is %N const\n", pred0));*/
+ if (is_Const(pred0) || is_SymConst(pred0)) {
+ *const_pred = pred0;
+ *other = pred1;
+ }
+
+ /*DB((dbg, LEVEL_4, "is %N const\n", pred1));*/
+ if (is_Const(pred1) || is_SymConst(pred1)) {
+ if (*const_pred != NULL) {
+ /* RETURN. We do not want both preds to be constant. */
+ return 0;
+ }
+
+ *other = pred0;
+ *const_pred = pred1;
+ }
+
+ if (*const_pred == NULL)
return 0;
+ else
+ return 1;
+}
+
+/* Returns 1 if loop exits within 2 steps of the iv.
+ * Norm_proj means we do not exit the loop.*/
+static unsigned simulate_next(ir_tarval **count_tar,
+ ir_tarval *stepped, ir_tarval *step_tar, ir_tarval *end_tar,
+ ir_relation norm_proj)
+{
+ ir_tarval *next;
- /*TODO test for impact on performance */
- if (loop_info.calls > 0)
+ DB((dbg, LEVEL_4, "Loop taken if (stepped)%ld %s (end)%ld ",
+ get_tarval_long(stepped),
+ get_relation_string((norm_proj)),
+ get_tarval_long(end_tar)));
+ DB((dbg, LEVEL_4, "comparing latest value %d\n", loop_info.latest_value));
+
+ /* If current iv does not stay in the loop,
+ * this run satisfied the exit condition. */
+ if (! (tarval_cmp(stepped, end_tar) & norm_proj))
+ return 1;
+
+ DB((dbg, LEVEL_4, "Result: (stepped)%ld IS %s (end)%ld\n",
+ get_tarval_long(stepped),
+ get_relation_string(tarval_cmp(stepped, end_tar)),
+ get_tarval_long(end_tar)));
+
+ /* next step */
+ if (is_Add(loop_info.add))
+ next = tarval_add(stepped, step_tar);
+ else
+ /* sub */
+ next = tarval_sub(stepped, step_tar, get_irn_mode(loop_info.end_val));
+
+ DB((dbg, LEVEL_4, "Loop taken if %ld %s %ld ",
+ get_tarval_long(next),
+ get_relation_string(norm_proj),
+ get_tarval_long(end_tar)));
+ DB((dbg, LEVEL_4, "comparing latest value %d\n", loop_info.latest_value));
+
+ /* Increase steps. */
+ *count_tar = tarval_add(*count_tar, get_tarval_one(get_tarval_mode(*count_tar)));
+
+ /* Next has to fail the loop condition, or we will never exit. */
+ if (! (tarval_cmp(next, end_tar) & norm_proj))
+ return 1;
+ else
return 0;
+}
+/* Check if loop meets requirements for a 'simple loop':
+ * - Exactly one cf out
+ * - Allowed calls
+ * - Max nodes after unrolling
+ * - tail-controlled
+ * - exactly one be
+ * - cmp
+ * Returns Projection of cmp node or NULL; */
+static ir_node *is_simple_loop(void)
+{
+ int arity, i;
+ ir_node *loop_block, *exit_block, *projx, *cond, *cmp;
- projx = get_irn_n(loop_info.cf_out.node, loop_info.cf_out.pos);
+ /* Maximum of one condition, and no endless loops. */
+ if (loop_info.cf_outs != 1)
+ return NULL;
+
+ DB((dbg, LEVEL_4, "1 loop exit\n"));
+
+#if LOOP_IGNORE_NODE_LIMITS
+ /* Ignore loop size. Probably not wise in other than testcases. */
+ loop_info.max_unroll = 40;
+#else
+ /* Calculate maximum unroll_nr keeping node count below limit. */
+ loop_info.max_unroll = (int)((double)opt_params.max_unrolled_loop_size / (double)loop_info.nodes);
+ if (loop_info.max_unroll < 2) {
+ count_stats(stats.too_large);
+ return NULL;
+ }
+#endif
+
+
+ DB((dbg, LEVEL_4, "maximum unroll factor %u, to not exceed node limit \n",
+ opt_params.max_unrolled_loop_size));
+
+ arity = get_irn_arity(loop_head);
+ /* RETURN if we have more than 1 be. */
+ /* Get my backedges without alien bes. */
+ loop_block = NULL;
+ for (i = 0; i < arity; ++i) {
+ ir_node *pred = get_irn_n(loop_head, i);
+ if (is_own_backedge(loop_head, i)) {
+ if (loop_block)
+ /* Our simple loops may have only one backedge. */
+ return NULL;
+ else {
+ loop_block = get_nodes_block(pred);
+ loop_info.be_src_pos = i;
+ }
+ }
+ }
+
+ DB((dbg, LEVEL_4, "loop has 1 own backedge.\n"));
+
+ exit_block = get_nodes_block(loop_info.cf_out.pred);
+ /* The loop has to be tail-controlled.
+ * This can be changed/improved,
+ * but we would need a duff iv. */
+ if (exit_block != loop_block)
+ return NULL;
+
+ DB((dbg, LEVEL_4, "tail-controlled loop.\n"));
+
+ /* find value on which loop exit depends */
+ projx = loop_info.cf_out.pred;
cond = get_irn_n(projx, 0);
- projres = get_irn_n(cond, 0);
+ cmp = get_irn_n(cond, 0);
+
+ if (!is_Cmp(cmp))
+ return NULL;
+
+ DB((dbg, LEVEL_5, "projection is %s\n", get_relation_string(get_Proj_proj(projx))));
+
+ switch(get_Proj_proj(projx)) {
+ case pn_Cond_false:
+ loop_info.exit_cond = 0;
+ break;
+ case pn_Cond_true:
+ loop_info.exit_cond = 1;
+ break;
+ default:
+ panic("Cond Proj_proj other than true/false");
+ }
+
+ DB((dbg, LEVEL_4, "Valid Cmp.\n"));
+ return cmp;
+}
+
+/* Returns 1 if all nodes are mode_Iu or mode_Is. */
+static unsigned are_mode_I(ir_node *n1, ir_node* n2, ir_node *n3)
+{
+ ir_mode *m1 = get_irn_mode(n1);
+ ir_mode *m2 = get_irn_mode(n2);
+ ir_mode *m3 = get_irn_mode(n3);
+
+ if ((m1 == mode_Iu && m2 == mode_Iu && m3 == mode_Iu) ||
+ (m1 == mode_Is && m2 == mode_Is && m3 == mode_Is))
+ return 1;
+ else
+ return 0;
+}
+
+/* Checks if cur_loop is a simple tail-controlled counting loop
+ * with start and end value loop invariant, step constant. */
+static unsigned get_unroll_decision_invariant(void)
+{
+
+ ir_node *projres, *loop_condition, *iteration_path;
+ unsigned success, is_latest_val;
+ ir_tarval *step_tar;
+ ir_mode *mode;
+
+
+ /* RETURN if loop is not 'simple' */
+ projres = is_simple_loop();
+ if (projres == NULL)
+ return 0;
+
+ /* Use a minimal size for the invariant unrolled loop,
+ * as duffs device produces overhead */
+ if (loop_info.nodes < opt_params.invar_unrolling_min_size)
+ return 0;
+
loop_condition = get_irn_n(projres, 0);
- DB((dbg, LEVEL_2, " loop condition %N\n", loop_condition));
+ success = get_invariant_pred(loop_condition, &loop_info.end_val, &iteration_path);
+ DB((dbg, LEVEL_4, "pred invar %d\n", success));
+
+ if (! success)
+ return 0;
+
+ DB((dbg, LEVEL_4, "Invariant End_val %N, other %N\n", loop_info.end_val, iteration_path));
+
+ /* We may find the add or the phi first.
+ * Until now we only have end_val. */
+ if (is_Add(iteration_path) || is_Sub(iteration_path)) {
+
+ /* We test against the latest value of the iv. */
+ is_latest_val = 1;
+
+ loop_info.add = iteration_path;
+ DB((dbg, LEVEL_4, "Case 1: Got add %N (maybe not sane)\n", loop_info.add));
+
+ /* Preds of the add should be step and the iteration_phi */
+ success = get_const_pred(loop_info.add, &loop_info.step, &loop_info.iteration_phi);
+ if (! success)
+ return 0;
+
+ DB((dbg, LEVEL_4, "Got step %N\n", loop_info.step));
+
+ if (! is_Phi(loop_info.iteration_phi))
+ return 0;
+
+ DB((dbg, LEVEL_4, "Got phi %N\n", loop_info.iteration_phi));
+
+ /* Find start_val.
+ * Does necessary sanity check of add, if it is already set. */
+ success = get_start_and_add(loop_info.iteration_phi, invariant);
+ if (! success)
+ return 0;
+
+ DB((dbg, LEVEL_4, "Got start A %N\n", loop_info.start_val));
+
+ } else if (is_Phi(iteration_path)) {
+ ir_node *new_iteration_phi;
+
+ /* We compare with the value the iv had entering this run. */
+ is_latest_val = 0;
+
+ loop_info.iteration_phi = iteration_path;
+ DB((dbg, LEVEL_4, "Case 2: Got phi %N\n", loop_info.iteration_phi));
+
+ /* Find start_val and add-node.
+ * Does necessary sanity check of add, if it is already set. */
+ success = get_start_and_add(loop_info.iteration_phi, invariant);
+ if (! success)
+ return 0;
+
+ DB((dbg, LEVEL_4, "Got start B %N\n", loop_info.start_val));
+ DB((dbg, LEVEL_4, "Got add or sub %N\n", loop_info.add));
+
+ success = get_const_pred(loop_info.add, &loop_info.step, &new_iteration_phi);
+ if (! success)
+ return 0;
+
+ DB((dbg, LEVEL_4, "Got step (B) %N\n", loop_info.step));
+
+ if (loop_info.iteration_phi != new_iteration_phi)
+ return 0;
+
+ } else {
+ return 0;
+ }
+
+ mode = get_irn_mode(loop_info.end_val);
+
+ DB((dbg, LEVEL_4, "start %N, end %N, step %N\n",
+ loop_info.start_val, loop_info.end_val, loop_info.step));
+
+ if (mode != mode_Is && mode != mode_Iu)
+ return 0;
+
+ /* TODO necessary? */
+ if (!are_mode_I(loop_info.start_val, loop_info.step, loop_info.end_val))
+ return 0;
+
+ DB((dbg, LEVEL_4, "mode integer\n"));
+
+ step_tar = get_Const_tarval(loop_info.step);
+
+ if (tarval_is_null(step_tar)) {
+ /* TODO Might be worth a warning. */
+ return 0;
+ }
+
+ DB((dbg, LEVEL_4, "step is not 0\n"));
+
+ create_duffs_block();
+
+ return loop_info.max_unroll;
+}
+
+/* Returns unroll factor,
+ * given maximum unroll factor and number of loop passes. */
+static unsigned get_preferred_factor_constant(ir_tarval *count_tar)
+{
+ ir_tarval *tar_6, *tar_5, *tar_4, *tar_3, *tar_2;
+ unsigned prefer;
+ ir_mode *mode = get_irn_mode(loop_info.end_val);
+
+ tar_6 = new_tarval_from_long(6, mode);
+ tar_5 = new_tarval_from_long(5, mode);
+ tar_4 = new_tarval_from_long(4, mode);
+ tar_3 = new_tarval_from_long(3, mode);
+ tar_2 = new_tarval_from_long(2, mode);
+
+ /* loop passes % {6, 5, 4, 3, 2} == 0 */
+ if (tarval_is_null(tarval_mod(count_tar, tar_6)))
+ prefer = 6;
+ else if (tarval_is_null(tarval_mod(count_tar, tar_5)))
+ prefer = 5;
+ else if (tarval_is_null(tarval_mod(count_tar, tar_4)))
+ prefer = 4;
+ else if (tarval_is_null(tarval_mod(count_tar, tar_3)))
+ prefer = 3;
+ else if (tarval_is_null(tarval_mod(count_tar, tar_2)))
+ prefer = 2;
+ else {
+ /* gcd(max_unroll, count_tar) */
+ int a = loop_info.max_unroll;
+ int b = (int)get_tarval_long(count_tar);
+ int c;
+
+ DB((dbg, LEVEL_4, "gcd of max_unroll %d and count_tar %d: ", a, b));
+
+ do {
+ c = a % b;
+ a = b; b = c;
+ } while( c != 0);
+
+ DB((dbg, LEVEL_4, "%d\n", a));
+ return a;
+ }
+
+ DB((dbg, LEVEL_4, "preferred unroll factor %d\n", prefer));
+
+ /*
+ * If our preference is greater than the allowed unroll factor
+ * we either might reduce the preferred factor and prevent a duffs device block,
+ * or create a duffs device block, from which in this case (constants only)
+ * we know the startloop at compiletime.
+ * The latter yields the following graphs.
+ * but for code generation we would want to use graph A.
+ * The graphs are equivalent. So, we can only reduce the preferred factor.
+ * A) B)
+ * PreHead PreHead
+ * | ,--. | ,--.
+ * \ Loop1 \ Loop2 \
+ * \ | | / | |
+ * Loop2 / / Loop1 /
+ * | `--' | `--'
+ */
+
+ if (prefer <= loop_info.max_unroll)
+ return prefer;
+ else {
+ switch(prefer) {
+ case 6:
+ if (loop_info.max_unroll >= 3)
+ return 3;
+ else if (loop_info.max_unroll >= 2)
+ return 2;
+ else
+ return 0;
+
+ case 4:
+ if (loop_info.max_unroll >= 2)
+ return 2;
+ else
+ return 0;
+
+ default:
+ return 0;
+ }
+ }
+}
+
+/* Check if cur_loop is a simple counting loop.
+ * Start, step and end are constants.
+ * TODO The whole constant case should use procedures similar to
+ * the invariant case, as they are more versatile. */
+/* TODO split. */
+static unsigned get_unroll_decision_constant(void)
+{
+ ir_node *cmp, *iteration_path;
+ unsigned success, is_latest_val;
+ ir_tarval *start_tar, *end_tar, *step_tar, *diff_tar, *count_tar;
+ ir_tarval *stepped;
+ ir_relation proj_proj, norm_proj;
+ ir_mode *mode;
+
+ /* RETURN if loop is not 'simple' */
+ cmp = is_simple_loop();
+ if (cmp == NULL)
+ return 0;
- /* One in of the loop condition needs to be loop invariant.
- * The other in is assigned by an add.
- * The add uses a loop invariant value
- * and another value that depends on a loop invariant start value and the add itself.
+ /* One in of the loop condition needs to be loop invariant. => end_val
+ * The other in is assigned by an add. => add
+ * The add uses a loop invariant value => step
+ * and a phi with a loop invariant start_val and the add node as ins.
^ ^
| | .-,
| Phi |
\ | |
- Add /
- |__/
+ ^ Add |
+ \ | \__|
+ cond
+ /\
*/
- end_val = NULL;
- /* Find the loop invariant in */
- /* Assumption that condition is cmp or mod.
- TODO other? */
- pred0 = get_irn_n(loop_condition, 0);
- pred1 = get_irn_n(loop_condition, 1);
+ success = get_const_pred(cmp, &loop_info.end_val, &iteration_path);
+ if (! success)
+ return 0;
- if (is_loop_invariant_val(pred0)) {
- end_val = pred0;
- iteration = pred1;
- }
+ DB((dbg, LEVEL_4, "End_val %N, other %N\n", loop_info.end_val, iteration_path));
+
+ /* We may find the add or the phi first.
+ * Until now we only have end_val. */
+ if (is_Add(iteration_path) || is_Sub(iteration_path)) {
+ /* We test against the latest value of the iv. */
+ is_latest_val = 1;
- if (is_loop_invariant_val(pred1)) {
- if (end_val != NULL)
- /* RETURN. loop condition does not change during the loop. */
+ loop_info.add = iteration_path;
+ DB((dbg, LEVEL_4, "Case 2: Got add %N (maybe not sane)\n", loop_info.add));
+
+ /* Preds of the add should be step and the iteration_phi */
+ success = get_const_pred(loop_info.add, &loop_info.step, &loop_info.iteration_phi);
+ if (! success)
return 0;
- end_val = pred1;
- iteration = pred0;
- }
+ DB((dbg, LEVEL_4, "Got step %N\n", loop_info.step));
+
+ if (! is_Phi(loop_info.iteration_phi))
+ return 0;
- DB((dbg, LEVEL_2, " end_val %N\n", end_val));
+ DB((dbg, LEVEL_4, "Got phi %N\n", loop_info.iteration_phi));
- /* Check for constraint of remaining in. */
- add = is_loop_iteration(iteration);
- if (! add)
- return 0;
+ /* Find start_val.
+ * Does necessary sanity check of add, if it is already set. */
+ success = get_start_and_add(loop_info.iteration_phi, constant);
+ if (! success)
+ return 0;
- DB((dbg, LEVEL_2, " add %N\n", add));
+ DB((dbg, LEVEL_4, "Got start %N\n", loop_info.start_val));
- add_in0 = get_irn_n(add, 0);
- add_in1 = get_irn_n(add, 1);
+ } else if (is_Phi(iteration_path)) {
+ ir_node *new_iteration_phi;
- if (is_loop_invariant_val(add_in0)) {
- step = add_in0;
- iteration_phi = add_in1;
- }
+ /* We compare with the value the iv had entering this run. */
+ is_latest_val = 0;
+
+ loop_info.iteration_phi = iteration_path;
+ DB((dbg, LEVEL_4, "Case 1: Got phi %N \n", loop_info.iteration_phi));
- if (is_loop_invariant_val(add_in1)) {
- if (step != NULL)
+ /* Find start_val and add-node.
+ * Does necessary sanity check of add, if it is already set. */
+ success = get_start_and_add(loop_info.iteration_phi, constant);
+ if (! success)
return 0;
- step = add_in1;
- iteration_phi = add_in0;
- }
- DB((dbg, LEVEL_2, " step %N\n", step));
+ DB((dbg, LEVEL_4, "Got start %N\n", loop_info.start_val));
+ DB((dbg, LEVEL_4, "Got add or sub %N\n", loop_info.add));
- if (! is_Phi(iteration_phi)) {
- if (is_Phi(iteration))
- iteration_phi = iteration;
- else
+ success = get_const_pred(loop_info.add, &loop_info.step, &new_iteration_phi);
+ if (! success)
+ return 0;
+
+ DB((dbg, LEVEL_4, "Got step %N\n", loop_info.step));
+
+ if (loop_info.iteration_phi != new_iteration_phi)
return 0;
+
+ } else {
+ /* RETURN */
+ return 0;
}
- DB((dbg, LEVEL_2, " #### COUNTING LOOP step %N end %N phi %N\n", step, end_val, iteration_phi));
+ mode = get_irn_mode(loop_info.end_val);
-#if 0
- phi for startval
+ DB((dbg, LEVEL_4, "start %N, end %N, step %N\n",
+ loop_info.start_val, loop_info.end_val, loop_info.step));
- mode = get_irn_mode(add);
+ if (mode != mode_Is && mode != mode_Iu)
+ return 0;
- block = new_Block(0, NULL);
- /*set_irg_current_Block(current_ir_graph, block);*/
+ /* TODO necessary? */
+ if (!are_mode_I(loop_info.start_val, loop_info.step, loop_info.end_val))
+ return 0;
- /*TODO*/
- unroll_mod_const = new_Const(unroll_number);
- module = new_r_Mod(block, new_NoMem(), end_val, step, mode, op_pin_state_pinned);
- /*new_Proj();*/
+ DB((dbg, LEVEL_4, "mode integer\n"));
+ end_tar = get_Const_tarval(loop_info.end_val);
+ start_tar = get_Const_tarval(loop_info.start_val);
+ step_tar = get_Const_tarval(loop_info.step);
-#endif
- return 0;
+ if (tarval_is_null(step_tar))
+ /* TODO Might be worth a warning. */
+ return 0;
+
+ DB((dbg, LEVEL_4, "step is not 0\n"));
+
+ if ((!tarval_is_negative(step_tar)) ^ (!is_Sub(loop_info.add)))
+ loop_info.decreasing = 1;
+
+ diff_tar = tarval_sub(end_tar, start_tar, mode);
+
+ /* We need at least count_tar steps to be close to end_val, maybe more.
+ * No way, that we have gone too many steps.
+ * This represents the 'latest value'.
+ * (If condition checks against latest value, is checked later) */
+ count_tar = tarval_div(diff_tar, step_tar);
+
+ /* Iv will not pass end_val (except overflows).
+ * Nothing done, as it would yield to no advantage. */
+ if (tarval_is_negative(count_tar)) {
+ DB((dbg, LEVEL_4, "Loop is endless or never taken."));
+ /* TODO Might be worth a warning. */
+ return 0;
+ }
+
+ count_stats(stats.u_simple_counting_loop);
+
+ loop_info.latest_value = is_latest_val;
+
+ /* TODO split here
+ if (! is_simple_counting_loop(&count_tar))
+ return 0;
+ */
+
+ /* stepped can be negative, if step < 0 */
+ stepped = tarval_mul(count_tar, step_tar);
+
+ /* step as close to end_val as possible, */
+ /* |stepped| <= |end_tar|, and dist(stepped, end_tar) is smaller than a step. */
+ if (is_Sub(loop_info.add))
+ stepped = tarval_sub(start_tar, stepped, mode_Is);
+ else
+ stepped = tarval_add(start_tar, stepped);
+
+ DB((dbg, LEVEL_4, "stepped to %ld\n", get_tarval_long(stepped)));
+
+ proj_proj = get_Cmp_relation(cmp);
+ /* Assure that norm_proj is the stay-in-loop case. */
+ if (loop_info.exit_cond == 1)
+ norm_proj = get_negated_relation(proj_proj);
+ else
+ norm_proj = proj_proj;
+
+ DB((dbg, LEVEL_4, "normalized projection %s\n", get_relation_string(norm_proj)));
+ /* Executed at most once (stay in counting loop if a Eq b) */
+ if (norm_proj == ir_relation_equal)
+ /* TODO Might be worth a warning. */
+ return 0;
+
+ /* calculates next values and increases count_tar according to it */
+ success = simulate_next(&count_tar, stepped, step_tar, end_tar, norm_proj);
+ if (! success)
+ return 0;
+
+ /* We run loop once more, if we compare to the
+ * not yet in-/decreased iv. */
+ if (is_latest_val == 0) {
+ DB((dbg, LEVEL_4, "condition uses not latest iv value\n"));
+ count_tar = tarval_add(count_tar, get_tarval_one(mode));
+ }
+
+ DB((dbg, LEVEL_4, "loop taken %ld times\n", get_tarval_long(count_tar)));
+
+ /* Assure the loop is taken at least 1 time. */
+ if (tarval_is_null(count_tar)) {
+ /* TODO Might be worth a warning. */
+ return 0;
+ }
+
+ loop_info.count_tar = count_tar;
+ return get_preferred_factor_constant(count_tar);
}
-#endif
/**
* Loop unrolling
*/
static void unroll_loop(void)
{
- int i;
- unsigned unroll_number;
- out_edge *ssa_outs;
- cur_loop_outs = NEW_ARR_F(out_edge, 0);
-
- /* Get loop outs */
- irg_walk_graph(current_ir_graph, get_loop_outs, NULL, NULL);
- unroll_number = get_unroll_decision(cur_loop_outs);
+ if (! (loop_info.nodes > 0))
+ return;
- /*dump_ir_block_graph(current_ir_graph, "-pre");*/
+#if LOOP_IGNORE_NODE_LIMITS
+ DB((dbg, LEVEL_1, "WARNING: Loop node limitations ignored."));
+#else
+ if (loop_info.nodes > opt_params.max_unrolled_loop_size) {
+ DB((dbg, LEVEL_2, "Nodes %d > allowed nodes %d\n",
+ loop_info.nodes, opt_params.max_unrolled_loop_size));
+ count_stats(stats.too_large);
+ return;
+ }
- if (unroll_number) {
- create_duffs_device(unroll_number);
+ if (loop_info.calls > 0) {
+ DB((dbg, LEVEL_2, "Calls %d > allowed calls 0\n",
+ loop_info.calls));
+ count_stats(stats.calls_limit);
+ return;
+ }
+#endif
- /* Copies the loop and allocs node_info */
- copy_loop(cur_loop_outs, unroll_number - 1);
- /*dump_ir_block_graph(current_ir_graph, "-cp");*/
+ unroll_nr = 0;
- /* Line up the floating copies. */
- place_copies(unroll_number - 1);
- /*dump_ir_block_graph(current_ir_graph, "-ord");*/
+ /* get_unroll_decision_constant and invariant are completely
+ * independent for flexibility.
+ * Some checks may be performed twice. */
- /* Extend loop successors */
- ssa_outs = extend_ins(cur_loop_outs, unroll_number - 1);
- /*dump_ir_block_graph(current_ir_graph, "-fixed")*/ ;
+ /* constant case? */
+ if (opt_params.allow_const_unrolling)
+ unroll_nr = get_unroll_decision_constant();
+ if (unroll_nr > 1) {
+ loop_info.unroll_kind = constant;
- /* Links are going to be overwritten */
- free_node_info_blocks();
+ } else {
+ /* invariant case? */
+ if (opt_params.allow_invar_unrolling)
+ unroll_nr = get_unroll_decision_invariant();
+ if (unroll_nr > 1)
+ loop_info.unroll_kind = invariant;
+ }
- /* Generate phis for all loop outs */
- for (i = 0; i < ARR_LEN(ssa_outs); ++i) {
- out_edge entry = ssa_outs[i];
- ir_node *node = entry.node;
- ir_node *pred = get_irn_n(entry.node, entry.pos);
+ DB((dbg, LEVEL_2, " *** Unrolling %d times ***\n", unroll_nr));
- DB((dbg, LEVEL_5, "Do? construct_ssa_n def %N node %N pos %d\n",
- pred, node, entry.pos));
+ if (unroll_nr > 1) {
+ loop_entries = NEW_ARR_F(entry_edge, 0);
- if (!is_End(node)) {
- DB((dbg, LEVEL_5, "construct_ssa_n def %N node %N pos %d\n",
- pred, node, entry.pos));
+ /* Get loop outs */
+ irg_walk_graph(current_ir_graph, get_loop_entries, NULL, NULL);
- construct_ssa_n(pred, node, unroll_number - 1);
- /*if (new_phi)
- construct_ssa_n(pred, new_phi, unroll_number - 1);*/
- }
+ if (loop_info.unroll_kind == constant) {
+ if ((int)get_tarval_long(loop_info.count_tar) == unroll_nr)
+ loop_info.needs_backedge = 0;
+ else
+ loop_info.needs_backedge = 1;
+ } else {
+ loop_info.needs_backedge = 1;
}
- /*dump_ir_block_graph(current_ir_graph, "-ssa-done");*/
- /* FREE */
- free_node_info();
+ /* Use phase to keep copy of nodes from the condition chain. */
+ phase = new_phase(current_ir_graph, phase_irn_init_default);
+
+ /* Copies the loop */
+ copy_loop(loop_entries, unroll_nr - 1);
+
+ /* Line up the floating copies. */
+ place_copies(unroll_nr - 1);
+ /* Remove phis with 1 in
+ * If there were no nested phis, this would not be necessary.
+ * Avoiding the creation in the first place
+ * leads to complex special cases. */
irg_walk_graph(current_ir_graph, correct_phis, NULL, NULL);
- DEL_ARR_F(ssa_outs);
+ if (loop_info.unroll_kind == constant)
+ count_stats(stats.constant_unroll);
+ else
+ count_stats(stats.invariant_unroll);
set_irg_doms_inconsistent(current_ir_graph);
set_irg_loopinfo_inconsistent(current_ir_graph);
+ /* TODO is it? */
set_irg_outs_inconsistent(current_ir_graph);
+
+ DEL_ARR_F(loop_entries);
}
- DEL_ARR_F(cur_loop_outs);
+
}
-/* Initialization and */
+/* Analyzes the loop, and checks if size is within allowed range.
+ * Decides if loop will be processed. */
static void init_analyze(ir_loop *loop)
{
- /* Init new for every loop */
cur_loop = loop;
loop_head = NULL;
loop_head_valid = 1;
- loop_inv_head = NULL;
- loop_peeled_head = NULL;
- loop_info.calls = 0;
- loop_info.blocks = 0;
- loop_info.cf_outs = 0;
+ /* Reset loop info */
+ memset(&loop_info, 0, sizeof(loop_info_t));
- DB((dbg, LEVEL_2, " >>>> current loop includes node %N <<<\n",
- get_loop_node(loop, 0)));
+ DB((dbg, LEVEL_1, " >>>> current loop includes node %N <<<\n",
+ get_loop_node(loop, 0)));
+ /* Collect loop informations: head, node counts. */
irg_walk_graph(current_ir_graph, get_loop_info, NULL, NULL);
/* RETURN if there is no valid head */
if (!loop_head || !loop_head_valid) {
- DB((dbg, LEVEL_2, "No valid loop head. Nothing done.\n"));
+ DB((dbg, LEVEL_1, "No valid loop head. Nothing done.\n"));
return;
+ } else {
+ DB((dbg, LEVEL_1, "Loophead: %N\n", loop_head));
}
- DB((dbg, LEVEL_2, "Loophead: %N\n", loop_head));
+ if (loop_info.branches > opt_params.max_branches) {
+ DB((dbg, LEVEL_1, "Branches %d > allowed branches %d\n",
+ loop_info.branches, opt_params.max_branches));
+ count_stats(stats.calls_limit);
+ return;
+ }
- if (enable_inversion)
- loop_inversion();
+ switch (loop_op) {
+ case loop_op_inversion:
+ loop_inversion();
+ break;
- if (enable_unrolling)
- unroll_loop();
+ case loop_op_unrolling:
+ unroll_loop();
+ break;
- DB((dbg, LEVEL_2, " <<<< end of loop with node %N >>>>\n",
- get_loop_node(loop, 0)));
+ default:
+ panic("Loop optimization not implemented.");
+ }
+ DB((dbg, LEVEL_1, " <<<< end of loop with node %N >>>>\n",
+ get_loop_node(loop, 0)));
}
-/* Find most inner loops and send them to analyze_loop */
-static void find_most_inner_loop(ir_loop *loop)
+/* Find innermost loops and add them to loops. */
+static void find_innermost_loop(ir_loop *loop)
{
/* descend into sons */
- int sons = get_loop_n_sons(loop);
+ size_t sons = get_loop_n_sons(loop);
if (sons == 0) {
ARR_APP1(ir_loop *, loops, loop);
} else {
- int s;
- for (s=0; s<sons; s++) {
- find_most_inner_loop(get_loop_son(loop, s));
+ size_t s;
+ for (s = 0; s < sons; ++s) {
+ find_innermost_loop(get_loop_son(loop, s));
}
}
}
-/**
- * Assure preconditions are met and go through all loops.
- */
+static void set_loop_params(void)
+{
+ opt_params.max_loop_size = 100;
+ opt_params.depth_adaption = -50;
+ opt_params.count_phi = 1;
+ opt_params.count_proj = 0;
+ opt_params.allowed_calls = 0;
+
+ opt_params.max_cc_size = 5;
+
+
+ opt_params.allow_const_unrolling = 1;
+ opt_params.allow_invar_unrolling = 0;
+
+ opt_params.invar_unrolling_min_size = 20;
+ opt_params.max_unrolled_loop_size = 400;
+ opt_params.max_branches = 9999;
+}
+
+/* Assure preconditions are met and go through all loops. */
void loop_optimization(ir_graph *irg)
{
ir_loop *loop;
- int i, sons, nr;
+ size_t sons, nr;
+ size_t i;
+
+ set_loop_params();
+
+ /* Reset stats for this procedure */
+ reset_stats();
- /* Init */
- free_list = NULL;
+ /* Preconditions */
set_current_ir_graph(irg);
edges_assure(irg);
loops = NEW_ARR_F(ir_loop *, 0);
/* List all inner loops */
for (nr = 0; nr < sons; ++nr) {
- find_most_inner_loop(get_loop_son(loop, nr));
+ find_innermost_loop(get_loop_son(loop, nr));
}
ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
- /* Set all links NULL */
+ /* Set all links to NULL */
irg_walk_graph(current_ir_graph, reset_link, NULL, NULL);
for (i = 0; i < ARR_LEN(loops); ++i) {
ir_loop *loop = loops[i];
+
+ count_stats(stats.loops);
+
+ /* Analyze and handle loop */
init_analyze(loop);
- /*dump_ir_block_graph(current_ir_graph, "-part");*/
+ /* Copied blocks do not have their phi list yet */
collect_phiprojs(irg);
+
+ /* Set links to NULL
+ * TODO Still necessary? */
irg_walk_graph(current_ir_graph, reset_link, NULL, NULL);
}
- /*dump_ir_block_graph(current_ir_graph, "-full");*/
+ print_stats();
DEL_ARR_F(loops);
ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
void do_loop_unrolling(ir_graph *irg)
{
- enable_unrolling = 1;
- enable_peeling = 0;
- enable_inversion = 0;
+ loop_op = loop_op_unrolling;
- DB((dbg, LEVEL_2, " >>> unrolling (Startnode %N) <<<\n",
+ DB((dbg, LEVEL_1, " >>> unrolling (Startnode %N) <<<\n",
get_irg_start(irg)));
loop_optimization(irg);
- DB((dbg, LEVEL_2, " >>> unrolling done (Startnode %N) <<<\n",
+ DB((dbg, LEVEL_1, " >>> unrolling done (Startnode %N) <<<\n",
get_irg_start(irg)));
}
void do_loop_inversion(ir_graph *irg)
{
- enable_unrolling = 0;
- enable_peeling = 0;
- enable_inversion = 1;
+ loop_op = loop_op_inversion;
- DB((dbg, LEVEL_2, " >>> inversion (Startnode %N) <<<\n",
+ DB((dbg, LEVEL_1, " >>> inversion (Startnode %N) <<<\n",
get_irg_start(irg)));
loop_optimization(irg);
- DB((dbg, LEVEL_2, " >>> inversion done (Startnode %N) <<<\n",
+ assure_cf_loop(irg);
+
+ DB((dbg, LEVEL_1, " >>> inversion done (Startnode %N) <<<\n",
get_irg_start(irg)));
}
void do_loop_peeling(ir_graph *irg)
{
- enable_unrolling = 0;
- enable_peeling = 1;
- enable_inversion = 0;
+ loop_op = loop_op_peeling;
- DB((dbg, LEVEL_2, " >>> peeling (Startnode %N) <<<\n",
+ DB((dbg, LEVEL_1, " >>> peeling (Startnode %N) <<<\n",
get_irg_start(irg)));
loop_optimization(irg);
- DB((dbg, LEVEL_2, " >>> peeling done (Startnode %N) <<<\n",
+ DB((dbg, LEVEL_1, " >>> peeling done (Startnode %N) <<<\n",
get_irg_start(irg)));
}
projects / libfirm / blobdiff