From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-wr1-x433.google.com (mail-wr1-x433.google.com [IPv6:2a00:1450:4864:20::433]) by sourceware.org (Postfix) with ESMTPS id E69D73858008 for ; Mon, 20 Nov 2023 14:39:39 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org E69D73858008 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 E69D73858008 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2a00:1450:4864:20::433 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1700491181; cv=none; b=oc8Gq9m5M65CZ2xUi25ppFVSJcdetoonc6HyHf6EZtWC5JiY+HSl+6XiV08BW6esn0Unmy2IjybMK1n7SriLza76hJHiPCzGVkro4VK/QIVgfWMtRWLU/+4KQIfYAsMTSy07xZr5v6OV/HhfwwSXq6sAeh54Yfs7Nz56VuhiSl4= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1700491181; c=relaxed/simple; bh=ZZP4ka1rFAYaXdff/7+VqPOAEpfmT1GIAAGedlVgplc=; h=DKIM-Signature:Mime-Version:Subject:From:Date:Message-Id:To; b=BX4KBq+ySiw+vX0T+Jla9JUji6L6c5iYn1r2RKVWiv0Mxl41a8o/ZPt4R7Ctq64AmCtnmKqJuKVYFgJwEVIcBnNNmNsvPHz7cLku2wW4wWZbJEXesD/JHtniXd4mZ7s1AOaaViv4Hgvh9RnULJcUy9yyZp93sCiXEIDVbTK5IDU= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-wr1-x433.google.com with SMTP id ffacd0b85a97d-32fa4183535so1060324f8f.1 for ; Mon, 20 Nov 2023 06:39:39 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; t=1700491178; x=1701095978; darn=gcc.gnu.org; h=to:references:message-id:content-transfer-encoding:cc:date :in-reply-to:from:subject:mime-version:from:to:cc:subject:date :message-id:reply-to; bh=zqsPSuzjlzzNlXTNy5qr5vYYd1peIYRZ+SAWKv8dX48=; b=A1wkVINTY3K7IBJJcCu4LYiFcCXgRq5uH690WNcmEe5XZvaWKEvXxNTYKCPNVR/Yxm GAMfP4r/BrgPQnhIq93P4/2Ka8YroplBRmshkNWPIKABSVO+8Sw7EOcAns1puaxBvtCR 3gWH4X/XQD6sSCqQaCw92muYsfkxF+sQn41bIqIghx/uboqBiij+/eQnV+vGDvYZsD4N cZRXFn2iLraaiueR/nk0RGxc8suYY0Ll8LFY9R6LP/xHcOqPgf2lqgW+yEMwqa8BssPr ZflitulkmPDoYf29m5uivAMZpPljtvbaHdQt5rZo/E3/Vc6YT7WJBOd9EbL4z/tVwKoV Jh9A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1700491178; x=1701095978; h=to:references:message-id:content-transfer-encoding:cc:date :in-reply-to:from:subject:mime-version:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=zqsPSuzjlzzNlXTNy5qr5vYYd1peIYRZ+SAWKv8dX48=; b=jMrm7VOMM9iK6oQttib4rNSEeo8gqEsbnmlURB/o1kTb62pefZdjjYPy8xq7oTOF1U MvrD1pdTo55BMsPg58ikMpCe0HqH6djXDd6LMkqL3OmuVJ+SJTAkJ9LRSr2mftJTXl5p X/E/oWmg/zo2Q56rVG5G4w2tVR2Efbk+oycEwX5/hu8ZpHRSWp4jCkYAiMQ+gBMgi26k J8CfhsHbSLytJGWrDJQFDg5WEHIe+LfBQ8BYZDedllUf87cyCgQnS1qvebq0XKegAPTo HU588nndpCFT+L+LdHUvWRwLzo5EVrZ2owrgNqxw8L5CqS21jDpADxUVEW1w6Y03G7Ff 4jFA== X-Gm-Message-State: AOJu0Ywyl+FAVVg+KeHnCDCvyeLixfRnKWHh/LAxnrInQs0tvE7rkctB PL3eQNBanwV2/eNVYXOYBj/J X-Google-Smtp-Source: AGHT+IE5aHJjiY0g6E68xtWKBg/WhLo6At1jVj2lSRo9exQsLm5hPXrGcnI2YmhdzSliBkdsIawhog== X-Received: by 2002:adf:f942:0:b0:32f:51c6:cd6c with SMTP id q2-20020adff942000000b0032f51c6cd6cmr4825938wrr.2.1700491178541; Mon, 20 Nov 2023 06:39:38 -0800 (PST) Received: from smtpclient.apple ([194.35.123.130]) by smtp.gmail.com with ESMTPSA id c11-20020adffb0b000000b0032ddf2804ccsm11389928wrr.83.2023.11.20.06.39.37 (version=TLS1_2 cipher=ECDHE-ECDSA-AES128-GCM-SHA256 bits=128/128); Mon, 20 Nov 2023 06:39:37 -0800 (PST) Content-Type: text/plain; charset=us-ascii Mime-Version: 1.0 (Mac OS X Mail 16.0 \(3731.700.6\)) Subject: Re: [PATCH 1/1] sched-deps.cc (find_modifiable_mems): Avoid exponential behavior From: Maxim Kuvyrkov In-Reply-To: <8587bddb-e348-a637-2fe2-8318bb09b3be@ispras.ru> Date: Mon, 20 Nov 2023 18:39:26 +0400 Cc: GCC Patches , Bernd Schmidt , Vladimir Makarov , Jeff Law Content-Transfer-Encoding: quoted-printable Message-Id: References: <20231120120649.672893-1-maxim.kuvyrkov@linaro.org> <20231120120649.672893-2-maxim.kuvyrkov@linaro.org> <8587bddb-e348-a637-2fe2-8318bb09b3be@ispras.ru> To: Alexander Monakov X-Mailer: Apple Mail (2.3731.700.6) X-Spam-Status: No, score=-5.2 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,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 Nov 20, 2023, at 17:52, Alexander Monakov = wrote: >=20 >=20 > On Mon, 20 Nov 2023, Maxim Kuvyrkov wrote: >=20 >> 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) ... >> =3D=3D=3D >> sp=3Dsp-4 // sp_insnA >> mem_insnA1[sp+A1] >> ... >> mem_insnAN[sp+AN] >> sp=3Dsp-4 // sp_insnB >> mem_insnB1[sp+B1] >> ... >> mem_insnBM[sp+BM] >> =3D=3D=3D >> ... 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. [For avoidance of doubt, below discussion is about the general = implementation of find_modifiable_mems() and not about the patch.] >=20 > It's a bit hard to read this without knowing which value of = 'backwards' > is assumed. >=20 > Say 'backwards' is true and we are inspecting producer sp_insnB of = mem_insnB1. > This is a true dependency. We know we can break it by adjusting B1 by = -4, but > we need to be careful not to move such modified mem_insnB1 above = sp_insnA, so > we need to iterate over *incoming true dependencies* of sp_insnB and = add them. >=20 > But the code seems to be iterating over *all incoming dependencies*, = so it > will e.g. take anti-dependency mem_insnA1 -> sp_insnB and create a = true > dependency mem_insnA1 -> mem_insnB1'. This seems utterly inefficient, = if my > understanding is correct. Yeap, your understanding is correct. However, this is what = find_modifiable_mems() has to do to avoid complicated analysis of = second-level dependencies. I think, the optimization that find_modifiable_mems() does can be = implemented as part of main dependency analysis, and I'm going to = discuss that with Bernd. I might be missing something, but it seems = that instruction transformations that find_modifiable_mems() is doing = are simpler than what ia64 speculation is doing. So, I think, we should = be able to leverage speculation infrastructure, rather than doing this = optimization "on the side" of normal scheduling. -- Maxim Kuvyrkov https://www.linaro.org