DIRECTORY CardTab, CD, CDCommandOps, CDProperties, CDSequencer, CDSequencerExtras, IO, List, PriorityQueue, Rope, RefTab,  SoftHdwAssembly, SoftHdwBasics, SoftHdwDelayPath, SoftHdwSimulate, SoftHdwCompiler, TerminalIO;


SoftHdwDelayPathImpl: CEDAR PROGRAM
IMPORTS CardTab, CDCommandOps, CDProperties,  CDSequencerExtras, IO, PriorityQueue, RefTab, SoftHdwAssembly, SoftHdwBasics, SoftHdwSimulate, TerminalIO

EXPORTS SoftHdwDelayPath
= BEGIN OPEN SoftHdwDelayPath, SoftHdwBasics, SoftHdwAssembly;

tempArrayPos: ArrayPosition _ NEW[ArrayPositionRec];

designToDelayNetworkKey: REF INT _ NEW[INT];
designToCurrentPathKey: REF INT _ NEW[INT];

CreateNetworkForSimulation: PUBLIC PROC [simulation: SoftHdwSimulate.Simulation] RETURNS [network: DelayNetwork] ~ {
network _ CreateNetwork[simulation.base];
CDProperties.PutDesignProp[simulation.design, designToDelayNetworkKey, network];
};

CreateNetwork: PUBLIC PROC [array: SoftHdwBasics.ArrayBase] RETURNS [network: DelayNetwork] ~ {
network _ NEW[DelayNetworkRec];
network.levelTable _ CardTab.Create[];
network.worstDelayTable _ PriorityQueue.Create[SortByDelay];
network.eventTable _ RefTab.Create[equal: ArrayPositionEqual, hash: ArrayPositionHash];
BuildCausalityGraph[array, network];
};

ResetNetwork: PUBLIC PROC [network: DelayNetwork] ~ {
network.worstDelayTable _ PriorityQueue.Create[SortByDelay]; };

BuildCausalityGraph: PROC [array: SoftHdwBasics.ArrayBase, network: DelayNetwork]  ~ {
BuildDelayTerms: RefTab.EachPairAction ~ {
pos: ArrayPosition _ NARROW[key];
SELECT pos.type FROM
Output => { BuildDelayTermsForGrain[pos, NARROW[val], array, network]; };
Long => {BuildDelayTermsForLongLine[pos, NARROW[val], array, network]; };
RAMEven => {BuildDelayTermsForRAM[pos, NARROW[val], array, network]; };
ENDCASE => ERROR;
};

table:  RefTab.Ref _ array.state.positionToEntity;
[] _ table.Pairs[BuildDelayTerms];
};

NameForType: PROC [type: NodeType] RETURNS [name: Rope.ROPE] ~ {
RETURN[nodeNames[type]];
};


EventFromPos: PROC [key: ArrayPosition, type: NodeType, network: DelayNetwork] RETURNS [event: DelayEvent] ~ {
val: RefTab.Val;
found: BOOL;
tempArrayPos^ _ key^;
tempArrayPos.type _ type;
[found, val] _ RefTab.Fetch[network.eventTable, tempArrayPos];
IF found THEN 
{ event _ NARROW[val];
RETURN[event]; }
ELSE 
{ newpos: ArrayPosition _ NEW[ArrayPositionRec _ tempArrayPos^];
event _ NEW[DelayEventRec _ [position: newpos]];
[] _ RefTab.Store[network.eventTable, newpos, event];
network.allDelayEvents _ CONS[event,network.allDelayEvents]; }; };



BuildDelayTermsForLongLine: PROC [pos: ArrayPosition, longLine: LongLine, array: ArrayBase, network: DelayNetwork] ~{
lineEvent: DelayEvent _ EventFromPos[pos, Long, network];
otherEvent: DelayEvent;
FOR index: CARDINAL IN [0..longLine.size) DO
longGrain: Grain _ longLine.grains[index];
IF longGrain.inputSelect=l THEN {
IF longGrain.flipFlop 
THEN { otherEvent _ EventFromPos[longGrain.key,  Master, network]; }
ELSE { otherEvent _ EventFromPos[longGrain.key,  Input, network]; };
CreateDelayTerm[lineEvent, otherEvent, LToI]; };

IF longGrain.ORUToL THEN {
otherEvent _ EventFromPos[longGrain.key, Output, network]; 
CreateDelayTerm[otherEvent,  lineEvent, ORUToL];  };
ENDLOOP; 
};

BuildDelayTermsForRAM: PROC [pos: ArrayPosition, RAMArray: MinorArray, array: ArrayBase, network: DelayNetwork] ~{
sourceEvent, destEvent: DelayEvent;
IF RAMArray.RAMEven OR RAMArray.RAMOdd THEN {
FOR grainIndex: INT IN [0..array.sizes.grain.x) DO
tempArrayPos^ _ pos^;
tempArrayPos.orientation _ Vertical;
tempArrayPos.grain.y _ 0;
tempArrayPos.grain.x _ grainIndex;
destEvent _ EventFromPos[tempArrayPos, LeftDown, network];
FOR adrIndex: INT IN [0..array.sizes.grain.y) DO
tempArrayPos^ _ pos^;
tempArrayPos.grain.x _ 0;
tempArrayPos.grain.y _ adrIndex;
tempArrayPos.orientation _ Horizontal;
sourceEvent _ EventFromPos[tempArrayPos, RightUp, network];
CreateDelayTerm[sourceEvent, destEvent, InputEnabled];
ENDLOOP;
ENDLOOP;
};
};


