From patchwork Tue Nov 14 19:08:03 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Aldy Hernandez X-Patchwork-Id: 837998 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-466768-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="EViHs1g2"; 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 3ybxqV6CCnz9ryk for ; Wed, 15 Nov 2017 06:08:22 +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:to :from:subject:cc:message-id:date:mime-version:content-type; q= dns; s=default; b=xwbQkXKS0AI/6MKL18Xsj6FpkdE2GWDcKSRHQt69G3T+fD YBWD1/+5O8fOpCJR9Vb9pRKgNHswudWtAgqjqbLzi2KwBHijXPOMG9A8wmJXV1ws KMUfO7M3LWTshTUvBiuUw/jaNtIlcmR34/7mpnLW0HvwqhVUlfuVowBTMr5Rs= 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:to :from:subject:cc:message-id:date:mime-version:content-type; s= default; bh=2phcxfq5Ja2l0QL8SW9WnkrTO28=; b=EViHs1g2hPZawytdPJM/ kFKDPXQZtZ1/JMff4bUjdstXN8KNCN0bhWLiip7opaKX/mzO+CXFWiCYbZdsrQKR 8wmX9UqtRP1HqmUV8+co/snH2r5K7eBIvwp5riqi8PSqsRJ5wULD+XBmKY0pxhL1 Ph8xCMzaC05X7oukS8xXpR0= Received: (qmail 74849 invoked by alias); 14 Nov 2017 19:08:11 -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 74832 invoked by uid 89); 14 Nov 2017 19:08:10 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-25.5 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, KAM_SHORT, KB_WAM_FROM_NAME_SINGLEWORD, RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.2 spammy=6488, Tracks, howdy X-HELO: mail-wm0-f43.google.com Received: from mail-wm0-f43.google.com (HELO mail-wm0-f43.google.com) (74.125.82.43) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 14 Nov 2017 19:08:08 +0000 Received: by mail-wm0-f43.google.com with SMTP id r68so23559621wmr.1 for ; Tue, 14 Nov 2017 11:08:07 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:to:from:subject:cc:message-id:date:user-agent :mime-version:content-language; bh=BTMPTbU6H6QqoRybFhlMwY/rD7tZe9KENreQ0ovWtTg=; b=ms+nD5EjyycKYNMLtzmYGOKeq6+9DLxv6cguOozE4g2ZII/880sxAItipfxZfoqgVG qWminL/D0tS+vAFAFpdW/r8xv4n8YndoYXXgCnB4+Vqpni1Qrv8Qjh9oeGzQXlsTDsm/ Ye47VG8kqZRA/uciWw6MLP3Of/VFA7gl8WuVuXB4oU49A8aQDDVHfsImQr5DKiXKErmy auZd4iVkvKtVxxc8r73zUz/7jI/nJ9F8p9FEFlK5QAfLqGxI1R/vO8wgrCBMfYWA+40i fTbhsX9OPHIa+EFukC1RI8CpDhgSizkdl4i0SpwwknCxGXR09mBatSag8RbjigpGrh2D BwtQ== X-Gm-Message-State: AJaThX7mDdO8y6CiVG1WFeF01+ZlvViRQ6x9eo8ePfVKEyVeMl/yLQgh zMaq9QrYH6g+UHiZqK88FpcNJutMYFQ= X-Google-Smtp-Source: AGs4zMb1iqGGhjQudwyc5U50wu+87PXiK25aT97RsZRSUZqaFv2qb604qg1YNym8WjhYXm95RBJi9Q== X-Received: by 10.28.239.12 with SMTP id n12mr8743782wmh.140.1510686485769; Tue, 14 Nov 2017 11:08:05 -0800 (PST) Received: from abulafia.quesejoda.com (78.red-88-13-206.dynamicip.rima-tde.net. [88.13.206.78]) by smtp.gmail.com with ESMTPSA id y84sm6510588wmg.39.2017.11.14.11.08.04 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 14 Nov 2017 11:08:04 -0800 (PST) To: Jeff Law , gcc-patches From: Aldy Hernandez Subject: [patch] backwards threader cleanups Cc: Andrew MacLeod Message-ID: <6ab6f238-276e-51d9-91a6-9de999d0daf0@redhat.com> Date: Tue, 14 Nov 2017 14:08:03 -0500 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.4.0 MIME-Version: 1.0 X-IsSubscribed: yes Howdy! For some upcoming work I need some pass local data that I don't want to be passing around as an argument. We have enough of those in the threader as it is. So I moved the current pass local data into its own class, and basically classified the entire pass, thus avoiding a lot of arguments. In doing this, I also noticed that not only was the prototype in the header file wrong, but it wasn't used anywhere. I have removed the useless header. The net result is less lines of code, even without taking into account the deleted header file. Oh yeah, we had no way of clearing a hash set. I've fixed this oversight :). Tested on x86-64 Linux. OK for trunk? gcc/ * hash-set.h (hash_set::empty): New. * tree-ssa-threadbackward.h: Remove. * tree-ssa-threadbackward.c (class thread_jumps): New. Move max_threaded_paths into class. (fsm_find_thread_path): Remove arguments that are now in class. (profitable_jump_thread_path): Rename to... (thread_jumps::profitable_jump_thread_path): ...this. (convert_and_register_jump_thread_path): Rename to... (thread_jumps::convert_and_register_current_path): ...this. (check_subpath_and_update_thread_path): Rename to... (thread_jumps::check_subpath_and_update_thread_path): ...this. (register_jump_thread_path_if_profitable): Rename to... (thread_jumps::register_jump_thread_path_if_profitable): ...this. (handle_phi): Rename to... (thread_jumps::handle_phi): ...this. (handle_assignment): Rename to... (thread_jumps::handle_assignment): ...this. (fsm_find_control_statement_thread_paths): Rename to... (thread_jumps::fsm_find_control_statement_thread_paths): ...this. (find_jump_threads_backwards): Rename to... (thread_jumps::find_jump_threads_backwards): ...this. Initialize path local data. (pass_thread_jumps::execute): Call find_jump_threads_backwards from within thread_jumps class. (pass_early_thread_jumps::execute): Same. diff --git a/gcc/hash-set.h b/gcc/hash-set.h index d2247d39571..8ce796d1c48 100644 --- a/gcc/hash-set.h +++ b/gcc/hash-set.h @@ -80,6 +80,10 @@ public: size_t elements () const { return m_table.elements (); } + /* Clear the hash table. */ + + void empty () { m_table.empty (); } + class iterator { public: diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c index 12bc80350f5..a1454f31bec 100644 --- a/gcc/tree-ssa-threadbackward.c +++ b/gcc/tree-ssa-threadbackward.c @@ -38,7 +38,35 @@ along with GCC; see the file COPYING3. If not see #include "tree-inline.h" #include "tree-vectorizer.h" -static int max_threaded_paths; +class thread_jumps +{ + private: + /* The maximum number of BB we are allowed to thread. */ + int max_threaded_paths; + /* Hash to keep track of seen bbs. */ + hash_set visited_bbs; + /* The current path we're analyzing. */ + auto_vec path; + /* Tracks if we have recursed through a loop PHI node. */ + bool seen_loop_phi; + /* Indicate that we could increase code size to improve the + code path. */ + bool speed_p; + + edge profitable_jump_thread_path (basic_block bbi, tree name, tree arg, + bool *creates_irreducible_loop); + void convert_and_register_current_path (edge taken_edge); + void register_jump_thread_path_if_profitable (tree name, tree arg, + basic_block def_bb); + void handle_assignment (gimple *stmt, tree name, basic_block def_bb); + void handle_phi (gphi *phi, tree name, basic_block def_bb); + void fsm_find_control_statement_thread_paths (tree name); + bool check_subpath_and_update_thread_path (basic_block last_bb, + basic_block new_bb, + int *next_path_length); + public: + void find_jump_threads_backwards (basic_block bb, bool speed_p); +}; /* Simple helper to get the last statement from BB, which is assumed to be a control statement. Return NULL if the last statement is @@ -61,14 +89,15 @@ get_gimple_control_stmt (basic_block bb) /* Return true if the CFG contains at least one path from START_BB to END_BB. When a path is found, record in PATH the blocks from - END_BB to START_BB. VISITED_BBS is used to make sure we don't fall - into an infinite loop. Bound the recursion to basic blocks - belonging to LOOP. */ + END_BB to START_BB. LOCAL_VISITED_BBS is used to make sure we + don't fall into an infinite loop. Bound the recursion to basic + blocks belonging to LOOP. */ static bool fsm_find_thread_path (basic_block start_bb, basic_block end_bb, vec &path, - hash_set &visited_bbs, loop_p loop) + hash_set &local_visited_bbs, + loop_p loop) { if (loop != start_bb->loop_father) return false; @@ -79,12 +108,13 @@ fsm_find_thread_path (basic_block start_bb, basic_block end_bb, return true; } - if (!visited_bbs.add (start_bb)) + if (!local_visited_bbs.add (start_bb)) { edge e; edge_iterator ei; FOR_EACH_EDGE (e, ei, start_bb->succs) - if (fsm_find_thread_path (e->dest, end_bb, path, visited_bbs, loop)) + if (fsm_find_thread_path (e->dest, end_bb, path, local_visited_bbs, + loop)) { path.safe_push (start_bb); return true; @@ -102,16 +132,14 @@ fsm_find_thread_path (basic_block start_bb, basic_block end_bb, NAME is the SSA_NAME of the variable we found to have a constant value on PATH. ARG is the constant value of NAME on that path. - BBI will be appended to PATH when we have a profitable jump threading - path. Callers are responsible for removing BBI from PATH in that case. - - SPEED_P indicate that we could increase code size to improve the - code path. */ + BBI will be appended to PATH when we have a profitable jump + threading path. Callers are responsible for removing BBI from PATH + in that case. */ -static edge -profitable_jump_thread_path (vec &path, - basic_block bbi, tree name, tree arg, - bool speed_p, bool *creates_irreducible_loop) +edge +thread_jumps::profitable_jump_thread_path (basic_block bbi, tree name, + tree arg, + bool *creates_irreducible_loop) { /* Note BBI is not in the path yet, hence the +1 in the test below to make sure BBI is accounted for in the path length test. */ @@ -412,14 +440,14 @@ profitable_jump_thread_path (vec &path, return taken_edge; } -/* PATH is vector of blocks forming a jump threading path in reverse - order. TAKEN_EDGE is the edge taken from path[0]. +/* The current path PATH is a vector of blocks forming a jump threading + path in reverse order. TAKEN_EDGE is the edge taken from path[0]. - Convert that path into the form used by register_jump_thread and - register the path. */ + Convert the current path into the form used by register_jump_thread and + register it. */ -static void -convert_and_register_jump_thread_path (vec &path, edge taken_edge) +void +thread_jumps::convert_and_register_current_path (edge taken_edge) { vec *jump_thread_path = new vec (); @@ -455,11 +483,10 @@ convert_and_register_jump_thread_path (vec &path, edge taken_edge) Store the length of the subpath in NEXT_PATH_LENGTH. */ -static bool -check_subpath_and_update_thread_path (basic_block last_bb, basic_block new_bb, - hash_set &visited_bbs, - vec &path, - int *next_path_length) +bool +thread_jumps::check_subpath_and_update_thread_path (basic_block last_bb, + basic_block new_bb, + int *next_path_length) { edge e; int e_count = 0; @@ -468,10 +495,10 @@ check_subpath_and_update_thread_path (basic_block last_bb, basic_block new_bb, FOR_EACH_EDGE (e, ei, last_bb->preds) { - hash_set visited_bbs; + hash_set local_visited_bbs; - if (fsm_find_thread_path (new_bb, e->src, next_path, visited_bbs, - e->src->loop_father)) + if (fsm_find_thread_path (new_bb, e->src, next_path, + local_visited_bbs, e->src->loop_father)) ++e_count; /* If there is more than one path, stop. */ @@ -507,28 +534,21 @@ check_subpath_and_update_thread_path (basic_block last_bb, basic_block new_bb, NAME is an SSA NAME with a possible constant value of ARG on PATH. - DEF_BB is the basic block that ultimately defines the constant. + DEF_BB is the basic block that ultimately defines the constant. */ - SPEED_P indicate that we could increase code size to improve the - code path. -*/ - -static void -register_jump_thread_path_if_profitable (vec &path, - tree name, - tree arg, - basic_block def_bb, - bool speed_p) +void +thread_jumps::register_jump_thread_path_if_profitable (tree name, tree arg, + basic_block def_bb) { if (TREE_CODE_CLASS (TREE_CODE (arg)) != tcc_constant) return; bool irreducible = false; - edge taken_edge = profitable_jump_thread_path (path, def_bb, name, arg, - speed_p, &irreducible); + edge taken_edge = profitable_jump_thread_path (def_bb, name, arg, + &irreducible); if (taken_edge) { - convert_and_register_jump_thread_path (path, taken_edge); + convert_and_register_current_path (taken_edge); path.pop (); if (irreducible) @@ -536,29 +556,15 @@ register_jump_thread_path_if_profitable (vec &path, } } -static void fsm_find_control_statement_thread_paths (tree, - hash_set &, - vec &, - bool, bool); - /* Given PHI which defines NAME in block DEF_BB, recurse through the PHI's arguments searching for paths where NAME will ultimately have a constant value. - VISITED_BBS tracks the blocks that have been encountered. - PATH contains the series of blocks to traverse that will result in - NAME having a constant value. - - SEEN_LOOP_PHI tracks if we have recursed through a loop PHI node. - - SPEED_P indicates if we are optimizing for speed over space. */ + NAME having a constant value. */ -static void -handle_phi (gphi *phi, tree name, basic_block def_bb, - hash_set &visited_bbs, - vec &path, - bool seen_loop_phi, bool speed_p) +void +thread_jumps::handle_phi (gphi *phi, tree name, basic_block def_bb) { /* Iterate over the arguments of PHI. */ for (unsigned int i = 0; i < gimple_phi_num_args (phi); i++) @@ -575,14 +581,13 @@ handle_phi (gphi *phi, tree name, basic_block def_bb, path.safe_push (bbi); /* Recursively follow SSA_NAMEs looking for a constant definition. */ - fsm_find_control_statement_thread_paths (arg, visited_bbs, path, - seen_loop_phi, speed_p); + fsm_find_control_statement_thread_paths (arg); path.pop (); continue; } - register_jump_thread_path_if_profitable (path, name, arg, bbi, speed_p); + register_jump_thread_path_if_profitable (name, arg, bbi); } } @@ -620,26 +625,16 @@ handle_assignment_p (gimple *stmt) PHI's arguments searching for paths where NAME will ultimately have a constant value. - VISITED_BBS tracks the blocks that have been encountered. - PATH contains the series of blocks to traverse that will result in - NAME having a constant value. - - SEEN_LOOP_PHI tracks if we have recursed through a loop PHI node. + NAME having a constant value. */ - SPEED_P indicates if we are optimizing for speed over space. */ - -static void -handle_assignment (gimple *stmt, tree name, basic_block def_bb, - hash_set &visited_bbs, - vec &path, - bool seen_loop_phi, bool speed_p) +void +thread_jumps::handle_assignment (gimple *stmt, tree name, basic_block def_bb) { tree arg = gimple_assign_rhs1 (stmt); if (TREE_CODE (arg) == SSA_NAME) - fsm_find_control_statement_thread_paths (arg, visited_bbs, - path, seen_loop_phi, speed_p); + fsm_find_control_statement_thread_paths (arg); else { @@ -648,8 +643,7 @@ handle_assignment (gimple *stmt, tree name, basic_block def_bb, block at this point. So we can just pop it. */ path.pop (); - register_jump_thread_path_if_profitable (path, name, arg, def_bb, - speed_p); + register_jump_thread_path_if_profitable (name, arg, def_bb); /* And put the current block back onto the path so that the state of the stack is unchanged when we leave. */ @@ -659,16 +653,10 @@ handle_assignment (gimple *stmt, tree name, basic_block def_bb, /* We trace the value of the SSA_NAME NAME back through any phi nodes looking for places where it gets a constant value and save the - path. + path. */ - SPEED_P indicate that we could increase code size to improve the - code path. */ - -static void -fsm_find_control_statement_thread_paths (tree name, - hash_set &visited_bbs, - vec &path, - bool seen_loop_phi, bool speed_p) +void +thread_jumps::fsm_find_control_statement_thread_paths (tree name) { /* If NAME appears in an abnormal PHI, then don't try to trace its value back through PHI nodes. */ @@ -722,7 +710,6 @@ fsm_find_control_statement_thread_paths (tree name, create bogus jump threading paths. */ visited_bbs.add (path[0]); if (!check_subpath_and_update_thread_path (last_bb_in_path, def_bb, - visited_bbs, path, &next_path_length)) return; } @@ -730,11 +717,9 @@ fsm_find_control_statement_thread_paths (tree name, gcc_assert (path.last () == def_bb); if (gimple_code (def_stmt) == GIMPLE_PHI) - handle_phi (as_a (def_stmt), name, def_bb, - visited_bbs, path, seen_loop_phi, speed_p); + handle_phi (as_a (def_stmt), name, def_bb); else if (gimple_code (def_stmt) == GIMPLE_ASSIGN) - handle_assignment (def_stmt, name, def_bb, - visited_bbs, path, seen_loop_phi, speed_p); + handle_assignment (def_stmt, name, def_bb); /* Remove all the nodes that we added from NEXT_PATH. */ if (next_path_length) @@ -749,8 +734,8 @@ fsm_find_control_statement_thread_paths (tree name, SPEED_P indicate that we could increase code size to improve the code path. */ -void -find_jump_threads_backwards (basic_block bb, bool speed_p) +void +thread_jumps::find_jump_threads_backwards (basic_block bb, bool speed_p) { gimple *stmt = get_gimple_control_stmt (bb); if (!stmt) @@ -774,13 +759,15 @@ find_jump_threads_backwards (basic_block bb, bool speed_p) if (!name || TREE_CODE (name) != SSA_NAME) return; - auto_vec bb_path; - bb_path.safe_push (bb); - hash_set visited_bbs; + /* Initialize the pass local data that changes at each iteration. */ + path.truncate (0); + path.safe_push (bb); + visited_bbs.empty (); + seen_loop_phi = false; + this->speed_p = speed_p; max_threaded_paths = PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATHS); - fsm_find_control_statement_thread_paths (name, visited_bbs, bb_path, false, - speed_p); + fsm_find_control_statement_thread_paths (name); } namespace { @@ -823,11 +810,12 @@ pass_thread_jumps::execute (function *fun) loop_optimizer_init (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES); /* Try to thread each block with more than one successor. */ + thread_jumps pass; basic_block bb; FOR_EACH_BB_FN (bb, fun) { if (EDGE_COUNT (bb->succs) > 1) - find_jump_threads_backwards (bb, true); + pass.find_jump_threads_backwards (bb, true); } bool changed = thread_through_all_blocks (true); @@ -883,11 +871,12 @@ pass_early_thread_jumps::execute (function *fun) loop_optimizer_init (AVOID_CFG_MODIFICATIONS); /* Try to thread each block with more than one successor. */ + thread_jumps pass; basic_block bb; FOR_EACH_BB_FN (bb, fun) { if (EDGE_COUNT (bb->succs) > 1) - find_jump_threads_backwards (bb, false); + pass.find_jump_threads_backwards (bb, false); } thread_through_all_blocks (true); diff --git a/gcc/tree-ssa-threadbackward.h b/gcc/tree-ssa-threadbackward.h deleted file mode 100644 index f758ff1f1ad..00000000000 --- a/gcc/tree-ssa-threadbackward.h +++ /dev/null @@ -1,25 +0,0 @@ -/* Header file for SSA dominator optimizations. - Copyright (C) 2013-2017 Free Software Foundation, Inc. - -This file is part of GCC. - -GCC is free software; you can redistribute it and/or modify it under -the terms of the GNU General Public License as published by the Free -Software Foundation; either version 3, or (at your option) any later -version. - -GCC is distributed in the hope that it will be useful, but WITHOUT ANY -WARRANTY; without even the implied warranty of MERCHANTABILITY or -FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - for more details. - -You should have received a copy of the GNU General Public License -along with GCC; see the file COPYING3. If not see -. */ - -#ifndef GCC_TREE_SSA_THREADFSM_H -#define GCC_TREE_SSA_THREADFSM_H - -extern void find_jump_threads_backwards (edge); - -#endif /* GCC_TREE_SSA_THREADFSM_H */