1*38fd1498Szrj /* Conditional compare related functions
2*38fd1498Szrj Copyright (C) 2014-2018 Free Software Foundation, Inc.
3*38fd1498Szrj
4*38fd1498Szrj This file is part of GCC.
5*38fd1498Szrj
6*38fd1498Szrj GCC is free software; you can redistribute it and/or modify it under
7*38fd1498Szrj the terms of the GNU General Public License as published by the Free
8*38fd1498Szrj Software Foundation; either version 3, or (at your option) any later
9*38fd1498Szrj version.
10*38fd1498Szrj
11*38fd1498Szrj GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12*38fd1498Szrj WARRANTY; without even the implied warranty of MERCHANTABILITY or
13*38fd1498Szrj FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14*38fd1498Szrj for more details.
15*38fd1498Szrj
16*38fd1498Szrj You should have received a copy of the GNU General Public License
17*38fd1498Szrj along with GCC; see the file COPYING3. If not see
18*38fd1498Szrj <http://www.gnu.org/licenses/>. */
19*38fd1498Szrj
20*38fd1498Szrj #include "config.h"
21*38fd1498Szrj #include "system.h"
22*38fd1498Szrj #include "coretypes.h"
23*38fd1498Szrj #include "backend.h"
24*38fd1498Szrj #include "target.h"
25*38fd1498Szrj #include "rtl.h"
26*38fd1498Szrj #include "tree.h"
27*38fd1498Szrj #include "gimple.h"
28*38fd1498Szrj #include "memmodel.h"
29*38fd1498Szrj #include "tm_p.h"
30*38fd1498Szrj #include "ssa.h"
31*38fd1498Szrj #include "expmed.h"
32*38fd1498Szrj #include "optabs.h"
33*38fd1498Szrj #include "emit-rtl.h"
34*38fd1498Szrj #include "stor-layout.h"
35*38fd1498Szrj #include "tree-ssa-live.h"
36*38fd1498Szrj #include "tree-outof-ssa.h"
37*38fd1498Szrj #include "cfgexpand.h"
38*38fd1498Szrj #include "ccmp.h"
39*38fd1498Szrj #include "predict.h"
40*38fd1498Szrj
41*38fd1498Szrj /* Check whether T is a simple boolean variable or a SSA name
42*38fd1498Szrj set by a comparison operator in the same basic block. */
43*38fd1498Szrj static bool
ccmp_tree_comparison_p(tree t,basic_block bb)44*38fd1498Szrj ccmp_tree_comparison_p (tree t, basic_block bb)
45*38fd1498Szrj {
46*38fd1498Szrj gimple *g = get_gimple_for_ssa_name (t);
47*38fd1498Szrj tree_code tcode;
48*38fd1498Szrj
49*38fd1498Szrj /* If we have a boolean variable allow it and generate a compare
50*38fd1498Szrj to zero reg when expanding. */
51*38fd1498Szrj if (!g)
52*38fd1498Szrj return (TREE_CODE (TREE_TYPE (t)) == BOOLEAN_TYPE);
53*38fd1498Szrj
54*38fd1498Szrj /* Check to see if SSA name is set by a comparison operator in
55*38fd1498Szrj the same basic block. */
56*38fd1498Szrj if (!is_gimple_assign (g))
57*38fd1498Szrj return false;
58*38fd1498Szrj if (bb != gimple_bb (g))
59*38fd1498Szrj return false;
60*38fd1498Szrj tcode = gimple_assign_rhs_code (g);
61*38fd1498Szrj return TREE_CODE_CLASS (tcode) == tcc_comparison;
62*38fd1498Szrj }
63*38fd1498Szrj
64*38fd1498Szrj /* The following functions expand conditional compare (CCMP) instructions.
65*38fd1498Szrj Here is a short description about the over all algorithm:
66*38fd1498Szrj * ccmp_candidate_p is used to identify the CCMP candidate
67*38fd1498Szrj
68*38fd1498Szrj * expand_ccmp_expr is the main entry, which calls expand_ccmp_expr_1
69*38fd1498Szrj to expand CCMP.
70*38fd1498Szrj
71*38fd1498Szrj * expand_ccmp_expr_1 uses a recursive algorithm to expand CCMP.
72*38fd1498Szrj It calls two target hooks gen_ccmp_first and gen_ccmp_next to generate
73*38fd1498Szrj CCMP instructions.
74*38fd1498Szrj - gen_ccmp_first expands the first compare in CCMP.
75*38fd1498Szrj - gen_ccmp_next expands the following compares.
76*38fd1498Szrj
77*38fd1498Szrj Both hooks return a comparison with the CC register that is equivalent
78*38fd1498Szrj to the value of the gimple comparison. This is used by the next CCMP
79*38fd1498Szrj and in the final conditional store.
80*38fd1498Szrj
81*38fd1498Szrj * We use cstorecc4 pattern to convert the CCmode intermediate to
82*38fd1498Szrj the integer mode result that expand_normal is expecting.
83*38fd1498Szrj
84*38fd1498Szrj Since the operands of the later compares might clobber CC reg, we do not
85*38fd1498Szrj emit the insns during expand. We keep the insn sequences in two seq
86*38fd1498Szrj
87*38fd1498Szrj * prep_seq, which includes all the insns to prepare the operands.
88*38fd1498Szrj * gen_seq, which includes all the compare and conditional compares.
89*38fd1498Szrj
90*38fd1498Szrj If all checks OK in expand_ccmp_expr, it emits insns in prep_seq, then
91*38fd1498Szrj insns in gen_seq. */
92*38fd1498Szrj
93*38fd1498Szrj /* Check whether G is a potential conditional compare candidate. */
94*38fd1498Szrj static bool
ccmp_candidate_p(gimple * g)95*38fd1498Szrj ccmp_candidate_p (gimple *g)
96*38fd1498Szrj {
97*38fd1498Szrj tree rhs;
98*38fd1498Szrj tree lhs, op0, op1;
99*38fd1498Szrj gimple *gs0, *gs1;
100*38fd1498Szrj tree_code tcode;
101*38fd1498Szrj basic_block bb;
102*38fd1498Szrj
103*38fd1498Szrj if (!g)
104*38fd1498Szrj return false;
105*38fd1498Szrj
106*38fd1498Szrj rhs = gimple_assign_rhs_to_tree (g);
107*38fd1498Szrj tcode = TREE_CODE (rhs);
108*38fd1498Szrj if (tcode != BIT_AND_EXPR && tcode != BIT_IOR_EXPR)
109*38fd1498Szrj return false;
110*38fd1498Szrj
111*38fd1498Szrj lhs = gimple_assign_lhs (g);
112*38fd1498Szrj op0 = TREE_OPERAND (rhs, 0);
113*38fd1498Szrj op1 = TREE_OPERAND (rhs, 1);
114*38fd1498Szrj bb = gimple_bb (g);
115*38fd1498Szrj
116*38fd1498Szrj if ((TREE_CODE (op0) != SSA_NAME) || (TREE_CODE (op1) != SSA_NAME)
117*38fd1498Szrj || !has_single_use (lhs))
118*38fd1498Szrj return false;
119*38fd1498Szrj
120*38fd1498Szrj gs0 = get_gimple_for_ssa_name (op0); /* gs0 may be NULL */
121*38fd1498Szrj gs1 = get_gimple_for_ssa_name (op1); /* gs1 may be NULL */
122*38fd1498Szrj
123*38fd1498Szrj if (ccmp_tree_comparison_p (op0, bb) && ccmp_tree_comparison_p (op1, bb))
124*38fd1498Szrj return true;
125*38fd1498Szrj if (ccmp_tree_comparison_p (op0, bb) && ccmp_candidate_p (gs1))
126*38fd1498Szrj return true;
127*38fd1498Szrj if (ccmp_tree_comparison_p (op1, bb) && ccmp_candidate_p (gs0))
128*38fd1498Szrj return true;
129*38fd1498Szrj /* We skip ccmp_candidate_p (gs1) && ccmp_candidate_p (gs0) since
130*38fd1498Szrj there is no way to set and maintain the CC flag on both sides of
131*38fd1498Szrj the logical operator at the same time. */
132*38fd1498Szrj return false;
133*38fd1498Szrj }
134*38fd1498Szrj
135*38fd1498Szrj /* Extract the comparison we want to do from the tree. */
136*38fd1498Szrj void
get_compare_parts(tree t,int * up,rtx_code * rcode,tree * rhs1,tree * rhs2)137*38fd1498Szrj get_compare_parts (tree t, int *up, rtx_code *rcode,
138*38fd1498Szrj tree *rhs1, tree *rhs2)
139*38fd1498Szrj {
140*38fd1498Szrj tree_code code;
141*38fd1498Szrj gimple *g = get_gimple_for_ssa_name (t);
142*38fd1498Szrj if (g)
143*38fd1498Szrj {
144*38fd1498Szrj *up = TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (g)));
145*38fd1498Szrj code = gimple_assign_rhs_code (g);
146*38fd1498Szrj *rcode = get_rtx_code (code, *up);
147*38fd1498Szrj *rhs1 = gimple_assign_rhs1 (g);
148*38fd1498Szrj *rhs2 = gimple_assign_rhs2 (g);
149*38fd1498Szrj }
150*38fd1498Szrj else
151*38fd1498Szrj {
152*38fd1498Szrj /* If g is not a comparison operator create a compare to zero. */
153*38fd1498Szrj *up = 1;
154*38fd1498Szrj *rcode = NE;
155*38fd1498Szrj *rhs1 = t;
156*38fd1498Szrj *rhs2 = build_zero_cst (TREE_TYPE (t));
157*38fd1498Szrj }
158*38fd1498Szrj }
159*38fd1498Szrj
160*38fd1498Szrj /* PREV is a comparison with the CC register which represents the
161*38fd1498Szrj result of the previous CMP or CCMP. The function expands the
162*38fd1498Szrj next compare based on G which is ANDed/ORed with the previous
163*38fd1498Szrj compare depending on CODE.
164*38fd1498Szrj PREP_SEQ returns all insns to prepare opearands for compare.
165*38fd1498Szrj GEN_SEQ returns all compare insns. */
166*38fd1498Szrj static rtx
expand_ccmp_next(tree op,tree_code code,rtx prev,rtx_insn ** prep_seq,rtx_insn ** gen_seq)167*38fd1498Szrj expand_ccmp_next (tree op, tree_code code, rtx prev,
168*38fd1498Szrj rtx_insn **prep_seq, rtx_insn **gen_seq)
169*38fd1498Szrj {
170*38fd1498Szrj rtx_code rcode;
171*38fd1498Szrj int unsignedp;
172*38fd1498Szrj tree rhs1, rhs2;
173*38fd1498Szrj
174*38fd1498Szrj get_compare_parts(op, &unsignedp, &rcode, &rhs1, &rhs2);
175*38fd1498Szrj return targetm.gen_ccmp_next (prep_seq, gen_seq, prev, rcode,
176*38fd1498Szrj rhs1, rhs2, get_rtx_code (code, 0));
177*38fd1498Szrj }
178*38fd1498Szrj
179*38fd1498Szrj /* Expand conditional compare gimple G. A typical CCMP sequence is like:
180*38fd1498Szrj
181*38fd1498Szrj CC0 = CMP (a, b);
182*38fd1498Szrj CC1 = CCMP (NE (CC0, 0), CMP (e, f));
183*38fd1498Szrj ...
184*38fd1498Szrj CCn = CCMP (NE (CCn-1, 0), CMP (...));
185*38fd1498Szrj
186*38fd1498Szrj hook gen_ccmp_first is used to expand the first compare.
187*38fd1498Szrj hook gen_ccmp_next is used to expand the following CCMP.
188*38fd1498Szrj PREP_SEQ returns all insns to prepare opearand.
189*38fd1498Szrj GEN_SEQ returns all compare insns. */
190*38fd1498Szrj static rtx
expand_ccmp_expr_1(gimple * g,rtx_insn ** prep_seq,rtx_insn ** gen_seq)191*38fd1498Szrj expand_ccmp_expr_1 (gimple *g, rtx_insn **prep_seq, rtx_insn **gen_seq)
192*38fd1498Szrj {
193*38fd1498Szrj tree exp = gimple_assign_rhs_to_tree (g);
194*38fd1498Szrj tree_code code = TREE_CODE (exp);
195*38fd1498Szrj basic_block bb = gimple_bb (g);
196*38fd1498Szrj
197*38fd1498Szrj tree op0 = TREE_OPERAND (exp, 0);
198*38fd1498Szrj tree op1 = TREE_OPERAND (exp, 1);
199*38fd1498Szrj gimple *gs0 = get_gimple_for_ssa_name (op0);
200*38fd1498Szrj gimple *gs1 = get_gimple_for_ssa_name (op1);
201*38fd1498Szrj rtx tmp;
202*38fd1498Szrj
203*38fd1498Szrj gcc_assert (code == BIT_AND_EXPR || code == BIT_IOR_EXPR);
204*38fd1498Szrj
205*38fd1498Szrj if (ccmp_tree_comparison_p (op0, bb))
206*38fd1498Szrj {
207*38fd1498Szrj if (ccmp_tree_comparison_p (op1, bb))
208*38fd1498Szrj {
209*38fd1498Szrj int unsignedp0, unsignedp1;
210*38fd1498Szrj rtx_code rcode0, rcode1;
211*38fd1498Szrj tree logical_op0_rhs1, logical_op0_rhs2;
212*38fd1498Szrj tree logical_op1_rhs1, logical_op1_rhs2;
213*38fd1498Szrj int speed_p = optimize_insn_for_speed_p ();
214*38fd1498Szrj
215*38fd1498Szrj rtx tmp2 = NULL_RTX, ret = NULL_RTX, ret2 = NULL_RTX;
216*38fd1498Szrj unsigned cost1 = MAX_COST;
217*38fd1498Szrj unsigned cost2 = MAX_COST;
218*38fd1498Szrj
219*38fd1498Szrj get_compare_parts (op0, &unsignedp0, &rcode0,
220*38fd1498Szrj &logical_op0_rhs1, &logical_op0_rhs2);
221*38fd1498Szrj
222*38fd1498Szrj get_compare_parts (op1, &unsignedp1, &rcode1,
223*38fd1498Szrj &logical_op1_rhs1, &logical_op1_rhs2);
224*38fd1498Szrj
225*38fd1498Szrj rtx_insn *prep_seq_1, *gen_seq_1;
226*38fd1498Szrj tmp = targetm.gen_ccmp_first (&prep_seq_1, &gen_seq_1, rcode0,
227*38fd1498Szrj logical_op0_rhs1, logical_op0_rhs2);
228*38fd1498Szrj if (tmp != NULL)
229*38fd1498Szrj {
230*38fd1498Szrj ret = expand_ccmp_next (op1, code, tmp, &prep_seq_1, &gen_seq_1);
231*38fd1498Szrj cost1 = seq_cost (prep_seq_1, speed_p);
232*38fd1498Szrj cost1 += seq_cost (gen_seq_1, speed_p);
233*38fd1498Szrj }
234*38fd1498Szrj
235*38fd1498Szrj /* FIXME: Temporary workaround for PR69619.
236*38fd1498Szrj Avoid exponential compile time due to expanding gs0 and gs1 twice.
237*38fd1498Szrj If gs0 and gs1 are complex, the cost will be high, so avoid
238*38fd1498Szrj reevaluation if above an arbitrary threshold. */
239*38fd1498Szrj rtx_insn *prep_seq_2, *gen_seq_2;
240*38fd1498Szrj if (tmp == NULL || cost1 < COSTS_N_INSNS (25))
241*38fd1498Szrj tmp2 = targetm.gen_ccmp_first (&prep_seq_2, &gen_seq_2, rcode1,
242*38fd1498Szrj logical_op1_rhs1, logical_op1_rhs2);
243*38fd1498Szrj if (!tmp && !tmp2)
244*38fd1498Szrj return NULL_RTX;
245*38fd1498Szrj if (tmp2 != NULL)
246*38fd1498Szrj {
247*38fd1498Szrj ret2 = expand_ccmp_next (op0, code, tmp2, &prep_seq_2,
248*38fd1498Szrj &gen_seq_2);
249*38fd1498Szrj cost2 = seq_cost (prep_seq_2, speed_p);
250*38fd1498Szrj cost2 += seq_cost (gen_seq_2, speed_p);
251*38fd1498Szrj }
252*38fd1498Szrj if (cost2 < cost1)
253*38fd1498Szrj {
254*38fd1498Szrj *prep_seq = prep_seq_2;
255*38fd1498Szrj *gen_seq = gen_seq_2;
256*38fd1498Szrj return ret2;
257*38fd1498Szrj }
258*38fd1498Szrj *prep_seq = prep_seq_1;
259*38fd1498Szrj *gen_seq = gen_seq_1;
260*38fd1498Szrj return ret;
261*38fd1498Szrj }
262*38fd1498Szrj else
263*38fd1498Szrj {
264*38fd1498Szrj tmp = expand_ccmp_expr_1 (gs1, prep_seq, gen_seq);
265*38fd1498Szrj if (!tmp)
266*38fd1498Szrj return NULL_RTX;
267*38fd1498Szrj return expand_ccmp_next (op0, code, tmp, prep_seq, gen_seq);
268*38fd1498Szrj }
269*38fd1498Szrj }
270*38fd1498Szrj else
271*38fd1498Szrj {
272*38fd1498Szrj gcc_assert (gimple_assign_rhs_code (gs0) == BIT_AND_EXPR
273*38fd1498Szrj || gimple_assign_rhs_code (gs0) == BIT_IOR_EXPR);
274*38fd1498Szrj gcc_assert (ccmp_tree_comparison_p (op1, bb));
275*38fd1498Szrj tmp = expand_ccmp_expr_1 (gs0, prep_seq, gen_seq);
276*38fd1498Szrj if (!tmp)
277*38fd1498Szrj return NULL_RTX;
278*38fd1498Szrj return expand_ccmp_next (op1, code, tmp, prep_seq, gen_seq);
279*38fd1498Szrj }
280*38fd1498Szrj
281*38fd1498Szrj return NULL_RTX;
282*38fd1498Szrj }
283*38fd1498Szrj
284*38fd1498Szrj /* Main entry to expand conditional compare statement G.
285*38fd1498Szrj Return NULL_RTX if G is not a legal candidate or expand fail.
286*38fd1498Szrj Otherwise return the target. */
287*38fd1498Szrj rtx
expand_ccmp_expr(gimple * g,machine_mode mode)288*38fd1498Szrj expand_ccmp_expr (gimple *g, machine_mode mode)
289*38fd1498Szrj {
290*38fd1498Szrj rtx_insn *last;
291*38fd1498Szrj rtx tmp;
292*38fd1498Szrj
293*38fd1498Szrj if (!ccmp_candidate_p (g))
294*38fd1498Szrj return NULL_RTX;
295*38fd1498Szrj
296*38fd1498Szrj last = get_last_insn ();
297*38fd1498Szrj
298*38fd1498Szrj rtx_insn *prep_seq = NULL, *gen_seq = NULL;
299*38fd1498Szrj tmp = expand_ccmp_expr_1 (g, &prep_seq, &gen_seq);
300*38fd1498Szrj
301*38fd1498Szrj if (tmp)
302*38fd1498Szrj {
303*38fd1498Szrj insn_code icode;
304*38fd1498Szrj machine_mode cc_mode = CCmode;
305*38fd1498Szrj rtx_code cmp_code = GET_CODE (tmp);
306*38fd1498Szrj
307*38fd1498Szrj #ifdef SELECT_CC_MODE
308*38fd1498Szrj cc_mode = SELECT_CC_MODE (cmp_code, XEXP (tmp, 0), const0_rtx);
309*38fd1498Szrj #endif
310*38fd1498Szrj icode = optab_handler (cstore_optab, cc_mode);
311*38fd1498Szrj if (icode != CODE_FOR_nothing)
312*38fd1498Szrj {
313*38fd1498Szrj rtx target = gen_reg_rtx (mode);
314*38fd1498Szrj
315*38fd1498Szrj emit_insn (prep_seq);
316*38fd1498Szrj emit_insn (gen_seq);
317*38fd1498Szrj
318*38fd1498Szrj tmp = emit_cstore (target, icode, cmp_code, cc_mode, cc_mode,
319*38fd1498Szrj 0, XEXP (tmp, 0), const0_rtx, 1, mode);
320*38fd1498Szrj if (tmp)
321*38fd1498Szrj return tmp;
322*38fd1498Szrj }
323*38fd1498Szrj }
324*38fd1498Szrj /* Clean up. */
325*38fd1498Szrj delete_insns_since (last);
326*38fd1498Szrj return NULL_RTX;
327*38fd1498Szrj }
328