BuildDelayTermsForGrain: PROC [pos: ArrayPosition, grain: Grain, array: ArrayBase, network: DelayNetwork] ~{
BuildDelayTermForLeftDown[pos, grain, network];
BuildDelayTermForRightUp[pos, grain, network];
BuildDelayTermForInput[pos, grain, network];
BuildDelayTermForOutput[pos, grain, network];
};

Huh: SIGNAL = CODE;
BuildDelayTermForLeftDown: PROC [pos: ArrayPosition, grain: Grain, network: DelayNetwork] ~{
destEvent: DelayEvent;
sourceEvent: DelayEvent;
IF grain.rightUpGrain#NIL THEN 
{ otherGrain: Grain _ grain.rightUpGrain;
destEvent _ EventFromPos[pos, LeftDown, network];
IF otherGrain.LDToLD THEN
{ sourceEvent _ EventFromPos[otherGrain.key, LeftDown, network];
CreateDelayTerm[sourceEvent, destEvent, LDToLD]; };
IF otherGrain.ORUToLD THEN
{ sourceEvent _ EventFromPos[otherGrain.key, Output, network];
CreateDelayTerm[sourceEvent, destEvent, ORUToLD]; };
}; };

BuildDelayTermForRightUp: PROC [pos: ArrayPosition, grain: Grain, network: DelayNetwork] ~{
destEvent: DelayEvent;
sourceEvent: DelayEvent;
IF grain.leftDownGrain#NIL THEN 
{ otherGrain: Grain _ grain.leftDownGrain;
destEvent _ EventFromPos[pos, RightUp, network];
IF grain.RUToRU THEN
{ sourceEvent _ EventFromPos[otherGrain.key, RightUp, network];
CreateDelayTerm[sourceEvent, destEvent, RUToRU]; };
IF grain.OLDToRU THEN 
{ sourceEvent _ EventFromPos[otherGrain.key, Output, network];
CreateDelayTerm[sourceEvent, destEvent, OLDToRU]; };
}; };

BuildDelayTermForInput: PROC [pos: ArrayPosition, grain: Grain, network: DelayNetwork] ~{
destEvent: DelayEvent _ EventFromPos[pos, Input, network];
sourceEvent: DelayEvent;
 SELECT grain.inputSelect FROM 
none => {};
oru => {
sourceEvent _ EventFromPos[pos, Output, network];
CreateDelayTerm[sourceEvent, destEvent, ORUToI]; };
old => { IF grain.leftDownGrain#NIL THEN 
{ sourceEvent _ EventFromPos[grain.leftDownGrain.key, Output, network];
CreateDelayTerm[sourceEvent, destEvent, OLDToI]; }; };
ld => {
 sourceEvent _ EventFromPos[pos, LeftDown, network];
CreateDelayTerm[sourceEvent, destEvent, LDToI]; };
l => {};
ru =>  { IF grain.leftDownGrain#NIL THEN 
{ sourceEvent _ EventFromPos[grain.leftDownGrain.key, RightUp, network];
CreateDelayTerm[sourceEvent, destEvent, RUToI]; }; };
ENDCASE => ERROR;
};

BuildDelayTermForOutput: PROC [pos: ArrayPosition, grain: Grain, network: DelayNetwork] ~{
destEvent: DelayEvent _ EventFromPos[pos, Output, network];
sourceEvent: DelayEvent;
IF grain.flipFlop THEN {
destEvent _ EventFromPos[pos, Master, network];
};
IF grain.parallelInput THEN {
sourceEvent _ EventFromPos[pos, Input, network];
CreateDelayTerm[sourceEvent, destEvent, ParallelInput];
};
FOR grainIndex: INT IN [0..grain.size) DO
IF grain.perpendicularGrains[grainIndex].inputEnabled AND grain.perpendicularGrains[grainIndex].grain#NIL THEN { 
sourceEvent _ EventFromPos[grain.perpendicularGrains[grainIndex].grain.key, Input, network];
CreateDelayTerm[sourceEvent, destEvent, InputEnabled];
};
ENDLOOP;
};

CreateDelayTerm: PROC [source: DelayEvent, dest: DelayEvent, type: NodeType] ~ {
term: DelayTerm _ NEW[DelayTermRec _ [inputDelayEvent: source, outputDelayEvent: dest]];
term.delay _ DelayForTerm[type];
term.position _ NEW[ArrayPositionRec _ dest.position^];
SELECT type FROM  
InputEnabled => {
SELECT dest.position.orientation FROM
Vertical => {
term.position.grain.y _ source.position.grain.y; };
Horizontal =>  {
term.position.grain.x _ source.position.grain.x; };
ENDCASE => ERROR;   };
ORUToLD, LDToLD => term.position^ _ source.position^; 
RUToI, ParallelInput,
LDToI, OLDToI, ORUToI, OLDToRU, RUToRU, LToI => NULL;
ORUToL =>  term.position.minorArray _ source.position.minorArray;
ENDCASE => ERROR;  
term.position.type _ type;
source.outputDelayTerms _ CONS[term, source.outputDelayTerms];
dest.inputDelayTerms _ CONS[term, dest.inputDelayTerms]; };

DelayForTerm:  PROC [type: NodeType]  RETURNS [INT] ~{
RETURN [SELECT type FROM
ParallelInput, InputEnabled, RUToI, LDToI, OLDToI, ORUToI, OLDToRU, RUToRU, ORUToLD, LDToLD => 1,
ENDCASE => 1 ]; 
};
MarkPrimaryInputs: PROC [network: DelayNetwork] ~ {
FOR events: DelayEvents _ network.allDelayEvents, events.rest 
WHILE events#NIL DO {
event: DelayEvent _ events.first;
IF event.inputDelayTerms=NIL THEN event.primaryInput _ TRUE; };
ENDLOOP; 
};


