
    <<>>
    <<SCPrivate.mesa>>
        <<Copyright Ó 1985, 1986, 1987 by Xerox Corporation.  All rights reserved.>>
        <<by Bryan Preas, July 10, 1985 11:48:30 am PDT >>
        <<Frank Bowers May 21, 1986 5:35:15 pm PDT>>
        <<last edited by Bryan Preas, April 19, 1987 12:55:45 pm PDT>>
    <<>>
    DIRECTORY
        CD, Core, CoreGeometry, DABasics, Rope, Route, RoutePrivate, RTBasic, RTCoreUtil, RTSets, SC;

    SCPrivate: CEDAR DEFINITIONS = {

    CompClass: TYPE = {other, logic, io, ft};
    DegreeOfConnection: TYPE = {full, min, none};
    UpperLowerConnection: TYPE = RECORD [
        lower, upper: DegreeOfConnection _ none];
    RouteTopology: TYPE = ARRAY MaxChanSr OF UpperLowerConnection;
    LRSide: TYPE = DABasics.LRSide;
    TBSide: TYPE = DABasics.TBSide;
    LRSideSet: TYPE = RTSets.RTSmSet -- OF LRSide -- ;
    SideSet: TYPE = RTSets.RTSmSet -- OF ValidSide -- ;
    RowSet: TYPE = RTSets.RTMdSet -- OF MaxRowSr -- ;
    ChanSet: TYPE = RTSets.RTMdSet -- OF MaxChanSr -- ;

    StructureData: TYPE = REF StructureDataRec;
    StructureDataRec: TYPE = RECORD [
        objects: Objects _ NIL,
        instances: Instances _ NIL,
        nets: Nets _ NIL];

    LayoutData: TYPE = REF LayoutDataRec;
    LayoutDataRec: TYPE = RECORD [
        totWidth, totHeight, initTotWidth, initTotHeight: SC.Number _ 0,
        bpRows: BpRows _ NIL,
        lgRows: LgRows _ NIL,
        sideChans: SideChans _ [NIL, NIL],
        rowChans: RowChans _ NIL,
        powerBuses: PowerBuses _ [NIL, NIL],
        layoutParms: LayoutParms,
        placeDat: REF ANY _ NIL,
        globalRoute: REF ANY _ NIL];

    Parms: TYPE = REF ParmsRec;
    ParmsRec: TYPE = RECORD [
        libName: Rope.ROPE _ NIL,
        libDesign: CD.Design _ NIL,
        ftObject, portObject, vddObject, gndObject: Object _ NIL];

    LayoutParms: TYPE = REF LayoutParmsRec;
    LayoutParmsRec: TYPE = RECORD [
        whichFom: FomType _ wlFom,
        useInteriorChanExits: BOOLEAN _ TRUE,
        rowDirection: SC.Direction _ horizontal,
        powerName: ARRAY LRSide OF Rope.ROPE];

    maxObjects: NAT = 100;
    maxPinsOnObject: NAT = 100;
    MaxObjectsSr: TYPE = NAT[1 .. maxObjects];  -- Object definitions
    ZMaxObjectsSr: TYPE = NAT[0 .. maxObjects];  -- Object definitions
    Objects: TYPE = REF ObjectsRec; 
    ObjectsRec: TYPE = RECORD [
        count: ZMaxObjectsSr _ 0,
        ob: ARRAY MaxObjectsSr OF Object _ ALL[NIL]]; 
    Object: TYPE = REF ObjectRec;
    ObjectRec: TYPE = RECORD [
        name: Rope.ROPE _ NIL, 
        objectNum: MaxObjectsSr,
        size, orgin: RTBasic.PQPos _ [0, 0], 
        numPins: NAT _ 0,
        pins: ObjectPins _ NIL, 
        typeClass: CompClass _ other,
        numTimesUsed: NAT _ 0,
        cdOb: CD.Object _ NIL,
        cellType: Core.CellType _ NIL];

    ObjectPin: TYPE = REF ObjectPinRec;
    ObjectPins: TYPE = REF ObjectPinsRec;
    ObjectPinsRec: TYPE = RECORD [
        p: SEQUENCE size: NAT OF ObjectPin];
    ObjectPinRec: TYPE = RECORD [
        name: Rope.ROPE _ NIL, 
        pinPos: PinPos,
        publicWire: Core.Wire,
        rect: SC.Rect _ [0, 0, 0, 0],
        layer: SC.Layer, 
        equivClass: Rope.ROPE _ NIL];
    PinPos: TYPE = RECORD [
        side: SC.SideOrNone _ none, 
        depth, location: SC.Number _ 0];

    <<bonding pad and logic component types >>
    maxInstance: NAT = 12000;
    MaxInstanceSr: TYPE = NAT[1 .. maxInstance];
    ZMaxInstanceSr: TYPE = NAT[0 .. maxInstance];
    Instance: TYPE = REF InstanceRec;
    InstanceList: TYPE = LIST OF Instance;
    Instances: TYPE = REF InstancesRec; 
    InstancesRec: TYPE = RECORD [
        count, numIOs, numLogics, numFts: ZMaxInstanceSr _ 0,
        inst: Insts _ NIL]; 
    Insts: TYPE = REF InstsOb;
    InstsOb: TYPE = ARRAY MaxInstanceSr OF Instance _ ALL[NIL];
    InstanceRec: TYPE = RECORD [
        name: Rope.ROPE,
        num: MaxInstanceSr,
        object: Object _ NIL,
        pinNets: PinNets _ NIL,
        prePos, curPos, initPos, fnlPos: INT _ 0,
        preOrien, curOrien, initOrien, fnlOrien: OrientationOrNone _ 0,
        offset: SC.Number _ 0,
        whichClass: CompClass,
        ftNet: Net _ NIL,
        equivPortClass: Rope.ROPE _ NIL,
        instDat: REF ANY _ NIL,
        compClassSel: SELECT OVERLAID CompClass FROM
            ft, logic => [
                preRow, curRow, initRow, fnlRow: ZMaxRowSr _ 0],
                <<ftNet: Net _ NIL],>>
            io => [
                preSide, curSide, initSide, fnlSide: SC.SideOrNone _ none],
                <<equivPortClass: Rope.ROPE _ NIL],>>
            ENDCASE];

    OrientationOrNone: TYPE = NAT[0 .. maxOrien];
    Orientation: TYPE = OrientationOrNone[1 .. maxOrien];
    maxOrien: NAT = 8;

    PinNets: TYPE = REF PinNetsRec;
    PinNetsRec: TYPE = RECORD[n: SEQUENCE size: NAT OF PinNet];
    PinNet: TYPE = REF PinNetRec;
    PinNetRec: TYPE = RECORD [
        pin: ObjectPin _ NIL,
        pinInChan: REF ANY _ NIL,        -- SCNewRoutePinsUtil.PinInChan
        net: Net _ NIL];

    <<interconnection net types >>
    PinType: TYPE = {compPin, externalPin, ftPin};
    maxNets: NAT = 8000;
    MaxNetsSr: TYPE = NAT[1 .. maxNets];
    ZMaxNetsSr: TYPE = NAT[0 .. maxNets];
    Net: TYPE = REF NetRec;
    NetList: TYPE = LIST OF Net;
    Nets: TYPE = REF NetsRec; 
    NetsRec: TYPE = RECORD [
        count: ZMaxNetsSr _ 0,
        nets: NetArrayRef]; 
    NetArray: TYPE = ARRAY MaxNetsSr OF Net _ ALL[NIL];
    NetArrayRef: TYPE = REF NetArray;
    NetRec: TYPE = RECORD [
        name: Rope.ROPE _ NIL,
        wire: Core.Wire _ NIL,            -- Core wire corresponding to this net
        num: MaxNetsSr,
        numberOfRegions: INT _ 0,        -- records number of breaks for this net
        brokenNets: LIST OF Route.Label _ NIL,    -- records names of broken nets
        trunkWidth, branchWidth: SC.Number _ 0,
        score, oldScore: REAL _ 0.0,         -- current and previous placement score
        updatedOnTrial: INT _ 0,            -- placement trial last updated
        externNet: ExtNet _ internalNet, 
        ftsOnRow: RowSet,             -- rows which have ft's on this net
        chanExits: ARRAY LRSide OF ChanSet,
        routeTopology: RouteTopology,        -- global routing
        netDat: REF ANY _ NIL,
        pinsOnChan: LIST OF RoutePrivate.Pin _ NIL,
        pins: NetPinSeq _ NIL,            -- sequence of instance/pins on net
        pinList:  REF ANY _ NIL,        -- pins for net in global routing (LIST OF SCNewRoutePinsUtil.PinInChan)
        edgeList: REF ANY _ NIL            -- edges for net in global routing (SCNewGlobalRoute.EdgeList)
        ];
    ExtNet: TYPE = {externalNet, internalNet};

    NetPinSeq: TYPE = REF NetPinSeqRec;
    NetPinSeqRec: TYPE = RECORD [
        np: SEQUENCE size: NAT OF NetPin];
    NetPin: TYPE = REF NetPinRec;
    NetPinRec: TYPE = RECORD [
        pinClass: PinType _ compPin,
        instance: Instance _ NIL, 
        pin: ObjectPin _ NIL
        ];

    maxPos: NAT = 1000;
    MaxPosSr: TYPE = NAT[1 .. maxPos];
    ZMaxPosSr: TYPE = NAT[0 .. maxPos];

    <<bonding pad side and logic row types >>
    BpRow: TYPE = REF BpRowRec;
    BpRows: TYPE = REF BpRowsRec; 
    BpRowsRec: TYPE = ARRAY SC.Side OF BpRow _ ALL[NIL]; 
    BpRowRec: TYPE = RECORD [
        bpSpacing: INT _ 0, 
        size, sideOrg: RTBasic.PQPos _ [0, 0], 
        dimInvalid: BOOLEAN _ TRUE, 
        initMaxBpsOnSide, maxBpsOnSide, nBpsOnSide: ZMaxPosSr _ 0, 
        bpsOnSide: ARRAY MaxPosSr OF Instance _ ALL[NIL], 
        fnlBpFxd, initBpFxd: BOOLEAN _ FALSE];

    maxLgRows: NAT = 50;
    MaxRowSr: TYPE = NAT[1 .. maxLgRows];
    ZMaxRowSr: TYPE = NAT[0 .. maxLgRows];
    LgRow: TYPE = REF LgRowRec;
    LgRows: TYPE = REF LgRowsRec;
    LgRowsRec: TYPE = RECORD [
        horzRowOrg, maxRowWidth: SC.Number _ 0,
        numMaxRows: NAT _ 0,
        count: ZMaxRowSr _ 0,
        rows: ARRAY MaxRowSr OF LgRow _ ALL[NIL]]; 
    LgRowRec: TYPE = RECORD [
        size, rowOrg: RTBasic.PQPos _ [0, 0], 
        dimInvalid: BOOLEAN _ TRUE,
        rowNum: NAT, 
        nLgsOnRow, nFtsOnRow: ZMaxPosSr _ 0, 
        lgsOnRow: ARRAY MaxPosSr OF Instance _ ALL[NIL], 
        fnlLgFxd, initLgFxd: BOOLEAN _ FALSE,
        cdOb: CD.Object _ NIL,
        publics: PublicPinList _ NIL,
        weight: NAT _ 0];

    maxChans: NAT = maxLgRows + 1;
    MaxChanSr: TYPE = NAT[1 .. maxChans];
    ZMaxChanSr: TYPE = NAT[0 .. maxChans];

    RowChan: TYPE = REF RowChanRec;
    RowChans: TYPE = REF RowChansRec;
    RowChansRec: TYPE = RECORD [
        count: ZMaxChanSr _ 0,
        chans: ARRAY MaxChanSr OF RowChan _ ALL[NIL]]; 
    RowChanRec: TYPE = RECORD [
        chanNum: NAT,
        initChanWidth, chanWidth, chanPos, wireLength, chanDensity: SC.Number _ 0,
        numTracks: NAT _ 0,
        numExits: ARRAY LRSide OF ZMaxExitsSr _ [0, 0], 
        exits: ExitArray _ NIL,
        publics: PublicPinList _ NIL,
        chanDat: REF ANY _ NIL
        ];
    ExitArrayOb: TYPE = ARRAY LRSide OF ARRAY MaxExitsSr OF Exit;
    ExitArray: TYPE = REF ExitArrayOb;
    maxExits: NAT = 100;
    MaxExitsSr: TYPE = NAT[1 .. maxExits];
    ZMaxExitsSr: TYPE = NAT[0 .. maxExits];
    Exit: TYPE = REF ExitRec;
    ExitRec: TYPE = RECORD [
        net: Net _ NIL,
        pinInChan: REF ANY _ NIL,        -- SCNewRoutePinsUtil.PinInChan
        pos: SC.Number _ 0,            -- track number
        layer: SC.Layer];

    SideChan: TYPE = REF SideChanRec;
    SideChans: TYPE = ARRAY LRSide OF SideChan;
    SideChanRec: TYPE = RECORD [
        side: SC.Side,
        initSideChanWidth, sideChanWidth, sideChanPos, wireLength: SC.Number _ 0,
        sideChanTracks: NAT _ 0];

    <<used to describe the bower nets>>
    PowerBuses: TYPE = ARRAY LRSide OF PowerBus;
    PowerBus: TYPE = REF PowerBusRec;
    PowerBusRec: TYPE = RECORD [
        name: Rope.ROPE _ NIL,
        net: Net _ NIL];

    <<used for decorating public wires on the input cellType>>
    PublicPinList: TYPE ~ LIST OF PublicPin;
    PublicPin: TYPE ~ REF PublicPinRec;
    PublicPinRec: TYPE ~ RECORD [
        wire: Core.Wire,
        object: CD.Object,
        trans: CD.Transformation];

    FomType: TYPE = {areaFom, wlFom};

    GetStructure: PROC [handle: SC.Handle, cellType: Core.CellType,
        flattenCellType: RTCoreUtil.FlattenCellTypeProc, decoration: CoreGeometry.Decoration]
        RETURNS [done: BOOLEAN];

    DestroyStructure: PROC [handle: SC.Handle];

    SetUpLayout: PROC [handle: SC.Handle, cellType: Core.CellType]
        RETURNS [done: BOOLEAN];

    DestroyLayout: PROC [handle: SC.Handle];

    DetailRoute: PROC [handle: SC.Handle] RETURNS [result: SC.Result];

    PosImprove: PROC [handle: SC.Handle, whichFom: FomType, maxCycles: INT];
        <<improve positions of cells on a row>>
        <<>>
    NewPosImprove:  PROCEDURE [handle: SC.Handle, whichFom: SCPrivate.FomType, maxCycles: INT];

    NewOrientImprove: PUBLIC PROCEDURE [handle: SC.Handle, whichFom: SCPrivate.FomType, maxCycles: INT];

    FTImprove: PROC [handle: SC.Handle, whichFom: FomType, maxCycles: INT];
        <<improve positions of the feedthrus on a row>>
        <<>>
    OrientImprove: PROC [handle: SC.Handle, whichFom: FomType, maxCycles: INT];

    SAInitialPlace: PROC [handle: SC.Handle, widthFactor: REAL, seed: INT] RETURNS [initialResult: SC.SAInitialResult];
        <<Initialize for simulated annealing improvement.>>

    SAGetParms: PROC [handle: SC.Handle, initialResult: SC.SAInitialResult, cellType: Core.CellType] RETURNS [saParms: SC.SAParms];
        <<determine parameters for simulated placement.>>
        <<>>
    SAPlaceImprove: PROC [handle: SC.Handle, saParms: SC.SAParms, widthFactor: REAL, seed: INT];
        <<Improve the placement for the instances (in pairs) by simulated annealing.>>

    SAPlaceImproveM: PROC [handle: SC.Handle, saParms: SC.SAParms, widthFactor: REAL, seed: INT];
        <<Improve the placement for the instances (one at a time) by simulated annealing.>>

    PlaceImprove: PROC [handle: SC.Handle, maxCycles: INT];
        <<Improve the placement for the instances by exhaustive search.>>

    SCRandomTest: PUBLIC PROCEDURE [handle: SC.Handle, trials, seed: INT];

    }.