public inbox for gcc-bugs@sourceware.org help / color / mirror / Atom feed
From: "amacleod at redhat dot com" <gcc-bugzilla@gcc.gnu.org> To: gcc-bugs@gcc.gnu.org Subject: [Bug tree-optimization/103821] [12 Regression] huge compile time (jump threading) at -O3 for simple code since r12-4790-g4b3a325f07acebf47e82de227ce1d5ba62f5bcae Date: Mon, 10 Jan 2022 21:12:39 +0000 [thread overview] Message-ID: <bug-103821-4-jjy883ZUJm@http.gcc.gnu.org/bugzilla/> (raw) In-Reply-To: <bug-103821-4@http.gcc.gnu.org/bugzilla/> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103821 --- Comment #3 from Andrew Macleod <amacleod at redhat dot com> --- Interesting. This isn't caused by jump threading, just exposed by it. We end up unrolling this loop, and the pattern of code creates a set of cascading multiplies for which we can precisely evaluate them with subranges. For instance, we calculate: _38 = int [8192, 8192][24576, 24576][40960, 40960][57344, 57344] so _38 has 4 subranges, and then we calculate: _39 = _38 * _38; we do 16 multiplications and end up with: int [67108864, 67108864][201326592, 201326592][335544320, 335544320][469762048, 469762048][603979776, 603979776][1006632960, 1006632960][1409286144, 1409286144][1677721600, 1677721600][+INF, +INF] This feeds other multiplies and progresses rapidly to blow up the number of subranges, which are then propagated via PHIs and other operations. Folding of subranges is an O(n*m) process. We perform the operation on each pair of subranges and union them. Values like _38 * _38 that continue feeding each other quickly become exponential. Then combining that with union (an inherently linear operation over the number of subranges) at each step of the way adds an additional quadratic operation on top of the exponential factor. I will adjust the wi_fold routine to recognize when the calculation is moving in an exponential direction, simply produce a summary a result instead of a precise one. Longer term, we could consider merging some of the subranges to prevent the exponential growth, but still retain some precision.
next prev parent reply other threads:[~2022-01-10 21:12 UTC|newest] Thread overview: 8+ messages / expand[flat|nested] mbox.gz Atom feed top 2021-12-23 20:14 [Bug tree-optimization/103821] New: [12 Regression] huge compile time (jump threading) at -O3 for simple code pinskia at gcc dot gnu.org 2021-12-23 20:14 ` [Bug tree-optimization/103821] " pinskia at gcc dot gnu.org 2021-12-23 20:14 ` pinskia at gcc dot gnu.org 2021-12-28 10:56 ` [Bug tree-optimization/103821] [12 Regression] huge compile time (jump threading) at -O3 for simple code since r12-4790-g4b3a325f07acebf47e82de227ce1d5ba62f5bcae marxin at gcc dot gnu.org 2022-01-04 13:26 ` rguenth at gcc dot gnu.org 2022-01-10 21:12 ` amacleod at redhat dot com [this message] 2022-01-11 14:39 ` cvs-commit at gcc dot gnu.org 2022-01-11 14:40 ` amacleod at redhat dot com
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=bug-103821-4-jjy883ZUJm@http.gcc.gnu.org/bugzilla/ \ --to=gcc-bugzilla@gcc.gnu.org \ --cc=gcc-bugs@gcc.gnu.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).