Logo Search packages:      
Sourcecode: faucc version File versions

declaration.c

/* $Id: declaration.c,v 1.178 2009-01-27 15:40:22 potyra Exp $ 
 *
 * Copyright (C) 2007-2009 FAUcc Team <info@faumachine.org>.
 * This program is free software. You can redistribute it and/or modify it
 * under the terms of the GNU General Public License, either version 2 of
 * the License, or (at your option) any later version. See COPYING.
 */

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "setup.h"
#include "identifier.h"
#include "declaration.h"
#include "expr.h"
#include "stmt.h"
#include "arch_i286_gen.h"
#include "arch_i386_gen.h"
#include "simplify.h"
#include "stmt.h"
#include "cc1.h"


void
declaration_rename_structunionenum(
      struct declaration *dion,
      enum type_type type,
      const char *old,
      const char *new
)
{
      struct expr *initializer;

      type_rename_structunionenum(dion->type_name, type, old, new);

      initializer = declaration_initializer_get(dion);
      if (initializer) {
            expr_rename_structunionenum(initializer, type, old, new);
      }
}

void
declaration_rename_type(
      struct declaration *dion,
      const char *old,
      const char *new
)
{
      type_rename_type(dion->type_name, old, new);
}

struct declaration *
declaration_new(void)
{
      struct declaration *d;

      d = malloc(sizeof(*d));
      assert(d);

      memset(d, 0, sizeof(*d));

      return d;
}

void
declaration_name_set(struct declaration *d, const char *name)
{
      d->identifier = name;
}

const char *
declaration_name_get(struct declaration *d)
{
      return d->identifier;
}

void
declaration_type_get(struct type **adp, struct declaration *dor)
{
      *adp = dor->type_name;
}

void
declaration_initializer_set(struct declaration *dor, struct expr *initializer)
{
      dor->initializer = initializer;
}

struct expr *
declaration_initializer_get(struct declaration *dor)
{
      return dor->initializer;
}

struct declaration *
declaration_identifier(const char *name)
{
      struct declaration *dor;

      dor = malloc(sizeof(*dor));
      assert(dor);

      memset(dor, 0, sizeof(*dor));

      dor->identifier = name;
      dor->type_name = type_type_spec();

      return dor;
}

void
declaration_free(struct declaration *dor)
{
}

static void
decl_reg_to_type_and_class(
      const char *name,
      enum type_type *typep,
      unsigned int *classp
)
{
      switch (opt_b) {
      case TARGET_I286:
            arch_i286_gen_class_and_type_get(name, classp, typep);
            break;
      case TARGET_I386:
            arch_i386_gen_class_and_type_get(name, classp, typep);
            break;
      default:
            assert(0);
      }
}

static unsigned int
decl_reg_class_or(unsigned int a, unsigned int b)
{
      switch (opt_b) {
      case TARGET_I286:
            return arch_i286_gen_class_or(a, b);
      case TARGET_I386:
            return arch_i386_gen_class_or(a, b);
      default:
            assert(0);
      }
}

static unsigned int
decl_reg_class_and(unsigned int a, unsigned int b)
{
      switch (opt_b) {
      case TARGET_I286:
            return arch_i286_gen_class_and(a, b);
      case TARGET_I386:
            return arch_i386_gen_class_and(a, b);
      default:
            assert(0);
      }
}

static void
decl_color_init(unsigned int *count)
{
      switch (opt_b) {
      case TARGET_I286:
            arch_i286_color_init(count);
            break;
      case TARGET_I386:
            arch_i386_color_init(count);
            break;
      default:
            assert(0);
      }
}

static void
decl_color_add(unsigned int *count, unsigned int class, enum type_type type)
{
      switch (opt_b) {
      case TARGET_I286:
            arch_i286_color_add(count, class, type);
            break;
      case TARGET_I386:
            arch_i386_color_add(count, class, type);
            break;
      default:
            assert(0);
      }
}

static void
decl_color_sub(unsigned int *count, unsigned int class, enum type_type type)
{
      switch (opt_b) {
      case TARGET_I286:
            arch_i286_color_sub(count, class, type);
            break;
      case TARGET_I386:
            arch_i386_color_sub(count, class, type);
            break;
      default:
            assert(0);
      }
}

static int
decl_color_check(unsigned int *count, unsigned int class, enum type_type type)
{
      switch (opt_b) {
      case TARGET_I286:
            return arch_i286_color_check(count, class, type);
      case TARGET_I386:
            return arch_i386_color_check(count, class, type);
      default:
            assert(0);
      }
}

static void
decl_reg_init(uint32_t *conflicts)
{
      switch (opt_b) {
      case TARGET_I286:
            arch_i286_gen_reg_init(conflicts);
            break;
      case TARGET_I386:
            arch_i386_gen_reg_init(conflicts);
            break;
      default:
            assert(0);
      }
}

static void
decl_reg_add(uint32_t *conflicts, unsigned int reg)
{
      switch (opt_b) {
      case TARGET_I286:
            arch_i286_gen_reg_add(conflicts, reg);
            break;
      case TARGET_I386:
            arch_i386_gen_reg_add(conflicts, reg);
            break;
      default:
            assert(0);
      }
}

static int
decl_reg_get(uint32_t *conflicts, unsigned int class, enum type_type type)
{
      switch (opt_b) {
      case TARGET_I286:
            return arch_i286_gen_reg_get(conflicts, class, type);
      case TARGET_I386:
            return arch_i386_gen_reg_get(conflicts, class, type);
      default:
            assert(0);
      }
}

static int
decl_add(struct decl_live **fp, struct decl_live **lp, struct declaration *d)
{
      struct decl_live *l;

      for (l = *fp; ; l = l->next) {
            if (! l) {
                  l = malloc(sizeof *l);
                  assert(l);

                  l->decl = d;

                  l->prev = *lp;
                  l->next = NULL;
                  if (l->prev) {
                        l->prev->next = l;
                  } else {
                        *fp = l;
                  }
                  *lp = l;
                  return 0;
            }
            if (l->decl == d) {
                  /* Already in list. */
                  return 1;
            }
      }
}

