Open64 (mfef90, whirl2f, and IR tools)
TAG: version-openad; SVN changeset: 916
|
00001 /* 00002 00003 Copyright (C) 2000, 2001 Silicon Graphics, Inc. All Rights Reserved. 00004 00005 This program is free software; you can redistribute it and/or modify it 00006 under the terms of version 2 of the GNU General Public License as 00007 published by the Free Software Foundation. 00008 00009 This program is distributed in the hope that it would be useful, but 00010 WITHOUT ANY WARRANTY; without even the implied warranty of 00011 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 00012 00013 Further, this software is distributed without any warranty that it is 00014 free of the rightful claim of any third person regarding infringement 00015 or the like. Any license provided herein, whether implied or 00016 otherwise, applies only to this software file. Patent licenses, if 00017 any, provided herein do not apply to combinations of this program with 00018 other software, or any other product whatsoever. 00019 00020 You should have received a copy of the GNU General Public License along 00021 with this program; if not, write the Free Software Foundation, Inc., 59 00022 Temple Place - Suite 330, Boston MA 02111-1307, USA. 00023 00024 Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pky, 00025 Mountain View, CA 94043, or: 00026 00027 http://www.sgi.com 00028 00029 For further information regarding this notice, see: 00030 00031 http://oss.sgi.com/projects/GenInfo/NoticeExplan 00032 00033 */ 00034 00035 00036 //* -*-Mode: c++;-*- (Tell emacs to use c++ mode) */ 00037 // 00038 // ==================================================================== 00039 // ==================================================================== 00040 // 00041 // $Author: 00042 // $Source: 00043 // 00044 // Revision history: 00045 // 07-Dec-96 - Original Version 00046 // 00047 // Description: 00048 // 00049 // This module contains the IPA implementation of array sections. See 00050 // the header (ipa_section.h) for more interface information. 00051 // 00052 // ==================================================================== 00053 // ==================================================================== 00054 00055 #include <elf.h> 00056 #include <sys/elf_whirl.h> 00057 #include <sys/types.h> 00058 #include <alloca.h> 00059 00060 #include "defs.h" 00061 #include "erglob.h" 00062 #include "tracing.h" 00063 #include "cxx_memory.h" 00064 #include "access_vector.h" 00065 #include "loop_info.h" 00066 #include "soe.h" 00067 #include "lno_bv.h" 00068 #include "ipl_summary.h" 00069 #include "ipl_summarize.h" 00070 #include "ipl_summarize_util.h" 00071 #include "ipl_main.h" 00072 #include "ipl_array_bread_write.h" 00073 #include "ipa_section_main.h" 00074 #include "ipa_lno_file.h" 00075 #include "ipl_lno_util.h" 00076 00077 00078 extern SUMMARY *Summary; // from IPL 00079 extern ARRAY_SUMMARY Array_Summary; // from ipl_linex 00080 00081 BOOL Trace_Sections = FALSE; 00082 00083 IVAR_ARRAY *Ivar = NULL; 00084 00085 // Maps used to carry over the loop and array access info 00086 LOOPINFO_TO_DLI_MAP* IPL_Loopinfo_Map = NULL; 00087 PROJ_REGION_TO_ACCESS_ARRAY_MAP* IPL_Access_Array_Map = NULL; 00088 00089 mINT32 00090 SYSTEM_OF_EQUATIONS::_work_cols; 00091 mINT32 00092 SYSTEM_OF_EQUATIONS::_work_rows_eq; 00093 mINT32 00094 SYSTEM_OF_EQUATIONS::_work_rows; 00095 00096 //==================================================================== 00097 // initialize ivar and ivar global arrays 00098 //==================================================================== 00099 extern void 00100 Init_ivar_arrays() 00101 { 00102 Ivar = Array_Summary_Output->Get_ivar_array(); 00103 Ipl_Summary_Symbol = Summary->Get_symbol(0); 00104 } 00105 00106 //==================================================================== 00107 // find the node in the ivar array 00108 //==================================================================== 00109 static INT32 00110 Get_ivar(const IVAR_ARRAY& iv_array, const IVAR& iv) 00111 { 00112 for (INT32 i = 0; i < iv_array.Elements(); ++i) { 00113 if (iv_array[i] == iv) { 00114 return i; 00115 } 00116 } 00117 return -1; 00118 } 00119 00120 // ----------------------------------------------------------- 00121 // The only linear symbols that are currently supported are: 00122 // named constants 00123 // global variables (possibly with offsets) 00124 // formal parameters (of the current PU, not the parent one) 00125 // ----------------------------------------------------------- 00126 static BOOL 00127 Access_vector_is_too_messy(ACCESS_VECTOR* av) 00128 { 00129 if (av->Too_Messy || 00130 av->Delinearized_Symbol || 00131 av->Contains_Non_Lin_Symb()) { 00132 return TRUE; 00133 } 00134 00135 if (av->Contains_Lin_Symb()) { 00136 00137 INTSYMB_ITER iter(av->Lin_Symb); 00138 for (INTSYMB_NODE* cur = iter.First(); 00139 !iter.Is_Empty(); 00140 cur = iter.Next()) { 00141 00142 ST* st = cur->Symbol.St(); 00143 00144 if (ST_class(st) == CLASS_CONST) { 00145 INT64 const_value; 00146 if (!Targ_Is_Integral(STC_val(st), &const_value) || 00147 const_value * cur->Coeff < INT32_MIN || 00148 const_value * cur->Coeff > INT32_MAX) { 00149 return TRUE; 00150 } 00151 } 00152 else if (ST_class(st) != CLASS_VAR) { 00153 return TRUE; 00154 } 00155 else if (ST_level(st) != GLOBAL_SYMTAB) { 00156 if ((ST_sclass(st) != SCLASS_FORMAL && 00157 ST_sclass(st) != SCLASS_FORMAL_REF) || 00158 ST_level(st) != CURRENT_SYMTAB) { 00159 return TRUE; 00160 } 00161 } 00162 } 00163 } 00164 00165 return FALSE; 00166 } 00167 00168 00169 //==================================================================== 00170 // loopinfo constructor 00171 //==================================================================== 00172 LOOPINFO::LOOPINFO(MEM_POOL* m, INT16 cd_idx) 00173 : _nest_level(0), 00174 _flags(0), 00175 _mem_pool(m), 00176 _kernel(CXX_NEW(PROJECTED_KERNEL_ARRAY(m),m)) 00177 { 00178 u1.u3._upper_linex = 0; 00179 u1.u3._lower_linex = 0; 00180 u1.u3._step_linex = 0; 00181 u1.u3._symbols = CXX_NEW(LOOP_SYMBOL_ARRAY(m), m); 00182 u1.u3._cd_idx = cd_idx; 00183 } 00184 00185 //==================================================================== 00186 // build the LINEX information from the access vector 00187 //==================================================================== 00188 LINEX* 00189 LOOPINFO::Build_linex(ACCESS_VECTOR* av) 00190 { 00191 if (!av || 00192 av->Too_Messy || 00193 av->Delinearized_Symbol || 00194 av->Contains_Non_Lin_Symb() || 00195 Access_vector_is_too_messy(av)) { 00196 return 0; 00197 } 00198 00199 LINEX* linex = CXX_NEW(LINEX(Mem_Pool()), Mem_Pool()); 00200 linex->Map_access_vector(av, FALSE, NULL); 00201 return linex; 00202 } 00203 00204 //==================================================================== 00205 // create the mapping from the do loop info which contains access 00206 // vectors to the loop-info structure 00207 //==================================================================== 00208 void 00209 LOOPINFO::Map_do_loop_info(DO_LOOP_INFO_BASE *dli) 00210 { 00211 // Enter LOOPINFO* to DO_LOOP_INFO_BASE* mapping into hash table 00212 IPL_Loopinfo_Map->Enter(this, dli); 00213 00214 Set_nest_level(dli->Get_depth()); 00215 00216 ACCESS_ARRAY* lb = dli->Get_lb(); 00217 ACCESS_ARRAY* ub = dli->Get_ub(); 00218 ACCESS_VECTOR* step = dli->Get_step(); 00219 00220 if (lb->Num_Vec() > 1 || ub->Num_Vec() > 1 || !step->Is_Const()) { 00221 if (Trace_Sections) { 00222 fprintf(TFile, "----LOOP has messy bounds---- \n"); 00223 dli->Print(TFile); 00224 fprintf(stdout, "----LOOP has messy bounds---- \n"); 00225 dli->Print(stdout); 00226 } 00227 Set_messy_bounds(); 00228 return; 00229 } 00230 00231 if (!(u1.u3._upper_linex = Build_linex(ub->Dim(0)))) { 00232 Set_messy_ub(); 00233 } 00234 if (!(u1.u3._lower_linex = Build_linex(lb->Dim(0)))) { 00235 Set_messy_lb(); 00236 } 00237 // Need to take the absolute value of the step, since we want 00238 // all array sections to have positive steps. Hence a loop 00239 // like: 00240 // do i = n, 1, -1 00241 // a(i) = 0 00242 // end do 00243 // Will have a section that looks like a(1:n:1) rather than 00244 // a(1:n:-1) (or a(n:1:-1) for that matter). 00245 INT64 const_offset = step->Const_Offset; 00246 if (step->Const_Offset < 0) { 00247 step->Const_Offset = -step->Const_Offset; 00248 } 00249 u1.u3._step_linex = Build_linex(step); 00250 step->Const_Offset = const_offset; 00251 } 00252 00253 //==================================================================== 00254 // Map an access vector to a linex 00255 // NOTE: the ordering is IMPORTANT: the loop coeff terms are first 00256 // ==================================================================== 00257 void 00258 LINEX::Map_access_vector(ACCESS_VECTOR *av, 00259 BOOL Is_LNO, 00260 IPA_LNO_READ_FILE* IPA_LNO_File) 00261 { 00262 // The precondition is that the access vector is not too messy for mapping 00263 Is_True(!Access_vector_is_too_messy(av), 00264 ("Messy access vectos can't be mapped into LINEX")); 00265 00266 BOOL processed = FALSE; 00267 00268 for (INT i = 0; i < av->Nest_Depth(); ++i) { 00269 if (av->Loop_Coeff(i) != 0) { 00270 Set_term(LTKIND_LINDEX, (COEFF)av->Loop_Coeff(i), i, 0); 00271 processed = TRUE; 00272 } 00273 } 00274 00275 if (av->Const_Offset != 0) { 00276 Set_term(LTKIND_CONST, (COEFF)av->Const_Offset, CONST_DESC, 0); 00277 processed = TRUE; 00278 } 00279 00280 if (av->Contains_Lin_Symb()) { 00281 00282 INTSYMB_ITER iter(av->Lin_Symb); 00283 for (INTSYMB_NODE* cur = iter.First(); 00284 !iter.Is_Empty(); 00285 cur = iter.Next()) { 00286 00287 // linear symbols must be named constants, globals or formals 00288 ST* st = cur->Symbol.St(); 00289 00290 if (ST_class(st) == CLASS_CONST) { 00291 INT64 const_value = Targ_To_Host(STC_val(st)); 00292 Set_term (LTKIND_CONST, (COEFF)const_value*cur->Coeff, CONST_DESC, 0); 00293 processed = TRUE; 00294 } 00295 else { 00296 Is_True(ST_class(st) == CLASS_VAR, 00297 ("LINEX::Map_access_vector(): Unexpected ST_clas")); 00298 00299 IVAR ivar; 00300 00301 if (ST_IDX_level(ST_st_idx(st)) == GLOBAL_SYMTAB) { 00302 new (&ivar) IVAR(st, cur->Symbol.WN_Offset(), cur->Symbol.Type); 00303 } 00304 else { 00305 UINT32 pos = Formal_Position(st); 00306 new (&ivar) IVAR(pos, cur->Symbol.WN_Offset(), cur->Symbol.Type); 00307 } 00308 00309 // lookup this IVAR, and add it if not found 00310 INT32 ivar_index = -1; 00311 if (!Is_LNO) { 00312 ivar_index = Get_ivar(*Ivar, ivar); 00313 00314 if (ivar_index == -1) { 00315 Ivar->AddElement(ivar); 00316 ivar_index = Ivar->Lastidx(); 00317 } 00318 } else { 00319 INT i; 00320 00321 for (i = 0; i < IPA_LNO_File->Ivar_Count(); i++) 00322 if (*(IPA_LNO_File->Ivar(i)) == ivar) 00323 break; 00324 00325 if (i < IPA_LNO_File->Ivar_Count()) { 00326 ivar_index = i; 00327 } else { 00328 ivar_index = IPA_LNO_File->Add_Translated_Ivar(ivar); 00329 } 00330 } 00331 00332 Set_term(LTKIND_IV, cur->Coeff, ivar_index, 0); 00333 processed = TRUE; 00334 } 00335 } 00336 } 00337 00338 // if no terms have been added in 00339 if (!processed) { 00340 Set_term(LTKIND_CONST, (COEFF)av->Const_Offset, CONST_DESC, 0); 00341 } 00342 } 00343 00344 //================================================================= 00345 // number of loop coefficient terms 00346 //================================================================= 00347 INT 00348 LINEX::Num_loop_coeff_terms() 00349 { 00350 INT num_loop_coeff = 0; 00351 for (INT i = 0; i <= Num_terms(); ++i) { 00352 if (Get_term(i)->Get_type() == LTKIND_LINDEX) { 00353 ++num_loop_coeff; 00354 } 00355 } 00356 return num_loop_coeff; 00357 } 00358 00359 //================================================================= 00360 // check if the coeff terms are the same 00361 //================================================================= 00362 BOOL 00363 LINEX::Loop_coeff_terms_equal(LINEX *kernel_linex) 00364 { 00365 INT i; 00366 INT num_coeffs = Num_loop_coeff_terms(); 00367 INT num_coeffs_kernel = kernel_linex->Num_loop_coeff_terms(); 00368 00369 if (num_coeffs != num_coeffs_kernel) 00370 return FALSE; 00371 00372 for (i=0; i < num_coeffs; ++i) 00373 { 00374 TERM *kernel_term = kernel_linex->Get_term(i); 00375 TERM *term = Get_term(i); 00376 FmtAssert((term->Get_type() == LTKIND_LINDEX), 00377 ("Expecting a term with kind == LTKIND_LINDEX")); 00378 if (term->Get_coeff() != kernel_term->Get_coeff() 00379 || term->Get_desc() != kernel_term->Get_desc()) 00380 return FALSE; 00381 } 00382 00383 // if we reach here then the coefficients of these terms are the same 00384 return TRUE; 00385 } 00386 00387 //==================================================================== 00388 // check to see if it has a term with this particular loop coefficient 00389 //==================================================================== 00390 BOOL 00391 LINEX::Has_loop_coeff(INT depth) 00392 { 00393 INT i; 00394 00395 for (i=0; i <= _larray.Lastidx(); ++i) 00396 { 00397 TERM *t = &(_larray)[i]; 00398 if ((t->Get_type() == LTKIND_LINDEX) && 00399 (t->Get_desc() == depth)) 00400 return TRUE; 00401 } 00402 return FALSE; 00403 } 00404 00405 00406 //=================================================================== 00407 // the kernel contains an array of LINEX structures, one for each 00408 // dimension of the array 00409 //=================================================================== 00410 LINEX_ARRAY* 00411 PROJECTED_REGION::Map_to_linex_array() 00412 { 00413 MEM_POOL* m = Mem_Pool(); 00414 LINEX_ARRAY* l = CXX_NEW(LINEX_ARRAY(m), m); 00415 PROJECTED_ARRAY* p = Get_projected_array(); 00416 00417 for (INT i = 0; i < p->Elements(); ++i) { 00418 PROJECTED_NODE* node = &(*p)[i]; 00419 FmtAssert(node->Is_unprojected(), ("Node has been projected\n")); 00420 FmtAssert(!node->Is_messy_lb(), ("Messy lower bound\n")); 00421 00422 // add a linex and copy into it 00423 LINEX* to = &(*l)[l->Newidx()]; 00424 new (to) LINEX(m); 00425 node->Get_lower_linex()->Copy(to); 00426 } 00427 00428 return l; 00429 } 00430 00431 //========================================================================== 00432 // DESCR: 00433 // Add_coupled_terms, add the coupled terms to the linex 00434 //========================================================================== 00435 void 00436 LINEX::Add_coupled_terms(LINEX* from) 00437 { 00438 for (INT i = 0; i<=from->Num_terms(); ++i) { 00439 TERM* term = from->Get_term(i); 00440 switch (term->Get_type()) { 00441 case LTKIND_NONE: 00442 case LTKIND_CONST: 00443 case LTKIND_LINDEX: 00444 case LTKIND_IV: 00445 break; 00446 case LTKIND_SUBSCR: 00447 Set_term(term); 00448 break; 00449 default: 00450 Fail_FmtAssertion("Unknown term type encountered \n"); 00451 break; 00452 } 00453 } 00454 } 00455 00456 //==================================================================== 00457 // Set_to_kernel_image, create the projected node which includes 00458 // the offset 00459 //==================================================================== 00460 void 00461 PROJECTED_NODE::Set_to_kernel_image(PROJECTED_NODE* pn_kernel, 00462 LINEX* lx_offset) 00463 { 00464 LINEX* lx_lower = pn_kernel->Get_lower_linex(); 00465 LINEX* lx_upper = pn_kernel->Get_upper_linex(); 00466 LINEX* lx_step = pn_kernel->Get_step_linex(); 00467 00468 if (lx_offset != NULL) { 00469 LINEX* lx_new_lower = lx_lower->Merge(lx_offset); 00470 Get_lower_linex()->Free_terms(); 00471 Set_lower_linex(lx_new_lower); 00472 if (lx_upper->Num_terms() >= 0) { 00473 LINEX* lx_new_upper = lx_upper->Merge(lx_offset); 00474 Get_upper_linex()->Free_terms(); 00475 Set_upper_linex(lx_new_upper); 00476 } 00477 } 00478 else { 00479 Get_lower_linex()->Free_terms(); 00480 Get_upper_linex()->Free_terms(); 00481 lx_lower->Copy(Get_lower_linex()); 00482 lx_upper->Copy(Get_upper_linex()); 00483 } 00484 Get_step_linex()->Free_terms(); 00485 lx_step->Copy(Get_step_linex()); 00486 00487 if (pn_kernel->Get_segment_length_linex() && 00488 pn_kernel->Get_segment_stride_linex()) { 00489 MEM_POOL* apool = Mem_Pool(); 00490 if (Get_segment_length_linex()) { 00491 Get_segment_length_linex()->Free_terms(); 00492 } 00493 else { 00494 Set_segment_length_linex(CXX_NEW(LINEX(apool), apool)); 00495 } 00496 if (Get_segment_stride_linex()) { 00497 Get_segment_stride_linex()->Free_terms(); 00498 } 00499 else { 00500 Set_segment_stride_linex(CXX_NEW(LINEX(apool), apool)); 00501 } 00502 pn_kernel->Get_segment_length_linex()->Copy(Get_segment_length_linex()); 00503 pn_kernel->Get_segment_stride_linex()->Copy(Get_segment_stride_linex()); 00504 } 00505 00506 if (pn_kernel->Is_unprojected()) 00507 Set_unprojected(); 00508 else 00509 Reset_is_unprojected(); 00510 } 00511 00512 //==================================================================== 00513 // project this region onto the loop 00514 // 00515 // This function handles the region projection. For uncoupled 00516 // subscript, the dimensions that are already ranges need not 00517 // be changed. 00518 // For instance: 00519 // A(1:I,I) after projection on 1<=I<=n becomes 00520 // {A(1:d,d),1<=d<=n} 00521 // 00522 // For coupled subscript, the dimensions that are already ranges 00523 // will have to be splitted if the loop index of the projection 00524 // appears in the range expressions. 00525 // For instance: 00526 // A(I:I+m,J) after projection on 1<=I<=n becomes 00527 // {A(min(1,1+m):max(m+1,m+n),J)} 00528 // and there might be some problems such as the stride of I etc. 00529 // The key issue is that after the projection, the region may not be 00530 // a convex set (there are holes in the set and the stride may not be 00531 // regular). 00532 // On the other hand, if 'I' also occurs in another dimension 00533 // A(I:I+m,I) then the projection is the same as the first case: 00534 // {A(d:d+m,d),1<=d<=n} 00535 // The key is that the access matrix cannot be singular. If it is not, 00536 // the integer lattice theory based on HNF comes to rescue. 00537 // 00538 //==================================================================== 00539 void 00540 PROJECTED_REGION::Project(INT depth, LOOPINFO* loop_info) 00541 { 00542 if (Is_messy_region()) { 00543 return; 00544 } 00545 00546 // if it is independent of the loop, there is nothing to project away 00547 PROJECTED_KERNEL* p = Get_projected_kernel(); 00548 FmtAssert(p, ("Null projected kernel encounterd\n")); 00549 if (p->Is_independent(depth)) { 00550 return; 00551 } 00552 00553 // check if the kernel has already been projected on the current loop 00554 if (p->Get_projected_level() > depth) { 00555 p->Project(depth, loop_info); 00556 } 00557 00558 if (p->Get_region() && p->Get_region()->Is_messy_region()) { 00559 Set_messy_region(); 00560 return; 00561 } 00562 00563 // after the kernel has been projected, copy the kernel and 00564 // adjust to account for the constant offset 00565 PROJECTED_ARRAY* array = Get_projected_array(); 00566 00567 for (INT i = 0; i < Get_num_dims(); ++i) { 00568 00569 PROJECTED_NODE* node = &(*array)[i]; 00570 00571 // for each dimension check if we need to update the projected node 00572 // this is only necessary if the subscript expression contains the 00573 // loop index variable 00574 // if unprojected then check the lower bound only 00575 // reset unprojected flag if we do project things away 00576 if (node->Get_lower_linex()->Has_loop_coeff(depth) || 00577 (!Is_unprojected_region() && 00578 node->Get_upper_linex()->Has_loop_coeff(depth))) { 00579 PROJECTED_NODE* pnode = p->Get_region()->Get_projected_node(i); 00580 node->Set_to_kernel_image(pnode, p->Get_Difference(i)); 00581 if (p->Get_Difference(i)) { 00582 p->Get_Difference(i)->Free_terms(); 00583 } 00584 } 00585 } 00586 00587 if (p->Get_Difference()) { 00588 p->Get_Difference()->Resetidx(); 00589 } 00590 00591 return; 00592 } 00593 00594 //=================================================================== 00595 // return the constant term of a lower linex 00596 //=================================================================== 00597 INT 00598 PROJECTED_NODE::Get_constant_term() 00599 { 00600 LINEX* lower = Get_lower_linex(); 00601 for (INT i=0; i<lower->Num_terms(); ++i) 00602 { 00603 TERM *term = lower->Get_term(i); 00604 if (term->Get_type() == LTKIND_CONST) 00605 return term->Get_coeff(); 00606 00607 } 00608 return 0; 00609 } 00610 00611 //=================================================================== 00612 // build a linex according to line 'i' of 'soe' 00613 // using the symbols in sym for linear terms. 00614 // dim = dimension of the system 00615 // depth = number of enclosing loops 00616 // which_array is used for coefficients 00617 // which_array = 0 (Work), = 1 (Eq) = 2 (Le) 00618 // is_lower_bound 00619 //=================================================================== 00620 void 00621 LINEX::Map_from_SOE(const SYSTEM_OF_EQUATIONS* soe, 00622 INT i, 00623 const LOOP_SYMBOL_ARRAY* syms, 00624 INT depth, 00625 INT dim, 00626 INT which_array, 00627 BOOL is_lower_bound) 00628 { 00629 switch (which_array) { 00630 case 0: { 00631 INT k; 00632 INT32 sign = is_lower_bound ? 1 : -1; 00633 00634 // loop index terms 00635 for (k = 0; k < depth; ++k) { 00636 if (soe->Work(i, dim+k) != 0) 00637 Set_term(LTKIND_LINDEX, sign * soe->Work(i, dim+k), k, 0); 00638 } 00639 00640 // constant term 00641 INT64 Const_Offset = -sign * soe->Work_Const(i); 00642 Set_term(LTKIND_CONST, (COEFF)Const_Offset, CONST_DESC, 0); 00643 00644 // IVAR terms 00645 for (INT iter = 0; 00646 k+dim < soe->Num_Vars() && iter < syms->Elements(); 00647 ++k, ++iter) { 00648 if (soe->Work(i, k+dim)) { 00649 Set_term(LTKIND_IV, 00650 sign * soe->Work(i,k+dim), 00651 (*syms)[iter].Ivar_Index(), 0); 00652 } 00653 } 00654 break; 00655 } 00656 00657 case 1: { 00658 const IMAT& aeq = soe->Aeq(); 00659 const INT64* beq = soe->Beq(); 00660 INT k; 00661 00662 // Must be lower_bound 00663 for (k = 0; k < depth; ++k) { 00664 if (aeq(i, dim+k) != 0) 00665 Set_term(LTKIND_LINDEX, -aeq(i, dim+k), k, 0); 00666 } 00667 00668 INT64 Const_Offset = beq[i]; 00669 Set_term(LTKIND_CONST, (COEFF)Const_Offset, CONST_DESC, 0); 00670 00671 for (INT iter=0; 00672 k+dim < soe->Num_Vars() && iter < syms->Elements(); 00673 ++k, ++iter) { 00674 if (aeq(i,k+dim)) { 00675 Set_term(LTKIND_IV, aeq(i, k+dim), (*syms)[iter].Ivar_Index(), 0); 00676 } 00677 } 00678 break; 00679 } 00680 00681 case 2: { 00682 const IMAT& ale = soe->Ale(); 00683 const INT64* ble = soe->Ble(); 00684 INT k; 00685 INT32 sign = is_lower_bound ? 1 : -1; 00686 00687 for (k = 0; k < depth; ++k) { 00688 if (ale(i, dim+k) != 0) 00689 Set_term(LTKIND_LINDEX, sign * ale(i, dim+k), k, 0); 00690 } 00691 00692 INT64 Const_Offset = -sign * ble[i]; 00693 Set_term(LTKIND_CONST, (COEFF)Const_Offset, CONST_DESC, 0); 00694 00695 for (INT iter = 0; 00696 k+dim < soe->Num_Vars() && iter < syms->Elements(); 00697 ++k, ++iter) { 00698 if (ale(i, k+dim)) { 00699 Set_term(LTKIND_IV, 00700 sign * ale(i, k+dim), 00701 (*syms)[iter].Ivar_Index(), 00702 0); 00703 } 00704 } 00705 break; 00706 } 00707 00708 default: 00709 Fail_FmtAssertion("Illegal Which Array \n"); 00710 break; 00711 } 00712 } 00713 00714 //----------------------------------------------------------------------- 00715 // NAME: LINEX::Substitute_Lindex 00716 // FUNCTION: Substitute the value of 'lx_substitute' into the LINDEX for 00717 // all occurrences of loop index number 'lindex'. 00718 //----------------------------------------------------------------------- 00719 00720 void LINEX::Substitute_Lindex(INT lindex, 00721 LINEX* lx_substitute) 00722 { 00723 INT lindex_coeff = 0; 00724 LINEX lx_temp(_larray.Get_Mem_Pool()); 00725 INT freeze_num_terms = Num_terms(); 00726 INT i; 00727 00728 for (i = 0; i <= freeze_num_terms; i++) { 00729 TERM* tm = Get_term(i); 00730 if (tm->Get_type() == LTKIND_LINDEX && tm->Get_desc() == lindex) { 00731 lindex_coeff += tm->Get_coeff(); 00732 } else { 00733 lx_temp.Set_term(tm); 00734 } 00735 } 00736 Free_terms(); 00737 for (i = 0; i <= lx_temp.Num_terms(); i++) 00738 Set_term(lx_temp.Get_term(i)); 00739 if (lindex_coeff == 0) 00740 return; 00741 for (i = 0; i <= lx_substitute->Num_terms(); i++) { 00742 TERM* tm = lx_substitute->Get_term(i); 00743 Set_term(tm->Get_type(), tm->Get_coeff() * lindex_coeff, tm->Get_desc(), 00744 tm->Get_projected_level()); 00745 } 00746 Simplify(); 00747 } 00748 00749 //================================================================== 00750 // set the region according to the SOE, pivot_row and stride 00751 //=================================================================== 00752 void 00753 PROJECTED_REGION::Set_region(SYSTEM_OF_EQUATIONS* soe, 00754 LOOP_SYMBOL_ARRAY* syms, 00755 INT strides[], 00756 INT pivot_row, 00757 INT pos, 00758 INT loop_step, 00759 INT projected_axle) 00760 { 00761 FmtAssert(soe, ("NULL SOE pointer passed to Set_Region")); 00762 00763 if (Trace_Sections) { 00764 fprintf(stdout, "PROJECTED_REGION::Set_region() BEGIN\n"); 00765 fprintf(stdout, "pivot_row = %d\n", pivot_row); 00766 fprintf(stdout, "pos = %d\n", pos); 00767 fprintf(stdout, "loop_step = %d\n", loop_step); 00768 fprintf(stdout, "projected_axle = %d\n", projected_axle); 00769 fprintf(TFile, "PROJECTED_REGION::Set_region() BEGIN\n"); 00770 fprintf(TFile, "pivot_row = %d\n", pivot_row); 00771 fprintf(TFile, "pos = %d\n", pos); 00772 fprintf(TFile, "loop_step = %d\n", loop_step); 00773 fprintf(TFile, "projected_axle = %d\n", projected_axle); 00774 } 00775 00776 Set_type(NON_MESSY_REGION); 00777 00778 // set the projected array, i.e. alloc memory for it 00779 PROJECTED_ARRAY* array = Get_projected_array(); 00780 if (!array) { 00781 array = CXX_NEW(PROJECTED_ARRAY(Mem_Pool()), Mem_Pool()); 00782 Set_projected_array(array); 00783 } 00784 00785 // now create numdim entries of the projected array 00786 INT num_dims = Get_num_dims(); 00787 INT depth = Get_depth(); 00788 array->Force_Alloc_array(num_dims); 00789 array->Setidx(num_dims-1); 00790 for (INT ii = 0; ii < num_dims; ++ii) { 00791 (*array)[ii].Init(Mem_Pool()); 00792 (*array)[ii].Set_unprojected(); 00793 } 00794 00795 // Set the stride of the pivoting axle 00796 // this is the variable that we are interested in, it is in this 00797 // particular column in the system of equations 00798 INT pivot_column = num_dims+pos; 00799 INT multiple = -soe->Aeq()(pivot_row, pivot_column); 00800 INT i; 00801 00802 for (i = 0; i < num_dims; ++i) { 00803 if (soe->Aeq()(pivot_row,i) != 0) { 00804 strides[i] = multiple*loop_step; 00805 break; 00806 } 00807 } 00808 00809 { 00810 BIT_VECTOR *ancestor_lo = CXX_NEW(BIT_VECTOR(num_dims, 00811 Array_Summary.Get_local_pool()), Array_Summary.Get_local_pool()); 00812 BIT_VECTOR *ancestor_up = CXX_NEW(BIT_VECTOR(num_dims, 00813 Array_Summary.Get_local_pool()), Array_Summary.Get_local_pool()); 00814 00815 // Set the equality axles first 00816 INT k = 0; 00817 for (i = 0; i < soe->Num_Eq_Constraints(); ++i) { 00818 if (i != pivot_row) { 00819 for (; k < num_dims; ++k) { 00820 if (k != projected_axle && soe->Aeq()(i,k) != 0) { 00821 (*array)[k].Set_linex_eq(soe, i, k, syms, depth, num_dims, 00822 strides[k]); 00823 ancestor_lo->Set(k); 00824 ancestor_up->Set(k); 00825 break; 00826 } 00827 } 00828 } 00829 } 00830 00831 // Filling the axles according to the topologic order (dependence) 00832 BOOL progress = TRUE; 00833 while (progress && 00834 ((ancestor_up->Pop_Count() != num_dims) || 00835 (ancestor_lo->Pop_Count() != num_dims))) { 00836 progress = FALSE; 00837 for (i = 0; i < soe->Num_Le_Constraints(); ++i) { 00838 INT axle = -1; 00839 for (k = 0; k < num_dims; ++k) { 00840 if (soe->Ale()(i,k) < 0 && !ancestor_lo->Test(k) || 00841 soe->Ale()(i,k) > 0 && !ancestor_up->Test(k)) { 00842 if (axle>=0) { 00843 axle = -1; 00844 break; 00845 } 00846 else { 00847 axle = k; 00848 } 00849 } 00850 } 00851 00852 if (axle >= 0) { 00853 00854 // Found one that only depends on the already converted axles. 00855 progress = TRUE; 00856 if (soe->Ale()(i,axle) < 0) { 00857 (*array)[axle].Set_linex_le(soe, i, axle, syms, depth, num_dims, 00858 strides[axle]); 00859 ancestor_lo->Set(axle); 00860 } 00861 else { 00862 (*array)[axle].Set_linex_le(soe, i, axle, syms, depth, num_dims, 00863 strides[axle]); 00864 ancestor_up->Set(axle); 00865 } 00866 (*array)[axle].Reset_is_unprojected(); 00867 } 00868 } 00869 } 00870 if (!progress) { 00871 Set_messy_region(); 00872 if (Trace_Sections) { 00873 fprintf(TFile, "PROJECTED_REGION::Set_Region: No progress\n"); 00874 fprintf(stdout, "PROJECTED_REGION::Set_Region: No progress\n"); 00875 } 00876 } 00877 } 00878 } 00879 00880 //======================================================================== 00881 // 00882 // Determine if two inequalities are actually one equality. 00883 // It returns TRUE if the vector sum of them is a zero vector. 00884 // 00885 //======================================================================== 00886 BOOL 00887 is_equality(const SYSTEM_OF_EQUATIONS *soe, const INT i, const INT j) 00888 { 00889 for (INT k = 0; k < soe->Num_Vars(); ++k) 00890 if ((soe->Work(i,k)+soe->Work(j,k)) != 0) 00891 return FALSE; 00892 00893 return (soe->Work_Const(i) + soe->Work_Const(j) == 0); 00894 } 00895 00896 //========================================================================= 00897 // set the linexs 00898 // Set_Axle in LNO's code 00899 //========================================================================= 00900 void 00901 PROJECTED_NODE::Set_linexs(const SYSTEM_OF_EQUATIONS *soe, 00902 INT i, 00903 INT j, 00904 const LOOP_SYMBOL_ARRAY* syms, 00905 INT depth, 00906 INT dim, 00907 INT stride) 00908 { 00909 INT k; 00910 BOOL Has_subscr_ltkind = FALSE; 00911 00912 // reset the node, clear all fields and existing linex structures 00913 Reset_node(); 00914 00915 LINEX* lower = Get_lower_linex(); 00916 LINEX* upper = Get_upper_linex(); 00917 LINEX* step = Get_step_linex(); 00918 00919 step->Set_term(LTKIND_CONST, abs(stride), CONST_DESC, 0); 00920 00921 // Two inequalities form an equality 00922 if (is_equality(soe, i, j)) { 00923 lower->Map_from_SOE(soe, i, syms, depth, dim, 0, TRUE); 00924 00925 // search for LTKIND = LTKIND_SUBSCR 00926 for (k = 0; k < dim; ++k) { 00927 if (soe->Work(i,k) != 0 && 2*k != i) { 00928 Has_subscr_ltkind = TRUE; 00929 break; 00930 } 00931 } 00932 00933 if (Has_subscr_ltkind) { 00934 for (k = 0; k<dim; ++k) { 00935 if (soe->Work(i,k) != 0) { 00936 lower->Set_term(LTKIND_SUBSCR, soe->Work(i,k),k,0); 00937 } 00938 } 00939 } 00940 00941 return; 00942 } 00943 00944 // Set the lower and upper bounds 00945 lower->Map_from_SOE(soe, i, syms, depth,dim, 0, TRUE); 00946 00947 for (k = 0; k < dim; ++k) { 00948 if (soe->Work(i,k) != 0 && 2*k != i) { 00949 Has_subscr_ltkind = TRUE; 00950 break; 00951 } 00952 } 00953 00954 if (Has_subscr_ltkind) { 00955 for (k = 0 ; k < dim; ++k) { 00956 if (soe->Work(i,k)) { 00957 lower->Set_term(LTKIND_SUBSCR, soe->Work(i,k),k,0); 00958 } 00959 } 00960 } 00961 00962 // reset this flag for use by upper bound 00963 Has_subscr_ltkind = FALSE; 00964 00965 upper->Map_from_SOE(soe, i, syms, depth, dim, 0, FALSE); 00966 00967 for (k = 0; k < dim; ++k) { 00968 if (soe->Work(i,k) != 0 && 2*k != i) { 00969 Has_subscr_ltkind = TRUE; 00970 break; 00971 } 00972 } 00973 00974 if (Has_subscr_ltkind) { 00975 for (k = 0; k < dim; ++k) { 00976 if (soe->Work(i,k)) { 00977 upper->Set_term(LTKIND_SUBSCR, soe->Work(i,k), k, 0); 00978 } 00979 } 00980 } 00981 } 00982 00983 00984 00985 //======================================================================== 00986 // set the linexs 00987 // Set_Axle_Eq in LNO's code 00988 //========================================================================= 00989 void 00990 PROJECTED_NODE::Set_linex_eq(const SYSTEM_OF_EQUATIONS *soe, 00991 INT i, 00992 INT j, 00993 const LOOP_SYMBOL_ARRAY *syms, 00994 INT depth, 00995 INT dim, 00996 INT stride) 00997 { 00998 INT k; 00999 01000 if (Trace_Sections) { 01001 fprintf(TFile, "Entered set_linex_eq: \n"); 01002 fprintf(stdout, "Entered set_linex_eq: \n"); 01003 } 01004 01005 // reset the node, clear all fields and existing linex structures 01006 Reset_node(); 01007 Set_unprojected(); 01008 01009 // map step to the constant linex value of stride 01010 LINEX* step = Get_step_linex(); 01011 step->Set_term(LTKIND_CONST, abs(stride), CONST_DESC, 0); 01012 if (Trace_Sections) { 01013 fprintf(TFile, "i = %d, depth = %d, dim = %d \n", i, depth, dim); 01014 fprintf(stdout, "i = %d, depth = %d, dim = %d \n", i, depth, dim); 01015 } 01016 01017 LINEX* lower = Get_lower_linex(); 01018 if (Trace_Sections) { 01019 fprintf(stdout, "lower linex before mapping is\n"); 01020 lower->Print(stdout); 01021 fprintf(TFile, "lower linex before mapping is\n"); 01022 lower->Print(TFile); 01023 } 01024 01025 lower->Map_from_SOE(soe, i, syms, depth, dim, 1, TRUE); 01026 01027 // Are there any LTKIND_SUBSCR terms 01028 BOOL has_coupled_subscript_terms = FALSE; 01029 for (k = 0; k < dim; ++k) { 01030 if (soe->Aeq()(i,k) && k != j) { 01031 has_coupled_subscript_terms = TRUE; 01032 break; 01033 } 01034 } 01035 01036 if (has_coupled_subscript_terms) { 01037 for (k=0; k< dim; ++k) { 01038 if (soe->Aeq()(i,k) && k != j) { 01039 lower->Set_term(LTKIND_SUBSCR, -soe->Aeq()(i,k), k, 0); 01040 } 01041 } 01042 } 01043 01044 if (Trace_Sections) { 01045 fprintf(TFile, "lower linex after mapping is\n"); 01046 lower->Print(TFile); 01047 fprintf(stdout, "lower linex after mapping is\n"); 01048 lower->Print(stdout); 01049 } 01050 } 01051 01052 //========================================================================= 01053 // Set_Linex_Le 01054 // in LNOs code, Set_Axle_Le 01055 //========================================================================= 01056 void 01057 PROJECTED_NODE::Set_linex_le(const SYSTEM_OF_EQUATIONS *soe, 01058 INT i, 01059 INT j, 01060 const LOOP_SYMBOL_ARRAY *syms, 01061 INT depth, 01062 INT dim, 01063 INT stride) 01064 { 01065 INT k; 01066 01067 // map step to the constant linex value of stride 01068 LINEX* step = Get_step_linex(); 01069 FmtAssert(step, ("Set_linex_le: Null step encountered\n")); 01070 step->Free_terms(); 01071 step->Set_term(LTKIND_CONST, abs(stride), CONST_DESC, 0); 01072 01073 // Set the lower bound 01074 if (soe->Ale()(i,j)<0) { 01075 if (Trace_Sections) { 01076 fprintf(TFile, "Set_linex_le: setting the lower bound\n"); 01077 fprintf(stdout, "Set_linex_le: setting the lower bound\n"); 01078 } 01079 01080 LINEX* lower = Get_lower_linex(); 01081 FmtAssert(lower, ("Set_linex_le: Null lower encountered\n")); 01082 lower->Free_terms(); 01083 lower->Map_from_SOE(soe, i, syms, depth, dim, 2, TRUE); 01084 01085 BOOL Has_subscr_ltkind = FALSE; 01086 for (k = 0; k<dim; ++k) { 01087 if (soe->Ale()(i,k) != 0 && k != j) { 01088 Has_subscr_ltkind = TRUE; 01089 break; 01090 } 01091 } 01092 01093 if (Has_subscr_ltkind) { 01094 for (k = 0; k < dim; ++k) { 01095 if (soe->Ale()(i,k) && k != j) { 01096 lower->Set_term(LTKIND_SUBSCR, soe->Ale()(i,k), k, 0); 01097 } 01098 } 01099 } 01100 } 01101 01102 else { 01103 if (Trace_Sections) { 01104 fprintf(TFile, "Set_linex_le: setting the upper bound\n"); 01105 fprintf(stdout, "Set_linex_le: setting the upper bound\n"); 01106 } 01107 01108 LINEX* upper = Get_upper_linex(); 01109 FmtAssert(upper, ("Set_linex_le: Null upper encountered\n")); 01110 upper->Free_terms(); 01111 upper->Map_from_SOE(soe, i, syms, depth,dim, 2, FALSE); 01112 01113 BOOL Has_subscr_ltkind = FALSE; 01114 for (k = 0; k<dim; ++k) { 01115 if (soe->Ale()(i,k) != 0 && k != j) { 01116 Has_subscr_ltkind = TRUE; 01117 break; 01118 } 01119 } 01120 01121 if (Has_subscr_ltkind ) { 01122 for (k = 0; k < dim; ++k) { 01123 if (soe->Ale()(i,k) && k != j) { 01124 upper->Set_term(LTKIND_SUBSCR, -soe->Ale()(i,k), k, 0); 01125 } 01126 } 01127 } 01128 } 01129 } 01130 01131 01132 //==================================================================== 01133 // create a PROJECTED_REGION from an access array 01134 //==================================================================== 01135 PROJECTED_REGION::PROJECTED_REGION(ACCESS_ARRAY* array, 01136 MEM_POOL* m, 01137 LOOPINFO* loop, 01138 BOOL in_ipl, 01139 IPA_LNO_READ_FILE* IPA_LNO_File) 01140 { 01141 mUINT8 num_dim = array->Num_Vec(); 01142 mUINT8 depth = loop ? loop->Get_nest_level()+1 : 0; 01143 INT i; 01144 01145 // initialize with defaults for unknown array regions 01146 Set_projected_array(NULL); 01147 Set_type(MESSY_REGION); 01148 Set_num_dims(num_dim); 01149 Set_depth(depth); 01150 Set_projected_kernel(NULL); 01151 Set_Mem_Pool(m); 01152 01153 // enter PROJECTED_REGION* to ACCESS_ARRAY* mapping into hash table 01154 if (in_ipl) { 01155 IPL_Access_Array_Map->Enter(this, array); 01156 } 01157 01158 // check for the cases that result in a messy region 01159 if (!array || array->Too_Messy) { 01160 return; 01161 } 01162 01163 for (i = 0; i < num_dim; ++i) { 01164 if (Access_vector_is_too_messy(array->Dim(i))) { 01165 return; 01166 } 01167 } 01168 01169 // NOW we have a non-messy region 01170 // set this region as unprojected when we first create it 01171 // when we project it then we will set it to FALSE; 01172 Set_type(NON_MESSY_REGION); 01173 Set_unprojected(); 01174 Set_projected_array(CXX_NEW(PROJECTED_ARRAY(m), m)); 01175 Get_projected_array()->Force_Alloc_array(num_dim); 01176 Get_projected_array()->Setidx(num_dim-1); 01177 01178 for (i = 0; i < num_dim; ++i) { 01179 PROJECTED_NODE* pn = Get_projected_node(i); 01180 pn->Init(m); 01181 pn->Get_lower_linex()->Map_access_vector(array->Dim(i), !in_ipl, 01182 IPA_LNO_File); 01183 pn->Set_unprojected(); 01184 } 01185 01186 // if the loop is not found, leave it unprojected 01187 if (!loop) { 01188 return; 01189 } 01190 01191 // update kernel information; add a kernel to this region 01192 BOOL match = TRUE; 01193 PROJECTED_KERNEL_ARRAY* kernels = loop->Get_kernels(); 01194 for (i = 0; i <= kernels->Lastidx(); ++i) { 01195 01196 PROJECTED_KERNEL* kernel = &(*kernels)[i]; 01197 INT j; 01198 01199 // check depth, number of dimensions, loop coeffs 01200 if (kernel->Get_depth() != depth || 01201 kernel->Get_num_dims() != num_dim) { 01202 continue; 01203 } 01204 01205 for (j = 0; j < num_dim; ++j) { 01206 // check to see if the lower linex matches up 01207 // with each LINEX in the projected kernel 01208 LINEX* lower = Get_projected_node(j)->Get_lower_linex(); 01209 LINEX* kernel_linex = kernel->Get_linex(j); 01210 if (!lower->Loop_coeff_terms_equal(kernel_linex)) { 01211 break; 01212 } 01213 } 01214 01215 if (j != num_dim) { 01216 match = FALSE; 01217 } 01218 01219 if (match) { 01220 kernel->Set_Difference(this); 01221 Set_projected_kernel(kernel); 01222 break; 01223 } 01224 } 01225 01226 // if the kernel has not been found, then create one and add it to 01227 // the list of kernels for the current loop nest 01228 if (Get_projected_kernel() == NULL) { 01229 PROJECTED_KERNEL* k = &(*kernels)[kernels->Newidx()]; 01230 k->Init(this, loop); 01231 Set_projected_kernel(k); 01232 } 01233 } 01234 01235 01236 01237 01238 //=================================================================== 01239 // compare 2 regions, 01240 // 0 ---- cannot compare 01241 // 1 ---- a <= b 01242 // 2 ---- b <= a 01243 // 3 ---- a == b 01244 //=================================================================== 01245 INT 01246 PROJECTED_REGION::Compare(PROJECTED_REGION *b) 01247 { 01248 INT i; 01249 INT result = 0; 01250 01251 if (Trace_Sections) 01252 { 01253 fprintf(TFile,"Compare two PROJECTED REGIONs \n"); 01254 b->Print(TFile); 01255 Print(TFile); 01256 fprintf(stdout,"Compare two PROJECTED REGIONs \n"); 01257 b->Print(stdout); 01258 Print(stdout); 01259 } 01260 01261 // First, the simple tests. 01262 if (Get_type() != b->Get_type()) 01263 return 0; 01264 01265 if (Get_num_dims() != b->Get_num_dims()) 01266 return 0; 01267 01268 // check if they are equivalent unprojected regions 01269 PROJECTED_ARRAY *array_a = Get_projected_array(); 01270 PROJECTED_ARRAY *array_b = b->Get_projected_array(); 01271 01272 for (i=0; i< Get_num_dims(); ++i) 01273 { 01274 PROJECTED_NODE *node_a, *node_b; 01275 node_a = &(*array_a)[i]; 01276 node_b = &(*array_b)[i]; 01277 if (!node_a->Equivalent(*node_b)) 01278 return 0; 01279 } 01280 01281 MEM_POOL *local_pool = Array_Summary.Get_local_pool(); 01282 MEM_POOL_Push(local_pool); 01283 { 01284 // Build the SOE to find the relations. 01285 SYSTEM_OF_EQUATIONS* soe = 01286 CXX_NEW(SYSTEM_OF_EQUATIONS(0, 0, Get_num_dims()+Get_depth(), 01287 local_pool), local_pool); 01288 LOOP_SYMBOL_ARRAY* syms = 01289 CXX_NEW(LOOP_SYMBOL_ARRAY(local_pool), local_pool); 01290 01291 // An array to hold the relation of each axle of 'a' and 'b' 01292 // relations[i] = 3 a._axle[i] == b._axle[i] 01293 // = 1 a._axle[i] < b._axle[i] 01294 // = 2 a._axle[i] > b._axle[i] 01295 // = 0 relation unknown 01296 for (i = 0; i < Get_num_dims(); ++i) { 01297 Add_to_SOE(this, i, soe, TRUE, syms, Get_depth(), Trace_Sections); 01298 Add_to_SOE(b, i, soe, TRUE, syms, Get_depth(), Trace_Sections); 01299 } 01300 01301 if (!soe->Copy_To_Work()) goto return_point; 01302 { 01303 INT16 * lower = CXX_NEW_ARRAY(INT16, Get_num_dims(), local_pool); 01304 INT16 * upper = CXX_NEW_ARRAY(INT16, Get_num_dims(), local_pool); 01305 01306 for (i = 0; i < Get_num_dims(); ++i) 01307 { 01308 lower[i] = soe->Simple_Redundant(4*i, 4*i+2); 01309 upper[i] = soe->Simple_Redundant(4*i+1, 4*i+3); 01310 } 01311 01312 // First test if they are all the same 01313 for (i = 0; i < Get_num_dims(); ++i) { 01314 if (lower[i]!=3 || upper[i]!=3) 01315 break; 01316 } 01317 01318 if (i==Get_num_dims()) { 01319 CXX_DELETE(lower, local_pool); 01320 CXX_DELETE(upper, local_pool); 01321 result = 3; 01322 goto return_point; 01323 } 01324 01325 BOOL exists_1 = FALSE; 01326 BOOL exists_2 = FALSE; 01327 01328 for (; i < Get_num_dims(); ++i) { 01329 exists_1 = (exists_1 || lower[i]==1 || upper[i]==1); 01330 exists_2 = (exists_2 || lower[i]==2 || upper[i]==2); 01331 if (exists_1 && exists_2) { 01332 CXX_DELETE(lower, local_pool); 01333 CXX_DELETE(upper, local_pool); 01334 result = 0; 01335 goto return_point; 01336 } 01337 } 01338 01339 CXX_DELETE(lower, local_pool); 01340 CXX_DELETE(upper, local_pool); 01341 01342 // Now, they are some undecided axles. Try to use the more powerful 01343 // (expensive) redundancy identification technique. 01344 BOOL redundant_1 = FALSE; 01345 BOOL redundant_2 = FALSE; 01346 01347 if (!exists_2) redundant_1 = soe->Prove_Redundant(0,Get_num_dims()); 01348 if (redundant_1 && exists_1) { 01349 result = 2; 01350 goto return_point; 01351 } 01352 01353 if (!exists_1) redundant_2 = soe->Prove_Redundant(1,Get_num_dims()); 01354 if (redundant_2 && exists_2) { 01355 result = 1; 01356 goto return_point; 01357 } 01358 01359 if (redundant_1 && redundant_2) { 01360 result = 3; 01361 goto return_point; 01362 } 01363 } 01364 return_point: 01365 CXX_DELETE(syms, local_pool); 01366 CXX_DELETE(soe, local_pool); 01367 01368 } 01369 MEM_POOL_Pop(local_pool); 01370 01371 return result; 01372 01373 } 01374 01375 //=================================================================== 01376 // Add a linex to the system of equations 01377 // for UB and LB, similar to Add_Access 01378 // The system of equations is setup as: 01379 // A*X + B*Y + C*Z <= b 01380 // X is a vector representing dimensions of the region 01381 // Y is a vector representing the loop indices 01382 // Z is a list of the symbolic variables in the linear term 01383 // b is a vector of constant offsets 01384 //=================================================================== 01385 void 01386 LOOPINFO::Add_bound(LINEX *l, 01387 SYSTEM_OF_EQUATIONS *soe, 01388 mUINT8 depth, 01389 INT num_dim, 01390 INT num_syms, 01391 LOOP_SYMBOL_ARRAY* sym) 01392 { 01393 INT pos, c = 0; 01394 01395 if (Trace_Sections) { 01396 fprintf(TFile, "\n Add_bound: Adding a LINEX to the SOE\n"); 01397 l->Print(TFile); 01398 fprintf(stdout, "\n Add_bound: Adding a LINEX to the SOE\n"); 01399 l->Print(stdout); 01400 } 01401 01402 // the size of the vector is = # of dimensions (for coupled 01403 // subscript values) + # of symbolic constants + # of loop indices + 1 01404 INT vector_size = num_dim + depth + num_syms; 01405 if (Trace_Sections) { 01406 fprintf(TFile, "num_dim = %d, depth = %d, num_syms = %d vector size %d \n", 01407 num_dim, depth, num_syms,vector_size); 01408 fprintf(stdout,"num_dim = %d, depth = %d, num_syms = %d vector size %d \n", 01409 num_dim, depth, num_syms,vector_size); 01410 } 01411 01412 mINT32* v = (mINT32*) alloca(sizeof(mINT32) * vector_size); 01413 bzero (v, sizeof(mINT32)*vector_size); 01414 01415 // for each term store the coeff in the right place in the 01416 // vector 01417 for (INT i=0; i<= l->Num_terms(); ++i) { 01418 TERM* term = l->Get_term(i); 01419 switch (term->Get_type()) { 01420 case LTKIND_CONST: 01421 c = term->Get_coeff(); 01422 break; 01423 01424 case LTKIND_LINDEX: 01425 // store the coefficient in the appropriate place 01426 v[num_dim+term->Get_desc()] = term->Get_coeff(); 01427 break; 01428 01429 case LTKIND_IV: 01430 pos = Locate_symbol(sym, soe, LOOP_SYMBOL(term->Get_desc())); 01431 v[num_dim+depth+pos] = term->Get_coeff(); 01432 break; 01433 01434 case LTKIND_SUBSCR: 01435 Fail_FmtAssertion("Add_bound:: LTKIND_SUBSCR not supported\n"); 01436 break; 01437 01438 case LTKIND_NONE: 01439 Fail_FmtAssertion("Add_bound:: unknown term kind LTKIND_NONE\n"); 01440 break; 01441 } 01442 } 01443 01444 if (Trace_Sections) { 01445 int k; 01446 fprintf(TFile, "vector size = %d \n", vector_size); 01447 01448 for (k=0; k<vector_size; ++k) 01449 fprintf (TFile, "v[%d] = %d \n", k, v[k]); 01450 01451 fprintf(stdout, "vector size = %d \n", vector_size); 01452 01453 for (k=0; k<vector_size; ++k) 01454 fprintf (stdout, "v[%d] = %d \n", k, v[k]); 01455 } 01456 01457 soe->Add_Le(v, c); 01458 01459 if (Trace_Sections) { 01460 fprintf(TFile,"\n Add_bound: New SOE is: \n"); 01461 soe->Print(TFile); 01462 fprintf(stdout,"\n Add_bound: New SOE is: \n"); 01463 soe->Print(stdout); 01464 } 01465 } 01466 01467 //----------------------------------------------------------------------- 01468 // NAME: LOOPINFO::Min_value 01469 // FUNCTION: Return a LINEX equal to the minimum value of the LOOPINFO's 01470 // loop index variable. Return NULL if this is too hard to compute. 01471 //----------------------------------------------------------------------- 01472 01473 LINEX* LOOPINFO::Min_value() 01474 { 01475 INT i; 01476 MEM_POOL* pool = Mem_Pool(); 01477 01478 if (Is_messy_lb()) 01479 return NULL; 01480 01481 INT lx_coeff = 0; 01482 LINEX* lx_lower = Get_lower_linex(); 01483 01484 for (i = 0; i <= lx_lower->Num_terms(); i++) { 01485 TERM* tm = lx_lower->Get_term(i); 01486 if (tm->Get_type() == LTKIND_LINDEX) { 01487 // Give up on trapezoidal loops for now. 01488 if (tm->Get_desc() != Get_nest_level()) 01489 return NULL; 01490 lx_coeff += tm->Get_coeff(); 01491 } 01492 } 01493 // No LINEX representation can include divide 01494 if (lx_coeff != -1) 01495 return NULL; 01496 01497 LINEX* lx_result = CXX_NEW(LINEX(pool), pool); 01498 for (i = 0; i <= lx_lower->Num_terms(); i++) { 01499 TERM* tm = lx_lower->Get_term(i); 01500 if (tm->Get_type() != LTKIND_LINDEX) 01501 lx_result->Set_term(tm->Get_type(), tm->Get_type() == LTKIND_CONST 01502 ? -tm->Get_coeff() : tm->Get_coeff(), tm->Get_desc(), 01503 tm->Get_projected_level()); 01504 } 01505 01506 return lx_result; 01507 } 01508 01509 //----------------------------------------------------------------------- 01510 // NAME: LOOPINFO::Max_value 01511 // FUNCTION: Return a LINEX equal to the maximum value of the LOOPINFO's 01512 // loop index variable. Return NULL if this is too hard to compute. 01513 //----------------------------------------------------------------------- 01514 01515 LINEX* LOOPINFO::Max_value() 01516 { 01517 MEM_POOL* pool = Mem_Pool(); 01518 INT i; 01519 01520 if (Is_messy_ub()) 01521 return NULL; 01522 01523 INT lx_coeff = 0; 01524 LINEX* lx_upper = Get_upper_linex(); 01525 01526 for (i = 0; i <= lx_upper->Num_terms(); i++) { 01527 TERM* tm = lx_upper->Get_term(i); 01528 if (tm->Get_type() == LTKIND_LINDEX) { 01529 // Give up on trapezoidal loops for now. 01530 if (tm->Get_desc() != Get_nest_level()) 01531 return NULL; 01532 lx_coeff += tm->Get_coeff(); 01533 } 01534 } 01535 01536 // No LINEX representation can include divide 01537 if (lx_coeff != 1) 01538 return NULL; 01539 01540 LINEX* lx_result = CXX_NEW(LINEX(pool), pool); 01541 for (i = 0; i <= lx_upper->Num_terms(); i++) { 01542 TERM* tm = lx_upper->Get_term(i); 01543 01544 if (tm->Get_type() != LTKIND_LINDEX) 01545 lx_result->Set_term(tm->Get_type(), tm->Get_type() == LTKIND_CONST 01546 ? tm->Get_coeff() : -tm->Get_coeff(), tm->Get_desc(), 01547 tm->Get_projected_level()); 01548 } 01549 01550 return lx_result; 01551 } 01552 01553 // ------------------------------------------------------- 01554 // Check if the inner loop is nested within the outer loop 01555 // ------------------------------------------------------- 01556 static BOOL 01557 Is_nested_within(WN* inner, WN* outer) 01558 { 01559 Is_True(WN_operator(inner) == OPR_DO_LOOP && 01560 WN_operator(outer) == OPR_DO_LOOP, 01561 ("Is_nested_within: Both nodes must be DO loops")); 01562 01563 for (WN* parent = LWN_Get_Parent(inner); 01564 parent; 01565 parent = LWN_Get_Parent(parent)) { 01566 if (parent == outer) { 01567 return TRUE; 01568 } 01569 } 01570 return FALSE; 01571 } 01572 01573 //================================================== 01574 // Return the number of loops surrounding this loop 01575 //================================================== 01576 static INT 01577 Get_surrounding_loop_count(LOOPINFO *l) 01578 { 01579 INT count = 1; 01580 WN* current = Get_cd_by_idx(l->Get_cd_idx())->Get_wn(); 01581 #if _RELY_ON_CD_ 01582 SUMMARY_CONTROL_DEPENDENCE* cd = Get_controlling_stmt(current); 01583 while (cd) { 01584 WN* parent = cd->Get_wn(); 01585 if (cd->Is_do_loop() && Is_nested_within(current, parent)) { 01586 ++count; 01587 current = parent; 01588 } 01589 cd = Get_controlling_stmt(parent); 01590 } 01591 #else 01592 Is_True(WN_operator(current) == OPR_DO_LOOP, 01593 ("WN for the LOOPINFO is not a OPR_DO_LOOP")); 01594 while (current = LWN_Get_Parent(current)) { 01595 if (WN_operator(current) == OPR_DO_LOOP) { 01596 ++count; 01597 } 01598 } 01599 #endif 01600 return count; 01601 } 01602 01603 //--------------------------------------------------------------- 01604 // Return the parent loop given the loopinfo of the current loop 01605 //--------------------------------------------------------------- 01606 static LOOPINFO* 01607 Get_parent(LOOPINFO *l) 01608 { 01609 WN* wn = Get_cd_by_idx(l->Get_cd_idx())->Get_wn(); 01610 SUMMARY_CONTROL_DEPENDENCE* cd = Get_controlling_stmt(wn); 01611 while (cd && !(cd->Is_do_loop() && Is_nested_within(wn, cd->Get_wn()))) { 01612 cd = Get_controlling_stmt(cd->Get_wn()); 01613 } 01614 if (cd && cd->Is_do_loop()) { 01615 return Array_Summary.Get_cfg_node_array(Get_cd_idx(cd))->Get_loopinfo(); 01616 } 01617 return NULL; 01618 } 01619 01620 01621 //=================================================================== 01622 // project the kernel 01623 // given a kernel, find its region of access AFTER all the enclosing 01624 // loops from level up are projected away 01625 //=================================================================== 01626 void 01627 PROJECTED_KERNEL::Project(mUINT8 level, LOOPINFO* loop) 01628 { 01629 if (_projected_level <= level ) return; 01630 _projected_level = level; 01631 01632 MEM_POOL* local_array_pool = Array_Summary.Get_local_pool(); 01633 01634 MEM_POOL_Push(local_array_pool); 01635 { 01636 INT num_vectors = Get_num_dims(); 01637 01638 // build the system of equations 01639 // number of variables = num of dimensions + depth? 01640 SYSTEM_OF_EQUATIONS* soe = 01641 CXX_NEW(SYSTEM_OF_EQUATIONS(0, 0, num_vectors+_depth, local_array_pool), 01642 local_array_pool); 01643 01644 LOOP_SYMBOL_ARRAY *syms = CXX_NEW(LOOP_SYMBOL_ARRAY(local_array_pool), local_array_pool); 01645 01646 INT* strides = CXX_NEW_ARRAY(INT, num_vectors, local_array_pool); 01647 INT* which_axle = CXX_NEW_ARRAY(INT, num_vectors, local_array_pool); 01648 INT eq_count = 0; 01649 INT i; 01650 01651 PROJECTED_REGION* region; 01652 // Test if the region was ever projected. 01653 if ((region = Get_region()) != NULL) { 01654 for (i = 0; i < num_vectors; ++i) { 01655 Add_to_SOE(region, i, soe, FALSE, syms, _depth, Trace_Sections); 01656 01657 LINEX* step = region->Get_projected_node(i)->Get_step_linex(); 01658 FmtAssert(step->Is_const(), ("Expecting a constant step")); 01659 strides[i] = step->Get_term(0)->Get_coeff(); 01660 if (region->Get_projected_node(i)->Is_unprojected()) { 01661 which_axle[eq_count] = i; 01662 eq_count++; 01663 } 01664 } 01665 } 01666 01667 // if region has not been projected, build the SOE from the 01668 // linex array (which contains the set of inequalities) 01669 else { 01670 for (i = 0; i < num_vectors; ++i) { 01671 INT num_syms = Ivar->Elements(); 01672 Get_linex(i)->Add_access(soe, _depth, num_vectors, i, num_syms, 01673 ACTION_EQ, syms, Trace_Sections); 01674 strides[i] = 1; 01675 which_axle[i] = i; 01676 } 01677 01678 region = CXX_NEW(PROJECTED_REGION(MESSY_REGION, _depth, num_vectors, 01679 Array_Summary.Get_array_pool()), Array_Summary.Get_array_pool()); 01680 Set_region(region); 01681 eq_count = num_vectors; 01682 } 01683 01684 // set the lower and upper bounds of the loop indices that need 01685 // to be projected 01686 INT pivot_row; 01687 INT step; 01688 INT num_do_loops = Get_surrounding_loop_count(loop); 01689 INT endloop = num_do_loops - level; 01690 01691 LOOPINFO *cur_loop = loop; 01692 for (i = 0 ; i < endloop; ++i) { 01693 if (cur_loop->Is_messy_any_bounds()) { 01694 if (Trace_Sections) { 01695 fprintf(TFile, "Messy bounds for loop during projection"); 01696 cur_loop->Print(TFile); 01697 fprintf(stdout, "Messy bounds for loop during projection"); 01698 cur_loop->Print(stdout); 01699 } 01700 goto pop_and_return; 01701 } 01702 else { 01703 LINEX *step_linex = cur_loop->Get_step_linex(); 01704 01705 FmtAssert(!cur_loop->Is_messy_step(), 01706 ("Project: expecting non-messy step ")); 01707 FmtAssert(step_linex->Is_const(), 01708 ("Project: step is not a constant \n")); 01709 01710 step = step_linex->Get_term(0)->Get_coeff(); 01711 01712 // check if any of the loop bounds are messy 01713 // if they are then we cannot project away anything useful 01714 INT num_syms = Ivar->Elements(); 01715 01716 if ( !cur_loop->Is_messy_lb() ) 01717 cur_loop->Add_bound(cur_loop->Get_lower_linex(), soe, 01718 _depth, num_vectors, num_syms, syms); 01719 01720 if ( !cur_loop->Is_messy_ub() ) 01721 cur_loop->Add_bound(cur_loop->Get_upper_linex(), soe, 01722 _depth, num_vectors, num_syms, syms); 01723 01724 // BOOL is_inconsistent = FALSE; 01725 01726 if (Trace_Sections) { 01727 fprintf(TFile, "Num vectors = %d \n", num_vectors); 01728 fprintf(TFile, "Base = %d \n", num_do_loops-i-1); 01729 fprintf(stdout, "Num vectors = %d \n", num_vectors); 01730 fprintf(stdout, "Base = %d \n", num_do_loops-i-1); 01731 } 01732 pivot_row = soe->Change_Base(num_vectors, 01733 num_do_loops - i - 1, 01734 local_array_pool); 01735 01736 if (Trace_Sections) { 01737 fprintf(TFile, "After base change, the SOE is"); 01738 soe->Print(TFile); 01739 fprintf(stdout, "After base change, the SOE is"); 01740 soe->Print(stdout); 01741 } 01742 01743 if (pivot_row < 0) { 01744 if (Trace_Sections) { 01745 fprintf(TFile, "pivot row < 0 during projection"); 01746 cur_loop->Print(TFile); 01747 fprintf(stdout, "pivot row < 0 during projection"); 01748 cur_loop->Print(stdout); 01749 } 01750 goto pop_and_return; 01751 } 01752 } 01753 cur_loop = Get_parent(cur_loop); 01754 } 01755 FmtAssert(pivot_row >= 0 && pivot_row < eq_count, 01756 ("PROJECTED_KERNEL::Project(): Invalid indexing of which_axle[]")); 01757 region->Set_region(soe, syms, strides, 01758 pivot_row, level, step, which_axle[pivot_row]); 01759 01760 if (Trace_Sections) { 01761 fprintf(TFile, "PROJECTED_KERNEL:: region generated is: \n"); 01762 if (region) { 01763 region->Print(TFile); 01764 } 01765 fprintf(stdout, "PROJECTED_KERNEL:: region generated is: \n"); 01766 if (region) { 01767 region->Print(stdout); 01768 } 01769 } 01770 } 01771 01772 pop_and_return: 01773 MEM_POOL_Pop(local_array_pool); 01774 } 01775 01776 01777 //=================================================================== 01778 // create a projected kernel given the initial region of the array 01779 //=================================================================== 01780 void 01781 PROJECTED_KERNEL::Init(PROJECTED_REGION* a, LOOPINFO* loop) 01782 { 01783 INT i; 01784 bzero(this, sizeof(PROJECTED_KERNEL)); 01785 _mem_pool = a->Mem_Pool(); 01786 _depth = loop->Get_nest_level() + 1; 01787 _projected_level = _depth + 1; 01788 _is_independent = CXX_NEW_ARRAY(BOOL,_depth,Array_Summary.Get_array_pool()); 01789 01790 for (i = 0; i < _depth; ++i) { 01791 _is_independent[i] = TRUE; 01792 } 01793 01794 _array = a->Map_to_linex_array(); 01795 _difference = CXX_NEW(LINEX_ARRAY(Array_Summary.Get_array_pool()), 01796 Array_Summary.Get_array_pool()); 01797 01798 // go through each dimension, get the lower linex since this 01799 // is the one that is set given that the node has not been 01800 // projected away 01801 PROJECTED_ARRAY* p = a->Get_projected_array(); 01802 for (i = 0; i < p->Elements(); ++i) { 01803 PROJECTED_NODE *node = &(*p)[i]; 01804 01805 FmtAssert((node->Is_unprojected()), (" Node has been projected\n")); 01806 FmtAssert(!(node->Is_messy_lb()), (" Messy lower bound\n")); 01807 01808 LINEX* lower = node->Get_lower_linex(); 01809 for (INT j = 0; j <= lower->Num_terms(); ++j) { 01810 TERM* term = lower->Get_term(j); 01811 // check if the term kind is one of the loop index 01812 // variables. If it is then set the is_independent to false 01813 // for that particular loop 01814 if (term->Get_type() == LTKIND_LINDEX) { 01815 _is_independent[term->Get_desc()] = FALSE; 01816 } 01817 } 01818 } 01819 } 01820 01821 //=================================================================== 01822 // initialize the region arrays 01823 //=================================================================== 01824 void 01825 REGION_ARRAYS::Init(mINT32 index, mINT32 element_size, MEM_POOL *m) 01826 { 01827 u1._regions = CXX_NEW(PROJECTED_REGION_INFO_ARRAY(m), m); 01828 _type = 0; 01829 _sym_index = index; 01830 _element_size = element_size; 01831 } 01832 01833 //=================================================================== 01834 // Copy the relevant fields over to the new regions array 01835 //=================================================================== 01836 void 01837 REGION_ARRAYS::Copy_write(REGION_ARRAYS *r) 01838 { 01839 Set_type(r->Get_type()); 01840 Set_sym_id(r->Get_sym_id()); 01841 Set_element_size(r->Get_element_size()); 01842 } 01843 01844 //=================================================================== 01845 // kill set for array regions 01846 //=================================================================== 01847 void 01848 CFG_NODE_INFO::Add_def_array(PROJECTED_REGION* p, 01849 mINT32 element_size, 01850 mINT32 sym_index) 01851 { 01852 ARRAY_OF_REGION_ARRAYS *def = Get_def_array(); 01853 01854 // search for it in the list of arrays 01855 PROJECTED_REGION_INFO_ARRAY* proj_array; 01856 for (INT i = 0; i <= def->Lastidx(); ++i) { 01857 REGION_ARRAYS* region_array = &(*def)[i]; 01858 if (region_array->Get_sym_id() == sym_index) { 01859 // add the projected region to the array 01860 proj_array = region_array->Get_projected_region_array(); 01861 INT id = proj_array->Newidx(); 01862 (*proj_array)[id].Set_projected_region(p); 01863 return; 01864 } 01865 } 01866 // if not found, extend the def array and add it in 01867 INT idx = def->Newidx(); 01868 REGION_ARRAYS *r = &(*def)[idx]; 01869 r->Init(sym_index, element_size, Array_Summary.Get_array_pool()); 01870 r->Set_is_def(); 01871 proj_array = r->Get_projected_region_array(); 01872 idx = proj_array->Newidx(); 01873 (*proj_array)[idx].Set_projected_region(p); 01874 01875 if (Trace_Sections) { 01876 fprintf(TFile, "adding array kill projected region node \n"); 01877 r->Print(TFile); 01878 fprintf(TFile, "finished adding array kill node \n"); 01879 fprintf(stdout, "adding array kill projected region node \n"); 01880 r->Print(stdout); 01881 fprintf(stdout, "finished adding array kill node \n"); 01882 } 01883 } 01884 01885 //=================================================================== 01886 // kill set for array regions 01887 //=================================================================== 01888 void 01889 CFG_NODE_INFO::Add_may_def_array(PROJECTED_REGION* p, 01890 mINT32 element_size, 01891 mINT32 sym_index) 01892 { 01893 INT i; 01894 ARRAY_OF_REGION_ARRAYS *def = Get_def_array(); 01895 01896 p->Set_is_may_kill(); 01897 // search for it in the list of arrays 01898 PROJECTED_REGION_INFO_ARRAY* proj_array; 01899 for (i = 0; i <= def->Lastidx(); ++i) { 01900 REGION_ARRAYS* region_array = &(*def)[i]; 01901 if (region_array->Get_sym_id() == sym_index) { 01902 // add the projected region to the array 01903 proj_array = region_array->Get_projected_region_array(); 01904 INT id = proj_array->Newidx(); 01905 (*proj_array)[id].Set_projected_region(p); 01906 return; 01907 } 01908 } 01909 // if not found, extend the use array and add it in 01910 INT idx = def->Newidx(); 01911 REGION_ARRAYS *r = &(*def)[idx]; 01912 r->Init(sym_index, element_size, Array_Summary.Get_array_pool()); 01913 r->Set_is_def(); 01914 proj_array = r->Get_projected_region_array(); 01915 idx = proj_array->Newidx(); 01916 (*proj_array)[idx].Set_projected_region(p); 01917 01918 if (Trace_Sections) { 01919 fprintf(TFile, "adding array kill projected region node \n"); 01920 r->Print(TFile); 01921 fprintf(TFile, "finished adding array kill node \n"); 01922 fprintf(stdout, "adding array kill projected region node \n"); 01923 r->Print(stdout); 01924 fprintf(stdout, "finished adding array kill node \n"); 01925 } 01926 } 01927 01928 //=================================================================== 01929 // upwardly exposed use set for for array regions 01930 //=================================================================== 01931 void 01932 CFG_NODE_INFO::Add_use_array(PROJECTED_REGION *p, 01933 mINT32 element_size, 01934 mINT32 sym_index) 01935 01936 { 01937 INT i; 01938 ARRAY_OF_REGION_ARRAYS *use = Get_use_array(); 01939 01940 // search for it in the list of arrays 01941 PROJECTED_REGION_INFO_ARRAY* proj_array; 01942 for (i = 0; i <= use->Lastidx(); ++i) { 01943 REGION_ARRAYS* region_array = &(*use)[i]; 01944 if (region_array->Get_sym_id() == sym_index) { 01945 // add the projected region to the array 01946 proj_array = region_array->Get_projected_region_array(); 01947 INT id = proj_array->Newidx(); 01948 (*proj_array)[id].Set_projected_region(p); 01949 return; 01950 } 01951 } 01952 // if not found, extend the use array and add it in 01953 INT idx = use->Newidx(); 01954 REGION_ARRAYS *r = &(*use)[idx]; 01955 r->Init(sym_index, element_size, Array_Summary.Get_array_pool()); 01956 r->Set_is_use(); 01957 proj_array = r->Get_projected_region_array(); 01958 idx = proj_array->Newidx(); 01959 (*proj_array)[idx].Set_projected_region(p); 01960 } 01961 01962 //=================================================================== 01963 // upwardly exposed use set for for array regions 01964 //=================================================================== 01965 void 01966 CFG_NODE_INFO::Add_may_use_array(PROJECTED_REGION *p, 01967 mINT32 element_size, 01968 mINT32 sym_index) 01969 { 01970 INT i; 01971 ARRAY_OF_REGION_ARRAYS *use = Get_use_array(); 01972 p->Set_is_may_use(); 01973 01974 // search for it in the list of arrays 01975 PROJECTED_REGION_INFO_ARRAY* proj_array; 01976 for (i = 0; i <= use->Lastidx(); ++i) { 01977 REGION_ARRAYS* region_array = &(*use)[i]; 01978 if (region_array->Get_sym_id() == sym_index) { 01979 // add the projected region to the array 01980 proj_array = region_array->Get_projected_region_array(); 01981 INT id = proj_array->Newidx(); 01982 (*proj_array)[id].Set_projected_region(p); 01983 return; 01984 } 01985 } 01986 01987 // if not found, extend the use array and add it in 01988 INT idx = use->Newidx(); 01989 REGION_ARRAYS *r = &(*use)[idx]; 01990 r->Init(sym_index, element_size, Array_Summary.Get_array_pool()); 01991 r->Set_is_use(); 01992 proj_array = r->Get_projected_region_array(); 01993 idx = proj_array->Newidx(); 01994 (*proj_array)[idx].Set_projected_region(p); 01995 } 01996 01997 //=================================================================== 01998 // store the array sections passed 01999 //=================================================================== 02000 void 02001 CFG_NODE_INFO::Add_array_param(PROJECTED_REGION *p, 02002 mINT32 sym_index, 02003 mINT32 element_size, 02004 INT16 callsite_id, 02005 INT16 actual_id) 02006 { 02007 ARRAY_OF_REGION_ARRAYS *calls = Get_param_array(); 02008 02009 p->Set_is_passed(); 02010 if (Trace_Sections) { 02011 fprintf(TFile, "Callsite id = %d, actual_id = %d \n", 02012 callsite_id, actual_id); 02013 fprintf(stdout, "Callsite id = %d, actual_id = %d \n", 02014 callsite_id, actual_id); 02015 } 02016 02017 p->Set_callsite_id(callsite_id); 02018 p->Set_actual_id(actual_id); 02019 02020 // search for it in the list of arrays 02021 PROJECTED_REGION_INFO_ARRAY* proj_array; 02022 02023 // extend the array and add it in 02024 INT call_idx = calls->Newidx(); 02025 REGION_ARRAYS *r = &(*calls)[call_idx]; 02026 r->Init(sym_index, element_size, Array_Summary.Get_array_pool()); 02027 r->Set_is_passed(); 02028 proj_array = r->Get_projected_region_array(); 02029 INT idx = proj_array->Newidx(); 02030 (*proj_array)[idx].Set_projected_region(p); 02031 SUMMARY_CALLSITE* callsite = Summary->Get_callsite(callsite_id); 02032 INT actual_index = callsite->Get_actual_index() + actual_id; 02033 SUMMARY_ACTUAL* actual = Summary->Get_actual(actual_index); 02034 actual->Set_pass_type(PASS_ARRAY_SECTION); 02035 actual->Set_index(call_idx); 02036 } 02037 02038 //=================================================================== 02039 // store the array sections passed 02040 //=================================================================== 02041 void 02042 CFG_NODE_INFO::Add_formal_array(PROJECTED_REGION *p, 02043 mINT32 element_size, 02044 mINT32 idx_symbol, 02045 mINT32 idx_formal) 02046 { 02047 ARRAY_OF_REGION_ARRAYS* ara_formal = Get_formal_array(); 02048 p->Set_is_formal(); 02049 INT formal_idx = ara_formal->Newidx(); 02050 REGION_ARRAYS* r = &(*ara_formal)[formal_idx]; 02051 r->Init(idx_symbol, element_size, Array_Summary.Get_array_pool()); 02052 r->Set_is_formal(); 02053 PROJECTED_REGION_INFO_ARRAY* proj_array = r->Get_projected_region_array(); 02054 INT idx = proj_array->Newidx(); 02055 (*proj_array)[idx].Set_projected_region(p); 02056 SUMMARY_FORMAL* sf = Summary->Get_formal(idx_formal); 02057 sf->Set_region_index(formal_idx); 02058 } 02059 02060 //=================================================================== 02061 // upwardly exposed use set for scalars 02062 //=================================================================== 02063 void 02064 CFG_NODE_INFO::Add_scalar_use(mINT32 id) 02065 { 02066 INT i; 02067 INT_ARRAY* use; 02068 use = Get_scalar_use_array(); 02069 02070 for (i=0; i<=use->Lastidx();++i) 02071 { 02072 SCALAR_INFO *val = &(*use)[i]; 02073 if (val->Get_id() == id) 02074 { 02075 val->Set_use(); 02076 02077 // set the euse bit, if the scalar is not killed or modified 02078 // this means that there is an exposed use in the node of 02079 // the cfg 02080 if (!val->Is_kill() && !val->Is_may_kill()) 02081 val->Set_euse(); 02082 return; 02083 } 02084 } 02085 02086 i = use->Newidx(); 02087 SCALAR_INFO* v = &(*use)[i]; 02088 v->Init(); 02089 v->Set_id(id); 02090 v->Set_use(); 02091 // if the scalar is not found, then the euse bit must be set 02092 v->Set_euse(); 02093 } 02094 02095 //=================================================================== 02096 // kill set for scalars 02097 //=================================================================== 02098 void 02099 CFG_NODE_INFO::Add_scalar_def(mINT32 id) 02100 { 02101 INT i; 02102 INT_ARRAY* def; 02103 def = Get_scalar_def_array(); 02104 02105 for (i=0; i<=def->Lastidx();++i) 02106 { 02107 SCALAR_INFO *val = &(*def)[i]; 02108 if (val->Get_id() == id) 02109 { 02110 val->Set_kill(); 02111 return; 02112 } 02113 } 02114 02115 i = def->Newidx(); 02116 SCALAR_INFO* v = &(*def)[i]; 02117 v->Init(); 02118 v->Set_id(id); 02119 v->Set_kill(); 02120 02121 } 02122 02123 //=================================================================== 02124 // may kill set for scalars 02125 //=================================================================== 02126 void 02127 CFG_NODE_INFO::Add_scalar_may_def(mINT32 id) 02128 { 02129 INT i; 02130 INT_ARRAY* def; 02131 def = Get_scalar_def_array(); 02132 02133 for (i=0; i<=def->Lastidx();++i) 02134 { 02135 SCALAR_INFO *val = &(*def)[i]; 02136 if (val->Get_id() == id) 02137 { 02138 val->Set_may_kill(); 02139 return; 02140 } 02141 } 02142 02143 i = def->Newidx(); 02144 SCALAR_INFO* v = &(*def)[i]; 02145 v->Init(); 02146 v->Set_id(id); 02147 v->Set_may_kill(); 02148 02149 } 02150 02151 //=================================================================== 02152 // kill set for scalars 02153 //=================================================================== 02154 void 02155 CFG_NODE_INFO::Add_scalar_may_use(mINT32 id) 02156 { 02157 INT i; 02158 INT_ARRAY* def; 02159 def = Get_scalar_def_array(); 02160 02161 for (i=0; i<=def->Lastidx();++i) 02162 { 02163 SCALAR_INFO *val = &(*def)[i]; 02164 if (val->Get_id() == id) 02165 { 02166 val->Set_may_use(); 02167 return; 02168 } 02169 } 02170 02171 i = def->Newidx(); 02172 SCALAR_INFO* v = &(*def)[i]; 02173 v->Init(); 02174 v->Set_id(id); 02175 v->Set_may_use(); 02176 02177 } 02178 02179 //=================================================================== 02180 // kill set for scalars 02181 //=================================================================== 02182 void 02183 CFG_NODE_INFO::Add_scalar_may_reduc(mINT32 id) 02184 { 02185 INT i; 02186 INT_ARRAY* def; 02187 def = Get_scalar_def_array(); 02188 02189 for (i=0; i<=def->Lastidx();++i) 02190 { 02191 SCALAR_INFO *val = &(*def)[i]; 02192 if (val->Get_id() == id) 02193 { 02194 val->Set_may_reduc(); 02195 return; 02196 } 02197 } 02198 02199 i = def->Newidx(); 02200 SCALAR_INFO* v = &(*def)[i]; 02201 v->Init(); 02202 v->Set_id(id); 02203 v->Set_may_reduc(); 02204 02205 } 02206 02207 //=================================================================== 02208 // reduc set for scalars 02209 //=================================================================== 02210 void 02211 CFG_NODE_INFO::Add_scalar_reduc(mINT32 id) 02212 { 02213 INT i; 02214 INT_ARRAY* reduc; 02215 reduc = Get_scalar_reduc_array(); 02216 02217 for (i=0; i<=reduc->Lastidx();++i) 02218 { 02219 SCALAR_INFO *val = &(*reduc)[i]; 02220 if (val->Get_id() == id) 02221 { 02222 val->Set_reduc(); 02223 return; 02224 } 02225 } 02226 02227 i = reduc->Newidx(); 02228 02229 SCALAR_INFO* v = &(*reduc)[i]; 02230 v->Init(); 02231 v->Set_id(id); 02232 v->Set_reduc(); 02233 02234 } 02235 02236 //=================================================================== 02237 // set scalar passed for reference parameters 02238 //=================================================================== 02239 INT 02240 CFG_NODE_INFO::Add_scalar_ref_passed(mINT32 id, mINT16 callsite_id) 02241 { 02242 INT i; 02243 INT_ARRAY* scalar_array; 02244 scalar_array = Get_scalar_array(); 02245 02246 for (i=0; i<=scalar_array->Lastidx();++i) 02247 { 02248 SCALAR_INFO *val = &(*scalar_array)[i]; 02249 if (val->Get_id() == id) 02250 { 02251 val->Set_passed_ref(); 02252 // record the last callsite id for nodes that have not 02253 // been killed, since this is used in the case of exposed use 02254 if ((val->Get_callsite_id() == 0) && (!val->Is_kill())) 02255 { 02256 val->Set_callsite_id(callsite_id); 02257 02258 } 02259 return i; 02260 } 02261 } 02262 02263 i = scalar_array->Newidx(); 02264 SCALAR_INFO* v = &(*scalar_array)[i]; 02265 v->Init(); 02266 v->Set_id(id); 02267 v->Set_passed_ref(); 02268 v->Set_callsite_id(callsite_id); 02269 02270 return i; 02271 } 02272 02273 02274 //=================================================================== 02275 // set scalar passed for reference parameters 02276 //=================================================================== 02277 INT 02278 CFG_NODE_INFO::Add_scalar_ref_may_passed(mINT32 id, mINT16 callsite_id) 02279 { 02280 INT i; 02281 INT_ARRAY* scalar_array; 02282 scalar_array = Get_scalar_array(); 02283 02284 for (i=0; i<=scalar_array->Lastidx();++i) 02285 { 02286 SCALAR_INFO *val = &(*scalar_array)[i]; 02287 if (val->Get_id() == id) 02288 { 02289 val->Set_may_passed_ref(); 02290 if (val->Get_callsite_id() == 0) 02291 val->Set_callsite_id(callsite_id); 02292 return i; 02293 } 02294 } 02295 02296 i = scalar_array->Newidx(); 02297 SCALAR_INFO* v = &(*scalar_array)[i]; 02298 v->Init(); 02299 v->Set_id(id); 02300 v->Set_may_passed_ref(); 02301 v->Set_callsite_id(callsite_id); 02302 return i; 02303 } 02304 02305 //=================================================================== 02306 // reduc set for arrays 02307 //=================================================================== 02308 void 02309 CFG_NODE_INFO::Add_array_reduc(mINT32 id) 02310 { 02311 INT i; 02312 INT_ARRAY* reduc; 02313 reduc = Get_array_reduc(); 02314 02315 for (i=0; i<=reduc->Lastidx();++i) 02316 { 02317 SCALAR_INFO *val = &(*reduc)[i]; 02318 if (val->Get_id() == id) 02319 { 02320 val->Set_array_reduc(); 02321 return; 02322 } 02323 } 02324 02325 i = reduc->Newidx(); 02326 SCALAR_INFO* v = &(*reduc)[i]; 02327 v->Init(); 02328 v->Set_id(id); 02329 v->Set_array_reduc(); 02330 02331 } 02332 02333 02334 //=================================================================== 02335 // reduc set for arrays 02336 //=================================================================== 02337 void 02338 CFG_NODE_INFO::Add_array_may_reduc(mINT32 id) 02339 { 02340 INT i; 02341 INT_ARRAY* reduc; 02342 reduc = Get_array_reduc(); 02343 02344 for (i=0; i<=reduc->Lastidx();++i) 02345 { 02346 SCALAR_INFO *val = &(*reduc)[i]; 02347 if (val->Get_id() == id) 02348 { 02349 val->Set_array_may_reduc(); 02350 return; 02351 } 02352 } 02353 02354 i = reduc->Newidx(); 02355 SCALAR_INFO* v = &(*reduc)[i]; 02356 v->Init(); 02357 v->Set_id(id); 02358 v->Set_array_may_reduc(); 02359 02360 } 02361 02362 //--------------------------------------------------------------------- 02363 // get an ivar 02364 //--------------------------------------------------------------------- 02365 IVAR* 02366 ARRAY_SUMMARY::Get_ivar_array(INT i) 02367 { 02368 FmtAssert(i <= _ivar->Lastidx(),("illegal ivar index \n")); 02369 return &(*_ivar)[i]; 02370 } 02371 02372 //--------------------------------------------------------------------- 02373 // get a term 02374 //--------------------------------------------------------------------- 02375 TERM* 02376 ARRAY_SUMMARY::Get_term_array(INT i) 02377 { 02378 FmtAssert(i <= _term_array->Lastidx(),("illegal term index \n")); 02379 return &(*_term_array)[i]; 02380 } 02381 02382 //--------------------------------------------------------------------- 02383 // get a projected array 02384 //--------------------------------------------------------------------- 02385 PROJECTED_NODE* 02386 ARRAY_SUMMARY::Get_projected_array(INT i) 02387 { 02388 FmtAssert(i <= _project_nodes->Lastidx(),("illegal project index\n")); 02389 return &(*_project_nodes)[i]; 02390 } 02391 02392 //--------------------------------------------------------------------- 02393 // get a projected region array 02394 //--------------------------------------------------------------------- 02395 PROJECTED_REGION* 02396 ARRAY_SUMMARY::Get_projected_region_array(INT i) 02397 { 02398 FmtAssert(i <= _projected_regions->Lastidx(),("illegal region index\n")); 02399 return &(*_projected_regions)[i]; 02400 } 02401 02402 //--------------------------------------------------------------------- 02403 // get a region array 02404 //--------------------------------------------------------------------- 02405 REGION_ARRAYS* 02406 ARRAY_SUMMARY::Get_region_array(INT i) 02407 { 02408 FmtAssert(i <= _region_arrays->Lastidx(),("illegal region array index\n")); 02409 return &(*_region_arrays)[i]; 02410 } 02411 02412 //--------------------------------------------------------------------- 02413 // get a cfg node array 02414 //--------------------------------------------------------------------- 02415 CFG_NODE_INFO* 02416 ARRAY_SUMMARY::Get_cfg_node_array(INT i) 02417 { 02418 FmtAssert(i <= _cfg_nodes->Lastidx(),("illegal cfg node index\n")); 02419 return &(*_cfg_nodes)[i]; 02420 } 02421 02422 //--------------------------------------------------------------------- 02423 // get a loopinfo array 02424 //--------------------------------------------------------------------- 02425 LOOPINFO* 02426 ARRAY_SUMMARY::Get_loopinfo_array(INT i) 02427 { 02428 FmtAssert(i <= _loop_nodes->Lastidx(),("illegal loopinfo index\n")); 02429 return &(*_loop_nodes)[i]; 02430 } 02431 02432 //--------------------------------------------------- 02433 // for array section tlogs record the following: 02434 // 1) number of LTKIND_CONST terms 02435 // 2) number of LTKIND_LINDEX terms 02436 // 4) number of LTKIND_IV terms 02437 // 5) number of LTKIND_SUBSCR terms 02438 //--------------------------------------------------- 02439 void 02440 ARRAY_SUMMARY::Record_tlogs(TERM_ARRAY *tarray, INT offset) 02441 { 02442 TLOG_INFO* tlog = Get_tlog_info(); 02443 //TERM_ARRAY *tarray = Get_term_array(); 02444 if (tarray) 02445 { 02446 for (INT i=offset; i<=tarray->Lastidx();++i) 02447 { 02448 TERM *t = &(*tarray)[i]; 02449 switch (t->Get_type()) 02450 { 02451 case LTKIND_CONST: 02452 tlog->Set_cterm_count(tlog->Get_cterm_count()+1); 02453 break; 02454 02455 case LTKIND_LINDEX: 02456 tlog->Set_lterm_count(tlog->Get_lterm_count()+1); 02457 break; 02458 02459 case LTKIND_IV: 02460 tlog->Set_iv_term_count(tlog->Get_iv_term_count()+1); 02461 break; 02462 02463 case LTKIND_SUBSCR: 02464 tlog->Set_sub_term_count(tlog->Get_sub_term_count()+1); 02465 break; 02466 } 02467 } 02468 } 02469 } 02470 02471 //----------------------------------------------------------------------- 02472 // NAME: PROJECTED_KERNEL::Set_Difference 02473 // FUNCTION: Set the "_difference" field in the PROJECTED_KERNEL to 02474 // 'pr' - that PROJECTED_KERNEL. 02475 //----------------------------------------------------------------------- 02476 02477 void PROJECTED_KERNEL::Set_Difference(PROJECTED_REGION* pr) 02478 { 02479 for (INT i = 0; i < Get_num_dims(); i++) { 02480 LINEX* lx_kernel = Get_linex(i); 02481 LINEX* lx_region = pr->Get_projected_node(i)->Get_lower_linex(); 02482 LINEX* lx_diff = lx_region->Subtract(lx_kernel); 02483 INT idx = _difference->Newidx(); 02484 LINEX* lx_new = &(*_difference)[idx]; 02485 lx_new->Init(Array_Summary.Get_array_pool()); 02486 lx_diff->Copy(lx_new); 02487 } 02488 }