1/* SSA operands management for trees.
2 Copyright (C) 2003-2017 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify
7it under the terms of the GNU General Public License as published by
8the Free Software Foundation; either version 3, or (at your option)
9any later version.
10
11GCC is distributed in the hope that it will be useful,
12but WITHOUT ANY WARRANTY; without even the implied warranty of
13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14GNU General Public License for more details.
15
16You should have received a copy of the GNU General Public License
17along with GCC; see the file COPYING3. If not see
18<http://www.gnu.org/licenses/>. */
19
20#include "config.h"
21#include "system.h"
22#include "coretypes.h"
23#include "backend.h"
24#include "tree.h"
25#include "gimple.h"
26#include "timevar.h"
27#include "ssa.h"
28#include "gimple-pretty-print.h"
29#include "diagnostic-core.h"
30#include "stmt.h"
31#include "print-tree.h"
32#include "dumpfile.h"
33
34
35/* This file contains the code required to manage the operands cache of the
36 SSA optimizer. For every stmt, we maintain an operand cache in the stmt
37 annotation. This cache contains operands that will be of interest to
38 optimizers and other passes wishing to manipulate the IL.
39
40 The operand type are broken up into REAL and VIRTUAL operands. The real
41 operands are represented as pointers into the stmt's operand tree. Thus
42 any manipulation of the real operands will be reflected in the actual tree.
43 Virtual operands are represented solely in the cache, although the base
44 variable for the SSA_NAME may, or may not occur in the stmt's tree.
45 Manipulation of the virtual operands will not be reflected in the stmt tree.
46
47 The routines in this file are concerned with creating this operand cache
48 from a stmt tree.
49
50 The operand tree is the parsed by the various get_* routines which look
51 through the stmt tree for the occurrence of operands which may be of
52 interest, and calls are made to the append_* routines whenever one is
53 found. There are 4 of these routines, each representing one of the
54 4 types of operands. Defs, Uses, Virtual Uses, and Virtual May Defs.
55
56 The append_* routines check for duplication, and simply keep a list of
57 unique objects for each operand type in the build_* extendable vectors.
58
59 Once the stmt tree is completely parsed, the finalize_ssa_operands()
60 routine is called, which proceeds to perform the finalization routine
61 on each of the 4 operand vectors which have been built up.
62
63 If the stmt had a previous operand cache, the finalization routines
64 attempt to match up the new operands with the old ones. If it's a perfect
65 match, the old vector is simply reused. If it isn't a perfect match, then
66 a new vector is created and the new operands are placed there. For
67 virtual operands, if the previous cache had SSA_NAME version of a
68 variable, and that same variable occurs in the same operands cache, then
69 the new cache vector will also get the same SSA_NAME.
70
71 i.e., if a stmt had a VUSE of 'a_5', and 'a' occurs in the new
72 operand vector for VUSE, then the new vector will also be modified
73 such that it contains 'a_5' rather than 'a'. */
74
75
76/* Flags to describe operand properties in helpers. */
77
78/* By default, operands are loaded. */
79#define opf_use 0
80
81/* Operand is the target of an assignment expression or a
82 call-clobbered variable. */
83#define opf_def (1 << 0)
84
85/* No virtual operands should be created in the expression. This is used
86 when traversing ADDR_EXPR nodes which have different semantics than
87 other expressions. Inside an ADDR_EXPR node, the only operands that we
88 need to consider are indices into arrays. For instance, &a.b[i] should
89 generate a USE of 'i' but it should not generate a VUSE for 'a' nor a
90 VUSE for 'b'. */
91#define opf_no_vops (1 << 1)
92
93/* Operand is in a place where address-taken does not imply addressable. */
94#define opf_non_addressable (1 << 3)
95
96/* Operand is in a place where opf_non_addressable does not apply. */
97#define opf_not_non_addressable (1 << 4)
98
99/* Operand is having its address taken. */
100#define opf_address_taken (1 << 5)
101
102/* Array for building all the use operands. */
103static vec<tree *> build_uses;
104
105/* The built VDEF operand. */
106static tree build_vdef;
107
108/* The built VUSE operand. */
109static tree build_vuse;
110
111/* Bitmap obstack for our datastructures that needs to survive across
112 compilations of multiple functions. */
113static bitmap_obstack operands_bitmap_obstack;
114
115static void get_expr_operands (struct function *, gimple *, tree *, int);
116
117/* Number of functions with initialized ssa_operands. */
118static int n_initialized = 0;
119
120/* Accessor to tree-ssa-operands.c caches. */
121static inline struct ssa_operands *
122gimple_ssa_operands (const struct function *fun)
123{
124 return &fun->gimple_df->ssa_operands;
125}
126
127
128/* Return true if the SSA operands cache is active. */
129
130bool
131ssa_operands_active (struct function *fun)
132{
133 if (fun == NULL)
134 return false;
135
136 return fun->gimple_df && gimple_ssa_operands (fun)->ops_active;
137}
138
139
140/* Create the VOP variable, an artificial global variable to act as a
141 representative of all of the virtual operands FUD chain. */
142
143static void
144create_vop_var (struct function *fn)
145{
146 tree global_var;
147
148 gcc_assert (fn->gimple_df->vop == NULL_TREE);
149
150 global_var = build_decl (BUILTINS_LOCATION, VAR_DECL,
151 get_identifier (".MEM"),
152 void_type_node);
153 DECL_ARTIFICIAL (global_var) = 1;
154 DECL_IGNORED_P (global_var) = 1;
155 TREE_READONLY (global_var) = 0;
156 DECL_EXTERNAL (global_var) = 1;
157 TREE_STATIC (global_var) = 1;
158 TREE_USED (global_var) = 1;
159 DECL_CONTEXT (global_var) = NULL_TREE;
160 TREE_THIS_VOLATILE (global_var) = 0;
161 TREE_ADDRESSABLE (global_var) = 0;
162 VAR_DECL_IS_VIRTUAL_OPERAND (global_var) = 1;
163
164 fn->gimple_df->vop = global_var;
165}
166
167/* These are the sizes of the operand memory buffer in bytes which gets
168 allocated each time more operands space is required. The final value is
169 the amount that is allocated every time after that.
170 In 1k we can fit 25 use operands (or 63 def operands) on a host with
171 8 byte pointers, that would be 10 statements each with 1 def and 2
172 uses. */
173
174#define OP_SIZE_INIT 0
175#define OP_SIZE_1 (1024 - sizeof (void *))
176#define OP_SIZE_2 (1024 * 4 - sizeof (void *))
177#define OP_SIZE_3 (1024 * 16 - sizeof (void *))
178
179/* Initialize the operand cache routines. */
180
181void
182init_ssa_operands (struct function *fn)
183{
184 if (!n_initialized++)
185 {
186 build_uses.create (10);
187 build_vuse = NULL_TREE;
188 build_vdef = NULL_TREE;
189 bitmap_obstack_initialize (&operands_bitmap_obstack);
190 }
191
192 gcc_assert (gimple_ssa_operands (fn)->operand_memory == NULL);
193 gimple_ssa_operands (fn)->operand_memory_index
194 = gimple_ssa_operands (fn)->ssa_operand_mem_size;
195 gimple_ssa_operands (fn)->ops_active = true;
196 gimple_ssa_operands (fn)->ssa_operand_mem_size = OP_SIZE_INIT;
197 create_vop_var (fn);
198}
199
200
201/* Dispose of anything required by the operand routines. */
202
203void
204fini_ssa_operands (struct function *fn)
205{
206 struct ssa_operand_memory_d *ptr;
207
208 if (!--n_initialized)
209 {
210 build_uses.release ();
211 build_vdef = NULL_TREE;
212 build_vuse = NULL_TREE;
213 }
214
215 gimple_ssa_operands (fn)->free_uses = NULL;
216
217 while ((ptr = gimple_ssa_operands (fn)->operand_memory) != NULL)
218 {
219 gimple_ssa_operands (fn)->operand_memory
220 = gimple_ssa_operands (fn)->operand_memory->next;
221 ggc_free (ptr);
222 }
223
224 gimple_ssa_operands (fn)->ops_active = false;
225
226 if (!n_initialized)
227 bitmap_obstack_release (&operands_bitmap_obstack);
228
229 fn->gimple_df->vop = NULL_TREE;
230}
231
232
233/* Return memory for an operand of size SIZE. */
234
235static inline void *
236ssa_operand_alloc (struct function *fn, unsigned size)
237{
238 char *ptr;
239
240 gcc_assert (size == sizeof (struct use_optype_d));
241
242 if (gimple_ssa_operands (fn)->operand_memory_index + size
243 >= gimple_ssa_operands (fn)->ssa_operand_mem_size)
244 {
245 struct ssa_operand_memory_d *ptr;
246
247 switch (gimple_ssa_operands (fn)->ssa_operand_mem_size)
248 {
249 case OP_SIZE_INIT:
250 gimple_ssa_operands (fn)->ssa_operand_mem_size = OP_SIZE_1;
251 break;
252 case OP_SIZE_1:
253 gimple_ssa_operands (fn)->ssa_operand_mem_size = OP_SIZE_2;
254 break;
255 case OP_SIZE_2:
256 case OP_SIZE_3:
257 gimple_ssa_operands (fn)->ssa_operand_mem_size = OP_SIZE_3;
258 break;
259 default:
260 gcc_unreachable ();
261 }
262
263
264 ptr = (ssa_operand_memory_d *) ggc_internal_alloc
265 (sizeof (void *) + gimple_ssa_operands (fn)->ssa_operand_mem_size);
266
267 ptr->next = gimple_ssa_operands (fn)->operand_memory;
268 gimple_ssa_operands (fn)->operand_memory = ptr;
269 gimple_ssa_operands (fn)->operand_memory_index = 0;
270 }
271
272 ptr = &(gimple_ssa_operands (fn)->operand_memory
273 ->mem[gimple_ssa_operands (fn)->operand_memory_index]);
274 gimple_ssa_operands (fn)->operand_memory_index += size;
275 return ptr;
276}
277
278
279/* Allocate a USE operand. */
280
281static inline struct use_optype_d *
282alloc_use (struct function *fn)
283{
284 struct use_optype_d *ret;
285 if (gimple_ssa_operands (fn)->free_uses)
286 {
287 ret = gimple_ssa_operands (fn)->free_uses;
288 gimple_ssa_operands (fn)->free_uses
289 = gimple_ssa_operands (fn)->free_uses->next;
290 }
291 else
292 ret = (struct use_optype_d *)
293 ssa_operand_alloc (fn, sizeof (struct use_optype_d));
294 return ret;
295}
296
297
298/* Adds OP to the list of uses of statement STMT after LAST. */
299
300static inline use_optype_p
301add_use_op (struct function *fn, gimple *stmt, tree *op, use_optype_p last)
302{
303 use_optype_p new_use;
304
305 new_use = alloc_use (fn);
306 USE_OP_PTR (new_use)->use = op;
307 link_imm_use_stmt (USE_OP_PTR (new_use), *op, stmt);
308 last->next = new_use;
309 new_use->next = NULL;
310 return new_use;
311}
312
313
314
315/* Takes elements from build_defs and turns them into def operands of STMT.
316 TODO -- Make build_defs vec of tree *. */
317
318static inline void
319finalize_ssa_defs (struct function *fn, gimple *stmt)
320{
321 /* Pre-pend the vdef we may have built. */
322 if (build_vdef != NULL_TREE)
323 {
324 tree oldvdef = gimple_vdef (stmt);
325 if (oldvdef
326 && TREE_CODE (oldvdef) == SSA_NAME)
327 oldvdef = SSA_NAME_VAR (oldvdef);
328 if (oldvdef != build_vdef)
329 gimple_set_vdef (stmt, build_vdef);
330 }
331
332 /* Clear and unlink a no longer necessary VDEF. */
333 if (build_vdef == NULL_TREE
334 && gimple_vdef (stmt) != NULL_TREE)
335 {
336 if (TREE_CODE (gimple_vdef (stmt)) == SSA_NAME)
337 {
338 unlink_stmt_vdef (stmt);
339 release_ssa_name_fn (fn, gimple_vdef (stmt));
340 }
341 gimple_set_vdef (stmt, NULL_TREE);
342 }
343
344 /* If we have a non-SSA_NAME VDEF, mark it for renaming. */
345 if (gimple_vdef (stmt)
346 && TREE_CODE (gimple_vdef (stmt)) != SSA_NAME)
347 {
348 fn->gimple_df->rename_vops = 1;
349 fn->gimple_df->ssa_renaming_needed = 1;
350 }
351}
352
353
354/* Takes elements from build_uses and turns them into use operands of STMT. */
355
356static inline void
357finalize_ssa_uses (struct function *fn, gimple *stmt)
358{
359 unsigned new_i;
360 struct use_optype_d new_list;
361 use_optype_p old_ops, ptr, last;
362
363 /* Pre-pend the VUSE we may have built. */
364 if (build_vuse != NULL_TREE)
365 {
366 tree oldvuse = gimple_vuse (stmt);
367 if (oldvuse
368 && TREE_CODE (oldvuse) == SSA_NAME)
369 oldvuse = SSA_NAME_VAR (oldvuse);
370 if (oldvuse != (build_vuse != NULL_TREE
371 ? build_vuse : build_vdef))
372 gimple_set_vuse (stmt, NULL_TREE);
373 build_uses.safe_insert (0, gimple_vuse_ptr (stmt));
374 }
375
376 new_list.next = NULL;
377 last = &new_list;
378
379 old_ops = gimple_use_ops (stmt);
380
381 /* Clear a no longer necessary VUSE. */
382 if (build_vuse == NULL_TREE
383 && gimple_vuse (stmt) != NULL_TREE)
384 gimple_set_vuse (stmt, NULL_TREE);
385
386 /* If there is anything in the old list, free it. */
387 if (old_ops)
388 {
389 for (ptr = old_ops; ptr->next; ptr = ptr->next)
390 delink_imm_use (USE_OP_PTR (ptr));
391 delink_imm_use (USE_OP_PTR (ptr));
392 ptr->next = gimple_ssa_operands (fn)->free_uses;
393 gimple_ssa_operands (fn)->free_uses = old_ops;
394 }
395
396 /* If we added a VUSE, make sure to set the operand if it is not already
397 present and mark it for renaming. */
398 if (build_vuse != NULL_TREE
399 && gimple_vuse (stmt) == NULL_TREE)
400 {
401 gimple_set_vuse (stmt, gimple_vop (fn));
402 fn->gimple_df->rename_vops = 1;
403 fn->gimple_df->ssa_renaming_needed = 1;
404 }
405
406 /* Now create nodes for all the new nodes. */
407 for (new_i = 0; new_i < build_uses.length (); new_i++)
408 {
409 tree *op = build_uses[new_i];
410 last = add_use_op (fn, stmt, op, last);
411 }
412
413 /* Now set the stmt's operands. */
414 gimple_set_use_ops (stmt, new_list.next);
415}
416
417
418/* Clear the in_list bits and empty the build array for VDEFs and
419 VUSEs. */
420
421static inline void
422cleanup_build_arrays (void)
423{
424 build_vdef = NULL_TREE;
425 build_vuse = NULL_TREE;
426 build_uses.truncate (0);
427}
428
429
430/* Finalize all the build vectors, fill the new ones into INFO. */
431
432static inline void
433finalize_ssa_stmt_operands (struct function *fn, gimple *stmt)
434{
435 finalize_ssa_defs (fn, stmt);
436 finalize_ssa_uses (fn, stmt);
437 cleanup_build_arrays ();
438}
439
440
441/* Start the process of building up operands vectors in INFO. */
442
443static inline void
444start_ssa_stmt_operands (void)
445{
446 gcc_assert (build_uses.length () == 0);
447 gcc_assert (build_vuse == NULL_TREE);
448 gcc_assert (build_vdef == NULL_TREE);
449}
450
451
452/* Add USE_P to the list of pointers to operands. */
453
454static inline void
455append_use (tree *use_p)
456{
457 build_uses.safe_push (use_p);
458}
459
460
461/* Add VAR to the set of variables that require a VDEF operator. */
462
463static inline void
464append_vdef (tree var)
465{
466 gcc_assert ((build_vdef == NULL_TREE
467 || build_vdef == var)
468 && (build_vuse == NULL_TREE
469 || build_vuse == var));
470
471 build_vdef = var;
472 build_vuse = var;
473}
474
475
476/* Add VAR to the set of variables that require a VUSE operator. */
477
478static inline void
479append_vuse (tree var)
480{
481 gcc_assert (build_vuse == NULL_TREE
482 || build_vuse == var);
483
484 build_vuse = var;
485}
486
487/* Add virtual operands for STMT. FLAGS is as in get_expr_operands. */
488
489static void
490add_virtual_operand (struct function *fn,
491 gimple *stmt ATTRIBUTE_UNUSED, int flags)
492{
493 /* Add virtual operands to the stmt, unless the caller has specifically
494 requested not to do that (used when adding operands inside an
495 ADDR_EXPR expression). */
496 if (flags & opf_no_vops)
497 return;
498
499 gcc_assert (!is_gimple_debug (stmt));
500
501 if (flags & opf_def)
502 append_vdef (gimple_vop (fn));
503 else
504 append_vuse (gimple_vop (fn));
505}
506
507
508/* Add *VAR_P to the appropriate operand array for statement STMT.
509 FLAGS is as in get_expr_operands. If *VAR_P is a GIMPLE register,
510 it will be added to the statement's real operands, otherwise it is
511 added to virtual operands. */
512
513static void
514add_stmt_operand (struct function *fn, tree *var_p, gimple *stmt, int flags)
515{
516 tree var = *var_p;
517
518 gcc_assert (SSA_VAR_P (*var_p));
519
520 if (is_gimple_reg (var))
521 {
522 /* The variable is a GIMPLE register. Add it to real operands. */
523 if (flags & opf_def)
524 ;
525 else
526 append_use (var_p);
527 if (DECL_P (*var_p))
528 fn->gimple_df->ssa_renaming_needed = 1;
529 }
530 else
531 {
532 /* Mark statements with volatile operands. */
533 if (!(flags & opf_no_vops)
534 && TREE_THIS_VOLATILE (var))
535 gimple_set_has_volatile_ops (stmt, true);
536
537 /* The variable is a memory access. Add virtual operands. */
538 add_virtual_operand (fn, stmt, flags);
539 }
540}
541
542/* Mark the base address of REF as having its address taken.
543 REF may be a single variable whose address has been taken or any
544 other valid GIMPLE memory reference (structure reference, array,
545 etc). */
546
547static void
548mark_address_taken (tree ref)
549{
550 tree var;
551
552 /* Note that it is *NOT OKAY* to use the target of a COMPONENT_REF
553 as the only thing we take the address of. If VAR is a structure,
554 taking the address of a field means that the whole structure may
555 be referenced using pointer arithmetic. See PR 21407 and the
556 ensuing mailing list discussion. */
557 var = get_base_address (ref);
558 if (var)
559 {
560 if (DECL_P (var))
561 TREE_ADDRESSABLE (var) = 1;
562 else if (TREE_CODE (var) == MEM_REF
563 && TREE_CODE (TREE_OPERAND (var, 0)) == ADDR_EXPR
564 && DECL_P (TREE_OPERAND (TREE_OPERAND (var, 0), 0)))
565 TREE_ADDRESSABLE (TREE_OPERAND (TREE_OPERAND (var, 0), 0)) = 1;
566 }
567}
568
569
570/* A subroutine of get_expr_operands to handle MEM_REF.
571
572 STMT is the statement being processed, EXPR is the MEM_REF
573 that got us here.
574
575 FLAGS is as in get_expr_operands. */
576
577static void
578get_mem_ref_operands (struct function *fn,
579 gimple *stmt, tree expr, int flags)
580{
581 tree *pptr = &TREE_OPERAND (expr, 0);
582
583 if (!(flags & opf_no_vops)
584 && TREE_THIS_VOLATILE (expr))
585 gimple_set_has_volatile_ops (stmt, true);
586
587 /* Add the VOP. */
588 add_virtual_operand (fn, stmt, flags);
589
590 /* If requested, add a USE operand for the base pointer. */
591 get_expr_operands (fn, stmt, pptr,
592 opf_non_addressable | opf_use
593 | (flags & (opf_no_vops|opf_not_non_addressable)));
594}
595
596
597/* A subroutine of get_expr_operands to handle TARGET_MEM_REF. */
598
599static void
600get_tmr_operands (struct function *fn, gimple *stmt, tree expr, int flags)
601{
602 if (!(flags & opf_no_vops)
603 && TREE_THIS_VOLATILE (expr))
604 gimple_set_has_volatile_ops (stmt, true);
605
606 /* First record the real operands. */
607 get_expr_operands (fn, stmt,
608 &TMR_BASE (expr), opf_use | (flags & opf_no_vops));
609 get_expr_operands (fn, stmt,
610 &TMR_INDEX (expr), opf_use | (flags & opf_no_vops));
611 get_expr_operands (fn, stmt,
612 &TMR_INDEX2 (expr), opf_use | (flags & opf_no_vops));
613
614 add_virtual_operand (fn, stmt, flags);
615}
616
617
618/* If STMT is a call that may clobber globals and other symbols that
619 escape, add them to the VDEF/VUSE lists for it. */
620
621static void
622maybe_add_call_vops (struct function *fn, gcall *stmt)
623{
624 int call_flags = gimple_call_flags (stmt);
625
626 /* If aliases have been computed already, add VDEF or VUSE
627 operands for all the symbols that have been found to be
628 call-clobbered. */
629 if (!(call_flags & ECF_NOVOPS))
630 {
631 /* A 'pure' or a 'const' function never call-clobbers anything. */
632 if (!(call_flags & (ECF_PURE | ECF_CONST)))
633 add_virtual_operand (fn, stmt, opf_def);
634 else if (!(call_flags & ECF_CONST))
635 add_virtual_operand (fn, stmt, opf_use);
636 }
637}
638
639
640/* Scan operands in the ASM_EXPR stmt referred to in INFO. */
641
642static void
643get_asm_stmt_operands (struct function *fn, gasm *stmt)
644{
645 size_t i, noutputs;
646 const char **oconstraints;
647 const char *constraint;
648 bool allows_mem, allows_reg, is_inout;
649
650 noutputs = gimple_asm_noutputs (stmt);
651 oconstraints = (const char **) alloca ((noutputs) * sizeof (const char *));
652
653 /* Gather all output operands. */
654 for (i = 0; i < gimple_asm_noutputs (stmt); i++)
655 {
656 tree link = gimple_asm_output_op (stmt, i);
657 constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
658 oconstraints[i] = constraint;
659 parse_output_constraint (&constraint, i, 0, 0, &allows_mem,
660 &allows_reg, &is_inout);
661
662 /* This should have been split in gimplify_asm_expr. */
663 gcc_assert (!allows_reg || !is_inout);
664
665 /* Memory operands are addressable. Note that STMT needs the
666 address of this operand. */
667 if (!allows_reg && allows_mem)
668 mark_address_taken (TREE_VALUE (link));
669
670 get_expr_operands (fn, stmt,
671 &TREE_VALUE (link), opf_def | opf_not_non_addressable);
672 }
673
674 /* Gather all input operands. */
675 for (i = 0; i < gimple_asm_ninputs (stmt); i++)
676 {
677 tree link = gimple_asm_input_op (stmt, i);
678 constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
679 parse_input_constraint (&constraint, 0, 0, noutputs, 0, oconstraints,
680 &allows_mem, &allows_reg);
681
682 /* Memory operands are addressable. Note that STMT needs the
683 address of this operand. */
684 if (!allows_reg && allows_mem)
685 mark_address_taken (TREE_VALUE (link));
686
687 get_expr_operands (fn, stmt, &TREE_VALUE (link), opf_not_non_addressable);
688 }
689
690 /* Clobber all memory and addressable symbols for asm ("" : : : "memory"); */
691 if (gimple_asm_clobbers_memory_p (stmt))
692 add_virtual_operand (fn, stmt, opf_def);
693}
694
695
696/* Recursively scan the expression pointed to by EXPR_P in statement
697 STMT. FLAGS is one of the OPF_* constants modifying how to
698 interpret the operands found. */
699
700static void
701get_expr_operands (struct function *fn, gimple *stmt, tree *expr_p, int flags)
702{
703 enum tree_code code;
704 enum tree_code_class codeclass;
705 tree expr = *expr_p;
706 int uflags = opf_use;
707
708 if (expr == NULL)
709 return;
710
711 if (is_gimple_debug (stmt))
712 uflags |= (flags & opf_no_vops);
713
714 code = TREE_CODE (expr);
715 codeclass = TREE_CODE_CLASS (code);
716
717 switch (code)
718 {
719 case ADDR_EXPR:
720 /* Taking the address of a variable does not represent a
721 reference to it, but the fact that the statement takes its
722 address will be of interest to some passes (e.g. alias
723 resolution). */
724 if ((!(flags & opf_non_addressable)
725 || (flags & opf_not_non_addressable))
726 && !is_gimple_debug (stmt))
727 mark_address_taken (TREE_OPERAND (expr, 0));
728
729 /* Otherwise, there may be variables referenced inside but there
730 should be no VUSEs created, since the referenced objects are
731 not really accessed. The only operands that we should find
732 here are ARRAY_REF indices which will always be real operands
733 (GIMPLE does not allow non-registers as array indices). */
734 flags |= opf_no_vops;
735 get_expr_operands (fn, stmt, &TREE_OPERAND (expr, 0),
736 flags | opf_not_non_addressable | opf_address_taken);
737 return;
738
739 case SSA_NAME:
740 case VAR_DECL:
741 case PARM_DECL:
742 case RESULT_DECL:
743 if (!(flags & opf_address_taken))
744 add_stmt_operand (fn, expr_p, stmt, flags);
745 return;
746
747 case DEBUG_EXPR_DECL:
748 gcc_assert (gimple_debug_bind_p (stmt));
749 return;
750
751 case MEM_REF:
752 get_mem_ref_operands (fn, stmt, expr, flags);
753 return;
754
755 case TARGET_MEM_REF:
756 get_tmr_operands (fn, stmt, expr, flags);
757 return;
758
759 case ARRAY_REF:
760 case ARRAY_RANGE_REF:
761 case COMPONENT_REF:
762 case REALPART_EXPR:
763 case IMAGPART_EXPR:
764 {
765 if (!(flags & opf_no_vops)
766 && TREE_THIS_VOLATILE (expr))
767 gimple_set_has_volatile_ops (stmt, true);
768
769 get_expr_operands (fn, stmt, &TREE_OPERAND (expr, 0), flags);
770
771 if (code == COMPONENT_REF)
772 {
773 if (!(flags & opf_no_vops)
774 && TREE_THIS_VOLATILE (TREE_OPERAND (expr, 1)))
775 gimple_set_has_volatile_ops (stmt, true);
776 get_expr_operands (fn, stmt, &TREE_OPERAND (expr, 2), uflags);
777 }
778 else if (code == ARRAY_REF || code == ARRAY_RANGE_REF)
779 {
780 get_expr_operands (fn, stmt, &TREE_OPERAND (expr, 1), uflags);
781 get_expr_operands (fn, stmt, &TREE_OPERAND (expr, 2), uflags);
782 get_expr_operands (fn, stmt, &TREE_OPERAND (expr, 3), uflags);
783 }
784
785 return;
786 }
787
788 case WITH_SIZE_EXPR:
789 /* WITH_SIZE_EXPR is a pass-through reference to its first argument,
790 and an rvalue reference to its second argument. */
791 get_expr_operands (fn, stmt, &TREE_OPERAND (expr, 1), uflags);
792 get_expr_operands (fn, stmt, &TREE_OPERAND (expr, 0), flags);
793 return;
794
795 case COND_EXPR:
796 case VEC_COND_EXPR:
797 case VEC_PERM_EXPR:
798 get_expr_operands (fn, stmt, &TREE_OPERAND (expr, 0), uflags);
799 get_expr_operands (fn, stmt, &TREE_OPERAND (expr, 1), uflags);
800 get_expr_operands (fn, stmt, &TREE_OPERAND (expr, 2), uflags);
801 return;
802
803 case CONSTRUCTOR:
804 {
805 /* General aggregate CONSTRUCTORs have been decomposed, but they
806 are still in use as the COMPLEX_EXPR equivalent for vectors. */
807 constructor_elt *ce;
808 unsigned HOST_WIDE_INT idx;
809
810 /* A volatile constructor is actually TREE_CLOBBER_P, transfer
811 the volatility to the statement, don't use TREE_CLOBBER_P for
812 mirroring the other uses of THIS_VOLATILE in this file. */
813 if (!(flags & opf_no_vops)
814 && TREE_THIS_VOLATILE (expr))
815 gimple_set_has_volatile_ops (stmt, true);
816
817 for (idx = 0;
818 vec_safe_iterate (CONSTRUCTOR_ELTS (expr), idx, &ce);
819 idx++)
820 get_expr_operands (fn, stmt, &ce->value, uflags);
821
822 return;
823 }
824
825 case BIT_FIELD_REF:
826 if (!(flags & opf_no_vops)
827 && TREE_THIS_VOLATILE (expr))
828 gimple_set_has_volatile_ops (stmt, true);
829 /* FALLTHRU */
830
831 case VIEW_CONVERT_EXPR:
832 do_unary:
833 get_expr_operands (fn, stmt, &TREE_OPERAND (expr, 0), flags);
834 return;
835
836 case BIT_INSERT_EXPR:
837 case COMPOUND_EXPR:
838 case OBJ_TYPE_REF:
839 case ASSERT_EXPR:
840 do_binary:
841 {
842 get_expr_operands (fn, stmt, &TREE_OPERAND (expr, 0), flags);
843 get_expr_operands (fn, stmt, &TREE_OPERAND (expr, 1), flags);
844 return;
845 }
846
847 case DOT_PROD_EXPR:
848 case SAD_EXPR:
849 case REALIGN_LOAD_EXPR:
850 case WIDEN_MULT_PLUS_EXPR:
851 case WIDEN_MULT_MINUS_EXPR:
852 case FMA_EXPR:
853 {
854 get_expr_operands (fn, stmt, &TREE_OPERAND (expr, 0), flags);
855 get_expr_operands (fn, stmt, &TREE_OPERAND (expr, 1), flags);
856 get_expr_operands (fn, stmt, &TREE_OPERAND (expr, 2), flags);
857 return;
858 }
859
860 case FUNCTION_DECL:
861 case LABEL_DECL:
862 case CONST_DECL:
863 case CASE_LABEL_EXPR:
864 /* Expressions that make no memory references. */
865 return;
866
867 default:
868 if (codeclass == tcc_unary)
869 goto do_unary;
870 if (codeclass == tcc_binary || codeclass == tcc_comparison)
871 goto do_binary;
872 if (codeclass == tcc_constant || codeclass == tcc_type)
873 return;
874 }
875
876 /* If we get here, something has gone wrong. */
877 if (flag_checking)
878 {
879 fprintf (stderr, "unhandled expression in get_expr_operands():\n");
880 debug_tree (expr);
881 fputs ("\n", stderr);
882 gcc_unreachable ();
883 }
884}
885
886
887/* Parse STMT looking for operands. When finished, the various
888 build_* operand vectors will have potential operands in them. */
889
890static void
891parse_ssa_operands (struct function *fn, gimple *stmt)
892{
893 enum gimple_code code = gimple_code (stmt);
894 size_t i, n, start = 0;
895
896 switch (code)
897 {
898 case GIMPLE_ASM:
899 get_asm_stmt_operands (fn, as_a <gasm *> (stmt));
900 break;
901
902 case GIMPLE_TRANSACTION:
903 /* The start of a transaction is a memory barrier. */
904 add_virtual_operand (fn, stmt, opf_def | opf_use);
905 break;
906
907 case GIMPLE_DEBUG:
908 if (gimple_debug_bind_p (stmt)
909 && gimple_debug_bind_has_value_p (stmt))
910 get_expr_operands (fn, stmt, gimple_debug_bind_get_value_ptr (stmt),
911 opf_use | opf_no_vops);
912 break;
913
914 case GIMPLE_RETURN:
915 append_vuse (gimple_vop (fn));
916 goto do_default;
917
918 case GIMPLE_CALL:
919 /* Add call-clobbered operands, if needed. */
920 maybe_add_call_vops (fn, as_a <gcall *> (stmt));
921 /* FALLTHRU */
922
923 case GIMPLE_ASSIGN:
924 get_expr_operands (fn, stmt, gimple_op_ptr (stmt, 0), opf_def);
925 start = 1;
926 /* FALLTHRU */
927
928 default:
929 do_default:
930 n = gimple_num_ops (stmt);
931 for (i = start; i < n; i++)
932 get_expr_operands (fn, stmt, gimple_op_ptr (stmt, i), opf_use);
933 break;
934 }
935}
936
937
938/* Create an operands cache for STMT. */
939
940static void
941build_ssa_operands (struct function *fn, gimple *stmt)
942{
943 /* Initially assume that the statement has no volatile operands. */
944 gimple_set_has_volatile_ops (stmt, false);
945
946 start_ssa_stmt_operands ();
947 parse_ssa_operands (fn, stmt);
948 finalize_ssa_stmt_operands (fn, stmt);
949}
950
951/* Verifies SSA statement operands. */
952
953DEBUG_FUNCTION bool
954verify_ssa_operands (struct function *fn, gimple *stmt)
955{
956 use_operand_p use_p;
957 def_operand_p def_p;
958 ssa_op_iter iter;
959 unsigned i;
960 tree def;
961 bool volatile_p = gimple_has_volatile_ops (stmt);
962
963 /* build_ssa_operands w/o finalizing them. */
964 gimple_set_has_volatile_ops (stmt, false);
965 start_ssa_stmt_operands ();
966 parse_ssa_operands (fn, stmt);
967
968 /* Now verify the built operands are the same as present in STMT. */
969 def = gimple_vdef (stmt);
970 if (def
971 && TREE_CODE (def) == SSA_NAME)
972 def = SSA_NAME_VAR (def);
973 if (build_vdef != def)
974 {
975 error ("virtual definition of statement not up-to-date");
976 return true;
977 }
978 if (gimple_vdef (stmt)
979 && ((def_p = gimple_vdef_op (stmt)) == NULL_DEF_OPERAND_P
980 || DEF_FROM_PTR (def_p) != gimple_vdef (stmt)))
981 {
982 error ("virtual def operand missing for stmt");
983 return true;
984 }
985
986 tree use = gimple_vuse (stmt);
987 if (use
988 && TREE_CODE (use) == SSA_NAME)
989 use = SSA_NAME_VAR (use);
990 if (build_vuse != use)
991 {
992 error ("virtual use of statement not up-to-date");
993 return true;
994 }
995 if (gimple_vuse (stmt)
996 && ((use_p = gimple_vuse_op (stmt)) == NULL_USE_OPERAND_P
997 || USE_FROM_PTR (use_p) != gimple_vuse (stmt)))
998 {
999 error ("virtual use operand missing for stmt");
1000 return true;
1001 }
1002
1003 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1004 {
1005 tree *op;
1006 FOR_EACH_VEC_ELT (build_uses, i, op)
1007 {
1008 if (use_p->use == op)
1009 {
1010 build_uses[i] = NULL;
1011 break;
1012 }
1013 }
1014 if (i == build_uses.length ())
1015 {
1016 error ("excess use operand for stmt");
1017 debug_generic_expr (USE_FROM_PTR (use_p));
1018 return true;
1019 }
1020 }
1021
1022 tree *op;
1023 FOR_EACH_VEC_ELT (build_uses, i, op)
1024 if (op != NULL)
1025 {
1026 error ("use operand missing for stmt");
1027 debug_generic_expr (*op);
1028 return true;
1029 }
1030
1031 if (gimple_has_volatile_ops (stmt) != volatile_p)
1032 {
1033 error ("stmt volatile flag not up-to-date");
1034 return true;
1035 }
1036
1037 cleanup_build_arrays ();
1038 return false;
1039}
1040
1041
1042/* Releases the operands of STMT back to their freelists, and clears
1043 the stmt operand lists. */
1044
1045void
1046free_stmt_operands (struct function *fn, gimple *stmt)
1047{
1048 use_optype_p uses = gimple_use_ops (stmt), last_use;
1049
1050 if (uses)
1051 {
1052 for (last_use = uses; last_use->next; last_use = last_use->next)
1053 delink_imm_use (USE_OP_PTR (last_use));
1054 delink_imm_use (USE_OP_PTR (last_use));
1055 last_use->next = gimple_ssa_operands (fn)->free_uses;
1056 gimple_ssa_operands (fn)->free_uses = uses;
1057 gimple_set_use_ops (stmt, NULL);
1058 }
1059
1060 if (gimple_has_mem_ops (stmt))
1061 {
1062 gimple_set_vuse (stmt, NULL_TREE);
1063 gimple_set_vdef (stmt, NULL_TREE);
1064 }
1065}
1066
1067
1068/* Get the operands of statement STMT. */
1069
1070void
1071update_stmt_operands (struct function *fn, gimple *stmt)
1072{
1073 /* If update_stmt_operands is called before SSA is initialized, do
1074 nothing. */
1075 if (!ssa_operands_active (fn))
1076 return;
1077
1078 timevar_push (TV_TREE_OPS);
1079
1080 gcc_assert (gimple_modified_p (stmt));
1081 build_ssa_operands (fn, stmt);
1082 gimple_set_modified (stmt, false);
1083
1084 timevar_pop (TV_TREE_OPS);
1085}
1086
1087
1088/* Swap operands EXP0 and EXP1 in statement STMT. No attempt is done
1089 to test the validity of the swap operation. */
1090
1091void
1092swap_ssa_operands (gimple *stmt, tree *exp0, tree *exp1)
1093{
1094 tree op0, op1;
1095 op0 = *exp0;
1096 op1 = *exp1;
1097
1098 if (op0 != op1)
1099 {
1100 /* Attempt to preserve the relative positions of these two operands in
1101 their * respective immediate use lists by adjusting their use pointer
1102 to point to the new operand position. */
1103 use_optype_p use0, use1, ptr;
1104 use0 = use1 = NULL;
1105
1106 /* Find the 2 operands in the cache, if they are there. */
1107 for (ptr = gimple_use_ops (stmt); ptr; ptr = ptr->next)
1108 if (USE_OP_PTR (ptr)->use == exp0)
1109 {
1110 use0 = ptr;
1111 break;
1112 }
1113
1114 for (ptr = gimple_use_ops (stmt); ptr; ptr = ptr->next)
1115 if (USE_OP_PTR (ptr)->use == exp1)
1116 {
1117 use1 = ptr;
1118 break;
1119 }
1120
1121 /* And adjust their location to point to the new position of the
1122 operand. */
1123 if (use0)
1124 USE_OP_PTR (use0)->use = exp1;
1125 if (use1)
1126 USE_OP_PTR (use1)->use = exp0;
1127
1128 /* Now swap the data. */
1129 *exp0 = op1;
1130 *exp1 = op0;
1131 }
1132}
1133
1134
1135/* Scan the immediate_use list for VAR making sure its linked properly.
1136 Return TRUE if there is a problem and emit an error message to F. */
1137
1138DEBUG_FUNCTION bool
1139verify_imm_links (FILE *f, tree var)
1140{
1141 use_operand_p ptr, prev, list;
1142 unsigned int count;
1143
1144 gcc_assert (TREE_CODE (var) == SSA_NAME);
1145
1146 list = &(SSA_NAME_IMM_USE_NODE (var));
1147 gcc_assert (list->use == NULL);
1148
1149 if (list->prev == NULL)
1150 {
1151 gcc_assert (list->next == NULL);
1152 return false;
1153 }
1154
1155 prev = list;
1156 count = 0;
1157 for (ptr = list->next; ptr != list; )
1158 {
1159 if (prev != ptr->prev)
1160 {
1161 fprintf (f, "prev != ptr->prev\n");
1162 goto error;
1163 }
1164
1165 if (ptr->use == NULL)
1166 {
1167 fprintf (f, "ptr->use == NULL\n");
1168 goto error; /* 2 roots, or SAFE guard node. */
1169 }
1170 else if (*(ptr->use) != var)
1171 {
1172 fprintf (f, "*(ptr->use) != var\n");
1173 goto error;
1174 }
1175
1176 prev = ptr;
1177 ptr = ptr->next;
1178
1179 count++;
1180 if (count == 0)
1181 {
1182 fprintf (f, "number of immediate uses doesn't fit unsigned int\n");
1183 goto error;
1184 }
1185 }
1186
1187 /* Verify list in the other direction. */
1188 prev = list;
1189 for (ptr = list->prev; ptr != list; )
1190 {
1191 if (prev != ptr->next)
1192 {
1193 fprintf (f, "prev != ptr->next\n");
1194 goto error;
1195 }
1196 prev = ptr;
1197 ptr = ptr->prev;
1198 if (count == 0)
1199 {
1200 fprintf (f, "count-- < 0\n");
1201 goto error;
1202 }
1203 count--;
1204 }
1205
1206 if (count != 0)
1207 {
1208 fprintf (f, "count != 0\n");
1209 goto error;
1210 }
1211
1212 return false;
1213
1214 error:
1215 if (ptr->loc.stmt && gimple_modified_p (ptr->loc.stmt))
1216 {
1217 fprintf (f, " STMT MODIFIED. - <%p> ", (void *)ptr->loc.stmt);
1218 print_gimple_stmt (f, ptr->loc.stmt, 0, TDF_SLIM);
1219 }
1220 fprintf (f, " IMM ERROR : (use_p : tree - %p:%p)", (void *)ptr,
1221 (void *)ptr->use);
1222 print_generic_expr (f, USE_FROM_PTR (ptr), TDF_SLIM);
1223 fprintf (f, "\n");
1224 return true;
1225}
1226
1227
1228/* Dump all the immediate uses to FILE. */
1229
1230void
1231dump_immediate_uses_for (FILE *file, tree var)
1232{
1233 imm_use_iterator iter;
1234 use_operand_p use_p;
1235
1236 gcc_assert (var && TREE_CODE (var) == SSA_NAME);
1237
1238 print_generic_expr (file, var, TDF_SLIM);
1239 fprintf (file, " : -->");
1240 if (has_zero_uses (var))
1241 fprintf (file, " no uses.\n");
1242 else
1243 if (has_single_use (var))
1244 fprintf (file, " single use.\n");
1245 else
1246 fprintf (file, "%d uses.\n", num_imm_uses (var));
1247
1248 FOR_EACH_IMM_USE_FAST (use_p, iter, var)
1249 {
1250 if (use_p->loc.stmt == NULL && use_p->use == NULL)
1251 fprintf (file, "***end of stmt iterator marker***\n");
1252 else
1253 if (!is_gimple_reg (USE_FROM_PTR (use_p)))
1254 print_gimple_stmt (file, USE_STMT (use_p), 0, TDF_VOPS|TDF_MEMSYMS);
1255 else
1256 print_gimple_stmt (file, USE_STMT (use_p), 0, TDF_SLIM);
1257 }
1258 fprintf (file, "\n");
1259}
1260
1261
1262/* Dump all the immediate uses to FILE. */
1263
1264void
1265dump_immediate_uses (FILE *file)
1266{
1267 tree var;
1268 unsigned int x;
1269
1270 fprintf (file, "Immediate_uses: \n\n");
1271 FOR_EACH_SSA_NAME (x, var, cfun)
1272 {
1273 dump_immediate_uses_for (file, var);
1274 }
1275}
1276
1277
1278/* Dump def-use edges on stderr. */
1279
1280DEBUG_FUNCTION void
1281debug_immediate_uses (void)
1282{
1283 dump_immediate_uses (stderr);
1284}
1285
1286
1287/* Dump def-use edges on stderr. */
1288
1289DEBUG_FUNCTION void
1290debug_immediate_uses_for (tree var)
1291{
1292 dump_immediate_uses_for (stderr, var);
1293}
1294
1295
1296/* Unlink STMTs virtual definition from the IL by propagating its use. */
1297
1298void
1299unlink_stmt_vdef (gimple *stmt)
1300{
1301 use_operand_p use_p;
1302 imm_use_iterator iter;
1303 gimple *use_stmt;
1304 tree vdef = gimple_vdef (stmt);
1305 tree vuse = gimple_vuse (stmt);
1306
1307 if (!vdef
1308 || TREE_CODE (vdef) != SSA_NAME)
1309 return;
1310
1311 FOR_EACH_IMM_USE_STMT (use_stmt, iter, vdef)
1312 {
1313 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
1314 SET_USE (use_p, vuse);
1315 }
1316
1317 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vdef))
1318 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vuse) = 1;
1319}
1320
1321/* Return true if the var whose chain of uses starts at PTR has a
1322 single nondebug use. Set USE_P and STMT to that single nondebug
1323 use, if so, or to NULL otherwise. */
1324bool
1325single_imm_use_1 (const ssa_use_operand_t *head,
1326 use_operand_p *use_p, gimple **stmt)
1327{
1328 ssa_use_operand_t *ptr, *single_use = 0;
1329
1330 for (ptr = head->next; ptr != head; ptr = ptr->next)
1331 if (USE_STMT(ptr) && !is_gimple_debug (USE_STMT (ptr)))
1332 {
1333 if (single_use)
1334 {
1335 single_use = NULL;
1336 break;
1337 }
1338 single_use = ptr;
1339 }
1340
1341 if (use_p)
1342 *use_p = single_use;
1343
1344 if (stmt)
1345 *stmt = single_use ? single_use->loc.stmt : NULL;
1346
1347 return single_use;
1348}
1349
1350