LevelizeDelayNetwork:  PUBLIC PROC [network: DelayNetwork] ~ {
FOR events: DelayEvents _ network.allDelayEvents, events.rest 
WHILE events#NIL DO
[] _ LevelizeEvent[events.first];
ENDLOOP;
BuildLevelTable[network];
};

LevelizeEvent: PROC [event: DelayEvent] RETURNS [level: INT] ~ {
DelayTermLevel: PROC [term: DelayTerm] RETURNS [level: INT] ~ {
RETURN[LevelizeEvent[term.inputDelayEvent]];
 };
IF event.level#(-1)  OR event.levelComputed THEN RETURN [event.level] ELSE 
{ maxlevel: INT _ -1; 
event.levelComputed _ TRUE;
FOR terms: DelayTerms _ event.inputDelayTerms, terms.rest 
WHILE terms#NIL DO 
term: DelayTerm _ terms.first;
level: INT _ DelayTermLevel[term];
maxlevel _ MAX[maxlevel,level];
ENDLOOP;
event.levelComputed _ TRUE;
IF (maxlevel > -1) 
THEN {
event.level _ maxlevel+1; 
RETURN[event.level]; 
}
ELSE { 
IF event.primaryInput 
THEN { event.level _ 0; RETURN[0]; }
ELSE { event.level _ -1; RETURN[-1]; };
};
};  
};


SortByDelay: PriorityQueue.SortPred ~ {
d1: DelayEvent _ NARROW[x];
d2: DelayEvent _ NARROW[y];
RETURN[d1.maxDelay > d2.maxDelay]; };

BuildLevelTable: PROC [network: DelayNetwork] ~ {
table: CardTab.Ref _ CardTab.Create[];
maxlevel: INT _ 0;
network.levelTable _ table;
FOR events: DelayEvents _ network.allDelayEvents, events.rest 
WHILE events#NIL DO
event: DelayEvent _ events.first;
level: INT _ event.level;
prevlist: DelayEvents _ NARROW[CardTab.Fetch[table,LOOPHOLE[level]].val];
newlist: DelayEvents _ CONS[event, prevlist];
maxlevel _ MAX[maxlevel,level];
[] _ CardTab.Store[table, LOOPHOLE[level], newlist];
ENDLOOP;
network.maxLevel _ maxlevel;
};


ComputeDelays: PUBLIC PROC [network: DelayNetwork] ~ {
FOR level: INT IN [0..network.maxLevel] DO
eventslist: DelayEvents _ NARROW[CardTab.Fetch[network.levelTable, LOOPHOLE[level]].val];
FOR events: DelayEvents _ eventslist, events.rest 
WHILE events#NIL DO
event: DelayEvent _ events.first;
ComputeEventDelay[event];
RecordMaxDelay[network, event];
ENDLOOP;
ENDLOOP;
};

RecordMaxDelay: PROC [network: DelayNetwork, event:  DelayEvent] ~ {
IF event.outputDelayTerms=NIL THEN {
PriorityQueue.Insert[network.worstDelayTable, event]; };
IF (network.maxDelayEvent = NIL) OR (event.maxDelay > network.maxDelayEvent.maxDelay)  THEN network.maxDelayEvent _ event
};


ComputeEventDelay: PROC [event: DelayEvent] ~ {
maxdelay: INT _ 0;
mindelay: INT _ LAST[INT];
zeroslack: DelayTerm;
FOR terms: DelayTerms _ event.inputDelayTerms, terms.rest 
WHILE terms#NIL DO 
term: DelayTerm _ terms.first;
delay: INT _ DelayTermDelay[term];
IF NOT term.blocked THEN {
IF delay > maxdelay THEN zeroslack _ term;
maxdelay _ MAX[maxdelay, delay];
mindelay _ MIN[mindelay, delay]; 
};
ENDLOOP;
event.minDelay _ mindelay;
event.maxDelay _ maxdelay;
event.zeroSlackTerm _ zeroslack;
};


DelayTermDelay: PROC [term: DelayTerm] RETURNS [delay: INT] ~ {
inputEvent: DelayEvent _ term.inputDelayEvent;
RETURN[term.delay + inputEvent.maxDelay]; };
ReportCriticalPath: PUBLIC PROC [network: DelayNetwork, eventPrintFn: EventPrintFn, termPrintFn:  TermPrintFn] ~ {
worstEvent: DelayEvent _ NARROW[PriorityQueue.Remove[network.worstDelayTable]];
TracePath[worstEvent, eventPrintFn, termPrintFn]; };

TracePath: PUBLIC PROC [event: DelayEvent, eventPrintFn: EventPrintFn, termPrintFn:  TermPrintFn] ~ {
nextevent: DelayEvent;
TerminalIO.PutF["\n--Delay Path  min %d, max %d:", IO.int[event.minDelay], IO.int[event.maxDelay]];
FOR term: DelayTerm _ event.zeroSlackTerm, nextevent.zeroSlackTerm
 WHILE term#NIL DO
eventPrintFn[term.outputDelayEvent];
nextevent _ term.inputDelayEvent;
ENDLOOP;
eventPrintFn[nextevent];
};

SummarizePath: PUBLIC PROC  [event: DelayEvent, eventPrintFn: EventPrintFn] ~ {
nextevent: DelayEvent;
TerminalIO.PutF["\n--Delay Path  min %d, max %d:", IO.int[event.minDelay], IO.int[event.maxDelay]];
TerminalIO.PutF["Output (Final) Event:  "];
PrintEvent[event];
TerminalIO.PutF["Start Event:  "];
FOR term: DelayTerm _ event.zeroSlackTerm, nextevent.zeroSlackTerm
 WHILE term#NIL DO
nextevent _ term.inputDelayEvent;
ENDLOOP;
eventPrintFn[nextevent];
};


