Re: conditional lim

[Evgeniya Maenkova <evgeniya dot maenkova at gmail dot com>]

On Tue, Jul 14, 2015 at 2:54 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Mon, Jun 29, 2015 at 4:21 PM, Evgeniya Maenkova
> <evgeniya.maenkova@gmail.com> wrote:
>> On Mon, Jun 29, 2015 at 5:10 PM, Richard Biener
>> <richard.guenther@gmail.com> wrote:
>>> On Tue, Jun 9, 2015 at 10:11 PM, Evgeniya Maenkova
>>> <evgeniya.maenkova@gmail.com> wrote:
>>>> On Tue, Jun 9, 2015 at 3:46 PM, Richard Biener
>>>> <richard.guenther@gmail.com> wrote:
>>>>> On Fri, May 29, 2015 at 3:14 PM, Evgeniya Maenkova
>>>>> <evgeniya.maenkova@gmail.com> wrote:
>>>>>> Hi Richard,
>>>>>>
>>>>>> Here is some explanation. I hope you let me know if I need to clarify something.
>>>>>>
>>>>>> Also, you asked me about concrete example, to make sure you donât miss
>>>>>> my answer here is the link:
>>>>>> https://gcc.gnu.org/ml/gcc-patches/2015-05/msg02417.html.
>>>>>>
>>>>>> Also, I doubt whether itâs convenient for you to create a build with
>>>>>> my patch or not. May be to clarify things you could send me some
>>>>>> examples/concrete cases, then Iâll compile them with
>>>>>> âfdump-tree-loopinit-details and âfdump-tree-lim-details and send you
>>>>>> these dumps. May be these dumps will be useful. (Iâll only disable
>>>>>> cleanup_cfg TODO after lim to let you know the exact picture after
>>>>>> lim).
>>>>>>
>>>>>> What do you think?
>>>>>>
>>>>>> 1.       invariantness _dom_walker â
>>>>>>
>>>>>> 1.1   for each GIMPLE_COND in given bb calls handle_cond_stmt to call
>>>>>> for true and false edges handle_branch_edge, which calls SET_TARGET_OF
>>>>>> for all bb âpredicatedâ by given GIMPLE_COND.
>>>>>>
>>>>>> SET_TARGET_OF sets in basic_blocks aux 2 facts:
>>>>>>
>>>>>> a)      this is true or false edge;
>>>>>>
>>>>>> b)      link to cond stmt;
>>>>>>
>>>>>> Handle_branch_edge works this way:
>>>>>>
>>>>>> If (cond1)
>>>>>>
>>>>>>   {
>>>>>>
>>>>>>      bb1;
>>>>>>
>>>>>>      if (cond2}
>>>>>>
>>>>>>        {
>>>>>>
>>>>>>            bb2;
>>>>>>
>>>>>>         }
>>>>>>
>>>>>>    Being called for cond1, it sets cond1 as condition for both bb1 and
>>>>>> bb2 (the whole branch for cond1, ie also for bb containing cond2),
>>>>>> then this method will be called (as there is dominance order) for
>>>>>> cond2 to correct things (ie to set cond2 as condition for bb2).
>>>>>
>>>>> Hmm, why not track the current condition as state during the DOM walk
>>>>> and thus avoid processing more than one basic-block in handle_branch_edge?
>>>>> Thus get rid of handle_branch_edge and instead do everything in handle_cond_stmt
>>>>> plus the dom-walkers BB visitor?
>>>>>
>>>> I need to look more carefully how to implement it, but I think I
>>>> understand what you mean and this optimization of course looks
>>>> reasonable to me. Will do.
>>>>
>>>>> I see you don't handle BBs with multiple predecessors - that's ok, but
>>>>> are you sure you don't run into correctness issues when not marking such
>>>>> BBs as predicated?  This misses handling of, say
>>>>>
>>>>>  if (a || b)
>>>>>    bb;
>>>>>
>>>>> which is a pity (but can be fixed later if desired).
>>>>>
>>>> I had some test (in gcc testsuite or bootstrap build) which worked
>>>> incorrectly because of multiple predecessors. As far as I remember the
>>>> situation was (further, will make some notes about such tests to
>>>> clarify this better), I mean with previous version of my code which
>>>> handled bb with 2 predecessors:
>>>> if (a)
>>>>   tmpvar=something;
>>>> while()
>>>>   if (a || b)
>>>>       basic_block {do something with tmpvar;} // I mean basic block
>>>> predicated by bb with a and bb with b
>>>>
>>>> So, if a is false, I mean we didn't do tmpvar=something (outside
>>>> loop), BUT we are in basick_block  (we went by bb with b), we got
>>>> Segmentation falt in basic_block {do something with tmpvar;}.
>>>>
>>>> I think we can reproduce all the details of this test if I remove not
>>>> handling bb with 2 predecessors.
>>>>
>>>> So I wouldn't move bb with 2 predecessors (this is not always executed
>>>> bb in any loop, not conditionally, they will not be moved at all).
>>>>
>>>> This is my more detail explanation on this point. Perhaps, I didn't
>>>> understand your question about correctness. Could you repeat it in
>>>> other words (based on this new clarification).
>>>>
>>>> So I think according to current code it will not be moved. What
>>>> incorrectness do you mean?
>>>
>>> If the block isn't marked as predicated the question is whether it is
>>> handled correctly or assumed to be unconditionally executed.
>>>
>>>>> I note that collecting predicates has similarities to what if-conversion
>>>>> does in tree-ifcvt.c (even if its implementation is completely different,
>>>>> of course).
>>>>>
>>>>
>>>> Ok, I'll look at this. But could you please clarify your point?
>>>> (Should I just take this into account with low priority and look at
>>>> this later or you want some refactoring?)
>>>
>>> I just noted similar code exists elsewhere - it may be possible to
>>> factor it out but I didn't investigate.  And no, doing that isn't a prerequesite
>>> for this patch.
>>>
>>>>>> 1.2   As 1.1 goes we identify whether some bb is predicated by some
>>>>>> condition or not.
>>>>>>
>>>>>> bb->aux->type will be [TRUE/FALSE]_TARGET_OF and
>>>>>> bb->aux->cond_stmt=cond stmt (the nearest condition).
>>>>>>
>>>>>> If bb is always executed bb->aux->type = ALWAYS_EXECUTED_IN,
>>>>>> bb->loop->loop (this info was available in the clean build).
>>>>>>
>>>>>> 1.3   As this walker is called in dominance order, information about
>>>>>> condition is available when invariantness_dom_walker is called for
>>>>>> given bb.  So we can make some computations based on bb->aux
>>>>>> structure. This is done in check_conditionally_executed. The main goal
>>>>>> of this method is to check that the root condition is always executed
>>>>>> in the loop. I did so to avoid situation like this
>>>>>>
>>>>>> Loop:
>>>>>>
>>>>>>    Jmp somewhere;
>>>>>>
>>>>>>   If (cond1)
>>>>>>
>>>>>>       If (cond2)
>>>>>>
>>>>>>          Etc
>>>>>>
>>>>>> By âroot conditionâ I mean cond1 in this case (the first cond in
>>>>>> dominance order).
>>>>>
>>>>> Ok, but this can't happen (an uncontional jump to somehwere).  It
>>>>> will always be a conditional jump (a loop exit) and thus should
>>>>> be handled already.
>>>>>
>>>>> Did you have a testcase that was mishandled?
>>>>
>>>> No, I have not such testcase. This is because I;m newbie at gcc and
>>>> compilers. If you tell me this fact, let's just remove this check?
>>>> Correct?
>>>
>>> Yes.
>>>
>>>>>
>>>>>> If  âroot conditionâ is not always executed we disable (free) all the
>>>>>> info in bb->aux, ie all the blocks becomes neither conditionally nor
>>>>>> always executed according to bb->aux.
>>>>>>
>>>>>> There is some optimization to donât go each time trough the conditions
>>>>>> chain (cond2->cond1), let me skip such details for now.
>>>>>>
>>>>>>
>>>>>>
>>>>>> 1.4   Then we calculate tgt_level  (which is used in move_computations later)
>>>>>>
>>>>>> The patch is the same for phi and regular stmt (calculate_tgt_level)
>>>>>>
>>>>>> 1)      If stmt is conditionally executed we compute max movement
>>>>>> (determine_max_movement) starting from
>>>>>> get_lim_data(condition)->max_loop.
>>>>>>
>>>>>> 2)      If stmt is not cond executed as start level  for
>>>>>> determine_max_movement computations we choose ALWAYS_EXECUTED_IN.
>>>>>>
>>>>>> To clarify why, see the comment
>>>>>>
>>>>>> /* The reason why we don't set start_level for MOVE_POSSIBLE
>>>>>>
>>>>>>           statements to more outer level is: this statement could depend on
>>>>>>
>>>>>>           conditional statements and even probably is not defined without this
>>>>>>
>>>>>>           condition. So either we should analyze these ones and move
>>>>>>
>>>>>>           under condition somehow or keep more strong start_level . */
>>>>>>
>>>>>> As you noted in your review there was some refactoring. Of course, I
>>>>>> had no goal to refactor existing code, I intended to remove some
>>>>>> duplication which I caused by my changes.  I hope we discuss in
>>>>>> details later if you donât like some refactoring.
>>>>>
>>>>> Refactoring makes a big patch harder to review because it ends up
>>>>> containing no-op changes.  It also makes it appear bigger than it
>>>>> really is ;)
>>>>>
>>>>> A reasonable solution is to factor out the refactoring to a separate patch.
>>>>>
>>>> I see what you mean.
>>>>
>>>>>> 2.       store_motion  - for some stmts set flags to ignore predicated
>>>>>> execution (I mean to move statements without conditions).
>>>>>
>>>>> That's for the existing "predicated" support as far as I can see.
>>>>>
>>>>>>
>>>>>>
>>>>>> 3.       move_computations. The patch is doing something in the
>>>>>> following 3 calls inside of this method.
>>>>>>
>>>>>>
>>>>>>
>>>>>> 3.1   (more details below) walker.walk â move computations(create if()
>>>>>> structure) and store information to create phi nodes later (which
>>>>>> statements require phi nodes, as they conditionally executed and there
>>>>>> are still their uses on other levels, what are the names for such phi
>>>>>> nodes, as we replace uses in here, in walker.walk.)
>>>>>
>>>>> What kind of uses are that?  By definition all stmts executed
>>>>> under condition A that are used in code not under condition A have
>>>>> a PHI node associated.  This is why the existing conditional movement
>>>>> handling moves PHI nodes (and all dependent computations).
>>>>>
>>>>> Are you thinking of
>>>>>
>>>>>   for (;;)
>>>>>     if (a) x = 1;
>>>>>
>>>>>   .. use of x
>>>>>
>>>>> ?
>>>> No, I think in this case phi node of x will be used in initial
>>>> (==loopinit) code (in 'use of x') instead of some version of x (which
>>>> I move).
>>>>
>>>>>If you move the PHI node for x then you don't need to insert any other
>>>>> PHI nodes (and you _do_ have to move the PHI node anyway).
>>>>
>>>>>
>>>>>> 3.2   (more details below) create_phi_nodes â create phi nodes for
>>>>>> statements which require that (see 3.1)
>>>>>
>>>>> Only PHI nodes need PHI node creation and only its dependences
>>>>> might need predication.
>>>>>
>>>>> That is, if you move a conditionally executed statement but not
>>>>> any PHI node it feeds then the movement is useless.
>>>>>
>>>>> But maybe I am missing something about the PHI business.
>>>>>
>>>> Ok. I have different understanding on this (and am afraid of this of
>>>> course :) ).
>>>>
>>>> See the example:
>>>> void bar (long);
>>>> void foo (int cond1, int cond2, int cond3, int m, int n)
>>>> {
>>>>   unsigned x;
>>>>   unsigned inv1;
>>>>
>>>>   for (x = 0; x < 1000; ++x)
>>>>     {
>>>>       if (cond1)
>>>>         {
>>>>           int tmp_inv1 = m*n;
>>>>           non_inv1 = tmp_inv1 + x;
>>>>         }
>>>>     }
>>>>   bar (non_inv1);
>>>> }
>>>>
>>>> This is working example, will attach loopinit and lim1 dumps.
>>>> There is no phi node for tmp_inv1 in loopinitat all. However, I think
>>>> we should move tmp_inv1. To use tmp_inv1 in non_inv1 we need phi node
>>>> (otherwise we get verification failure as bb with conditionally moved
>>>> tmp_inv1 doesn;t dominate bb with non_inv1). Another example if
>>>> non_inv1 is invariant but has not enough cost or something else. In
>>>> short, if it's still used in initial or others loops. Say, non_inv1 is
>>>> invariant and moved in another loop. Or something else.
>>>>
>>>> So, when I read
>>>> 'Only PHI nodes need PHI node creation'
>>>> and
>>>> 'That is, if you move a conditionally executed statement but not any
>>>> PHI node it feeds then the movement is useless.'
>>>> I think about this example and don't understand. Could you clarify?
>>>
>>> Ok, so this case is already handled by LIM by simply moving tmp_inv1 = m*n
>>> (and making it unconditionally execute before the loop).  In fact whether
>>> we can move it does not depend on whether 'cond' is invariant or not.
>>>
>>> If we couldn't execute m*n unconditionally on the loop preheader edge
>>> then we'd have to be able to also move the guarding condition.  Note
>>> that cost considerations shouldn't come into play here.
>>>
>>> So I was only thinking of the case where we also want to move the
>>> condition (which is wanted if we want to move a PHI node).
>>>
>>
>> Don't understand "So I was only thinking of the case where we also
>> want to move the condition (which is wanted if we want to move a PHI
>> node)."
>>
>> What about the case when we want to move condition but don't have phi
>> node to move.
>>
>> Let's consider a little bit modified example:
>>
>> void bar (long);
>> void foo (int cond1, int cond2, int cond3, int m, int n)
>>   {
>>      unsigned x;
>>      unsigned inv1;
>>
>>      for (x = 0; x < 1000; ++x)
>>        {
>>          if (n)
>>            {
>>              int tmp_inv1 = m/n;
>>              non_inv1 = tmp_inv1 + x;
>>             }
>>        }
>>      bar (non_inv1);
>>  }
>> We couldn't  move tmp_inv1 uncoditionally. Right (I have no clean
>> build at hands right now to check. If I'm wrong let's replace m/n to
>> something that couldn't be unconditionally moved :))? There is no phi
>> node for tmp_inv1.
>> Could you clarify what conditional lim should do in your opinion here?
>
> Nothing at this point.  If only then for the simple reason to make the
> first iteration of the patch simpler (still covering most cases).
>
> You seem to want to catch 100% of all possible cases.
>
>> Is it too little gain to move statements that only used in the same bb
>> or branch (I mean before phi node creation, even if stmt had phi
>> node)?
>>
>> In fact, we could have here 2 thousands of divisions:
>> if (n)
>>   {
>>     int tmp_inv1 = m/n;
>>     tmp_inv2 = something_which_couldn't_be moved_unconditionally (tmp_inv1);
>>     ...
>>     tmp_invN = something_which_couldn't_be moved_unconditionally (tmp_invN-1);
>>     non_inv1 = tmp_invN + x;
>>   }
>
> Of course we could.  But the patch didn't even exercise this case (no testcase).

