Index: polly/trunk/include/polly/ScopInfo.h =================================================================== --- polly/trunk/include/polly/ScopInfo.h +++ polly/trunk/include/polly/ScopInfo.h @@ -1429,6 +1429,22 @@ /// Return true if this statement does not contain any accesses. bool isEmpty() const { return MemAccs.empty(); } + /// Find all array accesses for @p Inst. + /// + /// @param Inst The instruction accessing an array. + /// + /// @return A list of array accesses (MemoryKind::Array) accessed by @p Inst. + /// If there is no such access, it returns nullptr. + const MemoryAccessList * + lookupArrayAccessesFor(const Instruction *Inst) const { + auto It = InstructionToAccess.find(Inst); + if (It == InstructionToAccess.end()) + return nullptr; + if (It->second.empty()) + return nullptr; + return &It->second; + } + /// Return the only array access for @p Inst, if existing. /// /// @param Inst The instruction for which to look up the access. @@ -1545,6 +1561,26 @@ return Instructions; } + /// Set the list of instructions for this statement. It replaces the current + /// list. + void setInstructions(ArrayRef Range) { + Instructions.assign(Range.begin(), Range.end()); + } + + std::vector::const_iterator insts_begin() const { + return Instructions.begin(); + } + + std::vector::const_iterator insts_end() const { + return Instructions.end(); + } + + /// The range of instructions in this statement. + llvm::iterator_range::const_iterator> + insts() const { + return {insts_begin(), insts_end()}; + } + const char *getBaseName() const; /// Set the isl AST build. Index: polly/trunk/include/polly/Support/VirtualInstruction.h =================================================================== --- polly/trunk/include/polly/Support/VirtualInstruction.h +++ polly/trunk/include/polly/Support/VirtualInstruction.h @@ -163,6 +163,183 @@ #endif }; +/// An iterator for virtual operands. +class VirtualOperandIterator + : public std::iterator { + friend class VirtualInstruction; + friend class VirtualUse; + + using super = std::iterator; + using Self = VirtualOperandIterator; + + ScopStmt *User; + User::op_iterator U; + + VirtualOperandIterator(ScopStmt *User, User::op_iterator U) + : User(User), U(U) {} + +public: + using pointer = typename super::pointer; + using reference = typename super::reference; + + inline bool operator==(const Self &that) const { + assert(this->User == that.User); + return this->U == that.U; + } + + inline bool operator!=(const Self &that) const { + assert(this->User == that.User); + return this->U != that.U; + } + + VirtualUse operator*() const { + return VirtualUse::create(User, User->getSurroundingLoop(), U->get(), true); + } + + Use *operator->() const { return U; } + + Self &operator++() { + U++; + return *this; + } + + Self operator++(int) { + Self tmp = *this; + ++*this; + return tmp; + } +}; + +/// This class represents a "virtual instruction", an instruction in a ScopStmt, +/// effectively a ScopStmt/Instruction-pair. +/// +/// An instructions can be moved between statements (e.g. to avoid a scalar +/// dependency) and even can be contained in multiple statements (for instance, +/// to recompute a value instead of transferring it), hence 'virtual'. This +/// class is required to represent such instructions that are not in their +/// 'physical' location anymore. +/// +/// A statement can currently not contain the same instructions multiple times +/// (that is, from different loop iterations). Therefore, a +/// ScopStmt/Instruction-pair uniquely identifies a virtual instructions. +/// ScopStmt::getInstruction() can contain the same instruction multiple times, +/// but they necessarily compute the same value. +class VirtualInstruction { + friend class VirtualOperandIterator; + friend struct llvm::DenseMapInfo; + +private: + /// The statement this virtual instruction is in. + ScopStmt *Stmt = nullptr; + + /// The instruction of a statement. + Instruction *Inst = nullptr; + +public: + VirtualInstruction() {} + + /// Create a new virtual instruction of an instruction @p Inst in @p Stmt. + VirtualInstruction(ScopStmt *Stmt, Instruction *Inst) + : Stmt(Stmt), Inst(Inst) { + assert(Stmt && Inst); + assert(Stmt->contains(Inst) && + "A virtual instruction must be exist in that statement"); + } + + VirtualOperandIterator operand_begin() const { + return VirtualOperandIterator(Stmt, Inst->op_begin()); + } + + VirtualOperandIterator operand_end() const { + return VirtualOperandIterator(Stmt, Inst->op_end()); + } + + /// Returns a list of virtual operands. + /// + /// Virtual operands, like virtual instructions, need to encode the ScopStmt + /// they are in. + llvm::iterator_range operands() const { + return {operand_begin(), operand_end()}; + } + + /// Return the SCoP everything is contained in. + Scop *getScop() const { return Stmt->getParent(); } + + /// Return the ScopStmt this virtual instruction is in. + ScopStmt *getStmt() const { return Stmt; } + + /// Return the instruction in the statement. + Instruction *getInstruction() const { return Inst; } + + /// Print a description of this object. + /// + /// @param OS Stream to print to. + /// @param Reproducible If true, ensures that the output is stable between + /// runs and is suitable for checks in regression tests. + /// This excludes printing e.g., pointer values. If false, + /// the output should not be used for regression tests, + /// but may contain more information useful in debugger + /// sessions. + void print(raw_ostream &OS, bool Reproducible = true) const; + +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) + void dump() const; +#endif +}; + +static inline bool operator==(VirtualInstruction LHS, VirtualInstruction RHS) { + return LHS.getStmt() == RHS.getStmt() && + LHS.getInstruction() == RHS.getInstruction(); +} + +/// Find all reachable instructions and accesses. +/// +/// @param S The SCoP to find everything reachable in. +/// @param LI LoopInfo required for analysis. +/// @param UsedInsts[out] Receives all reachable instructions. +/// @param UsedAccs[out] Receives all reachable accesses. +/// @param OnlyLocal If non-nullptr, activates local mode: The SCoP is +/// assumed to consist only of this statement and is +/// conservatively correct. Does not require walking the +/// whole SCoP. +void markReachable(Scop *S, LoopInfo *LI, + DenseSet &UsedInsts, + DenseSet &UsedAccs, + ScopStmt *OnlyLocal = nullptr); + } // namespace polly +namespace llvm { +/// Support VirtualInstructions in llvm::DenseMaps. +template <> struct DenseMapInfo { +public: + static bool isEqual(polly::VirtualInstruction LHS, + polly::VirtualInstruction RHS) { + return DenseMapInfo::isEqual(LHS.getStmt(), + RHS.getStmt()) && + DenseMapInfo::isEqual(LHS.getInstruction(), + RHS.getInstruction()); + } + + static polly::VirtualInstruction getTombstoneKey() { + polly::VirtualInstruction TombstoneKey; + TombstoneKey.Stmt = DenseMapInfo::getTombstoneKey(); + TombstoneKey.Inst = DenseMapInfo::getTombstoneKey(); + return TombstoneKey; + } + + static polly::VirtualInstruction getEmptyKey() { + polly::VirtualInstruction EmptyKey; + EmptyKey.Stmt = DenseMapInfo::getEmptyKey(); + EmptyKey.Inst = DenseMapInfo::getEmptyKey(); + return EmptyKey; + } + + static unsigned getHashValue(polly::VirtualInstruction Val) { + return DenseMapInfo>:: + getHashValue(std::make_pair(Val.getStmt(), Val.getInstruction())); + } +}; +} // namespace llvm + #endif /* POLLY_SUPPORT_VIRTUALINSTRUCTION_H */ Index: polly/trunk/lib/Analysis/ScopInfo.cpp =================================================================== --- polly/trunk/lib/Analysis/ScopInfo.cpp +++ polly/trunk/lib/Analysis/ScopInfo.cpp @@ -1313,7 +1313,7 @@ for (auto *MA : *this) { if (!MA->isRead()) continue; - if (!MA->isLatestAnyPHIKind()) + if (!MA->isOriginalAnyPHIKind()) continue; if (MA->getAccessInstruction() == PHI) Index: polly/trunk/lib/Support/VirtualInstruction.cpp =================================================================== --- polly/trunk/lib/Support/VirtualInstruction.cpp +++ polly/trunk/lib/Support/VirtualInstruction.cpp @@ -126,3 +126,276 @@ errs() << '\n'; } #endif + +void VirtualInstruction::print(raw_ostream &OS, bool Reproducible) const { + if (!Stmt || !Inst) { + OS << "[null VirtualInstruction]"; + return; + } + + OS << "[" << Stmt->getBaseName() << "]"; + Inst->print(OS, !Reproducible); +} + +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) +void VirtualInstruction::dump() const { + print(errs(), false); + errs() << '\n'; +} +#endif + +/// Return true if @p Inst cannot be removed, even if it is nowhere referenced. +static bool isRoot(const Instruction *Inst) { + // The store is handled by its MemoryAccess. The load must be reached from the + // roots in order to be marked as used. + if (isa(Inst) || isa(Inst)) + return false; + + // Terminator instructions (in region statements) are required for control + // flow. + if (isa(Inst)) + return true; + + // Writes to memory must be honored. + if (Inst->mayWriteToMemory()) + return true; + + return false; +} + +/// Return true if @p ComputingInst is used after SCoP @p S. It must not be +/// removed in order for its value to be available after the SCoP. +static bool isEscaping(Scop *S, Instruction *ComputingInst) { + for (Use &Use : ComputingInst->uses()) { + Instruction *User = cast(Use.getUser()); + if (!S->contains(User)) + return true; + } + return false; +} + +/// Return true for MemoryAccesses that cannot be removed because it represents +/// an llvm::Value that is used after the SCoP. +static bool isEscaping(MemoryAccess *MA) { + assert(MA->isOriginalValueKind()); + return isEscaping(MA->getStatement()->getParent(), + cast(MA->getAccessValue())); +} + +/// Add non-removable virtual instructions in @p Stmt to @p RootInsts. +static void +addInstructionRoots(ScopStmt *Stmt, + SmallVectorImpl &RootInsts) { + // For region statements we must keep all instructions because we do not + // support removing instructions from region statements. + if (!Stmt->isBlockStmt()) { + for (auto *BB : Stmt->getRegion()->blocks()) + for (Instruction &Inst : *BB) + RootInsts.emplace_back(Stmt, &Inst); + } + + for (Instruction *Inst : Stmt->getInstructions()) + if (isRoot(Inst)) + RootInsts.emplace_back(Stmt, Inst); +} + +/// Add non-removable memory accesses in @p Stmt to @p RootInsts. +/// +/// @param Local If true, all writes are assumed to escape. markAndSweep +/// algorithms can use this to be applicable to a single ScopStmt only without +/// the risk of removing definitions required by other statements. +/// If false, only writes for SCoP-escaping values are roots. This +/// is global mode, where such writes must be marked by theirs uses +/// in order to be reachable. +static void addAccessRoots(ScopStmt *Stmt, + SmallVectorImpl &RootAccs, + bool Local) { + for (auto *MA : *Stmt) { + if (!MA->isWrite()) + continue; + + // Writes to arrays are always used. + if (MA->isLatestArrayKind()) + RootAccs.push_back(MA); + + // Values are roots if they are escaping. + else if (MA->isLatestValueKind()) { + if (Local || isEscaping(MA)) + RootAccs.push_back(MA); + } + + // Exit phis are, by definition, escaping. + else if (MA->isLatestExitPHIKind()) + RootAccs.push_back(MA); + + // phi writes are only roots if we are not visiting the statement + // containing the PHINode. + else if (Local && MA->isLatestPHIKind()) + RootAccs.push_back(MA); + } +} + +/// Determine all instruction and access roots. +static void addRoots(ScopStmt *Stmt, + SmallVectorImpl &RootInsts, + SmallVectorImpl &RootAccs, bool Local) { + addInstructionRoots(Stmt, RootInsts); + addAccessRoots(Stmt, RootAccs, Local); +} + +/// Mark accesses and instructions as used if they are reachable from a root, +/// walking the operand trees. +/// +/// @param S The SCoP to walk. +/// @param LI The LoopInfo Analysis. +/// @param RootInsts List of root instructions. +/// @param RootAccs List of root accesses. +/// @param UsesInsts[out] Receives all reachable instructions, including the +/// roots. +/// @param UsedAccs[out] Receives all reachable accesses, including the roots. +/// @param OnlyLocal If non-nullptr, restricts walking to a single +/// statement. +static void walkReachable(Scop *S, LoopInfo *LI, + ArrayRef RootInsts, + ArrayRef RootAccs, + DenseSet &UsedInsts, + DenseSet &UsedAccs, + ScopStmt *OnlyLocal = nullptr) { + UsedInsts.clear(); + UsedAccs.clear(); + + SmallVector WorklistInsts; + SmallVector WorklistAccs; + + WorklistInsts.append(RootInsts.begin(), RootInsts.end()); + WorklistAccs.append(RootAccs.begin(), RootAccs.end()); + + auto AddToWorklist = [&](VirtualUse VUse) { + switch (VUse.getKind()) { + case VirtualUse::Block: + case VirtualUse::Constant: + case VirtualUse::Synthesizable: + case VirtualUse::Hoisted: + break; + case VirtualUse::ReadOnly: + // Read-only scalars only have MemoryAccesses if ModelReadOnlyScalars is + // enabled. + if (!VUse.getMemoryAccess()) + break; + LLVM_FALLTHROUGH; + case VirtualUse::Inter: + assert(VUse.getMemoryAccess()); + WorklistAccs.push_back(VUse.getMemoryAccess()); + break; + case VirtualUse::Intra: + WorklistInsts.emplace_back(VUse.getUser(), + cast(VUse.getValue())); + break; + } + }; + + while (true) { + // We have two worklists to process: Only when the MemoryAccess worklist is + // empty, we process the instruction worklist. + + while (!WorklistAccs.empty()) { + auto *Acc = WorklistAccs.pop_back_val(); + + ScopStmt *Stmt = Acc->getStatement(); + if (OnlyLocal && Stmt != OnlyLocal) + continue; + + auto Inserted = UsedAccs.insert(Acc); + if (!Inserted.second) + continue; + + if (Acc->isRead()) { + const ScopArrayInfo *SAI = Acc->getScopArrayInfo(); + + if (Acc->isOriginalValueKind()) { + MemoryAccess *DefAcc = S->getValueDef(SAI); + + // Accesses to read-only values do not have a definition. + if (DefAcc) + WorklistAccs.push_back(S->getValueDef(SAI)); + } + + if (Acc->isOriginalAnyPHIKind()) { + auto IncomingMAs = S->getPHIIncomings(SAI); + WorklistAccs.append(IncomingMAs.begin(), IncomingMAs.end()); + } + } + + if (Acc->isWrite()) { + if (Acc->isOriginalValueKind() || + (Acc->isOriginalArrayKind() && Acc->getAccessValue())) { + Loop *Scope = Stmt->getSurroundingLoop(); + VirtualUse VUse = + VirtualUse::create(S, Stmt, Scope, Acc->getAccessValue(), true); + AddToWorklist(VUse); + } + + if (Acc->isOriginalAnyPHIKind()) { + for (auto Incoming : Acc->getIncoming()) { + VirtualUse VUse = VirtualUse::create( + S, Stmt, LI->getLoopFor(Incoming.first), Incoming.second, true); + AddToWorklist(VUse); + } + } + + if (Acc->isOriginalArrayKind()) + WorklistInsts.emplace_back(Stmt, Acc->getAccessInstruction()); + } + } + + // If both worklists are empty, stop walking. + if (WorklistInsts.empty()) + break; + + VirtualInstruction VInst = WorklistInsts.pop_back_val(); + ScopStmt *Stmt = VInst.getStmt(); + Instruction *Inst = VInst.getInstruction(); + + // Do not process statements other than the local. + if (OnlyLocal && Stmt != OnlyLocal) + continue; + + auto InsertResult = UsedInsts.insert(VInst); + if (!InsertResult.second) + continue; + + // Add all operands to the worklists. + if (PHINode *PHI = dyn_cast(Inst)) { + if (MemoryAccess *PHIRead = Stmt->lookupPHIReadOf(PHI)) + WorklistAccs.push_back(PHIRead); + } else { + for (VirtualUse VUse : VInst.operands()) + AddToWorklist(VUse); + } + + // If there is an array access, also add its MemoryAccesses to the worklist. + const MemoryAccessList *Accs = Stmt->lookupArrayAccessesFor(Inst); + if (!Accs) + continue; + + for (MemoryAccess *Acc : *Accs) + WorklistAccs.push_back(Acc); + } +} + +void polly::markReachable(Scop *S, LoopInfo *LI, + DenseSet &UsedInsts, + DenseSet &UsedAccs, + ScopStmt *OnlyLocal) { + SmallVector RootInsts; + SmallVector RootAccs; + + if (OnlyLocal) { + addRoots(OnlyLocal, RootInsts, RootAccs, true); + } else { + for (auto &Stmt : *S) + addRoots(&Stmt, RootInsts, RootAccs, false); + } + + walkReachable(S, LI, RootInsts, RootAccs, UsedInsts, UsedAccs, OnlyLocal); +} Index: polly/trunk/lib/Transform/Simplify.cpp =================================================================== --- polly/trunk/lib/Transform/Simplify.cpp +++ polly/trunk/lib/Transform/Simplify.cpp @@ -16,6 +16,7 @@ #include "polly/ScopPass.h" #include "polly/Support/GICHelper.h" #include "polly/Support/ISLOStream.h" +#include "polly/Support/VirtualInstruction.h" #include "llvm/ADT/Statistic.h" #include "llvm/Support/Debug.h" #define DEBUG_TYPE "polly-simplify" @@ -35,6 +36,9 @@ STATISTIC(TotalOverwritesRemoved, "Number of removed overwritten writes"); STATISTIC(TotalRedundantWritesRemoved, "Number of writes of same value removed in any SCoP"); +STATISTIC(TotalDeadAccessesRemoved, "Number of dead accesses removed"); +STATISTIC(TotalDeadInstructionsRemoved, + "Number of unused instructions removed"); STATISTIC(TotalStmtsRemoved, "Number of statements removed in any SCoP"); static bool isImplicitRead(MemoryAccess *MA) { @@ -93,12 +97,19 @@ /// Number of redundant writes removed from this SCoP. int RedundantWritesRemoved = 0; + /// Number of unused accesses removed from this SCoP. + int DeadAccessesRemoved = 0; + + /// Number of unused instructions removed from this SCoP. + int DeadInstructionsRemoved = 0; + /// Number of unnecessary statements removed from the SCoP. int StmtsRemoved = 0; /// Return whether at least one simplification has been applied. bool isModified() const { return OverwritesRemoved > 0 || RedundantWritesRemoved > 0 || + DeadAccessesRemoved > 0 || DeadInstructionsRemoved > 0 || StmtsRemoved > 0; } @@ -308,6 +319,60 @@ TotalStmtsRemoved += StmtsRemoved; } + /// Mark all reachable instructions and access, and sweep those that are not + /// reachable. + void markAndSweep(LoopInfo *LI) { + DenseSet UsedMA; + DenseSet UsedInsts; + + // Get all reachable instructions and accesses. + markReachable(S, LI, UsedInsts, UsedMA); + + // Remove all non-reachable accesses. + // We need get all MemoryAccesses first, in order to not invalidate the + // iterators when removing them. + SmallVector AllMAs; + for (ScopStmt &Stmt : *S) + AllMAs.append(Stmt.begin(), Stmt.end()); + + for (MemoryAccess *MA : AllMAs) { + if (UsedMA.count(MA)) + continue; + DEBUG(dbgs() << "Removing " << MA << " because its value is not used\n"); + ScopStmt *Stmt = MA->getStatement(); + Stmt->removeSingleMemoryAccess(MA); + + DeadAccessesRemoved++; + TotalDeadAccessesRemoved++; + } + + // Remove all non-reachable instructions. + for (ScopStmt &Stmt : *S) { + SmallVector AllInsts(Stmt.insts_begin(), + Stmt.insts_end()); + SmallVector RemainInsts; + + for (Instruction *Inst : AllInsts) { + auto It = UsedInsts.find({&Stmt, Inst}); + if (It == UsedInsts.end()) { + DEBUG(dbgs() << "Removing "; Inst->print(dbgs()); + dbgs() << " because it is not used\n"); + DeadInstructionsRemoved++; + TotalDeadInstructionsRemoved++; + continue; + } + + RemainInsts.push_back(Inst); + + // If instructions appear multiple times, keep only the first. + UsedInsts.erase(It); + } + + // Set the new instruction list to be only those we did not remove. + Stmt.setInstructions(RemainInsts); + } + } + /// Print simplification statistics to @p OS. void printStatistics(llvm::raw_ostream &OS, int Indent = 0) const { OS.indent(Indent) << "Statistics {\n"; @@ -315,6 +380,10 @@ << '\n'; OS.indent(Indent + 4) << "Redundant writes removed: " << RedundantWritesRemoved << "\n"; + OS.indent(Indent + 4) << "Dead accesses removed: " << DeadAccessesRemoved + << '\n'; + OS.indent(Indent + 4) << "Dead instructions removed: " + << DeadInstructionsRemoved << '\n'; OS.indent(Indent + 4) << "Stmts removed: " << StmtsRemoved << "\n"; OS.indent(Indent) << "}\n"; } @@ -336,6 +405,7 @@ virtual void getAnalysisUsage(AnalysisUsage &AU) const override { AU.addRequiredTransitive(); + AU.addRequired(); AU.setPreservesAll(); } @@ -354,6 +424,10 @@ DEBUG(dbgs() << "Removing redundant writes...\n"); removeRedundantWrites(); + DEBUG(dbgs() << "Cleanup unused accesses...\n"); + LoopInfo *LI = &getAnalysis().getLoopInfo(); + markAndSweep(LI); + DEBUG(dbgs() << "Removing statements without side effects...\n"); removeUnnecessaryStmts(); @@ -382,6 +456,8 @@ OverwritesRemoved = 0; RedundantWritesRemoved = 0; + DeadAccessesRemoved = 0; + DeadInstructionsRemoved = 0; StmtsRemoved = 0; } }; @@ -393,5 +469,6 @@ INITIALIZE_PASS_BEGIN(Simplify, "polly-simplify", "Polly - Simplify", false, false) +INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) INITIALIZE_PASS_END(Simplify, "polly-simplify", "Polly - Simplify", false, false) Index: polly/trunk/test/Simplify/dead_access_load.ll =================================================================== --- polly/trunk/test/Simplify/dead_access_load.ll +++ polly/trunk/test/Simplify/dead_access_load.ll @@ -0,0 +1,46 @@ +; RUN: opt %loadPolly -polly-simplify -analyze < %s | FileCheck %s -match-full-lines +; +; Remove a dead load-instruction +; (an load whose result is not used anywhere) +; +; for (int j = 0; j < n; j += 1) { +; double val = A[0]; +; A[0] = 42.0; +; } +; +define void @func(i32 %n, double* noalias nonnull %A) { +entry: + br label %for + +for: + %j = phi i32 [0, %entry], [%j.inc, %inc] + %j.cmp = icmp slt i32 %j, %n + br i1 %j.cmp, label %body, label %exit + + body: + %val = load double, double* %A + store double 42.0, double* %A + br label %inc + +inc: + %j.inc = add nuw nsw i32 %j, 1 + br label %for + +exit: + br label %return + +return: + ret void +} + + +; CHECK: Statistics { +; CHECK: Dead accesses removed: 1 +; CHECK: Dead instructions removed: 1 +; CHECK: } + +; CHECK: After accesses { +; CHECK-NEXT: Stmt_body +; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: [n] -> { Stmt_body[i0] -> MemRef_A[0] }; +; CHECK-NEXT: } Index: polly/trunk/test/Simplify/dead_access_phi.ll =================================================================== --- polly/trunk/test/Simplify/dead_access_phi.ll +++ polly/trunk/test/Simplify/dead_access_phi.ll @@ -0,0 +1,53 @@ +; RUN: opt %loadPolly -polly-simplify -analyze < %s | FileCheck %s -match-full-lines +; +; Remove a dead PHI write/read pair +; (accesses that are effectively not used) +; +; for (int j = 0; j < n; j += 1) { +; body: +; double phi = 42; +; +; body_succ: +; A[0] = 42.0; +; } +; +define void @func(i32 %n, double* noalias nonnull %A) { +entry: + br label %for + +for: + %j = phi i32 [0, %entry], [%j.inc, %inc] + %j.cmp = icmp slt i32 %j, %n + br i1 %j.cmp, label %body, label %exit + + body: + br label %body_succ + + body_succ: + %phi = phi double [42.0, %body] + store double 42.0, double* %A + br label %inc + +inc: + %j.inc = add nuw nsw i32 %j, 1 + br label %for + +exit: + br label %return + +return: + ret void +} + + +; CHECK: Statistics { +; CHECK: Dead accesses removed: 2 +; CHECK: Dead instructions removed: 1 +; CHECK: Stmts removed: 1 +; CHECK: } + +; CHECK: After accesses { +; CHECK-NEXT: Stmt_body_succ +; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: [n] -> { Stmt_body_succ[i0] -> MemRef_A[0] }; +; CHECK-NEXT: } Index: polly/trunk/test/Simplify/dead_access_value.ll =================================================================== --- polly/trunk/test/Simplify/dead_access_value.ll +++ polly/trunk/test/Simplify/dead_access_value.ll @@ -0,0 +1,55 @@ +; RUN: opt %loadPolly -polly-simplify -analyze < %s | FileCheck %s -match-full-lines +; +; Remove a dead value write/read pair +; (accesses that are effectively not used) +; +; for (int j = 0; j < n; j += 1) { +; body: +; double val = 12.5 + 12.5; +; +; body_succ: +; double unused = val + 21.0; +; A[0] = 42.0; +; } +; +define void @func(i32 %n, double* noalias nonnull %A) { +entry: + br label %for + +for: + %j = phi i32 [0, %entry], [%j.inc, %inc] + %j.cmp = icmp slt i32 %j, %n + br i1 %j.cmp, label %body, label %exit + + body: + %val = fadd double 12.5, 12.5 + br label %body_succ + + body_succ: + %unused = fadd double %val, 21.0 + store double 42.0, double* %A + br label %inc + +inc: + %j.inc = add nuw nsw i32 %j, 1 + br label %for + +exit: + br label %return + +return: + ret void +} + + +; CHECK: Statistics { +; CHECK: Dead accesses removed: 2 +; CHECK: Dead instructions removed: 2 +; CHECK: Stmts removed: 1 +; CHECK: } + +; CHECK: After accesses { +; CHECK-NEXT: Stmt_body_succ +; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: [n] -> { Stmt_body_succ[i0] -> MemRef_A[0] }; +; CHECK-NEXT: } Index: polly/trunk/test/Simplify/dead_instruction.ll =================================================================== --- polly/trunk/test/Simplify/dead_instruction.ll +++ polly/trunk/test/Simplify/dead_instruction.ll @@ -0,0 +1,39 @@ +; RUN: opt %loadPolly -polly-simplify -analyze < %s | FileCheck %s -match-full-lines +; +; Remove a dead instruction +; (an instruction whose result is not used anywhere) +; +; for (int j = 0; j < n; j += 1) { +; double val = 21.0 + 21.0; +; A[0] = 42.0; +; } +; +define void @func(i32 %n, double* noalias nonnull %A) { +entry: + br label %for + +for: + %j = phi i32 [0, %entry], [%j.inc, %inc] + %j.cmp = icmp slt i32 %j, %n + br i1 %j.cmp, label %body, label %exit + + body: + %val = fadd double 21.0, 21.0 + store double 42.0, double* %A + br label %inc + +inc: + %j.inc = add nuw nsw i32 %j, 1 + br label %for + +exit: + br label %return + +return: + ret void +} + + +; CHECK: Statistics { +; CHECK: Dead instructions removed: 1 +; CHECK: }