Logo Search packages:      
Sourcecode: faucc version File versions

stmt.c

/* $Id: stmt.c,v 1.65 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 "identifier.h"
#include "expr.h"
#include "stmt.h"
#include "simplify.h"

#define countof(x)      (sizeof(x) / sizeof(x[0]))


static int stmt_change;


static void
stmt_check(struct stmt *s)
{
      struct stmt *cs;

      if (! s) {
            return;
      }

      if (s->stmt0) {
            stmt_check(s->stmt0);
      }
      if (s->stmt1) {
            stmt_check(s->stmt1);
      }
      for (cs = s->stmt_first; cs; cs = cs->next) {
            stmt_check(cs);
      }

      switch (s->type) {
      case STMT_LABEL:
            assert(s->label->def_first);
            assert(s->label->def_first == s->label->def_last);
            assert(s->label->def_first == s);
            break;
      case STMT_GOTO:
            assert(s->label->ref_first);
            assert(s->label->ref_last);
            assert(s->label->def_first);
            assert(s->label->def_first == s->label->def_last);
            break;
      default:
            break;
      }
}

void
stmt_rename_structunionenum(struct stmt *s, enum type_type type, const char *old, const char *new)
{
      struct stmt *cs;

      if (s->expr0) {
            expr_rename_structunionenum(s->expr0, type, old, new);
      }
      if (s->expr1) {
            expr_rename_structunionenum(s->expr1, type, old, new);
      }
      if (s->expr2) {
            expr_rename_structunionenum(s->expr2, type, old, new);
      }
      if (s->stmt0) {
            stmt_rename_structunionenum(s->stmt0, type, old, new);
      }
      if (s->stmt1) {
            stmt_rename_structunionenum(s->stmt1, type, old, new);
      }
      for (cs = s->stmt_first; cs; cs = cs->next) {
            stmt_rename_structunionenum(cs, type, old, new);
      }

      if (s->type == STMT_BLOCK) {
            struct declaration *dion;
            
            for (dion = s->scope->declaration_first; dion; dion = dion->next) {
                  declaration_rename_structunionenum(dion, type, old, new);
            }
      }
}

static void
stmt_replace_break(struct stmt *s, struct label *label)
{
      struct stmt *s1;

      switch (s->type) {
      case STMT_NONE:
            assert(0);
      case STMT_NULL:
            break;
      case STMT_LABEL:
      case STMT_CASE:
      case STMT_DEFAULT:
            stmt_replace_break(s->stmt0, label);
            break;
      case STMT_EXPR:
            break;
      case STMT_IF:
            stmt_replace_break(s->stmt0, label);
            if (s->stmt1) {
                  stmt_replace_break(s->stmt1, label);
            }
            break;
      case STMT_SWITCH:
      case STMT_WHILE:
      case STMT_DO_WHILE:
      case STMT_FOR:
            break;
      case STMT_GOTO:
      case STMT_CONTINUE:
            break;
      case STMT_BREAK:
            stmt_cp(s, stmt_goto(label));
            stmt_change = 1;
            break;
      case STMT_RETURN:
      case STMT_ASM:
            break;
      case STMT_BLOCK:
            for (s1 = s->stmt_first; s1; s1 = s1->next) {
                  stmt_replace_break(s1, label);
            }
            break;
      default:
            assert(0);
      }
}

void
stmt_replace_continue(struct stmt *s, struct label *label)
{
      struct stmt *s1;

      switch (s->type) {
      case STMT_NONE:
            assert(0);
      case STMT_NULL:
            break;
      case STMT_LABEL:
      case STMT_CASE:
      case STMT_DEFAULT:
            stmt_replace_continue(s->stmt0, label);
            break;
      case STMT_EXPR:
            break;
      case STMT_IF:
            stmt_replace_continue(s->stmt0, label);
            if (s->stmt1) {
                  stmt_replace_continue(s->stmt1, label);
            }
            break;
      case STMT_SWITCH:
            stmt_replace_continue(s->stmt0, label);
            break;
      case STMT_WHILE:
      case STMT_DO_WHILE:
      case STMT_FOR:
            break;
      case STMT_GOTO:
            break;
      case STMT_CONTINUE:
            stmt_cp(s, stmt_goto(label));
            stmt_change = 1;
            break;
      case STMT_BREAK:
      case STMT_RETURN:
      case STMT_ASM:
            break;
      case STMT_BLOCK:
            for (s1 = s->stmt_first; s1; s1 = s1->next) {
                  stmt_replace_continue(s1, label);
            }
            break;
      default:
            assert(0);
      }
}

void
stmt_prepend_first(
      struct stmt *block,
      struct stmt *n0
)
{
      n0->prev = NULL;
      n0->next = block->stmt_first;

      block->stmt_first = n0;
      if (n0->next) {
            n0->next->prev = n0;
      } else {
            block->stmt_last = n0;
      }
}

void
stmt_prepend(
      struct stmt *block,
      struct stmt *o0,
      struct stmt *n0
)
{
      if (o0) {
            n0->prev = o0->prev;
            n0->next = o0;
      } else {
            n0->prev = NULL;
            n0->next = NULL;
      }
      if (n0->prev) {
            n0->prev->next = n0;
      } else {
            block->stmt_first = n0;
      }
      if (n0->next) {
            n0->next->prev = n0;
      } else {
            block->stmt_last = n0;
      }
}

void
stmt_append(
      struct stmt *block,
      struct stmt *o0,
      struct stmt *n0
)
{
      if (o0) {
            n0->prev = o0;
            n0->next = o0->next;
      } else {
            n0->prev = NULL;
            n0->next = NULL;
      }
      if (n0->prev) {
            n0->prev->next = n0;
      } else {
            block->stmt_first = n0;
      }
      if (n0->next) {
            n0->next->prev = n0;
      } else {
            block->stmt_last = n0;
      }
}

void
stmt_append_last(
      struct stmt *block,
      struct stmt *n0
)
{
      n0->prev = block->stmt_last;
      n0->next = NULL;

      if (n0->prev) {
            n0->prev->next = n0;
      } else {
            block->stmt_first = n0;
      }
      block->stmt_last = n0;
}

static void
stmt_free_contents(struct stmt *s)
{
      switch (s->type) {
      case STMT_LABEL:
            label_def_del(s->label, s);
            break;
      case STMT_GOTO:
            label_ref_del(s->label, s);
            break;
      default:
            /* FIXME */
            break;
      }
      if (s->stmt0) {
            stmt_free(s->stmt0);
      }
      if (s->stmt1) {
            stmt_free(s->stmt1);
      }
      while (s->stmt_first) {
            struct stmt *act;

            act = s->stmt_first;

            s->stmt_first = act->next;
            if (act->next) {
                  act->next->prev = act->prev;
            } else {
                  s->stmt_last = act->prev;
            }

            stmt_free(act);
      }
}

