From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pl1-x635.google.com (mail-pl1-x635.google.com [IPv6:2607:f8b0:4864:20::635]) by sourceware.org (Postfix) with ESMTPS id 66AE33858409 for ; Mon, 15 Jan 2024 12:56:50 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 66AE33858409 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=linaro.org Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=linaro.org ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 66AE33858409 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2607:f8b0:4864:20::635 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1705323413; cv=none; b=md0Pz7j8Dty5sb0Vlq7SaMi2btt5tHWPRcRAsMJZXisIAZMES8SQgnA7ROJayp8tF1ZhDLqqhvXn/L4EqPuGionffnbVBP7wlTGQ+So4kXT7Yz+2KIJnRtgqEvWzNeuDDf3RdfhqpUs/eNn3z9D72y2ootj6d9SPzCbUiyw3kRc= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1705323413; c=relaxed/simple; bh=yOm1mREAk7T+TQoXjSPjfHM5OxBjANumkD5LPtyGM5k=; h=DKIM-Signature:MIME-Version:From:Date:Message-ID:Subject:To; b=THITsUzyVXLG3XDdE3Wo/Ij7b428BqvFdBEr4IlZBfqUtGx9n04ONrzjqMXHHsaIes1TABsHr2XAfRAqzhPZ1hSzyCxLOErQVD78YXEcSuawvUcdrwUmAWC3cslsqGeCrAOjwDfVxtA95O0EbKE068x6ya5idHq61oM7RK1BUzE= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-pl1-x635.google.com with SMTP id d9443c01a7336-1d437a2a4c7so15810225ad.0 for ; Mon, 15 Jan 2024 04:56:50 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; t=1705323408; x=1705928208; darn=gcc.gnu.org; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=wiQ4uHN1JZcuDKUYO9xBTl5ERQLoO6sftDNwKp+whwo=; b=gHK468RU1/1JzyljcRtdOX74WrcJkBd6sWAO6WAa+SMEw+OaIJN4kzO3w7RZ3Bf3JM eWVmQD0FTtcA0bss29L/n1wr1pY5Wy/w3Qn/ycSNLkikrl96MEptrP2N641fGJ0EwDPS XKyYzWKDcumv2tYgo3KXt4LvikpprSd9JYPhgTdemQAZfDX0jZrsb1eRYi/97QjXcnjG muYqzat/LTVQLuDOjCxotzEpq8aE8kO9qiV6L1JNgG0xwPiGL6RsgAv0a//D/tGcdTYH 7ynnTQsXaEDsp6Kp1t6N/E49qFiLRn2muBOBC5kCkI5JREat5zT5OP43n1FdG0BVVD4g fA3w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1705323408; x=1705928208; h=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=wiQ4uHN1JZcuDKUYO9xBTl5ERQLoO6sftDNwKp+whwo=; b=jPN43ruPrtyagpHDa5g10jXY2HRDuUFb4uwwyDI7G7WqPYkaOLIFlWDrXdEPeX55B4 cwCymdSCrYZ8pi8KDFSQvbE2iHGQt5jPJ0KD32fS1DxrUGc2CrdAI6NTz7qNhHuR0cmy kI7dWUJCCYghQ/1I2DSeglw/98pqGR+6fsLMmM2qbtFkbHurpmULjRA3Gy1Jz3iPKtGG YC/oeqhk2sSedsUWL66/BEYRPRg/FFqOPaLXU4meXyDUKYdLf1VU75QBJKbijIGrvzhm d3r73B6OJnmdf3vR7/bmbppkkj1WK26GrStwr6f5SJy5iDwmMPvfxfO7GyC0pfymtW8P +gIA== X-Gm-Message-State: AOJu0Yyw8E5n9vN6kOBoTyFcL2Na0UmCj7tvn0AvQ9ZDqAChefMx8MD6 5tT4rqDhRqvx/tiuKayr0vSH7cSBQ8sfIn6eIMNeAoiFdLu62V1hKVo6XyI= X-Google-Smtp-Source: AGHT+IE8gS9ctdfqM/3XspnKR4OV7VGElWsL09GoYbVGjqMZOl8qTYvjmxTJzCpCh8/vaUghudrDkrIW4jKnJU4mRUQ= X-Received: by 2002:a17:90b:4f92:b0:28e:193c:e404 with SMTP id qe18-20020a17090b4f9200b0028e193ce404mr8292658pjb.3.1705323407908; Mon, 15 Jan 2024 04:56:47 -0800 (PST) MIME-Version: 1.0 References: <20231120120649.672893-1-maxim.kuvyrkov@linaro.org> <20231122111415.815147-2-maxim.kuvyrkov@linaro.org> In-Reply-To: <20231122111415.815147-2-maxim.kuvyrkov@linaro.org> From: Maxim Kuvyrkov Date: Mon, 15 Jan 2024 16:56:35 +0400 Message-ID: Subject: Re: [PATCH v3 1/8] sched-deps.cc (find_modifiable_mems): Avoid exponential behavior To: gcc-patches@gcc.gnu.org Cc: Bernd Schmidt , Vladimir Makarov , Jeff Law , Alexander Monakov , Richard Guenther Content-Type: multipart/alternative; boundary="000000000000f4b502060efb8b6d" X-Spam-Status: No, score=-9.4 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,GIT_PATCH_0,HTML_MESSAGE,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: --000000000000f4b502060efb8b6d Content-Type: text/plain; charset="UTF-8" Hi Vladimir, Hi Jeff, Richard and Alexander have reviewed this patch and [I assume] have no further comments. OK to merge? On Wed, 22 Nov 2023 at 15:14, Maxim Kuvyrkov wrote: > This patch avoids sched-deps.cc:find_inc() creating exponential number > of dependencies, which become memory and compilation time hogs. > Consider example (simplified from PR96388) ... > === > sp=sp-4 // sp_insnA > mem_insnA1[sp+A1] > ... > mem_insnAN[sp+AN] > sp=sp-4 // sp_insnB > mem_insnB1[sp+B1] > ... > mem_insnBM[sp+BM] > === > > [For simplicity, let's assume find_inc(backwards==true)]. > In this example find_modifiable_mems() will arrange for mem_insnA* > to be able to pass sp_insnA, and, while doing this, will create > dependencies between all mem_insnA*s and sp_insnB -- because sp_insnB > is a consumer of sp_insnA. After this sp_insnB will have N new > backward dependencies. > Then find_modifiable_mems() gets to mem_insnB*s and starts to create > N new dependencies for _every_ mem_insnB*. This gets us N*M new > dependencies. > > In PR96833's testcase N and M are 10k-15k, which causes RAM usage of > 30GB and compilation time of 30 minutes, with sched2 accounting for > 95% of both metrics. After this patch the RAM usage is down to 1GB > and compilation time is down to 3-4 minutes, with sched2 no longer > standing out on -ftime-report or memory usage. > > gcc/ChangeLog: > > PR rtl-optimization/96388 > PR rtl-optimization/111554 > * sched-deps.cc (find_inc): Avoid exponential behavior. > --- > gcc/sched-deps.cc | 48 +++++++++++++++++++++++++++++++++++++++++++---- > 1 file changed, 44 insertions(+), 4 deletions(-) > > diff --git a/gcc/sched-deps.cc b/gcc/sched-deps.cc > index c23218890f3..005fc0f567e 100644 > --- a/gcc/sched-deps.cc > +++ b/gcc/sched-deps.cc > @@ -4779,24 +4779,59 @@ parse_add_or_inc (struct mem_inc_info *mii, > rtx_insn *insn, bool before_mem) > /* Once a suitable mem reference has been found and the corresponding data > in MII has been filled in, this function is called to find a suitable > add or inc insn involving the register we found in the memory > - reference. */ > + reference. > + If successful, this function will create additional dependencies > between > + - mii->inc_insn's producers and mii->mem_insn as a consumer (if > backwards) > + - mii->inc_insn's consumers and mii->mem_insn as a producer (if > !backwards). > +*/ > > static bool > find_inc (struct mem_inc_info *mii, bool backwards) > { > sd_iterator_def sd_it; > dep_t dep; > + sd_list_types_def mem_deps = backwards ? SD_LIST_HARD_BACK : > SD_LIST_FORW; > + int n_mem_deps = sd_lists_size (mii->mem_insn, mem_deps); > > - sd_it = sd_iterator_start (mii->mem_insn, > - backwards ? SD_LIST_HARD_BACK : SD_LIST_FORW); > + sd_it = sd_iterator_start (mii->mem_insn, mem_deps); > while (sd_iterator_cond (&sd_it, &dep)) > { > dep_node_t node = DEP_LINK_NODE (*sd_it.linkp); > rtx_insn *pro = DEP_PRO (dep); > rtx_insn *con = DEP_CON (dep); > - rtx_insn *inc_cand = backwards ? pro : con; > + rtx_insn *inc_cand; > + int n_inc_deps; > + > if (DEP_NONREG (dep) || DEP_MULTIPLE (dep)) > goto next; > + > + if (backwards) > + { > + inc_cand = pro; > + n_inc_deps = sd_lists_size (inc_cand, SD_LIST_BACK); > + } > + else > + { > + inc_cand = con; > + n_inc_deps = sd_lists_size (inc_cand, SD_LIST_FORW); > + } > + > + /* In the FOR_EACH_DEP loop below we will create additional > n_inc_deps > + for mem_insn. This by itself is not a problem, since each > mem_insn > + will have only a few inc_insns associated with it. However, if > + we consider that a single inc_insn may have a lot of mem_insns, > AND, > + on top of that, a few other inc_insns associated with it -- > + those _other inc_insns_ will get (n_mem_deps * number of MEM > insns) > + dependencies created for them. This may cause an exponential > + growth of memory usage and scheduling time. > + See PR96388 for details. > + We [heuristically] use n_inc_deps as a proxy for the number of MEM > + insns, and drop opportunities for breaking modifiable_mem > dependencies > + when dependency lists grow beyond reasonable size. */ > + if (n_mem_deps * n_inc_deps > + >= param_max_pending_list_length * param_max_pending_list_length) > + goto next; > + > if (parse_add_or_inc (mii, inc_cand, backwards)) > { > struct dep_replacement *desc; > @@ -4838,6 +4873,11 @@ find_inc (struct mem_inc_info *mii, bool backwards) > desc->insn = mii->mem_insn; > move_dep_link (DEP_NODE_BACK (node), INSN_HARD_BACK_DEPS (con), > INSN_SPEC_BACK_DEPS (con)); > + > + /* Make sure that n_inc_deps above is consistent with > dependencies > + we create. */ > + gcc_assert (mii->inc_insn == inc_cand); > + > if (backwards) > { > FOR_EACH_DEP (mii->inc_insn, SD_LIST_BACK, sd_it, dep) > -- > 2.34.1 > > -- Maxim Kuvyrkov www.linaro.org --000000000000f4b502060efb8b6d--