Drot.mesa
Copyright Ó 1987 by Xerox Corporation. All rights reserved.
Csaba Gabor August 19, 1987 8:19:18 pm PDT
Bertrand Serlet August 21, 1987 2:29:59 pm PDT
DIRECTORY
DrotBool, DrotCover, Core;
Drot: CEDAR DEFINITIONS
~ BEGIN OPEN DrotBool;
Generating Cells From Ropes
CellTypeFromExpressions: PROC [outputs: LIST OF ROPE, fanout: INT ← 4] RETURNS [Core.CellType];
What it does
Syntax:
output == variable assignment expression
assignment == ← / =
expression == variable | ~expression | (expression) | expression + expression | expression * expression
The order of precedence is ~, *, +
Parsing step
BoolTreeFromExpressionList: PROC [outputs: LIST OF ROPE, includeGlobalVariablesp: BOOLFALSE] RETURNS [tree: Dag];
Given a list of expressions, this will return a Dag which is a representation for this set of expressions. Each gate is represented as a node (as are inputs) with the inputs to a gate being its children.
AugmentBoolTreeBySingleExpression: PROC [tree: Dag, output: ROPE];
Given a single expression and a Dag, this will cause that expression to be incorporated into the Dag.
Building a Dag
MakeNewBoolTree: PROC [] RETURNS [tree: Dag];
This creates a new Dag with no children
MakeNewVariableNode: PROC [tree: Dag, name: ROPE] RETURNS [newNode: Node];
This creates a new node in tree which is treated as an input node with name the given name.
MakeNewNotNode: PROC [tree: Dag, node: Node] RETURNS [newNode: Node];
This creates a new node in tree which is the not of node.
MakeNewOrNode: PROC [tree: Dag, nodes: LIST OF Node] RETURNS [newNode: Node];
This creates a new node in tree which is the OR of all the nodes in the list of nodes.
MakeNewAndNode: PROC [tree: Dag, nodes: LIST OF Node] RETURNS [newNode: Node];
This creates a new node in tree which is the AND of all the nodes in the list of nodes.
NameNode: PROC [node: Node, name: ROPE];
This assigns the specified name to the specified node. This is useful for later referencing that node by name.
MakeOutputNode: PROC [tree: Dag, node: Node];
This causes the specified node to be viewed as one of the outputs.
Creating CellType from Dag
CreateCellTypeFromDag: PROC [tree: Dag, fanout: INT ← 4] RETURNS [Core.CellType];
This takes as input a tree (and fanout limitation) and returns the cell type generated. Currently, since there is only one library, the covering functions are internally generated. This is the main routine (the control)
RemoveDuplicateNodes: PROC [tree: Dag] RETURNS[modified: BOOL];
I think that what this is supposed to do is get rid of any duplicate expressions within the tree --
ReduceFanout: PROC [tree: Dag, fout: INT];
This splits nodes in tree where the fanout is greater than fout--
TwoifyTree: PROC [tree: Dag];
This will yield a tree where each node has fan-in at most 2 --
END.