static int
decl_remove(struct decl_live **fp, struct decl_live **lp, struct declaration *d)
{
      struct decl_live *l;

      for (l = *fp; ; l = l->next) {
            if (! l) {
                  return 1;
            }
            if (l->decl == d) {
                  if (l->prev) {
                        l->prev->next = l->next;
                  } else {
                        *fp = l->next;
                  }
                  if (l->next) {
                        l->next->prev = l->prev;
                  } else {
                        *lp = l->prev;
                  }

                  free(l);
                  return 0;
            }
      }
}

static int
decl_is_element(struct decl_live *first, struct declaration *d)
{
      struct decl_live *l;

      for (l = first; ; l = l->next) {
            if (! l) {
                  return 0;
            }
            if (l->decl == d) {
                  return 1;
            }
      }
}

static unsigned int
decl_count(struct decl_live *first)
{
      struct decl_live *l;
      unsigned int count;

      for (l = first, count = 0; l; l = l->next, count++) {
      }

      return count;
}

static int
decl_live_add(struct stmt *s, unsigned int tail, struct declaration *d)
{
      return decl_add(&s->decl_live_first[tail], &s->decl_live_last[tail], d);
}

static void
decl_conflict_add(struct declaration *d0, struct declaration *d1)
{
      if (d0 == d1) {
            /* Don't add conflicts with myself. */
            return;
      }

      decl_add(&d0->conflict_first, &d0->conflict_last, d1);
      decl_add(&d1->conflict_first, &d1->conflict_last, d0);
}

static void
decl_move_add(struct declaration *d0, struct declaration *d1)
{
      if (d0 == d1) {
            /* Don't add moves to myself. */
            return;
      }

      decl_add(&d0->move_first, &d0->move_last, d1);
      decl_add(&d1->move_first, &d1->move_last, d0);
}

static void
decl_move_remove(struct declaration *d0, struct declaration *d1)
{
      decl_remove(&d0->move_first, &d0->move_last, d1);
      decl_remove(&d1->move_first, &d1->move_last, d0);
}

static int
declaration_alive_merge0(struct stmt *s)
{
      struct decl_live *w;
      struct decl_live *l;
      int done;

      done = 1;

      for (l = s->decl_live_first[1]; l; l = l->next) {
            for (w = s->decl_write_first; ; w = w->next) {
                  if (! w) {
                        /* Not written in s. */
                        done &= decl_live_add(s, 0, l->decl);
                        break;
                  }
                  if (l->decl == w->decl) {
                        /* Written in s. */
                        break;
                  }
            }
      }

      return done;
}

static int
declaration_alive_merge1(struct stmt *s0, struct stmt *s1)
{
      struct decl_live *l;
      int done;

      done = 1;

      for (l = s1->decl_live_first[0]; l; l = l->next) {
            done &= decl_live_add(s0, 1, l->decl);
      }

      return done;
}

static void
declaration_alive_rhs_expr(struct stmt *s, struct expr *e)
{
      struct expr *ce;

      switch (e->type) {
      case EXPR_NONE:
            assert(0);
      case EXPR_BRACES:
            assert(0);

      case EXPR_SIZEOF_TYPE:
      case EXPR_SIZEOF_EXPR:
      case EXPR_BUILTIN_CONSTANT_P:
      case EXPR_BUILTIN_OFFSETOF:

      case EXPR_DOT:
      case EXPR_ARROW:
      case EXPR_ARRAY:

      case EXPR_PRE_INC:
      case EXPR_PRE_DEC:
      case EXPR_POST_INC:
      case EXPR_POST_DEC:

      case EXPR_LEFT_ASSIGN:
      case EXPR_RIGHT_ASSIGN:
      case EXPR_ADD_ASSIGN:
      case EXPR_SUB_ASSIGN:
      case EXPR_MUL_ASSIGN:
      case EXPR_DIV_ASSIGN:
      case EXPR_MOD_ASSIGN:
      case EXPR_AND_ASSIGN:
      case EXPR_OR_ASSIGN:
      case EXPR_XOR_ASSIGN:

      case EXPR_SHORT_AND:
      case EXPR_SHORT_OR:
      case EXPR_CONDITION:
      case EXPR_LIST:
            assert(0);

      case EXPR_INTEGER:
      case EXPR_REAL:
      case EXPR_STRING:
            break;

      case EXPR_AMPHERSAND:
            assert(e->expr0->type == EXPR_IDENTIFIER);
            if (e->expr0->declaration->storage == STORAGE_AUTO
             || e->expr0->declaration->storage == STORAGE_REGISTER) {
                  e->expr0->declaration->storage_class = DECL_CLASS_NONE;
                  assert(e->expr0->declaration->storage_mem);

                  decl_add(&s->decl_write_first, &s->decl_write_last,
                              e->expr0->declaration);
                  decl_add(&s->decl_live_first[1],
                              &s->decl_live_last[1],
                              e->expr0->declaration);
            }
            break;

      case EXPR_IDENTIFIER:
            if ((e->declaration->storage == STORAGE_AUTO
              || e->declaration->storage == STORAGE_REGISTER)
             && e->declaration->type_name->type != TYPE_ARRAY) {
                  decl_add(&s->decl_read_first, &s->decl_read_last,
                              e->declaration);
                  decl_add(&s->decl_live_first[0],
                              &s->decl_live_last[0],
                              e->declaration);
            }
            break;
            
      case EXPR_BUILTIN_VA_ARG:
      case EXPR_TYPE_CONVERSION:
      case EXPR_STAR:
      case EXPR_NEG:
      case EXPR_INV:
      case EXPR_NOT:
            declaration_alive_rhs_expr(s, e->expr0);
            break;

      case EXPR_LEFT:
      case EXPR_RIGHT:
      case EXPR_ADD:
      case EXPR_SUB:
      case EXPR_MUL:
      case EXPR_DIV:
      case EXPR_MOD:
      case EXPR_AND:
      case EXPR_OR:
      case EXPR_XOR:

      case EXPR_EQUAL:
      case EXPR_NOT_EQUAL:
      case EXPR_LESS:
      case EXPR_LESS_EQUAL:
      case EXPR_GREATER:
      case EXPR_GREATER_EQUAL:
            declaration_alive_rhs_expr(s, e->expr0);
            declaration_alive_rhs_expr(s, e->expr1);
            break;

      case EXPR_ASSIGN:
            assert(0);
            declaration_alive_rhs_expr(s, e->expr1);
            break;

      case EXPR_FUNC:
            declaration_alive_rhs_expr(s, e->expr0);
            for (ce = e->expr1->first; ce; ce = ce->next) {
                  declaration_alive_rhs_expr(s, ce);
            }
            break;
      }
}

