Handle TrackElement ripup & topological modifications. More...

Public Types
enum	FunctionFlag { ToRipupLimit = 0x0001, AllowExpand = 0x0002, NoExpand = 0x0004, PerpandicularsFirst = 0x0008, ToMoveUp = 0x0010, AllowLocalMoveUp = 0x0020, AllowTerminalMoveUp = 0x0040, AllowShortPivotUp = 0x0080, NoDoglegReuse = 0x0100, LeftAxisHint = 0x0200, RightAxisHint = 0x0400, NotOnLastRipup = 0x0800 }

Public Member Functions
	Manipulator (TrackElement *, SegmentFsm &)

TrackElement *	getSegment () const

DataNegociate *	getData () const

RoutingEvent *	getEvent () const

bool	canRipup (unsigned int flags=0) const

bool	isCaged (DbU::Unit) const

bool	ripup (unsigned int type, DbU::Unit axisHint=0)

bool	ripupPerpandiculars (unsigned int flags=0)

void	repackPerpandiculars ()

bool	ripple ()

bool	minimize ()

bool	slacken (unsigned int flags=KbNoFlags)

bool	pivotUp ()

bool	pivotDown ()

bool	moveUp (unsigned int flags=0)

bool	makeDogleg ()

bool	makeDogleg (DbU::Unit)

bool	makeDogleg (Interval)

bool	relax (Interval, unsigned int flags=AllowExpand)

bool	insertInTrack (size_t)

bool	shrinkToTrack (size_t, unsigned int flags=0, DbU::Unit leftAxisHint=0, DbU::Unit rightAxisHint=0)

bool	forceToTrack (size_t)

bool	forceOverLocals ()

Detailed Description

Handle TrackElement ripup & topological modifications.

Manipulator Structure

A Manipulator basically binds together a TrackElement, it's DataNegociate and RoutingEvent (cached for fast access), and a SegmentFsm.

The TrackElement may differs from the one of the SegmentFsm. This can occurs when manipulating perpandiculars or segments from other nets in conflict. For example: Manipulator::isCaged().

In the following documentation, the segment which is associated to the SegmentFsm will be called the reference segment.

Delayed Modifications

It is important to note that when a Manipulator is called to modificate a TrackElement, nothing is actually done by the Manipulator itself. Instead, the Manipulator create the relevant SegmentAction (s) that are stored in the SegmentFsm. The action themselves are done at the end of the SegmentFsm lifecycle (wrapped inside a Session).

This is not true! When dogleg are created, the topology is immediatly modificated. That way of doing must be clarified.

Member Enumeration Documentation

◆ FunctionFlag

enum FunctionFlag

The various flags that can be passed to the Manipulator methods.

Enumerator
ToRipupLimit	The ripup limit must be immediatly to it's limit for the current state.
AllowExpand	Allow break points for dogleg not to be exactly on the requested position. Meaning that they are moved to the least congested GCell.
NoExpand	Breakpoints for dogleg are kept right where they are requested.
PerpandicularsFirst	Reorder the events so that perpandiculars segments are re-processed before their reference segment. By default this is the other way around.
ToMoveUp	Try to move up ripped up segments.
AllowLocalMoveUp	Allow local segments to be moved up (forbidden by default).
AllowTerminalMoveUp	Allow terminal segments to be moved up (forbidden by default).
AllowShortPivotUp	Allow short segment yo be pivoted up.
NoDoglegReuse	When creating a dogleg, the default behavior is not to create a new one if there's already one in the same GCell. If this flag is set, a second dogleg will be created.
LeftAxisHint	An explicit left axis hint has been supplied as argument.
RightAxisHint	An explicit right axis hint has been supplied as argument.
NotOnLastRipup	The reference segment has still more than one ripup to go for the given state.

Constructor & Destructor Documentation

◆ Manipulator()

Manipulator	(	TrackElement *	segment,
		SegmentFsm &	fsm
	)

Parameters

segment	The TrackElement to manipulate.
fsm	The associated SegmentFsm.

Construct a new Manipulator on segment.

Referenced by Manipulator::forceOverLocals(), Manipulator::forceToTrack(), Manipulator::insertInTrack(), Manipulator::ripupPerpandiculars(), and Manipulator::shrinkToTrack().

Member Function Documentation

