From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ej1-x643.google.com (mail-ej1-x643.google.com [IPv6:2a00:1450:4864:20::643]) by sourceware.org (Postfix) with ESMTPS id 8A0263861812; Tue, 29 Sep 2020 08:47:09 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 8A0263861812 Received: by mail-ej1-x643.google.com with SMTP id o8so13825636ejb.10; Tue, 29 Sep 2020 01:47:09 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc:content-transfer-encoding; bh=/Ea2YjA8WcdcbEzNOZjlPmCqgkkNIoQpn+3IJSFXQtA=; b=QuVumhdcAe2B5Oj1tHmWHd0TVZvG0M/nqEnvjXGP6pdXIxtMiDqC0ppJuNDw0/m/0h relCbGnCyqKiQ6gLnYF1UdDVM3JEGvSD+m8dajEou67JALVBBQfN1MlUED+suvEgjAD7 z6HP3JcFR22nA/mmL5r6pIyGkZ/K982smWOhAFs0fCdeuKJmfHdl4KjG8c/yGmqV5sV0 hC6avzyxvDcvlafa55z1X84AkonWK0Y7MHe4Rro4rwX22xW4VrzK3X14Da3907wNoMMs QNDWJVj2f1Vp9IjvoAHeHpBrgSMDumctenbnudVWgr9o0h8TyyvbeDckerjveyTYW3fh vqBw== X-Gm-Message-State: AOAM530WfdiZHqqtqw0QMGicbPJdJuLHWef0edCy35esAQpFT10ap7rr lE5ao3XzAFmxzFStEiEcVyoRywbRE2sffXd5S4Y= X-Google-Smtp-Source: ABdhPJw9OuOpbDNoJ83wNpv/HP8uJxnKO7mfgRuubYHzjJr4yPcgAKfoArP7CNmyNYAHJa4000x3Ul4PAQ2a/E3dbPg= X-Received: by 2002:a17:906:91d3:: with SMTP id b19mr2841105ejx.235.1601369228492; Tue, 29 Sep 2020 01:47:08 -0700 (PDT) MIME-Version: 1.0 References: <2c3db526-cac6-4eeb-4afb-12024f8d5af2@suse.cz> <20191104144851.GJ4650@tucnak> <6169f91a-4884-55f5-c76f-ea1dae11d996@suse.cz> <35eb0279-77d8-36f8-3ab7-afb9ae97fdb3@suse.cz> <42c91f11-c1a6-3ae4-08da-0a0b77f63b80@suse.cz> <72541e13d26f92577637b8f0e23d82435f35ddea.camel@redhat.com> In-Reply-To: From: Richard Biener Date: Tue, 29 Sep 2020 10:46:57 +0200 Message-ID: Subject: Re: [PATCH] Add if-chain to switch conversion pass. To: =?UTF-8?Q?Martin_Li=C5=A1ka?= Cc: David Malcolm , Jakub Jelinek , kazu@gcc.gnu.org, GCC Patches , Jan Hubicka Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-1.7 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 29 Sep 2020 08:47:11 -0000 On Fri, Sep 25, 2020 at 4:05 PM Martin Li=C5=A1ka wrote: > > On 9/24/20 2:41 PM, Richard Biener wrote: > > On Wed, Sep 2, 2020 at 1:53 PM Martin Li=C5=A1ka wrote= : > >> > >> On 9/1/20 4:50 PM, David Malcolm wrote: > >>> Hope this is constructive > >>> Dave > >> > >> Thank you David. All of them very very useful! > >> > >> There's updated version of the patch. > > Hey. > > What a juicy patch review! > > > > > I noticed several functions without a function-level comment. > > Yep, but several of them are documented in a class declaration. Anyway, I= will > improve for the next time. > > > > > - cluster (tree case_label_expr, basic_block case_bb, profile_probabil= ity prob, > > - profile_probability subtree_prob); > > + inline cluster (tree case_label_expr, basic_block case_bb, > > + profile_probability prob, profile_probability subtree= _prob); > > > > I thought we generally leave this to the compiler ... > > > > +@item -fconvert-if-to-switch > > +@opindex fconvert-if-to-switch > > +Perform conversion of an if cascade into a switch statement. > > +Do so if the switch can be later transformed using a jump table > > +or a bit test. The transformation can help to produce faster code for > > +the switch statement. This flag is enabled by default > > +at @option{-O2} and higher. > > > > this mentions we do this only when we later can convert the > > switch again but both passes (we still have two :/) have > > independent guards. > > Yes, we have the option for jump tables (-jump-tables), but we miss one f= or a bit-test. > Moreover, as mentioned in the cover email, one can see it beneficial to c= onvert a if-chain > to switch as the expansion (without any BT and JT) can benefit from balan= ced tree. > > > > > + /* For now, just wipe the dominator information. */ > > + free_dominance_info (CDI_DOMINATORS); > > > > could at least be conditional on the vop renaming condition... > > > > + if (!all_candidates.is_empty ()) > > + mark_virtual_operands_for_renaming (fun); > > Yep. > > > > > + if (bitmap_bit_p (*visited_bbs, bb->index)) > > + break; > > + bitmap_set_bit (*visited_bbs, bb->index); > > > > since you are using a bitmap and not a sbitmap (why?) > > you can combine those into > > New to me, thanks. > > > > > if (!bitmap_set_bit (*visited_bbs, bb->index)) > > break; > > > > + /* Current we support following patterns (situations): > > + > > + 1) if condition with equal operation: > > + > > ... > > > > did you see whether using > > > > register_edge_assert_for (lhs, true_edge, code, lhs, rhs, asserts); > > > > works equally well? It fills the 'asserts' vector with relations > > derived from 'lhs'. There's also > > vr_values::extract_range_for_var_from_comparison_expr > > to compute the case_range > > Good point! I must admit that my patch doesn't properly handle negative c= onditions: > > if (argc !=3D 11111) > { > if (argc =3D=3D 1) > global =3D 222; > ... > } > > which can VRP correctly identify as anti-range: > int ~[11111, 11111] EQUIVALENCES: { argc_8(D) } (1 elements)$1 =3D void > > I have question about OR and AND conditions: > > : > _1 =3D aChar_8(D) =3D=3D 1; > _2 =3D aChar_8(D) =3D=3D 10; > _3 =3D _1 | _2; > if (_3 !=3D 0) > goto ; [INV] > else > goto ; [INV] > > : > _1 =3D aChar_8(D) !=3D 1; > _2 =3D aChar_8(D) !=3D 10; > _3 =3D _1 & _2; > if (_3 !=3D 0) > goto ; [INV] > else > goto ; [INV] > > Can I somehow get that from VRP (as I ask register_edge_assert_for only f= or LHS > of a condition)? Yes, you simply get all sorts of conditions that hold when a condition is true, not just those based on the SSA name you put in. But it occured to me that the use-case is somewhat different - for switch-conversion you want to know whether the test _exactly_ matches a range test, the VRP worker will not tell you that. For example if you had if (x && a > 3 && a < 7) then it will give you 'a in [4, 6]' and it might not give you 'x in [1, 1]' (for example if x is float). But that's require= d for correctness. So we're back to your custom crafted code unless we manage to somehow refactor the VRP condition analysis to handle both cases (should be possible I think, but have not looked too closely). Maybe the actual matching pieces can be shared at least. > > > > + /* If it's not the first condition, then we need a BB without > > + any statements. */ > > + if (!first) > > + { > > + unsigned stmt_count =3D 0; > > + for (gimple_stmt_iterator gsi =3D gsi_start_nondebug_bb (bb); > > + !gsi_end_p (gsi); gsi_next_nondebug (&gsi)) > > + ++stmt_count; > > + > > + if (stmt_count - visited_stmt_count !=3D 0) > > + break; > > > > hmm, OK, this might be a bit iffy to get correct then, still it's a lot > > of pattern maching code that is there elsewhere already. > > ifcombine simply hoists any stmts without side-effects up the > > dominator tree and thus only requires BBs without side-effects > > (IIRC there's a predicate fn for that). > > Yes, I completely miss support for code hoisting (expect first BB where w= e put gswitch). > If I'm correct hoisting should be possible where case destination should = be a new BB > that will contain original statements and then it will jump to a case des= tination block. > > > > > + /* Prevent loosing information for a PHI node where 2 edges will > > + be folded into one. Note that we must do the same also for fa= lse_edge > > + (for last BB in a if-elseif chain). */ > > + if (!chain->record_phi_arguments (true_edge) > > + || !chain->record_phi_arguments (false_edge)) > > > > I don't really get this - looking at record_phi_arguments it seems > > we're requiring that all edges into the same PHI from inside the case > > (irrespective of from which case label) have the same value for the > > PHI arg? > > I guess so, I'll refresh the functionality. > > > > > + if (arg !=3D *v) > > + return false; > > > > should use operand_equal_p at least, REAL_CSTs are for example > > not shared tree nodes. I'll also notice that if record_phi_arguments > > fails we still may have altered its hash-map even though the particular > > edge will not participate in the current chain, so it will affect other > > chains ending in the same BB. Overall this looks a bit too conservativ= e > > (and random, based on visiting order). > > Oh, yes, it's not properly cleared once we bail out for a particular chai= n. > > > > > + expanded_location loc > > + =3D expand_location (gimple_location (chain->m_first_condition)); > > + if (dump_file) > > + { > > + fprintf (dump_file, "Condition chain (at %s:%d) with %d condi= tions " > > + "(%d BBs) transformed into a switch statement.\n", > > + loc.file, loc.line, total_case_values, > > + chain->m_entries.length ()); > > > > Use dump_printf_loc and you can pass a gimple * stmt as location. > > > > + /* Follow if-elseif-elseif chain. */ > > + bb =3D false_edge->dest; > > > > so that means the code doesn't handle a tree, right? But what > > makes us sure the chain doesn't continue on the true_edge instead, > > guess this degenerate tree isn't handled either. > > As mentioned earlier, I didn't consider VAR !=3D CST type of conditions t= hat > makes it more complicated. > > > > > I was thinking on whether doing the switch discovery in a reverse > > CFG walk, recording for each BB what case_range(s) it represents > > for a particular variable(s) so when visiting a dominator you > > can quickly figure what's the relevant children (true, false or both). > > Sounds promising. Note that right now we do not support overlapping cases= like: > > if (5 <=3D argc && argc <=3D 10) > foo (); > else if (6 <=3D argc && argc <=3D 100) > foo (); > > So I'm wondering if we can support 2 children? > > > It would also make the matching a BB-local operation where you'd > > do the case_label discovery based on the single-pred BBs gimple-cond. > > Can you please describe more how will the walk work? > > > > > + output =3D bit_test_cluster::find_bit_tests (filtered_clusters); > > + r =3D output.length () < filtered_clusters.length (); > > + if (r) > > + dump_clusters (&output, "BT can be built"); > > > > so as of the very above comment - this might be guarded with > > flag_tree_switch_conversion? > > flag_tree_switch_conversion isn't connected to the if-chain pass (yet). > > > > > As mentioned previously I would have liked to see if-to-switch > > integrated with switch-conversion, having separate passes is > > somewhat awkward (for example the redundant and possibly > > expensive find_bit_tests). > > Well, the CFG transformation for BT and JT is not trivial and I would lik= e > to go in the first iteration through gswitch statements. > I have a massive speed up for the find_bit_tests/find_jump_tables. > > > > > + /* Move all statements from the BB to the BB with gswitch. *= / > > + auto_vec stmts; > > + for (gimple_stmt_iterator gsi =3D gsi_start_bb (entry.m_bb); > > + !gsi_end_p (gsi); gsi_next (&gsi)) > > + { > > + gimple *stmt =3D gsi_stmt (gsi); > > + if (gimple_code (stmt) !=3D GIMPLE_COND) > > + stmts.safe_push (stmt); > > + } > > + > > + for (unsigned i =3D 0; i < stmts.length (); i++) > > + { > > + gimple_stmt_iterator gsi_from =3D gsi_for_stmt (stmts[i])= ; > > + gsi_move_before (&gsi_from, &gsi); > > + } > > > > so you are already hoisting all stmts ... > > As mentioned, it's not supported right now. This moves all these kind of = "temp" statements: > > _1 =3D aChar_8(D) =3D=3D 1; > _2 =3D aChar_8(D) =3D=3D 10; > _3 =3D _1 | _2; Sure, but that _is_ hoisting of all stmts. > Martin > > > > > + make_edge (first_cond.m_bb, case_bb, 0); > > > > and if this doesn't create a new edge you need equivalent PHI > > args in the case_bb. To remove this restriction you "only" > > have to add a forwarder. Sth like > > > > edge e =3D make_edge (...); > > if (!e) > > { > > bb =3D create_basic_block (); > > make_edge (first_cond.m_bb, bb, 0); > > e =3D make_edge (bb, case_bb, 0); > > } > > fill PHI arg of 'e' from original value (no need to create the hash-= map then) > > > > Richard. > > > > > >> Martin >