aboutsummaryrefslogtreecommitdiff
path: root/bfd/pei-x86_64.c
blob: d95144246008d0e56c0c650ca3567337f800e2ad (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
/* BFD back-end for Intel 386 PE IMAGE COFF files.
   Copyright (C) 2006-2015 Free Software Foundation, Inc.

   This file is part of BFD, the Binary File Descriptor library.

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 3 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,
   MA 02110-1301, USA.

   Written by Kai Tietz, OneVision Software GmbH&CoKg.  */

#include "sysdep.h"
#include "bfd.h"

#define TARGET_SYM 		x86_64_pei_vec
#define TARGET_NAME 		"pei-x86-64"
#define COFF_IMAGE_WITH_PE
#define COFF_WITH_PE
#define COFF_WITH_pex64
#define PCRELOFFSET 		TRUE
#if defined (USE_MINGW64_LEADING_UNDERSCORES)
#define TARGET_UNDERSCORE 	'_'
#else
#define TARGET_UNDERSCORE 	0
#endif
/* Long section names not allowed in executable images, only object files.  */
#define COFF_LONG_SECTION_NAMES 0
#define COFF_SUPPORT_GNU_LINKONCE
#define COFF_LONG_FILENAMES
#define PDATA_ROW_SIZE	(3 * 4)

#define COFF_SECTION_ALIGNMENT_ENTRIES \
{ COFF_SECTION_NAME_EXACT_MATCH (".bss"), \
  COFF_ALIGNMENT_FIELD_EMPTY, COFF_ALIGNMENT_FIELD_EMPTY, 4 }, \
{ COFF_SECTION_NAME_PARTIAL_MATCH (".data"), \
  COFF_ALIGNMENT_FIELD_EMPTY, COFF_ALIGNMENT_FIELD_EMPTY, 4 }, \
{ COFF_SECTION_NAME_PARTIAL_MATCH (".rdata"), \
  COFF_ALIGNMENT_FIELD_EMPTY, COFF_ALIGNMENT_FIELD_EMPTY, 4 }, \
{ COFF_SECTION_NAME_PARTIAL_MATCH (".text"), \
  COFF_ALIGNMENT_FIELD_EMPTY, COFF_ALIGNMENT_FIELD_EMPTY, 4 }, \
{ COFF_SECTION_NAME_PARTIAL_MATCH (".idata"), \
  COFF_ALIGNMENT_FIELD_EMPTY, COFF_ALIGNMENT_FIELD_EMPTY, 2 }, \
{ COFF_SECTION_NAME_EXACT_MATCH (".pdata"), \
  COFF_ALIGNMENT_FIELD_EMPTY, COFF_ALIGNMENT_FIELD_EMPTY, 2 }, \
{ COFF_SECTION_NAME_PARTIAL_MATCH (".debug"), \
  COFF_ALIGNMENT_FIELD_EMPTY, COFF_ALIGNMENT_FIELD_EMPTY, 0 }, \
{ COFF_SECTION_NAME_PARTIAL_MATCH (".gnu.linkonce.wi."), \
  COFF_ALIGNMENT_FIELD_EMPTY, COFF_ALIGNMENT_FIELD_EMPTY, 0 }

/* Note we have to make sure not to include headers twice.
   Not all headers are wrapped in #ifdef guards, so we define
   PEI_HEADERS to prevent double including in coff-x86_64.c  */
#define PEI_HEADERS
#include "sysdep.h"
#include "bfd.h"
#include "libbfd.h"
#include "coff/x86_64.h"
#include "coff/internal.h"
#include "coff/pe.h"
#include "libcoff.h"
#include "libpei.h"
#include "libiberty.h"

#undef AOUTSZ
#define AOUTSZ		PEPAOUTSZ
#define PEAOUTHDR	PEPAOUTHDR

/* Name of registers according to SEH conventions.  */

static const char * const pex_regs[16] = {
  "rax", "rcx", "rdx", "rbx", "rsp", "rbp", "rsi", "rdi",
  "r8", "r9", "r10", "r11", "r12", "r13", "r14", "r15"
};

/* Swap in a runtime function.  */

static void
pex64_get_runtime_function (bfd *abfd, struct pex64_runtime_function *rf,
			    const void *data)
{
  const struct external_pex64_runtime_function *ex_rf =
    (const struct external_pex64_runtime_function *) data;
  rf->rva_BeginAddress = bfd_get_32 (abfd, ex_rf->rva_BeginAddress);
  rf->rva_EndAddress = bfd_get_32 (abfd, ex_rf->rva_EndAddress);
  rf->rva_UnwindData =	bfd_get_32 (abfd, ex_rf->rva_UnwindData);
}

/* Swap in unwind info header.  */

static void
pex64_get_unwind_info (bfd *abfd, struct pex64_unwind_info *ui, void *data)
{
  struct external_pex64_unwind_info *ex_ui =
    (struct external_pex64_unwind_info *) data;
  bfd_byte *ex_dta = (bfd_byte *) data;

  memset (ui, 0, sizeof (struct pex64_unwind_info));
  ui->Version = PEX64_UWI_VERSION (ex_ui->Version_Flags);
  ui->Flags = PEX64_UWI_FLAGS (ex_ui->Version_Flags);
  ui->SizeOfPrologue = (bfd_vma) ex_ui->SizeOfPrologue;
  ui->CountOfCodes = (bfd_vma) ex_ui->CountOfCodes;
  ui->FrameRegister = PEX64_UWI_FRAMEREG (ex_ui->FrameRegisterOffset);
  ui->FrameOffset = PEX64_UWI_FRAMEOFF (ex_ui->FrameRegisterOffset);
  ui->sizeofUnwindCodes = PEX64_UWI_SIZEOF_UWCODE_ARRAY (ui->CountOfCodes);
  ui->SizeOfBlock = ui->sizeofUnwindCodes + 4;
  ui->rawUnwindCodes = &ex_dta[4];

  ex_dta += ui->SizeOfBlock;
  switch (ui->Flags)
    {
    case UNW_FLAG_CHAININFO:
      ui->rva_BeginAddress = bfd_get_32 (abfd, ex_dta + 0);
      ui->rva_EndAddress = bfd_get_32 (abfd, ex_dta + 4);
      ui->rva_UnwindData = bfd_get_32 (abfd, ex_dta + 8);
      ui->SizeOfBlock += 12;
      return;
    case UNW_FLAG_EHANDLER:
    case UNW_FLAG_UHANDLER:
    case UNW_FLAG_FHANDLER:
      ui->rva_ExceptionHandler = bfd_get_32 (abfd, ex_dta);
      ui->SizeOfBlock += 4;
      return;
    default:
      return;
    }
}

/* Display unwind codes.  */

static void
pex64_xdata_print_uwd_codes (FILE *file, bfd *abfd,
			     struct pex64_unwind_info *ui,
			     struct pex64_runtime_function *rf)
{
  unsigned int i;
  unsigned int tmp; /* At least 32 bits.  */
  int save_allowed;

  if (ui->CountOfCodes == 0 || ui->rawUnwindCodes == NULL)
    return;

  /* According to UNWIND_CODE documentation:
      If an FP reg is used, the any unwind code taking an offset must only be
      used after the FP reg is established in the prolog.
     But there are counter examples of that in system dlls...  */
  save_allowed = TRUE;

  i = 0;

  if (ui->Version == 2
      && PEX64_UNWCODE_CODE (ui->rawUnwindCodes[1]) == UWOP_EPILOG)
    {
      /* Display epilog opcode (whose docoding is not fully documented).
         Looks to be designed to speed-up unwinding, as there is no need
	 to decode instruction flow if outside an epilog.  */
      unsigned int func_size = rf->rva_EndAddress - rf->rva_BeginAddress;

      fprintf (file, "\tv2 epilog (length: %02x) at pc+:",
	       ui->rawUnwindCodes[0]);
      if (PEX64_UNWCODE_INFO (ui->rawUnwindCodes[1]))
	fprintf (file, " 0x%x", func_size - ui->rawUnwindCodes[0]);
      i++;
      for (; i < ui->CountOfCodes; i++)
	{
	  const bfd_byte *dta = ui->rawUnwindCodes + 2 * i;
	  unsigned int off;

	  if (PEX64_UNWCODE_CODE (dta[1]) != UWOP_EPILOG)
	    break;
	  off = dta[0] | (PEX64_UNWCODE_INFO (dta[1]) << 8);
	  if (off == 0)
	    fprintf (file, " [pad]");
	  else
	    fprintf (file, " 0x%x", func_size - off);
	}
      fputc ('\n', file);
    }

  for (; i < ui->CountOfCodes; i++)
    {
      const bfd_byte *dta = ui->rawUnwindCodes + 2 * i;
      unsigned int info = PEX64_UNWCODE_INFO (dta[1]);
      int unexpected = FALSE;

      fprintf (file, "\t  pc+0x%02x: ", (unsigned int) dta[0]);
      switch (PEX64_UNWCODE_CODE (dta[1]))
	{
	case UWOP_PUSH_NONVOL:
	  fprintf (file, "push %s", pex_regs[info]);
	  break;
	case UWOP_ALLOC_LARGE:
	  if (info == 0)
	    {
	      tmp = bfd_get_16 (abfd, &dta[2]) * 8;
	      i++;
	    }
	  else
	    {
	      tmp = bfd_get_32 (abfd, &dta[2]);
	      i += 2;
	    }
	  fprintf (file, "alloc large area: rsp = rsp - 0x%x", tmp);
	  break;
	case UWOP_ALLOC_SMALL:
	  fprintf (file, "alloc small area: rsp = rsp - 0x%x", (info + 1) * 8);
	  break;
	case UWOP_SET_FPREG:
	  /* According to the documentation, info field is unused.  */
	  fprintf (file, "FPReg: %s = rsp + 0x%x (info = 0x%x)",
		   pex_regs[ui->FrameRegister],
		   (unsigned int) ui->FrameOffset * 16, info);
	  unexpected = ui->FrameRegister == 0;
	  save_allowed = FALSE;
	  break;
	case UWOP_SAVE_NONVOL:
	  tmp = bfd_get_16 (abfd, &dta[2]) * 8;
	  i++;
	  fprintf (file, "save %s at rsp + 0x%x", pex_regs[info], tmp);
	  unexpected = !save_allowed;
	  break;
	case UWOP_SAVE_NONVOL_FAR:
	  tmp = bfd_get_32 (abfd, &dta[2]);
	  i += 2;
	  fprintf (file, "save %s at rsp + 0x%x", pex_regs[info], tmp);
	  unexpected = !save_allowed;
	  break;
	case UWOP_SAVE_XMM:
	  if (ui->Version == 1)
	    {
	      tmp = bfd_get_16 (abfd, &dta[2]) * 8;
	      i++;
	      fprintf (file, "save mm%u at rsp + 0x%x", info, tmp);
	      unexpected = !save_allowed;
	    }
	  else if (ui->Version == 2)
	    {
	      fprintf (file, "epilog %02x %01x", dta[0], info);
	      unexpected = TRUE;
	    }
	  break;
	case UWOP_SAVE_XMM_FAR:
	  tmp = bfd_get_32 (abfd, &dta[2]) * 8;
	  i += 2;
	  fprintf (file, "save mm%u at rsp + 0x%x", info, tmp);
	  unexpected = !save_allowed;
	  break;
	case UWOP_SAVE_XMM128:
	  tmp = bfd_get_16 (abfd, &dta[2]) * 16;
	  i++;
	  fprintf (file, "save xmm%u at rsp + 0x%x", info, tmp);
	  unexpected = !save_allowed;
	  break;
	case UWOP_SAVE_XMM128_FAR:
	  tmp = bfd_get_32 (abfd, &dta[2]) * 16;
	  i += 2;
	  fprintf (file, "save xmm%u at rsp + 0x%x", info, tmp);
	  unexpected = !save_allowed;
	  break;
	case UWOP_PUSH_MACHFRAME:
	  fprintf (file, "interrupt entry (SS, old RSP, EFLAGS, CS, RIP");
	  if (info == 0)
	    fprintf (file, ")");
	  else if (info == 1)
	    fprintf (file, ",ErrorCode)");
	  else
	    fprintf (file, ", unknown(%u))", info);
	  break;
	default:
	  /* PR 17512: file: 2245-7442-0.004.  */
	  fprintf (file, _("Unknown: %x"), PEX64_UNWCODE_CODE (dta[1]));
	  break;
      }
      if (unexpected)
	fprintf (file, " [Unexpected!]");
      fputc ('\n', file);
    }
}

/* Check wether section SEC_NAME contains the xdata at address ADDR.  */

static asection *
pex64_get_section_by_rva (bfd *abfd, bfd_vma addr, const char *sec_name)
{
  asection *section = bfd_get_section_by_name (abfd, sec_name);
  bfd_vma vsize;
  bfd_size_type datasize = 0;

  if (section == NULL
      || coff_section_data (abfd, section) == NULL
      || pei_section_data (abfd, section) == NULL)
    return NULL;
  vsize = section->vma - pe_data (abfd)->pe_opthdr.ImageBase;
  datasize = section->size;
  if (!datasize || vsize > addr || (vsize + datasize) < addr)
    return NULL;
  return section;
}

/* Dump xdata at for function RF to FILE.  The argument XDATA_SECTION
   designate the bfd section containing the xdata, XDATA is its content,
   and ENDX the size if known (or NULL).  */

static void
pex64_dump_xdata (FILE *file, bfd *abfd,
		  asection *xdata_section, bfd_byte *xdata, bfd_vma *endx,
		  struct pex64_runtime_function *rf)
{
  bfd_vma vaddr;
  bfd_vma end_addr;
  bfd_vma addr = rf->rva_UnwindData;
  bfd_size_type sec_size = xdata_section->rawsize > 0 ? xdata_section->rawsize : xdata_section->size;
  struct pex64_unwind_info ui;

  vaddr = xdata_section->vma - pe_data (abfd)->pe_opthdr.ImageBase;
  addr -= vaddr;

  /* PR 17512: file: 2245-7442-0.004.  */
  if (addr >= sec_size)
    {
      fprintf (file, _("warning: xdata section corrupt\n"));
      return;
    }

  if (endx)
    {
      end_addr = endx[0] - vaddr;
      /* PR 17512: file: 2245-7442-0.004.  */
      if (end_addr > sec_size)
	{
	  fprintf (file, _("warning: xdata section corrupt"));
	  end_addr = sec_size;
	}
    }
  else
    end_addr = sec_size;

  pex64_get_unwind_info (abfd, &ui, &xdata[addr]);
  
  if (ui.Version != 1 && ui.Version != 2)
    {
      unsigned int i;
      fprintf (file, "\tVersion %u (unknown).\n",
	       (unsigned int) ui.Version);
      for (i = 0; addr < end_addr; addr += 1, i++)
	{
	  if ((i & 15) == 0)
	    fprintf (file, "\t  %03x:", i);
	  fprintf (file, " %02x", xdata[addr]);
	  if ((i & 15) == 15)
	    fprintf (file, "\n");
	}
      if ((i & 15) != 0)
	fprintf (file, "\n");
      return;
    }

  fprintf (file, "\tVersion: %d, Flags: ", ui.Version);
  switch (ui.Flags)
    {
    case UNW_FLAG_NHANDLER:
      fprintf (file, "none");
      break;
    case UNW_FLAG_EHANDLER:
      fprintf (file, "UNW_FLAG_EHANDLER");
      break;
    case UNW_FLAG_UHANDLER:
      fprintf (file, "UNW_FLAG_UHANDLER");
      break;
    case UNW_FLAG_FHANDLER:
      fprintf
	(file, "UNW_FLAG_EHANDLER | UNW_FLAG_UHANDLER");
      break;
    case UNW_FLAG_CHAININFO:
      fprintf (file, "UNW_FLAG_CHAININFO");
      break;
    default:
      fprintf (file, "unknown flags value 0x%x", (unsigned int) ui.Flags);
      break;
    }
  fputc ('\n', file);
  fprintf (file, "\tNbr codes: %u, ", (unsigned int) ui.CountOfCodes);
  fprintf (file, "Prologue size: 0x%02x, Frame offset: 0x%x, ",
	   (unsigned int) ui.SizeOfPrologue, (unsigned int) ui.FrameOffset);
  fprintf (file, "Frame reg: %s\n",
	   ui.FrameRegister == 0 ? "none"
	   : pex_regs[(unsigned int) ui.FrameRegister]);

  /* PR 17512: file: 2245-7442-0.004.  */
  if (ui.CountOfCodes * 2 + ui.rawUnwindCodes > xdata + xdata_section->size)
    fprintf (file, _("Too many unwind codes (%ld)\n"), (long) ui.CountOfCodes);
  else
    pex64_xdata_print_uwd_codes (file, abfd, &ui, rf);

  switch (ui.Flags)
    {
    case UNW_FLAG_EHANDLER:
    case UNW_FLAG_UHANDLER:
    case UNW_FLAG_FHANDLER:
      fprintf (file, "\tHandler: ");
      fprintf_vma (file, (ui.rva_ExceptionHandler
			  + pe_data (abfd)->pe_opthdr.ImageBase));
      fprintf (file, ".\n");
      break;
    case UNW_FLAG_CHAININFO:
      fprintf (file, "\tChain: start: ");
      fprintf_vma (file, ui.rva_BeginAddress);
      fprintf (file, ", end: ");
      fprintf_vma (file, ui.rva_EndAddress);
      fprintf (file, "\n\t unwind data: ");
      fprintf_vma (file, ui.rva_UnwindData);
      fprintf (file, ".\n");
      break;
    }

  /* Now we need end of this xdata block.  */
  addr += ui.SizeOfBlock;
  if (addr < end_addr)
    {
      unsigned int i;
      fprintf (file,"\tUser data:\n");
      for (i = 0; addr < end_addr; addr += 1, i++)
	{
	  if ((i & 15) == 0)
	    fprintf (file, "\t  %03x:", i);
	  fprintf (file, " %02x", xdata[addr]);
	  if ((i & 15) == 15)
	    fprintf (file, "\n");
	}
      if ((i & 15) != 0)
	fprintf (file, "\n");
    }
}

/* Helper function to sort xdata.  The entries of xdata are sorted to know
   the size of each entry.  */

static int
sort_xdata_arr (const void *l, const void *r)
{
  const bfd_vma *lp = (const bfd_vma *) l;
  const bfd_vma *rp = (const bfd_vma *) r;

  if (*lp == *rp)
    return 0;
  return (*lp < *rp ? -1 : 1);
}

/* Display unwind tables for x86-64.  */

static bfd_boolean
pex64_bfd_print_pdata_section (bfd *abfd, void *vfile, asection *pdata_section)
{
  FILE *file = (FILE *) vfile;
  bfd_byte *pdata = NULL;
  bfd_byte *xdata = NULL;
  asection *xdata_section = NULL;
  bfd_vma xdata_base;
  bfd_size_type i;
  bfd_size_type datasize;
  bfd_size_type stop;
  bfd_vma prev_beginaddress = (bfd_vma) -1;
  bfd_vma prev_unwinddata_rva = (bfd_vma) -1;
  bfd_vma imagebase;
  int onaline = PDATA_ROW_SIZE;
  int seen_error = 0;
  bfd_vma *xdata_arr = NULL;
  int xdata_arr_cnt;
  bfd_boolean virt_size_is_zero = FALSE;

  /* Sanity checks.  */
  if (pdata_section == NULL
      || coff_section_data (abfd, pdata_section) == NULL
      || pei_section_data (abfd, pdata_section) == NULL)
    return TRUE;

  stop = pei_section_data (abfd, pdata_section)->virt_size;
  if ((stop % onaline) != 0)
    fprintf (file,
	     _("Warning: %s section size (%ld) is not a multiple of %d\n"),
	     pdata_section->name, (long) stop, onaline);

  datasize = pdata_section->size;
  if (datasize == 0)
    {
      if (stop)
	fprintf (file, _("Warning: %s section size is zero\n"),
		 pdata_section->name);
      return TRUE;
    }

  /* virt_size might be zero for objects.  */
  if (stop == 0 && strcmp (abfd->xvec->name, "pe-x86-64") == 0)
    {
      stop = (datasize / onaline) * onaline;
      virt_size_is_zero = TRUE;
    }
  else if (datasize < stop)
      {
	fprintf (file,
		 _("Warning: %s section size (%ld) is smaller than virtual size (%ld)\n"),
		 pdata_section->name, (unsigned long) datasize,
		 (unsigned long) stop);
	/* Be sure not to read passed datasize.  */
	stop = datasize / onaline;
      }

  /* Display functions table.  */
  fprintf (file,
	   _("\nThe Function Table (interpreted %s section contents)\n"),
	   pdata_section->name);

  fprintf (file, _("vma:\t\t\tBeginAddress\t EndAddress\t  UnwindData\n"));

  if (!bfd_malloc_and_get_section (abfd, pdata_section, &pdata))
    goto done;

  /* Table of xdata entries.  */
  xdata_arr = (bfd_vma *) xmalloc (sizeof (bfd_vma) * ((stop / onaline) + 1));
  xdata_arr_cnt = 0;

  if (strcmp (abfd->xvec->name, "pei-x86-64") == 0)
    imagebase = pe_data (abfd)->pe_opthdr.ImageBase;
  else
    imagebase = 0;

  for (i = 0; i < stop; i += onaline)
    {
      struct pex64_runtime_function rf;

      if (i + PDATA_ROW_SIZE > stop)
	break;

      pex64_get_runtime_function (abfd, &rf, &pdata[i]);

      if (rf.rva_BeginAddress == 0 && rf.rva_EndAddress == 0
	  && rf.rva_UnwindData == 0)
	/* We are probably into the padding of the section now.  */
	break;
      fputc (' ', file);
      fprintf_vma (file, i + pdata_section->vma);
      fprintf (file, ":\t");
      fprintf_vma (file, imagebase + rf.rva_BeginAddress);
      fprintf (file, " ");
      fprintf_vma (file, imagebase + rf.rva_EndAddress);
      fprintf (file, " ");
      fprintf_vma (file, imagebase + rf.rva_UnwindData);
      fprintf (file, "\n");
      if (i != 0 && rf.rva_BeginAddress <= prev_beginaddress)
	{
	  seen_error = 1;
	  fprintf (file, "  has %s begin address as predecessor\n",
	    (rf.rva_BeginAddress < prev_beginaddress ? "smaller" : "same"));
        }
      prev_beginaddress = rf.rva_BeginAddress;
      /* Now we check for negative addresses.  */
      if ((prev_beginaddress & 0x80000000) != 0)
	{
	  seen_error = 1;
	  fprintf (file, "  has negative begin address\n");
	}
      if ((rf.rva_EndAddress & 0x80000000) != 0)
	{
	  seen_error = 1;
	  fprintf (file, "  has negative end address\n");
	}
      if ((rf.rva_UnwindData & 0x80000000) != 0)
	{
	  seen_error = 1;
	  fprintf (file, "  has negative unwind address\n");
	}
      else if ((rf.rva_UnwindData && !PEX64_IS_RUNTIME_FUNCTION_CHAINED (&rf))
		|| virt_size_is_zero)
	xdata_arr[xdata_arr_cnt++] = rf.rva_UnwindData;
    }

  if (seen_error)
    goto done;

  /* Add end of list marker.  */
  xdata_arr[xdata_arr_cnt++] = ~((bfd_vma) 0);

  /* Sort start RVAs of xdata.  */
  if (xdata_arr_cnt > 1)
    qsort (xdata_arr, (size_t) xdata_arr_cnt, sizeof (bfd_vma),
	   sort_xdata_arr);

  /* Find the section containing the unwind data (.xdata).  */
  xdata_base = xdata_arr[0];
  /* For sections with long names, first look for the same
     section name, replacing .pdata by .xdata prefix.  */
  if (strcmp (pdata_section->name, ".pdata") != 0)
    {
      size_t len = strlen (pdata_section->name);
      char *xdata_name = alloca (len + 1);

      xdata_name = memcpy (xdata_name, pdata_section->name, len + 1);
      /* Transform .pdata prefix into .xdata prefix.  */
      if (len > 1)
	xdata_name [1] = 'x';
      xdata_section = pex64_get_section_by_rva (abfd, xdata_base,
						xdata_name);
    }
  /* Second, try the .xdata section itself.  */
  if (!xdata_section)
    xdata_section = pex64_get_section_by_rva (abfd, xdata_base, ".xdata");
  /* Otherwise, if xdata_base is non zero, search also inside
     other standard sections.  */
  if (!xdata_section && xdata_base)
    xdata_section = pex64_get_section_by_rva (abfd, xdata_base, ".rdata");
  if (!xdata_section && xdata_base)
    xdata_section = pex64_get_section_by_rva (abfd, xdata_base, ".data");
  if (!xdata_section && xdata_base)
    xdata_section = pex64_get_section_by_rva (abfd, xdata_base, ".pdata");
  if (!xdata_section && xdata_base)
    xdata_section = pex64_get_section_by_rva (abfd, xdata_base, ".text");
  /* Transfer xdata section into xdata array.  */
  if (!xdata_section
      || !bfd_malloc_and_get_section (abfd, xdata_section, &xdata))
    goto done;

  /* Avoid "also used "... ouput for single unwind info
     in object file.  */
  prev_unwinddata_rva = (bfd_vma) -1;

  /* Do dump of pdata related xdata.  */
  for (i = 0; i < stop; i += onaline)
    {
      struct pex64_runtime_function rf;

      if (i + PDATA_ROW_SIZE > stop)
	break;

      pex64_get_runtime_function (abfd, &rf, &pdata[i]);

      if (rf.rva_BeginAddress == 0 && rf.rva_EndAddress == 0
	  && rf.rva_UnwindData == 0)
	/* We are probably into the padding of the section now.  */
	break;
      if (i == 0)
        fprintf (file, _("\nDump of %s\n"), xdata_section->name);

      fputc (' ', file);
      fprintf_vma (file, rf.rva_UnwindData + imagebase);

      if (prev_unwinddata_rva == rf.rva_UnwindData)
	{
	  /* Do not dump again the xdata for the same entry.  */
	  fprintf (file, " also used for function at ");
	  fprintf_vma (file, rf.rva_BeginAddress + imagebase);
	  fputc ('\n', file);
	  continue;
	}
      else
	prev_unwinddata_rva = rf.rva_UnwindData;

      fprintf (file, " (rva: %08x): ",
	       (unsigned int) rf.rva_UnwindData);
      fprintf_vma (file, rf.rva_BeginAddress + imagebase);
      fprintf (file, " - ");
      fprintf_vma (file, rf.rva_EndAddress + imagebase);
      fputc ('\n', file);

      if (rf.rva_UnwindData != 0 || virt_size_is_zero)
	{
	  if (PEX64_IS_RUNTIME_FUNCTION_CHAINED (&rf))
	    {
	      bfd_vma altent = PEX64_GET_UNWINDDATA_UNIFIED_RVA (&rf);
	      bfd_vma pdata_vma = bfd_get_section_vma (abfd, pdata_section);
	      struct pex64_runtime_function arf;

	      fprintf (file, "\t shares information with ");
	      altent += imagebase;

	      if (altent >= pdata_vma
		  && (altent + PDATA_ROW_SIZE <= pdata_vma
		      + pei_section_data (abfd, pdata_section)->virt_size))
		{
		  pex64_get_runtime_function
		    (abfd, &arf, &pdata[altent - pdata_vma]);
		  fprintf (file, "pdata element at 0x");
		  fprintf_vma (file, arf.rva_UnwindData);
		}
	      else
		fprintf (file, "unknown pdata element");
	      fprintf (file, ".\n");
	    }
	  else
	    {
	      bfd_vma *p;

	      /* Search for the current entry in the sorted array.  */
	      p = (bfd_vma *)
	          bsearch (&rf.rva_UnwindData, xdata_arr,
			   (size_t) xdata_arr_cnt, sizeof (bfd_vma),
			   sort_xdata_arr);

	      /* Advance to the next pointer into the xdata section.  We may
		 have shared xdata entries, which will result in a string of
		 identical pointers in the array; advance past all of them.  */
	      while (p[0] <= rf.rva_UnwindData)
		++p;

	      if (p[0] == ~((bfd_vma) 0))
		p = NULL;

	      pex64_dump_xdata (file, abfd, xdata_section, xdata, p, &rf);
	    }
	}
    }

 done:
  free (pdata);
  free (xdata_arr);
  free (xdata);

  return TRUE;
}

/* Static counter of number of found pdata sections.  */
static bfd_boolean pdata_count;

/* Functionn prototype.  */
bfd_boolean pex64_bfd_print_pdata (bfd *, void *);

/* Helper function for bfd_map_over_section.  */
static void
pex64_print_all_pdata_sections (bfd *abfd, asection *pdata, void *obj)
{
  if (CONST_STRNEQ (pdata->name, ".pdata"))
    {
      if (pex64_bfd_print_pdata_section (abfd, obj, pdata))
	pdata_count++;
    }
}

bfd_boolean
pex64_bfd_print_pdata (bfd *abfd, void *vfile)
{
  asection *pdata_section = bfd_get_section_by_name (abfd, ".pdata");

  if (pdata_section)
    return pex64_bfd_print_pdata_section (abfd, vfile, pdata_section);

  pdata_count = 0;
  bfd_map_over_sections (abfd, pex64_print_all_pdata_sections, vfile);
  return (pdata_count > 0);
}

#define bfd_pe_print_pdata   pex64_bfd_print_pdata
#define bfd_coff_std_swap_table bfd_coff_pei_swap_table

#include "coff-x86_64.c"
' href='#n4032'>4032 4033 4034 4035 4036 4037 4038 4039 4040 4041 4042 4043 4044 4045 4046 4047 4048 4049 4050 4051 4052 4053 4054 4055 4056 4057 4058 4059 4060 4061 4062 4063 4064 4065 4066 4067 4068 4069 4070 4071 4072 4073 4074 4075 4076 4077 4078 4079 4080 4081 4082 4083 4084 4085 4086 4087 4088 4089 4090 4091 4092 4093 4094 4095 4096 4097 4098 4099 4100 4101 4102 4103 4104 4105 4106 4107 4108 4109 4110 4111 4112 4113 4114 4115 4116 4117 4118 4119 4120 4121 4122 4123 4124 4125 4126 4127 4128 4129 4130 4131 4132 4133 4134 4135 4136 4137 4138 4139 4140 4141 4142 4143 4144 4145 4146 4147 4148 4149 4150 4151 4152 4153 4154 4155 4156 4157 4158 4159 4160 4161 4162 4163 4164 4165 4166 4167 4168 4169 4170 4171 4172 4173 4174 4175 4176 4177 4178 4179 4180 4181 4182 4183 4184 4185 4186 4187 4188 4189 4190 4191 4192 4193 4194 4195 4196 4197 4198 4199 4200 4201 4202 4203 4204 4205 4206 4207 4208 4209 4210 4211 4212 4213 4214 4215 4216 4217 4218 4219 4220 4221 4222 4223 4224 4225 4226 4227 4228 4229 4230 4231 4232 4233 4234 4235 4236 4237 4238 4239 4240 4241 4242 4243 4244 4245 4246 4247 4248 4249 4250 4251 4252 4253 4254 4255 4256 4257 4258 4259 4260 4261 4262 4263 4264 4265 4266 4267 4268 4269 4270 4271 4272 4273 4274 4275 4276 4277 4278 4279 4280 4281 4282 4283 4284 4285 4286 4287 4288 4289 4290 4291 4292 4293 4294 4295 4296 4297 4298 4299 4300 4301 4302 4303 4304 4305 4306 4307 4308 4309 4310 4311 4312 4313 4314 4315 4316 4317 4318 4319 4320 4321 4322 4323 4324 4325 4326 4327 4328 4329 4330 4331 4332 4333 4334 4335 4336 4337 4338 4339 4340 4341 4342 4343 4344 4345 4346 4347 4348 4349 4350 4351 4352 4353 4354 4355 4356 4357 4358 4359 4360 4361 4362 4363 4364 4365 4366 4367 4368 4369 4370 4371 4372 4373 4374 4375 4376 4377 4378 4379 4380 4381 4382 4383 4384 4385 4386 4387 4388 4389 4390 4391 4392 4393 4394 4395 4396 4397 4398 4399 4400 4401 4402 4403 4404 4405 4406 4407 4408 4409 4410 4411 4412 4413 4414 4415 4416 4417 4418 4419 4420 4421 4422 4423 4424 4425 4426 4427 4428 4429 4430 4431 4432 4433 4434 4435 4436 4437 4438 4439 4440 4441 4442 4443 4444 4445 4446 4447 4448 4449 4450 4451 4452 4453 4454 4455 4456 4457 4458 4459 4460 4461 4462 4463 4464 4465 4466 4467 4468 4469 4470 4471 4472 4473 4474 4475 4476 4477 4478 4479 4480 4481 4482 4483 4484 4485 4486 4487 4488 4489 4490 4491 4492 4493 4494 4495 4496 4497 4498 4499 4500 4501 4502 4503 4504 4505 4506 4507 4508 4509 4510 4511 4512 4513 4514 4515 4516 4517 4518 4519 4520 4521 4522 4523 4524 4525 4526 4527 4528 4529 4530 4531 4532 4533 4534 4535 4536 4537 4538 4539 4540 4541 4542 4543 4544 4545 4546 4547 4548 4549 4550 4551 4552 4553 4554 4555 4556 4557 4558 4559 4560 4561 4562 4563 4564 4565 4566 4567 4568 4569 4570 4571 4572 4573 4574 4575 4576 4577 4578 4579 4580 4581 4582 4583 4584 4585 4586 4587 4588 4589 4590 4591 4592 4593 4594 4595 4596 4597 4598 4599 4600 4601 4602 4603 4604 4605 4606 4607 4608 4609 4610 4611 4612 4613 4614 4615 4616 4617 4618 4619 4620 4621 4622 4623 4624 4625 4626 4627 4628 4629 4630 4631 4632 4633 4634 4635 4636 4637 4638 4639 4640 4641 4642 4643 4644 4645 4646 4647 4648 4649 4650 4651 4652 4653 4654 4655 4656 4657 4658 4659 4660 4661 4662 4663 4664 4665 4666 4667 4668 4669 4670 4671 4672 4673 4674 4675 4676 4677 4678 4679 4680 4681 4682 4683 4684 4685 4686 4687 4688 4689 4690 4691 4692 4693 4694 4695 4696 4697 4698 4699 4700 4701 4702 4703 4704 4705 4706 4707 4708 4709 4710 4711 4712 4713 4714 4715 4716 4717 4718 4719 4720 4721 4722 4723 4724 4725 4726 4727 4728 4729 4730 4731 4732 4733 4734 4735 4736 4737 4738 4739 4740 4741 4742 4743 4744 4745 4746 4747 4748 4749 4750 4751 4752 4753 4754 4755 4756 4757 4758 4759 4760 4761 4762 4763 4764 4765 4766 4767 4768 4769 4770 4771 4772 4773 4774 4775 4776 4777 4778 4779 4780 4781 4782 4783 4784 4785 4786 4787 4788 4789 4790 4791 4792 4793 4794 4795 4796 4797 4798 4799 4800 4801 4802 4803 4804 4805 4806 4807 4808 4809 4810 4811 4812 4813 4814 4815 4816 4817 4818 4819 4820 4821 4822 4823 4824 4825 4826 4827 4828 4829 4830 4831 4832 4833 4834 4835 4836 4837 4838 4839 4840 4841 4842 4843 4844 4845 4846 4847 4848 4849 4850 4851 4852 4853 4854 4855 4856 4857 4858 4859 4860 4861 4862 4863 4864 4865 4866 4867 4868 4869 4870 4871 4872 4873 4874 4875 4876 4877 4878 4879 4880 4881 4882 4883 4884 4885 4886 4887 4888 4889 4890 4891 4892 4893 4894 4895 4896 4897 4898 4899 4900 4901 4902 4903 4904 4905 4906 4907 4908 4909 4910 4911 4912 4913 4914 4915 4916 4917 4918 4919 4920 4921 4922 4923 4924 4925 4926 4927 4928 4929 4930 4931 4932 4933 4934 4935 4936 4937 4938 4939 4940 4941 4942 4943 4944 4945 4946 4947 4948 4949 4950 4951 4952 4953 4954 4955 4956 4957 4958 4959 4960 4961 4962 4963 4964 4965 4966 4967 4968 4969 4970 4971 4972 4973 4974 4975 4976 4977 4978 4979 4980 4981 4982 4983 4984 4985 4986 4987 4988 4989 4990 4991 4992 4993 4994 4995 4996 4997 4998 4999 5000 5001 5002 5003 5004 5005 5006 5007 5008 5009 5010 5011 5012 5013 5014 5015 5016 5017 5018 5019 5020 5021 5022 5023 5024 5025 5026 5027 5028 5029 5030 5031 5032 5033 5034 5035 5036 5037 5038 5039 5040 5041 5042 5043 5044 5045 5046 5047 5048 5049 5050 5051 5052 5053 5054 5055 5056 5057 5058 5059 5060 5061 5062 5063 5064 5065 5066 5067 5068 5069 5070 5071 5072 5073 5074 5075 5076 5077 5078 5079 5080 5081 5082 5083 5084 5085 5086 5087 5088 5089 5090 5091 5092 5093 5094 5095 5096 5097 5098 5099 5100 5101 5102 5103 5104 5105 5106 5107 5108 5109 5110 5111 5112 5113 5114 5115 5116 5117 5118 5119 5120 5121 5122 5123 5124 5125 5126 5127 5128 5129 5130 5131 5132 5133 5134 5135 5136 5137 5138 5139 5140 5141 5142 5143 5144 5145 5146 5147 5148 5149 5150 5151 5152 5153 5154 5155 5156 5157 5158 5159 5160 5161 5162 5163 5164 5165 5166 5167 5168 5169 5170 5171 5172 5173 5174 5175 5176 5177 5178 5179 5180 5181 5182 5183 5184 5185 5186 5187 5188 5189 5190 5191 5192 5193 5194 5195 5196 5197 5198 5199 5200 5201 5202 5203 5204 5205 5206 5207 5208 5209 5210 5211 5212 5213 5214 5215 5216 5217 5218 5219 5220 5221 5222 5223 5224 5225 5226 5227 5228 5229 5230 5231 5232 5233 5234 5235 5236 5237 5238 5239 5240 5241 5242 5243 5244 5245 5246 5247 5248 5249 5250 5251 5252 5253 5254 5255 5256 5257 5258 5259 5260 5261 5262 5263 5264 5265 5266 5267 5268 5269 5270 5271 5272 5273 5274 5275 5276 5277 5278 5279 5280 5281 5282 5283 5284 5285 5286 5287 5288 5289 5290 5291 5292 5293 5294 5295 5296 5297 5298 5299 5300 5301 5302 5303 5304 5305 5306 5307 5308 5309 5310 5311 5312 5313 5314 5315 5316 5317 5318 5319 5320 5321 5322 5323 5324 5325 5326 5327 5328 5329 5330 5331 5332 5333 5334 5335 5336 5337 5338 5339 5340 5341 5342 5343 5344 5345 5346 5347 5348 5349 5350 5351 5352 5353 5354 5355 5356 5357 5358 5359 5360 5361 5362 5363 5364 5365 5366 5367 5368 5369 5370 5371 5372 5373 5374 5375 5376 5377 5378 5379 5380 5381 5382 5383 5384 5385 5386 5387 5388 5389 5390 5391 5392 5393 5394 5395 5396 5397 5398 5399 5400 5401 5402 5403 5404 5405 5406 5407 5408 5409 5410 5411 5412 5413 5414 5415 5416 5417 5418 5419 5420 5421 5422 5423 5424 5425 5426 5427 5428 5429 5430 5431 5432 5433 5434 5435 5436 5437 5438 5439 5440 5441 5442 5443 5444 5445 5446 5447 5448 5449 5450 5451 5452 5453 5454 5455 5456 5457 5458 5459 5460 5461 5462 5463 5464 5465 5466 5467 5468 5469 5470 5471 5472 5473 5474 5475 5476 5477 5478 5479 5480 5481 5482 5483 5484 5485 5486 5487 5488 5489 5490 5491 5492 5493 5494 5495 5496 5497 5498 5499 5500 5501 5502 5503 5504 5505 5506 5507 5508 5509 5510 5511 5512 5513 5514 5515 5516 5517 5518 5519 5520 5521 5522 5523 5524 5525 5526 5527 5528 5529 5530 5531 5532 5533 5534 5535 5536 5537 5538 5539 5540 5541 5542 5543 5544 5545 5546 5547 5548 5549 5550 5551 5552 5553 5554 5555 5556 5557 5558 5559 5560 5561 5562 5563 5564 5565 5566 5567 5568 5569 5570 5571 5572 5573 5574 5575 5576 5577 5578 5579 5580 5581 5582 5583 5584 5585 5586 5587 5588 5589 5590 5591 5592 5593 5594 5595 5596 5597 5598 5599 5600 5601 5602 5603 5604 5605 5606 5607 5608 5609 5610 5611 5612 5613 5614 5615 5616 5617 5618 5619 5620 5621 5622 5623 5624 5625 5626 5627 5628 5629 5630 5631 5632 5633 5634 5635 5636 5637 5638 5639 5640 5641 5642 5643 5644 5645 5646 5647 5648 5649 5650 5651 5652 5653 5654 5655 5656 5657 5658 5659 5660 5661 5662 5663 5664 5665 5666 5667 5668 5669 5670 5671 5672 5673 5674 5675 5676 5677 5678 5679 5680 5681 5682 5683 5684 5685 5686 5687 5688 5689 5690 5691 5692 5693 5694 5695 5696 5697 5698 5699 5700 5701 5702 5703 5704 5705 5706 5707 5708 5709 5710 5711 5712 5713 5714 5715 5716 5717 5718 5719 5720 5721 5722 5723 5724 5725 5726 5727 5728 5729 5730 5731 5732 5733 5734 5735 5736 5737 5738 5739 5740 5741 5742 5743 5744 5745 5746 5747 5748 5749 5750 5751 5752 5753 5754 5755 5756 5757 5758 5759 5760 5761 5762 5763 5764 5765 5766 5767 5768 5769 5770 5771 5772 5773 5774 5775 5776 5777 5778 5779 5780 5781 5782 5783 5784 5785 5786 5787 5788 5789 5790 5791 5792 5793 5794 5795 5796 5797 5798 5799 5800 5801 5802 5803 5804 5805 5806 5807 5808 5809 5810 5811 5812 5813 5814 5815 5816 5817 5818 5819 5820 5821 5822 5823 5824 5825 5826 5827 5828 5829 5830 5831 5832 5833 5834 5835 5836 5837 5838 5839 5840 5841 5842 5843 5844 5845 5846 5847 5848 5849 5850 5851 5852 5853 5854 5855 5856 5857 5858 5859 5860 5861 5862 5863 5864 5865 5866 5867 5868 5869 5870 5871 5872 5873 5874 5875 5876 5877 5878 5879 5880 5881 5882 5883 5884 5885 5886 5887 5888 5889 5890 5891 5892 5893 5894 5895 5896 5897 5898 5899 5900 5901 5902 5903 5904 5905 5906 5907 5908 5909 5910 5911 5912 5913 5914 5915 5916 5917 5918 5919 5920 5921 5922 5923 5924 5925 5926 5927 5928 5929 5930 5931 5932 5933 5934 5935 5936 5937 5938 5939 5940 5941 5942 5943 5944 5945 5946 5947 5948 5949 5950 5951 5952 5953 5954 5955 5956 5957 5958 5959 5960 5961 5962 5963 5964 5965 5966 5967 5968 5969 5970 5971 5972 5973 5974 5975 5976 5977 5978 5979 5980 5981 5982 5983 5984 5985 5986 5987 5988 5989 5990 5991 5992 5993 5994 5995 5996 5997 5998 5999 6000 6001 6002 6003 6004 6005 6006 6007 6008 6009 6010 6011 6012 6013 6014 6015 6016 6017 6018 6019 6020
/* String length optimization
   Copyright (C) 2011-2023 Free Software Foundation, Inc.
   Contributed by Jakub Jelinek <jakub@redhat.com>

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3, or (at your option)
any later version.

GCC is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3.  If not see
<http://www.gnu.org/licenses/>.  */

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "rtl.h"
#include "tree.h"
#include "gimple.h"
#include "alloc-pool.h"
#include "tree-pass.h"
#include "ssa.h"
#include "cgraph.h"
#include "gimple-pretty-print.h"
#include "gimple-ssa-warn-access.h"
#include "gimple-ssa-warn-restrict.h"
#include "fold-const.h"
#include "stor-layout.h"
#include "gimple-iterator.h"
#include "gimple-fold.h"
#include "tree-eh.h"
#include "gimplify.h"
#include "gimplify-me.h"
#include "expr.h"
#include "tree-cfg.h"
#include "tree-dfa.h"
#include "domwalk.h"
#include "tree-ssa-alias.h"
#include "tree-ssa-propagate.h"
#include "tree-ssa-strlen.h"
#include "tree-hash-traits.h"
#include "builtins.h"
#include "pointer-query.h"
#include "target.h"
#include "diagnostic-core.h"
#include "diagnostic.h"
#include "intl.h"
#include "attribs.h"
#include "calls.h"
#include "cfgloop.h"
#include "tree-ssa-loop.h"
#include "tree-scalar-evolution.h"
#include "vr-values.h"
#include "gimple-range.h"
#include "tree-ssa.h"

/* A vector indexed by SSA_NAME_VERSION.  0 means unknown, positive value
   is an index into strinfo vector, negative value stands for
   string length of a string literal (~strlen).  */
static vec<int> ssa_ver_to_stridx;

/* Number of currently active string indexes plus one.  */
static int max_stridx;

/* Set to true to optimize, false when just checking.  */
static bool strlen_optimize;

/* String information record.  */
struct strinfo
{
  /* Number of leading characters that are known to be nonzero.  This is
     also the length of the string if FULL_STRING_P.

     The values in a list of related string pointers must be consistent;
     that is, if strinfo B comes X bytes after strinfo A, it must be
     the case that A->nonzero_chars == X + B->nonzero_chars.  */
  tree nonzero_chars;
  /* Any of the corresponding pointers for querying alias oracle.  */
  tree ptr;
  /* STMT is used for two things:

     - To record the statement that should be used for delayed length
       computations.  We maintain the invariant that all related strinfos
       have delayed lengths or none do.

     - To record the malloc or calloc call that produced this result
       to optimize away malloc/memset sequences.  STMT is reset after
       a calloc-allocated object has been stored a non-zero value into.  */
  gimple *stmt;
  /* Set to the dynamic allocation statement for the object (alloca,
     calloc, malloc, or VLA).  Unlike STMT, once set for a strinfo
     object, ALLOC doesn't change.  */
  gimple *alloc;
  /* Pointer to '\0' if known, if NULL, it can be computed as
     ptr + length.  */
  tree endptr;
  /* Reference count.  Any changes to strinfo entry possibly shared
     with dominating basic blocks need unshare_strinfo first, except
     for dont_invalidate which affects only the immediately next
     maybe_invalidate.  */
  int refcount;
  /* Copy of index.  get_strinfo (si->idx) should return si;  */
  int idx;
  /* These 3 fields are for chaining related string pointers together.
     E.g. for
     bl = strlen (b); dl = strlen (d); strcpy (a, b); c = a + bl;
     strcpy (c, d); e = c + dl;
     strinfo(a) -> strinfo(c) -> strinfo(e)
     All have ->first field equal to strinfo(a)->idx and are doubly
     chained through prev/next fields.  The later strinfos are required
     to point into the same string with zero or more bytes after
     the previous pointer and all bytes in between the two pointers
     must be non-zero.  Functions like strcpy or memcpy are supposed
     to adjust all previous strinfo lengths, but not following strinfo
     lengths (those are uncertain, usually invalidated during
     maybe_invalidate, except when the alias oracle knows better).
     Functions like strcat on the other side adjust the whole
     related strinfo chain.
     They are updated lazily, so to use the chain the same first fields
     and si->prev->next == si->idx needs to be verified.  */
  int first;
  int next;
  int prev;
  /* A flag whether the string is known to be written in the current
     function.  */
  bool writable;
  /* A flag for the next maybe_invalidate that this strinfo shouldn't
     be invalidated.  Always cleared by maybe_invalidate.  */
  bool dont_invalidate;
  /* True if the string is known to be nul-terminated after NONZERO_CHARS
     characters.  False is useful when detecting strings that are built
     up via successive memcpys.  */
  bool full_string_p;
};

/* Pool for allocating strinfo_struct entries.  */
static object_allocator<strinfo> strinfo_pool ("strinfo pool");

/* Vector mapping positive string indexes to strinfo, for the
   current basic block.  The first pointer in the vector is special,
   it is either NULL, meaning the vector isn't shared, or it is
   a basic block pointer to the owner basic_block if shared.
   If some other bb wants to modify the vector, the vector needs
   to be unshared first, and only the owner bb is supposed to free it.  */
static vec<strinfo *, va_heap, vl_embed> *stridx_to_strinfo;

/* One OFFSET->IDX mapping.  */
struct stridxlist
{
  struct stridxlist *next;
  HOST_WIDE_INT offset;
  int idx;
};

/* Hash table entry, mapping a DECL to a chain of OFFSET->IDX mappings.  */
struct decl_stridxlist_map
{
  struct tree_map_base base;
  struct stridxlist list;
};

/* Hash table for mapping decls to a chained list of offset -> idx
   mappings.  */
typedef hash_map<tree_decl_hash, stridxlist> decl_to_stridxlist_htab_t;
static decl_to_stridxlist_htab_t *decl_to_stridxlist_htab;

/* Hash table mapping strlen (or strnlen with constant bound and return
   smaller than bound) calls to stridx instances describing
   the calls' arguments.  Non-null only when warn_stringop_truncation
   is non-zero.  */
typedef std::pair<int, location_t> stridx_strlenloc;
static hash_map<tree, stridx_strlenloc> *strlen_to_stridx;

/* Obstack for struct stridxlist and struct decl_stridxlist_map.  */
static struct obstack stridx_obstack;

/* Last memcpy statement if it could be adjusted if the trailing
   '\0' written is immediately overwritten, or
   *x = '\0' store that could be removed if it is immediately overwritten.  */
struct laststmt_struct
{
  gimple *stmt;
  tree len;
  int stridx;
} laststmt;

static int get_stridx_plus_constant (strinfo *, unsigned HOST_WIDE_INT, tree);
static bool get_range_strlen_dynamic (tree, gimple *, c_strlen_data *,
				      bitmap, pointer_query *, unsigned *);

/* Sets MINMAX to either the constant value or the range VAL is in
   and returns either the constant value or VAL on success or null
   when the range couldn't be determined.  Uses RVALS or CFUN for
   range info, whichever is nonnull.  */

tree
get_range (tree val, gimple *stmt, wide_int minmax[2],
	   range_query *rvals /* = NULL */)
{
  if (!rvals)
    {
      if (!cfun)
	/* When called from front ends for global initializers CFUN
	   may be null.  */
	return NULL_TREE;

      rvals = get_range_query (cfun);
    }

  value_range vr;
  if (!rvals->range_of_expr (vr, val, stmt))
    return NULL_TREE;

  tree vrmin, vrmax;
  value_range_kind rng = get_legacy_range (vr, vrmin, vrmax);
  if (rng == VR_RANGE)
    {
      /* Only handle straight ranges.  */
      minmax[0] = wi::to_wide (vrmin);
      minmax[1] = wi::to_wide (vrmax);
      return val;
    }

  return NULL_TREE;
}

class strlen_pass : public dom_walker
{
public:
  strlen_pass (cdi_direction direction)
    : dom_walker (direction),
      ptr_qry (&m_ranger),
      m_cleanup_cfg (false)
  {
  }

  ~strlen_pass ();

  edge before_dom_children (basic_block) final override;
  void after_dom_children (basic_block) final override;

  bool check_and_optimize_stmt (bool *cleanup_eh);
  bool check_and_optimize_call (bool *zero_write);
  bool handle_assign (tree lhs, bool *zero_write);
  bool handle_store (bool *zero_write);
  void handle_pointer_plus ();
  void handle_builtin_strlen ();
  void handle_builtin_strchr ();
  void handle_builtin_strcpy (built_in_function);
  void handle_integral_assign (bool *cleanup_eh);
  void handle_builtin_stxncpy_strncat (bool append_p);
  void handle_builtin_memcpy (built_in_function bcode);
  void handle_builtin_strcat (built_in_function bcode);
  void handle_builtin_strncat (built_in_function);
  bool handle_builtin_memset (bool *zero_write);
  bool handle_builtin_memcmp ();
  bool handle_builtin_string_cmp ();
  void handle_alloc_call (built_in_function);
  void maybe_warn_overflow (gimple *stmt, bool call_lhs, tree len,
			    strinfo *si = NULL, bool plus_one = false,
			    bool rawmem = false);
  void maybe_warn_overflow (gimple *stmt, bool call_lhs,
			    unsigned HOST_WIDE_INT len,
			    strinfo *si = NULL,
			    bool plus_one = false, bool rawmem = false);
  void adjust_last_stmt (strinfo *si, gimple *stmt, bool is_strcat);
  tree strxcmp_eqz_result (gimple *stmt, tree arg1, int idx1,
			   tree arg2, int idx2,
			   unsigned HOST_WIDE_INT bound,
			   unsigned HOST_WIDE_INT len[2],
			   unsigned HOST_WIDE_INT *psize);
  bool count_nonzero_bytes (tree expr_or_type,
			    gimple *stmt,
			    unsigned lenrange[3], bool *nulterm,
			    bool *allnul, bool *allnonnul);
  bool count_nonzero_bytes (tree exp,
			    gimple *stmt,
			    unsigned HOST_WIDE_INT offset,
			    unsigned HOST_WIDE_INT nbytes,
			    unsigned lenrange[3], bool *nulterm,
			    bool *allnul, bool *allnonnul,
			    ssa_name_limit_t &snlim);
  bool count_nonzero_bytes_addr (tree exp,
				 gimple *stmt,
				 unsigned HOST_WIDE_INT offset,
				 unsigned HOST_WIDE_INT nbytes,
				 unsigned lenrange[3], bool *nulterm,
				 bool *allnul, bool *allnonnul,
				 ssa_name_limit_t &snlim);
  bool get_len_or_size (gimple *stmt, tree arg, int idx,
			unsigned HOST_WIDE_INT lenrng[2],
			unsigned HOST_WIDE_INT *size, bool *nulterm);

  gimple_ranger m_ranger;

  /* A pointer_query object to store information about pointers and
     their targets in.  */
  pointer_query ptr_qry;

  gimple_stmt_iterator m_gsi;

  /* Flag that will trigger TODO_cleanup_cfg to be returned in strlen
     execute function.  */
  bool m_cleanup_cfg;
};

/* Return:

   *  +1  if SI is known to start with more than OFF nonzero characters.

   *   0  if SI is known to start with exactly OFF nonzero characters.

   *  -1  if SI either does not start with OFF nonzero characters
	  or the relationship between the number of leading nonzero
	  characters in SI and OFF is unknown.  */

static int
compare_nonzero_chars (strinfo *si, unsigned HOST_WIDE_INT off)
{
  if (si->nonzero_chars
      && TREE_CODE (si->nonzero_chars) == INTEGER_CST)
    return compare_tree_int (si->nonzero_chars, off);
  else
    return -1;
}

/* Same as above but suitable also for strings with non-constant lengths.
   Uses RVALS to determine length range.  */

static int
compare_nonzero_chars (strinfo *si, gimple *stmt,
		       unsigned HOST_WIDE_INT off,
		       range_query *rvals)
{
  if (!si->nonzero_chars)
    return -1;

  if (TREE_CODE (si->nonzero_chars) == INTEGER_CST)
    return compare_tree_int (si->nonzero_chars, off);

  if (!rvals || TREE_CODE (si->nonzero_chars) != SSA_NAME)
    return -1;

  value_range vr;
  if (!rvals->range_of_expr (vr, si->nonzero_chars, stmt)
      || vr.varying_p ()
      || vr.undefined_p ())
    return -1;

  /* If the offset is less than the minimum length or if the bounds
     of the length range are equal return the result of the comparison
     same as in the constant case.  Otherwise return a conservative
     result.  */
  signop sign = TYPE_SIGN (vr.type ());
  unsigned prec = TYPE_PRECISION (vr.type ());
  int cmpmin = wi::cmp (vr.lower_bound (), wi::uhwi (off, prec), sign);
  if (cmpmin > 0 || vr.singleton_p ())
    return cmpmin;

  return -1;
}

/* Return true if SI is known to be a zero-length string.  */

static inline bool
zero_length_string_p (strinfo *si)
{
  return si->full_string_p && integer_zerop (si->nonzero_chars);
}

/* Return strinfo vector entry IDX.  */

static inline strinfo *
get_strinfo (int idx)
{
  if (vec_safe_length (stridx_to_strinfo) <= (unsigned int) idx)
    return NULL;
  return (*stridx_to_strinfo)[idx];
}

/* Get the next strinfo in the chain after SI, or null if none.  */

static inline strinfo *
get_next_strinfo (strinfo *si)
{
  if (si->next == 0)
    return NULL;
  strinfo *nextsi = get_strinfo (si->next);
  if (nextsi == NULL || nextsi->first != si->first || nextsi->prev != si->idx)
    return NULL;
  return nextsi;
}

/* Helper function for get_stridx.  Return the strinfo index of the address
   of EXP, which is available in PTR if nonnull.  If OFFSET_OUT, it is
   OK to return the index for some X <= &EXP and store &EXP - X in
   *OFFSET_OUT.  When RVALS is nonnull uses it to determine range
   information.  */

static int
get_addr_stridx (tree exp, gimple *stmt,
		 tree ptr, unsigned HOST_WIDE_INT *offset_out,
		 range_query *rvals = NULL)
{
  HOST_WIDE_INT off;
  struct stridxlist *list, *last = NULL;
  tree base;

  if (!decl_to_stridxlist_htab)
    return 0;

  poly_int64 poff;
  base = get_addr_base_and_unit_offset (exp, &poff);
  if (base == NULL || !DECL_P (base) || !poff.is_constant (&off))
    return 0;

  list = decl_to_stridxlist_htab->get (base);
  if (list == NULL)
    return 0;

  do
    {
      if (list->offset == off)
	{
	  if (offset_out)
	    *offset_out = 0;
	  return list->idx;
	}
      if (list->offset > off)
	return 0;
      last = list;
      list = list->next;
    }
  while (list);

  if ((offset_out || ptr) && last && last->idx > 0)
    {
      unsigned HOST_WIDE_INT rel_off
	= (unsigned HOST_WIDE_INT) off - last->offset;
      strinfo *si = get_strinfo (last->idx);
      if (si && compare_nonzero_chars (si, stmt, rel_off, rvals) >= 0)
	{
	  if (offset_out)
	    {
	      *offset_out = rel_off;
	      return last->idx;
	    }
	  else
	    return get_stridx_plus_constant (si, rel_off, ptr);
	}
    }
  return 0;
}

/* Returns string index for EXP.  When EXP is an SSA_NAME that refers
   to a known strinfo with an offset and OFFRNG is non-null, sets
   both elements of the OFFRNG array to the range of the offset and
   returns the index of the known strinfo.  In this case the result
   must not be used in for functions that modify the string.
   When nonnull, uses RVALS to determine range information.  */

static int
get_stridx (tree exp, gimple *stmt,
	    wide_int offrng[2] = NULL, range_query *rvals = NULL)
{
  if (offrng)
    offrng[0] = offrng[1] = wi::zero (TYPE_PRECISION (ptrdiff_type_node));

  if (TREE_CODE (exp) == SSA_NAME)
    {
      if (ssa_ver_to_stridx[SSA_NAME_VERSION (exp)])
	return ssa_ver_to_stridx[SSA_NAME_VERSION (exp)];

      tree e = exp;
      int last_idx = 0;
      HOST_WIDE_INT offset = 0;
      /* Follow a chain of at most 5 assignments.  */
      for (int i = 0; i < 5; i++)
	{
	  gimple *def_stmt = SSA_NAME_DEF_STMT (e);
	  if (!is_gimple_assign (def_stmt))
	    return last_idx;

	  tree_code rhs_code = gimple_assign_rhs_code (def_stmt);
	  tree ptr, off;

	  if (rhs_code == ADDR_EXPR)
	    {
	      /* Handle indices/offsets into VLAs which are implemented
	         as pointers to arrays.  */
	      ptr = gimple_assign_rhs1 (def_stmt);
	      ptr = TREE_OPERAND (ptr, 0);

	      /* Handle also VLAs of types larger than char.  */
	      if (tree eltsize = TYPE_SIZE_UNIT (TREE_TYPE (ptr)))
		{
		  if (TREE_CODE (ptr) == ARRAY_REF)
		    {
		      off = TREE_OPERAND (ptr, 1);
		      ptr = TREE_OPERAND (ptr, 0);
		      if (!integer_onep (eltsize))
			{
			  /* Scale the array index by the size of the element
			     type in the rare case that it's greater than
			     the typical 1 for char, making sure both operands
			     have the same type.  */
			  eltsize = fold_convert (ssizetype, eltsize);
			  off = fold_convert (ssizetype, off);
			  off = fold_build2 (MULT_EXPR, ssizetype, off, eltsize);
			}
		    }
		  else
		    off = integer_zero_node;
		}
	      else
		return 0;

	      if (TREE_CODE (ptr) != MEM_REF)
	        return 0;

	      /* Add the MEM_REF byte offset.  */
	      tree mem_off = TREE_OPERAND (ptr, 1);
	      off = fold_build2 (PLUS_EXPR, TREE_TYPE (off), off, mem_off);
	      ptr = TREE_OPERAND (ptr, 0);
	    }
	  else if (rhs_code == POINTER_PLUS_EXPR)
	    {
	      ptr = gimple_assign_rhs1 (def_stmt);
	      off = gimple_assign_rhs2 (def_stmt);
	    }
	  else
	    return 0;

	  if (TREE_CODE (ptr) != SSA_NAME)
	    return 0;

	  if (!tree_fits_shwi_p (off))
	    {
	      if (int idx = ssa_ver_to_stridx[SSA_NAME_VERSION (ptr)])
		if (offrng)
		  {
		    /* Only when requested by setting OFFRNG to non-null,
		       return the index corresponding to the SSA_NAME.
		       Do this irrespective of the whether the offset
		       is known.  */
		    if (get_range (off, def_stmt, offrng, rvals))
		      {
			/* When the offset range is known, increment it
			   it by the constant offset computed in prior
			   iterations and store it in the OFFRNG array.  */
 			offrng[0] += offset;
			offrng[1] += offset;
		      }
		    else
		      {
			/* When the offset range cannot be determined
			   store [0, SIZE_MAX] and let the caller decide
			   if the offset matters.  */
			offrng[1] = wi::to_wide (TYPE_MAX_VALUE (sizetype));
			offrng[0] = wi::zero (offrng[1].get_precision ());
		      }
		    return idx;
		  }
	      return 0;
	    }

	  HOST_WIDE_INT this_off = tree_to_shwi (off);
	  if (offrng)
	    {
	      offrng[0] += wi::shwi (this_off, offrng->get_precision ());
	      offrng[1] += offrng[0];
	    }

	  if (this_off < 0)
	    return last_idx;

	  offset = (unsigned HOST_WIDE_INT) offset + this_off;
	  if (offset < 0)
	    return last_idx;

	  if (int idx = ssa_ver_to_stridx[SSA_NAME_VERSION (ptr)])
	    {
	      strinfo *si = get_strinfo (idx);
	      if (si)
		{
		  if (compare_nonzero_chars (si, offset) >= 0)
		    return get_stridx_plus_constant (si, offset, exp);

		  if (offrng)
		    last_idx = idx;
		}
	    }
	  e = ptr;
	}

      return last_idx;
    }

  if (TREE_CODE (exp) == ADDR_EXPR)
    {
      int idx = get_addr_stridx (TREE_OPERAND (exp, 0), stmt, exp, NULL);
      if (idx != 0)
	return idx;
    }

  const char *p = c_getstr (exp);
  if (p)
    return ~(int) strlen (p);

  return 0;
}

/* Return true if strinfo vector is shared with the immediate dominator.  */

static inline bool
strinfo_shared (void)
{
  return vec_safe_length (stridx_to_strinfo)
	 && (*stridx_to_strinfo)[0] != NULL;
}

/* Unshare strinfo vector that is shared with the immediate dominator.  */

static void
unshare_strinfo_vec (void)
{
  strinfo *si;
  unsigned int i = 0;

  gcc_assert (strinfo_shared ());
  stridx_to_strinfo = vec_safe_copy (stridx_to_strinfo);
  for (i = 1; vec_safe_iterate (stridx_to_strinfo, i, &si); ++i)
    if (si != NULL)
      si->refcount++;
  (*stridx_to_strinfo)[0] = NULL;
}

/* Attempt to create a string index for exp, ADDR_EXPR's operand.
   Return a pointer to the location where the string index can
   be stored (if 0) or is stored, or NULL if this can't be tracked.  */

static int *
addr_stridxptr (tree exp)
{
  HOST_WIDE_INT off;

  poly_int64 poff;
  tree base = get_addr_base_and_unit_offset (exp, &poff);
  if (base == NULL_TREE || !DECL_P (base) || !poff.is_constant (&off))
    return NULL;

  if (!decl_to_stridxlist_htab)
    {
      decl_to_stridxlist_htab
       	= new hash_map<tree_decl_hash, stridxlist> (64);
      gcc_obstack_init (&stridx_obstack);
    }

  bool existed;
  stridxlist *list = &decl_to_stridxlist_htab->get_or_insert (base, &existed);
  if (existed)
    {
      int i;
      stridxlist *before = NULL;
      for (i = 0; i < 32; i++)
	{
	  if (list->offset == off)
	    return &list->idx;
	  if (list->offset > off && before == NULL)
	    before = list;
	  if (list->next == NULL)
	    break;
	  list = list->next;
	}
      if (i == 32)
	return NULL;
      if (before)
	{
	  list = before;
	  before = XOBNEW (&stridx_obstack, struct stridxlist);
	  *before = *list;
	  list->next = before;
	  list->offset = off;
	  list->idx = 0;
	  return &list->idx;
	}
      list->next = XOBNEW (&stridx_obstack, struct stridxlist);
      list = list->next;
    }

  list->next = NULL;
  list->offset = off;
  list->idx = 0;
  return &list->idx;
}

/* Create a new string index, or return 0 if reached limit.  */

static int
new_stridx (tree exp)
{
  int idx;
  if (max_stridx >= param_max_tracked_strlens)
    return 0;
  if (TREE_CODE (exp) == SSA_NAME)
    {
      if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp))
	return 0;
      idx = max_stridx++;
      ssa_ver_to_stridx[SSA_NAME_VERSION (exp)] = idx;
      return idx;
    }
  if (TREE_CODE (exp) == ADDR_EXPR)
    {
      int *pidx = addr_stridxptr (TREE_OPERAND (exp, 0));
      if (pidx != NULL)
	{
	  gcc_assert (*pidx == 0);
	  *pidx = max_stridx++;
	  return *pidx;
	}
    }
  return 0;
}

