From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ej1-x644.google.com (mail-ej1-x644.google.com [IPv6:2a00:1450:4864:20::644]) by sourceware.org (Postfix) with ESMTPS id 6AFBD3951896 for ; Tue, 6 Oct 2020 07:48:03 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 6AFBD3951896 Received: by mail-ej1-x644.google.com with SMTP id u21so16217222eja.2 for ; Tue, 06 Oct 2020 00:48:03 -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=oPjdX6e5xkEz9DxYnQuYR2GhM44eSyhhHtq+FpVjDN8=; b=E49uVGBTQWdu7PgOncFocUE9xOL/5lkAN4EjQu6SPd9q8ut6Ux2wx5VZBmtbIU4qlX 5Fvcfg/GdCkUKiOQDMB8/aVQ4cOXQJufhTg00g+sx+gYyGfOL9yCgspo9TwWJktmkbK+ UG+Qf7ybv0SzTVcFDho0QsStz8juYERAoycQDa0028Qdzu4B8uKSBW9VTZ+OvV4Nhvs3 cbyxsRHggWj6tNmAcQKHNjMoRHsMBnljopbcIRnIGg45YFto3WI1u6OcdD/i/KNEk1Xe uF2f6sbBToW7mRp6+8QE7jAcpeiX1ZnDt21Y5Zdlj9iG+T+taYAjYVRGr30eNYkZlH18 wzwg== X-Gm-Message-State: AOAM530WBogxVGfURg6a5fr1yGTUUIDZN4ufXVkAI9dEeaAX7QWpK9HZ uHj23NDhx3bU6c39kg/2vp8ebmzxMci/BjTKzgY= X-Google-Smtp-Source: ABdhPJw/SxtOTl7+SH+eUg+lpKPfaq8bAE41DKHMP6qkzXjCplbZSrztj8DD8tjLDa9Sp53RbYBkibTEKJGcMSKaBco= X-Received: by 2002:a17:906:6bce:: with SMTP id t14mr3879815ejs.118.1601970482417; Tue, 06 Oct 2020 00:48:02 -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, 6 Oct 2020 09:47:51 +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 , 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, 06 Oct 2020 07:48:05 -0000 On Fri, Oct 2, 2020 at 3:23 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. > > > > I noticed several functions without a function-level comment. > > > > - 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 ... > > Hey. > > This one is needed, otherwise we'll have a compilation error (multiple de= finitions). > > > > > +@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. > > All right, I'm planning to come up with -fbit-tests options and this tran= sformation > will happen only if BT or JT are enabled. > > > > > + /* For now, just wipe the dominator information. */ > > + free_dominance_info (CDI_DOMINATORS); > > > > could at least be conditional on the vop renaming condition... > > How do you mean this? don't free dominators if you didn't change anything. > > > > + if (!all_candidates.is_empty ()) > > + mark_virtual_operands_for_renaming (fun); > > > > + 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 > > Yes, sbitmap would be better. > > > > > if (!bitmap_set_bit (*visited_bbs, bb->index)) > > break; > > Unfortunately, bitmap_set_bit for sbitmap is a void return function. > Should I change it? No, with sbitmaps you have to keep your current code. > > > > + /* 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 > > > > + /* 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). > > > > + /* 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? > > > > + if (arg !=3D *v) > > + return false; > > This one is really needed for situations like: > > cat wchar.i > int i; > > int > pg_utf_mblen() { > int len; > if (i =3D=3D 4) > len =3D 3; > else if (i =3D=3D 2) > len =3D 4; > else if (i =3D=3D 6) > len =3D 1; > return len; > } > > where we end up just with one edge from switch BB to a destination BB whe= re > we have the PHI: > # len_4 =3D PHI <3(2), 4(3), len_6(D)(4), 1(5)> Yeah, see my comment on how to deal with this in code generation (introduce a forwarder block). > > > > 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). > > No, the m_phi_map is destroyed when we call 'delete chain'. > > > > > + 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. > > Good idea. > > > > > + /* 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. > > Well, I was thinking about this one more time. I would like to see > a first version that will handle the simple chains that are trivial > switch statements: > > if (x =3D=3D 1) > else if (x ..) > ... > > that was my original motivation and it has quite nice coverage. > Later we can support code hoisting and negative expressions > like x !=3D 123. Hopefully the upcoming Ranger infrastructure can help > us here. Is it acceptable approach for upcoming GCC 11? But is it really extensible with the current implementation? I doubt so. Richard. > Martin > > > > > 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). > > 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. > > > > + 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? > > > > 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). > > > > + /* 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 ... > > > > + 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 >