Browse Prior Art Database

Preserving Textual-Ordered States in a Control Flow Graph

IP.com Disclosure Number: IPCOM000104225D
Original Publication Date: 1993-Mar-01
Included in the Prior Art Database: 2005-Mar-18
Document File: 2 page(s) / 67K

Publishing Venue

IBM

Related People

Wyman, B: AUTHOR

Abstract

A method of preserving textually-ordered operations in a control flow graph by adding instructions to the graph is disclosed.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Preserving Textual-Ordered States in a Control Flow Graph

      A method of preserving textually-ordered operations in a
control flow graph by adding instructions to the graph is disclosed.

      When an instruction stream contains textually-ordered
operations, the conversion of the instruction stream to a control
flow graph requires that these textually-ordered states be saved at
the start of each basic block.  This allows the original state to be
reproduced at any point in the control flow graph.

      However, depending on the amount of state information required,
the storage requirements for saving these states at each block
boundary can become significant.  A method to preserve the state
information in the control flow graph without having to maintain the
captured state information is desirable.

      If textual state change operations are applicable within a
basic block, they must have a representation in the block's
instruction stream; otherwise, each state change would require the
basic block to be broken.

      During the first pass through the instruction stream, capture
the textually-ordered state information both at the start and end of
each basic block.  Then, in a process that traverses the graph,
inspect each control flow arc.  For each arc along which there is a
change of state (e.g., the predecessor's end-of-block state does not
match the head's start-of-block state), build the sequence of
state-change instructions that transform the predecessor (PRED)
block's exit state into the successor (SUCC) block's entry state, and
insert the instructions into the instruction stream of a basic block.

      The basic block into which this instruction sequence (called
the State Change Delta) should be inserted will depend on the other
adjacenc...