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) 201