1 /* Data references and dependences detectors. 2 Copyright (C) 2003-2013 Free Software Foundation, Inc. 3 Contributed by Sebastian Pop <pop@cri.ensmp.fr> 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify it under 8 the terms of the GNU General Public License as published by the Free 9 Software Foundation; either version 3, or (at your option) any later 10 version. 11 12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13 WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15 for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GCC; see the file COPYING3. If not see 19 <http://www.gnu.org/licenses/>. */ 20 21 #ifndef GCC_TREE_DATA_REF_H 22 #define GCC_TREE_DATA_REF_H 23 24 #include "graphds.h" 25 #include "omega.h" 26 #include "tree-chrec.h" 27 28 /* 29 innermost_loop_behavior describes the evolution of the address of the memory 30 reference in the innermost enclosing loop. The address is expressed as 31 BASE + STEP * # of iteration, and base is further decomposed as the base 32 pointer (BASE_ADDRESS), loop invariant offset (OFFSET) and 33 constant offset (INIT). Examples, in loop nest 34 35 for (i = 0; i < 100; i++) 36 for (j = 3; j < 100; j++) 37 38 Example 1 Example 2 39 data-ref a[j].b[i][j] *(p + x + 16B + 4B * j) 40 41 42 innermost_loop_behavior 43 base_address &a p 44 offset i * D_i x 45 init 3 * D_j + offsetof (b) 28 46 step D_j 4 47 48 */ 49 struct innermost_loop_behavior 50 { 51 tree base_address; 52 tree offset; 53 tree init; 54 tree step; 55 56 /* Alignment information. ALIGNED_TO is set to the largest power of two 57 that divides OFFSET. */ 58 tree aligned_to; 59 }; 60 61 /* Describes the evolutions of indices of the memory reference. The indices 62 are indices of the ARRAY_REFs, indexes in artificial dimensions 63 added for member selection of records and the operands of MEM_REFs. 64 BASE_OBJECT is the part of the reference that is loop-invariant 65 (note that this reference does not have to cover the whole object 66 being accessed, in which case UNCONSTRAINED_BASE is set; hence it is 67 not recommended to use BASE_OBJECT in any code generation). 68 For the examples above, 69 70 base_object: a *(p + x + 4B * j_0) 71 indices: {j_0, +, 1}_2 {16, +, 4}_2 72 4 73 {i_0, +, 1}_1 74 {j_0, +, 1}_2 75 */ 76 77 struct indices 78 { 79 /* The object. */ 80 tree base_object; 81 82 /* A list of chrecs. Access functions of the indices. */ 83 vec<tree> access_fns; 84 85 /* Whether BASE_OBJECT is an access representing the whole object 86 or whether the access could not be constrained. */ 87 bool unconstrained_base; 88 }; 89 90 struct dr_alias 91 { 92 /* The alias information that should be used for new pointers to this 93 location. */ 94 struct ptr_info_def *ptr_info; 95 }; 96 97 /* An integer vector. A vector formally consists of an element of a vector 98 space. A vector space is a set that is closed under vector addition 99 and scalar multiplication. In this vector space, an element is a list of 100 integers. */ 101 typedef int *lambda_vector; 102 103 /* An integer matrix. A matrix consists of m vectors of length n (IE 104 all vectors are the same length). */ 105 typedef lambda_vector *lambda_matrix; 106 107 /* Each vector of the access matrix represents a linear access 108 function for a subscript. First elements correspond to the 109 leftmost indices, ie. for a[i][j] the first vector corresponds to 110 the subscript in "i". The elements of a vector are relative to 111 the loop nests in which the data reference is considered, 112 i.e. the vector is relative to the SCoP that provides the context 113 in which this data reference occurs. 114 115 For example, in 116 117 | loop_1 118 | loop_2 119 | a[i+3][2*j+n-1] 120 121 if "i" varies in loop_1 and "j" varies in loop_2, the access 122 matrix with respect to the loop nest {loop_1, loop_2} is: 123 124 | loop_1 loop_2 param_n cst 125 | 1 0 0 3 126 | 0 2 1 -1 127 128 whereas the access matrix with respect to loop_2 considers "i" as 129 a parameter: 130 131 | loop_2 param_i param_n cst 132 | 0 1 0 3 133 | 2 0 1 -1 134 */ 135 struct access_matrix 136 { 137 vec<loop_p> loop_nest; 138 int nb_induction_vars; 139 vec<tree> parameters; 140 vec<lambda_vector, va_gc> *matrix; 141 }; 142 143 #define AM_LOOP_NEST(M) (M)->loop_nest 144 #define AM_NB_INDUCTION_VARS(M) (M)->nb_induction_vars 145 #define AM_PARAMETERS(M) (M)->parameters 146 #define AM_MATRIX(M) (M)->matrix 147 #define AM_NB_PARAMETERS(M) (AM_PARAMETERS(M)).length () 148 #define AM_CONST_COLUMN_INDEX(M) (AM_NB_INDUCTION_VARS (M) + AM_NB_PARAMETERS (M)) 149 #define AM_NB_COLUMNS(M) (AM_NB_INDUCTION_VARS (M) + AM_NB_PARAMETERS (M) + 1) 150 #define AM_GET_SUBSCRIPT_ACCESS_VECTOR(M, I) AM_MATRIX (M)[I] 151 #define AM_GET_ACCESS_MATRIX_ELEMENT(M, I, J) AM_GET_SUBSCRIPT_ACCESS_VECTOR (M, I)[J] 152 153 /* Return the column in the access matrix of LOOP_NUM. */ 154 155 static inline int 156 am_vector_index_for_loop (struct access_matrix *access_matrix, int loop_num) 157 { 158 int i; 159 loop_p l; 160 161 for (i = 0; AM_LOOP_NEST (access_matrix).iterate (i, &l); i++) 162 if (l->num == loop_num) 163 return i; 164 165 gcc_unreachable(); 166 } 167 168 struct data_reference 169 { 170 /* A pointer to the statement that contains this DR. */ 171 gimple stmt; 172 173 /* A pointer to the memory reference. */ 174 tree ref; 175 176 /* Auxiliary info specific to a pass. */ 177 void *aux; 178 179 /* True when the data reference is in RHS of a stmt. */ 180 bool is_read; 181 182 /* Behavior of the memory reference in the innermost loop. */ 183 struct innermost_loop_behavior innermost; 184 185 /* Subscripts of this data reference. */ 186 struct indices indices; 187 188 /* Alias information for the data reference. */ 189 struct dr_alias alias; 190 191 /* Matrix representation for the data access functions. */ 192 struct access_matrix *access_matrix; 193 }; 194 195 #define DR_STMT(DR) (DR)->stmt 196 #define DR_REF(DR) (DR)->ref 197 #define DR_BASE_OBJECT(DR) (DR)->indices.base_object 198 #define DR_UNCONSTRAINED_BASE(DR) (DR)->indices.unconstrained_base 199 #define DR_ACCESS_FNS(DR) (DR)->indices.access_fns 200 #define DR_ACCESS_FN(DR, I) DR_ACCESS_FNS (DR)[I] 201 #define DR_NUM_DIMENSIONS(DR) DR_ACCESS_FNS (DR).length () 202 #define DR_IS_READ(DR) (DR)->is_read 203 #define DR_IS_WRITE(DR) (!DR_IS_READ (DR)) 204 #define DR_BASE_ADDRESS(DR) (DR)->innermost.base_address 205 #define DR_OFFSET(DR) (DR)->innermost.offset 206 #define DR_INIT(DR) (DR)->innermost.init 207 #define DR_STEP(DR) (DR)->innermost.step 208 #define DR_PTR_INFO(DR) (DR)->alias.ptr_info 209 #define DR_ALIGNED_TO(DR) (DR)->innermost.aligned_to 210 #define DR_ACCESS_MATRIX(DR) (DR)->access_matrix 211 212 typedef struct data_reference *data_reference_p; 213 214 enum data_dependence_direction { 215 dir_positive, 216 dir_negative, 217 dir_equal, 218 dir_positive_or_negative, 219 dir_positive_or_equal, 220 dir_negative_or_equal, 221 dir_star, 222 dir_independent 223 }; 224 225 /* The description of the grid of iterations that overlap. At most 226 two loops are considered at the same time just now, hence at most 227 two functions are needed. For each of the functions, we store 228 the vector of coefficients, f[0] + x * f[1] + y * f[2] + ..., 229 where x, y, ... are variables. */ 230 231 #define MAX_DIM 2 232 233 /* Special values of N. */ 234 #define NO_DEPENDENCE 0 235 #define NOT_KNOWN (MAX_DIM + 1) 236 #define CF_NONTRIVIAL_P(CF) ((CF)->n != NO_DEPENDENCE && (CF)->n != NOT_KNOWN) 237 #define CF_NOT_KNOWN_P(CF) ((CF)->n == NOT_KNOWN) 238 #define CF_NO_DEPENDENCE_P(CF) ((CF)->n == NO_DEPENDENCE) 239 240 typedef vec<tree> affine_fn; 241 242 typedef struct 243 { 244 unsigned n; 245 affine_fn fns[MAX_DIM]; 246 } conflict_function; 247 248 /* What is a subscript? Given two array accesses a subscript is the 249 tuple composed of the access functions for a given dimension. 250 Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three 251 subscripts: (f1, g1), (f2, g2), (f3, g3). These three subscripts 252 are stored in the data_dependence_relation structure under the form 253 of an array of subscripts. */ 254 255 struct subscript 256 { 257 /* A description of the iterations for which the elements are 258 accessed twice. */ 259 conflict_function *conflicting_iterations_in_a; 260 conflict_function *conflicting_iterations_in_b; 261 262 /* This field stores the information about the iteration domain 263 validity of the dependence relation. */ 264 tree last_conflict; 265 266 /* Distance from the iteration that access a conflicting element in 267 A to the iteration that access this same conflicting element in 268 B. The distance is a tree scalar expression, i.e. a constant or a 269 symbolic expression, but certainly not a chrec function. */ 270 tree distance; 271 }; 272 273 typedef struct subscript *subscript_p; 274 275 #define SUB_CONFLICTS_IN_A(SUB) SUB->conflicting_iterations_in_a 276 #define SUB_CONFLICTS_IN_B(SUB) SUB->conflicting_iterations_in_b 277 #define SUB_LAST_CONFLICT(SUB) SUB->last_conflict 278 #define SUB_DISTANCE(SUB) SUB->distance 279 280 /* A data_dependence_relation represents a relation between two 281 data_references A and B. */ 282 283 struct data_dependence_relation 284 { 285 286 struct data_reference *a; 287 struct data_reference *b; 288 289 /* A "yes/no/maybe" field for the dependence relation: 290 291 - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence 292 relation between A and B, and the description of this relation 293 is given in the SUBSCRIPTS array, 294 295 - when "ARE_DEPENDENT == chrec_known", there is no dependence and 296 SUBSCRIPTS is empty, 297 298 - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence, 299 but the analyzer cannot be more specific. */ 300 tree are_dependent; 301 302 /* For each subscript in the dependence test, there is an element in 303 this array. This is the attribute that labels the edge A->B of 304 the data_dependence_relation. */ 305 vec<subscript_p> subscripts; 306 307 /* The analyzed loop nest. */ 308 vec<loop_p> loop_nest; 309 310 /* The classic direction vector. */ 311 vec<lambda_vector> dir_vects; 312 313 /* The classic distance vector. */ 314 vec<lambda_vector> dist_vects; 315 316 /* An index in loop_nest for the innermost loop that varies for 317 this data dependence relation. */ 318 unsigned inner_loop; 319 320 /* Is the dependence reversed with respect to the lexicographic order? */ 321 bool reversed_p; 322 323 /* When the dependence relation is affine, it can be represented by 324 a distance vector. */ 325 bool affine_p; 326 327 /* Set to true when the dependence relation is on the same data 328 access. */ 329 bool self_reference_p; 330 }; 331 332 typedef struct data_dependence_relation *ddr_p; 333 334 #define DDR_A(DDR) DDR->a 335 #define DDR_B(DDR) DDR->b 336 #define DDR_AFFINE_P(DDR) DDR->affine_p 337 #define DDR_ARE_DEPENDENT(DDR) DDR->are_dependent 338 #define DDR_SUBSCRIPTS(DDR) DDR->subscripts 339 #define DDR_SUBSCRIPT(DDR, I) DDR_SUBSCRIPTS (DDR)[I] 340 #define DDR_NUM_SUBSCRIPTS(DDR) DDR_SUBSCRIPTS (DDR).length () 341 342 #define DDR_LOOP_NEST(DDR) DDR->loop_nest 343 /* The size of the direction/distance vectors: the number of loops in 344 the loop nest. */ 345 #define DDR_NB_LOOPS(DDR) (DDR_LOOP_NEST (DDR).length ()) 346 #define DDR_INNER_LOOP(DDR) DDR->inner_loop 347 #define DDR_SELF_REFERENCE(DDR) DDR->self_reference_p 348 349 #define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects) 350 #define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects) 351 #define DDR_NUM_DIST_VECTS(DDR) \ 352 (DDR_DIST_VECTS (DDR).length ()) 353 #define DDR_NUM_DIR_VECTS(DDR) \ 354 (DDR_DIR_VECTS (DDR).length ()) 355 #define DDR_DIR_VECT(DDR, I) \ 356 DDR_DIR_VECTS (DDR)[I] 357 #define DDR_DIST_VECT(DDR, I) \ 358 DDR_DIST_VECTS (DDR)[I] 359 #define DDR_REVERSED_P(DDR) DDR->reversed_p 360 361 362 bool dr_analyze_innermost (struct data_reference *, struct loop *); 363 extern bool compute_data_dependences_for_loop (struct loop *, bool, 364 vec<loop_p> *, 365 vec<data_reference_p> *, 366 vec<ddr_p> *); 367 extern bool compute_data_dependences_for_bb (basic_block, bool, 368 vec<data_reference_p> *, 369 vec<ddr_p> *); 370 extern void debug_ddrs (vec<ddr_p> ); 371 extern void dump_data_reference (FILE *, struct data_reference *); 372 extern void debug_data_reference (struct data_reference *); 373 extern void debug_data_references (vec<data_reference_p> ); 374 extern void debug_data_dependence_relation (struct data_dependence_relation *); 375 extern void dump_data_dependence_relations (FILE *, vec<ddr_p> ); 376 extern void debug_data_dependence_relations (vec<ddr_p> ); 377 extern void free_dependence_relation (struct data_dependence_relation *); 378 extern void free_dependence_relations (vec<ddr_p> ); 379 extern void free_data_ref (data_reference_p); 380 extern void free_data_refs (vec<data_reference_p> ); 381 extern bool find_data_references_in_stmt (struct loop *, gimple, 382 vec<data_reference_p> *); 383 extern bool graphite_find_data_references_in_stmt (loop_p, loop_p, gimple, 384 vec<data_reference_p> *); 385 struct data_reference *create_data_ref (loop_p, loop_p, tree, gimple, bool); 386 extern bool find_loop_nest (struct loop *, vec<loop_p> *); 387 extern struct data_dependence_relation *initialize_data_dependence_relation 388 (struct data_reference *, struct data_reference *, vec<loop_p>); 389 extern void compute_affine_dependence (struct data_dependence_relation *, 390 loop_p); 391 extern void compute_self_dependence (struct data_dependence_relation *); 392 extern bool compute_all_dependences (vec<data_reference_p> , 393 vec<ddr_p> *, 394 vec<loop_p>, bool); 395 extern tree find_data_references_in_bb (struct loop *, basic_block, 396 vec<data_reference_p> *); 397 398 extern bool dr_may_alias_p (const struct data_reference *, 399 const struct data_reference *, bool); 400 extern bool dr_equal_offsets_p (struct data_reference *, 401 struct data_reference *); 402 403 404 /* Return true when the base objects of data references A and B are 405 the same memory object. */ 406 407 static inline bool 408 same_data_refs_base_objects (data_reference_p a, data_reference_p b) 409 { 410 return DR_NUM_DIMENSIONS (a) == DR_NUM_DIMENSIONS (b) 411 && operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), 0); 412 } 413 414 /* Return true when the data references A and B are accessing the same 415 memory object with the same access functions. */ 416 417 static inline bool 418 same_data_refs (data_reference_p a, data_reference_p b) 419 { 420 unsigned int i; 421 422 /* The references are exactly the same. */ 423 if (operand_equal_p (DR_REF (a), DR_REF (b), 0)) 424 return true; 425 426 if (!same_data_refs_base_objects (a, b)) 427 return false; 428 429 for (i = 0; i < DR_NUM_DIMENSIONS (a); i++) 430 if (!eq_evolutions_p (DR_ACCESS_FN (a, i), DR_ACCESS_FN (b, i))) 431 return false; 432 433 return true; 434 } 435 436 /* Return true when the DDR contains two data references that have the 437 same access functions. */ 438 439 static inline bool 440 same_access_functions (const struct data_dependence_relation *ddr) 441 { 442 unsigned i; 443 444 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) 445 if (!eq_evolutions_p (DR_ACCESS_FN (DDR_A (ddr), i), 446 DR_ACCESS_FN (DDR_B (ddr), i))) 447 return false; 448 449 return true; 450 } 451 452 /* Return true when DDR is an anti-dependence relation. */ 453 454 static inline bool 455 ddr_is_anti_dependent (ddr_p ddr) 456 { 457 return (DDR_ARE_DEPENDENT (ddr) == NULL_TREE 458 && DR_IS_READ (DDR_A (ddr)) 459 && DR_IS_WRITE (DDR_B (ddr)) 460 && !same_access_functions (ddr)); 461 } 462 463 /* Return true when DEPENDENCE_RELATIONS contains an anti-dependence. */ 464 465 static inline bool 466 ddrs_have_anti_deps (vec<ddr_p> dependence_relations) 467 { 468 unsigned i; 469 ddr_p ddr; 470 471 for (i = 0; dependence_relations.iterate (i, &ddr); i++) 472 if (ddr_is_anti_dependent (ddr)) 473 return true; 474 475 return false; 476 } 477 478 /* Returns the dependence level for a vector DIST of size LENGTH. 479 LEVEL = 0 means a lexicographic dependence, i.e. a dependence due 480 to the sequence of statements, not carried by any loop. */ 481 482 static inline unsigned 483 dependence_level (lambda_vector dist_vect, int length) 484 { 485 int i; 486 487 for (i = 0; i < length; i++) 488 if (dist_vect[i] != 0) 489 return i + 1; 490 491 return 0; 492 } 493 494 /* Return the dependence level for the DDR relation. */ 495 496 static inline unsigned 497 ddr_dependence_level (ddr_p ddr) 498 { 499 unsigned vector; 500 unsigned level = 0; 501 502 if (DDR_DIST_VECTS (ddr).exists ()) 503 level = dependence_level (DDR_DIST_VECT (ddr, 0), DDR_NB_LOOPS (ddr)); 504 505 for (vector = 1; vector < DDR_NUM_DIST_VECTS (ddr); vector++) 506 level = MIN (level, dependence_level (DDR_DIST_VECT (ddr, vector), 507 DDR_NB_LOOPS (ddr))); 508 return level; 509 } 510 511 512 513 /* A Reduced Dependence Graph (RDG) vertex representing a statement. */ 514 typedef struct rdg_vertex 515 { 516 /* The statement represented by this vertex. */ 517 gimple stmt; 518 519 /* Vector of data-references in this statement. */ 520 vec<data_reference_p> datarefs; 521 522 /* True when the statement contains a write to memory. */ 523 bool has_mem_write; 524 525 /* True when the statement contains a read from memory. */ 526 bool has_mem_reads; 527 } *rdg_vertex_p; 528 529 #define RDGV_STMT(V) ((struct rdg_vertex *) ((V)->data))->stmt 530 #define RDGV_DATAREFS(V) ((struct rdg_vertex *) ((V)->data))->datarefs 531 #define RDGV_HAS_MEM_WRITE(V) ((struct rdg_vertex *) ((V)->data))->has_mem_write 532 #define RDGV_HAS_MEM_READS(V) ((struct rdg_vertex *) ((V)->data))->has_mem_reads 533 #define RDG_STMT(RDG, I) RDGV_STMT (&(RDG->vertices[I])) 534 #define RDG_DATAREFS(RDG, I) RDGV_DATAREFS (&(RDG->vertices[I])) 535 #define RDG_MEM_WRITE_STMT(RDG, I) RDGV_HAS_MEM_WRITE (&(RDG->vertices[I])) 536 #define RDG_MEM_READS_STMT(RDG, I) RDGV_HAS_MEM_READS (&(RDG->vertices[I])) 537 538 void debug_rdg_vertex (struct graph *, int); 539 void debug_rdg_component (struct graph *, int); 540 void dump_rdg (FILE *, struct graph *); 541 void debug_rdg (struct graph *); 542 int rdg_vertex_for_stmt (struct graph *, gimple); 543 544 /* Data dependence type. */ 545 546 enum rdg_dep_type 547 { 548 /* Read After Write (RAW). */ 549 flow_dd = 'f', 550 551 /* Write After Read (WAR). */ 552 anti_dd = 'a', 553 554 /* Write After Write (WAW). */ 555 output_dd = 'o', 556 557 /* Read After Read (RAR). */ 558 input_dd = 'i' 559 }; 560 561 /* Dependence information attached to an edge of the RDG. */ 562 563 typedef struct rdg_edge 564 { 565 /* Type of the dependence. */ 566 enum rdg_dep_type type; 567 568 /* Levels of the dependence: the depth of the loops that carry the 569 dependence. */ 570 unsigned level; 571 572 /* Dependence relation between data dependences, NULL when one of 573 the vertices is a scalar. */ 574 ddr_p relation; 575 } *rdg_edge_p; 576 577 #define RDGE_TYPE(E) ((struct rdg_edge *) ((E)->data))->type 578 #define RDGE_LEVEL(E) ((struct rdg_edge *) ((E)->data))->level 579 #define RDGE_RELATION(E) ((struct rdg_edge *) ((E)->data))->relation 580 581 struct graph *build_rdg (struct loop *, 582 vec<loop_p> *, 583 vec<ddr_p> *, 584 vec<data_reference_p> *); 585 struct graph *build_empty_rdg (int); 586 void free_rdg (struct graph *); 587 588 /* Return the index of the variable VAR in the LOOP_NEST array. */ 589 590 static inline int 591 index_in_loop_nest (int var, vec<loop_p> loop_nest) 592 { 593 struct loop *loopi; 594 int var_index; 595 596 for (var_index = 0; loop_nest.iterate (var_index, &loopi); 597 var_index++) 598 if (loopi->num == var) 599 break; 600 601 return var_index; 602 } 603 604 bool rdg_defs_used_in_other_loops_p (struct graph *, int); 605 606 /* Returns true when the data reference DR the form "A[i] = ..." 607 with a stride equal to its unit type size. */ 608 609 static inline bool 610 adjacent_dr_p (struct data_reference *dr) 611 { 612 /* If this is a bitfield store bail out. */ 613 if (TREE_CODE (DR_REF (dr)) == COMPONENT_REF 614 && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (dr), 1))) 615 return false; 616 617 if (!DR_STEP (dr) 618 || TREE_CODE (DR_STEP (dr)) != INTEGER_CST) 619 return false; 620 621 return tree_int_cst_equal (fold_unary (ABS_EXPR, TREE_TYPE (DR_STEP (dr)), 622 DR_STEP (dr)), 623 TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr)))); 624 } 625 626 /* In tree-data-ref.c */ 627 void split_constant_offset (tree , tree *, tree *); 628 629 /* Strongly connected components of the reduced data dependence graph. */ 630 631 typedef struct rdg_component 632 { 633 int num; 634 vec<int> vertices; 635 } *rdgc; 636 637 638 639 /* Compute the greatest common divisor of a VECTOR of SIZE numbers. */ 640 641 static inline int 642 lambda_vector_gcd (lambda_vector vector, int size) 643 { 644 int i; 645 int gcd1 = 0; 646 647 if (size > 0) 648 { 649 gcd1 = vector[0]; 650 for (i = 1; i < size; i++) 651 gcd1 = gcd (gcd1, vector[i]); 652 } 653 return gcd1; 654 } 655 656 /* Allocate a new vector of given SIZE. */ 657 658 static inline lambda_vector 659 lambda_vector_new (int size) 660 { 661 return (lambda_vector) ggc_alloc_cleared_atomic (sizeof (int) * size); 662 } 663 664 /* Clear out vector VEC1 of length SIZE. */ 665 666 static inline void 667 lambda_vector_clear (lambda_vector vec1, int size) 668 { 669 memset (vec1, 0, size * sizeof (*vec1)); 670 } 671 672 /* Returns true when the vector V is lexicographically positive, in 673 other words, when the first nonzero element is positive. */ 674 675 static inline bool 676 lambda_vector_lexico_pos (lambda_vector v, 677 unsigned n) 678 { 679 unsigned i; 680 for (i = 0; i < n; i++) 681 { 682 if (v[i] == 0) 683 continue; 684 if (v[i] < 0) 685 return false; 686 if (v[i] > 0) 687 return true; 688 } 689 return true; 690 } 691 692 /* Return true if vector VEC1 of length SIZE is the zero vector. */ 693 694 static inline bool 695 lambda_vector_zerop (lambda_vector vec1, int size) 696 { 697 int i; 698 for (i = 0; i < size; i++) 699 if (vec1[i] != 0) 700 return false; 701 return true; 702 } 703 704 /* Allocate a matrix of M rows x N cols. */ 705 706 static inline lambda_matrix 707 lambda_matrix_new (int m, int n, struct obstack *lambda_obstack) 708 { 709 lambda_matrix mat; 710 int i; 711 712 mat = (lambda_matrix) obstack_alloc (lambda_obstack, 713 sizeof (lambda_vector *) * m); 714 715 for (i = 0; i < m; i++) 716 mat[i] = lambda_vector_new (n); 717 718 return mat; 719 } 720 721 #endif /* GCC_TREE_DATA_REF_H */ 722