ctrump/analyzer/cfg.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/cfg.h"
#include "ctrump/common/bitmap.h"
#include "ctrump/common/varray.h"
#include "ctrump/common/uthash.h"
#include "ctrump/common/intmap.h"
#include "ctrump/common/abort.h"
#include "ctrump/ast/ast.h"
#include "ctrump/analyzer/peel.h"

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

enum partial_bb_expr_code {
    BB_EXPR
};

struct partial_bb_expr {
    enum partial_bb_expr_code code;
    struct ctrump_stmt *at;

    union {
        struct ctrump_expr *expr;
    }u;
};

struct pending_chain {
    struct pending_chain *chain;
    struct ctrump_bb **resolve_ptr;
};

enum load_store_t {
    INIT,
    LOAD,
    STORE
};

struct ordered_load_store_node {
    enum load_store_t code;
    int op_idx;
    int var_idx;
};

struct partial_bb {
    int id;
    int flags;
    struct ctrump_varray preds, succs, exprs, dfs, children; /* partial_bb */
    struct ctrump_varray refs, stores;                       /* ctrump_var_ref, ctrump_var_store */
    struct ctrump_varray inits;                              /* ctrump_decl_with_init */
    struct ctrump_varray arr_loads, arr_stores;              /* ctrump_memory_load, memory_store */
    struct ctrump_varray ordered_load_store;                 /* ordered_load_store_node */
    struct ctrump_varray ordered_mem_load_store;             /* ctrump_ordered_memory_load_store_node */
    struct partial_bb *idom;
    struct pending_chain *resolve_pending;
    struct ctrump_loop_cfg_info *loop_cfg;
    int order;
    ctrump_bitmap_t use, kill, live, phi_inserted;
    struct ctrump_bb *bb;

    int num_phi;
    struct ctrump_phi_node *phi_nodes;
};

struct partial_var_info {
    struct ctrump_cfg_var_info result;
    ctrump_bitmap_t modified_at;
    struct ctrump_varray ssa_var_stack;
    struct ctrump_varray stack_depth;
    int map_val;
};

struct label_table {
    const struct ctrump_symbol *label_symbol;
    struct ctrump_stmt *stmt;
    UT_hash_handle hh;
};

struct build_cfg_env {
    struct ctrump_mempool *cfg_pool;
    struct ctrump_build_cfg_error *error;
    struct ctrump_mempool tmp_alloc;
    struct label_table *label_table;

    struct partial_bb **stmt_bb_table;
    struct partial_bb **dfs_order;
    ctrump_bitmap_t label_ref_bmp;
    int bb_id;
    int next_id;
    struct ctrump_varray basic_blocks;
};

static struct partial_bb *new_bb(struct build_cfg_env *env,
                                 struct ctrump_loop_cfg_info *cfg);
static void append_succs_maybe(struct partial_bb *bb, /* NULL if unreachable */
                               struct partial_bb *next,
                               struct build_cfg_env *env);
static void append_succs(struct partial_bb *bb,
                         struct partial_bb *next,
                         struct build_cfg_env *env);

static void build_cfg_expr_maybe(struct ctrump_expr *e,
                                 struct ctrump_stmt *at,
                                 struct build_cfg_env *env,
                                 struct ctrump_loop_cfg_info *cur_loop,
                                 struct partial_bb **current_bb_ptr);

static void build_cfg_expr(struct ctrump_expr *e,
                           struct ctrump_stmt *at,
                           struct build_cfg_env *env,
                           struct ctrump_loop_cfg_info *cur_loop,
                           struct partial_bb **current_bb_ptr);

static void build_cfg_initializer(struct ctrump_initializer *init,
                                  struct ctrump_stmt *stmt,
                                  struct build_cfg_env *env,
                                  struct ctrump_loop_cfg_info *loop,
                                  struct partial_bb **current_bb_ptr);

static void build_cfg_initializer_list(struct ctrump_initializer_list *list,
                                       struct ctrump_stmt *stmt,
                                       struct build_cfg_env *env,
                                       struct ctrump_loop_cfg_info *loop,
                                       struct partial_bb **current_bb_ptr);

#define zero_bmp ctrump_bmp_zero

#define HASH_FIND_SYM(head,findptr,out)                                 \
    HASH_FIND(hh,head,findptr,sizeof(struct ctrump_symbol*),out)

static void
delete_table(struct label_table *table)
{
    struct label_table *t;
    while (table) {
        t = table;
        HASH_DEL(table, t);
        free(t);
    }
}

static int
build_label_table(struct label_table **table,
                  const struct ctrump_compound_stmt *stmts,
                  struct build_cfg_env *env)
{
    struct ctrump_stmt *itm = stmts->items;
    int i, nitem = stmts->num_item;
    for (i=0; i<nitem; i++) {
        struct ctrump_stmt *stmt = &itm[i];
        if (stmt->code == CTRUMP_STMT_LABELED) {
            struct label_table *find, *t;
            const struct ctrump_symbol *label_symbol;
            label_symbol = stmt->u.labeled.label_symbol;

            HASH_FIND_SYM((*table), stmt->u.labeled.label_symbol, find);

            if (find) {
                env->error->code = CTRUMP_BUILD_CFG_ERROR_REDEFINE_LABEL;
                env->error->stmt = stmt;

                delete_table(*table);

                return -1;
            }

            t = ctrump_mempool_alloc(&env->tmp_alloc, sizeof(*t));

            t->label_symbol = label_symbol;
            t->stmt = stmt;
            HASH_ADD(hh, *table, label_symbol, sizeof(struct ctrump_symbol), t);
        } else if (stmt->code == CTRUMP_STMT_COMPOUND) {
            const struct ctrump_compound_stmt *comp = &stmt->u.compound;
            return build_label_table(table, comp, env);
        }
    }

    return 0;
}

static int
build_label_ref(struct label_table *table,
                const struct ctrump_compound_stmt *stmt,
                struct build_cfg_env *env)
{
    struct ctrump_stmt *itm = stmt->items;
    int i, nitem = stmt->num_item;
    for (i=0; i<nitem; i++) {
        struct ctrump_stmt *stmt = &itm[i];
        if (stmt->code == CTRUMP_STMT_GOTO) {
            const struct ctrump_goto_stmt *s = &stmt->u.goto_;
            struct label_table *t;
            HASH_FIND_SYM(table, s->label, t);

            if (t == NULL) {
                env->error->code = CTRUMP_BUILD_CFG_ERROR_UNDEFINED_LABEL;
                env->error->stmt = stmt;

                return -1;
            }

            ctrump_bitmap_set(env->label_ref_bmp, stmt->id);
            return 0;
        } else if (stmt->code == CTRUMP_STMT_COMPOUND) {
            const struct ctrump_compound_stmt *comp = &stmt->u.compound;
            return build_label_ref(table, comp, env);
        }
    }

    return 0;
}

static int
check_label_use(struct build_cfg_env *env,
                const struct ctrump_compound_stmt *stmts)
{
    struct label_table *table = NULL;
    int r;

    r = build_label_table(&table, stmts, env);
    if (r < 0)
        goto fail;

    r = build_label_ref(table, stmts, env);
    if (r < 0)
        goto fail;

    env->label_table = table;
    return 0;

fail:
    delete_table(table);
    return r;
}

static void
build_cfg_logical_expr(struct ctrump_expr *lhs,
                       struct ctrump_expr *rhs,
                       struct ctrump_stmt *at,
                       struct build_cfg_env *env,
                       struct ctrump_loop_cfg_info *cur_loop,
                       struct partial_bb **current_bb_ptr)
{
    struct partial_bb *next_bb = new_bb(env, cur_loop);
    struct partial_bb *rhs_bb = new_bb(env, cur_loop);

    build_cfg_expr(lhs, at, env, cur_loop, current_bb_ptr);
    append_succs(*current_bb_ptr, next_bb, env);
    append_succs(*current_bb_ptr, rhs_bb, env);

    build_cfg_expr(rhs, at, env, cur_loop, &rhs_bb);
    append_succs(rhs_bb, next_bb, env);

    *current_bb_ptr = next_bb;
}

static void
build_cfg_trinary_cond_expr(struct ctrump_expr *cond,
                            struct ctrump_expr *then_,
                            struct ctrump_expr *else_,
                            struct ctrump_stmt *at,
                            struct build_cfg_env *env,
                            struct ctrump_loop_cfg_info *cur_loop,
                            struct partial_bb **current_bb_ptr)
{
    struct partial_bb *next_bb = new_bb(env, cur_loop);
    struct partial_bb *then_bb = new_bb(env, cur_loop);
    struct partial_bb *else_bb = new_bb(env, cur_loop);

    build_cfg_expr(cond, at, env,cur_loop,  current_bb_ptr);
    append_succs(*current_bb_ptr, then_bb, env);
    append_succs(*current_bb_ptr, else_bb, env);
    build_cfg_expr(then_, at, env, cur_loop, &then_bb);
    build_cfg_expr(else_, at, env, cur_loop, &else_bb);

    append_succs(then_bb, next_bb, env);
    append_succs(else_bb, next_bb, env);

    *current_bb_ptr = next_bb;
}

struct flow_env {
    struct partial_bb *continue_to; 
    struct partial_bb *break_to; 
    struct partial_bb *return_to;   
    struct ctrump_loop_cfg_info *loop_cfg; 
};

static void
build_cfg_cond_expr(struct ctrump_expr *e,
                    struct ctrump_stmt *at,
                    struct build_cfg_env *env,
                    struct ctrump_loop_cfg_info *cur_loop,
                    struct partial_bb **current_bb_ptr)
{
    int i, n;
    struct ctrump_expr *args;

tailcall:
    switch (e->code) {
    case CTRUMP_EXPR_BIN_ASSIGN:
    case CTRUMP_EXPR_BIN_COMMA:
    case CTRUMP_CASE_BIN_ARITH_EXPR:
    case CTRUMP_CASE_BIN_EQ_EXPR:
    case CTRUMP_CASE_BIN_OP_ASSIGN_EXPR:
        build_cfg_cond_expr(e->u.binary.lhs, at, env, cur_loop, current_bb_ptr);
        e = e->u.binary.rhs;
        goto tailcall;

    case CTRUMP_EXPR_ARRREF:
        build_cfg_cond_expr(e->u.arr_ref.array, at, env, cur_loop, current_bb_ptr);
        e = e->u.arr_ref.subscript;
        goto tailcall;

    case CTRUMP_EXPR_MEMBER_REF:
    case CTRUMP_EXPR_PTR_MEMBER_REF:
        e = e->u.member_ref.obj_expr;
        goto tailcall;

    case CTRUMP_CASE_ALL_UNARY_EXPR:
        e = e->u.unary.expr;
        goto tailcall;

    case CTRUMP_EXPR_PAREN:
        e = e->u.paren.expr;
        goto tailcall;

    case CTRUMP_EXPR_CALL:
        n = e->u.call.num_args;
        args = e->u.call.args;
        for (i=0; i<n; i++) {
            build_cfg_cond_expr(&args[i], at, env, cur_loop, current_bb_ptr);
        }
        e = e->u.call.func_expr;
        goto tailcall;

    case CTRUMP_EXPR_VARREF:
    case CTRUMP_CASE_CONSTANT_TERM:
    case CTRUMP_EXPR_EMPTY:
        return;

    case CTRUMP_EXPR_CAST:
        e = e->u.cast.expr;
        goto tailcall;

    case CTRUMP_EXPR_IMPLICIT_CAST:
        e = e->u.implicit_cast.expr;
        goto tailcall;

    case CTRUMP_EXPR_MACRO_EXPAND:
        e = e->u.macro_expand.expanded;
        goto tailcall;

    case CTRUMP_CASE_BIN_LOG_EXPR:
        build_cfg_logical_expr(e->u.binary.lhs, e->u.binary.rhs, at, env, cur_loop, current_bb_ptr);
        break;

    case CTRUMP_EXPR_CONDITIONAL:
        build_cfg_trinary_cond_expr(e->u.cond.cond, e->u.cond.then_, e->u.cond.else_, at, env, cur_loop, current_bb_ptr);
        break;

    case CTRUMP_EXPR_INITIALIZER:
        build_cfg_initializer_list(&e->u.initializer.initializer, at, env, cur_loop, current_bb_ptr);
        break;

    case CTRUMP_EXPR_TEXT:
    case CTRUMP_EXPR_IVTMP:
        /* maybe bug */
        ctrump_unreachable("invalid expr code");
    }
}

static void
build_cfg_expr(struct ctrump_expr *e,
               struct ctrump_stmt *at,
               struct build_cfg_env *env,
               struct ctrump_loop_cfg_info *cur_loop,
               struct partial_bb **current_bb_ptr)
{
    struct partial_bb_expr *p;
    struct partial_bb *bb = *current_bb_ptr;
    VA_NEWELEM_P(&bb->exprs, &env->tmp_alloc);
    p = VA_LAST_PTR(struct partial_bb_expr, &bb->exprs);

