python/ctrump/memoptree.py

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.

'''
メモリアクセス認識、最適化

CSEとloop invariant code motionを行う

<h3>CSE</h3>
<code>
for (i=0; i<n; i++) {
    x[i] = a[i]
    y[i] = a[i+1]    
}
</code>
のように、ひとつの配列に対する複数のアクセスがあった場合に、それをひとつにまとめる。


<h3>loop invariant code motion</h3>
<code>
for (i=0; i<n; i++) {
    for (j=0; j<n; j++) {
        x[i][j] = y[i];
    }
}
</code>
のように、ループ内で不変なアクセスがあった場合、それをループ外へ移動する
'''


import ctrump
import copy

__all__ = ["MemoryOp", "MemoryOpTree", "loop_tree_to_memop_tree", "PtrIncVarEnv"]

class PtrIncVarEnv:
    def __init__(self):
        self.incr_table = {}
        self.array_table = {}

    def append_ptrinc(self, var, incr):
        if not var in self.array_table:
            self.array_table[var] = True

        if not incr in self.incr_table:
            self.incr_table[incr] = True

class MemAccessKey:
    '''メモリアクセスを辞書引きするときに使うキー
添字とインデクスからハッシュ値、同値性を求める'''
    def __init__(self, array, subscripts, load_store):
        name_hash = hash(array.var.name)

        subscript_hash = 0

        for i in subscripts:
            subscript_hash += ctrump.loop_subscript_hash(i)

        self.array_name = array.var.name
        self.subscripts = subscripts
        self.load_store = load_store

        self.hash = int((name_hash * subscript_hash + load_store)%0x7fffffff)

    def __hash__(self):
        return self.hash

    def __eq__(self, rhs):
        if rhs.array_name != self.array_name:
            return False
        if rhs.load_store != self.load_store:
            return False

        rs = rhs.subscripts
        ls = self.subscripts

        l = len(ls)
        if len(rs) != l:
            return False

        for i in range(0,l):
            if not ctrump.loop_subscript_equal(rs[i], ls[i]):
                return False

        return True

class CSETableNode:
    def __init__(self, node_list):
        self.node_list = node_list

class MemoryOpOptimizer:
    def __init__(self):
        self.changed = False
        self.cse_table = {}
        self.level_table = {}
        self.invariants = []
        self.neighbor_table = {}

    def change(self):
        self.changed = True

    def loop_invariant_motion_0(self, tree):
        tree_level = tree.loop_node.nest_level
        self.level_table[tree_level] = tree

        motion_ops = []
        for i in tree.ops:
            level = i.max_iv_level()

            if level != tree_level:
                motion_ops.append((i, level))
                i.removed = True
                self.changed = True

        tree.ops = filter(lambda x:not x.removed, tree.ops)

        for (i,level) in motion_ops:
            i.removed = False
            if (level == None) or (level < self.min_level):
                self.invariants.append(i)
                i.loop_node = None
            else:
                self.level_table[level].ops.append(i)
                i.loop_node = self.level_table[level].loop_node

        for i in tree.children:
            self.loop_invariant_motion_0(i)

    def loop_invariant_motion(self, tree):
        self.min_level = tree.loop_node.nest_level
        self.loop_invariant_motion_0(tree)

    def do_cse(self, prev_op, op):
        changed = True
        op.removed = True

        for i in op.children:
            i.chain = prev_op
            prev_op.children.append(i)

        new_offset_list = []

        l = len(op.offset_list)

        for i in range(0, l):
            (prev_off, prev_min, prev_max) = prev_op.offset_list[i]
            (op_off, op_min, op_max) = op.offset_list[i]

            if op_min < prev_min:
                prev_min = op_min
            if op_max > prev_max:
                prev_max = op_max

            new_offset_list.append((prev_off, prev_min, prev_max))

        prev_op.offset_list = new_offset_list

        prev_op.update_expr_list = prev_op.update_expr_list + op.update_expr_list

    def merge_neighbor_0(self, cur_op):
        table = self.neighbor_table
        array = cur_op.array
        num_sub = len(cur_op.subscripts)
        sub = cur_op.subscripts

        load_data_sub = cur_op.load_data_sub_offset()
        sub_sub = sub[0:load_data_sub]

        key = MemAccessKey(array, sub_sub, cur_op.load_store)

        if key in table:
            cse_node = table[key]

            found = False

            for prev_op in cse_node.node_list:
                if id(prev_op.chain) != id(cur_op.chain):
                    continue

                prev_last_sub = prev_op.subscripts[load_data_sub]
                cur_last_sub = cur_op.subscripts[load_data_sub]

                prev_indices = prev_last_sub.indices
                cur_indices = cur_last_sub.indices

                if len(prev_indices) != len(cur_indices):
                    continue

                # fixme miv
                if len(prev_indices) == 0:
                    self.changed = True
                    self.do_cse(prev_op, cur_op)

                    found = True
                elif len(prev_indices) == 1:
                    if ctrump.loop_index_equal(prev_indices[0], cur_indices[0]):
                        self.changed = True
                        self.do_cse(prev_op, cur_op)
                        found = True

            if not found:
                cse_node.node_list.append(cur_op)

        else:
            table[key] = CSETableNode([cur_op])


    # merge some memory reference 
    # ex) a[i] + a[i+1]
    def merge_neighbor(self, tree):
        for i in tree.ops:
            self.merge_neighbor_0(i)

        tree.ops = filter(lambda x:not x.removed, tree.ops)

        for i in tree.children:
            self.merge_neighbor(i)