/* Like new_stridx, but for ADDR_EXPR's operand instead.  */

static int
new_addr_stridx (tree exp)
{
  int *pidx;
  if (max_stridx >= param_max_tracked_strlens)
    return 0;
  pidx = addr_stridxptr (exp);
  if (pidx != NULL)
    {
      gcc_assert (*pidx == 0);
      *pidx = max_stridx++;
      return *pidx;
    }
  return 0;
}

/* Create a new strinfo.  */

static strinfo *
new_strinfo (tree ptr, int idx, tree nonzero_chars, bool full_string_p)
{
  strinfo *si = strinfo_pool.allocate ();
  si->nonzero_chars = nonzero_chars;
  STRIP_USELESS_TYPE_CONVERSION (ptr);
  si->ptr = ptr;
  si->stmt = NULL;
  si->alloc = NULL;
  si->endptr = NULL_TREE;
  si->refcount = 1;
  si->idx = idx;
  si->first = 0;
  si->prev = 0;
  si->next = 0;
  si->writable = false;
  si->dont_invalidate = false;
  si->full_string_p = full_string_p;
  return si;
}

/* Decrease strinfo refcount and free it if not referenced anymore.  */

static inline void
free_strinfo (strinfo *si)
{
  if (si && --si->refcount == 0)
    strinfo_pool.remove (si);
}

