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