MakeDelayPositionPath: PUBLIC PROC [event: DelayEvent] RETURNS [ArrayPositions] ~ {
nextevent: DelayEvent _ event;
pathlist: ArrayPositions _ NIL;
FOR term: DelayTerm _ event.zeroSlackTerm, nextevent.zeroSlackTerm
 WHILE term#NIL DO {
outEvent: DelayEvent _ term.outputDelayEvent;
pathlist _ CONS[outEvent.position, pathlist];
pathlist _ CONS[term.position, pathlist];
nextevent _ term.inputDelayEvent; };
ENDLOOP;
pathlist _ CONS[nextevent.position, pathlist];
RETURN[pathlist];
};

MakeColoredDelayPositionPath: PUBLIC PROC [event: DelayEvent] RETURNS [ColoredArrayPositions] ~ {
pathlist: ArrayPositions _ MakeDelayPositionPath[event];
cpathlist: ColoredArrayPositions _ NIL;
FOR poslist: ArrayPositions _ pathlist, poslist.rest WHILE poslist#NIL DO
cpathlist _ CONS[[color: red, position: poslist.first], cpathlist];
ENDLOOP;
RETURN[cpathlist];
};


PrintEvent: PUBLIC PROC [event: DelayEvent] ~ {
zeroslackdelay: INT _ 0;
IF event#NIL THEN {
IF event.zeroSlackTerm#NIL THEN zeroslackdelay _ event.zeroSlackTerm.delay;
TerminalIO.PutF["\nEvent: %g delay %g (%g)", IO.rope[ArrayPositionToRope[event.position]], IO.int[event.maxDelay],IO.int[zeroslackdelay]];
};
};

PrintTerm: PUBLIC PROC [term: DelayTerm] ~ {
TerminalIO.PutF["\n Term: %g delay %g", IO.rope[ArrayPositionToRope[term.position]], IO.int[term.delay]];
};

PrintGenericEvent: PUBLIC PROC [event: DelayEvent] ~ {
zeroslackdelay: INT _ 0;
IF event#NIL THEN {
IF event.zeroSlackTerm#NIL THEN zeroslackdelay _ event.zeroSlackTerm.delay;
TerminalIO.PutF["\nEvent: delay %g (%g)", IO.int[event.maxDelay],IO.int[zeroslackdelay]]; };
};

PrintGenericTerm: PUBLIC PROC [term: DelayTerm] ~ {
TerminalIO.PutF["\n Term:  delay %g", IO.int[term.delay]];
};


TimingAnalyze: PUBLIC PROC [simulation: SoftHdwSimulate.Simulation] RETURNS [network: DelayNetwork] ~ {
TerminalIO.PutF["\nCreating Timing Analysis Network..."];
network _ CreateNetworkForSimulation[simulation];
MarkPrimaryInputs[network];
LevelizeDelayNetwork[network];
TerminalIO.PutF["\nDoing Timing Analysis."];
ComputeDelays[network];
TerminalIO.PutF["\nLongest Critical Path:"];
ReportCriticalPath[network, PrintEvent, PrintTerm];
};

SoftHdwTimingAnalyze: PROC [command: CDSequencer.Command] = {
simulation: SoftHdwSimulate.Simulation _ NARROW[CDProperties.GetDesignProp[command.design, SoftHdwSimulate.designToSimulationKey]];
IF simulation#NIL THEN {
network: DelayNetwork _ NARROW[CDProperties.GetDesignProp[command.design, designToDelayNetworkKey]];
IF network=NIL THEN {
TerminalIO.PutF["\nCreating new Network for this design..."] ;
network _ CreateNetworkForSimulation[simulation];
MarkPrimaryInputs[network];
LevelizeDelayNetwork[network]; };
network.worstDelayTable _ PriorityQueue.Create[SortByDelay];
ComputeDelays[network]; 
TerminalIO.PutF["\nTiming Analysis Done."]; } 
ELSE TerminalIO.PutF["\nNo simulation found for this design!"];
};


PrintCriticalPath: PROC [command: CDSequencer.Command] = {
simulation: SoftHdwSimulate.Simulation _ NARROW[CDProperties.GetDesignProp[command.design, SoftHdwSimulate.designToSimulationKey]];
IF simulation#NIL THEN {
currentPath: DelayEvent _ NARROW[CDProperties.GetDesignProp[command.design, designToCurrentPathKey]];
IF currentPath#NIL THEN {
TerminalIO.PutF["\nCurrent Path:"];
TracePath[currentPath, PrintEvent, PrintTerm];
} 
ELSE TerminalIO.PutF["\nThere is no current critical path for this design."];
}
ELSE TerminalIO.PutF["\nNo simulation found for this design!"];
};