void
stmt_free(struct stmt *s)
{
      /* Free contents. */
      stmt_free_contents(s);

      /* Free struct. */
      free(s);
}

void
stmt_cp(struct stmt *o, struct stmt *n)
{
      /* Free old contents. */
      stmt_free_contents(o);

      /* Copy new contents to old struct. */
      o->type = n->type;
      o->label = n->label;
      if (o->type == STMT_LABEL) {
            label_def_del(n->label, n);
            label_def_add(o->label, o);
      } else if (o->type == STMT_GOTO) {
            label_ref_del(n->label, n);
            label_ref_add(o->label, o);
      }
      o->expr0 = n->expr0;
      o->expr1 = n->expr1;
      o->expr2 = n->expr2;
      o->stmt0 = n->stmt0;
      o->stmt1 = n->stmt1;
      o->code_len = n->code_len;
      o->code = n->code;
      o->output = n->output;
      o->input = n->input;
      o->change = n->change;
      o->stmt_first = n->stmt_first;
      o->stmt_last = n->stmt_last;
      o->scope = n->scope;

      o->jit = n->jit;

      /* Free new struct. */
      free(n);
}

void
stmt_replace_1_by_0(
      struct stmt *block,
      struct stmt *o0
)
{
      if (o0->prev) {
            o0->prev->next = o0->next;
      } else {
            block->stmt_first = o0->next;
      }
      if (o0->next) {
            o0->next->prev = o0->prev;
      } else {
            block->stmt_last = o0->prev;
      }

      stmt_free(o0);
}

void
stmt_replace_1_by_1(
      struct stmt *block,
      struct stmt *o0,
      struct stmt *n0
)
{
      n0->prev = o0->prev;
      n0->next = o0->next;

      if (n0->prev) {
            n0->prev->next = n0;
      } else {
            block->stmt_first = n0;
      }
      if (n0->next) {
            n0->next->prev = n0;
      } else {
            block->stmt_last = n0;
      }

      stmt_free(o0);
}

void
stmt_replace_1_by_2(
      struct stmt *block,
      struct stmt *o0,
      struct stmt *n0,
      struct stmt *n1
)
{
      n0->prev = o0->prev;
      n0->next = n1;
      n1->prev = n0;
      n1->next = o0->next;

      if (n0->prev) {
            n0->prev->next = n0;
      } else {
            block->stmt_first = n0;
      }
      if (n1->next) {
            n1->next->prev = n1;
      } else {
            block->stmt_last = n1;
      }

      stmt_free(o0);
}

void
stmt_replace_1_by_3(
      struct stmt *block,
      struct stmt *o0,
      struct stmt *n0,
      struct stmt *n1,
      struct stmt *n2
)
{
      n0->prev = o0->prev;
      n0->next = n1;
      n1->prev = n0;
      n1->next = n2;
      n2->prev = n1;
      n2->next = o0->next;

      if (n0->prev) {
            n0->prev->next = n0;
      } else {
            block->stmt_first = n0;
      }
      if (n2->next) {
            n2->next->prev = n2;
      } else {
            block->stmt_last = n2;
      }

      stmt_free(o0);
}

void
stmt_replace_1_by_4(
      struct stmt *block,
      struct stmt *o0,
      struct stmt *n0,
      struct stmt *n1,
      struct stmt *n2,
      struct stmt *n3
)
{
      n0->prev = o0->prev;
      n0->next = n1;
      n1->prev = n0;
      n1->next = n2;
      n2->prev = n1;
      n2->next = n3;
      n3->prev = n2;
      n3->next = o0->next;

      if (n0->prev) {
            n0->prev->next = n0;
      } else {
            block->stmt_first = n0;
      }
      if (n3->next) {
            n3->next->prev = n3;
      } else {
            block->stmt_last = n3;
      }

      stmt_free(o0);
}

void
stmt_replace_1_by_5(
      struct stmt *block,
      struct stmt *o0,
      struct stmt *n0,
      struct stmt *n1,
      struct stmt *n2,
      struct stmt *n3,
      struct stmt *n4
)
{
      n0->prev = o0->prev;
      n0->next = n1;
      n1->prev = n0;
      n1->next = n2;
      n2->prev = n1;
      n2->next = n3;
      n3->prev = n2;
      n3->next = n4;
      n4->prev = n3;
      n4->next = o0->next;

      if (n0->prev) {
            n0->prev->next = n0;
      } else {
            block->stmt_first = n0;
      }
      if (n4->next) {
            n4->next->prev = n4;
      } else {
            block->stmt_last = n4;
      }

      stmt_free(o0);
}

void
stmt_replace_1_by_6(
      struct stmt *block,
      struct stmt *o0,
      struct stmt *n0,
      struct stmt *n1,
      struct stmt *n2,
      struct stmt *n3,
      struct stmt *n4,
      struct stmt *n5
)
{
      n0->prev = o0->prev;
      n0->next = n1;
      n1->prev = n0;
      n1->next = n2;
      n2->prev = n1;
      n2->next = n3;
      n3->prev = n2;
      n3->next = n4;
      n4->prev = n3;
      n4->next = n5;
      n5->prev = n4;
      n5->next = o0->next;

      if (n0->prev) {
            n0->prev->next = n0;
      } else {
            block->stmt_first = n0;
      }
      if (n5->next) {
            n5->next->prev = n5;
      } else {
            block->stmt_last = n5;
      }

      stmt_free(o0);
}

