1# Copyright (C) 2011 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" 25 26# 27# Base utility types for the AST. 28# 29 30# Valid methods for Node: 31# 32# node.children -> Returns an array of immediate children. 33# 34# node.descendents -> Returns an array of all strict descendants (children 35# and children of children, transitively). 36# 37# node.flatten -> Returns an array containing the strict descendants and 38# the node itself. 39# 40# node.filter(type) -> Returns an array containing those elements in 41# node.flatten that are of the given type (is_a? type returns true). 42# 43# node.mapChildren{|v| ...} -> Returns a new node with all children 44# replaced according to the given block. 45# 46# Examples: 47# 48# node.filter(Setting).uniq -> Returns all of the settings that the AST's 49# IfThenElse blocks depend on. 50# 51# node.filter(StructOffset).uniq -> Returns all of the structure offsets 52# that the AST depends on. 53 54class Node 55 attr_reader :codeOrigin 56 57 def initialize(codeOrigin) 58 @codeOrigin = codeOrigin 59 end 60 61 def codeOriginString 62 @codeOrigin.to_s 63 end 64 65 def descendants 66 children.collect{|v| v.flatten}.flatten 67 end 68 69 def flatten 70 [self] + descendants 71 end 72 73 def filter(type) 74 flatten.select{|v| v.is_a? type} 75 end 76end 77 78class NoChildren < Node 79 def initialize(codeOrigin) 80 super(codeOrigin) 81 end 82 83 def children 84 [] 85 end 86 87 def mapChildren 88 self 89 end 90end 91 92class StructOffsetKey 93 attr_reader :struct, :field 94 95 def initialize(struct, field) 96 @struct = struct 97 @field = field 98 end 99 100 def hash 101 @struct.hash + @field.hash * 3 102 end 103 104 def eql?(other) 105 @struct == other.struct and @field == other.field 106 end 107end 108 109# 110# AST nodes. 111# 112 113class StructOffset < NoChildren 114 attr_reader :struct, :field 115 116 def initialize(codeOrigin, struct, field) 117 super(codeOrigin) 118 @struct = struct 119 @field = field 120 end 121 122 @@mapping = {} 123 124 def self.forField(codeOrigin, struct, field) 125 key = StructOffsetKey.new(struct, field) 126 127 unless @@mapping[key] 128 @@mapping[key] = StructOffset.new(codeOrigin, struct, field) 129 end 130 @@mapping[key] 131 end 132 133 def dump 134 "#{struct}::#{field}" 135 end 136 137 def <=>(other) 138 if @struct != other.struct 139 return @struct <=> other.struct 140 end 141 @field <=> other.field 142 end 143 144 def address? 145 false 146 end 147 148 def label? 149 false 150 end 151 152 def immediate? 153 true 154 end 155 156 def register? 157 false 158 end 159end 160 161class Sizeof < NoChildren 162 attr_reader :struct 163 164 def initialize(codeOrigin, struct) 165 super(codeOrigin) 166 @struct = struct 167 end 168 169 @@mapping = {} 170 171 def self.forName(codeOrigin, struct) 172 unless @@mapping[struct] 173 @@mapping[struct] = Sizeof.new(codeOrigin, struct) 174 end 175 @@mapping[struct] 176 end 177 178 def dump 179 "sizeof #{@struct}" 180 end 181 182 def <=>(other) 183 @struct <=> other.struct 184 end 185 186 def address? 187 false 188 end 189 190 def label? 191 false 192 end 193 194 def immediate? 195 true 196 end 197 198 def register? 199 false 200 end 201end 202 203class Immediate < NoChildren 204 attr_reader :value 205 206 def initialize(codeOrigin, value) 207 super(codeOrigin) 208 @value = value 209 raise "Bad immediate value #{value.inspect} at #{codeOriginString}" unless value.is_a? Integer 210 end 211 212 def dump 213 "#{value}" 214 end 215 216 def ==(other) 217 other.is_a? Immediate and other.value == @value 218 end 219 220 def address? 221 false 222 end 223 224 def label? 225 false 226 end 227 228 def immediate? 229 true 230 end 231 232 def register? 233 false 234 end 235end 236 237class AddImmediates < Node 238 attr_reader :left, :right 239 240 def initialize(codeOrigin, left, right) 241 super(codeOrigin) 242 @left = left 243 @right = right 244 end 245 246 def children 247 [@left, @right] 248 end 249 250 def mapChildren 251 AddImmediates.new(codeOrigin, (yield @left), (yield @right)) 252 end 253 254 def dump 255 "(#{left.dump} + #{right.dump})" 256 end 257 258 def address? 259 false 260 end 261 262 def label? 263 false 264 end 265 266 def immediate? 267 true 268 end 269 270 def register? 271 false 272 end 273end 274 275class SubImmediates < Node 276 attr_reader :left, :right 277 278 def initialize(codeOrigin, left, right) 279 super(codeOrigin) 280 @left = left 281 @right = right 282 end 283 284 def children 285 [@left, @right] 286 end 287 288 def mapChildren 289 SubImmediates.new(codeOrigin, (yield @left), (yield @right)) 290 end 291 292 def dump 293 "(#{left.dump} - #{right.dump})" 294 end 295 296 def address? 297 false 298 end 299 300 def label? 301 false 302 end 303 304 def immediate? 305 true 306 end 307 308 def register? 309 false 310 end 311end 312 313class MulImmediates < Node 314 attr_reader :left, :right 315 316 def initialize(codeOrigin, left, right) 317 super(codeOrigin) 318 @left = left 319 @right = right 320 end 321 322 def children 323 [@left, @right] 324 end 325 326 def mapChildren 327 MulImmediates.new(codeOrigin, (yield @left), (yield @right)) 328 end 329 330 def dump 331 "(#{left.dump} * #{right.dump})" 332 end 333 334 def address? 335 false 336 end 337 338 def label? 339 false 340 end 341 342 def immediate? 343 true 344 end 345 346 def register? 347 false 348 end 349end 350 351class NegImmediate < Node 352 attr_reader :child 353 354 def initialize(codeOrigin, child) 355 super(codeOrigin) 356 @child = child 357 end 358 359 def children 360 [@child] 361 end 362 363 def mapChildren 364 NegImmediate.new(codeOrigin, (yield @child)) 365 end 366 367 def dump 368 "(-#{@child.dump})" 369 end 370 371 def address? 372 false 373 end 374 375 def label? 376 false 377 end 378 379 def immediate? 380 true 381 end 382 383 def register? 384 false 385 end 386end 387 388class OrImmediates < Node 389 attr_reader :left, :right 390 391 def initialize(codeOrigin, left, right) 392 super(codeOrigin) 393 @left = left 394 @right = right 395 end 396 397 def children 398 [@left, @right] 399 end 400 401 def mapChildren 402 OrImmediates.new(codeOrigin, (yield @left), (yield @right)) 403 end 404 405 def dump 406 "(#{left.dump} | #{right.dump})" 407 end 408 409 def address? 410 false 411 end 412 413 def label? 414 false 415 end 416 417 def immediate? 418 true 419 end 420 421 def register? 422 false 423 end 424end 425 426class AndImmediates < Node 427 attr_reader :left, :right 428 429 def initialize(codeOrigin, left, right) 430 super(codeOrigin) 431 @left = left 432 @right = right 433 end 434 435 def children 436 [@left, @right] 437 end 438 439 def mapChildren 440 AndImmediates.new(codeOrigin, (yield @left), (yield @right)) 441 end 442 443 def dump 444 "(#{left.dump} & #{right.dump})" 445 end 446 447 def address? 448 false 449 end 450 451 def label? 452 false 453 end 454 455 def immediate? 456 true 457 end 458 459 def register? 460 false 461 end 462end 463 464class XorImmediates < Node 465 attr_reader :left, :right 466 467 def initialize(codeOrigin, left, right) 468 super(codeOrigin) 469 @left = left 470 @right = right 471 end 472 473 def children 474 [@left, @right] 475 end 476 477 def mapChildren 478 XorImmediates.new(codeOrigin, (yield @left), (yield @right)) 479 end 480 481 def dump 482 "(#{left.dump} ^ #{right.dump})" 483 end 484 485 def address? 486 false 487 end 488 489 def label? 490 false 491 end 492 493 def immediate? 494 true 495 end 496 497 def register? 498 false 499 end 500end 501 502class BitnotImmediate < Node 503 attr_reader :child 504 505 def initialize(codeOrigin, child) 506 super(codeOrigin) 507 @child = child 508 end 509 510 def children 511 [@child] 512 end 513 514 def mapChildren 515 BitnotImmediate.new(codeOrigin, (yield @child)) 516 end 517 518 def dump 519 "(~#{@child.dump})" 520 end 521 522 def address? 523 false 524 end 525 526 def label? 527 false 528 end 529 530 def immediate? 531 true 532 end 533 534 def register? 535 false 536 end 537end 538 539class RegisterID < NoChildren 540 attr_reader :name 541 542 def initialize(codeOrigin, name) 543 super(codeOrigin) 544 @name = name 545 end 546 547 @@mapping = {} 548 549 def self.forName(codeOrigin, name) 550 unless @@mapping[name] 551 @@mapping[name] = RegisterID.new(codeOrigin, name) 552 end 553 @@mapping[name] 554 end 555 556 def dump 557 name 558 end 559 560 def address? 561 false 562 end 563 564 def label? 565 false 566 end 567 568 def immediate? 569 false 570 end 571 572 def register? 573 true 574 end 575end 576 577class FPRegisterID < NoChildren 578 attr_reader :name 579 580 def initialize(codeOrigin, name) 581 super(codeOrigin) 582 @name = name 583 end 584 585 @@mapping = {} 586 587 def self.forName(codeOrigin, name) 588 unless @@mapping[name] 589 @@mapping[name] = FPRegisterID.new(codeOrigin, name) 590 end 591 @@mapping[name] 592 end 593 594 def dump 595 name 596 end 597 598 def address? 599 false 600 end 601 602 def label? 603 false 604 end 605 606 def immediate? 607 false 608 end 609 610 def register? 611 true 612 end 613end 614 615class SpecialRegister < NoChildren 616 def initialize(name) 617 @name = name 618 end 619 620 def address? 621 false 622 end 623 624 def label? 625 false 626 end 627 628 def immediate? 629 false 630 end 631 632 def register? 633 true 634 end 635end 636 637class Variable < NoChildren 638 attr_reader :name 639 640 def initialize(codeOrigin, name) 641 super(codeOrigin) 642 @name = name 643 end 644 645 @@mapping = {} 646 647 def self.forName(codeOrigin, name) 648 unless @@mapping[name] 649 @@mapping[name] = Variable.new(codeOrigin, name) 650 end 651 @@mapping[name] 652 end 653 654 def dump 655 name 656 end 657 658 def inspect 659 "<variable #{name} at #{codeOriginString}>" 660 end 661end 662 663class Address < Node 664 attr_reader :base, :offset 665 666 def initialize(codeOrigin, base, offset) 667 super(codeOrigin) 668 @base = base 669 @offset = offset 670 raise "Bad base for address #{base.inspect} at #{codeOriginString}" unless base.is_a? Variable or base.register? 671 raise "Bad offset for address #{offset.inspect} at #{codeOriginString}" unless offset.is_a? Variable or offset.immediate? 672 end 673 674 def withOffset(extraOffset) 675 Address.new(codeOrigin, @base, Immediate.new(codeOrigin, @offset.value + extraOffset)) 676 end 677 678 def children 679 [@base, @offset] 680 end 681 682 def mapChildren 683 Address.new(codeOrigin, (yield @base), (yield @offset)) 684 end 685 686 def dump 687 "#{offset.dump}[#{base.dump}]" 688 end 689 690 def address? 691 true 692 end 693 694 def label? 695 false 696 end 697 698 def immediate? 699 false 700 end 701 702 def register? 703 false 704 end 705end 706 707class BaseIndex < Node 708 attr_reader :base, :index, :scale, :offset 709 710 def initialize(codeOrigin, base, index, scale, offset) 711 super(codeOrigin) 712 @base = base 713 @index = index 714 @scale = scale 715 raise unless [1, 2, 4, 8].member? @scale 716 @offset = offset 717 end 718 719 def scaleShift 720 case scale 721 when 1 722 0 723 when 2 724 1 725 when 4 726 2 727 when 8 728 3 729 else 730 raise "Bad scale at #{codeOriginString}" 731 end 732 end 733 734 def withOffset(extraOffset) 735 BaseIndex.new(codeOrigin, @base, @index, @scale, Immediate.new(codeOrigin, @offset.value + extraOffset)) 736 end 737 738 def children 739 [@base, @index, @offset] 740 end 741 742 def mapChildren 743 BaseIndex.new(codeOrigin, (yield @base), (yield @index), @scale, (yield @offset)) 744 end 745 746 def dump 747 "#{offset.dump}[#{base.dump}, #{index.dump}, #{scale}]" 748 end 749 750 def address? 751 true 752 end 753 754 def label? 755 false 756 end 757 758 def immediate? 759 false 760 end 761 762 def register? 763 false 764 end 765end 766 767class AbsoluteAddress < NoChildren 768 attr_reader :address 769 770 def initialize(codeOrigin, address) 771 super(codeOrigin) 772 @address = address 773 end 774 775 def withOffset(extraOffset) 776 AbsoluteAddress.new(codeOrigin, Immediate.new(codeOrigin, @address.value + extraOffset)) 777 end 778 779 def dump 780 "#{address.dump}[]" 781 end 782 783 def address? 784 true 785 end 786 787 def label? 788 false 789 end 790 791 def immediate? 792 false 793 end 794 795 def register? 796 false 797 end 798end 799 800class Instruction < Node 801 attr_reader :opcode, :operands, :annotation 802 803 def initialize(codeOrigin, opcode, operands, annotation=nil) 804 super(codeOrigin) 805 @opcode = opcode 806 @operands = operands 807 @annotation = annotation 808 end 809 810 def children 811 operands 812 end 813 814 def mapChildren(&proc) 815 Instruction.new(codeOrigin, @opcode, @operands.map(&proc), @annotation) 816 end 817 818 def dump 819 "\t" + opcode.to_s + " " + operands.collect{|v| v.dump}.join(", ") 820 end 821 822 def lowerDefault 823 case opcode 824 when "localAnnotation" 825 $asm.putLocalAnnotation 826 when "globalAnnotation" 827 $asm.putGlobalAnnotation 828 else 829 raise "Unhandled opcode #{opcode} at #{codeOriginString}" 830 end 831 end 832end 833 834class Error < NoChildren 835 def initialize(codeOrigin) 836 super(codeOrigin) 837 end 838 839 def dump 840 "\terror" 841 end 842end 843 844class ConstDecl < Node 845 attr_reader :variable, :value 846 847 def initialize(codeOrigin, variable, value) 848 super(codeOrigin) 849 @variable = variable 850 @value = value 851 end 852 853 def children 854 [@variable, @value] 855 end 856 857 def mapChildren 858 ConstDecl.new(codeOrigin, (yield @variable), (yield @value)) 859 end 860 861 def dump 862 "const #{@variable.dump} = #{@value.dump}" 863 end 864end 865 866$labelMapping = {} 867 868class Label < NoChildren 869 attr_reader :name 870 871 def initialize(codeOrigin, name) 872 super(codeOrigin) 873 @name = name 874 end 875 876 def self.forName(codeOrigin, name) 877 if $labelMapping[name] 878 raise "Label name collision: #{name}" unless $labelMapping[name].is_a? Label 879 else 880 $labelMapping[name] = Label.new(codeOrigin, name) 881 end 882 $labelMapping[name] 883 end 884 885 def dump 886 "#{name}:" 887 end 888end 889 890class LocalLabel < NoChildren 891 attr_reader :name 892 893 def initialize(codeOrigin, name) 894 super(codeOrigin) 895 @name = name 896 end 897 898 @@uniqueNameCounter = 0 899 900 def self.forName(codeOrigin, name) 901 if $labelMapping[name] 902 raise "Label name collision: #{name}" unless $labelMapping[name].is_a? LocalLabel 903 else 904 $labelMapping[name] = LocalLabel.new(codeOrigin, name) 905 end 906 $labelMapping[name] 907 end 908 909 def self.unique(comment) 910 newName = "_#{comment}" 911 if $labelMapping[newName] 912 while $labelMapping[newName = "_#{@@uniqueNameCounter}_#{comment}"] 913 @@uniqueNameCounter += 1 914 end 915 end 916 forName(nil, newName) 917 end 918 919 def cleanName 920 if name =~ /^\./ 921 "_" + name[1..-1] 922 else 923 name 924 end 925 end 926 927 def dump 928 "#{name}:" 929 end 930end 931 932class LabelReference < Node 933 attr_reader :label 934 935 def initialize(codeOrigin, label) 936 super(codeOrigin) 937 @label = label 938 end 939 940 def children 941 [@label] 942 end 943 944 def mapChildren 945 LabelReference.new(codeOrigin, (yield @label)) 946 end 947 948 def name 949 label.name 950 end 951 952 def dump 953 label.name 954 end 955 956 def address? 957 false 958 end 959 960 def label? 961 true 962 end 963 964 def immediate? 965 false 966 end 967end 968 969class LocalLabelReference < NoChildren 970 attr_reader :label 971 972 def initialize(codeOrigin, label) 973 super(codeOrigin) 974 @label = label 975 end 976 977 def children 978 [@label] 979 end 980 981 def mapChildren 982 LocalLabelReference.new(codeOrigin, (yield @label)) 983 end 984 985 def name 986 label.name 987 end 988 989 def dump 990 label.name 991 end 992 993 def address? 994 false 995 end 996 997 def label? 998 true 999 end 1000 1001 def immediate? 1002 false 1003 end 1004end 1005 1006class Sequence < Node 1007 attr_reader :list 1008 1009 def initialize(codeOrigin, list) 1010 super(codeOrigin) 1011 @list = list 1012 end 1013 1014 def children 1015 list 1016 end 1017 1018 def mapChildren(&proc) 1019 Sequence.new(codeOrigin, @list.map(&proc)) 1020 end 1021 1022 def dump 1023 list.collect{|v| v.dump}.join("\n") 1024 end 1025end 1026 1027class True < NoChildren 1028 def initialize 1029 super(nil) 1030 end 1031 1032 @@instance = True.new 1033 1034 def self.instance 1035 @@instance 1036 end 1037 1038 def value 1039 true 1040 end 1041 1042 def dump 1043 "true" 1044 end 1045end 1046 1047class False < NoChildren 1048 def initialize 1049 super(nil) 1050 end 1051 1052 @@instance = False.new 1053 1054 def self.instance 1055 @@instance 1056 end 1057 1058 def value 1059 false 1060 end 1061 1062 def dump 1063 "false" 1064 end 1065end 1066 1067class TrueClass 1068 def asNode 1069 True.instance 1070 end 1071end 1072 1073class FalseClass 1074 def asNode 1075 False.instance 1076 end 1077end 1078 1079class Setting < NoChildren 1080 attr_reader :name 1081 1082 def initialize(codeOrigin, name) 1083 super(codeOrigin) 1084 @name = name 1085 end 1086 1087 @@mapping = {} 1088 1089 def self.forName(codeOrigin, name) 1090 unless @@mapping[name] 1091 @@mapping[name] = Setting.new(codeOrigin, name) 1092 end 1093 @@mapping[name] 1094 end 1095 1096 def dump 1097 name 1098 end 1099end 1100 1101class And < Node 1102 attr_reader :left, :right 1103 1104 def initialize(codeOrigin, left, right) 1105 super(codeOrigin) 1106 @left = left 1107 @right = right 1108 end 1109 1110 def children 1111 [@left, @right] 1112 end 1113 1114 def mapChildren 1115 And.new(codeOrigin, (yield @left), (yield @right)) 1116 end 1117 1118 def dump 1119 "(#{left.dump} and #{right.dump})" 1120 end 1121end 1122 1123class Or < Node 1124 attr_reader :left, :right 1125 1126 def initialize(codeOrigin, left, right) 1127 super(codeOrigin) 1128 @left = left 1129 @right = right 1130 end 1131 1132 def children 1133 [@left, @right] 1134 end 1135 1136 def mapChildren 1137 Or.new(codeOrigin, (yield @left), (yield @right)) 1138 end 1139 1140 def dump 1141 "(#{left.dump} or #{right.dump})" 1142 end 1143end 1144 1145class Not < Node 1146 attr_reader :child 1147 1148 def initialize(codeOrigin, child) 1149 super(codeOrigin) 1150 @child = child 1151 end 1152 1153 def children 1154 [@child] 1155 end 1156 1157 def mapChildren 1158 Not.new(codeOrigin, (yield @child)) 1159 end 1160 1161 def dump 1162 "(not #{child.dump})" 1163 end 1164end 1165 1166class Skip < NoChildren 1167 def initialize(codeOrigin) 1168 super(codeOrigin) 1169 end 1170 1171 def dump 1172 "\tskip" 1173 end 1174end 1175 1176class IfThenElse < Node 1177 attr_reader :predicate, :thenCase 1178 attr_accessor :elseCase 1179 1180 def initialize(codeOrigin, predicate, thenCase) 1181 super(codeOrigin) 1182 @predicate = predicate 1183 @thenCase = thenCase 1184 @elseCase = Skip.new(codeOrigin) 1185 end 1186 1187 def children 1188 if @elseCase 1189 [@predicate, @thenCase, @elseCase] 1190 else 1191 [@predicate, @thenCase] 1192 end 1193 end 1194 1195 def mapChildren 1196 IfThenElse.new(codeOrigin, (yield @predicate), (yield @thenCase), (yield @elseCase)) 1197 end 1198 1199 def dump 1200 "if #{predicate.dump}\n" + thenCase.dump + "\nelse\n" + elseCase.dump + "\nend" 1201 end 1202end 1203 1204class Macro < Node 1205 attr_reader :name, :variables, :body 1206 1207 def initialize(codeOrigin, name, variables, body) 1208 super(codeOrigin) 1209 @name = name 1210 @variables = variables 1211 @body = body 1212 end 1213 1214 def children 1215 @variables + [@body] 1216 end 1217 1218 def mapChildren 1219 Macro.new(codeOrigin, @name, @variables.map{|v| yield v}, (yield @body)) 1220 end 1221 1222 def dump 1223 "macro #{name}(" + variables.collect{|v| v.dump}.join(", ") + ")\n" + body.dump + "\nend" 1224 end 1225end 1226 1227class MacroCall < Node 1228 attr_reader :name, :operands, :annotation 1229 1230 def initialize(codeOrigin, name, operands, annotation) 1231 super(codeOrigin) 1232 @name = name 1233 @operands = operands 1234 raise unless @operands 1235 @operands.each{|v| raise unless v} 1236 @annotation = annotation 1237 end 1238 1239 def children 1240 @operands 1241 end 1242 1243 def mapChildren(&proc) 1244 MacroCall.new(codeOrigin, @name, @operands.map(&proc), @annotation) 1245 end 1246 1247 def dump 1248 "\t#{name}(" + operands.collect{|v| v.dump}.join(", ") + ")" 1249 end 1250end 1251 1252