Browse Prior Art Database

Algorithm for Control Flow Analysis in Independent Technology Logic

IP.com Disclosure Number: IPCOM000107790D
Original Publication Date: 1992-Mar-01
Included in the Prior Art Database: 2005-Mar-22
Document File: 5 page(s) / 169K

Publishing Venue

IBM

Related People

Caillet, B: AUTHOR [+2]

Abstract

Nowadays, a large design is described by means of a logic description independent of any technology. A piece of logic is defined as having Primary Inputs (PIs), Primary Outputs (POs), Latches and Internal Signals (ISs). The logic control flow is a series of decision elements. Each control flow element is called a "path". A path can go from PI to Latch, from PI to PO, from Latch to Latch or from Latch to PO. "ASSIGN" statements are used to set PO and Latches. "DECISION" statements are used to test the PI, Latches and IS: they are basically "IF...THEN...ELSE" statements. A control flow SLICE includes the series of statements that give the "trace" of an ASSIGN statement through all the decision elements that lead to the ASSIGN by means of GOTO(label) keywords. Figure 1 shows the characteristics of such descriptions for a logic.

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

Algorithm for Control Flow Analysis in Independent Technology Logic

       Nowadays, a large design is described by means of a logic
description independent of any technology. A piece of logic is
defined as having Primary Inputs (PIs), Primary Outputs (POs),
Latches and Internal Signals (ISs). The logic control flow is a
series of decision elements. Each control flow element is called a
"path". A path can go from PI to Latch, from PI to PO, from Latch
to Latch or from Latch to PO. "ASSIGN" statements are used to set PO
and Latches. "DECISION" statements are used to test the PI, Latches
and IS: they are basically "IF...THEN...ELSE" statements. A control
flow SLICE includes the series of statements that give the "trace" of
an ASSIGN statement through all the decision elements that lead to
the ASSIGN by means of GOTO(label) keywords. Figure 1 shows the
characteristics of such descriptions for a logic. One possible
description of the control flow is generated by an existing program
identified as B*.

      A problem associated with such descriptions is to recognize all
the "paths" defined by a control flow because there are not only
those built by following the "GOTO(label)" sequencing but also those
built by transitivity through "assigned" and "referenced" signals in
the logic (only signals are to be considered because paths end at
latches...):
     . A signal is "assigned" when it is the result of a Boolean
(AND, OR, XOR, NAND,...)  or arithmetic (ADD, SUB,...) operation. It
is basically the output of a logic function. Assignments can be found
only in ASSIGN statements.
     . A signal is "referenced" when it is used to build another
signal by one of the above operations. It is basically the input of a
logic function.

      References can be found in both ASSIGN (ASSIGN A$=B$ references
B$) and DECISION (IF A$=1 references A$) statements. See Figures 2
and 3..

      An algorithm is provided to recognize all the "paths" defined
in a control flow, based on the analysis of the B* control file
description and the respective indentation of all the elements. Such
an algorithm comprises 6 steps.
      1.   All B* control flow SLICES (i.e., from ASSIGN to blank
line) are studied to define two tables:
       .   One giving the number of decision elements of each SLICE.
       .   One giving, for each decision element, its indentation v/s
the value 0 for the ASSIGN statement.
      2.   All B* ASSIGN statements are analyzed and are put in
tables for each control flow SLICE:
      ...