void
stmt_replace_1_by_7(
      struct stmt *block,
      struct stmt *o0,
      struct stmt *n0,
      struct stmt *n1,
      struct stmt *n2,
      struct stmt *n3,
      struct stmt *n4,
      struct stmt *n5,
      struct stmt *n6
)
{
      n0->prev = o0->prev;
      n0->next = n1;
      n1->prev = n0;
      n1->next = n2;
      n2->prev = n1;
      n2->next = n3;
      n3->prev = n2;
      n3->next = n4;
      n4->prev = n3;
      n4->next = n5;
      n5->prev = n4;
      n5->next = n6;
      n6->prev = n5;
      n6->next = o0->next;

      if (n0->prev) {
            n0->prev->next = n0;
      } else {
            block->stmt_first = n0;
      }
      if (n6->next) {
            n6->next->prev = n6;
      } else {
            block->stmt_last = n6;
      }

      stmt_free(o0);
}

void
stmt_replace_1_by_8(
      struct stmt *block,
      struct stmt *o0,
      struct stmt *n0,
      struct stmt *n1,
      struct stmt *n2,
      struct stmt *n3,
      struct stmt *n4,
      struct stmt *n5,
      struct stmt *n6,
      struct stmt *n7
)
{
      n0->prev = o0->prev;
      n0->next = n1;
      n1->prev = n0;
      n1->next = n2;
      n2->prev = n1;
      n2->next = n3;
      n3->prev = n2;
      n3->next = n4;
      n4->prev = n3;
      n4->next = n5;
      n5->prev = n4;
      n5->next = n6;
      n6->prev = n5;
      n6->next = n7;
      n7->prev = n6;
      n7->next = o0->next;

      if (n0->prev) {
            n0->prev->next = n0;
      } else {
            block->stmt_first = n0;
      }
      if (n7->next) {
            n7->next->prev = n7;
      } else {
            block->stmt_last = n7;
      }

      stmt_free(o0);
}

void
stmt_replace_1_by_9(
      struct stmt *block,
      struct stmt *o0,
      struct stmt *n0,
      struct stmt *n1,
      struct stmt *n2,
      struct stmt *n3,
      struct stmt *n4,
      struct stmt *n5,
      struct stmt *n6,
      struct stmt *n7,
      struct stmt *n8
)
{
      n0->prev = o0->prev;
      n0->next = n1;
      n1->prev = n0;
      n1->next = n2;
      n2->prev = n1;
      n2->next = n3;
      n3->prev = n2;
      n3->next = n4;
      n4->prev = n3;
      n4->next = n5;
      n5->prev = n4;
      n5->next = n6;
      n6->prev = n5;
      n6->next = n7;
      n7->prev = n6;
      n7->next = n8;
      n8->prev = n7;
      n8->next = o0->next;

      if (n0->prev) {
            n0->prev->next = n0;
      } else {
            block->stmt_first = n0;
      }
      if (n8->next) {
            n8->next->prev = n8;
      } else {
            block->stmt_last = n8;
      }

      stmt_free(o0);
}

struct stmt *
stmt_replace_2_by_1(
      struct stmt *block,
      struct stmt *o0,
      struct stmt *n0
)
{
      struct stmt *next;

      next = o0->next->next;

      n0->prev = o0->prev;
      n0->next = o0->next->next;
      if (n0->prev) {
            n0->prev->next = n0;
      } else {
            block->stmt_first = n0;
      }
      if (n0->next) {
            n0->next->prev = n0;
      } else {
            block->stmt_last = n0;
      }

      stmt_free(o0->next);
      stmt_free(o0);

      return next;
}

struct stmt *
stmt_new(void)
{
      struct stmt *s;

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

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

      return s;
}

struct stmt *
stmt_dup(struct stmt *o)
{
      struct stmt *co;
      struct stmt *n;
      struct stmt *cn;

      if (o == NULL) {
            return NULL;
      }

      n = stmt_new();

      n->type = o->type;
      if (o->label
       && o->label->clone) {
            n->label = o->label->clone;
      } else {
            n->label = o->label;
      }
      if (n->type == STMT_LABEL) {
            label_def_add(n->label, n);
      } else if (n->type == STMT_GOTO) {
            label_ref_add(n->label, n);
      }
      n->expr0 = expr_dup(o->expr0);
      n->expr1 = expr_dup(o->expr1);
      n->expr2 = expr_dup(o->expr2);
      n->stmt0 = stmt_dup(o->stmt0);
      n->stmt1 = stmt_dup(o->stmt1);
      n->code_len = o->code_len;
      n->code = identifier_dup(o->code);
      n->output = constraint_list_dup(o->output);
      n->input = constraint_list_dup(o->input);
      n->change = constraint_list_dup(o->change);
      n->stmt_first = NULL;
      n->stmt_last = NULL;
      for (co = o->stmt_first; co; co = co->next) {
            cn = stmt_dup(co);

            cn->prev = n->stmt_last;
            cn->next = NULL;
            if (cn->prev) {
                  cn->prev->next = cn;
            } else {
                  n->stmt_first = cn;
            }
            n->stmt_last = cn;
      }
      n->scope = o->scope;
      n->jit = o->jit;

      return n;
}

struct stmt *
stmt_null(void)
{
      struct stmt *s;

      s = stmt_new();

      s->type = STMT_NULL;

      return s;
}

struct stmt *
stmt_label(struct label *label, struct stmt *s0)
{
      struct stmt *s;

      s = stmt_new();

      s->type = STMT_LABEL;
      s->label = label;
      s->stmt0 = s0;

      label_def_add(label, s);

      return s;
}

struct stmt *
stmt_expr(struct expr *e)
{
      struct stmt *s;

      assert(e);

      s = stmt_new();

      s->type = STMT_EXPR;
      s->expr0 = e;

      return s;
}

struct stmt *
stmt_if(struct expr *e, struct stmt *s0, struct stmt *s1)
{
      struct stmt *s;

      assert(e);
      assert(s0);
      /* s1 might be NULL. */

      s = stmt_new();

      s->type = STMT_IF;
      s->expr0 = e;
      s->stmt0 = s0;
      s->stmt1 = s1;

      return s;
}

struct stmt *
stmt_goto(struct label *label)
{
      struct stmt *s;

      s = stmt_new();

      s->type = STMT_GOTO;
      s->label = label;

      label_ref_add(label, s);

      return s;
}

