
import json
from dominanceFrontier import *
from dominatorTree import *
from dominators import find_dominators
from solutions.utils.form_blocks import form_blocks
from solutions.utils import cfg
import sys
import os

dir_path = os.path.dirname(os.path.realpath(__file__))
sys.path.insert(1, dir_path + '/../../../')

PHI_INSTRUCTION = {
    'dest': None,
    'op': 'phi',
    'labels': [],
    'args': [],
}


def get_block_variables(blocks):
    block_variables = dict()
    for name, instructions in blocks.items():
        block_variables[name] = get_variables_of_block(instructions)

    return block_variables


def to_ssa(function):
    blocks = cfg.block_map(form_blocks(function['instrs']))
    cfg.add_terminators(blocks)

    precs, succs = cfg.edges(blocks)

    block_variables = get_block_variables(blocks)
    variable_blocks = get_variable_blocks(block_variables)

    blocks_dominance_frontiers = get_dominance_frontiers(function)

    dominators = find_dominators(function)
    dominator_tree = create_dominator_tree(
        dominators, list(dominators.keys())[0])

    blocks = add_phi_to_blocks(
        blocks, variable_blocks, blocks_dominance_frontiers)

    name_stack = dict()

    for variable in variable_blocks.keys():
        name_stack[variable] = []

    rename(list(blocks.keys())[0], blocks, succs, name_stack, dominator_tree)

    return blocks


def rename(block_name, blocks, succs, name_stack, dominator_tree, start_name_counter=1):
    block_succs = succs[block_name]
    curr_name_stack = dict()

    for instruction in blocks[block_name]:
        if 'op' in instruction and instruction['op'] != 'phi':
            if 'args' in instruction:
                new_args = []
                for arg in instruction['args']:
                    new_args.append(name_stack[arg][-1])
                instruction['args'] = new_args

            if 'dest' in instruction:
                new_name = instruction['dest'] + '.' + str(start_name_counter)
                start_name_counter += 1
                name_stack[instruction['dest']].append(new_name)
                if instruction['dest'] in curr_name_stack.keys():
                    curr_name_stack[instruction['dest']].append(new_name)
                else:
                    curr_name_stack[instruction['dest']] = [new_name]
                instruction['dest'] = new_name

    for succ in block_succs:
        for instruction in blocks[succ]:
            if 'op' in instruction and instruction['op'] == 'phi':
                if len(name_stack[instruction['dest']]) != 0:
                    instruction['labels'].append(block_name)
                    instruction['args'].append(
                        name_stack[instruction['dest']][-1])

    for block in dominator_tree[block_name]:
        rename(block, blocks, succs, name_stack,
               dominator_tree, start_name_counter)

    for var, new_names in curr_name_stack.items():
        for new_name in new_names:
            name_stack[var].remove(new_name)


def get_phi_of_variable(variable_name):
    phi_instr = PHI_INSTRUCTION
    phi_instr['dest'] = variable_name
    return phi_instr


def add_phi_to_blocks(blocks, variable_blocks, blocks_dominance_frontiers):
    for variable_name, variable_blocks_names in variable_blocks.items():
        for block_name in variable_blocks_names:
            for dominance_frontier_blocks_name in blocks_dominance_frontiers[block_name]:
                phi = get_phi_of_variable(variable_name)
                if phi not in blocks[dominance_frontier_blocks_name]:
                    blocks[dominance_frontier_blocks_name].insert(
                        0, phi)
                if dominance_frontier_blocks_name not in variable_blocks_names:
                    variable_blocks_names.append(
                        dominance_frontier_blocks_name)
    return blocks


def get_variable_blocks(block_variables):
    variable_blocks = dict()
    for name, variables in block_variables.items():
        for variable in variables:
            if variable not in variable_blocks.keys():
                variable_blocks[variable] = [name]
            elif name not in variable_blocks[variable]:
                variable_blocks[variable].append(name)

    return variable_blocks


def get_variables_of_block(instructions):
    dest_vars = {i['dest'] for i in instructions if 'dest' in i}
    args_collection = [i['args'] for i in instructions if 'args' in i]

    args_vars = set()
    for args in args_collection:
        args_vars = args_vars.union(args)

    return args_vars.union(dest_vars)


if __name__ == '__main__':
    code = json.load(sys.stdin)
    for function in code['functions']:
        function_ssa = to_ssa(function)
        for label, instructions in function_ssa.items():
            print(label)
            print(instructions)
            print('==============')


