Bug Summary

File:build/gcc/vec.h
Warning:line 814, column 10
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-unknown-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name tree-ssa-pre.c -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model static -mframe-pointer=none -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/objdir/gcc -resource-dir /usr/lib64/clang/13.0.0 -D IN_GCC -D HAVE_CONFIG_H -I . -I . -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/. -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../include -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../libcpp/include -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../libcody -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../libdecnumber -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../libdecnumber/bid -I ../libdecnumber -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../libbacktrace -internal-isystem /usr/bin/../lib64/gcc/x86_64-suse-linux/11/../../../../include/c++/11 -internal-isystem /usr/bin/../lib64/gcc/x86_64-suse-linux/11/../../../../include/c++/11/x86_64-suse-linux -internal-isystem /usr/bin/../lib64/gcc/x86_64-suse-linux/11/../../../../include/c++/11/backward -internal-isystem /usr/lib64/clang/13.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/bin/../lib64/gcc/x86_64-suse-linux/11/../../../../x86_64-suse-linux/include -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-narrowing -Wwrite-strings -Wno-error=format-diag -Wno-long-long -Wno-variadic-macros -Wno-overlength-strings -fdeprecated-macro -fdebug-compilation-dir=/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/objdir/gcc -ferror-limit 19 -fno-rtti -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=plist-html -analyzer-config silence-checkers=core.NullDereference -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/objdir/clang-static-analyzer/2021-11-20-133755-20252-1/report-QTbnLJ.plist -x c++ /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c

/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c

