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