struct stmt *
stmt_return(struct expr *expr)
{
      struct stmt *s;

      s = stmt_new();

      s->type = STMT_RETURN;
      s->expr0 = expr;

      return s;
}

/* ------------------------------------------------------------------------- */

int
stmt_simplify_params(struct stmt *fs)
{
      struct declaration *oparam;
      struct declaration *nparam;
      struct declaration *prev;
      struct type *t;
      struct stmt *s;

      for (oparam = fs->scope->function->type_name->parameter->declaration_last;
          oparam;
          oparam = prev) {
            prev = oparam->prev;

            switch (oparam->type_name->type) {
            case TYPE_NONE:
            case TYPE_MAX:
                  assert(0);
            case TYPE_ELIPSIS:
                  continue;
            case TYPE_VOID:
                  continue;
            case TYPE_VA_LIST:
            case TYPE_POINTER:
            case TYPE_ENUM:
                  /* Copy as is... */
                  t = oparam->type_name;
                  goto copy;
            case TYPE_INT8:
            case TYPE_UINT8:
            case TYPE_INT16:
            case TYPE_UINT16:
            case TYPE_INT32:
            case TYPE_UINT32:
            case TYPE_INT64:
            case TYPE_UINT64:
            case TYPE_FLOAT32:
            case TYPE_FLOAT64:
            case TYPE_FLOAT80:
                  /* Copy as arithmetic type... */
                  t = type_arithmetic(oparam->type_name, oparam->type_name);

            copy: ;
                  nparam = declaration_identifier(identifier_tmp());
                  nparam->storage = STORAGE_PARAM;
                  nparam->type_name = t;

                  nparam->prev = oparam->prev;
                  nparam->next = oparam->next;
                  if (nparam->prev) {
                        nparam->prev->next = nparam;
                  } else {
                        fs->scope->function->type_name->parameter->declaration_first = nparam;
                  }
                  if (nparam->next) {
                        nparam->next->prev = nparam;
                  } else {
                        fs->scope->function->type_name->parameter->declaration_last = nparam;
                  }

                  oparam->storage = STORAGE_AUTO;

                  oparam->prev = NULL;
                  oparam->next = fs->scope->declaration_first;
                  fs->scope->declaration_first = oparam;
                  if (oparam->next) {
                        oparam->next->prev = oparam;
                  } else {
                        fs->scope->declaration_last = oparam;
                  }

                  if (t == oparam->type_name) {
                        s = stmt_expr(expr_assign(
                              expr_identifier(oparam),
                              expr_identifier(nparam)));
                  } else {
                        s = stmt_expr(expr_assign(
                              expr_identifier(oparam),
                              expr_cast(oparam->type_name,
                                    expr_identifier(nparam))));
                  }
                  stmt_prepend_first(fs, s);
                  break;

            case TYPE_STRUCT:
            case TYPE_UNION:
                  /* Leave as is... */
                  break;

            case TYPE_ARRAY:
            case TYPE_FUNCTION:
                  assert(0);
            }
      }

      return 1;
}

int
stmt_simplify_returns(struct stmt *fs)
{
      struct stmt *cs;
      struct type *type;
      struct declaration *var;
      struct label *label;
      struct stmt *s0;
      struct stmt *s1;

      assert(fs->type == STMT_BLOCK);

      if (fs->scope->function->attr_noreturn) {
            return 0;
      }

      type = fs->scope->function->type_name;
      type = type_call(type);
      type = type_pure(type);

      if (type->type == TYPE_VOID) {
            var = NULL;
      } else {
            var = simplify_declaration_add(fs->scope,
                        type, identifier_tmp());
      }
      label = label_new(identifier_tmp());

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

            next = cs->next;

            if (cs->type == STMT_RETURN) {
                  if (cs->expr0) {
                        assert(var);

                        s0 = stmt_expr(expr_assign(
                                    expr_identifier(var),
                                    expr_dup(cs->expr0)));
                        s1 = stmt_goto(label);

                        stmt_replace_1_by_2(fs, cs, s0, s1);
                  } else {
                        assert(! var);

                        s0 = stmt_goto(label);

                        stmt_replace_1_by_1(fs, cs, s0);
                  }
            }

            cs = next;
      }

      s0 = stmt_label(label, stmt_null());
      if (var) {
            s1 = stmt_return(expr_identifier(var));
      } else {
            s1 = stmt_return(NULL);
      }

      stmt_append(fs, fs->stmt_last, s0);
      stmt_append(fs, fs->stmt_last, s1);

      return 1;
}

static struct stmt *
simplify_get_case_stmt(struct stmt *s)
{
      struct stmt *cs;
      struct stmt *res;

      switch (s->type) {
      case STMT_NONE:
            assert(0);
      case STMT_NULL:
            return NULL;
      case STMT_LABEL:
            return simplify_get_case_stmt(s->stmt0);
      case STMT_CASE:
            return s;
      case STMT_DEFAULT:
            return simplify_get_case_stmt(s->stmt0);
      case STMT_EXPR:
            return NULL;
      case STMT_IF:
            res = simplify_get_case_stmt(s->stmt0);
            if (res) {
                  return res;
            }
            if (s->stmt1) {
                  res = simplify_get_case_stmt(s->stmt1);
                  if (res) {
                        return res;
                  }
            }
            return NULL;
      case STMT_SWITCH:
            return NULL;
      case STMT_WHILE:
      case STMT_DO_WHILE:
      case STMT_FOR:
            return simplify_get_case_stmt(s->stmt0);
      case STMT_GOTO:
      case STMT_BREAK:
      case STMT_CONTINUE:
      case STMT_RETURN:
      case STMT_ASM:
      case STMT_VA_START:
      case STMT_VA_END:
            return NULL;
      case STMT_BLOCK:
            for (cs = s->stmt_first; cs; cs = cs->next) {
                  res = simplify_get_case_stmt(cs);
                  if (res) {
                        return res;
                  }
            }
            return NULL;
      default:
            assert(0);
      }
      assert(0);
}

