gcc/dojump.c

   1 /* Convert tree expression to rtl instructions, for GNU compiler.
   2    Copyright (C) 1988-2016 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 3, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #include "config.h"
  21 #include "system.h"
  22 #include "coretypes.h"
  23 #include "backend.h"
  24 #include "target.h"
  25 #include "rtl.h"
  26 #include "tree.h"
  27 #include "predict.h"
  28 #include "tm_p.h"
  29 #include "optabs.h"
  30 #include "emit-rtl.h"
  31 #include "fold-const.h"
  32 #include "stor-layout.h"
  33 /* Include expr.h after insn-config.h so we get HAVE_conditional_move.  */
  34 #include "dojump.h"
  35 #include "explow.h"
  36 #include "expr.h"
  37 #include "langhooks.h"
  38
  39 static bool prefer_and_bit_test (machine_mode, int);
  40 static void do_jump_by_parts_greater (tree, tree, int,
  41                                       rtx_code_label *, rtx_code_label *, int);
  42 static void do_jump_by_parts_equality (tree, tree, rtx_code_label *,
  43                                        rtx_code_label *, int);
  44 static void do_compare_and_jump (tree, tree, enum rtx_code, enum rtx_code,
  45                                  rtx_code_label *, rtx_code_label *, int);
  46
  47 /* Invert probability if there is any.  -1 stands for unknown.  */
  48
  49 static inline int
  50 inv (int prob)
  51 {
  52   return prob == -1 ? -1 : REG_BR_PROB_BASE - prob;
  53 }
  54
  55 /* At the start of a function, record that we have no previously-pushed
  56    arguments waiting to be popped.  */
  57
  58 void
  59 init_pending_stack_adjust (void)
  60 {
  61   pending_stack_adjust = 0;
  62 }
  63
  64 /* Discard any pending stack adjustment.  This avoid relying on the
  65    RTL optimizers to remove useless adjustments when we know the
  66    stack pointer value is dead.  */
  67 void
  68 discard_pending_stack_adjust (void)
  69 {
  70   stack_pointer_delta -= pending_stack_adjust;
  71   pending_stack_adjust = 0;
  72 }
  73
  74 /* When exiting from function, if safe, clear out any pending stack adjust
  75    so the adjustment won't get done.
  76
  77    Note, if the current function calls alloca, then it must have a
  78    frame pointer regardless of the value of flag_omit_frame_pointer.  */
  79
  80 void
  81 clear_pending_stack_adjust (void)
  82 {
  83   if (optimize > 0
  84       && (! flag_omit_frame_pointer || cfun->calls_alloca)
  85       && EXIT_IGNORE_STACK)
  86     discard_pending_stack_adjust ();
  87 }
  88
  89 /* Pop any previously-pushed arguments that have not been popped yet.  */
  90
  91 void
  92 do_pending_stack_adjust (void)
  93 {
  94   if (inhibit_defer_pop == 0)
  95     {
  96       if (pending_stack_adjust != 0)
  97         adjust_stack (GEN_INT (pending_stack_adjust));
  98       pending_stack_adjust = 0;
  99     }
 100 }
 101
 102 /* Remember pending_stack_adjust/stack_pointer_delta.
 103    To be used around code that may call do_pending_stack_adjust (),
 104    but the generated code could be discarded e.g. using delete_insns_since.  */
 105
 106 void
 107 save_pending_stack_adjust (saved_pending_stack_adjust *save)
 108 {
 109   save->x_pending_stack_adjust = pending_stack_adjust;
 110   save->x_stack_pointer_delta = stack_pointer_delta;
 111 }
 112
 113 /* Restore the saved pending_stack_adjust/stack_pointer_delta.  */
 114
 115 void
 116 restore_pending_stack_adjust (saved_pending_stack_adjust *save)
 117 {
 118   if (inhibit_defer_pop == 0)
 119     {
 120       pending_stack_adjust = save->x_pending_stack_adjust;
 121       stack_pointer_delta = save->x_stack_pointer_delta;
 122     }
 123 }
 124 \f
 125 /* Expand conditional expressions.  */
 126
 127 /* Generate code to evaluate EXP and jump to LABEL if the value is zero.  */
 128
 129 void
 130 jumpifnot (tree exp, rtx_code_label *label, int prob)
 131 {
 132   do_jump (exp, label, NULL, inv (prob));
 133 }
 134
 135 void
 136 jumpifnot_1 (enum tree_code code, tree op0, tree op1, rtx_code_label *label,
 137              int prob)
 138 {
 139   do_jump_1 (code, op0, op1, label, NULL, inv (prob));
 140 }
 141
 142 /* Generate code to evaluate EXP and jump to LABEL if the value is nonzero.  */
 143
 144 void
 145 jumpif (tree exp, rtx_code_label *label, int prob)
 146 {
 147   do_jump (exp, NULL, label, prob);
 148 }
 149
 150 void
 151 jumpif_1 (enum tree_code code, tree op0, tree op1,
 152           rtx_code_label *label, int prob)
 153 {
 154   do_jump_1 (code, op0, op1, NULL, label, prob);
 155 }
 156
 157 /* Used internally by prefer_and_bit_test.  */
 158
 159 static GTY(()) rtx and_reg;
 160 static GTY(()) rtx and_test;
 161 static GTY(()) rtx shift_test;
 162
 163 /* Compare the relative costs of "(X & (1 << BITNUM))" and "(X >> BITNUM) & 1",
 164    where X is an arbitrary register of mode MODE.  Return true if the former
 165    is preferred.  */
 166
 167 static bool
 168 prefer_and_bit_test (machine_mode mode, int bitnum)
 169 {
 170   bool speed_p;
 171   wide_int mask = wi::set_bit_in_zero (bitnum, GET_MODE_PRECISION (mode));
 172
 173   if (and_test == 0)
 174     {
 175       /* Set up rtxes for the two variations.  Use NULL as a placeholder
 176          for the BITNUM-based constants.  */
 177       and_reg = gen_rtx_REG (mode, LAST_VIRTUAL_REGISTER + 1);
 178       and_test = gen_rtx_AND (mode, and_reg, NULL);
 179       shift_test = gen_rtx_AND (mode, gen_rtx_ASHIFTRT (mode, and_reg, NULL),
 180                                 const1_rtx);
 181     }
 182   else
 183     {
 184       /* Change the mode of the previously-created rtxes.  */
 185       PUT_MODE (and_reg, mode);
 186       PUT_MODE (and_test, mode);
 187       PUT_MODE (shift_test, mode);
 188       PUT_MODE (XEXP (shift_test, 0), mode);
 189     }
 190
 191   /* Fill in the integers.  */
 192   XEXP (and_test, 1) = immed_wide_int_const (mask, mode);
 193   XEXP (XEXP (shift_test, 0), 1) = GEN_INT (bitnum);
 194
 195   speed_p = optimize_insn_for_speed_p ();
 196   return (rtx_cost (and_test, mode, IF_THEN_ELSE, 0, speed_p)
 197           <= rtx_cost (shift_test, mode, IF_THEN_ELSE, 0, speed_p));
 198 }
 199
 200 /* Subroutine of do_jump, dealing with exploded comparisons of the type
 201    OP0 CODE OP1 .  IF_FALSE_LABEL and IF_TRUE_LABEL like in do_jump.
 202    PROB is probability of jump to if_true_label, or -1 if unknown.  */
 203
 204 void
 205 do_jump_1 (enum tree_code code, tree op0, tree op1,
 206            rtx_code_label *if_false_label, rtx_code_label *if_true_label,
 207            int prob)
 208 {
 209   machine_mode mode;
 210   rtx_code_label *drop_through_label = 0;
 211
 212   switch (code)
 213     {
 214     case EQ_EXPR:
 215       {
 216         tree inner_type = TREE_TYPE (op0);
 217
 218         gcc_assert (GET_MODE_CLASS (TYPE_MODE (inner_type))
 219                     != MODE_COMPLEX_FLOAT);
 220         gcc_assert (GET_MODE_CLASS (TYPE_MODE (inner_type))
 221                     != MODE_COMPLEX_INT);
 222
 223         if (integer_zerop (op1))
 224           do_jump (op0, if_true_label, if_false_label, inv (prob));
 225         else if (GET_MODE_CLASS (TYPE_MODE (inner_type)) == MODE_INT
 226                  && !can_compare_p (EQ, TYPE_MODE (inner_type), ccp_jump))
 227           do_jump_by_parts_equality (op0, op1, if_false_label, if_true_label,
 228                                      prob);
 229         else
 230           do_compare_and_jump (op0, op1, EQ, EQ, if_false_label, if_true_label,
 231                                prob);
 232         break;
 233       }
 234
 235     case NE_EXPR:
 236       {
 237         tree inner_type = TREE_TYPE (op0);
 238
 239         gcc_assert (GET_MODE_CLASS (TYPE_MODE (inner_type))
 240                     != MODE_COMPLEX_FLOAT);
 241         gcc_assert (GET_MODE_CLASS (TYPE_MODE (inner_type))
 242                     != MODE_COMPLEX_INT);
 243
 244         if (integer_zerop (op1))
 245           do_jump (op0, if_false_label, if_true_label, prob);
 246         else if (GET_MODE_CLASS (TYPE_MODE (inner_type)) == MODE_INT
 247            && !can_compare_p (NE, TYPE_MODE (inner_type), ccp_jump))
 248           do_jump_by_parts_equality (op0, op1, if_true_label, if_false_label,
 249                                      inv (prob));
 250         else
 251           do_compare_and_jump (op0, op1, NE, NE, if_false_label, if_true_label,
 252                                prob);
 253         break;
 254       }
 255
 256     case LT_EXPR:
 257       mode = TYPE_MODE (TREE_TYPE (op0));
 258       if (GET_MODE_CLASS (mode) == MODE_INT
 259           && ! can_compare_p (LT, mode, ccp_jump))
 260         do_jump_by_parts_greater (op0, op1, 1, if_false_label, if_true_label,
 261                                   prob);
 262       else
 263         do_compare_and_jump (op0, op1, LT, LTU, if_false_label, if_true_label,
 264                              prob);
 265       break;
 266
 267     case LE_EXPR:
 268       mode = TYPE_MODE (TREE_TYPE (op0));
 269       if (GET_MODE_CLASS (mode) == MODE_INT
 270           && ! can_compare_p (LE, mode, ccp_jump))
 271         do_jump_by_parts_greater (op0, op1, 0, if_true_label, if_false_label,
 272                                   inv (prob));
 273       else
 274         do_compare_and_jump (op0, op1, LE, LEU, if_false_label, if_true_label,
 275                              prob);
 276       break;
 277
 278     case GT_EXPR:
 279       mode = TYPE_MODE (TREE_TYPE (op0));
 280       if (GET_MODE_CLASS (mode) == MODE_INT
 281           && ! can_compare_p (GT, mode, ccp_jump))
 282         do_jump_by_parts_greater (op0, op1, 0, if_false_label, if_true_label,
 283                                   prob);
 284       else
 285         do_compare_and_jump (op0, op1, GT, GTU, if_false_label, if_true_label,
 286                              prob);
 287       break;
 288
 289     case GE_EXPR:
 290       mode = TYPE_MODE (TREE_TYPE (op0));
 291       if (GET_MODE_CLASS (mode) == MODE_INT
 292           && ! can_compare_p (GE, mode, ccp_jump))
 293         do_jump_by_parts_greater (op0, op1, 1, if_true_label, if_false_label,
 294                                   inv (prob));
 295       else
 296         do_compare_and_jump (op0, op1, GE, GEU, if_false_label, if_true_label,
 297                              prob);
 298       break;
 299
 300     case ORDERED_EXPR:
 301       do_compare_and_jump (op0, op1, ORDERED, ORDERED,
 302                            if_false_label, if_true_label, prob);
 303       break;
 304
 305     case UNORDERED_EXPR:
 306       do_compare_and_jump (op0, op1, UNORDERED, UNORDERED,
 307                            if_false_label, if_true_label, prob);
 308       break;
 309
 310     case UNLT_EXPR:
 311       do_compare_and_jump (op0, op1, UNLT, UNLT, if_false_label, if_true_label,
 312                            prob);
 313       break;
 314
 315     case UNLE_EXPR:
 316       do_compare_and_jump (op0, op1, UNLE, UNLE, if_false_label, if_true_label,
 317                            prob);
 318       break;
 319
 320     case UNGT_EXPR:
 321       do_compare_and_jump (op0, op1, UNGT, UNGT, if_false_label, if_true_label,
 322                            prob);
 323       break;
 324
 325     case UNGE_EXPR:
 326       do_compare_and_jump (op0, op1, UNGE, UNGE, if_false_label, if_true_label,
 327                            prob);
 328       break;
 329
 330     case UNEQ_EXPR:
 331       do_compare_and_jump (op0, op1, UNEQ, UNEQ, if_false_label, if_true_label,
 332                            prob);
 333       break;
 334
 335     case LTGT_EXPR:
 336       do_compare_and_jump (op0, op1, LTGT, LTGT, if_false_label, if_true_label,
 337                            prob);
 338       break;
 339
 340     case TRUTH_ANDIF_EXPR:
 341       {
 342         /* Spread the probability that the expression is false evenly between
 343            the two conditions. So the first condition is false half the total
 344            probability of being false. The second condition is false the other
 345            half of the total probability of being false, so its jump has a false
 346            probability of half the total, relative to the probability we
 347            reached it (i.e. the first condition was true).  */
 348         int op0_prob = -1;
 349         int op1_prob = -1;
 350         if (prob != -1)
 351           {
 352             int false_prob = inv (prob);
 353             int op0_false_prob = false_prob / 2;
 354             int op1_false_prob = GCOV_COMPUTE_SCALE ((false_prob / 2),
 355                                                      inv (op0_false_prob));
 356             /* Get the probability that each jump below is true.  */
 357             op0_prob = inv (op0_false_prob);
 358             op1_prob = inv (op1_false_prob);
 359           }
 360         if (if_false_label == NULL)
 361           {
 362             drop_through_label = gen_label_rtx ();
 363             do_jump (op0, drop_through_label, NULL, op0_prob);
 364             do_jump (op1, NULL, if_true_label, op1_prob);
 365           }
 366         else
 367           {
 368             do_jump (op0, if_false_label, NULL, op0_prob);
 369             do_jump (op1, if_false_label, if_true_label, op1_prob);
 370           }
 371         break;
 372       }
 373
 374     case TRUTH_ORIF_EXPR:
 375       {
 376         /* Spread the probability evenly between the two conditions. So
 377            the first condition has half the total probability of being true.
 378            The second condition has the other half of the total probability,
 379            so its jump has a probability of half the total, relative to
 380            the probability we reached it (i.e. the first condition was false).  */
 381         int op0_prob = -1;
 382         int op1_prob = -1;
 383         if (prob != -1)
 384           {
 385             op0_prob = prob / 2;
 386             op1_prob = GCOV_COMPUTE_SCALE ((prob / 2), inv (op0_prob));
 387           }
 388         if (if_true_label == NULL)
 389           {
 390             drop_through_label = gen_label_rtx ();
 391             do_jump (op0, NULL, drop_through_label, op0_prob);
 392             do_jump (op1, if_false_label, NULL, op1_prob);
 393           }
 394         else
 395           {
 396             do_jump (op0, NULL, if_true_label, op0_prob);
 397             do_jump (op1, if_false_label, if_true_label, op1_prob);
 398           }
 399         break;
 400       }
 401
 402     default:
 403       gcc_unreachable ();
 404     }
 405
 406   if (drop_through_label)
 407     {
 408       do_pending_stack_adjust ();
 409       emit_label (drop_through_label);
 410     }
 411 }
 412
 413 /* Generate code to evaluate EXP and jump to IF_FALSE_LABEL if
 414    the result is zero, or IF_TRUE_LABEL if the result is one.
 415    Either of IF_FALSE_LABEL and IF_TRUE_LABEL may be zero,
 416    meaning fall through in that case.
 417
 418    do_jump always does any pending stack adjust except when it does not
 419    actually perform a jump.  An example where there is no jump
 420    is when EXP is `(foo (), 0)' and IF_FALSE_LABEL is null.
 421
 422    PROB is probability of jump to if_true_label, or -1 if unknown.  */
 423
 424 void
 425 do_jump (tree exp, rtx_code_label *if_false_label,
 426          rtx_code_label *if_true_label, int prob)
 427 {
 428   enum tree_code code = TREE_CODE (exp);
 429   rtx temp;
 430   int i;
 431   tree type;
 432   machine_mode mode;
 433   rtx_code_label *drop_through_label = NULL;
 434
 435   switch (code)
 436     {
 437     case ERROR_MARK:
 438       break;
 439
 440     case INTEGER_CST:
 441       {
 442         rtx_code_label *lab = integer_zerop (exp) ? if_false_label
 443                                                   : if_true_label;
 444         if (lab)
 445           emit_jump (lab);
 446         break;
 447       }
 448
 449 #if 0
 450       /* This is not true with #pragma weak  */
 451     case ADDR_EXPR:
 452       /* The address of something can never be zero.  */
 453       if (if_true_label)
 454         emit_jump (if_true_label);
 455       break;
 456 #endif
 457
 458     case NOP_EXPR:
 459       if (TREE_CODE (TREE_OPERAND (exp, 0)) == COMPONENT_REF
 460           || TREE_CODE (TREE_OPERAND (exp, 0)) == BIT_FIELD_REF
 461           || TREE_CODE (TREE_OPERAND (exp, 0)) == ARRAY_REF
 462           || TREE_CODE (TREE_OPERAND (exp, 0)) == ARRAY_RANGE_REF)
 463         goto normal;
 464     case CONVERT_EXPR:
 465       /* If we are narrowing the operand, we have to do the compare in the
 466          narrower mode.  */
 467       if ((TYPE_PRECISION (TREE_TYPE (exp))
 468            < TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (exp, 0)))))
 469         goto normal;
 470     case NON_LVALUE_EXPR:
 471     case ABS_EXPR:
 472     case NEGATE_EXPR:
 473     case LROTATE_EXPR:
 474     case RROTATE_EXPR:
 475       /* These cannot change zero->nonzero or vice versa.  */
 476       do_jump (TREE_OPERAND (exp, 0), if_false_label, if_true_label, prob);
 477       break;
 478
 479     case TRUTH_NOT_EXPR:
 480       do_jump (TREE_OPERAND (exp, 0), if_true_label, if_false_label,
 481                inv (prob));
 482       break;
 483
 484     case COND_EXPR:
 485       {
 486         rtx_code_label *label1 = gen_label_rtx ();
 487         if (!if_true_label || !if_false_label)
 488           {
 489             drop_through_label = gen_label_rtx ();
 490             if (!if_true_label)
 491               if_true_label = drop_through_label;
 492             if (!if_false_label)
 493               if_false_label = drop_through_label;
 494           }
 495
 496         do_pending_stack_adjust ();
 497         do_jump (TREE_OPERAND (exp, 0), label1, NULL, -1);
 498         do_jump (TREE_OPERAND (exp, 1), if_false_label, if_true_label, prob);
 499         emit_label (label1);
 500         do_jump (TREE_OPERAND (exp, 2), if_false_label, if_true_label, prob);
 501         break;
 502       }
 503
 504     case COMPOUND_EXPR:
 505       /* Lowered by gimplify.c.  */
 506       gcc_unreachable ();
 507
 508     case MINUS_EXPR:
 509       /* Nonzero iff operands of minus differ.  */
 510       code = NE_EXPR;
 511
 512       /* FALLTHRU */
 513     case EQ_EXPR:
 514     case NE_EXPR:
 515     case LT_EXPR:
 516     case LE_EXPR:
 517     case GT_EXPR:
 518     case GE_EXPR:
 519     case ORDERED_EXPR:
 520     case UNORDERED_EXPR:
 521     case UNLT_EXPR:
 522     case UNLE_EXPR:
 523     case UNGT_EXPR:
 524     case UNGE_EXPR:
 525     case UNEQ_EXPR:
 526     case LTGT_EXPR:
 527     case TRUTH_ANDIF_EXPR:
 528     case TRUTH_ORIF_EXPR:
 529     other_code:
 530       do_jump_1 (code, TREE_OPERAND (exp, 0), TREE_OPERAND (exp, 1),
 531                  if_false_label, if_true_label, prob);
 532       break;
 533
 534     case BIT_AND_EXPR:
 535       /* fold_single_bit_test() converts (X & (1 << C)) into (X >> C) & 1.
 536          See if the former is preferred for jump tests and restore it
 537          if so.  */
 538       if (integer_onep (TREE_OPERAND (exp, 1)))
 539         {
 540           tree exp0 = TREE_OPERAND (exp, 0);
 541           rtx_code_label *set_label, *clr_label;
 542           int setclr_prob = prob;
 543
 544           /* Strip narrowing integral type conversions.  */
 545           while (CONVERT_EXPR_P (exp0)
 546                  && TREE_OPERAND (exp0, 0) != error_mark_node
 547                  && TYPE_PRECISION (TREE_TYPE (exp0))
 548                     <= TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (exp0, 0))))
 549             exp0 = TREE_OPERAND (exp0, 0);
 550
 551           /* "exp0 ^ 1" inverts the sense of the single bit test.  */
 552           if (TREE_CODE (exp0) == BIT_XOR_EXPR
 553               && integer_onep (TREE_OPERAND (exp0, 1)))
 554             {
 555               exp0 = TREE_OPERAND (exp0, 0);
 556               clr_label = if_true_label;
 557               set_label = if_false_label;
 558               setclr_prob = inv (prob);
 559             }
 560           else
 561             {
 562               clr_label = if_false_label;
 563               set_label = if_true_label;
 564             }
 565
 566           if (TREE_CODE (exp0) == RSHIFT_EXPR)
 567             {
 568               tree arg = TREE_OPERAND (exp0, 0);
 569               tree shift = TREE_OPERAND (exp0, 1);
 570               tree argtype = TREE_TYPE (arg);
 571               if (TREE_CODE (shift) == INTEGER_CST
 572                   && compare_tree_int (shift, 0) >= 0
 573                   && compare_tree_int (shift, HOST_BITS_PER_WIDE_INT) < 0
 574                   && prefer_and_bit_test (TYPE_MODE (argtype),
 575                                           TREE_INT_CST_LOW (shift)))
 576                 {
 577                   unsigned HOST_WIDE_INT mask
 578                     = (unsigned HOST_WIDE_INT) 1 << TREE_INT_CST_LOW (shift);
 579                   do_jump (build2 (BIT_AND_EXPR, argtype, arg,
 580                                    build_int_cstu (argtype, mask)),
 581                            clr_label, set_label, setclr_prob);
 582                   break;
 583                 }
 584             }
 585         }
 586
 587       /* If we are AND'ing with a small constant, do this comparison in the
 588          smallest type that fits.  If the machine doesn't have comparisons
 589          that small, it will be converted back to the wider comparison.
 590          This helps if we are testing the sign bit of a narrower object.
 591          combine can't do this for us because it can't know whether a
 592          ZERO_EXTRACT or a compare in a smaller mode exists, but we do.  */
 593
 594       if (! SLOW_BYTE_ACCESS
 595           && TREE_CODE (TREE_OPERAND (exp, 1)) == INTEGER_CST
 596           && TYPE_PRECISION (TREE_TYPE (exp)) <= HOST_BITS_PER_WIDE_INT
 597           && (i = tree_floor_log2 (TREE_OPERAND (exp, 1))) >= 0
 598           && (mode = mode_for_size (i + 1, MODE_INT, 0)) != BLKmode
 599           && (type = lang_hooks.types.type_for_mode (mode, 1)) != 0
 600           && TYPE_PRECISION (type) < TYPE_PRECISION (TREE_TYPE (exp))
 601           && have_insn_for (COMPARE, TYPE_MODE (type)))
 602         {
 603           do_jump (fold_convert (type, exp), if_false_label, if_true_label,
 604                    prob);
 605           break;
 606         }
 607
 608       if (TYPE_PRECISION (TREE_TYPE (exp)) > 1
 609           || TREE_CODE (TREE_OPERAND (exp, 1)) == INTEGER_CST)
 610         goto normal;
 611
 612       /* Boolean comparisons can be compiled as TRUTH_AND_EXPR.  */
 613
 614     case TRUTH_AND_EXPR:
 615       /* High branch cost, expand as the bitwise AND of the conditions.
 616          Do the same if the RHS has side effects, because we're effectively
 617          turning a TRUTH_AND_EXPR into a TRUTH_ANDIF_EXPR.  */
 618       if (BRANCH_COST (optimize_insn_for_speed_p (),
 619                        false) >= 4
 620           || TREE_SIDE_EFFECTS (TREE_OPERAND (exp, 1)))
 621         goto normal;
 622       code = TRUTH_ANDIF_EXPR;
 623       goto other_code;
 624
 625     case BIT_IOR_EXPR:
 626     case TRUTH_OR_EXPR:
 627       /* High branch cost, expand as the bitwise OR of the conditions.
 628          Do the same if the RHS has side effects, because we're effectively
 629          turning a TRUTH_OR_EXPR into a TRUTH_ORIF_EXPR.  */
 630       if (BRANCH_COST (optimize_insn_for_speed_p (), false) >= 4
 631           || TREE_SIDE_EFFECTS (TREE_OPERAND (exp, 1)))
 632         goto normal;
 633       code = TRUTH_ORIF_EXPR;
 634       goto other_code;
 635
 636       /* Fall through and generate the normal code.  */
 637     default:
 638     normal:
 639       temp = expand_normal (exp);
 640       do_pending_stack_adjust ();
 641       /* The RTL optimizers prefer comparisons against pseudos.  */
 642       if (GET_CODE (temp) == SUBREG)
 643         {
 644           /* Compare promoted variables in their promoted mode.  */
 645           if (SUBREG_PROMOTED_VAR_P (temp)
 646               && REG_P (XEXP (temp, 0)))
 647             temp = XEXP (temp, 0);
 648           else
 649             temp = copy_to_reg (temp);
 650         }
 651       do_compare_rtx_and_jump (temp, CONST0_RTX (GET_MODE (temp)),
 652                                NE, TYPE_UNSIGNED (TREE_TYPE (exp)),
 653                                GET_MODE (temp), NULL_RTX,
 654                                if_false_label, if_true_label, prob);
 655     }
 656
 657   if (drop_through_label)
 658     {
 659       do_pending_stack_adjust ();
 660       emit_label (drop_through_label);
 661     }
 662 }
 663 \f
 664 /* Compare OP0 with OP1, word at a time, in mode MODE.
 665    UNSIGNEDP says to do unsigned comparison.
 666    Jump to IF_TRUE_LABEL if OP0 is greater, IF_FALSE_LABEL otherwise.  */
 667
 668 static void
 669 do_jump_by_parts_greater_rtx (machine_mode mode, int unsignedp, rtx op0,
 670                               rtx op1, rtx_code_label *if_false_label,
 671                               rtx_code_label *if_true_label,
 672                               int prob)
 673 {
 674   int nwords = (GET_MODE_SIZE (mode) / UNITS_PER_WORD);
 675   rtx_code_label *drop_through_label = 0;
 676   bool drop_through_if_true = false, drop_through_if_false = false;
 677   enum rtx_code code = GT;
 678   int i;
 679
 680   if (! if_true_label || ! if_false_label)
 681     drop_through_label = gen_label_rtx ();
 682   if (! if_true_label)
 683     {
 684       if_true_label = drop_through_label;
 685       drop_through_if_true = true;
 686     }
 687   if (! if_false_label)
 688     {
 689       if_false_label = drop_through_label;
 690       drop_through_if_false = true;
 691     }
 692
 693   /* Deal with the special case 0 > x: only one comparison is necessary and
 694      we reverse it to avoid jumping to the drop-through label.  */
 695   if (op0 == const0_rtx && drop_through_if_true && !drop_through_if_false)
 696     {
 697       code = LE;
 698       if_true_label = if_false_label;
 699       if_false_label = drop_through_label;
 700       drop_through_if_true = false;
 701       drop_through_if_false = true;
 702     }
 703
 704   /* Compare a word at a time, high order first.  */
 705   for (i = 0; i < nwords; i++)
 706     {
 707       rtx op0_word, op1_word;
 708
 709       if (WORDS_BIG_ENDIAN)
 710         {
 711           op0_word = operand_subword_force (op0, i, mode);
 712           op1_word = operand_subword_force (op1, i, mode);
 713         }
 714       else
 715         {
 716           op0_word = operand_subword_force (op0, nwords - 1 - i, mode);
 717           op1_word = operand_subword_force (op1, nwords - 1 - i, mode);
 718         }
 719
 720       /* All but high-order word must be compared as unsigned.  */
 721       do_compare_rtx_and_jump (op0_word, op1_word, code, (unsignedp || i > 0),
 722                                word_mode, NULL_RTX, NULL, if_true_label,
 723                                prob);
 724
 725       /* Emit only one comparison for 0.  Do not emit the last cond jump.  */
 726       if (op0 == const0_rtx || i == nwords - 1)
 727         break;
 728
 729       /* Consider lower words only if these are equal.  */
 730       do_compare_rtx_and_jump (op0_word, op1_word, NE, unsignedp, word_mode,
 731                                NULL_RTX, NULL, if_false_label, inv (prob));
 732     }
 733
 734   if (!drop_through_if_false)
 735     emit_jump (if_false_label);
 736   if (drop_through_label)
 737     emit_label (drop_through_label);
 738 }
 739
 740 /* Given a comparison expression EXP for values too wide to be compared
 741    with one insn, test the comparison and jump to the appropriate label.
 742    The code of EXP is ignored; we always test GT if SWAP is 0,
 743    and LT if SWAP is 1.  */
 744
 745 static void
 746 do_jump_by_parts_greater (tree treeop0, tree treeop1, int swap,
 747                           rtx_code_label *if_false_label,
 748                           rtx_code_label *if_true_label, int prob)
 749 {
 750   rtx op0 = expand_normal (swap ? treeop1 : treeop0);
 751   rtx op1 = expand_normal (swap ? treeop0 : treeop1);
 752   machine_mode mode = TYPE_MODE (TREE_TYPE (treeop0));
 753   int unsignedp = TYPE_UNSIGNED (TREE_TYPE (treeop0));
 754
 755   do_jump_by_parts_greater_rtx (mode, unsignedp, op0, op1, if_false_label,
 756                                 if_true_label, prob);
 757 }
 758 \f
 759 /* Jump according to whether OP0 is 0.  We assume that OP0 has an integer
 760    mode, MODE, that is too wide for the available compare insns.  Either
 761    Either (but not both) of IF_TRUE_LABEL and IF_FALSE_LABEL may be NULL
 762    to indicate drop through.  */
 763
 764 static void
 765 do_jump_by_parts_zero_rtx (machine_mode mode, rtx op0,
 766                            rtx_code_label *if_false_label,
 767                            rtx_code_label *if_true_label, int prob)
 768 {
 769   int nwords = GET_MODE_SIZE (mode) / UNITS_PER_WORD;
 770   rtx part;
 771   int i;
 772   rtx_code_label *drop_through_label = NULL;
 773
 774   /* The fastest way of doing this comparison on almost any machine is to
 775      "or" all the words and compare the result.  If all have to be loaded
 776      from memory and this is a very wide item, it's possible this may
 777      be slower, but that's highly unlikely.  */
 778
 779   part = gen_reg_rtx (word_mode);
 780   emit_move_insn (part, operand_subword_force (op0, 0, mode));
 781   for (i = 1; i < nwords && part != 0; i++)
 782     part = expand_binop (word_mode, ior_optab, part,
 783                          operand_subword_force (op0, i, mode),
 784                          part, 1, OPTAB_WIDEN);
 785
 786   if (part != 0)
 787     {
 788       do_compare_rtx_and_jump (part, const0_rtx, EQ, 1, word_mode,
 789                                NULL_RTX, if_false_label, if_true_label, prob);
 790       return;
 791     }
 792
 793   /* If we couldn't do the "or" simply, do this with a series of compares.  */
 794   if (! if_false_label)
 795     if_false_label = drop_through_label = gen_label_rtx ();
 796
 797   for (i = 0; i < nwords; i++)
 798     do_compare_rtx_and_jump (operand_subword_force (op0, i, mode),
 799                              const0_rtx, EQ, 1, word_mode, NULL_RTX,
 800                              if_false_label, NULL, prob);
 801
 802   if (if_true_label)
 803     emit_jump (if_true_label);
 804
 805   if (drop_through_label)
 806     emit_label (drop_through_label);
 807 }
 808
 809 /* Test for the equality of two RTX expressions OP0 and OP1 in mode MODE,
 810    where MODE is an integer mode too wide to be compared with one insn.
 811    Either (but not both) of IF_TRUE_LABEL and IF_FALSE_LABEL may be NULL_RTX
 812    to indicate drop through.  */
 813
 814 static void
 815 do_jump_by_parts_equality_rtx (machine_mode mode, rtx op0, rtx op1,
 816                                rtx_code_label *if_false_label,
 817                                rtx_code_label *if_true_label, int prob)
 818 {
 819   int nwords = (GET_MODE_SIZE (mode) / UNITS_PER_WORD);
 820   rtx_code_label *drop_through_label = NULL;
 821   int i;
 822
 823   if (op1 == const0_rtx)
 824     {
 825       do_jump_by_parts_zero_rtx (mode, op0, if_false_label, if_true_label,
 826                                  prob);
 827       return;
 828     }
 829   else if (op0 == const0_rtx)
 830     {
 831       do_jump_by_parts_zero_rtx (mode, op1, if_false_label, if_true_label,
 832                                  prob);
 833       return;
 834     }
 835
 836   if (! if_false_label)
 837     drop_through_label = if_false_label = gen_label_rtx ();
 838
 839   for (i = 0; i < nwords; i++)
 840     do_compare_rtx_and_jump (operand_subword_force (op0, i, mode),
 841                              operand_subword_force (op1, i, mode),
 842                              EQ, 0, word_mode, NULL_RTX,
 843                              if_false_label, NULL, prob);
 844
 845   if (if_true_label)
 846     emit_jump (if_true_label);
 847   if (drop_through_label)
 848     emit_label (drop_through_label);
 849 }
 850
 851 /* Given an EQ_EXPR expression EXP for values too wide to be compared
 852    with one insn, test the comparison and jump to the appropriate label.  */
 853
 854 static void
 855 do_jump_by_parts_equality (tree treeop0, tree treeop1,
 856                            rtx_code_label *if_false_label,
 857                            rtx_code_label *if_true_label, int prob)
 858 {
 859   rtx op0 = expand_normal (treeop0);
 860   rtx op1 = expand_normal (treeop1);
 861   machine_mode mode = TYPE_MODE (TREE_TYPE (treeop0));
 862   do_jump_by_parts_equality_rtx (mode, op0, op1, if_false_label,
 863                                  if_true_label, prob);
 864 }
 865 \f
 866 /* Split a comparison into two others, the second of which has the other
 867    "orderedness".  The first is always ORDERED or UNORDERED if MODE
 868    does not honor NaNs (which means that it can be skipped in that case;
 869    see do_compare_rtx_and_jump).
 870
 871    The two conditions are written in *CODE1 and *CODE2.  Return true if
 872    the conditions must be ANDed, false if they must be ORed.  */
 873
 874 bool
 875 split_comparison (enum rtx_code code, machine_mode mode,
 876                   enum rtx_code *code1, enum rtx_code *code2)
 877 {
 878   switch (code)
 879     {
 880     case LT:
 881       *code1 = ORDERED;
 882       *code2 = UNLT;
 883       return true;
 884     case LE:
 885       *code1 = ORDERED;
 886       *code2 = UNLE;
 887       return true;
 888     case GT:
 889       *code1 = ORDERED;
 890       *code2 = UNGT;
 891       return true;
 892     case GE:
 893       *code1 = ORDERED;
 894       *code2 = UNGE;
 895       return true;
 896     case EQ:
 897       *code1 = ORDERED;
 898       *code2 = UNEQ;
 899       return true;
 900     case NE:
 901       *code1 = UNORDERED;
 902       *code2 = LTGT;
 903       return false;
 904     case UNLT:
 905       *code1 = UNORDERED;
 906       *code2 = LT;
 907       return false;
 908     case UNLE:
 909       *code1 = UNORDERED;
 910       *code2 = LE;
 911       return false;
 912     case UNGT:
 913       *code1 = UNORDERED;
 914       *code2 = GT;
 915       return false;
 916     case UNGE:
 917       *code1 = UNORDERED;
 918       *code2 = GE;
 919       return false;
 920     case UNEQ:
 921       *code1 = UNORDERED;
 922       *code2 = EQ;
 923       return false;
 924     case LTGT:
 925       /* Do not turn a trapping comparison into a non-trapping one.  */
 926       if (HONOR_SNANS (mode))
 927         {
 928           *code1 = LT;
 929           *code2 = GT;
 930           return false;
 931         }
 932       else
 933         {
 934           *code1 = ORDERED;
 935           *code2 = NE;
 936           return true;
 937         }
 938     default:
 939       gcc_unreachable ();
 940     }
 941 }
 942
 943
 944 /* Like do_compare_and_jump but expects the values to compare as two rtx's.
 945    The decision as to signed or unsigned comparison must be made by the caller.
 946
 947    If MODE is BLKmode, SIZE is an RTX giving the size of the objects being
 948    compared.  */
 949
 950 void
 951 do_compare_rtx_and_jump (rtx op0, rtx op1, enum rtx_code code, int unsignedp,
 952                          machine_mode mode, rtx size,
 953                          rtx_code_label *if_false_label,
 954                          rtx_code_label *if_true_label, int prob)
 955 {
 956   rtx tem;
 957   rtx_code_label *dummy_label = NULL;
 958
 959   /* Reverse the comparison if that is safe and we want to jump if it is
 960      false.  Also convert to the reverse comparison if the target can
 961      implement it.  */
 962   if ((! if_true_label
 963        || ! can_compare_p (code, mode, ccp_jump))
 964       && (! FLOAT_MODE_P (mode)
 965           || code == ORDERED || code == UNORDERED
 966           || (! HONOR_NANS (mode) && (code == LTGT || code == UNEQ))
 967           || (! HONOR_SNANS (mode) && (code == EQ || code == NE))))
 968     {
 969       enum rtx_code rcode;
 970       if (FLOAT_MODE_P (mode))
 971         rcode = reverse_condition_maybe_unordered (code);
 972       else
 973         rcode = reverse_condition (code);
 974
 975       /* Canonicalize to UNORDERED for the libcall.  */
 976       if (can_compare_p (rcode, mode, ccp_jump)
 977           || (code == ORDERED && ! can_compare_p (ORDERED, mode, ccp_jump)))
 978         {
 979           std::swap (if_true_label, if_false_label);
 980           code = rcode;
 981           prob = inv (prob);
 982         }
 983     }
 984
 985   /* If one operand is constant, make it the second one.  Only do this
 986      if the other operand is not constant as well.  */
 987
 988   if (swap_commutative_operands_p (op0, op1))
 989     {
 990       std::swap (op0, op1);
 991       code = swap_condition (code);
 992     }
 993
 994   do_pending_stack_adjust ();
 995
 996   code = unsignedp ? unsigned_condition (code) : code;
 997   if (0 != (tem = simplify_relational_operation (code, mode, VOIDmode,
 998                                                  op0, op1)))
 999     {
1000       if (CONSTANT_P (tem))
1001         {
1002           rtx_code_label *label = (tem == const0_rtx
1003                                    || tem == CONST0_RTX (mode))
1004                                         ? if_false_label : if_true_label;
1005           if (label)
1006             emit_jump (label);
1007           return;
1008         }
1009
1010       code = GET_CODE (tem);
1011       mode = GET_MODE (tem);
1012       op0 = XEXP (tem, 0);
1013       op1 = XEXP (tem, 1);
1014       unsignedp = (code == GTU || code == LTU || code == GEU || code == LEU);
1015     }
1016
1017   if (! if_true_label)
1018     dummy_label = if_true_label = gen_label_rtx ();
1019
1020   if (GET_MODE_CLASS (mode) == MODE_INT
1021       && ! can_compare_p (code, mode, ccp_jump))
1022     {
1023       switch (code)
1024         {
1025         case LTU:
1026           do_jump_by_parts_greater_rtx (mode, 1, op1, op0,
1027                                         if_false_label, if_true_label, prob);
1028           break;
1029
1030         case LEU:
1031           do_jump_by_parts_greater_rtx (mode, 1, op0, op1,
1032                                         if_true_label, if_false_label,
1033                                         inv (prob));
1034           break;
1035
1036         case GTU:
1037           do_jump_by_parts_greater_rtx (mode, 1, op0, op1,
1038                                         if_false_label, if_true_label, prob);
1039           break;
1040
1041         case GEU:
1042           do_jump_by_parts_greater_rtx (mode, 1, op1, op0,
1043                                         if_true_label, if_false_label,
1044                                         inv (prob));
1045           break;
1046
1047         case LT:
1048           do_jump_by_parts_greater_rtx (mode, 0, op1, op0,
1049                                         if_false_label, if_true_label, prob);
1050           break;
1051
1052         case LE:
1053           do_jump_by_parts_greater_rtx (mode, 0, op0, op1,
1054                                         if_true_label, if_false_label,
1055                                         inv (prob));
1056           break;
1057
1058         case GT:
1059           do_jump_by_parts_greater_rtx (mode, 0, op0, op1,
1060                                         if_false_label, if_true_label, prob);
1061           break;
1062
1063         case GE:
1064           do_jump_by_parts_greater_rtx (mode, 0, op1, op0,
1065                                         if_true_label, if_false_label,
1066                                         inv (prob));
1067           break;
1068
1069         case EQ:
1070           do_jump_by_parts_equality_rtx (mode, op0, op1, if_false_label,
1071                                          if_true_label, prob);
1072           break;
1073
1074         case NE:
1075           do_jump_by_parts_equality_rtx (mode, op0, op1, if_true_label,
1076                                          if_false_label, inv (prob));
1077           break;
1078
1079         default:
1080           gcc_unreachable ();
1081         }
1082     }
1083   else
1084     {
1085       if (SCALAR_FLOAT_MODE_P (mode)
1086           && ! can_compare_p (code, mode, ccp_jump)
1087           && can_compare_p (swap_condition (code), mode, ccp_jump))
1088         {
1089           code = swap_condition (code);
1090           std::swap (op0, op1);
1091         }
1092       else if (SCALAR_FLOAT_MODE_P (mode)
1093                && ! can_compare_p (code, mode, ccp_jump)
1094                /* Never split ORDERED and UNORDERED.
1095                   These must be implemented.  */
1096                && (code != ORDERED && code != UNORDERED)
1097                /* Split a floating-point comparison if
1098                   we can jump on other conditions...  */
1099                && (have_insn_for (COMPARE, mode)
1100                    /* ... or if there is no libcall for it.  */
1101                    || code_to_optab (code) == unknown_optab))
1102         {
1103           enum rtx_code first_code;
1104           bool and_them = split_comparison (code, mode, &first_code, &code);
1105
1106           /* If there are no NaNs, the first comparison should always fall
1107              through.  */
1108           if (!HONOR_NANS (mode))
1109             gcc_assert (first_code == (and_them ? ORDERED : UNORDERED));
1110
1111           else
1112             {
1113               int first_prob = prob;
1114               if (first_code == UNORDERED)
1115                 first_prob = REG_BR_PROB_BASE / 100;
1116               else if (first_code == ORDERED)
1117                 first_prob = REG_BR_PROB_BASE - REG_BR_PROB_BASE / 100;
1118               if (and_them)
1119                 {
1120                   rtx_code_label *dest_label;
1121                   /* If we only jump if true, just bypass the second jump.  */
1122                   if (! if_false_label)
1123                     {
1124                       if (! dummy_label)
1125                         dummy_label = gen_label_rtx ();
1126                       dest_label = dummy_label;
1127                     }
1128                   else
1129                     dest_label = if_false_label;
1130                   do_compare_rtx_and_jump (op0, op1, first_code, unsignedp, mode,
1131                                            size, dest_label, NULL, first_prob);
1132                 }
1133               else
1134                 do_compare_rtx_and_jump (op0, op1, first_code, unsignedp, mode,
1135                                          size, NULL, if_true_label, first_prob);
1136             }
1137         }
1138
1139       emit_cmp_and_jump_insns (op0, op1, code, size, mode, unsignedp,
1140                                if_true_label, prob);
1141     }
1142
1143   if (if_false_label)
1144     emit_jump (if_false_label);
1145   if (dummy_label)
1146     emit_label (dummy_label);
1147 }
1148
1149 /* Generate code for a comparison expression EXP (including code to compute
1150    the values to be compared) and a conditional jump to IF_FALSE_LABEL and/or
1151    IF_TRUE_LABEL.  One of the labels can be NULL_RTX, in which case the
1152    generated code will drop through.
1153    SIGNED_CODE should be the rtx operation for this comparison for
1154    signed data; UNSIGNED_CODE, likewise for use if data is unsigned.
1155
1156    We force a stack adjustment unless there are currently
1157    things pushed on the stack that aren't yet used.  */
1158
1159 static void
1160 do_compare_and_jump (tree treeop0, tree treeop1, enum rtx_code signed_code,
1161                      enum rtx_code unsigned_code,
1162                      rtx_code_label *if_false_label,
1163                      rtx_code_label *if_true_label, int prob)
1164 {
1165   rtx op0, op1;
1166   tree type;
1167   machine_mode mode;
1168   int unsignedp;
1169   enum rtx_code code;
1170
1171   /* Don't crash if the comparison was erroneous.  */
1172   op0 = expand_normal (treeop0);
1173   if (TREE_CODE (treeop0) == ERROR_MARK)
1174     return;
1175
1176   op1 = expand_normal (treeop1);
1177   if (TREE_CODE (treeop1) == ERROR_MARK)
1178     return;
1179
1180   type = TREE_TYPE (treeop0);
1181   mode = TYPE_MODE (type);
1182   if (TREE_CODE (treeop0) == INTEGER_CST
1183       && (TREE_CODE (treeop1) != INTEGER_CST
1184           || (GET_MODE_BITSIZE (mode)
1185               > GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (treeop1))))))
1186     {
1187       /* op0 might have been replaced by promoted constant, in which
1188          case the type of second argument should be used.  */
1189       type = TREE_TYPE (treeop1);
1190       mode = TYPE_MODE (type);
1191     }
1192   unsignedp = TYPE_UNSIGNED (type);
1193   code = unsignedp ? unsigned_code : signed_code;
1194
1195   /* If function pointers need to be "canonicalized" before they can
1196      be reliably compared, then canonicalize them.
1197      Only do this if *both* sides of the comparison are function pointers.
1198      If one side isn't, we want a noncanonicalized comparison.  See PR
1199      middle-end/17564.  */
1200   if (targetm.have_canonicalize_funcptr_for_compare ()
1201       && POINTER_TYPE_P (TREE_TYPE (treeop0))
1202       && POINTER_TYPE_P (TREE_TYPE (treeop1))
1203       && FUNC_OR_METHOD_TYPE_P (TREE_TYPE (TREE_TYPE (treeop0)))
1204       && FUNC_OR_METHOD_TYPE_P (TREE_TYPE (TREE_TYPE (treeop1))))
1205     {
1206       rtx new_op0 = gen_reg_rtx (mode);
1207       rtx new_op1 = gen_reg_rtx (mode);
1208
1209       emit_insn (targetm.gen_canonicalize_funcptr_for_compare (new_op0, op0));
1210       op0 = new_op0;
1211
1212       emit_insn (targetm.gen_canonicalize_funcptr_for_compare (new_op1, op1));
1213       op1 = new_op1;
1214     }
1215
1216   do_compare_rtx_and_jump (op0, op1, code, unsignedp, mode,
1217                            ((mode == BLKmode)
1218                             ? expr_size (treeop0) : NULL_RTX),
1219                            if_false_label, if_true_label, prob);
1220 }
1221
1222 #include "gt-dojump.h"