Patch handles this case (this is why I created phi nodes which we
tried to discuss).
Your comment is about test case not about the patch.

>
> Please make patches simple - support for moving non-PHIs can be added
> as a followup.  The first important part is to make the current code
> (moving PHIs)
> create control-flow rather than if-converted form.
>
> Richard.
>
>>
>>>>>>
>>>>>> 3.3   replace_uses_in_conditions
>>>>>>
>>>>>> After computations movements we can have several copies of the cond
>>>>>> stmt. In 3.1 we do replacement of uses based on stmtâs tgt_level. For,
>>>>>> cond stmt it doesnât work. As cond stmt, of course, have something in
>>>>>> lim_aux_data->tgt_level, but, in fact, they are moved only if
>>>>>> corresponding invariants are moved. So, in fact, the same cond (copies
>>>>>> of it, of course) could go to the different levels. So to fix these
>>>>>> uses, we call replace_uses_in_conditions.
>>>>>
>>>>> Hmm, but stmts that a condition depends on always have at least the
>>>>> target level of the condition statement.  Thus their computation is
>>>>> available in all other "same" conditon statements that might appear
>>>>> in more inner loop levels, no?  So isn't this just about performing the
>>>>> movement in a proper ordering?
>>>>
>>>> Let me give your more details, then may be you repeat question in other words.
>>>> for ()
>>>> {
>>>>   if (a)
>>>>     {
>>>>        inv1 = some_computations;
>>>>        if (inv1 < inv2)
>>>>             {
>>>>               inv3;
>>>>               inv4;
>>>>             }
>>>>        }
>>>> }
>>>>
>>>> So, the order for movement is: inv1; inv3; inv4. When we move inv1 we
>>>> have tgt_level for inv3 and inv4 computed but we have not created
>>>> copies of 'if (inv1 < inv2)' created. In theory, we can have several
>>>> copies:(1) for tgt_level of inv3 (2) for tgt_level of inv2 (3) in
>>>> initial cycle. if (1) is in tgt level of inv1 we need no replacement,
>>>> in other cases we need replacements. Of course, we know this(all the
>>>> info about tgt_levels) when we move inv1, but then we need to create
>>>> all needed copies (store it somehow, etc) of 'if (inv1 < inv2') and
>>>> make replacement in these copies. I don't see now why this is much
>>>> better. This doesn't mean that current solution is perfect, just
>>>> clarify your thought.
>>>
>>> I still don't get what "replacements" actually mean.  Let's extend the
>>> example to
>>>
>>> for ()  (A)
>>>   {
>>>> for ()  (B)
>>>> {
>>>>   if (a)
>>>>     {
>>>>        inv1 = some_computations;
>>>>        if (inv1 < inv2)
>>>>             {
>>>>               inv3;
>>>>               inv4;
>>>>             }
>>>>        }
>>>> }
>>>  }
>>>
>>> then you say the target level of inv1 could be 'A' and the target
>>> level of inv3 'B'
>>> and that of inv4 is 'B' as well.
>>>
>>> That's true.  So we move inv1 to before 'A' and inv3/inv4 to before 'B' guarded
>>> with if (inv1 < inv2).  I fail to see what "copies" we need here.  'inv1' is
>>> available in all target levels below its own, no copies needed.
>>>
>>
>> I meant the copies of conditions (COND_STMT: inv1 < inv2).
>>
>> Let's modify this example: tgt_level (inv1) = A; tgt_level(inv3) = A;
>> tgt_level(inv4) = B.
>>
>>  Then
>> if (a)
>>    inv1=some_computations;
>> if (inv1 < inv2)
>>    inv3;
>> <preheader edge for A, where phi for inv1(phi_for_inv1) is computed>
>> for ()  (A)
>>  {
>>  if (phi_for_inv1 <inv2)
>>    inv3
>>  for ()  (B)
>>    {
>>    if (a)
>>      {
>>         if (phi_for_inv1 < inv2)
>>           {
>>           }
>>      }
>>  }
>> So, we have 3 copies of inv1 < inv2 after lim (in some of them we use
>> inv1, in other phi_for_inv1). But this is the second priority for now
>> (this is all about whether we should move statements w/o phi node).
>>
>>>>>
>>>>>> More details on 3.1 and 3.2
>>>>>>
>>>>>> 3.1 The patch is very similar for phi stmts and regular stmts (there
>>>>>> is some difference for regular stmts related to the case when we move
>>>>>> sequence instead of single stmt, letâs skip it in this description,
>>>>>> will describe later. BTW, there are comments, in corresponding parts).
>>>>>>
>>>>>> a) for each bb we call check_conditionally_executed and if bb is cond
>>>>>> executed then invariant statement  will be moved conditionally.
>>>>>>
>>>>>> b) prepare_edge_for_stmt collects information needed to create phi
>>>>>> nodes in 3.2(add_info_for_phi) AND prepares edge ie creates if()
>>>>>> structure needed to move statement
>>>>>> (get_block_for_predicated_statement, see below). All of this is done
>>>>>> for cond executed stmt. Nothing is done for non cond executed.
>>>>>>
>>>>>> BTW, there is some strange names for functions like missed ending
>>>>>> (prepare_edge_for_stm, w/o t in the end, this is because of my script
>>>>>> to add â â before â(â, will fix in the next patch version, ignore
>>>>>> please so far).
>>>>>>
>>>>>> Get_block_for_predicated_stmt:
>>>>>>
>>>>>> Create bb where to add cond stmt to (or return existing, each loop has
>>>>>> a map  (level_cond_data_map is map <loop, cond_data_map> ,
>>>>>> cond_data_map is map <gimple, basic_block>) to identify if bb for
>>>>>> given cond was created or not for given level).
>>>>>>
>>>>>> Parameters of this method:
>>>>>>
>>>>>> Cond â condition of stmt, branch â is it on true or false edge of
>>>>>> cond, cond_map  - see above, level (tgt_level), preheader â
>>>>>> preheader_edge for level.
>>>>>>
>>>>>> So first of all we check whether there is a basic block for given
>>>>>> condition in given loop.
>>>>>>
>>>>>> a)      If such bb exists then we trying to find corresponding edge,
>>>>>> destination of this edge shouldnât be a post dominator of bb
>>>>>> (find_branch_edge).
>>>>>>
>>>>>> a.1) if such edge exists we return the most remote in this branch bb
>>>>>> (or create it), see get_most_remote_in_branch;
>>>>>>
>>>>>> a.2) if such edge doesnât exists, we create corresponding bb, see make_branch
>>>>>>
>>>>>>        b)  If such bb doesnât exist we create it (recursively calling
>>>>>> get_block_for_predicated_stmt if required bb is conditionally
>>>>>> executed).
>>>>>>
>>>>>> Will not describe it further so far (let me know if you would like to
>>>>>> read additional details).
>>>>>>
>>>>>> Add_info_for_phi
>>>>>>
>>>>>> The main goal of this method is to identify situation where
>>>>>> stmt(parameter,ie the statement which we are moving) or more exactly
>>>>>> lhs of this statement
>>>>>>
>>>>>> a)      is still used in other loops, so we need to create phi node to
>>>>>> use phi name inside other loops.
>>>>>>
>>>>>> b)      Is used in phi node of original loop and this phi node is
>>>>>> going to be moved. BUT, as we move phi node as assignment (in the case
>>>>>> of phi node with 2 arguments) we need to create phi node to use lhs of
>>>>>> statement (param of add_info_for_phi).
>>>>>>
>>>>>> In these cases we make corresponding replacements and store
>>>>>> information needed to create phi nodes and make some other
>>>>>> replacements in 3.3 (replace_uses_in_conditions).
>>>>>>
>>>>>> Add_info_for_phi calls create_tmp_var which requires some explanation.
>>>>>>
>>>>>> Create_tmp_var
>>>>>>
>>>>>> To create new names for phi nodes and to create default def for phi
>>>>>> arguments I use make_ssa_name and get_or_create_ssa_default_def. These
>>>>>> methods have some asserts (being merged):   (TREE_CODE (old_var) ==
>>>>>> VAR_DECL   || TREE_CODE (old_var) == PARM_DECL   || TREE_CODE
>>>>>> (old_var) == RESULT_DECL).
>>>>>>
>>>>>> So in some cases (when I know that I need to use methods mentioned
>>>>>> above, see the start of create_tmp_var, ie the uses in other loops) I
>>>>>> create new tmp variable to overcome these asserts. To be honest I
>>>>>> donât like this but donât know how to deal with this better.
>>>>>
>>>>> Hmm, don't you just run into SSA names here?  That is, TREE_CODE
>>>>> (old_var) == SSA_NAME?
>>>>> You can use make_ssa_name (TREE_TYPE (old_var), "plim") in this case.
>>>>>
>>>>> Or you run into the issue that anonymous SSA names cannot have default
>>>>> defintions (I don't understand why you need all the fuss about default defs).
>>>>
>>>> I used default defs to write something in phi args when I have no values on
>>>> corresponding branches. Say there is some tmp value which I should
>>>> create phi for.
>>>> if (a)
>>>>    {
>>>>      tmpvar=something
>>>>      b = something(tmpvar);
>>>>     }
>>>> else
>>>>    {
>>>>    }
>>>> When I move if (a) {tmpvar = something} and create phi for tmpvar (to
>>>> use phi result
>>>> in the initial cycle) i need to write something for 'not a' phi arg.
>>>> BUT, in some cases I use
>>>>  build_zero_cst (which I started to use after default defs use. I mean
>>>> I didn't know about
>>>>  build_zero_cst while I started to use default defs.). So may be I can replace
>>>> uses of default defs in such cases by build_zero_cst? I mean just SOME values
>>>> (as I know that control flow will never go to this places actually). I
>>>> mean if !a tmpvar will not used.
>>>
>>> Ok, this is again about the case where you are not moving a PHI node but
>>> creating it because you want to conditionally execute invariant stmts.
>>> Yes, a default def is ok here, but you can always use a new VAR_DECL
>>> just for the default def creation like gimple_fold_call does for example:
>>>
>>>                           tree var = create_tmp_var (TREE_TYPE (lhs));
>>>                           tree def = get_or_create_ssa_default_def (cfun, var);
>>>
>>> Note that I think we don't need to bother about this case as we'd only
>>> want to move PHI nodes in the first place (so you already have values
>>> for all PHI args).
>>>
>>>>>
>>>>>> And a couple of words regarding where we store info for phi nodes:
>>>>>>
>>>>>> Each loop contains in its aux  phi_data structure. On this stage we
>>>>>> only add there stmt (if phi node will be required), phi name=phi node
>>>>>> result name in names_map or fl_names_map). See the comment about
>>>>>> phi_data in patch.
>>>>>>
>>>>>> If there should be created several phi nodes for given lhs (I mean the
>>>>>> first place for phi node doesnât dominate on corresponding preheader,
>>>>>> we add only the last name in names_map (as intermediate names could be
>>>>>> created later, but the last name in bb which dominates preheader
>>>>>> should be used for replacement in other loops. Replacements were
>>>>>> already made in walker).
>>>>>>
>>>>>> If lhs is used only in phi node, which are moved and transformed into
>>>>>> assignment, and there is no uses in other loops, we need to create
>>>>>> only first level phi node (donât need to create phi nodes till some bb
>>>>>> which dominates preheader), then we add such name to fl_names_map.
>>>>>>
>>>>>> 3.2 Create_phi_nodes
>>>>>>
>>>>>> For each of the loops we go over ((phi_data*) loop->aux)->stmts. These
>>>>>> are statements which were moved, but they have uses in the original
>>>>>> loop (more exactly, their uses in some other loops replaced by some
>>>>>> name from ((phi_data*) loop->aux)->names_map or ((phi_data*)
>>>>>> loop->aux)->fl_names_map.
>>>>>>
>>>>>> So for each of such stmts we create phi nodes (for its lhs) chain.
>>>>>>
>>>>>> Basic block for phi node is found in get_bb_for_phi  for given bb with
>>>>>> stmt. If basic block for phi node dominates preheader->src we end
>>>>>> chain creation. There is some special condition for the case when we
>>>>>> need to create only first level phi node. (I described this situation
>>>>>> above, but let me know If I need to add  more details.
>>>>>>
>>>>>> Basic blocks can have maps to identify if we created phi node for
>>>>>> given variable in given basic_block, so we only add an edge argument
>>>>>> for such case (phi_map = new hash_map<basic_block, hash_map<tree,
>>>>>> gphi*>*>).
>>>>>
>>>>> Ok.
>>>>>
>>>>> Well - I think it might be easier code-generation-wise to have a separate
>>>>> phase move_phis executed before move_computations, that just moves
>>>>> invariant PHI nodes (which this all is about - see above) and their
>>>>> controlling conditions and only then move their dependencies.
>>>> I didn;t understand so far (I think let's clarify previous questions,especially
>>>> about phi nodes then let's go back to this one.)
>>>
>>> Yeah, I think the PHI node thing is our major mis-understanding (or the
>>> main thing that I think complicates the patch for too little gain - at least
>>> initially).
>>>
>>> Thanks,
>>> Richard.
>>>
>>>>>
>>>>> Thanks,
>>>>> Richard.
>>>>>
>>>>>> In short, thatâs all.
>>>>>>
>>>>>> Thanks,
>>>>>>
>>>>>> Evgeniya
>>>>>>
>>>>>>
>>>>>>
>>>>>> On Sat, May 9, 2015 at 1:07 AM, Evgeniya Maenkova
>>>>>> <evgeniya.maenkova@gmail.com> wrote:
>>>>>>> Hi,
>>>>>>>
>>>>>>> Could you please review my patch for predicated lim?
>>>>>>>
>>>>>>> Let me note some details about it:
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> 1)      Phi statements are still moved only if they have 1 or 2
>>>>>>> arguments. However, phi statements could be move under conditions (as
>>>>>>> itâs done for the other statements).  Probably, phi statement motion
>>>>>>> with 3 + arguments could be implemented in the next patch after
>>>>>>> predicated lim.
>>>>>>>
>>>>>>> 2)      Patch has limitations/features like (it was ok to me to
>>>>>>> implement it such way, maybe Iâm not correct. ):
>>>>>>>
>>>>>>> a)      Loop1
>>>>>>>
>>>>>>>     {
>>>>>>>
>>>>>>>               If (a)
>>>>>>>
>>>>>>>                  Loop2
>>>>>>>
>>>>>>>                      {
>>>>>>>
>>>>>>>                        Stmt - Invariant for Loop1
>>>>>>>
>>>>>>>                      }
>>>>>>>
>>>>>>>              }
>>>>>>>
>>>>>>>        In this case Stmt will be moved only out of Loop2, because of if (a).
>>>>>>>
>>>>>>> b)      Or
>>>>>>>
>>>>>>> Loop1
>>>>>>>
>>>>>>>     {
>>>>>>>
>>>>>>>          â
>>>>>>>
>>>>>>>          If (cond1)
>>>>>>>
>>>>>>>               If (cond2)
>>>>>>>
>>>>>>>                   If (cond3)
>>>>>>>
>>>>>>>                       Stmt;
>>>>>>>
>>>>>>>        }
>>>>>>>
>>>>>>> Stmt will be moved out only if cond1 is always executed in Loop1.
>>>>>>>
>>>>>>> c)       It took me a long time to write all of these code, so there
>>>>>>> might be other peculiarities which I forgot to mention. :)
>>>>>>>
>>>>>>>                        Letâs discuss these ones as you will review my patch.
>>>>>>>
>>>>>>> 3)      Patch consists of 9 files:
>>>>>>>
>>>>>>> a)      gcc/testsuite/gcc.dg/tree-ssa/loop-7.c,
>>>>>>> gcc/testsuite/gcc.dg/tree-ssa/recip-3.c â changed tests:
>>>>>>>
>>>>>>> -          gcc/testsuite/gcc.dg/tree-ssa/loop-7.c  changed as
>>>>>>> predicated lim moves 2 more statements out of the loop;
>>>>>>>
>>>>>>> -          gcc/testsuite/gcc.dg/tree-ssa/recip-3.c â with conditional
>>>>>>> lim recip optimization in this test doesnât work (the corresponding
>>>>>>> value is below threshold as I could see in the code for recip, 1<3).
>>>>>>> So to have recip working in this test I changed test a little bit.
>>>>>>>
>>>>>>> b)      gcc/tree-ssa-loop-im.c â the patched lim per se
>>>>>>>
>>>>>>> c)       gcc/testsuite/gcc.dg/tree-ssa/ssa-lim-13.c,
>>>>>>> gcc/testsuite/gcc.dg/tree-ssa/ssa-lim-14.c,
>>>>>>>
>>>>>>> gcc/testsuite/gcc.dg/tree-ssa/ssa-lim-15.c,
>>>>>>> gcc/testsuite/gcc.dg/tree-ssa/ssa-lim-16.c,
>>>>>>>
>>>>>>> gcc/testsuite/gcc.dg/tree-ssa/ssa-lim-17.c,
>>>>>>> gcc/testsuite/gcc.dg/tree-ssa/ssa-lim-18.c
>>>>>>>
>>>>>>> the tests for conditional lim.
>>>>>>>
>>>>>>> 4)      Patch testing:
>>>>>>>
>>>>>>> a)      make âk check (no difference in results for me for the clean
>>>>>>> build and the patched one,
>>>>>>>
>>>>>>> -          Revision: 222849,
>>>>>>>
>>>>>>> -          uname -a
>>>>>>>
>>>>>>>                Linux Istanbul 3.16.0-23-generic #31-Ubuntu SMP Tue Oct
>>>>>>> 21 18:00:35 UTC 2014 i686 i686 i686 GNU/Linux
>>>>>>>
>>>>>>> b)      Bootstrap.
>>>>>>>
>>>>>>>  It goes well now, however to fix it I have made a temporary hack in
>>>>>>> the lim code. And with this fix patch definitely shouldnât be
>>>>>>> committed.
>>>>>>>
>>>>>>> I did so, as I would like to discuss this issue first.
>>>>>>>
>>>>>>> The problem is: I got stage2-stage3 comparison failure on the single
>>>>>>> file (tree-vect-data-refs.o). After some investigation I understood
>>>>>>> that tree-vect-data-refs.o differs being compiled with and without
>>>>>>> â-gâ option (yes, more exactly on stage 2 this is  â-g âO2 âgtoggleâ,
>>>>>>> and for stage 3 this is â-g âO2â. But to simplify things I can
>>>>>>> reproduce this difference on the same build (even not bootstrapped),
>>>>>>> with option â âgâ and without it).
>>>>>>>
>>>>>>> Of course, the file compiled with âg option will contain debug
>>>>>>> information and will differ from the corresponding file without debug
>>>>>>> information. I mean there is the difference reported by
>>>>>>> contrib/compare-debug (I mean we talk about stripped files).
>>>>>>>
>>>>>>> Then I compared assemblers and lim dump files and made a conclusion
>>>>>>> the difference is:
>>>>>>>
>>>>>>> There is statement _484=something, which is conditionally moved out of
>>>>>>> loop X. In non debug cases no usages of _484 are left inside the loop
>>>>>>> X. In debug case, there is the single use in debug statement. So for
>>>>>>> debug case my patch generates phi statement for _484 to make it
>>>>>>> available inside the loop X. For non debug case, no such phi statement
>>>>>>> generated as there is no uses of _484.
>>>>>>>
>>>>>>> There is one more statement with lhs=_493, with exactly this pattern
>>>>>>> of use. But this is not important for our discussion.
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> So, in my opinion itâs ok to generate additional phi node for debug
>>>>>>> case. But Iâm not a compiler expert and maybe there is some
>>>>>>> requirement that debug and non-debug versions should differ only by
>>>>>>> debug statements, I donât know.
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> My temporary hack fix is just removing of such debug statements (no
>>>>>>> debug statements, no problems J).
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> The alternatives I see are:
>>>>>>>
>>>>>>> -          Move debug statements outside the loop (not good in my opinion);
>>>>>>>
>>>>>>> -          Somehow reset values in debug statements (not good in my
>>>>>>> opinion, if I could provide correct information for them);
>>>>>>>
>>>>>>> -          Generate phi for debug statements and fix bootstrap (say,
>>>>>>> letâs have some list of files, which we have special check for. I mean
>>>>>>> for my case, the difference is not in stage2 and stage3, itâs in debug
>>>>>>> and non-debug). I like this variant. However, as I donât see such list
>>>>>>> of special files in the whole gcc, I think I might be missing
>>>>>>> something.
>>>>>>>
>>>>>>> What do you think?
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> Thanks,
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> Evgeniya
>>
>>
>>
>> --
>> Thanks,
>>
>> Evgeniya
>>
>> perfstories.wordpress.com



-- 
Thanks,

Evgeniya

perfstories.wordpress.com