1 // Derived from Inferno utils/6c/peep.c 2 // http://code.google.com/p/inferno-os/source/browse/utils/6c/peep.c 3 // 4 // Copyright 1994-1999 Lucent Technologies Inc. All rights reserved. 5 // Portions Copyright 1995-1997 C H Forsyth (forsyth (a] terzarima.net) 6 // Portions Copyright 1997-1999 Vita Nuova Limited 7 // Portions Copyright 2000-2007 Vita Nuova Holdings Limited (www.vitanuova.com) 8 // Portions Copyright 2004,2006 Bruce Ellis 9 // Portions Copyright 2005-2007 C H Forsyth (forsyth (a] terzarima.net) 10 // Revisions Copyright 2000-2007 Lucent Technologies Inc. and others 11 // Portions Copyright 2009 The Go Authors. All rights reserved. 12 // 13 // Permission is hereby granted, free of charge, to any person obtaining a copy 14 // of this software and associated documentation files (the "Software"), to deal 15 // in the Software without restriction, including without limitation the rights 16 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 17 // copies of the Software, and to permit persons to whom the Software is 18 // furnished to do so, subject to the following conditions: 19 // 20 // The above copyright notice and this permission notice shall be included in 21 // all copies or substantial portions of the Software. 22 // 23 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 24 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 25 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 26 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 27 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 28 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 29 // THE SOFTWARE. 30 31 package x86 32 33 import ( 34 "cmd/compile/internal/gc" 35 "cmd/internal/obj" 36 "cmd/internal/obj/x86" 37 "fmt" 38 ) 39 40 const ( 41 REGEXT = 0 42 exregoffset = x86.REG_DI 43 ) 44 45 var gactive uint32 46 47 // do we need the carry bit 48 func needc(p *obj.Prog) bool { 49 for p != nil { 50 if p.Info.Flags&gc.UseCarry != 0 { 51 return true 52 } 53 if p.Info.Flags&(gc.SetCarry|gc.KillCarry) != 0 { 54 return false 55 } 56 p = p.Link 57 } 58 59 return false 60 } 61 62 func rnops(r *gc.Flow) *gc.Flow { 63 if r != nil { 64 var p *obj.Prog 65 var r1 *gc.Flow 66 for { 67 p = r.Prog 68 if p.As != obj.ANOP || p.From.Type != obj.TYPE_NONE || p.To.Type != obj.TYPE_NONE { 69 break 70 } 71 r1 = gc.Uniqs(r) 72 if r1 == nil { 73 break 74 } 75 r = r1 76 } 77 } 78 79 return r 80 } 81 82 func peep(firstp *obj.Prog) { 83 g := gc.Flowstart(firstp, nil) 84 if g == nil { 85 return 86 } 87 gactive = 0 88 89 // byte, word arithmetic elimination. 90 elimshortmov(g) 91 92 // constant propagation 93 // find MOV $con,R followed by 94 // another MOV $con,R without 95 // setting R in the interim 96 var p *obj.Prog 97 for r := g.Start; r != nil; r = r.Link { 98 p = r.Prog 99 switch p.As { 100 case x86.ALEAL: 101 if regtyp(&p.To) { 102 if p.From.Sym != nil { 103 if p.From.Index == x86.REG_NONE { 104 conprop(r) 105 } 106 } 107 } 108 109 case x86.AMOVB, 110 x86.AMOVW, 111 x86.AMOVL, 112 x86.AMOVSS, 113 x86.AMOVSD: 114 if regtyp(&p.To) { 115 if p.From.Type == obj.TYPE_CONST || p.From.Type == obj.TYPE_FCONST { 116 conprop(r) 117 } 118 } 119 } 120 } 121 122 var r1 *gc.Flow 123 var p1 *obj.Prog 124 var r *gc.Flow 125 var t int 126 loop1: 127 if gc.Debug['P'] != 0 && gc.Debug['v'] != 0 { 128 gc.Dumpit("loop1", g.Start, 0) 129 } 130 131 t = 0 132 for r = g.Start; r != nil; r = r.Link { 133 p = r.Prog 134 switch p.As { 135 case x86.AMOVL, 136 x86.AMOVSS, 137 x86.AMOVSD: 138 if regtyp(&p.To) { 139 if regtyp(&p.From) { 140 if copyprop(g, r) { 141 excise(r) 142 t++ 143 } else if subprop(r) && copyprop(g, r) { 144 excise(r) 145 t++ 146 } 147 } 148 } 149 150 case x86.AMOVBLZX, 151 x86.AMOVWLZX, 152 x86.AMOVBLSX, 153 x86.AMOVWLSX: 154 if regtyp(&p.To) { 155 r1 = rnops(gc.Uniqs(r)) 156 if r1 != nil { 157 p1 = r1.Prog 158 if p.As == p1.As && p.To.Type == p1.From.Type && p.To.Reg == p1.From.Reg { 159 p1.As = x86.AMOVL 160 t++ 161 } 162 } 163 } 164 165 case x86.AADDL, 166 x86.AADDW: 167 if p.From.Type != obj.TYPE_CONST || needc(p.Link) { 168 break 169 } 170 if p.From.Offset == -1 { 171 if p.As == x86.AADDL { 172 p.As = x86.ADECL 173 } else { 174 p.As = x86.ADECW 175 } 176 p.From = obj.Addr{} 177 break 178 } 179 180 if p.From.Offset == 1 { 181 if p.As == x86.AADDL { 182 p.As = x86.AINCL 183 } else { 184 p.As = x86.AINCW 185 } 186 p.From = obj.Addr{} 187 break 188 } 189 190 case x86.ASUBL, 191 x86.ASUBW: 192 if p.From.Type != obj.TYPE_CONST || needc(p.Link) { 193 break 194 } 195 if p.From.Offset == -1 { 196 if p.As == x86.ASUBL { 197 p.As = x86.AINCL 198 } else { 199 p.As = x86.AINCW 200 } 201 p.From = obj.Addr{} 202 break 203 } 204 205 if p.From.Offset == 1 { 206 if p.As == x86.ASUBL { 207 p.As = x86.ADECL 208 } else { 209 p.As = x86.ADECW 210 } 211 p.From = obj.Addr{} 212 break 213 } 214 } 215 } 216 217 if t != 0 { 218 goto loop1 219 } 220 221 // MOVSD removal. 222 // We never use packed registers, so a MOVSD between registers 223 // can be replaced by MOVAPD, which moves the pair of float64s 224 // instead of just the lower one. We only use the lower one, but 225 // the processor can do better if we do moves using both. 226 for r := g.Start; r != nil; r = r.Link { 227 p = r.Prog 228 if p.As == x86.AMOVSD { 229 if regtyp(&p.From) { 230 if regtyp(&p.To) { 231 p.As = x86.AMOVAPD 232 } 233 } 234 } 235 } 236 237 gc.Flowend(g) 238 } 239 240 func excise(r *gc.Flow) { 241 p := r.Prog 242 if gc.Debug['P'] != 0 && gc.Debug['v'] != 0 { 243 fmt.Printf("%v ===delete===\n", p) 244 } 245 246 obj.Nopout(p) 247 248 gc.Ostats.Ndelmov++ 249 } 250 251 func regtyp(a *obj.Addr) bool { 252 return a.Type == obj.TYPE_REG && (x86.REG_AX <= a.Reg && a.Reg <= x86.REG_DI || x86.REG_X0 <= a.Reg && a.Reg <= x86.REG_X7) 253 } 254 255 // movb elimination. 256 // movb is simulated by the linker 257 // when a register other than ax, bx, cx, dx 258 // is used, so rewrite to other instructions 259 // when possible. a movb into a register 260 // can smash the entire 64-bit register without 261 // causing any trouble. 262 func elimshortmov(g *gc.Graph) { 263 var p *obj.Prog 264 265 for r := g.Start; r != nil; r = r.Link { 266 p = r.Prog 267 if regtyp(&p.To) { 268 switch p.As { 269 case x86.AINCB, 270 x86.AINCW: 271 p.As = x86.AINCL 272 273 case x86.ADECB, 274 x86.ADECW: 275 p.As = x86.ADECL 276 277 case x86.ANEGB, 278 x86.ANEGW: 279 p.As = x86.ANEGL 280 281 case x86.ANOTB, 282 x86.ANOTW: 283 p.As = x86.ANOTL 284 } 285 286 if regtyp(&p.From) || p.From.Type == obj.TYPE_CONST { 287 // move or artihmetic into partial register. 288 // from another register or constant can be movl. 289 // we don't switch to 32-bit arithmetic if it can 290 // change how the carry bit is set (and the carry bit is needed). 291 switch p.As { 292 case x86.AMOVB, 293 x86.AMOVW: 294 p.As = x86.AMOVL 295 296 case x86.AADDB, 297 x86.AADDW: 298 if !needc(p.Link) { 299 p.As = x86.AADDL 300 } 301 302 case x86.ASUBB, 303 x86.ASUBW: 304 if !needc(p.Link) { 305 p.As = x86.ASUBL 306 } 307 308 case x86.AMULB, 309 x86.AMULW: 310 p.As = x86.AMULL 311 312 case x86.AIMULB, 313 x86.AIMULW: 314 p.As = x86.AIMULL 315 316 case x86.AANDB, 317 x86.AANDW: 318 p.As = x86.AANDL 319 320 case x86.AORB, 321 x86.AORW: 322 p.As = x86.AORL 323 324 case x86.AXORB, 325 x86.AXORW: 326 p.As = x86.AXORL 327 328 case x86.ASHLB, 329 x86.ASHLW: 330 p.As = x86.ASHLL 331 } 332 } else { 333 // explicit zero extension 334 switch p.As { 335 case x86.AMOVB: 336 p.As = x86.AMOVBLZX 337 338 case x86.AMOVW: 339 p.As = x86.AMOVWLZX 340 } 341 } 342 } 343 } 344 } 345 346 /* 347 * the idea is to substitute 348 * one register for another 349 * from one MOV to another 350 * MOV a, R0 351 * ADD b, R0 / no use of R1 352 * MOV R0, R1 353 * would be converted to 354 * MOV a, R1 355 * ADD b, R1 356 * MOV R1, R0 357 * hopefully, then the former or latter MOV 358 * will be eliminated by copy propagation. 359 */ 360 func subprop(r0 *gc.Flow) bool { 361 p := r0.Prog 362 v1 := &p.From 363 if !regtyp(v1) { 364 return false 365 } 366 v2 := &p.To 367 if !regtyp(v2) { 368 return false 369 } 370 for r := gc.Uniqp(r0); r != nil; r = gc.Uniqp(r) { 371 if gc.Debug['P'] != 0 && gc.Debug['v'] != 0 { 372 fmt.Printf("\t? %v\n", r.Prog) 373 } 374 if gc.Uniqs(r) == nil { 375 break 376 } 377 p = r.Prog 378 if p.As == obj.AVARDEF || p.As == obj.AVARKILL { 379 continue 380 } 381 if p.Info.Flags&gc.Call != 0 { 382 return false 383 } 384 385 if p.Info.Reguse|p.Info.Regset != 0 { 386 return false 387 } 388 389 if (p.Info.Flags&gc.Move != 0) && (p.Info.Flags&(gc.SizeL|gc.SizeQ|gc.SizeF|gc.SizeD) != 0) && p.To.Type == v1.Type && p.To.Reg == v1.Reg { 390 copysub(&p.To, v1, v2, 1) 391 if gc.Debug['P'] != 0 { 392 fmt.Printf("gotit: %v->%v\n%v", gc.Ctxt.Dconv(v1), gc.Ctxt.Dconv(v2), r.Prog) 393 if p.From.Type == v2.Type && p.From.Reg == v2.Reg { 394 fmt.Printf(" excise") 395 } 396 fmt.Printf("\n") 397 } 398 399 for r = gc.Uniqs(r); r != r0; r = gc.Uniqs(r) { 400 p = r.Prog 401 copysub(&p.From, v1, v2, 1) 402 copysub(&p.To, v1, v2, 1) 403 if gc.Debug['P'] != 0 { 404 fmt.Printf("%v\n", r.Prog) 405 } 406 } 407 408 t := int(v1.Reg) 409 v1.Reg = v2.Reg 410 v2.Reg = int16(t) 411 if gc.Debug['P'] != 0 { 412 fmt.Printf("%v last\n", r.Prog) 413 } 414 return true 415 } 416 417 if copyau(&p.From, v2) || copyau(&p.To, v2) { 418 break 419 } 420 if copysub(&p.From, v1, v2, 0) != 0 || copysub(&p.To, v1, v2, 0) != 0 { 421 break 422 } 423 } 424 425 return false 426 } 427 428 /* 429 * The idea is to remove redundant copies. 430 * v1->v2 F=0 431 * (use v2 s/v2/v1/)* 432 * set v1 F=1 433 * use v2 return fail 434 * ----------------- 435 * v1->v2 F=0 436 * (use v2 s/v2/v1/)* 437 * set v1 F=1 438 * set v2 return success 439 */ 440 func copyprop(g *gc.Graph, r0 *gc.Flow) bool { 441 p := r0.Prog 442 v1 := &p.From 443 v2 := &p.To 444 if copyas(v1, v2) { 445 return true 446 } 447 gactive++ 448 return copy1(v1, v2, r0.S1, 0) 449 } 450 451 func copy1(v1 *obj.Addr, v2 *obj.Addr, r *gc.Flow, f int) bool { 452 if uint32(r.Active) == gactive { 453 if gc.Debug['P'] != 0 { 454 fmt.Printf("act set; return 1\n") 455 } 456 return true 457 } 458 459 r.Active = int32(gactive) 460 if gc.Debug['P'] != 0 { 461 fmt.Printf("copy %v->%v f=%d\n", gc.Ctxt.Dconv(v1), gc.Ctxt.Dconv(v2), f) 462 } 463 var t int 464 var p *obj.Prog 465 for ; r != nil; r = r.S1 { 466 p = r.Prog 467 if gc.Debug['P'] != 0 { 468 fmt.Printf("%v", p) 469 } 470 if f == 0 && gc.Uniqp(r) == nil { 471 f = 1 472 if gc.Debug['P'] != 0 { 473 fmt.Printf("; merge; f=%d", f) 474 } 475 } 476 477 t = copyu(p, v2, nil) 478 switch t { 479 case 2: /* rar, can't split */ 480 if gc.Debug['P'] != 0 { 481 fmt.Printf("; %v rar; return 0\n", gc.Ctxt.Dconv(v2)) 482 } 483 return false 484 485 case 3: /* set */ 486 if gc.Debug['P'] != 0 { 487 fmt.Printf("; %v set; return 1\n", gc.Ctxt.Dconv(v2)) 488 } 489 return true 490 491 case 1, /* used, substitute */ 492 4: /* use and set */ 493 if f != 0 { 494 if gc.Debug['P'] == 0 { 495 return false 496 } 497 if t == 4 { 498 fmt.Printf("; %v used+set and f=%d; return 0\n", gc.Ctxt.Dconv(v2), f) 499 } else { 500 fmt.Printf("; %v used and f=%d; return 0\n", gc.Ctxt.Dconv(v2), f) 501 } 502 return false 503 } 504 505 if copyu(p, v2, v1) != 0 { 506 if gc.Debug['P'] != 0 { 507 fmt.Printf("; sub fail; return 0\n") 508 } 509 return false 510 } 511 512 if gc.Debug['P'] != 0 { 513 fmt.Printf("; sub %v/%v", gc.Ctxt.Dconv(v2), gc.Ctxt.Dconv(v1)) 514 } 515 if t == 4 { 516 if gc.Debug['P'] != 0 { 517 fmt.Printf("; %v used+set; return 1\n", gc.Ctxt.Dconv(v2)) 518 } 519 return true 520 } 521 } 522 523 if f == 0 { 524 t = copyu(p, v1, nil) 525 if f == 0 && (t == 2 || t == 3 || t == 4) { 526 f = 1 527 if gc.Debug['P'] != 0 { 528 fmt.Printf("; %v set and !f; f=%d", gc.Ctxt.Dconv(v1), f) 529 } 530 } 531 } 532 533 if gc.Debug['P'] != 0 { 534 fmt.Printf("\n") 535 } 536 if r.S2 != nil { 537 if !copy1(v1, v2, r.S2, f) { 538 return false 539 } 540 } 541 } 542 543 return true 544 } 545 546 /* 547 * return 548 * 1 if v only used (and substitute), 549 * 2 if read-alter-rewrite 550 * 3 if set 551 * 4 if set and used 552 * 0 otherwise (not touched) 553 */ 554 func copyu(p *obj.Prog, v *obj.Addr, s *obj.Addr) int { 555 switch p.As { 556 case obj.AJMP: 557 if s != nil { 558 if copysub(&p.To, v, s, 1) != 0 { 559 return 1 560 } 561 return 0 562 } 563 564 if copyau(&p.To, v) { 565 return 1 566 } 567 return 0 568 569 case obj.ARET: 570 if s != nil { 571 return 1 572 } 573 return 3 574 575 case obj.ACALL: 576 if REGEXT != 0 /*TypeKind(100016)*/ && v.Type == obj.TYPE_REG && v.Reg <= REGEXT && v.Reg > exregoffset { 577 return 2 578 } 579 if x86.REGARG >= 0 && v.Type == obj.TYPE_REG && v.Reg == x86.REGARG { 580 return 2 581 } 582 if v.Type == p.From.Type && v.Reg == p.From.Reg { 583 return 2 584 } 585 586 if s != nil { 587 if copysub(&p.To, v, s, 1) != 0 { 588 return 1 589 } 590 return 0 591 } 592 593 if copyau(&p.To, v) { 594 return 4 595 } 596 return 3 597 598 case obj.ATEXT: 599 if x86.REGARG >= 0 && v.Type == obj.TYPE_REG && v.Reg == x86.REGARG { 600 return 3 601 } 602 return 0 603 } 604 605 if p.As == obj.AVARDEF || p.As == obj.AVARKILL { 606 return 0 607 } 608 609 if (p.Info.Reguse|p.Info.Regset)&RtoB(int(v.Reg)) != 0 { 610 return 2 611 } 612 613 if p.Info.Flags&gc.LeftAddr != 0 { 614 if copyas(&p.From, v) { 615 return 2 616 } 617 } 618 619 if p.Info.Flags&(gc.RightRead|gc.RightWrite) == gc.RightRead|gc.RightWrite { 620 if copyas(&p.To, v) { 621 return 2 622 } 623 } 624 625 if p.Info.Flags&gc.RightWrite != 0 { 626 if copyas(&p.To, v) { 627 if s != nil { 628 return copysub(&p.From, v, s, 1) 629 } 630 if copyau(&p.From, v) { 631 return 4 632 } 633 return 3 634 } 635 } 636 637 if p.Info.Flags&(gc.LeftAddr|gc.LeftRead|gc.LeftWrite|gc.RightAddr|gc.RightRead|gc.RightWrite) != 0 { 638 if s != nil { 639 if copysub(&p.From, v, s, 1) != 0 { 640 return 1 641 } 642 return copysub(&p.To, v, s, 1) 643 } 644 645 if copyau(&p.From, v) { 646 return 1 647 } 648 if copyau(&p.To, v) { 649 return 1 650 } 651 } 652 653 return 0 654 } 655 656 /* 657 * direct reference, 658 * could be set/use depending on 659 * semantics 660 */ 661 func copyas(a *obj.Addr, v *obj.Addr) bool { 662 if x86.REG_AL <= a.Reg && a.Reg <= x86.REG_BL { 663 gc.Fatal("use of byte register") 664 } 665 if x86.REG_AL <= v.Reg && v.Reg <= x86.REG_BL { 666 gc.Fatal("use of byte register") 667 } 668 669 if a.Type != v.Type || a.Name != v.Name || a.Reg != v.Reg { 670 return false 671 } 672 if regtyp(v) { 673 return true 674 } 675 if (v.Type == obj.TYPE_MEM || v.Type == obj.TYPE_ADDR) && (v.Name == obj.NAME_AUTO || v.Name == obj.NAME_PARAM) { 676 if v.Offset == a.Offset { 677 return true 678 } 679 } 680 return false 681 } 682 683 func sameaddr(a *obj.Addr, v *obj.Addr) bool { 684 if a.Type != v.Type || a.Name != v.Name || a.Reg != v.Reg { 685 return false 686 } 687 if regtyp(v) { 688 return true 689 } 690 if (v.Type == obj.TYPE_MEM || v.Type == obj.TYPE_ADDR) && (v.Name == obj.NAME_AUTO || v.Name == obj.NAME_PARAM) { 691 if v.Offset == a.Offset { 692 return true 693 } 694 } 695 return false 696 } 697 698 /* 699 * either direct or indirect 700 */ 701 func copyau(a *obj.Addr, v *obj.Addr) bool { 702 if copyas(a, v) { 703 return true 704 } 705 if regtyp(v) { 706 if (a.Type == obj.TYPE_MEM || a.Type == obj.TYPE_ADDR) && a.Reg == v.Reg { 707 return true 708 } 709 if a.Index == v.Reg { 710 return true 711 } 712 } 713 714 return false 715 } 716 717 /* 718 * substitute s for v in a 719 * return failure to substitute 720 */ 721 func copysub(a *obj.Addr, v *obj.Addr, s *obj.Addr, f int) int { 722 if copyas(a, v) { 723 reg := int(s.Reg) 724 if reg >= x86.REG_AX && reg <= x86.REG_DI || reg >= x86.REG_X0 && reg <= x86.REG_X7 { 725 if f != 0 { 726 a.Reg = int16(reg) 727 } 728 } 729 730 return 0 731 } 732 733 if regtyp(v) { 734 reg := int(v.Reg) 735 if (a.Type == obj.TYPE_MEM || a.Type == obj.TYPE_ADDR) && int(a.Reg) == reg { 736 if (s.Reg == x86.REG_BP) && a.Index != obj.TYPE_NONE { 737 return 1 /* can't use BP-base with index */ 738 } 739 if f != 0 { 740 a.Reg = s.Reg 741 } 742 } 743 744 // return 0; 745 if int(a.Index) == reg { 746 if f != 0 { 747 a.Index = s.Reg 748 } 749 return 0 750 } 751 752 return 0 753 } 754 755 return 0 756 } 757 758 func conprop(r0 *gc.Flow) { 759 var p *obj.Prog 760 var t int 761 762 p0 := r0.Prog 763 v0 := &p0.To 764 r := r0 765 766 loop: 767 r = gc.Uniqs(r) 768 if r == nil || r == r0 { 769 return 770 } 771 if gc.Uniqp(r) == nil { 772 return 773 } 774 775 p = r.Prog 776 t = copyu(p, v0, nil) 777 switch t { 778 case 0, // miss 779 1: // use 780 goto loop 781 782 case 2, // rar 783 4: // use and set 784 break 785 786 case 3: // set 787 if p.As == p0.As { 788 if p.From.Type == p0.From.Type { 789 if p.From.Reg == p0.From.Reg { 790 if p.From.Node == p0.From.Node { 791 if p.From.Offset == p0.From.Offset { 792 if p.From.Scale == p0.From.Scale { 793 if p.From.Type == obj.TYPE_FCONST && p.From.Val.(float64) == p0.From.Val.(float64) { 794 if p.From.Index == p0.From.Index { 795 excise(r) 796 goto loop 797 } 798 } 799 } 800 } 801 } 802 } 803 } 804 } 805 } 806 } 807 808 func smallindir(a *obj.Addr, reg *obj.Addr) bool { 809 return regtyp(reg) && a.Type == obj.TYPE_MEM && a.Reg == reg.Reg && a.Index == x86.REG_NONE && 0 <= a.Offset && a.Offset < 4096 810 } 811 812 func stackaddr(a *obj.Addr) bool { 813 return a.Type == obj.TYPE_REG && a.Reg == x86.REG_SP 814 } 815
