[Polly][Simplify] Remove unused instructions and accesses.

[Meinersbur]

Summary

Use a mark-and-sweep algorithm to find and remove unused instructions and MemoryAccesses. This is useful in particular to remove scalar writes that are never used anywhere. A scalar write in a loop induces a write-after-write dependency that stops the loop iterations to be rescheduled. Such writes can be a result of previous transformations such as DeLICM and operand tree forwarding.

It adds a new class VirtualInstruction that represents an instruction in a particular statement. At the moment an instruction can only belong to the statement that represents a BasicBlock. In the future, instructions can be in one of multiple statements representing a BasicBlock (Nandini's work), in different statements than its BasicBlock would indicate, and even multiple statements at once (by forwarding operand trees). It also integrates nicely with the VirtualUse class.

ScopStmt::contains(Instruction*) currently uses the instruction's parent BasicBlock to check whether it contains the instruction. It will need to check the actual statement list when one of the aforementioned features become possible.

polly/trunk/include/polly/ScopInfo.h

Loop *getSurroundingLoop() const {
     assert(!isCopyStmt() &&
            "No surrounding loop for artificially created statements");
     return SurroundingLoop;
   }
 
   /// 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.
   /// @returns The unique array memory access related to Inst or nullptr if
   ///          no array access exists
   MemoryAccess *getArrayAccessOrNULLFor(const Instruction *Inst) const {
     auto It = InstructionToAccess.find(Inst);
     if (It == InstructionToAccess.end())
public:
 
   Scop *getParent() { return &Parent; }
   const Scop *getParent() const { return &Parent; }
 
   const std::vector<Instruction *> &getInstructions() const {
     return Instructions;
   }
 
+  /// Set the list of instructions for this statement. It replaces the current
+  /// list.
+  void setInstructions(ArrayRef<Instruction *> Range) {
+    Instructions.assign(Range.begin(), Range.end());
+  }
+
+  std::vector<Instruction *>::const_iterator insts_begin() const {
+    return Instructions.begin();
+  }
+
+  std::vector<Instruction *>::const_iterator insts_end() const {
+    return Instructions.end();
+  }
+
+  /// The range of instructions in this statement.
+  llvm::iterator_range<std::vector<Instruction *>::const_iterator>
+  insts() const {
+    return {insts_begin(), insts_end()};
+  }
+
   const char *getBaseName() const;
 
   /// Set the isl AST build.
   void setAstBuild(__isl_keep isl_ast_build *B) { Build = B; }
 
   /// Get the isl AST build.
   __isl_keep isl_ast_build *getAstBuild() const { return Build; }
 

polly/trunk/include/polly/Support/VirtualInstruction.h

public:
   ///                     debugger sessions.
   void print(raw_ostream &OS, bool Reproducible = true) const;
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   void dump() const;
 #endif
 };
 
+/// An iterator for virtual operands.
+class VirtualOperandIterator
+    : public std::iterator<std::forward_iterator_tag, VirtualUse> {
+  friend class VirtualInstruction;
+  friend class VirtualUse;
+
+  using super = std::iterator<std::forward_iterator_tag, VirtualUse>;
+  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<VirtualInstruction>;
+
+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<VirtualOperandIterator> 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<VirtualInstruction> &UsedInsts,
+                   DenseSet<MemoryAccess *> &UsedAccs,
+                   ScopStmt *OnlyLocal = nullptr);
+
 } // namespace polly
 