HighlightCriticalPath: PROC [command: CDSequencer.Command]~ {
simulation: SoftHdwSimulate.Simulation _ NARROW[CDProperties.GetDesignProp[command.design, SoftHdwSimulate.designToSimulationKey]];
IF simulation=NIL THEN TerminalIO.PutF["\nNo simulation found for this design!"] 
ELSE  {
network: DelayNetwork _ NARROW[CDProperties.GetDesignProp[command.design, designToDelayNetworkKey]];
IF network=NIL THEN TerminalIO.PutF["\nNo network for this design!"] 
ELSE {
worstEvent: DelayEvent _ NARROW[PriorityQueue.Remove[network.worstDelayTable]];
CDProperties.PutDesignProp[simulation.design, designToCurrentPathKey, worstEvent];
IF worstEvent.level = 0 THEN TerminalIO.PutF["\nThis delay path ends at level 0; You have probably finished looking at all the interesting paths."]
ELSE  {
posList: ColoredArrayPositions _ MakeColoredDelayPositionPath[worstEvent]; 
SummarizePath[worstEvent, PrintEvent];
SoftHdwAssembly.HighlightDesign[command.design, simulation.sizes, NIL];
SoftHdwAssembly.HighlightDesign[command.design, simulation.sizes, posList, NIL,  "Critical Path"];
};
};
};
};

BlockPath: PROC [command: CDSequencer.Command] = {
FindEvent: PROC [key: ArrayPosition, network: DelayNetwork] RETURNS [event: DelayEvent, found: BOOL] ~ {
val: RefTab.Val;
[found, val] _ RefTab.Fetch[network.eventTable, key];
IF found THEN 
{ event _ NARROW[val];
RETURN[event, TRUE]; }
ELSE RETURN [NIL,FALSE]; 
};
BlockPathForEvent: PROC [event: DelayEvent] ~ {
term: DelayTerm;
IF event.outputDelayTerms#NIL THEN  {
FOR terms: DelayTerms _ event.outputDelayTerms, terms.rest
 WHILE terms#NIL DO 
term _ terms.first;
term.blocked _ NOT term.blocked; 
ENDLOOP; 
IF term.blocked THEN TerminalIO.PutF["\nDelay Terms From %g Blocked.", IO.rope[ArrayPositionToRope[event.position]]]  
ELSE TerminalIO.PutF["\nDelay Terms From %g Unblocked.", IO.rope[ArrayPositionToRope[event.position]]]; };
};

simulation: SoftHdwSimulate.Simulation _ NARROW[CDProperties.GetDesignProp[command.design, SoftHdwSimulate.designToSimulationKey]];
ambiguous: BOOL;
position: SoftHdwBasics.ArrayPosition;
IF simulation=NIL THEN TerminalIO.PutF["\nNo simulation found for this design!"] 
ELSE {
network: DelayNetwork _ NARROW[CDProperties.GetDesignProp[command.design, designToDelayNetworkKey]];
IF network=NIL THEN TerminalIO.PutF["\nNo network for this design!"] 
ELSE {
[ambiguous, position] _ SoftHdwAssembly.CDToArrayPosition[simulation.sizes, simulation.program.coordinates, command.sPos];
IF ambiguous THEN TerminalIO.PutRope["\nAmbiguous position"]
ELSE {
event: DelayEvent;
found: BOOL;
[event,found] _  FindEvent[position, network];
IF NOT found THEN TerminalIO.PutF["\nNo Event found at that position!"]
ELSE BlockPathForEvent[event];
};
};
};
};

 InitCDCommands: PROC  ~ {
CDCommandOps.RegisterWithMenu[$SpecialMenu, "Timing Analyze", "Timing Analyze this design.", $SoftHdwTimingAnalyze, SoftHdwTimingAnalyze];
CDCommandOps.RegisterWithMenu[$SpecialMenu, "Show Critical Path", "Highlights a critical path in the current design", $SoftHdwHighlightCriticalPath, HighlightCriticalPath];
CDCommandOps.RegisterWithMenu[$SpecialMenu, "Print Last Path", "Prints the current critical path in the current design", $SoftHdwPrintCriticalPath, PrintCriticalPath];
CDSequencerExtras.RegisterCommand[key: $RosemaryPlotSelectedWires, proc: BlockPath, queue: doQueue];
};
TimingAnalyzeFlatCell: PUBLIC PROC [flatCell: SoftHdwCompiler.FlatCell] RETURNS [network: DelayNetwork] ~ {
TerminalIO.PutF["\nCreating Timing Analysis Network..."];
network _ CreateNetworkFromFlatCell[flatCell];
MarkPrimaryInputs[network];
LevelizeDelayNetwork[network];
TerminalIO.PutF["\nDoing Timing Analysis."];
ComputeDelays[network];
TerminalIO.PutF["\nLongest Critical Path:"];
ReportCriticalPath[network, PrintGenericEvent,  PrintGenericTerm];
};


CreateNetworkFromFlatCell: PUBLIC PROC [flatCell: SoftHdwCompiler.FlatCell] RETURNS [network: DelayNetwork] ~ {
EventFromPrim: PROC [prim: SoftHdwCompiler.Primitive] RETURNS [event: DelayEvent] ~ {
IF prim=NIL THEN {
event _ NEW[DelayEventRec];
network.allDelayEvents _ CONS[event,network.allDelayEvents];
}
 ELSE {
val: RefTab.Val;
found: BOOL;
[found, val] _ RefTab.Fetch[network.eventTable, prim];
IF found THEN {
event _ NARROW[val];
RETURN[event];
}
ELSE {
event _ NEW[DelayEventRec];
[] _ RefTab.Store[network.eventTable, prim, event];
network.allDelayEvents _ CONS[event,network.allDelayEvents];
};
}; 
};
BuildDelayEvents: RefTab.EachPairAction ~ {
prim: SoftHdwCompiler.Primitive _ NARROW[val];
outputEvent: DelayEvent _ NIL;
IF prim.flatClock=NIL THEN outputEvent _ EventFromPrim[prim]
ELSE {
outputEvent _ NEW[DelayEventRec];
network.allDelayEvents _ CONS[outputEvent, network.allDelayEvents];
};
FOR input: INT IN [0..prim.size) DO
inputEvent: DelayEvent _ EventFromPrim[prim[input].source];
CreateDelayTerm[inputEvent, outputEvent, 1];
ENDLOOP; 
};
CreateDelayTerm: PROC [source, dest: DelayEvent, delay: INT] ~ {
term: DelayTerm _ NEW[DelayTermRec _ [inputDelayEvent: source, outputDelayEvent: dest]];
term.delay _ delay;
source.outputDelayTerms _ CONS[term, source.outputDelayTerms];
dest.inputDelayTerms _ CONS[term, dest.inputDelayTerms]; 
};
network _ NEW[DelayNetworkRec];
network.levelTable _ CardTab.Create[];
network.worstDelayTable _ PriorityQueue.Create[SortByDelay];
network.eventTable _ RefTab.Create[];
[] _ RefTab.Pairs[flatCell.wires, BuildDelayEvents];
};


