190075Sobrien/* If-conversion support. 2169689Skan Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006 3169689Skan Free Software Foundation, Inc. 490075Sobrien 590075Sobrien This file is part of GCC. 690075Sobrien 790075Sobrien GCC is free software; you can redistribute it and/or modify it 890075Sobrien under the terms of the GNU General Public License as published by 990075Sobrien the Free Software Foundation; either version 2, or (at your option) 1090075Sobrien any later version. 1190075Sobrien 1290075Sobrien GCC is distributed in the hope that it will be useful, but WITHOUT 1390075Sobrien ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 1490075Sobrien or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public 1590075Sobrien License for more details. 1690075Sobrien 1790075Sobrien You should have received a copy of the GNU General Public License 1890075Sobrien along with GCC; see the file COPYING. If not, write to the Free 19169689Skan Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 20169689Skan 02110-1301, USA. */ 2190075Sobrien 2290075Sobrien#include "config.h" 2390075Sobrien#include "system.h" 24132718Skan#include "coretypes.h" 25132718Skan#include "tm.h" 2690075Sobrien 2790075Sobrien#include "rtl.h" 2890075Sobrien#include "regs.h" 2990075Sobrien#include "function.h" 3090075Sobrien#include "flags.h" 3190075Sobrien#include "insn-config.h" 3290075Sobrien#include "recog.h" 3396263Sobrien#include "except.h" 3490075Sobrien#include "hard-reg-set.h" 3590075Sobrien#include "basic-block.h" 3690075Sobrien#include "expr.h" 3790075Sobrien#include "real.h" 3890075Sobrien#include "output.h" 39132718Skan#include "optabs.h" 4090075Sobrien#include "toplev.h" 4190075Sobrien#include "tm_p.h" 42132718Skan#include "cfgloop.h" 43132718Skan#include "target.h" 44169689Skan#include "timevar.h" 45169689Skan#include "tree-pass.h" 4690075Sobrien 4790075Sobrien 4890075Sobrien#ifndef HAVE_conditional_execution 4990075Sobrien#define HAVE_conditional_execution 0 5090075Sobrien#endif 5190075Sobrien#ifndef HAVE_conditional_move 5290075Sobrien#define HAVE_conditional_move 0 5390075Sobrien#endif 5490075Sobrien#ifndef HAVE_incscc 5590075Sobrien#define HAVE_incscc 0 5690075Sobrien#endif 5790075Sobrien#ifndef HAVE_decscc 5890075Sobrien#define HAVE_decscc 0 5990075Sobrien#endif 6090075Sobrien#ifndef HAVE_trap 6190075Sobrien#define HAVE_trap 0 6290075Sobrien#endif 6390075Sobrien#ifndef HAVE_conditional_trap 6490075Sobrien#define HAVE_conditional_trap 0 6590075Sobrien#endif 6690075Sobrien 6790075Sobrien#ifndef MAX_CONDITIONAL_EXECUTE 6890075Sobrien#define MAX_CONDITIONAL_EXECUTE (BRANCH_COST + 1) 6990075Sobrien#endif 7090075Sobrien 71169689Skan#define NULL_BLOCK ((basic_block) NULL) 7290075Sobrien 7390075Sobrien/* # of IF-THEN or IF-THEN-ELSE blocks we looked at */ 7490075Sobrienstatic int num_possible_if_blocks; 7590075Sobrien 7690075Sobrien/* # of IF-THEN or IF-THEN-ELSE blocks were converted to conditional 7790075Sobrien execution. */ 7890075Sobrienstatic int num_updated_if_blocks; 7990075Sobrien 80132718Skan/* # of changes made which require life information to be updated. */ 81132718Skanstatic int num_true_changes; 8290075Sobrien 83117395Skan/* Whether conditional execution changes were made. */ 84117395Skanstatic int cond_exec_changed_p; 85117395Skan 8690075Sobrien/* True if life data ok at present. */ 8790075Sobrienstatic bool life_data_ok; 8890075Sobrien 8990075Sobrien/* Forward references. */ 90132718Skanstatic int count_bb_insns (basic_block); 91169689Skanstatic bool cheap_bb_rtx_cost_p (basic_block, int); 92132718Skanstatic rtx first_active_insn (basic_block); 93132718Skanstatic rtx last_active_insn (basic_block, int); 94132718Skanstatic basic_block block_fallthru (basic_block); 95132718Skanstatic int cond_exec_process_insns (ce_if_block_t *, rtx, rtx, rtx, rtx, int); 96132718Skanstatic rtx cond_exec_get_condition (rtx); 97132718Skanstatic int cond_exec_process_if_block (ce_if_block_t *, int); 98132718Skanstatic rtx noce_get_condition (rtx, rtx *); 99132718Skanstatic int noce_operand_ok (rtx); 100132718Skanstatic int noce_process_if_block (ce_if_block_t *); 101132718Skanstatic int process_if_block (ce_if_block_t *); 102132718Skanstatic void merge_if_block (ce_if_block_t *); 103132718Skanstatic int find_cond_trap (basic_block, edge, edge); 104132718Skanstatic basic_block find_if_header (basic_block, int); 105132718Skanstatic int block_jumps_and_fallthru_p (basic_block, basic_block); 106132718Skanstatic int find_if_block (ce_if_block_t *); 107132718Skanstatic int find_if_case_1 (basic_block, edge, edge); 108132718Skanstatic int find_if_case_2 (basic_block, edge, edge); 109132718Skanstatic int find_memory (rtx *, void *); 110132718Skanstatic int dead_or_predicable (basic_block, basic_block, basic_block, 111132718Skan basic_block, int); 112132718Skanstatic void noce_emit_move_insn (rtx, rtx); 113132718Skanstatic rtx block_has_only_trap (basic_block); 11490075Sobrien 115169689Skan/* Count the number of non-jump active insns in BB. */ 116169689Skan 117169689Skanstatic int 118169689Skancount_bb_insns (basic_block bb) 119132718Skan{ 120169689Skan int count = 0; 121169689Skan rtx insn = BB_HEAD (bb); 122169689Skan 123169689Skan while (1) 124132718Skan { 125169689Skan if (CALL_P (insn) || NONJUMP_INSN_P (insn)) 126169689Skan count++; 127169689Skan 128169689Skan if (insn == BB_END (bb)) 129169689Skan break; 130169689Skan insn = NEXT_INSN (insn); 131132718Skan } 132132718Skan 133169689Skan return count; 134132718Skan} 135132718Skan 136169689Skan/* Determine whether the total insn_rtx_cost on non-jump insns in 137169689Skan basic block BB is less than MAX_COST. This function returns 138169689Skan false if the cost of any instruction could not be estimated. */ 13990075Sobrien 140169689Skanstatic bool 141169689Skancheap_bb_rtx_cost_p (basic_block bb, int max_cost) 14290075Sobrien{ 14390075Sobrien int count = 0; 144132718Skan rtx insn = BB_HEAD (bb); 14590075Sobrien 14690075Sobrien while (1) 14790075Sobrien { 148169689Skan if (NONJUMP_INSN_P (insn)) 149169689Skan { 150169689Skan int cost = insn_rtx_cost (PATTERN (insn)); 151169689Skan if (cost == 0) 152169689Skan return false; 15390075Sobrien 154169689Skan /* If this instruction is the load or set of a "stack" register, 155169689Skan such as a floating point register on x87, then the cost of 156169689Skan speculatively executing this insn may need to include 157169689Skan the additional cost of popping its result off of the 158169689Skan register stack. Unfortunately, correctly recognizing and 159169689Skan accounting for this additional overhead is tricky, so for 160169689Skan now we simply prohibit such speculative execution. */ 161169689Skan#ifdef STACK_REGS 162169689Skan { 163169689Skan rtx set = single_set (insn); 164169689Skan if (set && STACK_REG_P (SET_DEST (set))) 165169689Skan return false; 166169689Skan } 167169689Skan#endif 168169689Skan 169169689Skan count += cost; 170169689Skan if (count >= max_cost) 171169689Skan return false; 172169689Skan } 173169689Skan else if (CALL_P (insn)) 174169689Skan return false; 175169689Skan 176132718Skan if (insn == BB_END (bb)) 17790075Sobrien break; 17890075Sobrien insn = NEXT_INSN (insn); 17990075Sobrien } 18090075Sobrien 181169689Skan return true; 18290075Sobrien} 18390075Sobrien 18490075Sobrien/* Return the first non-jump active insn in the basic block. */ 18590075Sobrien 18690075Sobrienstatic rtx 187132718Skanfirst_active_insn (basic_block bb) 18890075Sobrien{ 189132718Skan rtx insn = BB_HEAD (bb); 19090075Sobrien 191169689Skan if (LABEL_P (insn)) 19290075Sobrien { 193132718Skan if (insn == BB_END (bb)) 19490075Sobrien return NULL_RTX; 19590075Sobrien insn = NEXT_INSN (insn); 19690075Sobrien } 19790075Sobrien 198169689Skan while (NOTE_P (insn)) 19990075Sobrien { 200132718Skan if (insn == BB_END (bb)) 20190075Sobrien return NULL_RTX; 20290075Sobrien insn = NEXT_INSN (insn); 20390075Sobrien } 20490075Sobrien 205169689Skan if (JUMP_P (insn)) 20690075Sobrien return NULL_RTX; 20790075Sobrien 20890075Sobrien return insn; 20990075Sobrien} 21090075Sobrien 211117395Skan/* Return the last non-jump active (non-jump) insn in the basic block. */ 21290075Sobrien 213117395Skanstatic rtx 214132718Skanlast_active_insn (basic_block bb, int skip_use_p) 21590075Sobrien{ 216132718Skan rtx insn = BB_END (bb); 217132718Skan rtx head = BB_HEAD (bb); 218117395Skan 219169689Skan while (NOTE_P (insn) 220169689Skan || JUMP_P (insn) 221117395Skan || (skip_use_p 222169689Skan && NONJUMP_INSN_P (insn) 223117395Skan && GET_CODE (PATTERN (insn)) == USE)) 22490075Sobrien { 225117395Skan if (insn == head) 226117395Skan return NULL_RTX; 227117395Skan insn = PREV_INSN (insn); 22890075Sobrien } 22990075Sobrien 230169689Skan if (LABEL_P (insn)) 231117395Skan return NULL_RTX; 232117395Skan 233117395Skan return insn; 23490075Sobrien} 23590075Sobrien 236169689Skan/* Return the basic block reached by falling though the basic block BB. */ 23790075Sobrien 238117395Skanstatic basic_block 239132718Skanblock_fallthru (basic_block bb) 240117395Skan{ 241117395Skan edge e; 242169689Skan edge_iterator ei; 243117395Skan 244169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 245169689Skan if (e->flags & EDGE_FALLTHRU) 246169689Skan break; 247117395Skan 248117395Skan return (e) ? e->dest : NULL_BLOCK; 249117395Skan} 25090075Sobrien 25190075Sobrien/* Go through a bunch of insns, converting them to conditional 25290075Sobrien execution format if possible. Return TRUE if all of the non-note 25390075Sobrien insns were processed. */ 25490075Sobrien 25590075Sobrienstatic int 256132718Skancond_exec_process_insns (ce_if_block_t *ce_info ATTRIBUTE_UNUSED, 257132718Skan /* if block information */rtx start, 258132718Skan /* first insn to look at */rtx end, 259132718Skan /* last insn to look at */rtx test, 260132718Skan /* conditional execution test */rtx prob_val, 261132718Skan /* probability of branch taken. */int mod_ok) 26290075Sobrien{ 26390075Sobrien int must_be_last = FALSE; 26490075Sobrien rtx insn; 265117395Skan rtx xtest; 26690075Sobrien rtx pattern; 26790075Sobrien 268117395Skan if (!start || !end) 269117395Skan return FALSE; 270117395Skan 27190075Sobrien for (insn = start; ; insn = NEXT_INSN (insn)) 27290075Sobrien { 273169689Skan if (NOTE_P (insn)) 27490075Sobrien goto insn_done; 27590075Sobrien 276169689Skan gcc_assert(NONJUMP_INSN_P (insn) || CALL_P (insn)); 27790075Sobrien 27890075Sobrien /* Remove USE insns that get in the way. */ 27990075Sobrien if (reload_completed && GET_CODE (PATTERN (insn)) == USE) 28090075Sobrien { 281132718Skan /* ??? Ug. Actually unlinking the thing is problematic, 28290075Sobrien given what we'd have to coordinate with our callers. */ 283169689Skan SET_INSN_DELETED (insn); 28490075Sobrien goto insn_done; 28590075Sobrien } 28690075Sobrien 28790075Sobrien /* Last insn wasn't last? */ 28890075Sobrien if (must_be_last) 28990075Sobrien return FALSE; 29090075Sobrien 29190075Sobrien if (modified_in_p (test, insn)) 29290075Sobrien { 29390075Sobrien if (!mod_ok) 29490075Sobrien return FALSE; 29590075Sobrien must_be_last = TRUE; 29690075Sobrien } 29790075Sobrien 29890075Sobrien /* Now build the conditional form of the instruction. */ 29990075Sobrien pattern = PATTERN (insn); 300117395Skan xtest = copy_rtx (test); 30190075Sobrien 302117395Skan /* If this is already a COND_EXEC, rewrite the test to be an AND of the 303117395Skan two conditions. */ 304117395Skan if (GET_CODE (pattern) == COND_EXEC) 305117395Skan { 306117395Skan if (GET_MODE (xtest) != GET_MODE (COND_EXEC_TEST (pattern))) 307117395Skan return FALSE; 308117395Skan 309117395Skan xtest = gen_rtx_AND (GET_MODE (xtest), xtest, 310117395Skan COND_EXEC_TEST (pattern)); 311117395Skan pattern = COND_EXEC_CODE (pattern); 312117395Skan } 313117395Skan 314117395Skan pattern = gen_rtx_COND_EXEC (VOIDmode, xtest, pattern); 315117395Skan 31690075Sobrien /* If the machine needs to modify the insn being conditionally executed, 31790075Sobrien say for example to force a constant integer operand into a temp 31890075Sobrien register, do so here. */ 31990075Sobrien#ifdef IFCVT_MODIFY_INSN 320117395Skan IFCVT_MODIFY_INSN (ce_info, pattern, insn); 32190075Sobrien if (! pattern) 32290075Sobrien return FALSE; 32390075Sobrien#endif 32490075Sobrien 325117395Skan validate_change (insn, &PATTERN (insn), pattern, 1); 32690075Sobrien 327169689Skan if (CALL_P (insn) && prob_val) 32890075Sobrien validate_change (insn, ®_NOTES (insn), 32990075Sobrien alloc_EXPR_LIST (REG_BR_PROB, prob_val, 33090075Sobrien REG_NOTES (insn)), 1); 33190075Sobrien 33290075Sobrien insn_done: 33390075Sobrien if (insn == end) 33490075Sobrien break; 33590075Sobrien } 33690075Sobrien 33790075Sobrien return TRUE; 33890075Sobrien} 33990075Sobrien 34090075Sobrien/* Return the condition for a jump. Do not do any special processing. */ 34190075Sobrien 34290075Sobrienstatic rtx 343132718Skancond_exec_get_condition (rtx jump) 34490075Sobrien{ 34590075Sobrien rtx test_if, cond; 34690075Sobrien 34790075Sobrien if (any_condjump_p (jump)) 34890075Sobrien test_if = SET_SRC (pc_set (jump)); 34990075Sobrien else 35090075Sobrien return NULL_RTX; 35190075Sobrien cond = XEXP (test_if, 0); 35290075Sobrien 35390075Sobrien /* If this branches to JUMP_LABEL when the condition is false, 35490075Sobrien reverse the condition. */ 35590075Sobrien if (GET_CODE (XEXP (test_if, 2)) == LABEL_REF 35690075Sobrien && XEXP (XEXP (test_if, 2), 0) == JUMP_LABEL (jump)) 35790075Sobrien { 35890075Sobrien enum rtx_code rev = reversed_comparison_code (cond, jump); 35990075Sobrien if (rev == UNKNOWN) 36090075Sobrien return NULL_RTX; 36190075Sobrien 36290075Sobrien cond = gen_rtx_fmt_ee (rev, GET_MODE (cond), XEXP (cond, 0), 36390075Sobrien XEXP (cond, 1)); 36490075Sobrien } 36590075Sobrien 36690075Sobrien return cond; 36790075Sobrien} 36890075Sobrien 36990075Sobrien/* Given a simple IF-THEN or IF-THEN-ELSE block, attempt to convert it 37090075Sobrien to conditional execution. Return TRUE if we were successful at 371117395Skan converting the block. */ 37290075Sobrien 37390075Sobrienstatic int 374132718Skancond_exec_process_if_block (ce_if_block_t * ce_info, 375132718Skan /* if block information */int do_multiple_p) 37690075Sobrien{ 377117395Skan basic_block test_bb = ce_info->test_bb; /* last test block */ 378117395Skan basic_block then_bb = ce_info->then_bb; /* THEN */ 379117395Skan basic_block else_bb = ce_info->else_bb; /* ELSE or NULL */ 38090075Sobrien rtx test_expr; /* expression in IF_THEN_ELSE that is tested */ 38190075Sobrien rtx then_start; /* first insn in THEN block */ 38290075Sobrien rtx then_end; /* last insn + 1 in THEN block */ 38390075Sobrien rtx else_start = NULL_RTX; /* first insn in ELSE block or NULL */ 38490075Sobrien rtx else_end = NULL_RTX; /* last insn + 1 in ELSE block */ 38590075Sobrien int max; /* max # of insns to convert. */ 38690075Sobrien int then_mod_ok; /* whether conditional mods are ok in THEN */ 38790075Sobrien rtx true_expr; /* test for else block insns */ 38890075Sobrien rtx false_expr; /* test for then block insns */ 38990075Sobrien rtx true_prob_val; /* probability of else block */ 39090075Sobrien rtx false_prob_val; /* probability of then block */ 39190075Sobrien int n_insns; 39290075Sobrien enum rtx_code false_code; 39390075Sobrien 394117395Skan /* If test is comprised of && or || elements, and we've failed at handling 395117395Skan all of them together, just use the last test if it is the special case of 396117395Skan && elements without an ELSE block. */ 397117395Skan if (!do_multiple_p && ce_info->num_multiple_test_blocks) 398117395Skan { 399117395Skan if (else_bb || ! ce_info->and_and_p) 400117395Skan return FALSE; 401117395Skan 402117395Skan ce_info->test_bb = test_bb = ce_info->last_test_bb; 403117395Skan ce_info->num_multiple_test_blocks = 0; 404117395Skan ce_info->num_and_and_blocks = 0; 405117395Skan ce_info->num_or_or_blocks = 0; 406117395Skan } 407117395Skan 40890075Sobrien /* Find the conditional jump to the ELSE or JOIN part, and isolate 40990075Sobrien the test. */ 410132718Skan test_expr = cond_exec_get_condition (BB_END (test_bb)); 41190075Sobrien if (! test_expr) 41290075Sobrien return FALSE; 41390075Sobrien 41490075Sobrien /* If the conditional jump is more than just a conditional jump, 41590075Sobrien then we can not do conditional execution conversion on this block. */ 416132718Skan if (! onlyjump_p (BB_END (test_bb))) 41790075Sobrien return FALSE; 41890075Sobrien 419117395Skan /* Collect the bounds of where we're to search, skipping any labels, jumps 420117395Skan and notes at the beginning and end of the block. Then count the total 421117395Skan number of insns and see if it is small enough to convert. */ 422117395Skan then_start = first_active_insn (then_bb); 423117395Skan then_end = last_active_insn (then_bb, TRUE); 424117395Skan n_insns = ce_info->num_then_insns = count_bb_insns (then_bb); 425117395Skan max = MAX_CONDITIONAL_EXECUTE; 42690075Sobrien 42790075Sobrien if (else_bb) 42890075Sobrien { 429117395Skan max *= 2; 430117395Skan else_start = first_active_insn (else_bb); 431117395Skan else_end = last_active_insn (else_bb, TRUE); 432117395Skan n_insns += ce_info->num_else_insns = count_bb_insns (else_bb); 43390075Sobrien } 43490075Sobrien 43590075Sobrien if (n_insns > max) 43690075Sobrien return FALSE; 43790075Sobrien 43890075Sobrien /* Map test_expr/test_jump into the appropriate MD tests to use on 43990075Sobrien the conditionally executed code. */ 440132718Skan 44190075Sobrien true_expr = test_expr; 44290075Sobrien 443132718Skan false_code = reversed_comparison_code (true_expr, BB_END (test_bb)); 44490075Sobrien if (false_code != UNKNOWN) 44590075Sobrien false_expr = gen_rtx_fmt_ee (false_code, GET_MODE (true_expr), 44690075Sobrien XEXP (true_expr, 0), XEXP (true_expr, 1)); 44790075Sobrien else 44890075Sobrien false_expr = NULL_RTX; 44990075Sobrien 45090075Sobrien#ifdef IFCVT_MODIFY_TESTS 45190075Sobrien /* If the machine description needs to modify the tests, such as setting a 45290075Sobrien conditional execution register from a comparison, it can do so here. */ 453117395Skan IFCVT_MODIFY_TESTS (ce_info, true_expr, false_expr); 45490075Sobrien 455132718Skan /* See if the conversion failed. */ 45690075Sobrien if (!true_expr || !false_expr) 45790075Sobrien goto fail; 45890075Sobrien#endif 45990075Sobrien 460132718Skan true_prob_val = find_reg_note (BB_END (test_bb), REG_BR_PROB, NULL_RTX); 46190075Sobrien if (true_prob_val) 46290075Sobrien { 46390075Sobrien true_prob_val = XEXP (true_prob_val, 0); 46490075Sobrien false_prob_val = GEN_INT (REG_BR_PROB_BASE - INTVAL (true_prob_val)); 46590075Sobrien } 46690075Sobrien else 46790075Sobrien false_prob_val = NULL_RTX; 46890075Sobrien 469117395Skan /* If we have && or || tests, do them here. These tests are in the adjacent 470117395Skan blocks after the first block containing the test. */ 471117395Skan if (ce_info->num_multiple_test_blocks > 0) 472117395Skan { 473117395Skan basic_block bb = test_bb; 474117395Skan basic_block last_test_bb = ce_info->last_test_bb; 475117395Skan 476117395Skan if (! false_expr) 477117395Skan goto fail; 478117395Skan 479117395Skan do 480117395Skan { 481117395Skan rtx start, end; 482117395Skan rtx t, f; 483169689Skan enum rtx_code f_code; 484117395Skan 485117395Skan bb = block_fallthru (bb); 486117395Skan start = first_active_insn (bb); 487117395Skan end = last_active_insn (bb, TRUE); 488117395Skan if (start 489117395Skan && ! cond_exec_process_insns (ce_info, start, end, false_expr, 490117395Skan false_prob_val, FALSE)) 491117395Skan goto fail; 492117395Skan 493117395Skan /* If the conditional jump is more than just a conditional jump, then 494117395Skan we can not do conditional execution conversion on this block. */ 495132718Skan if (! onlyjump_p (BB_END (bb))) 496117395Skan goto fail; 497117395Skan 498117395Skan /* Find the conditional jump and isolate the test. */ 499132718Skan t = cond_exec_get_condition (BB_END (bb)); 500117395Skan if (! t) 501117395Skan goto fail; 502117395Skan 503169689Skan f_code = reversed_comparison_code (t, BB_END (bb)); 504169689Skan if (f_code == UNKNOWN) 505169689Skan goto fail; 506117395Skan 507169689Skan f = gen_rtx_fmt_ee (f_code, GET_MODE (t), XEXP (t, 0), XEXP (t, 1)); 508117395Skan if (ce_info->and_and_p) 509117395Skan { 510117395Skan t = gen_rtx_AND (GET_MODE (t), true_expr, t); 511117395Skan f = gen_rtx_IOR (GET_MODE (t), false_expr, f); 512117395Skan } 513117395Skan else 514117395Skan { 515117395Skan t = gen_rtx_IOR (GET_MODE (t), true_expr, t); 516117395Skan f = gen_rtx_AND (GET_MODE (t), false_expr, f); 517117395Skan } 518117395Skan 519117395Skan /* If the machine description needs to modify the tests, such as 520117395Skan setting a conditional execution register from a comparison, it can 521117395Skan do so here. */ 522117395Skan#ifdef IFCVT_MODIFY_MULTIPLE_TESTS 523117395Skan IFCVT_MODIFY_MULTIPLE_TESTS (ce_info, bb, t, f); 524117395Skan 525132718Skan /* See if the conversion failed. */ 526117395Skan if (!t || !f) 527117395Skan goto fail; 528117395Skan#endif 529117395Skan 530117395Skan true_expr = t; 531117395Skan false_expr = f; 532117395Skan } 533117395Skan while (bb != last_test_bb); 534117395Skan } 535117395Skan 53690075Sobrien /* For IF-THEN-ELSE blocks, we don't allow modifications of the test 53790075Sobrien on then THEN block. */ 53890075Sobrien then_mod_ok = (else_bb == NULL_BLOCK); 53990075Sobrien 54090075Sobrien /* Go through the THEN and ELSE blocks converting the insns if possible 54190075Sobrien to conditional execution. */ 54290075Sobrien 54390075Sobrien if (then_end 54490075Sobrien && (! false_expr 545117395Skan || ! cond_exec_process_insns (ce_info, then_start, then_end, 546117395Skan false_expr, false_prob_val, 547117395Skan then_mod_ok))) 54890075Sobrien goto fail; 54990075Sobrien 550117395Skan if (else_bb && else_end 551117395Skan && ! cond_exec_process_insns (ce_info, else_start, else_end, 55290075Sobrien true_expr, true_prob_val, TRUE)) 55390075Sobrien goto fail; 55490075Sobrien 555117395Skan /* If we cannot apply the changes, fail. Do not go through the normal fail 556117395Skan processing, since apply_change_group will call cancel_changes. */ 55790075Sobrien if (! apply_change_group ()) 558117395Skan { 559117395Skan#ifdef IFCVT_MODIFY_CANCEL 560117395Skan /* Cancel any machine dependent changes. */ 561117395Skan IFCVT_MODIFY_CANCEL (ce_info); 562117395Skan#endif 563117395Skan return FALSE; 564117395Skan } 56590075Sobrien 56690075Sobrien#ifdef IFCVT_MODIFY_FINAL 567132718Skan /* Do any machine dependent final modifications. */ 568117395Skan IFCVT_MODIFY_FINAL (ce_info); 56990075Sobrien#endif 57090075Sobrien 57190075Sobrien /* Conversion succeeded. */ 572169689Skan if (dump_file) 573169689Skan fprintf (dump_file, "%d insn%s converted to conditional execution.\n", 57490075Sobrien n_insns, (n_insns == 1) ? " was" : "s were"); 57590075Sobrien 57690075Sobrien /* Merge the blocks! */ 577117395Skan merge_if_block (ce_info); 578117395Skan cond_exec_changed_p = TRUE; 57990075Sobrien return TRUE; 58090075Sobrien 58190075Sobrien fail: 58290075Sobrien#ifdef IFCVT_MODIFY_CANCEL 58390075Sobrien /* Cancel any machine dependent changes. */ 584117395Skan IFCVT_MODIFY_CANCEL (ce_info); 58590075Sobrien#endif 58690075Sobrien 58790075Sobrien cancel_changes (0); 58890075Sobrien return FALSE; 58990075Sobrien} 59090075Sobrien 591132718Skan/* Used by noce_process_if_block to communicate with its subroutines. 59290075Sobrien 59390075Sobrien The subroutines know that A and B may be evaluated freely. They 594132718Skan know that X is a register. They should insert new instructions 59590075Sobrien before cond_earliest. */ 59690075Sobrien 59790075Sobrienstruct noce_if_info 59890075Sobrien{ 59990075Sobrien basic_block test_bb; 60090075Sobrien rtx insn_a, insn_b; 60190075Sobrien rtx x, a, b; 60290075Sobrien rtx jump, cond, cond_earliest; 603169689Skan /* True if "b" was originally evaluated unconditionally. */ 604169689Skan bool b_unconditional; 60590075Sobrien}; 60690075Sobrien 607132718Skanstatic rtx noce_emit_store_flag (struct noce_if_info *, rtx, int, int); 608132718Skanstatic int noce_try_move (struct noce_if_info *); 609132718Skanstatic int noce_try_store_flag (struct noce_if_info *); 610132718Skanstatic int noce_try_addcc (struct noce_if_info *); 611132718Skanstatic int noce_try_store_flag_constants (struct noce_if_info *); 612132718Skanstatic int noce_try_store_flag_mask (struct noce_if_info *); 613132718Skanstatic rtx noce_emit_cmove (struct noce_if_info *, rtx, enum rtx_code, rtx, 614132718Skan rtx, rtx, rtx); 615132718Skanstatic int noce_try_cmove (struct noce_if_info *); 616132718Skanstatic int noce_try_cmove_arith (struct noce_if_info *); 617132718Skanstatic rtx noce_get_alt_condition (struct noce_if_info *, rtx, rtx *); 618132718Skanstatic int noce_try_minmax (struct noce_if_info *); 619132718Skanstatic int noce_try_abs (struct noce_if_info *); 620169689Skanstatic int noce_try_sign_mask (struct noce_if_info *); 62190075Sobrien 62290075Sobrien/* Helper function for noce_try_store_flag*. */ 62390075Sobrien 62490075Sobrienstatic rtx 625132718Skannoce_emit_store_flag (struct noce_if_info *if_info, rtx x, int reversep, 626132718Skan int normalize) 62790075Sobrien{ 62890075Sobrien rtx cond = if_info->cond; 62990075Sobrien int cond_complex; 63090075Sobrien enum rtx_code code; 63190075Sobrien 63290075Sobrien cond_complex = (! general_operand (XEXP (cond, 0), VOIDmode) 63390075Sobrien || ! general_operand (XEXP (cond, 1), VOIDmode)); 63490075Sobrien 63590075Sobrien /* If earliest == jump, or when the condition is complex, try to 63690075Sobrien build the store_flag insn directly. */ 63790075Sobrien 63890075Sobrien if (cond_complex) 63990075Sobrien cond = XEXP (SET_SRC (pc_set (if_info->jump)), 0); 64090075Sobrien 64190075Sobrien if (reversep) 64290075Sobrien code = reversed_comparison_code (cond, if_info->jump); 64390075Sobrien else 64490075Sobrien code = GET_CODE (cond); 64590075Sobrien 64690075Sobrien if ((if_info->cond_earliest == if_info->jump || cond_complex) 64790075Sobrien && (normalize == 0 || STORE_FLAG_VALUE == normalize)) 64890075Sobrien { 64990075Sobrien rtx tmp; 65090075Sobrien 65190075Sobrien tmp = gen_rtx_fmt_ee (code, GET_MODE (x), XEXP (cond, 0), 65290075Sobrien XEXP (cond, 1)); 65390075Sobrien tmp = gen_rtx_SET (VOIDmode, x, tmp); 65490075Sobrien 65590075Sobrien start_sequence (); 65690075Sobrien tmp = emit_insn (tmp); 65790075Sobrien 65890075Sobrien if (recog_memoized (tmp) >= 0) 65990075Sobrien { 66090075Sobrien tmp = get_insns (); 66190075Sobrien end_sequence (); 662117395Skan emit_insn (tmp); 66390075Sobrien 66490075Sobrien if_info->cond_earliest = if_info->jump; 66590075Sobrien 66690075Sobrien return x; 66790075Sobrien } 66890075Sobrien 66990075Sobrien end_sequence (); 67090075Sobrien } 67190075Sobrien 672117395Skan /* Don't even try if the comparison operands or the mode of X are weird. */ 673117395Skan if (cond_complex || !SCALAR_INT_MODE_P (GET_MODE (x))) 67490075Sobrien return NULL_RTX; 67590075Sobrien 67690075Sobrien return emit_store_flag (x, code, XEXP (cond, 0), 67790075Sobrien XEXP (cond, 1), VOIDmode, 67890075Sobrien (code == LTU || code == LEU 67990075Sobrien || code == GEU || code == GTU), normalize); 68090075Sobrien} 68190075Sobrien 682132718Skan/* Emit instruction to move an rtx, possibly into STRICT_LOW_PART. 683132718Skan X is the destination/target and Y is the value to copy. */ 684132718Skan 68590075Sobrienstatic void 686132718Skannoce_emit_move_insn (rtx x, rtx y) 68790075Sobrien{ 688169689Skan enum machine_mode outmode; 68990075Sobrien rtx outer, inner; 69090075Sobrien int bitpos; 69190075Sobrien 69290075Sobrien if (GET_CODE (x) != STRICT_LOW_PART) 69390075Sobrien { 694169689Skan rtx seq, insn, target; 695169689Skan optab ot; 696169689Skan 697169689Skan start_sequence (); 698169689Skan /* Check that the SET_SRC is reasonable before calling emit_move_insn, 699169689Skan otherwise construct a suitable SET pattern ourselves. */ 700169689Skan insn = (OBJECT_P (y) || CONSTANT_P (y) || GET_CODE (y) == SUBREG) 701169689Skan ? emit_move_insn (x, y) 702169689Skan : emit_insn (gen_rtx_SET (VOIDmode, x, y)); 703169689Skan seq = get_insns (); 704169689Skan end_sequence(); 705169689Skan 706169689Skan if (recog_memoized (insn) <= 0) 707169689Skan { 708169689Skan if (GET_CODE (x) == ZERO_EXTRACT) 709169689Skan { 710169689Skan rtx op = XEXP (x, 0); 711169689Skan unsigned HOST_WIDE_INT size = INTVAL (XEXP (x, 1)); 712169689Skan unsigned HOST_WIDE_INT start = INTVAL (XEXP (x, 2)); 713169689Skan 714169689Skan /* store_bit_field expects START to be relative to 715169689Skan BYTES_BIG_ENDIAN and adjusts this value for machines with 716169689Skan BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN. In order to be able to 717169689Skan invoke store_bit_field again it is necessary to have the START 718169689Skan value from the first call. */ 719169689Skan if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN) 720169689Skan { 721169689Skan if (MEM_P (op)) 722169689Skan start = BITS_PER_UNIT - start - size; 723169689Skan else 724169689Skan { 725169689Skan gcc_assert (REG_P (op)); 726169689Skan start = BITS_PER_WORD - start - size; 727169689Skan } 728169689Skan } 729169689Skan 730169689Skan gcc_assert (start < (MEM_P (op) ? BITS_PER_UNIT : BITS_PER_WORD)); 731169689Skan store_bit_field (op, size, start, GET_MODE (x), y); 732169689Skan return; 733169689Skan } 734169689Skan 735169689Skan switch (GET_RTX_CLASS (GET_CODE (y))) 736169689Skan { 737169689Skan case RTX_UNARY: 738169689Skan ot = code_to_optab[GET_CODE (y)]; 739169689Skan if (ot) 740169689Skan { 741169689Skan start_sequence (); 742169689Skan target = expand_unop (GET_MODE (y), ot, XEXP (y, 0), x, 0); 743169689Skan if (target != NULL_RTX) 744169689Skan { 745169689Skan if (target != x) 746169689Skan emit_move_insn (x, target); 747169689Skan seq = get_insns (); 748169689Skan } 749169689Skan end_sequence (); 750169689Skan } 751169689Skan break; 752169689Skan 753169689Skan case RTX_BIN_ARITH: 754169689Skan case RTX_COMM_ARITH: 755169689Skan ot = code_to_optab[GET_CODE (y)]; 756169689Skan if (ot) 757169689Skan { 758169689Skan start_sequence (); 759169689Skan target = expand_binop (GET_MODE (y), ot, 760169689Skan XEXP (y, 0), XEXP (y, 1), 761169689Skan x, 0, OPTAB_DIRECT); 762169689Skan if (target != NULL_RTX) 763169689Skan { 764169689Skan if (target != x) 765169689Skan emit_move_insn (x, target); 766169689Skan seq = get_insns (); 767169689Skan } 768169689Skan end_sequence (); 769169689Skan } 770169689Skan break; 771169689Skan 772169689Skan default: 773169689Skan break; 774169689Skan } 775169689Skan } 776169689Skan 777169689Skan emit_insn (seq); 77890075Sobrien return; 77990075Sobrien } 78090075Sobrien 78190075Sobrien outer = XEXP (x, 0); 78290075Sobrien inner = XEXP (outer, 0); 78390075Sobrien outmode = GET_MODE (outer); 78490075Sobrien bitpos = SUBREG_BYTE (outer) * BITS_PER_UNIT; 785169689Skan store_bit_field (inner, GET_MODE_BITSIZE (outmode), bitpos, outmode, y); 78690075Sobrien} 78790075Sobrien 788169689Skan/* Return sequence of instructions generated by if conversion. This 789169689Skan function calls end_sequence() to end the current stream, ensures 790169689Skan that are instructions are unshared, recognizable non-jump insns. 791169689Skan On failure, this function returns a NULL_RTX. */ 792169689Skan 793169689Skanstatic rtx 794169689Skanend_ifcvt_sequence (struct noce_if_info *if_info) 795132718Skan{ 796169689Skan rtx insn; 797169689Skan rtx seq = get_insns (); 798169689Skan 799132718Skan set_used_flags (if_info->x); 800132718Skan set_used_flags (if_info->cond); 801132718Skan unshare_all_rtl_in_chain (seq); 802169689Skan end_sequence (); 803169689Skan 804169689Skan /* Make sure that all of the instructions emitted are recognizable, 805169689Skan and that we haven't introduced a new jump instruction. 806169689Skan As an exercise for the reader, build a general mechanism that 807169689Skan allows proper placement of required clobbers. */ 808169689Skan for (insn = seq; insn; insn = NEXT_INSN (insn)) 809169689Skan if (JUMP_P (insn) 810169689Skan || recog_memoized (insn) == -1) 811169689Skan return NULL_RTX; 812169689Skan 813169689Skan return seq; 814132718Skan} 815132718Skan 816132718Skan/* Convert "if (a != b) x = a; else x = b" into "x = a" and 817132718Skan "if (a == b) x = a; else x = b" into "x = b". */ 818132718Skan 819132718Skanstatic int 820132718Skannoce_try_move (struct noce_if_info *if_info) 821132718Skan{ 822132718Skan rtx cond = if_info->cond; 823132718Skan enum rtx_code code = GET_CODE (cond); 824132718Skan rtx y, seq; 825132718Skan 826132718Skan if (code != NE && code != EQ) 827132718Skan return FALSE; 828132718Skan 829132718Skan /* This optimization isn't valid if either A or B could be a NaN 830132718Skan or a signed zero. */ 831132718Skan if (HONOR_NANS (GET_MODE (if_info->x)) 832132718Skan || HONOR_SIGNED_ZEROS (GET_MODE (if_info->x))) 833132718Skan return FALSE; 834132718Skan 835132718Skan /* Check whether the operands of the comparison are A and in 836132718Skan either order. */ 837132718Skan if ((rtx_equal_p (if_info->a, XEXP (cond, 0)) 838132718Skan && rtx_equal_p (if_info->b, XEXP (cond, 1))) 839132718Skan || (rtx_equal_p (if_info->a, XEXP (cond, 1)) 840132718Skan && rtx_equal_p (if_info->b, XEXP (cond, 0)))) 841132718Skan { 842132718Skan y = (code == EQ) ? if_info->a : if_info->b; 843132718Skan 844132718Skan /* Avoid generating the move if the source is the destination. */ 845132718Skan if (! rtx_equal_p (if_info->x, y)) 846132718Skan { 847132718Skan start_sequence (); 848132718Skan noce_emit_move_insn (if_info->x, y); 849169689Skan seq = end_ifcvt_sequence (if_info); 850169689Skan if (!seq) 851169689Skan return FALSE; 852132718Skan 853132718Skan emit_insn_before_setloc (seq, if_info->jump, 854132718Skan INSN_LOCATOR (if_info->insn_a)); 855132718Skan } 856132718Skan return TRUE; 857132718Skan } 858132718Skan return FALSE; 859132718Skan} 860132718Skan 86190075Sobrien/* Convert "if (test) x = 1; else x = 0". 86290075Sobrien 86390075Sobrien Only try 0 and STORE_FLAG_VALUE here. Other combinations will be 86490075Sobrien tried in noce_try_store_flag_constants after noce_try_cmove has had 86590075Sobrien a go at the conversion. */ 86690075Sobrien 86790075Sobrienstatic int 868132718Skannoce_try_store_flag (struct noce_if_info *if_info) 86990075Sobrien{ 87090075Sobrien int reversep; 87190075Sobrien rtx target, seq; 87290075Sobrien 87390075Sobrien if (GET_CODE (if_info->b) == CONST_INT 87490075Sobrien && INTVAL (if_info->b) == STORE_FLAG_VALUE 87590075Sobrien && if_info->a == const0_rtx) 87690075Sobrien reversep = 0; 87790075Sobrien else if (if_info->b == const0_rtx 87890075Sobrien && GET_CODE (if_info->a) == CONST_INT 87990075Sobrien && INTVAL (if_info->a) == STORE_FLAG_VALUE 88090075Sobrien && (reversed_comparison_code (if_info->cond, if_info->jump) 88190075Sobrien != UNKNOWN)) 88290075Sobrien reversep = 1; 88390075Sobrien else 88490075Sobrien return FALSE; 88590075Sobrien 88690075Sobrien start_sequence (); 88790075Sobrien 88890075Sobrien target = noce_emit_store_flag (if_info, if_info->x, reversep, 0); 88990075Sobrien if (target) 89090075Sobrien { 89190075Sobrien if (target != if_info->x) 89290075Sobrien noce_emit_move_insn (if_info->x, target); 89390075Sobrien 894169689Skan seq = end_ifcvt_sequence (if_info); 895169689Skan if (! seq) 896169689Skan return FALSE; 89790075Sobrien 898169689Skan emit_insn_before_setloc (seq, if_info->jump, 899169689Skan INSN_LOCATOR (if_info->insn_a)); 90090075Sobrien return TRUE; 90190075Sobrien } 90290075Sobrien else 90390075Sobrien { 90490075Sobrien end_sequence (); 90590075Sobrien return FALSE; 90690075Sobrien } 90790075Sobrien} 90890075Sobrien 90990075Sobrien/* Convert "if (test) x = a; else x = b", for A and B constant. */ 91090075Sobrien 91190075Sobrienstatic int 912132718Skannoce_try_store_flag_constants (struct noce_if_info *if_info) 91390075Sobrien{ 91490075Sobrien rtx target, seq; 91590075Sobrien int reversep; 91690075Sobrien HOST_WIDE_INT itrue, ifalse, diff, tmp; 91790075Sobrien int normalize, can_reverse; 91890075Sobrien enum machine_mode mode; 91990075Sobrien 92090075Sobrien if (! no_new_pseudos 92190075Sobrien && GET_CODE (if_info->a) == CONST_INT 92290075Sobrien && GET_CODE (if_info->b) == CONST_INT) 92390075Sobrien { 92490075Sobrien mode = GET_MODE (if_info->x); 92590075Sobrien ifalse = INTVAL (if_info->a); 92690075Sobrien itrue = INTVAL (if_info->b); 92790075Sobrien 92890075Sobrien /* Make sure we can represent the difference between the two values. */ 92990075Sobrien if ((itrue - ifalse > 0) 93090075Sobrien != ((ifalse < 0) != (itrue < 0) ? ifalse < 0 : ifalse < itrue)) 93190075Sobrien return FALSE; 93290075Sobrien 93390075Sobrien diff = trunc_int_for_mode (itrue - ifalse, mode); 93490075Sobrien 93590075Sobrien can_reverse = (reversed_comparison_code (if_info->cond, if_info->jump) 93690075Sobrien != UNKNOWN); 93790075Sobrien 93890075Sobrien reversep = 0; 93990075Sobrien if (diff == STORE_FLAG_VALUE || diff == -STORE_FLAG_VALUE) 94090075Sobrien normalize = 0; 94190075Sobrien else if (ifalse == 0 && exact_log2 (itrue) >= 0 94290075Sobrien && (STORE_FLAG_VALUE == 1 94390075Sobrien || BRANCH_COST >= 2)) 94490075Sobrien normalize = 1; 94590075Sobrien else if (itrue == 0 && exact_log2 (ifalse) >= 0 && can_reverse 94690075Sobrien && (STORE_FLAG_VALUE == 1 || BRANCH_COST >= 2)) 94790075Sobrien normalize = 1, reversep = 1; 94890075Sobrien else if (itrue == -1 94990075Sobrien && (STORE_FLAG_VALUE == -1 95090075Sobrien || BRANCH_COST >= 2)) 95190075Sobrien normalize = -1; 95290075Sobrien else if (ifalse == -1 && can_reverse 95390075Sobrien && (STORE_FLAG_VALUE == -1 || BRANCH_COST >= 2)) 95490075Sobrien normalize = -1, reversep = 1; 95590075Sobrien else if ((BRANCH_COST >= 2 && STORE_FLAG_VALUE == -1) 95690075Sobrien || BRANCH_COST >= 3) 95790075Sobrien normalize = -1; 95890075Sobrien else 95990075Sobrien return FALSE; 96090075Sobrien 96190075Sobrien if (reversep) 962132718Skan { 96390075Sobrien tmp = itrue; itrue = ifalse; ifalse = tmp; 96490075Sobrien diff = trunc_int_for_mode (-diff, mode); 96590075Sobrien } 96690075Sobrien 96790075Sobrien start_sequence (); 96890075Sobrien target = noce_emit_store_flag (if_info, if_info->x, reversep, normalize); 96990075Sobrien if (! target) 97090075Sobrien { 97190075Sobrien end_sequence (); 97290075Sobrien return FALSE; 97390075Sobrien } 97490075Sobrien 97590075Sobrien /* if (test) x = 3; else x = 4; 97690075Sobrien => x = 3 + (test == 0); */ 97790075Sobrien if (diff == STORE_FLAG_VALUE || diff == -STORE_FLAG_VALUE) 97890075Sobrien { 97990075Sobrien target = expand_simple_binop (mode, 98090075Sobrien (diff == STORE_FLAG_VALUE 98190075Sobrien ? PLUS : MINUS), 98290075Sobrien GEN_INT (ifalse), target, if_info->x, 0, 98390075Sobrien OPTAB_WIDEN); 98490075Sobrien } 98590075Sobrien 98690075Sobrien /* if (test) x = 8; else x = 0; 98790075Sobrien => x = (test != 0) << 3; */ 98890075Sobrien else if (ifalse == 0 && (tmp = exact_log2 (itrue)) >= 0) 98990075Sobrien { 99090075Sobrien target = expand_simple_binop (mode, ASHIFT, 99190075Sobrien target, GEN_INT (tmp), if_info->x, 0, 99290075Sobrien OPTAB_WIDEN); 99390075Sobrien } 99490075Sobrien 99590075Sobrien /* if (test) x = -1; else x = b; 99690075Sobrien => x = -(test != 0) | b; */ 99790075Sobrien else if (itrue == -1) 99890075Sobrien { 99990075Sobrien target = expand_simple_binop (mode, IOR, 100090075Sobrien target, GEN_INT (ifalse), if_info->x, 0, 100190075Sobrien OPTAB_WIDEN); 100290075Sobrien } 100390075Sobrien 100490075Sobrien /* if (test) x = a; else x = b; 100590075Sobrien => x = (-(test != 0) & (b - a)) + a; */ 100690075Sobrien else 100790075Sobrien { 100890075Sobrien target = expand_simple_binop (mode, AND, 100990075Sobrien target, GEN_INT (diff), if_info->x, 0, 101090075Sobrien OPTAB_WIDEN); 101190075Sobrien if (target) 101290075Sobrien target = expand_simple_binop (mode, PLUS, 101390075Sobrien target, GEN_INT (ifalse), 101490075Sobrien if_info->x, 0, OPTAB_WIDEN); 101590075Sobrien } 101690075Sobrien 101790075Sobrien if (! target) 101890075Sobrien { 101990075Sobrien end_sequence (); 102090075Sobrien return FALSE; 102190075Sobrien } 102290075Sobrien 102390075Sobrien if (target != if_info->x) 102490075Sobrien noce_emit_move_insn (if_info->x, target); 102590075Sobrien 1026169689Skan seq = end_ifcvt_sequence (if_info); 1027169689Skan if (!seq) 102890075Sobrien return FALSE; 102990075Sobrien 1030169689Skan emit_insn_before_setloc (seq, if_info->jump, 1031169689Skan INSN_LOCATOR (if_info->insn_a)); 103290075Sobrien return TRUE; 103390075Sobrien } 103490075Sobrien 103590075Sobrien return FALSE; 103690075Sobrien} 103790075Sobrien 1038132718Skan/* Convert "if (test) foo++" into "foo += (test != 0)", and 103990075Sobrien similarly for "foo--". */ 104090075Sobrien 104190075Sobrienstatic int 1042132718Skannoce_try_addcc (struct noce_if_info *if_info) 104390075Sobrien{ 104490075Sobrien rtx target, seq; 104590075Sobrien int subtract, normalize; 104690075Sobrien 104790075Sobrien if (! no_new_pseudos 104890075Sobrien && GET_CODE (if_info->a) == PLUS 1049132718Skan && rtx_equal_p (XEXP (if_info->a, 0), if_info->b) 105090075Sobrien && (reversed_comparison_code (if_info->cond, if_info->jump) 105190075Sobrien != UNKNOWN)) 105290075Sobrien { 1053132718Skan rtx cond = if_info->cond; 1054132718Skan enum rtx_code code = reversed_comparison_code (cond, if_info->jump); 105590075Sobrien 1056132718Skan /* First try to use addcc pattern. */ 1057132718Skan if (general_operand (XEXP (cond, 0), VOIDmode) 1058132718Skan && general_operand (XEXP (cond, 1), VOIDmode)) 105990075Sobrien { 1060132718Skan start_sequence (); 1061132718Skan target = emit_conditional_add (if_info->x, code, 1062132718Skan XEXP (cond, 0), 1063132718Skan XEXP (cond, 1), 1064132718Skan VOIDmode, 1065132718Skan if_info->b, 1066132718Skan XEXP (if_info->a, 1), 1067132718Skan GET_MODE (if_info->x), 1068132718Skan (code == LTU || code == GEU 1069132718Skan || code == LEU || code == GTU)); 1070132718Skan if (target) 1071132718Skan { 1072132718Skan if (target != if_info->x) 1073132718Skan noce_emit_move_insn (if_info->x, target); 107490075Sobrien 1075169689Skan seq = end_ifcvt_sequence (if_info); 1076169689Skan if (!seq) 1077169689Skan return FALSE; 1078169689Skan 1079132718Skan emit_insn_before_setloc (seq, if_info->jump, 1080169689Skan INSN_LOCATOR (if_info->insn_a)); 1081132718Skan return TRUE; 1082132718Skan } 108390075Sobrien end_sequence (); 1084132718Skan } 108590075Sobrien 1086132718Skan /* If that fails, construct conditional increment or decrement using 1087132718Skan setcc. */ 1088132718Skan if (BRANCH_COST >= 2 1089132718Skan && (XEXP (if_info->a, 1) == const1_rtx 1090132718Skan || XEXP (if_info->a, 1) == constm1_rtx)) 1091132718Skan { 1092132718Skan start_sequence (); 1093132718Skan if (STORE_FLAG_VALUE == INTVAL (XEXP (if_info->a, 1))) 1094132718Skan subtract = 0, normalize = 0; 1095132718Skan else if (-STORE_FLAG_VALUE == INTVAL (XEXP (if_info->a, 1))) 1096132718Skan subtract = 1, normalize = 0; 1097132718Skan else 1098132718Skan subtract = 0, normalize = INTVAL (XEXP (if_info->a, 1)); 109990075Sobrien 110090075Sobrien 1101132718Skan target = noce_emit_store_flag (if_info, 1102132718Skan gen_reg_rtx (GET_MODE (if_info->x)), 1103132718Skan 1, normalize); 1104132718Skan 1105132718Skan if (target) 1106132718Skan target = expand_simple_binop (GET_MODE (if_info->x), 1107132718Skan subtract ? MINUS : PLUS, 1108132718Skan if_info->b, target, if_info->x, 1109132718Skan 0, OPTAB_WIDEN); 1110132718Skan if (target) 1111132718Skan { 1112132718Skan if (target != if_info->x) 1113132718Skan noce_emit_move_insn (if_info->x, target); 1114132718Skan 1115169689Skan seq = end_ifcvt_sequence (if_info); 1116169689Skan if (!seq) 1117132718Skan return FALSE; 1118132718Skan 1119132718Skan emit_insn_before_setloc (seq, if_info->jump, 1120169689Skan INSN_LOCATOR (if_info->insn_a)); 1121132718Skan return TRUE; 1122132718Skan } 1123132718Skan end_sequence (); 112490075Sobrien } 112590075Sobrien } 112690075Sobrien 112790075Sobrien return FALSE; 112890075Sobrien} 112990075Sobrien 113090075Sobrien/* Convert "if (test) x = 0;" to "x &= -(test == 0);" */ 113190075Sobrien 113290075Sobrienstatic int 1133132718Skannoce_try_store_flag_mask (struct noce_if_info *if_info) 113490075Sobrien{ 113590075Sobrien rtx target, seq; 113690075Sobrien int reversep; 113790075Sobrien 113890075Sobrien reversep = 0; 113990075Sobrien if (! no_new_pseudos 114090075Sobrien && (BRANCH_COST >= 2 114190075Sobrien || STORE_FLAG_VALUE == -1) 114290075Sobrien && ((if_info->a == const0_rtx 114390075Sobrien && rtx_equal_p (if_info->b, if_info->x)) 114490075Sobrien || ((reversep = (reversed_comparison_code (if_info->cond, 114590075Sobrien if_info->jump) 114690075Sobrien != UNKNOWN)) 114790075Sobrien && if_info->b == const0_rtx 114890075Sobrien && rtx_equal_p (if_info->a, if_info->x)))) 114990075Sobrien { 115090075Sobrien start_sequence (); 115190075Sobrien target = noce_emit_store_flag (if_info, 115290075Sobrien gen_reg_rtx (GET_MODE (if_info->x)), 115390075Sobrien reversep, -1); 115490075Sobrien if (target) 115590075Sobrien target = expand_simple_binop (GET_MODE (if_info->x), AND, 1156132718Skan if_info->x, 1157132718Skan target, if_info->x, 0, 115890075Sobrien OPTAB_WIDEN); 115990075Sobrien 116090075Sobrien if (target) 116190075Sobrien { 116290075Sobrien if (target != if_info->x) 116390075Sobrien noce_emit_move_insn (if_info->x, target); 116490075Sobrien 1165169689Skan seq = end_ifcvt_sequence (if_info); 1166169689Skan if (!seq) 116790075Sobrien return FALSE; 116890075Sobrien 1169132718Skan emit_insn_before_setloc (seq, if_info->jump, 1170169689Skan INSN_LOCATOR (if_info->insn_a)); 117190075Sobrien return TRUE; 117290075Sobrien } 117390075Sobrien 117490075Sobrien end_sequence (); 117590075Sobrien } 117690075Sobrien 117790075Sobrien return FALSE; 117890075Sobrien} 117990075Sobrien 118090075Sobrien/* Helper function for noce_try_cmove and noce_try_cmove_arith. */ 118190075Sobrien 118290075Sobrienstatic rtx 1183132718Skannoce_emit_cmove (struct noce_if_info *if_info, rtx x, enum rtx_code code, 1184132718Skan rtx cmp_a, rtx cmp_b, rtx vfalse, rtx vtrue) 118590075Sobrien{ 118690075Sobrien /* If earliest == jump, try to build the cmove insn directly. 118790075Sobrien This is helpful when combine has created some complex condition 118890075Sobrien (like for alpha's cmovlbs) that we can't hope to regenerate 118990075Sobrien through the normal interface. */ 119090075Sobrien 119190075Sobrien if (if_info->cond_earliest == if_info->jump) 119290075Sobrien { 119390075Sobrien rtx tmp; 119490075Sobrien 119590075Sobrien tmp = gen_rtx_fmt_ee (code, GET_MODE (if_info->cond), cmp_a, cmp_b); 119690075Sobrien tmp = gen_rtx_IF_THEN_ELSE (GET_MODE (x), tmp, vtrue, vfalse); 119790075Sobrien tmp = gen_rtx_SET (VOIDmode, x, tmp); 119890075Sobrien 119990075Sobrien start_sequence (); 120090075Sobrien tmp = emit_insn (tmp); 120190075Sobrien 120290075Sobrien if (recog_memoized (tmp) >= 0) 120390075Sobrien { 120490075Sobrien tmp = get_insns (); 120590075Sobrien end_sequence (); 1206117395Skan emit_insn (tmp); 120790075Sobrien 120890075Sobrien return x; 120990075Sobrien } 121090075Sobrien 121190075Sobrien end_sequence (); 121290075Sobrien } 121390075Sobrien 121490075Sobrien /* Don't even try if the comparison operands are weird. */ 121590075Sobrien if (! general_operand (cmp_a, GET_MODE (cmp_a)) 121690075Sobrien || ! general_operand (cmp_b, GET_MODE (cmp_b))) 121790075Sobrien return NULL_RTX; 121890075Sobrien 121990075Sobrien#if HAVE_conditional_move 122090075Sobrien return emit_conditional_move (x, code, cmp_a, cmp_b, VOIDmode, 122190075Sobrien vtrue, vfalse, GET_MODE (x), 122290075Sobrien (code == LTU || code == GEU 122390075Sobrien || code == LEU || code == GTU)); 122490075Sobrien#else 122590075Sobrien /* We'll never get here, as noce_process_if_block doesn't call the 122690075Sobrien functions involved. Ifdef code, however, should be discouraged 1227132718Skan because it leads to typos in the code not selected. However, 122890075Sobrien emit_conditional_move won't exist either. */ 122990075Sobrien return NULL_RTX; 123090075Sobrien#endif 123190075Sobrien} 123290075Sobrien 123390075Sobrien/* Try only simple constants and registers here. More complex cases 123490075Sobrien are handled in noce_try_cmove_arith after noce_try_store_flag_arith 123590075Sobrien has had a go at it. */ 123690075Sobrien 123790075Sobrienstatic int 1238132718Skannoce_try_cmove (struct noce_if_info *if_info) 123990075Sobrien{ 124090075Sobrien enum rtx_code code; 124190075Sobrien rtx target, seq; 124290075Sobrien 124390075Sobrien if ((CONSTANT_P (if_info->a) || register_operand (if_info->a, VOIDmode)) 124490075Sobrien && (CONSTANT_P (if_info->b) || register_operand (if_info->b, VOIDmode))) 124590075Sobrien { 124690075Sobrien start_sequence (); 124790075Sobrien 124890075Sobrien code = GET_CODE (if_info->cond); 124990075Sobrien target = noce_emit_cmove (if_info, if_info->x, code, 125090075Sobrien XEXP (if_info->cond, 0), 125190075Sobrien XEXP (if_info->cond, 1), 125290075Sobrien if_info->a, if_info->b); 125390075Sobrien 125490075Sobrien if (target) 125590075Sobrien { 125690075Sobrien if (target != if_info->x) 125790075Sobrien noce_emit_move_insn (if_info->x, target); 125890075Sobrien 1259169689Skan seq = end_ifcvt_sequence (if_info); 1260169689Skan if (!seq) 1261169689Skan return FALSE; 1262169689Skan 1263132718Skan emit_insn_before_setloc (seq, if_info->jump, 1264169689Skan INSN_LOCATOR (if_info->insn_a)); 126590075Sobrien return TRUE; 126690075Sobrien } 126790075Sobrien else 126890075Sobrien { 126990075Sobrien end_sequence (); 127090075Sobrien return FALSE; 127190075Sobrien } 127290075Sobrien } 127390075Sobrien 127490075Sobrien return FALSE; 127590075Sobrien} 127690075Sobrien 127790075Sobrien/* Try more complex cases involving conditional_move. */ 127890075Sobrien 127990075Sobrienstatic int 1280132718Skannoce_try_cmove_arith (struct noce_if_info *if_info) 128190075Sobrien{ 128290075Sobrien rtx a = if_info->a; 128390075Sobrien rtx b = if_info->b; 128490075Sobrien rtx x = if_info->x; 1285146895Skan rtx orig_a, orig_b; 128690075Sobrien rtx insn_a, insn_b; 128790075Sobrien rtx tmp, target; 128890075Sobrien int is_mem = 0; 1289169689Skan int insn_cost; 129090075Sobrien enum rtx_code code; 129190075Sobrien 129290075Sobrien /* A conditional move from two memory sources is equivalent to a 129390075Sobrien conditional on their addresses followed by a load. Don't do this 129490075Sobrien early because it'll screw alias analysis. Note that we've 129590075Sobrien already checked for no side effects. */ 129690075Sobrien if (! no_new_pseudos && cse_not_expected 1297169689Skan && MEM_P (a) && MEM_P (b) 129890075Sobrien && BRANCH_COST >= 5) 129990075Sobrien { 130090075Sobrien a = XEXP (a, 0); 130190075Sobrien b = XEXP (b, 0); 130290075Sobrien x = gen_reg_rtx (Pmode); 130390075Sobrien is_mem = 1; 130490075Sobrien } 130590075Sobrien 130690075Sobrien /* ??? We could handle this if we knew that a load from A or B could 130790075Sobrien not fault. This is also true if we've already loaded 130890075Sobrien from the address along the path from ENTRY. */ 130990075Sobrien else if (may_trap_p (a) || may_trap_p (b)) 131090075Sobrien return FALSE; 131190075Sobrien 131290075Sobrien /* if (test) x = a + b; else x = c - d; 131390075Sobrien => y = a + b; 131490075Sobrien x = c - d; 131590075Sobrien if (test) 131690075Sobrien x = y; 131790075Sobrien */ 1318132718Skan 131990075Sobrien code = GET_CODE (if_info->cond); 132090075Sobrien insn_a = if_info->insn_a; 132190075Sobrien insn_b = if_info->insn_b; 132290075Sobrien 1323169689Skan /* Total insn_rtx_cost should be smaller than branch cost. Exit 1324169689Skan if insn_rtx_cost can't be estimated. */ 1325169689Skan if (insn_a) 1326169689Skan { 1327169689Skan insn_cost = insn_rtx_cost (PATTERN (insn_a)); 1328169689Skan if (insn_cost == 0 || insn_cost > COSTS_N_INSNS (BRANCH_COST)) 1329169689Skan return FALSE; 1330169689Skan } 1331169689Skan else 1332169689Skan { 1333169689Skan insn_cost = 0; 1334169689Skan } 1335169689Skan 1336169689Skan if (insn_b) { 1337169689Skan insn_cost += insn_rtx_cost (PATTERN (insn_b)); 1338169689Skan if (insn_cost == 0 || insn_cost > COSTS_N_INSNS (BRANCH_COST)) 1339169689Skan return FALSE; 1340169689Skan } 1341169689Skan 134290075Sobrien /* Possibly rearrange operands to make things come out more natural. */ 134390075Sobrien if (reversed_comparison_code (if_info->cond, if_info->jump) != UNKNOWN) 134490075Sobrien { 134590075Sobrien int reversep = 0; 134690075Sobrien if (rtx_equal_p (b, x)) 134790075Sobrien reversep = 1; 134890075Sobrien else if (general_operand (b, GET_MODE (b))) 134990075Sobrien reversep = 1; 135090075Sobrien 135190075Sobrien if (reversep) 135290075Sobrien { 135390075Sobrien code = reversed_comparison_code (if_info->cond, if_info->jump); 135490075Sobrien tmp = a, a = b, b = tmp; 135590075Sobrien tmp = insn_a, insn_a = insn_b, insn_b = tmp; 135690075Sobrien } 135790075Sobrien } 135890075Sobrien 135990075Sobrien start_sequence (); 136090075Sobrien 1361146895Skan orig_a = a; 1362146895Skan orig_b = b; 1363146895Skan 136490075Sobrien /* If either operand is complex, load it into a register first. 136590075Sobrien The best way to do this is to copy the original insn. In this 1366132718Skan way we preserve any clobbers etc that the insn may have had. 136790075Sobrien This is of course not possible in the IS_MEM case. */ 136890075Sobrien if (! general_operand (a, GET_MODE (a))) 136990075Sobrien { 137090075Sobrien rtx set; 137190075Sobrien 137290075Sobrien if (no_new_pseudos) 137390075Sobrien goto end_seq_and_fail; 137490075Sobrien 137590075Sobrien if (is_mem) 137690075Sobrien { 137790075Sobrien tmp = gen_reg_rtx (GET_MODE (a)); 137890075Sobrien tmp = emit_insn (gen_rtx_SET (VOIDmode, tmp, a)); 137990075Sobrien } 138090075Sobrien else if (! insn_a) 138190075Sobrien goto end_seq_and_fail; 138290075Sobrien else 138390075Sobrien { 138490075Sobrien a = gen_reg_rtx (GET_MODE (a)); 138590075Sobrien tmp = copy_rtx (insn_a); 138690075Sobrien set = single_set (tmp); 138790075Sobrien SET_DEST (set) = a; 138890075Sobrien tmp = emit_insn (PATTERN (tmp)); 138990075Sobrien } 139090075Sobrien if (recog_memoized (tmp) < 0) 139190075Sobrien goto end_seq_and_fail; 139290075Sobrien } 139390075Sobrien if (! general_operand (b, GET_MODE (b))) 139490075Sobrien { 1395146895Skan rtx set, last; 139690075Sobrien 139790075Sobrien if (no_new_pseudos) 139890075Sobrien goto end_seq_and_fail; 139990075Sobrien 140090075Sobrien if (is_mem) 140190075Sobrien { 140290075Sobrien tmp = gen_reg_rtx (GET_MODE (b)); 1403146895Skan tmp = gen_rtx_SET (VOIDmode, tmp, b); 140490075Sobrien } 1405132718Skan else if (! insn_b) 140690075Sobrien goto end_seq_and_fail; 140790075Sobrien else 140890075Sobrien { 140990075Sobrien b = gen_reg_rtx (GET_MODE (b)); 141090075Sobrien tmp = copy_rtx (insn_b); 141190075Sobrien set = single_set (tmp); 141290075Sobrien SET_DEST (set) = b; 1413146895Skan tmp = PATTERN (tmp); 141490075Sobrien } 1415146895Skan 1416146895Skan /* If insn to set up A clobbers any registers B depends on, try to 1417146895Skan swap insn that sets up A with the one that sets up B. If even 1418146895Skan that doesn't help, punt. */ 1419146895Skan last = get_last_insn (); 1420146895Skan if (last && modified_in_p (orig_b, last)) 1421146895Skan { 1422146895Skan tmp = emit_insn_before (tmp, get_insns ()); 1423146895Skan if (modified_in_p (orig_a, tmp)) 1424146895Skan goto end_seq_and_fail; 1425146895Skan } 1426146895Skan else 1427146895Skan tmp = emit_insn (tmp); 1428146895Skan 142990075Sobrien if (recog_memoized (tmp) < 0) 143090075Sobrien goto end_seq_and_fail; 143190075Sobrien } 143290075Sobrien 143390075Sobrien target = noce_emit_cmove (if_info, x, code, XEXP (if_info->cond, 0), 143490075Sobrien XEXP (if_info->cond, 1), a, b); 143590075Sobrien 143690075Sobrien if (! target) 143790075Sobrien goto end_seq_and_fail; 143890075Sobrien 143990075Sobrien /* If we're handling a memory for above, emit the load now. */ 144090075Sobrien if (is_mem) 144190075Sobrien { 144290075Sobrien tmp = gen_rtx_MEM (GET_MODE (if_info->x), target); 144390075Sobrien 144490075Sobrien /* Copy over flags as appropriate. */ 144590075Sobrien if (MEM_VOLATILE_P (if_info->a) || MEM_VOLATILE_P (if_info->b)) 144690075Sobrien MEM_VOLATILE_P (tmp) = 1; 144790075Sobrien if (MEM_IN_STRUCT_P (if_info->a) && MEM_IN_STRUCT_P (if_info->b)) 144890075Sobrien MEM_IN_STRUCT_P (tmp) = 1; 144990075Sobrien if (MEM_SCALAR_P (if_info->a) && MEM_SCALAR_P (if_info->b)) 145090075Sobrien MEM_SCALAR_P (tmp) = 1; 145190075Sobrien if (MEM_ALIAS_SET (if_info->a) == MEM_ALIAS_SET (if_info->b)) 145290075Sobrien set_mem_alias_set (tmp, MEM_ALIAS_SET (if_info->a)); 145390075Sobrien set_mem_align (tmp, 145490075Sobrien MIN (MEM_ALIGN (if_info->a), MEM_ALIGN (if_info->b))); 145590075Sobrien 145690075Sobrien noce_emit_move_insn (if_info->x, tmp); 145790075Sobrien } 145890075Sobrien else if (target != x) 145990075Sobrien noce_emit_move_insn (x, target); 146090075Sobrien 1461169689Skan tmp = end_ifcvt_sequence (if_info); 1462169689Skan if (!tmp) 1463169689Skan return FALSE; 1464169689Skan 1465132718Skan emit_insn_before_setloc (tmp, if_info->jump, INSN_LOCATOR (if_info->insn_a)); 146690075Sobrien return TRUE; 146790075Sobrien 146890075Sobrien end_seq_and_fail: 146990075Sobrien end_sequence (); 147090075Sobrien return FALSE; 147190075Sobrien} 147290075Sobrien 147390075Sobrien/* For most cases, the simplified condition we found is the best 147490075Sobrien choice, but this is not the case for the min/max/abs transforms. 147590075Sobrien For these we wish to know that it is A or B in the condition. */ 147690075Sobrien 147790075Sobrienstatic rtx 1478132718Skannoce_get_alt_condition (struct noce_if_info *if_info, rtx target, 1479132718Skan rtx *earliest) 148090075Sobrien{ 148190075Sobrien rtx cond, set, insn; 148290075Sobrien int reverse; 148390075Sobrien 148490075Sobrien /* If target is already mentioned in the known condition, return it. */ 148590075Sobrien if (reg_mentioned_p (target, if_info->cond)) 148690075Sobrien { 148790075Sobrien *earliest = if_info->cond_earliest; 148890075Sobrien return if_info->cond; 148990075Sobrien } 149090075Sobrien 149190075Sobrien set = pc_set (if_info->jump); 149290075Sobrien cond = XEXP (SET_SRC (set), 0); 149390075Sobrien reverse 149490075Sobrien = GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF 149590075Sobrien && XEXP (XEXP (SET_SRC (set), 2), 0) == JUMP_LABEL (if_info->jump); 149690075Sobrien 149790075Sobrien /* If we're looking for a constant, try to make the conditional 149890075Sobrien have that constant in it. There are two reasons why it may 149990075Sobrien not have the constant we want: 150090075Sobrien 150190075Sobrien 1. GCC may have needed to put the constant in a register, because 150290075Sobrien the target can't compare directly against that constant. For 150390075Sobrien this case, we look for a SET immediately before the comparison 150490075Sobrien that puts a constant in that register. 150590075Sobrien 150690075Sobrien 2. GCC may have canonicalized the conditional, for example 150790075Sobrien replacing "if x < 4" with "if x <= 3". We can undo that (or 150890075Sobrien make equivalent types of changes) to get the constants we need 150990075Sobrien if they're off by one in the right direction. */ 151090075Sobrien 151190075Sobrien if (GET_CODE (target) == CONST_INT) 151290075Sobrien { 151390075Sobrien enum rtx_code code = GET_CODE (if_info->cond); 151490075Sobrien rtx op_a = XEXP (if_info->cond, 0); 151590075Sobrien rtx op_b = XEXP (if_info->cond, 1); 151690075Sobrien rtx prev_insn; 151790075Sobrien 151890075Sobrien /* First, look to see if we put a constant in a register. */ 1519169689Skan prev_insn = prev_nonnote_insn (if_info->cond_earliest); 152090075Sobrien if (prev_insn 152190075Sobrien && INSN_P (prev_insn) 152290075Sobrien && GET_CODE (PATTERN (prev_insn)) == SET) 152390075Sobrien { 152490075Sobrien rtx src = find_reg_equal_equiv_note (prev_insn); 152590075Sobrien if (!src) 152690075Sobrien src = SET_SRC (PATTERN (prev_insn)); 152790075Sobrien if (GET_CODE (src) == CONST_INT) 152890075Sobrien { 152990075Sobrien if (rtx_equal_p (op_a, SET_DEST (PATTERN (prev_insn)))) 153090075Sobrien op_a = src; 153190075Sobrien else if (rtx_equal_p (op_b, SET_DEST (PATTERN (prev_insn)))) 153290075Sobrien op_b = src; 153390075Sobrien 153490075Sobrien if (GET_CODE (op_a) == CONST_INT) 153590075Sobrien { 153690075Sobrien rtx tmp = op_a; 153790075Sobrien op_a = op_b; 153890075Sobrien op_b = tmp; 153990075Sobrien code = swap_condition (code); 154090075Sobrien } 154190075Sobrien } 154290075Sobrien } 154390075Sobrien 154490075Sobrien /* Now, look to see if we can get the right constant by 154590075Sobrien adjusting the conditional. */ 154690075Sobrien if (GET_CODE (op_b) == CONST_INT) 154790075Sobrien { 154890075Sobrien HOST_WIDE_INT desired_val = INTVAL (target); 154990075Sobrien HOST_WIDE_INT actual_val = INTVAL (op_b); 155090075Sobrien 155190075Sobrien switch (code) 155290075Sobrien { 155390075Sobrien case LT: 155490075Sobrien if (actual_val == desired_val + 1) 155590075Sobrien { 155690075Sobrien code = LE; 155790075Sobrien op_b = GEN_INT (desired_val); 155890075Sobrien } 155990075Sobrien break; 156090075Sobrien case LE: 156190075Sobrien if (actual_val == desired_val - 1) 156290075Sobrien { 156390075Sobrien code = LT; 156490075Sobrien op_b = GEN_INT (desired_val); 156590075Sobrien } 156690075Sobrien break; 156790075Sobrien case GT: 156890075Sobrien if (actual_val == desired_val - 1) 156990075Sobrien { 157090075Sobrien code = GE; 157190075Sobrien op_b = GEN_INT (desired_val); 157290075Sobrien } 157390075Sobrien break; 157490075Sobrien case GE: 157590075Sobrien if (actual_val == desired_val + 1) 157690075Sobrien { 157790075Sobrien code = GT; 157890075Sobrien op_b = GEN_INT (desired_val); 157990075Sobrien } 158090075Sobrien break; 158190075Sobrien default: 158290075Sobrien break; 158390075Sobrien } 158490075Sobrien } 158590075Sobrien 158690075Sobrien /* If we made any changes, generate a new conditional that is 158790075Sobrien equivalent to what we started with, but has the right 158890075Sobrien constants in it. */ 158990075Sobrien if (code != GET_CODE (if_info->cond) 159090075Sobrien || op_a != XEXP (if_info->cond, 0) 159190075Sobrien || op_b != XEXP (if_info->cond, 1)) 159290075Sobrien { 159390075Sobrien cond = gen_rtx_fmt_ee (code, GET_MODE (cond), op_a, op_b); 159490075Sobrien *earliest = if_info->cond_earliest; 159590075Sobrien return cond; 159690075Sobrien } 159790075Sobrien } 159890075Sobrien 159990075Sobrien cond = canonicalize_condition (if_info->jump, cond, reverse, 1600169689Skan earliest, target, false, true); 160190075Sobrien if (! cond || ! reg_mentioned_p (target, cond)) 160290075Sobrien return NULL; 160390075Sobrien 160490075Sobrien /* We almost certainly searched back to a different place. 160590075Sobrien Need to re-verify correct lifetimes. */ 160690075Sobrien 160790075Sobrien /* X may not be mentioned in the range (cond_earliest, jump]. */ 160890075Sobrien for (insn = if_info->jump; insn != *earliest; insn = PREV_INSN (insn)) 1609117395Skan if (INSN_P (insn) && reg_overlap_mentioned_p (if_info->x, PATTERN (insn))) 161090075Sobrien return NULL; 161190075Sobrien 161290075Sobrien /* A and B may not be modified in the range [cond_earliest, jump). */ 161390075Sobrien for (insn = *earliest; insn != if_info->jump; insn = NEXT_INSN (insn)) 161490075Sobrien if (INSN_P (insn) 161590075Sobrien && (modified_in_p (if_info->a, insn) 161690075Sobrien || modified_in_p (if_info->b, insn))) 161790075Sobrien return NULL; 161890075Sobrien 161990075Sobrien return cond; 162090075Sobrien} 162190075Sobrien 162290075Sobrien/* Convert "if (a < b) x = a; else x = b;" to "x = min(a, b);", etc. */ 162390075Sobrien 162490075Sobrienstatic int 1625132718Skannoce_try_minmax (struct noce_if_info *if_info) 1626132718Skan{ 162790075Sobrien rtx cond, earliest, target, seq; 162890075Sobrien enum rtx_code code, op; 162990075Sobrien int unsignedp; 163090075Sobrien 163190075Sobrien /* ??? Can't guarantee that expand_binop won't create pseudos. */ 163290075Sobrien if (no_new_pseudos) 163390075Sobrien return FALSE; 163490075Sobrien 1635117395Skan /* ??? Reject modes with NaNs or signed zeros since we don't know how 1636117395Skan they will be resolved with an SMIN/SMAX. It wouldn't be too hard 163790075Sobrien to get the target to tell us... */ 1638117395Skan if (HONOR_SIGNED_ZEROS (GET_MODE (if_info->x)) 1639117395Skan || HONOR_NANS (GET_MODE (if_info->x))) 164090075Sobrien return FALSE; 164190075Sobrien 164290075Sobrien cond = noce_get_alt_condition (if_info, if_info->a, &earliest); 164390075Sobrien if (!cond) 164490075Sobrien return FALSE; 164590075Sobrien 164690075Sobrien /* Verify the condition is of the form we expect, and canonicalize 164790075Sobrien the comparison code. */ 164890075Sobrien code = GET_CODE (cond); 164990075Sobrien if (rtx_equal_p (XEXP (cond, 0), if_info->a)) 165090075Sobrien { 165190075Sobrien if (! rtx_equal_p (XEXP (cond, 1), if_info->b)) 165290075Sobrien return FALSE; 165390075Sobrien } 165490075Sobrien else if (rtx_equal_p (XEXP (cond, 1), if_info->a)) 165590075Sobrien { 165690075Sobrien if (! rtx_equal_p (XEXP (cond, 0), if_info->b)) 165790075Sobrien return FALSE; 165890075Sobrien code = swap_condition (code); 165990075Sobrien } 166090075Sobrien else 166190075Sobrien return FALSE; 166290075Sobrien 166390075Sobrien /* Determine what sort of operation this is. Note that the code is for 166490075Sobrien a taken branch, so the code->operation mapping appears backwards. */ 166590075Sobrien switch (code) 166690075Sobrien { 166790075Sobrien case LT: 166890075Sobrien case LE: 166990075Sobrien case UNLT: 167090075Sobrien case UNLE: 167190075Sobrien op = SMAX; 167290075Sobrien unsignedp = 0; 167390075Sobrien break; 167490075Sobrien case GT: 167590075Sobrien case GE: 167690075Sobrien case UNGT: 167790075Sobrien case UNGE: 167890075Sobrien op = SMIN; 167990075Sobrien unsignedp = 0; 168090075Sobrien break; 168190075Sobrien case LTU: 168290075Sobrien case LEU: 168390075Sobrien op = UMAX; 168490075Sobrien unsignedp = 1; 168590075Sobrien break; 168690075Sobrien case GTU: 168790075Sobrien case GEU: 168890075Sobrien op = UMIN; 168990075Sobrien unsignedp = 1; 169090075Sobrien break; 169190075Sobrien default: 169290075Sobrien return FALSE; 169390075Sobrien } 169490075Sobrien 169590075Sobrien start_sequence (); 169690075Sobrien 169790075Sobrien target = expand_simple_binop (GET_MODE (if_info->x), op, 169890075Sobrien if_info->a, if_info->b, 169990075Sobrien if_info->x, unsignedp, OPTAB_WIDEN); 170090075Sobrien if (! target) 170190075Sobrien { 170290075Sobrien end_sequence (); 170390075Sobrien return FALSE; 170490075Sobrien } 170590075Sobrien if (target != if_info->x) 170690075Sobrien noce_emit_move_insn (if_info->x, target); 170790075Sobrien 1708169689Skan seq = end_ifcvt_sequence (if_info); 1709169689Skan if (!seq) 171090075Sobrien return FALSE; 171190075Sobrien 1712132718Skan emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATOR (if_info->insn_a)); 171390075Sobrien if_info->cond = cond; 171490075Sobrien if_info->cond_earliest = earliest; 171590075Sobrien 171690075Sobrien return TRUE; 171790075Sobrien} 171890075Sobrien 171990075Sobrien/* Convert "if (a < 0) x = -a; else x = a;" to "x = abs(a);", etc. */ 172090075Sobrien 172190075Sobrienstatic int 1722132718Skannoce_try_abs (struct noce_if_info *if_info) 1723132718Skan{ 172490075Sobrien rtx cond, earliest, target, seq, a, b, c; 172590075Sobrien int negate; 172690075Sobrien 172790075Sobrien /* ??? Can't guarantee that expand_binop won't create pseudos. */ 172890075Sobrien if (no_new_pseudos) 172990075Sobrien return FALSE; 173090075Sobrien 1731169689Skan /* Recognize A and B as constituting an ABS or NABS. The canonical 1732169689Skan form is a branch around the negation, taken when the object is the 1733169689Skan first operand of a comparison against 0 that evaluates to true. */ 173490075Sobrien a = if_info->a; 173590075Sobrien b = if_info->b; 173690075Sobrien if (GET_CODE (a) == NEG && rtx_equal_p (XEXP (a, 0), b)) 173790075Sobrien negate = 0; 173890075Sobrien else if (GET_CODE (b) == NEG && rtx_equal_p (XEXP (b, 0), a)) 173990075Sobrien { 174090075Sobrien c = a; a = b; b = c; 174190075Sobrien negate = 1; 174290075Sobrien } 174390075Sobrien else 174490075Sobrien return FALSE; 1745132718Skan 174690075Sobrien cond = noce_get_alt_condition (if_info, b, &earliest); 174790075Sobrien if (!cond) 174890075Sobrien return FALSE; 174990075Sobrien 175090075Sobrien /* Verify the condition is of the form we expect. */ 175190075Sobrien if (rtx_equal_p (XEXP (cond, 0), b)) 175290075Sobrien c = XEXP (cond, 1); 175390075Sobrien else if (rtx_equal_p (XEXP (cond, 1), b)) 1754169689Skan { 1755169689Skan c = XEXP (cond, 0); 1756169689Skan negate = !negate; 1757169689Skan } 175890075Sobrien else 175990075Sobrien return FALSE; 176090075Sobrien 1761169689Skan /* Verify that C is zero. Search one step backward for a 1762169689Skan REG_EQUAL note or a simple source if necessary. */ 176390075Sobrien if (REG_P (c)) 176490075Sobrien { 1765169689Skan rtx set, insn = prev_nonnote_insn (earliest); 1766169689Skan if (insn 1767169689Skan && (set = single_set (insn)) 1768169689Skan && rtx_equal_p (SET_DEST (set), c)) 1769169689Skan { 1770169689Skan rtx note = find_reg_equal_equiv_note (insn); 1771169689Skan if (note) 1772169689Skan c = XEXP (note, 0); 1773169689Skan else 1774169689Skan c = SET_SRC (set); 1775169689Skan } 1776169689Skan else 177790075Sobrien return FALSE; 177890075Sobrien } 1779169689Skan if (MEM_P (c) 178090075Sobrien && GET_CODE (XEXP (c, 0)) == SYMBOL_REF 178190075Sobrien && CONSTANT_POOL_ADDRESS_P (XEXP (c, 0))) 178290075Sobrien c = get_pool_constant (XEXP (c, 0)); 178390075Sobrien 178490075Sobrien /* Work around funny ideas get_condition has wrt canonicalization. 1785132718Skan Note that these rtx constants are known to be CONST_INT, and 178690075Sobrien therefore imply integer comparisons. */ 178790075Sobrien if (c == constm1_rtx && GET_CODE (cond) == GT) 178890075Sobrien ; 178990075Sobrien else if (c == const1_rtx && GET_CODE (cond) == LT) 179090075Sobrien ; 179190075Sobrien else if (c != CONST0_RTX (GET_MODE (b))) 179290075Sobrien return FALSE; 179390075Sobrien 179490075Sobrien /* Determine what sort of operation this is. */ 179590075Sobrien switch (GET_CODE (cond)) 179690075Sobrien { 179790075Sobrien case LT: 179890075Sobrien case LE: 179990075Sobrien case UNLT: 180090075Sobrien case UNLE: 180190075Sobrien negate = !negate; 180290075Sobrien break; 180390075Sobrien case GT: 180490075Sobrien case GE: 180590075Sobrien case UNGT: 180690075Sobrien case UNGE: 180790075Sobrien break; 180890075Sobrien default: 180990075Sobrien return FALSE; 181090075Sobrien } 181190075Sobrien 181290075Sobrien start_sequence (); 181390075Sobrien 1814132718Skan target = expand_abs_nojump (GET_MODE (if_info->x), b, if_info->x, 1); 181590075Sobrien 1816132718Skan /* ??? It's a quandary whether cmove would be better here, especially 181790075Sobrien for integers. Perhaps combine will clean things up. */ 181890075Sobrien if (target && negate) 181990075Sobrien target = expand_simple_unop (GET_MODE (target), NEG, target, if_info->x, 0); 182090075Sobrien 182190075Sobrien if (! target) 182290075Sobrien { 182390075Sobrien end_sequence (); 182490075Sobrien return FALSE; 182590075Sobrien } 182690075Sobrien 182790075Sobrien if (target != if_info->x) 182890075Sobrien noce_emit_move_insn (if_info->x, target); 182990075Sobrien 1830169689Skan seq = end_ifcvt_sequence (if_info); 1831169689Skan if (!seq) 183290075Sobrien return FALSE; 183390075Sobrien 1834132718Skan emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATOR (if_info->insn_a)); 183590075Sobrien if_info->cond = cond; 183690075Sobrien if_info->cond_earliest = earliest; 183790075Sobrien 183890075Sobrien return TRUE; 183990075Sobrien} 184090075Sobrien 1841169689Skan/* Convert "if (m < 0) x = b; else x = 0;" to "x = (m >> C) & b;". */ 1842169689Skan 1843169689Skanstatic int 1844169689Skannoce_try_sign_mask (struct noce_if_info *if_info) 1845169689Skan{ 1846169689Skan rtx cond, t, m, c, seq; 1847169689Skan enum machine_mode mode; 1848169689Skan enum rtx_code code; 1849169689Skan 1850169689Skan if (no_new_pseudos) 1851169689Skan return FALSE; 1852169689Skan 1853169689Skan cond = if_info->cond; 1854169689Skan code = GET_CODE (cond); 1855169689Skan m = XEXP (cond, 0); 1856169689Skan c = XEXP (cond, 1); 1857169689Skan 1858169689Skan t = NULL_RTX; 1859169689Skan if (if_info->a == const0_rtx) 1860169689Skan { 1861169689Skan if ((code == LT && c == const0_rtx) 1862169689Skan || (code == LE && c == constm1_rtx)) 1863169689Skan t = if_info->b; 1864169689Skan } 1865169689Skan else if (if_info->b == const0_rtx) 1866169689Skan { 1867169689Skan if ((code == GE && c == const0_rtx) 1868169689Skan || (code == GT && c == constm1_rtx)) 1869169689Skan t = if_info->a; 1870169689Skan } 1871169689Skan 1872169689Skan if (! t || side_effects_p (t)) 1873169689Skan return FALSE; 1874169689Skan 1875169689Skan /* We currently don't handle different modes. */ 1876169689Skan mode = GET_MODE (t); 1877169689Skan if (GET_MODE (m) != mode) 1878169689Skan return FALSE; 1879169689Skan 1880169689Skan /* This is only profitable if T is cheap, or T is unconditionally 1881169689Skan executed/evaluated in the original insn sequence. */ 1882169689Skan if (rtx_cost (t, SET) >= COSTS_N_INSNS (2) 1883169689Skan && (!if_info->b_unconditional 1884169689Skan || t != if_info->b)) 1885169689Skan return FALSE; 1886169689Skan 1887169689Skan start_sequence (); 1888169689Skan /* Use emit_store_flag to generate "m < 0 ? -1 : 0" instead of expanding 1889169689Skan "(signed) m >> 31" directly. This benefits targets with specialized 1890169689Skan insns to obtain the signmask, but still uses ashr_optab otherwise. */ 1891169689Skan m = emit_store_flag (gen_reg_rtx (mode), LT, m, const0_rtx, mode, 0, -1); 1892169689Skan t = m ? expand_binop (mode, and_optab, m, t, NULL_RTX, 0, OPTAB_DIRECT) 1893169689Skan : NULL_RTX; 1894169689Skan 1895169689Skan if (!t) 1896169689Skan { 1897169689Skan end_sequence (); 1898169689Skan return FALSE; 1899169689Skan } 1900169689Skan 1901169689Skan noce_emit_move_insn (if_info->x, t); 1902169689Skan 1903169689Skan seq = end_ifcvt_sequence (if_info); 1904169689Skan if (!seq) 1905169689Skan return FALSE; 1906169689Skan 1907169689Skan emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATOR (if_info->insn_a)); 1908169689Skan return TRUE; 1909169689Skan} 1910169689Skan 1911169689Skan 1912169689Skan/* Optimize away "if (x & C) x |= C" and similar bit manipulation 1913169689Skan transformations. */ 1914169689Skan 1915169689Skanstatic int 1916169689Skannoce_try_bitop (struct noce_if_info *if_info) 1917169689Skan{ 1918169689Skan rtx cond, x, a, result, seq; 1919169689Skan enum machine_mode mode; 1920169689Skan enum rtx_code code; 1921169689Skan int bitnum; 1922169689Skan 1923169689Skan x = if_info->x; 1924169689Skan cond = if_info->cond; 1925169689Skan code = GET_CODE (cond); 1926169689Skan 1927169689Skan /* Check for no else condition. */ 1928169689Skan if (! rtx_equal_p (x, if_info->b)) 1929169689Skan return FALSE; 1930169689Skan 1931169689Skan /* Check for a suitable condition. */ 1932169689Skan if (code != NE && code != EQ) 1933169689Skan return FALSE; 1934169689Skan if (XEXP (cond, 1) != const0_rtx) 1935169689Skan return FALSE; 1936169689Skan cond = XEXP (cond, 0); 1937169689Skan 1938169689Skan /* ??? We could also handle AND here. */ 1939169689Skan if (GET_CODE (cond) == ZERO_EXTRACT) 1940169689Skan { 1941169689Skan if (XEXP (cond, 1) != const1_rtx 1942169689Skan || GET_CODE (XEXP (cond, 2)) != CONST_INT 1943169689Skan || ! rtx_equal_p (x, XEXP (cond, 0))) 1944169689Skan return FALSE; 1945169689Skan bitnum = INTVAL (XEXP (cond, 2)); 1946169689Skan mode = GET_MODE (x); 1947169689Skan if (BITS_BIG_ENDIAN) 1948169689Skan bitnum = GET_MODE_BITSIZE (mode) - 1 - bitnum; 1949169689Skan if (bitnum < 0 || bitnum >= HOST_BITS_PER_WIDE_INT) 1950169689Skan return FALSE; 1951169689Skan } 1952169689Skan else 1953169689Skan return FALSE; 1954169689Skan 1955169689Skan a = if_info->a; 1956169689Skan if (GET_CODE (a) == IOR || GET_CODE (a) == XOR) 1957169689Skan { 1958169689Skan /* Check for "if (X & C) x = x op C". */ 1959169689Skan if (! rtx_equal_p (x, XEXP (a, 0)) 1960169689Skan || GET_CODE (XEXP (a, 1)) != CONST_INT 1961169689Skan || (INTVAL (XEXP (a, 1)) & GET_MODE_MASK (mode)) 1962169689Skan != (unsigned HOST_WIDE_INT) 1 << bitnum) 1963169689Skan return FALSE; 1964169689Skan 1965169689Skan /* if ((x & C) == 0) x |= C; is transformed to x |= C. */ 1966169689Skan /* if ((x & C) != 0) x |= C; is transformed to nothing. */ 1967169689Skan if (GET_CODE (a) == IOR) 1968169689Skan result = (code == NE) ? a : NULL_RTX; 1969169689Skan else if (code == NE) 1970169689Skan { 1971169689Skan /* if ((x & C) == 0) x ^= C; is transformed to x |= C. */ 1972169689Skan result = gen_int_mode ((HOST_WIDE_INT) 1 << bitnum, mode); 1973169689Skan result = simplify_gen_binary (IOR, mode, x, result); 1974169689Skan } 1975169689Skan else 1976169689Skan { 1977169689Skan /* if ((x & C) != 0) x ^= C; is transformed to x &= ~C. */ 1978169689Skan result = gen_int_mode (~((HOST_WIDE_INT) 1 << bitnum), mode); 1979169689Skan result = simplify_gen_binary (AND, mode, x, result); 1980169689Skan } 1981169689Skan } 1982169689Skan else if (GET_CODE (a) == AND) 1983169689Skan { 1984169689Skan /* Check for "if (X & C) x &= ~C". */ 1985169689Skan if (! rtx_equal_p (x, XEXP (a, 0)) 1986169689Skan || GET_CODE (XEXP (a, 1)) != CONST_INT 1987169689Skan || (INTVAL (XEXP (a, 1)) & GET_MODE_MASK (mode)) 1988169689Skan != (~((HOST_WIDE_INT) 1 << bitnum) & GET_MODE_MASK (mode))) 1989169689Skan return FALSE; 1990169689Skan 1991169689Skan /* if ((x & C) == 0) x &= ~C; is transformed to nothing. */ 1992169689Skan /* if ((x & C) != 0) x &= ~C; is transformed to x &= ~C. */ 1993169689Skan result = (code == EQ) ? a : NULL_RTX; 1994169689Skan } 1995169689Skan else 1996169689Skan return FALSE; 1997169689Skan 1998169689Skan if (result) 1999169689Skan { 2000169689Skan start_sequence (); 2001169689Skan noce_emit_move_insn (x, result); 2002169689Skan seq = end_ifcvt_sequence (if_info); 2003169689Skan if (!seq) 2004169689Skan return FALSE; 2005169689Skan 2006169689Skan emit_insn_before_setloc (seq, if_info->jump, 2007169689Skan INSN_LOCATOR (if_info->insn_a)); 2008169689Skan } 2009169689Skan return TRUE; 2010169689Skan} 2011169689Skan 2012169689Skan 2013102780Skan/* Similar to get_condition, only the resulting condition must be 2014102780Skan valid at JUMP, instead of at EARLIEST. */ 201590075Sobrien 201690075Sobrienstatic rtx 2017132718Skannoce_get_condition (rtx jump, rtx *earliest) 201890075Sobrien{ 2019169689Skan rtx cond, set, tmp; 2020102780Skan bool reverse; 202190075Sobrien 202290075Sobrien if (! any_condjump_p (jump)) 202390075Sobrien return NULL_RTX; 202490075Sobrien 202590075Sobrien set = pc_set (jump); 202690075Sobrien 2027102780Skan /* If this branches to JUMP_LABEL when the condition is false, 2028102780Skan reverse the condition. */ 2029102780Skan reverse = (GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF 2030102780Skan && XEXP (XEXP (SET_SRC (set), 2), 0) == JUMP_LABEL (jump)); 2031102780Skan 2032102780Skan /* If the condition variable is a register and is MODE_INT, accept it. */ 2033102780Skan 203490075Sobrien cond = XEXP (SET_SRC (set), 0); 2035102780Skan tmp = XEXP (cond, 0); 2036102780Skan if (REG_P (tmp) && GET_MODE_CLASS (GET_MODE (tmp)) == MODE_INT) 203790075Sobrien { 203890075Sobrien *earliest = jump; 203990075Sobrien 2040102780Skan if (reverse) 204190075Sobrien cond = gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond)), 2042102780Skan GET_MODE (cond), tmp, XEXP (cond, 1)); 2043102780Skan return cond; 204490075Sobrien } 204590075Sobrien 2046102780Skan /* Otherwise, fall back on canonicalize_condition to do the dirty 2047102780Skan work of manipulating MODE_CC values and COMPARE rtx codes. */ 2048169689Skan return canonicalize_condition (jump, cond, reverse, earliest, 2049169689Skan NULL_RTX, false, true); 2050169689Skan} 2051102780Skan 2052169689Skan/* Initialize for a simple IF-THEN or IF-THEN-ELSE block. We will not 2053169689Skan be using conditional execution. Set some fields of IF_INFO based 2054169689Skan on CE_INFO: test_bb, cond, jump, cond_earliest. Return TRUE if 2055169689Skan things look OK. */ 2056102780Skan 2057169689Skanstatic int 2058169689Skannoce_init_if_info (struct ce_if_block *ce_info, struct noce_if_info *if_info) 2059169689Skan{ 2060169689Skan basic_block test_bb = ce_info->test_bb; 2061169689Skan rtx cond, jump; 2062102780Skan 2063169689Skan /* If test is comprised of && or || elements, don't handle it unless 2064169689Skan it is the special case of && elements without an ELSE block. */ 2065169689Skan if (ce_info->num_multiple_test_blocks) 2066169689Skan { 2067169689Skan if (ce_info->else_bb || !ce_info->and_and_p) 2068169689Skan return FALSE; 2069102780Skan 2070169689Skan ce_info->test_bb = test_bb = ce_info->last_test_bb; 2071169689Skan ce_info->num_multiple_test_blocks = 0; 2072169689Skan ce_info->num_and_and_blocks = 0; 2073169689Skan ce_info->num_or_or_blocks = 0; 2074169689Skan } 2075102780Skan 2076169689Skan /* If this is not a standard conditional jump, we can't parse it. */ 2077169689Skan jump = BB_END (test_bb); 2078169689Skan cond = noce_get_condition (jump, &if_info->cond_earliest); 2079169689Skan if (!cond) 2080169689Skan return FALSE; 2081169689Skan 2082169689Skan /* If the conditional jump is more than just a conditional 2083169689Skan jump, then we can not do if-conversion on this block. */ 2084169689Skan if (! onlyjump_p (jump)) 2085169689Skan return FALSE; 2086169689Skan 2087169689Skan /* We must be comparing objects whose modes imply the size. */ 2088169689Skan if (GET_MODE (XEXP (cond, 0)) == BLKmode) 2089169689Skan return FALSE; 2090169689Skan 2091169689Skan if_info->test_bb = test_bb; 2092169689Skan if_info->cond = cond; 2093169689Skan if_info->jump = jump; 2094169689Skan 2095169689Skan return TRUE; 209690075Sobrien} 209790075Sobrien 209890075Sobrien/* Return true if OP is ok for if-then-else processing. */ 209990075Sobrien 210090075Sobrienstatic int 2101132718Skannoce_operand_ok (rtx op) 210290075Sobrien{ 210390075Sobrien /* We special-case memories, so handle any of them with 210490075Sobrien no address side effects. */ 2105169689Skan if (MEM_P (op)) 210690075Sobrien return ! side_effects_p (XEXP (op, 0)); 210790075Sobrien 210890075Sobrien if (side_effects_p (op)) 210990075Sobrien return FALSE; 211090075Sobrien 211190075Sobrien return ! may_trap_p (op); 211290075Sobrien} 211390075Sobrien 2114169689Skan/* Return true if a write into MEM may trap or fault. */ 2115169689Skan 2116169689Skanstatic bool 2117169689Skannoce_mem_write_may_trap_or_fault_p (rtx mem) 2118169689Skan{ 2119169689Skan rtx addr; 2120169689Skan 2121169689Skan if (MEM_READONLY_P (mem)) 2122169689Skan return true; 2123169689Skan 2124169689Skan if (may_trap_or_fault_p (mem)) 2125169689Skan return true; 2126169689Skan 2127169689Skan addr = XEXP (mem, 0); 2128169689Skan 2129169689Skan /* Call target hook to avoid the effects of -fpic etc.... */ 2130169689Skan addr = targetm.delegitimize_address (addr); 2131169689Skan 2132169689Skan while (addr) 2133169689Skan switch (GET_CODE (addr)) 2134169689Skan { 2135169689Skan case CONST: 2136169689Skan case PRE_DEC: 2137169689Skan case PRE_INC: 2138169689Skan case POST_DEC: 2139169689Skan case POST_INC: 2140169689Skan case POST_MODIFY: 2141169689Skan addr = XEXP (addr, 0); 2142169689Skan break; 2143169689Skan case LO_SUM: 2144169689Skan case PRE_MODIFY: 2145169689Skan addr = XEXP (addr, 1); 2146169689Skan break; 2147169689Skan case PLUS: 2148169689Skan if (GET_CODE (XEXP (addr, 1)) == CONST_INT) 2149169689Skan addr = XEXP (addr, 0); 2150169689Skan else 2151169689Skan return false; 2152169689Skan break; 2153169689Skan case LABEL_REF: 2154169689Skan return true; 2155169689Skan case SYMBOL_REF: 2156169689Skan if (SYMBOL_REF_DECL (addr) 2157169689Skan && decl_readonly_section (SYMBOL_REF_DECL (addr), 0)) 2158169689Skan return true; 2159169689Skan return false; 2160169689Skan default: 2161169689Skan return false; 2162169689Skan } 2163169689Skan 2164169689Skan return false; 2165169689Skan} 2166169689Skan 216790075Sobrien/* Given a simple IF-THEN or IF-THEN-ELSE block, attempt to convert it 216890075Sobrien without using conditional execution. Return TRUE if we were 2169117395Skan successful at converting the block. */ 217090075Sobrien 217190075Sobrienstatic int 2172132718Skannoce_process_if_block (struct ce_if_block * ce_info) 217390075Sobrien{ 2174117395Skan basic_block test_bb = ce_info->test_bb; /* test block */ 2175117395Skan basic_block then_bb = ce_info->then_bb; /* THEN */ 2176117395Skan basic_block else_bb = ce_info->else_bb; /* ELSE or NULL */ 2177117395Skan struct noce_if_info if_info; 2178117395Skan rtx insn_a, insn_b; 2179117395Skan rtx set_a, set_b; 2180117395Skan rtx orig_x, x, a, b; 2181117395Skan rtx jump, cond; 2182117395Skan 218390075Sobrien /* We're looking for patterns of the form 218490075Sobrien 218590075Sobrien (1) if (...) x = a; else x = b; 218690075Sobrien (2) x = b; if (...) x = a; 218790075Sobrien (3) if (...) x = a; // as if with an initial x = x. 218890075Sobrien 218990075Sobrien The later patterns require jumps to be more expensive. 219090075Sobrien 219190075Sobrien ??? For future expansion, look for multiple X in such patterns. */ 219290075Sobrien 2193169689Skan if (!noce_init_if_info (ce_info, &if_info)) 219490075Sobrien return FALSE; 219590075Sobrien 2196169689Skan cond = if_info.cond; 2197169689Skan jump = if_info.jump; 219890075Sobrien 219990075Sobrien /* Look for one of the potential sets. */ 220090075Sobrien insn_a = first_active_insn (then_bb); 220190075Sobrien if (! insn_a 2202117395Skan || insn_a != last_active_insn (then_bb, FALSE) 220390075Sobrien || (set_a = single_set (insn_a)) == NULL_RTX) 220490075Sobrien return FALSE; 220590075Sobrien 220690075Sobrien x = SET_DEST (set_a); 220790075Sobrien a = SET_SRC (set_a); 220890075Sobrien 220990075Sobrien /* Look for the other potential set. Make sure we've got equivalent 221090075Sobrien destinations. */ 221190075Sobrien /* ??? This is overconservative. Storing to two different mems is 221290075Sobrien as easy as conditionally computing the address. Storing to a 221390075Sobrien single mem merely requires a scratch memory to use as one of the 221490075Sobrien destination addresses; often the memory immediately below the 221590075Sobrien stack pointer is available for this. */ 221690075Sobrien set_b = NULL_RTX; 221790075Sobrien if (else_bb) 221890075Sobrien { 221990075Sobrien insn_b = first_active_insn (else_bb); 222090075Sobrien if (! insn_b 2221117395Skan || insn_b != last_active_insn (else_bb, FALSE) 222290075Sobrien || (set_b = single_set (insn_b)) == NULL_RTX 222390075Sobrien || ! rtx_equal_p (x, SET_DEST (set_b))) 222490075Sobrien return FALSE; 222590075Sobrien } 222690075Sobrien else 222790075Sobrien { 222890075Sobrien insn_b = prev_nonnote_insn (if_info.cond_earliest); 2229117395Skan /* We're going to be moving the evaluation of B down from above 2230117395Skan COND_EARLIEST to JUMP. Make sure the relevant data is still 2231117395Skan intact. */ 223290075Sobrien if (! insn_b 2233169689Skan || !NONJUMP_INSN_P (insn_b) 223490075Sobrien || (set_b = single_set (insn_b)) == NULL_RTX 223590075Sobrien || ! rtx_equal_p (x, SET_DEST (set_b)) 2236117395Skan || reg_overlap_mentioned_p (x, SET_SRC (set_b)) 2237117395Skan || modified_between_p (SET_SRC (set_b), 2238117395Skan PREV_INSN (if_info.cond_earliest), jump) 2239117395Skan /* Likewise with X. In particular this can happen when 2240117395Skan noce_get_condition looks farther back in the instruction 2241117395Skan stream than one might expect. */ 2242117395Skan || reg_overlap_mentioned_p (x, cond) 2243117395Skan || reg_overlap_mentioned_p (x, a) 2244117395Skan || modified_between_p (x, PREV_INSN (if_info.cond_earliest), jump)) 224590075Sobrien insn_b = set_b = NULL_RTX; 224690075Sobrien } 224790075Sobrien 2248117395Skan /* If x has side effects then only the if-then-else form is safe to 2249117395Skan convert. But even in that case we would need to restore any notes 2250132718Skan (such as REG_INC) at then end. That can be tricky if 2251117395Skan noce_emit_move_insn expands to more than one insn, so disable the 2252117395Skan optimization entirely for now if there are side effects. */ 2253117395Skan if (side_effects_p (x)) 2254117395Skan return FALSE; 225590075Sobrien 2256117395Skan b = (set_b ? SET_SRC (set_b) : x); 225790075Sobrien 225890075Sobrien /* Only operate on register destinations, and even then avoid extending 225990075Sobrien the lifetime of hard registers on small register class machines. */ 226090075Sobrien orig_x = x; 2261169689Skan if (!REG_P (x) 226290075Sobrien || (SMALL_REGISTER_CLASSES 226390075Sobrien && REGNO (x) < FIRST_PSEUDO_REGISTER)) 226490075Sobrien { 2265132718Skan if (no_new_pseudos || GET_MODE (x) == BLKmode) 226690075Sobrien return FALSE; 2267169689Skan 2268169689Skan if (GET_MODE (x) == ZERO_EXTRACT 2269169689Skan && (GET_CODE (XEXP (x, 1)) != CONST_INT 2270169689Skan || GET_CODE (XEXP (x, 2)) != CONST_INT)) 2271169689Skan return FALSE; 2272169689Skan 227390075Sobrien x = gen_reg_rtx (GET_MODE (GET_CODE (x) == STRICT_LOW_PART 227490075Sobrien ? XEXP (x, 0) : x)); 227590075Sobrien } 227690075Sobrien 227790075Sobrien /* Don't operate on sources that may trap or are volatile. */ 227890075Sobrien if (! noce_operand_ok (a) || ! noce_operand_ok (b)) 227990075Sobrien return FALSE; 228090075Sobrien 228190075Sobrien /* Set up the info block for our subroutines. */ 228290075Sobrien if_info.insn_a = insn_a; 228390075Sobrien if_info.insn_b = insn_b; 228490075Sobrien if_info.x = x; 228590075Sobrien if_info.a = a; 228690075Sobrien if_info.b = b; 2287169689Skan if_info.b_unconditional = else_bb == 0; 228890075Sobrien 228990075Sobrien /* Try optimizations in some approximation of a useful order. */ 229090075Sobrien /* ??? Should first look to see if X is live incoming at all. If it 229190075Sobrien isn't, we don't need anything but an unconditional set. */ 229290075Sobrien 229390075Sobrien /* Look and see if A and B are really the same. Avoid creating silly 229490075Sobrien cmove constructs that no one will fix up later. */ 229590075Sobrien if (rtx_equal_p (a, b)) 229690075Sobrien { 229790075Sobrien /* If we have an INSN_B, we don't have to create any new rtl. Just 229890075Sobrien move the instruction that we already have. If we don't have an 229990075Sobrien INSN_B, that means that A == X, and we've got a noop move. In 230090075Sobrien that case don't do anything and let the code below delete INSN_A. */ 230190075Sobrien if (insn_b && else_bb) 230290075Sobrien { 230390075Sobrien rtx note; 230490075Sobrien 2305132718Skan if (else_bb && insn_b == BB_END (else_bb)) 2306132718Skan BB_END (else_bb) = PREV_INSN (insn_b); 2307117395Skan reorder_insns (insn_b, insn_b, PREV_INSN (jump)); 230890075Sobrien 230990075Sobrien /* If there was a REG_EQUAL note, delete it since it may have been 231090075Sobrien true due to this insn being after a jump. */ 231190075Sobrien if ((note = find_reg_note (insn_b, REG_EQUAL, NULL_RTX)) != 0) 231290075Sobrien remove_note (insn_b, note); 231390075Sobrien 231490075Sobrien insn_b = NULL_RTX; 231590075Sobrien } 231690075Sobrien /* If we have "x = b; if (...) x = a;", and x has side-effects, then 231790075Sobrien x must be executed twice. */ 231890075Sobrien else if (insn_b && side_effects_p (orig_x)) 231990075Sobrien return FALSE; 2320132718Skan 232190075Sobrien x = orig_x; 232290075Sobrien goto success; 232390075Sobrien } 232490075Sobrien 2325132718Skan /* Disallow the "if (...) x = a;" form (with an implicit "else x = x;") 2326169689Skan for optimizations if writing to x may trap or fault, i.e. it's a memory 2327169689Skan other than a static var or a stack slot, is misaligned on strict 2328169689Skan aligned machines or is read-only. 2329169689Skan If x is a read-only memory, then the program is valid only if we 2330169689Skan avoid the store into it. If there are stores on both the THEN and 2331169689Skan ELSE arms, then we can go ahead with the conversion; either the 2332169689Skan program is broken, or the condition is always false such that the 2333169689Skan other memory is selected. */ 2334169689Skan if (!set_b && MEM_P (orig_x) && noce_mem_write_may_trap_or_fault_p (orig_x)) 2335169689Skan return FALSE; 2336132718Skan 2337132718Skan if (noce_try_move (&if_info)) 2338132718Skan goto success; 233990075Sobrien if (noce_try_store_flag (&if_info)) 234090075Sobrien goto success; 2341169689Skan if (noce_try_bitop (&if_info)) 2342169689Skan goto success; 234390075Sobrien if (noce_try_minmax (&if_info)) 234490075Sobrien goto success; 234590075Sobrien if (noce_try_abs (&if_info)) 234690075Sobrien goto success; 234790075Sobrien if (HAVE_conditional_move 234890075Sobrien && noce_try_cmove (&if_info)) 234990075Sobrien goto success; 235090075Sobrien if (! HAVE_conditional_execution) 235190075Sobrien { 235290075Sobrien if (noce_try_store_flag_constants (&if_info)) 235390075Sobrien goto success; 2354132718Skan if (noce_try_addcc (&if_info)) 235590075Sobrien goto success; 235690075Sobrien if (noce_try_store_flag_mask (&if_info)) 235790075Sobrien goto success; 235890075Sobrien if (HAVE_conditional_move 235990075Sobrien && noce_try_cmove_arith (&if_info)) 236090075Sobrien goto success; 2361169689Skan if (noce_try_sign_mask (&if_info)) 2362169689Skan goto success; 236390075Sobrien } 236490075Sobrien 236590075Sobrien return FALSE; 236690075Sobrien 236790075Sobrien success: 236890075Sobrien /* The original sets may now be killed. */ 236990075Sobrien delete_insn (insn_a); 237090075Sobrien 237190075Sobrien /* Several special cases here: First, we may have reused insn_b above, 237290075Sobrien in which case insn_b is now NULL. Second, we want to delete insn_b 237390075Sobrien if it came from the ELSE block, because follows the now correct 237490075Sobrien write that appears in the TEST block. However, if we got insn_b from 237590075Sobrien the TEST block, it may in fact be loading data needed for the comparison. 237690075Sobrien We'll let life_analysis remove the insn if it's really dead. */ 237790075Sobrien if (insn_b && else_bb) 237890075Sobrien delete_insn (insn_b); 237990075Sobrien 2380117395Skan /* The new insns will have been inserted immediately before the jump. We 2381117395Skan should be able to remove the jump with impunity, but the condition itself 2382117395Skan may have been modified by gcse to be shared across basic blocks. */ 238390075Sobrien delete_insn (jump); 238490075Sobrien 238590075Sobrien /* If we used a temporary, fix it up now. */ 238690075Sobrien if (orig_x != x) 238790075Sobrien { 238890075Sobrien start_sequence (); 2389132718Skan noce_emit_move_insn (orig_x, x); 2390117395Skan insn_b = get_insns (); 2391132718Skan set_used_flags (orig_x); 2392132718Skan unshare_all_rtl_in_chain (insn_b); 239390075Sobrien end_sequence (); 239490075Sobrien 2395132718Skan emit_insn_after_setloc (insn_b, BB_END (test_bb), INSN_LOCATOR (insn_a)); 239690075Sobrien } 239790075Sobrien 239890075Sobrien /* Merge the blocks! */ 2399117395Skan merge_if_block (ce_info); 240090075Sobrien 240190075Sobrien return TRUE; 240290075Sobrien} 2403169689Skan 2404169689Skan/* Check whether a block is suitable for conditional move conversion. 2405169689Skan Every insn must be a simple set of a register to a constant or a 2406169689Skan register. For each assignment, store the value in the array VALS, 2407169689Skan indexed by register number. COND is the condition we will 2408169689Skan test. */ 2409169689Skan 2410169689Skanstatic int 2411169689Skancheck_cond_move_block (basic_block bb, rtx *vals, rtx cond) 2412169689Skan{ 2413169689Skan rtx insn; 2414169689Skan 2415169689Skan FOR_BB_INSNS (bb, insn) 2416169689Skan { 2417169689Skan rtx set, dest, src; 2418169689Skan 2419169689Skan if (!INSN_P (insn) || JUMP_P (insn)) 2420169689Skan continue; 2421169689Skan set = single_set (insn); 2422169689Skan if (!set) 2423169689Skan return FALSE; 2424169689Skan 2425169689Skan dest = SET_DEST (set); 2426169689Skan src = SET_SRC (set); 2427169689Skan if (!REG_P (dest) 2428169689Skan || (SMALL_REGISTER_CLASSES && HARD_REGISTER_P (dest))) 2429169689Skan return FALSE; 2430169689Skan 2431169689Skan if (!CONSTANT_P (src) && !register_operand (src, VOIDmode)) 2432169689Skan return FALSE; 2433169689Skan 2434169689Skan if (side_effects_p (src) || side_effects_p (dest)) 2435169689Skan return FALSE; 2436169689Skan 2437169689Skan if (may_trap_p (src) || may_trap_p (dest)) 2438169689Skan return FALSE; 2439169689Skan 2440169689Skan /* Don't try to handle this if the source register was 2441169689Skan modified earlier in the block. */ 2442169689Skan if ((REG_P (src) 2443169689Skan && vals[REGNO (src)] != NULL) 2444169689Skan || (GET_CODE (src) == SUBREG && REG_P (SUBREG_REG (src)) 2445169689Skan && vals[REGNO (SUBREG_REG (src))] != NULL)) 2446169689Skan return FALSE; 2447169689Skan 2448169689Skan /* Don't try to handle this if the destination register was 2449169689Skan modified earlier in the block. */ 2450169689Skan if (vals[REGNO (dest)] != NULL) 2451169689Skan return FALSE; 2452169689Skan 2453169689Skan /* Don't try to handle this if the condition uses the 2454169689Skan destination register. */ 2455169689Skan if (reg_overlap_mentioned_p (dest, cond)) 2456169689Skan return FALSE; 2457169689Skan 2458169689Skan vals[REGNO (dest)] = src; 2459169689Skan 2460169689Skan /* Don't try to handle this if the source register is modified 2461169689Skan later in the block. */ 2462169689Skan if (!CONSTANT_P (src) 2463169689Skan && modified_between_p (src, insn, NEXT_INSN (BB_END (bb)))) 2464169689Skan return FALSE; 2465169689Skan } 2466169689Skan 2467169689Skan return TRUE; 2468169689Skan} 2469169689Skan 2470169689Skan/* Given a simple IF-THEN or IF-THEN-ELSE block, attempt to convert it 2471169689Skan using only conditional moves. Return TRUE if we were successful at 2472169689Skan converting the block. */ 2473169689Skan 2474169689Skanstatic int 2475169689Skancond_move_process_if_block (struct ce_if_block *ce_info) 2476169689Skan{ 2477169689Skan basic_block then_bb = ce_info->then_bb; 2478169689Skan basic_block else_bb = ce_info->else_bb; 2479169689Skan struct noce_if_info if_info; 2480169689Skan rtx jump, cond, insn, seq, cond_arg0, cond_arg1, loc_insn; 2481169689Skan int max_reg, size, c, i; 2482169689Skan rtx *then_vals; 2483169689Skan rtx *else_vals; 2484169689Skan enum rtx_code code; 2485169689Skan 2486169689Skan if (!HAVE_conditional_move || no_new_pseudos) 2487169689Skan return FALSE; 2488169689Skan 2489169689Skan memset (&if_info, 0, sizeof if_info); 2490169689Skan 2491169689Skan if (!noce_init_if_info (ce_info, &if_info)) 2492169689Skan return FALSE; 2493169689Skan 2494169689Skan cond = if_info.cond; 2495169689Skan jump = if_info.jump; 2496169689Skan 2497169689Skan /* Build a mapping for each block to the value used for each 2498169689Skan register. */ 2499169689Skan max_reg = max_reg_num (); 2500169689Skan size = (max_reg + 1) * sizeof (rtx); 2501169689Skan then_vals = (rtx *) alloca (size); 2502169689Skan else_vals = (rtx *) alloca (size); 2503169689Skan memset (then_vals, 0, size); 2504169689Skan memset (else_vals, 0, size); 2505169689Skan 2506169689Skan /* Make sure the blocks are suitable. */ 2507169689Skan if (!check_cond_move_block (then_bb, then_vals, cond) 2508169689Skan || (else_bb && !check_cond_move_block (else_bb, else_vals, cond))) 2509169689Skan return FALSE; 2510169689Skan 2511169689Skan /* Make sure the blocks can be used together. If the same register 2512169689Skan is set in both blocks, and is not set to a constant in both 2513169689Skan cases, then both blocks must set it to the same register. We 2514169689Skan have already verified that if it is set to a register, that the 2515169689Skan source register does not change after the assignment. Also count 2516169689Skan the number of registers set in only one of the blocks. */ 2517169689Skan c = 0; 2518169689Skan for (i = 0; i <= max_reg; ++i) 2519169689Skan { 2520169689Skan if (!then_vals[i] && !else_vals[i]) 2521169689Skan continue; 2522169689Skan 2523169689Skan if (!then_vals[i] || !else_vals[i]) 2524169689Skan ++c; 2525169689Skan else 2526169689Skan { 2527169689Skan if (!CONSTANT_P (then_vals[i]) 2528169689Skan && !CONSTANT_P (else_vals[i]) 2529169689Skan && !rtx_equal_p (then_vals[i], else_vals[i])) 2530169689Skan return FALSE; 2531169689Skan } 2532169689Skan } 2533169689Skan 2534169689Skan /* Make sure it is reasonable to convert this block. What matters 2535169689Skan is the number of assignments currently made in only one of the 2536169689Skan branches, since if we convert we are going to always execute 2537169689Skan them. */ 2538169689Skan if (c > MAX_CONDITIONAL_EXECUTE) 2539169689Skan return FALSE; 2540169689Skan 2541169689Skan /* Emit the conditional moves. First do the then block, then do 2542169689Skan anything left in the else blocks. */ 2543169689Skan 2544169689Skan code = GET_CODE (cond); 2545169689Skan cond_arg0 = XEXP (cond, 0); 2546169689Skan cond_arg1 = XEXP (cond, 1); 2547169689Skan 2548169689Skan start_sequence (); 2549169689Skan 2550169689Skan FOR_BB_INSNS (then_bb, insn) 2551169689Skan { 2552169689Skan rtx set, target, dest, t, e; 2553169689Skan unsigned int regno; 2554169689Skan 2555169689Skan if (!INSN_P (insn) || JUMP_P (insn)) 2556169689Skan continue; 2557169689Skan set = single_set (insn); 2558169689Skan gcc_assert (set && REG_P (SET_DEST (set))); 2559169689Skan 2560169689Skan dest = SET_DEST (set); 2561169689Skan regno = REGNO (dest); 2562169689Skan t = then_vals[regno]; 2563169689Skan e = else_vals[regno]; 2564169689Skan gcc_assert (t); 2565169689Skan if (!e) 2566169689Skan e = dest; 2567169689Skan target = noce_emit_cmove (&if_info, dest, code, cond_arg0, cond_arg1, 2568169689Skan t, e); 2569169689Skan if (!target) 2570169689Skan { 2571169689Skan end_sequence (); 2572169689Skan return FALSE; 2573169689Skan } 2574169689Skan 2575169689Skan if (target != dest) 2576169689Skan noce_emit_move_insn (dest, target); 2577169689Skan } 2578169689Skan 2579169689Skan if (else_bb) 2580169689Skan { 2581169689Skan FOR_BB_INSNS (else_bb, insn) 2582169689Skan { 2583169689Skan rtx set, target, dest; 2584169689Skan unsigned int regno; 2585169689Skan 2586169689Skan if (!INSN_P (insn) || JUMP_P (insn)) 2587169689Skan continue; 2588169689Skan set = single_set (insn); 2589169689Skan gcc_assert (set && REG_P (SET_DEST (set))); 2590169689Skan 2591169689Skan dest = SET_DEST (set); 2592169689Skan regno = REGNO (dest); 2593169689Skan 2594169689Skan /* If this register was set in the then block, we already 2595169689Skan handled this case above. */ 2596169689Skan if (then_vals[regno]) 2597169689Skan continue; 2598169689Skan gcc_assert (else_vals[regno]); 2599169689Skan 2600169689Skan target = noce_emit_cmove (&if_info, dest, code, cond_arg0, cond_arg1, 2601169689Skan dest, else_vals[regno]); 2602169689Skan if (!target) 2603169689Skan { 2604169689Skan end_sequence (); 2605169689Skan return FALSE; 2606169689Skan } 2607169689Skan 2608169689Skan if (target != dest) 2609169689Skan noce_emit_move_insn (dest, target); 2610169689Skan } 2611169689Skan } 2612169689Skan 2613169689Skan seq = end_ifcvt_sequence (&if_info); 2614169689Skan if (!seq) 2615169689Skan return FALSE; 2616169689Skan 2617169689Skan loc_insn = first_active_insn (then_bb); 2618169689Skan if (!loc_insn) 2619169689Skan { 2620169689Skan loc_insn = first_active_insn (else_bb); 2621169689Skan gcc_assert (loc_insn); 2622169689Skan } 2623169689Skan emit_insn_before_setloc (seq, jump, INSN_LOCATOR (loc_insn)); 2624169689Skan 2625169689Skan FOR_BB_INSNS (then_bb, insn) 2626169689Skan if (INSN_P (insn) && !JUMP_P (insn)) 2627169689Skan delete_insn (insn); 2628169689Skan if (else_bb) 2629169689Skan { 2630169689Skan FOR_BB_INSNS (else_bb, insn) 2631169689Skan if (INSN_P (insn) && !JUMP_P (insn)) 2632169689Skan delete_insn (insn); 2633169689Skan } 2634169689Skan delete_insn (jump); 2635169689Skan 2636169689Skan merge_if_block (ce_info); 2637169689Skan 2638169689Skan return TRUE; 2639169689Skan} 264090075Sobrien 264190075Sobrien/* Attempt to convert an IF-THEN or IF-THEN-ELSE block into 264290075Sobrien straight line code. Return true if successful. */ 264390075Sobrien 264490075Sobrienstatic int 2645132718Skanprocess_if_block (struct ce_if_block * ce_info) 264690075Sobrien{ 264790075Sobrien if (! reload_completed 2648117395Skan && noce_process_if_block (ce_info)) 264990075Sobrien return TRUE; 265090075Sobrien 2651169689Skan if (HAVE_conditional_move 2652169689Skan && cond_move_process_if_block (ce_info)) 2653169689Skan return TRUE; 2654169689Skan 2655117395Skan if (HAVE_conditional_execution && reload_completed) 2656117395Skan { 2657117395Skan /* If we have && and || tests, try to first handle combining the && and 2658117395Skan || tests into the conditional code, and if that fails, go back and 2659117395Skan handle it without the && and ||, which at present handles the && case 2660117395Skan if there was no ELSE block. */ 2661117395Skan if (cond_exec_process_if_block (ce_info, TRUE)) 2662117395Skan return TRUE; 266390075Sobrien 2664117395Skan if (ce_info->num_multiple_test_blocks) 2665117395Skan { 2666117395Skan cancel_changes (0); 2667117395Skan 2668117395Skan if (cond_exec_process_if_block (ce_info, FALSE)) 2669117395Skan return TRUE; 2670117395Skan } 2671117395Skan } 2672117395Skan 267390075Sobrien return FALSE; 267490075Sobrien} 267590075Sobrien 267690075Sobrien/* Merge the blocks and mark for local life update. */ 267790075Sobrien 267890075Sobrienstatic void 2679132718Skanmerge_if_block (struct ce_if_block * ce_info) 268090075Sobrien{ 2681117395Skan basic_block test_bb = ce_info->test_bb; /* last test block */ 2682117395Skan basic_block then_bb = ce_info->then_bb; /* THEN */ 2683117395Skan basic_block else_bb = ce_info->else_bb; /* ELSE or NULL */ 2684117395Skan basic_block join_bb = ce_info->join_bb; /* join block */ 268590075Sobrien basic_block combo_bb; 268690075Sobrien 268790075Sobrien /* All block merging is done into the lower block numbers. */ 268890075Sobrien 268990075Sobrien combo_bb = test_bb; 269090075Sobrien 2691117395Skan /* Merge any basic blocks to handle && and || subtests. Each of 2692117395Skan the blocks are on the fallthru path from the predecessor block. */ 2693117395Skan if (ce_info->num_multiple_test_blocks > 0) 2694117395Skan { 2695117395Skan basic_block bb = test_bb; 2696117395Skan basic_block last_test_bb = ce_info->last_test_bb; 2697117395Skan basic_block fallthru = block_fallthru (bb); 2698132718Skan 2699117395Skan do 2700117395Skan { 2701117395Skan bb = fallthru; 2702117395Skan fallthru = block_fallthru (bb); 2703132718Skan merge_blocks (combo_bb, bb); 2704132718Skan num_true_changes++; 2705117395Skan } 2706117395Skan while (bb != last_test_bb); 2707117395Skan } 2708117395Skan 2709117395Skan /* Merge TEST block into THEN block. Normally the THEN block won't have a 2710117395Skan label, but it might if there were || tests. That label's count should be 2711117395Skan zero, and it normally should be removed. */ 2712117395Skan 271396263Sobrien if (then_bb) 271496263Sobrien { 2715169689Skan if (combo_bb->il.rtl->global_live_at_end) 2716169689Skan COPY_REG_SET (combo_bb->il.rtl->global_live_at_end, 2717169689Skan then_bb->il.rtl->global_live_at_end); 2718132718Skan merge_blocks (combo_bb, then_bb); 2719132718Skan num_true_changes++; 272096263Sobrien } 272190075Sobrien 272290075Sobrien /* The ELSE block, if it existed, had a label. That label count 272390075Sobrien will almost always be zero, but odd things can happen when labels 272490075Sobrien get their addresses taken. */ 272590075Sobrien if (else_bb) 272690075Sobrien { 2727132718Skan merge_blocks (combo_bb, else_bb); 2728132718Skan num_true_changes++; 272990075Sobrien } 273090075Sobrien 273190075Sobrien /* If there was no join block reported, that means it was not adjacent 273290075Sobrien to the others, and so we cannot merge them. */ 273390075Sobrien 273490075Sobrien if (! join_bb) 273590075Sobrien { 2736132718Skan rtx last = BB_END (combo_bb); 273796263Sobrien 273890075Sobrien /* The outgoing edge for the current COMBO block should already 273990075Sobrien be correct. Verify this. */ 2740169689Skan if (EDGE_COUNT (combo_bb->succs) == 0) 2741169689Skan gcc_assert (find_reg_note (last, REG_NORETURN, NULL) 2742169689Skan || (NONJUMP_INSN_P (last) 2743169689Skan && GET_CODE (PATTERN (last)) == TRAP_IF 2744169689Skan && (TRAP_CONDITION (PATTERN (last)) 2745169689Skan == const_true_rtx))); 274690075Sobrien 2747169689Skan else 274896263Sobrien /* There should still be something at the end of the THEN or ELSE 274990075Sobrien blocks taking us to our final destination. */ 2750169689Skan gcc_assert (JUMP_P (last) 2751169689Skan || (EDGE_SUCC (combo_bb, 0)->dest == EXIT_BLOCK_PTR 2752169689Skan && CALL_P (last) 2753169689Skan && SIBLING_CALL_P (last)) 2754169689Skan || ((EDGE_SUCC (combo_bb, 0)->flags & EDGE_EH) 2755169689Skan && can_throw_internal (last))); 275690075Sobrien } 275790075Sobrien 275890075Sobrien /* The JOIN block may have had quite a number of other predecessors too. 275990075Sobrien Since we've already merged the TEST, THEN and ELSE blocks, we should 276090075Sobrien have only one remaining edge from our if-then-else diamond. If there 276190075Sobrien is more than one remaining edge, it must come from elsewhere. There 2762132718Skan may be zero incoming edges if the THEN block didn't actually join 2763169689Skan back up (as with a call to a non-return function). */ 2764169689Skan else if (EDGE_COUNT (join_bb->preds) < 2 276590075Sobrien && join_bb != EXIT_BLOCK_PTR) 276690075Sobrien { 276790075Sobrien /* We can merge the JOIN. */ 2768169689Skan if (combo_bb->il.rtl->global_live_at_end) 2769169689Skan COPY_REG_SET (combo_bb->il.rtl->global_live_at_end, 2770169689Skan join_bb->il.rtl->global_live_at_end); 2771117395Skan 2772132718Skan merge_blocks (combo_bb, join_bb); 2773132718Skan num_true_changes++; 277490075Sobrien } 277590075Sobrien else 277690075Sobrien { 277790075Sobrien /* We cannot merge the JOIN. */ 277890075Sobrien 277990075Sobrien /* The outgoing edge for the current COMBO block should already 278090075Sobrien be correct. Verify this. */ 2781169689Skan gcc_assert (single_succ_p (combo_bb) 2782169689Skan && single_succ (combo_bb) == join_bb); 278390075Sobrien 278490075Sobrien /* Remove the jump and cruft from the end of the COMBO block. */ 278590075Sobrien if (join_bb != EXIT_BLOCK_PTR) 2786169689Skan tidy_fallthru_edge (single_succ_edge (combo_bb)); 278790075Sobrien } 278890075Sobrien 278990075Sobrien num_updated_if_blocks++; 279090075Sobrien} 279190075Sobrien 2792117395Skan/* Find a block ending in a simple IF condition and try to transform it 2793117395Skan in some way. When converting a multi-block condition, put the new code 2794117395Skan in the first such block and delete the rest. Return a pointer to this 2795117395Skan first block if some transformation was done. Return NULL otherwise. */ 279690075Sobrien 2797117395Skanstatic basic_block 2798132718Skanfind_if_header (basic_block test_bb, int pass) 279990075Sobrien{ 2800117395Skan ce_if_block_t ce_info; 280190075Sobrien edge then_edge; 280290075Sobrien edge else_edge; 280390075Sobrien 280490075Sobrien /* The kind of block we're looking for has exactly two successors. */ 2805169689Skan if (EDGE_COUNT (test_bb->succs) != 2) 2806117395Skan return NULL; 280790075Sobrien 2808169689Skan then_edge = EDGE_SUCC (test_bb, 0); 2809169689Skan else_edge = EDGE_SUCC (test_bb, 1); 2810169689Skan 281190075Sobrien /* Neither edge should be abnormal. */ 281290075Sobrien if ((then_edge->flags & EDGE_COMPLEX) 281390075Sobrien || (else_edge->flags & EDGE_COMPLEX)) 2814117395Skan return NULL; 281590075Sobrien 2816132718Skan /* Nor exit the loop. */ 2817132718Skan if ((then_edge->flags & EDGE_LOOP_EXIT) 2818132718Skan || (else_edge->flags & EDGE_LOOP_EXIT)) 2819132718Skan return NULL; 2820132718Skan 282190075Sobrien /* The THEN edge is canonically the one that falls through. */ 282290075Sobrien if (then_edge->flags & EDGE_FALLTHRU) 282390075Sobrien ; 282490075Sobrien else if (else_edge->flags & EDGE_FALLTHRU) 282590075Sobrien { 282690075Sobrien edge e = else_edge; 282790075Sobrien else_edge = then_edge; 282890075Sobrien then_edge = e; 282990075Sobrien } 283090075Sobrien else 283190075Sobrien /* Otherwise this must be a multiway branch of some sort. */ 2832117395Skan return NULL; 283390075Sobrien 2834132718Skan memset (&ce_info, '\0', sizeof (ce_info)); 2835117395Skan ce_info.test_bb = test_bb; 2836117395Skan ce_info.then_bb = then_edge->dest; 2837117395Skan ce_info.else_bb = else_edge->dest; 2838117395Skan ce_info.pass = pass; 2839117395Skan 2840117395Skan#ifdef IFCVT_INIT_EXTRA_FIELDS 2841117395Skan IFCVT_INIT_EXTRA_FIELDS (&ce_info); 2842117395Skan#endif 2843117395Skan 2844117395Skan if (find_if_block (&ce_info)) 284590075Sobrien goto success; 2846117395Skan 284790075Sobrien if (HAVE_trap && HAVE_conditional_trap 284890075Sobrien && find_cond_trap (test_bb, then_edge, else_edge)) 284990075Sobrien goto success; 2850117395Skan 2851132718Skan if (dom_computed[CDI_POST_DOMINATORS] >= DOM_NO_FAST_QUERY 285290075Sobrien && (! HAVE_conditional_execution || reload_completed)) 285390075Sobrien { 285490075Sobrien if (find_if_case_1 (test_bb, then_edge, else_edge)) 285590075Sobrien goto success; 285690075Sobrien if (find_if_case_2 (test_bb, then_edge, else_edge)) 285790075Sobrien goto success; 285890075Sobrien } 285990075Sobrien 2860117395Skan return NULL; 286190075Sobrien 286290075Sobrien success: 2863169689Skan if (dump_file) 2864169689Skan fprintf (dump_file, "Conversion succeeded on pass %d.\n", pass); 2865117395Skan return ce_info.test_bb; 286690075Sobrien} 286790075Sobrien 2868117395Skan/* Return true if a block has two edges, one of which falls through to the next 2869117395Skan block, and the other jumps to a specific block, so that we can tell if the 2870117395Skan block is part of an && test or an || test. Returns either -1 or the number 2871117395Skan of non-note, non-jump, non-USE/CLOBBER insns in the block. */ 2872117395Skan 2873117395Skanstatic int 2874132718Skanblock_jumps_and_fallthru_p (basic_block cur_bb, basic_block target_bb) 2875117395Skan{ 2876117395Skan edge cur_edge; 2877117395Skan int fallthru_p = FALSE; 2878117395Skan int jump_p = FALSE; 2879117395Skan rtx insn; 2880117395Skan rtx end; 2881117395Skan int n_insns = 0; 2882169689Skan edge_iterator ei; 2883117395Skan 2884117395Skan if (!cur_bb || !target_bb) 2885117395Skan return -1; 2886117395Skan 2887117395Skan /* If no edges, obviously it doesn't jump or fallthru. */ 2888169689Skan if (EDGE_COUNT (cur_bb->succs) == 0) 2889117395Skan return FALSE; 2890117395Skan 2891169689Skan FOR_EACH_EDGE (cur_edge, ei, cur_bb->succs) 2892117395Skan { 2893117395Skan if (cur_edge->flags & EDGE_COMPLEX) 2894117395Skan /* Anything complex isn't what we want. */ 2895117395Skan return -1; 2896117395Skan 2897117395Skan else if (cur_edge->flags & EDGE_FALLTHRU) 2898117395Skan fallthru_p = TRUE; 2899117395Skan 2900117395Skan else if (cur_edge->dest == target_bb) 2901117395Skan jump_p = TRUE; 2902117395Skan 2903117395Skan else 2904117395Skan return -1; 2905117395Skan } 2906117395Skan 2907117395Skan if ((jump_p & fallthru_p) == 0) 2908117395Skan return -1; 2909117395Skan 2910117395Skan /* Don't allow calls in the block, since this is used to group && and || 2911117395Skan together for conditional execution support. ??? we should support 2912117395Skan conditional execution support across calls for IA-64 some day, but 2913117395Skan for now it makes the code simpler. */ 2914132718Skan end = BB_END (cur_bb); 2915132718Skan insn = BB_HEAD (cur_bb); 2916117395Skan 2917117395Skan while (insn != NULL_RTX) 2918117395Skan { 2919169689Skan if (CALL_P (insn)) 2920117395Skan return -1; 2921117395Skan 2922117395Skan if (INSN_P (insn) 2923169689Skan && !JUMP_P (insn) 2924117395Skan && GET_CODE (PATTERN (insn)) != USE 2925117395Skan && GET_CODE (PATTERN (insn)) != CLOBBER) 2926117395Skan n_insns++; 2927117395Skan 2928117395Skan if (insn == end) 2929117395Skan break; 2930117395Skan 2931117395Skan insn = NEXT_INSN (insn); 2932117395Skan } 2933117395Skan 2934117395Skan return n_insns; 2935117395Skan} 2936117395Skan 293790075Sobrien/* Determine if a given basic block heads a simple IF-THEN or IF-THEN-ELSE 293890075Sobrien block. If so, we'll try to convert the insns to not require the branch. 2939117395Skan Return TRUE if we were successful at converting the block. */ 294090075Sobrien 294190075Sobrienstatic int 2942132718Skanfind_if_block (struct ce_if_block * ce_info) 294390075Sobrien{ 2944117395Skan basic_block test_bb = ce_info->test_bb; 2945117395Skan basic_block then_bb = ce_info->then_bb; 2946117395Skan basic_block else_bb = ce_info->else_bb; 294790075Sobrien basic_block join_bb = NULL_BLOCK; 2948117395Skan edge cur_edge; 2949117395Skan basic_block next; 2950169689Skan edge_iterator ei; 295190075Sobrien 2952117395Skan ce_info->last_test_bb = test_bb; 2953117395Skan 2954117395Skan /* Discover if any fall through predecessors of the current test basic block 2955117395Skan were && tests (which jump to the else block) or || tests (which jump to 2956117395Skan the then block). */ 2957117395Skan if (HAVE_conditional_execution && reload_completed 2958169689Skan && single_pred_p (test_bb) 2959169689Skan && single_pred_edge (test_bb)->flags == EDGE_FALLTHRU) 2960117395Skan { 2961169689Skan basic_block bb = single_pred (test_bb); 2962117395Skan basic_block target_bb; 2963117395Skan int max_insns = MAX_CONDITIONAL_EXECUTE; 2964117395Skan int n_insns; 2965117395Skan 2966132718Skan /* Determine if the preceding block is an && or || block. */ 2967117395Skan if ((n_insns = block_jumps_and_fallthru_p (bb, else_bb)) >= 0) 2968117395Skan { 2969117395Skan ce_info->and_and_p = TRUE; 2970117395Skan target_bb = else_bb; 2971117395Skan } 2972117395Skan else if ((n_insns = block_jumps_and_fallthru_p (bb, then_bb)) >= 0) 2973117395Skan { 2974132718Skan ce_info->and_and_p = FALSE; 2975117395Skan target_bb = then_bb; 2976117395Skan } 2977117395Skan else 2978117395Skan target_bb = NULL_BLOCK; 2979117395Skan 2980117395Skan if (target_bb && n_insns <= max_insns) 2981117395Skan { 2982117395Skan int total_insns = 0; 2983117395Skan int blocks = 0; 2984117395Skan 2985117395Skan ce_info->last_test_bb = test_bb; 2986117395Skan 2987117395Skan /* Found at least one && or || block, look for more. */ 2988117395Skan do 2989117395Skan { 2990117395Skan ce_info->test_bb = test_bb = bb; 2991117395Skan total_insns += n_insns; 2992117395Skan blocks++; 2993117395Skan 2994169689Skan if (!single_pred_p (bb)) 2995117395Skan break; 2996117395Skan 2997169689Skan bb = single_pred (bb); 2998117395Skan n_insns = block_jumps_and_fallthru_p (bb, target_bb); 2999117395Skan } 3000117395Skan while (n_insns >= 0 && (total_insns + n_insns) <= max_insns); 3001117395Skan 3002117395Skan ce_info->num_multiple_test_blocks = blocks; 3003117395Skan ce_info->num_multiple_test_insns = total_insns; 3004117395Skan 3005117395Skan if (ce_info->and_and_p) 3006117395Skan ce_info->num_and_and_blocks = blocks; 3007117395Skan else 3008117395Skan ce_info->num_or_or_blocks = blocks; 3009117395Skan } 3010117395Skan } 3011117395Skan 3012169689Skan /* The THEN block of an IF-THEN combo must have exactly one predecessor, 3013169689Skan other than any || blocks which jump to the THEN block. */ 3014169689Skan if ((EDGE_COUNT (then_bb->preds) - ce_info->num_or_or_blocks) != 1) 3015169689Skan return FALSE; 3016169689Skan 3017169689Skan /* The edges of the THEN and ELSE blocks cannot have complex edges. */ 3018169689Skan FOR_EACH_EDGE (cur_edge, ei, then_bb->preds) 3019117395Skan { 3020117395Skan if (cur_edge->flags & EDGE_COMPLEX) 3021117395Skan return FALSE; 3022117395Skan } 3023117395Skan 3024169689Skan FOR_EACH_EDGE (cur_edge, ei, else_bb->preds) 3025117395Skan { 3026117395Skan if (cur_edge->flags & EDGE_COMPLEX) 3027117395Skan return FALSE; 3028117395Skan } 3029117395Skan 303090075Sobrien /* The THEN block of an IF-THEN combo must have zero or one successors. */ 3031169689Skan if (EDGE_COUNT (then_bb->succs) > 0 3032169689Skan && (!single_succ_p (then_bb) 3033169689Skan || (single_succ_edge (then_bb)->flags & EDGE_COMPLEX) 3034132718Skan || (flow2_completed && tablejump_p (BB_END (then_bb), NULL, NULL)))) 303590075Sobrien return FALSE; 303690075Sobrien 303790075Sobrien /* If the THEN block has no successors, conditional execution can still 303890075Sobrien make a conditional call. Don't do this unless the ELSE block has 303990075Sobrien only one incoming edge -- the CFG manipulation is too ugly otherwise. 304090075Sobrien Check for the last insn of the THEN block being an indirect jump, which 304190075Sobrien is listed as not having any successors, but confuses the rest of the CE 3042117395Skan code processing. ??? we should fix this in the future. */ 3043169689Skan if (EDGE_COUNT (then_bb->succs) == 0) 304490075Sobrien { 3045169689Skan if (single_pred_p (else_bb)) 304690075Sobrien { 3047132718Skan rtx last_insn = BB_END (then_bb); 304890075Sobrien 304990075Sobrien while (last_insn 3050169689Skan && NOTE_P (last_insn) 3051132718Skan && last_insn != BB_HEAD (then_bb)) 305290075Sobrien last_insn = PREV_INSN (last_insn); 305390075Sobrien 305490075Sobrien if (last_insn 3055169689Skan && JUMP_P (last_insn) 305690075Sobrien && ! simplejump_p (last_insn)) 305790075Sobrien return FALSE; 305890075Sobrien 305990075Sobrien join_bb = else_bb; 306090075Sobrien else_bb = NULL_BLOCK; 306190075Sobrien } 306290075Sobrien else 306390075Sobrien return FALSE; 306490075Sobrien } 306590075Sobrien 306690075Sobrien /* If the THEN block's successor is the other edge out of the TEST block, 306790075Sobrien then we have an IF-THEN combo without an ELSE. */ 3068169689Skan else if (single_succ (then_bb) == else_bb) 306990075Sobrien { 307090075Sobrien join_bb = else_bb; 307190075Sobrien else_bb = NULL_BLOCK; 307290075Sobrien } 307390075Sobrien 307490075Sobrien /* If the THEN and ELSE block meet in a subsequent block, and the ELSE 307590075Sobrien has exactly one predecessor and one successor, and the outgoing edge 307690075Sobrien is not complex, then we have an IF-THEN-ELSE combo. */ 3077169689Skan else if (single_succ_p (else_bb) 3078169689Skan && single_succ (then_bb) == single_succ (else_bb) 3079169689Skan && single_pred_p (else_bb) 3080169689Skan && ! (single_succ_edge (else_bb)->flags & EDGE_COMPLEX) 3081132718Skan && ! (flow2_completed && tablejump_p (BB_END (else_bb), NULL, NULL))) 3082169689Skan join_bb = single_succ (else_bb); 308390075Sobrien 308490075Sobrien /* Otherwise it is not an IF-THEN or IF-THEN-ELSE combination. */ 308590075Sobrien else 3086132718Skan return FALSE; 308790075Sobrien 308890075Sobrien num_possible_if_blocks++; 308990075Sobrien 3090169689Skan if (dump_file) 309190075Sobrien { 3092169689Skan fprintf (dump_file, 3093169689Skan "\nIF-THEN%s block found, pass %d, start block %d " 3094169689Skan "[insn %d], then %d [%d]", 3095117395Skan (else_bb) ? "-ELSE" : "", 3096117395Skan ce_info->pass, 3097169689Skan test_bb->index, 3098169689Skan BB_HEAD (test_bb) ? (int)INSN_UID (BB_HEAD (test_bb)) : -1, 3099169689Skan then_bb->index, 3100169689Skan BB_HEAD (then_bb) ? (int)INSN_UID (BB_HEAD (then_bb)) : -1); 3101117395Skan 310290075Sobrien if (else_bb) 3103169689Skan fprintf (dump_file, ", else %d [%d]", 3104169689Skan else_bb->index, 3105169689Skan BB_HEAD (else_bb) ? (int)INSN_UID (BB_HEAD (else_bb)) : -1); 3106117395Skan 3107169689Skan fprintf (dump_file, ", join %d [%d]", 3108169689Skan join_bb->index, 3109169689Skan BB_HEAD (join_bb) ? (int)INSN_UID (BB_HEAD (join_bb)) : -1); 3110117395Skan 3111117395Skan if (ce_info->num_multiple_test_blocks > 0) 3112169689Skan fprintf (dump_file, ", %d %s block%s last test %d [%d]", 3113117395Skan ce_info->num_multiple_test_blocks, 3114117395Skan (ce_info->and_and_p) ? "&&" : "||", 3115117395Skan (ce_info->num_multiple_test_blocks == 1) ? "" : "s", 3116117395Skan ce_info->last_test_bb->index, 3117132718Skan ((BB_HEAD (ce_info->last_test_bb)) 3118132718Skan ? (int)INSN_UID (BB_HEAD (ce_info->last_test_bb)) 3119117395Skan : -1)); 3120117395Skan 3121169689Skan fputc ('\n', dump_file); 312290075Sobrien } 312390075Sobrien 3124117395Skan /* Make sure IF, THEN, and ELSE, blocks are adjacent. Actually, we get the 3125117395Skan first condition for free, since we've already asserted that there's a 3126117395Skan fallthru edge from IF to THEN. Likewise for the && and || blocks, since 3127117395Skan we checked the FALLTHRU flag, those are already adjacent to the last IF 3128117395Skan block. */ 312990075Sobrien /* ??? As an enhancement, move the ELSE block. Have to deal with 3130169689Skan BLOCK notes, if by no other means than backing out the merge if they 313190075Sobrien exist. Sticky enough I don't want to think about it now. */ 3132117395Skan next = then_bb; 3133117395Skan if (else_bb && (next = next->next_bb) != else_bb) 313490075Sobrien return FALSE; 3135117395Skan if ((next = next->next_bb) != join_bb && join_bb != EXIT_BLOCK_PTR) 313690075Sobrien { 313790075Sobrien if (else_bb) 313890075Sobrien join_bb = NULL; 313990075Sobrien else 314090075Sobrien return FALSE; 314190075Sobrien } 314290075Sobrien 314390075Sobrien /* Do the real work. */ 3144117395Skan ce_info->else_bb = else_bb; 3145117395Skan ce_info->join_bb = join_bb; 3146117395Skan 3147117395Skan return process_if_block (ce_info); 314890075Sobrien} 314990075Sobrien 3150117395Skan/* Convert a branch over a trap, or a branch 3151117395Skan to a trap, into a conditional trap. */ 315290075Sobrien 315390075Sobrienstatic int 3154132718Skanfind_cond_trap (basic_block test_bb, edge then_edge, edge else_edge) 315590075Sobrien{ 3156117395Skan basic_block then_bb = then_edge->dest; 3157117395Skan basic_block else_bb = else_edge->dest; 3158117395Skan basic_block other_bb, trap_bb; 315990075Sobrien rtx trap, jump, cond, cond_earliest, seq; 316090075Sobrien enum rtx_code code; 316190075Sobrien 316290075Sobrien /* Locate the block with the trap instruction. */ 316390075Sobrien /* ??? While we look for no successors, we really ought to allow 316490075Sobrien EH successors. Need to fix merge_if_block for that to work. */ 316596263Sobrien if ((trap = block_has_only_trap (then_bb)) != NULL) 316696263Sobrien trap_bb = then_bb, other_bb = else_bb; 316796263Sobrien else if ((trap = block_has_only_trap (else_bb)) != NULL) 316896263Sobrien trap_bb = else_bb, other_bb = then_bb; 316990075Sobrien else 317090075Sobrien return FALSE; 317190075Sobrien 3172169689Skan if (dump_file) 317390075Sobrien { 3174169689Skan fprintf (dump_file, "\nTRAP-IF block found, start %d, trap %d\n", 317596263Sobrien test_bb->index, trap_bb->index); 317690075Sobrien } 317790075Sobrien 317890075Sobrien /* If this is not a standard conditional jump, we can't parse it. */ 3179132718Skan jump = BB_END (test_bb); 318090075Sobrien cond = noce_get_condition (jump, &cond_earliest); 318190075Sobrien if (! cond) 318290075Sobrien return FALSE; 318390075Sobrien 3184117395Skan /* If the conditional jump is more than just a conditional jump, then 3185117395Skan we can not do if-conversion on this block. */ 318690075Sobrien if (! onlyjump_p (jump)) 318790075Sobrien return FALSE; 318890075Sobrien 318990075Sobrien /* We must be comparing objects whose modes imply the size. */ 319090075Sobrien if (GET_MODE (XEXP (cond, 0)) == BLKmode) 319190075Sobrien return FALSE; 319290075Sobrien 319390075Sobrien /* Reverse the comparison code, if necessary. */ 319490075Sobrien code = GET_CODE (cond); 319590075Sobrien if (then_bb == trap_bb) 319690075Sobrien { 319790075Sobrien code = reversed_comparison_code (cond, jump); 319890075Sobrien if (code == UNKNOWN) 319990075Sobrien return FALSE; 320090075Sobrien } 320190075Sobrien 320290075Sobrien /* Attempt to generate the conditional trap. */ 3203132718Skan seq = gen_cond_trap (code, XEXP (cond, 0), 3204132718Skan XEXP (cond, 1), 320590075Sobrien TRAP_CODE (PATTERN (trap))); 320690075Sobrien if (seq == NULL) 320790075Sobrien return FALSE; 320890075Sobrien 3209132718Skan num_true_changes++; 3210132718Skan 321196263Sobrien /* Emit the new insns before cond_earliest. */ 3212132718Skan emit_insn_before_setloc (seq, cond_earliest, INSN_LOCATOR (trap)); 321390075Sobrien 321496263Sobrien /* Delete the trap block if possible. */ 321596263Sobrien remove_edge (trap_bb == then_bb ? then_edge : else_edge); 3216169689Skan if (EDGE_COUNT (trap_bb->preds) == 0) 3217169689Skan delete_basic_block (trap_bb); 321890075Sobrien 321996263Sobrien /* If the non-trap block and the test are now adjacent, merge them. 322096263Sobrien Otherwise we must insert a direct branch. */ 3221117395Skan if (test_bb->next_bb == other_bb) 322296263Sobrien { 3223117395Skan struct ce_if_block new_ce_info; 322496263Sobrien delete_insn (jump); 3225132718Skan memset (&new_ce_info, '\0', sizeof (new_ce_info)); 3226117395Skan new_ce_info.test_bb = test_bb; 3227117395Skan new_ce_info.then_bb = NULL; 3228117395Skan new_ce_info.else_bb = NULL; 3229117395Skan new_ce_info.join_bb = other_bb; 3230117395Skan merge_if_block (&new_ce_info); 323196263Sobrien } 323296263Sobrien else 323396263Sobrien { 323496263Sobrien rtx lab, newjump; 323596263Sobrien 323696263Sobrien lab = JUMP_LABEL (jump); 323796263Sobrien newjump = emit_jump_insn_after (gen_jump (lab), jump); 323896263Sobrien LABEL_NUSES (lab) += 1; 323996263Sobrien JUMP_LABEL (newjump) = lab; 324096263Sobrien emit_barrier_after (newjump); 324196263Sobrien 324296263Sobrien delete_insn (jump); 324396263Sobrien } 324496263Sobrien 324590075Sobrien return TRUE; 324690075Sobrien} 324790075Sobrien 3248132718Skan/* Subroutine of find_cond_trap: if BB contains only a trap insn, 324996263Sobrien return it. */ 325096263Sobrien 325196263Sobrienstatic rtx 3252132718Skanblock_has_only_trap (basic_block bb) 325396263Sobrien{ 325496263Sobrien rtx trap; 325596263Sobrien 325696263Sobrien /* We're not the exit block. */ 325796263Sobrien if (bb == EXIT_BLOCK_PTR) 325896263Sobrien return NULL_RTX; 325996263Sobrien 326096263Sobrien /* The block must have no successors. */ 3261169689Skan if (EDGE_COUNT (bb->succs) > 0) 326296263Sobrien return NULL_RTX; 326396263Sobrien 326496263Sobrien /* The only instruction in the THEN block must be the trap. */ 326596263Sobrien trap = first_active_insn (bb); 3266132718Skan if (! (trap == BB_END (bb) 326796263Sobrien && GET_CODE (PATTERN (trap)) == TRAP_IF 326896263Sobrien && TRAP_CONDITION (PATTERN (trap)) == const_true_rtx)) 326996263Sobrien return NULL_RTX; 327096263Sobrien 327196263Sobrien return trap; 327296263Sobrien} 327396263Sobrien 327490075Sobrien/* Look for IF-THEN-ELSE cases in which one of THEN or ELSE is 327590075Sobrien transformable, but not necessarily the other. There need be no 327690075Sobrien JOIN block. 327790075Sobrien 3278117395Skan Return TRUE if we were successful at converting the block. 327990075Sobrien 328090075Sobrien Cases we'd like to look at: 328190075Sobrien 328290075Sobrien (1) 328390075Sobrien if (test) goto over; // x not live 328490075Sobrien x = a; 328590075Sobrien goto label; 328690075Sobrien over: 328790075Sobrien 328890075Sobrien becomes 328990075Sobrien 329090075Sobrien x = a; 329190075Sobrien if (! test) goto label; 329290075Sobrien 329390075Sobrien (2) 329490075Sobrien if (test) goto E; // x not live 329590075Sobrien x = big(); 329690075Sobrien goto L; 329790075Sobrien E: 329890075Sobrien x = b; 329990075Sobrien goto M; 330090075Sobrien 330190075Sobrien becomes 330290075Sobrien 330390075Sobrien x = b; 330490075Sobrien if (test) goto M; 330590075Sobrien x = big(); 330690075Sobrien goto L; 330790075Sobrien 330890075Sobrien (3) // This one's really only interesting for targets that can do 330990075Sobrien // multiway branching, e.g. IA-64 BBB bundles. For other targets 331090075Sobrien // it results in multiple branches on a cache line, which often 331190075Sobrien // does not sit well with predictors. 331290075Sobrien 331390075Sobrien if (test1) goto E; // predicted not taken 331490075Sobrien x = a; 331590075Sobrien if (test2) goto F; 331690075Sobrien ... 331790075Sobrien E: 331890075Sobrien x = b; 331990075Sobrien J: 332090075Sobrien 332190075Sobrien becomes 332290075Sobrien 332390075Sobrien x = a; 332490075Sobrien if (test1) goto E; 332590075Sobrien if (test2) goto F; 332690075Sobrien 332790075Sobrien Notes: 332890075Sobrien 332990075Sobrien (A) Don't do (2) if the branch is predicted against the block we're 333090075Sobrien eliminating. Do it anyway if we can eliminate a branch; this requires 333190075Sobrien that the sole successor of the eliminated block postdominate the other 333290075Sobrien side of the if. 333390075Sobrien 333490075Sobrien (B) With CE, on (3) we can steal from both sides of the if, creating 333590075Sobrien 333690075Sobrien if (test1) x = a; 333790075Sobrien if (!test1) x = b; 333890075Sobrien if (test1) goto J; 333990075Sobrien if (test2) goto F; 334090075Sobrien ... 334190075Sobrien J: 334290075Sobrien 334390075Sobrien Again, this is most useful if J postdominates. 334490075Sobrien 334590075Sobrien (C) CE substitutes for helpful life information. 334690075Sobrien 334790075Sobrien (D) These heuristics need a lot of work. */ 334890075Sobrien 334990075Sobrien/* Tests for case 1 above. */ 335090075Sobrien 335190075Sobrienstatic int 3352132718Skanfind_if_case_1 (basic_block test_bb, edge then_edge, edge else_edge) 335390075Sobrien{ 335490075Sobrien basic_block then_bb = then_edge->dest; 335590075Sobrien basic_block else_bb = else_edge->dest, new_bb; 3356117395Skan int then_bb_index; 335790075Sobrien 3358169689Skan /* If we are partitioning hot/cold basic blocks, we don't want to 3359169689Skan mess up unconditional or indirect jumps that cross between hot 3360169689Skan and cold sections. 3361169689Skan 3362169689Skan Basic block partitioning may result in some jumps that appear to 3363169689Skan be optimizable (or blocks that appear to be mergeable), but which really 3364169689Skan must be left untouched (they are required to make it safely across 3365169689Skan partition boundaries). See the comments at the top of 3366169689Skan bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */ 3367169689Skan 3368169689Skan if ((BB_END (then_bb) 3369169689Skan && find_reg_note (BB_END (then_bb), REG_CROSSING_JUMP, NULL_RTX)) 3370169689Skan || (BB_END (test_bb) 3371169689Skan && find_reg_note (BB_END (test_bb), REG_CROSSING_JUMP, NULL_RTX)) 3372169689Skan || (BB_END (else_bb) 3373169689Skan && find_reg_note (BB_END (else_bb), REG_CROSSING_JUMP, 3374169689Skan NULL_RTX))) 3375169689Skan return FALSE; 3376169689Skan 337790075Sobrien /* THEN has one successor. */ 3378169689Skan if (!single_succ_p (then_bb)) 337990075Sobrien return FALSE; 338090075Sobrien 338190075Sobrien /* THEN does not fall through, but is not strange either. */ 3382169689Skan if (single_succ_edge (then_bb)->flags & (EDGE_COMPLEX | EDGE_FALLTHRU)) 338390075Sobrien return FALSE; 338490075Sobrien 338590075Sobrien /* THEN has one predecessor. */ 3386169689Skan if (!single_pred_p (then_bb)) 338790075Sobrien return FALSE; 338890075Sobrien 338990075Sobrien /* THEN must do something. */ 339090075Sobrien if (forwarder_block_p (then_bb)) 339190075Sobrien return FALSE; 339290075Sobrien 339390075Sobrien num_possible_if_blocks++; 3394169689Skan if (dump_file) 3395169689Skan fprintf (dump_file, 339690075Sobrien "\nIF-CASE-1 found, start %d, then %d\n", 339790075Sobrien test_bb->index, then_bb->index); 339890075Sobrien 339990075Sobrien /* THEN is small. */ 3400169689Skan if (! cheap_bb_rtx_cost_p (then_bb, COSTS_N_INSNS (BRANCH_COST))) 340190075Sobrien return FALSE; 340290075Sobrien 340390075Sobrien /* Registers set are dead, or are predicable. */ 3404132718Skan if (! dead_or_predicable (test_bb, then_bb, else_bb, 3405169689Skan single_succ (then_bb), 1)) 340690075Sobrien return FALSE; 340790075Sobrien 340890075Sobrien /* Conversion went ok, including moving the insns and fixing up the 340990075Sobrien jump. Adjust the CFG to match. */ 341090075Sobrien 3411169689Skan bitmap_ior (test_bb->il.rtl->global_live_at_end, 3412169689Skan else_bb->il.rtl->global_live_at_start, 3413169689Skan then_bb->il.rtl->global_live_at_end); 3414132718Skan 3415169689Skan 3416169689Skan /* We can avoid creating a new basic block if then_bb is immediately 3417169689Skan followed by else_bb, i.e. deleting then_bb allows test_bb to fall 3418169689Skan thru to else_bb. */ 3419169689Skan 3420169689Skan if (then_bb->next_bb == else_bb 3421169689Skan && then_bb->prev_bb == test_bb 3422169689Skan && else_bb != EXIT_BLOCK_PTR) 3423169689Skan { 3424169689Skan redirect_edge_succ (FALLTHRU_EDGE (test_bb), else_bb); 3425169689Skan new_bb = 0; 3426169689Skan } 3427169689Skan else 3428169689Skan new_bb = redirect_edge_and_branch_force (FALLTHRU_EDGE (test_bb), 3429169689Skan else_bb); 3430169689Skan 3431117395Skan then_bb_index = then_bb->index; 3432169689Skan delete_basic_block (then_bb); 3433117395Skan 343490075Sobrien /* Make rest of code believe that the newly created block is the THEN_BB 3435117395Skan block we removed. */ 343690075Sobrien if (new_bb) 343790075Sobrien { 3438117395Skan new_bb->index = then_bb_index; 3439169689Skan SET_BASIC_BLOCK (then_bb_index, new_bb); 3440169689Skan /* Since the fallthru edge was redirected from test_bb to new_bb, 3441169689Skan we need to ensure that new_bb is in the same partition as 3442169689Skan test bb (you can not fall through across section boundaries). */ 3443169689Skan BB_COPY_PARTITION (new_bb, test_bb); 344490075Sobrien } 344590075Sobrien /* We've possibly created jump to next insn, cleanup_cfg will solve that 344690075Sobrien later. */ 344790075Sobrien 3448132718Skan num_true_changes++; 344990075Sobrien num_updated_if_blocks++; 345090075Sobrien 345190075Sobrien return TRUE; 345290075Sobrien} 345390075Sobrien 345490075Sobrien/* Test for case 2 above. */ 345590075Sobrien 345690075Sobrienstatic int 3457132718Skanfind_if_case_2 (basic_block test_bb, edge then_edge, edge else_edge) 345890075Sobrien{ 345990075Sobrien basic_block then_bb = then_edge->dest; 346090075Sobrien basic_block else_bb = else_edge->dest; 3461169689Skan edge else_succ; 346290075Sobrien rtx note; 346390075Sobrien 3464169689Skan /* If we are partitioning hot/cold basic blocks, we don't want to 3465169689Skan mess up unconditional or indirect jumps that cross between hot 3466169689Skan and cold sections. 3467169689Skan 3468169689Skan Basic block partitioning may result in some jumps that appear to 3469169689Skan be optimizable (or blocks that appear to be mergeable), but which really 3470169689Skan must be left untouched (they are required to make it safely across 3471169689Skan partition boundaries). See the comments at the top of 3472169689Skan bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */ 3473169689Skan 3474169689Skan if ((BB_END (then_bb) 3475169689Skan && find_reg_note (BB_END (then_bb), REG_CROSSING_JUMP, NULL_RTX)) 3476169689Skan || (BB_END (test_bb) 3477169689Skan && find_reg_note (BB_END (test_bb), REG_CROSSING_JUMP, NULL_RTX)) 3478169689Skan || (BB_END (else_bb) 3479169689Skan && find_reg_note (BB_END (else_bb), REG_CROSSING_JUMP, 3480169689Skan NULL_RTX))) 3481169689Skan return FALSE; 3482169689Skan 348390075Sobrien /* ELSE has one successor. */ 3484169689Skan if (!single_succ_p (else_bb)) 348590075Sobrien return FALSE; 3486169689Skan else 3487169689Skan else_succ = single_succ_edge (else_bb); 348890075Sobrien 348990075Sobrien /* ELSE outgoing edge is not complex. */ 349090075Sobrien if (else_succ->flags & EDGE_COMPLEX) 349190075Sobrien return FALSE; 349290075Sobrien 349390075Sobrien /* ELSE has one predecessor. */ 3494169689Skan if (!single_pred_p (else_bb)) 349590075Sobrien return FALSE; 349690075Sobrien 349790075Sobrien /* THEN is not EXIT. */ 3498169689Skan if (then_bb->index < NUM_FIXED_BLOCKS) 349990075Sobrien return FALSE; 350090075Sobrien 350190075Sobrien /* ELSE is predicted or SUCC(ELSE) postdominates THEN. */ 3502132718Skan note = find_reg_note (BB_END (test_bb), REG_BR_PROB, NULL_RTX); 350390075Sobrien if (note && INTVAL (XEXP (note, 0)) >= REG_BR_PROB_BASE / 2) 350490075Sobrien ; 3505169689Skan else if (else_succ->dest->index < NUM_FIXED_BLOCKS 3506132718Skan || dominated_by_p (CDI_POST_DOMINATORS, then_bb, 3507117395Skan else_succ->dest)) 350890075Sobrien ; 350990075Sobrien else 351090075Sobrien return FALSE; 351190075Sobrien 351290075Sobrien num_possible_if_blocks++; 3513169689Skan if (dump_file) 3514169689Skan fprintf (dump_file, 351590075Sobrien "\nIF-CASE-2 found, start %d, else %d\n", 351690075Sobrien test_bb->index, else_bb->index); 351790075Sobrien 351890075Sobrien /* ELSE is small. */ 3519169689Skan if (! cheap_bb_rtx_cost_p (else_bb, COSTS_N_INSNS (BRANCH_COST))) 352090075Sobrien return FALSE; 352190075Sobrien 352290075Sobrien /* Registers set are dead, or are predicable. */ 352390075Sobrien if (! dead_or_predicable (test_bb, else_bb, then_bb, else_succ->dest, 0)) 352490075Sobrien return FALSE; 352590075Sobrien 352690075Sobrien /* Conversion went ok, including moving the insns and fixing up the 352790075Sobrien jump. Adjust the CFG to match. */ 352890075Sobrien 3529169689Skan bitmap_ior (test_bb->il.rtl->global_live_at_end, 3530169689Skan then_bb->il.rtl->global_live_at_start, 3531169689Skan else_bb->il.rtl->global_live_at_end); 353290075Sobrien 3533169689Skan delete_basic_block (else_bb); 3534132718Skan 3535132718Skan num_true_changes++; 353690075Sobrien num_updated_if_blocks++; 353790075Sobrien 353890075Sobrien /* ??? We may now fallthru from one of THEN's successors into a join 353990075Sobrien block. Rerun cleanup_cfg? Examine things manually? Wait? */ 354090075Sobrien 354190075Sobrien return TRUE; 354290075Sobrien} 354390075Sobrien 354490075Sobrien/* A subroutine of dead_or_predicable called through for_each_rtx. 354590075Sobrien Return 1 if a memory is found. */ 354690075Sobrien 354790075Sobrienstatic int 3548132718Skanfind_memory (rtx *px, void *data ATTRIBUTE_UNUSED) 354990075Sobrien{ 3550169689Skan return MEM_P (*px); 355190075Sobrien} 355290075Sobrien 355390075Sobrien/* Used by the code above to perform the actual rtl transformations. 355490075Sobrien Return TRUE if successful. 355590075Sobrien 355690075Sobrien TEST_BB is the block containing the conditional branch. MERGE_BB 355790075Sobrien is the block containing the code to manipulate. NEW_DEST is the 355890075Sobrien label TEST_BB should be branching to after the conversion. 355990075Sobrien REVERSEP is true if the sense of the branch should be reversed. */ 356090075Sobrien 356190075Sobrienstatic int 3562132718Skandead_or_predicable (basic_block test_bb, basic_block merge_bb, 3563132718Skan basic_block other_bb, basic_block new_dest, int reversep) 356490075Sobrien{ 3565169689Skan rtx head, end, jump, earliest = NULL_RTX, old_dest, new_label = NULL_RTX; 356690075Sobrien 3567132718Skan jump = BB_END (test_bb); 356890075Sobrien 356990075Sobrien /* Find the extent of the real code in the merge block. */ 3570132718Skan head = BB_HEAD (merge_bb); 3571132718Skan end = BB_END (merge_bb); 357290075Sobrien 3573169689Skan /* If merge_bb ends with a tablejump, predicating/moving insn's 3574169689Skan into test_bb and then deleting merge_bb will result in the jumptable 3575169689Skan that follows merge_bb being removed along with merge_bb and then we 3576169689Skan get an unresolved reference to the jumptable. */ 3577169689Skan if (tablejump_p (end, NULL, NULL)) 3578169689Skan return FALSE; 3579169689Skan 3580169689Skan if (LABEL_P (head)) 358190075Sobrien head = NEXT_INSN (head); 3582169689Skan if (NOTE_P (head)) 358390075Sobrien { 358490075Sobrien if (head == end) 358590075Sobrien { 358690075Sobrien head = end = NULL_RTX; 358790075Sobrien goto no_body; 358890075Sobrien } 358990075Sobrien head = NEXT_INSN (head); 359090075Sobrien } 359190075Sobrien 3592169689Skan if (JUMP_P (end)) 359390075Sobrien { 359490075Sobrien if (head == end) 359590075Sobrien { 359690075Sobrien head = end = NULL_RTX; 359790075Sobrien goto no_body; 359890075Sobrien } 359990075Sobrien end = PREV_INSN (end); 360090075Sobrien } 360190075Sobrien 360290075Sobrien /* Disable handling dead code by conditional execution if the machine needs 360390075Sobrien to do anything funny with the tests, etc. */ 360490075Sobrien#ifndef IFCVT_MODIFY_TESTS 360590075Sobrien if (HAVE_conditional_execution) 360690075Sobrien { 360790075Sobrien /* In the conditional execution case, we have things easy. We know 3608132718Skan the condition is reversible. We don't have to check life info 3609132718Skan because we're going to conditionally execute the code anyway. 361090075Sobrien All that's left is making sure the insns involved can actually 361190075Sobrien be predicated. */ 361290075Sobrien 361390075Sobrien rtx cond, prob_val; 361490075Sobrien 361590075Sobrien cond = cond_exec_get_condition (jump); 361690075Sobrien if (! cond) 361790075Sobrien return FALSE; 361890075Sobrien 361990075Sobrien prob_val = find_reg_note (jump, REG_BR_PROB, NULL_RTX); 362090075Sobrien if (prob_val) 362190075Sobrien prob_val = XEXP (prob_val, 0); 362290075Sobrien 362390075Sobrien if (reversep) 362490075Sobrien { 362590075Sobrien enum rtx_code rev = reversed_comparison_code (cond, jump); 362690075Sobrien if (rev == UNKNOWN) 362790075Sobrien return FALSE; 362890075Sobrien cond = gen_rtx_fmt_ee (rev, GET_MODE (cond), XEXP (cond, 0), 362990075Sobrien XEXP (cond, 1)); 363090075Sobrien if (prob_val) 363190075Sobrien prob_val = GEN_INT (REG_BR_PROB_BASE - INTVAL (prob_val)); 363290075Sobrien } 363390075Sobrien 3634117395Skan if (! cond_exec_process_insns ((ce_if_block_t *)0, head, end, cond, 3635117395Skan prob_val, 0)) 363690075Sobrien goto cancel; 363790075Sobrien 363890075Sobrien earliest = jump; 363990075Sobrien } 364090075Sobrien else 364190075Sobrien#endif 364290075Sobrien { 364390075Sobrien /* In the non-conditional execution case, we have to verify that there 364490075Sobrien are no trapping operations, no calls, no references to memory, and 364590075Sobrien that any registers modified are dead at the branch site. */ 364690075Sobrien 364790075Sobrien rtx insn, cond, prev; 364890075Sobrien regset merge_set, tmp, test_live, test_set; 364990075Sobrien struct propagate_block_info *pbi; 3650169689Skan unsigned i, fail = 0; 3651169689Skan bitmap_iterator bi; 365290075Sobrien 365390075Sobrien /* Check for no calls or trapping operations. */ 365490075Sobrien for (insn = head; ; insn = NEXT_INSN (insn)) 365590075Sobrien { 3656169689Skan if (CALL_P (insn)) 365790075Sobrien return FALSE; 365890075Sobrien if (INSN_P (insn)) 365990075Sobrien { 366090075Sobrien if (may_trap_p (PATTERN (insn))) 366190075Sobrien return FALSE; 366290075Sobrien 366390075Sobrien /* ??? Even non-trapping memories such as stack frame 366490075Sobrien references must be avoided. For stores, we collect 366590075Sobrien no lifetime info; for reads, we'd have to assert 366690075Sobrien true_dependence false against every store in the 366790075Sobrien TEST range. */ 366890075Sobrien if (for_each_rtx (&PATTERN (insn), find_memory, NULL)) 366990075Sobrien return FALSE; 367090075Sobrien } 367190075Sobrien if (insn == end) 367290075Sobrien break; 367390075Sobrien } 367490075Sobrien 367590075Sobrien if (! any_condjump_p (jump)) 367690075Sobrien return FALSE; 367790075Sobrien 367890075Sobrien /* Find the extent of the conditional. */ 367990075Sobrien cond = noce_get_condition (jump, &earliest); 368090075Sobrien if (! cond) 368190075Sobrien return FALSE; 368290075Sobrien 368390075Sobrien /* Collect: 368490075Sobrien MERGE_SET = set of registers set in MERGE_BB 368590075Sobrien TEST_LIVE = set of registers live at EARLIEST 368690075Sobrien TEST_SET = set of registers set between EARLIEST and the 368790075Sobrien end of the block. */ 368890075Sobrien 3689169689Skan tmp = ALLOC_REG_SET (®_obstack); 3690169689Skan merge_set = ALLOC_REG_SET (®_obstack); 3691169689Skan test_live = ALLOC_REG_SET (®_obstack); 3692169689Skan test_set = ALLOC_REG_SET (®_obstack); 369390075Sobrien 369490075Sobrien /* ??? bb->local_set is only valid during calculate_global_regs_live, 3695132718Skan so we must recompute usage for MERGE_BB. Not so bad, I suppose, 369690075Sobrien since we've already asserted that MERGE_BB is small. */ 3697169689Skan /* If we allocated new pseudos (e.g. in the conditional move 3698169689Skan expander called from noce_emit_cmove), we must resize the 3699169689Skan array first. */ 3700169689Skan if (max_regno < max_reg_num ()) 3701169689Skan { 3702169689Skan max_regno = max_reg_num (); 3703169689Skan allocate_reg_info (max_regno, FALSE, FALSE); 3704169689Skan } 370590075Sobrien propagate_block (merge_bb, tmp, merge_set, merge_set, 0); 370690075Sobrien 370790075Sobrien /* For small register class machines, don't lengthen lifetimes of 370890075Sobrien hard registers before reload. */ 370990075Sobrien if (SMALL_REGISTER_CLASSES && ! reload_completed) 371090075Sobrien { 3711169689Skan EXECUTE_IF_SET_IN_BITMAP (merge_set, 0, i, bi) 3712169689Skan { 3713169689Skan if (i < FIRST_PSEUDO_REGISTER 3714169689Skan && ! fixed_regs[i] 3715169689Skan && ! global_regs[i]) 371690075Sobrien fail = 1; 3717169689Skan } 371890075Sobrien } 371990075Sobrien 372090075Sobrien /* For TEST, we're interested in a range of insns, not a whole block. 372190075Sobrien Moreover, we're interested in the insns live from OTHER_BB. */ 372290075Sobrien 3723169689Skan COPY_REG_SET (test_live, other_bb->il.rtl->global_live_at_start); 372490075Sobrien pbi = init_propagate_block_info (test_bb, test_live, test_set, test_set, 372590075Sobrien 0); 372690075Sobrien 372790075Sobrien for (insn = jump; ; insn = prev) 372890075Sobrien { 372990075Sobrien prev = propagate_one_insn (pbi, insn); 373090075Sobrien if (insn == earliest) 373190075Sobrien break; 373290075Sobrien } 373390075Sobrien 373490075Sobrien free_propagate_block_info (pbi); 373590075Sobrien 373690075Sobrien /* We can perform the transformation if 373790075Sobrien MERGE_SET & (TEST_SET | TEST_LIVE) 373890075Sobrien and 3739169689Skan TEST_SET & merge_bb->il.rtl->global_live_at_start 374090075Sobrien are empty. */ 374190075Sobrien 3742169689Skan if (bitmap_intersect_p (test_set, merge_set) 3743169689Skan || bitmap_intersect_p (test_live, merge_set) 3744169689Skan || bitmap_intersect_p (test_set, 3745169689Skan merge_bb->il.rtl->global_live_at_start)) 3746169689Skan fail = 1; 374790075Sobrien 374890075Sobrien FREE_REG_SET (tmp); 374990075Sobrien FREE_REG_SET (merge_set); 375090075Sobrien FREE_REG_SET (test_live); 375190075Sobrien FREE_REG_SET (test_set); 375290075Sobrien 375390075Sobrien if (fail) 375490075Sobrien return FALSE; 375590075Sobrien } 375690075Sobrien 375790075Sobrien no_body: 375890075Sobrien /* We don't want to use normal invert_jump or redirect_jump because 375990075Sobrien we don't want to delete_insn called. Also, we want to do our own 376090075Sobrien change group management. */ 376190075Sobrien 376290075Sobrien old_dest = JUMP_LABEL (jump); 376390075Sobrien if (other_bb != new_dest) 376490075Sobrien { 376590075Sobrien new_label = block_label (new_dest); 376690075Sobrien if (reversep 376790075Sobrien ? ! invert_jump_1 (jump, new_label) 376890075Sobrien : ! redirect_jump_1 (jump, new_label)) 376990075Sobrien goto cancel; 377090075Sobrien } 377190075Sobrien 377290075Sobrien if (! apply_change_group ()) 377390075Sobrien return FALSE; 377490075Sobrien 377590075Sobrien if (other_bb != new_dest) 377690075Sobrien { 3777169689Skan redirect_jump_2 (jump, old_dest, new_label, -1, reversep); 377890075Sobrien 377990075Sobrien redirect_edge_succ (BRANCH_EDGE (test_bb), new_dest); 378090075Sobrien if (reversep) 378190075Sobrien { 378290075Sobrien gcov_type count, probability; 378390075Sobrien count = BRANCH_EDGE (test_bb)->count; 378490075Sobrien BRANCH_EDGE (test_bb)->count = FALLTHRU_EDGE (test_bb)->count; 378590075Sobrien FALLTHRU_EDGE (test_bb)->count = count; 378690075Sobrien probability = BRANCH_EDGE (test_bb)->probability; 378790075Sobrien BRANCH_EDGE (test_bb)->probability 378890075Sobrien = FALLTHRU_EDGE (test_bb)->probability; 378990075Sobrien FALLTHRU_EDGE (test_bb)->probability = probability; 379090075Sobrien update_br_prob_note (test_bb); 379190075Sobrien } 379290075Sobrien } 379390075Sobrien 379490075Sobrien /* Move the insns out of MERGE_BB to before the branch. */ 379590075Sobrien if (head != NULL) 379690075Sobrien { 3797169689Skan rtx insn; 3798169689Skan 3799132718Skan if (end == BB_END (merge_bb)) 3800132718Skan BB_END (merge_bb) = PREV_INSN (head); 380190075Sobrien 380290075Sobrien if (squeeze_notes (&head, &end)) 380390075Sobrien return TRUE; 380490075Sobrien 3805169689Skan /* PR 21767: When moving insns above a conditional branch, REG_EQUAL 3806169689Skan notes might become invalid. */ 3807169689Skan insn = head; 3808169689Skan do 3809169689Skan { 3810169689Skan rtx note, set; 3811169689Skan 3812169689Skan if (! INSN_P (insn)) 3813169689Skan continue; 3814169689Skan note = find_reg_note (insn, REG_EQUAL, NULL_RTX); 3815169689Skan if (! note) 3816169689Skan continue; 3817169689Skan set = single_set (insn); 3818169689Skan if (!set || !function_invariant_p (SET_SRC (set))) 3819169689Skan remove_note (insn, note); 3820169689Skan } while (insn != end && (insn = NEXT_INSN (insn))); 3821169689Skan 382290075Sobrien reorder_insns (head, end, PREV_INSN (earliest)); 382390075Sobrien } 382490075Sobrien 382590075Sobrien /* Remove the jump and edge if we can. */ 382690075Sobrien if (other_bb == new_dest) 382790075Sobrien { 382890075Sobrien delete_insn (jump); 382990075Sobrien remove_edge (BRANCH_EDGE (test_bb)); 383090075Sobrien /* ??? Can't merge blocks here, as then_bb is still in use. 383190075Sobrien At minimum, the merge will get done just before bb-reorder. */ 383290075Sobrien } 383390075Sobrien 383490075Sobrien return TRUE; 383590075Sobrien 383690075Sobrien cancel: 383790075Sobrien cancel_changes (0); 383890075Sobrien return FALSE; 383990075Sobrien} 384090075Sobrien 384190075Sobrien/* Main entry point for all if-conversion. */ 384290075Sobrien 3843169689Skanstatic void 3844132718Skanif_convert (int x_life_data_ok) 384590075Sobrien{ 3846117395Skan basic_block bb; 3847117395Skan int pass; 384890075Sobrien 384990075Sobrien num_possible_if_blocks = 0; 385090075Sobrien num_updated_if_blocks = 0; 3851132718Skan num_true_changes = 0; 385290075Sobrien life_data_ok = (x_life_data_ok != 0); 385390075Sobrien 3854169689Skan if ((! targetm.cannot_modify_jumps_p ()) 3855169689Skan && (!flag_reorder_blocks_and_partition || !no_new_pseudos 3856169689Skan || !targetm.have_named_sections)) 3857169689Skan { 3858169689Skan struct loops loops; 3859132718Skan 3860169689Skan flow_loops_find (&loops); 3861169689Skan mark_loop_exit_edges (&loops); 3862169689Skan flow_loops_free (&loops); 3863169689Skan free_dominance_info (CDI_DOMINATORS); 3864169689Skan } 386590075Sobrien 386690075Sobrien /* Compute postdominators if we think we'll use them. */ 386790075Sobrien if (HAVE_conditional_execution || life_data_ok) 3868132718Skan calculate_dominance_info (CDI_POST_DOMINATORS); 3869132718Skan 3870117395Skan if (life_data_ok) 3871117395Skan clear_bb_flags (); 387290075Sobrien 3873117395Skan /* Go through each of the basic blocks looking for things to convert. If we 3874117395Skan have conditional execution, we make multiple passes to allow us to handle 3875117395Skan IF-THEN{-ELSE} blocks within other IF-THEN{-ELSE} blocks. */ 3876117395Skan pass = 0; 3877117395Skan do 3878117395Skan { 3879117395Skan cond_exec_changed_p = FALSE; 3880117395Skan pass++; 388190075Sobrien 3882117395Skan#ifdef IFCVT_MULTIPLE_DUMPS 3883169689Skan if (dump_file && pass > 1) 3884169689Skan fprintf (dump_file, "\n\n========== Pass %d ==========\n", pass); 3885117395Skan#endif 3886117395Skan 3887117395Skan FOR_EACH_BB (bb) 3888117395Skan { 3889117395Skan basic_block new_bb; 3890117395Skan while ((new_bb = find_if_header (bb, pass))) 3891117395Skan bb = new_bb; 3892117395Skan } 3893117395Skan 3894117395Skan#ifdef IFCVT_MULTIPLE_DUMPS 3895169689Skan if (dump_file && cond_exec_changed_p) 3896169689Skan print_rtl_with_bb (dump_file, get_insns ()); 3897117395Skan#endif 389890075Sobrien } 3899117395Skan while (cond_exec_changed_p); 390090075Sobrien 3901117395Skan#ifdef IFCVT_MULTIPLE_DUMPS 3902169689Skan if (dump_file) 3903169689Skan fprintf (dump_file, "\n\n========== no more changes\n"); 3904117395Skan#endif 3905117395Skan 3906132718Skan free_dominance_info (CDI_POST_DOMINATORS); 390790075Sobrien 3908169689Skan if (dump_file) 3909169689Skan fflush (dump_file); 391090075Sobrien 3911117395Skan clear_aux_for_blocks (); 3912117395Skan 391390075Sobrien /* Rebuild life info for basic blocks that require it. */ 3914132718Skan if (num_true_changes && life_data_ok) 391590075Sobrien { 391690075Sobrien /* If we allocated new pseudos, we must resize the array for sched1. */ 391790075Sobrien if (max_regno < max_reg_num ()) 391890075Sobrien { 391990075Sobrien max_regno = max_reg_num (); 392090075Sobrien allocate_reg_info (max_regno, FALSE, FALSE); 392190075Sobrien } 3922117395Skan update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES, 3923117395Skan PROP_DEATH_NOTES | PROP_SCAN_DEAD_CODE 3924117395Skan | PROP_KILL_DEAD_CODE); 392590075Sobrien } 392690075Sobrien 392790075Sobrien /* Write the final stats. */ 3928169689Skan if (dump_file && num_possible_if_blocks > 0) 392990075Sobrien { 3930169689Skan fprintf (dump_file, 393190075Sobrien "\n%d possible IF blocks searched.\n", 393290075Sobrien num_possible_if_blocks); 3933169689Skan fprintf (dump_file, 393490075Sobrien "%d IF blocks converted.\n", 393590075Sobrien num_updated_if_blocks); 3936169689Skan fprintf (dump_file, 3937132718Skan "%d true changes made.\n\n\n", 3938132718Skan num_true_changes); 393990075Sobrien } 394090075Sobrien 394190075Sobrien#ifdef ENABLE_CHECKING 394290075Sobrien verify_flow_info (); 394390075Sobrien#endif 394490075Sobrien} 3945169689Skan 3946169689Skanstatic bool 3947169689Skangate_handle_if_conversion (void) 3948169689Skan{ 3949169689Skan return (optimize > 0); 3950169689Skan} 3951169689Skan 3952169689Skan/* If-conversion and CFG cleanup. */ 3953169689Skanstatic unsigned int 3954169689Skanrest_of_handle_if_conversion (void) 3955169689Skan{ 3956169689Skan if (flag_if_conversion) 3957169689Skan { 3958169689Skan if (dump_file) 3959169689Skan dump_flow_info (dump_file, dump_flags); 3960169689Skan cleanup_cfg (CLEANUP_EXPENSIVE); 3961169689Skan reg_scan (get_insns (), max_reg_num ()); 3962169689Skan if_convert (0); 3963169689Skan } 3964169689Skan 3965169689Skan timevar_push (TV_JUMP); 3966169689Skan cleanup_cfg (CLEANUP_EXPENSIVE); 3967169689Skan reg_scan (get_insns (), max_reg_num ()); 3968169689Skan timevar_pop (TV_JUMP); 3969169689Skan return 0; 3970169689Skan} 3971169689Skan 3972169689Skanstruct tree_opt_pass pass_rtl_ifcvt = 3973169689Skan{ 3974169689Skan "ce1", /* name */ 3975169689Skan gate_handle_if_conversion, /* gate */ 3976169689Skan rest_of_handle_if_conversion, /* execute */ 3977169689Skan NULL, /* sub */ 3978169689Skan NULL, /* next */ 3979169689Skan 0, /* static_pass_number */ 3980169689Skan TV_IFCVT, /* tv_id */ 3981169689Skan 0, /* properties_required */ 3982169689Skan 0, /* properties_provided */ 3983169689Skan 0, /* properties_destroyed */ 3984169689Skan 0, /* todo_flags_start */ 3985169689Skan TODO_dump_func, /* todo_flags_finish */ 3986169689Skan 'C' /* letter */ 3987169689Skan}; 3988169689Skan 3989169689Skanstatic bool 3990169689Skangate_handle_if_after_combine (void) 3991169689Skan{ 3992169689Skan return (optimize > 0 && flag_if_conversion); 3993169689Skan} 3994169689Skan 3995169689Skan 3996169689Skan/* Rerun if-conversion, as combine may have simplified things enough 3997169689Skan to now meet sequence length restrictions. */ 3998169689Skanstatic unsigned int 3999169689Skanrest_of_handle_if_after_combine (void) 4000169689Skan{ 4001169689Skan no_new_pseudos = 0; 4002169689Skan if_convert (1); 4003169689Skan no_new_pseudos = 1; 4004169689Skan return 0; 4005169689Skan} 4006169689Skan 4007169689Skanstruct tree_opt_pass pass_if_after_combine = 4008169689Skan{ 4009169689Skan "ce2", /* name */ 4010169689Skan gate_handle_if_after_combine, /* gate */ 4011169689Skan rest_of_handle_if_after_combine, /* execute */ 4012169689Skan NULL, /* sub */ 4013169689Skan NULL, /* next */ 4014169689Skan 0, /* static_pass_number */ 4015169689Skan TV_IFCVT, /* tv_id */ 4016169689Skan 0, /* properties_required */ 4017169689Skan 0, /* properties_provided */ 4018169689Skan 0, /* properties_destroyed */ 4019169689Skan 0, /* todo_flags_start */ 4020169689Skan TODO_dump_func | 4021169689Skan TODO_ggc_collect, /* todo_flags_finish */ 4022169689Skan 'C' /* letter */ 4023169689Skan}; 4024169689Skan 4025169689Skan 4026169689Skanstatic bool 4027169689Skangate_handle_if_after_reload (void) 4028169689Skan{ 4029169689Skan return (optimize > 0); 4030169689Skan} 4031169689Skan 4032169689Skanstatic unsigned int 4033169689Skanrest_of_handle_if_after_reload (void) 4034169689Skan{ 4035169689Skan /* Last attempt to optimize CFG, as scheduling, peepholing and insn 4036169689Skan splitting possibly introduced more crossjumping opportunities. */ 4037169689Skan cleanup_cfg (CLEANUP_EXPENSIVE 4038169689Skan | CLEANUP_UPDATE_LIFE 4039169689Skan | (flag_crossjumping ? CLEANUP_CROSSJUMP : 0)); 4040169689Skan if (flag_if_conversion2) 4041169689Skan if_convert (1); 4042169689Skan return 0; 4043169689Skan} 4044169689Skan 4045169689Skan 4046169689Skanstruct tree_opt_pass pass_if_after_reload = 4047169689Skan{ 4048169689Skan "ce3", /* name */ 4049169689Skan gate_handle_if_after_reload, /* gate */ 4050169689Skan rest_of_handle_if_after_reload, /* execute */ 4051169689Skan NULL, /* sub */ 4052169689Skan NULL, /* next */ 4053169689Skan 0, /* static_pass_number */ 4054169689Skan TV_IFCVT2, /* tv_id */ 4055169689Skan 0, /* properties_required */ 4056169689Skan 0, /* properties_provided */ 4057169689Skan 0, /* properties_destroyed */ 4058169689Skan 0, /* todo_flags_start */ 4059169689Skan TODO_dump_func | 4060169689Skan TODO_ggc_collect, /* todo_flags_finish */ 4061169689Skan 'E' /* letter */ 4062169689Skan}; 4063169689Skan 4064169689Skan 4065