From patchwork Tue Oct 18 14:03:48 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 683722 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 3syxdQ0nPnz9s8x for ; Wed, 19 Oct 2016 01:04:09 +1100 (AEDT) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=T/12PyGy; dkim-atps=neutral DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type; q=dns; s= default; b=OuPKP0knXKvdqKYdZPsSADA6WQZS8ZX5IRHwHYQcRtmqsddd5DGtz FSQSBKOF7XxXlSzbMOnFhbL1hq2YgcKFoEIKYblZROpL9tb4gB9+tvxFYz+ARr+w ahdXH8+E6J3dM+1upEcYJa1SU9N5VHsGcYkAsOETOM3DUGmVi6sXC0= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type; s= default; bh=E3D25eVtRDZjhDvPY9quUWKBwU4=; b=T/12PyGy/J/wH/PeiVRq g2KUplQJSYZ5hEHVQAMA6QWggUWE1x6gtbOREIZaXyeJzsfXZxN0DHfo8eaS98I2 ZC6fnpio2RFkXuE3hWdIgN1S5cIACRe96UZCIMxtaOSwmL27rgOsDDdO+1KubQ47 XXPxGGR4K0hqTo+8DcLATWg= Received: (qmail 129478 invoked by alias); 18 Oct 2016 14:04:02 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 128172 invoked by uid 89); 18 Oct 2016 14:04:00 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.2 required=5.0 tests=BAYES_00, RP_MATCHES_RCVD, SPF_PASS autolearn=ham version=3.3.2 spammy=boo, sk:inverte, bla, Hx-languages-length:1363 X-HELO: mx2.suse.de Received: from mx2.suse.de (HELO mx2.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 18 Oct 2016 14:03:50 +0000 Received: from relay2.suse.de (charybdis-ext.suse.de [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id 7C3FDAD70 for ; Tue, 18 Oct 2016 14:03:48 +0000 (UTC) Date: Tue, 18 Oct 2016 16:03:48 +0200 (CEST) From: Richard Biener To: gcc-patches@gcc.gnu.org Subject: [PATCH] Use RPO order for domwalk dominator children sort Message-ID: User-Agent: Alpine 2.11 (LSU 23 2013-08-11) MIME-Version: 1.0 For extern void baz (); extern void boo (); extern void bla (); int a[100]; void foo (int n) { for (int j = 0; j < n; ++j) { if (a[j+5]) { if (a[j]) break; baz (); } else bla (); boo (); } } we happen to visit BBs in an unfortunate order so that we do not have all predecessors visited when visiting the BB of boo(). This is because domwalk uses a postorder on the inverted graph to order dominator children -- that doesn't play well with loops (as we've figured elsewhere before). The following makes us use RPO order instead. This should help EVRP and DOM. Bootstrap & regtest running on x86_64-unknown-linux-gnu. Richard. 2016-10-18 Richard Biener * domwalk.c (dom_walker::walk): Use RPO order. Index: gcc/domwalk.c =================================================================== --- gcc/domwalk.c (revision 241300) +++ gcc/domwalk.c (working copy) @@ -243,7 +243,7 @@ dom_walker::walk (basic_block bb) if (m_dom_direction == CDI_DOMINATORS) { postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun)); - postorder_num = inverted_post_order_compute (postorder); + postorder_num = pre_and_rev_post_order_compute (NULL, postorder, true); bb_postorder = XNEWVEC (int, last_basic_block_for_fn (cfun)); for (int i = 0; i < postorder_num; ++i) bb_postorder[postorder[i]] = i;