From: "bin.cheng" <bin.cheng@linux.alibaba.com>
To: "GCC Patches" <gcc-patches@gcc.gnu.org>
Subject: [PATCH PR90078]Capping comp_cost computation in ivopts
Date: Wed, 17 Apr 2019 07:00:00 -0000 [thread overview]
Message-ID: <7cb22a67-89e5-45d3-aef4-398311416140.bin.cheng@linux.alibaba.com> (raw)
[-- Attachment #1: Type: text/plain, Size: 948 bytes --]
Hi,
As discussed in PR90078, this patch checks possible infinite_cost overflow in ivopts.
Also as discussed, overflow happens mostly because of cost scaling wrto bb_freq/loop_freq.
For the moment, we only implement capping in comp_cost operators, while in next
stage1, we may instead implement capping in get_scaled_computation_cost_at with
more supporting benchmark data.
BTW, I think switching costs around comparison between infinite_cost is unnecessary
since there will be no overflow in integer after capping with infinite_cost.
Bootstrap and test on x86_64, is it OK?
Thanks,
bin
2019-04-17 Bin Cheng <bin.cheng@linux.alibaba.com>
PR tree-optimization/92078
* tree-ssa-loop-ivopts.c (comp_cost::operator +,-,+=,-+,/=,*=): Add
checks for infinite_cost overflow.
2018-04-17 Bin Cheng <bin.cheng@linux.alibaba.com>
PR tree-optimization/92078
* gcc/testsuite/g++.dg/tree-ssa/pr90078.C: New test.
[-- Attachment #2: 0001-pr90078.patch --]
[-- Type: application/octet-stream, Size: 8310 bytes --]
diff --git a/gcc/testsuite/g++.dg/tree-ssa/pr90078.C b/gcc/testsuite/g++.dg/tree-ssa/pr90078.C
new file mode 100644
index 00000000000..e36f50e9d8a
--- /dev/null
+++ b/gcc/testsuite/g++.dg/tree-ssa/pr90078.C
@@ -0,0 +1,199 @@
+// { dg-do compile }
+// { dg-options "-std=c++14 -O2 -ftemplate-depth=1000000" }
+
+template <class T, int Dim0, int Dim1, int Dim2> struct Tensor3;
+template <class A, class T, int Dim0, int Dim1, int Dim2, char i, char j,
+ char k>
+struct Tensor3_Expr;
+
+template <class T, int Dim0, int Dim1, int Dim2, int Dim3> struct Tensor4;
+template <class A, class T, int Dim0, int Dim1, int Dim2, int Dim3, char i,
+ char j, char k, char l>
+struct Tensor4_Expr;
+
+template <char i, int Dim> struct Index
+{};
+template <const int N> struct Number
+{
+ Number(){};
+ operator int() const { return N; }
+};
+
+template <class T, int Tensor_Dim0, int Tensor_Dim1, int Tensor_Dim2>
+struct Tensor3
+{
+ T data[Tensor_Dim0][Tensor_Dim1][Tensor_Dim2];
+
+ T operator()(const int N1, const int N2, const int N3) const
+ {
+ return data[N1][N2][N3];
+ }
+
+ template <char i, char j, char k, int Dim0, int Dim1, int Dim2>
+ Tensor3_Expr<const Tensor3<T, Tensor_Dim0, Tensor_Dim1, Tensor_Dim2>, T,
+ Dim0, Dim1, Dim2, i, j, k>
+ operator()(const Index<i, Dim0>, const Index<j, Dim1>,
+ const Index<k, Dim2>) const
+ {
+ return Tensor3_Expr<const Tensor3<T, Tensor_Dim0, Tensor_Dim1, Tensor_Dim2>,
+ T, Dim0, Dim1, Dim2, i, j, k>(*this);
+ }
+};
+
+template <class A, class T, int Dim0, int Dim1, int Dim2, char i, char j,
+ char k>
+struct Tensor3_Expr
+{
+ A iter;
+
+ Tensor3_Expr(const A &a) : iter(a) {}
+ T operator()(const int N1, const int N2, const int N3) const
+ {
+ return iter(N1, N2, N3);
+ }
+};
+
+template <class A, class T, int Tensor_Dim0, int Tensor_Dim1, int Tensor_Dim2,
+ int Dim0, int Dim1, int Dim2, char i, char j, char k>
+struct Tensor3_Expr<Tensor3<A, Tensor_Dim0, Tensor_Dim1, Tensor_Dim2>, T, Dim0,
+ Dim1, Dim2, i, j, k>
+{
+ Tensor3<A, Tensor_Dim0, Tensor_Dim1, Tensor_Dim2> &iter;
+
+ Tensor3_Expr(Tensor3<A, Tensor_Dim0, Tensor_Dim1, Tensor_Dim2> &a) : iter(a)
+ {}
+ T operator()(const int N1, const int N2, const int N3) const
+ {
+ return iter(N1, N2, N3);
+ }
+};
+
+template <class A, class B, class T, class U, int Dim0, int Dim1, int Dim23,
+ int Dim4, int Dim5, char i, char j, char k, char l, char m>
+struct Tensor3_times_Tensor3_21
+{
+ Tensor3_Expr<A, T, Dim0, Dim1, Dim23, i, j, k> iterA;
+ Tensor3_Expr<B, U, Dim23, Dim4, Dim5, k, l, m> iterB;
+
+ template <int CurrentDim>
+ T eval(const int N1, const int N2, const int N3, const int N4,
+ const Number<CurrentDim> &) const
+ {
+ return iterA(N1, N2, CurrentDim - 1) * iterB(CurrentDim - 1, N3, N4)
+ + eval(N1, N2, N3, N4, Number<CurrentDim - 1>());
+ }
+ T eval(const int N1, const int N2, const int N3, const int N4,
+ const Number<1> &) const
+ {
+ return iterA(N1, N2, 0) * iterB(0, N3, N4);
+ }
+
+ Tensor3_times_Tensor3_21(
+ const Tensor3_Expr<A, T, Dim0, Dim1, Dim23, i, j, k> &a,
+ const Tensor3_Expr<B, U, Dim23, Dim4, Dim5, k, l, m> &b)
+ : iterA(a), iterB(b)
+ {}
+ T operator()(const int &N1, const int &N2, const int &N3,
+ const int &N4) const
+ {
+ return eval(N1, N2, N3, N4, Number<Dim23>());
+ }
+};
+
+template <class A, class B, class T, class U, int Dim0, int Dim1, int Dim23,
+ int Dim4, int Dim5, char i, char j, char k, char l, char m>
+Tensor4_Expr<Tensor3_times_Tensor3_21<A, B, T, U, Dim0, Dim1, Dim23, Dim4,
+ Dim5, i, j, k, l, m>,
+ T, Dim0, Dim1, Dim4, Dim5, i, j, l, m>
+operator*(const Tensor3_Expr<A, T, Dim0, Dim1, Dim23, i, j, k> &a,
+ const Tensor3_Expr<B, U, Dim23, Dim4, Dim5, k, l, m> &b)
+{
+ using TensorExpr = Tensor3_times_Tensor3_21<A, B, T, U, Dim0, Dim1, Dim23,
+ Dim4, Dim5, i, j, k, l, m>;
+ return Tensor4_Expr<TensorExpr, T, Dim0, Dim1, Dim4, Dim5, i, j, l, m>(
+ TensorExpr(a, b));
+};
+
+template <class T, int Tensor_Dim0, int Tensor_Dim1, int Tensor_Dim2,
+ int Tensor_Dim3>
+struct Tensor4
+{
+ T data[Tensor_Dim0][Tensor_Dim1][Tensor_Dim2][Tensor_Dim3];
+
+ Tensor4() {}
+ T &operator()(const int N1, const int N2, const int N3, const int N4)
+ {
+ return data[N1][N2][N3][N4];
+ }
+
+ template <char i, char j, char k, char l, int Dim0, int Dim1, int Dim2,
+ int Dim3>
+ Tensor4_Expr<Tensor4<T, Tensor_Dim0, Tensor_Dim1, Tensor_Dim2, Tensor_Dim3>,
+ T, Dim0, Dim1, Dim2, Dim3, i, j, k, l>
+ operator()(const Index<i, Dim0>, const Index<j, Dim1>, const Index<k, Dim2>,
+ const Index<l, Dim3>)
+ {
+ return Tensor4_Expr<
+ Tensor4<T, Tensor_Dim0, Tensor_Dim1, Tensor_Dim2, Tensor_Dim3>, T, Dim0,
+ Dim1, Dim2, Dim3, i, j, k, l>(*this);
+ };
+};
+
+template <class A, class T, int Dim0, int Dim1, int Dim2, int Dim3, char i,
+ char j, char k, char l>
+struct Tensor4_Expr
+{
+ A iter;
+
+ Tensor4_Expr(const A &a) : iter(a) {}
+ T operator()(const int N1, const int N2, const int N3, const int N4) const
+ {
+ return iter(N1, N2, N3, N4);
+ }
+};
+
+template <class A, class T, int Dim0, int Dim1, int Dim2, int Dim3, char i,
+ char j, char k, char l>
+struct Tensor4_Expr<Tensor4<A, Dim0, Dim1, Dim2, Dim3>, T, Dim0, Dim1, Dim2,
+ Dim3, i, j, k, l>
+{
+ Tensor4<A, Dim0, Dim1, Dim2, Dim3> &iter;
+
+ Tensor4_Expr(Tensor4<A, Dim0, Dim1, Dim2, Dim3> &a) : iter(a) {}
+ T operator()(const int N1, const int N2, const int N3, const int N4) const
+ {
+ return iter(N1, N2, N3, N4);
+ }
+
+ template <class B, class U, int Dim1_0, int Dim1_1, int Dim1_2, int Dim1_3,
+ char i_1, char j_1, char k_1, char l_1>
+ auto &operator=(const Tensor4_Expr<B, U, Dim1_0, Dim1_1, Dim1_2, Dim1_3, i_1,
+ j_1, k_1, l_1> &rhs)
+ {
+ for(int ii = 0; ii < Dim0; ++ii)
+ for(int jj = 0; jj < Dim1; ++jj)
+ for(int kk = 0; kk < Dim2; ++kk)
+ for(int ll = 0; ll < Dim3; ++ll)
+ {
+ iter(ii, jj, kk, ll) = rhs(ii, jj, kk, ll);
+ }
+ return *this;
+ }
+};
+
+int main()
+{
+ Tensor3<float, 100, 100, 1000> t1;
+ Tensor3<float, 1000, 100, 100> t2;
+
+ Index<'l', 100> l;
+ Index<'m', 100> m;
+ Index<'k', 1000> k;
+ Index<'n', 100> n;
+ Index<'o', 100> o;
+
+ Tensor4<float, 100, 100, 100, 100> res;
+ res(l, m, n, o) = t1(l, m, k) * t2(k, n, o);
+ return 0;
+}
+
diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c
index a2b6b2b2312..4ca1f0e9686 100644
--- a/gcc/tree-ssa-loop-ivopts.c
+++ b/gcc/tree-ssa-loop-ivopts.c
@@ -243,6 +243,9 @@ operator+ (comp_cost cost1, comp_cost cost2)
if (cost1.infinite_cost_p () || cost2.infinite_cost_p ())
return infinite_cost;
+ if (cost1.cost + cost2.cost >= infinite_cost.cost)
+ return infinite_cost;
+
cost1.cost += cost2.cost;
cost1.complexity += cost2.complexity;
@@ -256,6 +259,8 @@ operator- (comp_cost cost1, comp_cost cost2)
return infinite_cost;
gcc_assert (!cost2.infinite_cost_p ());
+ if (cost1.cost - cost2.cost >= infinite_cost.cost)
+ return infinite_cost;
cost1.cost -= cost2.cost;
cost1.complexity -= cost2.complexity;
@@ -276,6 +281,8 @@ comp_cost::operator+= (HOST_WIDE_INT c)
if (infinite_cost_p ())
return *this;
+ if (this->cost + c >= infinite_cost.cost)
+ return infinite_cost;
this->cost += c;
return *this;
@@ -287,6 +294,8 @@ comp_cost::operator-= (HOST_WIDE_INT c)
if (infinite_cost_p ())
return *this;
+ if (this->cost - c >= infinite_cost.cost)
+ return infinite_cost;
this->cost -= c;
return *this;
@@ -295,6 +304,7 @@ comp_cost::operator-= (HOST_WIDE_INT c)
comp_cost
comp_cost::operator/= (HOST_WIDE_INT c)
{
+ gcc_assert (c != 0);
if (infinite_cost_p ())
return *this;
@@ -309,6 +319,9 @@ comp_cost::operator*= (HOST_WIDE_INT c)
if (infinite_cost_p ())
return *this;
+ if (this->cost * c >= infinite_cost.cost)
+ return infinite_cost;
+
this->cost *= c;
return *this;
next reply other threads:[~2019-04-17 6:13 UTC|newest]
Thread overview: 8+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-04-17 7:00 bin.cheng [this message]
2019-04-17 7:19 ` Jakub Jelinek
2019-04-17 11:14 ` Bin.Cheng
2019-04-17 11:35 ` Jakub Jelinek
2019-05-05 6:02 ` bin.cheng
2019-05-06 10:11 ` Richard Biener
2019-05-06 10:24 ` Bin.Cheng
2019-05-06 10:27 ` Richard Biener
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=7cb22a67-89e5-45d3-aef4-398311416140.bin.cheng@linux.alibaba.com \
--to=bin.cheng@linux.alibaba.com \
--cc=gcc-patches@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: link
Be 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).