[Polly] [WIP] Adding Live-Range Reordering for Polly

[alexsusu]

Summary

Added Live-Range Reordering (LRR) for Polly.
To build this feature one needs to give (to build also PPCG with Polly):
    cmake -DPOLLY_ENABLE_GPGPU_CODEGEN=On ...

I got inspired heavily from llvm/tools/polly/lib/CodeGen/PPCGCodeGeneration.cpp - I duplicated the code existing there.
Basically what I did was to:
  - use from PPCGCodeGeneration.cpp method PPCGCodeGeneration::createPPCGScop() to initialize the maps containing the dependence analysis data;
  - implement in IslScheduleOptimizer::runOnScop(Scop &S) a good part of the construct_cpu_schedule_constraints() function from PPCG's cpu.c to compute the LRR constraints.

[Meinersbur]

Hi Alex,

thanks for the work, your experiments sound very promising. In any case, test cases would be needed.

Michael

lib/Transform/ScheduleOptimizer.cpp

97–103

Would it be possible to not require any part of ppcg? We only require a small part of it (the live-range reordering), having coupling with ppcg should not be necessary.

[bollu]

Thanks a lot for the patch! I took a shot at a first round of review :) I can be nitpicky, so we can hash out the details as we go along with the review.

lib/Transform/ScheduleOptimizer.cpp

391

Can we refactor this stuff to prevent code duplication between this and PPCGCodeGen?

411

Can we pull this out as well to prevent code duplication?

1923

I am wary of global mutable state. Can we try to refactor this so that we don't need it?

2100

Nit: prefer if(!LiveRangeReordering)

2113

From what I can tell, this object is a ScopPass to maintain the same interface? I would much rather it not be a class, and more importantly, not a ScopPass, because it's really not a pass :)

I'd also prefer it to not even exist. Rather, we can just have a function called ppcg_scop createPPCGScop(const Scop &S) or something like that.

2162

This seems quite error prone. Can we use a unique_ptr<ppcg_obj, (custom deallocator)> to free this safely?

[Meinersbur]

@bollu Alex added the code duplication because I suggested him to do so. IMHO the live-range reordering should not depend on ppcg at all. ppcg is not written as a library so in terms of software quality, we should not use it as one. On the llvm mailing list we currently discuss the inclusion of isl. I don't think we will not do the same for ppcg, meaning that if live-range reordering depends on it, we would have to remove it again should Polly be included into LLVM main.

lib/Transform/ScheduleOptimizer.cpp

1923–1924

Agreed, we should not use global state if avoidable. It is problematic if Polly is used as a library.

[bollu]

@Meinersbur I agree. However, I don't think that this is the right place for the code either. It is more a DependenceInfo thing, and maybe it makes sense to teach DependenceInfo to generate this information for us?

[Meinersbur]

@bollu I agree DependenceInfo would be a good place to compute the conditional dependencies. However, as long we don't have another consumer for this data, it doesn't seem important to me.

lib/Transform/ScheduleOptimizer.cpp

 #include <string>
 #include <vector>
 
 using namespace llvm;
 using namespace polly;
 
 #define DEBUG_TYPE "polly-opt-isl"
 