static struct stmt *
simplify_get_default_stmt(struct stmt *s)
{
      struct stmt *cs;
      struct stmt *res;

      switch (s->type) {
      case STMT_NONE:
            assert(0);
      case STMT_NULL:
            return NULL;
      case STMT_LABEL:
            return simplify_get_default_stmt(s->stmt0);
      case STMT_CASE:
            return simplify_get_default_stmt(s->stmt0);
      case STMT_DEFAULT:
            return s;
      case STMT_EXPR:
            return NULL;
      case STMT_IF:
            res = simplify_get_default_stmt(s->stmt0);
            if (res) {
                  return res;
            }
            if (s->stmt1) {
                  res = simplify_get_default_stmt(s->stmt1);
                  if (res) {
                        return res;
                  }
            }
            return NULL;
      case STMT_SWITCH:
            return NULL;
      case STMT_WHILE:
      case STMT_DO_WHILE:
      case STMT_FOR:
            return simplify_get_default_stmt(s->stmt0);
      case STMT_GOTO:
      case STMT_BREAK:
      case STMT_CONTINUE:
      case STMT_RETURN:
      case STMT_ASM:
      case STMT_VA_START:
      case STMT_VA_END:
            return NULL;
      case STMT_BLOCK:
            for (cs = s->stmt_first; cs; cs = cs->next) {
                  res = simplify_get_default_stmt(cs);
                  if (res) {
                        return res;
                  }
            }
            return NULL;
      default:
            assert(0);
      }
      assert(0);
}

static int
simplify_switch_ifgotoswitch_check(struct stmt *s)
{
      struct stmt *s0;
      int default_seen;

      if (s->stmt0->scope->declaration_first) {
            return 0;
      }
      default_seen = 0;
      for (s0 = s->stmt0->stmt_first; s0; s0 = s0->next) {
            if (s0->type == STMT_CASE) {
                  if (default_seen) {
                        return 0;
                  }
            } else if (s0->type == STMT_DEFAULT) {
                  default_seen = 1;
            } else {
                  return 0;
            }
            if (! s0->stmt0
             || s0->stmt0->type != STMT_GOTO) {
                  return 0;
            }
      }
      return default_seen;
}