static void
declaration_alive_lhs_expr(struct stmt *s, struct expr *e)
{
      if (e->type == EXPR_IDENTIFIER) {
            if ((e->declaration->storage == STORAGE_AUTO
              || e->declaration->storage == STORAGE_REGISTER)
             && s) {
                  decl_add(&s->decl_write_first, &s->decl_write_last,
                              e->declaration);
                  decl_add(&s->decl_live_first[1],
                              &s->decl_live_last[1],
                              e->declaration);
            }

      } else { assert(e->type == EXPR_STAR);
            declaration_alive_rhs_expr(s, e->expr0);
      }
}

static void
declaration_alive_expr(struct stmt *s, struct expr *e)
{
      if (e->type == EXPR_ASSIGN) {
            declaration_alive_lhs_expr(s, e->expr0);
            declaration_alive_rhs_expr(s, e->expr1);
      } else {
            declaration_alive_rhs_expr(s, e);
      }
}

static void
decl_expr_constraints(struct expr *e)
{
      struct expr *ce;

      if (e->expr0) {
            decl_expr_constraints(e->expr0);
      }
      if (e->expr1) {
            decl_expr_constraints(e->expr1);
      }
      for (ce = e->first; ce; ce = ce->next) {
            decl_expr_constraints(ce);
      }

      switch (e->type) {
      case EXPR_AMPHERSAND:
            assert(e->expr0->type == EXPR_IDENTIFIER);
            if (e->expr0->declaration->storage == STORAGE_AUTO
             || e->expr0->declaration->storage == STORAGE_REGISTER) {
                  e->expr0->declaration->storage_class = DECL_CLASS_NONE;
                  assert(e->expr0->declaration->storage_mem);
            }
            break;
      default:
            /* No constraints... */
            break;
      }
}

static void
decl_asm_constraints(
      unsigned int *classinfo,
      struct scope *scope,
      const char *s,
      struct expr *e
)
{
      unsigned int regs;
      int m;
      const char *str;
      unsigned int i;

      str = s;
      if ('0' <= *str && *str <= '9') {
            return;

      } else {
            regs = DECL_CLASS_NONE;
            m = 0;
            for (str = s; *str; str++) {
                  switch (*str) {
                  case '0': case '1': case '2': case '3': case '4':
                  case '5': case '6': case '7': case '8': case '9':
                        assert(0);
                  case '=':
                  case '&':
                  case '+':
                        break;
                  case 'A':
                  case 'D':
                  case 'S':
                  case 'a':
                  case 'b':
                  case 'c':
                  case 'd':
                  case 'f':
                  case 'q':
                  case 'r':
                  case 'l':
                  case 't':
                  case 'u':
                        i = (unsigned int) *str;

                        assert(classinfo[i] != DECL_CLASS_NONE);
                        
                        regs = decl_reg_class_or(regs, classinfo[i]);
                        break;
                  case 'i':
                        break;
                  case 'm':
                        m = 1;
                        break;
                  default:
                        fprintf(stderr, "Unknown constraint '%c'.\n",
                                    *str);
                        assert(0);
                  }
            }
      }

      switch (e->type) {
      case EXPR_INTEGER:
      case EXPR_REAL:
      case EXPR_AMPHERSAND:
      case EXPR_TYPE_CONVERSION:
            break;

      case EXPR_IDENTIFIER:
            if (e->declaration->storage == STORAGE_AUTO
             || e->declaration->storage == STORAGE_REGISTER) {
                  e->declaration->storage_class
                        = decl_reg_class_and(
                              e->declaration->storage_class, regs);
                  e->declaration->storage_mem &= m;
                  assert(e->declaration->storage_class != DECL_CLASS_NONE
                      || e->declaration->storage_mem);
            }
            break;

      default:
            assert(0);
      }
}

static void
decl_replace(
      struct expr *e,
      struct expr *old,
      struct expr *new
)
{
      if (e->type == EXPR_IDENTIFIER
       && e->declaration == old->declaration) {
            expr_cp(e, expr_dup(new));
      }
}

static void
decl_lhs_replace(
      struct expr *e,
      struct expr *old,
      struct expr *new
)
{
      if (! e) {
            return;
      }

      switch (e->type) {
      case EXPR_IDENTIFIER:
            decl_replace(e, old, new);
            break;
      case EXPR_ASSIGN:
            decl_replace(e->expr0, old, new);
            break;
      case EXPR_FUNC:
            break;
      default:
            assert(0);
      }
}

static void
decl_rhs_replace(
      struct expr *e,
      struct expr *old,
      struct expr *new
)
{
      struct expr *ce;

      if (! e) {
            return;
      }

      switch (e->type) {
      case EXPR_INTEGER:
            break;
      case EXPR_IDENTIFIER:
            decl_replace(e, old, new);
            break;
      case EXPR_ASSIGN:
            if (e->expr0->type == EXPR_STAR) {
                  assert(e->expr0->expr0->type == EXPR_TYPE_CONVERSION);
                  decl_replace(e->expr0->expr0->expr0, old, new);
            }
            decl_replace(e->expr1, old, new);
            if (e->expr1->expr0) {
                  decl_replace(e->expr1->expr0, old, new);
                  if (e->expr1->expr0->expr0) {
                        decl_replace(e->expr1->expr0->expr0, old, new);
                  }
            }
            if (e->expr1->expr1) {
                  decl_replace(e->expr1->expr1, old, new);
                  for (ce = e->expr1->expr1->first; ce; ce = ce->next) {
                        decl_replace(ce, old, new);
                  }
            }
            break;
      case EXPR_FUNC:
            decl_replace(e->expr0, old, new);
            for (ce = e->expr1->first; ce; ce = ce->next) {
                  decl_replace(ce, old, new);
            }
            break;
      case EXPR_EQUAL:
      case EXPR_NOT_EQUAL:
      case EXPR_LESS:
      case EXPR_LESS_EQUAL:
      case EXPR_GREATER:
      case EXPR_GREATER_EQUAL:
            decl_replace(e->expr0, old, new);
            decl_replace(e->expr1, old, new);
            break;
      default:
            assert(0);
      }
}

