Beyond Iteration Vectors: Instancewise Relational Abstract Domains

1. Aho, A., Sethi, R., Ullman, J.: Compilers: Principles, Techniques and Tools. Addison-Wesley, Reading (1986)

   Google Scholar 

2. Amiranoff, P.: An Automata-Theoretic Modelization of Instancewise Program Analysis: Transducers as mappings from Instances to Memory Locations. PhD thesis, CNAM, Paris (December 2004)

   Google Scholar 

3. Berstel, J.: Transductions and Context-Free Languages. Teubner, Stuttgart, Germany (1979)

   Google Scholar 

4. Bourdoncle, F.: Abstract interpretation by dynamic partitioning. J. of Functional Programming 2(4), 407–423 (1992)

   Article  MathSciNet  Google Scholar 

5. Cohen, A.: Program Analyse et transformation: from the Polytope Model to Formal Languages. PhD hesis, Université de Versailles, France (December 1999)

   Google Scholar 

6. Cohen, A., Collard, J.-F.: Instancewise reaching definition analysis for recursive programs using context-free transductions. In: Parallel Architectures and Compilation Techniques (PACT 1998), Paris, France, pp. 332–340. IEEE Computer Society, Los Alamitos (1998)

   Google Scholar 

7. Collard, J.-F.: Reasoning About Program Transformations. Springer, Heidelberg (2002)

   Google Scholar 

8. Cousot, P.: Semantic foundations of programs analysis. Prentice-Hall, Englewood Cliffs (1981)

   Google Scholar 

9. Cousot, P., Halbwachs, N.: Automatic discovery of linear restraints among variables of a program. In: 5th ACM Symp. on Principles of Programming Languages, pp. 84–96 (January 1978)

   Google Scholar 

10. Creusillet, B.: Array Region Analyses and Applications. PhD thesis, École Nationale Supérieure des Mines de Paris (ENSMP), France (December 1996)

    Google Scholar 

11. Deutsch, A.: Operational Models of Programming Languages and Representations of Relations on Regular Languages with Application to the Static Determination of Dynamic Aliasing Properties of Data. PhD thesis, École Polytechnique, France (April 1992)

    Google Scholar 

12. Deutsch, A.: Interprocedural may-alias analysis for pointers: beyond k-limiting. In: ACM Symp. on Programming Language Design and Implementation (PLDI 1994), Orlando, Florida, pp. 230–241 (June 1994)

    Google Scholar 

13. Elgot, C.C., Mezei, J.E.: On relations defined by generalized finite automata. IBM J. of Research and Development, 45–68 (1965)

    Google Scholar 

14. Epstein, D.B.A., Cannon, J.W., Holt, D.F., Levy, S.V.F., Paterson, M., Thurston, W.: Word Processing in Groups. Jones and Bartlett Publishers, Boston (1992)

    MATH  Google Scholar 

15. Esparza, J., Knoop, J.: An automata-theoretic approach to interprocedural data-flow analysis. In: Thomas, W. (ed.) FOSSACS 1999. LNCS, vol. 1578, pp. 14–30. Springer, Heidelberg (1999)

    Chapter  Google Scholar 

16. Esparza, J., Podelski, A.: Efficient algorithms for pre* and post* on interprocedural parallel flow graphs. In: ACM Symp. on Principles of Programming Languages (PoPL 2000), pp. 1–11 (2000)

    Google Scholar 

17. Feautrier, P.: Array expansion. In: ACM Intl. Conf. on Supercomputing, St. Malo, France, pp. 429–441 (July 1988)

    Google Scholar 

18. Feautrier, P.: Dataflow analysis of scalar and array references. Intl. J. of Parallel Programming 20(1), 23–53 (1991)

    Article  MATH  Google Scholar 

19. Feautrier, P.: Some efficient solutions to the affine scheduling problem, part II, multidimensional time. Intl. J. of Parallel Programming 21(6), 389–420 (1992); see also Part I, one dimensional time 21(5), 315–348

    Article  MathSciNet  MATH  Google Scholar 

20. Feautrier, P.: A parallelization framework for recursive tree programs. In: EuroPar 1998, Southampton, UK. LNCS. Springer, Heidelberg (1998)

    Google Scholar 

21. Fradet, P., Metayer, D.L.: Shape types. In: ACM Symp. on Principles of Programming Languages (PoPL 1997), Paris, France, pp. 27–39 (January 1997)

    Google Scholar 

22. Gerlek, M.P., Stoltz, E., Wolfe, M.J.: Beyond induction variables: detecting and classifying sequences using a demand-driven ssa form. ACM Trans. on Programming Languages and Systems 17(1), 85–122 (1995)

    Article  Google Scholar 

23. Ghiya, R., Hendren, L.J.: Is it a tree, a DAG, or a cyclic graph? A shape analysis for heap-directed pointers in C. In: ACM Symp. on Principles of Programming Languages (PoPL 1996), St. Petersburg Beach, Florida, pp. 1–15 (January 1996)

    Google Scholar 