/* Set strinfo in the vector entry IDX to SI.  */

static inline void
set_strinfo (int idx, strinfo *si)
{
  if (vec_safe_length (stridx_to_strinfo) && (*stridx_to_strinfo)[0])
    unshare_strinfo_vec ();
  if (vec_safe_length (stridx_to_strinfo) <= (unsigned int) idx)
    vec_safe_grow_cleared (stridx_to_strinfo, idx + 1, true);
  (*stridx_to_strinfo)[idx] = si;
}

/* Return the first strinfo in the related strinfo chain
   if all strinfos in between belong to the chain, otherwise NULL.  */

static strinfo *
verify_related_strinfos (strinfo *origsi)
{
  strinfo *si = origsi, *psi;

  if (origsi->first == 0)
    return NULL;
  for (; si->prev; si = psi)
    {
      if (si->first != origsi->first)
	return NULL;
      psi = get_strinfo (si->prev);
      if (psi == NULL)
	return NULL;
      if (psi->next != si->idx)
	return NULL;
    }
  if (si->idx != si->first)
    return NULL;
  return si;
}

/* Set SI's endptr to ENDPTR and compute its length based on SI->ptr.
   Use LOC for folding.  */

static void
set_endptr_and_length (location_t loc, strinfo *si, tree endptr)
{
  si->endptr = endptr;
  si->stmt = NULL;
  tree start_as_size = fold_convert_loc (loc, size_type_node, si->ptr);
  tree end_as_size = fold_convert_loc (loc, size_type_node, endptr);
  si->nonzero_chars = fold_build2_loc (loc, MINUS_EXPR, size_type_node,
				       end_as_size, start_as_size);
  si->full_string_p = true;
}

