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/DependenceInfo.h" 35 #include "polly/LinkAllPasses.h" 36 #include "polly/Options.h" 37 #include "polly/ScopInfo.h" 38 #include "llvm/Support/CommandLine.h" 39 #include "isl/isl-noexceptions.h" 40 41 using namespace llvm; 42 using namespace polly; 43 44 namespace { 45 46 cl::opt<int> DCEPreciseSteps( 47 "polly-dce-precise-steps", 48 cl::desc("The number of precise steps between two approximating " 49 "iterations. (A value of -1 schedules another approximation stage " 50 "before the actual dead code elimination."), 51 cl::ZeroOrMore, cl::init(-1), cl::cat(PollyCategory)); 52 53 class DeadCodeElim : public ScopPass { 54 public: 55 static char ID; 56 explicit DeadCodeElim() : ScopPass(ID) {} 57 58 /// Remove dead iterations from the schedule of @p S. 59 bool runOnScop(Scop &S) override; 60 61 /// Register all analyses and transformation required. 62 void getAnalysisUsage(AnalysisUsage &AU) const override; 63 64 private: 65 /// Return the set of live iterations. 66 /// 67 /// The set of live iterations are all iterations that write to memory and for 68 /// which we can not prove that there will be a later write that _must_ 69 /// overwrite the same memory location and is consequently the only one that 70 /// is visible after the execution of the SCoP. 71 /// 72 isl::union_set getLiveOut(Scop &S); 73 bool eliminateDeadCode(Scop &S, int PreciseSteps); 74 }; 75 } // namespace 76 77 char DeadCodeElim::ID = 0; 78 79 // To compute the live outs, we compute for the data-locations that are 80 // must-written to the last statement that touches these locations. On top of 81 // this we add all statements that perform may-write accesses. 82 // 83 // We could be more precise by removing may-write accesses for which we know 84 // that they are overwritten by a must-write after. However, at the moment the 85 // only may-writes we introduce access the full (unbounded) array, such that 86 // bounded write accesses can not overwrite all of the data-locations. As 87 // this means may-writes are in the current situation always live, there is 88 // no point in trying to remove them from the live-out set. 89 isl::union_set DeadCodeElim::getLiveOut(Scop &S) { 90 isl::union_map Schedule = S.getSchedule(); 91 isl::union_map MustWrites = S.getMustWrites(); 92 isl::union_map WriteIterations = MustWrites.reverse(); 93 isl::union_map WriteTimes = WriteIterations.apply_range(Schedule); 94 95 isl::union_map LastWriteTimes = WriteTimes.lexmax(); 96 isl::union_map LastWriteIterations = 97 LastWriteTimes.apply_range(Schedule.reverse()); 98 99 isl::union_set Live = LastWriteIterations.range(); 100 isl::union_map MayWrites = S.getMayWrites(); 101 Live = Live.unite(MayWrites.domain()); 102 return Live.coalesce(); 103 } 104 105 /// Performs polyhedral dead iteration elimination by: 106 /// o Assuming that the last write to each location is live. 107 /// o Following each RAW dependency from a live iteration backwards and adding 108 /// that iteration to the live set. 109 /// 110 /// To ensure the set of live iterations does not get too complex we always 111 /// combine a certain number of precise steps with one approximating step that 112 /// simplifies the life set with an affine hull. 113 bool DeadCodeElim::eliminateDeadCode(Scop &S, int PreciseSteps) { 114 DependenceInfo &DI = getAnalysis<DependenceInfo>(); 115 const Dependences &D = DI.getDependences(Dependences::AL_Statement); 116 117 if (!D.hasValidDependences()) 118 return false; 119 120 isl::union_set Live = getLiveOut(S); 121 isl::union_map Dep = 122 D.getDependences(Dependences::TYPE_RAW | Dependences::TYPE_RED); 123 Dep = Dep.reverse(); 124 125 if (PreciseSteps == -1) 126 Live = Live.affine_hull(); 127 128 isl::union_set OriginalDomain = S.getDomains(); 129 int Steps = 0; 130 while (true) { 131 Steps++; 132 133 isl::union_set Extra = Live.apply(Dep); 134 135 if (Extra.is_subset(Live)) 136 break; 137 138 Live = Live.unite(Extra); 139 140 if (Steps > PreciseSteps) { 141 Steps = 0; 142 Live = Live.affine_hull(); 143 } 144 145 Live = Live.intersect(OriginalDomain); 146 } 147 148 Live = Live.coalesce(); 149 150 bool Changed = S.restrictDomains(Live); 151 152 // FIXME: We can probably avoid the recomputation of all dependences by 153 // updating them explicitly. 154 if (Changed) 155 DI.recomputeDependences(Dependences::AL_Statement); 156 return Changed; 157 } 158 159 bool DeadCodeElim::runOnScop(Scop &S) { 160 return eliminateDeadCode(S, DCEPreciseSteps); 161 } 162 163 void DeadCodeElim::getAnalysisUsage(AnalysisUsage &AU) const { 164 ScopPass::getAnalysisUsage(AU); 165 AU.addRequired<DependenceInfo>(); 166 } 167 168 Pass *polly::createDeadCodeElimPass() { return new DeadCodeElim(); } 169 170 INITIALIZE_PASS_BEGIN(DeadCodeElim, "polly-dce", 171 "Polly - Remove dead iterations", false, false) 172 INITIALIZE_PASS_DEPENDENCY(DependenceInfo) 173 INITIALIZE_PASS_DEPENDENCY(ScopInfoRegionPass) 174 INITIALIZE_PASS_END(DeadCodeElim, "polly-dce", "Polly - Remove dead iterations", 175 false, false) 176