1 /* Header file for the value range relational processing.
2 Copyright (C) 2020-2022 Free Software Foundation, Inc.
3 Contributed by Andrew MacLeod <amacleod@redhat.com>
5 This file is part of GCC.
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
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
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/>. */
23 #include "coretypes.h"
29 #include "gimple-range.h"
30 #include "tree-pretty-print.h"
31 #include "gimple-pretty-print.h"
32 #include "alloc-pool.h"
33 #include "dominance.h"
35 #define VREL_LAST VREL_NE
37 static const char *kind_string
[VREL_LAST
+ 1] =
38 { "varying", "undefined", "<", "<=", ">", ">=", "==", "!=" };
40 // Print a relation_kind REL to file F.
43 print_relation (FILE *f
, relation_kind rel
)
45 fprintf (f
, " %s ", kind_string
[rel
]);
48 // This table is used to negate the operands. op1 REL op2 -> !(op1 REL op2).
49 relation_kind rr_negate_table
[VREL_LAST
+ 1] = {
50 VREL_VARYING
, VREL_UNDEFINED
, VREL_GE
, VREL_GT
, VREL_LE
, VREL_LT
, VREL_NE
,
53 // Negate the relation, as in logical negation.
56 relation_negate (relation_kind r
)
58 return rr_negate_table
[r
];
61 // This table is used to swap the operands. op1 REL op2 -> op2 REL op1.
62 relation_kind rr_swap_table
[VREL_LAST
+ 1] = {
63 VREL_VARYING
, VREL_UNDEFINED
, VREL_GT
, VREL_GE
, VREL_LT
, VREL_LE
, VREL_EQ
,
66 // Return the relation as if the operands were swapped.
69 relation_swap (relation_kind r
)
71 return rr_swap_table
[r
];
74 // This table is used to perform an intersection between 2 relations.
76 relation_kind rr_intersect_table
[VREL_LAST
+ 1][VREL_LAST
+ 1] = {
78 { VREL_VARYING
, VREL_UNDEFINED
, VREL_LT
, VREL_LE
, VREL_GT
, VREL_GE
, VREL_EQ
,
81 { VREL_UNDEFINED
, VREL_UNDEFINED
, VREL_UNDEFINED
, VREL_UNDEFINED
,
82 VREL_UNDEFINED
, VREL_UNDEFINED
, VREL_UNDEFINED
, VREL_UNDEFINED
},
84 { VREL_LT
, VREL_UNDEFINED
, VREL_LT
, VREL_LT
, VREL_UNDEFINED
, VREL_UNDEFINED
,
85 VREL_UNDEFINED
, VREL_LT
},
87 { VREL_LE
, VREL_UNDEFINED
, VREL_LT
, VREL_LE
, VREL_UNDEFINED
, VREL_EQ
,
90 { VREL_GT
, VREL_UNDEFINED
, VREL_UNDEFINED
, VREL_UNDEFINED
, VREL_GT
, VREL_GT
,
91 VREL_UNDEFINED
, VREL_GT
},
93 { VREL_GE
, VREL_UNDEFINED
, VREL_UNDEFINED
, VREL_EQ
, VREL_GT
, VREL_GE
,
96 { VREL_EQ
, VREL_UNDEFINED
, VREL_UNDEFINED
, VREL_EQ
, VREL_UNDEFINED
, VREL_EQ
,
97 VREL_EQ
, VREL_UNDEFINED
},
99 { VREL_NE
, VREL_UNDEFINED
, VREL_LT
, VREL_LT
, VREL_GT
, VREL_GT
,
100 VREL_UNDEFINED
, VREL_NE
} };
103 // Intersect relation R1 with relation R2 and return the resulting relation.
106 relation_intersect (relation_kind r1
, relation_kind r2
)
108 return rr_intersect_table
[r1
][r2
];
112 // This table is used to perform a union between 2 relations.
114 relation_kind rr_union_table
[VREL_LAST
+ 1][VREL_LAST
+ 1] = {
116 { VREL_VARYING
, VREL_VARYING
, VREL_VARYING
, VREL_VARYING
, VREL_VARYING
,
117 VREL_VARYING
, VREL_VARYING
, VREL_VARYING
},
119 { VREL_VARYING
, VREL_LT
, VREL_LE
, VREL_GT
, VREL_GE
, VREL_UNDEFINED
,
122 { VREL_VARYING
, VREL_LT
, VREL_LT
, VREL_LE
, VREL_NE
, VREL_VARYING
, VREL_LE
,
125 { VREL_VARYING
, VREL_LE
, VREL_LE
, VREL_LE
, VREL_VARYING
, VREL_VARYING
,
126 VREL_LE
, VREL_VARYING
},
128 { VREL_VARYING
, VREL_GT
, VREL_NE
, VREL_VARYING
, VREL_GT
, VREL_GE
, VREL_GE
,
131 { VREL_VARYING
, VREL_GE
, VREL_VARYING
, VREL_VARYING
, VREL_GE
, VREL_GE
,
132 VREL_GE
, VREL_VARYING
},
134 { VREL_VARYING
, VREL_EQ
, VREL_LE
, VREL_LE
, VREL_GE
, VREL_GE
, VREL_EQ
,
137 { VREL_VARYING
, VREL_NE
, VREL_NE
, VREL_VARYING
, VREL_NE
, VREL_VARYING
,
138 VREL_VARYING
, VREL_NE
} };
140 // Union relation R1 with relation R2 and return the result.
143 relation_union (relation_kind r1
, relation_kind r2
)
145 return rr_union_table
[r1
][r2
];
149 // This table is used to determine transitivity between 2 relations.
150 // (A relation0 B) and (B relation1 C) implies (A result C)
152 relation_kind rr_transitive_table
[VREL_LAST
+ 1][VREL_LAST
+ 1] = {
154 { VREL_VARYING
, VREL_VARYING
, VREL_VARYING
, VREL_VARYING
, VREL_VARYING
,
155 VREL_VARYING
, VREL_VARYING
, VREL_VARYING
},
157 { VREL_VARYING
, VREL_VARYING
, VREL_VARYING
, VREL_VARYING
, VREL_VARYING
,
158 VREL_VARYING
, VREL_VARYING
, VREL_VARYING
},
160 { VREL_VARYING
, VREL_VARYING
, VREL_LT
, VREL_LT
, VREL_VARYING
, VREL_VARYING
,
161 VREL_LT
, VREL_VARYING
},
163 { VREL_VARYING
, VREL_VARYING
, VREL_LT
, VREL_LE
, VREL_VARYING
, VREL_VARYING
,
164 VREL_LE
, VREL_VARYING
},
166 { VREL_VARYING
, VREL_VARYING
, VREL_VARYING
, VREL_VARYING
, VREL_GT
, VREL_GT
,
167 VREL_GT
, VREL_VARYING
},
169 { VREL_VARYING
, VREL_VARYING
, VREL_VARYING
, VREL_VARYING
, VREL_GT
, VREL_GE
,
170 VREL_GE
, VREL_VARYING
},
172 { VREL_VARYING
, VREL_VARYING
, VREL_LT
, VREL_LE
, VREL_GT
, VREL_GE
, VREL_EQ
,
175 { VREL_VARYING
, VREL_VARYING
, VREL_VARYING
, VREL_VARYING
, VREL_VARYING
,
176 VREL_VARYING
, VREL_VARYING
, VREL_VARYING
} };
178 // Apply transitive operation between relation R1 and relation R2, and
179 // return the resulting relation, if any.
182 relation_transitive (relation_kind r1
, relation_kind r2
)
184 return rr_transitive_table
[r1
][r2
];
187 // This vector maps a relation to the equivalent tree code.
189 tree_code relation_to_code
[VREL_LAST
+ 1] = {
190 ERROR_MARK
, ERROR_MARK
, LT_EXPR
, LE_EXPR
, GT_EXPR
, GE_EXPR
, EQ_EXPR
,
193 // This routine validates that a relation can be applied to a specific set of
194 // ranges. In particular, floating point x == x may not be true if the NaN bit
195 // is set in the range. Symbolically the oracle will determine x == x,
196 // but specific range instances may override this.
197 // To verify, attempt to fold the relation using the supplied ranges.
198 // One would expect [1,1] to be returned, anything else means there is something
199 // in the range preventing the relation from applying.
200 // If there is no mechanism to verify, assume the relation is acceptable.
203 relation_oracle::validate_relation (relation_kind rel
, vrange
&op1
, vrange
&op2
)
205 // If there is no mapping to a tree code, leave the relation as is.
206 tree_code code
= relation_to_code
[rel
];
207 if (code
== ERROR_MARK
)
210 // Undefined ranges cannot be checked either.
211 if (op1
.undefined_p () || op2
.undefined_p ())
214 tree t1
= op1
.type ();
215 tree t2
= op2
.type ();
217 // If the range types are not compatible, no relation can exist.
218 if (!range_compatible_p (t1
, t2
))
221 // If there is no handler, leave the relation as is.
222 range_op_handler
handler (code
, t1
);
226 // If the relation cannot be folded for any reason, leave as is.
227 Value_Range
result (boolean_type_node
);
228 if (!handler
.fold_range (result
, boolean_type_node
, op1
, op2
, rel
))
231 // The expression op1 REL op2 using REL should fold to [1,1].
232 // Any other result means the relation is not verified to be true.
233 if (result
.varying_p () || result
.zero_p ())
239 // If no range is available, create a varying range for each SSA name and
243 relation_oracle::validate_relation (relation_kind rel
, tree ssa1
, tree ssa2
)
245 Value_Range op1
, op2
;
246 op1
.set_varying (TREE_TYPE (ssa1
));
247 op2
.set_varying (TREE_TYPE (ssa2
));
249 return validate_relation (rel
, op1
, op2
);
252 // Given an equivalence set EQUIV, set all the bits in B that are still valid
253 // members of EQUIV in basic block BB.
256 relation_oracle::valid_equivs (bitmap b
, const_bitmap equivs
, basic_block bb
)
260 EXECUTE_IF_SET_IN_BITMAP (equivs
, 0, i
, bi
)
262 tree ssa
= ssa_name (i
);
263 const_bitmap ssa_equiv
= equiv_set (ssa
, bb
);
264 if (ssa_equiv
== equivs
)
265 bitmap_set_bit (b
, i
);
269 // -------------------------------------------------------------------------
271 // The very first element in the m_equiv chain is actually just a summary
272 // element in which the m_names bitmap is used to indicate that an ssa_name
273 // has an equivalence set in this block.
274 // This allows for much faster traversal of the DOM chain, as a search for
275 // SSA_NAME simply requires walking the DOM chain until a block is found
276 // which has the bit for SSA_NAME set. Then scan for the equivalency set in
277 // that block. No previous lists need be searched.
279 // If SSA has an equivalence in this list, find and return it.
280 // Otherwise return NULL.
283 equiv_chain::find (unsigned ssa
)
285 equiv_chain
*ptr
= NULL
;
286 // If there are equiv sets and SSA is in one in this list, find it.
287 // Otherwise return NULL.
288 if (bitmap_bit_p (m_names
, ssa
))
290 for (ptr
= m_next
; ptr
; ptr
= ptr
->m_next
)
291 if (bitmap_bit_p (ptr
->m_names
, ssa
))
297 // Dump the names in this equivalence set.
300 equiv_chain::dump (FILE *f
) const
307 fprintf (f
, "Equivalence set : [");
309 EXECUTE_IF_SET_IN_BITMAP (m_names
, 0, i
, bi
)
315 print_generic_expr (f
, ssa_name (i
), TDF_SLIM
);
321 // Instantiate an equivalency oracle.
323 equiv_oracle::equiv_oracle ()
325 bitmap_obstack_initialize (&m_bitmaps
);
327 m_equiv
.safe_grow_cleared (last_basic_block_for_fn (cfun
) + 1);
328 m_equiv_set
= BITMAP_ALLOC (&m_bitmaps
);
329 obstack_init (&m_chain_obstack
);
330 m_self_equiv
.create (0);
331 m_self_equiv
.safe_grow_cleared (num_ssa_names
+ 1);
334 // Destruct an equivalency oracle.
336 equiv_oracle::~equiv_oracle ()
338 m_self_equiv
.release ();
339 obstack_free (&m_chain_obstack
, NULL
);
341 bitmap_obstack_release (&m_bitmaps
);
344 // Find and return the equivalency set for SSA along the dominators of BB.
345 // This is the external API.
348 equiv_oracle::equiv_set (tree ssa
, basic_block bb
)
350 // Search the dominator tree for an equivalency.
351 equiv_chain
*equiv
= find_equiv_dom (ssa
, bb
);
353 return equiv
->m_names
;
355 // Otherwise return a cached equiv set containing just this SSA.
356 unsigned v
= SSA_NAME_VERSION (ssa
);
357 if (v
>= m_self_equiv
.length ())
358 m_self_equiv
.safe_grow_cleared (num_ssa_names
+ 1);
360 if (!m_self_equiv
[v
])
362 m_self_equiv
[v
] = BITMAP_ALLOC (&m_bitmaps
);
363 bitmap_set_bit (m_self_equiv
[v
], v
);
365 return m_self_equiv
[v
];
368 // Query if thre is a relation (equivalence) between 2 SSA_NAMEs.
371 equiv_oracle::query_relation (basic_block bb
, tree ssa1
, tree ssa2
)
373 // If the 2 ssa names share the same equiv set, they are equal.
374 if (equiv_set (ssa1
, bb
) == equiv_set (ssa2
, bb
))
379 // Query if thre is a relation (equivalence) between 2 SSA_NAMEs.
382 equiv_oracle::query_relation (basic_block bb ATTRIBUTE_UNUSED
, const_bitmap e1
,
385 // If the 2 ssa names share the same equiv set, they are equal.
386 if (bitmap_equal_p (e1
, e2
))
391 // If SSA has an equivalence in block BB, find and return it.
392 // Otherwise return NULL.
395 equiv_oracle::find_equiv_block (unsigned ssa
, int bb
) const
397 if (bb
>= (int)m_equiv
.length () || !m_equiv
[bb
])
400 return m_equiv
[bb
]->find (ssa
);
403 // Starting at block BB, walk the dominator chain looking for the nearest
404 // equivalence set containing NAME.
407 equiv_oracle::find_equiv_dom (tree name
, basic_block bb
) const
409 unsigned v
= SSA_NAME_VERSION (name
);
410 // Short circuit looking for names which have no equivalences.
411 // Saves time looking for something which does not exist.
412 if (!bitmap_bit_p (m_equiv_set
, v
))
415 // NAME has at least once equivalence set, check to see if it has one along
416 // the dominator tree.
417 for ( ; bb
; bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
419 equiv_chain
*ptr
= find_equiv_block (v
, bb
->index
);
426 // Register equivalance between ssa_name V and set EQUIV in block BB,
429 equiv_oracle::register_equiv (basic_block bb
, unsigned v
, equiv_chain
*equiv
)
431 // V will have an equivalency now.
432 bitmap_set_bit (m_equiv_set
, v
);
434 // If that equiv chain is in this block, simply use it.
435 if (equiv
->m_bb
== bb
)
437 bitmap_set_bit (equiv
->m_names
, v
);
438 bitmap_set_bit (m_equiv
[bb
->index
]->m_names
, v
);
442 // Otherwise create an equivalence for this block which is a copy
443 // of equiv, the add V to the set.
444 bitmap b
= BITMAP_ALLOC (&m_bitmaps
);
445 valid_equivs (b
, equiv
->m_names
, bb
);
446 bitmap_set_bit (b
, v
);
450 // Register equivalence between set equiv_1 and equiv_2 in block BB.
451 // Return NULL if either name can be merged with the other. Otherwise
452 // return a pointer to the combined bitmap of names. This allows the
453 // caller to do any setup required for a new element.
456 equiv_oracle::register_equiv (basic_block bb
, equiv_chain
*equiv_1
,
457 equiv_chain
*equiv_2
)
459 // If equiv_1 is already in BB, use it as the combined set.
460 if (equiv_1
->m_bb
== bb
)
462 valid_equivs (equiv_1
->m_names
, equiv_2
->m_names
, bb
);
463 // Its hard to delete from a single linked list, so
464 // just clear the second one.
465 if (equiv_2
->m_bb
== bb
)
466 bitmap_clear (equiv_2
->m_names
);
468 // Ensure the new names are in the summary for BB.
469 bitmap_ior_into (m_equiv
[bb
->index
]->m_names
, equiv_1
->m_names
);
472 // If equiv_2 is in BB, use it for the combined set.
473 if (equiv_2
->m_bb
== bb
)
475 valid_equivs (equiv_2
->m_names
, equiv_1
->m_names
, bb
);
476 // Ensure the new names are in the summary.
477 bitmap_ior_into (m_equiv
[bb
->index
]->m_names
, equiv_2
->m_names
);
481 // At this point, neither equivalence is from this block.
482 bitmap b
= BITMAP_ALLOC (&m_bitmaps
);
483 valid_equivs (b
, equiv_1
->m_names
, bb
);
484 valid_equivs (b
, equiv_2
->m_names
, bb
);
488 // Create an equivalency set containing only SSA in its definition block.
489 // This is done the first time SSA is registered in an equivalency and blocks
490 // any DOM searches past the definition.
493 equiv_oracle::register_initial_def (tree ssa
)
495 if (SSA_NAME_IS_DEFAULT_DEF (ssa
))
497 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (ssa
));
498 gcc_checking_assert (bb
&& !find_equiv_dom (ssa
, bb
));
500 unsigned v
= SSA_NAME_VERSION (ssa
);
501 bitmap_set_bit (m_equiv_set
, v
);
502 bitmap equiv_set
= BITMAP_ALLOC (&m_bitmaps
);
503 bitmap_set_bit (equiv_set
, v
);
504 add_equiv_to_block (bb
, equiv_set
);
507 // Register an equivalence between SSA1 and SSA2 in block BB.
508 // The equivalence oracle maintains a vector of equivalencies indexed by basic
509 // block. When an equivalence bteween SSA1 and SSA2 is registered in block BB,
510 // a query is made as to what equivalences both names have already, and
511 // any preexisting equivalences are merged to create a single equivalence
512 // containing all the ssa_names in this basic block.
515 equiv_oracle::register_relation (basic_block bb
, relation_kind k
, tree ssa1
,
518 // Only handle equality relations.
522 unsigned v1
= SSA_NAME_VERSION (ssa1
);
523 unsigned v2
= SSA_NAME_VERSION (ssa2
);
525 // If this is the first time an ssa_name has an equivalency registered
526 // create a self-equivalency record in the def block.
527 if (!bitmap_bit_p (m_equiv_set
, v1
))
528 register_initial_def (ssa1
);
529 if (!bitmap_bit_p (m_equiv_set
, v2
))
530 register_initial_def (ssa2
);
532 equiv_chain
*equiv_1
= find_equiv_dom (ssa1
, bb
);
533 equiv_chain
*equiv_2
= find_equiv_dom (ssa2
, bb
);
535 // Check if they are the same set
536 if (equiv_1
&& equiv_1
== equiv_2
)
541 // Case where we have 2 SSA_NAMEs that are not in any set.
542 if (!equiv_1
&& !equiv_2
)
544 bitmap_set_bit (m_equiv_set
, v1
);
545 bitmap_set_bit (m_equiv_set
, v2
);
547 equiv_set
= BITMAP_ALLOC (&m_bitmaps
);
548 bitmap_set_bit (equiv_set
, v1
);
549 bitmap_set_bit (equiv_set
, v2
);
551 else if (!equiv_1
&& equiv_2
)
552 equiv_set
= register_equiv (bb
, v1
, equiv_2
);
553 else if (equiv_1
&& !equiv_2
)
554 equiv_set
= register_equiv (bb
, v2
, equiv_1
);
556 equiv_set
= register_equiv (bb
, equiv_1
, equiv_2
);
558 // A non-null return is a bitmap that is to be added to the current
559 // block as a new equivalence.
563 add_equiv_to_block (bb
, equiv_set
);
566 // Add an equivalency record in block BB containing bitmap EQUIV_SET.
567 // Note the internal caller is responible for allocating EQUIV_SET properly.
570 equiv_oracle::add_equiv_to_block (basic_block bb
, bitmap equiv_set
)
574 // Check if this is the first time a block has an equivalence added.
575 // and create a header block. And set the summary for this block.
576 if (!m_equiv
[bb
->index
])
578 ptr
= (equiv_chain
*) obstack_alloc (&m_chain_obstack
,
579 sizeof (equiv_chain
));
580 ptr
->m_names
= BITMAP_ALLOC (&m_bitmaps
);
581 bitmap_copy (ptr
->m_names
, equiv_set
);
584 m_equiv
[bb
->index
] = ptr
;
587 // Now create the element for this equiv set and initialize it.
588 ptr
= (equiv_chain
*) obstack_alloc (&m_chain_obstack
, sizeof (equiv_chain
));
589 ptr
->m_names
= equiv_set
;
591 gcc_checking_assert (bb
->index
< (int)m_equiv
.length ());
592 ptr
->m_next
= m_equiv
[bb
->index
]->m_next
;
593 m_equiv
[bb
->index
]->m_next
= ptr
;
594 bitmap_ior_into (m_equiv
[bb
->index
]->m_names
, equiv_set
);
597 // Make sure the BB vector is big enough and grow it if needed.
600 equiv_oracle::limit_check (basic_block bb
)
602 int i
= (bb
) ? bb
->index
: last_basic_block_for_fn (cfun
);
603 if (i
>= (int)m_equiv
.length ())
604 m_equiv
.safe_grow_cleared (last_basic_block_for_fn (cfun
) + 1);
607 // Dump the equivalence sets in BB to file F.
610 equiv_oracle::dump (FILE *f
, basic_block bb
) const
612 if (bb
->index
>= (int)m_equiv
.length ())
614 if (!m_equiv
[bb
->index
])
617 equiv_chain
*ptr
= m_equiv
[bb
->index
]->m_next
;
618 for (; ptr
; ptr
= ptr
->m_next
)
622 // Dump all equivalence sets known to the oracle.
625 equiv_oracle::dump (FILE *f
) const
627 fprintf (f
, "Equivalency dump\n");
628 for (unsigned i
= 0; i
< m_equiv
.length (); i
++)
629 if (m_equiv
[i
] && BASIC_BLOCK_FOR_FN (cfun
, i
))
631 fprintf (f
, "BB%d\n", i
);
632 dump (f
, BASIC_BLOCK_FOR_FN (cfun
, i
));
637 // --------------------------------------------------------------------------
638 // Negate the current relation.
641 value_relation::negate ()
643 related
= relation_negate (related
);
646 // Perform an intersection between 2 relations. *this &&= p.
649 value_relation::intersect (value_relation
&p
)
651 // Save previous value
652 relation_kind old
= related
;
654 if (p
.op1 () == op1 () && p
.op2 () == op2 ())
655 related
= relation_intersect (kind (), p
.kind ());
656 else if (p
.op2 () == op1 () && p
.op1 () == op2 ())
657 related
= relation_intersect (kind (), relation_swap (p
.kind ()));
661 return old
!= related
;
664 // Perform a union between 2 relations. *this ||= p.
667 value_relation::union_ (value_relation
&p
)
669 // Save previous value
670 relation_kind old
= related
;
672 if (p
.op1 () == op1 () && p
.op2 () == op2 ())
673 related
= relation_union (kind(), p
.kind());
674 else if (p
.op2 () == op1 () && p
.op1 () == op2 ())
675 related
= relation_union (kind(), relation_swap (p
.kind ()));
679 return old
!= related
;
682 // Identify and apply any transitive relations between REL
683 // and THIS. Return true if there was a transformation.
686 value_relation::apply_transitive (const value_relation
&rel
)
688 relation_kind k
= VREL_VARYING
;
690 // Idenity any common operand, and notrmalize the relations to
691 // the form : A < B B < C produces A < C
692 if (rel
.op1 () == name2
)
695 if (rel
.op2 () == name1
)
697 k
= relation_transitive (kind (), rel
.kind ());
698 if (k
!= VREL_VARYING
)
705 else if (rel
.op1 () == name1
)
708 if (rel
.op2 () == name2
)
710 k
= relation_transitive (relation_swap (kind ()), rel
.kind ());
711 if (k
!= VREL_VARYING
)
719 else if (rel
.op2 () == name2
)
722 if (rel
.op1 () == name1
)
724 k
= relation_transitive (kind (), relation_swap (rel
.kind ()));
725 if (k
!= VREL_VARYING
)
732 else if (rel
.op2 () == name1
)
735 if (rel
.op1 () == name2
)
737 k
= relation_transitive (relation_swap (kind ()),
738 relation_swap (rel
.kind ()));
739 if (k
!= VREL_VARYING
)
750 // Dump the relation to file F.
753 value_relation::dump (FILE *f
) const
755 if (!name1
|| !name2
)
757 fprintf (f
, "uninitialized");
761 print_generic_expr (f
, op1 (), TDF_SLIM
);
762 print_relation (f
, kind ());
763 print_generic_expr (f
, op2 (), TDF_SLIM
);
767 // This container is used to link relations in a chain.
769 class relation_chain
: public value_relation
772 relation_chain
*m_next
;
775 // ------------------------------------------------------------------------
777 // Find the relation between any ssa_name in B1 and any name in B2 in LIST.
778 // This will allow equivalencies to be applied to any SSA_NAME in a relation.
781 relation_chain_head::find_relation (const_bitmap b1
, const_bitmap b2
) const
786 // If both b1 and b2 aren't referenced in thie block, cant be a relation
787 if (!bitmap_intersect_p (m_names
, b1
) || !bitmap_intersect_p (m_names
, b2
))
790 // Search for the fiorst relation that contains BOTH an element from B1
791 // and B2, and return that relation.
792 for (relation_chain
*ptr
= m_head
; ptr
; ptr
= ptr
->m_next
)
794 unsigned op1
= SSA_NAME_VERSION (ptr
->op1 ());
795 unsigned op2
= SSA_NAME_VERSION (ptr
->op2 ());
796 if (bitmap_bit_p (b1
, op1
) && bitmap_bit_p (b2
, op2
))
798 if (bitmap_bit_p (b1
, op2
) && bitmap_bit_p (b2
, op1
))
799 return relation_swap (ptr
->kind ());
805 // Instantiate a relation oracle.
807 dom_oracle::dom_oracle ()
809 m_relations
.create (0);
810 m_relations
.safe_grow_cleared (last_basic_block_for_fn (cfun
) + 1);
811 m_relation_set
= BITMAP_ALLOC (&m_bitmaps
);
812 m_tmp
= BITMAP_ALLOC (&m_bitmaps
);
813 m_tmp2
= BITMAP_ALLOC (&m_bitmaps
);
816 // Destruct a relation oracle.
818 dom_oracle::~dom_oracle ()
820 m_relations
.release ();
823 // Register relation K between ssa_name OP1 and OP2 on STMT.
826 relation_oracle::register_stmt (gimple
*stmt
, relation_kind k
, tree op1
,
829 gcc_checking_assert (TREE_CODE (op1
) == SSA_NAME
);
830 gcc_checking_assert (TREE_CODE (op2
) == SSA_NAME
);
831 gcc_checking_assert (stmt
&& gimple_bb (stmt
));
833 // Don't register lack of a relation.
834 if (k
== VREL_VARYING
)
837 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
839 value_relation
vr (k
, op1
, op2
);
840 fprintf (dump_file
, " Registering value_relation ");
842 fprintf (dump_file
, " (bb%d) at ", gimple_bb (stmt
)->index
);
843 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
846 // If an equivalence is being added between a PHI and one of its arguments
847 // make sure that that argument is not defined in the same block.
848 // This can happen along back edges and the equivalence will not be
849 // applicable as it would require a use before def.
850 if (k
== VREL_EQ
&& is_a
<gphi
*> (stmt
))
852 tree phi_def
= gimple_phi_result (stmt
);
853 gcc_checking_assert (phi_def
== op1
|| phi_def
== op2
);
857 if (gimple_bb (stmt
) == gimple_bb (SSA_NAME_DEF_STMT (arg
)))
859 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
861 fprintf (dump_file
, " Not registered due to ");
862 print_generic_expr (dump_file
, arg
, TDF_SLIM
);
863 fprintf (dump_file
, " being defined in the same block.\n");
868 register_relation (gimple_bb (stmt
), k
, op1
, op2
);
871 // Register relation K between ssa_name OP1 and OP2 on edge E.
874 relation_oracle::register_edge (edge e
, relation_kind k
, tree op1
, tree op2
)
876 gcc_checking_assert (TREE_CODE (op1
) == SSA_NAME
);
877 gcc_checking_assert (TREE_CODE (op2
) == SSA_NAME
);
879 // Do not register lack of relation, or blocks which have more than
880 // edge E for a predecessor.
881 if (k
== VREL_VARYING
|| !single_pred_p (e
->dest
))
884 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
886 value_relation
vr (k
, op1
, op2
);
887 fprintf (dump_file
, " Registering value_relation ");
889 fprintf (dump_file
, " on (%d->%d)\n", e
->src
->index
, e
->dest
->index
);
892 register_relation (e
->dest
, k
, op1
, op2
);
895 // Register relation K between OP! and OP2 in block BB.
896 // This creates the record and searches for existing records in the dominator
897 // tree to merge with.
900 dom_oracle::register_relation (basic_block bb
, relation_kind k
, tree op1
,
903 // If the 2 ssa_names are the same, do nothing. An equivalence is implied,
904 // and no other relation makes sense.
908 // Equivalencies are handled by the equivalence oracle.
910 equiv_oracle::register_relation (bb
, k
, op1
, op2
);
913 // if neither op1 nor op2 are in a relation before this is registered,
914 // there will be no transitive.
915 bool check
= bitmap_bit_p (m_relation_set
, SSA_NAME_VERSION (op1
))
916 || bitmap_bit_p (m_relation_set
, SSA_NAME_VERSION (op2
));
917 relation_chain
*ptr
= set_one_relation (bb
, k
, op1
, op2
);
919 register_transitives (bb
, *ptr
);
923 // Register relation K between OP! and OP2 in block BB.
924 // This creates the record and searches for existing records in the dominator
925 // tree to merge with. Return the record, or NULL if no record was created.
928 dom_oracle::set_one_relation (basic_block bb
, relation_kind k
, tree op1
,
931 gcc_checking_assert (k
!= VREL_VARYING
&& k
!= VREL_EQ
);
933 value_relation
vr(k
, op1
, op2
);
936 if (bbi
>= (int)m_relations
.length())
937 m_relations
.safe_grow_cleared (last_basic_block_for_fn (cfun
) + 1);
939 // Summary bitmap indicating what ssa_names have relations in this BB.
940 bitmap bm
= m_relations
[bbi
].m_names
;
942 bm
= m_relations
[bbi
].m_names
= BITMAP_ALLOC (&m_bitmaps
);
943 unsigned v1
= SSA_NAME_VERSION (op1
);
944 unsigned v2
= SSA_NAME_VERSION (op2
);
948 curr
= find_relation_block (bbi
, v1
, v2
, &ptr
);
949 // There is an existing relation in this block, just intersect with it.
950 if (curr
!= VREL_VARYING
)
952 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
954 fprintf (dump_file
, " Intersecting with existing ");
955 ptr
->dump (dump_file
);
957 // Check into whether we can simply replace the relation rather than
958 // intersecting it. This may help with some optimistic iterative
959 // updating algorithms.
960 bool new_rel
= ptr
->intersect (vr
);
961 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
963 fprintf (dump_file
, " to produce ");
964 ptr
->dump (dump_file
);
965 fprintf (dump_file
, " %s.\n", new_rel
? "Updated" : "No Change");
967 // If there was no change, return no record..
973 if (m_relations
[bbi
].m_num_relations
>= param_relation_block_limit
)
975 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
976 fprintf (dump_file
, " Not registered due to bb being full\n");
979 m_relations
[bbi
].m_num_relations
++;
980 // Check for an existing relation further up the DOM chain.
981 // By including dominating relations, The first one found in any search
982 // will be the aggregate of all the previous ones.
983 curr
= find_relation_dom (bb
, v1
, v2
);
984 if (curr
!= VREL_VARYING
)
985 k
= relation_intersect (curr
, k
);
987 bitmap_set_bit (bm
, v1
);
988 bitmap_set_bit (bm
, v2
);
989 bitmap_set_bit (m_relation_set
, v1
);
990 bitmap_set_bit (m_relation_set
, v2
);
992 ptr
= (relation_chain
*) obstack_alloc (&m_chain_obstack
,
993 sizeof (relation_chain
));
994 ptr
->set_relation (k
, op1
, op2
);
995 ptr
->m_next
= m_relations
[bbi
].m_head
;
996 m_relations
[bbi
].m_head
= ptr
;
1001 // Starting at ROOT_BB search the DOM tree looking for relations which
1002 // may produce transitive relations to RELATION. EQUIV1 and EQUIV2 are
1003 // bitmaps for op1/op2 and any of their equivalences that should also be
1007 dom_oracle::register_transitives (basic_block root_bb
,
1008 const value_relation
&relation
)
1011 // Only apply transitives to certain kinds of operations.
1012 switch (relation
.kind ())
1023 const_bitmap equiv1
= equiv_set (relation
.op1 (), root_bb
);
1024 const_bitmap equiv2
= equiv_set (relation
.op2 (), root_bb
);
1026 for (bb
= root_bb
; bb
; bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
1028 int bbi
= bb
->index
;
1029 if (bbi
>= (int)m_relations
.length())
1031 const_bitmap bm
= m_relations
[bbi
].m_names
;
1034 if (!bitmap_intersect_p (bm
, equiv1
) && !bitmap_intersect_p (bm
, equiv2
))
1036 // At least one of the 2 ops has a relation in this block.
1037 relation_chain
*ptr
;
1038 for (ptr
= m_relations
[bbi
].m_head
; ptr
; ptr
= ptr
->m_next
)
1040 // In the presence of an equivalence, 2 operands may do not
1041 // naturally match. ie with equivalence a_2 == b_3
1042 // given c_1 < a_2 && b_3 < d_4
1043 // convert the second relation (b_3 < d_4) to match any
1044 // equivalences to found in the first relation.
1045 // ie convert b_3 < d_4 to a_2 < d_4, which then exposes the
1046 // transitive operation: c_1 < a_2 && a_2 < d_4 -> c_1 < d_4
1049 tree p1
= ptr
->op1 ();
1050 tree p2
= ptr
->op2 ();
1051 // Find which equivalence is in the first operand.
1052 if (bitmap_bit_p (equiv1
, SSA_NAME_VERSION (p1
)))
1054 else if (bitmap_bit_p (equiv1
, SSA_NAME_VERSION (p2
)))
1059 // Find which equivalence is in the second operand.
1060 if (bitmap_bit_p (equiv2
, SSA_NAME_VERSION (p1
)))
1062 else if (bitmap_bit_p (equiv2
, SSA_NAME_VERSION (p2
)))
1067 // Ignore if both NULL (not relevant relation) or the same,
1071 // Any operand not an equivalence, just take the real operand.
1073 r1
= relation
.op1 ();
1075 r2
= relation
.op2 ();
1077 value_relation
nr (relation
.kind (), r1
, r2
);
1078 if (nr
.apply_transitive (*ptr
))
1080 if (!set_one_relation (root_bb
, nr
.kind (), nr
.op1 (), nr
.op2 ()))
1082 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1084 fprintf (dump_file
, " Registering transitive relation ");
1085 nr
.dump (dump_file
);
1086 fputc ('\n', dump_file
);
1094 // Find the relation between any ssa_name in B1 and any name in B2 in block BB.
1095 // This will allow equivalencies to be applied to any SSA_NAME in a relation.
1098 dom_oracle::find_relation_block (unsigned bb
, const_bitmap b1
,
1099 const_bitmap b2
) const
1101 if (bb
>= m_relations
.length())
1102 return VREL_VARYING
;
1104 return m_relations
[bb
].find_relation (b1
, b2
);
1107 // Search the DOM tree for a relation between an element of equivalency set B1
1108 // and B2, starting with block BB.
1111 dom_oracle::query_relation (basic_block bb
, const_bitmap b1
,
1115 if (bitmap_equal_p (b1
, b2
))
1118 // If either name does not occur in a relation anywhere, there isnt one.
1119 if (!bitmap_intersect_p (m_relation_set
, b1
)
1120 || !bitmap_intersect_p (m_relation_set
, b2
))
1121 return VREL_VARYING
;
1123 // Search each block in the DOM tree checking.
1124 for ( ; bb
; bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
1126 r
= find_relation_block (bb
->index
, b1
, b2
);
1127 if (r
!= VREL_VARYING
)
1130 return VREL_VARYING
;
1134 // Find a relation in block BB between ssa version V1 and V2. If a relation
1135 // is found, return a pointer to the chain object in OBJ.
1138 dom_oracle::find_relation_block (int bb
, unsigned v1
, unsigned v2
,
1139 relation_chain
**obj
) const
1141 if (bb
>= (int)m_relations
.length())
1142 return VREL_VARYING
;
1144 const_bitmap bm
= m_relations
[bb
].m_names
;
1146 return VREL_VARYING
;
1148 // If both b1 and b2 aren't referenced in thie block, cant be a relation
1149 if (!bitmap_bit_p (bm
, v1
) || !bitmap_bit_p (bm
, v2
))
1150 return VREL_VARYING
;
1152 relation_chain
*ptr
;
1153 for (ptr
= m_relations
[bb
].m_head
; ptr
; ptr
= ptr
->m_next
)
1155 unsigned op1
= SSA_NAME_VERSION (ptr
->op1 ());
1156 unsigned op2
= SSA_NAME_VERSION (ptr
->op2 ());
1157 if (v1
== op1
&& v2
== op2
)
1161 return ptr
->kind ();
1163 if (v1
== op2
&& v2
== op1
)
1167 return relation_swap (ptr
->kind ());
1171 return VREL_VARYING
;
1174 // Find a relation between SSA version V1 and V2 in the dominator tree
1175 // starting with block BB
1178 dom_oracle::find_relation_dom (basic_block bb
, unsigned v1
, unsigned v2
) const
1181 // IF either name does not occur in a relation anywhere, there isnt one.
1182 if (!bitmap_bit_p (m_relation_set
, v1
) || !bitmap_bit_p (m_relation_set
, v2
))
1183 return VREL_VARYING
;
1185 for ( ; bb
; bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
1187 r
= find_relation_block (bb
->index
, v1
, v2
);
1188 if (r
!= VREL_VARYING
)
1191 return VREL_VARYING
;
1195 // Query if there is a relation between SSA1 and SS2 in block BB or a
1199 dom_oracle::query_relation (basic_block bb
, tree ssa1
, tree ssa2
)
1202 unsigned v1
= SSA_NAME_VERSION (ssa1
);
1203 unsigned v2
= SSA_NAME_VERSION (ssa2
);
1207 // Check for equivalence first. They must be in each equivalency set.
1208 const_bitmap equiv1
= equiv_set (ssa1
, bb
);
1209 const_bitmap equiv2
= equiv_set (ssa2
, bb
);
1210 if (bitmap_bit_p (equiv1
, v2
) && bitmap_bit_p (equiv2
, v1
))
1213 // Initially look for a direct relationship and just return that.
1214 kind
= find_relation_dom (bb
, v1
, v2
);
1215 if (kind
!= VREL_VARYING
)
1218 // Query using the equivalence sets.
1219 kind
= query_relation (bb
, equiv1
, equiv2
);
1223 // Dump all the relations in block BB to file F.
1226 dom_oracle::dump (FILE *f
, basic_block bb
) const
1228 equiv_oracle::dump (f
,bb
);
1230 if (bb
->index
>= (int)m_relations
.length ())
1232 if (!m_relations
[bb
->index
].m_names
)
1235 relation_chain
*ptr
= m_relations
[bb
->index
].m_head
;
1236 for (; ptr
; ptr
= ptr
->m_next
)
1238 fprintf (f
, "Relational : ");
1244 // Dump all the relations known to file F.
1247 dom_oracle::dump (FILE *f
) const
1249 fprintf (f
, "Relation dump\n");
1250 for (unsigned i
= 0; i
< m_relations
.length (); i
++)
1251 if (BASIC_BLOCK_FOR_FN (cfun
, i
))
1253 fprintf (f
, "BB%d\n", i
);
1254 dump (f
, BASIC_BLOCK_FOR_FN (cfun
, i
));
1259 relation_oracle::debug () const
1264 path_oracle::path_oracle (relation_oracle
*oracle
)
1266 set_root_oracle (oracle
);
1267 bitmap_obstack_initialize (&m_bitmaps
);
1268 obstack_init (&m_chain_obstack
);
1270 // Initialize header records.
1271 m_equiv
.m_names
= BITMAP_ALLOC (&m_bitmaps
);
1272 m_equiv
.m_bb
= NULL
;
1273 m_equiv
.m_next
= NULL
;
1274 m_relations
.m_names
= BITMAP_ALLOC (&m_bitmaps
);
1275 m_relations
.m_head
= NULL
;
1276 m_killed_defs
= BITMAP_ALLOC (&m_bitmaps
);
1279 path_oracle::~path_oracle ()
1281 obstack_free (&m_chain_obstack
, NULL
);
1282 bitmap_obstack_release (&m_bitmaps
);
1285 // Return the equiv set for SSA, and if there isn't one, check for equivs
1286 // starting in block BB.
1289 path_oracle::equiv_set (tree ssa
, basic_block bb
)
1291 // Check the list first.
1292 equiv_chain
*ptr
= m_equiv
.find (SSA_NAME_VERSION (ssa
));
1294 return ptr
->m_names
;
1296 // Otherwise defer to the root oracle.
1298 return m_root
->equiv_set (ssa
, bb
);
1300 // Allocate a throw away bitmap if there isn't a root oracle.
1301 bitmap tmp
= BITMAP_ALLOC (&m_bitmaps
);
1302 bitmap_set_bit (tmp
, SSA_NAME_VERSION (ssa
));
1306 // Register an equivalence between SSA1 and SSA2 resolving unkowns from
1310 path_oracle::register_equiv (basic_block bb
, tree ssa1
, tree ssa2
)
1312 const_bitmap equiv_1
= equiv_set (ssa1
, bb
);
1313 const_bitmap equiv_2
= equiv_set (ssa2
, bb
);
1315 // Check if they are the same set, if so, we're done.
1316 if (bitmap_equal_p (equiv_1
, equiv_2
))
1319 // Don't mess around, simply create a new record and insert it first.
1320 bitmap b
= BITMAP_ALLOC (&m_bitmaps
);
1321 valid_equivs (b
, equiv_1
, bb
);
1322 valid_equivs (b
, equiv_2
, bb
);
1324 equiv_chain
*ptr
= (equiv_chain
*) obstack_alloc (&m_chain_obstack
,
1325 sizeof (equiv_chain
));
1328 ptr
->m_next
= m_equiv
.m_next
;
1329 m_equiv
.m_next
= ptr
;
1330 bitmap_ior_into (m_equiv
.m_names
, b
);
1333 // Register killing definition of an SSA_NAME.
1336 path_oracle::killing_def (tree ssa
)
1338 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1340 fprintf (dump_file
, " Registering killing_def (path_oracle) ");
1341 print_generic_expr (dump_file
, ssa
, TDF_SLIM
);
1342 fprintf (dump_file
, "\n");
1345 unsigned v
= SSA_NAME_VERSION (ssa
);
1347 bitmap_set_bit (m_killed_defs
, v
);
1348 bitmap_set_bit (m_equiv
.m_names
, v
);
1350 // Now add an equivalency with itself so we don't look to the root oracle.
1351 bitmap b
= BITMAP_ALLOC (&m_bitmaps
);
1352 bitmap_set_bit (b
, v
);
1353 equiv_chain
*ptr
= (equiv_chain
*) obstack_alloc (&m_chain_obstack
,
1354 sizeof (equiv_chain
));
1357 ptr
->m_next
= m_equiv
.m_next
;
1358 m_equiv
.m_next
= ptr
;
1360 // Walk the relation list and remove SSA from any relations.
1361 if (!bitmap_bit_p (m_relations
.m_names
, v
))
1364 bitmap_clear_bit (m_relations
.m_names
, v
);
1365 relation_chain
**prev
= &(m_relations
.m_head
);
1366 relation_chain
*next
= NULL
;
1367 for (relation_chain
*ptr
= m_relations
.m_head
; ptr
; ptr
= next
)
1369 gcc_checking_assert (*prev
== ptr
);
1371 if (SSA_NAME_VERSION (ptr
->op1 ()) == v
1372 || SSA_NAME_VERSION (ptr
->op2 ()) == v
)
1373 *prev
= ptr
->m_next
;
1375 prev
= &(ptr
->m_next
);
1379 // Register relation K between SSA1 and SSA2, resolving unknowns by
1380 // querying from BB.
1383 path_oracle::register_relation (basic_block bb
, relation_kind k
, tree ssa1
,
1386 // If the 2 ssa_names are the same, do nothing. An equivalence is implied,
1387 // and no other relation makes sense.
1391 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1393 value_relation
vr (k
, ssa1
, ssa2
);
1394 fprintf (dump_file
, " Registering value_relation (path_oracle) ");
1395 vr
.dump (dump_file
);
1396 fprintf (dump_file
, " (root: bb%d)\n", bb
->index
);
1399 relation_kind curr
= query_relation (bb
, ssa1
, ssa2
);
1400 if (curr
!= VREL_VARYING
)
1401 k
= relation_intersect (curr
, k
);
1405 register_equiv (bb
, ssa1
, ssa2
);
1409 bitmap_set_bit (m_relations
.m_names
, SSA_NAME_VERSION (ssa1
));
1410 bitmap_set_bit (m_relations
.m_names
, SSA_NAME_VERSION (ssa2
));
1411 relation_chain
*ptr
= (relation_chain
*) obstack_alloc (&m_chain_obstack
,
1412 sizeof (relation_chain
));
1413 ptr
->set_relation (k
, ssa1
, ssa2
);
1414 ptr
->m_next
= m_relations
.m_head
;
1415 m_relations
.m_head
= ptr
;
1418 // Query for a relationship between equiv set B1 and B2, resolving unknowns
1419 // starting at block BB.
1422 path_oracle::query_relation (basic_block bb
, const_bitmap b1
, const_bitmap b2
)
1424 if (bitmap_equal_p (b1
, b2
))
1427 relation_kind k
= m_relations
.find_relation (b1
, b2
);
1429 // Do not look at the root oracle for names that have been killed
1431 if (bitmap_intersect_p (m_killed_defs
, b1
)
1432 || bitmap_intersect_p (m_killed_defs
, b2
))
1435 if (k
== VREL_VARYING
&& m_root
)
1436 k
= m_root
->query_relation (bb
, b1
, b2
);
1441 // Query for a relationship between SSA1 and SSA2, resolving unknowns
1442 // starting at block BB.
1445 path_oracle::query_relation (basic_block bb
, tree ssa1
, tree ssa2
)
1447 unsigned v1
= SSA_NAME_VERSION (ssa1
);
1448 unsigned v2
= SSA_NAME_VERSION (ssa2
);
1453 const_bitmap equiv_1
= equiv_set (ssa1
, bb
);
1454 const_bitmap equiv_2
= equiv_set (ssa2
, bb
);
1455 if (bitmap_bit_p (equiv_1
, v2
) && bitmap_bit_p (equiv_2
, v1
))
1458 return query_relation (bb
, equiv_1
, equiv_2
);
1461 // Reset any relations registered on this path. ORACLE is the root
1465 path_oracle::reset_path (relation_oracle
*oracle
)
1467 set_root_oracle (oracle
);
1468 m_equiv
.m_next
= NULL
;
1469 bitmap_clear (m_equiv
.m_names
);
1470 m_relations
.m_head
= NULL
;
1471 bitmap_clear (m_relations
.m_names
);
1472 bitmap_clear (m_killed_defs
);
1475 // Dump relation in basic block... Do nothing here.
1478 path_oracle::dump (FILE *, basic_block
) const
1482 // Dump the relations and equivalencies found in the path.
1485 path_oracle::dump (FILE *f
) const
1487 equiv_chain
*ptr
= m_equiv
.m_next
;
1488 relation_chain
*ptr2
= m_relations
.m_head
;
1491 fprintf (f
, "\npath_oracle:\n");
1493 for (; ptr
; ptr
= ptr
->m_next
)
1496 for (; ptr2
; ptr2
= ptr2
->m_next
)
1498 fprintf (f
, "Relational : ");