sys/contrib/dev/acpica/source/compiler/asltree.c

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