ctrump/analyzer/loop.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/loop.h"
#include "ctrump/analyzer/peel.h"
#include "ctrump/analyzer/deptest.h"
#include "ctrump/common/intmap.h"
#include "ctrump/common/varray.h"
#include "ctrump/common/queue.h"
#include "ctrump/common/mempool.h"
#include "ctrump/common/bitmap.h"
#include "ctrump/common/abort.h"
#include "ctrump/ast/ast.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>

#define zero_bmp ctrump_bmp_zero
#define fill_bmp ctrump_bmp_fill

enum loop_cfg_node_code {
    LOOP_CFG_NODE_INNER_LOOP,   
    LOOP_CFG_NODE_BB            
};

struct loop_cfg_node {
    enum loop_cfg_node_code code;
    union {
        struct ctrump_loop_info_node *loop;
        struct ctrump_bb *bb;
    } u;
};

static void
find_invariant(struct ctrump_cfg *cfg,
               ctrump_bitmap_t invariant,
               ctrump_bitmap_t use,
               ctrump_bitmap_t modify)
{
    int num_var = cfg->num_var;

    /* invariant = used & not modify */
    ctrump_bitmap_nand(invariant, use, modify, num_var);

    /* addressed variable or global variable.
     * invariant should not be addressed and not be global */
    /* ctrump_bitmap_nand(invariant, invariant, cfg->global, num_var); */
    /* ctrump_bitmap_nand(invariant, invariant, cfg->addressed, num_var); */
}

struct iv_info {
    struct ctrump_pdg_node *reach_at_loop_entry; 
    int incr;                                    
};

static int
recog_inductive(struct iv_info *recog,
                struct ctrump_pdg_node *pdg)
{
    int add_val;
    int is_const;

    switch (pdg->code) {
    case CTRUMP_PDG_VALUE_REDUCTION:
        if (pdg->u.reduction.op == CTRUMP_REDUCTIVE_ADD) {
            add_val = ctrump_ast_fold_const_sint(pdg->u.reduction.value, &is_const);
            if (is_const) {
                recog->incr += add_val;
                return 1;
            }
        }
        return 0;

    case CTRUMP_PDG_VALUE_INCREMENTAL:
        if (pdg->u.incr.op == CTRUMP_PDG_INC) {
            recog->incr++;
            return 1;
        }
        return 0;

    default:
        break;
    }

    return 0;
}

static void
find_loop_carry_dependency(ctrump_bitmap_t modified_and_live_after_loop,
                           ctrump_bitmap_t loop_carry_dep,
                           struct ctrump_bb *cond_bb,
                           struct ctrump_bb *next_bb,
                           int num_bb,
                           ctrump_bitmap_t used,
                           ctrump_bitmap_t modify,
                           ctrump_bitmap_t inductive,
                           int num_var)
{
    /* updated in loop and live after loop */
    /* (live & ~kill) | use*/
    ctrump_bitmap_nand_or(modified_and_live_after_loop,
                          next_bb->live, next_bb->kill,
                          next_bb->use, num_var);
    ctrump_bitmap_and(modified_and_live_after_loop,
                      modified_and_live_after_loop, modify, num_var);

    /* live at end of cond_bb */
    ctrump_bitmap_nand_or(loop_carry_dep,
                          next_bb->live,
                          next_bb->kill,
                          next_bb->use,
                          num_var);

    /* live in top of loop
     *  = ((live at end of cond_bb) & ~cond_bb->kill) | cond_bb->use
     */
    ctrump_bitmap_nand_or(loop_carry_dep,
                          loop_carry_dep,
                          cond_bb->kill,
                          cond_bb->use,
                          num_var);

    /* live in top of loop and modified */
    ctrump_bitmap_and(loop_carry_dep, loop_carry_dep, modify, num_var);
    ctrump_bitmap_nand(loop_carry_dep, loop_carry_dep, inductive, num_var);
}

static void
find_iv(ctrump_bitmap_t inductive,
        struct loop_cfg_node *bbs,
        struct ctrump_loop_cfg_info *loop_cfg,
        ctrump_bitmap_t is_conditional_bb,
        int num_bb,
        int num_var,
        struct iv_info *iv_recogs,
        struct ctrump_intmap *var_info_map)
{
    int i, j, n;
    int pred_loop_index;
    struct ctrump_bb *cond_bb = loop_cfg->cond_bb;
    struct ctrump_bb *loop_pred = loop_cfg->loop_pred;

    assert(loop_pred);

    n = cond_bb->num_preds;
    /* find pred */
    for (i=0; i<n; i++) {
        if (cond_bb->preds[i] == loop_pred)
            break;
    }

    assert(i < n);
    pred_loop_index = i;

    /* candidate of inductives are variables that is updated and used in this loop.
     * So, inductives are updated by phi-node at loop entry
     */
    n = cond_bb->num_phi;
    for (i=0; i<n; i++) {
        struct ctrump_phi_node *p = &cond_bb->phi_nodes[i];
        int var_idx = p->var_index;
        struct ctrump_pdg_node *reach_at_loop_entry = p->nodes[pred_loop_index];
        struct iv_info *iv = &iv_recogs[var_idx];

        iv->reach_at_loop_entry = reach_at_loop_entry;
        ctrump_bitmap_set(inductive, var_idx);
    }

    /* bb is always processed when bb's dominance frontier is cond_bb. */
    for (i=0; i<num_bb; i++) {
        struct loop_cfg_node *node = &bbs[i];

        switch (node->code) {
        case LOOP_CFG_NODE_INNER_LOOP:
            /* variables are updated in inner-loop is not inductive */
            ctrump_bitmap_nand(inductive, inductive, node->u.loop->modify, num_var);
            break;

        case LOOP_CFG_NODE_BB:
            if (ctrump_bitmap_p(is_conditional_bb, i)) {
                /* variable that is modified in conditional is not inductive */
                ctrump_bitmap_nand(inductive, inductive, node->u.bb->kill, num_var);
            }
        }
    }

    /* bb is always processed when bb's dominance frontier is cond_bb. */
    for (i=0; i<num_bb; i++) {
        struct loop_cfg_node *node = &bbs[i];

        switch (node->code) {
        case LOOP_CFG_NODE_INNER_LOOP:
            /* do nothing */
            break;

        case LOOP_CFG_NODE_BB:
            if (! ctrump_bitmap_p(is_conditional_bb, i)) {
                struct ctrump_bb *bb = node->u.bb;
                struct ctrump_var_store *stores = bb->load_store.stores;
                int num_st = bb->load_store.num_store;
                for (j=0; j<num_st; j++) {
                    struct ctrump_var *v = stores[j].var;
                    struct ctrump_cfg_var_info *vi;
                    struct ctrump_pdg_node *pdg = stores[j].new_val;
                    struct iv_info *recog;
                    int found, index;

                    vi = ctrump_intmap_lookup(var_info_map, &found, v->id);
                    index = vi->index;
                    recog = &iv_recogs[index];

                    if (ctrump_bitmap_p(inductive, index)) {
                        if (! recog_inductive(recog, pdg)) {
                            ctrump_bitmap_clear(inductive,index);
                        }
                    }
                }
            }
        }
    }
}


enum parallel_access_type {
    LOAD,                   /* load */
    STORE,                  /* store */
};

#define PARALLEL_ACCESS_PARTIAL (1<<0)
#define PARALLEL_ACCESS_OP_ASSIGN (1<<1)
#define PARALLEL_ACCESS_INCPTR (1<<2) /* *a++ = x */
#define PARALLEL_ACCESS_INVARIANT_PTR (1<<3) /* *a = x */

struct parallel_access_info {
    enum parallel_access_type type; 
    int flags;                  
    struct ctrump_var *invariant; 
    int num_subscript;          
    struct ctrump_loop_subscript *subscripts; 
    int num_constraint;                       
    struct ctrump_loop_subscript_constraint *constraints; 
    struct ctrump_stmt *at_stmt;                          
    struct ctrump_expr *at_expr;                          
};


static struct parallel_access_info *
append_access_info(struct ctrump_varray *access_info,
                   struct ctrump_var *invariant_var,
                   int num_subscript,
                   struct ctrump_loop_subscript *subscripts,
                   int num_constraint,
                   struct ctrump_loop_subscript_constraint *constraints,
                   enum parallel_access_type type,
                   int flags,
                   struct ctrump_stmt *at_stmt,
                   struct ctrump_expr *at_expr,
                   struct ctrump_mempool *alloc)
{
    struct parallel_access_info *ai = access_info->elements;

    VA_NEWELEM_P(access_info, alloc);
    ai = VA_LAST_PTR(struct parallel_access_info, access_info);

    ai->invariant = invariant_var;
    ai->num_subscript = num_subscript;
    ai->subscripts = subscripts;
    ai->num_constraint = num_constraint;
    ai->constraints = constraints;
    ai->type = type;
    ai->at_stmt = at_stmt;
    ai->at_expr = at_expr;
    ai->flags = flags;

    return NULL;
}

static int
check_var_bmp_p(struct ctrump_var *var,
                ctrump_bitmap_t bmp,
                struct ctrump_intmap *var_info_map)
{
    struct ctrump_cfg_var_info *vi;
    int found, index;
    vi = ctrump_intmap_lookup(var_info_map, &found, var->id);
    index = vi->index;
    return ctrump_bitmap_p(bmp, index);
}

