From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 35484 invoked by alias); 2 Nov 2016 09:02:26 -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 35472 invoked by uid 89); 2 Nov 2016 09:02:26 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.4 required=5.0 tests=AWL,BAYES_00,FREEMAIL_FROM,RCVD_IN_DNSWL_NONE,RCVD_IN_SORBS_SPAM,SPF_PASS autolearn=no version=3.3.2 spammy= X-HELO: mail-wm0-f65.google.com Received: from mail-wm0-f65.google.com (HELO mail-wm0-f65.google.com) (74.125.82.65) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Wed, 02 Nov 2016 09:02:16 +0000 Received: by mail-wm0-f65.google.com with SMTP id u144so1897263wmu.0 for ; Wed, 02 Nov 2016 02:02:15 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=6QPAHcuQh17h59uFd6u7XLk7KOAJiYv95YaI5ppqidY=; b=J1tRxsLoMpY2bAR3U4HdotwwL7QaVIfG0yXSdcxBHXyx5OlfAK0QNXx9rGDl0O7laO pYAZQfyp1YCGgQcD4kgt2ATQXEHKKKYjwofEzydgKY1Heox62q3tmXwXRZhOpp6/ksaD 23dAY3GJWA6XfUVj3etFzCfebmtU28r3bpxY2Y3yjQdTRNMi91PSMw50k8e9+b8n1O7R UD7rXyjcVKYufNgql6hbk9plPgVZPYzut5scWfPWdPYjmaT4YaBUWWRbeTL5STwP9K0v vUCqDm/4ymOTYqSI6S5QjEsV0O5ktDgu/GjmCPxAVsrklh9ZBhHtIsxFD2iCIgws19I4 3FeQ== X-Gm-Message-State: ABUngvduKgnnBbVO2a3uLjE9nv3QzxaJd18r1PAAtgqiynDDf9w9Huwx2CW82HTPI9e2PPtjnJLNC/mqkal29w== X-Received: by 10.194.81.133 with SMTP id a5mr1939985wjy.86.1478077333974; Wed, 02 Nov 2016 02:02:13 -0700 (PDT) MIME-Version: 1.0 Received: by 10.28.73.215 with HTTP; Wed, 2 Nov 2016 02:02:13 -0700 (PDT) In-Reply-To: <20161031153504.GA3328@gate.crashing.org> References: <3d8d886a7e9d7bcf5bee9867e2f4849a210fd976.1477843149.git.segher@kernel.crashing.org> <20161031153504.GA3328@gate.crashing.org> From: Richard Biener Date: Wed, 02 Nov 2016 09:02:00 -0000 Message-ID: Subject: Re: [PATCH] bb-reorder: Improve compgotos pass (PR71785) To: Segher Boessenkool Cc: Steven Bosscher , GCC Patches Content-Type: text/plain; charset=UTF-8 X-IsSubscribed: yes X-SW-Source: 2016-11/txt/msg00119.txt.bz2 On Mon, Oct 31, 2016 at 4:35 PM, Segher Boessenkool wrote: > On Mon, Oct 31, 2016 at 04:09:48PM +0100, Steven Bosscher wrote: >> On Sun, Oct 30, 2016 at 8:10 PM, Segher Boessenkool wrote: >> > This patch solves this problem by simply running the duplicate_computed_gotos >> > pass again, as long as it does any work. The patch looks much bigger than >> > it is, because I factored out two routines to simplify the control flow. >> >> It's made the patch a bit difficult to read. Condensing it a bit... > > Well, it would have a goto crossing a loop, or two gotos crossing each > other, otherwise. I should have done it as two patches I guess (first > factor, then change). > >> > + for (;;) >> > { >> > + if (n_basic_blocks_for_fn (fun) <= NUM_FIXED_BLOCKS + 1) >> > + return 0; >> >> This test should not be needed in the loop. This pass can never >> collapse the function to a single basic block. > > Yeah maybe, but that relies on quite a few assumptions. This is strictly > an optimisation anyway, will move it outside the loop. > >> > + basic_block bb; >> > + FOR_EACH_BB_FN (bb, fun) >> > + { >> > + /* Build the reorder chain for the original order of blocks. */ >> > + if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (fun)) >> > + bb->aux = bb->next_bb; >> > + } >> > >> > + duplicate_computed_gotos_find_candidates (fun, candidates, max_size); >> > >> > + bool changed = false; >> > + if (!bitmap_empty_p (candidates)) >> > + changed = duplicate_computed_gotos_do_duplicate (fun, candidates); >> > >> > + if (changed) >> > + fixup_partitions (); >> > + >> > + cfg_layout_finalize (); >> >> I don't think you have to go into/out-of cfglayout mode for each iteration. > > Yeah probably. I was too lazy :-) It needs the cleanup_cfg every > iteration though, I was afraid that interacts. Ick. Why would it need a cfg-cleanup every iteration? I fear this is quadratic complexity in the number of edges to the compgoto block (and the size of the function). Can't the unfactoring perform the "cleanup" we rely on here? >> > /* Merge the duplicated blocks into predecessors, when possible. */ >> > + if (changed) >> > + cleanup_cfg (0); >> > + else >> > + break; >> > } >> >> Maybe a gcc_assert that the loop doesn't iterate more often than num_edges? > > Good plan (num blocks even). > > Thanks, > > > Segher