We show that attribute grammar techniques, used in the field of programming languages, form an efficient basis for the implementation of systems supporting hierarchical and incremental VLSI design. Such systems can interactively compute estimates for the speed and power dissipation of a circuit, check adherence to clocking disciplines, and recompute these quantities at reasonable cost as the designer changes the circuit, uses new modules, subsystems or standard cells. The bidirectional properties of devices and wires and the frequent use of signal feedback as a design technique imply that many properties of circuits are circular. Previous research has dealt almost exclusively with noncircular attribute grammars since this condition easily guarantees the existence and uniqueness of a consistent assignment of attribute values. We note that the noncircularity condition for attribute grammars is not a necessary one, it is sufficient that all circular attributes have a least fixed point obtainable with finite (and efficient) computation. We present efficient algorithms for exhaustive and incremental evaluation of circular attributes under any conditions that guarantee finite convergence. The algorithms are derived from those for noncircular attribute grammars by partitioning the underlying attribute dependency graph into its strongly connected components and ordering the evaluations to follow a topological sort of the resulting directed acyclic graph. The algorithms are efficient in the sense that their worst-case running time is proportional to the cost of computing the fixed points of only those strongly connected components containing affected attributes or attributes directly dependent on affected attributes. In the case that the attribute grammar is noncircular, both algorithms are optimal. We examine the algorithms under the condition that all circular attributes have monotone equations with values defined over a lattice of bounded height. Two examples of attributes meeting these conditions are given. As an example of a nontrivial and useful property which the proposed techniques can easily handle, we present attributes which solve the All Bidirectional Edges problem that labels the direction of information flow in a circuit. In a more complicated example, we present attributes that implement a switch-level logic simulator for CMOS circuits.