#define MAX(a,b) (((a)>(b))?(a):(b))

static void
parallel_store(struct ctrump_varray *access_info,
               struct ctrump_var *invariant_var,
               int num_subscript,
               struct ctrump_loop_subscript *subscripts,
               int num_constraint,
               struct ctrump_loop_subscript_constraint *constraints,
               int flags,
               struct ctrump_stmt *at_stmt,
               struct ctrump_expr *at_expr,
               struct ctrump_mempool *tmp_alloc)
{
    if ((flags & PARALLEL_ACCESS_PARTIAL) ||
        (flags & PARALLEL_ACCESS_OP_ASSIGN)) {
        append_access_info(access_info, invariant_var,
                           num_subscript, subscripts,
                           num_constraint, constraints,
                           LOAD, flags, at_stmt, at_expr, tmp_alloc);
    }

    append_access_info(access_info, invariant_var,
                       num_subscript, subscripts,
                       num_constraint, constraints,
                       STORE, flags, at_stmt, at_expr, tmp_alloc);
}                
static void
parallel_load(struct ctrump_varray *access_info,
              struct ctrump_var *invariant_var,
              int num_subscript,
              struct ctrump_loop_subscript *subscripts,
              int num_constraint,
              struct ctrump_loop_subscript_constraint *constraints,
              int flags,
              struct ctrump_stmt *at_stmt,
              struct ctrump_expr *at_expr,
              struct ctrump_mempool *tmp_alloc)
{
    append_access_info(access_info, invariant_var,
                       num_subscript, subscripts,
                       num_constraint, constraints,
                       LOAD, flags, at_stmt, at_expr, tmp_alloc);
}

static void
append_random_access_array(struct ctrump_varray *access,
                           struct ctrump_expr *array,
                           int num_subscript,
                           struct ctrump_subscript *subscripts,
                           struct ctrump_stmt *at_stmt,
                           struct ctrump_expr *at_expr,
                           enum ctrump_random_access_code code,
                           struct ctrump_mempool *alloc)
{
    struct ctrump_random_access *a;
    VA_NEWELEM_P(access, alloc);
    a = VA_LAST_PTR(struct ctrump_random_access, access);

    a->code = code;
    a->access_at_stmt = at_stmt;
    a->access_at_expr = at_expr;
    a->u.arr_not_invariant.array = array;
    a->u.arr_not_invariant.num_subscript = num_subscript;
    a->u.arr_not_invariant.subscripts = subscripts;
}

#define append_array_not_invariant(a,arr,ns,ss,ats,ate,alloc)           \
    append_random_access_array(a,arr,ns,ss,ats,ate,CTRUMP_RANDOM_ACCESS_ARRAY_NOT_INVARIANT,alloc)
#define append_subscript_not_inductive(a,arr,ns,ss,ats,ate,alloc)       \
    append_random_access_array(a,arr,ns,ss,ats,ate,CTRUMP_RANDOM_ACCESS_SUBSCRIPT_NOT_INDUCTIVE,alloc)
#define append_complicated_array(a,arr,ns,ss,ats,ate,alloc)             \
    append_random_access_array(a,arr,ns,ss,ats,ate,CTRUMP_RANDOM_ACCESS_COMPLICATED_ARRAY,alloc)

static void
append_complicated_subscript(struct ctrump_varray *access,
                             struct ctrump_expr *subscript_expr,
                             struct ctrump_stmt *at_stmt,
                             struct ctrump_expr *at_expr,
                             struct ctrump_mempool *alloc)
{
    struct ctrump_random_access *a;
    VA_NEWELEM_P(access, alloc);
    a = VA_LAST_PTR(struct ctrump_random_access, access);

    a->code = CTRUMP_RANDOM_ACCESS_COMPLICATED_SUBSCRIPT;
    a->access_at_stmt = at_stmt;
    a->access_at_expr = at_expr;

    a->u.complicated_subscript = subscript_expr;
}

static void
append_index_var_not_inductive(struct ctrump_varray *access,
                               struct ctrump_var *var,
                               struct ctrump_stmt *at_stmt,
                               struct ctrump_expr *at_expr,
                               struct ctrump_mempool *alloc)
{
    struct ctrump_random_access *a;
    VA_NEWELEM_P(access, alloc);
    a = VA_LAST_PTR(struct ctrump_random_access, access);

    a->code = CTRUMP_RANDOM_ACCESS_INDEX_VAR_NOT_INDUCTIVE;
    a->access_at_stmt = at_stmt;
    a->access_at_expr = at_expr;

    a->u.index_var_not_inductive = var;
}


static void
append_multiple_scaled_index(struct ctrump_varray *access,
                             struct ctrump_expr *index0,
                             struct ctrump_expr *index1,
                             struct ctrump_stmt *at_stmt,
                             struct ctrump_expr *at_expr,
                             struct ctrump_mempool *alloc)
{
    struct ctrump_random_access *a;
    VA_NEWELEM_P(access, alloc);
    a = VA_LAST_PTR(struct ctrump_random_access, access);

    a->code = CTRUMP_RANDOM_ACCESS_MULTIPLE_SCALED_INDEX;
    a->access_at_stmt = at_stmt;
    a->access_at_expr = at_expr;

    a->u.multiple_scaled_index.index0 = index0;
    a->u.multiple_scaled_index.index1 = index1;
}


static int
analyze_subscript_coef(struct ctrump_expr *e,
                       struct ctrump_expr **next_level_index_expr,
                       struct ctrump_var **coef_var,
                       ctrump_bitmap_t invariant,
                       struct ctrump_intmap *var_info_map)
{
    /* invariant * (iv) => subscript
     * invariant * invariant => not subscript
     * invariant + a => not subscript */

    if (e->code == CTRUMP_EXPR_BIN_MUL) {
        struct ctrump_expr *lhs = e->u.binary.lhs, *rhs = e->u.binary.rhs;
        struct ctrump_var *v;
        struct ctrump_cfg_var_info *vi;
        int found;
        lhs = ctrump_peel_paren(lhs);
        rhs = ctrump_peel_paren(rhs);
        if (lhs->code == CTRUMP_EXPR_VARREF) {
            v = lhs->u.varref.var;
            vi = ctrump_intmap_lookup(var_info_map, &found, v->id);
            assert(found);

            if (ctrump_bitmap_p(invariant, vi->index)) {
                *next_level_index_expr = rhs;
                *coef_var = v;
                return 1;
            }
        }

        if (rhs->code == CTRUMP_EXPR_VARREF) {
            v = rhs->u.varref.var;
            vi = ctrump_intmap_lookup(var_info_map, &found, v->id);
            assert(found);

            if (ctrump_bitmap_p(invariant, vi->index)) {
                *next_level_index_expr = lhs;
                *coef_var = v;
                return 1;
            }
        }
    }

    return 0;
}

struct add_stack_elem {
    int is_sign;                
    struct ctrump_expr *e;      
};

static int 
single_expr_subscripts_to_loop_subscript(struct ctrump_varray *random_access, /* struct ctrump_random_access */
                                         struct ctrump_varray *indices, /* struct ctrump_loop_index */
                                         int *constant_offset,
                                         struct ctrump_expr *subscript_expr,
                                         struct ctrump_expr **next_level_index_ret,
                                         struct ctrump_var **coef_var,
                                         struct iv_info **iv_level,
                                         ctrump_bitmap_t invariant,
                                         ctrump_bitmap_t *inductive_bmp,
                                         struct ctrump_intmap *var_info_map,
                                         int loop_level,
                                         struct ctrump_stmt *at_stmt,
                                         struct ctrump_expr *at_expr,
                                         struct ctrump_mempool *tmp_alloc)
{
    int offset_sum = 0;
    struct ctrump_expr *next_level_index = NULL;

    struct ctrump_varray add_stack;
    struct add_stack_elem ae;
    ctrump_varray_init(&add_stack, 4, sizeof(struct add_stack_elem));

    ae.e = subscript_expr;
    ae.is_sign = 0;
    VA_PUSH(struct add_stack_elem, &add_stack, ae);

    *next_level_index_ret = NULL;

