990 lines · cpp
1//===- ScheduleOptimizer.cpp - Calculate an optimized schedule ------------===//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// This pass generates an entirely new schedule tree from the data dependences10// and iteration domains. The new schedule tree is computed in two steps:11//12// 1) The isl scheduling optimizer is run13//14// The isl scheduling optimizer creates a new schedule tree that maximizes15// parallelism and tileability and minimizes data-dependence distances. The16// algorithm used is a modified version of the ``Pluto'' algorithm:17//18// U. Bondhugula, A. Hartono, J. Ramanujam, and P. Sadayappan.19// A Practical Automatic Polyhedral Parallelizer and Locality Optimizer.20// In Proceedings of the 2008 ACM SIGPLAN Conference On Programming Language21// Design and Implementation, PLDI ’08, pages 101–113. ACM, 2008.22//23// 2) A set of post-scheduling transformations is applied on the schedule tree.24//25// These optimizations include:26//27// - Tiling of the innermost tilable bands28// - Prevectorization - The choice of a possible outer loop that is strip-mined29// to the innermost level to enable inner-loop30// vectorization.31// - Some optimizations for spatial locality are also planned.32//33// For a detailed description of the schedule tree itself please see section 634// of:35//36// Polyhedral AST generation is more than scanning polyhedra37// Tobias Grosser, Sven Verdoolaege, Albert Cohen38// ACM Transactions on Programming Languages and Systems (TOPLAS),39// 37(4), July 201540// http://www.grosser.es/#pub-polyhedral-AST-generation41//42// This publication also contains a detailed discussion of the different options43// for polyhedral loop unrolling, full/partial tile separation and other uses44// of the schedule tree.45//46//===----------------------------------------------------------------------===//47 48#include "polly/ScheduleOptimizer.h"49#include "polly/CodeGen/CodeGeneration.h"50#include "polly/DependenceInfo.h"51#include "polly/ManualOptimizer.h"52#include "polly/MatmulOptimizer.h"53#include "polly/Options.h"54#include "polly/ScheduleTreeTransform.h"55#include "polly/ScopInfo.h"56#include "polly/Support/ISLOStream.h"57#include "polly/Support/ISLTools.h"58#include "llvm/ADT/Sequence.h"59#include "llvm/ADT/Statistic.h"60#include "llvm/Analysis/OptimizationRemarkEmitter.h"61#include "llvm/Support/CommandLine.h"62#include "isl/options.h"63 64using namespace llvm;65using namespace polly;66 67namespace llvm {68class Loop;69class Module;70} // namespace llvm71 72#include "polly/Support/PollyDebug.h"73#define DEBUG_TYPE "polly-opt-isl"74 75static cl::opt<std::string>76 OptimizeDeps("polly-opt-optimize-only",77 cl::desc("Only a certain kind of dependences (all/raw)"),78 cl::Hidden, cl::init("all"), cl::cat(PollyCategory));79 80static cl::opt<std::string>81 SimplifyDeps("polly-opt-simplify-deps",82 cl::desc("Dependences should be simplified (yes/no)"),83 cl::Hidden, cl::init("yes"), cl::cat(PollyCategory));84 85static cl::opt<int> MaxConstantTerm(86 "polly-opt-max-constant-term",87 cl::desc("The maximal constant term allowed (-1 is unlimited)"), cl::Hidden,88 cl::init(20), cl::cat(PollyCategory));89 90static cl::opt<int> MaxCoefficient(91 "polly-opt-max-coefficient",92 cl::desc("The maximal coefficient allowed (-1 is unlimited)"), cl::Hidden,93 cl::init(20), cl::cat(PollyCategory));94 95static cl::opt<std::string>96 MaximizeBandDepth("polly-opt-maximize-bands",97 cl::desc("Maximize the band depth (yes/no)"), cl::Hidden,98 cl::init("yes"), cl::cat(PollyCategory));99 100static cl::opt<int>101 ScheduleComputeOut("polly-schedule-computeout",102 cl::desc("Bound the scheduler by maximal amount"103 "of computational steps. "),104 cl::Hidden, cl::init(300000), cl::ZeroOrMore,105 cl::cat(PollyCategory));106 107static cl::opt<bool>108 GreedyFusion("polly-loopfusion-greedy",109 cl::desc("Aggressively try to fuse everything"), cl::Hidden,110 cl::cat(PollyCategory));111 112static cl::opt<std::string> OuterCoincidence(113 "polly-opt-outer-coincidence",114 cl::desc("Try to construct schedules where the outer member of each band "115 "satisfies the coincidence constraints (yes/no)"),116 cl::Hidden, cl::init("no"), cl::cat(PollyCategory));117 118static cl::opt<int> PrevectorWidth(119 "polly-prevect-width",120 cl::desc(121 "The number of loop iterations to strip-mine for pre-vectorization"),122 cl::Hidden, cl::init(4), cl::cat(PollyCategory));123 124static cl::opt<bool> FirstLevelTiling("polly-tiling",125 cl::desc("Enable loop tiling"),126 cl::init(true), cl::cat(PollyCategory));127 128static cl::opt<int> FirstLevelDefaultTileSize(129 "polly-default-tile-size",130 cl::desc("The default tile size (if not enough were provided by"131 " --polly-tile-sizes)"),132 cl::Hidden, cl::init(32), cl::cat(PollyCategory));133 134static cl::list<int>135 FirstLevelTileSizes("polly-tile-sizes",136 cl::desc("A tile size for each loop dimension, filled "137 "with --polly-default-tile-size"),138 cl::Hidden, cl::CommaSeparated, cl::cat(PollyCategory));139 140static cl::opt<bool>141 SecondLevelTiling("polly-2nd-level-tiling",142 cl::desc("Enable a 2nd level loop of loop tiling"),143 cl::cat(PollyCategory));144 145static cl::opt<int> SecondLevelDefaultTileSize(146 "polly-2nd-level-default-tile-size",147 cl::desc("The default 2nd-level tile size (if not enough were provided by"148 " --polly-2nd-level-tile-sizes)"),149 cl::Hidden, cl::init(16), cl::cat(PollyCategory));150 151static cl::list<int>152 SecondLevelTileSizes("polly-2nd-level-tile-sizes",153 cl::desc("A tile size for each loop dimension, filled "154 "with --polly-default-tile-size"),155 cl::Hidden, cl::CommaSeparated,156 cl::cat(PollyCategory));157 158static cl::opt<bool> RegisterTiling("polly-register-tiling",159 cl::desc("Enable register tiling"),160 cl::cat(PollyCategory));161 162static cl::opt<int> RegisterDefaultTileSize(163 "polly-register-tiling-default-tile-size",164 cl::desc("The default register tile size (if not enough were provided by"165 " --polly-register-tile-sizes)"),166 cl::Hidden, cl::init(2), cl::cat(PollyCategory));167 168static cl::list<int>169 RegisterTileSizes("polly-register-tile-sizes",170 cl::desc("A tile size for each loop dimension, filled "171 "with --polly-register-tile-size"),172 cl::Hidden, cl::CommaSeparated, cl::cat(PollyCategory));173 174static cl::opt<bool> PragmaBasedOpts(175 "polly-pragma-based-opts",176 cl::desc("Apply user-directed transformation from metadata"),177 cl::init(true), cl::cat(PollyCategory));178 179static cl::opt<bool> EnableReschedule("polly-reschedule",180 cl::desc("Optimize SCoPs using ISL"),181 cl::init(true), cl::cat(PollyCategory));182 183static cl::opt<bool>184 PMBasedOpts("polly-pattern-matching-based-opts",185 cl::desc("Perform optimizations based on pattern matching"),186 cl::init(true), cl::cat(PollyCategory));187 188static cl::opt<bool>189 EnablePostopts("polly-postopts",190 cl::desc("Apply post-rescheduling optimizations such as "191 "tiling (requires -polly-reschedule)"),192 cl::init(true), cl::cat(PollyCategory));193 194static cl::opt<bool> OptimizedScops(195 "polly-optimized-scops",196 cl::desc("Polly - Dump polyhedral description of Scops optimized with "197 "the isl scheduling optimizer and the set of post-scheduling "198 "transformations is applied on the schedule tree"),199 cl::cat(PollyCategory));200 201static cl::opt<bool> PollyPrintOptIsl("polly-print-opt-isl",202 cl::desc("A polly pass"),203 cl::cat(PollyCategory));204 205STATISTIC(ScopsProcessed, "Number of scops processed");206STATISTIC(ScopsRescheduled, "Number of scops rescheduled");207STATISTIC(ScopsOptimized, "Number of scops optimized");208 209STATISTIC(NumAffineLoopsOptimized, "Number of affine loops optimized");210STATISTIC(NumBoxedLoopsOptimized, "Number of boxed loops optimized");211 212#define THREE_STATISTICS(VARNAME, DESC) \213 static Statistic VARNAME[3] = { \214 {DEBUG_TYPE, #VARNAME "0", DESC " (original)"}, \215 {DEBUG_TYPE, #VARNAME "1", DESC " (after scheduler)"}, \216 {DEBUG_TYPE, #VARNAME "2", DESC " (after optimizer)"}}217 218THREE_STATISTICS(NumBands, "Number of bands");219THREE_STATISTICS(NumBandMembers, "Number of band members");220THREE_STATISTICS(NumCoincident, "Number of coincident band members");221THREE_STATISTICS(NumPermutable, "Number of permutable bands");222THREE_STATISTICS(NumFilters, "Number of filter nodes");223THREE_STATISTICS(NumExtension, "Number of extension nodes");224 225STATISTIC(FirstLevelTileOpts, "Number of first level tiling applied");226STATISTIC(SecondLevelTileOpts, "Number of second level tiling applied");227STATISTIC(RegisterTileOpts, "Number of register tiling applied");228STATISTIC(PrevectOpts, "Number of strip-mining for prevectorization applied");229STATISTIC(MatMulOpts,230 "Number of matrix multiplication patterns detected and optimized");231 232namespace {233/// Additional parameters of the schedule optimizer.234///235/// Target Transform Info and the SCoP dependencies used by the schedule236/// optimizer.237struct OptimizerAdditionalInfoTy {238 const llvm::TargetTransformInfo *TTI;239 const Dependences *D;240 bool PatternOpts;241 bool Postopts;242 bool Prevect;243 bool &DepsChanged;244 IslMaxOperationsGuard &MaxOpGuard;245};246 247class ScheduleTreeOptimizer final {248public:249 /// Apply schedule tree transformations.250 ///251 /// This function takes an (possibly already optimized) schedule tree and252 /// applies a set of additional optimizations on the schedule tree. The253 /// transformations applied include:254 ///255 /// - Pattern-based optimizations256 /// - Tiling257 /// - Prevectorization258 ///259 /// @param Schedule The schedule object the transformations will be applied260 /// to.261 /// @param OAI Target Transform Info and the SCoP dependencies.262 /// @returns The transformed schedule.263 static isl::schedule264 optimizeSchedule(isl::schedule Schedule,265 const OptimizerAdditionalInfoTy *OAI = nullptr);266 267 /// Apply schedule tree transformations.268 ///269 /// This function takes a node in an (possibly already optimized) schedule270 /// tree and applies a set of additional optimizations on this schedule tree271 /// node and its descendants. The transformations applied include:272 ///273 /// - Pattern-based optimizations274 /// - Tiling275 /// - Prevectorization276 ///277 /// @param Node The schedule object post-transformations will be applied to.278 /// @param OAI Target Transform Info and the SCoP dependencies.279 /// @returns The transformed schedule.280 static isl::schedule_node281 optimizeScheduleNode(isl::schedule_node Node,282 const OptimizerAdditionalInfoTy *OAI = nullptr);283 284 /// Decide if the @p NewSchedule is profitable for @p S.285 ///286 /// @param S The SCoP we optimize.287 /// @param NewSchedule The new schedule we computed.288 ///289 /// @return True, if we believe @p NewSchedule is an improvement for @p S.290 static bool isProfitableSchedule(polly::Scop &S, isl::schedule NewSchedule);291 292 /// Isolate a set of partial tile prefixes.293 ///294 /// This set should ensure that it contains only partial tile prefixes that295 /// have exactly VectorWidth iterations.296 ///297 /// @param Node A schedule node band, which is a parent of a band node,298 /// that contains a vector loop.299 /// @return Modified isl_schedule_node.300 static isl::schedule_node isolateFullPartialTiles(isl::schedule_node Node,301 int VectorWidth);302 303private:304 /// Check if this node is a band node we want to tile.305 ///306 /// We look for innermost band nodes where individual dimensions are marked as307 /// permutable.308 ///309 /// @param Node The node to check.310 static bool isTileableBandNode(isl::schedule_node Node);311 312 /// Check if this node is a band node we want to transform using pattern313 /// matching.314 ///315 /// We look for innermost band nodes where individual dimensions are marked as316 /// permutable. There is no restriction on the number of individual317 /// dimensions.318 ///319 /// @param Node The node to check.320 static bool isPMOptimizableBandNode(isl::schedule_node Node);321 322 /// Pre-vectorizes one scheduling dimension of a schedule band.323 ///324 /// prevectSchedBand splits out the dimension DimToVectorize, tiles it and325 /// sinks the resulting point loop.326 ///327 /// Example (DimToVectorize=0, VectorWidth=4):328 ///329 /// | Before transformation:330 /// |331 /// | A[i,j] -> [i,j]332 /// |333 /// | for (i = 0; i < 128; i++)334 /// | for (j = 0; j < 128; j++)335 /// | A(i,j);336 ///337 /// | After transformation:338 /// |339 /// | for (it = 0; it < 32; it+=1)340 /// | for (j = 0; j < 128; j++)341 /// | for (ip = 0; ip <= 3; ip++)342 /// | A(4 * it + ip,j);343 ///344 /// The goal of this transformation is to create a trivially vectorizable345 /// loop. This means a parallel loop at the innermost level that has a346 /// constant number of iterations corresponding to the target vector width.347 ///348 /// This transformation creates a loop at the innermost level. The loop has349 /// a constant number of iterations, if the number of loop iterations at350 /// DimToVectorize can be divided by VectorWidth. The default VectorWidth is351 /// currently constant and not yet target specific. This function does not352 /// reason about parallelism.353 static isl::schedule_node prevectSchedBand(isl::schedule_node Node,354 unsigned DimToVectorize,355 int VectorWidth);356 357 /// Apply additional optimizations on the bands in the schedule tree.358 ///359 /// We are looking for an innermost band node and apply the following360 /// transformations:361 ///362 /// - Tile the band363 /// - if the band is tileable364 /// - if the band has more than one loop dimension365 ///366 /// - Prevectorize the schedule of the band (or the point loop in case of367 /// tiling).368 /// - if vectorization is enabled369 ///370 /// @param Node The schedule node to (possibly) optimize.371 /// @param User A pointer to forward some use information372 /// (currently unused).373 static isl_schedule_node *optimizeBand(isl_schedule_node *Node, void *User);374 375 /// Apply tiling optimizations on the bands in the schedule tree.376 ///377 /// @param Node The schedule node to (possibly) optimize.378 static isl::schedule_node applyTileBandOpt(isl::schedule_node Node);379 380 /// Apply prevectorization on the bands in the schedule tree.381 ///382 /// @param Node The schedule node to (possibly) prevectorize.383 static isl::schedule_node applyPrevectBandOpt(isl::schedule_node Node);384};385 386isl::schedule_node387ScheduleTreeOptimizer::isolateFullPartialTiles(isl::schedule_node Node,388 int VectorWidth) {389 if (Node.is_null())390 return {};391 assert(isl_schedule_node_get_type(Node.get()) == isl_schedule_node_band);392 Node = Node.child(0).child(0);393 isl::union_map SchedRelUMap = Node.get_prefix_schedule_relation();394 isl::union_set ScheduleRangeUSet = SchedRelUMap.range();395 isl::set ScheduleRange{ScheduleRangeUSet};396 isl::set IsolateDomain = getPartialTilePrefixes(ScheduleRange, VectorWidth);397 auto AtomicOption = getDimOptions(IsolateDomain.ctx(), "atomic");398 isl::union_set IsolateOption = getIsolateOptions(IsolateDomain, 1);399 Node = Node.parent().parent();400 isl::union_set Options = IsolateOption.unite(AtomicOption);401 if (Node.is_null())402 return {};403 isl::schedule_node_band Result =404 Node.as<isl::schedule_node_band>().set_ast_build_options(Options);405 return Result;406}407 408struct InsertSimdMarkers final : ScheduleNodeRewriter<InsertSimdMarkers> {409 isl::schedule_node visitBand(isl::schedule_node_band Band) {410 isl::schedule_node Node = visitChildren(Band);411 412 // Only add SIMD markers to innermost bands.413 if (!Node.first_child().isa<isl::schedule_node_leaf>())414 return Node;415 416 isl::id LoopMarker = isl::id::alloc(Band.ctx(), "SIMD", nullptr);417 return Band.insert_mark(LoopMarker);418 }419};420 421isl::schedule_node ScheduleTreeOptimizer::prevectSchedBand(422 isl::schedule_node Node, unsigned DimToVectorize, int VectorWidth) {423 if (Node.is_null())424 return {};425 assert(isl_schedule_node_get_type(Node.get()) == isl_schedule_node_band);426 427 auto Space = isl::manage(isl_schedule_node_band_get_space(Node.get()));428 if (Space.is_null())429 return {};430 unsigned ScheduleDimensions = unsignedFromIslSize(Space.dim(isl::dim::set));431 assert(DimToVectorize < ScheduleDimensions);432 433 if (DimToVectorize > 0) {434 Node = isl::manage(435 isl_schedule_node_band_split(Node.release(), DimToVectorize));436 Node = Node.child(0);437 }438 if (DimToVectorize < ScheduleDimensions - 1)439 Node = isl::manage(isl_schedule_node_band_split(Node.release(), 1));440 Space = isl::manage(isl_schedule_node_band_get_space(Node.get()));441 auto Sizes = isl::multi_val::zero(Space);442 Sizes = Sizes.set_val(0, isl::val(Node.ctx(), VectorWidth));443 Node =444 isl::manage(isl_schedule_node_band_tile(Node.release(), Sizes.release()));445 Node = isolateFullPartialTiles(Node, VectorWidth);446 Node = Node.child(0);447 // Make sure the "trivially vectorizable loop" is not unrolled. Otherwise,448 // we will have troubles to match it in the backend.449 Node = Node.as<isl::schedule_node_band>().set_ast_build_options(450 isl::union_set(Node.ctx(), "{ unroll[x]: 1 = 0 }"));451 452 // Sink the inner loop into the smallest possible statements to make them453 // represent a single vector instruction if possible.454 Node = isl::manage(isl_schedule_node_band_sink(Node.release()));455 if (Node.is_null())456 return {};457 458 // Add SIMD markers to those vector statements.459 InsertSimdMarkers SimdMarkerInserter;460 Node = SimdMarkerInserter.visit(Node);461 462 if (!Node.is_null())463 PrevectOpts++;464 return Node.parent();465}466 467static bool isSimpleInnermostBand(const isl::schedule_node &Node) {468 assert(isl_schedule_node_get_type(Node.get()) == isl_schedule_node_band);469 assert(isl_schedule_node_n_children(Node.get()) == 1);470 471 auto ChildType = isl_schedule_node_get_type(Node.child(0).get());472 473 if (ChildType == isl_schedule_node_leaf)474 return true;475 476 if (ChildType != isl_schedule_node_sequence)477 return false;478 479 auto Sequence = Node.child(0);480 481 for (int c = 0, nc = isl_schedule_node_n_children(Sequence.get()); c < nc;482 ++c) {483 auto Child = Sequence.child(c);484 if (isl_schedule_node_get_type(Child.get()) != isl_schedule_node_filter)485 return false;486 if (isl_schedule_node_get_type(Child.child(0).get()) !=487 isl_schedule_node_leaf)488 return false;489 }490 return true;491}492 493/// Check if this node is a band node, which has only one child.494///495/// @param Node The node to check.496static bool isOneTimeParentBandNode(isl::schedule_node Node) {497 if (isl_schedule_node_get_type(Node.get()) != isl_schedule_node_band)498 return false;499 500 if (isl_schedule_node_n_children(Node.get()) != 1)501 return false;502 503 return true;504}505 506bool ScheduleTreeOptimizer::isTileableBandNode(isl::schedule_node Node) {507 if (!isOneTimeParentBandNode(Node))508 return false;509 510 if (!isl_schedule_node_band_get_permutable(Node.get()))511 return false;512 513 auto Space = isl::manage(isl_schedule_node_band_get_space(Node.get()));514 515 if (unsignedFromIslSize(Space.dim(isl::dim::set)) <= 1u)516 return false;517 518 return isSimpleInnermostBand(Node);519}520 521bool ScheduleTreeOptimizer::isPMOptimizableBandNode(isl::schedule_node Node) {522 if (!isOneTimeParentBandNode(Node))523 return false;524 525 return Node.child(0).isa<isl::schedule_node_leaf>();526}527 528__isl_give isl::schedule_node529ScheduleTreeOptimizer::applyTileBandOpt(isl::schedule_node Node) {530 if (FirstLevelTiling) {531 Node = tileNode(Node, "1st level tiling", FirstLevelTileSizes,532 FirstLevelDefaultTileSize);533 FirstLevelTileOpts++;534 }535 536 if (SecondLevelTiling) {537 Node = tileNode(Node, "2nd level tiling", SecondLevelTileSizes,538 SecondLevelDefaultTileSize);539 SecondLevelTileOpts++;540 }541 542 if (RegisterTiling) {543 Node =544 applyRegisterTiling(Node, RegisterTileSizes, RegisterDefaultTileSize);545 RegisterTileOpts++;546 }547 548 return Node;549}550 551isl::schedule_node552ScheduleTreeOptimizer::applyPrevectBandOpt(isl::schedule_node Node) {553 auto Space = isl::manage(isl_schedule_node_band_get_space(Node.get()));554 if (Space.is_null())555 return {};556 int Dims = unsignedFromIslSize(Space.dim(isl::dim::set));557 558 for (int i = Dims - 1; i >= 0; i--)559 if (Node.as<isl::schedule_node_band>().member_get_coincident(i)) {560 Node = prevectSchedBand(Node, i, PrevectorWidth);561 break;562 }563 564 return Node;565}566 567__isl_give isl_schedule_node *568ScheduleTreeOptimizer::optimizeBand(__isl_take isl_schedule_node *NodeArg,569 void *User) {570 const OptimizerAdditionalInfoTy *OAI =571 static_cast<const OptimizerAdditionalInfoTy *>(User);572 assert(OAI && "Expecting optimization options");573 574 isl::schedule_node Node = isl::manage(NodeArg);575 576 if (OAI->PatternOpts && isPMOptimizableBandNode(Node)) {577 isl::schedule_node PatternOptimizedSchedule =578 tryOptimizeMatMulPattern(Node, OAI->TTI, OAI->D);579 if (!PatternOptimizedSchedule.is_null()) {580 MatMulOpts++;581 OAI->DepsChanged = true;582 return PatternOptimizedSchedule.release();583 }584 }585 586 if (!isTileableBandNode(Node))587 return Node.release();588 589 if (OAI->Postopts)590 Node = applyTileBandOpt(Node);591 592 if (OAI->Prevect) {593 IslQuotaScope MaxScope = OAI->MaxOpGuard.enter();594 595 // FIXME: Prevectorization requirements are different from those checked by596 // isTileableBandNode.597 Node = applyPrevectBandOpt(Node);598 599 if (OAI->MaxOpGuard.hasQuotaExceeded() || Node.is_null())600 return (isl::schedule_node()).release();601 }602 603 return Node.release();604}605 606isl::schedule607ScheduleTreeOptimizer::optimizeSchedule(isl::schedule Schedule,608 const OptimizerAdditionalInfoTy *OAI) {609 auto Root = Schedule.get_root();610 Root = optimizeScheduleNode(Root, OAI);611 return Root.get_schedule();612}613 614isl::schedule_node ScheduleTreeOptimizer::optimizeScheduleNode(615 isl::schedule_node Node, const OptimizerAdditionalInfoTy *OAI) {616 Node = isl::manage(isl_schedule_node_map_descendant_bottom_up(617 Node.release(), optimizeBand,618 const_cast<void *>(static_cast<const void *>(OAI))));619 return Node;620}621 622bool ScheduleTreeOptimizer::isProfitableSchedule(Scop &S,623 isl::schedule NewSchedule) {624 // To understand if the schedule has been optimized we check if the schedule625 // has changed at all.626 // TODO: We can improve this by tracking if any necessarily beneficial627 // transformations have been performed. This can e.g. be tiling, loop628 // interchange, or ...) We can track this either at the place where the629 // transformation has been performed or, in case of automatic ILP based630 // optimizations, by comparing (yet to be defined) performance metrics631 // before/after the scheduling optimizer632 // (e.g., #stride-one accesses)633 // FIXME: A schedule tree whose union_map-conversion is identical to the634 // original schedule map may still allow for parallelization, i.e. can still635 // be profitable.636 auto NewScheduleMap = NewSchedule.get_map();637 auto OldSchedule = S.getSchedule();638 assert(!OldSchedule.is_null() &&639 "Only IslScheduleOptimizer can insert extension nodes "640 "that make Scop::getSchedule() return nullptr.");641 bool changed = !OldSchedule.is_equal(NewScheduleMap);642 return changed;643}644 645#ifndef NDEBUG646static void printSchedule(llvm::raw_ostream &OS, const isl::schedule &Schedule,647 StringRef Desc) {648 isl::ctx Ctx = Schedule.ctx();649 isl_printer *P = isl_printer_to_str(Ctx.get());650 P = isl_printer_set_yaml_style(P, ISL_YAML_STYLE_BLOCK);651 P = isl_printer_print_schedule(P, Schedule.get());652 char *Str = isl_printer_get_str(P);653 OS << Desc << ": \n" << Str << "\n";654 free(Str);655 isl_printer_free(P);656}657#endif658 659/// Collect statistics for the schedule tree.660///661/// @param Schedule The schedule tree to analyze. If not a schedule tree it is662/// ignored.663/// @param Version The version of the schedule tree that is analyzed.664/// 0 for the original schedule tree before any transformation.665/// 1 for the schedule tree after isl's rescheduling.666/// 2 for the schedule tree after optimizations are applied667/// (tiling, pattern matching)668static void walkScheduleTreeForStatistics(isl::schedule Schedule, int Version) {669 auto Root = Schedule.get_root();670 if (Root.is_null())671 return;672 673 isl_schedule_node_foreach_descendant_top_down(674 Root.get(),675 [](__isl_keep isl_schedule_node *nodeptr, void *user) -> isl_bool {676 isl::schedule_node Node = isl::manage_copy(nodeptr);677 int Version = *static_cast<int *>(user);678 679 switch (isl_schedule_node_get_type(Node.get())) {680 case isl_schedule_node_band: {681 NumBands[Version]++;682 if (isl_schedule_node_band_get_permutable(Node.get()) ==683 isl_bool_true)684 NumPermutable[Version]++;685 686 int CountMembers = isl_schedule_node_band_n_member(Node.get());687 NumBandMembers[Version] += CountMembers;688 for (int i = 0; i < CountMembers; i += 1) {689 if (Node.as<isl::schedule_node_band>().member_get_coincident(i))690 NumCoincident[Version]++;691 }692 break;693 }694 695 case isl_schedule_node_filter:696 NumFilters[Version]++;697 break;698 699 case isl_schedule_node_extension:700 NumExtension[Version]++;701 break;702 703 default:704 break;705 }706 707 return isl_bool_true;708 },709 &Version);710}711 712static void runIslScheduleOptimizerImpl(713 Scop &S,714 function_ref<const Dependences &(Dependences::AnalysisLevel)> GetDeps,715 TargetTransformInfo *TTI, OptimizationRemarkEmitter *ORE,716 isl::schedule &LastSchedule, bool &DepsChanged) {717 // Skip empty SCoPs but still allow code generation as it will delete the718 // loops present but not needed.719 if (S.getSize() == 0) {720 S.markAsOptimized();721 return;722 }723 724 ScopsProcessed++;725 726 // Schedule without optimizations.727 isl::schedule Schedule = S.getScheduleTree();728 walkScheduleTreeForStatistics(S.getScheduleTree(), 0);729 POLLY_DEBUG(printSchedule(dbgs(), Schedule, "Original schedule tree"));730 731 bool HasUserTransformation = false;732 if (PragmaBasedOpts) {733 isl::schedule ManuallyTransformed = applyManualTransformations(734 &S, Schedule, GetDeps(Dependences::AL_Statement), ORE);735 if (ManuallyTransformed.is_null()) {736 POLLY_DEBUG(dbgs() << "Error during manual optimization\n");737 return;738 }739 740 if (ManuallyTransformed.get() != Schedule.get()) {741 // User transformations have precedence over other transformations.742 HasUserTransformation = true;743 Schedule = std::move(ManuallyTransformed);744 POLLY_DEBUG(745 printSchedule(dbgs(), Schedule, "After manual transformations"));746 }747 }748 749 // Only continue if either manual transformations have been applied or we are750 // allowed to apply heuristics.751 // TODO: Detect disabled heuristics and no user-directed transformation752 // metadata earlier in ScopDetection.753 if (!HasUserTransformation && S.hasDisableHeuristicsHint()) {754 POLLY_DEBUG(dbgs() << "Heuristic optimizations disabled by metadata\n");755 return;756 }757 758 // Get dependency analysis.759 const Dependences &D = GetDeps(Dependences::AL_Statement);760 if (D.getSharedIslCtx() != S.getSharedIslCtx()) {761 POLLY_DEBUG(dbgs() << "DependenceInfo for another SCoP/isl_ctx\n");762 return;763 }764 if (!D.hasValidDependences()) {765 POLLY_DEBUG(dbgs() << "Dependency information not available\n");766 return;767 }768 769 isl_ctx *Ctx = S.getIslCtx().get();770 IslMaxOperationsGuard MaxOpGuard(Ctx, ScheduleComputeOut,771 /*AutoEnter=*/false);772 773 // Apply ISL's algorithm only if not overridden by the user. Note that774 // post-rescheduling optimizations (tiling, pattern-based, prevectorization)775 // rely on the coincidence/permutable annotations on schedule tree bands that776 // are added by the rescheduling analyzer. Therefore, disabling the777 // rescheduler implicitly also disables these optimizations.778 if (!EnableReschedule) {779 POLLY_DEBUG(dbgs() << "Skipping rescheduling due to command line option\n");780 } else if (HasUserTransformation) {781 POLLY_DEBUG(782 dbgs() << "Skipping rescheduling due to manual transformation\n");783 } else {784 // Build input data.785 int ValidityKinds =786 Dependences::TYPE_RAW | Dependences::TYPE_WAR | Dependences::TYPE_WAW;787 int ProximityKinds;788 789 if (OptimizeDeps == "all")790 ProximityKinds =791 Dependences::TYPE_RAW | Dependences::TYPE_WAR | Dependences::TYPE_WAW;792 else if (OptimizeDeps == "raw")793 ProximityKinds = Dependences::TYPE_RAW;794 else {795 errs() << "Do not know how to optimize for '" << OptimizeDeps << "'"796 << " Falling back to optimizing all dependences.\n";797 ProximityKinds =798 Dependences::TYPE_RAW | Dependences::TYPE_WAR | Dependences::TYPE_WAW;799 }800 801 isl::union_set Domain = S.getDomains();802 803 if (Domain.is_null())804 return;805 806 isl::union_map Validity = D.getDependences(ValidityKinds);807 isl::union_map Proximity = D.getDependences(ProximityKinds);808 809 // Simplify the dependences by removing the constraints introduced by the810 // domains. This can speed up the scheduling time significantly, as large811 // constant coefficients will be removed from the dependences. The812 // introduction of some additional dependences reduces the possible813 // transformations, but in most cases, such transformation do not seem to be814 // interesting anyway. In some cases this option may stop the scheduler to815 // find any schedule.816 if (SimplifyDeps == "yes") {817 Validity = Validity.gist_domain(Domain);818 Validity = Validity.gist_range(Domain);819 Proximity = Proximity.gist_domain(Domain);820 Proximity = Proximity.gist_range(Domain);821 } else if (SimplifyDeps != "no") {822 errs()823 << "warning: Option -polly-opt-simplify-deps should either be 'yes' "824 "or 'no'. Falling back to default: 'yes'\n";825 }826 827 POLLY_DEBUG(dbgs() << "\n\nCompute schedule from: ");828 POLLY_DEBUG(dbgs() << "Domain := " << Domain << ";\n");829 POLLY_DEBUG(dbgs() << "Proximity := " << Proximity << ";\n");830 POLLY_DEBUG(dbgs() << "Validity := " << Validity << ";\n");831 832 int IslMaximizeBands;833 if (MaximizeBandDepth == "yes") {834 IslMaximizeBands = 1;835 } else if (MaximizeBandDepth == "no") {836 IslMaximizeBands = 0;837 } else {838 errs()839 << "warning: Option -polly-opt-maximize-bands should either be 'yes'"840 " or 'no'. Falling back to default: 'yes'\n";841 IslMaximizeBands = 1;842 }843 844 int IslOuterCoincidence;845 if (OuterCoincidence == "yes") {846 IslOuterCoincidence = 1;847 } else if (OuterCoincidence == "no") {848 IslOuterCoincidence = 0;849 } else {850 errs() << "warning: Option -polly-opt-outer-coincidence should either be "851 "'yes' or 'no'. Falling back to default: 'no'\n";852 IslOuterCoincidence = 0;853 }854 855 isl_options_set_schedule_outer_coincidence(Ctx, IslOuterCoincidence);856 isl_options_set_schedule_maximize_band_depth(Ctx, IslMaximizeBands);857 isl_options_set_schedule_max_constant_term(Ctx, MaxConstantTerm);858 isl_options_set_schedule_max_coefficient(Ctx, MaxCoefficient);859 isl_options_set_tile_scale_tile_loops(Ctx, 0);860 861 auto OnErrorStatus = isl_options_get_on_error(Ctx);862 isl_options_set_on_error(Ctx, ISL_ON_ERROR_CONTINUE);863 864 auto SC = isl::schedule_constraints::on_domain(Domain);865 SC = SC.set_proximity(Proximity);866 SC = SC.set_validity(Validity);867 SC = SC.set_coincidence(Validity);868 869 {870 IslQuotaScope MaxOpScope = MaxOpGuard.enter();871 Schedule = SC.compute_schedule();872 }873 874 isl_options_set_on_error(Ctx, OnErrorStatus);875 876 if (!Schedule.is_null())877 ScopsRescheduled++;878 POLLY_DEBUG(printSchedule(dbgs(), Schedule, "After rescheduling"));879 }880 881 walkScheduleTreeForStatistics(Schedule, 1);882 883 if (GreedyFusion && !Schedule.is_null()) {884 isl::union_map Validity = D.getDependences(885 Dependences::TYPE_RAW | Dependences::TYPE_WAR | Dependences::TYPE_WAW);886 Schedule = applyGreedyFusion(Schedule, Validity);887 assert(!Schedule.is_null());888 }889 890 // Apply post-rescheduling optimizations (if enabled) and/or prevectorization.891 const OptimizerAdditionalInfoTy OAI = {892 TTI,893 const_cast<Dependences *>(&D),894 /*PatternOpts=*/!HasUserTransformation && PMBasedOpts,895 /*Postopts=*/!HasUserTransformation && EnablePostopts,896 /*Prevect=*/PollyVectorizerChoice != VECTORIZER_NONE,897 DepsChanged,898 MaxOpGuard};899 if (!Schedule.is_null() && (OAI.PatternOpts || OAI.Postopts || OAI.Prevect)) {900 Schedule = ScheduleTreeOptimizer::optimizeSchedule(Schedule, &OAI);901 Schedule = hoistExtensionNodes(Schedule);902 POLLY_DEBUG(printSchedule(dbgs(), Schedule, "After post-optimizations"));903 walkScheduleTreeForStatistics(Schedule, 2);904 }905 906 // Check for why any computation could have failed907 if (MaxOpGuard.hasQuotaExceeded()) {908 POLLY_DEBUG(dbgs() << "Schedule optimizer calculation exceeds ISL quota\n");909 return;910 } else if (isl_ctx_last_error(Ctx) != isl_error_none) {911 POLLY_DEBUG({912 const char *File = isl_ctx_last_error_file(Ctx);913 int Line = isl_ctx_last_error_line(Ctx);914 const char *Msg = isl_ctx_last_error_msg(Ctx);915 dbgs() << "ISL reported an error during the computation of a new "916 "schedule at "917 << File << ":" << Line << ": " << Msg;918 });919 isl_ctx_reset_error(Ctx);920 return;921 } else if (Schedule.is_null()) {922 POLLY_DEBUG(dbgs() << "Schedule optimizer did not compute a new schedule "923 "for unknown reasons\n");924 return;925 }926 927 // Skip profitability check if user transformation(s) have been applied.928 if (!HasUserTransformation &&929 !ScheduleTreeOptimizer::isProfitableSchedule(S, Schedule))930 return;931 932 auto ScopStats = S.getStatistics();933 ScopsOptimized++;934 NumAffineLoopsOptimized += ScopStats.NumAffineLoops;935 NumBoxedLoopsOptimized += ScopStats.NumBoxedLoops;936 LastSchedule = Schedule;937 938 S.setScheduleTree(Schedule);939 S.markAsOptimized();940 941 if (OptimizedScops)942 errs() << S;943}944 945static void runScheduleOptimizerPrinter(raw_ostream &OS,946 isl::schedule LastSchedule) {947 isl_printer *p;948 char *ScheduleStr;949 950 OS << "Calculated schedule:\n";951 952 if (LastSchedule.is_null()) {953 OS << "n/a\n";954 return;955 }956 957 p = isl_printer_to_str(LastSchedule.ctx().get());958 p = isl_printer_set_yaml_style(p, ISL_YAML_STYLE_BLOCK);959 p = isl_printer_print_schedule(p, LastSchedule.get());960 ScheduleStr = isl_printer_get_str(p);961 isl_printer_free(p);962 963 OS << ScheduleStr << "\n";964 965 free(ScheduleStr);966}967 968} // namespace969 970void polly::runIslScheduleOptimizer(Scop &S, TargetTransformInfo *TTI,971 DependenceAnalysis::Result &Deps) {972 auto GetDeps = [&Deps](Dependences::AnalysisLevel) -> const Dependences & {973 return Deps.getDependences(Dependences::AL_Statement);974 };975 OptimizationRemarkEmitter ORE(&S.getFunction());976 isl::schedule LastSchedule;977 bool DepsChanged = false;978 runIslScheduleOptimizerImpl(S, GetDeps, TTI, &ORE, LastSchedule, DepsChanged);979 if (DepsChanged)980 Deps.abandonDependences();981 982 if (PollyPrintOptIsl) {983 outs()984 << "Printing analysis 'Polly - Optimize schedule of SCoP' for region: '"985 << S.getName() << "' in function '" << S.getFunction().getName()986 << "':\n";987 runScheduleOptimizerPrinter(outs(), LastSchedule);988 }989}990