gcc/dojump.c

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