# Generation of Node Lists Using Segment Analysis

Original Publication Date: 1980-Dec-01

Included in the Prior Art Database: 2005-Feb-10

## Publishing Venue

IBM

## Related People

Rutledge, JD: AUTHOR [+2]

## Abstract

Two algorithms are describe for generating node lists for reducible graphs. The length of the node list produced by the algorithms given here is bounded above by (d+1)n, where n is the number of nodes in the graph and d is the number of nodes that are tails of back edges. For realistic programs, however, the algorithms given here produce much shorter node lists, generally of length less than 3n.**This text was extracted from a PDF file.**

**At least one non-text object (such as an image or picture) has been suppressed.**

**This is the abbreviated version, containing approximately 23% of the total text.**

__Page 1 of 6__**Generation of Node Lists Using Segment Analysis **

Two algorithms are describe for generating node lists for reducible graphs. The length of the node list produced by the algorithms given here is bounded above by (d+1)n, where n is the number of nodes in the graph and d is the number of nodes that are tails of back edges. For realistic programs, however, the algorithms given here produce much shorter node lists, generally of length less than 3n.

INTRODUCTION: Data Flow Analysis is the bringing of relevant
information from each part of a program, via existing paths, to each
other part. It is a prerequisite to global optimization. The three
main global optimization problems are described in the reference [1]
and are as follows:

1. Determination of available expressions to achieve commoning.

2. Determination of reaching definition points, to achieve

constant propagation and variable subsumption.

3. Determination of upward exposed uses, which along with (2)

gives the liveness information for variables, which is

essential for doing register allocation and assignment.

The above three problems will be formulated in terms of the control flow graph of the program for which the analysis is to be done. The nodes of the control flow graph are basic blocks, i.e., sequences of instructions which are always executed in order. If the first instruction of a basic block is executed, then every instruction in the basic block is executed. After the execution of the last instruction in a basic block, control may transfer to any one of a number of basic blocks called the immediate successors of the basic block just executed.

A path in a graph can be described by the sequence of nodes it traverses. The sequence of nodes will be referred to as the path's node description. A path having no repeated nodes is termed a simple path. A path having as its only repetition the first and last nodes is called a simple cycle. A simple cycle beginning with node n will be referred to as a cycle beginning with n.

A node list [2,4] is an ordered sequence of nodes of a control flow graph (with possible repetitions), such that every simple path in the graph is a subsequence of the node list. This has been called by some authors a strong node list [4].

2. PREAMBLE TO NODE LIST ALGORITHMS: Before discussing the algorithms, some background material on segment analysis is necessary.

By performing a depth first search (DFS)[S] on a control flow graph, the following information can be obtained. The search establishes an order 0 among the nodes, which will be called the search order. It also classifies the edges into forward (F) and backward (B) edges.

The depth first search algorithm for the graph G = (V,E, n(0), where V is the set of vertices, E the set of directed edges and n(0) the unique entry node, is as follows: Input: A graph G = (V,E, n(0)) represented by the successor list s(v). for

1

__Page 2 of 6__v Epsilon V. Outputs: (1) A partition of E into a set B of back edges and a...