×

zbMATH — the first resource for mathematics

All structured programs have small tree width and good register allocation. (English) Zbl 0924.68023
The register-allocation problem for a program written in an imperative language is modeled as the coloring problem of the interference graph of the control-flow graph \(G\) of the program. The lifetime of a variable is a connected subgraph of \(G\), and the interference graph is the intersection graph of the set \(X\) of all lifetimes of variables.
For general programs with unrestricted gotos, the control-flow graph can be any graph and so can interference graph. Therefore one cannot in polynomial time color the interference graph. The main result of this paper is the following statement.
For structured (goto-free) programs, including for example, short circuit evaluation and multiple exits from loops, it is possible to do register allocation in polynomial time within a factor 4 form optimality.

MSC:
68N01 General topics in the theory of software
68N15 Theory of programming languages
Software:
ALGOL 60; Modula
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alstrup, S.; Lauridsen, P.W.; Thorup, M., Generalized dominators for structured programs, Proceedings of the 3rd static analysis symposium, Lecture notes in computer science, 1145, (1996), p. 42-51 · Zbl 0961.68021
[2] Aho, A.V.; Sethi, R.; Ullman, J.D., Compilers: principles, techniques, and tools, (1986), Addison-Wesley Reading
[3] Arnborg, S.; Corneil, D.G.; Proskorowski, A., Complexity of finding embeddings in ak, SIAM J. alg. discrete methods, 8, 277-284, (1987) · Zbl 0611.05022
[4] Arnborg, S.; Lagergren, J.; Seese, D., Easy problems for tree decomposable graphs, J. algorithms, 12, 308-340, (1991) · Zbl 0734.68073
[5] Arnborg, S.; Proskorowski, A., Linear time algorithms for NP-hard problems restricted to partialk, SIAM J. alg. discrete methods, 23, 11-24, (1989) · Zbl 0666.68067
[6] Birkdal, L.; Tofte, M.; Vejlstrup, M., From region inference to von neuman machines via region representation inference, Proc. POPL’96, (1996), p. 171-183
[7] Bodlaender, H.L., A tourist guide through tree width, Acta cybernetica, 11, 1-23, (1993) · Zbl 0804.68101
[8] Bodlaender, H.L., A linear time algorithm for finding tree decompositions of small tree width, SIAM J. comput., 25, 1305-1317, (1996) · Zbl 0864.68074
[9] Bodlaender, H.L., Complexity of path forming games, Theoret. comput. sci., 110, 215-245, (1993) · Zbl 0776.90100
[10] Bodlaender, H.L.; Gilbert, J.R.; Hafsteinsson, H.; Kloks, T., Approximating tree width, path width, frontsize, and shortest elimination tree, J. algorithms, 18, 221-237, (1995)
[11] Bodlaender, H. L. Gustedt, J. Telle, J. A. 1998, Linear-time register allocation for a fixed number of registers, Proc. 9th SODA · Zbl 0930.68016
[12] Borie, R.B.; Parker, R.G.; Tovey, C.A., Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families, Algorithmica, 7, 555-581, (1992) · Zbl 0753.05062
[13] Briggs, P., Register allocation via graph coloring, (1992), Rice University
[14] Briggs, P.; Cooper, K.D.; Kennedy, K.; Torczon, L., Coloring heuristics for register allocation, Proc. SIGPLAN’89 conf. programming language design and implementation, (1989), p. 275-284
[15] Callahan, D.; Koblenz, B., Register allocation via hierarchical graph coloring, Proc. SIGPLAN’91conf. programming language design and implementation, (1991), p. 192-203
[16] Chaitin, G.J., Register allocation and spilling via graph coloring, Proc. SIGPLAN’82 symp. compiler construction, (1982), p. 98-105
[17] Chaitin, G.J.; Auslander, M.A.; Chandra, A.K.; Cocke, J.; Hoplins, M.E.; Markstein, P.W., Register allocation via graph coloring, Comput. lang., 6, 47-57, (1981)
[18] Courcelle, B.; Mosbah, M., Monadic second-order evaluations on tree decomposable graphs, Theoret. comput. sci., 109, 49-82, (1993) · Zbl 0789.68083
[19] Dahl, O.J.; Dijkstra, E.W.; Hoare, C.A.R., Structured programming, (1972), Academic Press London
[20] Dendris, N.; Kirousis, L.; Thilkos, D., Fugitive-search games on graphs and related parameters, Theoret. comput. sci., 172, 233-254, (1997) · Zbl 0903.68052
[21] Dijkstra, E.W., Go to statement considered harmful, Comm. assoc. comput. Mach., 11, 147-148, (1968)
[22] Ershov, A.P., Reduction of the problem of memory allocation in programming to the problem of colouring the vertices of a graph, Dokl. acad. nauk SSSR, 142, 785-787, (1962)
[23] Garey, M.R.; Johnson, D.S.; Miller, G.L.; Papadimitriou, C.H., The complexity of coloring circular arcs and chords, SIAM J. alg. discrete methods, 1, 216-227, (1980) · Zbl 0499.05058
[24] Gavril, F., Algorithms for minimum coloring, maximum clique, minimum covers by cliques, and maximum independent set of chordal graphs, SIAM J. comput., 1, 180-187, (1972) · Zbl 0227.05116
[25] Gavril, F., The intersection graph of subtrees in trees are exactly the chordal graphs, J. combin. theory ser. B, 16, 47-56, (1974) · Zbl 0266.05101
[26] Gupta, R.; Soffa, M.L.; Steele, T., Register allocation via clique separators, Proc. SIGPLAN’89 conf. programming language design and implementation, (1989), p. 264-274
[27] Halldórsson, M.M., A still better performance guarantee for approximate graph coloring, Inform. process lett., 45, 19-23, (1993) · Zbl 0768.68043
[28] Kannan, S.; Proebsting, T., Register allocation in structured programs, Proc. 6th SODA, (1995), p. 360-368 · Zbl 0849.68040
[29] Kernighan, B.R.; Ritchie, D.M., The C programming language, (1978), Prentice-Hall
[30] Knuth, D.E., Structured programming with go to statements, ACM comput. surveys, 6, 261-301, (1974) · Zbl 0301.68014
[31] Lund, C.; Yannakakis, M., On the hardness of approximating minimization problems, J. assoc. comput. Mach., 41, 960-981, (1994) · Zbl 0814.68064
[32] Naur, P., Revised report on the algorithmic language algol 60, Comm. assoc. comput. Mach., 6, 1-17, (1963) · Zbl 0109.35105
[33] Naur, P., Go to statements and good algol style, Bit, 3, 204-208, (1963)
[34] Nishizeki, T.; Takamizawa, K.; Saito, N., Algorithms for detecting series-parallel graphs and D-charts, Trans. inst. elect. commun. engrg. Japan, 59, 259-260, (1976)
[35] Norris, C.; Pollock, L.L., Register allocation over the program dependence graph, Proc. SIGPLAN’94 conf. programming language design and implementation, (1994), p. 266-277
[36] Robertson, N.; Seymour, P.D., Graph minors I: excluding a forest, J. combin. theory ser. B, 35, 39-61, (1983) · Zbl 0521.05062
[37] Robertson, N.; Seymour, P.D., Graph minors XIII: the disjoint paths problem, J. combin. theory ser. B, 63, 65-110, (1995) · Zbl 0823.05038
[38] Tofte, M.; Talpin, J.-P., Region-based memory management, Inform. and comput., 132, 109-176, (1997) · Zbl 0876.68027
[39] Wirth, N., The programming language PASCAL, Acta informatica, 1, 35-63, (1971) · Zbl 0205.18603
[40] Wirth, N., Programming in modula-2 (3rd corr. ed.), (1985), Springer-Verlag Berlin/New York · Zbl 0557.68007
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.