    /* loop for each index
     * a[i + j + k] : each {i,j,k}
     */
    while (add_stack.nelem) {
        int j, r;
        struct ctrump_var *var;
        struct ctrump_cfg_var_info *vi;
        int off, incr = 0, found, index;
        struct ctrump_expr *index_expr;
        struct ctrump_loop_index *loop_index;
        int is_sign;

        ae = VA_POP(struct add_stack_elem, &add_stack);

        subscript_expr = ctrump_peel_paren(ae.e);
        is_sign = ae.is_sign;

        ctrump_ast_fold_const_offset_sint(&off, &index_expr, subscript_expr);

        offset_sum += off;

        if (! index_expr)
            continue;

        index_expr = ctrump_peel_paren(index_expr);

        if (index_expr->code == CTRUMP_EXPR_BIN_ADD ||
            index_expr->code == CTRUMP_EXPR_BIN_SUB) {
            /* push rhs & extract lhs */

            ae.e = index_expr->u.binary.rhs;
            ae.is_sign = (index_expr->code == CTRUMP_EXPR_BIN_SUB);
            VA_PUSH(struct add_stack_elem, &add_stack, ae);
            index_expr = ctrump_peel_paren(index_expr->u.binary.lhs);
        }

        if (analyze_subscript_coef(index_expr, &next_level_index,
                                   coef_var, invariant, var_info_map)) {
            if (*next_level_index_ret) {
                /* currently it does not support [i*n+j*m] */

                append_multiple_scaled_index(random_access,
                                             *next_level_index_ret, next_level_index,
                                             at_stmt, at_expr, tmp_alloc);
                goto error;
            }

            *next_level_index_ret = next_level_index;

            continue;
        }

        if (index_expr->code != CTRUMP_EXPR_VARREF) {
            append_complicated_subscript(random_access, index_expr, at_stmt, at_expr, tmp_alloc);
            goto error;
        }

        var = index_expr->u.varref.var;
        vi = ctrump_intmap_lookup(var_info_map, &found, var->id);
        assert(found);

        index = vi->index;

        for (j=loop_level; j>=0; j--) {
            incr = iv_level[j][index].incr;
            r = ctrump_bitmap_p(inductive_bmp[j], index);

            if (r) {
                break;
            }
        }

        if (j==-1) {
            /* not inductive */

            if (! ctrump_bitmap_p(invariant, index)) {
                append_index_var_not_inductive(random_access,
                                               var, at_stmt, at_expr, tmp_alloc);
                goto error;
            }

            VA_NEWELEM(indices);
            loop_index = VA_LAST_PTR(struct ctrump_loop_index, indices);
            loop_index->code = CTRUMP_LOOP_INDEX_INVARIANT;
            loop_index->u.invariant = vi->var;
        } else {
            /* inductive */
            VA_NEWELEM(indices);
            loop_index = VA_LAST_PTR(struct ctrump_loop_index, indices);

            loop_index->code = CTRUMP_LOOP_INDEX_INDUCTIVE;
            loop_index->u.iv.incr = incr;
            loop_index->u.iv.iv_level = j;
            loop_index->u.iv.var = var;
            loop_index->u.iv.reach_at_loop_entry = iv_level[j][index].reach_at_loop_entry;
        }

        if (is_sign) {
            loop_index->flags = CTRUMP_LOOP_INDEX_NEGATIVE;
        } else {
            loop_index->flags = 0;
        }
    }

    *constant_offset = offset_sum;
    return 1;

error:
    return 0;
}



static int
expr_subscripts_to_loop_subscript(struct ctrump_varray *random_access,
                                  int num_subscript,
                                  struct ctrump_subscript *subscripts,
                                  int *num_loop_subscript,
                                  struct ctrump_loop_subscript **ret_subscripts,
                                  int *num_constraint,
                                  struct ctrump_loop_subscript_constraint **ret_constraints,
                                  int ptr_incr,
                                  int ptr_incr_iv_level,
                                  int loop_level,
                                  struct iv_info **iv_level,
                                  struct ctrump_loop_exit **exit_level,
                                  ctrump_bitmap_t invariant,
                                  ctrump_bitmap_t *inductive_bmp,
                                  struct ctrump_intmap *var_info_map,
                                  struct ctrump_expr *array,
                                  struct ctrump_stmt *at_stmt,
                                  struct ctrump_expr *at_expr,
                                  struct ctrump_mempool *tmp_alloc,
                                  struct ctrump_mempool *alloc,
                                  int *id)
{
    struct ctrump_varray loop_subscripts, loop_indices;
    struct ctrump_loop_subscript *reverse, *p;
    int i, n, nd, num_nd;

    ctrump_varray_init(&loop_subscripts, 4, sizeof(struct ctrump_loop_subscript));
    ctrump_varray_init(&loop_indices, 4, sizeof(struct ctrump_loop_index));

    /* There are 3 level loops
     * 
     * 1st: pointer subscript loop
     *      int ***a;
     *      a[99][33][48] : i = 0..nd_subscript
     *
     * 2nd: Ndimensional array subscript loop
     *      int a[][][]
     *      a[41][10][55] : nd = 0..num_nd
     *
     * 3rd: index scale
     *      int a[]
     *      a[((X*pitch)+Y)*pitch2+Z] : until scale is exist
     */

    for (i=0; i<num_subscript; i++) {
        /* int **array; array[i][j] */

        union ctrump_loop_subscript_scale subscript_scale = {0};
        enum ctrump_loop_subscript_code subscript_code = -1;

        struct ctrump_subscript *tree_subscript = &subscripts[i];

        num_nd = tree_subscript->num_nd_subscript;

        for (nd=0; nd<num_nd; nd++) {
            /* int array[10][20]; array[i][j] */
            struct ctrump_expr *subscript_expr;
            int subscript_coef;
            struct ctrump_subscript_nd *nds = &subscripts[i].nd_subscripts[nd];
            struct ctrump_loop_subscript *e;

            switch (nds->code) {
            case CTRUMP_SUBSCRIPT_RECORD_MEMBER:
                VA_NEWELEM(&loop_subscripts);
                e = VA_LAST_PTR(struct ctrump_loop_subscript, &loop_subscripts);
                e->id = (*id)++;
                e->code = CTRUMP_LOOP_SUBSCRIPT_RECORD_MEMBER;
                e->u.record_member.member_name = nds->u.record_member.member_name;
                e->u.record_member.record_type = nds->u.record_member.record_type;
                e->indices = NULL;
                e->num_index = 0;
                e->offset = 0;
                break;

            case CTRUMP_SUBSCRIPT_RECORD_MEMBER_TERMINAL:
                VA_NEWELEM(&loop_subscripts);
                e = VA_LAST_PTR(struct ctrump_loop_subscript, &loop_subscripts);
                e->id = (*id)++;
                e->code = CTRUMP_LOOP_SUBSCRIPT_RECORD_MEMBER_TERMINAL;
                e->u.record_member_terminal.member_name = nds->u.record_member_terminal.member_name;
                e->u.record_member_terminal.record_type = nds->u.record_member_terminal.record_type;
                e->u.record_member_terminal.load_type = nds->u.record_member_terminal.load_type;
                e->indices = NULL;
                e->num_index = 0;
                e->offset = 0;
                break;

            case CTRUMP_SUBSCRIPT_LOAD_RECORD:
            case CTRUMP_SUBSCRIPT_COEF_ARRAY:
            case CTRUMP_SUBSCRIPT_TERMINAL:
                switch (nds->code) {
                case CTRUMP_SUBSCRIPT_COEF_ARRAY:
                    subscript_expr = nds->u.array_coef.expr;
                    subscript_coef = nds->u.array_coef.coef;
                    subscript_code = CTRUMP_LOOP_SUBSCRIPT_COEF_ARRAYSIZE;
                    subscript_scale.array_size_coef = subscript_coef;
                    break;

                case CTRUMP_SUBSCRIPT_TERMINAL:
                    subscript_expr = nds->u.terminal.expr;
                    subscript_code = CTRUMP_LOOP_SUBSCRIPT_COEF_TERMINAL;
                    subscript_scale.load_type = nds->u.terminal.load_type;
                    break;

                case CTRUMP_SUBSCRIPT_LOAD_RECORD:
                    subscript_expr = nds->u.load_record.expr;
                    subscript_code = CTRUMP_LOOP_SUBSCRIPT_LOAD_RECORD;
                    subscript_scale.load_record.load_type = nds->u.load_record.load_type;
                    break;

                default:
                    ctrump_unreachable("compiler bug");
                    break;
                }


                /* analyze subscript
                 *  for (i=0; i<N; i++) {
                 *    for (j=0; j<M; j+=2) {
                 *      for (k=0; k<L; k++) {
                 *        a[(i*pitch_a + j + 3)*pitch_b+k] = 0;
                 *      }
                 *    }
                 *  }
                 * 
                 * is recognized as
                 * 
                 *  a[i][j+3][k] when (pitch_a > (M+3)*2 && pitch_b > L)
                 * 
                 * subscripts[0] = i, offset = 0, incr = 1
                 * subscripts[1] = j, offset = 3, incr = 2
                 * subscripts[2] = k, offset = 0, incr = 1
                 * 
                 * constraints[0] = pitch_b > L
                 * constraints[1] = pitch_a > M+3 * 2
                 */

                while (1) {
                    /* i*pitch */

                    struct ctrump_expr *next_level_index_expr = NULL;
                    struct ctrump_var *coef_var = NULL;
                    int subscript_off;

                    loop_indices.nelem = 0;
                    VA_NEWELEM(&loop_subscripts);
                    e = VA_LAST_PTR(struct ctrump_loop_subscript, &loop_subscripts);
                    e->id = (*id)++;

                    if (subscript_expr) {
                        /* ptr[subscript_expr] */
                        int r = single_expr_subscripts_to_loop_subscript(random_access,
                                                                         &loop_indices,
                                                                         &subscript_off,
                                                                         subscript_expr,
                                                                         &next_level_index_expr,
                                                                         &coef_var,
                                                                         iv_level,
                                                                         invariant,
                                                                         inductive_bmp,
                                                                         var_info_map,
                                                                         loop_level,
                                                                         at_stmt, at_expr, 
                                                                         tmp_alloc);

                        if (! r)
                            goto error;

                        e->code = subscript_code;
                        e->u = subscript_scale;
                        e->num_index = loop_indices.nelem;
                        e->offset = subscript_off;

                        if (next_level_index_expr == NULL) {
                            if (nd == (num_nd-1) && i == (num_subscript-1)) {
                                /* last */

                                if (ptr_incr != 0) {
                                    struct ctrump_loop_index *loop_index;
                                    VA_NEWELEM(&loop_indices);
                                    loop_index = VA_LAST_PTR(struct ctrump_loop_index, &loop_indices);

                                    loop_index->code = CTRUMP_LOOP_INDEX_POINTER_INC;
                                    loop_index->flags = 0;
                                    loop_index->u.ptrinc.incr = ptr_incr;
                                    loop_index->u.ptrinc.iv_level = ptr_incr_iv_level;
                                }
                            }

                            e->indices = ctrump_varray_copy(&loop_indices, alloc);

                            break;
                        }

                        e->indices = ctrump_varray_copy(&loop_indices, alloc);

                        subscript_code = CTRUMP_LOOP_SUBSCRIPT_COEF_SCALE;
                        subscript_scale.scale_array_coef = coef_var;
                        subscript_expr = ctrump_peel_paren(next_level_index_expr);
                        assert(coef_var);
                    } else {
                        /* *ptr */

                        if (ptr_incr != 0) {
                            struct ctrump_loop_index *loop_index;
                            loop_index = ctrump_mempool_alloc(alloc, sizeof(*loop_index));
                            
                            loop_index->code = CTRUMP_LOOP_INDEX_POINTER_INC;
                            loop_index->flags = 0;
                            loop_index->u.ptrinc.incr = ptr_incr;
                            loop_index->u.ptrinc.iv_level = ptr_incr_iv_level;

                            e->code = subscript_code;
                            e->u = subscript_scale;
                            e->num_index = 1;
                            e->indices = loop_index;
                            e->offset = 0;
                        } else {
                            e->code = subscript_code;
                            e->u = subscript_scale;
                            e->num_index = 0;
                            e->indices = 0;
                            e->offset = 0;
                        }

                        break;
                    }
                }
                break;
            }
        }
    }

    *num_constraint = 0;
    *ret_constraints = NULL;

    if (ptr_incr != 0) {        /* have array pointer increment */
                
    }

    n = *num_loop_subscript = loop_subscripts.nelem;
    reverse = ctrump_mempool_alloc(alloc, sizeof(*reverse)*n);
    p = loop_subscripts.elements;

    /* reverse subscripts */
    for (i=0; i<n; i++) {
        reverse[i] = p[n-1-i];
    }

    *ret_subscripts = reverse;

    ctrump_varray_discard(&loop_indices);

    return 1;

error:
    ctrump_varray_discard(&loop_subscripts);
    ctrump_varray_discard(&loop_indices);

    *num_constraint = 0;
    *ret_constraints = NULL;

    *num_loop_subscript = 0;
    *ret_subscripts = NULL;

    return 0;
}

