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