gcc/dojump.c

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