typedef void (*parallel_array_func_t)(struct ctrump_varray *access_info,
                                      struct ctrump_var *invariant_var,
                                      int num_subscript,
                                      struct ctrump_loop_subscript *subscripts,
                                      int num_constraint,
                                      struct ctrump_loop_subscript_constraint *constraints,
                                      int flags,
                                      struct ctrump_stmt *at_stmt,
                                      struct ctrump_expr *at_expr,
                                      struct ctrump_mempool *alloc);

static void
recog_array_index(parallel_array_func_t parallel_func,
                  struct ctrump_varray *parallel_access,
                  struct ctrump_varray *random_access,
                  struct ctrump_memory_access *memory_access,
                  ctrump_bitmap_t invariant,
                  ctrump_bitmap_t invariant_on_loop_top,
                  ctrump_bitmap_t *inductive,
                  struct ctrump_stmt *at_stmt,
                  struct ctrump_expr *at_expr,
                  struct ctrump_intmap *var_info_map,
                  int flags,
                  struct iv_info **iv_level,
                  struct ctrump_loop_exit **exit_level,
                  int loop_level,
                  const struct ctrump_abi *abi,
                  struct ctrump_mempool *tmp_alloc,
                  struct ctrump_mempool *loop_alloc,
                  int *id)
{
    struct ctrump_expr *arr = memory_access->array;
    struct ctrump_subscript *subscripts = memory_access->subscripts;
    int num_subscript = memory_access->num_subscript;

    struct ctrump_var *av;
    struct ctrump_loop_subscript *loop_subscripts;
    struct ctrump_loop_subscript_constraint *constraints;

    int num_loop_subscript, num_constraint, r;

    /* a[i] */
    arr = ctrump_peel_cast_to_pointer_from_array(arr);

    if (arr->code == CTRUMP_EXPR_VARREF) {
        int ptr_incr = 0;
        int ptr_incr_iv_level = 0;

        av = arr->u.varref.var;

        if (! check_var_bmp_p(av, invariant, var_info_map)) {
            int found;
            struct ctrump_cfg_var_info *vi = ctrump_intmap_lookup(var_info_map, 
                                                                  &found, av->id);
            assert(found);

            /* fixme : search each loop_level */
            if (!ctrump_bitmap_p(inductive[loop_level], vi->index)) {
                append_array_not_invariant(random_access, arr, num_subscript, subscripts, at_stmt, at_expr, tmp_alloc);
                return;
            }

            /* iv pointer *(p++) */
            ptr_incr = iv_level[loop_level][vi->index].incr;
            ptr_incr_iv_level = loop_level;
        }

        r = expr_subscripts_to_loop_subscript(random_access,
                                              num_subscript,
                                              subscripts,
                                              &num_loop_subscript,
                                              &loop_subscripts,
                                              &num_constraint,
                                              &constraints,
                                              ptr_incr, ptr_incr_iv_level,
                                              loop_level,
                                              iv_level,
                                              exit_level,
                                              invariant_on_loop_top,
                                              inductive,
                                              var_info_map,
                                              arr, at_stmt, at_expr, tmp_alloc, loop_alloc, id);

        if (! r) {
            return;
        }

        (*parallel_func)(parallel_access, av,
                         num_loop_subscript, loop_subscripts,
                         num_constraint, constraints, flags, at_stmt, at_expr, tmp_alloc);
    } else {
        append_complicated_array(random_access, arr, num_subscript, 
                                 subscripts, at_stmt, at_expr, tmp_alloc);
    }
}


int
ctrump_loop_index_equal(const struct ctrump_loop_index *i1,
                        const struct ctrump_loop_index *i2)
{
    if (i1->code != i2->code)
        return 0;
    if (i1->flags != i2->flags)
        return 0;

    switch (i1->code) {
    case CTRUMP_LOOP_INDEX_INDUCTIVE:
        if (i1->u.iv.var != i2->u.iv.var)
            return 0;

    case CTRUMP_LOOP_INDEX_INVARIANT:
        if (i1->u.invariant != i2->u.invariant)
            return 0;

    case CTRUMP_LOOP_INDEX_POINTER_INC:
        if (! (i1->u.ptrinc.iv_level == i2->u.ptrinc.iv_level &&
               i1->u.ptrinc.incr == i2->u.ptrinc.incr))
            return 0;
    }

    return 1;
}


int
ctrump_loop_subscript_equal(const struct ctrump_loop_subscript *s1,
                            const struct ctrump_loop_subscript *s2)
{
    int i, n;

    if (s1->offset != s2->offset)
        return 0;
    if (s1->num_index != s2->num_index)
        return 0;
    if (s1->code != s2->code)
        return 0;

    switch (s1->code) {
    case CTRUMP_LOOP_SUBSCRIPT_RECORD_MEMBER:
    case CTRUMP_LOOP_SUBSCRIPT_RECORD_MEMBER_TERMINAL:
        if (s1->u.record_member.member_name != s2->u.record_member.member_name)
            return 0;
        break;

        /* always two subscripts are equal
         * when subscripts are apply to same array. */
    case CTRUMP_LOOP_SUBSCRIPT_COEF_ARRAYSIZE:
    case CTRUMP_LOOP_SUBSCRIPT_COEF_TERMINAL:
    case CTRUMP_LOOP_SUBSCRIPT_COEF_SCALE: /* fixme : should handle as weak index when scale is differ */
    case CTRUMP_LOOP_SUBSCRIPT_COEF_CONSTANT: /* fixme : */
    case CTRUMP_LOOP_SUBSCRIPT_LOAD_RECORD:
        break;
    }

    n = s1->num_index;

    for (i=0; i<n; i++) {
        if (!ctrump_loop_index_equal(&s1->indices[i],
                                     &s2->indices[i]))
            return 0;
    }

    return 1;
}

int
ctrump_loop_index_hash(const struct ctrump_loop_index *i0)
{
    switch (i0->code) {
    case CTRUMP_LOOP_INDEX_INDUCTIVE:
        return i0->u.iv.var->name->hashval+1;

    case CTRUMP_LOOP_INDEX_INVARIANT:
        return i0->u.invariant->name->hashval+2;

    case CTRUMP_LOOP_INDEX_POINTER_INC:
        return (i0->u.ptrinc.iv_level<<10) | (i0->u.ptrinc.incr);
    }

    ctrump_unreachable("index_hash");
}

