osprey/be/lno/snl_trans.h File Reference
Go to the source code of this file.
Defines | |
| #define | snl_trans_INCLUDED "snl_trans.h" |
Functions/Subroutines | |
| void | SNL_Change_Reduction_Loop_Stmts (SX_PLIST *plist, WN *from, WN *to) |
| void | SNL_Expand_Reduction_Deps (WN *loop) |
| BOOL | SNL_Test_Reduction_Lexneg (EINDEX16 e, WN *awn, WN *bwn, INT alex, INT blex) |
| SNL_REGION | SNL_Remove_Unity_Trip_Loop (WN *wdloop, BOOL update_access) |
| SNL_REGION | SNL_Remove_Useless_Loops (WN *wn_tree, BOOL update_access) |
| void | Remove_Useless_Loops (SNL_REGION *region) |
| void | Print_Interchange (FILE *file, WN *outer_loop, INT permutation[], INT nloops) |
| void | Prompf_Interchange (WN *wn_outer, INT permutation[], INT nloops) |
| void | Prompf_Interchanges (WN *wn_outer, INT permutation[], INT nloops) |
| void | LNO_FB_Inv_Interchange (WN *wn_outer, INT permutation[], INT nloops) |
| void | LNO_FB_MP_Tile (WN *wn_tile_loop, INT tile_loop_tripcount, WN *wn_orig_loop) |
| WN * | SNL_Permute_Loops (WN *wn_outer, WN *wn_inner, INT permutation[], INT nloops, BOOL invariant, BOOL warn_lexneg) |
| BOOL | SNL_Update_Strip_Dependence (INT current_depth, INT s, INT i_for_s, EINDEX16 e, WN *awn, WN *bwn, INT alex, INT blex) |
| WN * | Tile_Loop (WN *wn_loop, INT tile_size, INT tile_level, SNL_INV_CACHE_BLOCK_REASON reason, SYMBOL *outersym, MEM_POOL *pool) |
| SNL_REGION | SNL_Regtile_Loop (WN *outerloop, INT u, INT nloops, BOOL unroll_just_inner, EST_REGISTER_USAGE est_register_usage, SX_INFO *pinfo, INT pinfo_depth, BOOL no_further_unroll, HASH_TABLE< WN *, WN * > **loop_map_ptr=NULL, SX_INFO **wdpinfo_ptr=NULL) |
Define Documentation
| #define snl_trans_INCLUDED "snl_trans.h" |
Description:
This file contains functions and classes for the transformation of simply nested loops. Code specific to general transformation is given in snl_gen.cxx, while code specific to invariant transformation is given in snl_inv.cxx.
The actual transformation theory is discussed in doc/Mongoose /snl-transformation.mif.
The assumption is that access vectors are up to date upon entry to SNL processing. I do not keep them up-to-date during the SNL transformation process, because while they are very useful for me to gather the information I need, the information I gather is actually tailored to my needs (SNL_NEST_INFO and SNL_TRANS_INDEX_DATA). But the access vectors are used by SNL_NEST_INFO().
For loop distribution, a dependence test is supplied, and it's noted where distribution would have to occur to make things legal. Then, if is a transformation is applied that can benefit by distribution, then distribution is applied at that point.
UPDATING DU/UD INFORMATION:
For invariant nests:
-- interchange involves no changes. -- cache tiling involves making new variables for tile indices, and using them only in bounds further in. Also, the bounds for the tile index loops themselves. But all the information is right there. -- regtiling is fine, since as long as everything is up-to-date before, then the copy routines do the right thing.
For general nests:
-- Protect_Nest_With_Conditionals: easy, since this only involves defs for the variables in the bounds information. -- U_Ctiling() uses SNL_TRANS_INDEX_DATA, which is augmented to include the defs for each index variable. So as long as that data structure is passed around when doing copies, no problem. -- General_2D_Regtile. Again as long as things are up-to-date before this code, no problem.
TODO: The Fix_Do_Du_Info() is a hack. Isn't there some better way to update index variable du chains? Can't I let them all rot and recompute them at the end (they're easy)? This might be too slow. It's not well thought out about what the minimal number of calls to it would be.
Definition at line 92 of file snl_trans.h.
Function Documentation
Definition at line 644 of file snl_trans.cxx.
References FEEDBACK::Annot_loop(), STACK< T >::Bottom_nth(), Build_Doloop_Stack(), Cur_PU_Feedback, CXX_DELETE_ARRAY, CXX_NEW_ARRAY, Do_Loop_Depth(), FB_Info_Loop::freq_iterate, FB_Info_Loop::freq_positive, FB_Info_Loop::freq_zero, i, Identity_Permutation(), idx, INT, Is_True, LNO_local_pool, FEEDBACK::Query_loop(), Scale_FB_Info_Loop(), SNL_Get_Inner_Snl_Loop(), stack, FB_FREQ::Uninitialized(), FB_FREQ::Value(), and FB_FREQ::Zero().
Referenced by SNL_INV_Transforms().
Definition at line 725 of file snl_trans.cxx.
References FEEDBACK::Annot_loop(), Cur_PU_Feedback, FB_Info_Loop::freq_out, Is_True, and FEEDBACK::Query_loop().
Referenced by Processor_2D_Tile_Loop(), and Processor_3D_Tile_Loop().
Definition at line 530 of file snl_trans.cxx.
References fprintf(), i, INT, SNL_Get_Inner_Snl_Loop(), WB_Whirl_Symbol(), and WN_linenum().
Referenced by SNL_GEN_Permute_Loops(), and SNL_INV_Permute_Loops().
Definition at line 567 of file snl_trans.cxx.
References STACK< T >::Bottom_nth(), Build_Doloop_Stack(), CXX_NEW_ARRAY, Do_Loop_Depth(), i, Identity_Permutation(), INT, PROMPF_INFO::Interchange(), LNO_local_pool, Prompf_Id_Map, Prompf_Info, SNL_Get_Inner_Snl_Loop(), stack, and WN_MAP32_Get.
Referenced by Prompf_Interchanges(), and SNL_Permute_Loops().
Definition at line 598 of file snl_trans.cxx.
References STACK< T >::Bottom_nth(), Build_Doloop_Stack(), CXX_NEW_ARRAY, Do_Loop_Depth(), first, i, INT, last, NULL, Permutation_Last(), Prompf_Interchange(), PROMPF_pool, SNL_Get_Inner_Snl_Loop(), and stack.
Referenced by Distribute_Traverse(), and SNL_INV_Transforms().
| void Remove_Useless_Loops | ( | SNL_REGION * | region | ) |
Definition at line 503 of file snl_trans.cxx.
References SNL_REGION::First, SNL_REGION::Last, NULL, RUL_Region_Update(), SNL_Remove_Useless_Loops(), TRUE, wn, WN_next(), and WN_prev().
Referenced by Do_Automatic_Transformation().
Definition at line 112 of file snl_trans.cxx.
References c, CXX_NEW_ARRAY, Du_Mgr, CHAIN_ITER::First(), FmtAssert, SX_PNODE::Has_Reduction(), i, ii, INT, DEF_LIST::Loop_stmt(), LWN_ITER, LWN_WALK_TreeIter, LWN_WALK_TreeNext, MEM_local_pool, n, CHAIN_ITER::Next(), NULL, OPC_DO_LOOP, OPR_LDID, red_manager, RED_NONE, DEF_LIST::Set_loop_stmt(), SNL_DEBUG2, symbol, SX_PNODE::Symbol(), DU_MANAGER::Ud_Get_Def(), REDUCTION_MANAGER::Which_Reduction(), wn, WN_do_body, WN_opcode(), and WN_operator().
Referenced by SNL_GEN_U_Ctiling(), SNL_INV_Cache_Block(), and SNL_INV_Local_Permute_Loops().
Definition at line 188 of file snl_trans.cxx.
References Array_Dependence_Graph, Create_DEPV_ARRAY(), CXX_DELETE, Delete_DEPV_ARRAY(), dg, FmtAssert, fprintf(), DIRECTED_GRAPH16< EDGE_TYPE, VERTEX_TYPE >::Get_Edge(), DIRECTED_GRAPH16< EDGE_TYPE, VERTEX_TYPE >::Get_Next_Edge(), DIRECTED_GRAPH16< EDGE_TYPE, VERTEX_TYPE >::Get_Sink(), DIRECTED_GRAPH16< EDGE_TYPE, VERTEX_TYPE >::Get_Source(), ARRAY_DIRECTED_GRAPH16::Get_Wn(), INT, Lex_Pos_Compose(), LNO_local_pool, LWN_Get_Parent, NULL, p1, p2, ARRAY_DIRECTED_GRAPH16::Pool(), ARRAY_DIRECTED_GRAPH16::Print(), red_manager, rm, snl_debug, TFile, and REDUCTION_MANAGER::Which_Reduction().
Referenced by SNL_GEN_U_Ctiling(), SNL_INV_Cache_Block(), and SNL_INV_Local_Permute_Loops().
| WN* SNL_Permute_Loops | ( | WN * | wn_outer, | |
| WN * | wn_inner, | |||
| INT | permutation[], | |||
| INT | nloops, | |||
| BOOL | invariant, | |||
| BOOL | warn_lexneg | |||
| ) |
Definition at line 784 of file snl_trans.cxx.
References Array_Dependence_Graph, STACK< T >::Bottom_nth(), Build_Doloop_Stack(), CXX_NEW_ARRAY, dg, Do_Loop_Depth(), first, FmtAssert, i, INT, PROMPF_INFO::Is_Enabled(), last, LNO_local_pool, NULL, Permutation_Last(), Prompf_Info, Prompf_Interchange(), Repair_Bad_Dependences(), SNL_GEN_Permute_Loops(), SNL_INV_Permute_Loops(), and stack.
Referenced by Parallel_Interchange(), and Parallelize_Doacross_Loop().
| SNL_REGION SNL_Regtile_Loop | ( | WN * | outerloop, | |
| INT | u, | |||
| INT | nloops, | |||
| BOOL | unroll_just_inner, | |||
| EST_REGISTER_USAGE | est_register_usage, | |||
| SX_INFO * | pinfo, | |||
| INT | pinfo_depth, | |||
| BOOL | no_further_unroll, | |||
| HASH_TABLE< WN *, WN * > ** | loop_map_ptr = NULL, |
|||
| SX_INFO ** | wdpinfo_ptr = NULL | |||
| ) |
Definition at line 1079 of file snl_trans.cxx.
References above, Add_To_Symbol(), Array_Dependence_Graph, BOOL, buf, Create_Preg_Symbol(), CXX_DELETE, CXX_DELETE_ARRAY, CXX_NEW, CXX_NEW_ARRAY, d, DevWarn, dg, Do_Depth(), Do_Loop_Depth(), Do_Wtype(), Du_Mgr, SX_INFO::Enter(), DO_LOOP_INFO::Est_Max_Iterations_Index, FALSE, Find_Next_Innermost_Do(), CHAIN_ITER::First(), SNL_REGION::First, EST_REGISTER_USAGE::Fits(), FmtAssert, Get_Do_Loop_Info(), i, ii, SX_PNODE::ILLEGAL, Increase_By(), INT, INT64, CHAIN_ITER::Is_Empty(), PROMPF_INFO::Is_Enabled(), Is_True, Iterations(), SNL_REGION::Last, LNO_Erase_Dg_From_Here_In(), LNO_Info_Map, LNO_Outer_Unroll_Min_For_Further_Unroll, loop_id, LWN_Copy_Frequency(), LWN_Copy_Tree(), LWN_Create_Block_From_Stmts_Above(), LWN_Create_Block_From_Stmts_Below(), LWN_Delete_Tree(), LWN_Get_Parent, LWN_Insert_Block_After(), LWN_Insert_Block_Before(), LWN_Scale_Frequency(), LWN_Scale_Frequency_Tree(), LWN_Set_Parent, Make_Loop_Mapping(), n, Name, SYMBOL::Name(), CHAIN_ITER::Next(), NULL, offset, OPR_INTCONST, SX_INFO::Plist, Prompf_Id_Map, Prompf_Info, red_manager, region, PROMPF_INFO::Register_Tile(), Replace_Symbols(), SX_PNODE::SE_NOT_REQD, SX_PNODE::SE_REQD, EST_REGISTER_USAGE::Set_Fits(), SNL_Add_Du_To_Index_Ldid(), SNL_local_pool, SNL_Regtile_Loop(), SNL_UBexp(), sprintf(), Step_Size(), TRUE, SYMBOL::Type, TYPE_ID, Unmapped_Vertices_Here_Out(), REDUCTION_MANAGER::Unroll_Update(), Unrolled_DU_Update(), Valid_SNL_Region(), Wind_Down(), wn, WN_const_val(), WN_CreateBlock, WN_do_body, WN_end, WN_first(), WN_index, WN_kid0(), WN_MAP32_Get, WN_next(), WN_offset(), WN_operator(), WN_prev(), WN_st(), WN_start, and WN_step.
Referenced by SNL_GEN_2D_Regtile(), SNL_INV_Register_Tile(), and SNL_Regtile_Loop().
| SNL_REGION SNL_Remove_Unity_Trip_Loop | ( | WN * | wdloop, | |
| BOOL | update_access | |||
| ) |
Definition at line 367 of file snl_trans.cxx.
References Array_Dependence_Graph, DevWarn, Du_Mgr, SNL_REGION::First, SNL_REGION::Last, NULL, region, Remove_Unity_Trip_Loop(), and Valid_SNL_Region().
Referenced by SNL_INV_Register_Tile(), and SNL_Remove_Useless_Loops().
| SNL_REGION SNL_Remove_Useless_Loops | ( | WN * | wn_tree, | |
| BOOL | update_access | |||
| ) |
Definition at line 429 of file snl_trans.cxx.
References DevWarn, SNL_REGION::First, i, INT, Iterations(), SNL_REGION::Last, LNO_local_pool, NULL, OPC_BLOCK, OPC_DO_LOOP, region, Remove_Zero_Trip_Loop(), RUL_Region_Update(), SNL_Remove_Unity_Trip_Loop(), SNL_Remove_Useless_Loops(), Valid_SNL_Region(), wn, WN_first(), WN_kid(), WN_kid_count(), WN_next(), WN_opcode(), and WN_prev().
Referenced by Remove_Useless_Loops(), and SNL_Remove_Useless_Loops().
Definition at line 294 of file snl_trans.cxx.
References Array_Dependence_Graph, Create_DEPV_ARRAY(), Delete_DEPV_ARRAY(), dg, FALSE, fflush(), FmtAssert, fprintf(), DIRECTED_GRAPH16< EDGE_TYPE, VERTEX_TYPE >::Get_Sink(), DIRECTED_GRAPH16< EDGE_TYPE, VERTEX_TYPE >::Get_Source(), ARRAY_DIRECTED_GRAPH16::Get_Wn(), Is_Lexpos(), Is_True, DEPV_LIST::Lex_Pos_Decompose(), LNO_local_pool, neg(), NULL, DEPV_LIST::Num_Dim(), DEPV_LIST::Num_Unused_Dim(), ARRAY_DIRECTED_GRAPH16::Pool(), pos(), ARRAY_DIRECTED_GRAPH16::Print(), DEPV_ARRAY::Print(), red_manager, rm, snl_debug, TFile, TRUE, and REDUCTION_MANAGER::Which_Reduction().
Referenced by SNL_GEN_U_Ctiling(), SNL_INV_Local_Permute_Loops(), and SNL_Update_Strip_Dependence().
| BOOL SNL_Update_Strip_Dependence | ( | INT | current_depth, | |
| INT | s, | |||
| INT | i_for_s, | |||
| EINDEX16 | e, | |||
| WN * | awn, | |||
| WN * | bwn, | |||
| INT | alex, | |||
| INT | blex | |||
| ) |
Definition at line 837 of file snl_trans.cxx.
References Array_Dependence_Graph, BOOL, conservative(), Create_DEPV_ARRAY(), d, Delete_DEPV_ARRAY(), DEP, DEP_Direction(), DEP_SetDirection(), DEP_SetDistance(), DEPV_ARRAY::Depv(), DEPV_Dep, dg, dir, DIR_EQ, DIR_NEG, DIR_NEGEQ, DIR_POS, DIR_POSEQ, DIR_POSNEG, DIR_STAR, FALSE, FmtAssert, i, ii, INT, Is_True, NULL, DEPV_ARRAY::Num_Dim(), DEPV_ARRAY::Num_Unused_Dim(), DEPV_ARRAY::Num_Vec(), ARRAY_DIRECTED_GRAPH16::Pool(), SNL_Test_Reduction_Lexneg(), and TRUE.
Referenced by SNL_GEN_U_Ctiling(), and SNL_INV_Cache_Block().
| WN* Tile_Loop | ( | WN * | wn_loop, | |
| INT | tile_size, | |||
| INT | tile_level, | |||
| SNL_INV_CACHE_BLOCK_REASON | reason, | |||
| SYMBOL * | outersym, | |||
| MEM_POOL * | pool | |||
| ) |
Definition at line 1011 of file snl_trans.cxx.
References Array_Dependence_Graph, Bound_Is_Too_Messy(), Build_Doloop_Stack(), Cur_PU_Feedback, dg, Du_Mgr, FALSE, SNL_REGION::First, Get_Do_Loop_Info(), Hoist_Lower_Bound(), Hoist_Upper_Bound(), INT, INT32, SNL_REGION::Last, DO_LOOP_INFO::LB, LNO_Build_Access(), LNO_default_pool, LNO_local_pool, LWN_Get_Parent, LWN_Set_Frequency(), MAX, NULL, red_manager, region, rm, SNL_INV_Cache_Block(), stack, ti, DO_LOOP_INFO::UB, Upper_Bound_Standardize(), WN_end, WN_MAP32_Get, WN_MAP_FEEDBACK, WN_start, and WN_step.
Referenced by Parallelize_Doacross_Loop(), Processor_2D_Tile_Loop(), Processor_3D_Tile_Loop(), Scalar_Expansion_Tile(), SE_Tile_Inner_Loop(), SNL_INV_Scalar_Expand_Tile(), and WBTR_Loop_Tiling().
