1 /* Gimple range edge functionaluity.
2 Copyright (C) 2020-2021 Free Software Foundation, Inc.
3 Contributed by Andrew MacLeod <amacleod@redhat.com>
4 and Aldy Hernandez <aldyh@redhat.com>.
5
6 This file is part of GCC.
7
8 GCC 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 3, or (at your option)
11 any later version.
12
13 GCC 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.
17
18 You should have received a copy of the GNU General Public License
19 along 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
35 // If there is a range control statment at the end of block BB, return it.
36 // Otherwise return NULL.
37
38 gimple *
gimple_outgoing_range_stmt_p(basic_block bb)39 gimple_outgoing_range_stmt_p (basic_block bb)
40 {
41 gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
42 if (!gsi_end_p (gsi))
43 {
44 gimple *s = gsi_stmt (gsi);
45 if (is_a<gcond *> (s) && gimple_range_handler (s))
46 return gsi_stmt (gsi);
47 gswitch *sw = dyn_cast<gswitch *> (s);
48 if (sw && irange::supports_type_p (TREE_TYPE (gimple_switch_index (sw))))
49 return gsi_stmt (gsi);
50 }
51 return NULL;
52 }
53
54
55 // Return a TRUE or FALSE range representing the edge value of a GCOND.
56
57 void
gcond_edge_range(irange & r,edge e)58 gcond_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 = int_range<2> (boolean_true_node, boolean_true_node);
63 else
64 r = int_range<2> (boolean_false_node, boolean_false_node);
65 }
66
67
gimple_outgoing_range(int max_sw_edges)68 gimple_outgoing_range::gimple_outgoing_range (int max_sw_edges)
69 {
70 m_edge_table = NULL;
71 m_max_edges = max_sw_edges;
72 }
73
74
~gimple_outgoing_range()75 gimple_outgoing_range::~gimple_outgoing_range ()
76 {
77 if (m_edge_table)
78 delete m_edge_table;
79 }
80
81
82 // Get a range for a switch edge E from statement S and return it in R.
83 // Use a cached value if it exists, or calculate it if not.
84
85 bool
get_edge_range(irange & r,gimple * s,edge e)86 gimple_outgoing_range::get_edge_range (irange &r, gimple *s, edge e)
87 {
88 gcc_checking_assert (is_a<gswitch *> (s));
89 gswitch *sw = as_a<gswitch *> (s);
90
91 // ADA currently has cases where the index is 64 bits and the case
92 // arguments are 32 bit, causing a trap when we create a case_range.
93 // Until this is resolved (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87798)
94 // punt on switches where the labels dont match the argument.
95 if (gimple_switch_num_labels (sw) > 1 &&
96 TYPE_PRECISION (TREE_TYPE (CASE_LOW (gimple_switch_label (sw, 1)))) !=
97 TYPE_PRECISION (TREE_TYPE (gimple_switch_index (sw))))
98 return false;
99
100 if (!m_edge_table)
101 m_edge_table = new hash_map<edge, irange *> (n_edges_for_fn (cfun));
102
103 irange **val = m_edge_table->get (e);
104 if (!val)
105 {
106 calc_switch_ranges (sw);
107 val = m_edge_table->get (e);
108 gcc_checking_assert (val);
109 }
110 r = **val;
111 return true;
112 }
113
114
115 // Calculate all switch edges from SW and cache them in the hash table.
116
117 void
calc_switch_ranges(gswitch * sw)118 gimple_outgoing_range::calc_switch_ranges (gswitch *sw)
119 {
120 bool existed;
121 unsigned x, lim;
122 lim = gimple_switch_num_labels (sw);
123 tree type = TREE_TYPE (gimple_switch_index (sw));
124 edge default_edge = gimple_switch_default_edge (cfun, sw);
125
126 // This should be the first call into this switch.
127 //
128 // Allocate an int_range_max for the default range case, start with
129 // varying and intersect each other case from it.
130 int_range_max default_range (type);
131
132 for (x = 1; x < lim; x++)
133 {
134 edge e = gimple_switch_edge (cfun, sw, x);
135
136 // If this edge is the same as the default edge, do nothing else.
137 if (e == default_edge)
138 continue;
139
140 tree low = CASE_LOW (gimple_switch_label (sw, x));
141 tree high = CASE_HIGH (gimple_switch_label (sw, x));
142 if (!high)
143 high = low;
144
145 // Remove the case range from the default case.
146 int_range_max def_range (low, high);
147 range_cast (def_range, type);
148 def_range.invert ();
149 default_range.intersect (def_range);
150
151 // Create/union this case with anything on else on the edge.
152 int_range_max case_range (low, high);
153 range_cast (case_range, type);
154 irange *&slot = m_edge_table->get_or_insert (e, &existed);
155 if (existed)
156 {
157 case_range.union_ (*slot);
158 if (slot->fits_p (case_range))
159 {
160 *slot = case_range;
161 continue;
162 }
163 }
164 // If there was an existing range and it doesn't fit, we lose the memory.
165 // It'll get reclaimed when the obstack is freed. This seems less
166 // intrusive than allocating max ranges for each case.
167 slot = m_range_allocator.allocate (case_range);
168 }
169
170 irange *&slot = m_edge_table->get_or_insert (default_edge, &existed);
171 // This should be the first call into this switch.
172 gcc_checking_assert (!existed);
173 irange *dr = m_range_allocator.allocate (default_range);
174 slot = dr;
175 }
176
177
178 // Calculate the range forced on on edge E by control flow, return it
179 // in R. Return the statment which defines the range, otherwise
180 // return NULL
181
182 gimple *
edge_range_p(irange & r,edge e)183 gimple_outgoing_range::edge_range_p (irange &r, edge e)
184 {
185 // Determine if there is an outgoing edge.
186 gimple *s = gimple_outgoing_range_stmt_p (e->src);
187 if (!s)
188 return NULL;
189
190 if (is_a<gcond *> (s))
191 {
192 gcond_edge_range (r, e);
193 return s;
194 }
195
196 // Only process switches if it within the size limit.
197 if (EDGE_COUNT (e->src->succs) > (unsigned)m_max_edges)
198 return NULL;
199
200 gcc_checking_assert (is_a<gswitch *> (s));
201 gswitch *sw = as_a<gswitch *> (s);
202 tree type = TREE_TYPE (gimple_switch_index (sw));
203
204 if (!irange::supports_type_p (type))
205 return NULL;
206
207 if (get_edge_range (r, sw, e))
208 return s;
209
210 return NULL;
211 }
212