From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lf1-x130.google.com (mail-lf1-x130.google.com [IPv6:2a00:1450:4864:20::130]) by sourceware.org (Postfix) with ESMTPS id DDBC93858D35 for ; Tue, 21 Nov 2023 10:32:19 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org DDBC93858D35 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 DDBC93858D35 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2a00:1450:4864:20::130 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1700562741; cv=none; b=HNPyD4qg2GFUHaIhafwrTHK7s9oeXqUGFNVHQzP9dfy/K48qetUS3Mlo1yMrK15o3Ws18j5eiY9EaGEnaKZR97+ZwKSjkMClWE5nhgS2/VQMKyZn58lNqcQwqCX24pUxj+VgtDlKBPzEPEAIhVDS7aadHGbrGBJNhWFuEQHcIl0= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1700562741; c=relaxed/simple; bh=5Rhok1nhlGHwMpXt0THTdDFTVz8JSDM6X1FEcN0TLik=; h=DKIM-Signature:Mime-Version:Subject:From:Date:Message-Id:To; b=nGPCCutdOHrTw2xIH8fd136Z3jpjmc7w4BEyD1KNyP2VJWSao+X4TGHwq2oGnWezo3m/wqfAdQWCTIjpHNpP8yLqF9rIQJvYkTFZp7dCIfiu0vf1CM/nIAzHLG2Uw39x8NSL02uzgmwHlCRRC5BfxoohE5q3TZO2+aUuD2peUp4= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-lf1-x130.google.com with SMTP id 2adb3069b0e04-50799fe3422so1163182e87.1 for ; Tue, 21 Nov 2023 02:32:19 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; t=1700562738; x=1701167538; 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=/wktgRIyRKqwCeQxiLHmq/BSChlLa/on+ilsnax2dJI=; b=tMGU4UWV9ccrg4zJUj06ARcaK5cu3jmHHS7Y4wCCZ11jMoBDxIlx6AXKNqc9+mL4aY ulJOmw3QiwNxCDHn3d+nRh+vibTFdS4CnpvRnpWFF3Ul0eHSmhM7cbafj1RzDS6J5e9y CZLYFQVh+qzAUhggth9BuHIQqu5kaEljd//z8yP8GHPY1XSrIUwlCPnsmOZbdsAQUw+Q 1inCUDINgIVmhImDAR9geJgjAOAxRAuTNgtaslOnIUIuof4TQ/TcnWmfl37/FRBjs2tD GPVlKocs3UJ7YyLqyxWtQIuFyXb0HS1neZ+OhmjmQolk9BKTxlxgLrICDDReMD/nL9t/ 80bQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1700562738; x=1701167538; 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=/wktgRIyRKqwCeQxiLHmq/BSChlLa/on+ilsnax2dJI=; b=popD6t8S02ClSqXxEFE0GwbzZZe8M8rajinPPO+P1T247GfiFdriOCMQB1Y5fCKQfb OQQLyhg4WTGL8O9K9qL1bljdMjsfaqGyCircJx3dfOyhC+5L9dcKy9A95Ou8XRalT1dN x/LAas4bnIvT6Ngf0YuBhJe3UAG24dYDstVfg1YhZOaJqMzyQ6wlAIe+IH6SlbuGTITp LhVbfcFef5zxDKw1FzICMmZkkD9haYr/4eWgi/x2H9Kls130CI6tWGSXqynkOLGed4Hx rP+iQqXEHXlGVe3e7fU/0POEywS124v1C8MI0WNGrTTCIwFZ06a+j01KgfH99+/1tDtf Wkow== X-Gm-Message-State: AOJu0YwoFMs2xzUmj8LGscvmPnk9RrrpvnRQZVKQ+Dz31gI8BpcOH7Xx TWTFG4AsYcl6lYS16KB25w8k X-Google-Smtp-Source: AGHT+IGN8P46/hhI/7WB1jkfpNOm3Lwma0NL6c+zlsHNAlm9AucD+OgQabPS+Io2n/K3ksy3pi8cSg== X-Received: by 2002:a2e:b809:0:b0:2c8:38b2:2c33 with SMTP id u9-20020a2eb809000000b002c838b22c33mr5659969ljo.3.1700562738114; Tue, 21 Nov 2023 02:32:18 -0800 (PST) Received: from smtpclient.apple ([185.216.146.33]) by smtp.gmail.com with ESMTPSA id w8-20020a05600c474800b0040836519dd9sm16878434wmo.25.2023.11.21.02.32.16 (version=TLS1_2 cipher=ECDHE-ECDSA-AES128-GCM-SHA256 bits=128/128); Tue, 21 Nov 2023 02:32:17 -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: Date: Tue, 21 Nov 2023 14:32:05 +0400 Cc: GCC Patches , Bernd Schmidt , Vladimir Makarov , Jeff Law Content-Transfer-Encoding: quoted-printable Message-Id: <478E2CE6-61BA-49E2-BD70-112A3653DFE0@linaro.org> 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=-4.5 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 20:30, Alexander Monakov = wrote: >=20 >=20 > On Mon, 20 Nov 2023, Maxim Kuvyrkov wrote: >=20 >>> 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. >>=20 >> [For avoidance of doubt, below discussion is about the general = implementation >> of find_modifiable_mems() and not about the patch.] >=20 > I was saying the commit message is hard to read (unless it's just me). >=20 >>> It's a bit hard to read this without knowing which value of = 'backwards' >>> is assumed. Oh, sorry, I misunderstood your comment. In the above example I want to describe outcome that current code = generates, without going into details about exactly how it does it. I'm = not sure how to make it more readable, and would appreciate suggestions. >>>=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. >>=20 >> Yeap, your understanding is correct. However, this is what >> find_modifiable_mems() has to do to avoid complicated analysis of = second-level >> dependencies. >=20 > What is the reason it cannot simply skip anti-dependencies in the > 'if (backwards)' loop, and true dependencies in the 'else' loop? I /think/, this should be possible. However, rather than improving = current implementation my preference is to rework it by integrating with = the main dependency analysis. This should provide both faster and more = precise dependency analysis, which would generate breakable addr/mem = dependencies. Thanks, -- Maxim Kuvyrkov https://www.linaro.org