polly/lib/Transform/ManualOptimizer.cpp

   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/DependenceInfo.h"
  15 #include "polly/Options.h"
  16 #include "polly/ScheduleTreeTransform.h"
  17 #include "polly/Support/ScopHelper.h"
  18 #include "llvm/ADT/StringRef.h"
  19 #include "llvm/Analysis/LoopInfo.h"
  20 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
  21 #include "llvm/IR/Metadata.h"
  22 #include "llvm/Transforms/Utils/LoopUtils.h"
  23 #include <optional>
  24
  25 #include "polly/Support/PollyDebug.h"
  26 #define DEBUG_TYPE "polly-opt-manual"
  27
  28 using namespace polly;
  29 using namespace llvm;
  30
  31 namespace {
  32
  33 static cl::opt<bool> IgnoreDepcheck(
  34     "polly-pragma-ignore-depcheck",
  35     cl::desc("Skip the dependency check for pragma-based transformations"),
  36     cl::cat(PollyCategory));
  37
  38 /// Same as llvm::hasUnrollTransformation(), but takes a LoopID as argument
  39 /// instead of a Loop.
  40 static TransformationMode hasUnrollTransformation(MDNode *LoopID) {
  41   if (getBooleanLoopAttribute(LoopID, "llvm.loop.unroll.disable"))
  42     return TM_SuppressedByUser;
  43
  44   std::optional<int> Count =
  45       getOptionalIntLoopAttribute(LoopID, "llvm.loop.unroll.count");
  46   if (Count)
  47     return *Count == 1 ? TM_SuppressedByUser : TM_ForcedByUser;
  48
  49   if (getBooleanLoopAttribute(LoopID, "llvm.loop.unroll.enable"))
  50     return TM_ForcedByUser;
  51
  52   if (getBooleanLoopAttribute(LoopID, "llvm.loop.unroll.full"))
  53     return TM_ForcedByUser;
  54
  55   if (hasDisableAllTransformsHint(LoopID))
  56     return TM_Disable;
  57
  58   return TM_Unspecified;
  59 }
  60
  61 // Return the first DebugLoc in the list.
  62 static DebugLoc findFirstDebugLoc(MDNode *MD) {
  63   if (MD) {
  64     for (const MDOperand &X : drop_begin(MD->operands(), 1)) {
  65       Metadata *A = X.get();
  66       if (!isa<DILocation>(A))
  67         continue;
  68       return cast<DILocation>(A);
  69     }
  70   }
  71
  72   return {};
  73 }
  74
  75 static DebugLoc findTransformationDebugLoc(MDNode *LoopMD, StringRef Name) {
  76   // First find dedicated transformation location
  77   // (such as the location of #pragma clang loop)
  78   MDNode *MD = findOptionMDForLoopID(LoopMD, Name);
  79   if (DebugLoc K = findFirstDebugLoc(MD))
  80     return K;
  81
  82   // Otherwise, fall back to the location of the loop itself
  83   return findFirstDebugLoc(LoopMD);
  84 }
  85
  86 /// Apply full or partial unrolling.
  87 static isl::schedule applyLoopUnroll(MDNode *LoopMD,
  88                                      isl::schedule_node BandToUnroll) {
  89   TransformationMode UnrollMode = ::hasUnrollTransformation(LoopMD);
  90   if (UnrollMode & TM_Disable)
  91     return {};
  92
  93   assert(!BandToUnroll.is_null());
  94   // TODO: Isl's codegen also supports unrolling by isl_ast_build via
  95   // isl_schedule_node_band_set_ast_build_options({ unroll[x] }) which would be
  96   // more efficient because the content duplication is delayed. However, the
  97   // unrolled loop could be input of another loop transformation which expects
  98   // the explicit schedule nodes. That is, we would need this explicit expansion
  99   // anyway and using the ISL codegen option is a compile-time optimization.
 100   int64_t Factor =
 101       getOptionalIntLoopAttribute(LoopMD, "llvm.loop.unroll.count").value_or(0);
 102   bool Full = getBooleanLoopAttribute(LoopMD, "llvm.loop.unroll.full");
 103   assert((!Full || !(Factor > 0)) &&
 104          "Cannot unroll fully and partially at the same time");
 105
 106   if (Full)
 107     return applyFullUnroll(BandToUnroll);
 108
 109   if (Factor > 0)
 110     return applyPartialUnroll(BandToUnroll, Factor);
 111
 112   // For heuristic unrolling, fall back to LLVM's LoopUnroll pass.
 113   return {};
 114 }
 115
 116 static isl::schedule applyLoopFission(MDNode *LoopMD,
 117                                       isl::schedule_node BandToFission) {
 118   // TODO: Make it possible to selectively fission substatements.
 119   // TODO: Apply followup loop properties.
 120   // TODO: Instead of fission every statement, find the maximum set that does
 121   // not cause a dependency violation.
 122   return applyMaxFission(BandToFission);
 123 }
 124
 125 // Return the properties from a LoopID. Scalar properties are ignored.
 126 static auto getLoopMDProps(MDNode *LoopMD) {
 127   return map_range(
 128       make_filter_range(
 129           drop_begin(LoopMD->operands(), 1),
 130           [](const MDOperand &MDOp) { return isa<MDNode>(MDOp.get()); }),
 131       [](const MDOperand &MDOp) { return cast<MDNode>(MDOp.get()); });
 132 }
 133
 134 /// Recursively visit all nodes in a schedule, loop for loop-transformations
 135 /// metadata and apply the first encountered.
 136 class SearchTransformVisitor final
 137     : public RecursiveScheduleTreeVisitor<SearchTransformVisitor> {
 138 private:
 139   using BaseTy = RecursiveScheduleTreeVisitor<SearchTransformVisitor>;
 140   BaseTy &getBase() { return *this; }
 141   const BaseTy &getBase() const { return *this; }
 142
 143   polly::Scop *S;
 144   const Dependences *D;
 145   OptimizationRemarkEmitter *ORE;
 146
 147   // Set after a transformation is applied. Recursive search must be aborted
 148   // once this happens to ensure that any new followup transformation is
 149   // transformed in innermost-first order.
 150   isl::schedule Result;
 151
 152   /// Check wether a schedule after a  transformation is legal. Return the old
 153   /// schedule without the transformation.
 154   isl::schedule
 155   checkDependencyViolation(llvm::MDNode *LoopMD, llvm::Value *CodeRegion,
 156                            const isl::schedule_node &OrigBand,
 157                            StringRef DebugLocAttr, StringRef TransPrefix,
 158                            StringRef RemarkName, StringRef TransformationName) {
 159     if (D->isValidSchedule(*S, Result))
 160       return Result;
 161
 162     LLVMContext &Ctx = LoopMD->getContext();
 163     POLLY_DEBUG(dbgs() << "Dependency violation detected\n");
 164
 165     DebugLoc TransformLoc = findTransformationDebugLoc(LoopMD, DebugLocAttr);
 166
 167     if (IgnoreDepcheck) {
 168       POLLY_DEBUG(dbgs() << "Still accepting transformation due to "
 169                             "-polly-pragma-ignore-depcheck\n");
 170       if (ORE) {
 171         ORE->emit(
 172             OptimizationRemark(DEBUG_TYPE, RemarkName, TransformLoc, CodeRegion)
 173             << (Twine("Could not verify dependencies for ") +
 174                 TransformationName +
 175                 "; still applying because of -polly-pragma-ignore-depcheck")
 176                    .str());
 177       }
 178       return Result;
 179     }
 180
 181     POLLY_DEBUG(dbgs() << "Rolling back transformation\n");
 182
 183     if (ORE) {
 184       ORE->emit(DiagnosticInfoOptimizationFailure(DEBUG_TYPE, RemarkName,
 185                                                   TransformLoc, CodeRegion)
 186                 << (Twine("not applying ") + TransformationName +
 187                     ": cannot ensure semantic equivalence due to possible "
 188                     "dependency violations")
 189                        .str());
 190     }
 191
 192     // If illegal, revert and remove the transformation to not risk re-trying
 193     // indefinitely.
 194     MDNode *NewLoopMD =
 195         makePostTransformationMetadata(Ctx, LoopMD, {TransPrefix}, {});
 196     BandAttr *Attr = getBandAttr(OrigBand);
 197     Attr->Metadata = NewLoopMD;
 198
 199     // Roll back old schedule.
 200     return OrigBand.get_schedule();
 201   }
 202
 203 public:
 204   SearchTransformVisitor(polly::Scop *S, const Dependences *D,
 205                          OptimizationRemarkEmitter *ORE)
 206       : S(S), D(D), ORE(ORE) {}
 207
 208   static isl::schedule applyOneTransformation(polly::Scop *S,
 209                                               const Dependences *D,
 210                                               OptimizationRemarkEmitter *ORE,
 211                                               const isl::schedule &Sched) {
 212     SearchTransformVisitor Transformer(S, D, ORE);
 213     Transformer.visit(Sched);
 214     return Transformer.Result;
 215   }
 216
 217   void visitBand(isl::schedule_node_band Band) {
 218     // Transform inner loops first (depth-first search).
 219     getBase().visitBand(Band);
 220     if (!Result.is_null())
 221       return;
 222
 223     // Since it is (currently) not possible to have a BandAttr marker that is
 224     // specific to each loop in a band, we only support single-loop bands.
 225     if (isl_schedule_node_band_n_member(Band.get()) != 1)
 226       return;
 227
 228     BandAttr *Attr = getBandAttr(Band);
 229     if (!Attr) {
 230       // Band has no attribute.
 231       return;
 232     }
 233
 234     // CodeRegion used but ORE to determine code hotness.
 235     // TODO: Works only for original loop; for transformed loops, should track
 236     // where the loop's body code comes from.
 237     Loop *Loop = Attr->OriginalLoop;
 238     Value *CodeRegion = nullptr;
 239     if (Loop)
 240       CodeRegion = Loop->getHeader();
 241
 242     MDNode *LoopMD = Attr->Metadata;
 243     if (!LoopMD)
 244       return;
 245
 246     // Iterate over loop properties to find the first transformation.
 247     // FIXME: If there are more than one transformation in the LoopMD (making
 248     // the order of transformations ambiguous), all others are silently ignored.
 249     for (MDNode *MD : getLoopMDProps(LoopMD)) {
 250       auto *NameMD = dyn_cast<MDString>(MD->getOperand(0).get());
 251       if (!NameMD)
 252         continue;
 253       StringRef AttrName = NameMD->getString();
 254
 255       // Honor transformation order; transform the first transformation in the
 256       // list first.
 257       if (AttrName == "llvm.loop.unroll.enable" ||
 258           AttrName == "llvm.loop.unroll.count" ||
 259           AttrName == "llvm.loop.unroll.full") {
 260         Result = applyLoopUnroll(LoopMD, Band);
 261         if (!Result.is_null())
 262           return;
 263       } else if (AttrName == "llvm.loop.distribute.enable") {
 264         Result = applyLoopFission(LoopMD, Band);
 265         if (!Result.is_null())
 266           Result = checkDependencyViolation(
 267               LoopMD, CodeRegion, Band, "llvm.loop.distribute.loc",
 268               "llvm.loop.distribute.", "FailedRequestedFission",
 269               "loop fission/distribution");
 270         if (!Result.is_null())
 271           return;
 272       }
 273
 274       // not a loop transformation; look for next property
 275     }
 276   }
 277
 278   void visitNode(isl::schedule_node Other) {
 279     if (!Result.is_null())
 280       return;
 281     getBase().visitNode(Other);
 282   }
 283 };
 284
 285 } // namespace
 286
 287 isl::schedule
 288 polly::applyManualTransformations(Scop *S, isl::schedule Sched,
 289                                   const Dependences &D,
 290                                   OptimizationRemarkEmitter *ORE) {
 291   // Search the loop nest for transformations until fixpoint.
 292   while (true) {
 293     isl::schedule Result =
 294         SearchTransformVisitor::applyOneTransformation(S, &D, ORE, Sched);
 295     if (Result.is_null()) {
 296       // No (more) transformation has been found.
 297       break;
 298     }
 299
 300     // Use transformed schedule and look for more transformations.
 301     Sched = Result;
 302   }
 303
 304   return Sched;
 305 }