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       /* FALLTHRU */
 465     case CONVERT_EXPR:
 466       /* If we are narrowing the operand, we have to do the compare in the
 467          narrower mode.  */
 468       if ((TYPE_PRECISION (TREE_TYPE (exp))
 469            < TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (exp, 0)))))
 470         goto normal;
 471       /* FALLTHRU */
 472     case NON_LVALUE_EXPR:
 473     case ABS_EXPR:
 474     case NEGATE_EXPR:
 475     case LROTATE_EXPR:
 476     case RROTATE_EXPR:
 477       /* These cannot change zero->nonzero or vice versa.  */
 478       do_jump (TREE_OPERAND (exp, 0), if_false_label, if_true_label, prob);
 479       break;
 480
 481     case TRUTH_NOT_EXPR:
 482       do_jump (TREE_OPERAND (exp, 0), if_true_label, if_false_label,
 483                inv (prob));
 484       break;
 485
 486     case COND_EXPR:
 487       {
 488         rtx_code_label *label1 = gen_label_rtx ();
 489         if (!if_true_label || !if_false_label)
 490           {
 491             drop_through_label = gen_label_rtx ();
 492             if (!if_true_label)
 493               if_true_label = drop_through_label;
 494             if (!if_false_label)
 495               if_false_label = drop_through_label;
 496           }
 497
 498         do_pending_stack_adjust ();
 499         do_jump (TREE_OPERAND (exp, 0), label1, NULL, -1);
 500         do_jump (TREE_OPERAND (exp, 1), if_false_label, if_true_label, prob);
 501         emit_label (label1);
 502         do_jump (TREE_OPERAND (exp, 2), if_false_label, if_true_label, prob);
 503         break;
 504       }
 505
 506     case COMPOUND_EXPR:
 507       /* Lowered by gimplify.c.  */
 508       gcc_unreachable ();
 509
 510     case MINUS_EXPR:
 511       /* Nonzero iff operands of minus differ.  */
 512       code = NE_EXPR;
 513
 514       /* FALLTHRU */
 515     case EQ_EXPR:
 516     case NE_EXPR:
 517     case LT_EXPR:
 518     case LE_EXPR:
 519     case GT_EXPR:
 520     case GE_EXPR:
 521     case ORDERED_EXPR:
 522     case UNORDERED_EXPR:
 523     case UNLT_EXPR:
 524     case UNLE_EXPR:
 525     case UNGT_EXPR:
 526     case UNGE_EXPR:
 527     case UNEQ_EXPR:
 528     case LTGT_EXPR:
 529     case TRUTH_ANDIF_EXPR:
 530     case TRUTH_ORIF_EXPR:
 531     other_code:
 532       do_jump_1 (code, TREE_OPERAND (exp, 0), TREE_OPERAND (exp, 1),
 533                  if_false_label, if_true_label, prob);
 534       break;
 535
 536     case BIT_AND_EXPR:
 537       /* fold_single_bit_test() converts (X & (1 << C)) into (X >> C) & 1.
 538          See if the former is preferred for jump tests and restore it
 539          if so.  */
 540       if (integer_onep (TREE_OPERAND (exp, 1)))
 541         {
 542           tree exp0 = TREE_OPERAND (exp, 0);
 543           rtx_code_label *set_label, *clr_label;
 544           int setclr_prob = prob;
 545
 546           /* Strip narrowing integral type conversions.  */
 547           while (CONVERT_EXPR_P (exp0)
 548                  && TREE_OPERAND (exp0, 0) != error_mark_node
 549                  && TYPE_PRECISION (TREE_TYPE (exp0))
 550                     <= TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (exp0, 0))))
 551             exp0 = TREE_OPERAND (exp0, 0);
 552
 553           /* "exp0 ^ 1" inverts the sense of the single bit test.  */
 554           if (TREE_CODE (exp0) == BIT_XOR_EXPR
 555               && integer_onep (TREE_OPERAND (exp0, 1)))
 556             {
 557               exp0 = TREE_OPERAND (exp0, 0);
 558               clr_label = if_true_label;
 559               set_label = if_false_label;
 560               setclr_prob = inv (prob);
 561             }
 562           else
 563             {
 564               clr_label = if_false_label;
 565               set_label = if_true_label;
 566             }
 567
 568           if (TREE_CODE (exp0) == RSHIFT_EXPR)
 569             {
 570               tree arg = TREE_OPERAND (exp0, 0);
 571               tree shift = TREE_OPERAND (exp0, 1);
 572               tree argtype = TREE_TYPE (arg);
 573               if (TREE_CODE (shift) == INTEGER_CST
 574                   && compare_tree_int (shift, 0) >= 0
 575                   && compare_tree_int (shift, HOST_BITS_PER_WIDE_INT) < 0
 576                   && prefer_and_bit_test (TYPE_MODE (argtype),
 577                                           TREE_INT_CST_LOW (shift)))
 578                 {
 579                   unsigned HOST_WIDE_INT mask
 580                     = HOST_WIDE_INT_1U << TREE_INT_CST_LOW (shift);
 581                   do_jump (build2 (BIT_AND_EXPR, argtype, arg,
 582                                    build_int_cstu (argtype, mask)),
 583                            clr_label, set_label, setclr_prob);
 584                   break;
 585                 }
 586             }
 587         }
 588
 589       /* If we are AND'ing with a small constant, do this comparison in the
 590          smallest type that fits.  If the machine doesn't have comparisons
 591          that small, it will be converted back to the wider comparison.
 592          This helps if we are testing the sign bit of a narrower object.
 593          combine can't do this for us because it can't know whether a
 594          ZERO_EXTRACT or a compare in a smaller mode exists, but we do.  */
 595
 596       if (! SLOW_BYTE_ACCESS
 597           && TREE_CODE (TREE_OPERAND (exp, 1)) == INTEGER_CST
 598           && TYPE_PRECISION (TREE_TYPE (exp)) <= HOST_BITS_PER_WIDE_INT
 599           && (i = tree_floor_log2 (TREE_OPERAND (exp, 1))) >= 0
 600           && (mode = mode_for_size (i + 1, MODE_INT, 0)) != BLKmode
 601           && (type = lang_hooks.types.type_for_mode (mode, 1)) != 0
 602           && TYPE_PRECISION (type) < TYPE_PRECISION (TREE_TYPE (exp))
 603           && have_insn_for (COMPARE, TYPE_MODE (type)))
 604         {
 605           do_jump (fold_convert (type, exp), if_false_label, if_true_label,
 606                    prob);
 607           break;
 608         }
 609
 610       if (TYPE_PRECISION (TREE_TYPE (exp)) > 1
 611           || TREE_CODE (TREE_OPERAND (exp, 1)) == INTEGER_CST)
 612         goto normal;
 613
 614       /* Boolean comparisons can be compiled as TRUTH_AND_EXPR.  */
 615       /* FALLTHRU */
 616
 617     case TRUTH_AND_EXPR:
 618       /* High branch cost, expand as the bitwise AND of the conditions.
 619          Do the same if the RHS has side effects, because we're effectively
 620          turning a TRUTH_AND_EXPR into a TRUTH_ANDIF_EXPR.  */
 621       if (BRANCH_COST (optimize_insn_for_speed_p (),
 622                        false) >= 4
 623           || TREE_SIDE_EFFECTS (TREE_OPERAND (exp, 1)))
 624         goto normal;
 625       code = TRUTH_ANDIF_EXPR;
 626       goto other_code;
 627
 628     case BIT_IOR_EXPR:
 629     case TRUTH_OR_EXPR:
 630       /* High branch cost, expand as the bitwise OR of the conditions.
 631          Do the same if the RHS has side effects, because we're effectively
 632          turning a TRUTH_OR_EXPR into a TRUTH_ORIF_EXPR.  */
 633       if (BRANCH_COST (optimize_insn_for_speed_p (), false) >= 4
 634           || TREE_SIDE_EFFECTS (TREE_OPERAND (exp, 1)))
 635         goto normal;
 636       code = TRUTH_ORIF_EXPR;
 637       goto other_code;
 638
 639       /* Fall through and generate the normal code.  */
 640     default:
 641     normal:
 642       temp = expand_normal (exp);
 643       do_pending_stack_adjust ();
 644       /* The RTL optimizers prefer comparisons against pseudos.  */
 645       if (GET_CODE (temp) == SUBREG)
 646         {
 647           /* Compare promoted variables in their promoted mode.  */
 648           if (SUBREG_PROMOTED_VAR_P (temp)
 649               && REG_P (XEXP (temp, 0)))
 650             temp = XEXP (temp, 0);
 651           else
 652             temp = copy_to_reg (temp);
 653         }
 654       do_compare_rtx_and_jump (temp, CONST0_RTX (GET_MODE (temp)),
 655                                NE, TYPE_UNSIGNED (TREE_TYPE (exp)),
 656                                GET_MODE (temp), NULL_RTX,
 657                                if_false_label, if_true_label, prob);
 658     }
 659
 660   if (drop_through_label)
 661     {
 662       do_pending_stack_adjust ();
 663       emit_label (drop_through_label);
 664     }
 665 }
 666 \f
 667 /* Compare OP0 with OP1, word at a time, in mode MODE.
 668    UNSIGNEDP says to do unsigned comparison.
 669    Jump to IF_TRUE_LABEL if OP0 is greater, IF_FALSE_LABEL otherwise.  */
 670
 671 static void
 672 do_jump_by_parts_greater_rtx (machine_mode mode, int unsignedp, rtx op0,
 673                               rtx op1, rtx_code_label *if_false_label,
 674                               rtx_code_label *if_true_label,
 675                               int prob)
 676 {
 677   int nwords = (GET_MODE_SIZE (mode) / UNITS_PER_WORD);
 678   rtx_code_label *drop_through_label = 0;
 679   bool drop_through_if_true = false, drop_through_if_false = false;
 680   enum rtx_code code = GT;
 681   int i;
 682
 683   if (! if_true_label || ! if_false_label)
 684     drop_through_label = gen_label_rtx ();
 685   if (! if_true_label)
 686     {
 687       if_true_label = drop_through_label;
 688       drop_through_if_true = true;
 689     }
 690   if (! if_false_label)
 691     {
 692       if_false_label = drop_through_label;
 693       drop_through_if_false = true;
 694     }
 695
 696   /* Deal with the special case 0 > x: only one comparison is necessary and
 697      we reverse it to avoid jumping to the drop-through label.  */
 698   if (op0 == const0_rtx && drop_through_if_true && !drop_through_if_false)
 699     {
 700       code = LE;
 701       if_true_label = if_false_label;
 702       if_false_label = drop_through_label;
 703       drop_through_if_true = false;
 704       drop_through_if_false = true;
 705     }
 706
 707   /* Compare a word at a time, high order first.  */
 708   for (i = 0; i < nwords; i++)
 709     {
 710       rtx op0_word, op1_word;
 711
 712       if (WORDS_BIG_ENDIAN)
 713         {
 714           op0_word = operand_subword_force (op0, i, mode);
 715           op1_word = operand_subword_force (op1, i, mode);
 716         }
 717       else
 718         {
 719           op0_word = operand_subword_force (op0, nwords - 1 - i, mode);
 720           op1_word = operand_subword_force (op1, nwords - 1 - i, mode);
 721         }
 722
 723       /* All but high-order word must be compared as unsigned.  */
 724       do_compare_rtx_and_jump (op0_word, op1_word, code, (unsignedp || i > 0),
 725                                word_mode, NULL_RTX, NULL, if_true_label,
 726                                prob);
 727
 728       /* Emit only one comparison for 0.  Do not emit the last cond jump.  */
 729       if (op0 == const0_rtx || i == nwords - 1)
 730         break;
 731
 732       /* Consider lower words only if these are equal.  */
 733       do_compare_rtx_and_jump (op0_word, op1_word, NE, unsignedp, word_mode,
 734                                NULL_RTX, NULL, if_false_label, inv (prob));
 735     }
 736
 737   if (!drop_through_if_false)
 738     emit_jump (if_false_label);
 739   if (drop_through_label)
 740     emit_label (drop_through_label);
 741 }
 742
 743 /* Given a comparison expression EXP for values too wide to be compared
 744    with one insn, test the comparison and jump to the appropriate label.
 745    The code of EXP is ignored; we always test GT if SWAP is 0,
 746    and LT if SWAP is 1.  */
 747
 748 static void
 749 do_jump_by_parts_greater (tree treeop0, tree treeop1, int swap,
 750                           rtx_code_label *if_false_label,
 751                           rtx_code_label *if_true_label, int prob)
 752 {
 753   rtx op0 = expand_normal (swap ? treeop1 : treeop0);
 754   rtx op1 = expand_normal (swap ? treeop0 : treeop1);
 755   machine_mode mode = TYPE_MODE (TREE_TYPE (treeop0));
 756   int unsignedp = TYPE_UNSIGNED (TREE_TYPE (treeop0));
 757
 758   do_jump_by_parts_greater_rtx (mode, unsignedp, op0, op1, if_false_label,
 759                                 if_true_label, prob);
 760 }
 761 \f
 762 /* Jump according to whether OP0 is 0.  We assume that OP0 has an integer
 763    mode, MODE, that is too wide for the available compare insns.  Either
 764    Either (but not both) of IF_TRUE_LABEL and IF_FALSE_LABEL may be NULL
 765    to indicate drop through.  */
 766
 767 static void
 768 do_jump_by_parts_zero_rtx (machine_mode mode, rtx op0,
 769                            rtx_code_label *if_false_label,
 770                            rtx_code_label *if_true_label, int prob)
 771 {
 772   int nwords = GET_MODE_SIZE (mode) / UNITS_PER_WORD;
 773   rtx part;
 774   int i;
 775   rtx_code_label *drop_through_label = NULL;
 776
 777   /* The fastest way of doing this comparison on almost any machine is to
 778      "or" all the words and compare the result.  If all have to be loaded
 779      from memory and this is a very wide item, it's possible this may
 780      be slower, but that's highly unlikely.  */
 781
 782   part = gen_reg_rtx (word_mode);
 783   emit_move_insn (part, operand_subword_force (op0, 0, mode));
 784   for (i = 1; i < nwords && part != 0; i++)
 785     part = expand_binop (word_mode, ior_optab, part,
 786                          operand_subword_force (op0, i, mode),
 787                          part, 1, OPTAB_WIDEN);
 788
 789   if (part != 0)
 790     {
 791       do_compare_rtx_and_jump (part, const0_rtx, EQ, 1, word_mode,
 792                                NULL_RTX, if_false_label, if_true_label, prob);
 793       return;
 794     }
 795
 796   /* If we couldn't do the "or" simply, do this with a series of compares.  */
 797   if (! if_false_label)
 798     if_false_label = drop_through_label = gen_label_rtx ();
 799
 800   for (i = 0; i < nwords; i++)
 801     do_compare_rtx_and_jump (operand_subword_force (op0, i, mode),
 802                              const0_rtx, EQ, 1, word_mode, NULL_RTX,
 803                              if_false_label, NULL, prob);
 804
 805   if (if_true_label)
 806     emit_jump (if_true_label);
 807
 808   if (drop_through_label)
 809     emit_label (drop_through_label);
 810 }
 811
 812 /* Test for the equality of two RTX expressions OP0 and OP1 in mode MODE,
 813    where MODE is an integer mode too wide to be compared with one insn.
 814    Either (but not both) of IF_TRUE_LABEL and IF_FALSE_LABEL may be NULL_RTX
 815    to indicate drop through.  */
 816
 817 static void
 818 do_jump_by_parts_equality_rtx (machine_mode mode, rtx op0, rtx op1,
 819                                rtx_code_label *if_false_label,
 820                                rtx_code_label *if_true_label, int prob)
 821 {
 822   int nwords = (GET_MODE_SIZE (mode) / UNITS_PER_WORD);
 823   rtx_code_label *drop_through_label = NULL;
 824   int i;
 825
 826   if (op1 == const0_rtx)
 827     {
 828       do_jump_by_parts_zero_rtx (mode, op0, if_false_label, if_true_label,
 829                                  prob);
 830       return;
 831     }
 832   else if (op0 == const0_rtx)
 833     {
 834       do_jump_by_parts_zero_rtx (mode, op1, if_false_label, if_true_label,
 835                                  prob);
 836       return;
 837     }
 838
 839   if (! if_false_label)
 840     drop_through_label = if_false_label = gen_label_rtx ();
 841
 842   for (i = 0; i < nwords; i++)
 843     do_compare_rtx_and_jump (operand_subword_force (op0, i, mode),
 844                              operand_subword_force (op1, i, mode),
 845                              EQ, 0, word_mode, NULL_RTX,
 846                              if_false_label, NULL, prob);
 847
 848   if (if_true_label)
 849     emit_jump (if_true_label);
 850   if (drop_through_label)
 851     emit_label (drop_through_label);
 852 }
 853
 854 /* Given an EQ_EXPR expression EXP for values too wide to be compared
 855    with one insn, test the comparison and jump to the appropriate label.  */
 856
 857 static void
 858 do_jump_by_parts_equality (tree treeop0, tree treeop1,
 859                            rtx_code_label *if_false_label,
 860                            rtx_code_label *if_true_label, int prob)
 861 {
 862   rtx op0 = expand_normal (treeop0);
 863   rtx op1 = expand_normal (treeop1);
 864   machine_mode mode = TYPE_MODE (TREE_TYPE (treeop0));
 865   do_jump_by_parts_equality_rtx (mode, op0, op1, if_false_label,
 866                                  if_true_label, prob);
 867 }
 868 \f
 869 /* Split a comparison into two others, the second of which has the other
 870    "orderedness".  The first is always ORDERED or UNORDERED if MODE
 871    does not honor NaNs (which means that it can be skipped in that case;
 872    see do_compare_rtx_and_jump).
 873
 874    The two conditions are written in *CODE1 and *CODE2.  Return true if
 875    the conditions must be ANDed, false if they must be ORed.  */
 876
 877 bool
 878 split_comparison (enum rtx_code code, machine_mode mode,
 879                   enum rtx_code *code1, enum rtx_code *code2)
 880 {
 881   switch (code)
 882     {
 883     case LT:
 884       *code1 = ORDERED;
 885       *code2 = UNLT;
 886       return true;
 887     case LE:
 888       *code1 = ORDERED;
 889       *code2 = UNLE;
 890       return true;
 891     case GT:
 892       *code1 = ORDERED;
 893       *code2 = UNGT;
 894       return true;
 895     case GE:
 896       *code1 = ORDERED;
 897       *code2 = UNGE;
 898       return true;
 899     case EQ:
 900       *code1 = ORDERED;
 901       *code2 = UNEQ;
 902       return true;
 903     case NE:
 904       *code1 = UNORDERED;
 905       *code2 = LTGT;
 906       return false;
 907     case UNLT:
 908       *code1 = UNORDERED;
 909       *code2 = LT;
 910       return false;
 911     case UNLE:
 912       *code1 = UNORDERED;
 913       *code2 = LE;
 914       return false;
 915     case UNGT:
 916       *code1 = UNORDERED;
 917       *code2 = GT;
 918       return false;
 919     case UNGE:
 920       *code1 = UNORDERED;
 921       *code2 = GE;
 922       return false;
 923     case UNEQ:
 924       *code1 = UNORDERED;
 925       *code2 = EQ;
 926       return false;
 927     case LTGT:
 928       /* Do not turn a trapping comparison into a non-trapping one.  */
 929       if (HONOR_SNANS (mode))
 930         {
 931           *code1 = LT;
 932           *code2 = GT;
 933           return false;
 934         }
 935       else
 936         {
 937           *code1 = ORDERED;
 938           *code2 = NE;
 939           return true;
 940         }
 941     default:
 942       gcc_unreachable ();
 943     }
 944 }
 945
 946
 947 /* Like do_compare_and_jump but expects the values to compare as two rtx's.
 948    The decision as to signed or unsigned comparison must be made by the caller.
 949
 950    If MODE is BLKmode, SIZE is an RTX giving the size of the objects being
 951    compared.  */
 952
 953 void
 954 do_compare_rtx_and_jump (rtx op0, rtx op1, enum rtx_code code, int unsignedp,
 955                          machine_mode mode, rtx size,
 956                          rtx_code_label *if_false_label,
 957                          rtx_code_label *if_true_label, int prob)
 958 {
 959   rtx tem;
 960   rtx_code_label *dummy_label = NULL;
 961
 962   /* Reverse the comparison if that is safe and we want to jump if it is
 963      false.  Also convert to the reverse comparison if the target can
 964      implement it.  */
 965   if ((! if_true_label
 966        || ! can_compare_p (code, mode, ccp_jump))
 967       && (! FLOAT_MODE_P (mode)
 968           || code == ORDERED || code == UNORDERED
 969           || (! HONOR_NANS (mode) && (code == LTGT || code == UNEQ))
 970           || (! HONOR_SNANS (mode) && (code == EQ || code == NE))))
 971     {
 972       enum rtx_code rcode;
 973       if (FLOAT_MODE_P (mode))
 974         rcode = reverse_condition_maybe_unordered (code);
 975       else
 976         rcode = reverse_condition (code);
 977
 978       /* Canonicalize to UNORDERED for the libcall.  */
 979       if (can_compare_p (rcode, mode, ccp_jump)
 980           || (code == ORDERED && ! can_compare_p (ORDERED, mode, ccp_jump)))
 981         {
 982           std::swap (if_true_label, if_false_label);
 983           code = rcode;
 984           prob = inv (prob);
 985         }
 986     }
 987
 988   /* If one operand is constant, make it the second one.  Only do this
 989      if the other operand is not constant as well.  */
 990
 991   if (swap_commutative_operands_p (op0, op1))
 992     {
 993       std::swap (op0, op1);
 994       code = swap_condition (code);
 995     }
 996
 997   do_pending_stack_adjust ();
 998
 999   code = unsignedp ? unsigned_condition (code) : code;
1000   if (0 != (tem = simplify_relational_operation (code, mode, VOIDmode,
1001                                                  op0, op1)))
1002     {
1003       if (CONSTANT_P (tem))
1004         {
1005           rtx_code_label *label = (tem == const0_rtx
1006                                    || tem == CONST0_RTX (mode))
1007                                         ? if_false_label : if_true_label;
1008           if (label)
1009             emit_jump (label);
1010           return;
1011         }
1012
1013       code = GET_CODE (tem);
1014       mode = GET_MODE (tem);
1015       op0 = XEXP (tem, 0);
1016       op1 = XEXP (tem, 1);
1017       unsignedp = (code == GTU || code == LTU || code == GEU || code == LEU);
1018     }
1019
1020   if (! if_true_label)
1021     dummy_label = if_true_label = gen_label_rtx ();
1022
1023   if (GET_MODE_CLASS (mode) == MODE_INT
1024       && ! can_compare_p (code, mode, ccp_jump))
1025     {
1026       switch (code)
1027         {
1028         case LTU:
1029           do_jump_by_parts_greater_rtx (mode, 1, op1, op0,
1030                                         if_false_label, if_true_label, prob);
1031           break;
1032
1033         case LEU:
1034           do_jump_by_parts_greater_rtx (mode, 1, op0, op1,
1035                                         if_true_label, if_false_label,
1036                                         inv (prob));
1037           break;
1038
1039         case GTU:
1040           do_jump_by_parts_greater_rtx (mode, 1, op0, op1,
1041                                         if_false_label, if_true_label, prob);
1042           break;
1043
1044         case GEU:
1045           do_jump_by_parts_greater_rtx (mode, 1, op1, op0,
1046                                         if_true_label, if_false_label,
1047                                         inv (prob));
1048           break;
1049
1050         case LT:
1051           do_jump_by_parts_greater_rtx (mode, 0, op1, op0,
1052                                         if_false_label, if_true_label, prob);
1053           break;
1054
1055         case LE:
1056           do_jump_by_parts_greater_rtx (mode, 0, op0, op1,
1057                                         if_true_label, if_false_label,
1058                                         inv (prob));
1059           break;
1060
1061         case GT:
1062           do_jump_by_parts_greater_rtx (mode, 0, op0, op1,
1063                                         if_false_label, if_true_label, prob);
1064           break;
1065
1066         case GE:
1067           do_jump_by_parts_greater_rtx (mode, 0, op1, op0,
1068                                         if_true_label, if_false_label,
1069                                         inv (prob));
1070           break;
1071
1072         case EQ:
1073           do_jump_by_parts_equality_rtx (mode, op0, op1, if_false_label,
1074                                          if_true_label, prob);
1075           break;
1076
1077         case NE:
1078           do_jump_by_parts_equality_rtx (mode, op0, op1, if_true_label,
1079                                          if_false_label, inv (prob));
1080           break;
1081
1082         default:
1083           gcc_unreachable ();
1084         }
1085     }
1086   else
1087     {
1088       if (SCALAR_FLOAT_MODE_P (mode)
1089           && ! can_compare_p (code, mode, ccp_jump)
1090           && can_compare_p (swap_condition (code), mode, ccp_jump))
1091         {
1092           code = swap_condition (code);
1093           std::swap (op0, op1);
1094         }
1095       else if (SCALAR_FLOAT_MODE_P (mode)
1096                && ! can_compare_p (code, mode, ccp_jump)
1097                /* Never split ORDERED and UNORDERED.
1098                   These must be implemented.  */
1099                && (code != ORDERED && code != UNORDERED)
1100                /* Split a floating-point comparison if
1101                   we can jump on other conditions...  */
1102                && (have_insn_for (COMPARE, mode)
1103                    /* ... or if there is no libcall for it.  */
1104                    || code_to_optab (code) == unknown_optab))
1105         {
1106           enum rtx_code first_code;
1107           bool and_them = split_comparison (code, mode, &first_code, &code);
1108
1109           /* If there are no NaNs, the first comparison should always fall
1110              through.  */
1111           if (!HONOR_NANS (mode))
1112             gcc_assert (first_code == (and_them ? ORDERED : UNORDERED));
1113
1114           else
1115             {
1116               int first_prob = prob;
1117               if (first_code == UNORDERED)
1118                 first_prob = REG_BR_PROB_BASE / 100;
1119               else if (first_code == ORDERED)
1120                 first_prob = REG_BR_PROB_BASE - REG_BR_PROB_BASE / 100;
1121               if (and_them)
1122                 {
1123                   rtx_code_label *dest_label;
1124                   /* If we only jump if true, just bypass the second jump.  */
1125                   if (! if_false_label)
1126                     {
1127                       if (! dummy_label)
1128                         dummy_label = gen_label_rtx ();
1129                       dest_label = dummy_label;
1130                     }
1131                   else
1132                     dest_label = if_false_label;
1133                   do_compare_rtx_and_jump (op0, op1, first_code, unsignedp, mode,
1134                                            size, dest_label, NULL, first_prob);
1135                 }
1136               else
1137                 do_compare_rtx_and_jump (op0, op1, first_code, unsignedp, mode,
1138                                          size, NULL, if_true_label, first_prob);
1139             }
1140         }
1141
1142       emit_cmp_and_jump_insns (op0, op1, code, size, mode, unsignedp,
1143                                if_true_label, prob);
1144     }
1145
1146   if (if_false_label)
1147     emit_jump (if_false_label);
1148   if (dummy_label)
1149     emit_label (dummy_label);
1150 }
1151
1152 /* Generate code for a comparison expression EXP (including code to compute
1153    the values to be compared) and a conditional jump to IF_FALSE_LABEL and/or
1154    IF_TRUE_LABEL.  One of the labels can be NULL_RTX, in which case the
1155    generated code will drop through.
1156    SIGNED_CODE should be the rtx operation for this comparison for
1157    signed data; UNSIGNED_CODE, likewise for use if data is unsigned.
1158
1159    We force a stack adjustment unless there are currently
1160    things pushed on the stack that aren't yet used.  */
1161
1162 static void
1163 do_compare_and_jump (tree treeop0, tree treeop1, enum rtx_code signed_code,
1164                      enum rtx_code unsigned_code,
1165                      rtx_code_label *if_false_label,
1166                      rtx_code_label *if_true_label, int prob)
1167 {
1168   rtx op0, op1;
1169   tree type;
1170   machine_mode mode;
1171   int unsignedp;
1172   enum rtx_code code;
1173
1174   /* Don't crash if the comparison was erroneous.  */
1175   op0 = expand_normal (treeop0);
1176   if (TREE_CODE (treeop0) == ERROR_MARK)
1177     return;
1178
1179   op1 = expand_normal (treeop1);
1180   if (TREE_CODE (treeop1) == ERROR_MARK)
1181     return;
1182
1183   type = TREE_TYPE (treeop0);
1184   mode = TYPE_MODE (type);
1185   if (TREE_CODE (treeop0) == INTEGER_CST
1186       && (TREE_CODE (treeop1) != INTEGER_CST
1187           || (GET_MODE_BITSIZE (mode)
1188               > GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (treeop1))))))
1189     {
1190       /* op0 might have been replaced by promoted constant, in which
1191          case the type of second argument should be used.  */
1192       type = TREE_TYPE (treeop1);
1193       mode = TYPE_MODE (type);
1194     }
1195   unsignedp = TYPE_UNSIGNED (type);
1196   code = unsignedp ? unsigned_code : signed_code;
1197
1198   /* If function pointers need to be "canonicalized" before they can
1199      be reliably compared, then canonicalize them.
1200      Only do this if *both* sides of the comparison are function pointers.
1201      If one side isn't, we want a noncanonicalized comparison.  See PR
1202      middle-end/17564.  */
1203   if (targetm.have_canonicalize_funcptr_for_compare ()
1204       && POINTER_TYPE_P (TREE_TYPE (treeop0))
1205       && POINTER_TYPE_P (TREE_TYPE (treeop1))
1206       && FUNC_OR_METHOD_TYPE_P (TREE_TYPE (TREE_TYPE (treeop0)))
1207       && FUNC_OR_METHOD_TYPE_P (TREE_TYPE (TREE_TYPE (treeop1))))
1208     {
1209       rtx new_op0 = gen_reg_rtx (mode);
1210       rtx new_op1 = gen_reg_rtx (mode);
1211
1212       emit_insn (targetm.gen_canonicalize_funcptr_for_compare (new_op0, op0));
1213       op0 = new_op0;
1214
1215       emit_insn (targetm.gen_canonicalize_funcptr_for_compare (new_op1, op1));
1216       op1 = new_op1;
1217     }
1218
1219   do_compare_rtx_and_jump (op0, op1, code, unsignedp, mode,
1220                            ((mode == BLKmode)
1221                             ? expr_size (treeop0) : NULL_RTX),
1222                            if_false_label, if_true_label, prob);
1223 }
1224
1225 #include "gt-dojump.h"