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           tem = if_true_label;
 991           if_true_label = if_false_label;
 992           if_false_label = tem;
 993           code = rcode;
 994           prob = inv (prob);
 995         }
 996     }
 997
 998   /* If one operand is constant, make it the second one.  Only do this
 999      if the other operand is not constant as well.  */
1000
1001   if (swap_commutative_operands_p (op0, op1))
1002     {
1003       tem = op0;
1004       op0 = op1;
1005       op1 = tem;
1006       code = swap_condition (code);
1007     }
1008
1009   do_pending_stack_adjust ();
1010
1011   code = unsignedp ? unsigned_condition (code) : code;
1012   if (0 != (tem = simplify_relational_operation (code, mode, VOIDmode,
1013                                                  op0, op1)))
1014     {
1015       if (CONSTANT_P (tem))
1016         {
1017           rtx label = (tem == const0_rtx || tem == CONST0_RTX (mode))
1018                       ? if_false_label : if_true_label;
1019           if (label)
1020             emit_jump (label);
1021           return;
1022         }
1023
1024       code = GET_CODE (tem);
1025       mode = GET_MODE (tem);
1026       op0 = XEXP (tem, 0);
1027       op1 = XEXP (tem, 1);
1028       unsignedp = (code == GTU || code == LTU || code == GEU || code == LEU);
1029     }
1030
1031   if (! if_true_label)
1032     dummy_label = if_true_label = gen_label_rtx ();
1033
1034   if (GET_MODE_CLASS (mode) == MODE_INT
1035       && ! can_compare_p (code, mode, ccp_jump))
1036     {
1037       switch (code)
1038         {
1039         case LTU:
1040           do_jump_by_parts_greater_rtx (mode, 1, op1, op0,
1041                                         if_false_label, if_true_label, prob);
1042           break;
1043
1044         case LEU:
1045           do_jump_by_parts_greater_rtx (mode, 1, op0, op1,
1046                                         if_true_label, if_false_label,
1047                                         inv (prob));
1048           break;
1049
1050         case GTU:
1051           do_jump_by_parts_greater_rtx (mode, 1, op0, op1,
1052                                         if_false_label, if_true_label, prob);
1053           break;
1054
1055         case GEU:
1056           do_jump_by_parts_greater_rtx (mode, 1, op1, op0,
1057                                         if_true_label, if_false_label,
1058                                         inv (prob));
1059           break;
1060
1061         case LT:
1062           do_jump_by_parts_greater_rtx (mode, 0, op1, op0,
1063                                         if_false_label, if_true_label, prob);
1064           break;
1065
1066         case LE:
1067           do_jump_by_parts_greater_rtx (mode, 0, op0, op1,
1068                                         if_true_label, if_false_label,
1069                                         inv (prob));
1070           break;
1071
1072         case GT:
1073           do_jump_by_parts_greater_rtx (mode, 0, op0, op1,
1074                                         if_false_label, if_true_label, prob);
1075           break;
1076
1077         case GE:
1078           do_jump_by_parts_greater_rtx (mode, 0, op1, op0,
1079                                         if_true_label, if_false_label,
1080                                         inv (prob));
1081           break;
1082
1083         case EQ:
1084           do_jump_by_parts_equality_rtx (mode, op0, op1, if_false_label,
1085                                          if_true_label, prob);
1086           break;
1087
1088         case NE:
1089           do_jump_by_parts_equality_rtx (mode, op0, op1, if_true_label,
1090                                          if_false_label, inv (prob));
1091           break;
1092
1093         default:
1094           gcc_unreachable ();
1095         }
1096     }
1097   else
1098     {
1099       if (SCALAR_FLOAT_MODE_P (mode)
1100           && ! can_compare_p (code, mode, ccp_jump)
1101           && can_compare_p (swap_condition (code), mode, ccp_jump))
1102         {
1103           rtx tmp;
1104           code = swap_condition (code);
1105           tmp = op0;
1106           op0 = op1;
1107           op1 = tmp;
1108         }
1109       else if (SCALAR_FLOAT_MODE_P (mode)
1110                && ! can_compare_p (code, mode, ccp_jump)
1111                /* Never split ORDERED and UNORDERED.
1112                   These must be implemented.  */
1113                && (code != ORDERED && code != UNORDERED)
1114                /* Split a floating-point comparison if
1115                   we can jump on other conditions...  */
1116                && (have_insn_for (COMPARE, mode)
1117                    /* ... or if there is no libcall for it.  */
1118                    || code_to_optab (code) == unknown_optab))
1119         {
1120           enum rtx_code first_code;
1121           bool and_them = split_comparison (code, mode, &first_code, &code);
1122
1123           /* If there are no NaNs, the first comparison should always fall
1124              through.  */
1125           if (!HONOR_NANS (mode))
1126             gcc_assert (first_code == (and_them ? ORDERED : UNORDERED));
1127
1128           else
1129             {
1130               int first_prob = prob;
1131               if (first_code == UNORDERED)
1132                 first_prob = REG_BR_PROB_BASE / 100;
1133               else if (first_code == ORDERED)
1134                 first_prob = REG_BR_PROB_BASE - REG_BR_PROB_BASE / 100;
1135               if (and_them)
1136                 {
1137                   rtx dest_label;
1138                   /* If we only jump if true, just bypass the second jump.  */
1139                   if (! if_false_label)
1140                     {
1141                       if (! dummy_label)
1142                         dummy_label = gen_label_rtx ();
1143                       dest_label = dummy_label;
1144                     }
1145                   else
1146                     dest_label = if_false_label;
1147                   do_compare_rtx_and_jump (op0, op1, first_code, unsignedp, mode,
1148                                            size, dest_label, NULL_RTX,
1149                                            first_prob);
1150                 }
1151               else
1152                 do_compare_rtx_and_jump (op0, op1, first_code, unsignedp, mode,
1153                                          size, NULL_RTX, if_true_label,
1154                                          first_prob);
1155             }
1156         }
1157
1158       emit_cmp_and_jump_insns (op0, op1, code, size, mode, unsignedp,
1159                                if_true_label, prob);
1160     }
1161
1162   if (if_false_label)
1163     emit_jump (if_false_label);
1164   if (dummy_label)
1165     emit_label (dummy_label);
1166 }
1167
1168 /* Generate code for a comparison expression EXP (including code to compute
1169    the values to be compared) and a conditional jump to IF_FALSE_LABEL and/or
1170    IF_TRUE_LABEL.  One of the labels can be NULL_RTX, in which case the
1171    generated code will drop through.
1172    SIGNED_CODE should be the rtx operation for this comparison for
1173    signed data; UNSIGNED_CODE, likewise for use if data is unsigned.
1174
1175    We force a stack adjustment unless there are currently
1176    things pushed on the stack that aren't yet used.  */
1177
1178 static void
1179 do_compare_and_jump (tree treeop0, tree treeop1, enum rtx_code signed_code,
1180                      enum rtx_code unsigned_code, rtx if_false_label,
1181                      rtx if_true_label, int prob)
1182 {
1183   rtx op0, op1;
1184   tree type;
1185   machine_mode mode;
1186   int unsignedp;
1187   enum rtx_code code;
1188
1189   /* Don't crash if the comparison was erroneous.  */
1190   op0 = expand_normal (treeop0);
1191   if (TREE_CODE (treeop0) == ERROR_MARK)
1192     return;
1193
1194   op1 = expand_normal (treeop1);
1195   if (TREE_CODE (treeop1) == ERROR_MARK)
1196     return;
1197
1198   type = TREE_TYPE (treeop0);
1199   mode = TYPE_MODE (type);
1200   if (TREE_CODE (treeop0) == INTEGER_CST
1201       && (TREE_CODE (treeop1) != INTEGER_CST
1202           || (GET_MODE_BITSIZE (mode)
1203               > GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (treeop1))))))
1204     {
1205       /* op0 might have been replaced by promoted constant, in which
1206          case the type of second argument should be used.  */
1207       type = TREE_TYPE (treeop1);
1208       mode = TYPE_MODE (type);
1209     }
1210   unsignedp = TYPE_UNSIGNED (type);
1211   code = unsignedp ? unsigned_code : signed_code;
1212
1213 #ifdef HAVE_canonicalize_funcptr_for_compare
1214   /* If function pointers need to be "canonicalized" before they can
1215      be reliably compared, then canonicalize them.
1216      Only do this if *both* sides of the comparison are function pointers.
1217      If one side isn't, we want a noncanonicalized comparison.  See PR
1218      middle-end/17564.  */
1219   if (HAVE_canonicalize_funcptr_for_compare
1220       && TREE_CODE (TREE_TYPE (treeop0)) == POINTER_TYPE
1221       && TREE_CODE (TREE_TYPE (TREE_TYPE (treeop0)))
1222           == FUNCTION_TYPE
1223       && TREE_CODE (TREE_TYPE (treeop1)) == POINTER_TYPE
1224       && TREE_CODE (TREE_TYPE (TREE_TYPE (treeop1)))
1225           == FUNCTION_TYPE)
1226     {
1227       rtx new_op0 = gen_reg_rtx (mode);
1228       rtx new_op1 = gen_reg_rtx (mode);
1229
1230       emit_insn (gen_canonicalize_funcptr_for_compare (new_op0, op0));
1231       op0 = new_op0;
1232
1233       emit_insn (gen_canonicalize_funcptr_for_compare (new_op1, op1));
1234       op1 = new_op1;
1235     }
1236 #endif
1237
1238   do_compare_rtx_and_jump (op0, op1, code, unsignedp, mode,
1239                            ((mode == BLKmode)
1240                             ? expr_size (treeop0) : NULL_RTX),
1241                            if_false_label, if_true_label, prob);
1242 }
1243
1244 #include "gt-dojump.h"