static void
decl_constraint_ease(
      struct stmt *block,
      struct stmt *s,
      struct constraint *c,
      struct expr **exprlist,
      unsigned int i
)
{
      struct type *t;
      struct declaration *dion;
      struct stmt *s0;
      struct stmt *s1;
      const char *constraint;

      t = expr_typeof(block->scope, c->expr);
      t = type_pure(t);

      if (t->type == TYPE_FLOAT32
       || t->type == TYPE_FLOAT64
       || t->type == TYPE_FLOAT80) {
            constraint = "=fm";
      } else {
            constraint = "=rm";
      }

      if (*c->string == '=') {
            /*
             * Output
             */
            if ((c->expr->type == EXPR_IDENTIFIER
              && c->expr->declaration->type_name->mod_volatile)
             || strcmp(c->string, "=m") == 0) {
                  /* Leave as is. */
                  exprlist[i] = c->expr;
                  return;
            }

            dion = declaration_identifier(identifier_tmp());
            dion->storage = STORAGE_AUTO;
            dion->type_name = t;

            scope_declaration_append(block->scope, dion);

            s0 = stmt_expr(expr_assign(
                        expr_dup(c->expr),
                        expr_identifier(dion)));
            constraint_output(s0, constraint, expr_dup(c->expr));
            constraint_input(s0, constraint + 1, expr_identifier(dion));
            s0->change = constraint_list_new();

            decl_lhs_replace(s->expr0, c->expr, expr_identifier(dion));
            expr_cp(c->expr, expr_identifier(dion));
            stmt_append(block, s, s0);

            exprlist[i] = c->expr;

      } else if (*c->string == '+') {
            /*
             * Input/Output
             */
            if ((c->expr->type == EXPR_IDENTIFIER
              && c->expr->declaration->type_name->mod_volatile)
             || strcmp(c->string, "+m") == 0) {
                  /* Leave as is. */
                  exprlist[i] = c->expr;
                  return;
            }

            dion = declaration_identifier(identifier_tmp());
            dion->storage = STORAGE_AUTO;
            dion->type_name = t;

            scope_declaration_append(block->scope, dion);

            s0 = stmt_expr(expr_assign(
                        expr_identifier(dion),
                        expr_dup(c->expr)));
            constraint_output(s0, constraint, expr_identifier(dion));
            constraint_input(s0, constraint + 1, expr_dup(c->expr));
            s0->change = constraint_list_new();

            s1 = stmt_expr(expr_assign(
                        expr_dup(c->expr),
                        expr_identifier(dion)));
            constraint_output(s1, constraint, expr_dup(c->expr));
            constraint_input(s1, constraint + 1, expr_identifier(dion));
            s1->change = constraint_list_new();

            stmt_prepend(block, s, s0);
            decl_lhs_replace(s->expr0, c->expr, expr_identifier(dion));
            decl_rhs_replace(s->expr0, c->expr, expr_identifier(dion));
            expr_cp(c->expr, expr_identifier(dion));
            stmt_append(block, s, s1);

            exprlist[i] = c->expr;

      } else if ('0' <= *c->string && *c->string <= '9') {
            /*
             * Input for Output
             */
            assert(atoi(c->string) < i);
            assert(atoi(c->string) < 100);

            if (exprlist[atoi(c->string)]->type == EXPR_IDENTIFIER
             && exprlist[atoi(c->string)]->declaration->type_name->mod_volatile) {
                  /* Leave as is. */
                  return;
            }

            s0 = stmt_expr(expr_assign(
                        expr_dup(exprlist[atoi(c->string)]),
                        expr_dup(c->expr)));
            constraint_output(s0, constraint, expr_dup(exprlist[atoi(c->string)]));
            constraint_input(s0, constraint + 1, expr_dup(c->expr));
            s0->change = constraint_list_new();

            stmt_prepend(block, s, s0);
            decl_rhs_replace(s->expr0, c->expr, expr_dup(exprlist[atoi(c->string)]));
            expr_cp(c->expr, expr_dup(exprlist[atoi(c->string)]));

      } else if (strchr(c->string, 'i')
            && expr_is_constant(c->expr)) {
            /*
             * Constant Input
             */
            /* Leave as is. */

      } else {
            /*
             * Input
             */
            if ((c->expr->type == EXPR_IDENTIFIER
              && c->expr->declaration->type_name->mod_volatile)
             || strcmp(c->string, "m") == 0) {
                  /* Leave as is. */
                  return;
            }
            if (strchr(c->string, 'r')
             && strchr(c->string, 'm')
             && strchr(c->string, 'i')) {
                  /* Everything allowed. Leave as is. */
                  return;
            }

            dion = declaration_identifier(identifier_tmp());
            dion->storage = STORAGE_AUTO;
            dion->type_name = t;

            scope_declaration_append(block->scope, dion);

            s0 = stmt_expr(expr_assign(
                        expr_identifier(dion),
                        expr_dup(c->expr)));
            constraint_output(s0, constraint, expr_identifier(dion));
            constraint_input(s0, constraint + 1, expr_dup(c->expr));
            s0->change = constraint_list_new();

            stmt_prepend(block, s, s0);
            decl_rhs_replace(s->expr0, c->expr, expr_identifier(dion));
            expr_cp(c->expr, expr_identifier(dion));
      }
}