/* Return the string length, or NULL if it can't be computed.
   The length may but need not be constant.  Instead, it might be
   the result of a strlen() call.  */

static tree
get_string_length (strinfo *si)
{
  /* If the length has already been computed return it if it's exact
     (i.e., the string is nul-terminated at NONZERO_CHARS), or return
     null if it isn't.  */
  if (si->nonzero_chars)
    return si->full_string_p ? si->nonzero_chars : NULL;

  /* If the string is the result of one of the built-in calls below
     attempt to compute the length from the call statement.  */
  if (si->stmt)
    {
      gimple *stmt = si->stmt, *lenstmt;
      tree callee, lhs, fn, tem;
      location_t loc;
      gimple_stmt_iterator gsi;

      gcc_assert (is_gimple_call (stmt));
      callee = gimple_call_fndecl (stmt);
      gcc_assert (callee && fndecl_built_in_p (callee, BUILT_IN_NORMAL));
      lhs = gimple_call_lhs (stmt);
      /* unshare_strinfo is intentionally not called here.  The (delayed)
	 transformation of strcpy or strcat into stpcpy is done at the place
	 of the former strcpy/strcat call and so can affect all the strinfos
	 with the same stmt.  If they were unshared before and transformation
	 has been already done, the handling of BUILT_IN_STPCPY{,_CHK} should
	 just compute the right length.  */
      switch (DECL_FUNCTION_CODE (callee))
	{
	case BUILT_IN_STRCAT:
	case BUILT_IN_STRCAT_CHK:
	  gsi = gsi_for_stmt (stmt);
	  fn = builtin_decl_implicit (BUILT_IN_STRLEN);
	  gcc_assert (lhs == NULL_TREE);
	  tem = unshare_expr (gimple_call_arg (stmt, 0));
	  lenstmt = gimple_build_call (fn, 1, tem);
	  lhs = make_ssa_name (TREE_TYPE (TREE_TYPE (fn)), lenstmt);
	  gimple_call_set_lhs (lenstmt, lhs);
	  gimple_set_vuse (lenstmt, gimple_vuse (stmt));
	  gsi_insert_before (&gsi, lenstmt, GSI_SAME_STMT);
	  tem = gimple_call_arg (stmt, 0);
          if (!ptrofftype_p (TREE_TYPE (lhs)))
            {
              lhs = convert_to_ptrofftype (lhs);
              lhs = force_gimple_operand_gsi (&gsi, lhs, true, NULL_TREE,
                                              true, GSI_SAME_STMT);
            }
	  lenstmt = gimple_build_assign
			(make_ssa_name (TREE_TYPE (gimple_call_arg (stmt, 0))),
			 POINTER_PLUS_EXPR,tem, lhs);
	  gsi_insert_before (&gsi, lenstmt, GSI_SAME_STMT);
	  gimple_call_set_arg (stmt, 0, gimple_assign_lhs (lenstmt));
	  lhs = NULL_TREE;
	  /* FALLTHRU */
	case BUILT_IN_STRCPY:
	case BUILT_IN_STRCPY_CHK:
	  gcc_assert (builtin_decl_implicit_p (BUILT_IN_STPCPY));
	  if (gimple_call_num_args (stmt) == 2)
	    fn = builtin_decl_implicit (BUILT_IN_STPCPY);
	  else
	    fn = builtin_decl_explicit (BUILT_IN_STPCPY_CHK);
	  gcc_assert (lhs == NULL_TREE);
	  if (dump_file && (dump_flags & TDF_DETAILS) != 0)
	    {
	      fprintf (dump_file, "Optimizing: ");
	      print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
	    }
	  gimple_call_set_fndecl (stmt, fn);
	  lhs = make_ssa_name (TREE_TYPE (TREE_TYPE (fn)), stmt);
	  gimple_call_set_lhs (stmt, lhs);
	  update_stmt (stmt);
	  if (dump_file && (dump_flags & TDF_DETAILS) != 0)
	    {
	      fprintf (dump_file, "into: ");
	      print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
	    }
	  /* FALLTHRU */
	case BUILT_IN_STPCPY:
	case BUILT_IN_STPCPY_CHK:
	  gcc_assert (lhs != NULL_TREE);
	  loc = gimple_location (stmt);
	  set_endptr_and_length (loc, si, lhs);
	  for (strinfo *chainsi = verify_related_strinfos (si);
	       chainsi != NULL;
	       chainsi = get_next_strinfo (chainsi))
	    if (chainsi->nonzero_chars == NULL)
	      set_endptr_and_length (loc, chainsi, lhs);
	  break;
	case BUILT_IN_ALLOCA:
	case BUILT_IN_ALLOCA_WITH_ALIGN:
	case BUILT_IN_MALLOC:
	  break;
	/* BUILT_IN_CALLOC always has si->nonzero_chars set.  */
	default:
	  gcc_unreachable ();
	  break;
	}
    }

  return si->nonzero_chars;
}

