ctrump/analyzer/analyze.c

Go to the documentation of this file.

/* -*- coding:utf-8 -*- 
 Copyright (c) 2009, Fixstars Corporation
 All rights reserved.
 
 Redistribution and use in source and binary forms, with or without modification, 
 are permitted provided that the following conditions are met:
 
   * Redistributions of source code must retain the above copyright notice,
     this list of conditions and the following disclaimer.
 
   * Redistributions in binary form must reproduce the above copyright notice,
     this list of conditions and the following disclaimer in the documentation
     and/or other materials provided with the distribution.
 
   * Neither the name of Fixstars Corporation nor the names of its contributors
     may be used to endorse or promote products derived from this software
     without specific prior written permission.
 
 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
 ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
 INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
 AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
 THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#include "ctrump/analyzer/analyze.h"
#include "ctrump/common/mempool.h"
#include "ctrump/ast/ast.h"
#include "ctrump/analyzer/cfg.h"
#include <stdlib.h>
#include "ctrump/common/abort.h"
#include "ctrump/common/varray.h"
#include "ctrump/common/intmap.h"

struct analyze_allocator
{
    struct ctrump_mempool *pool;
    int id;
};

struct build_loop_tree_state {
    int num_complicated;
    struct ctrump_complicated_loop reason;
    struct ctrump_intmap *var_info_map;
    struct ctrump_varray children; /* struct ctrump_loop_info_node * */
    struct ctrump_varray *loop_tree_roots; /* struct ctrump_loop_info_node * */
};

static void
init_build_loop_tree_state(struct build_loop_tree_state *st,
                           struct ctrump_intmap *var_info_map,
                           struct ctrump_varray *loops)
{
    st->num_complicated = 0;
    st->var_info_map = var_info_map;
    st->loop_tree_roots = loops;

    ctrump_varray_init(&st->children, 4, sizeof(struct ctrump_loop_info_node *));
}

static void
destroy_build_loop_tree_state(struct build_loop_tree_state *st)
{
    ctrump_varray_discard(&st->children);
}

static int analyze_loop_control_flow(struct build_loop_tree_state *st,
                                     struct ctrump_loop_cfg_info *attr,
                                     struct ctrump_cfg *cfg,
                                     struct ctrump_stmt *loop_body,
                                     struct ctrump_location *loc,
                                     struct analyze_allocator *alloc);

static void analyze_control_flow(struct build_loop_tree_state *st,
                                 struct ctrump_stmt *stmt,
                                 struct ctrump_cfg *cfg,
                                 struct analyze_allocator *alloc);

static void
build_loop_tree_compound_stmt(struct build_loop_tree_state *st,
                              struct ctrump_compound_stmt *stmt,
                              struct ctrump_cfg *cfg,
                              struct analyze_allocator *alloc)
{
    int ni = stmt->num_item;
    struct ctrump_stmt *items = stmt->items;
    int i;

    for (i=0; i<ni; i++) {
        analyze_control_flow(st, &items[i], cfg, alloc);
    }
}
static void
complicated_loop(struct build_loop_tree_state *st,
                 enum ctrump_complicated_loop_reason_code code,
                 struct ctrump_stmt *stmt)
{
    if (st->num_complicated == 0) {
        st->reason.reason = code;
        st->reason.stmt = stmt;
    }
    st->num_complicated ++;
}

