aboutsummaryrefslogtreecommitdiff
path: root/gcc/ada/exp_dbug.adb
blob: c2e774140ff5878cf164f112522a01ee1498b89c (plain)
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
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
------------------------------------------------------------------------------
--                                                                          --
--                         GNAT COMPILER COMPONENTS                         --
--                                                                          --
--                             E X P _ D B U G                              --
--                                                                          --
--                                 B o d y                                  --
--                                                                          --
--          Copyright (C) 1996-2020, Free Software Foundation, Inc.         --
--                                                                          --
-- GNAT is free software;  you can  redistribute it  and/or modify it under --
-- terms of the  GNU General Public License as published  by the Free Soft- --
-- ware  Foundation;  either version 3,  or (at your option) any later ver- --
-- sion.  GNAT is distributed in the hope that it will be useful, but WITH- --
-- OUT 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  distributed with GNAT; see file COPYING3.  If not, go to --
-- http://www.gnu.org/licenses for a complete copy of the license.          --
--                                                                          --
-- GNAT was originally developed  by the GNAT team at  New York University. --
-- Extensive contributions were provided by Ada Core Technologies Inc.      --
--                                                                          --
------------------------------------------------------------------------------

with Alloc;
with Atree;    use Atree;
with Debug;    use Debug;
with Einfo;    use Einfo;
with Exp_Util; use Exp_Util;
with Nlists;   use Nlists;
with Nmake;    use Nmake;
with Opt;      use Opt;
with Output;   use Output;
with Sem_Aux;  use Sem_Aux;
with Sem_Eval; use Sem_Eval;
with Sem_Util; use Sem_Util;
with Sinfo;    use Sinfo;
with Stand;    use Stand;
with Stringt;  use Stringt;
with Table;
with Tbuild;   use Tbuild;
with Urealp;   use Urealp;

