DIRECTORY Core, CoreClasses, IO, Sisyph, SymTab;FSM: CEDAR DEFINITIONS = BEGINFSMData:			TYPE = REF FSMDataRec;FSMDataRec:		TYPE = RECORD [name:				IO.ROPE				_ NIL,states:				States					_ NIL,initialState:		State					_ NIL,outInAll:			BOOL					_ TRUE, -- TRUE => all outputs avail as inputsoutIns:			LIST OF IO.ROPE		_ NIL, -- If ~outInAll then list of outs avail as inputsregister:			RegisterType			_ edgeTriggered,mach:				Expression			_ NIL,	-- privateassert:				Expression			_ NIL,	-- any guaranteed conditionspublics:			LIST OF IO.ROPE		_ NIL,	-- privatesrcCellType:		Core.CellType		_ NIL ];	-- privateStates:		TYPE = LIST OF State;State:		TYPE = REF StateRec;StateRec:	TYPE = RECORD [name:			IO.ROPE				_ NIL,outputs:		LIST OF IO.ROPE		_ NIL,	-- Moore state and outs, Mealy stateoutputsInv:	LIST OF IO.ROPE		_ NIL, 	-- explicit control of state encodingsoutTrans:		Transitions			_ NIL,inTrans:		Transitions			_ NIL,	-- privatesrcCellInst:	CellInstance			_ NIL ];	-- privateTransitions:	TYPE = LIST OF Transition;Transition:	TYPE = REF TransitionRec;TransitionRec:	TYPE = RECORD [enable:		Expression			_ NIL,outputs:		LIST OF IO.ROPE		_ NIL, 	-- Mealy outstarget:			State					_ NIL,srcCellInst:	CellInstance			_ NIL ];	-- privateExpression:		TYPE = REF;CellInstance:		TYPE = CoreClasses.CellInstance;RegisterType:	TYPE = {edgeTriggered, twoPhase, none};Context:		TYPE = REF ContextRec;ContextRec:	TYPE = RECORD[fsm:			FSMData,logic:			LIST OF CurrentLogic,data:			LIST OF CurrentData,state:			IO.ROPE,declares:		LIST OF Declaration,	-- Used during	declarationssignals:		Signals,					-- Used after all declarationsinvTab:		SymTab.Ref,stateTab:		SymTab.Ref ];CurrentLogic:	TYPE = LIST OF FieldValMask	_ NIL;CurrentData:		TYPE = LIST OF FieldValMask	_ NIL;FieldValMask:	TYPE = RECORD[f,v,m: NAT	_ default];Signals:			TYPE = REF SignalSeqRec;SignalSeqRec:	TYPE = RECORD [SEQUENCE size: NAT OF Declaration];Declaration:		TYPE = RECORD [name: IO.ROPE, io: InOut, size: NAT, index: NAT];InOut:			TYPE = {in, out, outIn};	-- outIn = clocked state variables, prev val inputdefault:			NAT = LAST[NAT];CodeMachine: PROC [fsm: FSMData, exprImplKey: ATOM _ $SC] RETURNS [ct: Core.CellType];SchStateCell:			PROC RETURNS [ct: Core.CellType];	-- Target SourceSchTransitionCell:	PROC RETURNS [ct: Core.CellType];	-- Source TargetSchMachine: PROC [cx:				Sisyph.Context,name:			IO.ROPE		_ NIL,register:		RegisterType	_ edgeTriggered,exprImplKey:	ATOM			_ $SC				]RETURNS [ct: Core.CellType];Create:	PROC[name: IO.ROPE] RETURNS[ctx: Context];Declare:	PROC[ctx: Context, name: IO.ROPE, io: InOut, size: NAT _ 1] RETURNS[ix: NAT];IfState:		PROC[ctx: Context, s: IO.ROPE];If:				PROC[ctx: Context, f, v: NAT, m: NAT _ default];And:			PROC[ctx: Context, f, v: NAT, m: NAT _ default];AddOut:		PROC[ctx: Context, f, v: NAT, m: NAT _ default];JmpState:	PROC[ctx: Context, s: IO.ROPE];Finish:		PROC[ctx: Context] RETURNS[mach: FSMData];EncodeStates:	PROC[fsm: FSMData];											-- multiple calls okConvertToExp:	PROC[fsm: FSMData] RETURNS[machine: LIST OF REF];	-- calls EncodeStatesImplementExprFile: PROC[file: IO.ROPE, register: RegisterType, exprImplKey: ATOM]RETURNS[Core.CellType];ImplementExpr: PROC[mach: Expression, register: RegisterType, exprImplKey: ATOM]RETURNS[Core.CellType];BuildSCMachine:	PROC[mach: Expression] RETURNS [Core.CellType];BuildSCGates:		PROC[mach: Expression] RETURNS [Core.CellType];BuildSCRegister:	PROC[mach: Expression] RETURNS [Core.CellType];END.     FSM.mesaCopyright ╙ 1986, 1987 by Xerox Corporation.  All rights reserved.Barth, July 17, 1987 5:42:41 pm PDTLast Edited by: Don Curry January 13, 1988 9:27:39 am PSTTheoryThis interface defines some routines for creating finite state machines and their corresponding cellTypes from either code or schematics.  The cellTypes can be created with or without a register for the outputs.  When a cellType without a register is created, all outputs have the prefix 'Nxt' to distinguish the signal names from inputs which where outputs from the previous cycle.  The cellTypes have a high level Rosemary eval proc and will recast into a variety of cell types depending on the parameter exprImplKey.  See FSMImpl.mesa for the latest catalogue of implementation choices for exprImplKey.Public Types - (for direct contruction of FSMData)Private Types - (used during indirect contruction of FSMData)Creation of FSM CellTypes from FSMData or Schematicsfsm.publics, fsm.mach and all inTrans fields are initialized to NIL.Sch cell name: ".fsm" is concatenated to name if supplied or the current object name if not.Sisyph is invoked to extract the schematic state machine.A state labelled Init must exist.Every state has an implicit transition to Init when Reset is asserted.The names used in the public of the cellType will be:"Vdd", "Gnd", "Reset",all input names,all output names (including automatically assigned xtra state bit names),SELECT registerType FROMedgeTriggered	=>	"Clock"twoPhase 	 	=>	"PhA", "PhB"ENDCASE 		=>	'Nxt' prepended to all outputs which are also inputs,Generating FSMDataThe following procs are useful for writing FSM Generators.You create a context:	ctx _ Create[]Declare names:			id: NAT _ ctx.Declare[name, in/out/outIn, size]Specify the transition:	ctx.IfState["state1"];	ctx.AddOut[id, val];	ctx.JmpState["state2"]; ... or maybe state outs:	ctx.IfState[NIL];		ctx.AddOut[id, val];	ctx.SetState["state"]; ...And finish:				fsm _ ctx.Finish[]IfState, and If push the context down one level.JmpState pops the context up one level.Only IfState can be used at the top level.Only If can be used at lower levels.And is used to extend a condition started by IfState or If.Transition Definition Construct: (outputs associated with transistions)IfState[state1], And[...], AddOut[...], JmpState[state2] provides a means of defining outputs for a transition between states.  Logical conditions applied to the context using And  are ANDed with state1 to enable the transition to state2. State Definition Construct: (outputs associated with states)IfState[NIL], AddOut[...], JmpState[state] provides an means of defining the outputs for a state (rather than a transition). Any logical conditions applied to the context using And between the IfState and JmpState trigger an ERROR in JmpState. Branch-contexts can be explored using the If call.Contexts and branch-contexts are terminated by JmpStateJmpState[NIL] can be used to just pop the context.The state "Init" must be declared.The input "Reset" is always implicit and causes a transition from anywhere to "Init".Outputs of "Init" may be defined using the State Definition ConstructOutputs which also appear as inputs (after one clock delay) can be declared as outIn (rather than just out).  Making more outputs available as inputs tends to decrease the number of xtra bits the FSM contructor needs to add in order to disambiguate states.  It also tends to decrease the term sizes.Example: Dragon SmallCache SCPmCodeFSMImpl.mesaComplete state assignments and convert to an ExpressionBuild Standard CellsЭ╩5  Ц"cedar" styleШ Ц"Cedar" styleЪ╧kЬЩJЪЬBЩBJЪЬ ЭЩ#JЪЬ9Щ9ЧJШ JЪЭ	ЬЭЬШ0JШ JЪЭЬЭЬЭЬЭШheadЩJЪЬ▌Щ▌ЧЩ2JЪЬЭЬЭЬШ!ЪЬЭЬЭЬШJЪЬ	ЭЬЭЬЭЬШJЪЬЭЬШJЪЬЭЬШJЪЬЭЬЭЬ╧c&ШCJЪЬ
ЭЬЭЬЭЬЭЬЭЬЮ1ШSJЪЬ+Ш+JЪЬЭЬЮ
Ш'JЪЬЭЬЮШ;JЪЬЭЬЭЬЭЬЭЬЭЬЮ
Ш-JЪЬЭЬЮ
Ш0ЧJЪЬ	ЭЬЭЬЭЬШJЪЬЭЬЭЬ
ШЪЬ
ЭЬЭЬШJЪЬЭЬЭЬЭЬШJЪЬ
ЭЬЭЬЭЬЭЬЭЬЮ$ШFJЪЬЭЬЭЬЭЬЭЬЭЬЮ&ШKJЪЬЭЬШJЪЬЭЬЮ
Ш)JЪЬЭЬЮ
Ш/ЧJЪЬЭЬЭЬЭЬШ'JЪЬЭЬЭЬШ%ЪЬЭЬЭЬШJЪЬЭЬШJЪЬ
ЭЬЭЬЭЬЭЬЭЬЮШ0JЪЬЭЬШJЪЬЭЬЮ
Ш/ЧJЪЬЭЬЭЬШJЪЬЭЬШ/JЪЬЭЬ#Ш5ЧЩ=JЪЬ
ЭЬЭЬШ ЪЬЭЬЭЬШJЪЬШJЪЬ	ЭЬЭЬШJЪЬЭЬЭЬШJЪЬ	ЭЬЭЬШJЪЬЭЬЭЬЮШ;JЪЬЮШ5JЪЬШJЪЬШЧJШ JЪ	ЬЭЬЭЬЭЬЭЬШ0JЪ	ЬЭЬЭЬЭЬЭЬШ0JЪЬЭЬЭЬЭЬШ2JЪЬЭЬЭЬШ#JЪЬЭЬЭЬЭЬЭЬЭЬШ@JЪЬЭЬЭЬЭЬЭЬЭЬ	ЭЬШNJЪЬ	ЭЬЮ2ШTJЪЬЭЬЭЬЭЬШЧЪЬ4Щ4Ъ╧nЬЭЬЭЬЭЬШVJЪЬDЩDЧJЪЯЬЭЬЭЬЮШBJЪЯЬЭЬЭЬЮШEЪЯ
ЬЭЬШJЪЬШJЪЬЭЬЭЬЭЬШJЪЬ(Ш(ЪЬЭЬЭЬШJЪЭЬШЧJЪЬ\Щ\JЪЬ9Щ9JЪЬ!Щ!JЪЬFЩFЧЪЬ5Щ5JЪЬЩJЪЬЩJЪЬIЩIЪЭЬЭЩJЪЬЩJЪЬЩJЪЬ
ЭЬ6ЩBЧЧЧЩЩ:JЪЬ$Щ$JЪЬЭЬ(Щ@JЪЬ_Щ_JЪЬXЩXJЪЬ!Щ!ЧJЩ JЪ╨bfЬаЬ!Щ0JЪЯЬЩ'JЪЬ╧bЬЩ*JЪЬбЬЩ$JЪбЬ*бЬбЬЩ;ЪЬGЩGJЪбЬбЬбЬбЬбЬбЬyбЬ<ЩяЧЪЬ<Щ<JЪбаЬбЬЯЬбЬИбЬбЬЯЬЯЬЩЇЧJЪЬ*бЬЩ2ЪЬ/ЯЩ7JЪбЬ*Щ2ЧJЪЬЯЬЩ"JЪЬбЬ?ЯЬЩUJЪЬЯЬ5ЩEJЩлЩ/Щ JЩ ЧЧJШ JЪ
ЯЬЭЬЭЬЭЬЭЬШ2JЪЯЬЭЬЭЬЭЬЭЬЭЬШVJШ JЪЯЬЭЬЭЬШ)JЪЯЬЭЬЭЬЭЬШ7JЪЯЬЭЬЭЬЭЬШ7JЪЯЬЭЬЭЬЭЬШ9JЪЯЬЭЬЭЬШ)JЪЯЬЭЬЭЬШ3ЧЩ7JЪЯЬЭЬЮШ@JЪЯЬЭЬЭЬ
ЭЬЭЬЭЬЮШUЧЩЪ
ЯЬЭЬЭЬЭЬ'ЭЬШQJЪЭЬШЧЪЯЬЭЬ8ЭЬШPJЪЭЬШЧJЪЯЬЭЬЭЬШ?JЪЯЬЭЬЭЬШ>JЪЯЬЭЬЭЬШ@JШ ЧJЪЭЬШJШ Ч ЕЧ    ▐  #3  