static void
analyze_control_flow(struct build_loop_tree_state *st,
                     struct ctrump_stmt *stmt,
                     struct ctrump_cfg *cfg,
                     struct analyze_allocator *alloc)
{
    int r;
tailcall:
    switch (stmt->code) {
    case CTRUMP_STMT_LABELED:
        stmt = stmt->u.labeled.stmt;
        goto tailcall;

    case CTRUMP_STMT_CASE:
        stmt = stmt->u.case_.stmt;
        goto tailcall;

    case CTRUMP_STMT_DEFAULT:
        stmt = stmt->u.default_.stmt;
        goto tailcall;

    case CTRUMP_STMT_COMPOUND:
        build_loop_tree_compound_stmt(st, &stmt->u.compound, cfg, alloc);
        return ;

    case CTRUMP_STMT_IF:
        stmt = stmt->u.if_.body;
        goto tailcall;

    case CTRUMP_STMT_IF_ELSE:
        analyze_control_flow(st, stmt->u.if_else.then_body, cfg, alloc);
        stmt = stmt->u.if_else.else_body;
        goto tailcall;

    case CTRUMP_STMT_SWITCH:
        stmt = stmt->u.switch_.body;
        goto tailcall;

    case CTRUMP_STMT_FOR:
        r = analyze_loop_control_flow(st,
                                      stmt->u.for_.loop_cfg,
                                      cfg,
                                      stmt->u.for_.body,
                                      &stmt->u.for_.kwd_loc,
                                      alloc);
        if (r < 0)
            complicated_loop(st, CTRUMP_COMPLICATED_LOOP_HAVE_COMPLICATED_NEST, stmt);
        return;

    case CTRUMP_STMT_FOR_DECL:
        r = analyze_loop_control_flow(st,
                                      stmt->u.for_decl.loop_cfg,
                                      cfg,
                                      stmt->u.for_decl.body,
                                      &stmt->u.for_decl.kwd_loc,
                                      alloc);
        if (r < 0)
            complicated_loop(st, CTRUMP_COMPLICATED_LOOP_HAVE_COMPLICATED_NEST, stmt);
        return;

    case CTRUMP_STMT_WHILE:
        r = analyze_loop_control_flow(st,
                                      stmt->u.while_.loop_cfg,
                                      cfg,
                                      stmt->u.while_.body,
                                      &stmt->u.while_.kwd_loc,
                                      alloc);
        if (r < 0)
            complicated_loop(st, CTRUMP_COMPLICATED_LOOP_HAVE_COMPLICATED_NEST, stmt);
        return;

    case CTRUMP_STMT_GOTO:
        complicated_loop(st, CTRUMP_COMPLICATED_LOOP_GOTO, stmt); return;
    case CTRUMP_STMT_BREAK:
        complicated_loop(st, CTRUMP_COMPLICATED_LOOP_BREAK, stmt); return;
    case CTRUMP_STMT_RETURN_EXPR:
    case CTRUMP_STMT_RETURN:
        complicated_loop(st, CTRUMP_COMPLICATED_LOOP_RETURN, stmt); return;
    case CTRUMP_STMT_DO_WHILE:
        complicated_loop(st, CTRUMP_COMPLICATED_LOOP_NEST, stmt);
        stmt = stmt->u.do_while.body;
        goto tailcall;

    case CTRUMP_STMT_EXPR:
    case CTRUMP_STMT_DECL:
    case CTRUMP_STMT_EMPTY:
    case CTRUMP_STMT_PRAGMA:
    case CTRUMP_STMT_SLASLA_COMMENT:
    case CTRUMP_STMT_SLAAST_COMMENT:
    case CTRUMP_STMT_DEFINE:
    case CTRUMP_STMT_UNDEF:
    case CTRUMP_STMT_CONTINUE:
    case CTRUMP_STMT_IFDEF:
    case CTRUMP_STMT_ASM:
    case CTRUMP_STMT_NEWLINE:
        return;

    case CTRUMP_STMT_LIST:
        break;
    }

    ctrump_unreachable("control_flow");
}

static void
append_root(struct ctrump_varray *roots,
            struct ctrump_varray *new_roots)
{
    int i, n;
    struct ctrump_loop_info_node **children;
    n = new_roots->nelem;
    children = new_roots->elements;

    /* children are roots of loop tree */
    for (i=0; i<n; i++) {
        VA_PUSH(struct ctrump_loop_info_node*,
                roots,
                children[i]);
    }
}

static int
analyze_loop_control_flow(struct build_loop_tree_state *prev_st,
                          struct ctrump_loop_cfg_info *cfg_info,
                          struct ctrump_cfg *cfg,
                          struct ctrump_stmt *body,
                          struct ctrump_location *loc,
                          struct analyze_allocator *alloc)
{
    struct build_loop_tree_state st;
    struct ctrump_loop_info_node *node;

