[Bug rtl-optimization/60757] New: combine uses exponential time in nonzero_bits1 recursion

[Bug rtl-optimization/60757] New: combine uses exponential time in nonzero_bits1 recursion

[amylaar at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60757

            Bug ID: 60757
           Summary: combine uses exponential time in nonzero_bits1
                    recursion
           Product: gcc
           Version: 4.9.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: rtl-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: amylaar at gcc dot gnu.org

Created attachment 32540
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=32540&action=edit
pruned down testcase

With a small fix to the rtx_costs for epiphany, gcc.c-torture/compile/pr43415.c
times out compiling at -O3.
Even when the loop iteration counts are pruned, it's still too much,
as nonzero_bits recurses for both operands of a binary operator...
going through 40 operations means 2^40 paths being followed...

[Bug rtl-optimization/60757] combine uses exponential time in nonzero_bits1 recursion

[amylaar at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60757

--- Comment #1 from Jorn Wolfgang Rennecke <amylaar at gcc dot gnu.org> ---
Created attachment 32541
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=32541&action=edit
epiphany cost fix that triggers combine exponential behaviour

[Bug rtl-optimization/60757] combine uses exponential time in nonzero_bits1 recursion

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60757

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
Can you point to the recursion please?

[Bug rtl-optimization/60757] combine uses exponential time in nonzero_bits1 recursion

[amylaar at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60757

--- Comment #3 from Jorn Wolfgang Rennecke <amylaar at gcc dot gnu.org> ---
Created attachment 32544
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=32544&action=edit
typescript with backtrace

It appears that some other epiphany patches I had in my tree I thought were
unrelated are, in fact, also relevant.

The exact version I've been using can be retrieved with:

git clone git@github.com:adapteva/epiphany-gcc.git
cd epiphany-gcc
git checkout ee67b804bd922ddcc72695973bed4641ba29801c

[Bug rtl-optimization/60757] combine uses exponential time in nonzero_bits1 recursion

[amylaar at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60757

--- Comment #4 from Jorn Wolfgang Rennecke <amylaar at gcc dot gnu.org> ---
(In reply to Jorn Wolfgang Rennecke from comment #3)
> Created attachment 32544 [details]
> typescript with backtrace
> 
> It appears that some other epiphany patches I had in my tree I thought were
> unrelated are, in fact, also relevant.
> 
> The exact version I've been using can be retrieved with:
> 
> git clone git@github.com:adapteva/epiphany-gcc.git
> cd epiphany-gcc
> git checkout ee67b804bd922ddcc72695973bed4641ba29801c

P.S.: that version sits on branch epiphany-gcc-4.8, so it should be sufficient
to clone that branch.  And it's based on the gcc git mirror, so if you have
a git local repo with gcc git mirror contents, most of the objects should
already be there.