/* Dump strlen data to FP for statement STMT.  When non-null, RVALS
   points to the valuation engine used to calculate ranges, and is
   used to dump strlen range for non-constant results.  */

DEBUG_FUNCTION void
dump_strlen_info (FILE *fp, gimple *stmt, range_query *rvals)
{
  if (stmt)
    {
      fprintf (fp, "\nDumping strlen pass data after ");
      print_gimple_expr (fp, stmt, TDF_LINENO);
      fputc ('\n', fp);
    }
  else
    fprintf (fp, "\nDumping strlen pass data\n");

  fprintf (fp, "max_stridx = %i\n", max_stridx);
  fprintf (fp, "ssa_ver_to_stridx has %u elements\n",
	   ssa_ver_to_stridx.length ());
  fprintf (fp, "stridx_to_strinfo");
  if (stridx_to_strinfo)
    {
      fprintf (fp, " has %u elements\n", stridx_to_strinfo->length ());
      for (unsigned i = 0; i != stridx_to_strinfo->length (); ++i)
	{
	  if (strinfo *si = (*stridx_to_strinfo)[i])
	    {
	      if (!si->idx)
		continue;
	      fprintf (fp, "  idx = %i", si->idx);
	      if (si->ptr)
		{
		  fprintf (fp, ", ptr = ");
		  print_generic_expr (fp, si->ptr);
		}

	      if (si->nonzero_chars)
		{
		  fprintf (fp, ", nonzero_chars = ");
		  print_generic_expr (fp, si->nonzero_chars);
		  if (TREE_CODE (si->nonzero_chars) == SSA_NAME)
		    {
		      value_range vr;
		      if (rvals)
			rvals->range_of_expr (vr, si->nonzero_chars,
					      si->stmt);
		      else
			get_range_query (cfun)->range_of_expr (vr,
							si->nonzero_chars);
		      vr.dump (fp);
		    }
		}

	      fprintf (fp, ", refcount = %i", si->refcount);
	      if (si->stmt)
		{
		  fprintf (fp, ", stmt = ");
		  print_gimple_expr (fp, si->stmt, 0);
		}
	      if (si->alloc)
		{
		  fprintf (fp, ", alloc = ");
		  print_gimple_expr (fp, si->alloc, 0);
		}
	      if (si->writable)
		fprintf (fp, ", writable");
	      if (si->dont_invalidate)
		fprintf (fp, ", dont_invalidate");
	      if (si->full_string_p)
		fprintf (fp, ", full_string_p");
	      if (strinfo *next = get_next_strinfo (si))
		{
		  fprintf (fp, ", {");
		  do
		    fprintf (fp, "%i%s", next->idx, next->first ? ", " : "");
		  while ((next = get_next_strinfo (next)));
		  fprintf (fp, "}");
		}
	      fputs ("\n", fp);
	    }
	}
    }
  else
    fprintf (fp, " = null\n");

  fprintf (fp, "decl_to_stridxlist_htab");
  if (decl_to_stridxlist_htab)
    {
      fputs ("\n", fp);
      typedef decl_to_stridxlist_htab_t::iterator iter_t;
      for (iter_t it = decl_to_stridxlist_htab->begin ();
	   it != decl_to_stridxlist_htab->end (); ++it)
	{
	  tree decl = (*it).first;
	  stridxlist *list = &(*it).second;
	  fprintf (fp, "  decl = ");
	  print_generic_expr (fp, decl);
	  if (list)
	    {
	      fprintf (fp, ", offsets = {");
	      for (; list; list = list->next)
		fprintf (fp, "%lli%s", (long long) list->offset,
			 list->next ? ", " : "");
	      fputs ("}", fp);
	    }
	  fputs ("\n", fp);
	}
    }
  else
    fprintf (fp, " = null\n");

  if (laststmt.stmt)
    {
      fprintf (fp, "laststmt = ");
      print_gimple_expr (fp, laststmt.stmt, 0);
      fprintf (fp, ", len = ");
      print_generic_expr (fp, laststmt.len);
      fprintf (fp, ", stridx = %i\n", laststmt.stridx);
    }
}

/* Helper of get_range_strlen_dynamic().  See below.  */

static bool
get_range_strlen_phi (tree src, gphi *phi,
		      c_strlen_data *pdata, bitmap visited,
		      pointer_query *ptr_qry, unsigned *pssa_def_max)
{
  if (!bitmap_set_bit (visited, SSA_NAME_VERSION (src)))
    return true;

  if (*pssa_def_max == 0)
    return false;

  --*pssa_def_max;

  /* Iterate over the PHI arguments and determine the minimum and maximum
     length/size of each and incorporate them into the overall result.  */
  for (unsigned i = 0; i != gimple_phi_num_args (phi); ++i)
    {
      tree arg = gimple_phi_arg_def (phi, i);
      if (arg == gimple_phi_result (phi))
	continue;

      c_strlen_data argdata = { };
      if (!get_range_strlen_dynamic (arg, phi, &argdata, visited, ptr_qry,
				     pssa_def_max))
	{
	  pdata->maxlen = build_all_ones_cst (size_type_node);
	  continue;
	}

      /* Set the DECL of an unterminated array this argument refers to
	 if one hasn't been found yet.  */
      if (!pdata->decl && argdata.decl)
	pdata->decl = argdata.decl;

      if (!argdata.minlen
	  || (integer_zerop (argdata.minlen)
	      && (!argdata.maxbound
		  || integer_all_onesp (argdata.maxbound))
	      && integer_all_onesp (argdata.maxlen)))
	{
	  /* Set the upper bound of the length to unbounded.  */
	  pdata->maxlen = build_all_ones_cst (size_type_node);
	  continue;
	}

      /* Adjust the minimum and maximum length determined so far and
	 the upper bound on the array size.  */
      if (TREE_CODE (argdata.minlen) == INTEGER_CST
	  && (!pdata->minlen
	      || tree_int_cst_lt (argdata.minlen, pdata->minlen)))
	pdata->minlen = argdata.minlen;

      if (TREE_CODE (argdata.maxlen) == INTEGER_CST
	  && (!pdata->maxlen
	      || (argdata.maxlen
		  && tree_int_cst_lt (pdata->maxlen, argdata.maxlen))))
	pdata->maxlen = argdata.maxlen;

      if (!pdata->maxbound
	  || TREE_CODE (pdata->maxbound) != INTEGER_CST
	  || (argdata.maxbound
	      && tree_int_cst_lt (pdata->maxbound, argdata.maxbound)
	      && !integer_all_onesp (argdata.maxbound)))
	pdata->maxbound = argdata.maxbound;
    }

  return true;
}

