+ i = find_rhs_use(state, entry->member, ins);
+ if (i < 0) {
+ continue;
+ }
+ rinfo = arch_reg_rhs(state, entry->member, i);
+ if ((info.reg == REG_UNNEEDED) && (rinfo.reg == REG_UNNEEDED)) {
+ continue;
+ }
+ replace_rhs_use(state, ins, out, entry->member);
+ }
+ transform_to_arch_instruction(state, out);
+ return out;
+}
+
+static struct triple *typed_pre_copy(
+ struct compile_state *state, struct type *type, struct triple *ins, int index)
+{
+ /* Carefully insert enough operations so that I can
+ * enter any operation with a GPR32.
+ */
+ struct triple *in;
+ struct triple **expr;
+ unsigned classes;
+ struct reg_info info;
+ int op;
+ if (ins->op == OP_PHI) {
+ internal_error(state, ins, "pre_copy on a phi?");
+ }
+ classes = arch_type_to_regcm(state, type);
+ info = arch_reg_rhs(state, ins, index);
+ expr = &RHS(ins, index);
+ if ((info.regcm & classes) == 0) {
+ FILE *fp = state->errout;
+ fprintf(fp, "src_type: ");
+ name_of(fp, ins->type);
+ fprintf(fp, "\ndst_type: ");
+ name_of(fp, type);
+ fprintf(fp, "\n");
+ internal_error(state, ins, "pre_copy with no register classes");
+ }
+ op = OP_COPY;
+ if (!equiv_types(type, (*expr)->type)) {
+ op = OP_CONVERT;
+ }
+ in = pre_triple(state, ins, op, type, *expr, 0);
+ unuse_triple(*expr, ins);
+ *expr = in;
+ use_triple(RHS(in, 0), in);
+ use_triple(in, ins);
+ transform_to_arch_instruction(state, in);
+ return in;
+
+}
+static struct triple *pre_copy(
+ struct compile_state *state, struct triple *ins, int index)
+{
+ return typed_pre_copy(state, RHS(ins, index)->type, ins, index);
+}
+
+
+static void insert_copies_to_phi(struct compile_state *state)
+{
+ /* To get out of ssa form we insert moves on the incoming
+ * edges to blocks containting phi functions.
+ */
+ struct triple *first;
+ struct triple *phi;
+
+ /* Walk all of the operations to find the phi functions */
+ first = state->first;
+ for(phi = first->next; phi != first ; phi = phi->next) {
+ struct block_set *set;
+ struct block *block;
+ struct triple **slot, *copy;
+ int edge;
+ if (phi->op != OP_PHI) {
+ continue;
+ }
+ phi->id |= TRIPLE_FLAG_POST_SPLIT;
+ block = phi->u.block;
+ slot = &RHS(phi, 0);
+ /* Phi's that feed into mandatory live range joins
+ * cause nasty complications. Insert a copy of
+ * the phi value so I never have to deal with
+ * that in the rest of the code.
+ */
+ copy = post_copy(state, phi);
+ copy->id |= TRIPLE_FLAG_PRE_SPLIT;
+ /* Walk all of the incoming edges/blocks and insert moves.
+ */
+ for(edge = 0, set = block->use; set; set = set->next, edge++) {
+ struct block *eblock;
+ struct triple *move;
+ struct triple *val;
+ struct triple *ptr;
+ eblock = set->member;
+ val = slot[edge];
+
+ if (val == phi) {
+ continue;
+ }
+
+ get_occurance(val->occurance);
+ move = build_triple(state, OP_COPY, val->type, val, 0,
+ val->occurance);
+ move->u.block = eblock;
+ move->id |= TRIPLE_FLAG_PRE_SPLIT;
+ use_triple(val, move);
+
+ slot[edge] = move;
+ unuse_triple(val, phi);
+ use_triple(move, phi);
+
+ /* Walk up the dominator tree until I have found the appropriate block */
+ while(eblock && !tdominates(state, val, eblock->last)) {
+ eblock = eblock->idom;
+ }
+ if (!eblock) {
+ internal_error(state, phi, "Cannot find block dominated by %p",
+ val);
+ }
+
+ /* Walk through the block backwards to find
+ * an appropriate location for the OP_COPY.
+ */
+ for(ptr = eblock->last; ptr != eblock->first; ptr = ptr->prev) {
+ struct triple **expr;
+ if (ptr->op == OP_PIECE) {
+ ptr = MISC(ptr, 0);
+ }
+ if ((ptr == phi) || (ptr == val)) {
+ goto out;
+ }
+ expr = triple_lhs(state, ptr, 0);
+ for(;expr; expr = triple_lhs(state, ptr, expr)) {
+ if ((*expr) == val) {
+ goto out;
+ }
+ }
+ expr = triple_rhs(state, ptr, 0);
+ for(;expr; expr = triple_rhs(state, ptr, expr)) {
+ if ((*expr) == phi) {
+ goto out;
+ }
+ }
+ }
+ out:
+ if (triple_is_branch(state, ptr)) {
+ internal_error(state, ptr,
+ "Could not insert write to phi");
+ }
+ insert_triple(state, after_lhs(state, ptr), move);
+ if (eblock->last == after_lhs(state, ptr)->prev) {
+ eblock->last = move;
+ }
+ transform_to_arch_instruction(state, move);
+ }
+ }
+ print_blocks(state, __func__, state->dbgout);
+}
+
+struct triple_reg_set;
+struct reg_block;
+
+
+static int do_triple_set(struct triple_reg_set **head,
+ struct triple *member, struct triple *new_member)
+{
+ struct triple_reg_set **ptr, *new;
+ if (!member)
+ return 0;
+ ptr = head;
+ while(*ptr) {
+ if ((*ptr)->member == member) {
+ return 0;
+ }
+ ptr = &(*ptr)->next;
+ }
+ new = xcmalloc(sizeof(*new), "triple_set");
+ new->member = member;
+ new->new = new_member;
+ new->next = *head;
+ *head = new;
+ return 1;
+}
+
+static void do_triple_unset(struct triple_reg_set **head, struct triple *member)
+{
+ struct triple_reg_set *entry, **ptr;
+ ptr = head;
+ while(*ptr) {
+ entry = *ptr;
+ if (entry->member == member) {
+ *ptr = entry->next;
+ xfree(entry);
+ return;
+ }
+ else {
+ ptr = &entry->next;
+ }
+ }
+}
+
+static int in_triple(struct reg_block *rb, struct triple *in)
+{
+ return do_triple_set(&rb->in, in, 0);
+}
+
+#if DEBUG_ROMCC_WARNING
+static void unin_triple(struct reg_block *rb, struct triple *unin)
+{
+ do_triple_unset(&rb->in, unin);
+}
+#endif
+
+static int out_triple(struct reg_block *rb, struct triple *out)
+{
+ return do_triple_set(&rb->out, out, 0);
+}
+#if DEBUG_ROMCC_WARNING
+static void unout_triple(struct reg_block *rb, struct triple *unout)
+{
+ do_triple_unset(&rb->out, unout);
+}
+#endif
+
+static int initialize_regblock(struct reg_block *blocks,
+ struct block *block, int vertex)
+{
+ struct block_set *user;
+ if (!block || (blocks[block->vertex].block == block)) {
+ return vertex;
+ }
+ vertex += 1;
+ /* Renumber the blocks in a convinient fashion */
+ block->vertex = vertex;
+ blocks[vertex].block = block;
+ blocks[vertex].vertex = vertex;
+ for(user = block->use; user; user = user->next) {
+ vertex = initialize_regblock(blocks, user->member, vertex);
+ }
+ return vertex;
+}
+
+static struct triple *part_to_piece(struct compile_state *state, struct triple *ins)
+{
+/* Part to piece is a best attempt and it cannot be correct all by
+ * itself. If various values are read as different sizes in different
+ * parts of the code this function cannot work. Or rather it cannot
+ * work in conjunction with compute_variable_liftimes. As the
+ * analysis will get confused.
+ */
+ struct triple *base;
+ unsigned reg;
+ if (!is_lvalue(state, ins)) {
+ return ins;
+ }
+ base = 0;
+ reg = 0;
+ while(ins && triple_is_part(state, ins) && (ins->op != OP_PIECE)) {
+ base = MISC(ins, 0);
+ switch(ins->op) {
+ case OP_INDEX:
+ reg += index_reg_offset(state, base->type, ins->u.cval)/REG_SIZEOF_REG;
+ break;
+ case OP_DOT:
+ reg += field_reg_offset(state, base->type, ins->u.field)/REG_SIZEOF_REG;
+ break;
+ default:
+ internal_error(state, ins, "unhandled part");
+ break;
+ }
+ ins = base;
+ }
+ if (base) {
+ if (reg > base->lhs) {
+ internal_error(state, base, "part out of range?");
+ }
+ ins = LHS(base, reg);
+ }
+ return ins;
+}
+
+static int this_def(struct compile_state *state,
+ struct triple *ins, struct triple *other)
+{
+ if (ins == other) {
+ return 1;
+ }
+ if (ins->op == OP_WRITE) {
+ ins = part_to_piece(state, MISC(ins, 0));
+ }
+ return ins == other;
+}
+
+static int phi_in(struct compile_state *state, struct reg_block *blocks,
+ struct reg_block *rb, struct block *suc)
+{
+ /* Read the conditional input set of a successor block
+ * (i.e. the input to the phi nodes) and place it in the
+ * current blocks output set.
+ */
+ struct block_set *set;
+ struct triple *ptr;
+ int edge;
+ int done, change;
+ change = 0;
+ /* Find the edge I am coming in on */
+ for(edge = 0, set = suc->use; set; set = set->next, edge++) {
+ if (set->member == rb->block) {
+ break;
+ }
+ }
+ if (!set) {
+ internal_error(state, 0, "Not coming on a control edge?");
+ }
+ for(done = 0, ptr = suc->first; !done; ptr = ptr->next) {
+ struct triple **slot, *expr, *ptr2;
+ int out_change, done2;
+ done = (ptr == suc->last);
+ if (ptr->op != OP_PHI) {
+ continue;
+ }
+ slot = &RHS(ptr, 0);
+ expr = slot[edge];
+ out_change = out_triple(rb, expr);
+ if (!out_change) {
+ continue;
+ }
+ /* If we don't define the variable also plast it
+ * in the current blocks input set.
+ */
+ ptr2 = rb->block->first;
+ for(done2 = 0; !done2; ptr2 = ptr2->next) {
+ if (this_def(state, ptr2, expr)) {
+ break;
+ }
+ done2 = (ptr2 == rb->block->last);
+ }
+ if (!done2) {
+ continue;
+ }
+ change |= in_triple(rb, expr);
+ }
+ return change;
+}
+
+static int reg_in(struct compile_state *state, struct reg_block *blocks,
+ struct reg_block *rb, struct block *suc)
+{
+ struct triple_reg_set *in_set;
+ int change;
+ change = 0;
+ /* Read the input set of a successor block
+ * and place it in the current blocks output set.
+ */
+ in_set = blocks[suc->vertex].in;
+ for(; in_set; in_set = in_set->next) {
+ int out_change, done;
+ struct triple *first, *last, *ptr;
+ out_change = out_triple(rb, in_set->member);
+ if (!out_change) {
+ continue;
+ }
+ /* If we don't define the variable also place it
+ * in the current blocks input set.
+ */
+ first = rb->block->first;
+ last = rb->block->last;
+ done = 0;
+ for(ptr = first; !done; ptr = ptr->next) {
+ if (this_def(state, ptr, in_set->member)) {
+ break;
+ }
+ done = (ptr == last);
+ }
+ if (!done) {
+ continue;
+ }
+ change |= in_triple(rb, in_set->member);
+ }
+ change |= phi_in(state, blocks, rb, suc);
+ return change;
+}
+
+static int use_in(struct compile_state *state, struct reg_block *rb)
+{
+ /* Find the variables we use but don't define and add
+ * it to the current blocks input set.
+ */
+#if DEBUG_ROMCC_WARNINGS
+#warning "FIXME is this O(N^2) algorithm bad?"
+#endif
+ struct block *block;
+ struct triple *ptr;
+ int done;
+ int change;
+ block = rb->block;
+ change = 0;
+ for(done = 0, ptr = block->last; !done; ptr = ptr->prev) {
+ struct triple **expr;
+ done = (ptr == block->first);
+ /* The variable a phi function uses depends on the
+ * control flow, and is handled in phi_in, not
+ * here.
+ */
+ if (ptr->op == OP_PHI) {
+ continue;
+ }
+ expr = triple_rhs(state, ptr, 0);
+ for(;expr; expr = triple_rhs(state, ptr, expr)) {
+ struct triple *rhs, *test;
+ int tdone;
+ rhs = part_to_piece(state, *expr);
+ if (!rhs) {
+ continue;
+ }
+
+ /* See if rhs is defined in this block.
+ * A write counts as a definition.
+ */
+ for(tdone = 0, test = ptr; !tdone; test = test->prev) {
+ tdone = (test == block->first);
+ if (this_def(state, test, rhs)) {
+ rhs = 0;
+ break;
+ }
+ }
+ /* If I still have a valid rhs add it to in */
+ change |= in_triple(rb, rhs);
+ }
+ }
+ return change;
+}
+
+static struct reg_block *compute_variable_lifetimes(
+ struct compile_state *state, struct basic_blocks *bb)
+{
+ struct reg_block *blocks;
+ int change;
+ blocks = xcmalloc(
+ sizeof(*blocks)*(bb->last_vertex + 1), "reg_block");
+ initialize_regblock(blocks, bb->last_block, 0);
+ do {
+ int i;
+ change = 0;
+ for(i = 1; i <= bb->last_vertex; i++) {
+ struct block_set *edge;
+ struct reg_block *rb;
+ rb = &blocks[i];
+ /* Add the all successor's input set to in */
+ for(edge = rb->block->edges; edge; edge = edge->next) {
+ change |= reg_in(state, blocks, rb, edge->member);
+ }
+ /* Add use to in... */
+ change |= use_in(state, rb);
+ }
+ } while(change);
+ return blocks;
+}
+
+static void free_variable_lifetimes(struct compile_state *state,
+ struct basic_blocks *bb, struct reg_block *blocks)
+{
+ int i;
+ /* free in_set && out_set on each block */
+ for(i = 1; i <= bb->last_vertex; i++) {
+ struct triple_reg_set *entry, *next;
+ struct reg_block *rb;
+ rb = &blocks[i];
+ for(entry = rb->in; entry ; entry = next) {
+ next = entry->next;
+ do_triple_unset(&rb->in, entry->member);
+ }
+ for(entry = rb->out; entry; entry = next) {
+ next = entry->next;
+ do_triple_unset(&rb->out, entry->member);
+ }
+ }
+ xfree(blocks);
+
+}
+
+typedef void (*wvl_cb_t)(
+ struct compile_state *state,
+ struct reg_block *blocks, struct triple_reg_set *live,
+ struct reg_block *rb, struct triple *ins, void *arg);
+
+static void walk_variable_lifetimes(struct compile_state *state,
+ struct basic_blocks *bb, struct reg_block *blocks,
+ wvl_cb_t cb, void *arg)
+{
+ int i;
+
+ for(i = 1; i <= state->bb.last_vertex; i++) {
+ struct triple_reg_set *live;
+ struct triple_reg_set *entry, *next;
+ struct triple *ptr, *prev;
+ struct reg_block *rb;
+ struct block *block;
+ int done;
+
+ /* Get the blocks */
+ rb = &blocks[i];
+ block = rb->block;
+
+ /* Copy out into live */
+ live = 0;
+ for(entry = rb->out; entry; entry = next) {
+ next = entry->next;
+ do_triple_set(&live, entry->member, entry->new);
+ }
+ /* Walk through the basic block calculating live */
+ for(done = 0, ptr = block->last; !done; ptr = prev) {
+ struct triple **expr;
+
+ prev = ptr->prev;
+ done = (ptr == block->first);
+
+ /* Ensure the current definition is in live */
+ if (triple_is_def(state, ptr)) {
+ do_triple_set(&live, ptr, 0);
+ }
+
+ /* Inform the callback function of what is
+ * going on.
+ */
+ cb(state, blocks, live, rb, ptr, arg);
+
+ /* Remove the current definition from live */
+ do_triple_unset(&live, ptr);
+
+ /* Add the current uses to live.
+ *
+ * It is safe to skip phi functions because they do
+ * not have any block local uses, and the block
+ * output sets already properly account for what
+ * control flow depedent uses phi functions do have.
+ */
+ if (ptr->op == OP_PHI) {
+ continue;
+ }
+ expr = triple_rhs(state, ptr, 0);
+ for(;expr; expr = triple_rhs(state, ptr, expr)) {
+ /* If the triple is not a definition skip it. */
+ if (!*expr || !triple_is_def(state, *expr)) {
+ continue;
+ }
+ do_triple_set(&live, *expr, 0);
+ }
+ }
+ /* Free live */
+ for(entry = live; entry; entry = next) {
+ next = entry->next;
+ do_triple_unset(&live, entry->member);
+ }
+ }
+}
+
+struct print_live_variable_info {
+ struct reg_block *rb;
+ FILE *fp;
+};
+#if DEBUG_EXPLICIT_CLOSURES
+static void print_live_variables_block(
+ struct compile_state *state, struct block *block, void *arg)
+
+{
+ struct print_live_variable_info *info = arg;
+ struct block_set *edge;
+ FILE *fp = info->fp;
+ struct reg_block *rb;
+ struct triple *ptr;
+ int phi_present;
+ int done;
+ rb = &info->rb[block->vertex];
+
+ fprintf(fp, "\nblock: %p (%d),",
+ block, block->vertex);
+ for(edge = block->edges; edge; edge = edge->next) {
+ fprintf(fp, " %p<-%p",
+ edge->member,
+ edge->member && edge->member->use?edge->member->use->member : 0);
+ }
+ fprintf(fp, "\n");
+ if (rb->in) {
+ struct triple_reg_set *in_set;
+ fprintf(fp, " in:");
+ for(in_set = rb->in; in_set; in_set = in_set->next) {
+ fprintf(fp, " %-10p", in_set->member);
+ }
+ fprintf(fp, "\n");
+ }
+ phi_present = 0;
+ for(done = 0, ptr = block->first; !done; ptr = ptr->next) {
+ done = (ptr == block->last);
+ if (ptr->op == OP_PHI) {
+ phi_present = 1;
+ break;
+ }
+ }
+ if (phi_present) {
+ int edge;
+ for(edge = 0; edge < block->users; edge++) {
+ fprintf(fp, " in(%d):", edge);
+ for(done = 0, ptr = block->first; !done; ptr = ptr->next) {
+ struct triple **slot;
+ done = (ptr == block->last);
+ if (ptr->op != OP_PHI) {
+ continue;
+ }
+ slot = &RHS(ptr, 0);
+ fprintf(fp, " %-10p", slot[edge]);
+ }
+ fprintf(fp, "\n");
+ }
+ }
+ if (block->first->op == OP_LABEL) {
+ fprintf(fp, "%p:\n", block->first);
+ }
+ for(done = 0, ptr = block->first; !done; ptr = ptr->next) {
+ done = (ptr == block->last);
+ display_triple(fp, ptr);
+ }
+ if (rb->out) {
+ struct triple_reg_set *out_set;
+ fprintf(fp, " out:");
+ for(out_set = rb->out; out_set; out_set = out_set->next) {
+ fprintf(fp, " %-10p", out_set->member);
+ }
+ fprintf(fp, "\n");
+ }
+ fprintf(fp, "\n");
+}
+
+static void print_live_variables(struct compile_state *state,
+ struct basic_blocks *bb, struct reg_block *rb, FILE *fp)
+{
+ struct print_live_variable_info info;
+ info.rb = rb;
+ info.fp = fp;
+ fprintf(fp, "\nlive variables by block\n");
+ walk_blocks(state, bb, print_live_variables_block, &info);
+
+}
+#endif
+
+static int count_triples(struct compile_state *state)
+{
+ struct triple *first, *ins;
+ int triples = 0;
+ first = state->first;
+ ins = first;
+ do {
+ triples++;
+ ins = ins->next;
+ } while (ins != first);
+ return triples;
+}
+
+
+struct dead_triple {
+ struct triple *triple;
+ struct dead_triple *work_next;
+ struct block *block;
+ int old_id;
+ int flags;
+#define TRIPLE_FLAG_ALIVE 1
+#define TRIPLE_FLAG_FREE 1
+};
+
+static void print_dead_triples(struct compile_state *state,
+ struct dead_triple *dtriple)
+{
+ struct triple *first, *ins;
+ struct dead_triple *dt;
+ FILE *fp;
+ if (!(state->compiler->debug & DEBUG_TRIPLES)) {
+ return;
+ }
+ fp = state->dbgout;
+ fprintf(fp, "--------------- dtriples ---------------\n");
+ first = state->first;
+ ins = first;
+ do {
+ dt = &dtriple[ins->id];
+ if ((ins->op == OP_LABEL) && (ins->use)) {
+ fprintf(fp, "\n%p:\n", ins);
+ }
+ fprintf(fp, "%c",
+ (dt->flags & TRIPLE_FLAG_ALIVE)?' ': '-');
+ display_triple(fp, ins);
+ if (triple_is_branch(state, ins)) {
+ fprintf(fp, "\n");
+ }
+ ins = ins->next;
+ } while(ins != first);
+ fprintf(fp, "\n");
+}
+
+
+static void awaken(
+ struct compile_state *state,
+ struct dead_triple *dtriple, struct triple **expr,
+ struct dead_triple ***work_list_tail)
+{
+ struct triple *triple;
+ struct dead_triple *dt;
+ if (!expr) {
+ return;
+ }
+ triple = *expr;
+ if (!triple) {
+ return;
+ }
+ if (triple->id <= 0) {
+ internal_error(state, triple, "bad triple id: %d",
+ triple->id);
+ }
+ if (triple->op == OP_NOOP) {
+ internal_error(state, triple, "awakening noop?");
+ return;
+ }
+ dt = &dtriple[triple->id];
+ if (!(dt->flags & TRIPLE_FLAG_ALIVE)) {
+ dt->flags |= TRIPLE_FLAG_ALIVE;
+ if (!dt->work_next) {
+ **work_list_tail = dt;
+ *work_list_tail = &dt->work_next;
+ }
+ }
+}
+
+static void eliminate_inefectual_code(struct compile_state *state)
+{
+ struct dead_triple *dtriple, *work_list, **work_list_tail, *dt;
+ int triples, i;
+ struct triple *first, *ins;
+
+ if (!(state->compiler->flags & COMPILER_ELIMINATE_INEFECTUAL_CODE)) {
+ return;
+ }
+
+ /* Setup the work list */
+ work_list = 0;
+ work_list_tail = &work_list;
+
+ first = state->first;
+
+ /* Count how many triples I have */
+ triples = count_triples(state);
+
+ /* Now put then in an array and mark all of the triples dead */
+ dtriple = xcmalloc(sizeof(*dtriple) * (triples + 1), "dtriples");
+
+ ins = first;
+ i = 1;
+ do {
+ dtriple[i].triple = ins;
+ dtriple[i].block = block_of_triple(state, ins);
+ dtriple[i].flags = 0;
+ dtriple[i].old_id = ins->id;
+ ins->id = i;
+ /* See if it is an operation we always keep */
+ if (!triple_is_pure(state, ins, dtriple[i].old_id)) {
+ awaken(state, dtriple, &ins, &work_list_tail);
+ }
+ i++;
+ ins = ins->next;
+ } while(ins != first);
+ while(work_list) {
+ struct block *block;
+ struct dead_triple *dt;
+ struct block_set *user;
+ struct triple **expr;
+ dt = work_list;
+ work_list = dt->work_next;
+ if (!work_list) {
+ work_list_tail = &work_list;
+ }
+ /* Make certain the block the current instruction is in lives */
+ block = block_of_triple(state, dt->triple);
+ awaken(state, dtriple, &block->first, &work_list_tail);
+ if (triple_is_branch(state, block->last)) {
+ awaken(state, dtriple, &block->last, &work_list_tail);
+ } else {
+ awaken(state, dtriple, &block->last->next, &work_list_tail);
+ }
+
+ /* Wake up the data depencencies of this triple */
+ expr = 0;
+ do {
+ expr = triple_rhs(state, dt->triple, expr);
+ awaken(state, dtriple, expr, &work_list_tail);
+ } while(expr);
+ do {
+ expr = triple_lhs(state, dt->triple, expr);
+ awaken(state, dtriple, expr, &work_list_tail);
+ } while(expr);
+ do {
+ expr = triple_misc(state, dt->triple, expr);
+ awaken(state, dtriple, expr, &work_list_tail);
+ } while(expr);
+ /* Wake up the forward control dependencies */
+ do {
+ expr = triple_targ(state, dt->triple, expr);
+ awaken(state, dtriple, expr, &work_list_tail);
+ } while(expr);
+ /* Wake up the reverse control dependencies of this triple */
+ for(user = dt->block->ipdomfrontier; user; user = user->next) {
+ struct triple *last;
+ last = user->member->last;
+ while((last->op == OP_NOOP) && (last != user->member->first)) {
+#if DEBUG_ROMCC_WARNINGS
+#warning "Should we bring the awakening noops back?"
+#endif
+ // internal_warning(state, last, "awakening noop?");
+ last = last->prev;
+ }
+ awaken(state, dtriple, &last, &work_list_tail);
+ }
+ }
+ print_dead_triples(state, dtriple);
+ for(dt = &dtriple[1]; dt <= &dtriple[triples]; dt++) {
+ if ((dt->triple->op == OP_NOOP) &&
+ (dt->flags & TRIPLE_FLAG_ALIVE)) {
+ internal_error(state, dt->triple, "noop effective?");
+ }
+ dt->triple->id = dt->old_id; /* Restore the color */
+ if (!(dt->flags & TRIPLE_FLAG_ALIVE)) {
+ release_triple(state, dt->triple);
+ }
+ }
+ xfree(dtriple);
+
+ rebuild_ssa_form(state);
+
+ print_blocks(state, __func__, state->dbgout);
+}
+
+
+static void insert_mandatory_copies(struct compile_state *state)
+{
+ struct triple *ins, *first;
+
+ /* The object is with a minimum of inserted copies,
+ * to resolve in fundamental register conflicts between
+ * register value producers and consumers.
+ * Theoretically we may be greater than minimal when we
+ * are inserting copies before instructions but that
+ * case should be rare.
+ */
+ first = state->first;
+ ins = first;
+ do {
+ struct triple_set *entry, *next;
+ struct triple *tmp;
+ struct reg_info info;
+ unsigned reg, regcm;
+ int do_post_copy, do_pre_copy;
+ tmp = 0;
+ if (!triple_is_def(state, ins)) {
+ goto next;
+ }
+ /* Find the architecture specific color information */
+ info = find_lhs_pre_color(state, ins, 0);
+ if (info.reg >= MAX_REGISTERS) {
+ info.reg = REG_UNSET;
+ }
+
+ reg = REG_UNSET;
+ regcm = arch_type_to_regcm(state, ins->type);
+ do_post_copy = do_pre_copy = 0;
+
+ /* Walk through the uses of ins and check for conflicts */
+ for(entry = ins->use; entry; entry = next) {
+ struct reg_info rinfo;
+ int i;
+ next = entry->next;
+ i = find_rhs_use(state, entry->member, ins);
+ if (i < 0) {
+ continue;
+ }
+
+ /* Find the users color requirements */
+ rinfo = arch_reg_rhs(state, entry->member, i);
+ if (rinfo.reg >= MAX_REGISTERS) {
+ rinfo.reg = REG_UNSET;
+ }
+
+ /* See if I need a pre_copy */
+ if (rinfo.reg != REG_UNSET) {
+ if ((reg != REG_UNSET) && (reg != rinfo.reg)) {
+ do_pre_copy = 1;
+ }
+ reg = rinfo.reg;
+ }
+ regcm &= rinfo.regcm;
+ regcm = arch_regcm_normalize(state, regcm);
+ if (regcm == 0) {
+ do_pre_copy = 1;
+ }
+ /* Always use pre_copies for constants.
+ * They do not take up any registers until a
+ * copy places them in one.
+ */
+ if ((info.reg == REG_UNNEEDED) &&
+ (rinfo.reg != REG_UNNEEDED)) {
+ do_pre_copy = 1;
+ }
+ }
+ do_post_copy =
+ !do_pre_copy &&
+ (((info.reg != REG_UNSET) &&
+ (reg != REG_UNSET) &&
+ (info.reg != reg)) ||
+ ((info.regcm & regcm) == 0));
+
+ reg = info.reg;
+ regcm = info.regcm;
+ /* Walk through the uses of ins and do a pre_copy or see if a post_copy is warranted */
+ for(entry = ins->use; entry; entry = next) {
+ struct reg_info rinfo;
+ int i;
+ next = entry->next;
+ i = find_rhs_use(state, entry->member, ins);
+ if (i < 0) {
+ continue;
+ }
+
+ /* Find the users color requirements */
+ rinfo = arch_reg_rhs(state, entry->member, i);
+ if (rinfo.reg >= MAX_REGISTERS) {
+ rinfo.reg = REG_UNSET;
+ }
+
+ /* Now see if it is time to do the pre_copy */
+ if (rinfo.reg != REG_UNSET) {
+ if (((reg != REG_UNSET) && (reg != rinfo.reg)) ||
+ ((regcm & rinfo.regcm) == 0) ||
+ /* Don't let a mandatory coalesce sneak
+ * into a operation that is marked to prevent
+ * coalescing.
+ */
+ ((reg != REG_UNNEEDED) &&
+ ((ins->id & TRIPLE_FLAG_POST_SPLIT) ||
+ (entry->member->id & TRIPLE_FLAG_PRE_SPLIT)))
+ ) {
+ if (do_pre_copy) {
+ struct triple *user;
+ user = entry->member;
+ if (RHS(user, i) != ins) {
+ internal_error(state, user, "bad rhs");
+ }
+ tmp = pre_copy(state, user, i);
+ tmp->id |= TRIPLE_FLAG_PRE_SPLIT;
+ continue;
+ } else {
+ do_post_copy = 1;
+ }
+ }
+ reg = rinfo.reg;
+ }
+ if ((regcm & rinfo.regcm) == 0) {
+ if (do_pre_copy) {
+ struct triple *user;
+ user = entry->member;
+ if (RHS(user, i) != ins) {
+ internal_error(state, user, "bad rhs");
+ }
+ tmp = pre_copy(state, user, i);
+ tmp->id |= TRIPLE_FLAG_PRE_SPLIT;
+ continue;
+ } else {
+ do_post_copy = 1;
+ }
+ }
+ regcm &= rinfo.regcm;
+
+ }
+ if (do_post_copy) {
+ struct reg_info pre, post;
+ tmp = post_copy(state, ins);
+ tmp->id |= TRIPLE_FLAG_PRE_SPLIT;
+ pre = arch_reg_lhs(state, ins, 0);
+ post = arch_reg_lhs(state, tmp, 0);
+ if ((pre.reg == post.reg) && (pre.regcm == post.regcm)) {
+ internal_error(state, tmp, "useless copy");
+ }
+ }
+ next:
+ ins = ins->next;
+ } while(ins != first);
+
+ print_blocks(state, __func__, state->dbgout);
+}
+
+
+struct live_range_edge;
+struct live_range_def;
+struct live_range {
+ struct live_range_edge *edges;
+ struct live_range_def *defs;
+/* Note. The list pointed to by defs is kept in order.
+ * That is baring splits in the flow control
+ * defs dominates defs->next wich dominates defs->next->next
+ * etc.
+ */
+ unsigned color;
+ unsigned classes;
+ unsigned degree;
+ unsigned length;
+ struct live_range *group_next, **group_prev;
+};
+
+struct live_range_edge {
+ struct live_range_edge *next;
+ struct live_range *node;
+};
+
+struct live_range_def {
+ struct live_range_def *next;
+ struct live_range_def *prev;
+ struct live_range *lr;
+ struct triple *def;
+ unsigned orig_id;
+};
+
+#define LRE_HASH_SIZE 2048
+struct lre_hash {
+ struct lre_hash *next;
+ struct live_range *left;
+ struct live_range *right;
+};
+
+
+struct reg_state {
+ struct lre_hash *hash[LRE_HASH_SIZE];
+ struct reg_block *blocks;
+ struct live_range_def *lrd;
+ struct live_range *lr;
+ struct live_range *low, **low_tail;
+ struct live_range *high, **high_tail;
+ unsigned defs;
+ unsigned ranges;
+ int passes, max_passes;
+};
+
+
+struct print_interference_block_info {
+ struct reg_state *rstate;
+ FILE *fp;
+ int need_edges;
+};
+static void print_interference_block(
+ struct compile_state *state, struct block *block, void *arg)
+
+{
+ struct print_interference_block_info *info = arg;
+ struct reg_state *rstate = info->rstate;
+ struct block_set *edge;
+ FILE *fp = info->fp;
+ struct reg_block *rb;
+ struct triple *ptr;
+ int phi_present;
+ int done;
+ rb = &rstate->blocks[block->vertex];
+
+ fprintf(fp, "\nblock: %p (%d),",
+ block, block->vertex);
+ for(edge = block->edges; edge; edge = edge->next) {
+ fprintf(fp, " %p<-%p",
+ edge->member,
+ edge->member && edge->member->use?edge->member->use->member : 0);
+ }
+ fprintf(fp, "\n");
+ if (rb->in) {
+ struct triple_reg_set *in_set;
+ fprintf(fp, " in:");
+ for(in_set = rb->in; in_set; in_set = in_set->next) {
+ fprintf(fp, " %-10p", in_set->member);
+ }
+ fprintf(fp, "\n");
+ }
+ phi_present = 0;
+ for(done = 0, ptr = block->first; !done; ptr = ptr->next) {
+ done = (ptr == block->last);
+ if (ptr->op == OP_PHI) {
+ phi_present = 1;
+ break;
+ }
+ }
+ if (phi_present) {
+ int edge;
+ for(edge = 0; edge < block->users; edge++) {
+ fprintf(fp, " in(%d):", edge);
+ for(done = 0, ptr = block->first; !done; ptr = ptr->next) {
+ struct triple **slot;
+ done = (ptr == block->last);
+ if (ptr->op != OP_PHI) {
+ continue;
+ }
+ slot = &RHS(ptr, 0);
+ fprintf(fp, " %-10p", slot[edge]);
+ }
+ fprintf(fp, "\n");
+ }
+ }
+ if (block->first->op == OP_LABEL) {
+ fprintf(fp, "%p:\n", block->first);
+ }
+ for(done = 0, ptr = block->first; !done; ptr = ptr->next) {
+ struct live_range *lr;
+ unsigned id;
+ done = (ptr == block->last);
+ lr = rstate->lrd[ptr->id].lr;
+
+ id = ptr->id;
+ ptr->id = rstate->lrd[id].orig_id;
+ SET_REG(ptr->id, lr->color);
+ display_triple(fp, ptr);
+ ptr->id = id;
+
+ if (triple_is_def(state, ptr) && (lr->defs == 0)) {
+ internal_error(state, ptr, "lr has no defs!");
+ }
+ if (info->need_edges) {
+ if (lr->defs) {
+ struct live_range_def *lrd;
+ fprintf(fp, " range:");
+ lrd = lr->defs;
+ do {
+ fprintf(fp, " %-10p", lrd->def);
+ lrd = lrd->next;
+ } while(lrd != lr->defs);
+ fprintf(fp, "\n");
+ }
+ if (lr->edges > 0) {
+ struct live_range_edge *edge;
+ fprintf(fp, " edges:");
+ for(edge = lr->edges; edge; edge = edge->next) {
+ struct live_range_def *lrd;
+ lrd = edge->node->defs;
+ do {
+ fprintf(fp, " %-10p", lrd->def);
+ lrd = lrd->next;
+ } while(lrd != edge->node->defs);
+ fprintf(fp, "|");
+ }
+ fprintf(fp, "\n");
+ }
+ }
+ /* Do a bunch of sanity checks */
+ valid_ins(state, ptr);
+ if ((ptr->id < 0) || (ptr->id > rstate->defs)) {
+ internal_error(state, ptr, "Invalid triple id: %d",
+ ptr->id);
+ }
+ }
+ if (rb->out) {
+ struct triple_reg_set *out_set;
+ fprintf(fp, " out:");
+ for(out_set = rb->out; out_set; out_set = out_set->next) {
+ fprintf(fp, " %-10p", out_set->member);
+ }
+ fprintf(fp, "\n");
+ }
+ fprintf(fp, "\n");
+}
+
+static void print_interference_blocks(
+ struct compile_state *state, struct reg_state *rstate, FILE *fp, int need_edges)
+{
+ struct print_interference_block_info info;
+ info.rstate = rstate;
+ info.fp = fp;
+ info.need_edges = need_edges;
+ fprintf(fp, "\nlive variables by block\n");
+ walk_blocks(state, &state->bb, print_interference_block, &info);
+
+}
+
+static unsigned regc_max_size(struct compile_state *state, int classes)
+{
+ unsigned max_size;
+ int i;
+ max_size = 0;
+ for(i = 0; i < MAX_REGC; i++) {
+ if (classes & (1 << i)) {
+ unsigned size;
+ size = arch_regc_size(state, i);
+ if (size > max_size) {
+ max_size = size;
+ }
+ }
+ }
+ return max_size;
+}
+
+static int reg_is_reg(struct compile_state *state, int reg1, int reg2)
+{
+ unsigned equivs[MAX_REG_EQUIVS];
+ int i;
+ if ((reg1 < 0) || (reg1 >= MAX_REGISTERS)) {
+ internal_error(state, 0, "invalid register");
+ }
+ if ((reg2 < 0) || (reg2 >= MAX_REGISTERS)) {
+ internal_error(state, 0, "invalid register");
+ }
+ arch_reg_equivs(state, equivs, reg1);
+ for(i = 0; (i < MAX_REG_EQUIVS) && equivs[i] != REG_UNSET; i++) {
+ if (equivs[i] == reg2) {
+ return 1;
+ }
+ }
+ return 0;
+}
+
+static void reg_fill_used(struct compile_state *state, char *used, int reg)
+{
+ unsigned equivs[MAX_REG_EQUIVS];
+ int i;
+ if (reg == REG_UNNEEDED) {
+ return;
+ }
+ arch_reg_equivs(state, equivs, reg);
+ for(i = 0; (i < MAX_REG_EQUIVS) && equivs[i] != REG_UNSET; i++) {
+ used[equivs[i]] = 1;
+ }
+ return;
+}
+
+static void reg_inc_used(struct compile_state *state, char *used, int reg)
+{
+ unsigned equivs[MAX_REG_EQUIVS];
+ int i;
+ if (reg == REG_UNNEEDED) {
+ return;
+ }
+ arch_reg_equivs(state, equivs, reg);
+ for(i = 0; (i < MAX_REG_EQUIVS) && equivs[i] != REG_UNSET; i++) {
+ used[equivs[i]] += 1;
+ }
+ return;
+}
+
+static unsigned int hash_live_edge(
+ struct live_range *left, struct live_range *right)
+{
+ unsigned int hash, val;
+ unsigned long lval, rval;
+ lval = ((unsigned long)left)/sizeof(struct live_range);
+ rval = ((unsigned long)right)/sizeof(struct live_range);
+ hash = 0;
+ while(lval) {
+ val = lval & 0xff;
+ lval >>= 8;
+ hash = (hash *263) + val;
+ }
+ while(rval) {
+ val = rval & 0xff;
+ rval >>= 8;
+ hash = (hash *263) + val;
+ }
+ hash = hash & (LRE_HASH_SIZE - 1);
+ return hash;
+}
+
+static struct lre_hash **lre_probe(struct reg_state *rstate,
+ struct live_range *left, struct live_range *right)
+{
+ struct lre_hash **ptr;
+ unsigned int index;
+ /* Ensure left <= right */
+ if (left > right) {
+ struct live_range *tmp;
+ tmp = left;
+ left = right;
+ right = tmp;
+ }
+ index = hash_live_edge(left, right);
+
+ ptr = &rstate->hash[index];
+ while(*ptr) {
+ if (((*ptr)->left == left) && ((*ptr)->right == right)) {
+ break;
+ }
+ ptr = &(*ptr)->next;
+ }
+ return ptr;
+}
+
+static int interfere(struct reg_state *rstate,
+ struct live_range *left, struct live_range *right)
+{
+ struct lre_hash **ptr;
+ ptr = lre_probe(rstate, left, right);
+ return ptr && *ptr;
+}
+
+static void add_live_edge(struct reg_state *rstate,
+ struct live_range *left, struct live_range *right)
+{
+ /* FIXME the memory allocation overhead is noticeable here... */
+ struct lre_hash **ptr, *new_hash;
+ struct live_range_edge *edge;
+
+ if (left == right) {
+ return;
+ }
+ if ((left == &rstate->lr[0]) || (right == &rstate->lr[0])) {
+ return;
+ }
+ /* Ensure left <= right */
+ if (left > right) {
+ struct live_range *tmp;
+ tmp = left;
+ left = right;
+ right = tmp;
+ }
+ ptr = lre_probe(rstate, left, right);
+ if (*ptr) {
+ return;
+ }
+#if 0
+ fprintf(state->errout, "new_live_edge(%p, %p)\n",
+ left, right);
+#endif
+ new_hash = xmalloc(sizeof(*new_hash), "lre_hash");
+ new_hash->next = *ptr;
+ new_hash->left = left;
+ new_hash->right = right;
+ *ptr = new_hash;
+
+ edge = xmalloc(sizeof(*edge), "live_range_edge");
+ edge->next = left->edges;
+ edge->node = right;
+ left->edges = edge;
+ left->degree += 1;
+
+ edge = xmalloc(sizeof(*edge), "live_range_edge");
+ edge->next = right->edges;
+ edge->node = left;
+ right->edges = edge;
+ right->degree += 1;
+}
+
+static void remove_live_edge(struct reg_state *rstate,
+ struct live_range *left, struct live_range *right)
+{
+ struct live_range_edge *edge, **ptr;
+ struct lre_hash **hptr, *entry;
+ hptr = lre_probe(rstate, left, right);
+ if (!hptr || !*hptr) {
+ return;
+ }
+ entry = *hptr;
+ *hptr = entry->next;
+ xfree(entry);
+
+ for(ptr = &left->edges; *ptr; ptr = &(*ptr)->next) {
+ edge = *ptr;
+ if (edge->node == right) {
+ *ptr = edge->next;
+ memset(edge, 0, sizeof(*edge));
+ xfree(edge);
+ right->degree--;
+ break;
+ }
+ }
+ for(ptr = &right->edges; *ptr; ptr = &(*ptr)->next) {
+ edge = *ptr;
+ if (edge->node == left) {
+ *ptr = edge->next;
+ memset(edge, 0, sizeof(*edge));
+ xfree(edge);
+ left->degree--;
+ break;
+ }
+ }
+}
+
+static void remove_live_edges(struct reg_state *rstate, struct live_range *range)
+{
+ struct live_range_edge *edge, *next;
+ for(edge = range->edges; edge; edge = next) {
+ next = edge->next;
+ remove_live_edge(rstate, range, edge->node);
+ }
+}
+
+static void transfer_live_edges(struct reg_state *rstate,
+ struct live_range *dest, struct live_range *src)
+{
+ struct live_range_edge *edge, *next;
+ for(edge = src->edges; edge; edge = next) {
+ struct live_range *other;
+ next = edge->next;
+ other = edge->node;
+ remove_live_edge(rstate, src, other);
+ add_live_edge(rstate, dest, other);
+ }
+}
+
+
+/* Interference graph...
+ *
+ * new(n) --- Return a graph with n nodes but no edges.
+ * add(g,x,y) --- Return a graph including g with an between x and y
+ * interfere(g, x, y) --- Return true if there exists an edge between the nodes
+ * x and y in the graph g
+ * degree(g, x) --- Return the degree of the node x in the graph g
+ * neighbors(g, x, f) --- Apply function f to each neighbor of node x in the graph g
+ *
+ * Implement with a hash table && a set of adjcency vectors.
+ * The hash table supports constant time implementations of add and interfere.
+ * The adjacency vectors support an efficient implementation of neighbors.
+ */
+
+/*
+ * +---------------------------------------------------+
+ * | +--------------+ |
+ * v v | |
+ * renumber -> build graph -> colalesce -> spill_costs -> simplify -> select
+ *
+ * -- In simplify implment optimistic coloring... (No backtracking)
+ * -- Implement Rematerialization it is the only form of spilling we can perform
+ * Essentially this means dropping a constant from a register because
+ * we can regenerate it later.
+ *
+ * --- Very conservative colalescing (don't colalesce just mark the opportunities)
+ * coalesce at phi points...
+ * --- Bias coloring if at all possible do the coalesing a compile time.
+ *
+ *
+ */
+
+#if DEBUG_ROMCC_WARNING
+static void different_colored(
+ struct compile_state *state, struct reg_state *rstate,
+ struct triple *parent, struct triple *ins)
+{
+ struct live_range *lr;
+ struct triple **expr;
+ lr = rstate->lrd[ins->id].lr;
+ expr = triple_rhs(state, ins, 0);
+ for(;expr; expr = triple_rhs(state, ins, expr)) {
+ struct live_range *lr2;
+ if (!*expr || (*expr == parent) || (*expr == ins)) {
+ continue;
+ }
+ lr2 = rstate->lrd[(*expr)->id].lr;
+ if (lr->color == lr2->color) {
+ internal_error(state, ins, "live range too big");
+ }
+ }
+}
+#endif
+
+static struct live_range *coalesce_ranges(
+ struct compile_state *state, struct reg_state *rstate,
+ struct live_range *lr1, struct live_range *lr2)
+{
+ struct live_range_def *head, *mid1, *mid2, *end, *lrd;
+ unsigned color;
+ unsigned classes;
+ if (lr1 == lr2) {
+ return lr1;
+ }
+ if (!lr1->defs || !lr2->defs) {
+ internal_error(state, 0,
+ "cannot coalese dead live ranges");
+ }
+ if ((lr1->color == REG_UNNEEDED) ||
+ (lr2->color == REG_UNNEEDED)) {
+ internal_error(state, 0,
+ "cannot coalesce live ranges without a possible color");
+ }
+ if ((lr1->color != lr2->color) &&
+ (lr1->color != REG_UNSET) &&
+ (lr2->color != REG_UNSET)) {
+ internal_error(state, lr1->defs->def,
+ "cannot coalesce live ranges of different colors");
+ }
+ color = lr1->color;
+ if (color == REG_UNSET) {
+ color = lr2->color;
+ }
+ classes = lr1->classes & lr2->classes;
+ if (!classes) {
+ internal_error(state, lr1->defs->def,
+ "cannot coalesce live ranges with dissimilar register classes");
+ }
+ if (state->compiler->debug & DEBUG_COALESCING) {
+ FILE *fp = state->errout;
+ fprintf(fp, "coalescing:");
+ lrd = lr1->defs;
+ do {
+ fprintf(fp, " %p", lrd->def);
+ lrd = lrd->next;
+ } while(lrd != lr1->defs);
+ fprintf(fp, " |");
+ lrd = lr2->defs;
+ do {
+ fprintf(fp, " %p", lrd->def);
+ lrd = lrd->next;
+ } while(lrd != lr2->defs);
+ fprintf(fp, "\n");
+ }
+ /* If there is a clear dominate live range put it in lr1,
+ * For purposes of this test phi functions are
+ * considered dominated by the definitions that feed into
+ * them.
+ */
+ if ((lr1->defs->prev->def->op == OP_PHI) ||
+ ((lr2->defs->prev->def->op != OP_PHI) &&
+ tdominates(state, lr2->defs->def, lr1->defs->def))) {
+ struct live_range *tmp;
+ tmp = lr1;
+ lr1 = lr2;
+ lr2 = tmp;
+ }
+#if 0
+ if (lr1->defs->orig_id & TRIPLE_FLAG_POST_SPLIT) {
+ fprintf(state->errout, "lr1 post\n");
+ }
+ if (lr1->defs->orig_id & TRIPLE_FLAG_PRE_SPLIT) {
+ fprintf(state->errout, "lr1 pre\n");
+ }
+ if (lr2->defs->orig_id & TRIPLE_FLAG_POST_SPLIT) {
+ fprintf(state->errout, "lr2 post\n");
+ }
+ if (lr2->defs->orig_id & TRIPLE_FLAG_PRE_SPLIT) {
+ fprintf(state->errout, "lr2 pre\n");
+ }
+#endif
+#if 0
+ fprintf(state->errout, "coalesce color1(%p): %3d color2(%p) %3d\n",
+ lr1->defs->def,
+ lr1->color,
+ lr2->defs->def,
+ lr2->color);
+#endif
+
+ /* Append lr2 onto lr1 */
+#if DEBUG_ROMCC_WARNINGS
+#warning "FIXME should this be a merge instead of a splice?"
+#endif
+ /* This FIXME item applies to the correctness of live_range_end
+ * and to the necessity of making multiple passes of coalesce_live_ranges.
+ * A failure to find some coalesce opportunities in coaleace_live_ranges
+ * does not impact the correct of the compiler just the efficiency with
+ * which registers are allocated.
+ */
+ head = lr1->defs;
+ mid1 = lr1->defs->prev;
+ mid2 = lr2->defs;
+ end = lr2->defs->prev;
+
+ head->prev = end;
+ end->next = head;
+
+ mid1->next = mid2;
+ mid2->prev = mid1;
+
+ /* Fixup the live range in the added live range defs */
+ lrd = head;
+ do {
+ lrd->lr = lr1;
+ lrd = lrd->next;
+ } while(lrd != head);
+
+ /* Mark lr2 as free. */
+ lr2->defs = 0;
+ lr2->color = REG_UNNEEDED;
+ lr2->classes = 0;
+
+ if (!lr1->defs) {
+ internal_error(state, 0, "lr1->defs == 0 ?");
+ }
+
+ lr1->color = color;
+ lr1->classes = classes;
+
+ /* Keep the graph in sync by transfering the edges from lr2 to lr1 */
+ transfer_live_edges(rstate, lr1, lr2);
+
+ return lr1;
+}
+
+static struct live_range_def *live_range_head(
+ struct compile_state *state, struct live_range *lr,
+ struct live_range_def *last)
+{
+ struct live_range_def *result;
+ result = 0;
+ if (last == 0) {
+ result = lr->defs;
+ }
+ else if (!tdominates(state, lr->defs->def, last->next->def)) {
+ result = last->next;
+ }
+ return result;
+}
+
+static struct live_range_def *live_range_end(
+ struct compile_state *state, struct live_range *lr,
+ struct live_range_def *last)
+{
+ struct live_range_def *result;
+ result = 0;
+ if (last == 0) {
+ result = lr->defs->prev;
+ }
+ else if (!tdominates(state, last->prev->def, lr->defs->prev->def)) {
+ result = last->prev;
+ }
+ return result;
+}
+
+
+static void initialize_live_ranges(
+ struct compile_state *state, struct reg_state *rstate)
+{
+ struct triple *ins, *first;
+ size_t count, size;
+ int i, j;
+
+ first = state->first;
+ /* First count how many instructions I have.
+ */
+ count = count_triples(state);
+ /* Potentially I need one live range definitions for each
+ * instruction.
+ */
+ rstate->defs = count;
+ /* Potentially I need one live range for each instruction
+ * plus an extra for the dummy live range.
+ */
+ rstate->ranges = count + 1;
+ size = sizeof(rstate->lrd[0]) * rstate->defs;
+ rstate->lrd = xcmalloc(size, "live_range_def");
+ size = sizeof(rstate->lr[0]) * rstate->ranges;
+ rstate->lr = xcmalloc(size, "live_range");
+
+ /* Setup the dummy live range */
+ rstate->lr[0].classes = 0;
+ rstate->lr[0].color = REG_UNSET;
+ rstate->lr[0].defs = 0;
+ i = j = 0;
+ ins = first;
+ do {
+ /* If the triple is a variable give it a live range */
+ if (triple_is_def(state, ins)) {
+ struct reg_info info;
+ /* Find the architecture specific color information */
+ info = find_def_color(state, ins);
+ i++;
+ rstate->lr[i].defs = &rstate->lrd[j];
+ rstate->lr[i].color = info.reg;
+ rstate->lr[i].classes = info.regcm;
+ rstate->lr[i].degree = 0;
+ rstate->lrd[j].lr = &rstate->lr[i];
+ }
+ /* Otherwise give the triple the dummy live range. */
+ else {
+ rstate->lrd[j].lr = &rstate->lr[0];
+ }
+
+ /* Initalize the live_range_def */
+ rstate->lrd[j].next = &rstate->lrd[j];
+ rstate->lrd[j].prev = &rstate->lrd[j];
+ rstate->lrd[j].def = ins;
+ rstate->lrd[j].orig_id = ins->id;
+ ins->id = j;
+
+ j++;
+ ins = ins->next;
+ } while(ins != first);
+ rstate->ranges = i;
+
+ /* Make a second pass to handle achitecture specific register
+ * constraints.
+ */
+ ins = first;
+ do {
+ int zlhs, zrhs, i, j;
+ if (ins->id > rstate->defs) {
+ internal_error(state, ins, "bad id");
+ }
+
+ /* Walk through the template of ins and coalesce live ranges */
+ zlhs = ins->lhs;
+ if ((zlhs == 0) && triple_is_def(state, ins)) {
+ zlhs = 1;
+ }
+ zrhs = ins->rhs;
+
+ if (state->compiler->debug & DEBUG_COALESCING2) {
+ fprintf(state->errout, "mandatory coalesce: %p %d %d\n",
+ ins, zlhs, zrhs);
+ }
+
+ for(i = 0; i < zlhs; i++) {
+ struct reg_info linfo;
+ struct live_range_def *lhs;
+ linfo = arch_reg_lhs(state, ins, i);
+ if (linfo.reg < MAX_REGISTERS) {
+ continue;
+ }
+ if (triple_is_def(state, ins)) {
+ lhs = &rstate->lrd[ins->id];
+ } else {
+ lhs = &rstate->lrd[LHS(ins, i)->id];
+ }
+
+ if (state->compiler->debug & DEBUG_COALESCING2) {
+ fprintf(state->errout, "coalesce lhs(%d): %p %d\n",
+ i, lhs, linfo.reg);
+ }
+
+ for(j = 0; j < zrhs; j++) {
+ struct reg_info rinfo;
+ struct live_range_def *rhs;
+ rinfo = arch_reg_rhs(state, ins, j);
+ if (rinfo.reg < MAX_REGISTERS) {
+ continue;
+ }
+ rhs = &rstate->lrd[RHS(ins, j)->id];
+
+ if (state->compiler->debug & DEBUG_COALESCING2) {
+ fprintf(state->errout, "coalesce rhs(%d): %p %d\n",
+ j, rhs, rinfo.reg);
+ }
+
+ if (rinfo.reg == linfo.reg) {
+ coalesce_ranges(state, rstate,
+ lhs->lr, rhs->lr);
+ }
+ }
+ }
+ ins = ins->next;
+ } while(ins != first);
+}
+
+static void graph_ins(
+ struct compile_state *state,
+ struct reg_block *blocks, struct triple_reg_set *live,
+ struct reg_block *rb, struct triple *ins, void *arg)
+{
+ struct reg_state *rstate = arg;
+ struct live_range *def;
+ struct triple_reg_set *entry;
+
+ /* If the triple is not a definition
+ * we do not have a definition to add to
+ * the interference graph.
+ */
+ if (!triple_is_def(state, ins)) {
+ return;
+ }
+ def = rstate->lrd[ins->id].lr;
+
+ /* Create an edge between ins and everything that is
+ * alive, unless the live_range cannot share
+ * a physical register with ins.
+ */
+ for(entry = live; entry; entry = entry->next) {
+ struct live_range *lr;
+ if ((entry->member->id < 0) || (entry->member->id > rstate->defs)) {
+ internal_error(state, 0, "bad entry?");
+ }
+ lr = rstate->lrd[entry->member->id].lr;
+ if (def == lr) {
+ continue;
+ }
+ if (!arch_regcm_intersect(def->classes, lr->classes)) {
+ continue;
+ }
+ add_live_edge(rstate, def, lr);
+ }
+ return;
+}
+
+#if DEBUG_CONSISTENCY > 1
+static struct live_range *get_verify_live_range(
+ struct compile_state *state, struct reg_state *rstate, struct triple *ins)
+{
+ struct live_range *lr;
+ struct live_range_def *lrd;
+ int ins_found;
+ if ((ins->id < 0) || (ins->id > rstate->defs)) {
+ internal_error(state, ins, "bad ins?");
+ }
+ lr = rstate->lrd[ins->id].lr;
+ ins_found = 0;
+ lrd = lr->defs;
+ do {
+ if (lrd->def == ins) {
+ ins_found = 1;
+ }
+ lrd = lrd->next;
+ } while(lrd != lr->defs);
+ if (!ins_found) {
+ internal_error(state, ins, "ins not in live range");
+ }
+ return lr;
+}
+
+static void verify_graph_ins(
+ struct compile_state *state,
+ struct reg_block *blocks, struct triple_reg_set *live,
+ struct reg_block *rb, struct triple *ins, void *arg)
+{
+ struct reg_state *rstate = arg;
+ struct triple_reg_set *entry1, *entry2;
+
+
+ /* Compare live against edges and make certain the code is working */
+ for(entry1 = live; entry1; entry1 = entry1->next) {
+ struct live_range *lr1;
+ lr1 = get_verify_live_range(state, rstate, entry1->member);
+ for(entry2 = live; entry2; entry2 = entry2->next) {
+ struct live_range *lr2;
+ struct live_range_edge *edge2;
+ int lr1_found;
+ int lr2_degree;
+ if (entry2 == entry1) {
+ continue;
+ }
+ lr2 = get_verify_live_range(state, rstate, entry2->member);
+ if (lr1 == lr2) {
+ internal_error(state, entry2->member,
+ "live range with 2 values simultaneously alive");
+ }
+ if (!arch_regcm_intersect(lr1->classes, lr2->classes)) {
+ continue;
+ }
+ if (!interfere(rstate, lr1, lr2)) {
+ internal_error(state, entry2->member,
+ "edges don't interfere?");
+ }
+
+ lr1_found = 0;
+ lr2_degree = 0;
+ for(edge2 = lr2->edges; edge2; edge2 = edge2->next) {
+ lr2_degree++;
+ if (edge2->node == lr1) {
+ lr1_found = 1;
+ }
+ }
+ if (lr2_degree != lr2->degree) {
+ internal_error(state, entry2->member,
+ "computed degree: %d does not match reported degree: %d\n",
+ lr2_degree, lr2->degree);
+ }
+ if (!lr1_found) {
+ internal_error(state, entry2->member, "missing edge");
+ }
+ }
+ }
+ return;
+}
+#endif
+
+static void print_interference_ins(
+ struct compile_state *state,
+ struct reg_block *blocks, struct triple_reg_set *live,
+ struct reg_block *rb, struct triple *ins, void *arg)
+{
+ struct reg_state *rstate = arg;
+ struct live_range *lr;
+ unsigned id;
+ FILE *fp = state->dbgout;
+
+ lr = rstate->lrd[ins->id].lr;
+ id = ins->id;
+ ins->id = rstate->lrd[id].orig_id;
+ SET_REG(ins->id, lr->color);
+ display_triple(state->dbgout, ins);
+ ins->id = id;
+
+ if (lr->defs) {
+ struct live_range_def *lrd;
+ fprintf(fp, " range:");
+ lrd = lr->defs;
+ do {
+ fprintf(fp, " %-10p", lrd->def);
+ lrd = lrd->next;
+ } while(lrd != lr->defs);
+ fprintf(fp, "\n");
+ }
+ if (live) {
+ struct triple_reg_set *entry;
+ fprintf(fp, " live:");
+ for(entry = live; entry; entry = entry->next) {
+ fprintf(fp, " %-10p", entry->member);
+ }
+ fprintf(fp, "\n");
+ }
+ if (lr->edges) {
+ struct live_range_edge *entry;
+ fprintf(fp, " edges:");
+ for(entry = lr->edges; entry; entry = entry->next) {
+ struct live_range_def *lrd;
+ lrd = entry->node->defs;
+ do {
+ fprintf(fp, " %-10p", lrd->def);
+ lrd = lrd->next;
+ } while(lrd != entry->node->defs);
+ fprintf(fp, "|");
+ }
+ fprintf(fp, "\n");
+ }
+ if (triple_is_branch(state, ins)) {
+ fprintf(fp, "\n");
+ }
+ return;
+}
+
+static int coalesce_live_ranges(
+ struct compile_state *state, struct reg_state *rstate)
+{
+ /* At the point where a value is moved from one
+ * register to another that value requires two
+ * registers, thus increasing register pressure.
+ * Live range coaleescing reduces the register
+ * pressure by keeping a value in one register
+ * longer.
+ *
+ * In the case of a phi function all paths leading
+ * into it must be allocated to the same register
+ * otherwise the phi function may not be removed.
+ *
+ * Forcing a value to stay in a single register
+ * for an extended period of time does have
+ * limitations when applied to non homogenous
+ * register pool.
+ *
+ * The two cases I have identified are:
+ * 1) Two forced register assignments may
+ * collide.
+ * 2) Registers may go unused because they
+ * are only good for storing the value
+ * and not manipulating it.
+ *
+ * Because of this I need to split live ranges,
+ * even outside of the context of coalesced live
+ * ranges. The need to split live ranges does
+ * impose some constraints on live range coalescing.
+ *
+ * - Live ranges may not be coalesced across phi
+ * functions. This creates a 2 headed live
+ * range that cannot be sanely split.
+ *
+ * - phi functions (coalesced in initialize_live_ranges)
+ * are handled as pre split live ranges so we will
+ * never attempt to split them.
+ */
+ int coalesced;
+ int i;
+
+ coalesced = 0;
+ for(i = 0; i <= rstate->ranges; i++) {
+ struct live_range *lr1;
+ struct live_range_def *lrd1;
+ lr1 = &rstate->lr[i];
+ if (!lr1->defs) {
+ continue;
+ }
+ lrd1 = live_range_end(state, lr1, 0);
+ for(; lrd1; lrd1 = live_range_end(state, lr1, lrd1)) {
+ struct triple_set *set;
+ if (lrd1->def->op != OP_COPY) {
+ continue;
+ }
+ /* Skip copies that are the result of a live range split. */
+ if (lrd1->orig_id & TRIPLE_FLAG_POST_SPLIT) {
+ continue;
+ }
+ for(set = lrd1->def->use; set; set = set->next) {
+ struct live_range_def *lrd2;
+ struct live_range *lr2, *res;
+
+ lrd2 = &rstate->lrd[set->member->id];
+
+ /* Don't coalesce with instructions
+ * that are the result of a live range
+ * split.
+ */
+ if (lrd2->orig_id & TRIPLE_FLAG_PRE_SPLIT) {
+ continue;
+ }
+ lr2 = rstate->lrd[set->member->id].lr;
+ if (lr1 == lr2) {
+ continue;
+ }
+ if ((lr1->color != lr2->color) &&
+ (lr1->color != REG_UNSET) &&
+ (lr2->color != REG_UNSET)) {
+ continue;
+ }
+ if ((lr1->classes & lr2->classes) == 0) {
+ continue;
+ }
+
+ if (interfere(rstate, lr1, lr2)) {
+ continue;
+ }
+
+ res = coalesce_ranges(state, rstate, lr1, lr2);
+ coalesced += 1;
+ if (res != lr1) {
+ goto next;
+ }
+ }
+ }
+ next:
+ ;
+ }
+ return coalesced;
+}
+
+
+static void fix_coalesce_conflicts(struct compile_state *state,
+ struct reg_block *blocks, struct triple_reg_set *live,
+ struct reg_block *rb, struct triple *ins, void *arg)
+{
+ int *conflicts = arg;
+ int zlhs, zrhs, i, j;
+
+ /* See if we have a mandatory coalesce operation between
+ * a lhs and a rhs value. If so and the rhs value is also
+ * alive then this triple needs to be pre copied. Otherwise
+ * we would have two definitions in the same live range simultaneously
+ * alive.
+ */
+ zlhs = ins->lhs;
+ if ((zlhs == 0) && triple_is_def(state, ins)) {
+ zlhs = 1;
+ }
+ zrhs = ins->rhs;
+ for(i = 0; i < zlhs; i++) {
+ struct reg_info linfo;
+ linfo = arch_reg_lhs(state, ins, i);
+ if (linfo.reg < MAX_REGISTERS) {
+ continue;
+ }
+ for(j = 0; j < zrhs; j++) {
+ struct reg_info rinfo;
+ struct triple *rhs;
+ struct triple_reg_set *set;
+ int found;
+ found = 0;
+ rinfo = arch_reg_rhs(state, ins, j);
+ if (rinfo.reg != linfo.reg) {
+ continue;
+ }
+ rhs = RHS(ins, j);
+ for(set = live; set && !found; set = set->next) {
+ if (set->member == rhs) {
+ found = 1;
+ }
+ }
+ if (found) {
+ struct triple *copy;
+ copy = pre_copy(state, ins, j);
+ copy->id |= TRIPLE_FLAG_PRE_SPLIT;
+ (*conflicts)++;
+ }
+ }
+ }
+ return;
+}
+
+static int correct_coalesce_conflicts(
+ struct compile_state *state, struct reg_block *blocks)
+{
+ int conflicts;
+ conflicts = 0;
+ walk_variable_lifetimes(state, &state->bb, blocks,
+ fix_coalesce_conflicts, &conflicts);
+ return conflicts;
+}
+
+static void replace_set_use(struct compile_state *state,
+ struct triple_reg_set *head, struct triple *orig, struct triple *new)
+{
+ struct triple_reg_set *set;
+ for(set = head; set; set = set->next) {
+ if (set->member == orig) {
+ set->member = new;
+ }
+ }
+}
+
+static void replace_block_use(struct compile_state *state,
+ struct reg_block *blocks, struct triple *orig, struct triple *new)
+{
+ int i;
+#if DEBUG_ROMCC_WARNINGS
+#warning "WISHLIST visit just those blocks that need it *"
+#endif
+ for(i = 1; i <= state->bb.last_vertex; i++) {
+ struct reg_block *rb;
+ rb = &blocks[i];
+ replace_set_use(state, rb->in, orig, new);
+ replace_set_use(state, rb->out, orig, new);
+ }
+}
+
+static void color_instructions(struct compile_state *state)
+{
+ struct triple *ins, *first;
+ first = state->first;
+ ins = first;
+ do {
+ if (triple_is_def(state, ins)) {
+ struct reg_info info;
+ info = find_lhs_color(state, ins, 0);
+ if (info.reg >= MAX_REGISTERS) {
+ info.reg = REG_UNSET;
+ }
+ SET_INFO(ins->id, info);
+ }
+ ins = ins->next;
+ } while(ins != first);
+}
+
+static struct reg_info read_lhs_color(
+ struct compile_state *state, struct triple *ins, int index)
+{
+ struct reg_info info;
+ if ((index == 0) && triple_is_def(state, ins)) {
+ info.reg = ID_REG(ins->id);
+ info.regcm = ID_REGCM(ins->id);
+ }
+ else if (index < ins->lhs) {
+ info = read_lhs_color(state, LHS(ins, index), 0);
+ }
+ else {
+ internal_error(state, ins, "Bad lhs %d", index);
+ info.reg = REG_UNSET;
+ info.regcm = 0;
+ }
+ return info;
+}
+
+static struct triple *resolve_tangle(
+ struct compile_state *state, struct triple *tangle)
+{
+ struct reg_info info, uinfo;
+ struct triple_set *set, *next;
+ struct triple *copy;
+
+#if DEBUG_ROMCC_WARNINGS
+#warning "WISHLIST recalculate all affected instructions colors"
+#endif
+ info = find_lhs_color(state, tangle, 0);
+ for(set = tangle->use; set; set = next) {
+ struct triple *user;
+ int i, zrhs;
+ next = set->next;
+ user = set->member;
+ zrhs = user->rhs;
+ for(i = 0; i < zrhs; i++) {
+ if (RHS(user, i) != tangle) {
+ continue;
+ }
+ uinfo = find_rhs_post_color(state, user, i);
+ if (uinfo.reg == info.reg) {
+ copy = pre_copy(state, user, i);
+ copy->id |= TRIPLE_FLAG_PRE_SPLIT;
+ SET_INFO(copy->id, uinfo);
+ }
+ }
+ }
+ copy = 0;
+ uinfo = find_lhs_pre_color(state, tangle, 0);
+ if (uinfo.reg == info.reg) {
+ struct reg_info linfo;
+ copy = post_copy(state, tangle);
+ copy->id |= TRIPLE_FLAG_PRE_SPLIT;
+ linfo = find_lhs_color(state, copy, 0);
+ SET_INFO(copy->id, linfo);
+ }
+ info = find_lhs_color(state, tangle, 0);
+ SET_INFO(tangle->id, info);
+
+ return copy;
+}
+
+
+static void fix_tangles(struct compile_state *state,
+ struct reg_block *blocks, struct triple_reg_set *live,
+ struct reg_block *rb, struct triple *ins, void *arg)
+{
+ int *tangles = arg;
+ struct triple *tangle;
+ do {
+ char used[MAX_REGISTERS];
+ struct triple_reg_set *set;
+ tangle = 0;
+
+ /* Find out which registers have multiple uses at this point */
+ memset(used, 0, sizeof(used));
+ for(set = live; set; set = set->next) {
+ struct reg_info info;
+ info = read_lhs_color(state, set->member, 0);
+ if (info.reg == REG_UNSET) {
+ continue;
+ }
+ reg_inc_used(state, used, info.reg);
+ }
+
+ /* Now find the least dominated definition of a register in
+ * conflict I have seen so far.
+ */
+ for(set = live; set; set = set->next) {
+ struct reg_info info;
+ info = read_lhs_color(state, set->member, 0);
+ if (used[info.reg] < 2) {
+ continue;
+ }
+ /* Changing copies that feed into phi functions
+ * is incorrect.
+ */
+ if (set->member->use &&
+ (set->member->use->member->op == OP_PHI)) {
+ continue;
+ }
+ if (!tangle || tdominates(state, set->member, tangle)) {
+ tangle = set->member;
+ }
+ }
+ /* If I have found a tangle resolve it */
+ if (tangle) {
+ struct triple *post_copy;
+ (*tangles)++;
+ post_copy = resolve_tangle(state, tangle);
+ if (post_copy) {
+ replace_block_use(state, blocks, tangle, post_copy);
+ }
+ if (post_copy && (tangle != ins)) {
+ replace_set_use(state, live, tangle, post_copy);
+ }
+ }
+ } while(tangle);
+ return;
+}
+
+static int correct_tangles(
+ struct compile_state *state, struct reg_block *blocks)
+{
+ int tangles;
+ tangles = 0;
+ color_instructions(state);
+ walk_variable_lifetimes(state, &state->bb, blocks,
+ fix_tangles, &tangles);
+ return tangles;
+}
+
+
+static void ids_from_rstate(struct compile_state *state, struct reg_state *rstate);
+static void cleanup_rstate(struct compile_state *state, struct reg_state *rstate);
+
+struct triple *find_constrained_def(
+ struct compile_state *state, struct live_range *range, struct triple *constrained)
+{
+ struct live_range_def *lrd, *lrd_next;
+ lrd_next = range->defs;
+ do {
+ struct reg_info info;
+ unsigned regcm;
+
+ lrd = lrd_next;
+ lrd_next = lrd->next;
+
+ regcm = arch_type_to_regcm(state, lrd->def->type);
+ info = find_lhs_color(state, lrd->def, 0);
+ regcm = arch_regcm_reg_normalize(state, regcm);
+ info.regcm = arch_regcm_reg_normalize(state, info.regcm);
+ /* If the 2 register class masks are equal then
+ * the current register class is not constrained.
+ */
+ if (regcm == info.regcm) {
+ continue;
+ }
+
+ /* If there is just one use.
+ * That use cannot accept a larger register class.
+ * There are no intervening definitions except
+ * definitions that feed into that use.
+ * Then a triple is not constrained.
+ * FIXME handle this case!
+ */
+#if DEBUG_ROMCC_WARNINGS
+#warning "FIXME ignore cases that cannot be fixed (a definition followed by a use)"
+#endif
+
+
+ /* Of the constrained live ranges deal with the
+ * least dominated one first.
+ */
+ if (state->compiler->debug & DEBUG_RANGE_CONFLICTS) {
+ fprintf(state->errout, "canidate: %p %-8s regcm: %x %x\n",
+ lrd->def, tops(lrd->def->op), regcm, info.regcm);
+ }
+ if (!constrained ||
+ tdominates(state, lrd->def, constrained))
+ {
+ constrained = lrd->def;
+ }
+ } while(lrd_next != range->defs);
+ return constrained;
+}
+
+static int split_constrained_ranges(
+ struct compile_state *state, struct reg_state *rstate,
+ struct live_range *range)
+{
+ /* Walk through the edges in conflict and our current live
+ * range, and find definitions that are more severly constrained
+ * than they type of data they contain require.
+ *
+ * Then pick one of those ranges and relax the constraints.
+ */
+ struct live_range_edge *edge;
+ struct triple *constrained;
+
+ constrained = 0;
+ for(edge = range->edges; edge; edge = edge->next) {
+ constrained = find_constrained_def(state, edge->node, constrained);
+ }
+#if DEBUG_ROMCC_WARNINGS
+#warning "FIXME should I call find_constrained_def here only if no previous constrained def was found?"
+#endif
+ if (!constrained) {
+ constrained = find_constrained_def(state, range, constrained);
+ }
+
+ if (state->compiler->debug & DEBUG_RANGE_CONFLICTS) {
+ fprintf(state->errout, "constrained: ");
+ display_triple(state->errout, constrained);
+ }
+ if (constrained) {
+ ids_from_rstate(state, rstate);
+ cleanup_rstate(state, rstate);
+ resolve_tangle(state, constrained);
+ }
+ return !!constrained;
+}
+
+static int split_ranges(
+ struct compile_state *state, struct reg_state *rstate,
+ char *used, struct live_range *range)
+{
+ int split;
+ if (state->compiler->debug & DEBUG_RANGE_CONFLICTS) {
+ fprintf(state->errout, "split_ranges %d %s %p\n",
+ rstate->passes, tops(range->defs->def->op), range->defs->def);
+ }
+ if ((range->color == REG_UNNEEDED) ||
+ (rstate->passes >= rstate->max_passes)) {
+ return 0;
+ }
+ split = split_constrained_ranges(state, rstate, range);
+
+ /* Ideally I would split the live range that will not be used
+ * for the longest period of time in hopes that this will
+ * (a) allow me to spill a register or
+ * (b) allow me to place a value in another register.
+ *
+ * So far I don't have a test case for this, the resolving
+ * of mandatory constraints has solved all of my
+ * know issues. So I have choosen not to write any
+ * code until I cat get a better feel for cases where
+ * it would be useful to have.
+ *
+ */
+#if DEBUG_ROMCC_WARNINGS
+#warning "WISHLIST implement live range splitting..."
+#endif
+
+ if (!split && (state->compiler->debug & DEBUG_RANGE_CONFLICTS2)) {
+ FILE *fp = state->errout;
+ print_interference_blocks(state, rstate, fp, 0);
+ print_dominators(state, fp, &state->bb);
+ }
+ return split;
+}
+
+static FILE *cgdebug_fp(struct compile_state *state)
+{
+ FILE *fp;
+ fp = 0;
+ if (!fp && (state->compiler->debug & DEBUG_COLOR_GRAPH2)) {
+ fp = state->errout;
+ }
+ if (!fp && (state->compiler->debug & DEBUG_COLOR_GRAPH)) {
+ fp = state->dbgout;
+ }
+ return fp;
+}
+
+static void cgdebug_printf(struct compile_state *state, const char *fmt, ...)
+{
+ FILE *fp;
+ fp = cgdebug_fp(state);
+ if (fp) {
+ va_list args;
+ va_start(args, fmt);
+ vfprintf(fp, fmt, args);
+ va_end(args);
+ }
+}
+
+static void cgdebug_flush(struct compile_state *state)
+{
+ FILE *fp;
+ fp = cgdebug_fp(state);
+ if (fp) {
+ fflush(fp);
+ }
+}
+
+static void cgdebug_loc(struct compile_state *state, struct triple *ins)
+{
+ FILE *fp;
+ fp = cgdebug_fp(state);
+ if (fp) {
+ loc(fp, state, ins);
+ }
+}
+
+static int select_free_color(struct compile_state *state,
+ struct reg_state *rstate, struct live_range *range)
+{
+ struct triple_set *entry;
+ struct live_range_def *lrd;
+ struct live_range_def *phi;
+ struct live_range_edge *edge;
+ char used[MAX_REGISTERS];
+ struct triple **expr;
+
+ /* Instead of doing just the trivial color select here I try
+ * a few extra things because a good color selection will help reduce
+ * copies.
+ */
+
+ /* Find the registers currently in use */
+ memset(used, 0, sizeof(used));
+ for(edge = range->edges; edge; edge = edge->next) {
+ if (edge->node->color == REG_UNSET) {
+ continue;
+ }
+ reg_fill_used(state, used, edge->node->color);
+ }
+
+ if (state->compiler->debug & DEBUG_COLOR_GRAPH2) {
+ int i;
+ i = 0;
+ for(edge = range->edges; edge; edge = edge->next) {
+ i++;
+ }
+ cgdebug_printf(state, "\n%s edges: %d",
+ tops(range->defs->def->op), i);
+ cgdebug_loc(state, range->defs->def);
+ cgdebug_printf(state, "\n");
+ for(i = 0; i < MAX_REGISTERS; i++) {
+ if (used[i]) {
+ cgdebug_printf(state, "used: %s\n",
+ arch_reg_str(i));
+ }
+ }
+ }
+
+ /* If a color is already assigned see if it will work */
+ if (range->color != REG_UNSET) {
+ struct live_range_def *lrd;
+ if (!used[range->color]) {
+ return 1;
+ }
+ for(edge = range->edges; edge; edge = edge->next) {
+ if (edge->node->color != range->color) {
+ continue;
+ }
+ warning(state, edge->node->defs->def, "edge: ");
+ lrd = edge->node->defs;
+ do {
+ warning(state, lrd->def, " %p %s",
+ lrd->def, tops(lrd->def->op));
+ lrd = lrd->next;
+ } while(lrd != edge->node->defs);
+ }
+ lrd = range->defs;
+ warning(state, range->defs->def, "def: ");
+ do {
+ warning(state, lrd->def, " %p %s",
+ lrd->def, tops(lrd->def->op));
+ lrd = lrd->next;
+ } while(lrd != range->defs);
+ internal_error(state, range->defs->def,
+ "live range with already used color %s",
+ arch_reg_str(range->color));
+ }
+
+ /* If I feed into an expression reuse it's color.
+ * This should help remove copies in the case of 2 register instructions
+ * and phi functions.
+ */
+ phi = 0;
+ lrd = live_range_end(state, range, 0);
+ for(; (range->color == REG_UNSET) && lrd ; lrd = live_range_end(state, range, lrd)) {
+ entry = lrd->def->use;
+ for(;(range->color == REG_UNSET) && entry; entry = entry->next) {
+ struct live_range_def *insd;
+ unsigned regcm;
+ insd = &rstate->lrd[entry->member->id];
+ if (insd->lr->defs == 0) {
+ continue;
+ }
+ if (!phi && (insd->def->op == OP_PHI) &&
+ !interfere(rstate, range, insd->lr)) {
+ phi = insd;
+ }
+ if (insd->lr->color == REG_UNSET) {
+ continue;
+ }
+ regcm = insd->lr->classes;
+ if (((regcm & range->classes) == 0) ||
+ (used[insd->lr->color])) {
+ continue;
+ }
+ if (interfere(rstate, range, insd->lr)) {
+ continue;
+ }
+ range->color = insd->lr->color;
+ }
+ }
+ /* If I feed into a phi function reuse it's color or the color
+ * of something else that feeds into the phi function.
+ */
+ if (phi) {
+ if (phi->lr->color != REG_UNSET) {
+ if (used[phi->lr->color]) {
+ range->color = phi->lr->color;
+ }
+ }
+ else {
+ expr = triple_rhs(state, phi->def, 0);
+ for(; expr; expr = triple_rhs(state, phi->def, expr)) {
+ struct live_range *lr;
+ unsigned regcm;
+ if (!*expr) {
+ continue;
+ }
+ lr = rstate->lrd[(*expr)->id].lr;
+ if (lr->color == REG_UNSET) {
+ continue;
+ }
+ regcm = lr->classes;
+ if (((regcm & range->classes) == 0) ||
+ (used[lr->color])) {
+ continue;
+ }
+ if (interfere(rstate, range, lr)) {
+ continue;
+ }
+ range->color = lr->color;
+ }
+ }
+ }
+ /* If I don't interfere with a rhs node reuse it's color */
+ lrd = live_range_head(state, range, 0);
+ for(; (range->color == REG_UNSET) && lrd ; lrd = live_range_head(state, range, lrd)) {
+ expr = triple_rhs(state, lrd->def, 0);
+ for(; expr; expr = triple_rhs(state, lrd->def, expr)) {
+ struct live_range *lr;
+ unsigned regcm;
+ if (!*expr) {
+ continue;
+ }
+ lr = rstate->lrd[(*expr)->id].lr;
+ if (lr->color == REG_UNSET) {
+ continue;
+ }
+ regcm = lr->classes;
+ if (((regcm & range->classes) == 0) ||
+ (used[lr->color])) {
+ continue;
+ }
+ if (interfere(rstate, range, lr)) {
+ continue;
+ }
+ range->color = lr->color;
+ break;
+ }
+ }
+ /* If I have not opportunitically picked a useful color
+ * pick the first color that is free.
+ */
+ if (range->color == REG_UNSET) {
+ range->color =
+ arch_select_free_register(state, used, range->classes);
+ }
+ if (range->color == REG_UNSET) {
+ struct live_range_def *lrd;
+ int i;
+ if (split_ranges(state, rstate, used, range)) {
+ return 0;
+ }
+ for(edge = range->edges; edge; edge = edge->next) {
+ warning(state, edge->node->defs->def, "edge reg %s",
+ arch_reg_str(edge->node->color));
+ lrd = edge->node->defs;
+ do {
+ warning(state, lrd->def, " %s %p",
+ tops(lrd->def->op), lrd->def);
+ lrd = lrd->next;
+ } while(lrd != edge->node->defs);
+ }
+ warning(state, range->defs->def, "range: ");
+ lrd = range->defs;
+ do {
+ warning(state, lrd->def, " %s %p",
+ tops(lrd->def->op), lrd->def);
+ lrd = lrd->next;
+ } while(lrd != range->defs);
+
+ warning(state, range->defs->def, "classes: %x",
+ range->classes);
+ for(i = 0; i < MAX_REGISTERS; i++) {
+ if (used[i]) {
+ warning(state, range->defs->def, "used: %s",
+ arch_reg_str(i));
+ }
+ }
+ error(state, range->defs->def, "too few registers");
+ }
+ range->classes &= arch_reg_regcm(state, range->color);
+ if ((range->color == REG_UNSET) || (range->classes == 0)) {
+ internal_error(state, range->defs->def, "select_free_color did not?");
+ }
+ return 1;
+}
+
+static int color_graph(struct compile_state *state, struct reg_state *rstate)
+{
+ int colored;
+ struct live_range_edge *edge;
+ struct live_range *range;
+ if (rstate->low) {
+ cgdebug_printf(state, "Lo: ");
+ range = rstate->low;
+ if (*range->group_prev != range) {
+ internal_error(state, 0, "lo: *prev != range?");
+ }
+ *range->group_prev = range->group_next;
+ if (range->group_next) {
+ range->group_next->group_prev = range->group_prev;
+ }
+ if (&range->group_next == rstate->low_tail) {
+ rstate->low_tail = range->group_prev;
+ }
+ if (rstate->low == range) {
+ internal_error(state, 0, "low: next != prev?");
+ }
+ }
+ else if (rstate->high) {
+ cgdebug_printf(state, "Hi: ");
+ range = rstate->high;
+ if (*range->group_prev != range) {
+ internal_error(state, 0, "hi: *prev != range?");
+ }
+ *range->group_prev = range->group_next;
+ if (range->group_next) {
+ range->group_next->group_prev = range->group_prev;
+ }
+ if (&range->group_next == rstate->high_tail) {
+ rstate->high_tail = range->group_prev;
+ }
+ if (rstate->high == range) {
+ internal_error(state, 0, "high: next != prev?");
+ }
+ }
+ else {
+ return 1;
+ }
+ cgdebug_printf(state, " %d\n", range - rstate->lr);
+ range->group_prev = 0;
+ for(edge = range->edges; edge; edge = edge->next) {
+ struct live_range *node;
+ node = edge->node;
+ /* Move nodes from the high to the low list */
+ if (node->group_prev && (node->color == REG_UNSET) &&
+ (node->degree == regc_max_size(state, node->classes))) {
+ if (*node->group_prev != node) {
+ internal_error(state, 0, "move: *prev != node?");
+ }
+ *node->group_prev = node->group_next;
+ if (node->group_next) {
+ node->group_next->group_prev = node->group_prev;
+ }
+ if (&node->group_next == rstate->high_tail) {
+ rstate->high_tail = node->group_prev;
+ }
+ cgdebug_printf(state, "Moving...%d to low\n", node - rstate->lr);
+ node->group_prev = rstate->low_tail;
+ node->group_next = 0;
+ *rstate->low_tail = node;
+ rstate->low_tail = &node->group_next;
+ if (*node->group_prev != node) {
+ internal_error(state, 0, "move2: *prev != node?");
+ }
+ }
+ node->degree -= 1;
+ }
+ colored = color_graph(state, rstate);
+ if (colored) {
+ cgdebug_printf(state, "Coloring %d @", range - rstate->lr);
+ cgdebug_loc(state, range->defs->def);
+ cgdebug_flush(state);
+ colored = select_free_color(state, rstate, range);
+ if (colored) {
+ cgdebug_printf(state, " %s\n", arch_reg_str(range->color));
+ }
+ }
+ return colored;
+}
+
+static void verify_colors(struct compile_state *state, struct reg_state *rstate)
+{
+ struct live_range *lr;
+ struct live_range_edge *edge;
+ struct triple *ins, *first;
+ char used[MAX_REGISTERS];
+ first = state->first;
+ ins = first;
+ do {
+ if (triple_is_def(state, ins)) {
+ if ((ins->id < 0) || (ins->id > rstate->defs)) {
+ internal_error(state, ins,
+ "triple without a live range def");
+ }
+ lr = rstate->lrd[ins->id].lr;
+ if (lr->color == REG_UNSET) {
+ internal_error(state, ins,
+ "triple without a color");
+ }
+ /* Find the registers used by the edges */
+ memset(used, 0, sizeof(used));
+ for(edge = lr->edges; edge; edge = edge->next) {
+ if (edge->node->color == REG_UNSET) {
+ internal_error(state, 0,
+ "live range without a color");
+ }
+ reg_fill_used(state, used, edge->node->color);
+ }
+ if (used[lr->color]) {
+ internal_error(state, ins,
+ "triple with already used color");
+ }
+ }
+ ins = ins->next;
+ } while(ins != first);
+}
+
+static void color_triples(struct compile_state *state, struct reg_state *rstate)
+{
+ struct live_range_def *lrd;
+ struct live_range *lr;
+ struct triple *first, *ins;
+ first = state->first;
+ ins = first;
+ do {
+ if ((ins->id < 0) || (ins->id > rstate->defs)) {
+ internal_error(state, ins,
+ "triple without a live range");
+ }
+ lrd = &rstate->lrd[ins->id];
+ lr = lrd->lr;
+ ins->id = lrd->orig_id;
+ SET_REG(ins->id, lr->color);
+ ins = ins->next;
+ } while (ins != first);
+}
+
+static struct live_range *merge_sort_lr(
+ struct live_range *first, struct live_range *last)
+{
+ struct live_range *mid, *join, **join_tail, *pick;
+ size_t size;
+ size = (last - first) + 1;
+ if (size >= 2) {
+ mid = first + size/2;
+ first = merge_sort_lr(first, mid -1);
+ mid = merge_sort_lr(mid, last);
+
+ join = 0;
+ join_tail = &join;
+ /* merge the two lists */
+ while(first && mid) {
+ if ((first->degree < mid->degree) ||
+ ((first->degree == mid->degree) &&
+ (first->length < mid->length))) {
+ pick = first;
+ first = first->group_next;
+ if (first) {
+ first->group_prev = 0;
+ }
+ }
+ else {
+ pick = mid;
+ mid = mid->group_next;
+ if (mid) {
+ mid->group_prev = 0;
+ }
+ }
+ pick->group_next = 0;
+ pick->group_prev = join_tail;
+ *join_tail = pick;
+ join_tail = &pick->group_next;
+ }
+ /* Splice the remaining list */
+ pick = (first)? first : mid;
+ *join_tail = pick;
+ if (pick) {
+ pick->group_prev = join_tail;
+ }
+ }
+ else {
+ if (!first->defs) {
+ first = 0;
+ }
+ join = first;
+ }
+ return join;
+}
+
+static void ids_from_rstate(struct compile_state *state,
+ struct reg_state *rstate)
+{
+ struct triple *ins, *first;
+ if (!rstate->defs) {
+ return;
+ }
+ /* Display the graph if desired */
+ if (state->compiler->debug & DEBUG_INTERFERENCE) {
+ FILE *fp = state->dbgout;
+ print_interference_blocks(state, rstate, fp, 0);
+ print_control_flow(state, fp, &state->bb);
+ fflush(fp);
+ }
+ first = state->first;
+ ins = first;
+ do {
+ if (ins->id) {
+ struct live_range_def *lrd;
+ lrd = &rstate->lrd[ins->id];
+ ins->id = lrd->orig_id;
+ }
+ ins = ins->next;
+ } while(ins != first);
+}
+
+static void cleanup_live_edges(struct reg_state *rstate)
+{
+ int i;
+ /* Free the edges on each node */
+ for(i = 1; i <= rstate->ranges; i++) {
+ remove_live_edges(rstate, &rstate->lr[i]);
+ }
+}
+
+static void cleanup_rstate(struct compile_state *state, struct reg_state *rstate)
+{
+ cleanup_live_edges(rstate);
+ xfree(rstate->lrd);
+ xfree(rstate->lr);
+
+ /* Free the variable lifetime information */
+ if (rstate->blocks) {
+ free_variable_lifetimes(state, &state->bb, rstate->blocks);
+ }
+ rstate->defs = 0;
+ rstate->ranges = 0;
+ rstate->lrd = 0;
+ rstate->lr = 0;
+ rstate->blocks = 0;
+}
+
+static void verify_consistency(struct compile_state *state);
+static void allocate_registers(struct compile_state *state)
+{
+ struct reg_state rstate;
+ int colored;
+
+ /* Clear out the reg_state */
+ memset(&rstate, 0, sizeof(rstate));
+ rstate.max_passes = state->compiler->max_allocation_passes;
+
+ do {
+ struct live_range **point, **next;
+ int tangles;
+ int coalesced;
+
+ if (state->compiler->debug & DEBUG_RANGE_CONFLICTS) {
+ FILE *fp = state->errout;
+ fprintf(fp, "pass: %d\n", rstate.passes);
+ fflush(fp);
+ }
+
+ /* Restore ids */
+ ids_from_rstate(state, &rstate);
+
+ /* Cleanup the temporary data structures */
+ cleanup_rstate(state, &rstate);
+
+ /* Compute the variable lifetimes */
+ rstate.blocks = compute_variable_lifetimes(state, &state->bb);
+
+ /* Fix invalid mandatory live range coalesce conflicts */
+ correct_coalesce_conflicts(state, rstate.blocks);
+
+ /* Fix two simultaneous uses of the same register.
+ * In a few pathlogical cases a partial untangle moves
+ * the tangle to a part of the graph we won't revisit.
+ * So we keep looping until we have no more tangle fixes
+ * to apply.
+ */
+ do {
+ tangles = correct_tangles(state, rstate.blocks);
+ } while(tangles);
+
+
+ print_blocks(state, "resolve_tangles", state->dbgout);
+ verify_consistency(state);
+
+ /* Allocate and initialize the live ranges */
+ initialize_live_ranges(state, &rstate);
+
+ /* Note currently doing coalescing in a loop appears to
+ * buys me nothing. The code is left this way in case
+ * there is some value in it. Or if a future bugfix
+ * yields some benefit.
+ */
+ do {
+ if (state->compiler->debug & DEBUG_COALESCING) {
+ fprintf(state->errout, "coalescing\n");
+ }
+
+ /* Remove any previous live edge calculations */
+ cleanup_live_edges(&rstate);
+
+ /* Compute the interference graph */
+ walk_variable_lifetimes(
+ state, &state->bb, rstate.blocks,
+ graph_ins, &rstate);
+
+ /* Display the interference graph if desired */
+ if (state->compiler->debug & DEBUG_INTERFERENCE) {
+ print_interference_blocks(state, &rstate, state->dbgout, 1);
+ fprintf(state->dbgout, "\nlive variables by instruction\n");
+ walk_variable_lifetimes(
+ state, &state->bb, rstate.blocks,
+ print_interference_ins, &rstate);
+ }
+
+ coalesced = coalesce_live_ranges(state, &rstate);
+
+ if (state->compiler->debug & DEBUG_COALESCING) {
+ fprintf(state->errout, "coalesced: %d\n", coalesced);
+ }
+ } while(coalesced);
+
+#if DEBUG_CONSISTENCY > 1
+# if 0
+ fprintf(state->errout, "verify_graph_ins...\n");
+# endif
+ /* Verify the interference graph */
+ walk_variable_lifetimes(
+ state, &state->bb, rstate.blocks,
+ verify_graph_ins, &rstate);
+# if 0
+ fprintf(state->errout, "verify_graph_ins done\n");
+#endif
+#endif
+
+ /* Build the groups low and high. But with the nodes
+ * first sorted by degree order.
+ */
+ rstate.low_tail = &rstate.low;
+ rstate.high_tail = &rstate.high;
+ rstate.high = merge_sort_lr(&rstate.lr[1], &rstate.lr[rstate.ranges]);
+ if (rstate.high) {
+ rstate.high->group_prev = &rstate.high;
+ }
+ for(point = &rstate.high; *point; point = &(*point)->group_next)
+ ;
+ rstate.high_tail = point;
+ /* Walk through the high list and move everything that needs
+ * to be onto low.
+ */
+ for(point = &rstate.high; *point; point = next) {
+ struct live_range *range;
+ next = &(*point)->group_next;
+ range = *point;
+
+ /* If it has a low degree or it already has a color
+ * place the node in low.
+ */
+ if ((range->degree < regc_max_size(state, range->classes)) ||
+ (range->color != REG_UNSET)) {
+ cgdebug_printf(state, "Lo: %5d degree %5d%s\n",
+ range - rstate.lr, range->degree,
+ (range->color != REG_UNSET) ? " (colored)": "");
+ *range->group_prev = range->group_next;
+ if (range->group_next) {
+ range->group_next->group_prev = range->group_prev;
+ }
+ if (&range->group_next == rstate.high_tail) {
+ rstate.high_tail = range->group_prev;
+ }
+ range->group_prev = rstate.low_tail;
+ range->group_next = 0;
+ *rstate.low_tail = range;
+ rstate.low_tail = &range->group_next;
+ next = point;
+ }
+ else {
+ cgdebug_printf(state, "hi: %5d degree %5d%s\n",
+ range - rstate.lr, range->degree,
+ (range->color != REG_UNSET) ? " (colored)": "");
+ }
+ }
+ /* Color the live_ranges */
+ colored = color_graph(state, &rstate);
+ rstate.passes++;
+ } while (!colored);
+
+ /* Verify the graph was properly colored */
+ verify_colors(state, &rstate);
+
+ /* Move the colors from the graph to the triples */
+ color_triples(state, &rstate);
+
+ /* Cleanup the temporary data structures */
+ cleanup_rstate(state, &rstate);
+
+ /* Display the new graph */
+ print_blocks(state, __func__, state->dbgout);
+}
+
+/* Sparce Conditional Constant Propogation
+ * =========================================
+ */
+struct ssa_edge;
+struct flow_block;
+struct lattice_node {
+ unsigned old_id;
+ struct triple *def;
+ struct ssa_edge *out;
+ struct flow_block *fblock;
+ struct triple *val;
+ /* lattice high val == def
+ * lattice const is_const(val)
+ * lattice low other
+ */
+};
+struct ssa_edge {
+ struct lattice_node *src;
+ struct lattice_node *dst;
+ struct ssa_edge *work_next;
+ struct ssa_edge *work_prev;
+ struct ssa_edge *out_next;
+};
+struct flow_edge {
+ struct flow_block *src;
+ struct flow_block *dst;
+ struct flow_edge *work_next;
+ struct flow_edge *work_prev;
+ struct flow_edge *in_next;
+ struct flow_edge *out_next;
+ int executable;
+};
+#define MAX_FLOW_BLOCK_EDGES 3
+struct flow_block {
+ struct block *block;
+ struct flow_edge *in;
+ struct flow_edge *out;
+ struct flow_edge *edges;
+};
+
+struct scc_state {
+ int ins_count;
+ struct lattice_node *lattice;
+ struct ssa_edge *ssa_edges;
+ struct flow_block *flow_blocks;
+ struct flow_edge *flow_work_list;
+ struct ssa_edge *ssa_work_list;
+};
+
+
+static int is_scc_const(struct compile_state *state, struct triple *ins)
+{
+ return ins && (triple_is_ubranch(state, ins) || is_const(ins));
+}
+
+static int is_lattice_hi(struct compile_state *state, struct lattice_node *lnode)
+{
+ return !is_scc_const(state, lnode->val) && (lnode->val == lnode->def);
+}
+
+static int is_lattice_const(struct compile_state *state, struct lattice_node *lnode)
+{
+ return is_scc_const(state, lnode->val);
+}
+
+static int is_lattice_lo(struct compile_state *state, struct lattice_node *lnode)
+{
+ return (lnode->val != lnode->def) && !is_scc_const(state, lnode->val);
+}
+
+static void scc_add_fedge(struct compile_state *state, struct scc_state *scc,
+ struct flow_edge *fedge)
+{
+ if (state->compiler->debug & DEBUG_SCC_TRANSFORM2) {
+ fprintf(state->errout, "adding fedge: %p (%4d -> %5d)\n",
+ fedge,
+ fedge->src->block?fedge->src->block->last->id: 0,
+ fedge->dst->block?fedge->dst->block->first->id: 0);
+ }
+ if ((fedge == scc->flow_work_list) ||
+ (fedge->work_next != fedge) ||
+ (fedge->work_prev != fedge)) {
+
+ if (state->compiler->debug & DEBUG_SCC_TRANSFORM2) {
+ fprintf(state->errout, "dupped fedge: %p\n",
+ fedge);
+ }
+ return;
+ }
+ if (!scc->flow_work_list) {
+ scc->flow_work_list = fedge;
+ fedge->work_next = fedge->work_prev = fedge;
+ }
+ else {
+ struct flow_edge *ftail;
+ ftail = scc->flow_work_list->work_prev;
+ fedge->work_next = ftail->work_next;
+ fedge->work_prev = ftail;
+ fedge->work_next->work_prev = fedge;
+ fedge->work_prev->work_next = fedge;
+ }
+}
+
+static struct flow_edge *scc_next_fedge(
+ struct compile_state *state, struct scc_state *scc)
+{
+ struct flow_edge *fedge;
+ fedge = scc->flow_work_list;
+ if (fedge) {
+ fedge->work_next->work_prev = fedge->work_prev;
+ fedge->work_prev->work_next = fedge->work_next;
+ if (fedge->work_next != fedge) {
+ scc->flow_work_list = fedge->work_next;
+ } else {
+ scc->flow_work_list = 0;
+ }
+ fedge->work_next = fedge->work_prev = fedge;
+ }
+ return fedge;
+}
+
+static void scc_add_sedge(struct compile_state *state, struct scc_state *scc,
+ struct ssa_edge *sedge)
+{
+ if (state->compiler->debug & DEBUG_SCC_TRANSFORM2) {
+ fprintf(state->errout, "adding sedge: %5ld (%4d -> %5d)\n",
+ (long)(sedge - scc->ssa_edges),
+ sedge->src->def->id,
+ sedge->dst->def->id);
+ }
+ if ((sedge == scc->ssa_work_list) ||
+ (sedge->work_next != sedge) ||
+ (sedge->work_prev != sedge)) {
+
+ if (state->compiler->debug & DEBUG_SCC_TRANSFORM2) {
+ fprintf(state->errout, "dupped sedge: %5ld\n",
+ (long)(sedge - scc->ssa_edges));
+ }
+ return;
+ }
+ if (!scc->ssa_work_list) {
+ scc->ssa_work_list = sedge;
+ sedge->work_next = sedge->work_prev = sedge;
+ }
+ else {
+ struct ssa_edge *stail;
+ stail = scc->ssa_work_list->work_prev;
+ sedge->work_next = stail->work_next;
+ sedge->work_prev = stail;
+ sedge->work_next->work_prev = sedge;
+ sedge->work_prev->work_next = sedge;
+ }
+}
+
+static struct ssa_edge *scc_next_sedge(
+ struct compile_state *state, struct scc_state *scc)
+{
+ struct ssa_edge *sedge;
+ sedge = scc->ssa_work_list;
+ if (sedge) {
+ sedge->work_next->work_prev = sedge->work_prev;
+ sedge->work_prev->work_next = sedge->work_next;
+ if (sedge->work_next != sedge) {
+ scc->ssa_work_list = sedge->work_next;
+ } else {
+ scc->ssa_work_list = 0;
+ }
+ sedge->work_next = sedge->work_prev = sedge;
+ }
+ return sedge;
+}
+
+static void initialize_scc_state(
+ struct compile_state *state, struct scc_state *scc)
+{
+ int ins_count, ssa_edge_count;
+ int ins_index, ssa_edge_index, fblock_index;
+ struct triple *first, *ins;
+ struct block *block;
+ struct flow_block *fblock;
+
+ memset(scc, 0, sizeof(*scc));
+
+ /* Inialize pass zero find out how much memory we need */
+ first = state->first;
+ ins = first;
+ ins_count = ssa_edge_count = 0;
+ do {
+ struct triple_set *edge;
+ ins_count += 1;
+ for(edge = ins->use; edge; edge = edge->next) {
+ ssa_edge_count++;
+ }
+ ins = ins->next;
+ } while(ins != first);
+ if (state->compiler->debug & DEBUG_SCC_TRANSFORM) {
+ fprintf(state->errout, "ins_count: %d ssa_edge_count: %d vertex_count: %d\n",
+ ins_count, ssa_edge_count, state->bb.last_vertex);
+ }
+ scc->ins_count = ins_count;
+ scc->lattice =
+ xcmalloc(sizeof(*scc->lattice)*(ins_count + 1), "lattice");
+ scc->ssa_edges =
+ xcmalloc(sizeof(*scc->ssa_edges)*(ssa_edge_count + 1), "ssa_edges");
+ scc->flow_blocks =
+ xcmalloc(sizeof(*scc->flow_blocks)*(state->bb.last_vertex + 1),
+ "flow_blocks");
+
+ /* Initialize pass one collect up the nodes */
+ fblock = 0;
+ block = 0;
+ ins_index = ssa_edge_index = fblock_index = 0;
+ ins = first;
+ do {
+ if ((ins->op == OP_LABEL) && (block != ins->u.block)) {
+ block = ins->u.block;
+ if (!block) {
+ internal_error(state, ins, "label without block");
+ }
+ fblock_index += 1;
+ block->vertex = fblock_index;
+ fblock = &scc->flow_blocks[fblock_index];
+ fblock->block = block;
+ fblock->edges = xcmalloc(sizeof(*fblock->edges)*block->edge_count,
+ "flow_edges");
+ }
+ {
+ struct lattice_node *lnode;
+ ins_index += 1;
+ lnode = &scc->lattice[ins_index];
+ lnode->def = ins;
+ lnode->out = 0;
+ lnode->fblock = fblock;
+ lnode->val = ins; /* LATTICE HIGH */
+ if (lnode->val->op == OP_UNKNOWNVAL) {
+ lnode->val = 0; /* LATTICE LOW by definition */
+ }
+ lnode->old_id = ins->id;
+ ins->id = ins_index;
+ }
+ ins = ins->next;
+ } while(ins != first);
+ /* Initialize pass two collect up the edges */
+ block = 0;
+ fblock = 0;
+ ins = first;
+ do {
+ {
+ struct triple_set *edge;
+ struct ssa_edge **stail;
+ struct lattice_node *lnode;
+ lnode = &scc->lattice[ins->id];
+ lnode->out = 0;
+ stail = &lnode->out;
+ for(edge = ins->use; edge; edge = edge->next) {
+ struct ssa_edge *sedge;
+ ssa_edge_index += 1;
+ sedge = &scc->ssa_edges[ssa_edge_index];
+ *stail = sedge;
+ stail = &sedge->out_next;
+ sedge->src = lnode;
+ sedge->dst = &scc->lattice[edge->member->id];
+ sedge->work_next = sedge->work_prev = sedge;
+ sedge->out_next = 0;
+ }
+ }
+ if ((ins->op == OP_LABEL) && (block != ins->u.block)) {
+ struct flow_edge *fedge, **ftail;
+ struct block_set *bedge;
+ block = ins->u.block;
+ fblock = &scc->flow_blocks[block->vertex];
+ fblock->in = 0;
+ fblock->out = 0;
+ ftail = &fblock->out;
+
+ fedge = fblock->edges;
+ bedge = block->edges;
+ for(; bedge; bedge = bedge->next, fedge++) {
+ fedge->dst = &scc->flow_blocks[bedge->member->vertex];
+ if (fedge->dst->block != bedge->member) {
+ internal_error(state, 0, "block mismatch");
+ }
+ *ftail = fedge;
+ ftail = &fedge->out_next;
+ fedge->out_next = 0;
+ }
+ for(fedge = fblock->out; fedge; fedge = fedge->out_next) {
+ fedge->src = fblock;
+ fedge->work_next = fedge->work_prev = fedge;
+ fedge->executable = 0;
+ }
+ }
+ ins = ins->next;
+ } while (ins != first);
+ block = 0;
+ fblock = 0;
+ ins = first;
+ do {
+ if ((ins->op == OP_LABEL) && (block != ins->u.block)) {
+ struct flow_edge **ftail;
+ struct block_set *bedge;
+ block = ins->u.block;
+ fblock = &scc->flow_blocks[block->vertex];
+ ftail = &fblock->in;
+ for(bedge = block->use; bedge; bedge = bedge->next) {
+ struct block *src_block;
+ struct flow_block *sfblock;
+ struct flow_edge *sfedge;
+ src_block = bedge->member;
+ sfblock = &scc->flow_blocks[src_block->vertex];
+ for(sfedge = sfblock->out; sfedge; sfedge = sfedge->out_next) {
+ if (sfedge->dst == fblock) {
+ break;
+ }
+ }
+ if (!sfedge) {
+ internal_error(state, 0, "edge mismatch");
+ }
+ *ftail = sfedge;
+ ftail = &sfedge->in_next;
+ sfedge->in_next = 0;
+ }
+ }
+ ins = ins->next;
+ } while(ins != first);
+ /* Setup a dummy block 0 as a node above the start node */
+ {
+ struct flow_block *fblock, *dst;
+ struct flow_edge *fedge;
+ fblock = &scc->flow_blocks[0];
+ fblock->block = 0;
+ fblock->edges = xcmalloc(sizeof(*fblock->edges)*1, "flow_edges");
+ fblock->in = 0;
+ fblock->out = fblock->edges;
+ dst = &scc->flow_blocks[state->bb.first_block->vertex];
+ fedge = fblock->edges;
+ fedge->src = fblock;
+ fedge->dst = dst;
+ fedge->work_next = fedge;
+ fedge->work_prev = fedge;
+ fedge->in_next = fedge->dst->in;
+ fedge->out_next = 0;
+ fedge->executable = 0;
+ fedge->dst->in = fedge;
+
+ /* Initialize the work lists */
+ scc->flow_work_list = 0;
+ scc->ssa_work_list = 0;
+ scc_add_fedge(state, scc, fedge);
+ }
+ if (state->compiler->debug & DEBUG_SCC_TRANSFORM) {
+ fprintf(state->errout, "ins_index: %d ssa_edge_index: %d fblock_index: %d\n",
+ ins_index, ssa_edge_index, fblock_index);
+ }
+}
+
+
+static void free_scc_state(
+ struct compile_state *state, struct scc_state *scc)
+{
+ int i;
+ for(i = 0; i < state->bb.last_vertex + 1; i++) {
+ struct flow_block *fblock;
+ fblock = &scc->flow_blocks[i];
+ if (fblock->edges) {
+ xfree(fblock->edges);
+ fblock->edges = 0;
+ }
+ }
+ xfree(scc->flow_blocks);
+ xfree(scc->ssa_edges);
+ xfree(scc->lattice);
+
+}
+
+static struct lattice_node *triple_to_lattice(
+ struct compile_state *state, struct scc_state *scc, struct triple *ins)
+{
+ if (ins->id <= 0) {
+ internal_error(state, ins, "bad id");
+ }
+ return &scc->lattice[ins->id];
+}
+
+static struct triple *preserve_lval(
+ struct compile_state *state, struct lattice_node *lnode)
+{
+ struct triple *old;
+ /* Preserve the original value */
+ if (lnode->val) {
+ old = dup_triple(state, lnode->val);
+ if (lnode->val != lnode->def) {
+ xfree(lnode->val);
+ }
+ lnode->val = 0;
+ } else {
+ old = 0;
+ }
+ return old;
+}
+
+static int lval_changed(struct compile_state *state,
+ struct triple *old, struct lattice_node *lnode)
+{
+ int changed;
+ /* See if the lattice value has changed */
+ changed = 1;
+ if (!old && !lnode->val) {
+ changed = 0;
+ }
+ if (changed &&
+ lnode->val && old &&
+ (memcmp(lnode->val->param, old->param,
+ TRIPLE_SIZE(lnode->val) * sizeof(lnode->val->param[0])) == 0) &&
+ (memcmp(&lnode->val->u, &old->u, sizeof(old->u)) == 0)) {
+ changed = 0;
+ }
+ if (old) {
+ xfree(old);
+ }
+ return changed;
+
+}
+
+static void scc_debug_lnode(
+ struct compile_state *state, struct scc_state *scc,
+ struct lattice_node *lnode, int changed)
+{
+ if ((state->compiler->debug & DEBUG_SCC_TRANSFORM2) && lnode->val) {
+ display_triple_changes(state->errout, lnode->val, lnode->def);
+ }
+ if (state->compiler->debug & DEBUG_SCC_TRANSFORM) {
+ FILE *fp = state->errout;
+ struct triple *val, **expr;
+ val = lnode->val? lnode->val : lnode->def;
+ fprintf(fp, "%p %s %3d %10s (",
+ lnode->def,
+ ((lnode->def->op == OP_PHI)? "phi: ": "expr:"),
+ lnode->def->id,
+ tops(lnode->def->op));
+ expr = triple_rhs(state, lnode->def, 0);
+ for(;expr;expr = triple_rhs(state, lnode->def, expr)) {
+ if (*expr) {
+ fprintf(fp, " %d", (*expr)->id);