1	/* If-conversion support.
2	Copyright (C) 2000-2024 Free Software Foundation, Inc.
3
4	This file is part of GCC.
5
6	GCC is free software; you can redistribute it and/or modify it
7	under the terms of the GNU General Public License as published by
8	the Free Software Foundation; either version 3, or (at your option)
9	any later version.
10
11	GCC is distributed in the hope that it will be useful, but WITHOUT
12	ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13	or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
14	License for more details.
15
16	You should have received a copy of the GNU General Public License
17	along with GCC; see the file COPYING3. If not see
18	<http://www.gnu.org/licenses/>. */
19
20	#include "config.h"
21	#include "system.h"
22	#include "coretypes.h"
23	#include "backend.h"
24	#include "target.h"
25	#include "rtl.h"
26	#include "tree.h"
27	#include "cfghooks.h"
28	#include "df.h"
29	#include "memmodel.h"
30	#include "tm_p.h"
31	#include "expmed.h"
32	#include "optabs.h"
33	#include "regs.h"
34	#include "emit-rtl.h"
35	#include "recog.h"
36
37	#include "cfgrtl.h"
38	#include "cfganal.h"
39	#include "cfgcleanup.h"
40	#include "expr.h"
41	#include "output.h"
42	#include "cfgloop.h"
43	#include "tree-pass.h"
44	#include "dbgcnt.h"
45	#include "shrink-wrap.h"
46	#include "rtl-iter.h"
47	#include "ifcvt.h"
48
49	#ifndef MAX_CONDITIONAL_EXECUTE
50	#define MAX_CONDITIONAL_EXECUTE \
51	(BRANCH_COST (optimize_function_for_speed_p (cfun), false) \
52	+ 1)
53	#endif
54
55	#define IFCVT_MULTIPLE_DUMPS 1
56
57	#define NULL_BLOCK ((basic_block) NULL)
58
59	/* True if after combine pass. */
60	static bool ifcvt_after_combine;
61
62	/* True if the target has the cbranchcc4 optab. */
63	static bool have_cbranchcc4;
64
65	/* # of IF-THEN or IF-THEN-ELSE blocks we looked at */
66	static int num_possible_if_blocks;
67
68	/* # of IF-THEN or IF-THEN-ELSE blocks were converted to conditional
69	execution. */
70	static int num_updated_if_blocks;
71
72	/* # of changes made. */
73	static int num_true_changes;
74
75	/* Whether conditional execution changes were made. */
76	static bool cond_exec_changed_p;
77
78	/* Forward references. */
79	static int count_bb_insns (const_basic_block);
80	static bool cheap_bb_rtx_cost_p (const_basic_block, profile_probability, int);
81	static rtx_insn *first_active_insn (basic_block);
82	static rtx_insn *last_active_insn (basic_block, bool);
83	static rtx_insn *find_active_insn_before (basic_block, rtx_insn *);
84	static rtx_insn *find_active_insn_after (basic_block, rtx_insn *);
85	static basic_block block_fallthru (basic_block);
86	static rtx cond_exec_get_condition (rtx_insn *, bool);
87	static rtx noce_get_condition (rtx_insn *, rtx_insn **, bool);
88	static bool noce_operand_ok (const_rtx);
89	static void merge_if_block (ce_if_block *);
90	static bool find_cond_trap (basic_block, edge, edge);
91	static basic_block find_if_header (basic_block, int);
92	static int block_jumps_and_fallthru (basic_block, basic_block);
93	static bool noce_find_if_block (basic_block, edge, edge, int);
94	static bool cond_exec_find_if_block (ce_if_block *);
95	static bool find_if_case_1 (basic_block, edge, edge);
96	static bool find_if_case_2 (basic_block, edge, edge);
97	static bool dead_or_predicable (basic_block, basic_block, basic_block,
98	edge, bool);
99	static void noce_emit_move_insn (rtx, rtx);
100	static rtx_insn *block_has_only_trap (basic_block);
101	static void need_cmov_or_rewire (basic_block, hash_set<rtx_insn *> *,
102	hash_map<rtx_insn *, int> *);
103	static bool noce_convert_multiple_sets_1 (struct noce_if_info *,
104	hash_set<rtx_insn *> *,
105	hash_map<rtx_insn *, int> *,
106	auto_vec<rtx> *,
107	auto_vec<rtx> *,
108	auto_vec<rtx_insn *> *, int *);
109
110	/* Count the number of non-jump active insns in BB. */
111
112	static int
113	count_bb_insns (const_basic_block bb)
114	{
115	int count = 0;
116	rtx_insn *insn = BB_HEAD (bb);
117
118	while (1)
119	{
120	if (active_insn_p (insn) && !JUMP_P (insn))
121	count++;
122
123	if (insn == BB_END (bb))
124	break;
125	insn = NEXT_INSN (insn);
126	}
127
128	return count;
129	}
130
131	/* Determine whether the total insn_cost on non-jump insns in
132	basic block BB is less than MAX_COST. This function returns
133	false if the cost of any instruction could not be estimated.
134
135	The cost of the non-jump insns in BB is scaled by REG_BR_PROB_BASE
136	as those insns are being speculated. MAX_COST is scaled with SCALE
137	plus a small fudge factor. */
138
139	static bool
140	cheap_bb_rtx_cost_p (const_basic_block bb,
141	profile_probability prob, int max_cost)
142	{
143	int count = 0;
144	rtx_insn *insn = BB_HEAD (bb);
145	bool speed = optimize_bb_for_speed_p (bb);
146	int scale = prob.initialized_p () ? prob.to_reg_br_prob_base ()
147	: REG_BR_PROB_BASE;
148
149	/* Set scale to REG_BR_PROB_BASE to void the identical scaling
150	applied to insn_cost when optimizing for size. Only do
151	this after combine because if-conversion might interfere with
152	passes before combine.
153
154	Use optimize_function_for_speed_p instead of the pre-defined
155	variable speed to make sure it is set to same value for all
156	basic blocks in one if-conversion transformation. */
157	if (!optimize_function_for_speed_p (cfun) && ifcvt_after_combine)
158	scale = REG_BR_PROB_BASE;
159	/* Our branch probability/scaling factors are just estimates and don't
160	account for cases where we can get speculation for free and other
161	secondary benefits. So we fudge the scale factor to make speculating
162	appear a little more profitable when optimizing for performance. */
163	else
164	scale += REG_BR_PROB_BASE / 8;
165
166
167	max_cost *= scale;
168
169	while (1)
170	{
171	if (NONJUMP_INSN_P (insn))
172	{
173	int cost = insn_cost (insn, speed) * REG_BR_PROB_BASE;
174	if (cost == 0)
175	return false;
176
177	/* If this instruction is the load or set of a "stack" register,
178	such as a floating point register on x87, then the cost of
179	speculatively executing this insn may need to include
180	the additional cost of popping its result off of the
181	register stack. Unfortunately, correctly recognizing and
182	accounting for this additional overhead is tricky, so for
183	now we simply prohibit such speculative execution. */
184	#ifdef STACK_REGS
185	{
186	rtx set = single_set (insn);
187	if (set && STACK_REG_P (SET_DEST (set)))
188	return false;
189	}
190	#endif
191
192	count += cost;
193	if (count >= max_cost)
194	return false;
195	}
196	else if (CALL_P (insn))
197	return false;
198
199	if (insn == BB_END (bb))
200	break;
201	insn = NEXT_INSN (insn);
202	}
203
204	return true;
205	}
206
207	/* Return the first non-jump active insn in the basic block. */
208
209	static rtx_insn *
210	first_active_insn (basic_block bb)
211	{
212	rtx_insn *insn = BB_HEAD (bb);
213
214	if (LABEL_P (insn))
215	{
216	if (insn == BB_END (bb))
217	return NULL;
218	insn = NEXT_INSN (insn);
219	}
220
221	while (NOTE_P (insn) || DEBUG_INSN_P (insn))
222	{
223	if (insn == BB_END (bb))
224	return NULL;
225	insn = NEXT_INSN (insn);
226	}
227
228	if (JUMP_P (insn))
229	return NULL;
230
231	return insn;
232	}
233
234	/* Return the last non-jump active (non-jump) insn in the basic block. */
235
236	static rtx_insn *
237	last_active_insn (basic_block bb, bool skip_use_p)
238	{
239	rtx_insn *insn = BB_END (bb);
240	rtx_insn *head = BB_HEAD (bb);
241
242	while (NOTE_P (insn)
243	|| JUMP_P (insn)
244	|| DEBUG_INSN_P (insn)
245	|| (skip_use_p
246	&& NONJUMP_INSN_P (insn)
247	&& GET_CODE (PATTERN (insn)) == USE))
248	{
249	if (insn == head)
250	return NULL;
251	insn = PREV_INSN (insn);
252	}
253
254	if (LABEL_P (insn))
255	return NULL;
256
257	return insn;
258	}
259
260	/* Return the active insn before INSN inside basic block CURR_BB. */
261
262	static rtx_insn *
263	find_active_insn_before (basic_block curr_bb, rtx_insn *insn)
264	{
265	if (!insn || insn == BB_HEAD (curr_bb))
266	return NULL;
267
268	while ((insn = PREV_INSN (insn)) != NULL_RTX)
269	{
270	if (NONJUMP_INSN_P (insn) || JUMP_P (insn) || CALL_P (insn))
271	break;
272
273	/* No other active insn all the way to the start of the basic block. */
274	if (insn == BB_HEAD (curr_bb))
275	return NULL;
276	}
277
278	return insn;
279	}
280
281	/* Return the active insn after INSN inside basic block CURR_BB. */
282
283	static rtx_insn *
284	find_active_insn_after (basic_block curr_bb, rtx_insn *insn)
285	{
286	if (!insn || insn == BB_END (curr_bb))
287	return NULL;
288
289	while ((insn = NEXT_INSN (insn)) != NULL_RTX)
290	{
291	if (NONJUMP_INSN_P (insn) || JUMP_P (insn) || CALL_P (insn))
292	break;
293
294	/* No other active insn all the way to the end of the basic block. */
295	if (insn == BB_END (curr_bb))
296	return NULL;
297	}
298
299	return insn;
300	}
301
302	/* Return the basic block reached by falling though the basic block BB. */
303
304	static basic_block
305	block_fallthru (basic_block bb)
306	{
307	edge e = find_fallthru_edge (edges: bb->succs);
308
309	return (e) ? e->dest : NULL_BLOCK;
310	}
311
312	/* Return true if RTXs A and B can be safely interchanged. */
313
314	static bool
315	rtx_interchangeable_p (const_rtx a, const_rtx b)
316	{
317	if (!rtx_equal_p (a, b))
318	return false;
319
320	if (GET_CODE (a) != MEM)
321	return true;
322
323	/* A dead type-unsafe memory reference is legal, but a live type-unsafe memory
324	reference is not. Interchanging a dead type-unsafe memory reference with
325	a live type-safe one creates a live type-unsafe memory reference, in other
326	words, it makes the program illegal.
327	We check here conservatively whether the two memory references have equal
328	memory attributes. */
329
330	return mem_attrs_eq_p (get_mem_attrs (x: a), get_mem_attrs (x: b));
331	}
332
333
334	/* Go through a bunch of insns, converting them to conditional
335	execution format if possible. Return TRUE if all of the non-note
336	insns were processed. */
337
338	static bool
339	cond_exec_process_insns (ce_if_block *ce_info ATTRIBUTE_UNUSED,
340	/* if block information */rtx_insn *start,
341	/* first insn to look at */rtx end,
342	/* last insn to look at */rtx test,
343	/* conditional execution test */profile_probability
344	prob_val,
345	/* probability of branch taken. */bool mod_ok)
346	{
347	bool must_be_last = false;
348	rtx_insn *insn;
349	rtx xtest;
350	rtx pattern;
351
352	if (!start || !end)
353	return false;
354
355	for (insn = start; ; insn = NEXT_INSN (insn))
356	{
357	/* dwarf2out can't cope with conditional prologues. */
358	if (NOTE_P (insn) && NOTE_KIND (insn) == NOTE_INSN_PROLOGUE_END)
359	return false;
360
361	if (NOTE_P (insn) || DEBUG_INSN_P (insn))
362	goto insn_done;
363
364	gcc_assert (NONJUMP_INSN_P (insn) || CALL_P (insn));
365
366	/* dwarf2out can't cope with conditional unwind info. */
367	if (RTX_FRAME_RELATED_P (insn))
368	return false;
369
370	/* Remove USE insns that get in the way. */
371	if (reload_completed && GET_CODE (PATTERN (insn)) == USE)
372	{
373	/* ??? Ug. Actually unlinking the thing is problematic,
374	given what we'd have to coordinate with our callers. */
375	SET_INSN_DELETED (insn);
376	goto insn_done;
377	}
378
379	/* Last insn wasn't last? */
380	if (must_be_last)
381	return false;
382
383	if (modified_in_p (test, insn))
384	{
385	if (!mod_ok)
386	return false;
387	must_be_last = true;
388	}
389
390	/* Now build the conditional form of the instruction. */
391	pattern = PATTERN (insn);
392	xtest = copy_rtx (test);
393
394	/* If this is already a COND_EXEC, rewrite the test to be an AND of the
395	two conditions. */
396	if (GET_CODE (pattern) == COND_EXEC)
397	{
398	if (GET_MODE (xtest) != GET_MODE (COND_EXEC_TEST (pattern)))
399	return false;
400
401	xtest = gen_rtx_AND (GET_MODE (xtest), xtest,
402	COND_EXEC_TEST (pattern));
403	pattern = COND_EXEC_CODE (pattern);
404	}
405
406	pattern = gen_rtx_COND_EXEC (VOIDmode, xtest, pattern);
407
408	/* If the machine needs to modify the insn being conditionally executed,
409	say for example to force a constant integer operand into a temp
410	register, do so here. */
411	#ifdef IFCVT_MODIFY_INSN
412	IFCVT_MODIFY_INSN (ce_info, pattern, insn);
413	if (! pattern)
414	return false;
415	#endif
416
417	validate_change (insn, &PATTERN (insn), pattern, 1);
418
419	if (CALL_P (insn) && prob_val.initialized_p ())
420	validate_change (insn, &REG_NOTES (insn),
421	gen_rtx_INT_LIST ((machine_mode) REG_BR_PROB,
422	prob_val.to_reg_br_prob_note (),
423	REG_NOTES (insn)), 1);
424
425	insn_done:
426	if (insn == end)
427	break;
428	}
429
430	return true;
431	}
432
433	/* Return the condition for a jump. Do not do any special processing. */
434
435	static rtx
436	cond_exec_get_condition (rtx_insn *jump, bool get_reversed = false)
437	{
438	rtx test_if, cond;
439
440	if (any_condjump_p (jump))
441	test_if = SET_SRC (pc_set (jump));
442	else
443	return NULL_RTX;
444	cond = XEXP (test_if, 0);
445
446	/* If this branches to JUMP_LABEL when the condition is false,
447	reverse the condition. */
448	if (get_reversed
449	|| (GET_CODE (XEXP (test_if, 2)) == LABEL_REF
450	&& label_ref_label (XEXP (test_if, 2))
451	== JUMP_LABEL (jump)))
452	{
453	enum rtx_code rev = reversed_comparison_code (cond, jump);
454	if (rev == UNKNOWN)
455	return NULL_RTX;
456
457	cond = gen_rtx_fmt_ee (rev, GET_MODE (cond), XEXP (cond, 0),
458	XEXP (cond, 1));
459	}
460
461	return cond;
462	}
463
464	/* Given a simple IF-THEN or IF-THEN-ELSE block, attempt to convert it
465	to conditional execution. Return TRUE if we were successful at
466	converting the block. */
467
468	static bool
469	cond_exec_process_if_block (ce_if_block * ce_info,
470	/* if block information */bool do_multiple_p)
471	{
472	basic_block test_bb = ce_info->test_bb; /* last test block */
473	basic_block then_bb = ce_info->then_bb; /* THEN */
474	basic_block else_bb = ce_info->else_bb; /* ELSE or NULL */
475	rtx test_expr; /* expression in IF_THEN_ELSE that is tested */
476	rtx_insn *then_start; /* first insn in THEN block */
477	rtx_insn *then_end; /* last insn + 1 in THEN block */
478	rtx_insn *else_start = NULL; /* first insn in ELSE block or NULL */
479	rtx_insn *else_end = NULL; /* last insn + 1 in ELSE block */
480	int max; /* max # of insns to convert. */
481	bool then_mod_ok; /* whether conditional mods are ok in THEN */
482	rtx true_expr; /* test for else block insns */
483	rtx false_expr; /* test for then block insns */
484	profile_probability true_prob_val;/* probability of else block */
485	profile_probability false_prob_val;/* probability of then block */
486	rtx_insn *then_last_head = NULL; /* Last match at the head of THEN */
487	rtx_insn *else_last_head = NULL; /* Last match at the head of ELSE */
488	rtx_insn *then_first_tail = NULL; /* First match at the tail of THEN */
489	rtx_insn *else_first_tail = NULL; /* First match at the tail of ELSE */
490	int then_n_insns, else_n_insns, n_insns;
491	enum rtx_code false_code;
492	rtx note;
493
494	/* If test is comprised of && or || elements, and we've failed at handling
495	all of them together, just use the last test if it is the special case of
496	&& elements without an ELSE block. */
497	if (!do_multiple_p && ce_info->num_multiple_test_blocks)
498	{
499	if (else_bb || ! ce_info->and_and_p)
500	return false;
501
502	ce_info->test_bb = test_bb = ce_info->last_test_bb;
503	ce_info->num_multiple_test_blocks = 0;
504	ce_info->num_and_and_blocks = 0;
505	ce_info->num_or_or_blocks = 0;
506	}
507
508	/* Find the conditional jump to the ELSE or JOIN part, and isolate
509	the test. */
510	test_expr = cond_exec_get_condition (BB_END (test_bb));
511	if (! test_expr)
512	return false;
513
514	/* If the conditional jump is more than just a conditional jump,
515	then we cannot do conditional execution conversion on this block. */
516	if (! onlyjump_p (BB_END (test_bb)))
517	return false;
518
519	/* Collect the bounds of where we're to search, skipping any labels, jumps
520	and notes at the beginning and end of the block. Then count the total
521	number of insns and see if it is small enough to convert. */
522	then_start = first_active_insn (bb: then_bb);
523	then_end = last_active_insn (bb: then_bb, skip_use_p: true);
524	then_n_insns = ce_info->num_then_insns = count_bb_insns (bb: then_bb);
525	n_insns = then_n_insns;
526	max = MAX_CONDITIONAL_EXECUTE;
527
528	if (else_bb)
529	{
530	int n_matching;
531
532	max *= 2;
533	else_start = first_active_insn (bb: else_bb);
534	else_end = last_active_insn (bb: else_bb, skip_use_p: true);
535	else_n_insns = ce_info->num_else_insns = count_bb_insns (bb: else_bb);
536	n_insns += else_n_insns;
537
538	/* Look for matching sequences at the head and tail of the two blocks,
539	and limit the range of insns to be converted if possible. */
540	n_matching = flow_find_cross_jump (then_bb, else_bb,
541	&then_first_tail, &else_first_tail,
542	NULL);
543	if (then_first_tail == BB_HEAD (then_bb))
544	then_start = then_end = NULL;
545	if (else_first_tail == BB_HEAD (else_bb))
546	else_start = else_end = NULL;
547
548	if (n_matching > 0)
549	{
550	if (then_end)
551	then_end = find_active_insn_before (curr_bb: then_bb, insn: then_first_tail);
552	if (else_end)
553	else_end = find_active_insn_before (curr_bb: else_bb, insn: else_first_tail);
554	n_insns -= 2 * n_matching;
555	}
556
557	if (then_start
558	&& else_start
559	&& then_n_insns > n_matching
560	&& else_n_insns > n_matching)
561	{
562	int longest_match = MIN (then_n_insns - n_matching,
563	else_n_insns - n_matching);
564	n_matching
565	= flow_find_head_matching_sequence (then_bb, else_bb,
566	&then_last_head,
567	&else_last_head,
568	longest_match);
569
570	if (n_matching > 0)
571	{
572	rtx_insn *insn;
573
574	/* We won't pass the insns in the head sequence to
575	cond_exec_process_insns, so we need to test them here
576	to make sure that they don't clobber the condition. */
577	for (insn = BB_HEAD (then_bb);
578	insn != NEXT_INSN (insn: then_last_head);
579	insn = NEXT_INSN (insn))
580	if (!LABEL_P (insn) && !NOTE_P (insn)
581	&& !DEBUG_INSN_P (insn)
582	&& modified_in_p (test_expr, insn))
583	return false;
584	}
585
586	if (then_last_head == then_end)
587	then_start = then_end = NULL;
588	if (else_last_head == else_end)
589	else_start = else_end = NULL;
590
591	if (n_matching > 0)
592	{
593	if (then_start)
594	then_start = find_active_insn_after (curr_bb: then_bb, insn: then_last_head);
595	if (else_start)
596	else_start = find_active_insn_after (curr_bb: else_bb, insn: else_last_head);
597	n_insns -= 2 * n_matching;
598	}
599	}
600	}
601
602	if (n_insns > max)
603	return false;
604
605	/* Map test_expr/test_jump into the appropriate MD tests to use on
606	the conditionally executed code. */
607
608	true_expr = test_expr;
609
610	false_code = reversed_comparison_code (true_expr, BB_END (test_bb));
611	if (false_code != UNKNOWN)
612	false_expr = gen_rtx_fmt_ee (false_code, GET_MODE (true_expr),
613	XEXP (true_expr, 0), XEXP (true_expr, 1));
614	else
615	false_expr = NULL_RTX;
616
617	#ifdef IFCVT_MODIFY_TESTS
618	/* If the machine description needs to modify the tests, such as setting a
619	conditional execution register from a comparison, it can do so here. */
620	IFCVT_MODIFY_TESTS (ce_info, true_expr, false_expr);
621
622	/* See if the conversion failed. */
623	if (!true_expr || !false_expr)
624	goto fail;
625	#endif
626
627	note = find_reg_note (BB_END (test_bb), REG_BR_PROB, NULL_RTX);
628	if (note)
629	{
630	true_prob_val = profile_probability::from_reg_br_prob_note (XINT (note, 0));
631	false_prob_val = true_prob_val.invert ();
632	}
633	else
634	{
635	true_prob_val = profile_probability::uninitialized ();
636	false_prob_val = profile_probability::uninitialized ();
637	}
638
639	/* If we have && or || tests, do them here. These tests are in the adjacent
640	blocks after the first block containing the test. */
641	if (ce_info->num_multiple_test_blocks > 0)
642	{
643	basic_block bb = test_bb;
644	basic_block last_test_bb = ce_info->last_test_bb;
645
646	if (! false_expr)
647	goto fail;
648
649	do
650	{
651	rtx_insn *start, *end;
652	rtx t, f;
653	enum rtx_code f_code;
654
655	bb = block_fallthru (bb);
656	start = first_active_insn (bb);
657	end = last_active_insn (bb, skip_use_p: true);
658	if (start
659	&& ! cond_exec_process_insns (ce_info, start, end, test: false_expr,
660	prob_val: false_prob_val, mod_ok: false))
661	goto fail;
662
663	/* If the conditional jump is more than just a conditional jump, then
664	we cannot do conditional execution conversion on this block. */
665	if (! onlyjump_p (BB_END (bb)))
666	goto fail;
667
668	/* Find the conditional jump and isolate the test. */
669	t = cond_exec_get_condition (BB_END (bb));
670	if (! t)
671	goto fail;
672
673	f_code = reversed_comparison_code (t, BB_END (bb));
674	if (f_code == UNKNOWN)
675	goto fail;
676
677	f = gen_rtx_fmt_ee (f_code, GET_MODE (t), XEXP (t, 0), XEXP (t, 1));
678	if (ce_info->and_and_p)
679	{
680	t = gen_rtx_AND (GET_MODE (t), true_expr, t);
681	f = gen_rtx_IOR (GET_MODE (t), false_expr, f);
682	}
683	else
684	{
685	t = gen_rtx_IOR (GET_MODE (t), true_expr, t);
686	f = gen_rtx_AND (GET_MODE (t), false_expr, f);
687	}
688
689	/* If the machine description needs to modify the tests, such as
690	setting a conditional execution register from a comparison, it can
691	do so here. */
692	#ifdef IFCVT_MODIFY_MULTIPLE_TESTS
693	IFCVT_MODIFY_MULTIPLE_TESTS (ce_info, bb, t, f);
694
695	/* See if the conversion failed. */
696	if (!t || !f)
697	goto fail;
698	#endif
699
700	true_expr = t;
701	false_expr = f;
702	}
703	while (bb != last_test_bb);
704	}
705
706	/* For IF-THEN-ELSE blocks, we don't allow modifications of the test
707	on then THEN block. */
708	then_mod_ok = (else_bb == NULL_BLOCK);
709
710	/* Go through the THEN and ELSE blocks converting the insns if possible
711	to conditional execution. */
712
713	if (then_end
714	&& (! false_expr
715	|| ! cond_exec_process_insns (ce_info, start: then_start, end: then_end,
716	test: false_expr, prob_val: false_prob_val,
717	mod_ok: then_mod_ok)))
718	goto fail;
719
720	if (else_bb && else_end
721	&& ! cond_exec_process_insns (ce_info, start: else_start, end: else_end,
722	test: true_expr, prob_val: true_prob_val, mod_ok: true))
723	goto fail;
724
725	/* If we cannot apply the changes, fail. Do not go through the normal fail
726	processing, since apply_change_group will call cancel_changes. */
727	if (! apply_change_group ())
728	{
729	#ifdef IFCVT_MODIFY_CANCEL
730	/* Cancel any machine dependent changes. */
731	IFCVT_MODIFY_CANCEL (ce_info);
732	#endif
733	return false;
734	}
735
736	#ifdef IFCVT_MODIFY_FINAL
737	/* Do any machine dependent final modifications. */
738	IFCVT_MODIFY_FINAL (ce_info);
739	#endif
740
741	/* Conversion succeeded. */
742	if (dump_file)
743	fprintf (stream: dump_file, format: "%d insn%s converted to conditional execution.\n",
744	n_insns, (n_insns == 1) ? " was" : "s were");
745
746	/* Merge the blocks! If we had matching sequences, make sure to delete one
747	copy at the appropriate location first: delete the copy in the THEN branch
748	for a tail sequence so that the remaining one is executed last for both
749	branches, and delete the copy in the ELSE branch for a head sequence so
750	that the remaining one is executed first for both branches. */
751	if (then_first_tail)
752	{
753	rtx_insn *from = then_first_tail;
754	if (!INSN_P (from))
755	from = find_active_insn_after (curr_bb: then_bb, insn: from);
756	delete_insn_chain (from, get_last_bb_insn (then_bb), false);
757	}
758	if (else_last_head)
759	delete_insn_chain (first_active_insn (bb: else_bb), else_last_head, false);
760
761	merge_if_block (ce_info);
762	cond_exec_changed_p = true;
763	return true;
764
765	fail:
766	#ifdef IFCVT_MODIFY_CANCEL
767	/* Cancel any machine dependent changes. */
768	IFCVT_MODIFY_CANCEL (ce_info);
769	#endif
770
771	cancel_changes (0);
772	return false;
773	}
774
775	static rtx noce_emit_store_flag (struct noce_if_info *, rtx, bool, int);
776	static bool noce_try_move (struct noce_if_info *);
777	static bool noce_try_ifelse_collapse (struct noce_if_info *);
778	static bool noce_try_store_flag (struct noce_if_info *);
779	static bool noce_try_addcc (struct noce_if_info *);
780	static bool noce_try_store_flag_constants (struct noce_if_info *);
781	static bool noce_try_store_flag_mask (struct noce_if_info *);
782	static rtx noce_emit_cmove (struct noce_if_info *, rtx, enum rtx_code, rtx,
783	rtx, rtx, rtx, rtx = NULL, rtx = NULL);
784	static bool noce_try_cmove (struct noce_if_info *);
785	static bool noce_try_cmove_arith (struct noce_if_info *);
786	static rtx noce_get_alt_condition (struct noce_if_info *, rtx, rtx_insn **);
787	static bool noce_try_minmax (struct noce_if_info *);
788	static bool noce_try_abs (struct noce_if_info *);
789	static bool noce_try_sign_mask (struct noce_if_info *);
790	static int noce_try_cond_zero_arith (struct noce_if_info *);
791
792	/* Return the comparison code for reversed condition for IF_INFO,
793	or UNKNOWN if reversing the condition is not possible. */
794
795	static inline enum rtx_code
796	noce_reversed_cond_code (struct noce_if_info *if_info)
797	{
798	if (if_info->rev_cond)
799	return GET_CODE (if_info->rev_cond);
800	return reversed_comparison_code (if_info->cond, if_info->jump);
801	}
802
803	/* Return true if SEQ is a good candidate as a replacement for the
804	if-convertible sequence described in IF_INFO.
805	This is the default implementation that targets can override
806	through a target hook. */
807
808	bool
809	default_noce_conversion_profitable_p (rtx_insn *seq,
810	struct noce_if_info *if_info)
811	{
812	bool speed_p = if_info->speed_p;
813
814	/* Cost up the new sequence. */
815	unsigned int cost = seq_cost (seq, speed_p);
816
817	if (cost <= if_info->original_cost)
818	return true;
819
820	/* When compiling for size, we can make a reasonably accurately guess
821	at the size growth. When compiling for speed, use the maximum. */
822	return speed_p && cost <= if_info->max_seq_cost;
823	}
824
825	/* Helper function for noce_try_store_flag*. */
826
827	static rtx
828	noce_emit_store_flag (struct noce_if_info *if_info, rtx x, bool reversep,
829	int normalize)
830	{
831	rtx cond = if_info->cond;
832	bool cond_complex;
833	enum rtx_code code;
834
835	cond_complex = (! general_operand (XEXP (cond, 0), VOIDmode)
836	|| ! general_operand (XEXP (cond, 1), VOIDmode));
837
838	/* If earliest == jump, or when the condition is complex, try to
839	build the store_flag insn directly. */
840
841	if (cond_complex)
842	{
843	rtx set = pc_set (if_info->jump);
844	cond = XEXP (SET_SRC (set), 0);
845	if (GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
846	&& label_ref_label (XEXP (SET_SRC (set), 2)) == JUMP_LABEL (if_info->jump))
847	reversep = !reversep;
848	if (if_info->then_else_reversed)
849	reversep = !reversep;
850	}
851	else if (reversep
852	&& if_info->rev_cond
853	&& general_operand (XEXP (if_info->rev_cond, 0), VOIDmode)
854	&& general_operand (XEXP (if_info->rev_cond, 1), VOIDmode))
855	{
856	cond = if_info->rev_cond;
857	reversep = false;
858	}
859
860	if (reversep)
861	code = reversed_comparison_code (cond, if_info->jump);
862	else
863	code = GET_CODE (cond);
864
865	if ((if_info->cond_earliest == if_info->jump || cond_complex)
866	&& (normalize == 0 || STORE_FLAG_VALUE == normalize))
867	{
868	rtx src = gen_rtx_fmt_ee (code, GET_MODE (x), XEXP (cond, 0),
869	XEXP (cond, 1));
870	rtx set = gen_rtx_SET (x, src);
871
872	start_sequence ();
873	rtx_insn *insn = emit_insn (set);
874
875	if (recog_memoized (insn) >= 0)
876	{
877	rtx_insn *seq = get_insns ();
878	end_sequence ();
879	emit_insn (seq);
880
881	if_info->cond_earliest = if_info->jump;
882
883	return x;
884	}
885
886	end_sequence ();
887	}
888
889	/* Don't even try if the comparison operands or the mode of X are weird. */
890	if (cond_complex || !SCALAR_INT_MODE_P (GET_MODE (x)))
891	return NULL_RTX;
892
893	return emit_store_flag (x, code, XEXP (cond, 0),
894	XEXP (cond, 1), VOIDmode,
895	(code == LTU || code == LEU
896	|| code == GEU || code == GTU), normalize);
897	}
898
899	/* Return true if X can be safely forced into a register by copy_to_mode_reg
900	/ force_operand. */
901
902	static bool
903	noce_can_force_operand (rtx x)
904	{
905	if (general_operand (x, VOIDmode))
906	return true;
907	if (SUBREG_P (x))
908	{
909	if (!noce_can_force_operand (SUBREG_REG (x)))
910	return false;
911	return true;
912	}
913	if (ARITHMETIC_P (x))
914	{
915	if (!noce_can_force_operand (XEXP (x, 0))
916	|| !noce_can_force_operand (XEXP (x, 1)))
917	return false;
918	switch (GET_CODE (x))
919	{
920	case MULT:
921	case DIV:
922	case MOD:
923	case UDIV:
924	case UMOD:
925	return true;
926	default:
927	return code_to_optab (GET_CODE (x));
928	}
929	}
930	if (UNARY_P (x))
931	{
932	if (!noce_can_force_operand (XEXP (x, 0)))
933	return false;
934	switch (GET_CODE (x))
935	{
936	case ZERO_EXTEND:
937	case SIGN_EXTEND:
938	case TRUNCATE:
939	case FLOAT_EXTEND:
940	case FLOAT_TRUNCATE:
941	case FIX:
942	case UNSIGNED_FIX:
943	case FLOAT:
944	case UNSIGNED_FLOAT:
945	return true;
946	default:
947	return code_to_optab (GET_CODE (x));
948	}
949	}
950	return false;
951	}
952
953	/* Emit instruction to move an rtx, possibly into STRICT_LOW_PART.
954	X is the destination/target and Y is the value to copy. */
955
956	static void
957	noce_emit_move_insn (rtx x, rtx y)
958	{
959	machine_mode outmode;
960	rtx outer, inner;
961	poly_int64 bitpos;
962
963	if (GET_CODE (x) != STRICT_LOW_PART)
964	{
965	rtx_insn *seq, *insn;
966	rtx target;
967	optab ot;
968
969	start_sequence ();
970	/* Check that the SET_SRC is reasonable before calling emit_move_insn,
971	otherwise construct a suitable SET pattern ourselves. */
972	insn = (OBJECT_P (y) || CONSTANT_P (y) || GET_CODE (y) == SUBREG)
973	? emit_move_insn (x, y)
974	: emit_insn (gen_rtx_SET (x, y));
975	seq = get_insns ();
976	end_sequence ();
977
978	if (recog_memoized (insn) <= 0)
979	{
980	if (GET_CODE (x) == ZERO_EXTRACT)
981	{
982	rtx op = XEXP (x, 0);
983	unsigned HOST_WIDE_INT size = INTVAL (XEXP (x, 1));
984	unsigned HOST_WIDE_INT start = INTVAL (XEXP (x, 2));
985
986	/* store_bit_field expects START to be relative to
987	BYTES_BIG_ENDIAN and adjusts this value for machines with
988	BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN. In order to be able to
989	invoke store_bit_field again it is necessary to have the START
990	value from the first call. */
991	if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
992	{
993	if (MEM_P (op))
994	start = BITS_PER_UNIT - start - size;
995	else
996	{
997	gcc_assert (REG_P (op));
998	start = BITS_PER_WORD - start - size;
999	}
1000	}
1001
1002	gcc_assert (start < (MEM_P (op) ? BITS_PER_UNIT : BITS_PER_WORD));
1003	store_bit_field (op, size, start, 0, 0, GET_MODE (x), y, false,
1004	false);
1005	return;
1006	}
1007
1008	switch (GET_RTX_CLASS (GET_CODE (y)))
1009	{
1010	case RTX_UNARY:
1011	ot = code_to_optab (GET_CODE (y));
1012	if (ot && noce_can_force_operand (XEXP (y, 0)))
1013	{
1014	start_sequence ();
1015	target = expand_unop (GET_MODE (y), ot, XEXP (y, 0), x, 0);
1016	if (target != NULL_RTX)
1017	{
1018	if (target != x)
1019	emit_move_insn (x, target);
1020	seq = get_insns ();
1021	}
1022	end_sequence ();
1023	}
1024	break;
1025
1026	case RTX_BIN_ARITH:
1027	case RTX_COMM_ARITH:
1028	ot = code_to_optab (GET_CODE (y));
1029	if (ot
1030	&& noce_can_force_operand (XEXP (y, 0))
1031	&& noce_can_force_operand (XEXP (y, 1)))
1032	{
1033	start_sequence ();
1034	target = expand_binop (GET_MODE (y), ot,
1035	XEXP (y, 0), XEXP (y, 1),
1036	x, 0, OPTAB_DIRECT);
1037	if (target != NULL_RTX)
1038	{
1039	if (target != x)
1040	emit_move_insn (x, target);
1041	seq = get_insns ();
1042	}
1043	end_sequence ();
1044	}
1045	break;
1046
1047	default:
1048	break;
1049	}
1050	}
1051
1052	emit_insn (seq);
1053	return;
1054	}
1055
1056	outer = XEXP (x, 0);
1057	inner = XEXP (outer, 0);
1058	outmode = GET_MODE (outer);
1059	bitpos = SUBREG_BYTE (outer) * BITS_PER_UNIT;
1060	store_bit_field (inner, GET_MODE_BITSIZE (mode: outmode), bitpos,
1061	0, 0, outmode, y, false, false);
1062	}
1063
1064	/* Return the CC reg if it is used in COND. */
1065
1066	static rtx
1067	cc_in_cond (rtx cond)
1068	{
1069	if (have_cbranchcc4 && cond
1070	&& GET_MODE_CLASS (GET_MODE (XEXP (cond, 0))) == MODE_CC)
1071	return XEXP (cond, 0);
1072
1073	return NULL_RTX;
1074	}
1075
1076	/* Return sequence of instructions generated by if conversion. This
1077	function calls end_sequence() to end the current stream, ensures
1078	that the instructions are unshared, recognizable non-jump insns.
1079	On failure, this function returns a NULL_RTX. */
1080
1081	static rtx_insn *
1082	end_ifcvt_sequence (struct noce_if_info *if_info)
1083	{
1084	rtx_insn *insn;
1085	rtx_insn *seq = get_insns ();
1086	rtx cc = cc_in_cond (cond: if_info->cond);
1087
1088	set_used_flags (if_info->x);
1089	set_used_flags (if_info->cond);
1090	set_used_flags (if_info->a);
1091	set_used_flags (if_info->b);
1092
1093	for (insn = seq; insn; insn = NEXT_INSN (insn))
1094	set_used_flags (insn);
1095
1096	unshare_all_rtl_in_chain (seq);
1097	end_sequence ();
1098
1099	/* Make sure that all of the instructions emitted are recognizable,
1100	and that we haven't introduced a new jump instruction.
1101	As an exercise for the reader, build a general mechanism that
1102	allows proper placement of required clobbers. */
1103	for (insn = seq; insn; insn = NEXT_INSN (insn))
1104	if (JUMP_P (insn)
1105	|| recog_memoized (insn) == -1
1106	/* Make sure new generated code does not clobber CC. */
1107	|| (cc && set_of (cc, insn)))
1108	return NULL;
1109
1110	return seq;
1111	}
1112
1113	/* Return true iff the then and else basic block (if it exists)
1114	consist of a single simple set instruction. */
1115
1116	static bool
1117	noce_simple_bbs (struct noce_if_info *if_info)
1118	{
1119	if (!if_info->then_simple)
1120	return false;
1121
1122	if (if_info->else_bb)
1123	return if_info->else_simple;
1124
1125	return true;
1126	}
1127
1128	/* Convert "if (a != b) x = a; else x = b" into "x = a" and
1129	"if (a == b) x = a; else x = b" into "x = b". */
1130
1131	static bool
1132	noce_try_move (struct noce_if_info *if_info)
1133	{
1134	rtx cond = if_info->cond;
1135	enum rtx_code code = GET_CODE (cond);
1136	rtx y;
1137	rtx_insn *seq;
1138
1139	if (code != NE && code != EQ)
1140	return false;
1141
1142	if (!noce_simple_bbs (if_info))
1143	return false;
1144
1145	/* This optimization isn't valid if either A or B could be a NaN
1146	or a signed zero. */
1147	if (HONOR_NANS (if_info->x)
1148	|| HONOR_SIGNED_ZEROS (if_info->x))
1149	return false;
1150
1151	/* Check whether the operands of the comparison are A and in
1152	either order. */
1153	if ((rtx_equal_p (if_info->a, XEXP (cond, 0))
1154	&& rtx_equal_p (if_info->b, XEXP (cond, 1)))
1155	|| (rtx_equal_p (if_info->a, XEXP (cond, 1))
1156	&& rtx_equal_p (if_info->b, XEXP (cond, 0))))
1157	{
1158	if (!rtx_interchangeable_p (a: if_info->a, b: if_info->b))
1159	return false;
1160
1161	y = (code == EQ) ? if_info->a : if_info->b;
1162
1163	/* Avoid generating the move if the source is the destination. */
1164	if (! rtx_equal_p (if_info->x, y))
1165	{
1166	start_sequence ();
1167	noce_emit_move_insn (x: if_info->x, y);
1168	seq = end_ifcvt_sequence (if_info);
1169	if (!seq)
1170	return false;
1171
1172	emit_insn_before_setloc (seq, if_info->jump,
1173	INSN_LOCATION (insn: if_info->insn_a));
1174	}
1175	if_info->transform_name = "noce_try_move";
1176	return true;
1177	}
1178	return false;
1179	}
1180
1181	/* Try forming an IF_THEN_ELSE (cond, b, a) and collapsing that
1182	through simplify_rtx. Sometimes that can eliminate the IF_THEN_ELSE.
1183	If that is the case, emit the result into x. */
1184
1185	static bool
1186	noce_try_ifelse_collapse (struct noce_if_info * if_info)
1187	{
1188	if (!noce_simple_bbs (if_info))
1189	return false;
1190
1191	machine_mode mode = GET_MODE (if_info->x);
1192	rtx if_then_else = simplify_gen_ternary (code: IF_THEN_ELSE, mode, op0_mode: mode,
1193	op0: if_info->cond, op1: if_info->b,
1194	op2: if_info->a);
1195
1196	if (GET_CODE (if_then_else) == IF_THEN_ELSE)
1197	return false;
1198
1199	rtx_insn *seq;
1200	start_sequence ();
1201	noce_emit_move_insn (x: if_info->x, y: if_then_else);
1202	seq = end_ifcvt_sequence (if_info);
1203	if (!seq)
1204	return false;
1205
1206	emit_insn_before_setloc (seq, if_info->jump,
1207	INSN_LOCATION (insn: if_info->insn_a));
1208
1209	if_info->transform_name = "noce_try_ifelse_collapse";
1210	return true;
1211	}
1212
1213
1214	/* Convert "if (test) x = 1; else x = 0".
1215
1216	Only try 0 and STORE_FLAG_VALUE here. Other combinations will be
1217	tried in noce_try_store_flag_constants after noce_try_cmove has had
1218	a go at the conversion. */
1219
1220	static bool
1221	noce_try_store_flag (struct noce_if_info *if_info)
1222	{
1223	bool reversep;
1224	rtx target;
1225	rtx_insn *seq;
1226
1227	if (!noce_simple_bbs (if_info))
1228	return false;
1229
1230	if (CONST_INT_P (if_info->b)
1231	&& INTVAL (if_info->b) == STORE_FLAG_VALUE
1232	&& if_info->a == const0_rtx)
1233	reversep = false;
1234	else if (if_info->b == const0_rtx
1235	&& CONST_INT_P (if_info->a)
1236	&& INTVAL (if_info->a) == STORE_FLAG_VALUE
1237	&& noce_reversed_cond_code (if_info) != UNKNOWN)
1238	reversep = true;
1239	else
1240	return false;
1241
1242	start_sequence ();
1243
1244	target = noce_emit_store_flag (if_info, x: if_info->x, reversep, normalize: 0);
1245	if (target)
1246	{
1247	if (target != if_info->x)
1248	noce_emit_move_insn (x: if_info->x, y: target);
1249
1250	seq = end_ifcvt_sequence (if_info);
1251	if (! seq)
1252	return false;
1253
1254	emit_insn_before_setloc (seq, if_info->jump,
1255	INSN_LOCATION (insn: if_info->insn_a));
1256	if_info->transform_name = "noce_try_store_flag";
1257	return true;
1258	}
1259	else
1260	{
1261	end_sequence ();
1262	return false;
1263	}
1264	}
1265
1266
1267	/* Convert "if (test) x = -A; else x = A" into
1268	x = A; if (test) x = -x if the machine can do the
1269	conditional negate form of this cheaply.
1270	Try this before noce_try_cmove that will just load the
1271	immediates into two registers and do a conditional select
1272	between them. If the target has a conditional negate or
1273	conditional invert operation we can save a potentially
1274	expensive constant synthesis. */
1275
1276	static bool
1277	noce_try_inverse_constants (struct noce_if_info *if_info)
1278	{
1279	if (!noce_simple_bbs (if_info))
1280	return false;
1281
1282	if (!CONST_INT_P (if_info->a)
1283	|| !CONST_INT_P (if_info->b)
1284	|| !REG_P (if_info->x))
1285	return false;
1286
1287	machine_mode mode = GET_MODE (if_info->x);
1288
1289	HOST_WIDE_INT val_a = INTVAL (if_info->a);
1290	HOST_WIDE_INT val_b = INTVAL (if_info->b);
1291
1292	rtx cond = if_info->cond;
1293
1294	rtx x = if_info->x;
1295	rtx target;
1296
1297	start_sequence ();
1298
1299	rtx_code code;
1300	if (val_b != HOST_WIDE_INT_MIN && val_a == -val_b)
1301	code = NEG;
1302	else if (val_a == ~val_b)
1303	code = NOT;
1304	else
1305	{
1306	end_sequence ();
1307	return false;
1308	}
1309
1310	rtx tmp = gen_reg_rtx (mode);
1311	noce_emit_move_insn (x: tmp, y: if_info->a);
1312
1313	target = emit_conditional_neg_or_complement (x, code, mode, cond, tmp, tmp);
1314
1315	if (target)
1316	{
1317	rtx_insn *seq = get_insns ();
1318
1319	if (!seq)
1320	{
1321	end_sequence ();
1322	return false;
1323	}
1324
1325	if (target != if_info->x)
1326	noce_emit_move_insn (x: if_info->x, y: target);
1327
1328	seq = end_ifcvt_sequence (if_info);
1329
1330	if (!seq)
1331	return false;
1332
1333	emit_insn_before_setloc (seq, if_info->jump,
1334	INSN_LOCATION (insn: if_info->insn_a));
1335	if_info->transform_name = "noce_try_inverse_constants";
1336	return true;
1337	}
1338
1339	end_sequence ();
1340	return false;
1341	}
1342
1343
1344	/* Convert "if (test) x = a; else x = b", for A and B constant.
1345	Also allow A = y + c1, B = y + c2, with a common y between A
1346	and B. */
1347
1348	static bool
1349	noce_try_store_flag_constants (struct noce_if_info *if_info)
1350	{
1351	rtx target;
1352	rtx_insn *seq;
1353	bool reversep;
1354	HOST_WIDE_INT itrue, ifalse, diff, tmp;
1355	int normalize;
1356	bool can_reverse;
1357	machine_mode mode = GET_MODE (if_info->x);
1358	rtx common = NULL_RTX;
1359
1360	rtx a = if_info->a;
1361	rtx b = if_info->b;
1362
1363	/* Handle cases like x := test ? y + 3 : y + 4. */
1364	if (GET_CODE (a) == PLUS
1365	&& GET_CODE (b) == PLUS
1366	&& CONST_INT_P (XEXP (a, 1))
1367	&& CONST_INT_P (XEXP (b, 1))
1368	&& rtx_equal_p (XEXP (a, 0), XEXP (b, 0))
1369	/* Allow expressions that are not using the result or plain
1370	registers where we handle overlap below. */
1371	&& (REG_P (XEXP (a, 0))
1372	|| (noce_operand_ok (XEXP (a, 0))
1373	&& ! reg_overlap_mentioned_p (if_info->x, XEXP (a, 0)))))
1374	{
1375	common = XEXP (a, 0);
1376	a = XEXP (a, 1);
1377	b = XEXP (b, 1);
1378	}
1379
1380	if (!noce_simple_bbs (if_info))
1381	return false;
1382
1383	if (CONST_INT_P (a)
1384	&& CONST_INT_P (b))
1385	{
1386	ifalse = INTVAL (a);
1387	itrue = INTVAL (b);
1388	bool subtract_flag_p = false;
1389
1390	diff = (unsigned HOST_WIDE_INT) itrue - ifalse;
1391	/* Make sure we can represent the difference between the two values. */
1392	if ((diff > 0)
1393	!= ((ifalse < 0) != (itrue < 0) ? ifalse < 0 : ifalse < itrue))
1394	return false;
1395
1396	diff = trunc_int_for_mode (diff, mode);
1397
1398	can_reverse = noce_reversed_cond_code (if_info) != UNKNOWN;
1399	reversep = false;
1400	if (diff == STORE_FLAG_VALUE || diff == -STORE_FLAG_VALUE)
1401	{
1402	normalize = 0;
1403	/* We could collapse these cases but it is easier to follow the
1404	diff/STORE_FLAG_VALUE combinations when they are listed
1405	explicitly. */
1406
1407	/* test ? 3 : 4
1408	=> 4 + (test != 0). */
1409	if (diff < 0 && STORE_FLAG_VALUE < 0)
1410	reversep = false;
1411	/* test ? 4 : 3
1412	=> can_reverse | 4 + (test == 0)
1413	!can_reverse | 3 - (test != 0). */
1414	else if (diff > 0 && STORE_FLAG_VALUE < 0)
1415	{
1416	reversep = can_reverse;
1417	subtract_flag_p = !can_reverse;
1418	/* If we need to subtract the flag and we have PLUS-immediate
1419	A and B then it is unlikely to be beneficial to play tricks
1420	here. */
1421	if (subtract_flag_p && common)
1422	return false;
1423	}
1424	/* test ? 3 : 4
1425	=> can_reverse | 3 + (test == 0)
1426	!can_reverse | 4 - (test != 0). */
1427	else if (diff < 0 && STORE_FLAG_VALUE > 0)
1428	{
1429	reversep = can_reverse;
1430	subtract_flag_p = !can_reverse;
1431	/* If we need to subtract the flag and we have PLUS-immediate
1432	A and B then it is unlikely to be beneficial to play tricks
1433	here. */
1434	if (subtract_flag_p && common)
1435	return false;
1436	}
1437	/* test ? 4 : 3
1438	=> 4 + (test != 0). */
1439	else if (diff > 0 && STORE_FLAG_VALUE > 0)
1440	reversep = false;
1441	else
1442	gcc_unreachable ();
1443	}
1444	/* Is this (cond) ? 2^n : 0? */
1445	else if (ifalse == 0 && pow2p_hwi (x: itrue)
1446	&& STORE_FLAG_VALUE == 1)
1447	normalize = 1;
1448	/* Is this (cond) ? 0 : 2^n? */
1449	else if (itrue == 0 && pow2p_hwi (x: ifalse) && can_reverse
1450	&& STORE_FLAG_VALUE == 1)
1451	{
1452	normalize = 1;
1453	reversep = true;
1454	}
1455	/* Is this (cond) ? -1 : x? */
1456	else if (itrue == -1
1457	&& STORE_FLAG_VALUE == -1)
1458	normalize = -1;
1459	/* Is this (cond) ? x : -1? */
1460	else if (ifalse == -1 && can_reverse
1461	&& STORE_FLAG_VALUE == -1)
1462	{
1463	normalize = -1;
1464	reversep = true;
1465	}
1466	else
1467	return false;
1468
1469	if (reversep)
1470	{
1471	std::swap (a&: itrue, b&: ifalse);
1472	diff = trunc_int_for_mode (-(unsigned HOST_WIDE_INT) diff, mode);
1473	}
1474
1475	start_sequence ();
1476
1477	/* If we have x := test ? x + 3 : x + 4 then move the original
1478	x out of the way while we store flags. */
1479	if (common && rtx_equal_p (common, if_info->x))
1480	{
1481	common = gen_reg_rtx (mode);
1482	noce_emit_move_insn (x: common, y: if_info->x);
1483	}
1484
1485	target = noce_emit_store_flag (if_info, x: if_info->x, reversep, normalize);
1486	if (! target)
1487	{
1488	end_sequence ();
1489	return false;
1490	}
1491
1492	/* if (test) x = 3; else x = 4;
1493	=> x = 3 + (test == 0); */
1494	if (diff == STORE_FLAG_VALUE || diff == -STORE_FLAG_VALUE)
1495	{
1496	/* Add the common part now. This may allow combine to merge this
1497	with the store flag operation earlier into some sort of conditional
1498	increment/decrement if the target allows it. */
1499	if (common)
1500	target = expand_simple_binop (mode, PLUS,
1501	target, common,
1502	target, 0, OPTAB_WIDEN);
1503
1504	/* Always use ifalse here. It should have been swapped with itrue
1505	when appropriate when reversep is true. */
1506	target = expand_simple_binop (mode, subtract_flag_p ? MINUS : PLUS,
1507	gen_int_mode (ifalse, mode), target,
1508	if_info->x, 0, OPTAB_WIDEN);
1509	}
1510	/* Other cases are not beneficial when the original A and B are PLUS
1511	expressions. */
1512	else if (common)
1513	{
1514	end_sequence ();
1515	return false;
1516	}
1517	/* if (test) x = 8; else x = 0;
1518	=> x = (test != 0) << 3; */
1519	else if (ifalse == 0 && (tmp = exact_log2 (x: itrue)) >= 0)
1520	{
1521	target = expand_simple_binop (mode, ASHIFT,
1522	target, GEN_INT (tmp), if_info->x, 0,
1523	OPTAB_WIDEN);
1524	}
1525
1526	/* if (test) x = -1; else x = b;
1527	=> x = -(test != 0) | b; */
1528	else if (itrue == -1)
1529	{
1530	target = expand_simple_binop (mode, IOR,
1531	target, gen_int_mode (ifalse, mode),
1532	if_info->x, 0, OPTAB_WIDEN);
1533	}
1534	else
1535	{
1536	end_sequence ();
1537	return false;
1538	}
1539
1540	if (! target)
1541	{
1542	end_sequence ();
1543	return false;
1544	}
1545
1546	if (target != if_info->x)
1547	noce_emit_move_insn (x: if_info->x, y: target);
1548
1549	seq = end_ifcvt_sequence (if_info);
1550	if (!seq || !targetm.noce_conversion_profitable_p (seq, if_info))
1551	return false;
1552
1553	emit_insn_before_setloc (seq, if_info->jump,
1554	INSN_LOCATION (insn: if_info->insn_a));
1555	if_info->transform_name = "noce_try_store_flag_constants";
1556
1557	return true;
1558	}
1559
1560	return false;
1561	}
1562
1563	/* Convert "if (test) foo++" into "foo += (test != 0)", and
1564	similarly for "foo--". */
1565
1566	static bool
1567	noce_try_addcc (struct noce_if_info *if_info)
1568	{
1569	rtx target;
1570	rtx_insn *seq;
1571	bool subtract;
1572	int normalize;
1573
1574	if (!noce_simple_bbs (if_info))
1575	return false;
1576
1577	if (GET_CODE (if_info->a) == PLUS
1578	&& rtx_equal_p (XEXP (if_info->a, 0), if_info->b)
1579	&& noce_reversed_cond_code (if_info) != UNKNOWN)
1580	{
1581	rtx cond = if_info->rev_cond;
1582	enum rtx_code code;
1583
1584	if (cond == NULL_RTX)
1585	{
1586	cond = if_info->cond;
1587	code = reversed_comparison_code (cond, if_info->jump);
1588	}
1589	else
1590	code = GET_CODE (cond);
1591
1592	/* First try to use addcc pattern. */
1593	if (general_operand (XEXP (cond, 0), VOIDmode)
1594	&& general_operand (XEXP (cond, 1), VOIDmode))
1595	{
1596	start_sequence ();
1597	target = emit_conditional_add (if_info->x, code,
1598	XEXP (cond, 0),
1599	XEXP (cond, 1),
1600	VOIDmode,
1601	if_info->b,
1602	XEXP (if_info->a, 1),
1603	GET_MODE (if_info->x),
1604	(code == LTU || code == GEU
1605	|| code == LEU || code == GTU));
1606	if (target)
1607	{
1608	if (target != if_info->x)
1609	noce_emit_move_insn (x: if_info->x, y: target);
1610
1611	seq = end_ifcvt_sequence (if_info);
1612	if (!seq || !targetm.noce_conversion_profitable_p (seq, if_info))
1613	return false;
1614
1615	emit_insn_before_setloc (seq, if_info->jump,
1616	INSN_LOCATION (insn: if_info->insn_a));
1617	if_info->transform_name = "noce_try_addcc";
1618
1619	return true;
1620	}
1621	end_sequence ();
1622	}
1623
1624	/* If that fails, construct conditional increment or decrement using
1625	setcc. We're changing a branch and an increment to a comparison and
1626	an ADD/SUB. */
1627	if (XEXP (if_info->a, 1) == const1_rtx
1628	|| XEXP (if_info->a, 1) == constm1_rtx)
1629	{
1630	start_sequence ();
1631	if (STORE_FLAG_VALUE == INTVAL (XEXP (if_info->a, 1)))
1632	subtract = false, normalize = 0;
1633	else if (-STORE_FLAG_VALUE == INTVAL (XEXP (if_info->a, 1)))
1634	subtract = true, normalize = 0;
1635	else
1636	subtract = false, normalize = INTVAL (XEXP (if_info->a, 1));
1637
1638
1639	target = noce_emit_store_flag (if_info,
1640	x: gen_reg_rtx (GET_MODE (if_info->x)),
1641	reversep: true, normalize);
1642
1643	if (target)
1644	target = expand_simple_binop (GET_MODE (if_info->x),
1645	subtract ? MINUS : PLUS,
1646	if_info->b, target, if_info->x,
1647	0, OPTAB_WIDEN);
1648	if (target)
1649	{
1650	if (target != if_info->x)
1651	noce_emit_move_insn (x: if_info->x, y: target);
1652
1653	seq = end_ifcvt_sequence (if_info);
1654	if (!seq || !targetm.noce_conversion_profitable_p (seq, if_info))
1655	return false;
1656
1657	emit_insn_before_setloc (seq, if_info->jump,
1658	INSN_LOCATION (insn: if_info->insn_a));
1659	if_info->transform_name = "noce_try_addcc";
1660	return true;
1661	}
1662	end_sequence ();
1663	}
1664	}
1665
1666	return false;
1667	}
1668
1669	/* Convert "if (test) x = 0;" to "x &= -(test == 0);" */
1670
1671	static bool
1672	noce_try_store_flag_mask (struct noce_if_info *if_info)
1673	{
1674	rtx target;
1675	rtx_insn *seq;
1676	bool reversep;
1677
1678	if (!noce_simple_bbs (if_info))
1679	return false;
1680
1681	reversep = false;
1682
1683	if ((if_info->a == const0_rtx
1684	&& (REG_P (if_info->b) || rtx_equal_p (if_info->b, if_info->x)))
1685	|| ((reversep = (noce_reversed_cond_code (if_info) != UNKNOWN))
1686	&& if_info->b == const0_rtx
1687	&& (REG_P (if_info->a) || rtx_equal_p (if_info->a, if_info->x))))
1688	{
1689	start_sequence ();
1690	target = noce_emit_store_flag (if_info,
1691	x: gen_reg_rtx (GET_MODE (if_info->x)),
1692	reversep, normalize: -1);
1693	if (target)
1694	target = expand_simple_binop (GET_MODE (if_info->x), AND,
1695	reversep ? if_info->a : if_info->b,
1696	target, if_info->x, 0,
1697	OPTAB_WIDEN);
1698
1699	if (target)
1700	{
1701	if (target != if_info->x)
1702	noce_emit_move_insn (x: if_info->x, y: target);
1703
1704	seq = end_ifcvt_sequence (if_info);
1705	if (!seq || !targetm.noce_conversion_profitable_p (seq, if_info))
1706	return false;
1707
1708	emit_insn_before_setloc (seq, if_info->jump,
1709	INSN_LOCATION (insn: if_info->insn_a));
1710	if_info->transform_name = "noce_try_store_flag_mask";
1711
1712	return true;
1713	}
1714
1715	end_sequence ();
1716	}
1717
1718	return false;
1719	}
1720
1721	/* Helper function for noce_try_cmove and noce_try_cmove_arith. */
1722
1723	static rtx
1724	noce_emit_cmove (struct noce_if_info *if_info, rtx x, enum rtx_code code,
1725	rtx cmp_a, rtx cmp_b, rtx vfalse, rtx vtrue, rtx cc_cmp,
1726	rtx rev_cc_cmp)
1727	{
1728	rtx target ATTRIBUTE_UNUSED;
1729	bool unsignedp ATTRIBUTE_UNUSED;
1730
1731	/* If earliest == jump, try to build the cmove insn directly.
1732	This is helpful when combine has created some complex condition
1733	(like for alpha's cmovlbs) that we can't hope to regenerate
1734	through the normal interface. */
1735
1736	if (if_info->cond_earliest == if_info->jump)
1737	{
1738	rtx cond = gen_rtx_fmt_ee (code, GET_MODE (if_info->cond), cmp_a, cmp_b);
1739	rtx if_then_else = gen_rtx_IF_THEN_ELSE (GET_MODE (x),
1740	cond, vtrue, vfalse);
1741	rtx set = gen_rtx_SET (x, if_then_else);
1742
1743	start_sequence ();
1744	rtx_insn *insn = emit_insn (set);
1745
1746	if (recog_memoized (insn) >= 0)
1747	{
1748	rtx_insn *seq = get_insns ();
1749	end_sequence ();
1750	emit_insn (seq);
1751
1752	return x;
1753	}
1754
1755	end_sequence ();
1756	}
1757
1758	unsignedp = (code == LTU || code == GEU
1759	|| code == LEU || code == GTU);
1760
1761	if (cc_cmp != NULL_RTX && rev_cc_cmp != NULL_RTX)
1762	target = emit_conditional_move (x, cc_cmp, rev_cc_cmp,
1763	vtrue, vfalse, GET_MODE (x));
1764	else
1765	{
1766	/* Don't even try if the comparison operands are weird
1767	except that the target supports cbranchcc4. */
1768	if (! general_operand (cmp_a, GET_MODE (cmp_a))
1769	|| ! general_operand (cmp_b, GET_MODE (cmp_b)))
1770	{
1771	if (!have_cbranchcc4
1772	|| GET_MODE_CLASS (GET_MODE (cmp_a)) != MODE_CC
1773	|| cmp_b != const0_rtx)
1774	return NULL_RTX;
1775	}
1776
1777	target = emit_conditional_move (x, { .code: code, .op0: cmp_a, .op1: cmp_b, VOIDmode },
1778	vtrue, vfalse, GET_MODE (x),
1779	unsignedp);
1780	}
1781
1782	if (target)
1783	return target;
1784
1785	/* We might be faced with a situation like:
1786
1787	x = (reg:M TARGET)
1788	vtrue = (subreg:M (reg:N VTRUE) BYTE)
1789	vfalse = (subreg:M (reg:N VFALSE) BYTE)
1790
1791	We can't do a conditional move in mode M, but it's possible that we
1792	could do a conditional move in mode N instead and take a subreg of
1793	the result.
1794
1795	If we can't create new pseudos, though, don't bother. */
1796	if (reload_completed)
1797	return NULL_RTX;
1798
1799	if (GET_CODE (vtrue) == SUBREG && GET_CODE (vfalse) == SUBREG)
1800	{
1801	rtx reg_vtrue = SUBREG_REG (vtrue);
1802	rtx reg_vfalse = SUBREG_REG (vfalse);
1803	poly_uint64 byte_vtrue = SUBREG_BYTE (vtrue);
1804	poly_uint64 byte_vfalse = SUBREG_BYTE (vfalse);
1805	rtx promoted_target;
1806
1807	if (GET_MODE (reg_vtrue) != GET_MODE (reg_vfalse)
1808	|| maybe_ne (a: byte_vtrue, b: byte_vfalse)
1809	|| (SUBREG_PROMOTED_VAR_P (vtrue)
1810	!= SUBREG_PROMOTED_VAR_P (vfalse))
1811	|| (SUBREG_PROMOTED_GET (vtrue)
1812	!= SUBREG_PROMOTED_GET (vfalse)))
1813	return NULL_RTX;
1814
1815	promoted_target = gen_reg_rtx (GET_MODE (reg_vtrue));
1816
1817	target = emit_conditional_move (promoted_target,
1818	{ .code: code, .op0: cmp_a, .op1: cmp_b, VOIDmode },
1819	reg_vtrue, reg_vfalse,
1820	GET_MODE (reg_vtrue), unsignedp);
1821	/* Nope, couldn't do it in that mode either. */
1822	if (!target)
1823	return NULL_RTX;
1824
1825	target = gen_rtx_SUBREG (GET_MODE (vtrue), promoted_target, byte_vtrue);
1826	SUBREG_PROMOTED_VAR_P (target) = SUBREG_PROMOTED_VAR_P (vtrue);
1827	SUBREG_PROMOTED_SET (target, SUBREG_PROMOTED_GET (vtrue));
1828	emit_move_insn (x, target);
1829	return x;
1830	}
1831	else
1832	return NULL_RTX;
1833	}
1834
1835	/* Emit a conditional zero, returning TARGET or NULL_RTX upon failure.
1836	IF_INFO describes the if-conversion scenario under consideration.
1837	CZERO_CODE selects the condition (EQ/NE).
1838	NON_ZERO_OP is the nonzero operand of the conditional move
1839	TARGET is the desired output register. */
1840
1841	static rtx
1842	noce_emit_czero (struct noce_if_info *if_info, enum rtx_code czero_code,
1843	rtx non_zero_op, rtx target)
1844	{
1845	machine_mode mode = GET_MODE (target);
1846	rtx cond_op0 = XEXP (if_info->cond, 0);
1847	rtx czero_cond
1848	= gen_rtx_fmt_ee (czero_code, GET_MODE (cond_op0), cond_op0, const0_rtx);
1849	rtx if_then_else
1850	= gen_rtx_IF_THEN_ELSE (mode, czero_cond, const0_rtx, non_zero_op);
1851	rtx set = gen_rtx_SET (target, if_then_else);
1852
1853	rtx_insn *insn = make_insn_raw (set);
1854
1855	if (recog_memoized (insn) >= 0)
1856	{
1857	add_insn (insn);
1858	return target;
1859	}
1860
1861	return NULL_RTX;
1862	}
1863
1864	/* Try only simple constants and registers here. More complex cases
1865	are handled in noce_try_cmove_arith after noce_try_store_flag_arith
1866	has had a go at it. */
1867
1868	static bool
1869	noce_try_cmove (struct noce_if_info *if_info)
1870	{
1871	enum rtx_code code;
1872	rtx target;
1873	rtx_insn *seq;
1874
1875	if (!noce_simple_bbs (if_info))
1876	return false;
1877
1878	if ((CONSTANT_P (if_info->a) || register_operand (if_info->a, VOIDmode))
1879	&& (CONSTANT_P (if_info->b) || register_operand (if_info->b, VOIDmode)))
1880	{
1881	start_sequence ();
1882
1883	code = GET_CODE (if_info->cond);
1884	target = noce_emit_cmove (if_info, x: if_info->x, code,
1885	XEXP (if_info->cond, 0),
1886	XEXP (if_info->cond, 1),
1887	vfalse: if_info->a, vtrue: if_info->b);
1888
1889	if (target)
1890	{
1891	if (target != if_info->x)
1892	noce_emit_move_insn (x: if_info->x, y: target);
1893
1894	seq = end_ifcvt_sequence (if_info);
1895	if (!seq || !targetm.noce_conversion_profitable_p (seq, if_info))
1896	return false;
1897
1898	emit_insn_before_setloc (seq, if_info->jump,
1899	INSN_LOCATION (insn: if_info->insn_a));
1900	if_info->transform_name = "noce_try_cmove";
1901
1902	return true;
1903	}
1904	/* If both a and b are constants try a last-ditch transformation:
1905	if (test) x = a; else x = b;
1906	=> x = (-(test != 0) & (b - a)) + a;
1907	Try this only if the target-specific expansion above has failed.
1908	The target-specific expander may want to generate sequences that
1909	we don't know about, so give them a chance before trying this
1910	approach. */
1911	else if (!targetm.have_conditional_execution ()
1912	&& CONST_INT_P (if_info->a) && CONST_INT_P (if_info->b))
1913	{
1914	machine_mode mode = GET_MODE (if_info->x);
1915	HOST_WIDE_INT ifalse = INTVAL (if_info->a);
1916	HOST_WIDE_INT itrue = INTVAL (if_info->b);
1917	rtx target = noce_emit_store_flag (if_info, x: if_info->x, reversep: false, normalize: -1);
1918	if (!target)
1919	{
1920	end_sequence ();
1921	return false;
1922	}
1923
1924	HOST_WIDE_INT diff = (unsigned HOST_WIDE_INT) itrue - ifalse;
1925	/* Make sure we can represent the difference
1926	between the two values. */
1927	if ((diff > 0)
1928	!= ((ifalse < 0) != (itrue < 0) ? ifalse < 0 : ifalse < itrue))
1929	{
1930	end_sequence ();
1931	return false;
1932	}
1933
1934	diff = trunc_int_for_mode (diff, mode);
1935	target = expand_simple_binop (mode, AND,
1936	target, gen_int_mode (diff, mode),
1937	if_info->x, 0, OPTAB_WIDEN);
1938	if (target)
1939	target = expand_simple_binop (mode, PLUS,
1940	target, gen_int_mode (ifalse, mode),
1941	if_info->x, 0, OPTAB_WIDEN);
1942	if (target)
1943	{
1944	if (target != if_info->x)
1945	noce_emit_move_insn (x: if_info->x, y: target);
1946
1947	seq = end_ifcvt_sequence (if_info);
1948	if (!seq || !targetm.noce_conversion_profitable_p (seq, if_info))
1949	return false;
1950
1951	emit_insn_before_setloc (seq, if_info->jump,
1952	INSN_LOCATION (insn: if_info->insn_a));
1953	if_info->transform_name = "noce_try_cmove";
1954	return true;
1955	}
1956	else
1957	{
1958	end_sequence ();
1959	return false;
1960	}
1961	}
1962	else
1963	end_sequence ();
1964	}
1965
1966	return false;
1967	}
1968
1969	/* Return true if X contains a conditional code mode rtx. */
1970
1971	static bool
1972	contains_ccmode_rtx_p (rtx x)
1973	{
1974	subrtx_iterator::array_type array;
1975	FOR_EACH_SUBRTX (iter, array, x, ALL)
1976	if (GET_MODE_CLASS (GET_MODE (*iter)) == MODE_CC)
1977	return true;
1978
1979	return false;
1980	}
1981
1982	/* Helper for bb_valid_for_noce_process_p. Validate that
1983	the rtx insn INSN is a single set that does not set
1984	the conditional register CC and is in general valid for
1985	if-conversion. */
1986
1987	static bool
1988	insn_valid_noce_process_p (rtx_insn *insn, rtx cc)
1989	{
1990	if (!insn
1991	|| !NONJUMP_INSN_P (insn)
1992	|| (cc && set_of (cc, insn)))
1993	return false;
1994
1995	rtx sset = single_set (insn);
1996
1997	/* Currently support only simple single sets in test_bb. */
1998	if (!sset
1999	|| !noce_operand_ok (SET_DEST (sset))
2000	|| contains_ccmode_rtx_p (SET_DEST (sset))
2001	|| !noce_operand_ok (SET_SRC (sset)))
2002	return false;
2003
2004	return true;
2005	}
2006
2007
2008	/* Return true iff the registers that the insns in BB_A set do not get
2009	used in BB_B. If TO_RENAME is non-NULL then it is a location that will be
2010	renamed later by the caller and so conflicts on it should be ignored
2011	in this function. */
2012
2013	static bool
2014	bbs_ok_for_cmove_arith (basic_block bb_a, basic_block bb_b, rtx to_rename)
2015	{
2016	rtx_insn *a_insn;
2017	bitmap bba_sets = BITMAP_ALLOC (obstack: &reg_obstack);
2018
2019	df_ref def;
2020	df_ref use;
2021
2022	FOR_BB_INSNS (bb_a, a_insn)
2023	{
2024	if (!active_insn_p (a_insn))
2025	continue;
2026
2027	rtx sset_a = single_set (insn: a_insn);
2028
2029	if (!sset_a)
2030	{
2031	BITMAP_FREE (bba_sets);
2032	return false;
2033	}
2034	/* Record all registers that BB_A sets. */
2035	FOR_EACH_INSN_DEF (def, a_insn)
2036	if (!(to_rename && DF_REF_REG (def) == to_rename))
2037	bitmap_set_bit (bba_sets, DF_REF_REGNO (def));
2038	}
2039
2040	rtx_insn *b_insn;
2041
2042	FOR_BB_INSNS (bb_b, b_insn)
2043	{
2044	if (!active_insn_p (b_insn))
2045	continue;
2046
2047	rtx sset_b = single_set (insn: b_insn);
2048
2049	if (!sset_b)
2050	{
2051	BITMAP_FREE (bba_sets);
2052	return false;
2053	}
2054
2055	/* Make sure this is a REG and not some instance
2056	of ZERO_EXTRACT or non-paradoxical SUBREG or other dangerous stuff.
2057	If we have a memory destination then we have a pair of simple
2058	basic blocks performing an operation of the form [addr] = c ? a : b.
2059	bb_valid_for_noce_process_p will have ensured that these are
2060	the only stores present. In that case [addr] should be the location
2061	to be renamed. Assert that the callers set this up properly. */
2062	if (MEM_P (SET_DEST (sset_b)))
2063	gcc_assert (rtx_equal_p (SET_DEST (sset_b), to_rename));
2064	else if (!REG_P (SET_DEST (sset_b))
2065	&& !paradoxical_subreg_p (SET_DEST (sset_b)))
2066	{
2067	BITMAP_FREE (bba_sets);
2068	return false;
2069	}
2070
2071	/* If the insn uses a reg set in BB_A return false. */
2072	FOR_EACH_INSN_USE (use, b_insn)
2073	{
2074	if (bitmap_bit_p (bba_sets, DF_REF_REGNO (use)))
2075	{
2076	BITMAP_FREE (bba_sets);
2077	return false;
2078	}
2079	}
2080
2081	}
2082
2083	BITMAP_FREE (bba_sets);
2084	return true;
2085	}
2086
2087	/* Emit copies of all the active instructions in BB except the last.
2088	This is a helper for noce_try_cmove_arith. */
2089
2090	static void
2091	noce_emit_all_but_last (basic_block bb)
2092	{
2093	rtx_insn *last = last_active_insn (bb, skip_use_p: false);
2094	rtx_insn *insn;
2095	FOR_BB_INSNS (bb, insn)
2096	{
2097	if (insn != last && active_insn_p (insn))
2098	{
2099	rtx_insn *to_emit = as_a <rtx_insn *> (p: copy_rtx (insn));
2100
2101	emit_insn (PATTERN (insn: to_emit));
2102	}
2103	}
2104	}
2105
2106	/* Helper for noce_try_cmove_arith. Emit the pattern TO_EMIT and return
2107	the resulting insn or NULL if it's not a valid insn. */
2108
2109	static rtx_insn *
2110	noce_emit_insn (rtx to_emit)
2111	{
2112	gcc_assert (to_emit);
2113	rtx_insn *insn = emit_insn (to_emit);
2114
2115	if (recog_memoized (insn) < 0)
2116	return NULL;
2117
2118	return insn;
2119	}
2120
2121	/* Helper for noce_try_cmove_arith. Emit a copy of the insns up to
2122	and including the penultimate one in BB if it is not simple
2123	(as indicated by SIMPLE). Then emit LAST_INSN as the last
2124	insn in the block. The reason for that is that LAST_INSN may
2125	have been modified by the preparation in noce_try_cmove_arith. */
2126
2127	static bool
2128	noce_emit_bb (rtx last_insn, basic_block bb, bool simple)
2129	{
2130	if (bb && !simple)
2131	noce_emit_all_but_last (bb);
2132
2133	if (last_insn && !noce_emit_insn (to_emit: last_insn))
2134	return false;
2135
2136	return true;
2137	}
2138
2139	/* Try more complex cases involving conditional_move. */
2140
2141	static bool
2142	noce_try_cmove_arith (struct noce_if_info *if_info)
2143	{
2144	rtx a = if_info->a;
2145	rtx b = if_info->b;
2146	rtx x = if_info->x;
2147	rtx orig_a, orig_b;
2148	rtx_insn *insn_a, *insn_b;
2149	bool a_simple = if_info->then_simple;
2150	bool b_simple = if_info->else_simple;
2151	basic_block then_bb = if_info->then_bb;
2152	basic_block else_bb = if_info->else_bb;
2153	rtx target;
2154	bool is_mem = false;
2155	enum rtx_code code;
2156	rtx cond = if_info->cond;
2157	rtx_insn *ifcvt_seq;
2158
2159	/* A conditional move from two memory sources is equivalent to a
2160	conditional on their addresses followed by a load. Don't do this
2161	early because it'll screw alias analysis. Note that we've
2162	already checked for no side effects. */
2163	if (cse_not_expected
2164	&& MEM_P (a) && MEM_P (b)
2165	&& MEM_ADDR_SPACE (a) == MEM_ADDR_SPACE (b))
2166	{
2167	machine_mode address_mode = get_address_mode (mem: a);
2168
2169	a = XEXP (a, 0);
2170	b = XEXP (b, 0);
2171	x = gen_reg_rtx (address_mode);
2172	is_mem = true;
2173	}
2174
2175	/* ??? We could handle this if we knew that a load from A or B could
2176	not trap or fault. This is also true if we've already loaded
2177	from the address along the path from ENTRY. */
2178	else if (may_trap_or_fault_p (a) || may_trap_or_fault_p (b))
2179	return false;
2180
2181	/* if (test) x = a + b; else x = c - d;
2182	=> y = a + b;
2183	x = c - d;
2184	if (test)
2185	x = y;
2186	*/
2187
2188	code = GET_CODE (cond);
2189	insn_a = if_info->insn_a;
2190	insn_b = if_info->insn_b;
2191
2192	machine_mode x_mode = GET_MODE (x);
2193
2194	if (!can_conditionally_move_p (mode: x_mode))
2195	return false;
2196
2197	/* Possibly rearrange operands to make things come out more natural. */
2198	if (noce_reversed_cond_code (if_info) != UNKNOWN)
2199	{
2200	bool reversep = false;
2201	if (rtx_equal_p (b, x))
2202	reversep = true;
2203	else if (general_operand (b, GET_MODE (b)))
2204	reversep = true;
2205
2206	if (reversep)
2207	{
2208	if (if_info->rev_cond)
2209	{
2210	cond = if_info->rev_cond;
2211	code = GET_CODE (cond);
2212	}
2213	else
2214	code = reversed_comparison_code (cond, if_info->jump);
2215	std::swap (a&: a, b&: b);
2216	std::swap (a&: insn_a, b&: insn_b);
2217	std::swap (a&: a_simple, b&: b_simple);
2218	std::swap (a&: then_bb, b&: else_bb);
2219	}
2220	}
2221
2222	if (then_bb && else_bb
2223	&& (!bbs_ok_for_cmove_arith (bb_a: then_bb, bb_b: else_bb, to_rename: if_info->orig_x)
2224	|| !bbs_ok_for_cmove_arith (bb_a: else_bb, bb_b: then_bb, to_rename: if_info->orig_x)))
2225	return false;
2226
2227	start_sequence ();
2228
2229	/* If one of the blocks is empty then the corresponding B or A value
2230	came from the test block. The non-empty complex block that we will
2231	emit might clobber the register used by B or A, so move it to a pseudo
2232	first. */
2233
2234	rtx tmp_a = NULL_RTX;
2235	rtx tmp_b = NULL_RTX;
2236
2237	if (b_simple || !else_bb)
2238	tmp_b = gen_reg_rtx (x_mode);
2239
2240	if (a_simple || !then_bb)
2241	tmp_a = gen_reg_rtx (x_mode);
2242
2243	orig_a = a;
2244	orig_b = b;
2245
2246	rtx emit_a = NULL_RTX;
2247	rtx emit_b = NULL_RTX;
2248	rtx_insn *tmp_insn = NULL;
2249	bool modified_in_a = false;
2250	bool modified_in_b = false;
2251	/* If either operand is complex, load it into a register first.
2252	The best way to do this is to copy the original insn. In this
2253	way we preserve any clobbers etc that the insn may have had.
2254	This is of course not possible in the IS_MEM case. */
2255
2256	if (! general_operand (a, GET_MODE (a)) || tmp_a)
2257	{
2258
2259	if (is_mem)
2260	{
2261	rtx reg = gen_reg_rtx (GET_MODE (a));
2262	emit_a = gen_rtx_SET (reg, a);
2263	}
2264	else
2265	{
2266	if (insn_a)
2267	{
2268	a = tmp_a ? tmp_a : gen_reg_rtx (GET_MODE (a));
2269
2270	rtx_insn *copy_of_a = as_a <rtx_insn *> (p: copy_rtx (insn_a));
2271	rtx set = single_set (insn: copy_of_a);
2272	SET_DEST (set) = a;
2273
2274	emit_a = PATTERN (insn: copy_of_a);
2275	}
2276	else
2277	{
2278	rtx tmp_reg = tmp_a ? tmp_a : gen_reg_rtx (GET_MODE (a));
2279	emit_a = gen_rtx_SET (tmp_reg, a);
2280	a = tmp_reg;
2281	}
2282	}
2283	}
2284
2285	if (! general_operand (b, GET_MODE (b)) || tmp_b)
2286	{
2287	if (is_mem)
2288	{
2289	rtx reg = gen_reg_rtx (GET_MODE (b));
2290	emit_b = gen_rtx_SET (reg, b);
2291	}
2292	else
2293	{
2294	if (insn_b)
2295	{
2296	b = tmp_b ? tmp_b : gen_reg_rtx (GET_MODE (b));
2297	rtx_insn *copy_of_b = as_a <rtx_insn *> (p: copy_rtx (insn_b));
2298	rtx set = single_set (insn: copy_of_b);
2299
2300	SET_DEST (set) = b;
2301	emit_b = PATTERN (insn: copy_of_b);
2302	}
2303	else
2304	{
2305	rtx tmp_reg = tmp_b ? tmp_b : gen_reg_rtx (GET_MODE (b));
2306	emit_b = gen_rtx_SET (tmp_reg, b);
2307	b = tmp_reg;
2308	}
2309	}
2310	}
2311
2312	modified_in_a = emit_a != NULL_RTX && modified_in_p (orig_b, emit_a);
2313	if (tmp_b && then_bb)
2314	{
2315	FOR_BB_INSNS (then_bb, tmp_insn)
2316	/* Don't check inside insn_a. We will have changed it to emit_a
2317	with a destination that doesn't conflict. */
2318	if (!(insn_a && tmp_insn == insn_a)
2319	&& modified_in_p (orig_b, tmp_insn))
2320	{
2321	modified_in_a = true;
2322	break;
2323	}
2324
2325	}
2326
2327	modified_in_b = emit_b != NULL_RTX && modified_in_p (orig_a, emit_b);
2328	if (tmp_a && else_bb)
2329	{
2330	FOR_BB_INSNS (else_bb, tmp_insn)
2331	/* Don't check inside insn_b. We will have changed it to emit_b
2332	with a destination that doesn't conflict. */
2333	if (!(insn_b && tmp_insn == insn_b)
2334	&& modified_in_p (orig_a, tmp_insn))
2335	{
2336	modified_in_b = true;
2337	break;
2338	}
2339	}
2340
2341	/* If insn to set up A clobbers any registers B depends on, try to
2342	swap insn that sets up A with the one that sets up B. If even
2343	that doesn't help, punt. */
2344	if (modified_in_a && !modified_in_b)
2345	{
2346	if (!noce_emit_bb (last_insn: emit_b, bb: else_bb, simple: b_simple))
2347	goto end_seq_and_fail;
2348
2349	if (!noce_emit_bb (last_insn: emit_a, bb: then_bb, simple: a_simple))
2350	goto end_seq_and_fail;
2351	}
2352	else if (!modified_in_a)
2353	{
2354	if (!noce_emit_bb (last_insn: emit_a, bb: then_bb, simple: a_simple))
2355	goto end_seq_and_fail;
2356
2357	if (!noce_emit_bb (last_insn: emit_b, bb: else_bb, simple: b_simple))
2358	goto end_seq_and_fail;
2359	}
2360	else
2361	goto end_seq_and_fail;
2362
2363	target = noce_emit_cmove (if_info, x, code, XEXP (cond, 0), XEXP (cond, 1),
2364	vfalse: a, vtrue: b);
2365
2366	if (! target)
2367	goto end_seq_and_fail;
2368
2369	/* If we're handling a memory for above, emit the load now. */
2370	if (is_mem)
2371	{
2372	rtx mem = gen_rtx_MEM (GET_MODE (if_info->x), target);
2373
2374	/* Copy over flags as appropriate. */
2375	if (MEM_VOLATILE_P (if_info->a) || MEM_VOLATILE_P (if_info->b))
2376	MEM_VOLATILE_P (mem) = 1;
2377	if (MEM_ALIAS_SET (if_info->a) == MEM_ALIAS_SET (if_info->b))
2378	set_mem_alias_set (mem, MEM_ALIAS_SET (if_info->a));
2379	set_mem_align (mem,
2380	MIN (MEM_ALIGN (if_info->a), MEM_ALIGN (if_info->b)));
2381
2382	gcc_assert (MEM_ADDR_SPACE (if_info->a) == MEM_ADDR_SPACE (if_info->b));
2383	set_mem_addr_space (mem, MEM_ADDR_SPACE (if_info->a));
2384
2385	noce_emit_move_insn (x: if_info->x, y: mem);
2386	}
2387	else if (target != x)
2388	noce_emit_move_insn (x, y: target);
2389
2390	ifcvt_seq = end_ifcvt_sequence (if_info);
2391	if (!ifcvt_seq || !targetm.noce_conversion_profitable_p (ifcvt_seq, if_info))
2392	return false;
2393
2394	emit_insn_before_setloc (ifcvt_seq, if_info->jump,
2395	INSN_LOCATION (insn: if_info->insn_a));
2396	if_info->transform_name = "noce_try_cmove_arith";
2397	return true;
2398
2399	end_seq_and_fail:
2400	end_sequence ();
2401	return false;
2402	}
2403
2404	/* For most cases, the simplified condition we found is the best
2405	choice, but this is not the case for the min/max/abs transforms.
2406	For these we wish to know that it is A or B in the condition. */
2407
2408	static rtx
2409	noce_get_alt_condition (struct noce_if_info *if_info, rtx target,
2410	rtx_insn **earliest)
2411	{
2412	rtx cond, set;
2413	rtx_insn *insn;
2414	bool reverse;
2415
2416	/* If target is already mentioned in the known condition, return it. */
2417	if (reg_mentioned_p (target, if_info->cond))
2418	{
2419	*earliest = if_info->cond_earliest;
2420	return if_info->cond;
2421	}
2422
2423	set = pc_set (if_info->jump);
2424	cond = XEXP (SET_SRC (set), 0);
2425	reverse
2426	= GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
2427	&& label_ref_label (XEXP (SET_SRC (set), 2)) == JUMP_LABEL (if_info->jump);
2428	if (if_info->then_else_reversed)
2429	reverse = !reverse;
2430
2431	/* If we're looking for a constant, try to make the conditional
2432	have that constant in it. There are two reasons why it may
2433	not have the constant we want:
2434
2435	1. GCC may have needed to put the constant in a register, because
2436	the target can't compare directly against that constant. For
2437	this case, we look for a SET immediately before the comparison
2438	that puts a constant in that register.
2439
2440	2. GCC may have canonicalized the conditional, for example
2441	replacing "if x < 4" with "if x <= 3". We can undo that (or
2442	make equivalent types of changes) to get the constants we need
2443	if they're off by one in the right direction. */
2444
2445	if (CONST_INT_P (target))
2446	{
2447	enum rtx_code code = GET_CODE (if_info->cond);
2448	rtx op_a = XEXP (if_info->cond, 0);
2449	rtx op_b = XEXP (if_info->cond, 1);
2450	rtx_insn *prev_insn;
2451
2452	/* First, look to see if we put a constant in a register. */
2453	prev_insn = prev_nonnote_nondebug_insn (if_info->cond_earliest);
2454	if (prev_insn
2455	&& BLOCK_FOR_INSN (insn: prev_insn)
2456	== BLOCK_FOR_INSN (insn: if_info->cond_earliest)
2457	&& INSN_P (prev_insn)
2458	&& GET_CODE (PATTERN (prev_insn)) == SET)
2459	{
2460	rtx src = find_reg_equal_equiv_note (prev_insn);
2461	if (!src)
2462	src = SET_SRC (PATTERN (prev_insn));
2463	if (CONST_INT_P (src))
2464	{
2465	if (rtx_equal_p (op_a, SET_DEST (PATTERN (prev_insn))))
2466	op_a = src;
2467	else if (rtx_equal_p (op_b, SET_DEST (PATTERN (prev_insn))))
2468	op_b = src;
2469
2470	if (CONST_INT_P (op_a))
2471	{
2472	std::swap (a&: op_a, b&: op_b);
2473	code = swap_condition (code);
2474	}
2475	}
2476	}
2477
2478	/* Now, look to see if we can get the right constant by
2479	adjusting the conditional. */
2480	if (CONST_INT_P (op_b))
2481	{
2482	HOST_WIDE_INT desired_val = INTVAL (target);
2483	HOST_WIDE_INT actual_val = INTVAL (op_b);
2484
2485	switch (code)
2486	{
2487	case LT:
2488	if (desired_val != HOST_WIDE_INT_MAX
2489	&& actual_val == desired_val + 1)
2490	{
2491	code = LE;
2492	op_b = GEN_INT (desired_val);
2493	}
2494	break;
2495	case LE:
2496	if (desired_val != HOST_WIDE_INT_MIN
2497	&& actual_val == desired_val - 1)
2498	{
2499	code = LT;
2500	op_b = GEN_INT (desired_val);
2501	}
2502	break;
2503	case GT:
2504	if (desired_val != HOST_WIDE_INT_MIN
2505	&& actual_val == desired_val - 1)
2506	{
2507	code = GE;
2508	op_b = GEN_INT (desired_val);
2509	}
2510	break;
2511	case GE:
2512	if (desired_val != HOST_WIDE_INT_MAX
2513	&& actual_val == desired_val + 1)
2514	{
2515	code = GT;
2516	op_b = GEN_INT (desired_val);
2517	}
2518	break;
2519	default:
2520	break;
2521	}
2522	}
2523
2524	/* If we made any changes, generate a new conditional that is
2525	equivalent to what we started with, but has the right
2526	constants in it. */
2527	if (code != GET_CODE (if_info->cond)
2528	|| op_a != XEXP (if_info->cond, 0)
2529	|| op_b != XEXP (if_info->cond, 1))
2530	{
2531	cond = gen_rtx_fmt_ee (code, GET_MODE (cond), op_a, op_b);
2532	*earliest = if_info->cond_earliest;
2533	return cond;
2534	}
2535	}
2536
2537	cond = canonicalize_condition (if_info->jump, cond, reverse,
2538	earliest, target, have_cbranchcc4, true);
2539	if (! cond || ! reg_mentioned_p (target, cond))
2540	return NULL;
2541
2542	/* We almost certainly searched back to a different place.
2543	Need to re-verify correct lifetimes. */
2544
2545	/* X may not be mentioned in the range (cond_earliest, jump]. */
2546	for (insn = if_info->jump; insn != *earliest; insn = PREV_INSN (insn))
2547	if (INSN_P (insn) && reg_overlap_mentioned_p (if_info->x, PATTERN (insn)))
2548	return NULL;
2549
2550	/* A and B may not be modified in the range [cond_earliest, jump). */
2551	for (insn = *earliest; insn != if_info->jump; insn = NEXT_INSN (insn))
2552	if (INSN_P (insn)
2553	&& (modified_in_p (if_info->a, insn)
2554	|| modified_in_p (if_info->b, insn)))
2555	return NULL;
2556
2557	return cond;
2558	}
2559
2560	/* Convert "if (a < b) x = a; else x = b;" to "x = min(a, b);", etc. */
2561
2562	static bool
2563	noce_try_minmax (struct noce_if_info *if_info)
2564	{
2565	rtx cond, target;
2566	rtx_insn *earliest, *seq;
2567	enum rtx_code code, op;
2568	bool unsignedp;
2569
2570	if (!noce_simple_bbs (if_info))
2571	return false;
2572
2573	/* ??? Reject modes with NaNs or signed zeros since we don't know how
2574	they will be resolved with an SMIN/SMAX. It wouldn't be too hard
2575	to get the target to tell us... */
2576	if (HONOR_SIGNED_ZEROS (if_info->x)
2577	|| HONOR_NANS (if_info->x))
2578	return false;
2579
2580	cond = noce_get_alt_condition (if_info, target: if_info->a, earliest: &earliest);
2581	if (!cond)
2582	return false;
2583
2584	/* Verify the condition is of the form we expect, and canonicalize
2585	the comparison code. */
2586	code = GET_CODE (cond);
2587	if (rtx_equal_p (XEXP (cond, 0), if_info->a))
2588	{
2589	if (! rtx_equal_p (XEXP (cond, 1), if_info->b))
2590	return false;
2591	}
2592	else if (rtx_equal_p (XEXP (cond, 1), if_info->a))
2593	{
2594	if (! rtx_equal_p (XEXP (cond, 0), if_info->b))
2595	return false;
2596	code = swap_condition (code);
2597	}
2598	else
2599	return false;
2600
2601	/* Determine what sort of operation this is. Note that the code is for
2602	a taken branch, so the code->operation mapping appears backwards. */
2603	switch (code)
2604	{
2605	case LT:
2606	case LE:
2607	case UNLT:
2608	case UNLE:
2609	op = SMAX;
2610	unsignedp = false;
2611	break;
2612	case GT:
2613	case GE:
2614	case UNGT:
2615	case UNGE:
2616	op = SMIN;
2617	unsignedp = false;
2618	break;
2619	case LTU:
2620	case LEU:
2621	op = UMAX;
2622	unsignedp = true;
2623	break;
2624	case GTU:
2625	case GEU:
2626	op = UMIN;
2627	unsignedp = true;
2628	break;
2629	default:
2630	return false;
2631	}
2632
2633	start_sequence ();
2634
2635	target = expand_simple_binop (GET_MODE (if_info->x), op,
2636	if_info->a, if_info->b,
2637	if_info->x, unsignedp, OPTAB_WIDEN);
2638	if (! target)
2639	{
2640	end_sequence ();
2641	return false;
2642	}
2643	if (target != if_info->x)
2644	noce_emit_move_insn (x: if_info->x, y: target);
2645
2646	seq = end_ifcvt_sequence (if_info);
2647	if (!seq)
2648	return false;
2649
2650	emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATION (insn: if_info->insn_a));
2651	if_info->cond = cond;
2652	if_info->cond_earliest = earliest;
2653	if_info->rev_cond = NULL_RTX;
2654	if_info->transform_name = "noce_try_minmax";
2655
2656	return true;
2657	}
2658
2659	/* Convert "if (a < 0) x = -a; else x = a;" to "x = abs(a);",
2660	"if (a < 0) x = ~a; else x = a;" to "x = one_cmpl_abs(a);",
2661	etc. */
2662
2663	static bool
2664	noce_try_abs (struct noce_if_info *if_info)
2665	{
2666	rtx cond, target, a, b, c;
2667	rtx_insn *earliest, *seq;
2668	bool negate;
2669	bool one_cmpl = false;
2670
2671	if (!noce_simple_bbs (if_info))
2672	return false;
2673
2674	/* Reject modes with signed zeros. */
2675	if (HONOR_SIGNED_ZEROS (if_info->x))
2676	return false;
2677
2678	/* Recognize A and B as constituting an ABS or NABS. The canonical
2679	form is a branch around the negation, taken when the object is the
2680	first operand of a comparison against 0 that evaluates to true. */
2681	a = if_info->a;
2682	b = if_info->b;
2683	if (GET_CODE (a) == NEG && rtx_equal_p (XEXP (a, 0), b))
2684	negate = false;
2685	else if (GET_CODE (b) == NEG && rtx_equal_p (XEXP (b, 0), a))
2686	{
2687	std::swap (a&: a, b&: b);
2688	negate = true;
2689	}
2690	else if (GET_CODE (a) == NOT && rtx_equal_p (XEXP (a, 0), b))
2691	{
2692	negate = false;
2693	one_cmpl = true;
2694	}
2695	else if (GET_CODE (b) == NOT && rtx_equal_p (XEXP (b, 0), a))
2696	{
2697	std::swap (a&: a, b&: b);
2698	negate = true;
2699	one_cmpl = true;
2700	}
2701	else
2702	return false;
2703
2704	cond = noce_get_alt_condition (if_info, target: b, earliest: &earliest);
2705	if (!cond)
2706	return false;
2707
2708	/* Verify the condition is of the form we expect. */
2709	if (rtx_equal_p (XEXP (cond, 0), b))
2710	c = XEXP (cond, 1);
2711	else if (rtx_equal_p (XEXP (cond, 1), b))
2712	{
2713	c = XEXP (cond, 0);
2714	negate = !negate;
2715	}
2716	else
2717	return false;
2718
2719	/* Verify that C is zero. Search one step backward for a
2720	REG_EQUAL note or a simple source if necessary. */
2721	if (REG_P (c))
2722	{
2723	rtx set;
2724	rtx_insn *insn = prev_nonnote_nondebug_insn (earliest);
2725	if (insn
2726	&& BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (insn: earliest)
2727	&& (set = single_set (insn))
2728	&& rtx_equal_p (SET_DEST (set), c))
2729	{
2730	rtx note = find_reg_equal_equiv_note (insn);
2731	if (note)
2732	c = XEXP (note, 0);
2733	else
2734	c = SET_SRC (set);
2735	}
2736	else
2737	return false;
2738	}
2739	if (MEM_P (c)
2740	&& GET_CODE (XEXP (c, 0)) == SYMBOL_REF
2741	&& CONSTANT_POOL_ADDRESS_P (XEXP (c, 0)))
2742	c = get_pool_constant (XEXP (c, 0));
2743
2744	/* Work around funny ideas get_condition has wrt canonicalization.
2745	Note that these rtx constants are known to be CONST_INT, and
2746	therefore imply integer comparisons.
2747	The one_cmpl case is more complicated, as we want to handle
2748	only x < 0 ? ~x : x or x >= 0 ? x : ~x to one_cmpl_abs (x)
2749	and x < 0 ? x : ~x or x >= 0 ? ~x : x to ~one_cmpl_abs (x),
2750	but not other cases (x > -1 is equivalent of x >= 0). */
2751	if (c == constm1_rtx && GET_CODE (cond) == GT)
2752	;
2753	else if (c == const1_rtx && GET_CODE (cond) == LT)
2754	{
2755	if (one_cmpl)
2756	return false;
2757	}
2758	else if (c == CONST0_RTX (GET_MODE (b)))
2759	{
2760	if (one_cmpl
2761	&& GET_CODE (cond) != GE
2762	&& GET_CODE (cond) != LT)
2763	return false;
2764	}
2765	else
2766	return false;
2767
2768	/* Determine what sort of operation this is. */
2769	switch (GET_CODE (cond))
2770	{
2771	case LT:
2772	case LE:
2773	case UNLT:
2774	case UNLE:
2775	negate = !negate;
2776	break;
2777	case GT:
2778	case GE:
2779	case UNGT:
2780	case UNGE:
2781	break;
2782	default:
2783	return false;
2784	}
2785
2786	start_sequence ();
2787	if (one_cmpl)
2788	target = expand_one_cmpl_abs_nojump (GET_MODE (if_info->x), b,
2789	if_info->x);
2790	else
2791	target = expand_abs_nojump (GET_MODE (if_info->x), b, if_info->x, 1);
2792
2793	/* ??? It's a quandary whether cmove would be better here, especially
2794	for integers. Perhaps combine will clean things up. */
2795	if (target && negate)
2796	{
2797	if (one_cmpl)
2798	target = expand_simple_unop (GET_MODE (target), NOT, target,
2799	if_info->x, 0);
2800	else
2801	target = expand_simple_unop (GET_MODE (target), NEG, target,
2802	if_info->x, 0);
2803	}
2804
2805	if (! target)
2806	{
2807	end_sequence ();
2808	return false;
2809	}
2810
2811	if (target != if_info->x)
2812	noce_emit_move_insn (x: if_info->x, y: target);
2813
2814	seq = end_ifcvt_sequence (if_info);
2815	if (!seq)
2816	return false;
2817
2818	emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATION (insn: if_info->insn_a));
2819	if_info->cond = cond;
2820	if_info->cond_earliest = earliest;
2821	if_info->rev_cond = NULL_RTX;
2822	if_info->transform_name = "noce_try_abs";
2823
2824	return true;
2825	}
2826
2827	/* Convert "if (m < 0) x = b; else x = 0;" to "x = (m >> C) & b;". */
2828
2829	static bool
2830	noce_try_sign_mask (struct noce_if_info *if_info)
2831	{
2832	rtx cond, t, m, c;
2833	rtx_insn *seq;
2834	machine_mode mode;
2835	enum rtx_code code;
2836	bool t_unconditional;
2837
2838	if (!noce_simple_bbs (if_info))
2839	return false;
2840
2841	cond = if_info->cond;
2842	code = GET_CODE (cond);
2843	m = XEXP (cond, 0);
2844	c = XEXP (cond, 1);
2845
2846	t = NULL_RTX;
2847	if (if_info->a == const0_rtx)
2848	{
2849	if ((code == LT && c == const0_rtx)
2850	|| (code == LE && c == constm1_rtx))
2851	t = if_info->b;
2852	}
2853	else if (if_info->b == const0_rtx)
2854	{
2855	if ((code == GE && c == const0_rtx)
2856	|| (code == GT && c == constm1_rtx))
2857	t = if_info->a;
2858	}
2859
2860	if (! t || side_effects_p (t))
2861	return false;
2862
2863	/* We currently don't handle different modes. */
2864	mode = GET_MODE (t);
2865	if (GET_MODE (m) != mode)
2866	return false;
2867
2868	/* This is only profitable if T is unconditionally executed/evaluated in the
2869	original insn sequence or T is cheap and can't trap or fault. The former
2870	happens if B is the non-zero (T) value and if INSN_B was taken from
2871	TEST_BB, or there was no INSN_B which can happen for e.g. conditional
2872	stores to memory. For the cost computation use the block TEST_BB where
2873	the evaluation will end up after the transformation. */
2874	t_unconditional
2875	= (t == if_info->b
2876	&& (if_info->insn_b == NULL_RTX
2877	|| BLOCK_FOR_INSN (insn: if_info->insn_b) == if_info->test_bb));
2878	if (!(t_unconditional
2879	|| ((set_src_cost (x: t, mode, speed_p: if_info->speed_p)
2880	< COSTS_N_INSNS (2))
2881	&& !may_trap_or_fault_p (t))))
2882	return false;
2883
2884	if (!noce_can_force_operand (x: t))
2885	return false;
2886
2887	start_sequence ();
2888	/* Use emit_store_flag to generate "m < 0 ? -1 : 0" instead of expanding
2889	"(signed) m >> 31" directly. This benefits targets with specialized
2890	insns to obtain the signmask, but still uses ashr_optab otherwise. */
2891	m = emit_store_flag (gen_reg_rtx (mode), LT, m, const0_rtx, mode, 0, -1);
2892	t = m ? expand_binop (mode, and_optab, m, t, NULL_RTX, 0, OPTAB_DIRECT)
2893	: NULL_RTX;
2894
2895	if (!t)
2896	{
2897	end_sequence ();
2898	return false;
2899	}
2900
2901	noce_emit_move_insn (x: if_info->x, y: t);
2902
2903	seq = end_ifcvt_sequence (if_info);
2904	if (!seq)
2905	return false;
2906
2907	emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATION (insn: if_info->insn_a));
2908	if_info->transform_name = "noce_try_sign_mask";
2909
2910	return true;
2911	}
2912
2913	/* Check if OP is supported by conditional zero based if conversion,
2914	returning TRUE if satisfied otherwise FALSE.
2915
2916	OP is the operation to check. */
2917
2918	static bool
2919	noce_cond_zero_binary_op_supported (rtx op)
2920	{
2921	enum rtx_code opcode = GET_CODE (op);
2922
2923	if (opcode == PLUS || opcode == MINUS || opcode == IOR || opcode == XOR
2924	|| opcode == ASHIFT || opcode == ASHIFTRT || opcode == LSHIFTRT
2925	|| opcode == ROTATE || opcode == ROTATERT || opcode == AND)
2926	return true;
2927
2928	return false;
2929	}
2930
2931	/* Helper function to return REG itself,
2932	otherwise NULL_RTX for other RTX_CODE. */
2933
2934	static rtx
2935	get_base_reg (rtx exp)
2936	{
2937	if (REG_P (exp))
2938	return exp;
2939
2940	return NULL_RTX;
2941	}
2942
2943	/* Check if IF-BB and THEN-BB satisfy the condition for conditional zero
2944	based if conversion, returning TRUE if satisfied otherwise FALSE.
2945
2946	IF_INFO describes the if-conversion scenario under consideration.
2947	COMMON_PTR points to the common REG of canonicalized IF_INFO->A and
2948	IF_INFO->B.
2949	CZERO_CODE_PTR points to the comparison code to use in czero RTX.
2950	A_PTR points to the A expression of canonicalized IF_INFO->A.
2951	TO_REPLACE points to the RTX to be replaced by czero RTX destnation. */
2952
2953	static bool
2954	noce_bbs_ok_for_cond_zero_arith (struct noce_if_info *if_info, rtx *common_ptr,
2955	rtx *bin_exp_ptr,
2956	enum rtx_code *czero_code_ptr, rtx *a_ptr,
2957	rtx **to_replace)
2958	{
2959	rtx common = NULL_RTX;
2960	rtx cond = if_info->cond;
2961	rtx a = copy_rtx (if_info->a);
2962	rtx b = copy_rtx (if_info->b);
2963	rtx bin_op1 = NULL_RTX;
2964	enum rtx_code czero_code = UNKNOWN;
2965	bool reverse = false;
2966	rtx op0, op1, bin_exp;
2967
2968	if (!noce_simple_bbs (if_info))
2969	return false;
2970
2971	/* COND must be EQ or NE comparision of a reg and 0. */
2972	if (GET_CODE (cond) != NE && GET_CODE (cond) != EQ)
2973	return false;
2974	if (!REG_P (XEXP (cond, 0)) || !rtx_equal_p (XEXP (cond, 1), const0_rtx))
2975	return false;
2976
2977	/* Canonicalize x = y : (y op z) to x = (y op z) : y. */
2978	if (REG_P (a) && noce_cond_zero_binary_op_supported (op: b))
2979	{
2980	std::swap (a&: a, b&: b);
2981	reverse = !reverse;
2982	}
2983
2984	/* Check if x = (y op z) : y is supported by czero based ifcvt. */
2985	if (!(noce_cond_zero_binary_op_supported (op: a) && REG_P (b)))
2986	return false;
2987
2988	bin_exp = a;
2989
2990	/* Canonicalize x = (z op y) : y to x = (y op z) : y */
2991	op1 = get_base_reg (XEXP (bin_exp, 1));
2992	if (op1 && rtx_equal_p (op1, b) && COMMUTATIVE_ARITH_P (bin_exp))
2993	std::swap (XEXP (bin_exp, 0), XEXP (bin_exp, 1));
2994
2995	op0 = get_base_reg (XEXP (bin_exp, 0));
2996	if (op0 && rtx_equal_p (op0, b))
2997	{
2998	common = b;
2999	bin_op1 = XEXP (bin_exp, 1);
3000	czero_code = (reverse ^ (GET_CODE (bin_exp) == AND))
3001	? noce_reversed_cond_code (if_info)
3002	: GET_CODE (cond);
3003	}
3004	else
3005	return false;
3006
3007	if (czero_code == UNKNOWN)
3008	return false;
3009
3010	if (REG_P (bin_op1))
3011	*to_replace = &XEXP (bin_exp, 1);
3012	else
3013	return false;
3014
3015	*common_ptr = common;
3016	*bin_exp_ptr = bin_exp;
3017	*czero_code_ptr = czero_code;
3018	*a_ptr = a;
3019
3020	return true;
3021	}
3022
3023	/* Try to covert if-then-else with conditional zero,
3024	returning TURE on success or FALSE on failure.
3025	IF_INFO describes the if-conversion scenario under consideration. */
3026
3027	static int
3028	noce_try_cond_zero_arith (struct noce_if_info *if_info)
3029	{
3030	rtx target, rtmp, a;
3031	rtx_insn *seq;
3032	machine_mode mode = GET_MODE (if_info->x);
3033	rtx common = NULL_RTX;
3034	enum rtx_code czero_code = UNKNOWN;
3035	rtx bin_exp = NULL_RTX;
3036	enum rtx_code bin_code = UNKNOWN;
3037	rtx non_zero_op = NULL_RTX;
3038	rtx *to_replace = NULL;
3039
3040	if (!noce_bbs_ok_for_cond_zero_arith (if_info, common_ptr: &common, bin_exp_ptr: &bin_exp, czero_code_ptr: &czero_code,
3041	a_ptr: &a, to_replace: &to_replace))
3042	return false;
3043
3044	start_sequence ();
3045
3046	bin_code = GET_CODE (bin_exp);
3047
3048	if (bin_code == AND)
3049	{
3050	rtmp = gen_reg_rtx (mode);
3051	noce_emit_move_insn (x: rtmp, y: a);
3052
3053	target = noce_emit_czero (if_info, czero_code, non_zero_op: common, target: if_info->x);
3054	if (!target)
3055	{
3056	end_sequence ();
3057	return false;
3058	}
3059
3060	target = expand_simple_binop (mode, IOR, rtmp, target, if_info->x, 0,
3061	OPTAB_WIDEN);
3062	if (!target)
3063	{
3064	end_sequence ();
3065	return false;
3066	}
3067
3068	if (target != if_info->x)
3069	noce_emit_move_insn (x: if_info->x, y: target);
3070	}
3071	else
3072	{
3073	non_zero_op = *to_replace;
3074	/* If x is used in both input and out like x = c ? x + z : x,
3075	use a new reg to avoid modifying x */
3076	if (common && rtx_equal_p (common, if_info->x))
3077	target = gen_reg_rtx (mode);
3078	else
3079	target = if_info->x;
3080
3081	target = noce_emit_czero (if_info, czero_code, non_zero_op, target);
3082	if (!target || !to_replace)
3083	{
3084	end_sequence ();
3085	return false;
3086	}
3087
3088	*to_replace = target;
3089	noce_emit_move_insn (x: if_info->x, y: a);
3090	}
3091
3092	seq = end_ifcvt_sequence (if_info);
3093	if (!seq || !targetm.noce_conversion_profitable_p (seq, if_info))
3094	return false;
3095
3096	emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATION (insn: if_info->insn_a));
3097	if_info->transform_name = "noce_try_cond_zero_arith";
3098	return true;
3099	}
3100
3101	/* Optimize away "if (x & C) x |= C" and similar bit manipulation
3102	transformations. */
3103
3104	static bool
3105	noce_try_bitop (struct noce_if_info *if_info)
3106	{
3107	rtx cond, x, a, result;
3108	rtx_insn *seq;
3109	scalar_int_mode mode;
3110	enum rtx_code code;
3111	int bitnum;
3112
3113	x = if_info->x;
3114	cond = if_info->cond;
3115	code = GET_CODE (cond);
3116
3117	/* Check for an integer operation. */
3118	if (!is_a <scalar_int_mode> (GET_MODE (x), result: &mode))
3119	return false;
3120
3121	if (!noce_simple_bbs (if_info))
3122	return false;
3123
3124	/* Check for no else condition. */
3125	if (! rtx_equal_p (x, if_info->b))
3126	return false;
3127
3128	/* Check for a suitable condition. */
3129	if (code != NE && code != EQ)
3130	return false;
3131	if (XEXP (cond, 1) != const0_rtx)
3132	return false;
3133	cond = XEXP (cond, 0);
3134
3135	/* ??? We could also handle AND here. */
3136	if (GET_CODE (cond) == ZERO_EXTRACT)
3137	{
3138	if (XEXP (cond, 1) != const1_rtx
3139	|| !CONST_INT_P (XEXP (cond, 2))
3140	|| ! rtx_equal_p (x, XEXP (cond, 0)))
3141	return false;
3142	bitnum = INTVAL (XEXP (cond, 2));
3143	if (BITS_BIG_ENDIAN)
3144	bitnum = GET_MODE_BITSIZE (mode) - 1 - bitnum;
3145	if (bitnum < 0 || bitnum >= HOST_BITS_PER_WIDE_INT)
3146	return false;
3147	}
3148	else
3149	return false;
3150
3151	a = if_info->a;
3152	if (GET_CODE (a) == IOR || GET_CODE (a) == XOR)
3153	{
3154	/* Check for "if (X & C) x = x op C". */
3155	if (! rtx_equal_p (x, XEXP (a, 0))
3156	|| !CONST_INT_P (XEXP (a, 1))
3157	|| (INTVAL (XEXP (a, 1)) & GET_MODE_MASK (mode))
3158	!= HOST_WIDE_INT_1U << bitnum)
3159	return false;
3160
3161	/* if ((x & C) == 0) x |= C; is transformed to x |= C. */
3162	/* if ((x & C) != 0) x |= C; is transformed to nothing. */
3163	if (GET_CODE (a) == IOR)
3164	result = (code == NE) ? a : NULL_RTX;
3165	else if (code == NE)
3166	{
3167	/* if ((x & C) == 0) x ^= C; is transformed to x |= C. */
3168	result = gen_int_mode (HOST_WIDE_INT_1 << bitnum, mode);
3169	result = simplify_gen_binary (code: IOR, mode, op0: x, op1: result);
3170	}
3171	else
3172	{
3173	/* if ((x & C) != 0) x ^= C; is transformed to x &= ~C. */
3174	result = gen_int_mode (~(HOST_WIDE_INT_1 << bitnum), mode);
3175	result = simplify_gen_binary (code: AND, mode, op0: x, op1: result);
3176	}
3177	}
3178	else if (GET_CODE (a) == AND)
3179	{
3180	/* Check for "if (X & C) x &= ~C". */
3181	if (! rtx_equal_p (x, XEXP (a, 0))
3182	|| !CONST_INT_P (XEXP (a, 1))
3183	|| (INTVAL (XEXP (a, 1)) & GET_MODE_MASK (mode))
3184	!= (~(HOST_WIDE_INT_1 << bitnum) & GET_MODE_MASK (mode)))
3185	return false;
3186
3187	/* if ((x & C) == 0) x &= ~C; is transformed to nothing. */
3188	/* if ((x & C) != 0) x &= ~C; is transformed to x &= ~C. */
3189	result = (code == EQ) ? a : NULL_RTX;
3190	}
3191	else
3192	return false;
3193
3194	if (result)
3195	{
3196	start_sequence ();
3197	noce_emit_move_insn (x, y: result);
3198	seq = end_ifcvt_sequence (if_info);
3199	if (!seq)
3200	return false;
3201
3202	emit_insn_before_setloc (seq, if_info->jump,
3203	INSN_LOCATION (insn: if_info->insn_a));
3204	}
3205	if_info->transform_name = "noce_try_bitop";
3206	return true;
3207	}
3208
3209
3210	/* Similar to get_condition, only the resulting condition must be
3211	valid at JUMP, instead of at EARLIEST.
3212
3213	If THEN_ELSE_REVERSED is true, the fallthrough does not go to the
3214	THEN block of the caller, and we have to reverse the condition. */
3215
3216	static rtx
3217	noce_get_condition (rtx_insn *jump, rtx_insn **earliest,
3218	bool then_else_reversed)
3219	{
3220	rtx cond, set, tmp;
3221	bool reverse;
3222
3223	if (! any_condjump_p (jump))
3224	return NULL_RTX;
3225
3226	set = pc_set (jump);
3227
3228	/* If this branches to JUMP_LABEL when the condition is false,
3229	reverse the condition. */
3230	reverse = (GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
3231	&& label_ref_label (XEXP (SET_SRC (set), 2)) == JUMP_LABEL (jump));
3232
3233	/* We may have to reverse because the caller's if block is not canonical,
3234	i.e. the THEN block isn't the fallthrough block for the TEST block
3235	(see find_if_header). */
3236	if (then_else_reversed)
3237	reverse = !reverse;
3238
3239	/* If the condition variable is a register and is MODE_INT, accept it. */
3240
3241	cond = XEXP (SET_SRC (set), 0);
3242	tmp = XEXP (cond, 0);
3243	if (REG_P (tmp) && GET_MODE_CLASS (GET_MODE (tmp)) == MODE_INT
3244	&& (GET_MODE (tmp) != BImode
3245	|| !targetm.small_register_classes_for_mode_p (BImode)))
3246	{
3247	*earliest = jump;
3248
3249	if (reverse)
3250	cond = gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond)),
3251	GET_MODE (cond), tmp, XEXP (cond, 1));
3252	return cond;
3253	}
3254
3255	/* Otherwise, fall back on canonicalize_condition to do the dirty
3256	work of manipulating MODE_CC values and COMPARE rtx codes. */
3257	tmp = canonicalize_condition (jump, cond, reverse, earliest,
3258	NULL_RTX, have_cbranchcc4, true);
3259
3260	/* We don't handle side-effects in the condition, like handling
3261	REG_INC notes and making sure no duplicate conditions are emitted. */
3262	if (tmp != NULL_RTX && side_effects_p (tmp))
3263	return NULL_RTX;
3264
3265	return tmp;
3266	}
3267
3268	/* Return true if OP is ok for if-then-else processing. */
3269
3270	static bool
3271	noce_operand_ok (const_rtx op)
3272	{
3273	if (side_effects_p (op))
3274	return false;
3275
3276	/* We special-case memories, so handle any of them with
3277	no address side effects. */
3278	if (MEM_P (op))
3279	return ! side_effects_p (XEXP (op, 0));
3280
3281	return ! may_trap_p (op);
3282	}
3283
3284	/* Return true iff basic block TEST_BB is valid for noce if-conversion.
3285	The condition used in this if-conversion is in COND.
3286	In practice, check that TEST_BB ends with a single set
3287	x := a and all previous computations
3288	in TEST_BB don't produce any values that are live after TEST_BB.
3289	In other words, all the insns in TEST_BB are there only
3290	to compute a value for x. Add the rtx cost of the insns
3291	in TEST_BB to COST. Record whether TEST_BB is a single simple
3292	set instruction in SIMPLE_P. */
3293
3294	static bool
3295	bb_valid_for_noce_process_p (basic_block test_bb, rtx cond,
3296	unsigned int *cost, bool *simple_p)
3297	{
3298	if (!test_bb)
3299	return false;
3300
3301	rtx_insn *last_insn = last_active_insn (bb: test_bb, skip_use_p: false);
3302	rtx last_set = NULL_RTX;
3303
3304	rtx cc = cc_in_cond (cond);
3305
3306	if (!insn_valid_noce_process_p (insn: last_insn, cc))
3307	return false;
3308
3309	/* Punt on blocks ending with asm goto or jumps with other side-effects,
3310	last_active_insn ignores JUMP_INSNs. */
3311	if (JUMP_P (BB_END (test_bb)) && !onlyjump_p (BB_END (test_bb)))
3312	return false;
3313
3314	last_set = single_set (insn: last_insn);
3315
3316	rtx x = SET_DEST (last_set);
3317	rtx_insn *first_insn = first_active_insn (bb: test_bb);
3318	rtx first_set = single_set (insn: first_insn);
3319
3320	if (!first_set)
3321	return false;
3322
3323	/* We have a single simple set, that's okay. */
3324	bool speed_p = optimize_bb_for_speed_p (test_bb);
3325
3326	if (first_insn == last_insn)
3327	{
3328	*simple_p = noce_operand_ok (SET_DEST (first_set));
3329	*cost += pattern_cost (first_set, speed_p);
3330	return *simple_p;
3331	}
3332
3333	rtx_insn *prev_last_insn = PREV_INSN (insn: last_insn);
3334	gcc_assert (prev_last_insn);
3335
3336	/* For now, disallow setting x multiple times in test_bb. */
3337	if (REG_P (x) && reg_set_between_p (x, first_insn, prev_last_insn))
3338	return false;
3339
3340	bitmap test_bb_temps = BITMAP_ALLOC (obstack: &reg_obstack);
3341
3342	/* The regs that are live out of test_bb. */
3343	bitmap test_bb_live_out = df_get_live_out (bb: test_bb);
3344
3345	int potential_cost = pattern_cost (last_set, speed_p);
3346	rtx_insn *insn;
3347	FOR_BB_INSNS (test_bb, insn)
3348	{
3349	if (insn != last_insn)
3350	{
3351	if (!active_insn_p (insn))
3352	continue;
3353
3354	if (!insn_valid_noce_process_p (insn, cc))
3355	goto free_bitmap_and_fail;
3356
3357	rtx sset = single_set (insn);
3358	gcc_assert (sset);
3359	rtx dest = SET_DEST (sset);
3360	if (SUBREG_P (dest))
3361	dest = SUBREG_REG (dest);
3362
3363	if (contains_mem_rtx_p (SET_SRC (sset))
3364	|| !REG_P (dest)
3365	|| reg_overlap_mentioned_p (dest, cond))
3366	goto free_bitmap_and_fail;
3367
3368	potential_cost += pattern_cost (sset, speed_p);
3369	bitmap_set_bit (test_bb_temps, REGNO (dest));
3370	}
3371	}
3372
3373	/* If any of the intermediate results in test_bb are live after test_bb
3374	then fail. */
3375	if (bitmap_intersect_p (test_bb_live_out, test_bb_temps))
3376	goto free_bitmap_and_fail;
3377
3378	BITMAP_FREE (test_bb_temps);
3379	*cost += potential_cost;
3380	*simple_p = false;
3381	return true;
3382
3383	free_bitmap_and_fail:
3384	BITMAP_FREE (test_bb_temps);
3385	return false;
3386	}
3387
3388	/* Helper function to emit a cmov sequence encapsulated in
3389	start_sequence () and end_sequence (). If NEED_CMOV is true
3390	we call noce_emit_cmove to create a cmove sequence. Otherwise emit
3391	a simple move. If successful, store the first instruction of the
3392	sequence in TEMP_DEST and the sequence costs in SEQ_COST. */
3393
3394	static rtx_insn*
3395	try_emit_cmove_seq (struct noce_if_info *if_info, rtx temp,
3396	rtx cond, rtx new_val, rtx old_val, bool need_cmov,
3397	unsigned *cost, rtx *temp_dest,
3398	rtx cc_cmp = NULL, rtx rev_cc_cmp = NULL)
3399	{
3400	rtx_insn *seq = NULL;
3401	*cost = 0;
3402
3403	rtx x = XEXP (cond, 0);
3404	rtx y = XEXP (cond, 1);
3405	rtx_code cond_code = GET_CODE (cond);
3406
3407	start_sequence ();
3408
3409	if (need_cmov)
3410	*temp_dest = noce_emit_cmove (if_info, x: temp, code: cond_code,
3411	cmp_a: x, cmp_b: y, vfalse: new_val, vtrue: old_val, cc_cmp, rev_cc_cmp);
3412	else
3413	{
3414	*temp_dest = temp;
3415	if (if_info->then_else_reversed)
3416	noce_emit_move_insn (x: temp, y: old_val);
3417	else
3418	noce_emit_move_insn (x: temp, y: new_val);
3419	}
3420
3421	if (*temp_dest != NULL_RTX)
3422	{
3423	seq = get_insns ();
3424	*cost = seq_cost (seq, if_info->speed_p);
3425	}
3426
3427	end_sequence ();
3428
3429	return seq;
3430	}
3431
3432	/* We have something like:
3433
3434	if (x > y)
3435	{ i = a; j = b; k = c; }
3436
3437	Make it:
3438
3439	tmp_i = (x > y) ? a : i;
3440	tmp_j = (x > y) ? b : j;
3441	tmp_k = (x > y) ? c : k;
3442	i = tmp_i;
3443	j = tmp_j;
3444	k = tmp_k;
3445
3446	Subsequent passes are expected to clean up the extra moves.
3447
3448	Look for special cases such as writes to one register which are
3449	read back in another SET, as might occur in a swap idiom or
3450	similar.
3451
3452	These look like:
3453
3454	if (x > y)
3455	i = a;
3456	j = i;
3457
3458	Which we want to rewrite to:
3459
3460	tmp_i = (x > y) ? a : i;
3461	tmp_j = (x > y) ? tmp_i : j;
3462	i = tmp_i;
3463	j = tmp_j;
3464
3465	We can catch these when looking at (SET x y) by keeping a list of the
3466	registers we would have targeted before if-conversion and looking back
3467	through it for an overlap with Y. If we find one, we rewire the
3468	conditional set to use the temporary we introduced earlier.
3469
3470	IF_INFO contains the useful information about the block structure and
3471	jump instructions. */
3472
3473	static bool
3474	noce_convert_multiple_sets (struct noce_if_info *if_info)
3475	{
3476	basic_block test_bb = if_info->test_bb;
3477	basic_block then_bb = if_info->then_bb;
3478	basic_block join_bb = if_info->join_bb;
3479	rtx_insn *jump = if_info->jump;
3480	rtx_insn *cond_earliest;
3481	rtx_insn *insn;
3482
3483	start_sequence ();
3484
3485	/* Decompose the condition attached to the jump. */
3486	rtx cond = noce_get_condition (jump, earliest: &cond_earliest, then_else_reversed: false);
3487	rtx x = XEXP (cond, 0);
3488	rtx y = XEXP (cond, 1);
3489
3490	/* The true targets for a conditional move. */
3491	auto_vec<rtx> targets;
3492	/* The temporaries introduced to allow us to not consider register
3493	overlap. */
3494	auto_vec<rtx> temporaries;
3495	/* The insns we've emitted. */
3496	auto_vec<rtx_insn *> unmodified_insns;
3497
3498	hash_set<rtx_insn *> need_no_cmov;
3499	hash_map<rtx_insn *, int> rewired_src;
3500
3501	need_cmov_or_rewire (then_bb, &need_no_cmov, &rewired_src);
3502
3503	int last_needs_comparison = -1;
3504
3505	bool ok = noce_convert_multiple_sets_1
3506	(if_info, &need_no_cmov, &rewired_src, &targets, &temporaries,
3507	&unmodified_insns, &last_needs_comparison);
3508	if (!ok)
3509	return false;
3510
3511	/* If there are insns that overwrite part of the initial
3512	comparison, we can still omit creating temporaries for
3513	the last of them.
3514	As the second try will always create a less expensive,
3515	valid sequence, we do not need to compare and can discard
3516	the first one. */
3517	if (last_needs_comparison != -1)
3518	{
3519	end_sequence ();
3520	start_sequence ();
3521	ok = noce_convert_multiple_sets_1
3522	(if_info, &need_no_cmov, &rewired_src, &targets, &temporaries,
3523	&unmodified_insns, &last_needs_comparison);
3524	/* Actually we should not fail anymore if we reached here,
3525	but better still check. */
3526	if (!ok)
3527	return false;
3528	}
3529
3530	/* We must have seen some sort of insn to insert, otherwise we were
3531	given an empty BB to convert, and we can't handle that. */
3532	gcc_assert (!unmodified_insns.is_empty ());
3533
3534	/* Now fixup the assignments. */
3535	for (unsigned i = 0; i < targets.length (); i++)
3536	if (targets[i] != temporaries[i])
3537	noce_emit_move_insn (x: targets[i], y: temporaries[i]);
3538
3539	/* Actually emit the sequence if it isn't too expensive. */
3540	rtx_insn *seq = get_insns ();
3541
3542	if (!targetm.noce_conversion_profitable_p (seq, if_info))
3543	{
3544	end_sequence ();
3545	return false;
3546	}
3547
3548	for (insn = seq; insn; insn = NEXT_INSN (insn))
3549	set_used_flags (insn);
3550
3551	/* Mark all our temporaries and targets as used. */
3552	for (unsigned i = 0; i < targets.length (); i++)
3553	{
3554	set_used_flags (temporaries[i]);
3555	set_used_flags (targets[i]);
3556	}
3557
3558	set_used_flags (cond);
3559	set_used_flags (x);
3560	set_used_flags (y);
3561
3562	unshare_all_rtl_in_chain (seq);
3563	end_sequence ();
3564
3565	if (!seq)
3566	return false;
3567
3568	for (insn = seq; insn; insn = NEXT_INSN (insn))
3569	if (JUMP_P (insn)
3570	|| recog_memoized (insn) == -1)
3571	return false;
3572
3573	emit_insn_before_setloc (seq, if_info->jump,
3574	INSN_LOCATION (insn: unmodified_insns.last ()));
3575
3576	/* Clean up THEN_BB and the edges in and out of it. */
3577	remove_edge (find_edge (test_bb, join_bb));
3578	remove_edge (find_edge (then_bb, join_bb));
3579	redirect_edge_and_branch_force (single_succ_edge (bb: test_bb), join_bb);
3580	delete_basic_block (then_bb);
3581	num_true_changes++;
3582
3583	/* Maybe merge blocks now the jump is simple enough. */
3584	if (can_merge_blocks_p (test_bb, join_bb))
3585	{
3586	merge_blocks (test_bb, join_bb);
3587	num_true_changes++;
3588	}
3589
3590	num_updated_if_blocks++;
3591	if_info->transform_name = "noce_convert_multiple_sets";
3592	return true;
3593	}
3594
3595	/* Helper function for noce_convert_multiple_sets_1. If store to
3596	DEST can affect P[0] or P[1], clear P[0]. Called via note_stores. */
3597
3598	static void
3599	check_for_cc_cmp_clobbers (rtx dest, const_rtx, void *p0)
3600	{
3601	rtx *p = (rtx *) p0;
3602	if (p[0] == NULL_RTX)
3603	return;
3604	if (reg_overlap_mentioned_p (dest, p[0])
3605	|| (p[1] && reg_overlap_mentioned_p (dest, p[1])))
3606	p[0] = NULL_RTX;
3607	}
3608
3609	/* This goes through all relevant insns of IF_INFO->then_bb and tries to
3610	create conditional moves. In case a simple move sufficis the insn
3611	should be listed in NEED_NO_CMOV. The rewired-src cases should be
3612	specified via REWIRED_SRC. TARGETS, TEMPORARIES and UNMODIFIED_INSNS
3613	are specified and used in noce_convert_multiple_sets and should be passed
3614	to this function.. */
3615
3616	static bool
3617	noce_convert_multiple_sets_1 (struct noce_if_info *if_info,
3618	hash_set<rtx_insn *> *need_no_cmov,
3619	hash_map<rtx_insn *, int> *rewired_src,
3620	auto_vec<rtx> *targets,
3621	auto_vec<rtx> *temporaries,
3622	auto_vec<rtx_insn *> *unmodified_insns,
3623	int *last_needs_comparison)
3624	{
3625	basic_block then_bb = if_info->then_bb;
3626	rtx_insn *jump = if_info->jump;
3627	rtx_insn *cond_earliest;
3628
3629	/* Decompose the condition attached to the jump. */
3630	rtx cond = noce_get_condition (jump, earliest: &cond_earliest, then_else_reversed: false);
3631
3632	rtx cc_cmp = cond_exec_get_condition (jump);
3633	if (cc_cmp)
3634	cc_cmp = copy_rtx (cc_cmp);
3635	rtx rev_cc_cmp = cond_exec_get_condition (jump, /* get_reversed */ true);
3636	if (rev_cc_cmp)
3637	rev_cc_cmp = copy_rtx (rev_cc_cmp);
3638
3639	rtx_insn *insn;
3640	int count = 0;
3641
3642	targets->truncate (size: 0);
3643	temporaries->truncate (size: 0);
3644	unmodified_insns->truncate (size: 0);
3645
3646	bool second_try = *last_needs_comparison != -1;
3647
3648	FOR_BB_INSNS (then_bb, insn)
3649	{
3650	/* Skip over non-insns. */
3651	if (!active_insn_p (insn))
3652	continue;
3653
3654	rtx set = single_set (insn);
3655	gcc_checking_assert (set);
3656
3657	rtx target = SET_DEST (set);
3658	rtx temp;
3659
3660	rtx new_val = SET_SRC (set);
3661	if (int *ii = rewired_src->get (k: insn))
3662	new_val = simplify_replace_rtx (new_val, (*targets)[*ii],
3663	(*temporaries)[*ii]);
3664	rtx old_val = target;
3665
3666	/* As we are transforming
3667	if (x > y)
3668	{
3669	a = b;
3670	c = d;
3671	}
3672	into
3673	a = (x > y) ...
3674	c = (x > y) ...
3675
3676	we potentially check x > y before every set.
3677	Even though the check might be removed by subsequent passes, this means
3678	that we cannot transform
3679	if (x > y)
3680	{
3681	x = y;
3682	...
3683	}
3684	into
3685	x = (x > y) ...
3686	...
3687	since this would invalidate x and the following to-be-removed checks.
3688	Therefore we introduce a temporary every time we are about to
3689	overwrite a variable used in the check. Costing of a sequence with
3690	these is going to be inaccurate so only use temporaries when
3691	needed.
3692
3693	If performing a second try, we know how many insns require a
3694	temporary. For the last of these, we can omit creating one. */
3695	if (reg_overlap_mentioned_p (target, cond)
3696	&& (!second_try || count < *last_needs_comparison))
3697	temp = gen_reg_rtx (GET_MODE (target));
3698	else
3699	temp = target;
3700
3701	/* We have identified swap-style idioms before. A normal
3702	set will need to be a cmov while the first instruction of a swap-style
3703	idiom can be a regular move. This helps with costing. */
3704	bool need_cmov = !need_no_cmov->contains (k: insn);
3705
3706	/* If we had a non-canonical conditional jump (i.e. one where
3707	the fallthrough is to the "else" case) we need to reverse
3708	the conditional select. */
3709	if (if_info->then_else_reversed)
3710	std::swap (a&: old_val, b&: new_val);
3711
3712	/* Try emitting a conditional move passing the backend the
3713	canonicalized comparison. The backend is then able to
3714	recognize expressions like
3715
3716	if (x > y)
3717	y = x;
3718
3719	as min/max and emit an insn, accordingly. */
3720	unsigned cost1 = 0, cost2 = 0;
3721	rtx_insn *seq, *seq1, *seq2 = NULL;
3722	rtx temp_dest = NULL_RTX, temp_dest1 = NULL_RTX, temp_dest2 = NULL_RTX;
3723	bool read_comparison = false;
3724
3725	seq1 = try_emit_cmove_seq (if_info, temp, cond,
3726	new_val, old_val, need_cmov,
3727	cost: &cost1, temp_dest: &temp_dest1);
3728
3729	/* Here, we try to pass the backend a non-canonicalized cc comparison
3730	as well. This allows the backend to emit a cmov directly without
3731	creating an additional compare for each. If successful, costing
3732	is easier and this sequence is usually preferred. */
3733	if (cc_cmp)
3734	seq2 = try_emit_cmove_seq (if_info, temp, cond,
3735	new_val, old_val, need_cmov,
3736	cost: &cost2, temp_dest: &temp_dest2, cc_cmp, rev_cc_cmp);
3737
3738	/* The backend might have created a sequence that uses the
3739	condition. Check this. */
3740	rtx_insn *walk = seq2;
3741	while (walk)
3742	{
3743	rtx set = single_set (insn: walk);
3744
3745	if (!set || !SET_SRC (set))
3746	{
3747	walk = NEXT_INSN (insn: walk);
3748	continue;
3749	}
3750
3751	rtx src = SET_SRC (set);
3752
3753	if (XEXP (set, 1) && GET_CODE (XEXP (set, 1)) == IF_THEN_ELSE)
3754	; /* We assume that this is the cmove created by the backend that
3755	naturally uses the condition. Therefore we ignore it. */
3756	else
3757	{
3758	if (reg_mentioned_p (XEXP (cond, 0), src)
3759	|| reg_mentioned_p (XEXP (cond, 1), src))
3760	{
3761	read_comparison = true;
3762	break;
3763	}
3764	}
3765
3766	walk = NEXT_INSN (insn: walk);
3767	}
3768
3769	/* Check which version is less expensive. */
3770	if (seq1 != NULL_RTX && (cost1 <= cost2 || seq2 == NULL_RTX))
3771	{
3772	seq = seq1;
3773	temp_dest = temp_dest1;
3774	if (!second_try)
3775	*last_needs_comparison = count;
3776	}
3777	else if (seq2 != NULL_RTX)
3778	{
3779	seq = seq2;
3780	temp_dest = temp_dest2;
3781	if (!second_try && read_comparison)
3782	*last_needs_comparison = count;
3783	}
3784	else
3785	{
3786	/* Nothing worked, bail out. */
3787	end_sequence ();
3788	return false;
3789	}
3790
3791	if (cc_cmp)
3792	{
3793	/* Check if SEQ can clobber registers mentioned in
3794	cc_cmp and/or rev_cc_cmp. If yes, we need to use
3795	only seq1 from that point on. */
3796	rtx cc_cmp_pair[2] = { cc_cmp, rev_cc_cmp };
3797	for (walk = seq; walk; walk = NEXT_INSN (insn: walk))
3798	{
3799	note_stores (walk, check_for_cc_cmp_clobbers, cc_cmp_pair);
3800	if (cc_cmp_pair[0] == NULL_RTX)
3801	{
3802	cc_cmp = NULL_RTX;
3803	rev_cc_cmp = NULL_RTX;
3804	break;
3805	}
3806	}
3807	}
3808
3809	/* End the sub sequence and emit to the main sequence. */
3810	emit_insn (seq);
3811
3812	/* Bookkeeping. */
3813	count++;
3814	targets->safe_push (obj: target);
3815	temporaries->safe_push (obj: temp_dest);
3816	unmodified_insns->safe_push (obj: insn);
3817	}
3818
3819	/* Even if we did not actually need the comparison, we want to make sure
3820	to try a second time in order to get rid of the temporaries. */
3821	if (*last_needs_comparison == -1)
3822	*last_needs_comparison = 0;
3823
3824
3825	return true;
3826	}
3827
3828
3829
3830	/* Return true iff basic block TEST_BB is comprised of only
3831	(SET (REG) (REG)) insns suitable for conversion to a series
3832	of conditional moves. Also check that we have more than one set
3833	(other routines can handle a single set better than we would), and
3834	fewer than PARAM_MAX_RTL_IF_CONVERSION_INSNS sets. While going
3835	through the insns store the sum of their potential costs in COST. */
3836
3837	static bool
3838	bb_ok_for_noce_convert_multiple_sets (basic_block test_bb, unsigned *cost)
3839	{
3840	rtx_insn *insn;
3841	unsigned count = 0;
3842	unsigned param = param_max_rtl_if_conversion_insns;
3843	bool speed_p = optimize_bb_for_speed_p (test_bb);
3844	unsigned potential_cost = 0;
3845
3846	FOR_BB_INSNS (test_bb, insn)
3847	{
3848	/* Skip over notes etc. */
3849	if (!active_insn_p (insn))
3850	continue;
3851
3852	/* We only handle SET insns. */
3853	rtx set = single_set (insn);
3854	if (set == NULL_RTX)
3855	return false;
3856
3857	rtx dest = SET_DEST (set);
3858	rtx src = SET_SRC (set);
3859
3860	/* We can possibly relax this, but for now only handle REG to REG
3861	(including subreg) moves. This avoids any issues that might come
3862	from introducing loads/stores that might violate data-race-freedom
3863	guarantees. */
3864	if (!REG_P (dest))
3865	return false;
3866
3867	if (!((REG_P (src) || CONSTANT_P (src))
3868	|| (GET_CODE (src) == SUBREG && REG_P (SUBREG_REG (src))
3869	&& subreg_lowpart_p (src))))
3870	return false;
3871
3872	/* Destination must be appropriate for a conditional write. */
3873	if (!noce_operand_ok (op: dest))
3874	return false;
3875
3876	/* We must be able to conditionally move in this mode. */
3877	if (!can_conditionally_move_p (GET_MODE (dest)))
3878	return false;
3879
3880	potential_cost += insn_cost (insn, speed_p);
3881
3882	count++;
3883	}
3884
3885	*cost += potential_cost;
3886
3887	/* If we would only put out one conditional move, the other strategies
3888	this pass tries are better optimized and will be more appropriate.
3889	Some targets want to strictly limit the number of conditional moves
3890	that are emitted, they set this through PARAM, we need to respect
3891	that. */
3892	return count > 1 && count <= param;
3893	}
3894
3895	/* Compute average of two given costs weighted by relative probabilities
3896	of respective basic blocks in an IF-THEN-ELSE. E is the IF-THEN edge.
3897	With P as the probability to take the IF-THEN branch, return
3898	P * THEN_COST + (1 - P) * ELSE_COST. */
3899	static unsigned
3900	average_cost (unsigned then_cost, unsigned else_cost, edge e)
3901	{
3902	return else_cost + e->probability.apply (val: (signed) (then_cost - else_cost));
3903	}
3904
3905	/* Given a simple IF-THEN-JOIN or IF-THEN-ELSE-JOIN block, attempt to convert
3906	it without using conditional execution. Return TRUE if we were successful
3907	at converting the block. */
3908
3909	static bool
3910	noce_process_if_block (struct noce_if_info *if_info)
3911	{
3912	basic_block test_bb = if_info->test_bb; /* test block */
3913	basic_block then_bb = if_info->then_bb; /* THEN */
3914	basic_block else_bb = if_info->else_bb; /* ELSE or NULL */
3915	basic_block join_bb = if_info->join_bb; /* JOIN */
3916	rtx_insn *jump = if_info->jump;
3917	rtx cond = if_info->cond;
3918	rtx_insn *insn_a, *insn_b;
3919	rtx set_a, set_b;
3920	rtx orig_x, x, a, b;
3921
3922	/* We're looking for patterns of the form
3923
3924	(1) if (...) x = a; else x = b;
3925	(2) x = b; if (...) x = a;
3926	(3) if (...) x = a; // as if with an initial x = x.
3927	(4) if (...) { x = a; y = b; z = c; } // Like 3, for multiple SETS.
3928	The later patterns require jumps to be more expensive.
3929	For the if (...) x = a; else x = b; case we allow multiple insns
3930	inside the then and else blocks as long as their only effect is
3931	to calculate a value for x.
3932	??? For future expansion, further expand the "multiple X" rules. */
3933
3934	/* First look for multiple SETS. The original costs already include
3935	a base cost of COSTS_N_INSNS (2): one instruction for the compare
3936	(which we will be needing either way) and one instruction for the
3937	branch. When comparing costs we want to use the branch instruction
3938	cost and the sets vs. the cmovs generated here. Therefore subtract
3939	the costs of the compare before checking.
3940	??? Actually, instead of the branch instruction costs we might want
3941	to use COSTS_N_INSNS (BRANCH_COST ()) as in other places. */
3942
3943	unsigned potential_cost = if_info->original_cost - COSTS_N_INSNS (1);
3944	unsigned old_cost = if_info->original_cost;
3945	if (!else_bb
3946	&& HAVE_conditional_move
3947	&& bb_ok_for_noce_convert_multiple_sets (test_bb: then_bb, cost: &potential_cost))
3948	{
3949	/* Temporarily set the original costs to what we estimated so
3950	we can determine if the transformation is worth it. */
3951	if_info->original_cost = potential_cost;
3952	if (noce_convert_multiple_sets (if_info))
3953	{
3954	if (dump_file && if_info->transform_name)
3955	fprintf (stream: dump_file, format: "if-conversion succeeded through %s\n",
3956	if_info->transform_name);
3957	return true;
3958	}
3959
3960	/* Restore the original costs. */
3961	if_info->original_cost = old_cost;
3962	}
3963
3964	bool speed_p = optimize_bb_for_speed_p (test_bb);
3965	unsigned int then_cost = 0, else_cost = 0;
3966	if (!bb_valid_for_noce_process_p (test_bb: then_bb, cond, cost: &then_cost,
3967	simple_p: &if_info->then_simple))
3968	return false;
3969
3970	if (else_bb
3971	&& !bb_valid_for_noce_process_p (test_bb: else_bb, cond, cost: &else_cost,
3972	simple_p: &if_info->else_simple))
3973	return false;
3974
3975	if (speed_p)
3976	if_info->original_cost += average_cost (then_cost, else_cost,
3977	e: find_edge (test_bb, then_bb));
3978	else
3979	if_info->original_cost += then_cost + else_cost;
3980
3981	insn_a = last_active_insn (bb: then_bb, skip_use_p: false);
3982	set_a = single_set (insn: insn_a);
3983	gcc_assert (set_a);
3984
3985	x = SET_DEST (set_a);
3986	a = SET_SRC (set_a);
3987
3988	/* Look for the other potential set. Make sure we've got equivalent
3989	destinations. */
3990	/* ??? This is overconservative. Storing to two different mems is
3991	as easy as conditionally computing the address. Storing to a
3992	single mem merely requires a scratch memory to use as one of the
3993	destination addresses; often the memory immediately below the
3994	stack pointer is available for this. */
3995	set_b = NULL_RTX;
3996	if (else_bb)
3997	{
3998	insn_b = last_active_insn (bb: else_bb, skip_use_p: false);
3999	set_b = single_set (insn: insn_b);
4000	gcc_assert (set_b);
4001
4002	if (!rtx_interchangeable_p (a: x, SET_DEST (set_b)))
4003	return false;
4004	}
4005	else
4006	{
4007	insn_b = if_info->cond_earliest;
4008	do
4009	insn_b = prev_nonnote_nondebug_insn (insn_b);
4010	while (insn_b
4011	&& (BLOCK_FOR_INSN (insn: insn_b)
4012	== BLOCK_FOR_INSN (insn: if_info->cond_earliest))
4013	&& !modified_in_p (x, insn_b));
4014
4015	/* We're going to be moving the evaluation of B down from above
4016	COND_EARLIEST to JUMP. Make sure the relevant data is still
4017	intact. */
4018	if (! insn_b
4019	|| BLOCK_FOR_INSN (insn: insn_b) != BLOCK_FOR_INSN (insn: if_info->cond_earliest)
4020	|| !NONJUMP_INSN_P (insn_b)
4021	|| (set_b = single_set (insn: insn_b)) == NULL_RTX
4022	|| ! rtx_interchangeable_p (a: x, SET_DEST (set_b))
4023	|| ! noce_operand_ok (SET_SRC (set_b))
4024	|| reg_overlap_mentioned_p (x, SET_SRC (set_b))
4025	|| modified_between_p (SET_SRC (set_b), insn_b, jump)
4026	/* Avoid extending the lifetime of hard registers on small
4027	register class machines. */
4028	|| (REG_P (SET_SRC (set_b))
4029	&& HARD_REGISTER_P (SET_SRC (set_b))
4030	&& targetm.small_register_classes_for_mode_p
4031	(GET_MODE (SET_SRC (set_b))))
4032	/* Likewise with X. In particular this can happen when
4033	noce_get_condition looks farther back in the instruction
4034	stream than one might expect. */
4035	|| reg_overlap_mentioned_p (x, cond)
4036	|| reg_overlap_mentioned_p (x, a)
4037	|| modified_between_p (x, insn_b, jump))
4038	{
4039	insn_b = NULL;
4040	set_b = NULL_RTX;
4041	}
4042	}
4043
4044	/* If x has side effects then only the if-then-else form is safe to
4045	convert. But even in that case we would need to restore any notes
4046	(such as REG_INC) at then end. That can be tricky if
4047	noce_emit_move_insn expands to more than one insn, so disable the
4048	optimization entirely for now if there are side effects. */
4049	if (side_effects_p (x))
4050	return false;
4051
4052	b = (set_b ? SET_SRC (set_b) : x);
4053
4054	/* Only operate on register destinations, and even then avoid extending
4055	the lifetime of hard registers on small register class machines. */
4056	orig_x = x;
4057	if_info->orig_x = orig_x;
4058	if (!REG_P (x)
4059	|| (HARD_REGISTER_P (x)
4060	&& targetm.small_register_classes_for_mode_p (GET_MODE (x))))
4061	{
4062	if (GET_MODE (x) == BLKmode)
4063	return false;
4064
4065	if (GET_CODE (x) == ZERO_EXTRACT
4066	&& (!CONST_INT_P (XEXP (x, 1))
4067	|| !CONST_INT_P (XEXP (x, 2))))
4068	return false;
4069
4070	x = gen_reg_rtx (GET_MODE (GET_CODE (x) == STRICT_LOW_PART
4071	? XEXP (x, 0) : x));
4072	}
4073
4074	/* Don't operate on sources that may trap or are volatile. */
4075	if (! noce_operand_ok (op: a) || ! noce_operand_ok (op: b))
4076	return false;
4077
4078	retry:
4079	/* Set up the info block for our subroutines. */
4080	if_info->insn_a = insn_a;
4081	if_info->insn_b = insn_b;
4082	if_info->x = x;
4083	if_info->a = a;
4084	if_info->b = b;
4085
4086	/* Try optimizations in some approximation of a useful order. */
4087	/* ??? Should first look to see if X is live incoming at all. If it
4088	isn't, we don't need anything but an unconditional set. */
4089
4090	/* Look and see if A and B are really the same. Avoid creating silly
4091	cmove constructs that no one will fix up later. */
4092	if (noce_simple_bbs (if_info)
4093	&& rtx_interchangeable_p (a, b))
4094	{
4095	/* If we have an INSN_B, we don't have to create any new rtl. Just
4096	move the instruction that we already have. If we don't have an
4097	INSN_B, that means that A == X, and we've got a noop move. In
4098	that case don't do anything and let the code below delete INSN_A. */
4099	if (insn_b && else_bb)
4100	{
4101	rtx note;
4102
4103	if (else_bb && insn_b == BB_END (else_bb))
4104	BB_END (else_bb) = PREV_INSN (insn: insn_b);
4105	reorder_insns (insn_b, insn_b, PREV_INSN (insn: jump));
4106
4107	/* If there was a REG_EQUAL note, delete it since it may have been
4108	true due to this insn being after a jump. */
4109	if ((note = find_reg_note (insn_b, REG_EQUAL, NULL_RTX)) != 0)
4110	remove_note (insn_b, note);
4111
4112	insn_b = NULL;
4113	}
4114	/* If we have "x = b; if (...) x = a;", and x has side-effects, then
4115	x must be executed twice. */
4116	else if (insn_b && side_effects_p (orig_x))
4117	return false;
4118
4119	x = orig_x;
4120	goto success;
4121	}
4122
4123	if (!set_b && MEM_P (orig_x))
4124	/* We want to avoid store speculation to avoid cases like
4125	if (pthread_mutex_trylock(mutex))
4126	++global_variable;
4127	Rather than go to much effort here, we rely on the SSA optimizers,
4128	which do a good enough job these days. */
4129	return false;
4130
4131	if (noce_try_move (if_info))
4132	goto success;
4133	if (noce_try_ifelse_collapse (if_info))
4134	goto success;
4135	if (noce_try_store_flag (if_info))
4136	goto success;
4137	if (noce_try_bitop (if_info))
4138	goto success;
4139	if (noce_try_minmax (if_info))
4140	goto success;
4141	if (noce_try_abs (if_info))
4142	goto success;
4143	if (noce_try_inverse_constants (if_info))
4144	goto success;
4145	if (!targetm.have_conditional_execution ()
4146	&& noce_try_store_flag_constants (if_info))
4147	goto success;
4148	if (HAVE_conditional_move
4149	&& noce_try_cmove (if_info))
4150	goto success;
4151	if (! targetm.have_conditional_execution ())
4152	{
4153	if (noce_try_addcc (if_info))
4154	goto success;
4155	if (noce_try_store_flag_mask (if_info))
4156	goto success;
4157	if (HAVE_conditional_move
4158	&& noce_try_cond_zero_arith (if_info))
4159	goto success;
4160	if (HAVE_conditional_move
4161	&& noce_try_cmove_arith (if_info))
4162	goto success;
4163	if (noce_try_sign_mask (if_info))
4164	goto success;
4165	}
4166
4167	if (!else_bb && set_b)
4168	{
4169	insn_b = NULL;
4170	set_b = NULL_RTX;
4171	b = orig_x;
4172	goto retry;
4173	}
4174
4175	return false;
4176
4177	success:
4178	if (dump_file && if_info->transform_name)
4179	fprintf (stream: dump_file, format: "if-conversion succeeded through %s\n",
4180	if_info->transform_name);
4181
4182	/* If we used a temporary, fix it up now. */
4183	if (orig_x != x)
4184	{
4185	rtx_insn *seq;
4186
4187	start_sequence ();
4188	noce_emit_move_insn (x: orig_x, y: x);
4189	seq = get_insns ();
4190	set_used_flags (orig_x);
4191	unshare_all_rtl_in_chain (seq);
4192	end_sequence ();
4193
4194	emit_insn_before_setloc (seq, BB_END (test_bb), INSN_LOCATION (insn: insn_a));
4195	}
4196
4197	/* The original THEN and ELSE blocks may now be removed. The test block
4198	must now jump to the join block. If the test block and the join block
4199	can be merged, do so. */
4200	if (else_bb)
4201	{
4202	delete_basic_block (else_bb);
4203	num_true_changes++;
4204	}
4205	else
4206	remove_edge (find_edge (test_bb, join_bb));
4207
4208	remove_edge (find_edge (then_bb, join_bb));
4209	redirect_edge_and_branch_force (single_succ_edge (bb: test_bb), join_bb);
4210	delete_basic_block (then_bb);
4211	num_true_changes++;
4212
4213	if (can_merge_blocks_p (test_bb, join_bb))
4214	{
4215	merge_blocks (test_bb, join_bb);
4216	num_true_changes++;
4217	}
4218
4219	num_updated_if_blocks++;
4220	return true;
4221	}
4222
4223	/* Check whether a block is suitable for conditional move conversion.
4224	Every insn must be a simple set of a register to a constant or a
4225	register. For each assignment, store the value in the pointer map
4226	VALS, keyed indexed by register pointer, then store the register
4227	pointer in REGS. COND is the condition we will test. */
4228
4229	static bool
4230	check_cond_move_block (basic_block bb,
4231	hash_map<rtx, rtx> *vals,
4232	vec<rtx> *regs,
4233	rtx cond)
4234	{
4235	rtx_insn *insn;
4236	rtx cc = cc_in_cond (cond);
4237
4238	/* We can only handle simple jumps at the end of the basic block.
4239	It is almost impossible to update the CFG otherwise. */
4240	insn = BB_END (bb);
4241	if (JUMP_P (insn) && !onlyjump_p (insn))
4242	return false;
4243
4244	FOR_BB_INSNS (bb, insn)
4245	{
4246	rtx set, dest, src;
4247
4248	if (!NONDEBUG_INSN_P (insn) || JUMP_P (insn))
4249	continue;
4250	set = single_set (insn);
4251	if (!set)
4252	return false;
4253
4254	dest = SET_DEST (set);
4255	src = SET_SRC (set);
4256	if (!REG_P (dest)
4257	|| (HARD_REGISTER_P (dest)
4258	&& targetm.small_register_classes_for_mode_p (GET_MODE (dest))))
4259	return false;
4260
4261	if (!CONSTANT_P (src) && !register_operand (src, VOIDmode))
4262	return false;
4263
4264	if (side_effects_p (src) || side_effects_p (dest))
4265	return false;
4266
4267	if (may_trap_p (src) || may_trap_p (dest))
4268	return false;
4269
4270	/* Don't try to handle this if the source register was
4271	modified earlier in the block. */
4272	if ((REG_P (src)
4273	&& vals->get (k: src))
4274	|| (GET_CODE (src) == SUBREG && REG_P (SUBREG_REG (src))
4275	&& vals->get (SUBREG_REG (src))))
4276	return false;
4277
4278	/* Don't try to handle this if the destination register was
4279	modified earlier in the block. */
4280	if (vals->get (k: dest))
4281	return false;
4282
4283	/* Don't try to handle this if the condition uses the
4284	destination register. */
4285	if (reg_overlap_mentioned_p (dest, cond))
4286	return false;
4287
4288	/* Don't try to handle this if the source register is modified
4289	later in the block. */
4290	if (!CONSTANT_P (src)
4291	&& modified_between_p (src, insn, NEXT_INSN (BB_END (bb))))
4292	return false;
4293
4294	/* Skip it if the instruction to be moved might clobber CC. */
4295	if (cc && set_of (cc, insn))
4296	return false;
4297
4298	vals->put (k: dest, v: src);
4299
4300	regs->safe_push (obj: dest);
4301	}
4302
4303	return true;
4304	}
4305
4306	/* Find local swap-style idioms in BB and mark the first insn (1)
4307	that is only a temporary as not needing a conditional move as
4308	it is going to be dead afterwards anyway.
4309
4310	(1) int tmp = a;
4311	a = b;
4312	b = tmp;
4313
4314	ifcvt
4315	-->
4316
4317	tmp = a;
4318	a = cond ? b : a_old;
4319	b = cond ? tmp : b_old;
4320
4321	Additionally, store the index of insns like (2) when a subsequent
4322	SET reads from their destination.
4323
4324	(2) int c = a;
4325	int d = c;
4326
4327	ifcvt
4328	-->
4329
4330	c = cond ? a : c_old;
4331	d = cond ? d : c; // Need to use c rather than c_old here.
4332	*/
4333
4334	static void
4335	need_cmov_or_rewire (basic_block bb,
4336	hash_set<rtx_insn *> *need_no_cmov,
4337	hash_map<rtx_insn *, int> *rewired_src)
4338	{
4339	rtx_insn *insn;
4340	int count = 0;
4341	auto_vec<rtx_insn *> insns;
4342	auto_vec<rtx> dests;
4343
4344	/* Iterate over all SETs, storing the destinations
4345	in DEST.
4346	- If we hit a SET that reads from a destination
4347	that we have seen before and the corresponding register
4348	is dead afterwards, the register does not need to be
4349	moved conditionally.
4350	- If we encounter a previously changed register,
4351	rewire the read to the original source. */
4352	FOR_BB_INSNS (bb, insn)
4353	{
4354	rtx set, src, dest;
4355
4356	if (!active_insn_p (insn))
4357	continue;
4358
4359	set = single_set (insn);
4360	if (set == NULL_RTX)
4361	continue;
4362
4363	src = SET_SRC (set);
4364	if (SUBREG_P (src))
4365	src = SUBREG_REG (src);
4366	dest = SET_DEST (set);
4367
4368	/* Check if the current SET's source is the same
4369	as any previously seen destination.
4370	This is quadratic but the number of insns in BB
4371	is bounded by PARAM_MAX_RTL_IF_CONVERSION_INSNS. */
4372	if (REG_P (src))
4373	for (int i = count - 1; i >= 0; --i)
4374	if (reg_overlap_mentioned_p (src, dests[i]))
4375	{
4376	if (find_reg_note (insn, REG_DEAD, src) != NULL_RTX)
4377	need_no_cmov->add (k: insns[i]);
4378	else
4379	rewired_src->put (k: insn, v: i);
4380	}
4381
4382	insns.safe_push (obj: insn);
4383	dests.safe_push (obj: dest);
4384
4385	count++;
4386	}
4387	}
4388
4389	/* Given a basic block BB suitable for conditional move conversion,
4390	a condition COND, and pointer maps THEN_VALS and ELSE_VALS containing
4391	the register values depending on COND, emit the insns in the block as
4392	conditional moves. If ELSE_BLOCK is true, THEN_BB was already
4393	processed. The caller has started a sequence for the conversion.
4394	Return true if successful, false if something goes wrong. */
4395
4396	static bool
4397	cond_move_convert_if_block (struct noce_if_info *if_infop,
4398	basic_block bb, rtx cond,
4399	hash_map<rtx, rtx> *then_vals,
4400	hash_map<rtx, rtx> *else_vals,
4401	bool else_block_p)
4402	{
4403	enum rtx_code code;
4404	rtx_insn *insn;
4405	rtx cond_arg0, cond_arg1;
4406
4407	code = GET_CODE (cond);
4408	cond_arg0 = XEXP (cond, 0);
4409	cond_arg1 = XEXP (cond, 1);
4410
4411	FOR_BB_INSNS (bb, insn)
4412	{
4413	rtx set, target, dest, t, e;
4414
4415	/* ??? Maybe emit conditional debug insn? */
4416	if (!NONDEBUG_INSN_P (insn) || JUMP_P (insn))
4417	continue;
4418	set = single_set (insn);
4419	gcc_assert (set && REG_P (SET_DEST (set)));
4420
4421	dest = SET_DEST (set);
4422
4423	rtx *then_slot = then_vals->get (k: dest);
4424	rtx *else_slot = else_vals->get (k: dest);
4425	t = then_slot ? *then_slot : NULL_RTX;
4426	e = else_slot ? *else_slot : NULL_RTX;
4427
4428	if (else_block_p)
4429	{
4430	/* If this register was set in the then block, we already
4431	handled this case there. */
4432	if (t)
4433	continue;
4434	t = dest;
4435	gcc_assert (e);
4436	}
4437	else
4438	{
4439	gcc_assert (t);
4440	if (!e)
4441	e = dest;
4442	}
4443
4444	if (if_infop->cond_inverted)
4445	std::swap (a&: t, b&: e);
4446
4447	target = noce_emit_cmove (if_info: if_infop, x: dest, code, cmp_a: cond_arg0, cmp_b: cond_arg1,
4448	vfalse: t, vtrue: e);
4449	if (!target)
4450	return false;
4451
4452	if (target != dest)
4453	noce_emit_move_insn (x: dest, y: target);
4454	}
4455
4456	return true;
4457	}
4458
4459	/* Given a simple IF-THEN-JOIN or IF-THEN-ELSE-JOIN block, attempt to convert
4460	it using only conditional moves. Return TRUE if we were successful at
4461	converting the block. */
4462
4463	static bool
4464	cond_move_process_if_block (struct noce_if_info *if_info)
4465	{
4466	basic_block test_bb = if_info->test_bb;
4467	basic_block then_bb = if_info->then_bb;
4468	basic_block else_bb = if_info->else_bb;
4469	basic_block join_bb = if_info->join_bb;
4470	rtx_insn *jump = if_info->jump;
4471	rtx cond = if_info->cond;
4472	rtx_insn *seq, *loc_insn;
4473	int c;
4474	vec<rtx> then_regs = vNULL;
4475	vec<rtx> else_regs = vNULL;
4476	bool success_p = false;
4477	int limit = param_max_rtl_if_conversion_insns;
4478
4479	/* Build a mapping for each block to the value used for each
4480	register. */
4481	hash_map<rtx, rtx> then_vals;
4482	hash_map<rtx, rtx> else_vals;
4483
4484	/* Make sure the blocks are suitable. */
4485	if (!check_cond_move_block (bb: then_bb, vals: &then_vals, regs: &then_regs, cond)
4486	|| (else_bb
4487	&& !check_cond_move_block (bb: else_bb, vals: &else_vals, regs: &else_regs, cond)))
4488	goto done;
4489
4490	/* Make sure the blocks can be used together. If the same register
4491	is set in both blocks, and is not set to a constant in both
4492	cases, then both blocks must set it to the same register. We
4493	have already verified that if it is set to a register, that the
4494	source register does not change after the assignment. Also count
4495	the number of registers set in only one of the blocks. */
4496	c = 0;
4497	for (rtx reg : then_regs)
4498	{
4499	rtx *then_slot = then_vals.get (k: reg);
4500	rtx *else_slot = else_vals.get (k: reg);
4501
4502	gcc_checking_assert (then_slot);
4503	if (!else_slot)
4504	++c;
4505	else
4506	{
4507	rtx then_val = *then_slot;
4508	rtx else_val = *else_slot;
4509	if (!CONSTANT_P (then_val) && !CONSTANT_P (else_val)
4510	&& !rtx_equal_p (then_val, else_val))
4511	goto done;
4512	}
4513	}
4514
4515	/* Finish off c for MAX_CONDITIONAL_EXECUTE. */
4516	for (rtx reg : else_regs)
4517	{
4518	gcc_checking_assert (else_vals.get (reg));
4519	if (!then_vals.get (k: reg))
4520	++c;
4521	}
4522
4523	/* Make sure it is reasonable to convert this block. What matters
4524	is the number of assignments currently made in only one of the
4525	branches, since if we convert we are going to always execute
4526	them. */
4527	if (c > MAX_CONDITIONAL_EXECUTE
4528	|| c > limit)
4529	goto done;
4530
4531	/* Try to emit the conditional moves. First do the then block,
4532	then do anything left in the else blocks. */
4533	start_sequence ();
4534	if (!cond_move_convert_if_block (if_infop: if_info, bb: then_bb, cond,
4535	then_vals: &then_vals, else_vals: &else_vals, else_block_p: false)
4536	|| (else_bb
4537	&& !cond_move_convert_if_block (if_infop: if_info, bb: else_bb, cond,
4538	then_vals: &then_vals, else_vals: &else_vals, else_block_p: true)))
4539	{
4540	end_sequence ();
4541	goto done;
4542	}
4543	seq = end_ifcvt_sequence (if_info);
4544	if (!seq || !targetm.noce_conversion_profitable_p (seq, if_info))
4545	goto done;
4546
4547	loc_insn = first_active_insn (bb: then_bb);
4548	if (!loc_insn)
4549	{
4550	loc_insn = first_active_insn (bb: else_bb);
4551	gcc_assert (loc_insn);
4552	}
4553	emit_insn_before_setloc (seq, jump, INSN_LOCATION (insn: loc_insn));
4554
4555	if (else_bb)
4556	{
4557	delete_basic_block (else_bb);
4558	num_true_changes++;
4559	}
4560	else
4561	remove_edge (find_edge (test_bb, join_bb));
4562
4563	remove_edge (find_edge (then_bb, join_bb));
4564	redirect_edge_and_branch_force (single_succ_edge (bb: test_bb), join_bb);
4565	delete_basic_block (then_bb);
4566	num_true_changes++;
4567
4568	if (can_merge_blocks_p (test_bb, join_bb))
4569	{
4570	merge_blocks (test_bb, join_bb);
4571	num_true_changes++;
4572	}
4573
4574	num_updated_if_blocks++;
4575	success_p = true;
4576
4577	done:
4578	then_regs.release ();
4579	else_regs.release ();
4580	return success_p;
4581	}
4582
4583
4584	/* Determine if a given basic block heads a simple IF-THEN-JOIN or an
4585	IF-THEN-ELSE-JOIN block.
4586
4587	If so, we'll try to convert the insns to not require the branch,
4588	using only transformations that do not require conditional execution.
4589
4590	Return TRUE if we were successful at converting the block. */
4591
4592	static bool
4593	noce_find_if_block (basic_block test_bb, edge then_edge, edge else_edge,
4594	int pass)
4595	{
4596	basic_block then_bb, else_bb, join_bb;
4597	bool then_else_reversed = false;
4598	rtx_insn *jump;
4599	rtx_insn *cond_earliest;
4600	struct noce_if_info if_info;
4601	bool speed_p = optimize_bb_for_speed_p (test_bb);
4602
4603	/* We only ever should get here before reload. */
4604	gcc_assert (!reload_completed);
4605
4606	/* Recognize an IF-THEN-ELSE-JOIN block. */
4607	if (single_pred_p (bb: then_edge->dest)
4608	&& single_succ_p (bb: then_edge->dest)
4609	&& single_pred_p (bb: else_edge->dest)
4610	&& single_succ_p (bb: else_edge->dest)
4611	&& single_succ (bb: then_edge->dest) == single_succ (bb: else_edge->dest))
4612	{
4613	then_bb = then_edge->dest;
4614	else_bb = else_edge->dest;
4615	join_bb = single_succ (bb: then_bb);
4616	}
4617	/* Recognize an IF-THEN-JOIN block. */
4618	else if (single_pred_p (bb: then_edge->dest)
4619	&& single_succ_p (bb: then_edge->dest)
4620	&& single_succ (bb: then_edge->dest) == else_edge->dest)
4621	{
4622	then_bb = then_edge->dest;
4623	else_bb = NULL_BLOCK;
4624	join_bb = else_edge->dest;
4625	}
4626	/* Recognize an IF-ELSE-JOIN block. We can have those because the order
4627	of basic blocks in cfglayout mode does not matter, so the fallthrough
4628	edge can go to any basic block (and not just to bb->next_bb, like in
4629	cfgrtl mode). */
4630	else if (single_pred_p (bb: else_edge->dest)
4631	&& single_succ_p (bb: else_edge->dest)
4632	&& single_succ (bb: else_edge->dest) == then_edge->dest)
4633	{
4634	/* The noce transformations do not apply to IF-ELSE-JOIN blocks.
4635	To make this work, we have to invert the THEN and ELSE blocks
4636	and reverse the jump condition. */
4637	then_bb = else_edge->dest;
4638	else_bb = NULL_BLOCK;
4639	join_bb = single_succ (bb: then_bb);
4640	then_else_reversed = true;
4641	}
4642	else
4643	/* Not a form we can handle. */
4644	return false;
4645
4646	/* The edges of the THEN and ELSE blocks cannot have complex edges. */
4647	if (single_succ_edge (bb: then_bb)->flags & EDGE_COMPLEX)
4648	return false;
4649	if (else_bb
4650	&& single_succ_edge (bb: else_bb)->flags & EDGE_COMPLEX)
4651	return false;
4652
4653	num_possible_if_blocks++;
4654
4655	if (dump_file)
4656	{
4657	fprintf (stream: dump_file,
4658	format: "\nIF-THEN%s-JOIN block found, pass %d, test %d, then %d",
4659	(else_bb) ? "-ELSE" : "",
4660	pass, test_bb->index, then_bb->index);
4661
4662	if (else_bb)
4663	fprintf (stream: dump_file, format: ", else %d", else_bb->index);
4664
4665	fprintf (stream: dump_file, format: ", join %d\n", join_bb->index);
4666	}
4667
4668	/* If the conditional jump is more than just a conditional
4669	jump, then we cannot do if-conversion on this block. */
4670	jump = BB_END (test_bb);
4671	if (! onlyjump_p (jump))
4672	return false;
4673
4674	/* Initialize an IF_INFO struct to pass around. */
4675	memset (s: &if_info, c: 0, n: sizeof if_info);
4676	if_info.test_bb = test_bb;
4677	if_info.then_bb = then_bb;
4678	if_info.else_bb = else_bb;
4679	if_info.join_bb = join_bb;
4680	if_info.cond = noce_get_condition (jump, earliest: &cond_earliest,
4681	then_else_reversed);
4682	rtx_insn *rev_cond_earliest;
4683	if_info.rev_cond = noce_get_condition (jump, earliest: &rev_cond_earliest,
4684	then_else_reversed: !then_else_reversed);
4685	if (!if_info.cond && !if_info.rev_cond)
4686	return false;
4687	if (!if_info.cond)
4688	{
4689	std::swap (a&: if_info.cond, b&: if_info.rev_cond);
4690	std::swap (a&: cond_earliest, b&: rev_cond_earliest);
4691	if_info.cond_inverted = true;
4692	}
4693	/* We must be comparing objects whose modes imply the size. */
4694	if (GET_MODE (XEXP (if_info.cond, 0)) == BLKmode)
4695	return false;
4696	gcc_assert (if_info.rev_cond == NULL_RTX
4697	|| rev_cond_earliest == cond_earliest);
4698	if_info.cond_earliest = cond_earliest;
4699	if_info.jump = jump;
4700	if_info.then_else_reversed = then_else_reversed;
4701	if_info.speed_p = speed_p;
4702	if_info.max_seq_cost
4703	= targetm.max_noce_ifcvt_seq_cost (then_edge);
4704	/* We'll add in the cost of THEN_BB and ELSE_BB later, when we check
4705	that they are valid to transform. We can't easily get back to the insn
4706	for COND (and it may not exist if we had to canonicalize to get COND),
4707	and jump_insns are always given a cost of 1 by seq_cost, so treat
4708	both instructions as having cost COSTS_N_INSNS (1). */
4709	if_info.original_cost = COSTS_N_INSNS (2);
4710
4711
4712	/* Do the real work. */
4713
4714	/* ??? noce_process_if_block has not yet been updated to handle
4715	inverted conditions. */
4716	if (!if_info.cond_inverted && noce_process_if_block (if_info: &if_info))
4717	return true;
4718
4719	if (HAVE_conditional_move
4720	&& cond_move_process_if_block (if_info: &if_info))
4721	return true;
4722
4723	return false;
4724	}
4725
4726
4727	/* Merge the blocks and mark for local life update. */
4728
4729	static void
4730	merge_if_block (struct ce_if_block * ce_info)
4731	{
4732	basic_block test_bb = ce_info->test_bb; /* last test block */
4733	basic_block then_bb = ce_info->then_bb; /* THEN */
4734	basic_block else_bb = ce_info->else_bb; /* ELSE or NULL */
4735	basic_block join_bb = ce_info->join_bb; /* join block */
4736	basic_block combo_bb;
4737
4738	/* All block merging is done into the lower block numbers. */
4739
4740	combo_bb = test_bb;
4741	df_set_bb_dirty (test_bb);
4742
4743	/* Merge any basic blocks to handle && and || subtests. Each of
4744	the blocks are on the fallthru path from the predecessor block. */
4745	if (ce_info->num_multiple_test_blocks > 0)
4746	{
4747	basic_block bb = test_bb;
4748	basic_block last_test_bb = ce_info->last_test_bb;
4749	basic_block fallthru = block_fallthru (bb);
4750
4751	do
4752	{
4753	bb = fallthru;
4754	fallthru = block_fallthru (bb);
4755	merge_blocks (combo_bb, bb);
4756	num_true_changes++;
4757	}
4758	while (bb != last_test_bb);
4759	}
4760
4761	/* Merge TEST block into THEN block. Normally the THEN block won't have a
4762	label, but it might if there were || tests. That label's count should be
4763	zero, and it normally should be removed. */
4764
4765	if (then_bb)
4766	{
4767	/* If THEN_BB has no successors, then there's a BARRIER after it.
4768	If COMBO_BB has more than one successor (THEN_BB), then that BARRIER
4769	is no longer needed, and in fact it is incorrect to leave it in
4770	the insn stream. */
4771	if (EDGE_COUNT (then_bb->succs) == 0
4772	&& EDGE_COUNT (combo_bb->succs) > 1)
4773	{
4774	rtx_insn *end = NEXT_INSN (BB_END (then_bb));
4775	while (end && NOTE_P (end) && !NOTE_INSN_BASIC_BLOCK_P (end))
4776	end = NEXT_INSN (insn: end);
4777
4778	if (end && BARRIER_P (end))
4779	delete_insn (end);
4780	}
4781	merge_blocks (combo_bb, then_bb);
4782	num_true_changes++;
4783	}
4784
4785	/* The ELSE block, if it existed, had a label. That label count
4786	will almost always be zero, but odd things can happen when labels
4787	get their addresses taken. */
4788	if (else_bb)
4789	{
4790	/* If ELSE_BB has no successors, then there's a BARRIER after it.
4791	If COMBO_BB has more than one successor (ELSE_BB), then that BARRIER
4792	is no longer needed, and in fact it is incorrect to leave it in
4793	the insn stream. */
4794	if (EDGE_COUNT (else_bb->succs) == 0
4795	&& EDGE_COUNT (combo_bb->succs) > 1)
4796	{
4797	rtx_insn *end = NEXT_INSN (BB_END (else_bb));
4798	while (end && NOTE_P (end) && !NOTE_INSN_BASIC_BLOCK_P (end))
4799	end = NEXT_INSN (insn: end);
4800
4801	if (end && BARRIER_P (end))
4802	delete_insn (end);
4803	}
4804	merge_blocks (combo_bb, else_bb);
4805	num_true_changes++;
4806	}
4807
4808	/* If there was no join block reported, that means it was not adjacent
4809	to the others, and so we cannot merge them. */
4810
4811	if (! join_bb)
4812	{
4813	rtx_insn *last = BB_END (combo_bb);
4814
4815	/* The outgoing edge for the current COMBO block should already
4816	be correct. Verify this. */
4817	if (EDGE_COUNT (combo_bb->succs) == 0)
4818	gcc_assert (find_reg_note (last, REG_NORETURN, NULL)
4819	|| (NONJUMP_INSN_P (last)
4820	&& GET_CODE (PATTERN (last)) == TRAP_IF
4821	&& (TRAP_CONDITION (PATTERN (last))
4822	== const_true_rtx)));
4823
4824	else
4825	/* There should still be something at the end of the THEN or ELSE
4826	blocks taking us to our final destination. */
4827	gcc_assert (JUMP_P (last)
4828	|| (EDGE_SUCC (combo_bb, 0)->dest
4829	== EXIT_BLOCK_PTR_FOR_FN (cfun)
4830	&& CALL_P (last)
4831	&& SIBLING_CALL_P (last))
4832	|| ((EDGE_SUCC (combo_bb, 0)->flags & EDGE_EH)
4833	&& can_throw_internal (last)));
4834	}
4835
4836	/* The JOIN block may have had quite a number of other predecessors too.
4837	Since we've already merged the TEST, THEN and ELSE blocks, we should
4838	have only one remaining edge from our if-then-else diamond. If there
4839	is more than one remaining edge, it must come from elsewhere. There
4840	may be zero incoming edges if the THEN block didn't actually join
4841	back up (as with a call to a non-return function). */
4842	else if (EDGE_COUNT (join_bb->preds) < 2
4843	&& join_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
4844	{
4845	/* We can merge the JOIN cleanly and update the dataflow try
4846	again on this pass.*/
4847	merge_blocks (combo_bb, join_bb);
4848	num_true_changes++;
4849	}
4850	else
4851	{
4852	/* We cannot merge the JOIN. */
4853
4854	/* The outgoing edge for the current COMBO block should already
4855	be correct. Verify this. */
4856	gcc_assert (single_succ_p (combo_bb)
4857	&& single_succ (combo_bb) == join_bb);
4858
4859	/* Remove the jump and cruft from the end of the COMBO block. */
4860	if (join_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
4861	tidy_fallthru_edge (single_succ_edge (bb: combo_bb));
4862	}
4863
4864	num_updated_if_blocks++;
4865	}
4866
4867	/* Find a block ending in a simple IF condition and try to transform it
4868	in some way. When converting a multi-block condition, put the new code
4869	in the first such block and delete the rest. Return a pointer to this
4870	first block if some transformation was done. Return NULL otherwise. */
4871
4872	static basic_block
4873	find_if_header (basic_block test_bb, int pass)
4874	{
4875	ce_if_block ce_info;
4876	edge then_edge;
4877	edge else_edge;
4878
4879	/* The kind of block we're looking for has exactly two successors. */
4880	if (EDGE_COUNT (test_bb->succs) != 2)
4881	return NULL;
4882
4883	then_edge = EDGE_SUCC (test_bb, 0);
4884	else_edge = EDGE_SUCC (test_bb, 1);
4885
4886	if (df_get_bb_dirty (then_edge->dest))
4887	return NULL;
4888	if (df_get_bb_dirty (else_edge->dest))
4889	return NULL;
4890
4891	/* Neither edge should be abnormal. */
4892	if ((then_edge->flags & EDGE_COMPLEX)
4893	|| (else_edge->flags & EDGE_COMPLEX))
4894	return NULL;
4895
4896	/* Nor exit the loop. */
4897	if ((then_edge->flags & EDGE_LOOP_EXIT)
4898	|| (else_edge->flags & EDGE_LOOP_EXIT))
4899	return NULL;
4900
4901	/* The THEN edge is canonically the one that falls through. */
4902	if (then_edge->flags & EDGE_FALLTHRU)
4903	;
4904	else if (else_edge->flags & EDGE_FALLTHRU)
4905	std::swap (a&: then_edge, b&: else_edge);
4906	else
4907	/* Otherwise this must be a multiway branch of some sort. */
4908	return NULL;
4909
4910	memset (s: &ce_info, c: 0, n: sizeof (ce_info));
4911	ce_info.test_bb = test_bb;
4912	ce_info.then_bb = then_edge->dest;
4913	ce_info.else_bb = else_edge->dest;
4914	ce_info.pass = pass;
4915
4916	#ifdef IFCVT_MACHDEP_INIT
4917	IFCVT_MACHDEP_INIT (&ce_info);
4918	#endif
4919
4920	if (!reload_completed
4921	&& noce_find_if_block (test_bb, then_edge, else_edge, pass))
4922	goto success;
4923
4924	if (reload_completed
4925	&& targetm.have_conditional_execution ()
4926	&& cond_exec_find_if_block (&ce_info))
4927	goto success;
4928
4929	if (targetm.have_trap ()
4930	&& optab_handler (op: ctrap_optab, mode: word_mode) != CODE_FOR_nothing
4931	&& find_cond_trap (test_bb, then_edge, else_edge))
4932	goto success;
4933
4934	if (dom_info_state (CDI_POST_DOMINATORS) >= DOM_NO_FAST_QUERY
4935	&& (reload_completed || !targetm.have_conditional_execution ()))
4936	{
4937	if (find_if_case_1 (test_bb, then_edge, else_edge))
4938	goto success;
4939	if (find_if_case_2 (test_bb, then_edge, else_edge))
4940	goto success;
4941	}
4942
4943	return NULL;
4944
4945	success:
4946	if (dump_file)
4947	fprintf (stream: dump_file, format: "Conversion succeeded on pass %d.\n", pass);
4948	/* Set this so we continue looking. */
4949	cond_exec_changed_p = true;
4950	return ce_info.test_bb;
4951	}
4952
4953	/* Return true if a block has two edges, one of which falls through to the next
4954	block, and the other jumps to a specific block, so that we can tell if the
4955	block is part of an && test or an || test. Returns either -1 or the number
4956	of non-note, non-jump, non-USE/CLOBBER insns in the block. */
4957
4958	static int
4959	block_jumps_and_fallthru (basic_block cur_bb, basic_block target_bb)
4960	{
4961	edge cur_edge;
4962	bool fallthru_p = false;
4963	bool jump_p = false;
4964	rtx_insn *insn;
4965	rtx_insn *end;
4966	int n_insns = 0;
4967	edge_iterator ei;
4968
4969	if (!cur_bb || !target_bb)
4970	return -1;
4971
4972	/* If no edges, obviously it doesn't jump or fallthru. */
4973	if (EDGE_COUNT (cur_bb->succs) == 0)
4974	return 0;
4975
4976	FOR_EACH_EDGE (cur_edge, ei, cur_bb->succs)
4977	{
4978	if (cur_edge->flags & EDGE_COMPLEX)
4979	/* Anything complex isn't what we want. */
4980	return -1;
4981
4982	else if (cur_edge->flags & EDGE_FALLTHRU)
4983	fallthru_p = true;
4984
4985	else if (cur_edge->dest == target_bb)
4986	jump_p = true;
4987
4988	else
4989	return -1;
4990	}
4991
4992	if ((jump_p & fallthru_p) == 0)
4993	return -1;
4994
4995	/* Don't allow calls in the block, since this is used to group && and ||
4996	together for conditional execution support. ??? we should support
4997	conditional execution support across calls for IA-64 some day, but
4998	for now it makes the code simpler. */
4999	end = BB_END (cur_bb);
5000	insn = BB_HEAD (cur_bb);
5001
5002	while (insn != NULL_RTX)
5003	{
5004	if (CALL_P (insn))
5005	return -1;
5006
5007	if (INSN_P (insn)
5008	&& !JUMP_P (insn)
5009	&& !DEBUG_INSN_P (insn)
5010	&& GET_CODE (PATTERN (insn)) != USE
5011	&& GET_CODE (PATTERN (insn)) != CLOBBER)
5012	n_insns++;
5013
5014	if (insn == end)
5015	break;
5016
5017	insn = NEXT_INSN (insn);
5018	}
5019
5020	return n_insns;
5021	}
5022
5023	/* Determine if a given basic block heads a simple IF-THEN or IF-THEN-ELSE
5024	block. If so, we'll try to convert the insns to not require the branch.
5025	Return TRUE if we were successful at converting the block. */
5026
5027	static bool
5028	cond_exec_find_if_block (struct ce_if_block * ce_info)
5029	{
5030	basic_block test_bb = ce_info->test_bb;
5031	basic_block then_bb = ce_info->then_bb;
5032	basic_block else_bb = ce_info->else_bb;
5033	basic_block join_bb = NULL_BLOCK;
5034	edge cur_edge;
5035	basic_block next;
5036	edge_iterator ei;
5037
5038	ce_info->last_test_bb = test_bb;
5039
5040	/* We only ever should get here after reload,
5041	and if we have conditional execution. */
5042	gcc_assert (reload_completed && targetm.have_conditional_execution ());
5043
5044	/* Discover if any fall through predecessors of the current test basic block
5045	were && tests (which jump to the else block) or || tests (which jump to
5046	the then block). */
5047	if (single_pred_p (bb: test_bb)
5048	&& single_pred_edge (bb: test_bb)->flags == EDGE_FALLTHRU)
5049	{
5050	basic_block bb = single_pred (bb: test_bb);
5051	basic_block target_bb;
5052	int max_insns = MAX_CONDITIONAL_EXECUTE;
5053	int n_insns;
5054
5055	/* Determine if the preceding block is an && or || block. */
5056	if ((n_insns = block_jumps_and_fallthru (cur_bb: bb, target_bb: else_bb)) >= 0)
5057	{
5058	ce_info->and_and_p = true;
5059	target_bb = else_bb;
5060	}
5061	else if ((n_insns = block_jumps_and_fallthru (cur_bb: bb, target_bb: then_bb)) >= 0)
5062	{
5063	ce_info->and_and_p = false;
5064	target_bb = then_bb;
5065	}
5066	else
5067	target_bb = NULL_BLOCK;
5068
5069	if (target_bb && n_insns <= max_insns)
5070	{
5071	int total_insns = 0;
5072	int blocks = 0;
5073
5074	ce_info->last_test_bb = test_bb;
5075
5076	/* Found at least one && or || block, look for more. */
5077	do
5078	{
5079	ce_info->test_bb = test_bb = bb;
5080	total_insns += n_insns;
5081	blocks++;
5082
5083	if (!single_pred_p (bb))
5084	break;
5085
5086	bb = single_pred (bb);
5087	n_insns = block_jumps_and_fallthru (cur_bb: bb, target_bb);
5088	}
5089	while (n_insns >= 0 && (total_insns + n_insns) <= max_insns);
5090
5091	ce_info->num_multiple_test_blocks = blocks;
5092	ce_info->num_multiple_test_insns = total_insns;
5093
5094	if (ce_info->and_and_p)
5095	ce_info->num_and_and_blocks = blocks;
5096	else
5097	ce_info->num_or_or_blocks = blocks;
5098	}
5099	}
5100
5101	/* The THEN block of an IF-THEN combo must have exactly one predecessor,
5102	other than any || blocks which jump to the THEN block. */
5103	if ((EDGE_COUNT (then_bb->preds) - ce_info->num_or_or_blocks) != 1)
5104	return false;
5105
5106	/* The edges of the THEN and ELSE blocks cannot have complex edges. */
5107	FOR_EACH_EDGE (cur_edge, ei, then_bb->preds)
5108	{
5109	if (cur_edge->flags & EDGE_COMPLEX)
5110	return false;
5111	}
5112
5113	FOR_EACH_EDGE (cur_edge, ei, else_bb->preds)
5114	{
5115	if (cur_edge->flags & EDGE_COMPLEX)
5116	return false;
5117	}
5118
5119	/* The THEN block of an IF-THEN combo must have zero or one successors. */
5120	if (EDGE_COUNT (then_bb->succs) > 0
5121	&& (!single_succ_p (bb: then_bb)
5122	|| (single_succ_edge (bb: then_bb)->flags & EDGE_COMPLEX)
5123	|| (epilogue_completed
5124	&& tablejump_p (BB_END (then_bb), NULL, NULL))))
5125	return false;
5126
5127	/* If the THEN block has no successors, conditional execution can still
5128	make a conditional call. Don't do this unless the ELSE block has
5129	only one incoming edge -- the CFG manipulation is too ugly otherwise.
5130	Check for the last insn of the THEN block being an indirect jump, which
5131	is listed as not having any successors, but confuses the rest of the CE
5132	code processing. ??? we should fix this in the future. */
5133	if (EDGE_COUNT (then_bb->succs) == 0)
5134	{
5135	if (single_pred_p (bb: else_bb) && else_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
5136	{
5137	rtx_insn *last_insn = BB_END (then_bb);
5138
5139	while (last_insn
5140	&& NOTE_P (last_insn)
5141	&& last_insn != BB_HEAD (then_bb))
5142	last_insn = PREV_INSN (insn: last_insn);
5143
5144	if (last_insn
5145	&& JUMP_P (last_insn)
5146	&& ! simplejump_p (last_insn))
5147	return false;
5148
5149	join_bb = else_bb;
5150	else_bb = NULL_BLOCK;
5151	}
5152	else
5153	return false;
5154	}
5155
5156	/* If the THEN block's successor is the other edge out of the TEST block,
5157	then we have an IF-THEN combo without an ELSE. */
5158	else if (single_succ (bb: then_bb) == else_bb)
5159	{
5160	join_bb = else_bb;
5161	else_bb = NULL_BLOCK;
5162	}
5163
5164	/* If the THEN and ELSE block meet in a subsequent block, and the ELSE
5165	has exactly one predecessor and one successor, and the outgoing edge
5166	is not complex, then we have an IF-THEN-ELSE combo. */
5167	else if (single_succ_p (bb: else_bb)
5168	&& single_succ (bb: then_bb) == single_succ (bb: else_bb)
5169	&& single_pred_p (bb: else_bb)
5170	&& !(single_succ_edge (bb: else_bb)->flags & EDGE_COMPLEX)
5171	&& !(epilogue_completed
5172	&& tablejump_p (BB_END (else_bb), NULL, NULL)))
5173	join_bb = single_succ (bb: else_bb);
5174
5175	/* Otherwise it is not an IF-THEN or IF-THEN-ELSE combination. */
5176	else
5177	return false;
5178
5179	num_possible_if_blocks++;
5180
5181	if (dump_file)
5182	{
5183	fprintf (stream: dump_file,
5184	format: "\nIF-THEN%s block found, pass %d, start block %d "
5185	"[insn %d], then %d [%d]",
5186	(else_bb) ? "-ELSE" : "",
5187	ce_info->pass,
5188	test_bb->index,
5189	BB_HEAD (test_bb) ? (int)INSN_UID (BB_HEAD (test_bb)) : -1,
5190	then_bb->index,
5191	BB_HEAD (then_bb) ? (int)INSN_UID (BB_HEAD (then_bb)) : -1);
5192
5193	if (else_bb)
5194	fprintf (stream: dump_file, format: ", else %d [%d]",
5195	else_bb->index,
5196	BB_HEAD (else_bb) ? (int)INSN_UID (BB_HEAD (else_bb)) : -1);
5197
5198	fprintf (stream: dump_file, format: ", join %d [%d]",
5199	join_bb->index,
5200	BB_HEAD (join_bb) ? (int)INSN_UID (BB_HEAD (join_bb)) : -1);
5201
5202	if (ce_info->num_multiple_test_blocks > 0)
5203	fprintf (stream: dump_file, format: ", %d %s block%s last test %d [%d]",
5204	ce_info->num_multiple_test_blocks,
5205	(ce_info->and_and_p) ? "&&" : "||",
5206	(ce_info->num_multiple_test_blocks == 1) ? "" : "s",
5207	ce_info->last_test_bb->index,
5208	((BB_HEAD (ce_info->last_test_bb))
5209	? (int)INSN_UID (BB_HEAD (ce_info->last_test_bb))
5210	: -1));
5211
5212	fputc (c: '\n', stream: dump_file);
5213	}
5214
5215	/* Make sure IF, THEN, and ELSE, blocks are adjacent. Actually, we get the
5216	first condition for free, since we've already asserted that there's a
5217	fallthru edge from IF to THEN. Likewise for the && and || blocks, since
5218	we checked the FALLTHRU flag, those are already adjacent to the last IF
5219	block. */
5220	/* ??? As an enhancement, move the ELSE block. Have to deal with
5221	BLOCK notes, if by no other means than backing out the merge if they
5222	exist. Sticky enough I don't want to think about it now. */
5223	next = then_bb;
5224	if (else_bb && (next = next->next_bb) != else_bb)
5225	return false;
5226	if ((next = next->next_bb) != join_bb
5227	&& join_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
5228	{
5229	if (else_bb)
5230	join_bb = NULL;
5231	else
5232	return false;
5233	}
5234
5235	/* Do the real work. */
5236
5237	ce_info->else_bb = else_bb;
5238	ce_info->join_bb = join_bb;
5239
5240	/* If we have && and || tests, try to first handle combining the && and ||
5241	tests into the conditional code, and if that fails, go back and handle
5242	it without the && and ||, which at present handles the && case if there
5243	was no ELSE block. */
5244	if (cond_exec_process_if_block (ce_info, do_multiple_p: true))
5245	return true;
5246
5247	if (ce_info->num_multiple_test_blocks)
5248	{
5249	cancel_changes (0);
5250
5251	if (cond_exec_process_if_block (ce_info, do_multiple_p: false))
5252	return true;
5253	}
5254
5255	return false;
5256	}
5257
5258	/* Convert a branch over a trap, or a branch
5259	to a trap, into a conditional trap. */
5260
5261	static bool
5262	find_cond_trap (basic_block test_bb, edge then_edge, edge else_edge)
5263	{
5264	basic_block then_bb = then_edge->dest;
5265	basic_block else_bb = else_edge->dest;
5266	basic_block other_bb, trap_bb;
5267	rtx_insn *trap, *jump;
5268	rtx cond;
5269	rtx_insn *cond_earliest;
5270
5271	/* Locate the block with the trap instruction. */
5272	/* ??? While we look for no successors, we really ought to allow
5273	EH successors. Need to fix merge_if_block for that to work. */
5274	if ((trap = block_has_only_trap (then_bb)) != NULL)
5275	trap_bb = then_bb, other_bb = else_bb;
5276	else if ((trap = block_has_only_trap (else_bb)) != NULL)
5277	trap_bb = else_bb, other_bb = then_bb;
5278	else
5279	return false;
5280
5281	if (dump_file)
5282	{
5283	fprintf (stream: dump_file, format: "\nTRAP-IF block found, start %d, trap %d\n",
5284	test_bb->index, trap_bb->index);
5285	}
5286
5287	/* If this is not a standard conditional jump, we can't parse it. */
5288	jump = BB_END (test_bb);
5289	cond = noce_get_condition (jump, earliest: &cond_earliest, then_else_reversed: then_bb == trap_bb);
5290	if (! cond)
5291	return false;
5292
5293	/* If the conditional jump is more than just a conditional jump, then
5294	we cannot do if-conversion on this block. Give up for returnjump_p,
5295	changing a conditional return followed by unconditional trap for
5296	conditional trap followed by unconditional return is likely not
5297	beneficial and harder to handle. */
5298	if (! onlyjump_p (jump) || returnjump_p (jump))
5299	return false;
5300
5301	/* We must be comparing objects whose modes imply the size. */
5302	if (GET_MODE (XEXP (cond, 0)) == BLKmode)
5303	return false;
5304
5305	/* Attempt to generate the conditional trap. */
5306	rtx_insn *seq = gen_cond_trap (GET_CODE (cond), copy_rtx (XEXP (cond, 0)),
5307	copy_rtx (XEXP (cond, 1)),
5308	TRAP_CODE (PATTERN (trap)));
5309	if (seq == NULL)
5310	return false;
5311
5312	/* If that results in an invalid insn, back out. */
5313	for (rtx_insn *x = seq; x; x = NEXT_INSN (insn: x))
5314	if (reload_completed
5315	? !valid_insn_p (x)
5316	: recog_memoized (insn: x) < 0)
5317	return false;
5318
5319	/* Emit the new insns before cond_earliest. */
5320	emit_insn_before_setloc (seq, cond_earliest, INSN_LOCATION (insn: trap));
5321
5322	/* Delete the trap block if possible. */
5323	remove_edge (trap_bb == then_bb ? then_edge : else_edge);
5324	df_set_bb_dirty (test_bb);
5325	df_set_bb_dirty (then_bb);
5326	df_set_bb_dirty (else_bb);
5327
5328	if (EDGE_COUNT (trap_bb->preds) == 0)
5329	{
5330	delete_basic_block (trap_bb);
5331	num_true_changes++;
5332	}
5333
5334	/* Wire together the blocks again. */
5335	if (current_ir_type () == IR_RTL_CFGLAYOUT)
5336	single_succ_edge (bb: test_bb)->flags |= EDGE_FALLTHRU;
5337	else if (trap_bb == then_bb)
5338	{
5339	rtx lab = JUMP_LABEL (jump);
5340	rtx_insn *seq = targetm.gen_jump (lab);
5341	rtx_jump_insn *newjump = emit_jump_insn_after (seq, jump);
5342	LABEL_NUSES (lab) += 1;
5343	JUMP_LABEL (newjump) = lab;
5344	emit_barrier_after (newjump);
5345	}
5346	delete_insn (jump);
5347
5348	if (can_merge_blocks_p (test_bb, other_bb))
5349	{
5350	merge_blocks (test_bb, other_bb);
5351	num_true_changes++;
5352	}
5353
5354	num_updated_if_blocks++;
5355	return true;
5356	}
5357
5358	/* Subroutine of find_cond_trap: if BB contains only a trap insn,
5359	return it. */
5360
5361	static rtx_insn *
5362	block_has_only_trap (basic_block bb)
5363	{
5364	rtx_insn *trap;
5365
5366	/* We're not the exit block. */
5367	if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
5368	return NULL;
5369
5370	/* The block must have no successors. */
5371	if (EDGE_COUNT (bb->succs) > 0)
5372	return NULL;
5373
5374	/* The only instruction in the THEN block must be the trap. */
5375	trap = first_active_insn (bb);
5376	if (! (trap == BB_END (bb)
5377	&& GET_CODE (PATTERN (trap)) == TRAP_IF
5378	&& TRAP_CONDITION (PATTERN (trap)) == const_true_rtx))
5379	return NULL;
5380
5381	return trap;
5382	}
5383
5384	/* Look for IF-THEN-ELSE cases in which one of THEN or ELSE is
5385	transformable, but not necessarily the other. There need be no
5386	JOIN block.
5387
5388	Return TRUE if we were successful at converting the block.
5389
5390	Cases we'd like to look at:
5391
5392	(1)
5393	if (test) goto over; // x not live
5394	x = a;
5395	goto label;
5396	over:
5397
5398	becomes
5399
5400	x = a;
5401	if (! test) goto label;
5402
5403	(2)
5404	if (test) goto E; // x not live
5405	x = big();
5406	goto L;
5407	E:
5408	x = b;
5409	goto M;
5410
5411	becomes
5412
5413	x = b;
5414	if (test) goto M;
5415	x = big();
5416	goto L;
5417
5418	(3) // This one's really only interesting for targets that can do
5419	// multiway branching, e.g. IA-64 BBB bundles. For other targets
5420	// it results in multiple branches on a cache line, which often
5421	// does not sit well with predictors.
5422
5423	if (test1) goto E; // predicted not taken
5424	x = a;
5425	if (test2) goto F;
5426	...
5427	E:
5428	x = b;
5429	J:
5430
5431	becomes
5432
5433	x = a;
5434	if (test1) goto E;
5435	if (test2) goto F;
5436
5437	Notes:
5438
5439	(A) Don't do (2) if the branch is predicted against the block we're
5440	eliminating. Do it anyway if we can eliminate a branch; this requires
5441	that the sole successor of the eliminated block postdominate the other
5442	side of the if.
5443
5444	(B) With CE, on (3) we can steal from both sides of the if, creating
5445
5446	if (test1) x = a;
5447	if (!test1) x = b;
5448	if (test1) goto J;
5449	if (test2) goto F;
5450	...
5451	J:
5452
5453	Again, this is most useful if J postdominates.
5454
5455	(C) CE substitutes for helpful life information.
5456
5457	(D) These heuristics need a lot of work. */
5458
5459	/* Tests for case 1 above. */
5460
5461	static bool
5462	find_if_case_1 (basic_block test_bb, edge then_edge, edge else_edge)
5463	{
5464	basic_block then_bb = then_edge->dest;
5465	basic_block else_bb = else_edge->dest;
5466	basic_block new_bb;
5467	int then_bb_index;
5468	profile_probability then_prob;
5469	rtx else_target = NULL_RTX;
5470
5471	/* If we are partitioning hot/cold basic blocks, we don't want to
5472	mess up unconditional or indirect jumps that cross between hot
5473	and cold sections.
5474
5475	Basic block partitioning may result in some jumps that appear to
5476	be optimizable (or blocks that appear to be mergeable), but which really
5477	must be left untouched (they are required to make it safely across
5478	partition boundaries). See the comments at the top of
5479	bb-reorder.cc:partition_hot_cold_basic_blocks for complete details. */
5480
5481	if ((BB_END (then_bb)
5482	&& JUMP_P (BB_END (then_bb))
5483	&& CROSSING_JUMP_P (BB_END (then_bb)))
5484	|| (JUMP_P (BB_END (test_bb))
5485	&& CROSSING_JUMP_P (BB_END (test_bb)))
5486	|| (BB_END (else_bb)
5487	&& JUMP_P (BB_END (else_bb))
5488	&& CROSSING_JUMP_P (BB_END (else_bb))))
5489	return false;
5490
5491	/* Verify test_bb ends in a conditional jump with no other side-effects. */
5492	if (!onlyjump_p (BB_END (test_bb)))
5493	return false;
5494
5495	/* THEN has one successor. */
5496	if (!single_succ_p (bb: then_bb))
5497	return false;
5498
5499	/* THEN does not fall through, but is not strange either. */
5500	if (single_succ_edge (bb: then_bb)->flags & (EDGE_COMPLEX | EDGE_FALLTHRU))
5501	return false;
5502
5503	/* THEN has one predecessor. */
5504	if (!single_pred_p (bb: then_bb))
5505	return false;
5506
5507	/* THEN must do something. */
5508	if (forwarder_block_p (then_bb))
5509	return false;
5510
5511	num_possible_if_blocks++;
5512	if (dump_file)
5513	fprintf (stream: dump_file,
5514	format: "\nIF-CASE-1 found, start %d, then %d\n",
5515	test_bb->index, then_bb->index);
5516
5517	then_prob = then_edge->probability.invert ();
5518
5519	/* We're speculating from the THEN path, we want to make sure the cost
5520	of speculation is within reason. */
5521	if (! cheap_bb_rtx_cost_p (bb: then_bb, prob: then_prob,
5522	COSTS_N_INSNS (BRANCH_COST (optimize_bb_for_speed_p (then_edge->src),
5523	predictable_edge_p (then_edge)))))
5524	return false;
5525
5526	if (else_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
5527	{
5528	rtx_insn *jump = BB_END (else_edge->src);
5529	gcc_assert (JUMP_P (jump));
5530	else_target = JUMP_LABEL (jump);
5531	}
5532
5533	/* Registers set are dead, or are predicable. */
5534	if (! dead_or_predicable (test_bb, then_bb, else_bb,
5535	single_succ_edge (bb: then_bb), true))
5536	return false;
5537
5538	/* Conversion went ok, including moving the insns and fixing up the
5539	jump. Adjust the CFG to match. */
5540
5541	/* We can avoid creating a new basic block if then_bb is immediately
5542	followed by else_bb, i.e. deleting then_bb allows test_bb to fall
5543	through to else_bb. */
5544
5545	if (then_bb->next_bb == else_bb
5546	&& then_bb->prev_bb == test_bb
5547	&& else_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
5548	{
5549	redirect_edge_succ (FALLTHRU_EDGE (test_bb), else_bb);
5550	new_bb = 0;
5551	}
5552	else if (else_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
5553	new_bb = force_nonfallthru_and_redirect (FALLTHRU_EDGE (test_bb),
5554	else_bb, else_target);
5555	else
5556	new_bb = redirect_edge_and_branch_force (FALLTHRU_EDGE (test_bb),
5557	else_bb);
5558
5559	df_set_bb_dirty (test_bb);
5560	df_set_bb_dirty (else_bb);
5561
5562	then_bb_index = then_bb->index;
5563	delete_basic_block (then_bb);
5564
5565	/* Make rest of code believe that the newly created block is the THEN_BB
5566	block we removed. */
5567	if (new_bb)
5568	{
5569	df_bb_replace (then_bb_index, new_bb);
5570	/* This should have been done above via force_nonfallthru_and_redirect
5571	(possibly called from redirect_edge_and_branch_force). */
5572	gcc_checking_assert (BB_PARTITION (new_bb) == BB_PARTITION (test_bb));
5573	}
5574
5575	num_true_changes++;
5576	num_updated_if_blocks++;
5577	return true;
5578	}
5579
5580	/* Test for case 2 above. */
5581
5582	static bool
5583	find_if_case_2 (basic_block test_bb, edge then_edge, edge else_edge)
5584	{
5585	basic_block then_bb = then_edge->dest;
5586	basic_block else_bb = else_edge->dest;
5587	edge else_succ;
5588	profile_probability then_prob, else_prob;
5589
5590	/* We do not want to speculate (empty) loop latches. */
5591	if (current_loops
5592	&& else_bb->loop_father->latch == else_bb)
5593	return false;
5594
5595	/* If we are partitioning hot/cold basic blocks, we don't want to
5596	mess up unconditional or indirect jumps that cross between hot
5597	and cold sections.
5598
5599	Basic block partitioning may result in some jumps that appear to
5600	be optimizable (or blocks that appear to be mergeable), but which really
5601	must be left untouched (they are required to make it safely across
5602	partition boundaries). See the comments at the top of
5603	bb-reorder.cc:partition_hot_cold_basic_blocks for complete details. */
5604
5605	if ((BB_END (then_bb)
5606	&& JUMP_P (BB_END (then_bb))
5607	&& CROSSING_JUMP_P (BB_END (then_bb)))
5608	|| (JUMP_P (BB_END (test_bb))
5609	&& CROSSING_JUMP_P (BB_END (test_bb)))
5610	|| (BB_END (else_bb)
5611	&& JUMP_P (BB_END (else_bb))
5612	&& CROSSING_JUMP_P (BB_END (else_bb))))
5613	return false;
5614
5615	/* Verify test_bb ends in a conditional jump with no other side-effects. */
5616	if (!onlyjump_p (BB_END (test_bb)))
5617	return false;
5618
5619	/* ELSE has one successor. */
5620	if (!single_succ_p (bb: else_bb))
5621	return false;
5622	else
5623	else_succ = single_succ_edge (bb: else_bb);
5624
5625	/* ELSE outgoing edge is not complex. */
5626	if (else_succ->flags & EDGE_COMPLEX)
5627	return false;
5628
5629	/* ELSE has one predecessor. */
5630	if (!single_pred_p (bb: else_bb))
5631	return false;
5632
5633	/* THEN is not EXIT. */
5634	if (then_bb->index < NUM_FIXED_BLOCKS)
5635	return false;
5636
5637	else_prob = else_edge->probability;
5638	then_prob = else_prob.invert ();
5639
5640	/* ELSE is predicted or SUCC(ELSE) postdominates THEN. */
5641	if (else_prob > then_prob)
5642	;
5643	else if (else_succ->dest->index < NUM_FIXED_BLOCKS
5644	|| dominated_by_p (CDI_POST_DOMINATORS, then_bb,
5645	else_succ->dest))
5646	;
5647	else
5648	return false;
5649
5650	num_possible_if_blocks++;
5651	if (dump_file)
5652	fprintf (stream: dump_file,
5653	format: "\nIF-CASE-2 found, start %d, else %d\n",
5654	test_bb->index, else_bb->index);
5655
5656	/* We're speculating from the ELSE path, we want to make sure the cost
5657	of speculation is within reason. */
5658	if (! cheap_bb_rtx_cost_p (bb: else_bb, prob: else_prob,
5659	COSTS_N_INSNS (BRANCH_COST (optimize_bb_for_speed_p (else_edge->src),
5660	predictable_edge_p (else_edge)))))
5661	return false;
5662
5663	/* Registers set are dead, or are predicable. */
5664	if (! dead_or_predicable (test_bb, else_bb, then_bb, else_succ, false))
5665	return false;
5666
5667	/* Conversion went ok, including moving the insns and fixing up the
5668	jump. Adjust the CFG to match. */
5669
5670	df_set_bb_dirty (test_bb);
5671	df_set_bb_dirty (then_bb);
5672	delete_basic_block (else_bb);
5673
5674	num_true_changes++;
5675	num_updated_if_blocks++;
5676
5677	/* ??? We may now fallthru from one of THEN's successors into a join
5678	block. Rerun cleanup_cfg? Examine things manually? Wait? */
5679
5680	return true;
5681	}
5682
5683	/* Used by the code above to perform the actual rtl transformations.
5684	Return TRUE if successful.
5685
5686	TEST_BB is the block containing the conditional branch. MERGE_BB
5687	is the block containing the code to manipulate. DEST_EDGE is an
5688	edge representing a jump to the join block; after the conversion,
5689	TEST_BB should be branching to its destination.
5690	REVERSEP is true if the sense of the branch should be reversed. */
5691
5692	static bool
5693	dead_or_predicable (basic_block test_bb, basic_block merge_bb,
5694	basic_block other_bb, edge dest_edge, bool reversep)
5695	{
5696	basic_block new_dest = dest_edge->dest;
5697	rtx_insn *head, *end, *jump;
5698	rtx_insn *earliest = NULL;
5699	rtx old_dest;
5700	bitmap merge_set = NULL;
5701	/* Number of pending changes. */
5702	int n_validated_changes = 0;
5703	rtx new_dest_label = NULL_RTX;
5704
5705	jump = BB_END (test_bb);
5706
5707	/* Find the extent of the real code in the merge block. */
5708	head = BB_HEAD (merge_bb);
5709	end = BB_END (merge_bb);
5710
5711	while (DEBUG_INSN_P (end) && end != head)
5712	end = PREV_INSN (insn: end);
5713
5714	/* If merge_bb ends with a tablejump, predicating/moving insn's
5715	into test_bb and then deleting merge_bb will result in the jumptable
5716	that follows merge_bb being removed along with merge_bb and then we
5717	get an unresolved reference to the jumptable. */
5718	if (tablejump_p (end, NULL, NULL))
5719	return false;
5720
5721	if (LABEL_P (head))
5722	head = NEXT_INSN (insn: head);
5723	while (DEBUG_INSN_P (head) && head != end)
5724	head = NEXT_INSN (insn: head);
5725	if (NOTE_P (head))
5726	{
5727	if (head == end)
5728	{
5729	head = end = NULL;
5730	goto no_body;
5731	}
5732	head = NEXT_INSN (insn: head);
5733	while (DEBUG_INSN_P (head) && head != end)
5734	head = NEXT_INSN (insn: head);
5735	}
5736
5737	if (JUMP_P (end))
5738	{
5739	if (!onlyjump_p (end))
5740	return false;
5741	if (head == end)
5742	{
5743	head = end = NULL;
5744	goto no_body;
5745	}
5746	end = PREV_INSN (insn: end);
5747	while (DEBUG_INSN_P (end) && end != head)
5748	end = PREV_INSN (insn: end);
5749	}
5750
5751	/* Don't move frame-related insn across the conditional branch. This
5752	can lead to one of the paths of the branch having wrong unwind info. */
5753	if (epilogue_completed)
5754	{
5755	rtx_insn *insn = head;
5756	while (1)
5757	{
5758	if (INSN_P (insn) && RTX_FRAME_RELATED_P (insn))
5759	return false;
5760	if (insn == end)
5761	break;
5762	insn = NEXT_INSN (insn);
5763	}
5764	}
5765
5766	/* Disable handling dead code by conditional execution if the machine needs
5767	to do anything funny with the tests, etc. */
5768	#ifndef IFCVT_MODIFY_TESTS
5769	if (targetm.have_conditional_execution ())
5770	{
5771	/* In the conditional execution case, we have things easy. We know
5772	the condition is reversible. We don't have to check life info
5773	because we're going to conditionally execute the code anyway.
5774	All that's left is making sure the insns involved can actually
5775	be predicated. */
5776
5777	rtx cond;
5778
5779	/* If the conditional jump is more than just a conditional jump,
5780	then we cannot do conditional execution conversion on this block. */
5781	if (!onlyjump_p (jump))
5782	goto nce;
5783
5784	cond = cond_exec_get_condition (jump);
5785	if (! cond)
5786	goto nce;
5787
5788	rtx note = find_reg_note (jump, REG_BR_PROB, NULL_RTX);
5789	profile_probability prob_val
5790	= (note ? profile_probability::from_reg_br_prob_note (XINT (note, 0))
5791	: profile_probability::uninitialized ());
5792
5793	if (reversep)
5794	{
5795	enum rtx_code rev = reversed_comparison_code (cond, jump);
5796	if (rev == UNKNOWN)
5797	return false;
5798	cond = gen_rtx_fmt_ee (rev, GET_MODE (cond), XEXP (cond, 0),
5799	XEXP (cond, 1));
5800	prob_val = prob_val.invert ();
5801	}
5802
5803	if (cond_exec_process_insns (NULL, start: head, end, test: cond, prob_val, mod_ok: false)
5804	&& verify_changes (0))
5805	n_validated_changes = num_validated_changes ();
5806	else
5807	cancel_changes (0);
5808
5809	earliest = jump;
5810	}
5811	nce:
5812	#endif
5813
5814	/* If we allocated new pseudos (e.g. in the conditional move
5815	expander called from noce_emit_cmove), we must resize the
5816	array first. */
5817	if (max_regno < max_reg_num ())
5818	max_regno = max_reg_num ();
5819
5820	/* Try the NCE path if the CE path did not result in any changes. */
5821	if (n_validated_changes == 0)
5822	{
5823	rtx cond;
5824	rtx_insn *insn;
5825	regset live;
5826	bool success;
5827
5828	/* In the non-conditional execution case, we have to verify that there
5829	are no trapping operations, no calls, no references to memory, and
5830	that any registers modified are dead at the branch site. */
5831
5832	if (!any_condjump_p (jump))
5833	return false;
5834
5835	/* Find the extent of the conditional. */
5836	cond = noce_get_condition (jump, earliest: &earliest, then_else_reversed: false);
5837	if (!cond)
5838	return false;
5839
5840	live = BITMAP_ALLOC (obstack: &reg_obstack);
5841	simulate_backwards_to_point (merge_bb, live, end);
5842	success = can_move_insns_across (head, end, earliest, jump,
5843	merge_bb, live,
5844	df_get_live_in (bb: other_bb), NULL);
5845	BITMAP_FREE (live);
5846	if (!success)
5847	return false;
5848
5849	/* Collect the set of registers set in MERGE_BB. */
5850	merge_set = BITMAP_ALLOC (obstack: &reg_obstack);
5851
5852	FOR_BB_INSNS (merge_bb, insn)
5853	if (NONDEBUG_INSN_P (insn))
5854	df_simulate_find_defs (insn, merge_set);
5855
5856	/* If shrink-wrapping, disable this optimization when test_bb is
5857	the first basic block and merge_bb exits. The idea is to not
5858	move code setting up a return register as that may clobber a
5859	register used to pass function parameters, which then must be
5860	saved in caller-saved regs. A caller-saved reg requires the
5861	prologue, killing a shrink-wrap opportunity. */
5862	if ((SHRINK_WRAPPING_ENABLED && !epilogue_completed)
5863	&& ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb == test_bb
5864	&& single_succ_p (bb: new_dest)
5865	&& single_succ (bb: new_dest) == EXIT_BLOCK_PTR_FOR_FN (cfun)
5866	&& bitmap_intersect_p (df_get_live_in (bb: new_dest), merge_set))
5867	{
5868	regset return_regs;
5869	unsigned int i;
5870
5871	return_regs = BITMAP_ALLOC (obstack: &reg_obstack);
5872
5873	/* Start off with the intersection of regs used to pass
5874	params and regs used to return values. */
5875	for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
5876	if (FUNCTION_ARG_REGNO_P (i)
5877	&& targetm.calls.function_value_regno_p (i))
5878	bitmap_set_bit (return_regs, INCOMING_REGNO (i));
5879
5880	bitmap_and_into (return_regs,
5881	df_get_live_out (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
5882	bitmap_and_into (return_regs,
5883	df_get_live_in (EXIT_BLOCK_PTR_FOR_FN (cfun)));
5884	if (!bitmap_empty_p (map: return_regs))
5885	{
5886	FOR_BB_INSNS_REVERSE (new_dest, insn)
5887	if (NONDEBUG_INSN_P (insn))
5888	{
5889	df_ref def;
5890
5891	/* If this insn sets any reg in return_regs, add all
5892	reg uses to the set of regs we're interested in. */
5893	FOR_EACH_INSN_DEF (def, insn)
5894	if (bitmap_bit_p (return_regs, DF_REF_REGNO (def)))
5895	{
5896	df_simulate_uses (insn, return_regs);
5897	break;
5898	}
5899	}
5900	if (bitmap_intersect_p (merge_set, return_regs))
5901	{
5902	BITMAP_FREE (return_regs);
5903	BITMAP_FREE (merge_set);
5904	return false;
5905	}
5906	}
5907	BITMAP_FREE (return_regs);
5908	}
5909	}
5910
5911	no_body:
5912	/* We don't want to use normal invert_jump or redirect_jump because
5913	we don't want to delete_insn called. Also, we want to do our own
5914	change group management. */
5915
5916	old_dest = JUMP_LABEL (jump);
5917	if (other_bb != new_dest)
5918	{
5919	if (!any_condjump_p (jump))
5920	goto cancel;
5921
5922	if (JUMP_P (BB_END (dest_edge->src)))
5923	new_dest_label = JUMP_LABEL (BB_END (dest_edge->src));
5924	else if (new_dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
5925	new_dest_label = ret_rtx;
5926	else
5927	new_dest_label = block_label (new_dest);
5928
5929	rtx_jump_insn *jump_insn = as_a <rtx_jump_insn *> (p: jump);
5930	if (reversep
5931	? ! invert_jump_1 (jump_insn, new_dest_label)
5932	: ! redirect_jump_1 (jump_insn, new_dest_label))
5933	goto cancel;
5934	}
5935
5936	if (verify_changes (n_validated_changes))
5937	confirm_change_group ();
5938	else
5939	goto cancel;
5940
5941	if (other_bb != new_dest)
5942	{
5943	redirect_jump_2 (as_a <rtx_jump_insn *> (p: jump), old_dest, new_dest_label,
5944	0, reversep);
5945
5946	redirect_edge_succ (BRANCH_EDGE (test_bb), new_dest);
5947	if (reversep)
5948	{
5949	std::swap (BRANCH_EDGE (test_bb)->probability,
5950	FALLTHRU_EDGE (test_bb)->probability);
5951	update_br_prob_note (test_bb);
5952	}
5953	}
5954
5955	/* Move the insns out of MERGE_BB to before the branch. */
5956	if (head != NULL)
5957	{
5958	rtx_insn *insn;
5959
5960	if (end == BB_END (merge_bb))
5961	BB_END (merge_bb) = PREV_INSN (insn: head);
5962
5963	/* PR 21767: when moving insns above a conditional branch, the REG_EQUAL
5964	notes being moved might become invalid. */
5965	insn = head;
5966	do
5967	{
5968	rtx note;
5969
5970	if (! INSN_P (insn))
5971	continue;
5972	note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
5973	if (! note)
5974	continue;
5975	remove_note (insn, note);
5976	} while (insn != end && (insn = NEXT_INSN (insn)));
5977
5978	/* PR46315: when moving insns above a conditional branch, the REG_EQUAL
5979	notes referring to the registers being set might become invalid. */
5980	if (merge_set)
5981	{
5982	unsigned i;
5983	bitmap_iterator bi;
5984
5985	EXECUTE_IF_SET_IN_BITMAP (merge_set, 0, i, bi)
5986	remove_reg_equal_equiv_notes_for_regno (i);
5987
5988	BITMAP_FREE (merge_set);
5989	}
5990
5991	reorder_insns (head, end, PREV_INSN (insn: earliest));
5992	}
5993
5994	/* Remove the jump and edge if we can. */
5995	if (other_bb == new_dest)
5996	{
5997	delete_insn (jump);
5998	remove_edge (BRANCH_EDGE (test_bb));
5999	/* ??? Can't merge blocks here, as then_bb is still in use.
6000	At minimum, the merge will get done just before bb-reorder. */
6001	}
6002
6003	return true;
6004
6005	cancel:
6006	cancel_changes (0);
6007
6008	if (merge_set)
6009	BITMAP_FREE (merge_set);
6010
6011	return false;
6012	}
6013
6014	/* Main entry point for all if-conversion. AFTER_COMBINE is true if
6015	we are after combine pass. */
6016
6017	static void
6018	if_convert (bool after_combine)
6019	{
6020	basic_block bb;
6021	int pass;
6022
6023	if (optimize == 1)
6024	{
6025	df_live_add_problem ();
6026	df_live_set_all_dirty ();
6027	}
6028
6029	/* Record whether we are after combine pass. */
6030	ifcvt_after_combine = after_combine;
6031	have_cbranchcc4 = (direct_optab_handler (op: cbranch_optab, CCmode)
6032	!= CODE_FOR_nothing);
6033	num_possible_if_blocks = 0;
6034	num_updated_if_blocks = 0;
6035	num_true_changes = 0;
6036
6037	loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
6038	mark_loop_exit_edges ();
6039	loop_optimizer_finalize ();
6040	free_dominance_info (CDI_DOMINATORS);
6041
6042	/* Compute postdominators. */
6043	calculate_dominance_info (CDI_POST_DOMINATORS);
6044
6045	df_set_flags (DF_LR_RUN_DCE);
6046
6047	/* Go through each of the basic blocks looking for things to convert. If we
6048	have conditional execution, we make multiple passes to allow us to handle
6049	IF-THEN{-ELSE} blocks within other IF-THEN{-ELSE} blocks. */
6050	pass = 0;
6051	do
6052	{
6053	df_analyze ();
6054	/* Only need to do dce on the first pass. */
6055	df_clear_flags (DF_LR_RUN_DCE);
6056	cond_exec_changed_p = false;
6057	pass++;
6058
6059	#ifdef IFCVT_MULTIPLE_DUMPS
6060	if (dump_file && pass > 1)
6061	fprintf (stream: dump_file, format: "\n\n========== Pass %d ==========\n", pass);
6062	#endif
6063
6064	FOR_EACH_BB_FN (bb, cfun)
6065	{
6066	basic_block new_bb;
6067	while (!df_get_bb_dirty (bb)
6068	&& (new_bb = find_if_header (test_bb: bb, pass)) != NULL)
6069	bb = new_bb;
6070	}
6071
6072	#ifdef IFCVT_MULTIPLE_DUMPS
6073	if (dump_file && cond_exec_changed_p)
6074	print_rtl_with_bb (dump_file, get_insns (), dump_flags);
6075	#endif
6076	}
6077	while (cond_exec_changed_p);
6078
6079	#ifdef IFCVT_MULTIPLE_DUMPS
6080	if (dump_file)
6081	fprintf (stream: dump_file, format: "\n\n========== no more changes\n");
6082	#endif
6083
6084	free_dominance_info (CDI_POST_DOMINATORS);
6085
6086	if (dump_file)
6087	fflush (stream: dump_file);
6088
6089	clear_aux_for_blocks ();
6090
6091	/* If we allocated new pseudos, we must resize the array for sched1. */
6092	if (max_regno < max_reg_num ())
6093	max_regno = max_reg_num ();
6094
6095	/* Write the final stats. */
6096	if (dump_file && num_possible_if_blocks > 0)
6097	{
6098	fprintf (stream: dump_file,
6099	format: "\n%d possible IF blocks searched.\n",
6100	num_possible_if_blocks);
6101	fprintf (stream: dump_file,
6102	format: "%d IF blocks converted.\n",
6103	num_updated_if_blocks);
6104	fprintf (stream: dump_file,
6105	format: "%d true changes made.\n\n\n",
6106	num_true_changes);
6107	}
6108
6109	if (optimize == 1)
6110	df_remove_problem (df_live);
6111
6112	/* Some non-cold blocks may now be only reachable from cold blocks.
6113	Fix that up. */
6114	fixup_partitions ();
6115
6116	checking_verify_flow_info ();
6117	}
6118
6119	/* If-conversion and CFG cleanup. */
6120	static void
6121	rest_of_handle_if_conversion (void)
6122	{
6123	int flags = 0;
6124
6125	if (flag_if_conversion)
6126	{
6127	if (dump_file)
6128	{
6129	dump_reg_info (dump_file);
6130	dump_flow_info (dump_file, dump_flags);
6131	}
6132	cleanup_cfg (CLEANUP_EXPENSIVE);
6133	if_convert (after_combine: false);
6134	if (num_updated_if_blocks)
6135	/* Get rid of any dead CC-related instructions. */
6136	flags |= CLEANUP_FORCE_FAST_DCE;
6137	}
6138
6139	cleanup_cfg (flags);
6140	}
6141
6142	namespace {
6143
6144	const pass_data pass_data_rtl_ifcvt =
6145	{
6146	.type: RTL_PASS, /* type */
6147	.name: "ce1", /* name */
6148	.optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
6149	.tv_id: TV_IFCVT, /* tv_id */
6150	.properties_required: 0, /* properties_required */
6151	.properties_provided: 0, /* properties_provided */
6152	.properties_destroyed: 0, /* properties_destroyed */
6153	.todo_flags_start: 0, /* todo_flags_start */
6154	TODO_df_finish, /* todo_flags_finish */
6155	};
6156
6157	class pass_rtl_ifcvt : public rtl_opt_pass
6158	{
6159	public:
6160	pass_rtl_ifcvt (gcc::context *ctxt)
6161	: rtl_opt_pass (pass_data_rtl_ifcvt, ctxt)
6162	{}
6163
6164	/* opt_pass methods: */
6165	bool gate (function *) final override
6166	{
6167	return (optimize > 0) && dbg_cnt (index: if_conversion);
6168	}
6169
6170	unsigned int execute (function *) final override
6171	{
6172	rest_of_handle_if_conversion ();
6173	return 0;
6174	}
6175
6176	}; // class pass_rtl_ifcvt
6177
6178	} // anon namespace
6179
6180	rtl_opt_pass *
6181	make_pass_rtl_ifcvt (gcc::context *ctxt)
6182	{
6183	return new pass_rtl_ifcvt (ctxt);
6184	}
6185
6186
6187	/* Rerun if-conversion, as combine may have simplified things enough
6188	to now meet sequence length restrictions. */
6189
6190	namespace {
6191
6192	const pass_data pass_data_if_after_combine =
6193	{
6194	.type: RTL_PASS, /* type */
6195	.name: "ce2", /* name */
6196	.optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
6197	.tv_id: TV_IFCVT, /* tv_id */
6198	.properties_required: 0, /* properties_required */
6199	.properties_provided: 0, /* properties_provided */
6200	.properties_destroyed: 0, /* properties_destroyed */
6201	.todo_flags_start: 0, /* todo_flags_start */
6202	TODO_df_finish, /* todo_flags_finish */
6203	};
6204
6205	class pass_if_after_combine : public rtl_opt_pass
6206	{
6207	public:
6208	pass_if_after_combine (gcc::context *ctxt)
6209	: rtl_opt_pass (pass_data_if_after_combine, ctxt)
6210	{}
6211
6212	/* opt_pass methods: */
6213	bool gate (function *) final override
6214	{
6215	return optimize > 0 && flag_if_conversion
6216	&& dbg_cnt (index: if_after_combine);
6217	}
6218
6219	unsigned int execute (function *) final override
6220	{
6221	if_convert (after_combine: true);
6222	return 0;
6223	}
6224
6225	}; // class pass_if_after_combine
6226
6227	} // anon namespace
6228
6229	rtl_opt_pass *
6230	make_pass_if_after_combine (gcc::context *ctxt)
6231	{
6232	return new pass_if_after_combine (ctxt);
6233	}
6234
6235
6236	namespace {
6237
6238	const pass_data pass_data_if_after_reload =
6239	{
6240	.type: RTL_PASS, /* type */
6241	.name: "ce3", /* name */
6242	.optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
6243	.tv_id: TV_IFCVT2, /* tv_id */
6244	.properties_required: 0, /* properties_required */
6245	.properties_provided: 0, /* properties_provided */
6246	.properties_destroyed: 0, /* properties_destroyed */
6247	.todo_flags_start: 0, /* todo_flags_start */
6248	TODO_df_finish, /* todo_flags_finish */
6249	};
6250
6251	class pass_if_after_reload : public rtl_opt_pass
6252	{
6253	public:
6254	pass_if_after_reload (gcc::context *ctxt)
6255	: rtl_opt_pass (pass_data_if_after_reload, ctxt)
6256	{}
6257
6258	/* opt_pass methods: */
6259	bool gate (function *) final override
6260	{
6261	return optimize > 0 && flag_if_conversion2
6262	&& dbg_cnt (index: if_after_reload);
6263	}
6264
6265	unsigned int execute (function *) final override
6266	{
6267	if_convert (after_combine: true);
6268	return 0;
6269	}
6270
6271	}; // class pass_if_after_reload
6272
6273	} // anon namespace
6274
6275	rtl_opt_pass *
6276	make_pass_if_after_reload (gcc::context *ctxt)
6277	{
6278	return new pass_if_after_reload (ctxt);
6279	}
6280