class MemoryOp:
    ACCESS_SEQUENTIAL = 0
    ACCESS_RANDOM = 1
#    ACCESS_CONSTANT = 2
    ACCESS_NULL = 3
    ACCESS_CALC_ADDR = 4

    STORE = 0
    LOAD = 1

    COMBINE_OFFSET = 0
    COMBINE_TAG = 1

    def __init__(self, chain, at_expr, array, subscripts, load_store, loop_node):

        self.at_expr = at_expr

        off = []
        for i in subscripts:
            if i.code == ctrump.LOOP_SUBSCRIPT_RECORD_MEMBER_TERMINAL:
                cur_off = i.member_name
                cur_min = 0
                cur_max = 0
            else:
                cur_off = i.offset
                cur_min = cur_off
                cur_max = cur_off

            off.append((cur_off,cur_min,cur_max))

        self.offset_list = off
        self.update_expr_list = [(off,at_expr)]
        self.array = array
        self.subscripts = subscripts
        self.chain = chain
        if chain:
            chain.children.append(self)
        self.load_store = load_store
        self.children = []
        self.removed = False
        self.loop_node = loop_node

        self.key = MemAccessKey(array, subscripts, load_store)

    def __hash__(self):
        if self.chain:
            return int((hash(self.key) + hash(self.chain))%0x7fffffff)
        else:
            return hash(self.key)
    def __eq__(self, rhs):
        return (self.key == rhs.key) and (self.chain == rhs.chain)


    def __repr__(self):
        ret = str(self.array.var.name)
        ret += ctrump.format_loop_subscripts(self.subscripts)
        for (off,min,max) in self.offset_list:
            ret += "(%d,%d)"%(min, max)
        if self.chain:
            ret += ' - (chain = %s)'%self.chain
        return ret

    def access_data_type(self):
        sub = self.subscripts
        l = len(sub)

        if l == 0:
            raise Exception('subscript should terminal')

        if sub[-1].code == ctrump.LOOP_SUBSCRIPT_COEF_TERMINAL:
            return sub[-1].load_type
        elif sub[-1].code == ctrump.LOOP_SUBSCRIPT_RECORD_MEMBER_TERMINAL:
            return sub[-1].load_type
        raise Exception("subscript should terminal '%s'"%(ctrump.loop_subscript_code_string_table[sub[-1].code]))

    def load_data_type(self):
        sub = self.subscripts[self.load_data_sub_offset()]

        if sub.code == ctrump.LOOP_SUBSCRIPT_COEF_TERMINAL:
            return sub.load_type
        elif sub.code == ctrump.LOOP_SUBSCRIPT_RECORD_MEMBER_TERMINAL:
            return sub.record_type
        elif sub.code == ctrump.LOOP_SUBSCRIPT_LOAD_RECORD:
            return sub.load_type
        raise Exception("subscript should terminal '%s'"%(ctrump.loop_subscript_code_string_table[sub[-1].code]))

    def load_data_range(self):
        off = self.load_data_sub_offset()
        (o, min, max) = self.offset_list[off]
        return (min,max)

    def load_data_sub_offset(self):
        sub = self.subscripts
        l = len(sub)

        if l == 0:
            raise Exception('subscript should terminal')

        if l >= 2:
            if sub[-2].code == ctrump.LOOP_SUBSCRIPT_LOAD_RECORD:
                return l-2

        return l-1


    def max_iv_level(self):
        max_level = None
        for i in self.subscripts:
            for j in i.indices:
                if (j.code == ctrump.LOOP_INDEX_INDUCTIVE or
                    j.code == ctrump.LOOP_INDEX_POINTER_INC):
                    if j.iv_level > max_level:
                        max_level = j.iv_level
        if self.chain:
            chain_level = self.chain.max_iv_level()
            if chain_level > max_level:
                max_level = chain_level

        return max_level

    def extract_iv(self, ptrinc_env):
        iv_list = []

        sub = self.subscripts
        for i in sub:
            for j in i.indices:
                if j.code == ctrump.LOOP_INDEX_INDUCTIVE:
                    iv_list.append(j)
                elif j.code == ctrump.LOOP_INDEX_POINTER_INC:
                    ptrinc_env.append_ptrinc(self.array, j.incr)

        return iv_list

    def gen_name(self):
        name = str(self.array.var.name)
        for i in self.subscripts:
            if i.code == ctrump.LOOP_SUBSCRIPT_RECORD_MEMBER:
                name += '_%s'%i.member_name
            elif i.code == ctrump.LOOP_SUBSCRIPT_RECORD_MEMBER_TERMINAL:
                name += '_%s'%i.member_name

            for j in i.indices:
                if j.code == ctrump.LOOP_INDEX_INDUCTIVE:
                    name += "_%s"%str(j.var.name)

        return name

    def is_partial_store(self):
        if self.load_store != self.STORE:
            return False

        sub_off = self.load_data_sub_offset()
        if sub_off != len(self.subscripts)-1:
            return True

        (range_min, range_max) = self.load_data_range()

        if range_min != 0 and range_max != 0:
            return True

        if len(self.subscripts) == 0:
            return False # ??

        sub = self.subscripts[-1]
        if sub.code != ctrump.LOOP_SUBSCRIPT_COEF_TERMINAL:
            return True

        if len(sub.indices) != 1:
            return True # fixme miv

        if (sub.indices[0].code == ctrump.LOOP_INDEX_INDUCTIVE or
            sub.indices[0].code == ctrump.LOOP_INDEX_POINTER_INC):
            if sub.indices[0].incr == 1:
                return False

        return True
            

