gcc/dojump.c

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