    build_cfg_cond_expr(e, at, env, cur_loop, current_bb_ptr);

    p->code = BB_EXPR;
    p->u.expr = e;
    p->at = at;
}

static void
append_pending(struct build_cfg_env *env,
               struct partial_bb *bb,
               struct ctrump_bb **resolve_ptr)
{
    struct pending_chain *pend = ctrump_mempool_alloc(&env->tmp_alloc,
                                                      sizeof(*pend));
    pend->chain = bb->resolve_pending;
    bb->resolve_pending = pend;
    pend->resolve_ptr = resolve_ptr;
}


static void
build_cfg_expr_maybe(struct ctrump_expr *e,
                     struct ctrump_stmt *at,
                     struct build_cfg_env *env,
                     struct ctrump_loop_cfg_info *cur_loop,
                     struct partial_bb **current_bb_ptr)
{
    if (*current_bb_ptr) {
        build_cfg_expr(e, at, env, cur_loop, current_bb_ptr);
    }
}


static void
append_succs(struct partial_bb *bb,
             struct partial_bb *next,
             struct build_cfg_env *env)
{
    VA_PUSH_P(struct partial_bb*, &bb->succs, next, &env->tmp_alloc);
    VA_PUSH_P(struct partial_bb*, &next->preds, bb, &env->tmp_alloc);
}


static void
append_succs_maybe(struct partial_bb *bb, /* NULL if unreachable */
                   struct partial_bb *next,
                   struct build_cfg_env *env)
{
    if (bb) {
        append_succs(bb, next, env);
    }
}


static struct partial_bb *
new_bb(struct build_cfg_env *env, struct ctrump_loop_cfg_info *loop)
{
    struct partial_bb *ret = ctrump_mempool_alloc(&env->tmp_alloc, sizeof(*ret));
    ret->id = env->bb_id++;
    ret->resolve_pending = NULL;
    ctrump_varray_init_pool(&ret->preds, 4, sizeof(struct partial_bb*), &env->tmp_alloc);
    ctrump_varray_init_pool(&ret->succs, 4, sizeof(struct partial_bb*), &env->tmp_alloc);
    ctrump_varray_init_pool(&ret->exprs, 4, sizeof(struct partial_bb_expr), &env->tmp_alloc);
    ctrump_varray_init_pool(&ret->dfs, 4, sizeof(struct partial_bb*), &env->tmp_alloc);
    ctrump_varray_init_pool(&ret->children, 4, sizeof(struct partial_bb*), &env->tmp_alloc);

    ctrump_varray_init_pool(&ret->refs, 4, sizeof(struct ctrump_var_ref), &env->tmp_alloc);
    ctrump_varray_init_pool(&ret->stores, 4, sizeof(struct ctrump_var_store), &env->tmp_alloc);

    ctrump_varray_init_pool(&ret->arr_loads, 4, sizeof(struct ctrump_memory_load), &env->tmp_alloc);
    ctrump_varray_init_pool(&ret->arr_stores, 4, sizeof(struct ctrump_memory_store), &env->tmp_alloc);
    ctrump_varray_init_pool(&ret->ordered_load_store, 4, sizeof(struct ordered_load_store_node), &env->tmp_alloc);
    ctrump_varray_init_pool(&ret->ordered_mem_load_store, 4, sizeof(struct ctrump_ordered_memory_load_store_node), &env->tmp_alloc);

    ret->phi_inserted = NULL;
    ret->loop_cfg = loop;
    ret->flags = 0;

    VA_PUSH_P(struct partial_bb*, &env->basic_blocks, ret, &env->tmp_alloc);

    env->next_id++;

    return ret;
}

static struct partial_bb *
get_id_bb(struct build_cfg_env *env,
          struct ctrump_stmt *stmt,
          struct ctrump_loop_cfg_info *cur_loop)
{
    int id = stmt->id;
    struct partial_bb *ret = env->stmt_bb_table[id];

    if (ret) {
        return ret;
    }

    ret = new_bb(env, cur_loop);

    env->stmt_bb_table[id] = ret;

    return ret;
}

static struct partial_bb *
get_id_bb_maybe(struct build_cfg_env *env,
                struct ctrump_stmt *stmt,
                struct ctrump_loop_cfg_info *loop,
                struct partial_bb *return_to_bb)
{
    if (stmt) {
        return get_id_bb(env, stmt, loop);
    } else {
        return return_to_bb;
    }
}



static int
build_cfg_stmt(struct ctrump_stmt *stmt,
               struct ctrump_stmt *next_stmt, /* NULL if current stmt is last of bb */
               struct build_cfg_env *env,
               const struct flow_env *flow_env,
               struct partial_bb **current_bb_ptr);

static int
build_cfg_compound(const struct ctrump_compound_stmt *stmts,
                   struct build_cfg_env *env,
                   const struct flow_env *flow_env,
                   struct partial_bb **current_bb_ptr, /* *current_bb_ptr is NULL if unreachable */
                   struct ctrump_stmt *next_block_stmt /* NULL if current stmt is last of bb */
    )
{
    int i, r;
    struct ctrump_stmt *items = stmts->items;
    int nitem = stmts->num_item;

    for (i=0; i<nitem; i++) {
        struct ctrump_stmt *stmt = &items[i];
        struct ctrump_stmt *next_stmt;

        if (i < nitem-1) {
            next_stmt = &items[i+1];
        } else {
            next_stmt = next_block_stmt;
        }

        r = build_cfg_stmt(stmt, next_stmt, env, flow_env, current_bb_ptr);
        if (r < 0)
            return r;
    }

    return 0;
}

static int
dfs_order(struct partial_bb *start,
          struct build_cfg_env *env,
          int num_bb,
          ctrump_bitmap_t bb_bitmap)
{
    /* depth first search */
    struct partial_bb **stack;
    int stk_size=1;
    ctrump_bitmap_t visited = bb_bitmap;
    int order = 0;

    stack = ctrump_mempool_alloc(&env->tmp_alloc, num_bb*sizeof(struct partial_bb*));
    env->dfs_order = ctrump_mempool_alloc(&env->tmp_alloc, num_bb*sizeof(struct partial_bb*));

    stack[0] = start;
    BMP_SET(visited, 0);

    while (stk_size) {
        struct partial_bb *top;
        struct partial_bb *succ;
        int i, n;
    next:
        top = stack[stk_size-1];
        n = top->succs.nelem;

        for (i=0; i<n; i++) {
            int id;
            succ = VA_ELEM(struct partial_bb *, &top->succs, i);
            id = succ->id;

            if (BMP_P(visited,id) == 0) {
                succ->idom = top;
                BMP_SET(visited, id);
                stack[stk_size] = succ;
                stk_size++;
                goto next;
            }
        }

        top->order = order;
        env->dfs_order[order] = top;
        order++;
        stk_size--;
    }

    return order;
}

static struct partial_bb *
nca(struct partial_bb *x,
    struct partial_bb *y)
{
    while (x != y) {
        int xo, yo;
        xo = x->order;
        yo = y->order;

        if (xo < yo) {
            x = x->idom;
            xo = x->order;
        } else {
            y = y->idom;
            yo = y->order;
        }
    }

    return x;
}

static void
build_dom(struct build_cfg_env *env,
          int num_bb)
{
    int changed = 1;
    int i, j;

    while (changed) {
        changed = 0;
        for (i=num_bb-1; i>=0; i--) {
            struct partial_bb *bb = env->dfs_order[i];
            int n = bb->preds.nelem;
            struct partial_bb *idom = bb->idom;
            for (j=0; j<n; j++) {
                struct partial_bb *new_idom;
                struct partial_bb *pred = VA_ELEM(struct partial_bb *, &bb->preds, j);
                new_idom = nca(idom, pred);
                if (idom != new_idom) {
                    bb->idom = new_idom;
                    idom = new_idom;
                    changed = 1;
                }
            }
        }
    }

    /* create dom tree */
    for (i=0; i<num_bb-1; i++) { /* (i==num_bb-1) is start bb */
        struct partial_bb *bb = env->dfs_order[i];
        struct partial_bb *idom = bb->idom;

        VA_PUSH_P(struct partial_bb*, &idom->children, bb, &env->tmp_alloc);
    }
}

static void
find_df(struct build_cfg_env *env,
        int num_bb)
{
    int i;
    for (i=0; i<num_bb; i++) {
        struct partial_bb *bb = env->dfs_order[i];
        struct partial_bb *succ, *child, *df;
        int i, n;
        n = bb->succs.nelem;
        for (i=0; i<n; i++) {
            succ = VA_ELEM(struct partial_bb *, &bb->succs, i);
            if (succ->idom != bb) {
                VA_PUSH_P(struct partial_bb *, &bb->dfs, succ, &env->tmp_alloc);
            }
        }

        n = bb->children.nelem;
        for (i=0; i<n; i++) {
            int j, m;
            child = VA_ELEM(struct partial_bb *, &bb->children, i);
            m = child->dfs.nelem;
            for (j=0; j<m; j++) {
                df = VA_ELEM(struct partial_bb *, &child->dfs, j);
                if (df->idom != bb) {
                    VA_PUSH_P(struct partial_bb *, &bb->dfs, df, &env->tmp_alloc);
                }
            }
        }
    }
}


static int
insert_phi(struct partial_bb **bbs,
           int num_bb,
           struct partial_var_info *var_info,
           int num_var_info,
           int id,
           ctrump_bitmap_t tmp_bitmap,
           struct ctrump_mempool *cfg_alloc)
{
    int i,j;

    for (i=0; i<num_var_info; i++) {
        ctrump_bitmap_t modified_at = var_info[i].modified_at;

        while (1) {
            /* 各BBで挿入するphiを求める */
            struct partial_bb *m_bb, **dfs;
            int m_bb_idx = ctrump_bitmap_ffs(modified_at, num_bb), num_df;

            if (m_bb_idx < 0)
                break;

            ctrump_bitmap_clear(modified_at, m_bb_idx);
            m_bb = bbs[m_bb_idx];

            num_df = m_bb->dfs.nelem;
            dfs = m_bb->dfs.elements;

            for (j=0; j<num_df; j++) {
                struct partial_bb *df_bb = dfs[j];
                if (ctrump_bitmap_p(df_bb->live, i) &&
                    (! ctrump_bitmap_p(df_bb->phi_inserted, i)))
                {
                    ctrump_bitmap_set(df_bb->phi_inserted, i);
                    ctrump_bitmap_set(modified_at, df_bb->order);
                }
            }
        }
    }

    for (i=0; i<num_bb; i++) {
        /* phiを挿入する */
        struct partial_bb *bb = bbs[i];
        int num_phi = ctrump_bitmap_popcnt(bb->phi_inserted, num_var_info);
        int num_pred = bb->preds.nelem;

        ctrump_bitmap_copy(tmp_bitmap, bb->phi_inserted, num_var_info);

        bb->phi_nodes = ctrump_mempool_alloc(cfg_alloc, sizeof(struct ctrump_phi_node)*num_phi);
        for (j=0; j<num_phi; j++) {
            int var_idx = ctrump_bitmap_ffs(tmp_bitmap, num_var_info);
            ctrump_bitmap_clear(tmp_bitmap, var_idx);

            bb->phi_nodes[j].id = id++;
            bb->phi_nodes[j].num_merge = num_pred;
            bb->phi_nodes[j].var_index = var_idx;
            bb->phi_nodes[j].nodes = ctrump_mempool_alloc(cfg_alloc, sizeof(struct ctrump_pdg_node*)*num_pred);
        }
        bb->num_phi = num_phi;
    }

    return id;
}

static struct ctrump_pdg_node *
alloc_pdg_node(struct ctrump_varray *pdg_node_list,
               struct ctrump_mempool *alloc,
               struct ctrump_stmt *at,
               int *id,
               enum ctrump_pdg_node_code code)
{
    struct ctrump_pdg_node *pdg = ctrump_mempool_alloc(alloc, sizeof(*pdg));
    pdg->code = code;
    pdg->id = (*id)++;
    pdg->at = at;
    VA_PUSH(struct ctrump_pdg_node*,pdg_node_list, pdg);
    return pdg;
}

