* @author Michael Beck
* @version $Id$
*
- * This phase find congruent blocks. Works currently for
- * predecessors of the end block only.
+ * This phase find congruent blocks.
* Two block are congruent, if they contains only equal calculations.
*/
#include "config.h"
-#include "ircons.h"
+
#include "iroptimize.h"
+#include "ircons.h"
#include "irgmod.h"
#include "irgraph_t.h"
#include "irnode_t.h"
#include "trouts.h"
#include "irgwalk.h"
#include "set.h"
+#include "irpass.h"
#include "debug.h"
-/* define this for gneral block shaping */
+/* define this for general block shaping: congruent blocks
+ are found not only before the end block but anywhere in the graph */
#define GENERAL_SHAPE
typedef struct partition_t partition_t;
tarval *tv; /**< For Const nodes, its tarval */
symconst_symbol sym; /**< For SymConst nodes, its symbol .*/
void *addr; /**< Alias all addresses. */
+ int intVal; /**< For Conv/Div nodes: strict/remainderless. */
} u;
};
struct obstack obst; /** obstack for temporary data */
};
-/** A node, input index pair. */
+/** A (node, input index) pair. */
struct pair_t {
pair_t *next; /**< Points to the next pair entry. */
ir_node *irn; /**< The IR-node. */
/**
* Dump partition to output.
*/
-static void dump_partition(const char *msg, const partition_t *part) {
+static void dump_partition(const char *msg, const partition_t *part)
+{
const block_t *block;
int first = 1;
/**
* Dumps a list.
*/
-static void dump_list(const char *msg, const block_t *block) {
+static void dump_list(const char *msg, const block_t *block)
+{
const block_t *p;
int first = 1;
/**
* Compare two pointer values of a listmap.
*/
-static int listmap_cmp_ptr(const void *elt, const void *key, size_t size) {
+static int listmap_cmp_ptr(const void *elt, const void *key, size_t size)
+{
const listmap_entry_t *e1 = elt;
const listmap_entry_t *e2 = key;
*
* @param map the listmap
*/
-static void listmap_init(listmap_t *map) {
+static void listmap_init(listmap_t *map)
+{
map->map = new_set(listmap_cmp_ptr, 16);
map->values = NULL;
} /* listmap_init */
*
* @param map the listmap
*/
-static void listmap_term(listmap_t *map) {
+static void listmap_term(listmap_t *map)
+{
del_set(map->map);
} /* listmap_term */
*
* @return the associated listmap entry for the given id
*/
-static listmap_entry_t *listmap_find(listmap_t *map, void *id) {
+static listmap_entry_t *listmap_find(listmap_t *map, void *id)
+{
listmap_entry_t key, *entry;
key.id = id;
*
* @return a hash value for the given opcode map entry
*/
-static unsigned opcode_hash(const opcode_key_t *entry) {
+static unsigned opcode_hash(const opcode_key_t *entry)
+{
+ /* assume long >= int */
return (entry->mode - (ir_mode *)0) * 9 + entry->code + entry->u.proj * 3 + HASH_PTR(entry->u.addr) + entry->arity;
} /* opcode_hash */
/**
* Compare two entries in the opcode map.
*/
-static int cmp_opcode(const void *elt, const void *key, size_t size) {
+static int cmp_opcode(const void *elt, const void *key, size_t size)
+{
const opcode_key_t *o1 = elt;
const opcode_key_t *o2 = key;
* Creates a new empty partition and put in on the
* partitions list.
*
- * @param meet_block the control flow meet block of thi partition
+ * @param meet_block the control flow meet block of this partition
* @param env the environment
*/
-static partition_t *create_partition(ir_node *meet_block, environment_t *env) {
- partition_t *part = obstack_alloc(&env->obst, sizeof(*part));
+static partition_t *create_partition(ir_node *meet_block, environment_t *env)
+{
+ partition_t *part = OALLOC(&env->obst, partition_t);
INIT_LIST_HEAD(&part->blocks);
part->meet_block = meet_block;
* @param partition the partition to add to
* @param env the environment
*/
-static block_t *create_block(ir_node *block, int meet_input, partition_t *partition, environment_t *env) {
- block_t *bl = obstack_alloc(&env->obst, sizeof(*bl));
+static block_t *create_block(ir_node *block, int meet_input, partition_t *partition, environment_t *env)
+{
+ block_t *bl = OALLOC(&env->obst, block_t);
set_irn_link(block, bl);
* @param block the block to add to
* @param env the environment
*/
-static node_t *create_node(ir_node *irn, block_t *block, environment_t *env) {
- node_t *node = obstack_alloc(&env->obst, sizeof(*node));
+static node_t *create_node(ir_node *irn, block_t *block, environment_t *env)
+{
+ node_t *node = OALLOC(&env->obst, node_t);
node->node = irn;
node->is_input = 0;
* @param idx the index of the block input in node's predecessors
* @param env the environment
*/
-static void add_pair(block_t *block, ir_node *irn, int idx, environment_t *env) {
- pair_t *pair = obstack_alloc(&env->obst, sizeof(*pair));
+static void add_pair(block_t *block, ir_node *irn, int idx, environment_t *env)
+{
+ pair_t *pair = OALLOC(&env->obst, pair_t);
pair->next = block->input_pairs;
pair->irn = irn;
* @param phi the Phi node
* @param env the environment
*/
-static void add_phi(block_t *block, ir_node *phi, environment_t *env) {
- phi_t *node = obstack_alloc(&env->obst, sizeof(*node));
+static void add_phi(block_t *block, ir_node *phi, environment_t *env)
+{
+ phi_t *node = OALLOC(&env->obst, phi_t);
node->next = block->phis;
node->phi = phi;
/**
* Creates an opcode from a node.
*/
-static opcode_key_t *opcode(const node_t *node, environment_t *env) {
+static opcode_key_t *opcode(const node_t *node, environment_t *env)
+{
opcode_key_t key, *entry;
ir_node *irn = node->node;
case iro_Const:
key.u.tv = get_Const_tarval(irn);
break;
+ case iro_Conv:
+ key.u.intVal = get_Conv_strict(irn);
+ break;
+ case iro_Load:
+ key.mode = get_Load_mode(irn);
+ break;
+ case iro_Div:
+ key.u.intVal = get_Div_no_remainder(irn);
+ break;
+ case iro_Builtin:
+ key.u.intVal = get_Builtin_kind(irn);
+ break;
default:
break;
}
*
* @return a new partition containing the nodes of g
*/
-static partition_t *split(partition_t *Z, block_t *g, environment_t *env) {
+static partition_t *split(partition_t *Z, block_t *g, environment_t *env)
+{
partition_t *Z_prime;
block_t *block;
unsigned n = 0;
} /* split */
/**
- * Rteurn non-zero if pred should be tread as a input node.
+ * Return non-zero if pred should be tread as a input node.
*/
-static int is_input_node(ir_node *pred, ir_node *irn, int index) {
+static int is_input_node(ir_node *pred, ir_node *irn, int index)
+{
/* for now, do NOT turn direct calls into indirect one */
if (index != 1)
return 1;
* @param part the partition
* @param env the environment
*/
-void propagate_blocks(partition_t *part, environment_t *env) {
+static void propagate_blocks(partition_t *part, environment_t *env)
+{
block_t *ready_blocks = NULL;
unsigned n_ready = 0;
block_t *bl, *next;
DB((dbg, LEVEL_3, " propagate Input %+F\n", node->node));
}
- /* Add bl to map[opcode(bl)]. */
+ /* Add bl to map[opcode(n)]. */
id = opcode(node, env);
entry = listmap_find(&map, id);
bl->next = entry->list;
*
* @param env the environment
*/
-void propagate(environment_t *env) {
+static void propagate(environment_t *env)
+{
partition_t *part, *next;
list_for_each_entry_safe(partition_t, part, next, &env->partitions, part_list) {
/**
* Map a block to the phi[block->input] live-trough.
*/
-static void *live_throughs(const block_t *bl, const ir_node *phi) {
+static void *live_throughs(const block_t *bl, const ir_node *phi)
+{
ir_node *input = get_Phi_pred(phi, bl->meet_input);
/* If this input is inside our block, this
* @param part the partition
* @param env the environment
*/
-void propagate_blocks_live_troughs(partition_t *part, environment_t *env) {
+static void propagate_blocks_live_troughs(partition_t *part, environment_t *env)
+{
const ir_node *meet_block = part->meet_block;
block_t *bl, *next;
listmap_t map;
*
* @param env the environment
*/
-void propagate_live_troughs(environment_t *env) {
+static void propagate_live_troughs(environment_t *env)
+{
partition_t *part, *next;
list_for_each_entry_safe(partition_t, part, next, &env->partitions, part_list) {
*
* @param part the partition to process
*/
-static void apply(ir_graph *irg, partition_t *part) {
+static void apply(ir_graph *irg, partition_t *part)
+{
block_t *repr = list_entry(part->blocks.next, block_t, block_list);
block_t *bl;
ir_node *block, *end, *meet_block, *p, *next;
if (is_op_forking(cfop)) {
/* a critical edge */
ir_node *block = new_r_Block(irg, 1, &ins[i]);
- ir_node *jmp = new_r_Jmp(irg, block);
+ ir_node *jmp = new_r_Jmp(block);
ins[i] = jmp;
}
}
for (repr_pair = repr->input_pairs; repr_pair != NULL; repr_pair = repr_pair->next) {
ir_node *input = get_irn_n(repr_pair->irn, repr_pair->index);
ir_mode *mode = get_irn_mode(input);
- ir_node *phi = new_r_Phi(current_ir_graph, block, n, repr_pair->ins, mode);
+ ir_node *phi = new_r_Phi(block, n, repr_pair->ins, mode);
set_irn_n(repr_pair->irn, repr_pair->index, phi);
DEL_ARR_F(repr_pair->ins);
* @param end_block the end block
* @param env the environment
*/
-static void partition_for_end_block(ir_node *end_block, environment_t *env) {
+static void partition_for_end_block(ir_node *end_block, environment_t *env)
+{
partition_t *part = create_partition(end_block, env);
ir_node *end;
int i;
* @param n_preds number of elements in preds
* @param env the environment
*/
-static void partition_for_block(ir_node *block, pred_t preds[], int n_preds, environment_t *env) {
+static void partition_for_block(ir_node *block, pred_t preds[], int n_preds, environment_t *env)
+{
partition_t *part = create_partition(block, env);
int i;
* Walker: clear the links of all block phi lists and normal
* links.
*/
-static void clear_phi_links(ir_node *irn, void *env) {
+static void clear_phi_links(ir_node *irn, void *env)
+{
(void) env;
if (is_Block(irn)) {
set_Block_phis(irn, NULL);
/**
* Walker, detect live-out nodes.
*/
-static void find_liveouts(ir_node *irn, void *ctx) {
+static void find_liveouts(ir_node *irn, void *ctx)
+{
environment_t *env = ctx;
ir_node **live_outs = env->live_outs;
ir_node *this_block;
/**
* Check if the current block is the meet block of a its predecessors.
*/
-static void check_for_cf_meet(ir_node *block, void *ctx) {
+static void check_for_cf_meet(ir_node *block, void *ctx)
+{
environment_t *env = ctx;
int i, k, n;
pred_t *preds;
/**
* Compare two nodes for root ordering.
*/
-static int cmp_nodes(const void *a, const void *b) {
- ir_node *const *pa = a;
- ir_node *const *pb = b;
+static int cmp_nodes(const void *a, const void *b)
+{
+ const ir_node *const *pa = a;
+ const ir_node *const *pb = b;
const ir_node *irn_a = *pa;
const ir_node *irn_b = *pb;
ir_opcode code_a = get_irn_opcode(irn_a);
/**
* Add the roots to all blocks.
*/
-static void add_roots(ir_graph *irg, environment_t *env) {
+static void add_roots(ir_graph *irg, environment_t *env)
+{
unsigned idx, n = get_irg_last_idx(irg);
ir_node **live_outs = env->live_outs;
block_t *bl;
}
/*
* Now sort the roots to normalize them as good as possible.
- * Else, we will split identical blocks if we start which different roots
+ * Else, we will split identical blocks if we start which different roots.
*/
for (bl = env->all_blocks; bl != NULL; bl = bl->all_next) {
int i, n = ARR_LEN(bl->roots);
#endif /* GENERAL_SHAPE */
/* Combines congruent end blocks into one. */
-int shape_blocks(ir_graph *irg) {
+int shape_blocks(ir_graph *irg)
+{
ir_graph *rem;
environment_t env;
partition_t *part;
+ block_t *bl;
int res, n;
rem = current_ir_graph;
// dump_ir_block_graph(irg, "-after");
}
+ for (bl = env.all_blocks; bl != NULL; bl = bl->all_next) {
+ DEL_ARR_F(bl->roots);
+ }
+
DEL_ARR_F(env.live_outs);
del_set(env.opcode2id_map);
obstack_free(&env.obst, NULL);
return res;
} /* shape_blocks */
+
+ir_graph_pass_t *shape_blocks_pass(const char *name)
+{
+ return def_graph_pass_ret(name ? name : "shape_blocks", shape_blocks);
+} /* shape_blocks_pass */
projects / libfirm / blobdiff