ifcvt.c revision 146895
190075Sobrien/* If-conversion support. 2132718Skan Copyright (C) 2000, 2001, 2002, 2003 Free Software Foundation, Inc. 390075Sobrien 490075Sobrien This file is part of GCC. 590075Sobrien 690075Sobrien GCC is free software; you can redistribute it and/or modify it 790075Sobrien under the terms of the GNU General Public License as published by 890075Sobrien the Free Software Foundation; either version 2, or (at your option) 990075Sobrien any later version. 1090075Sobrien 1190075Sobrien GCC is distributed in the hope that it will be useful, but WITHOUT 1290075Sobrien ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 1390075Sobrien or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public 1490075Sobrien License for more details. 1590075Sobrien 1690075Sobrien You should have received a copy of the GNU General Public License 1790075Sobrien along with GCC; see the file COPYING. If not, write to the Free 1890075Sobrien Software Foundation, 59 Temple Place - Suite 330, Boston, MA 1990075Sobrien 02111-1307, USA. */ 2090075Sobrien 2190075Sobrien#include "config.h" 2290075Sobrien#include "system.h" 23132718Skan#include "coretypes.h" 24132718Skan#include "tm.h" 2590075Sobrien 2690075Sobrien#include "rtl.h" 2790075Sobrien#include "regs.h" 2890075Sobrien#include "function.h" 2990075Sobrien#include "flags.h" 3090075Sobrien#include "insn-config.h" 3190075Sobrien#include "recog.h" 3296263Sobrien#include "except.h" 3390075Sobrien#include "hard-reg-set.h" 3490075Sobrien#include "basic-block.h" 3590075Sobrien#include "expr.h" 3690075Sobrien#include "real.h" 3790075Sobrien#include "output.h" 38132718Skan#include "optabs.h" 3990075Sobrien#include "toplev.h" 4090075Sobrien#include "tm_p.h" 41132718Skan#include "cfgloop.h" 42132718Skan#include "target.h" 4390075Sobrien 4490075Sobrien 4590075Sobrien#ifndef HAVE_conditional_execution 4690075Sobrien#define HAVE_conditional_execution 0 4790075Sobrien#endif 4890075Sobrien#ifndef HAVE_conditional_move 4990075Sobrien#define HAVE_conditional_move 0 5090075Sobrien#endif 5190075Sobrien#ifndef HAVE_incscc 5290075Sobrien#define HAVE_incscc 0 5390075Sobrien#endif 5490075Sobrien#ifndef HAVE_decscc 5590075Sobrien#define HAVE_decscc 0 5690075Sobrien#endif 5790075Sobrien#ifndef HAVE_trap 5890075Sobrien#define HAVE_trap 0 5990075Sobrien#endif 6090075Sobrien#ifndef HAVE_conditional_trap 6190075Sobrien#define HAVE_conditional_trap 0 6290075Sobrien#endif 6390075Sobrien 6490075Sobrien#ifndef MAX_CONDITIONAL_EXECUTE 6590075Sobrien#define MAX_CONDITIONAL_EXECUTE (BRANCH_COST + 1) 6690075Sobrien#endif 6790075Sobrien 6890075Sobrien#define NULL_EDGE ((struct edge_def *)NULL) 6990075Sobrien#define NULL_BLOCK ((struct basic_block_def *)NULL) 7090075Sobrien 7190075Sobrien/* # of IF-THEN or IF-THEN-ELSE blocks we looked at */ 7290075Sobrienstatic int num_possible_if_blocks; 7390075Sobrien 7490075Sobrien/* # of IF-THEN or IF-THEN-ELSE blocks were converted to conditional 7590075Sobrien execution. */ 7690075Sobrienstatic int num_updated_if_blocks; 7790075Sobrien 78132718Skan/* # of changes made which require life information to be updated. */ 79132718Skanstatic int num_true_changes; 8090075Sobrien 81117395Skan/* Whether conditional execution changes were made. */ 82117395Skanstatic int cond_exec_changed_p; 83117395Skan 8490075Sobrien/* True if life data ok at present. */ 8590075Sobrienstatic bool life_data_ok; 8690075Sobrien 8790075Sobrien/* Forward references. */ 88132718Skanstatic int count_bb_insns (basic_block); 89132718Skanstatic rtx first_active_insn (basic_block); 90132718Skanstatic rtx last_active_insn (basic_block, int); 91132718Skanstatic int seq_contains_jump (rtx); 92132718Skanstatic basic_block block_fallthru (basic_block); 93132718Skanstatic int cond_exec_process_insns (ce_if_block_t *, rtx, rtx, rtx, rtx, int); 94132718Skanstatic rtx cond_exec_get_condition (rtx); 95132718Skanstatic int cond_exec_process_if_block (ce_if_block_t *, int); 96132718Skanstatic rtx noce_get_condition (rtx, rtx *); 97132718Skanstatic int noce_operand_ok (rtx); 98132718Skanstatic int noce_process_if_block (ce_if_block_t *); 99132718Skanstatic int process_if_block (ce_if_block_t *); 100132718Skanstatic void merge_if_block (ce_if_block_t *); 101132718Skanstatic int find_cond_trap (basic_block, edge, edge); 102132718Skanstatic basic_block find_if_header (basic_block, int); 103132718Skanstatic int block_jumps_and_fallthru_p (basic_block, basic_block); 104132718Skanstatic int find_if_block (ce_if_block_t *); 105132718Skanstatic int find_if_case_1 (basic_block, edge, edge); 106132718Skanstatic int find_if_case_2 (basic_block, edge, edge); 107132718Skanstatic int find_memory (rtx *, void *); 108132718Skanstatic int dead_or_predicable (basic_block, basic_block, basic_block, 109132718Skan basic_block, int); 110132718Skanstatic void noce_emit_move_insn (rtx, rtx); 111132718Skanstatic rtx block_has_only_trap (basic_block); 112132718Skanstatic void mark_loop_exit_edges (void); 11390075Sobrien 114132718Skan/* Sets EDGE_LOOP_EXIT flag for all loop exits. */ 115132718Skanstatic void 116132718Skanmark_loop_exit_edges (void) 117132718Skan{ 118132718Skan struct loops loops; 119132718Skan basic_block bb; 120132718Skan edge e; 121132718Skan 122132718Skan flow_loops_find (&loops, LOOP_TREE); 123132718Skan free_dominance_info (CDI_DOMINATORS); 124132718Skan 125132718Skan if (loops.num > 1) 126132718Skan { 127132718Skan FOR_EACH_BB (bb) 128132718Skan { 129132718Skan for (e = bb->succ; e; e = e->succ_next) 130132718Skan { 131132718Skan if (find_common_loop (bb->loop_father, e->dest->loop_father) 132132718Skan != bb->loop_father) 133132718Skan e->flags |= EDGE_LOOP_EXIT; 134132718Skan else 135132718Skan e->flags &= ~EDGE_LOOP_EXIT; 136132718Skan } 137132718Skan } 138132718Skan } 139132718Skan 140132718Skan flow_loops_free (&loops); 141132718Skan} 142132718Skan 14390075Sobrien/* Count the number of non-jump active insns in BB. */ 14490075Sobrien 14590075Sobrienstatic int 146132718Skancount_bb_insns (basic_block bb) 14790075Sobrien{ 14890075Sobrien int count = 0; 149132718Skan rtx insn = BB_HEAD (bb); 15090075Sobrien 15190075Sobrien while (1) 15290075Sobrien { 15390075Sobrien if (GET_CODE (insn) == CALL_INSN || GET_CODE (insn) == INSN) 15490075Sobrien count++; 15590075Sobrien 156132718Skan if (insn == BB_END (bb)) 15790075Sobrien break; 15890075Sobrien insn = NEXT_INSN (insn); 15990075Sobrien } 16090075Sobrien 16190075Sobrien return count; 16290075Sobrien} 16390075Sobrien 16490075Sobrien/* Return the first non-jump active insn in the basic block. */ 16590075Sobrien 16690075Sobrienstatic rtx 167132718Skanfirst_active_insn (basic_block bb) 16890075Sobrien{ 169132718Skan rtx insn = BB_HEAD (bb); 17090075Sobrien 17190075Sobrien if (GET_CODE (insn) == CODE_LABEL) 17290075Sobrien { 173132718Skan if (insn == BB_END (bb)) 17490075Sobrien return NULL_RTX; 17590075Sobrien insn = NEXT_INSN (insn); 17690075Sobrien } 17790075Sobrien 17890075Sobrien while (GET_CODE (insn) == NOTE) 17990075Sobrien { 180132718Skan if (insn == BB_END (bb)) 18190075Sobrien return NULL_RTX; 18290075Sobrien insn = NEXT_INSN (insn); 18390075Sobrien } 18490075Sobrien 18590075Sobrien if (GET_CODE (insn) == JUMP_INSN) 18690075Sobrien return NULL_RTX; 18790075Sobrien 18890075Sobrien return insn; 18990075Sobrien} 19090075Sobrien 191117395Skan/* Return the last non-jump active (non-jump) insn in the basic block. */ 19290075Sobrien 193117395Skanstatic rtx 194132718Skanlast_active_insn (basic_block bb, int skip_use_p) 19590075Sobrien{ 196132718Skan rtx insn = BB_END (bb); 197132718Skan rtx head = BB_HEAD (bb); 198117395Skan 199117395Skan while (GET_CODE (insn) == NOTE 200117395Skan || GET_CODE (insn) == JUMP_INSN 201117395Skan || (skip_use_p 202117395Skan && GET_CODE (insn) == INSN 203117395Skan && GET_CODE (PATTERN (insn)) == USE)) 20490075Sobrien { 205117395Skan if (insn == head) 206117395Skan return NULL_RTX; 207117395Skan insn = PREV_INSN (insn); 20890075Sobrien } 20990075Sobrien 210117395Skan if (GET_CODE (insn) == CODE_LABEL) 211117395Skan return NULL_RTX; 212117395Skan 213117395Skan return insn; 21490075Sobrien} 21590075Sobrien 216132718Skan/* It is possible, especially when having dealt with multi-word 21790075Sobrien arithmetic, for the expanders to have emitted jumps. Search 21890075Sobrien through the sequence and return TRUE if a jump exists so that 21990075Sobrien we can abort the conversion. */ 22090075Sobrien 22190075Sobrienstatic int 222132718Skanseq_contains_jump (rtx insn) 22390075Sobrien{ 22490075Sobrien while (insn) 22590075Sobrien { 22690075Sobrien if (GET_CODE (insn) == JUMP_INSN) 22790075Sobrien return 1; 22890075Sobrien insn = NEXT_INSN (insn); 22990075Sobrien } 23090075Sobrien return 0; 23190075Sobrien} 232117395Skan 233117395Skanstatic basic_block 234132718Skanblock_fallthru (basic_block bb) 235117395Skan{ 236117395Skan edge e; 237117395Skan 238117395Skan for (e = bb->succ; 239117395Skan e != NULL_EDGE && (e->flags & EDGE_FALLTHRU) == 0; 240117395Skan e = e->succ_next) 241117395Skan ; 242117395Skan 243117395Skan return (e) ? e->dest : NULL_BLOCK; 244117395Skan} 24590075Sobrien 24690075Sobrien/* Go through a bunch of insns, converting them to conditional 24790075Sobrien execution format if possible. Return TRUE if all of the non-note 24890075Sobrien insns were processed. */ 24990075Sobrien 25090075Sobrienstatic int 251132718Skancond_exec_process_insns (ce_if_block_t *ce_info ATTRIBUTE_UNUSED, 252132718Skan /* if block information */rtx start, 253132718Skan /* first insn to look at */rtx end, 254132718Skan /* last insn to look at */rtx test, 255132718Skan /* conditional execution test */rtx prob_val, 256132718Skan /* probability of branch taken. */int mod_ok) 25790075Sobrien{ 25890075Sobrien int must_be_last = FALSE; 25990075Sobrien rtx insn; 260117395Skan rtx xtest; 26190075Sobrien rtx pattern; 26290075Sobrien 263117395Skan if (!start || !end) 264117395Skan return FALSE; 265117395Skan 26690075Sobrien for (insn = start; ; insn = NEXT_INSN (insn)) 26790075Sobrien { 26890075Sobrien if (GET_CODE (insn) == NOTE) 26990075Sobrien goto insn_done; 27090075Sobrien 27190075Sobrien if (GET_CODE (insn) != INSN && GET_CODE (insn) != CALL_INSN) 27290075Sobrien abort (); 27390075Sobrien 27490075Sobrien /* Remove USE insns that get in the way. */ 27590075Sobrien if (reload_completed && GET_CODE (PATTERN (insn)) == USE) 27690075Sobrien { 277132718Skan /* ??? Ug. Actually unlinking the thing is problematic, 27890075Sobrien given what we'd have to coordinate with our callers. */ 27990075Sobrien PUT_CODE (insn, NOTE); 28090075Sobrien NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED; 28190075Sobrien NOTE_SOURCE_FILE (insn) = 0; 28290075Sobrien goto insn_done; 28390075Sobrien } 28490075Sobrien 28590075Sobrien /* Last insn wasn't last? */ 28690075Sobrien if (must_be_last) 28790075Sobrien return FALSE; 28890075Sobrien 28990075Sobrien if (modified_in_p (test, insn)) 29090075Sobrien { 29190075Sobrien if (!mod_ok) 29290075Sobrien return FALSE; 29390075Sobrien must_be_last = TRUE; 29490075Sobrien } 29590075Sobrien 29690075Sobrien /* Now build the conditional form of the instruction. */ 29790075Sobrien pattern = PATTERN (insn); 298117395Skan xtest = copy_rtx (test); 29990075Sobrien 300117395Skan /* If this is already a COND_EXEC, rewrite the test to be an AND of the 301117395Skan two conditions. */ 302117395Skan if (GET_CODE (pattern) == COND_EXEC) 303117395Skan { 304117395Skan if (GET_MODE (xtest) != GET_MODE (COND_EXEC_TEST (pattern))) 305117395Skan return FALSE; 306117395Skan 307117395Skan xtest = gen_rtx_AND (GET_MODE (xtest), xtest, 308117395Skan COND_EXEC_TEST (pattern)); 309117395Skan pattern = COND_EXEC_CODE (pattern); 310117395Skan } 311117395Skan 312117395Skan pattern = gen_rtx_COND_EXEC (VOIDmode, xtest, pattern); 313117395Skan 31490075Sobrien /* If the machine needs to modify the insn being conditionally executed, 31590075Sobrien say for example to force a constant integer operand into a temp 31690075Sobrien register, do so here. */ 31790075Sobrien#ifdef IFCVT_MODIFY_INSN 318117395Skan IFCVT_MODIFY_INSN (ce_info, pattern, insn); 31990075Sobrien if (! pattern) 32090075Sobrien return FALSE; 32190075Sobrien#endif 32290075Sobrien 323117395Skan validate_change (insn, &PATTERN (insn), pattern, 1); 32490075Sobrien 32590075Sobrien if (GET_CODE (insn) == CALL_INSN && prob_val) 32690075Sobrien validate_change (insn, ®_NOTES (insn), 32790075Sobrien alloc_EXPR_LIST (REG_BR_PROB, prob_val, 32890075Sobrien REG_NOTES (insn)), 1); 32990075Sobrien 33090075Sobrien insn_done: 33190075Sobrien if (insn == end) 33290075Sobrien break; 33390075Sobrien } 33490075Sobrien 33590075Sobrien return TRUE; 33690075Sobrien} 33790075Sobrien 33890075Sobrien/* Return the condition for a jump. Do not do any special processing. */ 33990075Sobrien 34090075Sobrienstatic rtx 341132718Skancond_exec_get_condition (rtx jump) 34290075Sobrien{ 34390075Sobrien rtx test_if, cond; 34490075Sobrien 34590075Sobrien if (any_condjump_p (jump)) 34690075Sobrien test_if = SET_SRC (pc_set (jump)); 34790075Sobrien else 34890075Sobrien return NULL_RTX; 34990075Sobrien cond = XEXP (test_if, 0); 35090075Sobrien 35190075Sobrien /* If this branches to JUMP_LABEL when the condition is false, 35290075Sobrien reverse the condition. */ 35390075Sobrien if (GET_CODE (XEXP (test_if, 2)) == LABEL_REF 35490075Sobrien && XEXP (XEXP (test_if, 2), 0) == JUMP_LABEL (jump)) 35590075Sobrien { 35690075Sobrien enum rtx_code rev = reversed_comparison_code (cond, jump); 35790075Sobrien if (rev == UNKNOWN) 35890075Sobrien return NULL_RTX; 35990075Sobrien 36090075Sobrien cond = gen_rtx_fmt_ee (rev, GET_MODE (cond), XEXP (cond, 0), 36190075Sobrien XEXP (cond, 1)); 36290075Sobrien } 36390075Sobrien 36490075Sobrien return cond; 36590075Sobrien} 36690075Sobrien 36790075Sobrien/* Given a simple IF-THEN or IF-THEN-ELSE block, attempt to convert it 36890075Sobrien to conditional execution. Return TRUE if we were successful at 369117395Skan converting the block. */ 37090075Sobrien 37190075Sobrienstatic int 372132718Skancond_exec_process_if_block (ce_if_block_t * ce_info, 373132718Skan /* if block information */int do_multiple_p) 37490075Sobrien{ 375117395Skan basic_block test_bb = ce_info->test_bb; /* last test block */ 376117395Skan basic_block then_bb = ce_info->then_bb; /* THEN */ 377117395Skan basic_block else_bb = ce_info->else_bb; /* ELSE or NULL */ 37890075Sobrien rtx test_expr; /* expression in IF_THEN_ELSE that is tested */ 37990075Sobrien rtx then_start; /* first insn in THEN block */ 38090075Sobrien rtx then_end; /* last insn + 1 in THEN block */ 38190075Sobrien rtx else_start = NULL_RTX; /* first insn in ELSE block or NULL */ 38290075Sobrien rtx else_end = NULL_RTX; /* last insn + 1 in ELSE block */ 38390075Sobrien int max; /* max # of insns to convert. */ 38490075Sobrien int then_mod_ok; /* whether conditional mods are ok in THEN */ 38590075Sobrien rtx true_expr; /* test for else block insns */ 38690075Sobrien rtx false_expr; /* test for then block insns */ 38790075Sobrien rtx true_prob_val; /* probability of else block */ 38890075Sobrien rtx false_prob_val; /* probability of then block */ 38990075Sobrien int n_insns; 39090075Sobrien enum rtx_code false_code; 39190075Sobrien 392117395Skan /* If test is comprised of && or || elements, and we've failed at handling 393117395Skan all of them together, just use the last test if it is the special case of 394117395Skan && elements without an ELSE block. */ 395117395Skan if (!do_multiple_p && ce_info->num_multiple_test_blocks) 396117395Skan { 397117395Skan if (else_bb || ! ce_info->and_and_p) 398117395Skan return FALSE; 399117395Skan 400117395Skan ce_info->test_bb = test_bb = ce_info->last_test_bb; 401117395Skan ce_info->num_multiple_test_blocks = 0; 402117395Skan ce_info->num_and_and_blocks = 0; 403117395Skan ce_info->num_or_or_blocks = 0; 404117395Skan } 405117395Skan 40690075Sobrien /* Find the conditional jump to the ELSE or JOIN part, and isolate 40790075Sobrien the test. */ 408132718Skan test_expr = cond_exec_get_condition (BB_END (test_bb)); 40990075Sobrien if (! test_expr) 41090075Sobrien return FALSE; 41190075Sobrien 41290075Sobrien /* If the conditional jump is more than just a conditional jump, 41390075Sobrien then we can not do conditional execution conversion on this block. */ 414132718Skan if (! onlyjump_p (BB_END (test_bb))) 41590075Sobrien return FALSE; 41690075Sobrien 417117395Skan /* Collect the bounds of where we're to search, skipping any labels, jumps 418117395Skan and notes at the beginning and end of the block. Then count the total 419117395Skan number of insns and see if it is small enough to convert. */ 420117395Skan then_start = first_active_insn (then_bb); 421117395Skan then_end = last_active_insn (then_bb, TRUE); 422117395Skan n_insns = ce_info->num_then_insns = count_bb_insns (then_bb); 423117395Skan max = MAX_CONDITIONAL_EXECUTE; 42490075Sobrien 42590075Sobrien if (else_bb) 42690075Sobrien { 427117395Skan max *= 2; 428117395Skan else_start = first_active_insn (else_bb); 429117395Skan else_end = last_active_insn (else_bb, TRUE); 430117395Skan n_insns += ce_info->num_else_insns = count_bb_insns (else_bb); 43190075Sobrien } 43290075Sobrien 43390075Sobrien if (n_insns > max) 43490075Sobrien return FALSE; 43590075Sobrien 43690075Sobrien /* Map test_expr/test_jump into the appropriate MD tests to use on 43790075Sobrien the conditionally executed code. */ 438132718Skan 43990075Sobrien true_expr = test_expr; 44090075Sobrien 441132718Skan false_code = reversed_comparison_code (true_expr, BB_END (test_bb)); 44290075Sobrien if (false_code != UNKNOWN) 44390075Sobrien false_expr = gen_rtx_fmt_ee (false_code, GET_MODE (true_expr), 44490075Sobrien XEXP (true_expr, 0), XEXP (true_expr, 1)); 44590075Sobrien else 44690075Sobrien false_expr = NULL_RTX; 44790075Sobrien 44890075Sobrien#ifdef IFCVT_MODIFY_TESTS 44990075Sobrien /* If the machine description needs to modify the tests, such as setting a 45090075Sobrien conditional execution register from a comparison, it can do so here. */ 451117395Skan IFCVT_MODIFY_TESTS (ce_info, true_expr, false_expr); 45290075Sobrien 453132718Skan /* See if the conversion failed. */ 45490075Sobrien if (!true_expr || !false_expr) 45590075Sobrien goto fail; 45690075Sobrien#endif 45790075Sobrien 458132718Skan true_prob_val = find_reg_note (BB_END (test_bb), REG_BR_PROB, NULL_RTX); 45990075Sobrien if (true_prob_val) 46090075Sobrien { 46190075Sobrien true_prob_val = XEXP (true_prob_val, 0); 46290075Sobrien false_prob_val = GEN_INT (REG_BR_PROB_BASE - INTVAL (true_prob_val)); 46390075Sobrien } 46490075Sobrien else 46590075Sobrien false_prob_val = NULL_RTX; 46690075Sobrien 467117395Skan /* If we have && or || tests, do them here. These tests are in the adjacent 468117395Skan blocks after the first block containing the test. */ 469117395Skan if (ce_info->num_multiple_test_blocks > 0) 470117395Skan { 471117395Skan basic_block bb = test_bb; 472117395Skan basic_block last_test_bb = ce_info->last_test_bb; 473117395Skan 474117395Skan if (! false_expr) 475117395Skan goto fail; 476117395Skan 477117395Skan do 478117395Skan { 479117395Skan rtx start, end; 480117395Skan rtx t, f; 481117395Skan 482117395Skan bb = block_fallthru (bb); 483117395Skan start = first_active_insn (bb); 484117395Skan end = last_active_insn (bb, TRUE); 485117395Skan if (start 486117395Skan && ! cond_exec_process_insns (ce_info, start, end, false_expr, 487117395Skan false_prob_val, FALSE)) 488117395Skan goto fail; 489117395Skan 490117395Skan /* If the conditional jump is more than just a conditional jump, then 491117395Skan we can not do conditional execution conversion on this block. */ 492132718Skan if (! onlyjump_p (BB_END (bb))) 493117395Skan goto fail; 494117395Skan 495117395Skan /* Find the conditional jump and isolate the test. */ 496132718Skan t = cond_exec_get_condition (BB_END (bb)); 497117395Skan if (! t) 498117395Skan goto fail; 499117395Skan 500117395Skan f = gen_rtx_fmt_ee (reverse_condition (GET_CODE (t)), 501117395Skan GET_MODE (t), 502117395Skan XEXP (t, 0), 503117395Skan XEXP (t, 1)); 504117395Skan 505117395Skan if (ce_info->and_and_p) 506117395Skan { 507117395Skan t = gen_rtx_AND (GET_MODE (t), true_expr, t); 508117395Skan f = gen_rtx_IOR (GET_MODE (t), false_expr, f); 509117395Skan } 510117395Skan else 511117395Skan { 512117395Skan t = gen_rtx_IOR (GET_MODE (t), true_expr, t); 513117395Skan f = gen_rtx_AND (GET_MODE (t), false_expr, f); 514117395Skan } 515117395Skan 516117395Skan /* If the machine description needs to modify the tests, such as 517117395Skan setting a conditional execution register from a comparison, it can 518117395Skan do so here. */ 519117395Skan#ifdef IFCVT_MODIFY_MULTIPLE_TESTS 520117395Skan IFCVT_MODIFY_MULTIPLE_TESTS (ce_info, bb, t, f); 521117395Skan 522132718Skan /* See if the conversion failed. */ 523117395Skan if (!t || !f) 524117395Skan goto fail; 525117395Skan#endif 526117395Skan 527117395Skan true_expr = t; 528117395Skan false_expr = f; 529117395Skan } 530117395Skan while (bb != last_test_bb); 531117395Skan } 532117395Skan 53390075Sobrien /* For IF-THEN-ELSE blocks, we don't allow modifications of the test 53490075Sobrien on then THEN block. */ 53590075Sobrien then_mod_ok = (else_bb == NULL_BLOCK); 53690075Sobrien 53790075Sobrien /* Go through the THEN and ELSE blocks converting the insns if possible 53890075Sobrien to conditional execution. */ 53990075Sobrien 54090075Sobrien if (then_end 54190075Sobrien && (! false_expr 542117395Skan || ! cond_exec_process_insns (ce_info, then_start, then_end, 543117395Skan false_expr, false_prob_val, 544117395Skan then_mod_ok))) 54590075Sobrien goto fail; 54690075Sobrien 547117395Skan if (else_bb && else_end 548117395Skan && ! cond_exec_process_insns (ce_info, else_start, else_end, 54990075Sobrien true_expr, true_prob_val, TRUE)) 55090075Sobrien goto fail; 55190075Sobrien 552117395Skan /* If we cannot apply the changes, fail. Do not go through the normal fail 553117395Skan processing, since apply_change_group will call cancel_changes. */ 55490075Sobrien if (! apply_change_group ()) 555117395Skan { 556117395Skan#ifdef IFCVT_MODIFY_CANCEL 557117395Skan /* Cancel any machine dependent changes. */ 558117395Skan IFCVT_MODIFY_CANCEL (ce_info); 559117395Skan#endif 560117395Skan return FALSE; 561117395Skan } 56290075Sobrien 56390075Sobrien#ifdef IFCVT_MODIFY_FINAL 564132718Skan /* Do any machine dependent final modifications. */ 565117395Skan IFCVT_MODIFY_FINAL (ce_info); 56690075Sobrien#endif 56790075Sobrien 56890075Sobrien /* Conversion succeeded. */ 56990075Sobrien if (rtl_dump_file) 57090075Sobrien fprintf (rtl_dump_file, "%d insn%s converted to conditional execution.\n", 57190075Sobrien n_insns, (n_insns == 1) ? " was" : "s were"); 57290075Sobrien 57390075Sobrien /* Merge the blocks! */ 574117395Skan merge_if_block (ce_info); 575117395Skan cond_exec_changed_p = TRUE; 57690075Sobrien return TRUE; 57790075Sobrien 57890075Sobrien fail: 57990075Sobrien#ifdef IFCVT_MODIFY_CANCEL 58090075Sobrien /* Cancel any machine dependent changes. */ 581117395Skan IFCVT_MODIFY_CANCEL (ce_info); 58290075Sobrien#endif 58390075Sobrien 58490075Sobrien cancel_changes (0); 58590075Sobrien return FALSE; 58690075Sobrien} 58790075Sobrien 588132718Skan/* Used by noce_process_if_block to communicate with its subroutines. 58990075Sobrien 59090075Sobrien The subroutines know that A and B may be evaluated freely. They 591132718Skan know that X is a register. They should insert new instructions 59290075Sobrien before cond_earliest. */ 59390075Sobrien 59490075Sobrienstruct noce_if_info 59590075Sobrien{ 59690075Sobrien basic_block test_bb; 59790075Sobrien rtx insn_a, insn_b; 59890075Sobrien rtx x, a, b; 59990075Sobrien rtx jump, cond, cond_earliest; 60090075Sobrien}; 60190075Sobrien 602132718Skanstatic rtx noce_emit_store_flag (struct noce_if_info *, rtx, int, int); 603132718Skanstatic int noce_try_move (struct noce_if_info *); 604132718Skanstatic int noce_try_store_flag (struct noce_if_info *); 605132718Skanstatic int noce_try_addcc (struct noce_if_info *); 606132718Skanstatic int noce_try_store_flag_constants (struct noce_if_info *); 607132718Skanstatic int noce_try_store_flag_mask (struct noce_if_info *); 608132718Skanstatic rtx noce_emit_cmove (struct noce_if_info *, rtx, enum rtx_code, rtx, 609132718Skan rtx, rtx, rtx); 610132718Skanstatic int noce_try_cmove (struct noce_if_info *); 611132718Skanstatic int noce_try_cmove_arith (struct noce_if_info *); 612132718Skanstatic rtx noce_get_alt_condition (struct noce_if_info *, rtx, rtx *); 613132718Skanstatic int noce_try_minmax (struct noce_if_info *); 614132718Skanstatic int noce_try_abs (struct noce_if_info *); 61590075Sobrien 61690075Sobrien/* Helper function for noce_try_store_flag*. */ 61790075Sobrien 61890075Sobrienstatic rtx 619132718Skannoce_emit_store_flag (struct noce_if_info *if_info, rtx x, int reversep, 620132718Skan int normalize) 62190075Sobrien{ 62290075Sobrien rtx cond = if_info->cond; 62390075Sobrien int cond_complex; 62490075Sobrien enum rtx_code code; 62590075Sobrien 62690075Sobrien cond_complex = (! general_operand (XEXP (cond, 0), VOIDmode) 62790075Sobrien || ! general_operand (XEXP (cond, 1), VOIDmode)); 62890075Sobrien 62990075Sobrien /* If earliest == jump, or when the condition is complex, try to 63090075Sobrien build the store_flag insn directly. */ 63190075Sobrien 63290075Sobrien if (cond_complex) 63390075Sobrien cond = XEXP (SET_SRC (pc_set (if_info->jump)), 0); 63490075Sobrien 63590075Sobrien if (reversep) 63690075Sobrien code = reversed_comparison_code (cond, if_info->jump); 63790075Sobrien else 63890075Sobrien code = GET_CODE (cond); 63990075Sobrien 64090075Sobrien if ((if_info->cond_earliest == if_info->jump || cond_complex) 64190075Sobrien && (normalize == 0 || STORE_FLAG_VALUE == normalize)) 64290075Sobrien { 64390075Sobrien rtx tmp; 64490075Sobrien 64590075Sobrien tmp = gen_rtx_fmt_ee (code, GET_MODE (x), XEXP (cond, 0), 64690075Sobrien XEXP (cond, 1)); 64790075Sobrien tmp = gen_rtx_SET (VOIDmode, x, tmp); 64890075Sobrien 64990075Sobrien start_sequence (); 65090075Sobrien tmp = emit_insn (tmp); 65190075Sobrien 65290075Sobrien if (recog_memoized (tmp) >= 0) 65390075Sobrien { 65490075Sobrien tmp = get_insns (); 65590075Sobrien end_sequence (); 656117395Skan emit_insn (tmp); 65790075Sobrien 65890075Sobrien if_info->cond_earliest = if_info->jump; 65990075Sobrien 66090075Sobrien return x; 66190075Sobrien } 66290075Sobrien 66390075Sobrien end_sequence (); 66490075Sobrien } 66590075Sobrien 666117395Skan /* Don't even try if the comparison operands or the mode of X are weird. */ 667117395Skan if (cond_complex || !SCALAR_INT_MODE_P (GET_MODE (x))) 66890075Sobrien return NULL_RTX; 66990075Sobrien 67090075Sobrien return emit_store_flag (x, code, XEXP (cond, 0), 67190075Sobrien XEXP (cond, 1), VOIDmode, 67290075Sobrien (code == LTU || code == LEU 67390075Sobrien || code == GEU || code == GTU), normalize); 67490075Sobrien} 67590075Sobrien 676132718Skan/* Emit instruction to move an rtx, possibly into STRICT_LOW_PART. 677132718Skan X is the destination/target and Y is the value to copy. */ 678132718Skan 67990075Sobrienstatic void 680132718Skannoce_emit_move_insn (rtx x, rtx y) 68190075Sobrien{ 68290075Sobrien enum machine_mode outmode, inmode; 68390075Sobrien rtx outer, inner; 68490075Sobrien int bitpos; 68590075Sobrien 68690075Sobrien if (GET_CODE (x) != STRICT_LOW_PART) 68790075Sobrien { 68890075Sobrien emit_move_insn (x, y); 68990075Sobrien return; 69090075Sobrien } 69190075Sobrien 69290075Sobrien outer = XEXP (x, 0); 69390075Sobrien inner = XEXP (outer, 0); 69490075Sobrien outmode = GET_MODE (outer); 69590075Sobrien inmode = GET_MODE (inner); 69690075Sobrien bitpos = SUBREG_BYTE (outer) * BITS_PER_UNIT; 69790075Sobrien store_bit_field (inner, GET_MODE_BITSIZE (outmode), bitpos, outmode, y, 69890075Sobrien GET_MODE_BITSIZE (inmode)); 69990075Sobrien} 70090075Sobrien 701132718Skan/* Unshare sequence SEQ produced by if conversion. We care to mark 702132718Skan all arguments that may be shared with outer instruction stream. */ 703132718Skanstatic void 704132718Skanunshare_ifcvt_sequence (struct noce_if_info *if_info, rtx seq) 705132718Skan{ 706132718Skan set_used_flags (if_info->x); 707132718Skan set_used_flags (if_info->cond); 708132718Skan unshare_all_rtl_in_chain (seq); 709132718Skan} 710132718Skan 711132718Skan/* Convert "if (a != b) x = a; else x = b" into "x = a" and 712132718Skan "if (a == b) x = a; else x = b" into "x = b". */ 713132718Skan 714132718Skanstatic int 715132718Skannoce_try_move (struct noce_if_info *if_info) 716132718Skan{ 717132718Skan rtx cond = if_info->cond; 718132718Skan enum rtx_code code = GET_CODE (cond); 719132718Skan rtx y, seq; 720132718Skan 721132718Skan if (code != NE && code != EQ) 722132718Skan return FALSE; 723132718Skan 724132718Skan /* This optimization isn't valid if either A or B could be a NaN 725132718Skan or a signed zero. */ 726132718Skan if (HONOR_NANS (GET_MODE (if_info->x)) 727132718Skan || HONOR_SIGNED_ZEROS (GET_MODE (if_info->x))) 728132718Skan return FALSE; 729132718Skan 730132718Skan /* Check whether the operands of the comparison are A and in 731132718Skan either order. */ 732132718Skan if ((rtx_equal_p (if_info->a, XEXP (cond, 0)) 733132718Skan && rtx_equal_p (if_info->b, XEXP (cond, 1))) 734132718Skan || (rtx_equal_p (if_info->a, XEXP (cond, 1)) 735132718Skan && rtx_equal_p (if_info->b, XEXP (cond, 0)))) 736132718Skan { 737132718Skan y = (code == EQ) ? if_info->a : if_info->b; 738132718Skan 739132718Skan /* Avoid generating the move if the source is the destination. */ 740132718Skan if (! rtx_equal_p (if_info->x, y)) 741132718Skan { 742132718Skan start_sequence (); 743132718Skan noce_emit_move_insn (if_info->x, y); 744132718Skan seq = get_insns (); 745132718Skan unshare_ifcvt_sequence (if_info, seq); 746132718Skan end_sequence (); 747132718Skan 748132718Skan /* Make sure that all of the instructions emitted are 749132718Skan recognizable. As an excersise for the reader, build 750132718Skan a general mechanism that allows proper placement of 751132718Skan required clobbers. */ 752132718Skan for (y = seq; y ; y = NEXT_INSN (y)) 753132718Skan if (recog_memoized (y) == -1) 754132718Skan return FALSE; 755132718Skan 756132718Skan emit_insn_before_setloc (seq, if_info->jump, 757132718Skan INSN_LOCATOR (if_info->insn_a)); 758132718Skan } 759132718Skan return TRUE; 760132718Skan } 761132718Skan return FALSE; 762132718Skan} 763132718Skan 76490075Sobrien/* Convert "if (test) x = 1; else x = 0". 76590075Sobrien 76690075Sobrien Only try 0 and STORE_FLAG_VALUE here. Other combinations will be 76790075Sobrien tried in noce_try_store_flag_constants after noce_try_cmove has had 76890075Sobrien a go at the conversion. */ 76990075Sobrien 77090075Sobrienstatic int 771132718Skannoce_try_store_flag (struct noce_if_info *if_info) 77290075Sobrien{ 77390075Sobrien int reversep; 77490075Sobrien rtx target, seq; 77590075Sobrien 77690075Sobrien if (GET_CODE (if_info->b) == CONST_INT 77790075Sobrien && INTVAL (if_info->b) == STORE_FLAG_VALUE 77890075Sobrien && if_info->a == const0_rtx) 77990075Sobrien reversep = 0; 78090075Sobrien else if (if_info->b == const0_rtx 78190075Sobrien && GET_CODE (if_info->a) == CONST_INT 78290075Sobrien && INTVAL (if_info->a) == STORE_FLAG_VALUE 78390075Sobrien && (reversed_comparison_code (if_info->cond, if_info->jump) 78490075Sobrien != UNKNOWN)) 78590075Sobrien reversep = 1; 78690075Sobrien else 78790075Sobrien return FALSE; 78890075Sobrien 78990075Sobrien start_sequence (); 79090075Sobrien 79190075Sobrien target = noce_emit_store_flag (if_info, if_info->x, reversep, 0); 79290075Sobrien if (target) 79390075Sobrien { 79490075Sobrien if (target != if_info->x) 79590075Sobrien noce_emit_move_insn (if_info->x, target); 79690075Sobrien 79790075Sobrien seq = get_insns (); 798132718Skan unshare_ifcvt_sequence (if_info, seq); 79990075Sobrien end_sequence (); 800132718Skan emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATOR (if_info->insn_a)); 80190075Sobrien 80290075Sobrien return TRUE; 80390075Sobrien } 80490075Sobrien else 80590075Sobrien { 80690075Sobrien end_sequence (); 80790075Sobrien return FALSE; 80890075Sobrien } 80990075Sobrien} 81090075Sobrien 81190075Sobrien/* Convert "if (test) x = a; else x = b", for A and B constant. */ 81290075Sobrien 81390075Sobrienstatic int 814132718Skannoce_try_store_flag_constants (struct noce_if_info *if_info) 81590075Sobrien{ 81690075Sobrien rtx target, seq; 81790075Sobrien int reversep; 81890075Sobrien HOST_WIDE_INT itrue, ifalse, diff, tmp; 81990075Sobrien int normalize, can_reverse; 82090075Sobrien enum machine_mode mode; 82190075Sobrien 82290075Sobrien if (! no_new_pseudos 82390075Sobrien && GET_CODE (if_info->a) == CONST_INT 82490075Sobrien && GET_CODE (if_info->b) == CONST_INT) 82590075Sobrien { 82690075Sobrien mode = GET_MODE (if_info->x); 82790075Sobrien ifalse = INTVAL (if_info->a); 82890075Sobrien itrue = INTVAL (if_info->b); 82990075Sobrien 83090075Sobrien /* Make sure we can represent the difference between the two values. */ 83190075Sobrien if ((itrue - ifalse > 0) 83290075Sobrien != ((ifalse < 0) != (itrue < 0) ? ifalse < 0 : ifalse < itrue)) 83390075Sobrien return FALSE; 83490075Sobrien 83590075Sobrien diff = trunc_int_for_mode (itrue - ifalse, mode); 83690075Sobrien 83790075Sobrien can_reverse = (reversed_comparison_code (if_info->cond, if_info->jump) 83890075Sobrien != UNKNOWN); 83990075Sobrien 84090075Sobrien reversep = 0; 84190075Sobrien if (diff == STORE_FLAG_VALUE || diff == -STORE_FLAG_VALUE) 84290075Sobrien normalize = 0; 84390075Sobrien else if (ifalse == 0 && exact_log2 (itrue) >= 0 84490075Sobrien && (STORE_FLAG_VALUE == 1 84590075Sobrien || BRANCH_COST >= 2)) 84690075Sobrien normalize = 1; 84790075Sobrien else if (itrue == 0 && exact_log2 (ifalse) >= 0 && can_reverse 84890075Sobrien && (STORE_FLAG_VALUE == 1 || BRANCH_COST >= 2)) 84990075Sobrien normalize = 1, reversep = 1; 85090075Sobrien else if (itrue == -1 85190075Sobrien && (STORE_FLAG_VALUE == -1 85290075Sobrien || BRANCH_COST >= 2)) 85390075Sobrien normalize = -1; 85490075Sobrien else if (ifalse == -1 && can_reverse 85590075Sobrien && (STORE_FLAG_VALUE == -1 || BRANCH_COST >= 2)) 85690075Sobrien normalize = -1, reversep = 1; 85790075Sobrien else if ((BRANCH_COST >= 2 && STORE_FLAG_VALUE == -1) 85890075Sobrien || BRANCH_COST >= 3) 85990075Sobrien normalize = -1; 86090075Sobrien else 86190075Sobrien return FALSE; 86290075Sobrien 86390075Sobrien if (reversep) 864132718Skan { 86590075Sobrien tmp = itrue; itrue = ifalse; ifalse = tmp; 86690075Sobrien diff = trunc_int_for_mode (-diff, mode); 86790075Sobrien } 86890075Sobrien 86990075Sobrien start_sequence (); 87090075Sobrien target = noce_emit_store_flag (if_info, if_info->x, reversep, normalize); 87190075Sobrien if (! target) 87290075Sobrien { 87390075Sobrien end_sequence (); 87490075Sobrien return FALSE; 87590075Sobrien } 87690075Sobrien 87790075Sobrien /* if (test) x = 3; else x = 4; 87890075Sobrien => x = 3 + (test == 0); */ 87990075Sobrien if (diff == STORE_FLAG_VALUE || diff == -STORE_FLAG_VALUE) 88090075Sobrien { 88190075Sobrien target = expand_simple_binop (mode, 88290075Sobrien (diff == STORE_FLAG_VALUE 88390075Sobrien ? PLUS : MINUS), 88490075Sobrien GEN_INT (ifalse), target, if_info->x, 0, 88590075Sobrien OPTAB_WIDEN); 88690075Sobrien } 88790075Sobrien 88890075Sobrien /* if (test) x = 8; else x = 0; 88990075Sobrien => x = (test != 0) << 3; */ 89090075Sobrien else if (ifalse == 0 && (tmp = exact_log2 (itrue)) >= 0) 89190075Sobrien { 89290075Sobrien target = expand_simple_binop (mode, ASHIFT, 89390075Sobrien target, GEN_INT (tmp), if_info->x, 0, 89490075Sobrien OPTAB_WIDEN); 89590075Sobrien } 89690075Sobrien 89790075Sobrien /* if (test) x = -1; else x = b; 89890075Sobrien => x = -(test != 0) | b; */ 89990075Sobrien else if (itrue == -1) 90090075Sobrien { 90190075Sobrien target = expand_simple_binop (mode, IOR, 90290075Sobrien target, GEN_INT (ifalse), if_info->x, 0, 90390075Sobrien OPTAB_WIDEN); 90490075Sobrien } 90590075Sobrien 90690075Sobrien /* if (test) x = a; else x = b; 90790075Sobrien => x = (-(test != 0) & (b - a)) + a; */ 90890075Sobrien else 90990075Sobrien { 91090075Sobrien target = expand_simple_binop (mode, AND, 91190075Sobrien target, GEN_INT (diff), if_info->x, 0, 91290075Sobrien OPTAB_WIDEN); 91390075Sobrien if (target) 91490075Sobrien target = expand_simple_binop (mode, PLUS, 91590075Sobrien target, GEN_INT (ifalse), 91690075Sobrien if_info->x, 0, OPTAB_WIDEN); 91790075Sobrien } 91890075Sobrien 91990075Sobrien if (! target) 92090075Sobrien { 92190075Sobrien end_sequence (); 92290075Sobrien return FALSE; 92390075Sobrien } 92490075Sobrien 92590075Sobrien if (target != if_info->x) 92690075Sobrien noce_emit_move_insn (if_info->x, target); 92790075Sobrien 92890075Sobrien seq = get_insns (); 929132718Skan unshare_ifcvt_sequence (if_info, seq); 93090075Sobrien end_sequence (); 93190075Sobrien 93290075Sobrien if (seq_contains_jump (seq)) 93390075Sobrien return FALSE; 93490075Sobrien 935132718Skan emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATOR (if_info->insn_a)); 93690075Sobrien 93790075Sobrien return TRUE; 93890075Sobrien } 93990075Sobrien 94090075Sobrien return FALSE; 94190075Sobrien} 94290075Sobrien 943132718Skan/* Convert "if (test) foo++" into "foo += (test != 0)", and 94490075Sobrien similarly for "foo--". */ 94590075Sobrien 94690075Sobrienstatic int 947132718Skannoce_try_addcc (struct noce_if_info *if_info) 94890075Sobrien{ 94990075Sobrien rtx target, seq; 95090075Sobrien int subtract, normalize; 95190075Sobrien 95290075Sobrien if (! no_new_pseudos 95390075Sobrien && GET_CODE (if_info->a) == PLUS 954132718Skan && rtx_equal_p (XEXP (if_info->a, 0), if_info->b) 95590075Sobrien && (reversed_comparison_code (if_info->cond, if_info->jump) 95690075Sobrien != UNKNOWN)) 95790075Sobrien { 958132718Skan rtx cond = if_info->cond; 959132718Skan enum rtx_code code = reversed_comparison_code (cond, if_info->jump); 96090075Sobrien 961132718Skan /* First try to use addcc pattern. */ 962132718Skan if (general_operand (XEXP (cond, 0), VOIDmode) 963132718Skan && general_operand (XEXP (cond, 1), VOIDmode)) 96490075Sobrien { 965132718Skan start_sequence (); 966132718Skan target = emit_conditional_add (if_info->x, code, 967132718Skan XEXP (cond, 0), 968132718Skan XEXP (cond, 1), 969132718Skan VOIDmode, 970132718Skan if_info->b, 971132718Skan XEXP (if_info->a, 1), 972132718Skan GET_MODE (if_info->x), 973132718Skan (code == LTU || code == GEU 974132718Skan || code == LEU || code == GTU)); 975132718Skan if (target) 976132718Skan { 977132718Skan if (target != if_info->x) 978132718Skan noce_emit_move_insn (if_info->x, target); 97990075Sobrien 980132718Skan seq = get_insns (); 981132718Skan unshare_ifcvt_sequence (if_info, seq); 982132718Skan end_sequence (); 983132718Skan emit_insn_before_setloc (seq, if_info->jump, 984132718Skan INSN_LOCATOR (if_info->insn_a)); 985132718Skan return TRUE; 986132718Skan } 98790075Sobrien end_sequence (); 988132718Skan } 98990075Sobrien 990132718Skan /* If that fails, construct conditional increment or decrement using 991132718Skan setcc. */ 992132718Skan if (BRANCH_COST >= 2 993132718Skan && (XEXP (if_info->a, 1) == const1_rtx 994132718Skan || XEXP (if_info->a, 1) == constm1_rtx)) 995132718Skan { 996132718Skan start_sequence (); 997132718Skan if (STORE_FLAG_VALUE == INTVAL (XEXP (if_info->a, 1))) 998132718Skan subtract = 0, normalize = 0; 999132718Skan else if (-STORE_FLAG_VALUE == INTVAL (XEXP (if_info->a, 1))) 1000132718Skan subtract = 1, normalize = 0; 1001132718Skan else 1002132718Skan subtract = 0, normalize = INTVAL (XEXP (if_info->a, 1)); 100390075Sobrien 100490075Sobrien 1005132718Skan target = noce_emit_store_flag (if_info, 1006132718Skan gen_reg_rtx (GET_MODE (if_info->x)), 1007132718Skan 1, normalize); 1008132718Skan 1009132718Skan if (target) 1010132718Skan target = expand_simple_binop (GET_MODE (if_info->x), 1011132718Skan subtract ? MINUS : PLUS, 1012132718Skan if_info->b, target, if_info->x, 1013132718Skan 0, OPTAB_WIDEN); 1014132718Skan if (target) 1015132718Skan { 1016132718Skan if (target != if_info->x) 1017132718Skan noce_emit_move_insn (if_info->x, target); 1018132718Skan 1019132718Skan seq = get_insns (); 1020132718Skan unshare_ifcvt_sequence (if_info, seq); 1021132718Skan end_sequence (); 1022132718Skan 1023132718Skan if (seq_contains_jump (seq)) 1024132718Skan return FALSE; 1025132718Skan 1026132718Skan emit_insn_before_setloc (seq, if_info->jump, 1027132718Skan INSN_LOCATOR (if_info->insn_a)); 1028132718Skan 1029132718Skan return TRUE; 1030132718Skan } 1031132718Skan end_sequence (); 103290075Sobrien } 103390075Sobrien } 103490075Sobrien 103590075Sobrien return FALSE; 103690075Sobrien} 103790075Sobrien 103890075Sobrien/* Convert "if (test) x = 0;" to "x &= -(test == 0);" */ 103990075Sobrien 104090075Sobrienstatic int 1041132718Skannoce_try_store_flag_mask (struct noce_if_info *if_info) 104290075Sobrien{ 104390075Sobrien rtx target, seq; 104490075Sobrien int reversep; 104590075Sobrien 104690075Sobrien reversep = 0; 104790075Sobrien if (! no_new_pseudos 104890075Sobrien && (BRANCH_COST >= 2 104990075Sobrien || STORE_FLAG_VALUE == -1) 105090075Sobrien && ((if_info->a == const0_rtx 105190075Sobrien && rtx_equal_p (if_info->b, if_info->x)) 105290075Sobrien || ((reversep = (reversed_comparison_code (if_info->cond, 105390075Sobrien if_info->jump) 105490075Sobrien != UNKNOWN)) 105590075Sobrien && if_info->b == const0_rtx 105690075Sobrien && rtx_equal_p (if_info->a, if_info->x)))) 105790075Sobrien { 105890075Sobrien start_sequence (); 105990075Sobrien target = noce_emit_store_flag (if_info, 106090075Sobrien gen_reg_rtx (GET_MODE (if_info->x)), 106190075Sobrien reversep, -1); 106290075Sobrien if (target) 106390075Sobrien target = expand_simple_binop (GET_MODE (if_info->x), AND, 1064132718Skan if_info->x, 1065132718Skan target, if_info->x, 0, 106690075Sobrien OPTAB_WIDEN); 106790075Sobrien 106890075Sobrien if (target) 106990075Sobrien { 107090075Sobrien if (target != if_info->x) 107190075Sobrien noce_emit_move_insn (if_info->x, target); 107290075Sobrien 107390075Sobrien seq = get_insns (); 1074132718Skan unshare_ifcvt_sequence (if_info, seq); 107590075Sobrien end_sequence (); 107690075Sobrien 107790075Sobrien if (seq_contains_jump (seq)) 107890075Sobrien return FALSE; 107990075Sobrien 1080132718Skan emit_insn_before_setloc (seq, if_info->jump, 1081132718Skan INSN_LOCATOR (if_info->insn_a)); 108290075Sobrien 108390075Sobrien return TRUE; 108490075Sobrien } 108590075Sobrien 108690075Sobrien end_sequence (); 108790075Sobrien } 108890075Sobrien 108990075Sobrien return FALSE; 109090075Sobrien} 109190075Sobrien 109290075Sobrien/* Helper function for noce_try_cmove and noce_try_cmove_arith. */ 109390075Sobrien 109490075Sobrienstatic rtx 1095132718Skannoce_emit_cmove (struct noce_if_info *if_info, rtx x, enum rtx_code code, 1096132718Skan rtx cmp_a, rtx cmp_b, rtx vfalse, rtx vtrue) 109790075Sobrien{ 109890075Sobrien /* If earliest == jump, try to build the cmove insn directly. 109990075Sobrien This is helpful when combine has created some complex condition 110090075Sobrien (like for alpha's cmovlbs) that we can't hope to regenerate 110190075Sobrien through the normal interface. */ 110290075Sobrien 110390075Sobrien if (if_info->cond_earliest == if_info->jump) 110490075Sobrien { 110590075Sobrien rtx tmp; 110690075Sobrien 110790075Sobrien tmp = gen_rtx_fmt_ee (code, GET_MODE (if_info->cond), cmp_a, cmp_b); 110890075Sobrien tmp = gen_rtx_IF_THEN_ELSE (GET_MODE (x), tmp, vtrue, vfalse); 110990075Sobrien tmp = gen_rtx_SET (VOIDmode, x, tmp); 111090075Sobrien 111190075Sobrien start_sequence (); 111290075Sobrien tmp = emit_insn (tmp); 111390075Sobrien 111490075Sobrien if (recog_memoized (tmp) >= 0) 111590075Sobrien { 111690075Sobrien tmp = get_insns (); 111790075Sobrien end_sequence (); 1118117395Skan emit_insn (tmp); 111990075Sobrien 112090075Sobrien return x; 112190075Sobrien } 112290075Sobrien 112390075Sobrien end_sequence (); 112490075Sobrien } 112590075Sobrien 112690075Sobrien /* Don't even try if the comparison operands are weird. */ 112790075Sobrien if (! general_operand (cmp_a, GET_MODE (cmp_a)) 112890075Sobrien || ! general_operand (cmp_b, GET_MODE (cmp_b))) 112990075Sobrien return NULL_RTX; 113090075Sobrien 113190075Sobrien#if HAVE_conditional_move 113290075Sobrien return emit_conditional_move (x, code, cmp_a, cmp_b, VOIDmode, 113390075Sobrien vtrue, vfalse, GET_MODE (x), 113490075Sobrien (code == LTU || code == GEU 113590075Sobrien || code == LEU || code == GTU)); 113690075Sobrien#else 113790075Sobrien /* We'll never get here, as noce_process_if_block doesn't call the 113890075Sobrien functions involved. Ifdef code, however, should be discouraged 1139132718Skan because it leads to typos in the code not selected. However, 114090075Sobrien emit_conditional_move won't exist either. */ 114190075Sobrien return NULL_RTX; 114290075Sobrien#endif 114390075Sobrien} 114490075Sobrien 114590075Sobrien/* Try only simple constants and registers here. More complex cases 114690075Sobrien are handled in noce_try_cmove_arith after noce_try_store_flag_arith 114790075Sobrien has had a go at it. */ 114890075Sobrien 114990075Sobrienstatic int 1150132718Skannoce_try_cmove (struct noce_if_info *if_info) 115190075Sobrien{ 115290075Sobrien enum rtx_code code; 115390075Sobrien rtx target, seq; 115490075Sobrien 115590075Sobrien if ((CONSTANT_P (if_info->a) || register_operand (if_info->a, VOIDmode)) 115690075Sobrien && (CONSTANT_P (if_info->b) || register_operand (if_info->b, VOIDmode))) 115790075Sobrien { 115890075Sobrien start_sequence (); 115990075Sobrien 116090075Sobrien code = GET_CODE (if_info->cond); 116190075Sobrien target = noce_emit_cmove (if_info, if_info->x, code, 116290075Sobrien XEXP (if_info->cond, 0), 116390075Sobrien XEXP (if_info->cond, 1), 116490075Sobrien if_info->a, if_info->b); 116590075Sobrien 116690075Sobrien if (target) 116790075Sobrien { 116890075Sobrien if (target != if_info->x) 116990075Sobrien noce_emit_move_insn (if_info->x, target); 117090075Sobrien 117190075Sobrien seq = get_insns (); 1172132718Skan unshare_ifcvt_sequence (if_info, seq); 117390075Sobrien end_sequence (); 1174132718Skan emit_insn_before_setloc (seq, if_info->jump, 1175132718Skan INSN_LOCATOR (if_info->insn_a)); 117690075Sobrien return TRUE; 117790075Sobrien } 117890075Sobrien else 117990075Sobrien { 118090075Sobrien end_sequence (); 118190075Sobrien return FALSE; 118290075Sobrien } 118390075Sobrien } 118490075Sobrien 118590075Sobrien return FALSE; 118690075Sobrien} 118790075Sobrien 118890075Sobrien/* Try more complex cases involving conditional_move. */ 118990075Sobrien 119090075Sobrienstatic int 1191132718Skannoce_try_cmove_arith (struct noce_if_info *if_info) 119290075Sobrien{ 119390075Sobrien rtx a = if_info->a; 119490075Sobrien rtx b = if_info->b; 119590075Sobrien rtx x = if_info->x; 1196146895Skan rtx orig_a, orig_b; 119790075Sobrien rtx insn_a, insn_b; 119890075Sobrien rtx tmp, target; 119990075Sobrien int is_mem = 0; 120090075Sobrien enum rtx_code code; 120190075Sobrien 120290075Sobrien /* A conditional move from two memory sources is equivalent to a 120390075Sobrien conditional on their addresses followed by a load. Don't do this 120490075Sobrien early because it'll screw alias analysis. Note that we've 120590075Sobrien already checked for no side effects. */ 120690075Sobrien if (! no_new_pseudos && cse_not_expected 120790075Sobrien && GET_CODE (a) == MEM && GET_CODE (b) == MEM 120890075Sobrien && BRANCH_COST >= 5) 120990075Sobrien { 121090075Sobrien a = XEXP (a, 0); 121190075Sobrien b = XEXP (b, 0); 121290075Sobrien x = gen_reg_rtx (Pmode); 121390075Sobrien is_mem = 1; 121490075Sobrien } 121590075Sobrien 121690075Sobrien /* ??? We could handle this if we knew that a load from A or B could 121790075Sobrien not fault. This is also true if we've already loaded 121890075Sobrien from the address along the path from ENTRY. */ 121990075Sobrien else if (may_trap_p (a) || may_trap_p (b)) 122090075Sobrien return FALSE; 122190075Sobrien 122290075Sobrien /* if (test) x = a + b; else x = c - d; 122390075Sobrien => y = a + b; 122490075Sobrien x = c - d; 122590075Sobrien if (test) 122690075Sobrien x = y; 122790075Sobrien */ 1228132718Skan 122990075Sobrien code = GET_CODE (if_info->cond); 123090075Sobrien insn_a = if_info->insn_a; 123190075Sobrien insn_b = if_info->insn_b; 123290075Sobrien 123390075Sobrien /* Possibly rearrange operands to make things come out more natural. */ 123490075Sobrien if (reversed_comparison_code (if_info->cond, if_info->jump) != UNKNOWN) 123590075Sobrien { 123690075Sobrien int reversep = 0; 123790075Sobrien if (rtx_equal_p (b, x)) 123890075Sobrien reversep = 1; 123990075Sobrien else if (general_operand (b, GET_MODE (b))) 124090075Sobrien reversep = 1; 124190075Sobrien 124290075Sobrien if (reversep) 124390075Sobrien { 124490075Sobrien code = reversed_comparison_code (if_info->cond, if_info->jump); 124590075Sobrien tmp = a, a = b, b = tmp; 124690075Sobrien tmp = insn_a, insn_a = insn_b, insn_b = tmp; 124790075Sobrien } 124890075Sobrien } 124990075Sobrien 125090075Sobrien start_sequence (); 125190075Sobrien 1252146895Skan orig_a = a; 1253146895Skan orig_b = b; 1254146895Skan 125590075Sobrien /* If either operand is complex, load it into a register first. 125690075Sobrien The best way to do this is to copy the original insn. In this 1257132718Skan way we preserve any clobbers etc that the insn may have had. 125890075Sobrien This is of course not possible in the IS_MEM case. */ 125990075Sobrien if (! general_operand (a, GET_MODE (a))) 126090075Sobrien { 126190075Sobrien rtx set; 126290075Sobrien 126390075Sobrien if (no_new_pseudos) 126490075Sobrien goto end_seq_and_fail; 126590075Sobrien 126690075Sobrien if (is_mem) 126790075Sobrien { 126890075Sobrien tmp = gen_reg_rtx (GET_MODE (a)); 126990075Sobrien tmp = emit_insn (gen_rtx_SET (VOIDmode, tmp, a)); 127090075Sobrien } 127190075Sobrien else if (! insn_a) 127290075Sobrien goto end_seq_and_fail; 127390075Sobrien else 127490075Sobrien { 127590075Sobrien a = gen_reg_rtx (GET_MODE (a)); 127690075Sobrien tmp = copy_rtx (insn_a); 127790075Sobrien set = single_set (tmp); 127890075Sobrien SET_DEST (set) = a; 127990075Sobrien tmp = emit_insn (PATTERN (tmp)); 128090075Sobrien } 128190075Sobrien if (recog_memoized (tmp) < 0) 128290075Sobrien goto end_seq_and_fail; 128390075Sobrien } 128490075Sobrien if (! general_operand (b, GET_MODE (b))) 128590075Sobrien { 1286146895Skan rtx set, last; 128790075Sobrien 128890075Sobrien if (no_new_pseudos) 128990075Sobrien goto end_seq_and_fail; 129090075Sobrien 129190075Sobrien if (is_mem) 129290075Sobrien { 129390075Sobrien tmp = gen_reg_rtx (GET_MODE (b)); 1294146895Skan tmp = gen_rtx_SET (VOIDmode, tmp, b); 129590075Sobrien } 1296132718Skan else if (! insn_b) 129790075Sobrien goto end_seq_and_fail; 129890075Sobrien else 129990075Sobrien { 130090075Sobrien b = gen_reg_rtx (GET_MODE (b)); 130190075Sobrien tmp = copy_rtx (insn_b); 130290075Sobrien set = single_set (tmp); 130390075Sobrien SET_DEST (set) = b; 1304146895Skan tmp = PATTERN (tmp); 130590075Sobrien } 1306146895Skan 1307146895Skan /* If insn to set up A clobbers any registers B depends on, try to 1308146895Skan swap insn that sets up A with the one that sets up B. If even 1309146895Skan that doesn't help, punt. */ 1310146895Skan last = get_last_insn (); 1311146895Skan if (last && modified_in_p (orig_b, last)) 1312146895Skan { 1313146895Skan tmp = emit_insn_before (tmp, get_insns ()); 1314146895Skan if (modified_in_p (orig_a, tmp)) 1315146895Skan goto end_seq_and_fail; 1316146895Skan } 1317146895Skan else 1318146895Skan tmp = emit_insn (tmp); 1319146895Skan 132090075Sobrien if (recog_memoized (tmp) < 0) 132190075Sobrien goto end_seq_and_fail; 132290075Sobrien } 132390075Sobrien 132490075Sobrien target = noce_emit_cmove (if_info, x, code, XEXP (if_info->cond, 0), 132590075Sobrien XEXP (if_info->cond, 1), a, b); 132690075Sobrien 132790075Sobrien if (! target) 132890075Sobrien goto end_seq_and_fail; 132990075Sobrien 133090075Sobrien /* If we're handling a memory for above, emit the load now. */ 133190075Sobrien if (is_mem) 133290075Sobrien { 133390075Sobrien tmp = gen_rtx_MEM (GET_MODE (if_info->x), target); 133490075Sobrien 133590075Sobrien /* Copy over flags as appropriate. */ 133690075Sobrien if (MEM_VOLATILE_P (if_info->a) || MEM_VOLATILE_P (if_info->b)) 133790075Sobrien MEM_VOLATILE_P (tmp) = 1; 133890075Sobrien if (MEM_IN_STRUCT_P (if_info->a) && MEM_IN_STRUCT_P (if_info->b)) 133990075Sobrien MEM_IN_STRUCT_P (tmp) = 1; 134090075Sobrien if (MEM_SCALAR_P (if_info->a) && MEM_SCALAR_P (if_info->b)) 134190075Sobrien MEM_SCALAR_P (tmp) = 1; 134290075Sobrien if (MEM_ALIAS_SET (if_info->a) == MEM_ALIAS_SET (if_info->b)) 134390075Sobrien set_mem_alias_set (tmp, MEM_ALIAS_SET (if_info->a)); 134490075Sobrien set_mem_align (tmp, 134590075Sobrien MIN (MEM_ALIGN (if_info->a), MEM_ALIGN (if_info->b))); 134690075Sobrien 134790075Sobrien noce_emit_move_insn (if_info->x, tmp); 134890075Sobrien } 134990075Sobrien else if (target != x) 135090075Sobrien noce_emit_move_insn (x, target); 135190075Sobrien 135290075Sobrien tmp = get_insns (); 1353132718Skan unshare_ifcvt_sequence (if_info, tmp); 135490075Sobrien end_sequence (); 1355132718Skan emit_insn_before_setloc (tmp, if_info->jump, INSN_LOCATOR (if_info->insn_a)); 135690075Sobrien return TRUE; 135790075Sobrien 135890075Sobrien end_seq_and_fail: 135990075Sobrien end_sequence (); 136090075Sobrien return FALSE; 136190075Sobrien} 136290075Sobrien 136390075Sobrien/* For most cases, the simplified condition we found is the best 136490075Sobrien choice, but this is not the case for the min/max/abs transforms. 136590075Sobrien For these we wish to know that it is A or B in the condition. */ 136690075Sobrien 136790075Sobrienstatic rtx 1368132718Skannoce_get_alt_condition (struct noce_if_info *if_info, rtx target, 1369132718Skan rtx *earliest) 137090075Sobrien{ 137190075Sobrien rtx cond, set, insn; 137290075Sobrien int reverse; 137390075Sobrien 137490075Sobrien /* If target is already mentioned in the known condition, return it. */ 137590075Sobrien if (reg_mentioned_p (target, if_info->cond)) 137690075Sobrien { 137790075Sobrien *earliest = if_info->cond_earliest; 137890075Sobrien return if_info->cond; 137990075Sobrien } 138090075Sobrien 138190075Sobrien set = pc_set (if_info->jump); 138290075Sobrien cond = XEXP (SET_SRC (set), 0); 138390075Sobrien reverse 138490075Sobrien = GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF 138590075Sobrien && XEXP (XEXP (SET_SRC (set), 2), 0) == JUMP_LABEL (if_info->jump); 138690075Sobrien 138790075Sobrien /* If we're looking for a constant, try to make the conditional 138890075Sobrien have that constant in it. There are two reasons why it may 138990075Sobrien not have the constant we want: 139090075Sobrien 139190075Sobrien 1. GCC may have needed to put the constant in a register, because 139290075Sobrien the target can't compare directly against that constant. For 139390075Sobrien this case, we look for a SET immediately before the comparison 139490075Sobrien that puts a constant in that register. 139590075Sobrien 139690075Sobrien 2. GCC may have canonicalized the conditional, for example 139790075Sobrien replacing "if x < 4" with "if x <= 3". We can undo that (or 139890075Sobrien make equivalent types of changes) to get the constants we need 139990075Sobrien if they're off by one in the right direction. */ 140090075Sobrien 140190075Sobrien if (GET_CODE (target) == CONST_INT) 140290075Sobrien { 140390075Sobrien enum rtx_code code = GET_CODE (if_info->cond); 140490075Sobrien rtx op_a = XEXP (if_info->cond, 0); 140590075Sobrien rtx op_b = XEXP (if_info->cond, 1); 140690075Sobrien rtx prev_insn; 140790075Sobrien 140890075Sobrien /* First, look to see if we put a constant in a register. */ 140990075Sobrien prev_insn = PREV_INSN (if_info->cond_earliest); 141090075Sobrien if (prev_insn 141190075Sobrien && INSN_P (prev_insn) 141290075Sobrien && GET_CODE (PATTERN (prev_insn)) == SET) 141390075Sobrien { 141490075Sobrien rtx src = find_reg_equal_equiv_note (prev_insn); 141590075Sobrien if (!src) 141690075Sobrien src = SET_SRC (PATTERN (prev_insn)); 141790075Sobrien if (GET_CODE (src) == CONST_INT) 141890075Sobrien { 141990075Sobrien if (rtx_equal_p (op_a, SET_DEST (PATTERN (prev_insn)))) 142090075Sobrien op_a = src; 142190075Sobrien else if (rtx_equal_p (op_b, SET_DEST (PATTERN (prev_insn)))) 142290075Sobrien op_b = src; 142390075Sobrien 142490075Sobrien if (GET_CODE (op_a) == CONST_INT) 142590075Sobrien { 142690075Sobrien rtx tmp = op_a; 142790075Sobrien op_a = op_b; 142890075Sobrien op_b = tmp; 142990075Sobrien code = swap_condition (code); 143090075Sobrien } 143190075Sobrien } 143290075Sobrien } 143390075Sobrien 143490075Sobrien /* Now, look to see if we can get the right constant by 143590075Sobrien adjusting the conditional. */ 143690075Sobrien if (GET_CODE (op_b) == CONST_INT) 143790075Sobrien { 143890075Sobrien HOST_WIDE_INT desired_val = INTVAL (target); 143990075Sobrien HOST_WIDE_INT actual_val = INTVAL (op_b); 144090075Sobrien 144190075Sobrien switch (code) 144290075Sobrien { 144390075Sobrien case LT: 144490075Sobrien if (actual_val == desired_val + 1) 144590075Sobrien { 144690075Sobrien code = LE; 144790075Sobrien op_b = GEN_INT (desired_val); 144890075Sobrien } 144990075Sobrien break; 145090075Sobrien case LE: 145190075Sobrien if (actual_val == desired_val - 1) 145290075Sobrien { 145390075Sobrien code = LT; 145490075Sobrien op_b = GEN_INT (desired_val); 145590075Sobrien } 145690075Sobrien break; 145790075Sobrien case GT: 145890075Sobrien if (actual_val == desired_val - 1) 145990075Sobrien { 146090075Sobrien code = GE; 146190075Sobrien op_b = GEN_INT (desired_val); 146290075Sobrien } 146390075Sobrien break; 146490075Sobrien case GE: 146590075Sobrien if (actual_val == desired_val + 1) 146690075Sobrien { 146790075Sobrien code = GT; 146890075Sobrien op_b = GEN_INT (desired_val); 146990075Sobrien } 147090075Sobrien break; 147190075Sobrien default: 147290075Sobrien break; 147390075Sobrien } 147490075Sobrien } 147590075Sobrien 147690075Sobrien /* If we made any changes, generate a new conditional that is 147790075Sobrien equivalent to what we started with, but has the right 147890075Sobrien constants in it. */ 147990075Sobrien if (code != GET_CODE (if_info->cond) 148090075Sobrien || op_a != XEXP (if_info->cond, 0) 148190075Sobrien || op_b != XEXP (if_info->cond, 1)) 148290075Sobrien { 148390075Sobrien cond = gen_rtx_fmt_ee (code, GET_MODE (cond), op_a, op_b); 148490075Sobrien *earliest = if_info->cond_earliest; 148590075Sobrien return cond; 148690075Sobrien } 148790075Sobrien } 148890075Sobrien 148990075Sobrien cond = canonicalize_condition (if_info->jump, cond, reverse, 1490132718Skan earliest, target, false); 149190075Sobrien if (! cond || ! reg_mentioned_p (target, cond)) 149290075Sobrien return NULL; 149390075Sobrien 149490075Sobrien /* We almost certainly searched back to a different place. 149590075Sobrien Need to re-verify correct lifetimes. */ 149690075Sobrien 149790075Sobrien /* X may not be mentioned in the range (cond_earliest, jump]. */ 149890075Sobrien for (insn = if_info->jump; insn != *earliest; insn = PREV_INSN (insn)) 1499117395Skan if (INSN_P (insn) && reg_overlap_mentioned_p (if_info->x, PATTERN (insn))) 150090075Sobrien return NULL; 150190075Sobrien 150290075Sobrien /* A and B may not be modified in the range [cond_earliest, jump). */ 150390075Sobrien for (insn = *earliest; insn != if_info->jump; insn = NEXT_INSN (insn)) 150490075Sobrien if (INSN_P (insn) 150590075Sobrien && (modified_in_p (if_info->a, insn) 150690075Sobrien || modified_in_p (if_info->b, insn))) 150790075Sobrien return NULL; 150890075Sobrien 150990075Sobrien return cond; 151090075Sobrien} 151190075Sobrien 151290075Sobrien/* Convert "if (a < b) x = a; else x = b;" to "x = min(a, b);", etc. */ 151390075Sobrien 151490075Sobrienstatic int 1515132718Skannoce_try_minmax (struct noce_if_info *if_info) 1516132718Skan{ 151790075Sobrien rtx cond, earliest, target, seq; 151890075Sobrien enum rtx_code code, op; 151990075Sobrien int unsignedp; 152090075Sobrien 152190075Sobrien /* ??? Can't guarantee that expand_binop won't create pseudos. */ 152290075Sobrien if (no_new_pseudos) 152390075Sobrien return FALSE; 152490075Sobrien 1525117395Skan /* ??? Reject modes with NaNs or signed zeros since we don't know how 1526117395Skan they will be resolved with an SMIN/SMAX. It wouldn't be too hard 152790075Sobrien to get the target to tell us... */ 1528117395Skan if (HONOR_SIGNED_ZEROS (GET_MODE (if_info->x)) 1529117395Skan || HONOR_NANS (GET_MODE (if_info->x))) 153090075Sobrien return FALSE; 153190075Sobrien 153290075Sobrien cond = noce_get_alt_condition (if_info, if_info->a, &earliest); 153390075Sobrien if (!cond) 153490075Sobrien return FALSE; 153590075Sobrien 153690075Sobrien /* Verify the condition is of the form we expect, and canonicalize 153790075Sobrien the comparison code. */ 153890075Sobrien code = GET_CODE (cond); 153990075Sobrien if (rtx_equal_p (XEXP (cond, 0), if_info->a)) 154090075Sobrien { 154190075Sobrien if (! rtx_equal_p (XEXP (cond, 1), if_info->b)) 154290075Sobrien return FALSE; 154390075Sobrien } 154490075Sobrien else if (rtx_equal_p (XEXP (cond, 1), if_info->a)) 154590075Sobrien { 154690075Sobrien if (! rtx_equal_p (XEXP (cond, 0), if_info->b)) 154790075Sobrien return FALSE; 154890075Sobrien code = swap_condition (code); 154990075Sobrien } 155090075Sobrien else 155190075Sobrien return FALSE; 155290075Sobrien 155390075Sobrien /* Determine what sort of operation this is. Note that the code is for 155490075Sobrien a taken branch, so the code->operation mapping appears backwards. */ 155590075Sobrien switch (code) 155690075Sobrien { 155790075Sobrien case LT: 155890075Sobrien case LE: 155990075Sobrien case UNLT: 156090075Sobrien case UNLE: 156190075Sobrien op = SMAX; 156290075Sobrien unsignedp = 0; 156390075Sobrien break; 156490075Sobrien case GT: 156590075Sobrien case GE: 156690075Sobrien case UNGT: 156790075Sobrien case UNGE: 156890075Sobrien op = SMIN; 156990075Sobrien unsignedp = 0; 157090075Sobrien break; 157190075Sobrien case LTU: 157290075Sobrien case LEU: 157390075Sobrien op = UMAX; 157490075Sobrien unsignedp = 1; 157590075Sobrien break; 157690075Sobrien case GTU: 157790075Sobrien case GEU: 157890075Sobrien op = UMIN; 157990075Sobrien unsignedp = 1; 158090075Sobrien break; 158190075Sobrien default: 158290075Sobrien return FALSE; 158390075Sobrien } 158490075Sobrien 158590075Sobrien start_sequence (); 158690075Sobrien 158790075Sobrien target = expand_simple_binop (GET_MODE (if_info->x), op, 158890075Sobrien if_info->a, if_info->b, 158990075Sobrien if_info->x, unsignedp, OPTAB_WIDEN); 159090075Sobrien if (! target) 159190075Sobrien { 159290075Sobrien end_sequence (); 159390075Sobrien return FALSE; 159490075Sobrien } 159590075Sobrien if (target != if_info->x) 159690075Sobrien noce_emit_move_insn (if_info->x, target); 159790075Sobrien 159890075Sobrien seq = get_insns (); 1599132718Skan unshare_ifcvt_sequence (if_info, seq); 1600132718Skan end_sequence (); 160190075Sobrien 160290075Sobrien if (seq_contains_jump (seq)) 160390075Sobrien return FALSE; 160490075Sobrien 1605132718Skan emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATOR (if_info->insn_a)); 160690075Sobrien if_info->cond = cond; 160790075Sobrien if_info->cond_earliest = earliest; 160890075Sobrien 160990075Sobrien return TRUE; 161090075Sobrien} 161190075Sobrien 161290075Sobrien/* Convert "if (a < 0) x = -a; else x = a;" to "x = abs(a);", etc. */ 161390075Sobrien 161490075Sobrienstatic int 1615132718Skannoce_try_abs (struct noce_if_info *if_info) 1616132718Skan{ 161790075Sobrien rtx cond, earliest, target, seq, a, b, c; 161890075Sobrien int negate; 161990075Sobrien 162090075Sobrien /* ??? Can't guarantee that expand_binop won't create pseudos. */ 162190075Sobrien if (no_new_pseudos) 162290075Sobrien return FALSE; 162390075Sobrien 162490075Sobrien /* Recognize A and B as constituting an ABS or NABS. */ 162590075Sobrien a = if_info->a; 162690075Sobrien b = if_info->b; 162790075Sobrien if (GET_CODE (a) == NEG && rtx_equal_p (XEXP (a, 0), b)) 162890075Sobrien negate = 0; 162990075Sobrien else if (GET_CODE (b) == NEG && rtx_equal_p (XEXP (b, 0), a)) 163090075Sobrien { 163190075Sobrien c = a; a = b; b = c; 163290075Sobrien negate = 1; 163390075Sobrien } 163490075Sobrien else 163590075Sobrien return FALSE; 1636132718Skan 163790075Sobrien cond = noce_get_alt_condition (if_info, b, &earliest); 163890075Sobrien if (!cond) 163990075Sobrien return FALSE; 164090075Sobrien 164190075Sobrien /* Verify the condition is of the form we expect. */ 164290075Sobrien if (rtx_equal_p (XEXP (cond, 0), b)) 164390075Sobrien c = XEXP (cond, 1); 164490075Sobrien else if (rtx_equal_p (XEXP (cond, 1), b)) 164590075Sobrien c = XEXP (cond, 0); 164690075Sobrien else 164790075Sobrien return FALSE; 164890075Sobrien 164990075Sobrien /* Verify that C is zero. Search backward through the block for 165090075Sobrien a REG_EQUAL note if necessary. */ 165190075Sobrien if (REG_P (c)) 165290075Sobrien { 165390075Sobrien rtx insn, note = NULL; 165490075Sobrien for (insn = earliest; 1655132718Skan insn != BB_HEAD (if_info->test_bb); 165690075Sobrien insn = PREV_INSN (insn)) 1657132718Skan if (INSN_P (insn) 165890075Sobrien && ((note = find_reg_note (insn, REG_EQUAL, c)) 165990075Sobrien || (note = find_reg_note (insn, REG_EQUIV, c)))) 166090075Sobrien break; 166190075Sobrien if (! note) 166290075Sobrien return FALSE; 166390075Sobrien c = XEXP (note, 0); 166490075Sobrien } 166590075Sobrien if (GET_CODE (c) == MEM 166690075Sobrien && GET_CODE (XEXP (c, 0)) == SYMBOL_REF 166790075Sobrien && CONSTANT_POOL_ADDRESS_P (XEXP (c, 0))) 166890075Sobrien c = get_pool_constant (XEXP (c, 0)); 166990075Sobrien 167090075Sobrien /* Work around funny ideas get_condition has wrt canonicalization. 1671132718Skan Note that these rtx constants are known to be CONST_INT, and 167290075Sobrien therefore imply integer comparisons. */ 167390075Sobrien if (c == constm1_rtx && GET_CODE (cond) == GT) 167490075Sobrien ; 167590075Sobrien else if (c == const1_rtx && GET_CODE (cond) == LT) 167690075Sobrien ; 167790075Sobrien else if (c != CONST0_RTX (GET_MODE (b))) 167890075Sobrien return FALSE; 167990075Sobrien 168090075Sobrien /* Determine what sort of operation this is. */ 168190075Sobrien switch (GET_CODE (cond)) 168290075Sobrien { 168390075Sobrien case LT: 168490075Sobrien case LE: 168590075Sobrien case UNLT: 168690075Sobrien case UNLE: 168790075Sobrien negate = !negate; 168890075Sobrien break; 168990075Sobrien case GT: 169090075Sobrien case GE: 169190075Sobrien case UNGT: 169290075Sobrien case UNGE: 169390075Sobrien break; 169490075Sobrien default: 169590075Sobrien return FALSE; 169690075Sobrien } 169790075Sobrien 169890075Sobrien start_sequence (); 169990075Sobrien 1700132718Skan target = expand_abs_nojump (GET_MODE (if_info->x), b, if_info->x, 1); 170190075Sobrien 1702132718Skan /* ??? It's a quandary whether cmove would be better here, especially 170390075Sobrien for integers. Perhaps combine will clean things up. */ 170490075Sobrien if (target && negate) 170590075Sobrien target = expand_simple_unop (GET_MODE (target), NEG, target, if_info->x, 0); 170690075Sobrien 170790075Sobrien if (! target) 170890075Sobrien { 170990075Sobrien end_sequence (); 171090075Sobrien return FALSE; 171190075Sobrien } 171290075Sobrien 171390075Sobrien if (target != if_info->x) 171490075Sobrien noce_emit_move_insn (if_info->x, target); 171590075Sobrien 171690075Sobrien seq = get_insns (); 1717132718Skan unshare_ifcvt_sequence (if_info, seq); 1718132718Skan end_sequence (); 171990075Sobrien 172090075Sobrien if (seq_contains_jump (seq)) 172190075Sobrien return FALSE; 172290075Sobrien 1723132718Skan emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATOR (if_info->insn_a)); 172490075Sobrien if_info->cond = cond; 172590075Sobrien if_info->cond_earliest = earliest; 172690075Sobrien 172790075Sobrien return TRUE; 172890075Sobrien} 172990075Sobrien 1730102780Skan/* Similar to get_condition, only the resulting condition must be 1731102780Skan valid at JUMP, instead of at EARLIEST. */ 173290075Sobrien 173390075Sobrienstatic rtx 1734132718Skannoce_get_condition (rtx jump, rtx *earliest) 173590075Sobrien{ 1736102780Skan rtx cond, set, tmp, insn; 1737102780Skan bool reverse; 173890075Sobrien 173990075Sobrien if (! any_condjump_p (jump)) 174090075Sobrien return NULL_RTX; 174190075Sobrien 174290075Sobrien set = pc_set (jump); 174390075Sobrien 1744102780Skan /* If this branches to JUMP_LABEL when the condition is false, 1745102780Skan reverse the condition. */ 1746102780Skan reverse = (GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF 1747102780Skan && XEXP (XEXP (SET_SRC (set), 2), 0) == JUMP_LABEL (jump)); 1748102780Skan 1749102780Skan /* If the condition variable is a register and is MODE_INT, accept it. */ 1750102780Skan 175190075Sobrien cond = XEXP (SET_SRC (set), 0); 1752102780Skan tmp = XEXP (cond, 0); 1753102780Skan if (REG_P (tmp) && GET_MODE_CLASS (GET_MODE (tmp)) == MODE_INT) 175490075Sobrien { 175590075Sobrien *earliest = jump; 175690075Sobrien 1757102780Skan if (reverse) 175890075Sobrien cond = gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond)), 1759102780Skan GET_MODE (cond), tmp, XEXP (cond, 1)); 1760102780Skan return cond; 176190075Sobrien } 176290075Sobrien 1763102780Skan /* Otherwise, fall back on canonicalize_condition to do the dirty 1764102780Skan work of manipulating MODE_CC values and COMPARE rtx codes. */ 1765102780Skan 1766132718Skan tmp = canonicalize_condition (jump, cond, reverse, earliest, NULL_RTX, 1767132718Skan false); 1768102780Skan if (!tmp) 1769102780Skan return NULL_RTX; 1770102780Skan 1771102780Skan /* We are going to insert code before JUMP, not before EARLIEST. 1772102780Skan We must therefore be certain that the given condition is valid 1773102780Skan at JUMP by virtue of not having been modified since. */ 1774102780Skan for (insn = *earliest; insn != jump; insn = NEXT_INSN (insn)) 1775102780Skan if (INSN_P (insn) && modified_in_p (tmp, insn)) 1776102780Skan break; 1777102780Skan if (insn == jump) 1778102780Skan return tmp; 1779102780Skan 1780102780Skan /* The condition was modified. See if we can get a partial result 1781102780Skan that doesn't follow all the reversals. Perhaps combine can fold 1782102780Skan them together later. */ 1783102780Skan tmp = XEXP (tmp, 0); 1784102780Skan if (!REG_P (tmp) || GET_MODE_CLASS (GET_MODE (tmp)) != MODE_INT) 1785102780Skan return NULL_RTX; 1786132718Skan tmp = canonicalize_condition (jump, cond, reverse, earliest, tmp, 1787132718Skan false); 1788102780Skan if (!tmp) 1789102780Skan return NULL_RTX; 1790102780Skan 1791102780Skan /* For sanity's sake, re-validate the new result. */ 1792102780Skan for (insn = *earliest; insn != jump; insn = NEXT_INSN (insn)) 1793102780Skan if (INSN_P (insn) && modified_in_p (tmp, insn)) 1794102780Skan return NULL_RTX; 1795102780Skan 1796102780Skan return tmp; 179790075Sobrien} 179890075Sobrien 179990075Sobrien/* Return true if OP is ok for if-then-else processing. */ 180090075Sobrien 180190075Sobrienstatic int 1802132718Skannoce_operand_ok (rtx op) 180390075Sobrien{ 180490075Sobrien /* We special-case memories, so handle any of them with 180590075Sobrien no address side effects. */ 180690075Sobrien if (GET_CODE (op) == MEM) 180790075Sobrien return ! side_effects_p (XEXP (op, 0)); 180890075Sobrien 180990075Sobrien if (side_effects_p (op)) 181090075Sobrien return FALSE; 181190075Sobrien 181290075Sobrien return ! may_trap_p (op); 181390075Sobrien} 181490075Sobrien 181590075Sobrien/* Given a simple IF-THEN or IF-THEN-ELSE block, attempt to convert it 181690075Sobrien without using conditional execution. Return TRUE if we were 1817117395Skan successful at converting the block. */ 181890075Sobrien 181990075Sobrienstatic int 1820132718Skannoce_process_if_block (struct ce_if_block * ce_info) 182190075Sobrien{ 1822117395Skan basic_block test_bb = ce_info->test_bb; /* test block */ 1823117395Skan basic_block then_bb = ce_info->then_bb; /* THEN */ 1824117395Skan basic_block else_bb = ce_info->else_bb; /* ELSE or NULL */ 1825117395Skan struct noce_if_info if_info; 1826117395Skan rtx insn_a, insn_b; 1827117395Skan rtx set_a, set_b; 1828117395Skan rtx orig_x, x, a, b; 1829117395Skan rtx jump, cond; 1830117395Skan 183190075Sobrien /* We're looking for patterns of the form 183290075Sobrien 183390075Sobrien (1) if (...) x = a; else x = b; 183490075Sobrien (2) x = b; if (...) x = a; 183590075Sobrien (3) if (...) x = a; // as if with an initial x = x. 183690075Sobrien 183790075Sobrien The later patterns require jumps to be more expensive. 183890075Sobrien 183990075Sobrien ??? For future expansion, look for multiple X in such patterns. */ 184090075Sobrien 1841117395Skan /* If test is comprised of && or || elements, don't handle it unless it is 1842117395Skan the special case of && elements without an ELSE block. */ 1843117395Skan if (ce_info->num_multiple_test_blocks) 1844117395Skan { 1845117395Skan if (else_bb || ! ce_info->and_and_p) 1846117395Skan return FALSE; 184790075Sobrien 1848117395Skan ce_info->test_bb = test_bb = ce_info->last_test_bb; 1849117395Skan ce_info->num_multiple_test_blocks = 0; 1850117395Skan ce_info->num_and_and_blocks = 0; 1851117395Skan ce_info->num_or_or_blocks = 0; 1852117395Skan } 1853117395Skan 185490075Sobrien /* If this is not a standard conditional jump, we can't parse it. */ 1855132718Skan jump = BB_END (test_bb); 185690075Sobrien cond = noce_get_condition (jump, &if_info.cond_earliest); 185790075Sobrien if (! cond) 185890075Sobrien return FALSE; 185990075Sobrien 1860117395Skan /* If the conditional jump is more than just a conditional 1861117395Skan jump, then we can not do if-conversion on this block. */ 186290075Sobrien if (! onlyjump_p (jump)) 186390075Sobrien return FALSE; 186490075Sobrien 186590075Sobrien /* We must be comparing objects whose modes imply the size. */ 186690075Sobrien if (GET_MODE (XEXP (cond, 0)) == BLKmode) 186790075Sobrien return FALSE; 186890075Sobrien 186990075Sobrien /* Look for one of the potential sets. */ 187090075Sobrien insn_a = first_active_insn (then_bb); 187190075Sobrien if (! insn_a 1872117395Skan || insn_a != last_active_insn (then_bb, FALSE) 187390075Sobrien || (set_a = single_set (insn_a)) == NULL_RTX) 187490075Sobrien return FALSE; 187590075Sobrien 187690075Sobrien x = SET_DEST (set_a); 187790075Sobrien a = SET_SRC (set_a); 187890075Sobrien 187990075Sobrien /* Look for the other potential set. Make sure we've got equivalent 188090075Sobrien destinations. */ 188190075Sobrien /* ??? This is overconservative. Storing to two different mems is 188290075Sobrien as easy as conditionally computing the address. Storing to a 188390075Sobrien single mem merely requires a scratch memory to use as one of the 188490075Sobrien destination addresses; often the memory immediately below the 188590075Sobrien stack pointer is available for this. */ 188690075Sobrien set_b = NULL_RTX; 188790075Sobrien if (else_bb) 188890075Sobrien { 188990075Sobrien insn_b = first_active_insn (else_bb); 189090075Sobrien if (! insn_b 1891117395Skan || insn_b != last_active_insn (else_bb, FALSE) 189290075Sobrien || (set_b = single_set (insn_b)) == NULL_RTX 189390075Sobrien || ! rtx_equal_p (x, SET_DEST (set_b))) 189490075Sobrien return FALSE; 189590075Sobrien } 189690075Sobrien else 189790075Sobrien { 189890075Sobrien insn_b = prev_nonnote_insn (if_info.cond_earliest); 1899117395Skan /* We're going to be moving the evaluation of B down from above 1900117395Skan COND_EARLIEST to JUMP. Make sure the relevant data is still 1901117395Skan intact. */ 190290075Sobrien if (! insn_b 190390075Sobrien || GET_CODE (insn_b) != INSN 190490075Sobrien || (set_b = single_set (insn_b)) == NULL_RTX 190590075Sobrien || ! rtx_equal_p (x, SET_DEST (set_b)) 1906117395Skan || reg_overlap_mentioned_p (x, SET_SRC (set_b)) 1907117395Skan || modified_between_p (SET_SRC (set_b), 1908117395Skan PREV_INSN (if_info.cond_earliest), jump) 1909117395Skan /* Likewise with X. In particular this can happen when 1910117395Skan noce_get_condition looks farther back in the instruction 1911117395Skan stream than one might expect. */ 1912117395Skan || reg_overlap_mentioned_p (x, cond) 1913117395Skan || reg_overlap_mentioned_p (x, a) 1914117395Skan || modified_between_p (x, PREV_INSN (if_info.cond_earliest), jump)) 191590075Sobrien insn_b = set_b = NULL_RTX; 191690075Sobrien } 191790075Sobrien 1918117395Skan /* If x has side effects then only the if-then-else form is safe to 1919117395Skan convert. But even in that case we would need to restore any notes 1920132718Skan (such as REG_INC) at then end. That can be tricky if 1921117395Skan noce_emit_move_insn expands to more than one insn, so disable the 1922117395Skan optimization entirely for now if there are side effects. */ 1923117395Skan if (side_effects_p (x)) 1924117395Skan return FALSE; 192590075Sobrien 1926117395Skan b = (set_b ? SET_SRC (set_b) : x); 192790075Sobrien 192890075Sobrien /* Only operate on register destinations, and even then avoid extending 192990075Sobrien the lifetime of hard registers on small register class machines. */ 193090075Sobrien orig_x = x; 193190075Sobrien if (GET_CODE (x) != REG 193290075Sobrien || (SMALL_REGISTER_CLASSES 193390075Sobrien && REGNO (x) < FIRST_PSEUDO_REGISTER)) 193490075Sobrien { 1935132718Skan if (no_new_pseudos || GET_MODE (x) == BLKmode) 193690075Sobrien return FALSE; 193790075Sobrien x = gen_reg_rtx (GET_MODE (GET_CODE (x) == STRICT_LOW_PART 193890075Sobrien ? XEXP (x, 0) : x)); 193990075Sobrien } 194090075Sobrien 194190075Sobrien /* Don't operate on sources that may trap or are volatile. */ 194290075Sobrien if (! noce_operand_ok (a) || ! noce_operand_ok (b)) 194390075Sobrien return FALSE; 194490075Sobrien 194590075Sobrien /* Set up the info block for our subroutines. */ 194690075Sobrien if_info.test_bb = test_bb; 194790075Sobrien if_info.cond = cond; 194890075Sobrien if_info.jump = jump; 194990075Sobrien if_info.insn_a = insn_a; 195090075Sobrien if_info.insn_b = insn_b; 195190075Sobrien if_info.x = x; 195290075Sobrien if_info.a = a; 195390075Sobrien if_info.b = b; 195490075Sobrien 195590075Sobrien /* Try optimizations in some approximation of a useful order. */ 195690075Sobrien /* ??? Should first look to see if X is live incoming at all. If it 195790075Sobrien isn't, we don't need anything but an unconditional set. */ 195890075Sobrien 195990075Sobrien /* Look and see if A and B are really the same. Avoid creating silly 196090075Sobrien cmove constructs that no one will fix up later. */ 196190075Sobrien if (rtx_equal_p (a, b)) 196290075Sobrien { 196390075Sobrien /* If we have an INSN_B, we don't have to create any new rtl. Just 196490075Sobrien move the instruction that we already have. If we don't have an 196590075Sobrien INSN_B, that means that A == X, and we've got a noop move. In 196690075Sobrien that case don't do anything and let the code below delete INSN_A. */ 196790075Sobrien if (insn_b && else_bb) 196890075Sobrien { 196990075Sobrien rtx note; 197090075Sobrien 1971132718Skan if (else_bb && insn_b == BB_END (else_bb)) 1972132718Skan BB_END (else_bb) = PREV_INSN (insn_b); 1973117395Skan reorder_insns (insn_b, insn_b, PREV_INSN (jump)); 197490075Sobrien 197590075Sobrien /* If there was a REG_EQUAL note, delete it since it may have been 197690075Sobrien true due to this insn being after a jump. */ 197790075Sobrien if ((note = find_reg_note (insn_b, REG_EQUAL, NULL_RTX)) != 0) 197890075Sobrien remove_note (insn_b, note); 197990075Sobrien 198090075Sobrien insn_b = NULL_RTX; 198190075Sobrien } 198290075Sobrien /* If we have "x = b; if (...) x = a;", and x has side-effects, then 198390075Sobrien x must be executed twice. */ 198490075Sobrien else if (insn_b && side_effects_p (orig_x)) 198590075Sobrien return FALSE; 1986132718Skan 198790075Sobrien x = orig_x; 198890075Sobrien goto success; 198990075Sobrien } 199090075Sobrien 1991132718Skan /* Disallow the "if (...) x = a;" form (with an implicit "else x = x;") 1992132718Skan for most optimizations if writing to x may trap, i.e. its a memory 1993132718Skan other than a static var or a stack slot. */ 1994132718Skan if (! set_b 1995132718Skan && GET_CODE (orig_x) == MEM 1996132718Skan && ! MEM_NOTRAP_P (orig_x) 1997132718Skan && rtx_addr_can_trap_p (XEXP (orig_x, 0))) 1998132718Skan { 1999132718Skan if (HAVE_conditional_move) 2000132718Skan { 2001132718Skan if (noce_try_cmove (&if_info)) 2002132718Skan goto success; 2003132718Skan if (! HAVE_conditional_execution 2004132718Skan && noce_try_cmove_arith (&if_info)) 2005132718Skan goto success; 2006132718Skan } 2007132718Skan return FALSE; 2008132718Skan } 2009132718Skan 2010132718Skan if (noce_try_move (&if_info)) 2011132718Skan goto success; 201290075Sobrien if (noce_try_store_flag (&if_info)) 201390075Sobrien goto success; 201490075Sobrien if (noce_try_minmax (&if_info)) 201590075Sobrien goto success; 201690075Sobrien if (noce_try_abs (&if_info)) 201790075Sobrien goto success; 201890075Sobrien if (HAVE_conditional_move 201990075Sobrien && noce_try_cmove (&if_info)) 202090075Sobrien goto success; 202190075Sobrien if (! HAVE_conditional_execution) 202290075Sobrien { 202390075Sobrien if (noce_try_store_flag_constants (&if_info)) 202490075Sobrien goto success; 2025132718Skan if (noce_try_addcc (&if_info)) 202690075Sobrien goto success; 202790075Sobrien if (noce_try_store_flag_mask (&if_info)) 202890075Sobrien goto success; 202990075Sobrien if (HAVE_conditional_move 203090075Sobrien && noce_try_cmove_arith (&if_info)) 203190075Sobrien goto success; 203290075Sobrien } 203390075Sobrien 203490075Sobrien return FALSE; 203590075Sobrien 203690075Sobrien success: 203790075Sobrien /* The original sets may now be killed. */ 203890075Sobrien delete_insn (insn_a); 203990075Sobrien 204090075Sobrien /* Several special cases here: First, we may have reused insn_b above, 204190075Sobrien in which case insn_b is now NULL. Second, we want to delete insn_b 204290075Sobrien if it came from the ELSE block, because follows the now correct 204390075Sobrien write that appears in the TEST block. However, if we got insn_b from 204490075Sobrien the TEST block, it may in fact be loading data needed for the comparison. 204590075Sobrien We'll let life_analysis remove the insn if it's really dead. */ 204690075Sobrien if (insn_b && else_bb) 204790075Sobrien delete_insn (insn_b); 204890075Sobrien 2049117395Skan /* The new insns will have been inserted immediately before the jump. We 2050117395Skan should be able to remove the jump with impunity, but the condition itself 2051117395Skan may have been modified by gcse to be shared across basic blocks. */ 205290075Sobrien delete_insn (jump); 205390075Sobrien 205490075Sobrien /* If we used a temporary, fix it up now. */ 205590075Sobrien if (orig_x != x) 205690075Sobrien { 205790075Sobrien start_sequence (); 2058132718Skan noce_emit_move_insn (orig_x, x); 2059117395Skan insn_b = get_insns (); 2060132718Skan set_used_flags (orig_x); 2061132718Skan unshare_all_rtl_in_chain (insn_b); 206290075Sobrien end_sequence (); 206390075Sobrien 2064132718Skan emit_insn_after_setloc (insn_b, BB_END (test_bb), INSN_LOCATOR (insn_a)); 206590075Sobrien } 206690075Sobrien 206790075Sobrien /* Merge the blocks! */ 2068117395Skan merge_if_block (ce_info); 206990075Sobrien 207090075Sobrien return TRUE; 207190075Sobrien} 207290075Sobrien 207390075Sobrien/* Attempt to convert an IF-THEN or IF-THEN-ELSE block into 207490075Sobrien straight line code. Return true if successful. */ 207590075Sobrien 207690075Sobrienstatic int 2077132718Skanprocess_if_block (struct ce_if_block * ce_info) 207890075Sobrien{ 207990075Sobrien if (! reload_completed 2080117395Skan && noce_process_if_block (ce_info)) 208190075Sobrien return TRUE; 208290075Sobrien 2083117395Skan if (HAVE_conditional_execution && reload_completed) 2084117395Skan { 2085117395Skan /* If we have && and || tests, try to first handle combining the && and 2086117395Skan || tests into the conditional code, and if that fails, go back and 2087117395Skan handle it without the && and ||, which at present handles the && case 2088117395Skan if there was no ELSE block. */ 2089117395Skan if (cond_exec_process_if_block (ce_info, TRUE)) 2090117395Skan return TRUE; 209190075Sobrien 2092117395Skan if (ce_info->num_multiple_test_blocks) 2093117395Skan { 2094117395Skan cancel_changes (0); 2095117395Skan 2096117395Skan if (cond_exec_process_if_block (ce_info, FALSE)) 2097117395Skan return TRUE; 2098117395Skan } 2099117395Skan } 2100117395Skan 210190075Sobrien return FALSE; 210290075Sobrien} 210390075Sobrien 210490075Sobrien/* Merge the blocks and mark for local life update. */ 210590075Sobrien 210690075Sobrienstatic void 2107132718Skanmerge_if_block (struct ce_if_block * ce_info) 210890075Sobrien{ 2109117395Skan basic_block test_bb = ce_info->test_bb; /* last test block */ 2110117395Skan basic_block then_bb = ce_info->then_bb; /* THEN */ 2111117395Skan basic_block else_bb = ce_info->else_bb; /* ELSE or NULL */ 2112117395Skan basic_block join_bb = ce_info->join_bb; /* join block */ 211390075Sobrien basic_block combo_bb; 211490075Sobrien 211590075Sobrien /* All block merging is done into the lower block numbers. */ 211690075Sobrien 211790075Sobrien combo_bb = test_bb; 211890075Sobrien 2119117395Skan /* Merge any basic blocks to handle && and || subtests. Each of 2120117395Skan the blocks are on the fallthru path from the predecessor block. */ 2121117395Skan if (ce_info->num_multiple_test_blocks > 0) 2122117395Skan { 2123117395Skan basic_block bb = test_bb; 2124117395Skan basic_block last_test_bb = ce_info->last_test_bb; 2125117395Skan basic_block fallthru = block_fallthru (bb); 2126132718Skan 2127117395Skan do 2128117395Skan { 2129117395Skan bb = fallthru; 2130117395Skan fallthru = block_fallthru (bb); 2131132718Skan if (dom_computed[CDI_POST_DOMINATORS] >= DOM_NO_FAST_QUERY) 2132132718Skan delete_from_dominance_info (CDI_POST_DOMINATORS, bb); 2133132718Skan merge_blocks (combo_bb, bb); 2134132718Skan num_true_changes++; 2135117395Skan } 2136117395Skan while (bb != last_test_bb); 2137117395Skan } 2138117395Skan 2139117395Skan /* Merge TEST block into THEN block. Normally the THEN block won't have a 2140117395Skan label, but it might if there were || tests. That label's count should be 2141117395Skan zero, and it normally should be removed. */ 2142117395Skan 214396263Sobrien if (then_bb) 214496263Sobrien { 2145117395Skan if (combo_bb->global_live_at_end) 2146117395Skan COPY_REG_SET (combo_bb->global_live_at_end, 214796263Sobrien then_bb->global_live_at_end); 2148132718Skan if (dom_computed[CDI_POST_DOMINATORS] >= DOM_NO_FAST_QUERY) 2149132718Skan delete_from_dominance_info (CDI_POST_DOMINATORS, then_bb); 2150132718Skan merge_blocks (combo_bb, then_bb); 2151132718Skan num_true_changes++; 215296263Sobrien } 215390075Sobrien 215490075Sobrien /* The ELSE block, if it existed, had a label. That label count 215590075Sobrien will almost always be zero, but odd things can happen when labels 215690075Sobrien get their addresses taken. */ 215790075Sobrien if (else_bb) 215890075Sobrien { 2159132718Skan if (dom_computed[CDI_POST_DOMINATORS] >= DOM_NO_FAST_QUERY) 2160132718Skan delete_from_dominance_info (CDI_POST_DOMINATORS, else_bb); 2161132718Skan merge_blocks (combo_bb, else_bb); 2162132718Skan num_true_changes++; 216390075Sobrien } 216490075Sobrien 216590075Sobrien /* If there was no join block reported, that means it was not adjacent 216690075Sobrien to the others, and so we cannot merge them. */ 216790075Sobrien 216890075Sobrien if (! join_bb) 216990075Sobrien { 2170132718Skan rtx last = BB_END (combo_bb); 217196263Sobrien 217290075Sobrien /* The outgoing edge for the current COMBO block should already 217390075Sobrien be correct. Verify this. */ 217490075Sobrien if (combo_bb->succ == NULL_EDGE) 217596263Sobrien { 217696263Sobrien if (find_reg_note (last, REG_NORETURN, NULL)) 217796263Sobrien ; 217896263Sobrien else if (GET_CODE (last) == INSN 217996263Sobrien && GET_CODE (PATTERN (last)) == TRAP_IF 218096263Sobrien && TRAP_CONDITION (PATTERN (last)) == const_true_rtx) 218196263Sobrien ; 218296263Sobrien else 218396263Sobrien abort (); 218496263Sobrien } 218590075Sobrien 218696263Sobrien /* There should still be something at the end of the THEN or ELSE 218790075Sobrien blocks taking us to our final destination. */ 218896263Sobrien else if (GET_CODE (last) == JUMP_INSN) 218996263Sobrien ; 219096263Sobrien else if (combo_bb->succ->dest == EXIT_BLOCK_PTR 219196263Sobrien && GET_CODE (last) == CALL_INSN 219296263Sobrien && SIBLING_CALL_P (last)) 219396263Sobrien ; 219496263Sobrien else if ((combo_bb->succ->flags & EDGE_EH) 219596263Sobrien && can_throw_internal (last)) 219696263Sobrien ; 219796263Sobrien else 219890075Sobrien abort (); 219990075Sobrien } 220090075Sobrien 220190075Sobrien /* The JOIN block may have had quite a number of other predecessors too. 220290075Sobrien Since we've already merged the TEST, THEN and ELSE blocks, we should 220390075Sobrien have only one remaining edge from our if-then-else diamond. If there 220490075Sobrien is more than one remaining edge, it must come from elsewhere. There 2205132718Skan may be zero incoming edges if the THEN block didn't actually join 220690075Sobrien back up (as with a call to abort). */ 220790075Sobrien else if ((join_bb->pred == NULL 220890075Sobrien || join_bb->pred->pred_next == NULL) 220990075Sobrien && join_bb != EXIT_BLOCK_PTR) 221090075Sobrien { 221190075Sobrien /* We can merge the JOIN. */ 2212117395Skan if (combo_bb->global_live_at_end) 221390075Sobrien COPY_REG_SET (combo_bb->global_live_at_end, 221490075Sobrien join_bb->global_live_at_end); 2215117395Skan 2216132718Skan if (dom_computed[CDI_POST_DOMINATORS] >= DOM_NO_FAST_QUERY) 2217132718Skan delete_from_dominance_info (CDI_POST_DOMINATORS, join_bb); 2218132718Skan merge_blocks (combo_bb, join_bb); 2219132718Skan num_true_changes++; 222090075Sobrien } 222190075Sobrien else 222290075Sobrien { 222390075Sobrien /* We cannot merge the JOIN. */ 222490075Sobrien 222590075Sobrien /* The outgoing edge for the current COMBO block should already 222690075Sobrien be correct. Verify this. */ 222790075Sobrien if (combo_bb->succ->succ_next != NULL_EDGE 222890075Sobrien || combo_bb->succ->dest != join_bb) 222990075Sobrien abort (); 223090075Sobrien 223190075Sobrien /* Remove the jump and cruft from the end of the COMBO block. */ 223290075Sobrien if (join_bb != EXIT_BLOCK_PTR) 2233117395Skan tidy_fallthru_edge (combo_bb->succ, combo_bb, join_bb); 223490075Sobrien } 223590075Sobrien 223690075Sobrien num_updated_if_blocks++; 223790075Sobrien} 223890075Sobrien 2239117395Skan/* Find a block ending in a simple IF condition and try to transform it 2240117395Skan in some way. When converting a multi-block condition, put the new code 2241117395Skan in the first such block and delete the rest. Return a pointer to this 2242117395Skan first block if some transformation was done. Return NULL otherwise. */ 224390075Sobrien 2244117395Skanstatic basic_block 2245132718Skanfind_if_header (basic_block test_bb, int pass) 224690075Sobrien{ 2247117395Skan ce_if_block_t ce_info; 224890075Sobrien edge then_edge; 224990075Sobrien edge else_edge; 225090075Sobrien 225190075Sobrien /* The kind of block we're looking for has exactly two successors. */ 225290075Sobrien if ((then_edge = test_bb->succ) == NULL_EDGE 225390075Sobrien || (else_edge = then_edge->succ_next) == NULL_EDGE 225490075Sobrien || else_edge->succ_next != NULL_EDGE) 2255117395Skan return NULL; 225690075Sobrien 225790075Sobrien /* Neither edge should be abnormal. */ 225890075Sobrien if ((then_edge->flags & EDGE_COMPLEX) 225990075Sobrien || (else_edge->flags & EDGE_COMPLEX)) 2260117395Skan return NULL; 226190075Sobrien 2262132718Skan /* Nor exit the loop. */ 2263132718Skan if ((then_edge->flags & EDGE_LOOP_EXIT) 2264132718Skan || (else_edge->flags & EDGE_LOOP_EXIT)) 2265132718Skan return NULL; 2266132718Skan 226790075Sobrien /* The THEN edge is canonically the one that falls through. */ 226890075Sobrien if (then_edge->flags & EDGE_FALLTHRU) 226990075Sobrien ; 227090075Sobrien else if (else_edge->flags & EDGE_FALLTHRU) 227190075Sobrien { 227290075Sobrien edge e = else_edge; 227390075Sobrien else_edge = then_edge; 227490075Sobrien then_edge = e; 227590075Sobrien } 227690075Sobrien else 227790075Sobrien /* Otherwise this must be a multiway branch of some sort. */ 2278117395Skan return NULL; 227990075Sobrien 2280132718Skan memset (&ce_info, '\0', sizeof (ce_info)); 2281117395Skan ce_info.test_bb = test_bb; 2282117395Skan ce_info.then_bb = then_edge->dest; 2283117395Skan ce_info.else_bb = else_edge->dest; 2284117395Skan ce_info.pass = pass; 2285117395Skan 2286117395Skan#ifdef IFCVT_INIT_EXTRA_FIELDS 2287117395Skan IFCVT_INIT_EXTRA_FIELDS (&ce_info); 2288117395Skan#endif 2289117395Skan 2290117395Skan if (find_if_block (&ce_info)) 229190075Sobrien goto success; 2292117395Skan 229390075Sobrien if (HAVE_trap && HAVE_conditional_trap 229490075Sobrien && find_cond_trap (test_bb, then_edge, else_edge)) 229590075Sobrien goto success; 2296117395Skan 2297132718Skan if (dom_computed[CDI_POST_DOMINATORS] >= DOM_NO_FAST_QUERY 229890075Sobrien && (! HAVE_conditional_execution || reload_completed)) 229990075Sobrien { 230090075Sobrien if (find_if_case_1 (test_bb, then_edge, else_edge)) 230190075Sobrien goto success; 230290075Sobrien if (find_if_case_2 (test_bb, then_edge, else_edge)) 230390075Sobrien goto success; 230490075Sobrien } 230590075Sobrien 2306117395Skan return NULL; 230790075Sobrien 230890075Sobrien success: 230990075Sobrien if (rtl_dump_file) 2310117395Skan fprintf (rtl_dump_file, "Conversion succeeded on pass %d.\n", pass); 2311117395Skan return ce_info.test_bb; 231290075Sobrien} 231390075Sobrien 2314117395Skan/* Return true if a block has two edges, one of which falls through to the next 2315117395Skan block, and the other jumps to a specific block, so that we can tell if the 2316117395Skan block is part of an && test or an || test. Returns either -1 or the number 2317117395Skan of non-note, non-jump, non-USE/CLOBBER insns in the block. */ 2318117395Skan 2319117395Skanstatic int 2320132718Skanblock_jumps_and_fallthru_p (basic_block cur_bb, basic_block target_bb) 2321117395Skan{ 2322117395Skan edge cur_edge; 2323117395Skan int fallthru_p = FALSE; 2324117395Skan int jump_p = FALSE; 2325117395Skan rtx insn; 2326117395Skan rtx end; 2327117395Skan int n_insns = 0; 2328117395Skan 2329117395Skan if (!cur_bb || !target_bb) 2330117395Skan return -1; 2331117395Skan 2332117395Skan /* If no edges, obviously it doesn't jump or fallthru. */ 2333117395Skan if (cur_bb->succ == NULL_EDGE) 2334117395Skan return FALSE; 2335117395Skan 2336117395Skan for (cur_edge = cur_bb->succ; 2337117395Skan cur_edge != NULL_EDGE; 2338117395Skan cur_edge = cur_edge->succ_next) 2339117395Skan { 2340117395Skan if (cur_edge->flags & EDGE_COMPLEX) 2341117395Skan /* Anything complex isn't what we want. */ 2342117395Skan return -1; 2343117395Skan 2344117395Skan else if (cur_edge->flags & EDGE_FALLTHRU) 2345117395Skan fallthru_p = TRUE; 2346117395Skan 2347117395Skan else if (cur_edge->dest == target_bb) 2348117395Skan jump_p = TRUE; 2349117395Skan 2350117395Skan else 2351117395Skan return -1; 2352117395Skan } 2353117395Skan 2354117395Skan if ((jump_p & fallthru_p) == 0) 2355117395Skan return -1; 2356117395Skan 2357117395Skan /* Don't allow calls in the block, since this is used to group && and || 2358117395Skan together for conditional execution support. ??? we should support 2359117395Skan conditional execution support across calls for IA-64 some day, but 2360117395Skan for now it makes the code simpler. */ 2361132718Skan end = BB_END (cur_bb); 2362132718Skan insn = BB_HEAD (cur_bb); 2363117395Skan 2364117395Skan while (insn != NULL_RTX) 2365117395Skan { 2366117395Skan if (GET_CODE (insn) == CALL_INSN) 2367117395Skan return -1; 2368117395Skan 2369117395Skan if (INSN_P (insn) 2370117395Skan && GET_CODE (insn) != JUMP_INSN 2371117395Skan && GET_CODE (PATTERN (insn)) != USE 2372117395Skan && GET_CODE (PATTERN (insn)) != CLOBBER) 2373117395Skan n_insns++; 2374117395Skan 2375117395Skan if (insn == end) 2376117395Skan break; 2377117395Skan 2378117395Skan insn = NEXT_INSN (insn); 2379117395Skan } 2380117395Skan 2381117395Skan return n_insns; 2382117395Skan} 2383117395Skan 238490075Sobrien/* Determine if a given basic block heads a simple IF-THEN or IF-THEN-ELSE 238590075Sobrien block. If so, we'll try to convert the insns to not require the branch. 2386117395Skan Return TRUE if we were successful at converting the block. */ 238790075Sobrien 238890075Sobrienstatic int 2389132718Skanfind_if_block (struct ce_if_block * ce_info) 239090075Sobrien{ 2391117395Skan basic_block test_bb = ce_info->test_bb; 2392117395Skan basic_block then_bb = ce_info->then_bb; 2393117395Skan basic_block else_bb = ce_info->else_bb; 239490075Sobrien basic_block join_bb = NULL_BLOCK; 239590075Sobrien edge then_succ = then_bb->succ; 239690075Sobrien edge else_succ = else_bb->succ; 2397117395Skan int then_predecessors; 2398117395Skan int else_predecessors; 2399117395Skan edge cur_edge; 2400117395Skan basic_block next; 240190075Sobrien 2402117395Skan ce_info->last_test_bb = test_bb; 2403117395Skan 2404117395Skan /* Discover if any fall through predecessors of the current test basic block 2405117395Skan were && tests (which jump to the else block) or || tests (which jump to 2406117395Skan the then block). */ 2407117395Skan if (HAVE_conditional_execution && reload_completed 2408117395Skan && test_bb->pred != NULL_EDGE 2409117395Skan && test_bb->pred->pred_next == NULL_EDGE 2410117395Skan && test_bb->pred->flags == EDGE_FALLTHRU) 2411117395Skan { 2412117395Skan basic_block bb = test_bb->pred->src; 2413117395Skan basic_block target_bb; 2414117395Skan int max_insns = MAX_CONDITIONAL_EXECUTE; 2415117395Skan int n_insns; 2416117395Skan 2417132718Skan /* Determine if the preceding block is an && or || block. */ 2418117395Skan if ((n_insns = block_jumps_and_fallthru_p (bb, else_bb)) >= 0) 2419117395Skan { 2420117395Skan ce_info->and_and_p = TRUE; 2421117395Skan target_bb = else_bb; 2422117395Skan } 2423117395Skan else if ((n_insns = block_jumps_and_fallthru_p (bb, then_bb)) >= 0) 2424117395Skan { 2425132718Skan ce_info->and_and_p = FALSE; 2426117395Skan target_bb = then_bb; 2427117395Skan } 2428117395Skan else 2429117395Skan target_bb = NULL_BLOCK; 2430117395Skan 2431117395Skan if (target_bb && n_insns <= max_insns) 2432117395Skan { 2433117395Skan int total_insns = 0; 2434117395Skan int blocks = 0; 2435117395Skan 2436117395Skan ce_info->last_test_bb = test_bb; 2437117395Skan 2438117395Skan /* Found at least one && or || block, look for more. */ 2439117395Skan do 2440117395Skan { 2441117395Skan ce_info->test_bb = test_bb = bb; 2442117395Skan total_insns += n_insns; 2443117395Skan blocks++; 2444117395Skan 2445117395Skan if (bb->pred == NULL_EDGE || bb->pred->pred_next != NULL_EDGE) 2446117395Skan break; 2447117395Skan 2448117395Skan bb = bb->pred->src; 2449117395Skan n_insns = block_jumps_and_fallthru_p (bb, target_bb); 2450117395Skan } 2451117395Skan while (n_insns >= 0 && (total_insns + n_insns) <= max_insns); 2452117395Skan 2453117395Skan ce_info->num_multiple_test_blocks = blocks; 2454117395Skan ce_info->num_multiple_test_insns = total_insns; 2455117395Skan 2456117395Skan if (ce_info->and_and_p) 2457117395Skan ce_info->num_and_and_blocks = blocks; 2458117395Skan else 2459117395Skan ce_info->num_or_or_blocks = blocks; 2460117395Skan } 2461117395Skan } 2462117395Skan 2463117395Skan /* Count the number of edges the THEN and ELSE blocks have. */ 2464117395Skan then_predecessors = 0; 2465117395Skan for (cur_edge = then_bb->pred; 2466117395Skan cur_edge != NULL_EDGE; 2467117395Skan cur_edge = cur_edge->pred_next) 2468117395Skan { 2469117395Skan then_predecessors++; 2470117395Skan if (cur_edge->flags & EDGE_COMPLEX) 2471117395Skan return FALSE; 2472117395Skan } 2473117395Skan 2474117395Skan else_predecessors = 0; 2475117395Skan for (cur_edge = else_bb->pred; 2476117395Skan cur_edge != NULL_EDGE; 2477117395Skan cur_edge = cur_edge->pred_next) 2478117395Skan { 2479117395Skan else_predecessors++; 2480117395Skan if (cur_edge->flags & EDGE_COMPLEX) 2481117395Skan return FALSE; 2482117395Skan } 2483117395Skan 2484117395Skan /* The THEN block of an IF-THEN combo must have exactly one predecessor, 2485117395Skan other than any || blocks which jump to the THEN block. */ 2486117395Skan if ((then_predecessors - ce_info->num_or_or_blocks) != 1) 248790075Sobrien return FALSE; 248890075Sobrien 248990075Sobrien /* The THEN block of an IF-THEN combo must have zero or one successors. */ 249090075Sobrien if (then_succ != NULL_EDGE 249190075Sobrien && (then_succ->succ_next != NULL_EDGE 2492117395Skan || (then_succ->flags & EDGE_COMPLEX) 2493132718Skan || (flow2_completed && tablejump_p (BB_END (then_bb), NULL, NULL)))) 249490075Sobrien return FALSE; 249590075Sobrien 249690075Sobrien /* If the THEN block has no successors, conditional execution can still 249790075Sobrien make a conditional call. Don't do this unless the ELSE block has 249890075Sobrien only one incoming edge -- the CFG manipulation is too ugly otherwise. 249990075Sobrien Check for the last insn of the THEN block being an indirect jump, which 250090075Sobrien is listed as not having any successors, but confuses the rest of the CE 2501117395Skan code processing. ??? we should fix this in the future. */ 250290075Sobrien if (then_succ == NULL) 250390075Sobrien { 250490075Sobrien if (else_bb->pred->pred_next == NULL_EDGE) 250590075Sobrien { 2506132718Skan rtx last_insn = BB_END (then_bb); 250790075Sobrien 250890075Sobrien while (last_insn 250990075Sobrien && GET_CODE (last_insn) == NOTE 2510132718Skan && last_insn != BB_HEAD (then_bb)) 251190075Sobrien last_insn = PREV_INSN (last_insn); 251290075Sobrien 251390075Sobrien if (last_insn 251490075Sobrien && GET_CODE (last_insn) == JUMP_INSN 251590075Sobrien && ! simplejump_p (last_insn)) 251690075Sobrien return FALSE; 251790075Sobrien 251890075Sobrien join_bb = else_bb; 251990075Sobrien else_bb = NULL_BLOCK; 252090075Sobrien } 252190075Sobrien else 252290075Sobrien return FALSE; 252390075Sobrien } 252490075Sobrien 252590075Sobrien /* If the THEN block's successor is the other edge out of the TEST block, 252690075Sobrien then we have an IF-THEN combo without an ELSE. */ 252790075Sobrien else if (then_succ->dest == else_bb) 252890075Sobrien { 252990075Sobrien join_bb = else_bb; 253090075Sobrien else_bb = NULL_BLOCK; 253190075Sobrien } 253290075Sobrien 253390075Sobrien /* If the THEN and ELSE block meet in a subsequent block, and the ELSE 253490075Sobrien has exactly one predecessor and one successor, and the outgoing edge 253590075Sobrien is not complex, then we have an IF-THEN-ELSE combo. */ 253690075Sobrien else if (else_succ != NULL_EDGE 253790075Sobrien && then_succ->dest == else_succ->dest 253890075Sobrien && else_bb->pred->pred_next == NULL_EDGE 253990075Sobrien && else_succ->succ_next == NULL_EDGE 2540117395Skan && ! (else_succ->flags & EDGE_COMPLEX) 2541132718Skan && ! (flow2_completed && tablejump_p (BB_END (else_bb), NULL, NULL))) 254290075Sobrien join_bb = else_succ->dest; 254390075Sobrien 254490075Sobrien /* Otherwise it is not an IF-THEN or IF-THEN-ELSE combination. */ 254590075Sobrien else 2546132718Skan return FALSE; 254790075Sobrien 254890075Sobrien num_possible_if_blocks++; 254990075Sobrien 255090075Sobrien if (rtl_dump_file) 255190075Sobrien { 2552117395Skan fprintf (rtl_dump_file, "\nIF-THEN%s block found, pass %d, start block %d [insn %d], then %d [%d]", 2553117395Skan (else_bb) ? "-ELSE" : "", 2554117395Skan ce_info->pass, 2555132718Skan test_bb->index, (BB_HEAD (test_bb)) ? (int)INSN_UID (BB_HEAD (test_bb)) : -1, 2556132718Skan then_bb->index, (BB_HEAD (then_bb)) ? (int)INSN_UID (BB_HEAD (then_bb)) : -1); 2557117395Skan 255890075Sobrien if (else_bb) 2559117395Skan fprintf (rtl_dump_file, ", else %d [%d]", 2560132718Skan else_bb->index, (BB_HEAD (else_bb)) ? (int)INSN_UID (BB_HEAD (else_bb)) : -1); 2561117395Skan 2562117395Skan fprintf (rtl_dump_file, ", join %d [%d]", 2563132718Skan join_bb->index, (BB_HEAD (join_bb)) ? (int)INSN_UID (BB_HEAD (join_bb)) : -1); 2564117395Skan 2565117395Skan if (ce_info->num_multiple_test_blocks > 0) 2566117395Skan fprintf (rtl_dump_file, ", %d %s block%s last test %d [%d]", 2567117395Skan ce_info->num_multiple_test_blocks, 2568117395Skan (ce_info->and_and_p) ? "&&" : "||", 2569117395Skan (ce_info->num_multiple_test_blocks == 1) ? "" : "s", 2570117395Skan ce_info->last_test_bb->index, 2571132718Skan ((BB_HEAD (ce_info->last_test_bb)) 2572132718Skan ? (int)INSN_UID (BB_HEAD (ce_info->last_test_bb)) 2573117395Skan : -1)); 2574117395Skan 2575117395Skan fputc ('\n', rtl_dump_file); 257690075Sobrien } 257790075Sobrien 2578117395Skan /* Make sure IF, THEN, and ELSE, blocks are adjacent. Actually, we get the 2579117395Skan first condition for free, since we've already asserted that there's a 2580117395Skan fallthru edge from IF to THEN. Likewise for the && and || blocks, since 2581117395Skan we checked the FALLTHRU flag, those are already adjacent to the last IF 2582117395Skan block. */ 258390075Sobrien /* ??? As an enhancement, move the ELSE block. Have to deal with 258490075Sobrien BLOCK notes, if by no other means than aborting the merge if they 258590075Sobrien exist. Sticky enough I don't want to think about it now. */ 2586117395Skan next = then_bb; 2587117395Skan if (else_bb && (next = next->next_bb) != else_bb) 258890075Sobrien return FALSE; 2589117395Skan if ((next = next->next_bb) != join_bb && join_bb != EXIT_BLOCK_PTR) 259090075Sobrien { 259190075Sobrien if (else_bb) 259290075Sobrien join_bb = NULL; 259390075Sobrien else 259490075Sobrien return FALSE; 259590075Sobrien } 259690075Sobrien 259790075Sobrien /* Do the real work. */ 2598117395Skan ce_info->else_bb = else_bb; 2599117395Skan ce_info->join_bb = join_bb; 2600117395Skan 2601117395Skan return process_if_block (ce_info); 260290075Sobrien} 260390075Sobrien 2604117395Skan/* Convert a branch over a trap, or a branch 2605117395Skan to a trap, into a conditional trap. */ 260690075Sobrien 260790075Sobrienstatic int 2608132718Skanfind_cond_trap (basic_block test_bb, edge then_edge, edge else_edge) 260990075Sobrien{ 2610117395Skan basic_block then_bb = then_edge->dest; 2611117395Skan basic_block else_bb = else_edge->dest; 2612117395Skan basic_block other_bb, trap_bb; 261390075Sobrien rtx trap, jump, cond, cond_earliest, seq; 261490075Sobrien enum rtx_code code; 261590075Sobrien 261690075Sobrien /* Locate the block with the trap instruction. */ 261790075Sobrien /* ??? While we look for no successors, we really ought to allow 261890075Sobrien EH successors. Need to fix merge_if_block for that to work. */ 261996263Sobrien if ((trap = block_has_only_trap (then_bb)) != NULL) 262096263Sobrien trap_bb = then_bb, other_bb = else_bb; 262196263Sobrien else if ((trap = block_has_only_trap (else_bb)) != NULL) 262296263Sobrien trap_bb = else_bb, other_bb = then_bb; 262390075Sobrien else 262490075Sobrien return FALSE; 262590075Sobrien 262690075Sobrien if (rtl_dump_file) 262790075Sobrien { 262896263Sobrien fprintf (rtl_dump_file, "\nTRAP-IF block found, start %d, trap %d\n", 262996263Sobrien test_bb->index, trap_bb->index); 263090075Sobrien } 263190075Sobrien 263290075Sobrien /* If this is not a standard conditional jump, we can't parse it. */ 2633132718Skan jump = BB_END (test_bb); 263490075Sobrien cond = noce_get_condition (jump, &cond_earliest); 263590075Sobrien if (! cond) 263690075Sobrien return FALSE; 263790075Sobrien 2638117395Skan /* If the conditional jump is more than just a conditional jump, then 2639117395Skan we can not do if-conversion on this block. */ 264090075Sobrien if (! onlyjump_p (jump)) 264190075Sobrien return FALSE; 264290075Sobrien 264390075Sobrien /* We must be comparing objects whose modes imply the size. */ 264490075Sobrien if (GET_MODE (XEXP (cond, 0)) == BLKmode) 264590075Sobrien return FALSE; 264690075Sobrien 264790075Sobrien /* Reverse the comparison code, if necessary. */ 264890075Sobrien code = GET_CODE (cond); 264990075Sobrien if (then_bb == trap_bb) 265090075Sobrien { 265190075Sobrien code = reversed_comparison_code (cond, jump); 265290075Sobrien if (code == UNKNOWN) 265390075Sobrien return FALSE; 265490075Sobrien } 265590075Sobrien 265690075Sobrien /* Attempt to generate the conditional trap. */ 2657132718Skan seq = gen_cond_trap (code, XEXP (cond, 0), 2658132718Skan XEXP (cond, 1), 265990075Sobrien TRAP_CODE (PATTERN (trap))); 266090075Sobrien if (seq == NULL) 266190075Sobrien return FALSE; 266290075Sobrien 2663132718Skan num_true_changes++; 2664132718Skan 266596263Sobrien /* Emit the new insns before cond_earliest. */ 2666132718Skan emit_insn_before_setloc (seq, cond_earliest, INSN_LOCATOR (trap)); 266790075Sobrien 266896263Sobrien /* Delete the trap block if possible. */ 266996263Sobrien remove_edge (trap_bb == then_bb ? then_edge : else_edge); 267096263Sobrien if (trap_bb->pred == NULL) 267190075Sobrien { 2672132718Skan if (dom_computed[CDI_POST_DOMINATORS] >= DOM_NO_FAST_QUERY) 2673132718Skan delete_from_dominance_info (CDI_POST_DOMINATORS, trap_bb); 2674132718Skan delete_block (trap_bb); 267590075Sobrien } 267690075Sobrien 267796263Sobrien /* If the non-trap block and the test are now adjacent, merge them. 267896263Sobrien Otherwise we must insert a direct branch. */ 2679117395Skan if (test_bb->next_bb == other_bb) 268096263Sobrien { 2681117395Skan struct ce_if_block new_ce_info; 268296263Sobrien delete_insn (jump); 2683132718Skan memset (&new_ce_info, '\0', sizeof (new_ce_info)); 2684117395Skan new_ce_info.test_bb = test_bb; 2685117395Skan new_ce_info.then_bb = NULL; 2686117395Skan new_ce_info.else_bb = NULL; 2687117395Skan new_ce_info.join_bb = other_bb; 2688117395Skan merge_if_block (&new_ce_info); 268996263Sobrien } 269096263Sobrien else 269196263Sobrien { 269296263Sobrien rtx lab, newjump; 269396263Sobrien 269496263Sobrien lab = JUMP_LABEL (jump); 269596263Sobrien newjump = emit_jump_insn_after (gen_jump (lab), jump); 269696263Sobrien LABEL_NUSES (lab) += 1; 269796263Sobrien JUMP_LABEL (newjump) = lab; 269896263Sobrien emit_barrier_after (newjump); 269996263Sobrien 270096263Sobrien delete_insn (jump); 270196263Sobrien } 270296263Sobrien 270390075Sobrien return TRUE; 270490075Sobrien} 270590075Sobrien 2706132718Skan/* Subroutine of find_cond_trap: if BB contains only a trap insn, 270796263Sobrien return it. */ 270896263Sobrien 270996263Sobrienstatic rtx 2710132718Skanblock_has_only_trap (basic_block bb) 271196263Sobrien{ 271296263Sobrien rtx trap; 271396263Sobrien 271496263Sobrien /* We're not the exit block. */ 271596263Sobrien if (bb == EXIT_BLOCK_PTR) 271696263Sobrien return NULL_RTX; 271796263Sobrien 271896263Sobrien /* The block must have no successors. */ 271996263Sobrien if (bb->succ) 272096263Sobrien return NULL_RTX; 272196263Sobrien 272296263Sobrien /* The only instruction in the THEN block must be the trap. */ 272396263Sobrien trap = first_active_insn (bb); 2724132718Skan if (! (trap == BB_END (bb) 272596263Sobrien && GET_CODE (PATTERN (trap)) == TRAP_IF 272696263Sobrien && TRAP_CONDITION (PATTERN (trap)) == const_true_rtx)) 272796263Sobrien return NULL_RTX; 272896263Sobrien 272996263Sobrien return trap; 273096263Sobrien} 273196263Sobrien 273290075Sobrien/* Look for IF-THEN-ELSE cases in which one of THEN or ELSE is 273390075Sobrien transformable, but not necessarily the other. There need be no 273490075Sobrien JOIN block. 273590075Sobrien 2736117395Skan Return TRUE if we were successful at converting the block. 273790075Sobrien 273890075Sobrien Cases we'd like to look at: 273990075Sobrien 274090075Sobrien (1) 274190075Sobrien if (test) goto over; // x not live 274290075Sobrien x = a; 274390075Sobrien goto label; 274490075Sobrien over: 274590075Sobrien 274690075Sobrien becomes 274790075Sobrien 274890075Sobrien x = a; 274990075Sobrien if (! test) goto label; 275090075Sobrien 275190075Sobrien (2) 275290075Sobrien if (test) goto E; // x not live 275390075Sobrien x = big(); 275490075Sobrien goto L; 275590075Sobrien E: 275690075Sobrien x = b; 275790075Sobrien goto M; 275890075Sobrien 275990075Sobrien becomes 276090075Sobrien 276190075Sobrien x = b; 276290075Sobrien if (test) goto M; 276390075Sobrien x = big(); 276490075Sobrien goto L; 276590075Sobrien 276690075Sobrien (3) // This one's really only interesting for targets that can do 276790075Sobrien // multiway branching, e.g. IA-64 BBB bundles. For other targets 276890075Sobrien // it results in multiple branches on a cache line, which often 276990075Sobrien // does not sit well with predictors. 277090075Sobrien 277190075Sobrien if (test1) goto E; // predicted not taken 277290075Sobrien x = a; 277390075Sobrien if (test2) goto F; 277490075Sobrien ... 277590075Sobrien E: 277690075Sobrien x = b; 277790075Sobrien J: 277890075Sobrien 277990075Sobrien becomes 278090075Sobrien 278190075Sobrien x = a; 278290075Sobrien if (test1) goto E; 278390075Sobrien if (test2) goto F; 278490075Sobrien 278590075Sobrien Notes: 278690075Sobrien 278790075Sobrien (A) Don't do (2) if the branch is predicted against the block we're 278890075Sobrien eliminating. Do it anyway if we can eliminate a branch; this requires 278990075Sobrien that the sole successor of the eliminated block postdominate the other 279090075Sobrien side of the if. 279190075Sobrien 279290075Sobrien (B) With CE, on (3) we can steal from both sides of the if, creating 279390075Sobrien 279490075Sobrien if (test1) x = a; 279590075Sobrien if (!test1) x = b; 279690075Sobrien if (test1) goto J; 279790075Sobrien if (test2) goto F; 279890075Sobrien ... 279990075Sobrien J: 280090075Sobrien 280190075Sobrien Again, this is most useful if J postdominates. 280290075Sobrien 280390075Sobrien (C) CE substitutes for helpful life information. 280490075Sobrien 280590075Sobrien (D) These heuristics need a lot of work. */ 280690075Sobrien 280790075Sobrien/* Tests for case 1 above. */ 280890075Sobrien 280990075Sobrienstatic int 2810132718Skanfind_if_case_1 (basic_block test_bb, edge then_edge, edge else_edge) 281190075Sobrien{ 281290075Sobrien basic_block then_bb = then_edge->dest; 281390075Sobrien basic_block else_bb = else_edge->dest, new_bb; 281490075Sobrien edge then_succ = then_bb->succ; 2815117395Skan int then_bb_index; 281690075Sobrien 281790075Sobrien /* THEN has one successor. */ 281890075Sobrien if (!then_succ || then_succ->succ_next != NULL) 281990075Sobrien return FALSE; 282090075Sobrien 282190075Sobrien /* THEN does not fall through, but is not strange either. */ 282290075Sobrien if (then_succ->flags & (EDGE_COMPLEX | EDGE_FALLTHRU)) 282390075Sobrien return FALSE; 282490075Sobrien 282590075Sobrien /* THEN has one predecessor. */ 282690075Sobrien if (then_bb->pred->pred_next != NULL) 282790075Sobrien return FALSE; 282890075Sobrien 282990075Sobrien /* THEN must do something. */ 283090075Sobrien if (forwarder_block_p (then_bb)) 283190075Sobrien return FALSE; 283290075Sobrien 283390075Sobrien num_possible_if_blocks++; 283490075Sobrien if (rtl_dump_file) 283590075Sobrien fprintf (rtl_dump_file, 283690075Sobrien "\nIF-CASE-1 found, start %d, then %d\n", 283790075Sobrien test_bb->index, then_bb->index); 283890075Sobrien 283990075Sobrien /* THEN is small. */ 284090075Sobrien if (count_bb_insns (then_bb) > BRANCH_COST) 284190075Sobrien return FALSE; 284290075Sobrien 284390075Sobrien /* Registers set are dead, or are predicable. */ 2844132718Skan if (! dead_or_predicable (test_bb, then_bb, else_bb, 284590075Sobrien then_bb->succ->dest, 1)) 284690075Sobrien return FALSE; 284790075Sobrien 284890075Sobrien /* Conversion went ok, including moving the insns and fixing up the 284990075Sobrien jump. Adjust the CFG to match. */ 285090075Sobrien 285190075Sobrien bitmap_operation (test_bb->global_live_at_end, 285290075Sobrien else_bb->global_live_at_start, 285390075Sobrien then_bb->global_live_at_end, BITMAP_IOR); 2854132718Skan 285590075Sobrien new_bb = redirect_edge_and_branch_force (FALLTHRU_EDGE (test_bb), else_bb); 2856117395Skan then_bb_index = then_bb->index; 2857132718Skan if (dom_computed[CDI_POST_DOMINATORS] >= DOM_NO_FAST_QUERY) 2858132718Skan delete_from_dominance_info (CDI_POST_DOMINATORS, then_bb); 2859132718Skan delete_block (then_bb); 2860117395Skan 286190075Sobrien /* Make rest of code believe that the newly created block is the THEN_BB 2862117395Skan block we removed. */ 286390075Sobrien if (new_bb) 286490075Sobrien { 2865117395Skan new_bb->index = then_bb_index; 2866117395Skan BASIC_BLOCK (then_bb_index) = new_bb; 2867132718Skan if (dom_computed[CDI_POST_DOMINATORS] >= DOM_NO_FAST_QUERY) 2868132718Skan add_to_dominance_info (CDI_POST_DOMINATORS, new_bb); 286990075Sobrien } 287090075Sobrien /* We've possibly created jump to next insn, cleanup_cfg will solve that 287190075Sobrien later. */ 287290075Sobrien 2873132718Skan num_true_changes++; 287490075Sobrien num_updated_if_blocks++; 287590075Sobrien 287690075Sobrien return TRUE; 287790075Sobrien} 287890075Sobrien 287990075Sobrien/* Test for case 2 above. */ 288090075Sobrien 288190075Sobrienstatic int 2882132718Skanfind_if_case_2 (basic_block test_bb, edge then_edge, edge else_edge) 288390075Sobrien{ 288490075Sobrien basic_block then_bb = then_edge->dest; 288590075Sobrien basic_block else_bb = else_edge->dest; 288690075Sobrien edge else_succ = else_bb->succ; 288790075Sobrien rtx note; 288890075Sobrien 288990075Sobrien /* ELSE has one successor. */ 289090075Sobrien if (!else_succ || else_succ->succ_next != NULL) 289190075Sobrien return FALSE; 289290075Sobrien 289390075Sobrien /* ELSE outgoing edge is not complex. */ 289490075Sobrien if (else_succ->flags & EDGE_COMPLEX) 289590075Sobrien return FALSE; 289690075Sobrien 289790075Sobrien /* ELSE has one predecessor. */ 289890075Sobrien if (else_bb->pred->pred_next != NULL) 289990075Sobrien return FALSE; 290090075Sobrien 290190075Sobrien /* THEN is not EXIT. */ 290290075Sobrien if (then_bb->index < 0) 290390075Sobrien return FALSE; 290490075Sobrien 290590075Sobrien /* ELSE is predicted or SUCC(ELSE) postdominates THEN. */ 2906132718Skan note = find_reg_note (BB_END (test_bb), REG_BR_PROB, NULL_RTX); 290790075Sobrien if (note && INTVAL (XEXP (note, 0)) >= REG_BR_PROB_BASE / 2) 290890075Sobrien ; 290990075Sobrien else if (else_succ->dest->index < 0 2910132718Skan || dominated_by_p (CDI_POST_DOMINATORS, then_bb, 2911117395Skan else_succ->dest)) 291290075Sobrien ; 291390075Sobrien else 291490075Sobrien return FALSE; 291590075Sobrien 291690075Sobrien num_possible_if_blocks++; 291790075Sobrien if (rtl_dump_file) 291890075Sobrien fprintf (rtl_dump_file, 291990075Sobrien "\nIF-CASE-2 found, start %d, else %d\n", 292090075Sobrien test_bb->index, else_bb->index); 292190075Sobrien 292290075Sobrien /* ELSE is small. */ 2923117395Skan if (count_bb_insns (else_bb) > BRANCH_COST) 292490075Sobrien return FALSE; 292590075Sobrien 292690075Sobrien /* Registers set are dead, or are predicable. */ 292790075Sobrien if (! dead_or_predicable (test_bb, else_bb, then_bb, else_succ->dest, 0)) 292890075Sobrien return FALSE; 292990075Sobrien 293090075Sobrien /* Conversion went ok, including moving the insns and fixing up the 293190075Sobrien jump. Adjust the CFG to match. */ 293290075Sobrien 293390075Sobrien bitmap_operation (test_bb->global_live_at_end, 293490075Sobrien then_bb->global_live_at_start, 293590075Sobrien else_bb->global_live_at_end, BITMAP_IOR); 293690075Sobrien 2937132718Skan if (dom_computed[CDI_POST_DOMINATORS] >= DOM_NO_FAST_QUERY) 2938132718Skan delete_from_dominance_info (CDI_POST_DOMINATORS, else_bb); 2939132718Skan delete_block (else_bb); 2940132718Skan 2941132718Skan num_true_changes++; 294290075Sobrien num_updated_if_blocks++; 294390075Sobrien 294490075Sobrien /* ??? We may now fallthru from one of THEN's successors into a join 294590075Sobrien block. Rerun cleanup_cfg? Examine things manually? Wait? */ 294690075Sobrien 294790075Sobrien return TRUE; 294890075Sobrien} 294990075Sobrien 295090075Sobrien/* A subroutine of dead_or_predicable called through for_each_rtx. 295190075Sobrien Return 1 if a memory is found. */ 295290075Sobrien 295390075Sobrienstatic int 2954132718Skanfind_memory (rtx *px, void *data ATTRIBUTE_UNUSED) 295590075Sobrien{ 295690075Sobrien return GET_CODE (*px) == MEM; 295790075Sobrien} 295890075Sobrien 295990075Sobrien/* Used by the code above to perform the actual rtl transformations. 296090075Sobrien Return TRUE if successful. 296190075Sobrien 296290075Sobrien TEST_BB is the block containing the conditional branch. MERGE_BB 296390075Sobrien is the block containing the code to manipulate. NEW_DEST is the 296490075Sobrien label TEST_BB should be branching to after the conversion. 296590075Sobrien REVERSEP is true if the sense of the branch should be reversed. */ 296690075Sobrien 296790075Sobrienstatic int 2968132718Skandead_or_predicable (basic_block test_bb, basic_block merge_bb, 2969132718Skan basic_block other_bb, basic_block new_dest, int reversep) 297090075Sobrien{ 297196263Sobrien rtx head, end, jump, earliest, old_dest, new_label = NULL_RTX; 297290075Sobrien 2973132718Skan jump = BB_END (test_bb); 297490075Sobrien 297590075Sobrien /* Find the extent of the real code in the merge block. */ 2976132718Skan head = BB_HEAD (merge_bb); 2977132718Skan end = BB_END (merge_bb); 297890075Sobrien 297990075Sobrien if (GET_CODE (head) == CODE_LABEL) 298090075Sobrien head = NEXT_INSN (head); 298190075Sobrien if (GET_CODE (head) == NOTE) 298290075Sobrien { 298390075Sobrien if (head == end) 298490075Sobrien { 298590075Sobrien head = end = NULL_RTX; 298690075Sobrien goto no_body; 298790075Sobrien } 298890075Sobrien head = NEXT_INSN (head); 298990075Sobrien } 299090075Sobrien 299190075Sobrien if (GET_CODE (end) == JUMP_INSN) 299290075Sobrien { 299390075Sobrien if (head == end) 299490075Sobrien { 299590075Sobrien head = end = NULL_RTX; 299690075Sobrien goto no_body; 299790075Sobrien } 299890075Sobrien end = PREV_INSN (end); 299990075Sobrien } 300090075Sobrien 300190075Sobrien /* Disable handling dead code by conditional execution if the machine needs 300290075Sobrien to do anything funny with the tests, etc. */ 300390075Sobrien#ifndef IFCVT_MODIFY_TESTS 300490075Sobrien if (HAVE_conditional_execution) 300590075Sobrien { 300690075Sobrien /* In the conditional execution case, we have things easy. We know 3007132718Skan the condition is reversible. We don't have to check life info 3008132718Skan because we're going to conditionally execute the code anyway. 300990075Sobrien All that's left is making sure the insns involved can actually 301090075Sobrien be predicated. */ 301190075Sobrien 301290075Sobrien rtx cond, prob_val; 301390075Sobrien 301490075Sobrien cond = cond_exec_get_condition (jump); 301590075Sobrien if (! cond) 301690075Sobrien return FALSE; 301790075Sobrien 301890075Sobrien prob_val = find_reg_note (jump, REG_BR_PROB, NULL_RTX); 301990075Sobrien if (prob_val) 302090075Sobrien prob_val = XEXP (prob_val, 0); 302190075Sobrien 302290075Sobrien if (reversep) 302390075Sobrien { 302490075Sobrien enum rtx_code rev = reversed_comparison_code (cond, jump); 302590075Sobrien if (rev == UNKNOWN) 302690075Sobrien return FALSE; 302790075Sobrien cond = gen_rtx_fmt_ee (rev, GET_MODE (cond), XEXP (cond, 0), 302890075Sobrien XEXP (cond, 1)); 302990075Sobrien if (prob_val) 303090075Sobrien prob_val = GEN_INT (REG_BR_PROB_BASE - INTVAL (prob_val)); 303190075Sobrien } 303290075Sobrien 3033117395Skan if (! cond_exec_process_insns ((ce_if_block_t *)0, head, end, cond, 3034117395Skan prob_val, 0)) 303590075Sobrien goto cancel; 303690075Sobrien 303790075Sobrien earliest = jump; 303890075Sobrien } 303990075Sobrien else 304090075Sobrien#endif 304190075Sobrien { 304290075Sobrien /* In the non-conditional execution case, we have to verify that there 304390075Sobrien are no trapping operations, no calls, no references to memory, and 304490075Sobrien that any registers modified are dead at the branch site. */ 304590075Sobrien 304690075Sobrien rtx insn, cond, prev; 304790075Sobrien regset_head merge_set_head, tmp_head, test_live_head, test_set_head; 304890075Sobrien regset merge_set, tmp, test_live, test_set; 304990075Sobrien struct propagate_block_info *pbi; 305090075Sobrien int i, fail = 0; 305190075Sobrien 305290075Sobrien /* Check for no calls or trapping operations. */ 305390075Sobrien for (insn = head; ; insn = NEXT_INSN (insn)) 305490075Sobrien { 305590075Sobrien if (GET_CODE (insn) == CALL_INSN) 305690075Sobrien return FALSE; 305790075Sobrien if (INSN_P (insn)) 305890075Sobrien { 305990075Sobrien if (may_trap_p (PATTERN (insn))) 306090075Sobrien return FALSE; 306190075Sobrien 306290075Sobrien /* ??? Even non-trapping memories such as stack frame 306390075Sobrien references must be avoided. For stores, we collect 306490075Sobrien no lifetime info; for reads, we'd have to assert 306590075Sobrien true_dependence false against every store in the 306690075Sobrien TEST range. */ 306790075Sobrien if (for_each_rtx (&PATTERN (insn), find_memory, NULL)) 306890075Sobrien return FALSE; 306990075Sobrien } 307090075Sobrien if (insn == end) 307190075Sobrien break; 307290075Sobrien } 307390075Sobrien 307490075Sobrien if (! any_condjump_p (jump)) 307590075Sobrien return FALSE; 307690075Sobrien 307790075Sobrien /* Find the extent of the conditional. */ 307890075Sobrien cond = noce_get_condition (jump, &earliest); 307990075Sobrien if (! cond) 308090075Sobrien return FALSE; 308190075Sobrien 308290075Sobrien /* Collect: 308390075Sobrien MERGE_SET = set of registers set in MERGE_BB 308490075Sobrien TEST_LIVE = set of registers live at EARLIEST 308590075Sobrien TEST_SET = set of registers set between EARLIEST and the 308690075Sobrien end of the block. */ 308790075Sobrien 308890075Sobrien tmp = INITIALIZE_REG_SET (tmp_head); 308990075Sobrien merge_set = INITIALIZE_REG_SET (merge_set_head); 309090075Sobrien test_live = INITIALIZE_REG_SET (test_live_head); 309190075Sobrien test_set = INITIALIZE_REG_SET (test_set_head); 309290075Sobrien 309390075Sobrien /* ??? bb->local_set is only valid during calculate_global_regs_live, 3094132718Skan so we must recompute usage for MERGE_BB. Not so bad, I suppose, 309590075Sobrien since we've already asserted that MERGE_BB is small. */ 309690075Sobrien propagate_block (merge_bb, tmp, merge_set, merge_set, 0); 309790075Sobrien 309890075Sobrien /* For small register class machines, don't lengthen lifetimes of 309990075Sobrien hard registers before reload. */ 310090075Sobrien if (SMALL_REGISTER_CLASSES && ! reload_completed) 310190075Sobrien { 310290075Sobrien EXECUTE_IF_SET_IN_BITMAP 310390075Sobrien (merge_set, 0, i, 310490075Sobrien { 310590075Sobrien if (i < FIRST_PSEUDO_REGISTER 310690075Sobrien && ! fixed_regs[i] 310790075Sobrien && ! global_regs[i]) 310890075Sobrien fail = 1; 310990075Sobrien }); 311090075Sobrien } 311190075Sobrien 311290075Sobrien /* For TEST, we're interested in a range of insns, not a whole block. 311390075Sobrien Moreover, we're interested in the insns live from OTHER_BB. */ 311490075Sobrien 311590075Sobrien COPY_REG_SET (test_live, other_bb->global_live_at_start); 311690075Sobrien pbi = init_propagate_block_info (test_bb, test_live, test_set, test_set, 311790075Sobrien 0); 311890075Sobrien 311990075Sobrien for (insn = jump; ; insn = prev) 312090075Sobrien { 312190075Sobrien prev = propagate_one_insn (pbi, insn); 312290075Sobrien if (insn == earliest) 312390075Sobrien break; 312490075Sobrien } 312590075Sobrien 312690075Sobrien free_propagate_block_info (pbi); 312790075Sobrien 312890075Sobrien /* We can perform the transformation if 312990075Sobrien MERGE_SET & (TEST_SET | TEST_LIVE) 313090075Sobrien and 313190075Sobrien TEST_SET & merge_bb->global_live_at_start 313290075Sobrien are empty. */ 313390075Sobrien 313490075Sobrien bitmap_operation (tmp, test_set, test_live, BITMAP_IOR); 313590075Sobrien bitmap_operation (tmp, tmp, merge_set, BITMAP_AND); 313690075Sobrien EXECUTE_IF_SET_IN_BITMAP(tmp, 0, i, fail = 1); 313790075Sobrien 313890075Sobrien bitmap_operation (tmp, test_set, merge_bb->global_live_at_start, 313990075Sobrien BITMAP_AND); 314090075Sobrien EXECUTE_IF_SET_IN_BITMAP(tmp, 0, i, fail = 1); 314190075Sobrien 314290075Sobrien FREE_REG_SET (tmp); 314390075Sobrien FREE_REG_SET (merge_set); 314490075Sobrien FREE_REG_SET (test_live); 314590075Sobrien FREE_REG_SET (test_set); 314690075Sobrien 314790075Sobrien if (fail) 314890075Sobrien return FALSE; 314990075Sobrien } 315090075Sobrien 315190075Sobrien no_body: 315290075Sobrien /* We don't want to use normal invert_jump or redirect_jump because 315390075Sobrien we don't want to delete_insn called. Also, we want to do our own 315490075Sobrien change group management. */ 315590075Sobrien 315690075Sobrien old_dest = JUMP_LABEL (jump); 315790075Sobrien if (other_bb != new_dest) 315890075Sobrien { 315990075Sobrien new_label = block_label (new_dest); 316090075Sobrien if (reversep 316190075Sobrien ? ! invert_jump_1 (jump, new_label) 316290075Sobrien : ! redirect_jump_1 (jump, new_label)) 316390075Sobrien goto cancel; 316490075Sobrien } 316590075Sobrien 316690075Sobrien if (! apply_change_group ()) 316790075Sobrien return FALSE; 316890075Sobrien 316990075Sobrien if (other_bb != new_dest) 317090075Sobrien { 317190075Sobrien if (old_dest) 317290075Sobrien LABEL_NUSES (old_dest) -= 1; 317390075Sobrien if (new_label) 317490075Sobrien LABEL_NUSES (new_label) += 1; 317590075Sobrien JUMP_LABEL (jump) = new_label; 317690075Sobrien if (reversep) 317790075Sobrien invert_br_probabilities (jump); 317890075Sobrien 317990075Sobrien redirect_edge_succ (BRANCH_EDGE (test_bb), new_dest); 318090075Sobrien if (reversep) 318190075Sobrien { 318290075Sobrien gcov_type count, probability; 318390075Sobrien count = BRANCH_EDGE (test_bb)->count; 318490075Sobrien BRANCH_EDGE (test_bb)->count = FALLTHRU_EDGE (test_bb)->count; 318590075Sobrien FALLTHRU_EDGE (test_bb)->count = count; 318690075Sobrien probability = BRANCH_EDGE (test_bb)->probability; 318790075Sobrien BRANCH_EDGE (test_bb)->probability 318890075Sobrien = FALLTHRU_EDGE (test_bb)->probability; 318990075Sobrien FALLTHRU_EDGE (test_bb)->probability = probability; 319090075Sobrien update_br_prob_note (test_bb); 319190075Sobrien } 319290075Sobrien } 319390075Sobrien 319490075Sobrien /* Move the insns out of MERGE_BB to before the branch. */ 319590075Sobrien if (head != NULL) 319690075Sobrien { 3197132718Skan if (end == BB_END (merge_bb)) 3198132718Skan BB_END (merge_bb) = PREV_INSN (head); 319990075Sobrien 320090075Sobrien if (squeeze_notes (&head, &end)) 320190075Sobrien return TRUE; 320290075Sobrien 320390075Sobrien reorder_insns (head, end, PREV_INSN (earliest)); 320490075Sobrien } 320590075Sobrien 320690075Sobrien /* Remove the jump and edge if we can. */ 320790075Sobrien if (other_bb == new_dest) 320890075Sobrien { 320990075Sobrien delete_insn (jump); 321090075Sobrien remove_edge (BRANCH_EDGE (test_bb)); 321190075Sobrien /* ??? Can't merge blocks here, as then_bb is still in use. 321290075Sobrien At minimum, the merge will get done just before bb-reorder. */ 321390075Sobrien } 321490075Sobrien 321590075Sobrien return TRUE; 321690075Sobrien 321790075Sobrien cancel: 321890075Sobrien cancel_changes (0); 321990075Sobrien return FALSE; 322090075Sobrien} 322190075Sobrien 322290075Sobrien/* Main entry point for all if-conversion. */ 322390075Sobrien 322490075Sobrienvoid 3225132718Skanif_convert (int x_life_data_ok) 322690075Sobrien{ 3227117395Skan basic_block bb; 3228117395Skan int pass; 322990075Sobrien 323090075Sobrien num_possible_if_blocks = 0; 323190075Sobrien num_updated_if_blocks = 0; 3232132718Skan num_true_changes = 0; 323390075Sobrien life_data_ok = (x_life_data_ok != 0); 323490075Sobrien 3235132718Skan if (! (* targetm.cannot_modify_jumps_p) ()) 3236132718Skan mark_loop_exit_edges (); 3237132718Skan 3238117395Skan /* Free up basic_block_for_insn so that we don't have to keep it 3239132718Skan up to date, either here or in merge_blocks. */ 324090075Sobrien free_basic_block_vars (1); 324190075Sobrien 324290075Sobrien /* Compute postdominators if we think we'll use them. */ 324390075Sobrien if (HAVE_conditional_execution || life_data_ok) 3244132718Skan calculate_dominance_info (CDI_POST_DOMINATORS); 3245132718Skan 3246117395Skan if (life_data_ok) 3247117395Skan clear_bb_flags (); 324890075Sobrien 3249117395Skan /* Go through each of the basic blocks looking for things to convert. If we 3250117395Skan have conditional execution, we make multiple passes to allow us to handle 3251117395Skan IF-THEN{-ELSE} blocks within other IF-THEN{-ELSE} blocks. */ 3252117395Skan pass = 0; 3253117395Skan do 3254117395Skan { 3255117395Skan cond_exec_changed_p = FALSE; 3256117395Skan pass++; 325790075Sobrien 3258117395Skan#ifdef IFCVT_MULTIPLE_DUMPS 3259117395Skan if (rtl_dump_file && pass > 1) 3260117395Skan fprintf (rtl_dump_file, "\n\n========== Pass %d ==========\n", pass); 3261117395Skan#endif 3262117395Skan 3263117395Skan FOR_EACH_BB (bb) 3264117395Skan { 3265117395Skan basic_block new_bb; 3266117395Skan while ((new_bb = find_if_header (bb, pass))) 3267117395Skan bb = new_bb; 3268117395Skan } 3269117395Skan 3270117395Skan#ifdef IFCVT_MULTIPLE_DUMPS 3271117395Skan if (rtl_dump_file && cond_exec_changed_p) 3272117395Skan print_rtl_with_bb (rtl_dump_file, get_insns ()); 3273117395Skan#endif 327490075Sobrien } 3275117395Skan while (cond_exec_changed_p); 327690075Sobrien 3277117395Skan#ifdef IFCVT_MULTIPLE_DUMPS 3278117395Skan if (rtl_dump_file) 3279117395Skan fprintf (rtl_dump_file, "\n\n========== no more changes\n"); 3280117395Skan#endif 3281117395Skan 3282132718Skan free_dominance_info (CDI_POST_DOMINATORS); 328390075Sobrien 328490075Sobrien if (rtl_dump_file) 328590075Sobrien fflush (rtl_dump_file); 328690075Sobrien 3287117395Skan clear_aux_for_blocks (); 3288117395Skan 328990075Sobrien /* Rebuild life info for basic blocks that require it. */ 3290132718Skan if (num_true_changes && life_data_ok) 329190075Sobrien { 329290075Sobrien /* If we allocated new pseudos, we must resize the array for sched1. */ 329390075Sobrien if (max_regno < max_reg_num ()) 329490075Sobrien { 329590075Sobrien max_regno = max_reg_num (); 329690075Sobrien allocate_reg_info (max_regno, FALSE, FALSE); 329790075Sobrien } 3298117395Skan update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES, 3299117395Skan PROP_DEATH_NOTES | PROP_SCAN_DEAD_CODE 3300117395Skan | PROP_KILL_DEAD_CODE); 330190075Sobrien } 330290075Sobrien 330390075Sobrien /* Write the final stats. */ 330490075Sobrien if (rtl_dump_file && num_possible_if_blocks > 0) 330590075Sobrien { 330690075Sobrien fprintf (rtl_dump_file, 330790075Sobrien "\n%d possible IF blocks searched.\n", 330890075Sobrien num_possible_if_blocks); 330990075Sobrien fprintf (rtl_dump_file, 331090075Sobrien "%d IF blocks converted.\n", 331190075Sobrien num_updated_if_blocks); 331290075Sobrien fprintf (rtl_dump_file, 3313132718Skan "%d true changes made.\n\n\n", 3314132718Skan num_true_changes); 331590075Sobrien } 331690075Sobrien 331790075Sobrien#ifdef ENABLE_CHECKING 331890075Sobrien verify_flow_info (); 331990075Sobrien#endif 332090075Sobrien} 3321