int
ctrump_loop_subscript_hash(const struct ctrump_loop_subscript *s0)
{
    int i, n;
    int v = 0;

    switch (s0->code) {
    case CTRUMP_LOOP_SUBSCRIPT_RECORD_MEMBER:
        v = s0->u.record_member.member_name->hashval + 5;
        break;

    case CTRUMP_LOOP_SUBSCRIPT_RECORD_MEMBER_TERMINAL:
        v = s0->u.record_member.member_name->hashval + 4;
        break;

    case CTRUMP_LOOP_SUBSCRIPT_COEF_ARRAYSIZE:
        v = s0->u.array_size_coef * 7;
        break;

    case CTRUMP_LOOP_SUBSCRIPT_COEF_TERMINAL:
        v = 99;
        break;

    case CTRUMP_LOOP_SUBSCRIPT_COEF_SCALE: /* fixme : should handle as weak index when scale is differ */
        v = s0->u.scale_array_coef->name->hashval + 9;
        break;

    case CTRUMP_LOOP_SUBSCRIPT_COEF_CONSTANT: /* fixme : */
        v = s0->u.array_size_coef + 13;
        break;

    case CTRUMP_LOOP_SUBSCRIPT_LOAD_RECORD:
        v = s0->u.load_record.load_type->id*8;
    }

    v += s0->offset<<10;
    n = s0->num_index;

    for (i=0; i<n; i++) {
        v += ctrump_loop_index_hash(&s0->indices[i]);
    }

    return v;
}



typedef void (*parallel_pointer_func_t)(struct ctrump_varray *access_info,
                                        struct ctrump_var *inductive_var,
                                        struct ctrump_mempool *alloc);

static void
append_memory_access(struct ctrump_varray *acc,
                     struct ctrump_ordered_memory_load_store_node *ordered,
                     enum ctrump_load_store_t lscode,
                     struct parallel_access_info *ai,
                     struct ctrump_mempool *tmp_alloc,
                     struct ctrump_mempool *loop_alloc,
                     struct ctrump_intmap *var_info_map,
                     struct iv_info *iv_info,
                     int *id)
{
    int index = acc->nelem;
    struct ctrump_loop_memory_access *ma;

    ordered->op_index = index;
    ordered->code = lscode;

    VA_NEWELEM_P(acc, tmp_alloc);
    ma = VA_LAST_PTR(struct ctrump_loop_memory_access, acc);

    /* (ma->array.var)[ma->subscripts[0]][ma->subscripts[1]] */
    ma->id = (*id)++;
    ma->array.var = ai->invariant;
    ma->num_subscript = ai->num_subscript;
    ma->subscripts = ai->subscripts;
    ma->num_constraint = ai->num_constraint;
    ma->constraints = ai->constraints;
    ma->at_stmt = ai->at_stmt;
    ma->at_expr = ai->at_expr;
}


static void
classify_memop(struct ctrump_loop_info_node *loop_info_node,
               struct loop_cfg_node *bbs,
               ctrump_bitmap_t is_conditional_bb,
               int num_bb,
               int all_num_bb_in_cfg,
               ctrump_bitmap_t invariant,
               ctrump_bitmap_t invariant_on_loop_top,
               ctrump_bitmap_t *inductive,
               int num_var,
               struct ctrump_intmap *var_info_map,
               struct iv_info **iv_level,
               struct ctrump_loop_exit **exit_level,
               const struct ctrump_abi *abi,
               struct ctrump_mempool *loop_alloc,
               struct ctrump_mempool *tmp_alloc,
               int *id)
{
    int i,j, n;
    int loop_level = loop_info_node->nest_level;
    struct iv_info *iv_info = iv_level[loop_info_node->nest_level];
    struct ctrump_varray access_info;
    struct ctrump_varray random_access, load, store;
    struct ctrump_ordered_memory_load_store_node *ordered;
    struct parallel_access_info *ai, *a;
    ctrump_bitmap_t visited;
    struct stack_node {
        int i;
        struct ctrump_bb *bb;
    } *sp;
    struct ctrump_bb *exit, *entry;
    struct ctrump_varray dfs_stack; /* struct stack_node */
    struct ctrump_mempool memop_pool;

    ctrump_mempool_init(&memop_pool, 256);

    ctrump_varray_init_pool(&access_info, 16, sizeof(struct parallel_access_info), &memop_pool);
    ctrump_varray_init_pool(&random_access, 16, sizeof(struct ctrump_random_access), &memop_pool);

    visited = zero_bmp(all_num_bb_in_cfg, &memop_pool);
    ctrump_varray_init_pool(&dfs_stack, 16, sizeof(struct stack_node), &memop_pool);
    VA_NEWELEM_P(&dfs_stack, &memop_pool);
    sp = VA_LAST_PTR(struct stack_node, &dfs_stack);
    entry = loop_info_node->cfg_info->cond_bb;
    sp->bb = entry;
    sp->i = 0;
    exit = loop_info_node->cfg_info->break_bb;

    while (dfs_stack.nelem) {
        struct ctrump_bb *bb;

    next:
        sp = VA_LAST_PTR(struct stack_node, &dfs_stack);
        bb = sp->bb;
        for (i=sp->i; i<bb->num_succs; i++) {
            struct ctrump_bb *suc = bb->succs[i];

            if ((! ctrump_bitmap_p(visited,suc->id_in_cfg)) &&
                (suc != exit)) {
                ctrump_bitmap_set(visited, suc->id_in_cfg);

                /*  save i */
                sp->i = i;

                /* push */
                VA_NEWELEM_P(&dfs_stack, &memop_pool);
                sp = VA_LAST_PTR(struct stack_node ,&dfs_stack);
                sp->i = 0;
                sp->bb = suc;
                goto next;
            }
        }

        dfs_stack.nelem--;

        if (bb->loop_belong_to != loop_info_node->cfg_info)
            continue;

        /* finish all succs */
        struct ctrump_load_store_set *memop = &bb->load_store;
        struct ctrump_memory_load *loads = memop->mem_loads;
        struct ctrump_memory_store *stores = memop->mem_stores;
        struct ctrump_ordered_memory_load_store_node *ord = memop->ordered_load_store;
        int n;
        int is_cond_bb;
        int flags;

        if (bb->num_dfs == 1 &&
            bb->dfs[0] == entry) {
            /* dominance frontier is cond_bb 
             *  -> unconditional (always run)
             */
            is_cond_bb = 0;
        } else {
            is_cond_bb = 1;
        }

        n = memop->num_memop;
        for (j=0; j<n; j++) {
            struct ctrump_ordered_memory_load_store_node *n = &ord[j];
            struct ctrump_memory_store *as;
            struct ctrump_memory_load *al;

            switch (n->code) {
            case CTRUMP_MEMORY_LOAD:
                al = &loads[n->op_index];
                recog_array_index(parallel_load,
                                  &access_info, &random_access,
                                  &al->mem_access, invariant, invariant_on_loop_top,
                                  inductive,
                                  al->mem_access.at_stmt, al->mem_access.at_expr,
                                  var_info_map, 0, iv_level,
                                  exit_level, loop_level, abi, &memop_pool, loop_alloc, id);
                break;

            case CTRUMP_MEMORY_STORE:
                as = &stores[n->op_index];

                flags = 0;
                if (is_cond_bb ||
                    (as->mem_access.flags & CTRUMP_MEMORY_ACCESS_PARTIAL)) {
                    flags |= PARALLEL_ACCESS_PARTIAL;
                }

                if (IS_BIN_OP_ASSIGN(as->store_op)) {
                    flags |= PARALLEL_ACCESS_OP_ASSIGN;
                }

                recog_array_index(parallel_store,
                                  &access_info, &random_access,
                                  &as->mem_access, 
                                  invariant, invariant_on_loop_top,
                                  inductive, as->mem_access.at_stmt, as->mem_access.at_expr,
                                  var_info_map, flags, iv_level,
                                  exit_level, loop_level, abi, &memop_pool, loop_alloc, id);
                break;
            }
        }
    }

    loop_info_node->num_random_access = random_access.nelem;
    loop_info_node->random_accesses = ctrump_varray_copy(&random_access, loop_alloc);

    ctrump_varray_init_pool(&load, access_info.nelem, sizeof(struct ctrump_loop_memory_access), &memop_pool);
    ctrump_varray_init_pool(&store, access_info.nelem, sizeof(struct ctrump_loop_memory_access), &memop_pool);
    ordered = ctrump_mempool_alloc(loop_alloc, sizeof(*ordered)*access_info.nelem);

    ai = access_info.elements;
    n = access_info.nelem;

    for (i=0; i<n; i++) {
        a = &ai[i];

        switch (a->type) {
        case LOAD:
            append_memory_access(&load, &ordered[i], CTRUMP_MEMORY_LOAD,
                                 a, &memop_pool, loop_alloc, var_info_map, iv_info, id);
            break;
        case STORE:
            append_memory_access(&store, &ordered[i], CTRUMP_MEMORY_STORE,
                                 a, &memop_pool, loop_alloc, var_info_map, iv_info, id);
            break;
        }
    }

    loop_info_node->num_parallel_load = load.nelem;
    loop_info_node->parallel_loads = ctrump_varray_copy(&load, loop_alloc);

    loop_info_node->num_parallel_store = store.nelem;
    loop_info_node->parallel_stores = ctrump_varray_copy(&store, loop_alloc);

    loop_info_node->num_ordered_loadstore = access_info.nelem;
    loop_info_node->ordered_loadstore = ordered;

    ctrump_mempool_destroy(&memop_pool);
}