1/* Full and partial redundancy elimination and code hoisting on SSA GIMPLE.
2 Copyright (C) 2001-2021 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dan@dberlin.org> and Steven Bosscher
4 <stevenb@suse.de>
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#include "config.h"
23#include "system.h"
24#include "coretypes.h"
25#include "backend.h"
26#include "rtl.h"
27#include "tree.h"
28#include "gimple.h"
29#include "predict.h"
30#include "alloc-pool.h"
31#include "tree-pass.h"
32#include "ssa.h"
33#include "cgraph.h"
34#include "gimple-pretty-print.h"
35#include "fold-const.h"
36#include "cfganal.h"
37#include "gimple-fold.h"
38#include "tree-eh.h"
39#include "gimplify.h"
40#include "gimple-iterator.h"
41#include "tree-cfg.h"
42#include "tree-into-ssa.h"
43#include "tree-dfa.h"
44#include "tree-ssa.h"
45#include "cfgloop.h"
46#include "tree-ssa-sccvn.h"
47#include "tree-scalar-evolution.h"
48#include "dbgcnt.h"
49#include "domwalk.h"
50#include "tree-ssa-propagate.h"
51#include "tree-ssa-dce.h"
52#include "tree-cfgcleanup.h"
53#include "alias.h"
54#include "gimple-range.h"
55
56/* Even though this file is called tree-ssa-pre.c, we actually
57 implement a bit more than just PRE here. All of them piggy-back
58 on GVN which is implemented in tree-ssa-sccvn.c.
59
60 1. Full Redundancy Elimination (FRE)
61 This is the elimination phase of GVN.
62
63 2. Partial Redundancy Elimination (PRE)
64 This is adds computation of AVAIL_OUT and ANTIC_IN and
65 doing expression insertion to form GVN-PRE.
66
67 3. Code hoisting
68 This optimization uses the ANTIC_IN sets computed for PRE
69 to move expressions further up than PRE would do, to make
70 multiple computations of the same value fully redundant.
71 This pass is explained below (after the explanation of the
72 basic algorithm for PRE).
73*/
74
75/* TODO:
76
77 1. Avail sets can be shared by making an avail_find_leader that
78 walks up the dominator tree and looks in those avail sets.
79 This might affect code optimality, it's unclear right now.
80 Currently the AVAIL_OUT sets are the remaining quadraticness in
81 memory of GVN-PRE.
82 2. Strength reduction can be performed by anticipating expressions
83 we can repair later on.
84 3. We can do back-substitution or smarter value numbering to catch
85 commutative expressions split up over multiple statements.
86*/
87
88/* For ease of terminology, "expression node" in the below refers to
89 every expression node but GIMPLE_ASSIGN, because GIMPLE_ASSIGNs
90 represent the actual statement containing the expressions we care about,
91 and we cache the value number by putting it in the expression. */
92
93/* Basic algorithm for Partial Redundancy Elimination:
94
95 First we walk the statements to generate the AVAIL sets, the
96 EXP_GEN sets, and the tmp_gen sets. EXP_GEN sets represent the
97 generation of values/expressions by a given block. We use them
98 when computing the ANTIC sets. The AVAIL sets consist of
99 SSA_NAME's that represent values, so we know what values are
100 available in what blocks. AVAIL is a forward dataflow problem. In
101 SSA, values are never killed, so we don't need a kill set, or a
102 fixpoint iteration, in order to calculate the AVAIL sets. In
103 traditional parlance, AVAIL sets tell us the downsafety of the
104 expressions/values.
105
106 Next, we generate the ANTIC sets. These sets represent the
107 anticipatable expressions. ANTIC is a backwards dataflow
108 problem. An expression is anticipatable in a given block if it could
109 be generated in that block. This means that if we had to perform
110 an insertion in that block, of the value of that expression, we
111 could. Calculating the ANTIC sets requires phi translation of
112 expressions, because the flow goes backwards through phis. We must
113 iterate to a fixpoint of the ANTIC sets, because we have a kill
114 set. Even in SSA form, values are not live over the entire
115 function, only from their definition point onwards. So we have to
116 remove values from the ANTIC set once we go past the definition
117 point of the leaders that make them up.
118 compute_antic/compute_antic_aux performs this computation.
119
120 Third, we perform insertions to make partially redundant
121 expressions fully redundant.
122
123 An expression is partially redundant (excluding partial
124 anticipation) if:
125
126 1. It is AVAIL in some, but not all, of the predecessors of a
127 given block.
128 2. It is ANTIC in all the predecessors.
129
130 In order to make it fully redundant, we insert the expression into
131 the predecessors where it is not available, but is ANTIC.
132
133 When optimizing for size, we only eliminate the partial redundancy
134 if we need to insert in only one predecessor. This avoids almost
135 completely the code size increase that PRE usually causes.
136
137 For the partial anticipation case, we only perform insertion if it
138 is partially anticipated in some block, and fully available in all
139 of the predecessors.
140
141 do_pre_regular_insertion/do_pre_partial_partial_insertion
142 performs these steps, driven by insert/insert_aux.
143
144 Fourth, we eliminate fully redundant expressions.
145 This is a simple statement walk that replaces redundant
146 calculations with the now available values. */
147
148/* Basic algorithm for Code Hoisting:
149
150 Code hoisting is: Moving value computations up in the control flow
151 graph to make multiple copies redundant. Typically this is a size
152 optimization, but there are cases where it also is helpful for speed.
153
154 A simple code hoisting algorithm is implemented that piggy-backs on
155 the PRE infrastructure. For code hoisting, we have to know ANTIC_OUT
156 which is effectively ANTIC_IN - AVAIL_OUT. The latter two have to be
157 computed for PRE, and we can use them to perform a limited version of
158 code hoisting, too.
159
160 For the purpose of this implementation, a value is hoistable to a basic
161 block B if the following properties are met:
162
163 1. The value is in ANTIC_IN(B) -- the value will be computed on all
164 paths from B to function exit and it can be computed in B);
165
166 2. The value is not in AVAIL_OUT(B) -- there would be no need to
167 compute the value again and make it available twice;
168
169 3. All successors of B are dominated by B -- makes sure that inserting
170 a computation of the value in B will make the remaining
171 computations fully redundant;
172
173 4. At least one successor has the value in AVAIL_OUT -- to avoid
174 hoisting values up too far;
175
176 5. There are at least two successors of B -- hoisting in straight
177 line code is pointless.
178
179 The third condition is not strictly necessary, but it would complicate
180 the hoisting pass a lot. In fact, I don't know of any code hoisting
181 algorithm that does not have this requirement. Fortunately, experiments
182 have show that most candidate hoistable values are in regions that meet
183 this condition (e.g. diamond-shape regions).
184
185 The forth condition is necessary to avoid hoisting things up too far
186 away from the uses of the value. Nothing else limits the algorithm
187 from hoisting everything up as far as ANTIC_IN allows. Experiments
188 with SPEC and CSiBE have shown that hoisting up too far results in more
189 spilling, less benefits for code size, and worse benchmark scores.
190 Fortunately, in practice most of the interesting hoisting opportunities
191 are caught despite this limitation.
192
193 For hoistable values that meet all conditions, expressions are inserted
194 to make the calculation of the hoistable value fully redundant. We
195 perform code hoisting insertions after each round of PRE insertions,
196 because code hoisting never exposes new PRE opportunities, but PRE can
197 create new code hoisting opportunities.
198
199 The code hoisting algorithm is implemented in do_hoist_insert, driven
200 by insert/insert_aux. */
201
202/* Representations of value numbers:
203
204 Value numbers are represented by a representative SSA_NAME. We
205 will create fake SSA_NAME's in situations where we need a
206 representative but do not have one (because it is a complex
207 expression). In order to facilitate storing the value numbers in
208 bitmaps, and keep the number of wasted SSA_NAME's down, we also
209 associate a value_id with each value number, and create full blown
210 ssa_name's only where we actually need them (IE in operands of
211 existing expressions).
212
213 Theoretically you could replace all the value_id's with
214 SSA_NAME_VERSION, but this would allocate a large number of
215 SSA_NAME's (which are each > 30 bytes) just to get a 4 byte number.
216 It would also require an additional indirection at each point we
217 use the value id. */
218
219/* Representation of expressions on value numbers:
220
221 Expressions consisting of value numbers are represented the same
222 way as our VN internally represents them, with an additional
223 "pre_expr" wrapping around them in order to facilitate storing all
224 of the expressions in the same sets. */
225
226/* Representation of sets:
227
228 The dataflow sets do not need to be sorted in any particular order
229 for the majority of their lifetime, are simply represented as two
230 bitmaps, one that keeps track of values present in the set, and one
231 that keeps track of expressions present in the set.
232
233 When we need them in topological order, we produce it on demand by
234 transforming the bitmap into an array and sorting it into topo
235 order. */
236
237/* Type of expression, used to know which member of the PRE_EXPR union
238 is valid. */
239
240enum pre_expr_kind
241{
242 NAME,
243 NARY,
244 REFERENCE,
245 CONSTANT
246};
247
248union pre_expr_union
249{
250 tree name;
251 tree constant;
252 vn_nary_op_t nary;
253 vn_reference_t reference;
254};
255
256typedef struct pre_expr_d : nofree_ptr_hash <pre_expr_d>
257{
258 enum pre_expr_kind kind;
259 unsigned int id;
260 unsigned value_id;
261 location_t loc;
262 pre_expr_union u;
263
264 /* hash_table support. */
265 static inline hashval_t hash (const pre_expr_d *);
266 static inline int equal (const pre_expr_d *, const pre_expr_d *);
267} *pre_expr;
268
269#define PRE_EXPR_NAME(e)(e)->u.name (e)->u.name
270#define PRE_EXPR_NARY(e)(e)->u.nary (e)->u.nary
271#define PRE_EXPR_REFERENCE(e)(e)->u.reference (e)->u.reference
272#define PRE_EXPR_CONSTANT(e)(e)->u.constant (e)->u.constant
273
274/* Compare E1 and E1 for equality. */
275
276inline int
277pre_expr_d::equal (const pre_expr_d *e1, const pre_expr_d *e2)
278{
279 if (e1->kind != e2->kind)
280 return false;
281
282 switch (e1->kind)
283 {
284 case CONSTANT:
285 return vn_constant_eq_with_type (PRE_EXPR_CONSTANT (e1)(e1)->u.constant,
286 PRE_EXPR_CONSTANT (e2)(e2)->u.constant);
287 case NAME:
288 return PRE_EXPR_NAME (e1)(e1)->u.name == PRE_EXPR_NAME (e2)(e2)->u.name;
289 case NARY:
290 return vn_nary_op_eq (PRE_EXPR_NARY (e1)(e1)->u.nary, PRE_EXPR_NARY (e2)(e2)->u.nary);
291 case REFERENCE:
292 return vn_reference_eq (PRE_EXPR_REFERENCE (e1)(e1)->u.reference,
293 PRE_EXPR_REFERENCE (e2)(e2)->u.reference);
294 default:
295 gcc_unreachable ()(fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 295, __FUNCTION__))
;
296 }
297}
298
299/* Hash E. */
300
301inline hashval_t
302pre_expr_d::hash (const pre_expr_d *e)
303{
304 switch (e->kind)
305 {
306 case CONSTANT:
307 return vn_hash_constant_with_type (PRE_EXPR_CONSTANT (e)(e)->u.constant);
308 case NAME:
309 return SSA_NAME_VERSION (PRE_EXPR_NAME (e))(tree_check (((e)->u.name), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 309, __FUNCTION__, (SSA_NAME)))->base.u.version
;
310 case NARY:
311 return PRE_EXPR_NARY (e)(e)->u.nary->hashcode;
312 case REFERENCE:
313 return PRE_EXPR_REFERENCE (e)(e)->u.reference->hashcode;
314 default:
315 gcc_unreachable ()(fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 315, __FUNCTION__))
;
316 }
317}
318
319/* Next global expression id number. */
320static unsigned int next_expression_id;
321
322/* Mapping from expression to id number we can use in bitmap sets. */
323static vec<pre_expr> expressions;
324static hash_table<pre_expr_d> *expression_to_id;
325static vec<unsigned> name_to_id;
326
327/* Allocate an expression id for EXPR. */
328
329static inline unsigned int
330alloc_expression_id (pre_expr expr)
331{
332 struct pre_expr_d **slot;
333 /* Make sure we won't overflow. */
334 gcc_assert (next_expression_id + 1 > next_expression_id)((void)(!(next_expression_id + 1 > next_expression_id) ? fancy_abort
("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 334, __FUNCTION__), 0 : 0))
;
335 expr->id = next_expression_id++;
336 expressions.safe_push (expr);
337 if (expr->kind == NAME)
338 {
339 unsigned version = SSA_NAME_VERSION (PRE_EXPR_NAME (expr))(tree_check (((expr)->u.name), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 339, __FUNCTION__, (SSA_NAME)))->base.u.version
;
340 /* vec::safe_grow_cleared allocates no headroom. Avoid frequent
341 re-allocations by using vec::reserve upfront. */
342 unsigned old_len = name_to_id.length ();
343 name_to_id.reserve (num_ssa_names(vec_safe_length ((cfun + 0)->gimple_df->ssa_names)) - old_len);
344 name_to_id.quick_grow_cleared (num_ssa_names(vec_safe_length ((cfun + 0)->gimple_df->ssa_names)));
345 gcc_assert (name_to_id[version] == 0)((void)(!(name_to_id[version] == 0) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 345, __FUNCTION__), 0 : 0))
;
346 name_to_id[version] = expr->id;
347 }
348 else
349 {
350 slot = expression_to_id->find_slot (expr, INSERT);
351 gcc_assert (!*slot)((void)(!(!*slot) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 351, __FUNCTION__), 0 : 0))
;
352 *slot = expr;
353 }
354 return next_expression_id - 1;
355}
356
357/* Return the expression id for tree EXPR. */
358
359static inline unsigned int
360get_expression_id (const pre_expr expr)
361{
362 return expr->id;
363}
364
365static inline unsigned int
366lookup_expression_id (const pre_expr expr)
367{
368 struct pre_expr_d **slot;
369
370 if (expr->kind == NAME)
371 {
372 unsigned version = SSA_NAME_VERSION (PRE_EXPR_NAME (expr))(tree_check (((expr)->u.name), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 372, __FUNCTION__, (SSA_NAME)))->base.u.version
;
373 if (name_to_id.length () <= version)
374 return 0;
375 return name_to_id[version];
376 }
377 else
378 {
379 slot = expression_to_id->find_slot (expr, NO_INSERT);
380 if (!slot)
381 return 0;
382 return ((pre_expr)*slot)->id;
383 }
384}
385
386/* Return the existing expression id for EXPR, or create one if one
387 does not exist yet. */
388
389static inline unsigned int
390get_or_alloc_expression_id (pre_expr expr)
391{
392 unsigned int id = lookup_expression_id (expr);
393 if (id == 0)
394 return alloc_expression_id (expr);
395 return expr->id = id;
396}
397
398/* Return the expression that has expression id ID */
399
400static inline pre_expr
401expression_for_id (unsigned int id)
402{
403 return expressions[id];
404}
405
406static object_allocator<pre_expr_d> pre_expr_pool ("pre_expr nodes");
407
408/* Given an SSA_NAME NAME, get or create a pre_expr to represent it. */
409
410static pre_expr
411get_or_alloc_expr_for_name (tree name)
412{
413 struct pre_expr_d expr;
414 pre_expr result;
415 unsigned int result_id;
416
417 expr.kind = NAME;
418 expr.id = 0;
419 PRE_EXPR_NAME (&expr)(&expr)->u.name = name;
420 result_id = lookup_expression_id (&expr);
421 if (result_id != 0)
422 return expression_for_id (result_id);
423
424 result = pre_expr_pool.allocate ();
425 result->kind = NAME;
426 result->loc = UNKNOWN_LOCATION((location_t) 0);
427 result->value_id = VN_INFO (name)->value_id;
428 PRE_EXPR_NAME (result)(result)->u.name = name;
429 alloc_expression_id (result);
430 return result;
431}
432
433/* Given an NARY, get or create a pre_expr to represent it. */
434
435static pre_expr
436get_or_alloc_expr_for_nary (vn_nary_op_t nary,
437 location_t loc = UNKNOWN_LOCATION((location_t) 0))
438{
439 struct pre_expr_d expr;
440 pre_expr result;
441 unsigned int result_id;
442
443 expr.kind = NARY;
444 expr.id = 0;
445 PRE_EXPR_NARY (&expr)(&expr)->u.nary = nary;
446 result_id = lookup_expression_id (&expr);
447 if (result_id != 0)
448 return expression_for_id (result_id);
449
450 result = pre_expr_pool.allocate ();
451 result->kind = NARY;
452 result->loc = loc;
453 result->value_id = nary->value_id;
454 PRE_EXPR_NARY (result)(result)->u.nary = nary;
455 alloc_expression_id (result);
456 return result;
457}
458
459/* Given an REFERENCE, get or create a pre_expr to represent it. */
460
461static pre_expr
462get_or_alloc_expr_for_reference (vn_reference_t reference,
463 location_t loc = UNKNOWN_LOCATION((location_t) 0))
464{
465 struct pre_expr_d expr;
466 pre_expr result;
467 unsigned int result_id;
468
469 expr.kind = REFERENCE;
470 expr.id = 0;
471 PRE_EXPR_REFERENCE (&expr)(&expr)->u.reference = reference;
472 result_id = lookup_expression_id (&expr);
473 if (result_id != 0)
474 return expression_for_id (result_id);
475
476 result = pre_expr_pool.allocate ();
477 result->kind = REFERENCE;
478 result->loc = loc;
479 result->value_id = reference->value_id;
480 PRE_EXPR_REFERENCE (result)(result)->u.reference = reference;
481 alloc_expression_id (result);
482 return result;
483}
484
485
486/* An unordered bitmap set. One bitmap tracks values, the other,
487 expressions. */
488typedef class bitmap_set
489{
490public:
491 bitmap_head expressions;
492 bitmap_head values;
493} *bitmap_set_t;
494
495#define FOR_EACH_EXPR_ID_IN_SET(set, id, bi)for (bmp_iter_set_init (&((bi)), (&(set)->expressions
), (0), &((id))); bmp_iter_set (&((bi)), &((id)))
; bmp_iter_next (&((bi)), &((id))))
\
496 EXECUTE_IF_SET_IN_BITMAP (&(set)->expressions, 0, (id), (bi))for (bmp_iter_set_init (&((bi)), (&(set)->expressions
), (0), &((id))); bmp_iter_set (&((bi)), &((id)))
; bmp_iter_next (&((bi)), &((id))))
497
498#define FOR_EACH_VALUE_ID_IN_SET(set, id, bi)for (bmp_iter_set_init (&((bi)), (&(set)->values),
(0), &((id))); bmp_iter_set (&((bi)), &((id))); bmp_iter_next
(&((bi)), &((id))))
\
499 EXECUTE_IF_SET_IN_BITMAP (&(set)->values, 0, (id), (bi))for (bmp_iter_set_init (&((bi)), (&(set)->values),
(0), &((id))); bmp_iter_set (&((bi)), &((id))); bmp_iter_next
(&((bi)), &((id))))
500
501/* Mapping from value id to expressions with that value_id. */
502static vec<bitmap> value_expressions;
503/* We just record a single expression for each constant value,
504 one of kind CONSTANT. */
505static vec<pre_expr> constant_value_expressions;
506
507
508/* This structure is used to keep track of statistics on what
509 optimization PRE was able to perform. */
510static struct
511{
512 /* The number of new expressions/temporaries generated by PRE. */
513 int insertions;
514
515 /* The number of inserts found due to partial anticipation */
516 int pa_insert;
517
518 /* The number of inserts made for code hoisting. */
519 int hoist_insert;
520
521 /* The number of new PHI nodes added by PRE. */
522 int phis;
523} pre_stats;
524
525static bool do_partial_partial;
526static pre_expr bitmap_find_leader (bitmap_set_t, unsigned int);
527static void bitmap_value_insert_into_set (bitmap_set_t, pre_expr);
528static bool bitmap_value_replace_in_set (bitmap_set_t, pre_expr);
529static void bitmap_set_copy (bitmap_set_t, bitmap_set_t);
530static bool bitmap_set_contains_value (bitmap_set_t, unsigned int);
531static void bitmap_insert_into_set (bitmap_set_t, pre_expr);
532static bitmap_set_t bitmap_set_new (void);
533static tree create_expression_by_pieces (basic_block, pre_expr, gimple_seq *,
534 tree);
535static tree find_or_generate_expression (basic_block, tree, gimple_seq *);
536static unsigned int get_expr_value_id (pre_expr);
537
538/* We can add and remove elements and entries to and from sets
539 and hash tables, so we use alloc pools for them. */
540
541static object_allocator<bitmap_set> bitmap_set_pool ("Bitmap sets");
542static bitmap_obstack grand_bitmap_obstack;
543
544/* A three tuple {e, pred, v} used to cache phi translations in the
545 phi_translate_table. */
546
547typedef struct expr_pred_trans_d : public typed_noop_remove <expr_pred_trans_d>
548{
549 typedef expr_pred_trans_d value_type;
550 typedef expr_pred_trans_d compare_type;
551
552 /* The expression ID. */
553 unsigned e;
554
555 /* The value expression ID that resulted from the translation. */
556 unsigned v;
557
558 /* hash_table support. */
559 static inline void mark_empty (expr_pred_trans_d &);
560 static inline bool is_empty (const expr_pred_trans_d &);
561 static inline void mark_deleted (expr_pred_trans_d &);
562 static inline bool is_deleted (const expr_pred_trans_d &);
563 static const bool empty_zero_p = true;
564 static inline hashval_t hash (const expr_pred_trans_d &);
565 static inline int equal (const expr_pred_trans_d &, const expr_pred_trans_d &);
566} *expr_pred_trans_t;
567typedef const struct expr_pred_trans_d *const_expr_pred_trans_t;
568
569inline bool
570expr_pred_trans_d::is_empty (const expr_pred_trans_d &e)
571{
572 return e.e == 0;
573}
574
575inline bool
576expr_pred_trans_d::is_deleted (const expr_pred_trans_d &e)
577{
578 return e.e == -1u;
579}
580
581inline void
582expr_pred_trans_d::mark_empty (expr_pred_trans_d &e)
583{
584 e.e = 0;
585}
586
587inline void
588expr_pred_trans_d::mark_deleted (expr_pred_trans_d &e)
589{
590 e.e = -1u;
591}
592
593inline hashval_t
594expr_pred_trans_d::hash (const expr_pred_trans_d &e)
595{
596 return e.e;
597}
598
599inline int
600expr_pred_trans_d::equal (const expr_pred_trans_d &ve1,
601 const expr_pred_trans_d &ve2)
602{
603 return ve1.e == ve2.e;
604}
605
606/* Sets that we need to keep track of. */
607typedef struct bb_bitmap_sets
608{
609 /* The EXP_GEN set, which represents expressions/values generated in
610 a basic block. */
611 bitmap_set_t exp_gen;
612
613 /* The PHI_GEN set, which represents PHI results generated in a
614 basic block. */
615 bitmap_set_t phi_gen;
616
617 /* The TMP_GEN set, which represents results/temporaries generated
618 in a basic block. IE the LHS of an expression. */
619 bitmap_set_t tmp_gen;
620
621 /* The AVAIL_OUT set, which represents which values are available in
622 a given basic block. */
623 bitmap_set_t avail_out;
624
625 /* The ANTIC_IN set, which represents which values are anticipatable
626 in a given basic block. */
627 bitmap_set_t antic_in;
628
629 /* The PA_IN set, which represents which values are
630 partially anticipatable in a given basic block. */
631 bitmap_set_t pa_in;
632
633 /* The NEW_SETS set, which is used during insertion to augment the
634 AVAIL_OUT set of blocks with the new insertions performed during
635 the current iteration. */
636 bitmap_set_t new_sets;
637
638 /* A cache for value_dies_in_block_x. */
639 bitmap expr_dies;
640
641 /* The live virtual operand on successor edges. */
642 tree vop_on_exit;
643
644 /* PHI translate cache for the single successor edge. */
645 hash_table<expr_pred_trans_d> *phi_translate_table;
646
647 /* True if we have visited this block during ANTIC calculation. */
648 unsigned int visited : 1;
649
650 /* True when the block contains a call that might not return. */
651 unsigned int contains_may_not_return_call : 1;
652} *bb_value_sets_t;
653
654#define EXP_GEN(BB)((bb_value_sets_t) ((BB)->aux))->exp_gen ((bb_value_sets_t) ((BB)->aux))->exp_gen
655#define PHI_GEN(BB)((bb_value_sets_t) ((BB)->aux))->phi_gen ((bb_value_sets_t) ((BB)->aux))->phi_gen
656#define TMP_GEN(BB)((bb_value_sets_t) ((BB)->aux))->tmp_gen ((bb_value_sets_t) ((BB)->aux))->tmp_gen
657#define AVAIL_OUT(BB)((bb_value_sets_t) ((BB)->aux))->avail_out ((bb_value_sets_t) ((BB)->aux))->avail_out
658#define ANTIC_IN(BB)((bb_value_sets_t) ((BB)->aux))->antic_in ((bb_value_sets_t) ((BB)->aux))->antic_in
659#define PA_IN(BB)((bb_value_sets_t) ((BB)->aux))->pa_in ((bb_value_sets_t) ((BB)->aux))->pa_in
660#define NEW_SETS(BB)((bb_value_sets_t) ((BB)->aux))->new_sets ((bb_value_sets_t) ((BB)->aux))->new_sets
661#define EXPR_DIES(BB)((bb_value_sets_t) ((BB)->aux))->expr_dies ((bb_value_sets_t) ((BB)->aux))->expr_dies
662#define PHI_TRANS_TABLE(BB)((bb_value_sets_t) ((BB)->aux))->phi_translate_table ((bb_value_sets_t) ((BB)->aux))->phi_translate_table
663#define BB_VISITED(BB)((bb_value_sets_t) ((BB)->aux))->visited ((bb_value_sets_t) ((BB)->aux))->visited
664#define BB_MAY_NOTRETURN(BB)((bb_value_sets_t) ((BB)->aux))->contains_may_not_return_call ((bb_value_sets_t) ((BB)->aux))->contains_may_not_return_call
665#define BB_LIVE_VOP_ON_EXIT(BB)((bb_value_sets_t) ((BB)->aux))->vop_on_exit ((bb_value_sets_t) ((BB)->aux))->vop_on_exit
666
667
668/* Add the tuple mapping from {expression E, basic block PRED} to
669 the phi translation table and return whether it pre-existed. */
670
671static inline bool
672phi_trans_add (expr_pred_trans_t *entry, pre_expr e, basic_block pred)
673{
674 if (!PHI_TRANS_TABLE (pred)((bb_value_sets_t) ((pred)->aux))->phi_translate_table)
675 PHI_TRANS_TABLE (pred)((bb_value_sets_t) ((pred)->aux))->phi_translate_table = new hash_table<expr_pred_trans_d> (11);
676
677 expr_pred_trans_t slot;
678 expr_pred_trans_d tem;
679 unsigned id = get_expression_id (e);
680 tem.e = id;
681 slot = PHI_TRANS_TABLE (pred)((bb_value_sets_t) ((pred)->aux))->phi_translate_table->find_slot_with_hash (tem, id, INSERT);
682 if (slot->e)
683 {
684 *entry = slot;
685 return true;
686 }
687
688 *entry = slot;
689 slot->e = id;
690 return false;
691}
692
693
694/* Add expression E to the expression set of value id V. */
695
696static void
697add_to_value (unsigned int v, pre_expr e)
698{
699 gcc_checking_assert (get_expr_value_id (e) == v)((void)(!(get_expr_value_id (e) == v) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 699, __FUNCTION__), 0 : 0))
;
700
701 if (value_id_constant_p (v))
702 {
703 if (e->kind != CONSTANT)
704 return;
705
706 if (-v >= constant_value_expressions.length ())
707 constant_value_expressions.safe_grow_cleared (-v + 1);
708
709 pre_expr leader = constant_value_expressions[-v];
710 if (!leader)
711 constant_value_expressions[-v] = e;
712 }
713 else
714 {
715 if (v >= value_expressions.length ())
716 value_expressions.safe_grow_cleared (v + 1);
717
718 bitmap set = value_expressions[v];
719 if (!set)
720 {
721 set = BITMAP_ALLOCbitmap_alloc (&grand_bitmap_obstack);
722 value_expressions[v] = set;
723 }
724 bitmap_set_bit (set, get_or_alloc_expression_id (e));
725 }
726}
727
728/* Create a new bitmap set and return it. */
729
730static bitmap_set_t
731bitmap_set_new (void)
732{
733 bitmap_set_t ret = bitmap_set_pool.allocate ();
734 bitmap_initialize (&ret->expressions, &grand_bitmap_obstack);
735 bitmap_initialize (&ret->values, &grand_bitmap_obstack);
736 return ret;
737}
738
739/* Return the value id for a PRE expression EXPR. */
740
741static unsigned int
742get_expr_value_id (pre_expr expr)
743{
744 /* ??? We cannot assert that expr has a value-id (it can be 0), because
745 we assign value-ids only to expressions that have a result
746 in set_hashtable_value_ids. */
747 return expr->value_id;
748}
749
750/* Return a VN valnum (SSA name or constant) for the PRE value-id VAL. */
751
752static tree
753vn_valnum_from_value_id (unsigned int val)
754{
755 if (value_id_constant_p (val))
756 {
757 pre_expr vexpr = constant_value_expressions[-val];
758 if (vexpr)
759 return PRE_EXPR_CONSTANT (vexpr)(vexpr)->u.constant;
760 return NULL_TREE(tree) nullptr;
761 }
762
763 bitmap exprset = value_expressions[val];
764 bitmap_iterator bi;
765 unsigned int i;
766 EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)for (bmp_iter_set_init (&(bi), (exprset), (0), &(i));
bmp_iter_set (&(bi), &(i)); bmp_iter_next (&(bi)
, &(i)))
767 {
768 pre_expr vexpr = expression_for_id (i);
769 if (vexpr->kind == NAME)
770 return VN_INFO (PRE_EXPR_NAME (vexpr)(vexpr)->u.name)->valnum;
771 }
772 return NULL_TREE(tree) nullptr;
773}
774
775/* Insert an expression EXPR into a bitmapped set. */
776
777static void
778bitmap_insert_into_set (bitmap_set_t set, pre_expr expr)
779{
780 unsigned int val = get_expr_value_id (expr);
781 if (! value_id_constant_p (val))
782 {
783 /* Note this is the only function causing multiple expressions
784 for the same value to appear in a set. This is needed for
785 TMP_GEN, PHI_GEN and NEW_SETs. */
786 bitmap_set_bit (&set->values, val);
787 bitmap_set_bit (&set->expressions, get_or_alloc_expression_id (expr));
788 }
789}
790
791/* Copy a bitmapped set ORIG, into bitmapped set DEST. */
792
793static void
794bitmap_set_copy (bitmap_set_t dest, bitmap_set_t orig)
795{
796 bitmap_copy (&dest->expressions, &orig->expressions);
797 bitmap_copy (&dest->values, &orig->values);
798}
799
800
801/* Free memory used up by SET. */
802static void
803bitmap_set_free (bitmap_set_t set)
804{
805 bitmap_clear (&set->expressions);
806 bitmap_clear (&set->values);
807}
808
809static void
810pre_expr_DFS (pre_expr expr, bitmap_set_t set, bitmap val_visited,
811 vec<pre_expr> &post);
812
813/* DFS walk leaders of VAL to their operands with leaders in SET, collecting
814 expressions in SET in postorder into POST. */
815
816static void
817pre_expr_DFS (unsigned val, bitmap_set_t set, bitmap val_visited,
818 vec<pre_expr> &post)
819{
820 unsigned int i;
821 bitmap_iterator bi;
822
823 /* Iterate over all leaders and DFS recurse. Borrowed from
824 bitmap_find_leader. */
825 bitmap exprset = value_expressions[val];
826 if (!exprset->first->next)
827 {
828 EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)for (bmp_iter_set_init (&(bi), (exprset), (0), &(i));
bmp_iter_set (&(bi), &(i)); bmp_iter_next (&(bi)
, &(i)))
829 if (bitmap_bit_p (&set->expressions, i))
830 pre_expr_DFS (expression_for_id (i), set, val_visited, post);
831 return;
832 }
833
834 EXECUTE_IF_AND_IN_BITMAP (exprset, &set->expressions, 0, i, bi)for (bmp_iter_and_init (&(bi), (exprset), (&set->expressions
), (0), &(i)); bmp_iter_and (&(bi), &(i)); bmp_iter_next
(&(bi), &(i)))
835 pre_expr_DFS (expression_for_id (i), set, val_visited, post);
836}
837
838/* DFS walk EXPR to its operands with leaders in SET, collecting
839 expressions in SET in postorder into POST. */
840
841static void
842pre_expr_DFS (pre_expr expr, bitmap_set_t set, bitmap val_visited,
843 vec<pre_expr> &post)
844{
845 switch (expr->kind)
846 {
847 case NARY:
848 {
849 vn_nary_op_t nary = PRE_EXPR_NARY (expr)(expr)->u.nary;
850 for (unsigned i = 0; i < nary->length; i++)
851 {
852 if (TREE_CODE (nary->op[i])((enum tree_code) (nary->op[i])->base.code) != SSA_NAME)
853 continue;
854 unsigned int op_val_id = VN_INFO (nary->op[i])->value_id;
855 /* If we already found a leader for the value we've
856 recursed already. Avoid the costly bitmap_find_leader. */
857 if (bitmap_bit_p (&set->values, op_val_id)
858 && bitmap_set_bit (val_visited, op_val_id))
859 pre_expr_DFS (op_val_id, set, val_visited, post);
860 }
861 break;
862 }
863 case REFERENCE:
864 {
865 vn_reference_t ref = PRE_EXPR_REFERENCE (expr)(expr)->u.reference;
866 vec<vn_reference_op_s> operands = ref->operands;
867 vn_reference_op_t operand;
868 for (unsigned i = 0; operands.iterate (i, &operand); i++)
869 {
870 tree op[3];
871 op[0] = operand->op0;
872 op[1] = operand->op1;
873 op[2] = operand->op2;
874 for (unsigned n = 0; n < 3; ++n)
875 {
876 if (!op[n] || TREE_CODE (op[n])((enum tree_code) (op[n])->base.code) != SSA_NAME)
877 continue;
878 unsigned op_val_id = VN_INFO (op[n])->value_id;
879 if (bitmap_bit_p (&set->values, op_val_id)
880 && bitmap_set_bit (val_visited, op_val_id))
881 pre_expr_DFS (op_val_id, set, val_visited, post);
882 }
883 }
884 break;
885 }
886 default:;
887 }
888 post.quick_push (expr);
889}
890
891/* Generate an topological-ordered array of bitmap set SET. */
892
893static vec<pre_expr>
894sorted_array_from_bitmap_set (bitmap_set_t set)
895{
896 unsigned int i;
897 bitmap_iterator bi;
898 vec<pre_expr> result;
899
900 /* Pre-allocate enough space for the array. */
901 result.create (bitmap_count_bits (&set->expressions));
902
903 auto_bitmap val_visited (&grand_bitmap_obstack);
904 bitmap_tree_view (val_visited);
905 FOR_EACH_VALUE_ID_IN_SET (set, i, bi)for (bmp_iter_set_init (&((bi)), (&(set)->values),
(0), &((i))); bmp_iter_set (&((bi)), &((i))); bmp_iter_next
(&((bi)), &((i))))
906 if (bitmap_set_bit (val_visited, i))
907 pre_expr_DFS (i, set, val_visited, result);
908
909 return result;
910}
911
912/* Subtract all expressions contained in ORIG from DEST. */
913
914static bitmap_set_t
915bitmap_set_subtract_expressions (bitmap_set_t dest, bitmap_set_t orig)
916{
917 bitmap_set_t result = bitmap_set_new ();
918 bitmap_iterator bi;
919 unsigned int i;
920
921 bitmap_and_compl (&result->expressions, &dest->expressions,
922 &orig->expressions);
923
924 FOR_EACH_EXPR_ID_IN_SET (result, i, bi)for (bmp_iter_set_init (&((bi)), (&(result)->expressions
), (0), &((i))); bmp_iter_set (&((bi)), &((i))); bmp_iter_next
(&((bi)), &((i))))
925 {
926 pre_expr expr = expression_for_id (i);
927 unsigned int value_id = get_expr_value_id (expr);
928 bitmap_set_bit (&result->values, value_id);
929 }
930
931 return result;
932}
933
934/* Subtract all values in bitmap set B from bitmap set A. */
935
936static void
937bitmap_set_subtract_values (bitmap_set_t a, bitmap_set_t b)
938{
939 unsigned int i;
940 bitmap_iterator bi;
941 unsigned to_remove = -1U;
942 bitmap_and_compl_into (&a->values, &b->values);
943 FOR_EACH_EXPR_ID_IN_SET (a, i, bi)for (bmp_iter_set_init (&((bi)), (&(a)->expressions
), (0), &((i))); bmp_iter_set (&((bi)), &((i))); bmp_iter_next
(&((bi)), &((i))))
944 {
945 if (to_remove != -1U)
946 {
947 bitmap_clear_bit (&a->expressions, to_remove);
948 to_remove = -1U;
949 }
950 pre_expr expr = expression_for_id (i);
951 if (! bitmap_bit_p (&a->values, get_expr_value_id (expr)))
952 to_remove = i;
953 }
954 if (to_remove != -1U)
955 bitmap_clear_bit (&a->expressions, to_remove);
956}
957
958
959/* Return true if bitmapped set SET contains the value VALUE_ID. */
960
961static bool
962bitmap_set_contains_value (bitmap_set_t set, unsigned int value_id)
963{
964 if (value_id_constant_p (value_id))
965 return true;
966
967 return bitmap_bit_p (&set->values, value_id);
968}
969
970/* Return true if two bitmap sets are equal. */
971
972static bool
973bitmap_set_equal (bitmap_set_t a, bitmap_set_t b)
974{
975 return bitmap_equal_p (&a->values, &b->values);
976}
977
978/* Replace an instance of EXPR's VALUE with EXPR in SET if it exists,
979 and add it otherwise. Return true if any changes were made. */
980
981static bool
982bitmap_value_replace_in_set (bitmap_set_t set, pre_expr expr)
983{
984 unsigned int val = get_expr_value_id (expr);
985 if (value_id_constant_p (val))
986 return false;
987
988 if (bitmap_set_contains_value (set, val))
989 {
990 /* The number of expressions having a given value is usually
991 significantly less than the total number of expressions in SET.
992 Thus, rather than check, for each expression in SET, whether it
993 has the value LOOKFOR, we walk the reverse mapping that tells us
994 what expressions have a given value, and see if any of those
995 expressions are in our set. For large testcases, this is about
996 5-10x faster than walking the bitmap. If this is somehow a
997 significant lose for some cases, we can choose which set to walk
998 based on the set size. */
999 unsigned int i;
1000 bitmap_iterator bi;
1001 bitmap exprset = value_expressions[val];
1002 EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)for (bmp_iter_set_init (&(bi), (exprset), (0), &(i));
bmp_iter_set (&(bi), &(i)); bmp_iter_next (&(bi)
, &(i)))
1003 {
1004 if (bitmap_clear_bit (&set->expressions, i))
1005 {
1006 bitmap_set_bit (&set->expressions, get_expression_id (expr));
1007 return i != get_expression_id (expr);
1008 }
1009 }
1010 gcc_unreachable ()(fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 1010, __FUNCTION__))
;
1011 }
1012
1013 bitmap_insert_into_set (set, expr);
1014 return true;
1015}
1016
1017/* Insert EXPR into SET if EXPR's value is not already present in
1018 SET. */
1019
1020static void
1021bitmap_value_insert_into_set (bitmap_set_t set, pre_expr expr)
1022{
1023 unsigned int val = get_expr_value_id (expr);
1024
1025 gcc_checking_assert (expr->id == get_or_alloc_expression_id (expr))((void)(!(expr->id == get_or_alloc_expression_id (expr)) ?
fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 1025, __FUNCTION__), 0 : 0))
;
1026
1027 /* Constant values are always considered to be part of the set. */
1028 if (value_id_constant_p (val))
1029 return;
1030
1031 /* If the value membership changed, add the expression. */
1032 if (bitmap_set_bit (&set->values, val))
1033 bitmap_set_bit (&set->expressions, expr->id);
1034}
1035
1036/* Print out EXPR to outfile. */
1037
1038static void
1039print_pre_expr (FILE *outfile, const pre_expr expr)
1040{
1041 if (! expr)
1042 {
1043 fprintf (outfile, "NULL");
1044 return;
1045 }
1046 switch (expr->kind)
1047 {
1048 case CONSTANT:
1049 print_generic_expr (outfile, PRE_EXPR_CONSTANT (expr)(expr)->u.constant);
1050 break;
1051 case NAME:
1052 print_generic_expr (outfile, PRE_EXPR_NAME (expr)(expr)->u.name);
1053 break;
1054 case NARY:
1055 {
1056 unsigned int i;
1057 vn_nary_op_t nary = PRE_EXPR_NARY (expr)(expr)->u.nary;
1058 fprintf (outfile, "{%s,", get_tree_code_name (nary->opcode));
1059 for (i = 0; i < nary->length; i++)
1060 {
1061 print_generic_expr (outfile, nary->op[i]);
1062 if (i != (unsigned) nary->length - 1)
1063 fprintf (outfile, ",");
1064 }
1065 fprintf (outfile, "}");
1066 }
1067 break;
1068
1069 case REFERENCE:
1070 {
1071 vn_reference_t ref = PRE_EXPR_REFERENCE (expr)(expr)->u.reference;
1072 print_vn_reference_ops (outfile, ref->operands);
1073 if (ref->vuse)
1074 {
1075 fprintf (outfile, "@");
1076 print_generic_expr (outfile, ref->vuse);
1077 }
1078 }
1079 break;
1080 }
1081}
1082void debug_pre_expr (pre_expr);
1083
1084/* Like print_pre_expr but always prints to stderr. */
1085DEBUG_FUNCTION__attribute__ ((__used__)) void
1086debug_pre_expr (pre_expr e)
1087{
1088 print_pre_expr (stderrstderr, e);
1089 fprintf (stderrstderr, "\n");
1090}
1091
1092/* Print out SET to OUTFILE. */
1093
1094static void
1095print_bitmap_set (FILE *outfile, bitmap_set_t set,
1096 const char *setname, int blockindex)
1097{
1098 fprintf (outfile, "%s[%d] := { ", setname, blockindex);
1099 if (set)
1100 {
1101 bool first = true;
1102 unsigned i;
1103 bitmap_iterator bi;
1104
1105 FOR_EACH_EXPR_ID_IN_SET (set, i, bi)for (bmp_iter_set_init (&((bi)), (&(set)->expressions
), (0), &((i))); bmp_iter_set (&((bi)), &((i))); bmp_iter_next
(&((bi)), &((i))))
1106 {
1107 const pre_expr expr = expression_for_id (i);
1108
1109 if (!first)
1110 fprintf (outfile, ", ");
1111 first = false;
1112 print_pre_expr (outfile, expr);
1113
1114 fprintf (outfile, " (%04d)", get_expr_value_id (expr));
1115 }
1116 }
1117 fprintf (outfile, " }\n");
1118}
1119
1120void debug_bitmap_set (bitmap_set_t);
1121
1122DEBUG_FUNCTION__attribute__ ((__used__)) void
1123debug_bitmap_set (bitmap_set_t set)
1124{
1125 print_bitmap_set (stderrstderr, set, "debug", 0);
1126}
1127
1128void debug_bitmap_sets_for (basic_block);
1129
1130DEBUG_FUNCTION__attribute__ ((__used__)) void
1131debug_bitmap_sets_for (basic_block bb)
1132{
1133 print_bitmap_set (stderrstderr, AVAIL_OUT (bb)((bb_value_sets_t) ((bb)->aux))->avail_out, "avail_out", bb->index);
1134 print_bitmap_set (stderrstderr, EXP_GEN (bb)((bb_value_sets_t) ((bb)->aux))->exp_gen, "exp_gen", bb->index);
1135 print_bitmap_set (stderrstderr, PHI_GEN (bb)((bb_value_sets_t) ((bb)->aux))->phi_gen, "phi_gen", bb->index);
1136 print_bitmap_set (stderrstderr, TMP_GEN (bb)((bb_value_sets_t) ((bb)->aux))->tmp_gen, "tmp_gen", bb->index);
1137 print_bitmap_set (stderrstderr, ANTIC_IN (bb)((bb_value_sets_t) ((bb)->aux))->antic_in, "antic_in", bb->index);
1138 if (do_partial_partial)
1139 print_bitmap_set (stderrstderr, PA_IN (bb)((bb_value_sets_t) ((bb)->aux))->pa_in, "pa_in", bb->index);
1140 print_bitmap_set (stderrstderr, NEW_SETS (bb)((bb_value_sets_t) ((bb)->aux))->new_sets, "new_sets", bb->index);
1141}
1142
1143/* Print out the expressions that have VAL to OUTFILE. */
1144
1145static void
1146print_value_expressions (FILE *outfile, unsigned int val)
1147{
1148 bitmap set = value_expressions[val];
1149 if (set)
1150 {
1151 bitmap_set x;
1152 char s[10];
1153 sprintf (s, "%04d", val);
1154 x.expressions = *set;
1155 print_bitmap_set (outfile, &x, s, 0);
1156 }
1157}
1158
1159
1160DEBUG_FUNCTION__attribute__ ((__used__)) void
1161debug_value_expressions (unsigned int val)
1162{
1163 print_value_expressions (stderrstderr, val);
1164}
1165
1166/* Given a CONSTANT, allocate a new CONSTANT type PRE_EXPR to
1167 represent it. */
1168
1169static pre_expr
1170get_or_alloc_expr_for_constant (tree constant)
1171{
1172 unsigned int result_id;
1173 struct pre_expr_d expr;
1174 pre_expr newexpr;
1175
1176 expr.kind = CONSTANT;
1177 PRE_EXPR_CONSTANT (&expr)(&expr)->u.constant = constant;
1178 result_id = lookup_expression_id (&expr);
1179 if (result_id != 0)
1180 return expression_for_id (result_id);
1181
1182 newexpr = pre_expr_pool.allocate ();
1183 newexpr->kind = CONSTANT;
1184 newexpr->loc = UNKNOWN_LOCATION((location_t) 0);
1185 PRE_EXPR_CONSTANT (newexpr)(newexpr)->u.constant = constant;
1186 alloc_expression_id (newexpr);
1187 newexpr->value_id = get_or_alloc_constant_value_id (constant);
1188 add_to_value (newexpr->value_id, newexpr);
1189 return newexpr;
1190}
1191
1192/* Get or allocate a pre_expr for a piece of GIMPLE, and return it.
1193 Currently only supports constants and SSA_NAMES. */
1194static pre_expr
1195get_or_alloc_expr_for (tree t)
1196{
1197 if (TREE_CODE (t)((enum tree_code) (t)->base.code) == SSA_NAME)
1198 return get_or_alloc_expr_for_name (t);
1199 else if (is_gimple_min_invariant (t))
1200 return get_or_alloc_expr_for_constant (t);
1201 gcc_unreachable ()(fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 1201, __FUNCTION__))
;
1202}
1203
1204/* Return the folded version of T if T, when folded, is a gimple
1205 min_invariant or an SSA name. Otherwise, return T. */
1206
1207static pre_expr
1208fully_constant_expression (pre_expr e)
1209{
1210 switch (e->kind)
1211 {
1212 case CONSTANT:
1213 return e;
1214 case NARY:
1215 {
1216 vn_nary_op_t nary = PRE_EXPR_NARY (e)(e)->u.nary;
1217 tree res = vn_nary_simplify (nary);
1218 if (!res)
1219 return e;
1220 if (is_gimple_min_invariant (res))
1221 return get_or_alloc_expr_for_constant (res);
1222 if (TREE_CODE (res)((enum tree_code) (res)->base.code) == SSA_NAME)
1223 return get_or_alloc_expr_for_name (res);
1224 return e;
1225 }
1226 case REFERENCE:
1227 {
1228 vn_reference_t ref = PRE_EXPR_REFERENCE (e)(e)->u.reference;
1229 tree folded;
1230 if ((folded = fully_constant_vn_reference_p (ref)))
1231 return get_or_alloc_expr_for_constant (folded);
1232 return e;
1233 }
1234 default:
1235 return e;
1236 }
1237 return e;
1238}
1239
1240/* Translate the VUSE backwards through phi nodes in E->dest, so that
1241 it has the value it would have in E->src. Set *SAME_VALID to true
1242 in case the new vuse doesn't change the value id of the OPERANDS. */
1243
1244static tree
1245translate_vuse_through_block (vec<vn_reference_op_s> operands,
1246 alias_set_type set, alias_set_type base_set,
1247 tree type, tree vuse, edge e, bool *same_valid)
1248{
1249 basic_block phiblock = e->dest;
1250 gimple *phi = SSA_NAME_DEF_STMT (vuse)(tree_check ((vuse), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 1250, __FUNCTION__, (SSA_NAME)))->ssa_name.def_stmt
;
1251 ao_ref ref;
1252
1253 if (same_valid)
1254 *same_valid = true;
1255
1256 if (gimple_bb (phi) != phiblock)
1257 return vuse;
1258
1259 /* We have pruned expressions that are killed in PHIBLOCK via
1260 prune_clobbered_mems but we have not rewritten the VUSE to the one
1261 live at the start of the block. If there is no virtual PHI to translate
1262 through return the VUSE live at entry. Otherwise the VUSE to translate
1263 is the def of the virtual PHI node. */
1264 phi = get_virtual_phi (phiblock);
1265 if (!phi)
1266 return BB_LIVE_VOP_ON_EXIT((bb_value_sets_t) ((get_immediate_dominator (CDI_DOMINATORS,
phiblock))->aux))->vop_on_exit
1267 (get_immediate_dominator (CDI_DOMINATORS, phiblock))((bb_value_sets_t) ((get_immediate_dominator (CDI_DOMINATORS,
phiblock))->aux))->vop_on_exit
;
1268
1269 if (same_valid
1270 && ao_ref_init_from_vn_reference (&ref, set, base_set, type, operands))
1271 {
1272 bitmap visited = NULLnullptr;
1273 /* Try to find a vuse that dominates this phi node by skipping
1274 non-clobbering statements. */
1275 unsigned int cnt = param_sccvn_max_alias_queries_per_accessglobal_options.x_param_sccvn_max_alias_queries_per_access;
1276 vuse = get_continuation_for_phi (phi, &ref, true,
1277 cnt, &visited, false, NULLnullptr, NULLnullptr);
1278 if (visited)
1279 BITMAP_FREE (visited)((void) (bitmap_obstack_free ((bitmap) visited), (visited) = (
bitmap) nullptr))
;
1280 }
1281 else
1282 vuse = NULL_TREE(tree) nullptr;
1283 /* If we didn't find any, the value ID can't stay the same. */
1284 if (!vuse && same_valid)
1285 *same_valid = false;
1286
1287 /* ??? We would like to return vuse here as this is the canonical
1288 upmost vdef that this reference is associated with. But during
1289 insertion of the references into the hash tables we only ever
1290 directly insert with their direct gimple_vuse, hence returning
1291 something else would make us not find the other expression. */
1292 return PHI_ARG_DEF (phi, e->dest_idx)gimple_phi_arg_def ((phi), (e->dest_idx));
1293}
1294
1295/* Like bitmap_find_leader, but checks for the value existing in SET1 *or*
1296 SET2 *or* SET3. This is used to avoid making a set consisting of the union
1297 of PA_IN and ANTIC_IN during insert and phi-translation. */
1298
1299static inline pre_expr
1300find_leader_in_sets (unsigned int val, bitmap_set_t set1, bitmap_set_t set2,
1301 bitmap_set_t set3 = NULLnullptr)
1302{
1303 pre_expr result = NULLnullptr;
1304
1305 if (set1)
1306 result = bitmap_find_leader (set1, val);
1307 if (!result && set2)
1308 result = bitmap_find_leader (set2, val);
1309 if (!result && set3)
1310 result = bitmap_find_leader (set3, val);
1311 return result;
1312}
1313
1314/* Get the tree type for our PRE expression e. */
1315
1316static tree
1317get_expr_type (const pre_expr e)
1318{
1319 switch (e->kind)
1320 {
1321 case NAME:
1322 return TREE_TYPE (PRE_EXPR_NAME (e))((contains_struct_check (((e)->u.name), (TS_TYPED), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 1322, __FUNCTION__))->typed.type)
;
1323 case CONSTANT:
1324 return TREE_TYPE (PRE_EXPR_CONSTANT (e))((contains_struct_check (((e)->u.constant), (TS_TYPED), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 1324, __FUNCTION__))->typed.type)
;
1325 case REFERENCE:
1326 return PRE_EXPR_REFERENCE (e)(e)->u.reference->type;
1327 case NARY:
1328 return PRE_EXPR_NARY (e)(e)->u.nary->type;
1329 }
1330 gcc_unreachable ()(fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 1330, __FUNCTION__))
;
1331}
1332
1333/* Get a representative SSA_NAME for a given expression that is available in B.
1334 Since all of our sub-expressions are treated as values, we require
1335 them to be SSA_NAME's for simplicity.
1336 Prior versions of GVNPRE used to use "value handles" here, so that
1337 an expression would be VH.11 + VH.10 instead of d_3 + e_6. In
1338 either case, the operands are really values (IE we do not expect
1339 them to be usable without finding leaders). */
1340
1341static tree
1342get_representative_for (const pre_expr e, basic_block b = NULLnullptr)
1343{
1344 tree name, valnum = NULL_TREE(tree) nullptr;
1345 unsigned int value_id = get_expr_value_id (e);
1346
1347 switch (e->kind)
1348 {
1349 case NAME:
1350 return PRE_EXPR_NAME (e)(e)->u.name;
1351 case CONSTANT:
1352 return PRE_EXPR_CONSTANT (e)(e)->u.constant;
1353 case NARY:
1354 case REFERENCE:
1355 {
1356 /* Go through all of the expressions representing this value
1357 and pick out an SSA_NAME. */
1358 unsigned int i;
1359 bitmap_iterator bi;
1360 bitmap exprs = value_expressions[value_id];
1361 EXECUTE_IF_SET_IN_BITMAP (exprs, 0, i, bi)for (bmp_iter_set_init (&(bi), (exprs), (0), &(i)); bmp_iter_set
(&(bi), &(i)); bmp_iter_next (&(bi), &(i)))
1362 {
1363 pre_expr rep = expression_for_id (i);
1364 if (rep->kind == NAME)
1365 {
1366 tree name = PRE_EXPR_NAME (rep)(rep)->u.name;
1367 valnum = VN_INFO (name)->valnum;
1368 gimple *def = SSA_NAME_DEF_STMT (name)(tree_check ((name), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 1368, __FUNCTION__, (SSA_NAME)))->ssa_name.def_stmt
;
1369 /* We have to return either a new representative or one
1370 that can be used for expression simplification and thus
1371 is available in B. */
1372 if (! b
1373 || gimple_nop_p (def)
1374 || dominated_by_p (CDI_DOMINATORS, b, gimple_bb (def)))
1375 return name;
1376 }
1377 else if (rep->kind == CONSTANT)
1378 return PRE_EXPR_CONSTANT (rep)(rep)->u.constant;
1379 }
1380 }
1381 break;
1382 }
1383
1384 /* If we reached here we couldn't find an SSA_NAME. This can
1385 happen when we've discovered a value that has never appeared in
1386 the program as set to an SSA_NAME, as the result of phi translation.
1387 Create one here.
1388 ??? We should be able to re-use this when we insert the statement
1389 to compute it. */
1390 name = make_temp_ssa_name (get_expr_type (e), gimple_build_nop (), "pretmp");
1391 vn_ssa_aux_t vn_info = VN_INFO (name);
1392 vn_info->value_id = value_id;
1393 vn_info->valnum = valnum ? valnum : name;
1394 vn_info->visited = true;
1395 /* ??? For now mark this SSA name for release by VN. */
1396 vn_info->needs_insertion = true;
1397 add_to_value (value_id, get_or_alloc_expr_for_name (name));
1398 if (dump_file && (dump_flags & TDF_DETAILS))
1399 {
1400 fprintf (dump_file, "Created SSA_NAME representative ");
1401 print_generic_expr (dump_file, name);
1402 fprintf (dump_file, " for expression:");
1403 print_pre_expr (dump_file, e);
1404 fprintf (dump_file, " (%04d)\n", value_id);
1405 }
1406
1407 return name;
1408}
1409
1410
1411static pre_expr
1412phi_translate (bitmap_set_t, pre_expr, bitmap_set_t, bitmap_set_t, edge);
1413
1414/* Translate EXPR using phis in PHIBLOCK, so that it has the values of
1415 the phis in PRED. Return NULL if we can't find a leader for each part
1416 of the translated expression. */
1417
1418static pre_expr
1419phi_translate_1 (bitmap_set_t dest,
1420 pre_expr expr, bitmap_set_t set1, bitmap_set_t set2, edge e)
1421{
1422 basic_block pred = e->src;
1423 basic_block phiblock = e->dest;
1424 location_t expr_loc = expr->loc;
1425 switch (expr->kind)
1426 {
1427 case NARY:
1428 {
1429 unsigned int i;
1430 bool changed = false;
1431 vn_nary_op_t nary = PRE_EXPR_NARY (expr)(expr)->u.nary;
1432 vn_nary_op_t newnary = XALLOCAVAR (struct vn_nary_op_s,((struct vn_nary_op_s *) __builtin_alloca((sizeof_vn_nary_op (
nary->length))))
1433 sizeof_vn_nary_op (nary->length))((struct vn_nary_op_s *) __builtin_alloca((sizeof_vn_nary_op (
nary->length))))
;
1434 memcpy (newnary, nary, sizeof_vn_nary_op (nary->length));
1435
1436 for (i = 0; i < newnary->length; i++)
1437 {
1438 if (TREE_CODE (newnary->op[i])((enum tree_code) (newnary->op[i])->base.code) != SSA_NAME)
1439 continue;
1440 else
1441 {
1442 pre_expr leader, result;
1443 unsigned int op_val_id = VN_INFO (newnary->op[i])->value_id;
1444 leader = find_leader_in_sets (op_val_id, set1, set2);
1445 result = phi_translate (dest, leader, set1, set2, e);
1446 if (result && result != leader)
1447 /* If op has a leader in the sets we translate make
1448 sure to use the value of the translated expression.
1449 We might need a new representative for that. */
1450 newnary->op[i] = get_representative_for (result, pred);
1451 else if (!result)
1452 return NULLnullptr;
1453
1454 changed |= newnary->op[i] != nary->op[i];
1455 }
1456 }
1457 if (changed)
1458 {
1459 pre_expr constant;
1460 unsigned int new_val_id;
1461
1462 PRE_EXPR_NARY (expr)(expr)->u.nary = newnary;
1463 constant = fully_constant_expression (expr);
1464 PRE_EXPR_NARY (expr)(expr)->u.nary = nary;
1465 if (constant != expr)
1466 {
1467 /* For non-CONSTANTs we have to make sure we can eventually
1468 insert the expression. Which means we need to have a
1469 leader for it. */
1470 if (constant->kind != CONSTANT)
1471 {
1472 /* Do not allow simplifications to non-constants over
1473 backedges as this will likely result in a loop PHI node
1474 to be inserted and increased register pressure.
1475 See PR77498 - this avoids doing predcoms work in
1476 a less efficient way. */
1477 if (e->flags & EDGE_DFS_BACK)
1478 ;
1479 else
1480 {
1481 unsigned value_id = get_expr_value_id (constant);
1482 /* We want a leader in ANTIC_OUT or AVAIL_OUT here.
1483 dest has what we computed into ANTIC_OUT sofar
1484 so pick from that - since topological sorting
1485 by sorted_array_from_bitmap_set isn't perfect
1486 we may lose some cases here. */
1487 constant = find_leader_in_sets (value_id, dest,
1488 AVAIL_OUT (pred)((bb_value_sets_t) ((pred)->aux))->avail_out);
1489 if (constant)
1490 {
1491 if (dump_file && (dump_flags & TDF_DETAILS))
1492 {
1493 fprintf (dump_file, "simplifying ");
1494 print_pre_expr (dump_file, expr);
1495 fprintf (dump_file, " translated %d -> %d to ",
1496 phiblock->index, pred->index);
1497 PRE_EXPR_NARY (expr)(expr)->u.nary = newnary;
1498 print_pre_expr (dump_file, expr);
1499 PRE_EXPR_NARY (expr)(expr)->u.nary = nary;
1500 fprintf (dump_file, " to ");
1501 print_pre_expr (dump_file, constant);
1502 fprintf (dump_file, "\n");
1503 }
1504 return constant;
1505 }
1506 }
1507 }
1508 else
1509 return constant;
1510 }
1511
1512 tree result = vn_nary_op_lookup_pieces (newnary->length,
1513 newnary->opcode,
1514 newnary->type,
1515 &newnary->op[0],
1516 &nary);
1517 if (result && is_gimple_min_invariant (result))
1518 return get_or_alloc_expr_for_constant (result);
1519
1520 if (!nary || nary->predicated_values)
1521 {
1522 new_val_id = get_next_value_id ();
1523 nary = vn_nary_op_insert_pieces (newnary->length,
1524 newnary->opcode,
1525 newnary->type,
1526 &newnary->op[0],
1527 result, new_val_id);
1528 }
1529 expr = get_or_alloc_expr_for_nary (nary, expr_loc);
1530 add_to_value (get_expr_value_id (expr), expr);
1531 }
1532 return expr;
1533 }
1534 break;
1535
1536 case REFERENCE:
1537 {
1538 vn_reference_t ref = PRE_EXPR_REFERENCE (expr)(expr)->u.reference;
1539 vec<vn_reference_op_s> operands = ref->operands;
1540 tree vuse = ref->vuse;
1541 tree newvuse = vuse;
1542 vec<vn_reference_op_s> newoperands = vNULL;
1543 bool changed = false, same_valid = true;
1544 unsigned int i, n;
1545 vn_reference_op_t operand;
1546 vn_reference_t newref;
1547
1548 for (i = 0; operands.iterate (i, &operand); i++)
1549 {
1550 pre_expr opresult;
1551 pre_expr leader;
1552 tree op[3];
1553 tree type = operand->type;
1554 vn_reference_op_s newop = *operand;
1555 op[0] = operand->op0;
1556 op[1] = operand->op1;
1557 op[2] = operand->op2;
1558 for (n = 0; n < 3; ++n)
1559 {
1560 unsigned int op_val_id;
1561 if (!op[n])
1562 continue;
1563 if (TREE_CODE (op[n])((enum tree_code) (op[n])->base.code) != SSA_NAME)
1564 {
1565 /* We can't possibly insert these. */
1566 if (n != 0
1567 && !is_gimple_min_invariant (op[n]))
1568 break;
1569 continue;
1570 }
1571 op_val_id = VN_INFO (op[n])->value_id;
1572 leader = find_leader_in_sets (op_val_id, set1, set2);
1573 opresult = phi_translate (dest, leader, set1, set2, e);
1574 if (opresult && opresult != leader)
1575 {
1576 tree name = get_representative_for (opresult);
1577 changed |= name != op[n];
1578 op[n] = name;
1579 }
1580 else if (!opresult)
1581 break;
1582 }
1583 if (n != 3)
1584 {
1585 newoperands.release ();
1586 return NULLnullptr;
1587 }
1588 /* When we translate a MEM_REF across a backedge and we have
1589 restrict info that's not from our functions parameters
1590 we have to remap it since we now may deal with a different
1591 instance where the dependence info is no longer valid.
1592 See PR102970. Note instead of keeping a remapping table
1593 per backedge we simply throw away restrict info. */
1594 if ((newop.opcode == MEM_REF
1595 || newop.opcode == TARGET_MEM_REF)
1596 && newop.clique > 1
1597 && (e->flags & EDGE_DFS_BACK))
1598 {
1599 newop.clique = 0;
1600 newop.base = 0;
1601 changed = true;
1602 }
1603 if (!changed)
1604 continue;
1605 if (!newoperands.exists ())
1606 newoperands = operands.copy ();
1607 /* We may have changed from an SSA_NAME to a constant */
1608 if (newop.opcode == SSA_NAME && TREE_CODE (op[0])((enum tree_code) (op[0])->base.code) != SSA_NAME)
1609 newop.opcode = TREE_CODE (op[0])((enum tree_code) (op[0])->base.code);
1610 newop.type = type;
1611 newop.op0 = op[0];
1612 newop.op1 = op[1];
1613 newop.op2 = op[2];
1614 newoperands[i] = newop;
1615 }
1616 gcc_checking_assert (i == operands.length ())((void)(!(i == operands.length ()) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 1616, __FUNCTION__), 0 : 0))
;
1617
1618 if (vuse)
1619 {
1620 newvuse = translate_vuse_through_block (newoperands.exists ()
1621 ? newoperands : operands,
1622 ref->set, ref->base_set,
1623 ref->type, vuse, e,
1624 changed
1625 ? NULLnullptr : &same_valid);
1626 if (newvuse == NULL_TREE(tree) nullptr)
1627 {
1628 newoperands.release ();
1629 return NULLnullptr;
1630 }
1631 }
1632
1633 if (changed || newvuse != vuse)
1634 {
1635 unsigned int new_val_id;
1636
1637 tree result = vn_reference_lookup_pieces (newvuse, ref->set,
1638 ref->base_set,
1639 ref->type,
1640 newoperands.exists ()
1641 ? newoperands : operands,
1642 &newref, VN_WALK);
1643 if (result)
1644 newoperands.release ();
1645
1646 /* We can always insert constants, so if we have a partial
1647 redundant constant load of another type try to translate it
1648 to a constant of appropriate type. */
1649 if (result && is_gimple_min_invariant (result))
1650 {
1651 tree tem = result;
1652 if (!useless_type_conversion_p (ref->type, TREE_TYPE (result)((contains_struct_check ((result), (TS_TYPED), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 1652, __FUNCTION__))->typed.type)
))
1653 {
1654 tem = fold_unary (VIEW_CONVERT_EXPR, ref->type, result)fold_unary_loc (((location_t) 0), VIEW_CONVERT_EXPR, ref->
type, result)
;
1655 if (tem && !is_gimple_min_invariant (tem))
1656 tem = NULL_TREE(tree) nullptr;
1657 }
1658 if (tem)
1659 return get_or_alloc_expr_for_constant (tem);
1660 }
1661
1662 /* If we'd have to convert things we would need to validate
1663 if we can insert the translated expression. So fail
1664 here for now - we cannot insert an alias with a different
1665 type in the VN tables either, as that would assert. */
1666 if (result
1667 && !useless_type_conversion_p (ref->type, TREE_TYPE (result)((contains_struct_check ((result), (TS_TYPED), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 1667, __FUNCTION__))->typed.type)
))
1668 return NULLnullptr;
1669 else if (!result && newref
1670 && !useless_type_conversion_p (ref->type, newref->type))
1671 {
1672 newoperands.release ();
1673 return NULLnullptr;
1674 }
1675
1676 if (newref)
1677 new_val_id = newref->value_id;
1678 else
1679 {
1680 if (changed || !same_valid)
1681 new_val_id = get_next_value_id ();
1682 else
1683 new_val_id = ref->value_id;
1684 if (!newoperands.exists ())
1685 newoperands = operands.copy ();
1686 newref = vn_reference_insert_pieces (newvuse, ref->set,
1687 ref->base_set, ref->type,
1688 newoperands,
1689 result, new_val_id);
1690 newoperands = vNULL;
1691 }
1692 expr = get_or_alloc_expr_for_reference (newref, expr_loc);
1693 add_to_value (new_val_id, expr);
1694 }
1695 newoperands.release ();
1696 return expr;
1697 }
1698 break;
1699
1700 case NAME:
1701 {
1702 tree name = PRE_EXPR_NAME (expr)(expr)->u.name;
1703 gimple *def_stmt = SSA_NAME_DEF_STMT (name)(tree_check ((name), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 1703, __FUNCTION__, (SSA_NAME)))->ssa_name.def_stmt
;
1704 /* If the SSA name is defined by a PHI node in this block,
1705 translate it. */
1706 if (gimple_code (def_stmt) == GIMPLE_PHI
1707 && gimple_bb (def_stmt) == phiblock)
1708 {
1709 tree def = PHI_ARG_DEF (def_stmt, e->dest_idx)gimple_phi_arg_def ((def_stmt), (e->dest_idx));
1710
1711 /* Handle constant. */
1712 if (is_gimple_min_invariant (def))
1713 return get_or_alloc_expr_for_constant (def);
1714
1715 return get_or_alloc_expr_for_name (def);
1716 }
1717 /* Otherwise return it unchanged - it will get removed if its
1718 value is not available in PREDs AVAIL_OUT set of expressions
1719 by the subtraction of TMP_GEN. */
1720 return expr;
1721 }
1722
1723 default:
1724 gcc_unreachable ()(fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 1724, __FUNCTION__))
;
1725 }
1726}
1727
1728/* Wrapper around phi_translate_1 providing caching functionality. */
1729
1730static pre_expr
1731phi_translate (bitmap_set_t dest, pre_expr expr,
1732 bitmap_set_t set1, bitmap_set_t set2, edge e)
1733{
1734 expr_pred_trans_t slot = NULLnullptr;
1735 pre_expr phitrans;
1736
1737 if (!expr)
1738 return NULLnullptr;
1739
1740 /* Constants contain no values that need translation. */
1741 if (expr->kind == CONSTANT)
1742 return expr;
1743
1744 if (value_id_constant_p (get_expr_value_id (expr)))
1745 return expr;
1746
1747 /* Don't add translations of NAMEs as those are cheap to translate. */
1748 if (expr->kind != NAME)
1749 {
1750 if (phi_trans_add (&slot, expr, e->src))
1751 return slot->v == 0 ? NULLnullptr : expression_for_id (slot->v);
1752 /* Store NULL for the value we want to return in the case of
1753 recursing. */
1754 slot->v = 0;
1755 }
1756
1757 /* Translate. */
1758 basic_block saved_valueize_bb = vn_context_bb;
1759 vn_context_bb = e->src;
1760 phitrans = phi_translate_1 (dest, expr, set1, set2, e);
1761 vn_context_bb = saved_valueize_bb;
1762
1763 if (slot)
1764 {
1765 /* We may have reallocated. */
1766 phi_trans_add (&slot, expr, e->src);
1767 if (phitrans)
1768 slot->v = get_expression_id (phitrans);
1769 else
1770 /* Remove failed translations again, they cause insert
1771 iteration to not pick up new opportunities reliably. */
1772 PHI_TRANS_TABLE (e->src)((bb_value_sets_t) ((e->src)->aux))->phi_translate_table->clear_slot (slot);
1773 }
1774
1775 return phitrans;
1776}
1777
1778
1779/* For each expression in SET, translate the values through phi nodes
1780 in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting
1781 expressions in DEST. */
1782
1783static void
1784phi_translate_set (bitmap_set_t dest, bitmap_set_t set, edge e)
1785{
1786 bitmap_iterator bi;
1787 unsigned int i;
1788
1789 if (gimple_seq_empty_p (phi_nodes (e->dest)))
1790 {
1791 bitmap_set_copy (dest, set);
1792 return;
1793 }
1794
1795 /* Allocate the phi-translation cache where we have an idea about
1796 its size. hash-table implementation internals tell us that
1797 allocating the table to fit twice the number of elements will
1798 make sure we do not usually re-allocate. */
1799 if (!PHI_TRANS_TABLE (e->src)((bb_value_sets_t) ((e->src)->aux))->phi_translate_table)
1800 PHI_TRANS_TABLE (e->src)((bb_value_sets_t) ((e->src)->aux))->phi_translate_table = new hash_table<expr_pred_trans_d>
1801 (2 * bitmap_count_bits (&set->expressions));
1802 FOR_EACH_EXPR_ID_IN_SET (set, i, bi)for (bmp_iter_set_init (&((bi)), (&(set)->expressions
), (0), &((i))); bmp_iter_set (&((bi)), &((i))); bmp_iter_next
(&((bi)), &((i))))
1803 {
1804 pre_expr expr = expression_for_id (i);
1805 pre_expr translated = phi_translate (dest, expr, set, NULLnullptr, e);
1806 if (!translated)
1807 continue;
1808
1809 bitmap_insert_into_set (dest, translated);
1810 }
1811}
1812
1813/* Find the leader for a value (i.e., the name representing that
1814 value) in a given set, and return it. Return NULL if no leader
1815 is found. */
1816
1817static pre_expr
1818bitmap_find_leader (bitmap_set_t set, unsigned int val)
1819{
1820 if (value_id_constant_p (val))
1821 return constant_value_expressions[-val];
1822
1823 if (bitmap_set_contains_value (set, val))
1824 {
1825 /* Rather than walk the entire bitmap of expressions, and see
1826 whether any of them has the value we are looking for, we look
1827 at the reverse mapping, which tells us the set of expressions
1828 that have a given value (IE value->expressions with that
1829 value) and see if any of those expressions are in our set.
1830 The number of expressions per value is usually significantly
1831 less than the number of expressions in the set. In fact, for
1832 large testcases, doing it this way is roughly 5-10x faster
1833 than walking the bitmap.
1834 If this is somehow a significant lose for some cases, we can
1835 choose which set to walk based on which set is smaller. */
1836 unsigned int i;
1837 bitmap_iterator bi;
1838 bitmap exprset = value_expressions[val];
1839
1840 if (!exprset->first->next)
1841 EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)for (bmp_iter_set_init (&(bi), (exprset), (0), &(i));
bmp_iter_set (&(bi), &(i)); bmp_iter_next (&(bi)
, &(i)))
1842 if (bitmap_bit_p (&set->expressions, i))
1843 return expression_for_id (i);
1844
1845 EXECUTE_IF_AND_IN_BITMAP (exprset, &set->expressions, 0, i, bi)for (bmp_iter_and_init (&(bi), (exprset), (&set->expressions
), (0), &(i)); bmp_iter_and (&(bi), &(i)); bmp_iter_next
(&(bi), &(i)))
1846 return expression_for_id (i);
1847 }
1848 return NULLnullptr;
1849}
1850
1851/* Determine if EXPR, a memory expression, is ANTIC_IN at the top of
1852 BLOCK by seeing if it is not killed in the block. Note that we are
1853 only determining whether there is a store that kills it. Because
1854 of the order in which clean iterates over values, we are guaranteed
1855 that altered operands will have caused us to be eliminated from the
1856 ANTIC_IN set already. */
1857
1858static bool
1859value_dies_in_block_x (pre_expr expr, basic_block block)
1860{
1861 tree vuse = PRE_EXPR_REFERENCE (expr)(expr)->u.reference->vuse;
1862 vn_reference_t refx = PRE_EXPR_REFERENCE (expr)(expr)->u.reference;
1863 gimple *def;
1864 gimple_stmt_iterator gsi;
1865 unsigned id = get_expression_id (expr);
1866 bool res = false;
1867 ao_ref ref;
1868
1869 if (!vuse)
1870 return false;
1871
1872 /* Lookup a previously calculated result. */
1873 if (EXPR_DIES (block)((bb_value_sets_t) ((block)->aux))->expr_dies
1874 && bitmap_bit_p (EXPR_DIES (block)((bb_value_sets_t) ((block)->aux))->expr_dies, id * 2))
1875 return bitmap_bit_p (EXPR_DIES (block)((bb_value_sets_t) ((block)->aux))->expr_dies, id * 2 + 1);
1876
1877 /* A memory expression {e, VUSE} dies in the block if there is a
1878 statement that may clobber e. If, starting statement walk from the
1879 top of the basic block, a statement uses VUSE there can be no kill
1880 inbetween that use and the original statement that loaded {e, VUSE},
1881 so we can stop walking. */
1882 ref.base = NULL_TREE(tree) nullptr;
1883 for (gsi = gsi_start_bb (block); !gsi_end_p (gsi); gsi_next (&gsi))
1884 {
1885 tree def_vuse, def_vdef;
1886 def = gsi_stmt (gsi);
1887 def_vuse = gimple_vuse (def);
1888 def_vdef = gimple_vdef (def);
1889
1890 /* Not a memory statement. */
1891 if (!def_vuse)
1892 continue;
1893
1894 /* Not a may-def. */
1895 if (!def_vdef)
1896 {
1897 /* A load with the same VUSE, we're done. */
1898 if (def_vuse == vuse)
1899 break;
1900
1901 continue;
1902 }
1903
1904 /* Init ref only if we really need it. */
1905 if (ref.base == NULL_TREE(tree) nullptr
1906 && !ao_ref_init_from_vn_reference (&ref, refx->set, refx->base_set,
1907 refx->type, refx->operands))
1908 {
1909 res = true;
1910 break;
1911 }
1912 /* If the statement may clobber expr, it dies. */
1913 if (stmt_may_clobber_ref_p_1 (def, &ref))
1914 {
1915 res = true;
1916 break;
1917 }
1918 }
1919
1920 /* Remember the result. */
1921 if (!EXPR_DIES (block)((bb_value_sets_t) ((block)->aux))->expr_dies)
1922 EXPR_DIES (block)((bb_value_sets_t) ((block)->aux))->expr_dies = BITMAP_ALLOCbitmap_alloc (&grand_bitmap_obstack);
1923 bitmap_set_bit (EXPR_DIES (block)((bb_value_sets_t) ((block)->aux))->expr_dies, id * 2);
1924 if (res)
1925 bitmap_set_bit (EXPR_DIES (block)((bb_value_sets_t) ((block)->aux))->expr_dies, id * 2 + 1);
1926
1927 return res;
1928}
1929
1930
1931/* Determine if OP is valid in SET1 U SET2, which it is when the union
1932 contains its value-id. */
1933
1934static bool
1935op_valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, tree op)
1936{
1937 if (op && TREE_CODE (op)((enum tree_code) (op)->base.code) == SSA_NAME)
1938 {
1939 unsigned int value_id = VN_INFO (op)->value_id;
1940 if (!(bitmap_set_contains_value (set1, value_id)
1941 || (set2 && bitmap_set_contains_value (set2, value_id))))
1942 return false;
1943 }
1944 return true;
1945}
1946
1947/* Determine if the expression EXPR is valid in SET1 U SET2.
1948 ONLY SET2 CAN BE NULL.
1949 This means that we have a leader for each part of the expression
1950 (if it consists of values), or the expression is an SSA_NAME.
1951 For loads/calls, we also see if the vuse is killed in this block. */
1952
1953static bool
1954valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, pre_expr expr)
1955{
1956 switch (expr->kind)
1957 {
1958 case NAME:
1959 /* By construction all NAMEs are available. Non-available
1960 NAMEs are removed by subtracting TMP_GEN from the sets. */
1961 return true;
1962 case NARY:
1963 {
1964 unsigned int i;
1965 vn_nary_op_t nary = PRE_EXPR_NARY (expr)(expr)->u.nary;
1966 for (i = 0; i < nary->length; i++)
1967 if (!op_valid_in_sets (set1, set2, nary->op[i]))
1968 return false;
1969 return true;
1970 }
1971 break;
1972 case REFERENCE:
1973 {
1974 vn_reference_t ref = PRE_EXPR_REFERENCE (expr)(expr)->u.reference;
1975 vn_reference_op_t vro;
1976 unsigned int i;
1977
1978 FOR_EACH_VEC_ELT (ref->operands, i, vro)for (i = 0; (ref->operands).iterate ((i), &(vro)); ++(
i))
1979 {
1980 if (!op_valid_in_sets (set1, set2, vro->op0)
1981 || !op_valid_in_sets (set1, set2, vro->op1)
1982 || !op_valid_in_sets (set1, set2, vro->op2))
1983 return false;
1984 }
1985 return true;
1986 }
1987 default:
1988 gcc_unreachable ()(fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 1988, __FUNCTION__))
;
1989 }
1990}
1991
1992/* Clean the set of expressions SET1 that are no longer valid in SET1 or SET2.
1993 This means expressions that are made up of values we have no leaders for
1994 in SET1 or SET2. */
1995
1996static void
1997clean (bitmap_set_t set1, bitmap_set_t set2 = NULLnullptr)
1998{
1999 vec<pre_expr> exprs = sorted_array_from_bitmap_set (set1);
2000 pre_expr expr;
2001 int i;
2002
2003 FOR_EACH_VEC_ELT (exprs, i, expr)for (i = 0; (exprs).iterate ((i), &(expr)); ++(i))
2004 {
2005 if (!valid_in_sets (set1, set2, expr))
2006 {
2007 unsigned int val = get_expr_value_id (expr);
2008 bitmap_clear_bit (&set1->expressions, get_expression_id (expr));
2009 /* We are entered with possibly multiple expressions for a value
2010 so before removing a value from the set see if there's an
2011 expression for it left. */
2012 if (! bitmap_find_leader (set1, val))
2013 bitmap_clear_bit (&set1->values, val);
2014 }
2015 }
2016 exprs.release ();
2017
2018 if (flag_checkingglobal_options.x_flag_checking)
2019 {
2020 unsigned j;
2021 bitmap_iterator bi;
2022 FOR_EACH_EXPR_ID_IN_SET (set1, j, bi)for (bmp_iter_set_init (&((bi)), (&(set1)->expressions
), (0), &((j))); bmp_iter_set (&((bi)), &((j))); bmp_iter_next
(&((bi)), &((j))))
2023 gcc_assert (valid_in_sets (set1, set2, expression_for_id (j)))((void)(!(valid_in_sets (set1, set2, expression_for_id (j))) ?
fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 2023, __FUNCTION__), 0 : 0))
;
2024 }
2025}
2026
2027/* Clean the set of expressions that are no longer valid in SET because
2028 they are clobbered in BLOCK or because they trap and may not be executed. */
2029
2030static void
2031prune_clobbered_mems (bitmap_set_t set, basic_block block)
2032{
2033 bitmap_iterator bi;
2034 unsigned i;
2035 unsigned to_remove = -1U;
2036 bool any_removed = false;
2037
2038 FOR_EACH_EXPR_ID_IN_SET (set, i, bi)for (bmp_iter_set_init (&((bi)), (&(set)->expressions
), (0), &((i))); bmp_iter_set (&((bi)), &((i))); bmp_iter_next
(&((bi)), &((i))))
2039 {
2040 /* Remove queued expr. */
2041 if (to_remove != -1U)
2042 {
2043 bitmap_clear_bit (&set->expressions, to_remove);
2044 any_removed = true;
2045 to_remove = -1U;
2046 }
2047
2048 pre_expr expr = expression_for_id (i);
2049 if (expr->kind == REFERENCE)
2050 {
2051 vn_reference_t ref = PRE_EXPR_REFERENCE (expr)(expr)->u.reference;
2052 if (ref->vuse)
2053 {
2054 gimple *def_stmt = SSA_NAME_DEF_STMT (ref->vuse)(tree_check ((ref->vuse), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 2054, __FUNCTION__, (SSA_NAME)))->ssa_name.def_stmt
;
2055 if (!gimple_nop_p (def_stmt)
2056 && ((gimple_bb (def_stmt) != block
2057 && !dominated_by_p (CDI_DOMINATORS,
2058 block, gimple_bb (def_stmt)))
2059 || (gimple_bb (def_stmt) == block
2060 && value_dies_in_block_x (expr, block))))
2061 to_remove = i;
2062 }
2063 /* If the REFERENCE may trap make sure the block does not contain
2064 a possible exit point.
2065 ??? This is overly conservative if we translate AVAIL_OUT
2066 as the available expression might be after the exit point. */
2067 if (BB_MAY_NOTRETURN (block)((bb_value_sets_t) ((block)->aux))->contains_may_not_return_call
2068 && vn_reference_may_trap (ref))
2069 to_remove = i;
2070 }
2071 else if (expr->kind == NARY)
2072 {
2073 vn_nary_op_t nary = PRE_EXPR_NARY (expr)(expr)->u.nary;
2074 /* If the NARY may trap make sure the block does not contain
2075 a possible exit point.
2076 ??? This is overly conservative if we translate AVAIL_OUT
2077 as the available expression might be after the exit point. */
2078 if (BB_MAY_NOTRETURN (block)((bb_value_sets_t) ((block)->aux))->contains_may_not_return_call
2079 && vn_nary_may_trap (nary))
2080 to_remove = i;
2081 }
2082 }
2083
2084 /* Remove queued expr. */
2085 if (to_remove != -1U)
2086 {
2087 bitmap_clear_bit (&set->expressions, to_remove);
2088 any_removed = true;
2089 }
2090
2091 /* Above we only removed expressions, now clean the set of values
2092 which no longer have any corresponding expression. We cannot
2093 clear the value at the time we remove an expression since there
2094 may be multiple expressions per value.
2095 If we'd queue possibly to be removed values we could use
2096 the bitmap_find_leader way to see if there's still an expression
2097 for it. For some ratio of to be removed values and number of
2098 values/expressions in the set this might be faster than rebuilding
2099 the value-set. */
2100 if (any_removed)
2101 {
2102 bitmap_clear (&set->values);
2103 FOR_EACH_EXPR_ID_IN_SET (set, i, bi)for (bmp_iter_set_init (&((bi)), (&(set)->expressions
), (0), &((i))); bmp_iter_set (&((bi)), &((i))); bmp_iter_next
(&((bi)), &((i))))
2104 {
2105 pre_expr expr = expression_for_id (i);
2106 unsigned int value_id = get_expr_value_id (expr);
2107 bitmap_set_bit (&set->values, value_id);
2108 }
2109 }
2110}
2111
2112/* Compute the ANTIC set for BLOCK.
2113
2114 If succs(BLOCK) > 1 then
2115 ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK)
2116 else if succs(BLOCK) == 1 then
2117 ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)])
2118
2119 ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
2120
2121 Note that clean() is deferred until after the iteration. */
2122
2123static bool
2124compute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge)
2125{
2126 bitmap_set_t S, old, ANTIC_OUT;
2127 edge e;
2128 edge_iterator ei;
2129
2130 bool was_visited = BB_VISITED (block)((bb_value_sets_t) ((block)->aux))->visited;
2131 bool changed = ! BB_VISITED (block)((bb_value_sets_t) ((block)->aux))->visited;
2132 BB_VISITED (block)((bb_value_sets_t) ((block)->aux))->visited = 1;
2133 old = ANTIC_OUT = S = NULLnullptr;
2134
2135 /* If any edges from predecessors are abnormal, antic_in is empty,
2136 so do nothing. */
2137 if (block_has_abnormal_pred_edge)
2138 goto maybe_dump_sets;
2139
2140 old = ANTIC_IN (block)((bb_value_sets_t) ((block)->aux))->antic_in;
2141 ANTIC_OUT = bitmap_set_new ();
2142
2143 /* If the block has no successors, ANTIC_OUT is empty. */
2144 if (EDGE_COUNT (block->succs)vec_safe_length (block->succs) == 0)
2145 ;
2146 /* If we have one successor, we could have some phi nodes to
2147 translate through. */
2148 else if (single_succ_p (block))
2149 {
2150 e = single_succ_edge (block);
2151 gcc_assert (BB_VISITED (e->dest))((void)(!(((bb_value_sets_t) ((e->dest)->aux))->visited
) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 2151, __FUNCTION__), 0 : 0))
;
2152 phi_translate_set (ANTIC_OUT, ANTIC_IN (e->dest)((bb_value_sets_t) ((e->dest)->aux))->antic_in, e);
2153 }
2154 /* If we have multiple successors, we take the intersection of all of
2155 them. Note that in the case of loop exit phi nodes, we may have
2156 phis to translate through. */
2157 else
2158 {
2159 size_t i;
2160 edge first = NULLnullptr;
2161
2162 auto_vec<edge> worklist (EDGE_COUNT (block->succs)vec_safe_length (block->succs));
2163 FOR_EACH_EDGE (e, ei, block->succs)for ((ei) = ei_start_1 (&((block->succs))); ei_cond ((
ei), &(e)); ei_next (&(ei)))
2164 {
2165 if (!first
2166 && BB_VISITED (e->dest)((bb_value_sets_t) ((e->dest)->aux))->visited)
2167 first = e;
2168 else if (BB_VISITED (e->dest)((bb_value_sets_t) ((e->dest)->aux))->visited)
2169 worklist.quick_push (e);
2170 else
2171 {
2172 /* Unvisited successors get their ANTIC_IN replaced by the
2173 maximal set to arrive at a maximum ANTIC_IN solution.
2174 We can ignore them in the intersection operation and thus
2175 need not explicitely represent that maximum solution. */
2176 if (dump_file && (dump_flags & TDF_DETAILS))
2177 fprintf (dump_file, "ANTIC_IN is MAX on %d->%d\n",
2178 e->src->index, e->dest->index);
2179 }
2180 }
2181
2182 /* Of multiple successors we have to have visited one already
2183 which is guaranteed by iteration order. */
2184 gcc_assert (first != NULL)((void)(!(first != nullptr) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 2184, __FUNCTION__), 0 : 0))
;
2185
2186 phi_translate_set (ANTIC_OUT, ANTIC_IN (first->dest)((bb_value_sets_t) ((first->dest)->aux))->antic_in, first);
2187
2188 /* If we have multiple successors we need to intersect the ANTIC_OUT
2189 sets. For values that's a simple intersection but for
2190 expressions it is a union. Given we want to have a single
2191 expression per value in our sets we have to canonicalize.
2192 Avoid randomness and running into cycles like for PR82129 and
2193 canonicalize the expression we choose to the one with the
2194 lowest id. This requires we actually compute the union first. */
2195 FOR_EACH_VEC_ELT (worklist, i, e)for (i = 0; (worklist).iterate ((i), &(e)); ++(i))
2196 {
2197 if (!gimple_seq_empty_p (phi_nodes (e->dest)))
2198 {
2199 bitmap_set_t tmp = bitmap_set_new ();
2200 phi_translate_set (tmp, ANTIC_IN (e->dest)((bb_value_sets_t) ((e->dest)->aux))->antic_in, e);
2201 bitmap_and_into (&ANTIC_OUT->values, &tmp->values);
2202 bitmap_ior_into (&ANTIC_OUT->expressions, &tmp->expressions);
2203 bitmap_set_free (tmp);
2204 }
2205 else
2206 {
2207 bitmap_and_into (&ANTIC_OUT->values, &ANTIC_IN (e->dest)((bb_value_sets_t) ((e->dest)->aux))->antic_in->values);
2208 bitmap_ior_into (&ANTIC_OUT->expressions,
2209 &ANTIC_IN (e->dest)((bb_value_sets_t) ((e->dest)->aux))->antic_in->expressions);
2210 }
2211 }
2212 if (! worklist.is_empty ())
2213 {
2214 /* Prune expressions not in the value set. */
2215 bitmap_iterator bi;
2216 unsigned int i;
2217 unsigned int to_clear = -1U;
2218 FOR_EACH_EXPR_ID_IN_SET (ANTIC_OUT, i, bi)for (bmp_iter_set_init (&((bi)), (&(ANTIC_OUT)->expressions
), (0), &((i))); bmp_iter_set (&((bi)), &((i))); bmp_iter_next
(&((bi)), &((i))))
2219 {
2220 if (to_clear != -1U)
2221 {
2222 bitmap_clear_bit (&ANTIC_OUT->expressions, to_clear);
2223 to_clear = -1U;
2224 }
2225 pre_expr expr = expression_for_id (i);
2226 unsigned int value_id = get_expr_value_id (expr);
2227 if (!bitmap_bit_p (&ANTIC_OUT->values, value_id))
2228 to_clear = i;
2229 }
2230 if (to_clear != -1U)
2231 bitmap_clear_bit (&ANTIC_OUT->expressions, to_clear);
2232 }
2233 }
2234
2235 /* Prune expressions that are clobbered in block and thus become
2236 invalid if translated from ANTIC_OUT to ANTIC_IN. */
2237 prune_clobbered_mems (ANTIC_OUT, block);
2238
2239 /* Generate ANTIC_OUT - TMP_GEN. */
2240 S = bitmap_set_subtract_expressions (ANTIC_OUT, TMP_GEN (block)((bb_value_sets_t) ((block)->aux))->tmp_gen);
2241
2242 /* Start ANTIC_IN with EXP_GEN - TMP_GEN. */
2243 ANTIC_IN (block)((bb_value_sets_t) ((block)->aux))->antic_in = bitmap_set_subtract_expressions (EXP_GEN (block)((bb_value_sets_t) ((block)->aux))->exp_gen,
2244 TMP_GEN (block)((bb_value_sets_t) ((block)->aux))->tmp_gen);
2245
2246 /* Then union in the ANTIC_OUT - TMP_GEN values,
2247 to get ANTIC_OUT U EXP_GEN - TMP_GEN */
2248 bitmap_ior_into (&ANTIC_IN (block)((bb_value_sets_t) ((block)->aux))->antic_in->values, &S->values);
2249 bitmap_ior_into (&ANTIC_IN (block)((bb_value_sets_t) ((block)->aux))->antic_in->expressions, &S->expressions);
2250
2251 /* clean (ANTIC_IN (block)) is defered to after the iteration converged
2252 because it can cause non-convergence, see for example PR81181. */
2253
2254 /* Intersect ANTIC_IN with the old ANTIC_IN. This is required until
2255 we properly represent the maximum expression set, thus not prune
2256 values without expressions during the iteration. */
2257 if (was_visited
2258 && bitmap_and_into (&ANTIC_IN (block)((bb_value_sets_t) ((block)->aux))->antic_in->values, &old->values))
2259 {
2260 if (dump_file && (dump_flags & TDF_DETAILS))
2261 fprintf (dump_file, "warning: intersecting with old ANTIC_IN "
2262 "shrinks the set\n");
2263 /* Prune expressions not in the value set. */
2264 bitmap_iterator bi;
2265 unsigned int i;
2266 unsigned int to_clear = -1U;
2267 FOR_EACH_EXPR_ID_IN_SET (ANTIC_IN (block), i, bi)for (bmp_iter_set_init (&((bi)), (&(((bb_value_sets_t
) ((block)->aux))->antic_in)->expressions), (0), &
((i))); bmp_iter_set (&((bi)), &((i))); bmp_iter_next
(&((bi)), &((i))))
2268 {
2269 if (to_clear != -1U)
2270 {
2271 bitmap_clear_bit (&ANTIC_IN (block)((bb_value_sets_t) ((block)->aux))->antic_in->expressions, to_clear);
2272 to_clear = -1U;
2273 }
2274 pre_expr expr = expression_for_id (i);
2275 unsigned int value_id = get_expr_value_id (expr);
2276 if (!bitmap_bit_p (&ANTIC_IN (block)((bb_value_sets_t) ((block)->aux))->antic_in->values, value_id))
2277 to_clear = i;
2278 }
2279 if (to_clear != -1U)
2280 bitmap_clear_bit (&ANTIC_IN (block)((bb_value_sets_t) ((block)->aux))->antic_in->expressions, to_clear);
2281 }
2282
2283 if (!bitmap_set_equal (old, ANTIC_IN (block)((bb_value_sets_t) ((block)->aux))->antic_in))
2284 changed = true;
2285
2286 maybe_dump_sets:
2287 if (dump_file && (dump_flags & TDF_DETAILS))
2288 {
2289 if (ANTIC_OUT)
2290 print_bitmap_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index);
2291
2292 if (changed)
2293 fprintf (dump_file, "[changed] ");
2294 print_bitmap_set (dump_file, ANTIC_IN (block)((bb_value_sets_t) ((block)->aux))->antic_in, "ANTIC_IN",
2295 block->index);
2296
2297 if (S)
2298 print_bitmap_set (dump_file, S, "S", block->index);
2299 }
2300 if (old)
2301 bitmap_set_free (old);
2302 if (S)
2303 bitmap_set_free (S);
2304 if (ANTIC_OUT)
2305 bitmap_set_free (ANTIC_OUT);
2306 return changed;
2307}
2308
2309/* Compute PARTIAL_ANTIC for BLOCK.
2310
2311 If succs(BLOCK) > 1 then
2312 PA_OUT[BLOCK] = value wise union of PA_IN[b] + all ANTIC_IN not
2313 in ANTIC_OUT for all succ(BLOCK)
2314 else if succs(BLOCK) == 1 then
2315 PA_OUT[BLOCK] = phi_translate (PA_IN[succ(BLOCK)])
2316
2317 PA_IN[BLOCK] = clean(PA_OUT[BLOCK] - TMP_GEN[BLOCK] - ANTIC_IN[BLOCK])
2318
2319*/
2320static void
2321compute_partial_antic_aux (basic_block block,
2322 bool block_has_abnormal_pred_edge)
2323{
2324 bitmap_set_t old_PA_IN;
2325 bitmap_set_t PA_OUT;
2326 edge e;
2327 edge_iterator ei;
2328 unsigned long max_pa = param_max_partial_antic_lengthglobal_options.x_param_max_partial_antic_length;
2329
2330 old_PA_IN = PA_OUT = NULLnullptr;
2331
2332 /* If any edges from predecessors are abnormal, antic_in is empty,
2333 so do nothing. */
2334 if (block_has_abnormal_pred_edge)
2335 goto maybe_dump_sets;
2336
2337 /* If there are too many partially anticipatable values in the
2338 block, phi_translate_set can take an exponential time: stop
2339 before the translation starts. */
2340 if (max_pa
2341 && single_succ_p (block)
2342 && bitmap_count_bits (&PA_IN (single_succ (block))((bb_value_sets_t) ((single_succ (block))->aux))->pa_in->values) > max_pa)
2343 goto maybe_dump_sets;
2344
2345 old_PA_IN = PA_IN (block)((bb_value_sets_t) ((block)->aux))->pa_in;
2346 PA_OUT = bitmap_set_new ();
2347
2348 /* If the block has no successors, ANTIC_OUT is empty. */
2349 if (EDGE_COUNT (block->succs)vec_safe_length (block->succs) == 0)
2350 ;
2351 /* If we have one successor, we could have some phi nodes to
2352 translate through. Note that we can't phi translate across DFS
2353 back edges in partial antic, because it uses a union operation on
2354 the successors. For recurrences like IV's, we will end up
2355 generating a new value in the set on each go around (i + 3 (VH.1)
2356 VH.1 + 1 (VH.2), VH.2 + 1 (VH.3), etc), forever. */
2357 else if (single_succ_p (block))
2358 {
2359 e = single_succ_edge (block);
2360 if (!(e->flags & EDGE_DFS_BACK))
2361 phi_translate_set (PA_OUT, PA_IN (e->dest)((bb_value_sets_t) ((e->dest)->aux))->pa_in, e);
2362 }
2363 /* If we have multiple successors, we take the union of all of
2364 them. */
2365 else
2366 {
2367 size_t i;
2368
2369 auto_vec<edge> worklist (EDGE_COUNT (block->succs)vec_safe_length (block->succs));
2370 FOR_EACH_EDGE (e, ei, block->succs)for ((ei) = ei_start_1 (&((block->succs))); ei_cond ((
ei), &(e)); ei_next (&(ei)))
2371 {
2372 if (e->flags & EDGE_DFS_BACK)
2373 continue;
2374 worklist.quick_push (e);
2375 }
2376 if (worklist.length () > 0)
2377 {
2378 FOR_EACH_VEC_ELT (worklist, i, e)for (i = 0; (worklist).iterate ((i), &(e)); ++(i))
2379 {
2380 unsigned int i;
2381 bitmap_iterator bi;
2382
2383 FOR_EACH_EXPR_ID_IN_SET (ANTIC_IN (e->dest), i, bi)for (bmp_iter_set_init (&((bi)), (&(((bb_value_sets_t
) ((e->dest)->aux))->antic_in)->expressions), (0)
, &((i))); bmp_iter_set (&((bi)), &((i))); bmp_iter_next
(&((bi)), &((i))))
2384 bitmap_value_insert_into_set (PA_OUT,
2385 expression_for_id (i));
2386 if (!gimple_seq_empty_p (phi_nodes (e->dest)))
2387 {
2388 bitmap_set_t pa_in = bitmap_set_new ();
2389 phi_translate_set (pa_in, PA_IN (e->dest)((bb_value_sets_t) ((e->dest)->aux))->pa_in, e);
2390 FOR_EACH_EXPR_ID_IN_SET (pa_in, i, bi)for (bmp_iter_set_init (&((bi)), (&(pa_in)->expressions
), (0), &((i))); bmp_iter_set (&((bi)), &((i))); bmp_iter_next
(&((bi)), &((i))))
2391 bitmap_value_insert_into_set (PA_OUT,
2392 expression_for_id (i));
2393 bitmap_set_free (pa_in);
2394 }
2395 else
2396 FOR_EACH_EXPR_ID_IN_SET (PA_IN (e->dest), i, bi)for (bmp_iter_set_init (&((bi)), (&(((bb_value_sets_t
) ((e->dest)->aux))->pa_in)->expressions), (0), &
((i))); bmp_iter_set (&((bi)), &((i))); bmp_iter_next
(&((bi)), &((i))))
2397 bitmap_value_insert_into_set (PA_OUT,
2398 expression_for_id (i));
2399 }
2400 }
2401 }
2402
2403 /* Prune expressions that are clobbered in block and thus become
2404 invalid if translated from PA_OUT to PA_IN. */
2405 prune_clobbered_mems (PA_OUT, block);
2406
2407 /* PA_IN starts with PA_OUT - TMP_GEN.
2408 Then we subtract things from ANTIC_IN. */
2409 PA_IN (block)((bb_value_sets_t) ((block)->aux))->pa_in = bitmap_set_subtract_expressions (PA_OUT, TMP_GEN (block)((bb_value_sets_t) ((block)->aux))->tmp_gen);
2410
2411 /* For partial antic, we want to put back in the phi results, since
2412 we will properly avoid making them partially antic over backedges. */
2413 bitmap_ior_into (&PA_IN (block)((bb_value_sets_t) ((block)->aux))->pa_in->values, &PHI_GEN (block)((bb_value_sets_t) ((block)->aux))->phi_gen->values);
2414 bitmap_ior_into (&PA_IN (block)((bb_value_sets_t) ((block)->aux))->pa_in->expressions, &PHI_GEN (block)((bb_value_sets_t) ((block)->aux))->phi_gen->expressions);
2415
2416 /* PA_IN[block] = PA_IN[block] - ANTIC_IN[block] */
2417 bitmap_set_subtract_values (PA_IN (block)((bb_value_sets_t) ((block)->aux))->pa_in, ANTIC_IN (block)((bb_value_sets_t) ((block)->aux))->antic_in);
2418
2419 clean (PA_IN (block)((bb_value_sets_t) ((block)->aux))->pa_in, ANTIC_IN (block)((bb_value_sets_t) ((block)->aux))->antic_in);
2420
2421 maybe_dump_sets:
2422 if (dump_file && (dump_flags & TDF_DETAILS))
2423 {
2424 if (PA_OUT)
2425 print_bitmap_set (dump_file, PA_OUT, "PA_OUT", block->index);
2426
2427 print_bitmap_set (dump_file, PA_IN (block)((bb_value_sets_t) ((block)->aux))->pa_in, "PA_IN", block->index);
2428 }
2429 if (old_PA_IN)
2430 bitmap_set_free (old_PA_IN);
2431 if (PA_OUT)
2432 bitmap_set_free (PA_OUT);
2433}
2434
2435/* Compute ANTIC and partial ANTIC sets. */
2436
2437static void
2438compute_antic (void)
2439{
2440 bool changed = true;
2441 int num_iterations = 0;
2442 basic_block block;
2443 int i;
2444 edge_iterator ei;
2445 edge e;
2446
2447 /* If any predecessor edges are abnormal, we punt, so antic_in is empty.
2448 We pre-build the map of blocks with incoming abnormal edges here. */
2449 auto_sbitmap has_abnormal_preds (last_basic_block_for_fn (cfun)(((cfun + 0))->cfg->x_last_basic_block));
2450 bitmap_clear (has_abnormal_preds);
2451
2452 FOR_ALL_BB_FN (block, cfun)for (block = (((cfun + 0))->cfg->x_entry_block_ptr); block
; block = block->next_bb)
2453 {
2454 BB_VISITED (block)((bb_value_sets_t) ((block)->aux))->visited = 0;
2455
2456 FOR_EACH_EDGE (e, ei, block->preds)for ((ei) = ei_start_1 (&((block->preds))); ei_cond ((
ei), &(e)); ei_next (&(ei)))
2457 if (e->flags & EDGE_ABNORMAL)
2458 {
2459 bitmap_set_bit (has_abnormal_preds, block->index);
2460 break;
2461 }
2462
2463 /* While we are here, give empty ANTIC_IN sets to each block. */
2464 ANTIC_IN (block)((bb_value_sets_t) ((block)->aux))->antic_in = bitmap_set_new ();
2465 if (do_partial_partial)
2466 PA_IN (block)((bb_value_sets_t) ((block)->aux))->pa_in = bitmap_set_new ();
2467 }
2468
2469 /* At the exit block we anticipate nothing. */
2470 BB_VISITED (EXIT_BLOCK_PTR_FOR_FN (cfun))((bb_value_sets_t) (((((cfun + 0))->cfg->x_exit_block_ptr
))->aux))->visited
= 1;
2471
2472 /* For ANTIC computation we need a postorder that also guarantees that
2473 a block with a single successor is visited after its successor.
2474 RPO on the inverted CFG has this property. */
2475 auto_vec<int, 20> postorder;
2476 inverted_post_order_compute (&postorder);
2477
2478 auto_sbitmap worklist (last_basic_block_for_fn (cfun)(((cfun + 0))->cfg->x_last_basic_block) + 1);
2479 bitmap_clear (worklist);
2480 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)for ((ei) = ei_start_1 (&(((((cfun + 0))->cfg->x_exit_block_ptr
)->preds))); ei_cond ((ei), &(e)); ei_next (&(ei))
)
2481 bitmap_set_bit (worklist, e->src->index);
2482 while (changed)
2483 {
2484 if (dump_file && (dump_flags & TDF_DETAILS))
2485 fprintf (dump_file, "Starting iteration %d\n", num_iterations);
2486 /* ??? We need to clear our PHI translation cache here as the
2487 ANTIC sets shrink and we restrict valid translations to
2488 those having operands with leaders in ANTIC. Same below
2489 for PA ANTIC computation. */
2490 num_iterations++;
2491 changed = false;
2492 for (i = postorder.length () - 1; i >= 0; i--)
2493 {
2494 if (bitmap_bit_p (worklist, postorder[i]))
2495 {
2496 basic_block block = BASIC_BLOCK_FOR_FN (cfun, postorder[i])((*(((cfun + 0))->cfg->x_basic_block_info))[(postorder[
i])])
;
2497 bitmap_clear_bit (worklist, block->index);
2498 if (compute_antic_aux (block,
2499 bitmap_bit_p (has_abnormal_preds,
2500 block->index)))
2501 {
2502 FOR_EACH_EDGE (e, ei, block->preds)for ((ei) = ei_start_1 (&((block->preds))); ei_cond ((
ei), &(e)); ei_next (&(ei)))
2503 bitmap_set_bit (worklist, e->src->index);
2504 changed = true;
2505 }
2506 }
2507 }
2508 /* Theoretically possible, but *highly* unlikely. */
2509 gcc_checking_assert (num_iterations < 500)((void)(!(num_iterations < 500) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 2509, __FUNCTION__), 0 : 0))
;
2510 }
2511
2512 /* We have to clean after the dataflow problem converged as cleaning
2513 can cause non-convergence because it is based on expressions
2514 rather than values. */
2515 FOR_EACH_BB_FN (block, cfun)for (block = ((cfun + 0))->cfg->x_entry_block_ptr->next_bb
; block != ((cfun + 0))->cfg->x_exit_block_ptr; block =
block->next_bb)
2516 clean (ANTIC_IN (block)((bb_value_sets_t) ((block)->aux))->antic_in);
2517
2518 statistics_histogram_event (cfun(cfun + 0), "compute_antic iterations",
2519 num_iterations);
2520
2521 if (do_partial_partial)
2522 {
2523 /* For partial antic we ignore backedges and thus we do not need
2524 to perform any iteration when we process blocks in postorder. */
2525 for (i = postorder.length () - 1; i >= 0; i--)
2526 {
2527 basic_block block = BASIC_BLOCK_FOR_FN (cfun, postorder[i])((*(((cfun + 0))->cfg->x_basic_block_info))[(postorder[
i])])
;
2528 compute_partial_antic_aux (block,
2529 bitmap_bit_p (has_abnormal_preds,
2530 block->index));
2531 }
2532 }
2533}
2534
2535
2536/* Inserted expressions are placed onto this worklist, which is used
2537 for performing quick dead code elimination of insertions we made
2538 that didn't turn out to be necessary. */
2539static bitmap inserted_exprs;
2540
2541/* The actual worker for create_component_ref_by_pieces. */
2542
2543static tree
2544create_component_ref_by_pieces_1 (basic_block block, vn_reference_t ref,
2545 unsigned int *operand, gimple_seq *stmts)
2546{
2547 vn_reference_op_t currop = &ref->operands[*operand];
2548 tree genop;
2549 ++*operand;
2550 switch (currop->opcode)
2551 {
2552 case CALL_EXPR:
2553 gcc_unreachable ()(fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 2553, __FUNCTION__))
;
2554
2555 case MEM_REF:
2556 {
2557 tree baseop = create_component_ref_by_pieces_1 (block, ref, operand,
2558 stmts);
2559 if (!baseop)
2560 return NULL_TREE(tree) nullptr;
2561 tree offset = currop->op0;
2562 if (TREE_CODE (baseop)((enum tree_code) (baseop)->base.code) == ADDR_EXPR
2563 && handled_component_p (TREE_OPERAND (baseop, 0)(*((const_cast<tree*> (tree_operand_check ((baseop), (0
), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 2563, __FUNCTION__)))))
))
2564 {
2565 poly_int64 off;
2566 tree base;
2567 base = get_addr_base_and_unit_offset (TREE_OPERAND (baseop, 0)(*((const_cast<tree*> (tree_operand_check ((baseop), (0
), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 2567, __FUNCTION__)))))
,
2568 &off);
2569 gcc_assert (base)((void)(!(base) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 2569, __FUNCTION__), 0 : 0))
;
2570 offset = int_const_binop (PLUS_EXPR, offset,
2571 build_int_cst (TREE_TYPE (offset)((contains_struct_check ((offset), (TS_TYPED), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 2571, __FUNCTION__))->typed.type)
,
2572 off));
2573 baseop = build_fold_addr_expr (base)build_fold_addr_expr_loc (((location_t) 0), (base));
2574 }
2575 genop = build2 (MEM_REF, currop->type, baseop, offset);
2576 MR_DEPENDENCE_CLIQUE (genop)((tree_check2 ((genop), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 2576, __FUNCTION__, (MEM_REF), (TARGET_MEM_REF)))->base.
u.dependence_info.clique)
= currop->clique;
2577 MR_DEPENDENCE_BASE (genop)((tree_check2 ((genop), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 2577, __FUNCTION__, (MEM_REF), (TARGET_MEM_REF)))->base.
u.dependence_info.base)
= currop->base;
2578 REF_REVERSE_STORAGE_ORDER (genop)((tree_check2 ((genop), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 2578, __FUNCTION__, (BIT_FIELD_REF), (MEM_REF)))->base.default_def_flag
)
= currop->reverse;
2579 return genop;
2580 }
2581
2582 case TARGET_MEM_REF:
2583 {
2584 tree genop0 = NULL_TREE(tree) nullptr, genop1 = NULL_TREE(tree) nullptr;
2585 vn_reference_op_t nextop = &ref->operands[(*operand)++];
2586 tree baseop = create_component_ref_by_pieces_1 (block, ref, operand,
2587 stmts);
2588 if (!baseop)
2589 return NULL_TREE(tree) nullptr;
2590 if (currop->op0)
2591 {
2592 genop0 = find_or_generate_expression (block, currop->op0, stmts);
2593 if (!genop0)
2594 return NULL_TREE(tree) nullptr;
2595 }
2596 if (nextop->op0)
2597 {
2598 genop1 = find_or_generate_expression (block, nextop->op0, stmts);
2599 if (!genop1)
2600 return NULL_TREE(tree) nullptr;
2601 }
2602 genop = build5 (TARGET_MEM_REF, currop->type,
2603 baseop, currop->op2, genop0, currop->op1, genop1);
2604
2605 MR_DEPENDENCE_CLIQUE (genop)((tree_check2 ((genop), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 2605, __FUNCTION__, (MEM_REF), (TARGET_MEM_REF)))->base.
u.dependence_info.clique)
= currop->clique;
2606 MR_DEPENDENCE_BASE (genop)((tree_check2 ((genop), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 2606, __FUNCTION__, (MEM_REF), (TARGET_MEM_REF)))->base.
u.dependence_info.base)
= currop->base;
2607 return genop;
2608 }
2609
2610 case ADDR_EXPR:
2611 if (currop->op0)
2612 {
2613 gcc_assert (is_gimple_min_invariant (currop->op0))((void)(!(is_gimple_min_invariant (currop->op0)) ? fancy_abort
("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 2613, __FUNCTION__), 0 : 0))
;
2614 return currop->op0;
2615 }
2616 /* Fallthrough. */
2617 case REALPART_EXPR:
2618 case IMAGPART_EXPR:
2619 case VIEW_CONVERT_EXPR:
2620 {
2621 tree genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
2622 stmts);
2623 if (!genop0)
2624 return NULL_TREE(tree) nullptr;
2625 return fold_build1 (currop->opcode, currop->type, genop0)fold_build1_loc (((location_t) 0), currop->opcode, currop->
type, genop0 )
;
2626 }
2627
2628 case WITH_SIZE_EXPR:
2629 {
2630 tree genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
2631 stmts);
2632 if (!genop0)
2633 return NULL_TREE(tree) nullptr;
2634 tree genop1 = find_or_generate_expression (block, currop->op0, stmts);
2635 if (!genop1)
2636 return NULL_TREE(tree) nullptr;
2637 return fold_build2 (currop->opcode, currop->type, genop0, genop1)fold_build2_loc (((location_t) 0), currop->opcode, currop->
type, genop0, genop1 )
;
2638 }
2639
2640 case BIT_FIELD_REF:
2641 {
2642 tree genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
2643 stmts);
2644 if (!genop0)
2645 return NULL_TREE(tree) nullptr;
2646 tree op1 = currop->op0;
2647 tree op2 = currop->op1;
2648 tree t = build3 (BIT_FIELD_REF, currop->type, genop0, op1, op2);
2649 REF_REVERSE_STORAGE_ORDER (t)((tree_check2 ((t), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 2649, __FUNCTION__, (BIT_FIELD_REF), (MEM_REF)))->base.default_def_flag
)
= currop->reverse;
2650 return fold (t);
2651 }
2652
2653 /* For array ref vn_reference_op's, operand 1 of the array ref
2654 is op0 of the reference op and operand 3 of the array ref is
2655 op1. */
2656 case ARRAY_RANGE_REF:
2657 case ARRAY_REF:
2658 {
2659 tree genop0;
2660 tree genop1 = currop->op0;
2661 tree genop2 = currop->op1;
2662 tree genop3 = currop->op2;
2663 genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
2664 stmts);
2665 if (!genop0)
2666 return NULL_TREE(tree) nullptr;
2667 genop1 = find_or_generate_expression (block, genop1, stmts);
2668 if (!genop1)
2669 return NULL_TREE(tree) nullptr;
2670 if (genop2)
2671 {
2672 tree domain_type = TYPE_DOMAIN (TREE_TYPE (genop0))((tree_check ((((contains_struct_check ((genop0), (TS_TYPED),
"/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 2672, __FUNCTION__))->typed.type)), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 2672, __FUNCTION__, (ARRAY_TYPE)))->type_non_common.values
)
;
2673 /* Drop zero minimum index if redundant. */
2674 if (integer_zerop (genop2)
2675 && (!domain_type
2676 || integer_zerop (TYPE_MIN_VALUE (domain_type)((tree_check5 ((domain_type), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 2676, __FUNCTION__, (INTEGER_TYPE), (ENUMERAL_TYPE), (BOOLEAN_TYPE
), (REAL_TYPE), (FIXED_POINT_TYPE)))->type_non_common.minval
)
)))
2677 genop2 = NULL_TREE(tree) nullptr;
2678 else
2679 {
2680 genop2 = find_or_generate_expression (block, genop2, stmts);
2681 if (!genop2)
2682 return NULL_TREE(tree) nullptr;
2683 }
2684 }
2685 if (genop3)
2686 {
2687 tree elmt_type = TREE_TYPE (TREE_TYPE (genop0))((contains_struct_check ((((contains_struct_check ((genop0), (
TS_TYPED), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 2687, __FUNCTION__))->typed.type)), (TS_TYPED), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 2687, __FUNCTION__))->typed.type)
;
2688 /* We can't always put a size in units of the element alignment
2689 here as the element alignment may be not visible. See
2690 PR43783. Simply drop the element size for constant
2691 sizes. */
2692 if (TREE_CODE (genop3)((enum tree_code) (genop3)->base.code) == INTEGER_CST
2693 && TREE_CODE (TYPE_SIZE_UNIT (elmt_type))((enum tree_code) (((tree_class_check ((elmt_type), (tcc_type
), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 2693, __FUNCTION__))->type_common.size_unit))->base.code
)
== INTEGER_CST
2694 && wi::eq_p (wi::to_offset (TYPE_SIZE_UNIT (elmt_type)((tree_class_check ((elmt_type), (tcc_type), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 2694, __FUNCTION__))->type_common.size_unit)
),
2695 (wi::to_offset (genop3)
2696 * vn_ref_op_align_unit (currop))))
2697 genop3 = NULL_TREE(tree) nullptr;
2698 else
2699 {
2700 genop3 = find_or_generate_expression (block, genop3, stmts);
2701 if (!genop3)
2702 return NULL_TREE(tree) nullptr;
2703 }
2704 }
2705 return build4 (currop->opcode, currop->type, genop0, genop1,
2706 genop2, genop3);
2707 }
2708 case COMPONENT_REF:
2709 {
2710 tree op0;
2711 tree op1;
2712 tree genop2 = currop->op1;
2713 op0 = create_component_ref_by_pieces_1 (block, ref, operand, stmts);
2714 if (!op0)
2715 return NULL_TREE(tree) nullptr;
2716 /* op1 should be a FIELD_DECL, which are represented by themselves. */
2717 op1 = currop->op0;
2718 if (genop2)
2719 {
2720 genop2 = find_or_generate_expression (block, genop2, stmts);
2721 if (!genop2)
2722 return NULL_TREE(tree) nullptr;
2723 }
2724 return fold_build3 (COMPONENT_REF, TREE_TYPE (op1), op0, op1, genop2)fold_build3_loc (((location_t) 0), COMPONENT_REF, ((contains_struct_check
((op1), (TS_TYPED), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 2724, __FUNCTION__))->typed.type), op0, op1, genop2 )
;
2725 }
2726
2727 case SSA_NAME:
2728 {
2729 genop = find_or_generate_expression (block, currop->op0, stmts);
2730 return genop;
2731 }
2732 case STRING_CST:
2733 case INTEGER_CST:
2734 case POLY_INT_CST:
2735 case COMPLEX_CST:
2736 case VECTOR_CST:
2737 case REAL_CST:
2738 case CONSTRUCTOR:
2739 case VAR_DECL:
2740 case PARM_DECL:
2741 case CONST_DECL:
2742 case RESULT_DECL:
2743 case FUNCTION_DECL:
2744 return currop->op0;
2745
2746 default:
2747 gcc_unreachable ()(fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 2747, __FUNCTION__))
;
2748 }
2749}
2750
2751/* For COMPONENT_REF's and ARRAY_REF's, we can't have any intermediates for the
2752 COMPONENT_REF or MEM_REF or ARRAY_REF portion, because we'd end up with
2753 trying to rename aggregates into ssa form directly, which is a no no.
2754
2755 Thus, this routine doesn't create temporaries, it just builds a
2756 single access expression for the array, calling
2757 find_or_generate_expression to build the innermost pieces.
2758
2759 This function is a subroutine of create_expression_by_pieces, and
2760 should not be called on it's own unless you really know what you
2761 are doing. */
2762
2763static tree
2764create_component_ref_by_pieces (basic_block block, vn_reference_t ref,
2765 gimple_seq *stmts)
2766{
2767 unsigned int op = 0;
2768 return create_component_ref_by_pieces_1 (block, ref, &op, stmts);
2769}
2770
2771/* Find a simple leader for an expression, or generate one using
2772 create_expression_by_pieces from a NARY expression for the value.
2773 BLOCK is the basic_block we are looking for leaders in.
2774 OP is the tree expression to find a leader for or generate.
2775 Returns the leader or NULL_TREE on failure. */
2776
2777static tree
2778find_or_generate_expression (basic_block block, tree op, gimple_seq *stmts)
2779{
2780 pre_expr expr = get_or_alloc_expr_for (op);
2781 unsigned int lookfor = get_expr_value_id (expr);
2782 pre_expr leader = bitmap_find_leader (AVAIL_OUT (block)((bb_value_sets_t) ((block)->aux))->avail_out, lookfor);
2783 if (leader)
2784 {
2785 if (leader->kind == NAME)
2786 return PRE_EXPR_NAME (leader)(leader)->u.name;
2787 else if (leader->kind == CONSTANT)
2788 return PRE_EXPR_CONSTANT (leader)(leader)->u.constant;
2789
2790 /* Defer. */
2791 return NULL_TREE(tree) nullptr;
2792 }
2793
2794 /* It must be a complex expression, so generate it recursively. Note
2795 that this is only necessary to handle gcc.dg/tree-ssa/ssa-pre28.c
2796 where the insert algorithm fails to insert a required expression. */
2797 bitmap exprset = value_expressions[lookfor];
2798 bitmap_iterator bi;
2799 unsigned int i;
2800 EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)for (bmp_iter_set_init (&(bi), (exprset), (0), &(i));
bmp_iter_set (&(bi), &(i)); bmp_iter_next (&(bi)
, &(i)))
2801 {
2802 pre_expr temp = expression_for_id (i);
2803 /* We cannot insert random REFERENCE expressions at arbitrary
2804 places. We can insert NARYs which eventually re-materializes
2805 its operand values. */
2806 if (temp->kind == NARY)
2807 return create_expression_by_pieces (block, temp, stmts,
2808 get_expr_type (expr));
2809 }
2810
2811 /* Defer. */
2812 return NULL_TREE(tree) nullptr;
2813}
2814
2815/* Create an expression in pieces, so that we can handle very complex
2816 expressions that may be ANTIC, but not necessary GIMPLE.
2817 BLOCK is the basic block the expression will be inserted into,
2818 EXPR is the expression to insert (in value form)
2819 STMTS is a statement list to append the necessary insertions into.
2820
2821 This function will die if we hit some value that shouldn't be
2822 ANTIC but is (IE there is no leader for it, or its components).
2823 The function returns NULL_TREE in case a different antic expression
2824 has to be inserted first.
2825 This function may also generate expressions that are themselves
2826 partially or fully redundant. Those that are will be either made
2827 fully redundant during the next iteration of insert (for partially
2828 redundant ones), or eliminated by eliminate (for fully redundant
2829 ones). */
2830
2831static tree
2832create_expression_by_pieces (basic_block block, pre_expr expr,
2833 gimple_seq *stmts, tree type)
2834{
2835 tree name;
2836 tree folded;
2837 gimple_seq forced_stmts = NULLnullptr;
2838 unsigned int value_id;
2839 gimple_stmt_iterator gsi;
2840 tree exprtype = type ? type : get_expr_type (expr);
1
Assuming 'type' is non-null
2
'?' condition is true
2841 pre_expr nameexpr;
2842 gassign *newstmt;
2843
2844 switch (expr->kind)
3
Control jumps to 'case NARY:' at line 2941
2845 {
2846 /* We may hit the NAME/CONSTANT case if we have to convert types
2847 that value numbering saw through. */
2848 case NAME:
2849 folded = PRE_EXPR_NAME (expr)(expr)->u.name;
2850 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (folded)(tree_check ((folded), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 2850, __FUNCTION__, (SSA_NAME)))->base.asm_written_flag
)
2851 return NULL_TREE(tree) nullptr;
2852 if (useless_type_conversion_p (exprtype, TREE_TYPE (folded)((contains_struct_check ((folded), (TS_TYPED), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 2852, __FUNCTION__))->typed.type)
))
2853 return folded;
2854 break;
2855 case CONSTANT:
2856 {
2857 folded = PRE_EXPR_CONSTANT (expr)(expr)->u.constant;
2858 tree tem = fold_convert (exprtype, folded)fold_convert_loc (((location_t) 0), exprtype, folded);
2859 if (is_gimple_min_invariant (tem))
2860 return tem;
2861 break;
2862 }
2863 case REFERENCE:
2864 if (PRE_EXPR_REFERENCE (expr)(expr)->u.reference->operands[0].opcode == CALL_EXPR)
2865 {
2866 vn_reference_t ref = PRE_EXPR_REFERENCE (expr)(expr)->u.reference;
2867 unsigned int operand = 1;
2868 vn_reference_op_t currop = &ref->operands[0];
2869 tree sc = NULL_TREE(tree) nullptr;
2870 tree fn = NULL_TREE(tree) nullptr;
2871 if (currop->op0)
2872 {
2873 fn = find_or_generate_expression (block, currop->op0, stmts);
2874 if (!fn)
2875 return NULL_TREE(tree) nullptr;
2876 }
2877 if (currop->op1)
2878 {
2879 sc = find_or_generate_expression (block, currop->op1, stmts);
2880 if (!sc)
2881 return NULL_TREE(tree) nullptr;
2882 }
2883 auto_vec<tree> args (ref->operands.length () - 1);
2884 while (operand < ref->operands.length ())
2885 {
2886 tree arg = create_component_ref_by_pieces_1 (block, ref,
2887 &operand, stmts);
2888 if (!arg)
2889 return NULL_TREE(tree) nullptr;
2890 args.quick_push (arg);
2891 }
2892 gcall *call;
2893 if (currop->op0)
2894 {
2895 call = gimple_build_call_vec (fn, args);
2896 gimple_call_set_fntype (call, currop->type);
2897 }
2898 else
2899 call = gimple_build_call_internal_vec ((internal_fn)currop->clique,
2900 args);
2901 gimple_set_location (call, expr->loc);
2902 if (sc)
2903 gimple_call_set_chain (call, sc);
2904 tree forcedname = make_ssa_name (ref->type);
2905 gimple_call_set_lhs (call, forcedname);
2906 /* There's no CCP pass after PRE which would re-compute alignment
2907 information so make sure we re-materialize this here. */
2908 if (gimple_call_builtin_p (call, BUILT_IN_ASSUME_ALIGNED)
2909 && args.length () - 2 <= 1
2910 && tree_fits_uhwi_p (args[1])
2911 && (args.length () != 3 || tree_fits_uhwi_p (args[2])))
2912 {
2913 unsigned HOST_WIDE_INTlong halign = tree_to_uhwi (args[1]);
2914 unsigned HOST_WIDE_INTlong hmisalign
2915 = args.length () == 3 ? tree_to_uhwi (args[2]) : 0;
2916 if ((halign & (halign - 1)) == 0
2917 && (hmisalign & ~(halign - 1)) == 0
2918 && (unsigned int)halign != 0)
2919 set_ptr_info_alignment (get_ptr_info (forcedname),
2920 halign, hmisalign);
2921 }
2922 gimple_set_vuse (call, BB_LIVE_VOP_ON_EXIT (block)((bb_value_sets_t) ((block)->aux))->vop_on_exit);
2923 gimple_seq_add_stmt_without_update (&forced_stmts, call);
2924 folded = forcedname;
2925 }
2926 else
2927 {
2928 folded = create_component_ref_by_pieces (block,
2929 PRE_EXPR_REFERENCE (expr)(expr)->u.reference,
2930 stmts);
2931 if (!folded)
2932 return NULL_TREE(tree) nullptr;
2933 name = make_temp_ssa_name (exprtype, NULLnullptr, "pretmp");
2934 newstmt = gimple_build_assign (name, folded);
2935 gimple_set_location (newstmt, expr->loc);
2936 gimple_seq_add_stmt_without_update (&forced_stmts, newstmt);
2937 gimple_set_vuse (newstmt, BB_LIVE_VOP_ON_EXIT (block)((bb_value_sets_t) ((block)->aux))->vop_on_exit);
2938 folded = name;
2939 }
2940 break;
2941 case NARY:
2942 {
2943 vn_nary_op_t nary = PRE_EXPR_NARY (expr)(expr)->u.nary;
2944 tree *genop = XALLOCAVEC (tree, nary->length)((tree *) __builtin_alloca(sizeof (tree) * (nary->length))
)
;
2945 unsigned i;
2946 for (i = 0; i < nary->length; ++i)
4
Assuming 'i' is < field 'length'
5
Loop condition is true. Entering loop body
10
Assuming 'i' is < field 'length'
11
Loop condition is true. Entering loop body
15
Assuming 'i' is >= field 'length'
16
Loop condition is false. Execution continues on line 2966
2947 {
2948 genop[i] = find_or_generate_expression (block, nary->op[i], stmts);
2949 if (!genop[i])
6
Assuming the condition is false
7
Taking false branch
12
Assuming the condition is false
13
Taking false branch
2950 return NULL_TREE(tree) nullptr;
2951 /* Ensure genop[] is properly typed for POINTER_PLUS_EXPR. It
2952 may have conversions stripped. */
2953 if (nary->opcode
13.1
Field 'opcode' is not equal to POINTER_PLUS_EXPR
13.1
Field 'opcode' is not equal to POINTER_PLUS_EXPR
== POINTER_PLUS_EXPR
)
8
Assuming field 'opcode' is not equal to POINTER_PLUS_EXPR
9
Taking false branch
14
Taking false branch
2954 {
2955 if (i == 0)
2956 genop[i] = gimple_convert (&forced_stmts,
2957 nary->type, genop[i]);
2958 else if (i == 1)
2959 genop[i] = gimple_convert (&forced_stmts,
2960 sizetypesizetype_tab[(int) stk_sizetype], genop[i]);
2961 }
2962 else
2963 genop[i] = gimple_convert (&forced_stmts,
2964 TREE_TYPE (nary->op[i])((contains_struct_check ((nary->op[i]), (TS_TYPED), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 2964, __FUNCTION__))->typed.type)
, genop[i]);
2965 }
2966 if (nary->opcode == CONSTRUCTOR)
17
Assuming field 'opcode' is equal to CONSTRUCTOR
18
Taking true branch
2967 {
2968 vec<constructor_elt, va_gc> *elts = NULLnullptr;
2969 for (i = 0; i < nary->length; ++i)
19
Loop condition is true. Entering loop body
43
Loop condition is true. Entering loop body
2970 CONSTRUCTOR_APPEND_ELT (elts, NULL_TREE, genop[i])do { constructor_elt _ce___ = {(tree) nullptr, genop[i]}; vec_safe_push
((elts), _ce___); } while (0)
;
20
Calling 'vec_safe_push<constructor_elt, va_gc>'
41
Returning from 'vec_safe_push<constructor_elt, va_gc>'
42
Loop condition is false. Exiting loop
44
Passing value via 1st parameter 'v'
45
Calling 'vec_safe_push<constructor_elt, va_gc>'
2971 folded = build_constructor (nary->type, elts);
2972 name = make_temp_ssa_name (exprtype, NULLnullptr, "pretmp");
2973 newstmt = gimple_build_assign (name, folded);
2974 gimple_set_location (newstmt, expr->loc);
2975 gimple_seq_add_stmt_without_update (&forced_stmts, newstmt);
2976 folded = name;
2977 }
2978 else
2979 {
2980 switch (nary->length)
2981 {
2982 case 1:
2983 folded = gimple_build (&forced_stmts, expr->loc,
2984 nary->opcode, nary->type, genop[0]);
2985 break;
2986 case 2:
2987 folded = gimple_build (&forced_stmts, expr->loc, nary->opcode,
2988 nary->type, genop[0], genop[1]);
2989 break;
2990 case 3:
2991 folded = gimple_build (&forced_stmts, expr->loc, nary->opcode,
2992 nary->type, genop[0], genop[1],
2993 genop[2]);
2994 break;
2995 default:
2996 gcc_unreachable ()(fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 2996, __FUNCTION__))
;
2997 }
2998 }
2999 }
3000 break;
3001 default:
3002 gcc_unreachable ()(fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 3002, __FUNCTION__))
;
3003 }
3004
3005 folded = gimple_convert (&forced_stmts, exprtype, folded);
3006
3007 /* If there is nothing to insert, return the simplified result. */
3008 if (gimple_seq_empty_p (forced_stmts))
3009 return folded;
3010 /* If we simplified to a constant return it and discard eventually
3011 built stmts. */
3012 if (is_gimple_min_invariant (folded))
3013 {
3014 gimple_seq_discard (forced_stmts);
3015 return folded;
3016 }
3017 /* Likewise if we simplified to sth not queued for insertion. */
3018 bool found = false;
3019 gsi = gsi_last (forced_stmts)gsi_last_1 (&(forced_stmts));
3020 for (; !gsi_end_p (gsi); gsi_prev (&gsi))
3021 {
3022 gimple *stmt = gsi_stmt (gsi);
3023 tree forcedname = gimple_get_lhs (stmt);
3024 if (forcedname == folded)
3025 {
3026 found = true;
3027 break;
3028 }
3029 }
3030 if (! found)
3031 {
3032 gimple_seq_discard (forced_stmts);
3033 return folded;
3034 }
3035 gcc_assert (TREE_CODE (folded) == SSA_NAME)((void)(!(((enum tree_code) (folded)->base.code) == SSA_NAME
) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 3035, __FUNCTION__), 0 : 0))
;
3036
3037 /* If we have any intermediate expressions to the value sets, add them
3038 to the value sets and chain them in the instruction stream. */
3039 if (forced_stmts)
3040 {
3041 gsi = gsi_start (forced_stmts)gsi_start_1 (&(forced_stmts));
3042 for (; !gsi_end_p (gsi); gsi_next (&gsi))
3043 {
3044 gimple *stmt = gsi_stmt (gsi);
3045 tree forcedname = gimple_get_lhs (stmt);
3046 pre_expr nameexpr;
3047
3048 if (forcedname != folded)
3049 {
3050 vn_ssa_aux_t vn_info = VN_INFO (forcedname);
3051 vn_info->valnum = forcedname;
3052 vn_info->value_id = get_next_value_id ();
3053 nameexpr = get_or_alloc_expr_for_name (forcedname);
3054 add_to_value (vn_info->value_id, nameexpr);
3055 if (NEW_SETS (block)((bb_value_sets_t) ((block)->aux))->new_sets)
3056 bitmap_value_replace_in_set (NEW_SETS (block)((bb_value_sets_t) ((block)->aux))->new_sets, nameexpr);
3057 bitmap_value_replace_in_set (AVAIL_OUT (block)((bb_value_sets_t) ((block)->aux))->avail_out, nameexpr);
3058 }
3059
3060 bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (forcedname)(tree_check ((forcedname), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 3060, __FUNCTION__, (SSA_NAME)))->base.u.version
);
3061 }
3062 gimple_seq_add_seq (stmts, forced_stmts);
3063 }
3064
3065 name = folded;
3066
3067 /* Fold the last statement. */
3068 gsi = gsi_last (*stmts)gsi_last_1 (&(*stmts));
3069 if (fold_stmt_inplace (&gsi))
3070 update_stmt (gsi_stmt (gsi));
3071
3072 /* Add a value number to the temporary.
3073 The value may already exist in either NEW_SETS, or AVAIL_OUT, because
3074 we are creating the expression by pieces, and this particular piece of
3075 the expression may have been represented. There is no harm in replacing
3076 here. */
3077 value_id = get_expr_value_id (expr);
3078 vn_ssa_aux_t vn_info = VN_INFO (name);
3079 vn_info->value_id = value_id;
3080 vn_info->valnum = vn_valnum_from_value_id (value_id);
3081 if (vn_info->valnum == NULL_TREE(tree) nullptr)
3082 vn_info->valnum = name;
3083 gcc_assert (vn_info->valnum != NULL_TREE)((void)(!(vn_info->valnum != (tree) nullptr) ? fancy_abort
("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 3083, __FUNCTION__), 0 : 0))
;
3084 nameexpr = get_or_alloc_expr_for_name (name);
3085 add_to_value (value_id, nameexpr);
3086 if (NEW_SETS (block)((bb_value_sets_t) ((block)->aux))->new_sets)
3087 bitmap_value_replace_in_set (NEW_SETS (block)((bb_value_sets_t) ((block)->aux))->new_sets, nameexpr);
3088 bitmap_value_replace_in_set (AVAIL_OUT (block)((bb_value_sets_t) ((block)->aux))->avail_out, nameexpr);
3089
3090 pre_stats.insertions++;
3091 if (dump_file && (dump_flags & TDF_DETAILS))
3092 {
3093 fprintf (dump_file, "Inserted ");
3094 print_gimple_stmt (dump_file, gsi_stmt (gsi_last (*stmts)gsi_last_1 (&(*stmts))), 0);
3095 fprintf (dump_file, " in predecessor %d (%04d)\n",
3096 block->index, value_id);
3097 }
3098
3099 return name;
3100}
3101
3102
3103/* Insert the to-be-made-available values of expression EXPRNUM for each
3104 predecessor, stored in AVAIL, into the predecessors of BLOCK, and
3105 merge the result with a phi node, given the same value number as
3106 NODE. Return true if we have inserted new stuff. */
3107
3108static bool
3109insert_into_preds_of_block (basic_block block, unsigned int exprnum,
3110 vec<pre_expr> &avail)
3111{
3112 pre_expr expr = expression_for_id (exprnum);
3113 pre_expr newphi;
3114 unsigned int val = get_expr_value_id (expr);
3115 edge pred;
3116 bool insertions = false;
3117 bool nophi = false;
3118 basic_block bprime;
3119 pre_expr eprime;
3120 edge_iterator ei;
3121 tree type = get_expr_type (expr);
3122 tree temp;
3123 gphi *phi;
3124
3125 /* Make sure we aren't creating an induction variable. */
3126 if (bb_loop_depth (block) > 0 && EDGE_COUNT (block->preds)vec_safe_length (block->preds) == 2)
3127 {
3128 bool firstinsideloop = false;
3129 bool secondinsideloop = false;
3130 firstinsideloop = flow_bb_inside_loop_p (block->loop_father,
3131 EDGE_PRED (block, 0)(*(block)->preds)[(0)]->src);
3132 secondinsideloop = flow_bb_inside_loop_p (block->loop_father,
3133 EDGE_PRED (block, 1)(*(block)->preds)[(1)]->src);
3134 /* Induction variables only have one edge inside the loop. */
3135 if ((firstinsideloop ^ secondinsideloop)
3136 && expr->kind != REFERENCE)
3137 {
3138 if (dump_file && (dump_flags & TDF_DETAILS))
3139 fprintf (dump_file, "Skipping insertion of phi for partial "
3140 "redundancy: Looks like an induction variable\n");
3141 nophi = true;
3142 }
3143 }
3144
3145 /* Make the necessary insertions. */
3146 FOR_EACH_EDGE (pred, ei, block->preds)for ((ei) = ei_start_1 (&((block->preds))); ei_cond ((
ei), &(pred)); ei_next (&(ei)))
3147 {
3148 /* When we are not inserting a PHI node do not bother inserting
3149 into places that do not dominate the anticipated computations. */
3150 if (nophi && !dominated_by_p (CDI_DOMINATORS, block, pred->src))
3151 continue;
3152 gimple_seq stmts = NULLnullptr;
3153 tree builtexpr;
3154 bprime = pred->src;
3155 eprime = avail[pred->dest_idx];
3156 builtexpr = create_expression_by_pieces (bprime, eprime,
3157 &stmts, type);
3158 gcc_assert (!(pred->flags & EDGE_ABNORMAL))((void)(!(!(pred->flags & EDGE_ABNORMAL)) ? fancy_abort
("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 3158, __FUNCTION__), 0 : 0))
;
3159 if (!gimple_seq_empty_p (stmts))
3160 {
3161 basic_block new_bb = gsi_insert_seq_on_edge_immediate (pred, stmts);
3162 gcc_assert (! new_bb)((void)(!(! new_bb) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 3162, __FUNCTION__), 0 : 0))
;
3163 insertions = true;
3164 }
3165 if (!builtexpr)
3166 {
3167 /* We cannot insert a PHI node if we failed to insert
3168 on one edge. */
3169 nophi = true;
3170 continue;
3171 }
3172 if (is_gimple_min_invariant (builtexpr))
3173 avail[pred->dest_idx] = get_or_alloc_expr_for_constant (builtexpr);
3174 else
3175 avail[pred->dest_idx] = get_or_alloc_expr_for_name (builtexpr);
3176 }
3177 /* If we didn't want a phi node, and we made insertions, we still have
3178 inserted new stuff, and thus return true. If we didn't want a phi node,
3179 and didn't make insertions, we haven't added anything new, so return
3180 false. */
3181 if (nophi && insertions)
3182 return true;
3183 else if (nophi && !insertions)
3184 return false;
3185
3186 /* Now build a phi for the new variable. */
3187 temp = make_temp_ssa_name (type, NULLnullptr, "prephitmp");
3188 phi = create_phi_node (temp, block);
3189
3190 vn_ssa_aux_t vn_info = VN_INFO (temp);
3191 vn_info->value_id = val;
3192 vn_info->valnum = vn_valnum_from_value_id (val);
3193 if (vn_info->valnum == NULL_TREE(tree) nullptr)
3194 vn_info->valnum = temp;
3195 bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (temp)(tree_check ((temp), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 3195, __FUNCTION__, (SSA_NAME)))->base.u.version
);
3196 FOR_EACH_EDGE (pred, ei, block->preds)for ((ei) = ei_start_1 (&((block->preds))); ei_cond ((
ei), &(pred)); ei_next (&(ei)))
3197 {
3198 pre_expr ae = avail[pred->dest_idx];
3199 gcc_assert (get_expr_type (ae) == type((void)(!(get_expr_type (ae) == type || useless_type_conversion_p
(type, get_expr_type (ae))) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 3200, __FUNCTION__), 0 : 0))
3200 || useless_type_conversion_p (type, get_expr_type (ae)))((void)(!(get_expr_type (ae) == type || useless_type_conversion_p
(type, get_expr_type (ae))) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 3200, __FUNCTION__), 0 : 0))
;
3201 if (ae->kind == CONSTANT)
3202 add_phi_arg (phi, unshare_expr (PRE_EXPR_CONSTANT (ae)(ae)->u.constant),
3203 pred, UNKNOWN_LOCATION((location_t) 0));
3204 else
3205 add_phi_arg (phi, PRE_EXPR_NAME (ae)(ae)->u.name, pred, UNKNOWN_LOCATION((location_t) 0));
3206 }
3207
3208 newphi = get_or_alloc_expr_for_name (temp);
3209 add_to_value (val, newphi);
3210
3211 /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing
3212 this insertion, since we test for the existence of this value in PHI_GEN
3213 before proceeding with the partial redundancy checks in insert_aux.
3214
3215 The value may exist in AVAIL_OUT, in particular, it could be represented
3216 by the expression we are trying to eliminate, in which case we want the
3217 replacement to occur. If it's not existing in AVAIL_OUT, we want it
3218 inserted there.
3219
3220 Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of
3221 this block, because if it did, it would have existed in our dominator's
3222 AVAIL_OUT, and would have been skipped due to the full redundancy check.
3223 */
3224
3225 bitmap_insert_into_set (PHI_GEN (block)((bb_value_sets_t) ((block)->aux))->phi_gen, newphi);
3226 bitmap_value_replace_in_set (AVAIL_OUT (block)((bb_value_sets_t) ((block)->aux))->avail_out,
3227 newphi);
3228 if (NEW_SETS (block)((bb_value_sets_t) ((block)->aux))->new_sets)
3229 bitmap_insert_into_set (NEW_SETS (block)((bb_value_sets_t) ((block)->aux))->new_sets, newphi);
3230
3231 /* If we insert a PHI node for a conversion of another PHI node
3232 in the same basic-block try to preserve range information.
3233 This is important so that followup loop passes receive optimal
3234 number of iteration analysis results. See PR61743. */
3235 if (expr->kind == NARY
3236 && CONVERT_EXPR_CODE_P (expr->u.nary->opcode)((expr->u.nary->opcode) == NOP_EXPR || (expr->u.nary
->opcode) == CONVERT_EXPR)
3237 && TREE_CODE (expr->u.nary->op[0])((enum tree_code) (expr->u.nary->op[0])->base.code) == SSA_NAME
3238 && gimple_bb (SSA_NAME_DEF_STMT (expr->u.nary->op[0])(tree_check ((expr->u.nary->op[0]), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 3238, __FUNCTION__, (SSA_NAME)))->ssa_name.def_stmt
) == block
3239 && INTEGRAL_TYPE_P (type)(((enum tree_code) (type)->base.code) == ENUMERAL_TYPE || (
(enum tree_code) (type)->base.code) == BOOLEAN_TYPE || ((enum
tree_code) (type)->base.code) == INTEGER_TYPE)
3240 && INTEGRAL_TYPE_P (TREE_TYPE (expr->u.nary->op[0]))(((enum tree_code) (((contains_struct_check ((expr->u.nary
->op[0]), (TS_TYPED), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 3240, __FUNCTION__))->typed.type))->base.code) == ENUMERAL_TYPE
|| ((enum tree_code) (((contains_struct_check ((expr->u.nary
->op[0]), (TS_TYPED), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 3240, __FUNCTION__))->typed.type))->base.code) == BOOLEAN_TYPE
|| ((enum tree_code) (((contains_struct_check ((expr->u.nary
->op[0]), (TS_TYPED), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 3240, __FUNCTION__))->typed.type))->base.code) == INTEGER_TYPE
)
3241 && (TYPE_PRECISION (type)((tree_class_check ((type), (tcc_type), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 3241, __FUNCTION__))->type_common.precision)
3242 >= TYPE_PRECISION (TREE_TYPE (expr->u.nary->op[0]))((tree_class_check ((((contains_struct_check ((expr->u.nary
->op[0]), (TS_TYPED), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 3242, __FUNCTION__))->typed.type)), (tcc_type), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 3242, __FUNCTION__))->type_common.precision)
)
3243 && SSA_NAME_RANGE_INFO (expr->u.nary->op[0])(tree_check ((expr->u.nary->op[0]), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 3243, __FUNCTION__, (SSA_NAME)))->ssa_name.info.range_info
)
3244 {
3245 value_range r;
3246 if (get_range_query (cfun(cfun + 0))->range_of_expr (r, expr->u.nary->op[0])
3247 && r.kind () == VR_RANGE
3248 && !wi::neg_p (r.lower_bound (), SIGNED)
3249 && !wi::neg_p (r.upper_bound (), SIGNED))
3250 /* Just handle extension and sign-changes of all-positive ranges. */
3251 set_range_info (temp, VR_RANGE,
3252 wide_int_storage::from (r.lower_bound (),
3253 TYPE_PRECISION (type)((tree_class_check ((type), (tcc_type), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 3253, __FUNCTION__))->type_common.precision)
,
3254 TYPE_SIGN (type)((signop) ((tree_class_check ((type), (tcc_type), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 3254, __FUNCTION__))->base.u.bits.unsigned_flag))
),
3255 wide_int_storage::from (r.upper_bound (),
3256 TYPE_PRECISION (type)((tree_class_check ((type), (tcc_type), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 3256, __FUNCTION__))->type_common.precision)
,
3257 TYPE_SIGN (type)((signop) ((tree_class_check ((type), (tcc_type), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 3257, __FUNCTION__))->base.u.bits.unsigned_flag))
));
3258 }
3259
3260 if (dump_file && (dump_flags & TDF_DETAILS))
3261 {
3262 fprintf (dump_file, "Created phi ");
3263 print_gimple_stmt (dump_file, phi, 0);
3264 fprintf (dump_file, " in block %d (%04d)\n", block->index, val);
3265 }
3266 pre_stats.phis++;
3267 return true;
3268}
3269
3270
3271
3272/* Perform insertion of partially redundant or hoistable values.
3273 For BLOCK, do the following:
3274 1. Propagate the NEW_SETS of the dominator into the current block.
3275 If the block has multiple predecessors,
3276 2a. Iterate over the ANTIC expressions for the block to see if
3277 any of them are partially redundant.
3278 2b. If so, insert them into the necessary predecessors to make
3279 the expression fully redundant.
3280 2c. Insert a new PHI merging the values of the predecessors.
3281 2d. Insert the new PHI, and the new expressions, into the
3282 NEW_SETS set.
3283 If the block has multiple successors,
3284 3a. Iterate over the ANTIC values for the block to see if
3285 any of them are good candidates for hoisting.
3286 3b. If so, insert expressions computing the values in BLOCK,
3287 and add the new expressions into the NEW_SETS set.
3288 4. Recursively call ourselves on the dominator children of BLOCK.
3289
3290 Steps 1, 2a, and 4 are done by insert_aux. 2b, 2c and 2d are done by
3291 do_pre_regular_insertion and do_partial_insertion. 3a and 3b are
3292 done in do_hoist_insertion.
3293*/
3294
3295static bool
3296do_pre_regular_insertion (basic_block block, basic_block dom,
3297 vec<pre_expr> exprs)
3298{
3299 bool new_stuff = false;
3300 pre_expr expr;
3301 auto_vec<pre_expr, 2> avail;
3302 int i;
3303
3304 avail.safe_grow (EDGE_COUNT (block->preds)vec_safe_length (block->preds), true);
3305
3306 FOR_EACH_VEC_ELT (exprs, i, expr)for (i = 0; (exprs).iterate ((i), &(expr)); ++(i))
3307 {
3308 if (expr->kind == NARY
3309 || expr->kind == REFERENCE)
3310 {
3311 unsigned int val;
3312 bool by_some = false;
3313 bool cant_insert = false;
3314 bool all_same = true;
3315 pre_expr first_s = NULLnullptr;
3316 edge pred;
3317 basic_block bprime;
3318 pre_expr eprime = NULLnullptr;
3319 edge_iterator ei;
3320 pre_expr edoubleprime = NULLnullptr;
3321 bool do_insertion = false;
3322
3323 val = get_expr_value_id (expr);
3324 if (bitmap_set_contains_value (PHI_GEN (block)((bb_value_sets_t) ((block)->aux))->phi_gen, val))
3325 continue;
3326 if (bitmap_set_contains_value (AVAIL_OUT (dom)((bb_value_sets_t) ((dom)->aux))->avail_out, val))
3327 {
3328 if (dump_file && (dump_flags & TDF_DETAILS))
3329 {
3330 fprintf (dump_file, "Found fully redundant value: ");
3331 print_pre_expr (dump_file, expr);
3332 fprintf (dump_file, "\n");
3333 }
3334 continue;
3335 }
3336
3337 FOR_EACH_EDGE (pred, ei, block->preds)for ((ei) = ei_start_1 (&((block->preds))); ei_cond ((
ei), &(pred)); ei_next (&(ei)))
3338 {
3339 unsigned int vprime;
3340
3341 /* We should never run insertion for the exit block
3342 and so not come across fake pred edges. */
3343 gcc_assert (!(pred->flags & EDGE_FAKE))((void)(!(!(pred->flags & EDGE_FAKE)) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 3343, __FUNCTION__), 0 : 0))
;
3344 bprime = pred->src;
3345 /* We are looking at ANTIC_OUT of bprime. */
3346 eprime = phi_translate (NULLnullptr, expr, ANTIC_IN (block)((bb_value_sets_t) ((block)->aux))->antic_in, NULLnullptr, pred);
3347
3348 /* eprime will generally only be NULL if the
3349 value of the expression, translated
3350 through the PHI for this predecessor, is
3351 undefined. If that is the case, we can't
3352 make the expression fully redundant,
3353 because its value is undefined along a
3354 predecessor path. We can thus break out
3355 early because it doesn't matter what the
3356 rest of the results are. */
3357 if (eprime == NULLnullptr)
3358 {
3359 avail[pred->dest_idx] = NULLnullptr;
3360 cant_insert = true;
3361 break;
3362 }
3363
3364 vprime = get_expr_value_id (eprime);
3365 edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime)((bb_value_sets_t) ((bprime)->aux))->avail_out,
3366 vprime);
3367 if (edoubleprime == NULLnullptr)
3368 {
3369 avail[pred->dest_idx] = eprime;
3370 all_same = false;
3371 }
3372 else
3373 {
3374 avail[pred->dest_idx] = edoubleprime;
3375 by_some = true;
3376 /* We want to perform insertions to remove a redundancy on
3377 a path in the CFG we want to optimize for speed. */
3378 if (optimize_edge_for_speed_p (pred))
3379 do_insertion = true;
3380 if (first_s == NULLnullptr)
3381 first_s = edoubleprime;
3382 else if (!pre_expr_d::equal (first_s, edoubleprime))
3383 all_same = false;
3384 }
3385 }
3386 /* If we can insert it, it's not the same value
3387 already existing along every predecessor, and
3388 it's defined by some predecessor, it is
3389 partially redundant. */
3390 if (!cant_insert && !all_same && by_some)
3391 {
3392 if (!do_insertion)
3393 {
3394 if (dump_file && (dump_flags & TDF_DETAILS))
3395 {
3396 fprintf (dump_file, "Skipping partial redundancy for "
3397 "expression ");
3398 print_pre_expr (dump_file, expr);
3399 fprintf (dump_file, " (%04d), no redundancy on to be "
3400 "optimized for speed edge\n", val);
3401 }
3402 }
3403 else if (dbg_cnt (treepre_insert))
3404 {
3405 if (dump_file && (dump_flags & TDF_DETAILS))
3406 {
3407 fprintf (dump_file, "Found partial redundancy for "
3408 "expression ");
3409 print_pre_expr (dump_file, expr);
3410 fprintf (dump_file, " (%04d)\n",
3411 get_expr_value_id (expr));
3412 }
3413 if (insert_into_preds_of_block (block,
3414 get_expression_id (expr),
3415 avail))
3416 new_stuff = true;
3417 }
3418 }
3419 /* If all edges produce the same value and that value is
3420 an invariant, then the PHI has the same value on all
3421 edges. Note this. */
3422 else if (!cant_insert
3423 && all_same
3424 && (edoubleprime->kind != NAME
3425 || !SSA_NAME_OCCURS_IN_ABNORMAL_PHI(tree_check (((edoubleprime)->u.name), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 3426, __FUNCTION__, (SSA_NAME)))->base.asm_written_flag
3426 (PRE_EXPR_NAME (edoubleprime))(tree_check (((edoubleprime)->u.name), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 3426, __FUNCTION__, (SSA_NAME)))->base.asm_written_flag
))
3427 {
3428 gcc_assert (edoubleprime->kind == CONSTANT((void)(!(edoubleprime->kind == CONSTANT || edoubleprime->
kind == NAME) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 3429, __FUNCTION__), 0 : 0))
3429 || edoubleprime->kind == NAME)((void)(!(edoubleprime->kind == CONSTANT || edoubleprime->
kind == NAME) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 3429, __FUNCTION__), 0 : 0))
;
3430
3431 tree temp = make_temp_ssa_name (get_expr_type (expr),
3432 NULLnullptr, "pretmp");
3433 gassign *assign
3434 = gimple_build_assign (temp,
3435 edoubleprime->kind == CONSTANT ?
3436 PRE_EXPR_CONSTANT (edoubleprime)(edoubleprime)->u.constant :
3437 PRE_EXPR_NAME (edoubleprime)(edoubleprime)->u.name);
3438 gimple_stmt_iterator gsi = gsi_after_labels (block);
3439 gsi_insert_before (&gsi, assign, GSI_NEW_STMT);
3440
3441 vn_ssa_aux_t vn_info = VN_INFO (temp);
3442 vn_info->value_id = val;
3443 vn_info->valnum = vn_valnum_from_value_id (val);
3444 if (vn_info->valnum == NULL_TREE(tree) nullptr)
3445 vn_info->valnum = temp;
3446 bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (temp)(tree_check ((temp), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 3446, __FUNCTION__, (SSA_NAME)))->base.u.version
);
3447 pre_expr newe = get_or_alloc_expr_for_name (temp);
3448 add_to_value (val, newe);
3449 bitmap_value_replace_in_set (AVAIL_OUT (block)((bb_value_sets_t) ((block)->aux))->avail_out, newe);
3450 bitmap_insert_into_set (NEW_SETS (block)((bb_value_sets_t) ((block)->aux))->new_sets, newe);
3451 bitmap_insert_into_set (PHI_GEN (block)((bb_value_sets_t) ((block)->aux))->phi_gen, newe);
3452 }
3453 }
3454 }
3455
3456 return new_stuff;
3457}
3458
3459
3460/* Perform insertion for partially anticipatable expressions. There
3461 is only one case we will perform insertion for these. This case is
3462 if the expression is partially anticipatable, and fully available.
3463 In this case, we know that putting it earlier will enable us to
3464 remove the later computation. */
3465
3466static bool
3467do_pre_partial_partial_insertion (basic_block block, basic_block dom,
3468 vec<pre_expr> exprs)
3469{
3470 bool new_stuff = false;
3471 pre_expr expr;
3472 auto_vec<pre_expr, 2> avail;
3473 int i;
3474
3475 avail.safe_grow (EDGE_COUNT (block->preds)vec_safe_length (block->preds), true);
3476
3477 FOR_EACH_VEC_ELT (exprs, i, expr)for (i = 0; (exprs).iterate ((i), &(expr)); ++(i))
3478 {
3479 if (expr->kind == NARY
3480 || expr->kind == REFERENCE)
3481 {
3482 unsigned int val;
3483 bool by_all = true;
3484 bool cant_insert = false;
3485 edge pred;
3486 basic_block bprime;
3487 pre_expr eprime = NULLnullptr;
3488 edge_iterator ei;
3489
3490 val = get_expr_value_id (expr);
3491 if (bitmap_set_contains_value (PHI_GEN (block)((bb_value_sets_t) ((block)->aux))->phi_gen, val))
3492 continue;
3493 if (bitmap_set_contains_value (AVAIL_OUT (dom)((bb_value_sets_t) ((dom)->aux))->avail_out, val))
3494 continue;
3495
3496 FOR_EACH_EDGE (pred, ei, block->preds)for ((ei) = ei_start_1 (&((block->preds))); ei_cond ((
ei), &(pred)); ei_next (&(ei)))
3497 {
3498 unsigned int vprime;
3499 pre_expr edoubleprime;
3500
3501 /* We should never run insertion for the exit block
3502 and so not come across fake pred edges. */
3503 gcc_assert (!(pred->flags & EDGE_FAKE))((void)(!(!(pred->flags & EDGE_FAKE)) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 3503, __FUNCTION__), 0 : 0))
;
3504 bprime = pred->src;
3505 eprime = phi_translate (NULLnullptr, expr, ANTIC_IN (block)((bb_value_sets_t) ((block)->aux))->antic_in,
3506 PA_IN (block)((bb_value_sets_t) ((block)->aux))->pa_in, pred);
3507
3508 /* eprime will generally only be NULL if the
3509 value of the expression, translated
3510 through the PHI for this predecessor, is
3511 undefined. If that is the case, we can't
3512 make the expression fully redundant,
3513 because its value is undefined along a
3514 predecessor path. We can thus break out
3515 early because it doesn't matter what the
3516 rest of the results are. */
3517 if (eprime == NULLnullptr)
3518 {
3519 avail[pred->dest_idx] = NULLnullptr;
3520 cant_insert = true;
3521 break;
3522 }
3523
3524 vprime = get_expr_value_id (eprime);
3525 edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime)((bb_value_sets_t) ((bprime)->aux))->avail_out, vprime);
3526 avail[pred->dest_idx] = edoubleprime;
3527 if (edoubleprime == NULLnullptr)
3528 {
3529 by_all = false;
3530 break;
3531 }
3532 }
3533
3534 /* If we can insert it, it's not the same value
3535 already existing along every predecessor, and
3536 it's defined by some predecessor, it is
3537 partially redundant. */
3538 if (!cant_insert && by_all)
3539 {
3540 edge succ;
3541 bool do_insertion = false;
3542
3543 /* Insert only if we can remove a later expression on a path
3544 that we want to optimize for speed.
3545 The phi node that we will be inserting in BLOCK is not free,
3546 and inserting it for the sake of !optimize_for_speed successor
3547 may cause regressions on the speed path. */
3548 FOR_EACH_EDGE (succ, ei, block->succs)for ((ei) = ei_start_1 (&((block->succs))); ei_cond ((
ei), &(succ)); ei_next (&(ei)))
3549 {
3550 if (bitmap_set_contains_value (PA_IN (succ->dest)((bb_value_sets_t) ((succ->dest)->aux))->pa_in, val)
3551 || bitmap_set_contains_value (ANTIC_IN (succ->dest)((bb_value_sets_t) ((succ->dest)->aux))->antic_in, val))
3552 {
3553 if (optimize_edge_for_speed_p (succ))
3554 do_insertion = true;
3555 }
3556 }
3557
3558 if (!do_insertion)
3559 {
3560 if (dump_file && (dump_flags & TDF_DETAILS))
3561 {
3562 fprintf (dump_file, "Skipping partial partial redundancy "
3563 "for expression ");
3564 print_pre_expr (dump_file, expr);
3565 fprintf (dump_file, " (%04d), not (partially) anticipated "
3566 "on any to be optimized for speed edges\n", val);
3567 }
3568 }
3569 else if (dbg_cnt (treepre_insert))
3570 {
3571 pre_stats.pa_insert++;
3572 if (dump_file && (dump_flags & TDF_DETAILS))
3573 {
3574 fprintf (dump_file, "Found partial partial redundancy "
3575 "for expression ");
3576 print_pre_expr (dump_file, expr);
3577 fprintf (dump_file, " (%04d)\n",
3578 get_expr_value_id (expr));
3579 }
3580 if (insert_into_preds_of_block (block,
3581 get_expression_id (expr),
3582 avail))
3583 new_stuff = true;
3584 }
3585 }
3586 }
3587 }
3588
3589 return new_stuff;
3590}
3591
3592/* Insert expressions in BLOCK to compute hoistable values up.
3593 Return TRUE if something was inserted, otherwise return FALSE.
3594 The caller has to make sure that BLOCK has at least two successors. */
3595
3596static bool
3597do_hoist_insertion (basic_block block)
3598{
3599 edge e;
3600 edge_iterator ei;
3601 bool new_stuff = false;
3602 unsigned i;
3603 gimple_stmt_iterator last;
3604
3605 /* At least two successors, or else... */
3606 gcc_assert (EDGE_COUNT (block->succs) >= 2)((void)(!(vec_safe_length (block->succs) >= 2) ? fancy_abort
("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 3606, __FUNCTION__), 0 : 0))
;
3607
3608 /* Check that all successors of BLOCK are dominated by block.
3609 We could use dominated_by_p() for this, but actually there is a much
3610 quicker check: any successor that is dominated by BLOCK can't have
3611 more than one predecessor edge. */
3612 FOR_EACH_EDGE (e, ei, block->succs)for ((ei) = ei_start_1 (&((block->succs))); ei_cond ((
ei), &(e)); ei_next (&(ei)))
3613 if (! single_pred_p (e->dest))
3614 return false;
3615
3616 /* Determine the insertion point. If we cannot safely insert before
3617 the last stmt if we'd have to, bail out. */
3618 last = gsi_last_bb (block);
3619 if (!gsi_end_p (last)
3620 && !is_ctrl_stmt (gsi_stmt (last))
3621 && stmt_ends_bb_p (gsi_stmt (last)))
3622 return false;
3623
3624 /* Compute the set of hoistable expressions from ANTIC_IN. First compute
3625 hoistable values. */
3626 bitmap_set hoistable_set;
3627
3628 /* A hoistable value must be in ANTIC_IN(block)
3629 but not in AVAIL_OUT(BLOCK). */
3630 bitmap_initialize (&hoistable_set.values, &grand_bitmap_obstack);
3631 bitmap_and_compl (&hoistable_set.values,
3632 &ANTIC_IN (block)((bb_value_sets_t) ((block)->aux))->antic_in->values, &AVAIL_OUT (block)((bb_value_sets_t) ((block)->aux))->avail_out->values);
3633
3634 /* Short-cut for a common case: hoistable_set is empty. */
3635 if (bitmap_empty_p (&hoistable_set.values))
3636 return false;
3637
3638 /* Compute which of the hoistable values is in AVAIL_OUT of
3639 at least one of the successors of BLOCK. */
3640 bitmap_head availout_in_some;
3641 bitmap_initialize (&availout_in_some, &grand_bitmap_obstack);
3642 FOR_EACH_EDGE (e, ei, block->succs)for ((ei) = ei_start_1 (&((block->succs))); ei_cond ((
ei), &(e)); ei_next (&(ei)))
3643 /* Do not consider expressions solely because their availability
3644 on loop exits. They'd be ANTIC-IN throughout the whole loop
3645 and thus effectively hoisted across loops by combination of
3646 PRE and hoisting. */
3647 if (! loop_exit_edge_p (block->loop_father, e))
3648 bitmap_ior_and_into (&availout_in_some, &hoistable_set.values,
3649 &AVAIL_OUT (e->dest)((bb_value_sets_t) ((e->dest)->aux))->avail_out->values);
3650 bitmap_clear (&hoistable_set.values);
3651
3652 /* Short-cut for a common case: availout_in_some is empty. */
3653 if (bitmap_empty_p (&availout_in_some))
3654 return false;
3655
3656 /* Hack hoitable_set in-place so we can use sorted_array_from_bitmap_set. */
3657 bitmap_move (&hoistable_set.values, &availout_in_some);
3658 hoistable_set.expressions = ANTIC_IN (block)((bb_value_sets_t) ((block)->aux))->antic_in->expressions;
3659
3660 /* Now finally construct the topological-ordered expression set. */
3661 vec<pre_expr> exprs = sorted_array_from_bitmap_set (&hoistable_set);
3662
3663 bitmap_clear (&hoistable_set.values);
3664
3665 /* If there are candidate values for hoisting, insert expressions
3666 strategically to make the hoistable expressions fully redundant. */
3667 pre_expr expr;
3668 FOR_EACH_VEC_ELT (exprs, i, expr)for (i = 0; (exprs).iterate ((i), &(expr)); ++(i))
3669 {
3670 /* While we try to sort expressions topologically above the
3671 sorting doesn't work out perfectly. Catch expressions we
3672 already inserted. */
3673 unsigned int value_id = get_expr_value_id (expr);
3674 if (bitmap_set_contains_value (AVAIL_OUT (block)((bb_value_sets_t) ((block)->aux))->avail_out, value_id))
3675 {
3676 if (dump_file && (dump_flags & TDF_DETAILS))
3677 {
3678 fprintf (dump_file,
3679 "Already inserted expression for ");
3680 print_pre_expr (dump_file, expr);
3681 fprintf (dump_file, " (%04d)\n", value_id);
3682 }
3683 continue;
3684 }
3685
3686 /* If we end up with a punned expression representation and this
3687 happens to be a float typed one give up - we can't know for
3688 sure whether all paths perform the floating-point load we are
3689 about to insert and on some targets this can cause correctness
3690 issues. See PR88240. */
3691 if (expr->kind == REFERENCE
3692 && PRE_EXPR_REFERENCE (expr)(expr)->u.reference->punned
3693 && FLOAT_TYPE_P (get_expr_type (expr))((((enum tree_code) (get_expr_type (expr))->base.code) == REAL_TYPE
) || ((((enum tree_code) (get_expr_type (expr))->base.code
) == COMPLEX_TYPE || (((enum tree_code) (get_expr_type (expr)
)->base.code) == VECTOR_TYPE)) && (((enum tree_code
) (((contains_struct_check ((get_expr_type (expr)), (TS_TYPED
), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 3693, __FUNCTION__))->typed.type))->base.code) == REAL_TYPE
)))
)
3694 continue;
3695
3696 /* OK, we should hoist this value. Perform the transformation. */
3697 pre_stats.hoist_insert++;
3698 if (dump_file && (dump_flags & TDF_DETAILS))
3699 {
3700 fprintf (dump_file,
3701 "Inserting expression in block %d for code hoisting: ",
3702 block->index);
3703 print_pre_expr (dump_file, expr);
3704 fprintf (dump_file, " (%04d)\n", value_id);
3705 }
3706
3707 gimple_seq stmts = NULLnullptr;
3708 tree res = create_expression_by_pieces (block, expr, &stmts,
3709 get_expr_type (expr));
3710
3711 /* Do not return true if expression creation ultimately
3712 did not insert any statements. */
3713 if (gimple_seq_empty_p (stmts))
3714 res = NULL_TREE(tree) nullptr;
3715 else
3716 {
3717 if (gsi_end_p (last) || is_ctrl_stmt (gsi_stmt (last)))
3718 gsi_insert_seq_before (&last, stmts, GSI_SAME_STMT);
3719 else
3720 gsi_insert_seq_after (&last, stmts, GSI_NEW_STMT);
3721 }
3722
3723 /* Make sure to not return true if expression creation ultimately
3724 failed but also make sure to insert any stmts produced as they
3725 are tracked in inserted_exprs. */
3726 if (! res)
3727 continue;
3728
3729 new_stuff = true;
3730 }
3731
3732 exprs.release ();
3733
3734 return new_stuff;
3735}
3736
3737/* Perform insertion of partially redundant and hoistable values. */
3738
3739static void
3740insert (void)
3741{
3742 basic_block bb;
3743
3744 FOR_ALL_BB_FN (bb, cfun)for (bb = (((cfun + 0))->cfg->x_entry_block_ptr); bb; bb
= bb->next_bb)
3745 NEW_SETS (bb)((bb_value_sets_t) ((bb)->aux))->new_sets = bitmap_set_new ();
3746
3747 int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (cfun))((int *) xmalloc (sizeof (int) * ((((cfun + 0))->cfg->x_n_basic_blocks
))))
;
3748 int *bb_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun) + 1)((int *) xmalloc (sizeof (int) * ((((cfun + 0))->cfg->x_last_basic_block
) + 1)))
;
3749 int rpo_num = pre_and_rev_post_order_compute (NULLnullptr, rpo, false);
3750 for (int i = 0; i < rpo_num; ++i)
3751 bb_rpo[rpo[i]] = i;
3752
3753 int num_iterations = 0;
3754 bool changed;
3755 do
3756 {
3757 num_iterations++;
3758 if (dump_file && dump_flags & TDF_DETAILS)
3759 fprintf (dump_file, "Starting insert iteration %d\n", num_iterations);
3760
3761 changed = false;
3762 for (int idx = 0; idx < rpo_num; ++idx)
3763 {
3764 basic_block block = BASIC_BLOCK_FOR_FN (cfun, rpo[idx])((*(((cfun + 0))->cfg->x_basic_block_info))[(rpo[idx])]
)
;
3765 basic_block dom = get_immediate_dominator (CDI_DOMINATORS, block);
3766 if (dom)
3767 {
3768 unsigned i;
3769 bitmap_iterator bi;
3770 bitmap_set_t newset;
3771
3772 /* First, update the AVAIL_OUT set with anything we may have
3773 inserted higher up in the dominator tree. */
3774 newset = NEW_SETS (dom)((bb_value_sets_t) ((dom)->aux))->new_sets;
3775
3776 /* Note that we need to value_replace both NEW_SETS, and
3777 AVAIL_OUT. For both the case of NEW_SETS, the value may be
3778 represented by some non-simple expression here that we want
3779 to replace it with. */
3780 bool avail_out_changed = false;
3781 FOR_EACH_EXPR_ID_IN_SET (newset, i, bi)for (bmp_iter_set_init (&((bi)), (&(newset)->expressions
), (0), &((i))); bmp_iter_set (&((bi)), &((i))); bmp_iter_next
(&((bi)), &((i))))
3782 {
3783 pre_expr expr = expression_for_id (i);
3784 bitmap_value_replace_in_set (NEW_SETS (block)((bb_value_sets_t) ((block)->aux))->new_sets, expr);
3785 avail_out_changed
3786 |= bitmap_value_replace_in_set (AVAIL_OUT (block)((bb_value_sets_t) ((block)->aux))->avail_out, expr);
3787 }
3788 /* We need to iterate if AVAIL_OUT of an already processed
3789 block source changed. */
3790 if (avail_out_changed && !changed)
3791 {
3792 edge_iterator ei;
3793 edge e;
3794 FOR_EACH_EDGE (e, ei, block->succs)for ((ei) = ei_start_1 (&((block->succs))); ei_cond ((
ei), &(e)); ei_next (&(ei)))
3795 if (e->dest->index != EXIT_BLOCK(1)
3796 && bb_rpo[e->dest->index] < idx)
3797 changed = true;
3798 }
3799
3800 /* Insert expressions for partial redundancies. */
3801 if (flag_tree_preglobal_options.x_flag_tree_pre && !single_pred_p (block))
3802 {
3803 vec<pre_expr> exprs
3804 = sorted_array_from_bitmap_set (ANTIC_IN (block)((bb_value_sets_t) ((block)->aux))->antic_in);
3805 /* Sorting is not perfect, iterate locally. */
3806 while (do_pre_regular_insertion (block, dom, exprs))
3807 ;
3808 exprs.release ();
3809 if (do_partial_partial)
3810 {
3811 exprs = sorted_array_from_bitmap_set (PA_IN (block)((bb_value_sets_t) ((block)->aux))->pa_in);
3812 while (do_pre_partial_partial_insertion (block, dom,
3813 exprs))
3814 ;
3815 exprs.release ();
3816 }
3817 }
3818 }
3819 }
3820
3821 /* Clear the NEW sets before the next iteration. We have already
3822 fully propagated its contents. */
3823 if (changed)
3824 FOR_ALL_BB_FN (bb, cfun)for (bb = (((cfun + 0))->cfg->x_entry_block_ptr); bb; bb
= bb->next_bb)
3825 bitmap_set_free (NEW_SETS (bb)((bb_value_sets_t) ((bb)->aux))->new_sets);
3826 }
3827 while (changed);
3828
3829 statistics_histogram_event (cfun(cfun + 0), "insert iterations", num_iterations);
3830
3831 /* AVAIL_OUT is not needed after insertion so we don't have to
3832 propagate NEW_SETS from hoist insertion. */
3833 FOR_ALL_BB_FN (bb, cfun)for (bb = (((cfun + 0))->cfg->x_entry_block_ptr); bb; bb
= bb->next_bb)
3834 {
3835 bitmap_set_free (NEW_SETS (bb)((bb_value_sets_t) ((bb)->aux))->new_sets);
3836 bitmap_set_pool.remove (NEW_SETS (bb)((bb_value_sets_t) ((bb)->aux))->new_sets);
3837 NEW_SETS (bb)((bb_value_sets_t) ((bb)->aux))->new_sets = NULLnullptr;
3838 }
3839
3840 /* Insert expressions for hoisting. Do a backward walk here since
3841 inserting into BLOCK exposes new opportunities in its predecessors.
3842 Since PRE and hoist insertions can cause back-to-back iteration
3843 and we are interested in PRE insertion exposed hoisting opportunities
3844 but not in hoisting exposed PRE ones do hoist insertion only after
3845 PRE insertion iteration finished and do not iterate it. */
3846 if (flag_code_hoistingglobal_options.x_flag_code_hoisting)
3847 for (int idx = rpo_num - 1; idx >= 0; --idx)
3848 {
3849 basic_block block = BASIC_BLOCK_FOR_FN (cfun, rpo[idx])((*(((cfun + 0))->cfg->x_basic_block_info))[(rpo[idx])]
)
;
3850 if (EDGE_COUNT (block->succs)vec_safe_length (block->succs) >= 2)
3851 changed |= do_hoist_insertion (block);
3852 }
3853
3854 free (rpo);
3855 free (bb_rpo);
3856}
3857
3858
3859/* Compute the AVAIL set for all basic blocks.
3860
3861 This function performs value numbering of the statements in each basic
3862 block. The AVAIL sets are built from information we glean while doing
3863 this value numbering, since the AVAIL sets contain only one entry per
3864 value.
3865
3866 AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
3867 AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */
3868
3869static void
3870compute_avail (function *fun)
3871{
3872
3873 basic_block block, son;
3874 basic_block *worklist;
3875 size_t sp = 0;
3876 unsigned i;
3877 tree name;
3878
3879 /* We pretend that default definitions are defined in the entry block.
3880 This includes function arguments and the static chain decl. */
3881 FOR_EACH_SSA_NAME (i, name, fun)for (i = 1; (fun)->gimple_df->ssa_names->iterate (i,
&name); ++i) if (name)
3882 {
3883 pre_expr e;
3884 if (!SSA_NAME_IS_DEFAULT_DEF (name)(tree_check ((name), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 3884, __FUNCTION__, (SSA_NAME)))->base.default_def_flag
3885 || has_zero_uses (name)
3886 || virtual_operand_p (name))
3887 continue;
3888
3889 e = get_or_alloc_expr_for_name (name);
3890 add_to_value (get_expr_value_id (e), e);
3891 bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR_FOR_FN (fun))((bb_value_sets_t) ((((fun)->cfg->x_entry_block_ptr))->
aux))->tmp_gen
, e);
3892 bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR_FOR_FN (fun))((bb_value_sets_t) ((((fun)->cfg->x_entry_block_ptr))->
aux))->avail_out
,
3893 e);
3894 }
3895
3896 if (dump_file && (dump_flags & TDF_DETAILS))
3897 {
3898 print_bitmap_set (dump_file, TMP_GEN (ENTRY_BLOCK_PTR_FOR_FN (fun))((bb_value_sets_t) ((((fun)->cfg->x_entry_block_ptr))->
aux))->tmp_gen
,
3899 "tmp_gen", ENTRY_BLOCK(0));
3900 print_bitmap_set (dump_file, AVAIL_OUT (ENTRY_BLOCK_PTR_FOR_FN (fun))((bb_value_sets_t) ((((fun)->cfg->x_entry_block_ptr))->
aux))->avail_out
,
3901 "avail_out", ENTRY_BLOCK(0));
3902 }
3903
3904 /* Allocate the worklist. */
3905 worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun))((basic_block *) xmalloc (sizeof (basic_block) * (((fun)->
cfg->x_n_basic_blocks))))
;
3906
3907 /* Seed the algorithm by putting the dominator children of the entry
3908 block on the worklist. */
3909 for (son = first_dom_son (CDI_DOMINATORS, ENTRY_BLOCK_PTR_FOR_FN (fun)((fun)->cfg->x_entry_block_ptr));
3910 son;
3911 son = next_dom_son (CDI_DOMINATORS, son))
3912 worklist[sp++] = son;
3913
3914 BB_LIVE_VOP_ON_EXIT (ENTRY_BLOCK_PTR_FOR_FN (fun))((bb_value_sets_t) ((((fun)->cfg->x_entry_block_ptr))->
aux))->vop_on_exit
3915 = ssa_default_def (fun, gimple_vop (fun));
3916
3917 /* Loop until the worklist is empty. */
3918 while (sp)
3919 {
3920 gimple *stmt;
3921 basic_block dom;
3922
3923 /* Pick a block from the worklist. */
3924 block = worklist[--sp];
3925 vn_context_bb = block;
3926
3927 /* Initially, the set of available values in BLOCK is that of
3928 its immediate dominator. */
3929 dom = get_immediate_dominator (CDI_DOMINATORS, block);
3930 if (dom)
3931 {
3932 bitmap_set_copy (AVAIL_OUT (block)((bb_value_sets_t) ((block)->aux))->avail_out, AVAIL_OUT (dom)((bb_value_sets_t) ((dom)->aux))->avail_out);
3933 BB_LIVE_VOP_ON_EXIT (block)((bb_value_sets_t) ((block)->aux))->vop_on_exit = BB_LIVE_VOP_ON_EXIT (dom)((bb_value_sets_t) ((dom)->aux))->vop_on_exit;
3934 }
3935
3936 /* Generate values for PHI nodes. */
3937 for (gphi_iterator gsi = gsi_start_phis (block); !gsi_end_p (gsi);
3938 gsi_next (&gsi))
3939 {
3940 tree result = gimple_phi_result (gsi.phi ());
3941
3942 /* We have no need for virtual phis, as they don't represent
3943 actual computations. */
3944 if (virtual_operand_p (result))
3945 {
3946 BB_LIVE_VOP_ON_EXIT (block)((bb_value_sets_t) ((block)->aux))->vop_on_exit = result;
3947 continue;
3948 }
3949
3950 pre_expr e = get_or_alloc_expr_for_name (result);
3951 add_to_value (get_expr_value_id (e), e);
3952 bitmap_value_insert_into_set (AVAIL_OUT (block)((bb_value_sets_t) ((block)->aux))->avail_out, e);
3953 bitmap_insert_into_set (PHI_GEN (block)((bb_value_sets_t) ((block)->aux))->phi_gen, e);
3954 }
3955
3956 BB_MAY_NOTRETURN (block)((bb_value_sets_t) ((block)->aux))->contains_may_not_return_call = 0;
3957
3958 /* Now compute value numbers and populate value sets with all
3959 the expressions computed in BLOCK. */
3960 bool set_bb_may_notreturn = false;
3961 for (gimple_stmt_iterator gsi = gsi_start_bb (block); !gsi_end_p (gsi);
3962 gsi_next (&gsi))
3963 {
3964 ssa_op_iter iter;
3965 tree op;
3966
3967 stmt = gsi_stmt (gsi);
3968
3969 if (set_bb_may_notreturn)
3970 {
3971 BB_MAY_NOTRETURN (block)((bb_value_sets_t) ((block)->aux))->contains_may_not_return_call = 1;
3972 set_bb_may_notreturn = false;
3973 }
3974
3975 /* Cache whether the basic-block has any non-visible side-effect
3976 or control flow.
3977 If this isn't a call or it is the last stmt in the
3978 basic-block then the CFG represents things correctly. */
3979 if (is_gimple_call (stmt) && !stmt_ends_bb_p (stmt))
3980 {
3981 /* Non-looping const functions always return normally.
3982 Otherwise the call might not return or have side-effects
3983 that forbids hoisting possibly trapping expressions
3984 before it. */
3985 int flags = gimple_call_flags (stmt);
3986 if (!(flags & (ECF_CONST(1 << 0)|ECF_PURE(1 << 1)))
3987 || (flags & ECF_LOOPING_CONST_OR_PURE(1 << 2))
3988 || stmt_can_throw_external (fun, stmt))
3989 /* Defer setting of BB_MAY_NOTRETURN to avoid it
3990 influencing the processing of the call itself. */
3991 set_bb_may_notreturn = true;
3992 }
3993
3994 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)for (op = op_iter_init_tree (&(iter), stmt, 0x02); !op_iter_done
(&(iter)); (void) (op = op_iter_next_tree (&(iter)))
)
3995 {
3996 pre_expr e = get_or_alloc_expr_for_name (op);
3997
3998 add_to_value (get_expr_value_id (e), e);
3999 bitmap_insert_into_set (TMP_GEN (block)((bb_value_sets_t) ((block)->aux))->tmp_gen, e);
4000 bitmap_value_insert_into_set (AVAIL_OUT (block)((bb_value_sets_t) ((block)->aux))->avail_out, e);
4001 }
4002
4003 if (gimple_vdef (stmt))
4004 BB_LIVE_VOP_ON_EXIT (block)((bb_value_sets_t) ((block)->aux))->vop_on_exit = gimple_vdef (stmt);
4005
4006 if (gimple_has_side_effects (stmt)
4007 || stmt_could_throw_p (fun, stmt)
4008 || is_gimple_debug (stmt))
4009 continue;
4010
4011 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)for (op = op_iter_init_tree (&(iter), stmt, 0x01); !op_iter_done
(&(iter)); (void) (op = op_iter_next_tree (&(iter)))
)
4012 {
4013 if (ssa_undefined_value_p (op))
4014 continue;
4015 pre_expr e = get_or_alloc_expr_for_name (op);
4016 bitmap_value_insert_into_set (EXP_GEN (block)((bb_value_sets_t) ((block)->aux))->exp_gen, e);
4017 }
4018
4019 switch (gimple_code (stmt))
4020 {
4021 case GIMPLE_RETURN:
4022 continue;
4023
4024 case GIMPLE_CALL:
4025 {
4026 vn_reference_t ref;
4027 vn_reference_s ref1;
4028 pre_expr result = NULLnullptr;
4029
4030 vn_reference_lookup_call (as_a <gcall *> (stmt), &ref, &ref1);
4031 /* There is no point to PRE a call without a value. */
4032 if (!ref || !ref->result)
4033 continue;
4034
4035 /* If the value of the call is not invalidated in
4036 this block until it is computed, add the expression
4037 to EXP_GEN. */
4038 if ((!gimple_vuse (stmt)
4039 || gimple_code
4040 (SSA_NAME_DEF_STMT (gimple_vuse (stmt))(tree_check ((gimple_vuse (stmt)), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 4040, __FUNCTION__, (SSA_NAME)))->ssa_name.def_stmt
) == GIMPLE_PHI
4041 || gimple_bb (SSA_NAME_DEF_STMT(tree_check ((gimple_vuse (stmt)), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 4042, __FUNCTION__, (SSA_NAME)))->ssa_name.def_stmt
4042 (gimple_vuse (stmt))(tree_check ((gimple_vuse (stmt)), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 4042, __FUNCTION__, (SSA_NAME)))->ssa_name.def_stmt
) != block)
4043 /* If the REFERENCE traps and there was a preceding
4044 point in the block that might not return avoid
4045 adding the reference to EXP_GEN. */
4046 && (!BB_MAY_NOTRETURN (block)((bb_value_sets_t) ((block)->aux))->contains_may_not_return_call
4047 || !vn_reference_may_trap (ref)))
4048 {
4049 result = get_or_alloc_expr_for_reference
4050 (ref, gimple_location (stmt));
4051 add_to_value (get_expr_value_id (result), result);
4052 bitmap_value_insert_into_set (EXP_GEN (block)((bb_value_sets_t) ((block)->aux))->exp_gen, result);
4053 }
4054 continue;
4055 }
4056
4057 case GIMPLE_ASSIGN:
4058 {
4059 pre_expr result = NULLnullptr;
4060 switch (vn_get_stmt_kind (stmt))
4061 {
4062 case VN_NARY:
4063 {
4064 enum tree_code code = gimple_assign_rhs_code (stmt);
4065 vn_nary_op_t nary;
4066
4067 /* COND_EXPR is awkward in that it contains an
4068 embedded complex expression.
4069 Don't even try to shove it through PRE. */
4070 if (code == COND_EXPR)
4071 continue;
4072
4073 vn_nary_op_lookup_stmt (stmt, &nary);
4074 if (!nary || nary->predicated_values)
4075 continue;
4076
4077 /* If the NARY traps and there was a preceding
4078 point in the block that might not return avoid
4079 adding the nary to EXP_GEN. */
4080 if (BB_MAY_NOTRETURN (block)((bb_value_sets_t) ((block)->aux))->contains_may_not_return_call
4081 && vn_nary_may_trap (nary))
4082 continue;
4083
4084 result = get_or_alloc_expr_for_nary
4085 (nary, gimple_location (stmt));
4086 break;
4087 }
4088
4089 case VN_REFERENCE:
4090 {
4091 tree rhs1 = gimple_assign_rhs1 (stmt);
4092 ao_ref rhs1_ref;
4093 ao_ref_init (&rhs1_ref, rhs1);
4094 alias_set_type set = ao_ref_alias_set (&rhs1_ref);
4095 alias_set_type base_set
4096 = ao_ref_base_alias_set (&rhs1_ref);
4097 vec<vn_reference_op_s> operands
4098 = vn_reference_operands_for_lookup (rhs1);
4099 vn_reference_t ref;
4100 vn_reference_lookup_pieces (gimple_vuse (stmt), set,
4101 base_set, TREE_TYPE (rhs1)((contains_struct_check ((rhs1), (TS_TYPED), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 4101, __FUNCTION__))->typed.type)
,
4102 operands, &ref, VN_WALK);
4103 if (!ref)
4104 {
4105 operands.release ();
4106 continue;
4107 }
4108
4109 /* If the REFERENCE traps and there was a preceding
4110 point in the block that might not return avoid
4111 adding the reference to EXP_GEN. */
4112 if (BB_MAY_NOTRETURN (block)((bb_value_sets_t) ((block)->aux))->contains_may_not_return_call
4113 && vn_reference_may_trap (ref))
4114 {
4115 operands.release ();
4116 continue;
4117 }
4118
4119 /* If the value of the reference is not invalidated in
4120 this block until it is computed, add the expression
4121 to EXP_GEN. */
4122 if (gimple_vuse (stmt))
4123 {
4124 gimple *def_stmt;
4125 bool ok = true;
4126 def_stmt = SSA_NAME_DEF_STMT (gimple_vuse (stmt))(tree_check ((gimple_vuse (stmt)), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 4126, __FUNCTION__, (SSA_NAME)))->ssa_name.def_stmt
;
4127 while (!gimple_nop_p (def_stmt)
4128 && gimple_code (def_stmt) != GIMPLE_PHI
4129 && gimple_bb (def_stmt) == block)
4130 {
4131 if (stmt_may_clobber_ref_p
4132 (def_stmt, gimple_assign_rhs1 (stmt)))
4133 {
4134 ok = false;
4135 break;
4136 }
4137 def_stmt
4138 = SSA_NAME_DEF_STMT (gimple_vuse (def_stmt))(tree_check ((gimple_vuse (def_stmt)), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 4138, __FUNCTION__, (SSA_NAME)))->ssa_name.def_stmt
;
4139 }
4140 if (!ok)
4141 {
4142 operands.release ();
4143 continue;
4144 }
4145 }
4146
4147 /* If the load was value-numbered to another
4148 load make sure we do not use its expression
4149 for insertion if it wouldn't be a valid
4150 replacement. */
4151 /* At the momemt we have a testcase
4152 for hoist insertion of aligned vs. misaligned
4153 variants in gcc.dg/torture/pr65270-1.c thus
4154 with just alignment to be considered we can
4155 simply replace the expression in the hashtable
4156 with the most conservative one. */
4157 vn_reference_op_t ref1 = &ref->operands.last ();
4158 while (ref1->opcode != TARGET_MEM_REF
4159 && ref1->opcode != MEM_REF
4160 && ref1 != &ref->operands[0])
4161 --ref1;
4162 vn_reference_op_t ref2 = &operands.last ();
4163 while (ref2->opcode != TARGET_MEM_REF
4164 && ref2->opcode != MEM_REF
4165 && ref2 != &operands[0])
4166 --ref2;
4167 if ((ref1->opcode == TARGET_MEM_REF
4168 || ref1->opcode == MEM_REF)
4169 && (TYPE_ALIGN (ref1->type)(((tree_class_check ((ref1->type), (tcc_type), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 4169, __FUNCTION__))->type_common.align) ? ((unsigned)1)
<< (((tree_class_check ((ref1->type), (tcc_type), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 4169, __FUNCTION__))->type_common.align) - 1) : 0)
4170 > TYPE_ALIGN (ref2->type)(((tree_class_check ((ref2->type), (tcc_type), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 4170, __FUNCTION__))->type_common.align) ? ((unsigned)1)
<< (((tree_class_check ((ref2->type), (tcc_type), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 4170, __FUNCTION__))->type_common.align) - 1) : 0)
))
4171 ref1->type
4172 = build_aligned_type (ref1->type,
4173 TYPE_ALIGN (ref2->type)(((tree_class_check ((ref2->type), (tcc_type), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 4173, __FUNCTION__))->type_common.align) ? ((unsigned)1)
<< (((tree_class_check ((ref2->type), (tcc_type), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 4173, __FUNCTION__))->type_common.align) - 1) : 0)
);
4174 /* TBAA behavior is an obvious part so make sure
4175 that the hashtable one covers this as well
4176 by adjusting the ref alias set and its base. */
4177 if (ref->set == set
4178 || alias_set_subset_of (set, ref->set))
4179 ;
4180 else if (ref1->opcode != ref2->opcode
4181 || (ref1->opcode != MEM_REF
4182 && ref1->opcode != TARGET_MEM_REF))
4183 {
4184 /* With mismatching base opcodes or bases
4185 other than MEM_REF or TARGET_MEM_REF we
4186 can't do any easy TBAA adjustment. */
4187 operands.release ();
4188 continue;
4189 }
4190 else if (alias_set_subset_of (ref->set, set))
4191 {
4192 ref->set = set;
4193 if (ref1->opcode == MEM_REF)
4194 ref1->op0
4195 = wide_int_to_tree (TREE_TYPE (ref2->op0)((contains_struct_check ((ref2->op0), (TS_TYPED), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 4195, __FUNCTION__))->typed.type)
,
4196 wi::to_wide (ref1->op0));
4197 else
4198 ref1->op2
4199 = wide_int_to_tree (TREE_TYPE (ref2->op2)((contains_struct_check ((ref2->op2), (TS_TYPED), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 4199, __FUNCTION__))->typed.type)
,
4200 wi::to_wide (ref1->op2));
4201 }
4202 else
4203 {
4204 ref->set = 0;
4205 if (ref1->opcode == MEM_REF)
4206 ref1->op0
4207 = wide_int_to_tree (ptr_type_nodeglobal_trees[TI_PTR_TYPE],
4208 wi::to_wide (ref1->op0));
4209 else
4210 ref1->op2
4211 = wide_int_to_tree (ptr_type_nodeglobal_trees[TI_PTR_TYPE],
4212 wi::to_wide (ref1->op2));
4213 }
4214 operands.release ();
4215
4216 result = get_or_alloc_expr_for_reference
4217 (ref, gimple_location (stmt));
4218 break;
4219 }
4220
4221 default:
4222 continue;
4223 }
4224
4225 add_to_value (get_expr_value_id (result), result);
4226 bitmap_value_insert_into_set (EXP_GEN (block)((bb_value_sets_t) ((block)->aux))->exp_gen, result);
4227 continue;
4228 }
4229 default:
4230 break;
4231 }
4232 }
4233 if (set_bb_may_notreturn)
4234 {
4235 BB_MAY_NOTRETURN (block)((bb_value_sets_t) ((block)->aux))->contains_may_not_return_call = 1;
4236 set_bb_may_notreturn = false;
4237 }
4238
4239 if (dump_file && (dump_flags & TDF_DETAILS))
4240 {
4241 print_bitmap_set (dump_file, EXP_GEN (block)((bb_value_sets_t) ((block)->aux))->exp_gen,
4242 "exp_gen", block->index);
4243 print_bitmap_set (dump_file, PHI_GEN (block)((bb_value_sets_t) ((block)->aux))->phi_gen,
4244 "phi_gen", block->index);
4245 print_bitmap_set (dump_file, TMP_GEN (block)((bb_value_sets_t) ((block)->aux))->tmp_gen,
4246 "tmp_gen", block->index);
4247 print_bitmap_set (dump_file, AVAIL_OUT (block)((bb_value_sets_t) ((block)->aux))->avail_out,
4248 "avail_out", block->index);
4249 }
4250
4251 /* Put the dominator children of BLOCK on the worklist of blocks
4252 to compute available sets for. */
4253 for (son = first_dom_son (CDI_DOMINATORS, block);
4254 son;
4255 son = next_dom_son (CDI_DOMINATORS, son))
4256 worklist[sp++] = son;
4257 }
4258 vn_context_bb = NULLnullptr;
4259
4260 free (worklist);
4261}
4262
4263
4264/* Initialize data structures used by PRE. */
4265
4266static void
4267init_pre (void)
4268{
4269 basic_block bb;
4270
4271 next_expression_id = 1;
4272 expressions.create (0);
4273 expressions.safe_push (NULLnullptr);
4274 value_expressions.create (get_max_value_id () + 1);
4275 value_expressions.quick_grow_cleared (get_max_value_id () + 1);
4276 constant_value_expressions.create (get_max_constant_value_id () + 1);
4277 constant_value_expressions.quick_grow_cleared (get_max_constant_value_id () + 1);
4278 name_to_id.create (0);
4279
4280 inserted_exprs = BITMAP_ALLOCbitmap_alloc (NULLnullptr);
4281
4282 connect_infinite_loops_to_exit ();
4283 memset (&pre_stats, 0, sizeof (pre_stats));
4284
4285 alloc_aux_for_blocks (sizeof (struct bb_bitmap_sets));
4286
4287 calculate_dominance_info (CDI_DOMINATORS);
4288
4289 bitmap_obstack_initialize (&grand_bitmap_obstack);
4290 expression_to_id = new hash_table<pre_expr_d> (num_ssa_names(vec_safe_length ((cfun + 0)->gimple_df->ssa_names)) * 3);
4291 FOR_ALL_BB_FN (bb, cfun)for (bb = (((cfun + 0))->cfg->x_entry_block_ptr); bb; bb
= bb->next_bb)
4292 {
4293 EXP_GEN (bb)((bb_value_sets_t) ((bb)->aux))->exp_gen = bitmap_set_new ();
4294 PHI_GEN (bb)((bb_value_sets_t) ((bb)->aux))->phi_gen = bitmap_set_new ();
4295 TMP_GEN (bb)((bb_value_sets_t) ((bb)->aux))->tmp_gen = bitmap_set_new ();
4296 AVAIL_OUT (bb)((bb_value_sets_t) ((bb)->aux))->avail_out = bitmap_set_new ();
4297 PHI_TRANS_TABLE (bb)((bb_value_sets_t) ((bb)->aux))->phi_translate_table = NULLnullptr;
4298 }
4299}
4300
4301
4302/* Deallocate data structures used by PRE. */
4303
4304static void
4305fini_pre ()
4306{
4307 value_expressions.release ();
4308 constant_value_expressions.release ();
4309 expressions.release ();
4310 BITMAP_FREE (inserted_exprs)((void) (bitmap_obstack_free ((bitmap) inserted_exprs), (inserted_exprs
) = (bitmap) nullptr))
;
4311 bitmap_obstack_release (&grand_bitmap_obstack);
4312 bitmap_set_pool.release ();
4313 pre_expr_pool.release ();
4314 delete expression_to_id;
4315 expression_to_id = NULLnullptr;
4316 name_to_id.release ();
4317
4318 basic_block bb;
4319 FOR_ALL_BB_FN (bb, cfun)for (bb = (((cfun + 0))->cfg->x_entry_block_ptr); bb; bb
= bb->next_bb)
4320 if (bb->aux && PHI_TRANS_TABLE (bb)((bb_value_sets_t) ((bb)->aux))->phi_translate_table)
4321 delete PHI_TRANS_TABLE (bb)((bb_value_sets_t) ((bb)->aux))->phi_translate_table;
4322 free_aux_for_blocks ();
4323}
4324
4325namespace {
4326
4327const pass_data pass_data_pre =
4328{
4329 GIMPLE_PASS, /* type */
4330 "pre", /* name */
4331 OPTGROUP_NONE, /* optinfo_flags */
4332 TV_TREE_PRE, /* tv_id */
4333 ( PROP_cfg(1 << 3) | PROP_ssa(1 << 5) ), /* properties_required */
4334 0, /* properties_provided */
4335 0, /* properties_destroyed */
4336 TODO_rebuild_alias(1 << 20), /* todo_flags_start */
4337 0, /* todo_flags_finish */
4338};
4339
4340class pass_pre : public gimple_opt_pass
4341{
4342public:
4343 pass_pre (gcc::context *ctxt)
4344 : gimple_opt_pass (pass_data_pre, ctxt)
4345 {}
4346
4347 /* opt_pass methods: */
4348 virtual bool gate (function *)
4349 { return flag_tree_preglobal_options.x_flag_tree_pre != 0 || flag_code_hoistingglobal_options.x_flag_code_hoisting != 0; }
4350 virtual unsigned int execute (function *);
4351
4352}; // class pass_pre
4353
4354/* Valueization hook for RPO VN when we are calling back to it
4355 at ANTIC compute time. */
4356
4357static tree
4358pre_valueize (tree name)
4359{
4360 if (TREE_CODE (name)((enum tree_code) (name)->base.code) == SSA_NAME)
4361 {
4362 tree tem = VN_INFO (name)->valnum;
4363 if (tem != VN_TOP && tem != name)
4364 {
4365 if (TREE_CODE (tem)((enum tree_code) (tem)->base.code) != SSA_NAME
4366 || SSA_NAME_IS_DEFAULT_DEF (tem)(tree_check ((tem), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 4366, __FUNCTION__, (SSA_NAME)))->base.default_def_flag
)
4367 return tem;
4368 /* We create temporary SSA names for representatives that
4369 do not have a definition (yet) but are not default defs either
4370 assume they are fine to use. */
4371 basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (tem)(tree_check ((tem), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 4371, __FUNCTION__, (SSA_NAME)))->ssa_name.def_stmt
);
4372 if (! def_bb
4373 || dominated_by_p (CDI_DOMINATORS, vn_context_bb, def_bb))
4374 return tem;
4375 /* ??? Now we could look for a leader. Ideally we'd somehow
4376 expose RPO VN leaders and get rid of AVAIL_OUT as well... */
4377 }
4378 }
4379 return name;
4380}
4381
4382unsigned int
4383pass_pre::execute (function *fun)
4384{
4385 unsigned int todo = 0;
4386
4387 do_partial_partial =
4388 flag_tree_partial_preglobal_options.x_flag_tree_partial_pre && optimize_function_for_speed_p (fun);
4389
4390 /* This has to happen before VN runs because
4391 loop_optimizer_init may create new phis, etc. */
4392 loop_optimizer_init (LOOPS_NORMAL(LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
)
);
4393 split_edges_for_insertion ();
4394 scev_initialize ();
4395 calculate_dominance_info (CDI_DOMINATORS);
4396
4397 run_rpo_vn (VN_WALK);
4398
4399 init_pre ();
4400
4401 vn_valueize = pre_valueize;
4402
4403 /* Insert can get quite slow on an incredibly large number of basic
4404 blocks due to some quadratic behavior. Until this behavior is
4405 fixed, don't run it when he have an incredibly large number of
4406 bb's. If we aren't going to run insert, there is no point in
4407 computing ANTIC, either, even though it's plenty fast nor do
4408 we require AVAIL. */
4409 if (n_basic_blocks_for_fn (fun)((fun)->cfg->x_n_basic_blocks) < 4000)
4410 {
4411 compute_avail (fun);
4412 compute_antic ();
4413 insert ();
4414 }
4415
4416 /* Make sure to remove fake edges before committing our inserts.
4417 This makes sure we don't end up with extra critical edges that
4418 we would need to split. */
4419 remove_fake_exit_edges ();
4420 gsi_commit_edge_inserts ();
4421
4422 /* Eliminate folds statements which might (should not...) end up
4423 not keeping virtual operands up-to-date. */
4424 gcc_assert (!need_ssa_update_p (fun))((void)(!(!need_ssa_update_p (fun)) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-pre.c"
, 4424, __FUNCTION__), 0 : 0))
;
4425
4426 statistics_counter_event (fun, "Insertions", pre_stats.insertions);
4427 statistics_counter_event (fun, "PA inserted", pre_stats.pa_insert);
4428 statistics_counter_event (fun, "HOIST inserted", pre_stats.hoist_insert);
4429 statistics_counter_event (fun, "New PHIs", pre_stats.phis);
4430
4431 todo |= eliminate_with_rpo_vn (inserted_exprs);
4432
4433 vn_valueize = NULLnullptr;
4434
4435 /* Because we don't follow exactly the standard PRE algorithm, and decide not
4436 to insert PHI nodes sometimes, and because value numbering of casts isn't
4437 perfect, we sometimes end up inserting dead code. This simple DCE-like
4438 pass removes any insertions we made that weren't actually used. */
4439 simple_dce_from_worklist (inserted_exprs);
4440
4441 fini_pre ();
4442
4443 scev_finalize ();
4444 loop_optimizer_finalize ();
4445
4446 /* TODO: tail_merge_optimize may merge all predecessors of a block, in which
4447 case we can merge the block with the remaining predecessor of the block.
4448 It should either:
4449 - call merge_blocks after each tail merge iteration
4450 - call merge_blocks after all tail merge iterations
4451 - mark TODO_cleanup_cfg when necessary
4452 - share the cfg cleanup with fini_pre. */
4453 todo |= tail_merge_optimize (todo);
4454
4455 free_rpo_vn ();
4456
4457 /* Tail merging invalidates the virtual SSA web, together with
4458 cfg-cleanup opportunities exposed by PRE this will wreck the
4459 SSA updating machinery. So make sure to run update-ssa
4460 manually, before eventually scheduling cfg-cleanup as part of
4461 the todo. */
4462 update_ssa (TODO_update_ssa_only_virtuals(1 << 14));
4463
4464 return todo;
4465}
4466
4467} // anon namespace
4468
4469gimple_opt_pass *
4470make_pass_pre (gcc::context *ctxt)
4471{
4472 return new pass_pre (ctxt);
4473}

