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
outgoing_range()55 outgoing_range::outgoing_range ()
56 {
57 m_edge_table = NULL;
58 }
59
~outgoing_range()60 outgoing_range::~outgoing_range ()
61 {
62 if (m_edge_table)
63 delete m_edge_table;
64 }
65
66
67 // Get a range for a switch edge E from statement S and return it in R.
68 // Use a cached value if it exists, or calculate it if not.
69
70 bool
get_edge_range(irange & r,gimple * s,edge e)71 outgoing_range::get_edge_range (irange &r, gimple *s, edge e)
72 {
73 gcc_checking_assert (is_a<gswitch *> (s));
74 gswitch *sw = as_a<gswitch *> (s);
75
76 // ADA currently has cases where the index is 64 bits and the case
77 // arguments are 32 bit, causing a trap when we create a case_range.
78 // Until this is resolved (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87798)
79 // punt on switches where the labels dont match the argument.
80 if (gimple_switch_num_labels (sw) > 1 &&
81 TYPE_PRECISION (TREE_TYPE (CASE_LOW (gimple_switch_label (sw, 1)))) !=
82 TYPE_PRECISION (TREE_TYPE (gimple_switch_index (sw))))
83 return false;
84
85 if (!m_edge_table)
86 m_edge_table = new hash_map<edge, irange *> (n_edges_for_fn (cfun));
87
88 irange **val = m_edge_table->get (e);
89 if (!val)
90 {
91 calc_switch_ranges (sw);
92 val = m_edge_table->get (e);
93 gcc_checking_assert (val);
94 }
95 r = **val;
96 return true;
97 }
98
99
100 // Calculate all switch edges from SW and cache them in the hash table.
101
102 void
calc_switch_ranges(gswitch * sw)103 outgoing_range::calc_switch_ranges (gswitch *sw)
104 {
105 bool existed;
106 unsigned x, lim;
107 lim = gimple_switch_num_labels (sw);
108 tree type = TREE_TYPE (gimple_switch_index (sw));
109 edge default_edge = gimple_switch_default_edge (cfun, sw);
110
111 // This should be the first call into this switch.
112 //
113 // Allocate an int_range_max for the default range case, start with
114 // varying and intersect each other case from it.
115 irange *default_range = m_range_allocator.allocate (255);
116 default_range->set_varying (type);
117
118 for (x = 1; x < lim; x++)
119 {
120 edge e = gimple_switch_edge (cfun, sw, x);
121
122 // If this edge is the same as the default edge, do nothing else.
123 if (e == default_edge)
124 continue;
125
126 tree low = CASE_LOW (gimple_switch_label (sw, x));
127 tree high = CASE_HIGH (gimple_switch_label (sw, x));
128 if (!high)
129 high = low;
130
131 // Remove the case range from the default case.
132 int_range_max def_range (low, high);
133 range_cast (def_range, type);
134 def_range.invert ();
135 default_range->intersect (def_range);
136
137 // Create/union this case with anything on else on the edge.
138 int_range_max case_range (low, high);
139 range_cast (case_range, type);
140 irange *&slot = m_edge_table->get_or_insert (e, &existed);
141 if (existed)
142 {
143 case_range.union_ (*slot);
144 if (slot->fits_p (case_range))
145 {
146 *slot = case_range;
147 continue;
148 }
149 }
150 // If there was an existing range and it doesn't fit, we lose the memory.
151 // It'll get reclaimed when the obstack is freed. This seems less
152 // intrusive than allocating max ranges for each case.
153 slot = m_range_allocator.allocate (case_range);
154 }
155
156 irange *&slot = m_edge_table->get_or_insert (default_edge, &existed);
157 // This should be the first call into this switch.
158 gcc_checking_assert (!existed);
159 slot = default_range;
160 }
161
162
163 // Calculate the range forced on on edge E by control flow, return it
164 // in R. Return the statment which defines the range, otherwise
165 // return NULL
166
167 gimple *
edge_range_p(irange & r,edge e)168 outgoing_range::edge_range_p (irange &r, edge e)
169 {
170 // Determine if there is an outgoing edge.
171 gimple *s = gimple_outgoing_range_stmt_p (e->src);
172 if (!s)
173 return NULL;
174
175 if (is_a<gcond *> (s))
176 {
177 if (e->flags & EDGE_TRUE_VALUE)
178 r = int_range<2> (boolean_true_node, boolean_true_node);
179 else if (e->flags & EDGE_FALSE_VALUE)
180 r = int_range<2> (boolean_false_node, boolean_false_node);
181 else
182 gcc_unreachable ();
183 return s;
184 }
185
186 gcc_checking_assert (is_a<gswitch *> (s));
187 gswitch *sw = as_a<gswitch *> (s);
188 tree type = TREE_TYPE (gimple_switch_index (sw));
189
190 if (!irange::supports_type_p (type))
191 return NULL;
192
193 if (get_edge_range (r, sw, e))
194 return s;
195
196 return NULL;
197 }
198