struct bb_info {
    struct ctrump_bb *bb;
    int index;
};

static struct bb_info *
alloc_bb_info(struct ctrump_mempool *alloc,
              struct ctrump_bb *bb)
{
    struct bb_info *info = ctrump_mempool_alloc(alloc, sizeof(*info));

    info->bb = bb;

    return info;
}

static int
build_bfs_order(struct ctrump_intmap *ret,
                struct ctrump_bb *cond_bb,
                struct ctrump_bb *body_bb,
                struct loop_cfg_node **bfs_order_ret_ptr,
                struct ctrump_mempool *tmp_alloc)
{
    struct ctrump_intmap_bucket *bucket;
    int found;
    struct ctrump_queue queue;
    struct ctrump_intmap index_map; /* cfgid -> index map */
    struct bb_info *bb_info;
    int index = 0, i, n;
    int q_elem;
    struct ctrump_varray bfs_order;
    struct loop_cfg_node *bfs_order_ret;
    struct ctrump_bb **bbs;

    ctrump_intmap_init(&index_map, 53);
    ctrump_queue_init(&queue, 16, sizeof(struct bb_info*));
    ctrump_varray_init(&bfs_order, 16, sizeof(struct ctrump_bb*));

    bucket = ctrump_intmap_lookup_add(&index_map, &found, cond_bb->id);

    bb_info = alloc_bb_info(tmp_alloc, cond_bb);
    bb_info->index = index;
    index++;
    VA_PUSH(struct ctrump_bb*, &bfs_order, cond_bb);

    bucket->val = bb_info;

    bb_info = alloc_bb_info(tmp_alloc, body_bb);
    QUEUE_PUSH(struct bb_info*, &queue, bb_info);

    q_elem = 1;

    while (q_elem) {
        int i, n;
        struct ctrump_bb *bb;

        QUEUE_POP(struct bb_info*, &queue, bb_info);
        bb = bb_info->bb;
        bb_info->index = index;

        n = bb->num_succs;
        VA_PUSH(struct ctrump_bb*, &bfs_order, bb);

        index++;
        q_elem--;

        if (CTRUMP_BB_IS_LOOP_ENTRY(bb)) {
            /* In the outer loop, 
             * inner loops are handled as single bb-node. */
            struct ctrump_bb *succ = bb->loop_belong_to->break_bb;
            bucket = ctrump_intmap_lookup_add(&index_map, &found, succ->id);
            if (!found) {
                bb_info = alloc_bb_info(tmp_alloc, succ);
                QUEUE_PUSH(struct bb_info*, &queue, bb_info);
                bucket->val = bb_info;
                q_elem++;
            }
        } else {
            for (i=0; i<n; i++) {
                struct ctrump_bb *succ = bb->succs[i];
                bucket = ctrump_intmap_lookup_add(&index_map, &found, succ->id);
                if (!found) {
                    bb_info = alloc_bb_info(tmp_alloc, succ);
                    QUEUE_PUSH(struct bb_info*, &queue, bb_info);
                    bucket->val = bb_info;
                    q_elem++;
                }
            }
        }
    }
    
    ctrump_intmap_resize_pool(ret, &index_map, tmp_alloc);
    ctrump_intmap_free(&index_map);
    ctrump_queue_destroy(&queue);

    n = bfs_order.nelem;
    bbs = bfs_order.elements;
    bfs_order_ret = ctrump_mempool_alloc(tmp_alloc, sizeof(*ret)*n);

    for (i=0; i<n; i++) {
        if (bbs[i] != cond_bb && CTRUMP_BB_IS_LOOP_ENTRY(bbs[i])) {
            /* inner loop */
            bfs_order_ret[i].code = LOOP_CFG_NODE_INNER_LOOP;
            bfs_order_ret[i].u.loop = bbs[i]->loop_belong_to->u.loop_info_node;
        } else {
            bfs_order_ret[i].code = LOOP_CFG_NODE_BB;
            bfs_order_ret[i].u.bb = bbs[i];
        }
    }

    *bfs_order_ret_ptr = bfs_order_ret;
    ctrump_varray_discard(&bfs_order);

    return n;
}

static int
get_var_id(struct ctrump_var *var,
           struct ctrump_intmap *var_info_map)
{
    struct ctrump_cfg_var_info *vi;
    int found;
    vi = ctrump_intmap_lookup(var_info_map, &found, var->id);

    return vi->index;
}

static int
is_invariant_expr(struct ctrump_expr *expr,
                  ctrump_bitmap_t invariant,
                  struct ctrump_intmap *var_info_map)
{
    struct ctrump_var *v;

    switch (expr->code) {
    case CTRUMP_EXPR_VARREF:
        v = expr->u.varref.var;
        return ctrump_bitmap_p(invariant, get_var_id(v, var_info_map));

    case CTRUMP_CASE_CONSTANT_TERM:
        return 1;

    case CTRUMP_CASE_BIN_ARITH_EXPR:
    case CTRUMP_CASE_BIN_LOG_EXPR:
        return is_invariant_expr(expr->u.binary.lhs,invariant,var_info_map) &&
            is_invariant_expr(expr->u.binary.rhs,invariant,var_info_map);

    default:
        break;
    }

    return 0;
}

static void
recog_exit_cond_cmp(struct ctrump_loop_exit *loop_exit,
                    struct ctrump_expr *lhs,
                    struct ctrump_expr *rhs,                
                    ctrump_bitmap_t inductive,
                    ctrump_bitmap_t invariant,
                    struct ctrump_intmap *var_info_map,
                    struct iv_info *iv,
                    enum ctrump_expr_code cmp_op)
{
    int is_bound_invariant;
    int ind_var_info_id;
    struct ctrump_var *ind_var;

    if (lhs->code != CTRUMP_EXPR_VARREF) {
        goto unpredicatable;
    }

    ind_var = lhs->u.varref.var;
    ind_var_info_id = get_var_id(ind_var, var_info_map);

    if (! BMP_P(inductive, ind_var_info_id)) {
        goto unpredicatable;
    }

    is_bound_invariant = is_invariant_expr(rhs, invariant, var_info_map);
    if (! is_bound_invariant) {
        goto unpredicatable;
    }

    /* 'inductive op invariant' */
    loop_exit->code = CTRUMP_LOOP_COUNT_PREDICTABLE;
    loop_exit->u.pred.cmp_op = cmp_op;
    loop_exit->u.pred.incr = iv[ind_var_info_id].incr;
    loop_exit->u.pred.inductive = ind_var;
    loop_exit->u.pred.iv_loop_entry_value = iv[ind_var_info_id].reach_at_loop_entry;
    loop_exit->u.pred.bound = rhs;
    return;

unpredicatable:
    loop_exit->code = CTRUMP_LOOP_COUNT_UNPREDICTABLE;
}

static void
recog_exit_cond(struct ctrump_loop_exit *loop_exit,
                struct ctrump_expr *cond_expr,
                ctrump_bitmap_t inductive,
                ctrump_bitmap_t invariant,
                struct ctrump_intmap *var_info_map,
                struct iv_info *iv_info)
{
    switch (cond_expr->code) {
    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:
        recog_exit_cond_cmp(loop_exit,
                            cond_expr->u.binary.lhs, cond_expr->u.binary.rhs,
                            inductive, invariant, var_info_map, iv_info, cond_expr->code);
        break;

    default:
        loop_exit->code = CTRUMP_LOOP_COUNT_UNPREDICTABLE;
        break;
    }
}

struct analyze_loop_node_info {
    ctrump_bitmap_t is_conditional_bb; 
    ctrump_bitmap_t tmp_bmp;           
    int num_bb;                        
    struct loop_cfg_node *bfs_order;   
    struct iv_info *iv_info;           
};

static void
init_analyze_loop_node_info(struct analyze_loop_node_info *dest,
                            struct ctrump_cfg *cfg,
                            struct ctrump_loop_info_node *node,
                            struct ctrump_mempool *loop_alloc,
                            struct ctrump_mempool *tmp_alloc)

{
    struct ctrump_loop_cfg_info *loop_cfg_info = node->cfg_info;
    struct ctrump_intmap bb_info_map;
    struct loop_cfg_node *bfs_order;
    int num_bb, num_var = cfg->num_var;
    ctrump_bitmap_t use, modify, is_conditional_bb;
    int i;
    struct iv_info *iv_info;

    is_conditional_bb = zero_bmp(num_var, tmp_alloc);
    num_bb = build_bfs_order(&bb_info_map,
                             loop_cfg_info->cond_bb,
                             loop_cfg_info->body_start_bb, &bfs_order,
                             tmp_alloc);
    /*
    exe_order = ctrump_mempool_alloc(tmp_alloc, num_bb*sizeof(struct loop_cfg_node*));
    for (i=0; i<num_bb; i++) {
        exe_order[i] = &bfs_order[i];
    }
    qsort(exe_order, num_bb, sizeof(struct loop_cfg_node*), cmp_bb_id);
    */

    use = zero_bmp(num_var, loop_alloc);
    modify = zero_bmp(num_var, loop_alloc);

    iv_info = ctrump_mempool_alloc(tmp_alloc, sizeof(struct iv_info)*num_var);
    for (i=0; i<num_var; i++) {
        iv_info[i].incr = 0;
    }

