summaryrefslogtreecommitdiffhomepage
path: root/ir/be/beutil.c
diff options
context:
space:
mode:
authorMatthias Braun <matze@braunis.de>2014-08-21 13:48:55 +0200
committerMatthias Braun <matze@braunis.de>2014-08-21 13:58:29 +0200
commit0632abc1600b0f512945116af36e0dbdaefb5f47 (patch)
treeb6f1991476a27266774fc120f3ceea42b3e60540 /ir/be/beutil.c
parente353af9a2dd70bb283051040f7ba7bd729e1c05e (diff)
merge beirgmod.* into beutil.*
Diffstat (limited to 'ir/be/beutil.c')
-rw-r--r--ir/be/beutil.c137
1 files changed, 129 insertions, 8 deletions
diff --git a/ir/be/beutil.c b/ir/be/beutil.c
index b32242c..9373c2c 100644
--- a/ir/be/beutil.c
+++ b/ir/be/beutil.c
@@ -10,17 +10,23 @@
*/
#include <stdio.h>
-#include "irgwalk.h"
-#include "irdom_t.h"
+#include "bearch.h"
+#include "beirg.h"
+#include "belive.h"
+#include "benode.h"
+#include "besched.h"
+#include "bessaconstr.h"
+#include "beutil.h"
#include "ircons.h"
-#include "iropt.h"
+#include "irdom_t.h"
+#include "iredges_t.h"
+#include "irgmod.h"
#include "irgopt.h"
+#include "irgwalk.h"
+#include "irnodeset.h"
+#include "iropt.h"
#include "irtools.h"
-#include "iredges_t.h"
-
-#include "beutil.h"
-#include "besched.h"
-#include "bearch.h"
+#include "util.h"
/**
* Gets the Proj with number pn from irn.
@@ -62,3 +68,118 @@ ir_node **be_get_cfgpostorder(ir_graph *irg)
return list;
}
+
+static int cmp_node_nr(const void *a, const void *b)
+{
+ ir_node **p1 = (ir_node**)a;
+ ir_node **p2 = (ir_node**)b;
+ long n1 = get_irn_node_nr(*p1);
+ long n2 = get_irn_node_nr(*p2);
+ return (n1>n2) - (n1<n2);
+}
+
+ir_node *insert_Perm_before(ir_graph *irg, const arch_register_class_t *cls,
+ ir_node *const pos)
+{
+ ir_nodeset_t live;
+ ir_nodeset_init(&live);
+ be_lv_t *lv = be_get_irg_liveness(irg);
+ be_liveness_nodes_live_before(lv, cls, pos, &live);
+
+ size_t n = ir_nodeset_size(&live);
+ if (n == 0) {
+ ir_nodeset_destroy(&live);
+ return NULL;
+ }
+
+ ir_node **nodes = XMALLOCN(ir_node*, n);
+ size_t p = 0;
+ foreach_ir_nodeset(&live, irn, iter) {
+ nodes[p++] = irn;
+ }
+ ir_nodeset_destroy(&live);
+ /* make the input order deterministic */
+ QSORT(nodes, n, cmp_node_nr);
+
+ ir_node *const block = get_nodes_block(pos);
+ ir_node *const perm = be_new_Perm(cls, block, n, nodes);
+ sched_add_before(pos, perm);
+ free(nodes);
+
+ for (size_t i = 0; i < n; ++i) {
+ ir_node *perm_op = get_irn_n(perm, i);
+ ir_mode *mode = get_irn_mode(perm_op);
+ ir_node *proj = new_r_Proj(perm, mode, i);
+
+ be_ssa_construction_env_t senv;
+ be_ssa_construction_init(&senv, irg);
+ be_ssa_construction_add_copy(&senv, perm_op);
+ be_ssa_construction_add_copy(&senv, proj);
+ be_ssa_construction_fix_users(&senv, perm_op);
+ be_ssa_construction_update_liveness_phis(&senv, lv);
+ be_liveness_update(lv, perm_op);
+ be_liveness_update(lv, proj);
+ be_ssa_construction_destroy(&senv);
+ }
+ return perm;
+}
+
+//---------------------------------------------------------------------------
+
+typedef struct remove_dead_nodes_env_t_ {
+ bitset_t *reachable;
+ be_lv_t *lv;
+} remove_dead_nodes_env_t;
+
+/**
+ * Post-walker: remember all visited nodes in a bitset.
+ */
+static void mark_dead_nodes_walker(ir_node *node, void *data)
+{
+ remove_dead_nodes_env_t *env = (remove_dead_nodes_env_t*) data;
+ bitset_set(env->reachable, get_irn_idx(node));
+}
+
+/**
+ * Post-block-walker:
+ * Walk through the schedule of every block and remove all dead nodes from it.
+ */
+static void remove_dead_nodes_walker(ir_node *block, void *data)
+{
+ remove_dead_nodes_env_t *env = (remove_dead_nodes_env_t*) data;
+
+ sched_foreach_safe(block, node) {
+ if (bitset_is_set(env->reachable, get_irn_idx(node)))
+ continue;
+
+ if (env->lv != NULL)
+ be_liveness_remove(env->lv, node);
+ sched_remove(node);
+
+ /* kill projs */
+ if (get_irn_mode(node) == mode_T) {
+ foreach_out_edge_safe(node, edge) {
+ ir_node *proj = get_edge_src_irn(edge);
+ if (!is_Proj(proj))
+ continue;
+ if (env->lv != NULL)
+ be_liveness_remove(env->lv, proj);
+ kill_node(proj);
+ }
+ }
+ kill_node(node);
+ }
+}
+
+void be_remove_dead_nodes_from_schedule(ir_graph *irg)
+{
+ remove_dead_nodes_env_t env;
+ env.reachable = bitset_alloca(get_irg_last_idx(irg));
+ env.lv = be_get_irg_liveness(irg);
+
+ /* mark all reachable nodes */
+ irg_walk_graph(irg, mark_dead_nodes_walker, NULL, &env);
+
+ /* walk schedule and remove non-marked nodes */
+ irg_block_walk_graph(irg, remove_dead_nodes_walker, NULL, &env);
+}