◆ getSegment()

TrackElement * getSegment ( ) const

inline

Returns: The working TrackElement.

◆ getData()

DataNegociate * getData ( ) const

inline

Returns: The DataNegociate of the TrackElement (act as a cache).

◆ getEvent()

RoutingEvent * getEvent ( ) const

inline

Returns: The RoutingEvent associated to the TrackElement (act as a cache).

◆ canRipup()

bool canRipup ( unsigned int flags = 0 ) const

Returns: true if the maximum ripup, for the given SegmentFsm::State has not been reached. If flags contains Manipulator::HasNextRipup, return true only if it still have at least one ripup to go.

Referenced by Manipulator::forceToTrack(), and Manipulator::ripup().

◆ isCaged()

bool isCaged ( DbU::Unit axis ) const

Returns: true if the segment is enclosed (in it's Track) by two fixed or blockage segments which at least one is closer than 10 lambdas from axis. Mostly used to know if a perpandicular is actually restricting the axis span of a reference segment.

Referenced by Manipulator::ripupPerpandiculars().

◆ ripup()

bool ripup	(	unsigned int	type,
		DbU::Unit	axisHint = `0`
	)

Parameters

type	The type of ripup action.
axisHint	An indication as where to move the riped up segment.

Returns: true if the operation has succedeed.

If the TrackElement can be ripped up, schedule a ripup action, possibly with a hint for the preferred axis position.

Referenced by Manipulator::forceOverLocals(), Manipulator::forceToTrack(), Manipulator::insertInTrack(), and Manipulator::ripupPerpandiculars().

◆ ripupPerpandiculars()

bool ripupPerpandiculars ( unsigned int flags = 0 )

Schedule a ripup of all the perpandiculars of the reference segment. flags that modificate the behavior:

Manipulator::PerpandicularsFirst : the queue will be reordered so that all the perpandiculars are re-processed (placed) before the reference segment.
Manipulator::ToRipupLimit : the ripup count of the reference segment is set to the limit (i.e. only one more attempt before a slackening occurs).

The method will fails (return false) if at least one perpandicular can't be changed of track (i.e. ripped up) and none of it's neighbors could be ripped up either. Meaning that the free span on that track cannot be changed.

Referenced by SegmentFsm::conflictSolveByPlaceds().

◆ repackPerpandiculars()

bool repackPerpandiculars ( )

Ripup all the perpandiculars of the reference segment, except fixed or globals. The reference segment is rescheduled first (before it's perpandicular).

This function may be used to find a better placement, maximizing the overlap of the various perpandiculars.

Ripup all perpandiculars and the reference segment itself for a complete re-placement. The reference segment will be reprocessed before it's perpandiculars.

◆ ripple()

bool ripple ( )

Returns: true if the reference segment is local.

Applies only on reference segments that are of local type. Tries to make room for the reference segment by ripping up it's neigbors on the parallels tracks. On a vertical plane, left neigbors are shifted one track left (trough axis hint) and right ones, one track right. Note that they are ripped up and the shift is just a hint, there's no guarantee that the router can honor it.

Referenced by Manipulator::ripupPerpandiculars().

◆ minimize()

bool minimize ( )

Returns: true if the reference segment can be mimized in a suitable track hole.

Compute the miminal span of the reference segment, summing up contraints from source anchor and target anchors (if any) and perpandiculars. Then find holes in the avalaible tracks, and check if one is suitable for the miminized segment (try first the biggest hole).

This operation can only be called once on a segment (a flag is set in the event).

◆ slacken()

bool slacken ( unsigned int flags = KbNoFlags )

Simple proxy towards TrackElement::slacken().

To be reviewed.

◆ pivotUp()

bool pivotUp ( )

Tries to move up the reference segment. The segment will be moved up only if a half track is free (for a local) or a full track is free (for a global).

This function do not modifies/create perpandiculars.

Referenced by SegmentFsm::solveFullBlockages().

◆ pivotDown()

bool pivotDown ( )

Tries to move down the reference segment. The segment will be moved up only if two track are free (whether global or local). Is is more restrictive than Manipulator::pivotUp().

This function do not modifies/create perpandiculars.

◆ moveUp()

bool moveUp ( unsigned int flags = 0 )

Tries to move up a segment, if there is enough space in the RoutingPlane above and in the same direction.

This function may modificate perpandiculars in order to maintain connexity.

To be reviewed.

Referenced by SegmentFsm::solveFullBlockages().

◆ makeDogleg() [1/3]

bool makeDogleg ( )

Returns: false if the segment is not local or the dogleg cannot be done.

For local reference segment only, look in the first track candidate for other segment overlapping and break the reference accordingly.

◆ makeDogleg() [2/3]

bool makeDogleg ( DbU::Unit position )

Create a dogleg in the GCell under position.

◆ makeDogleg() [3/3]

bool makeDogleg ( Interval overlap )

Create a dogleg to avoid the obstructed interval overlap.

◆ relax()

bool relax	(	Interval	overlap,
		unsigned int	flags = `AllowExpand`
	)

Break the reference segment so it can detour around the interval overlap. If overlap is completly enclosed inside the span of the reference segment two dogleg will be created. If the overlap occurs only on one side of the reference segment, only one dogleg will be created.

If flags contains Manipulator::AllowExpand, the dogleg are not created exactly at the edges of the overlap but on the lowest density GCell (outside the overlap interval).

The axis of the created dogleg are sets so that the broken part of the segment completly enclose overlap. That is, the orignal segment no longer intersect with overlap. So the min dogleg is pushed to the left and the max to the right if they are in the same GCell as the min/max of overlap. Otherwise (they have been expanded), they are put in the center of the GCell.

We do not allow to dogleg twice in the same GCell, so if min or max is in respectively the first or last GCell, it is not done. Moreover if there is only one dogleg and it is in the first or last GCell, the relax method is cancelled (and returns false). It means that this is the segment which is likely to be enclosed inside overlap.

Important: The doglegs are created immediatly and not in a delayed fashion like the SegmentAction.

Two Doglegs (min & max), no expansion

Two Doglegs (min & max), with expansion

One Dogleg (min)

One Dogleg (max)

◆ insertInTrack()

bool insertInTrack ( size_t i )

Try to insert the reference segment in the track at index i (in the cost table from SegmentFsm). The insertion is done by ripping up overlapping segment or shrinking them to left/right if possible.

This operation ripup the processed segment neighbors (and their perpandiculars).

◆ shrinkToTrack()

bool shrinkToTrack	(	size_t	i,
		unsigned int	flags = `0`,
		DbU::Unit	leftAxisHint = `0`,
		DbU::Unit	rightAxisHint = `0`
	)

Attempt to minimize the reference segment to fit into the track. For this operation to succeed, the minimal span of the segment must not overlap any other segment already in the track. To reach the minimal span the perpandiculars are ripped up with an axis hint which is the center of the minimal span or the explicit value given as arguments leftAxisHint and rightAxisHint if flags contains respectively Manipulator::LeftAxisHint or Manipulator::RightAxisHint.

This operation ripup the processed segment itself and its perpandiculars.

◆ forceToTrack()

bool forceToTrack ( size_t i )

Try to insert the reference segment in the track at index i (in the cost table from SegmentFsm). The insertion is done by forcibly ripping up the overlapping segments and their perpandiculars.

This operation ripup the processed segment neighbors (and their perpandiculars).

◆ forceOverLocals()

bool forceOverLocals ( )

Loop over all the candidate tracks and, insert in the first which all conflicting segments are locals (rip them up).

The documentation for this class was generated from the following files:

Manipulator.h
Manipulator.cpp
Manipulator.dox

Kite - Detailed Router

Public Types

Public Member Functions

Detailed Description

Manipulator Structure

Delayed Modifications

Member Enumeration Documentation

◆ FunctionFlag

Constructor & Destructor Documentation

◆ Manipulator()

Member Function Documentation

◆ getSegment()

◆ getData()

◆ getEvent()

◆ canRipup()

◆ isCaged()

◆ ripup()

◆ ripupPerpandiculars()

◆ repackPerpandiculars()

◆ ripple()

◆ minimize()

◆ slacken()

◆ pivotUp()

◆ pivotDown()

◆ moveUp()

◆ makeDogleg() [1/3]

◆ makeDogleg() [2/3]

◆ makeDogleg() [3/3]

◆ relax()

◆ insertInTrack()

◆ shrinkToTrack()

◆ forceToTrack()

◆ forceOverLocals()