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