gcc/dojump.c

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