1 # Copyright 2016, VIXL authors 2 # All rights reserved. 3 # 4 # Redistribution and use in source and binary forms, with or without 5 # modification, are permitted provided that the following conditions are met: 6 # 7 # * Redistributions of source code must retain the above copyright notice, 8 # this list of conditions and the following disclaimer. 9 # * Redistributions in binary form must reproduce the above copyright notice, 10 # this list of conditions and the following disclaimer in the documentation 11 # and/or other materials provided with the distribution. 12 # * Neither the name of ARM Limited nor the names of its contributors may be 13 # used to endorse or promote products derived from this software without 14 # specific prior written permission. 15 # 16 # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS CONTRIBUTORS "AS IS" AND 17 # ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 18 # WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 19 # DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE 20 # FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 21 # DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 22 # SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 23 # CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 24 # OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 25 # OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 26 27 import itertools 28 import random 29 import os.path 30 from copy import deepcopy 31 32 class OperandList(object): 33 """ 34 Convenience class representing a list of operand objects. It can be viewed is 35 an iterator over operand objects. 36 37 Attributes: 38 operand_list 39 """ 40 41 def __init__(self, operand_list): 42 self.operand_list = operand_list 43 44 def __iter__(self): 45 return iter(self.operand_list) 46 47 def unwrap(self): 48 """ 49 Return a list of `Operand` objects, unwrapping `OperandWrapper` objects into 50 `Operand` objects. For example: 51 52 ~~~ 53 Condition, Register, Operand(Register, Shift, Register) 54 ~~~ 55 56 Unwraps to: 57 58 ~~~ 59 Condition, Register, Register, Shift, Register 60 ~~~ 61 """ 62 return itertools.chain(*self.operand_list) 63 64 def ExcludeVariants(self, type_name, variant_to_exclude): 65 """ 66 Remove variants in `variant_to_exclude` from operands with type `type_name`. 67 """ 68 # Find the list of operand with type `type_name`. 69 relevant_operands = filter(lambda operand: operand.type_name == type_name, 70 self) 71 for operand in relevant_operands: 72 # Remove the intersection of the existing variants and variants we do not 73 # want. 74 for variant in set(operand.variants) & set(variant_to_exclude): 75 operand.variants.remove(variant) 76 77 def GetNames(self): 78 """ 79 Return the list of all `Operand` names, excluding `OperandWrapper` objects. 80 """ 81 return [operand.name for operand in self.unwrap()] 82 83 84 class InputList(object): 85 """ 86 Convevience class representing a list of input objects. 87 88 This class is an iterator over input objects. 89 90 Attributes: 91 inputs 92 """ 93 94 def __init__(self, inputs): 95 self.inputs = inputs 96 97 def __iter__(self): 98 return iter(self.inputs) 99 100 def GetNames(self): 101 """ 102 Return the list of input names. 103 """ 104 return [input.name for input in self] 105 106 107 class TestCase(object): 108 """ 109 Object representation of a test case, as described in JSON. This object is 110 used to build sets of operands and inputs that will be used by the generator 111 to produce C++ arrays. 112 113 Attributes: 114 name Name of the test case, it is used to name the array to 115 produce. 116 seed Seed value to use for reproducable random generation. 117 operand_names List of operand names this test case covers. 118 input_names List of input names this test case covers. 119 operand_filter Python expression as a string to filter out operands. 120 input_filter Python expression as a string to filter out inputs. 121 operand_limit Optional limit of the number of operands to generate. 122 input_limit Optional limit of the number of inputs to generate. 123 it_condition If not None, an IT instruction needs to be generated for the 124 instruction under test to be valid. This member is a string 125 template indicating the name of the condition operand, to be 126 used with "format". For example, it will most likely have 127 the value "{cond}". 128 """ 129 130 # Declare functions that will be callable from Python expressions in 131 # `self.operand_filter`. 132 operand_filter_runtime = { 133 'register_is_low': lambda register: 134 register in ["r0", "r1", "r2", "r3", "r4", "r5", "r6", "r7"] 135 } 136 137 def __init__(self, name, seed, operand_names, input_names, operand_filter, 138 input_filter, operand_limit, input_limit, it_condition): 139 self.name = name 140 self.seed = seed 141 self.operand_names = operand_names 142 self.input_names = input_names 143 self.operand_filter = operand_filter 144 self.input_filter = input_filter 145 self.operand_limit = operand_limit 146 self.input_limit = input_limit 147 self.it_condition = it_condition 148 149 def GenerateOperands(self, operand_types): 150 """ 151 Generate a list of tuples, each tuple describing what operands to pass to an 152 instruction to encode it. We use this to generate operand definitions. 153 154 The algorithm used is a simple product of all operand variants. To limit 155 what we generate, we choose to apply the product only on operands with their 156 name in the `self.operand_names` list. 157 158 Additionally, we use the Python expression in `self.operand_filter` to 159 filter out tuples we do not want. 160 161 Argument: 162 operand_types The `OperandList` object that describe the form of the 163 instruction to generate code for. 164 """ 165 # Build a list of all possible variants as a list of tuples. If the 166 # operand's name is not in `self.operand_names`, then we restrict the list 167 # to contain default variant. Each tuple in the list has the form 168 # `(name, [variant1, variant2, ...])`. For example: 169 # 170 # [ 171 # ('cond', ['al', 'ne', 'eq', ...]), # All condition variants. 172 # ('rd', ['r0', 'r1', ...]), # All register variants. 173 # ('rn', ['r0']) # Default register variant (r0). 174 # ... 175 # ] 176 variants = [ 177 [(operand_type.name, variant) for variant in operand_type.variants] 178 if operand_type.name in self.operand_names 179 else [(operand_type.name, operand_type.default)] 180 for operand_type in operand_types.unwrap() 181 ] 182 lambda_string = "lambda {args}: {expression}".format( 183 args=",".join(operand_types.GetNames()), 184 expression=self.operand_filter) 185 filter_lambda = eval(lambda_string, self.operand_filter_runtime) 186 187 def BuildOperandDefinition(operands): 188 """ 189 Take a list of tuples describing the operands and build a definition from 190 it. A definition is a tuple with a list of variants and a 191 `expect_instruction_before` string. 192 193 For example, we are turning this: 194 195 [ 196 ('cond', 'ne'), 197 ('rd', 'r0'), 198 ('rn', 'r1'), 199 ('rm', 'r0) 200 [ 201 202 Into: 203 204 (['ne', 'r0', 'r1', 'r0'], "It ne;") 205 206 """ 207 return ( 208 # Build a list of operands by only keeping the second element of each 209 # tuple. 210 [operand[1] for operand in operands], 211 # The next field is a boolean indicating if the test case needs to 212 # generate an IT instruction. 213 "true" if self.it_condition else "false", 214 # If so, what condition should it be? 215 self.it_condition.format(**dict(operands)) if self.it_condition else "al" 216 ) 217 218 # Build and return a list of operand definitions by computing the product of 219 # all variants and filtering them with `filter_lambda`. 220 # 221 # Operand definitions consist of a list with a list of variants and an 222 # optional `expect_instruction_before` string. For example: 223 # 224 # [ 225 # (['al', 'r0', 'r1', 'r2'], ""), 226 # (['ne', 'r0', 'r1', 'r0'], "It ne;"), 227 # ... 228 # ] 229 # 230 # Here, the filtered product of variants builds a list of lists of tuples, as such: 231 # 232 # [ 233 # [('cond', 'al'), ('rd', 'r0'), ('rn', 'r1'), ('rn', 'r2')] 234 # [('cond', 'ne'), ('rd', 'r0'), ('rn', 'r1'), ('rn', 'r0')], 235 # ... 236 # ] 237 # 238 # We then pass them to `BuildOperandDefinition` to produce the expected form 239 # out of it. 240 result = [ 241 BuildOperandDefinition(operands) 242 for operands in itertools.product(*variants) 243 if filter_lambda(**dict(operands)) 244 ] 245 if self.operand_limit is None: 246 return result 247 else: 248 # Use a fixed seed to randomly choose a limited set of operands. 249 random.seed(self.seed) 250 return random.sample(result, self.operand_limit) 251 252 def GenerateInputs(self, input_types): 253 """ 254 Generate a list of tuples, each tuple describing what input to pass to an 255 instruction at runtime. We use this to generate input definitions. 256 257 The algorithm used is a simple product of all input values. To limit what 258 we generate, we choose to apply the product only on inputs with their name 259 in the `self.input_names` list. 260 261 Additionally, we use the Python expression in `self.input_filter` to filter 262 out tuples we do not want. 263 264 Argument: 265 input_types The `InputList` object describing the list of inputs the 266 instruction can take. 267 """ 268 # Build a list of all possible values as a list of lists. If the input's 269 # name is not in `self.input_names`, then we restrict the list to the 270 # default value. 271 values = [ 272 input_type.values 273 if input_type.name in self.input_names else [input_type.default] 274 for input_type in input_types 275 ] 276 lambda_string = "lambda {args}: {expression}".format( 277 args=", ".join(input_types.GetNames()), 278 expression=self.input_filter) 279 filter_lambda = eval(lambda_string) 280 # Build and return a list of input definitions, such as 281 # [('NoFlag', '0xffffffff', 0xabababab'), ...] for example. 282 result = [ 283 input_definition 284 for input_definition in itertools.product(*values) 285 if filter_lambda(*input_definition) 286 ] 287 if self.input_limit is None: 288 return result 289 else: 290 # Use a fixed seed to randomly choose a limited set of inputs. 291 random.seed(self.seed) 292 return random.sample(result, self.input_limit) 293 294 295 class Generator(object): 296 """ 297 A `Generator` object contains all information needed to generate a test file. 298 Each method will return a string used to fill a variable in a template. 299 300 301 Attributes: 302 test_name Name of the test inferred from the name of the configuration 303 file. It has the following form: `type-op1-op2-op3-isa`. 304 test_type Type of the test, extracted from test_name. 305 mnemonics List of instruction mnemonics. 306 operands `OperandList` object. 307 inputs `InputList` object. 308 test_cases List of `TestCase` objects. 309 """ 310 311 def __init__(self, test_name, test_isa, test_type, mnemonics, operands, 312 inputs, test_cases): 313 self.test_name = test_name 314 self.test_isa = test_isa 315 self.test_type = test_type 316 self.mnemonics = mnemonics 317 self.inputs = inputs 318 self.test_cases = test_cases 319 320 # A simulator test cannot easily make use of the PC and SP registers. 321 if self.test_type == "simulator": 322 # We need to explicitely create our own deep copy the operands before we 323 # can modify them. 324 self.operands = deepcopy(operands) 325 self.operands.ExcludeVariants("Register", ["r13", "r15"]) 326 else: 327 self.operands = operands 328 329 def MnemonicToMethodName(self, mnemonic): 330 if self.test_type in ["simulator", "macro-assembler"]: 331 # Return a MacroAssembler method name 332 return mnemonic.capitalize() 333 else: 334 # Return an Assembler method name 335 method_name = mnemonic.lower() 336 return "and_" if method_name == "and" else method_name 337 338 def InstructionListDeclaration(self): 339 """ 340 ~~~ 341 M(Adc) \ 342 M(Adcs) \ 343 M(Add) \ 344 M(Adds) \ 345 M(And) \ 346 ... 347 ~~~ 348 """ 349 return "".join([ 350 "M({}) \\\n".format(self.MnemonicToMethodName(mnemonic)) 351 for mnemonic in self.mnemonics 352 ]) 353 354 def OperandDeclarations(self): 355 """ 356 ~~~ 357 Condition cond; 358 Register rd; 359 Register rn; 360 ... 361 ~~~ 362 """ 363 return "".join([operand.Declare() for operand in self.operands]) 364 365 def InputDeclarations(self): 366 """ 367 ~~~ 368 uint32_t cond; 369 uint32_t rd; 370 uint32_t rn; 371 ... 372 ~~~ 373 """ 374 return "".join([input.Declare() for input in self.inputs]) 375 376 def InputDefinitions(self): 377 """ 378 ~~~ 379 static const Inputs kCondition[] = {{...},{...}, ...}; 380 static const Inputs kRdIsRd[] = {{...},{...}, ...}; 381 ... 382 ~~~ 383 """ 384 def InputDefinition(test_input): 385 inputs = [ 386 "{{{}}}".format(",".join(input)) 387 for input in test_input.GenerateInputs(self.inputs) 388 ] 389 390 return """static const Inputs k{name}[] = {{ {input} }}; 391 """.format(name=test_input.name, input=",".join(inputs)) 392 393 return "\n".join(map(InputDefinition, self.test_cases)) 394 395 def TestCaseDefinitions(self): 396 """ 397 For simulator tests: 398 ~~~ 399 {{eq, r0, r0, ...}, 400 "eq r0 r0 ...", 401 "Condition_eq_r0_...", 402 ARRAY_SIZE(kCondition), kCondition}, 403 ... 404 {{eq, r0, r0, ...}, 405 "eq r0 r0 ...", 406 "RdIsRd_eq_r0_...", 407 ARRAY_SIZE(kRdIsRd), kRdIsRn}, 408 ... 409 ~~~ 410 411 For assembler tests: 412 ~~~ 413 {{eq, r0, r0, ...}, 414 "", 415 "eq r0 r0 ...", 416 "Condition_eq_r0_...", 417 ... 418 {{eq, r0, r0, ...}, 419 "", 420 "eq r0 r0 ...", 421 "RdIsRd_eq_r0_..."} 422 ... 423 {{eq, r0, r0, ...}, 424 "It eq", 425 "eq r0 r0 ...", 426 "RdIsRd_eq_r0_..."} 427 ... 428 ~~~ 429 """ 430 def SimulatorTestCaseDefinition(test_case): 431 test_cases = [ 432 """{{ {{ {operands} }}, 433 "{operands_description}", 434 "{identifier}", 435 ARRAY_SIZE(k{test_case_name}), 436 k{test_case_name} }} 437 """.format(operands=",".join(operand), 438 operands_description=" ".join(operand), 439 identifier=test_case.name + "_" + "_".join(operand), 440 test_case_name=test_case.name) 441 for operand, _, _ in test_case.GenerateOperands(self.operands) 442 ] 443 return ",\n".join(test_cases) 444 445 def AssemblerTestCaseDefinition(test_case): 446 test_cases = [ 447 """{{ {{ {operands} }}, 448 {in_it_block}, 449 {it_condition}, 450 "{operands_description}", 451 "{identifier}" }} 452 """.format(operands=",".join(operand), 453 in_it_block=in_it_block, 454 it_condition=it_condition, 455 operands_description=" ".join(operand), 456 identifier="_".join(operand)) 457 for operand, in_it_block, it_condition 458 in test_case.GenerateOperands(self.operands) 459 ] 460 return ",\n".join(test_cases) 461 462 def MacroAssemblerTestCaseDefinition(test_case): 463 test_cases = [ 464 """{{ {{ {operands} }}, 465 "{operands_description}", 466 "{identifier}" }} 467 """.format(operands=",".join(operand), 468 operands_description=", ".join(operand), 469 identifier="_".join(operand)) 470 for operand, _, _ in test_case.GenerateOperands(self.operands) 471 ] 472 return ",\n".join(test_cases) 473 474 if self.test_type == "simulator": 475 return ",\n".join(map(SimulatorTestCaseDefinition, self.test_cases)) 476 elif self.test_type == "assembler": 477 return ",\n".join(map(AssemblerTestCaseDefinition, self.test_cases)) 478 elif self.test_type == "macro-assembler": 479 return ",\n".join(map(MacroAssemblerTestCaseDefinition, self.test_cases)) 480 else: 481 raise Exception("Unrecognized test type \"{}\".".format(self.test_type)) 482 483 def IncludeTraceFiles(self): 484 """ 485 ~~~ 486 #include "aarch32/traces/sim-...-a32.h" 487 #include "aarch32/traces/sim-...-a32.h" 488 ... 489 ~~~ 490 """ 491 operands = "-".join(self.operands.GetNames()) 492 return "".join([ 493 "#include \"aarch32/traces/" + self.GetTraceFileName(mnemonic) + "\"\n" 494 for mnemonic in self.mnemonics 495 ]) 496 497 def MacroAssemblerMethodArgs(self): 498 """ 499 ~~~ 500 Condition cond, Register rd, Register rm, const Operand& immediate 501 ~~~ 502 """ 503 return ", ".join([ 504 operand.GetArgumentType() + " " + operand.name 505 for operand in self.operands 506 ]) 507 508 def MacroAssemblerSetISA(self): 509 """ 510 Generate code to set the ISA. 511 """ 512 if self.test_isa == "t32": 513 return "masm.UseT32();" 514 else: 515 return "masm.UseA32();" 516 517 def CodeInstantiateOperands(self): 518 """ 519 ~~~ 520 Condition cond = kTests[i].operands.cond; 521 Register rd = kTests[i].operands.rd; 522 ... 523 ~~~ 524 """ 525 code = "".join([operand.Instantiate() for operand in self.operands]) 526 if self.test_type in ["simulator", "macro-assembler"]: 527 # Simulator tests need scratch registers to function and uses 528 # `UseScratchRegisterScope` to dynamically allocate them. We need to 529 # exclude all register operands from the list of available scratch 530 # registers. 531 # MacroAssembler test also need to ensure that they don't try to run tests 532 # with registers that are scratch registers; the MacroAssembler contains 533 # assertions to protect against such usage. 534 excluded_registers = [ 535 "scratch_registers.Exclude({});".format(operand.name) 536 for operand in self.operands.unwrap() 537 if operand.type_name == "Register" 538 ] 539 return code + "\n".join(excluded_registers) 540 return code 541 542 def CodePrologue(self): 543 """ 544 ~~~ 545 __ Ldr(rn, MemOperand(input_ptr, offsetof(Inputs, rn))); 546 __ Ldr(rm, MemOperand(input_ptr, offsetof(Inputs, rm))); 547 ... 548 ~~~ 549 """ 550 return "".join([input.Prologue() for input in self.inputs]) 551 552 def CodeEpilogue(self): 553 """ 554 ~~~ 555 __ Str(rn, MemOperand(result_ptr, offsetof(Inputs, rn))); 556 __ Str(rm, MemOperand(result_ptr, offsetof(Inputs, rm))); 557 ... 558 ~~~ 559 """ 560 return "".join([input.Epilogue() for input in self.inputs]) 561 562 def CodeParameterList(self): 563 """ 564 ~~~ 565 cond, rd, rn, immediate 566 ~~~ 567 """ 568 return ", ".join([ 569 operand.name 570 for operand in self.operands 571 ]) 572 573 def TracePrintOutputs(self): 574 """ 575 ~~~ 576 printf("0x%08" PRIx32, results[i]->outputs[j].cond); 577 printf(", "); 578 printf("0x%08" PRIx32, results[i]->outputs[j].rd); 579 printf(", "); 580 ... 581 ~~~ 582 """ 583 return "printf(\", \");".join( 584 [input.PrintOutput() for input in self.inputs]) 585 586 587 def CheckInstantiateResults(self): 588 """ 589 ~~~ 590 uint32_t cond = results[i]->outputs[j].cond; 591 uint32_t rd = results[i]->outputs[j].rd; 592 ... 593 ~~~ 594 """ 595 return "".join([input.InstantiateResult() for input in self.inputs]) 596 597 def CheckInstantiateInputs(self): 598 """ 599 ~~~ 600 uint32_t cond_input = kTests[i].inputs[j].cond; 601 uint32_t rd_input = kTests[i].inputs[j].rd; 602 ... 603 ~~~ 604 """ 605 return "".join([input.InstantiateInput("_input") for input in self.inputs]) 606 607 def CheckInstantiateReferences(self): 608 """ 609 ~~~ 610 uint32_t cond_ref = reference[i].outputs[j].cond; 611 uint32_t rd_ref = reference[i].outputs[j].rd; 612 ... 613 ~~~ 614 """ 615 return "".join([input.InstantiateReference("_ref") for input in self.inputs]) 616 617 def CheckResultsAgainstReferences(self): 618 """ 619 ~~~ 620 (cond != cond_ref) || (rd != rd_ref) || ... 621 ~~~ 622 """ 623 return " || ".join([input.Compare("", "!=", "_ref") for input in self.inputs]) 624 625 def CheckPrintInput(self): 626 """ 627 ~~~ 628 printf("0x%08" PRIx32, cond_input); 629 printf(", "); 630 printf("0x%08" PRIx32, rd_input); 631 printf(", "); 632 ... 633 ~~~ 634 """ 635 return "printf(\", \");".join( 636 [input.PrintInput("_input") for input in self.inputs]) 637 638 def CheckPrintExpected(self): 639 """ 640 ~~~ 641 printf("0x%08" PRIx32, cond_ref); 642 printf(", "); 643 printf("0x%08" PRIx32, rd_ref); 644 printf(", "); 645 ... 646 ~~~ 647 """ 648 return "printf(\", \");".join( 649 [input.PrintInput("_ref") for input in self.inputs]) 650 651 def CheckPrintFound(self): 652 """ 653 ~~~ 654 printf("0x%08" PRIx32, cond); 655 printf(", "); 656 printf("0x%08" PRIx32, rd); 657 printf(", "); 658 ... 659 ~~~ 660 """ 661 return "printf(\", \");".join( 662 [input.PrintInput("") for input in self.inputs]) 663 664 def TestName(self): 665 """ 666 ~~~ 667 SIMULATOR_COND_RD_RN_RM_... 668 ~~~ 669 """ 670 return self.test_type.replace("-", "_").upper() + "_" + \ 671 self.test_name.replace("-", "_").upper() 672 673 def GetTraceFileName(self, mnemonic): 674 """ 675 Return the name of a trace file for a given mnemonic. 676 """ 677 return self.test_type + "-" + self.test_name + "-" + \ 678 mnemonic.lower() + ".h" 679 680 def WriteEmptyTraces(self, output_directory): 681 """ 682 Write out empty trace files so we can compile the new test cases. 683 """ 684 for mnemonic in self.mnemonics: 685 # The MacroAssembler tests have no traces. 686 if self.test_type == "macro-assembler": continue 687 688 with open(os.path.join(output_directory, self.GetTraceFileName(mnemonic)), 689 "w") as f: 690 code = "static const TestResult *kReference{} = NULL;\n" 691 f.write(code.format(self.MnemonicToMethodName(mnemonic))) 692 693 def GetIsaGuard(self): 694 """ 695 This guard ensure the ISA of the test is enabled. 696 """ 697 if 'A32' in self.TestName(): 698 return 'VIXL_INCLUDE_TARGET_A32' 699 else: 700 assert 'T32' in self.TestName() 701 return 'VIXL_INCLUDE_TARGET_T32' 702 703