+namespace llvm {
+/// Support VirtualInstructions in llvm::DenseMaps.
+template <> struct DenseMapInfo<polly::VirtualInstruction> {
+public:
+  static bool isEqual(polly::VirtualInstruction LHS,
+                      polly::VirtualInstruction RHS) {
+    return DenseMapInfo<polly::ScopStmt *>::isEqual(LHS.getStmt(),
+                                                    RHS.getStmt()) &&
+           DenseMapInfo<Instruction *>::isEqual(LHS.getInstruction(),
+                                                RHS.getInstruction());
+  }
+
+  static polly::VirtualInstruction getTombstoneKey() {
+    polly::VirtualInstruction TombstoneKey;
+    TombstoneKey.Stmt = DenseMapInfo<polly::ScopStmt *>::getTombstoneKey();
+    TombstoneKey.Inst = DenseMapInfo<Instruction *>::getTombstoneKey();
+    return TombstoneKey;
+  }
+
+  static polly::VirtualInstruction getEmptyKey() {
+    polly::VirtualInstruction EmptyKey;
+    EmptyKey.Stmt = DenseMapInfo<polly::ScopStmt *>::getEmptyKey();
+    EmptyKey.Inst = DenseMapInfo<Instruction *>::getEmptyKey();
+    return EmptyKey;
+  }
+
+  static unsigned getHashValue(polly::VirtualInstruction Val) {
+    return DenseMapInfo<std::pair<polly::ScopStmt *, Instruction *>>::
+        getHashValue(std::make_pair(Val.getStmt(), Val.getInstruction()));
+  }
+};
+} // namespace llvm
+
 #endif /* POLLY_SUPPORT_VIRTUALINSTRUCTION_H */

polly/trunk/lib/Analysis/ScopInfo.cpp

for (MemoryAccess *Access : MemAccs) {
     S.addAccessData(Access);
   }
 }
 
 MemoryAccess *ScopStmt::lookupPHIReadOf(PHINode *PHI) const {
   for (auto *MA : *this) {
     if (!MA->isRead())
       continue;
-    if (!MA->isLatestAnyPHIKind())
+    if (!MA->isOriginalAnyPHIKind())
       continue;
 
     if (MA->getAccessInstruction() == PHI)
       return MA;
   }
   return nullptr;
 }
 

polly/trunk/lib/Support/VirtualInstruction.cpp

 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 void VirtualUse::dump() const {
   print(errs(), false);
   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<LoadInst>(Inst) || isa<StoreInst>(Inst))