static int
recog_reductive(struct ctrump_expr *e,
                struct ctrump_var *v,
                int is_float,
                enum ctrump_reductive_expr_code *ret_code,
                struct ctrump_expr **ret_expr)
{
tailcall:
    switch (e->code) {
    case CTRUMP_EXPR_BIN_ASSIGN:
    case CTRUMP_EXPR_BIN_COMMA:
        e = e->u.binary.rhs;
        goto tailcall;

    case CTRUMP_CASE_BIN_ARITH_EXPR:
    case CTRUMP_CASE_BIN_EQ_EXPR:
    case CTRUMP_CASE_BIN_OP_ASSIGN_EXPR:
    case CTRUMP_CASE_BIN_LOG_EXPR:
    {
        /* fixme : more strictness
         *   should reject 'i += x+i'
         */
        struct ctrump_expr *l=e->u.binary.lhs, *r=e->u.binary.rhs;

        if (l->code == CTRUMP_EXPR_VARREF &&
            l->u.varref.var == v) {
            /* v = l op r  && v == l */

            if (ctrump_expr_occur_var(r, v)) {
                /* 'v = v + (3+v)' is not reductive*/
                return 0;
            }

#define REDUC_CASE_LHS(ecode,rcode,r)           \
            case ecode:                         \
                *ret_code = rcode;              \
                *ret_expr = r;                  \
                return 1;

            if (is_float) {
                switch (e->code) {
                    REDUC_CASE_LHS(CTRUMP_EXPR_BIN_ADD, CTRUMP_REDUCTIVE_FADD, r);
                    REDUC_CASE_LHS(CTRUMP_EXPR_BIN_SUB, CTRUMP_REDUCTIVE_FSUB, r);
                    REDUC_CASE_LHS(CTRUMP_EXPR_BIN_MUL, CTRUMP_REDUCTIVE_FMUL, r);

                default:
                    return 0;
                }
            } else {
                switch (e->code) {
                    REDUC_CASE_LHS(CTRUMP_EXPR_BIN_ADD, CTRUMP_REDUCTIVE_ADD, r);
                    REDUC_CASE_LHS(CTRUMP_EXPR_BIN_SUB, CTRUMP_REDUCTIVE_SUB, r);
                    REDUC_CASE_LHS(CTRUMP_EXPR_BIN_MUL, CTRUMP_REDUCTIVE_MUL, r);
                    REDUC_CASE_LHS(CTRUMP_EXPR_BIN_LOR, CTRUMP_REDUCTIVE_LOR, r);
                    REDUC_CASE_LHS(CTRUMP_EXPR_BIN_LAND, CTRUMP_REDUCTIVE_LAND, r);
                    REDUC_CASE_LHS(CTRUMP_EXPR_BIN_BOR, CTRUMP_REDUCTIVE_BOR, r);
                    REDUC_CASE_LHS(CTRUMP_EXPR_BIN_BAND, CTRUMP_REDUCTIVE_BAND, r);
                    REDUC_CASE_LHS(CTRUMP_EXPR_BIN_BXOR, CTRUMP_REDUCTIVE_BXOR, r);

                default:
                    return 0;
                }
            }
        } else if (r->code == CTRUMP_EXPR_VARREF &&
                   r->u.varref.var == v) {
            /* v = l op r && v == r */

            if (ctrump_expr_occur_var(l,v)) {
                return 0;
            }

            if (is_float) {
                switch (e->code) {
                    REDUC_CASE_LHS(CTRUMP_EXPR_BIN_ADD, CTRUMP_REDUCTIVE_FADD, l);
                    REDUC_CASE_LHS(CTRUMP_EXPR_BIN_SUB, CTRUMP_REDUCTIVE_FSUB, l);
                    REDUC_CASE_LHS(CTRUMP_EXPR_BIN_MUL, CTRUMP_REDUCTIVE_FMUL, l);

                default:
                    return 0;
                }
            } else {
                switch (e->code) {
                    REDUC_CASE_LHS(CTRUMP_EXPR_BIN_ADD, CTRUMP_REDUCTIVE_ADD, l);
                    REDUC_CASE_LHS(CTRUMP_EXPR_BIN_SUB, CTRUMP_REDUCTIVE_SUB, l);
                    REDUC_CASE_LHS(CTRUMP_EXPR_BIN_MUL, CTRUMP_REDUCTIVE_MUL, l);
                    REDUC_CASE_LHS(CTRUMP_EXPR_BIN_LOR, CTRUMP_REDUCTIVE_LOR, r);
                    REDUC_CASE_LHS(CTRUMP_EXPR_BIN_LAND, CTRUMP_REDUCTIVE_LAND, r);
                    REDUC_CASE_LHS(CTRUMP_EXPR_BIN_BOR, CTRUMP_REDUCTIVE_BOR, l);
                    REDUC_CASE_LHS(CTRUMP_EXPR_BIN_BAND, CTRUMP_REDUCTIVE_BAND, l);
                    REDUC_CASE_LHS(CTRUMP_EXPR_BIN_BXOR, CTRUMP_REDUCTIVE_BXOR, l);

                default:
                    return 0;
                }
            }
        } else {
            return 0;
        }
        return 0;
    }

    case CTRUMP_EXPR_PAREN:
        e = e->u.paren.expr;
        goto tailcall;

    case CTRUMP_EXPR_MACRO_EXPAND:
        e = e->u.macro_expand.expanded;
        goto tailcall;


    case CTRUMP_EXPR_ARRREF:
    case CTRUMP_EXPR_MEMBER_REF:
    case CTRUMP_EXPR_PTR_MEMBER_REF:
    case CTRUMP_EXPR_UNA_PTRREF:
    case CTRUMP_EXPR_UNA_POS:
    case CTRUMP_EXPR_UNA_NEG:
    case CTRUMP_EXPR_UNA_BCMPL:
    case CTRUMP_EXPR_UNA_LNEG:
    case CTRUMP_EXPR_UNA_ADDR:
    case CTRUMP_EXPR_CALL:
    case CTRUMP_EXPR_VARREF:
    case CTRUMP_CASE_CONSTANT_TERM:
    case CTRUMP_EXPR_EMPTY:
    case CTRUMP_EXPR_CONDITIONAL:
    case CTRUMP_EXPR_INITIALIZER:
        return 0;

    case CTRUMP_EXPR_CAST:
    case CTRUMP_EXPR_IMPLICIT_CAST:
        /* ??
         *  int v;
         *  v = (float)(v + x);
         */
        return 0;

    case CTRUMP_EXPR_TEXT:
    case CTRUMP_EXPR_IVTMP:

    case CTRUMP_EXPR_UNA_PRE_INC:
    case CTRUMP_EXPR_UNA_PRE_DEC:
    case CTRUMP_EXPR_UNA_POST_INC:
    case CTRUMP_EXPR_UNA_POST_DEC:
        /* maybe bug */
        ctrump_unreachable("invalid expr code");
    }

    return 0;
}

static struct ctrump_pdg_node *
ssa_node_store_expr(enum ctrump_expr_code op_code,
                    struct ctrump_var *var,
                    struct ctrump_expr *store_val,
                    struct ctrump_varray *pdg_node_list,
                    struct ctrump_pdg_node *old_val,
                    struct ctrump_stmt *at,
                    struct ctrump_mempool *alloc,
                    int *id)
{
    struct ctrump_pdg_node *pdg;
    struct ctrump_expr *reduc_val;
    enum ctrump_reductive_expr_code reduc_op;
    struct ctrump_texpr *t = store_val->type;
    int is_float = ctrump_type_is_float(t);
    int is_reduc;
    enum ctrump_incremental_expr_code incr_code;

    switch (op_code) {
    case CTRUMP_EXPR_UNA_PRE_INC:
    case CTRUMP_EXPR_UNA_PRE_DEC:
    case CTRUMP_EXPR_UNA_POST_INC:
    case CTRUMP_EXPR_UNA_POST_DEC:
        pdg = alloc_pdg_node(pdg_node_list, alloc, at, id, CTRUMP_PDG_VALUE_INCREMENTAL);
        pdg->u.incr.prev_val = old_val;

        if (is_float) {
            switch(op_code) {
            case CTRUMP_EXPR_UNA_POST_INC:
            case CTRUMP_EXPR_UNA_PRE_INC:
                incr_code = CTRUMP_PDG_FINC;
                break;

            case CTRUMP_EXPR_UNA_PRE_DEC:incr_code = CTRUMP_PDG_FDEC;
            case CTRUMP_EXPR_UNA_POST_DEC:
                incr_code = CTRUMP_PDG_FDEC;
                break;

            default:
                ctrump_unreachable("incr op");
            }
        } else {
            switch(op_code) {
            case CTRUMP_EXPR_UNA_POST_INC:
            case CTRUMP_EXPR_UNA_PRE_INC:
                incr_code = CTRUMP_PDG_INC;
                break;

            case CTRUMP_EXPR_UNA_PRE_DEC:incr_code = CTRUMP_PDG_DEC;
            case CTRUMP_EXPR_UNA_POST_DEC:
                incr_code = CTRUMP_PDG_FDEC;
                break;

            default:
                ctrump_unreachable("incr op");
            }
        }
        pdg->u.incr.op = incr_code;
        return pdg;

    case CTRUMP_EXPR_BIN_ADD_ASSIGN:
    case CTRUMP_EXPR_BIN_SUB_ASSIGN:
    case CTRUMP_EXPR_BIN_MUL_ASSIGN:
        pdg = alloc_pdg_node(pdg_node_list, alloc, at, id, CTRUMP_PDG_VALUE_REDUCTION);
        pdg->u.reduction.value = store_val;
        pdg->u.reduction.prev_val = old_val;
        if (is_float) {
            switch (op_code) {
            case CTRUMP_EXPR_BIN_ADD_ASSIGN:
                reduc_op = CTRUMP_REDUCTIVE_FADD;
                break;
            case CTRUMP_EXPR_BIN_SUB_ASSIGN:
                reduc_op = CTRUMP_REDUCTIVE_FSUB;
                break;
            case CTRUMP_EXPR_BIN_MUL_ASSIGN:
                reduc_op = CTRUMP_REDUCTIVE_FMUL;
                break;

            default:
                ctrump_unreachable("reduc op");
            }
        } else {
            switch (op_code) {
            case CTRUMP_EXPR_BIN_ADD_ASSIGN:
                reduc_op = CTRUMP_REDUCTIVE_ADD;
                break;
            case CTRUMP_EXPR_BIN_SUB_ASSIGN:
                reduc_op = CTRUMP_REDUCTIVE_SUB;
                break;
            case CTRUMP_EXPR_BIN_MUL_ASSIGN:
                reduc_op = CTRUMP_REDUCTIVE_MUL;
                break;

            default:
                ctrump_unreachable("reduc op");
            }
        }
        pdg->u.reduction.op = reduc_op;
        return pdg;

    default:
        break;
    }

    is_reduc = recog_reductive(store_val, var, is_float, &reduc_op, &reduc_val);

    if (is_reduc) {
        pdg = alloc_pdg_node(pdg_node_list, alloc, at, id, CTRUMP_PDG_VALUE_REDUCTION);
        pdg->u.reduction.op = reduc_op;
        pdg->u.reduction.value = reduc_val;
        pdg->u.reduction.prev_val = old_val;
    } else {
        pdg = alloc_pdg_node(pdg_node_list, alloc, at, id, CTRUMP_PDG_VALUE_EXPR);
        pdg->u.expr.val = store_val;
        pdg->u.expr.store_op = op_code;
    }

    return pdg;
}


static int
assign_pdg_node_bb(struct ctrump_varray *pdg_node_list,
                   struct partial_bb *bb,
                   struct partial_var_info *var_info,
                   int num_var_info,
                   int id, struct ctrump_mempool *cfg_alloc)
{
    int i,j,k;
    struct ordered_load_store_node *ls;
    struct ctrump_var_ref *refs = bb->refs.elements;
    struct ctrump_var_store *stores = bb->stores.elements;
    struct partial_bb **succs, **children;
    int num_ls, num_phi, num_succ, num_child;
    for (i=0; i<num_var_info; i++) {
        int depth = var_info[i].ssa_var_stack.nelem;
        VA_PUSH(int, &var_info[i].stack_depth, depth);
    }

    num_phi = bb->num_phi;
    for (i=0; i<num_phi; i++) {
        struct ctrump_phi_node *n = &bb->phi_nodes[i];
        struct partial_var_info *vi = &var_info[n->var_index];
        struct ctrump_pdg_node *phi_pdg = alloc_pdg_node(pdg_node_list, cfg_alloc, NULL, &id, CTRUMP_PDG_VALUE_PHI);

        phi_pdg->u.phi = n;

        VA_PUSH(struct ctrump_pdg_node *, &vi->ssa_var_stack, phi_pdg);
    }

    ls = bb->ordered_load_store.elements;
    num_ls = bb->ordered_load_store.nelem;

    for (i=0; i<num_ls; i++) {
        struct ordered_load_store_node *n = &ls[i];
        struct partial_var_info *vi = &var_info[n->var_idx];
        struct ctrump_var_store *vs;
        struct ctrump_var_ref *vr;
        struct ctrump_pdg_node *pdg, *old_pdg;

        switch (n->code) {
        case LOAD:
            pdg = VA_TOP(struct ctrump_pdg_node*, &vi->ssa_var_stack);
            vr = &refs[n->op_idx];
            vr->ref_expr->u.varref.pdg = pdg;
            break;

        case STORE:
            vs = &stores[n->op_idx];
            old_pdg = VA_TOP(struct ctrump_pdg_node*, &vi->ssa_var_stack);

            pdg = ssa_node_store_expr(vs->store_op, vs->var, vs->val, pdg_node_list, old_pdg, vs->at, cfg_alloc, &id);

            vs->new_val = pdg;
            VA_PUSH(struct ctrump_pdg_node*, &vi->ssa_var_stack, pdg);
            break;

        case INIT:
            ctrump_fixme("init");
            break;
        }
    }

    succs = bb->succs.elements;
    num_succ = bb->succs.nelem;

    /* update succ's phi */
    for (i=0; i<num_succ; i++) {
        struct partial_bb *succ = succs[i];
        struct partial_bb **preds;
        struct ctrump_phi_node *phi_nodes;

        /* find self */
        preds = succ->preds.elements;
        for (j=0; ;j++) {
            if (preds[j] == bb) {
                break;
            }
        }

        phi_nodes = succ->phi_nodes;
        num_phi = succ->num_phi;
        for (k=0; k<num_phi; k++) {
            struct ctrump_phi_node *n = &phi_nodes[k];
            struct partial_var_info *vi = &var_info[n->var_index];
            struct ctrump_pdg_node *pdg = VA_TOP(struct ctrump_pdg_node *, &vi->ssa_var_stack);
            n->nodes[j] = pdg;
        }
    }

    children = bb->children.elements;
    num_child = bb->children.nelem;
    for (i=0; i<num_child; i++) {
        id = assign_pdg_node_bb(pdg_node_list, children[i], var_info, num_var_info, id, cfg_alloc);
    }

    for (i=0; i<num_var_info; i++) {
        int depth = VA_POP(int, &var_info[i].stack_depth);
        var_info[i].ssa_var_stack.nelem = depth;
    }

    return id;
}