static int
decl_can_coalesce(struct declaration *d0, struct declaration *d1)
{
      unsigned int count0[DECL_CLASS_COUNT];
      unsigned int count1[DECL_CLASS_COUNT];
      struct decl_live *l0;
      struct decl_live *l1;
      struct declaration *n;
      int first;
      int check;

      decl_color_init(count0);

      for (l0 = d0->conflict_first; l0; l0 = l0->next) {
            n = l0->decl;

            first = 1;
            decl_color_init(count1);
            for (l1 = n->conflict_first; l1; l1 = l1->next) {
                  if (l1->decl == d0
                   || l1->decl == d1) {
                        if (first) {
                              decl_color_add(count1,
                                    decl_reg_class_and(
                                          d0->storage_class,
                                          d1->storage_class),
                                    d0->type_name->type);
                              first = 0;
                        }
                  } else {
                        decl_color_add(count1,
                              l1->decl->storage_class,
                              l1->decl->type_name->type);
                  }
            }

            check = decl_color_check(count1, n->storage_class,
                        n->type_name->type);
            if (! check) {
                  decl_color_add(count0, n->storage_class,
                              n->type_name->type);
            }
      }
      for (l0 = d1->conflict_first; l0; l0 = l0->next) {
            n = l0->decl;

            if (decl_is_element(d0->conflict_first, n)) {
                  continue;
            }

            first = 1;
            decl_color_init(count1);
            for (l1 = n->conflict_first; l1; l1 = l1->next) {
                  if (l1->decl == d0
                   || l1->decl == d1) {
                        if (first) {
                              decl_color_add(count1,
                                    decl_reg_class_and(
                                          d0->storage_class,
                                          d1->storage_class),
                                    d0->type_name->type);
                              first = 0;
                        }
                  } else {
                        decl_color_add(count1,
                              l1->decl->storage_class,
                              l1->decl->type_name->type);
                  }
            }

            check = decl_color_check(count1, n->storage_class,
                        n->type_name->type);
            if (! check) {
                  decl_color_add(count0, n->storage_class,
                              n->type_name->type);
            }
      }

      return decl_color_check(count0,
            decl_reg_class_and(d0->storage_class, d1->storage_class),
            d0->type_name->type);
}

static void
decl_coalesce(struct declaration *d0, struct declaration *d1)
{
      struct declaration *n;

      while (d0->conflict_first) {
            n = d0->conflict_first->decl;

            decl_remove(&n->conflict_first, &n->conflict_last, d0);
            decl_add(&n->conflict_first, &n->conflict_last, d1);

            decl_remove(&d0->conflict_first, &d0->conflict_last, n);
            decl_add(&d1->conflict_first, &d1->conflict_last, n);
      }
      while (d0->move_first) {
            n = d0->move_first->decl;
            assert(n != d0);

            decl_move_remove(d0, n);
            decl_move_add(d1, n);
      }

      d0->storage_class = decl_reg_class_and(
                  d0->storage_class, d1->storage_class);
      d1->storage_class = decl_reg_class_and(
                  d0->storage_class, d1->storage_class);
      d0->storage_mem &= d1->storage_mem;
      d1->storage_mem &= d0->storage_mem;

      d0->clone = d1;
}

