1 /* 2 * gcr.h -- 3 * 4 * Routines to implement a modified version of Rivest's Greedy Router. 5 * 6 * ********************************************************************* 7 * * Copyright (C) 1985, 1990 Regents of the University of California. * 8 * * Permission to use, copy, modify, and distribute this * 9 * * software and its documentation for any purpose and without * 10 * * fee is hereby granted, provided that the above copyright * 11 * * notice appear in all copies. The University of California * 12 * * makes no representations about the suitability of this * 13 * * software for any purpose. It is provided "as is" without * 14 * * express or implied warranty. Export of this software outside * 15 * * of the United States of America may require an export license. * 16 * ********************************************************************* 17 * 18 * 19 * rcsid "$Header: /usr/cvsroot/magic-8.0/gcr/gcr.h,v 1.1.1.1 2008/02/03 20:43:50 tim Exp $" 20 */ 21 22 #ifndef _GCR_H 23 #define _GCR_H 24 25 #include "utils/magic.h" 26 27 /* GCRPin: One of these for each pin location along each edge of a channel. 28 * All of the pins for a given net are stored on a doubly-linked list 29 * for the net, sorted from left to right and bottom to top. Stored 30 * with the pin are its track and column coordinates (not the actual 31 * locations of terminals). 32 * 33 * A pin also stores crossing information for use by the global router, 34 * namely gcr_cost (the best cost known so far to reach this pin), 35 * gcr_side (GEO_NORTH, GEO_SOUTH, GEO_EAST, or GEO_WEST, giving the 36 * side of the channel that the pin lies on), and gcr_linked, pointing 37 * to the pin (in the neighboring channel) that shares the same crossing 38 * point as this one. 39 * 40 * x= 0 means the pin is at the left edge of the channel. 41 * x= length+1 means the pin is at the right edge of the channel. 42 * y= 0 means the pin is at the bottom edge of the channel. 43 * y= width+1 means the pin is at the top edge of the channel. 44 * 45 * A net id is in two parts, a net id (gcr_pId) and a segment 46 * id (gcr_pSeg). During global routing the net id is an integer 47 * net id, not a pointer to a struct (it doesn't turn into a 48 * pointer until just before channel routing). The segment id 49 * distinguishes parts of a net which are not connected within a 50 * channel because they are connected elsewhere (this prevents 51 * the router from generating loops in the routing). 52 */ 53 typedef struct pin 54 { 55 int gcr_x, gcr_y; /* Column and track coordinates */ 56 57 /* Information on nearest obstacle */ 58 int gcr_pFlags; /* 0=clear,1=Obstacle,2=Hazard */ 59 short gcr_pSize; /* Size of nearest obstacle */ 60 short gcr_pDist; /* Distance to nearest obstacle */ 61 62 /* 63 * Net id and segment id assigned to this pin. 64 * Special semantics: 65 * gcr_pId == GCR_BLOCKEDNETID means this pin is blocked. 66 * gcr_pSeg == GCR_STEMSEGID means this pin is a stem tip; 67 * gcr_pId gives the net to which the stem tip belongs. 68 */ 69 int gcr_pSeg; /* Id naming part of a net id */ 70 struct gcrnet *gcr_pId; /* Net structure for pin's net */ 71 72 /* 73 * These fields link available pins along the side of a channel 74 * during global routing, and link pins in a net during channel 75 * routing. 76 */ 77 struct pin *gcr_pNext; /* Next pin to the right or up */ 78 struct pin *gcr_pPrev; /* Next pin left or down */ 79 80 /* 81 * Stuff for the global router. 82 * This is NOT valid in transformed channels, so should 83 * not be used by the channel router. 84 */ 85 int gcr_cost; /* Used during global routing */ 86 struct chan *gcr_ch; /* Channel to which this pin belongs */ 87 int gcr_side; /* Side of channel this pin lies on */ 88 struct pin *gcr_linked; /* Pin (in channel abutting this one) 89 * sharing same crossing point. 90 */ 91 Point gcr_point; /* Point along channel boundary 92 * in edit cell coords. 93 */ 94 } GCRPin; 95 96 #define GCR_BLOCKEDNETID ((GCRNet *) -1) 97 #define GCR_STEMSEGID (-1) 98 99 /* GCRNet: One structure for each net to be routed. Nets have pointers, 100 * to their leftmost and rightmost pins. The dist field stores the 101 * distance from an unsplit rising or falling active net's current 102 * track to its next connection. Nets are linked so they may be 103 * freed when the routing is complete. 104 * 105 * Each net_id/seg_id pair generates a unique gcrnet struct. 106 */ 107 typedef struct gcrnet 108 { 109 int gcr_Id; /* Integer identifying the net */ 110 int gcr_dist; /* Distance to target track +/- */ 111 int gcr_sortKey; /* Use to prioritize nets */ 112 int gcr_track; /* Track index, used for working 113 * storage in colInit. 114 */ 115 GCRPin *gcr_lPin; /* Leftmost pin of net */ 116 GCRPin *gcr_rPin; /* Rightmost pin of net */ 117 struct gcrnet *gcr_next; /* Next on a linked list of nets */ 118 } GCRNet; 119 120 121 /* GRColEl: Used in array form, this struct stores horizontal and vertical 122 * wiring for the current column as it is routed. Locations 1..width are 123 * valid tracks, while 0 and width+1 are wiring to channel top and bottom. 124 * 125 * gcr_hi and gcr_lo are used to maintain ordered doubly linked lists of 126 * all tracks occupied by the same net. 127 * 128 * gcr_hOk and gcr_lOk are tricky. They are needed because we 129 * artificially split nets near the end of a channel if there 130 * are multiple end connections. The net must stay split, but 131 * what's tricky is that several groups of tracks may exist that 132 * are connected within the groups, but the groups haven't been 133 * connected together yet. These flags keep track of this information. 134 * For example, if gcr_hOk is TRUE but gcr_lOk is false, it 135 * means we don't need to collapse this track with the next one 136 * up, but we do need to join this track with the next one down. 137 * These flags are only used near the ends of channels, and are 138 * normally FALSE. 139 */ 140 typedef struct gcrColEl 141 { 142 GCRNet * gcr_h; /* Net for horizontal wiring */ 143 GCRNet * gcr_v; /* Net for vertical wiring */ 144 int gcr_hi; /* Next higher track for net gcr_h */ 145 int gcr_lo; /* Next lower track for net gcr_h */ 146 bool gcr_hOk; /* TRUE if don't need to collapse up */ 147 bool gcr_lOk; /* TRUE if don't need to collapse dn */ 148 int gcr_flags; /* Flags from the "result" array */ 149 GCRNet * gcr_wanted; /* Net that wants this track for end pin*/ 150 } GCRColEl; 151 152 153 /* GCRChannel: 154 * 155 * Represents all information concerning a channel to be routed. 156 * In order to handle boundary conditions more easily, the grid 157 * arrays, such as gcr_lCol and gcr_result hold an extra grid 158 * point's worth on each side: the grids run from 0 through 159 * length+1 in x, and from 0 through width+1 in y. The actual 160 * channel is from 1..length and 1..width 161 */ 162 163 #define CHAN_NORMAL 0 164 #define CHAN_HRIVER 1 165 #define CHAN_VRIVER 2 166 167 typedef struct chan 168 { 169 /* Description of the channel */ 170 int gcr_type; /* CHAN_NORMAL (0) if a normal channel, 171 * CHAN_HRIVER if only horizontal river routes 172 * are allowed, CHAN_VRIVER if only vertical 173 * river routes are allowed. 174 */ 175 int gcr_length; /* Number of columns in the channel */ 176 int gcr_width; /* Number of tracks in the channel */ 177 Point gcr_origin; /* Grid 0 point */ 178 Rect gcr_area; /* Area of channel in edit cell coords */ 179 Transform gcr_transform; /* Transform used when cell has been flipped 180 * or rotated. Apply this transfrom to grid 181 * coords, scale by grid size, then displace 182 * by gcr_origin to get edit cell coords. 183 */ 184 185 /* For use by the global router */ 186 short *gcr_dRowsByCol;/* Horizontal density during global routing */ 187 short *gcr_dColsByRow;/* Vertical density during global routing */ 188 short gcr_dMaxByCol; /* Max horizontal density */ 189 short gcr_dMaxByRow; /* Max vertical density */ 190 #define IDENSITY 191 #ifdef IDENSITY 192 short *gcr_iRowsByCol;/* FOR DEBUGGING */ 193 short *gcr_iColsByRow;/* FOR DEBUGGING */ 194 #endif /* IDENSITY */ 195 struct chan *gcr_next; /* For linked lists of channels */ 196 197 /* Description of the connections */ 198 GCRPin *gcr_tPins; /* Pins at the top of the channel */ 199 GCRPin *gcr_bPins; /* Pins at the bottom of the channel */ 200 GCRPin *gcr_lPins; /* Pins at the left edge of the channel */ 201 GCRPin *gcr_rPins; /* Pins at the right edge of the channel */ 202 GCRNet *gcr_nets; /* Data for each net */ 203 204 /* Working storage */ 205 GCRColEl *gcr_lCol; /* Column for vertical wiring */ 206 int *gcr_density; /* Density for each column */ 207 short **gcr_result; /* Array of columns, storing the result */ 208 209 /* For hanging additional information in channels */ 210 ClientData gcr_client; /* For hire */ 211 int gcr_orient; /* Channel orientation */ 212 } GCRChannel; 213 214 /* Macros that look like procedures */ 215 216 /************************************************************************ 217 * Is1stPin(pin) 218 * GCRPin * pin; 219 * 220 * Return TRUE if the indexed pin is the first pin on its list. 221 */ 222 #define Is1stPin(pin) ((pin)==(pin)->gcr_pId->gcr_lPin) 223 224 /************************************************************************ 225 * IsLstPin(pin) 226 * GCRPin * pin; 227 * 228 * Return TRUE if the indexed pin is the last pin on its list. 229 */ 230 #define IsLstPin(pin) ((pin)==(pin)->gcr_pId->gcr_rPin) 231 232 /************************************************************************ 233 * GCRNearEnd(channel, column) 234 * GCRChannel * channel; 235 * int column; 236 * 237 * Return TRUE if the column is within GCREndDist of the end of the channel. 238 */ 239 #define GCRNearEnd(ch,col) (((ch)->gcr_length+1-(col)) <= GCREndDist) 240 241 /************************************************************************ 242 * GCRPin1st(net) 243 * GCRNet * net; 244 * 245 * Return a pointer to the net's first pin. 246 */ 247 #define GCRPin1st(n) ((n)->gcr_lPin) 248 249 /************************************************************************ 250 * GCRPinNext(pin) 251 * GCRPin * pin; 252 * 253 * Return a pointer to a net's next pin. 254 */ 255 #define GCRPinNext(p) ((p)->gcr_pNext) 256 257 #define BLOCK(i) (((i)&GCRBLKM) && ((i)&GCRBLKP)) 258 #define CLEAR(i) (!((i)&(GCRBLKM|GCRBLKP))) 259 #define HAS_M(i) (((i)&GCRBLKM) && (!((i)&GCRBLKP))) 260 #define HAS_P(i) (((i)&GCRBLKP) && (!((i)&GCRBLKM))) 261 #define IS_EMPTY(c,x,y) ((x)<0 ? TRUE : ((x)>(c)->gcr_length ? TRUE : \ 262 CLEAR((c)->gcr_result[x][y]))) 263 264 265 /* 266 * Constants for the result array bits. Metal and poly here refer to 267 * the preferred materials for the long and short dimension of the 268 * channel. 269 */ 270 271 /* 272 * The input routine sets these to show where the obstacles are. 273 * These entries need to be present in these positions. 274 */ 275 #define GCRBLKM 0x0001 /* 1 if the location is blocked with metal */ 276 #define GCRBLKP 0x0002 /* 1 if the location is blocked with poly */ 277 278 /* The router sets these bits to show the wiring it produces */ 279 #define GCRU 0x0004 /* 1 if connect from track upwards */ 280 #define GCRR 0x0008 /* 1 if connect to the right */ 281 #define GCRX 0x0010 /* 1 if metal/poly contact */ 282 283 /* 284 * These bits are used to indicate whether obstacles block tracks 285 * or columns for the density computation; they are reset to zero 286 * after density initialization so they don't interfere with the 287 * wiring bits above (which occupy the same bit positions and mean 288 * something entirely different). 289 */ 290 #define GCRBLKT 0x0004 /* Blocks a track */ 291 #define GCRBLKC 0x0008 /* Blocks a column */ 292 293 /* The obstacle identifier sets these to say how to avoid obstacles */ 294 #define GCRVL 0x0020 /* 1 if the track should be vacated here */ 295 #define GCRV2 0x0040 /* 1 if vacate here due to 2-layer obstacle */ 296 #define GCRTC 0x0080 /* 1 if track contact needed */ 297 #define GCRCC 0x0100 /* 1 if column contact needed */ 298 #define GCRTE 0x0200 /* 1 if track can't be use in next column to rt */ 299 #define GCRCE 0x0400 /* 1 if column ends beyond this point */ 300 301 /* The metal maximizer sets these bits */ 302 #define GCRVM 0x0800 /* 1 if vertical poly changed to metal */ 303 #define GCRXX 0x1000 /* 1 if via not deleted */ 304 305 /* The hazard generation code uses these bits */ 306 #define GCRVR 0x2000 /* 1 if hazard to nets entering from the right */ 307 #define GCRVU 0x4000 /* 1 if hazard to nets entering from the top */ 308 #define GCRVD 0x8000 /* 1 if hazard to nets entering from the bottom */ 309 #define EMPTY -1 310 311 /* Flag bits used to indicate obstacles or hazards over pins */ 312 #define GCRCLR 0 /* No hazard or obstacle over crossing */ 313 #define GCRHAZRD 1 /* Hazard over crossing */ 314 #define GCROBST 2 /* Obstacle over crossing */ 315 #define GCRBLK 4 /* Blocked area over crossing */ 316 #define GCRTCC 8 /* Track or column contact near crossing */ 317 318 /* Clip a value (e.g, column or track number) to lie within a range */ 319 #define INRANGE(x, min, max) \ 320 ((x) < (min) ? (min) : ((x) > (max) ? (max) : (x))) 321 322 /* These are parameters the user sets to control the router. */ 323 extern int GCRMinJog; 324 extern int GCREndDist; 325 extern int GCRSteadyNet; 326 extern float GCRObstDist; 327 extern int GCRMinChannelSize; 328 extern bool GcrShowMap; 329 extern bool GcrShowEnd; 330 extern bool GcrShowResult; 331 extern bool GcrNoCheck; 332 extern bool GcrDebug; 333 334 335 /* Procedures exported by the greedy router to the rest of the world: */ 336 337 extern GCRChannel *GCRNewChannel(); 338 extern void GCRFreeChannel(); 339 extern GCRChannel *GCRRouteFromFile(); 340 extern int GCRroute(); 341 extern void GCRFlipLeftRight(); 342 extern void GCRFlipXY(); 343 extern void GCRNoFlip(); 344 extern void GCRShow(); 345 346 #endif /* _GCR_H */ 347