* [PATCH PR90078]Capping comp_cost computation in ivopts @ 2019-04-17 7:00 bin.cheng 2019-04-17 7:19 ` Jakub Jelinek 0 siblings, 1 reply; 8+ messages in thread From: bin.cheng @ 2019-04-17 7:00 UTC (permalink / raw) To: GCC Patches [-- 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; ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH PR90078]Capping comp_cost computation in ivopts 2019-04-17 7:00 [PATCH PR90078]Capping comp_cost computation in ivopts bin.cheng @ 2019-04-17 7:19 ` Jakub Jelinek 2019-04-17 11:14 ` Bin.Cheng 0 siblings, 1 reply; 8+ messages in thread From: Jakub Jelinek @ 2019-04-17 7:19 UTC (permalink / raw) To: bin.cheng; +Cc: GCC Patches On Wed, Apr 17, 2019 at 02:13:12PM +0800, bin.cheng wrote: > 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. --- 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; As #define INFTY 10000000 what is the reason to keep the previous condition as well? I mean, if cost1.cost == INFTY or cost2.cost == INFTY, cost1.cost + cost2.cost >= INFTY too. Unless costs can go negative. @@ -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; Unless costs can be negative, when you first bail out for cost1.cost == INFTY, then cost1.cost - cost2.cost won't be INFTY (but could get negative). So shouldn't there be a guard against that instead? Or, if costs can be negative, shouldn't there be also guards that it doesn't grow too negative (say smaller than -INFTY)? Jakub ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH PR90078]Capping comp_cost computation in ivopts 2019-04-17 7:19 ` Jakub Jelinek @ 2019-04-17 11:14 ` Bin.Cheng 2019-04-17 11:35 ` Jakub Jelinek 0 siblings, 1 reply; 8+ messages in thread From: Bin.Cheng @ 2019-04-17 11:14 UTC (permalink / raw) To: Jakub Jelinek; +Cc: bin.cheng, GCC Patches On Wed, Apr 17, 2019 at 3:10 PM Jakub Jelinek <jakub@redhat.com> wrote: > > On Wed, Apr 17, 2019 at 02:13:12PM +0800, bin.cheng wrote: > > 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. > > --- 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; > > As > #define INFTY 10000000 > what is the reason to keep the previous condition as well? > I mean, if cost1.cost == INFTY or cost2.cost == INFTY, > cost1.cost + cost2.cost >= INFTY too. > Unless costs can go negative. It's a bit complicated, but in general, costs can go negative. > > @@ -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; > > Unless costs can be negative, when you first bail out > for cost1.cost == INFTY, then cost1.cost - cost2.cost won't > be INFTY (but could get negative). So shouldn't there be a guard against > that instead? Or, if costs can be negative, shouldn't there be also > guards that it doesn't grow too negative (say smaller than -INFTY)? Negative cost is kind of a result of booking cost cancellation at different place. For example, it mostly comes from in modeling auto increment/decrement addressing mode. To be specific, when IV's increment instruction can be merged into addressing mode, we cancel cost of IV increment operation in cand-use cost. Very likely 4 will be subtracted. In general, we wouldn't expect negative cost can go too big, so there is no -INFTY logic in ivopts at all. So this is the least invasive fix for the moment, I would consider capping bb_freq/loop_freq in the future which should rule out the overflow possibility in the first place. Thanks, bin > > Jakub ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH PR90078]Capping comp_cost computation in ivopts 2019-04-17 11:14 ` Bin.Cheng @ 2019-04-17 11:35 ` Jakub Jelinek 2019-05-05 6:02 ` bin.cheng 0 siblings, 1 reply; 8+ messages in thread From: Jakub Jelinek @ 2019-04-17 11:35 UTC (permalink / raw) To: Bin.Cheng; +Cc: bin.cheng, GCC Patches On Wed, Apr 17, 2019 at 07:14:05PM +0800, Bin.Cheng wrote: > > As > > #define INFTY 10000000 > > what is the reason to keep the previous condition as well? > > I mean, if cost1.cost == INFTY or cost2.cost == INFTY, > > cost1.cost + cost2.cost >= INFTY too. > > Unless costs can go negative. > It's a bit complicated, but in general, costs can go negative. Ok, no objections from me then (but as I don't know anything about it, not an ack either; you are ivopts maintainer, so you don't need one). Jakub ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH PR90078]Capping comp_cost computation in ivopts 2019-04-17 11:35 ` Jakub Jelinek @ 2019-05-05 6:02 ` bin.cheng 2019-05-06 10:11 ` Richard Biener 0 siblings, 1 reply; 8+ messages in thread From: bin.cheng @ 2019-05-05 6:02 UTC (permalink / raw) To: Jakub Jelinek; +Cc: GCC Patches [-- Attachment #1: Type: text/plain, Size: 2346 bytes --] > ------------------------------------------------------------------ > Sender:Jakub Jelinek <jakub@redhat.com> > Sent At:2019 Apr. 17 (Wed.) 19:27 > Recipient:Bin.Cheng <amker.cheng@gmail.com> > Cc:bin.cheng <bin.cheng@linux.alibaba.com>; GCC Patches <gcc-patches@gcc.gnu.org> > Subject:Re: [PATCH PR90078]Capping comp_cost computation in ivopts > > > On Wed, Apr 17, 2019 at 07:14:05PM +0800, Bin.Cheng wrote: > > > As > > > #define INFTY 10000000 > > > what is the reason to keep the previous condition as well? > > > I mean, if cost1.cost == INFTY or cost2.cost == INFTY, > > > cost1.cost + cost2.cost >= INFTY too. > > > Unless costs can go negative. > > It's a bit complicated, but in general, costs can go negative. > > Ok, no objections from me then (but as I don't know anything about it, > not an ack either; you are ivopts maintainer, so you don't need one). Hi, The previous patch was reverted on GCC-9 because of PR90240. PR90240 is now fixed by another patch. This is the updated patch for PR90078. It promotes type of ivopts cost from int to int64_t, as well as change behavior of infinite_cost overflow from saturation to assert. Please note, implicit conversions are kept in cost computation as before without introducing any narrowing. Bootstrap/test on x86_64 along with PR90240 patch. Is it OK? Thanks, bin 2019-05-05 Bin Cheng <bin.cheng@linux.alibaba.com> PR tree-optimization/90078 * tree-ssa-loop-ivopts.c (inttypes.h): Include new header file. (INFTY): Increase the value for infinite cost. (struct comp_cost): Promote type of members to int64_t. (infinite_cost): Don't set complexity in initialization. (comp_cost::operator +,-,+=,-+,/=,*=): Assert when cost computation overflows to infinite_cost. (adjust_setup_cost): Promote type of parameter and cost computation to int64_t. (struct ainc_cost_data, struct iv_ca): Promote type of member to int64_t. (get_scaled_computation_cost_at, determine_iv_cost): Promote type of cost computation to int64_t. (determine_group_iv_costs, iv_ca_dump, find_optimal_iv_set): Use int64_t's format specifier in dump. 2018-05-05 Bin Cheng <bin.cheng@linux.alibaba.com> PR tree-optimization/90078 * g++.dg/tree-ssa/pr90078.C: New test. [-- Attachment #2: 0002-Fix-pr90078-by-promoting-type-of-IVOPTs-cost-to-int6.patch --] [-- Type: application/octet-stream, Size: 14220 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 534e1463807..b626d33d209 100644 --- a/gcc/tree-ssa-loop-ivopts.c +++ b/gcc/tree-ssa-loop-ivopts.c @@ -66,6 +66,8 @@ along with GCC; see the file COPYING3. If not see to decide costs more precisely, but getting all the interactions right would be complicated. */ +#include <inttypes.h> + #include "config.h" #include "system.h" #include "coretypes.h" @@ -114,7 +116,7 @@ along with GCC; see the file COPYING3. If not see interface between the GIMPLE and RTL worlds. */ /* The infinite cost. */ -#define INFTY 10000000 +#define INFTY 1000000000L /* Returns the expected number of loop iterations for LOOP. The average trip count is computed from profile data if it @@ -180,7 +182,7 @@ struct comp_cost comp_cost (): cost (0), complexity (0), scratch (0) {} - comp_cost (int cost, unsigned complexity, int scratch = 0) + comp_cost (int64_t cost, unsigned complexity, int64_t scratch = 0) : cost (cost), complexity (complexity), scratch (scratch) {} @@ -220,16 +222,16 @@ struct comp_cost /* Returns true if COST1 is smaller or equal than COST2. */ friend bool operator<= (comp_cost cost1, comp_cost cost2); - int cost; /* The runtime cost. */ + int64_t cost; /* The runtime cost. */ unsigned complexity; /* The estimate of the complexity of the code for the computation (in no concrete units -- complexity field should be larger for more complex expressions and addressing modes). */ - int scratch; /* Scratch used during cost computation. */ + int64_t scratch; /* Scratch used during cost computation. */ }; static const comp_cost no_cost; -static const comp_cost infinite_cost (INFTY, INFTY, INFTY); +static const comp_cost infinite_cost (INFTY, 0, INFTY); bool comp_cost::infinite_cost_p () @@ -243,6 +245,7 @@ operator+ (comp_cost cost1, comp_cost cost2) if (cost1.infinite_cost_p () || cost2.infinite_cost_p ()) return infinite_cost; + gcc_assert (cost1.cost + cost2.cost < infinite_cost.cost); cost1.cost += cost2.cost; cost1.complexity += cost2.complexity; @@ -256,6 +259,7 @@ operator- (comp_cost cost1, comp_cost cost2) return infinite_cost; gcc_assert (!cost2.infinite_cost_p ()); + gcc_assert (cost1.cost - cost2.cost < infinite_cost.cost); cost1.cost -= cost2.cost; cost1.complexity -= cost2.complexity; @@ -276,6 +280,7 @@ comp_cost::operator+= (HOST_WIDE_INT c) if (infinite_cost_p ()) return *this; + gcc_assert (this->cost + c < infinite_cost.cost); this->cost += c; return *this; @@ -287,6 +292,7 @@ comp_cost::operator-= (HOST_WIDE_INT c) if (infinite_cost_p ()) return *this; + gcc_assert (this->cost - c < infinite_cost.cost); this->cost -= c; return *this; @@ -295,6 +301,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 +316,7 @@ comp_cost::operator*= (HOST_WIDE_INT c) if (infinite_cost_p ()) return *this; + gcc_assert (this->cost * c < infinite_cost.cost); this->cost *= c; return *this; @@ -638,7 +646,7 @@ struct iv_ca comp_cost cand_use_cost; /* Total cost of candidates. */ - unsigned cand_cost; + int64_t cand_cost; /* Number of times each invariant variable is used. */ unsigned *n_inv_var_uses; @@ -4025,16 +4033,16 @@ get_computation_at (struct loop *loop, gimple *at, if we're optimizing for speed, amortize it over the per-iteration cost. If ROUND_UP_P is true, the result is round up rather than to zero when optimizing for speed. */ -static unsigned -adjust_setup_cost (struct ivopts_data *data, unsigned cost, +static int64_t +adjust_setup_cost (struct ivopts_data *data, int64_t cost, bool round_up_p = false) { if (cost == INFTY) return cost; else if (optimize_loop_for_speed_p (data->current_loop)) { - HOST_WIDE_INT niters = avg_loop_niter (data->current_loop); - return ((HOST_WIDE_INT) cost + (round_up_p ? niters - 1 : 0)) / niters; + int64_t niters = (int64_t) avg_loop_niter (data->current_loop); + return (cost + (round_up_p ? niters - 1 : 0)) / niters; } else return cost; @@ -4305,7 +4313,7 @@ enum ainc_type struct ainc_cost_data { - unsigned costs[AINC_NONE]; + int64_t costs[AINC_NONE]; }; static comp_cost @@ -4566,12 +4574,12 @@ get_scaled_computation_cost_at (ivopts_data *data, gimple *at, comp_cost cost) if (scale_factor == 1) return cost; - int scaled_cost + int64_t scaled_cost = cost.scratch + (cost.cost - cost.scratch) * scale_factor; if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "Scaling cost based on bb prob " - "by %2.2f: %d (scratch: %d) -> %d\n", + fprintf (dump_file, "Scaling cost based on bb prob by %2.2f: " + "%" PRId64 " (scratch: %" PRId64 ") -> %" PRId64 "\n", 1.0f * scale_factor, cost.cost, cost.scratch, scaled_cost); cost.cost = scaled_cost; @@ -5539,7 +5547,7 @@ determine_group_iv_costs (struct ivopts_data *data) || group->cost_map[j].cost.infinite_cost_p ()) continue; - fprintf (dump_file, " %d\t%d\t%d\t", + fprintf (dump_file, " %d\t%" PRId64 "\t%d\t", group->cost_map[j].cand->id, group->cost_map[j].cost.cost, group->cost_map[j].cost.complexity); @@ -5569,7 +5577,7 @@ static void determine_iv_cost (struct ivopts_data *data, struct iv_cand *cand) { comp_cost cost_base; - unsigned cost, cost_step; + int64_t cost, cost_step; tree base; gcc_assert (cand->iv != NULL); @@ -6139,11 +6147,11 @@ iv_ca_dump (struct ivopts_data *data, FILE *file, struct iv_ca *ivs) unsigned i; comp_cost cost = iv_ca_cost (ivs); - fprintf (file, " cost: %d (complexity %d)\n", cost.cost, + fprintf (file, " cost: %" PRId64 " (complexity %d)\n", cost.cost, cost.complexity); - fprintf (file, " cand_cost: %d\n cand_group_cost: %d (complexity %d)\n", - ivs->cand_cost, ivs->cand_use_cost.cost, - ivs->cand_use_cost.complexity); + fprintf (file, " cand_cost: %" PRId64 "\n cand_group_cost: " + "%" PRId64 " (complexity %d)\n", ivs->cand_cost, + ivs->cand_use_cost.cost, ivs->cand_use_cost.complexity); bitmap_print (file, ivs->cands, " candidates: ","\n"); for (i = 0; i < ivs->upto; i++) @@ -6151,9 +6159,9 @@ iv_ca_dump (struct ivopts_data *data, FILE *file, struct iv_ca *ivs) struct iv_group *group = data->vgroups[i]; struct cost_pair *cp = iv_ca_cand_for_group (ivs, group); if (cp) - fprintf (file, " group:%d --> iv_cand:%d, cost=(%d,%d)\n", - group->id, cp->cand->id, cp->cost.cost, - cp->cost.complexity); + fprintf (file, " group:%d --> iv_cand:%d, cost=(" + "%" PRId64 ",%d)\n", group->id, cp->cand->id, + cp->cost.cost, cp->cost.complexity); else fprintf (file, " group:%d --> ??\n", group->id); } @@ -6751,9 +6759,9 @@ find_optimal_iv_set (struct ivopts_data *data) if (dump_file && (dump_flags & TDF_DETAILS)) { - fprintf (dump_file, "Original cost %d (complexity %d)\n\n", + fprintf (dump_file, "Original cost %" PRId64 " (complexity %d)\n\n", origcost.cost, origcost.complexity); - fprintf (dump_file, "Final cost %d (complexity %d)\n\n", + fprintf (dump_file, "Final cost %" PRId64 " (complexity %d)\n\n", cost.cost, cost.complexity); } ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH PR90078]Capping comp_cost computation in ivopts 2019-05-05 6:02 ` bin.cheng @ 2019-05-06 10:11 ` Richard Biener 2019-05-06 10:24 ` Bin.Cheng 0 siblings, 1 reply; 8+ messages in thread From: Richard Biener @ 2019-05-06 10:11 UTC (permalink / raw) To: bin.cheng; +Cc: Jakub Jelinek, GCC Patches On Sun, May 5, 2019 at 8:03 AM bin.cheng <bin.cheng@linux.alibaba.com> wrote: > > > ------------------------------------------------------------------ > > Sender:Jakub Jelinek <jakub@redhat.com> > > Sent At:2019 Apr. 17 (Wed.) 19:27 > > Recipient:Bin.Cheng <amker.cheng@gmail.com> > > Cc:bin.cheng <bin.cheng@linux.alibaba.com>; GCC Patches <gcc-patches@gcc.gnu.org> > > Subject:Re: [PATCH PR90078]Capping comp_cost computation in ivopts > > > > > > On Wed, Apr 17, 2019 at 07:14:05PM +0800, Bin.Cheng wrote: > > > > As > > > > #define INFTY 10000000 > > > > what is the reason to keep the previous condition as well? > > > > I mean, if cost1.cost == INFTY or cost2.cost == INFTY, > > > > cost1.cost + cost2.cost >= INFTY too. > > > > Unless costs can go negative. > > > It's a bit complicated, but in general, costs can go negative. > > > > Ok, no objections from me then (but as I don't know anything about it, > > not an ack either; you are ivopts maintainer, so you don't need one). > > Hi, > The previous patch was reverted on GCC-9 because of PR90240. PR90240 is now > fixed by another patch. This is the updated patch for PR90078. It promotes type > of ivopts cost from int to int64_t, as well as change behavior of infinite_cost overflow > from saturation to assert. > Please note, implicit conversions are kept in cost computation as before without > introducing any narrowing. > > Bootstrap/test on x86_64 along with PR90240 patch. Is it OK? Do not include system headers in .c files, instead those need to be (and are already) included via system.h. /* The infinite cost. */ -#define INFTY 10000000 +#define INFTY 1000000000L do we actually need this? What happens on a ilp32 host? That is, I believe you can drop the 'L' (it fits into an int anyways) @@ -256,6 +259,7 @@ operator- (comp_cost cost1, comp_cost cost2) return infinite_cost; gcc_assert (!cost2.infinite_cost_p ()); + gcc_assert (cost1.cost - cost2.cost < infinite_cost.cost); cost1.cost -= cost2.cost; cost1.complexity -= cost2.complexity; probably a pre-existing issue, but we do not seem to handle underflow here in general, nor check that underflow doesn't get us below -INFTY. I guess we really don't want negative costs? That doesn't seem to be documented and I was also wondering why the cost isn't unsigned... @@ -638,7 +646,7 @@ struct iv_ca comp_cost cand_use_cost; /* Total cost of candidates. */ - unsigned cand_cost; + int64_t cand_cost; /* Number of times each invariant variable is used. */ unsigned *n_inv_var_uses; shows this "issue". Can't we use uint64_t throughout the patch? Otherwise this looks OK. Thanks, Richard. > Thanks, > bin > 2019-05-05 Bin Cheng <bin.cheng@linux.alibaba.com> > > PR tree-optimization/90078 > * tree-ssa-loop-ivopts.c (inttypes.h): Include new header file. > (INFTY): Increase the value for infinite cost. > (struct comp_cost): Promote type of members to int64_t. > (infinite_cost): Don't set complexity in initialization. > (comp_cost::operator +,-,+=,-+,/=,*=): Assert when cost computation > overflows to infinite_cost. > (adjust_setup_cost): Promote type of parameter and cost computation > to int64_t. > (struct ainc_cost_data, struct iv_ca): Promote type of member to > int64_t. > (get_scaled_computation_cost_at, determine_iv_cost): Promote type of > cost computation to int64_t. > (determine_group_iv_costs, iv_ca_dump, find_optimal_iv_set): Use > int64_t's format specifier in dump. > > 2018-05-05 Bin Cheng <bin.cheng@linux.alibaba.com> > > PR tree-optimization/90078 > * g++.dg/tree-ssa/pr90078.C: New test. ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH PR90078]Capping comp_cost computation in ivopts 2019-05-06 10:11 ` Richard Biener @ 2019-05-06 10:24 ` Bin.Cheng 2019-05-06 10:27 ` Richard Biener 0 siblings, 1 reply; 8+ messages in thread From: Bin.Cheng @ 2019-05-06 10:24 UTC (permalink / raw) To: Richard Biener; +Cc: bin.cheng, Jakub Jelinek, GCC Patches On Mon, May 6, 2019 at 6:11 PM Richard Biener <richard.guenther@gmail.com> wrote: > > On Sun, May 5, 2019 at 8:03 AM bin.cheng <bin.cheng@linux.alibaba.com> wrote: > > > > > ------------------------------------------------------------------ > > > Sender:Jakub Jelinek <jakub@redhat.com> > > > Sent At:2019 Apr. 17 (Wed.) 19:27 > > > Recipient:Bin.Cheng <amker.cheng@gmail.com> > > > Cc:bin.cheng <bin.cheng@linux.alibaba.com>; GCC Patches <gcc-patches@gcc.gnu.org> > > > Subject:Re: [PATCH PR90078]Capping comp_cost computation in ivopts > > > > > > > > > On Wed, Apr 17, 2019 at 07:14:05PM +0800, Bin.Cheng wrote: > > > > > As > > > > > #define INFTY 10000000 > > > > > what is the reason to keep the previous condition as well? > > > > > I mean, if cost1.cost == INFTY or cost2.cost == INFTY, > > > > > cost1.cost + cost2.cost >= INFTY too. > > > > > Unless costs can go negative. > > > > It's a bit complicated, but in general, costs can go negative. > > > > > > Ok, no objections from me then (but as I don't know anything about it, > > > not an ack either; you are ivopts maintainer, so you don't need one). > > > > Hi, > > The previous patch was reverted on GCC-9 because of PR90240. PR90240 is now > > fixed by another patch. This is the updated patch for PR90078. It promotes type > > of ivopts cost from int to int64_t, as well as change behavior of infinite_cost overflow > > from saturation to assert. > > Please note, implicit conversions are kept in cost computation as before without > > introducing any narrowing. > > > > Bootstrap/test on x86_64 along with PR90240 patch. Is it OK? > > Do not include system headers in .c files, instead those need to be > (and are already) > included via system.h. > > /* The infinite cost. */ > -#define INFTY 10000000 > +#define INFTY 1000000000L > > do we actually need this? What happens on a ilp32 host? That is, I believe > you can drop the 'L' (it fits into an int anyways) Yeah, now I think if int64_t is necessary or not. With the scaling bound and assertions. > > @@ -256,6 +259,7 @@ operator- (comp_cost cost1, comp_cost cost2) > return infinite_cost; > > gcc_assert (!cost2.infinite_cost_p ()); > + gcc_assert (cost1.cost - cost2.cost < infinite_cost.cost); > > cost1.cost -= cost2.cost; > cost1.complexity -= cost2.complexity; > > probably a pre-existing issue, but we do not seem to handle underflow > here in general, nor check that underflow doesn't get us below -INFTY. > > I guess we really don't want negative costs? That doesn't seem to be > documented and I was also wondering why the cost isn't unsigned... > > @@ -638,7 +646,7 @@ struct iv_ca > comp_cost cand_use_cost; > > /* Total cost of candidates. */ > - unsigned cand_cost; > + int64_t cand_cost; > > /* Number of times each invariant variable is used. */ > unsigned *n_inv_var_uses; > > shows this "issue". Can't we use uint64_t throughout the patch? Oh, it's actually explained in previous message, https://gcc.gnu.org/ml/gcc-patches/2019-04/msg00697.html In short, yes the cost can be negative. The negative cost should be small in absolute value, and we don't check -INFTY. With the scaling bound change, I don't think -INFTY is possible IIUC. Thanks, bin > > Otherwise this looks OK. > > Thanks, > Richard. > > > Thanks, > > bin > > 2019-05-05 Bin Cheng <bin.cheng@linux.alibaba.com> > > > > PR tree-optimization/90078 > > * tree-ssa-loop-ivopts.c (inttypes.h): Include new header file. > > (INFTY): Increase the value for infinite cost. > > (struct comp_cost): Promote type of members to int64_t. > > (infinite_cost): Don't set complexity in initialization. > > (comp_cost::operator +,-,+=,-+,/=,*=): Assert when cost computation > > overflows to infinite_cost. > > (adjust_setup_cost): Promote type of parameter and cost computation > > to int64_t. > > (struct ainc_cost_data, struct iv_ca): Promote type of member to > > int64_t. > > (get_scaled_computation_cost_at, determine_iv_cost): Promote type of > > cost computation to int64_t. > > (determine_group_iv_costs, iv_ca_dump, find_optimal_iv_set): Use > > int64_t's format specifier in dump. > > > > 2018-05-05 Bin Cheng <bin.cheng@linux.alibaba.com> > > > > PR tree-optimization/90078 > > * g++.dg/tree-ssa/pr90078.C: New test. ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH PR90078]Capping comp_cost computation in ivopts 2019-05-06 10:24 ` Bin.Cheng @ 2019-05-06 10:27 ` Richard Biener 0 siblings, 0 replies; 8+ messages in thread From: Richard Biener @ 2019-05-06 10:27 UTC (permalink / raw) To: Bin.Cheng; +Cc: bin.cheng, Jakub Jelinek, GCC Patches On Mon, May 6, 2019 at 12:24 PM Bin.Cheng <amker.cheng@gmail.com> wrote: > > On Mon, May 6, 2019 at 6:11 PM Richard Biener > <richard.guenther@gmail.com> wrote: > > > > On Sun, May 5, 2019 at 8:03 AM bin.cheng <bin.cheng@linux.alibaba.com> wrote: > > > > > > > ------------------------------------------------------------------ > > > > Sender:Jakub Jelinek <jakub@redhat.com> > > > > Sent At:2019 Apr. 17 (Wed.) 19:27 > > > > Recipient:Bin.Cheng <amker.cheng@gmail.com> > > > > Cc:bin.cheng <bin.cheng@linux.alibaba.com>; GCC Patches <gcc-patches@gcc.gnu.org> > > > > Subject:Re: [PATCH PR90078]Capping comp_cost computation in ivopts > > > > > > > > > > > > On Wed, Apr 17, 2019 at 07:14:05PM +0800, Bin.Cheng wrote: > > > > > > As > > > > > > #define INFTY 10000000 > > > > > > what is the reason to keep the previous condition as well? > > > > > > I mean, if cost1.cost == INFTY or cost2.cost == INFTY, > > > > > > cost1.cost + cost2.cost >= INFTY too. > > > > > > Unless costs can go negative. > > > > > It's a bit complicated, but in general, costs can go negative. > > > > > > > > Ok, no objections from me then (but as I don't know anything about it, > > > > not an ack either; you are ivopts maintainer, so you don't need one). > > > > > > Hi, > > > The previous patch was reverted on GCC-9 because of PR90240. PR90240 is now > > > fixed by another patch. This is the updated patch for PR90078. It promotes type > > > of ivopts cost from int to int64_t, as well as change behavior of infinite_cost overflow > > > from saturation to assert. > > > Please note, implicit conversions are kept in cost computation as before without > > > introducing any narrowing. > > > > > > Bootstrap/test on x86_64 along with PR90240 patch. Is it OK? > > > > Do not include system headers in .c files, instead those need to be > > (and are already) > > included via system.h. > > > > /* The infinite cost. */ > > -#define INFTY 10000000 > > +#define INFTY 1000000000L > > > > do we actually need this? What happens on a ilp32 host? That is, I believe > > you can drop the 'L' (it fits into an int anyways) > Yeah, now I think if int64_t is necessary or not. With the scaling > bound and assertions. > > > > @@ -256,6 +259,7 @@ operator- (comp_cost cost1, comp_cost cost2) > > return infinite_cost; > > > > gcc_assert (!cost2.infinite_cost_p ()); > > + gcc_assert (cost1.cost - cost2.cost < infinite_cost.cost); > > > > cost1.cost -= cost2.cost; > > cost1.complexity -= cost2.complexity; > > > > probably a pre-existing issue, but we do not seem to handle underflow > > here in general, nor check that underflow doesn't get us below -INFTY. > > > > I guess we really don't want negative costs? That doesn't seem to be > > documented and I was also wondering why the cost isn't unsigned... > > > > @@ -638,7 +646,7 @@ struct iv_ca > > comp_cost cand_use_cost; > > > > /* Total cost of candidates. */ > > - unsigned cand_cost; > > + int64_t cand_cost; > > > > /* Number of times each invariant variable is used. */ > > unsigned *n_inv_var_uses; > > > > shows this "issue". Can't we use uint64_t throughout the patch? > Oh, it's actually explained in previous message, > https://gcc.gnu.org/ml/gcc-patches/2019-04/msg00697.html > In short, yes the cost can be negative. The negative cost should be > small in absolute value, and we don't check -INFTY. With the scaling > bound change, I don't think -INFTY is possible IIUC. Ah, I see. The patch is OK then with 1000000000L in the #define changed to just 1000000000 Richard. > Thanks, > bin > > > > Otherwise this looks OK. > > > > Thanks, > > Richard. > > > > > Thanks, > > > bin > > > 2019-05-05 Bin Cheng <bin.cheng@linux.alibaba.com> > > > > > > PR tree-optimization/90078 > > > * tree-ssa-loop-ivopts.c (inttypes.h): Include new header file. > > > (INFTY): Increase the value for infinite cost. > > > (struct comp_cost): Promote type of members to int64_t. > > > (infinite_cost): Don't set complexity in initialization. > > > (comp_cost::operator +,-,+=,-+,/=,*=): Assert when cost computation > > > overflows to infinite_cost. > > > (adjust_setup_cost): Promote type of parameter and cost computation > > > to int64_t. > > > (struct ainc_cost_data, struct iv_ca): Promote type of member to > > > int64_t. > > > (get_scaled_computation_cost_at, determine_iv_cost): Promote type of > > > cost computation to int64_t. > > > (determine_group_iv_costs, iv_ca_dump, find_optimal_iv_set): Use > > > int64_t's format specifier in dump. > > > > > > 2018-05-05 Bin Cheng <bin.cheng@linux.alibaba.com> > > > > > > PR tree-optimization/90078 > > > * g++.dg/tree-ssa/pr90078.C: New test. ^ permalink raw reply [flat|nested] 8+ messages in thread
end of thread, other threads:[~2019-05-06 10:27 UTC | newest] Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2019-04-17 7:00 [PATCH PR90078]Capping comp_cost computation in ivopts bin.cheng 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
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).