+    return false;
+
+  // Terminator instructions (in region statements) are required for control
+  // flow.
+  if (isa<TerminatorInst>(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<Instruction>(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<Instruction>(MA->getAccessValue()));
+}
+
+/// Add non-removable virtual instructions in @p Stmt to @p RootInsts.
+static void
+addInstructionRoots(ScopStmt *Stmt,
+                    SmallVectorImpl<VirtualInstruction> &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<MemoryAccess *> &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<VirtualInstruction> &RootInsts,
+                     SmallVectorImpl<MemoryAccess *> &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<VirtualInstruction> RootInsts,
+                          ArrayRef<MemoryAccess *> RootAccs,
+                          DenseSet<VirtualInstruction> &UsedInsts,
+                          DenseSet<MemoryAccess *> &UsedAccs,
+                          ScopStmt *OnlyLocal = nullptr) {
+  UsedInsts.clear();
+  UsedAccs.clear();
+
+  SmallVector<VirtualInstruction, 32> WorklistInsts;
+  SmallVector<MemoryAccess *, 32> 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<Instruction>(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<PHINode>(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<VirtualInstruction> &UsedInsts,
+                          DenseSet<MemoryAccess *> &UsedAccs,
+                          ScopStmt *OnlyLocal) {
+  SmallVector<VirtualInstruction, 32> RootInsts;
+  SmallVector<MemoryAccess *, 32> 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);
+}

polly/trunk/lib/Transform/Simplify.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "polly/Simplify.h"
 #include "polly/ScopInfo.h"
 #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"
 
 using namespace llvm;
 using namespace polly;
 
 namespace {
 
 STATISTIC(ScopsProcessed, "Number of SCoPs processed");
 STATISTIC(ScopsModified, "Number of SCoPs simplified");
 
 STATISTIC(PairUnequalAccRels, "Number of Load-Store pairs NOT removed because "
                               "of different access relations");
 STATISTIC(InBetweenStore, "Number of Load-Store pairs NOT removed because "
                           "there is another store between them");
 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) {
   return MA->isRead() && MA->isOriginalScalarKind();
 }
 
 static bool isExplicitAccess(MemoryAccess *MA) {
   return MA->isOriginalArrayKind();
private:
   Scop *S;
 
   /// Number of writes that are overwritten anyway.
   int OverwritesRemoved = 0;
 
   /// 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;
   }
 
   MemoryAccess *getReadAccessForValue(ScopStmt *Stmt, llvm::Value *Val) {
     if (!isa<Instruction>(Val))
       return nullptr;
 
     for (auto *MA : *Stmt) {
void removeUnnecessaryStmts() {
     S->simplifySCoP(true);
     assert(NumStmtsBefore >= S->getSize());
     StmtsRemoved = NumStmtsBefore - S->getSize();
     DEBUG(dbgs() << "Removed " << StmtsRemoved << " (of " << NumStmtsBefore
                  << ") statements\n");
     TotalStmtsRemoved += StmtsRemoved;
   }
 
+  /// Mark all reachable instructions and access, and sweep those that are not
+  /// reachable.
+  void markAndSweep(LoopInfo *LI) {
+    DenseSet<MemoryAccess *> UsedMA;
+    DenseSet<VirtualInstruction> 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<MemoryAccess *, 64> 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<Instruction *, 32> AllInsts(Stmt.insts_begin(),
+                                              Stmt.insts_end());
+      SmallVector<Instruction *, 32> 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";
     OS.indent(Indent + 4) << "Overwrites removed: " << OverwritesRemoved
                           << '\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";
   }
 
   /// Print the current state of all MemoryAccesses to @p OS.
   void printAccesses(llvm::raw_ostream &OS, int Indent = 0) const {
     OS.indent(Indent) << "After accesses {\n";
     for (auto &Stmt : *S) {
       OS.indent(Indent + 4) << Stmt.getBaseName() << "\n";
       for (auto *MA : Stmt)
         MA->print(OS);
     }
     OS.indent(Indent) << "}\n";
   }
 
 public:
   static char ID;
   explicit Simplify() : ScopPass(ID) {}
 
   virtual void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequiredTransitive<ScopInfoRegionPass>();
+    AU.addRequired<LoopInfoWrapperPass>();
     AU.setPreservesAll();
   }
 
   virtual bool runOnScop(Scop &S) override {
     // Reset statistics of last processed SCoP.
     releaseMemory();
     assert(!isModified());
 
     // Prepare processing of this SCoP.
     this->S = &S;
     ScopsProcessed++;
 
     DEBUG(dbgs() << "Removing overwrites...\n");
     removeOverwrites();
 
     DEBUG(dbgs() << "Removing redundant writes...\n");
     removeRedundantWrites();
 
+    DEBUG(dbgs() << "Cleanup unused accesses...\n");
+    LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
+    markAndSweep(LI);
+
     DEBUG(dbgs() << "Removing statements without side effects...\n");
     removeUnnecessaryStmts();
 
     if (isModified())
       ScopsModified++;
     DEBUG(dbgs() << "\nFinal Scop:\n");
     DEBUG(S.print(dbgs()));
 
virtual void printScop(raw_ostream &OS, Scop &S) const override {
     printAccesses(OS);
   }
 
   virtual void releaseMemory() override {
     S = nullptr;
 
     OverwritesRemoved = 0;
     RedundantWritesRemoved = 0;
+    DeadAccessesRemoved = 0;
+    DeadInstructionsRemoved = 0;
     StmtsRemoved = 0;
   }
 };
 
 char Simplify::ID;
 } // anonymous namespace
 
 Pass *polly::createSimplifyPass() { return new Simplify(); }
 
 INITIALIZE_PASS_BEGIN(Simplify, "polly-simplify", "Polly - Simplify", false,
                       false)
+INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 INITIALIZE_PASS_END(Simplify, "polly-simplify", "Polly - Simplify", false,
                     false)

polly/trunk/test/Simplify/dead_access_load.ll

+; 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: }

polly/trunk/test/Simplify/dead_access_phi.ll

+; 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: }

polly/trunk/test/Simplify/dead_access_value.ll

+; 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: }

polly/trunk/test/Simplify/dead_instruction.ll

+; 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: }