    init_build_loop_tree_state(&st, prev_st->var_info_map,
                               prev_st->loop_tree_roots);

    analyze_control_flow(&st, body, cfg, alloc);

    if (st.num_complicated != 0) {
        /* too complicated */

        cfg_info->code = CTRUMP_LOOP_COMPLICATED;
        cfg_info->u.complicated = st.reason;

        append_root(prev_st->loop_tree_roots, &st.children);

        destroy_build_loop_tree_state(&st);

        return -1;
    }

    node = ctrump_mempool_alloc(alloc->pool, sizeof(*node));
    node->id = alloc->id++;
    node->nest_level = 0;

    if (st.children.nelem) {
        node->num_child = st.children.nelem;
        node->children = ctrump_varray_copy(&st.children, alloc->pool);
    } else {
        node->children = NULL;
        node->num_child = 0;
    }
    node->parent = NULL;
    node->cfg_info = cfg_info;
    node->loc = *loc;

    VA_PUSH(struct ctrump_loop_info_node*, &prev_st->children, node);

    destroy_build_loop_tree_state(&st);

    return 0;
}

static void
build_loop_tree_func(struct ctrump_varray *loops,
                     struct ctrump_fundef *func,
                     struct ctrump_cfg *cfg,
                     struct ctrump_intmap *var_info_map,
                     const struct ctrump_abi *abi,
                     struct analyze_allocator *alloc)
{
    struct build_loop_tree_state st;
    int i, n;
    struct ctrump_loop_info_node **roots;

    init_build_loop_tree_state(&st, var_info_map, loops);

    build_loop_tree_compound_stmt(&st, &func->body, cfg, alloc);

    append_root(loops, &st.children);

    n = loops->nelem;
    roots = loops->elements;
    for (i=0; i<n; i++) {
        struct ctrump_loop_info *loop_info = ctrump_mempool_alloc(alloc->pool, sizeof(*loop_info));
        struct ctrump_loop_info_node *root = roots[i];
        loop_info->id = alloc->id++;
        loop_info->root = root;
        alloc->id = ctrump_analyze_loop(loop_info, &loop_info->nest_level, root, cfg,
                                        var_info_map, abi, alloc->pool, alloc->id);
    }

    destroy_build_loop_tree_state(&st);
}

int
ctrump_analyze(struct ctrump_translation_unit *unit,
               const struct ctrump_abi *abi,
               struct ctrump_mempool *pool,
               struct ctrump_build_cfg_error *error,
               int num_ast,
               int id_base)
{
    int i, r;
    int id = id_base;
    int nd = unit->num_decl;
    struct analyze_allocator alloc;
    struct ctrump_varray loops;

    ctrump_varray_init(&loops, 16, sizeof(struct ctrump_loop_info *));

    alloc.pool = pool;
    for (i=0; i<nd; i++) {
        struct ctrump_extdecl *d = unit->decls + i;
        struct ctrump_intmap var_info_map;
        switch (d->code) {
        case CTRUMP_EXT_FUNCTION_DEFINITION:
        {
            struct ctrump_mempool ana_pool;
            ctrump_mempool_init(&ana_pool, 1024);
            d->u.func_def.cfg = ctrump_mempool_alloc(pool, sizeof(*d->u.func_def.cfg));
            d->u.func_def.cfg->id = id;
            id++;
            r = ctrump_build_cfg(d->u.func_def.cfg, &var_info_map, error, &d->u.func_def, pool, &ana_pool, id_base, id);
            if (r < 0) {
                ctrump_mempool_destroy(&ana_pool);
                ctrump_varray_discard(&loops);
                return r;
            }
            id = r;
            alloc.id = id;

            build_loop_tree_func(&loops, &d->u.func_def, d->u.func_def.cfg, &var_info_map, abi, &alloc);

            id = alloc.id;

            d->u.func_def.cfg->num_loop = loops.nelem;
            d->u.func_def.cfg->loop_tree_roots = ctrump_varray_copy(&loops, pool);

            ctrump_mempool_destroy(&ana_pool);

            loops.nelem = 0;
        }
            break;

        default:
            break;
        }
    }

    ctrump_varray_discard(&loops);

    return id;
}

---