InitCDCommands[];

END.
n
SoftHdwDelayPathImpl.mesa
Copyright Σ 1988 by Xerox Corporation.  All rights reserved.
Minsky, August 18, 1989 5:09:04 pm PDT

Barth, September 6, 1989 2:52:27 pm PDT
... Parses an element of the positionToEntity table into DelayTerm links between events.
... Look up an event of the given type for a grain at a given position. 
Creates a new event if none exists. 
 ...Create DelayTerms to drive all READ Data  events (LeftDown Vertical) from all READ ADRRESS lines (RightUp Horizontal) . 
Loop over every ReadData output event, and create DelayTerms from all ReadAdr input events. 
TerminalIO.PutF["RAM Tile at %g\n", IO.rope[ArrayPositionToRope[pos]]];
TerminalIO.PutF["RamEven %g, RAMOdd %g \n", IO.bool[RAMArray.RAMEven], IO.bool[RAMArray.RAMOdd]];
 ...For each element of a grain {Output,Input,RightUp,LeftDown} these procedures create a new DelayEvent if needed, and create DelayTerms from any other DelayEvents which drive the element. 
Create DelayTerm for LeftDown line
Create DelayTerm for RightUp line
Long Lines are handled by BuildDelayTermsForLongLine
Mung the arrayposition grain pos coordinates to accurately pinpoint the device
For a long line dest, we need to mung the minor array pos to be nonzero

... Marks all DelayEvents which have no inputDelayTerms as primary inputs.
When the causality graph has been constructed, the delay events are ordered by 'level'. The level of a delay event is one greater than the maximum level of all the events that can cause it to occur. Primary Inputs are level zero. Events which have no primary inputs as predecessors have level -1. 

When the level for a delay event is requested, it is recursively computed if it has not already been determined. Delay events at the same level are linked together in a list. A table, indexed by level, to the head of each list is created.

If  an event still has a level of -1, after its predecessors have been levelized, and it is not  a primary input, then it returns a level of -1. If it is a primary input, it returns a level of 0. 
-- Previous event levels have all been computed, and max is > -1, so return max+1
Create a table, indexed by level, of lists of delayevents.
Record the maximum level encountered.
Delay events are visited from the lowest level (closest to the primary input) to the highest level, computing delay by maximizing the contributions from each equation term.
Each equation term's contribution is the term's delay plus the delay of the input event to the term. 

 ... records terminal events into a priority queue, sorted by delay. 
