[Polly] Understand performance overhead of isl hybrid small-integer optimization

[Quuxplusone]

Bugzilla Link	PR23887
Status	NEW
Importance	P normal
Reported by	Tobias Grosser (tobias@grosser.es)
Reported on	2015-06-18 16:52:23 -0700
Last modified on	2016-01-18 16:50:59 -0800
Version	unspecified
Hardware	PC Linux
CC	llvm-bugs@lists.llvm.org
Fixed by commit(s)
Attachments	0001-use-ONLY-32bit-integers.patch (3785 bytes, text/plain)
Blocks	PR23885
Blocked by
See also

Created attachment 14493
use only 32 bit integers

In r240027 a new small-integer optimization has been comitted to Polly, where
all isl_int computations are using a hybrid data-type that is either a 32-bit
integer (common case) or an imath integer.

Even though this already gives nice speedups, it would be interesting to see if
there is anything left to gain compared to plain int32 integers.

We attach a patch that allows us to use int32_t [1]. Running this on polybench-
c-3.2's 3mm, we get the
following speedup:

sio-imath:

$time polly-clang-opt linear-algebra/kernels/3mm/3mm.c -I utilities/ -O3 -mllvm
-polly  -mllvm -polly-dependences-computeout=0  -c -mllvm -polly-ignore-aliasing

real    0m0.344s
user    0m0.340s
sys 0m0.004s

int32_t:

$time polly-clang-opt linear-algebra/kernels/3mm/3mm.c -I utilities/ -O3 -mllvm
-polly  -mllvm -polly-dependences-computeout=0  -c -mllvm -polly-ignore-aliasing

real    0m0.296s
user    0m0.285s
sys 0m0.011s

For 3mm this shows there is still some scope for improvement. 3mm may be a
special case as we currently
generate a rather complicated context object that may require many isl
operations. As this also slows down
the alias-run-time checks, we disabled them in the above performance run. We
should probably run this patch on a larger set of tests (LLVM test suite?) to
get some more data. Also. it is unclear if there are still some low-hanging
fruits.

[1] For this to work we need to enable sio-imath (patch pending) and we need to
ensure we do not create large integers:

index 0e7527e..6203792 100644
--- a/lib/Analysis/ScopInfo.cpp
+++ b/lib/Analysis/ScopInfo.cpp
@@ -573,8 +573,8 @@ void MemoryAccess::computeBoundsOnAccessRelation(unsigned
ElementSize) {
   auto Max = (UB - APInt(BW, 1)).sdiv(APInt(BW, ElementSize));

   isl_set *AccessRange = isl_map_range(isl_map_copy(AccessRelation));
-  AccessRange =
-      addRangeBoundsToSet(AccessRange, ConstantRange(Min, Max), 0,
isl_dim_set);
+  //AccessRange =
+  //    addRangeBoundsToSet(AccessRange, ConstantRange(Min, Max), 0,
isl_dim_set);
   AccessRelation = isl_map_intersect_range(AccessRelation, AccessRange);
 }

@@ -1332,7 +1332,7 @@ void Scop::addParameterBounds() {

     ConstantRange SRange = SE->getSignedRange(ParamID.first);

-    Context = addRangeBoundsToSet(Context, SRange, dim, isl_dim_param);
+    //Context = addRangeBoundsToSet(Context, SRange, dim, isl_dim_param);

[Quuxplusone]

Attached 0001-use-ONLY-32bit-integers.patch (3785 bytes, text/plain): use only 32 bit integers

[Quuxplusone]

Move bugs to Polly product.