import json
from dominanceFrontier import *
from dominatorTree import *
from dominators import find_dominators
from solutions.utils.form_blocks import form_blocks
from solutions.utils import cfg
import sys
import os

dir_path = os.path.dirname(os.path.realpath(__file__))
sys.path.insert(1, dir_path + '/../../../')

PHI_INSTRUCTION = {
    'dest': None,
    'op': 'phi',
    'labels': [],
    'args': [],
}


def get_block_variables(blocks):
    block_variables = dict()
    for name, instructions in blocks.items():
        block_variables[name] = get_variables_of_block(instructions)

    return block_variables


def to_ssa(function):
    blocks = cfg.block_map(form_blocks(function['instrs']))
    cfg.add_terminators(blocks)

    precs, succs = cfg.edges(blocks)

    block_variables = get_block_variables(blocks)
    variable_blocks = get_variable_blocks(block_variables)

    blocks_dominance_frontiers = get_dominance_frontiers(function)

    dominators = find_dominators(function)
    dominator_tree = create_dominator_tree(
        dominators, list(dominators.keys())[0])

    blocks = add_phi_to_blocks(
        blocks, variable_blocks, blocks_dominance_frontiers)

    name_stack = dict()

    for variable in variable_blocks.keys():
        name_stack[variable] = []

    rename(list(blocks.keys())[0], blocks, succs, name_stack, dominator_tree)

    return blocks


def rename(block_name, blocks, succs, name_stack, dominator_tree, start_name_counter=1):
    block_succs = succs[block_name]
    curr_name_stack = dict()

    for instruction in blocks[block_name]:
        if 'op' in instruction and instruction['op'] != 'phi':
            if 'args' in instruction:
                new_args = []
                for arg in instruction['args']:
                    new_args.append(name_stack[arg][-1])
                instruction['args'] = new_args

            if 'dest' in instruction:
                new_name = instruction['dest'] + '.' + str(start_name_counter)
                start_name_counter += 1
                name_stack[instruction['dest']].append(new_name)
                if instruction['dest'] in curr_name_stack.keys():
                    curr_name_stack[instruction['dest']].append(new_name)
                else:
                    curr_name_stack[instruction['dest']] = [new_name]
                instruction['dest'] = new_name

    for succ in block_succs:
        for instruction in blocks[succ]:
            if 'op' in instruction and instruction['op'] == 'phi':
                if len(name_stack[instruction['dest']]) != 0:
                    instruction['labels'].append(block_name)
                    instruction['args'].append(
                        name_stack[instruction['dest']][-1])

    for block in dominator_tree[block_name]:
        rename(block, blocks, succs, name_stack,
               dominator_tree, start_name_counter)

    for var, new_names in curr_name_stack.items():
        for new_name in new_names:
            name_stack[var].remove(new_name)


def get_phi_of_variable(variable_name):
    phi_instr = PHI_INSTRUCTION
    phi_instr['dest'] = variable_name
    return phi_instr


def add_phi_to_blocks(blocks, variable_blocks, blocks_dominance_frontiers):
    for variable_name, variable_blocks_names in variable_blocks.items():
        for block_name in variable_blocks_names:
            for dominance_frontier_blocks_name in blocks_dominance_frontiers[block_name]:
                phi = get_phi_of_variable(variable_name)
                if phi not in blocks[dominance_frontier_blocks_name]:
                    blocks[dominance_frontier_blocks_name].insert(
                        0, phi)
                if dominance_frontier_blocks_name not in variable_blocks_names:
                    variable_blocks_names.append(
                        dominance_frontier_blocks_name)
    return blocks


def get_variable_blocks(block_variables):
    variable_blocks = dict()
    for name, variables in block_variables.items():
        for variable in variables:
            if variable not in variable_blocks.keys():
                variable_blocks[variable] = [name]
            elif name not in variable_blocks[variable]:
                variable_blocks[variable].append(name)

    return variable_blocks


def get_variables_of_block(instructions):
    dest_vars = {i['dest'] for i in instructions if 'dest' in i}
    args_collection = [i['args'] for i in instructions if 'args' in i]

    args_vars = set()
    for args in args_collection:
        args_vars = args_vars.union(args)

    return args_vars.union(dest_vars)


if __name__ == '__main__':
    code = json.load(sys.stdin)
    for function in code['functions']:
        function_ssa = to_ssa(function)
        for label, instructions in function_ssa.items():
            print(label)
            print(instructions)
            print('==============')
