forked from gcc-mirror/gcc
/
tree-ssa-ccp.c
2483 lines (2131 loc) · 70.6 KB
/
tree-ssa-ccp.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
/* Conditional constant propagation pass for the GNU compiler.
Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009,
2010, 2011, 2012 Free Software Foundation, Inc.
Adapted from original RTL SSA-CCP by Daniel Berlin <dberlin@dberlin.org>
Adapted to GIMPLE trees by Diego Novillo <dnovillo@redhat.com>
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the
Free Software Foundation; either version 3, or (at your option) any
later version.
GCC is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
for more details.
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3. If not see
<http://www.gnu.org/licenses/>. */
/* Conditional constant propagation (CCP) is based on the SSA
propagation engine (tree-ssa-propagate.c). Constant assignments of
the form VAR = CST are propagated from the assignments into uses of
VAR, which in turn may generate new constants. The simulation uses
a four level lattice to keep track of constant values associated
with SSA names. Given an SSA name V_i, it may take one of the
following values:
UNINITIALIZED -> the initial state of the value. This value
is replaced with a correct initial value
the first time the value is used, so the
rest of the pass does not need to care about
it. Using this value simplifies initialization
of the pass, and prevents us from needlessly
scanning statements that are never reached.
UNDEFINED -> V_i is a local variable whose definition
has not been processed yet. Therefore we
don't yet know if its value is a constant
or not.
CONSTANT -> V_i has been found to hold a constant
value C.
VARYING -> V_i cannot take a constant value, or if it
does, it is not possible to determine it
at compile time.
The core of SSA-CCP is in ccp_visit_stmt and ccp_visit_phi_node:
1- In ccp_visit_stmt, we are interested in assignments whose RHS
evaluates into a constant and conditional jumps whose predicate
evaluates into a boolean true or false. When an assignment of
the form V_i = CONST is found, V_i's lattice value is set to
CONSTANT and CONST is associated with it. This causes the
propagation engine to add all the SSA edges coming out the
assignment into the worklists, so that statements that use V_i
can be visited.
If the statement is a conditional with a constant predicate, we
mark the outgoing edges as executable or not executable
depending on the predicate's value. This is then used when
visiting PHI nodes to know when a PHI argument can be ignored.
2- In ccp_visit_phi_node, if all the PHI arguments evaluate to the
same constant C, then the LHS of the PHI is set to C. This
evaluation is known as the "meet operation". Since one of the
goals of this evaluation is to optimistically return constant
values as often as possible, it uses two main short cuts:
- If an argument is flowing in through a non-executable edge, it
is ignored. This is useful in cases like this:
if (PRED)
a_9 = 3;
else
a_10 = 100;
a_11 = PHI (a_9, a_10)
If PRED is known to always evaluate to false, then we can
assume that a_11 will always take its value from a_10, meaning
that instead of consider it VARYING (a_9 and a_10 have
different values), we can consider it CONSTANT 100.
- If an argument has an UNDEFINED value, then it does not affect
the outcome of the meet operation. If a variable V_i has an
UNDEFINED value, it means that either its defining statement
hasn't been visited yet or V_i has no defining statement, in
which case the original symbol 'V' is being used
uninitialized. Since 'V' is a local variable, the compiler
may assume any initial value for it.
After propagation, every variable V_i that ends up with a lattice
value of CONSTANT will have the associated constant value in the
array CONST_VAL[i].VALUE. That is fed into substitute_and_fold for
final substitution and folding.
References:
Constant propagation with conditional branches,
Wegman and Zadeck, ACM TOPLAS 13(2):181-210.
Building an Optimizing Compiler,
Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
Advanced Compiler Design and Implementation,
Steven Muchnick, Morgan Kaufmann, 1997, Section 12.6 */
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "tree.h"
#include "flags.h"
#include "tm_p.h"
#include "basic-block.h"
#include "output.h"
#include "function.h"
#include "tree-pretty-print.h"
#include "gimple-pretty-print.h"
#include "timevar.h"
#include "tree-dump.h"
#include "tree-flow.h"
#include "tree-pass.h"
#include "tree-ssa-propagate.h"
#include "value-prof.h"
#include "langhooks.h"
#include "target.h"
#include "diagnostic-core.h"
#include "dbgcnt.h"
#include "gimple-fold.h"
#include "params.h"
/* Possible lattice values. */
typedef enum
{
UNINITIALIZED,
UNDEFINED,
CONSTANT,
VARYING
} ccp_lattice_t;
struct prop_value_d {
/* Lattice value. */
ccp_lattice_t lattice_val;
/* Propagated value. */
tree value;
/* Mask that applies to the propagated value during CCP. For
X with a CONSTANT lattice value X & ~mask == value & ~mask. */
double_int mask;
};
typedef struct prop_value_d prop_value_t;
/* Array of propagated constant values. After propagation,
CONST_VAL[I].VALUE holds the constant value for SSA_NAME(I). If
the constant is held in an SSA name representing a memory store
(i.e., a VDEF), CONST_VAL[I].MEM_REF will contain the actual
memory reference used to store (i.e., the LHS of the assignment
doing the store). */
static prop_value_t *const_val;
static void canonicalize_float_value (prop_value_t *);
static bool ccp_fold_stmt (gimple_stmt_iterator *);
/* Dump constant propagation value VAL to file OUTF prefixed by PREFIX. */
static void
dump_lattice_value (FILE *outf, const char *prefix, prop_value_t val)
{
switch (val.lattice_val)
{
case UNINITIALIZED:
fprintf (outf, "%sUNINITIALIZED", prefix);
break;
case UNDEFINED:
fprintf (outf, "%sUNDEFINED", prefix);
break;
case VARYING:
fprintf (outf, "%sVARYING", prefix);
break;
case CONSTANT:
fprintf (outf, "%sCONSTANT ", prefix);
if (TREE_CODE (val.value) != INTEGER_CST
|| double_int_zero_p (val.mask))
print_generic_expr (outf, val.value, dump_flags);
else
{
double_int cval = double_int_and_not (tree_to_double_int (val.value),
val.mask);
fprintf (outf, "%sCONSTANT " HOST_WIDE_INT_PRINT_DOUBLE_HEX,
prefix, cval.high, cval.low);
fprintf (outf, " (" HOST_WIDE_INT_PRINT_DOUBLE_HEX ")",
val.mask.high, val.mask.low);
}
break;
default:
gcc_unreachable ();
}
}
/* Print lattice value VAL to stderr. */
void debug_lattice_value (prop_value_t val);
DEBUG_FUNCTION void
debug_lattice_value (prop_value_t val)
{
dump_lattice_value (stderr, "", val);
fprintf (stderr, "\n");
}
/* Compute a default value for variable VAR and store it in the
CONST_VAL array. The following rules are used to get default
values:
1- Global and static variables that are declared constant are
considered CONSTANT.
2- Any other value is considered UNDEFINED. This is useful when
considering PHI nodes. PHI arguments that are undefined do not
change the constant value of the PHI node, which allows for more
constants to be propagated.
3- Variables defined by statements other than assignments and PHI
nodes are considered VARYING.
4- Initial values of variables that are not GIMPLE registers are
considered VARYING. */
static prop_value_t
get_default_value (tree var)
{
tree sym = SSA_NAME_VAR (var);
prop_value_t val = { UNINITIALIZED, NULL_TREE, { 0, 0 } };
gimple stmt;
stmt = SSA_NAME_DEF_STMT (var);
if (gimple_nop_p (stmt))
{
/* Variables defined by an empty statement are those used
before being initialized. If VAR is a local variable, we
can assume initially that it is UNDEFINED, otherwise we must
consider it VARYING. */
if (is_gimple_reg (sym)
&& TREE_CODE (sym) == VAR_DECL)
val.lattice_val = UNDEFINED;
else
{
val.lattice_val = VARYING;
val.mask = double_int_minus_one;
}
}
else if (is_gimple_assign (stmt)
/* Value-returning GIMPLE_CALL statements assign to
a variable, and are treated similarly to GIMPLE_ASSIGN. */
|| (is_gimple_call (stmt)
&& gimple_call_lhs (stmt) != NULL_TREE)
|| gimple_code (stmt) == GIMPLE_PHI)
{
tree cst;
if (gimple_assign_single_p (stmt)
&& DECL_P (gimple_assign_rhs1 (stmt))
&& (cst = get_symbol_constant_value (gimple_assign_rhs1 (stmt))))
{
val.lattice_val = CONSTANT;
val.value = cst;
}
else
/* Any other variable defined by an assignment or a PHI node
is considered UNDEFINED. */
val.lattice_val = UNDEFINED;
}
else
{
/* Otherwise, VAR will never take on a constant value. */
val.lattice_val = VARYING;
val.mask = double_int_minus_one;
}
return val;
}
/* Get the constant value associated with variable VAR. */
static inline prop_value_t *
get_value (tree var)
{
prop_value_t *val;
if (const_val == NULL)
return NULL;
val = &const_val[SSA_NAME_VERSION (var)];
if (val->lattice_val == UNINITIALIZED)
*val = get_default_value (var);
canonicalize_float_value (val);
return val;
}
/* Return the constant tree value associated with VAR. */
static inline tree
get_constant_value (tree var)
{
prop_value_t *val;
if (TREE_CODE (var) != SSA_NAME)
{
if (is_gimple_min_invariant (var))
return var;
return NULL_TREE;
}
val = get_value (var);
if (val
&& val->lattice_val == CONSTANT
&& (TREE_CODE (val->value) != INTEGER_CST
|| double_int_zero_p (val->mask)))
return val->value;
return NULL_TREE;
}
/* Sets the value associated with VAR to VARYING. */
static inline void
set_value_varying (tree var)
{
prop_value_t *val = &const_val[SSA_NAME_VERSION (var)];
val->lattice_val = VARYING;
val->value = NULL_TREE;
val->mask = double_int_minus_one;
}
/* For float types, modify the value of VAL to make ccp work correctly
for non-standard values (-0, NaN):
If HONOR_SIGNED_ZEROS is false, and VAL = -0, we canonicalize it to 0.
If HONOR_NANS is false, and VAL is NaN, we canonicalize it to UNDEFINED.
This is to fix the following problem (see PR 29921): Suppose we have
x = 0.0 * y
and we set value of y to NaN. This causes value of x to be set to NaN.
When we later determine that y is in fact VARYING, fold uses the fact
that HONOR_NANS is false, and we try to change the value of x to 0,
causing an ICE. With HONOR_NANS being false, the real appearance of
NaN would cause undefined behavior, though, so claiming that y (and x)
are UNDEFINED initially is correct. */
static void
canonicalize_float_value (prop_value_t *val)
{
enum machine_mode mode;
tree type;
REAL_VALUE_TYPE d;
if (val->lattice_val != CONSTANT
|| TREE_CODE (val->value) != REAL_CST)
return;
d = TREE_REAL_CST (val->value);
type = TREE_TYPE (val->value);
mode = TYPE_MODE (type);
if (!HONOR_SIGNED_ZEROS (mode)
&& REAL_VALUE_MINUS_ZERO (d))
{
val->value = build_real (type, dconst0);
return;
}
if (!HONOR_NANS (mode)
&& REAL_VALUE_ISNAN (d))
{
val->lattice_val = UNDEFINED;
val->value = NULL;
return;
}
}
/* Return whether the lattice transition is valid. */
static bool
valid_lattice_transition (prop_value_t old_val, prop_value_t new_val)
{
/* Lattice transitions must always be monotonically increasing in
value. */
if (old_val.lattice_val < new_val.lattice_val)
return true;
if (old_val.lattice_val != new_val.lattice_val)
return false;
if (!old_val.value && !new_val.value)
return true;
/* Now both lattice values are CONSTANT. */
/* Allow transitioning from &x to &x & ~3. */
if (TREE_CODE (old_val.value) != INTEGER_CST
&& TREE_CODE (new_val.value) == INTEGER_CST)
return true;
/* Bit-lattices have to agree in the still valid bits. */
if (TREE_CODE (old_val.value) == INTEGER_CST
&& TREE_CODE (new_val.value) == INTEGER_CST)
return double_int_equal_p
(double_int_and_not (tree_to_double_int (old_val.value),
new_val.mask),
double_int_and_not (tree_to_double_int (new_val.value),
new_val.mask));
/* Otherwise constant values have to agree. */
return operand_equal_p (old_val.value, new_val.value, 0);
}
/* Set the value for variable VAR to NEW_VAL. Return true if the new
value is different from VAR's previous value. */
static bool
set_lattice_value (tree var, prop_value_t new_val)
{
/* We can deal with old UNINITIALIZED values just fine here. */
prop_value_t *old_val = &const_val[SSA_NAME_VERSION (var)];
canonicalize_float_value (&new_val);
/* We have to be careful to not go up the bitwise lattice
represented by the mask.
??? This doesn't seem to be the best place to enforce this. */
if (new_val.lattice_val == CONSTANT
&& old_val->lattice_val == CONSTANT
&& TREE_CODE (new_val.value) == INTEGER_CST
&& TREE_CODE (old_val->value) == INTEGER_CST)
{
double_int diff;
diff = double_int_xor (tree_to_double_int (new_val.value),
tree_to_double_int (old_val->value));
new_val.mask = double_int_ior (new_val.mask,
double_int_ior (old_val->mask, diff));
}
gcc_assert (valid_lattice_transition (*old_val, new_val));
/* If *OLD_VAL and NEW_VAL are the same, return false to inform the
caller that this was a non-transition. */
if (old_val->lattice_val != new_val.lattice_val
|| (new_val.lattice_val == CONSTANT
&& TREE_CODE (new_val.value) == INTEGER_CST
&& (TREE_CODE (old_val->value) != INTEGER_CST
|| !double_int_equal_p (new_val.mask, old_val->mask))))
{
/* ??? We would like to delay creation of INTEGER_CSTs from
partially constants here. */
if (dump_file && (dump_flags & TDF_DETAILS))
{
dump_lattice_value (dump_file, "Lattice value changed to ", new_val);
fprintf (dump_file, ". Adding SSA edges to worklist.\n");
}
*old_val = new_val;
gcc_assert (new_val.lattice_val != UNINITIALIZED);
return true;
}
return false;
}
static prop_value_t get_value_for_expr (tree, bool);
static prop_value_t bit_value_binop (enum tree_code, tree, tree, tree);
static void bit_value_binop_1 (enum tree_code, tree, double_int *, double_int *,
tree, double_int, double_int,
tree, double_int, double_int);
/* Return a double_int that can be used for bitwise simplifications
from VAL. */
static double_int
value_to_double_int (prop_value_t val)
{
if (val.value
&& TREE_CODE (val.value) == INTEGER_CST)
return tree_to_double_int (val.value);
else
return double_int_zero;
}
/* Return the value for the address expression EXPR based on alignment
information. */
static prop_value_t
get_value_from_alignment (tree expr)
{
tree type = TREE_TYPE (expr);
prop_value_t val;
unsigned HOST_WIDE_INT bitpos;
unsigned int align;
gcc_assert (TREE_CODE (expr) == ADDR_EXPR);
align = get_object_alignment_1 (TREE_OPERAND (expr, 0), &bitpos);
val.mask
= double_int_and_not (POINTER_TYPE_P (type) || TYPE_UNSIGNED (type)
? double_int_mask (TYPE_PRECISION (type))
: double_int_minus_one,
uhwi_to_double_int (align / BITS_PER_UNIT - 1));
val.lattice_val = double_int_minus_one_p (val.mask) ? VARYING : CONSTANT;
if (val.lattice_val == CONSTANT)
val.value
= double_int_to_tree (type, uhwi_to_double_int (bitpos / BITS_PER_UNIT));
else
val.value = NULL_TREE;
return val;
}
/* Return the value for the tree operand EXPR. If FOR_BITS_P is true
return constant bits extracted from alignment information for
invariant addresses. */
static prop_value_t
get_value_for_expr (tree expr, bool for_bits_p)
{
prop_value_t val;
if (TREE_CODE (expr) == SSA_NAME)
{
val = *get_value (expr);
if (for_bits_p
&& val.lattice_val == CONSTANT
&& TREE_CODE (val.value) == ADDR_EXPR)
val = get_value_from_alignment (val.value);
}
else if (is_gimple_min_invariant (expr)
&& (!for_bits_p || TREE_CODE (expr) != ADDR_EXPR))
{
val.lattice_val = CONSTANT;
val.value = expr;
val.mask = double_int_zero;
canonicalize_float_value (&val);
}
else if (TREE_CODE (expr) == ADDR_EXPR)
val = get_value_from_alignment (expr);
else
{
val.lattice_val = VARYING;
val.mask = double_int_minus_one;
val.value = NULL_TREE;
}
return val;
}
/* Return the likely CCP lattice value for STMT.
If STMT has no operands, then return CONSTANT.
Else if undefinedness of operands of STMT cause its value to be
undefined, then return UNDEFINED.
Else if any operands of STMT are constants, then return CONSTANT.
Else return VARYING. */
static ccp_lattice_t
likely_value (gimple stmt)
{
bool has_constant_operand, has_undefined_operand, all_undefined_operands;
tree use;
ssa_op_iter iter;
unsigned i;
enum gimple_code code = gimple_code (stmt);
/* This function appears to be called only for assignments, calls,
conditionals, and switches, due to the logic in visit_stmt. */
gcc_assert (code == GIMPLE_ASSIGN
|| code == GIMPLE_CALL
|| code == GIMPLE_COND
|| code == GIMPLE_SWITCH);
/* If the statement has volatile operands, it won't fold to a
constant value. */
if (gimple_has_volatile_ops (stmt))
return VARYING;
/* Arrive here for more complex cases. */
has_constant_operand = false;
has_undefined_operand = false;
all_undefined_operands = true;
FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
{
prop_value_t *val = get_value (use);
if (val->lattice_val == UNDEFINED)
has_undefined_operand = true;
else
all_undefined_operands = false;
if (val->lattice_val == CONSTANT)
has_constant_operand = true;
}
/* There may be constants in regular rhs operands. For calls we
have to ignore lhs, fndecl and static chain, otherwise only
the lhs. */
for (i = (is_gimple_call (stmt) ? 2 : 0) + gimple_has_lhs (stmt);
i < gimple_num_ops (stmt); ++i)
{
tree op = gimple_op (stmt, i);
if (!op || TREE_CODE (op) == SSA_NAME)
continue;
if (is_gimple_min_invariant (op))
has_constant_operand = true;
}
if (has_constant_operand)
all_undefined_operands = false;
/* If the operation combines operands like COMPLEX_EXPR make sure to
not mark the result UNDEFINED if only one part of the result is
undefined. */
if (has_undefined_operand && all_undefined_operands)
return UNDEFINED;
else if (code == GIMPLE_ASSIGN && has_undefined_operand)
{
switch (gimple_assign_rhs_code (stmt))
{
/* Unary operators are handled with all_undefined_operands. */
case PLUS_EXPR:
case MINUS_EXPR:
case POINTER_PLUS_EXPR:
/* Not MIN_EXPR, MAX_EXPR. One VARYING operand may be selected.
Not bitwise operators, one VARYING operand may specify the
result completely. Not logical operators for the same reason.
Not COMPLEX_EXPR as one VARYING operand makes the result partly
not UNDEFINED. Not *DIV_EXPR, comparisons and shifts because
the undefined operand may be promoted. */
return UNDEFINED;
default:
;
}
}
/* If there was an UNDEFINED operand but the result may be not UNDEFINED
fall back to CONSTANT. During iteration UNDEFINED may still drop
to CONSTANT. */
if (has_undefined_operand)
return CONSTANT;
/* We do not consider virtual operands here -- load from read-only
memory may have only VARYING virtual operands, but still be
constant. */
if (has_constant_operand
|| gimple_references_memory_p (stmt))
return CONSTANT;
return VARYING;
}
/* Returns true if STMT cannot be constant. */
static bool
surely_varying_stmt_p (gimple stmt)
{
/* If the statement has operands that we cannot handle, it cannot be
constant. */
if (gimple_has_volatile_ops (stmt))
return true;
/* If it is a call and does not return a value or is not a
builtin and not an indirect call, it is varying. */
if (is_gimple_call (stmt))
{
tree fndecl;
if (!gimple_call_lhs (stmt)
|| ((fndecl = gimple_call_fndecl (stmt)) != NULL_TREE
&& !DECL_BUILT_IN (fndecl)))
return true;
}
/* Any other store operation is not interesting. */
else if (gimple_vdef (stmt))
return true;
/* Anything other than assignments and conditional jumps are not
interesting for CCP. */
if (gimple_code (stmt) != GIMPLE_ASSIGN
&& gimple_code (stmt) != GIMPLE_COND
&& gimple_code (stmt) != GIMPLE_SWITCH
&& gimple_code (stmt) != GIMPLE_CALL)
return true;
return false;
}
/* Initialize local data structures for CCP. */
static void
ccp_initialize (void)
{
basic_block bb;
const_val = XCNEWVEC (prop_value_t, num_ssa_names);
/* Initialize simulation flags for PHI nodes and statements. */
FOR_EACH_BB (bb)
{
gimple_stmt_iterator i;
for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i))
{
gimple stmt = gsi_stmt (i);
bool is_varying;
/* If the statement is a control insn, then we do not
want to avoid simulating the statement once. Failure
to do so means that those edges will never get added. */
if (stmt_ends_bb_p (stmt))
is_varying = false;
else
is_varying = surely_varying_stmt_p (stmt);
if (is_varying)
{
tree def;
ssa_op_iter iter;
/* If the statement will not produce a constant, mark
all its outputs VARYING. */
FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
set_value_varying (def);
}
prop_set_simulate_again (stmt, !is_varying);
}
}
/* Now process PHI nodes. We never clear the simulate_again flag on
phi nodes, since we do not know which edges are executable yet,
except for phi nodes for virtual operands when we do not do store ccp. */
FOR_EACH_BB (bb)
{
gimple_stmt_iterator i;
for (i = gsi_start_phis (bb); !gsi_end_p (i); gsi_next (&i))
{
gimple phi = gsi_stmt (i);
if (!is_gimple_reg (gimple_phi_result (phi)))
prop_set_simulate_again (phi, false);
else
prop_set_simulate_again (phi, true);
}
}
}
/* Debug count support. Reset the values of ssa names
VARYING when the total number ssa names analyzed is
beyond the debug count specified. */
static void
do_dbg_cnt (void)
{
unsigned i;
for (i = 0; i < num_ssa_names; i++)
{
if (!dbg_cnt (ccp))
{
const_val[i].lattice_val = VARYING;
const_val[i].mask = double_int_minus_one;
const_val[i].value = NULL_TREE;
}
}
}
/* Do final substitution of propagated values, cleanup the flowgraph and
free allocated storage.
Return TRUE when something was optimized. */
static bool
ccp_finalize (void)
{
bool something_changed;
unsigned i;
do_dbg_cnt ();
/* Derive alignment and misalignment information from partially
constant pointers in the lattice. */
for (i = 1; i < num_ssa_names; ++i)
{
tree name = ssa_name (i);
prop_value_t *val;
struct ptr_info_def *pi;
unsigned int tem, align;
if (!name
|| !POINTER_TYPE_P (TREE_TYPE (name)))
continue;
val = get_value (name);
if (val->lattice_val != CONSTANT
|| TREE_CODE (val->value) != INTEGER_CST)
continue;
/* Trailing constant bits specify the alignment, trailing value
bits the misalignment. */
tem = val->mask.low;
align = (tem & -tem);
if (align == 1)
continue;
pi = get_ptr_info (name);
pi->align = align;
pi->misalign = TREE_INT_CST_LOW (val->value) & (align - 1);
}
/* Perform substitutions based on the known constant values. */
something_changed = substitute_and_fold (get_constant_value,
ccp_fold_stmt, true);
free (const_val);
const_val = NULL;
return something_changed;;
}
/* Compute the meet operator between *VAL1 and *VAL2. Store the result
in VAL1.
any M UNDEFINED = any
any M VARYING = VARYING
Ci M Cj = Ci if (i == j)
Ci M Cj = VARYING if (i != j)
*/
static void
ccp_lattice_meet (prop_value_t *val1, prop_value_t *val2)
{
if (val1->lattice_val == UNDEFINED)
{
/* UNDEFINED M any = any */
*val1 = *val2;
}
else if (val2->lattice_val == UNDEFINED)
{
/* any M UNDEFINED = any
Nothing to do. VAL1 already contains the value we want. */
;
}
else if (val1->lattice_val == VARYING
|| val2->lattice_val == VARYING)
{
/* any M VARYING = VARYING. */
val1->lattice_val = VARYING;
val1->mask = double_int_minus_one;
val1->value = NULL_TREE;
}
else if (val1->lattice_val == CONSTANT
&& val2->lattice_val == CONSTANT
&& TREE_CODE (val1->value) == INTEGER_CST
&& TREE_CODE (val2->value) == INTEGER_CST)
{
/* Ci M Cj = Ci if (i == j)
Ci M Cj = VARYING if (i != j)
For INTEGER_CSTs mask unequal bits. If no equal bits remain,
drop to varying. */
val1->mask
= double_int_ior (double_int_ior (val1->mask,
val2->mask),
double_int_xor (tree_to_double_int (val1->value),
tree_to_double_int (val2->value)));
if (double_int_minus_one_p (val1->mask))
{
val1->lattice_val = VARYING;
val1->value = NULL_TREE;
}
}
else if (val1->lattice_val == CONSTANT
&& val2->lattice_val == CONSTANT
&& simple_cst_equal (val1->value, val2->value) == 1)
{
/* Ci M Cj = Ci if (i == j)
Ci M Cj = VARYING if (i != j)
VAL1 already contains the value we want for equivalent values. */
}
else if (val1->lattice_val == CONSTANT
&& val2->lattice_val == CONSTANT
&& (TREE_CODE (val1->value) == ADDR_EXPR
|| TREE_CODE (val2->value) == ADDR_EXPR))
{
/* When not equal addresses are involved try meeting for
alignment. */
prop_value_t tem = *val2;
if (TREE_CODE (val1->value) == ADDR_EXPR)
*val1 = get_value_for_expr (val1->value, true);
if (TREE_CODE (val2->value) == ADDR_EXPR)
tem = get_value_for_expr (val2->value, true);
ccp_lattice_meet (val1, &tem);
}
else
{
/* Any other combination is VARYING. */
val1->lattice_val = VARYING;
val1->mask = double_int_minus_one;
val1->value = NULL_TREE;
}
}
/* Loop through the PHI_NODE's parameters for BLOCK and compare their
lattice values to determine PHI_NODE's lattice value. The value of a
PHI node is determined calling ccp_lattice_meet with all the arguments
of the PHI node that are incoming via executable edges. */
static enum ssa_prop_result
ccp_visit_phi_node (gimple phi)
{
unsigned i;
prop_value_t *old_val, new_val;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\nVisiting PHI node: ");
print_gimple_stmt (dump_file, phi, 0, dump_flags);
}
old_val = get_value (gimple_phi_result (phi));
switch (old_val->lattice_val)
{
case VARYING:
return SSA_PROP_VARYING;
case CONSTANT:
new_val = *old_val;
break;
case UNDEFINED:
new_val.lattice_val = UNDEFINED;
new_val.value = NULL_TREE;
break;
default:
gcc_unreachable ();
}
for (i = 0; i < gimple_phi_num_args (phi); i++)
{
/* Compute the meet operator over all the PHI arguments flowing
through executable edges. */
edge e = gimple_phi_arg_edge (phi, i);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file,
"\n Argument #%d (%d -> %d %sexecutable)\n",
i, e->src->index, e->dest->index,
(e->flags & EDGE_EXECUTABLE) ? "" : "not ");
}
/* If the incoming edge is executable, Compute the meet operator for
the existing value of the PHI node and the current PHI argument. */
if (e->flags & EDGE_EXECUTABLE)
{
tree arg = gimple_phi_arg (phi, i)->def;
prop_value_t arg_val = get_value_for_expr (arg, false);
ccp_lattice_meet (&new_val, &arg_val);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\t");
print_generic_expr (dump_file, arg, dump_flags);
dump_lattice_value (dump_file, "\tValue: ", arg_val);
fprintf (dump_file, "\n");
}
if (new_val.lattice_val == VARYING)
break;
}
}