static int
assign_pdg_node(struct ctrump_varray *pdg_node_list,
                struct partial_bb *entry,
                struct partial_var_info *var_info,
                int num_var_info,
                int id,
                struct ctrump_mempool *cfg_alloc)
{
    int i;
    for (i=0; i<num_var_info; i++) {
        enum ctrump_pdg_node_code code;
        struct ctrump_pdg_node *pdg;

        ctrump_varray_init(&var_info[i].ssa_var_stack, 4, sizeof(struct ctrump_pdg_node*));
        ctrump_varray_init(&var_info[i].stack_depth, 4, sizeof(int));

        switch (var_info[i].result.var->stor_class) {
        case CTRUMP_STOR_CLASS_ARGMENT:
            code = CTRUMP_PDG_VALUE_ARG;
            break;

        case CTRUMP_STOR_CLASS_STATIC:
        case CTRUMP_STOR_CLASS_EXTERN:
        case CTRUMP_STOR_CLASS_EXTDEF:
            code = CTRUMP_PDG_VALUE_GLOBAL;
            break;

        default:
            code = CTRUMP_PDG_VALUE_UNINITIALIZED;
            break;
        }

        pdg = alloc_pdg_node(pdg_node_list, cfg_alloc, NULL, &id, code);
        VA_PUSH(struct ctrump_pdg_node*, &var_info[i].ssa_var_stack, pdg);
    }

    id = assign_pdg_node_bb(pdg_node_list, entry, var_info, 
                            num_var_info, id, cfg_alloc);

    for (i=0; i<num_var_info; i++) {
        ctrump_varray_discard(&var_info[i].ssa_var_stack);
        ctrump_varray_discard(&var_info[i].stack_depth);
    }

    return id;
}

static int
extract_load_store_expr_rval(struct ctrump_expr *e,
                             struct ctrump_stmt *at,
                             struct partial_bb *bb,
                             struct ctrump_intmap *var_info_map,
                             struct ctrump_build_cfg_error *error,
                             struct ctrump_mempool *cfg_alloc,
                             struct ctrump_mempool *tmp_alloc);

#define CHECK_ERROR(e) {int r = (e); if (r < 0) return r;}

static struct ctrump_subscript *
append_nd_subscript(struct ctrump_varray *subscripts, /* struct ctrump_subscript */
                    struct ctrump_varray *nd_subscripts, /* struct ctrump_subscript_nd */
                    struct ctrump_subscript *s,
                    struct ctrump_texpr *load_data_texpr,
                    struct ctrump_expr *subscript,
                    struct ctrump_mempool *cfg_alloc)
{
    struct ctrump_subscript_nd *nds;

    if (ctrump_is_scalar_type(load_data_texpr)) {
        if (nd_subscripts->nelem == 0) {
            /* first subscript */
        } else {
            s->num_nd_subscript = nd_subscripts->nelem;
            s->nd_subscripts = ctrump_varray_copy(nd_subscripts, cfg_alloc);

            VA_NEWELEM(subscripts);
            s = VA_LAST_PTR(struct ctrump_subscript, subscripts);
        }

        nd_subscripts->nelem = 0;

        VA_NEWELEM(nd_subscripts);
        nds = VA_LAST_PTR(struct ctrump_subscript_nd, nd_subscripts);
        nds->code = CTRUMP_SUBSCRIPT_TERMINAL;
        nds->u.terminal.expr = subscript;
        nds->u.terminal.load_type = load_data_texpr;
    } else if (load_data_texpr->code == CTRUMP_TYPE_UNION ||
               load_data_texpr->code == CTRUMP_TYPE_STRUCT) {
        VA_NEWELEM(nd_subscripts);
        nds = VA_LAST_PTR(struct ctrump_subscript_nd, nd_subscripts);

        nds->code = CTRUMP_SUBSCRIPT_LOAD_RECORD;
        nds->u.load_record.load_type = load_data_texpr;
        nds->u.load_record.expr = subscript;
    } else {
        VA_NEWELEM(nd_subscripts);
        nds = VA_LAST_PTR(struct ctrump_subscript_nd, nd_subscripts);

        nds->code = CTRUMP_SUBSCRIPT_COEF_ARRAY;
        nds->u.array_coef.coef = load_data_texpr->u.array.size;
        nds->u.array_coef.expr = subscript;
    }

    return s;
}

static struct ctrump_subscript *
append_record_member_ref(struct ctrump_varray *subscripts, /* struct ctrump_subscript */
                         struct ctrump_varray *nd_subscripts, /* struct ctrump_subscript_nd */
                         struct ctrump_subscript *s,
                         struct ctrump_member_ref *ref,
                         struct ctrump_texpr *load_data_type,
                         int is_pointer,
                         struct ctrump_mempool *cfg_alloc)
{
    struct ctrump_subscript_nd *nds;
    struct ctrump_texpr *type;
    VA_NEWELEM(nd_subscripts);
    nds = VA_LAST_PTR(struct ctrump_subscript_nd, nd_subscripts);

    type = ref->obj_expr->type;
    if (is_pointer) {
        type = ctrump_retrieve_pointer_type(type);
        assert(type);
    }

    if (ctrump_is_scalar_type(load_data_type)) {
        nds->code = CTRUMP_SUBSCRIPT_RECORD_MEMBER_TERMINAL;
        nds->u.record_member_terminal.member_name = ref->member_name;
        nds->u.record_member_terminal.record_type = type;
        nds->u.record_member_terminal.load_type = load_data_type;
    } else {
        nds->code = CTRUMP_SUBSCRIPT_RECORD_MEMBER;
        nds->u.record_member.member_name = ref->member_name;
        nds->u.record_member.record_type = type;
    }

    return s;
}

static int
recog_array_access(struct ctrump_expr **ret_array,
                   struct ctrump_subscript **ret_vec,
                   int *num_ret,
                   struct ctrump_expr *access_expr,
                   struct partial_bb *bb,
                   struct ctrump_intmap *var_info_map,
                   struct ctrump_build_cfg_error *error,
                   struct ctrump_stmt *at,
                   struct ctrump_mempool *cfg_alloc,
                   struct ctrump_mempool *tmp_alloc)
{
    struct ctrump_subscript *ret;
    struct ctrump_expr *peeled_array;

    /* a[i][j] : array access */
    struct ctrump_subscript *subscript_elems;
    struct ctrump_subscript *s;
    struct ctrump_varray subscripts;
    struct ctrump_varray nd_subscripts;
    struct ctrump_expr *array, *subscript;
    int i, n;

    ctrump_varray_init(&subscripts, 4, sizeof(struct ctrump_subscript));
    ctrump_varray_init(&nd_subscripts, 4, sizeof(struct ctrump_subscript_nd));

    VA_NEWELEM(&subscripts);
    s = VA_LAST_PTR(struct ctrump_subscript, &subscripts);

    array = access_expr;

    while (1) {
        struct ctrump_texpr *array_texpr;
        enum ctrump_expr_code expr_code;
        peeled_array = ctrump_peel_cast_to_pointer_from_array(array);
        array_texpr = peeled_array->type;
        array_texpr = ctrump_get_unqualified_type(array_texpr);

        expr_code = peeled_array->code;

        switch (expr_code) {
        case CTRUMP_EXPR_ARRREF:
            subscript = peeled_array->u.arr_ref.subscript;

            CHECK_ERROR(extract_load_store_expr_rval(subscript, at, bb, var_info_map, error, cfg_alloc, tmp_alloc));
            s = append_nd_subscript(&subscripts, &nd_subscripts,
                                    s, array_texpr,
                                    subscript, cfg_alloc);

            array = peeled_array->u.arr_ref.array;
            break;

        case CTRUMP_EXPR_PTR_MEMBER_REF:
            s = append_record_member_ref(&subscripts, &nd_subscripts,
                                         s, &peeled_array->u.member_ref, array_texpr, 1, cfg_alloc);
            /* p->x => p[0].x */
            peeled_array = ctrump_peel_cast_to_pointer_from_array(peeled_array);
            array_texpr = peeled_array->type;
            array_texpr = ctrump_get_unqualified_type(array_texpr);
            s = append_nd_subscript(&subscripts, &nd_subscripts,
                                    s, array_texpr,
                                    NULL, cfg_alloc);

            array = peeled_array->u.member_ref.obj_expr;
            break;

        case CTRUMP_EXPR_MEMBER_REF:
            s = append_record_member_ref(&subscripts, &nd_subscripts,
                                         s, &peeled_array->u.member_ref, array_texpr, 0, cfg_alloc);
            array = peeled_array->u.member_ref.obj_expr;
            break;

        case CTRUMP_EXPR_UNA_PTRREF:
            s = append_nd_subscript(&subscripts, &nd_subscripts,
                                    s, array_texpr,
                                    NULL, cfg_alloc);
            array = peeled_array->u.unary.expr;
            break;

        default:
            array = peeled_array;
            goto end;
        }
    }
end:

    s->num_nd_subscript = nd_subscripts.nelem;
    s->nd_subscripts = ctrump_varray_close(&nd_subscripts, cfg_alloc);

    n = subscripts.nelem;
    subscript_elems = subscripts.elements;
    ret = ctrump_mempool_alloc(cfg_alloc, sizeof(*ret)*n);

    for (i=0; i<n; i++) {
        ret[i] = subscript_elems[i];
    }

    *num_ret = n;
    *ret_vec = ret;

    ctrump_varray_discard(&subscripts);

    *ret_array = array;
    return 0;
}

static void
append_ordered_memop(struct ctrump_varray *memop,
                     enum ctrump_load_store_t load_store,
                     int idx, struct ctrump_mempool *tmp_alloc)
{
    struct ctrump_ordered_memory_load_store_node *n;
    VA_NEWELEM_P(memop, tmp_alloc);
    n = VA_LAST_PTR(struct ctrump_ordered_memory_load_store_node, memop);
    n->code = load_store;
    n->op_index = idx;
}

static int
append_memory_store(struct ctrump_varray *store,
                    struct ctrump_varray *ordered,
                    struct partial_bb *bb,
                    struct ctrump_intmap *var_info_map,
                    struct ctrump_build_cfg_error *error,
                    struct ctrump_stmt *at_stmt,
                    enum ctrump_expr_code store_op,
                    struct ctrump_expr *dest_expr,
                    struct ctrump_expr *val,
                    int flags,
                    struct ctrump_mempool *cfg_alloc,
                    struct ctrump_mempool *tmp_alloc)
{
    int num_subscript;
    struct ctrump_subscript *subscript;
    struct ctrump_expr *array_expr;
    struct ctrump_memory_store *ms;
    int idx;

    CHECK_ERROR(recog_array_access(&array_expr, &subscript, &num_subscript, dest_expr,
                                   bb, var_info_map, error, at_stmt, cfg_alloc, tmp_alloc));


    if (array_expr) {
        CHECK_ERROR(extract_load_store_expr_rval(array_expr, at_stmt, bb, var_info_map, error, cfg_alloc, tmp_alloc));
    }

    idx = store->nelem;

    VA_NEWELEM_P(store, tmp_alloc);
    ms = VA_LAST_PTR(struct ctrump_memory_store, store);
    ms->mem_access.at_stmt = at_stmt;
    ms->mem_access.at_expr = dest_expr;

    ms->mem_access.array = array_expr;
    ms->mem_access.subscripts = subscript;
    ms->mem_access.num_subscript = num_subscript;
    ms->mem_access.flags = flags;
    ms->val = val;
    ms->store_op = store_op;

    append_ordered_memop(ordered, CTRUMP_MEMORY_STORE, idx, tmp_alloc);

