On Tue, Oct 21, 2014 at 4:34 PM, Yuri Rumyantsev <ysrum...@gmail.com> wrote:
> Richard,
>
> In my initial design I did such splitting but before start real
> if-conversion but I decided to not perform it since code size for
> if-converted loop is growing (number of phi nodes is increased). It is
> worth noting also that for phi with #nodes > 2 we need to get all
> predicates (except one) to do phi-predication and it means that block
> containing such phi can have only 1 critical edge.
Can you point me to the patch with the special insertion code then?
I definitely want to avoid the mess we ran into with the reassoc
code "clever" insertion code.
Richard.
> Thanks.
> Yuri.
>
> 2014-10-21 18:19 GMT+04:00 Richard Biener <richard.guent...@gmail.com>:
>> On Tue, Oct 21, 2014 at 4:09 PM, Richard Biener
>> <richard.guent...@gmail.com> wrote:
>>> On Tue, Oct 21, 2014 at 3:58 PM, Yuri Rumyantsev <ysrum...@gmail.com> wrote:
>>>> Richard,
>>>>
>>>> I saw the sources of these functions, but I can't understand why I
>>>> should use something else? Note that all predicate computations are
>>>> located in basic blocks ( by design of if-conv) and there is special
>>>> function that put these computations in bb
>>>> (insert_gimplified_predicates). Edge contains only predicate not its
>>>> computations. New function - find_insertion_point() does very simple
>>>> search - it finds out the latest (in current bb) operand def-stmt of
>>>> predicates taken from all incoming edges.
>>>> In original algorithm the predicate of non-critical edge is taken to
>>>> perform phi-node predication since for critical edge it does not work
>>>> properly.
>>>>
>>>> My question is: does your comments mean that I should re-design my
>>>> extensions?
>>>
>>> Well, we have infrastructure for inserting code on edges and you've
>>> made critical edges predicated correctly. So why re-invent the wheel?
>>> I realize this is very similar to my initial suggestion to simply split
>>> critical edges in loops you want to if-convert but delays splitting
>>> until it turns out to be necessary (which might be good for the
>>> !force_vect case).
>>>
>>> For edge predicates you simply can emit their computation on the
>>> edge, no?
>>>
>>> Btw, I very originally suggested to rework if-conversion to only
>>> record edge predicates - having both block and edge predicates
>>> somewhat complicates the code and makes it harder to
>>> maintain (thus also the suggestion to simply split critical edges
>>> if necessary to make BB predicates work always).
>>>
>>> Your patches add a lot of code and to me it seems we can avoid
>>> doing so much special casing.
>>
>> For example attacking the critical edge issue by a simple
>>
>> Index: tree-if-conv.c
>> ===================================================================
>> --- tree-if-conv.c (revision 216508)
>> +++ tree-if-conv.c (working copy)
>> @@ -980,11 +980,7 @@ if_convertible_bb_p (struct loop *loop,
>> if (EDGE_COUNT (e->src->succs) == 1)
>> found = true;
>> if (!found)
>> - {
>> - if (dump_file && (dump_flags & TDF_DETAILS))
>> - fprintf (dump_file, "only critical predecessors\n");
>> - return false;
>> - }
>> + split_edge (EDGE_PRED (bb, 0));
>> }
>>
>> return true;
>>
>> it changes the number of blocks in the loop, so
>> get_loop_body_in_if_conv_order should probably be re-done with the
>> above eventually signalling that it created a new block. Or the above
>> should populate a vector of edges to split and do that after the
>> loop calling if_convertible_bb_p.
>>
>> Richard.
>>
>>> Richard.
>>>
>>>> Thanks.
>>>> Yuri.
>>>>
>>>> BTW Jeff did initial review of my changes related to predicate
>>>> computation for join blocks. I presented him updated patch with
>>>> test-case and some minor changes in patch. But still did not get any
>>>> feedback on it. Could you please take a look also on it?
>>>>
>>>>
>>>> 2014-10-21 17:38 GMT+04:00 Richard Biener <richard.guent...@gmail.com>:
>>>>> On Tue, Oct 21, 2014 at 3:20 PM, Yuri Rumyantsev <ysrum...@gmail.com>
>>>>> wrote:
>>>>>> Richard,
>>>>>>
>>>>>> Yes, This patch does not make sense since phi node predication for bb
>>>>>> with critical incoming edges only performs another function which is
>>>>>> absent (predicate_extended_scalar_phi).
>>>>>>
>>>>>> BTW I see that commit_edge_insertions() is used for rtx instructions
>>>>>> only but you propose to use it for tree also.
>>>>>> Did I miss something?
>>>>>
>>>>> Ah, it's gsi_commit_edge_inserts () (or gsi_commit_one_edge_insert
>>>>> if you want easy access to the newly created basic block to push
>>>>> the predicate to - see gsi_commit_edge_inserts implementation).
>>>>>
>>>>> Richard.
>>>>>
>>>>>> Thanks ahead.
>>>>>>
>>>>>>
>>>>>> 2014-10-21 16:44 GMT+04:00 Richard Biener <richard.guent...@gmail.com>:
>>>>>>> On Tue, Oct 21, 2014 at 2:25 PM, Yuri Rumyantsev <ysrum...@gmail.com>
>>>>>>> wrote:
>>>>>>>> Richard,
>>>>>>>>
>>>>>>>> I did some changes in patch and ChangeLog to mark that support for
>>>>>>>> if-convert of blocks with only critical incoming edges will be added
>>>>>>>> in the future (more precise in patch.4).
>>>>>>>
>>>>>>> But the same reasoning applies to this version of the patch when
>>>>>>> flag_force_vectorize is true!? (insertion point and invalid SSA form)
>>>>>>>
>>>>>>> Which means the patch doesn't make sense in isolation?
>>>>>>>
>>>>>>> Btw, I think for the case you should simply do gsi_insert_on_edge ()
>>>>>>> and commit_edge_insertions () before the call to combine_blocks
>>>>>>> (pushing the edge predicate to the newly created block).
>>>>>>>
>>>>>>> Richard.
>>>>>>>
>>>>>>>> Could you please review it.
>>>>>>>>
>>>>>>>> Thanks.
>>>>>>>>
>>>>>>>> ChangeLog:
>>>>>>>>
>>>>>>>> 2014-10-21 Yuri Rumyantsev <ysrum...@gmail.com>
>>>>>>>>
>>>>>>>> (flag_force_vectorize): New variable.
>>>>>>>> (edge_predicate): New function.
>>>>>>>> (set_edge_predicate): New function.
>>>>>>>> (add_to_dst_predicate_list): Conditionally invoke add_to_predicate_list
>>>>>>>> if destination block of edge is not always executed. Set-up predicate
>>>>>>>> for critical edge.
>>>>>>>> (if_convertible_phi_p): Accept phi nodes with more than two args
>>>>>>>> if FLAG_FORCE_VECTORIZE was set-up.
>>>>>>>> (ifcvt_can_use_mask_load_store): Use FLAG_FORCE_VECTORIZE.
>>>>>>>> (if_convertible_stmt_p): Fix up pre-function comments.
>>>>>>>> (all_preds_critical_p): New function.
>>>>>>>> (if_convertible_bb_p): Use call of all_preds_critical_p
>>>>>>>> to reject temporarily block if-conversion with incoming critical edges
>>>>>>>> if FLAG_FORCE_VECTORIZE was not set-up. This restriction will be
>>>>>>>> deleted
>>>>>>>> after adding support for extended predication.
>>>>>>>> (predicate_bbs): Skip loop exit block also.Invoke build2_loc
>>>>>>>> to compute predicate instead of fold_build2_loc.
>>>>>>>> Add zeroing of edge 'aux' field.
>>>>>>>> (find_phi_replacement_condition): Extend function interface:
>>>>>>>> it returns NULL if given phi node must be handled by means of
>>>>>>>> extended phi node predication. If number of predecessors of phi-block
>>>>>>>> is equal 2 and at least one incoming edge is not critical original
>>>>>>>> algorithm is used.
>>>>>>>> (tree_if_conversion): Temporarily set-up FLAG_FORCE_VECTORIZE to false.
>>>>>>>> Nullify 'aux' field of edges for blocks with two successors.
>>>>>>>>
>>>>>>>> 2014-10-20 17:55 GMT+04:00 Yuri Rumyantsev <ysrum...@gmail.com>:
>>>>>>>>> Richard,
>>>>>>>>>
>>>>>>>>> Thanks for your answer!
>>>>>>>>>
>>>>>>>>> In current implementation phi node conversion assume that one of
>>>>>>>>> incoming edge to bb containing given phi has at least one non-critical
>>>>>>>>> edge and choose it to insert predicated code. But if we choose
>>>>>>>>> critical edge we need to determine insert point and insertion
>>>>>>>>> direction (before/after) since in other case we can get invalid ssa
>>>>>>>>> form (use before def). This is done by my new function which is not in
>>>>>>>>> current patch ( I will present this patch later). SO I assume that we
>>>>>>>>> need to leave this patch as it is to not introduce new bugs.
>>>>>>>>>
>>>>>>>>> Thanks.
>>>>>>>>> Yuri.
>>>>>>>>>
>>>>>>>>> 2014-10-20 12:00 GMT+04:00 Richard Biener
>>>>>>>>> <richard.guent...@gmail.com>:
>>>>>>>>>> On Fri, Oct 17, 2014 at 4:09 PM, Yuri Rumyantsev
>>>>>>>>>> <ysrum...@gmail.com> wrote:
>>>>>>>>>>> Richard,
>>>>>>>>>>>
>>>>>>>>>>> I reworked the patch as you proposed, but I didn't understand what
>>>>>>>>>>> did you mean by:
>>>>>>>>>>>
>>>>>>>>>>>>So please rework the patch so critical edges are always handled
>>>>>>>>>>>>correctly.
>>>>>>>>>>>
>>>>>>>>>>> In current patch flag_force_vectorize is used (1) to reject phi
>>>>>>>>>>> nodes
>>>>>>>>>>> with more than 2 arguments; (2) to reject basic blocks with only
>>>>>>>>>>> critical incoming edges since support for extended predication of
>>>>>>>>>>> phi
>>>>>>>>>>> nodes will be in next patch.
>>>>>>>>>>
>>>>>>>>>> I mean that (2) should not be rejected dependent on
>>>>>>>>>> flag_force_vectorize.
>>>>>>>>>> It was rejected because if-cvt couldn't handle it correctly before
>>>>>>>>>> but with
>>>>>>>>>> this patch this is fixed. I see no reason to still reject this then
>>>>>>>>>> even
>>>>>>>>>> for !flag_force_vectorize.
>>>>>>>>>>
>>>>>>>>>> Rejecting PHIs with more than two arguments with flag_force_vectorize
>>>>>>>>>> is ok.
>>>>>>>>>>
>>>>>>>>>> Richard.
>>>>>>>>>>
>>>>>>>>>>> Could you please clarify your statement.
>>>>>>>>>>>
>>>>>>>>>>> I attached modified patch.
>>>>>>>>>>>
>>>>>>>>>>> ChangeLog:
>>>>>>>>>>>
>>>>>>>>>>> 2014-10-17 Yuri Rumyantsev <ysrum...@gmail.com>
>>>>>>>>>>>
>>>>>>>>>>> (flag_force_vectorize): New variable.
>>>>>>>>>>> (edge_predicate): New function.
>>>>>>>>>>> (set_edge_predicate): New function.
>>>>>>>>>>> (add_to_dst_predicate_list): Conditionally invoke
>>>>>>>>>>> add_to_predicate_list
>>>>>>>>>>> if destination block of edge is not always executed. Set-up
>>>>>>>>>>> predicate
>>>>>>>>>>> for critical edge.
>>>>>>>>>>> (if_convertible_phi_p): Accept phi nodes with more than two args
>>>>>>>>>>> if FLAG_FORCE_VECTORIZE was set-up.
>>>>>>>>>>> (ifcvt_can_use_mask_load_store): Use FLAG_FORCE_VECTORIZE.
>>>>>>>>>>> (if_convertible_stmt_p): Fix up pre-function comments.
>>>>>>>>>>> (all_edges_are_critical): New function.
>>>>>>>>>>> (if_convertible_bb_p): Use call of all_preds_critical_p
>>>>>>>>>>> to reject block if-conversion with incoming critical edges only if
>>>>>>>>>>> FLAG_FORCE_VECTORIZE was not set-up.
>>>>>>>>>>> (predicate_bbs): Skip loop exit block also.Invoke build2_loc
>>>>>>>>>>> to compute predicate instead of fold_build2_loc.
>>>>>>>>>>> Add zeroing of edge 'aux' field.
>>>>>>>>>>> (find_phi_replacement_condition): Extend function interface:
>>>>>>>>>>> it returns NULL if given phi node must be handled by means of
>>>>>>>>>>> extended phi node predication. If number of predecessors of
>>>>>>>>>>> phi-block
>>>>>>>>>>> is equal 2 and atleast one incoming edge is not critical original
>>>>>>>>>>> algorithm is used.
>>>>>>>>>>> (tree_if_conversion): Temporary set-up FLAG_FORCE_VECTORIZE to
>>>>>>>>>>> false.
>>>>>>>>>>> Nullify 'aux' field of edges for blocks with two successors.
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> 2014-10-17 13:09 GMT+04:00 Richard Biener
>>>>>>>>>>> <richard.guent...@gmail.com>:
>>>>>>>>>>>> On Thu, Oct 16, 2014 at 5:42 PM, Yuri Rumyantsev
>>>>>>>>>>>> <ysrum...@gmail.com> wrote:
>>>>>>>>>>>>> Richard,
>>>>>>>>>>>>>
>>>>>>>>>>>>> Here is reduced patch as you requested. All your remarks have
>>>>>>>>>>>>> been fixed.
>>>>>>>>>>>>> Could you please look at it ( I have already sent the patch with
>>>>>>>>>>>>> changes in add_to_predicate_list for review).
>>>>>>>>>>>>
>>>>>>>>>>>> + if (dump_file && (dump_flags & TDF_DETAILS))
>>>>>>>>>>>> + fprintf (dump_file, "More than two phi node
>>>>>>>>>>>> args.\n");
>>>>>>>>>>>> + return false;
>>>>>>>>>>>> + }
>>>>>>>>>>>> +
>>>>>>>>>>>> + }
>>>>>>>>>>>>
>>>>>>>>>>>> Excess vertical space.
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> +/* Assumes that BB has more than 2 predecessors.
>>>>>>>>>>>>
>>>>>>>>>>>> More than 1 predecessor?
>>>>>>>>>>>>
>>>>>>>>>>>> + Returns false if at least one successor is not on critical edge
>>>>>>>>>>>> + and true otherwise. */
>>>>>>>>>>>> +
>>>>>>>>>>>> +static inline bool
>>>>>>>>>>>> +all_edges_are_critical (basic_block bb)
>>>>>>>>>>>> +{
>>>>>>>>>>>>
>>>>>>>>>>>> "all_preds_critical_p" would be a better name
>>>>>>>>>>>>
>>>>>>>>>>>> + if (EDGE_COUNT (bb->preds) > 2)
>>>>>>>>>>>> + {
>>>>>>>>>>>> + if (!flag_force_vectorize)
>>>>>>>>>>>> + return false;
>>>>>>>>>>>> + }
>>>>>>>>>>>>
>>>>>>>>>>>> as I said in the last review I don't think we should restrict edge
>>>>>>>>>>>> predicates to flag_force_vectorize. At least I can't see how
>>>>>>>>>>>> if-conversion is magically more expensive for that case?
>>>>>>>>>>>>
>>>>>>>>>>>> So please rework the patch so critical edges are always handled
>>>>>>>>>>>> correctly.
>>>>>>>>>>>>
>>>>>>>>>>>> Ok with that and the above suggested changes.
>>>>>>>>>>>>
>>>>>>>>>>>> Thanks,
>>>>>>>>>>>> Richard.
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>> Thanks.
>>>>>>>>>>>>> Yuri.
>>>>>>>>>>>>> ChangeLog
>>>>>>>>>>>>> 2014-10-16 Yuri Rumyantsev <ysrum...@gmail.com>
>>>>>>>>>>>>>
>>>>>>>>>>>>> (flag_force_vectorize): New variable.
>>>>>>>>>>>>> (edge_predicate): New function.
>>>>>>>>>>>>> (set_edge_predicate): New function.
>>>>>>>>>>>>> (add_to_dst_predicate_list): Conditionally invoke
>>>>>>>>>>>>> add_to_predicate_list
>>>>>>>>>>>>> if destination block of edge is not always executed. Set-up
>>>>>>>>>>>>> predicate
>>>>>>>>>>>>> for critical edge.
>>>>>>>>>>>>> (if_convertible_phi_p): Accept phi nodes with more than two args
>>>>>>>>>>>>> if FLAG_FORCE_VECTORIZE was set-up.
>>>>>>>>>>>>> (ifcvt_can_use_mask_load_store): Use FLAG_FORCE_VECTORIZE.
>>>>>>>>>>>>> (if_convertible_stmt_p): Fix up pre-function comments.
>>>>>>>>>>>>> (all_edges_are_critical): New function.
>>>>>>>>>>>>> (if_convertible_bb_p): Allow bb has more than two predecessors if
>>>>>>>>>>>>> FLAG_FORCE_VECTORIZE was set-up. Use call of
>>>>>>>>>>>>> all_edges_are_critical
>>>>>>>>>>>>> to reject block if-conversion with incoming critical edges only if
>>>>>>>>>>>>> FLAG_FORCE_VECTORIZE was not set-up.
>>>>>>>>>>>>> (predicate_bbs): Skip loop exit block also.Invoke build2_loc
>>>>>>>>>>>>> to compute predicate instead of fold_build2_loc.
>>>>>>>>>>>>> Add zeroing of edge 'aux' field.
>>>>>>>>>>>>> (find_phi_replacement_condition): Extend function interface:
>>>>>>>>>>>>> it returns NULL if given phi node must be handled by means of
>>>>>>>>>>>>> extended phi node predication. If number of predecessors of
>>>>>>>>>>>>> phi-block
>>>>>>>>>>>>> is equal 2 and atleast one incoming edge is not critical original
>>>>>>>>>>>>> algorithm is used.
>>>>>>>>>>>>> (tree_if_conversion): Temporary set-up FLAG_FORCE_VECTORIZE to
>>>>>>>>>>>>> false.
>>>>>>>>>>>>> Nullify 'aux' field of edges for blocks with two successors.
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> 2014-10-15 13:50 GMT+04:00 Richard Biener
>>>>>>>>>>>>> <richard.guent...@gmail.com>:
>>>>>>>>>>>>>> On Mon, Oct 13, 2014 at 11:38 AM, Yuri Rumyantsev
>>>>>>>>>>>>>> <ysrum...@gmail.com> wrote:
>>>>>>>>>>>>>>> Richard,
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> Here is updated patch (part1) for extended if conversion.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> Second part of patch will be sent later.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> Ok, I'm starting to look at this. I'd still like you to split
>>>>>>>>>>>>>> things up
>>>>>>>>>>>>>> more.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> static inline void
>>>>>>>>>>>>>> add_to_predicate_list (struct loop *loop, basic_block bb, tree
>>>>>>>>>>>>>> nc)
>>>>>>>>>>>>>> {
>>>>>>>>>>>>>> ...
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> + /* We use notion of cd equivalence to get simplier
>>>>>>>>>>>>>> predicate for
>>>>>>>>>>>>>> + join block, e.g. if join block has 2 predecessors with
>>>>>>>>>>>>>> predicates
>>>>>>>>>>>>>> + p1 & p2 and p1 & !p2, we'd like to get p1 for it
>>>>>>>>>>>>>> instead of
>>>>>>>>>>>>>> + p1 & p2 | p1 & !p2. */
>>>>>>>>>>>>>> + if (dom_bb != loop->header
>>>>>>>>>>>>>> + && get_immediate_dominator (CDI_POST_DOMINATORS,
>>>>>>>>>>>>>> dom_bb) == bb)
>>>>>>>>>>>>>> + {
>>>>>>>>>>>>>> + gcc_assert (flow_bb_inside_loop_p (loop, dom_bb));
>>>>>>>>>>>>>> + bc = bb_predicate (dom_bb);
>>>>>>>>>>>>>> + gcc_assert (!is_true_predicate (bc));
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> these changes look worthwhile even for !flag_force_vectorize.
>>>>>>>>>>>>>> So please
>>>>>>>>>>>>>> split the change to add_to_predicate_list out and compute
>>>>>>>>>>>>>> post-dominators
>>>>>>>>>>>>>> unconditionally. Note that you should call free_dominance_info
>>>>>>>>>>>>>> (CDI_POST_DOMINATORS) at the end of if-conversion.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> + if (!dominated_by_p (CDI_DOMINATORS, loop->latch, e->dest))
>>>>>>>>>>>>>> + add_to_predicate_list (loop, e->dest, cond);
>>>>>>>>>>>>>> +
>>>>>>>>>>>>>> + /* If edge E is critical save predicate on it. */
>>>>>>>>>>>>>> + if (EDGE_COUNT (e->dest->preds) >= 2)
>>>>>>>>>>>>>> + set_edge_predicate (e, cond);
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> how do we know the edge is critical by this simple check? Why
>>>>>>>>>>>>>> not
>>>>>>>>>>>>>> simply always save edge predicates (well, you kind of do but omit
>>>>>>>>>>>>>> the case where e->src dominates e->dest).
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> Btw, you can rely on edge->aux being NULL at the start of the
>>>>>>>>>>>>>> pass but need to clear it at the end (best use
>>>>>>>>>>>>>> clear_aux_for_edges ()
>>>>>>>>>>>>>> for that). So stuff like
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> + extract_true_false_edges_from_block (bb, &true_edge,
>>>>>>>>>>>>>> &false_edge);
>>>>>>>>>>>>>> + if (flag_force_vectorize)
>>>>>>>>>>>>>> + true_edge->aux = false_edge->aux = NULL;
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> shouldn't be necessary.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> I think the edge predicate handling should also be
>>>>>>>>>>>>>> unconditionally
>>>>>>>>>>>>>> and not depend on flag_force_vectorize.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> + /* The loop latch and loop exit block are always executed
>>>>>>>>>>>>>> and
>>>>>>>>>>>>>> + have no extra conditions to be processed: skip them. */
>>>>>>>>>>>>>> + if (bb == loop->latch
>>>>>>>>>>>>>> + || bb_with_exit_edge_p (loop, bb))
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> I don't think the edge stuff is true - given you still only
>>>>>>>>>>>>>> reset the
>>>>>>>>>>>>>> loop->latch bb predicate the change looks broken.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> + /* Fold_build2 can produce bool conversion which is not
>>>>>>>>>>>>>> + supported by vectorizer, so re-build it without
>>>>>>>>>>>>>> folding.
>>>>>>>>>>>>>> + For example, such conversion is generated for
>>>>>>>>>>>>>> sequence:
>>>>>>>>>>>>>> + _Bool _7, _8, _9;
>>>>>>>>>>>>>> + _7 = _6 != 13; _8 = _6 != 0; _9 = _8 & _9;
>>>>>>>>>>>>>> + if (_9 != 0) --> (bool)_9. */
>>>>>>>>>>>>>> +
>>>>>>>>>>>>>> + if (CONVERT_EXPR_P (c)
>>>>>>>>>>>>>> + && TREE_CODE_CLASS (code) == tcc_comparison)
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> I think you should simply use canonicalize_cond_expr_cond on the
>>>>>>>>>>>>>> folding result. Or rather _not_ fold at all - we are taking the
>>>>>>>>>>>>>> operands from the GIMPLE condition unmodified after all.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> - add_to_dst_predicate_list (loop, false_edge,
>>>>>>>>>>>>>> - unshare_expr (cond), c2);
>>>>>>>>>>>>>> + add_to_dst_predicate_list (loop, false_edge,
>>>>>>>>>>>>>> unshare_expr (cond),
>>>>>>>>>>>>>> + unshare_expr (c2));
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> why is it necessary to unshare c2?
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> Please split out the PHI-with-multi-arg handling (I have not
>>>>>>>>>>>>>> looked at
>>>>>>>>>>>>>> that in detail).
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> Thanks,
>>>>>>>>>>>>>> Richard.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> Changelog.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> 2014-10-13 Yuri Rumyantsev <ysrum...@gmail.com>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> * tree-if-conv.c (cgraph.h): Add include file to detect
>>>>>>>>>>>>>>> function clone.
>>>>>>>>>>>>>>> (flag_force_vectorize): New variable.
>>>>>>>>>>>>>>> (edge_predicate): New function.
>>>>>>>>>>>>>>> (set_edge_predicate): New function.
>>>>>>>>>>>>>>> (add_to_predicate_list): Check unconditionally that bb is always
>>>>>>>>>>>>>>> executed to early exit. Use predicate of cd-equivalent block
>>>>>>>>>>>>>>> for join blocks if it exists.
>>>>>>>>>>>>>>> (add_to_dst_predicate_list): Invoke add_to_predicate_list if
>>>>>>>>>>>>>>> destination block of edge is not always executed. Set-up
>>>>>>>>>>>>>>> predicate
>>>>>>>>>>>>>>> for critical edge.
>>>>>>>>>>>>>>> (if_convertible_phi_p): Accept phi nodes with more than two args
>>>>>>>>>>>>>>> if FLAG_FORCE_VECTORIZE was set-up.
>>>>>>>>>>>>>>> (ifcvt_can_use_mask_load_store): Use FLAG_FORCE_VECTORIZE.
>>>>>>>>>>>>>>> (if_convertible_stmt_p): Fix up pre-function comments.
>>>>>>>>>>>>>>> (all_edges_are_critical): New function.
>>>>>>>>>>>>>>> (if_convertible_bb_p): Allow bb has more than two predecessors
>>>>>>>>>>>>>>> if
>>>>>>>>>>>>>>> FLAG_FORCE_VECTORIZE was set-up. Use call of
>>>>>>>>>>>>>>> all_edges_are_critical
>>>>>>>>>>>>>>> to reject block if-conversion with incoming critical edges only
>>>>>>>>>>>>>>> if
>>>>>>>>>>>>>>> FLAG_FORCE_VECTORIZE was not set-up.
>>>>>>>>>>>>>>> (predicate_bbs): Skip loop exit block also. Add check that if
>>>>>>>>>>>>>>> fold_build2 produces bool conversion, recompute predicate using
>>>>>>>>>>>>>>> build2_loc. Add zeroing of edge 'aux' field under
>>>>>>>>>>>>>>> FLAG_FORCE_VECTORIZE.
>>>>>>>>>>>>>>> (if_convertible_loop_p_1): Recompute POST_DOMINATOR tree if
>>>>>>>>>>>>>>> FLAG_FORCE_VECTORIZE was set-up to calculate cd equivalent bb's.
>>>>>>>>>>>>>>> (find_phi_replacement_condition): Extend function interface:
>>>>>>>>>>>>>>> it returns NULL if given phi node must be handled by means of
>>>>>>>>>>>>>>> extended phi node predication. If number of predecessors of
>>>>>>>>>>>>>>> phi-block
>>>>>>>>>>>>>>> is equal 2 and atleast one incoming edge is not critical
>>>>>>>>>>>>>>> original
>>>>>>>>>>>>>>> algorithm is used.
>>>>>>>>>>>>>>> (get_predicate_for_edge): New function.
>>>>>>>>>>>>>>> (find_insertion_point): New function.
>>>>>>>>>>>>>>> (predicate_arbitrary_scalar_phi): New function.
>>>>>>>>>>>>>>> (predicate_all_scalar_phis): Introduce new variable BEFORE.
>>>>>>>>>>>>>>> Invoke find_insertion_point to initialize gsi and
>>>>>>>>>>>>>>> predicate_arbitrary_scalar_phi if TRUE_BB is NULL - it signals
>>>>>>>>>>>>>>> that extended predication must be applied).
>>>>>>>>>>>>>>> (insert_gimplified_predicates): Add test for non-predicated
>>>>>>>>>>>>>>> basic
>>>>>>>>>>>>>>> blocks that there are no gimplified statements to insert. Insert
>>>>>>>>>>>>>>> predicates at the block begining for extended if-conversion.
>>>>>>>>>>>>>>> (tree_if_conversion): Initialize flag_force_vectorize from
>>>>>>>>>>>>>>> current
>>>>>>>>>>>>>>> loop or outer loop (to support pragma omp declare).Do loop
>>>>>>>>>>>>>>> versioning
>>>>>>>>>>>>>>> for innermost loop marked with pragma omp simd and
>>>>>>>>>>>>>>> FLAG_TREE_LOOP_IF_CONVERT was not sett-up. Nullify 'aux' field
>>>>>>>>>>>>>>> of edges
>>>>>>>>>>>>>>> for blocks with two successors.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> 2014-09-22 12:28 GMT+04:00 Yuri Rumyantsev <ysrum...@gmail.com>:
>>>>>>>>>>>>>>>> Richard,
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> here is reduced patch (part.1) which was reduced almost twice.
>>>>>>>>>>>>>>>> Let's me also answer on your comments.
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> 1. I really use edge field 'aux' to keep predicate for
>>>>>>>>>>>>>>>> critical edges.
>>>>>>>>>>>>>>>> My previous code was not correct and now it looks like:
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> if (EDGE_COUNT (b->succs) == 1 || EDGE_COUNT
>>>>>>>>>>>>>>>> (e->dest->preds) == 1)
>>>>>>>>>>>>>>>> /* Edge E is not critical, use predicate of edge source
>>>>>>>>>>>>>>>> bb. */
>>>>>>>>>>>>>>>> c = bb_predicate (b);
>>>>>>>>>>>>>>>> else
>>>>>>>>>>>>>>>> /* Edge E is critical and its aux field contains
>>>>>>>>>>>>>>>> predicate. */
>>>>>>>>>>>>>>>> c = edge_predicate (e);
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> 2. I completely delete all code related to creation of
>>>>>>>>>>>>>>>> conditional
>>>>>>>>>>>>>>>> expressions and completely rely on bool pattern recognition in
>>>>>>>>>>>>>>>> vectorizer. But we need to delete all dead predicate
>>>>>>>>>>>>>>>> computations
>>>>>>>>>>>>>>>> which are not used since they prevent vectorization. I will
>>>>>>>>>>>>>>>> add this
>>>>>>>>>>>>>>>> local-dce function in next patch.
>>>>>>>>>>>>>>>> 3. I also did not include in this patch recognition of general
>>>>>>>>>>>>>>>> phi-nodes with two arguments only for which conversion of
>>>>>>>>>>>>>>>> conditional
>>>>>>>>>>>>>>>> scalar reduction can be applied also.
>>>>>>>>>>>>>>>> Note that all these changes are applied for loop marked with
>>>>>>>>>>>>>>>> pragma
>>>>>>>>>>>>>>>> omp simd only.
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> 2014-09-22 Yuri Rumyantsev <ysrum...@gmail.com>
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> * tree-if-conv.c (cgraph.h): Add include file to detect
>>>>>>>>>>>>>>>> function clone.
>>>>>>>>>>>>>>>> (flag_force_vectorize): New variable.
>>>>>>>>>>>>>>>> (edge_predicate): New function.
>>>>>>>>>>>>>>>> (set_edge_predicate): New function.
>>>>>>>>>>>>>>>> (convert_name_to_cmp): New function.
>>>>>>>>>>>>>>>> (add_to_predicate_list): Check unconditionally that bb is
>>>>>>>>>>>>>>>> always
>>>>>>>>>>>>>>>> executed to early exit. Use predicate of cd-equivalent block
>>>>>>>>>>>>>>>> for join blocks if it exists.
>>>>>>>>>>>>>>>> (add_to_dst_predicate_list): Invoke add_to_predicate_list if
>>>>>>>>>>>>>>>> destination block of edge is not always executed. Set-up
>>>>>>>>>>>>>>>> predicate
>>>>>>>>>>>>>>>> for critical edge.
>>>>>>>>>>>>>>>> (if_convertible_phi_p): Accept phi nodes with more than two
>>>>>>>>>>>>>>>> args
>>>>>>>>>>>>>>>> if FLAG_FORCE_VECTORIZE was set-up.
>>>>>>>>>>>>>>>> (ifcvt_can_use_mask_load_store): Use FLAG_FORCE_VECTORIZE.
>>>>>>>>>>>>>>>> (if_convertible_stmt_p): Fix up pre-function comments.
>>>>>>>>>>>>>>>> (all_edges_are_critical): New function.
>>>>>>>>>>>>>>>> (if_convertible_bb_p): Allow bb has more than two predecessors
>>>>>>>>>>>>>>>> if
>>>>>>>>>>>>>>>> FLAG_FORCE_VECTORIZE was set-up. Use call of
>>>>>>>>>>>>>>>> all_edges_are_critical
>>>>>>>>>>>>>>>> to reject block if-conversion with incoming critical edges
>>>>>>>>>>>>>>>> only if
>>>>>>>>>>>>>>>> FLAG_FORCE_VECTORIZE was not set-up.
>>>>>>>>>>>>>>>> (predicate_bbs): Skip loop exit block also. Add check that if
>>>>>>>>>>>>>>>> fold_build2 produces bool conversion, recompute predicate using
>>>>>>>>>>>>>>>> build2_loc. Add zeroing of edge 'aux' field under
>>>>>>>>>>>>>>>> FLAG_FORCE_VECTORIZE.
>>>>>>>>>>>>>>>> (if_convertible_loop_p_1): Recompute POST_DOMINATOR tree if
>>>>>>>>>>>>>>>> FLAG_FORCE_VECTORIZE was set-up to calculate cd equivalent
>>>>>>>>>>>>>>>> bb's.
>>>>>>>>>>>>>>>> (find_phi_replacement_condition): Extend function interface:
>>>>>>>>>>>>>>>> it returns NULL if given phi node must be handled by means of
>>>>>>>>>>>>>>>> extended phi node predication. If number of predecessors of
>>>>>>>>>>>>>>>> phi-block
>>>>>>>>>>>>>>>> is equal 2 and atleast one incoming edge is not critical
>>>>>>>>>>>>>>>> original
>>>>>>>>>>>>>>>> algorithm is used.
>>>>>>>>>>>>>>>> (get_predicate_for_edge): New function.
>>>>>>>>>>>>>>>> (find_insertion_point): New function.
>>>>>>>>>>>>>>>> (predicate_arbitrary_scalar_phi): New function.
>>>>>>>>>>>>>>>> (predicate_all_scalar_phis): Introduce new variable BEFORE.
>>>>>>>>>>>>>>>> Invoke find_insertion_point to initialize gsi and
>>>>>>>>>>>>>>>> predicate_arbitrary_scalar_phi if TRUE_BB is NULL - it signals
>>>>>>>>>>>>>>>> that extended predication must be applied).
>>>>>>>>>>>>>>>> (insert_gimplified_predicates): Add test for non-predicated
>>>>>>>>>>>>>>>> basic
>>>>>>>>>>>>>>>> blocks that there are no gimplified statements to insert.
>>>>>>>>>>>>>>>> Insert
>>>>>>>>>>>>>>>> predicates at the block begining for extended if-conversion.
>>>>>>>>>>>>>>>> (tree_if_conversion): Initialize flag_force_vectorize from
>>>>>>>>>>>>>>>> current
>>>>>>>>>>>>>>>> loop or outer loop (to support pragma omp declare).Do loop
>>>>>>>>>>>>>>>> versioning
>>>>>>>>>>>>>>>> for innermost loop marked with pragma omp simd and
>>>>>>>>>>>>>>>> FLAG_TREE_LOOP_IF_CONVERT was not sett-up. Nullify 'aux' field
>>>>>>>>>>>>>>>> of edges
>>>>>>>>>>>>>>>> for blocks with two successors.
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> 2014-09-08 17:10 GMT+04:00 Richard Biener
>>>>>>>>>>>>>>>> <richard.guent...@gmail.com>:
>>>>>>>>>>>>>>>>> On Fri, Aug 15, 2014 at 2:02 PM, Yuri Rumyantsev
>>>>>>>>>>>>>>>>> <ysrum...@gmail.com> wrote:
>>>>>>>>>>>>>>>>>> Richard!
>>>>>>>>>>>>>>>>>> Here is updated patch with the following changes:
>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>> 1. Any restrictions on phi-function were eliminated for
>>>>>>>>>>>>>>>>>> extended conversion.
>>>>>>>>>>>>>>>>>> 2. Put predicate for critical edges to 'aux' field of edge,
>>>>>>>>>>>>>>>>>> i.e.
>>>>>>>>>>>>>>>>>> negate_predicate was deleted.
>>>>>>>>>>>>>>>>>> 3. Deleted splitting of critical edges, i.e. both outgoing
>>>>>>>>>>>>>>>>>> edges can
>>>>>>>>>>>>>>>>>> be critical.
>>>>>>>>>>>>>>>>>> 4. Use notion of cd-equivalence to set-up predicate for join
>>>>>>>>>>>>>>>>>> basic
>>>>>>>>>>>>>>>>>> blocks to simplify it.
>>>>>>>>>>>>>>>>>> 5. I decided to not design pre-pass since it will lead
>>>>>>>>>>>>>>>>>> generating
>>>>>>>>>>>>>>>>>> chain of cond expressions for phi-node if conversion,
>>>>>>>>>>>>>>>>>> whereas for phi
>>>>>>>>>>>>>>>>>> of kind
>>>>>>>>>>>>>>>>>> x = PHI <1(2), 1(3), 2(4)>
>>>>>>>>>>>>>>>>>> only one cond expression is required and this is considered
>>>>>>>>>>>>>>>>>> as simple
>>>>>>>>>>>>>>>>>> optimization for arbitrary phi-function. More precise,
>>>>>>>>>>>>>>>>>> if phi-function have only two different arguments and one of
>>>>>>>>>>>>>>>>>> them has
>>>>>>>>>>>>>>>>>> single occurrence, if- conversion is performed as if phi
>>>>>>>>>>>>>>>>>> have only 2
>>>>>>>>>>>>>>>>>> arguments.
>>>>>>>>>>>>>>>>>> For arbitrary phi function a chain of cond expressions is
>>>>>>>>>>>>>>>>>> produced.
>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>> Updated patch is attached.
>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>> Any comments will be appreciated.
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>> The patch is still very big and does multiple things at once
>>>>>>>>>>>>>>>>> which makes
>>>>>>>>>>>>>>>>> it hard to review.
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>> In addition to that it changes function singatures without
>>>>>>>>>>>>>>>>> updating
>>>>>>>>>>>>>>>>> the function comments. For example what is the convert_bool
>>>>>>>>>>>>>>>>> argument doing to add_to_dst_predicate_list? Why do we need
>>>>>>>>>>>>>>>>> all this added logic.
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>> You duplicate operand_equal_for_phi_arg_p.
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>> I think the code handling PHIs with more than two operands but
>>>>>>>>>>>>>>>>> only two unequal operands is useful generally, so that's an
>>>>>>>>>>>>>>>>> obvious
>>>>>>>>>>>>>>>>> candidate for splitting out into a separate patch.
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>> + CONVERT_BOOL argument was added to convert bool predicate
>>>>>>>>>>>>>>>>> computations
>>>>>>>>>>>>>>>>> + which is not supported by vectorizer to int type through
>>>>>>>>>>>>>>>>> creating of
>>>>>>>>>>>>>>>>> + conditional expressions. */
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>> Example? The vectorizer has patterns for bool predicate
>>>>>>>>>>>>>>>>> computations.
>>>>>>>>>>>>>>>>> This seems to be another feature that needs splitting out.
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>> The way you get around the critical edge parts looks awkward
>>>>>>>>>>>>>>>>> to me.
>>>>>>>>>>>>>>>>> Please either do _all_ predicates as edge predicates or simply
>>>>>>>>>>>>>>>>> split critical edges (of the respective loop body).
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>> I still think that an utility doing same PHI arg merging by
>>>>>>>>>>>>>>>>> introducing
>>>>>>>>>>>>>>>>> forwarder blocks would be nicer to have.
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>> I'd restructure the main tree_if_conversion function to apply
>>>>>>>>>>>>>>>>> these
>>>>>>>>>>>>>>>>> CFG pre-transforms when we are going to version the loop
>>>>>>>>>>>>>>>>> for if conversion (eventually transitioning to always doing
>>>>>>>>>>>>>>>>> that).
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>> So - please split up the patch. It's way too big.
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>> Thanks,
>>>>>>>>>>>>>>>>> Richard.
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>> 2014-08-15 Yuri Rumyantsev <ysrum...@gmail.com>
>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>> * tree-if-conv.c (cgraph.h): Add include file to detect
>>>>>>>>>>>>>>>>>> function clone.
>>>>>>>>>>>>>>>>>> (flag_force_vectorize): New variable.
>>>>>>>>>>>>>>>>>> (edge_predicate): New function.
>>>>>>>>>>>>>>>>>> (set_edge_predicate): New function.
>>>>>>>>>>>>>>>>>> (add_stmt_to_bb_predicate_gimplified_stmts): New function.
>>>>>>>>>>>>>>>>>> (init_bb_predicate): Add initialization of negate_predicate
>>>>>>>>>>>>>>>>>> field.
>>>>>>>>>>>>>>>>>> (reset_bb_predicate): Reset negate_predicate to NULL_TREE.
>>>>>>>>>>>>>>>>>> (convert_name_to_cmp): New function.
>>>>>>>>>>>>>>>>>> (get_type_for_cond): New function.
>>>>>>>>>>>>>>>>>> (convert_bool_predicate): New function.
>>>>>>>>>>>>>>>>>> (predicate_disjunction): New function.
>>>>>>>>>>>>>>>>>> (predicate_conjunction): New function.
>>>>>>>>>>>>>>>>>> (add_to_predicate_list): Add convert_bool argument.
>>>>>>>>>>>>>>>>>> Use predicate of cd-equivalent block if convert_bool is true
>>>>>>>>>>>>>>>>>> and
>>>>>>>>>>>>>>>>>> such bb exists; save it in static variable for further
>>>>>>>>>>>>>>>>>> possible use.
>>>>>>>>>>>>>>>>>> Add call of predicate_disjunction if convert_bool argument
>>>>>>>>>>>>>>>>>> is true.
>>>>>>>>>>>>>>>>>> (add_to_dst_predicate_list): Add convert_bool argument.
>>>>>>>>>>>>>>>>>> Add early function exit if edge target block is always
>>>>>>>>>>>>>>>>>> executed.
>>>>>>>>>>>>>>>>>> Add call of predicate_conjunction if convert_bool argument
>>>>>>>>>>>>>>>>>> is true.
>>>>>>>>>>>>>>>>>> Pass convert_bool argument for add_to_predicate_list.
>>>>>>>>>>>>>>>>>> Set-up predicate for crritical edge if convert_bool is true.
>>>>>>>>>>>>>>>>>> (equal_phi_args): New function.
>>>>>>>>>>>>>>>>>> (phi_has_two_different_args): New function.
>>>>>>>>>>>>>>>>>> (if_convertible_phi_p): Accept phi nodes with more than two
>>>>>>>>>>>>>>>>>> args
>>>>>>>>>>>>>>>>>> if flag_force_vectorize wa set-up.
>>>>>>>>>>>>>>>>>> (ifcvt_can_use_mask_load_store): Add test on
>>>>>>>>>>>>>>>>>> flag_force_vectorize.
>>>>>>>>>>>>>>>>>> (if_convertible_stmt_p): Allow calls of function clones if
>>>>>>>>>>>>>>>>>> flag_force_vectorize was set-up.
>>>>>>>>>>>>>>>>>> (all_edges_are_critical): New function.
>>>>>>>>>>>>>>>>>> (if_convertible_bb_p): Allow bb has more than two
>>>>>>>>>>>>>>>>>> predecessors if
>>>>>>>>>>>>>>>>>> flag_force_vectorize was set-up. Use call of
>>>>>>>>>>>>>>>>>> all_edges_are_critical
>>>>>>>>>>>>>>>>>> to reject block if-conversion with imcoming critical edges
>>>>>>>>>>>>>>>>>> only if
>>>>>>>>>>>>>>>>>> flag_force_vectorize was not set-up.
>>>>>>>>>>>>>>>>>> (walk_cond_tree): New function.
>>>>>>>>>>>>>>>>>> (vect_bool_pattern_is_applicable): New function.
>>>>>>>>>>>>>>>>>> (predicate_bbs): Add convert_bool argument which is used to
>>>>>>>>>>>>>>>>>> transform
>>>>>>>>>>>>>>>>>> comparison expressions of boolean type into conditional
>>>>>>>>>>>>>>>>>> expressions
>>>>>>>>>>>>>>>>>> with integral operands. If convert_bool argument was set-up
>>>>>>>>>>>>>>>>>> and
>>>>>>>>>>>>>>>>>> vect bool pattern can be appied perform the following
>>>>>>>>>>>>>>>>>> transformation:
>>>>>>>>>>>>>>>>>> (bool) x != 0 --> y = (int) x; x != 0;
>>>>>>>>>>>>>>>>>> Add check that if fold_build2 produces bool conversion if
>>>>>>>>>>>>>>>>>> convert_bool
>>>>>>>>>>>>>>>>>> was set-up, recompute predicate using build2_loc. Additional
>>>>>>>>>>>>>>>>>> argument
>>>>>>>>>>>>>>>>>> 'convert_bool" is passed to add_to_dst_predicate_list and
>>>>>>>>>>>>>>>>>> add_to_predicate_list.
>>>>>>>>>>>>>>>>>> (if_convertible_loop_p_1): Recompute POST_DOMINATOR tree if
>>>>>>>>>>>>>>>>>> flag_force_vectorize was set-up to calculate cd equivalent
>>>>>>>>>>>>>>>>>> bb's.
>>>>>>>>>>>>>>>>>> Call predicate_bbs with additional argument equal to false.
>>>>>>>>>>>>>>>>>> (find_phi_replacement_condition): Extend function interface:
>>>>>>>>>>>>>>>>>> it returns NULL if given phi node must be handled by means of
>>>>>>>>>>>>>>>>>> extended phi node predication. If number of predecessors of
>>>>>>>>>>>>>>>>>> phi-block
>>>>>>>>>>>>>>>>>> is equal 2 and atleast one incoming edge is not critical
>>>>>>>>>>>>>>>>>> original
>>>>>>>>>>>>>>>>>> algorithm is used.
>>>>>>>>>>>>>>>>>> (is_cond_scalar_reduction): Add 'extended' argument which
>>>>>>>>>>>>>>>>>> signals that
>>>>>>>>>>>>>>>>>> phi arguments must be evaluated through
>>>>>>>>>>>>>>>>>> phi_has_two_different_args.
>>>>>>>>>>>>>>>>>> (predicate_scalar_phi): Add invoсation of
>>>>>>>>>>>>>>>>>> convert_name_to_cmp if cond
>>>>>>>>>>>>>>>>>> is SSA_NAME. Add 'false' argument to call of
>>>>>>>>>>>>>>>>>> is_cond_scalar_reduction.
>>>>>>>>>>>>>>>>>> (get_predicate_for_edge): New function.
>>>>>>>>>>>>>>>>>> (find_insertion_point): New function.
>>>>>>>>>>>>>>>>>> (predicate_arbitrary_phi): New function.
>>>>>>>>>>>>>>>>>> (predicate_extended_scalar_phi): New function.
>>>>>>>>>>>>>>>>>> (predicate_all_scalar_phis): Add code to set-up gimple
>>>>>>>>>>>>>>>>>> statement
>>>>>>>>>>>>>>>>>> iterator for predication of extended scalar phi's for
>>>>>>>>>>>>>>>>>> insertion.
>>>>>>>>>>>>>>>>>> (insert_gimplified_predicates): Add test for non-predicated
>>>>>>>>>>>>>>>>>> basic
>>>>>>>>>>>>>>>>>> blocks that there are no gimplified statements to insert.
>>>>>>>>>>>>>>>>>> Insert
>>>>>>>>>>>>>>>>>> predicates at the block begining for extended if-conversion.
>>>>>>>>>>>>>>>>>> (predicate_mem_writes): Invoke convert_name_to_cmp for
>>>>>>>>>>>>>>>>>> extended
>>>>>>>>>>>>>>>>>> predication to build mask.
>>>>>>>>>>>>>>>>>> (combine_blocks): Pass flag_force_vectorize to predicate_bbs.
>>>>>>>>>>>>>>>>>> (tree_if_conversion): Initialize flag_force_vectorize from
>>>>>>>>>>>>>>>>>> current
>>>>>>>>>>>>>>>>>> loop or outer loop (to support pragma omp declare).Do loop
>>>>>>>>>>>>>>>>>> versioning
>>>>>>>>>>>>>>>>>> for innermost loop marked with pragma omp simd.
>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>> 2014-08-01 13:40 GMT+04:00 Richard Biener
>>>>>>>>>>>>>>>>>> <richard.guent...@gmail.com>:
>>>>>>>>>>>>>>>>>>> On Wed, Jun 25, 2014 at 4:06 PM, Yuri Rumyantsev
>>>>>>>>>>>>>>>>>>> <ysrum...@gmail.com> wrote:
>>>>>>>>>>>>>>>>>>>> Hi All,
>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>> We implemented additional support for pragma omp simd in
>>>>>>>>>>>>>>>>>>>> part of
>>>>>>>>>>>>>>>>>>>> extended if-conversion loops with such pragma. These
>>>>>>>>>>>>>>>>>>>> extensions
>>>>>>>>>>>>>>>>>>>> include:
>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>> 1. All extensions are performed only if considered loop or
>>>>>>>>>>>>>>>>>>>> its outer
>>>>>>>>>>>>>>>>>>>> loop was marked with pragma omp simd (force_vectorize);
>>>>>>>>>>>>>>>>>>>> For ordinary
>>>>>>>>>>>>>>>>>>>> loops behavior was not changed.
>>>>>>>>>>>>>>>>>>>> 2. Took off cfg restriction on basic block which can have
>>>>>>>>>>>>>>>>>>>> more than 2
>>>>>>>>>>>>>>>>>>>> predecessors.
>>>>>>>>>>>>>>>>>>>> 3. Put additional restriction on phi nodes which was
>>>>>>>>>>>>>>>>>>>> missed in current design:
>>>>>>>>>>>>>>>>>>>> all phi nodes must be in non-predicated basic block to
>>>>>>>>>>>>>>>>>>>> conform
>>>>>>>>>>>>>>>>>>>> semantic of COND_EXPR which is used for transformation.
>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>> How is that so? If the PHI is predicated then its result
>>>>>>>>>>>>>>>>>>> will be used
>>>>>>>>>>>>>>>>>>> in a PHI node again and thus we'd create a sequence of
>>>>>>>>>>>>>>>>>>> COND_EXPRs.
>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>> No?
>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>> 4. Extend predication of phi nodes: phi may have more than
>>>>>>>>>>>>>>>>>>>> 2 arguments
>>>>>>>>>>>>>>>>>>>> with some limitations:
>>>>>>>>>>>>>>>>>>>> - for phi nodes which have more than 2 arguments, but
>>>>>>>>>>>>>>>>>>>> only two
>>>>>>>>>>>>>>>>>>>> arguments are different and one of them has the only
>>>>>>>>>>>>>>>>>>>> occurence,
>>>>>>>>>>>>>>>>>>>> transformation to single COND_EXPR can be done.
>>>>>>>>>>>>>>>>>>>> - if phi node has more different arguments and all edge
>>>>>>>>>>>>>>>>>>>> predicates
>>>>>>>>>>>>>>>>>>>> correspondent to phi-arguments are disjoint, a chain of
>>>>>>>>>>>>>>>>>>>> COND_EXPR
>>>>>>>>>>>>>>>>>>>> will be generated for it. In current design very simple
>>>>>>>>>>>>>>>>>>>> check is used:
>>>>>>>>>>>>>>>>>>>> check starting from end that two edges correspondent to
>>>>>>>>>>>>>>>>>>>> neighbor
>>>>>>>>>>>>>>>>>>>> arguments have common predecessor which is used for
>>>>>>>>>>>>>>>>>>>> further check
>>>>>>>>>>>>>>>>>>>> with next edge.
>>>>>>>>>>>>>>>>>>>> These guarantee that phi predication will produce the
>>>>>>>>>>>>>>>>>>>> correct result.
>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>> Btw, you can think of these extensions as unfactoring a PHI
>>>>>>>>>>>>>>>>>>> node by
>>>>>>>>>>>>>>>>>>> inserting forwarder blocks. Thus
>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>> x = PHI <1(2), 1(3), 2(4)>
>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>> becomes
>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>> bb 5: <forwarder-from(2)-and(3)>
>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>> x = PHI <1(5), 2(4)>
>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>> and
>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>> x = PHI <1(2), 2(3), 3(4)>
>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>> becomes
>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>> bb 5:
>>>>>>>>>>>>>>>>>>> x' = PHI <1(2), 2(3)>
>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>> b = PHI<x'(5), 3(4)>
>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>> which means that 3) has to work. Note that we want this
>>>>>>>>>>>>>>>>>>> kind of
>>>>>>>>>>>>>>>>>>> PHI transforms for out-of-SSA as well to reduce the number
>>>>>>>>>>>>>>>>>>> of
>>>>>>>>>>>>>>>>>>> copies we need to insert on edges.
>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>> Thus it would be nice if you implemented 4) in terms of a
>>>>>>>>>>>>>>>>>>> pre-pass
>>>>>>>>>>>>>>>>>>> over the force_vect loops PHI nodes, applying that CFG
>>>>>>>>>>>>>>>>>>> transform.
>>>>>>>>>>>>>>>>>>> And make 3) work properly if it doesn't already.
>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>> It looks like you introduce a "negate predicate" to work
>>>>>>>>>>>>>>>>>>> around the
>>>>>>>>>>>>>>>>>>> critical edge limitation? Please instead change
>>>>>>>>>>>>>>>>>>> if-conversion to
>>>>>>>>>>>>>>>>>>> work with edge predicates (as opposed to BB predicates).
>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>> Thanks,
>>>>>>>>>>>>>>>>>>> Richard.
>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>> Here is example of such extended predication (compile with
>>>>>>>>>>>>>>>>>>>> -march=core-avx2):
>>>>>>>>>>>>>>>>>>>> #pragma omp simd safelen(8)
>>>>>>>>>>>>>>>>>>>> for (i=0; i<512; i++)
>>>>>>>>>>>>>>>>>>>> {
>>>>>>>>>>>>>>>>>>>> float t = a[i];
>>>>>>>>>>>>>>>>>>>> if (t > 0 & t < 1.0e+17f)
>>>>>>>>>>>>>>>>>>>> if (c[i] != 0)
>>>>>>>>>>>>>>>>>>>> res += 1;
>>>>>>>>>>>>>>>>>>>> }
>>>>>>>>>>>>>>>>>>>> <bb 4>:
>>>>>>>>>>>>>>>>>>>> # res_15 = PHI <res_1(5), 0(3)>
>>>>>>>>>>>>>>>>>>>> # i_16 = PHI <i_11(5), 0(3)>
>>>>>>>>>>>>>>>>>>>> # ivtmp_17 = PHI <ivtmp_14(5), 512(3)>
>>>>>>>>>>>>>>>>>>>> t_5 = a[i_16];
>>>>>>>>>>>>>>>>>>>> _6 = t_5 > 0.0;
>>>>>>>>>>>>>>>>>>>> _7 = t_5 < 9.9999998430674944e+16;
>>>>>>>>>>>>>>>>>>>> _8 = _7 & _6;
>>>>>>>>>>>>>>>>>>>> _ifc__28 = (unsigned int) _8;
>>>>>>>>>>>>>>>>>>>> _10 = &c[i_16];
>>>>>>>>>>>>>>>>>>>> _ifc__36 = _ifc__28 != 0 ? 4294967295 : 0;
>>>>>>>>>>>>>>>>>>>> _9 = MASK_LOAD (_10, 0B, _ifc__36);
>>>>>>>>>>>>>>>>>>>> _ifc__29 = _ifc__28 != 0 ? 1 : 0;
>>>>>>>>>>>>>>>>>>>> _ifc__30 = (int) _ifc__29;
>>>>>>>>>>>>>>>>>>>> _ifc__31 = _9 != 0 ? _ifc__30 : 0;
>>>>>>>>>>>>>>>>>>>> _ifc__32 = _ifc__28 != 0 ? 1 : 0;
>>>>>>>>>>>>>>>>>>>> _ifc__33 = (int) _ifc__32;
>>>>>>>>>>>>>>>>>>>> _ifc__34 = _9 == 0 ? _ifc__33 : 0;
>>>>>>>>>>>>>>>>>>>> _ifc__35 = _ifc__31 != 0 ? 1 : 0;
>>>>>>>>>>>>>>>>>>>> res_1 = res_15 + _ifc__35;
>>>>>>>>>>>>>>>>>>>> i_11 = i_16 + 1;
>>>>>>>>>>>>>>>>>>>> ivtmp_14 = ivtmp_17 - 1;
>>>>>>>>>>>>>>>>>>>> if (ivtmp_14 != 0)
>>>>>>>>>>>>>>>>>>>> goto <bb 4>;
>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>> Bootstrap and regression testing did not show any new
>>>>>>>>>>>>>>>>>>>> failures.
>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>> gcc/ChageLog
>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>> 2014-06-25 Yuri Rumyantsev <ysrum...@gmail.com>
>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>> * tree-if-conv.c (flag_force_vectorize): New variable.
>>>>>>>>>>>>>>>>>>>> (struct bb_predicate_s): Add negate_predicate field.
>>>>>>>>>>>>>>>>>>>> (bb_negate_predicate): New function.
>>>>>>>>>>>>>>>>>>>> (set_bb_negate_predicate): New function.
>>>>>>>>>>>>>>>>>>>> (bb_copy_predicate): New function.
>>>>>>>>>>>>>>>>>>>> (add_stmt_to_bb_predicate_gimplified_stmts): New function.
>>>>>>>>>>>>>>>>>>>> (init_bb_predicate): Add initialization of
>>>>>>>>>>>>>>>>>>>> negate_predicate field.
>>>>>>>>>>>>>>>>>>>> (reset_bb_predicate): Reset negate_predicate to NULL_TREE.
>>>>>>>>>>>>>>>>>>>> (convert_name_to_cmp): New function.
>>>>>>>>>>>>>>>>>>>> (get_type_for_cond): New function.
>>>>>>>>>>>>>>>>>>>> (convert_bool_predicate): New function.
>>>>>>>>>>>>>>>>>>>> (predicate_disjunction): New function.
>>>>>>>>>>>>>>>>>>>> (predicate_conjunction): New function.
>>>>>>>>>>>>>>>>>>>> (add_to_predicate_list): Add convert_bool argument.
>>>>>>>>>>>>>>>>>>>> Add call of predicate_disjunction if convert_bool argument
>>>>>>>>>>>>>>>>>>>> is true.
>>>>>>>>>>>>>>>>>>>> (add_to_dst_predicate_list): Add convert_bool argument.
>>>>>>>>>>>>>>>>>>>> Add early function exit if edge target block is always
>>>>>>>>>>>>>>>>>>>> executed.
>>>>>>>>>>>>>>>>>>>> Add call of predicate_conjunction if convert_bool argument
>>>>>>>>>>>>>>>>>>>> is true.
>>>>>>>>>>>>>>>>>>>> Pass convert_bool argument for add_to_predicate_list.
>>>>>>>>>>>>>>>>>>>> (equal_phi_args): New function.
>>>>>>>>>>>>>>>>>>>> (phi_has_two_different_args): New function.
>>>>>>>>>>>>>>>>>>>> (phi_args_disjoint): New function.
>>>>>>>>>>>>>>>>>>>> (if_convertible_phi_p): Accept phi nodes with more than
>>>>>>>>>>>>>>>>>>>> two args
>>>>>>>>>>>>>>>>>>>> for loops marked with pragma omp simd. Add check that phi
>>>>>>>>>>>>>>>>>>>> nodes are
>>>>>>>>>>>>>>>>>>>> in non-predicated basic blocks.
>>>>>>>>>>>>>>>>>>>> (ifcvt_can_use_mask_load_store): Use flag_force_vectorize.
>>>>>>>>>>>>>>>>>>>> (all_edges_are_critical): New function.
>>>>>>>>>>>>>>>>>>>> (if_convertible_bb_p): Allow bb has more than two
>>>>>>>>>>>>>>>>>>>> predecessors if
>>>>>>>>>>>>>>>>>>>> flag_force_vectorize was setup. Use call of
>>>>>>>>>>>>>>>>>>>> all_edges_are_critical
>>>>>>>>>>>>>>>>>>>> to reject block if-conversion with imcoming critical edges
>>>>>>>>>>>>>>>>>>>> only if
>>>>>>>>>>>>>>>>>>>> flag_force_vectorize was not setup.
>>>>>>>>>>>>>>>>>>>> (walk_cond_tree): New function.
>>>>>>>>>>>>>>>>>>>> (vect_bool_pattern_is_applicable): New function.
>>>>>>>>>>>>>>>>>>>> (predicate_bbs): Add convert_bool argument that is used to
>>>>>>>>>>>>>>>>>>>> transform
>>>>>>>>>>>>>>>>>>>> comparison expressions of boolean type into conditional
>>>>>>>>>>>>>>>>>>>> expressions
>>>>>>>>>>>>>>>>>>>> with integral operands. If bool_conv argument is false or
>>>>>>>>>>>>>>>>>>>> both
>>>>>>>>>>>>>>>>>>>> outgoing edges are not critical old algorithm of predicate
>>>>>>>>>>>>>>>>>>>> assignments
>>>>>>>>>>>>>>>>>>>> is used, otherwise the following code was added: check on
>>>>>>>>>>>>>>>>>>>> applicable
>>>>>>>>>>>>>>>>>>>> of vect-bool-pattern recognition and trnasformation of
>>>>>>>>>>>>>>>>>>>> (bool) x != 0 --> y = (int) x; x != 0;
>>>>>>>>>>>>>>>>>>>> compute predicates for both outgoing edges one of which is
>>>>>>>>>>>>>>>>>>>> critical
>>>>>>>>>>>>>>>>>>>> one using 'normal' edge, i.e. compute true and false
>>>>>>>>>>>>>>>>>>>> predicates using
>>>>>>>>>>>>>>>>>>>> normal outgoing edge only; evaluated predicates are stored
>>>>>>>>>>>>>>>>>>>> in
>>>>>>>>>>>>>>>>>>>> predicate and negate_predicate fields of struct
>>>>>>>>>>>>>>>>>>>> bb_predicate_s and
>>>>>>>>>>>>>>>>>>>> negate_predicate of normal edge conatins predicate of
>>>>>>>>>>>>>>>>>>>> critical edge,
>>>>>>>>>>>>>>>>>>>> but generated gimplified statements are stored in their
>>>>>>>>>>>>>>>>>>>> destination
>>>>>>>>>>>>>>>>>>>> block fields. Additional argument 'convert_bool" is passed
>>>>>>>>>>>>>>>>>>>> to
>>>>>>>>>>>>>>>>>>>> add_to_dst_predicate_list and add_to_predicate_list.
>>>>>>>>>>>>>>>>>>>> (if_convertible_loop_p_1): Call predicate_bbs with
>>>>>>>>>>>>>>>>>>>> additional argument
>>>>>>>>>>>>>>>>>>>> equal to false.
>>>>>>>>>>>>>>>>>>>> (find_phi_replacement_condition): Extend function
>>>>>>>>>>>>>>>>>>>> interface:
>>>>>>>>>>>>>>>>>>>> it returns NULL if given phi node must be handled by means
>>>>>>>>>>>>>>>>>>>> of
>>>>>>>>>>>>>>>>>>>> extended phi node predication. If number of predecessors
>>>>>>>>>>>>>>>>>>>> of phi-block
>>>>>>>>>>>>>>>>>>>> is equal 2 and atleast one incoming edge is not critical
>>>>>>>>>>>>>>>>>>>> original
>>>>>>>>>>>>>>>>>>>> algorithm is used.
>>>>>>>>>>>>>>>>>>>> (is_cond_scalar_reduction): Add 'extended' argument which
>>>>>>>>>>>>>>>>>>>> signals that
>>>>>>>>>>>>>>>>>>>> both phi arguments must be evaluated through
>>>>>>>>>>>>>>>>>>>> phi_has_two_different_args.
>>>>>>>>>>>>>>>>>>>> (predicate_scalar_phi): Add invoсation of
>>>>>>>>>>>>>>>>>>>> convert_name_to_cmp if cond
>>>>>>>>>>>>>>>>>>>> is SSA_NAME. Add 'false' argument to call of
>>>>>>>>>>>>>>>>>>>> is_cond_scalar_reduction.
>>>>>>>>>>>>>>>>>>>> (get_predicate_for_edge): New function.
>>>>>>>>>>>>>>>>>>>> (find_insertion_point): New function.
>>>>>>>>>>>>>>>>>>>> (predicate_phi_disjoint_args): New function.
>>>>>>>>>>>>>>>>>>>> (predicate_extended_scalar_phi): New function.
>>>>>>>>>>>>>>>>>>>> (predicate_all_scalar_phis): Add code to set-up gimple
>>>>>>>>>>>>>>>>>>>> statement
>>>>>>>>>>>>>>>>>>>> iterator for predication of extended scalar phi's for
>>>>>>>>>>>>>>>>>>>> insertion.
>>>>>>>>>>>>>>>>>>>> (insert_gimplified_predicates): Add test for
>>>>>>>>>>>>>>>>>>>> non-predicated basic
>>>>>>>>>>>>>>>>>>>> blocks that there are no gimplified statements to insert.
>>>>>>>>>>>>>>>>>>>> Insert
>>>>>>>>>>>>>>>>>>>> predicates at the block begining for extended
>>>>>>>>>>>>>>>>>>>> if-conversion.
>>>>>>>>>>>>>>>>>>>> (predicate_mem_writes): Invoke convert_name_to_cmp for
>>>>>>>>>>>>>>>>>>>> extended
>>>>>>>>>>>>>>>>>>>> predication to build mask.
>>>>>>>>>>>>>>>>>>>> (combine_blocks): Pass flag_force_vectorize to
>>>>>>>>>>>>>>>>>>>> predicate_bbs.
>>>>>>>>>>>>>>>>>>>> (split_crit_edge): New function.
>>>>>>>>>>>>>>>>>>>> (tree_if_conversion): Initialize flag_force_vectorize from
>>>>>>>>>>>>>>>>>>>> current
>>>>>>>>>>>>>>>>>>>> loop or outer loop (to support pragma omp declare). Invoke
>>>>>>>>>>>>>>>>>>>> split_crit_edge for extended predication. Do loop
>>>>>>>>>>>>>>>>>>>> versioning for
>>>>>>>>>>>>>>>>>>>> innermost loop marked with pragma omp simd.