static void
stmt_sim_in_stmt(struct stmt *block, struct stmt *s)
{
      struct label *label0;
      struct label *label1;
      struct label *label2;
      struct label *label3;
      struct stmt *s0;
      struct stmt *s1;
      struct stmt *s2;
      struct stmt *s3;
      struct stmt *s4;
      struct stmt *s5;
      struct stmt *s6;
      struct stmt *s7;
      struct stmt *s8;
      struct stmt *cs;

      switch (s->type) {
      case STMT_NONE:
            assert(0);

      case STMT_NULL:
            if (block) {
                  /*
                   * Replace
                   *          ;
                   * by
                   *          ---
                   */
                  stmt_replace_1_by_0(block, s);
                  stmt_change = 1;

                  stmt_check(block);
            }
            break;

      case STMT_LABEL:
            if (block
             && s->stmt0->type != STMT_NULL) {
                  /*
                   * Replace
                   *          l0:   s;
                   * by
                   *          l0:   ;
                   *                s;
                   */
                  s0 = stmt_label(s->label, stmt_null());
                  s1 = stmt_dup(s->stmt0);

                  stmt_replace_1_by_2(block, s, s0, s1);
                  stmt_change = 1;

                  stmt_check(block);
            }
            break;

      case STMT_CASE:
      case STMT_DEFAULT:
            assert(0);

      case STMT_EXPR:
            break;

      case STMT_IF:
            if (block
             && s->stmt0->type != STMT_GOTO
             && s->stmt1) {
                  /*
                   * Replace
                   *      if (e) s0;
                   *      else s1;
                   * by
                   *      0:        if (e) goto label0;
                   *      1:        s1;
                   *      2:        goto label1;
                   *      3:      label0: ;
                   *      4:        s0;
                   *      5:      label1: ;
                   */
                  label0 = label_new(identifier_tmp());
                  label1 = label_new(identifier_tmp());

                  s0 = stmt_if(expr_dup(s->expr0),
                              stmt_goto(label0), NULL);
                  s1 = stmt_dup(s->stmt1);
                  s2 = stmt_goto(label1);
                  s3 = stmt_label(label0, stmt_null());
                  s4 = stmt_dup(s->stmt0);
                  s5 = stmt_label(label1, stmt_null());

                  stmt_replace_1_by_6(block, s,
                              s0, s1, s2, s3, s4, s5);

                  stmt_change = 1;

                  stmt_check(block);
                  break;
            }

            if (block
             && s->stmt0->type != STMT_GOTO
             && ! s->stmt1) {
                  /*
                   * Replace
                   *      if (e) s0;
                   * by
                   *      0:        if (! e) goto label;
                   *      1:        s0;
                   *      2:      label:  ;
                   */
                  label0 = label_new(identifier_tmp());

                  s0 = stmt_if(expr_not(expr_dup(s->expr0)),
                              stmt_goto(label0), NULL);
                  s1 = stmt_dup(s->stmt0);
                  s2 = stmt_label(label0, stmt_null());

                  stmt_replace_1_by_3(block, s, s0, s1, s2);

                  stmt_change = 1;

                  stmt_check(block);
                  break;
            }
            break;

      case STMT_SWITCH:
                        if (! block
             || simplify_switch_ifgotoswitch_check(s)) {
                  goto simplify_switch_done;
            }

            /*
             * Replace
             *      switch (e) {
             *      case A: sA;
             *      case B: sB;
             *      ...
             *      default: sDefault;
             *      ...
             *      case N: sN;
             *      }
             * by
             *      0:              switch (e) {
             *      1:              case A:
             *      2:                    goto LA;
             *      3:              case B:
             *      4:                    goto LB;
             *      ..      .
             *      10:             case N:
             *      11:                   goto LN;
             *      20:             default:
             *      21:                   goto LDefault;
             *                      }
             *      30:             {
             *      31:             LA:
             *      32:                   sA;
             *      33:             LB:
             *      34:                   sB;
             *      ...
             *      40:             LDefault:
             *      41:                   sDefault;
             *      ...
             *      50:             LN:
             *      51:                   sN;
             *                      }
             *      60:       end:  ;
             *
             * Replace all "break;" by "goto end;"
             */
            label0 = label_new(identifier_tmp());

            stmt_replace_break(s->stmt0, label0);

            /* New Switch Statement */
            s0 = stmt_new();
            s0->type = STMT_SWITCH;
            s0->expr0 = s->expr0;
            s0->stmt0 = stmt_new();
            s0->stmt0->type = STMT_BLOCK;
            s0->stmt0->stmt_first = NULL;
            s0->stmt0->stmt_last = NULL;
            s0->stmt0->scope = s->stmt0->scope;

            /* New Block */
            s1 = stmt_dup(s->stmt0);

            /* end: Label */
            s2 = stmt_label(label0, stmt_null());

            /*
             * Replace "case" statements.
             */
            while ((s3 = simplify_get_case_stmt(s1)) != NULL) {
                  /* Replace by label. */
                  label1 = label_new(identifier_tmp());

                  /* Add new case statement to new switch. */
                  s4 = stmt_new();
                  s4->type = STMT_CASE;
                  s4->expr0 = expr_dup(s3->expr0);
                  s4->stmt0 = stmt_goto(label1);

                  stmt_prepend_first(s0->stmt0, s4);

                  /* Replace old case statement by new label. */
                  s4 = stmt_label(label1, stmt_null());
                  s5 = stmt_dup(s3->stmt0);

                  stmt_replace_1_by_2(s1, s3, s4, s5);
            }

            /*
             * Replace "default" statement (if present).
             */
            s3 = simplify_get_default_stmt(s1);

            if (s3) {
                  /* Goto default statement. */
                  label1 = label_new(identifier_tmp());
            } else {
                  /* No default statement => goto end. */
                  label1 = label0;
            }

            s4 = stmt_new();
            s4->type = STMT_DEFAULT;
            s4->stmt0 = stmt_goto(label1);

            /* Add new default statement to new switch. */
            stmt_append_last(s0->stmt0, s4);

            if (s3) {
                  /* Replace old default statement by new label. */
                  s4 = stmt_label(label1, stmt_null());
                  s5 = stmt_dup(s3->stmt0);

                  stmt_replace_1_by_2(s1, s3, s4, s5);
            }

            stmt_replace_1_by_3(block, s, s0, s1, s2);

            stmt_change = 1;

            stmt_check(block);
      simplify_switch_done:;
            break;

      case STMT_WHILE:
            if (block) {
                  /*
                   * Replace
                   *      while (e) s;
                   * by
                   *      0:        goto L1;
                   *      1:      L0:     ;
                   *      2:        s;
                   *      3:      L1:     ;
                   *      4:        if (e) goto L0;
                   *      5:      L2:     ;
                   *
                   * Substitute "break" and "continue" in "s" by
                   * "goto L2;" and "goto L1;".
                   */
                  label0 = label_new(identifier_tmp());
                  label1 = label_new(identifier_tmp());
                  label2 = label_new(identifier_tmp());

                  stmt_replace_continue(s->stmt0, label1);
                  stmt_replace_break(s->stmt0, label2);

                  s0 = stmt_goto(label1);
                  s1 = stmt_label(label0, stmt_null());
                  s2 = stmt_dup(s->stmt0);
                  s3 = stmt_label(label1, stmt_null());
                  s4 = stmt_if(expr_dup(s->expr0),
                              stmt_goto(label0), NULL);
                  s5 = stmt_label(label2, stmt_null());

                  stmt_replace_1_by_6(block, s,
                               s0, s1, s2, s3, s4, s5);

                  stmt_change |= 1;

                  stmt_check(block);
            }
            break;

      case STMT_DO_WHILE:
            if (block) {
                  /*
                   * Replace
                   *      do s; while (e);
                   * by
                   *      0:      L0:     ;
                   *      1:        s;
                   *      2:      L1:     ;
                   *      3:        if (e) goto L0;
                   *      4:      L2:     ;
                   *
                   * Substitute "break" and "continue" in "s" by
                   * "goto L2;" and "goto L1;".
                   */
                  label0 = label_new(identifier_tmp());
                  label1 = label_new(identifier_tmp());
                  label2 = label_new(identifier_tmp());

                  stmt_replace_continue(s->stmt0, label1);
                  stmt_replace_break(s->stmt0, label2);

                  s0 = stmt_label(label0, stmt_null());
                  s1 = stmt_dup(s->stmt0);
                  s2 = stmt_label(label1, stmt_null());
                  s3 = stmt_if(expr_dup(s->expr0),
                              stmt_goto(label0), NULL);
                  s4 = stmt_label(label2, stmt_null());

                  stmt_replace_1_by_5(block, s,
                              s0, s1, s2, s3, s4);
                  stmt_change = 1;

                  stmt_check(block);
            }
            break;

      case STMT_FOR:
            if (block) {
                  /*
                   * Replace
                   *      for (e0; e1; e2) s
                   * by
                   *      0:        e0;
                   *      1:        goto L2;
                   *      2:      L0:     ;
                   *      3:        s
                   *      4:      L1:     ;
                   *      5:        e2;
                   *      6:      L2:     ;
                   *      7:        if (e1) goto L0;
                   *      8:      L3:     ;
                   *
                   * Substitute "break" and "continue" in "s" by
                   * "goto L3" and "goto L1".
                   */
                  label0 = label_new(identifier_tmp());
                  label1 = label_new(identifier_tmp());
                  label2 = label_new(identifier_tmp());
                  label3 = label_new(identifier_tmp());

                  stmt_replace_continue(s->stmt0, label1);
                  stmt_replace_break(s->stmt0, label3);

                  if (s->expr0) {
                        s0 = stmt_expr(expr_dup(s->expr0));
                  } else {
                        s0 = stmt_null();
                  }
                  s1 = stmt_goto(label2);
                  s2 = stmt_label(label0, stmt_null());
                  s3 = stmt_dup(s->stmt0);
                  s4 = stmt_label(label1, stmt_null());
                  if (s->expr2) {
                        s5 = stmt_expr(expr_dup(s->expr2));
                  } else {
                        s5 = stmt_null();
                  }
                  s6 = stmt_label(label2, stmt_null());
                  if (s->expr1) {
                        s7 = stmt_if(expr_dup(s->expr1),
                                    stmt_goto(label0), NULL);
                  } else {
                        s7 = stmt_goto(label0);
                  }
                  s8 = stmt_label(label3, stmt_null());

                  stmt_replace_1_by_9(block, s,
                              s0, s1, s2, s3, s4, s5, s6, s7, s8);
                  stmt_change = 1;

                  stmt_check(block);
            }
            break;

      case STMT_GOTO:
      case STMT_CONTINUE:
      case STMT_BREAK:
            break;

      case STMT_RETURN:
      case STMT_ASM:
      case STMT_VA_START:
      case STMT_VA_END:
            break;

      case STMT_BLOCK:
            for (cs = s->stmt_first; cs; ) {
                  struct stmt *next;

                  next = cs->next;
                  stmt_sim_in_stmt(s, cs);
                  cs = next;
            }
            for (cs = s->stmt_first; cs; ) {
                  struct stmt *next;

                  next = cs->next;

                  if (cs->type == STMT_BLOCK
                   && ! cs->scope->declaration_first) {
                        /* Merge blocks. */
                        while (cs->stmt_first) {
                              /* Remove statement from inner block.*/
                              s0 = cs->stmt_last;
                              if (s0->prev) {
                                    s0->prev->next = s0->next;
                              } else {
                                    cs->stmt_first = s0->next;
                              }
                              cs->stmt_last = s0->prev;

                              /* Add statement to outer block. */
                              s0->prev = cs;
                              s0->next = cs->next;
                              s0->prev->next = s0;
                              if (s0->next) {
                                    s0->next->prev = s0;
                              } else {
                                    s->stmt_last = s0;
                              }
                        }

                        /* Remove inner block. */
                        if (cs->prev) {
                              cs->prev->next = cs->next;
                        } else {
                              s->stmt_first = cs->next;
                        }
                        if (cs->next) {
                              cs->next->prev = cs->prev;
                        } else {
                              s->stmt_last = cs->prev;
                        }

                        /* Don't free block! It's part of a scope! */

                        stmt_change = 1;
                  }

                  cs = next;
            }
            stmt_check(block);
            break;

      default:
            assert(0);
      }
}