    return 0;
}

static void
add_var_loadstore(struct partial_bb *bb,
                  enum load_store_t code,
                  int op_idx,
                  int var_idx,
                  struct ctrump_mempool *tmp_alloc)
{
    struct ordered_load_store_node *n;
    VA_NEWELEM_P(&bb->ordered_load_store, tmp_alloc);
    n = VA_LAST_PTR(struct ordered_load_store_node, &bb->ordered_load_store);
    n->code = code;
    n->op_idx = op_idx;
    n->var_idx = var_idx;
}

static void
add_var_store(struct partial_bb *bb,
              struct partial_var_info *vi,
              struct ctrump_varray *stores,
              struct ctrump_stmt *at,
              struct ctrump_var *var,
              struct ctrump_expr *var_ref_expr,
              struct ctrump_expr *val_expr, /* NULL if set by initializer */
              struct ctrump_pdg_node *pdg, /* NULL if set by store (set after) */
              enum ctrump_expr_code store_op,
              int flags,
              struct ctrump_mempool *tmp_alloc,
              enum load_store_t store_code)
{
    struct ctrump_var_store *d;
    int op_idx = stores->nelem;
    VA_NEWELEM_P(stores, tmp_alloc);
    d = VA_LAST_PTR(struct ctrump_var_store, stores);
    d->at = at;
    d->var = var;
    d->val = val_expr;
    d->store_op = store_op;
    d->flags = flags;
    d->var_ref = var_ref_expr;

    ctrump_bitmap_set(bb->kill, vi->result.index);
    ctrump_bitmap_set(vi->modified_at, bb->order);

    add_var_loadstore(bb, store_code, op_idx, vi->result.index, tmp_alloc);
}

              
static int
extract_load_store_assign(enum ctrump_expr_code store_op,
                          struct ctrump_expr *lhs,
                          struct ctrump_expr *val_expr,
                          struct ctrump_stmt *at,
                          struct partial_bb *bb,
                          struct ctrump_intmap *var_info_map,
                          struct ctrump_build_cfg_error *error,
                          struct ctrump_mempool *cfg_alloc,
                          struct ctrump_mempool *tmp_alloc)
{
    int found;
    int flags = 0;
    struct partial_var_info *vi;

    struct ctrump_varray *stores = &bb->stores;
    struct ctrump_varray *mem_store = &bb->arr_stores;
    struct ctrump_varray *mem_ordered = &bb->ordered_mem_load_store;

    lhs = ctrump_peel_paren(lhs);

    switch (lhs->code) {
    case CTRUMP_EXPR_VARREF:
        vi = ctrump_intmap_lookup(var_info_map, &found, lhs->u.varref.var->id);
        assert(found);

        add_var_store(bb, vi, stores, at, lhs->u.varref.var, lhs, val_expr,
                      NULL, store_op, flags, tmp_alloc, STORE);

        lhs->u.varref.pdg = NULL;

        if (flags & CTRUMP_MEMORY_ACCESS_PARTIAL) {
            /*
             *   struct { int x; int y; } a
             *   a.x = 10
             *  is interpreted as 
             *   a_new.x = 10
             *   a_new.y = a_old.y
             *   a = a_new;
             *  So, member update uses previous value.
             */
            ctrump_bitmap_set(bb->use, vi->result.index);
        }

        break;

    case CTRUMP_EXPR_UNA_PTRREF:
    case CTRUMP_EXPR_ARRREF:
    case CTRUMP_EXPR_PTR_MEMBER_REF:
    case CTRUMP_EXPR_MEMBER_REF:
        CHECK_ERROR(append_memory_store(mem_store, mem_ordered, bb, var_info_map, error,
                                        at, store_op, lhs, val_expr, flags,
                                        cfg_alloc, tmp_alloc));
        break;

    default:
        error->code = CTRUMP_BUILD_CFG_ERROR_INVALID_LVALUE;
        error->stmt = at;
        return -1;
    }

    return 0;
}

static int
append_memory_load(struct ctrump_varray *aload,
                   struct ctrump_varray *ordered,
                   struct partial_bb *bb,
                   struct ctrump_intmap *var_info_map,
                   struct ctrump_build_cfg_error *error,
                   struct ctrump_stmt *at_stmt,
                   struct ctrump_expr *load_expr,
                   struct ctrump_mempool *cfg_alloc,
                   struct ctrump_mempool *tmp_alloc)
{
    struct ctrump_memory_load *al;
    struct ctrump_subscript *subscripts;
    int num_subscript;
    int idx = aload->nelem;
    struct ctrump_expr *next_array_expr;

    CHECK_ERROR(recog_array_access(&next_array_expr, &subscripts, &num_subscript, load_expr,
                                   bb, var_info_map, error, at_stmt, cfg_alloc, tmp_alloc));
    if (next_array_expr) {
        CHECK_ERROR(extract_load_store_expr_rval(next_array_expr, at_stmt, bb,
                                                 var_info_map, error, cfg_alloc, tmp_alloc));
    }

    VA_NEWELEM_P(aload, tmp_alloc);
    al = VA_LAST_PTR(struct ctrump_memory_load, aload);
    al->mem_access.subscripts = subscripts;
    al->mem_access.num_subscript = num_subscript;
    al->mem_access.flags = 0;
    al->mem_access.array = next_array_expr;

    al->mem_access.at_stmt = at_stmt;
    al->mem_access.at_expr = load_expr;

    append_ordered_memop(ordered, CTRUMP_MEMORY_LOAD, idx, tmp_alloc);

    return 0;
}

static int extract_load_store_initializer(struct ctrump_initializer *initializer,
                                          struct ctrump_stmt *at,
                                          struct partial_bb *bb,
                                          struct ctrump_intmap *var_info_map,
                                          struct ctrump_build_cfg_error *error,
                                          struct ctrump_mempool *cfg_alloc,
                                          struct ctrump_mempool *tmp_alloc);

static int
extract_load_store_initializer_list(struct ctrump_initializer_list *init_list,
                                    struct ctrump_stmt *at,
                                    struct partial_bb *bb,
                                    struct ctrump_intmap *var_info_map,
                                    struct ctrump_build_cfg_error *error,
                                    struct ctrump_mempool *cfg_alloc,
                                    struct ctrump_mempool *tmp_alloc)
{
    int i, j, n, m;
    n = init_list->num_elem;
    for (i=0; i<n; i++) {
        struct ctrump_initializer_list_elem *e = &init_list->elems[i];

        m = e->num_designator;


        for (j=0; j<m; j++) {
            /* extract from designator : { [a[i]][b[j]] = 0; } */
            struct ctrump_designator *d = &e->designators_list[j];
            switch (d->code) {
            case CTRUMP_DESIGNATOR_INDEX:
                CHECK_ERROR(extract_load_store_expr_rval(d->u.index.index,
                                                         at, bb, var_info_map,
                                                         error, cfg_alloc, tmp_alloc));
                break;

            case CTRUMP_DESIGNATOR_IDENT:
                /* do nothing */
                break;
            }
        }

        CHECK_ERROR(extract_load_store_initializer(&e->initializer,
                                                   at, bb, var_info_map,
                                                   error, cfg_alloc, tmp_alloc));
    }

    return 0;
}

static int
extract_load_store_initializer(struct ctrump_initializer *initializer,
                               struct ctrump_stmt *at,
                               struct partial_bb *bb,
                               struct ctrump_intmap *var_info_map,
                               struct ctrump_build_cfg_error *error,
                               struct ctrump_mempool *cfg_alloc,
                               struct ctrump_mempool *tmp_alloc)
{
    switch (initializer->code) {
    case CTRUMP_INITIALIZER_EXPR:
        CHECK_ERROR(extract_load_store_expr_rval(initializer->u.expr,
                                                 at, bb, var_info_map,
                                                 error, cfg_alloc, tmp_alloc));
        break;

    case CTRUMP_INITIALIZER_NESTED:
        CHECK_ERROR(extract_load_store_initializer_list(initializer->u.nest,
                                                        at, bb, var_info_map,
                                                        error, cfg_alloc, tmp_alloc));
        break;

    case CTRUMP_INITIALIZER_EMPTY:
        break;
    }

    return 0;
}



static int
extract_load_store_expr_rval(struct ctrump_expr *e,
                             struct ctrump_stmt *at,
                             struct partial_bb *bb,
                             struct ctrump_intmap *var_info_map,
                             struct ctrump_build_cfg_error *error,
                             struct ctrump_mempool *cfg_alloc,
                             struct ctrump_mempool *tmp_alloc)
{
    struct ctrump_varray *refs = &bb->refs;
    struct ctrump_varray *aload = &bb->arr_loads;
    struct ctrump_var_ref *u;
    struct ctrump_expr *una;
    struct ctrump_binary_expr *bin;
    struct partial_var_info *vi;
    int var_index, op_index, found;
    struct ctrump_varray *mem_ordered = &bb->ordered_mem_load_store;
    int i, n;
    struct ctrump_initializer_list *init_list;

tailcall:
    switch (e->code) {
    case CTRUMP_EXPR_VARREF:
        op_index = refs->nelem;
        VA_NEWELEM_P(refs, tmp_alloc);
        u = VA_LAST_PTR(struct ctrump_var_ref, refs);
        u->at = at;
        u->ref_expr = e;

        vi = ctrump_intmap_lookup(var_info_map, &found, e->u.varref.var->id);
        var_index = vi->result.index;
        e->u.varref.pdg = NULL;

        add_var_loadstore(bb, LOAD, op_index, var_index, tmp_alloc);

        if (ctrump_bitmap_p(bb->kill, var_index) == 0) {
            ctrump_bitmap_set(bb->use, var_index);
        } else {
            /* already killed */
        }
        break;

    case CTRUMP_EXPR_CAST:
        e = e->u.cast.expr;
        goto tailcall;

    case CTRUMP_EXPR_IMPLICIT_CAST:
        e = e->u.implicit_cast.expr;
        goto tailcall;

    case CTRUMP_CASE_CONSTANT_TERM:
    case CTRUMP_EXPR_EMPTY:
        break;

    case CTRUMP_EXPR_BIN_COMMA:
    case CTRUMP_EXPR_BIN_ADD:
    case CTRUMP_EXPR_BIN_SUB:
    case CTRUMP_EXPR_BIN_MUL:
    case CTRUMP_EXPR_BIN_DIV:
    case CTRUMP_EXPR_BIN_MOD:
    case CTRUMP_EXPR_BIN_BAND:
    case CTRUMP_EXPR_BIN_BOR:
    case CTRUMP_EXPR_BIN_BXOR:
    case CTRUMP_EXPR_BIN_LSHIFT:
    case CTRUMP_EXPR_BIN_RSHIFT:
    case CTRUMP_EXPR_BIN_GT:
    case CTRUMP_EXPR_BIN_GE:
    case CTRUMP_EXPR_BIN_LT:
    case CTRUMP_EXPR_BIN_LE:
    case CTRUMP_EXPR_BIN_EQ:
    case CTRUMP_EXPR_BIN_NE:
        bin = &e->u.binary;
        CHECK_ERROR(extract_load_store_expr_rval(bin->lhs, at, bb, var_info_map, error, cfg_alloc, tmp_alloc));
        e = bin->rhs;
        goto tailcall;

    case CTRUMP_EXPR_BIN_ASSIGN:
        bin = &e->u.binary;
        CHECK_ERROR(extract_load_store_expr_rval(bin->rhs, at, bb, var_info_map, error, cfg_alloc, tmp_alloc));
        CHECK_ERROR(extract_load_store_assign(e->code, bin->lhs, bin->rhs,
                                              at, bb, var_info_map, error, cfg_alloc, tmp_alloc));
        break;

    case CTRUMP_CASE_BIN_OP_ASSIGN_EXPR:
        bin = &e->u.binary;
        CHECK_ERROR(extract_load_store_expr_rval(bin->lhs, at, bb, var_info_map, error, cfg_alloc, tmp_alloc));
        CHECK_ERROR(extract_load_store_expr_rval(bin->rhs, at, bb, var_info_map, error, cfg_alloc, tmp_alloc));
        CHECK_ERROR(extract_load_store_assign(e->code, bin->lhs, bin->rhs,
                                              at, bb, var_info_map, error, cfg_alloc, tmp_alloc));
        break;

    case CTRUMP_EXPR_UNA_PRE_INC:
    case CTRUMP_EXPR_UNA_POST_INC:
    case CTRUMP_EXPR_UNA_PRE_DEC:
    case CTRUMP_EXPR_UNA_POST_DEC:
        una = e->u.unary.expr;
        CHECK_ERROR(extract_load_store_expr_rval(una, at, bb, var_info_map, error, cfg_alloc, tmp_alloc));
        CHECK_ERROR(extract_load_store_assign(e->code, una, una,
                                              at, bb, var_info_map, error, cfg_alloc, tmp_alloc));
        break;

    case CTRUMP_EXPR_UNA_POS:
    case CTRUMP_EXPR_UNA_NEG:
    case CTRUMP_EXPR_UNA_BCMPL:
    case CTRUMP_EXPR_UNA_LNEG:
        e = e->u.unary.expr;
        goto tailcall;

    case CTRUMP_EXPR_PAREN:
        e = e->u.paren.expr;
        goto tailcall;

    case CTRUMP_EXPR_UNA_ADDR:
        e = e->u.unary.expr;
    addr_expr:
        switch (e->code) {
        case CTRUMP_EXPR_VARREF:
            e->u.varref.var->addressed = 1;
            e->u.varref.pdg = NULL;
            break;

        case CTRUMP_EXPR_ARRREF:
            /* &a[i] = (a+i) */
            CHECK_ERROR(extract_load_store_expr_rval(e->u.arr_ref.array, at, bb, var_info_map, error, cfg_alloc, tmp_alloc));
            e = e->u.arr_ref.subscript;
            goto tailcall;

        case CTRUMP_EXPR_UNA_PTRREF:
            /* &*a = a */
            e = e->u.unary.expr;
            goto tailcall;

        case CTRUMP_EXPR_PAREN:
            e = e->u.paren.expr;
            goto addr_expr;

        default:
            error->code = CTRUMP_BUILD_CFG_ERROR_INVALID_ADDRESSOP;
            error->stmt = at;
            return -1;
        }
        break;

    case CTRUMP_CASE_BIN_LOG_EXPR:
        /* rhs of logical expr is handled in other bb */
        bin = &e->u.binary;
        e = bin->lhs;
        goto tailcall;

    case CTRUMP_EXPR_CONDITIONAL:
        /* `then' and `else' expr are handled in other bb */
        e = e->u.cond.cond;
        goto tailcall;

    case CTRUMP_EXPR_CALL:
        n = e->u.call.num_args;
        for (i=0; i<n; i++) {
            CHECK_ERROR(extract_load_store_expr_rval(&e->u.call.args[i], at, bb, var_info_map,
                                                     error, cfg_alloc, tmp_alloc));
        }
        e = e->u.call.func_expr;
        goto tailcall;

    case CTRUMP_EXPR_UNA_PTRREF:
    case CTRUMP_EXPR_PTR_MEMBER_REF:
    case CTRUMP_EXPR_MEMBER_REF:
    case CTRUMP_EXPR_ARRREF:
        CHECK_ERROR(append_memory_load(aload, mem_ordered, bb, var_info_map, error, at,
                                       e, cfg_alloc, tmp_alloc));
        break;

    case CTRUMP_EXPR_INITIALIZER:
        init_list = &e->u.initializer.initializer;
        CHECK_ERROR(extract_load_store_initializer_list(init_list, at, bb, var_info_map,
                                                        error, cfg_alloc, tmp_alloc));
        
        break;

    case CTRUMP_EXPR_MACRO_EXPAND:
        ctrump_fixme("extract load store");
        break;

    case CTRUMP_EXPR_TEXT:
    case CTRUMP_EXPR_IVTMP:
        ctrump_unreachable("invalid expr code");
    }

