1# Copyright (C) 2011, 2012 Apple Inc. All rights reserved. 2# 3# Redistribution and use in source and binary forms, with or without 4# modification, are permitted provided that the following conditions 5# are met: 6# 1. Redistributions of source code must retain the above copyright 7# notice, this list of conditions and the following disclaimer. 8# 2. Redistributions in binary form must reproduce the above copyright 9# notice, this list of conditions and the following disclaimer in the 10# documentation and/or other materials provided with the distribution. 11# 12# THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS'' 13# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, 14# THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 15# PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS 16# BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 17# CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 18# SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 19# INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 20# CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 21# ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF 22# THE POSSIBILITY OF SUCH DAMAGE. 23 24require 'config' 25require 'ast' 26require 'opt' 27 28# This file contains utilities that are useful for implementing a backend 29# for RISC-like processors (ARM, MIPS, etc). 30 31# 32# Lowering of simple branch ops. For example: 33# 34# baddiz foo, bar, baz 35# 36# will become: 37# 38# addi foo, bar 39# bz baz 40# 41 42def riscLowerSimpleBranchOps(list) 43 newList = [] 44 list.each { 45 | node | 46 if node.is_a? Instruction 47 annotation = node.annotation 48 case node.opcode 49 when /^b(addi|subi|ori|addp)/ 50 op = $1 51 branch = "b" + $~.post_match 52 53 case op 54 when "addi" 55 op = "addis" 56 when "addp" 57 op = "addps" 58 when "subi" 59 op = "subis" 60 when "ori" 61 op = "oris" 62 end 63 64 newList << Instruction.new(node.codeOrigin, op, node.operands[0..-2], annotation) 65 newList << Instruction.new(node.codeOrigin, branch, [node.operands[-1]]) 66 when 'bmulis', 'bmulz', 'bmulnz' 67 condition = $~.post_match 68 newList << Instruction.new(node.codeOrigin, "muli", node.operands[0..-2], annotation) 69 newList << Instruction.new(node.codeOrigin, "bti" + condition, [node.operands[-2], node.operands[-1]]) 70 else 71 newList << node 72 end 73 else 74 newList << node 75 end 76 } 77 newList 78end 79 80# 81# Lowing of complex branch ops. For example: 82# 83# bmulio foo, bar, baz 84# 85# becomes: 86# 87# smulli foo, bar, bar, tmp1 88# rshifti bar, 31, tmp2 89# bineq tmp1, tmp2, baz 90# 91 92def riscLowerHardBranchOps(list) 93 newList = [] 94 list.each { 95 | node | 96 if node.is_a? Instruction and node.opcode == "bmulio" 97 tmp1 = Tmp.new(node.codeOrigin, :gpr) 98 tmp2 = Tmp.new(node.codeOrigin, :gpr) 99 newList << Instruction.new(node.codeOrigin, "smulli", [node.operands[0], node.operands[1], node.operands[1], tmp1], node.annotation) 100 newList << Instruction.new(node.codeOrigin, "rshifti", [node.operands[-2], Immediate.new(node.codeOrigin, 31), tmp2]) 101 newList << Instruction.new(node.codeOrigin, "bineq", [tmp1, tmp2, node.operands[-1]]) 102 else 103 newList << node 104 end 105 } 106 newList 107end 108 109# 110# Lowering of shift ops. For example: 111# 112# lshifti foo, bar 113# 114# will become: 115# 116# andi foo, 31, tmp 117# lshifti tmp, bar 118# 119 120def riscSanitizeShift(operand, list) 121 return operand if operand.immediate? 122 123 tmp = Tmp.new(operand.codeOrigin, :gpr) 124 list << Instruction.new(operand.codeOrigin, "andi", [operand, Immediate.new(operand.codeOrigin, 31), tmp]) 125 tmp 126end 127 128def riscLowerShiftOps(list) 129 newList = [] 130 list.each { 131 | node | 132 if node.is_a? Instruction 133 case node.opcode 134 when "lshifti", "rshifti", "urshifti", "lshiftp", "rshiftp", "urshiftp" 135 if node.operands.size == 2 136 newList << Instruction.new(node.codeOrigin, node.opcode, [riscSanitizeShift(node.operands[0], newList), node.operands[1]], node.annotation) 137 else 138 newList << Instruction.new(node.codeOrigin, node.opcode, [node.operands[0], riscSanitizeShift(node.operands[1], newList), node.operands[2]], node.annotation) 139 raise "Wrong number of operands for shift at #{node.codeOriginString}" unless node.operands.size == 3 140 end 141 else 142 newList << node 143 end 144 else 145 newList << node 146 end 147 } 148 newList 149end 150 151# 152# Lowering of malformed addresses. For example: 153# 154# loadp 10000[foo], bar 155# 156# will become: 157# 158# move 10000, tmp 159# addp foo, tmp 160# loadp 0[tmp], bar 161# 162# Note that you use this lowering phase by passing it a block that returns true 163# if you don't want to lower the address, or false if you do. For example to get 164# the effect of the example above, the block would have to say something like: 165# 166# riscLowerMalformedAddresses(thingy) { 167# | node, address | 168# if address.is_a? Address 169# address.offset.value > 1000 170# else 171# true # don't lower anything else, in this example 172# end 173# } 174# 175# See arm.rb for a different example, in which we lower all BaseIndex addresses 176# that have non-zero offset, all Address addresses that have large offsets, and 177# all other addresses (like AbsoluteAddress). 178# 179 180class Node 181 def riscLowerMalformedAddressesRecurse(list, topLevelNode, &block) 182 mapChildren { 183 | subNode | 184 subNode.riscLowerMalformedAddressesRecurse(list, topLevelNode, &block) 185 } 186 end 187end 188 189class Address 190 def riscLowerMalformedAddressesRecurse(list, node, &block) 191 return self if yield node, self 192 193 tmp = Tmp.new(codeOrigin, :gpr) 194 list << Instruction.new(codeOrigin, "move", [offset, tmp]) 195 list << Instruction.new(codeOrigin, "addp", [base, tmp]) 196 Address.new(codeOrigin, tmp, Immediate.new(codeOrigin, 0)) 197 end 198end 199 200class BaseIndex 201 def riscLowerMalformedAddressesRecurse(list, node, &block) 202 return self if yield node, self 203 204 tmp = Tmp.new(codeOrigin, :gpr) 205 list << Instruction.new(codeOrigin, "leap", [BaseIndex.new(codeOrigin, base, index, scale, Immediate.new(codeOrigin, 0)), tmp]) 206 Address.new(codeOrigin, tmp, offset).riscLowerMalformedAddressesRecurse(list, node, &block) 207 end 208end 209 210class AbsoluteAddress 211 def riscLowerMalformedAddressesRecurse(list, node, &block) 212 return self if yield node, self 213 214 tmp = Tmp.new(codeOrigin, :gpr) 215 list << Instruction.new(codeOrigin, "move", [address, tmp]) 216 Address.new(codeOrigin, tmp, Immediate.new(codeOrigin, 0)) 217 end 218end 219 220def riscLowerMalformedAddresses(list, &block) 221 newList = [] 222 list.each { 223 | node | 224 newList << node.riscLowerMalformedAddressesRecurse(newList, node, &block) 225 } 226 newList 227end 228 229# 230# Lowering of malformed addresses in double loads and stores. For example: 231# 232# loadd [foo, bar, 8], baz 233# 234# becomes: 235# 236# leap [foo, bar, 8], tmp 237# loadd [tmp], baz 238# 239 240class Node 241 def riscDoubleAddress(list) 242 self 243 end 244end 245 246class BaseIndex 247 def riscDoubleAddress(list) 248 tmp = Tmp.new(codeOrigin, :gpr) 249 list << Instruction.new(codeOrigin, "leap", [self, tmp]) 250 Address.new(codeOrigin, tmp, Immediate.new(codeOrigin, 0)) 251 end 252end 253 254def riscLowerMalformedAddressesDouble(list) 255 newList = [] 256 list.each { 257 | node | 258 if node.is_a? Instruction 259 case node.opcode 260 when "loadd" 261 newList << Instruction.new(node.codeOrigin, "loadd", [node.operands[0].riscDoubleAddress(newList), node.operands[1]], node.annotation) 262 when "stored" 263 newList << Instruction.new(node.codeOrigin, "stored", [node.operands[0], node.operands[1].riscDoubleAddress(newList)], node.annotation) 264 else 265 newList << node 266 end 267 else 268 newList << node 269 end 270 } 271 newList 272end 273 274# 275# Lowering of misplaced immediates for opcodes in opcodeList. For example, if storei is in opcodeList: 276# 277# storei 0, [foo] 278# 279# will become: 280# 281# move 0, tmp 282# storei tmp, [foo] 283# 284 285def riscLowerMisplacedImmediates(list, opcodeList) 286 newList = [] 287 list.each { 288 | node | 289 if node.is_a? Instruction 290 if opcodeList.include? node.opcode 291 operands = node.operands 292 newOperands = [] 293 operands.each { 294 | operand | 295 if operand.is_a? Immediate 296 tmp = Tmp.new(operand.codeOrigin, :gpr) 297 newList << Instruction.new(operand.codeOrigin, "move", [operand, tmp]) 298 newOperands << tmp 299 else 300 newOperands << operand 301 end 302 } 303 newList << Instruction.new(node.codeOrigin, node.opcode, newOperands, node.annotation) 304 else 305 newList << node 306 end 307 else 308 newList << node 309 end 310 } 311 newList 312end 313 314# 315# Lowering of malformed immediates except when used in a "move" instruction. 316# For example: 317# 318# addp 642641, foo 319# 320# will become: 321# 322# move 642641, tmp 323# addp tmp, foo 324# 325 326class Node 327 def riscLowerMalformedImmediatesRecurse(list, validImmediates) 328 mapChildren { 329 | node | 330 node.riscLowerMalformedImmediatesRecurse(list, validImmediates) 331 } 332 end 333end 334 335class Address 336 def riscLowerMalformedImmediatesRecurse(list, validImmediates) 337 self 338 end 339end 340 341class BaseIndex 342 def riscLowerMalformedImmediatesRecurse(list, validImmediates) 343 self 344 end 345end 346 347class AbsoluteAddress 348 def riscLowerMalformedImmediatesRecurse(list, validImmediates) 349 self 350 end 351end 352 353class Immediate 354 def riscLowerMalformedImmediatesRecurse(list, validImmediates) 355 unless validImmediates.include? value 356 tmp = Tmp.new(codeOrigin, :gpr) 357 list << Instruction.new(codeOrigin, "move", [self, tmp]) 358 tmp 359 else 360 self 361 end 362 end 363end 364 365def riscLowerMalformedImmediates(list, validImmediates) 366 newList = [] 367 list.each { 368 | node | 369 if node.is_a? Instruction 370 annotation = node.annotation 371 case node.opcode 372 when "move" 373 newList << node 374 when "addi", "addp", "addq", "addis", "subi", "subp", "subq", "subis" 375 if node.operands[0].is_a? Immediate and 376 (not validImmediates.include? node.operands[0].value) and 377 validImmediates.include? -node.operands[0].value 378 node.operands.size == 2 379 if node.opcode =~ /add/ 380 newOpcode = "sub" + $~.post_match 381 else 382 newOpcode = "add" + $~.post_match 383 end 384 newList << Instruction.new(node.codeOrigin, newOpcode, 385 [Immediate.new(node.codeOrigin, -node.operands[0].value)] + node.operands[1..-1], 386 annotation) 387 else 388 newList << node.riscLowerMalformedImmediatesRecurse(newList, validImmediates) 389 end 390 when "muli", "mulp", "mulq" 391 if node.operands[0].is_a? Immediate 392 tmp = Tmp.new(codeOrigin, :gpr) 393 newList << Instruction.new(node.codeOrigin, "move", [node.operands[0], tmp], annotation) 394 newList << Instruction.new(node.codeOrigin, node.opcode, [tmp] + node.operands[1..-1]) 395 else 396 newList << node.riscLowerMalformedImmediatesRecurse(newList, validImmediates) 397 end 398 else 399 newList << node.riscLowerMalformedImmediatesRecurse(newList, validImmediates) 400 end 401 else 402 newList << node 403 end 404 } 405 newList 406end 407 408# 409# Lowering of misplaced addresses. For example: 410# 411# addi foo, [bar] 412# 413# will become: 414# 415# loadi [bar], tmp 416# addi foo, tmp 417# storei tmp, [bar] 418# 419# Another example: 420# 421# addi [foo], bar 422# 423# will become: 424# 425# loadi [foo], tmp 426# addi tmp, bar 427# 428 429def riscAsRegister(preList, postList, operand, suffix, needStore) 430 return operand unless operand.address? 431 432 tmp = Tmp.new(operand.codeOrigin, if suffix == "d" then :fpr else :gpr end) 433 preList << Instruction.new(operand.codeOrigin, "load" + suffix, [operand, tmp]) 434 if needStore 435 postList << Instruction.new(operand.codeOrigin, "store" + suffix, [tmp, operand]) 436 end 437 tmp 438end 439 440def riscAsRegisters(preList, postList, operands, suffix) 441 newOperands = [] 442 operands.each_with_index { 443 | operand, index | 444 newOperands << riscAsRegister(preList, postList, operand, suffix, index == operands.size - 1) 445 } 446 newOperands 447end 448 449def riscLowerMisplacedAddresses(list) 450 newList = [] 451 list.each { 452 | node | 453 if node.is_a? Instruction 454 postInstructions = [] 455 annotation = node.annotation 456 case node.opcode 457 when "addi", "addis", "andi", "lshifti", "muli", "negi", "noti", "ori", "oris", 458 "rshifti", "urshifti", "subi", "subis", "xori", /^bi/, /^bti/, /^ci/, /^ti/ 459 newList << Instruction.new(node.codeOrigin, 460 node.opcode, 461 riscAsRegisters(newList, postInstructions, node.operands, "i"), 462 annotation) 463 when "addp", "andp", "lshiftp", "mulp", "negp", "orp", "rshiftp", "urshiftp", 464 "subp", "xorp", /^bp/, /^btp/, /^cp/ 465 newList << Instruction.new(node.codeOrigin, 466 node.opcode, 467 riscAsRegisters(newList, postInstructions, node.operands, "p"), 468 annotation) 469 when "addq", "andq", "lshiftq", "mulq", "negq", "orq", "rshiftq", "urshiftq", 470 "subq", "xorq", /^bq/, /^btq/, /^cq/ 471 newList << Instruction.new(node.codeOrigin, 472 node.opcode, 473 riscAsRegisters(newList, postInstructions, node.operands, "q"), 474 annotation) 475 when "bbeq", "bbneq", "bba", "bbaeq", "bbb", "bbbeq", "btbz", "btbnz", "tbz", "tbnz", 476 "cbeq", "cbneq", "cba", "cbaeq", "cbb", "cbbeq" 477 newList << Instruction.new(node.codeOrigin, 478 node.opcode, 479 riscAsRegisters(newList, postInstructions, node.operands, "b"), 480 annotation) 481 when "bbgt", "bbgteq", "bblt", "bblteq", "btbs", "tbs", "cbgt", "cbgteq", "cblt", "cblteq" 482 newList << Instruction.new(node.codeOrigin, 483 node.opcode, 484 riscAsRegisters(newList, postInstructions, node.operands, "bs"), 485 annotation) 486 when "addd", "divd", "subd", "muld", "sqrtd", /^bd/ 487 newList << Instruction.new(node.codeOrigin, 488 node.opcode, 489 riscAsRegisters(newList, postInstructions, node.operands, "d"), 490 annotation) 491 when "jmp", "call" 492 newList << Instruction.new(node.codeOrigin, 493 node.opcode, 494 [riscAsRegister(newList, postInstructions, node.operands[0], "p", false)], 495 annotation) 496 else 497 newList << node 498 end 499 newList += postInstructions 500 else 501 newList << node 502 end 503 } 504 newList 505end 506 507# 508# Lowering of register reuse in compare instructions. For example: 509# 510# cieq t0, t1, t0 511# 512# will become: 513# 514# mov tmp, t0 515# cieq tmp, t1, t0 516# 517 518def riscLowerRegisterReuse(list) 519 newList = [] 520 list.each { 521 | node | 522 if node.is_a? Instruction 523 annotation = node.annotation 524 case node.opcode 525 when "cieq", "cineq", "cia", "ciaeq", "cib", "cibeq", "cigt", "cigteq", "cilt", "cilteq", 526 "cpeq", "cpneq", "cpa", "cpaeq", "cpb", "cpbeq", "cpgt", "cpgteq", "cplt", "cplteq", 527 "tis", "tiz", "tinz", "tbs", "tbz", "tbnz", "tps", "tpz", "tpnz", "cbeq", "cbneq", 528 "cba", "cbaeq", "cbb", "cbbeq", "cbgt", "cbgteq", "cblt", "cblteq" 529 if node.operands.size == 2 530 if node.operands[0] == node.operands[1] 531 tmp = Tmp.new(node.codeOrigin, :gpr) 532 newList << Instruction.new(node.codeOrigin, "move", [node.operands[0], tmp], annotation) 533 newList << Instruction.new(node.codeOrigin, node.opcode, [tmp, node.operands[1]]) 534 else 535 newList << node 536 end 537 else 538 raise "Wrong number of arguments at #{node.codeOriginString}" unless node.operands.size == 3 539 if node.operands[0] == node.operands[2] 540 tmp = Tmp.new(node.codeOrigin, :gpr) 541 newList << Instruction.new(node.codeOrigin, "move", [node.operands[0], tmp], annotation) 542 newList << Instruction.new(node.codeOrigin, node.opcode, [tmp, node.operands[1], node.operands[2]]) 543 elsif node.operands[1] == node.operands[2] 544 tmp = Tmp.new(node.codeOrigin, :gpr) 545 newList << Instruction.new(node.codeOrigin, "move", [node.operands[1], tmp], annotation) 546 newList << Instruction.new(node.codeOrigin, node.opcode, [node.operands[0], tmp, node.operands[2]]) 547 else 548 newList << node 549 end 550 end 551 else 552 newList << node 553 end 554 else 555 newList << node 556 end 557 } 558 newList 559end 560 561# 562# Lowering of the not instruction. The following: 563# 564# noti t0 565# 566# becomes: 567# 568# xori -1, t0 569# 570 571def riscLowerNot(list) 572 newList = [] 573 list.each { 574 | node | 575 if node.is_a? Instruction 576 case node.opcode 577 when "noti", "notp" 578 raise "Wrong nubmer of operands at #{node.codeOriginString}" unless node.operands.size == 1 579 suffix = node.opcode[-1..-1] 580 newList << Instruction.new(node.codeOrigin, "xor" + suffix, 581 [Immediate.new(node.codeOrigin, -1), node.operands[0]]) 582 else 583 newList << node 584 end 585 else 586 newList << node 587 end 588 } 589 return newList 590end 591 592# 593# Lowing of complex branch ops on 64-bit. For example: 594# 595# bmulio foo, bar, baz 596# 597# becomes: 598# 599# smulli foo, bar, bar 600# rshiftp bar, 32, tmp1 601# rshifti bar, 31, tmp2 602# zxi2p bar, bar 603# bineq tmp1, tmp2, baz 604# 605 606def riscLowerHardBranchOps64(list) 607 newList = [] 608 list.each { 609 | node | 610 if node.is_a? Instruction and node.opcode == "bmulio" 611 tmp1 = Tmp.new(node.codeOrigin, :gpr) 612 tmp2 = Tmp.new(node.codeOrigin, :gpr) 613 newList << Instruction.new(node.codeOrigin, "smulli", [node.operands[0], node.operands[1], node.operands[1]]) 614 newList << Instruction.new(node.codeOrigin, "rshiftp", [node.operands[1], Immediate.new(node.codeOrigin, 32), tmp1]) 615 newList << Instruction.new(node.codeOrigin, "rshifti", [node.operands[1], Immediate.new(node.codeOrigin, 31), tmp2]) 616 newList << Instruction.new(node.codeOrigin, "zxi2p", [node.operands[1], node.operands[1]]) 617 newList << Instruction.new(node.codeOrigin, "bineq", [tmp1, tmp2, node.operands[2]]) 618 else 619 newList << node 620 end 621 } 622 newList 623end 624 625# 626# Lowering of test instructions. For example: 627# 628# btiz t0, t1, .foo 629# 630# becomes: 631# 632# andi t0, t1, tmp 633# bieq tmp, 0, .foo 634# 635# and another example: 636# 637# tiz t0, t1, t2 638# 639# becomes: 640# 641# andi t0, t1, tmp 642# cieq tmp, 0, t2 643# 644 645def riscLowerTest(list) 646 def emit(newList, andOpcode, branchOpcode, node) 647 if node.operands.size == 2 648 newList << Instruction.new(node.codeOrigin, branchOpcode, [node.operands[0], Immediate.new(node.codeOrigin, 0), node.operands[1]]) 649 return 650 end 651 652 raise "Incorrect number of operands at #{codeOriginString}" unless node.operands.size == 3 653 654 if node.operands[0].immediate? and node.operands[0].value == -1 655 newList << Instruction.new(node.codeOrigin, branchOpcode, [node.operands[1], Immediate.new(node.codeOrigin, 0), node.operands[2]]) 656 return 657 end 658 659 if node.operands[1].immediate? and node.operands[1].value == -1 660 newList << Instruction.new(node.codeOrigin, branchOpcode, [node.operands[0], Immediate.new(node.codeOrigin, 0), node.operands[2]]) 661 return 662 end 663 664 tmp = Tmp.new(node.codeOrigin, :gpr) 665 newList << Instruction.new(node.codeOrigin, andOpcode, [node.operands[0], node.operands[1], tmp]) 666 newList << Instruction.new(node.codeOrigin, branchOpcode, [tmp, Immediate.new(node.codeOrigin, 0), node.operands[2]]) 667 end 668 669 newList = [] 670 list.each { 671 | node | 672 if node.is_a? Instruction 673 case node.opcode 674 when "btis" 675 emit(newList, "andi", "bilt", node) 676 when "btiz" 677 emit(newList, "andi", "bieq", node) 678 when "btinz" 679 emit(newList, "andi", "bineq", node) 680 when "btps" 681 emit(newList, "andp", "bplt", node) 682 when "btpz" 683 emit(newList, "andp", "bpeq", node) 684 when "btpnz" 685 emit(newList, "andp", "bpneq", node) 686 when "btqs" 687 emit(newList, "andq", "bqlt", node) 688 when "btqz" 689 emit(newList, "andq", "bqeq", node) 690 when "btqnz" 691 emit(newList, "andq", "bqneq", node) 692 when "btbs" 693 emit(newList, "andi", "bblt", node) 694 when "btbz" 695 emit(newList, "andi", "bbeq", node) 696 when "btbnz" 697 emit(newList, "andi", "bbneq", node) 698 when "tis" 699 emit(newList, "andi", "cilt", node) 700 when "tiz" 701 emit(newList, "andi", "cieq", node) 702 when "tinz" 703 emit(newList, "andi", "cineq", node) 704 when "tps" 705 emit(newList, "andp", "cplt", node) 706 when "tpz" 707 emit(newList, "andp", "cpeq", node) 708 when "tpnz" 709 emit(newList, "andp", "cpneq", node) 710 when "tqs" 711 emit(newList, "andq", "cqlt", node) 712 when "tqz" 713 emit(newList, "andq", "cqeq", node) 714 when "tqnz" 715 emit(newList, "andq", "cqneq", node) 716 when "tbs" 717 emit(newList, "andi", "cblt", node) 718 when "tbz" 719 emit(newList, "andi", "cbeq", node) 720 when "tbnz" 721 emit(newList, "andi", "cbneq", node) 722 else 723 newList << node 724 end 725 else 726 newList << node 727 end 728 } 729 return newList 730end 731