[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.