1
2 /* gcrEdge.c -
3 *
4 * The greedy router:
5 * Functions to make connections at the far end of the channel.
6 *
7 * *********************************************************************
8 * * Copyright (C) 1985, 1990 Regents of the University of California. *
9 * * Permission to use, copy, modify, and distribute this *
10 * * software and its documentation for any purpose and without *
11 * * fee is hereby granted, provided that the above copyright *
12 * * notice appear in all copies. The University of California *
13 * * makes no representations about the suitability of this *
14 * * software for any purpose. It is provided "as is" without *
15 * * express or implied warranty. Export of this software outside *
16 * * of the United States of America may require an export license. *
17 * *********************************************************************
18 */
19
20 #ifndef lint
21 static char rcsid[] __attribute__ ((unused)) = "$Header: /usr/cvsroot/magic-8.0/gcr/gcrEdge.c,v 1.1.1.1 2008/02/03 20:43:50 tim Exp $";
22 #endif /* not lint */
23
24 #include <stdio.h>
25
26 #include "utils/magic.h"
27 #include "utils/geometry.h"
28 #include "tiles/tile.h"
29 #include "gcr/gcr.h"
30
31 /*
32 * ----------------------------------------------------------------------------
33 *
34 * gcrWanted --
35 *
36 * Reserve tracks needed to make connections at the end of the channel
37 * for net occupying track. Net must be unsplit. If very close then
38 * reserve all tracks needed by net; otherwise just 1.
39 *
40 * Results:
41 * None.
42 *
43 * Side effects:
44 * Mark the desired tracks for such nets as "wanted" by that net.
45 *
46 * ----------------------------------------------------------------------------
47 */
48
49 void
gcrWanted(ch,track,column)50 gcrWanted(ch, track, column)
51 GCRChannel *ch;
52 int track, column;
53 {
54 GCRColEl *col = ch->gcr_lCol;
55 GCRPin *pin, *next;
56 GCRNet *net;
57
58 net = col[track].gcr_h;
59 if (net == (GCRNet *) NULL)
60 return;
61
62 /* Done if the net is split */
63 if (col[track].gcr_hi != EMPTY || col[track].gcr_lo != EMPTY)
64 return;
65
66 /* Done if no pins */
67 pin = GCRPin1st(net);
68 if (pin == (GCRPin *) NULL)
69 return;
70
71 /* Done if interior pin */
72 if (pin->gcr_x != ch->gcr_length + 1)
73 return;
74
75 next = GCRPinNext(pin);
76 if (next == (GCRPin *) NULL) col[pin->gcr_y].gcr_wanted = net;
77 else if (GCRNearEnd(ch, column))
78 {
79 for (col[pin->gcr_y].gcr_wanted = net; next; next = GCRPinNext(next))
80 col[next->gcr_y].gcr_wanted = net;
81 }
82 }
83
84 /*
85 * ----------------------------------------------------------------------------
86 *
87 * gcrMarkWanted --
88 *
89 * Mark tracks near the end of the channel that are wanted to make some
90 * connection at the end of the channel.
91 *
92 * Results:
93 * None.
94 *
95 * Side effects:
96 * Changes the wanted field in column elements.
97 *
98 * ----------------------------------------------------------------------------
99 */
100
101 void
gcrMarkWanted(ch)102 gcrMarkWanted(ch)
103 GCRChannel *ch;
104 {
105 GCRColEl *col = ch->gcr_lCol;
106 GCRPin *pin = ch->gcr_rPins;
107 int track;
108
109 for (track = 1; track <= ch->gcr_width; track++)
110 if (pin[track].gcr_pId)
111 col[track].gcr_wanted = pin[track].gcr_pId;
112 }
113
114 /*
115 * ----------------------------------------------------------------------------
116 *
117 * gcrUncollapse --
118 *
119 * Add vertical segments to this column to split nets making more than
120 * one connection at the end of the channel. Pick a pattern that will
121 * create the most split. Generate all legal combinations and pick the
122 * best. This differs from gcrCollapse in that there are no links
123 * between tracks to be followed.
124 *
125 * Results:
126 * None.
127 *
128 * Side effects:
129 * If the evaluated column is the best seen, then gcrEvalPat saves it
130 * away. In any event, gcrEvalPat sets its col argument to NULL.
131 *
132 * ----------------------------------------------------------------------------
133 */
134
135 void
gcrUncollapse(ch,col,width,bot,top,split)136 gcrUncollapse(ch, col, width, bot, top, split)
137 GCRChannel *ch; /* Channel being processed */
138 GCRColEl **col;
139 int width; /* Size of array pointed to by *col */
140 int bot, top; /* Consider tracks between bot .. top inclusive */
141 int split; /* Somewhere between 0 and width inclusive */
142 {
143 int i, to, type, extra, flags;
144 GCRColEl *newCol, *gcrCopyCol();
145 GCRNet *net, *hnet;
146
147 ASSERT(split <= width, "gcrUncollapse.");
148 for (i = bot; i <= top; i++)
149 {
150 /*
151 * If the track is free but needs to get assigned a net for
152 * a right edge connection...
153 */
154 net = (*col)[i].gcr_h;
155 if (net == (GCRNet *) NULL
156 && (*col)[i].gcr_wanted
157 && ((*col)[i].gcr_v == (GCRNet *) NULL
158 || (*col)[i].gcr_v == net))
159 {
160 /*
161 * Look upwards for the next track that is either assigned to
162 * the net or wants to get assigned the net. If blocked
163 * vertically then give up. If found, weight the worth of
164 * the potential connection.
165 */
166 for (to = i + 1; to <= width; to++)
167 {
168 flags = (*col)[to].gcr_flags;
169 hnet = (*col)[to].gcr_h;
170
171 /*
172 * Abort if blocked. The last argument indicates that it is
173 * okay to stop at this location only if this location holds
174 * the net to which (*col)[i] wants to connect.
175 */
176 if (gcrBlocked(*col, to, net, hnet != (*col)[i].gcr_wanted))
177 {
178 to = width + 1;
179 break;
180 }
181 else if (hnet == (*col)[i].gcr_wanted)
182 {
183 /* Connect to a track already assigned to the net. */
184 type = 1;
185 extra = 2;
186 break;
187 }
188 else if ((*col)[to].gcr_wanted == (*col)[i].gcr_wanted
189 && hnet == (GCRNet *) NULL)
190 {
191 /* Connect to another track not yet part of the net. */
192 extra = 1;
193 type = 2;
194 break;
195 }
196 else if (flags & GCRCE)
197 {
198 to = width + 1;
199 break;
200 }
201 }
202 }
203 else if (net)
204 {
205 /*
206 * If the track is assigned to a net and this net has more
207 * connections to make at the end, look upward for the next
208 * track that is empty and wants to connect to this net.
209 * No collapses of split tracks should occur here, since
210 * this function comes after collapsing split nets.
211 */
212 for (to = i + 1; to <= width; to++)
213 {
214 /*
215 * Skip if the track ends in the next column. The last
216 * argument indicates that it is okay to stop here if
217 * this location wants to get hooked up to "net".
218 */
219 flags = (*col)[to].gcr_flags;
220 if (gcrBlocked(*col, to, net, net == (*col)[to].gcr_wanted))
221 {
222 to = width + 1;
223 break;
224 }
225 else if( (*col)[to].gcr_wanted == net
226 && (*col)[to].gcr_h == (GCRNet *) NULL)
227 {
228 /*
229 * Link track "i" (already assigned to the net) to
230 * track "to" (track being uncollapsed).
231 */
232 extra = 2;
233 type = 3;
234 break;
235 }
236 else if (flags & GCRCE)
237 {
238 to = width + 1;
239 break;
240 }
241 }
242 }
243 else continue;
244
245 if (to <= width)
246 {
247 /* Found something to connect */
248 newCol = gcrCopyCol( *col, width);
249 switch (type)
250 {
251 case 1:
252 gcrMoveTrack(newCol, net, to, i);
253 break;
254 case 2:
255 net = newCol[to].gcr_wanted;
256 gcrLinkTrack(newCol, net, to, width);
257 gcrMoveTrack(newCol, net, to, i);
258 break;
259 case 3:
260 gcrMoveTrack(newCol, net, i, to);
261 break;
262 }
263
264 ASSERT(i < to, "gcrEdge.c, gcrUncollapse");
265 gcrUncollapse(ch, &newCol, width, to, top, split+extra);
266
267 /* Don't bother to recheck stuff above the last jog */
268 if (top > to) top = to-1;
269 }
270
271 }
272
273 gcrEvalPat(col, split, width);
274 *col = (GCRColEl *) NULL;
275 }
276