polly/lib/Transform/DeadCodeElimination.cpp

   1 //===- DeadCodeElimination.cpp - Eliminate dead iteration  ----------------===//
   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-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // The polyhedral dead code elimination pass analyses a SCoP to eliminate
  10 // statement instances that can be proven dead.
  11 // As a consequence, the code generated for this SCoP may execute a statement
  12 // less often. This means, a statement may be executed only in certain loop
  13 // iterations or it may not even be part of the generated code at all.
  14 //
  15 // This code:
  16 //
  17 //    for (i = 0; i < N; i++)
  18 //        arr[i] = 0;
  19 //    for (i = 0; i < N; i++)
  20 //        arr[i] = 10;
  21 //    for (i = 0; i < N; i++)
  22 //        arr[i] = i;
  23 //
  24 // is e.g. simplified to:
  25 //
  26 //    for (i = 0; i < N; i++)
  27 //        arr[i] = i;
  28 //
  29 // The idea and the algorithm used was first implemented by Sven Verdoolaege in
  30 // the 'ppcg' tool.
  31 //
  32 //===----------------------------------------------------------------------===//
  33
  34 #include "polly/DeadCodeElimination.h"
  35 #include "polly/DependenceInfo.h"
  36 #include "polly/LinkAllPasses.h"
  37 #include "polly/Options.h"
  38 #include "polly/ScopInfo.h"
  39 #include "llvm/Support/CommandLine.h"
  40 #include "isl/isl-noexceptions.h"
  41
  42 using namespace llvm;
  43 using namespace polly;
  44
  45 namespace {
  46
  47 cl::opt<int> DCEPreciseSteps(
  48     "polly-dce-precise-steps",
  49     cl::desc("The number of precise steps between two approximating "
  50              "iterations. (A value of -1 schedules another approximation stage "
  51              "before the actual dead code elimination."),
  52     cl::init(-1), cl::cat(PollyCategory));
  53
  54 class DeadCodeElimWrapperPass final : public ScopPass {
  55 public:
  56   static char ID;
  57   explicit DeadCodeElimWrapperPass() : ScopPass(ID) {}
  58
  59   /// Remove dead iterations from the schedule of @p S.
  60   bool runOnScop(Scop &S) override;
  61
  62   /// Register all analyses and transformation required.
  63   void getAnalysisUsage(AnalysisUsage &AU) const override;
  64 };
  65
  66 char DeadCodeElimWrapperPass::ID = 0;
  67
  68 /// Return the set of live iterations.
  69 ///
  70 /// The set of live iterations are all iterations that write to memory and for
  71 /// which we can not prove that there will be a later write that _must_
  72 /// overwrite the same memory location and is consequently the only one that
  73 /// is visible after the execution of the SCoP.
  74 ///
  75 /// To compute the live outs, we compute for the data-locations that are
  76 /// must-written to the last statement that touches these locations. On top of
  77 /// this we add all statements that perform may-write accesses.
  78 ///
  79 /// We could be more precise by removing may-write accesses for which we know
  80 /// that they are overwritten by a must-write after. However, at the moment the
  81 /// only may-writes we introduce access the full (unbounded) array, such that
  82 /// bounded write accesses can not overwrite all of the data-locations. As
  83 /// this means may-writes are in the current situation always live, there is
  84 /// no point in trying to remove them from the live-out set.
  85 static isl::union_set getLiveOut(Scop &S) {
  86   isl::union_map Schedule = S.getSchedule();
  87   isl::union_map MustWrites = S.getMustWrites();
  88   isl::union_map WriteIterations = MustWrites.reverse();
  89   isl::union_map WriteTimes = WriteIterations.apply_range(Schedule);
  90
  91   isl::union_map LastWriteTimes = WriteTimes.lexmax();
  92   isl::union_map LastWriteIterations =
  93       LastWriteTimes.apply_range(Schedule.reverse());
  94
  95   isl::union_set Live = LastWriteIterations.range();
  96   isl::union_map MayWrites = S.getMayWrites();
  97   Live = Live.unite(MayWrites.domain());
  98   return Live.coalesce();
  99 }
 100
 101 /// Performs polyhedral dead iteration elimination by:
 102 /// o Assuming that the last write to each location is live.
 103 /// o Following each RAW dependency from a live iteration backwards and adding
 104 ///   that iteration to the live set.
 105 ///
 106 /// To ensure the set of live iterations does not get too complex we always
 107 /// combine a certain number of precise steps with one approximating step that
 108 /// simplifies the life set with an affine hull.
 109 static bool runDeadCodeElimination(Scop &S, int PreciseSteps,
 110                                    const Dependences &D) {
 111   if (!D.hasValidDependences())
 112     return false;
 113
 114   isl::union_set Live = getLiveOut(S);
 115   isl::union_map Dep =
 116       D.getDependences(Dependences::TYPE_RAW | Dependences::TYPE_RED);
 117   Dep = Dep.reverse();
 118
 119   if (PreciseSteps == -1)
 120     Live = Live.affine_hull();
 121
 122   isl::union_set OriginalDomain = S.getDomains();
 123   int Steps = 0;
 124   while (true) {
 125     Steps++;
 126
 127     isl::union_set Extra = Live.apply(Dep);
 128
 129     if (Extra.is_subset(Live))
 130       break;
 131
 132     Live = Live.unite(Extra);
 133
 134     if (Steps > PreciseSteps) {
 135       Steps = 0;
 136       Live = Live.affine_hull();
 137     }
 138
 139     Live = Live.intersect(OriginalDomain);
 140   }
 141
 142   Live = Live.coalesce();
 143
 144   return S.restrictDomains(Live);
 145 }
 146
 147 bool DeadCodeElimWrapperPass::runOnScop(Scop &S) {
 148   auto &DI = getAnalysis<DependenceInfo>();
 149   const Dependences &Deps = DI.getDependences(Dependences::AL_Statement);
 150
 151   bool Changed = runDeadCodeElimination(S, DCEPreciseSteps, Deps);
 152
 153   // FIXME: We can probably avoid the recomputation of all dependences by
 154   // updating them explicitly.
 155   if (Changed)
 156     DI.recomputeDependences(Dependences::AL_Statement);
 157
 158   return false;
 159 }
 160
 161 void DeadCodeElimWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
 162   ScopPass::getAnalysisUsage(AU);
 163   AU.addRequired<DependenceInfo>();
 164 }
 165
 166 } // namespace
 167
 168 Pass *polly::createDeadCodeElimWrapperPass() {
 169   return new DeadCodeElimWrapperPass();
 170 }
 171
 172 llvm::PreservedAnalyses DeadCodeElimPass::run(Scop &S, ScopAnalysisManager &SAM,
 173                                               ScopStandardAnalysisResults &SAR,
 174                                               SPMUpdater &U) {
 175   DependenceAnalysis::Result &DA = SAM.getResult<DependenceAnalysis>(S, SAR);
 176   const Dependences &Deps = DA.getDependences(Dependences::AL_Statement);
 177
 178   bool Changed = runDeadCodeElimination(S, DCEPreciseSteps, Deps);
 179
 180   // FIXME: We can probably avoid the recomputation of all dependences by
 181   // updating them explicitly.
 182   if (Changed)
 183     DA.recomputeDependences(Dependences::AL_Statement);
 184
 185   if (!Changed)
 186     return PreservedAnalyses::all();
 187
 188   PreservedAnalyses PA;
 189   PA.preserveSet<AllAnalysesOn<Module>>();
 190   PA.preserveSet<AllAnalysesOn<Function>>();
 191   PA.preserveSet<AllAnalysesOn<Loop>>();
 192   return PA;
 193 }
 194
 195 INITIALIZE_PASS_BEGIN(DeadCodeElimWrapperPass, "polly-dce",
 196                       "Polly - Remove dead iterations", false, false)
 197 INITIALIZE_PASS_DEPENDENCY(DependenceInfo)
 198 INITIALIZE_PASS_DEPENDENCY(ScopInfoRegionPass)
 199 INITIALIZE_PASS_END(DeadCodeElimWrapperPass, "polly-dce",
 200                     "Polly - Remove dead iterations", false, false)