Skip to Main content Skip to Navigation
Reports

The Treewidth of Java Programs

Jens Gustedt 1 Ole A. Maehle Jan Arne Telle
1 RESEDAS - Software Tools for Telecommunications and Distributed Systems
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Intuitively, the treewidth of a graph $G$ measures how close $G$ is to being a tree. The lower the treewidth, the faster we can solve various optimization problems on $G$, by dynamic programming along the tree structure. In the paper M.Thorup, All Structured Programs have Small Tree-Width and Good Register Allocation [8] it is shown that the control-flow graph of any goto-free C program is at most 6. This result opened for the possibility of applying the dynamic programming bounded treewidth algorithms to various compiler optimization tasks. In this paper we explore this possibility, in particular for Java programs. We first show that even if Java does not have a goto, the labelled break and continue statements are in a sense equally bad, and can be used to construct Java programs that are arbitrarily hard to understand and optimize. For Java programs lacking these labelled constructs Thorup's result for C still holds, and in the second part of the paper we analyze the treewidth of label-free Java programs empirically. We do this by means of a parser that computes a tree-decomposition of the control-flow graph of a given Java program. We report on experiments running the parser on several of the Java API packages, and the results tell us that on average the treewidth of the control-flow graph of these Java programs is no more than 2.5. This is the first empirical test of Thorup's result, and it confirms our suspicion that the upper bounds of treewidth 6, 5 and 4 are rarely met in practice, boding well for the application of treewidth to compiler optimization.
Document type :
Reports
Complete list of metadatas

Cited literature [9 references]  Display  Hide  Download

https://hal.inria.fr/inria-00072269
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 8:16:05 PM
Last modification on : Sunday, May 20, 2018 - 8:20:10 PM
Long-term archiving on: : Sunday, April 4, 2010 - 11:01:24 PM

Identifiers

  • HAL Id : inria-00072269, version 1

Collections

Citation

Jens Gustedt, Ole A. Maehle, Jan Arne Telle. The Treewidth of Java Programs. [Research Report] RR-4318, INRIA. 2001, pp.11. ⟨inria-00072269⟩

Share

Metrics

Record views

225

Files downloads

528