PLAOpsImplD.mesa
Copyright c 1984 by Xerox Corporation. All rights reserved.
Don Curry April 30, 1987 10:20:23 pm PDT
Last Edited by: Don Curry July 18, 1988 2:22:02 pm PDT
DIRECTORY
BasicTime, BoolEx, CommandTool, FileNames, FS, RefTab, SymTab, IO, PLAOps, REFBit, RefText, Rope, RopeList;
PLAOpsImplD: CEDAR PROGRAM
IMPORTS CommandTool, BoolEx, FileNames, FS, RefTab, SymTab, IO, PLAOps, RefText, Rope, RopeList, REFBit EXPORTS PLAOps =
BEGIN
OPEN PLAOps;
OpIndex: TYPE = BoolEx.OpIndex;
CopyPLA: PUBLIC PROC[old: PLA] RETURNS[new: PLA] = {
new   ← NewPLA[old.data, old.out, old.name];
new.time  ← old.time;
new.termList ← CopyTermList[old.termList]};
plas: SymTab.Ref ← SymTab.Create[];
FlushPLACache: PUBLIC PROC = {SymTab.Erase[plas]};
ReadPLAFile: PUBLIC PROC
[name: IO.ROPE, log:IO.STREAMNIL, useCache: BOOLFALSE] RETURNS[pla: PLA] = {
ENABLE FS.Error => IF error.group = user THEN {
log.PutRope[error.explanation];
CONTINUE };
fullPathName: IO.ROPE;
plaName:   IO.ROPE;
rope:    IO.ROPE;
inName:   IO.ROPE;
outName:   IO.ROPE;
iForm:   Format;
oForm:   Format;
iFormat:   Format;
oFormat:   Format;
checkedOnce: BOOL   ← FALSE;
length:   CARDINAL ← 0;
time:    BasicTime.GMT;
inStm:    IO.STREAM;
aliasTab:   SymTab.Ref ← NIL;
IF log = NIL THEN log ← IO.noWhereStream;
IF useCache AND SymTab.Fetch[plas, name].found THEN {
pla ← CopyPLA[NARROW[SymTab.Fetch[plas, name].val]];
log.PutF["PLA: %g\n", IO.rope[name]];
RETURN[pla]};
fullPathName ← FileNames.FileWithSearchRules[
root:     name,
defaultExtension: ".ttt",
searchRules:   LIST[initialWorkingDirectory]].fullPath;
plaName ← FileNames.GetShortName[fullPathName];
plaName ← plaName.Substr[0, plaName.Index[0, "."]];
inStm  ← FS.StreamOpen[fileName: fullPathName];
IF inStm=NIL THEN RETURN[NIL];
DO
ENABLE IO.EndOfStream => EXIT;
rope ← IO.GetCedarTokenRope[inStm].token; -- Skips comments
SELECT TRUE FROM
Rope.Equal[rope, "Name"]  => {plaName  ← IO.GetTokenRope[inStm].token};
Rope.Equal[rope, "Date"]  =>
{[ ] ← IO.GetChar[inStm]; time    ← IO.GetTime[inStm]};
Rope.Equal[rope, "InType"] => {inName  ← IO.GetTokenRope[inStm].token;
IF inName.Equal["LIST"] THEN DO
rope ← IO.GetTokenRope[inStm].token;
inName ← inName.Cat[rope];
IF rope.Equal["]"] THEN EXIT;
inName ← inName.Cat[" "] ENDLOOP};
Rope.Equal[rope, "OutType"] => {outName ← IO.GetTokenRope[inStm].token;
IF outName.Equal["LIST"] THEN DO
rope ← IO.GetTokenRope[inStm].token;
outName ← outName.Cat[rope];
IF rope.Equal["]"] THEN EXIT;
outName ← outName.Cat[" "] ENDLOOP};
Rope.Equal[rope, "Alias"] => {
alias: IO.ROPE;
rope ← IO.GetTokenRope[inStm].token;
alias ← IO.GetTokenRope[inStm].token; --
IF aliasTab=NIL THEN aliasTab ← SymTab.Create[];
[]←SymTab.Store[aliasTab, rope, alias]};
Rope.Equal[rope, "Terms"]  =>
{[ ] ← IO.GetChar[inStm];  length  ← IO.GetCard[inStm]};
Rope.Equal[rope, "BitFormat"] => {
WHILE NOT Rope.Equal[IO.GetTokenRope[inStm].token,"BitTotal"] DO ENDLOOP;
[ ]  ← IO.GetChar[inStm]; [ ]   ← IO.GetTokenRope[inStm]};
Rope.Equal[rope, "TermList"] => {[ ] ← IO.GetChar[inStm]; EXIT};
ENDCASE => {LOOP};
ENDLOOP;
IF outName=NILTHEN {log.PutRope["\nI couldn't find 'OutType'\n"]; RETURN[NIL]};
IF inName=NILTHEN {log.PutRope["\nI couldn't find 'InType'\n"]; RETURN[NIL]};
pla ← NewPLA[inName, outName, plaName];
IF pla=NIL THEN {log.PutRope["\nProblem with 'InType' or 'OutType'\n"]; RETURN[NIL]};
pla.time ← time;
DO
ENABLE IO.EndOfStream => EXIT;
rope ← GetLine[inStm];
IF (rope ← TranslateAlias[rope, aliasTab])=NIL THEN LOOP;
IF NOT checkedOnce THEN {
checkedOnce ← TRUE;
[iFormat, oFormat] ← RopeToFormat[rope];
iForm ← REFBit.Desc[pla.data].fieldForm;
oForm ← REFBit.Desc[pla.out].fieldForm;
IF iFormat.size # iForm.size THEN {SIGNAL InvalidTermRope[rope]; EXIT};
IF oFormat.size # oForm.size THEN {SIGNAL InvalidTermRope[rope]; EXIT};
FOR i: NAT IN [0..iFormat.size) DO
IF iFormat[i].bitSize#iForm[i].bitSize THEN
{SIGNAL InvalidTermRope[rope]; EXIT};
REPEAT Exit => EXIT ENDLOOP;
FOR i: NAT IN [0..oFormat.size) DO
IF oFormat[i].bitSize#oForm[i].bitSize THEN
{SIGNAL InvalidTermRope[rope]; EXIT};
};
AppendTerm[RopeToTerm[rope, pla.termList, iForm, oForm], pla.termList];
IF (pla.termList.length MOD 100)=0 THEN log.PutRope["!"] ELSE
IF (pla.termList.length MOD 10)=0 THEN log.PutRope["."];
ENDLOOP;
IF pla.termList.length # length THEN
log.PutF["Number of terms changed to: %g\n", IO.int[pla.termList.length]];
log.PutF["Reading pla on file: %g\n", IO.rope[name]];
log.PutRope[PLAHeader[pla]];
[] ← SymTab.Store[plas, name, CopyPLA[pla]]};
GetLine: PROC[stream: IO.STREAM] RETURNS[line: IO.ROPENIL] = {
buffer: REF TEXT = RefText.ObtainScratch[256];
bLen: NAT ← 0;
chars: INT ← 0;
{ ENABLE UNWIND => RefText.ReleaseScratch[buffer];
DO
char: CHAR ← stream.GetChar[! IO.EndOfStream => IF chars > 0 THEN EXIT ELSE REJECT];
IF char = IO.CR THEN EXIT;
IF char = IO.LF THEN EXIT;
chars ← chars + 1;
IF bLen = 256 THEN {
buffer.length ← bLen;
line ← Rope.Concat[line, Rope.FromRefText[buffer]];
bLen ← 0};
buffer[bLen] ← char;
bLen ← bLen+1;
ENDLOOP};
buffer.length ← bLen;
IF bLen # 0 THEN line ← Rope.Concat[line, Rope.FromRefText[buffer]];
RefText.ReleaseScratch[buffer];
RETURN [line]};
TranslateAlias: PROC[rope: IO.ROPE, aliasTab: SymTab.Ref] RETURNS[new: IO.ROPENIL] = {
IF rope=NIL OR rope.Length=0 THEN RETURN[NIL];
IF aliasTab=NIL
THEN new ← rope
ELSE {
ris: IO.STREAMIO.RIS[rope];
DO
ENABLE IO.EndOfStream => EXIT;
item:  IO.ROPE;
skipped: INT;
[item, skipped] ← IO.GetTokenRope[ris];
IF item=NIL OR item.Length=0 THEN EXIT;
IF SymTab.Fetch[aliasTab, item].found
THEN item ← NARROW[SymTab.Fetch[aliasTab, item].val];
IF skipped#0 THEN new ← new.Cat[" "];
new ← new.Cat[item] ENDLOOP} };
WritePLAFile: PUBLIC PROC
[pla: PLA, fileName: IO.ROPENIL, log: IO.STREAMNIL] = {
out: IO.STREAM;
IF fileName=NIL THEN fileName←pla.name;
IF NOT fileName.Substr[fileName.Length[]-4, 4].Equal[".ttt"] THEN
fileName ← fileName.Cat[".ttt"];
out ← FS.StreamOpen[fileName, $create];
IF log=NIL THEN log ← IO.noWhereStream;
log.PutF["Writing pla on file: %g\n", IO.rope[fileName]];
log.PutRope[PLAHeader[pla]];
WritePLA[pla, out];
out.Close[]};
WritePLA: PUBLIC PROC[pla: PLA, out: IO.STREAM] = {
out.PutRope[PLAHeader[pla]];
out.PutRope[REFBit.FormatListing[pla.data]];
out.PutRope[REFBit.FormatListing[pla.out]];
out.PutRope["\nTermList:\n"];
ListTermList[
pla.termList,
FALSE,
FALSE,
out,
REFBit.Desc[pla.data].fieldForm,
REFBit.Desc[pla.out].fieldForm]};
PLAToExpression: PUBLIC PROC[pla: PLA]
RETURNS[expression: Exp] = {
outForm:  Format ← REFBit.Desc[pla.out].bitForm;
inForm:  Format ← REFBit.Desc[pla.data].bitForm;
mach:   LIST OF REF;
name:   IO.ROPEIF pla.name=NIL THEN "MachineName" ELSE pla.name;
termIndex: INT ← 0;
termTab:  RefTab.Ref ← RefTab.Create[];
TermID:  TYPE = RECORD[name: IO.ROPE, expr: Exp];
FOR term: Term ← pla.termList.end, term.last WHILE term#NIL DO
termDef: LIST OF REF;
and:  LIST OF REFNIL;
andEx: REFNIL;
termID: IO.ROPE ← MakeIndexedId["Term", termIndex, pla.termList.length];
termIndex ← termIndex+1;
FOR in: INT DECREASING IN [0..inForm.size) DO
q: Qrt;
IF (q ← GetInQrt[term, inForm[in].firstBit]) = dontcare THEN LOOP;
IF inForm[in].name#NIL
THEN IF q = one
THEN and ← CONS[inForm[in].name,           and]
ELSE and ← CONS[LIST[BoolEx.OpNm[not], inForm[in].name],  and]
ELSE IF q = zero
THEN and ← CONS[inForm[in].nameInv,          and]
ELSE and ← CONS[LIST[BoolEx.OpNm[not], inForm[in].nameInv], and]
ENDLOOP;
andEx ← IF and.rest=NIL THEN and.first ELSE CONS[BoolEx.OpNm[and], and];
[]←RefTab.Store[termTab, term, NEW[TermID ← [termID, andEx]]];
termDef ← LIST[ BoolEx.OpNm[var], termID, andEx];
mach ← CONS[termDef, mach];
ENDLOOP;
FOR outIndex: INT DECREASING IN [0..outForm.size) DO
out: LIST OF REF;
or:  LIST OF REFNIL;
orEx: REFNIL;
FOR term: Term ← pla.termList.end, term.last WHILE term#NIL DO
IF GetOutQrt[term, outForm[outIndex].firstBit]=one THEN {
termID: REF TermID ← NARROW[RefTab.Fetch[termTab, term].val];
or ← CONS[termID.name, or]};
ENDLOOP;
orEx ← IF or.rest=NIL THEN or.first ELSE CONS[BoolEx.OpNm[or], or];
out ← LIST[ BoolEx.OpNm[out], outForm[outIndex].name, orEx];
mach ← CONS[out, mach];
ENDLOOP;
mach ← CONS[BoolEx.OpNm[mach], CONS[name, mach]];
AddSharedInverters[mach];
expression ← mach};
MakeIndexedId: PROC[id: IO.ROPE, index, size: CARDINAL] RETURNS[IO.ROPE] = {
RETURN[SELECT size FROM
<10  => IO.PutFR["%g%01g", IO.rope[id], IO.card[index]],
<100  => IO.PutFR["%g%02g", IO.rope[id], IO.card[index]],
<1000  => IO.PutFR["%g%03g", IO.rope[id], IO.card[index]],
<10000 => IO.PutFR["%g%04g", IO.rope[id], IO.card[index]],
ENDCASE => ERROR]};
MakeDummyRef: PROC[id: IO.ROPE, size: INT] RETURNS[ref: REF] = {
name: IO.ROPE ← "LIST[";
FOR i: INT IN [0..size) DO name ← name.Cat[" ", MakeIndexedId[id,i,size] ] ENDLOOP;
name ← name.Cat[" ]"];
ref ← REFBit.NEWFromName[name]};
This doesn't seem to be a very useful function.
Or plane: Making each term correspond to independent outputs can't help minimize the or plane.
And plane: Making the terms correspond to inputs just seems to increase the connections in the ouput plane.
SplitPLA: PUBLIC PROC[pla: PLA] RETURNS[andPla, orPla: PLA] = {
termRef:  REF  ← MakeDummyRef["Term", pla.termList.length];
inForm:  Format ← REFBit.Desc[pla.data].bitForm;
termForm: Format ← REFBit.Desc[termRef].bitForm;
outForm:  Format ← REFBit.Desc[pla.out].bitForm;
defs:   LIST OF REF ← NIL;
defaultName: IO.ROPE  ← "MachineName";
index:   INT  ← 0;
tempAnd:  Term;
tempOr:  Term;
andPla     ← NewPLA[pla.data, termRef, pla.name.Cat["AndPlane"]];
orPla      ← NewPLA[termRef, pla.out, pla.name.Cat["OrPlane"]];
tempAnd     ← NewTerm[andPla.termList.inBits, andPla.termList.outBits];
tempOr     ← NewTerm[orPla.termList.inBits,  orPla.termList.outBits];
FOR term: Term ← pla.termList.begin, term.next WHILE term#NIL DO
SetOutQrt[one, tempAnd, termForm[index].firstBit]; tempAnd.in ← term.in;
ACopy[tempAnd, andPla.termList];
SetOutQrt[zero, tempAnd, termForm[index].firstBit];
index ← index+1 ENDLOOP;
FOR out: INT IN [0..outForm.size) DO
index ← 0;
SetOutQrt[one, tempOr, outForm[out].firstBit];
FOR term: Term ← pla.termList.begin, term.next WHILE term#NIL DO
IF GetOutQrt[term, outForm[out].firstBit]=one THEN
SetInQrt[one, tempOr, termForm[index].firstBit];
index ← index+1 ENDLOOP;
ACopy[tempOr, orPla.termList];
FOR inWd: INT IN [0..tempOr.in.wdSize) DO tempOr.in[inWd] ← initInQrtWdc ENDLOOP;
SetOutQrt[zero, tempOr, outForm[out].firstBit];
ENDLOOP;
[ ] ← ConvertTermListToCompleteSum[andPla.termList, FALSE, FALSE];
[ ] ← FindAMinimalCover[andPla.termList, 120];
[ ] ← ConvertTermListToCompleteSum[orPla.termList, FALSE, FALSE];
[ ] ← FindAMinimalCover[orPla.termList, 120]};
Array:   TYPE = REF ArrayRec;
ArrayRec:  TYPE = RECORD[
maxGates:  INT,
colNm:  SeqNm,
seq:   SEQUENCE size: CARDINAL OF Row];
Row:    TYPE = REF RowRec;
RowRec:   TYPE = RECORD
[expr: LIST OF IO.ROPE, marked: INT, smallest: INT, seq: SEQUENCE size: CARDINAL OF BOOL];
SeqNm:   TYPE = REF SeqNmRec;
SeqNmRec:  TYPE = RECORD[SEQUENCE size: CARDINAL OF IO.ROPE];
Factor: PUBLIC PROC[pla: PLA] RETURNS[mach: Exp] = {
inForm:  Format ← REFBit.Desc[pla.data].bitForm;
outForm:  Format ← REFBit.Desc[pla.out].bitForm;
andXDim:  INT  ← 2*inForm.size;
andYDim:  INT  ← pla.termList.length;
orXDim:   INT  ← pla.termList.length;
orYDim:   INT  ← outForm.size;
badRow:   INT  ← -1;
levelSum:  INT  ← 0;
defs:   LIST OF REF;
andNm:  IO.ROPE ← "Factor";
termNm:  IO.ROPE ← "Term";
orNm:   IO.ROPE ← "Sum";
machName: IO.ROPE ← IF pla.name=NIL THEN "MachineName" ELSE pla.name;
index:   INT  ← 0;
gateOp:  OpIndex ← nand; -- The last AND plane gateOp is the first OR plane gateOp.
andAry:  Array  ← NEW[ArrayRec[andYDim]];
orAry:  Array  ← NEW[ArrayRec[orYDim]];
andAry.colNm   ← NEW[SeqNmRec[andXDim]];
orAry.colNm    ← NEW[SeqNmRec[orXDim]];
FOR col: INT IN [0..andXDim) DO
input:  INTIF col < inForm.size THEN col ELSE col-inForm.size;
name:  IO.ROPE ← inForm[input].name;
nameInv: IO.ROPE ← Rope.Cat["~", name];
andAry.colNm[col] ← IF col < inForm.size THEN name ELSE nameInv ENDLOOP;
FOR col: INT IN [0..orXDim) DO
name: IO.ROPE ← MakeIndexedId[termNm, col, orXDim];
orAry.colNm[col] ← name ENDLOOP;
FOR row: INT IN [0..andYDim) DO
andAry[row]    ← NEW[RowRec[andXDim]];
andAry[row].expr  ← NIL;
andAry[row].marked ← 0 ENDLOOP;
FOR row: INT IN [0..orYDim) DO
orAry[row]    ← NEW[RowRec[orXDim]];
orAry[row].expr   ← NIL;
orAry[row].marked  ← 0 ENDLOOP;
FOR term: Term ← pla.termList.begin, term.next WHILE term#NIL DO
FOR in: INT IN [0..inForm.size)  DO
q: Qrt ← GetInQrt[term, inForm[in].firstBit];
andAry[index][in]     ← q=one;
andAry[index][in+inForm.size] ← q=zero;
ENDLOOP;
FOR out: INT IN [0..outForm.size) DO
q: Qrt ← GetOutQrt[term, outForm[out].firstBit];
orAry[out][index]     ← q=one;
ENDLOOP;
index ← index + 1 ENDLOOP;
FOR initOp: OpIndex IN [and..or] DO
ary:   Array  ← IF initOp=and THEN andAry ELSE orAry;
baseNm:  IO.ROPE ← IF initOp=and THEN andNm ELSE orNm;
maxExposed: INT ← 0;
IF initOp#and AND initOp#or THEN LOOP;
maxExposed ← 0;
FOR row: INT IN [0..ary.size) DO
cnt: INT ← 0;
FOR col: INT IN [0..ary[row].size) DO IF ary[row][col] THEN cnt ← cnt+1 ENDLOOP;
maxExposed ← MAX[cnt, maxExposed] ENDLOOP;
ary.maxGates ← 1;
WHILE maxExposed > 4
DO maxExposed ← (maxExposed-1)/4+1; ary.maxGates ← ary.maxGates*4 ENDLOOP;
FOR level: INT ← 0, level+1 DO
new:    Array;
nextColHeads: LIST OF IO.ROPE;
newCols:   INT ← 0;
gateCnt:   INT ← 0;
levelSum ← levelSum + 1;
Init row params
FOR row: INT IN [0..ary.size) DO
[]←GetRowParmsAndSetSmallest[ary, row] ENDLOOP;
DO
nameIf2OrMore: IO.ROPEIO.PutFR["%g%gx%03g",
IO.rope[baseNm], IO.int[level], IO.int[gateCnt]];
def: LIST OF IO.ROPEAddBestGate4[ary, nameIf2OrMore];
IF def = NIL THEN EXIT;
IF def.rest=NIL
THEN {
name: IO.ROPE ← InvertName[def.first];
IF RopeList.Memb[nextColHeads, name] THEN ERROR; -- check assumption
nextColHeads ← CONS[name, nextColHeads]}
ELSE {
list, term: LIST OF REF;
FOR def ← def, def.rest WHILE def#NIL DO list ← CONS[def.first, list] ENDLOOP;
list ← CONS[BoolEx.OpNm[gateOp], list];
term ← LIST[BoolEx.OpNm[var], nameIf2OrMore, list];
defs ← CONS[term, defs];
nextColHeads ← CONS[nameIf2OrMore, nextColHeads];
gateCnt ← gateCnt+1};
ENDLOOP;
IF GetMaxGates[ary] NOT IN (ary.maxGates/4..ary.maxGates] THEN ERROR;
IF (ary.maxGates = 1) THEN {
FOR row: INT IN [0..ary.size) DO
name: IO.ROPEIF initOp=and
THEN orAry.colNm[row]
ELSE outForm[row].name;
def: REF ← ary[row].expr.first;
IF ary[row].expr.rest#NIL THEN ERROR;
IF (initOp=or) AND ((levelSum MOD 2)=1) THEN
{inv: LIST OF REFLIST[BoolEx.OpNm[not], def]; def ← inv};
def ← LIST[BoolEx.OpNm[(IF initOp=and THEN var ELSE out)], name, def];
defs ← CONS[def, defs];
ENDLOOP;
EXIT};
gateOp ← IF gateOp=nand THEN nor ELSE nand; -- must be after test for loop exit
new ← NEW[ArrayRec[ary.size]];
newCols ← RopeList.Length[nextColHeads];
new.colNm ← NEW[SeqNmRec[newCols]];
new.maxGates ← ary.maxGates/4;
FOR col: INT IN [0..newCols) DO
new.colNm[col] ← nextColHeads.first;
nextColHeads ← nextColHeads.rest ENDLOOP;
FOR row: INT IN [0..ary.size) DO
new[row]    ← NEW[RowRec[newCols]];
new[row].expr  ← NIL;
new[row].marked ← 0;
FOR col: INT IN [0..newCols) DO
new[row][col] ← RopeList.Memb[ary[row].expr, new.colNm[col]] ENDLOOP;
ENDLOOP;
ary ← new;
ENDLOOP;
ENDLOOP;
defs ← CONS[BoolEx.OpNm[mach], CONS[machName, defs]];
AddSharedInverters[defs];
BoolEx.Sort[defs];
mach ← defs};
AddBestGate4: PROC[ary: Array, nameIf2OrMore: IO.ROPE]
RETURNS[gate: LIST OF IO.ROPE] = {
gateExpr:  IO.ROPENIL;
bestFanIn: INT ← 1;
fanCnts:  ARRAY [1..4] OF INTALL[0];
fanCols:  ARRAY [1..4] OF INTALL[-1];
Find fanCols and fanCnts;
FOR fanIn: INT IN [1..4] DO
maxCol: INT ← -1;
maxCnt: INT ← 0;
FOR col: INT IN [0..ary.colNm.size) DO
cnt: INT ← 0;
FOR fc: INT IN [1..fanIn) DO
IF fanCols[fc]=col THEN GOTO Loop REPEAT Loop => LOOP ENDLOOP;
FOR row: INT IN [0..ary.size) DO
IF NOT ary[row].marked=(fanIn-1) THEN LOOP;
IF ary[row][col] THEN cnt ← cnt + 1 ENDLOOP;
IF cnt > maxCnt THEN {maxCnt ← cnt; maxCol ← col} ENDLOOP;
IF maxCnt = 0 THEN IF fanIn=1 THEN RETURN[NIL] ELSE EXIT;
fanCnts[fanIn] ← maxCnt;
fanCols[fanIn] ← maxCol;
FOR row: INT IN [0..ary.size) DO
IF ary[row].marked=(fanIn-1) AND ary[row][maxCol]
THEN ary[row].marked ← ary[row].marked+1 ENDLOOP;
ENDLOOP;
Reduce fanCnts for smaller fanIns;
FOR row: INT IN [0..ary.size) DO
FOR fanIn: INT IN [1..4) DO
IF ary[row].marked < fanIn THEN LOOP;
IF fanCols[fanIn]#-1 AND ary[row].smallest > fanIn
THEN fanCnts[fanIn] ← fanCnts[fanIn]-1 ENDLOOP ENDLOOP;
Find best fanIn;
FOR fanIn: INT IN (1..4] DO
IF fanIn*fanCnts[fanIn] >= bestFanIn*fanCnts[bestFanIn] THEN bestFanIn ← fanIn;
ENDLOOP; -- use larger gates if equal
Build Gate
FOR fanIn: INT IN [1..bestFanIn] DO
gate ← CONS[ary.colNm[fanCols[fanIn]], gate] ENDLOOP;
gateExpr ← IF bestFanIn>1
THEN nameIf2OrMore
ELSE InvertName[gate.first];
Add Gate
FOR row: INT IN [0..ary.size) DO
IF bestFanIn IN [ary[row].smallest .. ary[row].marked] THEN {
ary[row].expr ← CONS[gateExpr, ary[row].expr];
FOR fanIn: INT IN [1..bestFanIn] DO ary[row][fanCols[fanIn]] ← FALSE ENDLOOP};
[]←GetRowParmsAndSetSmallest[ary, row];
ary[row].marked ← 0;
ENDLOOP};
AddSharedInverters: PROC[mach: LIST OF REF] = {
ConvertInvToList: PROC[ref: REF] RETURNS[REF] = {
WITH ref SELECT FROM
rope: IO.ROPE   => IF rope.Fetch[]='~
THENRETURN[LIST[BoolEx.OpNm[not], ConvertInvToList[rope.Substr[1]]]]
ELSERETURN[rope];
elist: LIST OF REF => {
FOR elist ← elist.rest, elist.rest WHILE elist#NIL DO
elist.first ← ConvertInvToList[elist.first] ENDLOOP;
RETURN[ref]};
ENDCASE => ERROR};
RemoveDoubleInvs: PROC[ref: REF] RETURNS[REF] = {
WITH ref SELECT FROM
rope: IO.ROPE   => RETURN[rope];
elist: LIST OF REF => {
op: OpIndex ← BoolEx.NmOp[NARROW[elist.first]];
SELECT op FROM
not  => {
elist.rest.first ← RemoveDoubleInvs[elist.rest.first];
WITH elist.rest.first SELECT FROM
rp: IO.ROPE  => RETURN[ref];
el: LIST OF REF => {
op ← BoolEx.NmOp[NARROW[el.first]];
SELECT op FROM
not  => RETURN[el.rest.first]
ENDCASE => RETURN[ref]};
ENDCASE => ERROR};
ENDCASE => {
FOR elist ← elist.rest, elist.rest WHILE elist#NIL DO
elist.first ← RemoveDoubleInvs[elist.first] ENDLOOP;
RETURN[ref]} };
ENDCASE => ERROR};
UseInvDefs: PROC[ref: REF] RETURNS[REF] = {
WITH ref SELECT FROM
rope: IO.ROPE   => RETURN[ref];
elist: LIST OF REF => {
op: OpIndex ← BoolEx.NmOp[NARROW[elist.first]];
SELECT op FROM
not  => {
elist.rest.first ← UseInvDefs[elist.rest.first];
WITH elist.rest.first SELECT FROM
rp: IO.ROPE  => {
invNm: IO.ROPEIO.PutFR["NOT%g", IO.rope[rp]];
IF SymTab.Insert[invTab, rp, invNm] THEN {
invDef: LIST OF REFLIST[BoolEx.OpNm[var], invNm, ref];
defs ← CONS[invDef, defs]};
RETURN[invNm]};
el: LIST OF REF => RETURN[ref]
ENDCASE   => ERROR};
ENDCASE => {
FOR elist ← elist.rest, elist.rest WHILE elist#NIL DO
elist.first ← UseInvDefs[elist.first] ENDLOOP;
RETURN[ref]} };
ENDCASE => ERROR};
invTab: SymTab.Ref ← SymTab.Create[];
defs: LIST OF REF ← mach.rest.rest;
FOR dfs: LIST OF REF ← defs, dfs.rest WHILE dfs#NIL DO
def: LIST OF REFNARROW[dfs.first];
def.rest.rest.first ← ConvertInvToList[def.rest.rest.first]; ENDLOOP;
FOR dfs: LIST OF REF ← defs, dfs.rest WHILE dfs#NIL DO
def: LIST OF REFNARROW[dfs.first];
def.rest.rest.first ← RemoveDoubleInvs[def.rest.rest.first]; ENDLOOP;
FOR dfs: LIST OF REF ← defs, dfs.rest WHILE dfs#NIL DO
def: LIST OF REFNARROW[dfs.first];
def.rest.rest.first ← UseInvDefs[def.rest.rest.first]; ENDLOOP;
mach.rest.rest ← defs};
InvertName: PROC[name: IO.ROPE ] RETURNS[IO.ROPE] =
{RETURN[IF name.Fetch[]='~ THEN name.Substr[1] ELSE Rope.Cat["~", name]]};
RopesToRefs: PROC[ropes: LIST OF IO.ROPE] RETURNS[refs: LIST OF REF] = {
IF ropes=NIL THEN RETURN[NIL];
RETURN[CONS[ropes.first, RopesToRefs[ropes.rest]]]};
GetMaxGates: PROC[arry: Array] RETURNS[max: INT ← 0] = {
FOR row: INT IN [0..arry.size) DO
max ← MAX[max, RopeList.Length[arry[row].expr]] ENDLOOP};
GetRowParmsAndSetSmallest: PROC[arry: Array, row: INT]
RETURNS[nofGates, exposed: INT ← 0] = {
FOR col: INT IN [0..arry[row].size) DO IF arry[row][col] THEN exposed ← exposed+1 ENDLOOP;
FOR list: LIST OF IO.ROPE ← arry[row].expr, list.rest WHILE list#NIL
DO nofGates←nofGates+1 ENDLOOP;
arry[row].smallest ← MAX[1, (exposed - (arry.maxGates-nofGates-1)*4)];
IF arry[row].smallest>4 THEN ERROR};
ShowArray: PROC[ary: Array, log: IO.STREAM] = { -- for debugging
FOR row: INT DECREASING IN [0..ary.size) DO
nofGates, exposed: INT;
[nofGates, exposed] ← GetRowParmsAndSetSmallest[ary, row];
log.PutF["%2g g:%g e:%2g s:%g m:%2g ",
IO.int[row],
IO.int[nofGates],
IO.int[exposed],
IO.int[ary[row].smallest],
IO.int[ary[row].marked]];
FOR col: INT IN [0..ary[row].size) DO
log.PutChar[IF ary[row][col] THEN '1 ELSE '.] ENDLOOP;
log.PutChar[IO.CR] ENDLOOP};
CTCompressPLA: PUBLIC PROC[pla: PLA, complete: BOOLFALSE] RETURNS[new: PLA] = {
name:  IO.ROPE ← (IF pla.name.Length[]=0 THEN "Temp" ELSE pla.name);
cmdLine: IO.ROPE;
cmdLine ← IF complete
THENIO.PutFR["PLAOpsCompress -c %g", IO.rope[name]]
ELSEIO.PutFR["PLAOpsCompress %g",  IO.rope[name]];
PLAOps.WritePLAFile[pla];
[]𡤌ommandTool.DoCommand[cmdLine, NIL];
new ← PLAOps.ReadPLAFile[name.Cat[".com.ttt"], IO.noWhereStream]};
FactorExpression: PUBLIC PROC[mach: Exp] RETURNS[newMach: Exp] = {
pla: PLA ← ExpressionToPLA[mach];
newMach ← Factor[pla]};
CompressExpression: PUBLIC PROC[mach: Exp, complete: BOOLFALSE]
RETURNS[newMach: Exp] = {
machName: IO.ROPE ← NARROW[NARROW[mach, LIST OF REF].rest.first];
pla:   PLA  ← ExpressionToPLA[mach];
IF complete
THEN pla ← CTCompressPLA[pla, TRUE]
ELSE  {
[] ← ConvertTermListToCompleteSum[pla.termList, FALSE, FALSE];
PLAOps.WritePLAFile[pla]};
newMach ← PLAToExpression[pla]};
ExpressionToPLA: PUBLIC PROC[expression: Exp] RETURNS[pla: PLA] = {
TwoTermIns: TYPE = RECORD[in0, in1: PLAOps.QWSeq];
inName:  IO.ROPE ← "LIST[ ";
outName:  IO.ROPE ← "LIST[ ";
inNames:  LIST OF IO.ROPENIL;
outNames: LIST OF IO.ROPENIL;
outForm:  Format;
inForm:  Format;
temp:   Term;
terms:   PLAOps.TermList ← NIL;
machName: IO.ROPE;
inTab:  SymTab.Ref;
outTab:  SymTab.Ref;
tranStateTab: SymTab.Ref ← SymTab.Create[];
uniqueIdx: INT ← 0;
MkInNm: SymTab.EachPairAction = {IF val=key THEN inNames ← CONS[key, inNames]};
MkOutNmAndCollectTranStates: SymTab.EachPairAction = {
outNames ← CONS[key, outNames];
val  ← CollectTranStates[key, val];
IF val#NIL THEN { -- pretend the remaining expression had a Term Def
uniqueNm: IO.ROPEIO.PutFR["uniqueName%g", IO.int[uniqueIdx]];
uniqueIdx←uniqueIdx+1;
IF ~SymTab.Insert[inTab, uniqueNm, val] THEN ERROR;
AppendSymTabRpItem[tranStateTab, uniqueNm, key]}};
CollectTranStates: PROC[out: IO.ROPE, e: Exp] RETURNS[Exp] = {
WITH e SELECT FROM
rope: IO.ROPE  =>
{AppendSymTabRpItem[tranStateTab, rope, out]; RETURN[NIL]};
elist: LIST OF REF => IF BoolEx.NmOp[NARROW[elist.first]]#or
THEN RETURN[e]
ELSE {
ls: LIST OF REF ← elist;
WHILE ls.rest#NIL DO
ls.rest.first ← CollectTranStates[out, ls.rest.first];
IF ls.rest.first=NIL
THEN ls.rest ← ls.rest.rest
ELSE ls ← ls.rest ENDLOOP;
RETURN[IF elist.rest=NIL THEN NIL ELSE elist]};
ENDCASE    => ERROR};
AppendSymTabRpItem: PROC[tab: SymTab.Ref, key, item: IO.ROPE] = {
list: LIST OF IO.ROPENARROW[SymTab.Fetch[tab, key].val];
list ← CONS[item, list];
[]←SymTab.Store[tab, key, list]};
AddTranStateOutsToPla: SymTab.EachPairAction = {
Build: PROC[e: REF] RETURNS[be: TermList] = {
WITH e SELECT FROM
in: REF INT   => {
be ← NEW[TermListRec ←
[inBits: pla.termList.inBits, outBits: pla.termList.outBits]];
SetInQrt[one, temp, inForm[in^].firstBit];
ACopy[temp, be];
SetInQrt[dontcare, temp, inForm[in^].firstBit]};
rope: IO.ROPE => RETURN[Build[SymTab.Fetch[inTab, rope].val]];
elist: LIST OF REF => {
op: OpIndex ← BoolEx.NmOp[NARROW[elist.first]];
be ← SELECT op FROM
or, nor  => OrFalse,
and, nand => AndTrue,
not   => NIL,
ENDCASE  => ERROR;
FOR elist ← elist.rest, elist.rest WHILE elist#NIL DO
arg: TermList ← Build[elist.first];
SELECT op FROM
or, nor  => be ← Or [arg, be];
and, nand => be ← And [arg, be];
not   => be ← Not [arg];
ENDCASE  => ERROR ENDLOOP;
SELECT op FROM
nor, nand  => be ← Not[be] ENDCASE};
ENDCASE => ERROR};
outs:  LIST OF IO.ROPENARROW[val];
outIdxs: LIST OF INTNIL;
FOR outIdx: INT IN [0..outForm.size) DO
IF RopeList.Memb[outs, outForm[outIdx].name]
THEN outIdxs ← CONS[outIdx, outIdxs] ENDLOOP;
FOR ls: LIST OF INT ← outIdxs, ls.rest WHILE ls#NIL DO
SetOutQrt[one, temp, outForm[ls.first].firstBit] ENDLOOP;
terms ← Build[SymTab.Fetch[inTab, key].val];
FOR term: Term ← terms.begin, term.next WHILE term#NIL DO
[temp.in, term.in] ← TwoTermIns[term.in, temp.in];
ACopy[temp, pla.termList];
[temp.in, term.in] ← TwoTermIns[term.in, temp.in] ENDLOOP;
FOR ls: LIST OF INT ← outIdxs, ls.rest WHILE ls#NIL DO
SetOutQrt[zero, temp, outForm[ls.first].firstBit] ENDLOOP};
IF expression=NIL THEN RETURN[NIL];
expression ← BoolEx.Copy[expression];
[machName, inTab, outTab] ← BoolEx.GetExpressionTables[expression];
[]←SymTab.Pairs[inTab,  MkInNm];
[]←SymTab.Pairs[outTab, MkOutNmAndCollectTranStates];
inNames ← RopeList.Sort[inNames, RopeList.IgnoreCase];
outNames ← RopeList.Sort[outNames, RopeList.IgnoreCase];
FOR inNames ← inNames, inNames.rest WHILE inNames#NIL DO
inName ← inName.Cat[inNames.first, " "]
REPEAT FINISHED => inName ← inName.Cat["]"] ENDLOOP;
FOR outNames ← outNames, outNames.rest WHILE outNames#NIL DO
outName ← outName.Cat[outNames.first, " "]
REPEAT FINISHED => outName ← outName.Cat["]"] ENDLOOP;
pla  ← NewPLA[inName, outName, machName];
outForm ← REFBit.Desc[pla.out].bitForm;
inForm ← REFBit.Desc[pla.data].bitForm;
temp  ← NewTerm[pla.termList.inBits, pla.termList.outBits];
FOR index: INT IN [0..temp.in.wdSize) DO temp.in[index] ← initInQrtWdc ENDLOOP;
FOR in: INT IN [0..inForm.size) DO
IF SymTab.Store[inTab, inForm[in].name, NEW[INT ← in]] THEN ERROR ENDLOOP;
[]←SymTab.Pairs[tranStateTab, AddTranStateOutsToPla]};
verbose: BOOLFALSE;
PLAHeader: PUBLIC PROC [pla: PLA] RETURNS[header: IO.ROPE] = {
out: IO.STREAMIO.ROS[];
out.PutRope["\n"];
IF pla.name#NIL THEN-- notice this is just for next line
out.PutF["Name: %g\n", IO.rope[pla.name]];
out.PutF["Date: %g\n", IO.time[pla.time]];
out.PutF["InType: %g\n", IO.rope[REFBit.Desc[pla.data].typeName]];
out.PutF["OutType: %g\n", IO.rope[REFBit.Desc[pla.out].typeName]];
out.PutF["Terms: %g\n", IO.card[pla.termList.length]];
header ← IO.RopeFromROS[out]};
StripDirFromName: PROC[ file: IO.ROPE] RETURNS[IO.ROPE] = {
index: INT𡤀
WHILE index>=0 DO
index ← file.Find[s2: ">"];
file ← file.Substr[start: index+1] ENDLOOP;
RETURN[file]};
DefaultCMDLine: PUBLIC PROC[ cmdLine, default: IO.ROPE] RETURNS[IO.ROPE] = {
DO
ENABLE IO.EndOfStream => EXIT;
default ← IO.GetTokenRope[IO.RIS[cmdLine]].token; EXIT; ENDLOOP;
RETURN[default]};
initialWorkingDirectory: IO.ROPE ← FileNames.CurrentWorkingDirectory[];
EqualExpr:   PUBLIC PROC[e0, e1: Exp] RETURNS[equal: BOOL] = {
pla0: PLA ← ExpressionToPLA[e0];
pla1: PLA ← ExpressionToPLA[e1];
nm0: IO.ROPEIF e0=NIL THEN NIL ELSE NARROW[NARROW[e0, LIST OF REF].rest.first];
nm1: IO.ROPEIF e1=NIL THEN NIL ELSE NARROW[NARROW[e1, LIST OF REF].rest.first];
IF e0=e1 THEN RETURN[TRUE];
IF e0=NIL OR e1=NIL THEN RETURN[FALSE];
IF NOT Rope.Equal[nm0, nm1] THEN RETURN[FALSE];
RETURN[EqualPLA[pla0, pla1]]};
EqualPLA:   PUBLIC PROC[pla0, pla1: PLA]  RETURNS[equal: BOOL] = {
inForm:  Format;
outForm:  Format;
IF pla0=pla1 THEN RETURN[TRUE];
IF pla0=NIL OR pla1=NIL THEN RETURN[FALSE];
inForm ← REFBit.Desc[pla0.data].bitForm;
outForm ← REFBit.Desc[pla0.out].bitForm;
pla1      ← ReconfigurePLA[pla1, pla0.data, pla0.out];
IF pla1=NIL THEN RETURN[FALSE];
FOR out: INT IN [0..outForm.size) DO
t0, t1: Term;
be0: BoolExpr ← GetOutputBE[pla0, outForm[out].firstBit];
be1: BoolExpr ← GetOutputBE[pla1, outForm[out].firstBit];
[] ← ConvertTermListToCompleteSum[be0, TRUE, TRUE];
[] ← ConvertTermListToCompleteSum[be1, TRUE, TRUE];
IF be0.length # be1.length THEN RETURN[TRUE];
t0 ← be0.begin;
t1 ← be1.begin;
FOR term: INT IN [0..be0.length)
DO IF NOT EqualTerm[t0, t1] THEN RETURN[FALSE]; t0 ← t0.next; t1 ← t1.next
ENDLOOP ENDLOOP;
RETURN[TRUE]};
EqualTerm:   PUBLIC PROC[term0, term1: Term] RETURNS[equal: BOOL] = {
IF term0=term1 THEN RETURN[TRUE];
IF term0=NIL OR term1=NIL THEN RETURN[FALSE];
IF term0.in.wdSize # term1.in.wdSize THEN RETURN[FALSE];
IF term0.out.wdSize # term1.out.wdSize THEN RETURN[FALSE];
FOR in: INT IN [0..term0.in.wdSize) DO
IF term0.in[in]#term1.in[in] THEN RETURN[FALSE] ENDLOOP;
FOR out: INT IN [0..term0.out.wdSize) DO
IF term0.out[out]#term1.out[out] THEN RETURN[FALSE] ENDLOOP;
RETURN[TRUE]};
END.