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" 25require "ast" 26 27# 28# node.resolveSettings(settings) 29# 30# Construct a new AST that does not have any IfThenElse nodes by 31# substituting concrete boolean values for each Setting. 32# 33 34class Node 35 def resolveSettings(settings) 36 mapChildren { 37 | child | 38 child.resolveSettings(settings) 39 } 40 end 41end 42 43class True 44 def resolveSettings(settings) 45 self 46 end 47end 48 49class False 50 def resolveSettings(settings) 51 self 52 end 53end 54 55class Setting 56 def resolveSettings(settings) 57 settings[@name].asNode 58 end 59end 60 61class And 62 def resolveSettings(settings) 63 (@left.resolveSettings(settings).value and @right.resolveSettings(settings).value).asNode 64 end 65end 66 67class Or 68 def resolveSettings(settings) 69 (@left.resolveSettings(settings).value or @right.resolveSettings(settings).value).asNode 70 end 71end 72 73class Not 74 def resolveSettings(settings) 75 (not @child.resolveSettings(settings).value).asNode 76 end 77end 78 79class IfThenElse 80 def resolveSettings(settings) 81 if @predicate.resolveSettings(settings).value 82 @thenCase.resolveSettings(settings) 83 else 84 @elseCase.resolveSettings(settings) 85 end 86 end 87end 88 89class Sequence 90 def resolveSettings(settings) 91 newList = [] 92 @list.each { 93 | item | 94 item = item.resolveSettings(settings) 95 if item.is_a? Sequence 96 newList += item.list 97 else 98 newList << item 99 end 100 } 101 Sequence.new(codeOrigin, newList) 102 end 103end 104 105# 106# node.demacroify(macros) 107# node.substitute(mapping) 108# 109# demacroify() constructs a new AST that does not have any Macro 110# nodes, while substitute() replaces Variable nodes with the given 111# nodes in the mapping. 112# 113 114class Node 115 def demacroify(macros) 116 mapChildren { 117 | child | 118 child.demacroify(macros) 119 } 120 end 121 122 def substitute(mapping) 123 mapChildren { 124 | child | 125 child.substitute(mapping) 126 } 127 end 128 129 def substituteLabels(mapping) 130 mapChildren { 131 | child | 132 child.substituteLabels(mapping) 133 } 134 end 135end 136 137class Macro 138 def substitute(mapping) 139 myMapping = {} 140 mapping.each_pair { 141 | key, value | 142 unless @variables.include? key 143 myMapping[key] = value 144 end 145 } 146 mapChildren { 147 | child | 148 child.substitute(myMapping) 149 } 150 end 151end 152 153class Variable 154 def substitute(mapping) 155 if mapping[self] 156 mapping[self] 157 else 158 self 159 end 160 end 161end 162 163class LocalLabel 164 def substituteLabels(mapping) 165 if mapping[self] 166 mapping[self] 167 else 168 self 169 end 170 end 171end 172 173class Sequence 174 def substitute(constants) 175 newList = [] 176 myConstants = constants.dup 177 @list.each { 178 | item | 179 if item.is_a? ConstDecl 180 myConstants[item.variable] = item.value.substitute(myConstants) 181 else 182 newList << item.substitute(myConstants) 183 end 184 } 185 Sequence.new(codeOrigin, newList) 186 end 187 188 def renameLabels(comment) 189 mapping = {} 190 191 @list.each { 192 | item | 193 if item.is_a? LocalLabel 194 mapping[item] = LocalLabel.unique(if comment then comment + "_" else "" end + item.cleanName) 195 end 196 } 197 198 substituteLabels(mapping) 199 end 200 201 def demacroify(macros) 202 myMacros = macros.dup 203 @list.each { 204 | item | 205 if item.is_a? Macro 206 myMacros[item.name] = item 207 end 208 } 209 newList = [] 210 @list.each { 211 | item | 212 if item.is_a? Macro 213 # Ignore. 214 elsif item.is_a? MacroCall 215 mapping = {} 216 myMyMacros = myMacros.dup 217 raise "Could not find macro #{item.name} at #{item.codeOriginString}" unless myMacros[item.name] 218 raise "Argument count mismatch for call to #{item.name} at #{item.codeOriginString}" unless item.operands.size == myMacros[item.name].variables.size 219 item.operands.size.times { 220 | idx | 221 if item.operands[idx].is_a? Variable and myMacros[item.operands[idx].name] 222 myMyMacros[myMacros[item.name].variables[idx].name] = myMacros[item.operands[idx].name] 223 mapping[myMacros[item.name].variables[idx].name] = nil 224 elsif item.operands[idx].is_a? Macro 225 myMyMacros[myMacros[item.name].variables[idx].name] = item.operands[idx] 226 mapping[myMacros[item.name].variables[idx].name] = nil 227 else 228 myMyMacros[myMacros[item.name].variables[idx]] = nil 229 mapping[myMacros[item.name].variables[idx]] = item.operands[idx] 230 end 231 } 232 if item.annotation 233 newList << Instruction.new(item.codeOrigin, "localAnnotation", [], item.annotation) 234 end 235 newList += myMacros[item.name].body.substitute(mapping).demacroify(myMyMacros).renameLabels(item.name).list 236 else 237 newList << item.demacroify(myMacros) 238 end 239 } 240 Sequence.new(codeOrigin, newList).substitute({}) 241 end 242end 243 244# 245# node.resolveOffsets(offsets, sizes) 246# 247# Construct a new AST that has offset values instead of symbolic 248# offsets. 249# 250 251class Node 252 def resolveOffsets(offsets, sizes) 253 mapChildren { 254 | child | 255 child.resolveOffsets(offsets, sizes) 256 } 257 end 258end 259 260class StructOffset 261 def resolveOffsets(offsets, sizes) 262 if offsets[self] 263 Immediate.new(codeOrigin, offsets[self]) 264 else 265 self 266 end 267 end 268end 269 270class Sizeof 271 def resolveOffsets(offsets, sizes) 272 if sizes[self] 273 Immediate.new(codeOrigin, sizes[self]) 274 else 275 puts "Could not find #{self.inspect} in #{sizes.keys.inspect}" 276 puts "sizes = #{sizes.inspect}" 277 self 278 end 279 end 280end 281 282# 283# node.fold 284# 285# Resolve constant references and compute arithmetic expressions. 286# 287 288class Node 289 def fold 290 mapChildren { 291 | child | 292 child.fold 293 } 294 end 295end 296 297class AddImmediates 298 def fold 299 @left = @left.fold 300 @right = @right.fold 301 return self unless @left.is_a? Immediate 302 return self unless @right.is_a? Immediate 303 Immediate.new(codeOrigin, @left.value + @right.value) 304 end 305end 306 307class SubImmediates 308 def fold 309 @left = @left.fold 310 @right = @right.fold 311 return self unless @left.is_a? Immediate 312 return self unless @right.is_a? Immediate 313 Immediate.new(codeOrigin, @left.value - @right.value) 314 end 315end 316 317class MulImmediates 318 def fold 319 @left = @left.fold 320 @right = @right.fold 321 return self unless @left.is_a? Immediate 322 return self unless @right.is_a? Immediate 323 Immediate.new(codeOrigin, @left.value * @right.value) 324 end 325end 326 327class NegImmediate 328 def fold 329 @child = @child.fold 330 return self unless @child.is_a? Immediate 331 Immediate.new(codeOrigin, -@child.value) 332 end 333end 334 335class OrImmediates 336 def fold 337 @left = @left.fold 338 @right = @right.fold 339 return self unless @left.is_a? Immediate 340 return self unless @right.is_a? Immediate 341 Immediate.new(codeOrigin, @left.value | @right.value) 342 end 343end 344 345class AndImmediates 346 def fold 347 @left = @left.fold 348 @right = @right.fold 349 return self unless @left.is_a? Immediate 350 return self unless @right.is_a? Immediate 351 Immediate.new(codeOrigin, @left.value & @right.value) 352 end 353end 354 355class XorImmediates 356 def fold 357 @left = @left.fold 358 @right = @right.fold 359 return self unless @left.is_a? Immediate 360 return self unless @right.is_a? Immediate 361 Immediate.new(codeOrigin, @left.value ^ @right.value) 362 end 363end 364 365class BitnotImmediate 366 def fold 367 @child = @child.fold 368 return self unless @child.is_a? Immediate 369 Immediate.new(codeOrigin, ~@child.value) 370 end 371end 372 373# 374# node.resolveAfterSettings(offsets, sizes) 375# 376# Compile assembly against a set of offsets. 377# 378 379class Node 380 def resolve(offsets, sizes) 381 demacroify({}).resolveOffsets(offsets, sizes).fold 382 end 383end 384 385# 386# node.validate 387# 388# Checks that the node is ready for backend compilation. 389# 390 391class Node 392 def validate 393 raise "Unresolved #{dump} at #{codeOriginString}" 394 end 395 396 def validateChildren 397 children.each { 398 | node | 399 node.validate 400 } 401 end 402end 403 404class Sequence 405 def validate 406 validateChildren 407 408 # Further verify that this list contains only instructions, labels, and skips. 409 @list.each { 410 | node | 411 unless node.is_a? Instruction or 412 node.is_a? Label or 413 node.is_a? LocalLabel or 414 node.is_a? Skip 415 raise "Unexpected #{node.inspect} at #{node.codeOrigin}" 416 end 417 } 418 end 419end 420 421class Immediate 422 def validate 423 end 424end 425 426class RegisterID 427 def validate 428 end 429end 430 431class FPRegisterID 432 def validate 433 end 434end 435 436class Address 437 def validate 438 validateChildren 439 end 440end 441 442class BaseIndex 443 def validate 444 validateChildren 445 end 446end 447 448class AbsoluteAddress 449 def validate 450 validateChildren 451 end 452end 453 454class Instruction 455 def validate 456 validateChildren 457 end 458end 459 460class SubImmediates 461 def validate 462 raise "Invalid operand #{left.dump} to immediate subtraction" unless left.immediateOperand? 463 raise "Invalid operand #{right.dump} to immediate subtraction" unless right.immediateOperand? 464 end 465end 466 467class Error 468 def validate 469 end 470end 471 472class Label 473 def validate 474 end 475end 476 477class LocalLabel 478 def validate 479 end 480end 481 482class LabelReference 483 def validate 484 end 485end 486 487class LocalLabelReference 488 def validate 489 end 490end 491 492class Skip 493 def validate 494 end 495end 496 497