795 lines · cpp
1//===------ Simplify.cpp ----------------------------------------*- 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// Simplify a SCoP by removing unnecessary statements and accesses.10//11//===----------------------------------------------------------------------===//12 13#include "polly/Simplify.h"14#include "polly/Options.h"15#include "polly/ScopInfo.h"16#include "polly/Support/GICHelper.h"17#include "polly/Support/ISLOStream.h"18#include "polly/Support/ISLTools.h"19#include "polly/Support/VirtualInstruction.h"20#include "llvm/ADT/Statistic.h"21#include "llvm/Support/Debug.h"22#include <optional>23 24#include "polly/Support/PollyDebug.h"25#define DEBUG_TYPE "polly-simplify"26 27using namespace llvm;28using namespace polly;29 30namespace {31 32static cl::opt<bool>33 PollyPrintSimplify("polly-print-simplify",34 cl::desc("Polly - Print Simplify actions"),35 cl::cat(PollyCategory));36 37#define TWO_STATISTICS(VARNAME, DESC) \38 static llvm::Statistic VARNAME[2] = { \39 {DEBUG_TYPE, #VARNAME "0", DESC " (first)"}, \40 {DEBUG_TYPE, #VARNAME "1", DESC " (second)"}}41 42/// Number of max disjuncts we allow in removeOverwrites(). This is to avoid43/// that the analysis of accesses in a statement is becoming too complex. Chosen44/// to be relatively small because all the common cases should access only few45/// array elements per statement.46static unsigned const SimplifyMaxDisjuncts = 4;47 48TWO_STATISTICS(ScopsProcessed, "Number of SCoPs processed");49TWO_STATISTICS(ScopsModified, "Number of SCoPs simplified");50 51TWO_STATISTICS(TotalEmptyDomainsRemoved,52 "Number of statement with empty domains removed in any SCoP");53TWO_STATISTICS(TotalOverwritesRemoved, "Number of removed overwritten writes");54TWO_STATISTICS(TotalWritesCoalesced, "Number of writes coalesced with another");55TWO_STATISTICS(TotalRedundantWritesRemoved,56 "Number of writes of same value removed in any SCoP");57TWO_STATISTICS(TotalEmptyPartialAccessesRemoved,58 "Number of empty partial accesses removed");59TWO_STATISTICS(TotalDeadAccessesRemoved, "Number of dead accesses removed");60TWO_STATISTICS(TotalDeadInstructionsRemoved,61 "Number of unused instructions removed");62TWO_STATISTICS(TotalStmtsRemoved, "Number of statements removed in any SCoP");63 64TWO_STATISTICS(NumValueWrites, "Number of scalar value writes after Simplify");65TWO_STATISTICS(66 NumValueWritesInLoops,67 "Number of scalar value writes nested in affine loops after Simplify");68TWO_STATISTICS(NumPHIWrites,69 "Number of scalar phi writes after the first simplification");70TWO_STATISTICS(71 NumPHIWritesInLoops,72 "Number of scalar phi writes nested in affine loops after Simplify");73TWO_STATISTICS(NumSingletonWrites, "Number of singleton writes after Simplify");74TWO_STATISTICS(75 NumSingletonWritesInLoops,76 "Number of singleton writes nested in affine loops after Simplify");77 78static bool isImplicitRead(MemoryAccess *MA) {79 return MA->isRead() && MA->isOriginalScalarKind();80}81 82static bool isExplicitAccess(MemoryAccess *MA) {83 return MA->isOriginalArrayKind();84}85 86static bool isImplicitWrite(MemoryAccess *MA) {87 return MA->isWrite() && MA->isOriginalScalarKind();88}89 90/// Like isl::union_map::unite, but may also return an underapproximated91/// result if getting too complex.92///93/// This is implemented by adding disjuncts to the results until the limit is94/// reached.95static isl::union_map underapproximatedAddMap(isl::union_map UMap,96 isl::map Map) {97 if (UMap.is_null() || Map.is_null())98 return {};99 100 isl::map PrevMap = UMap.extract_map(Map.get_space());101 102 // Fast path: If known that we cannot exceed the disjunct limit, just add103 // them.104 if (unsignedFromIslSize(PrevMap.n_basic_map()) +105 unsignedFromIslSize(Map.n_basic_map()) <=106 SimplifyMaxDisjuncts)107 return UMap.unite(Map);108 109 isl::map Result = isl::map::empty(PrevMap.get_space());110 for (isl::basic_map BMap : PrevMap.get_basic_map_list()) {111 if (unsignedFromIslSize(Result.n_basic_map()) > SimplifyMaxDisjuncts)112 break;113 Result = Result.unite(BMap);114 }115 for (isl::basic_map BMap : Map.get_basic_map_list()) {116 if (unsignedFromIslSize(Result.n_basic_map()) > SimplifyMaxDisjuncts)117 break;118 Result = Result.unite(BMap);119 }120 121 isl::union_map UResult =122 UMap.subtract(isl::map::universe(PrevMap.get_space()));123 UResult.unite(Result);124 125 return UResult;126}127 128class SimplifyImpl final {129private:130 /// The invocation id (if there are multiple instances in the pass manager's131 /// pipeline) to determine which statistics to update.132 int CallNo;133 134 /// The last/current SCoP that is/has been processed.135 Scop *S = nullptr;136 137 /// Number of statements with empty domains removed from the SCoP.138 int EmptyDomainsRemoved = 0;139 140 /// Number of writes that are overwritten anyway.141 int OverwritesRemoved = 0;142 143 /// Number of combined writes.144 int WritesCoalesced = 0;145 146 /// Number of redundant writes removed from this SCoP.147 int RedundantWritesRemoved = 0;148 149 /// Number of writes with empty access domain removed.150 int EmptyPartialAccessesRemoved = 0;151 152 /// Number of unused accesses removed from this SCoP.153 int DeadAccessesRemoved = 0;154 155 /// Number of unused instructions removed from this SCoP.156 int DeadInstructionsRemoved = 0;157 158 /// Number of unnecessary statements removed from the SCoP.159 int StmtsRemoved = 0;160 161 /// Remove statements that are never executed due to their domains being162 /// empty.163 ///164 /// In contrast to Scop::simplifySCoP, this removes based on the SCoP's165 /// effective domain, i.e. including the SCoP's context as used by some other166 /// simplification methods in this pass. This is necessary because the167 /// analysis on empty domains is unreliable, e.g. remove a scalar value168 /// definition MemoryAccesses, but not its use.169 void removeEmptyDomainStmts();170 171 /// Remove writes that are overwritten unconditionally later in the same172 /// statement.173 ///174 /// There must be no read of the same value between the write (that is to be175 /// removed) and the overwrite.176 void removeOverwrites();177 178 /// Combine writes that write the same value if possible.179 ///180 /// This function is able to combine:181 /// - Partial writes with disjoint domain.182 /// - Writes that write to the same array element.183 ///184 /// In all cases, both writes must write the same values.185 void coalesceWrites();186 187 /// Remove writes that just write the same value already stored in the188 /// element.189 void removeRedundantWrites();190 191 /// Remove statements without side effects.192 void removeUnnecessaryStmts();193 194 /// Remove accesses that have an empty domain.195 void removeEmptyPartialAccesses();196 197 /// Mark all reachable instructions and access, and sweep those that are not198 /// reachable.199 void markAndSweep(LoopInfo *LI);200 201 /// Print simplification statistics to @p OS.202 void printStatistics(llvm::raw_ostream &OS, int Indent = 0) const;203 204 /// Print the current state of all MemoryAccesses to @p OS.205 void printAccesses(llvm::raw_ostream &OS, int Indent = 0) const;206 207public:208 explicit SimplifyImpl(int CallNo = 0) : CallNo(CallNo) {}209 210 void run(Scop &S, LoopInfo *LI);211 212 void printScop(raw_ostream &OS, Scop &S) const;213 214 /// Return whether at least one simplification has been applied.215 bool isModified() const;216};217 218/// Return whether at least one simplification has been applied.219bool SimplifyImpl::isModified() const {220 return EmptyDomainsRemoved > 0 || OverwritesRemoved > 0 ||221 WritesCoalesced > 0 || RedundantWritesRemoved > 0 ||222 EmptyPartialAccessesRemoved > 0 || DeadAccessesRemoved > 0 ||223 DeadInstructionsRemoved > 0 || StmtsRemoved > 0;224}225 226/// Remove statements that are never executed due to their domains being227/// empty.228///229/// In contrast to Scop::simplifySCoP, this removes based on the SCoP's230/// effective domain, i.e. including the SCoP's context as used by some other231/// simplification methods in this pass. This is necessary because the232/// analysis on empty domains is unreliable, e.g. remove a scalar value233/// definition MemoryAccesses, but not its use.234void SimplifyImpl::removeEmptyDomainStmts() {235 size_t NumStmtsBefore = S->getSize();236 237 S->removeStmts([](ScopStmt &Stmt) -> bool {238 auto EffectiveDomain =239 Stmt.getDomain().intersect_params(Stmt.getParent()->getContext());240 return EffectiveDomain.is_empty();241 });242 243 assert(NumStmtsBefore >= S->getSize());244 EmptyDomainsRemoved = NumStmtsBefore - S->getSize();245 POLLY_DEBUG(dbgs() << "Removed " << EmptyDomainsRemoved << " (of "246 << NumStmtsBefore << ") statements with empty domains \n");247 TotalEmptyDomainsRemoved[CallNo] += EmptyDomainsRemoved;248}249 250/// Remove writes that are overwritten unconditionally later in the same251/// statement.252///253/// There must be no read of the same value between the write (that is to be254/// removed) and the overwrite.255void SimplifyImpl::removeOverwrites() {256 for (auto &Stmt : *S) {257 isl::set Domain = Stmt.getDomain();258 isl::union_map WillBeOverwritten = isl::union_map::empty(S->getIslCtx());259 260 SmallVector<MemoryAccess *, 32> Accesses(getAccessesInOrder(Stmt));261 262 // Iterate in reverse order, so the overwrite comes before the write that263 // is to be removed.264 for (auto *MA : reverse(Accesses)) {265 266 // In region statements, the explicit accesses can be in blocks that are267 // can be executed in any order. We therefore process only the implicit268 // writes and stop after that.269 if (Stmt.isRegionStmt() && isExplicitAccess(MA))270 break;271 272 auto AccRel = MA->getAccessRelation();273 AccRel = AccRel.intersect_domain(Domain);274 AccRel = AccRel.intersect_params(S->getContext());275 276 // If a value is read in-between, do not consider it as overwritten.277 if (MA->isRead()) {278 // Invalidate all overwrites for the array it accesses to avoid too279 // complex isl sets.280 isl::map AccRelUniv = isl::map::universe(AccRel.get_space());281 WillBeOverwritten = WillBeOverwritten.subtract(AccRelUniv);282 continue;283 }284 285 // If all of a write's elements are overwritten, remove it.286 isl::union_map AccRelUnion = AccRel;287 if (AccRelUnion.is_subset(WillBeOverwritten)) {288 POLLY_DEBUG(dbgs() << "Removing " << MA289 << " which will be overwritten anyway\n");290 291 Stmt.removeSingleMemoryAccess(MA);292 OverwritesRemoved++;293 TotalOverwritesRemoved[CallNo]++;294 }295 296 // Unconditional writes overwrite other values.297 if (MA->isMustWrite()) {298 // Avoid too complex isl sets. If necessary, throw away some of the299 // knowledge.300 WillBeOverwritten = underapproximatedAddMap(WillBeOverwritten, AccRel);301 }302 }303 }304}305 306/// Combine writes that write the same value if possible.307///308/// This function is able to combine:309/// - Partial writes with disjoint domain.310/// - Writes that write to the same array element.311///312/// In all cases, both writes must write the same values.313void SimplifyImpl::coalesceWrites() {314 for (auto &Stmt : *S) {315 isl::set Domain = Stmt.getDomain().intersect_params(S->getContext());316 317 // We let isl do the lookup for the same-value condition. For this, we318 // wrap llvm::Value into an isl::set such that isl can do the lookup in319 // its hashtable implementation. llvm::Values are only compared within a320 // ScopStmt, so the map can be local to this scope. TODO: Refactor with321 // ZoneAlgorithm::makeValueSet()322 SmallDenseMap<Value *, isl::set> ValueSets;323 auto makeValueSet = [&ValueSets, this](Value *V) -> isl::set {324 assert(V);325 isl::set &Result = ValueSets[V];326 if (Result.is_null()) {327 isl::ctx Ctx = S->getIslCtx();328 std::string Name = getIslCompatibleName(329 "Val", V, ValueSets.size() - 1, std::string(), UseInstructionNames);330 isl::id Id = isl::id::alloc(Ctx, Name, V);331 Result = isl::set::universe(332 isl::space(Ctx, 0, 0).set_tuple_id(isl::dim::set, Id));333 }334 return Result;335 };336 337 // List of all eligible (for coalescing) writes of the future.338 // { [Domain[] -> Element[]] -> [Value[] -> MemoryAccess[]] }339 isl::union_map FutureWrites = isl::union_map::empty(S->getIslCtx());340 341 // Iterate over accesses from the last to the first.342 SmallVector<MemoryAccess *, 32> Accesses(getAccessesInOrder(Stmt));343 for (MemoryAccess *MA : reverse(Accesses)) {344 // In region statements, the explicit accesses can be in blocks that can345 // be executed in any order. We therefore process only the implicit346 // writes and stop after that.347 if (Stmt.isRegionStmt() && isExplicitAccess(MA))348 break;349 350 // { Domain[] -> Element[] }351 isl::map AccRel = MA->getLatestAccessRelation().intersect_domain(Domain);352 353 // { [Domain[] -> Element[]] }354 isl::set AccRelWrapped = AccRel.wrap();355 356 // { Value[] }357 isl::set ValSet;358 359 if (MA->isMustWrite() && (MA->isOriginalScalarKind() ||360 isa<StoreInst>(MA->getAccessInstruction()))) {361 // Normally, tryGetValueStored() should be used to determine which362 // element is written, but it can return nullptr; For PHI accesses,363 // getAccessValue() returns the PHI instead of the PHI's incoming364 // value. In this case, where we only compare values of a single365 // statement, this is fine, because within a statement, a PHI in a366 // successor block has always the same value as the incoming write. We367 // still preferably use the incoming value directly so we also catch368 // direct uses of that.369 Value *StoredVal = MA->tryGetValueStored();370 if (!StoredVal)371 StoredVal = MA->getAccessValue();372 ValSet = makeValueSet(StoredVal);373 374 // { Domain[] }375 isl::set AccDomain = AccRel.domain();376 377 // Parts of the statement's domain that is not written by this access.378 isl::set UndefDomain = Domain.subtract(AccDomain);379 380 // { Element[] }381 isl::set ElementUniverse =382 isl::set::universe(AccRel.get_space().range());383 384 // { Domain[] -> Element[] }385 isl::map UndefAnything =386 isl::map::from_domain_and_range(UndefDomain, ElementUniverse);387 388 // We are looking a compatible write access. The other write can389 // access these elements...390 isl::map AllowedAccesses = AccRel.unite(UndefAnything);391 392 // ... and must write the same value.393 // { [Domain[] -> Element[]] -> Value[] }394 isl::map Filter =395 isl::map::from_domain_and_range(AllowedAccesses.wrap(), ValSet);396 397 // Lookup future write that fulfills these conditions.398 // { [[Domain[] -> Element[]] -> Value[]] -> MemoryAccess[] }399 isl::union_map Filtered =400 FutureWrites.uncurry().intersect_domain(Filter.wrap());401 402 // Iterate through the candidates.403 for (isl::map Map : Filtered.get_map_list()) {404 MemoryAccess *OtherMA = (MemoryAccess *)Map.get_space()405 .get_tuple_id(isl::dim::out)406 .get_user();407 408 isl::map OtherAccRel =409 OtherMA->getLatestAccessRelation().intersect_domain(Domain);410 411 // The filter only guaranteed that some of OtherMA's accessed412 // elements are allowed. Verify that it only accesses allowed413 // elements. Otherwise, continue with the next candidate.414 if (!OtherAccRel.is_subset(AllowedAccesses).is_true())415 continue;416 417 // The combined access relation.418 // { Domain[] -> Element[] }419 isl::map NewAccRel = AccRel.unite(OtherAccRel);420 simplify(NewAccRel);421 422 // Carry out the coalescing.423 Stmt.removeSingleMemoryAccess(MA);424 OtherMA->setNewAccessRelation(NewAccRel);425 426 // We removed MA, OtherMA takes its role.427 MA = OtherMA;428 429 TotalWritesCoalesced[CallNo]++;430 WritesCoalesced++;431 432 // Don't look for more candidates.433 break;434 }435 }436 437 // Two writes cannot be coalesced if there is another access (to some of438 // the written elements) between them. Remove all visited write accesses439 // from the list of eligible writes. Don't just remove the accessed440 // elements, but any MemoryAccess that touches any of the invalidated441 // elements.442 SmallPtrSet<MemoryAccess *, 2> TouchedAccesses;443 for (isl::map Map :444 FutureWrites.intersect_domain(AccRelWrapped).get_map_list()) {445 MemoryAccess *MA = (MemoryAccess *)Map.get_space()446 .range()447 .unwrap()448 .get_tuple_id(isl::dim::out)449 .get_user();450 TouchedAccesses.insert(MA);451 }452 isl::union_map NewFutureWrites =453 isl::union_map::empty(FutureWrites.ctx());454 for (isl::map FutureWrite : FutureWrites.get_map_list()) {455 MemoryAccess *MA = (MemoryAccess *)FutureWrite.get_space()456 .range()457 .unwrap()458 .get_tuple_id(isl::dim::out)459 .get_user();460 if (!TouchedAccesses.count(MA))461 NewFutureWrites = NewFutureWrites.unite(FutureWrite);462 }463 FutureWrites = NewFutureWrites;464 465 if (MA->isMustWrite() && !ValSet.is_null()) {466 // { MemoryAccess[] }467 auto AccSet =468 isl::set::universe(isl::space(S->getIslCtx(), 0, 0)469 .set_tuple_id(isl::dim::set, MA->getId()));470 471 // { Val[] -> MemoryAccess[] }472 isl::map ValAccSet = isl::map::from_domain_and_range(ValSet, AccSet);473 474 // { [Domain[] -> Element[]] -> [Value[] -> MemoryAccess[]] }475 isl::map AccRelValAcc =476 isl::map::from_domain_and_range(AccRelWrapped, ValAccSet.wrap());477 FutureWrites = FutureWrites.unite(AccRelValAcc);478 }479 }480 }481}482 483/// Remove writes that just write the same value already stored in the484/// element.485void SimplifyImpl::removeRedundantWrites() {486 for (auto &Stmt : *S) {487 SmallDenseMap<Value *, isl::set> ValueSets;488 auto makeValueSet = [&ValueSets, this](Value *V) -> isl::set {489 assert(V);490 isl::set &Result = ValueSets[V];491 if (Result.is_null()) {492 isl_ctx *Ctx = S->getIslCtx().get();493 std::string Name = getIslCompatibleName(494 "Val", V, ValueSets.size() - 1, std::string(), UseInstructionNames);495 isl::id Id = isl::manage(isl_id_alloc(Ctx, Name.c_str(), V));496 Result = isl::set::universe(497 isl::space(Ctx, 0, 0).set_tuple_id(isl::dim::set, Id));498 }499 return Result;500 };501 502 isl::set Domain = Stmt.getDomain();503 Domain = Domain.intersect_params(S->getContext());504 505 // List of element reads that still have the same value while iterating506 // through the MemoryAccesses.507 // { [Domain[] -> Element[]] -> Val[] }508 isl::union_map Known = isl::union_map::empty(S->getIslCtx());509 510 SmallVector<MemoryAccess *, 32> Accesses(getAccessesInOrder(Stmt));511 for (MemoryAccess *MA : Accesses) {512 // Is the memory access in a defined order relative to the other513 // accesses? In region statements, only the first and the last accesses514 // have defined order. Execution of those in the middle may depend on515 // runtime conditions an therefore cannot be modified.516 bool IsOrdered =517 Stmt.isBlockStmt() || MA->isOriginalScalarKind() ||518 (!S->getBoxedLoops().size() && MA->getAccessInstruction() &&519 Stmt.getEntryBlock() == MA->getAccessInstruction()->getParent());520 521 isl::map AccRel = MA->getAccessRelation();522 AccRel = AccRel.intersect_domain(Domain);523 isl::set AccRelWrapped = AccRel.wrap();524 525 // Determine whether a write is redundant (stores only values that are526 // already present in the written array elements) and remove it if this527 // is the case.528 if (IsOrdered && MA->isMustWrite() &&529 (isa<StoreInst>(MA->getAccessInstruction()) ||530 MA->isOriginalScalarKind())) {531 Value *StoredVal = MA->tryGetValueStored();532 if (!StoredVal)533 StoredVal = MA->getAccessValue();534 535 if (StoredVal) {536 // Lookup in the set of known values.537 isl::map AccRelStoredVal = isl::map::from_domain_and_range(538 AccRelWrapped, makeValueSet(StoredVal));539 if (isl::union_map(AccRelStoredVal).is_subset(Known)) {540 POLLY_DEBUG(dbgs() << "Cleanup of " << MA << ":\n");541 POLLY_DEBUG(dbgs() << " Scalar: " << *StoredVal << "\n");542 POLLY_DEBUG(dbgs() << " AccRel: " << AccRel << "\n");543 544 Stmt.removeSingleMemoryAccess(MA);545 546 RedundantWritesRemoved++;547 TotalRedundantWritesRemoved[CallNo]++;548 }549 }550 }551 552 // Update the know values set.553 if (MA->isRead()) {554 // Loaded values are the currently known values of the array element555 // it was loaded from.556 Value *LoadedVal = MA->getAccessValue();557 if (LoadedVal && IsOrdered) {558 isl::map AccRelVal = isl::map::from_domain_and_range(559 AccRelWrapped, makeValueSet(LoadedVal));560 561 Known = Known.unite(AccRelVal);562 }563 } else if (MA->isWrite()) {564 // Remove (possibly) overwritten values from the known elements set.565 // We remove all elements of the accessed array to avoid too complex566 // isl sets.567 isl::set AccRelUniv = isl::set::universe(AccRelWrapped.get_space());568 Known = Known.subtract_domain(AccRelUniv);569 570 // At this point, we could add the written value of must-writes.571 // However, writing same values is already handled by572 // coalesceWrites().573 }574 }575 }576}577 578/// Remove statements without side effects.579void SimplifyImpl::removeUnnecessaryStmts() {580 auto NumStmtsBefore = S->getSize();581 S->simplifySCoP(true);582 assert(NumStmtsBefore >= S->getSize());583 StmtsRemoved = NumStmtsBefore - S->getSize();584 POLLY_DEBUG(dbgs() << "Removed " << StmtsRemoved << " (of " << NumStmtsBefore585 << ") statements\n");586 TotalStmtsRemoved[CallNo] += StmtsRemoved;587}588 589/// Remove accesses that have an empty domain.590void SimplifyImpl::removeEmptyPartialAccesses() {591 for (ScopStmt &Stmt : *S) {592 // Defer the actual removal to not invalidate iterators.593 SmallVector<MemoryAccess *, 8> DeferredRemove;594 595 for (MemoryAccess *MA : Stmt) {596 if (!MA->isWrite())597 continue;598 599 isl::map AccRel = MA->getAccessRelation();600 if (!AccRel.is_empty().is_true())601 continue;602 603 POLLY_DEBUG(604 dbgs() << "Removing " << MA605 << " because it's a partial access that never occurs\n");606 DeferredRemove.push_back(MA);607 }608 609 for (MemoryAccess *MA : DeferredRemove) {610 Stmt.removeSingleMemoryAccess(MA);611 EmptyPartialAccessesRemoved++;612 TotalEmptyPartialAccessesRemoved[CallNo]++;613 }614 }615}616 617/// Mark all reachable instructions and access, and sweep those that are not618/// reachable.619void SimplifyImpl::markAndSweep(LoopInfo *LI) {620 DenseSet<MemoryAccess *> UsedMA;621 DenseSet<VirtualInstruction> UsedInsts;622 623 // Get all reachable instructions and accesses.624 markReachable(S, LI, UsedInsts, UsedMA);625 626 // Remove all non-reachable accesses.627 // We need get all MemoryAccesses first, in order to not invalidate the628 // iterators when removing them.629 SmallVector<MemoryAccess *, 64> AllMAs;630 for (ScopStmt &Stmt : *S)631 AllMAs.append(Stmt.begin(), Stmt.end());632 633 for (MemoryAccess *MA : AllMAs) {634 if (UsedMA.count(MA))635 continue;636 POLLY_DEBUG(dbgs() << "Removing " << MA637 << " because its value is not used\n");638 ScopStmt *Stmt = MA->getStatement();639 Stmt->removeSingleMemoryAccess(MA);640 641 DeadAccessesRemoved++;642 TotalDeadAccessesRemoved[CallNo]++;643 }644 645 // Remove all non-reachable instructions.646 for (ScopStmt &Stmt : *S) {647 // Note that for region statements, we can only remove the non-terminator648 // instructions of the entry block. All other instructions are not in the649 // instructions list, but implicitly always part of the statement.650 651 SmallVector<Instruction *, 32> AllInsts(Stmt.insts_begin(),652 Stmt.insts_end());653 SmallVector<Instruction *, 32> RemainInsts;654 655 for (Instruction *Inst : AllInsts) {656 auto It = UsedInsts.find({&Stmt, Inst});657 if (It == UsedInsts.end()) {658 POLLY_DEBUG(dbgs() << "Removing "; Inst->print(dbgs());659 dbgs() << " because it is not used\n");660 DeadInstructionsRemoved++;661 TotalDeadInstructionsRemoved[CallNo]++;662 continue;663 }664 665 RemainInsts.push_back(Inst);666 667 // If instructions appear multiple times, keep only the first.668 UsedInsts.erase(It);669 }670 671 // Set the new instruction list to be only those we did not remove.672 Stmt.setInstructions(RemainInsts);673 }674}675 676/// Print simplification statistics to @p OS.677void SimplifyImpl::printStatistics(llvm::raw_ostream &OS, int Indent) const {678 OS.indent(Indent) << "Statistics {\n";679 OS.indent(Indent + 4) << "Empty domains removed: " << EmptyDomainsRemoved680 << '\n';681 OS.indent(Indent + 4) << "Overwrites removed: " << OverwritesRemoved << '\n';682 OS.indent(Indent + 4) << "Partial writes coalesced: " << WritesCoalesced683 << "\n";684 OS.indent(Indent + 4) << "Redundant writes removed: "685 << RedundantWritesRemoved << "\n";686 OS.indent(Indent + 4) << "Accesses with empty domains removed: "687 << EmptyPartialAccessesRemoved << "\n";688 OS.indent(Indent + 4) << "Dead accesses removed: " << DeadAccessesRemoved689 << '\n';690 OS.indent(Indent + 4) << "Dead instructions removed: "691 << DeadInstructionsRemoved << '\n';692 OS.indent(Indent + 4) << "Stmts removed: " << StmtsRemoved << "\n";693 OS.indent(Indent) << "}\n";694}695 696/// Print the current state of all MemoryAccesses to @p OS.697void SimplifyImpl::printAccesses(llvm::raw_ostream &OS, int Indent) const {698 OS.indent(Indent) << "After accesses {\n";699 for (auto &Stmt : *S) {700 OS.indent(Indent + 4) << Stmt.getBaseName() << "\n";701 for (auto *MA : Stmt)702 MA->print(OS);703 }704 OS.indent(Indent) << "}\n";705}706 707void SimplifyImpl::run(Scop &S, LoopInfo *LI) {708 // Must not have run before.709 assert(!this->S);710 assert(!isModified());711 712 // Prepare processing of this SCoP.713 this->S = &S;714 ScopsProcessed[CallNo]++;715 716 POLLY_DEBUG(dbgs() << "Removing statements that are never executed...\n");717 removeEmptyDomainStmts();718 719 POLLY_DEBUG(dbgs() << "Removing partial writes that never happen...\n");720 removeEmptyPartialAccesses();721 722 POLLY_DEBUG(dbgs() << "Removing overwrites...\n");723 removeOverwrites();724 725 POLLY_DEBUG(dbgs() << "Coalesce partial writes...\n");726 coalesceWrites();727 728 POLLY_DEBUG(dbgs() << "Removing redundant writes...\n");729 removeRedundantWrites();730 731 POLLY_DEBUG(dbgs() << "Cleanup unused accesses...\n");732 markAndSweep(LI);733 734 POLLY_DEBUG(dbgs() << "Removing statements without side effects...\n");735 removeUnnecessaryStmts();736 737 if (isModified())738 ScopsModified[CallNo]++;739 POLLY_DEBUG(dbgs() << "\nFinal Scop:\n");740 POLLY_DEBUG(dbgs() << S);741 742 auto ScopStats = S.getStatistics();743 NumValueWrites[CallNo] += ScopStats.NumValueWrites;744 NumValueWritesInLoops[CallNo] += ScopStats.NumValueWritesInLoops;745 NumPHIWrites[CallNo] += ScopStats.NumPHIWrites;746 NumPHIWritesInLoops[CallNo] += ScopStats.NumPHIWritesInLoops;747 NumSingletonWrites[CallNo] += ScopStats.NumSingletonWrites;748 NumSingletonWritesInLoops[CallNo] += ScopStats.NumSingletonWritesInLoops;749}750 751void SimplifyImpl::printScop(raw_ostream &OS, Scop &S) const {752 assert(&S == this->S &&753 "Can only print analysis for the last processed SCoP");754 printStatistics(OS);755 756 if (!isModified()) {757 OS << "SCoP could not be simplified\n";758 return;759 }760 printAccesses(OS);761}762 763} // anonymous namespace764 765SmallVector<MemoryAccess *, 32> polly::getAccessesInOrder(ScopStmt &Stmt) {766 SmallVector<MemoryAccess *, 32> Accesses;767 768 for (MemoryAccess *MemAcc : Stmt)769 if (isImplicitRead(MemAcc))770 Accesses.push_back(MemAcc);771 772 for (MemoryAccess *MemAcc : Stmt)773 if (isExplicitAccess(MemAcc))774 Accesses.push_back(MemAcc);775 776 for (MemoryAccess *MemAcc : Stmt)777 if (isImplicitWrite(MemAcc))778 Accesses.push_back(MemAcc);779 780 return Accesses;781}782 783bool polly::runSimplify(Scop &S, int CallNo) {784 SimplifyImpl Impl(CallNo);785 Impl.run(S, S.getLI());786 if (PollyPrintSimplify) {787 outs() << "Printing analysis 'Polly - Simplify' for region: '"788 << S.getName() << "' in function '" << S.getFunction().getName()789 << "':\n";790 Impl.printScop(outs(), S);791 }792 793 return Impl.isModified();794}795