Index: lib/Analysis/DependenceInfo.cpp
===================================================================
--- lib/Analysis/DependenceInfo.cpp
+++ lib/Analysis/DependenceInfo.cpp
@@ -774,6 +774,94 @@
   return IsValid;
 }
 
+// Find the maximum number of input or output dimensions among all isl_maps
+// in a isl_union_map. Used as a callback for isl_union_map_foreach_map.
+// @see unifyDepsMap
+static isl_stat findMaxDimsCount(__isl_take isl_map *map, void *user) {
+  assert(user && "Expected valid pointer to store max dimension count.");
+  unsigned *Maxdims = (unsigned *)user;
+
+  unsigned NInDims = isl_map_dim(map, isl_dim_in);
+  unsigned NOutDims = isl_map_dim(map, isl_dim_out);
+  isl_map_free(map);
+
+  *Maxdims = std::max(*Maxdims, NInDims);
+  *Maxdims = std::max(*Maxdims, NOutDims);
+
+  return isl_stat_ok;
+}
+
+// Helper struct used to store information used by
+// appendInputDimsAndUnion.
+// @see appendInputDimsAndUnion
+struct AlignInputsMapInfo {
+  // Number of input & dimensions that is expected for an isl_map;
+  unsigned NExpectedDims;
+
+  // Final isl_union_map that is a concatenation of all the isl_maps
+  // appendInputDimsAndUnion is run on.
+  isl_union_map *out;
+
+  AlignInputsMapInfo() : NExpectedDims(0), out(nullptr){};
+};
+
+// Pad each isl_map with dimensions such that they all have the
+// same number of input & output dimensions. Used as callback for
+// isl_union_map_foreach_map.
+// @see unifyDepsMap
+static isl_stat appendInputDimsAndUnion(__isl_take isl_map *map, void *user) {
+  AlignInputsMapInfo *info = (AlignInputsMapInfo *)(user);
+  assert(info && "expected valid user pointer");
+
+  unsigned InN = isl_map_dim(map, isl_dim_in);
+  unsigned OutN = isl_map_dim(map, isl_dim_out);
+
+  assert(
+      InN <= info->NExpectedDims &&
+      "Found map with more than maximum number of expected input dimensions.");
+
+  assert(
+      OutN <= info->NExpectedDims &&
+      "Found map with more than maximum number of expected output dimensions.");
+
+  // TODO: I don't fully understand the implications of doing this,
+  // since isl_map_add_dims flattens the map. However, I believe that it
+  // is okay to flatten dependences over a schedule.
+  map = isl_map_add_dims(map, isl_dim_in, info->NExpectedDims - InN);
+  map = isl_map_add_dims(map, isl_dim_out, info->NExpectedDims - OutN);
+
+  if (!info->out)
+    info->out = isl_union_map_from_map(map);
+  else
+    info->out = isl_union_map_union(info->out, isl_union_map_from_map(map));
+
+  return isl_stat_ok;
+}
+
+// The isl_maps that comprise of the Deps may have different dimensions
+// per isl_map. We need to force them to have the same number of dimensions
+// since we wish to unify this into an isl_map. So, we figure out what
+// the maximum number of dimensions are, and we pad each isl_map's input
+// and output dimensions to be the same number throughout the isl_union_map.
+//
+// We expect that the number of input and output dimensions for each map in Deps
+// to be equal, since they represent dependences.
+//
+// Postcondition:
+//    forall m, n \in out,
+//      dim_in(n) = dim_in(m) = dim_out(n) = dim_out(m)
+// @see Dependences::isParallel
+static isl_map *unifyDepsMap(isl_union_map *Deps) {
+  AlignInputsMapInfo info;
+  isl_union_map_foreach_map(Deps, &findMaxDimsCount, &info.NExpectedDims);
+
+  isl_union_map_foreach_map(Deps, &appendInputDimsAndUnion, &info);
+  isl_union_map_free(Deps);
+  Deps = info.out;
+
+  return isl_map_from_union_map(Deps);
+}
+
 // Check if the current scheduling dimension is parallel.
 //
 // We check for parallelism by verifying that the loop does not carry any
@@ -802,7 +890,7 @@
     return true;
   }
 
-  ScheduleDeps = isl_map_from_union_map(Deps);
+  ScheduleDeps = unifyDepsMap(Deps);
   Dimension = isl_map_dim(ScheduleDeps, isl_dim_out) - 1;
 
   for (unsigned i = 0; i < Dimension; i++)
Index: test/DependenceInfo/is_parallel_irregular_deps.ll
===================================================================
--- /dev/null
+++ test/DependenceInfo/is_parallel_irregular_deps.ll
@@ -0,0 +1,49 @@
+; This contains dependences which do not generate the same space
+; when called with -poyhedral-info. This tests that we unify these
+; correctly, and not crash by calling isl_map_from_union_map directly.
+
+
+; RUN: opt %loadPolly -polyhedral-info -polly-check-parallel -analyze %s
+
+; static const int N = 200;
+; 
+; void crash(int A[N]) {
+;   int i = 0, j = 0;
+;   for (i = 0; i < N; i++) {
+;       A[i] = 0;
+; 
+;     for (j = 0; j < N; j++)
+;         A[j] = 42;
+;   }
+; }
+  
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.11.0"
+
+define void @crash(i32* %A) {
+entry.split:
+  br label %for.body
+ 
+for.body:                                         ; preds =  %for.inc
+  %indvars.iv3 = phi i64 [ 0, %entry.split ], [ %indvars.iv.next4, %for.inc ]
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv3
+  store i32 0, i32* %arrayidx, align 4
+  br label %for.body.inner
+
+for.body.inner:                                        ; preds = %for.body, %for.body.inner
+  %indvars.iv = phi i64 [ 0, %for.body ], [ %indvars.iv.next, %for.body.inner ]
+  %arrayidx5 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  store i32 42, i32* %arrayidx5, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp ne i64 %indvars.iv.next, 200
+  br i1 %exitcond, label %for.body.inner, label %for.inc
+
+for.inc:                                         ; preds = %for.body.inner
+  %indvars.iv.next4 = add nuw nsw i64 %indvars.iv3, 1
+  %exitcond5 = icmp ne i64 %indvars.iv.next4, 200
+  br i1 %exitcond5, label %for.body, label %for.end
+
+for.end:                                         ; preds = %for.inc
+  ret void
+}