1/* Gimple range edge functionality.
2 Copyright (C) 2020-2023 Free Software Foundation, Inc.
3 Contributed by Andrew MacLeod <amacleod@redhat.com>
4 and Aldy Hernandez <aldyh@redhat.com>.
5
6This file is part of GCC.
7
8GCC is free software; you can redistribute it and/or modify
9it under the terms of the GNU General Public License as published by
10the Free Software Foundation; either version 3, or (at your option)
11any later version.
12
13GCC is distributed in the hope that it will be useful,
14but WITHOUT ANY WARRANTY; without even the implied warranty of
15MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16GNU General Public License for more details.
17
18You should have received a copy of the GNU General Public License
19along with GCC; see the file COPYING3. If not see
20<http://www.gnu.org/licenses/>. */
21
22
23#include "config.h"
24#include "system.h"
25#include "coretypes.h"
26#include "backend.h"
27#include "tree.h"
28#include "gimple.h"
29#include "ssa.h"
30#include "gimple-pretty-print.h"
31#include "gimple-iterator.h"
32#include "tree-cfg.h"
33#include "gimple-range.h"
34#include "value-range-storage.h"
35
36// If there is a range control statement at the end of block BB, return it.
37// Otherwise return NULL.
38
39gimple *
40gimple_outgoing_range_stmt_p (basic_block bb)
41{
42 gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
43 if (!gsi_end_p (i: gsi))
44 {
45 gimple *s = gsi_stmt (i: gsi);
46 if (is_a<gcond *> (p: s) && gimple_range_op_handler::supported_p (s))
47 return gsi_stmt (i: gsi);
48 if (is_a <gswitch *> (p: s))
49 return gsi_stmt (i: gsi);
50 }
51 return NULL;
52}
53
54
55// Return a TRUE or FALSE range representing the edge value of a GCOND.
56
57void
58gcond_edge_range (irange &r, edge e)
59{
60 gcc_checking_assert (e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE));
61 if (e->flags & EDGE_TRUE_VALUE)
62 r = range_true ();
63 else
64 r = range_false ();
65}
66
67
68gimple_outgoing_range::gimple_outgoing_range (int max_sw_edges)
69{
70 m_edge_table = NULL;
71 m_max_edges = max_sw_edges;
72 m_range_allocator = new vrange_allocator;
73}
74
75
76gimple_outgoing_range::~gimple_outgoing_range ()
77{
78 if (m_edge_table)
79 delete m_edge_table;
80 delete m_range_allocator;
81}
82
83
84// Get a range for a switch edge E from statement S and return it in R.
85// Use a cached value if it exists, or calculate it if not.
86
87bool
88gimple_outgoing_range::switch_edge_range (irange &r, gswitch *sw, edge e)
89{
90 // ADA currently has cases where the index is 64 bits and the case
91 // arguments are 32 bit, causing a trap when we create a case_range.
92 // Until this is resolved (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87798)
93 // punt on switches where the labels don't match the argument.
94 if (gimple_switch_num_labels (gs: sw) > 1 &&
95 TYPE_PRECISION (TREE_TYPE (CASE_LOW (gimple_switch_label (sw, 1)))) !=
96 TYPE_PRECISION (TREE_TYPE (gimple_switch_index (sw))))
97 return false;
98
99 if (!m_edge_table)
100 m_edge_table = new hash_map<edge, vrange_storage *> (n_edges_for_fn (cfun));
101
102 vrange_storage **val = m_edge_table->get (k: e);
103 if (!val)
104 {
105 calc_switch_ranges (sw);
106 val = m_edge_table->get (k: e);
107 gcc_checking_assert (val);
108 }
109 (*val)->get_vrange (r, TREE_TYPE (gimple_switch_index (sw)));
110 return true;
111}
112
113
114// Calculate all switch edges from SW and cache them in the hash table.
115
116void
117gimple_outgoing_range::calc_switch_ranges (gswitch *sw)
118{
119 bool existed;
120 unsigned x, lim;
121 lim = gimple_switch_num_labels (gs: sw);
122 tree type = TREE_TYPE (gimple_switch_index (sw));
123 edge default_edge = gimple_switch_default_edge (cfun, sw);
124
125 // This should be the first call into this switch.
126 //
127 // Allocate an int_range_max for the default range case, start with
128 // varying and intersect each other case from it.
129 int_range_max default_range (type);
130
131 for (x = 1; x < lim; x++)
132 {
133 edge e = gimple_switch_edge (cfun, sw, x);
134
135 // If this edge is the same as the default edge, do nothing else.
136 if (e == default_edge)
137 continue;
138
139 wide_int low = wi::to_wide (CASE_LOW (gimple_switch_label (sw, x)));
140 wide_int high;
141 tree tree_high = CASE_HIGH (gimple_switch_label (sw, x));
142 if (tree_high)
143 high = wi::to_wide (t: tree_high);
144 else
145 high = low;
146
147 // Remove the case range from the default case.
148 int_range_max def_range (type, low, high);
149 range_cast (r&: def_range, type);
150 def_range.invert ();
151 default_range.intersect (def_range);
152
153 // Create/union this case with anything on else on the edge.
154 int_range_max case_range (type, low, high);
155 range_cast (r&: case_range, type);
156 vrange_storage *&slot = m_edge_table->get_or_insert (k: e, existed: &existed);
157 if (existed)
158 {
159 // If this doesn't change the value, move on.
160 int_range_max tmp;
161 slot->get_vrange (r&: tmp, type);
162 if (!case_range.union_ (tmp))
163 continue;
164 if (slot->fits_p (r: case_range))
165 {
166 slot->set_vrange (case_range);
167 continue;
168 }
169 }
170 // If there was an existing range and it doesn't fit, we lose the memory.
171 // It'll get reclaimed when the obstack is freed. This seems less
172 // intrusive than allocating max ranges for each case.
173 slot = m_range_allocator->clone (r: case_range);
174 }
175
176 vrange_storage *&slot = m_edge_table->get_or_insert (k: default_edge, existed: &existed);
177 // This should be the first call into this switch.
178 gcc_checking_assert (!existed);
179 slot = m_range_allocator->clone (r: default_range);
180}
181
182
183// Calculate the range forced on on edge E by control flow, return it
184// in R. Return the statement which defines the range, otherwise
185// return NULL
186
187gimple *
188gimple_outgoing_range::edge_range_p (irange &r, edge e)
189{
190 if (single_succ_p (bb: e->src))
191 return NULL;
192
193 // Determine if there is an outgoing edge.
194 gimple *s = gimple_outgoing_range_stmt_p (bb: e->src);
195 if (!s)
196 return NULL;
197
198 if (is_a<gcond *> (p: s))
199 {
200 gcond_edge_range (r, e);
201 return s;
202 }
203
204 // Only process switches if it within the size limit.
205 if (EDGE_COUNT (e->src->succs) > (unsigned)m_max_edges)
206 return NULL;
207
208 gcc_checking_assert (is_a<gswitch *> (s));
209 gswitch *sw = as_a<gswitch *> (p: s);
210
211 // Switches can only be integers.
212 if (switch_edge_range (r&: as_a <irange> (v&: r), sw, e))
213 return s;
214
215 return NULL;
216}
217

source code of gcc/gimple-range-edge.cc