#include "config.h"
#endif
+#include <stdlib.h>
+
#include "pset.h"
#include "impl.h"
#include "irmode.h"
#include "irdom.h"
+#include "bera.h"
+#include "beutil.h"
#include "besched_t.h"
#include "belive_t.h"
+#include "bemodule.h"
+
+be_ra_timer_t *global_ra_timer = NULL;
-static INLINE int values_interfere_dom(const ir_node *a, const ir_node *b)
+static sched_timestep_t get_time_step(const ir_node *irn)
{
- const ir_node *b1 = get_nodes_block(a);
- const ir_node *b2 = get_nodes_block(b);
- int lo_a, lo_b;
+ if(is_Phi(irn))
+ return 0;
+
+ return sched_get_time_step(irn);
+}
- assert(block_dominates(b1, b2));
+int value_dominates(const ir_node *a, const ir_node *b)
+{
+ int res = 0;
+ const ir_node *ba = get_block(a);
+ const ir_node *bb = get_block(b);
/*
- * if the two blocks are not equal, a and b can only interfere if a is
- * live in at b2.
+ * a and b are not in the same block,
+ * so dominance is determined by the dominance of the blocks.
*/
- if(b1 != b2 && !is_live_in(b2, a))
- return 0;
-
- lo_a = is_live_end(b2, a);
- lo_b = is_live_end(b2, b);
+ if(ba != bb) {
+ res = block_dominates(ba, bb);
/*
- * If the two blocks are the same and one value is live out and the
- * definition of the other is after the definition ov the live out
- * value, they interfere.
+ * Dominance is determined by the time steps of the schedule.
*/
- if(b1 == b2) {
- int pos_a = sched_get_time_step(a);
- int pos_b = sched_get_time_step(b);
-
- if((pos_a < pos_b && lo_a) || (pos_b < pos_a && lo_b))
- return 1;
+ } else {
+ sched_timestep_t as = get_time_step(a);
+ sched_timestep_t bs = get_time_step(b);
+ res = as <= bs;
}
- /*
- * Now it is left to check, if the sequence from the last use of 'b'
- * (or the end of the block b2, if b is live out)
- * to the def of 'b' contains a use and NOT the def of 'a'. Then they
- * also interfere
- */
- {
- const ir_node *irn;
-
- /* Initialize the liveness. */
- int a_live = lo_a;
- int b_live = lo_b;
-
- /* Go from the end of block b2 and try to detect the liveness. */
- sched_foreach_reverse(b2, irn) {
- int i, n;
-
- /*
- * If the definition of 'a' was found 'a' and 'b' interfere, if
- * 'b' is live here.
- */
- if(irn == a)
- return b_live;
-
- /* Same goes for 'b'. */
- if(irn == b)
- return a_live;
-
- /* If 'a' is not yet live, search for a use. */
- if(!a_live) {
- for(i = 0, n = get_irn_arity(irn); i < n; ++i)
- if(get_irn_n(irn, i) == a) {
- a_live = 1;
- break;
- }
- }
-
- /* Same for 'b' */
- if(!b_live) {
- for(i = 0, n = get_irn_arity(irn); i < n; ++i)
- if(get_irn_n(irn, i) == b) {
- b_live = 1;
- break;
- }
- }
+ return res;
+}
+/**
+ * Check, if two values interfere.
+ * @param a The first value.
+ * @param b The second value.
+ * @return 1, if a and b interfere, 0 if not.
+ */
+int values_interfere(const be_lv_t *lv, const ir_node *a, const ir_node *b)
+{
+ int a2b = value_dominates(a, b);
+ int b2a = value_dominates(b, a);
+
+ /* If there is no dominance relation, they do not interfere. */
+ if((a2b | b2a) > 0) {
+ const ir_edge_t *edge;
+ ir_node *bb;
+
+ /*
+ * Adjust a and b so, that a dominates b if
+ * a dominates b or vice versa.
+ */
+ if(b2a) {
+ const ir_node *t = a;
+ a = b;
+ b = t;
}
- }
- assert(0 && "You may never reach this place");
+ bb = get_nodes_block(b);
+
+ /*
+ * If a is live end in b's block it is
+ * live at b's definition (a dominates b)
+ */
+ if(be_is_live_end(lv, bb, a))
+ return 1;
+
+ /*
+ * Look at all usages of a.
+ * If there's one usage of a in the block of b, then
+ * we check, if this use is dominated by b, if that's true
+ * a and b interfere. Note that b must strictly dominate the user,
+ * since if b is the last user of in the block, b and a do not
+ * interfere.
+ * Uses of a not in b's block can be disobeyed, because the
+ * check for a being live at the end of b's block is already
+ * performed.
+ */
+ foreach_out_edge(a, edge) {
+ const ir_node *user = get_edge_src_irn(edge);
+ if(get_nodes_block(user) == bb && !is_Phi(user) && b != user && value_dominates(b, user))
+ return 1;
+ }
+ }
- /* This is never reached */
return 0;
}
-int values_interfere(const ir_node *a, const ir_node *b)
+/** The list of register allocators */
+static be_module_list_entry_t *register_allocators = NULL;
+static be_ra_t *selected_allocator = NULL;
+
+void be_register_allocator(const char *name, be_ra_t *allocator)
{
- const ir_node *b1 = get_nodes_block(a);
- const ir_node *b2 = get_nodes_block(b);
-
- if(block_dominates(b1, b2))
- return values_interfere_dom(a, b);
- else if(block_dominates(b2, b1))
- return values_interfere_dom(b, a);
- else
- return 0;
+ if(selected_allocator == NULL)
+ selected_allocator = allocator;
+ be_add_module_to_list(®ister_allocators, name, allocator);
+}
+
+void be_allocate_registers(be_irg_t *birg)
+{
+ assert(selected_allocator != NULL);
+ if(selected_allocator != NULL) {
+ selected_allocator->allocate(birg);
+ }
+}
+
+void be_init_ra(void)
+{
+ lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
+
+ be_add_module_list_opt(be_grp, "regalloc", "register allocator",
+ ®ister_allocators, (void**) &selected_allocator);
}
+BE_REGISTER_MODULE_CONSTRUCTOR(init_be_ra);
projects / libfirm / blobdiff