+
+
+
+// Inspired directly from PPCGCodeGeneration.cpp
+
+#include "polly/ScopInfo.h"
+#include "isl/union_map.h"
+
+extern "C" {
+#include "ppcg/cuda.h"
+#include "ppcg/gpu.h"
+#include "ppcg/gpu_print.h"
+#include "ppcg/ppcg.h"
+#include "ppcg/schedule.h"
+}
+
+using namespace polly;
+using namespace llvm;
+
+
+
 static cl::opt<std::string>
     OptimizeDeps("polly-opt-optimize-only",
                  cl::desc("Only a certain kind of dependences (all/raw)"),
                  cl::Hidden, cl::init("all"), cl::ZeroOrMore,
                  cl::cat(PollyCategory));
 
 static cl::opt<std::string>
     SimplifyDeps("polly-opt-simplify-deps",

 
 static cl::opt<bool> OptimizedScops(
     "polly-optimized-scops",
     cl::desc("Polly - Dump polyhedral description of Scops optimized with "
              "the isl scheduling optimizer and the set of post-scheduling "
              "transformations is applied on the schedule tree"),
     cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
 
+// (The name of the option is inspired from PPCG: see e.g. file polly/lib/External/ppcg/ppcg_options.c)
+static cl::opt<bool> LiveRangeReordering(
+    "polly-live-range-reordering",
+    cl::desc("Polly - Perform live range reordering (similar to PPCG) "
+             "to allow successive live ranges on the same memory element to be reordered. "
+             "(in order to avoid serializing the successive uses of memory. "
+             "This can allow tiling and parallelizing.)"),
+    cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
+
+
+
 STATISTIC(ScopsProcessed, "Number of scops processed");
 STATISTIC(ScopsRescheduled, "Number of scops rescheduled");
 STATISTIC(ScopsOptimized, "Number of scops optimized");
 
 STATISTIC(NumAffineLoopsOptimized, "Number of affine loops optimized");
 STATISTIC(NumBoxedLoopsOptimized, "Number of boxed loops optimized");
 
 #define THREE_STATISTICS(VARNAME, DESC)                                        \

 
 STATISTIC(FirstLevelTileOpts, "Number of first level tiling applied");
 STATISTIC(SecondLevelTileOpts, "Number of second level tiling applied");
 STATISTIC(RegisterTileOpts, "Number of register tiling applied");
 STATISTIC(PrevectOpts, "Number of strip-mining for prevectorization applied");
 STATISTIC(MatMulOpts,
           "Number of matrix multiplication patterns detected and optimized");
 
+
+
+
+
+
+
+
+// Alex: making cl::opt from PPCGCodeGeneration.cpp simple vars:
+bool DumpSchedule = false;
+bool DumpCode = false;
+bool DumpKernelIR = false;
+bool DumpKernelASM = false;
+bool FastMath = false;
+bool SharedMemory = false;
+bool PrivateMemory = false;
+
+
+/// Used to store information PPCG wants for kills. This information is
+/// used by live range reordering.
+///
+/// @see computeLiveRangeReordering
+/// @see GPUNodeBuilder::createPPCGScop
+/// @see GPUNodeBuilder::createPPCGProg
+struct MustKillsInfo {
+  /// Collection of all kill statements that will be sequenced at the end of
+  /// PPCGScop->schedule.
+  ///
+  /// The nodes in `KillsSchedule` will be merged using `isl_schedule_set`
+  /// which merges schedules in *arbitrary* order.
+  /// (we don't care about the order of the kills anyway).
+  isl::schedule KillsSchedule;
+  /// Map from kill statement instances to scalars that need to be
+  /// killed.
+  ///
+  /// We currently derive kill information for:
+  ///  1. phi nodes. PHI nodes are not alive outside the scop and can
+  ///     consequently all be killed.
+  ///  2. Scalar arrays that are not used outside the Scop. This is
+  ///     checked by `isScalarUsesContainedInScop`.
+  /// [params] -> { [Stmt_phantom[] -> ref_phantom[]] -> scalar_to_kill[] }
+  isl::union_map TaggedMustKills;
+
+  /// Tagged must kills stripped of the tags.
+  /// [params] -> { Stmt_phantom[]  -> scalar_to_kill[] }
+  isl::union_map MustKills;
+
+  MustKillsInfo() : KillsSchedule(nullptr) {}
+};
+
+
+
+
+
+/// Check if SAI's uses are entirely contained within Scop S.
+/// If a scalar is used only with a Scop, we are free to kill it, as no data
+/// can flow in/out of the value any more.
+/// @see computeMustKillsInfo
+static bool isScalarUsesContainedInScop(const Scop &S,
+                                        const ScopArrayInfo *SAI) {
+  assert(SAI->isValueKind() && "this function only deals with scalars."
+                               " Dealing with arrays required alias analysis");
+
+  const Region &R = S.getRegion();
+  for (User *U : SAI->getBasePtr()->users()) {
+    Instruction *I = dyn_cast<Instruction>(U);
+    assert(I && "invalid user of scop array info");
+    if (!R.contains(I))
+      return false;
+  }
+  return true;
+}
+
+/// Compute must-kills needed to enable live range reordering with PPCG.
+///
+/// @params S The Scop to compute live range reordering information
+/// @returns live range reordering information that can be used to setup
+/// PPCG.
+static MustKillsInfo computeMustKillsInfo(const Scop &S) {
+  const isl::space ParamSpace = S.getParamSpace();
+  MustKillsInfo Info;
+
+  // 1. Collect all ScopArrayInfo that satisfy *any* of the criteria:
+  //      1.1 phi nodes in scop.
+  //      1.2 scalars that are only used within the scop
+  SmallVector<isl::id, 4> KillMemIds;
+  for (ScopArrayInfo *SAI : S.arrays()) {
+    if (SAI->isPHIKind() ||
+        (SAI->isValueKind() && isScalarUsesContainedInScop(S, SAI)))
+      KillMemIds.push_back(isl::manage(SAI->getBasePtrId().release()));
+  }
+
+  Info.TaggedMustKills = isl::union_map::empty(ParamSpace);
+  Info.MustKills = isl::union_map::empty(ParamSpace);
+
+  // Initialising KillsSchedule to `isl_set_empty` creates an empty node in the
+  // schedule:
+  //     - filter: "[control] -> { }"
+  // So, we choose to not create this to keep the output a little nicer,
+  // at the cost of some code complexity.
+  Info.KillsSchedule = nullptr;
+
+  for (isl::id &ToKillId : KillMemIds) {
+    isl::id KillStmtId = isl::id::alloc(
+        S.getIslCtx(),
+        std::string("SKill_phantom_").append(ToKillId.get_name()), nullptr);
+
+    // NOTE: construction of tagged_must_kill:
+    // 2. We need to construct a map:
+    //     [param] -> { [Stmt_phantom[] -> ref_phantom[]] -> scalar_to_kill[] }
+    // To construct this, we use `isl_map_domain_product` on 2 maps`:
+    // 2a. StmtToScalar:
+    //         [param] -> { Stmt_phantom[] -> scalar_to_kill[] }
+    // 2b. PhantomRefToScalar:
+    //         [param] -> { ref_phantom[] -> scalar_to_kill[] }
+    //
+    // Combining these with `isl_map_domain_product` gives us
+    // TaggedMustKill:
+    //     [param] -> { [Stmt[] -> phantom_ref[]] -> scalar_to_kill[] }
+
+    // 2a. [param] -> { Stmt[] -> scalar_to_kill[] }
+    isl::map StmtToScalar = isl::map::universe(ParamSpace);
+    StmtToScalar = StmtToScalar.set_tuple_id(isl::dim::in, isl::id(KillStmtId));
+    StmtToScalar = StmtToScalar.set_tuple_id(isl::dim::out, isl::id(ToKillId));
+
+    isl::id PhantomRefId = isl::id::alloc(
+        S.getIslCtx(), std::string("ref_phantom") + ToKillId.get_name(),
+        nullptr);
+
+    // 2b. [param] -> { phantom_ref[] -> scalar_to_kill[] }
+    isl::map PhantomRefToScalar = isl::map::universe(ParamSpace);
+    PhantomRefToScalar =
+        PhantomRefToScalar.set_tuple_id(isl::dim::in, PhantomRefId);
+    PhantomRefToScalar =
+        PhantomRefToScalar.set_tuple_id(isl::dim::out, ToKillId);
+
+    // 2. [param] -> { [Stmt[] -> phantom_ref[]] -> scalar_to_kill[] }
+    isl::map TaggedMustKill = StmtToScalar.domain_product(PhantomRefToScalar);
+    Info.TaggedMustKills = Info.TaggedMustKills.unite(TaggedMustKill);
+
+    // 2. [param] -> { Stmt[] -> scalar_to_kill[] }
+    Info.MustKills = Info.TaggedMustKills.domain_factor_domain();
+
+    // 3. Create the kill schedule of the form:
+    //     "[param] -> { Stmt_phantom[] }"
+    // Then add this to Info.KillsSchedule.
+    isl::space KillStmtSpace = ParamSpace;
+    KillStmtSpace = KillStmtSpace.set_tuple_id(isl::dim::set, KillStmtId);
+    isl::union_set KillStmtDomain = isl::set::universe(KillStmtSpace);
+
+    isl::schedule KillSchedule = isl::schedule::from_domain(KillStmtDomain);
+    if (Info.KillsSchedule)
+      Info.KillsSchedule = Info.KillsSchedule.set(KillSchedule);
+    else
+      Info.KillsSchedule = KillSchedule;
+  }
+
+  return Info;
+}
+
+
+
+/* IMPORTANT: the methods below are defined in PPCGCodeGeneration.cpp:
+ */
+// PPCGWrapperLRR is very similar to class PPCGCodeGeneration
+namespace {
+class PPCGWrapperLRR : public ScopPass {
+public:
+  static char ID;
+
+  /// The scop that is currently processed.
+  Scop *S;
+
+
+
+
+  PPCGWrapperLRR() : ScopPass(ID) {}
+
+  /// Construct compilation options for PPCG.
+  ///
+  /// @returns The compilation options.
+  ppcg_options *createPPCGOptions() {
+    auto DebugOptions =
+        (ppcg_debug_options *)malloc(sizeof(ppcg_debug_options));
+    auto Options = (ppcg_options *)malloc(sizeof(ppcg_options));
+
+    DebugOptions->dump_schedule_constraints = false;
+    DebugOptions->dump_schedule = false;
+    DebugOptions->dump_final_schedule = false;
+    DebugOptions->dump_sizes = false;
+    DebugOptions->verbose = false;
+
+    Options->debug = DebugOptions;
+
+    Options->group_chains = false;
+    Options->reschedule = true;
+    Options->scale_tile_loops = false;
+    Options->wrap = false;
+
+    Options->non_negative_parameters = false;
+    Options->ctx = nullptr;
+    Options->sizes = nullptr;
+
+    Options->tile = true;
+    Options->tile_size = 32;
+
+    Options->isolate_full_tiles = false;
+
+    Options->use_private_memory = PrivateMemory;
+    Options->use_shared_memory = SharedMemory;
+    Options->max_shared_memory = 48 * 1024;
+
+    Options->target = PPCG_TARGET_CUDA;
+    Options->openmp = false;
+    Options->linearize_device_arrays = true;
+    Options->allow_gnu_extensions = false;
+
+    Options->unroll_copy_shared = false;
+    Options->unroll_gpu_tile = false;
+    Options->live_range_reordering = true;
+
+    Options->live_range_reordering = true;
+    Options->hybrid = false;
+    Options->opencl_compiler_options = nullptr;
+    Options->opencl_use_gpu = false;
+    Options->opencl_n_include_file = 0;
+    Options->opencl_include_files = nullptr;
+    Options->opencl_print_kernel_types = false;
+    Options->opencl_embed_kernel_code = false;
+
+    Options->save_schedule_file = nullptr;
+    Options->load_schedule_file = nullptr;
+
+    return Options;
+  }
+
+
+  /// Get a tagged access relation containing all accesses of type @p AccessTy.
+  ///
+  /// Instead of a normal access of the form:
+  ///
+  ///   Stmt[i,j,k] -> Array[f_0(i,j,k), f_1(i,j,k)]
+  ///
+  /// a tagged access has the form
+  ///
+  ///   [Stmt[i,j,k] -> id[]] -> Array[f_0(i,j,k), f_1(i,j,k)]
+  ///
+  /// where 'id' is an additional space that references the memory access that
+  /// triggered the access.
+  ///
+  /// @param AccessTy The type of the memory accesses to collect.
+  ///
+  /// @return The relation describing all tagged memory accesses.
+  isl_union_map *getTaggedAccesses(enum MemoryAccess::AccessType AccessTy) {
+    isl_union_map *Accesses = isl_union_map_empty(S->getParamSpace().release());
+
+    for (auto &Stmt : *S)
+      for (auto &Acc : Stmt)
+        if (Acc->getType() == AccessTy) {
+          isl_map *Relation = Acc->getAccessRelation().release();
+          Relation =
+              isl_map_intersect_domain(Relation, Stmt.getDomain().release());
+
+          isl_space *Space = isl_map_get_space(Relation);
+          Space = isl_space_range(Space);
+          Space = isl_space_from_range(Space);
+          Space =
+              isl_space_set_tuple_id(Space, isl_dim_in, Acc->getId().release());
+          isl_map *Universe = isl_map_universe(Space);
+          Relation = isl_map_domain_product(Relation, Universe);
+          Accesses = isl_union_map_add_map(Accesses, Relation);
+        }
+
+    return Accesses;
+  }
+
+  /// Get the set of all read accesses, tagged with the access id.
+  ///
+  /// @see getTaggedAccesses
+  isl_union_map *getTaggedReads() {
+    return getTaggedAccesses(MemoryAccess::READ);
+  }
+
+  /// Get the set of all may (and must) accesses, tagged with the access id.
+  ///
+  /// @see getTaggedAccesses
+  isl_union_map *getTaggedMayWrites() {
+    return isl_union_map_union(getTaggedAccesses(MemoryAccess::MAY_WRITE),
+                               getTaggedAccesses(MemoryAccess::MUST_WRITE));
+  }
+
+  /// Get the set of all must accesses, tagged with the access id.
+  ///
+  /// @see getTaggedAccesses
+  isl_union_map *getTaggedMustWrites() {
+    return getTaggedAccesses(MemoryAccess::MUST_WRITE);
+  }
+
+
+  /// Collect parameter and array names as isl_ids.
+  ///
+  /// To reason about the different parameters and arrays used, ppcg requires
+  /// a list of all isl_ids in use. As PPCG traditionally performs
+  /// source-to-source compilation each of these isl_ids is mapped to the
+  /// expression that represents it. As we do not have a corresponding
+  /// expression in Polly, we just map each id to a 'zero' expression to match
+  /// the data format that ppcg expects.
+  ///
+  /// @returns Retun a map from collected ids to 'zero' ast expressions.
+  __isl_give isl_id_to_ast_expr *getNames() {
+    auto *Names = isl_id_to_ast_expr_alloc(
+        S->getIslCtx().get(),
+        S->getNumParams() + std::distance(S->array_begin(), S->array_end()));
+    auto *Zero = isl_ast_expr_from_val(isl_val_zero(S->getIslCtx().get()));
+
+    for (const SCEV *P : S->parameters()) {
+      isl_id *Id = S->getIdForParam(P).release();
+      Names = isl_id_to_ast_expr_set(Names, Id, isl_ast_expr_copy(Zero));
+    }
+
+    for (auto &Array : S->arrays()) {
+      auto Id = Array->getBasePtrId().release();
+      Names = isl_id_to_ast_expr_set(Names, Id, isl_ast_expr_copy(Zero));
+    }
+
+    isl_ast_expr_free(Zero);
+
+    return Names;
+  }
+
+  ppcg_scop *createPPCGScop() {
+    DEBUG(dbgs() << "Entered createPPCGScop()\n");
+
+    MustKillsInfo KillsInfo = computeMustKillsInfo(*S);
+
+    auto PPCGScop = (ppcg_scop *)malloc(sizeof(ppcg_scop));
+
+    PPCGScop->options = createPPCGOptions();
+    // enable live range reordering
+    PPCGScop->options->live_range_reordering = 1;
+
+    PPCGScop->start = 0;
+    PPCGScop->end = 0;
+
+    PPCGScop->context = S->getContext().release();
+    PPCGScop->domain = S->getDomains().release();
+    // TODO TODO: investigate this further. PPCG calls collect_call_domains.
+    PPCGScop->call = isl_union_set_from_set(S->getContext().release());
+    PPCGScop->tagged_reads = getTaggedReads();
+    PPCGScop->reads = S->getReads().release();
+    PPCGScop->live_in = nullptr;
+    PPCGScop->tagged_may_writes = getTaggedMayWrites();
+    PPCGScop->may_writes = S->getWrites().release();
+    PPCGScop->tagged_must_writes = getTaggedMustWrites();
+    PPCGScop->must_writes = S->getMustWrites().release();
+    PPCGScop->live_out = nullptr;
+    PPCGScop->tagged_must_kills = KillsInfo.TaggedMustKills.take();
+    PPCGScop->must_kills = KillsInfo.MustKills.take();
+
+    PPCGScop->tagger = nullptr;
+    PPCGScop->independence =
+        isl_union_map_empty(isl_set_get_space(PPCGScop->context));
+    PPCGScop->dep_flow = nullptr;
+    PPCGScop->tagged_dep_flow = nullptr;
+    PPCGScop->dep_false = nullptr;
+    PPCGScop->dep_forced = nullptr;
+    PPCGScop->dep_order = nullptr;
+    PPCGScop->tagged_dep_order = nullptr;
+
+    PPCGScop->schedule = S->getScheduleTree().release();
+    // If we have something non-trivial to kill, add it to the schedule
+    if (KillsInfo.KillsSchedule.get())
+      PPCGScop->schedule = isl_schedule_sequence(
+          PPCGScop->schedule, KillsInfo.KillsSchedule.take());
+
+    PPCGScop->names = getNames();
+    PPCGScop->pet = nullptr;
+
+    compute_tagger(PPCGScop);
+    compute_dependences(PPCGScop);
+    eliminate_dead_code(PPCGScop);
+
+    DEBUG(dbgs() << "Exiting createPPCGScop()\n");
+
+    return PPCGScop;
+  } // END createPPCGScop()
+
+
+  /// Free the options in the ppcg scop structure.
+  ///
+  /// ppcg is not freeing these options for us. To avoid leaks we do this
+  /// ourselves.
+  ///
+  /// @param PPCGScop The scop referencing the options to free.
+  void freeOptions(ppcg_scop *PPCGScop) {
+    free(PPCGScop->options->debug);
+    PPCGScop->options->debug = nullptr;
+    free(PPCGScop->options);
+    PPCGScop->options = nullptr;
+  }
+
+
+  // Alex: this is just a bogus definition of runScop()
+  bool runOnScop(Scop &CurrentScop) override {
+  }
+
+}; // END: class PPCGWrapperLRR
+} // END: namespace
+
+char PPCGWrapperLRR::ID = 1;
+// Alex: END NEW code
+
+
+
+
+
+
 /// Create an isl::union_set, which describes the isolate option based on
 /// IsolateDomain.
 ///
 /// @param IsolateDomain An isl::set whose @p OutDimsNum last dimensions should
 ///                      belong to the current band node.
 /// @param OutDimsNum    A number of dimensions that should belong to
 ///                      the current band node.
 static isl::union_set getIsolateOptions(isl::set IsolateDomain,
isl_schedule_node_foreach_descendant_top_down(
           break;
         }
 
         return isl_bool_true;
       },
       &Version);
 }
 
+
+
+PPCGWrapperLRR ppcgObj;
+ppcg_scop *ps = NULL;
+void FreePPCGObjects() {
+  if (LiveRangeReordering == true) {
+    /* Implementing the deallocation functionality at the end of
+                              PPCGCodeGeneration::runOnScop() */
+
+    ppcgObj.freeOptions(ps);
+
+    // ppcg_scop_free(ps);
+    // Implementing the functionality of ppcg_scop_free(ps);
+  isl_set_free(ps->context);
+  isl_union_set_free(ps->domain);
+  isl_union_set_free(ps->call);
+  isl_union_map_free(ps->tagged_reads);
+  isl_union_map_free(ps->reads);
+  isl_union_map_free(ps->live_in);
+  isl_union_map_free(ps->tagged_may_writes);
+  isl_union_map_free(ps->tagged_must_writes);
+  isl_union_map_free(ps->may_writes);
+  isl_union_map_free(ps->must_writes);
+  isl_union_map_free(ps->live_out);
+  isl_union_map_free(ps->tagged_must_kills);
+  isl_union_map_free(ps->must_kills);
+// TODO TODO: free these objects also
+// Avoiding various deallocation errors because the ISL objects were not allocated
+  //isl_union_map_free(ps->tagged_dep_flow);
+  //isl_union_map_free(ps->dep_flow);
+  isl_union_map_free(ps->dep_false);
+  // isl_union_map_free(ps->dep_forced);
+  //isl_union_map_free(ps->tagged_dep_order);
+  //isl_union_map_free(ps->dep_order);
+  isl_schedule_free(ps->schedule);
+  isl_union_pw_multi_aff_free(ps->tagger);
+    isl_union_map_free(ps->independence);
+  isl_id_to_ast_expr_free(ps->names);
+
+    DEBUG(dbgs() << "FreePPCGObjects(): (LiveRangeReordering == true) exiting... \n");
+  }
+}
+
 bool IslScheduleOptimizer::runOnScop(Scop &S) {
   // Skip SCoPs in case they're already optimised by PPCGCodeGeneration
   if (S.isToBeSkipped())
     return false;
 
   // Skip empty SCoPs but still allow code generation as it will delete the
   // loops present but not needed.
   if (S.getSize() == 0) {
if (SimplifyDeps == "yes") {
     Validity = Validity.gist_range(Domain);
     Proximity = Proximity.gist_domain(Domain);
     Proximity = Proximity.gist_range(Domain);
   } else if (SimplifyDeps != "no") {
     errs() << "warning: Option -polly-opt-simplify-deps should either be 'yes' "
               "or 'no'. Falling back to default: 'yes'\n";
   }
 
+  if (LiveRangeReordering == false) {
     DEBUG(dbgs() << "\n\nCompute schedule from: ");
     DEBUG(dbgs() << "Domain := " << Domain << ";\n");
     DEBUG(dbgs() << "Proximity := " << Proximity << ";\n");
     DEBUG(dbgs() << "Validity := " << Validity << ";\n");
-
+  }
   unsigned IslSerializeSCCs;
 
   if (FusionStrategy == "max") {
     IslSerializeSCCs = 0;
   } else if (FusionStrategy == "min") {
     IslSerializeSCCs = 1;
   } else {
     errs() << "warning: Unknown fusion strategy. Falling back to maximal "
bool IslScheduleOptimizer::runOnScop(Scop &S) {
 
   isl_ctx *Ctx = S.getIslCtx().get();
 
   isl_options_set_schedule_outer_coincidence(Ctx, IslOuterCoincidence);
   isl_options_set_schedule_serialize_sccs(Ctx, IslSerializeSCCs);
   isl_options_set_schedule_maximize_band_depth(Ctx, IslMaximizeBands);
   isl_options_set_schedule_max_constant_term(Ctx, MaxConstantTerm);
   isl_options_set_schedule_max_coefficient(Ctx, MaxCoefficient);
+  // NEW code
+  // From PPCGCodeGeneration.cpp: Set scheduling strategy to same strategy PPCG is using.
+  //isl_options_set_schedule_outer_coincidence(PPCGGen->ctx, true);
+  //isl_options_set_schedule_maximize_band_depth(PPCGGen->ctx, true);
+  isl_options_set_schedule_whole_component(Ctx, false);
+  // END NEW code
   isl_options_set_tile_scale_tile_loops(Ctx, 0);
 
   auto OnErrorStatus = isl_options_get_on_error(Ctx);
   isl_options_set_on_error(Ctx, ISL_ON_ERROR_CONTINUE);
 
   auto SC = isl::schedule_constraints::on_domain(Domain);
+
+
+
+  // NEW code starts here
+  if (LiveRangeReordering == false) {
+    DEBUG(dbgs() << "LiveRangeReordering == false\n");
+
     SC = SC.set_proximity(Proximity);
     SC = SC.set_validity(Validity);
     SC = SC.set_coincidence(Validity);
+  }
+  else {
+    DEBUG(dbgs() << "LiveRangeReordering == true\n");
+
+    ppcgObj.S = &S;
+
+    // This code is inspired from PPCGCodeGeneration::runOnScop()
+    ps = ppcgObj.createPPCGScop();
+
+    // IMPORTANT NOTE: from isl-noexceptions.h: inline isl::union_map give(__isl_take isl_union_map *ptr);
+    isl::union_map psTaggedDepFlow = give(ps->tagged_dep_flow);
+    isl::union_map psTaggedDepOrder = give(ps->tagged_dep_order);
+    //
+    SC = SC.set_conditional_validity(
+                            psTaggedDepFlow,
+                            psTaggedDepOrder
+                            );
+
+    isl::union_map psDepFlow = give(ps->dep_flow);
+    Validity = give(psDepFlow.copy());
+    isl::union_map psDepForced = give(ps->dep_forced);
+    Validity = Validity.unite(psDepForced);
+
+    // TODO TODO: if (ps->options->openmp)
+      isl::union_map Coincidence = give(Validity.copy());
+      isl::union_map psDepOrder = give(ps->dep_order);
+      Coincidence = Coincidence.unite(psDepOrder);
+      SC = SC.set_coincidence(Coincidence);
+
+    SC = SC.set_proximity(psDepFlow); //give(ps->dep_flow));
+    /* From https://lirias.kuleuven.be/bitstream/123456789/519489/1/live_range_reordering.pdf:
+       "The proximity constraints are set to the union of the flow and the
+         false dependences."
+     TODO TODO: therefore, we need to SC.set_proximity(union(psDepFlow, dep_false)); */
+
+    SC = SC.set_validity(Validity);
+
+
+    DEBUG(dbgs() << "\n\nCompute schedule from: ");
+    DEBUG(dbgs() << "Domain := " << Domain << ";\n");
+    DEBUG(dbgs() << "Proximity := " << psDepFlow << ";\n");
+    DEBUG(dbgs() << "Validity := " << Validity << ";\n");
+    DEBUG(dbgs() << "Coincidence := " << Coincidence << ";\n");
+    DEBUG(dbgs() << "psTaggedDepFlow := " << psTaggedDepFlow << ";\n");
+    DEBUG(dbgs() << "psTaggedDepOrder := " << psTaggedDepOrder << ";\n");
+  }
+  // END new code
+
   auto Schedule = SC.compute_schedule();
   isl_options_set_on_error(Ctx, OnErrorStatus);
 
   walkScheduleTreeForStatistics(Schedule, 1);
 
   // In cases the scheduler is not able to optimize the code, we just do not
   // touch the schedule.
-  if (!Schedule)
+  if (!Schedule) {
+    FreePPCGObjects();
     return false;
+  }
 
   ScopsRescheduled++;
 
   DEBUG({
     auto *P = isl_printer_to_str(Ctx);
     P = isl_printer_set_yaml_style(P, ISL_YAML_STYLE_BLOCK);
     P = isl_printer_print_schedule(P, Schedule.get());
     auto *str = isl_printer_get_str(P);
     dbgs() << "NewScheduleTree: \n" << str << "\n";
     free(str);
     isl_printer_free(P);
   });
 
   Function &F = S.getFunction();
   auto *TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
   const OptimizerAdditionalInfoTy OAI = {TTI, const_cast<Dependences *>(&D)};
   auto NewSchedule = ScheduleTreeOptimizer::optimizeSchedule(Schedule, &OAI);
   walkScheduleTreeForStatistics(NewSchedule, 2);
 
-  if (!ScheduleTreeOptimizer::isProfitableSchedule(S, NewSchedule))
+  if (!ScheduleTreeOptimizer::isProfitableSchedule(S, NewSchedule)) {
+    FreePPCGObjects();
     return false;
+  }
 
   auto ScopStats = S.getStatistics();
   ScopsOptimized++;
   NumAffineLoopsOptimized += ScopStats.NumAffineLoops;
   NumBoxedLoopsOptimized += ScopStats.NumBoxedLoops;
 
   S.setScheduleTree(NewSchedule);
   S.markAsOptimized();
 
   if (OptimizedScops)
     errs() << S;
 
+  FreePPCGObjects();
   return false;
 }
 
 void IslScheduleOptimizer::printScop(raw_ostream &OS, Scop &) const {
   isl_printer *p;
   char *ScheduleStr;
 
   OS << "Calculated schedule:\n";

 
 INITIALIZE_PASS_BEGIN(IslScheduleOptimizer, "polly-opt-isl",
                       "Polly - Optimize schedule of SCoP", false, false);
 INITIALIZE_PASS_DEPENDENCY(DependenceInfo);
 INITIALIZE_PASS_DEPENDENCY(ScopInfoRegionPass);
 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass);
 INITIALIZE_PASS_END(IslScheduleOptimizer, "polly-opt-isl",
                     "Polly - Optimize schedule of SCoP", false, false)
+