    return 0;
}

static int
extract_load_store(struct partial_bb *bb,
                   struct ctrump_intmap *var_info_map,
                   struct ctrump_build_cfg_error *error,
                   struct ctrump_mempool *cfg_alloc,
                   struct ctrump_mempool *tmp_alloc)
{
    int i, n;
    struct partial_bb_expr *el = (struct partial_bb_expr*)bb->exprs.elements;

    n = bb->exprs.nelem;

    for (i=0; i<n; i++) {
        switch (el[i].code) {
        case BB_EXPR:
            CHECK_ERROR(extract_load_store_expr_rval(el[i].u.expr,
                                                     el[i].at,
                                                     bb,
                                                     var_info_map,
                                                     error,
                                                     cfg_alloc,
                                                     tmp_alloc));
            break;

        }
    }

    return 0;
}

static void
assign_var_info_expr(struct ctrump_varray *info,
                     struct ctrump_intmap *info_map,
                     struct ctrump_expr *e,
                     int num_bb,
                     struct ctrump_mempool *tmp_alloc)
{
    struct ctrump_binary_expr *bin;
    struct partial_var_info *vi;
    struct ctrump_var *v;
    struct ctrump_intmap_bucket *b;
    int found;
    int n, i;

tailcall:
    switch (e->code) {
    case CTRUMP_EXPR_VARREF:
        v = e->u.varref.var;
        b = ctrump_intmap_lookup_add(info_map, &found, v->id);
        if (found == 0) {
            int index = info->nelem;
            VA_NEWELEM_P(info, tmp_alloc);
            vi = VA_LAST_PTR(struct partial_var_info, info);
            vi->result.index = index;
            vi->result.var = v;
            vi->modified_at = zero_bmp(num_bb, tmp_alloc);

            b->val = (void*)(intptr_t)index;
        }
        break;

    case CTRUMP_EXPR_CAST:
        e = e->u.cast.expr;
        goto tailcall;

    case CTRUMP_EXPR_IMPLICIT_CAST:
        e = e->u.implicit_cast.expr;
        goto tailcall;

    case CTRUMP_EXPR_UNA_PTRREF:
    case CTRUMP_EXPR_UNA_POS:
    case CTRUMP_EXPR_UNA_NEG:
    case CTRUMP_EXPR_UNA_ADDR:
    case CTRUMP_EXPR_UNA_PRE_INC:
    case CTRUMP_EXPR_UNA_POST_INC:
    case CTRUMP_EXPR_UNA_PRE_DEC:
    case CTRUMP_EXPR_UNA_POST_DEC:
    case CTRUMP_EXPR_UNA_BCMPL:
    case CTRUMP_EXPR_UNA_LNEG:
        e = e->u.unary.expr;
        goto tailcall;

    case CTRUMP_EXPR_PAREN:
        e = e->u.paren.expr;
        goto tailcall;

    case CTRUMP_CASE_CONSTANT_TERM:
    case CTRUMP_EXPR_EMPTY:
        break;

    case CTRUMP_CASE_BIN_EQ_EXPR:
    case CTRUMP_CASE_BIN_ARITH_EXPR:
    case CTRUMP_EXPR_BIN_ASSIGN:
    case CTRUMP_CASE_BIN_OP_ASSIGN_EXPR:
    case CTRUMP_EXPR_BIN_COMMA:
        bin = &e->u.binary;
        assign_var_info_expr(info, info_map, bin->lhs, num_bb, tmp_alloc);
        e = bin->rhs;
        goto tailcall;

    case CTRUMP_EXPR_ARRREF:
        assign_var_info_expr(info, info_map, e->u.arr_ref.array, num_bb, tmp_alloc);
        e = e->u.arr_ref.subscript;
        goto tailcall;

    case CTRUMP_CASE_BIN_LOG_EXPR:
        /* rhs of logical expr exsits in other bb */
        bin = &e->u.binary;
        e = bin->lhs;
        goto tailcall;

    case CTRUMP_EXPR_CONDITIONAL:
        /* `then' and `else' expr exists in other bb */
        e = e->u.cond.cond;
        goto tailcall;

    case CTRUMP_EXPR_CALL:
        n = e->u.call.num_args;
        for (i=0; i<n; i++) {
            assign_var_info_expr(info, info_map, &e->u.call.args[i],
                                 num_bb, tmp_alloc);
        }
        e = e->u.call.func_expr;
        goto tailcall;

    case CTRUMP_EXPR_MEMBER_REF:
    case CTRUMP_EXPR_PTR_MEMBER_REF:
        e = e->u.member_ref.obj_expr;
        goto tailcall;

    case CTRUMP_EXPR_INITIALIZER:
        ctrump_fixme("assign var info");
        break;

    case CTRUMP_EXPR_MACRO_EXPAND:
    case CTRUMP_EXPR_TEXT:
    case CTRUMP_EXPR_IVTMP:
        ctrump_unreachable("invalid expr code");
    }
}

static void assign_var_info_initializer(struct ctrump_varray *var_info_vec,
                                        struct ctrump_intmap *var_info_map,
                                        struct ctrump_initializer *initializer,
                                        int num_bb, 
                                        struct ctrump_mempool *tmp_alloc);

static void
assign_var_info_initializer_list(struct ctrump_varray *var_info_vec,
                                 struct ctrump_intmap *var_info_map,
                                 struct ctrump_initializer_list *inits,
                                 int num_bb, struct ctrump_mempool *tmp_alloc)
{
    int i, j, n, m;
    
    n = inits->num_elem;
    for (i=0; i<n; i++) {
        struct ctrump_initializer_list_elem *e = &inits->elems[i];

        m = e->num_designator;

        for (j=0; j<m; j++) {
            struct ctrump_designator *d = &e->designators_list[j];
            if (d->code == CTRUMP_DESIGNATOR_INDEX) {
                assign_var_info_expr(var_info_vec, var_info_map,
                                     d->u.index.index, num_bb, tmp_alloc);
            }
        }

        assign_var_info_initializer(var_info_vec, var_info_map,
                                    &e->initializer, num_bb, tmp_alloc);
    }
}

static void
assign_var_info_initializer(struct ctrump_varray *var_info_vec,
                            struct ctrump_intmap *var_info_map,
                            struct ctrump_initializer *initializer,
                            int num_bb, 
                            struct ctrump_mempool *tmp_alloc)
{
    switch (initializer->code) {
    case CTRUMP_INITIALIZER_EXPR:
        assign_var_info_expr(var_info_vec, var_info_map,
                             initializer->u.expr, num_bb, tmp_alloc);
        break;

    case CTRUMP_INITIALIZER_NESTED:
        assign_var_info_initializer_list(var_info_vec, var_info_map,
                                         initializer->u.nest, num_bb, tmp_alloc);
        break;

    case CTRUMP_INITIALIZER_EMPTY:
        break;
    }
}

static int
assign_var_info(struct partial_bb **bb_vec,
                int num_bb,
                struct ctrump_varray *var_info_vec, /* var info id -> var info */
                struct ctrump_intmap *var_info_map, /* tree var id -> var info id */
                struct ctrump_mempool *tmp_alloc)
{
    int i;
    for (i=0; i<num_bb; i++) {
        struct partial_bb *bb = bb_vec[i];
        int j;
        int n = bb->exprs.nelem;
        struct partial_bb_expr *exprs = bb->exprs.elements;
        for (j=0; j<n; j++) {
            switch (exprs[j].code) {
            case BB_EXPR:
                assign_var_info_expr(var_info_vec, var_info_map,
                                     exprs[j].u.expr, num_bb, tmp_alloc);
                break;
            }
        }
    }

    return var_info_vec->nelem;
}

static void
calc_df(struct partial_bb **dfs_order,
        int num_bb,
        struct ctrump_intmap *varinfo_map,
        int num_var_info,
        ctrump_bitmap_t tmp_bitmap)
{
    int i,j;
    int changed = 1;

    for (i=0; i<num_bb; i++) {
        struct partial_bb *bb = dfs_order[i];
        ctrump_bitmap_copy(bb->live, bb->use, num_var_info);
    }

    while (changed) {
        changed = 0;

        for (i=0; i<num_bb; i++) {
            struct partial_bb *bb = dfs_order[i];
            int np = bb->succs.nelem;
            struct partial_bb **pb = bb->succs.elements;
            ctrump_bitmap_t live = bb->live;

            ctrump_bitmap_copy(tmp_bitmap, bb->live, num_var_info);

            for (j=0; j<np; j++) {
                /* live = live | pb->use | (pb->readh & ~pb->kill) */
                ctrump_bitmap_nand_or(live, pb[j]->live, pb[j]->kill, live, num_var_info);
                ctrump_bitmap_or(live, live, pb[j]->use, num_var_info);
            }

            if (ctrump_bitmap_eq(live, tmp_bitmap, num_var_info) == 0) {
                changed = 1;
            }
        }
    }
}

static void
resolve_bb_vec(struct ctrump_bb **bb_vec,
               struct ctrump_varray *partial_vec,
               struct ctrump_bb **basic_blocks)
{
    int n = partial_vec->nelem, i;
    struct partial_bb *target;

    for (i=0; i<n; i++) {
        target = VA_ELEM(struct partial_bb*, partial_vec, i);
        bb_vec[i] = basic_blocks[target->id];
    }
}

static int
build_cfg(struct ctrump_cfg *ret,
          struct ctrump_intmap *var_info_map,
          struct ctrump_mempool *cfg_pool,
          struct ctrump_mempool *varmap_pool,
          const struct ctrump_compound_stmt *stmts,
          struct build_cfg_env *env)
{
    struct partial_bb *start, *end, *bb;
    struct flow_env flow;
    int i, num_bb, num_create_bb, r, num_var_info;
    struct ctrump_bb **basic_blocks;
    ctrump_bitmap_t bb_bitmap;
    struct ctrump_varray var_set;
    ctrump_bitmap_t tmp_bmp;
    struct ctrump_cfg_var_info *vi;
    struct partial_var_info *pvi;
    struct ctrump_intmap tmp_var_map;
    struct ctrump_intmap_iterator iter;
    struct ctrump_intmap_bucket *b;
    struct ctrump_varray pdg_node_list;

