/* $Id$ Copyright 1989-2016 MINES ParisTech This file is part of PIPS. PIPS is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or any later version. PIPS is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with PIPS. If not, see . */ #ifdef HAVE_CONFIG_H #include "pips_config.h" #endif #include #include #include "genC.h" #include "misc.h" #include "freia.h" #include "freia_spoc.h" #include "linear.h" #include "ri.h" #include "effects.h" #include "ri-util.h" #include "effects-util.h" #include "properties.h" #include "freia_spoc_private.h" #include "hwac.h" // help reduce code size: #define T true #define F false static void comment(string_buffer code, spoc_hardware_type hw, dagvtx v, int stage, int side, bool flip) { sb_cat(code, " // ", what_operation(hw), " ", i2a(dagvtx_number(v)), " ", dagvtx_operation(v)); sb_cat(code, " stage ", i2a(stage)); if (hw!=spoc_type_alu) sb_cat(code, " side ", i2a(side)); if (hw==spoc_type_alu && flip) sb_cat(code, " flipped"); sb_cat(code, "\n"); } /********************************************************* ALU CONFIGURATION */ // value to set operation, in same order as enum declaration static const spoc_alu_op_t ALU_OP[] = { { alu_unused, alu_unused, NULL, F, F, F }, // ADD { alu_add, alu_add, "SPOC_ALU_ADD_IN0_IN1", F, T, T }, { alu_add_0cst, alu_add_1cst, "SPOC_ALU_ADD_IN0_CONST", T, T, F }, { alu_add_1cst, alu_add_0cst, "SPOC_ALU_ADD_IN1_CONST", T, F, T }, // ADDSAT { alu_addsat, alu_addsat, "SPOC_ALU_ADDSAT_IN0_IN1", F, T, T }, { alu_addsat_0cst, alu_addsat_1cst, "SPOC_ALU_ADDSAT_IN0_CONST", T, T, F }, { alu_addsat_1cst, alu_addsat_0cst, "SPOC_ALU_ADDSAT_IN1_CONST", T, F, T }, // SUB { alu_sub_01, alu_sub_10, "SPOC_ALU_SUB_IN0_IN1", F, T, T }, { alu_sub_10, alu_sub_01, "SPOC_ALU_SUB_IN1_IN0", F, T, T }, { alu_sub_0cst, alu_sub_1cst, "SPOC_ALU_SUB_IN0_CONST", T, T, F }, { alu_sub_1cst, alu_sub_0cst, "SPOC_ALU_SUB_IN1_CONST", T, F, T }, { alu_sub_cst0, alu_sub_cst1, "SPOC_ALU_SUB_CONST_IN0", T, T, F }, { alu_sub_cst1, alu_sub_cst0, "SPOC_ALU_SUB_CONST_IN1", T, F, T }, // SUBSAT { alu_subsat_01, alu_subsat_10, "SPOC_ALU_SUBSAT_IN0_IN1", F, T, T }, { alu_subsat_10, alu_subsat_01, "SPOC_ALU_SUBSAT_IN1_IN0", F, T, T }, { alu_subsat_0cst, alu_subsat_1cst, "SPOC_ALU_SUBSAT_IN0_CONST", T, T, F }, { alu_subsat_1cst, alu_subsat_0cst, "SPOC_ALU_SUBSAT_IN1_CONST", T, F, T }, { alu_subsat_cst0, alu_subsat_cst1, "SPOC_ALU_SUBSAT_CONST_IN0", T, T, F }, { alu_subsat_cst1, alu_subsat_cst0, "SPOC_ALU_SUBSAT_CONST_IN1", T, F, T }, // ABSSUB { alu_abssub, alu_abssub, "SPOC_ALU_ABSSUB_IN0_IN1", F, T, T }, { alu_abssub_0cst, alu_abssub_1cst, "SPOC_ALU_ABSSUB_IN0_CONST", T, T, F }, { alu_abssub_1cst, alu_abssub_0cst, "SPOC_ALU_ABSSUB_IN1_CONST", T, F, T }, // MUL { alu_mul, alu_mul, "SPOC_ALU_MUL_IN0_IN1", F, T, T }, { alu_mul_0cst, alu_mul_1cst, "SPOC_ALU_MUL_IN0_CONST", T, T, F }, { alu_mul_1cst, alu_mul_0cst, "SPOC_ALU_MUL_IN1_CONST", T, F, T }, // DIV { alu_div_01, alu_div_10, "SPOC_ALU_DIV_IN0_IN1", F, T, T }, { alu_div_10, alu_div_01, "SPOC_ALU_DIV_IN1_IN0", F, T, T }, { alu_div_0cst, alu_div_1cst, "SPOC_ALU_DIV_IN0_CONST", T, T, F }, { alu_div_1cst, alu_div_0cst, "SPOC_ALU_DIV_IN1_CONST", T, F, T }, { alu_div_cst0, alu_div_cst1, "SPOC_ALU_DIV_CONST_IN0", T, T, F }, { alu_div_cst1, alu_div_cst0, "SPOC_ALU_DIV_CONST_IN1", T, F, T }, // LOG2 { alu_log2_0, alu_log2_1, "SPOC_ALU_LOG2_IN0", F, T, F }, { alu_log2_1, alu_log2_0, "SPOC_ALU_LOG2_IN1", F, F, T }, // INF { alu_inf_01, alu_inf_01, "SPOC_ALU_INF_IN0_IN1", F, T, T }, { alu_inf_0cst, alu_inf_1cst, "SPOC_ALU_INF_IN0_CONST", T, T, F }, { alu_inf_1cst, alu_inf_0cst, "SPOC_ALU_INF_IN1_CONST", T, F, T }, // SUP { alu_sup_01, alu_sup_01, "SPOC_ALU_SUP_IN0_IN1", F, T, T }, { alu_sup_0cst, alu_sup_1cst, "SPOC_ALU_SUP_IN0_CONST", T, T, F }, { alu_sup_1cst, alu_sup_0cst, "SPOC_ALU_SUP_IN1_CONST", T, F, T }, // AND { alu_and, alu_and, "SPOC_ALU_AND_IN0_IN1", F, T, T }, { alu_and_0cst, alu_and_1cst, "SPOC_ALU_AND_IN0_CONST", T, T, F }, { alu_and_1cst, alu_and_0cst, "SPOC_ALU_AND_IN1_CONST", T, F, T }, // OR { alu_or, alu_or, "SPOC_ALU_OR_IN0_IN1", F, T, T }, { alu_or_0cst, alu_or_1cst, "SPOC_ALU_OR_IN0_CONST", T, T, F }, { alu_or_1cst, alu_or_0cst, "SPOC_ALU_OR_IN1_CONST", T, F, T }, // XOR { alu_xor, alu_xor, "SPOC_ALU_XOR_IN0_IN1", F, T, T }, { alu_xor_0cst, alu_xor_1cst, "SPOC_ALU_XOR_IN0_CONST", T, T, F }, { alu_xor_1cst, alu_xor_0cst, "SPOC_ALU_XOR_IN1_CONST", T, F, T }, // NOT { alu_not_0, alu_not_1, "SPOC_ALU_NOT_IN0", F, T, F }, { alu_not_1, alu_not_0, "SPOC_ALU_NOT_IN1", F, F, T }, // MISC { alu_copy_cst, alu_copy_cst, "SPOC_ALU_COPY_CONST", T, F, F }, { alu_mask_0, alu_mask_1, "SPOC_ALU_MASK_IN0_IN1", F, T, T }, { alu_mask_1, alu_mask_0, "SPOC_ALU_MASK_IN1_IN0", F, T, T }, // hmmm, the input images are exchanged from AIPO to SPOC? { alu_repcst_0, alu_repcst_1, "SPOC_ALU_REPLACE_IN1_IN0_CONST", T, T, T }, { alu_repcst_1, alu_repcst_0, "SPOC_ALU_REPLACE_IN0_IN1_CONST", T, T, T } // and so on? }; static const spoc_alu_op_t *get_spoc_alu_conf(spoc_alu_t alu) { return &ALU_OP[alu]; } /* generate a configuration for the ALU hardware component. */ static void spoc_alu_conf (spoc_alu_t alu, string_buffer body, __attribute__ ((__unused__)) string_buffer tail, int stage, bool flip, dagvtx orig, hash_table hp) { if (alu!=alu_unused) // should not be called? copy? { if (flip) // only flip if distinct { spoc_alu_t flipped_alu = get_spoc_alu_conf(alu)->flipped; if (alu!=flipped_alu) alu = flipped_alu; else flip = false; } const spoc_alu_op_t * aluop = get_spoc_alu_conf(alu); message_assert("alu operation found", alu==aluop->op); string s_stage = strdup(i2a(stage)); comment(body, spoc_type_alu, orig, stage, -1, flip); sb_cat(body, " si.alu[", s_stage, "][0].op = ", aluop->setting, ";\n"); if (aluop->use_cst) { expression arg = EXPRESSION(CAR(freia_get_vertex_params(orig))); string s_var = hash_get(hp, arg); // res += "spocinstr.alu[%stage][0].constant = " + var + ";\n"; sb_cat(body, " sp.alu[", s_stage, "][0].constant = ", s_var, ";\n"); } free(s_stage); } } /***************************************** POC & TH & MEASURE CONFIGURATIONS */ /* generate a configuration for a POC (morpho) hardware component. */ static void spoc_poc_conf (spoc_poc_t poc, string_buffer body, __attribute__ ((__unused__)) string_buffer tail, int stage, int side, dagvtx orig, hash_table hp) // expression -> parameter name { if (poc.op!=spoc_poc_unused) // should not be called? { string s_stag = strdup(i2a(stage)), s_side = strdup(i2a(side)); // only one argument is expected, the kernel expression arg = EXPRESSION(CAR(freia_get_vertex_params(orig))); string s_var = hash_get(hp, arg); // spocinstr.poc[0][0].op = SPOC_POC_ERODE; comment(body, spoc_type_poc, orig, stage, side, false); sb_cat(body, " si.poc[", s_stag, "][", s_side, "].op = "); if (poc.op==spoc_poc_erode) sb_cat(body, "SPOC_POC_ERODE;\n"); else if (poc.op==spoc_poc_dilate) sb_cat(body, "SPOC_POC_DILATE;\n"); else if (poc.op==spoc_poc_conv) sb_cat(body, "SPOC_POC_CONV;\n"); else pips_internal_error("unexpected poc operation %d", poc.op); // spocinstr.poc[0][0].grid = SPOC_POC_8_CONNEX; sb_cat(body, " si.poc[", s_stag, "][", s_side, "].grid = "); if (poc.connectivity==6) sb_cat(body, "SPOC_POC_6_CONNEX;\n"); else if (poc.connectivity==8) sb_cat(body, "SPOC_POC_8_CONNEX;\n"); else pips_internal_error("unexpected poc connectivity %d", poc.connectivity); // for(i=0 ; i<9 ; i++) spocparam.poc[0][0].kernel[i] = kernel[i]; sb_cat(body, " for(i=0 ; i<9 ; i++)\n" " sp.poc[", s_stag, "][", s_side, "].kernel[i] = ", s_var, "[i];\n"); free(s_stag); free(s_side); } } /* generate a configuration for a threshold component. */ static void spoc_th_conf (string_buffer body, __attribute__ ((__unused__)) string_buffer tail, int stage, int side, dagvtx orig, hash_table hp) { list largs = freia_get_vertex_params(orig); pips_assert("3 arguments to threshold", gen_length(largs)==3); expression e_inf = EXPRESSION(CAR(largs)), e_sup = EXPRESSION(CAR(CDR(largs))), e_bin = EXPRESSION(CAR(CDR(CDR(largs)))); string s_inf = hash_get(hp, e_inf), s_sup = hash_get(hp, e_sup), s_bin = hash_get(hp, e_bin), s_stag = strdup(i2a(stage)), s_side = strdup(i2a(side)); // spocinstr.th[0][0].op = // (binarize==true) ? SPOC_TH_BINARIZE : SPOC_TH_NO_BINARIZE; // spocparam.th[0][0].boundmin = boundinf; // spocparam.th[0][0].boundmax = boundsup; comment(body, spoc_type_thr, orig, stage, side, false); sb_cat(body, " si.th[", s_stag, "][", s_side, "].op = ", s_bin, "? SPOC_TH_BINARIZE : SPOC_TH_NO_BINARIZE;\n", " sp.th[", s_stag, "][", s_side, "].boundmin = ", s_inf, ";\n", " sp.th[", s_stag, "][", s_side, "].boundmax = ", s_sup, ";\n"); free(s_stag); free(s_side); } static int spoc_measure_n_params(spoc_measure_t measure) { switch (measure) { case measure_none: return 0; case measure_max_coord: case measure_min_coord: return 3; default: return 1; } } /* there is no real configuration for the measures, * the issue is just to fetch them. */ static void spoc_measure_conf (spoc_measure_t measure, __attribute__ ((__unused__)) string_buffer body, string_buffer tail, int stage, int side, dagvtx orig, hash_table hp) { int n = spoc_measure_n_params(measure); if (n==0) return; pips_assert("1 to 3 parameters", n>=1 && n<=3); string s_stage = strdup(i2a(stage)), s_side = strdup(i2a(side)), reduc = strdup(cat("reduc.measure[", s_stage, "][", s_side, "].")); list largs = freia_get_vertex_params(orig); pips_assert("argument list length is okay", (int) gen_length(largs)==n); string v_1 = hash_get(hp, EXPRESSION(CAR(largs))), v_2 = NULL, v_3 = NULL; if (n>=2) v_2 = hash_get(hp, EXPRESSION(CAR(CDR(largs)))); if (n>=3) v_3 = hash_get(hp, EXPRESSION(CAR(CDR(CDR(largs))))); sb_cat(tail, "\n"); comment(tail, spoc_type_mes, orig, stage, side, false); switch (measure) { case measure_max: case measure_min: case measure_max_coord: case measure_min_coord: sb_cat(tail, " *", v_1, " = (int32_t) ", reduc, measure==measure_min||measure==measure_min_coord? "minimum": "maximum", ";\n"); if (n>1) { sb_cat(tail, " *", v_2, " = (uint32_t) ", reduc, measure==measure_min||measure==measure_min_coord? "min": "max", "_coord_x;\n", " *", v_3, " = (uint32_t) ", reduc, measure==measure_min||measure==measure_min_coord? "min": "max", "_coord_y;\n"); } break; case measure_vol: sb_cat(tail, " *", v_1, " = (int32_t) ", reduc, "volume;\n"); break; default: pips_internal_error("unexpected measure %d", measure); } free(s_stage); free(s_side); free(reduc); } /* basic configuration generation for a stage, depending on hw description * @returns the number of arguments expected? * what about their type? */ static void basic_spoc_conf (spoc_hardware_type op, string_buffer body, string_buffer tail, int stage, int side, bool flip, const spoc_hw_t * conf, dagvtx orig, hash_table hp) { // only one call should be used for AIPO functions ? switch (op) { case spoc_type_poc: spoc_poc_conf(conf->poc[0], body, tail, stage, side, orig, hp); break; case spoc_type_alu: spoc_alu_conf(conf->alu, body, tail, stage, flip, orig, hp); break; case spoc_type_thr: spoc_th_conf(body, tail, stage, side, orig, hp); break; case spoc_type_mes: spoc_measure_conf(conf->mes[0], body, tail, stage, side, orig, hp); break; case spoc_type_inp: case spoc_type_nop: // copy, no code break; default: pips_internal_error("unexpected op type %s", what_operation(op)); } if (op!=spoc_type_nop) sb_cat(body, "\n"); } /* a data structure to describe a schedule for an operation */ typedef struct { entity image; // output of this operation dagvtx producer; // possibly NULL on input and output int stage; // stage of production spoc_hardware_type level; // nope | input < poc < alu < threshold < measure int side; // 0 or 1 bool flip; // whether alu op is flipped bool used; // whether the image has been used by an output bool just_used; // idem but at this stage // where this was used, to detect some particular cases? int used_stage; spoc_hardware_type used_level; } op_schedule; static void init_op_schedule(op_schedule * op, dagvtx v, int side) { op->image = v? dagvtx_image(v): NULL; op->producer = v; op->stage = 0; op->level = spoc_type_inp; op->side = side; op->flip = false; op->used = false; op->just_used = false; op->used_stage = -1; // never used op->used_level = spoc_type_inp; } static int max_stage(const op_schedule * in0, const op_schedule * in1) { if (in0->image) if (in1->image) // both return (in0->stage > in1->stage)? in0->stage: in1->stage; else // only in0 return in0->stage; else if (in1->image) // only in1 return in1->stage; else // none return 0; } /* is image needed? */ static bool image_is_needed(dagvtx prod, dag d, set todo) { bool needed = false; if (prod) { if (gen_in_list_p(prod, dag_outputs(d))) needed = true; else { SET_FOREACH(dagvtx, v, todo) { list preds = dag_vertex_preds(d, v); needed = gen_in_list_p(prod, preds); gen_free_list(preds), preds = NIL; if (needed) break; } } pips_debug(7, "\"%"_intFMT"\" is%s needed\n", dagvtx_number(prod), needed? "": " not"); } return needed; } // debug static void print_op_schedule(FILE * out, const string name, const op_schedule * op) { fprintf(out, "sched '%s' = %s (%" _intFMT " %s) %d:%s:%d %s %sused (%d:%s)\n", name, op->image? entity_local_name(op->image): "NULL", dagvtx_number(op->producer), dagvtx_operation(op->producer), op->stage, what_operation(op->level), op->side, (op->level==spoc_type_alu)? (op->flip? "/": "."): "", op->used? "": "not ", op->used_stage, what_operation(op->used_level)); } static bool check_mux_availibity(hash_table wiring, int stage, int mux) { _int index = 2 * (stage*4+mux) + 1; // odds return !hash_defined_p(wiring, (void *) index); } static void set_mux(hash_table wiring, int stage, int mux) { _int index = 2 * (stage*4+mux) + 1; // odds hash_put(wiring, (void *) index, (void *) index); } /* can I get out of stage on this side? */ static bool check_wiring_output(hash_table wiring, int stage, int side) { return check_mux_availibity(wiring, stage, side? 3: 0); } static _int component_index(int stage, int level, int side) { pips_assert("spoc component", level>=spoc_type_poc && level<= spoc_type_mes); if (level==spoc_type_alu) side=0; return 2 * (2 * (stage*4+level) + side) + 2; // even } static void set_component(hash_table wiring, int stage, int level, int side) { _int index = component_index(stage, level, side); hash_put(wiring, (void *) index, (void *) index); // scratch everything on the path before the used component if (stage>0 && level==spoc_type_poc) set_component(wiring, stage-1, spoc_type_mes, side); if (level==spoc_type_mes) set_component(wiring, stage, spoc_type_thr, side); } static bool available_component (hash_table wiring, int stage, int level, int side) { _int index = component_index(stage, level, side); return !hash_defined_p(wiring, (void *) index); } /* return the first stage after stage/level with both paths available */ static int find_first_crossing(hash_table wiring, int stage, int level) { if (level>spoc_type_alu) stage++; while (!(check_wiring_output(wiring, stage, 0) && check_wiring_output(wiring, stage, 1))) stage++; return stage; } /* return the stage & side of the first component available * after (start_stage, level, side) which is the source of the used image, * for an operation of type target_level */ static void find_first_available_component( hash_table wiring, int start_stage, int level, int side, // image comes from int target_level, bool crossing, // whether to include a crossing on the path... int * pstage, int * pside) { int stage = start_stage; int preferred, other; if (side>=0) preferred = side, other = 1 - side; // side==-1, alu... else preferred = 0, other = 1; if (target_level==spoc_type_alu) preferred=0, other=0; if (target_level<=level) stage++; if (crossing) { stage = find_first_crossing(wiring, stage, level); if (target_levelspoc_type_alu); while (!(pok=available_component(wiring, stage, target_level, preferred)) && (skip_first_other || !available_component(wiring, stage, target_level, other))) { stage++; skip_first_other = false; } // hmmm... if (pok && level<=spoc_type_alu && stage==start_stage+1 && target_levelside = -100; out->used = false; out->used_stage = -1; out->used_level = spoc_type_inp; in0->just_used = false; in1->just_used = false; ifdebug(6) { pips_debug(6, "scheduling (%" _intFMT " %s) %s\n", dagvtx_number(op), dagvtx_operation(op), vtxcontent_out(c)==entity_undefined? "": entity_local_name(vtxcontent_out(c))); print_op_schedule(stderr, "in0", in0); print_op_schedule(stderr, "in1", in1); } spoc_hardware_type level = (spoc_hardware_type) vtxcontent_optype(c); // measurements is special case, because the image is not consummed... if (level == spoc_type_mes) { pips_assert("one input image", gen_length(vtxcontent_inputs(c))==1); entity measured = ENTITY(CAR(vtxcontent_inputs(c))); pips_assert("input image available", measured==in0->image || measured==in1->image); // go to the end of the stage of the image producer, // on same side... if (in0->image == in1->image) { // we have the same image, chose closest to mes, and prefer in0 if (in0->level>=in1->level) *out = *in0, in0->used = (in0->level!=spoc_type_mes), in0->just_used = true, in1->used = false; else *out = *in1, in1->used = (in0->level!=spoc_type_mes), in1->just_used = true, in0->used = false; } else // take the available one, whatever { if (measured==in0->image) *out = *in0, in0->used = (in0->level!=spoc_type_mes), in0->just_used = true, in1->used = false; else *out = *in1, in1->used = (in0->level!=spoc_type_mes), in1->just_used = true, in0->used = false; } } else { // how many images (arguments) are needed by the operation? int needed = (int) gen_length(vtxcontent_inputs(c)); switch (needed) { case 0: // ALU CONST GENERATION ? pips_assert("alu const image generation", level==spoc_type_alu); // I must check that the alu is not already used?! // So I take a safe bet... // ??? argh... the image may have been cleaned of not used any more... out->stage = max_stage(in0, in1); // hmmm... I should also check that the component is not already used... if (in0->image && in0->stage == out->stage && in0->level >= spoc_type_alu) out->stage++; if (in1->image && in1->stage == out->stage && in1->level >= spoc_type_alu) out->stage++; // ensure there is at least one path for the output while (!(check_wiring_output(wiring, out->stage, 0) || check_wiring_output(wiring, out->stage, 1))) out->stage++; // two paths are required if one of the other image is still needed. if ((in0->image && image_is_needed(in0->producer, computed, todo)) || (in1->image && image_is_needed(in1->producer, computed, todo))) { while (! (check_wiring_output(wiring, out->stage, 0) && check_wiring_output(wiring, out->stage, 1))) out->stage++; } in0->used = false, in1->used = false; break; case 1: // ANYTHING, may have to chose a side. { entity dep = ENTITY(CAR(vtxcontent_inputs(c))); pips_assert("dependence is available", dep==in0->image || dep==in1->image); op_schedule * used, * notused; // where is the needed image? put it in used if (in0->image == in1->image) { // if the same image is available, // chose the not already used one if (in0->used) used = in1, notused = in0; else if (in0->used) used = in0, notused = in1; // or the one which is already engaged on a side? else if (in0->level >= spoc_type_thr && level <= spoc_type_alu) used = in0, notused = in1; else if (in1->level >= spoc_type_thr && level <= spoc_type_alu) used = in1, notused = in0; // or the earliest one, or in0 by default else if (in1->stagestage || (in1->stage==in0->stage && in1->level < in0->level)) used = in1, notused = in0; else used = in0, notused = in1; } else // just take the right one { used = dep==in0->image? in0: in1; notused = dep==in0->image? in1: in0; } pips_debug(7, "using %s (%d %s %d)\n", entity_local_name(used->image), used->stage, what_operation(used->level), used->side); // default stage and side... out->stage = used->stage; out->side = used->side; used->used = true; used->just_used = true; bool used_image_still_needed = image_is_needed(used->producer, computed, todo); // handle copy... if it is still there, it must be needed, // so just put it where it is available for later use. // ??? output copies should not be handled by the pipeline! if (level == spoc_type_nop) { // go to the end of the local path switch (used->level) { case spoc_type_inp: case spoc_type_poc: level = spoc_type_poc; break; case spoc_type_alu: level = spoc_type_alu; break; case spoc_type_thr: case spoc_type_mes: level = spoc_type_poc; out->stage++; break; default: pips_internal_error("unexpected spoc type %d", used->level); } // we need to put some space to extract the other image on another path if (used_image_still_needed) { if (level==spoc_type_poc) { // switch side if straight path is not available? if (!check_wiring_output(wiring, out->stage, out->side)) out->side = 1 - out->side; pips_assert("available path", check_wiring_output(wiring, out->stage, out->side)); out->stage++; } else if (level==spoc_type_alu) { // choose one side, prefer 0 if (check_wiring_output(wiring, out->stage, 0)) out->side = 0; else if (check_wiring_output(wiring, out->stage, 1)) out->side = 1; else pips_internal_error("no available path for copy of needed image"); out->stage++; level = spoc_type_poc; } else pips_internal_error("should not get there"); } else pips_debug(8, "copied image %s is not needed further\n", entity_local_name(used->image)); break; } pips_assert("not a copy", level!=spoc_type_nop); // ??? hmmm... an ALU used the operation??? find_first_available_component (wiring, // source (level may be shifted for ALU/morph issue, see freia_50 used->stage, used->used_stage!=-1 && used->used_level==spoc_type_alu && level==spoc_type_poc? spoc_type_poc: used->level, used->side, level, used_image_still_needed && used->image!=notused->image, &out->stage, &out->side); // tell which image was used used->used = true; notused->used = false; // record last use used->used_stage = out->stage; used->used_level = level; break; } case 2: // ALU // what if same image is used as both operands? if (!in1->image) *in1 = *in0; if (!in0->image) *in0 = *in1; pips_assert("alu binary operation", level==spoc_type_alu); out->stage = max_stage(in0, in1); // update input image status in0->used = true, in0->just_used = true; in1->used = true, in1->just_used = true; if (out->stage==in0->stage && in0->level >= spoc_type_alu) out->stage++; if (out->stage==in1->stage && in1->level >= spoc_type_alu) out->stage++; // including where last used in0->used_stage = out->stage; in0->used_level = level; in1->used_stage = out->stage; in1->used_level = level; break; default: pips_internal_error("shoud not get there"); } } // common settings out->level = level; if (out->level == spoc_type_alu) out->side = -1; else if (out->side==-1) { // must set a size if not already chosen int stage = out->levelstage-1: out->stage; if (check_wiring_output(wiring, stage, 0)) out->side = 0; else if (check_wiring_output(wiring, stage, 1)) out->side = 1; else pips_internal_error("no available path"); } if (vtxcontent_out(c)!=entity_undefined) { out->image = vtxcontent_out(c); out->producer = op; } // else it is a measure, don't change... ifdebug(6) print_op_schedule(stderr, "out", out); } /* all possible wirings at one stage */ static void generate_wiring_stage (string_buffer code, int stage, int in_side, // 0, 1, -1 for "alu"... int out_side, hash_table wiring) { pips_assert("check sides", in_side>=-1 && in_side<=1 && out_side>=0 && out_side<=1); pips_debug(7, "stage %d in %d -> out %d\n", stage, in_side, out_side); switch (in_side) { case -1: if (out_side) { set_wiring(code, stage, 1, 1, wiring); set_wiring(code, stage, 3, 0, wiring); } else { set_wiring(code, stage, 0, 1, wiring); set_wiring(code, stage, 2, 0, wiring); } break; case 0: if (out_side) { set_wiring(code, stage, 1, 0, wiring); set_wiring(code, stage, 3, 0, wiring); } else set_wiring(code, stage, 0, 0, wiring); break; case 1: if (out_side) set_wiring(code, stage, 3, 1, wiring); else { set_wiring(code, stage, 0, 1, wiring); set_wiring(code, stage, 2, 1, wiring); } break; default: pips_internal_error("should not get there..."); } } /* generate wire code from in to out, record choices in wiring. */ static void generate_wiring (string_buffer code, op_schedule * in, op_schedule * out, hash_table wiring) { pips_debug(6, "%s [%d %s %d] -> [%d %s %d] %" _intFMT "\n", entity_local_name(in->image), in->stage, what_operation(in->level), in->side, out->stage, what_operation(out->level), out->side, dagvtx_number(out->producer)); pips_assert("ordered schedule", (in->stage < out->stage) || ((in->stage == out->stage) && (in->level <= out->level))); // code comment... string in_stage = strdup(i2a(in->stage)), out_stage = strdup(i2a(out->stage)), in_side = strdup(i2a(in->side)), out_side = strdup(i2a(out->side)); sb_cat(code, " // ", entity_local_name(in->image), " [", in_stage, " ", what_operation(in->level)); if (in->level!=spoc_type_alu) sb_cat(code, " ", in_side); sb_cat(code, "] -> [", out_stage, " ", what_operation(out->level)); if (out->level!=spoc_type_alu) sb_cat(code, " ", out_side); sb_cat(code, "] ", i2a(dagvtx_number(out->producer)), " ", dagvtx_operation(out->producer), "\n"); free(in_stage); free(out_stage); free(in_side); free(out_side); // let us wire! if (in->stage==out->stage) { switch (in->level) { case spoc_type_inp: case spoc_type_poc: if (out->level<=spoc_type_poc) pips_assert("same side if early", in->side==out->side); if (out->level<=spoc_type_alu) sb_cat(code, " // nope\n"); // ELSE thr or mes... else { generate_wiring_stage(code, in->stage, in->side, out->side, wiring); if (in->level == spoc_type_inp) { // the poc was passed by wiring... in->level = spoc_type_poc; set_component(wiring, in->stage, in->level, in->side); } } break; case spoc_type_alu: // out->level is after thr, so there is a side if (out->side!=-1) generate_wiring_stage(code, in->stage, -1, out->side, wiring); // else: X alu -> W alu, possibly because it operation is a copy break; case spoc_type_thr: case spoc_type_mes: case spoc_type_out: // no choice pips_assert("same side", in->side==out->side); sb_cat(code, " // nope\n"); break; case spoc_type_nop: default: pips_internal_error("shoud not get there"); } // record operation flipping if (out->level == spoc_type_alu && dagvtx_optype(out->producer)==spoc_type_alu) // skip copy { vtxcontent cout = dagvtx_content(out->producer); list lins = vtxcontent_inputs(cout); pips_assert("sanity", in->side>=0 && lins); switch (gen_length(lins)) { case 2: if (in->side==0) out->flip = !(in->image == ENTITY(CAR(lins))); else // in->side==1 out->flip = (in->image == ENTITY(CAR(lins))); break; case 1: out->flip = (in->side==1); break; default: case 0: pips_internal_error("should not get there"); } } } else // in->stage < out->stage { // let us do it with a recursion... int prefered; op_schedule saved = *in; switch (in->level) { case spoc_type_inp: case spoc_type_poc: set_component(wiring, in->stage, spoc_type_poc, in->side); _FALLTHROUGH_; case spoc_type_alu: // chose prefered side if (in->level==spoc_type_alu) // try direct, or default to 0 prefered = (out->side>=0)? out->side: 0; else // take the right side as soon as possible? // ??? what if the path is not possible later? prefered = (out->side==-1)? in->side: out->side; // try both cases if (check_wiring_output(wiring, in->stage, prefered)) { generate_wiring_stage(code, in->stage, in->side, prefered, wiring); set_component(wiring, in->stage, spoc_type_mes, prefered); in->stage++; in->side = prefered; in->level = spoc_type_inp; generate_wiring(code, in, out, wiring); } else if (check_wiring_output(wiring, in->stage, 1 - prefered)) { generate_wiring_stage(code, in->stage, in->side, 1 - prefered, wiring); set_component(wiring, in->stage, spoc_type_mes, 1 - prefered); in->stage++; in->side = 1 - prefered; in->level = spoc_type_inp; generate_wiring(code, in, out, wiring); } else pips_internal_error("no available path..."); // we may still use the result for something else... others? if (saved.level<=spoc_type_alu && out->level<=spoc_type_poc && // restore to the previous stage saved.stage==out->stage-1) { pips_debug(7, "restoring previous schedule...\n"); *in = saved; } if (in->level == spoc_type_inp) in->level = spoc_type_poc; // the poc was passed by wiring break; case spoc_type_thr: case spoc_type_mes: case spoc_type_out: // no choice, skip to input of next stage in->stage++; in->level = spoc_type_inp; generate_wiring(code, in, out, wiring); break; case spoc_type_nop: default: pips_internal_error("shoud not get there"); } } } /* build up final pipeline code from various pieces * @param module * @param function_name to be generated * @param code output * @param head input, function parameters * @param body input, pipeline stage initialization * @param tail input, getting back reduction results * @param n_im_* number of in and out paramters to function * @param some_reductions if there are * @param p_* variables sent and received from pipeline */ static void freia_spoc_code_buildup (string module, string function_name, // buffers which hold different parts of the code string_buffer code, const string_buffer head, const string_buffer body, const string_buffer tail, // number of images in & out int n_im_out, int n_im_in, // parts which may be needed bool some_reductions, bool some_kernels, // input/output parameters const string out0, const string out1, const string in0, const string in1) { // function header: freia_error helper_function(freia_data_2d ... sb_cat(code, "\n" "// FREIA-SPoC helper function for module ", module, "\n" "freia_status ", function_name, "(\n"); // first, image arguments if (n_im_out>0) sb_cat(code, " " FREIA_IMAGE "o0"); if (n_im_out>1) sb_cat(code, ",\n " FREIA_IMAGE "o1"); if (n_im_out!=0 && n_im_in>0) sb_cat(code, ",\n"); if (n_im_in>0) sb_cat(code, " const " FREIA_IMAGE "i0"); if (n_im_in>1) sb_cat(code, ",\n const " FREIA_IMAGE "i1"); string_buffer_append_sb(code, head); // end of headers (some arguments may have been added by stages), // and begin the function body sb_cat(code, ")\n{\n" FREIA_SPOC_DECL); if (some_reductions) sb_cat(code, " spoc_reduction reduc;\n" " freia_reduction_results redres;\n"); if (some_kernels) sb_cat(code, " int i;\n"); sb_cat(code, "\n"); sb_cat(code, " // init pipe to nop\n" " spoc_init_pipe(&si, &sp, ", i2a(FREIA_DEFAULT_BPP), ");\n" "\n"); string_buffer_append_sb(code, body); // generate actual call to the accelerator sb_cat(code, FREIA_SPOC_CALL_START); if (some_reductions) sb_cat(code, FREIA_SPOC_CALL_REDUC); sb_cat(code, FREIA_SPOC_CALL_END " // actual call of spoc hardware\n" " freia_cg_template_process_2i_2o", "(¶m, ", out0, ", ", out1, ", ", in0, ", ", in1, ");\n", NULL); if (some_reductions) sb_cat(code, "\n" " // get reductions\n" " freia_cg_read_reduction_results(&redres);\n"); string_buffer_append_sb(code, tail); sb_cat(code, "\n return ret;\n}\n"); } /* tell whether the image produced by prod is definitely consummed by v * given the global dag d and the set of vertex still to be computed todo. */ static bool is_consummed_by_vertex(dagvtx prod, dagvtx v, dag d, set todo) { bool consummed; // no producer, no problem if (!prod) consummed = true; // the image is a global output, it must be kept else if (gen_in_list_p(prod, dag_outputs(d))) consummed = false; // the image is consummed by v else if (gen_in_list_p(v, dagvtx_succs(prod))) { set succs = set_make(set_pointer); set_assign_list(succs, dagvtx_succs(prod)); set_del_element(succs, succs, v); // other todos expect this image? consummed = !set_intersection_p(succs, todo); set_free(succs); } else consummed = false; pips_debug(7, "%"_intFMT" is %sconsummed by %"_intFMT"\n", dagvtx_number(prod), consummed? "": "not ", dagvtx_number(v)); return consummed; } /* generate a SPoC pipeline from a single DAG for module. * * @param module current * @param helper name of function to generate * @param code output here * @param dpipe dag to consider * @param lparams parameters to call helper * @return number of output images * * some side effects: * - if there is an overflow, dpipe updated with remaining vertices. * - accelerated statements are cleaned * * I should have really done an allocation on a infinite pipeline, * and then cut it, instead of this half measure to handle overflows, * but that would change a lot of things to go back. */ static _int freia_spoc_pipeline (string module, string helper, string_buffer code, dag dpipe, list * lparams, const set output_images) { hash_table wiring = hash_table_make(hash_int, 128); list outs = NIL; bool some_reductions = false, some_kernels = false; int pipeline_depth = get_int_property(spoc_depth_prop); pips_debug(3, "running on '%s' for %d operations\n", module, (int) (gen_length(dag_vertices(dpipe)) - gen_length(dag_inputs(dpipe)))); pips_assert("non empty dag", gen_length(dag_vertices(dpipe))>0); // build list of output entities from the pipe FOREACH(dagvtx, v, dag_outputs(dpipe)) outs = CONS(entity, vtxcontent_out(dagvtx_content(v)), outs); outs = gen_nreverse(outs); // generate a helper function in some file int cst = 0; string_buffer head = string_buffer_make(true), body = string_buffer_make(true), tail = string_buffer_make(true); // first arguments are out & in images int n_im_in = gen_length(dag_inputs(dpipe)); pips_assert("0, 1, 2 input images", n_im_in>=0 && n_im_in<=2); // piped images in helper string p_in0 = "NULL", p_in1 = "NULL", p_out0 = "NULL", p_out1 = "NULL"; // piped images in function entity a_in0 = NULL, a_in1 = NULL; dagvtx v_in0 = NULL; op_schedule in0, in1, out; list /* of entity */ limg = NIL; int live_images = 0; // build input arguments/parameters/arguments if (n_im_in>=1) { v_in0 = DAGVTX(CAR(dag_inputs(dpipe))); a_in0 = vtxcontent_out(dagvtx_content(v_in0)); p_in0 = "i0"; init_op_schedule(&in0, v_in0, 0); limg = CONS(entity, a_in0, NIL); live_images++; } else init_op_schedule(&in0, NULL, 0); if (n_im_in==1 && gen_length(dagvtx_succs(v_in0))>1) { // help scheduling by providing the first input twice. init_op_schedule(&in1, v_in0, 1); p_in1 = "i0"; live_images++; } else if (n_im_in>=2) { dagvtx v_in1 = DAGVTX(CAR(CDR(dag_inputs(dpipe)))); a_in1 = vtxcontent_out(dagvtx_content(v_in1)); p_in1 = "i1"; init_op_schedule(&in1, v_in1, 1); limg = gen_nconc(limg, CONS(entity, a_in1, NIL)); live_images++; } else init_op_schedule(&in1, NULL, 1); list vertices = gen_nreverse(gen_copy_seq(dag_vertices(dpipe))); set todo = set_make(set_pointer); FOREACH(dagvtx, vi, dag_inputs(dpipe)) gen_remove(&vertices, vi); set_assign_list(todo, vertices); set skipped = set_make(set_pointer); // expression/variable -> parameter string name hash_table hparams = hash_table_make(hash_pointer, 0); // keep track of current stage for comments, and to detect overflows int stage = -1; FOREACH(dagvtx, v, vertices) { pips_debug(3, "considering vertex %"_intFMT"\n", dagvtx_number(v)); // skip inputs if (dagvtx_number(v)==0) break; // on overflow... if (!set_empty_p(skipped)) { // check for dependencies on skipped vertices... bool toskip = false; SET_FOREACH(dagvtx, sk, skipped) { // skip because of missing deps if (gen_in_list_p(v, dagvtx_succs(sk))) { pips_debug(7, "skipping %"_intFMT", deps on %"_intFMT"\n", dagvtx_number(v), dagvtx_number(sk)); toskip = true; break; } } // or no available output path, none created by consumming an image if (!toskip && dagvtx_succs(v) && live_images==2 && !(is_consummed_by_vertex(in0.producer, v, dpipe, todo) || is_consummed_by_vertex(in1.producer, v, dpipe, todo))) { pips_debug(7, "skipping %"_intFMT", no path\n", dagvtx_number(v)); toskip = true; } if (toskip) { set_add_element(skipped, skipped, v); continue; } } pips_debug(7, "dealing with vertex %" _intFMT ", %d to go, %d path\n", dagvtx_number(v), set_size(todo), live_images); vtxcontent vc = dagvtx_content(v); pips_assert("there is a statement", pstatement_statement_p(vtxcontent_source(vc))); statement s = pstatement_statement(vtxcontent_source(vc)); call c = freia_statement_to_call(s); // extract the api information now, because of scheduling side // effects on out so that out.provider may be changed on measures int optype = dagvtx_optype(v), opid = dagvtx_opid(v); const freia_api_t * api = get_freia_api(opid); pips_assert("AIPO function found", api!=NULL); set_del_element(todo, todo, v); // schedule... where_to_perform_operation(v, &in0, &in1, dpipe, todo, &out, wiring); // detect pipeline overflow if (out.stage >= pipeline_depth) { // pipeline is full, vi was not computed: pips_debug(3, "pipeline overflow on %" _intFMT "\n", dagvtx_number(v)); set_add_element(todo, todo, v); // now, there may be other vertices which are computable... // but the splitting put there after this one in the vertex list // hmmm... set_add_element(skipped, skipped, v); } else // the vertex is added to the pipeline... { // record set_component(wiring, out.stage, out.level, out.side); // get needed parameters if any *lparams = gen_nconc(*lparams, freia_extract_params(opid, call_arguments(c), head, NULL, hparams, &cst)); some_reductions |= vtxcontent_optype(vc)==spoc_type_mes; some_kernels |= vtxcontent_optype(vc)==spoc_type_poc; // there may be regressions if it is a little bit out of order... // add a comment each time a new stage is started. if (out.stage!=stage) { stage = out.stage; sb_cat(body, "\n // STAGE ", i2a(stage), "\n"); } // generate wiring, which may change flip stage on ALU operation // special case if in0==in1 is needed? no, rely on just_used if (in0.just_used) generate_wiring(body, &in0, &out, wiring); if (in1.just_used) generate_wiring(body, &in1, &out, wiring); // generate stage code basic_spoc_conf(optype, body, tail, out.stage, out.side, out.flip, &(api->spoc), v, hparams); bool in0_needed = image_is_needed(in0.producer, dpipe, todo), in1_needed = image_is_needed(in1.producer, dpipe, todo); // first, keep where it is... if (in0.stage==out.stage && in0.level==out.level && in0.side==out.side) in0 = out; else if (in1.stage==out.stage && in1.level==out.level && in1.side==out.side) in1 = out; // else overwrite not needed used image else if (!in0_needed && in0.used) in0 = out; else if (!in1_needed && in1.used) in1 = out; // else, overwrite same image if not needed else if (!in0_needed || out.image==in0.image) { if (in1.image) in0 = out; else in1 = out; // rather keep it the available slot? } else if (!in1_needed || out.image==in1.image) { if (in0.image) in1 = out; else in0 = out; // idem } // the image is available twice which is needed else if (in0.image && in0.image == in1.image) { // we have the same image, overwrite the used one if (in0.used) in0 = out; else if (in1.used) in1 = out; // if none where used, overwrite the one on the current side // ??? in0.side == -1 && in1.side==-1 ? else if (in0.side == out.side) in0 = out; else if (in1.side == out.side) in1 = out; else if (out.side==-1) // just choose one? in0 = out; else pips_internal_error("should not get there (same image)?"); } else { pips_assert("overflow mode", !set_empty_p(skipped)); // ??? hmmm, we get there on overflow, if an input image is // still to be used, but 2 computed images are extracted. // what we are in effect doing is to modify the schedule, // possibly breaking the 2 live image property in the process, // in order to attempt to fill in the pipe a little more... if (out.image) { if (in0.just_used) { in0 = out; in0_needed = true; } else if (in1.just_used) { in1 = out; in1_needed = true; } else // not sure of the conditions above to choose between in0 and in1 pips_internal_error("computed image not extracted..."); } } // anyway, we must clean unuseful variables, because // the scheduling on image entities to check deps (still ?) if (!in0_needed && in0.producer!=out.producer) init_op_schedule(&in0, NULL, 0); if (!in1_needed && in1.producer!=out.producer) init_op_schedule(&in1, NULL, 0); // update count of live images for overflow mode live_images = 0; if (image_is_needed(in0.producer, dpipe, todo)) live_images++; if (image_is_needed(in1.producer, dpipe, todo)) live_images++; } } set computed = set_make(set_pointer); set_assign_list(computed, vertices); set_difference(computed, computed, todo); // pipeline interruption? if (!set_empty_p(todo)) { // what are the effective outputs in the middle of the pipeline list new_outs = NIL; if (image_is_needed(in1.producer, dpipe, todo) && !gen_in_list_p(in1.producer, dag_inputs(dpipe))) new_outs = CONS(entity, in1.image, new_outs); if (image_is_needed(in0.producer, dpipe, todo) && !gen_in_list_p(in0.producer, dag_inputs(dpipe))) // should also check that in0!=in1? new_outs = CONS(entity, in0.image, new_outs); // gen_free_list(dag_outputs(dpipe)); // dag_outputs(dpipe) = outs; gen_free_list(outs), outs = new_outs; } // cleanup dpipe of computed vertices FOREACH(dagvtx, vr, vertices) { if (set_belong_p(computed, vr)) { dag_remove_vertex(dpipe, vr); if (pstatement_statement_p(vtxcontent_source(dagvtx_content(vr)))) hwac_kill_statement(pstatement_statement (vtxcontent_source(dagvtx_content(vr)))); free_dagvtx(vr); } } // hmmm??? dag_compute_outputs(dpipe, NULL, output_images, NIL, false); gen_free_list(vertices), vertices = NIL; set_free(computed), computed = NULL; // handle pipe outputs (may have been interrupted) int n_im_out = gen_length(outs); pips_assert("0, 1, 2 output images", n_im_out>=0 && n_im_out<=2); pips_assert("some input or output images", n_im_out || n_im_in); if (n_im_out==0) { sb_cat(body, "\n // no output image\n"); } else if (n_im_out==1) { entity imout = ENTITY(CAR(outs)); // put producer in in0 if (in1.image==in0.image) { pips_assert("image found", in0.image==imout); // choose the latest if (in1.stage>in0.stage || (in1.stage==in0.stage && in1.level>in0.level)) out = in0, in0 = in1, in1 = out; } // else just take the right one else if (in1.image==imout && in0.image!=imout) out = in0, in0 = in1, in1 = out; else if (in0.image==imout) ; // ok else pips_internal_error("result image is not alive"); out.image = imout; out.producer = NULL; out.level = spoc_type_out; out.stage = in0.stage; out.side = in0.side>=0? in0.side: 0; // choose 0 by default if alu // switch if side is not available if (in0.side<0 && !check_wiring_output(wiring, out.stage, out.side)) out.side = 1 - out.side; sb_cat(body, "\n" " // output image ", entity_local_name(imout), " on ", i2a(out.side), "\n"); generate_wiring(body, &in0, &out, wiring); // do not trust the default initialisation of the paths in0 = out; out.stage = pipeline_depth-1; sb_cat(body, "\n // fill in to the end...\n"); generate_wiring(body, &in0, &out, wiring); if (out.side) p_out1 = "o0"; else p_out0 = "o0"; limg = CONS(entity, imout, limg); } else if (n_im_out==2) { entity out0 = ENTITY(CAR(outs)), out1 = ENTITY(CAR(CDR(outs))); int out0_side, out1_side; pips_assert("output two results in two variables", out0!=out1); // make out0 match in0 and out1 match in1 if (out0 != in0.image) out = in0, in0 = in1, in1 = out; pips_assert("results are available", out0==in0.image && out1==in1.image); pips_debug(7, "out0 %s out1 %s in0(%d.%d.%d) %s in1(%d.%d.%d) %s\n", entity_local_name(out0), entity_local_name(out1), in0.stage, in0.level, in0.side, entity_local_name(in0.image), in1.stage, in1.level, in1.side, entity_local_name(in1.image)); // the more advanced image in the pipe decides its output side bool in0_advanced = in0.stage>in1.stage || (in0.stage==in1.stage && in0.level>in1.level); if (in0_advanced) { out0_side = in0.side; if (out0_side==-1) out0_side = 0; // alu, choose! out1_side = 1 - out0_side; } else // in1 is more forward { out1_side = in1.side; if (out1_side==-1) out1_side = 1; // alu, choose! out0_side = 1 - out1_side; } pips_assert("2 images: one output on each side", (out0_side==0 && out1_side==1) || (out0_side==1 && out1_side==0)); limg = CONS(entity, out0, CONS(entity, out1, limg)); if (out1_side) // out1 on side 1, thus out0 side 0 p_out0 = "o0", p_out1 = "o1"; else // they are reversed p_out0 = "o1", p_out1 = "o0"; int out_stage = (in0.stage>in1.stage)? in0.stage: in1.stage; sb_cat(body, "\n" " // output image ", entity_local_name(out0), " on ", i2a(out0_side)); sb_cat(body, " and image ", entity_local_name(out1), " on ", i2a(out1_side), "\n"); // extract the first one. out.image = out0; out.producer = NULL; out.level = spoc_type_out; out.side = out0_side; out.stage = out_stage; generate_wiring(body, &in0, &out, wiring); // do not trust the default initialisation of the pipeline in0 = out; out.stage = pipeline_depth-1; sb_cat(body, "\n // fill in to the end...\n"); generate_wiring(body, &in0, &out, wiring); // extract the seconde one sb_cat(body, "\n"); out.image = out1; out.producer = NULL; out.level = spoc_type_out; out.side = out1_side; out.stage = out_stage; generate_wiring(body, &in1, &out, wiring); // do not trust the default initialisation of the pipeline in1 = out; out.stage = pipeline_depth-1; sb_cat(body, "\n // fill in to the end...\n"); generate_wiring(body, &in1, &out, wiring); } else pips_internal_error("only 0 to 2 output images!"); // handle function image arguments freia_add_image_arguments(limg, lparams); // build whole code from various pieces freia_spoc_code_buildup(module, helper, code, head, body, tail, n_im_out, n_im_in, some_reductions, some_kernels, p_out0, p_out1, p_in0, p_in1); // cleanup gen_free_list(outs); set_free(todo); set_free(skipped); hash_table_free(wiring); string_buffer_free(&head); string_buffer_free(&body); string_buffer_free(&tail); return n_im_out; } /***************************************************************** MISC UTIL */ /* current list of computable that may be used to know about the * global context when comparing to vertices in "dagvtx_spoc_priority". */ static list dagvtx_spoc_priority_computables = NIL; // idem for vertices computed in current pipe static list dagvtx_spoc_priority_current = NIL; #if 0 /* return the number of poc operations which have the same input node * as ref from the global list, including the ref itself. */ static int poc_count_same_inputs(const dagvtx ref) { pips_assert("global list is defined", dagvtx_spoc_priority_computables); pips_assert("vertex is in list", gen_in_list_p(ref, dagvtx_spoc_priority_computables)); pips_assert("vertex is a poc operation", dagvtx_optype(ref)==spoc_type_poc); dagvtx src = DAGVTX(CAR(vtxcontent_inputs(dagvtx_content(ref)))); int n = 0; FOREACH(dagvtx, v, dagvtx_spoc_priority_computables) if (dagvtx_optype(v)==spoc_type_poc && DAGVTX(CAR(vtxcontent_inputs(dagvtx_content(v)))) == src) n++; FOREACH(dagvtx, v, dagvtx_spoc_priority_current) if (dagvtx_optype(v)==spoc_type_poc && DAGVTX(CAR(vtxcontent_inputs(dagvtx_content(v)))) == src) n++; pips_assert("at least myself", n>0); return n; } #endif /* ? = Morpho(I); ? = ALU(I, ?); */ static bool erode_alu_shared_p(vtxcontent c1, vtxcontent c2) { return vtxcontent_optype(c1)==spoc_type_poc && vtxcontent_optype(c2)==spoc_type_alu && gen_length(vtxcontent_inputs(c2))==2 && gen_in_list_p(ENTITY(CAR(vtxcontent_inputs(c1))), vtxcontent_inputs(c2)); } /* comparison function for sorting dagvtx in qsort, * this is deep voodoo, because the priority has an impact on * correctness? that should not be the case as only computations * allowed by dependencies are schedule. * non implemented functions are pushed late. * tells v1 < v2 => -1 => v1 BEFORE v2 */ static int dagvtx_spoc_priority(const dagvtx * v1, const dagvtx * v2) { string why = "none"; int result = 0; vtxcontent c1 = dagvtx_content(*v1), c2 = dagvtx_content(*v2); // prioritize first scalar ops, measures and last copies // if there is only one of them if (vtxcontent_optype(c1)!=vtxcontent_optype(c2)) { // non implemented operations if (vtxcontent_optype(c1)==spoc_type_sni) result = 1, why = "not"; else if (vtxcontent_optype(c2)==spoc_type_sni) result = -1, why = "not"; // then scalars operations first to remove (scalar) dependences else if (vtxcontent_optype(c1)==spoc_type_oth) result = -1, why = "scal"; else if (vtxcontent_optype(c2)==spoc_type_oth) result = 1, why = "scal"; // then measurements are put first else if (vtxcontent_optype(c1)==spoc_type_mes) result = -1, why = "mes"; else if (vtxcontent_optype(c2)==spoc_type_mes) result = 1, why = "mes"; // the copies are performed last... else if (vtxcontent_optype(c1)==spoc_type_nop) result = 1, why = "copy"; else if (vtxcontent_optype(c2)==spoc_type_nop) result = -1, why = "copy"; // special morpho/alu case with a shared input image else if (erode_alu_shared_p(c1, c2)) result = 1, why = "shared"; else if (erode_alu_shared_p(c2, c1)) result = -1, why = "shared"; } if (result==0) { // if not set by previous case, use other criterions int l1 = (int) gen_length(vtxcontent_inputs(c1)), l2 = (int) gen_length(vtxcontent_inputs(c2)); // count non mesure successors: int nms1 = 0, nms2 = 0; FOREACH(dagvtx, vs1, dagvtx_succs(*v1)) if (dagvtx_optype(vs1)!=spoc_type_mes) nms1++; FOREACH(dagvtx, vs2, dagvtx_succs(*v2)) if (dagvtx_optype(vs2)!=spoc_type_mes) nms2++; // the decision process is mostly based on the number of inputs // images to the two compared operations. if (l1!=l2 && (l1==0 || l2==0)) // put image generators at the end, after any other computation result = l2-l1, why = "args"; else if (nms1!=nms2 && l1==1 && l2==1) // the less successors the better? the rational is: // - mesures are handled before and do not have successors anyway, // - so this is about whether a result of an unary op is reused by // two nodes, in which case it will just jam the pipeline, so // try to put other computations before it. Note that mes // successors do not really count, as the image is not lost. result = nms1 - nms2, why = "succs"; else if (l1!=l2) // else ??? no effect on my validation. result = l2-l1, why = "args2"; else if (vtxcontent_optype(c1)!=vtxcontent_optype(c2)) // otherwise use the op types, which are somehow ordered // so that if all is well the pipe is filled in order. result = vtxcontent_optype(c1) - vtxcontent_optype(c2), why = "ops"; else /* // unsuccessful attempt for freia_43 if (vtxcontent_optype(c1)==spoc_type_poc) { int same1 = poc_count_same_inputs(*v1), same2 = poc_count_same_inputs(*v2); if (same1!=same2) // chose the one with more inputs result = same1-same2, why = "pocinputs"; else // same as last case result = dagvtx_number(*v1) - dagvtx_number(*v2), why = "stats"; } else */ // if all else fails, rely on statement numbers. result = dagvtx_number(*v1) - dagvtx_number(*v2), why = "stats"; } pips_debug(7, "%" _intFMT " %s %s %" _intFMT " %s (%s)\n", dagvtx_number(*v1), dagvtx_operation(*v1), result<0? ">": (result==0? "=": "<"), dagvtx_number(*v2), dagvtx_operation(*v2), why); pips_assert("total order", v1==v2 || result!=0); return result; } /************************************************************ IMPLEMENTATION */ /* update sure/maybe set of live images after computing vertex v * that is the images that may be output from the pipeline. * this is voodoo... */ static void live_update(dag d, dagvtx v, set sure, set maybe) { vtxcontent c = dagvtx_content(v); // skip "other" statements if (dagvtx_other_stuff_p(v)) return; list ins = vtxcontent_inputs(c); int nins = gen_length(ins); entity out = vtxcontent_out(c); int nout = out!=entity_undefined? 1: 0; list preds = dag_vertex_preds(d, v); set all = set_make(set_pointer); set_union(all, sure, maybe); pips_assert("inputs are available", list_in_set_p(preds, all)); set_free(all), all = NULL; switch (nins) { case 0: // no input image is used // maybe is unchanged // I guess it is not "NOP"... pips_assert("one output...", nout==1); set_union(maybe, maybe, sure); break; case 1: if (nout) { // 1 -> 1 if (set_size(sure)==1 && !list_in_set_p(preds, sure)) { set_assign_list(maybe, preds); set_union(maybe, maybe, sure); } else { set_append_list(maybe, preds); } } break; case 2: // any of the inputs may be kept set_assign_list(maybe, preds); break; default: pips_internal_error("unpexted number of inputs to vertex: %d", nins); } if (nout==1) { set_clear(sure); set_add_element(sure, sure, v); } // else sure is kept set_difference(maybe, maybe, sure); // cleanup gen_free_list(preds), preds = NIL; } /* returns an allocated set of vertices with live outputs. */ static set output_arcs(dag d, set vs) { set out_nodes = set_make(set_pointer); // direct output nodes SET_FOREACH(dagvtx, v, vs) { if (vtxcontent_out(dagvtx_content(v))!=entity_undefined) { // this vertex produces an image bool is_needed = false; // it is needed if... list succs = dagvtx_succs(v); if (gen_in_list_p(v, dag_outputs(d))) is_needed = true; else if (succs) { // some succs are not yet computed... FOREACH(dagvtx, vsucc, succs) if (!set_belong_p(vs, vsucc)) is_needed = true; } // else there is no successor!? if (is_needed) set_add_element(out_nodes, out_nodes, v); } } return out_nodes; } /* how many output arcs from this set of vertices? */ static int number_of_output_arcs(dag d, set vs) { set out_nodes = output_arcs(d, vs); int n_arcs = set_size(out_nodes); set_free(out_nodes); return n_arcs; } /* @return whether it is a 3x3 convolution */ static bool convolution_33(dagvtx v) { if (freia_convolution_p(v)) { _int w, h; if (freia_convolution_width_height(v, &w, &h, false) && w==3 && h==3) return true; } return false; } /* does this dag contains a spoc non implemented operation? */ static bool dag_spoc_not_implemented(dag d) { FOREACH(dagvtx, v, dag_vertices(d)) if (dagvtx_optype(v)==spoc_type_sni || // special handling of convolution (freia_convolution_p(v) && !convolution_33(v))) return true; return false; } /* return first vertex in the list which is compatible, or NULL if none. */ static dagvtx first_which_may_be_added (dag dall, set current, // of dagvtx list lv, // of candidate dagvtx set sure, // of dagvtx set maybe) // image entities { dagvtx chosen = NULL; set inputs = set_make(set_pointer); set current_output = output_arcs(dall, current); int n_outputs = set_size(current_output); pips_assert("should be okay at first!", n_outputs<=2); pips_debug(8, "#outputs = %d\n", n_outputs); // output arcs from this subset // set outputs = output_arcs(current); FOREACH(dagvtx, v, lv) { pips_debug(8, "considering vertex %"_intFMT"\n", dagvtx_number(v)); pips_assert("not yet there", !set_belong_p(current, v)); // some intermediate stuff if (dagvtx_optype(v)==spoc_type_oth) { chosen = v; break; } // no image is produce, so no image output is added... if (!dagvtx_image(v)) { pips_assert("is a mesure", dagvtx_optype(v)==spoc_type_mes); chosen = v; break; } list preds = dag_vertex_preds(dall, v); set_assign_list(inputs, preds); pips_debug(8, "#inputs = %d\n", set_size(inputs)); int npreds = gen_length(preds); gen_free_list(preds), preds = NIL; //pips_debug(7, "vertex %"_intFMT": %d preds\n", dagvtx_number(v), npreds); if (npreds==2) // binary alu operations... { if (!set_inclusion_p(sure, inputs)) continue; // two lives, but the var reuse will break the pipe by hidding // the other live which is not used by the computation of v. if (n_outputs==2 && set_size(inputs)==1) continue; // another more general case from freia_68 set all_lives = set_make(set_pointer); set_intersection(all_lives, inputs, maybe); set_union(all_lives, current_output, all_lives); int n_lives = set_size(all_lives); set_free(all_lives); // cannot do, we would go over the limit... if (n_lives>2) continue; } set_add_element(current, current, v); int narcs_with_v = number_of_output_arcs(dall, current); set_del_element(current, current, v); if (narcs_with_v <= 2) { chosen = v; break; } } // none found set_free(inputs); return chosen; } /* split dag dall into a list of pipelinable dags * which must be processed in that order (?) * side effect: dall is more or less consummed... */ static list /* of dags */ split_dag(dag initial, const set output_images) { // this may happen if an input image is also an output image... // pips_assert("no image reuse", single_image_assignement_p(initial)); if (!single_image_assignement_p(initial)) pips_user_warning("still some image reuse...\n"); // ifdebug(1) pips_assert("initial dag ok", dag_consistent_p(initial)); // if everything was removed by optimizations, there is nothing to do. if (dag_computation_count(initial)==0) return NIL; dag dall = copy_dag(initial); int nvertices = gen_length(dag_vertices(dall)); list ld = NIL, lcurrent = NIL; set current = set_make(set_pointer), computed = set_make(set_pointer), maybe = set_make(set_pointer), sure = set_make(set_pointer), avails = set_make(set_pointer); // well, there are not all available always! set_assign_list(maybe, dag_inputs(dall)); // set_assign(avails, maybe); set_assign(computed, maybe); int count = 0; do { count++; set_union(avails, sure, maybe); ifdebug(4) { pips_debug(4, "round %d:\n", count); set_fprint(stderr, "computed", computed, (gen_string_func_t) dagvtx_to_string); set_fprint(stderr, "current", current, (gen_string_func_t) dagvtx_to_string); set_fprint(stderr, "avails", avails, (gen_string_func_t) dagvtx_to_string); set_fprint(stderr, "maybe", maybe, (gen_string_func_t) dagvtx_to_string); set_fprint(stderr, "sure", sure, (gen_string_func_t) dagvtx_to_string); } list computables = dag_computable_vertices(dall, computed, avails, current); dagvtx_spoc_priority_computables = computables; dagvtx_spoc_priority_current = lcurrent; gen_sort_list(computables, (int(*)(const void*,const void*)) dagvtx_spoc_priority); dagvtx_spoc_priority_computables = NIL; dagvtx_spoc_priority_current = NIL; pips_assert("something must be computable if current is empty", computables || !set_empty_p(current)); pips_debug(4, "%d computable vertices\n", (int) gen_length(computables)); ifdebug(5) dagvtx_nb_dump(stderr, "computables", computables); // take the first one possible in the pipe, if any dagvtx vok = first_which_may_be_added(dall, current, computables, sure, maybe); if (vok && (dagvtx_optype(vok)==spoc_type_sni || (freia_convolution_p(vok) && !convolution_33(vok))) && lcurrent) // extract non implemented nodes alone only! vok = NULL; if (vok) { pips_debug(5, "extracting %" _intFMT "...\n", dagvtx_number(vok)); set_add_element(current, current, vok); lcurrent = CONS(dagvtx, vok, lcurrent); set_add_element(computed, computed, vok); live_update(dall, vok, sure, maybe); // set_union(avails, sure, maybe); } // no stuff vertex can be added, or it was the last one, // or it is not implemented and thus to be extracted "alone" if (!vok || set_size(computed)==nvertices || (vok && (dagvtx_optype(vok)==spoc_type_sni || (freia_convolution_p(vok) && !convolution_33(vok))))) { // ifdebug(5) // set_fprint(stderr, "closing current", current, ) pips_debug(5, "closing current...\n"); pips_assert("current not empty", !set_empty_p(current)); // gen_sort_list(lcurrent, (gen_cmp_func_t) dagvtx_ordering); lcurrent = gen_nreverse(lcurrent); // close current and build a deterministic dag... dag nd = make_dag(NIL, NIL, NIL); FOREACH(dagvtx, v, lcurrent) { pips_debug(7, "extracting node %" _intFMT "\n", dagvtx_number(v)); dag_append_vertex(nd, copy_dagvtx_norec(v)); } dag_compute_outputs(nd, NULL, output_images, NIL, false); dag_cleanup_other_statements(nd); ifdebug(7) { // dag_dump(stderr, "updated dall", dall); dag_dump(stderr, "pushed dag", nd); } // update global list of dags to return. ld = CONS(dag, nd, ld); // cleanup gen_free_list(lcurrent), lcurrent = NIL; set_clear(current); set_clear(sure); set_assign(maybe, computed); } gen_free_list(computables); } while (set_size(computed)!=nvertices); // checks and cleanup pips_assert("current empty list", !lcurrent); pips_assert("all vertices were computed", set_size(computed)==nvertices); set_free(current); set_free(computed); set_free(sure); set_free(maybe); set_free(avails); free_dag(dall); pips_debug(5, "returning %d dags\n", (int) gen_length(ld)); return gen_nreverse(ld); } /* generate helpers for statements in ls of module * output resulting functions in helper, which may be empty in some cases. * @param module * @param ls list of statements for the dag (in reverse order) * @param helper output file * @param helpers created functions * @param number current helper dag count * @return list of intermediate images to allocate */ list freia_spoc_compile_calls (string module, dag fulld, sequence sq, list /* of statements */ ls, const hash_table occs, hash_table exchanges, const set output_images, FILE * helper_file, set helpers, int number) { // build DAG for ls pips_debug(3, "considering %d statements\n", (int) gen_length(ls)); pips_assert("some statements", ls); int n_op_init, n_op_init_copies; freia_aipo_count(fulld, &n_op_init, &n_op_init_copies); // must have distinct images... hash_table init = hash_table_make(hash_pointer, 0); list new_images = dag_fix_image_reuse(fulld, init, occs); list added_before = NIL, added_after = NIL; freia_dag_optimize(fulld, exchanges, &added_before, &added_after); // remove copies and duplicates if possible... // ??? maybe there should be an underlying transitive closure? not sure. int n_op_opt, n_op_opt_copies; freia_aipo_count(fulld, &n_op_opt, &n_op_opt_copies); fprintf(helper_file, "\n" "// dag %d: %d ops and %d copies, " "optimized to %d ops and %d+%d+%d copies\n", number, n_op_init, n_op_init_copies, n_op_opt, n_op_opt_copies, (int) gen_length(added_before), (int) gen_length(added_after)); // dump final dag dag_dot_dump_prefix(module, "dag_cleaned_", number, fulld, added_before, added_after); string fname_fulldag = strdup(cat(module, "_spoc", HELPER, i2a(number))); // split dag in one-pipe dags. list ld = split_dag(fulld, output_images); // nothing to do! // it would have been interesting not to create thehelper file in this case. // if (ld==NIL) return; FOREACH(dag, dfix, ld) freia_hack_fix_global_ins_outs(fulld, dfix); // globally remaining statements set global_remainings = set_make(set_pointer); set_assign_list(global_remainings, ls); string_buffer code = string_buffer_make(true); int n_spoc_calls = 0; int n_pipes = 0; int stnb = -1; set stats = set_make(set_pointer), dones = set_make(set_pointer); FOREACH(dag, d, ld) { // skip non implemented stuff if (dag_spoc_not_implemented(d)) continue; // fix connectivity dag_statements(stats, d); freia_migrate_statements(sq, stats, dones); set_union(dones, dones, stats); set remainings = set_make(set_pointer); set_append_vertex_statements(remainings, dag_vertices(d)); // remove special inputs nodes // FOREACH(dagvtx, inp, dag_inputs(d)) // set_del_element(remainings, remainings, inp); // generate a new helper function for dag d string fname_dag = strdup(cat(fname_fulldag, "_", i2a(n_pipes++))); ifdebug(4) dag_dump(stderr, "d", d); dag_dot_dump(module, fname_dag, d, NIL, NIL); // one logical pipeline may be split because of overflow // the dag is updated to reflect that as a code generation side effect int split = 0; while (dag_vertices(d)) { // fix internal ins/outs, that are tempered with by split & overflows freia_hack_fix_global_ins_outs(fulld, d); ifdebug(6) { pips_debug(4, "dag for split %d\n", split); dag_dump(stderr, "d", d); } string fname_split = strdup(cat(fname_dag, "_", i2a(split++))); list /* of expression */ lparams = NIL; _int nout = freia_spoc_pipeline(module, fname_split, code, d, &lparams, output_images); stnb = freia_substitute_by_helper_call(d, global_remainings, remainings, ls, fname_split, lparams, helpers, stnb); // record (simple) signature hash_put(init, local_name_to_top_level_entity(fname_split), (void*) nout); free(fname_split), fname_split = NULL; } n_spoc_calls += split; fprintf(helper_file, "// split %d: %d cut%s\n", n_pipes-1, split, split>1? "s": ""); set_free(remainings), remainings = NULL; free(fname_dag), fname_dag = NULL; } set_free(stats); set_free(dones); fprintf(helper_file, "// # SPOC calls: %d\n", n_spoc_calls); freia_insert_added_stats(ls, added_before, true); added_before = NIL; freia_insert_added_stats(ls, added_after, false); added_after = NIL; string_buffer_to_file(code, helper_file); string_buffer_free(&code); // cleanup set_free(global_remainings), global_remainings = NULL; free(fname_fulldag), fname_fulldag = NULL; FOREACH(dag, dc, ld) free_dag(dc); gen_free_list(ld); // deal with new images list real_new_images = freia_allocate_new_images_if_needed(ls, new_images, occs, init, init); gen_free_list(new_images); hash_table_free(init); return real_new_images; }