    /* extract all used & modified variable */
    for (i=0; i<num_bb; i++) {
        struct loop_cfg_node *node = &bfs_order[i];
        struct ctrump_bb *bb;

        switch (node->code) {
        case LOOP_CFG_NODE_INNER_LOOP:
            ctrump_bitmap_or(use, use, node->u.loop->use, num_var);
            ctrump_bitmap_or(modify, modify, node->u.loop->modify, num_var);
            break;

        case LOOP_CFG_NODE_BB:
            bb = node->u.bb;
            ctrump_bitmap_or(use, use, bb->use, num_var);
            ctrump_bitmap_or(modify, modify, bb->kill, num_var);
            if (bb->num_dfs == 1 &&
                bb->dfs[0] == loop_cfg_info->cond_bb) {
                /* dominance frontier is cond_bb 
                 *  -> unconditional (always run)
                 */
            } else {
                ctrump_bitmap_set(is_conditional_bb, i);
            }
            break;
        }
    }

    dest->num_bb = num_bb;
    dest->bfs_order = bfs_order;
    /*dest->exe_order = exe_order;*/
    dest->is_conditional_bb = is_conditional_bb;
    dest->iv_info = iv_info;
    dest->tmp_bmp = zero_bmp(num_var, tmp_alloc);

    node->use = use;
    node->modify = modify;

    loop_cfg_info->u.loop_info_node = node;
    loop_cfg_info->cond_bb->loop_belong_to = loop_cfg_info;

    loop_cfg_info->code = CTRUMP_LOOP;
}


static int
ctrump_find_iv_node(struct ctrump_loop_info *loop_info,
                    struct ctrump_loop_info_node *loop_info_node,
                    struct analyze_loop_node_info *analyze_info,
                    struct ctrump_cfg *cfg,
                    struct ctrump_intmap *var_info_map,
                    struct ctrump_mempool *loop_alloc,
                    struct ctrump_mempool *tmp_alloc,
                    int id)
{
    struct ctrump_loop_cfg_info *loop_cfg_info = loop_info_node->cfg_info;
    struct loop_cfg_node *bfs_order;
    int num_bb, num_var = cfg->num_var;
    ctrump_bitmap_t invariant, use, modify, inductive, is_conditional_bb;
    ctrump_bitmap_t modified_and_live_after_loop, carry_dep;
    ctrump_bitmap_t tmp_bmp;
    struct iv_info *iv_info;

    num_bb = analyze_info->num_bb;
    bfs_order = analyze_info->bfs_order;
    tmp_bmp = analyze_info->tmp_bmp;
    is_conditional_bb = analyze_info->is_conditional_bb;
    use = loop_info_node->use;
    modify = loop_info_node->modify;

    iv_info = analyze_info->iv_info;

    carry_dep = zero_bmp(num_var, loop_alloc);
    inductive = zero_bmp(num_var, loop_alloc);
    invariant = zero_bmp(num_var, loop_alloc);

    modified_and_live_after_loop = zero_bmp(num_var, loop_alloc);

    find_invariant(cfg, invariant, use, modify);
    find_iv(inductive, bfs_order, loop_cfg_info,
            is_conditional_bb, num_bb, num_var,
            iv_info, var_info_map);

    ctrump_bitmap_copy(tmp_bmp, inductive, num_var);

    find_loop_carry_dependency(modified_and_live_after_loop,
                               carry_dep,
                               loop_cfg_info->cond_bb,
                               loop_cfg_info->break_bb,
                               num_bb,
                               use, modify,
                               inductive,
                               num_var);

    loop_info_node->num_var = num_var;
    loop_info_node->inductive_var = inductive;
    loop_info_node->invariant_var = invariant;
    loop_info_node->modified_and_live_after_loop = modified_and_live_after_loop;
    loop_info_node->carry_dep = carry_dep;

    return id;
}

static int
assign_nest_level(struct ctrump_loop_info_node *loop_tree_node,
                  int max_nest_level,
                  int nest_level)
{
    int i, n;
    loop_tree_node->nest_level = nest_level;

    n = loop_tree_node->num_child;
    for (i=0; i<n; i++) {
        max_nest_level = assign_nest_level(loop_tree_node->children[i],
                                           max_nest_level,
                                           nest_level+1);
        loop_tree_node->children[i]->parent = loop_tree_node;
    }

    if (nest_level > max_nest_level) {
        return nest_level;
    }
    return max_nest_level;
}

static int
analyze_loop_iv(struct ctrump_loop_info *dest,
                struct ctrump_loop_info_node **dfs_order,
                int num_node,
                struct analyze_loop_node_info *analyze_info,
                struct ctrump_cfg *cfg,
                struct ctrump_intmap *var_info_map,
                struct ctrump_mempool *loop_alloc,
                struct ctrump_mempool *tmp_alloc,
                int id)
{
    int i;

    for (i=0; i<num_node; i++) {
        id = ctrump_find_iv_node(dest,
                                 dfs_order[i],
                                 &analyze_info[i],
                                 cfg, var_info_map, loop_alloc, tmp_alloc, id);
    }

    return id;
}


static void
analyze_memory_access_level(struct ctrump_loop_info *dest,
                            struct ctrump_loop_info_node *loop_tree_node,
                            struct analyze_loop_node_info *analyze_info,
                            struct ctrump_cfg *cfg,
                            struct ctrump_intmap *var_info_map,
                            const struct ctrump_abi *abi,
                            struct ctrump_mempool *loop_alloc,
                            struct ctrump_mempool *tmp_alloc,
                            struct iv_info **iv_level,
                            ctrump_bitmap_t *ivbmp_level,
                            ctrump_bitmap_t invariant_on_loop_top,
                            struct ctrump_loop_exit **exit_level,
                            int *id)
{
    int i, n;
    int level = loop_tree_node->nest_level;
    struct analyze_loop_node_info *self_info;
    self_info = &analyze_info[loop_tree_node->dfs_order];
    n = loop_tree_node->num_child;
    iv_level[level] = self_info->iv_info;
    ivbmp_level[level] = loop_tree_node->inductive_var;
    exit_level[level] = &loop_tree_node->exit_info;

    for (i=0; i<n; i++) {
        struct ctrump_loop_info_node *child = loop_tree_node->children[i];
        analyze_memory_access_level(dest, child,
                                    analyze_info,
                                    cfg, var_info_map, abi,
                                    loop_alloc, tmp_alloc, iv_level,
                                    ivbmp_level, invariant_on_loop_top, exit_level, id);
    }

    classify_memop(loop_tree_node, self_info->bfs_order,
                   self_info->is_conditional_bb,
                   self_info->num_bb,
                   cfg->num_bb,
                   loop_tree_node->invariant_var,
                   invariant_on_loop_top,
                   ivbmp_level,
                   cfg->num_var,
                   var_info_map,
                   iv_level, exit_level, abi, loop_alloc, tmp_alloc, id);
}

static void
analyze_memory_access(struct ctrump_loop_info *dest,
                      struct ctrump_loop_info_node *loop_tree_node,
                      struct analyze_loop_node_info *analyze_info,
                      struct ctrump_cfg *cfg,
                      struct ctrump_intmap *var_info_map,
                      const struct ctrump_abi *abi,
                      struct ctrump_mempool *loop_alloc,
                      struct ctrump_mempool *tmp_alloc,
                      int *id)
{
    int max_level = dest->nest_level;
    struct iv_info **iv_level = malloc(sizeof(struct iv_info*)*max_level);
    ctrump_bitmap_t *iv_bitmap = malloc(sizeof(ctrump_bitmap_t)*max_level);
    struct ctrump_loop_exit **exit_level = malloc(sizeof(struct ctrump_loop_exit)*max_level);
    ctrump_bitmap_t invariant_on_loop_top = loop_tree_node->invariant_var;
    analyze_memory_access_level(dest, loop_tree_node, 
                                analyze_info, cfg, var_info_map, 
                                abi, loop_alloc, tmp_alloc, iv_level, iv_bitmap, invariant_on_loop_top, exit_level, id);
    free(iv_level);
}


static int
count_loop_node(struct ctrump_loop_info_node *node, int dfs_order_index)
{
    int i,n = node->num_child;

    for (i=0; i<n; i++) {
        dfs_order_index = count_loop_node(node->children[i], dfs_order_index);
    }

    node->dfs_order = dfs_order_index;

    return dfs_order_index + 1;
}

static int
build_dfs_order(struct ctrump_loop_info_node **dfs_order, struct ctrump_loop_info_node *node,
                int dfs_order_index)
{
    int i, n = node->num_child;
    for (i=0; i<n; i++) {
        dfs_order_index = build_dfs_order(dfs_order, node->children[i], dfs_order_index);
    }
    dfs_order[dfs_order_index] = node;

    return dfs_order_index+1;
}


static void
init_analyze_info(struct analyze_loop_node_info *info,
                  struct ctrump_loop_info_node **node_dfs_order,
                  int num_node,
                  struct ctrump_cfg *cfg,
                  struct ctrump_mempool *loop_alloc,
                  struct ctrump_mempool *tmp_alloc)
{
    int i;

    for (i=0; i<num_node; i++) {
        init_analyze_loop_node_info(&info[i], cfg, node_dfs_order[i],
                                    loop_alloc, tmp_alloc);
    }
}

