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