/* Return the maximum possible length of the string PTR that's less
   than MAXLEN given the size of the object of subobject it points
   to at the given STMT.  MAXLEN is the maximum length of the string
   determined so far.  Return null when no such maximum can be
   determined.  */

static tree
get_maxbound (tree ptr, gimple *stmt, offset_int maxlen,
	      pointer_query *ptr_qry)
{
  access_ref aref;
  if (!ptr_qry->get_ref (ptr, stmt, &aref))
    return NULL_TREE;

  offset_int sizrem = aref.size_remaining ();
  if (sizrem <= 0)
    return NULL_TREE;

  if (sizrem < maxlen)
    maxlen = sizrem - 1;

  /* Try to determine the maximum from the subobject at the offset.
     This handles MEM [&some-struct, member-offset] that's often
     the result of folding COMPONENT_REF [some-struct, member].  */
  tree reftype = TREE_TYPE (aref.ref);
  if (!RECORD_OR_UNION_TYPE_P (reftype)
      || aref.offrng[0] != aref.offrng[1]
      || !wi::fits_shwi_p (aref.offrng[0]))
    return wide_int_to_tree (size_type_node, maxlen);

  HOST_WIDE_INT off = aref.offrng[0].to_shwi ();
  tree fld = field_at_offset (reftype, NULL_TREE, off);
  if (!fld || !DECL_SIZE_UNIT (fld))
    return wide_int_to_tree (size_type_node, maxlen);

  offset_int size = wi::to_offset (DECL_SIZE_UNIT (fld));
  if (maxlen < size)
    return wide_int_to_tree (size_type_node, maxlen);

  return wide_int_to_tree (size_type_node, size - 1);
}

/* Attempt to determine the length of the string SRC.  On success, store
   the length in *PDATA and return true.  Otherwise, return false.
   VISITED is a bitmap of visited PHI nodes.  RVALS points to the valuation
   engine used to calculate ranges.  PSSA_DEF_MAX to an SSA_NAME
   assignment limit used to prevent runaway recursion.  */

static bool
get_range_strlen_dynamic (tree src, gimple *stmt,
			  c_strlen_data *pdata, bitmap visited,
			  pointer_query *ptr_qry, unsigned *pssa_def_max)
{
  int idx = get_stridx (src, stmt);
  if (!idx)
    {
      if (TREE_CODE (src) == SSA_NAME)
	{
	  gimple *def_stmt = SSA_NAME_DEF_STMT (src);
	  if (gphi *phi = dyn_cast<gphi *>(def_stmt))
	    return get_range_strlen_phi (src, phi, pdata, visited, ptr_qry,
					 pssa_def_max);
	}

      /* Return success regardless of the result and handle *PDATA
	 in the caller.  */
      get_range_strlen (src, pdata, 1);
      return true;
    }

  if (idx < 0)
    {
      /* SRC is a string of constant length.  */
      pdata->minlen = build_int_cst (size_type_node, ~idx);
      pdata->maxlen = pdata->minlen;
      pdata->maxbound = pdata->maxlen;
      return true;
    }

  if (strinfo *si = get_strinfo (idx))
    {
      pdata->minlen = get_string_length (si);
      if (!pdata->minlen && si->nonzero_chars)
	{
	  if (TREE_CODE (si->nonzero_chars) == INTEGER_CST)
	    pdata->minlen = si->nonzero_chars;
	  else if (TREE_CODE (si->nonzero_chars) == SSA_NAME)
	    {
	      value_range vr;
	      ptr_qry->rvals->range_of_expr (vr, si->nonzero_chars, si->stmt);
	      if (vr.undefined_p () || vr.varying_p ())
		pdata->minlen = build_zero_cst (size_type_node);
	      else
		{
		  tree type = vr.type ();
		  pdata->minlen = wide_int_to_tree (type, vr.lower_bound ());
		  pdata->maxlen = wide_int_to_tree (type, vr.upper_bound ());
		}
	    }
	  else
	    pdata->minlen = build_zero_cst (size_type_node);

	  tree base = si->ptr;
	  if (TREE_CODE (base) == ADDR_EXPR)
	    base = TREE_OPERAND (base, 0);

	  HOST_WIDE_INT off;
	  poly_int64 poff;
	  base = get_addr_base_and_unit_offset (base, &poff);
	  if (base
	      && DECL_P (base)
	      && TREE_CODE (TREE_TYPE (base)) == ARRAY_TYPE
	      && TYPE_SIZE_UNIT (TREE_TYPE (base))
	      && poff.is_constant (&off))
	    {
	      tree basetype = TREE_TYPE (base);
	      tree size = TYPE_SIZE_UNIT (basetype);
	      if (TREE_CODE (size) == INTEGER_CST)
		{
		  ++off;   /* Increment for the terminating nul.  */
		  tree toffset = build_int_cst (size_type_node, off);
		  pdata->maxlen = fold_build2 (MINUS_EXPR, size_type_node, size,
					       toffset);
		  pdata->maxbound = pdata->maxlen;
		}
	      else	
		pdata->maxlen = build_all_ones_cst (size_type_node);
	    }
	  else
	    pdata->maxlen = build_all_ones_cst (size_type_node);
	}
      else if (pdata->minlen && TREE_CODE (pdata->minlen) == SSA_NAME)
	{
	  value_range vr;
	  ptr_qry->rvals->range_of_expr (vr, si->nonzero_chars, stmt);
	  if (vr.varying_p () || vr.undefined_p ())
	    {
	      pdata->minlen = build_zero_cst (size_type_node);
	      pdata->maxlen = build_all_ones_cst (size_type_node);
	    }
	  else
	    {
	      tree type = vr.type ();
	      pdata->minlen = wide_int_to_tree (type, vr.lower_bound ());
	      pdata->maxlen = wide_int_to_tree (type, vr.upper_bound ());
	      offset_int max = offset_int::from (vr.upper_bound (0), SIGNED);
	      if (tree maxbound = get_maxbound (si->ptr, stmt, max, ptr_qry))
		pdata->maxbound = maxbound;
	      else
		pdata->maxbound = pdata->maxlen;
	    }
	}
      else if (pdata->minlen && TREE_CODE (pdata->minlen) == INTEGER_CST)
	{
	  pdata->maxlen = pdata->minlen;
	  pdata->maxbound = pdata->minlen;
	}
      else
	{
	  /* For PDATA->MINLEN that's a non-constant expression such
	     as PLUS_EXPR whose value range is unknown, set the bounds
	     to zero and SIZE_MAX.  */
	  pdata->minlen = build_zero_cst (size_type_node);
	  pdata->maxlen = build_all_ones_cst (size_type_node);
	}

      return true;
    }

  return false;
}

/* Analogous to get_range_strlen but for dynamically created strings,
   i.e., those created by calls to strcpy as opposed to just string
   constants.
   Try to obtain the range of the lengths of the string(s) referenced
   by SRC, or the size of the largest array SRC refers to if the range
   of lengths cannot be determined, and store all in *PDATA.  RVALS
   points to the valuation engine used to calculate ranges.  */

void
get_range_strlen_dynamic (tree src, gimple *stmt, c_strlen_data *pdata,
			  pointer_query &ptr_qry)
{
  auto_bitmap visited;
  tree maxbound = pdata->maxbound;

  unsigned limit = param_ssa_name_def_chain_limit;
  if (!get_range_strlen_dynamic (src, stmt, pdata, visited, &ptr_qry, &limit))
    {
      /* On failure extend the length range to an impossible maximum
	 (a valid MAXLEN must be less than PTRDIFF_MAX - 1).  Other
	 members can stay unchanged regardless.  */
      pdata->minlen = ssize_int (0);
      pdata->maxlen = build_all_ones_cst (size_type_node);
    }
  else if (!pdata->minlen)
    pdata->minlen = ssize_int (0);

  /* If it's unchanged from it initial non-null value, set the conservative
     MAXBOUND to SIZE_MAX.  Otherwise leave it null (if it is null).  */
  if (maxbound && pdata->maxbound == maxbound)
    pdata->maxbound = build_all_ones_cst (size_type_node);
}

/* Invalidate string length information for strings whose length might
   change due to stores in STMT, except those marked DONT_INVALIDATE.
   For string-modifying statements, ZERO_WRITE is set when the statement
   wrote only zeros.
   Returns true if any STRIDX_TO_STRINFO entries were considered
   for invalidation.  */

static bool
maybe_invalidate (gimple *stmt, bool zero_write = false)
{
  if (dump_file && (dump_flags & TDF_DETAILS))
    {
      fprintf (dump_file, "%s called for ", __func__);
      print_gimple_stmt (dump_file, stmt, TDF_LINENO);
    }

  strinfo *si;
  bool nonempty = false;

  for (unsigned i = 1; vec_safe_iterate (stridx_to_strinfo, i, &si); ++i)
    {
      if (si == NULL || !POINTER_TYPE_P (TREE_TYPE (si->ptr)))
	continue;

      nonempty = true;

      /* Unconditionally reset DONT_INVALIDATE.  */
      bool dont_invalidate = si->dont_invalidate;
      si->dont_invalidate = false;

      if (dont_invalidate)
	continue;

      ao_ref r;
      tree size = si->nonzero_chars;
      ao_ref_init_from_ptr_and_size (&r, si->ptr, size);
      /* Include the terminating nul in the size of the string
	 to consider when determining possible clobber.  But do not
	 add it to 'size' since we don't know whether it would
	 actually fit the allocated area.  */
      if (known_size_p (r.size))
	{
	  if (known_le (r.size, HOST_WIDE_INT_MAX - BITS_PER_UNIT))
	    r.max_size += BITS_PER_UNIT;
	  else
	    r.max_size = -1;
	}
      if (stmt_may_clobber_ref_p_1 (stmt, &r))
	{
	  if (dump_file && (dump_flags & TDF_DETAILS))
	    {
	      fputs ("  statement may clobber object ", dump_file);
	      print_generic_expr (dump_file, si->ptr);
	      if (size && tree_fits_uhwi_p (size))
		fprintf (dump_file, " " HOST_WIDE_INT_PRINT_UNSIGNED
			 " bytes in size", tree_to_uhwi (size));
	      fputc ('\n', dump_file);
	    }

	  set_strinfo (i, NULL);
	  free_strinfo (si);
	  continue;
	}

      if (size
	  && !zero_write
	  && si->stmt
	  && is_gimple_call (si->stmt)
	  && (DECL_FUNCTION_CODE (gimple_call_fndecl (si->stmt))
	      == BUILT_IN_CALLOC))
	{
	  /* If the clobber test above considered the length of
	     the string (including the nul), then for (potentially)
	     non-zero writes that might modify storage allocated by
	     calloc consider the whole object and if it might be
	     clobbered by the statement reset the statement.  */
	  ao_ref_init_from_ptr_and_size (&r, si->ptr, NULL_TREE);
	  if (stmt_may_clobber_ref_p_1 (stmt, &r))
	    si->stmt = NULL;
	}
    }

  if (dump_file && (dump_flags & TDF_DETAILS))
    fprintf (dump_file, "%s returns %i\n", __func__, nonempty);

  return nonempty;
}

/* Unshare strinfo record SI, if it has refcount > 1 or
   if stridx_to_strinfo vector is shared with some other
   bbs.  */

static strinfo *
unshare_strinfo (strinfo *si)
{
  strinfo *nsi;

  if (si->refcount == 1 && !strinfo_shared ())
    return si;

  nsi = new_strinfo (si->ptr, si->idx, si->nonzero_chars, si->full_string_p);
  nsi->stmt = si->stmt;
  nsi->alloc = si->alloc;
  nsi->endptr = si->endptr;
  nsi->first = si->first;
  nsi->prev = si->prev;
  nsi->next = si->next;
  nsi->writable = si->writable;
  set_strinfo (si->idx, nsi);
  free_strinfo (si);
  return nsi;
}

/* Attempt to create a new strinfo for BASESI + OFF, or find existing
   strinfo if there is any.  Return it's idx, or 0 if no strinfo has
   been created.  */

static int
get_stridx_plus_constant (strinfo *basesi, unsigned HOST_WIDE_INT off,
			  tree ptr)
{
  if (TREE_CODE (ptr) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr))
    return 0;

  if (compare_nonzero_chars (basesi, off) < 0
      || !tree_fits_uhwi_p (basesi->nonzero_chars))
    return 0;

  unsigned HOST_WIDE_INT nonzero_chars
    = tree_to_uhwi (basesi->nonzero_chars) - off;
  strinfo *si = basesi, *chainsi;
  if (si->first || si->prev || si->next)
    si = verify_related_strinfos (basesi);
  if (si == NULL
      || si->nonzero_chars == NULL_TREE
      || TREE_CODE (si->nonzero_chars) != INTEGER_CST)
    return 0;

  if (TREE_CODE (ptr) == SSA_NAME
      && ssa_ver_to_stridx.length () <= SSA_NAME_VERSION (ptr))
    ssa_ver_to_stridx.safe_grow_cleared (num_ssa_names, true);

  gcc_checking_assert (compare_tree_int (si->nonzero_chars, off) != -1);
  for (chainsi = si; chainsi->next; chainsi = si)
    {
      si = get_next_strinfo (chainsi);
      if (si == NULL
	  || si->nonzero_chars == NULL_TREE
	  || TREE_CODE (si->nonzero_chars) != INTEGER_CST)
	break;
      int r = compare_tree_int (si->nonzero_chars, nonzero_chars);
      if (r != 1)
	{
	  if (r == 0)
	    {
	      if (TREE_CODE (ptr) == SSA_NAME)
		ssa_ver_to_stridx[SSA_NAME_VERSION (ptr)] = si->idx;
	      else
		{
		  int *pidx = addr_stridxptr (TREE_OPERAND (ptr, 0));
		  if (pidx != NULL && *pidx == 0)
		    *pidx = si->idx;
		}
	      return si->idx;
	    }
	  break;
	}
    }

  int idx = new_stridx (ptr);
  if (idx == 0)
    return 0;
  si = new_strinfo (ptr, idx, build_int_cst (size_type_node, nonzero_chars),
		    basesi->full_string_p);
  set_strinfo (idx, si);
  if (strinfo *nextsi = get_strinfo (chainsi->next))
    {
      nextsi = unshare_strinfo (nextsi);
      si->next = nextsi->idx;
      nextsi->prev = idx;
    }
  chainsi = unshare_strinfo (chainsi);
  if (chainsi->first == 0)
    chainsi->first = chainsi->idx;
  chainsi->next = idx;
  if (chainsi->endptr == NULL_TREE && zero_length_string_p (si))
    chainsi->endptr = ptr;
  si->endptr = chainsi->endptr;
  si->prev = chainsi->idx;
  si->first = chainsi->first;
  si->writable = chainsi->writable;
  return si->idx;
}

/* Note that PTR, a pointer SSA_NAME initialized in the current stmt, points
   to a zero-length string and if possible chain it to a related strinfo
   chain whose part is or might be CHAINSI.  */

