From patchwork Thu Nov 21 14:48:32 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 1198989 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-514322-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=suse.de Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="uB/8j24x"; dkim-atps=neutral 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 47Jj9t3vywz9sQy for ; Fri, 22 Nov 2019 01:48:48 +1100 (AEDT) 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=FqNu/6d/rAmVjWYFap6E/tman/F9iLZrPXdCSolnlaPUGOHOFlRoV aJz7LI0eS0Hg6H9MuysEYKV2KpHj38i/busBkuWKmTcQfpxWCevt0t17qQQhUZkl jvU1KdJPSSmjJOkobS+77ZSsxFAXmhJDt5HWQ4JyOAVSfYQj/7hjc0= 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=ASMKxgxVAC8igpxksHzlcK7AAFk=; b=uB/8j24xstY4SRqI2ImI os0HifPFL78+hEYnfed+c66dzHOiDujfKrwt30ooz0jNvv8zQatPEhD4ZXtdmi8+ FayKzT8gziIyRT2kG9xdvTb6fbAELrYMc8EdKa4Ah65pNKcvdm9ZYuXF5TvKXlXM AcUbrrLEQ3a7xjZhdW5UZZc= Received: (qmail 107088 invoked by alias); 21 Nov 2019 14:48:41 -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 107017 invoked by uid 89); 21 Nov 2019 14:48:38 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-10.6 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_2, GIT_PATCH_3, KAM_ASCII_DIVIDERS, SPF_PASS autolearn=ham version=3.3.1 spammy=defaulted, gsi_stmt, cfgloop.c, UD:cfgloop.c X-HELO: mx1.suse.de Received: from mx2.suse.de (HELO mx1.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Thu, 21 Nov 2019 14:48:35 +0000 Received: from relay2.suse.de (unknown [195.135.220.254]) by mx1.suse.de (Postfix) with ESMTP id C4FF4ADD9 for ; Thu, 21 Nov 2019 14:48:32 +0000 (UTC) Date: Thu, 21 Nov 2019 15:48:32 +0100 (CET) From: Richard Biener To: gcc-patches@gcc.gnu.org Subject: [PATCH] Avoid excessive get_loop_body calls Message-ID: User-Agent: Alpine 2.21 (LSU 202 2017-01-01) MIME-Version: 1.0 This cuts down the number significantly coming from estimate_numbers_of_iterations where even loop exits may not be computed in some callers and thus the single_exit () early-outs do not work. Bootstrapped on x86_64-unknown-linux-gnu, testing in progress. Richard. 2019-11-21 Richard Biener * cfgloop.h (get_loop_exit_edges): Add extra parameter denoting loop body, defaulted to NULL. (single_likely_exit): Add exit vector argument * tree-ssa-loop-niter.h (loop_only_exit_p): Add loop body argument. (number_of_iterations_exit): Likewise. (number_of_iterations_exit_assumptions): Likewise. * cfgloop.c (get_loop_exit_edges): Use passed in loop body if not NULL. * cfgloopanal.c (single_likely_exit): Use passed in exit vector. * tree-ssa-loop-ivcanon.c (canonicalize_loop_induction_variables): Compute exit vector around call to single_likely_exit. * tree-ssa-loop-ivopts.c (tree_ssa_iv_optimize_loop): Pass down loop body to loop_only_exit_p. * tree-ssa-loop-niter.c (loop_only_exit_p): Get loop body from caller. (number_of_iterations_exit_assumptions): Get loop body from caller if not NULL. (number_of_iterations_exit): Pass through new loop body arg. (infer_loop_bounds_from_undefined): Get loop body from caller. (estimate_numbers_of_iterations): Compute loop body once. Index: gcc/cfgloop.c =================================================================== --- gcc/cfgloop.c (revision 278550) +++ gcc/cfgloop.c (working copy) @@ -1203,12 +1203,11 @@ release_recorded_exits (function *fn) /* Returns the list of the exit edges of a LOOP. */ vec -get_loop_exit_edges (const class loop *loop) +get_loop_exit_edges (const class loop *loop, basic_block *body) { vec edges = vNULL; edge e; unsigned i; - basic_block *body; edge_iterator ei; struct loop_exit *exit; @@ -1223,14 +1222,20 @@ get_loop_exit_edges (const class loop *l } else { - body = get_loop_body (loop); + bool body_from_caller = true; + if (!body) + { + body = get_loop_body (loop); + body_from_caller = false; + } for (i = 0; i < loop->num_nodes; i++) FOR_EACH_EDGE (e, ei, body[i]->succs) { if (!flow_bb_inside_loop_p (loop, e->dest)) edges.safe_push (e); } - free (body); + if (!body_from_caller) + free (body); } return edges; Index: gcc/cfgloop.h =================================================================== --- gcc/cfgloop.h (revision 278550) +++ gcc/cfgloop.h (working copy) @@ -379,9 +379,9 @@ extern basic_block *get_loop_body_in_cus extern basic_block *get_loop_body_in_custom_order (const class loop *, void *, int (*) (const void *, const void *, void *)); -extern vec get_loop_exit_edges (const class loop *); +extern vec get_loop_exit_edges (const class loop *, basic_block * = NULL); extern edge single_exit (const class loop *); -extern edge single_likely_exit (class loop *loop); +extern edge single_likely_exit (class loop *loop, vec); extern unsigned num_loop_branches (const class loop *); extern edge loop_preheader_edge (const class loop *); Index: gcc/cfgloopanal.c =================================================================== --- gcc/cfgloopanal.c (revision 278550) +++ gcc/cfgloopanal.c (working copy) @@ -467,16 +467,14 @@ mark_loop_exit_edges (void) to noreturn call. */ edge -single_likely_exit (class loop *loop) +single_likely_exit (class loop *loop, vec exits) { edge found = single_exit (loop); - vec exits; unsigned i; edge ex; if (found) return found; - exits = get_loop_exit_edges (loop); FOR_EACH_VEC_ELT (exits, i, ex) { if (probably_never_executed_edge_p (cfun, ex) @@ -489,12 +487,8 @@ single_likely_exit (class loop *loop) if (!found) found = ex; else - { - exits.release (); - return NULL; - } + return NULL; } - exits.release (); return found; } Index: gcc/tree-ssa-loop-ivcanon.c =================================================================== --- gcc/tree-ssa-loop-ivcanon.c (revision 278550) +++ gcc/tree-ssa-loop-ivcanon.c (working copy) @@ -1222,8 +1222,10 @@ canonicalize_loop_induction_variables (c by find_loop_niter_by_eval. Be sure to keep it for future. */ if (niter && TREE_CODE (niter) == INTEGER_CST) { + vec exits = get_loop_exit_edges (loop); record_niter_bound (loop, wi::to_widest (niter), - exit == single_likely_exit (loop), true); + exit == single_likely_exit (loop, exits), true); + exits.release (); } /* Force re-computation of loop bounds so we can remove redundant exits. */ Index: gcc/tree-ssa-loop-ivopts.c =================================================================== --- gcc/tree-ssa-loop-ivopts.c (revision 278550) +++ gcc/tree-ssa-loop-ivopts.c (working copy) @@ -7977,7 +7977,8 @@ tree_ssa_iv_optimize_loop (struct ivopts data->body_includes_call = loop_body_includes_call (body, loop->num_nodes); renumber_gimple_stmt_uids_in_blocks (body, loop->num_nodes); - data->loop_single_exit_p = exit != NULL && loop_only_exit_p (loop, exit); + data->loop_single_exit_p + = exit != NULL && loop_only_exit_p (loop, body, exit); /* For each ssa name determines whether it behaves as an induction variable in some loop. */ Index: gcc/tree-ssa-loop-niter.c =================================================================== --- gcc/tree-ssa-loop-niter.c (revision 278550) +++ gcc/tree-ssa-loop-niter.c (working copy) @@ -2367,27 +2367,23 @@ simplify_using_outer_evolutions (class l /* Returns true if EXIT is the only possible exit from LOOP. */ bool -loop_only_exit_p (const class loop *loop, const_edge exit) +loop_only_exit_p (const class loop *loop, basic_block *body, const_edge exit) { - basic_block *body; gimple_stmt_iterator bsi; unsigned i; if (exit != single_exit (loop)) return false; - body = get_loop_body (loop); for (i = 0; i < loop->num_nodes; i++) { for (bsi = gsi_start_bb (body[i]); !gsi_end_p (bsi); gsi_next (&bsi)) if (stmt_can_terminate_bb_p (gsi_stmt (bsi))) { - free (body); return true; } } - free (body); return true; } @@ -2403,7 +2399,8 @@ loop_only_exit_p (const class loop *loop bool number_of_iterations_exit_assumptions (class loop *loop, edge exit, class tree_niter_desc *niter, - gcond **at_stmt, bool every_iteration) + gcond **at_stmt, bool every_iteration, + basic_block *body) { gimple *last; gcond *stmt; @@ -2477,8 +2474,17 @@ number_of_iterations_exit_assumptions (c iv0.base = expand_simple_operations (iv0.base); iv1.base = expand_simple_operations (iv1.base); + bool body_from_caller = true; + if (!body) + { + body = get_loop_body (loop); + body_from_caller = false; + } + bool only_exit_p = loop_only_exit_p (loop, body, exit); + if (!body_from_caller) + free (body); if (!number_of_iterations_cond (loop, type, &iv0, code, &iv1, niter, - loop_only_exit_p (loop, exit), safe)) + only_exit_p, safe)) { fold_undefer_and_ignore_overflow_warnings (); return false; @@ -2721,11 +2727,12 @@ number_of_iterations_popcount (loop_p lo bool number_of_iterations_exit (class loop *loop, edge exit, class tree_niter_desc *niter, - bool warn, bool every_iteration) + bool warn, bool every_iteration, + basic_block *body) { gcond *stmt; if (!number_of_iterations_exit_assumptions (loop, exit, niter, - &stmt, every_iteration)) + &stmt, every_iteration, body)) return false; if (integer_nonzerop (niter->assumptions)) @@ -3837,16 +3844,13 @@ infer_loop_bounds_from_signedness (class */ static void -infer_loop_bounds_from_undefined (class loop *loop) +infer_loop_bounds_from_undefined (class loop *loop, basic_block *bbs) { unsigned i; - basic_block *bbs; gimple_stmt_iterator bsi; basic_block bb; bool reliable; - bbs = get_loop_body (loop); - for (i = 0; i < loop->num_nodes; i++) { bb = bbs[i]; @@ -3871,8 +3875,6 @@ infer_loop_bounds_from_undefined (class } } - - free (bbs); } /* Compare wide ints, callback for qsort. */ @@ -4275,8 +4277,9 @@ estimate_numbers_of_iterations (class lo diagnose those loops with -Waggressive-loop-optimizations. */ number_of_latch_executions (loop); - exits = get_loop_exit_edges (loop); - likely_exit = single_likely_exit (loop); + basic_block *body = get_loop_body (loop); + exits = get_loop_exit_edges (loop, body); + likely_exit = single_likely_exit (loop, exits); FOR_EACH_VEC_ELT (exits, i, ex) { if (ex == likely_exit) @@ -4296,7 +4299,8 @@ estimate_numbers_of_iterations (class lo } } - if (!number_of_iterations_exit (loop, ex, &niter_desc, false, false)) + if (!number_of_iterations_exit (loop, ex, &niter_desc, + false, false, body)) continue; niter = niter_desc.niter; @@ -4313,7 +4317,7 @@ estimate_numbers_of_iterations (class lo exits.release (); if (flag_aggressive_loop_optimizations) - infer_loop_bounds_from_undefined (loop); + infer_loop_bounds_from_undefined (loop, body); discover_iteration_bound_by_body_walk (loop); Index: gcc/tree-ssa-loop-niter.h =================================================================== --- gcc/tree-ssa-loop-niter.h (revision 278550) +++ gcc/tree-ssa-loop-niter.h (working copy) @@ -22,13 +22,16 @@ along with GCC; see the file COPYING3. extern tree expand_simple_operations (tree, tree = NULL); extern tree simplify_using_initial_conditions (class loop *, tree); -extern bool loop_only_exit_p (const class loop *, const_edge); +extern bool loop_only_exit_p (const class loop *, basic_block *body, + const_edge); extern bool number_of_iterations_exit (class loop *, edge, class tree_niter_desc *niter, bool, - bool every_iteration = true); + bool every_iteration = true, + basic_block * = NULL); extern bool number_of_iterations_exit_assumptions (class loop *, edge, class tree_niter_desc *, - gcond **, bool = true); + gcond **, bool = true, + basic_block * = NULL); extern tree find_loop_niter (class loop *, edge *); extern bool finite_loop_p (class loop *); extern tree loop_niter_by_eval (class loop *, edge);