Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 1 | //===----- ScopDetection.cpp - Detect Scops --------------------*- C++ -*-===// |
| 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
| 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
| 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
| 10 | // Detect the maximal Scops of a function. |
| 11 | // |
| 12 | // A static control part (Scop) is a subgraph of the control flow graph (CFG) |
| 13 | // that only has statically known control flow and can therefore be described |
| 14 | // within the polyhedral model. |
| 15 | // |
| 16 | // Every Scop fullfills these restrictions: |
| 17 | // |
| 18 | // * It is a single entry single exit region |
| 19 | // |
| 20 | // * Only affine linear bounds in the loops |
| 21 | // |
| 22 | // Every natural loop in a Scop must have a number of loop iterations that can |
| 23 | // be described as an affine linear function in surrounding loop iterators or |
| 24 | // parameters. (A parameter is a scalar that does not change its value during |
| 25 | // execution of the Scop). |
| 26 | // |
| 27 | // * Only comparisons of affine linear expressions in conditions |
| 28 | // |
| 29 | // * All loops and conditions perfectly nested |
| 30 | // |
| 31 | // The control flow needs to be structured such that it could be written using |
| 32 | // just 'for' and 'if' statements, without the need for any 'goto', 'break' or |
| 33 | // 'continue'. |
| 34 | // |
| 35 | // * Side effect free functions call |
| 36 | // |
| 37 | // Only function calls and intrinsics that do not have side effects are allowed |
| 38 | // (readnone). |
| 39 | // |
| 40 | // The Scop detection finds the largest Scops by checking if the largest |
| 41 | // region is a Scop. If this is not the case, its canonical subregions are |
| 42 | // checked until a region is a Scop. It is now tried to extend this Scop by |
| 43 | // creating a larger non canonical region. |
| 44 | // |
| 45 | //===----------------------------------------------------------------------===// |
| 46 | |
Tobias Grosser | ecfe21b | 2013-03-20 18:03:18 +0000 | [diff] [blame] | 47 | #include "polly/CodeGen/BlockGenerators.h" |
Tobias Grosser | ba0d092 | 2015-05-09 09:13:42 +0000 | [diff] [blame] | 48 | #include "polly/CodeGen/CodeGeneration.h" |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 49 | #include "polly/LinkAllPasses.h" |
Tobias Grosser | 637bd63 | 2013-05-07 07:31:10 +0000 | [diff] [blame] | 50 | #include "polly/Options.h" |
Tobias Grosser | ecfe21b | 2013-03-20 18:03:18 +0000 | [diff] [blame] | 51 | #include "polly/ScopDetection.h" |
Tobias Grosser | ba0d092 | 2015-05-09 09:13:42 +0000 | [diff] [blame] | 52 | #include "polly/ScopDetectionDiagnostic.h" |
Tobias Grosser | 120db6b | 2011-11-07 12:58:54 +0000 | [diff] [blame] | 53 | #include "polly/Support/SCEVValidator.h" |
Tobias Grosser | 8362818 | 2013-05-07 08:11:54 +0000 | [diff] [blame] | 54 | #include "polly/Support/ScopHelper.h" |
Tobias Grosser | a63b7ce | 2015-05-03 05:21:36 +0000 | [diff] [blame] | 55 | #include "polly/Support/ScopLocation.h" |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 56 | #include "llvm/ADT/Statistic.h" |
| 57 | #include "llvm/Analysis/AliasAnalysis.h" |
Tobias Grosser | 6e9f25a | 2011-11-09 22:35:00 +0000 | [diff] [blame] | 58 | #include "llvm/Analysis/LoopInfo.h" |
Matt Arsenault | 8ca3681 | 2014-07-19 18:40:17 +0000 | [diff] [blame] | 59 | #include "llvm/Analysis/PostDominators.h" |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 60 | #include "llvm/Analysis/RegionIterator.h" |
Tobias Grosser | 6e9f25a | 2011-11-09 22:35:00 +0000 | [diff] [blame] | 61 | #include "llvm/Analysis/ScalarEvolution.h" |
Tobias Grosser | b8710b5 | 2011-11-10 12:44:50 +0000 | [diff] [blame] | 62 | #include "llvm/Analysis/ScalarEvolutionExpressions.h" |
Chandler Carruth | 6b96c24 | 2014-03-06 00:47:27 +0000 | [diff] [blame] | 63 | #include "llvm/IR/DebugInfo.h" |
Tobias Grosser | 8519f89 | 2013-12-18 10:49:53 +0000 | [diff] [blame] | 64 | #include "llvm/IR/DiagnosticInfo.h" |
| 65 | #include "llvm/IR/DiagnosticPrinter.h" |
Tobias Grosser | ba0d092 | 2015-05-09 09:13:42 +0000 | [diff] [blame] | 66 | #include "llvm/IR/IntrinsicInst.h" |
Chandler Carruth | 6b96c24 | 2014-03-06 00:47:27 +0000 | [diff] [blame] | 67 | #include "llvm/IR/LLVMContext.h" |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 68 | #include "llvm/Support/Debug.h" |
Tobias Grosser | 60b54f1 | 2011-11-08 15:41:28 +0000 | [diff] [blame] | 69 | #include <set> |
| 70 | |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 71 | using namespace llvm; |
| 72 | using namespace polly; |
| 73 | |
Chandler Carruth | 95fef94 | 2014-04-22 03:30:19 +0000 | [diff] [blame] | 74 | #define DEBUG_TYPE "polly-detect" |
| 75 | |
Tobias Grosser | d1e33e7 | 2015-02-19 05:31:07 +0000 | [diff] [blame] | 76 | static cl::opt<bool> DetectUnprofitable("polly-detect-unprofitable", |
| 77 | cl::desc("Detect unprofitable scops"), |
| 78 | cl::Hidden, cl::init(false), |
| 79 | cl::ZeroOrMore, cl::cat(PollyCategory)); |
| 80 | |
Tobias Grosser | 483a90d | 2014-07-09 10:50:10 +0000 | [diff] [blame] | 81 | static cl::opt<std::string> OnlyFunction( |
| 82 | "polly-only-func", |
| 83 | cl::desc("Only run on functions that contain a certain string"), |
| 84 | cl::value_desc("string"), cl::ValueRequired, cl::init(""), |
| 85 | cl::cat(PollyCategory)); |
Tobias Grosser | 2ff8723 | 2011-10-23 11:17:06 +0000 | [diff] [blame] | 86 | |
Tobias Grosser | 483a90d | 2014-07-09 10:50:10 +0000 | [diff] [blame] | 87 | static cl::opt<std::string> OnlyRegion( |
| 88 | "polly-only-region", |
| 89 | cl::desc("Only run on certain regions (The provided identifier must " |
| 90 | "appear in the name of the region's entry block"), |
| 91 | cl::value_desc("identifier"), cl::ValueRequired, cl::init(""), |
| 92 | cl::cat(PollyCategory)); |
Tobias Grosser | 4449e52 | 2014-01-27 14:24:53 +0000 | [diff] [blame] | 93 | |
Tobias Grosser | 60cd932 | 2011-11-10 12:47:26 +0000 | [diff] [blame] | 94 | static cl::opt<bool> |
Tobias Grosser | 483a90d | 2014-07-09 10:50:10 +0000 | [diff] [blame] | 95 | IgnoreAliasing("polly-ignore-aliasing", |
| 96 | cl::desc("Ignore possible aliasing of the array bases"), |
| 97 | cl::Hidden, cl::init(false), cl::ZeroOrMore, |
| 98 | cl::cat(PollyCategory)); |
Tobias Grosser | 2ff8723 | 2011-10-23 11:17:06 +0000 | [diff] [blame] | 99 | |
Johannes Doerfert | b164c79 | 2014-09-18 11:17:17 +0000 | [diff] [blame] | 100 | bool polly::PollyUseRuntimeAliasChecks; |
| 101 | static cl::opt<bool, true> XPollyUseRuntimeAliasChecks( |
| 102 | "polly-use-runtime-alias-checks", |
| 103 | cl::desc("Use runtime alias checks to resolve possible aliasing."), |
| 104 | cl::location(PollyUseRuntimeAliasChecks), cl::Hidden, cl::ZeroOrMore, |
| 105 | cl::init(true), cl::cat(PollyCategory)); |
| 106 | |
Tobias Grosser | 637bd63 | 2013-05-07 07:31:10 +0000 | [diff] [blame] | 107 | static cl::opt<bool> |
Tobias Grosser | 483a90d | 2014-07-09 10:50:10 +0000 | [diff] [blame] | 108 | ReportLevel("polly-report", |
| 109 | cl::desc("Print information about the activities of Polly"), |
| 110 | cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory)); |
Tobias Grosser | 531891e | 2012-11-01 16:45:20 +0000 | [diff] [blame] | 111 | |
| 112 | static cl::opt<bool> |
Tobias Grosser | 483a90d | 2014-07-09 10:50:10 +0000 | [diff] [blame] | 113 | AllowNonAffine("polly-allow-nonaffine", |
| 114 | cl::desc("Allow non affine access functions in arrays"), |
| 115 | cl::Hidden, cl::init(false), cl::ZeroOrMore, |
| 116 | cl::cat(PollyCategory)); |
Tobias Grosser | a187964 | 2011-12-20 10:43:14 +0000 | [diff] [blame] | 117 | |
Johannes Doerfert | ba65c16 | 2015-02-24 11:45:21 +0000 | [diff] [blame] | 118 | static cl::opt<bool> AllowNonAffineSubRegions( |
| 119 | "polly-allow-nonaffine-branches", |
| 120 | cl::desc("Allow non affine conditions for branches"), cl::Hidden, |
Johannes Doerfert | a36842f | 2015-02-26 11:09:24 +0000 | [diff] [blame] | 121 | cl::init(true), cl::ZeroOrMore, cl::cat(PollyCategory)); |
Johannes Doerfert | ba65c16 | 2015-02-24 11:45:21 +0000 | [diff] [blame] | 122 | |
Johannes Doerfert | f3e98f4 | 2015-04-12 22:52:20 +0000 | [diff] [blame] | 123 | static cl::opt<bool> |
| 124 | AllowNonAffineSubLoops("polly-allow-nonaffine-loops", |
| 125 | cl::desc("Allow non affine conditions for loops"), |
| 126 | cl::Hidden, cl::init(false), cl::ZeroOrMore, |
| 127 | cl::cat(PollyCategory)); |
| 128 | |
Tobias Grosser | bfbc369 | 2015-01-09 00:01:33 +0000 | [diff] [blame] | 129 | static cl::opt<bool> AllowUnsigned("polly-allow-unsigned", |
| 130 | cl::desc("Allow unsigned expressions"), |
| 131 | cl::Hidden, cl::init(false), cl::ZeroOrMore, |
| 132 | cl::cat(PollyCategory)); |
| 133 | |
Tobias Grosser | c7d3fc5 | 2013-07-25 03:02:29 +0000 | [diff] [blame] | 134 | static cl::opt<bool, true> |
Tobias Grosser | 483a90d | 2014-07-09 10:50:10 +0000 | [diff] [blame] | 135 | TrackFailures("polly-detect-track-failures", |
| 136 | cl::desc("Track failure strings in detecting scop regions"), |
| 137 | cl::location(PollyTrackFailures), cl::Hidden, cl::ZeroOrMore, |
Andreas Simbuerger | 3efe40b | 2014-08-17 10:09:03 +0000 | [diff] [blame] | 138 | cl::init(true), cl::cat(PollyCategory)); |
Tobias Grosser | c7d3fc5 | 2013-07-25 03:02:29 +0000 | [diff] [blame] | 139 | |
Andreas Simbuerger | 0447240 | 2014-05-24 09:25:10 +0000 | [diff] [blame] | 140 | static cl::opt<bool> KeepGoing("polly-detect-keep-going", |
| 141 | cl::desc("Do not fail on the first error."), |
| 142 | cl::Hidden, cl::ZeroOrMore, cl::init(false), |
| 143 | cl::cat(PollyCategory)); |
| 144 | |
Sebastian Pop | 1801668 | 2014-04-08 21:20:44 +0000 | [diff] [blame] | 145 | static cl::opt<bool, true> |
Tobias Grosser | 483a90d | 2014-07-09 10:50:10 +0000 | [diff] [blame] | 146 | PollyDelinearizeX("polly-delinearize", |
| 147 | cl::desc("Delinearize array access functions"), |
| 148 | cl::location(PollyDelinearize), cl::Hidden, |
Tobias Grosser | 6973cb6 | 2015-03-08 15:21:18 +0000 | [diff] [blame] | 149 | cl::ZeroOrMore, cl::init(true), cl::cat(PollyCategory)); |
Sebastian Pop | 1801668 | 2014-04-08 21:20:44 +0000 | [diff] [blame] | 150 | |
Tobias Grosser | a168993 | 2014-02-18 18:49:49 +0000 | [diff] [blame] | 151 | static cl::opt<bool> |
Tobias Grosser | 483a90d | 2014-07-09 10:50:10 +0000 | [diff] [blame] | 152 | VerifyScops("polly-detect-verify", |
| 153 | cl::desc("Verify the detected SCoPs after each transformation"), |
| 154 | cl::Hidden, cl::init(false), cl::ZeroOrMore, |
| 155 | cl::cat(PollyCategory)); |
Tobias Grosser | a168993 | 2014-02-18 18:49:49 +0000 | [diff] [blame] | 156 | |
Johannes Doerfert | d020b77 | 2015-08-27 06:53:52 +0000 | [diff] [blame] | 157 | static cl::opt<bool> AllowNonSCEVBackedgeTakenCount( |
| 158 | "polly-allow-non-scev-backedge-taken-count", |
| 159 | cl::desc("Allow loops even if SCEV cannot provide a trip count"), |
| 160 | cl::Hidden, cl::init(true), cl::ZeroOrMore, cl::cat(PollyCategory)); |
| 161 | |
Tobias Grosser | c7d3fc5 | 2013-07-25 03:02:29 +0000 | [diff] [blame] | 162 | bool polly::PollyTrackFailures = false; |
Sebastian Pop | 1801668 | 2014-04-08 21:20:44 +0000 | [diff] [blame] | 163 | bool polly::PollyDelinearize = false; |
Johannes Doerfert | 43e1ead | 2014-07-15 21:06:48 +0000 | [diff] [blame] | 164 | StringRef polly::PollySkipFnAttr = "polly.skip.fn"; |
Tobias Grosser | c7d3fc5 | 2013-07-25 03:02:29 +0000 | [diff] [blame] | 165 | |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 166 | //===----------------------------------------------------------------------===// |
| 167 | // Statistics. |
| 168 | |
| 169 | STATISTIC(ValidRegion, "Number of regions that a valid part of Scop"); |
| 170 | |
Tobias Grosser | 8519f89 | 2013-12-18 10:49:53 +0000 | [diff] [blame] | 171 | class DiagnosticScopFound : public DiagnosticInfo { |
| 172 | private: |
| 173 | static int PluginDiagnosticKind; |
| 174 | |
| 175 | Function &F; |
| 176 | std::string FileName; |
| 177 | unsigned EntryLine, ExitLine; |
| 178 | |
| 179 | public: |
Tobias Grosser | 1b12f46 | 2013-12-18 11:14:36 +0000 | [diff] [blame] | 180 | DiagnosticScopFound(Function &F, std::string FileName, unsigned EntryLine, |
| 181 | unsigned ExitLine) |
Tobias Grosser | 8519f89 | 2013-12-18 10:49:53 +0000 | [diff] [blame] | 182 | : DiagnosticInfo(PluginDiagnosticKind, DS_Note), F(F), FileName(FileName), |
Tobias Grosser | 1b12f46 | 2013-12-18 11:14:36 +0000 | [diff] [blame] | 183 | EntryLine(EntryLine), ExitLine(ExitLine) {} |
Tobias Grosser | 8519f89 | 2013-12-18 10:49:53 +0000 | [diff] [blame] | 184 | |
| 185 | virtual void print(DiagnosticPrinter &DP) const; |
| 186 | |
| 187 | static bool classof(const DiagnosticInfo *DI) { |
| 188 | return DI->getKind() == PluginDiagnosticKind; |
| 189 | } |
| 190 | }; |
| 191 | |
| 192 | int DiagnosticScopFound::PluginDiagnosticKind = 10; |
| 193 | |
Tobias Grosser | 8519f89 | 2013-12-18 10:49:53 +0000 | [diff] [blame] | 194 | void DiagnosticScopFound::print(DiagnosticPrinter &DP) const { |
Tobias Grosser | 1b12f46 | 2013-12-18 11:14:36 +0000 | [diff] [blame] | 195 | DP << "Polly detected an optimizable loop region (scop) in function '" << F |
| 196 | << "'\n"; |
Tobias Grosser | 8519f89 | 2013-12-18 10:49:53 +0000 | [diff] [blame] | 197 | |
| 198 | if (FileName.empty()) { |
| 199 | DP << "Scop location is unknown. Compile with debug info " |
| 200 | "(-g) to get more precise information. "; |
Tobias Grosser | 1b12f46 | 2013-12-18 11:14:36 +0000 | [diff] [blame] | 201 | return; |
Tobias Grosser | 8519f89 | 2013-12-18 10:49:53 +0000 | [diff] [blame] | 202 | } |
| 203 | |
| 204 | DP << FileName << ":" << EntryLine << ": Start of scop\n"; |
| 205 | DP << FileName << ":" << ExitLine << ": End of scop"; |
| 206 | } |
| 207 | |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 208 | //===----------------------------------------------------------------------===// |
| 209 | // ScopDetection. |
Andreas Simbuerger | 01a37a0 | 2014-04-02 11:54:01 +0000 | [diff] [blame] | 210 | |
Johannes Doerfert | b164c79 | 2014-09-18 11:17:17 +0000 | [diff] [blame] | 211 | ScopDetection::ScopDetection() : FunctionPass(ID) { |
| 212 | if (!PollyUseRuntimeAliasChecks) |
| 213 | return; |
| 214 | |
Johannes Doerfert | 928229f | 2014-09-29 17:06:29 +0000 | [diff] [blame] | 215 | // Disable runtime alias checks if we ignore aliasing all together. |
| 216 | if (IgnoreAliasing) { |
| 217 | PollyUseRuntimeAliasChecks = false; |
| 218 | return; |
| 219 | } |
| 220 | |
Johannes Doerfert | b164c79 | 2014-09-18 11:17:17 +0000 | [diff] [blame] | 221 | if (AllowNonAffine) { |
| 222 | DEBUG(errs() << "WARNING: We disable runtime alias checks as non affine " |
| 223 | "accesses are enabled.\n"); |
| 224 | PollyUseRuntimeAliasChecks = false; |
| 225 | } |
Johannes Doerfert | b164c79 | 2014-09-18 11:17:17 +0000 | [diff] [blame] | 226 | } |
| 227 | |
Andreas Simbuerger | 01a37a0 | 2014-04-02 11:54:01 +0000 | [diff] [blame] | 228 | template <class RR, typename... Args> |
| 229 | inline bool ScopDetection::invalid(DetectionContext &Context, bool Assert, |
| 230 | Args &&... Arguments) const { |
| 231 | |
| 232 | if (!Context.Verifying) { |
Andreas Simbuerger | 4870e09 | 2014-05-24 09:25:01 +0000 | [diff] [blame] | 233 | RejectLog &Log = Context.Log; |
| 234 | std::shared_ptr<RR> RejectReason = std::make_shared<RR>(Arguments...); |
Andreas Simbuerger | 01a37a0 | 2014-04-02 11:54:01 +0000 | [diff] [blame] | 235 | |
Andreas Simbuerger | 8a00c9b | 2014-05-24 09:25:06 +0000 | [diff] [blame] | 236 | if (PollyTrackFailures) |
Andreas Simbuerger | 4870e09 | 2014-05-24 09:25:01 +0000 | [diff] [blame] | 237 | Log.report(RejectReason); |
Andreas Simbuerger | 4870e09 | 2014-05-24 09:25:01 +0000 | [diff] [blame] | 238 | |
| 239 | DEBUG(dbgs() << RejectReason->getMessage()); |
Andreas Simbuerger | 01a37a0 | 2014-04-02 11:54:01 +0000 | [diff] [blame] | 240 | DEBUG(dbgs() << "\n"); |
| 241 | } else { |
| 242 | assert(!Assert && "Verification of detected scop failed"); |
| 243 | } |
| 244 | |
| 245 | return false; |
| 246 | } |
| 247 | |
Tobias Grosser | a168993 | 2014-02-18 18:49:49 +0000 | [diff] [blame] | 248 | bool ScopDetection::isMaxRegionInScop(const Region &R, bool Verify) const { |
| 249 | if (!ValidRegions.count(&R)) |
| 250 | return false; |
| 251 | |
Johannes Doerfert | 3f1c285 | 2015-02-19 18:11:50 +0000 | [diff] [blame] | 252 | if (Verify) { |
Johannes Doerfert | f3e98f4 | 2015-04-12 22:52:20 +0000 | [diff] [blame] | 253 | BoxedLoopsSetTy DummyBoxedLoopsSet; |
Johannes Doerfert | ba65c16 | 2015-02-24 11:45:21 +0000 | [diff] [blame] | 254 | NonAffineSubRegionSetTy DummyNonAffineSubRegionSet; |
| 255 | DetectionContext Context(const_cast<Region &>(R), *AA, |
Johannes Doerfert | f3e98f4 | 2015-04-12 22:52:20 +0000 | [diff] [blame] | 256 | DummyNonAffineSubRegionSet, DummyBoxedLoopsSet, |
| 257 | false /*verifying*/); |
Johannes Doerfert | 3f1c285 | 2015-02-19 18:11:50 +0000 | [diff] [blame] | 258 | return isValidRegion(Context); |
| 259 | } |
Tobias Grosser | a168993 | 2014-02-18 18:49:49 +0000 | [diff] [blame] | 260 | |
| 261 | return true; |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 262 | } |
| 263 | |
Tobias Grosser | 4f129a6 | 2011-10-08 00:30:55 +0000 | [diff] [blame] | 264 | std::string ScopDetection::regionIsInvalidBecause(const Region *R) const { |
Andreas Simbuerger | 8a00c9b | 2014-05-24 09:25:06 +0000 | [diff] [blame] | 265 | if (!RejectLogs.count(R)) |
Tobias Grosser | 4f129a6 | 2011-10-08 00:30:55 +0000 | [diff] [blame] | 266 | return ""; |
| 267 | |
Andreas Simbuerger | 8a00c9b | 2014-05-24 09:25:06 +0000 | [diff] [blame] | 268 | // Get the first error we found. Even in keep-going mode, this is the first |
| 269 | // reason that caused the candidate to be rejected. |
| 270 | RejectLog Errors = RejectLogs.at(R); |
Andreas Simbuerger | 83ed861 | 2014-06-12 07:25:08 +0000 | [diff] [blame] | 271 | |
| 272 | // This can happen when we marked a region invalid, but didn't track |
| 273 | // an error for it. |
| 274 | if (Errors.size() == 0) |
| 275 | return ""; |
| 276 | |
| 277 | RejectReasonPtr RR = *Errors.begin(); |
| 278 | return RR->getMessage(); |
Tobias Grosser | 4f129a6 | 2011-10-08 00:30:55 +0000 | [diff] [blame] | 279 | } |
| 280 | |
Johannes Doerfert | f3e98f4 | 2015-04-12 22:52:20 +0000 | [diff] [blame] | 281 | bool ScopDetection::addOverApproximatedRegion(Region *AR, |
| 282 | DetectionContext &Context) const { |
| 283 | |
| 284 | // If we already know about Ar we can exit. |
| 285 | if (!Context.NonAffineSubRegionSet.insert(AR)) |
| 286 | return true; |
| 287 | |
| 288 | // All loops in the region have to be overapproximated too if there |
| 289 | // are accesses that depend on the iteration count. |
| 290 | for (BasicBlock *BB : AR->blocks()) { |
Johannes Doerfert | ba65c16 | 2015-02-24 11:45:21 +0000 | [diff] [blame] | 291 | Loop *L = LI->getLoopFor(BB); |
Johannes Doerfert | f3e98f4 | 2015-04-12 22:52:20 +0000 | [diff] [blame] | 292 | if (AR->contains(L)) |
| 293 | Context.BoxedLoopsSet.insert(L); |
Johannes Doerfert | ba65c16 | 2015-02-24 11:45:21 +0000 | [diff] [blame] | 294 | } |
Johannes Doerfert | f3e98f4 | 2015-04-12 22:52:20 +0000 | [diff] [blame] | 295 | |
| 296 | return (AllowNonAffineSubLoops || Context.BoxedLoopsSet.empty()); |
Johannes Doerfert | ba65c16 | 2015-02-24 11:45:21 +0000 | [diff] [blame] | 297 | } |
| 298 | |
Tobias Grosser | e602a07 | 2013-05-07 07:30:56 +0000 | [diff] [blame] | 299 | bool ScopDetection::isValidCFG(BasicBlock &BB, |
| 300 | DetectionContext &Context) const { |
Johannes Doerfert | fb79a96 | 2015-02-23 14:18:28 +0000 | [diff] [blame] | 301 | Region &CurRegion = Context.CurRegion; |
| 302 | |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 303 | TerminatorInst *TI = BB.getTerminator(); |
| 304 | |
| 305 | // Return instructions are only valid if the region is the top level region. |
Johannes Doerfert | fb79a96 | 2015-02-23 14:18:28 +0000 | [diff] [blame] | 306 | if (isa<ReturnInst>(TI) && !CurRegion.getExit() && TI->getNumOperands() == 0) |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 307 | return true; |
| 308 | |
| 309 | BranchInst *Br = dyn_cast<BranchInst>(TI); |
| 310 | |
Andreas Simbuerger | 01a37a0 | 2014-04-02 11:54:01 +0000 | [diff] [blame] | 311 | if (!Br) |
| 312 | return invalid<ReportNonBranchTerminator>(Context, /*Assert=*/true, &BB); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 313 | |
Tobias Grosser | 74394f0 | 2013-01-14 22:40:23 +0000 | [diff] [blame] | 314 | if (Br->isUnconditional()) |
| 315 | return true; |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 316 | |
| 317 | Value *Condition = Br->getCondition(); |
| 318 | |
| 319 | // UndefValue is not allowed as condition. |
Andreas Simbuerger | 01a37a0 | 2014-04-02 11:54:01 +0000 | [diff] [blame] | 320 | if (isa<UndefValue>(Condition)) |
Andreas Simbuerger | 5569bf3 | 2014-06-26 10:06:40 +0000 | [diff] [blame] | 321 | return invalid<ReportUndefCond>(Context, /*Assert=*/true, Br, &BB); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 322 | |
| 323 | // Only Constant and ICmpInst are allowed as condition. |
Johannes Doerfert | ba65c16 | 2015-02-24 11:45:21 +0000 | [diff] [blame] | 324 | if (!(isa<Constant>(Condition) || isa<ICmpInst>(Condition))) { |
Johannes Doerfert | f3e98f4 | 2015-04-12 22:52:20 +0000 | [diff] [blame] | 325 | if (!AllowNonAffineSubRegions || |
| 326 | !addOverApproximatedRegion(RI->getRegionFor(&BB), Context)) |
Johannes Doerfert | ba65c16 | 2015-02-24 11:45:21 +0000 | [diff] [blame] | 327 | return invalid<ReportInvalidCond>(Context, /*Assert=*/true, Br, &BB); |
| 328 | } |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 329 | |
| 330 | // Allow perfectly nested conditions. |
| 331 | assert(Br->getNumSuccessors() == 2 && "Unexpected number of successors"); |
| 332 | |
| 333 | if (ICmpInst *ICmp = dyn_cast<ICmpInst>(Condition)) { |
| 334 | // Unsigned comparisons are not allowed. They trigger overflow problems |
| 335 | // in the code generation. |
| 336 | // |
| 337 | // TODO: This is not sufficient and just hides bugs. However it does pretty |
| 338 | // well. |
Tobias Grosser | bfbc369 | 2015-01-09 00:01:33 +0000 | [diff] [blame] | 339 | if (ICmp->isUnsigned() && !AllowUnsigned) |
Tobias Grosser | a8512b1 | 2015-05-20 15:37:11 +0000 | [diff] [blame] | 340 | return invalid<ReportUnsignedCond>(Context, /*Assert=*/true, Br, &BB); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 341 | |
| 342 | // Are both operands of the ICmp affine? |
Tobias Grosser | 74394f0 | 2013-01-14 22:40:23 +0000 | [diff] [blame] | 343 | if (isa<UndefValue>(ICmp->getOperand(0)) || |
Andreas Simbuerger | 01a37a0 | 2014-04-02 11:54:01 +0000 | [diff] [blame] | 344 | isa<UndefValue>(ICmp->getOperand(1))) |
Andreas Simbuerger | 5569bf3 | 2014-06-26 10:06:40 +0000 | [diff] [blame] | 345 | return invalid<ReportUndefOperand>(Context, /*Assert=*/true, &BB, ICmp); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 346 | |
Johannes Doerfert | 7ca8dc2 | 2015-09-09 14:19:04 +0000 | [diff] [blame] | 347 | // TODO: FIXME: IslExprBuilder is not capable of producing valid code |
| 348 | // for arbitrary pointer expressions at the moment. Until |
| 349 | // this is fixed we disallow pointer expressions completely. |
| 350 | if (ICmp->getOperand(0)->getType()->isPointerTy()) |
| 351 | return false; |
| 352 | |
Sebastian Pop | 9f57c5b | 2013-04-10 04:05:18 +0000 | [diff] [blame] | 353 | Loop *L = LI->getLoopFor(ICmp->getParent()); |
| 354 | const SCEV *LHS = SE->getSCEVAtScope(ICmp->getOperand(0), L); |
| 355 | const SCEV *RHS = SE->getSCEVAtScope(ICmp->getOperand(1), L); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 356 | |
Johannes Doerfert | fb79a96 | 2015-02-23 14:18:28 +0000 | [diff] [blame] | 357 | if (!isAffineExpr(&CurRegion, LHS, *SE) || |
Johannes Doerfert | ba65c16 | 2015-02-24 11:45:21 +0000 | [diff] [blame] | 358 | !isAffineExpr(&CurRegion, RHS, *SE)) { |
Johannes Doerfert | f3e98f4 | 2015-04-12 22:52:20 +0000 | [diff] [blame] | 359 | if (!AllowNonAffineSubRegions || |
| 360 | !addOverApproximatedRegion(RI->getRegionFor(&BB), Context)) |
Johannes Doerfert | ba65c16 | 2015-02-24 11:45:21 +0000 | [diff] [blame] | 361 | return invalid<ReportNonAffBranch>(Context, /*Assert=*/true, &BB, LHS, |
| 362 | RHS, ICmp); |
| 363 | } |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 364 | } |
| 365 | |
| 366 | // Allow loop exit conditions. |
| 367 | Loop *L = LI->getLoopFor(&BB); |
| 368 | if (L && L->getExitingBlock() == &BB) |
| 369 | return true; |
| 370 | |
| 371 | // Allow perfectly nested conditions. |
| 372 | Region *R = RI->getRegionFor(&BB); |
Andreas Simbuerger | 01a37a0 | 2014-04-02 11:54:01 +0000 | [diff] [blame] | 373 | if (R->getEntry() != &BB) |
| 374 | return invalid<ReportCondition>(Context, /*Assert=*/true, &BB); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 375 | |
| 376 | return true; |
| 377 | } |
| 378 | |
| 379 | bool ScopDetection::isValidCallInst(CallInst &CI) { |
Johannes Doerfert | 3f500fa | 2015-01-25 18:07:30 +0000 | [diff] [blame] | 380 | if (CI.doesNotReturn()) |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 381 | return false; |
| 382 | |
| 383 | if (CI.doesNotAccessMemory()) |
| 384 | return true; |
| 385 | |
| 386 | Function *CalledFunction = CI.getCalledFunction(); |
| 387 | |
| 388 | // Indirect calls are not supported. |
| 389 | if (CalledFunction == 0) |
| 390 | return false; |
| 391 | |
Tobias Grosser | 9c0ffe3 | 2015-08-30 16:57:15 +0000 | [diff] [blame] | 392 | if (isIgnoredIntrinsic(&CI)) |
| 393 | return true; |
Johannes Doerfert | 3f500fa | 2015-01-25 18:07:30 +0000 | [diff] [blame] | 394 | |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 395 | return false; |
| 396 | } |
| 397 | |
Tobias Grosser | 458fb78 | 2014-01-28 12:58:58 +0000 | [diff] [blame] | 398 | bool ScopDetection::isInvariant(const Value &Val, const Region &Reg) const { |
| 399 | // A reference to function argument or constant value is invariant. |
| 400 | if (isa<Argument>(Val) || isa<Constant>(Val)) |
| 401 | return true; |
| 402 | |
| 403 | const Instruction *I = dyn_cast<Instruction>(&Val); |
| 404 | if (!I) |
| 405 | return false; |
| 406 | |
| 407 | if (!Reg.contains(I)) |
| 408 | return true; |
| 409 | |
| 410 | if (I->mayHaveSideEffects()) |
| 411 | return false; |
| 412 | |
| 413 | // When Val is a Phi node, it is likely not invariant. We do not check whether |
| 414 | // Phi nodes are actually invariant, we assume that Phi nodes are usually not |
| 415 | // invariant. Recursively checking the operators of Phi nodes would lead to |
| 416 | // infinite recursion. |
| 417 | if (isa<PHINode>(*I)) |
| 418 | return false; |
| 419 | |
Tobias Grosser | 2610889 | 2014-04-02 20:18:19 +0000 | [diff] [blame] | 420 | for (const Use &Operand : I->operands()) |
Tobias Grosser | 1d19190 | 2014-03-03 13:13:55 +0000 | [diff] [blame] | 421 | if (!isInvariant(*Operand, Reg)) |
Tobias Grosser | 458fb78 | 2014-01-28 12:58:58 +0000 | [diff] [blame] | 422 | return false; |
Tobias Grosser | 458fb78 | 2014-01-28 12:58:58 +0000 | [diff] [blame] | 423 | |
| 424 | // When the instruction is a load instruction, check that no write to memory |
| 425 | // in the region aliases with the load. |
| 426 | if (const LoadInst *LI = dyn_cast<LoadInst>(I)) { |
Chandler Carruth | bdb4a39 | 2015-06-04 03:49:46 +0000 | [diff] [blame] | 427 | auto Loc = MemoryLocation::get(LI); |
Johannes Doerfert | ca08c44 | 2015-02-21 16:18:28 +0000 | [diff] [blame] | 428 | |
Tobias Grosser | 458fb78 | 2014-01-28 12:58:58 +0000 | [diff] [blame] | 429 | // Check if any basic block in the region can modify the location pointed to |
| 430 | // by 'Loc'. If so, 'Val' is (likely) not invariant in the region. |
Tobias Grosser | 2610889 | 2014-04-02 20:18:19 +0000 | [diff] [blame] | 431 | for (const BasicBlock *BB : Reg.blocks()) |
Tobias Grosser | 1d19190 | 2014-03-03 13:13:55 +0000 | [diff] [blame] | 432 | if (AA->canBasicBlockModify(*BB, Loc)) |
Tobias Grosser | 458fb78 | 2014-01-28 12:58:58 +0000 | [diff] [blame] | 433 | return false; |
Tobias Grosser | 458fb78 | 2014-01-28 12:58:58 +0000 | [diff] [blame] | 434 | } |
| 435 | |
| 436 | return true; |
| 437 | } |
| 438 | |
Sebastian Pop | 422e33f | 2014-06-03 18:16:31 +0000 | [diff] [blame] | 439 | MapInsnToMemAcc InsnToMemAcc; |
| 440 | |
Sebastian Pop | b57c099 | 2014-05-12 20:24:26 +0000 | [diff] [blame] | 441 | bool ScopDetection::hasAffineMemoryAccesses(DetectionContext &Context) const { |
Johannes Doerfert | fb79a96 | 2015-02-23 14:18:28 +0000 | [diff] [blame] | 442 | Region &CurRegion = Context.CurRegion; |
| 443 | |
Tobias Grosser | 230acc4 | 2014-09-13 14:47:55 +0000 | [diff] [blame] | 444 | for (const SCEVUnknown *BasePointer : Context.NonAffineAccesses) { |
Sebastian Pop | 46e1ecd | 2014-05-09 22:45:15 +0000 | [diff] [blame] | 445 | Value *BaseValue = BasePointer->getValue(); |
Tobias Grosser | a5c092d | 2015-06-04 16:03:16 +0000 | [diff] [blame] | 446 | auto Shape = std::shared_ptr<ArrayShape>(new ArrayShape(BasePointer)); |
Tobias Grosser | 230acc4 | 2014-09-13 14:47:55 +0000 | [diff] [blame] | 447 | bool BasePtrHasNonAffine = false; |
Sebastian Pop | 46e1ecd | 2014-05-09 22:45:15 +0000 | [diff] [blame] | 448 | |
| 449 | // First step: collect parametric terms in all array references. |
| 450 | SmallVector<const SCEV *, 4> Terms; |
Tobias Grosser | 230acc4 | 2014-09-13 14:47:55 +0000 | [diff] [blame] | 451 | for (const auto &Pair : Context.Accesses[BasePointer]) { |
Tobias Grosser | 1b13dde | 2015-06-29 14:44:22 +0000 | [diff] [blame] | 452 | if (auto *AF = dyn_cast<SCEVAddRecExpr>(Pair.second)) |
Tobias Grosser | 23bceb2 | 2015-06-29 14:44:17 +0000 | [diff] [blame] | 453 | SE->collectParametricTerms(AF, Terms); |
Tobias Grosser | 1b13dde | 2015-06-29 14:44:22 +0000 | [diff] [blame] | 454 | |
| 455 | // In case the outermost expression is a plain add, we check if any of its |
| 456 | // terms has the form 4 * %inst * %param * %param ..., aka a term that |
| 457 | // contains a product between a parameter and an instruction that is |
| 458 | // inside the scop. Such instructions, if allowed at all, are instructions |
| 459 | // SCEV can not represent, but Polly is still looking through. As a |
| 460 | // result, these instructions can depend on induction variables and are |
| 461 | // most likely no array sizes. However, terms that are multiplied with |
| 462 | // them are likely candidates for array sizes. |
| 463 | if (auto *AF = dyn_cast<SCEVAddExpr>(Pair.second)) { |
| 464 | for (auto Op : AF->operands()) { |
| 465 | if (auto *AF2 = dyn_cast<SCEVAddRecExpr>(Op)) |
| 466 | SE->collectParametricTerms(AF2, Terms); |
| 467 | if (auto *AF2 = dyn_cast<SCEVMulExpr>(Op)) { |
| 468 | SmallVector<const SCEV *, 0> Operands; |
Tobias Grosser | 1b13dde | 2015-06-29 14:44:22 +0000 | [diff] [blame] | 469 | |
| 470 | for (auto *MulOp : AF2->operands()) { |
| 471 | if (auto *Const = dyn_cast<SCEVConstant>(MulOp)) |
| 472 | Operands.push_back(Const); |
| 473 | if (auto *Unknown = dyn_cast<SCEVUnknown>(MulOp)) { |
| 474 | if (auto *Inst = dyn_cast<Instruction>(Unknown->getValue())) { |
| 475 | if (!Context.CurRegion.contains(Inst)) |
| 476 | Operands.push_back(MulOp); |
Tobias Grosser | 1b13dde | 2015-06-29 14:44:22 +0000 | [diff] [blame] | 477 | |
| 478 | } else { |
| 479 | Operands.push_back(MulOp); |
| 480 | } |
| 481 | } |
| 482 | } |
| 483 | Terms.push_back(SE->getMulExpr(Operands)); |
| 484 | } |
| 485 | } |
| 486 | } |
Tobias Grosser | 230acc4 | 2014-09-13 14:47:55 +0000 | [diff] [blame] | 487 | } |
Sebastian Pop | e8863b8 | 2014-05-12 19:02:02 +0000 | [diff] [blame] | 488 | |
Sebastian Pop | 46e1ecd | 2014-05-09 22:45:15 +0000 | [diff] [blame] | 489 | // Second step: find array shape. |
Sebastian Pop | 422e33f | 2014-06-03 18:16:31 +0000 | [diff] [blame] | 490 | SE->findArrayDimensions(Terms, Shape->DelinearizedSizes, |
| 491 | Context.ElementSize[BasePointer]); |
Sebastian Pop | 46e1ecd | 2014-05-09 22:45:15 +0000 | [diff] [blame] | 492 | |
Johannes Doerfert | 8983031 | 2015-05-03 16:03:01 +0000 | [diff] [blame] | 493 | if (!AllowNonAffine) |
Tobias Grosser | 80e237b | 2015-07-29 13:52:05 +0000 | [diff] [blame] | 494 | for (const SCEV *DelinearizedSize : Shape->DelinearizedSizes) { |
| 495 | if (auto *Unknown = dyn_cast<SCEVUnknown>(DelinearizedSize)) { |
| 496 | auto *value = dyn_cast<Value>(Unknown->getValue()); |
| 497 | if (isa<UndefValue>(value)) { |
| 498 | invalid<ReportDifferentArrayElementSize>( |
| 499 | Context, /*Assert=*/true, |
| 500 | Context.Accesses[BasePointer].front().first, BaseValue); |
| 501 | return false; |
| 502 | } |
| 503 | } |
Johannes Doerfert | 8983031 | 2015-05-03 16:03:01 +0000 | [diff] [blame] | 504 | if (hasScalarDepsInsideRegion(DelinearizedSize, &CurRegion)) |
| 505 | invalid<ReportNonAffineAccess>( |
| 506 | Context, /*Assert=*/true, DelinearizedSize, |
| 507 | Context.Accesses[BasePointer].front().first, BaseValue); |
Tobias Grosser | 80e237b | 2015-07-29 13:52:05 +0000 | [diff] [blame] | 508 | } |
Johannes Doerfert | 8983031 | 2015-05-03 16:03:01 +0000 | [diff] [blame] | 509 | |
Tobias Grosser | 230acc4 | 2014-09-13 14:47:55 +0000 | [diff] [blame] | 510 | // No array shape derived. |
| 511 | if (Shape->DelinearizedSizes.empty()) { |
| 512 | if (AllowNonAffine) |
| 513 | continue; |
Sebastian Pop | e8863b8 | 2014-05-12 19:02:02 +0000 | [diff] [blame] | 514 | |
Tobias Grosser | 230acc4 | 2014-09-13 14:47:55 +0000 | [diff] [blame] | 515 | for (const auto &Pair : Context.Accesses[BasePointer]) { |
| 516 | const Instruction *Insn = Pair.first; |
| 517 | const SCEV *AF = Pair.second; |
Sebastian Pop | 46e1ecd | 2014-05-09 22:45:15 +0000 | [diff] [blame] | 518 | |
Johannes Doerfert | fb79a96 | 2015-02-23 14:18:28 +0000 | [diff] [blame] | 519 | if (!isAffineExpr(&CurRegion, AF, *SE, BaseValue)) { |
Tobias Grosser | 230acc4 | 2014-09-13 14:47:55 +0000 | [diff] [blame] | 520 | invalid<ReportNonAffineAccess>(Context, /*Assert=*/true, AF, Insn, |
| 521 | BaseValue); |
| 522 | if (!KeepGoing) |
| 523 | return false; |
| 524 | } |
| 525 | } |
| 526 | continue; |
Sebastian Pop | 46e1ecd | 2014-05-09 22:45:15 +0000 | [diff] [blame] | 527 | } |
Tobias Grosser | 230acc4 | 2014-09-13 14:47:55 +0000 | [diff] [blame] | 528 | |
| 529 | // Third step: compute the access functions for each subscript. |
| 530 | // |
| 531 | // We first store the resulting memory accesses in TempMemoryAccesses. Only |
| 532 | // if the access functions for all memory accesses have been successfully |
| 533 | // delinearized we continue. Otherwise, we either report a failure or, if |
| 534 | // non-affine accesses are allowed, we drop the information. In case the |
| 535 | // information is dropped the memory accesses need to be overapproximated |
| 536 | // when translated to a polyhedral representation. |
| 537 | MapInsnToMemAcc TempMemoryAccesses; |
| 538 | for (const auto &Pair : Context.Accesses[BasePointer]) { |
| 539 | const Instruction *Insn = Pair.first; |
Tobias Grosser | 1b13dde | 2015-06-29 14:44:22 +0000 | [diff] [blame] | 540 | auto *AF = Pair.second; |
Tobias Grosser | 230acc4 | 2014-09-13 14:47:55 +0000 | [diff] [blame] | 541 | bool IsNonAffine = false; |
Tobias Grosser | d8308fb | 2015-06-05 05:52:15 +0000 | [diff] [blame] | 542 | TempMemoryAccesses.insert(std::make_pair(Insn, MemAcc(Insn, Shape))); |
Tobias Grosser | a5c092d | 2015-06-04 16:03:16 +0000 | [diff] [blame] | 543 | MemAcc *Acc = &TempMemoryAccesses.find(Insn)->second; |
Tobias Grosser | 230acc4 | 2014-09-13 14:47:55 +0000 | [diff] [blame] | 544 | |
| 545 | if (!AF) { |
Johannes Doerfert | fb79a96 | 2015-02-23 14:18:28 +0000 | [diff] [blame] | 546 | if (isAffineExpr(&CurRegion, Pair.second, *SE, BaseValue)) |
Tobias Grosser | 230acc4 | 2014-09-13 14:47:55 +0000 | [diff] [blame] | 547 | Acc->DelinearizedSubscripts.push_back(Pair.second); |
| 548 | else |
| 549 | IsNonAffine = true; |
| 550 | } else { |
Tobias Grosser | 23bceb2 | 2015-06-29 14:44:17 +0000 | [diff] [blame] | 551 | SE->computeAccessFunctions(AF, Acc->DelinearizedSubscripts, |
Tobias Grosser | 230acc4 | 2014-09-13 14:47:55 +0000 | [diff] [blame] | 552 | Shape->DelinearizedSizes); |
| 553 | if (Acc->DelinearizedSubscripts.size() == 0) |
| 554 | IsNonAffine = true; |
| 555 | for (const SCEV *S : Acc->DelinearizedSubscripts) |
Johannes Doerfert | fb79a96 | 2015-02-23 14:18:28 +0000 | [diff] [blame] | 556 | if (!isAffineExpr(&CurRegion, S, *SE, BaseValue)) |
Tobias Grosser | 230acc4 | 2014-09-13 14:47:55 +0000 | [diff] [blame] | 557 | IsNonAffine = true; |
| 558 | } |
| 559 | |
| 560 | // (Possibly) report non affine access |
| 561 | if (IsNonAffine) { |
| 562 | BasePtrHasNonAffine = true; |
| 563 | if (!AllowNonAffine) |
Tobias Grosser | 021eaef | 2015-01-08 19:03:10 +0000 | [diff] [blame] | 564 | invalid<ReportNonAffineAccess>(Context, /*Assert=*/true, Pair.second, |
| 565 | Insn, BaseValue); |
Tobias Grosser | 230acc4 | 2014-09-13 14:47:55 +0000 | [diff] [blame] | 566 | if (!KeepGoing && !AllowNonAffine) |
| 567 | return false; |
| 568 | } |
| 569 | } |
| 570 | |
| 571 | if (!BasePtrHasNonAffine) |
| 572 | InsnToMemAcc.insert(TempMemoryAccesses.begin(), TempMemoryAccesses.end()); |
Sebastian Pop | 46e1ecd | 2014-05-09 22:45:15 +0000 | [diff] [blame] | 573 | } |
Sebastian Pop | e8863b8 | 2014-05-12 19:02:02 +0000 | [diff] [blame] | 574 | return true; |
Sebastian Pop | 46e1ecd | 2014-05-09 22:45:15 +0000 | [diff] [blame] | 575 | } |
| 576 | |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 577 | bool ScopDetection::isValidMemoryAccess(Instruction &Inst, |
| 578 | DetectionContext &Context) const { |
Johannes Doerfert | fb79a96 | 2015-02-23 14:18:28 +0000 | [diff] [blame] | 579 | Region &CurRegion = Context.CurRegion; |
| 580 | |
Tobias Grosser | e5e171e | 2011-11-10 12:45:03 +0000 | [diff] [blame] | 581 | Value *Ptr = getPointerOperand(Inst); |
Sebastian Pop | 9f57c5b | 2013-04-10 04:05:18 +0000 | [diff] [blame] | 582 | Loop *L = LI->getLoopFor(Inst.getParent()); |
| 583 | const SCEV *AccessFunction = SE->getSCEVAtScope(Ptr, L); |
Tobias Grosser | b8710b5 | 2011-11-10 12:44:50 +0000 | [diff] [blame] | 584 | const SCEVUnknown *BasePointer; |
Tobias Grosser | e5e171e | 2011-11-10 12:45:03 +0000 | [diff] [blame] | 585 | Value *BaseValue; |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 586 | |
Tobias Grosser | b8710b5 | 2011-11-10 12:44:50 +0000 | [diff] [blame] | 587 | BasePointer = dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFunction)); |
| 588 | |
Andreas Simbuerger | 01a37a0 | 2014-04-02 11:54:01 +0000 | [diff] [blame] | 589 | if (!BasePointer) |
Andreas Simbuerger | 5569bf3 | 2014-06-26 10:06:40 +0000 | [diff] [blame] | 590 | return invalid<ReportNoBasePtr>(Context, /*Assert=*/true, &Inst); |
Tobias Grosser | b8710b5 | 2011-11-10 12:44:50 +0000 | [diff] [blame] | 591 | |
| 592 | BaseValue = BasePointer->getValue(); |
| 593 | |
Andreas Simbuerger | 01a37a0 | 2014-04-02 11:54:01 +0000 | [diff] [blame] | 594 | if (isa<UndefValue>(BaseValue)) |
Andreas Simbuerger | 5569bf3 | 2014-06-26 10:06:40 +0000 | [diff] [blame] | 595 | return invalid<ReportUndefBasePtr>(Context, /*Assert=*/true, &Inst); |
Tobias Grosser | b8710b5 | 2011-11-10 12:44:50 +0000 | [diff] [blame] | 596 | |
Tobias Grosser | 458fb78 | 2014-01-28 12:58:58 +0000 | [diff] [blame] | 597 | // Check that the base address of the access is invariant in the current |
| 598 | // region. |
Johannes Doerfert | fb79a96 | 2015-02-23 14:18:28 +0000 | [diff] [blame] | 599 | if (!isInvariant(*BaseValue, CurRegion)) |
Tobias Grosser | ab2227a | 2014-01-28 13:43:24 +0000 | [diff] [blame] | 600 | // Verification of this property is difficult as the independent blocks |
| 601 | // pass may introduce aliasing that we did not have when running the |
| 602 | // scop detection. |
Andreas Simbuerger | 5569bf3 | 2014-06-26 10:06:40 +0000 | [diff] [blame] | 603 | return invalid<ReportVariantBasePtr>(Context, /*Assert=*/false, BaseValue, |
| 604 | &Inst); |
Tobias Grosser | 458fb78 | 2014-01-28 12:58:58 +0000 | [diff] [blame] | 605 | |
Tobias Grosser | b8710b5 | 2011-11-10 12:44:50 +0000 | [diff] [blame] | 606 | AccessFunction = SE->getMinusSCEV(AccessFunction, BasePointer); |
| 607 | |
Tobias Grosser | bcd4eff | 2014-09-13 14:47:40 +0000 | [diff] [blame] | 608 | const SCEV *Size = SE->getElementSize(&Inst); |
| 609 | if (Context.ElementSize.count(BasePointer)) { |
| 610 | if (Context.ElementSize[BasePointer] != Size) |
| 611 | return invalid<ReportDifferentArrayElementSize>(Context, /*Assert=*/true, |
| 612 | &Inst, BaseValue); |
| 613 | } else { |
| 614 | Context.ElementSize[BasePointer] = Size; |
| 615 | } |
| 616 | |
Johannes Doerfert | f3e98f4 | 2015-04-12 22:52:20 +0000 | [diff] [blame] | 617 | bool isVariantInNonAffineLoop = false; |
| 618 | SetVector<const Loop *> Loops; |
| 619 | findLoops(AccessFunction, Loops); |
| 620 | for (const Loop *L : Loops) |
| 621 | if (Context.BoxedLoopsSet.count(L)) |
| 622 | isVariantInNonAffineLoop = true; |
| 623 | |
| 624 | if (PollyDelinearize && !isVariantInNonAffineLoop) { |
Tobias Grosser | 230acc4 | 2014-09-13 14:47:55 +0000 | [diff] [blame] | 625 | Context.Accesses[BasePointer].push_back({&Inst, AccessFunction}); |
Sebastian Pop | 46e1ecd | 2014-05-09 22:45:15 +0000 | [diff] [blame] | 626 | |
Johannes Doerfert | fb79a96 | 2015-02-23 14:18:28 +0000 | [diff] [blame] | 627 | if (!isAffineExpr(&CurRegion, AccessFunction, *SE, BaseValue)) |
Tobias Grosser | 230acc4 | 2014-09-13 14:47:55 +0000 | [diff] [blame] | 628 | Context.NonAffineAccesses.insert(BasePointer); |
| 629 | } else if (!AllowNonAffine) { |
Johannes Doerfert | f3e98f4 | 2015-04-12 22:52:20 +0000 | [diff] [blame] | 630 | if (isVariantInNonAffineLoop || |
| 631 | !isAffineExpr(&CurRegion, AccessFunction, *SE, BaseValue)) |
Sebastian Pop | cd3bb59 | 2014-04-10 16:08:11 +0000 | [diff] [blame] | 632 | return invalid<ReportNonAffineAccess>(Context, /*Assert=*/true, |
Andreas Simbuerger | d46b935 | 2014-08-17 10:09:11 +0000 | [diff] [blame] | 633 | AccessFunction, &Inst, BaseValue); |
Sebastian Pop | 1801668 | 2014-04-08 21:20:44 +0000 | [diff] [blame] | 634 | } |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 635 | |
| 636 | // FIXME: Alias Analysis thinks IntToPtrInst aliases with alloca instructions |
| 637 | // created by IndependentBlocks Pass. |
Andreas Simbuerger | 5569bf3 | 2014-06-26 10:06:40 +0000 | [diff] [blame] | 638 | if (IntToPtrInst *Inst = dyn_cast<IntToPtrInst>(BaseValue)) |
| 639 | return invalid<ReportIntToPtr>(Context, /*Assert=*/true, Inst); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 640 | |
Tobias Grosser | 1eedb67 | 2014-09-24 21:04:29 +0000 | [diff] [blame] | 641 | if (IgnoreAliasing) |
Sebastian Pop | 8c2d753 | 2013-07-03 22:50:36 +0000 | [diff] [blame] | 642 | return true; |
Tobias Grosser | fff5adc | 2011-11-10 13:21:43 +0000 | [diff] [blame] | 643 | |
Sebastian Pop | 8c2d753 | 2013-07-03 22:50:36 +0000 | [diff] [blame] | 644 | // Check if the base pointer of the memory access does alias with |
| 645 | // any other pointer. This cannot be handled at the moment. |
Benjamin Kramer | ae81abf | 2014-10-05 11:58:57 +0000 | [diff] [blame] | 646 | AAMDNodes AATags; |
| 647 | Inst.getAAMetadata(AATags); |
| 648 | AliasSet &AS = Context.AST.getAliasSetForPointer( |
Chandler Carruth | afa4ea7 | 2015-06-17 08:29:32 +0000 | [diff] [blame] | 649 | BaseValue, MemoryLocation::UnknownSize, AATags); |
Tobias Grosser | 428b3e4 | 2013-02-04 15:46:25 +0000 | [diff] [blame] | 650 | |
Sebastian Pop | 8c2d753 | 2013-07-03 22:50:36 +0000 | [diff] [blame] | 651 | // INVALID triggers an assertion in verifying mode, if it detects that a |
| 652 | // SCoP was detected by SCoP detection and that this SCoP was invalidated by |
| 653 | // a pass that stated it would preserve the SCoPs. We disable this check as |
| 654 | // the independent blocks pass may create memory references which seem to |
| 655 | // alias, if -basicaa is not available. They actually do not, but as we can |
| 656 | // not proof this without -basicaa we would fail. We disable this check to |
| 657 | // not cause irrelevant verification failures. |
Tobias Grosser | 1eedb67 | 2014-09-24 21:04:29 +0000 | [diff] [blame] | 658 | if (!AS.isMustAlias()) { |
| 659 | if (PollyUseRuntimeAliasChecks) { |
| 660 | bool CanBuildRunTimeCheck = true; |
| 661 | // The run-time alias check places code that involves the base pointer at |
| 662 | // the beginning of the SCoP. This breaks if the base pointer is defined |
| 663 | // inside the scop. Hence, we can only create a run-time check if we are |
| 664 | // sure the base pointer is not an instruction defined inside the scop. |
| 665 | for (const auto &Ptr : AS) { |
| 666 | Instruction *Inst = dyn_cast<Instruction>(Ptr.getValue()); |
Johannes Doerfert | fb79a96 | 2015-02-23 14:18:28 +0000 | [diff] [blame] | 667 | if (Inst && CurRegion.contains(Inst)) { |
Tobias Grosser | 1eedb67 | 2014-09-24 21:04:29 +0000 | [diff] [blame] | 668 | CanBuildRunTimeCheck = false; |
| 669 | break; |
| 670 | } |
| 671 | } |
| 672 | |
| 673 | if (CanBuildRunTimeCheck) |
| 674 | return true; |
| 675 | } |
Andreas Simbuerger | e2c9243 | 2014-06-26 10:19:57 +0000 | [diff] [blame] | 676 | return invalid<ReportAlias>(Context, /*Assert=*/false, &Inst, AS); |
Tobias Grosser | 1eedb67 | 2014-09-24 21:04:29 +0000 | [diff] [blame] | 677 | } |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 678 | |
| 679 | return true; |
| 680 | } |
| 681 | |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 682 | bool ScopDetection::isValidInstruction(Instruction &Inst, |
| 683 | DetectionContext &Context) const { |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 684 | // We only check the call instruction but not invoke instruction. |
| 685 | if (CallInst *CI = dyn_cast<CallInst>(&Inst)) { |
| 686 | if (isValidCallInst(*CI)) |
| 687 | return true; |
| 688 | |
Andreas Simbuerger | 01a37a0 | 2014-04-02 11:54:01 +0000 | [diff] [blame] | 689 | return invalid<ReportFuncCall>(Context, /*Assert=*/true, &Inst); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 690 | } |
| 691 | |
| 692 | if (!Inst.mayWriteToMemory() && !Inst.mayReadFromMemory()) { |
Tobias Grosser | 5b1a7f2 | 2013-07-22 03:50:33 +0000 | [diff] [blame] | 693 | if (!isa<AllocaInst>(Inst)) |
| 694 | return true; |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 695 | |
Andreas Simbuerger | 01a37a0 | 2014-04-02 11:54:01 +0000 | [diff] [blame] | 696 | return invalid<ReportAlloca>(Context, /*Assert=*/true, &Inst); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 697 | } |
| 698 | |
| 699 | // Check the access function. |
Tobias Grosser | d1e33e7 | 2015-02-19 05:31:07 +0000 | [diff] [blame] | 700 | if (isa<LoadInst>(Inst) || isa<StoreInst>(Inst)) { |
| 701 | Context.hasStores |= isa<StoreInst>(Inst); |
| 702 | Context.hasLoads |= isa<LoadInst>(Inst); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 703 | return isValidMemoryAccess(Inst, Context); |
Tobias Grosser | d1e33e7 | 2015-02-19 05:31:07 +0000 | [diff] [blame] | 704 | } |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 705 | |
| 706 | // We do not know this instruction, therefore we assume it is invalid. |
Andreas Simbuerger | 01a37a0 | 2014-04-02 11:54:01 +0000 | [diff] [blame] | 707 | return invalid<ReportUnknownInst>(Context, /*Assert=*/true, &Inst); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 708 | } |
| 709 | |
Johannes Doerfert | d020b77 | 2015-08-27 06:53:52 +0000 | [diff] [blame] | 710 | bool ScopDetection::canUseISLTripCount(Loop *L, |
| 711 | DetectionContext &Context) const { |
| 712 | |
| 713 | Region &CurRegion = Context.CurRegion; |
| 714 | |
| 715 | // Ensure the loop has a single back edge. |
| 716 | if (L->getNumBackEdges() != 1) |
| 717 | return false; |
| 718 | |
| 719 | // Ensure the loop has a single exiting block. |
| 720 | BasicBlock *ExitingBB = L->getExitingBlock(); |
| 721 | if (!ExitingBB) |
| 722 | return false; |
| 723 | |
| 724 | // Ensure the exiting block is terminated by a conditional branch. |
| 725 | BranchInst *Term = dyn_cast<BranchInst>(ExitingBB->getTerminator()); |
| 726 | if (!Term || !Term->isConditional()) |
| 727 | return false; |
| 728 | |
| 729 | Value *Cond = Term->getCondition(); |
| 730 | |
| 731 | // If the terminating condition is an integer comparison, ensure that it is a |
| 732 | // comparison between a recurrence and an invariant value. |
| 733 | if (ICmpInst *I = dyn_cast<ICmpInst>(Cond)) { |
| 734 | const Value *Op0 = I->getOperand(0); |
| 735 | const Value *Op1 = I->getOperand(1); |
| 736 | const SCEV *LHS = SE->getSCEVAtScope(const_cast<Value *>(Op0), L); |
| 737 | const SCEV *RHS = SE->getSCEVAtScope(const_cast<Value *>(Op1), L); |
| 738 | if ((isa<SCEVAddRecExpr>(LHS) && !isInvariant(*Op1, CurRegion)) || |
| 739 | (isa<SCEVAddRecExpr>(RHS) && !isInvariant(*Op0, CurRegion))) |
| 740 | return false; |
| 741 | } |
| 742 | |
| 743 | // If the terminating condition is not an integer comparison, ensure that it |
| 744 | // is a constant. |
| 745 | else if (!isa<ConstantInt>(Cond)) |
| 746 | return false; |
| 747 | |
| 748 | // We can use ISL to compute the trip count of L. |
| 749 | return true; |
| 750 | } |
| 751 | |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 752 | bool ScopDetection::isValidLoop(Loop *L, DetectionContext &Context) const { |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 753 | // Is the loop count affine? |
Johannes Doerfert | d020b77 | 2015-08-27 06:53:52 +0000 | [diff] [blame] | 754 | bool IsLoopCountAffine = false; |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 755 | const SCEV *LoopCount = SE->getBackedgeTakenCount(L); |
Johannes Doerfert | d020b77 | 2015-08-27 06:53:52 +0000 | [diff] [blame] | 756 | if (!isa<SCEVCouldNotCompute>(LoopCount)) |
| 757 | IsLoopCountAffine = isAffineExpr(&Context.CurRegion, LoopCount, *SE); |
| 758 | else |
| 759 | IsLoopCountAffine = canUseISLTripCount(L, Context); |
| 760 | if (IsLoopCountAffine) { |
Johannes Doerfert | f3e98f4 | 2015-04-12 22:52:20 +0000 | [diff] [blame] | 761 | Context.hasAffineLoops = true; |
Johannes Doerfert | ba65c16 | 2015-02-24 11:45:21 +0000 | [diff] [blame] | 762 | return true; |
Johannes Doerfert | f3e98f4 | 2015-04-12 22:52:20 +0000 | [diff] [blame] | 763 | } |
| 764 | |
| 765 | if (AllowNonAffineSubRegions) { |
| 766 | Region *R = RI->getRegionFor(L->getHeader()); |
| 767 | if (R->contains(L)) |
| 768 | if (addOverApproximatedRegion(R, Context)) |
| 769 | return true; |
| 770 | } |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 771 | |
Johannes Doerfert | ba65c16 | 2015-02-24 11:45:21 +0000 | [diff] [blame] | 772 | return invalid<ReportLoopBound>(Context, /*Assert=*/true, L, LoopCount); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 773 | } |
| 774 | |
Tobias Grosser | ed21a1f | 2015-08-27 16:55:18 +0000 | [diff] [blame] | 775 | bool ScopDetection::hasMoreThanOneLoop(Region *R) const { |
Tobias Grosser | 050e0cb | 2015-08-31 12:08:11 +0000 | [diff] [blame] | 776 | auto LoopNum = 0; |
Tobias Grosser | ed21a1f | 2015-08-27 16:55:18 +0000 | [diff] [blame] | 777 | |
Tobias Grosser | 050e0cb | 2015-08-31 12:08:11 +0000 | [diff] [blame] | 778 | auto L = LI->getLoopFor(R->getEntry()); |
| 779 | L = L ? R->outermostLoopInRegion(L) : nullptr; |
| 780 | L = L ? L->getParentLoop() : nullptr; |
Tobias Grosser | ed21a1f | 2015-08-27 16:55:18 +0000 | [diff] [blame] | 781 | |
Tobias Grosser | 050e0cb | 2015-08-31 12:08:11 +0000 | [diff] [blame] | 782 | auto SubLoops = |
| 783 | L ? L->getSubLoopsVector() : std::vector<Loop *>(LI->begin(), LI->end()); |
| 784 | |
| 785 | for (auto &SubLoop : SubLoops) |
| 786 | if (R->contains(SubLoop)) { |
| 787 | LoopNum++; |
Tobias Grosser | 40820ca | 2015-08-31 21:04:51 +0000 | [diff] [blame] | 788 | if (SubLoop->getSubLoopsVector().size() > 0) |
Tobias Grosser | 050e0cb | 2015-08-31 12:08:11 +0000 | [diff] [blame] | 789 | LoopNum++; |
| 790 | |
| 791 | if (LoopNum >= 2) |
Tobias Grosser | ed21a1f | 2015-08-27 16:55:18 +0000 | [diff] [blame] | 792 | return true; |
Tobias Grosser | 050e0cb | 2015-08-31 12:08:11 +0000 | [diff] [blame] | 793 | } |
Tobias Grosser | ed21a1f | 2015-08-27 16:55:18 +0000 | [diff] [blame] | 794 | return false; |
| 795 | } |
| 796 | |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 797 | Region *ScopDetection::expandRegion(Region &R) { |
Hongbin Zheng | ed986ab | 2012-04-07 15:14:28 +0000 | [diff] [blame] | 798 | // Initial no valid region was found (greater than R) |
Tobias Grosser | d5d93ec | 2015-06-04 17:59:54 +0000 | [diff] [blame] | 799 | std::unique_ptr<Region> LastValidRegion; |
| 800 | auto ExpandedRegion = std::unique_ptr<Region>(R.getExpandedRegion()); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 801 | |
| 802 | DEBUG(dbgs() << "\tExpanding " << R.getNameStr() << "\n"); |
| 803 | |
Hongbin Zheng | ed986ab | 2012-04-07 15:14:28 +0000 | [diff] [blame] | 804 | while (ExpandedRegion) { |
Johannes Doerfert | f3e98f4 | 2015-04-12 22:52:20 +0000 | [diff] [blame] | 805 | DetectionContext Context( |
Tobias Grosser | d5d93ec | 2015-06-04 17:59:54 +0000 | [diff] [blame] | 806 | *ExpandedRegion, *AA, NonAffineSubRegionMap[ExpandedRegion.get()], |
| 807 | BoxedLoopsMap[ExpandedRegion.get()], false /* verifying */); |
Hongbin Zheng | ed986ab | 2012-04-07 15:14:28 +0000 | [diff] [blame] | 808 | DEBUG(dbgs() << "\t\tTrying " << ExpandedRegion->getNameStr() << "\n"); |
Andreas Simbuerger | b379edb | 2014-06-27 06:21:14 +0000 | [diff] [blame] | 809 | // Only expand when we did not collect errors. |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 810 | |
Johannes Doerfert | 717b866 | 2015-09-08 21:44:27 +0000 | [diff] [blame] | 811 | if (!Context.Log.hasErrors()) { |
Hongbin Zheng | ed986ab | 2012-04-07 15:14:28 +0000 | [diff] [blame] | 812 | // If the exit is valid check all blocks |
| 813 | // - if true, a valid region was found => store it + keep expanding |
| 814 | // - if false, .tbd. => stop (should this really end the loop?) |
Andreas Simbuerger | b379edb | 2014-06-27 06:21:14 +0000 | [diff] [blame] | 815 | if (!allBlocksValid(Context) || Context.Log.hasErrors()) |
| 816 | break; |
| 817 | |
Tobias Grosser | d7e5864 | 2013-04-10 06:55:45 +0000 | [diff] [blame] | 818 | // Store this region, because it is the greatest valid (encountered so |
| 819 | // far). |
Tobias Grosser | d5d93ec | 2015-06-04 17:59:54 +0000 | [diff] [blame] | 820 | LastValidRegion = std::move(ExpandedRegion); |
Hongbin Zheng | ed986ab | 2012-04-07 15:14:28 +0000 | [diff] [blame] | 821 | |
| 822 | // Create and test the next greater region (if any) |
Tobias Grosser | d5d93ec | 2015-06-04 17:59:54 +0000 | [diff] [blame] | 823 | ExpandedRegion = |
| 824 | std::unique_ptr<Region>(LastValidRegion->getExpandedRegion()); |
Hongbin Zheng | ed986ab | 2012-04-07 15:14:28 +0000 | [diff] [blame] | 825 | |
| 826 | } else { |
| 827 | // Create and test the next greater region (if any) |
Tobias Grosser | d5d93ec | 2015-06-04 17:59:54 +0000 | [diff] [blame] | 828 | ExpandedRegion = |
| 829 | std::unique_ptr<Region>(ExpandedRegion->getExpandedRegion()); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 830 | } |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 831 | } |
| 832 | |
Tobias Grosser | 378a9f2 | 2013-11-16 19:34:11 +0000 | [diff] [blame] | 833 | DEBUG({ |
| 834 | if (LastValidRegion) |
| 835 | dbgs() << "\tto " << LastValidRegion->getNameStr() << "\n"; |
| 836 | else |
| 837 | dbgs() << "\tExpanding " << R.getNameStr() << " failed\n"; |
| 838 | }); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 839 | |
Tobias Grosser | d5d93ec | 2015-06-04 17:59:54 +0000 | [diff] [blame] | 840 | return LastValidRegion.release(); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 841 | } |
Sebastian Pop | 2c9ec2e | 2013-06-03 16:35:37 +0000 | [diff] [blame] | 842 | static bool regionWithoutLoops(Region &R, LoopInfo *LI) { |
Tobias Grosser | 2610889 | 2014-04-02 20:18:19 +0000 | [diff] [blame] | 843 | for (const BasicBlock *BB : R.blocks()) |
Tobias Grosser | 1d19190 | 2014-03-03 13:13:55 +0000 | [diff] [blame] | 844 | if (R.contains(LI->getLoopFor(BB))) |
Sebastian Pop | 2c9ec2e | 2013-06-03 16:35:37 +0000 | [diff] [blame] | 845 | return false; |
| 846 | |
| 847 | return true; |
| 848 | } |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 849 | |
Tobias Grosser | 28a70c5 | 2014-01-29 19:05:30 +0000 | [diff] [blame] | 850 | // Remove all direct and indirect children of region R from the region set Regs, |
| 851 | // but do not recurse further if the first child has been found. |
| 852 | // |
| 853 | // Return the number of regions erased from Regs. |
David Peixotto | 8da2b93 | 2014-10-22 20:39:07 +0000 | [diff] [blame] | 854 | static unsigned eraseAllChildren(ScopDetection::RegionSet &Regs, |
David Blaikie | b035f6d | 2014-04-15 18:45:27 +0000 | [diff] [blame] | 855 | const Region &R) { |
Tobias Grosser | 28a70c5 | 2014-01-29 19:05:30 +0000 | [diff] [blame] | 856 | unsigned Count = 0; |
David Blaikie | b035f6d | 2014-04-15 18:45:27 +0000 | [diff] [blame] | 857 | for (auto &SubRegion : R) { |
David Peixotto | 8da2b93 | 2014-10-22 20:39:07 +0000 | [diff] [blame] | 858 | if (Regs.count(SubRegion.get())) { |
Tobias Grosser | 28a70c5 | 2014-01-29 19:05:30 +0000 | [diff] [blame] | 859 | ++Count; |
David Peixotto | 8da2b93 | 2014-10-22 20:39:07 +0000 | [diff] [blame] | 860 | Regs.remove(SubRegion.get()); |
Tobias Grosser | 28a70c5 | 2014-01-29 19:05:30 +0000 | [diff] [blame] | 861 | } else { |
David Blaikie | b035f6d | 2014-04-15 18:45:27 +0000 | [diff] [blame] | 862 | Count += eraseAllChildren(Regs, *SubRegion); |
Tobias Grosser | 28a70c5 | 2014-01-29 19:05:30 +0000 | [diff] [blame] | 863 | } |
| 864 | } |
| 865 | return Count; |
| 866 | } |
| 867 | |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 868 | void ScopDetection::findScops(Region &R) { |
Johannes Doerfert | f3e98f4 | 2015-04-12 22:52:20 +0000 | [diff] [blame] | 869 | DetectionContext Context(R, *AA, NonAffineSubRegionMap[&R], BoxedLoopsMap[&R], |
Johannes Doerfert | ba65c16 | 2015-02-24 11:45:21 +0000 | [diff] [blame] | 870 | false /*verifying*/); |
Johannes Doerfert | 6a4d81c | 2015-03-08 15:11:50 +0000 | [diff] [blame] | 871 | |
| 872 | bool RegionIsValid = false; |
Tobias Grosser | 02e6589 | 2015-09-08 19:46:41 +0000 | [diff] [blame] | 873 | if (!DetectUnprofitable && regionWithoutLoops(R, LI)) |
Johannes Doerfert | 6a4d81c | 2015-03-08 15:11:50 +0000 | [diff] [blame] | 874 | invalid<ReportUnprofitable>(Context, /*Assert=*/true, &R); |
| 875 | else |
| 876 | RegionIsValid = isValidRegion(Context); |
| 877 | |
Johannes Doerfert | 3f1c285 | 2015-02-19 18:11:50 +0000 | [diff] [blame] | 878 | bool HasErrors = !RegionIsValid || Context.Log.size() > 0; |
Andreas Simbuerger | 0447240 | 2014-05-24 09:25:10 +0000 | [diff] [blame] | 879 | |
Johannes Doerfert | 3f1c285 | 2015-02-19 18:11:50 +0000 | [diff] [blame] | 880 | if (PollyTrackFailures && HasErrors) |
| 881 | RejectLogs.insert(std::make_pair(&R, Context.Log)); |
| 882 | |
| 883 | if (!HasErrors) { |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 884 | ++ValidRegion; |
| 885 | ValidRegions.insert(&R); |
| 886 | return; |
| 887 | } |
| 888 | |
David Blaikie | b035f6d | 2014-04-15 18:45:27 +0000 | [diff] [blame] | 889 | for (auto &SubRegion : R) |
Tobias Grosser | 00dc309 | 2014-03-02 12:02:46 +0000 | [diff] [blame] | 890 | findScops(*SubRegion); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 891 | |
| 892 | // Try to expand regions. |
| 893 | // |
| 894 | // As the region tree normally only contains canonical regions, non canonical |
| 895 | // regions that form a Scop are not found. Therefore, those non canonical |
| 896 | // regions are checked by expanding the canonical ones. |
| 897 | |
Tobias Grosser | 0d1eee3 | 2013-02-05 11:56:05 +0000 | [diff] [blame] | 898 | std::vector<Region *> ToExpand; |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 899 | |
David Blaikie | b035f6d | 2014-04-15 18:45:27 +0000 | [diff] [blame] | 900 | for (auto &SubRegion : R) |
| 901 | ToExpand.push_back(SubRegion.get()); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 902 | |
Tobias Grosser | 2610889 | 2014-04-02 20:18:19 +0000 | [diff] [blame] | 903 | for (Region *CurrentRegion : ToExpand) { |
Andreas Simbuerger | b379edb | 2014-06-27 06:21:14 +0000 | [diff] [blame] | 904 | // Skip regions that had errors. |
| 905 | bool HadErrors = RejectLogs.hasErrors(CurrentRegion); |
| 906 | if (HadErrors) |
| 907 | continue; |
| 908 | |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 909 | // Skip invalid regions. Regions may become invalid, if they are element of |
| 910 | // an already expanded region. |
David Peixotto | 8da2b93 | 2014-10-22 20:39:07 +0000 | [diff] [blame] | 911 | if (!ValidRegions.count(CurrentRegion)) |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 912 | continue; |
| 913 | |
| 914 | Region *ExpandedR = expandRegion(*CurrentRegion); |
| 915 | |
| 916 | if (!ExpandedR) |
| 917 | continue; |
| 918 | |
| 919 | R.addSubRegion(ExpandedR, true); |
| 920 | ValidRegions.insert(ExpandedR); |
David Peixotto | 8da2b93 | 2014-10-22 20:39:07 +0000 | [diff] [blame] | 921 | ValidRegions.remove(CurrentRegion); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 922 | |
Tobias Grosser | 28a70c5 | 2014-01-29 19:05:30 +0000 | [diff] [blame] | 923 | // Erase all (direct and indirect) children of ExpandedR from the valid |
| 924 | // regions and update the number of valid regions. |
David Blaikie | b035f6d | 2014-04-15 18:45:27 +0000 | [diff] [blame] | 925 | ValidRegion -= eraseAllChildren(ValidRegions, *ExpandedR); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 926 | } |
| 927 | } |
| 928 | |
| 929 | bool ScopDetection::allBlocksValid(DetectionContext &Context) const { |
Johannes Doerfert | fb79a96 | 2015-02-23 14:18:28 +0000 | [diff] [blame] | 930 | Region &CurRegion = Context.CurRegion; |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 931 | |
Johannes Doerfert | fb79a96 | 2015-02-23 14:18:28 +0000 | [diff] [blame] | 932 | for (const BasicBlock *BB : CurRegion.blocks()) { |
Tobias Grosser | 1d19190 | 2014-03-03 13:13:55 +0000 | [diff] [blame] | 933 | Loop *L = LI->getLoopFor(BB); |
Andreas Simbuerger | 0447240 | 2014-05-24 09:25:10 +0000 | [diff] [blame] | 934 | if (L && L->getHeader() == BB && (!isValidLoop(L, Context) && !KeepGoing)) |
Sebastian Pop | b88ea5e | 2013-06-11 22:20:32 +0000 | [diff] [blame] | 935 | return false; |
| 936 | } |
| 937 | |
Johannes Doerfert | fb79a96 | 2015-02-23 14:18:28 +0000 | [diff] [blame] | 938 | for (BasicBlock *BB : CurRegion.blocks()) |
Andreas Simbuerger | 0447240 | 2014-05-24 09:25:10 +0000 | [diff] [blame] | 939 | if (!isValidCFG(*BB, Context) && !KeepGoing) |
Sebastian Pop | 9e3d2dd | 2013-06-11 22:20:27 +0000 | [diff] [blame] | 940 | return false; |
| 941 | |
Johannes Doerfert | fb79a96 | 2015-02-23 14:18:28 +0000 | [diff] [blame] | 942 | for (BasicBlock *BB : CurRegion.blocks()) |
Tobias Grosser | 1d19190 | 2014-03-03 13:13:55 +0000 | [diff] [blame] | 943 | for (BasicBlock::iterator I = BB->begin(), E = --BB->end(); I != E; ++I) |
Andreas Simbuerger | 0447240 | 2014-05-24 09:25:10 +0000 | [diff] [blame] | 944 | if (!isValidInstruction(*I, Context) && !KeepGoing) |
Sebastian Pop | 8ca899c | 2013-06-14 20:20:43 +0000 | [diff] [blame] | 945 | return false; |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 946 | |
Sebastian Pop | e8863b8 | 2014-05-12 19:02:02 +0000 | [diff] [blame] | 947 | if (!hasAffineMemoryAccesses(Context)) |
Sebastian Pop | 46e1ecd | 2014-05-09 22:45:15 +0000 | [diff] [blame] | 948 | return false; |
| 949 | |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 950 | return true; |
| 951 | } |
| 952 | |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 953 | bool ScopDetection::isValidRegion(DetectionContext &Context) const { |
Johannes Doerfert | fb79a96 | 2015-02-23 14:18:28 +0000 | [diff] [blame] | 954 | Region &CurRegion = Context.CurRegion; |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 955 | |
Johannes Doerfert | fb79a96 | 2015-02-23 14:18:28 +0000 | [diff] [blame] | 956 | DEBUG(dbgs() << "Checking region: " << CurRegion.getNameStr() << "\n\t"); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 957 | |
Johannes Doerfert | fb79a96 | 2015-02-23 14:18:28 +0000 | [diff] [blame] | 958 | if (CurRegion.isTopLevelRegion()) { |
Tobias Grosser | f084edd | 2014-10-22 23:00:03 +0000 | [diff] [blame] | 959 | DEBUG(dbgs() << "Top level region is invalid\n"); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 960 | return false; |
| 961 | } |
| 962 | |
Johannes Doerfert | fb79a96 | 2015-02-23 14:18:28 +0000 | [diff] [blame] | 963 | if (!CurRegion.getEntry()->getName().count(OnlyRegion)) { |
Tobias Grosser | 4449e52 | 2014-01-27 14:24:53 +0000 | [diff] [blame] | 964 | DEBUG({ |
| 965 | dbgs() << "Region entry does not match -polly-region-only"; |
| 966 | dbgs() << "\n"; |
| 967 | }); |
| 968 | return false; |
| 969 | } |
| 970 | |
Johannes Doerfert | fb79a96 | 2015-02-23 14:18:28 +0000 | [diff] [blame] | 971 | if (!CurRegion.getEnteringBlock()) { |
| 972 | BasicBlock *entry = CurRegion.getEntry(); |
Sebastian Pop | 9d63234 | 2013-06-11 22:20:40 +0000 | [diff] [blame] | 973 | Loop *L = LI->getLoopFor(entry); |
| 974 | |
| 975 | if (L) { |
Andreas Simbuerger | 01a37a0 | 2014-04-02 11:54:01 +0000 | [diff] [blame] | 976 | if (!L->isLoopSimplifyForm()) |
| 977 | return invalid<ReportSimpleLoop>(Context, /*Assert=*/true); |
Sebastian Pop | 9d63234 | 2013-06-11 22:20:40 +0000 | [diff] [blame] | 978 | |
| 979 | for (pred_iterator PI = pred_begin(entry), PE = pred_end(entry); PI != PE; |
| 980 | ++PI) { |
| 981 | // Region entering edges come from the same loop but outside the region |
| 982 | // are not allowed. |
Johannes Doerfert | fb79a96 | 2015-02-23 14:18:28 +0000 | [diff] [blame] | 983 | if (L->contains(*PI) && !CurRegion.contains(*PI)) |
Andreas Simbuerger | 5569bf3 | 2014-06-26 10:06:40 +0000 | [diff] [blame] | 984 | return invalid<ReportIndEdge>(Context, /*Assert=*/true, *PI); |
Sebastian Pop | 9d63234 | 2013-06-11 22:20:40 +0000 | [diff] [blame] | 985 | } |
| 986 | } |
Tobias Grosser | 8edce4e | 2013-04-16 08:04:42 +0000 | [diff] [blame] | 987 | } |
| 988 | |
Tobias Grosser | d654c25 | 2012-04-10 18:12:19 +0000 | [diff] [blame] | 989 | // SCoP cannot contain the entry block of the function, because we need |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 990 | // to insert alloca instruction there when translate scalar to array. |
Johannes Doerfert | fb79a96 | 2015-02-23 14:18:28 +0000 | [diff] [blame] | 991 | if (CurRegion.getEntry() == |
| 992 | &(CurRegion.getEntry()->getParent()->getEntryBlock())) |
| 993 | return invalid<ReportEntry>(Context, /*Assert=*/true, CurRegion.getEntry()); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 994 | |
Tobias Grosser | ed21a1f | 2015-08-27 16:55:18 +0000 | [diff] [blame] | 995 | if (!DetectUnprofitable && !hasMoreThanOneLoop(&CurRegion)) |
| 996 | invalid<ReportUnprofitable>(Context, /*Assert=*/true, &CurRegion); |
| 997 | |
Hongbin Zheng | 94868e6 | 2012-04-07 12:29:17 +0000 | [diff] [blame] | 998 | if (!allBlocksValid(Context)) |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 999 | return false; |
| 1000 | |
Tobias Grosser | d1e33e7 | 2015-02-19 05:31:07 +0000 | [diff] [blame] | 1001 | // We can probably not do a lot on scops that only write or only read |
| 1002 | // data. |
| 1003 | if (!DetectUnprofitable && (!Context.hasStores || !Context.hasLoads)) |
Johannes Doerfert | 6a4d81c | 2015-03-08 15:11:50 +0000 | [diff] [blame] | 1004 | invalid<ReportUnprofitable>(Context, /*Assert=*/true, &CurRegion); |
Tobias Grosser | d1e33e7 | 2015-02-19 05:31:07 +0000 | [diff] [blame] | 1005 | |
Johannes Doerfert | f3e98f4 | 2015-04-12 22:52:20 +0000 | [diff] [blame] | 1006 | // Check if there was at least one non-overapproximated loop in the region or |
| 1007 | // we allow regions without loops. |
Tobias Grosser | 02e6589 | 2015-09-08 19:46:41 +0000 | [diff] [blame] | 1008 | if (!DetectUnprofitable && !Context.hasAffineLoops) |
Johannes Doerfert | f3e98f4 | 2015-04-12 22:52:20 +0000 | [diff] [blame] | 1009 | invalid<ReportUnprofitable>(Context, /*Assert=*/true, &CurRegion); |
| 1010 | |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 1011 | DEBUG(dbgs() << "OK\n"); |
| 1012 | return true; |
| 1013 | } |
| 1014 | |
Johannes Doerfert | 43e1ead | 2014-07-15 21:06:48 +0000 | [diff] [blame] | 1015 | void ScopDetection::markFunctionAsInvalid(Function *F) const { |
| 1016 | F->addFnAttr(PollySkipFnAttr); |
| 1017 | } |
| 1018 | |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 1019 | bool ScopDetection::isValidFunction(llvm::Function &F) { |
Johannes Doerfert | 43e1ead | 2014-07-15 21:06:48 +0000 | [diff] [blame] | 1020 | return !F.hasFnAttribute(PollySkipFnAttr); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 1021 | } |
| 1022 | |
Tobias Grosser | b2863ca | 2013-03-04 19:49:51 +0000 | [diff] [blame] | 1023 | void ScopDetection::printLocations(llvm::Function &F) { |
Tobias Grosser | 2610889 | 2014-04-02 20:18:19 +0000 | [diff] [blame] | 1024 | for (const Region *R : *this) { |
Tobias Grosser | 531891e | 2012-11-01 16:45:20 +0000 | [diff] [blame] | 1025 | unsigned LineEntry, LineExit; |
| 1026 | std::string FileName; |
| 1027 | |
Tobias Grosser | 00dc309 | 2014-03-02 12:02:46 +0000 | [diff] [blame] | 1028 | getDebugLocation(R, LineEntry, LineExit, FileName); |
Tobias Grosser | 8519f89 | 2013-12-18 10:49:53 +0000 | [diff] [blame] | 1029 | DiagnosticScopFound Diagnostic(F, FileName, LineEntry, LineExit); |
| 1030 | F.getContext().diagnose(Diagnostic); |
Tobias Grosser | 531891e | 2012-11-01 16:45:20 +0000 | [diff] [blame] | 1031 | } |
| 1032 | } |
| 1033 | |
Daniel Jasper | 8a1dea0 | 2014-10-27 19:45:31 +0000 | [diff] [blame] | 1034 | void ScopDetection::emitMissedRemarksForValidRegions( |
| 1035 | const Function &F, const RegionSet &ValidRegions) { |
Andreas Simbuerger | 5569bf3 | 2014-06-26 10:06:40 +0000 | [diff] [blame] | 1036 | for (const Region *R : ValidRegions) { |
| 1037 | const Region *Parent = R->getParent(); |
| 1038 | if (Parent && !Parent->isTopLevelRegion() && RejectLogs.count(Parent)) |
| 1039 | emitRejectionRemarks(F, RejectLogs.at(Parent)); |
| 1040 | } |
| 1041 | } |
| 1042 | |
| 1043 | void ScopDetection::emitMissedRemarksForLeaves(const Function &F, |
| 1044 | const Region *R) { |
| 1045 | for (const std::unique_ptr<Region> &Child : *R) { |
| 1046 | bool IsValid = ValidRegions.count(Child.get()); |
| 1047 | if (IsValid) |
| 1048 | continue; |
| 1049 | |
| 1050 | bool IsLeaf = Child->begin() == Child->end(); |
| 1051 | if (!IsLeaf) |
| 1052 | emitMissedRemarksForLeaves(F, Child.get()); |
| 1053 | else { |
| 1054 | if (RejectLogs.count(Child.get())) { |
| 1055 | emitRejectionRemarks(F, RejectLogs.at(Child.get())); |
| 1056 | } |
| 1057 | } |
| 1058 | } |
| 1059 | } |
| 1060 | |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 1061 | bool ScopDetection::runOnFunction(llvm::Function &F) { |
Chandler Carruth | f557987 | 2015-01-17 14:16:56 +0000 | [diff] [blame] | 1062 | LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); |
Matt Arsenault | 8ca3681 | 2014-07-19 18:40:17 +0000 | [diff] [blame] | 1063 | RI = &getAnalysis<RegionInfoPass>().getRegionInfo(); |
Tobias Grosser | 02e6589 | 2015-09-08 19:46:41 +0000 | [diff] [blame] | 1064 | if (!DetectUnprofitable && LI->empty()) |
Sebastian Pop | 8fe6d11 | 2013-05-30 17:47:32 +0000 | [diff] [blame] | 1065 | return false; |
| 1066 | |
Chandler Carruth | 66ef16b | 2015-09-09 22:13:56 +0000 | [diff] [blame^] | 1067 | AA = &getAnalysis<AAResultsWrapperPass>().getAAResults(); |
Tobias Grosser | c5bcf24 | 2015-08-17 10:57:08 +0000 | [diff] [blame] | 1068 | SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE(); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 1069 | Region *TopRegion = RI->getTopLevelRegion(); |
| 1070 | |
Tobias Grosser | 2ff8723 | 2011-10-23 11:17:06 +0000 | [diff] [blame] | 1071 | releaseMemory(); |
| 1072 | |
Tobias Grosser | a3ab27e | 2014-05-07 11:23:32 +0000 | [diff] [blame] | 1073 | if (OnlyFunction != "" && !F.getName().count(OnlyFunction)) |
Tobias Grosser | 2ff8723 | 2011-10-23 11:17:06 +0000 | [diff] [blame] | 1074 | return false; |
| 1075 | |
Tobias Grosser | 1bb59b0 | 2012-12-29 23:47:38 +0000 | [diff] [blame] | 1076 | if (!isValidFunction(F)) |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 1077 | return false; |
| 1078 | |
| 1079 | findScops(*TopRegion); |
Tobias Grosser | 531891e | 2012-11-01 16:45:20 +0000 | [diff] [blame] | 1080 | |
Andreas Simbuerger | 5569bf3 | 2014-06-26 10:06:40 +0000 | [diff] [blame] | 1081 | // Only makes sense when we tracked errors. |
| 1082 | if (PollyTrackFailures) { |
| 1083 | emitMissedRemarksForValidRegions(F, ValidRegions); |
| 1084 | emitMissedRemarksForLeaves(F, TopRegion); |
| 1085 | } |
| 1086 | |
| 1087 | for (const Region *R : ValidRegions) |
| 1088 | emitValidRemarks(F, R); |
| 1089 | |
Johannes Doerfert | a05214f | 2014-10-15 23:24:28 +0000 | [diff] [blame] | 1090 | if (ReportLevel) |
Tobias Grosser | b2863ca | 2013-03-04 19:49:51 +0000 | [diff] [blame] | 1091 | printLocations(F); |
Tobias Grosser | 531891e | 2012-11-01 16:45:20 +0000 | [diff] [blame] | 1092 | |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 1093 | return false; |
| 1094 | } |
| 1095 | |
Johannes Doerfert | ba65c16 | 2015-02-24 11:45:21 +0000 | [diff] [blame] | 1096 | bool ScopDetection::isNonAffineSubRegion(const Region *SubR, |
| 1097 | const Region *ScopR) const { |
| 1098 | return NonAffineSubRegionMap.lookup(ScopR).count(SubR); |
| 1099 | } |
| 1100 | |
Johannes Doerfert | f3e98f4 | 2015-04-12 22:52:20 +0000 | [diff] [blame] | 1101 | const ScopDetection::BoxedLoopsSetTy * |
| 1102 | ScopDetection::getBoxedLoops(const Region *R) const { |
| 1103 | auto BLMIt = BoxedLoopsMap.find(R); |
| 1104 | if (BLMIt == BoxedLoopsMap.end()) |
| 1105 | return nullptr; |
| 1106 | return &BLMIt->second; |
| 1107 | } |
| 1108 | |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 1109 | void polly::ScopDetection::verifyRegion(const Region &R) const { |
| 1110 | assert(isMaxRegionInScop(R) && "Expect R is a valid region."); |
Johannes Doerfert | f3e98f4 | 2015-04-12 22:52:20 +0000 | [diff] [blame] | 1111 | |
| 1112 | BoxedLoopsSetTy DummyBoxedLoopsSet; |
Johannes Doerfert | ba65c16 | 2015-02-24 11:45:21 +0000 | [diff] [blame] | 1113 | NonAffineSubRegionSetTy DummyNonAffineSubRegionSet; |
| 1114 | DetectionContext Context(const_cast<Region &>(R), *AA, |
Johannes Doerfert | f3e98f4 | 2015-04-12 22:52:20 +0000 | [diff] [blame] | 1115 | DummyNonAffineSubRegionSet, DummyBoxedLoopsSet, |
| 1116 | true /*verifying*/); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 1117 | isValidRegion(Context); |
| 1118 | } |
| 1119 | |
| 1120 | void polly::ScopDetection::verifyAnalysis() const { |
Tobias Grosser | a168993 | 2014-02-18 18:49:49 +0000 | [diff] [blame] | 1121 | if (!VerifyScops) |
| 1122 | return; |
| 1123 | |
Tobias Grosser | 2610889 | 2014-04-02 20:18:19 +0000 | [diff] [blame] | 1124 | for (const Region *R : ValidRegions) |
Tobias Grosser | 00dc309 | 2014-03-02 12:02:46 +0000 | [diff] [blame] | 1125 | verifyRegion(*R); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 1126 | } |
| 1127 | |
| 1128 | void ScopDetection::getAnalysisUsage(AnalysisUsage &AU) const { |
Chandler Carruth | f557987 | 2015-01-17 14:16:56 +0000 | [diff] [blame] | 1129 | AU.addRequired<LoopInfoWrapperPass>(); |
Tobias Grosser | c5bcf24 | 2015-08-17 10:57:08 +0000 | [diff] [blame] | 1130 | AU.addRequired<ScalarEvolutionWrapperPass>(); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 1131 | // We also need AA and RegionInfo when we are verifying analysis. |
Chandler Carruth | 66ef16b | 2015-09-09 22:13:56 +0000 | [diff] [blame^] | 1132 | AU.addRequiredTransitive<AAResultsWrapperPass>(); |
Matt Arsenault | 8ca3681 | 2014-07-19 18:40:17 +0000 | [diff] [blame] | 1133 | AU.addRequiredTransitive<RegionInfoPass>(); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 1134 | AU.setPreservesAll(); |
| 1135 | } |
| 1136 | |
Tobias Grosser | 4d96c8d | 2013-03-23 01:05:07 +0000 | [diff] [blame] | 1137 | void ScopDetection::print(raw_ostream &OS, const Module *) const { |
Tobias Grosser | 2610889 | 2014-04-02 20:18:19 +0000 | [diff] [blame] | 1138 | for (const Region *R : ValidRegions) |
Tobias Grosser | 00dc309 | 2014-03-02 12:02:46 +0000 | [diff] [blame] | 1139 | OS << "Valid Region for Scop: " << R->getNameStr() << '\n'; |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 1140 | |
| 1141 | OS << "\n"; |
| 1142 | } |
| 1143 | |
| 1144 | void ScopDetection::releaseMemory() { |
| 1145 | ValidRegions.clear(); |
Andreas Simbuerger | 4870e09 | 2014-05-24 09:25:01 +0000 | [diff] [blame] | 1146 | RejectLogs.clear(); |
Johannes Doerfert | ba65c16 | 2015-02-24 11:45:21 +0000 | [diff] [blame] | 1147 | NonAffineSubRegionMap.clear(); |
Tobias Grosser | 4b6aa6e | 2015-04-18 11:01:25 +0000 | [diff] [blame] | 1148 | InsnToMemAcc.clear(); |
Andreas Simbuerger | 4870e09 | 2014-05-24 09:25:01 +0000 | [diff] [blame] | 1149 | |
Hongbin Zheng | 94c5df1 | 2011-05-06 02:38:20 +0000 | [diff] [blame] | 1150 | // Do not clear the invalid function set. |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 1151 | } |
| 1152 | |
| 1153 | char ScopDetection::ID = 0; |
| 1154 | |
Tobias Grosser | 4d96c8d | 2013-03-23 01:05:07 +0000 | [diff] [blame] | 1155 | Pass *polly::createScopDetectionPass() { return new ScopDetection(); } |
| 1156 | |
Tobias Grosser | 73600b8 | 2011-10-08 00:30:40 +0000 | [diff] [blame] | 1157 | INITIALIZE_PASS_BEGIN(ScopDetection, "polly-detect", |
| 1158 | "Polly - Detect static control parts (SCoPs)", false, |
Tobias Grosser | 4d96c8d | 2013-03-23 01:05:07 +0000 | [diff] [blame] | 1159 | false); |
Chandler Carruth | 66ef16b | 2015-09-09 22:13:56 +0000 | [diff] [blame^] | 1160 | INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass); |
Chandler Carruth | f557987 | 2015-01-17 14:16:56 +0000 | [diff] [blame] | 1161 | INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass); |
Matt Arsenault | 8ca3681 | 2014-07-19 18:40:17 +0000 | [diff] [blame] | 1162 | INITIALIZE_PASS_DEPENDENCY(RegionInfoPass); |
Tobias Grosser | c5bcf24 | 2015-08-17 10:57:08 +0000 | [diff] [blame] | 1163 | INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass); |
Tobias Grosser | 73600b8 | 2011-10-08 00:30:40 +0000 | [diff] [blame] | 1164 | INITIALIZE_PASS_END(ScopDetection, "polly-detect", |
| 1165 | "Polly - Detect static control parts (SCoPs)", false, false) |