1 /* Gimple ranger SSA cache implementation.
2 Copyright (C) 2017-2021 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
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
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"
25 #include "insn-codes.h"
29 #include "gimple-pretty-print.h"
30 #include "gimple-range.h"
32 // During contructor, allocate the vector of ssa_names.
34 non_null_ref::non_null_ref ()
37 m_nn
.safe_grow_cleared (num_ssa_names
);
38 bitmap_obstack_initialize (&m_bitmaps
);
41 // Free any bitmaps which were allocated,a swell as the vector itself.
43 non_null_ref::~non_null_ref ()
45 bitmap_obstack_release (&m_bitmaps
);
49 // Return true if NAME has a non-null dereference in block bb. If this is the
50 // first query for NAME, calculate the summary first.
51 // If SEARCH_DOM is true, the search the dominator tree as well.
54 non_null_ref::non_null_deref_p (tree name
, basic_block bb
, bool search_dom
)
56 if (!POINTER_TYPE_P (TREE_TYPE (name
)))
59 unsigned v
= SSA_NAME_VERSION (name
);
63 if (bitmap_bit_p (m_nn
[v
], bb
->index
))
66 // See if any dominator has set non-zero.
67 if (search_dom
&& dom_info_available_p (CDI_DOMINATORS
))
69 // Search back to the Def block, or the top, whichever is closer.
70 basic_block def_bb
= gimple_bb (SSA_NAME_DEF_STMT (name
));
71 basic_block def_dom
= def_bb
72 ? get_immediate_dominator (CDI_DOMINATORS
, def_bb
)
76 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
77 if (bitmap_bit_p (m_nn
[v
], bb
->index
))
83 // Allocate an populate the bitmap for NAME. An ON bit for a block
84 // index indicates there is a non-null reference in that block. In
85 // order to populate the bitmap, a quick run of all the immediate uses
86 // are made and the statement checked to see if a non-null dereference
87 // is made on that statement.
90 non_null_ref::process_name (tree name
)
92 unsigned v
= SSA_NAME_VERSION (name
);
94 imm_use_iterator iter
;
97 // Only tracked for pointers.
98 if (!POINTER_TYPE_P (TREE_TYPE (name
)))
101 // Already processed if a bitmap has been allocated.
105 b
= BITMAP_ALLOC (&m_bitmaps
);
107 // Loop over each immediate use and see if it implies a non-null value.
108 FOR_EACH_IMM_USE_FAST (use_p
, iter
, name
)
110 gimple
*s
= USE_STMT (use_p
);
111 unsigned index
= gimple_bb (s
)->index
;
113 // If bit is already set for this block, dont bother looking again.
114 if (bitmap_bit_p (b
, index
))
117 // If we can infer a nonnull range, then set the bit for this BB
118 if (!SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name
)
119 && infer_nonnull_range (s
, name
))
120 bitmap_set_bit (b
, index
);
126 // -------------------------------------------------------------------------
128 // This class represents the API into a cache of ranges for an SSA_NAME.
129 // Routines must be implemented to set, get, and query if a value is set.
131 class ssa_block_ranges
134 virtual void set_bb_range (const basic_block bb
, const irange
&r
) = 0;
135 virtual bool get_bb_range (irange
&r
, const basic_block bb
) = 0;
136 virtual bool bb_range_p (const basic_block bb
) = 0;
141 // Print the list of known ranges for file F in a nice format.
144 ssa_block_ranges::dump (FILE *f
)
149 FOR_EACH_BB_FN (bb
, cfun
)
150 if (get_bb_range (r
, bb
))
152 fprintf (f
, "BB%d -> ", bb
->index
);
158 // This class implements the range cache as a linear vector, indexed by BB.
159 // It caches a varying and undefined range which are used instead of
160 // allocating new ones each time.
162 class sbr_vector
: public ssa_block_ranges
165 sbr_vector (tree t
, irange_allocator
*allocator
);
167 virtual void set_bb_range (const basic_block bb
, const irange
&r
) OVERRIDE
;
168 virtual bool get_bb_range (irange
&r
, const basic_block bb
) OVERRIDE
;
169 virtual bool bb_range_p (const basic_block bb
) OVERRIDE
;
171 irange
**m_tab
; // Non growing vector.
173 int_range
<2> m_varying
;
174 int_range
<2> m_undefined
;
176 irange_allocator
*m_irange_allocator
;
180 // Initialize a block cache for an ssa_name of type T.
182 sbr_vector::sbr_vector (tree t
, irange_allocator
*allocator
)
184 gcc_checking_assert (TYPE_P (t
));
186 m_irange_allocator
= allocator
;
187 m_tab_size
= last_basic_block_for_fn (cfun
) + 1;
188 m_tab
= (irange
**)allocator
->get_memory (m_tab_size
* sizeof (irange
*));
189 memset (m_tab
, 0, m_tab_size
* sizeof (irange
*));
191 // Create the cached type range.
192 m_varying
.set_varying (t
);
193 m_undefined
.set_undefined ();
196 // Set the range for block BB to be R.
199 sbr_vector::set_bb_range (const basic_block bb
, const irange
&r
)
202 gcc_checking_assert (bb
->index
< m_tab_size
);
205 else if (r
.undefined_p ())
208 m
= m_irange_allocator
->allocate (r
);
209 m_tab
[bb
->index
] = m
;
212 // Return the range associated with block BB in R. Return false if
213 // there is no range.
216 sbr_vector::get_bb_range (irange
&r
, const basic_block bb
)
218 gcc_checking_assert (bb
->index
< m_tab_size
);
219 irange
*m
= m_tab
[bb
->index
];
228 // Return true if a range is present.
231 sbr_vector::bb_range_p (const basic_block bb
)
233 gcc_checking_assert (bb
->index
< m_tab_size
);
234 return m_tab
[bb
->index
] != NULL
;
237 // -------------------------------------------------------------------------
239 // Initialize the block cache.
241 block_range_cache::block_range_cache ()
243 m_ssa_ranges
.create (0);
244 m_ssa_ranges
.safe_grow_cleared (num_ssa_names
);
245 m_irange_allocator
= new irange_allocator
;
248 // Remove any m_block_caches which have been created.
250 block_range_cache::~block_range_cache ()
252 delete m_irange_allocator
;
253 // Release the vector itself.
254 m_ssa_ranges
.release ();
257 // Set the range for NAME on entry to block BB to R.
258 // If it has not been // accessed yet, allocate it first.
261 block_range_cache::set_bb_range (tree name
, const basic_block bb
,
264 unsigned v
= SSA_NAME_VERSION (name
);
265 if (v
>= m_ssa_ranges
.length ())
266 m_ssa_ranges
.safe_grow_cleared (num_ssa_names
+ 1);
268 if (!m_ssa_ranges
[v
])
270 void *r
= m_irange_allocator
->get_memory (sizeof (sbr_vector
));
271 m_ssa_ranges
[v
] = new (r
) sbr_vector (TREE_TYPE (name
),
274 m_ssa_ranges
[v
]->set_bb_range (bb
, r
);
278 // Return a pointer to the ssa_block_cache for NAME. If it has not been
279 // accessed yet, return NULL.
281 inline ssa_block_ranges
*
282 block_range_cache::query_block_ranges (tree name
)
284 unsigned v
= SSA_NAME_VERSION (name
);
285 if (v
>= m_ssa_ranges
.length () || !m_ssa_ranges
[v
])
287 return m_ssa_ranges
[v
];
292 // Return the range for NAME on entry to BB in R. Return true if there
296 block_range_cache::get_bb_range (irange
&r
, tree name
, const basic_block bb
)
298 ssa_block_ranges
*ptr
= query_block_ranges (name
);
300 return ptr
->get_bb_range (r
, bb
);
304 // Return true if NAME has a range set in block BB.
307 block_range_cache::bb_range_p (tree name
, const basic_block bb
)
309 ssa_block_ranges
*ptr
= query_block_ranges (name
);
311 return ptr
->bb_range_p (bb
);
315 // Print all known block caches to file F.
318 block_range_cache::dump (FILE *f
)
321 for (x
= 0; x
< m_ssa_ranges
.length (); ++x
)
325 fprintf (f
, " Ranges for ");
326 print_generic_expr (f
, ssa_name (x
), TDF_NONE
);
328 m_ssa_ranges
[x
]->dump (f
);
334 // Print all known ranges on entry to blobk BB to file F.
337 block_range_cache::dump (FILE *f
, basic_block bb
, bool print_varying
)
341 bool summarize_varying
= false;
342 for (x
= 1; x
< m_ssa_ranges
.length (); ++x
)
344 if (!gimple_range_ssa_p (ssa_name (x
)))
346 if (m_ssa_ranges
[x
] && m_ssa_ranges
[x
]->get_bb_range (r
, bb
))
348 if (!print_varying
&& r
.varying_p ())
350 summarize_varying
= true;
353 print_generic_expr (f
, ssa_name (x
), TDF_NONE
);
359 // If there were any varying entries, lump them all together.
360 if (summarize_varying
)
362 fprintf (f
, "VARYING_P on entry : ");
363 for (x
= 1; x
< num_ssa_names
; ++x
)
365 if (!gimple_range_ssa_p (ssa_name (x
)))
367 if (m_ssa_ranges
[x
] && m_ssa_ranges
[x
]->get_bb_range (r
, bb
))
371 print_generic_expr (f
, ssa_name (x
), TDF_NONE
);
380 // -------------------------------------------------------------------------
382 // Initialize a global cache.
384 ssa_global_cache::ssa_global_cache ()
387 m_tab
.safe_grow_cleared (num_ssa_names
);
388 m_irange_allocator
= new irange_allocator
;
391 // Deconstruct a global cache.
393 ssa_global_cache::~ssa_global_cache ()
396 delete m_irange_allocator
;
399 // Retrieve the global range of NAME from cache memory if it exists.
400 // Return the value in R.
403 ssa_global_cache::get_global_range (irange
&r
, tree name
) const
405 unsigned v
= SSA_NAME_VERSION (name
);
406 if (v
>= m_tab
.length ())
409 irange
*stow
= m_tab
[v
];
416 // Set the range for NAME to R in the global cache.
417 // Return TRUE if there was already a range set, otherwise false.
420 ssa_global_cache::set_global_range (tree name
, const irange
&r
)
422 unsigned v
= SSA_NAME_VERSION (name
);
423 if (v
>= m_tab
.length ())
424 m_tab
.safe_grow_cleared (num_ssa_names
+ 1);
426 irange
*m
= m_tab
[v
];
427 if (m
&& m
->fits_p (r
))
430 m_tab
[v
] = m_irange_allocator
->allocate (r
);
434 // Set the range for NAME to R in the glonbal cache.
437 ssa_global_cache::clear_global_range (tree name
)
439 unsigned v
= SSA_NAME_VERSION (name
);
440 if (v
>= m_tab
.length ())
441 m_tab
.safe_grow_cleared (num_ssa_names
+ 1);
445 // Clear the global cache.
448 ssa_global_cache::clear ()
450 memset (m_tab
.address(), 0, m_tab
.length () * sizeof (irange
*));
453 // Dump the contents of the global cache to F.
456 ssa_global_cache::dump (FILE *f
)
460 fprintf (f
, "Non-varying global ranges:\n");
461 fprintf (f
, "=========================:\n");
462 for ( x
= 1; x
< num_ssa_names
; x
++)
463 if (gimple_range_ssa_p (ssa_name (x
)) &&
464 get_global_range (r
, ssa_name (x
)) && !r
.varying_p ())
466 print_generic_expr (f
, ssa_name (x
), TDF_NONE
);
474 // --------------------------------------------------------------------------
477 // This class will manage the timestamps for each ssa_name.
478 // When a value is calculated, the timestamp is set to the current time.
479 // Current time is then incremented. Any dependencies will already have
480 // been calculated, and will thus have older timestamps.
481 // If one of those values is ever calculated again, it will get a newer
482 // timestamp, and the "current_p" check will fail.
489 bool current_p (tree name
, tree dep1
, tree dep2
) const;
490 void set_timestamp (tree name
);
491 void set_always_current (tree name
);
493 unsigned temporal_value (unsigned ssa
) const;
495 unsigned m_current_time
;
496 vec
<unsigned> m_timestamp
;
500 temporal_cache::temporal_cache ()
503 m_timestamp
.create (0);
504 m_timestamp
.safe_grow_cleared (num_ssa_names
);
508 temporal_cache::~temporal_cache ()
510 m_timestamp
.release ();
513 // Return the timestamp value for SSA, or 0 if there isnt one.
516 temporal_cache::temporal_value (unsigned ssa
) const
518 if (ssa
>= m_timestamp
.length ())
520 return m_timestamp
[ssa
];
523 // Return TRUE if the timestampe for NAME is newer than any of its dependents.
524 // Up to 2 dependencies can be checked.
527 temporal_cache::current_p (tree name
, tree dep1
, tree dep2
) const
529 unsigned ts
= temporal_value (SSA_NAME_VERSION (name
));
533 // Any non-registered dependencies will have a value of 0 and thus be older.
534 // Return true if time is newer than either dependent.
536 if (dep1
&& ts
< temporal_value (SSA_NAME_VERSION (dep1
)))
538 if (dep2
&& ts
< temporal_value (SSA_NAME_VERSION (dep2
)))
544 // This increments the global timer and sets the timestamp for NAME.
547 temporal_cache::set_timestamp (tree name
)
549 unsigned v
= SSA_NAME_VERSION (name
);
550 if (v
>= m_timestamp
.length ())
551 m_timestamp
.safe_grow_cleared (num_ssa_names
+ 20);
552 m_timestamp
[v
] = ++m_current_time
;
555 // Set the timestamp to 0, marking it as "always up to date".
558 temporal_cache::set_always_current (tree name
)
560 unsigned v
= SSA_NAME_VERSION (name
);
561 if (v
>= m_timestamp
.length ())
562 m_timestamp
.safe_grow_cleared (num_ssa_names
+ 20);
566 // --------------------------------------------------------------------------
568 ranger_cache::ranger_cache (gimple_ranger
&q
) : query (q
)
570 m_workback
.create (0);
571 m_workback
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
572 m_update_list
.create (0);
573 m_update_list
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
574 m_update_list
.truncate (0);
575 m_poor_value_list
.create (0);
576 m_poor_value_list
.safe_grow_cleared (20);
577 m_poor_value_list
.truncate (0);
578 m_temporal
= new temporal_cache
;
579 unsigned x
, lim
= last_basic_block_for_fn (cfun
);
580 // Calculate outgoing range info upfront. This will fully populate the
581 // m_maybe_variant bitmap which will help eliminate processing of names
582 // which never have their ranges adjusted.
583 for (x
= 0; x
< lim
; x
++)
585 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, x
);
591 ranger_cache::~ranger_cache ()
594 m_poor_value_list
.release ();
595 m_workback
.release ();
596 m_update_list
.release ();
599 // Dump the global caches to file F. if GORI_DUMP is true, dump the
603 ranger_cache::dump (FILE *f
, bool gori_dump
)
608 fprintf (f
, "\nDUMPING GORI MAP\n");
609 gori_compute::dump (f
);
614 // Dump the caches for basic block BB to file F.
617 ranger_cache::dump (FILE *f
, basic_block bb
)
619 m_on_entry
.dump (f
, bb
);
622 // Get the global range for NAME, and return in R. Return false if the
623 // global range is not set.
626 ranger_cache::get_global_range (irange
&r
, tree name
) const
628 return m_globals
.get_global_range (r
, name
);
631 // Get the global range for NAME, and return in R if the value is not stale.
632 // If the range is set, but is stale, mark it current and return false.
633 // If it is not set pick up the legacy global value, mark it current, and
635 // Note there is always a value returned in R. The return value indicates
636 // whether that value is an up-to-date calculated value or not..
639 ranger_cache::get_non_stale_global_range (irange
&r
, tree name
)
641 if (m_globals
.get_global_range (r
, name
))
643 if (m_temporal
->current_p (name
, depend1 (name
), depend2 (name
)))
648 // Global has never been accessed, so pickup the legacy global value.
649 r
= gimple_range_global (name
);
650 m_globals
.set_global_range (name
, r
);
652 // After a stale check failure, mark the value as always current until a
654 m_temporal
->set_always_current (name
);
657 // Set the global range of NAME to R.
660 ranger_cache::set_global_range (tree name
, const irange
&r
)
662 if (m_globals
.set_global_range (name
, r
))
664 // If there was already a range set, propagate the new value.
665 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (name
));
667 bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
669 if (DEBUG_RANGE_CACHE
)
670 fprintf (dump_file
, " GLOBAL :");
672 propagate_updated_value (name
, bb
);
674 // Constants no longer need to tracked. Any further refinement has to be
675 // undefined. Propagation works better with constants. PR 100512.
676 // Pointers which resolve to non-zero also do not need
677 // tracking in the cache as they will never change. See PR 98866.
678 // Otherwise mark the value as up-to-date.
680 || (POINTER_TYPE_P (TREE_TYPE (name
)) && r
.nonzero_p ()))
682 set_range_invariant (name
);
683 m_temporal
->set_always_current (name
);
686 m_temporal
->set_timestamp (name
);
689 // Push a request for a new lookup in block BB of name. Return true if
690 // the request is actually made (ie, isn't a duplicate).
693 ranger_cache::push_poor_value (basic_block bb
, tree name
)
695 if (m_poor_value_list
.length ())
697 // Don't push anything else to the same block. If there are multiple
698 // things required, another request will come during a later evaluation
699 // and this prevents oscillation building uneccessary depth.
700 if ((m_poor_value_list
.last ()).bb
== bb
)
704 struct update_record rec
;
707 m_poor_value_list
.safe_push (rec
);
711 // Provide lookup for the gori-computes class to access the best known range
712 // of an ssa_name in any given basic block. Note, this does no additonal
713 // lookups, just accesses the data that is already known.
716 ranger_cache::ssa_range_in_bb (irange
&r
, tree name
, basic_block bb
)
718 gimple
*s
= SSA_NAME_DEF_STMT (name
);
719 basic_block def_bb
= ((s
&& gimple_bb (s
)) ? gimple_bb (s
) :
720 ENTRY_BLOCK_PTR_FOR_FN (cfun
));
723 // NAME is defined in this block, so request its current value
724 if (!m_globals
.get_global_range (r
, name
))
726 // If it doesn't have a value calculated, it means it's a
727 // "poor" value being used in some calculation. Queue it up
728 // as a poor value to be improved later.
729 r
= gimple_range_global (name
);
730 if (push_poor_value (bb
, name
))
732 if (DEBUG_RANGE_CACHE
)
735 "*CACHE* no global def in bb %d for ", bb
->index
);
736 print_generic_expr (dump_file
, name
, TDF_SLIM
);
737 fprintf (dump_file
, " depth : %d\n",
738 m_poor_value_list
.length ());
743 // Look for the on-entry value of name in BB from the cache.
744 else if (!m_on_entry
.get_bb_range (r
, name
, bb
))
746 // If it has no entry but should, then mark this as a poor value.
747 // Its not a poor value if it does not have *any* edge ranges,
748 // Then global range is as good as it gets.
749 if (has_edge_range_p (name
) && push_poor_value (bb
, name
))
751 if (DEBUG_RANGE_CACHE
)
754 "*CACHE* no on entry range in bb %d for ", bb
->index
);
755 print_generic_expr (dump_file
, name
, TDF_SLIM
);
756 fprintf (dump_file
, " depth : %d\n", m_poor_value_list
.length ());
759 // Try to pick up any known global value as a best guess for now.
760 if (!m_globals
.get_global_range (r
, name
))
761 r
= gimple_range_global (name
);
764 // Check if pointers have any non-null dereferences. Non-call
765 // exceptions mean we could throw in the middle of the block, so just
766 // punt for now on those.
767 if (r
.varying_p () && m_non_null
.non_null_deref_p (name
, bb
, false) &&
768 !cfun
->can_throw_non_call_exceptions
)
769 r
= range_nonzero (TREE_TYPE (name
));
772 // Return a static range for NAME on entry to basic block BB in R. If
773 // calc is true, fill any cache entries required between BB and the
774 // def block for NAME. Otherwise, return false if the cache is empty.
777 ranger_cache::block_range (irange
&r
, basic_block bb
, tree name
, bool calc
)
779 gcc_checking_assert (gimple_range_ssa_p (name
));
781 // If there are no range calculations anywhere in the IL, global range
782 // applies everywhere, so don't bother caching it.
783 if (!has_edge_range_p (name
))
788 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
789 basic_block def_bb
= NULL
;
791 def_bb
= gimple_bb (def_stmt
);;
794 // If we get to the entry block, this better be a default def
795 // or range_on_entry was called for a block not dominated by
797 gcc_checking_assert (SSA_NAME_IS_DEFAULT_DEF (name
));
798 def_bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
801 // There is no range on entry for the definition block.
805 // Otherwise, go figure out what is known in predecessor blocks.
806 fill_block_cache (name
, bb
, def_bb
);
807 gcc_checking_assert (m_on_entry
.bb_range_p (name
, bb
));
809 return m_on_entry
.get_bb_range (r
, name
, bb
);
812 // Add BB to the list of blocks to update, unless it's already in the list.
815 ranger_cache::add_to_update (basic_block bb
)
817 if (!m_update_list
.contains (bb
))
818 m_update_list
.quick_push (bb
);
821 // If there is anything in the propagation update_list, continue
822 // processing NAME until the list of blocks is empty.
825 ranger_cache::propagate_cache (tree name
)
830 int_range_max new_range
;
831 int_range_max current_range
;
832 int_range_max e_range
;
834 // Process each block by seeing if its calculated range on entry is
835 // the same as its cached value. If there is a difference, update
836 // the cache to reflect the new value, and check to see if any
837 // successors have cache entries which may need to be checked for
840 while (m_update_list
.length () > 0)
842 bb
= m_update_list
.pop ();
843 gcc_checking_assert (m_on_entry
.bb_range_p (name
, bb
));
844 m_on_entry
.get_bb_range (current_range
, name
, bb
);
846 // Calculate the "new" range on entry by unioning the pred edges.
847 new_range
.set_undefined ();
848 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
850 if (DEBUG_RANGE_CACHE
)
851 fprintf (dump_file
, " edge %d->%d :", e
->src
->index
, bb
->index
);
852 // Get whatever range we can for this edge.
853 if (!outgoing_edge_range_p (e_range
, e
, name
))
855 ssa_range_in_bb (e_range
, name
, e
->src
);
856 if (DEBUG_RANGE_CACHE
)
858 fprintf (dump_file
, "No outgoing edge range, picked up ");
859 e_range
.dump(dump_file
);
860 fprintf (dump_file
, "\n");
865 if (DEBUG_RANGE_CACHE
)
867 fprintf (dump_file
, "outgoing range :");
868 e_range
.dump(dump_file
);
869 fprintf (dump_file
, "\n");
872 new_range
.union_ (e_range
);
873 if (new_range
.varying_p ())
877 if (DEBUG_RANGE_CACHE
)
879 fprintf (dump_file
, "FWD visiting block %d for ", bb
->index
);
880 print_generic_expr (dump_file
, name
, TDF_SLIM
);
881 fprintf (dump_file
, " starting range : ");
882 current_range
.dump (dump_file
);
883 fprintf (dump_file
, "\n");
886 // If the range on entry has changed, update it.
887 if (new_range
!= current_range
)
889 if (DEBUG_RANGE_CACHE
)
891 fprintf (dump_file
, " Updating range to ");
892 new_range
.dump (dump_file
);
893 fprintf (dump_file
, "\n Updating blocks :");
895 m_on_entry
.set_bb_range (name
, bb
, new_range
);
896 // Mark each successor that has a range to re-check its range
897 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
898 if (m_on_entry
.bb_range_p (name
, e
->dest
))
900 if (DEBUG_RANGE_CACHE
)
901 fprintf (dump_file
, " bb%d",e
->dest
->index
);
902 add_to_update (e
->dest
);
904 if (DEBUG_RANGE_CACHE
)
905 fprintf (dump_file
, "\n");
908 if (DEBUG_RANGE_CACHE
)
910 fprintf (dump_file
, "DONE visiting blocks for ");
911 print_generic_expr (dump_file
, name
, TDF_SLIM
);
912 fprintf (dump_file
, "\n");
916 // Check to see if an update to the value for NAME in BB has any effect
917 // on values already in the on-entry cache for successor blocks.
918 // If it does, update them. Don't visit any blocks which dont have a cache
922 ranger_cache::propagate_updated_value (tree name
, basic_block bb
)
927 // The update work list should be empty at this point.
928 gcc_checking_assert (m_update_list
.length () == 0);
929 gcc_checking_assert (bb
);
931 if (DEBUG_RANGE_CACHE
)
933 fprintf (dump_file
, " UPDATE cache for ");
934 print_generic_expr (dump_file
, name
, TDF_SLIM
);
935 fprintf (dump_file
, " in BB %d : successors : ", bb
->index
);
937 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
939 // Only update active cache entries.
940 if (m_on_entry
.bb_range_p (name
, e
->dest
))
942 add_to_update (e
->dest
);
943 if (DEBUG_RANGE_CACHE
)
944 fprintf (dump_file
, " UPDATE: bb%d", e
->dest
->index
);
947 if (m_update_list
.length () != 0)
949 if (DEBUG_RANGE_CACHE
)
950 fprintf (dump_file
, "\n");
951 propagate_cache (name
);
955 if (DEBUG_RANGE_CACHE
)
956 fprintf (dump_file
, " : No updates!\n");
960 // Make sure that the range-on-entry cache for NAME is set for block BB.
961 // Work back through the CFG to DEF_BB ensuring the range is calculated
962 // on the block/edges leading back to that point.
965 ranger_cache::fill_block_cache (tree name
, basic_block bb
, basic_block def_bb
)
969 int_range_max block_result
;
970 int_range_max undefined
;
971 unsigned poor_list_start
= m_poor_value_list
.length ();
973 // At this point we shouldn't be looking at the def, entry or exit block.
974 gcc_checking_assert (bb
!= def_bb
&& bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
) &&
975 bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
977 // If the block cache is set, then we've already visited this block.
978 if (m_on_entry
.bb_range_p (name
, bb
))
981 // Visit each block back to the DEF. Initialize each one to UNDEFINED.
982 // m_visited at the end will contain all the blocks that we needed to set
983 // the range_on_entry cache for.
984 m_workback
.truncate (0);
985 m_workback
.quick_push (bb
);
986 undefined
.set_undefined ();
987 m_on_entry
.set_bb_range (name
, bb
, undefined
);
988 gcc_checking_assert (m_update_list
.length () == 0);
990 if (DEBUG_RANGE_CACHE
)
992 fprintf (dump_file
, "\n");
993 print_generic_expr (dump_file
, name
, TDF_SLIM
);
994 fprintf (dump_file
, " : ");
997 while (m_workback
.length () > 0)
999 basic_block node
= m_workback
.pop ();
1000 if (DEBUG_RANGE_CACHE
)
1002 fprintf (dump_file
, "BACK visiting block %d for ", node
->index
);
1003 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1004 fprintf (dump_file
, "\n");
1007 FOR_EACH_EDGE (e
, ei
, node
->preds
)
1009 basic_block pred
= e
->src
;
1012 if (DEBUG_RANGE_CACHE
)
1013 fprintf (dump_file
, " %d->%d ",e
->src
->index
, e
->dest
->index
);
1015 // If the pred block is the def block add this BB to update list.
1018 add_to_update (node
);
1022 // If the pred is entry but NOT def, then it is used before
1023 // defined, it'll get set to [] and no need to update it.
1024 if (pred
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1026 if (DEBUG_RANGE_CACHE
)
1027 fprintf (dump_file
, "entry: bail.");
1031 // Regardless of whether we have visited pred or not, if the
1032 // pred has a non-null reference, revisit this block.
1033 // Don't search the DOM tree.
1034 if (m_non_null
.non_null_deref_p (name
, pred
, false))
1036 if (DEBUG_RANGE_CACHE
)
1037 fprintf (dump_file
, "nonnull: update ");
1038 add_to_update (node
);
1041 // If the pred block already has a range, or if it can contribute
1042 // something new. Ie, the edge generates a range of some sort.
1043 if (m_on_entry
.get_bb_range (r
, name
, pred
))
1045 if (DEBUG_RANGE_CACHE
)
1046 fprintf (dump_file
, "has cache, ");
1047 if (!r
.undefined_p () || has_edge_range_p (name
, e
))
1049 add_to_update (node
);
1050 if (DEBUG_RANGE_CACHE
)
1051 fprintf (dump_file
, "update. ");
1056 if (DEBUG_RANGE_CACHE
)
1057 fprintf (dump_file
, "pushing undefined pred block. ");
1058 // If the pred hasn't been visited (has no range), add it to
1060 gcc_checking_assert (!m_on_entry
.bb_range_p (name
, pred
));
1061 m_on_entry
.set_bb_range (name
, pred
, undefined
);
1062 m_workback
.quick_push (pred
);
1066 if (DEBUG_RANGE_CACHE
)
1067 fprintf (dump_file
, "\n");
1069 // Now fill in the marked blocks with values.
1070 propagate_cache (name
);
1071 if (DEBUG_RANGE_CACHE
)
1072 fprintf (dump_file
, " Propagation update done.\n");
1074 // Now that the cache has been updated, check to see if there were any
1075 // SSA_NAMES used in filling the cache which were "poor values".
1076 // Evaluate them, and inject any new values into the propagation
1077 // list, and see if it improves any on-entry values.
1078 if (poor_list_start
!= m_poor_value_list
.length ())
1080 gcc_checking_assert (poor_list_start
< m_poor_value_list
.length ());
1081 while (poor_list_start
< m_poor_value_list
.length ())
1083 // Find a range for this unresolved value.
1084 // Note, this may spawn new cache filling cycles, but by the time it
1085 // is finished, the work vectors will all be back to the same state
1086 // as before the call. The update record vector will always be
1087 // returned to the current state upon return.
1088 struct update_record rec
= m_poor_value_list
.pop ();
1089 basic_block calc_bb
= rec
.bb
;
1092 if (DEBUG_RANGE_CACHE
)
1094 fprintf (dump_file
, "(%d:%d)Calculating ",
1095 m_poor_value_list
.length () + 1, poor_list_start
);
1096 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1097 fprintf (dump_file
, " used POOR VALUE for ");
1098 print_generic_expr (dump_file
, rec
.calc
, TDF_SLIM
);
1099 fprintf (dump_file
, " in bb%d, trying to improve:\n",
1103 // Calculate a range at the exit from the block so the caches feeding
1104 // this block will be filled, and we'll get a "better" value.
1105 query
.range_on_exit (tmp
, calc_bb
, rec
.calc
);
1107 // Then ask for NAME to be re-evaluated on outgoing edges and
1108 // use any new values.
1109 propagate_updated_value (name
, calc_bb
);