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