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 ~ {
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: 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]; };
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[];