void
declaration_alive(
      struct storage_register *reginfo,
      unsigned int *classinfo,
      unsigned int *typeinfo,
      struct stmt *fs
)
{
      struct expr *exprlist[100];
      struct declaration *dion;
      struct declaration *stack_first;
      struct declaration *stack_last;
      struct stmt *cs;
      struct stmt *ss;
      struct constraint *c;
      struct stmt *target;
      unsigned int i;
      int done;

#if 0
      print_stmt(stderr, 1, 0, fs);
      fprintf(stderr, "\n");
#endif

      for (cs = fs->stmt_first; cs; ) {
            struct stmt *next;

            next = cs->next;

            i = 0;
            if (cs->output) {
                  for (c = cs->output->first; c; c = c->next) {
                        decl_constraint_ease(fs, cs, c, exprlist, i);
                        i++;
                  }
            }
            if (cs->input) {
                  for (c = cs->input->last; c; c = c->prev) {
                        decl_constraint_ease(fs, cs, c, exprlist, i);
                        i++;
                  }
            }

            cs = next;
      }

#if 0
      print_stmt(stderr, 1, 0, fs);
      fprintf(stderr, "\n");
#endif

      if (fs->scope->declaration_first != fs->scope->declaration_last) {
            /*
             * Sort declarations. Register variables to top of
             * declaration list.
             */
            for (dion = fs->scope->declaration_first;
                dion && dion->storage == STORAGE_REGISTER;
                dion = dion->next) {
            }
            if (dion) {
                  struct declaration *dion2;

                  for (dion2 = dion->next;
                      dion2;
                      dion2 = dion2->next) {
                        if (dion2->storage != STORAGE_REGISTER) {
                              continue;
                        }
                  
                        /* Move dion2 before dion. */
                        dion2->prev->next = dion2->next;
                        if (dion2->next) {
                              dion2->next->prev = dion2->prev;
                        } else {
                              fs->scope->declaration_last
                                    = dion2->prev;
                        }

                        dion2->prev = dion->prev;
                        dion2->next = dion;
                        if (dion2->prev) {
                              dion2->prev->next = dion2;
                        } else {
                              fs->scope->declaration_first
                                    = dion2;
                        }
                        dion2->next->prev = dion2;
                  }
            }
      }

#if 0
      print_stmt(stderr, 1, 0, fs);
      fprintf(stderr, "\n");
#endif

      for (dion = fs->scope->declaration_first; dion; dion = dion->next) {
            if (dion->storage != STORAGE_AUTO
             && dion->storage != STORAGE_REGISTER) {
                  continue;
            }
            assert(dion->identifier);

            dion->storage_class = typeinfo[dion->type_name->type];
            dion->storage_mem = 1;
      }

      for (cs = fs->stmt_first; cs; cs = cs->next) {
            switch (cs->type) {
            case STMT_NONE:
                  assert(0);

            case STMT_NULL:
            case STMT_CASE:
            case STMT_DEFAULT:
            case STMT_WHILE:
            case STMT_DO_WHILE:
            case STMT_FOR:
            case STMT_BREAK:
            case STMT_CONTINUE:
            case STMT_BLOCK:
                  assert(0);

            case STMT_LABEL:
            case STMT_EXPR:
            case STMT_IF:
            case STMT_SWITCH:
            case STMT_GOTO:
            case STMT_RETURN:
            case STMT_VA_START:
            case STMT_VA_END:
                  if (cs->expr0) {
                        decl_expr_constraints(cs->expr0);
                  }
                  if (cs->expr1) {
                        decl_expr_constraints(cs->expr1);
                  }
                  break;

            case STMT_ASM:
                  break;

            default:
                  assert(0);
            }

            if (cs->output) {
                  for (c = cs->output->first; c; c = c->next) {
                        decl_expr_constraints(c->expr);
                        decl_asm_constraints(
                                    classinfo, fs->scope,
                                    c->string, c->expr);
                  }
            }
            if (cs->input) {
                  for (c = cs->input->first; c; c = c->next) {
                        decl_expr_constraints(c->expr);
                        decl_asm_constraints(
                                    classinfo, fs->scope,
                                    c->string, c->expr);
                  }
            }
      }

      for (cs = fs->stmt_first; cs; cs = cs->next) {
            cs->decl_write_first = NULL;
            cs->decl_write_last = NULL;
            cs->decl_read_first = NULL;
            cs->decl_read_last = NULL;
            cs->decl_live_first[0] = NULL;
            cs->decl_live_last[0] = NULL;
            cs->decl_live_first[1] = NULL;
            cs->decl_live_last[1] = NULL;
      }

      for (cs = fs->stmt_first; cs; cs = cs->next) {
            switch (cs->type) {
            case STMT_NONE:
                  assert(0);

            case STMT_NULL:
            case STMT_CASE:
            case STMT_DEFAULT:
            case STMT_WHILE:
            case STMT_DO_WHILE:
            case STMT_FOR:
            case STMT_BREAK:
            case STMT_CONTINUE:
            case STMT_BLOCK:
                  assert(0);

            case STMT_LABEL:
            case STMT_GOTO:
                  break;

            case STMT_EXPR:
            case STMT_IF:
            case STMT_SWITCH:
                  declaration_alive_expr(cs, cs->expr0);
                  break;

            case STMT_RETURN:
                  if (cs->expr0) {
                        declaration_alive_expr(cs, cs->expr0);
                  }
                  break;

            case STMT_ASM:
                  break;

            case STMT_VA_START:
                  declaration_alive_lhs_expr(cs, cs->expr0);
                  declaration_alive_rhs_expr(cs, cs->expr1);
                  break;

            case STMT_VA_END:
                  break;

            default:
                  assert(0);
            }

            /* All statements might have constraints... */
            if (cs->output) {
                  for (c = cs->output->first; c; c = c->next) {
                        assert(c->string[0] == '=');
                        assert(c->expr->type == EXPR_IDENTIFIER);

                        declaration_alive_lhs_expr(cs, c->expr);
                  }
            }
            if (cs->input) {
                  for (c = cs->input->first; c; c = c->next) {
                        assert(c->string[0] != '=');
                        declaration_alive_rhs_expr(cs, c->expr);
                  }
            }
      }

      stmt_opt_label_hashlist(fs);

      do {
            done = 1;

            /* Iterate bottom up! */
            for (cs = fs->stmt_last; cs; cs = cs->prev) {
                  done &= declaration_alive_merge0(cs);

                  switch (cs->type) {
                  case STMT_NONE:
                        assert(0);
                  case STMT_NULL:
                  case STMT_CASE:
                  case STMT_DEFAULT:
                  case STMT_WHILE:
                  case STMT_DO_WHILE:
                  case STMT_FOR:
                  case STMT_BREAK:
                  case STMT_CONTINUE:
                  case STMT_BLOCK:
                        assert(0);

                  case STMT_LABEL:
                        assert(cs->stmt0->type == STMT_NULL);
                        /*FALLTHROUGH*/
                  case STMT_ASM:
                  case STMT_VA_START:
                  case STMT_VA_END:
                        if (cs->next) {
                              done &= declaration_alive_merge1(cs,
                                          cs->next);
                        }
                        break;

                  case STMT_EXPR:
                        if (cs->expr0->type != EXPR_FUNC
                         || cs->expr0->expr0->type != EXPR_IDENTIFIER
                         || ! cs->expr0->expr0->declaration->attr_noreturn) {
                              if (cs->next) {
                                    done &= declaration_alive_merge1(
                                          cs, cs->next);
                              }
                        }
                        break;

                  case STMT_IF:
                        if (cs->next) {
                              done &= declaration_alive_merge1(cs,
                                          cs->next);
                        }
                        target = stmt_opt_label_lookup(
                                    cs->stmt0->label);
                        done &= declaration_alive_merge1(cs,
                                    target);
                        break;

                  case STMT_SWITCH:
                        for (ss = cs->stmt0->stmt_first;
                            ss;
                            ss = ss->next) {
                              target = stmt_opt_label_lookup(
                                          ss->stmt0->label);
                              done &= declaration_alive_merge1(cs,
                                          target);
                        }
                        break;

                  case STMT_GOTO:
                        target = stmt_opt_label_lookup(cs->label);
                        done &= declaration_alive_merge1(cs,
                                    target);
                        break;

                  case STMT_RETURN:
                        /* No next statement. */
                        break;

                  default:
                        assert(0);
                  }
            }
      } while (! done);

#if 0
      print_stmt(stderr, 1, 0, fs);
      fprintf(stderr, "\n");
#endif

      if (fs->stmt_first
       && fs->stmt_first->decl_live_first[0]) {
            struct decl_live *l;

            fprintf(stderr, "Live variables at start of function:\n");
            for (l = fs->stmt_first->decl_live_first[0]; l; l = l->next) {
                  fprintf(stderr, "\t%s\n", l->decl->identifier);
            }
      }

      /*
       * Build conflict matrix.
       */
      for (cs = fs->stmt_first; cs; cs = cs->next) {
            if (cs->output) {
                  for (c = cs->output->first; c; c = c->next) {
                        assert(c->string[0] == '=');
                        assert(c->expr->type == EXPR_IDENTIFIER);

                        if (c->string[1] == '&') {
                              struct constraint *c1;

                              assert(cs->input);
                              for (c1 = cs->input->first;
                                  c1;
                                  c1 = c1->next) {
                                    if (c1->expr->type == EXPR_IDENTIFIER) {
                                          decl_conflict_add(c->expr->declaration,
                                                      c1->expr->declaration);
                                    }
                              }
                        }
                  }
            }
            if (cs->change) {
                  for (c = cs->change->first; c; c = c->next) {
                        enum type_type type;
                        unsigned int class;
                        struct declaration *var;

                        if (strcmp(c->string, "cc") == 0
                         || strcmp(c->string, "memory") == 0) {
                              continue;
                        }

                        decl_reg_to_type_and_class(c->string,
                                    &type, &class);

                        var = simplify_declaration_add(fs->scope,
                                    type_gen(type),
                                    identifier_tmp());
                        var->storage = STORAGE_AUTO;
                        var->storage_class = class;

                        /* decl_live_add(cs, 0, var); Correct? */
                        decl_live_add(cs, 1, var);
                  }
            }
      }
      for (cs = fs->stmt_first; cs; cs = cs->next) {
            struct decl_live *l0;
            struct decl_live *l1;

            for (l0 = cs->decl_live_first[0]; l0; l0 = l0->next) {
                  for (l1 = l0->next; l1; l1 = l1->next) {
                        decl_conflict_add(l0->decl, l1->decl);
                  }
            }
            for (l0 = cs->decl_live_first[1]; l0; l0 = l0->next) {
                  for (l1 = l0->next; l1; l1 = l1->next) {
                        decl_conflict_add(l0->decl, l1->decl);
                  }
            }
      }

#if 0
      print_stmt(stderr, 1, 0, fs);
      fprintf(stderr, "\n");
#endif
#if 0
      /*
       * Print conflict matrix.
       */
      for (dion = fs->scope->declaration_first; dion; dion = dion->next) {
            struct decl_live *l;

            if (dion->storage != STORAGE_AUTO
             && dion->storage != STORAGE_REGISTER) {
                  continue;
            }
            fprintf(stderr, "%s:", dion->identifier);
            for (l = dion->conflict_first; l; l = l->next) {
                  fprintf(stderr, " %s", l->decl->identifier);
            }
            fprintf(stderr, "\n");
      }
#endif

      /*
       * Calculate spill costs.
       */
      for (cs = fs->stmt_first; cs; cs = cs->next) {
            struct decl_live *l;

            for (l = cs->decl_write_first; l; l = l->next) {
                  l->decl->spills++;
            }
            for (l = cs->decl_read_first; l; l = l->next) {
                  l->decl->spills++;
            }
      }

      /*
       * Build move matrix.
       */
      for (cs = fs->stmt_first; cs; cs = cs->next) {
            if (cs->type == STMT_EXPR
             && cs->expr0->type == EXPR_ASSIGN
             && cs->expr0->expr0->type == EXPR_IDENTIFIER
             && (cs->expr0->expr0->declaration->storage == STORAGE_AUTO
              || cs->expr0->expr0->declaration->storage == STORAGE_REGISTER)
             && cs->expr0->expr1->type == EXPR_IDENTIFIER
             && (cs->expr0->expr1->declaration->storage == STORAGE_AUTO
              || cs->expr0->expr1->declaration->storage == STORAGE_REGISTER)) {
                  decl_move_add(cs->expr0->expr0->declaration,
                              cs->expr0->expr1->declaration);
            }
      }

      /*
       * Initialize class counts.
       */
      for (dion = fs->scope->declaration_first; dion;  dion = dion->next) {
            struct decl_live *l;

            decl_color_init(dion->reg_count);
            for (l = dion->conflict_first; l; l = l->next) {
                  decl_color_add(dion->reg_count, l->decl->storage_class,
                              l->decl->type_name->type);
            }
      }

      /*
       * Try to assign registers.
       */
      stack_first = NULL;
      stack_last = NULL;

      for (;;) {
            unsigned int count[DECL_CLASS_COUNT];
            struct declaration *seldion;
            unsigned int seldegree;
            struct decl_live *l0;

            /*
             * Select variable to be removed from list.
             */
      again:      ;
            /* Simplify */
            for (dion = fs->scope->declaration_first;
                dion;
                dion = dion->next) {
                  int check;

                  if (dion->storage != STORAGE_AUTO
                   && dion->storage != STORAGE_REGISTER) {
                        continue;
                  }

                  if (dion->move_first) {
                        /* Ignore move related nodes. */
                        continue;
                  }

                  decl_color_init(count);
                  for (l0 = dion->conflict_first; l0; l0 = l0->next) {
                        decl_color_add(count, l0->decl->storage_class,
                                    l0->decl->type_name->type);
                  }
                  check = decl_color_check(count, dion->storage_class,
                              dion->type_name->type);
                  if (check) {
                        seldion = dion;
                        goto selected;
                  }
            }

            /* Coalesce */
            seldion = NULL;
            for (dion = fs->scope->declaration_first;
                dion;
                dion = dion->next) {
                  if (dion->storage != STORAGE_AUTO
                   && dion->storage != STORAGE_REGISTER) {
                        continue;
                  }

                  for (l0 = dion->move_first; l0; l0 = l0->next) {
                        if (decl_is_element(dion->conflict_first,
                                    l0->decl)) {
                              continue;
                        }
                        if (! decl_can_coalesce(dion, l0->decl)) {
                              continue;
                        }
                        seldion = dion;
                        break;
                  }

                  if (seldion) {
                        decl_coalesce(seldion, l0->decl);
                        break;
                  }
            }
            if (seldion) {
                  goto selected;
            }

            /* Freeze */
            for (dion = fs->scope->declaration_first;
                dion;
                dion = dion->next) {
                  int check;

                  if (dion->storage != STORAGE_AUTO
                   && dion->storage != STORAGE_REGISTER) {
                        continue;
                  }

                  if (! dion->move_first) {
                        continue;
                  }

                  decl_color_init(count);
                  for (l0 = dion->conflict_first; l0; l0 = l0->next) {
                        decl_color_add(count, l0->decl->storage_class,
                                    l0->decl->type_name->type);
                  }
                  check = decl_color_check(count, dion->storage_class,
                              dion->type_name->type);
                  if (check) {
                        /* Remove "move" info. */
                        while (dion->move_first) {
                              decl_move_remove(dion,
                                          dion->move_first->decl);
                        }
                        goto again;
                  }
            }

            /* Spill */
            seldion = NULL;
            seldegree = 0;
            for (dion = fs->scope->declaration_first;
                dion;
                dion = dion->next) {
                  if (dion->storage != STORAGE_AUTO
                   && dion->storage != STORAGE_REGISTER) {
                        continue;
                  }

#if 0
                  if (dion->move_first) {
                        /* Ignore move related nodes. */
                        continue;
                  }
#endif

                  if (dion->storage_mem) {
                        if (! seldion
                         || seldegree < decl_count(dion->conflict_first)) {
                              seldion = dion;
                              seldegree = decl_count(dion->conflict_first);
                        }
                  }
            }
            if (seldion) {
                  goto selected;
            }

            /* No more variables left. */
            break;

      selected:;
            /*
             * Remove variable from list.
             */
            if (seldion->prev) {
                  seldion->prev->next = seldion->next;
            } else {
                  fs->scope->declaration_first = seldion->next;
            }
            if (seldion->next) {
                  seldion->next->prev = seldion->prev;
            } else {
                  fs->scope->declaration_last = seldion->prev;
            }

            /*
             * Add to operation stack.
             */
            seldion->prev = stack_last;
            seldion->next = NULL;
            if (seldion->prev) {
                  seldion->prev->next = seldion;
            } else {
                  stack_first = seldion;
            }
            stack_last = seldion;

            /*
             * Remove move info.
             */
            while (seldion->move_first) {
                  decl_move_remove(seldion,
                              seldion->move_first->decl);
            }

            /*
             * Move variable from conflict list of neighbours
             * to their conflict_save list.
             */
            for (l0 = seldion->conflict_first; l0; l0 = l0->next) {
                  struct declaration *n;

                  n = l0->decl;

                  /* Remove variable from conflict list. */
                  decl_remove(&n->conflict_first,
                        &n->conflict_last, seldion);

                  /* Add variable to conflict_save list. */
                  decl_add(&n->conflict_save_first,
                        &n->conflict_save_last, seldion);
            }
      }

      /* All variables must be on stack. */
#if 1
      for (dion = fs->scope->declaration_first;
          dion;
          dion = dion->next) {
            struct decl_live *l;

            if (dion->storage != STORAGE_AUTO
             && dion->storage != STORAGE_REGISTER) {
                  continue;
            }
            for (i = 0; ; i++) {
                  assert(i < 256);
                  if (classinfo[i] == dion->storage_class) {
                        break;
                  }
            }
            fprintf(stderr, "%s (class: \"%c\", type: %s, mem: %u):",
                        dion->identifier,
                        i,
                        type_info[dion->type_name->type],
                        dion->storage_mem);
            for (l = dion->conflict_first; l; l = l->next) {
                  fprintf(stderr, " %s", l->decl->identifier);
            }
            fprintf(stderr, "\n");
      }
#endif
      for (dion = fs->scope->declaration_first;
          dion;
          dion = dion->next) {
            if (dion->storage != STORAGE_AUTO
             && dion->storage != STORAGE_REGISTER) {
                  continue;
            }
            assert(0);
      }

      while (stack_last) {
            struct decl_live *l0;
            int reg;

            dion = stack_last;

            /*
             * Remove variable from stack.
             */
            if (dion->prev) {
                  dion->prev->next = dion->next;
            } else {
                  stack_first = dion->next;
            }
            assert(! dion->next);
            stack_last = dion->prev;

            /*
             * Re-add variable to variable list.
             */
            dion->prev = fs->scope->declaration_last;
            dion->next = NULL;
            if (dion->prev) {
                  dion->prev->next = dion;
            } else {
                  fs->scope->declaration_first = dion;
            }
            fs->scope->declaration_last = dion;

            /*
             * Move variable from conflict_save list of neighbours
             * to their conflict list.
             */
            for (l0 = dion->conflict_first; l0; l0 = l0->next) {
                  struct declaration *n;

                  n = l0->decl;

                  /* Remove variable from conflict_save list. */
                  decl_remove(&n->conflict_save_first,
                        &n->conflict_save_last, dion);

                  /* Add variable to conflict list. */
                  decl_add(&n->conflict_first,
                        &n->conflict_last, dion);
            }

            if (dion->clone) {
                  dion->storage_register = dion->clone->storage_register;
                  dion->storage = dion->clone->storage;

                  dion->clone = NULL;

            } else {
                  /* Assign register. */
                  decl_reg_init(dion->reg_count);

                  for (l0 = dion->conflict_first; l0; l0 = l0->next) {
                        if (l0->decl->storage_register != DECL_MEMORY) {
                              decl_reg_add(dion->reg_count,
                                    l0->decl->storage_register);
                        }
                  }

                  reg = decl_reg_get(dion->reg_count,
                              dion->storage_class,
                              dion->type_name->type);

                  if (0 <= reg) {
                        dion->storage_register = reg;
                        dion->storage = STORAGE_REGISTER;

                  } else if (dion->storage_mem) {
                        dion->storage_register = DECL_MEMORY;
                        dion->storage = STORAGE_AUTO;

                  } else {
                        for (i = 0; ; i++) {
                              assert(i < 256);
                              if (classinfo[i] == dion->storage_class) {
                                    break;
                              }
                        }
                        fprintf(stderr, "No register for %s found (class \"%c\", type %s).\n",
                                    dion->identifier,
                                    i,
                                    type_info[dion->type_name->type]);
                        for (l0 = dion->conflict_first; l0; l0 = l0->next) {
                              for (i = 0; ; i++) {
                                    assert(i < 256);
                                    if (classinfo[i] == l0->decl->storage_class) {
                                          break;
                                    }
                              }
                              fprintf(stderr, "%s: (class \"%c\", type %s): %s\n",
                                    l0->decl->identifier,
                                    i,
                                    type_info[l0->decl->type_name->type],
                                    reginfo[l0->decl->storage_register].name);
                        }
                        assert(0);
                  }
            }
#if 0
            if (dion->storage_register != DECL_MEMORY) {
                  fprintf(stderr, "%s: %s\n",
                              dion->identifier,
                              reginfo[dion->storage_register].name);
            } else {
                  fprintf(stderr, "%s: %s\n", dion->identifier, "memory");
            }
#endif
      }
}

Generated by  Doxygen 1.6.0   Back to index