1 //===------ FlattenSchedule.cpp --------------------------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // Try to reduce the number of scatter dimension. Useful to make isl_union_map
10 // schedules more understandable. This is only intended for debugging and
11 // unittests, not for production use.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "polly/FlattenSchedule.h"
16 #include "polly/FlattenAlgo.h"
17 #include "polly/ScopInfo.h"
18 #include "polly/ScopPass.h"
19 #include "polly/Support/ISLOStream.h"
20 #include "polly/Support/ISLTools.h"
21 #define DEBUG_TYPE "polly-flatten-schedule"
22 
23 using namespace polly;
24 using namespace llvm;
25 
26 namespace {
27 
28 /// Print a schedule to @p OS.
29 ///
30 /// Prints the schedule for each statements on a new line.
31 void printSchedule(raw_ostream &OS, const isl::union_map &Schedule,
32                    int indent) {
33   for (isl::map Map : Schedule.get_map_list())
34     OS.indent(indent) << Map << "\n";
35 }
36 
37 /// Flatten the schedule stored in an polly::Scop.
38 class FlattenSchedule final : public ScopPass {
39 private:
40   FlattenSchedule(const FlattenSchedule &) = delete;
41   const FlattenSchedule &operator=(const FlattenSchedule &) = delete;
42 
43   std::shared_ptr<isl_ctx> IslCtx;
44   isl::union_map OldSchedule;
45 
46 public:
47   static char ID;
48   explicit FlattenSchedule() : ScopPass(ID) {}
49 
50   virtual void getAnalysisUsage(AnalysisUsage &AU) const override {
51     AU.addRequiredTransitive<ScopInfoRegionPass>();
52     AU.setPreservesAll();
53   }
54 
55   virtual bool runOnScop(Scop &S) override {
56     // Keep a reference to isl_ctx to ensure that it is not freed before we free
57     // OldSchedule.
58     IslCtx = S.getSharedIslCtx();
59 
60     LLVM_DEBUG(dbgs() << "Going to flatten old schedule:\n");
61     OldSchedule = S.getSchedule();
62     LLVM_DEBUG(printSchedule(dbgs(), OldSchedule, 2));
63 
64     auto Domains = S.getDomains();
65     auto RestrictedOldSchedule = OldSchedule.intersect_domain(Domains);
66     LLVM_DEBUG(dbgs() << "Old schedule with domains:\n");
67     LLVM_DEBUG(printSchedule(dbgs(), RestrictedOldSchedule, 2));
68 
69     auto NewSchedule = flattenSchedule(RestrictedOldSchedule);
70 
71     LLVM_DEBUG(dbgs() << "Flattened new schedule:\n");
72     LLVM_DEBUG(printSchedule(dbgs(), NewSchedule, 2));
73 
74     NewSchedule = NewSchedule.gist_domain(Domains);
75     LLVM_DEBUG(dbgs() << "Gisted, flattened new schedule:\n");
76     LLVM_DEBUG(printSchedule(dbgs(), NewSchedule, 2));
77 
78     S.setSchedule(NewSchedule);
79     return false;
80   }
81 
82   virtual void printScop(raw_ostream &OS, Scop &S) const override {
83     OS << "Schedule before flattening {\n";
84     printSchedule(OS, OldSchedule, 4);
85     OS << "}\n\n";
86 
87     OS << "Schedule after flattening {\n";
88     printSchedule(OS, S.getSchedule(), 4);
89     OS << "}\n";
90   }
91 
92   virtual void releaseMemory() override {
93     OldSchedule = {};
94     IslCtx.reset();
95   }
96 };
97 
98 char FlattenSchedule::ID;
99 
100 /// Print result from FlattenSchedule.
101 class FlattenSchedulePrinterLegacyPass final : public ScopPass {
102 public:
103   static char ID;
104 
105   FlattenSchedulePrinterLegacyPass()
106       : FlattenSchedulePrinterLegacyPass(outs()){};
107   explicit FlattenSchedulePrinterLegacyPass(llvm::raw_ostream &OS)
108       : ScopPass(ID), OS(OS) {}
109 
110   bool runOnScop(Scop &S) override {
111     FlattenSchedule &P = getAnalysis<FlattenSchedule>();
112 
113     OS << "Printing analysis '" << P.getPassName() << "' for region: '"
114        << S.getRegion().getNameStr() << "' in function '"
115        << S.getFunction().getName() << "':\n";
116     P.printScop(OS, S);
117 
118     return false;
119   }
120 
121   void getAnalysisUsage(AnalysisUsage &AU) const override {
122     ScopPass::getAnalysisUsage(AU);
123     AU.addRequired<FlattenSchedule>();
124     AU.setPreservesAll();
125   }
126 
127 private:
128   llvm::raw_ostream &OS;
129 };
130 
131 char FlattenSchedulePrinterLegacyPass::ID = 0;
132 } // anonymous namespace
133 
134 Pass *polly::createFlattenSchedulePass() { return new FlattenSchedule(); }
135 
136 Pass *polly::createFlattenSchedulePrinterLegacyPass(llvm::raw_ostream &OS) {
137   return new FlattenSchedulePrinterLegacyPass(OS);
138 }
139 
140 INITIALIZE_PASS_BEGIN(FlattenSchedule, "polly-flatten-schedule",
141                       "Polly - Flatten schedule", false, false)
142 INITIALIZE_PASS_END(FlattenSchedule, "polly-flatten-schedule",
143                     "Polly - Flatten schedule", false, false)
144 
145 INITIALIZE_PASS_BEGIN(FlattenSchedulePrinterLegacyPass,
146                       "polly-print-flatten-schedule",
147                       "Polly - Print flattened schedule", false, false)
148 INITIALIZE_PASS_DEPENDENCY(FlattenSchedule)
149 INITIALIZE_PASS_END(FlattenSchedulePrinterLegacyPass,
150                     "polly-print-flatten-schedule",
151                     "Polly - Print flattened schedule", false, false)
152