static strinfo *
zero_length_string (tree ptr, strinfo *chainsi)
{
  strinfo *si;
  int idx;
  if (ssa_ver_to_stridx.length () <= SSA_NAME_VERSION (ptr))
    ssa_ver_to_stridx.safe_grow_cleared (num_ssa_names, true);
  gcc_checking_assert (TREE_CODE (ptr) == SSA_NAME
		       && ssa_ver_to_stridx[SSA_NAME_VERSION (ptr)] == 0);

  if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr))
    return NULL;
  if (chainsi != NULL)
    {
      si = verify_related_strinfos (chainsi);
      if (si)
	{
	  do
	    {
	      /* We shouldn't mix delayed and non-delayed lengths.  */
	      gcc_assert (si->full_string_p);
	      if (si->endptr == NULL_TREE)
		{
		  si = unshare_strinfo (si);
		  si->endptr = ptr;
		}
	      chainsi = si;
	      si = get_next_strinfo (si);
	    }
	  while (si != NULL);
	  if (zero_length_string_p (chainsi))
	    {
	      if (chainsi->next)
		{
		  chainsi = unshare_strinfo (chainsi);
		  chainsi->next = 0;
		}
	      ssa_ver_to_stridx[SSA_NAME_VERSION (ptr)] = chainsi->idx;
	      return chainsi;
	    }
	}
      else
	{
	  /* We shouldn't mix delayed and non-delayed lengths.  */
	  gcc_assert (chainsi->full_string_p);
	  if (chainsi->first || chainsi->prev || chainsi->next)
	    {
	      chainsi = unshare_strinfo (chainsi);
	      chainsi->first = 0;
	      chainsi->prev = 0;
	      chainsi->next = 0;
	    }
	}
    }
  idx = new_stridx (ptr);
  if (idx == 0)
    return NULL;
  si = new_strinfo (ptr, idx, build_int_cst (size_type_node, 0), true);
  set_strinfo (idx, si);
  si->endptr = ptr;
  if (chainsi != NULL)
    {
      chainsi = unshare_strinfo (chainsi);
      if (chainsi->first == 0)
	chainsi->first = chainsi->idx;
      chainsi->next = idx;
      if (chainsi->endptr == NULL_TREE)
	chainsi->endptr = ptr;
      si->prev = chainsi->idx;
      si->first = chainsi->first;
      si->writable = chainsi->writable;
    }
  return si;
}

/* For strinfo ORIGSI whose length has been just updated, adjust other
   related strinfos so that they match the new ORIGSI.  This involves:

   - adding ADJ to the nonzero_chars fields
   - copying full_string_p from the new ORIGSI.  */

static void
adjust_related_strinfos (location_t loc, strinfo *origsi, tree adj)
{
  strinfo *si = verify_related_strinfos (origsi);

  if (si == NULL)
    return;

  while (1)
    {
      strinfo *nsi;

      if (si != origsi)
	{
	  tree tem;

	  si = unshare_strinfo (si);
	  /* We shouldn't see delayed lengths here; the caller must
	     have calculated the old length in order to calculate
	     the adjustment.  */
	  gcc_assert (si->nonzero_chars);
	  tem = fold_convert_loc (loc, TREE_TYPE (si->nonzero_chars), adj);
	  si->nonzero_chars = fold_build2_loc (loc, PLUS_EXPR,
					       TREE_TYPE (si->nonzero_chars),
					       si->nonzero_chars, tem);
	  si->full_string_p = origsi->full_string_p;

	  si->endptr = NULL_TREE;
	  si->dont_invalidate = true;
	}
      nsi = get_next_strinfo (si);
      if (nsi == NULL)
	return;
      si = nsi;
    }
}

/* Find if there are other SSA_NAME pointers equal to PTR
   for which we don't track their string lengths yet.  If so, use
   IDX for them.  */

static void
find_equal_ptrs (tree ptr, int idx)
{
  if (TREE_CODE (ptr) != SSA_NAME)
    return;
  while (1)
    {
      gimple *stmt = SSA_NAME_DEF_STMT (ptr);
      if (!is_gimple_assign (stmt))
	return;
      ptr = gimple_assign_rhs1 (stmt);
      switch (gimple_assign_rhs_code (stmt))
	{
	case SSA_NAME:
	  break;
	CASE_CONVERT:
	  if (!POINTER_TYPE_P (TREE_TYPE (ptr)))
	    return;
	  if (TREE_CODE (ptr) == SSA_NAME)
	    break;
	  if (TREE_CODE (ptr) != ADDR_EXPR)
	    return;
	  /* FALLTHRU */
	case ADDR_EXPR:
	  {
	    int *pidx = addr_stridxptr (TREE_OPERAND (ptr, 0));
	    if (pidx != NULL && *pidx == 0)
	      *pidx = idx;
	    return;
	  }
	default:
	  return;
	}

      /* We might find an endptr created in this pass.  Grow the
	 vector in that case.  */
      if (ssa_ver_to_stridx.length () <= SSA_NAME_VERSION (ptr))
	ssa_ver_to_stridx.safe_grow_cleared (num_ssa_names, true);

      if (ssa_ver_to_stridx[SSA_NAME_VERSION (ptr)] != 0)
	return;
      ssa_ver_to_stridx[SSA_NAME_VERSION (ptr)] = idx;
    }
}

/* Return true if STMT is a call to a builtin function with the right
   arguments and attributes that should be considered for optimization
   by this pass.  */

static bool
valid_builtin_call (gimple *stmt)
{
  if (!gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
    return false;

  tree callee = gimple_call_fndecl (stmt);
  switch (DECL_FUNCTION_CODE (callee))
    {
    case BUILT_IN_MEMCMP:
    case BUILT_IN_MEMCMP_EQ:
    case BUILT_IN_STRCMP:
    case BUILT_IN_STRNCMP:
    case BUILT_IN_STRCHR:
    case BUILT_IN_STRLEN:
    case BUILT_IN_STRNLEN:
      /* The above functions should be pure.  Punt if they aren't.  */
      if (gimple_vdef (stmt) || gimple_vuse (stmt) == NULL_TREE)
	return false;
      break;

    case BUILT_IN_ALLOCA:
    case BUILT_IN_ALLOCA_WITH_ALIGN:
    case BUILT_IN_CALLOC:
    case BUILT_IN_MALLOC:
    case BUILT_IN_MEMCPY:
    case BUILT_IN_MEMCPY_CHK:
    case BUILT_IN_MEMPCPY:
    case BUILT_IN_MEMPCPY_CHK:
    case BUILT_IN_MEMSET:
    case BUILT_IN_STPCPY:
    case BUILT_IN_STPCPY_CHK:
    case BUILT_IN_STPNCPY:
    case BUILT_IN_STPNCPY_CHK:
    case BUILT_IN_STRCAT:
    case BUILT_IN_STRCAT_CHK:
    case BUILT_IN_STRCPY:
    case BUILT_IN_STRCPY_CHK:
    case BUILT_IN_STRNCAT:
    case BUILT_IN_STRNCAT_CHK:
    case BUILT_IN_STRNCPY:
    case BUILT_IN_STRNCPY_CHK:
      /* The above functions should be neither const nor pure.  Punt if they
	 aren't.  */
      if (gimple_vdef (stmt) == NULL_TREE || gimple_vuse (stmt) == NULL_TREE)
	return false;
      break;

    default:
      break;
    }

  return true;
}

/* If the last .MEM setter statement before STMT is
   memcpy (x, y, strlen (y) + 1), the only .MEM use of it is STMT
   and STMT is known to overwrite x[strlen (x)], adjust the last memcpy to
   just memcpy (x, y, strlen (y)).  SI must be the zero length
   strinfo.  */

void
strlen_pass::adjust_last_stmt (strinfo *si, gimple *stmt, bool is_strcat)
{
  tree vuse, callee, len;
  struct laststmt_struct last = laststmt;
  strinfo *lastsi, *firstsi;
  unsigned len_arg_no = 2;

  laststmt.stmt = NULL;
  laststmt.len = NULL_TREE;
  laststmt.stridx = 0;

  if (last.stmt == NULL)
    return;

  vuse = gimple_vuse (stmt);
  if (vuse == NULL_TREE
      || SSA_NAME_DEF_STMT (vuse) != last.stmt
      || !has_single_use (vuse))
    return;

  gcc_assert (last.stridx > 0);
  lastsi = get_strinfo (last.stridx);
  if (lastsi == NULL)
    return;

  if (lastsi != si)
    {
      if (lastsi->first == 0 || lastsi->first != si->first)
	return;

      firstsi = verify_related_strinfos (si);
      if (firstsi == NULL)
	return;
      while (firstsi != lastsi)
	{
	  firstsi = get_next_strinfo (firstsi);
	  if (firstsi == NULL)
	    return;
	}
    }

  if (!is_strcat && !zero_length_string_p (si))
    return;

  if (is_gimple_assign (last.stmt))
    {
      gimple_stmt_iterator gsi;

      if (!integer_zerop (gimple_assign_rhs1 (last.stmt)))
	return;
      if (stmt_could_throw_p (cfun, last.stmt))
	return;
      gsi = gsi_for_stmt (last.stmt);
      unlink_stmt_vdef (last.stmt);
      release_defs (last.stmt);
      gsi_remove (&gsi, true);
      return;
    }

  if (!valid_builtin_call (last.stmt))
    return;

  callee = gimple_call_fndecl (last.stmt);
  switch (DECL_FUNCTION_CODE (callee))
    {
    case BUILT_IN_MEMCPY:
    case BUILT_IN_MEMCPY_CHK:
      break;
    default:
      return;
    }

  len = gimple_call_arg (last.stmt, len_arg_no);
  if (tree_fits_uhwi_p (len))
    {
      if (!tree_fits_uhwi_p (last.len)
	  || integer_zerop (len)
	  || tree_to_uhwi (len) != tree_to_uhwi (last.len) + 1)
	return;
      /* Don't adjust the length if it is divisible by 4, it is more efficient
	 to store the extra '\0' in that case.  */
      if ((tree_to_uhwi (len) & 3) == 0)
	return;

      /* Don't fold away an out of bounds access, as this defeats proper
	 warnings.  */
      tree dst = gimple_call_arg (last.stmt, 0);

      access_ref aref;
      tree size = compute_objsize (dst, stmt, 1, &aref, &ptr_qry);
      if (size && tree_int_cst_lt (size, len))
	return;
    }
  else if (TREE_CODE (len) == SSA_NAME)
    {
      gimple *def_stmt = SSA_NAME_DEF_STMT (len);
      if (!is_gimple_assign (def_stmt)
	  || gimple_assign_rhs_code (def_stmt) != PLUS_EXPR
	  || gimple_assign_rhs1 (def_stmt) != last.len
	  || !integer_onep (gimple_assign_rhs2 (def_stmt)))
	return;
    }
  else
    return;

  gimple_call_set_arg (last.stmt, len_arg_no, last.len);
  update_stmt (last.stmt);
}

/* For an LHS that is an SSA_NAME that is the result of a strlen()
   call, or when BOUND is non-null, of a strnlen() call, set LHS
   range info to [0, min (MAX, BOUND)] when the range includes more
   than one value and return LHS.  Otherwise, when the range
   [MIN, MAX] is such that MIN == MAX, return the tree representation
   of (MIN). The latter allows callers to fold suitable strnlen() calls
   to constants.  */

tree
set_strlen_range (tree lhs, wide_int min, wide_int max,
		  tree bound /* = NULL_TREE */)
{
  if (TREE_CODE (lhs) != SSA_NAME
      || !INTEGRAL_TYPE_P (TREE_TYPE (lhs)))
    return NULL_TREE;

  if (bound)
    {
      /* For strnlen, adjust MIN and MAX as necessary.  If the bound
	 is less than the size of the array set MAX to it.  It it's
	 greater than MAX and MAX is non-zero bump MAX down to account
	 for the necessary terminating nul.  Otherwise leave it alone.  */
      if (TREE_CODE (bound) == INTEGER_CST)
	{
	  wide_int wibnd = wi::to_wide (bound);
	  int cmp = wi::cmpu (wibnd, max);
	  if (cmp < 0)
	    max = wibnd;
	  else if (cmp && wi::ne_p (max, min))
	    --max;
	}
      else if (TREE_CODE (bound) == SSA_NAME)
	{
	  value_range r;
	  get_range_query (cfun)->range_of_expr (r, bound);
	  if (!r.undefined_p ())
	    {
	      /* For a bound in a known range, adjust the range determined
		 above as necessary.  For a bound in some anti-range or
		 in an unknown range, use the range determined by callers.  */
	      if (wi::ltu_p (r.lower_bound (), min))
		min = r.lower_bound ();
	      if (wi::ltu_p (r.upper_bound (), max))
		max = r.upper_bound ();
	    }
	}
    }

  if (min == max)
    return wide_int_to_tree (size_type_node, min);

  value_range vr (TREE_TYPE (lhs), min, max);
  set_range_info (lhs, vr);
  return lhs;
}

/* For an LHS that is an SSA_NAME and for strlen() or strnlen() argument
   SRC, set LHS range info to [0, min (N, BOUND)] if SRC refers to
   a character array A[N] with unknown length bounded by N, and for
   strnlen(), by min (N, BOUND).  */

static tree
maybe_set_strlen_range (tree lhs, tree src, tree bound)
{
  if (TREE_CODE (lhs) != SSA_NAME
      || !INTEGRAL_TYPE_P (TREE_TYPE (lhs)))
    return NULL_TREE;

  if (TREE_CODE (src) == SSA_NAME)
    {
      gimple *def = SSA_NAME_DEF_STMT (src);
      if (is_gimple_assign (def)
	  && gimple_assign_rhs_code (def) == ADDR_EXPR)
	src = gimple_assign_rhs1 (def);
    }

  /* The longest string is PTRDIFF_MAX - 1 bytes including the final
     NUL so that the difference between a pointer to just past it and
     one to its beginning is positive.  */
  wide_int max = wi::to_wide (TYPE_MAX_VALUE (ptrdiff_type_node)) - 2;

  if (TREE_CODE (src) == ADDR_EXPR)
    {
      /* The last array member of a struct can be bigger than its size
	 suggests if it's treated as a poor-man's flexible array member.  */
      src = TREE_OPERAND (src, 0);
      if (TREE_CODE (src) != MEM_REF
	  && !array_ref_flexible_size_p (src))
	{
	  tree type = TREE_TYPE (src);
	  tree size = TYPE_SIZE_UNIT (type);
	  if (size
	      && TREE_CODE (size) == INTEGER_CST
	      && !integer_zerop (size))
	    {
	      /* Even though such uses of strlen would be undefined,
		 avoid relying on arrays of arrays in case some genius
		 decides to call strlen on an unterminated array element
		 that's followed by a terminated one.  Likewise, avoid
		 assuming that a struct array member is necessarily
		 nul-terminated (the nul may be in the member that
		 follows).  In those cases, assume that the length
		 of the string stored in such an array is bounded
		 by the size of the enclosing object if one can be
		 determined.  */
	      tree base = get_base_address (src);
	      if (VAR_P (base))
		{
		  if (tree size = DECL_SIZE_UNIT (base))
		    if (size
			&& TREE_CODE (size) == INTEGER_CST
			&& TREE_CODE (TREE_TYPE (base)) != POINTER_TYPE)
		      max = wi::to_wide (size);
		}
	    }

	  /* For strlen() the upper bound above is equal to
	     the longest string that can be stored in the array
	     (i.e., it accounts for the terminating nul.  For
	     strnlen() bump up the maximum by one since the array
	     need not be nul-terminated.  */
	  if (!bound && max != 0)
	    --max;
	}
    }

  wide_int min = wi::zero (max.get_precision ());
  return set_strlen_range (lhs, min, max, bound);
}

/* Diagnose buffer overflow by a STMT writing LEN + PLUS_ONE bytes,
   either into a region allocated for the object SI when non-null,
   or into an object designated by the LHS of STMT otherwise.
   For a call STMT, when CALL_LHS is set use its left hand side
   as the destination, otherwise use argument zero.
   When nonnull uses RVALS to determine range information.
   RAWMEM may be set by memcpy and other raw memory functions
   to allow accesses across subobject boundaries.  */

void
strlen_pass::maybe_warn_overflow (gimple *stmt, bool call_lhs, tree len,
				  strinfo *si, bool plus_one, bool rawmem)
{
  if (!len || warning_suppressed_p (stmt, OPT_Wstringop_overflow_))
    return;

  /* The DECL of the function performing the write if it is done
     by one.  */
  tree writefn = NULL_TREE;
  /* The destination expression involved in the store or call STMT.  */
  tree dest = NULL_TREE;

  if (is_gimple_assign (stmt))
    dest = gimple_assign_lhs (stmt);
  else if (is_gimple_call (stmt))
    {
      if (call_lhs)
	dest = gimple_call_lhs (stmt);
      else
	{
	  gcc_assert (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL));
	  dest = gimple_call_arg (stmt, 0);
	}

      if (!dest)
	return;
      writefn = gimple_call_fndecl (stmt);
    }
  else
    return;

  if (warning_suppressed_p (dest, OPT_Wstringop_overflow_))
    return;

  const int ostype = rawmem ? 0 : 1;

  /* Use maximum precision to avoid overflow in the addition below.
     Make sure all operands have the same precision to keep wide_int
     from ICE'ing.  */

  access_ref aref;
  /* The size of the destination region (which is smaller than
     the destination object for stores at a non-zero offset).  */
  tree destsize = compute_objsize (dest, stmt, ostype, &aref, &ptr_qry);

  if (!destsize)
    {
      aref.sizrng[0] = 0;
      aref.sizrng[1] = wi::to_offset (max_object_size ());
    }

  /* Return early if the DESTSIZE size expression is the same as LEN
     and the offset into the destination is zero.  This might happen
     in the case of a pair of malloc and memset calls to allocate
     an object and clear it as if by calloc.  */
  if (destsize == len && !plus_one
      && aref.offrng[0] == 0 && aref.offrng[0] == aref.offrng[1])
    return;

  wide_int rng[2];
  if (!get_range (len, stmt, rng, ptr_qry.rvals))
    return;

  widest_int lenrng[2] =
    { widest_int::from (rng[0], SIGNED), widest_int::from (rng[1], SIGNED) };

  if (plus_one)
    {
      lenrng[0] += 1;
      lenrng[1] += 1;
    }

  /* The size of the remaining space in the destination computed
     as the size of the latter minus the offset into it.  */
  widest_int spcrng[2];
  {
    offset_int remrng[2];
    remrng[1] = aref.size_remaining (remrng);
    spcrng[0] = remrng[0] == -1 ? 0 : widest_int::from (remrng[0], UNSIGNED);
    spcrng[1] = widest_int::from (remrng[1], UNSIGNED);
  }

  if (wi::leu_p (lenrng[0], spcrng[0])
      && wi::leu_p (lenrng[1], spcrng[1]))
    return;

  location_t loc = gimple_or_expr_nonartificial_location (stmt, dest);
  bool warned = false;
  if (wi::leu_p (lenrng[0], spcrng[1]))
    {
      if (len != destsize
	  && (!si || rawmem || !is_strlen_related_p (si->ptr, len)))
	return;

      warned = (writefn
		? warning_at (loc, OPT_Wstringop_overflow_,
			      "%qD writing one too many bytes into a region "
			      "of a size that depends on %<strlen%>",
			      writefn)
		: warning_at (loc, OPT_Wstringop_overflow_,
			      "writing one too many bytes into a region "
			      "of a size that depends on %<strlen%>"));
    }
  else if (lenrng[0] == lenrng[1])
    {
      if (spcrng[0] == spcrng[1])
	warned = (writefn
		  ? warning_n (loc, OPT_Wstringop_overflow_,
			       lenrng[0].to_uhwi (),
			       "%qD writing %wu byte into a region "
			       "of size %wu",
			       "%qD writing %wu bytes into a region "
			       "of size %wu",
			       writefn, lenrng[0].to_uhwi (),
			       spcrng[0].to_uhwi ())
		  : warning_n (loc, OPT_Wstringop_overflow_,
			       lenrng[0].to_uhwi (),
			       "writing %wu byte into a region "
			       "of size %wu",
			       "writing %wu bytes into a region "
			       "of size %wu",
			       lenrng[0].to_uhwi (),
			       spcrng[0].to_uhwi ()));
      else
	warned = (writefn
		  ? warning_n (loc, OPT_Wstringop_overflow_,
			       lenrng[0].to_uhwi (),
			       "%qD writing %wu byte into a region "
			       "of size between %wu and %wu",
			       "%qD writing %wu bytes into a region "
			       "of size between %wu and %wu",
			       writefn, lenrng[0].to_uhwi (),
			       spcrng[0].to_uhwi (), spcrng[1].to_uhwi ())
		  : warning_n (loc, OPT_Wstringop_overflow_,
			       lenrng[0].to_uhwi (),
			       "writing %wu byte into a region "
			       "of size between %wu and %wu",
			       "writing %wu bytes into a region "
			       "of size between %wu and %wu",
			       lenrng[0].to_uhwi (),
			       spcrng[0].to_uhwi (), spcrng[1].to_uhwi ()));
    }
  else if (spcrng[0] == spcrng[1])
    warned = (writefn
	      ? warning_at (loc, OPT_Wstringop_overflow_,
			    "%qD writing between %wu and %wu bytes "
			    "into a region of size %wu",
			    writefn, lenrng[0].to_uhwi (),
			    lenrng[1].to_uhwi (),
			    spcrng[0].to_uhwi ())
	      : warning_at (loc, OPT_Wstringop_overflow_,
			    "writing between %wu and %wu bytes "
			    "into a region of size %wu",
			    lenrng[0].to_uhwi (),
			    lenrng[1].to_uhwi (),
			    spcrng[0].to_uhwi ()));
  else
    warned = (writefn
	      ? warning_at (loc, OPT_Wstringop_overflow_,
			    "%qD writing between %wu and %wu bytes "
			    "into a region of size between %wu and %wu",
			    writefn, lenrng[0].to_uhwi (),
			    lenrng[1].to_uhwi (),
			    spcrng[0].to_uhwi (), spcrng[1].to_uhwi ())
	      : warning_at (loc, OPT_Wstringop_overflow_,
			    "writing between %wu and %wu bytes "
			    "into a region of size between %wu and %wu",
			    lenrng[0].to_uhwi (),
			    lenrng[1].to_uhwi (),
			    spcrng[0].to_uhwi (), spcrng[1].to_uhwi ()));

  if (!warned)
    return;

  suppress_warning (stmt, OPT_Wstringop_overflow_);

  aref.inform_access (access_write_only);
}

