1091 lines · cpp
1//===- ForwardOpTree.h ------------------------------------------*- C++ -*-===//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// Move instructions between statements.10//11//===----------------------------------------------------------------------===//12 13#include "polly/ForwardOpTree.h"14#include "polly/Options.h"15#include "polly/ScopBuilder.h"16#include "polly/ScopInfo.h"17#include "polly/Support/GICHelper.h"18#include "polly/Support/ISLOStream.h"19#include "polly/Support/ISLTools.h"20#include "polly/Support/VirtualInstruction.h"21#include "polly/ZoneAlgo.h"22#include "llvm/ADT/STLExtras.h"23#include "llvm/ADT/SmallVector.h"24#include "llvm/ADT/Statistic.h"25#include "llvm/Analysis/LoopInfo.h"26#include "llvm/Analysis/ValueTracking.h"27#include "llvm/IR/Instruction.h"28#include "llvm/IR/Instructions.h"29#include "llvm/IR/Value.h"30#include "llvm/Support/Casting.h"31#include "llvm/Support/CommandLine.h"32#include "llvm/Support/Compiler.h"33#include "llvm/Support/Debug.h"34#include "llvm/Support/ErrorHandling.h"35#include "llvm/Support/raw_ostream.h"36#include "isl/ctx.h"37#include "isl/isl-noexceptions.h"38#include <cassert>39#include <memory>40 41#include "polly/Support/PollyDebug.h"42#define DEBUG_TYPE "polly-optree"43 44using namespace llvm;45using namespace polly;46 47static cl::opt<bool>48 AnalyzeKnown("polly-optree-analyze-known",49 cl::desc("Analyze array contents for load forwarding"),50 cl::cat(PollyCategory), cl::init(true), cl::Hidden);51 52static cl::opt<bool>53 NormalizePHIs("polly-optree-normalize-phi",54 cl::desc("Replace PHIs by their incoming values"),55 cl::cat(PollyCategory), cl::init(false), cl::Hidden);56 57static cl::opt<unsigned>58 MaxOps("polly-optree-max-ops",59 cl::desc("Maximum number of ISL operations to invest for known "60 "analysis; 0=no limit"),61 cl::init(1000000), cl::cat(PollyCategory), cl::Hidden);62 63static cl::opt<bool>64 PollyPrintOptree("polly-print-optree",65 cl::desc("Polly - Print forward operand tree result"),66 cl::cat(PollyCategory));67 68STATISTIC(KnownAnalyzed, "Number of successfully analyzed SCoPs");69STATISTIC(KnownOutOfQuota,70 "Analyses aborted because max_operations was reached");71 72STATISTIC(TotalInstructionsCopied, "Number of copied instructions");73STATISTIC(TotalKnownLoadsForwarded,74 "Number of forwarded loads because their value was known");75STATISTIC(TotalReloads, "Number of reloaded values");76STATISTIC(TotalReadOnlyCopied, "Number of copied read-only accesses");77STATISTIC(TotalForwardedTrees, "Number of forwarded operand trees");78STATISTIC(TotalModifiedStmts,79 "Number of statements with at least one forwarded tree");80 81STATISTIC(ScopsModified, "Number of SCoPs with at least one forwarded tree");82 83STATISTIC(NumValueWrites, "Number of scalar value writes after OpTree");84STATISTIC(NumValueWritesInLoops,85 "Number of scalar value writes nested in affine loops after OpTree");86STATISTIC(NumPHIWrites, "Number of scalar phi writes after OpTree");87STATISTIC(NumPHIWritesInLoops,88 "Number of scalar phi writes nested in affine loops after OpTree");89STATISTIC(NumSingletonWrites, "Number of singleton writes after OpTree");90STATISTIC(NumSingletonWritesInLoops,91 "Number of singleton writes nested in affine loops after OpTree");92 93namespace {94 95/// The state of whether an operand tree was/can be forwarded.96///97/// The items apply to an instructions and its operand tree with the instruction98/// as the root element. If the value in question is not an instruction in the99/// SCoP, it can be a leaf of an instruction's operand tree.100enum ForwardingDecision {101 /// An uninitialized value.102 FD_Unknown,103 104 /// The root instruction or value cannot be forwarded at all.105 FD_CannotForward,106 107 /// The root instruction or value can be forwarded as a leaf of a larger108 /// operand tree.109 /// It does not make sense to move the value itself, it would just replace it110 /// by a use of itself. For instance, a constant "5" used in a statement can111 /// be forwarded, but it would just replace it by the same constant "5".112 /// However, it makes sense to move as an operand of113 ///114 /// %add = add 5, 5115 ///116 /// where "5" is moved as part of a larger operand tree. "5" would be placed117 /// (disregarding for a moment that literal constants don't have a location118 /// and can be used anywhere) into the same statement as %add would.119 FD_CanForwardLeaf,120 121 /// The root instruction can be forwarded and doing so avoids a scalar122 /// dependency.123 ///124 /// This can be either because the operand tree can be moved to the target125 /// statement, or a memory access is redirected to read from a different126 /// location.127 FD_CanForwardProfitably,128 129 /// A forwarding method cannot be applied to the operand tree.130 /// The difference to FD_CannotForward is that there might be other methods131 /// that can handle it.132 FD_NotApplicable133};134 135/// Represents the evaluation of and action to taken when forwarding a value136/// from an operand tree.137struct ForwardingAction {138 using KeyTy = std::pair<Value *, ScopStmt *>;139 140 /// Evaluation of forwarding a value.141 ForwardingDecision Decision = FD_Unknown;142 143 /// Callback to execute the forwarding.144 /// Returning true allows deleting the polly::MemoryAccess if the value is the145 /// root of the operand tree (and its elimination the reason why the146 /// forwarding is done). Return false if the MemoryAccess is reused or there147 /// might be other users of the read accesses. In the letter case the148 /// polly::SimplifyPass can remove dead MemoryAccesses.149 std::function<bool()> Execute = []() -> bool {150 llvm_unreachable("unspecified how to forward");151 };152 153 /// Other values that need to be forwarded if this action is executed. Their154 /// actions are executed after this one.155 SmallVector<KeyTy, 4> Depends;156 157 /// Named ctor: The method creating this object does not apply to the kind of158 /// value, but other methods may.159 static ForwardingAction notApplicable() {160 ForwardingAction Result;161 Result.Decision = FD_NotApplicable;162 return Result;163 }164 165 /// Named ctor: The value cannot be forwarded.166 static ForwardingAction cannotForward() {167 ForwardingAction Result;168 Result.Decision = FD_CannotForward;169 return Result;170 }171 172 /// Named ctor: The value can just be used without any preparation.173 static ForwardingAction triviallyForwardable(bool IsProfitable, Value *Val) {174 ForwardingAction Result;175 Result.Decision =176 IsProfitable ? FD_CanForwardProfitably : FD_CanForwardLeaf;177 Result.Execute = [=]() {178 POLLY_DEBUG(dbgs() << " trivially forwarded: " << *Val << "\n");179 return true;180 };181 return Result;182 }183 184 /// Name ctor: The value can be forwarded by executing an action.185 static ForwardingAction canForward(std::function<bool()> Execute,186 ArrayRef<KeyTy> Depends,187 bool IsProfitable) {188 ForwardingAction Result;189 Result.Decision =190 IsProfitable ? FD_CanForwardProfitably : FD_CanForwardLeaf;191 Result.Execute = std::move(Execute);192 Result.Depends.append(Depends.begin(), Depends.end());193 return Result;194 }195};196 197/// Implementation of operand tree forwarding for a specific SCoP.198///199/// For a statement that requires a scalar value (through a value read200/// MemoryAccess), see if its operand can be moved into the statement. If so,201/// the MemoryAccess is removed and the all the operand tree instructions are202/// moved into the statement. All original instructions are left in the source203/// statements. The simplification pass can clean these up.204class ForwardOpTreeImpl final : ZoneAlgorithm {205private:206 using MemoizationTy = DenseMap<ForwardingAction::KeyTy, ForwardingAction>;207 208 /// Scope guard to limit the number of isl operations for this pass.209 IslMaxOperationsGuard &MaxOpGuard;210 211 /// How many instructions have been copied to other statements.212 int NumInstructionsCopied = 0;213 214 /// Number of loads forwarded because their value was known.215 int NumKnownLoadsForwarded = 0;216 217 /// Number of values reloaded from known array elements.218 int NumReloads = 0;219 220 /// How many read-only accesses have been copied.221 int NumReadOnlyCopied = 0;222 223 /// How many operand trees have been forwarded.224 int NumForwardedTrees = 0;225 226 /// Number of statements with at least one forwarded operand tree.227 int NumModifiedStmts = 0;228 229 /// Whether we carried out at least one change to the SCoP.230 bool Modified = false;231 232 /// Cache of how to forward values.233 /// The key of this map is the llvm::Value to be forwarded and the234 /// polly::ScopStmt it is forwarded from. This is because the same llvm::Value235 /// can evaluate differently depending on where it is evaluate. For instance,236 /// a synthesizable Scev represents a recurrence with an loop but the loop's237 /// exit value if evaluated after the loop.238 /// The cached results are only valid for the current TargetStmt.239 /// CHECKME: ScalarEvolution::getScevAtScope should take care for getting the240 /// exit value when instantiated outside of the loop. The primary concern is241 /// ambiguity when crossing PHI nodes, which currently is not supported.242 MemoizationTy ForwardingActions;243 244 /// Contains the zones where array elements are known to contain a specific245 /// value.246 /// { [Element[] -> Zone[]] -> ValInst[] }247 /// @see computeKnown()248 isl::union_map Known;249 250 /// Translator for newly introduced ValInsts to already existing ValInsts such251 /// that new introduced load instructions can reuse the Known analysis of its252 /// original load. { ValInst[] -> ValInst[] }253 isl::union_map Translator;254 255 /// Get list of array elements that do contain the same ValInst[] at Domain[].256 ///257 /// @param ValInst { Domain[] -> ValInst[] }258 /// The values for which we search for alternative locations,259 /// per statement instance.260 ///261 /// @return { Domain[] -> Element[] }262 /// For each statement instance, the array elements that contain the263 /// same ValInst.264 isl::union_map findSameContentElements(isl::union_map ValInst) {265 assert(!ValInst.is_single_valued().is_false());266 267 // { Domain[] }268 isl::union_set Domain = ValInst.domain();269 270 // { Domain[] -> Scatter[] }271 isl::union_map Schedule = getScatterFor(Domain);272 273 // { Element[] -> [Scatter[] -> ValInst[]] }274 isl::union_map MustKnownCurried =275 convertZoneToTimepoints(Known, isl::dim::in, false, true).curry();276 277 // { [Domain[] -> ValInst[]] -> Scatter[] }278 isl::union_map DomValSched = ValInst.domain_map().apply_range(Schedule);279 280 // { [Scatter[] -> ValInst[]] -> [Domain[] -> ValInst[]] }281 isl::union_map SchedValDomVal =282 DomValSched.range_product(ValInst.range_map()).reverse();283 284 // { Element[] -> [Domain[] -> ValInst[]] }285 isl::union_map MustKnownInst = MustKnownCurried.apply_range(SchedValDomVal);286 287 // { Domain[] -> Element[] }288 isl::union_map MustKnownMap =289 MustKnownInst.uncurry().domain().unwrap().reverse();290 simplify(MustKnownMap);291 292 return MustKnownMap;293 }294 295 /// Find a single array element for each statement instance, within a single296 /// array.297 ///298 /// @param MustKnown { Domain[] -> Element[] }299 /// Set of candidate array elements.300 /// @param Domain { Domain[] }301 /// The statement instance for which we need elements for.302 ///303 /// @return { Domain[] -> Element[] }304 /// For each statement instance, an array element out of @p MustKnown.305 /// All array elements must be in the same array (Polly does not yet306 /// support reading from different accesses using the same307 /// MemoryAccess). If no mapping for all of @p Domain exists, returns308 /// null.309 isl::map singleLocation(isl::union_map MustKnown, isl::set Domain) {310 // { Domain[] -> Element[] }311 isl::map Result;312 313 // Make irrelevant elements not interfere.314 Domain = Domain.intersect_params(S->getContext());315 316 // MemoryAccesses can read only elements from a single array317 // (i.e. not: { Dom[0] -> A[0]; Dom[1] -> B[1] }).318 // Look through all spaces until we find one that contains at least the319 // wanted statement instance.s320 for (isl::map Map : MustKnown.get_map_list()) {321 // Get the array this is accessing.322 isl::id ArrayId = Map.get_tuple_id(isl::dim::out);323 ScopArrayInfo *SAI = static_cast<ScopArrayInfo *>(ArrayId.get_user());324 325 // No support for generation of indirect array accesses.326 if (SAI->getBasePtrOriginSAI())327 continue;328 329 // Determine whether this map contains all wanted values.330 isl::set MapDom = Map.domain();331 if (!Domain.is_subset(MapDom).is_true())332 continue;333 334 // There might be multiple array elements that contain the same value, but335 // choose only one of them. lexmin is used because it returns a one-value336 // mapping, we do not care about which one.337 // TODO: Get the simplest access function.338 Result = Map.lexmin();339 break;340 }341 342 return Result;343 }344 345public:346 ForwardOpTreeImpl(Scop *S, LoopInfo *LI, IslMaxOperationsGuard &MaxOpGuard)347 : ZoneAlgorithm("polly-optree", S, LI), MaxOpGuard(MaxOpGuard) {}348 349 /// Compute the zones of known array element contents.350 ///351 /// @return True if the computed #Known is usable.352 bool computeKnownValues() {353 isl::union_map MustKnown, KnownFromLoad, KnownFromInit;354 355 // Check that nothing strange occurs.356 collectCompatibleElts();357 358 {359 IslQuotaScope QuotaScope = MaxOpGuard.enter();360 361 computeCommon();362 if (NormalizePHIs)363 computeNormalizedPHIs();364 Known = computeKnown(true, true);365 366 // Preexisting ValInsts use the known content analysis of themselves.367 Translator = makeIdentityMap(Known.range(), false);368 }369 370 if (Known.is_null() || Translator.is_null() || NormalizeMap.is_null()) {371 assert(isl_ctx_last_error(IslCtx.get()) == isl_error_quota);372 Known = {};373 Translator = {};374 NormalizeMap = {};375 POLLY_DEBUG(dbgs() << "Known analysis exceeded max_operations\n");376 return false;377 }378 379 KnownAnalyzed++;380 POLLY_DEBUG(dbgs() << "All known: " << Known << "\n");381 382 return true;383 }384 385 void printStatistics(raw_ostream &OS, int Indent = 0) {386 OS.indent(Indent) << "Statistics {\n";387 OS.indent(Indent + 4) << "Instructions copied: " << NumInstructionsCopied388 << '\n';389 OS.indent(Indent + 4) << "Known loads forwarded: " << NumKnownLoadsForwarded390 << '\n';391 OS.indent(Indent + 4) << "Reloads: " << NumReloads << '\n';392 OS.indent(Indent + 4) << "Read-only accesses copied: " << NumReadOnlyCopied393 << '\n';394 OS.indent(Indent + 4) << "Operand trees forwarded: " << NumForwardedTrees395 << '\n';396 OS.indent(Indent + 4) << "Statements with forwarded operand trees: "397 << NumModifiedStmts << '\n';398 OS.indent(Indent) << "}\n";399 }400 401 void printStatements(raw_ostream &OS, int Indent = 0) const {402 OS.indent(Indent) << "After statements {\n";403 for (auto &Stmt : *S) {404 OS.indent(Indent + 4) << Stmt.getBaseName() << "\n";405 for (auto *MA : Stmt)406 MA->print(OS);407 408 OS.indent(Indent + 12);409 Stmt.printInstructions(OS);410 }411 OS.indent(Indent) << "}\n";412 }413 414 /// Create a new MemoryAccess of type read and MemoryKind::Array.415 ///416 /// @param Stmt The statement in which the access occurs.417 /// @param LI The instruction that does the access.418 /// @param AccessRelation The array element that each statement instance419 /// accesses.420 ///421 /// @param The newly created access.422 MemoryAccess *makeReadArrayAccess(ScopStmt *Stmt, LoadInst *LI,423 isl::map AccessRelation) {424 isl::id ArrayId = AccessRelation.get_tuple_id(isl::dim::out);425 ScopArrayInfo *SAI = reinterpret_cast<ScopArrayInfo *>(ArrayId.get_user());426 427 // Create a dummy SCEV access, to be replaced anyway.428 SmallVector<const SCEV *, 4> Sizes;429 Sizes.reserve(SAI->getNumberOfDimensions());430 SmallVector<const SCEV *, 4> Subscripts;431 Subscripts.reserve(SAI->getNumberOfDimensions());432 for (unsigned i = 0; i < SAI->getNumberOfDimensions(); i += 1) {433 Sizes.push_back(SAI->getDimensionSize(i));434 Subscripts.push_back(nullptr);435 }436 437 MemoryAccess *Access =438 new MemoryAccess(Stmt, LI, MemoryAccess::READ, SAI->getBasePtr(),439 LI->getType(), true, {}, Sizes, LI, MemoryKind::Array);440 S->addAccessFunction(Access);441 Stmt->addAccess(Access, true);442 443 Access->setNewAccessRelation(AccessRelation);444 445 return Access;446 }447 448 /// Forward a load by reading from an array element that contains the same449 /// value. Typically the location it was loaded from.450 ///451 /// @param TargetStmt The statement the operand tree will be copied to.452 /// @param Inst The (possibly speculatable) instruction to forward.453 /// @param UseStmt The statement that uses @p Inst.454 /// @param UseLoop The loop @p Inst is used in.455 /// @param DefStmt The statement @p Inst is defined in.456 /// @param DefLoop The loop which contains @p Inst.457 ///458 /// @return A ForwardingAction object describing the feasibility and459 /// profitability evaluation and the callback carrying-out the value460 /// forwarding.461 ForwardingAction forwardKnownLoad(ScopStmt *TargetStmt, Instruction *Inst,462 ScopStmt *UseStmt, Loop *UseLoop,463 ScopStmt *DefStmt, Loop *DefLoop) {464 // Cannot do anything without successful known analysis.465 if (Known.is_null() || Translator.is_null() ||466 MaxOpGuard.hasQuotaExceeded())467 return ForwardingAction::notApplicable();468 469 LoadInst *LI = dyn_cast<LoadInst>(Inst);470 if (!LI)471 return ForwardingAction::notApplicable();472 473 ForwardingDecision OpDecision =474 forwardTree(TargetStmt, LI->getPointerOperand(), DefStmt, DefLoop);475 switch (OpDecision) {476 case FD_CanForwardProfitably:477 case FD_CanForwardLeaf:478 break;479 case FD_CannotForward:480 return ForwardingAction::cannotForward();481 default:482 llvm_unreachable("Shouldn't return this");483 }484 485 MemoryAccess *Access = TargetStmt->getArrayAccessOrNULLFor(LI);486 if (Access) {487 // If the load is already in the statement, no forwarding is necessary.488 // However, it might happen that the LoadInst is already present in the489 // statement's instruction list. In that case we do as follows:490 // - For the evaluation, we can trivially forward it as it is491 // benefit of forwarding an already present instruction.492 // - For the execution, prepend the instruction (to make it493 // available to all instructions following in the instruction list), but494 // do not add another MemoryAccess.495 auto ExecAction = [this, TargetStmt, LI, Access]() -> bool {496 TargetStmt->prependInstruction(LI);497 POLLY_DEBUG(498 dbgs() << " forwarded known load with preexisting MemoryAccess"499 << Access << "\n");500 (void)Access;501 502 NumKnownLoadsForwarded++;503 TotalKnownLoadsForwarded++;504 return true;505 };506 return ForwardingAction::canForward(507 ExecAction, {{LI->getPointerOperand(), DefStmt}}, true);508 }509 510 // Allow the following Isl calculations (until we return the511 // ForwardingAction, excluding the code inside the lambda that will be512 // executed later) to fail.513 IslQuotaScope QuotaScope = MaxOpGuard.enter();514 515 // { DomainDef[] -> ValInst[] }516 isl::map ExpectedVal = makeValInst(Inst, UseStmt, UseLoop);517 assert(!isNormalized(ExpectedVal).is_false() &&518 "LoadInsts are always normalized");519 520 // { DomainUse[] -> DomainTarget[] }521 isl::map UseToTarget = getDefToTarget(UseStmt, TargetStmt);522 523 // { DomainTarget[] -> ValInst[] }524 isl::map TargetExpectedVal = ExpectedVal.apply_domain(UseToTarget);525 isl::union_map TranslatedExpectedVal =526 isl::union_map(TargetExpectedVal).apply_range(Translator);527 528 // { DomainTarget[] -> Element[] }529 isl::union_map Candidates = findSameContentElements(TranslatedExpectedVal);530 531 isl::map SameVal = singleLocation(Candidates, getDomainFor(TargetStmt));532 if (SameVal.is_null())533 return ForwardingAction::notApplicable();534 535 POLLY_DEBUG(dbgs() << " expected values where " << TargetExpectedVal536 << "\n");537 POLLY_DEBUG(dbgs() << " candidate elements where " << Candidates538 << "\n");539 540 // { ValInst[] }541 isl::space ValInstSpace = ExpectedVal.get_space().range();542 543 // After adding a new load to the SCoP, also update the Known content544 // about it. The new load will have a known ValInst of545 // { [DomainTarget[] -> Value[]] }546 // but which -- because it is a copy of it -- has same value as the547 // { [DomainDef[] -> Value[]] }548 // that it replicates. Instead of cloning the known content of549 // [DomainDef[] -> Value[]]550 // for DomainTarget[], we add a 'translator' that maps551 // [DomainTarget[] -> Value[]] to [DomainDef[] -> Value[]]552 // before comparing to the known content.553 // TODO: 'Translator' could also be used to map PHINodes to their incoming554 // ValInsts.555 isl::map LocalTranslator;556 if (!ValInstSpace.is_wrapping().is_false()) {557 // { DefDomain[] -> Value[] }558 isl::map ValInsts = ExpectedVal.range().unwrap();559 560 // { DefDomain[] }561 isl::set DefDomain = ValInsts.domain();562 563 // { Value[] }564 isl::space ValSpace = ValInstSpace.unwrap().range();565 566 // { Value[] -> Value[] }567 isl::map ValToVal =568 isl::map::identity(ValSpace.map_from_domain_and_range(ValSpace));569 570 // { DomainDef[] -> DomainTarget[] }571 isl::map DefToTarget = getDefToTarget(DefStmt, TargetStmt);572 573 // { [TargetDomain[] -> Value[]] -> [DefDomain[] -> Value] }574 LocalTranslator = DefToTarget.reverse().product(ValToVal);575 POLLY_DEBUG(dbgs() << " local translator is " << LocalTranslator576 << "\n");577 578 if (LocalTranslator.is_null())579 return ForwardingAction::notApplicable();580 }581 582 auto ExecAction = [this, TargetStmt, LI, SameVal,583 LocalTranslator]() -> bool {584 TargetStmt->prependInstruction(LI);585 MemoryAccess *Access = makeReadArrayAccess(TargetStmt, LI, SameVal);586 POLLY_DEBUG(dbgs() << " forwarded known load with new MemoryAccess"587 << Access << "\n");588 (void)Access;589 590 if (!LocalTranslator.is_null())591 Translator = Translator.unite(LocalTranslator);592 593 NumKnownLoadsForwarded++;594 TotalKnownLoadsForwarded++;595 return true;596 };597 return ForwardingAction::canForward(598 ExecAction, {{LI->getPointerOperand(), DefStmt}}, true);599 }600 601 /// Forward a scalar by redirecting the access to an array element that stores602 /// the same value.603 ///604 /// @param TargetStmt The statement the operand tree will be copied to.605 /// @param Inst The scalar to forward.606 /// @param UseStmt The statement that uses @p Inst.607 /// @param UseLoop The loop @p Inst is used in.608 /// @param DefStmt The statement @p Inst is defined in.609 /// @param DefLoop The loop which contains @p Inst.610 ///611 /// @return A ForwardingAction object describing the feasibility and612 /// profitability evaluation and the callback carrying-out the value613 /// forwarding.614 ForwardingAction reloadKnownContent(ScopStmt *TargetStmt, Instruction *Inst,615 ScopStmt *UseStmt, Loop *UseLoop,616 ScopStmt *DefStmt, Loop *DefLoop) {617 // Cannot do anything without successful known analysis.618 if (Known.is_null() || Translator.is_null() ||619 MaxOpGuard.hasQuotaExceeded())620 return ForwardingAction::notApplicable();621 622 // Don't spend too much time analyzing whether it can be reloaded.623 IslQuotaScope QuotaScope = MaxOpGuard.enter();624 625 // { DomainDef[] -> ValInst[] }626 isl::union_map ExpectedVal = makeNormalizedValInst(Inst, UseStmt, UseLoop);627 628 // { DomainUse[] -> DomainTarget[] }629 isl::map UseToTarget = getDefToTarget(UseStmt, TargetStmt);630 631 // { DomainTarget[] -> ValInst[] }632 isl::union_map TargetExpectedVal = ExpectedVal.apply_domain(UseToTarget);633 isl::union_map TranslatedExpectedVal =634 TargetExpectedVal.apply_range(Translator);635 636 // { DomainTarget[] -> Element[] }637 isl::union_map Candidates = findSameContentElements(TranslatedExpectedVal);638 639 isl::map SameVal = singleLocation(Candidates, getDomainFor(TargetStmt));640 simplify(SameVal);641 if (SameVal.is_null())642 return ForwardingAction::notApplicable();643 644 auto ExecAction = [this, TargetStmt, Inst, SameVal]() {645 MemoryAccess *Access = TargetStmt->lookupInputAccessOf(Inst);646 if (!Access)647 Access = TargetStmt->ensureValueRead(Inst);648 Access->setNewAccessRelation(SameVal);649 650 POLLY_DEBUG(dbgs() << " forwarded known content of " << *Inst651 << " which is " << SameVal << "\n");652 TotalReloads++;653 NumReloads++;654 return false;655 };656 657 return ForwardingAction::canForward(ExecAction, {}, true);658 }659 660 /// Forwards a speculatively executable instruction.661 ///662 /// @param TargetStmt The statement the operand tree will be copied to.663 /// @param UseInst The (possibly speculatable) instruction to forward.664 /// @param DefStmt The statement @p UseInst is defined in.665 /// @param DefLoop The loop which contains @p UseInst.666 ///667 /// @return A ForwardingAction object describing the feasibility and668 /// profitability evaluation and the callback carrying-out the value669 /// forwarding.670 ForwardingAction forwardSpeculatable(ScopStmt *TargetStmt,671 Instruction *UseInst, ScopStmt *DefStmt,672 Loop *DefLoop) {673 // PHIs, unless synthesizable, are not yet supported.674 if (isa<PHINode>(UseInst))675 return ForwardingAction::notApplicable();676 677 // Compatible instructions must satisfy the following conditions:678 // 1. Idempotent (instruction will be copied, not moved; although its679 // original instance might be removed by simplification)680 // 2. Not access memory (There might be memory writes between)681 // 3. Not cause undefined behaviour (we might copy to a location when the682 // original instruction was no executed; this is currently not possible683 // because we do not forward PHINodes)684 // 4. Not leak memory if executed multiple times (i.e. malloc)685 //686 // Instruction::mayHaveSideEffects is not sufficient because it considers687 // malloc to not have side-effects. llvm::isSafeToSpeculativelyExecute is688 // not sufficient because it allows memory accesses.689 if (mayHaveNonDefUseDependency(*UseInst))690 return ForwardingAction::notApplicable();691 692 SmallVector<ForwardingAction::KeyTy, 4> Depends;693 Depends.reserve(UseInst->getNumOperands());694 for (Value *OpVal : UseInst->operand_values()) {695 ForwardingDecision OpDecision =696 forwardTree(TargetStmt, OpVal, DefStmt, DefLoop);697 switch (OpDecision) {698 case FD_CannotForward:699 return ForwardingAction::cannotForward();700 701 case FD_CanForwardLeaf:702 case FD_CanForwardProfitably:703 Depends.emplace_back(OpVal, DefStmt);704 break;705 706 case FD_NotApplicable:707 case FD_Unknown:708 llvm_unreachable(709 "forwardTree should never return FD_NotApplicable/FD_Unknown");710 }711 }712 713 auto ExecAction = [this, TargetStmt, UseInst]() {714 // To ensure the right order, prepend this instruction before its715 // operands. This ensures that its operands are inserted before the716 // instruction using them.717 TargetStmt->prependInstruction(UseInst);718 719 POLLY_DEBUG(dbgs() << " forwarded speculable instruction: " << *UseInst720 << "\n");721 NumInstructionsCopied++;722 TotalInstructionsCopied++;723 return true;724 };725 return ForwardingAction::canForward(ExecAction, Depends, true);726 }727 728 /// Determines whether an operand tree can be forwarded and returns729 /// instructions how to do so in the form of a ForwardingAction object.730 ///731 /// @param TargetStmt The statement the operand tree will be copied to.732 /// @param UseVal The value (usually an instruction) which is root of an733 /// operand tree.734 /// @param UseStmt The statement that uses @p UseVal.735 /// @param UseLoop The loop @p UseVal is used in.736 ///737 /// @return A ForwardingAction object describing the feasibility and738 /// profitability evaluation and the callback carrying-out the value739 /// forwarding.740 ForwardingAction forwardTreeImpl(ScopStmt *TargetStmt, Value *UseVal,741 ScopStmt *UseStmt, Loop *UseLoop) {742 ScopStmt *DefStmt = nullptr;743 Loop *DefLoop = nullptr;744 745 // { DefDomain[] -> TargetDomain[] }746 isl::map DefToTarget;747 748 VirtualUse VUse = VirtualUse::create(UseStmt, UseLoop, UseVal, true);749 switch (VUse.getKind()) {750 case VirtualUse::Constant:751 case VirtualUse::Block:752 case VirtualUse::Hoisted:753 // These can be used anywhere without special considerations.754 return ForwardingAction::triviallyForwardable(false, UseVal);755 756 case VirtualUse::Synthesizable: {757 // Check if the value is synthesizable at the new location as well. This758 // might be possible when leaving a loop for which ScalarEvolution is759 // unable to derive the exit value for.760 // TODO: If there is a LCSSA PHI at the loop exit, use that one.761 // If the SCEV contains a SCEVAddRecExpr, we currently depend on that we762 // do not forward past its loop header. This would require us to use a763 // previous loop induction variable instead the current one. We currently764 // do not allow forwarding PHI nodes, thus this should never occur (the765 // only exception where no phi is necessary being an unreachable loop766 // without edge from the outside).767 VirtualUse TargetUse = VirtualUse::create(768 S, TargetStmt, TargetStmt->getSurroundingLoop(), UseVal, true);769 if (TargetUse.getKind() == VirtualUse::Synthesizable)770 return ForwardingAction::triviallyForwardable(false, UseVal);771 772 POLLY_DEBUG(773 dbgs() << " Synthesizable would not be synthesizable anymore: "774 << *UseVal << "\n");775 return ForwardingAction::cannotForward();776 }777 778 case VirtualUse::ReadOnly: {779 if (!ModelReadOnlyScalars)780 return ForwardingAction::triviallyForwardable(false, UseVal);781 782 // If we model read-only scalars, we need to create a MemoryAccess for it.783 auto ExecAction = [this, TargetStmt, UseVal]() {784 TargetStmt->ensureValueRead(UseVal);785 786 POLLY_DEBUG(dbgs() << " forwarded read-only value " << *UseVal787 << "\n");788 NumReadOnlyCopied++;789 TotalReadOnlyCopied++;790 791 // Note that we cannot return true here. With a operand tree792 // depth of 0, UseVal is the use in TargetStmt that we try to replace.793 // With -polly-analyze-read-only-scalars=true we would ensure the794 // existence of a MemoryAccess (which already exists for a leaf) and be795 // removed again by tryForwardTree because it's goal is to remove this796 // scalar MemoryAccess. It interprets FD_CanForwardTree as the797 // permission to do so.798 return false;799 };800 return ForwardingAction::canForward(ExecAction, {}, false);801 }802 803 case VirtualUse::Intra:804 // Knowing that UseStmt and DefStmt are the same statement instance, just805 // reuse the information about UseStmt for DefStmt806 DefStmt = UseStmt;807 808 [[fallthrough]];809 case VirtualUse::Inter:810 Instruction *Inst = cast<Instruction>(UseVal);811 812 if (!DefStmt) {813 DefStmt = S->getStmtFor(Inst);814 if (!DefStmt)815 return ForwardingAction::cannotForward();816 }817 818 DefLoop = LI->getLoopFor(Inst->getParent());819 820 ForwardingAction SpeculativeResult =821 forwardSpeculatable(TargetStmt, Inst, DefStmt, DefLoop);822 if (SpeculativeResult.Decision != FD_NotApplicable)823 return SpeculativeResult;824 825 ForwardingAction KnownResult = forwardKnownLoad(826 TargetStmt, Inst, UseStmt, UseLoop, DefStmt, DefLoop);827 if (KnownResult.Decision != FD_NotApplicable)828 return KnownResult;829 830 ForwardingAction ReloadResult = reloadKnownContent(831 TargetStmt, Inst, UseStmt, UseLoop, DefStmt, DefLoop);832 if (ReloadResult.Decision != FD_NotApplicable)833 return ReloadResult;834 835 // When no method is found to forward the operand tree, we effectively836 // cannot handle it.837 POLLY_DEBUG(dbgs() << " Cannot forward instruction: " << *Inst838 << "\n");839 return ForwardingAction::cannotForward();840 }841 842 llvm_unreachable("Case unhandled");843 }844 845 /// Determines whether an operand tree can be forwarded. Previous evaluations846 /// are cached.847 ///848 /// @param TargetStmt The statement the operand tree will be copied to.849 /// @param UseVal The value (usually an instruction) which is root of an850 /// operand tree.851 /// @param UseStmt The statement that uses @p UseVal.852 /// @param UseLoop The loop @p UseVal is used in.853 ///854 /// @return FD_CannotForward if @p UseVal cannot be forwarded.855 /// FD_CanForwardLeaf if @p UseVal is forwardable, but not856 /// profitable.857 /// FD_CanForwardProfitably if @p UseVal is forwardable and useful to858 /// do.859 ForwardingDecision forwardTree(ScopStmt *TargetStmt, Value *UseVal,860 ScopStmt *UseStmt, Loop *UseLoop) {861 // Lookup any cached evaluation.862 auto It = ForwardingActions.find({UseVal, UseStmt});863 if (It != ForwardingActions.end())864 return It->second.Decision;865 866 // Make a new evaluation.867 ForwardingAction Action =868 forwardTreeImpl(TargetStmt, UseVal, UseStmt, UseLoop);869 ForwardingDecision Result = Action.Decision;870 871 // Remember for the next time.872 assert(!ForwardingActions.count({UseVal, UseStmt}) &&873 "circular dependency?");874 ForwardingActions.insert({{UseVal, UseStmt}, std::move(Action)});875 876 return Result;877 }878 879 /// Forward an operand tree using cached actions.880 ///881 /// @param Stmt Statement the operand tree is moved into.882 /// @param UseVal Root of the operand tree within @p Stmt.883 /// @param RA The MemoryAccess for @p UseVal that the forwarding intends884 /// to remove.885 void applyForwardingActions(ScopStmt *Stmt, Value *UseVal, MemoryAccess *RA) {886 using ChildItTy =887 decltype(std::declval<ForwardingAction>().Depends.begin());888 using EdgeTy = std::pair<ForwardingAction *, ChildItTy>;889 890 DenseSet<ForwardingAction::KeyTy> Visited;891 SmallVector<EdgeTy, 32> Stack;892 SmallVector<ForwardingAction *, 32> Ordered;893 894 // Seed the tree search using the root value.895 assert(ForwardingActions.count({UseVal, Stmt}));896 ForwardingAction *RootAction = &ForwardingActions[{UseVal, Stmt}];897 Stack.emplace_back(RootAction, RootAction->Depends.begin());898 899 // Compute the postorder of the operand tree: all operands of an instruction900 // must be visited before the instruction itself. As an additional901 // requirement, the topological ordering must be 'compact': Any subtree node902 // must not be interleaved with nodes from a non-shared subtree. This is903 // because the same llvm::Instruction can be materialized multiple times as904 // used at different ScopStmts which might be different values. Intersecting905 // these lifetimes may result in miscompilations.906 // FIXME: Intersecting lifetimes might still be possible for the roots907 // themselves, since instructions are just prepended to a ScopStmt's908 // instruction list.909 while (!Stack.empty()) {910 EdgeTy &Top = Stack.back();911 ForwardingAction *TopAction = Top.first;912 ChildItTy &TopEdge = Top.second;913 914 if (TopEdge == TopAction->Depends.end()) {915 // Postorder sorting916 Ordered.push_back(TopAction);917 Stack.pop_back();918 continue;919 }920 ForwardingAction::KeyTy Key = *TopEdge;921 922 // Next edge for this level923 ++TopEdge;924 925 auto VisitIt = Visited.insert(Key);926 if (!VisitIt.second)927 continue;928 929 assert(ForwardingActions.count(Key) &&930 "Must not insert new actions during execution phase");931 ForwardingAction *ChildAction = &ForwardingActions[Key];932 Stack.emplace_back(ChildAction, ChildAction->Depends.begin());933 }934 935 // Actually, we need the reverse postorder because actions prepend new936 // instructions. Therefore, the first one will always be the action for the937 // operand tree's root.938 assert(Ordered.back() == RootAction);939 if (RootAction->Execute())940 Stmt->removeSingleMemoryAccess(RA);941 Ordered.pop_back();942 for (auto DepAction : reverse(Ordered)) {943 assert(DepAction->Decision != FD_Unknown &&944 DepAction->Decision != FD_CannotForward);945 assert(DepAction != RootAction);946 DepAction->Execute();947 }948 }949 950 /// Try to forward an operand tree rooted in @p RA.951 bool tryForwardTree(MemoryAccess *RA) {952 assert(RA->isLatestScalarKind());953 POLLY_DEBUG(dbgs() << "Trying to forward operand tree " << RA << "...\n");954 955 ScopStmt *Stmt = RA->getStatement();956 Loop *InLoop = Stmt->getSurroundingLoop();957 958 isl::map TargetToUse;959 if (!Known.is_null()) {960 isl::space DomSpace = Stmt->getDomainSpace();961 TargetToUse =962 isl::map::identity(DomSpace.map_from_domain_and_range(DomSpace));963 }964 965 ForwardingDecision Assessment =966 forwardTree(Stmt, RA->getAccessValue(), Stmt, InLoop);967 968 // If considered feasible and profitable, forward it.969 bool Changed = false;970 if (Assessment == FD_CanForwardProfitably) {971 applyForwardingActions(Stmt, RA->getAccessValue(), RA);972 Changed = true;973 }974 975 ForwardingActions.clear();976 return Changed;977 }978 979 /// Return which SCoP this instance is processing.980 Scop *getScop() const { return S; }981 982 /// Run the algorithm: Use value read accesses as operand tree roots and try983 /// to forward them into the statement.984 bool forwardOperandTrees() {985 for (ScopStmt &Stmt : *S) {986 bool StmtModified = false;987 988 // Because we are modifying the MemoryAccess list, collect them first to989 // avoid iterator invalidation.990 SmallVector<MemoryAccess *, 16> Accs(Stmt.begin(), Stmt.end());991 992 for (MemoryAccess *RA : Accs) {993 if (!RA->isRead())994 continue;995 if (!RA->isLatestScalarKind())996 continue;997 998 if (tryForwardTree(RA)) {999 Modified = true;1000 StmtModified = true;1001 NumForwardedTrees++;1002 TotalForwardedTrees++;1003 }1004 }1005 1006 if (StmtModified) {1007 NumModifiedStmts++;1008 TotalModifiedStmts++;1009 }1010 }1011 1012 if (Modified) {1013 ScopsModified++;1014 S->realignParams();1015 }1016 return Modified;1017 }1018 1019 /// Print the pass result, performed transformations and the SCoP after the1020 /// transformation.1021 void print(raw_ostream &OS, int Indent = 0) {1022 printStatistics(OS, Indent);1023 1024 if (!Modified) {1025 // This line can easily be checked in regression tests.1026 OS << "ForwardOpTree executed, but did not modify anything\n";1027 return;1028 }1029 1030 printStatements(OS, Indent);1031 }1032 1033 bool isModified() const { return Modified; }1034};1035 1036static std::unique_ptr<ForwardOpTreeImpl> runForwardOpTreeImpl(Scop &S,1037 LoopInfo &LI) {1038 std::unique_ptr<ForwardOpTreeImpl> Impl;1039 {1040 IslMaxOperationsGuard MaxOpGuard(S.getIslCtx().get(), MaxOps, false);1041 Impl = std::make_unique<ForwardOpTreeImpl>(&S, &LI, MaxOpGuard);1042 1043 if (AnalyzeKnown) {1044 POLLY_DEBUG(dbgs() << "Prepare forwarders...\n");1045 Impl->computeKnownValues();1046 }1047 1048 POLLY_DEBUG(dbgs() << "Forwarding operand trees...\n");1049 Impl->forwardOperandTrees();1050 1051 if (MaxOpGuard.hasQuotaExceeded()) {1052 POLLY_DEBUG(dbgs() << "Not all operations completed because of "1053 "max_operations exceeded\n");1054 KnownOutOfQuota++;1055 }1056 }1057 1058 POLLY_DEBUG(dbgs() << "\nFinal Scop:\n");1059 POLLY_DEBUG(dbgs() << S);1060 1061 // Update statistics1062 Scop::ScopStatistics ScopStats = S.getStatistics();1063 NumValueWrites += ScopStats.NumValueWrites;1064 NumValueWritesInLoops += ScopStats.NumValueWritesInLoops;1065 NumPHIWrites += ScopStats.NumPHIWrites;1066 NumPHIWritesInLoops += ScopStats.NumPHIWritesInLoops;1067 NumSingletonWrites += ScopStats.NumSingletonWrites;1068 NumSingletonWritesInLoops += ScopStats.NumSingletonWritesInLoops;1069 1070 return Impl;1071}1072} // namespace1073 1074bool polly::runForwardOpTree(Scop &S) {1075 LoopInfo &LI = *S.getLI();1076 1077 std::unique_ptr<ForwardOpTreeImpl> Impl = runForwardOpTreeImpl(S, LI);1078 if (PollyPrintOptree) {1079 outs() << "Printing analysis 'Polly - Forward operand tree' for region: '"1080 << S.getName() << "' in function '" << S.getFunction().getName()1081 << "':\n";1082 if (Impl) {1083 assert(Impl->getScop() == &S);1084 1085 Impl->print(outs());1086 }1087 }1088 1089 return Impl->isModified();1090}1091