1 /* CYGNUS LOCAL dependency analysis */
3 /* Analyze loop dependencies
4 Copyright (C) 2000 Free Software Foundation, Inc.
6 This file is part of GNU CC.
8 GNU CC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2, or (at your option)
13 GNU CC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GNU CC; see the file COPYING. If not, write to
20 the Free Software Foundation, 59 Temple Place - Suite 330,
21 Boston, MA 02111-1307, USA. */
24 Practical Dependence Testing, Goff, Kennedy, Tseng, PLDI, 1991
25 High Performance Compilers for Parallel Computing, Wolfe
37 #define MAX_SUBSCRIPTS 13
40 We perform the following steps:
42 Build the data structures def_use_chain, loop_chain, and induction_chain.
44 Determine if a loop index is a normalized induction variable.
45 A loop is currently considered to be a for loop having an index set to an
46 initial value, conditional check of the index, and increment/decrement of
49 Determine the distance and direction vectors. Both are two dimensioned
50 arrays where the first dimension represents a loop and the second
51 dimension represents a subscript. Dependencies are actually per loop, not
52 per subscript. So for:
53 for (i = 0; i < 10; i++)
54 for (j = 0; j < 10; j++)
55 array [i][j] = array[i][j-1]
56 We find the dependencies: loop1/sub_i, loop1/sub_j, loop2/sub_i, loop2/sub_j
57 and then intersect loop1/sub_i V loop2/sub_i and loop1/sub_i V loop2/sub_j
58 We determine the type of dependence, which determines which test we use.
59 We then try to refine the type of dependence we have and add the
60 dependence to the dep_chain
63 enum dependence_type
{flow
, anti
, output
, none
};
64 static const char * dependence_string
[] = {"flow", "anti", "output", "none"};
66 enum direction_type
{lt
, le
, eq
, gt
, ge
, star
, independent
, undef
};
67 static const char * direction_string
[] = {"<", "<=", "=", ">", ">=", "*",
68 "INDEPENDENT", "UNDEFINED"};
70 enum def_use_type
{def
, use
, init_def_use
};
72 enum du_status_type
{seen
, unseen
};
74 enum loop_status_type
{normal
, unnormal
};
76 enum complexity_type
{ziv
, strong_siv
, weak_siv
, weak_zero_siv
,
77 weak_crossing_siv
, miv
};
79 /* Given a def/use one can chase the next chain to follow the def/use
80 for that variable. Alternately one can sequentially follow each
81 element of def_use_chain. */
83 typedef struct def_use
87 /* loop containing this def/use */
94 enum def_use_type type
;
96 enum du_status_type status
;
97 /* next def/use for this same name */
99 /* dependencies for this def */
100 struct dependence
*dep
;
103 /* Given a loop* one can chase the next_nest chain to follow the nested
104 loops for that loop. Alternately one can sequentially follow each
105 element of loop_chain and check outer_loop to get all loops
106 contained within a certain loop. */
110 /* outermost loop containing this loop */
113 tree containing_loop
;
114 /* nest level for this loop */
116 /* can loop be normalized? */
117 enum loop_status_type status
;
118 /* loop* for loop contained in this loop */
119 struct loop
*next_nest
;
120 /* induction variables for this loop. Currently only the index variable. */
121 struct induction
*ind
;
124 /* Pointed to by loop. One per induction variable. */
126 typedef struct induction
130 /* increment. Currently only +1 or -1 */
136 /* next induction variable for this loop. Currently null. */
137 struct induction
*next
;
140 /* Pointed to by def/use. One per dependence. */
142 typedef struct dependence
146 enum dependence_type dependence
;
147 enum direction_type direction
[MAX_SUBSCRIPTS
];
148 int distance
[MAX_SUBSCRIPTS
];
149 struct dependence
*next
;
152 /* subscripts are represented by an array of these. Each reflects one
153 X * i + Y term, where X and Y are constants. */
155 typedef struct subscript
157 /* ordinal subscript number */
165 /* next subscript term. Currently null. */
166 struct subscript
*next
;
169 /* Remember the destination the front end encountered. */
171 static tree dest_to_remember
;
173 /* Chain for def_use */
174 static varray_type def_use_chain
;
176 /* Chain for dependence */
177 static varray_type dep_chain
;
180 static varray_type loop_chain
;
182 /* Chain for induction */
183 static varray_type induction_chain
;
185 void init_dependence_analysis
PARAMS ((tree
));
186 static void build_def_use
PARAMS ((tree
, enum def_use_type
));
187 static loop
* add_loop
PARAMS ((tree
, tree
, int));
188 static int find_induction_variable
PARAMS ((tree
, tree
, tree
, loop
*));
189 static int get_low_bound
PARAMS ((tree
, char*));
190 static int have_induction_variable
PARAMS ((tree
, char*));
191 static void link_loops
PARAMS ((void));
192 static void get_node_dependence
PARAMS ((void));
193 static void check_node_dependence
PARAMS ((def_use
*));
194 static int get_coefficients
PARAMS ((def_use
*, subscript
[]));
195 static int get_one_coefficient
PARAMS ((tree
, subscript
*, def_use
*, enum tree_code
*));
196 static void normalize_coefficients
PARAMS ((subscript
[], loop
*, int));
197 static void classify_dependence
PARAMS ((subscript
[], subscript
[],
198 enum complexity_type
[], int*, int));
199 static void ziv_test
PARAMS ((subscript
[], subscript
[], enum direction_type
[][],
200 int[][], loop
*, int));
201 static void siv_test
PARAMS ((subscript
[], subscript
[], enum direction_type
[][],
202 int[][], loop
*, int));
203 static int check_subscript_induction
PARAMS ((subscript
*, subscript
*, loop
*));
204 static void gcd_test
PARAMS ((subscript
[], subscript
[], enum direction_type
[][],
205 int[][], loop
*, int));
206 static int find_gcd
PARAMS ((int, int));
207 static void merge_dependencies
PARAMS ((enum direction_type
[][], int[][], int, int));
208 static void dump_array_ref
PARAMS ((tree
));
209 static void dump_one_node
PARAMS ((def_use
*, varray_type
*));
210 static void dump_node_dependence
PARAMS ((void));
211 int search_dependence
PARAMS ((tree
));
212 void remember_dest_for_dependence
PARAMS ((tree
));
213 int have_dependence_p
PARAMS ((rtx
, rtx
, enum direction_type
[], int[]));
214 void end_dependence_analysis
PARAMS ((void));
216 /* Build dependence chain 'dep_chain', which is used by have_dependence_p,
217 for the function given by EXP. */
220 init_dependence_analysis (exp
)
225 VARRAY_GENERIC_PTR_INIT (def_use_chain
, 50, "def_use_chain");
226 VARRAY_GENERIC_PTR_INIT (dep_chain
, 50, "dep_chain");
227 VARRAY_GENERIC_PTR_INIT (loop_chain
, 50, "loop_chain");
228 VARRAY_GENERIC_PTR_INIT (induction_chain
, 50, "induction_chain");
230 build_def_use (exp
, init_def_use
);
234 get_node_dependence ();
236 /* dump_node_dependence (&def_use_chain);*/
238 for (du_ptr
= VARRAY_TOP (def_use_chain
, generic
);
239 VARRAY_POP (def_use_chain
);
240 du_ptr
= VARRAY_TOP (def_use_chain
, generic
))
245 VARRAY_FREE (def_use_chain
);
246 VARRAY_FREE (loop_chain
);
247 VARRAY_FREE (induction_chain
);
250 /* Build ARRAY_REF def/use info 'def_use_chain' starting at EXP which is a def
254 build_def_use (exp
, du_type
)
256 enum def_use_type du_type
;
258 static tree outer_loop
;
260 static tree current_loop
;
262 static loop
*loop_def
;
268 if (du_type
== init_def_use
)
276 switch (TREE_CODE (node
))
279 node
= TREE_OPERAND (node
, 0);
282 build_def_use (TREE_VALUE (node
), 0);
283 node
= TREE_CHAIN (node
);
286 node
= TREE_CHAIN (node
);
289 if (! nloop
) outer_loop
= node
;
292 loop_def
= add_loop (node
, outer_loop
, nloop
);
293 if (find_induction_variable (TREE_OPERAND (node
, 0),
294 TREE_OPERAND (node
, 1),
295 TREE_OPERAND (node
, 2), loop_def
)
297 loop_def
->status
= unnormal
;
299 build_def_use (TREE_OPERAND (node
, 3), 0);
302 node
= TREE_CHAIN (node
);
305 /* Is an induction variable modified? */
307 && TREE_CODE (TREE_OPERAND (node
, 0)) == VAR_DECL
308 && have_induction_variable
309 (loop_def
->outer_loop
,
310 IDENTIFIER_POINTER (DECL_NAME (TREE_OPERAND (node
, 0)))) >= 0)
311 loop_def
->status
= unnormal
;
313 if (TREE_CODE (TREE_OPERAND (node
, 0)) == ARRAY_REF
314 || TREE_CODE (TREE_OPERAND (node
, 0)) == INDIRECT_REF
)
315 build_def_use (TREE_OPERAND (node
, 0), def
);
317 build_def_use (TREE_OPERAND (node
, 1), use
);
318 node
= TREE_CHAIN (node
);
321 if (! TREE_OPERAND (node
, 1)
322 || TREE_CODE (TREE_OPERAND (node
, 1)) != ARRAY_REF
)
327 node
= TREE_OPERAND (node
, 1);
332 char null_string
= '\0';
334 VARRAY_PUSH_GENERIC_PTR (def_use_chain
, xmalloc (sizeof (def_use
)));
335 du_ptr
= VARRAY_GENERIC_PTR (def_use_chain
, du_idx
++);
336 du_ptr
->type
= du_type
;
337 du_ptr
->status
= unseen
;
338 du_ptr
->outer_loop
= outer_loop
;
339 du_ptr
->containing_loop
= current_loop
;
340 du_ptr
->expression
= node
;
341 du_ptr
->variable
= &null_string
;
344 for (array_ref
= node
;
345 TREE_CODE (array_ref
) == ARRAY_REF
;
346 array_ref
= TREE_OPERAND (array_ref
, 0))
349 if (TREE_CODE (array_ref
) == COMPONENT_REF
)
351 array_ref
= TREE_OPERAND (array_ref
, 1);
352 if (! (TREE_CODE (array_ref
) == FIELD_DECL
353 && TREE_CODE (TREE_TYPE (array_ref
)) == ARRAY_TYPE
))
364 && strcmp (IDENTIFIER_POINTER (DECL_NAME (array_ref
)),
365 ((def_use
*) (VARRAY_GENERIC_PTR
366 (def_use_chain
, i
)))->variable
);
372 for (tmp_duc
= ((def_use
*) (VARRAY_GENERIC_PTR (def_use_chain
, i
)));
374 tmp_duc
= ((def_use
*)tmp_duc
->next
));
375 tmp_duc
->next
= du_ptr
;
377 else du_ptr
->next
= 0;
378 du_ptr
->variable
= IDENTIFIER_POINTER (DECL_NAME (array_ref
));
385 node
= TREE_CHAIN (node
);
389 if (TREE_CODE (TREE_OPERAND (node
, 0)) == MODIFY_EXPR
)
390 build_def_use (TREE_OPERAND (node
, 0), def
);
391 node
= TREE_CHAIN (node
);
395 if (TREE_CODE_CLASS (TREE_CODE (node
)) == '2')
397 build_def_use (TREE_OPERAND (node
, 0), use
);
398 build_def_use (TREE_OPERAND (node
, 1), use
);
399 node
= TREE_CHAIN (node
);
406 /* Add a loop to 'loop_chain' corresponding to for loop LOOP_NODE at depth
407 NLOOP, whose outermost loop is OUTER_LOOP */
410 add_loop (loop_node
, outer_loop
, nloop
)
417 VARRAY_PUSH_GENERIC_PTR (loop_chain
, xmalloc (sizeof (loop
)));
418 loop_ptr
= VARRAY_TOP (loop_chain
, generic
);
419 loop_ptr
->outer_loop
= outer_loop
;
420 loop_ptr
->containing_loop
= loop_node
;
421 loop_ptr
->depth
= nloop
;
422 loop_ptr
->status
= normal
;
423 loop_ptr
->next_nest
= 0;
428 /* Update LOOP_DEF if for loop's COND_NODE and INCR_NODE define an index that
429 is a normalized induction variable. */
432 find_induction_variable (init_node
, cond_node
, incr_node
, loop_def
)
439 enum tree_code incr_code
;
442 if (! init_node
|| ! incr_node
|| ! cond_node
)
444 /* Allow for ',' operator in increment expression of FOR */
447 while (TREE_CODE (incr
) == COMPOUND_EXPR
)
449 incr_code
= TREE_CODE (TREE_OPERAND (incr
, 0));
450 if (incr_code
== PREDECREMENT_EXPR
|| incr_code
== POSTDECREMENT_EXPR
451 || incr_code
== PREINCREMENT_EXPR
|| incr_code
== POSTINCREMENT_EXPR
)
453 incr_node
= TREE_OPERAND (incr
, 0);
456 incr_code
= TREE_CODE (TREE_OPERAND (incr
, 1));
457 if (incr_code
== PREDECREMENT_EXPR
|| incr_code
== POSTDECREMENT_EXPR
458 || incr_code
== PREINCREMENT_EXPR
|| incr_code
== POSTINCREMENT_EXPR
)
460 incr_node
= TREE_OPERAND (incr
, 1);
463 incr
= TREE_OPERAND (incr
, 1);
466 /* Allow index condition to be part of logical expression */
467 cond_node
= TREE_VALUE (cond_node
);
470 #define INDEX_LIMIT_CHECK(node) \
471 (TREE_CODE_CLASS (TREE_CODE (node)) == '<') \
472 && (TREE_CODE (TREE_OPERAND (node, 0)) == VAR_DECL \
473 && (IDENTIFIER_POINTER (DECL_NAME (TREE_OPERAND (node, 0))) \
474 == IDENTIFIER_POINTER (DECL_NAME (TREE_OPERAND (incr_node, 0))))) \
477 while (TREE_CODE (incr
) == TRUTH_ANDIF_EXPR
478 || TREE_CODE (incr
) == TRUTH_ORIF_EXPR
)
480 if (INDEX_LIMIT_CHECK (TREE_OPERAND (incr
, 0)))
482 cond_node
= TREE_OPERAND (incr
, 0);
485 if (INDEX_LIMIT_CHECK (TREE_OPERAND (incr
, 1)))
487 cond_node
= TREE_OPERAND (incr
, 1);
490 incr
= TREE_OPERAND (incr
, 0);
493 incr_code
= TREE_CODE (incr_node
);
494 if ((incr_code
== PREDECREMENT_EXPR
|| incr_code
== POSTDECREMENT_EXPR
495 || incr_code
== PREINCREMENT_EXPR
|| incr_code
== POSTINCREMENT_EXPR
)
496 && TREE_CODE_CLASS (TREE_CODE (cond_node
)) == '<')
498 if (!INDEX_LIMIT_CHECK (cond_node
))
501 VARRAY_PUSH_GENERIC_PTR (induction_chain
, xmalloc (sizeof (induction
)));
502 ind_ptr
= VARRAY_TOP (induction_chain
, generic
);
503 loop_def
->ind
= ind_ptr
;
504 ind_ptr
->variable
= IDENTIFIER_POINTER (DECL_NAME (TREE_OPERAND
506 ind_ptr
->increment
= TREE_INT_CST_LOW (TREE_OPERAND (incr_node
, 1));
507 if (TREE_CODE (incr_node
) == PREDECREMENT_EXPR
508 || TREE_CODE (incr_node
) == POSTDECREMENT_EXPR
)
509 ind_ptr
->increment
= -ind_ptr
->increment
;
511 ind_ptr
->low_bound
= get_low_bound (init_node
, ind_ptr
->variable
);
512 if (TREE_CODE (TREE_OPERAND (cond_node
, 0)) == VAR_DECL
513 && IDENTIFIER_POINTER (DECL_NAME (TREE_OPERAND (cond_node
, 0)))
514 == ind_ptr
->variable
)
515 if (TREE_CODE (TREE_OPERAND (cond_node
, 1)) == INTEGER_CST
)
516 ind_ptr
->high_bound
= TREE_INT_CST_LOW (TREE_OPERAND (cond_node
, 1));
518 ind_ptr
->high_bound
= ind_ptr
->increment
< 0 ? INT_MIN
: INT_MAX
;
519 else if (TREE_CODE (TREE_OPERAND (cond_node
, 1)) == VAR_DECL
520 && IDENTIFIER_POINTER (DECL_NAME (TREE_OPERAND (cond_node
, 1)))
521 == ind_ptr
->variable
)
522 if (TREE_CODE (TREE_OPERAND (cond_node
, 0)) == INTEGER_CST
)
523 ind_ptr
->high_bound
= TREE_INT_CST_LOW (TREE_OPERAND (cond_node
, 0));
525 ind_ptr
->high_bound
= ind_ptr
->increment
< 0 ? INT_MIN
: INT_MAX
;
532 /* Return the low bound for induction VARIABLE in NODE */
535 get_low_bound (node
, variable
)
540 if (TREE_CODE (node
) == SCOPE_STMT
)
541 node
= TREE_CHAIN (node
);
546 while (TREE_CODE (node
) == COMPOUND_EXPR
)
548 if (TREE_CODE (TREE_OPERAND (node
, 0)) == MODIFY_EXPR
549 && (TREE_CODE (TREE_OPERAND (node
, 0)) == VAR_DECL
550 && IDENTIFIER_POINTER (DECL_NAME (TREE_OPERAND (node
, 0)))
555 if (TREE_CODE (node
) == EXPR_STMT
)
556 node
= TREE_OPERAND (node
, 0);
557 if (TREE_CODE (node
) == MODIFY_EXPR
558 && (TREE_CODE (TREE_OPERAND (node
, 0)) == VAR_DECL
559 && IDENTIFIER_POINTER (DECL_NAME (TREE_OPERAND (node
, 0)))
562 return TREE_INT_CST_LOW (TREE_OPERAND (node
, 1));
568 /* Return the ordinal subscript position for IND_VAR if it is an induction
569 variable contained in OUTER_LOOP, otherwise return -1. */
572 have_induction_variable (outer_loop
, ind_var
)
578 unsigned int ind_idx
= 0;
579 unsigned int loop_idx
= 0;
581 for (loop_ptr
= VARRAY_GENERIC_PTR (loop_chain
, loop_idx
);
582 loop_ptr
&& loop_idx
< VARRAY_SIZE (loop_chain
);
583 loop_ptr
= VARRAY_GENERIC_PTR (loop_chain
, ++loop_idx
))
584 if (loop_ptr
->outer_loop
== outer_loop
)
585 for (ind_ptr
= loop_ptr
->ind
;
586 ind_ptr
&& ind_idx
< VARRAY_SIZE (induction_chain
);
587 ind_ptr
= ind_ptr
->next
)
589 if (! strcmp (ind_ptr
->variable
, ind_var
))
595 /* Chain the nodes of 'loop_chain'. */
600 unsigned int loop_idx
= 0;
601 loop
*loop_ptr
, *prev_loop_ptr
= 0;
603 prev_loop_ptr
= VARRAY_GENERIC_PTR (loop_chain
, loop_idx
);
604 for (loop_ptr
= VARRAY_GENERIC_PTR (loop_chain
, ++loop_idx
);
605 loop_ptr
&& loop_idx
< VARRAY_SIZE (loop_chain
);
606 loop_ptr
= VARRAY_GENERIC_PTR (loop_chain
, ++loop_idx
))
608 if (prev_loop_ptr
->outer_loop
== loop_ptr
->outer_loop
)
610 if (prev_loop_ptr
->depth
== loop_ptr
->depth
- 1)
611 prev_loop_ptr
->next_nest
= loop_ptr
;
612 prev_loop_ptr
= loop_ptr
;
617 /* Check the dependence for each member of 'def_use_chain'. */
620 get_node_dependence ()
626 for (du_ptr
= VARRAY_GENERIC_PTR (def_use_chain
, du_idx
);
627 du_ptr
&& du_idx
< VARRAY_SIZE (def_use_chain
);
628 du_ptr
= VARRAY_GENERIC_PTR (def_use_chain
, du_idx
++))
630 if (du_ptr
->status
== unseen
)
631 check_node_dependence (du_ptr
);
635 /* Check the dependence for definition DU. */
638 check_node_dependence (du
)
641 def_use
*def_ptr
, *use_ptr
;
642 dependence
*dep_ptr
, *dep_list
;
643 subscript icoefficients
[MAX_SUBSCRIPTS
];
644 subscript ocoefficients
[MAX_SUBSCRIPTS
];
645 loop
*loop_ptr
, *ck_loop_ptr
;
646 unsigned int loop_idx
= 0;
647 int distance
[MAX_SUBSCRIPTS
][MAX_SUBSCRIPTS
];
651 enum direction_type direction
[MAX_SUBSCRIPTS
][MAX_SUBSCRIPTS
];
652 enum complexity_type complexity
[MAX_SUBSCRIPTS
];
656 for (j
= 1 ; j
< MAX_SUBSCRIPTS
; j
++)
658 direction
[j
][0] = undef
;
662 for (def_ptr
= du
; def_ptr
; def_ptr
= def_ptr
->next
)
664 if (def_ptr
->type
!= def
)
666 subscript_count
= get_coefficients (def_ptr
, ocoefficients
);
667 if (subscript_count
< 0)
671 for (loop_ptr
= VARRAY_GENERIC_PTR (loop_chain
, loop_idx
);
672 loop_ptr
&& loop_idx
< VARRAY_SIZE (loop_chain
);
673 loop_ptr
= VARRAY_GENERIC_PTR (loop_chain
, ++loop_idx
))
675 if (loop_ptr
->outer_loop
== def_ptr
->outer_loop
)
680 for (ck_loop_ptr
= loop_ptr
;
681 ck_loop_ptr
&& loop_idx
< VARRAY_SIZE (loop_chain
);
682 ck_loop_ptr
= VARRAY_GENERIC_PTR (loop_chain
, ++loop_idx
))
684 if (ck_loop_ptr
->outer_loop
== def_ptr
->outer_loop
685 && ck_loop_ptr
->status
== unnormal
)
691 normalize_coefficients (ocoefficients
, loop_ptr
, subscript_count
);
693 for (use_ptr
= du
; use_ptr
; use_ptr
= use_ptr
->next
)
695 if (def_ptr
== use_ptr
696 || def_ptr
->outer_loop
!= use_ptr
->outer_loop
)
698 def_ptr
->status
= seen
;
699 use_ptr
->status
= seen
;
700 subscript_count
= get_coefficients (use_ptr
, icoefficients
);
701 normalize_coefficients (icoefficients
, loop_ptr
, subscript_count
);
702 classify_dependence (icoefficients
, ocoefficients
, complexity
,
703 &separability
, subscript_count
);
705 for (i
= 1, ck_loop_ptr
= loop_ptr
; ck_loop_ptr
; i
++)
707 for (j
= 1; j
<= subscript_count
; j
++)
709 direction
[i
][j
] = star
;
710 distance
[i
][j
] = INT_MAX
;
711 if (separability
&& complexity
[j
] == ziv
)
712 ziv_test (icoefficients
, ocoefficients
, direction
, distance
,
714 else if (separability
715 && (complexity
[j
] == strong_siv
716 || complexity
[j
] == weak_zero_siv
717 || complexity
[j
] == weak_crossing_siv
))
718 siv_test (icoefficients
, ocoefficients
, direction
, distance
,
721 gcd_test (icoefficients
, ocoefficients
, direction
, distance
,
723 /* ?? Add other tests: single variable exact test, banerjee */
726 ck_loop_ptr
= ck_loop_ptr
->next_nest
;
729 merge_dependencies (direction
, distance
, i
- 1, j
- 1);
732 for (j
= 1; j
<= i
- 1; j
++)
734 if (direction
[j
][0] != independent
)
737 if (! have_dependence
)
740 VARRAY_PUSH_GENERIC_PTR (dep_chain
, xmalloc (sizeof (dependence
)));
741 dep_ptr
= VARRAY_TOP (dep_chain
, generic
);
742 dep_ptr
->source
= use_ptr
->expression
;
743 dep_ptr
->destination
= def_ptr
->expression
;
746 if (def_ptr
< use_ptr
&& use_ptr
->type
== use
)
747 dep_ptr
->dependence
= flow
;
748 else if (def_ptr
> use_ptr
&& use_ptr
->type
== use
)
749 dep_ptr
->dependence
= anti
;
750 else dep_ptr
->dependence
= output
;
752 for (j
= 1 ; j
<= i
- 1 ; j
++)
754 if (direction
[j
][0] == gt
)
756 dep_ptr
->dependence
= anti
;
757 direction
[j
][0] = lt
;
758 distance
[j
][0] = -distance
[j
][0];
761 else if (direction
[j
][0] == lt
)
763 dep_ptr
->dependence
= flow
;
767 for (j
= 1 ; j
< MAX_SUBSCRIPTS
; j
++)
769 dep_ptr
->direction
[j
] = direction
[j
][0];
770 dep_ptr
->distance
[j
] = distance
[j
][0];
773 for (dep_list
= def_ptr
->dep
;
774 dep_list
&& dep_list
->next
;
775 dep_list
= dep_list
->next
)
780 /* Dummy for rtl interface */
781 dependence
*dep_root_ptr
;
783 VARRAY_PUSH_GENERIC_PTR (dep_chain
, xmalloc (sizeof (dependence
)));
784 dep_root_ptr
= VARRAY_TOP (dep_chain
, generic
);
785 dep_root_ptr
->source
= 0;
786 dep_root_ptr
->destination
= def_ptr
->expression
;
787 dep_root_ptr
->dependence
= none
;
788 dep_root_ptr
->next
= dep_ptr
;
789 def_ptr
->dep
= dep_ptr
;
792 dep_list
->next
= dep_ptr
;
797 /* Get the COEFFICIENTS and offset for def/use DU. */
800 get_coefficients (du
, coefficients
)
802 subscript coefficients
[MAX_SUBSCRIPTS
];
810 for (array_ref
= du
->expression
;
811 TREE_CODE (array_ref
) == ARRAY_REF
;
812 array_ref
= TREE_OPERAND (array_ref
, 0))
817 for (i
= 0; i
< MAX_SUBSCRIPTS
; i
++)
819 coefficients
[i
].position
= 0;
820 coefficients
[i
].coefficient
= INT_MIN
;
821 coefficients
[i
].offset
= INT_MIN
;
822 coefficients
[i
].variable
= 0;
823 coefficients
[i
].next
= 0;
826 for (array_ref
= du
->expression
;
827 TREE_CODE (array_ref
) == ARRAY_REF
;
828 array_ref
= TREE_OPERAND (array_ref
, 0))
830 if (TREE_CODE (TREE_OPERAND (array_ref
, 1)) == INTEGER_CST
)
831 coefficients
[idx
].offset
= TREE_INT_CST_LOW (TREE_OPERAND (array_ref
, 1));
833 if (get_one_coefficient (TREE_OPERAND (array_ref
, 1),
834 &coefficients
[idx
], du
, 0) < 0)
841 /* Get the COEFFICIENTS and offset for NODE having TYPE and defined in DU. */
844 get_one_coefficient (node
, coefficients
, du
, type
)
846 subscript
*coefficients
;
848 enum tree_code
*type
;
850 enum tree_code tree_op
, tree_op_code
;
853 tree_op
= TREE_CODE (node
);
857 if (tree_op
== VAR_DECL
)
859 index
= have_induction_variable (du
->outer_loop
,
860 IDENTIFIER_POINTER (DECL_NAME (node
)));
863 coefficients
->position
= index
;
864 coefficients
->variable
= IDENTIFIER_POINTER (DECL_NAME (node
));
865 coefficients
->coefficient
= 1;
866 if (coefficients
->offset
== INT_MIN
)
867 coefficients
->offset
= 0;
871 else if (tree_op
== INTEGER_CST
)
873 return TREE_INT_CST_LOW (node
);
875 else if (tree_op
== NON_LVALUE_EXPR
)
877 return get_one_coefficient (TREE_OPERAND (node
, 0), coefficients
, du
,
880 else if (tree_op
== PLUS_EXPR
)
882 value
= get_one_coefficient (TREE_OPERAND (node
, 0), coefficients
, du
,
884 if (tree_op_code
== INTEGER_CST
)
885 coefficients
->offset
= value
;
887 value
= get_one_coefficient (TREE_OPERAND (node
, 1), coefficients
, du
,
889 if (tree_op_code
== INTEGER_CST
)
890 coefficients
->offset
= value
;
894 else if (tree_op
== MINUS_EXPR
)
896 value
= get_one_coefficient (TREE_OPERAND (node
, 0), coefficients
, du
,
898 if (tree_op_code
== INTEGER_CST
)
899 coefficients
->offset
= value
;
901 value
= get_one_coefficient (TREE_OPERAND (node
, 1), coefficients
, du
,
903 if (tree_op_code
== INTEGER_CST
)
904 coefficients
->offset
= -value
;
908 else if (tree_op
== MULT_EXPR
)
910 int value0
, value1
, value0_is_idx
, value1_is_idx
;
912 value0
= get_one_coefficient (TREE_OPERAND (node
, 0), coefficients
, du
,
914 if (tree_op_code
== VAR_DECL
)
917 value1
= get_one_coefficient (TREE_OPERAND (node
, 1), coefficients
, du
,
919 if (tree_op_code
== VAR_DECL
)
923 coefficients
->coefficient
= value1
;
924 else if (value1_is_idx
)
925 coefficients
->coefficient
= value0
;
930 /* Adjust the COEFFICIENTS as if loop LOOP_PTR were normalized to start at 0. */
933 normalize_coefficients (coefficients
, loop_ptr
, count
)
934 subscript coefficients
[MAX_SUBSCRIPTS
];
942 for (i
= 1; i
<= count
; i
++)
944 for (ck_loop_ptr
= loop_ptr
; ck_loop_ptr
;
945 ck_loop_ptr
= ck_loop_ptr
->next_nest
)
946 for (ind_ptr
= ck_loop_ptr
->ind
; ind_ptr
; ind_ptr
= ind_ptr
->next
)
948 if (coefficients
[i
].variable
== ind_ptr
->variable
)
950 if (ind_ptr
->low_bound
< ind_ptr
->high_bound
)
951 coefficients
[i
].offset
+= coefficients
[i
].coefficient
952 * ind_ptr
->low_bound
;
953 else if (ind_ptr
->high_bound
!= INT_MIN
)
955 coefficients
[i
].offset
= coefficients
[i
].coefficient
956 * ind_ptr
->high_bound
;
957 coefficients
[i
].coefficient
= coefficients
[i
].coefficient
966 /* Determine the COMPLEXITY and SEPARABILITY for COUNT subscripts of
967 inputs ICOEFFICIENTS and outputs OCOEFFICIENTS */
970 classify_dependence (icoefficients
, ocoefficients
, complexity
, separability
,
972 subscript icoefficients
[MAX_SUBSCRIPTS
];
973 subscript ocoefficients
[MAX_SUBSCRIPTS
];
974 enum complexity_type complexity
[MAX_SUBSCRIPTS
];
978 char *iiv_used
[MAX_SUBSCRIPTS
];
979 char *oiv_used
[MAX_SUBSCRIPTS
];
980 int ocoeff
[MAX_SUBSCRIPTS
];
981 int icoeff
[MAX_SUBSCRIPTS
];
984 memset (iiv_used
, 0, sizeof (tree
) * MAX_SUBSCRIPTS
);
985 memset (oiv_used
, 0, sizeof (tree
) * MAX_SUBSCRIPTS
);
986 memset (icoeff
, 0, sizeof (int) * MAX_SUBSCRIPTS
);
987 memset (ocoeff
, 0, sizeof (int) * MAX_SUBSCRIPTS
);
988 for (idx
= 1; idx
<= count
; idx
++)
990 if (icoefficients
[idx
].variable
!= 0)
994 iiv_used
[idx
] = icoefficients
[idx
].variable
;
995 icoeff
[idx
] = icoefficients
[idx
].coefficient
;
998 if (ocoefficients
[idx
].variable
!= 0)
1000 if (! oiv_used
[idx
])
1002 oiv_used
[idx
] = ocoefficients
[idx
].variable
;
1003 ocoeff
[idx
] = ocoefficients
[idx
].coefficient
;
1008 for (idx
= 1; idx
<= count
; idx
++)
1010 if (iiv_used
[idx
] == 0 && oiv_used
[idx
] == 0)
1011 complexity
[idx
] = ziv
;
1012 else if (iiv_used
[idx
] == oiv_used
[idx
])
1014 if (icoeff
[idx
] == ocoeff
[idx
])
1015 complexity
[idx
] = strong_siv
;
1016 else if (icoeff
[idx
] == -1 * ocoeff
[idx
])
1017 complexity
[idx
] = weak_crossing_siv
;
1019 complexity
[idx
] = weak_siv
;
1021 else if (icoeff
[idx
] == 0 || ocoeff
[idx
] == 0)
1022 complexity
[idx
] = weak_zero_siv
;
1023 else complexity
[idx
] = miv
;
1027 for (idx
= 1; idx
<= count
; idx
++)
1029 for (cidx
= 1; cidx
<= count
; cidx
++)
1032 && iiv_used
[idx
] && oiv_used
[cidx
]
1033 && iiv_used
[idx
] == oiv_used
[cidx
])
1039 /* Determine the DIRECTION and DISTANCE dependency for subscript SUB of
1040 inputs ICOEFFICIENTS and outputs OCOEFFICIENTS of loop LOOP_PTR using
1041 the zero induction variable test */
1044 ziv_test (icoefficients
, ocoefficients
, direction
, distance
, loop_ptr
, sub
)
1045 subscript icoefficients
[MAX_SUBSCRIPTS
];
1046 subscript ocoefficients
[MAX_SUBSCRIPTS
];
1047 enum direction_type direction
[MAX_SUBSCRIPTS
][MAX_SUBSCRIPTS
];
1048 int distance
[MAX_SUBSCRIPTS
][MAX_SUBSCRIPTS
];
1054 if (ocoefficients
[sub
].offset
!=
1055 icoefficients
[sub
].offset
)
1056 direction
[loop_ptr
->depth
][idx
] = independent
;
1059 /* Determine the DIRECTION and DISTANCE dependency for subscript SUB of
1060 inputs ICOEFFICIENTS and outputs OCOEFFICIENTS of loop LOOP_PTR using
1061 the single induction variable test */
1064 siv_test (icoefficients
, ocoefficients
, direction
, distance
, loop_ptr
, sub
)
1065 subscript icoefficients
[MAX_SUBSCRIPTS
];
1066 subscript ocoefficients
[MAX_SUBSCRIPTS
];
1067 enum direction_type direction
[MAX_SUBSCRIPTS
][MAX_SUBSCRIPTS
];
1068 int distance
[MAX_SUBSCRIPTS
][MAX_SUBSCRIPTS
];
1076 if (! check_subscript_induction (&icoefficients
[sub
], &ocoefficients
[sub
],
1080 coef_diff
= icoefficients
[sub
].offset
- ocoefficients
[sub
].offset
;
1081 /* strong_siv requires equal coefficients. weak_crossing_siv requires
1082 coefficients to have equal absolute value. weak_zero_siv uses the
1083 nonzero coefficient. */
1085 if (ocoefficients
[sub
].coefficient
== INT_MIN
)
1086 coef
= icoefficients
[sub
].coefficient
;
1087 else if (icoefficients
[sub
].coefficient
== INT_MIN
)
1088 coef
= ocoefficients
[sub
].coefficient
;
1089 else if (ocoefficients
[sub
].coefficient
==
1090 -1 * icoefficients
[sub
].coefficient
)
1091 coef
= 2 * abs (ocoefficients
[sub
].coefficient
);
1093 coef
= icoefficients
[sub
].coefficient
;
1095 gcd
= -coef_diff
/ coef
;
1096 if (gcd
* coef
!= -coef_diff
)
1098 direction
[loop_ptr
->depth
][sub
] = independent
;
1102 distance
[loop_ptr
->depth
][sub
] = gcd
;
1104 direction
[loop_ptr
->depth
][sub
] = gt
;
1106 direction
[loop_ptr
->depth
][sub
] = lt
;
1108 direction
[loop_ptr
->depth
][sub
] = eq
;
1112 /* Return 1 if an induction variable of LOOP_PTR is used by either
1113 input ICOEFFICIENT or output OCOEFFICIENT */
1116 check_subscript_induction (icoefficient
, ocoefficient
, loop_ptr
)
1117 subscript
*icoefficient
;
1118 subscript
*ocoefficient
;
1122 int sub_ind_input
= 0;
1123 int sub_ind_output
= 0;
1125 for (ind_ptr
= loop_ptr
->ind
; ind_ptr
; ind_ptr
= ind_ptr
->next
)
1127 if (icoefficient
->variable
== ind_ptr
->variable
)
1129 if (ocoefficient
->variable
== ind_ptr
->variable
)
1132 if (sub_ind_input
|| sub_ind_output
)
1138 #define abs(n) (n < 0 ? -n : n)
1140 /* Determine the DIRECTION and DISTANCE dependency for subscript SUB of
1141 inputs ICOEFFICIENTS and outputs OCOEFFICIENTS of loop LOOP_PTR using
1142 the greatest common denominator test */
1145 gcd_test (icoefficients
, ocoefficients
, direction
, distance
, loop_ptr
, sub
)
1146 subscript icoefficients
[MAX_SUBSCRIPTS
];
1147 subscript ocoefficients
[MAX_SUBSCRIPTS
];
1148 enum direction_type direction
[MAX_SUBSCRIPTS
][MAX_SUBSCRIPTS
];
1149 int distance
[MAX_SUBSCRIPTS
][MAX_SUBSCRIPTS
];
1156 if (! check_subscript_induction (&icoefficients
[sub
], &ocoefficients
[sub
],
1160 g
= find_gcd (icoefficients
[sub
].coefficient
,
1161 ocoefficients
[sub
].coefficient
);
1164 coef_diff
= icoefficients
[sub
].offset
- ocoefficients
[sub
].offset
;
1166 if (gg
* g
!= coef_diff
)
1168 direction
[loop_ptr
->depth
][sub
] = independent
;
1171 /* ?? gcd does not yield direction and distance. Wolfe's direction
1172 vector hierarchy can be used to give this. */
1175 /* Find the gcd of X and Y using Euclid's algorithm */
1207 /* Merge SUBSCRIPT_COUNT DIRECTIONs and DISTANCEs for LOOP_COUNT loops.
1208 We use a predefined array to handle the direction merge.
1209 The distance merge makes use of the fact that distances default to
1210 INT_MAX. Distances are '&' together. Watch out for a negative distance.
1214 merge_dependencies (direction
, distance
, loop_count
, subscript_count
)
1215 enum direction_type direction
[MAX_SUBSCRIPTS
][MAX_SUBSCRIPTS
];
1216 int distance
[MAX_SUBSCRIPTS
][MAX_SUBSCRIPTS
];
1218 int subscript_count
;
1223 enum direction_type direction_merge
[8][8] =
1224 {{lt
, le
, le
, star
, star
, lt
, independent
, lt
},
1225 {le
, le
, le
, star
, star
, le
, independent
, le
},
1226 {le
, le
, eq
, ge
, ge
, eq
, independent
, eq
},
1227 {star
, star
, ge
, gt
, ge
, gt
, independent
, ge
},
1228 {star
, star
, ge
, ge
, ge
, ge
, independent
, ge
},
1229 {lt
, le
, eq
, gt
, ge
, star
, independent
, star
},
1230 {independent
, independent
, independent
, independent
, independent
},
1231 {independent
, independent
, independent
}
1234 for (i
= 1; i
<= loop_count
; i
++)
1236 distance
[i
][0] = INT_MAX
;
1237 direction
[i
][0] = star
;
1239 for (j
= 1; j
<= subscript_count
; j
++)
1241 if (distance
[i
][j
] < 0)
1243 distance
[i
][0] = distance
[i
][0] & abs (distance
[i
][j
]);
1247 distance
[i
][0] = distance
[i
][0] & distance
[i
][j
];
1248 direction
[i
][0] = direction_merge
[(int)direction
[i
][0]]
1249 [(int)direction
[i
][j
]];
1251 distance
[i
][0] = sign
* distance
[i
][0];
1255 /* Dump ARRAY_REF NODE. */
1258 dump_array_ref (node
)
1261 enum tree_code tree_op
= TREE_CODE (node
);
1263 if (tree_op
== VAR_DECL
)
1265 printf ("%s", IDENTIFIER_POINTER (DECL_NAME (node
)));
1267 else if (tree_op
== INTEGER_CST
)
1269 printf ("%d", (int)TREE_INT_CST_LOW (node
));
1271 else if (tree_op
== PLUS_EXPR
)
1273 dump_array_ref (TREE_OPERAND (node
, 0));
1275 dump_array_ref (TREE_OPERAND (node
, 1));
1277 else if (tree_op
== MINUS_EXPR
)
1279 dump_array_ref (TREE_OPERAND (node
, 0));
1281 dump_array_ref (TREE_OPERAND (node
, 1));
1283 else if (tree_op
== MULT_EXPR
)
1285 dump_array_ref (TREE_OPERAND (node
, 0));
1287 dump_array_ref (TREE_OPERAND (node
, 1));
1291 /* Dump def/use DU. */
1294 dump_one_node (du
, seen
)
1299 dependence
*dep_ptr
;
1302 for (du_ptr
= du
; du_ptr
; du_ptr
= du_ptr
->next
)
1304 printf ("%s ", du_ptr
->variable
);
1305 for (array_ref
= du_ptr
->expression
;
1306 TREE_CODE (array_ref
) == ARRAY_REF
;
1307 array_ref
= TREE_OPERAND (array_ref
, 0))
1310 dump_array_ref (TREE_OPERAND (array_ref
, 1));
1314 printf (" Outer Loop %x Containing Loop %x Expression %x %s\n",
1315 (int)du_ptr
->outer_loop
,
1316 (int)du_ptr
->containing_loop
,
1317 (int)du_ptr
->expression
, du_ptr
->type
== def
? "Def" : "Use");
1318 VARRAY_PUSH_GENERIC_PTR (*seen
, du_ptr
);
1320 for (dep_ptr
= du_ptr
->dep
; dep_ptr
; dep_ptr
= dep_ptr
->next
)
1323 printf ("%s Dependence with %x ",
1324 dependence_string
[(int)dep_ptr
->dependence
],
1325 (int)dep_ptr
->source
);
1326 printf ("Dir/Dist ");
1327 for (i
= 1 ; i
< MAX_SUBSCRIPTS
; i
++)
1328 if (dep_ptr
->direction
[i
] != undef
)
1329 printf ("[%d] %s/%d ", i
,
1330 direction_string
[(int)dep_ptr
->direction
[i
]],
1331 dep_ptr
->distance
[i
]);
1337 /* Dump dependence info. */
1340 dump_node_dependence (void)
1343 unsigned int du_idx
, seen_idx
, i
;
1346 VARRAY_GENERIC_PTR_INIT (seen
, 20, "seen");
1349 for (du_ptr
= VARRAY_GENERIC_PTR (def_use_chain
, du_idx
);
1350 du_idx
< VARRAY_SIZE (def_use_chain
);
1351 du_ptr
= VARRAY_GENERIC_PTR (def_use_chain
, du_idx
++))
1353 for (i
= 0; i
< VARRAY_SIZE (seen
) && VARRAY_GENERIC_PTR (seen
, i
)
1355 if (i
>= VARRAY_SIZE (seen
))
1356 dump_one_node (du_ptr
, &seen
);
1361 /* Return the index into 'dep_chain' if there is a dependency for destination
1362 dest_to_remember (set by remember_dest_for_dependence) and source node.
1363 Called by the front end, which adds the index onto a MEM rtx. */
1366 search_dependence (node
)
1369 dependence
*dep_ptr
;
1375 if (TREE_CODE (node
) == INDIRECT_REF
&& TREE_OPERAND (node
, 1)
1376 && TREE_CODE (TREE_OPERAND (node
, 1)) == ARRAY_REF
)
1377 node
= TREE_OPERAND (node
, 1);
1379 for (dep_ptr
= VARRAY_GENERIC_PTR (dep_chain
, 0);
1380 dep_ptr
; dep_ptr
= VARRAY_GENERIC_PTR (dep_chain
, dep_idx
++))
1382 if ((node
== dep_ptr
->source
1383 && dest_to_remember
== dep_ptr
->destination
)
1384 || (! dep_ptr
->source
&& node
== dep_ptr
->destination
))
1392 /* Remember a destination NODE for search_dependence. */
1395 remember_dest_for_dependence (node
)
1400 if (TREE_CODE (node
) == INDIRECT_REF
&& TREE_OPERAND (node
, 1)
1401 && TREE_CODE (TREE_OPERAND (node
, 1)) == ARRAY_REF
)
1402 node
= TREE_OPERAND (node
, 1);
1403 dest_to_remember
= node
;
1407 #ifndef MEM_DEPENDENCY
1408 #define MEM_DEPENDENCY(RTX) XCWINT(RTX, 2, MEM)
1411 /* Return 1 along with the dependence DIRECTION and DISTANCE if there is a
1412 dependence from dest_rtx to src_rtx. */
1415 have_dependence_p (dest_rtx
, src_rtx
, direction
, distance
)
1418 enum direction_type direction
[MAX_SUBSCRIPTS
];
1419 int distance
[MAX_SUBSCRIPTS
];
1421 int dest_idx
, src_idx
;
1423 dependence
*dep_ptr
;
1425 if (GET_CODE (SET_DEST (PATTERN (dest_rtx
))) == MEM
)
1427 dest
= SET_DEST (PATTERN (dest_rtx
));
1428 dest_idx
= MEM_DEPENDENCY (dest
) - 1;
1430 if (GET_CODE (SET_SRC (PATTERN (src_rtx
))) == MEM
)
1432 src
= SET_SRC (PATTERN (src_rtx
));
1433 src_idx
= MEM_DEPENDENCY (dest
) - 1;
1435 if (dest_idx
>= 0 || src_idx
>= 0)
1438 for (dep_ptr
= VARRAY_GENERIC_PTR (dep_chain
, -dest_idx
);
1439 dep_ptr
; dep_ptr
= dep_ptr
->next
)
1441 if (dep_ptr
== VARRAY_GENERIC_PTR (dep_chain
, -src_idx
))
1443 direction
= (enum direction_type
*) &dep_ptr
->direction
;
1444 distance
= (int*) &dep_ptr
->distance
;
1451 /* Cleanup when dependency analysis is complete. */
1454 end_dependence_analysis (void)
1456 VARRAY_FREE (dep_chain
);