static void
find_loop_entry(struct ctrump_loop_info_node **nodes,
                int num_node)
{
    int i, j;
    for (i=0; i<num_node; i++) {
        struct ctrump_loop_info_node *node = nodes[i];
        struct ctrump_loop_cfg_info *cfg_info = node->cfg_info;
        struct ctrump_bb *cond_bb = cfg_info->cond_bb;
        int num_pred = cond_bb->num_preds;
        struct ctrump_bb **preds = cond_bb->preds;

        int bb_before_loop = -1;

        for (j=0; j<num_pred; j++) {
            struct ctrump_bb *p = preds[j];

            if ((p->num_dfs == 1) &&
                (p->dfs[0] == cond_bb)) {
                /* elements of loop */
            } else {
                /* number of bb_before_loop should be 1 */
                assert(bb_before_loop == -1);

                bb_before_loop = j;
            }
        }

        /* number of bb_before_loop should be 1 */
        assert(bb_before_loop != -1);
    }
}

static void
iv_canonicalize(struct ctrump_loop_info_node **dfs_order,
                struct analyze_loop_node_info *info,
                int num_node)
{
    int i;
    int change = 0;
    do {
        for (i=0; i<num_node; i++) {
            //iv_canonicalize_node(dfs_order[i], &info[i]);
        }
    } while (change);
}


static void
loop_exit_analyze(struct ctrump_loop_info_node **nodes,
                  struct analyze_loop_node_info *info,
                  int num_node,
                  struct ctrump_intmap *var_info_map)
{
    int i;
    for (i=0; i<num_node; i++) {
        struct ctrump_loop_info_node *node = nodes[i];

        recog_exit_cond(&node->exit_info,
                        node->cfg_info->exit_cond,
                        node->inductive_var, node->invariant_var, 
                        var_info_map, info[i].iv_info);
    }
}

struct recog_reduction_info {
    enum ctrump_reductive_expr_code code;
    struct ctrump_stmt *at;
};

static void
merge_reduc_op(ctrump_bitmap_t is_reduc,
               ctrump_bitmap_t is_initial,
               struct recog_reduction_info *reduc_list,
               int var_idx,
               enum ctrump_reductive_expr_code merge_op,
               struct ctrump_stmt *at)
{
    if (ctrump_bitmap_p(is_reduc, var_idx)) {
        if (ctrump_bitmap_p(is_initial, var_idx)) {
            /* first operation */
            ctrump_bitmap_clear(is_initial, var_idx);
            reduc_list[var_idx].code = merge_op;
            reduc_list[var_idx].at = at;
        } else {
            if (reduc_list[var_idx].code != merge_op) {
                ctrump_bitmap_clear(is_reduc, var_idx);
            }
        }
    }
}

static enum ctrump_reductive_expr_code incr_op_to_reduc_op[] = {
    [CTRUMP_PDG_INC] = CTRUMP_REDUCTIVE_ADD,
    [CTRUMP_PDG_DEC] = CTRUMP_REDUCTIVE_SUB,
    [CTRUMP_PDG_FINC] = CTRUMP_REDUCTIVE_FADD,
    [CTRUMP_PDG_FDEC] = CTRUMP_REDUCTIVE_FSUB,
};

static void
recog_reduction_domtree(struct ctrump_bb *bb,
                        struct ctrump_bb *exit_bb,
                        struct ctrump_intmap *var_info_map,
                        int num_var,
                        ctrump_bitmap_t is_reduc,
                        ctrump_bitmap_t is_initial,
                        struct recog_reduction_info *reduc_list)
{
    int i, n = bb->num_dom_children;
    struct ctrump_var_store *st;
    for (i=0; i<n; i++) {
        struct ctrump_bb *c = bb->dom_children[i];

        if (c != exit_bb) {
            recog_reduction_domtree(c, exit_bb, var_info_map, num_var,
                                    is_reduc, is_initial, reduc_list);
        }
    }

    n = bb->load_store.num_store;
    st = bb->load_store.stores;
    for (i=0; i<n; i++) {
        struct ctrump_var_store *s = &st[i];
        struct ctrump_pdg_node *store_val = s->new_val;
        struct ctrump_var *var = s->var;
        int found;
        struct ctrump_cfg_var_info *vi = ctrump_intmap_lookup(var_info_map, &found, var->id);
        int var_idx = vi->index;

        assert(found);

        switch (store_val->code) {
        case CTRUMP_PDG_VALUE_REDUCTION:
            merge_reduc_op(is_reduc, is_initial, reduc_list,
                           var_idx, store_val->u.reduction.op, store_val->at);
            break;

        case CTRUMP_PDG_VALUE_INCREMENTAL:
            merge_reduc_op(is_reduc, is_initial, reduc_list,
                           var_idx, incr_op_to_reduc_op[store_val->u.incr.op], store_val->at);
            break;

        default:
            /* not reduction */
            ctrump_bitmap_clear(is_reduc, var_idx);
            break;
        }
    }
}

static void
recog_reduction(struct ctrump_loop_info_node **loops,
                int num_loop_node,
                struct analyze_loop_node_info *info_list,
                struct ctrump_intmap *var_info_map,
                struct ctrump_cfg_var_info *var_info_list,
                int num_var,
                struct ctrump_mempool *loop_alloc,
                struct ctrump_mempool *tmp_alloc)
{
    int i, j;

    ctrump_bitmap_t is_reduc = ctrump_bmp_alloc(num_var, tmp_alloc);
    ctrump_bitmap_t is_initial = ctrump_bmp_alloc(num_var, tmp_alloc);
    struct recog_reduction_info *reduc_list = ctrump_mempool_alloc(tmp_alloc, num_var*sizeof(*reduc_list));

    for (i=0; i<num_loop_node; i++) {
        struct ctrump_loop_info_node *n = loops[i];
        int num_reduc;

        ctrump_bitmap_set_all(is_reduc, num_var);
        ctrump_bitmap_set_all(is_initial, num_var);

        recog_reduction_domtree(n->cfg_info->cond_bb, n->cfg_info->break_bb,
                                var_info_map, num_var, is_reduc, is_initial, reduc_list);

        /* remove uninitialized */
        ctrump_bitmap_nand(is_reduc, is_reduc, is_initial, num_var);

        /* reductions should be modified in this loop */
        ctrump_bitmap_and(is_reduc, is_reduc, n->modified_and_live_after_loop, num_var);

        num_reduc = ctrump_bitmap_popcnt(is_reduc, num_var);

        /* reduction is not carry dependency */
        ctrump_bitmap_nand(n->carry_dep, n->carry_dep, is_reduc, num_var);

        n->num_reduc_op = num_reduc;
        n->reductions = ctrump_mempool_alloc(loop_alloc, num_reduc*sizeof(*n->reductions));

        for (j=0; j<num_reduc; j++) {
            int pos = ctrump_bitmap_ffs(is_reduc, num_var);
            assert(pos >= 0);

            ctrump_bitmap_clear(is_reduc, pos);

            n->reductions[j].op = reduc_list[pos].code;
            n->reductions[j].var = var_info_list[pos].var;
            n->reductions[j].at = reduc_list[pos].at;
        }
    }
}

int
ctrump_analyze_loop(struct ctrump_loop_info *dest,
                    int *level_depth,
                    struct ctrump_loop_info_node *loop_tree_node,
                    struct ctrump_cfg *cfg,
                    struct ctrump_intmap *var_info_map,
                    const struct ctrump_abi *abi,
                    struct ctrump_mempool *loop_alloc,
                    int id)
{
    struct ctrump_mempool tmp_alloc;
    struct analyze_loop_node_info *analyze_info_dfs; /* depth first search - post ordering */
    int num_loop_node;
    struct ctrump_loop_info_node **dfs_order;

    ctrump_mempool_init(&tmp_alloc, 1024);

    num_loop_node = count_loop_node(loop_tree_node, 0);
    dfs_order = ctrump_mempool_alloc(&tmp_alloc, num_loop_node*sizeof(*dfs_order));
    build_dfs_order(dfs_order, loop_tree_node, 0);
    analyze_info_dfs = ctrump_mempool_alloc(&tmp_alloc, num_loop_node*sizeof(*analyze_info_dfs));

    init_analyze_info(analyze_info_dfs, dfs_order, num_loop_node, cfg, loop_alloc, &tmp_alloc);

    *level_depth = assign_nest_level(loop_tree_node, 0, 0) + 1; /* maxdepth + 1 */
    find_loop_entry(dfs_order, num_loop_node);

    id = analyze_loop_iv(dest, dfs_order, num_loop_node, analyze_info_dfs, cfg, var_info_map, loop_alloc, &tmp_alloc, id);
    iv_canonicalize(dfs_order, analyze_info_dfs, num_loop_node);
    loop_exit_analyze(dfs_order, analyze_info_dfs, num_loop_node, var_info_map);

    analyze_memory_access(dest, loop_tree_node, analyze_info_dfs, cfg, var_info_map, abi, loop_alloc, &tmp_alloc, &id);

    recog_reduction(dfs_order, num_loop_node, analyze_info_dfs, var_info_map, cfg->var_info, cfg->num_var, loop_alloc, &tmp_alloc);

    ctrump_mempool_destroy(&tmp_alloc);

    ctrump_get_loop_depinfo(dest, &id, loop_alloc);

    return id;
}

---