[Bug c++/90078] New: ICE with deep templates caused by overflow [PATCH]

[wlandry at caltech dot edu]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=90078

Bug ID: 90078
   Summary: ICE with deep templates caused by overflow [PATCH]
   Product: gcc
   Version: tree-ssa
Status: UNCONFIRMED
  Severity: normal
  Priority: P3
 Component: c++
  Assignee: unassigned at gcc dot gnu.org
  Reporter: wlandry at caltech dot edu
  Target Milestone: ---

Created attachment 46160
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=46160&action=edit
Failing test case

Compiling the attached code with

  g++ -O2 ftensorShowcase.cpp -c -ftemplate-depth=100

fails with the internal compiler error below.  Using godbolt, it seems that
this bug started in gcc 7.1 and is still present in trunk.

In gcc/tree-ssa-loop-ivopts.c, there is a cost struct that has a concept of
infinity.  For very deep, recursive templates, the cost can get larger than
'infinity' (1000).  The diff below against trunk implements saturating
arithmetic.  It seems to work.

Thanks.

==


diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c
index a2b6b2b2312..a89782b13d0 100644
--- a/gcc/tree-ssa-loop-ivopts.c
+++ b/gcc/tree-ssa-loop-ivopts.c
@@ -276,7 +276,11 @@ comp_cost::operator+= (HOST_WIDE_INT c)
   if (infinite_cost_p ())
 return *this;

-  this->cost += c;
+  /* Switch around comparison to avoid overflow */
+  if (c > infinite_cost.cost - this->cost)
+this->cost = infinite_cost.cost;
+  else
+this->cost += c;

   return *this;
 }
@@ -287,7 +291,11 @@ comp_cost::operator-= (HOST_WIDE_INT c)
   if (infinite_cost_p ())
 return *this;

-  this->cost -= c;
+  /* Switch around comparison to avoid overflow */
+  if (c < -infinite_cost.cost + this->cost )
+this->cost = infinite_cost.cost;
+  else
+this->cost -= c;

   return *this;
 }
@@ -298,7 +306,10 @@ comp_cost::operator/= (HOST_WIDE_INT c)
   if (infinite_cost_p ())
 return *this;

-  this->cost /= c;
+  if (c == 0)
+this->cost = infinite_cost.cost;
+  else
+this->cost /= c;

   return *this;
 }
@@ -309,7 +320,11 @@ comp_cost::operator*= (HOST_WIDE_INT c)
   if (infinite_cost_p ())
 return *this;

-  this->cost *= c;
+  /* Switch around comparison to avoid overflow */
+  if (c > infinite_cost.cost / this->cost )
+this->cost = infinite_cost.cost;
+  else
+this->cost *= c;

   return *this;
 }


==

during GIMPLE pass: ivopts
ftensorShowcase.cpp: In member function ‘auto& Tensor4_Expr, T, Dim0, Dim1, Dim2, Dim3, i, j, k, l>::operator=(const
Tensor4_Expr&) [with
B = Tensor3_times_Tensor3_21, const
Tensor3, float, float, 100, 100, 1000, 100, 100, 'l',
'm', 'k', 'n', 'o'>; U = float; int Dim1_0 = 100; int Dim1_1 = 100; int Dim1_2
= 100; int Dim1_3 = 100; char i_1 = 'l'; char j_1 = 'm'; char k_1 = 'n'; char
l_1 = 'o'; A = float; T = float; int Dim0 = 100; int Dim1 = 100; int Dim2 =
100; int Dim3 = 100; char i = 'l'; char j = 'm'; char k = 'n'; char l = 'o']’:
ftensorShowcase.cpp:170:9: internal compiler error: in try_improve_iv_set, at
tree-ssa-loop-ivopts.c:6667
   auto &operator=(const Tensor4_Expr for instructions.

[Bug c++/90078] [7/8/9 Regression] ICE with deep templates caused by overflow [PATCH]

[wlandry at caltech dot edu]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=90078

--- Comment #3 from Walter Landry  ---
(In reply to Martin Liška from comment #2)
> I'm adding the pass maintainer to CC.
> @Walter: Do you have an account so that you'll be able to propose the patch
> to GCC patches mailing list?

The only account I have with GCC is bugzilla.  I have never posted anything to
gcc-patches, but long ago I sent some messages to g...@gcc.gnu.org.  Let me know
what you want me to do.

[Bug tree-optimization/90078] [7/8/9 Regression] ICE with deep templates caused by overflow [PATCH]

[wlandry at caltech dot edu]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=90078

--- Comment #8 from Walter Landry  ---
(In reply to Martin Liška from comment #5)
> (In reply to bin cheng from comment #4)
> > Another problem is the generated binary has segment fault issue even
> > compiled O0:
> > 
> > $ ./g++ -O0 pr90078.cc -o a.out -ftemplate-depth=100 -ftime-report  -g
> > -std=c++14
> > $ gdb --args ./a.out
> > 
> > Dump of assembler code for function main():
> >0x00400572 <+0>: push   %rbp
> >0x00400573 <+1>: mov%rsp,%rbp
> >0x00400576 <+4>: sub$0x2625a020,%rsp
> >0x0040057d <+11>:lea-0x2625a020(%rbp),%rax
> >0x00400584 <+18>:mov%rax,%rdi
> > => 0x00400587 <+21>:callq  0x4006c0  > 100, 100>::Tensor4()>
> >0x0040058c <+26>:lea-0x4c4b410(%rbp),%rax
> >0x00400593 <+33>:lea-0xe4e1c10(%rbp),%rdx
> > 
> > The segment fault happens at the callq instruction.
> 
> Yes, same happens also for clang. It's a stack overflow:

That is not surprising.  The code recurses 1000 times.  I would not consider
crashing at runtime to be a bug.