All structured programs have small tree width and good register allocation
type: Item
instance of: scholarly article
title: All structured programs have small tree width and good register allocation
zbMATH Open document ID: 0924.68023
author: Mikkel Thorup
published in: Information and Computation
publication date: 1998-11-10T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68N01
Mathematics Subject Classification ID: 68N15
zbMATH DE Number: 1221106
zbMATH Keywords: register-allocation problem
reviewed by: Anatoly V. Anisimov
describes a project that uses: Modula
describes a project that uses: ALGOL 60
MaRDI profile type: Publication
full work available at URL: inco.1997.2697
OpenAlex ID: W1989556004
cites work: Generalized dominators for structured programs
cites work: Complexity of Finding Embeddings in a k-Tree
cites work: Easy problems for tree-decomposable graphs
cites work: Linear time algorithms for NP-hard problems restricted to partial k- trees
cites work: Q4291429
cites work: A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
cites work: Complexity of path-forming games
cites work: Q4250226
cites work: Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
cites work: Monadic second-order evaluations on tree-decomposable graphs
cites work: Q5684216
cites work: Fugitive-search games on graphs and related parameters
cites work: Q5530093
cites work: The Complexity of Coloring Circular Arcs and Chords
cites work: Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
cites work: The intersection graphs of subtrees in trees are exactly the chordal graphs
cites work: A still better performance guarantee for approximate graph coloring
cites work: Q4886067
cites work: Q4055144
cites work: On the hardness of approximating minimization problems
cites work: Revised report on the algorithmic language ALGOL 60
cites work: Graph minors. I. Excluding a forest
cites work: Graph minors. XIII: The disjoint paths problem
cites work: Region-based memory management
cites work: The programming language Pascal
cites work: Q3221372
DOI: 10.1006/INCO.1997.2697
description: scientific article; zbMATH DE number 1221106