1 //===------ ManualOptimizer.cpp -------------------------------------------===//
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 // Handle pragma/metadata-directed transformations.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "polly/ManualOptimizer.h"
14 #include "polly/ScheduleTreeTransform.h"
15 #include "polly/Support/ScopHelper.h"
16 #include "llvm/ADT/Optional.h"
17 #include "llvm/ADT/StringRef.h"
18 #include "llvm/Analysis/LoopInfo.h"
19 #include "llvm/IR/Metadata.h"
20 #include "llvm/Transforms/Utils/LoopUtils.h"
21 
22 #define DEBUG_TYPE "polly-opt-manual"
23 
24 using namespace polly;
25 using namespace llvm;
26 
27 namespace {
28 /// Same as llvm::hasUnrollTransformation(), but takes a LoopID as argument
29 /// instead of a Loop.
30 static TransformationMode hasUnrollTransformation(MDNode *LoopID) {
31   if (getBooleanLoopAttribute(LoopID, "llvm.loop.unroll.disable"))
32     return TM_SuppressedByUser;
33 
34   Optional<int> Count =
35       getOptionalIntLoopAttribute(LoopID, "llvm.loop.unroll.count");
36   if (Count.hasValue())
37     return Count.getValue() == 1 ? TM_SuppressedByUser : TM_ForcedByUser;
38 
39   if (getBooleanLoopAttribute(LoopID, "llvm.loop.unroll.enable"))
40     return TM_ForcedByUser;
41 
42   if (getBooleanLoopAttribute(LoopID, "llvm.loop.unroll.full"))
43     return TM_ForcedByUser;
44 
45   if (hasDisableAllTransformsHint(LoopID))
46     return TM_Disable;
47 
48   return TM_Unspecified;
49 }
50 
51 /// Apply full or partial unrolling.
52 static isl::schedule applyLoopUnroll(MDNode *LoopMD,
53                                      isl::schedule_node BandToUnroll) {
54   TransformationMode UnrollMode = ::hasUnrollTransformation(LoopMD);
55   if (UnrollMode & TM_Disable)
56     return {};
57 
58   assert(!BandToUnroll.is_null());
59   // TODO: Isl's codegen also supports unrolling by isl_ast_build via
60   // isl_schedule_node_band_set_ast_build_options({ unroll[x] }) which would be
61   // more efficient because the content duplication is delayed. However, the
62   // unrolled loop could be input of another loop transformation which expects
63   // the explicit schedule nodes. That is, we would need this explicit expansion
64   // anyway and using the ISL codegen option is a compile-time optimization.
65   int64_t Factor = getOptionalIntLoopAttribute(LoopMD, "llvm.loop.unroll.count")
66                        .getValueOr(0);
67   bool Full = getBooleanLoopAttribute(LoopMD, "llvm.loop.unroll.full");
68   assert((!Full || !(Factor > 0)) &&
69          "Cannot unroll fully and partially at the same time");
70 
71   if (Full)
72     return applyFullUnroll(BandToUnroll);
73 
74   if (Factor > 0)
75     return applyPartialUnroll(BandToUnroll, Factor);
76 
77   // For heuristic unrolling, fall back to LLVM's LoopUnroll pass.
78   return {};
79 }
80 
81 // Return the properties from a LoopID. Scalar properties are ignored.
82 static auto getLoopMDProps(MDNode *LoopMD) {
83   return map_range(
84       make_filter_range(
85           drop_begin(LoopMD->operands(), 1),
86           [](const MDOperand &MDOp) { return isa<MDNode>(MDOp.get()); }),
87       [](const MDOperand &MDOp) { return cast<MDNode>(MDOp.get()); });
88 }
89 
90 /// Recursively visit all nodes in a schedule, loop for loop-transformations
91 /// metadata and apply the first encountered.
92 class SearchTransformVisitor
93     : public RecursiveScheduleTreeVisitor<SearchTransformVisitor> {
94 private:
95   using BaseTy = RecursiveScheduleTreeVisitor<SearchTransformVisitor>;
96   BaseTy &getBase() { return *this; }
97   const BaseTy &getBase() const { return *this; }
98 
99   // Set after a transformation is applied. Recursive search must be aborted
100   // once this happens to ensure that any new followup transformation is
101   // transformed in innermost-first order.
102   isl::schedule Result;
103 
104 public:
105   static isl::schedule applyOneTransformation(const isl::schedule &Sched) {
106     SearchTransformVisitor Transformer;
107     Transformer.visit(Sched);
108     return Transformer.Result;
109   }
110 
111   void visitBand(const isl::schedule_node &Band) {
112     // Transform inner loops first (depth-first search).
113     getBase().visitBand(Band);
114     if (!Result.is_null())
115       return;
116 
117     // Since it is (currently) not possible to have a BandAttr marker that is
118     // specific to each loop in a band, we only support single-loop bands.
119     if (isl_schedule_node_band_n_member(Band.get()) != 1)
120       return;
121 
122     BandAttr *Attr = getBandAttr(Band);
123     if (!Attr) {
124       // Band has no attribute.
125       return;
126     }
127 
128     MDNode *LoopMD = Attr->Metadata;
129     if (!LoopMD)
130       return;
131 
132     // Iterate over loop properties to find the first transformation.
133     // FIXME: If there are more than one transformation in the LoopMD (making
134     // the order of transformations ambiguous), all others are silently ignored.
135     for (MDNode *MD : getLoopMDProps(LoopMD)) {
136       auto *NameMD = dyn_cast<MDString>(MD->getOperand(0).get());
137       if (!NameMD)
138         continue;
139       StringRef AttrName = NameMD->getString();
140 
141       // Honor transformation order; transform the first transformation in the
142       // list first.
143       if (AttrName == "llvm.loop.unroll.enable" ||
144           AttrName == "llvm.loop.unroll.count" ||
145           AttrName == "llvm.loop.unroll.full") {
146         Result = applyLoopUnroll(LoopMD, Band);
147         if (!Result.is_null())
148           return;
149       }
150 
151       // not a loop transformation; look for next property
152       continue;
153     }
154   }
155 
156   void visitNode(const isl::schedule_node &Other) {
157     if (!Result.is_null())
158       return;
159     getBase().visitNode(Other);
160   }
161 };
162 
163 } // namespace
164 
165 isl::schedule polly::applyManualTransformations(Scop *S, isl::schedule Sched) {
166   // Search the loop nest for transformations until fixpoint.
167   while (true) {
168     isl::schedule Result =
169         SearchTransformVisitor::applyOneTransformation(Sched);
170     if (Result.is_null()) {
171       // No (more) transformation has been found.
172       break;
173     }
174 
175     // Use transformed schedule and look for more transformations.
176     Sched = Result;
177   }
178 
179   return Sched;
180 }
181