ctrump/analyzer/loop.h

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.
*/

#ifndef CTRUMP_ANALYZER_LOOP_H
#define CTRUMP_ANALYZER_LOOP_H

#include "ctrump/analyzer/var.h"
#include "ctrump/analyzer/cfg.h"
#include "ctrump/ast/expr-code.h"

#ifdef __cplusplus
extern "C" {
#endif

struct ctrump_expr;
struct ctrump_stmt;
struct ctrump_var;

enum ctrump_complicated_loop_reason_code {
    CTRUMP_COMPLICATED_LOOP_BREAK, 
    CTRUMP_COMPLICATED_LOOP_GOTO,  
    CTRUMP_COMPLICATED_LOOP_RETURN, 
    CTRUMP_COMPLICATED_LOOP_HAVE_COMPLICATED_NEST, 
    CTRUMP_COMPLICATED_LOOP_INVOKE_FUNC,           
    CTRUMP_COMPLICATED_LOOP_NEST, 
    CTRUMP_COMPLICATED_LOOP_HAS_MULTI_ENTRY 
};

struct ctrump_complicated_loop {
    enum ctrump_complicated_loop_reason_code reason; 
    struct ctrump_stmt *stmt;                        
};

struct ctrump_loop_iv {
    int iv_level;               
    int incr;                   
    struct ctrump_var *var;     
    struct ctrump_pdg_node *reach_at_loop_entry; 
};

struct ctrump_loop_pointer_inc {
    int iv_level;               
    int incr;                   
    /* pointer_inc.var is array of this memory access */
};

struct ctrump_loop_array {
    struct ctrump_var *var;     
};

/* Subscript is valid when (lhs `cmp_op` rhs*rhs_coef + rhs_off) is True */
struct ctrump_loop_subscript_constraint {
    enum ctrump_expr_code cmp_op;
    struct ctrump_expr *lhs;
    int rhs_coef;
    int rhs_off;
    struct ctrump_expr *rhs;
};

enum ctrump_loop_index_code {
    CTRUMP_LOOP_INDEX_INDUCTIVE, 
    CTRUMP_LOOP_INDEX_INVARIANT, 
    CTRUMP_LOOP_INDEX_POINTER_INC 
};

struct ctrump_loop_index {
    enum ctrump_loop_index_code code; 
#define CTRUMP_LOOP_INDEX_NEGATIVE (1<<0)

    int flags;

    union {
        struct ctrump_loop_iv iv; 
        struct ctrump_loop_pointer_inc ptrinc; 
        struct ctrump_var *invariant; 
    } u;
};

struct ctrump_loop_subscript_record_member {
    const struct ctrump_symbol *member_name; 
    struct ctrump_texpr *record_type;        
};

struct ctrump_loop_subscript_record_member_terminal {
    const struct ctrump_symbol *member_name; 
    struct ctrump_texpr *record_type;        
    struct ctrump_texpr *load_type;          
};

struct ctrump_loop_subscript_load_record {
    struct ctrump_texpr *load_type; 
};

enum ctrump_loop_subscript_code {
    CTRUMP_LOOP_SUBSCRIPT_COEF_TERMINAL, 
    CTRUMP_LOOP_SUBSCRIPT_COEF_ARRAYSIZE, 
    CTRUMP_LOOP_SUBSCRIPT_COEF_CONSTANT,  
    CTRUMP_LOOP_SUBSCRIPT_RECORD_MEMBER,  
    CTRUMP_LOOP_SUBSCRIPT_RECORD_MEMBER_TERMINAL, 
    CTRUMP_LOOP_SUBSCRIPT_LOAD_RECORD,            
    CTRUMP_LOOP_SUBSCRIPT_COEF_SCALE              
};


struct ctrump_loop_subscript {
    int id;                     
    enum ctrump_loop_subscript_code code; 
    /* ex) a[i+x-5]; a+=4;
     *  offset = -5
     *  num_index = 3
     *   indicies[0] = iv:i
     *   indicies[1] = invariant:x
     *   indicies[2] = pointer_incr:4
     */

    int offset;                 
    int num_index;              
    struct ctrump_loop_index *indices; 
    union ctrump_loop_subscript_scale {
        /* a[i * pitch + j] 
         *  -> a[i (scale_array_coef=pitch)][j (terminal)]
         */
        struct ctrump_var *scale_array_coef; /* case CTRUMP_LOOP_SUBSCRIPT_COEF_SCALE */

        /* int a[10][20];
         * a[i][j];
         *  -> a[i (array_size_coef=20)][j (terminal)];
         *
         * int a[100];
         * a[i*10 + j];
         *  a[i (array_size_coef=10)][j (terminal)];
         */
        int array_size_coef;                 /* case CTRUMP_LOOP_SUBSCRIPT_COEF_(ARRAYSIZE|CONSTANT) */

        /* struct xyz {int x[3]; int y} st;
         * st[i].x[3];
         *  -> st[i (load_record = "xyz")][0 (field="x")]
         */
        struct ctrump_loop_subscript_load_record load_record; /* case CTRUMP_LOOP_SUBSCRIPT_LOAD_RECORD */
        struct ctrump_loop_subscript_record_member record_member; /* case CTRUMP_LOOP_SUBSCRIPT_RECORD_MEMBER */
        struct ctrump_loop_subscript_record_member_terminal record_member_terminal; /* case CTRUMP_LOOP_SUBSCRIPT_RECORD_MEMBER_TERMINAL */

        struct ctrump_texpr *load_type; /* case CTRUMP_LOOP_SUBSCRIPT_COEF_TERMINAL */
    } u;
};


CTRUMP_EXTDEF int
ctrump_loop_subscript_equal(const struct ctrump_loop_subscript *s1,
                            const struct ctrump_loop_subscript *s2);

CTRUMP_EXTDEF int
ctrump_loop_index_equal(const struct ctrump_loop_index *i1,
                        const struct ctrump_loop_index *i2);

CTRUMP_EXTDEF int
ctrump_loop_subscript_hash(const struct ctrump_loop_subscript *s);

struct ctrump_loop_memory_access {
    int id;                     
    int num_subscript;                        
    struct ctrump_loop_subscript *subscripts; 
    int num_constraint;                       
    struct ctrump_loop_subscript_constraint *constraints; 
    struct ctrump_loop_array array; 
    struct ctrump_stmt *at_stmt; 
    struct ctrump_expr *at_expr; 
};

struct ctrump_array_access {
    struct ctrump_expr *array;  
    int num_subscript;                   
    struct ctrump_subscript *subscripts; 
};

enum ctrump_random_access_code {
    CTRUMP_RANDOM_ACCESS_POINTER_NOT_INDUCTIVE, 
    CTRUMP_RANDOM_ACCESS_COMPLICATED_POINTER,   
    CTRUMP_RANDOM_ACCESS_ARRAY_NOT_INVARIANT,   
    CTRUMP_RANDOM_ACCESS_SUBSCRIPT_NOT_INDUCTIVE, 
    CTRUMP_RANDOM_ACCESS_COMPLICATED_ARRAY,       
    CTRUMP_RANDOM_ACCESS_MULTIPLE_SCALED_INDEX,   
    CTRUMP_RANDOM_ACCESS_COMPLICATED_SUBSCRIPT,   
    CTRUMP_RANDOM_ACCESS_INDEX_VAR_NOT_INDUCTIVE  
};

struct ctrump_random_access_multiple_scaled_index {
    struct ctrump_expr *index0;
    struct ctrump_expr *index1;
};

struct ctrump_random_access {
    enum ctrump_random_access_code code; 
    struct ctrump_stmt *access_at_stmt;  
    struct ctrump_expr *access_at_expr;  
    union {
        struct ctrump_array_access arr_not_invariant; /* case CTRUMP_RANDOM_ACCESS_ARRAY_NOT_INVARIANT */
        struct ctrump_array_access sub_not_inductive; /* case CTRUMP_RANDOM_ACCESS_SUBSCRIPT_NOT_INDUCTIVE */
        struct ctrump_var *index_var_not_inductive;   /* case CTRUMP_RANDOM_ACCESS_INDEX_VAR_NOT_INDUCTIVE */
        struct ctrump_array_access complicated_array; /* case CTRUMP_RANDOM_ACCESS_COMPLICATED_ARRAY */
        struct ctrump_random_access_multiple_scaled_index multiple_scaled_index; /* case CTRUMP_RANDOM_ACCESS_MULTIPLE_SCALED_INDEX */
        struct ctrump_expr *complicated_subscript; /* case CTRUMP_RANDOM_ACCESS_COMPLICATED_SUBSCRIPT */
    }u;
};

enum ctrump_loop_count_code {
    CTRUMP_LOOP_COUNT_CONSTANT, 
    CTRUMP_LOOP_COUNT_PREDICTABLE, 
    CTRUMP_LOOP_COUNT_UNPREDICTABLE 
};

struct ctrump_loop_count_pred_info {
    enum ctrump_expr_code cmp_op; 
    int incr;                     
    struct ctrump_var *inductive; 
    struct ctrump_pdg_node *iv_loop_entry_value; 
    struct ctrump_expr *bound;                   
};

struct ctrump_loop_exit {
    enum ctrump_loop_count_code code; 
    union {
        struct ctrump_loop_count_pred_info pred; /* case CTRUMP_LOOP_COUNT_PREDICTABLE */
        int count;                               /* case CTRUMP_LOOP_COUNT_CONSTANT */
    }u;
};

struct ctrump_loop_info {
    int id;
    int nest_level;             /* maxlevel + 1 */

    struct ctrump_loop_info_node *root; 
};

#include "ctrump/analyzer/deptest.h"

struct ctrump_loop_info_node {
    int id;

    struct ctrump_location loc; 
    struct ctrump_loop_depinfo depinfo; 
    int nest_level;
    int dfs_order;                        
    struct ctrump_loop_info_node *parent; 
    struct ctrump_loop_cfg_info *cfg_info; 
    int num_var;                
    ctrump_bitmap_t inductive_var;                
    ctrump_bitmap_t invariant_var;                
    ctrump_bitmap_t modified_and_live_after_loop; 
    ctrump_bitmap_t carry_dep;                    
    ctrump_bitmap_t modify;                       
    ctrump_bitmap_t use;                          
    int num_child;                           
    struct ctrump_loop_info_node **children; 
    struct ctrump_loop_exit exit_info;       
    int num_parallel_load;      
    int num_parallel_store;     
    int num_random_access;      
    int num_ordered_loadstore;  
    struct ctrump_loop_memory_access *parallel_loads; 
    struct ctrump_loop_memory_access *parallel_stores; 
    struct ctrump_ordered_memory_load_store_node *ordered_loadstore; /* vec [num_ordered_loadstore] */

    struct ctrump_random_access *random_accesses;      
    int num_reduc_op;                         
    struct ctrump_loop_reduction *reductions; 
};

struct ctrump_loop_reduction {
    enum ctrump_reductive_expr_code op; 
    struct ctrump_var *var;             
    struct ctrump_stmt *at;             
};

enum ctrump_loop_code {
    CTRUMP_LOOP_UNANALYZED,     
    CTRUMP_LOOP_COMPLICATED,    
    CTRUMP_LOOP,                
};

struct ctrump_loop_cfg_info {
    int id;
    enum ctrump_loop_code code; 
    struct ctrump_stmt *loop_stmt; 
    struct ctrump_bb *loop_pred; 
    struct ctrump_bb *cond_bb;   
    struct ctrump_bb *body_start_bb; 
    struct ctrump_bb *break_bb;      
    struct ctrump_expr *exit_cond; 
    union {
        struct ctrump_complicated_loop complicated; /* case CTRUMP_LOOP_COMPLICATED */
        struct ctrump_loop_info_node *loop_info_node; /* case CTRUMP_LOOP */
    } u;
};

struct ctrump_abi;
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);

#ifdef __cplusplus
}
#endif
#endif

---