From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 31982 invoked by alias); 19 Nov 2004 22:46:46 -0000 Mailing-List: contact gcc-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Archive: List-Post: List-Help: Sender: gcc-owner@gcc.gnu.org Received: (qmail 31674 invoked from network); 19 Nov 2004 22:46:18 -0000 Received: from unknown (HELO mx1.redhat.com) (66.187.233.31) by sourceware.org with SMTP; 19 Nov 2004 22:46:18 -0000 Received: from int-mx1.corp.redhat.com (int-mx1.corp.redhat.com [172.16.52.254]) by mx1.redhat.com (8.12.11/8.12.11) with ESMTP id iAJMkHF0031617; Fri, 19 Nov 2004 17:46:17 -0500 Received: from vpn50-60.rdu.redhat.com (vpn50-60.rdu.redhat.com [172.16.50.60]) by int-mx1.corp.redhat.com (8.11.6/8.11.6) with ESMTP id iAJMkCr00527; Fri, 19 Nov 2004 17:46:12 -0500 Subject: Slow profile updating (pr 15524) From: Jeffrey A Law Reply-To: law@redhat.com To: jh@suse.com Cc: gcc@gcc.gnu.org Content-Type: text/plain Organization: Red Hat, Inc Date: Sat, 20 Nov 2004 00:41:00 -0000 Message-Id: <1100904370.27318.54.camel@localhost.localdomain> Mime-Version: 1.0 Content-Transfer-Encoding: 7bit X-SW-Source: 2004-11/txt/msg00705.txt.bz2 Believe it or not we're at a point where updating of the profile in response to a jump thread is the most expensive routine in the compiler for PR 15524. If we look up update_bb_profile_for_threading we see one loop of significance: else FOR_EACH_EDGE (c, ei, bb->succs) c->probability = ((c->probability * REG_BR_PROB_BASE) / (double) prob); So anytime we thread through some block BB, we have to walk through all its successors to rescale their probabilities. Needless to say that gets rather expensive, especially if BB has a large switch statement and several of its incoming edges are threadable. Is it the case that the computation of c->probability actually has to happen in the order you specified via the parenthesis? If not, then we could precompute REG_BR_PROB_BASE / (double) prob outside the loop which would result in a loop like tmp = REG_BR_PROB_BASE / (double) prob; FOR_EACH_EDGE (c, ei, bb->succs) c->probability *= tmp; Which would probably provide a reasonable improvement. And if that's safe, then we'd probably want to rewrite it like else if (prob != REG_BR_PROB_BASE) { double tmp = REG_BR_PROB_BASE / (double) prob; FOR_EACH_EDGE 9c, ei, bb->succs) c->probability *= tmp; } Which avoids the loop completely if nothing is going to change (as is the case for pr15524). Doing something like this would give us a net improvement of 15-20% on PR 15524. Alternately we might want to look at whether or not we can rescale the successor blocks en-masse after all the redirections for a particular block are complete. Thoughts? jeff