On Wed, Jul 15, 2015 at 10:36 AM, Evgeniya Maenkova <evgeniya.maenk...@gmail.com> wrote: > On Tue, Jul 14, 2015 at 2:54 PM, Richard Biener > <richard.guent...@gmail.com> wrote: >> On Mon, Jun 29, 2015 at 4:21 PM, Evgeniya Maenkova >> <evgeniya.maenk...@gmail.com> wrote: >>> On Mon, Jun 29, 2015 at 5:10 PM, Richard Biener >>> <richard.guent...@gmail.com> wrote: >>>> On Tue, Jun 9, 2015 at 10:11 PM, Evgeniya Maenkova >>>> <evgeniya.maenk...@gmail.com> wrote: >>>>> On Tue, Jun 9, 2015 at 3:46 PM, Richard Biener >>>>> <richard.guent...@gmail.com> wrote: >>>>>> On Fri, May 29, 2015 at 3:14 PM, Evgeniya Maenkova >>>>>> <evgeniya.maenk...@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.
My comment was about the lack of a testcase for this in the patch submission. But my whole point is that supporting this should be split off to a followup patch to make both patches easier to review. Richard. >> >> 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.maenk...@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