[Polly] Fix long loop due to unsigned warparound.

Meinersbur · Meinersbur · commit 1ef55ac96e9d · 2020-04-27T12:15:56.000-05:00
After the update to ISL to isl-0.22.1-87-gfee05a13 and its change of
isl_*_dim returning -1 instead of 0, the -1 got wrapped-around to
UINT_MAX because Polly often uses 'unsigned' type to represent
dimensions, as ISL did before this patch. This may happen in normal
executions after an out-of-quota.

Fix by catching the error-case earlier.
diff --git a/polly/lib/Support/ISLTools.cpp b/polly/lib/Support/ISLTools.cpp
@@ -159,8 +159,13 @@ isl::set polly::singleton(isl::union_set USet, isl::space ExpectedSpace) {
 
 unsigned polly::getNumScatterDims(const isl::union_map &Schedule) {
   unsigned Dims = 0;
-  for (isl::map Map : Schedule.get_map_list())
+  for (isl::map Map : Schedule.get_map_list()) {
+    // Map.dim would return UINT_MAX.
+    if (!Map)
+      continue;
+
     Dims = std::max(Dims, Map.dim(isl::dim::out));
+  }
   return Dims;
 }
 
@@ -435,11 +440,17 @@ isl::map polly::distributeDomain(isl::map Map) {
 
   isl::space Space = Map.get_space();
   isl::space DomainSpace = Space.domain();
+  if (!DomainSpace)
+    return {};
   unsigned DomainDims = DomainSpace.dim(isl::dim::set);
   isl::space RangeSpace = Space.range().unwrap();
   isl::space Range1Space = RangeSpace.domain();
+  if (!Range1Space)
+    return {};
   unsigned Range1Dims = Range1Space.dim(isl::dim::set);
   isl::space Range2Space = RangeSpace.range();
+  if (!Range2Space)
+    return {};
   unsigned Range2Dims = Range2Space.dim(isl::dim::set);
 
   isl::space OutputSpace =
@@ -578,6 +589,10 @@ static void foreachPoint(isl::basic_set BSet,
 /// Ordering is based on the lower bounds of the set's dimensions. First
 /// dimensions are considered first.
 static int flatCompare(const isl::basic_set &A, const isl::basic_set &B) {
+  // Quick bail-out on out-of-quota.
+  if (!A || !B)
+    return 0;
+
   unsigned ALen = A.dim(isl::dim::set);
   unsigned BLen = B.dim(isl::dim::set);
   unsigned Len = std::min(ALen, BLen);
diff --git a/polly/test/ForwardOpTree/out-of-quota1.ll b/polly/test/ForwardOpTree/out-of-quota1.ll
@@ -0,0 +1,59 @@
+; RUN: opt %loadPolly -polly-optree -analyze %s | FileCheck %s
+
+; This used to loop infinitely because of UINT_MAX returned by ISL on out-of-quota.
+
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+
+%struct.storable_picture.5.221.389.509.629.797.917.1133.1205.1445.1469.1517.1541.1565.1589.1661.1685.1757.1781.1829.1877.2165.2285.2405.2429.2453.2477.2501.2525.2837.2861.2885.2909.4417.1.7.13.17.23.29.55.57.59.61.187 = type { i32, i32, i32, i32, i32, [50 x [6 x [33 x i64]]], [50 x [6 x [33 x i64]]], [50 x [6 x [33 x i64]]], [50 x [6 x [33 x i64]]], i32, i32, i32, i32, i32, i32, i32, i32, i32, i16, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i16**, i16***, i8*, i16**, i8***, i64***, i64***, i16****, i8**, i8**, %struct.storable_picture.5.221.389.509.629.797.917.1133.1205.1445.1469.1517.1541.1565.1589.1661.1685.1757.1781.1829.1877.2165.2285.2405.2429.2453.2477.2501.2525.2837.2861.2885.2909.4417.1.7.13.17.23.29.55.57.59.61.187*, %struct.storable_picture.5.221.389.509.629.797.917.1133.1205.1445.1469.1517.1541.1565.1589.1661.1685.1757.1781.1829.1877.2165.2285.2405.2429.2453.2477.2501.2525.2837.2861.2885.2909.4417.1.7.13.17.23.29.55.57.59.61.187*, %struct.storable_picture.5.221.389.509.629.797.917.1133.1205.1445.1469.1517.1541.1565.1589.1661.1685.1757.1781.1829.1877.2165.2285.2405.2429.2453.2477.2501.2525.2837.2861.2885.2909.4417.1.7.13.17.23.29.55.57.59.61.187*, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, [2 x i32], i32, %struct.DecRefPicMarking_s.4.220.388.508.628.796.916.1132.1204.1444.1468.1516.1540.1564.1588.1660.1684.1756.1780.1828.1876.2164.2284.2404.2428.2452.2476.2500.2524.2836.2860.2884.2908.4416.0.6.12.16.22.28.54.56.58.60.186*, i32 }
+%struct.DecRefPicMarking_s.4.220.388.508.628.796.916.1132.1204.1444.1468.1516.1540.1564.1588.1660.1684.1756.1780.1828.1876.2164.2284.2404.2428.2452.2476.2500.2524.2836.2860.2884.2908.4416.0.6.12.16.22.28.54.56.58.60.186 = type { i32, i32, i32, i32, i32, %struct.DecRefPicMarking_s.4.220.388.508.628.796.916.1132.1204.1444.1468.1516.1540.1564.1588.1660.1684.1756.1780.1828.1876.2164.2284.2404.2428.2452.2476.2500.2524.2836.2860.2884.2908.4416.0.6.12.16.22.28.54.56.58.60.186* }
+
+define void @func() {
+entry:
+  %0 = load %struct.storable_picture.5.221.389.509.629.797.917.1133.1205.1445.1469.1517.1541.1565.1589.1661.1685.1757.1781.1829.1877.2165.2285.2405.2429.2453.2477.2501.2525.2837.2861.2885.2909.4417.1.7.13.17.23.29.55.57.59.61.187*, %struct.storable_picture.5.221.389.509.629.797.917.1133.1205.1445.1469.1517.1541.1565.1589.1661.1685.1757.1781.1829.1877.2165.2285.2405.2429.2453.2477.2501.2525.2837.2861.2885.2909.4417.1.7.13.17.23.29.55.57.59.61.187** undef, align 8
+  %1 = load %struct.storable_picture.5.221.389.509.629.797.917.1133.1205.1445.1469.1517.1541.1565.1589.1661.1685.1757.1781.1829.1877.2165.2285.2405.2429.2453.2477.2501.2525.2837.2861.2885.2909.4417.1.7.13.17.23.29.55.57.59.61.187*, %struct.storable_picture.5.221.389.509.629.797.917.1133.1205.1445.1469.1517.1541.1565.1589.1661.1685.1757.1781.1829.1877.2165.2285.2405.2429.2453.2477.2501.2525.2837.2861.2885.2909.4417.1.7.13.17.23.29.55.57.59.61.187** undef, align 8
+  %2 = load %struct.storable_picture.5.221.389.509.629.797.917.1133.1205.1445.1469.1517.1541.1565.1589.1661.1685.1757.1781.1829.1877.2165.2285.2405.2429.2453.2477.2501.2525.2837.2861.2885.2909.4417.1.7.13.17.23.29.55.57.59.61.187*, %struct.storable_picture.5.221.389.509.629.797.917.1133.1205.1445.1469.1517.1541.1565.1589.1661.1685.1757.1781.1829.1877.2165.2285.2405.2429.2453.2477.2501.2525.2837.2861.2885.2909.4417.1.7.13.17.23.29.55.57.59.61.187** undef, align 8
+  %3 = load i16, i16* undef, align 4
+  %conv2081956 = zext i16 %3 to i64
+  br label %for.cond212.preheader
+
+for.cond212.preheader:
+  %indvars.iv1926 = phi i64 [ %indvars.iv.next1927, %for.inc354 ], [ 0, %entry ]
+  br label %for.body215
+
+for.body215:
+  %indvars.iv1921 = phi i64 [ 0, %for.cond212.preheader ], [ %indvars.iv.next1922, %for.body215 ]
+  %4 = shl nuw nsw i64 %indvars.iv1921, 1
+  %arrayidx230 = getelementptr inbounds %struct.storable_picture.5.221.389.509.629.797.917.1133.1205.1445.1469.1517.1541.1565.1589.1661.1685.1757.1781.1829.1877.2165.2285.2405.2429.2453.2477.2501.2525.2837.2861.2885.2909.4417.1.7.13.17.23.29.55.57.59.61.187, %struct.storable_picture.5.221.389.509.629.797.917.1133.1205.1445.1469.1517.1541.1565.1589.1661.1685.1757.1781.1829.1877.2165.2285.2405.2429.2453.2477.2501.2525.2837.2861.2885.2909.4417.1.7.13.17.23.29.55.57.59.61.187* %1, i64 0, i32 5, i64 %indvars.iv1926, i64 1, i64 %4
+  store i64 undef, i64* %arrayidx230, align 8
+  %5 = or i64 %4, 1
+  %arrayidx248 = getelementptr inbounds %struct.storable_picture.5.221.389.509.629.797.917.1133.1205.1445.1469.1517.1541.1565.1589.1661.1685.1757.1781.1829.1877.2165.2285.2405.2429.2453.2477.2501.2525.2837.2861.2885.2909.4417.1.7.13.17.23.29.55.57.59.61.187, %struct.storable_picture.5.221.389.509.629.797.917.1133.1205.1445.1469.1517.1541.1565.1589.1661.1685.1757.1781.1829.1877.2165.2285.2405.2429.2453.2477.2501.2525.2837.2861.2885.2909.4417.1.7.13.17.23.29.55.57.59.61.187* %1, i64 0, i32 5, i64 %indvars.iv1926, i64 1, i64 %5
+  store i64 undef, i64* %arrayidx248, align 8
+  %arrayidx264 = getelementptr inbounds %struct.storable_picture.5.221.389.509.629.797.917.1133.1205.1445.1469.1517.1541.1565.1589.1661.1685.1757.1781.1829.1877.2165.2285.2405.2429.2453.2477.2501.2525.2837.2861.2885.2909.4417.1.7.13.17.23.29.55.57.59.61.187, %struct.storable_picture.5.221.389.509.629.797.917.1133.1205.1445.1469.1517.1541.1565.1589.1661.1685.1757.1781.1829.1877.2165.2285.2405.2429.2453.2477.2501.2525.2837.2861.2885.2909.4417.1.7.13.17.23.29.55.57.59.61.187* %2, i64 0, i32 5, i64 %indvars.iv1926, i64 1, i64 %4
+  store i64 undef, i64* %arrayidx264, align 8
+  %arrayidx282 = getelementptr inbounds %struct.storable_picture.5.221.389.509.629.797.917.1133.1205.1445.1469.1517.1541.1565.1589.1661.1685.1757.1781.1829.1877.2165.2285.2405.2429.2453.2477.2501.2525.2837.2861.2885.2909.4417.1.7.13.17.23.29.55.57.59.61.187, %struct.storable_picture.5.221.389.509.629.797.917.1133.1205.1445.1469.1517.1541.1565.1589.1661.1685.1757.1781.1829.1877.2165.2285.2405.2429.2453.2477.2501.2525.2837.2861.2885.2909.4417.1.7.13.17.23.29.55.57.59.61.187* %2, i64 0, i32 5, i64 %indvars.iv1926, i64 1, i64 %5
+  store i64 undef, i64* %arrayidx282, align 8
+  %arrayidx298 = getelementptr inbounds %struct.storable_picture.5.221.389.509.629.797.917.1133.1205.1445.1469.1517.1541.1565.1589.1661.1685.1757.1781.1829.1877.2165.2285.2405.2429.2453.2477.2501.2525.2837.2861.2885.2909.4417.1.7.13.17.23.29.55.57.59.61.187, %struct.storable_picture.5.221.389.509.629.797.917.1133.1205.1445.1469.1517.1541.1565.1589.1661.1685.1757.1781.1829.1877.2165.2285.2405.2429.2453.2477.2501.2525.2837.2861.2885.2909.4417.1.7.13.17.23.29.55.57.59.61.187* %1, i64 0, i32 5, i64 %indvars.iv1926, i64 0, i64 %4
+  store i64 undef, i64* %arrayidx298, align 8
+  %arrayidx307 = getelementptr inbounds %struct.storable_picture.5.221.389.509.629.797.917.1133.1205.1445.1469.1517.1541.1565.1589.1661.1685.1757.1781.1829.1877.2165.2285.2405.2429.2453.2477.2501.2525.2837.2861.2885.2909.4417.1.7.13.17.23.29.55.57.59.61.187, %struct.storable_picture.5.221.389.509.629.797.917.1133.1205.1445.1469.1517.1541.1565.1589.1661.1685.1757.1781.1829.1877.2165.2285.2405.2429.2453.2477.2501.2525.2837.2861.2885.2909.4417.1.7.13.17.23.29.55.57.59.61.187* %0, i64 0, i32 5, i64 %indvars.iv1926, i64 2, i64 %5
+  %6 = load i64, i64* %arrayidx307, align 8
+  %arrayidx316 = getelementptr inbounds %struct.storable_picture.5.221.389.509.629.797.917.1133.1205.1445.1469.1517.1541.1565.1589.1661.1685.1757.1781.1829.1877.2165.2285.2405.2429.2453.2477.2501.2525.2837.2861.2885.2909.4417.1.7.13.17.23.29.55.57.59.61.187, %struct.storable_picture.5.221.389.509.629.797.917.1133.1205.1445.1469.1517.1541.1565.1589.1661.1685.1757.1781.1829.1877.2165.2285.2405.2429.2453.2477.2501.2525.2837.2861.2885.2909.4417.1.7.13.17.23.29.55.57.59.61.187* %1, i64 0, i32 5, i64 %indvars.iv1926, i64 0, i64 %5
+  store i64 %6, i64* %arrayidx316, align 8
+  %arrayidx332 = getelementptr inbounds %struct.storable_picture.5.221.389.509.629.797.917.1133.1205.1445.1469.1517.1541.1565.1589.1661.1685.1757.1781.1829.1877.2165.2285.2405.2429.2453.2477.2501.2525.2837.2861.2885.2909.4417.1.7.13.17.23.29.55.57.59.61.187, %struct.storable_picture.5.221.389.509.629.797.917.1133.1205.1445.1469.1517.1541.1565.1589.1661.1685.1757.1781.1829.1877.2165.2285.2405.2429.2453.2477.2501.2525.2837.2861.2885.2909.4417.1.7.13.17.23.29.55.57.59.61.187* %2, i64 0, i32 5, i64 %indvars.iv1926, i64 0, i64 %4
+  store i64 undef, i64* %arrayidx332, align 8
+  %arrayidx350 = getelementptr inbounds %struct.storable_picture.5.221.389.509.629.797.917.1133.1205.1445.1469.1517.1541.1565.1589.1661.1685.1757.1781.1829.1877.2165.2285.2405.2429.2453.2477.2501.2525.2837.2861.2885.2909.4417.1.7.13.17.23.29.55.57.59.61.187, %struct.storable_picture.5.221.389.509.629.797.917.1133.1205.1445.1469.1517.1541.1565.1589.1661.1685.1757.1781.1829.1877.2165.2285.2405.2429.2453.2477.2501.2525.2837.2861.2885.2909.4417.1.7.13.17.23.29.55.57.59.61.187* %2, i64 0, i32 5, i64 %indvars.iv1926, i64 0, i64 %5
+  store i64 undef, i64* %arrayidx350, align 8
+  %indvars.iv.next1922 = add nuw nsw i64 %indvars.iv1921, 1
+  %exitcond1925 = icmp eq i64 %indvars.iv.next1922, 16
+  br i1 %exitcond1925, label %for.inc354, label %for.body215
+
+for.inc354:
+  %indvars.iv.next1927 = add nuw nsw i64 %indvars.iv1926, 1
+  %exitcond1930 = icmp eq i64 %indvars.iv1926, %conv2081956
+  br i1 %exitcond1930, label %for.body930, label %for.cond212.preheader
+
+for.body930:
+  br label %for.body930
+}
+
+
+; CHECK: ForwardOpTree executed, but did not modify anything
