sys/contrib/dev/acpica/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 <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
  54 static ACPI_PARSE_OBJECT *
  55 TrGetNextNode (
  56     void);
  57
  58
  59 /*******************************************************************************
  60  *
  61  * FUNCTION:    TrGetNextNode
  62  *
  63  * PARAMETERS:  None
  64  *
  65  * RETURN:      New parse node. Aborts on allocation failure
  66  *
  67  * DESCRIPTION: Allocate a new parse node for the parse tree. Bypass the local
  68  *              dynamic memory manager for performance reasons (This has a
  69  *              major impact on the speed of the compiler.)
  70  *
  71  ******************************************************************************/
  72
  73 static ACPI_PARSE_OBJECT *
  74 TrGetNextNode (
  75     void)
  76 {
  77     ASL_CACHE_INFO          *Cache;
  78
  79
  80     if (Gbl_ParseOpCacheNext >= Gbl_ParseOpCacheLast)
  81     {
  82         /* Allocate a new buffer */
  83
  84         Cache = UtLocalCalloc (sizeof (Cache->Next) +
  85             (sizeof (ACPI_PARSE_OBJECT) * ASL_PARSEOP_CACHE_SIZE));
  86
  87         /* Link new cache buffer to head of list */
  88
  89         Cache->Next = Gbl_ParseOpCacheList;
  90         Gbl_ParseOpCacheList = Cache;
  91
  92         /* Setup cache management pointers */
  93
  94         Gbl_ParseOpCacheNext = ACPI_CAST_PTR (ACPI_PARSE_OBJECT, Cache->Buffer);
  95         Gbl_ParseOpCacheLast = Gbl_ParseOpCacheNext + ASL_PARSEOP_CACHE_SIZE;
  96     }
  97
  98     Gbl_ParseOpCount++;
  99     return (Gbl_ParseOpCacheNext++);
 100 }
 101
 102
 103 /*******************************************************************************
 104  *
 105  * FUNCTION:    TrAllocateNode
 106  *
 107  * PARAMETERS:  ParseOpcode         - Opcode to be assigned to the node
 108  *
 109  * RETURN:      New parse node. Aborts on allocation failure
 110  *
 111  * DESCRIPTION: Allocate and initialize a new parse node for the parse tree
 112  *
 113  ******************************************************************************/
 114
 115 ACPI_PARSE_OBJECT *
 116 TrAllocateNode (
 117     UINT32                  ParseOpcode)
 118 {
 119     ACPI_PARSE_OBJECT       *Op;
 120
 121
 122     Op = TrGetNextNode ();
 123
 124     Op->Asl.ParseOpcode       = (UINT16) ParseOpcode;
 125     Op->Asl.Filename          = Gbl_Files[ASL_FILE_INPUT].Filename;
 126     Op->Asl.LineNumber        = Gbl_CurrentLineNumber;
 127     Op->Asl.LogicalLineNumber = Gbl_LogicalLineNumber;
 128     Op->Asl.LogicalByteOffset = Gbl_CurrentLineOffset;
 129     Op->Asl.Column            = Gbl_CurrentColumn;
 130
 131     UtSetParseOpName (Op);
 132     return (Op);
 133 }
 134
 135
 136 /*******************************************************************************
 137  *
 138  * FUNCTION:    TrReleaseNode
 139  *
 140  * PARAMETERS:  Op            - Op to be released
 141  *
 142  * RETURN:      None
 143  *
 144  * DESCRIPTION: "release" a node. In truth, nothing is done since the node
 145  *              is part of a larger buffer
 146  *
 147  ******************************************************************************/
 148
 149 void
 150 TrReleaseNode (
 151     ACPI_PARSE_OBJECT       *Op)
 152 {
 153
 154     return;
 155 }
 156
 157
 158 /*******************************************************************************
 159  *
 160  * FUNCTION:    TrUpdateNode
 161  *
 162  * PARAMETERS:  ParseOpcode         - New opcode to be assigned to the node
 163  *              Op                - An existing parse node
 164  *
 165  * RETURN:      The updated node
 166  *
 167  * DESCRIPTION: Change the parse opcode assigned to a node. Usually used to
 168  *              change an opcode to DEFAULT_ARG so that the node is ignored
 169  *              during the code generation. Also used to set generic integers
 170  *              to a specific size (8, 16, 32, or 64 bits)
 171  *
 172  ******************************************************************************/
 173
 174 ACPI_PARSE_OBJECT *
 175 TrUpdateNode (
 176     UINT32                  ParseOpcode,
 177     ACPI_PARSE_OBJECT       *Op)
 178 {
 179
 180     if (!Op)
 181     {
 182         return (NULL);
 183     }
 184
 185     DbgPrint (ASL_PARSE_OUTPUT,
 186         "\nUpdateNode: Old - %s, New - %s\n",
 187         UtGetOpName (Op->Asl.ParseOpcode),
 188         UtGetOpName (ParseOpcode));
 189
 190     /* Assign new opcode and name */
 191
 192     if (Op->Asl.ParseOpcode == PARSEOP_ONES)
 193     {
 194         switch (ParseOpcode)
 195         {
 196         case PARSEOP_BYTECONST:
 197
 198             Op->Asl.Value.Integer = ACPI_UINT8_MAX;
 199             break;
 200
 201         case PARSEOP_WORDCONST:
 202
 203             Op->Asl.Value.Integer = ACPI_UINT16_MAX;
 204             break;
 205
 206         case PARSEOP_DWORDCONST:
 207
 208             Op->Asl.Value.Integer = ACPI_UINT32_MAX;
 209             break;
 210
 211         /* Don't need to do the QWORD case */
 212
 213         default:
 214
 215             /* Don't care about others */
 216             break;
 217         }
 218     }
 219
 220     Op->Asl.ParseOpcode = (UINT16) ParseOpcode;
 221     UtSetParseOpName (Op);
 222
 223     /*
 224      * For the BYTE, WORD, and DWORD constants, make sure that the integer
 225      * that was passed in will actually fit into the data type
 226      */
 227     switch (ParseOpcode)
 228     {
 229     case PARSEOP_BYTECONST:
 230
 231         UtCheckIntegerRange (Op, 0x00, ACPI_UINT8_MAX);
 232         Op->Asl.Value.Integer &= ACPI_UINT8_MAX;
 233         break;
 234
 235     case PARSEOP_WORDCONST:
 236
 237         UtCheckIntegerRange (Op, 0x00, ACPI_UINT16_MAX);
 238         Op->Asl.Value.Integer &= ACPI_UINT16_MAX;
 239         break;
 240
 241     case PARSEOP_DWORDCONST:
 242
 243         UtCheckIntegerRange (Op, 0x00, ACPI_UINT32_MAX);
 244         Op->Asl.Value.Integer &= ACPI_UINT32_MAX;
 245         break;
 246
 247     default:
 248
 249         /* Don't care about others, don't need to check QWORD */
 250
 251         break;
 252     }
 253
 254     return (Op);
 255 }
 256
 257
 258 /*******************************************************************************
 259  *
 260  * FUNCTION:    TrPrintNodeCompileFlags
 261  *
 262  * PARAMETERS:  Flags               - Flags word to be decoded
 263  *
 264  * RETURN:      None
 265  *
 266  * DESCRIPTION: Decode a flags word to text. Displays all flags that are set.
 267  *
 268  ******************************************************************************/
 269
 270 void
 271 TrPrintNodeCompileFlags (
 272     UINT32                  Flags)
 273 {
 274     UINT32                  i;
 275     UINT32                  FlagBit = 1;
 276     char                    *FlagName = NULL;
 277
 278
 279     for (i = 0; i < 32; i++)
 280     {
 281         switch (Flags & FlagBit)
 282         {
 283         case NODE_VISITED:
 284
 285             FlagName = "NODE_VISITED";
 286             break;
 287
 288         case NODE_AML_PACKAGE:
 289
 290             FlagName = "NODE_AML_PACKAGE";
 291             break;
 292
 293         case NODE_IS_TARGET:
 294
 295             FlagName = "NODE_IS_TARGET";
 296             break;
 297
 298         case NODE_IS_RESOURCE_DESC:
 299
 300             FlagName = "NODE_IS_RESOURCE_DESC";
 301             break;
 302
 303         case NODE_IS_RESOURCE_FIELD:
 304
 305             FlagName = "NODE_IS_RESOURCE_FIELD";
 306             break;
 307
 308         case NODE_HAS_NO_EXIT:
 309
 310             FlagName = "NODE_HAS_NO_EXIT";
 311             break;
 312
 313         case NODE_IF_HAS_NO_EXIT:
 314
 315             FlagName = "NODE_IF_HAS_NO_EXIT";
 316             break;
 317
 318         case NODE_NAME_INTERNALIZED:
 319
 320             FlagName = "NODE_NAME_INTERNALIZED";
 321             break;
 322
 323         case NODE_METHOD_NO_RETVAL:
 324
 325             FlagName = "NODE_METHOD_NO_RETVAL";
 326             break;
 327
 328         case NODE_METHOD_SOME_NO_RETVAL:
 329
 330             FlagName = "NODE_METHOD_SOME_NO_RETVAL";
 331             break;
 332
 333         case NODE_RESULT_NOT_USED:
 334
 335             FlagName = "NODE_RESULT_NOT_USED";
 336             break;
 337
 338         case NODE_METHOD_TYPED:
 339
 340             FlagName = "NODE_METHOD_TYPED";
 341             break;
 342
 343         case NODE_COMPILE_TIME_CONST:
 344
 345             FlagName = "NODE_COMPILE_TIME_CONST";
 346             break;
 347
 348         case NODE_IS_TERM_ARG:
 349
 350             FlagName = "NODE_IS_TERM_ARG";
 351             break;
 352
 353         case NODE_WAS_ONES_OP:
 354
 355             FlagName = "NODE_WAS_ONES_OP";
 356             break;
 357
 358         case NODE_IS_NAME_DECLARATION:
 359
 360             FlagName = "NODE_IS_NAME_DECLARATION";
 361             break;
 362
 363         case NODE_COMPILER_EMITTED:
 364
 365             FlagName = "NODE_COMPILER_EMITTED";
 366             break;
 367
 368         case NODE_IS_DUPLICATE:
 369
 370             FlagName = "NODE_IS_DUPLICATE";
 371             break;
 372
 373         case NODE_IS_RESOURCE_DATA:
 374
 375             FlagName = "NODE_IS_RESOURCE_DATA";
 376             break;
 377
 378         case NODE_IS_NULL_RETURN:
 379
 380             FlagName = "NODE_IS_NULL_RETURN";
 381             break;
 382
 383         default:
 384             break;
 385         }
 386
 387         if (FlagName)
 388         {
 389             DbgPrint (ASL_PARSE_OUTPUT, " %s", FlagName);
 390             FlagName = NULL;
 391         }
 392
 393         FlagBit <<= 1;
 394     }
 395 }
 396
 397
 398 /*******************************************************************************
 399  *
 400  * FUNCTION:    TrSetNodeFlags
 401  *
 402  * PARAMETERS:  Op                  - An existing parse node
 403  *              Flags               - New flags word
 404  *
 405  * RETURN:      The updated parser op
 406  *
 407  * DESCRIPTION: Set bits in the node flags word. Will not clear bits, only set
 408  *
 409  ******************************************************************************/
 410
 411 ACPI_PARSE_OBJECT *
 412 TrSetNodeFlags (
 413     ACPI_PARSE_OBJECT       *Op,
 414     UINT32                  Flags)
 415 {
 416
 417     if (!Op)
 418     {
 419         return (NULL);
 420     }
 421
 422     DbgPrint (ASL_PARSE_OUTPUT,
 423         "\nSetNodeFlags: %s Op %p, %8.8X", Op->Asl.ParseOpName, Op, Flags);
 424
 425     TrPrintNodeCompileFlags (Flags);
 426     DbgPrint (ASL_PARSE_OUTPUT, "\n\n");
 427
 428     Op->Asl.CompileFlags |= Flags;
 429     return (Op);
 430 }
 431
 432
 433 /*******************************************************************************
 434  *
 435  * FUNCTION:    TrSetNodeAmlLength
 436  *
 437  * PARAMETERS:  Op                  - An existing parse node
 438  *              Length              - AML Length
 439  *
 440  * RETURN:      The updated parser op
 441  *
 442  * DESCRIPTION: Set the AML Length in a node. Used by the parser to indicate
 443  *              the presence of a node that must be reduced to a fixed length
 444  *              constant.
 445  *
 446  ******************************************************************************/
 447
 448 ACPI_PARSE_OBJECT *
 449 TrSetNodeAmlLength (
 450     ACPI_PARSE_OBJECT       *Op,
 451     UINT32                  Length)
 452 {
 453
 454     DbgPrint (ASL_PARSE_OUTPUT,
 455         "\nSetNodeAmlLength: Op %p, %8.8X\n", Op, Length);
 456
 457     if (!Op)
 458     {
 459         return (NULL);
 460     }
 461
 462     Op->Asl.AmlLength = Length;
 463     return (Op);
 464 }
 465
 466
 467 /*******************************************************************************
 468  *
 469  * FUNCTION:    TrSetEndLineNumber
 470  *
 471  * PARAMETERS:  Op                - An existing parse node
 472  *
 473  * RETURN:      None.
 474  *
 475  * DESCRIPTION: Set the ending line numbers (file line and logical line) of a
 476  *              parse node to the current line numbers.
 477  *
 478  ******************************************************************************/
 479
 480 void
 481 TrSetEndLineNumber (
 482     ACPI_PARSE_OBJECT       *Op)
 483 {
 484
 485     /* If the end line # is already set, just return */
 486
 487     if (Op->Asl.EndLine)
 488     {
 489         return;
 490     }
 491
 492     Op->Asl.EndLine        = Gbl_CurrentLineNumber;
 493     Op->Asl.EndLogicalLine = Gbl_LogicalLineNumber;
 494 }
 495
 496
 497 /*******************************************************************************
 498  *
 499  * FUNCTION:    TrCreateAssignmentNode
 500  *
 501  * PARAMETERS:  Target              - Assignment target
 502  *              Source              - Assignment source
 503  *
 504  * RETURN:      Pointer to the new node. Aborts on allocation failure
 505  *
 506  * DESCRIPTION: Implements the C-style '=' operator. It changes the parse
 507  *              tree if possible to utilize the last argument of the math
 508  *              operators which is a target operand -- thus saving invocation
 509  *              of and additional Store() operator. An optimization.
 510  *
 511  ******************************************************************************/
 512
 513 ACPI_PARSE_OBJECT *
 514 TrCreateAssignmentNode (
 515     ACPI_PARSE_OBJECT       *Target,
 516     ACPI_PARSE_OBJECT       *Source)
 517 {
 518     ACPI_PARSE_OBJECT       *TargetOp;
 519     ACPI_PARSE_OBJECT       *SourceOp1;
 520     ACPI_PARSE_OBJECT       *SourceOp2;
 521     ACPI_PARSE_OBJECT       *Operator;
 522
 523
 524     DbgPrint (ASL_PARSE_OUTPUT,
 525         "\nTrCreateAssignmentNode  Line [%u to %u] Source %s Target %s\n",
 526         Source->Asl.LineNumber, Source->Asl.EndLine,
 527         UtGetOpName (Source->Asl.ParseOpcode),
 528         UtGetOpName (Target->Asl.ParseOpcode));
 529
 530     TrSetNodeFlags (Target, NODE_IS_TARGET);
 531
 532     switch (Source->Asl.ParseOpcode)
 533     {
 534     /*
 535      * Only these operators can be optimized because they have
 536      * a target operand
 537      */
 538     case PARSEOP_ADD:
 539     case PARSEOP_AND:
 540     case PARSEOP_DIVIDE:
 541     case PARSEOP_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
 599 CannotOptimize:
 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
 628 ACPI_PARSE_OBJECT *
 629 TrCreateLeafNode (
 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
 659 ACPI_PARSE_OBJECT *
 660 TrCreateNullTarget (
 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
 696 ACPI_PARSE_OBJECT *
 697 TrCreateConstantLeafNode (
 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
 791 ACPI_PARSE_OBJECT *
 792 TrCreateTargetOperand (
 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
 851 ACPI_PARSE_OBJECT *
 852 TrCreateValuedLeafNode (
 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
 926 ACPI_PARSE_OBJECT *
 927 TrCreateNode (
 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
1052 ACPI_PARSE_OBJECT *
1053 TrLinkChildren (
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
1179 ACPI_PARSE_OBJECT *
1180 TrLinkPeerNode (
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
1252 ACPI_PARSE_OBJECT *
1253 TrLinkPeerNodes (
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
1316 ACPI_PARSE_OBJECT *
1317 TrLinkChildNode (
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
1364 ACPI_STATUS
1365 TrWalkParseTree (
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 }