Browse Prior Art Database

Algorithm for Tracing Execution Paths to a Given Location in a Program

IP.com Disclosure Number: IPCOM000075317D
Original Publication Date: 1971-Sep-01
Included in the Prior Art Database: 2005-Feb-24
Document File: 4 page(s) / 78K

Publishing Venue

IBM

Related People

Soule, K: AUTHOR

Abstract

This programming algorithm can trace all program paths which would cause a given instruction to be executed.

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 44% of the total text.

Page 1 of 4

Algorithm for Tracing Execution Paths to a Given Location in a Program

This programming algorithm can trace all program paths which would cause a given instruction to be executed.

The algorithm involves the use of the following:
1) A set of Master Records which describe the

program to be analyzed.
2) A table called the Path Table. This table is

built in a storage unit and represents the path

currently being built.

After being completely built, the path represented in the Path Table is written onto an external device. The individual entries in the Path Table are then used to determine, in a systematic manner, other paths by which control may be transferred to the given instruction.

The instructions of the program being traced are grouped into segments. A segment consists of one or more instructions which occupy consecutively accessed locations in storage, and which are executed as a unit. Any instruction to which control may be transferred by an instruction other than the prior instruction is the beginning of a segment; any instruction which may transfer control to other than the next sequential instruction is the end of a segment. Also, any instruction following the last instruction of a segment begins a new segment, and any instruction preceding the first instruction of a segment ends a segment.

Each instruction in the program being traced is described by one Master Record. Master Records are ordered by the location of the instructions they describe. The Master Record for the first instruction in a segment includes a list of all instructions which may transfer control to that segment. These are called "From Addresses" in the flow-chart.

Each entry in the Path Table represents one segment and the Path Table entries are ordered by the sequence in which the segments will be executed. Since each path must end with the given segment, the given segment is represented by the last entry in the Path Table.

The following paragraphs describe the process pictured in the flowcharts (Fig. 1). The flowcharts are followed by definitions of the special notation used. Building a Path.

Since paths are built backwards with respect to the order in which the segments would be executed, the Path Table is filled with entries starting at the bottom. When building a path, the list of From Addresses in the Master Record for the first instruction in the given segment is accessed. The first From Address in the list is that of the last instruction of the prior segment in the path. The segment pointed to by this From Address is added to the path and is represented by the prior entry in the Path Table. In like manner, the first From Address in the Master Record for the first instruction of each segment in the path is used to determine the prior segment.

1

Page 2 of 4

(This is described in the flowchart blocks beginning at the block 1 and ending at the later connector blocks 5, 6 or 7.) Various criteria may be used to terminate the construction of a path. When t...