    start = new_bb(env, NULL);
    end = new_bb(env, NULL);

    flow.return_to = end;
    flow.break_to = NULL;
    flow.continue_to = NULL;
    flow.loop_cfg = NULL;

    bb = start;
    r = build_cfg_compound(stmts, env, &flow, &bb, NULL);
    if (r < 0)
        return r;

    /* reach to last */
    if (bb != end) {
        append_succs_maybe(bb, end, env);
    }

    num_create_bb = env->bb_id;

    bb_bitmap = zero_bmp(num_create_bb, &env->tmp_alloc);

    /* create dfs tree */
    num_bb = dfs_order(start, env, num_create_bb, bb_bitmap);

    /* build dominator tree */
    build_dom(env, num_bb);

    /* find dominance frontier */
    find_df(env, num_bb);

    basic_blocks = ctrump_mempool_alloc(env->cfg_pool, sizeof(struct ctrump_bb*)*num_bb);

    ctrump_varray_init_pool(&var_set, 16, sizeof(struct partial_var_info), &env->tmp_alloc);

    ctrump_intmap_init_pool(&tmp_var_map, 45, &env->tmp_alloc);
    num_var_info = assign_var_info((struct partial_bb**)env->basic_blocks.elements,
                                   env->basic_blocks.nelem,
                                   &var_set,
                                   &tmp_var_map,
                                   &env->tmp_alloc);
    ctrump_intmap_resize_pool(var_info_map, &tmp_var_map, varmap_pool);

    vi = ctrump_mempool_alloc(env->cfg_pool, sizeof(struct ctrump_cfg_var_info)*num_var_info);
    pvi = var_set.elements;
    for (i=0; i<num_var_info; i++) {
        vi[i] = pvi[i].result;
    }
    ret->var_info = vi;
    ret->num_var = num_var_info;

    /* update pointer (index -> pointer to partial_var_info) */
    ctrump_intmap_iterator_begin(&iter, var_info_map);
    while (ctrump_intmap_iterator_next(&b, &iter, var_info_map)) {
        int map_val = (intptr_t)b->val;
        b->val = &pvi[map_val];
        pvi[map_val].map_val = map_val;
    }

    for (i=0; i<num_bb; i++) {
        struct partial_bb *pb = VA_ELEM(struct partial_bb*, &env->basic_blocks, i);
        pb->use = zero_bmp(num_var_info, env->cfg_pool);
        pb->kill = zero_bmp(num_var_info, env->cfg_pool);
        pb->live = zero_bmp(num_var_info, env->cfg_pool);
        pb->phi_inserted = zero_bmp(num_var_info, &env->tmp_alloc);
    }

    for (i=0; i<num_bb; i++) {
        struct partial_bb *pb = VA_ELEM(struct partial_bb*, &env->basic_blocks, i);
        int r = extract_load_store(pb, var_info_map, env->error, cfg_pool, &env->tmp_alloc);
        if (r < 0) {
            return r;
        }
    }

    tmp_bmp = zero_bmp(num_var_info, &env->tmp_alloc);

    /* calc data flow */
    calc_df(env->dfs_order, num_bb,
            var_info_map, num_var_info, tmp_bmp);

    /* insert phi nodes */
    env->next_id = insert_phi(env->dfs_order, num_bb,
                              var_set.elements, num_var_info, env->next_id, tmp_bmp, env->cfg_pool);

    ctrump_varray_init(&pdg_node_list, 16, sizeof(struct ctrump_pdg_node*));
    env->next_id = assign_pdg_node(&pdg_node_list, start, var_set.elements,
                                   num_var_info, env->next_id, env->cfg_pool);
    ctrump_varray_discard(&pdg_node_list);

    /* convert partial_bb to ctrump_bb */
    for (i=0; i<num_bb; i++) {
        struct partial_bb *pb = VA_ELEM(struct partial_bb*, &env->basic_blocks, i);
        struct ctrump_bb *b = ctrump_mempool_alloc(env->cfg_pool, sizeof(*b));
        struct ctrump_phi_node *phis;

        int j, n;

#define ALLOC_BB_VEC(aname, numname, vaname)                            \
        b->aname = ctrump_mempool_alloc(env->cfg_pool, sizeof(struct ctrump_bb*)*pb->vaname.nelem); \
        b->numname = pb->vaname.nelem;

        ALLOC_BB_VEC(succs, num_succs, succs);
        ALLOC_BB_VEC(preds, num_preds, preds);
        ALLOC_BB_VEC(dom_children, num_dom_children, children);
        ALLOC_BB_VEC(dfs, num_dfs, dfs);

#define COPY_VEC(aname, numname, vaname)                                \
        b->aname = ctrump_varray_copy(&pb->vaname, env->cfg_pool);      \
        b->numname = pb->vaname.nelem;

        COPY_VEC(load_store.refs, load_store.num_ref, refs);
        COPY_VEC(load_store.stores, load_store.num_store, stores);
        COPY_VEC(load_store.mem_loads, load_store.num_mem_load, arr_loads);
        COPY_VEC(load_store.mem_stores, load_store.num_mem_store, arr_stores);
        COPY_VEC(load_store.ordered_load_store, load_store.num_memop, ordered_mem_load_store);

        b->exprs = ctrump_mempool_alloc(env->cfg_pool, sizeof(struct ctrump_expr*)*pb->exprs.nelem);
        b->num_exprs = pb->exprs.nelem;

        for (j=0; j<pb->exprs.nelem; j++) {
            struct partial_bb_expr *pbe = &((struct partial_bb_expr*)pb->exprs.elements)[j];
            assert(pbe->code == BB_EXPR);
            b->exprs[j] = pbe->u.expr;
        }

        phis = b->phi_nodes = pb->phi_nodes;
        n = b->num_phi = pb->num_phi;

        for (j=0; j<n; j++) {
            phis[j].merge_at = b;
        }

        b->id = env->next_id ++;
        b->id_in_cfg = i;
        b->kill = pb->kill;
        b->use = pb->use;
        b->live = pb->live;
        b->num_var = num_var_info;
        b->loop_belong_to = pb->loop_cfg;
        b->flags = pb->flags;

        basic_blocks[i] = b;
    }

    for (i=0; i<num_bb; i++) {
        struct ctrump_bb *b = basic_blocks[i];
        struct partial_bb *pb = VA_ELEM(struct partial_bb*, &env->basic_blocks, i);
        struct pending_chain *pend;

        resolve_bb_vec(b->succs, &pb->succs, basic_blocks);
        resolve_bb_vec(b->preds, &pb->preds, basic_blocks);
        resolve_bb_vec(b->dfs, &pb->dfs, basic_blocks);
        resolve_bb_vec(b->dom_children, &pb->children, basic_blocks);

        /* loop_info is updated at ctrump_analyze_loop
         * if b is loop entrance */
        pb->bb = b;

        pend = pb->resolve_pending;
        while (pend) {
            *pend->resolve_ptr = b;
            pend = pend->chain;
        }
    }

    ret->head = basic_blocks[start->id];
    ret->tail = basic_blocks[end->id];
    ret->num_bb = num_bb;
    ret->basic_blocks = basic_blocks;

    ret->addressed = zero_bmp(num_var_info, env->cfg_pool);
    for (i=0; i<num_var_info; i++) {
        if (vi[i].var->addressed) {
            ctrump_bitmap_set(ret->addressed, i);
        }
    }

    ret->global = zero_bmp(num_var_info, env->cfg_pool);
    for (i=0; i<num_var_info; i++) {
        enum ctrump_stor_class cls = vi[i].var->stor_class;
        (void)cls;
        if (! (cls == CTRUMP_STOR_CLASS_AUTO ||
               cls == CTRUMP_STOR_CLASS_AUTO_UNSPECIFIED ||
               cls == CTRUMP_STOR_CLASS_ARGMENT) ) {
            ctrump_bitmap_set(ret->global, i);
        }
    }

    /* update pointer (index -> pointer to partial_var_info) */
    ctrump_intmap_iterator_begin(&iter, var_info_map);
    while (ctrump_intmap_iterator_next(&b, &iter, var_info_map)) {
        int map_val = ((struct partial_var_info*)b->val)->map_val;
        b->val = &vi[map_val];
    }

    return num_bb ;
}

static int
build_cfg_loop(struct ctrump_stmt *body,
               struct ctrump_expr *exit_cond,
               struct partial_bb *cond_bb_enter,
               struct partial_bb *cond_bb_exit,
               struct partial_bb *return_bb,
               struct partial_bb *continue_bb_enter,
               struct partial_bb *continue_bb_exit,
               struct ctrump_stmt *next_stmt,
               struct ctrump_loop_cfg_info *loop,
               struct build_cfg_env *env,
               struct ctrump_loop_cfg_info *outer_loop,
               struct partial_bb **current_bb_ptr)
{
    struct partial_bb *current_bb = *current_bb_ptr;
    struct partial_bb *loop_body_bb;
    struct partial_bb *break_bb;
    int r;
    struct flow_env flow;

    loop->exit_cond = exit_cond;
    loop->id = env->next_id++;

    break_bb = get_id_bb_maybe(env, next_stmt, outer_loop, return_bb);

    flow.return_to = return_bb;
    flow.break_to = break_bb;
    flow.continue_to = continue_bb_enter;
    flow.loop_cfg = loop;

    loop_body_bb = new_bb(env, loop);
    cond_bb_enter->flags |= CTRUMP_BB_LOOP_ENTRY;
    append_pending(env, cond_bb_enter, &loop->cond_bb);
    append_pending(env, break_bb, &loop->break_bb);
    append_pending(env, loop_body_bb, &loop->body_start_bb);

    /* entrance -> cond
     * cond -> exit
     * cond -> body
     * end of body -> continue (loop end)
     *
     * part of body -> break (by `break')
     * part of body -> continue (by `continue')
     */

    append_succs_maybe(current_bb, cond_bb_enter, env);

    if (current_bb) {
        append_pending(env, current_bb, &loop->loop_pred);
    } else {
        loop->loop_pred = NULL;
    }

    append_succs(cond_bb_exit, loop_body_bb, env);
    append_succs(cond_bb_exit, break_bb, env);

    r = build_cfg_stmt(body, NULL, env, &flow, &loop_body_bb);
    if (r < 0)
        return r;

    /* loop_body_bb has end of body */
    if (loop_body_bb) {
        append_succs(loop_body_bb, continue_bb_enter, env);
    }

    *current_bb_ptr = break_bb;

    return 0;
}
               
static int
build_cfg_for(struct ctrump_loop_cfg_info **loop_ret,
              struct ctrump_expr *cond,
              struct ctrump_expr *iter,
              struct ctrump_stmt *body,
              struct ctrump_stmt *next_stmt,
              struct build_cfg_env *env,
              const struct flow_env *flow_env,
              struct partial_bb **current_bb_ptr)
{
    struct partial_bb *cond_bb_enter, *cond_bb_exit;
    struct partial_bb *continue_bb_enter, *continue_bb_exit;

    struct ctrump_loop_cfg_info *loop = ctrump_mempool_alloc(env->cfg_pool,
                                                             sizeof(*loop));

    *loop_ret = loop;

    cond_bb_exit = cond_bb_enter = new_bb(env, loop);
    continue_bb_exit = continue_bb_enter = new_bb(env, loop);

    build_cfg_expr(cond, body, env, loop, &cond_bb_exit);
    build_cfg_expr(iter, body, env, loop, &continue_bb_exit);
    append_succs(continue_bb_exit, cond_bb_enter, env);

    return build_cfg_loop(body, cond,
                          cond_bb_enter,
                          cond_bb_exit,
                          flow_env->return_to,
                          continue_bb_enter,
                          continue_bb_exit,
                          next_stmt, loop, env,
                          flow_env->loop_cfg, current_bb_ptr);
}

static int
build_cfg_while(struct ctrump_loop_cfg_info **loop_ret,
                struct ctrump_expr *cond,
                struct ctrump_stmt *body,
                struct ctrump_stmt *next_stmt,
                struct build_cfg_env *env,
                const struct flow_env *flow_env,
                struct partial_bb **current_bb_ptr)
{
    struct partial_bb *cond_bb_enter, *cond_bb_exit;
    struct partial_bb *continue_bb;
    struct ctrump_loop_cfg_info *loop = ctrump_mempool_alloc(env->cfg_pool,
                                                             sizeof(*loop));

    *loop_ret = loop;

    cond_bb_enter = cond_bb_exit = new_bb(env, loop);
    continue_bb = cond_bb_enter;

    build_cfg_expr(cond, body, env, loop, &cond_bb_exit);

    return build_cfg_loop(body, cond,
                          cond_bb_enter,
                          cond_bb_exit,
                          flow_env->return_to,
                          continue_bb,
                          continue_bb,
                          next_stmt, loop, env,
                          flow_env->loop_cfg, current_bb_ptr);
}