24. Giavitto, J.-L., Michel, O., Sansonnet, J.-P.: Group-based fields. In: Proc. of the Parallel Symbolic Languages and Systems (October 1995); see also Design and Implementation of 8^1/2, a Declarative Data-Parallel Language, RR 1012, Laboratoire de Recherche en Informatique, Université Paris Sud 11, France (1995)

    Google Scholar 

25. Hampapuram, H., Yang, Y., Das, M.: Symbolic path simulation in path-sensitive dataflow analysis. In: Proc. of the ACM Workshop on Program Analysis for Software Tools and Engineering (PASTE 2005), Lisbon, Portugal, pp. 52–58 (September 2005)

    Google Scholar 

26. Harrison, W.L.: The interprocedural analysis and automatic parallelisation of Scheme programs. Lisp and Symbolic Computation 2(3), 176–396 (1989)

    Article  MathSciNet  Google Scholar 

27. Hendren, L.J., Hummel, J., Nicolau, A.: Abstractions for recursive pointer data structures: improving the analysis and transformation of imperative programs. In: ACM Symp. on Programming Language Design and Implementation (PLDI 1992), pp. 249–260. San Francisco, Calfifornia (1992)

    Chapter  Google Scholar 

28. Klarlund, N., Schwartzbach, M.I.: Graph types. In: ACM Symp. on Principles of Programming Languages (PoPL 1993), Charleston, South Carolina, pp. 196–205 (January 1993)

    Google Scholar 

29. Maydan, D.E., Amarasinghe, S.P., Lam, M.S.: Array dataflow analysis and its use in array privatization. In: 20th ACM Symp. on Principles of Programming Languages, Charleston, South Carolina, pp. 2–15 (January 1993)

    Google Scholar 

30. Might, M., Shivers, O.: Environment analysis via Delta CFA. In: ACM Symp. on Principles of Programming Languages (PoPL 2006), Charleston, South Carolina, pp. 127–140 (January 2006)

    Google Scholar 

31. Nielson, F., Nielson, H., Hankin, C.: Principles of Program Analysis. Springer, Heidelberg (1999)

    MATH  Google Scholar 

32. Okasaki, C.: Functional data structures. Advanced Functional Programming, 131–158 (1996)

    Google Scholar 

33. Pelletier, M., Sakarovitch, J.: On the representation of finite deterministic 2-tape automata. Theoretical Computer Science 225(1–2), 1–63 (1999)

    Article  MathSciNet  MATH  Google Scholar 

34. Perrin, G.-R., Darte, A. (eds.): The Data Parallel Programming Model. LNCS, vol. 1132. Springer, Heidelberg (1996)

    Google Scholar 

35. Pop, S., Cohen, A., Silber, G.-A.: Induction variable analysis with delayed abstractions. In: Conte, T., Navarro, N., Hwu, W.-m.W., Valero, M., Ungerer, T. (eds.) HiPEAC 2005. LNCS, vol. 3793, pp. 218–232. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

36. Pugh, W.: A practical algorithm for exact array dependence analysis. Communications of the ACM 35(8), 27–47 (1992)

    Article  Google Scholar 

37. Reps, T., Horwitz, S., Sagiv, M.: Precise interprocedural dataflow analysis via graph reachability. In: ACM Symp. on Principles of Programming Languages (PoPL 1995), San Francisco, CA (January 1995)

    Google Scholar 

38. Reps, T.W., Schwoon, S., Jha, S.: Weighted pushdown systems and their application to interprocedural dataflow analysis. In: Cousot, R. (ed.) SAS 2003. LNCS, vol. 2694, pp. 189–213. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

39. Rozenberg, G., Salomaa, A. (eds.): Handbook of Formal Languages. Word Language Grammar, vol. 1. Springer, Heidelberg (1997)

    MATH  Google Scholar 

40. Rozenberg, G., Salomaa, A. (eds.): Handbook of Formal Languages. Beyond Words, vol. 3. Springer, Heidelberg (1997)

    MATH  Google Scholar 

41. Sagiv, S., Reps, T.W., Wilhelm, R.: Parametric shape analysis via 3-valued logic. In: ACM Symp. on Principles of Programming Languages (PoPL 1999), San Antonio, Texas, pp. 105–118 (January 1999)

    Google Scholar 

42. Sharir, M., Pnueli, A.: Program Flow Analysis: Theory and Applications. In: Two Approaches to Interprocedural Data Flow Analysis. Prentice Hall, Englewood Cliffs (1981)

    Google Scholar 

43. Venet, A.: Nonuniform alias analysis of recursive data structures and arrays. In: Hermenegildo, M.V., Puebla, G. (eds.) SAS 2002. LNCS, vol. 2477, pp. 36–51. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

44. Venet, A.: A scalable nonuniform pointer analysis for embedded programs. In: Giacobazzi, R. (ed.) SAS 2004. LNCS, vol. 3148, pp. 149–164. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

45. Wolfe, M.J.: High Performance Compilers for Parallel Computing. Addison-Wesley, Reading (1996)

    MATH  Google Scholar 

46. Wu, P., Cohen, A., Padua, D., Hoeflinger, J.: Monotonic evolution: an alternative to induction variable substitution for dependence analysis. In: ACM Intl. Conf. on Supercomputing (ICS 2001), Sorrento, Italy (June 2001)

    Google Scholar 

Download references