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