/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/vec.h

1/* Vector API for GNU compiler.
2 Copyright (C) 2004-2021 Free Software Foundation, Inc.
3 Contributed by Nathan Sidwell <nathan@codesourcery.com>
4 Re-implemented in C++ by Diego Novillo <dnovillo@google.com>
5
6This file is part of GCC.
7
8GCC is free software; you can redistribute it and/or modify it under
9the terms of the GNU General Public License as published by the Free
10Software Foundation; either version 3, or (at your option) any later
11version.
12
13GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14WARRANTY; without even the implied warranty of MERCHANTABILITY or
15FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16for 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#ifndef GCC_VEC_H
23#define GCC_VEC_H
24
25/* Some gen* file have no ggc support as the header file gtype-desc.h is
26 missing. Provide these definitions in case ggc.h has not been included.
27 This is not a problem because any code that runs before gengtype is built
28 will never need to use GC vectors.*/
29
30extern void ggc_free (void *);
31extern size_t ggc_round_alloc_size (size_t requested_size);
32extern void *ggc_realloc (void *, size_t MEM_STAT_DECL);
33
34/* Templated vector type and associated interfaces.
35
36 The interface functions are typesafe and use inline functions,
37 sometimes backed by out-of-line generic functions. The vectors are
38 designed to interoperate with the GTY machinery.
39
40 There are both 'index' and 'iterate' accessors. The index accessor
41 is implemented by operator[]. The iterator returns a boolean
42 iteration condition and updates the iteration variable passed by
43 reference. Because the iterator will be inlined, the address-of
44 can be optimized away.
45
46 Each operation that increases the number of active elements is
47 available in 'quick' and 'safe' variants. The former presumes that
48 there is sufficient allocated space for the operation to succeed
49 (it dies if there is not). The latter will reallocate the
50 vector, if needed. Reallocation causes an exponential increase in
51 vector size. If you know you will be adding N elements, it would
52 be more efficient to use the reserve operation before adding the
53 elements with the 'quick' operation. This will ensure there are at
54 least as many elements as you ask for, it will exponentially
55 increase if there are too few spare slots. If you want reserve a
56 specific number of slots, but do not want the exponential increase
57 (for instance, you know this is the last allocation), use the
58 reserve_exact operation. You can also create a vector of a
59 specific size from the get go.
60
61 You should prefer the push and pop operations, as they append and
62 remove from the end of the vector. If you need to remove several
63 items in one go, use the truncate operation. The insert and remove
64 operations allow you to change elements in the middle of the
65 vector. There are two remove operations, one which preserves the
66 element ordering 'ordered_remove', and one which does not
67 'unordered_remove'. The latter function copies the end element
68 into the removed slot, rather than invoke a memmove operation. The
69 'lower_bound' function will determine where to place an item in the
70 array using insert that will maintain sorted order.
71
72 Vectors are template types with three arguments: the type of the
73 elements in the vector, the allocation strategy, and the physical
74 layout to use
75
76 Four allocation strategies are supported:
77
78 - Heap: allocation is done using malloc/free. This is the
79 default allocation strategy.
80
81 - GC: allocation is done using ggc_alloc/ggc_free.
82
83 - GC atomic: same as GC with the exception that the elements
84 themselves are assumed to be of an atomic type that does
85 not need to be garbage collected. This means that marking
86 routines do not need to traverse the array marking the
87 individual elements. This increases the performance of
88 GC activities.
89
90 Two physical layouts are supported:
91
92 - Embedded: The vector is structured using the trailing array
93 idiom. The last member of the structure is an array of size
94 1. When the vector is initially allocated, a single memory
95 block is created to hold the vector's control data and the
96 array of elements. These vectors cannot grow without
97 reallocation (see discussion on embeddable vectors below).
98
99 - Space efficient: The vector is structured as a pointer to an
100 embedded vector. This is the default layout. It means that
101 vectors occupy a single word of storage before initial
102 allocation. Vectors are allowed to grow (the internal
103 pointer is reallocated but the main vector instance does not
104 need to relocate).
105
106 The type, allocation and layout are specified when the vector is
107 declared.
108
109 If you need to directly manipulate a vector, then the 'address'
110 accessor will return the address of the start of the vector. Also
111 the 'space' predicate will tell you whether there is spare capacity
112 in the vector. You will not normally need to use these two functions.
113
114 Notes on the different layout strategies
115
116 * Embeddable vectors (vec<T, A, vl_embed>)
117
118 These vectors are suitable to be embedded in other data
119 structures so that they can be pre-allocated in a contiguous
120 memory block.
121
122 Embeddable vectors are implemented using the trailing array
123 idiom, thus they are not resizeable without changing the address
124 of the vector object itself. This means you cannot have
125 variables or fields of embeddable vector type -- always use a
126 pointer to a vector. The one exception is the final field of a
127 structure, which could be a vector type.
128
129 You will have to use the embedded_size & embedded_init calls to
130 create such objects, and they will not be resizeable (so the
131 'safe' allocation variants are not available).
132
133 Properties of embeddable vectors:
134
135 - The whole vector and control data are allocated in a single
136 contiguous block. It uses the trailing-vector idiom, so
137 allocation must reserve enough space for all the elements
138 in the vector plus its control data.
139 - The vector cannot be re-allocated.
140 - The vector cannot grow nor shrink.
141 - No indirections needed for access/manipulation.
142 - It requires 2 words of storage (prior to vector allocation).
143
144
145 * Space efficient vector (vec<T, A, vl_ptr>)
146
147 These vectors can grow dynamically and are allocated together
148 with their control data. They are suited to be included in data
149 structures. Prior to initial allocation, they only take a single
150 word of storage.
151
152 These vectors are implemented as a pointer to embeddable vectors.
153 The semantics allow for this pointer to be NULL to represent
154 empty vectors. This way, empty vectors occupy minimal space in
155 the structure containing them.
156
157 Properties:
158
159 - The whole vector and control data are allocated in a single
160 contiguous block.
161 - The whole vector may be re-allocated.
162 - Vector data may grow and shrink.
163 - Access and manipulation requires a pointer test and
164 indirection.
165 - It requires 1 word of storage (prior to vector allocation).
166
167 An example of their use would be,
168
169 struct my_struct {
170 // A space-efficient vector of tree pointers in GC memory.
171 vec<tree, va_gc, vl_ptr> v;
172 };
173
174 struct my_struct *s;
175
176 if (s->v.length ()) { we have some contents }
177 s->v.safe_push (decl); // append some decl onto the end
178 for (ix = 0; s->v.iterate (ix, &elt); ix++)
179 { do something with elt }
180*/
181
182/* Support function for statistics. */
183extern void dump_vec_loc_statistics (void);
184
185/* Hashtable mapping vec addresses to descriptors. */
186extern htab_t vec_mem_usage_hash;
187
188/* Control data for vectors. This contains the number of allocated
189 and used slots inside a vector. */
190
191struct vec_prefix
192{
193 /* FIXME - These fields should be private, but we need to cater to
194 compilers that have stricter notions of PODness for types. */
195
196 /* Memory allocation support routines in vec.c. */
197 void register_overhead (void *, size_t, size_t CXX_MEM_STAT_INFO);
198 void release_overhead (void *, size_t, size_t, bool CXX_MEM_STAT_INFO);
199 static unsigned calculate_allocation (vec_prefix *, unsigned, bool);
200 static unsigned calculate_allocation_1 (unsigned, unsigned);
201
202 /* Note that vec_prefix should be a base class for vec, but we use
203 offsetof() on vector fields of tree structures (e.g.,
204 tree_binfo::base_binfos), and offsetof only supports base types.
205
206 To compensate, we make vec_prefix a field inside vec and make
207 vec a friend class of vec_prefix so it can access its fields. */
208 template <typename, typename, typename> friend struct vec;
209
210 /* The allocator types also need access to our internals. */
211 friend struct va_gc;
212 friend struct va_gc_atomic;
213 friend struct va_heap;
214
215 unsigned m_alloc : 31;
216 unsigned m_using_auto_storage : 1;
217 unsigned m_num;
218};
219
220/* Calculate the number of slots to reserve a vector, making sure that
221 RESERVE slots are free. If EXACT grow exactly, otherwise grow
222 exponentially. PFX is the control data for the vector. */
223
224inline unsigned
225vec_prefix::calculate_allocation (vec_prefix *pfx, unsigned reserve,
226 bool exact)
227{
228 if (exact
30.1
'exact' is false
30.1
'exact' is false
)
31
Taking false branch
229 return (pfx ? pfx->m_num : 0) + reserve;
230 else if (!pfx
31.1
'pfx' is null
31.1
'pfx' is null
)
32
Taking true branch
231 return MAX (4, reserve)((4) > (reserve) ? (4) : (reserve));
33
'?' condition is true
34
Returning the value 4, which participates in a condition later
232 return calculate_allocation_1 (pfx->m_alloc, pfx->m_num + reserve);
233}
234
235template<typename, typename, typename> struct vec;
236
237/* Valid vector layouts
238
239 vl_embed - Embeddable vector that uses the trailing array idiom.
240 vl_ptr - Space efficient vector that uses a pointer to an
241 embeddable vector. */
242struct vl_embed { };
243struct vl_ptr { };
244
245
246/* Types of supported allocations
247
248 va_heap - Allocation uses malloc/free.
249 va_gc - Allocation uses ggc_alloc.
250 va_gc_atomic - Same as GC, but individual elements of the array
251 do not need to be marked during collection. */
252
253/* Allocator type for heap vectors. */
254struct va_heap
255{
256 /* Heap vectors are frequently regular instances, so use the vl_ptr
257 layout for them. */
258 typedef vl_ptr default_layout;
259
260 template<typename T>
261 static void reserve (vec<T, va_heap, vl_embed> *&, unsigned, bool
262 CXX_MEM_STAT_INFO);
263
264 template<typename T>
265 static void release (vec<T, va_heap, vl_embed> *&);
266};
267
268
269/* Allocator for heap memory. Ensure there are at least RESERVE free
270 slots in V. If EXACT is true, grow exactly, else grow
271 exponentially. As a special case, if the vector had not been
272 allocated and RESERVE is 0, no vector will be created. */
273
274template<typename T>
275inline void
276va_heap::reserve (vec<T, va_heap, vl_embed> *&v, unsigned reserve, bool exact
277 MEM_STAT_DECL)
278{
279 size_t elt_size = sizeof (T);
280 unsigned alloc
281 = vec_prefix::calculate_allocation (v ? &v->m_vecpfx : 0, reserve, exact);
282 gcc_checking_assert (alloc)((void)(!(alloc) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/vec.h"
, 282, __FUNCTION__), 0 : 0))
;
283
284 if (GATHER_STATISTICS0 && v)
285 v->m_vecpfx.release_overhead (v, elt_size * v->allocated (),
286 v->allocated (), false);
287
288 size_t size = vec<T, va_heap, vl_embed>::embedded_size (alloc);
289 unsigned nelem = v ? v->length () : 0;
290 v = static_cast <vec<T, va_heap, vl_embed> *> (xrealloc (v, size));
291 v->embedded_init (alloc, nelem);
292
293 if (GATHER_STATISTICS0)
294 v->m_vecpfx.register_overhead (v, alloc, elt_size PASS_MEM_STAT);
295}
296
297
298#if GCC_VERSION(4 * 1000 + 2) >= 4007
299#pragma GCC diagnostic push
300#pragma GCC diagnostic ignored "-Wfree-nonheap-object"
301#endif
302
303/* Free the heap space allocated for vector V. */
304
305template<typename T>
306void
307va_heap::release (vec<T, va_heap, vl_embed> *&v)
308{
309 size_t elt_size = sizeof (T);
310 if (v == NULLnullptr)
311 return;
312
313 if (GATHER_STATISTICS0)
314 v->m_vecpfx.release_overhead (v, elt_size * v->allocated (),
315 v->allocated (), true);
316 ::free (v);
317 v = NULLnullptr;
318}
319
320#if GCC_VERSION(4 * 1000 + 2) >= 4007
321#pragma GCC diagnostic pop
322#endif
323
324/* Allocator type for GC vectors. Notice that we need the structure
325 declaration even if GC is not enabled. */
326
327struct va_gc
328{
329 /* Use vl_embed as the default layout for GC vectors. Due to GTY
330 limitations, GC vectors must always be pointers, so it is more
331 efficient to use a pointer to the vl_embed layout, rather than
332 using a pointer to a pointer as would be the case with vl_ptr. */
333 typedef vl_embed default_layout;
334
335 template<typename T, typename A>
336 static void reserve (vec<T, A, vl_embed> *&, unsigned, bool
337 CXX_MEM_STAT_INFO);
338
339 template<typename T, typename A>
340 static void release (vec<T, A, vl_embed> *&v);
341};
342
343
344/* Free GC memory used by V and reset V to NULL. */
345
346template<typename T, typename A>
347inline void
348va_gc::release (vec<T, A, vl_embed> *&v)
349{
350 if (v)
351 ::ggc_free (v);
352 v = NULLnullptr;
353}
354
355
356/* Allocator for GC memory. Ensure there are at least RESERVE free
357 slots in V. If EXACT is true, grow exactly, else grow
358 exponentially. As a special case, if the vector had not been
359 allocated and RESERVE is 0, no vector will be created. */
360
361template<typename T, typename A>
362void
363va_gc::reserve (vec<T, A, vl_embed> *&v, unsigned reserve, bool exact
364 MEM_STAT_DECL)
365{
366 unsigned alloc
367 = vec_prefix::calculate_allocation (v
28.1
'v' is null
50.1
'v' is non-null
28.1
'v' is null
50.1
'v' is non-null
? &v->m_vecpfx : 0, reserve, exact)
;
29
'?' condition is false
30
Calling 'vec_prefix::calculate_allocation'
35
Returning from 'vec_prefix::calculate_allocation'
51
'?' condition is true
368 if (!alloc
35.1
'alloc' is 4
35.1
'alloc' is 4
)
36
Taking false branch
52
Assuming 'alloc' is 0
53
Taking true branch
369 {
370 ::ggc_free (v);
371 v = NULLnullptr;
54
Null pointer value stored to 'elts'
372 return;
373 }
374
375 /* Calculate the amount of space we want. */
376 size_t size = vec<T, A, vl_embed>::embedded_size (alloc);
377
378 /* Ask the allocator how much space it will really give us. */
379 size = ::ggc_round_alloc_size (size);
380
381 /* Adjust the number of slots accordingly. */
382 size_t vec_offset = sizeof (vec_prefix);
383 size_t elt_size = sizeof (T);
384 alloc = (size - vec_offset) / elt_size;
385
386 /* And finally, recalculate the amount of space we ask for. */
387 size = vec_offset + alloc * elt_size;
388
389 unsigned nelem = v
36.1
'v' is null
36.1
'v' is null
? v->length () : 0;
37
'?' condition is false
390 v = static_cast <vec<T, A, vl_embed> *> (::ggc_realloc (v, size
38
Value assigned to 'elts'
391 PASS_MEM_STAT));
392 v->embedded_init (alloc, nelem);
393}
394
395
396/* Allocator type for GC vectors. This is for vectors of types
397 atomics w.r.t. collection, so allocation and deallocation is
398 completely inherited from va_gc. */
399struct va_gc_atomic : va_gc
400{
401};
402
403
404/* Generic vector template. Default values for A and L indicate the
405 most commonly used strategies.
406
407 FIXME - Ideally, they would all be vl_ptr to encourage using regular
408 instances for vectors, but the existing GTY machinery is limited
409 in that it can only deal with GC objects that are pointers
410 themselves.
411
412 This means that vector operations that need to deal with
413 potentially NULL pointers, must be provided as free
414 functions (see the vec_safe_* functions above). */
415template<typename T,
416 typename A = va_heap,
417 typename L = typename A::default_layout>
418struct GTY((user)) vec
419{
420};
421
422/* Allow C++11 range-based 'for' to work directly on vec<T>*. */
423template<typename T, typename A, typename L>
424T* begin (vec<T,A,L> *v) { return v ? v->begin () : nullptr; }
425template<typename T, typename A, typename L>
426T* end (vec<T,A,L> *v) { return v ? v->end () : nullptr; }
427template<typename T, typename A, typename L>
428const T* begin (const vec<T,A,L> *v) { return v ? v->begin () : nullptr; }
429template<typename T, typename A, typename L>
430const T* end (const vec<T,A,L> *v) { return v ? v->end () : nullptr; }
431
432/* Generic vec<> debug helpers.
433
434 These need to be instantiated for each vec<TYPE> used throughout
435 the compiler like this:
436
437 DEFINE_DEBUG_VEC (TYPE)
438
439 The reason we have a debug_helper() is because GDB can't
440 disambiguate a plain call to debug(some_vec), and it must be called
441 like debug<TYPE>(some_vec). */
442
443template<typename T>
444void
445debug_helper (vec<T> &ref)
446{
447 unsigned i;
448 for (i = 0; i < ref.length (); ++i)
449 {
450 fprintf (stderrstderr, "[%d] = ", i);
451 debug_slim (ref[i]);
452 fputc ('\n', stderrstderr);
453 }
454}
455
456/* We need a separate va_gc variant here because default template
457 argument for functions cannot be used in c++-98. Once this
458 restriction is removed, those variant should be folded with the
459 above debug_helper. */
460
461template<typename T>
462void
463debug_helper (vec<T, va_gc> &ref)
464{
465 unsigned i;
466 for (i = 0; i < ref.length (); ++i)
467 {
468 fprintf (stderrstderr, "[%d] = ", i);
469 debug_slim (ref[i]);
470 fputc ('\n', stderrstderr);
471 }
472}
473
474/* Macro to define debug(vec<T>) and debug(vec<T, va_gc>) helper
475 functions for a type T. */
476
477#define DEFINE_DEBUG_VEC(T)template void debug_helper (vec<T> &); template void
debug_helper (vec<T, va_gc> &); __attribute__ ((__used__
)) void debug (vec<T> &ref) { debug_helper <T>
(ref); } __attribute__ ((__used__)) void debug (vec<T>
*ptr) { if (ptr) debug (*ptr); else fprintf (stderr, "<nil>\n"
); } __attribute__ ((__used__)) void debug (vec<T, va_gc>
&ref) { debug_helper <T> (ref); } __attribute__ ((
__used__)) void debug (vec<T, va_gc> *ptr) { if (ptr) debug
(*ptr); else fprintf (stderr, "<nil>\n"); }
\
478 template void debug_helper (vec<T> &); \
479 template void debug_helper (vec<T, va_gc> &); \
480 /* Define the vec<T> debug functions. */ \
481 DEBUG_FUNCTION__attribute__ ((__used__)) void \
482 debug (vec<T> &ref) \
483 { \
484 debug_helper <T> (ref); \
485 } \
486 DEBUG_FUNCTION__attribute__ ((__used__)) void \
487 debug (vec<T> *ptr) \
488 { \
489 if (ptr) \
490 debug (*ptr); \
491 else \
492 fprintf (stderrstderr, "<nil>\n"); \
493 } \
494 /* Define the vec<T, va_gc> debug functions. */ \
495 DEBUG_FUNCTION__attribute__ ((__used__)) void \
496 debug (vec<T, va_gc> &ref) \
497 { \
498 debug_helper <T> (ref); \
499 } \
500 DEBUG_FUNCTION__attribute__ ((__used__)) void \
501 debug (vec<T, va_gc> *ptr) \
502 { \
503 if (ptr) \
504 debug (*ptr); \
505 else \
506 fprintf (stderrstderr, "<nil>\n"); \
507 }
508
509/* Default-construct N elements in DST. */
510
511template <typename T>
512inline void
513vec_default_construct (T *dst, unsigned n)
514{
515#ifdef BROKEN_VALUE_INITIALIZATION
516 /* Versions of GCC before 4.4 sometimes leave certain objects
517 uninitialized when value initialized, though if the type has
518 user defined default ctor, that ctor is invoked. As a workaround
519 perform clearing first and then the value initialization, which
520 fixes the case when value initialization doesn't initialize due to
521 the bugs and should initialize to all zeros, but still allows
522 vectors for types with user defined default ctor that initializes
523 some or all elements to non-zero. If T has no user defined
524 default ctor and some non-static data members have user defined
525 default ctors that initialize to non-zero the workaround will
526 still not work properly; in that case we just need to provide
527 user defined default ctor. */
528 memset (dst, '\0', sizeof (T) * n);
529#endif
530 for ( ; n; ++dst, --n)
531 ::new (static_cast<void*>(dst)) T ();
532}
533
534/* Copy-construct N elements in DST from *SRC. */
535
536template <typename T>
537inline void
538vec_copy_construct (T *dst, const T *src, unsigned n)
539{
540 for ( ; n; ++dst, ++src, --n)
541 ::new (static_cast<void*>(dst)) T (*src);
542}
543
544/* Type to provide zero-initialized values for vec<T, A, L>. This is
545 used to provide nil initializers for vec instances. Since vec must
546 be a trivially copyable type that can be copied by memcpy and zeroed
547 out by memset, it must have defaulted default and copy ctor and copy
548 assignment. To initialize a vec either use value initialization
549 (e.g., vec() or vec v{ };) or assign it the value vNULL. This isn't
550 needed for file-scope and function-local static vectors, which are
551 zero-initialized by default. */
552struct vnull { };
553constexpr vnull vNULL{ };
554
555
556/* Embeddable vector. These vectors are suitable to be embedded
557 in other data structures so that they can be pre-allocated in a
558 contiguous memory block.
559
560 Embeddable vectors are implemented using the trailing array idiom,
561 thus they are not resizeable without changing the address of the
562 vector object itself. This means you cannot have variables or
563 fields of embeddable vector type -- always use a pointer to a
564 vector. The one exception is the final field of a structure, which
565 could be a vector type.
566
567 You will have to use the embedded_size & embedded_init calls to
568 create such objects, and they will not be resizeable (so the 'safe'
569 allocation variants are not available).
570
571 Properties:
572
573 - The whole vector and control data are allocated in a single
574 contiguous block. It uses the trailing-vector idiom, so
575 allocation must reserve enough space for all the elements
576 in the vector plus its control data.
577 - The vector cannot be re-allocated.
578 - The vector cannot grow nor shrink.
579 - No indirections needed for access/manipulation.
580 - It requires 2 words of storage (prior to vector allocation). */
581
582template<typename T, typename A>
583struct GTY((user)) vec<T, A, vl_embed>
584{
585public:
586 unsigned allocated (void) const { return m_vecpfx.m_alloc; }
587 unsigned length (void) const { return m_vecpfx.m_num; }
588 bool is_empty (void) const { return m_vecpfx.m_num == 0; }
589 T *address (void) { return m_vecdata; }
590 const T *address (void) const { return m_vecdata; }
591 T *begin () { return address (); }
592 const T *begin () const { return address (); }
593 T *end () { return address () + length (); }
594 const T *end () const { return address () + length (); }
595 const T &operator[] (unsigned) const;
596 T &operator[] (unsigned);
597 T &last (void);
598 bool space (unsigned) const;
599 bool iterate (unsigned, T *) const;
600 bool iterate (unsigned, T **) const;
601 vec *copy (ALONE_CXX_MEM_STAT_INFO) const;
602 void splice (const vec &);
603 void splice (const vec *src);
604 T *quick_push (const T &);
605 T &pop (void);
606 void truncate (unsigned);
607 void quick_insert (unsigned, const T &);
608 void ordered_remove (unsigned);
609 void unordered_remove (unsigned);
610 void block_remove (unsigned, unsigned);
611 void qsort (int (*) (const void *, const void *))qsort (int (*) (const void *, const void *));
612 void sort (int (*) (const void *, const void *, void *), void *);
613 void stablesort (int (*) (const void *, const void *, void *), void *);
614 T *bsearch (const void *key, int (*compar)(const void *, const void *));
615 T *bsearch (const void *key,
616 int (*compar)(const void *, const void *, void *), void *);
617 unsigned lower_bound (T, bool (*)(const T &, const T &)) const;
618 bool contains (const T &search) const;
619 static size_t embedded_size (unsigned);
620 void embedded_init (unsigned, unsigned = 0, unsigned = 0);
621 void quick_grow (unsigned len);
622 void quick_grow_cleared (unsigned len);
623
624 /* vec class can access our internal data and functions. */
625 template <typename, typename, typename> friend struct vec;
626
627 /* The allocator types also need access to our internals. */
628 friend struct va_gc;
629 friend struct va_gc_atomic;
630 friend struct va_heap;
631
632 /* FIXME - These fields should be private, but we need to cater to
633 compilers that have stricter notions of PODness for types. */
634 vec_prefix m_vecpfx;
635 T m_vecdata[1];
636};
637
638
639/* Convenience wrapper functions to use when dealing with pointers to
640 embedded vectors. Some functionality for these vectors must be
641 provided via free functions for these reasons:
642
643 1- The pointer may be NULL (e.g., before initial allocation).
644
645 2- When the vector needs to grow, it must be reallocated, so
646 the pointer will change its value.
647
648 Because of limitations with the current GC machinery, all vectors
649 in GC memory *must* be pointers. */
650
651
652/* If V contains no room for NELEMS elements, return false. Otherwise,
653 return true. */
654template<typename T, typename A>
655inline bool
656vec_safe_space (const vec<T, A, vl_embed> *v, unsigned nelems)
657{
658 return v
23.1
'v' is null
23.1
'v' is null
? v->space (nelems) : nelems == 0
;
24
'?' condition is false
25
Returning zero, which participates in a condition later
659}
660
661
662/* If V is NULL, return 0. Otherwise, return V->length(). */
663template<typename T, typename A>
664inline unsigned
665vec_safe_length (const vec<T, A, vl_embed> *v)
666{
667 return v ? v->length () : 0;
668}
669
670
671/* If V is NULL, return NULL. Otherwise, return V->address(). */
672template<typename T, typename A>
673inline T *
674vec_safe_address (vec<T, A, vl_embed> *v)
675{
676 return v ? v->address () : NULLnullptr;
677}
678
679
680/* If V is NULL, return true. Otherwise, return V->is_empty(). */
681template<typename T, typename A>
682inline bool
683vec_safe_is_empty (vec<T, A, vl_embed> *v)
684{
685 return v ? v->is_empty () : true;
686}
687
688/* If V does not have space for NELEMS elements, call
689 V->reserve(NELEMS, EXACT). */
690template<typename T, typename A>
691inline bool
692vec_safe_reserve (vec<T, A, vl_embed> *&v, unsigned nelems, bool exact = false
693 CXX_MEM_STAT_INFO)
694{
695 bool extend = nelems
21.1
'nelems' is 1
46.1
'nelems' is 1
21.1
'nelems' is 1
46.1
'nelems' is 1
? !vec_safe_space (v, nelems) : false;
22
'?' condition is true
23
Calling 'vec_safe_space<constructor_elt, va_gc>'
26
Returning from 'vec_safe_space<constructor_elt, va_gc>'
47
'?' condition is true
48
Assuming the condition is true
696 if (extend
26.1
'extend' is true
48.1
'extend' is true
26.1
'extend' is true
48.1
'extend' is true
)
27
Taking true branch
49
Taking true branch
697 A::reserve (v, nelems, exact PASS_MEM_STAT);
28
Calling 'va_gc::reserve'
39
Returning from 'va_gc::reserve'
50
Calling 'va_gc::reserve'
55
Returning from 'va_gc::reserve'
698 return extend;
699}
700
701template<typename T, typename A>
702inline bool
703vec_safe_reserve_exact (vec<T, A, vl_embed> *&v, unsigned nelems
704 CXX_MEM_STAT_INFO)
705{
706 return vec_safe_reserve (v, nelems, true PASS_MEM_STAT);
707}
708
709
710/* Allocate GC memory for V with space for NELEMS slots. If NELEMS
711 is 0, V is initialized to NULL. */
712
713template<typename T, typename A>
714inline void
715vec_alloc (vec<T, A, vl_embed> *&v, unsigned nelems CXX_MEM_STAT_INFO)
716{
717 v = NULLnullptr;
718 vec_safe_reserve (v, nelems, false PASS_MEM_STAT);
719}
720
721
722/* Free the GC memory allocated by vector V and set it to NULL. */
723
724template<typename T, typename A>
725inline void
726vec_free (vec<T, A, vl_embed> *&v)
727{
728 A::release (v);
729}
730
731
732/* Grow V to length LEN. Allocate it, if necessary. */
733template<typename T, typename A>
734inline void
735vec_safe_grow (vec<T, A, vl_embed> *&v, unsigned len,
736 bool exact = false CXX_MEM_STAT_INFO)
737{
738 unsigned oldlen = vec_safe_length (v);
739 gcc_checking_assert (len >= oldlen)((void)(!(len >= oldlen) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/vec.h"
, 739, __FUNCTION__), 0 : 0))
;
740 vec_safe_reserve (v, len - oldlen, exact PASS_MEM_STAT);
741 v->quick_grow (len);
742}
743
744
745/* If V is NULL, allocate it. Call V->safe_grow_cleared(LEN). */
746template<typename T, typename A>
747inline void
748vec_safe_grow_cleared (vec<T, A, vl_embed> *&v, unsigned len,
749 bool exact = false CXX_MEM_STAT_INFO)
750{
751 unsigned oldlen = vec_safe_length (v);
752 vec_safe_grow (v, len, exact PASS_MEM_STAT);
753 vec_default_construct (v->address () + oldlen, len - oldlen);
754}
755
756
757/* Assume V is not NULL. */
758
759template<typename T>
760inline void
761vec_safe_grow_cleared (vec<T, va_heap, vl_ptr> *&v,
762 unsigned len, bool exact = false CXX_MEM_STAT_INFO)
763{
764 v->safe_grow_cleared (len, exact PASS_MEM_STAT);
765}
766
767/* If V does not have space for NELEMS elements, call
768 V->reserve(NELEMS, EXACT). */
769
770template<typename T>
771inline bool
772vec_safe_reserve (vec<T, va_heap, vl_ptr> *&v, unsigned nelems, bool exact = false
773 CXX_MEM_STAT_INFO)
774{
775 return v->reserve (nelems, exact);
776}
777
778
779/* If V is NULL return false, otherwise return V->iterate(IX, PTR). */
780template<typename T, typename A>
781inline bool
782vec_safe_iterate (const vec<T, A, vl_embed> *v, unsigned ix, T **ptr)
783{
784 if (v)
785 return v->iterate (ix, ptr);
786 else
787 {
788 *ptr = 0;
789 return false;
790 }
791}
792
793template<typename T, typename A>
794inline bool
795vec_safe_iterate (const vec<T, A, vl_embed> *v, unsigned ix, T *ptr)
796{
797 if (v)
798 return v->iterate (ix, ptr);
799 else
800 {
801 *ptr = 0;
802 return false;
803 }
804}
805
806
807/* If V has no room for one more element, reallocate it. Then call
808 V->quick_push(OBJ). */
809template<typename T, typename A>
810inline T *
811vec_safe_push (vec<T, A, vl_embed> *&v, const T &obj CXX_MEM_STAT_INFO)
812{
813 vec_safe_reserve (v, 1, false PASS_MEM_STAT);
21
Calling 'vec_safe_reserve<constructor_elt, va_gc>'
40
Returning from 'vec_safe_reserve<constructor_elt, va_gc>'
46
Calling 'vec_safe_reserve<constructor_elt, va_gc>'
56
Returning from 'vec_safe_reserve<constructor_elt, va_gc>'
814 return v->quick_push (obj);
57
Called C++ object pointer is null
815}
816
817
818/* if V has no room for one more element, reallocate it. Then call
819 V->quick_insert(IX, OBJ). */
820template<typename T, typename A>
821inline void
822vec_safe_insert (vec<T, A, vl_embed> *&v, unsigned ix, const T &obj
823 CXX_MEM_STAT_INFO)
824{
825 vec_safe_reserve (v, 1, false PASS_MEM_STAT);
826 v->quick_insert (ix, obj);
827}
828
829
830/* If V is NULL, do nothing. Otherwise, call V->truncate(SIZE). */
831template<typename T, typename A>
832inline void
833vec_safe_truncate (vec<T, A, vl_embed> *v, unsigned size)
834{
835 if (v)
836 v->truncate (size);
837}
838
839
840/* If SRC is not NULL, return a pointer to a copy of it. */
841template<typename T, typename A>
842inline vec<T, A, vl_embed> *
843vec_safe_copy (vec<T, A, vl_embed> *src CXX_MEM_STAT_INFO)
844{
845 return src ? src->copy (ALONE_PASS_MEM_STAT) : NULLnullptr;
846}
847
848/* Copy the elements from SRC to the end of DST as if by memcpy.
849 Reallocate DST, if necessary. */
850template<typename T, typename A>
851inline void
852vec_safe_splice (vec<T, A, vl_embed> *&dst, const vec<T, A, vl_embed> *src
853 CXX_MEM_STAT_INFO)
854{
855 unsigned src_len = vec_safe_length (src);
856 if (src_len)
857 {
858 vec_safe_reserve_exact (dst, vec_safe_length (dst) + src_len
859 PASS_MEM_STAT);
860 dst->splice (*src);
861 }
862}
863
864/* Return true if SEARCH is an element of V. Note that this is O(N) in the
865 size of the vector and so should be used with care. */
866
867template<typename T, typename A>
868inline bool
869vec_safe_contains (vec<T, A, vl_embed> *v, const T &search)
870{
871 return v ? v->contains (search) : false;
872}
873
874/* Index into vector. Return the IX'th element. IX must be in the
875 domain of the vector. */
876
877template<typename T, typename A>
878inline const T &
879vec<T, A, vl_embed>::operator[] (unsigned ix) const
880{
881 gcc_checking_assert (ix < m_vecpfx.m_num)((void)(!(ix < m_vecpfx.m_num) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/vec.h"
, 881, __FUNCTION__), 0 : 0))
;
882 return m_vecdata[ix];
883}
884
885template<typename T, typename A>
886inline T &
887vec<T, A, vl_embed>::operator[] (unsigned ix)
888{
889 gcc_checking_assert (ix < m_vecpfx.m_num)((void)(!(ix < m_vecpfx.m_num) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/vec.h"
, 889, __FUNCTION__), 0 : 0))
;
890 return m_vecdata[ix];
891}
892
893
894/* Get the final element of the vector, which must not be empty. */
895
896template<typename T, typename A>
897inline T &
898vec<T, A, vl_embed>::last (void)
899{
900 gcc_checking_assert (m_vecpfx.m_num > 0)((void)(!(m_vecpfx.m_num > 0) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/vec.h"
, 900, __FUNCTION__), 0 : 0))
;
901 return (*this)[m_vecpfx.m_num - 1];
902}
903
904
905/* If this vector has space for NELEMS additional entries, return
906 true. You usually only need to use this if you are doing your
907 own vector reallocation, for instance on an embedded vector. This
908 returns true in exactly the same circumstances that vec::reserve
909 will. */
910
911template<typename T, typename A>
912inline bool
913vec<T, A, vl_embed>::space (unsigned nelems) const
914{
915 return m_vecpfx.m_alloc - m_vecpfx.m_num >= nelems;
916}
917
918
919/* Return iteration condition and update PTR to point to the IX'th
920 element of this vector. Use this to iterate over the elements of a
921 vector as follows,
922
923 for (ix = 0; vec<T, A>::iterate (v, ix, &ptr); ix++)
924 continue; */
925
926template<typename T, typename A>
927inline bool
928vec<T, A, vl_embed>::iterate (unsigned ix, T *ptr) const
929{
930 if (ix < m_vecpfx.m_num)
931 {
932 *ptr = m_vecdata[ix];
933 return true;
934 }
935 else
936 {
937 *ptr = 0;
938 return false;
939 }
940}
941
942
943/* Return iteration condition and update *PTR to point to the
944 IX'th element of this vector. Use this to iterate over the
945 elements of a vector as follows,
946
947 for (ix = 0; v->iterate (ix, &ptr); ix++)
948 continue;
949
950 This variant is for vectors of objects. */
951
952template<typename T, typename A>
953inline bool
954vec<T, A, vl_embed>::iterate (unsigned ix, T **ptr) const
955{
956 if (ix < m_vecpfx.m_num)
957 {
958 *ptr = CONST_CAST (T *, &m_vecdata[ix])(const_cast<T *> ((&m_vecdata[ix])));
959 return true;
960 }
961 else
962 {
963 *ptr = 0;
964 return false;
965 }
966}
967
968
969/* Return a pointer to a copy of this vector. */
970
971template<typename T, typename A>
972inline vec<T, A, vl_embed> *
973vec<T, A, vl_embed>::copy (ALONE_MEM_STAT_DECLvoid) const
974{
975 vec<T, A, vl_embed> *new_vec = NULLnullptr;
976 unsigned len = length ();
977 if (len)
978 {
979 vec_alloc (new_vec, len PASS_MEM_STAT);
980 new_vec->embedded_init (len, len);
981 vec_copy_construct (new_vec->address (), m_vecdata, len);
982 }
983 return new_vec;
984}
985
986
987/* Copy the elements from SRC to the end of this vector as if by memcpy.
988 The vector must have sufficient headroom available. */
989
990template<typename T, typename A>
991inline void
992vec<T, A, vl_embed>::splice (const vec<T, A, vl_embed> &src)
993{
994 unsigned len = src.length ();
995 if (len)
996 {
997 gcc_checking_assert (space (len))((void)(!(space (len)) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/vec.h"
, 997, __FUNCTION__), 0 : 0))
;
998 vec_copy_construct (end (), src.address (), len);
999 m_vecpfx.m_num += len;
1000 }
1001}
1002
1003template<typename T, typename A>
1004inline void
1005vec<T, A, vl_embed>::splice (const vec<T, A, vl_embed> *src)
1006{
1007 if (src)
1008 splice (*src);
1009}
1010
1011
1012/* Push OBJ (a new element) onto the end of the vector. There must be
1013 sufficient space in the vector. Return a pointer to the slot
1014 where OBJ was inserted. */
1015
1016template<typename T, typename A>
1017inline T *
1018vec<T, A, vl_embed>::quick_push (const T &obj)
1019{
1020 gcc_checking_assert (space (1))((void)(!(space (1)) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/vec.h"
, 1020, __FUNCTION__), 0 : 0))
;
1021 T *slot = &m_vecdata[m_vecpfx.m_num++];
1022 *slot = obj;
1023 return slot;
1024}
1025
1026
1027/* Pop and return the last element off the end of the vector. */
1028
1029template<typename T, typename A>
1030inline T &
1031vec<T, A, vl_embed>::pop (void)
1032{
1033 gcc_checking_assert (length () > 0)((void)(!(length () > 0) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/vec.h"
, 1033, __FUNCTION__), 0 : 0))
;
1034 return m_vecdata[--m_vecpfx.m_num];
1035}
1036
1037
1038/* Set the length of the vector to SIZE. The new length must be less
1039 than or equal to the current length. This is an O(1) operation. */
1040
1041template<typename T, typename A>
1042inline void
1043vec<T, A, vl_embed>::truncate (unsigned size)
1044{
1045 gcc_checking_assert (length () >= size)((void)(!(length () >= size) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/vec.h"
, 1045, __FUNCTION__), 0 : 0))
;
1046 m_vecpfx.m_num = size;
1047}
1048
1049
1050/* Insert an element, OBJ, at the IXth position of this vector. There
1051 must be sufficient space. */
1052
1053template<typename T, typename A>
1054inline void
1055vec<T, A, vl_embed>::quick_insert (unsigned ix, const T &obj)
1056{
1057 gcc_checking_assert (length () < allocated ())((void)(!(length () < allocated ()) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/vec.h"
, 1057, __FUNCTION__), 0 : 0))
;
1058 gcc_checking_assert (ix <= length ())((void)(!(ix <= length ()) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/vec.h"
, 1058, __FUNCTION__), 0 : 0))
;
1059 T *slot = &m_vecdata[ix];
1060 memmove (slot + 1, slot, (m_vecpfx.m_num++ - ix) * sizeof (T));
1061 *slot = obj;
1062}
1063
1064
1065/* Remove an element from the IXth position of this vector. Ordering of
1066 remaining elements is preserved. This is an O(N) operation due to
1067 memmove. */
1068
1069template<typename T, typename A>
1070inline void
1071vec<T, A, vl_embed>::ordered_remove (unsigned ix)
1072{
1073 gcc_checking_assert (ix < length ())((void)(!(ix < length ()) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/vec.h"
, 1073, __FUNCTION__), 0 : 0))
;
1074 T *slot = &m_vecdata[ix];
1075 memmove (slot, slot + 1, (--m_vecpfx.m_num - ix) * sizeof (T));
1076}
1077
1078
1079/* Remove elements in [START, END) from VEC for which COND holds. Ordering of
1080 remaining elements is preserved. This is an O(N) operation. */
1081
1082#define VEC_ORDERED_REMOVE_IF_FROM_TO(vec, read_index, write_index, \{ ((void)(!((end) <= (vec).length ()) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/vec.h"
, 1083, __FUNCTION__), 0 : 0)); for (read_index = write_index
= (start); read_index < (end); ++read_index) { elem_ptr =
&(vec)[read_index]; bool remove_p = (cond); if (remove_p
) continue; if (read_index != write_index) (vec)[write_index]
= (vec)[read_index]; write_index++; } if (read_index - write_index
> 0) (vec).block_remove (write_index, read_index - write_index
); }
1083 elem_ptr, start, end, cond){ ((void)(!((end) <= (vec).length ()) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/vec.h"
, 1083, __FUNCTION__), 0 : 0)); for (read_index = write_index
= (start); read_index < (end); ++read_index) { elem_ptr =
&(vec)[read_index]; bool remove_p = (cond); if (remove_p
) continue; if (read_index != write_index) (vec)[write_index]
= (vec)[read_index]; write_index++; } if (read_index - write_index
> 0) (vec).block_remove (write_index, read_index - write_index
); }
\
1084 { \
1085 gcc_assert ((end) <= (vec).length ())((void)(!((end) <= (vec).length ()) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/vec.h"
, 1085, __FUNCTION__), 0 : 0))
; \
1086 for (read_index = write_index = (start); read_index < (end); \
1087 ++read_index) \
1088 { \
1089 elem_ptr = &(vec)[read_index]; \
1090 bool remove_p = (cond); \
1091 if (remove_p) \
1092 continue; \
1093 \
1094 if (read_index != write_index) \
1095 (vec)[write_index] = (vec)[read_index]; \
1096 \
1097 write_index++; \
1098 } \
1099 \
1100 if (read_index - write_index > 0) \
1101 (vec).block_remove (write_index, read_index - write_index); \
1102 }
1103
1104
1105/* Remove elements from VEC for which COND holds. Ordering of remaining
1106 elements is preserved. This is an O(N) operation. */
1107
1108#define VEC_ORDERED_REMOVE_IF(vec, read_index, write_index, elem_ptr, \{ ((void)(!(((vec).length ()) <= ((vec)).length ()) ? fancy_abort
("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/vec.h"
, 1109, __FUNCTION__), 0 : 0)); for (read_index = write_index
= (0); read_index < ((vec).length ()); ++read_index) { elem_ptr
= &((vec))[read_index]; bool remove_p = ((cond)); if (remove_p
) continue; if (read_index != write_index) ((vec))[write_index
] = ((vec))[read_index]; write_index++; } if (read_index - write_index
> 0) ((vec)).block_remove (write_index, read_index - write_index
); }
1109 cond){ ((void)(!(((vec).length ()) <= ((vec)).length ()) ? fancy_abort
("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/vec.h"
, 1109, __FUNCTION__), 0 : 0)); for (read_index = write_index
= (0); read_index < ((vec).length ()); ++read_index) { elem_ptr
= &((vec))[read_index]; bool remove_p = ((cond)); if (remove_p
) continue; if (read_index != write_index) ((vec))[write_index
] = ((vec))[read_index]; write_index++; } if (read_index - write_index
> 0) ((vec)).block_remove (write_index, read_index - write_index
); }
\
1110 VEC_ORDERED_REMOVE_IF_FROM_TO ((vec), read_index, write_index, \{ ((void)(!(((vec).length ()) <= ((vec)).length ()) ? fancy_abort
("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/vec.h"
, 1111, __FUNCTION__), 0 : 0)); for (read_index = write_index
= (0); read_index < ((vec).length ()); ++read_index) { elem_ptr
= &((vec))[read_index]; bool remove_p = ((cond)); if (remove_p
) continue; if (read_index != write_index) ((vec))[write_index
] = ((vec))[read_index]; write_index++; } if (read_index - write_index
> 0) ((vec)).block_remove (write_index, read_index - write_index
); }
1111 elem_ptr, 0, (vec).length (), (cond)){ ((void)(!(((vec).length ()) <= ((vec)).length ()) ? fancy_abort
("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/vec.h"
, 1111, __FUNCTION__), 0 : 0)); for (read_index = write_index
= (0); read_index < ((vec).length ()); ++read_index) { elem_ptr
= &((vec))[read_index]; bool remove_p = ((cond)); if (remove_p
) continue; if (read_index != write_index) ((vec))[write_index
] = ((vec))[read_index]; write_index++; } if (read_index - write_index
> 0) ((vec)).block_remove (write_index, read_index - write_index
); }
1112
1113/* Remove an element from the IXth position of this vector. Ordering of
1114 remaining elements is destroyed. This is an O(1) operation. */
1115
1116template<typename T, typename A>
1117inline void
1118vec<T, A, vl_embed>::unordered_remove (unsigned ix)
1119{
1120 gcc_checking_assert (ix < length ())((void)(!(ix < length ()) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/vec.h"
, 1120, __FUNCTION__), 0 : 0))
;
1121 m_vecdata[ix] = m_vecdata[--m_vecpfx.m_num];
1122}
1123
1124
1125/* Remove LEN elements starting at the IXth. Ordering is retained.
1126 This is an O(N) operation due to memmove. */
1127
1128template<typename T, typename A>
1129inline void
1130vec<T, A, vl_embed>::block_remove (unsigned ix, unsigned len)
1131{
1132 gcc_checking_assert (ix + len <= length ())((void)(!(ix + len <= length ()) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/vec.h"
, 1132, __FUNCTION__), 0 : 0))
;
1133 T *slot = &m_vecdata[ix];
1134 m_vecpfx.m_num -= len;
1135 memmove (slot, slot + len, (m_vecpfx.m_num - ix) * sizeof (T));
1136}
1137
1138
1139/* Sort the contents of this vector with qsort. CMP is the comparison
1140 function to pass to qsort. */
1141
1142template<typename T, typename A>
1143inline void
1144vec<T, A, vl_embed>::qsort (int (*cmp) (const void *, const void *))qsort (int (*cmp) (const void *, const void *))
1145{
1146 if (length () > 1)
1147 gcc_qsort (address (), length (), sizeof (T), cmp);
1148}
1149
1150/* Sort the contents of this vector with qsort. CMP is the comparison
1151 function to pass to qsort. */
1152
1153template<typename T, typename A>
1154inline void
1155vec<T, A, vl_embed>::sort (int (*cmp) (const void *, const void *, void *),
1156 void *data)
1157{
1158 if (length () > 1)
1159 gcc_sort_r (address (), length (), sizeof (T), cmp, data);
1160}
1161
1162/* Sort the contents of this vector with gcc_stablesort_r. CMP is the
1163 comparison function to pass to qsort. */
1164
1165template<typename T, typename A>
1166inline void
1167vec<T, A, vl_embed>::stablesort (int (*cmp) (const void *, const void *,
1168 void *), void *data)
1169{
1170 if (length () > 1)
1171 gcc_stablesort_r (address (), length (), sizeof (T), cmp, data);
1172}
1173
1174/* Search the contents of the sorted vector with a binary search.
1175 CMP is the comparison function to pass to bsearch. */
1176
1177template<typename T, typename A>
1178inline T *
1179vec<T, A, vl_embed>::bsearch (const void *key,
1180 int (*compar) (const void *, const void *))
1181{
1182 const void *base = this->address ();
1183 size_t nmemb = this->length ();
1184 size_t size = sizeof (T);
1185 /* The following is a copy of glibc stdlib-bsearch.h. */
1186 size_t l, u, idx;
1187 const void *p;
1188 int comparison;
1189
1190 l = 0;
1191 u = nmemb;
1192 while (l < u)
1193 {
1194 idx = (l + u) / 2;
1195 p = (const void *) (((const char *) base) + (idx * size));
1196 comparison = (*compar) (key, p);
1197 if (comparison < 0)
1198 u = idx;
1199 else if (comparison > 0)
1200 l = idx + 1;
1201 else
1202 return (T *)const_cast<void *>(p);
1203 }
1204
1205 return NULLnullptr;
1206}
1207
1208/* Search the contents of the sorted vector with a binary search.
1209 CMP is the comparison function to pass to bsearch. */
1210
1211template<typename T, typename A>
1212inline T *
1213vec<T, A, vl_embed>::bsearch (const void *key,
1214 int (*compar) (const void *, const void *,
1215 void *), void *data)
1216{
1217 const void *base = this->address ();
1218 size_t nmemb = this->length ();
1219 size_t size = sizeof (T);
1220 /* The following is a copy of glibc stdlib-bsearch.h. */
1221 size_t l, u, idx;
1222 const void *p;
1223 int comparison;
1224
1225 l = 0;
1226 u = nmemb;
1227 while (l < u)
1228 {
1229 idx = (l + u) / 2;
1230 p = (const void *) (((const char *) base) + (idx * size));
1231 comparison = (*compar) (key, p, data);
1232 if (comparison < 0)
1233 u = idx;
1234 else if (comparison > 0)
1235 l = idx + 1;
1236 else
1237 return (T *)const_cast<void *>(p);
1238 }
1239
1240 return NULLnullptr;
1241}
1242
1243/* Return true if SEARCH is an element of V. Note that this is O(N) in the
1244 size of the vector and so should be used with care. */
1245
1246template<typename T, typename A>
1247inline bool
1248vec<T, A, vl_embed>::contains (const T &search) const
1249{
1250 unsigned int len = length ();
1251 for (unsigned int i = 0; i < len; i++)
1252 if ((*this)[i] == search)
1253 return true;
1254
1255 return false;
1256}
1257
1258/* Find and return the first position in which OBJ could be inserted
1259 without changing the ordering of this vector. LESSTHAN is a
1260 function that returns true if the first argument is strictly less
1261 than the second. */
1262
1263template<typename T, typename A>
1264unsigned
1265vec<T, A, vl_embed>::lower_bound (T obj, bool (*lessthan)(const T &, const T &))
1266 const
1267{
1268 unsigned int len = length ();
1269 unsigned int half, middle;
1270 unsigned int first = 0;
1271 while (len > 0)
1272 {
1273 half = len / 2;
1274 middle = first;
1275 middle += half;
1276 T middle_elem = (*this)[middle];
1277 if (lessthan (middle_elem, obj))
1278 {
1279 first = middle;
1280 ++first;
1281 len = len - half - 1;
1282 }
1283 else
1284 len = half;
1285 }
1286 return first;
1287}
1288
1289
1290/* Return the number of bytes needed to embed an instance of an
1291 embeddable vec inside another data structure.
1292
1293 Use these methods to determine the required size and initialization
1294 of a vector V of type T embedded within another structure (as the
1295 final member):
1296
1297 size_t vec<T, A, vl_embed>::embedded_size (unsigned alloc);
1298 void v->embedded_init (unsigned alloc, unsigned num);
1299
1300 These allow the caller to perform the memory allocation. */
1301
1302template<typename T, typename A>
1303inline size_t
1304vec<T, A, vl_embed>::embedded_size (unsigned alloc)
1305{
1306 struct alignas (T) U { char data[sizeof (T)]; };
1307 typedef vec<U, A, vl_embed> vec_embedded;
1308 typedef typename std::conditional<std::is_standard_layout<T>::value,
1309 vec, vec_embedded>::type vec_stdlayout;
1310 static_assert (sizeof (vec_stdlayout) == sizeof (vec), "");
1311 static_assert (alignof (vec_stdlayout) == alignof (vec), "");
1312 return offsetof (vec_stdlayout, m_vecdata)__builtin_offsetof(vec_stdlayout, m_vecdata) + alloc * sizeof (T);
1313}
1314
1315
1316/* Initialize the vector to contain room for ALLOC elements and
1317 NUM active elements. */
1318
1319template<typename T, typename A>
1320inline void
1321vec<T, A, vl_embed>::embedded_init (unsigned alloc, unsigned num, unsigned aut)
1322{
1323 m_vecpfx.m_alloc = alloc;
1324 m_vecpfx.m_using_auto_storage = aut;
1325 m_vecpfx.m_num = num;
1326}
1327
1328
1329/* Grow the vector to a specific length. LEN must be as long or longer than
1330 the current length. The new elements are uninitialized. */
1331
1332template<typename T, typename A>
1333inline void
1334vec<T, A, vl_embed>::quick_grow (unsigned len)
1335{
1336 gcc_checking_assert (length () <= len && len <= m_vecpfx.m_alloc)((void)(!(length () <= len && len <= m_vecpfx.m_alloc
) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/vec.h"
, 1336, __FUNCTION__), 0 : 0))
;
1337 m_vecpfx.m_num = len;
1338}
1339
1340
1341/* Grow the vector to a specific length. LEN must be as long or longer than
1342 the current length. The new elements are initialized to zero. */
1343
1344template<typename T, typename A>
1345inline void
1346vec<T, A, vl_embed>::quick_grow_cleared (unsigned len)
1347{
1348 unsigned oldlen = length ();
1349 size_t growby = len - oldlen;
1350 quick_grow (len);
1351 if (growby != 0)
1352 vec_default_construct (address () + oldlen, growby);
1353}
1354
1355/* Garbage collection support for vec<T, A, vl_embed>. */
1356
1357template<typename T>
1358void
1359gt_ggc_mx (vec<T, va_gc> *v)
1360{
1361 extern void gt_ggc_mx (T &);
1362 for (unsigned i = 0; i < v->length (); i++)
1363 gt_ggc_mx ((*v)[i]);
1364}
1365
1366template<typename T>
1367void
1368gt_ggc_mx (vec<T, va_gc_atomic, vl_embed> *v ATTRIBUTE_UNUSED__attribute__ ((__unused__)))
1369{
1370 /* Nothing to do. Vectors of atomic types wrt GC do not need to
1371 be traversed. */
1372}
1373
1374
1375/* PCH support for vec<T, A, vl_embed>. */
1376
1377template<typename T, typename A>
1378void
1379gt_pch_nx (vec<T, A, vl_embed> *v)
1380{
1381 extern void gt_pch_nx (T &);
1382 for (unsigned i = 0; i < v->length (); i++)
1383 gt_pch_nx ((*v)[i]);
1384}
1385
1386template<typename T, typename A>
1387void
1388gt_pch_nx (vec<T *, A, vl_embed> *v, gt_pointer_operator op, void *cookie)
1389{
1390 for (unsigned i = 0; i < v->length (); i++)
1391 op (&((*v)[i]), cookie);
1392}
1393
1394template<typename T, typename A>
1395void
1396gt_pch_nx (vec<T, A, vl_embed> *v, gt_pointer_operator op, void *cookie)
1397{
1398 extern void gt_pch_nx (T *, gt_pointer_operator, void *);
1399