package body Exp_Dbug is

   --  The following table is used to queue up the entities passed as
   --  arguments to Qualify_Entity_Names for later processing when
   --  Qualify_All_Entity_Names is called.

   package Name_Qualify_Units is new Table.Table (
     Table_Component_Type => Node_Id,
     Table_Index_Type     => Nat,
     Table_Low_Bound      => 1,
     Table_Initial        => Alloc.Name_Qualify_Units_Initial,
     Table_Increment      => Alloc.Name_Qualify_Units_Increment,
     Table_Name           => "Name_Qualify_Units");

   --------------------------------
   -- Use of Qualification Flags --
   --------------------------------

   --  There are two flags used to keep track of qualification of entities

   --    Has_Fully_Qualified_Name
   --    Has_Qualified_Name

   --  The difference between these is as follows. Has_Qualified_Name is
   --  set to indicate that the name has been qualified as required by the
   --  spec of this package. As described there, this may involve the full
   --  qualification for the name, but for some entities, notably procedure
   --  local variables, this full qualification is not required.

   --  The flag Has_Fully_Qualified_Name is set if indeed the name has been
   --  fully qualified in the Ada sense. If Has_Fully_Qualified_Name is set,
   --  then Has_Qualified_Name is also set, but the other way round is not
   --  the case.

   --  Consider the following example:

   --     with ...
   --     procedure X is
   --       B : Ddd.Ttt;
   --       procedure Y is ..

   --  Here B is a procedure local variable, so it does not need fully
   --  qualification. The flag Has_Qualified_Name will be set on the
   --  first attempt to qualify B, to indicate that the job is done
   --  and need not be redone.

   --  But Y is qualified as x__y, since procedures are always fully
   --  qualified, so the first time that an attempt is made to qualify
   --  the name y, it will be replaced by x__y, and both flags are set.

   --  Why the two flags? Well there are cases where we derive type names
   --  from object names. As noted in the spec, type names are always
   --  fully qualified. Suppose for example that the backend has to build
   --  a padded type for variable B. then it will construct the PAD name
   --  from B, but it requires full qualification, so the fully qualified
   --  type name will be x__b___PAD. The two flags allow the circuit for
   --  building this name to realize efficiently that b needs further
   --  qualification.

   --------------------
   -- Homonym_Suffix --
   --------------------

   --  The string defined here (and its associated length) is used to gather
   --  the homonym string that will be appended to Name_Buffer when the name
   --  is complete. Strip_Suffixes appends to this string as does
   --  Append_Homonym_Number, and Output_Homonym_Numbers_Suffix appends the
   --  string to the end of Name_Buffer.

   Homonym_Numbers : String (1 .. 256);
   Homonym_Len     : Natural := 0;

   ----------------------
   -- Local Procedures --
   ----------------------

   procedure Add_Uint_To_Buffer (U : Uint);
   --  Add image of universal integer to Name_Buffer, updating Name_Len

   procedure Add_Real_To_Buffer (U : Ureal);
   --  Add nnn_ddd to Name_Buffer, where nnn and ddd are integer values of
   --  the normalized numerator and denominator of the given real value.

   procedure Append_Homonym_Number (E : Entity_Id);
   --  If the entity E has homonyms in the same scope, then make an entry
   --  in the Homonym_Numbers array, bumping Homonym_Count accordingly.

   function Bounds_Match_Size (E : Entity_Id) return  Boolean;
   --  Determine whether the bounds of E match the size of the type. This is
   --  used to determine whether encoding is required for a discrete type.

   function Is_Handled_Scale_Factor (U : Ureal) return Boolean;
   --  The argument U is the Small_Value of a fixed-point type. This function
   --  determines whether the back-end can handle this scale factor. When it
   --  cannot, we have to output a GNAT encoding for the corresponding type.

   procedure Output_Homonym_Numbers_Suffix;
   --  If homonym numbers are stored, then output them into Name_Buffer

   procedure Prepend_String_To_Buffer (S : String);
   --  Prepend given string to the contents of the string buffer, updating
   --  the value in Name_Len (i.e. string is added at start of buffer).

   procedure Prepend_Uint_To_Buffer (U : Uint);
   --  Prepend image of universal integer to Name_Buffer, updating Name_Len

   procedure Qualify_Entity_Name (Ent : Entity_Id);
   --  If not already done, replaces the Chars field of the given entity
   --  with the appropriate fully qualified name.

   procedure Reset_Buffers;
   --  Reset the contents of Name_Buffer and Homonym_Numbers by setting their
   --  respective lengths to zero.

   procedure Strip_Suffixes (BNPE_Suffix_Found : in out Boolean);
   --  Given an qualified entity name in Name_Buffer, remove any plain X or
   --  X{nb} qualification suffix. The contents of Name_Buffer is not changed
   --  but Name_Len may be adjusted on return to remove the suffix. If a
   --  BNPE suffix is found and stripped, then BNPE_Suffix_Found is set to
   --  True. If no suffix is found, then BNPE_Suffix_Found is not modified.
   --  This routine also searches for a homonym suffix, and if one is found
   --  it is also stripped, and the entries are added to the global homonym
   --  list (Homonym_Numbers) so that they can later be put back.

   ------------------------
   -- Add_Real_To_Buffer --
   ------------------------

   procedure Add_Real_To_Buffer (U : Ureal) is
   begin
      Add_Uint_To_Buffer (Norm_Num (U));
      Add_Str_To_Name_Buffer ("_");
      Add_Uint_To_Buffer (Norm_Den (U));
   end Add_Real_To_Buffer;

   ------------------------
   -- Add_Uint_To_Buffer --
   ------------------------

   procedure Add_Uint_To_Buffer (U : Uint) is
   begin
      if U < 0 then
         Add_Uint_To_Buffer (-U);
         Add_Char_To_Name_Buffer ('m');
      else
         UI_Image (U, Decimal);
         Add_Str_To_Name_Buffer (UI_Image_Buffer (1 .. UI_Image_Length));
      end if;
   end Add_Uint_To_Buffer;

   ---------------------------
   -- Append_Homonym_Number --
   ---------------------------

   procedure Append_Homonym_Number (E : Entity_Id) is

      procedure Add_Nat_To_H (Nr : Nat);
      --  Little procedure to append Nr to Homonym_Numbers

      ------------------
      -- Add_Nat_To_H --
      ------------------

      procedure Add_Nat_To_H (Nr : Nat) is
      begin
         if Nr >= 10 then
            Add_Nat_To_H (Nr / 10);
         end if;

         Homonym_Len := Homonym_Len + 1;
         Homonym_Numbers (Homonym_Len) :=
           Character'Val (Nr mod 10 + Character'Pos ('0'));
      end Add_Nat_To_H;

   --  Start of processing for Append_Homonym_Number

   begin
      if Has_Homonym (E) then
         if Homonym_Len > 0 then
            Homonym_Len := Homonym_Len + 1;
            Homonym_Numbers (Homonym_Len) := '_';
         end if;

         Add_Nat_To_H (Homonym_Number (E));
      end if;
   end Append_Homonym_Number;

   -----------------------
   -- Bounds_Match_Size --
   -----------------------

   function Bounds_Match_Size (E : Entity_Id) return Boolean is
      Siz : Uint;

   begin
      if not Is_OK_Static_Subtype (E) then
         return False;

      elsif Is_Integer_Type (E)
        and then Subtypes_Statically_Match (E, Base_Type (E))
      then
         return True;

      --  Here we check if the static bounds match the natural size, which is
      --  the size passed through with the debugging information. This is the
      --  Esize rounded up to 8, 16, 32, 64 or 128 as appropriate.

      else
         declare
            Umark  : constant Uintp.Save_Mark := Uintp.Mark;
            Result : Boolean;

         begin
            if Esize (E) <= 8 then
               Siz := Uint_8;
            elsif Esize (E) <= 16 then
               Siz := Uint_16;
            elsif Esize (E) <= 32 then
               Siz := Uint_32;
            elsif Esize (E) <= 64 then
               Siz := Uint_64;
            else
               Siz := Uint_128;
            end if;

            if Is_Modular_Integer_Type (E) or else Is_Enumeration_Type (E) then
               Result :=
                 Expr_Rep_Value (Type_Low_Bound (E)) = 0
                   and then
                 2 ** Siz - Expr_Rep_Value (Type_High_Bound (E)) = 1;

            else
               Result :=
                 Expr_Rep_Value (Type_Low_Bound (E)) + 2 ** (Siz - 1) = 0
                   and then
                 2 ** (Siz - 1) - Expr_Rep_Value (Type_High_Bound (E)) = 1;
            end if;

            Release (Umark);
            return Result;
         end;
      end if;
   end Bounds_Match_Size;

   --------------------------------
   -- Debug_Renaming_Declaration --
   --------------------------------

   function Debug_Renaming_Declaration (N : Node_Id) return Node_Id is
      Loc : constant Source_Ptr := Sloc (N);
      Ent : constant Node_Id    := Defining_Entity (N);
      Nam : constant Node_Id    := Name (N);
      Ren : Node_Id;
      Typ : Entity_Id;
      Obj : Entity_Id;
      Res : Node_Id;

      Enable : Boolean := Nkind (N) = N_Package_Renaming_Declaration;
      --  By default, we do not generate an encoding for renaming. This is
      --  however done (in which case this is set to True) in a few cases:
      --    - when a package is renamed,
      --    - when the renaming involves a packed array,
      --    - when the renaming involves a packed record.

      Last_Is_Indexed_Comp : Boolean := False;
      --  Whether the last subscript value was an indexed component access (XS)

      procedure Enable_If_Packed_Array (N : Node_Id);
      --  Enable encoding generation if N is a packed array

      function Output_Subscript (N : Node_Id; S : String) return Boolean;
      --  Outputs a single subscript value as ?nnn (subscript is compile time
      --  known value with value nnn) or as ?e (subscript is local constant
      --  with name e), where S supplies the proper string to use for ?.
      --  Returns False if the subscript is not of an appropriate type to
      --  output in one of these two forms. The result is prepended to the
      --  name stored in Name_Buffer.

      function Scope_Contains (Sc : Node_Id; Ent : Entity_Id) return Boolean;
      --  Return whether Ent belong to the Sc scope

      ----------------------------
      -- Enable_If_Packed_Array --
      ----------------------------

      procedure Enable_If_Packed_Array (N : Node_Id) is
         T : constant Entity_Id := Underlying_Type (Etype (N));

      begin
         Enable :=
           Enable
             or else
               (Ekind (T) in Array_Kind
                 and then Present (Packed_Array_Impl_Type (T)));
      end Enable_If_Packed_Array;

      ----------------------
      -- Output_Subscript --
      ----------------------

      function Output_Subscript (N : Node_Id; S : String) return Boolean is
      begin
         if Compile_Time_Known_Value (N) then
            Prepend_Uint_To_Buffer (Expr_Value (N));

         elsif Nkind (N) = N_Identifier
           and then Scope_Contains (Scope (Entity (N)), Ent)
           and then (Ekind (Entity (N)) = E_Constant
                      or else Ekind (Entity (N)) = E_In_Parameter)
         then
            Prepend_String_To_Buffer (Get_Name_String (Chars (Entity (N))));

         else
            return False;
         end if;

         Prepend_String_To_Buffer (S);
         return True;
      end Output_Subscript;

      --------------------
      -- Scope_Contains --
      --------------------

      function Scope_Contains (Sc : Node_Id; Ent : Entity_Id) return Boolean is
         Cur : Node_Id := Scope (Ent);

      begin
         while Present (Cur) loop
            if Cur = Sc then
               return True;
            end if;

            Cur := Scope (Cur);
         end loop;

         return False;
      end Scope_Contains;

   --  Start of processing for Debug_Renaming_Declaration

   begin
      if not Comes_From_Source (N) and then not Needs_Debug_Info (Ent) then
         return Empty;
      end if;

      --  Get renamed entity and compute suffix

      Name_Len := 0;
      Ren := Nam;
      loop
         --  The expression that designates the renamed object is sometimes
         --  expanded into bit-wise operations. We want to work instead on
         --  array/record components accesses, so try to analyze the unexpanded
         --  forms.

         Ren := Original_Node (Ren);

         case Nkind (Ren) is
            when N_Expanded_Name
               | N_Identifier
            =>
               if not Present (Renamed_Object (Entity (Ren))) then
                  exit;
               end if;

               --  This is a renaming of a renaming: traverse until the final
               --  renaming to see if anything is packed along the way.

               Ren := Renamed_Object (Entity (Ren));

            when N_Selected_Component =>
               declare
                  Sel_Id    : constant Entity_Id :=
                                Entity (Selector_Name (Ren));
                  First_Bit : Uint;

               begin
                  --  If the renaming involves a call to a primitive function,
                  --  we are out of the scope of renaming encodings. We will
                  --  very likely create a variable to hold the renamed value
                  --  anyway, so the renaming entity will be available in
                  --  debuggers.

                  exit when Ekind (Sel_Id) not in E_Component | E_Discriminant;

                  First_Bit := Normalized_First_Bit (Sel_Id);
                  Enable :=
                    Enable
                      or else Is_Packed
                                (Underlying_Type (Etype (Prefix (Ren))))
                      or else (First_Bit /= No_Uint
                                and then First_Bit /= Uint_0);
               end;

               Prepend_String_To_Buffer
                 (Get_Name_String (Chars (Selector_Name (Ren))));
               Prepend_String_To_Buffer ("XR");
               Ren := Prefix (Ren);
               Last_Is_Indexed_Comp := False;

            when N_Indexed_Component =>
               declare
                  X : Node_Id;

               begin
                  Enable_If_Packed_Array (Prefix (Ren));

                  X := Last (Expressions (Ren));
                  while Present (X) loop
                     if not Output_Subscript (X, "XS") then
                        Set_Materialize_Entity (Ent);
                        return Empty;
                     end if;

                     Prev (X);
                     Last_Is_Indexed_Comp := True;
                  end loop;
               end;

               Ren := Prefix (Ren);

            when N_Slice =>

               --  Assuming X is an array:
               --      X (Y1 .. Y2) (Y3)

               --  is equivalent to:
               --      X (Y3)

               --  GDB cannot handle packed array slices, so avoid describing
               --  the slice if we can avoid it.

               if not Last_Is_Indexed_Comp then
                  Enable_If_Packed_Array (Prefix (Ren));
                  Typ := Etype (First_Index (Etype (Ren)));

                  if not Output_Subscript (Type_High_Bound (Typ), "XS") then
                     Set_Materialize_Entity (Ent);
                     return Empty;
                  end if;

                  if not Output_Subscript (Type_Low_Bound  (Typ), "XL") then
                     Set_Materialize_Entity (Ent);
                     return Empty;
                  end if;

                  Last_Is_Indexed_Comp := False;
               end if;

               Ren := Prefix (Ren);

            when N_Explicit_Dereference =>
               Prepend_String_To_Buffer ("XA");
               Ren := Prefix (Ren);
               Last_Is_Indexed_Comp := False;

            --  For now, anything else simply results in no translation

            when others =>
               Set_Materialize_Entity (Ent);
               return Empty;
         end case;
      end loop;

      --  If we found no reason here to emit an encoding, stop now

      if not Enable then
         Set_Materialize_Entity (Ent);
         return Empty;
      end if;

      Prepend_String_To_Buffer ("___XE");

      --  Include the designation of the form of renaming

      case Nkind (N) is
         when N_Object_Renaming_Declaration =>
            Prepend_String_To_Buffer ("___XR");

         when N_Exception_Renaming_Declaration =>
            Prepend_String_To_Buffer ("___XRE");

         when N_Package_Renaming_Declaration =>
            Prepend_String_To_Buffer ("___XRP");

         when others =>
            return Empty;
      end case;

      --  Add the name of the renaming entity to the front

      Prepend_String_To_Buffer (Get_Name_String (Chars (Ent)));

      --  If it is a child unit create a fully qualified name, to disambiguate
      --  multiple child units with the same name and different parents.

      if Nkind (N) = N_Package_Renaming_Declaration
        and then Is_Child_Unit (Ent)
      then
         Prepend_String_To_Buffer ("__");
         Prepend_String_To_Buffer
           (Get_Name_String (Chars (Scope (Ent))));
      end if;

      --  Create the special object whose name is the debug encoding for the
      --  renaming declaration.

      --  For now, the object name contains the suffix encoding for the renamed
      --  object, but not the name of the leading entity. The object is linked
      --  the renamed entity using the Debug_Renaming_Link field. Then the
      --  Qualify_Entity_Name procedure uses this link to create the proper
      --  fully qualified name.

      --  The reason we do things this way is that we really need to copy the
      --  qualification of the renamed entity, and it is really much easier to
      --  do this after the renamed entity has itself been fully qualified.

      Obj := Make_Defining_Identifier (Loc, Chars => Name_Enter);
      Res :=
        Make_Object_Declaration (Loc,
          Defining_Identifier => Obj,
          Object_Definition   => New_Occurrence_Of
                                   (Standard_Debug_Renaming_Type, Loc));

      Set_Debug_Renaming_Link (Obj, Entity (Ren));

      Set_Debug_Info_Needed (Obj);

      --  The renamed entity may be a temporary, e.g. the result of an
      --  implicit dereference in an iterator. Indicate that the temporary
      --  itself requires debug information. If the renamed entity comes
      --  from source this is a no-op.

      Set_Debug_Info_Needed (Entity (Ren));

      --  Mark the object as internal so that it won't be initialized when
      --  pragma Initialize_Scalars or Normalize_Scalars is in use.

      Set_Is_Internal (Obj);

      return Res;

   --  If we get an exception, just figure it is a case that we cannot
   --  successfully handle using our current approach, since this is
   --  only for debugging, no need to take the compilation with us.

   exception
      when others =>
         return Make_Null_Statement (Loc);
   end Debug_Renaming_Declaration;

   -----------------------------
   -- Is_Handled_Scale_Factor --
   -----------------------------

   function Is_Handled_Scale_Factor (U : Ureal) return Boolean is
   begin
      --  Keep in sync with gigi (see E_*_Fixed_Point_Type handling in
      --  decl.c:gnat_to_gnu_entity).

      if UI_Eq (Numerator (U), Uint_1) then
         if Rbase (U) = 2 or else Rbase (U) = 10 then
            return True;
         end if;
      end if;

      return
        (UI_Is_In_Int_Range (Norm_Num (U))
           and then
         UI_Is_In_Int_Range (Norm_Den (U)));
   end Is_Handled_Scale_Factor;

   ----------------------
   -- Get_Encoded_Name --
   ----------------------

   --  Note: see spec for details on encodings

   procedure Get_Encoded_Name (E : Entity_Id) is
      Has_Suffix : Boolean;

   begin
      --  If not generating code, there is no need to create encoded names, and
      --  problems when the back-end is called to annotate types without full
      --  code generation. See comments in Get_External_Name for additional
      --  details.

      --  However we do create encoded names if the back end is active, even
      --  if Operating_Mode got reset. Otherwise any serious error reported
      --  by the backend calling Error_Msg changes the Compilation_Mode to
      --  Check_Semantics, which disables the functionality of this routine,
      --  causing the generation of spurious additional errors.

      --  Couldn't we just test Original_Operating_Mode here? ???

      if Operating_Mode /= Generate_Code and then not Generating_Code then
         return;
      end if;

      Get_Name_String (Chars (E));

      --  Nothing to do if we do not have a type

      if not Is_Type (E)

      --  Or if this is an enumeration base type

        or else (Is_Enumeration_Type (E) and then Is_Base_Type (E))

      --  Or if this is a dummy type for a renaming

        or else (Name_Len >= 3 and then
                   Name_Buffer (Name_Len - 2 .. Name_Len) = "_XR")

        or else (Name_Len >= 4 and then
                   (Name_Buffer (Name_Len - 3 .. Name_Len) = "_XRE"
                      or else
                    Name_Buffer (Name_Len - 3 .. Name_Len) = "_XRP"))

      --  For all these cases, just return the name unchanged

      then
         Name_Buffer (Name_Len + 1) := ASCII.NUL;
         return;
      end if;

      Has_Suffix := True;

      --  Fixed-point case: generate GNAT encodings when asked to or when we
      --  know the back-end will not be able to handle the scale factor.

      if Is_Fixed_Point_Type (E)
        and then (GNAT_Encodings /= DWARF_GNAT_Encodings_Minimal
                   or else not Is_Handled_Scale_Factor (Small_Value (E)))
      then
         Get_External_Name (E, True, "XF_");
         Add_Real_To_Buffer (Delta_Value (E));

         if Small_Value (E) /= Delta_Value (E) then
            Add_Str_To_Name_Buffer ("_");
            Add_Real_To_Buffer (Small_Value (E));
         end if;

      --  Discrete case where bounds do not match size. Not necessary if we can
      --  emit standard DWARF.

      elsif GNAT_Encodings /= DWARF_GNAT_Encodings_Minimal
        and then Is_Discrete_Type (E)
        and then not Bounds_Match_Size (E)
      then
         declare
            Lo : constant Node_Id := Type_Low_Bound (E);
            Hi : constant Node_Id := Type_High_Bound (E);

            Lo_Con : constant Boolean := Compile_Time_Known_Value (Lo);
            Hi_Con : constant Boolean := Compile_Time_Known_Value (Hi);

            Lo_Discr : constant Boolean :=
                         Nkind (Lo) = N_Identifier
                           and then Ekind (Entity (Lo)) = E_Discriminant;

            Hi_Discr : constant Boolean :=
                         Nkind (Hi) = N_Identifier
                           and then Ekind (Entity (Hi)) = E_Discriminant;

            Lo_Encode : constant Boolean := Lo_Con or Lo_Discr;
            Hi_Encode : constant Boolean := Hi_Con or Hi_Discr;

            Biased : constant Boolean := Has_Biased_Representation (E);

         begin
            if Biased then
               Get_External_Name (E, True, "XB");
            else
               Get_External_Name (E, True, "XD");
            end if;

            if Lo_Encode or Hi_Encode then
               if Biased then
                  Add_Str_To_Name_Buffer ("_");
               else
                  if Lo_Encode then
                     if Hi_Encode then
                        Add_Str_To_Name_Buffer ("LU_");
                     else
                        Add_Str_To_Name_Buffer ("L_");
                     end if;
                  else
                     Add_Str_To_Name_Buffer ("U_");
                  end if;
               end if;

               if Lo_Con then
                  Add_Uint_To_Buffer (Expr_Rep_Value (Lo));
               elsif Lo_Discr then
                  Get_Name_String_And_Append (Chars (Entity (Lo)));
               end if;

               if Lo_Encode and Hi_Encode then
                  Add_Str_To_Name_Buffer ("__");
               end if;

               if Hi_Con then
                  Add_Uint_To_Buffer (Expr_Rep_Value (Hi));
               elsif Hi_Discr then
                  Get_Name_String_And_Append (Chars (Entity (Hi)));
               end if;
            end if;
         end;

      --  For all other cases, the encoded name is the normal type name

      else
         Has_Suffix := False;
         Get_External_Name (E);
      end if;

      if Debug_Flag_B and then Has_Suffix then
         Write_Str ("**** type ");
         Write_Name (Chars (E));
         Write_Str (" is encoded as ");
         Write_Str (Name_Buffer (1 .. Name_Len));
         Write_Eol;
      end if;

      Name_Buffer (Name_Len + 1) := ASCII.NUL;
   end Get_Encoded_Name;

   -----------------------
   -- Get_External_Name --
   -----------------------

   procedure Get_External_Name
     (Entity     : Entity_Id;
      Has_Suffix : Boolean := False;
      Suffix     : String  := "")
   is
      procedure Get_Qualified_Name_And_Append (Entity : Entity_Id);
      --  Appends fully qualified name of given entity to Name_Buffer

      -----------------------------------
      -- Get_Qualified_Name_And_Append --
      -----------------------------------

      procedure Get_Qualified_Name_And_Append (Entity : Entity_Id) is
      begin
         --  If the entity is a compilation unit, its scope is Standard,
         --  there is no outer scope, and the no further qualification
         --  is required.

         --  If the front end has already computed a fully qualified name,
         --  then it is also the case that no further qualification is
         --  required.

         if Present (Scope (Scope (Entity)))
           and then not Has_Fully_Qualified_Name (Entity)
         then
            Get_Qualified_Name_And_Append (Scope (Entity));
            Add_Str_To_Name_Buffer ("__");
            Get_Name_String_And_Append (Chars (Entity));
            Append_Homonym_Number (Entity);

         else
            Get_Name_String_And_Append (Chars (Entity));
         end if;
      end Get_Qualified_Name_And_Append;

      --  Local variables

      E : Entity_Id := Entity;

   --  Start of processing for Get_External_Name

   begin
      --  If we are not in code generation mode, this procedure may still be
      --  called from Back_End (more specifically - from gigi for doing type
      --  representation annotation or some representation-specific checks).
      --  But in this mode there is no need to mess with external names.

      --  Furthermore, the call causes difficulties in this case because the
      --  string representing the homonym number is not correctly reset as a
      --  part of the call to Output_Homonym_Numbers_Suffix (which is not
      --  called in gigi).

      if Operating_Mode /= Generate_Code then
         return;
      end if;

      Reset_Buffers;

      --  If this is a child unit, we want the child

      if Nkind (E) = N_Defining_Program_Unit_Name then
         E := Defining_Identifier (Entity);
      end if;

      --  Case of interface name being used

      if Ekind (E) in E_Constant
                    | E_Exception
                    | E_Function
                    | E_Procedure
                    | E_Variable
        and then Present (Interface_Name (E))
        and then No (Address_Clause (E))
        and then not Has_Suffix
      then
         Append (Global_Name_Buffer, Strval (Interface_Name (E)));

      --  All other cases besides the interface name case

      else
         --  If this is a library level subprogram (i.e. a subprogram that is a
         --  compilation unit other than a subunit), then we prepend _ada_ to
         --  ensure distinctions required as described in the spec.

         --  Check explicitly for child units, because those are not flagged
         --  as Compilation_Units by lib. Should they be ???

         if Is_Subprogram (E)
           and then (Is_Compilation_Unit (E) or Is_Child_Unit (E))
           and then not Has_Suffix
         then
            Add_Str_To_Name_Buffer ("_ada_");
         end if;

         --  If the entity is a subprogram instance that is not a compilation
         --  unit, generate the name of the original Ada entity, which is the
         --  one gdb needs.

         if Is_Generic_Instance (E)
           and then Is_Subprogram (E)
           and then not Is_Compilation_Unit (Scope (E))
           and then Ekind (Scope (E)) in E_Package | E_Package_Body
           and then Present (Related_Instance (Scope (E)))
         then
            E := Related_Instance (Scope (E));
         end if;

         Get_Qualified_Name_And_Append (E);
      end if;

      if Has_Suffix then
         Add_Str_To_Name_Buffer ("___");
         Add_Str_To_Name_Buffer (Suffix);
      end if;

      --  Add a special prefix to distinguish Ghost entities. In Ignored Ghost
      --  mode, these entities should not leak in the "living" space and they
      --  should be removed by the compiler in a post-processing pass. Thus,
      --  the prefix allows anyone to check that the final executable indeed
      --  does not contain such entities, in such a case. Do not insert this
      --  prefix for compilation units, whose name is used as a basis for the
      --  name of the generated elaboration procedure and (when appropriate)
      --  the executable produced. Only insert this prefix once, for Ghost
      --  entities declared inside other Ghost entities. Three leading
      --  underscores are used so that "___ghost_" is a unique substring of
      --  names produced for Ghost entities, while "__ghost_" can appear in
      --  names of entities inside a child/local package called "Ghost".

      --  The compiler-generated finalizer for an enabled Ghost unit is treated
      --  specially, as its name must be known to the binder, which has no
      --  knowledge of Ghost status. In that case, the finalizer is not marked
      --  as Ghost so that no prefix is added. Note that the special ___ghost_
      --  prefix is retained when the Ghost unit is ignored, which still allows
      --  inspecting the final executable for the presence of an ignored Ghost
      --  finalizer procedure.

      if Is_Ghost_Entity (E)
        and then not Is_Compilation_Unit (E)
        and then (Name_Len < 9
                   or else Name_Buffer (1 .. 9) /= "___ghost_")
      then
         Insert_Str_In_Name_Buffer ("___ghost_", 1);
      end if;

      Name_Buffer (Name_Len + 1) := ASCII.NUL;
   end Get_External_Name;

   --------------------------
   -- Get_Variant_Encoding --
   --------------------------

   procedure Get_Variant_Encoding (V : Node_Id) is
      Choice : Node_Id;

      procedure Choice_Val (Typ : Character; Choice : Node_Id);
      --  Output encoded value for a single choice value. Typ is the key
      --  character ('S', 'F', or 'T') that precedes the choice value.

      ----------------
      -- Choice_Val --
      ----------------

      procedure Choice_Val (Typ : Character; Choice : Node_Id) is
      begin
         if Nkind (Choice) = N_Integer_Literal then
            Add_Char_To_Name_Buffer (Typ);
            Add_Uint_To_Buffer (Intval (Choice));

         --  Character literal with no entity present (this is the case
         --  Standard.Character or Standard.Wide_Character as root type)

         elsif Nkind (Choice) = N_Character_Literal
           and then No (Entity (Choice))
         then
            Add_Char_To_Name_Buffer (Typ);
            Add_Uint_To_Buffer (Char_Literal_Value (Choice));

         else
            declare
               Ent : constant Entity_Id := Entity (Choice);

            begin
               if Ekind (Ent) = E_Enumeration_Literal then
                  Add_Char_To_Name_Buffer (Typ);
                  Add_Uint_To_Buffer (Enumeration_Rep (Ent));

               else
                  pragma Assert (Ekind (Ent) = E_Constant);
                  Choice_Val (Typ, Constant_Value (Ent));
               end if;
            end;
         end if;
      end Choice_Val;

   --  Start of processing for Get_Variant_Encoding

   begin
      Name_Len := 0;

      Choice := First (Discrete_Choices (V));
      while Present (Choice) loop
         if Nkind (Choice) = N_Others_Choice then
            Add_Char_To_Name_Buffer ('O');

         elsif Nkind (Choice) = N_Range then
            Choice_Val ('R', Low_Bound (Choice));
            Choice_Val ('T', High_Bound (Choice));

         elsif Is_Entity_Name (Choice)
           and then Is_Type (Entity (Choice))
         then
            Choice_Val ('R', Type_Low_Bound (Entity (Choice)));
            Choice_Val ('T', Type_High_Bound (Entity (Choice)));

         elsif Nkind (Choice) = N_Subtype_Indication then
            declare
               Rang : constant Node_Id :=
                        Range_Expression (Constraint (Choice));
            begin
               Choice_Val ('R', Low_Bound (Rang));
               Choice_Val ('T', High_Bound (Rang));
            end;

         else
            Choice_Val ('S', Choice);
         end if;

         Next (Choice);
      end loop;

      Name_Buffer (Name_Len + 1) := ASCII.NUL;

      if Debug_Flag_B then
         declare
            VP : constant Node_Id := Parent (V);    -- Variant_Part
            CL : constant Node_Id := Parent (VP);   -- Component_List
            RD : constant Node_Id := Parent (CL);   -- Record_Definition
            FT : constant Node_Id := Parent (RD);   -- Full_Type_Declaration

         begin
            Write_Str ("**** variant for type ");
            Write_Name (Chars (Defining_Identifier (FT)));
            Write_Str (" is encoded as ");
            Write_Str (Name_Buffer (1 .. Name_Len));
            Write_Eol;
         end;
      end if;
   end Get_Variant_Encoding;

   -----------------------------------------
   -- Build_Subprogram_Instance_Renamings --
   -----------------------------------------

   procedure Build_Subprogram_Instance_Renamings
     (N       : Node_Id;
      Wrapper : Entity_Id)
   is
      Loc  : Source_Ptr;
      Decl : Node_Id;
      E    : Entity_Id;

   begin
      E := First_Entity (Wrapper);
      while Present (E) loop
         if Nkind (Parent (E)) = N_Object_Declaration
           and then Is_Elementary_Type (Etype (E))
         then
            Loc := Sloc (Expression (Parent (E)));
            Decl := Make_Object_Renaming_Declaration (Loc,
               Defining_Identifier =>
                 Make_Defining_Identifier (Loc, Chars (E)),
               Subtype_Mark        => New_Occurrence_Of (Etype (E), Loc),
               Name                => New_Occurrence_Of (E, Loc));

            Append (Decl, Declarations (N));
            Set_Debug_Info_Needed (Defining_Identifier (Decl));
         end if;

         Next_Entity (E);
      end loop;
   end Build_Subprogram_Instance_Renamings;

   ------------------------------------
   -- Get_Secondary_DT_External_Name --
   ------------------------------------

   procedure Get_Secondary_DT_External_Name
     (Typ          : Entity_Id;
      Ancestor_Typ : Entity_Id;
      Suffix_Index : Int)
   is
   begin
      Get_External_Name (Typ);

      if Ancestor_Typ /= Typ then
         declare
            Len      : constant Natural := Name_Len;
            Save_Str : constant String (1 .. Name_Len)
                         := Name_Buffer (1 .. Name_Len);
         begin
            Get_External_Name (Ancestor_Typ);

            --  Append the extended name of the ancestor to the
            --  extended name of Typ

            Name_Buffer (Len + 2 .. Len + Name_Len + 1) :=
              Name_Buffer (1 .. Name_Len);
            Name_Buffer (1 .. Len) := Save_Str;
            Name_Buffer (Len + 1) := '_';
            Name_Len := Len + Name_Len + 1;
         end;
      end if;

      Add_Nat_To_Name_Buffer (Suffix_Index);
   end Get_Secondary_DT_External_Name;

   ---------------------------------
   -- Make_Packed_Array_Impl_Type_Name --
   ---------------------------------

   function Make_Packed_Array_Impl_Type_Name
     (Typ   : Entity_Id;
      Csize : Uint)
      return  Name_Id
   is
   begin
      Get_Name_String (Chars (Typ));
      Add_Str_To_Name_Buffer ("___XP");
      Add_Uint_To_Buffer (Csize);
      return Name_Find;
   end Make_Packed_Array_Impl_Type_Name;

   -----------------------------------
   -- Output_Homonym_Numbers_Suffix --
   -----------------------------------

   procedure Output_Homonym_Numbers_Suffix is
      J : Natural;

   begin
      if Homonym_Len > 0 then

         --  Check for all 1's, in which case we do not output

         J := 1;
         loop
            exit when Homonym_Numbers (J) /= '1';

            --  If we reached end of string we do not output

            if J = Homonym_Len then
               Homonym_Len := 0;
               return;
            end if;

            exit when Homonym_Numbers (J + 1) /= '_';
            J := J + 2;
         end loop;

         --  If we exit the loop then suffix must be output

         Add_Str_To_Name_Buffer ("__");
         Add_Str_To_Name_Buffer (Homonym_Numbers (1 .. Homonym_Len));
         Homonym_Len := 0;
      end if;
   end Output_Homonym_Numbers_Suffix;

   ------------------------------
   -- Prepend_String_To_Buffer --
   ------------------------------

   procedure Prepend_String_To_Buffer (S : String) is
      N : constant Integer := S'Length;
   begin
      Name_Buffer (1 + N .. Name_Len + N) := Name_Buffer (1 .. Name_Len);
      Name_Buffer (1 .. N) := S;
      Name_Len := Name_Len + N;
   end Prepend_String_To_Buffer;

   ----------------------------
   -- Prepend_Uint_To_Buffer --
   ----------------------------

   procedure Prepend_Uint_To_Buffer (U : Uint) is
   begin
      if U < 0 then
         Prepend_String_To_Buffer ("m");
         Prepend_Uint_To_Buffer (-U);
      else
         UI_Image (U, Decimal);
         Prepend_String_To_Buffer (UI_Image_Buffer (1 .. UI_Image_Length));
      end if;
   end Prepend_Uint_To_Buffer;

   ------------------------------
   -- Qualify_All_Entity_Names --
   ------------------------------

   procedure Qualify_All_Entity_Names is
      E   : Entity_Id;
      Ent : Entity_Id;
      Nod : Node_Id;

   begin
      for J in Name_Qualify_Units.First .. Name_Qualify_Units.Last loop
         Nod := Name_Qualify_Units.Table (J);

         --  When a scoping construct is ignored Ghost, it is rewritten as
         --  a null statement. Skip such constructs as they no longer carry
         --  names.

         if Nkind (Nod) = N_Null_Statement then
            goto Continue;
         end if;

         E := Defining_Entity (Nod);
         Reset_Buffers;
         Qualify_Entity_Name (E);

         --  Normally entities in the qualification list are scopes, but in the
         --  case of a library-level package renaming there is an associated
         --  variable that encodes the debugger name and that variable is
         --  entered in the list since it occurs in the Aux_Decls list of the
         --  compilation and doesn't have a normal scope.

         if Ekind (E) /= E_Variable then
            Ent := First_Entity (E);
            while Present (Ent) loop
               Reset_Buffers;
               Qualify_Entity_Name (Ent);
               Next_Entity (Ent);

               --  There are odd cases where Last_Entity (E) = E. This happens
               --  in the case of renaming of packages. This test avoids
               --  getting stuck in such cases.

               exit when Ent = E;
            end loop;
         end if;

         <<Continue>>
         null;
      end loop;
   end Qualify_All_Entity_Names;

   -------------------------
   -- Qualify_Entity_Name --
   -------------------------

   procedure Qualify_Entity_Name (Ent : Entity_Id) is

      Full_Qualify_Name : String (1 .. Name_Buffer'Length);
      Full_Qualify_Len  : Natural := 0;
      --  Used to accumulate fully qualified name of subprogram

      procedure Fully_Qualify_Name (E : Entity_Id);
      --  Used to qualify a subprogram or type name, where full
      --  qualification up to Standard is always used. Name is set
      --  in Full_Qualify_Name with the length in Full_Qualify_Len.
      --  Note that this routine does not prepend the _ada_ string
      --  required for library subprograms (this is done in the back end).

      function Is_BNPE (S : Entity_Id) return Boolean;
      --  Determines if S is a BNPE, i.e. Body-Nested Package Entity, which
      --  is defined to be a package which is immediately nested within a
      --  package body.

      function Qualify_Needed (S : Entity_Id) return Boolean;
      --  Given a scope, determines if the scope is to be included in the
      --  fully qualified name, True if so, False if not. Blocks and loops
      --  are excluded from a qualified name.

      procedure Set_BNPE_Suffix (E : Entity_Id);
      --  Recursive routine to append the BNPE qualification suffix. Works
      --  from right to left with E being the current entity in the list.
      --  The result does NOT have the trailing n's and trailing b stripped.
      --  The caller must do this required stripping.

      procedure Set_Entity_Name (E : Entity_Id);
      --  Internal recursive routine that does most of the work. This routine
      --  leaves the result sitting in Name_Buffer and Name_Len.

      BNPE_Suffix_Needed : Boolean := False;
      --  Set true if a body-nested package entity suffix is required

      Save_Chars : constant Name_Id := Chars (Ent);
      --  Save original name

      ------------------------
      -- Fully_Qualify_Name --
      ------------------------

      procedure Fully_Qualify_Name (E : Entity_Id) is
         Discard : Boolean := False;

      begin
         --  Ignore empty entry (can happen in error cases)

         if No (E) then
            return;

         --  If this we are qualifying entities local to a generic instance,
         --  use the name of the original instantiation, not that of the
         --  anonymous subprogram in the wrapper package, so that gdb doesn't
         --  have to know about these.

         elsif Is_Generic_Instance (E)
           and then Is_Subprogram (E)
           and then not Comes_From_Source (E)
           and then not Is_Compilation_Unit (Scope (E))
         then
            Fully_Qualify_Name (Related_Instance (Scope (E)));
            return;
         end if;

         --  If we reached fully qualified name, then just copy it

         if Has_Fully_Qualified_Name (E) then
            Get_Name_String (Chars (E));
            Strip_Suffixes (Discard);
            Full_Qualify_Name (1 .. Name_Len) := Name_Buffer (1 .. Name_Len);
            Full_Qualify_Len := Name_Len;
            Set_Has_Fully_Qualified_Name (Ent);

         --  Case of non-fully qualified name

         else
            if Scope (E) = Standard_Standard then
               Set_Has_Fully_Qualified_Name (Ent);
            else
               Fully_Qualify_Name (Scope (E));
               Full_Qualify_Name (Full_Qualify_Len + 1) := '_';
               Full_Qualify_Name (Full_Qualify_Len + 2) := '_';
               Full_Qualify_Len := Full_Qualify_Len + 2;
            end if;

            if Has_Qualified_Name (E) then
               Get_Unqualified_Name_String (Chars (E));
            else
               Get_Name_String (Chars (E));
            end if;

            --  Here we do one step of the qualification

            Full_Qualify_Name
              (Full_Qualify_Len + 1 .. Full_Qualify_Len + Name_Len) :=
                 Name_Buffer (1 .. Name_Len);
            Full_Qualify_Len := Full_Qualify_Len + Name_Len;
            Append_Homonym_Number (E);
         end if;

         if Is_BNPE (E) then
            BNPE_Suffix_Needed := True;
         end if;
      end Fully_Qualify_Name;

      -------------
      -- Is_BNPE --
      -------------

      function Is_BNPE (S : Entity_Id) return Boolean is
      begin
         return Ekind (S) = E_Package and then Is_Package_Body_Entity (S);
      end Is_BNPE;

      --------------------
      -- Qualify_Needed --
      --------------------

      function Qualify_Needed (S : Entity_Id) return Boolean is
      begin
         --  If we got all the way to Standard, then we have certainly
         --  fully qualified the name, so set the flag appropriately,
         --  and then return False, since we are most certainly done.

         if S = Standard_Standard then
            Set_Has_Fully_Qualified_Name (Ent, True);
            return False;

         --  Otherwise figure out if further qualification is required

         else
            return Is_Subprogram (Ent)
              or else Ekind (Ent) = E_Subprogram_Body
              or else (Ekind (S) /= E_Block
                        and then Ekind (S) /= E_Loop
                        and then not Is_Dynamic_Scope (S));
         end if;
      end Qualify_Needed;

      ---------------------
      -- Set_BNPE_Suffix --
      ---------------------

      procedure Set_BNPE_Suffix (E : Entity_Id) is
         S : constant Entity_Id := Scope (E);

      begin
         if Qualify_Needed (S) then
            Set_BNPE_Suffix (S);

            if Is_BNPE (E) then
               Add_Char_To_Name_Buffer ('b');
            else
               Add_Char_To_Name_Buffer ('n');
            end if;

         else
            Add_Char_To_Name_Buffer ('X');
         end if;
      end Set_BNPE_Suffix;

      ---------------------
      -- Set_Entity_Name --
      ---------------------

      procedure Set_Entity_Name (E : Entity_Id) is
         S : constant Entity_Id := Scope (E);

      begin
         --  If we reach an already qualified name, just take the encoding
         --  except that we strip the package body suffixes, since these
         --  will be separately put on later.

         if Has_Qualified_Name (E) then
            Get_Name_String_And_Append (Chars (E));
            Strip_Suffixes (BNPE_Suffix_Needed);

            --  If the top level name we are adding is itself fully
            --  qualified, then that means that the name that we are
            --  preparing for the Fully_Qualify_Name call will also
            --  generate a fully qualified name.

            if Has_Fully_Qualified_Name (E) then
               Set_Has_Fully_Qualified_Name (Ent);
            end if;

         --  Case where upper level name is not encoded yet

         else
            --  Recurse if further qualification required

            if Qualify_Needed (S) then
               Set_Entity_Name (S);
               Add_Str_To_Name_Buffer ("__");
            end if;

            --  Otherwise get name and note if it is a BNPE

            Get_Name_String_And_Append (Chars (E));

            if Is_BNPE (E) then
               BNPE_Suffix_Needed := True;
            end if;

            Append_Homonym_Number (E);
         end if;
      end Set_Entity_Name;

   --  Start of processing for Qualify_Entity_Name

   begin
      if Has_Qualified_Name (Ent) then
         return;

      --  If the entity is a variable encoding the debug name for an object
      --  renaming, then the qualified name of the entity associated with the
      --  renamed object can now be incorporated in the debug name.

      elsif Ekind (Ent) = E_Variable
        and then Present (Debug_Renaming_Link (Ent))
      then
         Name_Len := 0;
         Qualify_Entity_Name (Debug_Renaming_Link (Ent));
         Get_Name_String (Chars (Ent));

         --  Retrieve the now-qualified name of the renamed entity and insert
         --  it in the middle of the name, just preceding the suffix encoding
         --  describing the renamed object.

         declare
            Renamed_Id : constant String :=
                           Get_Name_String (Chars (Debug_Renaming_Link (Ent)));
            Insert_Len : constant Integer := Renamed_Id'Length + 1;
            Index      : Natural := Name_Len - 3;

         begin
            --  Loop backwards through the name to find the start of the "___"
            --  sequence associated with the suffix.

            while Index >= Name_Buffer'First
              and then (Name_Buffer (Index + 1) /= '_'
                         or else Name_Buffer (Index + 2) /= '_'
                         or else Name_Buffer (Index + 3) /= '_')
            loop
               Index := Index - 1;
            end loop;

            pragma Assert (Name_Buffer (Index + 1 .. Index + 3) = "___");

            --  Insert an underscore separator and the entity name just in
            --  front of the suffix.

            Name_Buffer (Index + 1 + Insert_Len .. Name_Len + Insert_Len) :=
              Name_Buffer (Index + 1 .. Name_Len);
            Name_Buffer (Index + 1) := '_';
            Name_Buffer (Index + 2 .. Index + Insert_Len) := Renamed_Id;
            Name_Len := Name_Len + Insert_Len;
         end;

         --  Reset the name of the variable to the new name that includes the
         --  name of the renamed entity.

         Set_Chars (Ent, Name_Enter);

         --  If the entity needs qualification by its scope then develop it
         --  here, add the variable's name, and again reset the entity name.

         if Qualify_Needed (Scope (Ent)) then
            Name_Len := 0;
            Set_Entity_Name (Scope (Ent));
            Add_Str_To_Name_Buffer ("__");

            Get_Name_String_And_Append (Chars (Ent));

            Set_Chars (Ent, Name_Enter);
         end if;

         Set_Has_Qualified_Name (Ent);
         return;

      elsif Is_Subprogram (Ent)
        or else Ekind (Ent) = E_Subprogram_Body
        or else Is_Type (Ent)
        or else Ekind (Ent) = E_Exception
      then
         Fully_Qualify_Name (Ent);
         Name_Len := Full_Qualify_Len;
         Name_Buffer (1 .. Name_Len) := Full_Qualify_Name (1 .. Name_Len);

      --  Qualification needed for enumeration literals when generating C code
      --  (to simplify their management in the backend).

      elsif Modify_Tree_For_C
        and then Ekind (Ent) = E_Enumeration_Literal
        and then Scope (Ultimate_Alias (Ent)) /= Standard_Standard
      then
         Fully_Qualify_Name (Ent);
         Name_Len := Full_Qualify_Len;
         Name_Buffer (1 .. Name_Len) := Full_Qualify_Name (1 .. Name_Len);

      elsif Qualify_Needed (Scope (Ent)) then
         Name_Len := 0;
         Set_Entity_Name (Ent);

      else
         Set_Has_Qualified_Name (Ent);

         --  If a variable is hidden by a subsequent loop variable, qualify
         --  the name of that loop variable to prevent visibility issues when
         --  translating to C. Note that gdb probably never handled properly
         --  this accidental hiding, given that loops are not scopes at
         --  runtime. We also qualify a name if it hides an outer homonym,
         --  and both are declared in blocks.

         if Modify_Tree_For_C and then Ekind (Ent) =  E_Variable then
            if Present (Hiding_Loop_Variable (Ent)) then
               declare
                  Var : constant Entity_Id := Hiding_Loop_Variable (Ent);

               begin
                  Set_Entity_Name (Var);
                  Add_Str_To_Name_Buffer ("L");
                  Set_Chars (Var, Name_Enter);
               end;

            elsif Present (Homonym (Ent))
              and then Ekind (Scope (Ent)) = E_Block
              and then Ekind (Scope (Homonym (Ent))) = E_Block
            then
               Set_Entity_Name (Ent);
               Add_Str_To_Name_Buffer ("B");
               Set_Chars (Ent, Name_Enter);
            end if;
         end if;

         return;
      end if;

      --  Fall through with a fully qualified name in Name_Buffer/Name_Len

      Output_Homonym_Numbers_Suffix;

      --  Add body-nested package suffix if required

      if BNPE_Suffix_Needed
        and then Ekind (Ent) /= E_Enumeration_Literal
      then
         Set_BNPE_Suffix (Ent);

         --  Strip trailing n's and last trailing b as required. note that
         --  we know there is at least one b, or no suffix would be generated.

         while Name_Buffer (Name_Len) = 'n' loop
            Name_Len := Name_Len - 1;
         end loop;

         Name_Len := Name_Len - 1;
      end if;

      Set_Chars (Ent, Name_Enter);
      Set_Has_Qualified_Name (Ent);

      if Debug_Flag_BB then
         Write_Str ("*** ");
         Write_Name (Save_Chars);
         Write_Str (" qualified as ");
         Write_Name (Chars (Ent));
         Write_Eol;
      end if;
   end Qualify_Entity_Name;

   --------------------------
   -- Qualify_Entity_Names --
   --------------------------

   procedure Qualify_Entity_Names (N : Node_Id) is
   begin
      Name_Qualify_Units.Append (N);
   end Qualify_Entity_Names;

   -------------------
   -- Reset_Buffers --
   -------------------

   procedure Reset_Buffers is
   begin
      Name_Len    := 0;
      Homonym_Len := 0;
   end Reset_Buffers;

   --------------------
   -- Strip_Suffixes --
   --------------------

   procedure Strip_Suffixes (BNPE_Suffix_Found : in out Boolean) is
      SL : Natural;

      pragma Warnings (Off, BNPE_Suffix_Found);
      --  Since this procedure only ever sets the flag

   begin
      --  Search for and strip BNPE suffix

      for J in reverse 2 .. Name_Len loop
         if Name_Buffer (J) = 'X' then
            Name_Len := J - 1;
            BNPE_Suffix_Found := True;
            exit;
         end if;

         exit when Name_Buffer (J) /= 'b' and then Name_Buffer (J) /= 'n';
      end loop;

      --  Search for and strip homonym numbers suffix

      for J in reverse 2 .. Name_Len - 2 loop
         if Name_Buffer (J) = '_'
           and then Name_Buffer (J + 1) = '_'
         then
            if Name_Buffer (J + 2) in '0' .. '9' then
               if Homonym_Len > 0 then
                  Homonym_Len := Homonym_Len + 1;
                  Homonym_Numbers (Homonym_Len) := '-';
               end if;

               SL := Name_Len - (J + 1);

               Homonym_Numbers (Homonym_Len + 1 .. Homonym_Len + SL) :=
                 Name_Buffer (J + 2 .. Name_Len);
               Name_Len := J - 1;
               Homonym_Len := Homonym_Len + SL;
            end if;

            exit;
         end if;
      end loop;
   end Strip_Suffixes;

end Exp_Dbug;
/span> () || limit_vr->varying_p () || (limit_vr->symbolic_p () && ! (limit_vr->kind () == VR_RANGE && (limit_vr->min () == limit_vr->max () || operand_equal_p (limit_vr->min (), limit_vr->max (), 0))))) limit_vr = NULL; /* Initially, the new range has the same set of equivalences of VAR's range. This will be revised before returning the final value. Since assertions may be chained via mutually exclusive predicates, we will need to trim the set of equivalences before we are done. */ gcc_assert (vr_p->equiv () == NULL); vr_p->equiv_add (var, get_value_range (var), &vrp_equiv_obstack); /* Extract a new range based on the asserted comparison for VAR and LIMIT's value range. Notice that if LIMIT has an anti-range, we will only use it for equality comparisons (EQ_EXPR). For any other kind of assertion, we cannot derive a range from LIMIT's anti-range that can be used to describe the new range. For instance, ASSERT_EXPR <x_2, x_2 <= b_4>. If b_4 is ~[2, 10], then b_4 takes on the ranges [-INF, 1] and [11, +INF]. There is no single range for x_2 that could describe LE_EXPR, so we might as well build the range [b_4, +INF] for it. One special case we handle is extracting a range from a range test encoded as (unsigned)var + CST <= limit. */ if (TREE_CODE (op) == NOP_EXPR || TREE_CODE (op) == PLUS_EXPR) { if (TREE_CODE (op) == PLUS_EXPR) { min = fold_build1 (NEGATE_EXPR, TREE_TYPE (TREE_OPERAND (op, 1)), TREE_OPERAND (op, 1)); max = int_const_binop (PLUS_EXPR, limit, min); op = TREE_OPERAND (op, 0); } else { min = build_int_cst (TREE_TYPE (var), 0); max = limit; } /* Make sure to not set TREE_OVERFLOW on the final type conversion. We are willingly interpreting large positive unsigned values as negative signed values here. */ min = force_fit_type (TREE_TYPE (var), wi::to_widest (min), 0, false); max = force_fit_type (TREE_TYPE (var), wi::to_widest (max), 0, false); /* We can transform a max, min range to an anti-range or vice-versa. Use set_and_canonicalize which does this for us. */ if (cond_code == LE_EXPR) vr_p->set (min, max, vr_p->equiv ()); else if (cond_code == GT_EXPR) vr_p->set (min, max, vr_p->equiv (), VR_ANTI_RANGE); else gcc_unreachable (); } else if (cond_code == EQ_EXPR) { enum value_range_kind range_kind; if (limit_vr) { range_kind = limit_vr->kind (); min = limit_vr->min (); max = limit_vr->max (); } else { range_kind = VR_RANGE; min = limit; max = limit; } vr_p->update (min, max, range_kind); /* When asserting the equality VAR == LIMIT and LIMIT is another SSA name, the new range will also inherit the equivalence set from LIMIT. */ if (TREE_CODE (limit) == SSA_NAME) vr_p->equiv_add (limit, get_value_range (limit), &vrp_equiv_obstack); } else if (cond_code == NE_EXPR) { /* As described above, when LIMIT's range is an anti-range and this assertion is an inequality (NE_EXPR), then we cannot derive anything from the anti-range. For instance, if LIMIT's range was ~[0, 0], the assertion 'VAR != LIMIT' does not imply that VAR's range is [0, 0]. So, in the case of anti-ranges, we just assert the inequality using LIMIT and not its anti-range. If LIMIT_VR is a range, we can only use it to build a new anti-range if LIMIT_VR is a single-valued range. For instance, if LIMIT_VR is [0, 1], the predicate VAR != [0, 1] does not mean that VAR's range is ~[0, 1]. Rather, it means that for value 0 VAR should be ~[0, 0] and for value 1, VAR should be ~[1, 1]. We cannot represent these ranges. The only situation in which we can build a valid anti-range is when LIMIT_VR is a single-valued range (i.e., LIMIT_VR->MIN == LIMIT_VR->MAX). In that case, build the anti-range ~[LIMIT_VR->MIN, LIMIT_VR->MAX]. */ if (limit_vr && limit_vr->kind () == VR_RANGE && compare_values (limit_vr->min (), limit_vr->max ()) == 0) { min = limit_vr->min (); max = limit_vr->max (); } else { /* In any other case, we cannot use LIMIT's range to build a valid anti-range. */ min = max = limit; } /* If MIN and MAX cover the whole range for their type, then just use the original LIMIT. */ if (INTEGRAL_TYPE_P (type) && vrp_val_is_min (min) && vrp_val_is_max (max)) min = max = limit; vr_p->set (min, max, vr_p->equiv (), VR_ANTI_RANGE); } else if (cond_code == LE_EXPR || cond_code == LT_EXPR) { min = TYPE_MIN_VALUE (type); if (limit_vr == NULL || limit_vr->kind () == VR_ANTI_RANGE) max = limit; else { /* If LIMIT_VR is of the form [N1, N2], we need to build the range [MIN, N2] for LE_EXPR and [MIN, N2 - 1] for LT_EXPR. */ max = limit_vr->max (); } /* If the maximum value forces us to be out of bounds, simply punt. It would be pointless to try and do anything more since this all should be optimized away above us. */ if (cond_code == LT_EXPR && compare_values (max, min) == 0) vr_p->set_varying (TREE_TYPE (min)); else { /* For LT_EXPR, we create the range [MIN, MAX - 1]. */ if (cond_code == LT_EXPR) { if (TYPE_PRECISION (TREE_TYPE (max)) == 1 && !TYPE_UNSIGNED (TREE_TYPE (max))) max = fold_build2 (PLUS_EXPR, TREE_TYPE (max), max, build_int_cst (TREE_TYPE (max), -1)); else max = fold_build2 (MINUS_EXPR, TREE_TYPE (max), max, build_int_cst (TREE_TYPE (max), 1)); /* Signal to compare_values_warnv this expr doesn't overflow. */ if (EXPR_P (max)) TREE_NO_WARNING (max) = 1; } vr_p->update (min, max); } } else if (cond_code == GE_EXPR || cond_code == GT_EXPR) { max = TYPE_MAX_VALUE (type); if (limit_vr == NULL || limit_vr->kind () == VR_ANTI_RANGE) min = limit; else { /* If LIMIT_VR is of the form [N1, N2], we need to build the range [N1, MAX] for GE_EXPR and [N1 + 1, MAX] for GT_EXPR. */ min = limit_vr->min (); } /* If the minimum value forces us to be out of bounds, simply punt. It would be pointless to try and do anything more since this all should be optimized away above us. */ if (cond_code == GT_EXPR && compare_values (min, max) == 0) vr_p->set_varying (TREE_TYPE (min)); else { /* For GT_EXPR, we create the range [MIN + 1, MAX]. */ if (cond_code == GT_EXPR) { if (TYPE_PRECISION (TREE_TYPE (min)) == 1 && !TYPE_UNSIGNED (TREE_TYPE (min))) min = fold_build2 (MINUS_EXPR, TREE_TYPE (min), min, build_int_cst (TREE_TYPE (min), -1)); else min = fold_build2 (PLUS_EXPR, TREE_TYPE (min), min, build_int_cst (TREE_TYPE (min), 1)); /* Signal to compare_values_warnv this expr doesn't overflow. */ if (EXPR_P (min)) TREE_NO_WARNING (min) = 1; } vr_p->update (min, max); } } else gcc_unreachable (); /* Finally intersect the new range with what we already know about var. */ vr_p->intersect (get_value_range (var)); } /* Extract value range information from an ASSERT_EXPR EXPR and store it in *VR_P. */ void vr_values::extract_range_from_assert (value_range_equiv *vr_p, tree expr) { tree var = ASSERT_EXPR_VAR (expr); tree cond = ASSERT_EXPR_COND (expr); tree limit, op; enum tree_code cond_code; gcc_assert (COMPARISON_CLASS_P (cond)); /* Find VAR in the ASSERT_EXPR conditional. */ if (var == TREE_OPERAND (cond, 0) || TREE_CODE (TREE_OPERAND (cond, 0)) == PLUS_EXPR || TREE_CODE (TREE_OPERAND (cond, 0)) == NOP_EXPR) { /* If the predicate is of the form VAR COMP LIMIT, then we just take LIMIT from the RHS and use the same comparison code. */ cond_code = TREE_CODE (cond); limit = TREE_OPERAND (cond, 1); op = TREE_OPERAND (cond, 0); } else { /* If the predicate is of the form LIMIT COMP VAR, then we need to flip around the comparison code to create the proper range for VAR. */ cond_code = swap_tree_comparison (TREE_CODE (cond)); limit = TREE_OPERAND (cond, 0); op = TREE_OPERAND (cond, 1); } extract_range_for_var_from_comparison_expr (var, cond_code, op, limit, vr_p); } /* Extract range information from SSA name VAR and store it in VR. If VAR has an interesting range, use it. Otherwise, create the range [VAR, VAR] and return it. This is useful in situations where we may have conditionals testing values of VARYING names. For instance, x_3 = y_5; if (x_3 > y_5) ... Even if y_5 is deemed VARYING, we can determine that x_3 > y_5 is always false. */ void vr_values::extract_range_from_ssa_name (value_range_equiv *vr, tree var) { const value_range_equiv *var_vr = get_value_range (var); if (!var_vr->varying_p ()) vr->deep_copy (var_vr); else vr->set (var); if (!vr->undefined_p ()) vr->equiv_add (var, get_value_range (var), &vrp_equiv_obstack); } /* Extract range information from a binary expression OP0 CODE OP1 based on the ranges of each of its operands with resulting type EXPR_TYPE. The resulting range is stored in *VR. */ void vr_values::extract_range_from_binary_expr (value_range_equiv *vr, enum tree_code code, tree expr_type, tree op0, tree op1) { /* Get value ranges for each operand. For constant operands, create a new value range with the operand to simplify processing. */ value_range vr0, vr1; if (TREE_CODE (op0) == SSA_NAME) vr0 = *(get_value_range (op0)); else if (is_gimple_min_invariant (op0)) vr0.set (op0); else vr0.set_varying (TREE_TYPE (op0)); if (TREE_CODE (op1) == SSA_NAME) vr1 = *(get_value_range (op1)); else if (is_gimple_min_invariant (op1)) vr1.set (op1); else vr1.set_varying (TREE_TYPE (op1)); /* If one argument is varying, we can sometimes still deduce a range for the output: any + [3, +INF] is in [MIN+3, +INF]. */ if (INTEGRAL_TYPE_P (TREE_TYPE (op0)) && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (op0))) { if (vr0.varying_p () && !vr1.varying_p ()) vr0 = value_range (vrp_val_min (expr_type), vrp_val_max (expr_type)); else if (vr1.varying_p () && !vr0.varying_p ()) vr1 = value_range (vrp_val_min (expr_type), vrp_val_max (expr_type)); } range_fold_binary_expr (vr, code, expr_type, &vr0, &vr1); /* Set value_range for n in following sequence: def = __builtin_memchr (arg, 0, sz) n = def - arg Here the range for n can be set to [0, PTRDIFF_MAX - 1]. */ if (vr->varying_p () && code == POINTER_DIFF_EXPR && TREE_CODE (op0) == SSA_NAME && TREE_CODE (op1) == SSA_NAME) { tree op0_ptype = TREE_TYPE (TREE_TYPE (op0)); tree op1_ptype = TREE_TYPE (TREE_TYPE (op1)); gcall *call_stmt = NULL; if (TYPE_MODE (op0_ptype) == TYPE_MODE (char_type_node) && TYPE_PRECISION (op0_ptype) == TYPE_PRECISION (char_type_node) && TYPE_MODE (op1_ptype) == TYPE_MODE (char_type_node) && TYPE_PRECISION (op1_ptype) == TYPE_PRECISION (char_type_node) && (call_stmt = dyn_cast<gcall *>(SSA_NAME_DEF_STMT (op0))) && gimple_call_builtin_p (call_stmt, BUILT_IN_MEMCHR) && operand_equal_p (op0, gimple_call_lhs (call_stmt), 0) && operand_equal_p (op1, gimple_call_arg (call_stmt, 0), 0) && integer_zerop (gimple_call_arg (call_stmt, 1))) { tree max = vrp_val_max (ptrdiff_type_node); wide_int wmax = wi::to_wide (max, TYPE_PRECISION (TREE_TYPE (max))); tree range_min = build_zero_cst (expr_type); tree range_max = wide_int_to_tree (expr_type, wmax - 1); vr->set (range_min, range_max); return; } } /* Try harder for PLUS and MINUS if the range of one operand is symbolic and based on the other operand, for example if it was deduced from a symbolic comparison. When a bound of the range of the first operand is invariant, we set the corresponding bound of the new range to INF in order to avoid recursing on the range of the second operand. */ if (vr->varying_p () && (code == PLUS_EXPR || code == MINUS_EXPR) && TREE_CODE (op1) == SSA_NAME && vr0.kind () == VR_RANGE && symbolic_range_based_on_p (&vr0, op1)) { const bool minus_p = (code == MINUS_EXPR); value_range n_vr1; /* Try with VR0 and [-INF, OP1]. */ if (is_gimple_min_invariant (minus_p ? vr0.max () : vr0.min ())) n_vr1.set (vrp_val_min (expr_type), op1); /* Try with VR0 and [OP1, +INF]. */ else if (is_gimple_min_invariant (minus_p ? vr0.min () : vr0.max ())) n_vr1.set (op1, vrp_val_max (expr_type)); /* Try with VR0 and [OP1, OP1]. */ else n_vr1.set (op1, op1); range_fold_binary_expr (vr, code, expr_type, &vr0, &n_vr1); } if (vr->varying_p () && (code == PLUS_EXPR || code == MINUS_EXPR) && TREE_CODE (op0) == SSA_NAME && vr1.kind () == VR_RANGE && symbolic_range_based_on_p (&vr1, op0)) { const bool minus_p = (code == MINUS_EXPR); value_range n_vr0; /* Try with [-INF, OP0] and VR1. */ if (is_gimple_min_invariant (minus_p ? vr1.max () : vr1.min ())) n_vr0.set (vrp_val_min (expr_type), op0); /* Try with [OP0, +INF] and VR1. */ else if (is_gimple_min_invariant (minus_p ? vr1.min (): vr1.max ())) n_vr0.set (op0, vrp_val_max (expr_type)); /* Try with [OP0, OP0] and VR1. */ else n_vr0.set (op0); range_fold_binary_expr (vr, code, expr_type, &n_vr0, &vr1); } /* If we didn't derive a range for MINUS_EXPR, and op1's range is ~[op0,op0] or vice-versa, then we can derive a non-null range. This happens often for pointer subtraction. */ if (vr->varying_p () && (code == MINUS_EXPR || code == POINTER_DIFF_EXPR) && TREE_CODE (op0) == SSA_NAME && ((vr0.kind () == VR_ANTI_RANGE && vr0.min () == op1 && vr0.min () == vr0.max ()) || (vr1.kind () == VR_ANTI_RANGE && vr1.min () == op0 && vr1.min () == vr1.max ()))) { vr->set_nonzero (expr_type); vr->equiv_clear (); } } /* Extract range information from a unary expression CODE OP0 based on the range of its operand with resulting type TYPE. The resulting range is stored in *VR. */ void vr_values::extract_range_from_unary_expr (value_range_equiv *vr, enum tree_code code, tree type, tree op0) { value_range vr0; /* Get value ranges for the operand. For constant operands, create a new value range with the operand to simplify processing. */ if (TREE_CODE (op0) == SSA_NAME) vr0 = *(get_value_range (op0)); else if (is_gimple_min_invariant (op0)) vr0.set (op0); else vr0.set_varying (type); range_fold_unary_expr (vr, code, type, &vr0, TREE_TYPE (op0)); } /* Extract range information from a conditional expression STMT based on the ranges of each of its operands and the expression code. */ void vr_values::extract_range_from_cond_expr (value_range_equiv *vr, gassign *stmt) { /* Get value ranges for each operand. For constant operands, create a new value range with the operand to simplify processing. */ tree op0 = gimple_assign_rhs2 (stmt); value_range_equiv tem0; const value_range_equiv *vr0 = &tem0; if (TREE_CODE (op0) == SSA_NAME) vr0 = get_value_range (op0); else if (is_gimple_min_invariant (op0)) tem0.set (op0); else tem0.set_varying (TREE_TYPE (op0)); tree op1 = gimple_assign_rhs3 (stmt); value_range_equiv tem1; const value_range_equiv *vr1 = &tem1; if (TREE_CODE (op1) == SSA_NAME) vr1 = get_value_range (op1); else if (is_gimple_min_invariant (op1)) tem1.set (op1); else tem1.set_varying (TREE_TYPE (op1)); /* The resulting value range is the union of the operand ranges */ vr->deep_copy (vr0); vr->union_ (vr1); } /* Extract range information from a comparison expression EXPR based on the range of its operand and the expression code. */ void vr_values::extract_range_from_comparison (value_range_equiv *vr, gimple *stmt) { enum tree_code code = gimple_assign_rhs_code (stmt); tree type = gimple_expr_type (stmt); tree op0 = gimple_assign_rhs1 (stmt); tree op1 = gimple_assign_rhs2 (stmt); bool sop; tree val = simplifier.vrp_evaluate_conditional_warnv_with_ops (stmt, code, op0, op1, false, &sop, NULL); if (val) { /* Since this expression was found on the RHS of an assignment, its type may be different from _Bool. Convert VAL to EXPR's type. */ val = fold_convert (type, val); if (is_gimple_min_invariant (val)) vr->set (val); else vr->update (val, val); } else /* The result of a comparison is always true or false. */ set_value_range_to_truthvalue (vr, type); } /* Helper function for simplify_internal_call_using_ranges and extract_range_basic. Return true if OP0 SUBCODE OP1 for SUBCODE {PLUS,MINUS,MULT}_EXPR is known to never overflow or always overflow. Set *OVF to true if it is known to always overflow. */ static bool check_for_binary_op_overflow (range_query *query, enum tree_code subcode, tree type, tree op0, tree op1, bool *ovf) { value_range vr0, vr1; if (TREE_CODE (op0) == SSA_NAME) vr0 = *query->get_value_range (op0); else if (TREE_CODE (op0) == INTEGER_CST) vr0.set (op0); else vr0.set_varying (TREE_TYPE (op0)); if (TREE_CODE (op1) == SSA_NAME) vr1 = *query->get_value_range (op1); else if (TREE_CODE (op1) == INTEGER_CST) vr1.set (op1); else vr1.set_varying (TREE_TYPE (op1)); tree vr0min = vr0.min (), vr0max = vr0.max (); tree vr1min = vr1.min (), vr1max = vr1.max (); if (!range_int_cst_p (&vr0) || TREE_OVERFLOW (vr0min) || TREE_OVERFLOW (vr0max)) { vr0min = vrp_val_min (TREE_TYPE (op0)); vr0max = vrp_val_max (TREE_TYPE (op0)); } if (!range_int_cst_p (&vr1) || TREE_OVERFLOW (vr1min) || TREE_OVERFLOW (vr1max)) { vr1min = vrp_val_min (TREE_TYPE (op1)); vr1max = vrp_val_max (TREE_TYPE (op1)); } *ovf = arith_overflowed_p (subcode, type, vr0min, subcode == MINUS_EXPR ? vr1max : vr1min); if (arith_overflowed_p (subcode, type, vr0max, subcode == MINUS_EXPR ? vr1min : vr1max) != *ovf) return false; if (subcode == MULT_EXPR) { if (arith_overflowed_p (subcode, type, vr0min, vr1max) != *ovf || arith_overflowed_p (subcode, type, vr0max, vr1min) != *ovf) return false; } if (*ovf) { /* So far we found that there is an overflow on the boundaries. That doesn't prove that there is an overflow even for all values in between the boundaries. For that compute widest_int range of the result and see if it doesn't overlap the range of type. */ widest_int wmin, wmax; widest_int w[4]; int i; w[0] = wi::to_widest (vr0min); w[1] = wi::to_widest (vr0max); w[2] = wi::to_widest (vr1min); w[3] = wi::to_widest (vr1max); for (i = 0; i < 4; i++) { widest_int wt; switch (subcode) { case PLUS_EXPR: wt = wi::add (w[i & 1], w[2 + (i & 2) / 2]); break; case MINUS_EXPR: wt = wi::sub (w[i & 1], w[2 + (i & 2) / 2]); break; case MULT_EXPR: wt = wi::mul (w[i & 1], w[2 + (i & 2) / 2]); break; default: gcc_unreachable (); } if (i == 0) { wmin = wt; wmax = wt; } else { wmin = wi::smin (wmin, wt); wmax = wi::smax (wmax, wt); } } /* The result of op0 CODE op1 is known to be in range [wmin, wmax]. */ widest_int wtmin = wi::to_widest (vrp_val_min (type)); widest_int wtmax = wi::to_widest (vrp_val_max (type)); /* If all values in [wmin, wmax] are smaller than [wtmin, wtmax] or all are larger than [wtmin, wtmax], the arithmetic operation will always overflow. */ if (wmax < wtmin || wmin > wtmax) return true; return false; } return true; } /* Derive a range from a builtin. Set range in VR and return TRUE if successful. */ bool vr_values::extract_range_from_ubsan_builtin (value_range_equiv *vr, gimple *stmt) { gcc_assert (is_gimple_call (stmt)); tree type = gimple_expr_type (stmt); enum tree_code subcode = ERROR_MARK; combined_fn cfn = gimple_call_combined_fn (stmt); scalar_int_mode mode; switch (cfn) { case CFN_UBSAN_CHECK_ADD: subcode = PLUS_EXPR; break; case CFN_UBSAN_CHECK_SUB: subcode = MINUS_EXPR; break; case CFN_UBSAN_CHECK_MUL: subcode = MULT_EXPR; break; default: break; } if (subcode != ERROR_MARK) { bool saved_flag_wrapv = flag_wrapv; /* Pretend the arithmetics is wrapping. If there is any overflow, we'll complain, but will actually do wrapping operation. */ flag_wrapv = 1; extract_range_from_binary_expr (vr, subcode, type, gimple_call_arg (stmt, 0), gimple_call_arg (stmt, 1)); flag_wrapv = saved_flag_wrapv; /* If for both arguments vrp_valueize returned non-NULL, this should have been already folded and if not, it wasn't folded because of overflow. Avoid removing the UBSAN_CHECK_* calls in that case. */ if (vr->kind () == VR_RANGE && (vr->min () == vr->max () || operand_equal_p (vr->min (), vr->max (), 0))) vr->set_varying (vr->type ()); return !vr->varying_p (); } return false; } /* Try to derive a nonnegative or nonzero range out of STMT relying primarily on generic routines in fold in conjunction with range data. Store the result in *VR */ void vr_values::extract_range_basic (value_range_equiv *vr, gimple *stmt) { bool sop; tree type = gimple_expr_type (stmt); if (is_gimple_call (stmt)) { combined_fn cfn = gimple_call_combined_fn (stmt); switch (cfn) { case CFN_UBSAN_CHECK_ADD: case CFN_UBSAN_CHECK_SUB: case CFN_UBSAN_CHECK_MUL: if (extract_range_from_ubsan_builtin (vr, stmt)) return; break; default: if (range_of_builtin_call (*this, *vr, as_a<gcall *> (stmt))) { /* The original code nuked equivalences every time a range was found, so do the same here. */ vr->equiv_clear (); return; } break; } } /* Handle extraction of the two results (result of arithmetics and a flag whether arithmetics overflowed) from {ADD,SUB,MUL}_OVERFLOW internal function. Similarly from ATOMIC_COMPARE_EXCHANGE. */ else if (is_gimple_assign (stmt) && (gimple_assign_rhs_code (stmt) == REALPART_EXPR || gimple_assign_rhs_code (stmt) == IMAGPART_EXPR) && INTEGRAL_TYPE_P (type)) { enum tree_code code = gimple_assign_rhs_code (stmt); tree op = gimple_assign_rhs1 (stmt); if (TREE_CODE (op) == code && TREE_CODE (TREE_OPERAND (op, 0)) == SSA_NAME) { gimple *g = SSA_NAME_DEF_STMT (TREE_OPERAND (op, 0)); if (is_gimple_call (g) && gimple_call_internal_p (g)) { enum tree_code subcode = ERROR_MARK; switch (gimple_call_internal_fn (g)) { case IFN_ADD_OVERFLOW: subcode = PLUS_EXPR; break; case IFN_SUB_OVERFLOW: subcode = MINUS_EXPR; break; case IFN_MUL_OVERFLOW: subcode = MULT_EXPR; break; case IFN_ATOMIC_COMPARE_EXCHANGE: if (code == IMAGPART_EXPR) { /* This is the boolean return value whether compare and exchange changed anything or not. */ vr->set (build_int_cst (type, 0), build_int_cst (type, 1)); return; } break; default: break; } if (subcode != ERROR_MARK) { tree op0 = gimple_call_arg (g, 0); tree op1 = gimple_call_arg (g, 1); if (code == IMAGPART_EXPR) { bool ovf = false; if (check_for_binary_op_overflow (this, subcode, type, op0, op1, &ovf)) vr->set (build_int_cst (type, ovf)); else if (TYPE_PRECISION (type) == 1 && !TYPE_UNSIGNED (type)) vr->set_varying (type); else vr->set (build_int_cst (type, 0), build_int_cst (type, 1)); } else if (types_compatible_p (type, TREE_TYPE (op0)) && types_compatible_p (type, TREE_TYPE (op1))) { bool saved_flag_wrapv = flag_wrapv; /* Pretend the arithmetics is wrapping. If there is any overflow, IMAGPART_EXPR will be set. */ flag_wrapv = 1; extract_range_from_binary_expr (vr, subcode, type, op0, op1); flag_wrapv = saved_flag_wrapv; } else { value_range_equiv vr0, vr1; bool saved_flag_wrapv = flag_wrapv; /* Pretend the arithmetics is wrapping. If there is any overflow, IMAGPART_EXPR will be set. */ flag_wrapv = 1; extract_range_from_unary_expr (&vr0, NOP_EXPR, type, op0); extract_range_from_unary_expr (&vr1, NOP_EXPR, type, op1); range_fold_binary_expr (vr, subcode, type, &vr0, &vr1); flag_wrapv = saved_flag_wrapv; } return; } } } } if (INTEGRAL_TYPE_P (type) && gimple_stmt_nonnegative_warnv_p (stmt, &sop)) set_value_range_to_nonnegative (vr, type); else if (vrp_stmt_computes_nonzero (stmt)) { vr->set_nonzero (type); vr->equiv_clear (); } else vr->set_varying (type); } /* Try to compute a useful range out of assignment STMT and store it in *VR. */ void vr_values::extract_range_from_assignment (value_range_equiv *vr, gassign *stmt) { enum tree_code code = gimple_assign_rhs_code (stmt); if (code == ASSERT_EXPR) extract_range_from_assert (vr, gimple_assign_rhs1 (stmt)); else if (code == SSA_NAME) extract_range_from_ssa_name (vr, gimple_assign_rhs1 (stmt)); else if (TREE_CODE_CLASS (code) == tcc_binary) extract_range_from_binary_expr (vr, gimple_assign_rhs_code (stmt), gimple_expr_type (stmt), gimple_assign_rhs1 (stmt), gimple_assign_rhs2 (stmt)); else if (TREE_CODE_CLASS (code) == tcc_unary) extract_range_from_unary_expr (vr, gimple_assign_rhs_code (stmt), gimple_expr_type (stmt), gimple_assign_rhs1 (stmt)); else if (code == COND_EXPR) extract_range_from_cond_expr (vr, stmt); else if (TREE_CODE_CLASS (code) == tcc_comparison) extract_range_from_comparison (vr, stmt); else if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS && is_gimple_min_invariant (gimple_assign_rhs1 (stmt))) vr->set (gimple_assign_rhs1 (stmt)); else vr->set_varying (TREE_TYPE (gimple_assign_lhs (stmt))); if (vr->varying_p ()) extract_range_basic (vr, stmt); } /* Given two numeric value ranges VR0, VR1 and a comparison code COMP: - Return BOOLEAN_TRUE_NODE if VR0 COMP VR1 always returns true for all the values in the ranges. - Return BOOLEAN_FALSE_NODE if the comparison always returns false. - Return NULL_TREE if it is not always possible to determine the value of the comparison. Also set *STRICT_OVERFLOW_P to indicate whether comparision evaluation assumed signed overflow is undefined. */ static tree compare_ranges (enum tree_code comp, const value_range_equiv *vr0, const value_range_equiv *vr1, bool *strict_overflow_p) { /* VARYING or UNDEFINED ranges cannot be compared. */ if (vr0->varying_p () || vr0->undefined_p () || vr1->varying_p () || vr1->undefined_p ()) return NULL_TREE; /* Anti-ranges need to be handled separately. */ if (vr0->kind () == VR_ANTI_RANGE || vr1->kind () == VR_ANTI_RANGE) { /* If both are anti-ranges, then we cannot compute any comparison. */ if (vr0->kind () == VR_ANTI_RANGE && vr1->kind () == VR_ANTI_RANGE) return NULL_TREE; /* These comparisons are never statically computable. */ if (comp == GT_EXPR || comp == GE_EXPR || comp == LT_EXPR || comp == LE_EXPR) return NULL_TREE; /* Equality can be computed only between a range and an anti-range. ~[VAL1, VAL2] == [VAL1, VAL2] is always false. */ if (vr0->kind () == VR_RANGE) /* To simplify processing, make VR0 the anti-range. */ std::swap (vr0, vr1); gcc_assert (comp == NE_EXPR || comp == EQ_EXPR); if (compare_values_warnv (vr0->min (), vr1->min (), strict_overflow_p) == 0 && compare_values_warnv (vr0->max (), vr1->max (), strict_overflow_p) == 0) return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node; return NULL_TREE; } /* Simplify processing. If COMP is GT_EXPR or GE_EXPR, switch the operands around and change the comparison code. */ if (comp == GT_EXPR || comp == GE_EXPR) { comp = (comp == GT_EXPR) ? LT_EXPR : LE_EXPR; std::swap (vr0, vr1); } if (comp == EQ_EXPR) { /* Equality may only be computed if both ranges represent exactly one value. */ if (compare_values_warnv (vr0->min (), vr0->max (), strict_overflow_p) == 0 && compare_values_warnv (vr1->min (), vr1->max (), strict_overflow_p) == 0) { int cmp_min = compare_values_warnv (vr0->min (), vr1->min (), strict_overflow_p); int cmp_max = compare_values_warnv (vr0->max (), vr1->max (), strict_overflow_p); if (cmp_min == 0 && cmp_max == 0) return boolean_true_node; else if (cmp_min != -2 && cmp_max != -2) return boolean_false_node; } /* If [V0_MIN, V1_MAX] < [V1_MIN, V1_MAX] then V0 != V1. */ else if (compare_values_warnv (vr0->min (), vr1->max (), strict_overflow_p) == 1 || compare_values_warnv (vr1->min (), vr0->max (), strict_overflow_p) == 1) return boolean_false_node; return NULL_TREE; } else if (comp == NE_EXPR) { int cmp1, cmp2; /* If VR0 is completely to the left or completely to the right of VR1, they are always different. Notice that we need to make sure that both comparisons yield similar results to avoid comparing values that cannot be compared at compile-time. */ cmp1 = compare_values_warnv (vr0->max (), vr1->min (), strict_overflow_p); cmp2 = compare_values_warnv (vr0->min (), vr1->max (), strict_overflow_p); if ((cmp1 == -1 && cmp2 == -1) || (cmp1 == 1 && cmp2 == 1)) return boolean_true_node; /* If VR0 and VR1 represent a single value and are identical, return false. */ else if (compare_values_warnv (vr0->min (), vr0->max (), strict_overflow_p) == 0 && compare_values_warnv (vr1->min (), vr1->max (), strict_overflow_p) == 0 && compare_values_warnv (vr0->min (), vr1->min (), strict_overflow_p) == 0 && compare_values_warnv (vr0->max (), vr1->max (), strict_overflow_p) == 0) return boolean_false_node; /* Otherwise, they may or may not be different. */ else return NULL_TREE; } else if (comp == LT_EXPR || comp == LE_EXPR) { int tst; /* If VR0 is to the left of VR1, return true. */ tst = compare_values_warnv (vr0->max (), vr1->min (), strict_overflow_p); if ((comp == LT_EXPR && tst == -1) || (comp == LE_EXPR && (tst == -1 || tst == 0))) return boolean_true_node; /* If VR0 is to the right of VR1, return false. */ tst = compare_values_warnv (vr0->min (), vr1->max (), strict_overflow_p); if ((comp == LT_EXPR && (tst == 0 || tst == 1)) || (comp == LE_EXPR && tst == 1)) return boolean_false_node; /* Otherwise, we don't know. */ return NULL_TREE; } gcc_unreachable (); } /* Given a value range VR, a value VAL and a comparison code COMP, return BOOLEAN_TRUE_NODE if VR COMP VAL always returns true for all the values in VR. Return BOOLEAN_FALSE_NODE if the comparison always returns false. Return NULL_TREE if it is not always possible to determine the value of the comparison. Also set *STRICT_OVERFLOW_P to indicate whether comparision evaluation assumed signed overflow is undefined. */ static tree compare_range_with_value (enum tree_code comp, const value_range *vr, tree val, bool *strict_overflow_p) { if (vr->varying_p () || vr->undefined_p ()) return NULL_TREE; /* Anti-ranges need to be handled separately. */ if (vr->kind () == VR_ANTI_RANGE) { /* For anti-ranges, the only predicates that we can compute at compile time are equality and inequality. */ if (comp == GT_EXPR || comp == GE_EXPR || comp == LT_EXPR || comp == LE_EXPR) return NULL_TREE; /* ~[VAL_1, VAL_2] OP VAL is known if VAL_1 <= VAL <= VAL_2. */ if (!vr->may_contain_p (val)) return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node; return NULL_TREE; } if (comp == EQ_EXPR) { /* EQ_EXPR may only be computed if VR represents exactly one value. */ if (compare_values_warnv (vr->min (), vr->max (), strict_overflow_p) == 0) { int cmp = compare_values_warnv (vr->min (), val, strict_overflow_p); if (cmp == 0) return boolean_true_node; else if (cmp == -1 || cmp == 1 || cmp == 2) return boolean_false_node; } else if (compare_values_warnv (val, vr->min (), strict_overflow_p) == -1 || compare_values_warnv (vr->max (), val, strict_overflow_p) == -1) return boolean_false_node; return NULL_TREE; } else if (comp == NE_EXPR) { /* If VAL is not inside VR, then they are always different. */ if (compare_values_warnv (vr->max (), val, strict_overflow_p) == -1 || compare_values_warnv (vr->min (), val, strict_overflow_p) == 1) return boolean_true_node; /* If VR represents exactly one value equal to VAL, then return false. */ if (compare_values_warnv (vr->min (), vr->max (), strict_overflow_p) == 0 && compare_values_warnv (vr->min (), val, strict_overflow_p) == 0) return boolean_false_node; /* Otherwise, they may or may not be different. */ return NULL_TREE; } else if (comp == LT_EXPR || comp == LE_EXPR) { int tst; /* If VR is to the left of VAL, return true. */ tst = compare_values_warnv (vr->max (), val, strict_overflow_p); if ((comp == LT_EXPR && tst == -1) || (comp == LE_EXPR && (tst == -1 || tst == 0))) return boolean_true_node; /* If VR is to the right of VAL, return false. */ tst = compare_values_warnv (vr->min (), val, strict_overflow_p); if ((comp == LT_EXPR && (tst == 0 || tst == 1)) || (comp == LE_EXPR && tst == 1)) return boolean_false_node; /* Otherwise, we don't know. */ return NULL_TREE; } else if (comp == GT_EXPR || comp == GE_EXPR) { int tst; /* If VR is to the right of VAL, return true. */ tst = compare_values_warnv (vr->min (), val, strict_overflow_p); if ((comp == GT_EXPR && tst == 1) || (comp == GE_EXPR && (tst == 0 || tst == 1))) return boolean_true_node; /* If VR is to the left of VAL, return false. */ tst = compare_values_warnv (vr->max (), val, strict_overflow_p); if ((comp == GT_EXPR && (tst == -1 || tst == 0)) || (comp == GE_EXPR && tst == -1)) return boolean_false_node; /* Otherwise, we don't know. */ return NULL_TREE; } gcc_unreachable (); } /* Given a VAR in STMT within LOOP, determine the bounds of the variable and store it in MIN/MAX and return TRUE. If no bounds could be determined, return FALSE. */ bool bounds_of_var_in_loop (tree *min, tree *max, range_query *query, class loop *loop, gimple *stmt, tree var) { tree init, step, chrec, tmin, tmax, type = TREE_TYPE (var); enum ev_direction dir; chrec = instantiate_parameters (loop, analyze_scalar_evolution (loop, var)); /* Like in PR19590, scev can return a constant function. */ if (is_gimple_min_invariant (chrec)) { *min = *max = chrec; goto fix_overflow; } if (TREE_CODE (chrec) != POLYNOMIAL_CHREC) return false; init = initial_condition_in_loop_num (chrec, loop->num); step = evolution_part_in_loop_num (chrec, loop->num); /* If INIT is an SSA with a singleton range, set INIT to said singleton, otherwise leave INIT alone. */ if (TREE_CODE (init) == SSA_NAME) query->get_value_range (init, stmt)->singleton_p (&init); /* Likewise for step. */ if (TREE_CODE (step) == SSA_NAME) query->get_value_range (step, stmt)->singleton_p (&step); /* If STEP is symbolic, we can't know whether INIT will be the minimum or maximum value in the range. Also, unless INIT is a simple expression, compare_values and possibly other functions in tree-vrp won't be able to handle it. */ if (step == NULL_TREE || !is_gimple_min_invariant (step) || !valid_value_p (init)) return false; dir = scev_direction (chrec); if (/* Do not adjust ranges if we do not know whether the iv increases or decreases, ... */ dir == EV_DIR_UNKNOWN /* ... or if it may wrap. */ || scev_probably_wraps_p (NULL_TREE, init, step, stmt, get_chrec_loop (chrec), true)) return false; if (POINTER_TYPE_P (type) || !TYPE_MIN_VALUE (type)) tmin = lower_bound_in_type (type, type); else tmin = TYPE_MIN_VALUE (type); if (POINTER_TYPE_P (type) || !TYPE_MAX_VALUE (type)) tmax = upper_bound_in_type (type, type); else tmax = TYPE_MAX_VALUE (type); /* Try to use estimated number of iterations for the loop to constrain the final value in the evolution. */ if (TREE_CODE (step) == INTEGER_CST && is_gimple_val (init) && (TREE_CODE (init) != SSA_NAME || query->get_value_range (init, stmt)->kind () == VR_RANGE)) { widest_int nit; /* We are only entering here for loop header PHI nodes, so using the number of latch executions is the correct thing to use. */ if (max_loop_iterations (loop, &nit)) { signop sgn = TYPE_SIGN (TREE_TYPE (step)); wi::overflow_type overflow; widest_int wtmp = wi::mul (wi::to_widest (step), nit, sgn, &overflow); /* If the multiplication overflowed we can't do a meaningful adjustment. Likewise if the result doesn't fit in the type of the induction variable. For a signed type we have to check whether the result has the expected signedness which is that of the step as number of iterations is unsigned. */ if (!overflow && wi::fits_to_tree_p (wtmp, TREE_TYPE (init)) && (sgn == UNSIGNED || wi::gts_p (wtmp, 0) == wi::gts_p (wi::to_wide (step), 0))) { value_range maxvr, vr0, vr1; if (TREE_CODE (init) == SSA_NAME) vr0 = *(query->get_value_range (init, stmt)); else if (is_gimple_min_invariant (init)) vr0.set (init); else vr0.set_varying (TREE_TYPE (init)); tree tem = wide_int_to_tree (TREE_TYPE (init), wtmp); vr1.set (tem, tem); range_fold_binary_expr (&maxvr, PLUS_EXPR, TREE_TYPE (init), &vr0, &vr1); /* Likewise if the addition did. */ if (maxvr.kind () == VR_RANGE) { value_range initvr; if (TREE_CODE (init) == SSA_NAME) initvr = *(query->get_value_range (init, stmt)); else if (is_gimple_min_invariant (init)) initvr.set (init); else return false; /* Check if init + nit * step overflows. Though we checked scev {init, step}_loop doesn't wrap, it is not enough because the loop may exit immediately. Overflow could happen in the plus expression in this case. */ if ((dir == EV_DIR_DECREASES && compare_values (maxvr.min (), initvr.min ()) != -1) || (dir == EV_DIR_GROWS && compare_values (maxvr.max (), initvr.max ()) != 1)) return false; tmin = maxvr.min (); tmax = maxvr.max (); } } } } *min = tmin; *max = tmax; if (dir == EV_DIR_DECREASES) *max = init; else *min = init; fix_overflow: /* Even for valid range info, sometimes overflow flag will leak in. As GIMPLE IL should have no constants with TREE_OVERFLOW set, we drop them. */ if (TREE_OVERFLOW_P (*min)) *min = drop_tree_overflow (*min); if (TREE_OVERFLOW_P (*max)) *max = drop_tree_overflow (*max); gcc_checking_assert (compare_values (*min, *max) != 1); return true; } /* Given a range VR, a LOOP and a variable VAR, determine whether it would be profitable to adjust VR using scalar evolution information for VAR. If so, update VR with the new limits. */ void vr_values::adjust_range_with_scev (value_range_equiv *vr, class loop *loop, gimple *stmt, tree var) { tree min, max; if (bounds_of_var_in_loop (&min, &max, this, loop, stmt, var)) { if (vr->undefined_p () || vr->varying_p ()) { /* For VARYING or UNDEFINED ranges, just about anything we get from scalar evolutions should be better. */ vr->update (min, max); } else if (vr->kind () == VR_RANGE) { /* Start with the input range... */ tree vrmin = vr->min (); tree vrmax = vr->max (); /* ...and narrow it down with what we got from SCEV. */ if (compare_values (min, vrmin) == 1) vrmin = min; if (compare_values (max, vrmax) == -1) vrmax = max; vr->update (vrmin, vrmax); } else if (vr->kind () == VR_ANTI_RANGE) { /* ?? As an enhancement, if VR, MIN, and MAX are constants, one could just intersect VR with a range of [MIN,MAX]. */ } } } /* Dump value ranges of all SSA_NAMEs to FILE. */ void vr_values::dump_all_value_ranges (FILE *file) { size_t i; for (i = 0; i < num_vr_values; i++) { if (vr_value[i] && ssa_name (i)) { print_generic_expr (file, ssa_name (i)); fprintf (file, ": "); dump_value_range (file, vr_value[i]); fprintf (file, "\n"); } } fprintf (file, "\n"); } /* Initialize VRP lattice. */ vr_values::vr_values () : simplifier (this) { values_propagated = false; num_vr_values = num_ssa_names * 2; vr_value = XCNEWVEC (value_range_equiv *, num_vr_values); vr_phi_edge_counts = XCNEWVEC (int, num_ssa_names); bitmap_obstack_initialize (&vrp_equiv_obstack); } /* Free VRP lattice. */ vr_values::~vr_values () { /* Free allocated memory. */ free (vr_value); free (vr_phi_edge_counts); bitmap_obstack_release (&vrp_equiv_obstack); /* So that we can distinguish between VRP data being available and not available. */ vr_value = NULL; vr_phi_edge_counts = NULL; } /* A hack. */ static class vr_values *x_vr_values; /* Return the singleton value-range for NAME or NAME. */ static inline tree vrp_valueize (tree name) { if (TREE_CODE (name) == SSA_NAME) { const value_range_equiv *vr = x_vr_values->get_value_range (name); if (vr->kind () == VR_RANGE && (TREE_CODE (vr->min ()) == SSA_NAME || is_gimple_min_invariant (vr->min ())) && vrp_operand_equal_p (vr->min (), vr->max ())) return vr->min (); } return name; } /* Return the singleton value-range for NAME if that is a constant but signal to not follow SSA edges. */ static inline tree vrp_valueize_1 (tree name) { if (TREE_CODE (name) == SSA_NAME) { /* If the definition may be simulated again we cannot follow this SSA edge as the SSA propagator does not necessarily re-visit the use. */ gimple *def_stmt = SSA_NAME_DEF_STMT (name); if (!gimple_nop_p (def_stmt) && prop_simulate_again_p (def_stmt)) return NULL_TREE; const value_range_equiv *vr = x_vr_values->get_value_range (name); tree singleton; if (vr->singleton_p (&singleton)) return singleton; } return name; } /* Given STMT, an assignment or call, return its LHS if the type of the LHS is suitable for VRP analysis, else return NULL_TREE. */ tree get_output_for_vrp (gimple *stmt) { if (!is_gimple_assign (stmt) && !is_gimple_call (stmt)) return NULL_TREE; /* We only keep track of ranges in integral and pointer types. */ tree lhs = gimple_get_lhs (stmt); if (TREE_CODE (lhs) == SSA_NAME && ((INTEGRAL_TYPE_P (TREE_TYPE (lhs)) /* It is valid to have NULL MIN/MAX values on a type. See build_range_type. */ && TYPE_MIN_VALUE (TREE_TYPE (lhs)) && TYPE_MAX_VALUE (TREE_TYPE (lhs))) || POINTER_TYPE_P (TREE_TYPE (lhs)))) return lhs; return NULL_TREE; } /* Visit assignment STMT. If it produces an interesting range, record the range in VR and set LHS to OUTPUT_P. */ void vr_values::vrp_visit_assignment_or_call (gimple *stmt, tree *output_p, value_range_equiv *vr) { tree lhs = get_output_for_vrp (stmt); *output_p = lhs; /* We only keep track of ranges in integral and pointer types. */ if (lhs) { enum gimple_code code = gimple_code (stmt); /* Try folding the statement to a constant first. */ x_vr_values = this; tree tem = gimple_fold_stmt_to_constant_1 (stmt, vrp_valueize, vrp_valueize_1); x_vr_values = NULL; if (tem) { if (TREE_CODE (tem) == SSA_NAME && (SSA_NAME_IS_DEFAULT_DEF (tem) || ! prop_simulate_again_p (SSA_NAME_DEF_STMT (tem)))) { extract_range_from_ssa_name (vr, tem); return; } else if (is_gimple_min_invariant (tem)) { vr->set (tem); return; } } /* Then dispatch to value-range extracting functions. */ if (code == GIMPLE_CALL) extract_range_basic (vr, stmt); else extract_range_from_assignment (vr, as_a <gassign *> (stmt)); } } /* Helper that gets the value range of the SSA_NAME with version I or a symbolic range containing the SSA_NAME only if the value range is varying or undefined. Uses TEM as storage for the alternate range. */ const value_range_equiv * simplify_using_ranges::get_vr_for_comparison (int i, value_range_equiv *tem) { /* Shallow-copy equiv bitmap. */ const value_range_equiv *vr = query->get_value_range (ssa_name (i)); /* If name N_i does not have a valid range, use N_i as its own range. This allows us to compare against names that may have N_i in their ranges. */ if (vr->varying_p () || vr->undefined_p ()) { tem->set (ssa_name (i)); return tem; } return vr; } /* Compare all the value ranges for names equivalent to VAR with VAL using comparison code COMP. Return the same value returned by compare_range_with_value, including the setting of *STRICT_OVERFLOW_P. */ tree simplify_using_ranges::compare_name_with_value (enum tree_code comp, tree var, tree val, bool *strict_overflow_p, bool use_equiv_p) { /* Get the set of equivalences for VAR. */ bitmap e = query->get_value_range (var)->equiv (); /* Start at -1. Set it to 0 if we do a comparison without relying on overflow, or 1 if all comparisons rely on overflow. */ int used_strict_overflow = -1; /* Compare vars' value range with val. */ value_range_equiv tem_vr; const value_range_equiv *equiv_vr = get_vr_for_comparison (SSA_NAME_VERSION (var), &tem_vr); bool sop = false; tree retval = compare_range_with_value (comp, equiv_vr, val, &sop); if (retval) used_strict_overflow = sop ? 1 : 0; /* If the equiv set is empty we have done all work we need to do. */ if (e == NULL) { if (retval && used_strict_overflow > 0) *strict_overflow_p = true; return retval; } unsigned i; bitmap_iterator bi; EXECUTE_IF_SET_IN_BITMAP (e, 0, i, bi) { tree name = ssa_name (i); if (!name) continue; if (!use_equiv_p && !SSA_NAME_IS_DEFAULT_DEF (name) && prop_simulate_again_p (SSA_NAME_DEF_STMT (name))) continue; equiv_vr = get_vr_for_comparison (i, &tem_vr); sop = false; tree t = compare_range_with_value (comp, equiv_vr, val, &sop); if (t) { /* If we get different answers from different members of the equivalence set this check must be in a dead code region. Folding it to a trap representation would be correct here. For now just return don't-know. */ if (retval != NULL && t != retval) { retval = NULL_TREE; break; } retval = t; if (!sop) used_strict_overflow = 0; else if (used_strict_overflow < 0) used_strict_overflow = 1; } } if (retval && used_strict_overflow > 0) *strict_overflow_p = true; return retval; } /* Given a comparison code COMP and names N1 and N2, compare all the ranges equivalent to N1 against all the ranges equivalent to N2 to determine the value of N1 COMP N2. Return the same value returned by compare_ranges. Set *STRICT_OVERFLOW_P to indicate whether we relied on undefined signed overflow in the comparison. */ tree simplify_using_ranges::compare_names (enum tree_code comp, tree n1, tree n2, bool *strict_overflow_p) { /* Compare the ranges of every name equivalent to N1 against the ranges of every name equivalent to N2. */ bitmap e1 = query->get_value_range (n1)->equiv (); bitmap e2 = query->get_value_range (n2)->equiv (); /* Use the fake bitmaps if e1 or e2 are not available. */ static bitmap s_e1 = NULL, s_e2 = NULL; static bitmap_obstack *s_obstack = NULL; if (s_obstack == NULL) { s_obstack = XNEW (bitmap_obstack); bitmap_obstack_initialize (s_obstack); s_e1 = BITMAP_ALLOC (s_obstack); s_e2 = BITMAP_ALLOC (s_obstack); } if (e1 == NULL) e1 = s_e1; if (e2 == NULL) e2 = s_e2; /* Add N1 and N2 to their own set of equivalences to avoid duplicating the body of the loop just to check N1 and N2 ranges. */ bitmap_set_bit (e1, SSA_NAME_VERSION (n1)); bitmap_set_bit (e2, SSA_NAME_VERSION (n2)); /* If the equivalence sets have a common intersection, then the two names can be compared without checking their ranges. */ if (bitmap_intersect_p (e1, e2)) { bitmap_clear_bit (e1, SSA_NAME_VERSION (n1)); bitmap_clear_bit (e2, SSA_NAME_VERSION (n2)); return (comp == EQ_EXPR || comp == GE_EXPR || comp == LE_EXPR) ? boolean_true_node : boolean_false_node; } /* Start at -1. Set it to 0 if we do a comparison without relying on overflow, or 1 if all comparisons rely on overflow. */ int used_strict_overflow = -1; /* Otherwise, compare all the equivalent ranges. First, add N1 and N2 to their own set of equivalences to avoid duplicating the body of the loop just to check N1 and N2 ranges. */ bitmap_iterator bi1; unsigned i1; EXECUTE_IF_SET_IN_BITMAP (e1, 0, i1, bi1) { if (!ssa_name (i1)) continue; value_range_equiv tem_vr1; const value_range_equiv *vr1 = get_vr_for_comparison (i1, &tem_vr1); tree t = NULL_TREE, retval = NULL_TREE; bitmap_iterator bi2; unsigned i2; EXECUTE_IF_SET_IN_BITMAP (e2, 0, i2, bi2) { if (!ssa_name (i2)) continue; bool sop = false; value_range_equiv tem_vr2; const value_range_equiv *vr2 = get_vr_for_comparison (i2, &tem_vr2); t = compare_ranges (comp, vr1, vr2, &sop); if (t) { /* If we get different answers from different members of the equivalence set this check must be in a dead code region. Folding it to a trap representation would be correct here. For now just return don't-know. */ if (retval != NULL && t != retval) { bitmap_clear_bit (e1, SSA_NAME_VERSION (n1)); bitmap_clear_bit (e2, SSA_NAME_VERSION (n2)); return NULL_TREE; } retval = t; if (!sop) used_strict_overflow = 0; else if (used_strict_overflow < 0) used_strict_overflow = 1; } } if (retval) { bitmap_clear_bit (e1, SSA_NAME_VERSION (n1)); bitmap_clear_bit (e2, SSA_NAME_VERSION (n2)); if (used_strict_overflow > 0) *strict_overflow_p = true; return retval; } } /* None of the equivalent ranges are useful in computing this comparison. */ bitmap_clear_bit (e1, SSA_NAME_VERSION (n1)); bitmap_clear_bit (e2, SSA_NAME_VERSION (n2)); return NULL_TREE; } /* Helper function for vrp_evaluate_conditional_warnv & other optimizers. */ tree simplify_using_ranges::vrp_evaluate_conditional_warnv_with_ops_using_ranges (enum tree_code code, tree op0, tree op1, bool * strict_overflow_p) { const value_range_equiv *vr0, *vr1; vr0 = (TREE_CODE (op0) == SSA_NAME) ? query->get_value_range (op0) : NULL; vr1 = (TREE_CODE (op1) == SSA_NAME) ? query->get_value_range (op1) : NULL; tree res = NULL_TREE; if (vr0 && vr1) res = compare_ranges (code, vr0, vr1, strict_overflow_p); if (!res && vr0) res = compare_range_with_value (code, vr0, op1, strict_overflow_p); if (!res && vr1) res = (compare_range_with_value (swap_tree_comparison (code), vr1, op0, strict_overflow_p)); return res; } /* Helper function for vrp_evaluate_conditional_warnv. */ tree simplify_using_ranges::vrp_evaluate_conditional_warnv_with_ops (gimple *stmt, enum tree_code code, tree op0, tree op1, bool use_equiv_p, bool *strict_overflow_p, bool *only_ranges) { tree ret; if (only_ranges) *only_ranges = true; /* We only deal with integral and pointer types. */ if (!INTEGRAL_TYPE_P (TREE_TYPE (op0)) && !POINTER_TYPE_P (TREE_TYPE (op0))) return NULL_TREE; /* If OP0 CODE OP1 is an overflow comparison, if it can be expressed as a simple equality test, then prefer that over its current form for evaluation. An overflow test which collapses to an equality test can always be expressed as a comparison of one argument against zero. Overflow occurs when the chosen argument is zero and does not occur if the chosen argument is not zero. */ tree x; if (overflow_comparison_p (code, op0, op1, use_equiv_p, &x)) { wide_int max = wi::max_value (TYPE_PRECISION (TREE_TYPE (op0)), UNSIGNED); /* B = A - 1; if (A < B) -> B = A - 1; if (A == 0) B = A - 1; if (A > B) -> B = A - 1; if (A != 0) B = A + 1; if (B < A) -> B = A + 1; if (B == 0) B = A + 1; if (B > A) -> B = A + 1; if (B != 0) */ if (integer_zerop (x)) { op1 = x; code = (code == LT_EXPR || code == LE_EXPR) ? EQ_EXPR : NE_EXPR; } /* B = A + 1; if (A > B) -> B = A + 1; if (B == 0) B = A + 1; if (A < B) -> B = A + 1; if (B != 0) B = A - 1; if (B > A) -> B = A - 1; if (A == 0) B = A - 1; if (B < A) -> B = A - 1; if (A != 0) */ else if (wi::to_wide (x) == max - 1) { op0 = op1; op1 = wide_int_to_tree (TREE_TYPE (op0), 0); code = (code == GT_EXPR || code == GE_EXPR) ? EQ_EXPR : NE_EXPR; } else { value_range vro, vri; if (code == GT_EXPR || code == GE_EXPR) { vro.set (TYPE_MIN_VALUE (TREE_TYPE (op0)), x, VR_ANTI_RANGE); vri.set (TYPE_MIN_VALUE (TREE_TYPE (op0)), x); } else if (code == LT_EXPR || code == LE_EXPR) { vro.set (TYPE_MIN_VALUE (TREE_TYPE (op0)), x); vri.set (TYPE_MIN_VALUE (TREE_TYPE (op0)), x, VR_ANTI_RANGE); } else gcc_unreachable (); const value_range_equiv *vr0 = query->get_value_range (op0, stmt); /* If vro, the range for OP0 to pass the overflow test, has no intersection with *vr0, OP0's known range, then the overflow test can't pass, so return the node for false. If it is the inverted range, vri, that has no intersection, then the overflow test must pass, so return the node for true. In other cases, we could proceed with a simplified condition comparing OP0 and X, with LE_EXPR for previously LE_ or LT_EXPR and GT_EXPR otherwise, but the comments next to the enclosing if suggest it's not generally profitable to do so. */ vro.intersect (vr0); if (vro.undefined_p ()) return boolean_false_node; vri.intersect (vr0); if (vri.undefined_p ()) return boolean_true_node; } } if ((ret = vrp_evaluate_conditional_warnv_with_ops_using_ranges (code, op0, op1, strict_overflow_p))) return ret; if (only_ranges) *only_ranges = false; /* Do not use compare_names during propagation, it's quadratic. */ if (TREE_CODE (op0) == SSA_NAME && TREE_CODE (op1) == SSA_NAME && use_equiv_p) return compare_names (code, op0, op1, strict_overflow_p); else if (TREE_CODE (op0) == SSA_NAME) return compare_name_with_value (code, op0, op1, strict_overflow_p, use_equiv_p); else if (TREE_CODE (op1) == SSA_NAME) return compare_name_with_value (swap_tree_comparison (code), op1, op0, strict_overflow_p, use_equiv_p); return NULL_TREE; } /* Given (CODE OP0 OP1) within STMT, try to simplify it based on value range information. Return NULL if the conditional cannot be evaluated. The ranges of all the names equivalent with the operands in COND will be used when trying to compute the value. If the result is based on undefined signed overflow, issue a warning if appropriate. */ tree simplify_using_ranges::vrp_evaluate_conditional (tree_code code, tree op0, tree op1, gimple *stmt) { bool sop; tree ret; bool only_ranges; /* Some passes and foldings leak constants with overflow flag set into the IL. Avoid doing wrong things with these and bail out. */ if ((TREE_CODE (op0) == INTEGER_CST && TREE_OVERFLOW (op0)) || (TREE_CODE (op1) == INTEGER_CST && TREE_OVERFLOW (op1))) return NULL_TREE; sop = false; ret = vrp_evaluate_conditional_warnv_with_ops (stmt, code, op0, op1, true, &sop, &only_ranges); if (ret && sop) { enum warn_strict_overflow_code wc; const char* warnmsg; if (is_gimple_min_invariant (ret)) { wc = WARN_STRICT_OVERFLOW_CONDITIONAL; warnmsg = G_("assuming signed overflow does not occur when " "simplifying conditional to constant"); } else { wc = WARN_STRICT_OVERFLOW_COMPARISON; warnmsg = G_("assuming signed overflow does not occur when " "simplifying conditional"); } if (issue_strict_overflow_warning (wc)) { location_t location; if (!gimple_has_location (stmt)) location = input_location; else location = gimple_location (stmt); warning_at (location, OPT_Wstrict_overflow, "%s", warnmsg); } } if (warn_type_limits && ret && only_ranges && TREE_CODE_CLASS (code) == tcc_comparison && TREE_CODE (op0) == SSA_NAME) { /* If the comparison is being folded and the operand on the LHS is being compared against a constant value that is outside of the natural range of OP0's type, then the predicate will always fold regardless of the value of OP0. If -Wtype-limits was specified, emit a warning. */ tree type = TREE_TYPE (op0); const value_range_equiv *vr0 = query->get_value_range (op0, stmt); if (vr0->varying_p () && INTEGRAL_TYPE_P (type) && is_gimple_min_invariant (op1)) { location_t location; if (!gimple_has_location (stmt)) location = input_location; else location = gimple_location (stmt); warning_at (location, OPT_Wtype_limits, integer_zerop (ret) ? G_("comparison always false " "due to limited range of data type") : G_("comparison always true " "due to limited range of data type")); } } return ret; } /* Visit conditional statement STMT. If we can determine which edge will be taken out of STMT's basic block, record it in *TAKEN_EDGE_P. Otherwise, set *TAKEN_EDGE_P to NULL. */ void simplify_using_ranges::vrp_visit_cond_stmt (gcond *stmt, edge *taken_edge_p) { tree val; *taken_edge_p = NULL; if (dump_file && (dump_flags & TDF_DETAILS)) { tree use; ssa_op_iter i; fprintf (dump_file, "\nVisiting conditional with predicate: "); print_gimple_stmt (dump_file, stmt, 0); fprintf (dump_file, "\nWith known ranges\n"); FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE) { fprintf (dump_file, "\t"); print_generic_expr (dump_file, use); fprintf (dump_file, ": "); dump_value_range (dump_file, query->get_value_range (use, stmt)); } fprintf (dump_file, "\n"); } /* Compute the value of the predicate COND by checking the known ranges of each of its operands. Note that we cannot evaluate all the equivalent ranges here because those ranges may not yet be final and with the current propagation strategy, we cannot determine when the value ranges of the names in the equivalence set have changed. For instance, given the following code fragment i_5 = PHI <8, i_13> ... i_14 = ASSERT_EXPR <i_5, i_5 != 0> if (i_14 == 1) ... Assume that on the first visit to i_14, i_5 has the temporary range [8, 8] because the second argument to the PHI function is not yet executable. We derive the range ~[0, 0] for i_14 and the equivalence set { i_5 }. So, when we visit 'if (i_14 == 1)' for the first time, since i_14 is equivalent to the range [8, 8], we determine that the predicate is always false. On the next round of propagation, i_13 is determined to be VARYING, which causes i_5 to drop down to VARYING. So, another visit to i_14 is scheduled. In this second visit, we compute the exact same range and equivalence set for i_14, namely ~[0, 0] and { i_5 }. But we did not have the previous range for i_5 registered, so vrp_visit_assignment thinks that the range for i_14 has not changed. Therefore, the predicate 'if (i_14 == 1)' is not visited again, which stops propagation from visiting statements in the THEN clause of that if(). To properly fix this we would need to keep the previous range value for the names in the equivalence set. This way we would've discovered that from one visit to the other i_5 changed from range [8, 8] to VR_VARYING. However, fixing this apparent limitation may not be worth the additional checking. Testing on several code bases (GCC, DLV, MICO, TRAMP3D and SPEC2000) showed that doing this results in 4 more predicates folded in SPEC. */ bool sop; val = vrp_evaluate_conditional_warnv_with_ops (stmt, gimple_cond_code (stmt), gimple_cond_lhs (stmt), gimple_cond_rhs (stmt), false, &sop, NULL); if (val) *taken_edge_p = find_taken_edge (gimple_bb (stmt), val); if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "\nPredicate evaluates to: "); if (val == NULL_TREE) fprintf (dump_file, "DON'T KNOW\n"); else print_generic_stmt (dump_file, val); } } /* Searches the case label vector VEC for the ranges of CASE_LABELs that are used in range VR. The indices are placed in MIN_IDX1, MAX_IDX, MIN_IDX2 and MAX_IDX2. If the ranges of CASE_LABELs are empty then MAX_IDX1 < MIN_IDX1. Returns true if the default label is not needed. */ static bool find_case_label_ranges (gswitch *stmt, const value_range *vr, size_t *min_idx1, size_t *max_idx1, size_t *min_idx2, size_t *max_idx2) { size_t i, j, k, l; unsigned int n = gimple_switch_num_labels (stmt); bool take_default; tree case_low, case_high; tree min = vr->min (), max = vr->max (); gcc_checking_assert (!vr->varying_p () && !vr->undefined_p ()); take_default = !find_case_label_range (stmt, min, max, &i, &j); /* Set second range to empty. */ *min_idx2 = 1; *max_idx2 = 0; if (vr->kind () == VR_RANGE) { *min_idx1 = i; *max_idx1 = j; return !take_default; } /* Set first range to all case labels. */ *min_idx1 = 1; *max_idx1 = n - 1; if (i > j) return false; /* Make sure all the values of case labels [i , j] are contained in range [MIN, MAX]. */ case_low = CASE_LOW (gimple_switch_label (stmt, i)); case_high = CASE_HIGH (gimple_switch_label (stmt, j)); if (tree_int_cst_compare (case_low, min) < 0) i += 1; if (case_high != NULL_TREE && tree_int_cst_compare (max, case_high) < 0) j -= 1; if (i > j) return false; /* If the range spans case labels [i, j], the corresponding anti-range spans the labels [1, i - 1] and [j + 1, n - 1]. */ k = j + 1; l = n - 1; if (k > l) { k = 1; l = 0; } j = i - 1; i = 1; if (i > j) { i = k; j = l; k = 1; l = 0; } *min_idx1 = i; *max_idx1 = j; *min_idx2 = k; *max_idx2 = l; return false; } /* Visit switch statement STMT. If we can determine which edge will be taken out of STMT's basic block, record it in *TAKEN_EDGE_P. Otherwise, *TAKEN_EDGE_P set to NULL. */ void vr_values::vrp_visit_switch_stmt (gswitch *stmt, edge *taken_edge_p) { tree op, val; const value_range_equiv *vr; size_t i = 0, j = 0, k, l; bool take_default; *taken_edge_p = NULL; op = gimple_switch_index (stmt); if (TREE_CODE (op) != SSA_NAME) return; vr = get_value_range (op); if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "\nVisiting switch expression with operand "); print_generic_expr (dump_file, op); fprintf (dump_file, " with known range "); dump_value_range (dump_file, vr); fprintf (dump_file, "\n"); } if (vr->undefined_p () || vr->varying_p () || vr->symbolic_p ()) return; /* Find the single edge that is taken from the switch expression. */ take_default = !find_case_label_ranges (stmt, vr, &i, &j, &k, &l); /* Check if the range spans no CASE_LABEL. If so, we only reach the default label */ if (j < i) { gcc_assert (take_default); val = gimple_switch_default_label (stmt); } else { /* Check if labels with index i to j and maybe the default label are all reaching the same label. */ val = gimple_switch_label (stmt, i); if (take_default && CASE_LABEL (gimple_switch_default_label (stmt)) != CASE_LABEL (val)) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " not a single destination for this " "range\n"); return; } for (++i; i <= j; ++i) { if (CASE_LABEL (gimple_switch_label (stmt, i)) != CASE_LABEL (val)) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " not a single destination for this " "range\n"); return; } } for (; k <= l; ++k) { if (CASE_LABEL (gimple_switch_label (stmt, k)) != CASE_LABEL (val)) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " not a single destination for this " "range\n"); return; } } } *taken_edge_p = find_edge (gimple_bb (stmt), label_to_block (cfun, CASE_LABEL (val))); if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, " will take edge to "); print_generic_stmt (dump_file, CASE_LABEL (val)); } } /* Evaluate statement STMT. If the statement produces a useful range, set VR and corepsponding OUTPUT_P. If STMT is a conditional branch and we can determine its truth value, the taken edge is recorded in *TAKEN_EDGE_P. */ void vr_values::extract_range_from_stmt (gimple *stmt, edge *taken_edge_p, tree *output_p, value_range_equiv *vr) { if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "\nextract_range_from_stmt visiting:\n"); print_gimple_stmt (dump_file, stmt, 0, dump_flags); } if (!stmt_interesting_for_vrp (stmt)) gcc_assert (stmt_ends_bb_p (stmt)); else if (is_gimple_assign (stmt) || is_gimple_call (stmt)) vrp_visit_assignment_or_call (stmt, output_p, vr); else if (gimple_code (stmt) == GIMPLE_COND) simplifier.vrp_visit_cond_stmt (as_a <gcond *> (stmt), taken_edge_p); else if (gimple_code (stmt) == GIMPLE_SWITCH) vrp_visit_switch_stmt (as_a <gswitch *> (stmt), taken_edge_p); } /* Visit all arguments for PHI node PHI that flow through executable edges. If a valid value range can be derived from all the incoming value ranges, set a new range in VR_RESULT. */ void vr_values::extract_range_from_phi_node (gphi *phi, value_range_equiv *vr_result) { tree lhs = PHI_RESULT (phi); const value_range_equiv *lhs_vr = get_value_range (lhs); bool first = true; int old_edges; class loop *l; if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "\nVisiting PHI node: "); print_gimple_stmt (dump_file, phi, 0, dump_flags); } bool may_simulate_backedge_again = false; int edges = 0; for (size_t i = 0; i < gimple_phi_num_args (phi); i++) { edge e = gimple_phi_arg_edge (phi, i); if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, " Argument #%d (%d -> %d %sexecutable)\n", (int) i, e->src->index, e->dest->index, (e->flags & EDGE_EXECUTABLE) ? "" : "not "); } if (e->flags & EDGE_EXECUTABLE) { value_range_equiv vr_arg_tem; const value_range_equiv *vr_arg = &vr_arg_tem; ++edges; tree arg = PHI_ARG_DEF (phi, i); if (TREE_CODE (arg) == SSA_NAME) { /* See if we are eventually going to change one of the args. */ gimple *def_stmt = SSA_NAME_DEF_STMT (arg); if (! gimple_nop_p (def_stmt) && prop_simulate_again_p (def_stmt) && e->flags & EDGE_DFS_BACK) may_simulate_backedge_again = true; const value_range_equiv *vr_arg_ = get_value_range (arg); /* Do not allow equivalences or symbolic ranges to leak in from backedges. That creates invalid equivalencies. See PR53465 and PR54767. */ if (e->flags & EDGE_DFS_BACK) { if (!vr_arg_->varying_p () && !vr_arg_->undefined_p ()) { vr_arg_tem.set (vr_arg_->min (), vr_arg_->max (), NULL, vr_arg_->kind ()); if (vr_arg_tem.symbolic_p ()) vr_arg_tem.set_varying (TREE_TYPE (arg)); } else vr_arg = vr_arg_; } /* If the non-backedge arguments range is VR_VARYING then we can still try recording a simple equivalence. */ else if (vr_arg_->varying_p ()) vr_arg_tem.set (arg); else vr_arg = vr_arg_; } else { if (TREE_OVERFLOW_P (arg)) arg = drop_tree_overflow (arg); vr_arg_tem.set (arg); } if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "\t"); print_generic_expr (dump_file, arg, dump_flags); fprintf (dump_file, ": "); dump_value_range (dump_file, vr_arg); fprintf (dump_file, "\n"); } if (first) vr_result->deep_copy (vr_arg); else vr_result->union_ (vr_arg); first = false; if (vr_result->varying_p ()) break; } } if (vr_result->varying_p ()) goto varying; else if (vr_result->undefined_p ()) goto update_range; old_edges = vr_phi_edge_counts[SSA_NAME_VERSION (lhs)]; vr_phi_edge_counts[SSA_NAME_VERSION (lhs)] = edges; /* To prevent infinite iterations in the algorithm, derive ranges when the new value is slightly bigger or smaller than the previous one. We don't do this if we have seen a new executable edge; this helps us avoid an infinity for conditionals which are not in a loop. If the old value-range was VR_UNDEFINED use the updated range and iterate one more time. If we will not simulate this PHI again via the backedge allow us to iterate. */ if (edges > 0 && gimple_phi_num_args (phi) > 1 && edges == old_edges && !lhs_vr->undefined_p () && may_simulate_backedge_again) { /* Compare old and new ranges, fall back to varying if the values are not comparable. */ int cmp_min = compare_values (lhs_vr->min (), vr_result->min ()); if (cmp_min == -2) goto varying; int cmp_max = compare_values (lhs_vr->max (), vr_result->max ()); if (cmp_max == -2) goto varying; /* For non VR_RANGE or for pointers fall back to varying if the range changed. */ if ((lhs_vr->kind () != VR_RANGE || vr_result->kind () != VR_RANGE || POINTER_TYPE_P (TREE_TYPE (lhs))) && (cmp_min != 0 || cmp_max != 0)) goto varying; /* If the new minimum is larger than the previous one retain the old value. If the new minimum value is smaller than the previous one and not -INF go all the way to -INF + 1. In the first case, to avoid infinite bouncing between different minimums, and in the other case to avoid iterating millions of times to reach -INF. Going to -INF + 1 also lets the following iteration compute whether there will be any overflow, at the expense of one additional iteration. */ tree new_min = vr_result->min (); tree new_max = vr_result->max (); if (cmp_min < 0) new_min = lhs_vr->min (); else if (cmp_min > 0 && (TREE_CODE (vr_result->min ()) != INTEGER_CST || tree_int_cst_lt (vrp_val_min (vr_result->type ()), vr_result->min ()))) new_min = int_const_binop (PLUS_EXPR, vrp_val_min (vr_result->type ()), build_int_cst (vr_result->type (), 1)); /* Similarly for the maximum value. */ if (cmp_max > 0) new_max = lhs_vr->max (); else if (cmp_max < 0 && (TREE_CODE (vr_result->max ()) != INTEGER_CST || tree_int_cst_lt (vr_result->max (), vrp_val_max (vr_result->type ())))) new_max = int_const_binop (MINUS_EXPR, vrp_val_max (vr_result->type ()), build_int_cst (vr_result->type (), 1)); vr_result->update (new_min, new_max, vr_result->kind ()); /* If we dropped either bound to +-INF then if this is a loop PHI node SCEV may known more about its value-range. */ if (cmp_min > 0 || cmp_min < 0 || cmp_max < 0 || cmp_max > 0) goto scev_check; goto infinite_check; } goto update_range; varying: vr_result->set_varying (TREE_TYPE (lhs)); scev_check: /* If this is a loop PHI node SCEV may known more about its value-range. scev_check can be reached from two paths, one is a fall through from above "varying" label, the other is direct goto from code block which tries to avoid infinite simulation. */ if (scev_initialized_p () && (l = loop_containing_stmt (phi)) && l->header == gimple_bb (phi)) adjust_range_with_scev (vr_result, l, phi, lhs); infinite_check: /* If we will end up with a (-INF, +INF) range, set it to VARYING. Same if the previous max value was invalid for the type and we end up with vr_result.min > vr_result.max. */ if ((!vr_result->varying_p () && !vr_result->undefined_p ()) && !((vrp_val_is_max (vr_result->max ()) && vrp_val_is_min (vr_result->min ())) || compare_values (vr_result->min (), vr_result->max ()) > 0)) ; else vr_result->set_varying (TREE_TYPE (lhs)); /* If the new range is different than the previous value, keep iterating. */ update_range: return; } /* Simplify boolean operations if the source is known to be already a boolean. */ bool simplify_using_ranges::simplify_truth_ops_using_ranges (gimple_stmt_iterator *gsi, gimple *stmt) { enum tree_code rhs_code = gimple_assign_rhs_code (stmt); tree lhs, op0, op1; bool need_conversion; /* We handle only !=/== case here. */ gcc_assert (rhs_code == EQ_EXPR || rhs_code == NE_EXPR); op0 = gimple_assign_rhs1 (stmt); if (!op_with_boolean_value_range_p (op0)) return false; op1 = gimple_assign_rhs2 (stmt); if (!op_with_boolean_value_range_p (op1)) return false; /* Reduce number of cases to handle to NE_EXPR. As there is no BIT_XNOR_EXPR we cannot replace A == B with a single statement. */ if (rhs_code == EQ_EXPR) { if (TREE_CODE (op1) == INTEGER_CST) op1 = int_const_binop (BIT_XOR_EXPR, op1, build_int_cst (TREE_TYPE (op1), 1)); else return false; } lhs = gimple_assign_lhs (stmt); need_conversion = !useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (op0)); /* Make sure to not sign-extend a 1-bit 1 when converting the result. */ if (need_conversion && !TYPE_UNSIGNED (TREE_TYPE (op0)) && TYPE_PRECISION (TREE_TYPE (op0)) == 1 && TYPE_PRECISION (TREE_TYPE (lhs)) > 1) return false; /* For A != 0 we can substitute A itself. */ if (integer_zerop (op1)) gimple_assign_set_rhs_with_ops (gsi, need_conversion ? NOP_EXPR : TREE_CODE (op0), op0); /* For A != B we substitute A ^ B. Either with conversion. */ else if (need_conversion) { tree tem = make_ssa_name (TREE_TYPE (op0)); gassign *newop = gimple_build_assign (tem, BIT_XOR_EXPR, op0, op1); gsi_insert_before (gsi, newop, GSI_SAME_STMT); if (INTEGRAL_TYPE_P (TREE_TYPE (tem)) && TYPE_PRECISION (TREE_TYPE (tem)) > 1) set_range_info (tem, VR_RANGE, wi::zero (TYPE_PRECISION (TREE_TYPE (tem))), wi::one (TYPE_PRECISION (TREE_TYPE (tem)))); gimple_assign_set_rhs_with_ops (gsi, NOP_EXPR, tem); } /* Or without. */ else gimple_assign_set_rhs_with_ops (gsi, BIT_XOR_EXPR, op0, op1); update_stmt (gsi_stmt (*gsi)); fold_stmt (gsi, follow_single_use_edges); return true; } /* Simplify a division or modulo operator to a right shift or bitwise and if the first operand is unsigned or is greater than zero and the second operand is an exact power of two. For TRUNC_MOD_EXPR op0 % op1 with constant op1 (op1min = op1) or with op1 in [op1min, op1max] range, optimize it into just op0 if op0's range is known to be a subset of [-op1min + 1, op1min - 1] for signed and [0, op1min - 1] for unsigned modulo. */ bool simplify_using_ranges::simplify_div_or_mod_using_ranges (gimple_stmt_iterator *gsi, gimple *stmt) { enum tree_code rhs_code = gimple_assign_rhs_code (stmt); tree val = NULL; tree op0 = gimple_assign_rhs1 (stmt); tree op1 = gimple_assign_rhs2 (stmt); tree op0min = NULL_TREE, op0max = NULL_TREE; tree op1min = op1; const value_range *vr = NULL; if (TREE_CODE (op0) == INTEGER_CST) { op0min = op0; op0max = op0; } else { vr = query->get_value_range (op0, stmt); if (range_int_cst_p (vr)) { op0min = vr->min (); op0max = vr->max (); } } if (rhs_code == TRUNC_MOD_EXPR && TREE_CODE (op1) == SSA_NAME) { const value_range_equiv *vr1 = query->get_value_range (op1, stmt); if (range_int_cst_p (vr1)) op1min = vr1->min (); } if (rhs_code == TRUNC_MOD_EXPR && TREE_CODE (op1min) == INTEGER_CST && tree_int_cst_sgn (op1min) == 1 && op0max && tree_int_cst_lt (op0max, op1min)) { if (TYPE_UNSIGNED (TREE_TYPE (op0)) || tree_int_cst_sgn (op0min) >= 0 || tree_int_cst_lt (fold_unary (NEGATE_EXPR, TREE_TYPE (op1min), op1min), op0min)) { /* If op0 already has the range op0 % op1 has, then TRUNC_MOD_EXPR won't change anything. */ gimple_assign_set_rhs_from_tree (gsi, op0); return true; } } if (TREE_CODE (op0) != SSA_NAME) return false; if (!integer_pow2p (op1)) { /* X % -Y can be only optimized into X % Y either if X is not INT_MIN, or Y is not -1. Fold it now, as after remove_range_assertions the range info might be not available anymore. */ if (rhs_code == TRUNC_MOD_EXPR && fold_stmt (gsi, follow_single_use_edges)) return true; return false; } if (TYPE_UNSIGNED (TREE_TYPE (op0))) val = integer_one_node; else { bool sop = false; val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop); if (val && sop && integer_onep (val) && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC)) { location_t location; if (!gimple_has_location (stmt)) location = input_location; else location = gimple_location (stmt); warning_at (location, OPT_Wstrict_overflow, "assuming signed overflow does not occur when " "simplifying %</%> or %<%%%> to %<>>%> or %<&%>"); } } if (val && integer_onep (val)) { tree t; if (rhs_code == TRUNC_DIV_EXPR) { t = build_int_cst (integer_type_node, tree_log2 (op1)); gimple_assign_set_rhs_code (stmt, RSHIFT_EXPR); gimple_assign_set_rhs1 (stmt, op0); gimple_assign_set_rhs2 (stmt, t); } else { t = build_int_cst (TREE_TYPE (op1), 1); t = int_const_binop (MINUS_EXPR, op1, t); t = fold_convert (TREE_TYPE (op0), t); gimple_assign_set_rhs_code (stmt, BIT_AND_EXPR); gimple_assign_set_rhs1 (stmt, op0); gimple_assign_set_rhs2 (stmt, t); } update_stmt (stmt); fold_stmt (gsi, follow_single_use_edges); return true; } return false; } /* Simplify a min or max if the ranges of the two operands are disjoint. Return true if we do simplify. */ bool simplify_using_ranges::simplify_min_or_max_using_ranges (gimple_stmt_iterator *gsi, gimple *stmt) { tree op0 = gimple_assign_rhs1 (stmt); tree op1 = gimple_assign_rhs2 (stmt); bool sop = false; tree val; val = (vrp_evaluate_conditional_warnv_with_ops_using_ranges (LE_EXPR, op0, op1, &sop)); if (!val) { sop = false; val = (vrp_evaluate_conditional_warnv_with_ops_using_ranges (LT_EXPR, op0, op1, &sop)); } if (val) { if (sop && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC)) { location_t location; if (!gimple_has_location (stmt)) location = input_location; else location = gimple_location (stmt); warning_at (location, OPT_Wstrict_overflow, "assuming signed overflow does not occur when " "simplifying %<min/max (X,Y)%> to %<X%> or %<Y%>"); } /* VAL == TRUE -> OP0 < or <= op1 VAL == FALSE -> OP0 > or >= op1. */ tree res = ((gimple_assign_rhs_code (stmt) == MAX_EXPR) == integer_zerop (val)) ? op0 : op1; gimple_assign_set_rhs_from_tree (gsi, res); return true; } return false; } /* If the operand to an ABS_EXPR is >= 0, then eliminate the ABS_EXPR. If the operand is <= 0, then simplify the ABS_EXPR into a NEGATE_EXPR. */ bool simplify_using_ranges::simplify_abs_using_ranges (gimple_stmt_iterator *gsi, gimple *stmt) { tree op = gimple_assign_rhs1 (stmt); const value_range *vr = query->get_value_range (op, stmt); if (vr) { tree val = NULL; bool sop = false; val = compare_range_with_value (LE_EXPR, vr, integer_zero_node, &sop); if (!val) { /* The range is neither <= 0 nor > 0. Now see if it is either < 0 or >= 0. */ sop = false; val = compare_range_with_value (LT_EXPR, vr, integer_zero_node, &sop); } if (val) { if (sop && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC)) { location_t location; if (!gimple_has_location (stmt)) location = input_location; else location = gimple_location (stmt); warning_at (location, OPT_Wstrict_overflow, "assuming signed overflow does not occur when " "simplifying %<abs (X)%> to %<X%> or %<-X%>"); } gimple_assign_set_rhs1 (stmt, op); if (integer_zerop (val)) gimple_assign_set_rhs_code (stmt, SSA_NAME); else gimple_assign_set_rhs_code (stmt, NEGATE_EXPR); update_stmt (stmt); fold_stmt (gsi, follow_single_use_edges); return true; } } return false; } /* value_range wrapper for wi_set_zero_nonzero_bits. Return TRUE if VR was a constant range and we were able to compute the bit masks. */ static bool vr_set_zero_nonzero_bits (const tree expr_type, const value_range *vr, wide_int *may_be_nonzero, wide_int *must_be_nonzero) { if (range_int_cst_p (vr)) { wi_set_zero_nonzero_bits (expr_type, wi::to_wide (vr->min ()), wi::to_wide (vr->max ()), *may_be_nonzero, *must_be_nonzero); return true; } *may_be_nonzero = wi::minus_one (TYPE_PRECISION (expr_type)); *must_be_nonzero = wi::zero (TYPE_PRECISION (expr_type)); return false; } /* Optimize away redundant BIT_AND_EXPR and BIT_IOR_EXPR. If all the bits that are being cleared by & are already known to be zero from VR, or all the bits that are being set by | are already known to be one from VR, the bit operation is redundant. */ bool simplify_using_ranges::simplify_bit_ops_using_ranges (gimple_stmt_iterator *gsi, gimple *stmt) { tree op0 = gimple_assign_rhs1 (stmt); tree op1 = gimple_assign_rhs2 (stmt); tree op = NULL_TREE; value_range vr0, vr1; wide_int may_be_nonzero0, may_be_nonzero1; wide_int must_be_nonzero0, must_be_nonzero1; wide_int mask; if (TREE_CODE (op0) == SSA_NAME) vr0 = *(query->get_value_range (op0, stmt)); else if (is_gimple_min_invariant (op0)) vr0.set (op0); else return false; if (TREE_CODE (op1) == SSA_NAME) vr1 = *(query->get_value_range (op1, stmt)); else if (is_gimple_min_invariant (op1)) vr1.set (op1); else return false; if (!vr_set_zero_nonzero_bits (TREE_TYPE (op0), &vr0, &may_be_nonzero0, &must_be_nonzero0)) return false; if (!vr_set_zero_nonzero_bits (TREE_TYPE (op1), &vr1, &may_be_nonzero1, &must_be_nonzero1)) return false; switch (gimple_assign_rhs_code (stmt)) { case BIT_AND_EXPR: mask = wi::bit_and_not (may_be_nonzero0, must_be_nonzero1); if (mask == 0) { op = op0; break; } mask = wi::bit_and_not (may_be_nonzero1, must_be_nonzero0); if (mask == 0) { op = op1; break; } break; case BIT_IOR_EXPR: mask = wi::bit_and_not (may_be_nonzero0, must_be_nonzero1); if (mask == 0) { op = op1; break; } mask = wi::bit_and_not (may_be_nonzero1, must_be_nonzero0); if (mask == 0) { op = op0; break; } break; default: gcc_unreachable (); } if (op == NULL_TREE) return false; gimple_assign_set_rhs_with_ops (gsi, TREE_CODE (op), op); update_stmt (gsi_stmt (*gsi)); return true; } /* We are comparing trees OP0 and OP1 using COND_CODE. OP0 has a known value range VR. If there is one and only one value which will satisfy the conditional, then return that value. Else return NULL. If signed overflow must be undefined for the value to satisfy the conditional, then set *STRICT_OVERFLOW_P to true. */ static tree test_for_singularity (enum tree_code cond_code, tree op0, tree op1, const value_range *vr) { tree min = NULL; tree max = NULL; /* Extract minimum/maximum values which satisfy the conditional as it was written. */ if (cond_code == LE_EXPR || cond_code == LT_EXPR) { min = TYPE_MIN_VALUE (TREE_TYPE (op0)); max = op1; if (cond_code == LT_EXPR) { tree one = build_int_cst (TREE_TYPE (op0), 1); max = fold_build2 (MINUS_EXPR, TREE_TYPE (op0), max, one); /* Signal to compare_values_warnv this expr doesn't overflow. */ if (EXPR_P (max)) TREE_NO_WARNING (max) = 1; } } else if (cond_code == GE_EXPR || cond_code == GT_EXPR) { max = TYPE_MAX_VALUE (TREE_TYPE (op0)); min = op1; if (cond_code == GT_EXPR) { tree one = build_int_cst (TREE_TYPE (op0), 1); min = fold_build2 (PLUS_EXPR, TREE_TYPE (op0), min, one); /* Signal to compare_values_warnv this expr doesn't overflow. */ if (EXPR_P (min)) TREE_NO_WARNING (min) = 1; } } /* Now refine the minimum and maximum values using any value range information we have for op0. */ if (min && max) { tree type = TREE_TYPE (op0); tree tmin = wide_int_to_tree (type, vr->lower_bound ()); tree tmax = wide_int_to_tree (type, vr->upper_bound ()); if (compare_values (tmin, min) == 1) min = tmin; if (compare_values (tmax, max) == -1) max = tmax; /* If the new min/max values have converged to a single value, then there is only one value which can satisfy the condition, return that value. */ if (operand_equal_p (min, max, 0) && is_gimple_min_invariant (min)) return min; } return NULL; } /* Return whether the value range *VR fits in an integer type specified by PRECISION and UNSIGNED_P. */ bool range_fits_type_p (const value_range *vr, unsigned dest_precision, signop dest_sgn) { tree src_type; unsigned src_precision; widest_int tem; signop src_sgn; /* We can only handle integral and pointer types. */ src_type = vr->type (); if (!INTEGRAL_TYPE_P (src_type) && !POINTER_TYPE_P (src_type)) return false; /* An extension is fine unless VR is SIGNED and dest_sgn is UNSIGNED, and so is an identity transform. */ src_precision = TYPE_PRECISION (vr->type ()); src_sgn = TYPE_SIGN (src_type); if ((src_precision < dest_precision && !(dest_sgn == UNSIGNED && src_sgn == SIGNED)) || (src_precision == dest_precision && src_sgn == dest_sgn)) return true; /* Now we can only handle ranges with constant bounds. */ if (!range_int_cst_p (vr)) return false; /* For sign changes, the MSB of the wide_int has to be clear. An unsigned value with its MSB set cannot be represented by a signed wide_int, while a negative value cannot be represented by an unsigned wide_int. */ if (src_sgn != dest_sgn && (wi::lts_p (wi::to_wide (vr->min ()), 0) || wi::lts_p (wi::to_wide (vr->max ()), 0))) return false; /* Then we can perform the conversion on both ends and compare the result for equality. */ tem = wi::ext (wi::to_widest (vr->min ()), dest_precision, dest_sgn); if (tem != wi::to_widest (vr->min ())) return false; tem = wi::ext (wi::to_widest (vr->max ()), dest_precision, dest_sgn); if (tem != wi::to_widest (vr->max ())) return false; return true; } /* If COND can be folded entirely as TRUE or FALSE, rewrite the conditional as such, and return TRUE. */ bool simplify_using_ranges::fold_cond (gcond *cond) { /* ?? vrp_folder::fold_predicate_in() is a superset of this. At some point we should merge all variants of this code. */ edge taken_edge; vrp_visit_cond_stmt (cond, &taken_edge); int_range_max r; if (query->range_of_stmt (r, cond) && r.singleton_p ()) { // COND has already been folded if arguments are constant. if (TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME && TREE_CODE (gimple_cond_rhs (cond)) != SSA_NAME) return false; if (r.zero_p ()) { gcc_checking_assert (!taken_edge || taken_edge->flags & EDGE_FALSE_VALUE); if (dump_file && (dump_flags & TDF_DETAILS) && !taken_edge) fprintf (dump_file, "\nPredicate evaluates to: 0\n"); gimple_cond_make_false (cond); } else { gcc_checking_assert (!taken_edge || taken_edge->flags & EDGE_TRUE_VALUE); if (dump_file && (dump_flags & TDF_DETAILS) && !taken_edge) fprintf (dump_file, "\nPredicate evaluates to: 1\n"); gimple_cond_make_true (cond); } update_stmt (cond); return true; } if (taken_edge) { if (taken_edge->flags & EDGE_TRUE_VALUE) gimple_cond_make_true (cond); else if (taken_edge->flags & EDGE_FALSE_VALUE) gimple_cond_make_false (cond); else gcc_unreachable (); update_stmt (cond); return true; } return false; } /* Simplify a conditional using a relational operator to an equality test if the range information indicates only one value can satisfy the original conditional. */ bool simplify_using_ranges::simplify_cond_using_ranges_1 (gcond *stmt) { tree op0 = gimple_cond_lhs (stmt); tree op1 = gimple_cond_rhs (stmt); enum tree_code cond_code = gimple_cond_code (stmt); if (fold_cond (stmt)) return true; if (cond_code != NE_EXPR && cond_code != EQ_EXPR && TREE_CODE (op0) == SSA_NAME && INTEGRAL_TYPE_P (TREE_TYPE (op0)) && is_gimple_min_invariant (op1)) { const value_range *vr = query->get_value_range (op0, stmt); /* If we have range information for OP0, then we might be able to simplify this conditional. */ if (!vr->undefined_p () && !vr->varying_p ()) { tree new_tree = test_for_singularity (cond_code, op0, op1, vr); if (new_tree) { if (dump_file) { fprintf (dump_file, "Simplified relational "); print_gimple_stmt (dump_file, stmt, 0); fprintf (dump_file, " into "); } gimple_cond_set_code (stmt, EQ_EXPR); gimple_cond_set_lhs (stmt, op0); gimple_cond_set_rhs (stmt, new_tree); update_stmt (stmt); if (dump_file) { print_gimple_stmt (dump_file, stmt, 0); fprintf (dump_file, "\n"); } return true; } /* Try again after inverting the condition. We only deal with integral types here, so no need to worry about issues with inverting FP comparisons. */ new_tree = test_for_singularity (invert_tree_comparison (cond_code, false), op0, op1, vr); if (new_tree) { if (dump_file) { fprintf (dump_file, "Simplified relational "); print_gimple_stmt (dump_file, stmt, 0); fprintf (dump_file, " into "); } gimple_cond_set_code (stmt, NE_EXPR); gimple_cond_set_lhs (stmt, op0); gimple_cond_set_rhs (stmt, new_tree); update_stmt (stmt); if (dump_file) { print_gimple_stmt (dump_file, stmt, 0); fprintf (dump_file, "\n"); } return true; } } } return false; } /* Simplify a switch statement using the value range of the switch argument. */ bool simplify_using_ranges::simplify_switch_using_ranges (gswitch *stmt) { tree op = gimple_switch_index (stmt); const value_range *vr = NULL; bool take_default; edge e; edge_iterator ei; size_t i = 0, j = 0, n, n2; tree vec2; switch_update su; size_t k = 1, l = 0; if (TREE_CODE (op) == SSA_NAME) { vr = query->get_value_range (op, stmt); /* We can only handle integer ranges. */ if (vr->varying_p () || vr->undefined_p () || vr->symbolic_p ()) return false; /* Find case label for min/max of the value range. */ take_default = !find_case_label_ranges (stmt, vr, &i, &j, &k, &l); } else if (TREE_CODE (op) == INTEGER_CST) { take_default = !find_case_label_index (stmt, 1, op, &i); if (take_default) { i = 1; j = 0; } else { j = i; } } else return false; n = gimple_switch_num_labels (stmt); /* We can truncate the case label ranges that partially overlap with OP's value range. */ size_t min_idx = 1, max_idx = 0; if (vr != NULL) find_case_label_range (stmt, vr->min (), vr->max (), &min_idx, &max_idx); if (min_idx <= max_idx) { tree min_label = gimple_switch_label (stmt, min_idx); tree max_label = gimple_switch_label (stmt, max_idx); /* Avoid changing the type of the case labels when truncating. */ tree case_label_type = TREE_TYPE (CASE_LOW (min_label)); tree vr_min = fold_convert (case_label_type, vr->min ()); tree vr_max = fold_convert (case_label_type, vr->max ()); if (vr->kind () == VR_RANGE) { /* If OP's value range is [2,8] and the low label range is 0 ... 3, truncate the label's range to 2 .. 3. */ if (tree_int_cst_compare (CASE_LOW (min_label), vr_min) < 0 && CASE_HIGH (min_label) != NULL_TREE && tree_int_cst_compare (CASE_HIGH (min_label), vr_min) >= 0) CASE_LOW (min_label) = vr_min; /* If OP's value range is [2,8] and the high label range is 7 ... 10, truncate the label's range to 7 .. 8. */ if (tree_int_cst_compare (CASE_LOW (max_label), vr_max) <= 0 && CASE_HIGH (max_label) != NULL_TREE && tree_int_cst_compare (CASE_HIGH (max_label), vr_max) > 0) CASE_HIGH (max_label) = vr_max; } else if (vr->kind () == VR_ANTI_RANGE) { tree one_cst = build_one_cst (case_label_type); if (min_label == max_label) { /* If OP's value range is ~[7,8] and the label's range is 7 ... 10, truncate the label's range to 9 ... 10. */ if (tree_int_cst_compare (CASE_LOW (min_label), vr_min) == 0 && CASE_HIGH (min_label) != NULL_TREE && tree_int_cst_compare (CASE_HIGH (min_label), vr_max) > 0) CASE_LOW (min_label) = int_const_binop (PLUS_EXPR, vr_max, one_cst); /* If OP's value range is ~[7,8] and the label's range is 5 ... 8, truncate the label's range to 5 ... 6. */ if (tree_int_cst_compare (CASE_LOW (min_label), vr_min) < 0 && CASE_HIGH (min_label) != NULL_TREE && tree_int_cst_compare (CASE_HIGH (min_label), vr_max) == 0) CASE_HIGH (min_label) = int_const_binop (MINUS_EXPR, vr_min, one_cst); } else { /* If OP's value range is ~[2,8] and the low label range is 0 ... 3, truncate the label's range to 0 ... 1. */ if (tree_int_cst_compare (CASE_LOW (min_label), vr_min) < 0 && CASE_HIGH (min_label) != NULL_TREE && tree_int_cst_compare (CASE_HIGH (min_label), vr_min) >= 0) CASE_HIGH (min_label) = int_const_binop (MINUS_EXPR, vr_min, one_cst); /* If OP's value range is ~[2,8] and the high label range is 7 ... 10, truncate the label's range to 9 ... 10. */ if (tree_int_cst_compare (CASE_LOW (max_label), vr_max) <= 0 && CASE_HIGH (max_label) != NULL_TREE && tree_int_cst_compare (CASE_HIGH (max_label), vr_max) > 0) CASE_LOW (max_label) = int_const_binop (PLUS_EXPR, vr_max, one_cst); } } /* Canonicalize singleton case ranges. */ if (tree_int_cst_equal (CASE_LOW (min_label), CASE_HIGH (min_label))) CASE_HIGH (min_label) = NULL_TREE; if (tree_int_cst_equal (CASE_LOW (max_label), CASE_HIGH (max_label))) CASE_HIGH (max_label) = NULL_TREE; } /* We can also eliminate case labels that lie completely outside OP's value range. */ /* Bail out if this is just all edges taken. */ if (i == 1 && j == n - 1 && take_default) return false; /* Build a new vector of taken case labels. */ vec2 = make_tree_vec (j - i + 1 + l - k + 1 + (int)take_default); n2 = 0; /* Add the default edge, if necessary. */ if (take_default) TREE_VEC_ELT (vec2, n2++) = gimple_switch_default_label (stmt); for (; i <= j; ++i, ++n2) TREE_VEC_ELT (vec2, n2) = gimple_switch_label (stmt, i); for (; k <= l; ++k, ++n2) TREE_VEC_ELT (vec2, n2) = gimple_switch_label (stmt, k); /* Mark needed edges. */ for (i = 0; i < n2; ++i) { e = find_edge (gimple_bb (stmt), label_to_block (cfun, CASE_LABEL (TREE_VEC_ELT (vec2, i)))); e->aux = (void *)-1; } /* Queue not needed edges for later removal. */ FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->succs) { if (e->aux == (void *)-1) { e->aux = NULL; continue; } if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "removing unreachable case label\n"); } to_remove_edges.safe_push (e); e->flags &= ~EDGE_EXECUTABLE; e->flags |= EDGE_IGNORE; } /* And queue an update for the stmt. */ su.stmt = stmt; su.vec = vec2; to_update_switch_stmts.safe_push (su); return true; } void simplify_using_ranges::cleanup_edges_and_switches (void) { int i; edge e; switch_update *su; /* Remove dead edges from SWITCH_EXPR optimization. This leaves the CFG in a broken state and requires a cfg_cleanup run. */ FOR_EACH_VEC_ELT (to_remove_edges, i, e) remove_edge (e); /* Update SWITCH_EXPR case label vector. */ FOR_EACH_VEC_ELT (to_update_switch_stmts, i, su) { size_t j; size_t n = TREE_VEC_LENGTH (su->vec); tree label; gimple_switch_set_num_labels (su->stmt, n); for (j = 0; j < n; j++) gimple_switch_set_label (su->stmt, j, TREE_VEC_ELT (su->vec, j)); /* As we may have replaced the default label with a regular one make sure to make it a real default label again. This ensures optimal expansion. */ label = gimple_switch_label (su->stmt, 0); CASE_LOW (label) = NULL_TREE; CASE_HIGH (label) = NULL_TREE; } if (!to_remove_edges.is_empty ()) { free_dominance_info (CDI_DOMINATORS); loops_state_set (LOOPS_NEED_FIXUP); } to_remove_edges.release (); to_update_switch_stmts.release (); } /* Simplify an integral conversion from an SSA name in STMT. */ static bool simplify_conversion_using_ranges (gimple_stmt_iterator *gsi, gimple *stmt) { tree innerop, middleop, finaltype; gimple *def_stmt; signop inner_sgn, middle_sgn, final_sgn; unsigned inner_prec, middle_prec, final_prec; widest_int innermin, innermed, innermax, middlemin, middlemed, middlemax; finaltype = TREE_TYPE (gimple_assign_lhs (stmt)); if (!INTEGRAL_TYPE_P (finaltype)) return false; middleop = gimple_assign_rhs1 (stmt); def_stmt = SSA_NAME_DEF_STMT (middleop); if (!is_gimple_assign (def_stmt) || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt))) return false; innerop = gimple_assign_rhs1 (def_stmt); if (TREE_CODE (innerop) != SSA_NAME || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (innerop)) return false; /* Get the value-range of the inner operand. Use get_range_info in case innerop was created during substitute-and-fold. */ wide_int imin, imax; value_range vr; if (!INTEGRAL_TYPE_P (TREE_TYPE (innerop))) return false; get_range_info (innerop, vr); if (vr.undefined_p () || vr.varying_p ()) return false; innermin = widest_int::from (vr.lower_bound (), TYPE_SIGN (TREE_TYPE (innerop))); innermax = widest_int::from (vr.upper_bound (), TYPE_SIGN (TREE_TYPE (innerop))); /* Simulate the conversion chain to check if the result is equal if the middle conversion is removed. */ inner_prec = TYPE_PRECISION (TREE_TYPE (innerop)); middle_prec = TYPE_PRECISION (TREE_TYPE (middleop)); final_prec = TYPE_PRECISION (finaltype); /* If the first conversion is not injective, the second must not be widening. */ if (wi::gtu_p (innermax - innermin, wi::mask <widest_int> (middle_prec, false)) && middle_prec < final_prec) return false; /* We also want a medium value so that we can track the effect that narrowing conversions with sign change have. */ inner_sgn = TYPE_SIGN (TREE_TYPE (innerop)); if (inner_sgn == UNSIGNED) innermed = wi::shifted_mask <widest_int> (1, inner_prec - 1, false); else innermed = 0; if (wi::cmp (innermin, innermed, inner_sgn) >= 0 || wi::cmp (innermed, innermax, inner_sgn) >= 0) innermed = innermin; middle_sgn = TYPE_SIGN (TREE_TYPE (middleop)); middlemin = wi::ext (innermin, middle_prec, middle_sgn); middlemed = wi::ext (innermed, middle_prec, middle_sgn); middlemax = wi::ext (innermax, middle_prec, middle_sgn); /* Require that the final conversion applied to both the original and the intermediate range produces the same result. */ final_sgn = TYPE_SIGN (finaltype); if (wi::ext (middlemin, final_prec, final_sgn) != wi::ext (innermin, final_prec, final_sgn) || wi::ext (middlemed, final_prec, final_sgn) != wi::ext (innermed, final_prec, final_sgn) || wi::ext (middlemax, final_prec, final_sgn) != wi::ext (innermax, final_prec, final_sgn)) return false; gimple_assign_set_rhs1 (stmt, innerop); fold_stmt (gsi, follow_single_use_edges); return true; } /* Simplify a conversion from integral SSA name to float in STMT. */ bool simplify_using_ranges::simplify_float_conversion_using_ranges (gimple_stmt_iterator *gsi, gimple *stmt) { tree rhs1 = gimple_assign_rhs1 (stmt); const value_range *vr = query->get_value_range (rhs1, stmt); scalar_float_mode fltmode = SCALAR_FLOAT_TYPE_MODE (TREE_TYPE (gimple_assign_lhs (stmt))); scalar_int_mode mode; tree tem; gassign *conv; /* We can only handle constant ranges. */ if (!range_int_cst_p (vr)) return false; /* First check if we can use a signed type in place of an unsigned. */ scalar_int_mode rhs_mode = SCALAR_INT_TYPE_MODE (TREE_TYPE (rhs1)); if (TYPE_UNSIGNED (TREE_TYPE (rhs1)) && can_float_p (fltmode, rhs_mode, 0) != CODE_FOR_nothing && range_fits_type_p (vr, TYPE_PRECISION (TREE_TYPE (rhs1)), SIGNED)) mode = rhs_mode; /* If we can do the conversion in the current input mode do nothing. */ else if (can_float_p (fltmode, rhs_mode, TYPE_UNSIGNED (TREE_TYPE (rhs1))) != CODE_FOR_nothing) return false; /* Otherwise search for a mode we can use, starting from the narrowest integer mode available. */ else { mode = NARROWEST_INT_MODE; for (;;) { /* If we cannot do a signed conversion to float from mode or if the value-range does not fit in the signed type try with a wider mode. */ if (can_float_p (fltmode, mode, 0) != CODE_FOR_nothing && range_fits_type_p (vr, GET_MODE_PRECISION (mode), SIGNED)) break; /* But do not widen the input. Instead leave that to the optabs expansion code. */ if (!GET_MODE_WIDER_MODE (mode).exists (&mode) || GET_MODE_PRECISION (mode) > TYPE_PRECISION (TREE_TYPE (rhs1))) return false; } } /* It works, insert a truncation or sign-change before the float conversion. */ tem = make_ssa_name (build_nonstandard_integer_type (GET_MODE_PRECISION (mode), 0)); conv = gimple_build_assign (tem, NOP_EXPR, rhs1); gsi_insert_before (gsi, conv, GSI_SAME_STMT); gimple_assign_set_rhs1 (stmt, tem); fold_stmt (gsi, follow_single_use_edges); return true; } /* Simplify an internal fn call using ranges if possible. */ bool simplify_using_ranges::simplify_internal_call_using_ranges (gimple_stmt_iterator *gsi, gimple *stmt) { enum tree_code subcode; bool is_ubsan = false; bool ovf = false; switch (gimple_call_internal_fn (stmt)) { case IFN_UBSAN_CHECK_ADD: subcode = PLUS_EXPR; is_ubsan = true; break; case IFN_UBSAN_CHECK_SUB: subcode = MINUS_EXPR; is_ubsan = true; break; case IFN_UBSAN_CHECK_MUL: subcode = MULT_EXPR; is_ubsan = true; break; case IFN_ADD_OVERFLOW: subcode = PLUS_EXPR; break; case IFN_SUB_OVERFLOW: subcode = MINUS_EXPR; break; case IFN_MUL_OVERFLOW: subcode = MULT_EXPR; break; default: return false; } tree op0 = gimple_call_arg (stmt, 0); tree op1 = gimple_call_arg (stmt, 1); tree type; if (is_ubsan) { type = TREE_TYPE (op0); if (VECTOR_TYPE_P (type)) return false; } else if (gimple_call_lhs (stmt) == NULL_TREE) return false; else type = TREE_TYPE (TREE_TYPE (gimple_call_lhs (stmt))); if (!check_for_binary_op_overflow (query, subcode, type, op0, op1, &ovf) || (is_ubsan && ovf)) return false; gimple *g; location_t loc = gimple_location (stmt); if (is_ubsan) g = gimple_build_assign (gimple_call_lhs (stmt), subcode, op0, op1); else { int prec = TYPE_PRECISION (type); tree utype = type; if (ovf || !useless_type_conversion_p (type, TREE_TYPE (op0)) || !useless_type_conversion_p (type, TREE_TYPE (op1))) utype = build_nonstandard_integer_type (prec, 1); if (TREE_CODE (op0) == INTEGER_CST) op0 = fold_convert (utype, op0); else if (!useless_type_conversion_p (utype, TREE_TYPE (op0))) { g = gimple_build_assign (make_ssa_name (utype), NOP_EXPR, op0); gimple_set_location (g, loc); gsi_insert_before (gsi, g, GSI_SAME_STMT); op0 = gimple_assign_lhs (g); } if (TREE_CODE (op1) == INTEGER_CST) op1 = fold_convert (utype, op1); else if (!useless_type_conversion_p (utype, TREE_TYPE (op1))) { g = gimple_build_assign (make_ssa_name (utype), NOP_EXPR, op1); gimple_set_location (g, loc); gsi_insert_before (gsi, g, GSI_SAME_STMT); op1 = gimple_assign_lhs (g); } g = gimple_build_assign (make_ssa_name (utype), subcode, op0, op1); gimple_set_location (g, loc); gsi_insert_before (gsi, g, GSI_SAME_STMT); if (utype != type) { g = gimple_build_assign (make_ssa_name (type), NOP_EXPR, gimple_assign_lhs (g)); gimple_set_location (g, loc); gsi_insert_before (gsi, g, GSI_SAME_STMT); } g = gimple_build_assign (gimple_call_lhs (stmt), COMPLEX_EXPR, gimple_assign_lhs (g), build_int_cst (type, ovf)); } gimple_set_location (g, loc); gsi_replace (gsi, g, false); return true; } /* Return true if VAR is a two-valued variable. Set a and b with the two-values when it is true. Return false otherwise. */ bool simplify_using_ranges::two_valued_val_range_p (tree var, tree *a, tree *b) { value_range vr = *query->get_value_range (var); vr.normalize_symbolics (); if (vr.varying_p () || vr.undefined_p ()) return false; if ((vr.num_pairs () == 1 && vr.upper_bound () - vr.lower_bound () == 1) || (vr.num_pairs () == 2 && vr.lower_bound (0) == vr.upper_bound (0) && vr.lower_bound (1) == vr.upper_bound (1))) { *a = wide_int_to_tree (TREE_TYPE (var), vr.lower_bound ()); *b = wide_int_to_tree (TREE_TYPE (var), vr.upper_bound ()); return true; } return false; } simplify_using_ranges::simplify_using_ranges (range_query *query) : query (query) { to_remove_edges = vNULL; to_update_switch_stmts = vNULL; } simplify_using_ranges::~simplify_using_ranges () { cleanup_edges_and_switches (); } /* Simplify STMT using ranges if possible. */ bool simplify_using_ranges::simplify (gimple_stmt_iterator *gsi) { gcc_checking_assert (query); gimple *stmt = gsi_stmt (*gsi); if (is_gimple_assign (stmt)) { enum tree_code rhs_code = gimple_assign_rhs_code (stmt); tree rhs1 = gimple_assign_rhs1 (stmt); tree rhs2 = gimple_assign_rhs2 (stmt); tree lhs = gimple_assign_lhs (stmt); tree val1 = NULL_TREE, val2 = NULL_TREE; use_operand_p use_p; gimple *use_stmt; /* Convert: LHS = CST BINOP VAR Where VAR is two-valued and LHS is used in GIMPLE_COND only To: LHS = VAR == VAL1 ? (CST BINOP VAL1) : (CST BINOP VAL2) Also handles: LHS = VAR BINOP CST Where VAR is two-valued and LHS is used in GIMPLE_COND only To: LHS = VAR == VAL1 ? (VAL1 BINOP CST) : (VAL2 BINOP CST) */ if (TREE_CODE_CLASS (rhs_code) == tcc_binary && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)) && ((TREE_CODE (rhs1) == INTEGER_CST && TREE_CODE (rhs2) == SSA_NAME) || (TREE_CODE (rhs2) == INTEGER_CST && TREE_CODE (rhs1) == SSA_NAME)) && single_imm_use (lhs, &use_p, &use_stmt) && gimple_code (use_stmt) == GIMPLE_COND) { tree new_rhs1 = NULL_TREE; tree new_rhs2 = NULL_TREE; tree cmp_var = NULL_TREE; if (TREE_CODE (rhs2) == SSA_NAME && two_valued_val_range_p (rhs2, &val1, &val2)) { /* Optimize RHS1 OP [VAL1, VAL2]. */ new_rhs1 = int_const_binop (rhs_code, rhs1, val1); new_rhs2 = int_const_binop (rhs_code, rhs1, val2); cmp_var = rhs2; } else if (TREE_CODE (rhs1) == SSA_NAME && two_valued_val_range_p (rhs1, &val1, &val2)) { /* Optimize [VAL1, VAL2] OP RHS2. */ new_rhs1 = int_const_binop (rhs_code, val1, rhs2); new_rhs2 = int_const_binop (rhs_code, val2, rhs2); cmp_var = rhs1; } /* If we could not find two-vals or the optimzation is invalid as in divide by zero, new_rhs1 / new_rhs will be NULL_TREE. */ if (new_rhs1 && new_rhs2) { tree cond = build2 (EQ_EXPR, boolean_type_node, cmp_var, val1); gimple_assign_set_rhs_with_ops (gsi, COND_EXPR, cond, new_rhs1, new_rhs2); update_stmt (gsi_stmt (*gsi)); fold_stmt (gsi, follow_single_use_edges); return true; } } switch (rhs_code) { case EQ_EXPR: case NE_EXPR: /* Transform EQ_EXPR, NE_EXPR into BIT_XOR_EXPR or identity if the RHS is zero or one, and the LHS are known to be boolean values. */ if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1))) return simplify_truth_ops_using_ranges (gsi, stmt); break; /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR and BIT_AND_EXPR respectively if the first operand is greater than zero and the second operand is an exact power of two. Also optimize TRUNC_MOD_EXPR away if the second operand is constant and the first operand already has the right value range. */ case TRUNC_DIV_EXPR: case TRUNC_MOD_EXPR: if ((TREE_CODE (rhs1) == SSA_NAME || TREE_CODE (rhs1) == INTEGER_CST) && INTEGRAL_TYPE_P (TREE_TYPE (rhs1))) return simplify_div_or_mod_using_ranges (gsi, stmt); break; /* Transform ABS (X) into X or -X as appropriate. */ case ABS_EXPR: if (TREE_CODE (rhs1) == SSA_NAME && INTEGRAL_TYPE_P (TREE_TYPE (rhs1))) return simplify_abs_using_ranges (gsi, stmt); break; case BIT_AND_EXPR: case BIT_IOR_EXPR: /* Optimize away BIT_AND_EXPR and BIT_IOR_EXPR if all the bits being cleared are already cleared or all the bits being set are already set. */ if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1))) return simplify_bit_ops_using_ranges (gsi, stmt); break; CASE_CONVERT: if (TREE_CODE (rhs1) == SSA_NAME && INTEGRAL_TYPE_P (TREE_TYPE (rhs1))) return simplify_conversion_using_ranges (gsi, stmt); break; case FLOAT_EXPR: if (TREE_CODE (rhs1) == SSA_NAME && INTEGRAL_TYPE_P (TREE_TYPE (rhs1))) return simplify_float_conversion_using_ranges (gsi, stmt); break; case MIN_EXPR: case MAX_EXPR: return simplify_min_or_max_using_ranges (gsi, stmt); default: break; } } else if (gimple_code (stmt) == GIMPLE_COND) return simplify_cond_using_ranges_1 (as_a <gcond *> (stmt)); else if (gimple_code (stmt) == GIMPLE_SWITCH) return simplify_switch_using_ranges (as_a <gswitch *> (stmt)); else if (is_gimple_call (stmt) && gimple_call_internal_p (stmt)) return simplify_internal_call_using_ranges (gsi, stmt); return false; } /* Set the lattice entry for VAR to VR. */ void vr_values::set_vr_value (tree var, value_range_equiv *vr) { if (SSA_NAME_VERSION (var) >= num_vr_values) return; vr_value[SSA_NAME_VERSION (var)] = vr; } /* Swap the lattice entry for VAR with VR and return the old entry. */ value_range_equiv * vr_values::swap_vr_value (tree var, value_range_equiv *vr) { if (SSA_NAME_VERSION (var) >= num_vr_values) return NULL; std::swap (vr_value[SSA_NAME_VERSION (var)], vr); return vr; }