From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 57717 invoked by alias); 2 Aug 2017 09:53:43 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 56568 invoked by uid 89); 2 Aug 2017 09:53:41 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.3 required=5.0 tests=AWL,BAYES_00,KAM_LAZY_DOMAIN_SECURITY,RP_MATCHES_RCVD autolearn=no version=3.3.2 spammy=Ball X-Spam-User: qpsmtpd, 2 recipients X-HELO: nikam.ms.mff.cuni.cz Received: from nikam.ms.mff.cuni.cz (HELO nikam.ms.mff.cuni.cz) (195.113.20.16) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Wed, 02 Aug 2017 09:53:40 +0000 Received: by nikam.ms.mff.cuni.cz (Postfix, from userid 16202) id EB29354938B; Wed, 2 Aug 2017 11:53:36 +0200 (CEST) Date: Wed, 02 Aug 2017 09:53:00 -0000 From: Jan Hubicka To: Yuri Gribov Cc: GCC Patches , marxin@gcc.gnu.org Subject: Re: [PATCH][PR 59521] Respect probabilities when expanding switch statement Message-ID: <20170802095336.GD98370@kam.mff.cuni.cz> References: <20170718074519.GA55807@kam.mff.cuni.cz> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.23 (2014-03-12) X-SW-Source: 2017-08/txt/msg00152.txt.bz2 Hello, sorry for not responding for a while. Martin Liska has patch to move switch expansion to gimple level that will likely simplify the code combinatoin. > > combine_predictions_for_bb calculates final probability for edges of > if-else or switch statements. > > For if-elses this is done by combining values computed by different > predictors using Dempster-Shafer theory. For switch statement DS is > not used, mainly because we do not have heuristics for predicting > which case will be taken (paper by Larus concluded that using if-else > heuristics does not give good results). > > So until this patch we just used set_even_probabilities. The name of > this function is misleading, in addition to setting even probabilities > it can also understand that some edges are very unlikely and set > unlikely probs for those. With patch it now also understands that one > edge is very likely. I am not sure that the conclusion of Ball&Larus paper applies to us here. In addition to usual if-then-else heuristics we have those based on walk of CFG (such as ones predicting paths to unlikely calls) and those should work well on switch statements. We discussed adding predictor combining code for BBs with more than 2 successors. Martin, do you have some code for that? I guess teaching even propbabilities about likely edges also works, but perhaps doing more general prediction combining would be cleaner... Honza