00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057 #include <sys/types.h>
00058 #include <alloca.h>
00059
00060 #include "defs.h"
00061 #include "cxx_memory.h"
00062 #include "soe.h"
00063 #include "ipa_section.h"
00064 #include "ipa_lno_util.h"
00065
00066 #ifndef IPA_SUMMARY
00067 INT IPA_Ivar_Global_Count;
00068 INT IPA_Ivar_Count;
00069 #if !(defined(linux) || defined(BUILD_OS_DARWIN))
00070 mINT32
00071 SYSTEM_OF_EQUATIONS::_work_cols;
00072 mINT32
00073 SYSTEM_OF_EQUATIONS::_work_rows_eq;
00074 mINT32
00075 SYSTEM_OF_EQUATIONS::_work_rows;
00076 MEM_POOL*
00077 MAT<int>::_default_pool;
00078 #endif
00079 #endif
00080
00081
00082
00083
00084 void
00085 LINEX::Free_terms()
00086 {
00087 _larray.Free_array();
00088 _larray.Resetidx();
00089 }
00090
00091
00092
00093
00094 void
00095 PROJECTED_NODE::Reset_node()
00096 {
00097 LINEX *l;
00098 if (l = Get_upper_linex())
00099 l->Free_terms();
00100 if (l = Get_lower_linex())
00101 l->Free_terms();
00102 if (l = Get_step_linex())
00103 l->Free_terms();
00104 if (l = Get_segment_length_linex())
00105 l->Free_terms();
00106 if (l = Get_segment_stride_linex())
00107 l->Free_terms();
00108
00109 Set_flags(0);
00110 }
00111
00112
00113
00114
00115 void
00116 PROJECTED_NODE::Set_constant_linexs(INT32 upper,
00117 INT32 lower,
00118 INT32 step,
00119 INT32 segment_length,
00120 INT32 segment_stride)
00121 {
00122 MEM_POOL* pool = Mem_Pool();
00123 Set_upper_linex((LINEX*)CXX_NEW(LINEX(pool),pool));
00124 Get_upper_linex()->Set_term(LTKIND_CONST, upper, CONST_DESC,0);
00125 Set_lower_linex((LINEX*)CXX_NEW(LINEX(pool),pool));
00126 Get_lower_linex()->Set_term(LTKIND_CONST, lower, CONST_DESC,0);
00127 Set_step_linex((LINEX*)CXX_NEW(LINEX(pool),pool));
00128 Get_step_linex()->Set_term(LTKIND_CONST, step, CONST_DESC,0);
00129 if (segment_length <= 0) {
00130 Set_segment_length_linex(NULL);
00131 Set_segment_stride_linex(NULL);
00132 } else {
00133 Set_segment_length_linex((LINEX*)CXX_NEW(LINEX(pool),pool));
00134 Get_segment_length_linex()->Set_term(LTKIND_CONST, segment_length,
00135 CONST_DESC,0);
00136 Set_segment_stride_linex((LINEX*)CXX_NEW(LINEX(pool),pool));
00137 Get_segment_stride_linex()->Set_term(LTKIND_CONST, segment_stride,
00138 CONST_DESC,0);
00139 }
00140 Set_flags(0);
00141 }
00142
00143
00144
00145
00146 void
00147 PROJECTED_NODE::Set_constant_two_strided_section(INT32 lower,
00148 INT32 upper,
00149 INT32 step,
00150 INT32 seg_len,
00151 INT32 seg_stride)
00152 {
00153 MEM_POOL* pool = Mem_Pool();
00154 Set_lower_linex(CXX_NEW(LINEX(pool), pool));
00155 Get_lower_linex()->Set_term(LTKIND_CONST, lower, CONST_DESC, 0);
00156
00157 Set_upper_linex(CXX_NEW(LINEX(pool), pool));
00158 Get_upper_linex()->Set_term(LTKIND_CONST, upper, CONST_DESC, 0);
00159
00160 Set_step_linex(CXX_NEW(LINEX(pool), pool));
00161 Get_step_linex()->Set_term(LTKIND_CONST, step, CONST_DESC, 0);
00162
00163 Set_segment_length_linex(CXX_NEW(LINEX(pool), pool));
00164 Get_segment_length_linex()->Set_term(LTKIND_CONST, seg_len, CONST_DESC, 0);
00165
00166 Set_segment_stride_linex(CXX_NEW(LINEX(pool), pool));
00167 Get_segment_stride_linex()->Set_term(LTKIND_CONST, seg_stride, CONST_DESC,0);
00168
00169 Set_flags(0);
00170 }
00171
00172
00173
00174
00175
00176
00177
00178 void PROJECTED_NODE::Fill_Out()
00179 {
00180 LINEX* lx_lower = Get_lower_linex();
00181 LINEX* lx_upper = Get_upper_linex();
00182 LINEX* lx_step = Get_step_linex();
00183 if (lx_upper != NULL && lx_upper->Num_terms() >= 0
00184 && lx_step != NULL && lx_step->Num_terms() >= 0)
00185 return;
00186 Reset_is_unprojected();
00187 if (lx_upper != NULL)
00188 lx_upper->Free_terms();
00189 if (lx_step != NULL)
00190 lx_step->Free_terms();
00191 lx_step->Set_term(LTKIND_CONST, (INT32) 1, CONST_DESC, 0);
00192 for (INT i = 0; i <= lx_lower->Num_terms(); i++)
00193 lx_upper->Set_term(lx_lower->Get_term(i));
00194 }
00195
00196 #if !(defined(linux) || defined(BUILD_OS_DARWIN))
00197
00198
00199
00200 void
00201 PROJECTED_NODE::Set_linexs(LINEX* low_new,
00202 LINEX* up_new,
00203 LINEX* step_new,
00204 LINEX* segment_length_new,
00205 LINEX* segment_stride_new)
00206 {
00207 Reset_node();
00208
00209 if (low_new)
00210 low_new->Copy(Get_lower_linex());
00211 if (up_new)
00212 up_new->Copy(Get_upper_linex());
00213 if (step_new)
00214 step_new->Copy(Get_step_linex());
00215 if (segment_length_new)
00216
00217 segment_length_new->Copy(Get_segment_length_linex());
00218 if (segment_stride_new)
00219 segment_stride_new->Copy(Get_segment_stride_linex());
00220 }
00221 #endif
00222
00223
00224
00225
00226
00227
00228 void
00229 LINEX::Copy(LINEX *to)
00230 {
00231 if (this == to)
00232 return;
00233
00234 for (INT i = 0; i <= Num_terms(); ++i) {
00235 if ((Get_term(i)->Get_coeff() == 0 &&
00236 Get_term(i)->Get_type() == LTKIND_CONST) ||
00237 (Get_term(i)->Get_coeff() != 0))
00238 to->Set_term(Get_term(i));
00239 }
00240 }
00241
00242
00243
00244
00245 void
00246 PROJECTED_NODE::Copy(PROJECTED_NODE* to)
00247 {
00248 MEM_POOL* m = Mem_Pool();
00249 if (this == to)
00250 return;
00251
00252 to->Set_flags(Get_flags());
00253
00254 to->Set_lower_linex(CXX_NEW(LINEX(m), m));
00255 Get_lower_linex()->Copy(to->Get_lower_linex());
00256
00257 to->Set_upper_linex(CXX_NEW(LINEX(m), m));
00258 Get_upper_linex()->Copy(to->Get_upper_linex());
00259
00260 to->Set_step_linex(CXX_NEW(LINEX(m), m));
00261 Get_step_linex()->Copy(to->Get_step_linex());
00262
00263 if (Get_segment_length_linex() != NULL) {
00264 to->Set_segment_length_linex(CXX_NEW(LINEX(m), m));
00265 Get_segment_length_linex()->Copy(to->Get_segment_length_linex());
00266 } else {
00267 to->Set_segment_length_linex(NULL);
00268 }
00269
00270 if (Get_segment_stride_linex() != NULL) {
00271 to->Set_segment_stride_linex(CXX_NEW(LINEX(m), m));
00272 Get_segment_stride_linex()->Copy(to->Get_segment_stride_linex());
00273 } else {
00274 to->Set_segment_stride_linex(NULL);
00275 }
00276 }
00277
00278
00279
00280
00281 void
00282 PROJECTED_REGION::Copy_projected_node(PROJECTED_NODE* node)
00283 {
00284 PROJECTED_NODE* to = Get_projected_node(Get_projected_array()->Newidx());
00285 node->Copy(to);
00286 }
00287
00288
00289
00290
00291 PROJECTED_REGION::PROJECTED_REGION(PROJECTED_REGION* p)
00292 {
00293 Set_Mem_Pool(Mem_Pool());
00294 Set_num_dims(p->Get_num_dims());
00295 Set_type(p->Get_type());
00296 Set_depth(p->Get_depth());
00297 Set_projected_kernel(p->Get_projected_kernel());
00298 Set_projected_array(CXX_NEW(PROJECTED_ARRAY(Mem_Pool()), Mem_Pool()));
00299 for (INT i = 0; i < Get_num_dims(); ++i) {
00300 Copy_projected_node(p->Get_projected_node(i));
00301 }
00302 }
00303
00304
00305
00306
00307 BOOL LINEX::Is_const()
00308 {
00309 return ((Num_terms() == 0) && (Get_term(0)->Get_type() == LTKIND_CONST));
00310 }
00311
00312
00313
00314
00315 INT
00316 LINEX::Max(LINEX* l)
00317 {
00318 Is_True(Is_const(), ("LINEX::Max - Expecting constant LINEX"));
00319 Is_True(l->Is_const(), ("LINEX::Max - Expecting constant LINEX"));
00320
00321 INT32 val1 = Get_term(0)->Get_coeff();
00322 INT32 val2 = l->Get_term(0)->Get_coeff();
00323
00324 return MAX(val1, val2);
00325 }
00326
00327
00328
00329
00330 BOOL
00331 LINEX::Equivalent(LINEX &b )
00332 {
00333 INT32 num_terms = Num_terms();
00334 if (num_terms != b.Num_terms()) {
00335 return FALSE;
00336 }
00337
00338 for (INT i = 0; i <= num_terms; ++i) {
00339 if (!Get_term(i)->Equivalent(*b.Get_term(i))) {
00340 return FALSE;
00341 }
00342 }
00343
00344 return TRUE;
00345 }
00346
00347
00348
00349
00350
00351 BOOL
00352 TERM::Equivalent (TERM& t)
00353 {
00354 return (Get_type() == t.Get_type() &&
00355 Get_coeff() == t.Get_coeff() &&
00356 Get_desc() == t.Get_desc());
00357 }
00358
00359
00360
00361
00362 void
00363 LINEX::Set_linex_terms(INT start_index, INT end_index, TERM* term)
00364 {
00365 for (INT i = start_index; i < end_index; ++i) {
00366 Set_term(&term[i]);
00367 }
00368 }
00369
00370
00371
00372
00373
00374
00375
00376 void
00377 PROJECTED_NODE::Create_linex(TERM* term)
00378 {
00379 MEM_POOL* pool = Mem_Pool();
00380 INT uterm_index = Get_ub_term_index();
00381 INT lterm_index = Get_lb_term_index();
00382 INT sterm_index = Get_step_term_index();
00383 INT segment_length_index = Get_segment_length_term_index();
00384 INT segment_stride_index = Get_segment_stride_term_index();
00385
00386 INT uterm_count = Get_ub_term_count();
00387 INT lterm_count = Get_lb_term_count();
00388 INT sterm_count = Get_step_term_count();
00389 INT segment_length_count = Get_segment_length_term_count();
00390 INT segment_stride_count = Get_segment_stride_term_count();
00391
00392
00393 Set_upper_linex((LINEX*) CXX_NEW(LINEX(pool), pool));
00394 Set_lower_linex((LINEX*) CXX_NEW(LINEX(pool), pool));
00395 Set_step_linex((LINEX*) CXX_NEW(LINEX(pool), pool));
00396 if (segment_length_count > 0)
00397 Set_segment_length_linex((LINEX*) CXX_NEW(LINEX(pool), pool));
00398 else
00399 Set_segment_length_linex(NULL);
00400 if (segment_stride_count > 0)
00401 Set_segment_stride_linex((LINEX*) CXX_NEW(LINEX(pool), pool));
00402 else
00403 Set_segment_stride_linex(NULL);
00404
00405 Get_upper_linex()->Set_linex_terms(uterm_index, uterm_index+uterm_count,
00406 term);
00407 Get_lower_linex()->Set_linex_terms(lterm_index, lterm_index+lterm_count,
00408 term);
00409 Get_step_linex()->Set_linex_terms(sterm_index, sterm_index+sterm_count,
00410 term);
00411 if (segment_length_count > 0)
00412 Get_segment_length_linex()->Set_linex_terms(segment_length_index,
00413 segment_length_index+segment_length_count, term);
00414 if (segment_stride_count > 0)
00415 Get_segment_stride_linex()->Set_linex_terms(segment_stride_index,
00416 segment_stride_index+segment_stride_count, term);
00417 }
00418
00419
00420
00421
00422
00423
00424
00425 void
00426 LOOPINFO::Create_linex(TERM* term)
00427 {
00428 MEM_POOL* pool = Mem_Pool();
00429
00430
00431
00432 INT ub_start = Get_ub_term_index();
00433 INT ub_end = ub_start + Get_ub_term_count();
00434 INT lb_start = Get_lb_term_index();
00435 INT lb_end = lb_start + Get_lb_term_count();
00436 INT step_start = Get_step_term_index();
00437 INT step_end = step_start + Get_step_term_count();
00438
00439 if (!Is_messy_ub()) {
00440 u1.u3._upper_linex = CXX_NEW(LINEX(pool), pool);
00441 u1.u3._upper_linex->Set_linex_terms(ub_start, ub_end, term);
00442 }
00443
00444 if (!Is_messy_lb()) {
00445 u1.u3._lower_linex = CXX_NEW(LINEX(pool), pool);
00446 u1.u3._lower_linex->Set_linex_terms(lb_start, lb_end, term);
00447 }
00448
00449 if (!Is_messy_step()) {
00450 u1.u3._step_linex = CXX_NEW(LINEX(pool), pool);
00451 u1.u3._step_linex->Set_linex_terms(step_start, step_end, term);
00452 }
00453 }
00454
00455
00456
00457
00458 void
00459 LINEX::Init(MEM_POOL *m)
00460 {
00461
00462 new (this) LINEX(m);
00463 }
00464
00465
00466
00467
00468
00469
00470 extern INT
00471 Locate_symbol(LOOP_SYMBOL_ARRAY* syms,
00472 SYSTEM_OF_EQUATIONS* soe,
00473 const LOOP_SYMBOL& symbol)
00474 {
00475 for (INT i = 0; i < syms->Elements(); ++i) {
00476 if ((*syms)[i] == symbol) {
00477 return i;
00478 }
00479 }
00480
00481 syms->AddElement(symbol);
00482 soe->Add_Vars(1);
00483 return i;
00484 }
00485
00486
00487
00488
00489
00490
00491
00492
00493
00494
00495 void
00496 LINEX::Add_access(SYSTEM_OF_EQUATIONS *soe,
00497 mUINT8 depth,
00498 INT num_dim,
00499 INT axle,
00500 INT num_syms,
00501 ACTION_TYPE act,
00502 LOOP_SYMBOL_ARRAY* sym,
00503 BOOL trace)
00504 {
00505 INT pos, c = 0;
00506 BOOL ltkind_subscr = FALSE;
00507
00508 if (trace) {
00509 fprintf(stderr, "\n Add_access: Adding a LINEX to the SOE\n");
00510 Print(stderr);
00511 fprintf(stderr, "\n to SOE:\n");
00512 soe->Print(stderr);
00513 }
00514
00515
00516
00517 INT vector_size = num_dim + depth + num_syms + 1;
00518 if (trace) {
00519 printf("num_dim = %d, depth = %d, num_syms = %d vector size %d \n",
00520 num_dim, depth, num_syms,vector_size);
00521 }
00522
00523 mINT32* v = (mINT32*) alloca(sizeof(mINT32) * vector_size);
00524 bzero(v, sizeof(mINT32) * vector_size);
00525
00526
00527 for (INT i = 0; i <= Num_terms(); ++i) {
00528 TERM* term = Get_term(i);
00529 switch (term->Get_type()) {
00530
00531 case LTKIND_CONST:
00532 c = term->Get_coeff();
00533 break;
00534
00535 case LTKIND_LINDEX:
00536
00537
00538
00539
00540
00541 v[num_dim+term->Get_desc()] = term->Get_coeff();
00542 break;
00543
00544 case LTKIND_SUBSCR:
00545 v[term->Get_desc()] = term->Get_coeff();
00546 ltkind_subscr = TRUE;
00547 break;
00548
00549 case LTKIND_IV:
00550 pos = Locate_symbol(sym, soe, LOOP_SYMBOL(term->Get_desc()));
00551 v[num_dim + depth + pos] = term->Get_coeff();
00552 break;
00553
00554 case LTKIND_NONE:
00555 Fail_FmtAssertion("Add_access: invalid ltkind = LTKIND_NONE");
00556 break;
00557 }
00558 }
00559
00560 if (!ltkind_subscr) {
00561 if (act == ACTION_LO)
00562 v[axle] = -1;
00563 else
00564 v[axle] = 1;
00565 }
00566
00567
00568
00569
00570
00571
00572 if (act != ACTION_LO) {
00573 for (INT i = num_dim; i < vector_size; ++i)
00574 v[i] = -v[i];
00575 }
00576
00577
00578 if (act == ACTION_LO)
00579 c = -c;
00580
00581
00582
00583 if (act != ACTION_EQ)
00584 soe->Add_Le(v, c);
00585 else
00586
00587
00588 soe->Add_Eq(v,c);
00589
00590 if (trace) {
00591 fprintf(stderr,"\n Add_access: New SOE is:\n");
00592 soe->Print(stderr);
00593 }
00594 }
00595
00596
00597
00598
00599
00600 extern void
00601 Add_to_SOE(PROJECTED_REGION* a,
00602 const INT pos,
00603 SYSTEM_OF_EQUATIONS* soe,
00604 const BOOL convert_equation,
00605 LOOP_SYMBOL_ARRAY* sym,
00606 INT depth,
00607 BOOL trace)
00608 {
00609 #ifdef IPA_SUMMARY
00610 INT num_syms = Ivar->Elements();
00611 #else
00612 INT num_syms = IPA_Ivar_Count;
00613 #endif
00614
00615 PROJECTED_ARRAY* array = a->Get_projected_array();
00616 PROJECTED_NODE* node = &(*array)[pos];
00617
00618 if (!node->Is_unprojected() &&
00619 node->Get_upper_linex()->Num_terms() != -1) {
00620 node->Get_lower_linex()->Add_access(soe, depth, a->Get_num_dims(), pos,
00621 num_syms, ACTION_LO,
00622 sym, trace);
00623
00624 node->Get_upper_linex()->Add_access(soe, depth, a->Get_num_dims(), pos,
00625 num_syms, ACTION_UP,
00626 sym, trace);
00627 }
00628 else {
00629 if (convert_equation) {
00630 node->Get_lower_linex()->Add_access(soe, depth, a->Get_num_dims(), pos,
00631 num_syms, ACTION_LO,
00632 sym, trace);
00633
00634 node->Get_lower_linex()->Add_access(soe, depth, a->Get_num_dims(), pos,
00635 num_syms, ACTION_UP,
00636 sym, trace);
00637 }
00638 else {
00639 node->Get_lower_linex()->Add_access(soe, depth, a->Get_num_dims(), pos,
00640 num_syms, ACTION_EQ,
00641 sym, trace);
00642 }
00643 }
00644 }
00645
00646
00647
00648
00649 PROJECTED_REGION::PROJECTED_REGION(mINT16 type,
00650 mUINT8 depth,
00651 mUINT8 dim,
00652 MEM_POOL* mem_pool)
00653 : _type (type),
00654 _num_dims (dim),
00655 _depth (depth),
00656 _mem_pool (mem_pool)
00657 {
00658 u2._projected_kernel = 0;
00659 u1._region = CXX_NEW(PROJECTED_ARRAY(mem_pool), mem_pool);
00660 u1._region->Force_Alloc_array(dim);
00661 u1._region->Setidx(dim-1);
00662 for (INT i = 0; i < dim; i++) {
00663 (*(u1._region))[i].Init(mem_pool);
00664 }
00665 }
00666
00667
00668
00669
00670 void
00671 PROJECTED_NODE::Init(MEM_POOL *m)
00672 {
00673 Set_Mem_Pool(m);
00674
00675 Set_upper_linex(CXX_NEW(LINEX(m), m));
00676 Get_upper_linex()->Init(m);
00677
00678 Set_lower_linex(CXX_NEW(LINEX(m), m));
00679 Get_lower_linex()->Init(m);
00680
00681 Set_step_linex(CXX_NEW(LINEX(m), m));
00682 Get_step_linex()->Init(m);
00683
00684 Set_segment_length_linex(NULL);
00685 Set_segment_stride_linex(NULL);
00686
00687 Set_flags(0);
00688 }
00689
00690
00691
00692
00693
00694 BOOL
00695 PROJECTED_NODE::Equivalent(PROJECTED_NODE &b)
00696 {
00697 return ((Get_flags() == b.Get_flags()) &&
00698 (Get_upper_linex()->Equivalent(*b.Get_upper_linex())) &&
00699 (Get_lower_linex()->Equivalent(*b.Get_lower_linex())) &&
00700 (Get_step_linex()->Equivalent(*b.Get_step_linex())) &&
00701 (Get_segment_length_linex() == NULL &&
00702 b.Get_segment_length_linex() == NULL ||
00703 Get_segment_length_linex() != NULL &&
00704 b.Get_segment_length_linex() == NULL &&
00705 Get_segment_length_linex()->
00706 Equivalent(*b.Get_segment_length_linex())) &&
00707 (Get_segment_stride_linex() == NULL &&
00708 b.Get_segment_stride_linex() == NULL ||
00709 Get_segment_stride_linex() != NULL &&
00710 b.Get_segment_stride_linex() == NULL &&
00711 Get_segment_stride_linex()->
00712 Equivalent(*b.Get_segment_stride_linex())));
00713 }
00714
00715
00716
00717
00718
00719 BOOL
00720 PROJECTED_REGION::Equivalent(PROJECTED_REGION* p)
00721 {
00722 if (Is_messy_region() && p->Is_messy_region()) {
00723 return TRUE;
00724 }
00725
00726 INT num_dims = Get_num_dims();
00727 if (num_dims != p->Get_num_dims()) {
00728 return FALSE;
00729 }
00730
00731
00732
00733
00734
00735
00736
00737
00738 for (INT i = 1; i < num_dims; ++i) {
00739 PROJECTED_NODE* p1 = Get_projected_node(i);
00740 PROJECTED_NODE* p2 = p->Get_projected_node(i);
00741 Is_True(p1 && p2, ("PROJECTED_REGION::Equivalent: NULL projected node\n"));
00742 if (!p1->Equivalent(*p2)) {
00743 return FALSE;
00744 }
00745 }
00746
00747 return TRUE;
00748 }
00749
00750
00751
00752
00753
00754
00755
00756
00757
00758
00759 BOOL
00760 PROJECTED_REGION::May_Union(PROJECTED_REGION& b,
00761 BOOL trace)
00762 {
00763 if (trace) {
00764 fprintf(stderr,"Union two PROJECTED REGIONs \n");
00765 b.Print(stderr);
00766 Print(stderr);
00767 }
00768
00769
00770 if (Is_messy_region()) {
00771 return FALSE;
00772 }
00773 else if (b.Is_messy_region()) {
00774 Set_messy_region();
00775 return TRUE;
00776 }
00777
00778 BOOL change = FALSE;
00779 MEM_POOL* local_pool = Mem_Pool();
00780 LOOPINFO l(local_pool);
00781
00782 for (INT i = 0; i < Get_num_dims(); ++i) {
00783
00784
00785 PROJECTED_NODE* ax = Get_projected_node(i);
00786 if (ax->Has_all_messy_bounds()) {
00787 continue;
00788 }
00789
00790
00791 PROJECTED_NODE* bx = b.Get_projected_node(i);
00792 if (ax->Is_messy_lb() || ax->Is_messy_ub() ||
00793 bx->Is_messy_lb() || bx->Is_messy_ub()) {
00794 ax->Set_all_messy_bounds();
00795 change = TRUE;
00796 continue;
00797 }
00798
00799 ax->Fill_Out();
00800 bx->Fill_Out();
00801
00802
00803 LINEX* lx_a_step = ax->Get_step_linex();
00804 LINEX* lx_b_step = bx->Get_step_linex();
00805 if (!lx_a_step->Is_const() || !lx_b_step->Is_const()) {
00806 if (!lx_a_step->Is_const() || lx_a_step->Get_constant_term() != 1) {
00807 lx_a_step->Free_terms();
00808 lx_a_step->Set_term(LTKIND_CONST, (mINT32) 1, CONST_DESC, 0);
00809 change = TRUE;
00810 }
00811 }
00812 else {
00813 INT a_coeff = lx_a_step->Get_term(0)->Get_coeff();
00814 INT b_coeff = lx_b_step->Get_term(0)->Get_coeff();
00815 INT gcd = Gcd(a_coeff, b_coeff);
00816 LINEX* ax_lower = ax->Get_lower_linex();
00817 LINEX* bx_lower = bx->Get_lower_linex();
00818 LINEX* lx_diff = ax_lower->Subtract(bx_lower);
00819 lx_diff->Simplify();
00820 if (!lx_diff->Is_const()) {
00821 if (lx_a_step->Get_term(0)->Get_coeff() != 1) {
00822 lx_a_step->Get_term(0)->Set_coeff(1);
00823 change = TRUE;
00824 }
00825 }
00826 else {
00827 INT diff = lx_diff->Get_term(0)->Get_coeff();
00828 if (diff < 0)
00829 diff = -diff;
00830 if (diff % gcd != 0) {
00831 if (lx_a_step->Get_term(0)->Get_coeff() != 1) {
00832 lx_a_step->Get_term(0)->Set_coeff(1);
00833 change = TRUE;
00834 }
00835 }
00836 else {
00837 if (lx_a_step->Get_term(0)->Get_coeff() != gcd) {
00838 lx_a_step->Get_term(0)->Set_coeff(gcd);
00839 change = TRUE;
00840 }
00841 }
00842 }
00843 }
00844
00845
00846 SYSTEM_OF_EQUATIONS* soe =
00847 CXX_NEW(SYSTEM_OF_EQUATIONS(0, 0, b.Get_num_dims() + b.Get_depth(),
00848 local_pool), local_pool);
00849 LOOP_SYMBOL_ARRAY* syms =
00850 CXX_NEW(LOOP_SYMBOL_ARRAY(local_pool), local_pool);
00851
00852
00853 Add_to_SOE(this, i, soe, TRUE, syms, Get_depth(), trace);
00854 Add_to_SOE(&b, i, soe, TRUE, syms, Get_depth(), trace);
00855
00856
00857
00858 if (soe->Copy_To_Work()) {
00859 BOOL* is_redundant =
00860 CXX_NEW_ARRAY(BOOL, soe->Num_Le_Constraints(), local_pool);
00861 INT num_con = soe->Num_Le_Constraints();
00862
00863 num_con -= soe->Mark_Simple_Redundant(is_redundant);
00864 if (num_con > 2) {
00865
00866
00867 num_con -= soe->Mark_New_Redundant(is_redundant);
00868 }
00869
00870
00871 if (num_con == 2) {
00872 if (!((is_redundant[0] && !is_redundant[2]
00873 || !is_redundant[0] && is_redundant[2])
00874 && (is_redundant[1] && !is_redundant[3]
00875 || !is_redundant[1] && is_redundant[3]))) {
00876 ax->Set_all_messy_bounds();
00877 change = TRUE;
00878 continue;
00879 }
00880 if (!ax->Matching_Segment_Stride(bx)
00881 || ax->Get_segment_length_linex() != NULL
00882 && !ax->Get_segment_length_linex()->Is_const()
00883 || bx->Get_segment_length_linex() != NULL
00884 && !bx->Get_segment_length_linex()->Is_const()) {
00885 LINEX* lx_seg_length = ax->Get_segment_length_linex();
00886 lx_seg_length->Free_terms();
00887 LINEX* lx_seg_stride = ax->Get_segment_stride_linex();
00888 lx_seg_stride->Free_terms();
00889 }
00890 else if (ax->Get_segment_stride_linex() != NULL) {
00891 LINEX* lx_a_seg_length = ax->Get_segment_length_linex();
00892 INT a_const_value = lx_a_seg_length->Get_constant_term();
00893 LINEX* lx_b_seg_length = bx->Get_segment_length_linex();
00894 INT b_const_value = lx_b_seg_length->Get_constant_term();
00895 INT difference = a_const_value > b_const_value
00896 ? a_const_value - b_const_value : b_const_value - a_const_value;
00897 ax->Get_segment_length_linex()->Set_term(LTKIND_CONST,
00898 difference, CONST_DESC, 0);
00899 ax->Get_segment_length_linex()->Simplify();
00900 LINEX* ax_lower = ax->Get_lower_linex();
00901 LINEX* bx_lower = bx->Get_lower_linex();
00902 LINEX* lx_diff = ax_lower->Subtract(bx_lower);
00903 if (!lx_diff->Is_const()) {
00904 ax->Get_segment_length_linex()->Free_terms();
00905 ax->Set_segment_length_linex(NULL);
00906 ax->Get_segment_stride_linex()->Free_terms();
00907 ax->Set_segment_stride_linex(NULL);
00908 }
00909 else {
00910 INT difference = lx_diff->Get_constant_term();
00911 if (difference < 0)
00912 difference = -difference;
00913 ax->Get_segment_length_linex()->Set_term(LTKIND_CONST,
00914 difference, CONST_DESC,0);
00915 ax->Get_segment_length_linex()->Simplify();
00916 }
00917 }
00918
00919
00920 LINEX* lb = ax->Get_lower_linex();
00921 if (lb && !lb->Equivalent(*(bx->Get_lower_linex()))) {
00922 if (!is_redundant[0]) {
00923 lb->Free_terms();
00924 (bx->Get_lower_linex())->Copy(lb);
00925 change = TRUE;
00926 }
00927 }
00928
00929 LINEX* ub = ax->Get_upper_linex();
00930 if (ub && !ub->Equivalent(*(bx->Get_upper_linex()))) {
00931 if (!is_redundant[1]) {
00932 ub->Free_terms();
00933 (bx->Get_upper_linex())->Copy(ub);
00934 change = TRUE;
00935 }
00936 }
00937
00938 }
00939 else {
00940
00941 ax->Set_all_messy_bounds();
00942 change = TRUE;
00943 }
00944 }
00945 else {
00946
00947 ax->Set_all_messy_bounds();
00948 change = TRUE;
00949 }
00950 }
00951
00952 if (trace) {
00953 fprintf(stderr,"Result of Unioning two PROJECTED REGIONs \n");
00954 Print(stderr);
00955 }
00956
00957 return change;
00958 }
00959
00960
00961
00962
00963 BOOL
00964 TERM::Is_equal(TERM* t, INT count)
00965 {
00966 for (INT i = 0; i <= count; ++i) {
00967 if (! t[i].Equivalent(this[i])) {
00968 return FALSE;
00969 }
00970 }
00971 return TRUE;
00972 }
00973
00974
00975
00976
00977 void
00978 PROJECTED_REGION::Copy_write(PROJECTED_REGION *p_in)
00979 {
00980 Set_type(p_in->Get_type());
00981 Set_num_dims(p_in->Get_num_dims());
00982 Set_depth(p_in->Get_depth());
00983 if (p_in->Is_passed())
00984 {
00985 Set_callsite_id(p_in->Get_callsite_id());
00986 Set_actual_id(p_in->Get_actual_id());
00987 }
00988 }
00989
00990 void
00991 Print_Symbol_Array(LOOP_SYMBOL_ARRAY* sa, FILE *fp)
00992 {
00993 for (INT i = 0; i <= sa->Lastidx(); i++) {
00994 fprintf(fp, "[%d] ", i);
00995 (*sa)[i].Print(fp);
00996 }
00997 }
00998
00999
01000
01001
01002
01003 BOOL
01004 PROJECTED_REGION::Constant_bounds(mUINT8 first_dim)
01005 {
01006 for (INT i = first_dim; i < _num_dims; ++i) {
01007 PROJECTED_NODE *node = Get_projected_node(i);
01008 LINEX* lower = node->Get_upper_linex();
01009 LINEX* upper = node->Get_upper_linex();
01010 if (!lower || !lower->Is_const() || !upper || !upper->Is_const()) {
01011 return FALSE;
01012 }
01013 }
01014 return TRUE;
01015 }
01016
01017
01018
01019
01020 INT
01021 LINEX::Get_constant_term()
01022 {
01023 for (INT i = 0; i <= Num_terms(); ++i) {
01024 if (Get_term(i)->Get_type() == LTKIND_CONST)
01025 return Get_term(i)->Get_coeff();
01026 }
01027
01028 return 0;
01029 }
01030
01031
01032
01033
01034 PROJECTED_REGION*
01035 REGION_ARRAYS::Get_Projected_Region(INT i)
01036 {
01037 PROJECTED_REGION_INFO_ARRAY *info = Get_projected_region_array();
01038
01039 Is_True(info && info->Lastidx() != -1, ("Expecting at least 1 projected region in Reshape \n"));
01040 Is_True(info->Lastidx() >= i, ("Projected_Region %d exceeded size of array %d \n", i, info->Lastidx()));
01041
01042 PROJECTED_REGION_INFO *region_info = &(*info)[i];
01043 PROJECTED_REGION *proj_shape = region_info->Get_projected_region();
01044 Is_True(proj_shape, ("NULL Projected Region in REGION_ARRAYS::Get_Projected_Region \n"));
01045
01046 return proj_shape;
01047 }
01048
01049
01050
01051
01052
01053
01054 void LINEX::Remove_Zero_Terms()
01055 {
01056 INT j = 0;
01057 INT num_init_terms = Num_terms();
01058 for (INT i = 0; i <= Num_terms(); i++) {
01059 TERM* tm = Get_term(i);
01060 if (tm->Get_coeff() != 0) {
01061 if (i != j)
01062 _larray[j] = _larray[i];
01063 j++;
01064 }
01065 }
01066 INT difference = i - j;
01067 for (i = 0; i < difference; i++)
01068 _larray.Decidx();
01069
01070
01071
01072
01073 if ((Num_terms() == -1) && (num_init_terms != -1))
01074 {
01075 Set_term(LTKIND_CONST, 0, CONST_DESC, 0);
01076 }
01077 }
01078
01079
01080
01081
01082
01083
01084
01085 void LINEX::Simplify()
01086 {
01087 for (INT i = 0; i <= Num_terms(); i++) {
01088 TERM* tm_i = Get_term(i);
01089 for (INT j = i + 1; j <= Num_terms(); j++) {
01090 TERM* tm_j = Get_term(j);
01091 if (tm_i->Get_type() == tm_j->Get_type()
01092 && tm_i->Get_desc() == tm_j->Get_desc()
01093 && tm_i->Get_projected_level() == tm_j->Get_projected_level()) {
01094 tm_i->Set_coeff(tm_i->Get_coeff() + tm_j->Get_coeff());
01095 tm_j->Set_coeff(0);
01096 }
01097 }
01098 }
01099 Remove_Zero_Terms();
01100 }
01101
01102
01103
01104
01105
01106
01107 void PROJECTED_NODE::Simplify()
01108 {
01109 if (!Is_messy_lb()) {
01110 LINEX* lx_lower = Get_lower_linex();
01111 lx_lower->Simplify();
01112 }
01113 if (!Is_messy_ub()) {
01114 LINEX* lx_upper = Get_upper_linex();
01115 lx_upper->Simplify();
01116 }
01117 if (!Is_messy_step()) {
01118 LINEX* lx_step = Get_step_linex();
01119 lx_step->Simplify();
01120 }
01121 if (Get_segment_length_linex() != NULL)
01122 Get_segment_length_linex()->Simplify();
01123 if (Get_segment_stride_linex() != NULL)
01124 Get_segment_stride_linex()->Simplify();
01125 }
01126
01127
01128
01129
01130
01131
01132 void PROJECTED_REGION::Simplify()
01133 {
01134 if (Is_messy_region())
01135 return;
01136 for (INT i = 0; i < Get_num_dims(); i++) {
01137 PROJECTED_NODE* pn = Get_projected_node(i);
01138 pn->Simplify();
01139 }
01140 }
01141
01142 BOOL PROJECTED_REGION::Has_Messy_Bounds()
01143 {
01144 for (INT i = 0; i < Get_num_dims(); i++) {
01145 PROJECTED_NODE* pn = Get_projected_node(i);
01146 if (pn->Has_a_messy_bound())
01147 return TRUE;
01148 }
01149 return FALSE;
01150 }
01151
01152 BOOL PROJECTED_REGION::Has_Important_Messy_Bounds()
01153 {
01154 for (INT i = 1; i < Get_num_dims(); i++) {
01155 PROJECTED_NODE* pn = Get_projected_node(i);
01156 if (pn->Has_a_messy_bound())
01157 return TRUE;
01158 }
01159 return FALSE;
01160 }
01161
01162 void PROJECTED_REGION::Fill_Out()
01163 {
01164 if (Is_messy_region())
01165 return;
01166 Reset_is_unprojected();
01167 for (INT i = 0; i < Get_num_dims(); i++) {
01168 PROJECTED_NODE* pn = Get_projected_node(i);
01169 pn->Fill_Out();
01170 }
01171 }
01172
01173 BOOL PROJECTED_NODE::Matching_Segment_Stride(PROJECTED_NODE* pn)
01174 {
01175 if (pn == NULL)
01176 return FALSE;
01177
01178 LINEX* ss_one = Get_segment_stride_linex();
01179 LINEX* ss_two = pn->Get_segment_stride_linex();
01180
01181 if (ss_one == NULL && ss_two == NULL)
01182 return TRUE;
01183 if (ss_one == NULL || ss_two == NULL)
01184 return FALSE;
01185 return ss_one->Equivalent(*ss_two);
01186 }
01187
01188 BOOL PROJECTED_REGION::Matching_Segment_Stride(PROJECTED_REGION* pr)
01189 {
01190 if (pr == NULL)
01191 return FALSE;
01192 if (Is_messy_region() || pr->Is_messy_region())
01193 return (Is_messy_region() == pr->Is_messy_region());
01194 if (Get_num_dims() != pr->Get_num_dims())
01195 return FALSE;
01196 for (INT i = 0; i < Get_num_dims(); i++) {
01197 PROJECTED_NODE* pn_one = Get_projected_node(i);
01198 PROJECTED_NODE* pn_two = pr->Get_projected_node(i);
01199 if (!pn_one->Matching_Segment_Stride(pn_two))
01200 return FALSE;
01201 }
01202 return TRUE;
01203 }
01204
01205
01206
01207
01208
01209
01210 LINEX* LINEX::Merge(LINEX *l1)
01211 {
01212 INT c = 0;
01213
01214
01215 FmtAssert(_larray.Get_Mem_Pool() == l1->_larray.Get_Mem_Pool(),
01216 ("LINEX::Merge: Inconsistent mem pools"));
01217 MEM_POOL* mem_pool = _larray.Get_Mem_Pool();
01218
01219
01220 INT coeff_max = -1;
01221 INT sub_coeff_max = -1;
01222 INT isym_coeff_max = -1;
01223 for (INT i = 0; i <= Num_terms(); i++) {
01224 TERM* term = Get_term(i);
01225 switch (term->Get_type()) {
01226 case LTKIND_LINDEX:
01227 if (term->Get_desc() > coeff_max)
01228 coeff_max = term->Get_desc();
01229 break;
01230 case LTKIND_SUBSCR:
01231 if (term->Get_desc() > sub_coeff_max)
01232 sub_coeff_max = term->Get_desc();
01233 break;
01234 case LTKIND_IV:
01235 if (term->Get_desc() > isym_coeff_max)
01236 isym_coeff_max = term->Get_desc();
01237 break;
01238 }
01239 }
01240 for (i = 0; i <= l1->Num_terms(); i++) {
01241 TERM* term = l1->Get_term(i);
01242 switch (term->Get_type()) {
01243 case LTKIND_LINDEX:
01244 if (term->Get_desc() > coeff_max)
01245 coeff_max = term->Get_desc();
01246 break;
01247 case LTKIND_SUBSCR:
01248 if (term->Get_desc() > sub_coeff_max)
01249 sub_coeff_max = term->Get_desc();
01250 break;
01251 case LTKIND_IV:
01252 if (term->Get_desc() > isym_coeff_max)
01253 isym_coeff_max = term->Get_desc();
01254 break;
01255 }
01256 }
01257
01258
01259 INT* coeff = (INT*) alloca(sizeof(INT) * (coeff_max + 1));
01260 INT* sub_coeff = (INT*) alloca(sizeof(INT) * (sub_coeff_max + 1));
01261 INT* isym_coeff = (INT*) alloca(sizeof(INT) * (isym_coeff_max + 1));
01262 bzero(coeff, sizeof(INT) * (coeff_max + 1));
01263 bzero(sub_coeff, sizeof(INT) * (sub_coeff_max + 1));
01264 bzero(isym_coeff, sizeof(INT) * (isym_coeff_max + 1));
01265
01266 LINEX* l = CXX_NEW(LINEX(mem_pool), mem_pool);
01267
01268
01269 for (i = 0; i <= Num_terms(); i++) {
01270 TERM *term = Get_term(i);
01271 switch (term->Get_type()) {
01272 case LTKIND_NONE:
01273 break;
01274 case LTKIND_CONST:
01275 c += term->Get_coeff();
01276 break;
01277 case LTKIND_LINDEX:
01278 coeff[term->Get_desc()] += term->Get_coeff();
01279 break;
01280 case LTKIND_SUBSCR:
01281 sub_coeff[term->Get_desc()] += term->Get_coeff();
01282 break;
01283 case LTKIND_IV:
01284 isym_coeff[term->Get_desc()] += term->Get_coeff();
01285 break;
01286 }
01287 }
01288 for (i = 0; i<= l1->Num_terms(); ++i) {
01289 TERM *term = l1->Get_term(i);
01290 switch (term->Get_type()) {
01291 case LTKIND_NONE:
01292 break;
01293 case LTKIND_CONST:
01294 c += term->Get_coeff();
01295 break;
01296 case LTKIND_LINDEX:
01297 coeff[term->Get_desc()] += term->Get_coeff();
01298 break;
01299 case LTKIND_SUBSCR:
01300 sub_coeff[term->Get_desc()] += term->Get_coeff();
01301 break;
01302 case LTKIND_IV:
01303 isym_coeff[term->Get_desc()] += term->Get_coeff();
01304 break;
01305 }
01306 }
01307
01308
01309 l->Set_term(LTKIND_CONST, c, CONST_DESC, 0);
01310 for (i = 0; i <= coeff_max; i++)
01311 if (coeff[i])
01312 l->Set_term(LTKIND_LINDEX, coeff[i], i, 0);
01313 for (i = 0; i <= sub_coeff_max; i++)
01314 if (sub_coeff[i])
01315 l->Set_term(LTKIND_SUBSCR, sub_coeff[i], i, 0);
01316 for (i = 0; i <= isym_coeff_max; i++)
01317 if (isym_coeff[i])
01318 l->Set_term(LTKIND_IV, isym_coeff[i], i, 0);
01319
01320 return l;
01321 }
01322
01323
01324
01325
01326
01327 LINEX* LINEX::Subtract(LINEX *l1)
01328 {
01329 INT c = 0;
01330
01331
01332 FmtAssert(_larray.Get_Mem_Pool() == l1->_larray.Get_Mem_Pool(),
01333 ("LINEX::Subtract: Inconsistent mem pools"));
01334 MEM_POOL* mem_pool = _larray.Get_Mem_Pool();
01335
01336
01337 INT coeff_max = -1;
01338 INT sub_coeff_max = -1;
01339 INT isym_coeff_max = -1;
01340 for (INT i = 0; i <= Num_terms(); i++) {
01341 TERM* term = Get_term(i);
01342 switch (term->Get_type()) {
01343 case LTKIND_LINDEX:
01344 if (term->Get_desc() > coeff_max)
01345 coeff_max = term->Get_desc();
01346 break;
01347 case LTKIND_SUBSCR:
01348 if (term->Get_desc() > sub_coeff_max)
01349 sub_coeff_max = term->Get_desc();
01350 break;
01351 case LTKIND_IV:
01352 if (term->Get_desc() > isym_coeff_max)
01353 isym_coeff_max = term->Get_desc();
01354 break;
01355 }
01356 }
01357 for (i = 0; i <= l1->Num_terms(); i++) {
01358 TERM* term = l1->Get_term(i);
01359 switch (term->Get_type()) {
01360 case LTKIND_LINDEX:
01361 if (term->Get_desc() > coeff_max)
01362 coeff_max = term->Get_desc();
01363 break;
01364 case LTKIND_SUBSCR:
01365 if (term->Get_desc() > sub_coeff_max)
01366 sub_coeff_max = term->Get_desc();
01367 break;
01368 case LTKIND_IV:
01369 if (term->Get_desc() > isym_coeff_max)
01370 isym_coeff_max = term->Get_desc();
01371 break;
01372 }
01373 }
01374
01375
01376 INT* coeff = (INT*) alloca(sizeof(INT) * (coeff_max + 1));
01377 INT* sub_coeff = (INT*) alloca(sizeof(INT) * (sub_coeff_max + 1));
01378 INT* isym_coeff = (INT*) alloca(sizeof(INT) * (isym_coeff_max + 1));
01379 bzero(coeff, sizeof(INT) * (coeff_max + 1));
01380 bzero(sub_coeff, sizeof(INT) * (sub_coeff_max + 1));
01381 bzero(isym_coeff, sizeof(INT) * (isym_coeff_max + 1));
01382
01383 LINEX* l = CXX_NEW(LINEX(mem_pool), mem_pool);
01384
01385
01386 for (i = 0; i <= Num_terms(); i++) {
01387 TERM *term = Get_term(i);
01388 switch (term->Get_type()) {
01389 case LTKIND_NONE:
01390 break;
01391 case LTKIND_CONST:
01392 c += term->Get_coeff();
01393 break;
01394 case LTKIND_LINDEX:
01395 coeff[term->Get_desc()] += term->Get_coeff();
01396 break;
01397 case LTKIND_SUBSCR:
01398 sub_coeff[term->Get_desc()] += term->Get_coeff();
01399 break;
01400 case LTKIND_IV:
01401 isym_coeff[term->Get_desc()] += term->Get_coeff();
01402 break;
01403 }
01404 }
01405 for (i = 0; i<= l1->Num_terms(); ++i) {
01406 TERM *term = l1->Get_term(i);
01407 switch (term->Get_type()) {
01408 case LTKIND_NONE:
01409 break;
01410 case LTKIND_CONST:
01411 c -= term->Get_coeff();
01412 break;
01413 case LTKIND_LINDEX:
01414 coeff[term->Get_desc()] -= term->Get_coeff();
01415 break;
01416 case LTKIND_SUBSCR:
01417 sub_coeff[term->Get_desc()] -= term->Get_coeff();
01418 break;
01419 case LTKIND_IV:
01420 isym_coeff[term->Get_desc()] -= term->Get_coeff();
01421 break;
01422 }
01423 }
01424
01425
01426 l->Set_term(LTKIND_CONST, c, CONST_DESC, 0);
01427 for (i = 0; i <= coeff_max; i++)
01428 if (coeff[i])
01429 l->Set_term(LTKIND_LINDEX, coeff[i], i, 0);
01430 for (i = 0; i <= sub_coeff_max; i++)
01431 if (sub_coeff[i])
01432 l->Set_term(LTKIND_SUBSCR, sub_coeff[i], i, 0);
01433 for (i = 0; i <= isym_coeff_max; i++)
01434 if (isym_coeff[i])
01435 l->Set_term(LTKIND_IV, isym_coeff[i], i, 0);
01436
01437 return l;
01438 }
01439