306 lines · 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-exception6//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 28using namespace polly;29using namespace llvm;30 31namespace {32 33static 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 argument39/// instead of a Loop.40static 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.62static 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 75static DebugLoc findTransformationDebugLoc(MDNode *LoopMD, StringRef Name) {76 // First find dedicated transformation location77 // (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 itself83 return findFirstDebugLoc(LoopMD);84}85 86/// Apply full or partial unrolling.87static 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 via95 // isl_schedule_node_band_set_ast_build_options({ unroll[x] }) which would be96 // more efficient because the content duplication is delayed. However, the97 // unrolled loop could be input of another loop transformation which expects98 // the explicit schedule nodes. That is, we would need this explicit expansion99 // 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 116static 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 does121 // not cause a dependency violation.122 return applyMaxFission(BandToFission);123}124 125// Return the properties from a LoopID. Scalar properties are ignored.126static 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-transformations135/// metadata and apply the first encountered.136class SearchTransformVisitor final137 : public RecursiveScheduleTreeVisitor<SearchTransformVisitor> {138private: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 aborted148 // once this happens to ensure that any new followup transformation is149 // transformed in innermost-first order.150 isl::schedule Result;151 152 /// Check whether a schedule after a transformation is legal. Return the old153 /// schedule without the transformation.154 isl::schedule155 checkDependencyViolation(llvm::MDNode *LoopMD, llvm::BasicBlock *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-trying193 // 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 203public: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 is224 // 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 track236 // where the loop's body code comes from.237 Loop *Loop = Attr->OriginalLoop;238 BasicBlock *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 (making248 // 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 the256 // 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 property275 }276 }277 278 void visitNode(isl::schedule_node Other) {279 if (!Result.is_null())280 return;281 getBase().visitNode(Other);282 }283};284 285} // namespace286 287isl::schedule288polly::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}306