1 /****************************************************************************** 2 * 3 * Module Name: asltree - parse tree management 4 * 5 *****************************************************************************/ 6 7 /* 8 * Copyright (C) 2000 - 2015, Intel Corp. 9 * All rights reserved. 10 * 11 * Redistribution and use in source and binary forms, with or without 12 * modification, are permitted provided that the following conditions 13 * are met: 14 * 1. Redistributions of source code must retain the above copyright 15 * notice, this list of conditions, and the following disclaimer, 16 * without modification. 17 * 2. Redistributions in binary form must reproduce at minimum a disclaimer 18 * substantially similar to the "NO WARRANTY" disclaimer below 19 * ("Disclaimer") and any redistribution must be conditioned upon 20 * including a substantially similar Disclaimer requirement for further 21 * binary redistribution. 22 * 3. Neither the names of the above-listed copyright holders nor the names 23 * of any contributors may be used to endorse or promote products derived 24 * from this software without specific prior written permission. 25 * 26 * Alternatively, this software may be distributed under the terms of the 27 * GNU General Public License ("GPL") version 2 as published by the Free 28 * Software Foundation. 29 * 30 * NO WARRANTY 31 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 32 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 33 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR 34 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 35 * HOLDERS OR CONTRIBUTORS BE LIABLE FOR SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 36 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 37 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 38 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 39 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING 40 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 41 * POSSIBILITY OF SUCH DAMAGES. 42 */ 43 44 #include "aslcompiler.h" 45 #include "aslcompiler.y.h" 46 #include "acapps.h" 47 #include <time.h> 48 49 #define _COMPONENT ACPI_COMPILER 50 ACPI_MODULE_NAME ("asltree") 51 52 /* Local prototypes */ 53 54 static ACPI_PARSE_OBJECT * 55 TrGetNextNode ( 56 void); 57 58 59 /******************************************************************************* 60 * 61 * FUNCTION: TrGetNextNode 62 * 63 * PARAMETERS: None 64 * 65 * RETURN: New parse node. Aborts on allocation failure 66 * 67 * DESCRIPTION: Allocate a new parse node for the parse tree. Bypass the local 68 * dynamic memory manager for performance reasons (This has a 69 * major impact on the speed of the compiler.) 70 * 71 ******************************************************************************/ 72 73 static ACPI_PARSE_OBJECT * 74 TrGetNextNode ( 75 void) 76 { 77 ASL_CACHE_INFO *Cache; 78 79 80 if (Gbl_ParseOpCacheNext >= Gbl_ParseOpCacheLast) 81 { 82 /* Allocate a new buffer */ 83 84 Cache = UtLocalCalloc (sizeof (Cache->Next) + 85 (sizeof (ACPI_PARSE_OBJECT) * ASL_PARSEOP_CACHE_SIZE)); 86 87 /* Link new cache buffer to head of list */ 88 89 Cache->Next = Gbl_ParseOpCacheList; 90 Gbl_ParseOpCacheList = Cache; 91 92 /* Setup cache management pointers */ 93 94 Gbl_ParseOpCacheNext = ACPI_CAST_PTR (ACPI_PARSE_OBJECT, Cache->Buffer); 95 Gbl_ParseOpCacheLast = Gbl_ParseOpCacheNext + ASL_PARSEOP_CACHE_SIZE; 96 } 97 98 Gbl_ParseOpCount++; 99 return (Gbl_ParseOpCacheNext++); 100 } 101 102 103 /******************************************************************************* 104 * 105 * FUNCTION: TrAllocateNode 106 * 107 * PARAMETERS: ParseOpcode - Opcode to be assigned to the node 108 * 109 * RETURN: New parse node. Aborts on allocation failure 110 * 111 * DESCRIPTION: Allocate and initialize a new parse node for the parse tree 112 * 113 ******************************************************************************/ 114 115 ACPI_PARSE_OBJECT * 116 TrAllocateNode ( 117 UINT32 ParseOpcode) 118 { 119 ACPI_PARSE_OBJECT *Op; 120 121 122 Op = TrGetNextNode (); 123 124 Op->Asl.ParseOpcode = (UINT16) ParseOpcode; 125 Op->Asl.Filename = Gbl_Files[ASL_FILE_INPUT].Filename; 126 Op->Asl.LineNumber = Gbl_CurrentLineNumber; 127 Op->Asl.LogicalLineNumber = Gbl_LogicalLineNumber; 128 Op->Asl.LogicalByteOffset = Gbl_CurrentLineOffset; 129 Op->Asl.Column = Gbl_CurrentColumn; 130 131 UtSetParseOpName (Op); 132 return (Op); 133 } 134 135 136 /******************************************************************************* 137 * 138 * FUNCTION: TrReleaseNode 139 * 140 * PARAMETERS: Op - Op to be released 141 * 142 * RETURN: None 143 * 144 * DESCRIPTION: "release" a node. In truth, nothing is done since the node 145 * is part of a larger buffer 146 * 147 ******************************************************************************/ 148 149 void 150 TrReleaseNode ( 151 ACPI_PARSE_OBJECT *Op) 152 { 153 154 return; 155 } 156 157 158 /******************************************************************************* 159 * 160 * FUNCTION: TrUpdateNode 161 * 162 * PARAMETERS: ParseOpcode - New opcode to be assigned to the node 163 * Op - An existing parse node 164 * 165 * RETURN: The updated node 166 * 167 * DESCRIPTION: Change the parse opcode assigned to a node. Usually used to 168 * change an opcode to DEFAULT_ARG so that the node is ignored 169 * during the code generation. Also used to set generic integers 170 * to a specific size (8, 16, 32, or 64 bits) 171 * 172 ******************************************************************************/ 173 174 ACPI_PARSE_OBJECT * 175 TrUpdateNode ( 176 UINT32 ParseOpcode, 177 ACPI_PARSE_OBJECT *Op) 178 { 179 180 if (!Op) 181 { 182 return (NULL); 183 } 184 185 DbgPrint (ASL_PARSE_OUTPUT, 186 "\nUpdateNode: Old - %s, New - %s\n", 187 UtGetOpName (Op->Asl.ParseOpcode), 188 UtGetOpName (ParseOpcode)); 189 190 /* Assign new opcode and name */ 191 192 if (Op->Asl.ParseOpcode == PARSEOP_ONES) 193 { 194 switch (ParseOpcode) 195 { 196 case PARSEOP_BYTECONST: 197 198 Op->Asl.Value.Integer = ACPI_UINT8_MAX; 199 break; 200 201 case PARSEOP_WORDCONST: 202 203 Op->Asl.Value.Integer = ACPI_UINT16_MAX; 204 break; 205 206 case PARSEOP_DWORDCONST: 207 208 Op->Asl.Value.Integer = ACPI_UINT32_MAX; 209 break; 210 211 /* Don't need to do the QWORD case */ 212 213 default: 214 215 /* Don't care about others */ 216 break; 217 } 218 } 219 220 Op->Asl.ParseOpcode = (UINT16) ParseOpcode; 221 UtSetParseOpName (Op); 222 223 /* 224 * For the BYTE, WORD, and DWORD constants, make sure that the integer 225 * that was passed in will actually fit into the data type 226 */ 227 switch (ParseOpcode) 228 { 229 case PARSEOP_BYTECONST: 230 231 UtCheckIntegerRange (Op, 0x00, ACPI_UINT8_MAX); 232 Op->Asl.Value.Integer &= ACPI_UINT8_MAX; 233 break; 234 235 case PARSEOP_WORDCONST: 236 237 UtCheckIntegerRange (Op, 0x00, ACPI_UINT16_MAX); 238 Op->Asl.Value.Integer &= ACPI_UINT16_MAX; 239 break; 240 241 case PARSEOP_DWORDCONST: 242 243 UtCheckIntegerRange (Op, 0x00, ACPI_UINT32_MAX); 244 Op->Asl.Value.Integer &= ACPI_UINT32_MAX; 245 break; 246 247 default: 248 249 /* Don't care about others, don't need to check QWORD */ 250 251 break; 252 } 253 254 return (Op); 255 } 256 257 258 /******************************************************************************* 259 * 260 * FUNCTION: TrPrintNodeCompileFlags 261 * 262 * PARAMETERS: Flags - Flags word to be decoded 263 * 264 * RETURN: None 265 * 266 * DESCRIPTION: Decode a flags word to text. Displays all flags that are set. 267 * 268 ******************************************************************************/ 269 270 void 271 TrPrintNodeCompileFlags ( 272 UINT32 Flags) 273 { 274 UINT32 i; 275 UINT32 FlagBit = 1; 276 char *FlagName = NULL; 277 278 279 for (i = 0; i < 32; i++) 280 { 281 switch (Flags & FlagBit) 282 { 283 case NODE_VISITED: 284 285 FlagName = "NODE_VISITED"; 286 break; 287 288 case NODE_AML_PACKAGE: 289 290 FlagName = "NODE_AML_PACKAGE"; 291 break; 292 293 case NODE_IS_TARGET: 294 295 FlagName = "NODE_IS_TARGET"; 296 break; 297 298 case NODE_IS_RESOURCE_DESC: 299 300 FlagName = "NODE_IS_RESOURCE_DESC"; 301 break; 302 303 case NODE_IS_RESOURCE_FIELD: 304 305 FlagName = "NODE_IS_RESOURCE_FIELD"; 306 break; 307 308 case NODE_HAS_NO_EXIT: 309 310 FlagName = "NODE_HAS_NO_EXIT"; 311 break; 312 313 case NODE_IF_HAS_NO_EXIT: 314 315 FlagName = "NODE_IF_HAS_NO_EXIT"; 316 break; 317 318 case NODE_NAME_INTERNALIZED: 319 320 FlagName = "NODE_NAME_INTERNALIZED"; 321 break; 322 323 case NODE_METHOD_NO_RETVAL: 324 325 FlagName = "NODE_METHOD_NO_RETVAL"; 326 break; 327 328 case NODE_METHOD_SOME_NO_RETVAL: 329 330 FlagName = "NODE_METHOD_SOME_NO_RETVAL"; 331 break; 332 333 case NODE_RESULT_NOT_USED: 334 335 FlagName = "NODE_RESULT_NOT_USED"; 336 break; 337 338 case NODE_METHOD_TYPED: 339 340 FlagName = "NODE_METHOD_TYPED"; 341 break; 342 343 case NODE_COULD_NOT_REDUCE: 344 345 FlagName = "NODE_COULD_NOT_REDUCE"; 346 break; 347 348 case NODE_COMPILE_TIME_CONST: 349 350 FlagName = "NODE_COMPILE_TIME_CONST"; 351 break; 352 353 case NODE_IS_TERM_ARG: 354 355 FlagName = "NODE_IS_TERM_ARG"; 356 break; 357 358 case NODE_WAS_ONES_OP: 359 360 FlagName = "NODE_WAS_ONES_OP"; 361 break; 362 363 case NODE_IS_NAME_DECLARATION: 364 365 FlagName = "NODE_IS_NAME_DECLARATION"; 366 break; 367 368 case NODE_COMPILER_EMITTED: 369 370 FlagName = "NODE_COMPILER_EMITTED"; 371 break; 372 373 case NODE_IS_DUPLICATE: 374 375 FlagName = "NODE_IS_DUPLICATE"; 376 break; 377 378 case NODE_IS_RESOURCE_DATA: 379 380 FlagName = "NODE_IS_RESOURCE_DATA"; 381 break; 382 383 case NODE_IS_NULL_RETURN: 384 385 FlagName = "NODE_IS_NULL_RETURN"; 386 break; 387 388 default: 389 break; 390 } 391 392 if (FlagName) 393 { 394 DbgPrint (ASL_PARSE_OUTPUT, " %s", FlagName); 395 FlagName = NULL; 396 } 397 398 FlagBit <<= 1; 399 } 400 } 401 402 403 /******************************************************************************* 404 * 405 * FUNCTION: TrSetNodeFlags 406 * 407 * PARAMETERS: Op - An existing parse node 408 * Flags - New flags word 409 * 410 * RETURN: The updated parser op 411 * 412 * DESCRIPTION: Set bits in the node flags word. Will not clear bits, only set 413 * 414 ******************************************************************************/ 415 416 ACPI_PARSE_OBJECT * 417 TrSetNodeFlags ( 418 ACPI_PARSE_OBJECT *Op, 419 UINT32 Flags) 420 { 421 422 if (!Op) 423 { 424 return (NULL); 425 } 426 427 DbgPrint (ASL_PARSE_OUTPUT, 428 "\nSetNodeFlags: %s Op %p, %8.8X", Op->Asl.ParseOpName, Op, Flags); 429 430 TrPrintNodeCompileFlags (Flags); 431 DbgPrint (ASL_PARSE_OUTPUT, "\n\n"); 432 433 Op->Asl.CompileFlags |= Flags; 434 return (Op); 435 } 436 437 438 /******************************************************************************* 439 * 440 * FUNCTION: TrSetNodeAmlLength 441 * 442 * PARAMETERS: Op - An existing parse node 443 * Length - AML Length 444 * 445 * RETURN: The updated parser op 446 * 447 * DESCRIPTION: Set the AML Length in a node. Used by the parser to indicate 448 * the presence of a node that must be reduced to a fixed length 449 * constant. 450 * 451 ******************************************************************************/ 452 453 ACPI_PARSE_OBJECT * 454 TrSetNodeAmlLength ( 455 ACPI_PARSE_OBJECT *Op, 456 UINT32 Length) 457 { 458 459 DbgPrint (ASL_PARSE_OUTPUT, 460 "\nSetNodeAmlLength: Op %p, %8.8X\n", Op, Length); 461 462 if (!Op) 463 { 464 return (NULL); 465 } 466 467 Op->Asl.AmlLength = Length; 468 return (Op); 469 } 470 471 472 /******************************************************************************* 473 * 474 * FUNCTION: TrSetEndLineNumber 475 * 476 * PARAMETERS: Op - An existing parse node 477 * 478 * RETURN: None. 479 * 480 * DESCRIPTION: Set the ending line numbers (file line and logical line) of a 481 * parse node to the current line numbers. 482 * 483 ******************************************************************************/ 484 485 void 486 TrSetEndLineNumber ( 487 ACPI_PARSE_OBJECT *Op) 488 { 489 490 /* If the end line # is already set, just return */ 491 492 if (Op->Asl.EndLine) 493 { 494 return; 495 } 496 497 Op->Asl.EndLine = Gbl_CurrentLineNumber; 498 Op->Asl.EndLogicalLine = Gbl_LogicalLineNumber; 499 } 500 501 502 /******************************************************************************* 503 * 504 * FUNCTION: TrCreateAssignmentNode 505 * 506 * PARAMETERS: Target - Assignment target 507 * Source - Assignment source 508 * 509 * RETURN: Pointer to the new node. Aborts on allocation failure 510 * 511 * DESCRIPTION: Implements the C-style '=' operator. It changes the parse 512 * tree if possible to utilize the last argument of the math 513 * operators which is a target operand -- thus saving invocation 514 * of and additional Store() operator. An optimization. 515 * 516 ******************************************************************************/ 517 518 ACPI_PARSE_OBJECT * 519 TrCreateAssignmentNode ( 520 ACPI_PARSE_OBJECT *Target, 521 ACPI_PARSE_OBJECT *Source) 522 { 523 ACPI_PARSE_OBJECT *TargetOp; 524 ACPI_PARSE_OBJECT *SourceOp1; 525 ACPI_PARSE_OBJECT *SourceOp2; 526 ACPI_PARSE_OBJECT *Operator; 527 528 529 DbgPrint (ASL_PARSE_OUTPUT, 530 "\nTrCreateAssignmentNode Line [%u to %u] Source %s Target %s\n", 531 Source->Asl.LineNumber, Source->Asl.EndLine, 532 UtGetOpName (Source->Asl.ParseOpcode), 533 UtGetOpName (Target->Asl.ParseOpcode)); 534 535 TrSetNodeFlags (Target, NODE_IS_TARGET); 536 537 switch (Source->Asl.ParseOpcode) 538 { 539 /* 540 * Only these operators can be optimized because they have 541 * a target operand 542 */ 543 case PARSEOP_ADD: 544 case PARSEOP_AND: 545 case PARSEOP_DIVIDE: 546 case PARSEOP_INDEX: 547 case PARSEOP_MOD: 548 case PARSEOP_MULTIPLY: 549 case PARSEOP_NOT: 550 case PARSEOP_OR: 551 case PARSEOP_SHIFTLEFT: 552 case PARSEOP_SHIFTRIGHT: 553 case PARSEOP_SUBTRACT: 554 case PARSEOP_XOR: 555 556 break; 557 558 /* Otherwise, just create a normal Store operator */ 559 560 default: 561 562 goto CannotOptimize; 563 } 564 565 /* 566 * Transform the parse tree such that the target is moved to the 567 * last operand of the operator 568 */ 569 SourceOp1 = Source->Asl.Child; 570 SourceOp2 = SourceOp1->Asl.Next; 571 572 /* NOT only has one operand, but has a target */ 573 574 if (Source->Asl.ParseOpcode == PARSEOP_NOT) 575 { 576 SourceOp2 = SourceOp1; 577 } 578 579 /* DIVIDE has an extra target operand (remainder) */ 580 581 if (Source->Asl.ParseOpcode == PARSEOP_DIVIDE) 582 { 583 SourceOp2 = SourceOp2->Asl.Next; 584 } 585 586 TargetOp = SourceOp2->Asl.Next; 587 588 /* 589 * Can't perform this optimization if there already is a target 590 * for the operator (ZERO is a "no target" placeholder). 591 */ 592 if (TargetOp->Asl.ParseOpcode != PARSEOP_ZERO) 593 { 594 goto CannotOptimize; 595 } 596 597 /* Link in the target as the final operand */ 598 599 SourceOp2->Asl.Next = Target; 600 Target->Asl.Parent = Source; 601 602 return (Source); 603 604 605 CannotOptimize: 606 607 Operator = TrAllocateNode (PARSEOP_STORE); 608 TrLinkChildren (Operator, 2, Source, Target); 609 610 /* Set the appropriate line numbers for the new node */ 611 612 Operator->Asl.LineNumber = Target->Asl.LineNumber; 613 Operator->Asl.LogicalLineNumber = Target->Asl.LogicalLineNumber; 614 Operator->Asl.LogicalByteOffset = Target->Asl.LogicalByteOffset; 615 Operator->Asl.Column = Target->Asl.Column; 616 617 return (Operator); 618 } 619 620 621 /******************************************************************************* 622 * 623 * FUNCTION: TrCreateLeafNode 624 * 625 * PARAMETERS: ParseOpcode - New opcode to be assigned to the node 626 * 627 * RETURN: Pointer to the new node. Aborts on allocation failure 628 * 629 * DESCRIPTION: Create a simple leaf node (no children or peers, and no value 630 * assigned to the node) 631 * 632 ******************************************************************************/ 633 634 ACPI_PARSE_OBJECT * 635 TrCreateLeafNode ( 636 UINT32 ParseOpcode) 637 { 638 ACPI_PARSE_OBJECT *Op; 639 640 641 Op = TrAllocateNode (ParseOpcode); 642 643 DbgPrint (ASL_PARSE_OUTPUT, 644 "\nCreateLeafNode Ln/Col %u/%u NewNode %p Op %s\n\n", 645 Op->Asl.LineNumber, Op->Asl.Column, Op, UtGetOpName (ParseOpcode)); 646 647 return (Op); 648 } 649 650 651 /******************************************************************************* 652 * 653 * FUNCTION: TrCreateNullTarget 654 * 655 * PARAMETERS: None 656 * 657 * RETURN: Pointer to the new node. Aborts on allocation failure 658 * 659 * DESCRIPTION: Create a "null" target node. This is defined by the ACPI 660 * specification to be a zero AML opcode, and indicates that 661 * no target has been specified for the parent operation 662 * 663 ******************************************************************************/ 664 665 ACPI_PARSE_OBJECT * 666 TrCreateNullTarget ( 667 void) 668 { 669 ACPI_PARSE_OBJECT *Op; 670 671 672 Op = TrAllocateNode (PARSEOP_ZERO); 673 Op->Asl.CompileFlags |= (NODE_IS_TARGET | NODE_COMPILE_TIME_CONST); 674 675 DbgPrint (ASL_PARSE_OUTPUT, 676 "\nCreateNullTarget Ln/Col %u/%u NewNode %p Op %s\n", 677 Op->Asl.LineNumber, Op->Asl.Column, Op, 678 UtGetOpName (Op->Asl.ParseOpcode)); 679 680 return (Op); 681 } 682 683 684 /******************************************************************************* 685 * 686 * FUNCTION: TrCreateConstantLeafNode 687 * 688 * PARAMETERS: ParseOpcode - The constant opcode 689 * 690 * RETURN: Pointer to the new node. Aborts on allocation failure 691 * 692 * DESCRIPTION: Create a leaf node (no children or peers) for one of the 693 * special constants - __LINE__, __FILE__, and __DATE__. 694 * 695 * Note: An implemenation of __FUNC__ cannot happen here because we don't 696 * have a full parse tree at this time and cannot find the parent control 697 * method. If it is ever needed, __FUNC__ must be implemented later, after 698 * the parse tree has been fully constructed. 699 * 700 ******************************************************************************/ 701 702 ACPI_PARSE_OBJECT * 703 TrCreateConstantLeafNode ( 704 UINT32 ParseOpcode) 705 { 706 ACPI_PARSE_OBJECT *Op = NULL; 707 time_t CurrentTime; 708 char *StaticTimeString; 709 char *TimeString; 710 char *Filename; 711 712 713 switch (ParseOpcode) 714 { 715 case PARSEOP___LINE__: 716 717 Op = TrAllocateNode (PARSEOP_INTEGER); 718 Op->Asl.Value.Integer = Op->Asl.LineNumber; 719 break; 720 721 case PARSEOP___PATH__: 722 723 Op = TrAllocateNode (PARSEOP_STRING_LITERAL); 724 725 /* Op.Asl.Filename contains the full pathname to the file */ 726 727 Op->Asl.Value.String = Op->Asl.Filename; 728 break; 729 730 case PARSEOP___FILE__: 731 732 Op = TrAllocateNode (PARSEOP_STRING_LITERAL); 733 734 /* Get the simple filename from the full path */ 735 736 FlSplitInputPathname (Op->Asl.Filename, NULL, &Filename); 737 Op->Asl.Value.String = Filename; 738 break; 739 740 case PARSEOP___DATE__: 741 742 Op = TrAllocateNode (PARSEOP_STRING_LITERAL); 743 744 /* Get a copy of the current time */ 745 746 CurrentTime = time (NULL); 747 StaticTimeString = ctime (&CurrentTime); 748 TimeString = UtLocalCalloc (strlen (StaticTimeString) + 1); 749 strcpy (TimeString, StaticTimeString); 750 751 TimeString[strlen(TimeString) -1] = 0; /* Remove trailing newline */ 752 Op->Asl.Value.String = TimeString; 753 break; 754 755 default: /* This would be an internal error */ 756 757 return (NULL); 758 } 759 760 DbgPrint (ASL_PARSE_OUTPUT, 761 "\nCreateConstantLeafNode Ln/Col %u/%u NewNode %p " 762 "Op %s Value %8.8X%8.8X \n", 763 Op->Asl.LineNumber, Op->Asl.Column, Op, UtGetOpName (ParseOpcode), 764 ACPI_FORMAT_UINT64 (Op->Asl.Value.Integer)); 765 return (Op); 766 } 767 768 769 /******************************************************************************* 770 * 771 * FUNCTION: TrCreateTargetOperand 772 * 773 * PARAMETERS: OriginalOp - Op to be copied 774 * 775 * RETURN: Pointer to the new node. Aborts on allocation failure 776 * 777 * DESCRIPTION: Copy an existing node (and subtree). Used in ASL+ (C-style) 778 * expressions where the target is the same as one of the 779 * operands. A new node and subtree must be created from the 780 * original so that the parse tree can be linked properly. 781 * 782 * NOTE: This code is specific to target operands that are the last 783 * operand in an ASL/AML operator. Meaning that the top-level 784 * parse Op in a possible subtree has a NULL Next pointer. 785 * This simplifies the recursion. 786 * 787 * Subtree example: 788 * DeRefOf (Local1) += 32 789 * 790 * This gets converted to: 791 * Add (DeRefOf (Local1), 32, DeRefOf (Local1)) 792 * 793 * Each DeRefOf has a single child, Local1. Even more complex 794 * subtrees can be created via the Index and DeRefOf operators. 795 * 796 ******************************************************************************/ 797 798 ACPI_PARSE_OBJECT * 799 TrCreateTargetOperand ( 800 ACPI_PARSE_OBJECT *OriginalOp, 801 ACPI_PARSE_OBJECT *ParentOp) 802 { 803 ACPI_PARSE_OBJECT *Op; 804 805 806 if (!OriginalOp) 807 { 808 return (NULL); 809 } 810 811 Op = TrGetNextNode (); 812 813 /* Copy the pertinent values (omit link pointer fields) */ 814 815 Op->Asl.Value = OriginalOp->Asl.Value; 816 Op->Asl.Filename = OriginalOp->Asl.Filename; 817 Op->Asl.LineNumber = OriginalOp->Asl.LineNumber; 818 Op->Asl.LogicalLineNumber = OriginalOp->Asl.LogicalLineNumber; 819 Op->Asl.LogicalByteOffset = OriginalOp->Asl.LogicalByteOffset; 820 Op->Asl.Column = OriginalOp->Asl.Column; 821 Op->Asl.Flags = OriginalOp->Asl.Flags; 822 Op->Asl.CompileFlags = OriginalOp->Asl.CompileFlags; 823 Op->Asl.AmlOpcode = OriginalOp->Asl.AmlOpcode; 824 Op->Asl.ParseOpcode = OriginalOp->Asl.ParseOpcode; 825 Op->Asl.Parent = ParentOp; 826 UtSetParseOpName (Op); 827 828 /* Copy a possible subtree below this node */ 829 830 if (OriginalOp->Asl.Child) 831 { 832 Op->Asl.Child = TrCreateTargetOperand (OriginalOp->Asl.Child, Op); 833 } 834 835 if (OriginalOp->Asl.Next) /* Null for top-level node */ 836 { 837 Op->Asl.Next = TrCreateTargetOperand (OriginalOp->Asl.Next, ParentOp); 838 } 839 840 return (Op); 841 } 842 843 844 /******************************************************************************* 845 * 846 * FUNCTION: TrCreateValuedLeafNode 847 * 848 * PARAMETERS: ParseOpcode - New opcode to be assigned to the node 849 * Value - Value to be assigned to the node 850 * 851 * RETURN: Pointer to the new node. Aborts on allocation failure 852 * 853 * DESCRIPTION: Create a leaf node (no children or peers) with a value 854 * assigned to it 855 * 856 ******************************************************************************/ 857 858 ACPI_PARSE_OBJECT * 859 TrCreateValuedLeafNode ( 860 UINT32 ParseOpcode, 861 UINT64 Value) 862 { 863 ACPI_PARSE_OBJECT *Op; 864 865 866 Op = TrAllocateNode (ParseOpcode); 867 868 DbgPrint (ASL_PARSE_OUTPUT, 869 "\nCreateValuedLeafNode Ln/Col %u/%u NewNode %p " 870 "Op %s Value %8.8X%8.8X ", 871 Op->Asl.LineNumber, Op->Asl.Column, Op, UtGetOpName(ParseOpcode), 872 ACPI_FORMAT_UINT64 (Value)); 873 Op->Asl.Value.Integer = Value; 874 875 switch (ParseOpcode) 876 { 877 case PARSEOP_STRING_LITERAL: 878 879 DbgPrint (ASL_PARSE_OUTPUT, "STRING->%s", Value); 880 break; 881 882 case PARSEOP_NAMESEG: 883 884 DbgPrint (ASL_PARSE_OUTPUT, "NAMESEG->%s", Value); 885 break; 886 887 case PARSEOP_NAMESTRING: 888 889 DbgPrint (ASL_PARSE_OUTPUT, "NAMESTRING->%s", Value); 890 break; 891 892 case PARSEOP_EISAID: 893 894 DbgPrint (ASL_PARSE_OUTPUT, "EISAID->%s", Value); 895 break; 896 897 case PARSEOP_METHOD: 898 899 DbgPrint (ASL_PARSE_OUTPUT, "METHOD"); 900 break; 901 902 case PARSEOP_INTEGER: 903 904 DbgPrint (ASL_PARSE_OUTPUT, "INTEGER->%8.8X%8.8X", 905 ACPI_FORMAT_UINT64 (Value)); 906 break; 907 908 default: 909 910 break; 911 } 912 913 DbgPrint (ASL_PARSE_OUTPUT, "\n\n"); 914 return (Op); 915 } 916 917 918 /******************************************************************************* 919 * 920 * FUNCTION: TrCreateNode 921 * 922 * PARAMETERS: ParseOpcode - Opcode to be assigned to the node 923 * NumChildren - Number of children to follow 924 * ... - A list of child nodes to link to the new 925 * node. NumChildren long. 926 * 927 * RETURN: Pointer to the new node. Aborts on allocation failure 928 * 929 * DESCRIPTION: Create a new parse node and link together a list of child 930 * nodes underneath the new node. 931 * 932 ******************************************************************************/ 933 934 ACPI_PARSE_OBJECT * 935 TrCreateNode ( 936 UINT32 ParseOpcode, 937 UINT32 NumChildren, 938 ...) 939 { 940 ACPI_PARSE_OBJECT *Op; 941 ACPI_PARSE_OBJECT *Child; 942 ACPI_PARSE_OBJECT *PrevChild; 943 va_list ap; 944 UINT32 i; 945 BOOLEAN FirstChild; 946 947 948 va_start (ap, NumChildren); 949 950 /* Allocate one new node */ 951 952 Op = TrAllocateNode (ParseOpcode); 953 954 DbgPrint (ASL_PARSE_OUTPUT, 955 "\nCreateNode Ln/Col %u/%u NewParent %p Child %u Op %s ", 956 Op->Asl.LineNumber, Op->Asl.Column, Op, 957 NumChildren, UtGetOpName(ParseOpcode)); 958 959 /* Some extra debug output based on the parse opcode */ 960 961 switch (ParseOpcode) 962 { 963 case PARSEOP_ASL_CODE: 964 965 RootNode = Op; 966 Op->Asl.ParseOpcode = PARSEOP_DEFAULT_ARG; 967 DbgPrint (ASL_PARSE_OUTPUT, "ASLCODE (Tree Completed)->"); 968 break; 969 970 case PARSEOP_DEFINITION_BLOCK: 971 972 DbgPrint (ASL_PARSE_OUTPUT, "DEFINITION_BLOCK (Tree Completed)->"); 973 break; 974 975 case PARSEOP_OPERATIONREGION: 976 977 DbgPrint (ASL_PARSE_OUTPUT, "OPREGION->"); 978 break; 979 980 case PARSEOP_OR: 981 982 DbgPrint (ASL_PARSE_OUTPUT, "OR->"); 983 break; 984 985 default: 986 987 /* Nothing to do for other opcodes */ 988 989 break; 990 } 991 992 /* Link the new node to its children */ 993 994 PrevChild = NULL; 995 FirstChild = TRUE; 996 for (i = 0; i < NumChildren; i++) 997 { 998 /* Get the next child */ 999 1000 Child = va_arg (ap, ACPI_PARSE_OBJECT *); 1001 DbgPrint (ASL_PARSE_OUTPUT, "%p, ", Child); 1002 1003 /* 1004 * If child is NULL, this means that an optional argument 1005 * was omitted. We must create a placeholder with a special 1006 * opcode (DEFAULT_ARG) so that the code generator will know 1007 * that it must emit the correct default for this argument 1008 */ 1009 if (!Child) 1010 { 1011 Child = TrAllocateNode (PARSEOP_DEFAULT_ARG); 1012 } 1013 1014 /* Link first child to parent */ 1015 1016 if (FirstChild) 1017 { 1018 FirstChild = FALSE; 1019 Op->Asl.Child = Child; 1020 } 1021 1022 /* Point all children to parent */ 1023 1024 Child->Asl.Parent = Op; 1025 1026 /* Link children in a peer list */ 1027 1028 if (PrevChild) 1029 { 1030 PrevChild->Asl.Next = Child; 1031 }; 1032 1033 /* 1034 * This child might be a list, point all nodes in the list 1035 * to the same parent 1036 */ 1037 while (Child->Asl.Next) 1038 { 1039 Child = Child->Asl.Next; 1040 Child->Asl.Parent = Op; 1041 } 1042 1043 PrevChild = Child; 1044 } 1045 va_end(ap); 1046 1047 DbgPrint (ASL_PARSE_OUTPUT, "\n"); 1048 return (Op); 1049 } 1050 1051 1052 /******************************************************************************* 1053 * 1054 * FUNCTION: TrLinkChildren 1055 * 1056 * PARAMETERS: Op - An existing parse node 1057 * NumChildren - Number of children to follow 1058 * ... - A list of child nodes to link to the new 1059 * node. NumChildren long. 1060 * 1061 * RETURN: The updated (linked) node 1062 * 1063 * DESCRIPTION: Link a group of nodes to an existing parse node 1064 * 1065 ******************************************************************************/ 1066 1067 ACPI_PARSE_OBJECT * 1068 TrLinkChildren ( 1069 ACPI_PARSE_OBJECT *Op, 1070 UINT32 NumChildren, 1071 ...) 1072 { 1073 ACPI_PARSE_OBJECT *Child; 1074 ACPI_PARSE_OBJECT *PrevChild; 1075 va_list ap; 1076 UINT32 i; 1077 BOOLEAN FirstChild; 1078 1079 1080 va_start (ap, NumChildren); 1081 1082 1083 TrSetEndLineNumber (Op); 1084 1085 DbgPrint (ASL_PARSE_OUTPUT, 1086 "\nLinkChildren Line [%u to %u] NewParent %p Child %u Op %s ", 1087 Op->Asl.LineNumber, Op->Asl.EndLine, 1088 Op, NumChildren, UtGetOpName(Op->Asl.ParseOpcode)); 1089 1090 switch (Op->Asl.ParseOpcode) 1091 { 1092 case PARSEOP_ASL_CODE: 1093 1094 RootNode = Op; 1095 Op->Asl.ParseOpcode = PARSEOP_DEFAULT_ARG; 1096 DbgPrint (ASL_PARSE_OUTPUT, "ASLCODE (Tree Completed)->"); 1097 break; 1098 1099 case PARSEOP_DEFINITION_BLOCK: 1100 1101 DbgPrint (ASL_PARSE_OUTPUT, "DEFINITION_BLOCK (Tree Completed)->"); 1102 break; 1103 1104 case PARSEOP_OPERATIONREGION: 1105 1106 DbgPrint (ASL_PARSE_OUTPUT, "OPREGION->"); 1107 break; 1108 1109 case PARSEOP_OR: 1110 1111 DbgPrint (ASL_PARSE_OUTPUT, "OR->"); 1112 break; 1113 1114 default: 1115 1116 /* Nothing to do for other opcodes */ 1117 1118 break; 1119 } 1120 1121 /* Link the new node to it's children */ 1122 1123 PrevChild = NULL; 1124 FirstChild = TRUE; 1125 for (i = 0; i < NumChildren; i++) 1126 { 1127 Child = va_arg (ap, ACPI_PARSE_OBJECT *); 1128 1129 if ((Child == PrevChild) && (Child != NULL)) 1130 { 1131 AslError (ASL_WARNING, ASL_MSG_COMPILER_INTERNAL, Child, 1132 "Child node list invalid"); 1133 va_end(ap); 1134 return (Op); 1135 } 1136 1137 DbgPrint (ASL_PARSE_OUTPUT, "%p, ", Child); 1138 1139 /* 1140 * If child is NULL, this means that an optional argument 1141 * was omitted. We must create a placeholder with a special 1142 * opcode (DEFAULT_ARG) so that the code generator will know 1143 * that it must emit the correct default for this argument 1144 */ 1145 if (!Child) 1146 { 1147 Child = TrAllocateNode (PARSEOP_DEFAULT_ARG); 1148 } 1149 1150 /* Link first child to parent */ 1151 1152 if (FirstChild) 1153 { 1154 FirstChild = FALSE; 1155 Op->Asl.Child = Child; 1156 } 1157 1158 /* Point all children to parent */ 1159 1160 Child->Asl.Parent = Op; 1161 1162 /* Link children in a peer list */ 1163 1164 if (PrevChild) 1165 { 1166 PrevChild->Asl.Next = Child; 1167 }; 1168 1169 /* 1170 * This child might be a list, point all nodes in the list 1171 * to the same parent 1172 */ 1173 while (Child->Asl.Next) 1174 { 1175 Child = Child->Asl.Next; 1176 Child->Asl.Parent = Op; 1177 } 1178 1179 PrevChild = Child; 1180 } 1181 1182 va_end(ap); 1183 DbgPrint (ASL_PARSE_OUTPUT, "\n\n"); 1184 return (Op); 1185 } 1186 1187 1188 /******************************************************************************* 1189 * 1190 * FUNCTION: TrLinkPeerNode 1191 * 1192 * PARAMETERS: Op1 - First peer 1193 * Op2 - Second peer 1194 * 1195 * RETURN: Op1 or the non-null node. 1196 * 1197 * DESCRIPTION: Link two nodes as peers. Handles cases where one peer is null. 1198 * 1199 ******************************************************************************/ 1200 1201 ACPI_PARSE_OBJECT * 1202 TrLinkPeerNode ( 1203 ACPI_PARSE_OBJECT *Op1, 1204 ACPI_PARSE_OBJECT *Op2) 1205 { 1206 ACPI_PARSE_OBJECT *Next; 1207 1208 1209 DbgPrint (ASL_PARSE_OUTPUT, 1210 "\nLinkPeerNode: 1=%p (%s), 2=%p (%s)\n", 1211 Op1, Op1 ? UtGetOpName(Op1->Asl.ParseOpcode) : NULL, 1212 Op2, Op2 ? UtGetOpName(Op2->Asl.ParseOpcode) : NULL); 1213 1214 1215 if ((!Op1) && (!Op2)) 1216 { 1217 DbgPrint (ASL_PARSE_OUTPUT, "\nTwo Null nodes!\n"); 1218 return (Op1); 1219 } 1220 1221 /* If one of the nodes is null, just return the non-null node */ 1222 1223 if (!Op2) 1224 { 1225 return (Op1); 1226 } 1227 1228 if (!Op1) 1229 { 1230 return (Op2); 1231 } 1232 1233 if (Op1 == Op2) 1234 { 1235 DbgPrint (ASL_DEBUG_OUTPUT, 1236 "\n************* Internal error, linking node to itself %p\n", 1237 Op1); 1238 AslError (ASL_WARNING, ASL_MSG_COMPILER_INTERNAL, Op1, 1239 "Linking node to itself"); 1240 return (Op1); 1241 } 1242 1243 Op1->Asl.Parent = Op2->Asl.Parent; 1244 1245 /* 1246 * Op 1 may already have a peer list (such as an IF/ELSE pair), 1247 * so we must walk to the end of the list and attach the new 1248 * peer at the end 1249 */ 1250 Next = Op1; 1251 while (Next->Asl.Next) 1252 { 1253 Next = Next->Asl.Next; 1254 } 1255 1256 Next->Asl.Next = Op2; 1257 return (Op1); 1258 } 1259 1260 1261 /******************************************************************************* 1262 * 1263 * FUNCTION: TrLinkPeerNodes 1264 * 1265 * PARAMETERS: NumPeers - The number of nodes in the list to follow 1266 * ... - A list of nodes to link together as peers 1267 * 1268 * RETURN: The first node in the list (head of the peer list) 1269 * 1270 * DESCRIPTION: Link together an arbitrary number of peer nodes. 1271 * 1272 ******************************************************************************/ 1273 1274 ACPI_PARSE_OBJECT * 1275 TrLinkPeerNodes ( 1276 UINT32 NumPeers, 1277 ...) 1278 { 1279 ACPI_PARSE_OBJECT *This; 1280 ACPI_PARSE_OBJECT *Next; 1281 va_list ap; 1282 UINT32 i; 1283 ACPI_PARSE_OBJECT *Start; 1284 1285 1286 DbgPrint (ASL_PARSE_OUTPUT, 1287 "\nLinkPeerNodes: (%u) ", NumPeers); 1288 1289 va_start (ap, NumPeers); 1290 This = va_arg (ap, ACPI_PARSE_OBJECT *); 1291 Start = This; 1292 1293 /* 1294 * Link all peers 1295 */ 1296 for (i = 0; i < (NumPeers -1); i++) 1297 { 1298 DbgPrint (ASL_PARSE_OUTPUT, "%u=%p ", (i+1), This); 1299 1300 while (This->Asl.Next) 1301 { 1302 This = This->Asl.Next; 1303 } 1304 1305 /* Get another peer node */ 1306 1307 Next = va_arg (ap, ACPI_PARSE_OBJECT *); 1308 if (!Next) 1309 { 1310 Next = TrAllocateNode (PARSEOP_DEFAULT_ARG); 1311 } 1312 1313 /* link new node to the current node */ 1314 1315 This->Asl.Next = Next; 1316 This = Next; 1317 } 1318 va_end (ap); 1319 1320 DbgPrint (ASL_PARSE_OUTPUT,"\n"); 1321 return (Start); 1322 } 1323 1324 1325 /******************************************************************************* 1326 * 1327 * FUNCTION: TrLinkChildNode 1328 * 1329 * PARAMETERS: Op1 - Parent node 1330 * Op2 - Op to become a child 1331 * 1332 * RETURN: The parent node 1333 * 1334 * DESCRIPTION: Link two nodes together as a parent and child 1335 * 1336 ******************************************************************************/ 1337 1338 ACPI_PARSE_OBJECT * 1339 TrLinkChildNode ( 1340 ACPI_PARSE_OBJECT *Op1, 1341 ACPI_PARSE_OBJECT *Op2) 1342 { 1343 ACPI_PARSE_OBJECT *Next; 1344 1345 1346 DbgPrint (ASL_PARSE_OUTPUT, 1347 "\nLinkChildNode: Parent=%p (%s), Child=%p (%s)\n", 1348 Op1, Op1 ? UtGetOpName(Op1->Asl.ParseOpcode): NULL, 1349 Op2, Op2 ? UtGetOpName(Op2->Asl.ParseOpcode): NULL); 1350 1351 if (!Op1 || !Op2) 1352 { 1353 return (Op1); 1354 } 1355 1356 Op1->Asl.Child = Op2; 1357 1358 /* Set the child and all peers of the child to point to the parent */ 1359 1360 Next = Op2; 1361 while (Next) 1362 { 1363 Next->Asl.Parent = Op1; 1364 Next = Next->Asl.Next; 1365 } 1366 1367 return (Op1); 1368 } 1369 1370 1371 /******************************************************************************* 1372 * 1373 * FUNCTION: TrWalkParseTree 1374 * 1375 * PARAMETERS: Visitation - Type of walk 1376 * DescendingCallback - Called during tree descent 1377 * AscendingCallback - Called during tree ascent 1378 * Context - To be passed to the callbacks 1379 * 1380 * RETURN: Status from callback(s) 1381 * 1382 * DESCRIPTION: Walk the entire parse tree. 1383 * 1384 ******************************************************************************/ 1385 1386 ACPI_STATUS 1387 TrWalkParseTree ( 1388 ACPI_PARSE_OBJECT *Op, 1389 UINT32 Visitation, 1390 ASL_WALK_CALLBACK DescendingCallback, 1391 ASL_WALK_CALLBACK AscendingCallback, 1392 void *Context) 1393 { 1394 UINT32 Level; 1395 BOOLEAN NodePreviouslyVisited; 1396 ACPI_PARSE_OBJECT *StartOp = Op; 1397 ACPI_STATUS Status; 1398 1399 1400 if (!RootNode) 1401 { 1402 return (AE_OK); 1403 } 1404 1405 Level = 0; 1406 NodePreviouslyVisited = FALSE; 1407 1408 switch (Visitation) 1409 { 1410 case ASL_WALK_VISIT_DOWNWARD: 1411 1412 while (Op) 1413 { 1414 if (!NodePreviouslyVisited) 1415 { 1416 /* Let the callback process the node. */ 1417 1418 Status = DescendingCallback (Op, Level, Context); 1419 if (ACPI_SUCCESS (Status)) 1420 { 1421 /* Visit children first, once */ 1422 1423 if (Op->Asl.Child) 1424 { 1425 Level++; 1426 Op = Op->Asl.Child; 1427 continue; 1428 } 1429 } 1430 else if (Status != AE_CTRL_DEPTH) 1431 { 1432 /* Exit immediately on any error */ 1433 1434 return (Status); 1435 } 1436 } 1437 1438 /* Terminate walk at start op */ 1439 1440 if (Op == StartOp) 1441 { 1442 break; 1443 } 1444 1445 /* No more children, visit peers */ 1446 1447 if (Op->Asl.Next) 1448 { 1449 Op = Op->Asl.Next; 1450 NodePreviouslyVisited = FALSE; 1451 } 1452 else 1453 { 1454 /* No children or peers, re-visit parent */ 1455 1456 if (Level != 0 ) 1457 { 1458 Level--; 1459 } 1460 Op = Op->Asl.Parent; 1461 NodePreviouslyVisited = TRUE; 1462 } 1463 } 1464 break; 1465 1466 case ASL_WALK_VISIT_UPWARD: 1467 1468 while (Op) 1469 { 1470 /* Visit leaf node (no children) or parent node on return trip */ 1471 1472 if ((!Op->Asl.Child) || 1473 (NodePreviouslyVisited)) 1474 { 1475 /* Let the callback process the node. */ 1476 1477 Status = AscendingCallback (Op, Level, Context); 1478 if (ACPI_FAILURE (Status)) 1479 { 1480 return (Status); 1481 } 1482 } 1483 else 1484 { 1485 /* Visit children first, once */ 1486 1487 Level++; 1488 Op = Op->Asl.Child; 1489 continue; 1490 } 1491 1492 /* Terminate walk at start op */ 1493 1494 if (Op == StartOp) 1495 { 1496 break; 1497 } 1498 1499 /* No more children, visit peers */ 1500 1501 if (Op->Asl.Next) 1502 { 1503 Op = Op->Asl.Next; 1504 NodePreviouslyVisited = FALSE; 1505 } 1506 else 1507 { 1508 /* No children or peers, re-visit parent */ 1509 1510 if (Level != 0 ) 1511 { 1512 Level--; 1513 } 1514 Op = Op->Asl.Parent; 1515 NodePreviouslyVisited = TRUE; 1516 } 1517 } 1518 break; 1519 1520 case ASL_WALK_VISIT_TWICE: 1521 1522 while (Op) 1523 { 1524 if (NodePreviouslyVisited) 1525 { 1526 Status = AscendingCallback (Op, Level, Context); 1527 if (ACPI_FAILURE (Status)) 1528 { 1529 return (Status); 1530 } 1531 } 1532 else 1533 { 1534 /* Let the callback process the node. */ 1535 1536 Status = DescendingCallback (Op, Level, Context); 1537 if (ACPI_SUCCESS (Status)) 1538 { 1539 /* Visit children first, once */ 1540 1541 if (Op->Asl.Child) 1542 { 1543 Level++; 1544 Op = Op->Asl.Child; 1545 continue; 1546 } 1547 } 1548 else if (Status != AE_CTRL_DEPTH) 1549 { 1550 /* Exit immediately on any error */ 1551 1552 return (Status); 1553 } 1554 } 1555 1556 /* Terminate walk at start op */ 1557 1558 if (Op == StartOp) 1559 { 1560 break; 1561 } 1562 1563 /* No more children, visit peers */ 1564 1565 if (Op->Asl.Next) 1566 { 1567 Op = Op->Asl.Next; 1568 NodePreviouslyVisited = FALSE; 1569 } 1570 else 1571 { 1572 /* No children or peers, re-visit parent */ 1573 1574 if (Level != 0 ) 1575 { 1576 Level--; 1577 } 1578 Op = Op->Asl.Parent; 1579 NodePreviouslyVisited = TRUE; 1580 } 1581 } 1582 break; 1583 1584 default: 1585 /* No other types supported */ 1586 break; 1587 } 1588 1589 /* If we get here, the walk completed with no errors */ 1590 1591 return (AE_OK); 1592 } 1593