Find the minimum and maximum delay term contributions.
Printing and Tracing Critical Paths
Hack to find a critical path and print it.
...Prints out a delay path by traing an event back, following the zero slack pointers, until an event with no input terms is reached. 
termPrintFn[term];
...Just print out the total path delays.
... Traces an event back through the zero slack terms, creating a list of  the array positions
of the events. This path is useful for highlighting the critical path. 
... Traces an event back through the zero slack terms, creating a list of colored array positions
of the events. This path is useful for highlighting the critical path. 
TerminalIO.PutF["Event: %g delay %g (%g) \n", IO.rope[ArrayPositionToRope[event.position]], IO.int[event.maxDelay],IO.int[zeroslackdelay]];
TerminalIO.PutF[" Term: %g delay %g\n", IO.rope[ArrayPositionToRope[term.position]], IO.int[term.delay]];
... If a network already exists, just recompute the delays, else create a new one.
For user interface, create a new PriorityQueue each time recompute the network delays.
Save the current path for later.
... Find the Event which the user clicked on,  and toggle the blocked flag of all the terms which it sources.
...Toggle all outputDelayTerms blocked flag.
TerminalIO.PutF["clicked at %g\n", IO.rope[ArrayPositionToRope[position]]];
Create DelayNetwork from a FlatCell
Look up a DelayEvent for the given primitive.   
Creates a new event if none exists. 
For Primary Inputs, we will be passed NIL instead of a primitive. Just return a new anonymous event.
Parses Primitives into DelayEvents and DelayTerms
Install CD Menu commands
ΚT™
codeš
œ™K™<K™'K™'—KšΟk	œ
œ>œ…
˜Ϊ
K˜K˜šΟnœœ
˜#Kšœ
˜—
K˜Kšœ˜Kšœœ
œœ
˜>K˜Kšœœ˜4K˜Kš	œœ
œœ
œ˜,Kš	œœ
œœ
œ˜+K˜šžœœ
œ*œ˜tKš
œ)˜)Kš
œP˜PK˜K˜—šž
œœ
œ"œ˜_Kšœ
œ˜Kš
œ&˜&Kš
œ<˜<Kš
œW˜WKš
œ$˜$—K˜K˜šžœœ
œ˜5Kš
œ?˜?—K˜šžœœ=˜Všžœ˜*Kš
œX™XKšœœ˜!šœ
˜Kšœ)œ˜IKšœ)œ˜IKšœ'œ˜GKšœœ
˜—Kš
œ˜—K˜Kš
œ2˜2Kš
œ"˜"K˜K˜—šžœœœ
œ˜@Kšœ˜K˜K˜—K˜šžœœ=œ˜nK™HK™$K˜Kšœ˜Kš
œ˜Kš
œ˜Kš
œ>˜>šœœ
˜šœ
œ˜Kšœ
˜—š
˜šœœ#˜@šœœ%˜0Kš
œ5˜5Kšœœ%˜BK˜—————K˜K˜šžœœU˜uKš
œ9˜9Kš
œ˜šœœ
œ˜,Kš
œ*˜*šœœ˜!šœ˜Kšœ@˜DKšœ=˜D—Kš
œ0˜0K˜—šœ˜Kš
œ;˜;Kš
œ4˜4——Kšœ˜	K˜K˜—šžœœW˜rKš
œ|™|Kš
œ#˜#K™\Kšœ$œ 
™GKšœ,œœ™ašœœœ˜-šœ
œ
œ˜2K˜K˜$K˜Kš
œ"˜"Kš
œ:˜:šœœ
œ˜0K˜Kš
œ˜Kš
œ ˜ K˜&Kš
œ;˜;Kš
œ6˜6Kšœ
˜—Kšœ
˜——K˜—˜K˜K˜—šžœœO˜lKš
œΎ
™Ύ
Kš
œ/˜/Kš
œ.˜.Kš
œ,˜,Kš
œ-˜-K˜K˜—Kšžœœœ
˜šžœœ=˜\Kš
œ˜Kš
œ˜Kšœœ
œ
˜š
œ"™"š
œ)˜)Kš
œ1˜1šœ˜š
œ@˜@Kš
œ3˜3——šœ˜š
œ>˜>Kš
œ4˜4———˜K˜———šžœœ=˜[Kš
œ˜Kš
œ˜Kšœœ
œ
˜ š
œ!™!š
œ*˜*Kš
œ0˜0šœ˜š
œ?˜?Kš
œ3˜3——šœ˜š
œ>˜>Kš
œ4˜4———K˜K˜——šžœœ=˜YKš
œ:˜:Kš
œ˜šœœ
˜Kš
œ˜š
œ˜Kš
œ1˜1Kš
œ3˜3—šœ	œœ
œ
˜)š
œG˜GKš
œ6˜6——š
œ˜Kš
œ4˜4Kš
œ2˜2—Jšœž™4Kš
œ˜šœ	œœ
œ
˜)š
œH˜HKš
œ5˜5——Kšœœ
˜—K˜—K˜šžœœ=˜ZKš
œ;˜;Kš
œ˜šœœ˜Kš
œ/˜/Kš
œ˜—šœœ˜Kš
œ0˜0Kš
œ7˜7Kš
œ˜—šœ
œ
œ˜)šœ4œ-œ˜qKš
œ\˜\Kš
œ6˜6Kš
œ˜—Kšœ
˜—Kš
œ˜K˜—šžœœ;˜PKšœœC˜XKš
œ ˜ Kšœœ$˜7K™Nšœœ˜š
œ˜šœ˜%˜
Kš
œ3˜3—š
œ˜Kš
œ3˜3—Kšœœ˜——Kš
œ6˜6Kš
œ˜Kšœ0œ
˜5K™GKš
œA˜AKšœœ˜—Kš
œ˜Kšœœ ˜>Kšœœ ˜;K˜—šžœœœœ˜6šœ˜Kšœbœ	˜rK˜——K™šžœœ˜3K™Jšœ;˜>šœ˜Kš
œ!˜!Kšœ	œ
œ˜?—Kšœ˜	—˜K˜——K˜K™™—™šžœœ
œ˜>šœ;˜>Kšœ˜Kš
œ!˜!—Kšœ
˜K˜—K˜K˜K™Δ
šž
œœœ	œ˜@šžœœœ	œ˜?Kšœ&˜,Kš
œ˜—Kš
œœœ
œœ
˜Kšœœ˜Kšœœ
˜šœ7˜:šœœ
œ
˜Kš
œ˜Kšœœ˜"Kšœœ˜—Kšœ
˜—Kšœœ
˜šœ
˜Kšœ˜™QKšœ
˜Kšœ˜Kš
œ
˜
—šœ˜šœ˜Kšœœ˜$Kšœœ˜'——K˜——K˜—˜K˜—K˜šžœ˜'Kšœœ˜Kšœœ˜Kšœ˜%K˜—K™:K™%šžœœ˜1K˜&Kšœ
œ˜Kš
œ˜šœ;˜>šœœ
˜K˜!Kšœœ˜Kšœœœ˜IKšœœ˜-Kšœœ˜Kšœœ˜4—Kšœ
˜Kš
œ˜—˜K˜K˜——K™¬
™eK™—šž
œœ
œ˜6šœœ
œ˜*Kšœœ#œ˜Yšœ/˜2šœœ
˜K˜!K˜K˜——Kšœ
˜—Kšœ
˜K˜K˜—šžœœ0˜DK™Ešœœ
œ˜$Kš
œ8˜8—šœœœ4œ˜yK˜K˜——K˜K™6šžœœ˜/Kšœ
œ˜Kšœ
œœ
œ˜Kš
œ˜šœ7˜:šœœ
œ
˜Kš
œ˜Kšœœ˜"šœ
œœ˜Kšœœ˜*Kšœœ˜ Kšœœ˜!Kš
œ˜——Kšœ
˜—Kš
œ˜Kš
œ˜Kš
œ ˜ K˜—K˜K˜šžœœœ	œ˜?Kš
œ.˜.Kšœ&˜,—Ihead1™#K™*šžœœS˜rKšœœ0˜OKš
œ4˜4K˜—šž	œœO˜eK™†
Kš
œ˜Kšœ3œœ˜cšœ?˜BKšœ
œ˜Kš
œ$˜$Kš
œ™Kš
œ!˜!—Kšœ
˜Kš
œ˜K˜K˜—šž
œœ
œ5˜OK™(Kš
œ˜Kšœ3œœ˜cKš
œ+˜+Kš
œ˜Kš
œ"˜"šœ?˜BKšœ
œ˜Kš
œ!˜!—Kšœ
˜Kš
œ˜K˜K˜K˜—šžœœ
œœ˜SK™^K™GKš
œ˜Kšœœ
˜šœ?˜BKšœ
œ˜Kš
œ-˜-Kšœœ˜-Kšœœ˜)Kš
œ$˜$Kšœ
˜—Kšœœ˜.Kšœ˜K˜K˜—šžœœ
œœ˜aK™aK™GKš
œ8˜8Kšœ#˜'šœ2œ	˜IKšœœ3˜CKšœ
˜—Kšœ˜K˜K˜—K˜šž
œœ
œ˜/Kšœœ˜šœœ
œ˜Kšœœ
œ,˜Kšœ-œ,œœ˜Š
K˜——K˜K˜—šž	œœ
œ˜,Kšœ(œ+œ˜iK˜K˜—šžœœ
œ˜6Kšœœ˜šœœ
œ˜Kšœœ
œ,˜KKšœ.œ,œœ™‹
Kšœ)œœ˜\—K˜K˜—šžœœ
œ˜3Kšœ(œ+œ™iKšœ&œ˜:K˜K˜—K˜šž
œœ*œ˜gKš
œ9˜9Kš
œ1˜1K˜Kš
œ˜Kš
œ,˜,Kš
œ˜Kš
œ,˜,Kš
œ3˜3K˜K˜—Kšžœœ#˜=™RKšœ)œT˜ƒ
šœ
˜KšœœF˜dšœœ
œ˜Kš
œ>˜>Kš
œ1˜1K˜Kš
œ!˜!—Kš
œV™VKš
œ<˜<Kš
œ˜Kš
œ.˜.Kšœ;˜?—K˜—K˜K˜šžœœ#˜:Kšœ)œT˜ƒ
šœ
˜KšœœE˜ešœ

˜Kš
œ#˜#Kš
œ.˜.Kš
œ˜KšœH˜M—K˜
—Kšœ;˜?K˜—K˜K˜šžœ
œ"˜=Kšœ)œT˜ƒ
šœœ
œ:
˜Qšœ˜KšœœF˜dšœœ
œ2˜Ešœ˜Kšœœ0˜OK™ Kš
œR˜Ršœœv˜“
šœ˜Kš
œK˜KKš
œ&˜&KšœBœ˜GKšœKœ˜bK˜—K˜—K˜————Kš
œ˜—K˜Kšž	œœ#˜2™mšž	œœ-œœ˜hK˜Kš
œ5˜5šœœ
˜šœ
œ˜Kšœœ˜—Kšœ
œœ
œ˜—K˜—šžœœ˜/K™,Kš
œ˜šœœ
œ˜%šœ7˜:Kšœ
œ˜Kš
œ˜Kšœœ˜!Kšœ˜	—Kšœœ3œ-˜vKšœ5œ/˜j—K˜K˜—Kšœ)œT˜ƒ
Kšœœ
˜Kš
œ&˜&šœœ
œ:
˜Qšœ˜KšœœF˜dšœœ
œ2˜Ešœ˜Kš
œz˜zšœœ+˜<šœ˜Kš
œ˜Kšœœ
˜Kšœ#œ&™KKš
œ.˜.šœ
œœ6˜GKšœ˜—K˜——K˜——K˜——K˜K˜—šœ
žœœ˜Kš
œŠ
˜Š
Kš
œ¬
˜¬
Kš
Ϥ
˜§
Kš
œd˜dK˜—L™#šžœœ&œ˜kKš
œ9˜9Kš
œ.˜.K˜Kš
œ˜Kš
œ,˜,Kš
œ˜Kš
œ,˜,Kš
œB˜BK˜K˜—K˜šžœœ
œ&œ˜ošž
œœ#œ˜UK™0K™$K™dšœœ
œ˜Kšœœ˜Kšœœ˜<Kš
œ
˜
—šœ
œ˜K˜Kšœ˜Kš
œ6˜6šœœ˜Kšœœ˜Kšœ˜Kš
œ
˜
—šœ
˜Kšœœ˜Kš
œ3˜3Kšœœ˜<Kš
œ˜—Kš
œ˜—Kš
œ˜—šžœ˜+Kš
œ1™1Kšœ"œ˜.Kšœœ
˜Kšœœ
œ"˜<šœ˜Kšœœ˜!Kšœœ&˜CKš
œ˜—šœœ
œ˜#Kš
œ;˜;Kš
œ,˜,Kšœ˜	—Kš
œ˜—šžœœ#œ˜@KšœœC˜XKš
œ˜Kšœœ ˜>Kšœœ˜9Kš
œ˜—Kšœ
œ˜Kš
œ&˜&Kš
œ<˜<Kš
œ%˜%Kš
œ4˜4K˜K˜K˜—L™K˜K˜—Kšœ
˜—…—Rlx.