+/**
+ * Returns the difference of regs_output - regs_input;
+ */
+static int get_reg_difference(block_sched_env_t *be, ir_node *irn) {
+ int num_out = 0;
+ int num_in = 0;
+ int i;
+
+ if (get_irn_mode(irn) == mode_T) {
+ /* mode_T nodes: num out regs == num Projs with mode datab */
+ const ir_edge_t *edge;
+ foreach_out_edge(irn, edge) {
+ ir_node *proj = get_edge_src_irn(edge);
+ if (mode_is_datab(get_irn_mode(proj)))
+ num_out++;
+ }
+ }
+ else
+ num_out = 1;
+
+ /* num in regs: number of ins with mode datab and not ignore */
+ for (i = get_irn_arity(irn) - 1; i >= 0; i--) {
+ ir_node *in = get_irn_n(irn, i);
+ if (mode_is_datab(get_irn_mode(in)) && ! arch_irn_is(be->sched_env->arch_env, in, ignore))
+ num_in++;
+ }
+
+ return num_out - num_in;
+}
+
+/**
+ * Execute the heuristic function,
+ */
+static ir_node *select_node_heuristic(block_sched_env_t *be, nodeset *ns)
+{
+ ir_node *irn, *cand = NULL;
+
+/* prefer instructions which can be scheduled early */
+#define PRIO_TIME 16
+/* prefer instructions with lots of successors */
+#define PRIO_NUMSUCCS 8
+/* prefer instructions with long critical path */
+#define PRIO_LEVEL 12
+/* prefer instructions coming early in preorder */
+#define PRIO_PREORD 8
+/* weight of current register pressure */
+#define PRIO_CUR_PRESS 20
+/* weight of register pressure difference */
+#define PRIO_CHG_PRESS 8
+
+ /* schedule keeps as early as possible */
+ foreach_nodeset(ns, irn) {
+ if (be_is_Keep(irn)) {
+ nodeset_break(ns);
+ return irn;
+ }
+ }
+
+ if (be->sched_env->sel_strategy & BE_SCHED_SELECT_HEUR) {
+ int max_prio = INT_MIN;
+ int cur_prio = INT_MIN;
+ int cur_pressure = get_cur_reg_pressure(be);
+ int reg_fact, cand_reg_fact;
+
+ /* priority based selection, heuristic inspired by mueller diss */
+ foreach_nodeset(ns, irn) {
+ /* make sure that branches are scheduled last */
+ if (! arch_irn_class_is(be->sched_env->arch_env, irn, branch)) {
+ int rdiff = get_irn_reg_diff(be, irn);
+ int sign = rdiff < 0;
+ int chg = (rdiff < 0 ? -rdiff : rdiff) << PRIO_CHG_PRESS;
+
+ reg_fact = chg << cur_pressure;
+ if (reg_fact < chg)
+ reg_fact = INT_MAX - 2;
+ reg_fact = sign ? -reg_fact : reg_fact;
+
+ cur_prio = (get_irn_critical_path_len(be, irn) << PRIO_LEVEL)
+ //- (get_irn_delay(be, irn) << PRIO_LEVEL)
+ + (get_irn_num_user(be, irn) << PRIO_NUMSUCCS)
+ - (get_irn_etime(be, irn) << PRIO_TIME)
+// - ((get_irn_reg_diff(be, irn) >> PRIO_CHG_PRESS) << ((cur_pressure >> PRIO_CUR_PRESS) - 3))
+ - reg_fact
+ + (get_irn_preorder(be, irn) << PRIO_PREORD); /* high preorder means early schedule */
+ if (cur_prio > max_prio) {
+ cand = irn;
+ max_prio = cur_prio;
+ cand_reg_fact = reg_fact;
+ }
+
+ DBG((be->dbg, LEVEL_4, "checked NODE %+F\n", irn));
+ DBG((be->dbg, LEVEL_4, "\tpriority: %d\n", cur_prio));
+ DBG((be->dbg, LEVEL_4, "\tpath len: %d (%d)\n", get_irn_critical_path_len(be, irn), get_irn_critical_path_len(be, irn) << PRIO_LEVEL));
+ DBG((be->dbg, LEVEL_4, "\tdelay: %d (%d)\n", get_irn_delay(be, irn), get_irn_delay(be, irn) << PRIO_LEVEL));
+ DBG((be->dbg, LEVEL_4, "\t#user: %d (%d)\n", get_irn_num_user(be, irn), get_irn_num_user(be, irn) << PRIO_NUMSUCCS));
+ DBG((be->dbg, LEVEL_4, "\tetime: %d (%d)\n", get_irn_etime(be, irn), -(get_irn_etime(be, irn) << PRIO_TIME)));
+ DBG((be->dbg, LEVEL_4, "\tpreorder: %d (%d)\n", get_irn_preorder(be, irn), get_irn_preorder(be, irn) << PRIO_PREORD));
+ DBG((be->dbg, LEVEL_4, "\treg diff: %d (%d)\n", get_irn_reg_diff(be, irn), -cand_reg_fact));
+ DBG((be->dbg, LEVEL_4, "\tpressure: %d\n", cur_pressure));
+ }
+ }
+
+ if (cand) {
+ DBG((be->dbg, LEVEL_4, "heuristic selected %+F:\n", cand));
+ }
+ else {
+ cand = nodeset_first(ns);
+ }
+ }
+ else {
+ /* use backend selector */
+ cand = be->selector->select(be->selector_block_env, ns);
+ }
+
+ return cand;
+}
+
+/**
+ * Returns non-zero if root is a root in the block block.
+ */
+static int is_root(ir_node *root, ir_node *block) {
+ const ir_edge_t *edge;
+
+ foreach_out_edge(root, edge) {
+ ir_node *succ = get_edge_src_irn(edge);
+
+ if (is_Block(succ))
+ continue;
+ /* Phi nodes are always in "another block */
+ if (is_Phi(succ))
+ continue;
+ if (get_nodes_block(succ) == block)
+ return 0;
+ }
+ return 1;
+}
+
+/* we need a special mark */
+static char _mark;
+#define MARK &_mark
+
+static firm_dbg_module_t *xxxdbg;
+
+/**
+ * descent into a dag and create a pre-order list.
+ */
+static void descent(ir_node *root, ir_node *block, ir_node **list, block_sched_env_t *env, unsigned path_len) {
+ int i;
+
+ if (! is_Phi(root)) {
+ path_len += exectime(env->sched_env, root);
+ if (get_irn_critical_path_len(env, root) < path_len) {
+ set_irn_critical_path_len(env, root, path_len);
+ }
+
+ /* Phi nodes always leave the block */
+ for (i = get_irn_arity(root) - 1; i >= 0; --i) {
+ ir_node *pred = get_irn_n(root, i);
+
+ DBG((xxxdbg, LEVEL_3, " node %+F\n", pred));
+ /* Blocks may happen as predecessors of End nodes */
+ if (is_Block(pred))
+ continue;
+
+ /* already seen nodes are not marked */
+ if (get_irn_link(pred) != MARK)
+ continue;
+
+ /* don't leave our block */
+ if (get_nodes_block(pred) != block)
+ continue;
+
+ set_irn_link(pred, NULL);
+
+ descent(pred, block, list, env, path_len);
+ }
+ }
+ set_irn_link(root, *list);
+ *list = root;
+}
+