A region analysis algorithm for the live variables problem

DOI10.1007/BF02242267MaRDI QIDQ799117zbMATH OpenOpenAlexFDO

Authors Zbigniew J. Czech

Publication date 1984

Published in Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02242267

zbMATH Keywords

data flow analysisglobal program optimizationinterval analysislive variablesreducible flow graphsregion analysis algorithmtime complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60) Graph theory (including graph drawing) in computer science (68R10)

Review text

An algorithm to solve the live variables problem on reducible flow graphs is presented. It is based on the concept of a region of a flow graph. The algorithm is compared for time complexity with the well-known round-robin version of the iterative algorithm on self-replicating families of reducible flow graphs. The results of comparison are inconclusive in that the region analysis algorithm requires fewer bit- vector operations on some graphs and more on others.

Recommendations

• scientific article; zbMATH DE number 3885296
• scientific article; zbMATH DE number 3870590
• A Fast and Usually Linear Algorithm for Global Flow Analysis
• An efficient general iterative algorithm for dataflow analysis
• Using locality of flow in dataflow analyses.

Cites work

• A Comparison of Two Algorithms for Global Data Flow Analysis
• A Fast and Usually Linear Algorithm for Global Flow Analysis
• A global flow analysis algorithm
• A program data flow analysis procedure
• A Simple Algorithm for Global Data Flow Analysis Problems
• Characterizations of Reducible Flow Graphs
• Fast algorithms for the elimination of common subexpressions
• Global Data Flow Analysis and Iterative Algorithms
• scientific article; zbMATH DE number 3485178 (Why is no real title available?)
• scientific article; zbMATH DE number 3485226 (Why is no real title available?)
• scientific article; zbMATH DE number 3551830 (Why is no real title available?)
• scientific article; zbMATH DE number 3592938 (Why is no real title available?)
• scientific article; zbMATH DE number 3617563 (Why is no real title available?)
• scientific article; zbMATH DE number 3388535 (Why is no real title available?)
• Monotone data flow analysis frameworks
• Node listings for reducible flow graphs
• Use-definition chains with applications

Cited in

(3)

• scientific article; zbMATH DE number 3885296 (Why is no real title available?)
• scientific article; zbMATH DE number 3870590 (Why is no real title available?)
• A Fast and Usually Linear Algorithm for Global Flow Analysis

This page was built for publication: A region analysis algorithm for the live variables problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q799117)