static int
build_cfg_do_while(struct ctrump_expr *cond,
                   struct ctrump_stmt *body,
                   struct ctrump_stmt *next_stmt,
                   struct build_cfg_env *env,
                   const struct flow_env *flow_env,
                   struct partial_bb **current_bb_ptr)
{
    struct partial_bb *continue_bb;
    struct partial_bb *next_bb;
    struct partial_bb *body_bb, *body_bb_enter;
    struct flow_env flow;
    int r;

    body_bb = body_bb_enter = get_id_bb(env, body, flow_env->loop_cfg);
    next_bb = get_id_bb_maybe(env, next_stmt, flow_env->loop_cfg, flow_env->return_to);

    continue_bb = body_bb;
    flow.return_to = flow_env->return_to;
    flow.break_to = next_bb;
    flow.continue_to = continue_bb;

    append_succs_maybe(*current_bb_ptr, body_bb_enter, env);

    r = build_cfg_stmt(body, next_stmt,
                       env, &flow, &body_bb);
    if (r < 0)
        return r;

    build_cfg_expr_maybe(cond, body, env, flow_env->loop_cfg, &body_bb);
    append_succs_maybe(body_bb, body_bb_enter, env);
    if (next_stmt) {
        append_succs_maybe(body_bb, next_bb, env);
    }

    *current_bb_ptr = body_bb;

    return 0;
}

static void
build_cfg_initializer_list(struct ctrump_initializer_list *list,
                           struct ctrump_stmt *stmt,
                           struct build_cfg_env *env,
                           struct ctrump_loop_cfg_info *cur_loop,
                           struct partial_bb **current_bb_ptr)
{
    int i, j, n, m;
    n = list->num_elem;

    for (i=0; i<n; i++) {
        struct ctrump_initializer_list_elem *e = &list->elems[i];

        m = e->num_designator;
        for (j=0; j<m; j++) {
            struct ctrump_designator *d = &e->designators_list[j];

            switch (d->code) {
            case CTRUMP_DESIGNATOR_INDEX:
                build_cfg_expr_maybe(d->u.index.index,
                                     stmt, env, cur_loop, current_bb_ptr);
                break;

            case CTRUMP_DESIGNATOR_IDENT:
                /* do nothing */
                break;
            }
        }

        build_cfg_initializer(&e->initializer, stmt, env, cur_loop, current_bb_ptr);
    }
}

static void
build_cfg_initializer(struct ctrump_initializer *init,
                      struct ctrump_stmt *stmt,
                      struct build_cfg_env *env,
                      struct ctrump_loop_cfg_info *cur_loop,
                      struct partial_bb **current_bb_ptr)
{
    switch (init->code) {
    case CTRUMP_INITIALIZER_EMPTY:
        break;

    case CTRUMP_INITIALIZER_EXPR:
        build_cfg_expr_maybe(init->u.expr, stmt, env, cur_loop, current_bb_ptr);
        break;

    case CTRUMP_INITIALIZER_NESTED:
        build_cfg_initializer_list(init->u.nest, stmt, env, cur_loop, current_bb_ptr);
        break;
    }
}

static void
build_cfg_decl(struct ctrump_stmt *stmt,
               struct ctrump_decl *decl,
               struct build_cfg_env *env,
               struct ctrump_loop_cfg_info *cur_loop,
               struct partial_bb **current_bb_ptr)
{
    int i, n = decl->num_decls;
    for (i=0; i<n; i++) {
        struct ctrump_decl_with_init *dwi = &decl->decls[i];
        build_cfg_initializer(&dwi->initializer, stmt, env, cur_loop, current_bb_ptr);
    }
}

static int
build_cfg_stmt(struct ctrump_stmt *stmt,
               struct ctrump_stmt *next_stmt, /* NULL if current stmt is last of bb */
               struct build_cfg_env *env,
               const struct flow_env *flow_env,
               struct partial_bb **current_bb_ptr /* *current_bb_ptr is NULL if unreachable */
    )
{
    struct partial_bb *next_bb;
    struct partial_bb *current_bb = *current_bb_ptr;
    struct partial_bb *then_bb, *else_bb;
    int r;

    switch (stmt->code) {
    case CTRUMP_STMT_GOTO: {
        const struct ctrump_goto_stmt *s = &stmt->u.goto_;
        struct label_table *t, *table;
        struct partial_bb *label_bb;
        table = env->label_table;
        HASH_FIND_SYM(table, s->label, t);

        label_bb = get_id_bb(env, t->stmt, flow_env->loop_cfg);
        append_succs_maybe(current_bb, label_bb, env);

        current_bb = NULL;
        break;
    }

    case CTRUMP_STMT_CONTINUE:
        if (flow_env->continue_to == NULL) {
            env->error->code = CTRUMP_BUILD_CFG_ERROR_CONTINUE_IN_NOT_LOOP;
            env->error->stmt = stmt;
            return -1;
        }

        append_succs_maybe(current_bb, flow_env->continue_to, env);
        current_bb = NULL;
        break;

    case CTRUMP_STMT_BREAK:
        if (flow_env->break_to == NULL) {
            env->error->code = CTRUMP_BUILD_CFG_ERROR_BREAK_IN_NOT_LOOP;
            env->error->stmt = stmt;
            return -1;
        }
        append_succs_maybe(current_bb, flow_env->break_to, env);
        current_bb = NULL;
        break;

    case CTRUMP_STMT_RETURN_EXPR:
        build_cfg_expr_maybe(&stmt->u.ret_expr.retval, stmt, env, flow_env->loop_cfg, &current_bb);
        /* fall through */

    case CTRUMP_STMT_RETURN:
        append_succs_maybe(current_bb, flow_env->return_to, env);
        current_bb = NULL;
        break;

    case CTRUMP_STMT_LABELED:
        if (BMP_P(env->label_ref_bmp, stmt->id)) {
            next_bb = get_id_bb(env, stmt->u.labeled.stmt, flow_env->loop_cfg);
            append_succs(current_bb, next_bb, env);
            current_bb = next_bb;
        }

        build_cfg_stmt(stmt->u.labeled.stmt, next_stmt, env, flow_env, &current_bb);
        break;

    case CTRUMP_STMT_COMPOUND:
        r = build_cfg_compound(&stmt->u.compound,
                               env, flow_env, &current_bb, next_stmt);
        if (r < 0)
            return r;
        break;

    case CTRUMP_STMT_IF:
        build_cfg_expr_maybe(&stmt->u.if_.cond, stmt, env, flow_env->loop_cfg, &current_bb);

        if (current_bb) {
            then_bb = get_id_bb(env, stmt->u.if_.body, flow_env->loop_cfg);
            append_succs(current_bb, then_bb, env);
        } else {
            then_bb = NULL;
        }
        build_cfg_stmt(stmt->u.if_.body, NULL,
                       env, flow_env, &then_bb);

        if (current_bb) {
            next_bb = get_id_bb_maybe(env, next_stmt, flow_env->loop_cfg, flow_env->return_to);
            append_succs_maybe(then_bb, next_bb, env);
            append_succs(current_bb, next_bb, env);
            current_bb = next_bb;
        } else if (then_bb) {
            current_bb = then_bb;
        } else {
            /* unreachable bb */
            current_bb = NULL;
        }
        break;

    case CTRUMP_STMT_IF_ELSE:
        build_cfg_expr_maybe(&stmt->u.if_else.cond, stmt, env, flow_env->loop_cfg, &current_bb);

        if (current_bb) {
            then_bb = get_id_bb(env, stmt->u.if_else.then_body, flow_env->loop_cfg);
            else_bb = get_id_bb(env, stmt->u.if_else.else_body, flow_env->loop_cfg);
            append_succs(current_bb, then_bb, env);
            append_succs(current_bb, else_bb, env);
        } else {
            then_bb = NULL;
            else_bb = NULL;
        }

        build_cfg_stmt(stmt->u.if_else.then_body, NULL,
                       env, flow_env, &then_bb);
        build_cfg_stmt(stmt->u.if_else.else_body, NULL,
                       env, flow_env, &else_bb);

        if (then_bb && else_bb) {
            next_bb = get_id_bb_maybe(env, next_stmt, flow_env->loop_cfg, flow_env->return_to);
            append_succs(then_bb, next_bb, env);
            append_succs(else_bb, next_bb, env);

            current_bb = next_bb;
        } else if (then_bb) {
            current_bb = then_bb;
        } else if (else_bb) {
            current_bb = else_bb;
        } else {
            /* unreachable bb */
            current_bb = NULL;
        }
        break;

    case CTRUMP_STMT_EXPR:
        build_cfg_expr_maybe(&stmt->u.expr.expr, stmt, env,  flow_env->loop_cfg, &current_bb);
        break;

    case CTRUMP_STMT_FOR:
        build_cfg_expr_maybe(&stmt->u.for_.init, stmt, env, flow_env->loop_cfg, &current_bb);
        r = build_cfg_for(&stmt->u.for_.loop_cfg,
                          &stmt->u.for_.cond,
                          &stmt->u.for_.iter,
                          stmt->u.for_.body,
                          next_stmt, env, flow_env, &current_bb);
        stmt->u.for_.loop_cfg->loop_stmt = stmt;
        if (r < 0)
            return r;
        break;

    case CTRUMP_STMT_WHILE:
        r = build_cfg_while(&stmt->u.while_.loop_cfg,
                            &stmt->u.while_.cond,
                            stmt->u.while_.body,
                            next_stmt, env, flow_env, &current_bb);
        stmt->u.while_.loop_cfg->loop_stmt = stmt;
        if (r < 0)
            return r;
        break;

    case CTRUMP_STMT_DO_WHILE:
        r = build_cfg_do_while(&stmt->u.do_while.cond,
                               stmt->u.do_while.body,
                               next_stmt, env, flow_env, &current_bb);
        if (r < 0)
            return r;
        break;

    case CTRUMP_STMT_DECL:
        build_cfg_decl(stmt, &stmt->u.decl, env, flow_env->loop_cfg, &current_bb);
        break;

    case CTRUMP_STMT_FOR_DECL:
        build_cfg_decl(stmt, &stmt->u.for_decl.init, env, flow_env->loop_cfg, &current_bb);
        r = build_cfg_for(&stmt->u.for_decl.loop_cfg,
                          &stmt->u.for_decl.cond,
                          &stmt->u.for_decl.iter,
                          stmt->u.for_decl.body,
                          next_stmt, env, flow_env, &current_bb);
        stmt->u.for_decl.loop_cfg->loop_stmt = stmt;
        if (r < 0)
            return r;
        break;

    case CTRUMP_STMT_CASE:      /* todo: switch case */
    case CTRUMP_STMT_DEFAULT:
    case CTRUMP_STMT_SWITCH:
        ctrump_fixme("control flow");
        break;

    case CTRUMP_STMT_PRAGMA:
    case CTRUMP_STMT_SLASLA_COMMENT:
    case CTRUMP_STMT_SLAAST_COMMENT:
    case CTRUMP_STMT_IFDEF:
    case CTRUMP_STMT_ASM:
    case CTRUMP_STMT_DEFINE:
    case CTRUMP_STMT_UNDEF:
    case CTRUMP_STMT_EMPTY:
    case CTRUMP_STMT_NEWLINE:
        /* do nothing */
        break;

    case CTRUMP_STMT_LIST:
        ctrump_unreachable("stmt list");
        break;
    }

    *current_bb_ptr = current_bb;
    return 0;
}

int
ctrump_build_cfg(struct ctrump_cfg *ret,
                 struct ctrump_intmap *var_info_map,
                 struct ctrump_build_cfg_error *error,
                 const struct ctrump_fundef *def,
                 struct ctrump_mempool *cfg_pool,
                 struct ctrump_mempool *varmap_pool,
                 int num_ast,
                 int id_begin)
{
    struct build_cfg_env env;
    int r, i, num_bb;

    ctrump_mempool_init(&env.tmp_alloc, 1024);

    env.label_ref_bmp = zero_bmp(num_ast, &env.tmp_alloc);
    env.stmt_bb_table = ctrump_mempool_alloc(&env.tmp_alloc, num_ast * sizeof(struct ctrump_bb*));
    env.next_id = id_begin;
    env.bb_id = 0;
    env.error = error;
    env.cfg_pool = cfg_pool;

    ctrump_varray_init_pool(&env.basic_blocks, 16, sizeof(struct partial_bb*), &env.tmp_alloc);

    for (i=0; i<num_ast; i++) {
        env.stmt_bb_table[i] = NULL;
    }

    r = check_label_use(&env, &def->body);
    if (r < 0) 
        goto quit;

    num_bb = build_cfg(ret, var_info_map, cfg_pool, varmap_pool, &def->body, &env);
    delete_table(env.label_table);
    if (num_bb < 0) {
        r = -1;
        goto quit;
    }

    r = env.next_id;

quit:
    ctrump_mempool_destroy(&env.tmp_alloc);

    return r;
}

---