gcc/simple-break-elim.c

   1 /* Break and continue statement elimination for GIMPLE.
   2    Copyright (C) 2002, 2003 Free Software Foundation, Inc.
   3    Contributed by Sebastian Pop <s.pop@laposte.net>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "tree.h"
  27 #include "c-tree.h"
  28 #include "c-common.h"
  29 #include "tree-simple.h"
  30 #include "tree-dchain.h"
  31 #include "diagnostic.h"
  32
  33 /* This pass eliminates all BREAK_STMTs and CONTINUE_STMTs from loops.
  34    It performs also dead code elimination.  This pass works on double linked
  35    statements on the GIMPLE representation.
  36    After this pass we obtain a subset of the GIMPLE grammar since all
  37    SWITCH_STMTs are trasformed into IF_STMTs.  */
  38
  39 /* For normalizing the flow in the loop body, there are two approaches :
  40    Solution 1: copy statements (explicit control flow).
  41    Solution 2: use logical variables (data controled flow).
  42
  43    The first solution raises a difficult problem linked to the visibility of a
  44    variable in different scopes.
  45
  46    The second solution is similar to the one adopted by the McCAT compiler for
  47    eliminating GOTO_STMTs.  They describe an algorithm for eliminating goto
  48    statements, but they use BREAK_STMTs for exiting loops.  The following
  49    implementation is an extension of their algorithm and is based on the same
  50    principle : the use of logical variables for controlling the control flow.
  51
  52    References :
  53    - Taming Control Flow : A structured Approach to Eliminate Goto Statements,
  54    Ana M. Erosa and Laurie J. Hendren, in the proceedings of the 1994
  55    International Conference on Computer Languages (ICCL'94) pp.229-240.
  56
  57    - Erosa's MSc. Thesis, University McGill :
  58    A goto-elimination method and its implementation for the McCAT C compiler,
  59    http://www.sable.mcgill.ca/~hendren/ftp/erosa/thesis.ps.gz  */
  60
  61
  62 enum eval_bool {
  63   EVAL_FALSE = 0,
  64   EVAL_TRUE,
  65   EVAL_DONT_KNOW
  66 };
  67
  68 static void break_continue_elimination_rec (tree);
  69 static void break_elimination (tree);
  70 static void continue_stmt_solution2 (tree *);
  71 static void break_stmt_solution2 (tree *);
  72 static void outward_motion (tree, tree, tree,
  73                             void (*) (tree, tree, tree, tree));
  74 static void update_break_paths (tree, tree, tree, tree);
  75 static void switch_to_if (tree);
  76 static void construct_body_for_case_labels (tree);
  77 static void complete_body_of_case_labels (tree);
  78 static void reorder_case_labels (tree);
  79 static tree cases_to_if (tree, tree);
  80 static enum eval_bool eval_bool_condition (tree);
  81
  82 /* Static variables.  */
  83 static PATH_TYPE PATH_TOP;
  84
  85
  86 /* Entry point to the break and continue elimination pass.  FN is the
  87    FUNCTION_DECL node for the function we want to gimplify.  */
  88
  89 void
  90 break_continue_elimination (tree fn)
  91 {
  92   tree fn_body;
  93
  94   /* Don't bother doing anything if the program has errors.  */
  95   if (errorcount || sorrycount)
  96     return;
  97
  98   fn_body = COMPOUND_BODY (DECL_SAVED_TREE (fn));
  99   if (fn_body == NULL)
 100     return;
 101
 102   /* Create a new binding level for the temporaries created by the
 103      gimplification process.  */
 104   pushlevel (0);
 105
 106   /* Transform breaks and continues from the function's body.  */
 107   break_continue_elimination_rec (fn_body);
 108
 109   /* Declare the new temporary variables.  */
 110   dchain_declare_tmp_vars (getdecls(), fn_body);
 111
 112   /* Restore the binding level.  */
 113   poplevel (1, 1, 0);
 114 }
 115
 116 /* A helper function that transforms all [BREAK|CONTINUE]_STMTs from NODE
 117    recursively.  */
 118
 119 static void
 120 break_continue_elimination_rec (tree node)
 121 {
 122   while (node && node != error_mark_node)
 123     {
 124       switch (TREE_CODE (node))
 125         {
 126         case COMPOUND_STMT:
 127           PATH_PUSH (node);
 128           break_continue_elimination_rec (COMPOUND_BODY (node));
 129           PATH_POP ();
 130           break;
 131
 132         case FOR_STMT:
 133           dchain_build_scope (&FOR_BODY (node));
 134           PATH_PUSH (node);
 135           break_continue_elimination_rec (FOR_BODY (node));
 136           PATH_POP ();
 137           break;
 138
 139         case WHILE_STMT:
 140           dchain_build_scope (&WHILE_BODY (node));
 141           PATH_PUSH (node);
 142           break_continue_elimination_rec (WHILE_BODY (node));
 143           PATH_POP ();
 144           break;
 145
 146         case DO_STMT:
 147           dchain_build_scope (&DO_BODY (node));
 148           PATH_PUSH (node);
 149           break_continue_elimination_rec (DO_BODY (node));
 150           PATH_POP ();
 151           break;
 152
 153         case SWITCH_STMT:
 154           /* Transform this node into an IF_STMT, since a SWITCH_STMT contains
 155              BREAK_STMTs that aren't of the same type as those we'll eliminate.
 156              This transformation eliminate BREAK_STMTs that refers to a switch.  */
 157           switch_to_if (node);
 158           break;
 159
 160         case IF_STMT:
 161           dchain_build_scope (&THEN_CLAUSE (node));
 162           PATH_PUSH (node);
 163           break_continue_elimination_rec (THEN_CLAUSE (node));
 164           PATH_POP ();
 165           if (ELSE_CLAUSE (node))
 166             {
 167               dchain_build_scope (&ELSE_CLAUSE (node));
 168               PATH_PUSH (node);
 169               break_continue_elimination_rec (ELSE_CLAUSE (node));
 170               PATH_POP ();
 171             }
 172           break;
 173
 174         case CONTINUE_STMT:
 175           continue_stmt_solution2 (&node);
 176           break;
 177
 178         case BREAK_STMT:
 179           break_stmt_solution2 (&node);
 180           break;
 181
 182         default:
 183           break;
 184         }
 185       node = NEXT_STMT (node);
 186     }
 187 }
 188
 189 /* This function transforms all BREAK_STMTs from NODE and all BREAK_STMTs and
 190    CONTINUE_STMTs from its nested loops.  We call this function only in special
 191    cases when we have no information about a potential outer loop to which a
 192    CONTINUE_STMT could be related.  This is the reason to keep it static.  */
 193
 194 static void
 195 break_elimination (tree node)
 196 {
 197   while (node && node != error_mark_node)
 198     {
 199       switch (TREE_CODE (node))
 200         {
 201         case COMPOUND_STMT:
 202           PATH_PUSH (node);
 203           break_elimination (COMPOUND_BODY (node));
 204           PATH_POP ();
 205           break;
 206
 207         case FOR_STMT:
 208           dchain_build_scope (&FOR_BODY (node));
 209           PATH_PUSH (node);
 210           break_continue_elimination_rec (FOR_BODY (node));
 211           PATH_POP ();
 212           break;
 213
 214         case WHILE_STMT:
 215           dchain_build_scope (&WHILE_BODY (node));
 216           PATH_PUSH (node);
 217           break_continue_elimination_rec (WHILE_BODY (node));
 218           PATH_POP ();
 219           break;
 220
 221         case DO_STMT:
 222           dchain_build_scope (&DO_BODY (node));
 223           PATH_PUSH (node);
 224           break_continue_elimination_rec (DO_BODY (node));
 225           PATH_POP ();
 226           break;
 227
 228         case SWITCH_STMT:
 229           /* Transform this node into an IF_STMT, since a SWITCH_STMT contains
 230              BREAK_STMTs that aren't of the same type as those we'll eliminate.
 231              This transformation eliminate BREAK_STMTs that refers to a switch.  */
 232           switch_to_if (node);
 233           break;
 234
 235         case IF_STMT:
 236           dchain_build_scope (&THEN_CLAUSE (node));
 237           PATH_PUSH (node);
 238           break_elimination (THEN_CLAUSE (node));
 239           PATH_POP ();
 240           if (ELSE_CLAUSE (node))
 241             {
 242               dchain_build_scope (&ELSE_CLAUSE (node));
 243               PATH_PUSH (node);
 244               break_elimination (ELSE_CLAUSE (node));
 245               PATH_POP ();
 246             }
 247           break;
 248
 249         case BREAK_STMT:
 250           break_stmt_solution2 (&node);
 251           break;
 252
 253         default:
 254           break;
 255         }
 256       node = NEXT_STMT (node);
 257     }
 258 }
 259
 260 /* Determines wether the chain NODE contains a nested statement CODE.  */
 261
 262 int
 263 chain_contains_stmt_p (tree node, enum tree_code code)
 264 {
 265   while (node)
 266     {
 267       if (TREE_CODE (node) == code)
 268         return 1;
 269
 270       switch (TREE_CODE (node))
 271         {
 272         case LABEL_STMT:
 273           return 1;
 274
 275         case COMPOUND_STMT:
 276           if (chain_contains_stmt_p (COMPOUND_BODY (node), code))
 277             return 1;
 278           break;
 279
 280         case FOR_STMT:
 281           if (chain_contains_stmt_p (FOR_INIT_STMT (node), code))
 282             return 1;
 283           if (chain_contains_stmt_p (FOR_BODY (node), code))
 284             return 1;
 285           break;
 286
 287         case WHILE_STMT:
 288           if (chain_contains_stmt_p (WHILE_BODY (node), code))
 289             return 1;
 290           break;
 291
 292         case DO_STMT:
 293           if (chain_contains_stmt_p (DO_BODY (node), code))
 294             return 1;
 295           break;
 296
 297         case IF_STMT:
 298           if (chain_contains_stmt_p (THEN_CLAUSE (node), code))
 299             return 1;
 300           if (chain_contains_stmt_p (ELSE_CLAUSE (node), code))
 301             return 1;
 302           break;
 303
 304         case SWITCH_STMT:
 305           if (chain_contains_stmt_p (SWITCH_BODY (node), code))
 306             return 1;
 307           break;
 308
 309         case EXPR_STMT:
 310         case DECL_STMT:
 311         case RETURN_STMT:
 312         case SCOPE_STMT:
 313         case FILE_STMT:
 314         case GOTO_STMT:
 315         case ASM_STMT:
 316         case CASE_LABEL:
 317         case CONTINUE_STMT:
 318         case BREAK_STMT:
 319         default:
 320           break;
 321
 322         }
 323       node = TREE_CHAIN (node);
 324     }
 325   return 0;
 326 }
 327
 328 /* If PARENT is a statement with a condition, then insert CONDITION in its
 329    condition as the first operand of an TRUTH_ANDIF_EXPR.  That means that the
 330    CONDITION is executed before the evaluation of the rest of loop's condition.  */
 331
 332 void
 333 insert_andif_in_condition (tree condition, tree parent)
 334 {
 335   switch (TREE_CODE (parent))
 336     {
 337     case FOR_STMT:
 338       if (FOR_COND (parent))
 339         FOR_COND (parent) = fold (build (TRUTH_ANDIF_EXPR, integer_type_node,
 340                                          condition, FOR_COND (parent)));
 341       else
 342         FOR_COND (parent) = condition;
 343       break;
 344
 345     case WHILE_STMT:
 346       if (WHILE_COND (parent))
 347         WHILE_COND (parent) = fold (build (TRUTH_ANDIF_EXPR, integer_type_node,
 348                                            condition, WHILE_COND (parent)));
 349       else
 350         WHILE_COND (parent) = condition;
 351       break;
 352
 353     case DO_STMT:
 354       if (DO_COND (parent))
 355         DO_COND (parent) = fold (build (TRUTH_ANDIF_EXPR, integer_type_node,
 356                                         condition, DO_COND (parent)));
 357       else
 358         DO_COND (parent) = condition;
 359       break;
 360
 361     case IF_STMT:
 362       if (IF_COND (parent))
 363         IF_COND (parent) = fold (build (TRUTH_ANDIF_EXPR, integer_type_node,
 364                                         condition, IF_COND (parent)));
 365       else
 366         IF_COND (parent) = condition;
 367       break;
 368
 369     default:
 370       break;
 371     }
 372 }
 373
 374 /* If PARENT is a statement with a condition, then insert CONDITION in its
 375    condition as the first operand of an TRUTH_ORIF_EXPR.  That means that the
 376    CONDITION is executed before the evaluation of the rest of loop's condition.  */
 377
 378 void
 379 insert_orif_in_condition (tree condition, tree parent)
 380 {
 381   switch (TREE_CODE (parent))
 382     {
 383     case FOR_STMT:
 384       if (FOR_COND (parent))
 385         FOR_COND (parent) = fold (build (TRUTH_ORIF_EXPR, integer_type_node,
 386                                          condition, FOR_COND (parent)));
 387       else
 388         FOR_COND (parent) = condition;
 389       break;
 390
 391     case WHILE_STMT:
 392       if (WHILE_COND (parent))
 393         WHILE_COND (parent) = fold (build (TRUTH_ORIF_EXPR, integer_type_node,
 394                                            condition, WHILE_COND (parent)));
 395       else
 396         WHILE_COND (parent) = condition;
 397       break;
 398
 399     case DO_STMT:
 400       if (DO_COND (parent))
 401         DO_COND (parent) = fold (build (TRUTH_ORIF_EXPR, integer_type_node,
 402                                         condition, DO_COND (parent)));
 403       else
 404         DO_COND (parent) = condition;
 405       break;
 406
 407     case IF_STMT:
 408       if (IF_COND (parent))
 409         IF_COND (parent) = fold (build (TRUTH_ORIF_EXPR, integer_type_node,
 410                                         condition, IF_COND (parent)));
 411       else
 412         IF_COND (parent) = condition;
 413       break;
 414
 415     default:
 416       break;
 417     }
 418 }
 419
 420
 421 /* Solution 2: DATA_CONTROLED_FLOW
 422    use logical variables to decide wether the code following
 423    the CONTINUE_STMT in the parent block will be executed or not.
 424    This solution avoids to expand the code, but the control flow
 425    is no more explicit since the control depends on the logical
 426    variables : we transformed the control flow in a data flow.
 427    This is the solution adopted by the McCAT compiler.
 428
 429    Example : "while (c) {s1; s2; continue; s3;}"
 430    Calling continue_stmt_solution2 (continue);
 431    transforms the previous while into the following :
 432    "while (c) {s1; s2;}"  if "s3;" doesn't contain LABEL_STMTs (entry points),
 433    "while (c) {s1; s2; if (1 == 0) {s3;}"  otherwise.
 434
 435    Example : "while (c1) {s1; if (c2) {s2; continue; s3;} s4;}"
 436    Calling continue_stmt_solution2 (continue);
 437    transforms the previous while into the following :
 438    "while (c1) {int t=0; s1; if (c2) {s2; t=1;} if (t==0) {s4;}}"
 439    if there are no entry points in s3,
 440    "while (c1) {int t=0; s1; if (c2) {s2; t=1; if (1==0) {s3;}} if (t==0) {s4;}}"
 441    if there's an entry point in s3.  */
 442
 443 static void
 444 continue_stmt_solution2 (tree *stmt)
 445 {
 446   int one_if = 0;
 447   PATH_TYPE related_parent;
 448   tree related_loop;
 449
 450   /* Search the related loop statement.  */
 451   {
 452     related_parent = PATH_TOP;
 453     do {
 454       related_parent = PATH_PARENT (related_parent);
 455       related_loop = PATH_STMT (related_parent);
 456     } while (TREE_CODE (related_loop) == COMPOUND_STMT
 457              || (TREE_CODE (related_loop) == IF_STMT && (one_if = 1)));
 458   }
 459
 460   /* Move the flow down to the end of the related_loop's body.  */
 461   if (one_if == 0)
 462     /* The CONTINUE_STMT is unconditional.  The logical variable is always true.
 463        That will allow outward_motion to eliminate dead code in some cases.  */
 464     {
 465       tree prev;
 466       prev = PREV_STMT (*stmt);
 467
 468       /* Move the flow out up to the end of the related_loop's body.
 469          Stop before we move the flow out of related_parent : that's a CONTINUE_STMT.  */
 470       flow_out_of (/* Exit the loop's body, don't exit the loop.  */ PATH_CHILD (related_parent),
 471                    PATH_TOP,
 472                    /* Delete the CONTINUE_STMT.  */ prev,
 473                    /* Allow code elimination.  */ integer_one_node,
 474                    /* Updating function */ update_break_paths);
 475       *stmt = prev;
 476     }
 477   else
 478     /* The CONTINUE_STMT is conditional.  */
 479     {
 480       tree lvar, lvar_one;
 481
 482       /* Initialise a logical variable to false at the beginning of the loop.  */
 483       lvar = create_tmp_var (integer_type_node);
 484       DECL_INITIAL (lvar) = integer_zero_node;
 485
 486       /* Replace the CONTINUE_STMT by "lvar=1".  */
 487       lvar_one = build (MODIFY_EXPR, integer_type_node, lvar,
 488                         integer_one_node);
 489       lvar_one = build_stmt (EXPR_STMT, lvar_one);
 490       dchain_replace_stmt (*stmt, lvar_one);
 491       *stmt = lvar_one;
 492
 493       /* Move the flow down to the end of the related_loop's body.
 494          Stop before we move the flow out of related_parent : that's a CONTINUE_STMT.  */
 495       flow_out_of (PATH_CHILD (related_parent), PATH_TOP, lvar_one, lvar, update_break_paths);
 496     }
 497 }
 498
 499 /* Remove FOR_EXPR of a FOR_STMT.  */
 500 #define REMOVE_FOR_EXPR(NODE) do {                                             \
 501   if (TREE_CODE (NODE) == FOR_STMT && FOR_EXPR (NODE))                         \
 502     {                                                                          \
 503       tree reeval;                                                             \
 504       reeval = build_stmt (EXPR_STMT, FOR_EXPR (NODE));                        \
 505       insert_before_continue_end (reeval, FOR_BODY (NODE), STMT_LINENO (NODE));\
 506       FOR_EXPR (NODE) = NULL_TREE;                                             \
 507     }                                                                          \
 508 } while (0)
 509
 510 /* Solution 2: DATA_CONTROLED_FLOW
 511    use logical variables to decide wether the code following
 512    the BREAK_STMT in the parent block will be executed or not.
 513    This solution avoids to expand the code, but the control flow
 514    is no more explicit since the control depends on the logical
 515    variables : we transformed the control flow in a data flow.
 516    This is the solution adopted by the McCAT compiler.
 517
 518    Example : "while (c1) {s1; if (c2) {s2; break_stmt; s3;} s4;}"
 519    Calling break_stmt_solution2 (break_stmt);
 520    transforms the previous while into the following :
 521    "int t=0; while (t==0 && c1) {s1; if (c2) {s2; t=1;} if (t==0) {s4;}}"
 522    if there are no entry points in s3,
 523    "int t=0; while (t==0 && c1) {s1; if (c2) {s2; t=1; if (1==0) {s3;}} if (t==0) {s4;}}"
 524    if there's an entry point in s3.  */
 525
 526 static void
 527 break_stmt_solution2 (tree *stmt)
 528 {
 529   int one_if = 0;
 530   PATH_TYPE related_parent;
 531   tree related_loop;
 532   tree lvar, lvar_one;
 533
 534   /* Search the related loop statement.  */
 535   {
 536     related_parent = PATH_TOP;
 537     do {
 538       related_parent = PATH_PARENT (related_parent);
 539       related_loop = PATH_STMT (related_parent);
 540     } while (TREE_CODE (related_loop) == COMPOUND_STMT
 541              || (TREE_CODE (related_loop) == IF_STMT && (one_if = 1)));
 542   }
 543
 544   /* Replace the BREAK_STMT by "lvar=1;".  */
 545   {
 546     /* Initialise a logical variable to false in the function's scope.  */
 547     lvar = create_tmp_var (integer_type_node);
 548     DECL_INITIAL (lvar) = integer_zero_node;
 549
 550     /* Replace the BREAK_STMT by "lvar=1".  */
 551     lvar_one = build (MODIFY_EXPR, integer_type_node, lvar,
 552                       integer_one_node);
 553     lvar_one = build_stmt (EXPR_STMT, lvar_one);
 554     dchain_replace_stmt (*stmt, lvar_one);
 555     *stmt = lvar_one;
 556   }
 557
 558   if (one_if == 0)
 559     /* The BREAK_STMT is unconditional.  The logical variable is always true.
 560        That will allow outward_motion to eliminate dead code in some cases.  */
 561     {
 562       flow_out_of (PATH_CHILD (related_parent), PATH_TOP, lvar_one,
 563                    integer_one_node, update_break_paths);
 564
 565       /* Remove the FOR_EXPR, since when we break a loop we don't want to
 566          reevaluate it again.  After the break elimination, we exit the FOR_STMT
 567          after the evaluation of its FOR_COND.  If the loop contains a BREAK_STMT,
 568          then we evaluate the FOR_EXPR before exiting the FOR_STMT, and that is
 569          not the exact semantic of a BREAK_STMT.  */
 570       REMOVE_FOR_EXPR (related_loop);
 571
 572       /* Move the flow out of related_loop.  */
 573       outward_motion (related_loop, NULL_TREE, lvar, update_break_paths);
 574     }
 575   else
 576     /* The BREAK_STMT is conditional.  */
 577     flow_out_of (related_parent, PATH_TOP, lvar_one, lvar, update_break_paths);
 578
 579   /* Reinitialize to false the logical variable once we have left the loop.  */
 580   if (PREV_STMT (related_loop) && NEXT_STMT (related_loop))
 581     /* The given related_loop is in a statement chain : it is not a fake loop.  */
 582     dchain_insert_stmt_after
 583       (related_loop, build_stmt (EXPR_STMT,
 584                                  build_modify_expr (lvar, NOP_EXPR,
 585                                                     integer_zero_node)));
 586 }
 587
 588 /* If the LVAR is true, then LAST_EXECUTED is the last statement to be executed
 589    in the INNER structure (that can be an IF_STMT, WHILE_STMT, ... ).  The
 590    control is moved out of the OUTER structure under the control of LVAR.
 591    PATH_TYPE must be under the same implementation as the PATH defined above :
 592    a TREE_LIST and the inner element is the first element in the list.  */
 593
 594 void
 595 flow_out_of (PATH_TYPE outer, PATH_TYPE inner, tree last_to_be_executed,
 596              tree lvar, void (*update_paths_fnct) (tree, tree, tree, tree))
 597 {
 598   do {
 599     /* Remove the FOR_EXPR, since when we break a loop we don't want to
 600        reevaluate its FOR_EXPR again.  After the break elimination,
 601        we exit the FOR_STMT after the evaluation of its FOR_COND.
 602        If the loop contains a BREAK_STMT, then we evaluate the FOR_EXPR before
 603        exiting the FOR_STMT, and that is not the exact semantic of a BREAK_STMT.  */
 604     REMOVE_FOR_EXPR (PATH_STMT (inner));
 605
 606     outward_motion (PATH_STMT (inner), last_to_be_executed, lvar, update_paths_fnct);
 607
 608     last_to_be_executed = PATH_STMT (inner);
 609
 610   } while (PATH_STMT (inner) != PATH_STMT (outer)
 611            && (inner = PATH_PARENT (inner)));
 612 }
 613
 614 #undef REMOVE_FOR_EXPR
 615
 616 /* Make the control flow exit from a statement PARENT, by transforming control
 617    flow into data controlled flow.
 618    LAST_EXECUTED is the last statement that the caller wants to be executed in
 619    the current scope when the value of the logical variable LVAR becomes true.
 620    If the logical variable is 'integer_one_node', then the caller expects that
 621    the code following LAST_EXECUTED should never be executed.  If there are no
 622    entry points (LABEL_STMTs) between LAST_EXECUTED and the end of the scope,
 623    then we can eliminate dead code, else we insert the code following
 624    LAST_EXECUTED in an 'if (0)' statement.
 625
 626    Example :  "while (c) {s1; s2; s3; s4; s5;}"
 627    Calling outward_motion (WHILE_BODY (while), s3, integer_one_node)
 628    produces the following statement chain :
 629    "while (c) {s1; s2; s3;}"  if "s4; s5;" doesn't contain LABEL_STMTs.
 630    "while (c) {s1; s2; s3; if (1==0) {s4; s5;}}"  otherwise.
 631
 632    Example :  "while (c) {s1; s2;}"
 633    Calling outward_motion (while, NULL_TREE, lvar);
 634    produces the following statement chain :
 635    "while (lvar == 0 && c) {s1; s2;}".  */
 636
 637 static void
 638 outward_motion (tree parent, tree last_executed, tree lvar,
 639                 void (*update_paths_fnct) (tree, tree, tree, tree))
 640 {
 641   if (!parent)
 642     abort ();
 643
 644   switch (TREE_CODE (parent))
 645     {
 646     case COMPOUND_STMT:
 647       /* Move the control flow at the end of the COMPOUND_BODY under the control of lvar.  */
 648       {
 649         if (TREE_CODE (last_executed) == SCOPE_STMT
 650             && SCOPE_END_P (last_executed))
 651           /* LAST_EXECUTED is an end scope : nothing to do.  */
 652           return;
 653
 654         if (lvar == integer_one_node)
 655           /* The caller expects  'if (1 == 0) {rest_of_code;}' to be built.
 656              For removing dead code we have to determine wether the rest of
 657              code contains LABEL_STMTs that are potential entry points.
 658              These extra checking can be removed if we run this function
 659              after the goto elimination.  */
 660           if (!chain_contains_stmt_p (last_executed, LABEL_STMT))
 661             /* The COMPOUND_BODY doesn't contain LABEL_STMTs after LAST_EXECUTED,
 662                so we can safely remove this code.  */
 663             {
 664               /* FIXME : Maybe we delete some GOTO_STMTs without deleting them
 665                  from the GOTO_LIST... */
 666               dchain_delete_stmts (last_executed, tree_last (last_executed));
 667               return;
 668             }
 669
 670         /* Transform the chain <LAST_EXECUTED; rest_of_code;>
 671            into <LAST_EXECUTED; if (lvar==0) {rest_of_code;}>.  */
 672         eliminate_with_if (last_executed, tree_last (last_executed), lvar,
 673                            update_paths_fnct);
 674         break;
 675       }
 676
 677     case FOR_STMT:
 678     case WHILE_STMT:
 679     case DO_STMT:
 680       {
 681         /* Insert the stop condition in the loop condition.  */
 682         insert_andif_in_condition
 683           (build (EQ_EXPR, integer_type_node, lvar, integer_zero_node), parent);
 684         break;
 685       }
 686
 687     case IF_STMT:
 688       {
 689         /* Nothing to do.  */
 690         break;
 691       }
 692
 693     default:
 694       /* Nothing falls down here.  */
 695       abort ();
 696       break;
 697     }
 698 }
 699
 700 /* Update all paths used in the break_elimination pass.  In fact there's nothing
 701    to do since we work only on a single path top down, whereas in goto elimination
 702    we have to keep up to date a set of paths.  */
 703
 704 static void
 705 update_break_paths (tree st1, tree st2, tree begin_stmt, tree end_stmt)
 706 {
 707 }
 708
 709 /* Transforms a SWITCH_STMT in a nested IF_STMT.
 710    STMT is supposed to be a SWITCH_STMT.  */
 711
 712 static void
 713 switch_to_if (tree stmt)
 714 {
 715   tree switch_body;
 716   tree open_scope, close_scope;
 717   tree first_case_label;
 718   tree if_stmt;
 719
 720   if (TREE_CODE (stmt) != SWITCH_STMT)
 721     abort ();
 722
 723   switch_body = SWITCH_BODY (stmt);
 724   open_scope = COMPOUND_BODY (switch_body);
 725   close_scope = tree_last (open_scope);
 726   first_case_label = open_scope;
 727
 728   /* Search the first CASE_LABEL from the SWITCH_STMT.  */
 729   while (first_case_label && TREE_CODE (first_case_label) != CASE_LABEL)
 730     first_case_label = NEXT_STMT (first_case_label);
 731
 732   if (first_case_label == NULL_TREE)
 733     /* There aren't CASE_LABELs in this SWITCH_STMT.
 734        We have to delete the SWITCH_STMT.  */
 735     {
 736       dchain_delete_stmts (PREV_STMT (stmt), NEXT_STMT (stmt));
 737       return;
 738     }
 739
 740   /* Step 0: Delete all unreachable statements from the last declaration up to
 741      the first case_label.  Maybe we have to warn here that there's dead code
 742      in a switch?  */
 743   {
 744     tree last_decl;
 745
 746     last_decl = open_scope;
 747     while (TREE_CHAIN (last_decl) && TREE_CODE (TREE_CHAIN (last_decl)) == DECL_STMT)
 748       last_decl = TREE_CHAIN (last_decl);
 749
 750     dchain_delete_stmts (last_decl, first_case_label);
 751   }
 752
 753   /* Step 1: Include all statements of a CASE_LABEL in a COMPOUND_STMT.  */
 754   construct_body_for_case_labels (first_case_label);
 755
 756   /* Step 2: Copy statements from following CASE_LABELs : that simulates the
 757      fall through mechanism.  Eliminate BREAK_STMTs and dead code.  */
 758   complete_body_of_case_labels (first_case_label);
 759
 760   /* Step 3: Reorder CASE_LABELs in the SWITCH_STMT.  The minimum reorder is to
 761      place the default case at the last position.  */
 762   reorder_case_labels (first_case_label);
 763
 764   /* Replace the cursor on the first_case_label.  */
 765   first_case_label = open_scope;
 766   while (TREE_CODE (first_case_label) != CASE_LABEL)
 767     first_case_label = NEXT_STMT (first_case_label);
 768
 769   /* Step 4: Creates an IF_STMT for each CASE_LABEL :
 770      'if (switch_cond == case_number)'.  */
 771   if_stmt = cases_to_if (SWITCH_COND (stmt), first_case_label);
 772
 773   /* Step 5: Replace the SWITCH_STMT by its SWITCH_BODY in which we find all
 774      local definitions and the constructed IF_STMT.  */
 775   dchain_insert_chain (PREV_STMT (first_case_label), close_scope, if_stmt, if_stmt);
 776   eliminate_compound_stmts (COMPOUND_BODY (switch_body));
 777   dchain_replace_stmt (stmt, switch_body);
 778 }
 779
 780 /* NODE is the first CASE_LABEL of a SWITCH_STMT.  This function constructs a
 781    COMPOUND_STMT around the body of every CASE_LABEL of a SWITCH_STMT.  */
 782
 783 static void
 784 construct_body_for_case_labels (tree node)
 785 {
 786   tree case_label = node;
 787
 788   /* For each statement in SWITCH_BODY,  */
 789   while (node != NULL_TREE && NEXT_STMT (node) != NULL_TREE)
 790     {
 791       if (TREE_CODE (node) == CASE_LABEL
 792           && TREE_CODE (NEXT_STMT (node)) == CASE_LABEL)
 793         /* The CASE_LABEL is followed by another CASE_LABEL.
 794            Transform it into CASE_LABEL; COMPOUND_STMT; CASE_LABEL; with a
 795            COMPOUND_STMT empty.  It will be filled with code copied from the
 796            body of the next CASE_LABEL later in complete_body_of_case_labels ().  */
 797         {
 798           tree compound_stmt;
 799
 800           /* Construct an empty COMPOUND_STMT.  */
 801           compound_stmt = NULL_TREE;
 802           dchain_build_scope (&compound_stmt);
 803           dchain_insert_stmt_after (node, compound_stmt);
 804
 805           /* Next iteration.  */
 806           node = case_label = NEXT_STMT (compound_stmt);
 807           continue;
 808         }
 809
 810       if (TREE_CODE (node) == CASE_LABEL
 811           && TREE_CODE (NEXT_STMT (node)) == COMPOUND_STMT
 812           && (TREE_CODE (NEXT_STMT (NEXT_STMT (node))) == CASE_LABEL
 813               || NEXT_STMT (NEXT_STMT (NEXT_STMT (node))) == NULL_TREE))
 814         /* The case has already a COMPOUND_STMT : don't construct another one.  */
 815         {
 816           node = case_label = NEXT_STMT (NEXT_STMT (node));
 817           continue;
 818         }
 819
 820       if (TREE_CODE (NEXT_STMT (node)) == CASE_LABEL
 821           || NEXT_STMT (NEXT_STMT (node)) == NULL_TREE)
 822         /* The next statement ends the CASE_LABEL's body.  */
 823         {
 824           tree compound_stmt, next;
 825
 826           /* Store a pointer to the next statement.  */
 827           next = NEXT_STMT (node);
 828
 829           /* Construct a COMPOUND_STMT.  */
 830           compound_stmt = NULL_TREE;
 831           dchain_build_scope (&compound_stmt);
 832
 833           /* Rewire.  */
 834           {
 835             tree open_scope, close_scope;
 836
 837             open_scope = COMPOUND_BODY (compound_stmt);
 838             close_scope = NEXT_STMT (open_scope);
 839
 840             /* Insert statements that belongs to the CASE_LABEL in its body.  */
 841             dchain_insert_chain (open_scope, close_scope,
 842                                  NEXT_STMT (case_label), node);
 843
 844             dchain_insert_chain (case_label, next, compound_stmt, compound_stmt);
 845           }
 846
 847           /* Next iteration.  */
 848           node = case_label = next;
 849           continue;
 850         }
 851       else
 852         /* Next iteration.  */
 853         node = NEXT_STMT (node);
 854     }
 855 }
 856
 857 /* The following macros access a regular SWITCH_BODY : each CASE_LABEL has a
 858    body composed of a COMPOUND_STMT.  Thus we have a chain under the following
 859    format: CASE_LABEL; COMPOUND_STMT; CASE_LABEL; ... COMPOUND_STMT;.  */
 860 #define NEXT_CASE(NODE) NEXT_STMT (NEXT_STMT (NODE))
 861 #define PREV_CASE(NODE) PREV_STMT (PREV_STMT (NODE))
 862 #define FOREACH_CASE(NODE)  for (; TREE_CODE (NODE) != SCOPE_STMT; (NODE) = NEXT_CASE (NODE))
 863 #define FOREACH_CASE_BOTTOM_UP(NODE)  for (; NODE && TREE_CODE (NODE) == CASE_LABEL; NODE = PREV_CASE (NODE))
 864 #define LAST_CASE(NODE) for (; TREE_CODE (NEXT_CASE (NODE)) == CASE_LABEL; (NODE) = NEXT_CASE (NODE))
 865 #define CASE_BODY(NODE) NEXT_STMT (NODE)
 866
 867 /* NODE is the first CASE_LABEL of a SWITCH_STMT.  This function suposes that
 868    SWITCH_BODY is composed as described by the following schema :
 869    {CASE_LABEL; COMPOUND_STMT; CASE_LABEL; COMPOUND_STMT; ... COMPOUND_STMT;}
 870    every CASE_LABEL is followed by a COMPOUND_STMT.
 871    This function completes the body of a CASE_LABEL by copying statements in
 872    order to simulate the fall through mechanism.
 873
 874    FIXME: An optimized way to do this job is bottom-up : begin the completion of
 875    bodies from the last CASE_LABEL and follow the PREV_STMT chain.
 876    Apply the break and dead code elimination for each CASE_LABEL body before
 877    copying the code for the PREV_CASE.
 878
 879    The transformation is done bottom-up.
 880    Example of the execution of this algorithm :
 881    switch ()
 882    {
 883    case 1: {b1;}
 884    case 2: {b2;}
 885    case 3: {b3;}
 886    }
 887    0. Nothing to copy : "case 3" is the last in SWITCH_BODY.
 888    1. Apply break/dead code elimination on {b3;} gives {a3;}.
 889    switch ()
 890    {
 891    case 1: {b1;}
 892    case 2: {b2;}
 893    case 3: {a3;}
 894    }
 895    2. Copy a3; after b2;.
 896    switch ()
 897    {
 898    case 1: {b1;}
 899    case 2: {b2; a3;}
 900    case 3: {a3;}
 901    }
 902    3. Apply break/dead code elimination on {b2; a3;} gives {a2;}.
 903    switch ()
 904    {
 905    case 1: {b1;}
 906    case 2: {a2;}
 907    case 3: {a3;}
 908    }
 909    4. Copy a2; after b1;.
 910    switch ()
 911    {
 912    case 1: {b1; a2;}
 913    case 2: {a2;}
 914    case 3: {a3;}
 915    }
 916    5. Apply break/dead code elimination on {b1; a2;} gives {a1;}.
 917    switch ()
 918    {
 919    case 1: {a1;}
 920    case 2: {a2;}
 921    case 3: {a3;}
 922    }
 923    6. End.  */
 924
 925 static void
 926 complete_body_of_case_labels (tree node)
 927 {
 928   LAST_CASE (node);
 929
 930   /* For each CASE_LABEL in SWITCH_BODY,  */
 931   FOREACH_CASE_BOTTOM_UP (node)
 932     {
 933       tree last_stmt, next_case;
 934       tree close_scope;
 935
 936       close_scope = tree_last (COMPOUND_BODY (TREE_CHAIN (node)));
 937       last_stmt = PREV_STMT (close_scope);
 938       next_case = NEXT_CASE (node);
 939
 940       if (TREE_CODE (next_case) == CASE_LABEL)
 941         /* Copy the CASE_BODY of the next CASE_LABEL after the last
 942            statement of the body of this CASE_LABEL.  */
 943         {
 944           dchain_insert_stmt_after (last_stmt,
 945                                     dchain_deep_copy_node (CASE_BODY (next_case)));
 946
 947           /* Delete all LABEL_STMTs we've copied.  This way we avoid duplicated
 948              label definitions.  That is what we could call following the same
 949              terminology as McGill : 'avoid a LABEL_STMT capture'.  */
 950           dchain_delete_labels (COMPOUND_BODY (NEXT_STMT (last_stmt)));
 951         }
 952       /* else
 953          This is the last CASE_LABEL of the SWITCH_BODY : nothing to copy.  */
 954
 955       /* Eliminate BREAK_STMTs and dead code.  */
 956       {
 957         tree fake_do, fake_body;
 958
 959         fake_body = CASE_BODY (node);
 960
 961         /* Construct a fake DO_STMT whose body is the COMPOUND_STMT of this
 962            CASE_LABEL.  */
 963         fake_do = build_stmt (DO_STMT, integer_zero_node, fake_body);
 964
 965         /* 'break_elimination' is called only since we cannot eliminate
 966            CONTINUE_STMTs that refers to an outer loop.  CONTINUE_STMTs are
 967            eliminated once the SWITCH_STMT was completely transformed by
 968            reruning the pass once again on the produced IF_STMT.  */
 969         break_elimination (fake_do);
 970       }
 971     }
 972 }
 973
 974 /* NODE is the first CASE_LABEL statement of a SWITCH_BODY.
 975    This function suposes that a SWITCH_BODY is composed as described by the
 976    following schema :
 977    {CASE_LABEL; COMPOUND_STMT; CASE_LABEL; COMPOUND_STMT; ... COMPOUND_STMT;}
 978    every CASE_LABEL is followed by a COMPOUND_STMT.  Moreover it supposes that
 979    there's no fall through between cases, and that all BREAK_STMTs were deleted.
 980    This function reorder CASE_LABELs in the SWITCH_BODY.
 981    It performs for the moment the minimum : ensure that the DEFAULT case is the
 982    last case in the SWITCH_BODY.
 983    Other optimisations based on the reordering of cases could be implemented
 984    or rewritten (from switch_stack)*/
 985
 986 static void
 987 reorder_case_labels (tree node)
 988 {
 989   /* For each CASE_LABEL in SWITCH_BODY, search the DEFAULT case.  */
 990   FOREACH_CASE (node)
 991     {
 992       if (CASE_LOW (node) == NULL_TREE
 993           && CASE_HIGH (node) == NULL_TREE)
 994         /* That's the DEFAULT case : move it at the end of the SWITCH_BODY.  */
 995         {
 996           tree default_case;
 997           default_case = node;
 998
 999           if (TREE_CODE (NEXT_CASE (default_case)) == SCOPE_STMT)
1000             /* The DEFAULT case is well placed at the end of the SWITCH_BODY.  */
1001             break;
1002
1003           /* Delete the default_case from its position.  */
1004           dchain_delete_stmts (PREV_STMT (default_case), NEXT_CASE (default_case));
1005
1006           /* Search the last CASE_LABEL in this SWITCH_STMT.  */
1007           LAST_CASE (node);
1008
1009           node = CASE_BODY (node);
1010
1011           /* Add the default_case's body at the end of the SWITCH_BODY.  */
1012           dchain_insert_stmt_after (node, CASE_BODY (default_case));
1013
1014           /* Add the default_case label.  */
1015           dchain_insert_stmt_after (node, default_case);
1016
1017           /* That's all.  */
1018           break;
1019         }
1020     }
1021 }
1022
1023 /* NODE is a CASE_LABEL of a SWITCH_BODY.  SVAR is the SWITCH_COND.
1024    This function transforms all cases of a SWITCH_STMT into a nested IF_STMT.
1025    This function suposes that a SWITCH_BODY is composed as described by the
1026    following schema :
1027    {CASE_LABEL; COMPOUND_STMT; ... default: COMPOUND_STMT;}
1028    every CASE_LABEL is followed by a COMPOUND_STMT, there's no fall through
1029    between cases, all BREAK_STMTs were deleted, and the DEFAULT case is the last
1030    in the SWITCH_BODY.  */
1031
1032 static tree
1033 cases_to_if (tree svar, tree node)
1034 {
1035   tree then_clause, else_clause;
1036   tree low, high;
1037   tree cond;
1038
1039   if (TREE_CODE (node) == SCOPE_STMT)
1040     /* The previous CASE_LABEL was the last one.  That means that this
1041        SWITCH_STMT doesn't contain a DEFAULT case.  */
1042     return NULL_TREE;
1043
1044   low = CASE_LOW (node);
1045   high = CASE_HIGH (node);
1046   if (low && high)
1047     /* Range.  */
1048     {
1049       tree le, ge;
1050
1051       /* Construct the condition : (low >= svar && svar <= high).  */
1052       ge = build (GE_EXPR, integer_type_node, svar, low);
1053       le = build (LE_EXPR, integer_type_node, svar, high);
1054       cond = build (TRUTH_ANDIF_EXPR, integer_type_node, le, ge);
1055     }
1056   else if (low)
1057     /* A normal case.  Construct the condition : (svar == low).  */
1058     cond = build (EQ_EXPR, integer_type_node, svar, low);
1059   else
1060     /* The default case : we're on the last case of the SWITCH_BODY.  */
1061     {
1062       else_clause = CASE_BODY (node);
1063
1064       /* The else_clause becomes part of the IF_STMT : remove its pointers to
1065          the statemtent chain.  */
1066       NEXT_STMT (else_clause) = NULL_TREE;
1067       PREV_STMT (else_clause) = NULL_TREE;
1068
1069       return else_clause;
1070     }
1071
1072   then_clause = CASE_BODY (node);
1073   else_clause = cases_to_if (svar, NEXT_CASE (node));
1074
1075   /* The then_clause becomes part of the IF_STMT : remove its pointers to
1076      the statemtent chain.  */
1077   NEXT_STMT (then_clause) = NULL_TREE;
1078   PREV_STMT (then_clause) = NULL_TREE;
1079
1080   /* Be sure that the constructed else_clause has a scope.  */
1081   dchain_build_scope (&else_clause);
1082
1083   /* Construct an IF_STMT.  */
1084   return build_stmt (IF_STMT, cond, then_clause, else_clause);
1085 }
1086
1087 /* Eliminate COMPOUND_STMTs from the chain pointed by STMT.  Only COMPOUND_STMTs
1088    that doesn't contain variable declarations are opened and their statements
1089    are chained at STMT's level.  This function eliminate IF, WHILE, DO and FOR
1090    statements if the function eval_bool_condition is able to determine
1091    condition's valuation.  */
1092
1093 void
1094 eliminate_compound_stmts (tree stmt)
1095 {
1096   while (stmt != NULL_TREE)
1097     {
1098       switch (TREE_CODE (stmt))
1099         {
1100         case COMPOUND_STMT:
1101           if (!SCOPE_STMT_BLOCK (COMPOUND_BODY (stmt)))
1102             /* This COMPOUND_STMT doesn't contain declarations : open it.  */
1103             {
1104               tree prev;
1105               prev = PREV_STMT (stmt);
1106               dchain_insert_chain (prev, NEXT_STMT (stmt),
1107                                    /* First stmt is open_scope : don't copy it.  */
1108                                    NEXT_STMT (COMPOUND_BODY (stmt)),
1109                                    /* Last stmt is close_scope : don't copy it.  */
1110                                    PREV_STMT (tree_last (COMPOUND_BODY (stmt))));
1111               stmt = prev;
1112             }
1113           else
1114             /* Keep the COMPOUND_STMT, but remove unneeded COMPOUND_STMTs from
1115                its body.  */
1116             eliminate_compound_stmts (COMPOUND_BODY (stmt));
1117           break;
1118
1119         case FOR_STMT:
1120           {
1121             if (eval_bool_condition (FOR_COND (stmt)) == EVAL_FALSE
1122                 && !chain_contains_stmt_p (FOR_BODY (stmt), LABEL_STMT))
1123               /* Eliminate this FOR_STMT.  */
1124               dchain_delete_stmts (PREV_STMT (stmt), NEXT_STMT (stmt));
1125             else
1126               /* Keep the FOR_STMT, but eliminate unneeded COMPOUND_STMTs from
1127                  its body.  */
1128               {
1129                 dchain_build_scope (&FOR_BODY (stmt));
1130                 eliminate_compound_stmts (COMPOUND_BODY (FOR_BODY (stmt)));
1131               }
1132             break;
1133           }
1134
1135         case WHILE_STMT:
1136           {
1137             if (eval_bool_condition (WHILE_COND (stmt)) == EVAL_FALSE
1138                 && !chain_contains_stmt_p (WHILE_BODY (stmt), LABEL_STMT))
1139               /* Eliminate this WHILE_STMT.  */
1140               dchain_delete_stmts (PREV_STMT (stmt), NEXT_STMT (stmt));
1141             else
1142               /* Keep the WHILE_STMT, but eliminate unneeded COMPOUND_STMTs from
1143                  its body.  */
1144               {
1145                 dchain_build_scope (&WHILE_BODY (stmt));
1146                 eliminate_compound_stmts (COMPOUND_BODY (WHILE_BODY (stmt)));
1147               }
1148             break;
1149           }
1150
1151         case DO_STMT:
1152           {
1153             if (eval_bool_condition (DO_COND (stmt)) == EVAL_FALSE
1154                 && !chain_contains_stmt_p (DO_BODY (stmt), LABEL_STMT))
1155               /* Eliminate this DO_STMT : keep only its DO_BODY.  */
1156               {
1157                 dchain_replace_stmt (stmt, DO_BODY (stmt));
1158                 stmt = DO_BODY (stmt);
1159
1160                 /* Eliminate COMPOUND_STMTs from DO_BODY.  */
1161                 continue;
1162               }
1163             else
1164               /* Keep the DO_STMT, but eliminate unneeded COMPOUND_STMTs from
1165                  its body.  */
1166               {
1167                 dchain_build_scope (&DO_BODY (stmt));
1168                 eliminate_compound_stmts (COMPOUND_BODY (DO_BODY (stmt)));
1169                 break;
1170               }
1171           }
1172
1173         case SWITCH_STMT:
1174           dchain_build_scope (&SWITCH_BODY (stmt));
1175           eliminate_compound_stmts (COMPOUND_BODY (SWITCH_BODY (stmt)));
1176           break;
1177
1178         case IF_STMT:
1179           {
1180             enum eval_bool evc;
1181             evc = eval_bool_condition (IF_COND (stmt));
1182
1183             if (evc == EVAL_TRUE
1184                 && !chain_contains_stmt_p (ELSE_CLAUSE (stmt), LABEL_STMT))
1185               /* Eliminate this IF_STMT : keep only its THEN_CLAUSE.  */
1186               {
1187                 dchain_build_scope (&THEN_CLAUSE (stmt));
1188                 dchain_replace_stmt (stmt, THEN_CLAUSE (stmt));
1189                 stmt = THEN_CLAUSE (stmt);
1190                 continue;
1191               }
1192             else if (evc == EVAL_FALSE
1193                      && !chain_contains_stmt_p (THEN_CLAUSE (stmt), LABEL_STMT))
1194               /* Eliminate this IF_STMT : keep only its ELSE_CLAUSE.  */
1195               {
1196                 dchain_build_scope (&ELSE_CLAUSE (stmt));
1197                 dchain_replace_stmt (stmt, ELSE_CLAUSE (stmt));
1198                 stmt = ELSE_CLAUSE (stmt);
1199                 continue;
1200               }
1201             else
1202               /* Keep both clauses of the IF_STMT.  */
1203               {
1204                 dchain_build_scope (&THEN_CLAUSE (stmt));
1205                 dchain_build_scope (&ELSE_CLAUSE (stmt));
1206                 eliminate_compound_stmts (COMPOUND_BODY (THEN_CLAUSE (stmt)));
1207                 eliminate_compound_stmts (COMPOUND_BODY (ELSE_CLAUSE (stmt)));
1208               }
1209             break;
1210           }
1211
1212         default:
1213           /* Nothing to do.  */
1214           break;
1215         }
1216
1217       /* Next iteration.  */
1218       stmt = NEXT_STMT (stmt);
1219     }
1220 }
1221
1222 /* Try to evaluate the boolean value of EXPR.  */
1223
1224 static enum eval_bool
1225 eval_bool_condition (tree expr)
1226 {
1227   tree f;
1228   f = fold (expr);
1229
1230   switch (TREE_CODE (f))
1231     {
1232     case INTEGER_CST:
1233       if (TREE_INT_CST_LOW (f) == 0)
1234         return EVAL_FALSE;
1235       else
1236         return EVAL_TRUE;
1237
1238     case NE_EXPR:
1239     case EQ_EXPR:
1240       {
1241         tree op0, op1;
1242         op0 = TREE_OPERAND (f, 0);
1243         op1 = TREE_OPERAND (f, 1);
1244
1245         if (TREE_CODE (op0) == INTEGER_CST
1246             && TREE_CODE (op1) == INTEGER_CST)
1247           /* Both operands are integers.  */
1248           {
1249             int i0, i1;
1250             i0 = TREE_INT_CST_LOW (op0);
1251             i1 = TREE_INT_CST_LOW (op1);
1252
1253             if (TREE_CODE (f) == EQ_EXPR)
1254               {
1255                 if (i0 == i1)
1256                   return EVAL_TRUE;
1257                 else
1258                   return EVAL_FALSE;
1259               }
1260             else /* NE_EXPR */
1261               {
1262                 if (i0 != i1)
1263                   return EVAL_TRUE;
1264                 else
1265                   return EVAL_FALSE;
1266               }
1267           }
1268         else
1269           return EVAL_DONT_KNOW;
1270       }
1271
1272     default:
1273       return EVAL_DONT_KNOW;
1274     }
1275 }