From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lf1-x135.google.com (mail-lf1-x135.google.com [IPv6:2a00:1450:4864:20::135]) by sourceware.org (Postfix) with ESMTPS id 79A4B3858D20 for ; Fri, 14 Apr 2023 11:56:41 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 79A4B3858D20 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com Received: by mail-lf1-x135.google.com with SMTP id u12so5325185lfu.5 for ; Fri, 14 Apr 2023 04:56:41 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1681473400; x=1684065400; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:from:to:cc:subject:date :message-id:reply-to; bh=5p9TnSQXqk3X315liPd5Cs4XLFTR9o127oPK9P2gaUk=; b=aspDyrosxjkn7FcGw3qyRMUbEOBhGRnJpvTkz0L4DWvEfWJLYgxk08sw/Nk7P0o0V6 XVDaFAl31p9hxcHjlQXOzfL0jOEljJBcTPrce3PD3Nu0GDSjR31dixRHTeUES+33JwpU AOqv3P1WfcFYypnKtpOZOXT13D9GVHxlFxAHRZk6Hhk2gJ2EcEPVa3fvu9685ErASub+ ckKAO/KGD3NLyuB5fEltsUcpvFUolJyVHgx0oIFi9ALAfwlOu+GzrJ1+xNwAjUGQCFPk 24PiiPBOg+Qgw1Oo6orO1e2lIG9XD4cv2GziBudNNUkv67vwqRllR8KwPh+81aVZYHnk JkUg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1681473400; x=1684065400; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=5p9TnSQXqk3X315liPd5Cs4XLFTR9o127oPK9P2gaUk=; b=hKjGk0V4+wJqSoxWeMMeCVv4HP4GEMYQeL4DLOCdwKd/SjPyvRwP5e3O7clsWRR9wk slqQxAm2sIHF130T4DIjT47inj6ku4bL+OYx6uLxf8UFuC3v4x8OKVSN+DazfX6UWJSI OVBKo73Mr0+yVLA9wbDd14OHAOiG/dsJbBbIg7tMCtGTzDxuluvy1xkvWhNXZhEGEy4q PZ3ThkBvnz1zB0TQ8kXo5K8fdahZJvMgU0GUsy4WHOIAEnrjQUWAt5cv8e9zTF6wmPX1 HSA/cumOH0Xc20cfJRv/FgBqROLdSPlVJVJN8ocSkpj4xvERN7p7YWTEt/jwAGyW+Udx DUfg== X-Gm-Message-State: AAQBX9d3NQzgznGJGRI2IfU/DG4CtiLKbIBHmuNIN2VPZ3i2D5dk2Eqn 9Zi1oNFvFFZ8wAX37+3A0jpHHyRWJVb91qWM98w= X-Google-Smtp-Source: AKy350ZP5E7Sgq7DaWwcnopV/NTMRycF/sgYcfkj0bbOeJI2ZgDAxjW803J0JKlvHKayG3SVWHyNz0+pEqqdJOw7MFc= X-Received: by 2002:ac2:52b3:0:b0:4e0:822f:9500 with SMTP id r19-20020ac252b3000000b004e0822f9500mr1794217lfm.12.1681473399699; Fri, 14 Apr 2023 04:56:39 -0700 (PDT) MIME-Version: 1.0 References: <1d4c9e6c-85e4-7eff-0833-aca7f874fbda@linux.ibm.com> <575418e4-7d40-3d56-044b-fdd91a7c657a@linux.ibm.com> In-Reply-To: <575418e4-7d40-3d56-044b-fdd91a7c657a@linux.ibm.com> From: Richard Biener Date: Fri, 14 Apr 2023 13:56:27 +0200 Message-ID: Subject: Re: PATCH] tree-ssa-sink: Add heuristics for code sinking To: Ajit Agarwal Cc: gcc-patches , Segher Boessenkool , Peter Bergner , Jeff Law Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-7.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,FREEMAIL_FROM,GIT_PATCH_0,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS,TXREP,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: On Fri, Apr 14, 2023 at 12:08=E2=80=AFPM Ajit Agarwal wrote: > > Hello Richard: > > On 14/04/23 2:29 pm, Richard Biener wrote: > > On Fri, Apr 14, 2023 at 10:42=E2=80=AFAM Ajit Agarwal via Gcc-patches > > wrote: > >> > >> Hello All: > >> > >> This patch add heuristics for code sinking opportunities. > >> Bootstrapped and regtested for powerpc64-linux-gnu. > >> > >> Thanks & Regards > >> Ajit > >> > >> tree-ssa-sink: Add heuristics for code sinking. > >> > >> Add following code sinking heuristics: > >> > >> 1. from code block dominates the call. > >> 2. To Code block have uses inside the function call. > >> 3. Loop headers. > >> 4. Sinking from code block after call increases register > >> pressure. > >> 5. Sinking calls. > >> > >> 2023-04-14 Ajit Kumar Agarwal > >> > >> gcc/ChangeLog: > >> > >> * tree-ssa-sink.cc (statement_sink_location): Add heuristics > >> for code sinking. > >> --- > >> gcc/tree-ssa-sink.cc | 33 +++++++++++++++++++++++++++++++++ > >> 1 file changed, 33 insertions(+) > >> > >> diff --git a/gcc/tree-ssa-sink.cc b/gcc/tree-ssa-sink.cc > >> index 87b1d40c174..8de88b259a3 100644 > >> --- a/gcc/tree-ssa-sink.cc > >> +++ b/gcc/tree-ssa-sink.cc > >> @@ -465,6 +465,39 @@ statement_sink_location (gimple *stmt, basic_bloc= k frombb, > >> if (sinkbb =3D=3D frombb) > >> return false; > >> > >> + auto_vec h; > >> + h =3D get_all_dominated_blocks (CDI_DOMINATORS, > >> + frombb); > >> + bool is_call =3D false; > >> + while (h.length ()) > >> + { > >> + basic_block bb =3D h.pop (); > >> + > >> + if (bb =3D=3D frombb) > >> + continue; > >> + > >> + for (gimple_stmt_iterator gsi =3D gsi_last_bb (bb); !gsi= _end_p (gsi);) > >> + { > >> + gimple *stmt =3D gsi_stmt (gsi); > >> + > >> + if (is_gimple_call (stmt)) > >> + { > >> + is_call =3D true; > >> + break; > >> + } > >> + > >> + if (!gsi_end_p (gsi)) > >> + gsi_prev (&gsi); > >> + } > >> + } > >> + > >> + if (!is_gimple_call (stmt) > >> + && (gimple_bb (use) !=3D frombb) > >> + && !is_gimple_call (use) > >> + && dominated_by_p (CDI_DOMINATORS, sinkbb, frombb) > >> + && is_call) > >> + return false; > >> + > > > > Sorry, but this lacks a comment, it doesn't explain why the existing he= uristics > > are not enough (select_best_block), it repeats dominance computing. > > > > More so it lacks a testcase demonstrating the effect. > > > > Added testscases and comments in the code. > The heuristics are added to relieve from register pressure. > > Thanks & Regards > Ajit > > Here is the patch. > > tree-ssa-sink: Add heuristics for code sinking. > > Add following code sinking heuristics: > > 1. from code block dominates the call. > 2. To Code block have uses inside the function call. > 3. Loop headers. > 4. Sinking from code block after call increases register > pressure. > 5. Sinking calls. > > 2023-04-14 Ajit Kumar Agarwal > > gcc/ChangeLog: > > * tree-ssa-sink.cc (statement_sink_location): Add heuristics > for code sinking. > > gcc/testsuite/ChangeLog: > > * gcc.dg/tree-ssa/ssa-sink-20.c: New testcase. > * gcc.dg/tree-ssa/ssa-sink-21.c: New testcase. > --- > gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c | 16 ++++++++++++++++ > gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c | 20 ++++++++++++++++++++ > gcc/tree-ssa-sink.cc | 6 ++++++ > 3 files changed, 42 insertions(+) > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c > > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c b/gcc/testsuite/= gcc.dg/tree-ssa/ssa-sink-20.c > new file mode 100644 > index 00000000000..ed2aefc01aa > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c > @@ -0,0 +1,16 @@ > +/* { dg-do compile } */ > +/* { dg-options "-O2 -fdump-tree-sink -fdump-tree-optimized" } */ > + > +void bar(); > +int j; > +void foo(int a, int b, int c, int d, int e, int f) > +{ > + int l; > + l =3D a + b + c + d +e + f; > + if (a !=3D 5) > + { why should we not sink the computes inside if (a !=3D 5)? > + bar(); you probably want to avoid sinking after the call but since this is all in a single BB, GIMPLE doesn't really define a schedule of stmts here and so passes like sinking shouldn't really bother to look. > + j =3D l; > + } > +} > +/* { dg-final { scan-tree-dump-times "Sunk statements: 1" 0 "sink1" } } = */ Btw, you probably want to check "Sunk statements: 0" 1 "sink1" instead. Otherwise sinking two stmts would be OK? > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c b/gcc/testsuite/= gcc.dg/tree-ssa/ssa-sink-21.c > new file mode 100644 > index 00000000000..a39724df8ec > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c > @@ -0,0 +1,20 @@ > +/* { dg-do compile } */ > +/* { dg-options "-O2 -fdump-tree-sink-stats" } */ > + > +void bar(); > +int j, x; > +void foo(int a, int b, int c, int d, int e, int f) > +{ > + int l; > + l =3D a + b + c + d +e + f; > + if (a !=3D 5) > + { same here > + bar(); > + if (b !=3D 3) > + x =3D 3; > + else > + x =3D 5; > + j =3D l; > + } > +} > +/* { dg-final { scan-tree-dump-times "Sunk statements: 1" 0 "sink1" } } = */ > diff --git a/gcc/tree-ssa-sink.cc b/gcc/tree-ssa-sink.cc > index 8de88b259a3..932fd71bec2 100644 > --- a/gcc/tree-ssa-sink.cc > +++ b/gcc/tree-ssa-sink.cc > @@ -465,6 +465,12 @@ statement_sink_location (gimple *stmt, basic_block f= rombb, > if (sinkbb =3D=3D frombb) > return false; > > + /* The below heuristics describes the following. > + a) If the candidate to sink has call in the dominator basic > + basic blocks. > + b) statement to sink doesn't have use in the call. > + c) candidate block dominates sink block. > + In the above cases are true then don't do code sinking. */ but then the existing heuristic would try to find a better block. Consider +void bar(); +int j, x; +void foo(int a, int b, int c, int d, int e, int f) +{ + int l; + l =3D a + b + c + d +e + f; + if (a !=3D 5) + { + if (b !=3D 3) + x =3D 3; + else + x =3D 5; + bar(); + j =3D l; + } +} we do not want to completely disable sinking but might want to sink before bar() instead of not at all if the position after bar() we'd otherwi= se sink to is executed with the same conditions than the position before bar (= ). So I don't think the implementation is good at all - it wires things in the wrong place. Richard. > auto_vec h; > h =3D get_all_dominated_blocks (CDI_DOMINATORS, > frombb); > -- > 2.31.1 > > > > Richard. > > > >> if (sinkbb =3D=3D gimple_bb (use)) > >> *togsi =3D gsi_for_stmt (use); > >> else > >> -- > >> 2.31.1 > >>