int
stmt_simplify(struct stmt *fs)
{
      int retval;

      retval = 0;

      do {
            stmt_change = 0;
            stmt_sim_in_stmt(fs, fs);
            retval |= stmt_change;
      } while (stmt_change);

      return retval;
}

/* ------------------------------------------------------------------------- */

void
stmt_opt_label_hashlist(struct stmt *fs)
{
      /* Nothing to do... */
}


struct stmt *
stmt_opt_label_lookup(struct label *label)
{
      assert(label->def_first);
      assert(label->def_first == label->def_last);

      return label->def_first;
}

static void
stmt_opt_control_in_stmt(struct stmt *fs, struct stmt *s)
{
      struct stmt *ss;
      struct stmt *s0;
      struct stmt *s1;
      struct stmt *target;

      switch (s->type) {
      case STMT_NONE:
            assert(0);

      case STMT_CASE:
      case STMT_DEFAULT:
      case STMT_WHILE:
      case STMT_DO_WHILE:
      case STMT_FOR:
      case STMT_CONTINUE:
      case STMT_BREAK:
      case STMT_BLOCK:
            /* Should have been removed by simplify_control. */
            assert(0);

      case STMT_NULL:
            /*
             * Replace
             *                ;
             * by
             *                ---
             */
            stmt_replace_1_by_0(fs, s);
            stmt_change = 1;
            break;

      case STMT_LABEL:
            assert(s->stmt0->type == STMT_NULL);
            break;

      case STMT_EXPR:
            break;

      case STMT_IF:
            assert(s->expr0);
            assert(s->stmt0
                && s->stmt0->type == STMT_GOTO);
            assert(! s->stmt1);

            if (s->expr0->type == EXPR_INTEGER
             && s->expr0->integer == 0) {
                  /*
                   * Replace
                   *                if (0) goto l0;
                   * by
                   *                ---
                   */
                  stmt_replace_1_by_0(fs, s);
                  stmt_change = 1;

            } else if (s->expr0->type == EXPR_INTEGER
                  && s->expr0->integer != 0) {
                  /*
                   * Replace
                   *                if (1) goto l0;
                   * by
                   *                goto l0;
                   */
                  s0 = stmt_goto(s->stmt0->label);

                  stmt_replace_1_by_1(fs, s, s0);
                  stmt_change = 1;

            } else if (s->next
                  && s->next->type == STMT_LABEL
                  && strcmp(s->stmt0->label->identifier,
                        s->next->label->identifier) == 0) {
                  /*
                   * Replace
                   *                if (e) goto l0;
                   *          l0:   ;
                   * by
                   *                e;
                   *          l0:   ;
                   */
                  s0 = stmt_expr(expr_dup(s->expr0));

                  stmt_replace_1_by_1(fs, s, s0);
                  stmt_change = 1;

            } else if (s->next
                  && s->next->type == STMT_GOTO
                  && s->next->next
                  && s->next->next->type == STMT_LABEL
                  && strcmp(s->stmt0->label->identifier,
                        s->next->next->label->identifier) == 0) {
                  /*
                   * Replace
                   *                if (e) goto l0;
                   *                goto l1;
                   *          l0:   ;
                   * by
                   *                if (! e) goto l1;
                   *                goto l0;
                   *                goto l1;
                   *          l0:   ;
                   */
                  /*
                   * NOTE:
                   * We *mustn't* replace
                   *                if (e) goto l0;
                   *                goto l1;
                   *          l0:   ;
                   * by
                   *                if (! e) goto l1;
                   *          l0:   ;
                   *
                   * as we cannot replace *2* statements
                   * by 1!
                   */
                  s0 = stmt_if(expr_not(expr_dup(s->expr0)),
                              stmt_goto(s->next->label),
                              NULL);
                  s1 = stmt_goto(s->stmt0->label);

                  stmt_replace_1_by_2(fs, s, s0, s1);
                  stmt_change = 1;

            } else {
                  /* Try to optimize goto. */
                  stmt_opt_control_in_stmt(NULL, s->stmt0);
            }
            break;

      case STMT_SWITCH:
            if (s->expr0->type == EXPR_INTEGER) {
                  /*
                   * Replace
                   *          switch (numX) {
                   *          case ...: goto l0;
                   *          case ...: goto l1;
                   *          ...
                   *          case numX: goto lX;
                   *          ...
                   *          default: goto ldef;
                   *          }
                   * by
                   *          goto lX;
                   */
                  struct label *label;

                  label = NULL;

                  for (ss = s->stmt0->stmt_first; ss; ss = ss->next) {
                        assert(ss->type == STMT_CASE
                            || ss->type == STMT_DEFAULT);
                        assert(ss->stmt0
                            && ss->stmt0->type == STMT_GOTO);
                        
                        if (ss->type == STMT_CASE
                         && s->expr0->integer == ss->expr0->integer) {
                              label = ss->stmt0->label;

                        } else if (ss->type == STMT_DEFAULT
                              && label == NULL) {
                              label = ss->stmt0->label;
                        }
                  }

                  assert(label);

                  s0 = stmt_goto(label);

                  stmt_replace_1_by_1(fs, s, s0);
                  stmt_change = 1;

            } else {
                  /* Try to optimize gotos. */
                  for (ss = s->stmt0->stmt_first; ss; ss = ss->next) {
                        assert(ss->type == STMT_CASE
                            || ss->type == STMT_DEFAULT);
                        assert(ss->stmt0
                            && ss->stmt0->type == STMT_GOTO);

                        stmt_opt_control_in_stmt(NULL, ss->stmt0);
                  }
            }
            break;

      case STMT_GOTO:
            target = stmt_opt_label_lookup(s->label);
            assert(target);

            if (s->next
             && s->next == target) {
                  /*
                   * Replace
                   *                goto l0;
                   *          l0:   ;
                   * by
                   *          l0:   ;
                   */
                  assert(fs);

                  stmt_replace_1_by_0(fs, s);
                  stmt_change = 1;

            } else if (target->next
                  && target->next->type == STMT_GOTO
                  && s->label != target->next->label) {
                  /*
                   * Replace
                   *                goto l0;
                   *                ...
                   *          l0:   ;
                   *                goto l1;
                   *                ...
                   *          l1:   ;
                   * by
                   *                goto l1;
                   *                ...
                   *          l0:   ;
                   *                goto l1;
                   *                ...
                   *          l1:   ;
                   */
                  label_ref_del(s->label, s);
                  s->label = target->next->label;
                  label_ref_add(s->label, s);
                  stmt_change = 1;

            } else if (target->next
                  && target->next->type == STMT_LABEL) {
                  /*
                   * Replace
                   *                goto l0;
                   *                ...
                   *          l0:   ;
                   *          l1:   ;
                   * by
                   *                goto l1;
                   *                ...
                   *          l0:   ;
                   *          l1:   ;
                   */
                  label_ref_del(s->label, s);
                  s->label = target->next->label;
                  label_ref_add(s->label, s);
                  stmt_change = 1;
            }
            break;

      case STMT_RETURN:
      case STMT_ASM:
      case STMT_VA_START:
      case STMT_VA_END:
            break;

      default:
            assert(0);
      }
}

