146 lines · 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-exception6//7//===----------------------------------------------------------------------===//8//9// The polyhedral dead code elimination pass analyses a SCoP to eliminate10// statement instances that can be proven dead.11// As a consequence, the code generated for this SCoP may execute a statement12// less often. This means, a statement may be executed only in certain loop13// 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 in30// the 'ppcg' tool.31//32//===----------------------------------------------------------------------===//33 34#include "polly/DeadCodeElimination.h"35#include "polly/DependenceInfo.h"36#include "polly/Options.h"37#include "polly/ScopInfo.h"38#include "llvm/Support/CommandLine.h"39#include "isl/isl-noexceptions.h"40 41using namespace llvm;42using namespace polly;43 44namespace {45 46cl::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::init(-1), cl::cat(PollyCategory));52 53/// Return the set of live iterations.54///55/// The set of live iterations are all iterations that write to memory and for56/// which we can not prove that there will be a later write that _must_57/// overwrite the same memory location and is consequently the only one that58/// is visible after the execution of the SCoP.59///60/// To compute the live outs, we compute for the data-locations that are61/// must-written to the last statement that touches these locations. On top of62/// this we add all statements that perform may-write accesses.63///64/// We could be more precise by removing may-write accesses for which we know65/// that they are overwritten by a must-write after. However, at the moment the66/// only may-writes we introduce access the full (unbounded) array, such that67/// bounded write accesses can not overwrite all of the data-locations. As68/// this means may-writes are in the current situation always live, there is69/// no point in trying to remove them from the live-out set.70static isl::union_set getLiveOut(Scop &S) {71 isl::union_map Schedule = S.getSchedule();72 isl::union_map MustWrites = S.getMustWrites();73 isl::union_map WriteIterations = MustWrites.reverse();74 isl::union_map WriteTimes = WriteIterations.apply_range(Schedule);75 76 isl::union_map LastWriteTimes = WriteTimes.lexmax();77 isl::union_map LastWriteIterations =78 LastWriteTimes.apply_range(Schedule.reverse());79 80 isl::union_set Live = LastWriteIterations.range();81 isl::union_map MayWrites = S.getMayWrites();82 Live = Live.unite(MayWrites.domain());83 return Live.coalesce();84}85 86/// Performs polyhedral dead iteration elimination by:87/// o Assuming that the last write to each location is live.88/// o Following each RAW dependency from a live iteration backwards and adding89/// that iteration to the live set.90///91/// To ensure the set of live iterations does not get too complex we always92/// combine a certain number of precise steps with one approximating step that93/// simplifies the life set with an affine hull.94static bool runDeadCodeElimination(Scop &S, int PreciseSteps,95 const Dependences &D) {96 if (!D.hasValidDependences())97 return false;98 99 isl::union_set Live = getLiveOut(S);100 isl::union_map Dep =101 D.getDependences(Dependences::TYPE_RAW | Dependences::TYPE_RED);102 Dep = Dep.reverse();103 104 if (PreciseSteps == -1)105 Live = Live.affine_hull();106 107 isl::union_set OriginalDomain = S.getDomains();108 int Steps = 0;109 while (true) {110 Steps++;111 112 isl::union_set Extra = Live.apply(Dep);113 114 if (Extra.is_subset(Live))115 break;116 117 Live = Live.unite(Extra);118 119 if (Steps > PreciseSteps) {120 Steps = 0;121 Live = Live.affine_hull();122 }123 124 Live = Live.intersect(OriginalDomain);125 }126 127 Live = Live.coalesce();128 129 return S.restrictDomains(Live);130}131 132} // namespace133 134bool polly::runDeadCodeElim(Scop &S, DependenceAnalysis::Result &DA) {135 const Dependences &Deps = DA.getDependences(Dependences::AL_Statement);136 137 bool Changed = runDeadCodeElimination(S, DCEPreciseSteps, Deps);138 139 // FIXME: We can probably avoid the recomputation of all dependences by140 // updating them explicitly.141 if (Changed)142 DA.recomputeDependences(Dependences::AL_Statement);143 144 return Changed;145}146