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_COMPILE_TIME_CONST: 344 345 FlagName = "NODE_COMPILE_TIME_CONST"; 346 break; 347 348 case NODE_IS_TERM_ARG: 349 350 FlagName = "NODE_IS_TERM_ARG"; 351 break; 352 353 case NODE_WAS_ONES_OP: 354 355 FlagName = "NODE_WAS_ONES_OP"; 356 break; 357 358 case NODE_IS_NAME_DECLARATION: 359 360 FlagName = "NODE_IS_NAME_DECLARATION"; 361 break; 362 363 case NODE_COMPILER_EMITTED: 364 365 FlagName = "NODE_COMPILER_EMITTED"; 366 break; 367 368 case NODE_IS_DUPLICATE: 369 370 FlagName = "NODE_IS_DUPLICATE"; 371 break; 372 373 case NODE_IS_RESOURCE_DATA: 374 375 FlagName = "NODE_IS_RESOURCE_DATA"; 376 break; 377 378 case NODE_IS_NULL_RETURN: 379 380 FlagName = "NODE_IS_NULL_RETURN"; 381 break; 382 383 default: 384 break; 385 } 386 387 if (FlagName) 388 { 389 DbgPrint (ASL_PARSE_OUTPUT, " %s", FlagName); 390 FlagName = NULL; 391 } 392 393 FlagBit <<= 1; 394 } 395 } 396 397 398 /******************************************************************************* 399 * 400 * FUNCTION: TrSetNodeFlags 401 * 402 * PARAMETERS: Op - An existing parse node 403 * Flags - New flags word 404 * 405 * RETURN: The updated parser op 406 * 407 * DESCRIPTION: Set bits in the node flags word. Will not clear bits, only set 408 * 409 ******************************************************************************/ 410 411 ACPI_PARSE_OBJECT * 412 TrSetNodeFlags ( 413 ACPI_PARSE_OBJECT *Op, 414 UINT32 Flags) 415 { 416 417 if (!Op) 418 { 419 return (NULL); 420 } 421 422 DbgPrint (ASL_PARSE_OUTPUT, 423 "\nSetNodeFlags: %s Op %p, %8.8X", Op->Asl.ParseOpName, Op, Flags); 424 425 TrPrintNodeCompileFlags (Flags); 426 DbgPrint (ASL_PARSE_OUTPUT, "\n\n"); 427 428 Op->Asl.CompileFlags |= Flags; 429 return (Op); 430 } 431 432 433 /******************************************************************************* 434 * 435 * FUNCTION: TrSetNodeAmlLength 436 * 437 * PARAMETERS: Op - An existing parse node 438 * Length - AML Length 439 * 440 * RETURN: The updated parser op 441 * 442 * DESCRIPTION: Set the AML Length in a node. Used by the parser to indicate 443 * the presence of a node that must be reduced to a fixed length 444 * constant. 445 * 446 ******************************************************************************/ 447 448 ACPI_PARSE_OBJECT * 449 TrSetNodeAmlLength ( 450 ACPI_PARSE_OBJECT *Op, 451 UINT32 Length) 452 { 453 454 DbgPrint (ASL_PARSE_OUTPUT, 455 "\nSetNodeAmlLength: Op %p, %8.8X\n", Op, Length); 456 457 if (!Op) 458 { 459 return (NULL); 460 } 461 462 Op->Asl.AmlLength = Length; 463 return (Op); 464 } 465 466 467 /******************************************************************************* 468 * 469 * FUNCTION: TrSetEndLineNumber 470 * 471 * PARAMETERS: Op - An existing parse node 472 * 473 * RETURN: None. 474 * 475 * DESCRIPTION: Set the ending line numbers (file line and logical line) of a 476 * parse node to the current line numbers. 477 * 478 ******************************************************************************/ 479 480 void 481 TrSetEndLineNumber ( 482 ACPI_PARSE_OBJECT *Op) 483 { 484 485 /* If the end line # is already set, just return */ 486 487 if (Op->Asl.EndLine) 488 { 489 return; 490 } 491 492 Op->Asl.EndLine = Gbl_CurrentLineNumber; 493 Op->Asl.EndLogicalLine = Gbl_LogicalLineNumber; 494 } 495 496 497 /******************************************************************************* 498 * 499 * FUNCTION: TrCreateAssignmentNode 500 * 501 * PARAMETERS: Target - Assignment target 502 * Source - Assignment source 503 * 504 * RETURN: Pointer to the new node. Aborts on allocation failure 505 * 506 * DESCRIPTION: Implements the C-style '=' operator. It changes the parse 507 * tree if possible to utilize the last argument of the math 508 * operators which is a target operand -- thus saving invocation 509 * of and additional Store() operator. An optimization. 510 * 511 ******************************************************************************/ 512 513 ACPI_PARSE_OBJECT * 514 TrCreateAssignmentNode ( 515 ACPI_PARSE_OBJECT *Target, 516 ACPI_PARSE_OBJECT *Source) 517 { 518 ACPI_PARSE_OBJECT *TargetOp; 519 ACPI_PARSE_OBJECT *SourceOp1; 520 ACPI_PARSE_OBJECT *SourceOp2; 521 ACPI_PARSE_OBJECT *Operator; 522 523 524 DbgPrint (ASL_PARSE_OUTPUT, 525 "\nTrCreateAssignmentNode Line [%u to %u] Source %s Target %s\n", 526 Source->Asl.LineNumber, Source->Asl.EndLine, 527 UtGetOpName (Source->Asl.ParseOpcode), 528 UtGetOpName (Target->Asl.ParseOpcode)); 529 530 TrSetNodeFlags (Target, NODE_IS_TARGET); 531 532 switch (Source->Asl.ParseOpcode) 533 { 534 /* 535 * Only these operators can be optimized because they have 536 * a target operand 537 */ 538 case PARSEOP_ADD: 539 case PARSEOP_AND: 540 case PARSEOP_DIVIDE: 541 case PARSEOP_INDEX: 542 case PARSEOP_MOD: 543 case PARSEOP_MULTIPLY: 544 case PARSEOP_NOT: 545 case PARSEOP_OR: 546 case PARSEOP_SHIFTLEFT: 547 case PARSEOP_SHIFTRIGHT: 548 case PARSEOP_SUBTRACT: 549 case PARSEOP_XOR: 550 551 break; 552 553 /* Otherwise, just create a normal Store operator */ 554 555 default: 556 557 goto CannotOptimize; 558 } 559 560 /* 561 * Transform the parse tree such that the target is moved to the 562 * last operand of the operator 563 */ 564 SourceOp1 = Source->Asl.Child; 565 SourceOp2 = SourceOp1->Asl.Next; 566 567 /* NOT only has one operand, but has a target */ 568 569 if (Source->Asl.ParseOpcode == PARSEOP_NOT) 570 { 571 SourceOp2 = SourceOp1; 572 } 573 574 /* DIVIDE has an extra target operand (remainder) */ 575 576 if (Source->Asl.ParseOpcode == PARSEOP_DIVIDE) 577 { 578 SourceOp2 = SourceOp2->Asl.Next; 579 } 580 581 TargetOp = SourceOp2->Asl.Next; 582 583 /* 584 * Can't perform this optimization if there already is a target 585 * for the operator (ZERO is a "no target" placeholder). 586 */ 587 if (TargetOp->Asl.ParseOpcode != PARSEOP_ZERO) 588 { 589 goto CannotOptimize; 590 } 591 592 /* Link in the target as the final operand */ 593 594 SourceOp2->Asl.Next = Target; 595 Target->Asl.Parent = Source; 596 597 return (Source); 598 599 600 CannotOptimize: 601 602 Operator = TrAllocateNode (PARSEOP_STORE); 603 TrLinkChildren (Operator, 2, Source, Target); 604 605 /* Set the appropriate line numbers for the new node */ 606 607 Operator->Asl.LineNumber = Target->Asl.LineNumber; 608 Operator->Asl.LogicalLineNumber = Target->Asl.LogicalLineNumber; 609 Operator->Asl.LogicalByteOffset = Target->Asl.LogicalByteOffset; 610 Operator->Asl.Column = Target->Asl.Column; 611 612 return (Operator); 613 } 614 615 616 /******************************************************************************* 617 * 618 * FUNCTION: TrCreateLeafNode 619 * 620 * PARAMETERS: ParseOpcode - New opcode to be assigned to the node 621 * 622 * RETURN: Pointer to the new node. Aborts on allocation failure 623 * 624 * DESCRIPTION: Create a simple leaf node (no children or peers, and no value 625 * assigned to the node) 626 * 627 ******************************************************************************/ 628 629 ACPI_PARSE_OBJECT * 630 TrCreateLeafNode ( 631 UINT32 ParseOpcode) 632 { 633 ACPI_PARSE_OBJECT *Op; 634 635 636 Op = TrAllocateNode (ParseOpcode); 637 638 DbgPrint (ASL_PARSE_OUTPUT, 639 "\nCreateLeafNode Ln/Col %u/%u NewNode %p Op %s\n\n", 640 Op->Asl.LineNumber, Op->Asl.Column, Op, UtGetOpName (ParseOpcode)); 641 642 return (Op); 643 } 644 645 646 /******************************************************************************* 647 * 648 * FUNCTION: TrCreateNullTarget 649 * 650 * PARAMETERS: None 651 * 652 * RETURN: Pointer to the new node. Aborts on allocation failure 653 * 654 * DESCRIPTION: Create a "null" target node. This is defined by the ACPI 655 * specification to be a zero AML opcode, and indicates that 656 * no target has been specified for the parent operation 657 * 658 ******************************************************************************/ 659 660 ACPI_PARSE_OBJECT * 661 TrCreateNullTarget ( 662 void) 663 { 664 ACPI_PARSE_OBJECT *Op; 665 666 667 Op = TrAllocateNode (PARSEOP_ZERO); 668 Op->Asl.CompileFlags |= (NODE_IS_TARGET | NODE_COMPILE_TIME_CONST); 669 670 DbgPrint (ASL_PARSE_OUTPUT, 671 "\nCreateNullTarget Ln/Col %u/%u NewNode %p Op %s\n", 672 Op->Asl.LineNumber, Op->Asl.Column, Op, 673 UtGetOpName (Op->Asl.ParseOpcode)); 674 675 return (Op); 676 } 677 678 679 /******************************************************************************* 680 * 681 * FUNCTION: TrCreateConstantLeafNode 682 * 683 * PARAMETERS: ParseOpcode - The constant opcode 684 * 685 * RETURN: Pointer to the new node. Aborts on allocation failure 686 * 687 * DESCRIPTION: Create a leaf node (no children or peers) for one of the 688 * special constants - __LINE__, __FILE__, and __DATE__. 689 * 690 * Note: An implemenation of __FUNC__ cannot happen here because we don't 691 * have a full parse tree at this time and cannot find the parent control 692 * method. If it is ever needed, __FUNC__ must be implemented later, after 693 * the parse tree has been fully constructed. 694 * 695 ******************************************************************************/ 696 697 ACPI_PARSE_OBJECT * 698 TrCreateConstantLeafNode ( 699 UINT32 ParseOpcode) 700 { 701 ACPI_PARSE_OBJECT *Op = NULL; 702 time_t CurrentTime; 703 char *StaticTimeString; 704 char *TimeString; 705 char *Filename; 706 707 708 switch (ParseOpcode) 709 { 710 case PARSEOP___LINE__: 711 712 Op = TrAllocateNode (PARSEOP_INTEGER); 713 Op->Asl.Value.Integer = Op->Asl.LineNumber; 714 break; 715 716 case PARSEOP___PATH__: 717 718 Op = TrAllocateNode (PARSEOP_STRING_LITERAL); 719 720 /* Op.Asl.Filename contains the full pathname to the file */ 721 722 Op->Asl.Value.String = Op->Asl.Filename; 723 break; 724 725 case PARSEOP___FILE__: 726 727 Op = TrAllocateNode (PARSEOP_STRING_LITERAL); 728 729 /* Get the simple filename from the full path */ 730 731 FlSplitInputPathname (Op->Asl.Filename, NULL, &Filename); 732 Op->Asl.Value.String = Filename; 733 break; 734 735 case PARSEOP___DATE__: 736 737 Op = TrAllocateNode (PARSEOP_STRING_LITERAL); 738 739 /* Get a copy of the current time */ 740 741 CurrentTime = time (NULL); 742 StaticTimeString = ctime (&CurrentTime); 743 TimeString = UtLocalCalloc (strlen (StaticTimeString) + 1); 744 strcpy (TimeString, StaticTimeString); 745 746 TimeString[strlen(TimeString) -1] = 0; /* Remove trailing newline */ 747 Op->Asl.Value.String = TimeString; 748 break; 749 750 default: /* This would be an internal error */ 751 752 return (NULL); 753 } 754 755 DbgPrint (ASL_PARSE_OUTPUT, 756 "\nCreateConstantLeafNode Ln/Col %u/%u NewNode %p Op %s Value %8.8X%8.8X \n", 757 Op->Asl.LineNumber, Op->Asl.Column, Op, UtGetOpName (ParseOpcode), 758 ACPI_FORMAT_UINT64 (Op->Asl.Value.Integer)); 759 return (Op); 760 } 761 762 763 /******************************************************************************* 764 * 765 * FUNCTION: TrCreateTargetOperand 766 * 767 * PARAMETERS: OriginalOp - Op to be copied 768 * 769 * RETURN: Pointer to the new node. Aborts on allocation failure 770 * 771 * DESCRIPTION: Copy an existing node (and subtree). Used in ASL+ (C-style) 772 * expressions where the target is the same as one of the 773 * operands. A new node and subtree must be created from the 774 * original so that the parse tree can be linked properly. 775 * 776 * NOTE: This code is specific to target operands that are the last 777 * operand in an ASL/AML operator. Meaning that the top-level 778 * parse Op in a possible subtree has a NULL Next pointer. 779 * This simplifies the recursion. 780 * 781 * Subtree example: 782 * DeRefOf (Local1) += 32 783 * 784 * This gets converted to: 785 * Add (DeRefOf (Local1), 32, DeRefOf (Local1)) 786 * 787 * Each DeRefOf has a single child, Local1. Even more complex 788 * subtrees can be created via the Index and DeRefOf operators. 789 * 790 ******************************************************************************/ 791 792 ACPI_PARSE_OBJECT * 793 TrCreateTargetOperand ( 794 ACPI_PARSE_OBJECT *OriginalOp, 795 ACPI_PARSE_OBJECT *ParentOp) 796 { 797 ACPI_PARSE_OBJECT *Op; 798 799 800 if (!OriginalOp) 801 { 802 return (NULL); 803 } 804 805 Op = TrGetNextNode (); 806 807 /* Copy the pertinent values (omit link pointer fields) */ 808 809 Op->Asl.Value = OriginalOp->Asl.Value; 810 Op->Asl.Filename = OriginalOp->Asl.Filename; 811 Op->Asl.LineNumber = OriginalOp->Asl.LineNumber; 812 Op->Asl.LogicalLineNumber = OriginalOp->Asl.LogicalLineNumber; 813 Op->Asl.LogicalByteOffset = OriginalOp->Asl.LogicalByteOffset; 814 Op->Asl.Column = OriginalOp->Asl.Column; 815 Op->Asl.Flags = OriginalOp->Asl.Flags; 816 Op->Asl.CompileFlags = OriginalOp->Asl.CompileFlags; 817 Op->Asl.AmlOpcode = OriginalOp->Asl.AmlOpcode; 818 Op->Asl.ParseOpcode = OriginalOp->Asl.ParseOpcode; 819 Op->Asl.Parent = ParentOp; 820 UtSetParseOpName (Op); 821 822 /* Copy a possible subtree below this node */ 823 824 if (OriginalOp->Asl.Child) 825 { 826 Op->Asl.Child = TrCreateTargetOperand (OriginalOp->Asl.Child, Op); 827 } 828 829 if (OriginalOp->Asl.Next) /* Null for top-level node */ 830 { 831 Op->Asl.Next = TrCreateTargetOperand (OriginalOp->Asl.Next, ParentOp); 832 } 833 834 return (Op); 835 } 836 837 838 /******************************************************************************* 839 * 840 * FUNCTION: TrCreateValuedLeafNode 841 * 842 * PARAMETERS: ParseOpcode - New opcode to be assigned to the node 843 * Value - Value to be assigned to the node 844 * 845 * RETURN: Pointer to the new node. Aborts on allocation failure 846 * 847 * DESCRIPTION: Create a leaf node (no children or peers) with a value 848 * assigned to it 849 * 850 ******************************************************************************/ 851 852 ACPI_PARSE_OBJECT * 853 TrCreateValuedLeafNode ( 854 UINT32 ParseOpcode, 855 UINT64 Value) 856 { 857 ACPI_PARSE_OBJECT *Op; 858 859 860 Op = TrAllocateNode (ParseOpcode); 861 862 DbgPrint (ASL_PARSE_OUTPUT, 863 "\nCreateValuedLeafNode Ln/Col %u/%u NewNode %p Op %s Value %8.8X%8.8X ", 864 Op->Asl.LineNumber, Op->Asl.Column, Op, UtGetOpName(ParseOpcode), 865 ACPI_FORMAT_UINT64 (Value)); 866 Op->Asl.Value.Integer = Value; 867 868 switch (ParseOpcode) 869 { 870 case PARSEOP_STRING_LITERAL: 871 872 DbgPrint (ASL_PARSE_OUTPUT, "STRING->%s", Value); 873 break; 874 875 case PARSEOP_NAMESEG: 876 877 DbgPrint (ASL_PARSE_OUTPUT, "NAMESEG->%s", Value); 878 break; 879 880 case PARSEOP_NAMESTRING: 881 882 DbgPrint (ASL_PARSE_OUTPUT, "NAMESTRING->%s", Value); 883 break; 884 885 case PARSEOP_EISAID: 886 887 DbgPrint (ASL_PARSE_OUTPUT, "EISAID->%s", Value); 888 break; 889 890 case PARSEOP_METHOD: 891 892 DbgPrint (ASL_PARSE_OUTPUT, "METHOD"); 893 break; 894 895 case PARSEOP_INTEGER: 896 897 DbgPrint (ASL_PARSE_OUTPUT, "INTEGER->%8.8X%8.8X", 898 ACPI_FORMAT_UINT64 (Value)); 899 break; 900 901 default: 902 903 break; 904 } 905 906 DbgPrint (ASL_PARSE_OUTPUT, "\n\n"); 907 return (Op); 908 } 909 910 911 /******************************************************************************* 912 * 913 * FUNCTION: TrCreateNode 914 * 915 * PARAMETERS: ParseOpcode - Opcode to be assigned to the node 916 * NumChildren - Number of children to follow 917 * ... - A list of child nodes to link to the new 918 * node. NumChildren long. 919 * 920 * RETURN: Pointer to the new node. Aborts on allocation failure 921 * 922 * DESCRIPTION: Create a new parse node and link together a list of child 923 * nodes underneath the new node. 924 * 925 ******************************************************************************/ 926 927 ACPI_PARSE_OBJECT * 928 TrCreateNode ( 929 UINT32 ParseOpcode, 930 UINT32 NumChildren, 931 ...) 932 { 933 ACPI_PARSE_OBJECT *Op; 934 ACPI_PARSE_OBJECT *Child; 935 ACPI_PARSE_OBJECT *PrevChild; 936 va_list ap; 937 UINT32 i; 938 BOOLEAN FirstChild; 939 940 941 va_start (ap, NumChildren); 942 943 /* Allocate one new node */ 944 945 Op = TrAllocateNode (ParseOpcode); 946 947 DbgPrint (ASL_PARSE_OUTPUT, 948 "\nCreateNode Ln/Col %u/%u NewParent %p Child %u Op %s ", 949 Op->Asl.LineNumber, Op->Asl.Column, Op, NumChildren, UtGetOpName(ParseOpcode)); 950 951 /* Some extra debug output based on the parse opcode */ 952 953 switch (ParseOpcode) 954 { 955 case PARSEOP_DEFINITIONBLOCK: 956 957 RootNode = Op; 958 DbgPrint (ASL_PARSE_OUTPUT, "DEFINITION_BLOCK (Tree Completed)->"); 959 break; 960 961 case PARSEOP_OPERATIONREGION: 962 963 DbgPrint (ASL_PARSE_OUTPUT, "OPREGION->"); 964 break; 965 966 case PARSEOP_OR: 967 968 DbgPrint (ASL_PARSE_OUTPUT, "OR->"); 969 break; 970 971 default: 972 973 /* Nothing to do for other opcodes */ 974 975 break; 976 } 977 978 /* Link the new node to its children */ 979 980 PrevChild = NULL; 981 FirstChild = TRUE; 982 for (i = 0; i < NumChildren; i++) 983 { 984 /* Get the next child */ 985 986 Child = va_arg (ap, ACPI_PARSE_OBJECT *); 987 DbgPrint (ASL_PARSE_OUTPUT, "%p, ", Child); 988 989 /* 990 * If child is NULL, this means that an optional argument 991 * was omitted. We must create a placeholder with a special 992 * opcode (DEFAULT_ARG) so that the code generator will know 993 * that it must emit the correct default for this argument 994 */ 995 if (!Child) 996 { 997 Child = TrAllocateNode (PARSEOP_DEFAULT_ARG); 998 } 999 1000 /* Link first child to parent */ 1001 1002 if (FirstChild) 1003 { 1004 FirstChild = FALSE; 1005 Op->Asl.Child = Child; 1006 } 1007 1008 /* Point all children to parent */ 1009 1010 Child->Asl.Parent = Op; 1011 1012 /* Link children in a peer list */ 1013 1014 if (PrevChild) 1015 { 1016 PrevChild->Asl.Next = Child; 1017 }; 1018 1019 /* 1020 * This child might be a list, point all nodes in the list 1021 * to the same parent 1022 */ 1023 while (Child->Asl.Next) 1024 { 1025 Child = Child->Asl.Next; 1026 Child->Asl.Parent = Op; 1027 } 1028 1029 PrevChild = Child; 1030 } 1031 va_end(ap); 1032 1033 DbgPrint (ASL_PARSE_OUTPUT, "\n"); 1034 return (Op); 1035 } 1036 1037 1038 /******************************************************************************* 1039 * 1040 * FUNCTION: TrLinkChildren 1041 * 1042 * PARAMETERS: Op - An existing parse node 1043 * NumChildren - Number of children to follow 1044 * ... - A list of child nodes to link to the new 1045 * node. NumChildren long. 1046 * 1047 * RETURN: The updated (linked) node 1048 * 1049 * DESCRIPTION: Link a group of nodes to an existing parse node 1050 * 1051 ******************************************************************************/ 1052 1053 ACPI_PARSE_OBJECT * 1054 TrLinkChildren ( 1055 ACPI_PARSE_OBJECT *Op, 1056 UINT32 NumChildren, 1057 ...) 1058 { 1059 ACPI_PARSE_OBJECT *Child; 1060 ACPI_PARSE_OBJECT *PrevChild; 1061 va_list ap; 1062 UINT32 i; 1063 BOOLEAN FirstChild; 1064 1065 1066 va_start (ap, NumChildren); 1067 1068 1069 TrSetEndLineNumber (Op); 1070 1071 DbgPrint (ASL_PARSE_OUTPUT, 1072 "\nLinkChildren Line [%u to %u] NewParent %p Child %u Op %s ", 1073 Op->Asl.LineNumber, Op->Asl.EndLine, 1074 Op, NumChildren, UtGetOpName(Op->Asl.ParseOpcode)); 1075 1076 switch (Op->Asl.ParseOpcode) 1077 { 1078 case PARSEOP_DEFINITIONBLOCK: 1079 1080 RootNode = Op; 1081 DbgPrint (ASL_PARSE_OUTPUT, "DEFINITION_BLOCK (Tree Completed)->"); 1082 break; 1083 1084 case PARSEOP_OPERATIONREGION: 1085 1086 DbgPrint (ASL_PARSE_OUTPUT, "OPREGION->"); 1087 break; 1088 1089 case PARSEOP_OR: 1090 1091 DbgPrint (ASL_PARSE_OUTPUT, "OR->"); 1092 break; 1093 1094 default: 1095 1096 /* Nothing to do for other opcodes */ 1097 1098 break; 1099 } 1100 1101 /* Link the new node to it's children */ 1102 1103 PrevChild = NULL; 1104 FirstChild = TRUE; 1105 for (i = 0; i < NumChildren; i++) 1106 { 1107 Child = va_arg (ap, ACPI_PARSE_OBJECT *); 1108 1109 if ((Child == PrevChild) && (Child != NULL)) 1110 { 1111 AslError (ASL_WARNING, ASL_MSG_COMPILER_INTERNAL, Child, 1112 "Child node list invalid"); 1113 va_end(ap); 1114 return (Op); 1115 } 1116 1117 DbgPrint (ASL_PARSE_OUTPUT, "%p, ", Child); 1118 1119 /* 1120 * If child is NULL, this means that an optional argument 1121 * was omitted. We must create a placeholder with a special 1122 * opcode (DEFAULT_ARG) so that the code generator will know 1123 * that it must emit the correct default for this argument 1124 */ 1125 if (!Child) 1126 { 1127 Child = TrAllocateNode (PARSEOP_DEFAULT_ARG); 1128 } 1129 1130 /* Link first child to parent */ 1131 1132 if (FirstChild) 1133 { 1134 FirstChild = FALSE; 1135 Op->Asl.Child = Child; 1136 } 1137 1138 /* Point all children to parent */ 1139 1140 Child->Asl.Parent = Op; 1141 1142 /* Link children in a peer list */ 1143 1144 if (PrevChild) 1145 { 1146 PrevChild->Asl.Next = Child; 1147 }; 1148 1149 /* 1150 * This child might be a list, point all nodes in the list 1151 * to the same parent 1152 */ 1153 while (Child->Asl.Next) 1154 { 1155 Child = Child->Asl.Next; 1156 Child->Asl.Parent = Op; 1157 } 1158 PrevChild = Child; 1159 } 1160 1161 va_end(ap); 1162 DbgPrint (ASL_PARSE_OUTPUT, "\n\n"); 1163 return (Op); 1164 } 1165 1166 1167 /******************************************************************************* 1168 * 1169 * FUNCTION: TrLinkPeerNode 1170 * 1171 * PARAMETERS: Op1 - First peer 1172 * Op2 - Second peer 1173 * 1174 * RETURN: Op1 or the non-null node. 1175 * 1176 * DESCRIPTION: Link two nodes as peers. Handles cases where one peer is null. 1177 * 1178 ******************************************************************************/ 1179 1180 ACPI_PARSE_OBJECT * 1181 TrLinkPeerNode ( 1182 ACPI_PARSE_OBJECT *Op1, 1183 ACPI_PARSE_OBJECT *Op2) 1184 { 1185 ACPI_PARSE_OBJECT *Next; 1186 1187 1188 DbgPrint (ASL_PARSE_OUTPUT, 1189 "\nLinkPeerNode: 1=%p (%s), 2=%p (%s)\n", 1190 Op1, Op1 ? UtGetOpName(Op1->Asl.ParseOpcode) : NULL, 1191 Op2, Op2 ? UtGetOpName(Op2->Asl.ParseOpcode) : NULL); 1192 1193 1194 if ((!Op1) && (!Op2)) 1195 { 1196 DbgPrint (ASL_PARSE_OUTPUT, "\nTwo Null nodes!\n"); 1197 return (Op1); 1198 } 1199 1200 /* If one of the nodes is null, just return the non-null node */ 1201 1202 if (!Op2) 1203 { 1204 return (Op1); 1205 } 1206 1207 if (!Op1) 1208 { 1209 return (Op2); 1210 } 1211 1212 if (Op1 == Op2) 1213 { 1214 DbgPrint (ASL_DEBUG_OUTPUT, 1215 "\n************* Internal error, linking node to itself %p\n", 1216 Op1); 1217 AslError (ASL_WARNING, ASL_MSG_COMPILER_INTERNAL, Op1, 1218 "Linking node to itself"); 1219 return (Op1); 1220 } 1221 1222 Op1->Asl.Parent = Op2->Asl.Parent; 1223 1224 /* 1225 * Op 1 may already have a peer list (such as an IF/ELSE pair), 1226 * so we must walk to the end of the list and attach the new 1227 * peer at the end 1228 */ 1229 Next = Op1; 1230 while (Next->Asl.Next) 1231 { 1232 Next = Next->Asl.Next; 1233 } 1234 1235 Next->Asl.Next = Op2; 1236 return (Op1); 1237 } 1238 1239 1240 /******************************************************************************* 1241 * 1242 * FUNCTION: TrLinkPeerNodes 1243 * 1244 * PARAMETERS: NumPeers - The number of nodes in the list to follow 1245 * ... - A list of nodes to link together as peers 1246 * 1247 * RETURN: The first node in the list (head of the peer list) 1248 * 1249 * DESCRIPTION: Link together an arbitrary number of peer nodes. 1250 * 1251 ******************************************************************************/ 1252 1253 ACPI_PARSE_OBJECT * 1254 TrLinkPeerNodes ( 1255 UINT32 NumPeers, 1256 ...) 1257 { 1258 ACPI_PARSE_OBJECT *This; 1259 ACPI_PARSE_OBJECT *Next; 1260 va_list ap; 1261 UINT32 i; 1262 ACPI_PARSE_OBJECT *Start; 1263 1264 1265 DbgPrint (ASL_PARSE_OUTPUT, 1266 "\nLinkPeerNodes: (%u) ", NumPeers); 1267 1268 va_start (ap, NumPeers); 1269 This = va_arg (ap, ACPI_PARSE_OBJECT *); 1270 Start = This; 1271 1272 /* 1273 * Link all peers 1274 */ 1275 for (i = 0; i < (NumPeers -1); i++) 1276 { 1277 DbgPrint (ASL_PARSE_OUTPUT, "%u=%p ", (i+1), This); 1278 1279 while (This->Asl.Next) 1280 { 1281 This = This->Asl.Next; 1282 } 1283 1284 /* Get another peer node */ 1285 1286 Next = va_arg (ap, ACPI_PARSE_OBJECT *); 1287 if (!Next) 1288 { 1289 Next = TrAllocateNode (PARSEOP_DEFAULT_ARG); 1290 } 1291 1292 /* link new node to the current node */ 1293 1294 This->Asl.Next = Next; 1295 This = Next; 1296 } 1297 va_end (ap); 1298 1299 DbgPrint (ASL_PARSE_OUTPUT,"\n"); 1300 return (Start); 1301 } 1302 1303 1304 /******************************************************************************* 1305 * 1306 * FUNCTION: TrLinkChildNode 1307 * 1308 * PARAMETERS: Op1 - Parent node 1309 * Op2 - Op to become a child 1310 * 1311 * RETURN: The parent node 1312 * 1313 * DESCRIPTION: Link two nodes together as a parent and child 1314 * 1315 ******************************************************************************/ 1316 1317 ACPI_PARSE_OBJECT * 1318 TrLinkChildNode ( 1319 ACPI_PARSE_OBJECT *Op1, 1320 ACPI_PARSE_OBJECT *Op2) 1321 { 1322 ACPI_PARSE_OBJECT *Next; 1323 1324 1325 DbgPrint (ASL_PARSE_OUTPUT, 1326 "\nLinkChildNode: Parent=%p (%s), Child=%p (%s)\n", 1327 Op1, Op1 ? UtGetOpName(Op1->Asl.ParseOpcode): NULL, 1328 Op2, Op2 ? UtGetOpName(Op2->Asl.ParseOpcode): NULL); 1329 1330 if (!Op1 || !Op2) 1331 { 1332 return (Op1); 1333 } 1334 1335 Op1->Asl.Child = Op2; 1336 1337 /* Set the child and all peers of the child to point to the parent */ 1338 1339 Next = Op2; 1340 while (Next) 1341 { 1342 Next->Asl.Parent = Op1; 1343 Next = Next->Asl.Next; 1344 } 1345 1346 return (Op1); 1347 } 1348 1349 1350 /******************************************************************************* 1351 * 1352 * FUNCTION: TrWalkParseTree 1353 * 1354 * PARAMETERS: Visitation - Type of walk 1355 * DescendingCallback - Called during tree descent 1356 * AscendingCallback - Called during tree ascent 1357 * Context - To be passed to the callbacks 1358 * 1359 * RETURN: Status from callback(s) 1360 * 1361 * DESCRIPTION: Walk the entire parse tree. 1362 * 1363 ******************************************************************************/ 1364 1365 ACPI_STATUS 1366 TrWalkParseTree ( 1367 ACPI_PARSE_OBJECT *Op, 1368 UINT32 Visitation, 1369 ASL_WALK_CALLBACK DescendingCallback, 1370 ASL_WALK_CALLBACK AscendingCallback, 1371 void *Context) 1372 { 1373 UINT32 Level; 1374 BOOLEAN NodePreviouslyVisited; 1375 ACPI_PARSE_OBJECT *StartOp = Op; 1376 ACPI_STATUS Status; 1377 1378 1379 if (!RootNode) 1380 { 1381 return (AE_OK); 1382 } 1383 1384 Level = 0; 1385 NodePreviouslyVisited = FALSE; 1386 1387 switch (Visitation) 1388 { 1389 case ASL_WALK_VISIT_DOWNWARD: 1390 1391 while (Op) 1392 { 1393 if (!NodePreviouslyVisited) 1394 { 1395 /* Let the callback process the node. */ 1396 1397 Status = DescendingCallback (Op, Level, Context); 1398 if (ACPI_SUCCESS (Status)) 1399 { 1400 /* Visit children first, once */ 1401 1402 if (Op->Asl.Child) 1403 { 1404 Level++; 1405 Op = Op->Asl.Child; 1406 continue; 1407 } 1408 } 1409 else if (Status != AE_CTRL_DEPTH) 1410 { 1411 /* Exit immediately on any error */ 1412 1413 return (Status); 1414 } 1415 } 1416 1417 /* Terminate walk at start op */ 1418 1419 if (Op == StartOp) 1420 { 1421 break; 1422 } 1423 1424 /* No more children, visit peers */ 1425 1426 if (Op->Asl.Next) 1427 { 1428 Op = Op->Asl.Next; 1429 NodePreviouslyVisited = FALSE; 1430 } 1431 else 1432 { 1433 /* No children or peers, re-visit parent */ 1434 1435 if (Level != 0 ) 1436 { 1437 Level--; 1438 } 1439 Op = Op->Asl.Parent; 1440 NodePreviouslyVisited = TRUE; 1441 } 1442 } 1443 break; 1444 1445 case ASL_WALK_VISIT_UPWARD: 1446 1447 while (Op) 1448 { 1449 /* Visit leaf node (no children) or parent node on return trip */ 1450 1451 if ((!Op->Asl.Child) || 1452 (NodePreviouslyVisited)) 1453 { 1454 /* Let the callback process the node. */ 1455 1456 Status = AscendingCallback (Op, Level, Context); 1457 if (ACPI_FAILURE (Status)) 1458 { 1459 return (Status); 1460 } 1461 } 1462 else 1463 { 1464 /* Visit children first, once */ 1465 1466 Level++; 1467 Op = Op->Asl.Child; 1468 continue; 1469 } 1470 1471 /* Terminate walk at start op */ 1472 1473 if (Op == StartOp) 1474 { 1475 break; 1476 } 1477 1478 /* No more children, visit peers */ 1479 1480 if (Op->Asl.Next) 1481 { 1482 Op = Op->Asl.Next; 1483 NodePreviouslyVisited = FALSE; 1484 } 1485 else 1486 { 1487 /* No children or peers, re-visit parent */ 1488 1489 if (Level != 0 ) 1490 { 1491 Level--; 1492 } 1493 Op = Op->Asl.Parent; 1494 NodePreviouslyVisited = TRUE; 1495 } 1496 } 1497 break; 1498 1499 case ASL_WALK_VISIT_TWICE: 1500 1501 while (Op) 1502 { 1503 if (NodePreviouslyVisited) 1504 { 1505 Status = AscendingCallback (Op, Level, Context); 1506 if (ACPI_FAILURE (Status)) 1507 { 1508 return (Status); 1509 } 1510 } 1511 else 1512 { 1513 /* Let the callback process the node. */ 1514 1515 Status = DescendingCallback (Op, Level, Context); 1516 if (ACPI_SUCCESS (Status)) 1517 { 1518 /* Visit children first, once */ 1519 1520 if (Op->Asl.Child) 1521 { 1522 Level++; 1523 Op = Op->Asl.Child; 1524 continue; 1525 } 1526 } 1527 else if (Status != AE_CTRL_DEPTH) 1528 { 1529 /* Exit immediately on any error */ 1530 1531 return (Status); 1532 } 1533 } 1534 1535 /* Terminate walk at start op */ 1536 1537 if (Op == StartOp) 1538 { 1539 break; 1540 } 1541 1542 /* No more children, visit peers */ 1543 1544 if (Op->Asl.Next) 1545 { 1546 Op = Op->Asl.Next; 1547 NodePreviouslyVisited = FALSE; 1548 } 1549 else 1550 { 1551 /* No children or peers, re-visit parent */ 1552 1553 if (Level != 0 ) 1554 { 1555 Level--; 1556 } 1557 Op = Op->Asl.Parent; 1558 NodePreviouslyVisited = TRUE; 1559 } 1560 } 1561 break; 1562 1563 default: 1564 /* No other types supported */ 1565 break; 1566 } 1567 1568 /* If we get here, the walk completed with no errors */ 1569 1570 return (AE_OK); 1571 } 1572