SoftHdwDelayPathImpl.mesa
Copyright Ó 1988 by Xerox Corporation. All rights reserved.
Minsky, August 18, 1989 5:09:04 pm PDT
Barth, September 8, 1989 2:19:13 pm PDT
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 INTNEW[INT];
designToCurrentPathKey: REF INTNEW[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 ~ {
Parses an element of the positionToEntity table into DelayTerm links between events.
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;
};
[] ← RefTab.Pairs[array.state.positionToEntity, BuildDelayTerms];
};
NameForType: PROC [type: NodeType] RETURNS [name: Rope.ROPE] ~ {
RETURN[nodeNames[type]];
};
EventFromPos: PROC [key: ArrayPosition, type: NodeType, network: DelayNetwork] RETURNS [event: DelayEvent] ~ {
... Look up an event of the given type for a grain at a given position.
Creates a new event if none exists.
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 ← SoftHdwBasics.CopyArrayPosition[tempArrayPos];
event ← NEW[DelayEventRec ← [source: newpos]];
[] ← RefTab.Store[network.eventTable, newpos, event];
network.allDelayEvents ← CONS[event, network.allDelayEvents];
};
};
BuildDelayTermsForLongLine: PROC [pos: ArrayPosition, longLine: LongLine, array: ArrayBase, network: DelayNetwork] ~ {
otherEvent: DelayEvent;
FOR index: CARDINAL IN [0..longLine.size) DO
longGrain: Grain ← longLine.grains[index];
IF longGrain.inputSelect=l THEN {
lineEvent: DelayEvent ← EventFromPos[pos, Long, network];
otherEvent ← EventFromPos[longGrain.key, Input, network];
CreateDelayTerm[lineEvent, otherEvent, LToI];
};
IF longGrain.ORUToL THEN {
lineEvent: DelayEvent ← EventFromPos[pos, Long, network];
otherEvent ← EventFromPos[longGrain.key, Output, network];
CreateDelayTerm[otherEvent, lineEvent, ORUToL];
};
ENDLOOP;
};
BuildDelayTermsForRAM: PROC [pos: ArrayPosition, RAMArray: MinorArray, array: ArrayBase, network: DelayNetwork] ~{
...Create DelayTerms to drive all READ Data events (LeftDown Vertical) from all READ ADRRESS lines (RightUp Horizontal) .
sourceEvent, destEvent: DelayEvent;
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]];
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] ~{
...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.
BuildDelayTermForLeftDown[pos, grain, network];
BuildDelayTermForRightUp[pos, grain, network];
BuildDelayTermForInput[pos, grain, network];
BuildDelayTermForOutput[pos, grain, network];
};
BuildDelayTermForLeftDown: PROC [pos: ArrayPosition, grain: Grain, network: DelayNetwork] ~{
IF grain.rightUpGrain#NIL THEN { -- Create DelayTerm for LeftDown line
otherGrain: Grain ← grain.rightUpGrain;
IF otherGrain.LDToLD THEN {
destEvent: DelayEvent ← EventFromPos[pos, LeftDown, network];
sourceEvent: DelayEvent ← EventFromPos[otherGrain.key, LeftDown, network];
CreateDelayTerm[sourceEvent, destEvent, LDToLD];
};
IF otherGrain.ORUToLD THEN {
destEvent: DelayEvent ← EventFromPos[pos, LeftDown, network];
sourceEvent: DelayEvent ← EventFromPos[otherGrain.key, Output, network];
CreateDelayTerm[sourceEvent, destEvent, ORUToLD];
};
};
};
BuildDelayTermForRightUp: PROC [pos: ArrayPosition, grain: Grain, network: DelayNetwork] ~{
IF grain.leftDownGrain#NIL THEN { -- Create DelayTerm for RightUp line
otherGrain: Grain ← grain.leftDownGrain;
IF grain.RUToRU THEN {
destEvent: DelayEvent ← EventFromPos[pos, RightUp, network];
sourceEvent: DelayEvent ← EventFromPos[otherGrain.key, RightUp, network];
CreateDelayTerm[sourceEvent, destEvent, RUToRU];
};
IF grain.OLDToRU THEN {
destEvent: DelayEvent ← EventFromPos[pos, RightUp, network];
sourceEvent: DelayEvent ← EventFromPos[otherGrain.key, Output, network];
CreateDelayTerm[sourceEvent, destEvent, OLDToRU];
};
};
};
BuildDelayTermForInput: PROC [pos: ArrayPosition, grain: Grain, network: DelayNetwork] ~{
SELECT grain.inputSelect FROM
none => NULL;
oru => {
destEvent: DelayEvent ← EventFromPos[pos, Input, network];
sourceEvent: DelayEvent ← EventFromPos[pos, Output, network];
CreateDelayTerm[sourceEvent, destEvent, ORUToI];
};
old => IF grain.leftDownGrain#NIL THEN {
destEvent: DelayEvent ← EventFromPos[pos, Input, network];
sourceEvent: DelayEvent ← EventFromPos[grain.leftDownGrain.key, Output, network];
CreateDelayTerm[sourceEvent, destEvent, OLDToI];
};
ld => {
destEvent: DelayEvent ← EventFromPos[pos, Input, network];
sourceEvent: DelayEvent ← EventFromPos[pos, LeftDown, network];
CreateDelayTerm[sourceEvent, destEvent, LDToI];
};
l => NULL; -- Long Lines are handled by BuildDelayTermsForLongLine
ru => IF grain.leftDownGrain#NIL THEN {
destEvent: DelayEvent ← EventFromPos[pos, Input, network];
sourceEvent: DelayEvent ← EventFromPos[grain.leftDownGrain.key, RightUp, network];
CreateDelayTerm[sourceEvent, destEvent, RUToI];
};
ENDCASE => ERROR;
};
BuildDelayTermForOutput: PROC [pos: ArrayPosition, grain: Grain, network: DelayNetwork] ~{
IF grain.parallelInput THEN {
destEvent: DelayEvent ← EventFromPos[pos, IF grain.flipFlop THEN Master ELSE Output, network];
sourceEvent: DelayEvent ← 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 {
destEvent: DelayEvent ← EventFromPos[pos, IF grain.flipFlop THEN Master ELSE Output, network];
sourceEvent: DelayEvent ← 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]];
termPosition: ArrayPositionRec ← NARROW[dest.source, ArrayPosition]^;
sourcePosition: ArrayPosition ← NARROW[source.source];
term.delay ← DelayForTerm[type];
Mung the arrayposition grain pos coordinates to accurately pinpoint the device
SELECT type FROM
InputEnabled => {
SELECT NARROW[dest.source, ArrayPosition].orientation FROM
Vertical => {
termPosition.grain.y ← sourcePosition.grain.y; };
Horizontal => {
termPosition.grain.x ← sourcePosition.grain.x; };
ENDCASE => ERROR; };
ORUToLD, LDToLD => termPosition ← sourcePosition^;
RUToI, ParallelInput,
LDToI, OLDToI, ORUToI, OLDToRU, RUToRU, LToI => NULL;
For a long line dest, we need to mung the minor array pos to be nonzero
ORUToL => termPosition.minorArray ← sourcePosition.minorArray;
ENDCASE => ERROR;
termPosition.type ← type;
term.source ← SoftHdwBasics.CopyArrayPositionRec[termPosition];
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] ~ {
... Marks all DelayEvents which have no inputDelayTerms as primary inputs.
FOR events: DelayEvents ← network.allDelayEvents, events.rest
WHILE events#NIL DO {
event: DelayEvent ← events.first;
IF event.inputDelayTerms=NIL THEN event.primaryInput ← TRUE; };
ENDLOOP;
};
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.
LevelizeDelayNetwork: PUBLIC PROC [network: DelayNetwork] ~ {
FOR events: DelayEvents ← network.allDelayEvents, events.rest WHILE events#NIL DO
[] ← LevelizeEvent[events.first];
ENDLOOP;
BuildLevelTable[network];
};
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.
LevelizeEvent: PROC [event: DelayEvent] RETURNS [level: INT] ~ {
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 ← LevelizeEvent[term.inputDelayEvent];
maxlevel ← MAX[maxlevel, level];
ENDLOOP;
event.levelComputed ← TRUE;
level ← event.level ← IF (maxlevel>-1) THEN maxlevel+1 ELSE (IF event.primaryInput THEN 0 ELSE -1);
};
};
SortByDelay: PriorityQueue.SortPred ~ {
d1: DelayEvent ← NARROW[x];
d2: DelayEvent ← NARROW[y];
RETURN[d1.maxDelay > d2.maxDelay]; };
Create a table, indexed by level, of lists of delayevents.
Record the maximum level encountered.
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;
};
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.
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;
};
ComputeSlack: PUBLIC PROC [network: DelayNetwork] ~ {
FOR level: INT DECREASING IN [0..network.maxLevel] DO
eventslist: DelayEvents ← NARROW[CardTab.Fetch[network.levelTable, LOOPHOLE[level]].val];
FOR events: DelayEvents ← eventslist, events.rest UNTIL events=NIL DO
event: DelayEvent ← events.first;
slack: INT ← 0;
FOR terms: DelayTerms ← event.outputDelayTerms, terms.rest UNTIL terms=NIL DO
term: DelayTerm ← terms.first;
slack ← MAX[slack, term.outputDelayEvent.maxDelay-term.delay-event.maxDelay];
ENDLOOP;
event.slack ← slack;
ENDLOOP;
ENDLOOP;
};
RecordMaxDelay: PROC [network: DelayNetwork, event: DelayEvent] ~ {
records terminal events into a priority queue, sorted by delay.
IF event.outputDelayTerms=NIL THEN {
PriorityQueue.Insert[network.worstDelayTable, event];
};
IF (network.maxDelayEvent = NIL) OR (event.maxDelay > network.maxDelayEvent.maxDelay) THEN network.maxDelayEvent ← event;
};
Find the minimum and maximum delay term contributions.
ComputeEventDelay: PROC [event: DelayEvent] ~ {
maxdelay: INT ← 0;
mindelay: INTLAST[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]; };
Printing and Tracing Critical Paths
Hack to find a critical path and print it.
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] ~ {
...Prints out a delay path by traing an event back, following the zero slack pointers, until an event with no input terms is reached.
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];
termPrintFn[term];
nextevent ← term.inputDelayEvent;
ENDLOOP;
eventPrintFn[nextevent];
};
SummarizePath: PUBLIC PROC [event: DelayEvent, eventPrintFn: EventPrintFn] ~ {
...Just print out the total path delays.
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] ~ {
... 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.
nextevent: DelayEvent ← event;
pathlist: ArrayPositions ← NIL;
FOR term: DelayTerm ← event.zeroSlackTerm, nextevent.zeroSlackTerm
WHILE term#NIL DO {
outEvent: DelayEvent ← term.outputDelayEvent;
pathlist ← CONS[NARROW[outEvent.source], pathlist];
pathlist ← CONS[NARROW[term.source], pathlist];
nextevent ← term.inputDelayEvent; };
ENDLOOP;
pathlist ← CONS[NARROW[nextevent.source], pathlist];
RETURN[pathlist];
};
MakeColoredDelayPositionPath: PUBLIC PROC [event: DelayEvent] RETURNS [ColoredArrayPositions] ~ {
... 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.
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[NARROW[event.source]]], IO.int[event.maxDelay],IO.int[zeroslackdelay]];
};
};
PrintTerm: PUBLIC PROC [term: DelayTerm] ~ {
TerminalIO.PutF["\n Term: %g delay %g", IO.rope[ArrayPositionToRope[NARROW[term.source]]], 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["Event: %g delay %g (%g) \n", IO.rope[ArrayPositionToRope[event.position]], IO.int[event.maxDelay],IO.int[zeroslackdelay]];
TerminalIO.PutF["\nEvent: delay %g (%g)", IO.int[event.maxDelay],IO.int[zeroslackdelay]]; };
};
PrintGenericTerm: PUBLIC PROC [term: DelayTerm] ~ {
TerminalIO.PutF[" Term: %g delay %g\n", IO.rope[ArrayPositionToRope[term.position]], IO.int[term.delay]];
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] = {
... If a network already exists, just recompute the delays, else create a new one.
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]; };
For user interface, create a new PriorityQueue each time recompute the network delays.
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]];
Save the current path for later.
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] = {
... Find the Event which the user clicked on, and toggle the blocked flag of all the terms which it sources.
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] ~ {
...Toggle all outputDelayTerms blocked flag.
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[NARROW[event.source]]]]
ELSE TerminalIO.PutF["\nDelay Terms From %g Unblocked.", IO.rope[ArrayPositionToRope[NARROW[event.source]]]]; };
};
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;
TerminalIO.PutF["clicked at %g\n", IO.rope[ArrayPositionToRope[position]]];
[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];
};
Create DelayNetwork from a FlatCell
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] ~ {
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.
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 ~ {
CreateDelayTerm: PROC [source, dest: DelayEvent, delay: INT] ~ {
term: DelayTerm ← NEW[DelayTermRec ← [inputDelayEvent: source, outputDelayEvent: dest, source: prim]];
term.delay ← delay;
source.outputDelayTerms ← CONS[term, source.outputDelayTerms];
dest.inputDelayTerms ← CONS[term, dest.inputDelayTerms];
};
Parses Primitives into DelayEvents and DelayTerms
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];
};
IF outputEvent.source#NIL THEN ERROR;
outputEvent.source ← prim;
FOR input: INT IN [0..prim.size) DO
inputEvent: DelayEvent ← EventFromPrim[prim[input].source];
CreateDelayTerm[inputEvent, outputEvent, 1];
ENDLOOP;
};
network ← NEW[DelayNetworkRec];
network.levelTable ← CardTab.Create[];
network.worstDelayTable ← PriorityQueue.Create[SortByDelay];
network.eventTable ← RefTab.Create[];
[] ← RefTab.Pairs[flatCell.wires, BuildDelayEvents];
};
Install CD Menu commands
InitCDCommands[];
END.