static void
stmt_opt_control(struct stmt *fs)
{
      struct stmt *cs;

      assert(fs->type == STMT_BLOCK);

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

            next = cs->next;

            stmt_opt_control_in_stmt(fs, cs);

            cs = next;
      }
}

static void
stmt_opt_mark_unused(struct stmt *s)
{
      struct stmt *cs;

      if (s->stmt0) {
            stmt_opt_mark_unused(s->stmt0);
      }
      if (s->stmt1) {
            stmt_opt_mark_unused(s->stmt1);
      }
      for (cs = s->stmt_first; cs; cs = cs->next) {
            stmt_opt_mark_unused(cs);
      }

      s->stmt_used = 0;
      s->label_used = 0;
}

static void
stmt_opt_mark_used_in_stmt(struct stmt *s)
{
      struct stmt *ss;
      struct stmt *target;

      if (! s
       || s->stmt_used) {
            return;
      }
      s->stmt_used = 1;

      switch (s->type) {
      case STMT_NONE:
            assert(0);
      
      case STMT_CASE:
      case STMT_DEFAULT:
      case STMT_WHILE:
      case STMT_DO_WHILE:
      case STMT_FOR:
      case STMT_CONTINUE:
      case STMT_BREAK:
      case STMT_BLOCK:
            /* Should have been removed by simplify_control. */
            assert(0);

      case STMT_NULL:
            /* Should have been removed above. */
            assert(0);

      case STMT_LABEL:
      case STMT_EXPR:
      case STMT_ASM:
      case STMT_VA_START:
      case STMT_VA_END:
            stmt_opt_mark_used_in_stmt(s->next);
            break;

      case STMT_IF:
            stmt_opt_mark_used_in_stmt(s->stmt0);
            stmt_opt_mark_used_in_stmt(s->next);
            break;

      case STMT_SWITCH:
            for (ss = s->stmt0->stmt_first; ss; ss = ss->next) {
                  stmt_opt_mark_used_in_stmt(ss->stmt0);
            }
            break;

      case STMT_GOTO:
            target = stmt_opt_label_lookup(s->label);

            target->label_used = 1;
            stmt_opt_mark_used_in_stmt(target);
            break;

      case STMT_RETURN:
            break;

      default:
            assert(0);
      }
}

static void
stmt_opt_mark_used(struct stmt *fs)
{
      assert(fs->type == STMT_BLOCK);

      stmt_opt_mark_used_in_stmt(fs->stmt_first);
}

static void
stmt_opt_remove_unused(struct stmt *fs)
{
      struct stmt *cs;

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

            next = cs->next;

            if (! cs->stmt_used
             || (cs->type == STMT_LABEL
              && ! cs->label_used)) {
                  stmt_replace_1_by_0(fs, cs);
                  stmt_change = 1;
            }
      
            cs = next;
      }
}

int
stmt_optimize(struct stmt *fs)
{
      stmt_change = 0;

      stmt_opt_label_hashlist(fs);
      stmt_opt_control(fs);
      stmt_opt_mark_unused(fs);
      stmt_opt_mark_used(fs);
      stmt_opt_remove_unused(fs);

      return stmt_change;
}

Generated by  Doxygen 1.6.0   Back to index