class MemoryOpTree:
    def __init__(self, loop_node, ops, children):
        self.loop_node = loop_node
        self.ops = ops
        self.children = children

    def __repr__(self):
        ret = "ops = \n" + str(self.ops) + "\n"
        ret += "children = \n" + str(self.children) + "\n"
        return ret

    def get_depth(self):
        max_depth = 0
        for i in self.children:
            d = i.get_depth()
            if d > max_depth:
                max_depth = d
        return max_depth + 1

    def optimize(self):
        invariants = []
        while True:
            optimizer = MemoryOpOptimizer()

            for i in invariants:
                optimizer.merge_neighbor_0(i)
            invariants = filter(lambda x:not x.removed, invariants)

            optimizer.merge_neighbor(self)
            optimizer.loop_invariant_motion(self)

            invariants += optimizer.invariants

            if not optimizer.changed:
                break

        return invariants

class MemoryOperation:
    def __init__(self, tree, invariants):
        self.tree = tree
        self.invariants = invariants

    def optimize(self):
        invariants = self.tree.optimize()
        self.invariants += invariants

def loop_tree_to_memop_tree_0(loop_tree):
    table = {}

    cur_level = loop_tree.nest_level

    loads = copy.copy(loop_tree.parallel_loads)
    stores = copy.copy(loop_tree.parallel_stores)

    ops = []
    children = []

    for i in loop_tree.children:
        n = loop_tree_to_memop_tree_0(i)
        children.append(n)

    load_store = loads 

    def filter_single_op(i, load_store):
        num_subscript = i.num_subscript
        prev_sub_n = 0
        chain = None

        for j in range(0, num_subscript):
            sub = i.subscripts[j]
            if (sub.code == ctrump.LOOP_SUBSCRIPT_RECORD_MEMBER_TERMINAL or
                sub.code == ctrump.LOOP_SUBSCRIPT_COEF_TERMINAL):
                cur_subscripts = i.subscripts[prev_sub_n:j+1]
                if j != (num_subscript-1):
                    memop = MemoryOp.LOAD
                else:
                    memop = load_store

                replace_expr = None
                if j == num_subscript-1:
                    replace_expr = i.at_expr

                cur_op = MemoryOp(chain, replace_expr, i.array, cur_subscripts, memop, loop_tree)
                ops.append(cur_op)

                chain = cur_op
                prev_sub_n = j+1

        if prev_sub_n != num_subscript:
            raise NotImplementedError('non terminal memory operation')

    for i in loads:
        filter_single_op(i, MemoryOp.LOAD)
    for i in stores:
        filter_single_op(i, MemoryOp.STORE)

    return MemoryOpTree(loop_tree, ops, children)

def loop_tree_to_memop_tree(loop_tree):
    return MemoryOperation(loop_tree_to_memop_tree_0(loop_tree), [])

---