/* Convenience wrapper for the above.  */

void
strlen_pass::maybe_warn_overflow (gimple *stmt, bool call_lhs,
				  unsigned HOST_WIDE_INT len,
				  strinfo *si, bool plus_one, bool rawmem)
{
  tree tlen = build_int_cst (size_type_node, len);
  maybe_warn_overflow (stmt, call_lhs, tlen, si, plus_one, rawmem);
}

/* Handle a strlen call.  If strlen of the argument is known, replace
   the strlen call with the known value, otherwise remember that strlen
   of the argument is stored in the lhs SSA_NAME.  */

void
strlen_pass::handle_builtin_strlen ()
{
  gimple *stmt = gsi_stmt (m_gsi);
  tree lhs = gimple_call_lhs (stmt);

  if (lhs == NULL_TREE)
    return;

  location_t loc = gimple_location (stmt);
  tree callee = gimple_call_fndecl (stmt);
  tree src = gimple_call_arg (stmt, 0);
  tree bound = (DECL_FUNCTION_CODE (callee) == BUILT_IN_STRNLEN
		? gimple_call_arg (stmt, 1) : NULL_TREE);
  int idx = get_stridx (src, stmt);
  if (idx || (bound && integer_zerop (bound)))
    {
      strinfo *si = NULL;
      tree rhs;

      if (idx < 0)
	rhs = build_int_cst (TREE_TYPE (lhs), ~idx);
      else if (idx == 0)
	rhs = bound;
      else
	{
	  rhs = NULL_TREE;
	  si = get_strinfo (idx);
	  if (si != NULL)
	    {
	      rhs = get_string_length (si);
	      /* For strnlen, if bound is constant, even if si is not known
		 to be zero terminated, if we know at least bound bytes are
		 not zero, the return value will be bound.  */
	      if (rhs == NULL_TREE
		  && bound != NULL_TREE
		  && TREE_CODE (bound) == INTEGER_CST
		  && si->nonzero_chars != NULL_TREE
		  && TREE_CODE (si->nonzero_chars) == INTEGER_CST
		  && tree_int_cst_le (bound, si->nonzero_chars))
		rhs = bound;
	    }
	}
      if (rhs != NULL_TREE)
	{
	  if (dump_file && (dump_flags & TDF_DETAILS) != 0)
	    {
	      fprintf (dump_file, "Optimizing: ");
	      print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
	    }
	  rhs = unshare_expr (rhs);
	  if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
	    rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);

	  if (bound)
	    rhs = fold_build2_loc (loc, MIN_EXPR, TREE_TYPE (rhs), rhs, bound);

	  gimplify_and_update_call_from_tree (&m_gsi, rhs);
	  stmt = gsi_stmt (m_gsi);
	  update_stmt (stmt);
	  if (dump_file && (dump_flags & TDF_DETAILS) != 0)
	    {
	      fprintf (dump_file, "into: ");
	      print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
	    }

	  if (si != NULL
	      /* Don't update anything for strnlen.  */
	      && bound == NULL_TREE
	      && TREE_CODE (si->nonzero_chars) != SSA_NAME
	      && TREE_CODE (si->nonzero_chars) != INTEGER_CST
	      && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
	    {
	      si = unshare_strinfo (si);
	      si->nonzero_chars = lhs;
	      gcc_assert (si->full_string_p);
	    }

	  if (strlen_to_stridx
	      && (bound == NULL_TREE
		  /* For strnlen record this only if the call is proven
		     to return the same value as strlen would.  */
		  || (TREE_CODE (bound) == INTEGER_CST
		      && TREE_CODE (rhs) == INTEGER_CST
		      && tree_int_cst_lt (rhs, bound))))
	    strlen_to_stridx->put (lhs, stridx_strlenloc (idx, loc));

	  return;
	}
    }
  if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
    return;

  if (idx == 0)
    idx = new_stridx (src);
  else
    {
      strinfo *si = get_strinfo (idx);
      if (si != NULL)
	{
	  if (!si->full_string_p && !si->stmt)
	    {
	      /* Until now we only had a lower bound on the string length.
		 Install LHS as the actual length.  */
	      si = unshare_strinfo (si);
	      tree old = si->nonzero_chars;
	      si->nonzero_chars = lhs;
	      si->full_string_p = true;
	      if (old && TREE_CODE (old) == INTEGER_CST)
		{
		  old = fold_convert_loc (loc, TREE_TYPE (lhs), old);
		  tree adj = fold_build2_loc (loc, MINUS_EXPR,
					      TREE_TYPE (lhs), lhs, old);
		  adjust_related_strinfos (loc, si, adj);
		  /* Use the constant minimum length as the lower bound
		     of the non-constant length.  */
		  wide_int min = wi::to_wide (old);
		  wide_int max
		    = wi::to_wide (TYPE_MAX_VALUE (ptrdiff_type_node)) - 2;
		  set_strlen_range (lhs, min, max);
		}
	      else
		{
		  si->first = 0;
		  si->prev = 0;
		  si->next = 0;
		}
	    }
	  return;
	}
    }
  if (idx)
    {
      if (!bound)
	{
	  /* Only store the new length information for calls to strlen(),
	     not for those to strnlen().  */
	  strinfo *si = new_strinfo (src, idx, lhs, true);
	  set_strinfo (idx, si);
	  find_equal_ptrs (src, idx);
	}

      /* For SRC that is an array of N elements, set LHS's range
	 to [0, min (N, BOUND)].  A constant return value means
	 the range would have consisted of a single value.  In
	 that case, fold the result into the returned constant.  */
      if (tree ret = maybe_set_strlen_range (lhs, src, bound))
	if (TREE_CODE (ret) == INTEGER_CST)
	  {
	    if (dump_file && (dump_flags & TDF_DETAILS) != 0)
	      {
		fprintf (dump_file, "Optimizing: ");
		print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
	      }
	    if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (ret)))
	      ret = fold_convert_loc (loc, TREE_TYPE (lhs), ret);
	    gimplify_and_update_call_from_tree (&m_gsi, ret);
	    stmt = gsi_stmt (m_gsi);
	    update_stmt (stmt);
	    if (dump_file && (dump_flags & TDF_DETAILS) != 0)
	      {
		fprintf (dump_file, "into: ");
		print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
	      }
	  }

      if (strlen_to_stridx && !bound)
	strlen_to_stridx->put (lhs, stridx_strlenloc (idx, loc));
    }
}

/* Handle a strchr call.  If strlen of the first argument is known, replace
   the strchr (x, 0) call with the endptr or x + strlen, otherwise remember
   that lhs of the call is endptr and strlen of the argument is endptr - x.  */

void
strlen_pass::handle_builtin_strchr ()
{
  gimple *stmt = gsi_stmt (m_gsi);
  tree lhs = gimple_call_lhs (stmt);

  if (lhs == NULL_TREE)
    return;

  if (!integer_zerop (gimple_call_arg (stmt, 1)))
    return;

  tree src = gimple_call_arg (stmt, 0);

  /* Avoid folding if the first argument is not a nul-terminated array.
     Defer warning until later.  */
  if (!check_nul_terminated_array (NULL_TREE, src))
    return;

  int idx = get_stridx (src, stmt);
  if (idx)
    {
      strinfo *si = NULL;
      tree rhs;

      if (idx < 0)
	rhs = build_int_cst (size_type_node, ~idx);
      else
	{
	  rhs = NULL_TREE;
	  si = get_strinfo (idx);
	  if (si != NULL)
	    rhs = get_string_length (si);
	}
      if (rhs != NULL_TREE)
	{
	  location_t loc = gimple_location (stmt);

	  if (dump_file && (dump_flags & TDF_DETAILS) != 0)
	    {
	      fprintf (dump_file, "Optimizing: ");
	      print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
	    }
	  if (si != NULL && si->endptr != NULL_TREE)
	    {
	      rhs = unshare_expr (si->endptr);
	      if (!useless_type_conversion_p (TREE_TYPE (lhs),
					      TREE_TYPE (rhs)))
		rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
	    }
	  else
	    {
	      rhs = fold_convert_loc (loc, sizetype, unshare_expr (rhs));
	      rhs = fold_build2_loc (loc, POINTER_PLUS_EXPR,
				     TREE_TYPE (src), src, rhs);
	      if (!useless_type_conversion_p (TREE_TYPE (lhs),
					      TREE_TYPE (rhs)))
		rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
	    }
	  gimplify_and_update_call_from_tree (&m_gsi, rhs);
	  stmt = gsi_stmt (m_gsi);
	  update_stmt (stmt);
	  if (dump_file && (dump_flags & TDF_DETAILS) != 0)
	    {
	      fprintf (dump_file, "into: ");
	      print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
	    }
	  if (si != NULL
	      && si->endptr == NULL_TREE
	      && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
	    {
	      si = unshare_strinfo (si);
	      si->endptr = lhs;
	    }
	  zero_length_string (lhs, si);
	  return;
	}
    }
  if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
    return;
  if (TREE_CODE (src) != SSA_NAME || !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (src))
    {
      if (idx == 0)
	idx = new_stridx (src);
      else if (get_strinfo (idx) != NULL)
	{
	  zero_length_string (lhs, NULL);
	  return;
	}
      if (idx)
	{
	  location_t loc = gimple_location (stmt);
	  tree lhsu = fold_convert_loc (loc, size_type_node, lhs);
	  tree srcu = fold_convert_loc (loc, size_type_node, src);
	  tree length = fold_build2_loc (loc, MINUS_EXPR,
					 size_type_node, lhsu, srcu);
	  strinfo *si = new_strinfo (src, idx, length, true);
	  si->endptr = lhs;
	  set_strinfo (idx, si);
	  find_equal_ptrs (src, idx);
	  zero_length_string (lhs, si);
	}
    }
  else
    zero_length_string (lhs, NULL);
}

/* Handle a strcpy-like ({st{r,p}cpy,__st{r,p}cpy_chk}) call.
   If strlen of the second argument is known, strlen of the first argument
   is the same after this call.  Furthermore, attempt to convert it to
   memcpy.  Uses RVALS to determine range information.  */

void
strlen_pass::handle_builtin_strcpy (built_in_function bcode)
{
  int idx, didx;
  tree src, dst, srclen, len, lhs, type, fn, oldlen;
  bool success;
  gimple *stmt = gsi_stmt (m_gsi);
  strinfo *si, *dsi, *olddsi, *zsi;
  location_t loc;

  src = gimple_call_arg (stmt, 1);
  dst = gimple_call_arg (stmt, 0);
  lhs = gimple_call_lhs (stmt);
  idx = get_stridx (src, stmt);
  si = NULL;
  if (idx > 0)