From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 91070 invoked by alias); 1 Apr 2016 19:25:09 -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 91029 invoked by uid 89); 1 Apr 2016 19:25:08 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.6 required=5.0 tests=BAYES_00,RCVD_IN_DNSWL_LOW autolearn=ham version=3.3.2 spammy=thousands X-HELO: mail-ob0-f182.google.com Received: from mail-ob0-f182.google.com (HELO mail-ob0-f182.google.com) (209.85.214.182) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-GCM-SHA256 encrypted) ESMTPS; Fri, 01 Apr 2016 19:24:53 +0000 Received: by mail-ob0-f182.google.com with SMTP id kf9so129084669obc.1 for ; Fri, 01 Apr 2016 12:24:53 -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=OJRbKYHw8PwuWpQMlCB+uzNqO7EvDAWPMUOltTaFTwo=; b=g0HRfntK2zdpxw6DEqesfkPZybjtmItxSJ2Wb66yHOdWzXQXK8N8tQFc60FFpSvqrg mf0CDc5Ni02aow6GuwZLNWRHTIsJ+iCAeSg0tIJi89L4GN6irE0RGabixU99aZqNu0qE hCTzxNaeAJrUPK8gNfnYh87iBv2cgejf8Fpv8NHwNlDTZxViHhKKsI3pDfFLucxFHuya raUhAr/MrVnvJH09WEqMyNzMiXW2mXAOqqVFMy8gOdwfnwayO7GVHI8BTVQUDrGtxHYE WaYJkKEODQHY+iS7tbk+fUbbj4PsSzPJGY/Ure+IWPJVTwMdp7oAPvxZ054PqLTp5JCw BlBg== X-Gm-Message-State: AD7BkJIW3wBkbNqM14uBVT2pefr1cuNzD2yY1sA4fpGh10A+I3Tat0gfl7IVnihpRJquGyAjf7kWdTrYAWzj3A== X-Received: by 10.182.79.167 with SMTP id k7mr4176851obx.43.1459538691836; Fri, 01 Apr 2016 12:24:51 -0700 (PDT) MIME-Version: 1.0 Received: by 10.182.102.105 with HTTP; Fri, 1 Apr 2016 12:24:32 -0700 (PDT) In-Reply-To: <1459538004-13812-1-git-send-email-patrick@parcs.ath.cx> References: <1459538004-13812-1-git-send-email-patrick@parcs.ath.cx> From: Patrick Palka Date: Fri, 01 Apr 2016 19:25:00 -0000 Message-ID: Subject: Re: [PATCH] Fix PR c++/70452 (regression in C++ parsing performance) To: GCC Patches Cc: Jason Merrill , Patrick Palka Content-Type: text/plain; charset=UTF-8 X-SW-Source: 2016-04/txt/msg00088.txt.bz2 On Fri, Apr 1, 2016 at 3:13 PM, Patrick Palka wrote: > Currently during constexpr CALL_EXPR evaluation we create a new copy of > the callee function's body for each separate call with no attempt made > at reusing the function body. So when a function ends up getting called > 10s of thousands of times durnig constexpr evaluuation, we end up > creating 10s of thousands of copies of the function. > > This patch is an attempt at reusing these copies instead of having a new > copy get created each call. It implements a per-function freelist of > the unshared body/parm/res copies that were created by copy_fn(). When > a constexpr call is finished it pushes the body/parm/res trees to the > freelist, and before a call is evaluated it tries to reuse the trees > from the freelist, falling back to copy_fn() only if the freelist is > empty. > > Consequently, instead of creating 10s of thousands of copies for 10s of > thousands of calls, the number of copies that're made corresponds to the > recursion depth of the function. This makes sense because the reason we > create copies in the first place (IIUC) is to ensure that recursive > calls to a function do not share the same > PARM_DECLs/VAR_DECLs/RESULT_DECLs. > > In order for this reuse to work properly in the presence of SAVE_EXPRs, > we have to track each SAVE_EXPR (belonging to the callee) that we > evaluate during the call and then forget its value after the call. > constexpr-vla4.C is a new test that would fail if this patch had missed > this SAVE_EXPR part. > > With this patch, the compile time of the test case in the PR gets cut > from 3.5s to 2s and memory usage gets cut from 550M to 200M. > > I bootstrapped + regtested this change on x86_64-pc-linux-gnu, and also > compile-tested it against boost with no regressions. > > gcc/cp/ChangeLog: > > PR c++/70452 > * constexpr.c (struct bpr_entry): New struct. > (struct constexpr_fundef): New field bpr_freelist. > (retrieve_constexpr_fundef): Initialize field bpr_freelist to > NULL. > (register_constexpr_fundef): Likewise. > (cxx_eval_call_expression): Check constexpr_fundef::bpr_freelist > for a reusable copy of the function's body before creating a new > copy. Keep track of the callee's SAVE_EXPRs that we evaluate > and forget their values afterwards. Push the function body we > used onto the freelist for later reuse. > > gcc/testsuite/ChangeLog: > > PR c++/70452 > * g++.dg/ext/constexpr-vla4.C: New test. > --- > gcc/cp/constexpr.c | 55 ++++++++++++++++++++++++++++--- > gcc/testsuite/g++.dg/ext/constexpr-vla4.C | 17 ++++++++++ > 2 files changed, 67 insertions(+), 5 deletions(-) > create mode 100644 gcc/testsuite/g++.dg/ext/constexpr-vla4.C > > diff --git a/gcc/cp/constexpr.c b/gcc/cp/constexpr.c > index ea605dc..fc9b67c 100644 > --- a/gcc/cp/constexpr.c > +++ b/gcc/cp/constexpr.c > @@ -112,11 +112,24 @@ ensure_literal_type_for_constexpr_object (tree decl) > return decl; > } > > +/* The representation of a single node in the constexpr_fundef::bpr_freelist chain. */ > + > +struct GTY((chain_next ("%h.prev"))) bpr_entry > +{ > + tree body; > + tree parms; > + tree res; > + struct bpr_entry *prev; > +}; > + > /* Representation of entries in the constexpr function definition table. */ > > struct GTY((for_user)) constexpr_fundef { > tree decl; > tree body; > + /* A chain of unused copies of this function's body awaiting reuse for > + CALL_EXPR evaluation. */ > + struct bpr_entry *bpr_freelist; > }; > > struct constexpr_fundef_hasher : ggc_ptr_hash > @@ -154,7 +167,7 @@ constexpr_fundef_hasher::hash (constexpr_fundef *fundef) > static constexpr_fundef * > retrieve_constexpr_fundef (tree fun) > { > - constexpr_fundef fundef = { NULL, NULL }; > + constexpr_fundef fundef = { NULL, NULL, NULL }; > if (constexpr_fundef_table == NULL) > return NULL; > > @@ -806,6 +819,7 @@ register_constexpr_fundef (tree fun, tree body) > > entry.decl = fun; > entry.body = body; > + entry.bpr_freelist = NULL; > slot = constexpr_fundef_table->find_slot (&entry, INSERT); > > gcc_assert (*slot == NULL); > @@ -1377,10 +1391,21 @@ cxx_eval_call_expression (const constexpr_ctx *ctx, tree t, > if (!result || result == error_mark_node) > { > gcc_assert (DECL_SAVED_TREE (fun)); > - tree parms, res; > + tree body, parms, res; > > - /* Unshare the whole function body. */ > - tree body = copy_fn (fun, parms, res); > + /* Reuse or create a new unshared copy of this function's body. */ > + if (bpr_entry *bpr = new_call.fundef->bpr_freelist) > + { > + body = bpr->body; > + parms = bpr->parms; > + res = bpr->res; > + new_call.fundef->bpr_freelist = bpr->prev; > + } > + else > + { > + /* Unshare the whole function body. */ > + body = copy_fn (fun, parms, res); > + } > > /* Associate the bindings with the remapped parms. */ > tree bound = new_call.bindings; > @@ -1409,11 +1434,22 @@ cxx_eval_call_expression (const constexpr_ctx *ctx, tree t, > else > ctx->values->put (res, NULL_TREE); > > + /* Track the SAVE_EXPRs of the callee that we evaluate so that > + we can later forget their values. */ > + constexpr_ctx ctx_with_save_exprs = *ctx; > + hash_set save_exprs; > + ctx_with_save_exprs.save_exprs = &save_exprs; Didn't like the way this comment is worded so I changed it to + /* Track the callee's evaluated SAVE_EXPRs so that we can forget + their values after the call. */