1#----------------------------------------------------------------- 2# mazeroute.tcl 3#----------------------------------------------------------------- 4# Defines procedure "mazeroute <netlist>", requiring a .net file as 5# an argument. Attempts a single-pass maze route of the contents 6# of the netlist. 7#----------------------------------------------------------------- 8 9global Opts 10 11proc mazeroute {netfile} { 12 if [catch {open $netfile r} fnet] { 13 set netname [file rootname $netfile] 14 if [catch {open ${netfile}.net r} fnet] { 15 puts stderr "Can't read netlist file $netfile" 16 return 1; 17 } 18 } 19 # 1st line of the netlist file is throw-away 20 gets $fnet line 21 22 set destnet {} 23 while {[gets $fnet line] >= 0} { 24 if {$line == ""} { 25 set destnet {} 26 } elseif {$destnet == {}} { 27 set destnet $line 28 } else { 29 set startnet $line 30 iroute route -dlabel $destnet -slabel $startnet -timeout 3 31 set destnet $startnet 32 } 33 } 34} 35 36#----------------------------------------------------------------- 37# Interactive mazerouter GUI. Shows a list of nets from the 38# selected netlist. Allows one to select the order of routing, 39# route individual nets, rip up individual nets, etc. 40# 41# This GUI more or less replaces the "specialopen netlist" window. 42#----------------------------------------------------------------- 43 44proc genmazehelper {} { 45 global Opts 46 set Opts(preproutes) 0 47 set Opts(fenced) 0 48 49 if {![catch {wm deiconify .mazehelper ; raise .mazehelper}]} {return} 50 51 toplevel .mazehelper 52 wm protocol .mazehelper WM_DELETE_WINDOW {destroy .mazehelper} 53 54 frame .mazehelper.mazemenu 55 frame .mazehelper.unrouted 56 frame .mazehelper.transfer 57 frame .mazehelper.routed 58 59 pack .mazehelper.mazemenu -side top -anchor w 60 61 button .mazehelper.mazemenu.load -text "Load" -command {loadnetlist} 62 label .mazehelper.mazemenu.netlist -text "(no netlist loaded)" 63 button .mazehelper.mazemenu.fence -text "Fence" -command {buildfence} 64 button .mazehelper.mazemenu.sort -text "Sort" -command {sortnets} 65 button .mazehelper.mazemenu.params -text "Params" -command {genmazeparams} 66 67 pack .mazehelper.mazemenu.load -side left 68 pack .mazehelper.mazemenu.netlist -side left -fill x -expand true 69 pack .mazehelper.mazemenu.fence -side left 70 pack .mazehelper.mazemenu.sort -side left 71 pack .mazehelper.mazemenu.params -side left 72 73 label .mazehelper.unrouted.title -text "Unrouted:" 74 listbox .mazehelper.unrouted.contents -background white -selectmode extended 75 76 label .mazehelper.routed.title -text "Routed:" 77 listbox .mazehelper.routed.contents -background white -selectmode extended 78 79 button .mazehelper.transfer.ripup -text "<--" -command {ripupnet} 80 button .mazehelper.transfer.route -text "-->" -command {routenet} 81 82 pack .mazehelper.transfer.ripup -side top 83 pack .mazehelper.transfer.route -side top 84 85 pack .mazehelper.unrouted.title -side top 86 pack .mazehelper.unrouted.contents -side top -fill both -expand true 87 88 pack .mazehelper.routed.title -side top 89 pack .mazehelper.routed.contents -side top -fill both -expand true 90 91 pack .mazehelper.unrouted -side left -fill both -expand true 92 pack .mazehelper.transfer -side left 93 pack .mazehelper.routed -side left -fill both -expand true 94 95} 96 97#----------------------------------------------------------------- 98# Route parameters (to be completed) 99#----------------------------------------------------------------- 100 101proc genmazeparams {} { 102 global Opts 103 104 if {![catch {wm deiconify .mazeparams ; raise .mazeparams}]} {return} 105 106 toplevel .mazeparams 107 wm protocol .mazeparams WM_DELETE_WINDOW {destroy .mazeparams} 108 109 set routeparams {layer active width hCost vCost jogCost hintCost overCost} 110 set curRparams [iroute layers -list] 111 112 set contparams {contact active width cost} 113 set curCparams [iroute contact -list] 114 115 set k 0 116 label .mazeparams.t1 -text "Layer" 117 label .mazeparams.t2 -text "Active" 118 label .mazeparams.t3 -text "Width" 119 label .mazeparams.t4 -text "Horizontal Cost" 120 label .mazeparams.t5 -text "Vertical Cost" 121 label .mazeparams.t6 -text "Jog Cost" 122 label .mazeparams.t7 -text "Hint Cost" 123 label .mazeparams.t8 -text "Overroute Cost" 124 foreach layer $curRparams { 125 incr k 126 label .mazeparams.r${k}0 -text [lindex $layer 0] 127 checkbox .mazeparams.r${k}1 128 for {set j 2} {$j < 8} {incr j} { 129 entry .mazeparams.r${k}${j} -text [lindex $contact $j] 130 } 131 } 132 incr k 133 label .mazeparams.t1 -text "Contact" 134 label .mazeparams.t2 -text "Active" 135 label .mazeparams.t3 -text "Size" 136 label .mazeparams.t4 -text "Cost" 137 foreach contact $curCparams { 138 incr k 139 label .mazeparams.r${k}0 -text [lindex $contact 0] 140 checkbox .mazeparams.r${k}1 141 for {set j 2} {$j < 4} {incr j} { 142 entry .mazeparams.r${k}${j} -text [lindex $contact $j] 143 } 144 } 145} 146 147#----------------------------------------------------------------- 148# Load a magic-style netlist 149#----------------------------------------------------------------- 150 151proc loadnetlist { {netfile {}} } { 152 global Opts 153 154 if {$netfile == {}} { 155 set netfile [ tk_getOpenFile -filetypes \ 156 {{NET {.net {.net}}} {"All files" {*}}}] 157 } 158 159 if [catch {open $netfile r} fnet] { 160 set netname [file rootname $netfile] 161 if [catch {open ${netfile}.net r} fnet] { 162 puts stderr "Can't read netlist file $netfile" 163 return 1; 164 } 165 } 166 167 # Clear out the listbox contents. 168 .mazehelper.unrouted.contents delete 0 end 169 .mazehelper.routed.contents delete 0 end 170 set $Opts(preproutes) 0 171 172 # 1st line of the netlist file is throw-away 173 gets $fnet line 174 175 set currentnet {} 176 while {[gets $fnet line] >= 0} { 177 if {$line == ""} { 178 if {[llength $currentnet] > 0} { 179 .mazehelper.unrouted.contents insert end $currentnet 180 set currentnet {} 181 } 182 } else { 183 lappend currentnet $line 184 } 185 } 186 187 # Make sure final net gets added. . . 188 189 if {[llength $currentnet] > 0} { 190 .mazehelper.unrouted.contents insert end $currentnet 191 } 192 193 .mazehelper.mazemenu.netlist configure -text [file tail $netfile] 194 195 # Verify all unrouted nets (check if any are already routed) 196 197 .mazehelper.unrouted.contents select set 0 end 198 verifynet unrouted quiet 199 .mazehelper.unrouted.contents select clear 0 end 200 201 close $fnet 202} 203 204#----------------------------------------------------------------- 205# Place a contact on each network endpoint. Aids in preventing 206# the router from routing over pins by blocking access to the 207# space over every pin that will be routed to. 208# 209# Changed 9/25/06---contact only in subcells. 210# Changed 9/26/06---use obstruction layer, not contacts 211#----------------------------------------------------------------- 212 213proc obstructendpoints {} { 214 global Opts 215 set Opts(preproutes) 1 216 217 box values 0 0 0 0 218 foreach net [.mazehelper.unrouted.contents get 0 end] { 219 foreach endpoint $net { 220 set layer [goto $endpoint] 221 # Ignore via layers; these are already obstructed for our purposes. 222 if {[string first metal $layer] == 0} { 223 set lnum [string range $layer 5 end] 224 incr lnum 225 set obslayer obsm${lnum} 226 set viasize [tech drc width m${lnum}c] 227 228 box size ${viasize}i ${viasize}i 229 paint $obslayer 230 } 231 } 232 } 233} 234 235#----------------------------------------------------------------- 236# Free the obstruction above endpoints for each endpoint in the 237# current network. 238#----------------------------------------------------------------- 239 240proc freeendpoints {net} { 241 box values 0 0 0 0 242 foreach endpoint $net { 243 if {[string first / $endpoint] > 0} { 244 set layer [goto $endpoint] 245 if {[string first metal $layer] == 0} { 246 set lnum [string range $layer 5 end] 247 incr lnum 248 set obslayer obsm${lnum} 249 set viasize [tech drc width m${lnum}c] 250 box size ${viasize}i ${viasize}i 251 erase $obslayer 252 } 253 } 254 } 255} 256 257#----------------------------------------------------------------- 258# Free the obstruction above each pin in the current network. 259#----------------------------------------------------------------- 260 261proc freepinobstructions {net} { 262 box values 0 0 0 0 263 foreach endpoint $net { 264 if {[string first / $endpoint] <= 0} { 265 set layer [goto $endpoint] 266 if {[string first metal $layer] == 0} { 267 set lnum [string range $layer 5 end] 268 incr lnum 269 set obslayer obsm${lnum} 270 set viasize [tech drc width m${lnum}c] 271 box size ${viasize}i ${viasize}i 272 erase $obslayer 273 } 274 } 275 } 276} 277 278#----------------------------------------------------------------- 279# Sorting routine for two pins---sort by leftmost pin position. 280#----------------------------------------------------------------- 281 282proc sortpinslr {pina pinb} { 283 goto $pina 284 set xa [lindex [box values] 0] 285 goto $pinb 286 set xb [lindex [box values] 0] 287 if {$xa > $xb} {return 1} else {return -1} 288} 289 290#----------------------------------------------------------------- 291# Sort a net so that the endpoints are ordered left to right 292#----------------------------------------------------------------- 293 294proc sortnetslr {} { 295 set allnets [.mazehelper.unrouted.contents get 0 end] 296 .mazehelper.unrouted.contents delete 0 end 297 magic::suspendall 298 foreach net $allnets { 299 set netafter [lsort -command sortpinslr $net] 300 .mazehelper.unrouted.contents insert 0 $netafter 301 } 302 magic::resumeall 303} 304 305#----------------------------------------------------------------- 306# Procedure to find the leftmost point of a net. 307#----------------------------------------------------------------- 308 309proc getnetleft {net} { 310 foreach endpoint $net { 311 set layer [goto $endpoint] 312 set xtest [lindex [box values] 0] 313 if [catch {if {$xtest < $xmin} {set xmin $xtest}}] {set xmin $xtest} 314 } 315 return $xmin 316} 317 318#----------------------------------------------------------------- 319# Procedure to compare nets according to the number of nodes 320#----------------------------------------------------------------- 321 322proc routecomp {a b} { 323 set alen [llength $a] 324 set blen [llength $b] 325 if {$alen > $blen} { 326 return -1 327 } elseif {$alen < $blen} { 328 return 1 329 } else { 330 # Sort by leftmost route. 331 set aleft [getnetleft $a] 332 set bleft [getnetleft $b] 333 if {$aleft > $bleft} {return 1} else {return -1} 334 } 335} 336 337#----------------------------------------------------------------- 338# Sort unrouted nets from longest to shortest 339#----------------------------------------------------------------- 340 341proc sortnets {} { 342 set listbefore [.mazehelper.unrouted.contents get 0 end] 343 .mazehelper.unrouted.contents delete 0 end 344 magic::suspendall 345 set listafter [lsort -command routecomp $listbefore] 346 foreach net $listafter { 347 .mazehelper.unrouted.contents insert end $net 348 } 349 magic::resumeall 350} 351 352#----------------------------------------------------------------- 353# Disassemble all networks into 2-point routes 354#----------------------------------------------------------------- 355 356proc disassemble {} { 357 set allnets [.mazehelper.unrouted.contents get 0 end] 358 .mazehelper.unrouted.contents delete 0 end 359 foreach net $allnets { 360 for {set i 1} {$i < [llength $net]} {incr i} { 361 set j $i 362 incr j -1 363 set newnet [lrange $net $j $i] 364 .mazehelper.unrouted.contents insert end $newnet 365 } 366 } 367} 368 369#----------------------------------------------------------------- 370# Fence the area around the cell 371#----------------------------------------------------------------- 372 373proc buildfence {} { 374 global Opts 375 376 pushbox 377 if {$Opts(fenced) == 0} { 378 select top cell 379 box grow c 1i 380 set ibounds [box values] 381 set illx [lindex $ibounds 0] 382 set illy [lindex $ibounds 1] 383 set iurx [lindex $ibounds 2] 384 set iury [lindex $ibounds 3] 385 box grow c 10i 386 set obounds [box values] 387 set ollx [lindex $obounds 0] 388 set olly [lindex $obounds 1] 389 set ourx [lindex $obounds 2] 390 set oury [lindex $obounds 3] 391 box values ${ollx}i ${iury}i ${ourx}i ${oury}i 392 paint fence 393 box values ${ollx}i ${olly}i ${ourx}i ${illy}i 394 paint fence 395 box values ${ollx}i ${olly}i ${illx}i ${oury}i 396 paint fence 397 box values ${iurx}i ${olly}i ${ourx}i ${oury}i 398 paint fence 399 set Opts(fenced) 1 400 } else { 401 select top cell 402 box grow c 12i 403 erase fence 404 set Opts(fenced) 0 405 } 406 popbox 407} 408 409#----------------------------------------------------------------- 410# Load a list of failed routes 411#----------------------------------------------------------------- 412 413proc loadfailed { {netfile {}} } { 414 415 if {$netfile == {}} { 416 set netfile [ tk_getOpenFile -filetypes \ 417 {{FAILED {.failed {.failed}}} {"All files" {*}}}] 418 } 419 420 if [catch {open $netfile r} fnet] { 421 set netname [file rootname $netfile] 422 if [catch {open ${netfile}.failed r} fnet] { 423 puts stderr "Can't read file of failed routes $netfile" 424 return 1; 425 } 426 } 427 428 # Clear out the listbox contents. 429 .mazehelper.unrouted.contents delete 0 end 430 .mazehelper.routed.contents delete 0 end 431 432 433 # Read each line into the "unrouted" list. 434 while {[gets $fnet line] >= 0} { 435 .mazehelper.unrouted.contents insert end $line 436 } 437 438 .mazehelper.mazemenu.netlist configure -text $netfile 439 440 close $fnet 441} 442 443#----------------------------------------------------------------- 444# Save the list of failed routes 445#----------------------------------------------------------------- 446 447proc savefailed { {netfile {}} } { 448 449 set netfile [.mazehelper.mazemenu.netlist cget -text] 450 if {$netfile == {}} { 451 set netfile [ tk_getOpenFile -filetypes \ 452 {{FAILED {.failed {.failed}}} {"All files" {*}}}] 453 } else { 454 set netname [file rootname $netfile] 455 set netname ${netname}.failed 456 } 457 458 if [catch {open $netfile w} fnet] { 459 set netname [file rootname $netfile] 460 if [catch {open ${netfile}.failed w} fnet] { 461 puts stderr "Can't write file of failed routes $netfile" 462 return 1; 463 } 464 } 465 466 foreach net [.mazehelper.unrouted.contents get 0 end] { 467 puts $fnet "$net" 468 } 469 470 close $fnet 471} 472 473#----------------------------------------------------------------- 474# Get the selected network and maze route it 475#----------------------------------------------------------------- 476 477proc routenet {} { 478 global Opts 479 480 set drcstate [drc status] 481 drc off 482 483 # Prepare routes by placing an obstruction layer on each pin 484 # Only do this if we have defined obstruction layers! 485 486 if {$Opts(preproutes) == 0} { 487 set allLayers [tech layers *] 488 if {[lsearch $allLayers obs*] >= 0} { 489 magic::suspendall 490 obstructendpoints 491 magic::resumeall 492 } 493 } 494 495 set unroutable {} 496 set sellist [.mazehelper.unrouted.contents curselection] 497 set startidx [lindex $sellist 0] 498 while {[llength $sellist] > 0} { 499 set cidx [lindex $sellist 0] 500 set rlist [.mazehelper.unrouted.contents get $cidx] 501 if {$Opts(preproutes) == 1} {freeendpoints $rlist} 502 for {set i 1} {$i < [llength $rlist]} {incr i} { 503 set j $i 504 incr j -1 505 set startnet [lindex $rlist $j] 506 set destnet [lindex $rlist $i] 507 set rresult [iroute route -slabel $startnet -dlabel $destnet -timeout 3] 508 509 # break on any failure 510 if {$rresult != "Route success" && \ 511 $rresult != "Route best before interrupt" && \ 512 $rresult != "Route already routed"} { 513 break 514 } else { 515 set rresult "success" 516 } 517 } 518 519 .mazehelper.unrouted.contents delete $cidx $cidx 520 if {$rresult == "success"} { 521 .mazehelper.routed.contents insert end $rlist 522 } else { 523 # scramble list; we may have better luck routing in a different order 524 set rfirst [lindex $rlist 0] 525 set rlist [lrange $rlist 1 end] 526 lappend rlist $rfirst 527 lappend unroutable $rlist 528 } 529 set sellist [.mazehelper.unrouted.contents curselection] 530 if {$Opts(preproutes) == 1} {freepinobstructions $rlist} 531 } 532 .mazehelper.unrouted.contents selection set $startidx 533 foreach badnet $unroutable { 534 .mazehelper.unrouted.contents insert $startidx $badnet 535 } 536 537 if {$drcstate == 1} {drc on} 538} 539 540#----------------------------------------------------------------- 541# Get the selected network and remove it 542#----------------------------------------------------------------- 543 544proc ripupnet {} { 545 set sellist [.mazehelper.routed.contents curselection] 546 set startidx [lindex $sellist 0] 547 while {[llength $sellist] > 0} { 548 set cidx [lindex $sellist 0] 549 set rlist [.mazehelper.routed.contents get $cidx] 550 set netname [lindex $rlist 0] 551 select clear 552 set layertype [goto $netname] 553 select more box ${layertype},connect ;# chunk 554 select more box ${layertype},connect ;# region 555 select more box ${layertype},connect ;# net 556 delete 557 558 .mazehelper.routed.contents delete $cidx $cidx 559 .mazehelper.unrouted.contents insert end $rlist 560 561 set sellist [.mazehelper.routed.contents curselection] 562 } 563 .mazehelper.routed.contents selection set $startidx 564} 565 566#----------------------------------------------------------------- 567# Get the selected network and verify the route 568#----------------------------------------------------------------- 569 570proc verifynet { {column routed} {infolevel verbose} } { 571 set sellist [.mazehelper.${column}.contents curselection] 572 set startidx [lindex $sellist 0] 573 magic::suspendall 574 while {$sellist != {}} { 575 set cidx [lindex $sellist 0] 576 set errors 0 577 set rlist [.mazehelper.${column}.contents get $cidx] 578 set netname [lindex $rlist 0] 579 select clear 580 set layertype [goto $netname] 581 if {$layertype == {}} { 582 incr errors 583 } else { 584 select more box ${layertype},connect ;# chunk 585 select more box ${layertype},connect ;# region 586 select more box ${layertype},connect ;# net 587 set sellist [what -list] 588 set sellabels [lindex $sellist 1] 589 set labellist {} 590 foreach label $sellabels { 591 set labtext [lindex $label 0] 592 set labinst [lindex $label 2] 593 if {$labinst == {}} { 594 set labname ${labtext} 595 } else { 596 set labname ${labinst}/${labtext} 597 } 598 lappend labellist $labname 599 } 600 601 # Backslash substitute brackets prior to using lsearch, or this won't work 602 # on such labels. Hopefully this won't confuse things. . . 603 set newrlist [string map {\[ < \] >} $rlist] 604 set newlabellist [string map {\[ < \] >} $labellist] 605 606 # Compare labellist to rlist---they are supposed to be the same! 607 608 foreach entry $newlabellist { 609 if {[lsearch $newrlist $entry] < 0} { 610 if {"$infolevel" == "verbose"} { 611 puts stderr "ERROR: Net entry $entry in layout is not in the netlist!" 612 } 613 incr errors 614 } 615 } 616 foreach entry $newrlist { 617 if {[lsearch $newlabellist $entry] < 0} { 618 if {"$infolevel" == "verbose"} { 619 puts stderr "ERROR: Net entry $entry in netlist is not in the layout!" 620 } 621 incr errors 622 } 623 } 624 if {$errors == 0 && "$infolevel" == "verbose"} {puts stdout "VERIFIED"} 625 } 626 627 # If column is "routed" and we're not verified, move to "unrouted". 628 # If column is "unrouted" and we're verified, move to "routed". 629 630 if {"$column" == "routed"} { 631 if {$errors > 0} { 632 .mazehelper.routed.contents delete $cidx $cidx 633 .mazehelper.unrouted.contents insert end $rlist 634 } else { 635 .mazehelper.routed.contents selection clear $cidx 636 incr startidx 637 } 638 } else { 639 if {$errors == 0} { 640 .mazehelper.unrouted.contents delete $cidx $cidx 641 .mazehelper.routed.contents insert end $rlist 642 } else { 643 .mazehelper.unrouted.contents selection clear $cidx 644 incr startidx 645 } 646 } 647 648 # Get the selection list again 649 set sellist [.mazehelper.${column}.contents curselection] 650 } 651 magic::resumeall 652 .mazehelper.${column}.contents selection set $startidx 653} 654 655#----------------------------------------------------------------- 656# Reset the maze helper, deleting all routes. 657#----------------------------------------------------------------- 658 659proc resetmazehelper {} { 660 .mazehelper.routed.contents delete 0 end 661 .mazehelper.unrouted.contents delete 0 end 662} 663 664#----------------------------------------------------------------- 665# Add the "mazehelper" function to the Magic Options 666#----------------------------------------------------------------- 667 668proc addmazehelper {optmenu} { 669 global Opts 670 $optmenu add check -label "Maze Router" -variable Opts(mazeroute) -command \ 671 {if {$Opts(mazeroute) == 0} {destroy .mazehelper} else {genmazehelper}} 672} 673 674#----------------------------------------------------------------- 675 676