-
Notifications
You must be signed in to change notification settings - Fork 9
/
alias.bib
1224 lines (1021 loc) · 45.3 KB
/
alias.bib
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
%%% Alias and pointer analysis bibliography
% Also some other interprocedural analysis.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% From Michael Wolfe
%%%
@INCOLLECTION{jones.muchnick.81,
author = "Neil D. Jones and Steven S. Muchnick",
title = "Flow Analysis and Optimization of {L}isp-like Structures",
pages = "102--131",
editor = "Steven S. Muchnick and Neil D. Jones",
booktitle = "Program Flow Analysis: Theory and Applications",
publisher = "Prentice Hall",
year = 1981,
}
@INPROCEEDINGS{landi.popl.91,
author = "William Landi and Barbara G. Ryder",
title = "Pointer-Induced Aliasing: A Problem Classification",
crossref = "POPL91",
pages = "93--103",
}
@INPROCEEDINGS{chase.pldi.90,
author = "David R. Chase and Mark Wegman and F. Kenneth Zadeck",
title = "Analysis of Pointers and Structures",
crossref = "PLDI90",
pages = "296--310",
}
@INPROCEEDINGS{larus.pldi.88,
author = "James R. Larus and Paul N. Hilfinger",
title = "Detecting Conflicts Between Structure Accesses",
crossref = "PLDI88",
pages = "21--34",
}
@INPROCEEDINGS{emami.pldi.94,
author = "Maryam Emami and Rakesh Ghiya and Laurie J. Hendren",
title = "Context-Sensitive Interprocedural Points-to Analysis in the Presence of Function Pointers",
crossref = "PLDI94",
pages = "242--256",
}
@INPROCEEDINGS{hendren.ics.89,
author = "Laurie J. Hendren and Alexandru Nicolau",
title = "Interference Analysis Tools for Parallelizing Programs with Recursive Data Structures",
crossref = "ICS89",
pages = "205--214",
}
@ARTICLE{hendren.tpds.90,
author = "Laurie J. Hendren and Alexandru Nicolau",
title = "Parallelizing Programs with Recursive Data Structures",
pages = "35--47",
journal = tpds,
year = 1990,
volume = 1,
number = 1,
month = jan,
}
@inproceedings{horwitz.pldi.89,
author = "Susan Horwitz and Phil Pfeiffer and Thomas Reps",
title = "Dependence Analysis for Pointer Variables",
crossref = "PLDI89",
pages = "28--40",
}
@INPROCEEDINGS{loeliger.super.91,
author = "Jon Loeliger and Robert Metzger and Mark Seligman and Sean Stroud",
title = "Pointer Target Tracking: An Empirical Study",
crossref = "SC1991",
pages = "14--23",
}
@INPROCEEDINGS{smith.super.91,
author = "Lauren L. Smith",
title = "Vectorizing {C} Compilers: How Good Are They?",
crossref = "SC1991",
pages = "544--553",
}
@INPROCEEDINGS{guarna.icpp.88,
author = "Guarna, Jr., Vincent A.",
title = "A Technique for Analyzing Pointer and Structure References in Parallel Restructuring Compilers",
crossref = "ICPP88",
pages = "212--220",
volume = "II",
}
@INPROCEEDINGS{landi.pldi.92,
author = "William Landi and Barbara G. Ryder",
title = "A Safe Approximate Algorithm for Interprocedural Pointer Aliasing",
crossref = "PLDI92",
pages = "235--248",
}
@InProceedings{landi.pldi.93,
author = "William Landi and Barbara G. Ryder and Sean Zhang",
title = "Interprocedural modification side effect analysis with pointer aliasing",
crossref = "PLDI93",
pages = "56--67",
abstract =
"We present a new interprocedural modification side effects
algorithm for C programs, that can discern side effects through
general-purpose pointer usage. Ours is the first complete design and
implementation of such an algorithm. Preliminary performance findings
support the practicality of the technique, which is based on our
previous approximation algorithm for pointer aliases [LR92]. Each
indirect store through a pointer variable is found, on average, to
correspond to a store into 1.2 locations. This indicates that our
program-point-specific pointer aliasing information is quite precise
when used to determine the effects of these stores.",
}
@Article{RyderLSZA2001,
author = "Barbara G. Ryder and William A. Landi and Philip A. Stocks and Sean Zhang and Rita Altucher",
title = "A schema for interprocedural modification side-effect analysis with pointer aliasing",
journal = TOPLAS,
year = 2001,
volume = 23,
number = 2,
pages = "105--186",
month = mar,
abstract =
"The first interprocedural modification side-effects analysis for C (MODC)
that obtains better than worst-case precision on programs with
general-purpose pointer usage is presented with empirical results. The
analysis consists of an algorithm schema corresponding to a family of MODC
algorithms with two independent phases: one for determining
pointer-induced aliases and a subsequent one for propagating
interprocedural side effects. These MODC algorithms are parameterized by
the aliasing method used. The empirical results compare the performance of
two dissimilar MODC algorithms: MODC(FSAlias) uses a flow-sensitive,
calling-context-sensitive interprocedural alias analysis; MODC(FIAlias
uses a flow-insensitive, calling-context-insensitive alias analysis which
is much faster, but less accurate. These two algorithms were profiled on
45 programs ranging in size from 250 to 30,000 lines of C code, and the
results demonstrate dramatically the possible cost-precision
trade-offs. This first comparative implementation of MODC analyses offers
insight into the differences between flow-/context-sensitive and
flow-/context-insensitive analyses. The analysis cost versus precision
trade-offs in side-effect information obtained are reported. The results
show surprisingly that the precision of flow-sensitive side-effect
analysis is not always prohibitive in cost, and that the precision of
flow-insensitive analysis is substantially better than worst-case
estimates and seems sufficient for certain applications. On average
MODC(FSAlias) for procedures and calls is in the range of 20\% more precise
than MODC(FIAlias); however, the performance was found to be at least an
order of magnitude slower than MODC(FIAlias).",
}
@INPROCEEDINGS{choi.popl.93,
author = "Jong-Deok Choi and Michael Burke and Paul Carini",
title = "Efficient Flow-Sensitive Interprocedural Computation of Pointer-Induced Aliases and Side Effects",
crossref = "POPL93",
pages = "232--245",
}
@ARTICLE{marlowe.sigplan.93,
author = "Thomas J. Marlowe and William G. Landi and Barbara G. Ryder and Jong-Deok Choi and Michael G. Burke and Paul Carini",
title = "Pointer-Induced Aliasing: A Clarification",
journal = "SIGPLAN Notices",
year = 1993,
volume = 28,
number = 9,
pages = "67--70",
month = sep,
}
@INPROCEEDINGS{hendren.pldi.92,
author = "Laurie J. Hendren and Joseph Hummel and Alexandru Nicolau",
title = "Abstractions for Recursive Pointer Data Structures: Improving the Analysis and Transformation of Imperative Programs",
crossref = "PLDI92",
pages = "249--260",
}
@ARTICLE{hummel.loplas.92,
author = "Joseph Hummel and Laurie J. Hendren and Alexandru Nicolau",
title = "Abstract Description of Pointer Data Structures: An Approach for Improving the Analysis and Optimization of Imperative Programs",
pages = "243--260",
journal = loplas,
year = 1992,
volume = 1,
number = 3,
month = sep,
}
@INPROCEEDINGS{hummel.ipps.94,
author = "Joseph Hummel and Laurie J. Hendren and Alexandru Nicolau",
title = "A Language for Conveying the Aliasing Properties of Dynamic, Pointer-Based Data Structures",
crossref = "IPPS94",
pages = "208--216",
}
@INPROCEEDINGS{hummel.pldi.94,
author = "Joseph Hummel and Laurie J. Hendren and Alexandru Nicolau",
title = "A General Data Dependence Test for Dynamic, Pointer-Based Data Structures",
crossref = "PLDI94",
pages = "218--229",
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Alias analysis
%%%
@InProceedings{CWZ:APS,
author = "David R. Chase and Mark Wegman and F. Kenneth Zadeck",
title = "Analysis of Pointers and Structures",
crossref = "PLDI90",
pages = "296--310",
}
@InProceedings{LandiWilli1992a,
author = "William Landi and Barbara G. Ryder",
title = "A safe approximate algorithm for interprocedural
pointer aliasing",
crossref = "PLDI92",
pages = "235--248",
abstracturl = "file://cs.rutgers.edu/pub/technical-reports/lcsr-tr-168.abstract",
url = "file://cs.rutgers.edu/pub/technical-reports/lcsr-tr-168.ps.Z",
}
@TechReport{LandiR91:TR,
author = "William Landi and Barbara G. Ryder",
title = "A Safe Approximation Algorithm for Interprocedural
Pointer Aliasing",
institution = "Rutgers University",
year = 1991,
number = "LCSR-TR-168",
month = sep
}
@InProceedings{PLDI94*242,
author = "Maryam Emami and Rakesh Ghiya and Laurie J. Hendren",
title = "Context-Sensitive Interprocedural Points-to Analysis
in the Presence of Function Pointers",
crossref = "PLDI94",
pages = "242--256",
}
@InProceedings{Wilson:1995:ECP,
author = "Robert P. Wilson and Monica S. Lam",
title = "Efficient context-sensitive pointer analysis for {C}
programs",
crossref = "PLDI95",
pages = "1--12",
coden = "SINODQ",
ISSN = "0362-1340",
abstract = "This paper proposes an efficient technique for
context-sensitive pointer analysis that is applicable
to real C programs. For efficiency, we summarize the
effects of procedures using partial transfer functions.
A partial transfer function (PTF) describes the
behavior of a procedure assuming that certain alias
relationships hold when it is called. We can reuse a
PTF in many calling contexts as long as the aliases
among the inputs to the procedure are the same. Our
empirical results demonstrate that this technique is
successful-a single PTF per procedure is usually
sufficient to obtain completely context-sensitive
results. Because many C programs use features such as
type casts and pointer arithmetic to circumvent the
high-level type system, our algorithm is based on a
low-level representation of memory locations that
safely handles all the features of C. We have
implemented our algorithm in the SUIF compiler system
and we show that it runs efficiently for a set of C
benchmarks. (16 Refs.)",
affiliation = "Comput. Syst. Lab., Stanford Univ., CA, USA",
classification = "C6140D (High level languages); C6150C (Compilers,
interpreters and other processors)",
keywords = "Alias relationships; C benchmarks; C programs;
Compiler system; Context-sensitive pointer analysis;
High-level type system; Memory locations; Partial
transfer functions; Pointer arithmetic; Procedure call;
SUIF; Type casts",
thesaurus = "C language; Program compilers; Remote procedure
calls",
}
@InProceedings{POPL93*232,
author = "Jong-Deok Choi and Michael Burke and Paul Carini",
title = "Efficient Flow-Sensitive Interprocedural Computation
of Pointer-Induced Aliases and Side Effects",
pages = "232--245",
crossref = "POPL93",
}
@InProceedings{Deutsch94a,
author = "Alain Deutsch",
title = "Interprocedural May-Alias Analysis for Pointers:
Beyond {$k$}-Limiting",
crossref = "PLDI94",
pages = "230--241",
note = "SIGPLAN Notices, 29(6)",
abstract = "Existing methods for alias analysis of recursive
pointer data structures are based on two approximation
techniques: {\em $k$-limiting}, which blurs distinction
between sub-objects below depth $k$; and {\em
store-based\/} (or equivalently location or
region-based) approximations, which blur distinction
between elements of recursive data structures. Although
notable progress in interprocedural alias analysis has
been recently accomplished, very little progress in the
precision of analysis of recursive pointer data
structures has been seen since the inception of these
approximation techniques by Jones and Muchnick a decade
ago. As a result, optimizing, verifying and
parallelizing programs with pointers has remained
difficult. We present a new parametric framework for
analyzing recursive pointer data structures which can
express a new natural class of alias information not
accessible to existing methods. The key idea is to
represent alias information by pairs of {\em symbolic
access paths\/} which are qualified by symbolic
descriptions of the positions for which the alias pair
holds. Based on this result, we present an algorithm
for interprocedural may-alias analysis with pointers
which on numerous examples that occur in practice is
much more precise than recently published algorithms.",
}
@InProceedings{Deutsch95,
author = "Alain Deutsch",
title = "Semantic Models and Abstract Interpretation Techniques
for Inductive Data Structures and Pointers",
crossref = "PEPM95",
pages = "226--229",
}
@InProceedings{POPL::Steensgaard1996,
title = "Points-to Analysis in Almost Linear Time",
author = "Bjarne Steensgaard",
crossref = "POPL96",
pages = "32--41",
}
@InProceedings{Steensgaard96,
author = "Bjarne Steensgaard",
title = "Points-to analysis by type inference of programs with
structures and unions",
crossref = "CC96",
pages = "136-150"
}
@InProceedings{Jones:Muchnick:acm:popl:1982,
author = "Neil D. Jones and Stephen S. Muchnick",
title = "A Flexible Approach to Interprocedural Data Flow
Analysis and Programs with Recursive Data Structures",
crossref = "POPL82",
pages = "66--74",
abstract = "A new approach to data flow analysis of procedural
programs and programs with recursive data structures is
described. The method depends on simulation of the
interpreter for the subject programming language using
a retrieval function to approximate a program's data
structures.",
}
@InProceedings{POPL79*244,
author = "Neil D. Jones and Steven S. Muchnick",
title = "Flow analysis and optimization of {LISP}-like
structures",
crossref = "POPL79",
pages = "244--256",
}
@InProceedings{Ruf:1995:CAA,
author = "Erik Ruf",
title = "Context-insensitive alias analysis reconsidered",
crossref = "PLDI95",
pages = "13--22",
coden = "SINODQ",
ISSN = "0362-1340",
abstract = "Recent work on alias analysis in the presence of
pointers has concentrated on context-sensitive
interprocedural analyses, which treat multiple calls to
a single procedure independently rather than
constructing a single approximation to a procedure's
effect on all of its callers. While context-sensitive
modeling offers the potential for greater precision by
considering only realizable call-return paths, its
empirical benefits have yet to be measured. This paper
compares the precision of a simple, efficient,
context-insensitive points-to analysis for the C
programming language with that of a maximally
context-sensitive version of the same analysis. We
demonstrate that, for a number of pointer-intensive
benchmark programs, context-insensitivity exerts little
to no precision penalty. We also describe techniques
for using the output of context-insensitive analysis to
improve the efficiency of context-sensitive analysis
without affecting precision. (23 Refs.)",
affiliation = "Microsoft Corp., Redmond, WA, USA",
classification = "C6110 (Systems analysis and programming); C6150C
(Compilers, interpreters and other processors); C6150N
(Distributed systems software)",
keywords = "C programming language; Call-return paths; Compilers;
Context-insensitive alias analysis; Context-insensitive
analysis; Context-insensitivity; Context-sensitive
analysis; Context-sensitive interprocedural analyses;
Context-sensitive modeling; Multiple procedure calls;
Pointer-intensive benchmark programs; Pointers;
Precision penalty",
thesaurus = "C language; Data flow analysis; Program compilers;
Remote procedure calls; Software performance
evaluation",
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Shape analysis
%%%
@InProceedings{HendrenHumNic92,
author = "Laurie J. Hendren and Joseph Hummel and Alexandru
Nicolau",
title = "Abstractions for Recursive Pointer Data Structures:
Improving the Analysis and Transformation of Imperative
Programs",
crossref = "PLDI92",
pages = "249--260",
url = "ftp://ftp-acaps.cs.mcgill.ca/pub/doc/papers/PLDI92.ps.gz",
}
@Article{Ghiya:1996:CAP,
author = "Rakesh Ghiya and Laurie J. Hendren",
title = "Connection Analysis: A Practical Interprocedural
Heap Analysis for {C}",
journal = "International Journal of Parallel Programming",
volume = "24",
number = "6",
pages = "547--578",
month = dec,
year = "1996",
coden = "IJPPE5",
ISSN = "0885-7458",
affiliation = "McGill Univ",
affiliationaddress = "Que, Can",
classification = "722.4; 723.1; 723.1.1; 723.5; 922.2; C4240P
(Parallel programming and algorithm theory); C6110P
(Parallel programming); C6120 (File organisation);
C6140D (High level languages); C6150C (Compilers,
interpreters and other processors)",
corpsource = "Sch. of Comput. Sci., McGill Univ., Montreal, Que.,
Canada",
journalabr = "Int J Parallel Program",
keywords = "array dependence; C (programming language); C
language; C programs; Computer aided analysis;
Connection analysis; connection analysis; connection
matrices; connection relationships; conservative
estimate; context sensitive interprocedural analysis;
Context sensitive languages; disjoint objects;
dynamically allocated arrays; heap access
disambiguation; heap allocated objects; Heap analysis
technique; heap directed pointers; interference
analysis; McCAT optimizing/parallelizing C compiler;
optimising compilers; Parallel processing systems;
parallel programming; parallelising compilers;
parallelizing compilers; Pointer disambiguation;
points-to analysis; Program compilers; program control
structures; program point; scientific programs;
Statistical methods; storage management",
treatment = "P Practical",
}
@InProceedings{POPL::GhiyaH1996,
title = "Is it a Tree, a {DAG}, or a Cyclic Graph? {A} Shape
Analysis for Heap-Directed Pointers in~{C}",
author = "Rakesh Ghiya and Laurie J. Hendren",
crossref = "POPL96",
pages = "1--15",
}
@InProceedings{POPL::FradetM1997,
title = "Shape Types",
author = "Pascal Fradet and Daniel Le M{\'e}tayer",
crossref = "POPL97",
pages = "27--39",
}
@InProceedings{GolanGuetaBARSY2011,
author = "Guy Golan-Gueta and Nathan Bronson and Alex Aiken and G. Ramalingam and Mooly Sagiv and Eran Yahav",
title = "Automatic fine-grain locking using shape properties",
crossref = "OOPSLA2011",
pages = "225--242",
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Everything else
%%%
@InProceedings{LandiR91,
author = "William Landi and Barbara G. Ryder",
title = "Pointer-induced Aliasing: A Problem Classification",
crossref = "POPL91",
pages = "93--103",
sequence = 27
}
@InProceedings{LandiR92,
author = "William Landi and Barbara G. Ryder",
title = "A safe approximate algorithm for interprocedural pointer
aliasing",
crossref = "PLDI92",
pages = "235--248",
}
@InProceedings{ChaseWZ90,
author = "David R. Chase and Mark Wegman and F. Kenneth Zadeck",
title = "Analysis of Pointers and Structures",
crossref = "PLDI90",
pages = "296--310",
}
@Article{HendrenN90,
author = "Laurie J. Hendren and Alexandru Nicolau",
title = "Parallelizing Programs with Recursive Data Structures",
journal = "IEEE Transactions on Parallel and Distributed Systems",
year = 1990,
volume = 1,
number = 1,
pages = "35--47",
month = jan
}
@InCollection{JonesM81,
author = "Neil D. Jones and Steven S. Muchnick",
title = "Flow analysis and optimization of {Lisp}-like structures",
booktitle = "Program Flow Analysis: Theory and Applications",
publisher = "Prentice-Hall",
address = "Englewood Cliffs, N.J.",
year = 1981,
OMITeditor = "Steven S. Muchnick and Neil D. Jones",
pages = "102--131",
chapter = 4
}
@book{AdvancedCompiler,
author = {Steven S. Muchnick},
title = {Advanced Compiler Design and Implementation},
year = {1997},
isbn = {1-55860-320-4},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
}
@book{DataFlow,
author = {Steven S. Muchnick and N. D. Jones},
title = {Program Flow Analysis: Theory and Applications},
publisher = {Prentice-Hall},
year = {1981},
address = {Englewood Cliffs, New Jersey, USA},
}
@InProceedings{JonesM82,
author = "Neil D. Jones and Steve S. Muchnick",
title = "A Flexible Approach to Interprocedural Data Flow Analysis
and Programs With Recursive Data Structures",
crossref = "POPL82",
pages = "66--74",
}
@InProceedings{LarusH88:PLDI,
author = "James R. Larus and Paul N. Hilfinger",
title = "Detecting conflicts between structure accesses",
crossref = "PLDI88",
pages = "21--34",
}
@InProceedings{LarusH88:PPEALS,
author = "James R. Larus and Paul N. Hilfinger",
title = "Restructuring {Lisp} Programs for Concurrent Execution",
booktitle = "Proceedings of the ACM/SIGPLAN PPEALS 1988",
pages = "100--110",
year = 1988,
month = Jul # "~19--21,",
note = "SIGPLAN Notices 23, Volume II"
}
@Unpublished{BradleeH88,
author = "David Bradlee and Dov Harel",
title = "Flow insensitive aliasing and the memory reference graph",
note = "Rough Draft",
year = 1988,
month = nov # "~2,"
}
@TechReport{Ghiya92,
author = "Rakesh Ghiya",
title = "Interprocedural analysis in the presence of function pointers",
institution = "McGill University School of Computer Science, Advanced
Compilers, Architectures, and Parallel Systems Group",
year = 1992,
type = "ACAPS Technical Memo",
number = 62,
address = Montreal,
month = Dec # "~28,"
}
@TechReport{HendrenEGV93,
author = "Laurie J. Hendren and Maryam Emami and Rakesh Ghiya and
Clark Verbrugge",
title = "A practical context-sensitive interprocedural alias
analysis framework for {C} compilers",
institution = "McGill University School of Computer Science, Advanced
Compilers, Architectures, and Parallel Systems Group",
year = 1993,
type = "ACAPS Technical Memo",
number = 72,
address = Montreal,
month = Jul # "~24,"
}
@InProceedings{Weihl80,
author = "William E. Weihl",
title = "Interprocedural Data Flow Analysis in the Presence of
Pointers, Procedure Variables, and Label Variables",
crossref = "POPL80",
pages = "83--94",
}
@InProceedings{Hogg-oopsla91,
author = "John Hogg",
title = "Islands: Aliasing Protection in Object-Oriented Languages",
crossref = "OOPSLA91",
pages = "271--285",
keywords = "olit oopsla91",
}
@InProceedings{Almeida97,
author = "Paulo Sergio Almeida",
title = "Balloon types: Controlling sharing of state in data types",
crossref = "ECOOP97",
pages = "32--59",
}
@InProceedings{NobleVP98,
author = "James Noble and Jan Vitek and John Potter",
title = "Flexible Alias Protection",
crossref = "ECOOP98",
pages = "158--185",
}
@InProceedings{lu:2006:owner-accessiblity,
author = "Yi Lu and John Potter",
title = "On ownership and accessibility",
crossref = "ECOOP2006",
pages = "99--123",
}
@Article{Baker95,
author = "Henry G. Baker",
title = "`{Use}-once' variables and linear objects -- storage
management, reflection and multi-threading",
journal = "SIGPLAN Notices",
year = "1995",
volume = "30",
number = "1",
pages = "45--52",
month = jan,
note2 = "HAR",
url = "ftp://ftp.netcom.com/pub/hbaker/",
abstract = "Programming languages should have 'use-once' variables
in addition to the usual 'multiple-use' variables.
'Use-once' variables are bound to linear (unshared,
unaliased, or singly-referenced) objects. Linear
objects are cheap to access and manage, because they
require no synchronization or tracing garbage
collection. Linear objects can elegantly and
efficiently solve otherwise difficult problems of
functional/mostly-functional systems-e.g., in-place
updating and the efficient initialization of functional
objects. Use-once variables are ideal for directly
manipulating resources reflective languages. A
'use-once' variable must be dynamically referenced
exactly once within its scope. Unreferenced use-once
variables must be explicitly killed, and
multiply-referenced use-once variables must be
explicitly copied; this duplication and deletion is
subject to the constraint that some linear data types
do not support duplication and deletion methods.
Use-once variables are bound only to linear objects,
which may reference other linear or non-linear objects.
Non-linear objects can reference other non-linear
objects, but can reference a linear object only in a
way that ensures mutual exclusion. Although
implementations have long had implicit use-once
variables and linear objects, most languages do not
provide the programmer any help for their utilization.
For example, use-once variables allow for the
safe/controlled use of reified language implementation
objects like single-use continuations. Linear objects
and use-once variables map elegantly into dataflow
models of concurrent computation, and the graphical
representations of dataflow models make an appealing
visual linear programming language.",
}
@InProceedings{ChirimarJa1992a,
author = "Jawahar Chirimar and Carl A. Gunter and Jon G.
Riecke",
booktitle = "Conference on Lisp and Functional programming",
title = "Proving Memory Management Invariants for a Language
Based on Linear Logic",
year = "1992",
abstracturl = "http://www.research.att.com:80/orgs/ssr/people/riecke/abstracts/linear-logic-lfp.html",
url = "ftp://ftp.research.att.com/dist/riecke/linear-logic-lfp.ps.gz",
pages = "139--150",
}
@Unpublished{GeniusTZ97,
author = "Daniela Genius and Martin Trapp and Wolf Zimmermann",
title = "An approach to improve locality using sandwich types",
note = "Submission to OOPSLA '98 (?)",
year = 1997
}
@InProceedings{POPL::ShapiroH1997,
title = "Fast and Accurate Flow-Insensitive Points-To Analysis",
author = "Marc Shapiro and Susan Horwitz",
crossref = "POPL97",
pages = "1--14",
references = "\cite{PLDI::AustinBS1994} \cite{POPL::ChoiBC1993}
\cite{PLDI::ChaseWZ1990} \cite{POPL::Deutsch1990}
\cite{PLDI::Deutsch1994} \cite{PLDI::EmamiGH1994}
\cite{POPL::GhiyaH1996} \cite{PLDI::HorwitzPR1989}
\cite{PLDI::LandiR1992} \cite{PLDI::LandiRZ1993}
\cite{PLDI::Ruf1995} \cite{POPL::SagivRW1996}
\cite{POPL::Steensgaard1996} \cite{POPL::Weihl1980}
\cite{PLDI::WilsonL1995}",
}
@InProceedings{AldrichKC2002,
author = "Jonathan Aldrich and Valentin Kostadinov and Craig Chambers",
title = "Alias annotations for program understanding",
crossref = "OOPSLA2002",
pages = "311--330",
}
@InProceedings{AldrichC2004,
author = "Jonathan Aldrich and Craig Chambers",
title = "Ownership domains: Separating aliasing policy from mechanism",
crossref = "ECOOP2004",
pages = "1--25",
abstract =
"Ownership types promise to provide a practical mechanism for enforcing
stronger encapsulation by controlling aliasing in object-oriented
languages. However, previous ownership type proposals have tied the
aliasing policy of a system to the mechanism of ownership. As a result,
these proposals are too weak to express many important aliasing
constraints, yet also so restrictive that they prohibit many useful
programming idioms.
\par
In this paper, we propose ownership domains, which decouple encapsulation
policy from the mechanism of ownership in two key ways. First, developers
can specify multiple ownership domains for each object, permitting a
fine-grained control of aliasing compared to systems that provide only one
ownership domain for each object. Second, developers can specify the
permitted aliasing between each pair of domains in the system, providing
more flexibility compared to systems that enforce a fixed policy for
inter-domain aliasing. Because it decouples policy from mechanism, our
alias control system is both more precise and more flexible than previous
ownership type systems.",
}
@InProceedings{BoyapatiLS2003,
author = "Chandrasekhar Boyapati and Barbara Liskov and Liuba Shrira",
title = "Ownership types for object encapsulation",
crossref = "POPL2003",
pages = "213--223",
}
@PhdThesis{Boyapati2004:PhD,
author = "Chandrasekhar Boyapati",
title = "{SafeJava}: A Unified Type System for Safe Programming",
school = MITEECS,
year = 2004,
address = MITaddr,
month = feb,
}
@InProceedings{Wadler90,
author = "Philip Wadler",
title = "Linear types can change the world!",
booktitle = "{IFIP {TC} 2} Working Conference on Programming Concepts and Methods",
pages = "347--359",
year = 1990,
OMITeditor = "M. Broy and C. Jones",
address = "Sea of Galilee, Israel",
month = apr,
abstract =
"The linear logic of J.-Y. Girard suggests a new type system for functional
languages, one which supports operations that ``change the world''. Values
belonging to a linear type must be used exactly once: like the world, they
cannot be duplicated or destroyed. Such values require no reference
counting or garbage collection, and safely admit destructive array
update. Linear types extend Schmidt's notion of single threading; provide
an alternative to Hudak and Bloss' update analysis; and offer a practical
complement to Lafont and Holmström's elegant linear languages."
}
@InProceedings{FahndrichD2002,
author = "Manuel F{\"a}hndrich and Robert DeLine",
title = "Adoption and focus: Practical linear types for imperative programming",
crossref = "PLDI2002",
pages = "13--24",
}
@Article{HindP2001,
author = "Michael Hind and Anthony Pioli",
title = "Evaluating the effectiveness of pointer alias analyses",
journal = "Science of Computer Programming",
year = 2001,
volume = 39,
number = 1,
pages = "31--55",
month = jan
}
@InProceedings{RinardSB2004,
author = "Martin Rinard and Alexandru S{\u{a}}lcianu and Suhabe Bugrara",
authorASCII = "Alexandru Salcianu",
title = "A classification system and analysis for aspect-oriented programs",
crossref = "FSE2004",
pages = "147--158",
abstract =
"We present a new classification system for aspect-oriented programs. This
system characterizes the interactions between aspects and methods and
identifies classes of interactions that enable modular reasoning about the
crosscut program. We argue that this system can help developers structure
their understanding of aspect-oriented programs and promotes their ability
to reason productively about the consequences of crosscutting a program
with a given aspect.
\par
We have designed and implemented a program analysis system that
automatically classifies interactions between aspects and methods and have
applied this analysis to a set of benchmark programs. We found that our
analysis is able to 1) identify interactions with desirable properties
(such as lack of interference), 2) identify potentially problematic
interactions (such as interference caused by the aspect and the method both
writing the same field), and 3) direct the developer's attention to the
causes of such interactions.",
}
@InProceedings{SalcianuR2001,
author = "Alexandru S{\u{a}}lcianu and Martin Rinard",
authorASCII = "Alexandru Salcianu",
title = "Pointer and escape analysis for multithreaded programs",
crossref = "PPOPP2001",
pages = "12--23",
}
@InProceedings{TkachukD03,
author = "Oksana Tkachuk and Matthew B. Dwyer",
title = "Adapting side effects analysis for modular program model checking",
crossref = "FSE2003",
pages = "188--197",
}
@InProceedings{CahoonM2001,
author = "Brendon Cahoon and Kathryn S. McKinley",
title = "Data flow analysis for software prefetching linked data structures in {Java}",
crossref = "PACT2001",
pages = "280--291",
}
@InProceedings{ParkG92,
author = "Young Gil Park and Benjamin Goldberg",
title = "Escape analysis on lists",
crossref = "PLDI92",
pages = "116--127",
}
@InProceedings{ChoiGSSM99,
author = "Jong-Deok Choi and Manish Gupta and Mauricio J. Serrano and Vugranam C. Sreedhar and Samuel P. Midkiff",
title = "Escape analysis for {Java}",
crossref = "OOPSLA99",
pages = "1--19",
}
@InProceedings{Minsky96,
author = "Naftaly H. Minsky",
title = "Towards alias-free pointers",
crossref = "ECOOP96",
pages = "189--209",
}
@InProceedings{aiken:PLDI03,
author = {Alex Aiken and Jeffrey S. Foster and John Kodumal and
Tachio Terauchi},
title = "Checking and inferring local non-aliasing",
crossref = "PLDI2003",
pages = {129--140},
}
@InProceedings{AvotsDLL2005,
author = "Dzintars Avots and Michael Dalton and V. Benjamin
Livshits and Monica Lam",
title = "Improving software security with a {C} pointer analysis",
crossref = "ICSE2005",
pages = "332--341",
}
@InProceedings{KuncakLR2002,
author = "Viktor Kuncak and Patrick Lam and Martin Rinard",
title = "Role analysis",
crossref = "POPL2002",
pages = "17--32",
}
@InProceedings{Das:01:EISPAO,
author = {Manuvir Das and Ben Liblit and Manuel F\"ahndrich
and Jakob Rehof},
title = {Estimating the Impact of Scalable Pointer Analysis
on Optimization},