| File: | src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Analysis/LoopNestAnalysis.cpp |
| Warning: | line 87, column 56 Called C++ object pointer is null |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
| 1 | //===- LoopNestAnalysis.cpp - Loop Nest Analysis --------------------------==// | ||||
| 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 | /// \file | ||||
| 10 | /// The implementation for the loop nest analysis. | ||||
| 11 | /// | ||||
| 12 | //===----------------------------------------------------------------------===// | ||||
| 13 | |||||
| 14 | #include "llvm/Analysis/LoopNestAnalysis.h" | ||||
| 15 | #include "llvm/ADT/BreadthFirstIterator.h" | ||||
| 16 | #include "llvm/ADT/Statistic.h" | ||||
| 17 | #include "llvm/Analysis/PostDominators.h" | ||||
| 18 | #include "llvm/Analysis/ValueTracking.h" | ||||
| 19 | |||||
| 20 | using namespace llvm; | ||||
| 21 | |||||
| 22 | #define DEBUG_TYPE"loopnest" "loopnest" | ||||
| 23 | #ifndef NDEBUG1 | ||||
| 24 | static const char *VerboseDebug = DEBUG_TYPE"loopnest" "-verbose"; | ||||
| 25 | #endif | ||||
| 26 | |||||
| 27 | /// Determine whether the loops structure violates basic requirements for | ||||
| 28 | /// perfect nesting: | ||||
| 29 | /// - the inner loop should be the outer loop's only child | ||||
| 30 | /// - the outer loop header should 'flow' into the inner loop preheader | ||||
| 31 | /// or jump around the inner loop to the outer loop latch | ||||
| 32 | /// - if the inner loop latch exits the inner loop, it should 'flow' into | ||||
| 33 | /// the outer loop latch. | ||||
| 34 | /// Returns true if the loop structure satisfies the basic requirements and | ||||
| 35 | /// false otherwise. | ||||
| 36 | static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop, | ||||
| 37 | ScalarEvolution &SE); | ||||
| 38 | |||||
| 39 | //===----------------------------------------------------------------------===// | ||||
| 40 | // LoopNest implementation | ||||
| 41 | // | ||||
| 42 | |||||
| 43 | LoopNest::LoopNest(Loop &Root, ScalarEvolution &SE) | ||||
| 44 | : MaxPerfectDepth(getMaxPerfectDepth(Root, SE)) { | ||||
| 45 | append_range(Loops, breadth_first(&Root)); | ||||
| 46 | } | ||||
| 47 | |||||
| 48 | std::unique_ptr<LoopNest> LoopNest::getLoopNest(Loop &Root, | ||||
| 49 | ScalarEvolution &SE) { | ||||
| 50 | return std::make_unique<LoopNest>(Root, SE); | ||||
| 51 | } | ||||
| 52 | |||||
| 53 | bool LoopNest::arePerfectlyNested(const Loop &OuterLoop, const Loop &InnerLoop, | ||||
| 54 | ScalarEvolution &SE) { | ||||
| 55 | assert(!OuterLoop.isInnermost() && "Outer loop should have subloops")((void)0); | ||||
| 56 | assert(!InnerLoop.isOutermost() && "Inner loop should have a parent")((void)0); | ||||
| 57 | LLVM_DEBUG(dbgs() << "Checking whether loop '" << OuterLoop.getName()do { } while (false) | ||||
| 58 | << "' and '" << InnerLoop.getName()do { } while (false) | ||||
| 59 | << "' are perfectly nested.\n")do { } while (false); | ||||
| 60 | |||||
| 61 | // Determine whether the loops structure satisfies the following requirements: | ||||
| 62 | // - the inner loop should be the outer loop's only child | ||||
| 63 | // - the outer loop header should 'flow' into the inner loop preheader | ||||
| 64 | // or jump around the inner loop to the outer loop latch | ||||
| 65 | // - if the inner loop latch exits the inner loop, it should 'flow' into | ||||
| 66 | // the outer loop latch. | ||||
| 67 | if (!checkLoopsStructure(OuterLoop, InnerLoop, SE)) { | ||||
| 68 | LLVM_DEBUG(dbgs() << "Not perfectly nested: invalid loop structure.\n")do { } while (false); | ||||
| 69 | return false; | ||||
| 70 | } | ||||
| 71 | |||||
| 72 | // Bail out if we cannot retrieve the outer loop bounds. | ||||
| 73 | auto OuterLoopLB = OuterLoop.getBounds(SE); | ||||
| 74 | if (OuterLoopLB == None) { | ||||
| 75 | LLVM_DEBUG(dbgs() << "Cannot compute loop bounds of OuterLoop: "do { } while (false) | ||||
| 76 | << OuterLoop << "\n";)do { } while (false); | ||||
| 77 | return false; | ||||
| 78 | } | ||||
| 79 | |||||
| 80 | // Identify the outer loop latch comparison instruction. | ||||
| 81 | const BasicBlock *Latch = OuterLoop.getLoopLatch(); | ||||
| 82 | assert(Latch && "Expecting a valid loop latch")((void)0); | ||||
| 83 | const BranchInst *BI = dyn_cast<BranchInst>(Latch->getTerminator()); | ||||
| 84 | assert(BI && BI->isConditional() &&((void)0) | ||||
| 85 | "Expecting loop latch terminator to be a branch instruction")((void)0); | ||||
| 86 | |||||
| 87 | const CmpInst *OuterLoopLatchCmp = dyn_cast<CmpInst>(BI->getCondition()); | ||||
| |||||
| 88 | DEBUG_WITH_TYPE(do { } while (false) | ||||
| 89 | VerboseDebug, if (OuterLoopLatchCmp) {do { } while (false) | ||||
| 90 | dbgs() << "Outer loop latch compare instruction: " << *OuterLoopLatchCmpdo { } while (false) | ||||
| 91 | << "\n";do { } while (false) | ||||
| 92 | })do { } while (false); | ||||
| 93 | |||||
| 94 | // Identify the inner loop guard instruction. | ||||
| 95 | BranchInst *InnerGuard = InnerLoop.getLoopGuardBranch(); | ||||
| 96 | const CmpInst *InnerLoopGuardCmp = | ||||
| 97 | (InnerGuard) ? dyn_cast<CmpInst>(InnerGuard->getCondition()) : nullptr; | ||||
| 98 | |||||
| 99 | DEBUG_WITH_TYPE(do { } while (false) | ||||
| 100 | VerboseDebug, if (InnerLoopGuardCmp) {do { } while (false) | ||||
| 101 | dbgs() << "Inner loop guard compare instruction: " << *InnerLoopGuardCmpdo { } while (false) | ||||
| 102 | << "\n";do { } while (false) | ||||
| 103 | })do { } while (false); | ||||
| 104 | |||||
| 105 | // Determine whether instructions in a basic block are one of: | ||||
| 106 | // - the inner loop guard comparison | ||||
| 107 | // - the outer loop latch comparison | ||||
| 108 | // - the outer loop induction variable increment | ||||
| 109 | // - a phi node, a cast or a branch | ||||
| 110 | auto containsOnlySafeInstructions = [&](const BasicBlock &BB) { | ||||
| 111 | return llvm::all_of(BB, [&](const Instruction &I) { | ||||
| 112 | bool isAllowed = isSafeToSpeculativelyExecute(&I) || isa<PHINode>(I) || | ||||
| 113 | isa<BranchInst>(I); | ||||
| 114 | if (!isAllowed) { | ||||
| 115 | DEBUG_WITH_TYPE(VerboseDebug, {do { } while (false) | ||||
| 116 | dbgs() << "Instruction: " << I << "\nin basic block: " << BBdo { } while (false) | ||||
| 117 | << " is considered unsafe.\n";do { } while (false) | ||||
| 118 | })do { } while (false); | ||||
| 119 | return false; | ||||
| 120 | } | ||||
| 121 | |||||
| 122 | // The only binary instruction allowed is the outer loop step instruction, | ||||
| 123 | // the only comparison instructions allowed are the inner loop guard | ||||
| 124 | // compare instruction and the outer loop latch compare instruction. | ||||
| 125 | if ((isa<BinaryOperator>(I) && &I != &OuterLoopLB->getStepInst()) || | ||||
| 126 | (isa<CmpInst>(I) && &I != OuterLoopLatchCmp && | ||||
| 127 | &I != InnerLoopGuardCmp)) { | ||||
| 128 | DEBUG_WITH_TYPE(VerboseDebug, {do { } while (false) | ||||
| 129 | dbgs() << "Instruction: " << I << "\nin basic block:" << BBdo { } while (false) | ||||
| 130 | << "is unsafe.\n";do { } while (false) | ||||
| 131 | })do { } while (false); | ||||
| 132 | return false; | ||||
| 133 | } | ||||
| 134 | return true; | ||||
| 135 | }); | ||||
| 136 | }; | ||||
| 137 | |||||
| 138 | // Check the code surrounding the inner loop for instructions that are deemed | ||||
| 139 | // unsafe. | ||||
| 140 | const BasicBlock *OuterLoopHeader = OuterLoop.getHeader(); | ||||
| 141 | const BasicBlock *OuterLoopLatch = OuterLoop.getLoopLatch(); | ||||
| 142 | const BasicBlock *InnerLoopPreHeader = InnerLoop.getLoopPreheader(); | ||||
| 143 | |||||
| 144 | if (!containsOnlySafeInstructions(*OuterLoopHeader) || | ||||
| 145 | !containsOnlySafeInstructions(*OuterLoopLatch) || | ||||
| 146 | (InnerLoopPreHeader != OuterLoopHeader && | ||||
| 147 | !containsOnlySafeInstructions(*InnerLoopPreHeader)) || | ||||
| 148 | !containsOnlySafeInstructions(*InnerLoop.getExitBlock())) { | ||||
| 149 | LLVM_DEBUG(dbgs() << "Not perfectly nested: code surrounding inner loop is "do { } while (false) | ||||
| 150 | "unsafe\n";)do { } while (false); | ||||
| 151 | return false; | ||||
| 152 | } | ||||
| 153 | |||||
| 154 | LLVM_DEBUG(dbgs() << "Loop '" << OuterLoop.getName() << "' and '"do { } while (false) | ||||
| 155 | << InnerLoop.getName() << "' are perfectly nested.\n")do { } while (false); | ||||
| 156 | |||||
| 157 | return true; | ||||
| 158 | } | ||||
| 159 | |||||
| 160 | SmallVector<LoopVectorTy, 4> | ||||
| 161 | LoopNest::getPerfectLoops(ScalarEvolution &SE) const { | ||||
| 162 | SmallVector<LoopVectorTy, 4> LV; | ||||
| 163 | LoopVectorTy PerfectNest; | ||||
| 164 | |||||
| 165 | for (Loop *L : depth_first(const_cast<Loop *>(Loops.front()))) { | ||||
| 166 | if (PerfectNest.empty()) | ||||
| |||||
| 167 | PerfectNest.push_back(L); | ||||
| 168 | |||||
| 169 | auto &SubLoops = L->getSubLoops(); | ||||
| 170 | if (SubLoops.size() == 1 && arePerfectlyNested(*L, *SubLoops.front(), SE)) { | ||||
| 171 | PerfectNest.push_back(SubLoops.front()); | ||||
| 172 | } else { | ||||
| 173 | LV.push_back(PerfectNest); | ||||
| 174 | PerfectNest.clear(); | ||||
| 175 | } | ||||
| 176 | } | ||||
| 177 | |||||
| 178 | return LV; | ||||
| 179 | } | ||||
| 180 | |||||
| 181 | unsigned LoopNest::getMaxPerfectDepth(const Loop &Root, ScalarEvolution &SE) { | ||||
| 182 | LLVM_DEBUG(dbgs() << "Get maximum perfect depth of loop nest rooted by loop '"do { } while (false) | ||||
| 183 | << Root.getName() << "'\n")do { } while (false); | ||||
| 184 | |||||
| 185 | const Loop *CurrentLoop = &Root; | ||||
| 186 | const auto *SubLoops = &CurrentLoop->getSubLoops(); | ||||
| 187 | unsigned CurrentDepth = 1; | ||||
| 188 | |||||
| 189 | while (SubLoops->size() == 1) { | ||||
| 190 | const Loop *InnerLoop = SubLoops->front(); | ||||
| 191 | if (!arePerfectlyNested(*CurrentLoop, *InnerLoop, SE)) { | ||||
| 192 | LLVM_DEBUG({do { } while (false) | ||||
| 193 | dbgs() << "Not a perfect nest: loop '" << CurrentLoop->getName()do { } while (false) | ||||
| 194 | << "' is not perfectly nested with loop '"do { } while (false) | ||||
| 195 | << InnerLoop->getName() << "'\n";do { } while (false) | ||||
| 196 | })do { } while (false); | ||||
| 197 | break; | ||||
| 198 | } | ||||
| 199 | |||||
| 200 | CurrentLoop = InnerLoop; | ||||
| 201 | SubLoops = &CurrentLoop->getSubLoops(); | ||||
| 202 | ++CurrentDepth; | ||||
| 203 | } | ||||
| 204 | |||||
| 205 | return CurrentDepth; | ||||
| 206 | } | ||||
| 207 | |||||
| 208 | const BasicBlock &LoopNest::skipEmptyBlockUntil(const BasicBlock *From, | ||||
| 209 | const BasicBlock *End, | ||||
| 210 | bool CheckUniquePred) { | ||||
| 211 | assert(From && "Expecting valid From")((void)0); | ||||
| 212 | assert(End && "Expecting valid End")((void)0); | ||||
| 213 | |||||
| 214 | if (From == End || !From->getUniqueSuccessor()) | ||||
| 215 | return *From; | ||||
| 216 | |||||
| 217 | auto IsEmpty = [](const BasicBlock *BB) { | ||||
| 218 | return (BB->getInstList().size() == 1); | ||||
| 219 | }; | ||||
| 220 | |||||
| 221 | // Visited is used to avoid running into an infinite loop. | ||||
| 222 | SmallPtrSet<const BasicBlock *, 4> Visited; | ||||
| 223 | const BasicBlock *BB = From->getUniqueSuccessor(); | ||||
| 224 | const BasicBlock *PredBB = From; | ||||
| 225 | while (BB && BB != End && IsEmpty(BB) && !Visited.count(BB) && | ||||
| 226 | (!CheckUniquePred || BB->getUniquePredecessor())) { | ||||
| 227 | Visited.insert(BB); | ||||
| 228 | PredBB = BB; | ||||
| 229 | BB = BB->getUniqueSuccessor(); | ||||
| 230 | } | ||||
| 231 | |||||
| 232 | return (BB == End) ? *End : *PredBB; | ||||
| 233 | } | ||||
| 234 | |||||
| 235 | static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop, | ||||
| 236 | ScalarEvolution &SE) { | ||||
| 237 | // The inner loop must be the only outer loop's child. | ||||
| 238 | if ((OuterLoop.getSubLoops().size() != 1) || | ||||
| 239 | (InnerLoop.getParentLoop() != &OuterLoop)) | ||||
| 240 | return false; | ||||
| 241 | |||||
| 242 | // We expect loops in normal form which have a preheader, header, latch... | ||||
| 243 | if (!OuterLoop.isLoopSimplifyForm() || !InnerLoop.isLoopSimplifyForm()) | ||||
| 244 | return false; | ||||
| 245 | |||||
| 246 | const BasicBlock *OuterLoopHeader = OuterLoop.getHeader(); | ||||
| 247 | const BasicBlock *OuterLoopLatch = OuterLoop.getLoopLatch(); | ||||
| 248 | const BasicBlock *InnerLoopPreHeader = InnerLoop.getLoopPreheader(); | ||||
| 249 | const BasicBlock *InnerLoopLatch = InnerLoop.getLoopLatch(); | ||||
| 250 | const BasicBlock *InnerLoopExit = InnerLoop.getExitBlock(); | ||||
| 251 | |||||
| 252 | // We expect rotated loops. The inner loop should have a single exit block. | ||||
| 253 | if (OuterLoop.getExitingBlock() != OuterLoopLatch || | ||||
| 254 | InnerLoop.getExitingBlock() != InnerLoopLatch || !InnerLoopExit) | ||||
| 255 | return false; | ||||
| 256 | |||||
| 257 | // Returns whether the block `ExitBlock` contains at least one LCSSA Phi node. | ||||
| 258 | auto ContainsLCSSAPhi = [](const BasicBlock &ExitBlock) { | ||||
| 259 | return any_of(ExitBlock.phis(), [](const PHINode &PN) { | ||||
| 260 | return PN.getNumIncomingValues() == 1; | ||||
| 261 | }); | ||||
| 262 | }; | ||||
| 263 | |||||
| 264 | // Returns whether the block `BB` qualifies for being an extra Phi block. The | ||||
| 265 | // extra Phi block is the additional block inserted after the exit block of an | ||||
| 266 | // "guarded" inner loop which contains "only" Phi nodes corresponding to the | ||||
| 267 | // LCSSA Phi nodes in the exit block. | ||||
| 268 | auto IsExtraPhiBlock = [&](const BasicBlock &BB) { | ||||
| 269 | return BB.getFirstNonPHI() == BB.getTerminator() && | ||||
| 270 | all_of(BB.phis(), [&](const PHINode &PN) { | ||||
| 271 | return all_of(PN.blocks(), [&](const BasicBlock *IncomingBlock) { | ||||
| 272 | return IncomingBlock == InnerLoopExit || | ||||
| 273 | IncomingBlock == OuterLoopHeader; | ||||
| 274 | }); | ||||
| 275 | }); | ||||
| 276 | }; | ||||
| 277 | |||||
| 278 | const BasicBlock *ExtraPhiBlock = nullptr; | ||||
| 279 | // Ensure the only branch that may exist between the loops is the inner loop | ||||
| 280 | // guard. | ||||
| 281 | if (OuterLoopHeader != InnerLoopPreHeader) { | ||||
| 282 | const BasicBlock &SingleSucc = | ||||
| 283 | LoopNest::skipEmptyBlockUntil(OuterLoopHeader, InnerLoopPreHeader); | ||||
| 284 | |||||
| 285 | // no conditional branch present | ||||
| 286 | if (&SingleSucc != InnerLoopPreHeader) { | ||||
| 287 | const BranchInst *BI = dyn_cast<BranchInst>(SingleSucc.getTerminator()); | ||||
| 288 | |||||
| 289 | if (!BI || BI != InnerLoop.getLoopGuardBranch()) | ||||
| 290 | return false; | ||||
| 291 | |||||
| 292 | bool InnerLoopExitContainsLCSSA = ContainsLCSSAPhi(*InnerLoopExit); | ||||
| 293 | |||||
| 294 | // The successors of the inner loop guard should be the inner loop | ||||
| 295 | // preheader or the outer loop latch possibly through empty blocks. | ||||
| 296 | for (const BasicBlock *Succ : BI->successors()) { | ||||
| 297 | const BasicBlock *PotentialInnerPreHeader = Succ; | ||||
| 298 | const BasicBlock *PotentialOuterLatch = Succ; | ||||
| 299 | |||||
| 300 | // Ensure the inner loop guard successor is empty before skipping | ||||
| 301 | // blocks. | ||||
| 302 | if (Succ->getInstList().size() == 1) { | ||||
| 303 | PotentialInnerPreHeader = | ||||
| 304 | &LoopNest::skipEmptyBlockUntil(Succ, InnerLoopPreHeader); | ||||
| 305 | PotentialOuterLatch = | ||||
| 306 | &LoopNest::skipEmptyBlockUntil(Succ, OuterLoopLatch); | ||||
| 307 | } | ||||
| 308 | |||||
| 309 | if (PotentialInnerPreHeader == InnerLoopPreHeader) | ||||
| 310 | continue; | ||||
| 311 | if (PotentialOuterLatch == OuterLoopLatch) | ||||
| 312 | continue; | ||||
| 313 | |||||
| 314 | // If `InnerLoopExit` contains LCSSA Phi instructions, additional block | ||||
| 315 | // may be inserted before the `OuterLoopLatch` to which `BI` jumps. The | ||||
| 316 | // loops are still considered perfectly nested if the extra block only | ||||
| 317 | // contains Phi instructions from InnerLoopExit and OuterLoopHeader. | ||||
| 318 | if (InnerLoopExitContainsLCSSA && IsExtraPhiBlock(*Succ) && | ||||
| 319 | Succ->getSingleSuccessor() == OuterLoopLatch) { | ||||
| 320 | // Points to the extra block so that we can reference it later in the | ||||
| 321 | // final check. We can also conclude that the inner loop is | ||||
| 322 | // guarded and there exists LCSSA Phi node in the exit block later if | ||||
| 323 | // we see a non-null `ExtraPhiBlock`. | ||||
| 324 | ExtraPhiBlock = Succ; | ||||
| 325 | continue; | ||||
| 326 | } | ||||
| 327 | |||||
| 328 | DEBUG_WITH_TYPE(VerboseDebug, {do { } while (false) | ||||
| 329 | dbgs() << "Inner loop guard successor " << Succ->getName()do { } while (false) | ||||
| 330 | << " doesn't lead to inner loop preheader or "do { } while (false) | ||||
| 331 | "outer loop latch.\n";do { } while (false) | ||||
| 332 | })do { } while (false); | ||||
| 333 | return false; | ||||
| 334 | } | ||||
| 335 | } | ||||
| 336 | } | ||||
| 337 | |||||
| 338 | // Ensure the inner loop exit block lead to the outer loop latch possibly | ||||
| 339 | // through empty blocks. | ||||
| 340 | if ((!ExtraPhiBlock
| ||||
| 341 | &LoopNest::skipEmptyBlockUntil(InnerLoop.getExitBlock(), | ||||
| 342 | ExtraPhiBlock) != ExtraPhiBlock) && | ||||
| 343 | (&LoopNest::skipEmptyBlockUntil(InnerLoop.getExitBlock(), | ||||
| 344 | OuterLoopLatch) != OuterLoopLatch)) { | ||||
| 345 | DEBUG_WITH_TYPE(do { } while (false) | ||||
| 346 | VerboseDebug,do { } while (false) | ||||
| 347 | dbgs() << "Inner loop exit block " << *InnerLoopExitdo { } while (false) | ||||
| 348 | << " does not directly lead to the outer loop latch.\n";)do { } while (false); | ||||
| 349 | return false; | ||||
| 350 | } | ||||
| 351 | |||||
| 352 | return true; | ||||
| 353 | } | ||||
| 354 | |||||
| 355 | AnalysisKey LoopNestAnalysis::Key; | ||||
| 356 | |||||
| 357 | raw_ostream &llvm::operator<<(raw_ostream &OS, const LoopNest &LN) { | ||||
| 358 | OS << "IsPerfect="; | ||||
| 359 | if (LN.getMaxPerfectDepth() == LN.getNestDepth()) | ||||
| 360 | OS << "true"; | ||||
| 361 | else | ||||
| 362 | OS << "false"; | ||||
| 363 | OS << ", Depth=" << LN.getNestDepth(); | ||||
| 364 | OS << ", OutermostLoop: " << LN.getOutermostLoop().getName(); | ||||
| 365 | OS << ", Loops: ( "; | ||||
| 366 | for (const Loop *L : LN.getLoops()) | ||||
| 367 | OS << L->getName() << " "; | ||||
| 368 | OS << ")"; | ||||
| 369 | |||||
| 370 | return OS; | ||||
| 371 | } | ||||
| 372 | |||||
| 373 | //===----------------------------------------------------------------------===// | ||||
| 374 | // LoopNestPrinterPass implementation | ||||
| 375 | // | ||||
| 376 | |||||
| 377 | PreservedAnalyses LoopNestPrinterPass::run(Loop &L, LoopAnalysisManager &AM, | ||||
| 378 | LoopStandardAnalysisResults &AR, | ||||
| 379 | LPMUpdater &U) { | ||||
| 380 | if (auto LN = LoopNest::getLoopNest(L, AR.SE)) | ||||
| 381 | OS << *LN << "\n"; | ||||
| 382 | |||||
| 383 | return PreservedAnalyses::all(); | ||||
| 384 | } |
| 1 | //===- Optional.h - Simple variant for passing optional values --*- C++ -*-===// |
| 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 | // This file provides Optional, a template class modeled in the spirit of |
| 10 | // OCaml's 'opt' variant. The idea is to strongly type whether or not |
| 11 | // a value can be optional. |
| 12 | // |
| 13 | //===----------------------------------------------------------------------===// |
| 14 | |
| 15 | #ifndef LLVM_ADT_OPTIONAL_H |
| 16 | #define LLVM_ADT_OPTIONAL_H |
| 17 | |
| 18 | #include "llvm/ADT/Hashing.h" |
| 19 | #include "llvm/ADT/None.h" |
| 20 | #include "llvm/ADT/STLForwardCompat.h" |
| 21 | #include "llvm/Support/Compiler.h" |
| 22 | #include "llvm/Support/type_traits.h" |
| 23 | #include <cassert> |
| 24 | #include <memory> |
| 25 | #include <new> |
| 26 | #include <utility> |
| 27 | |
| 28 | namespace llvm { |
| 29 | |
| 30 | class raw_ostream; |
| 31 | |
| 32 | namespace optional_detail { |
| 33 | |
| 34 | /// Storage for any type. |
| 35 | // |
| 36 | // The specialization condition intentionally uses |
| 37 | // llvm::is_trivially_copy_constructible instead of |
| 38 | // std::is_trivially_copy_constructible. GCC versions prior to 7.4 may |
| 39 | // instantiate the copy constructor of `T` when |
| 40 | // std::is_trivially_copy_constructible is instantiated. This causes |
| 41 | // compilation to fail if we query the trivially copy constructible property of |
| 42 | // a class which is not copy constructible. |
| 43 | // |
| 44 | // The current implementation of OptionalStorage insists that in order to use |
| 45 | // the trivial specialization, the value_type must be trivially copy |
| 46 | // constructible and trivially copy assignable due to =default implementations |
| 47 | // of the copy/move constructor/assignment. It does not follow that this is |
| 48 | // necessarily the case std::is_trivially_copyable is true (hence the expanded |
| 49 | // specialization condition). |
| 50 | // |
| 51 | // The move constructible / assignable conditions emulate the remaining behavior |
| 52 | // of std::is_trivially_copyable. |
| 53 | template <typename T, bool = (llvm::is_trivially_copy_constructible<T>::value && |
| 54 | std::is_trivially_copy_assignable<T>::value && |
| 55 | (std::is_trivially_move_constructible<T>::value || |
| 56 | !std::is_move_constructible<T>::value) && |
| 57 | (std::is_trivially_move_assignable<T>::value || |
| 58 | !std::is_move_assignable<T>::value))> |
| 59 | class OptionalStorage { |
| 60 | union { |
| 61 | char empty; |
| 62 | T value; |
| 63 | }; |
| 64 | bool hasVal; |
| 65 | |
| 66 | public: |
| 67 | ~OptionalStorage() { reset(); } |
| 68 | |
| 69 | constexpr OptionalStorage() noexcept : empty(), hasVal(false) {} |
| 70 | |
| 71 | constexpr OptionalStorage(OptionalStorage const &other) : OptionalStorage() { |
| 72 | if (other.hasValue()) { |
| 73 | emplace(other.value); |
| 74 | } |
| 75 | } |
| 76 | constexpr OptionalStorage(OptionalStorage &&other) : OptionalStorage() { |
| 77 | if (other.hasValue()) { |
| 78 | emplace(std::move(other.value)); |
| 79 | } |
| 80 | } |
| 81 | |
| 82 | template <class... Args> |
| 83 | constexpr explicit OptionalStorage(in_place_t, Args &&... args) |
| 84 | : value(std::forward<Args>(args)...), hasVal(true) {} |
| 85 | |
| 86 | void reset() noexcept { |
| 87 | if (hasVal) { |
| 88 | value.~T(); |
| 89 | hasVal = false; |
| 90 | } |
| 91 | } |
| 92 | |
| 93 | constexpr bool hasValue() const noexcept { return hasVal; } |
| 94 | |
| 95 | T &getValue() LLVM_LVALUE_FUNCTION& noexcept { |
| 96 | assert(hasVal)((void)0); |
| 97 | return value; |
| 98 | } |
| 99 | constexpr T const &getValue() const LLVM_LVALUE_FUNCTION& noexcept { |
| 100 | assert(hasVal)((void)0); |
| 101 | return value; |
| 102 | } |
| 103 | #if LLVM_HAS_RVALUE_REFERENCE_THIS1 |
| 104 | T &&getValue() && noexcept { |
| 105 | assert(hasVal)((void)0); |
| 106 | return std::move(value); |
| 107 | } |
| 108 | #endif |
| 109 | |
| 110 | template <class... Args> void emplace(Args &&... args) { |
| 111 | reset(); |
| 112 | ::new ((void *)std::addressof(value)) T(std::forward<Args>(args)...); |
| 113 | hasVal = true; |
| 114 | } |
| 115 | |
| 116 | OptionalStorage &operator=(T const &y) { |
| 117 | if (hasValue()) { |
| 118 | value = y; |
| 119 | } else { |
| 120 | ::new ((void *)std::addressof(value)) T(y); |
| 121 | hasVal = true; |
| 122 | } |
| 123 | return *this; |
| 124 | } |
| 125 | OptionalStorage &operator=(T &&y) { |
| 126 | if (hasValue()) { |
| 127 | value = std::move(y); |
| 128 | } else { |
| 129 | ::new ((void *)std::addressof(value)) T(std::move(y)); |
| 130 | hasVal = true; |
| 131 | } |
| 132 | return *this; |
| 133 | } |
| 134 | |
| 135 | OptionalStorage &operator=(OptionalStorage const &other) { |
| 136 | if (other.hasValue()) { |
| 137 | if (hasValue()) { |
| 138 | value = other.value; |
| 139 | } else { |
| 140 | ::new ((void *)std::addressof(value)) T(other.value); |
| 141 | hasVal = true; |
| 142 | } |
| 143 | } else { |
| 144 | reset(); |
| 145 | } |
| 146 | return *this; |
| 147 | } |
| 148 | |
| 149 | OptionalStorage &operator=(OptionalStorage &&other) { |
| 150 | if (other.hasValue()) { |
| 151 | if (hasValue()) { |
| 152 | value = std::move(other.value); |
| 153 | } else { |
| 154 | ::new ((void *)std::addressof(value)) T(std::move(other.value)); |
| 155 | hasVal = true; |
| 156 | } |
| 157 | } else { |
| 158 | reset(); |
| 159 | } |
| 160 | return *this; |
| 161 | } |
| 162 | }; |
| 163 | |
| 164 | template <typename T> class OptionalStorage<T, true> { |
| 165 | union { |
| 166 | char empty; |
| 167 | T value; |
| 168 | }; |
| 169 | bool hasVal = false; |
| 170 | |
| 171 | public: |
| 172 | ~OptionalStorage() = default; |
| 173 | |
| 174 | constexpr OptionalStorage() noexcept : empty{} {} |
| 175 | |
| 176 | constexpr OptionalStorage(OptionalStorage const &other) = default; |
| 177 | constexpr OptionalStorage(OptionalStorage &&other) = default; |
| 178 | |
| 179 | OptionalStorage &operator=(OptionalStorage const &other) = default; |
| 180 | OptionalStorage &operator=(OptionalStorage &&other) = default; |
| 181 | |
| 182 | template <class... Args> |
| 183 | constexpr explicit OptionalStorage(in_place_t, Args &&... args) |
| 184 | : value(std::forward<Args>(args)...), hasVal(true) {} |
| 185 | |
| 186 | void reset() noexcept { |
| 187 | if (hasVal) { |
| 188 | value.~T(); |
| 189 | hasVal = false; |
| 190 | } |
| 191 | } |
| 192 | |
| 193 | constexpr bool hasValue() const noexcept { return hasVal; } |
| 194 | |
| 195 | T &getValue() LLVM_LVALUE_FUNCTION& noexcept { |
| 196 | assert(hasVal)((void)0); |
| 197 | return value; |
| 198 | } |
| 199 | constexpr T const &getValue() const LLVM_LVALUE_FUNCTION& noexcept { |
| 200 | assert(hasVal)((void)0); |
| 201 | return value; |
| 202 | } |
| 203 | #if LLVM_HAS_RVALUE_REFERENCE_THIS1 |
| 204 | T &&getValue() && noexcept { |
| 205 | assert(hasVal)((void)0); |
| 206 | return std::move(value); |
| 207 | } |
| 208 | #endif |
| 209 | |
| 210 | template <class... Args> void emplace(Args &&... args) { |
| 211 | reset(); |
| 212 | ::new ((void *)std::addressof(value)) T(std::forward<Args>(args)...); |
| 213 | hasVal = true; |
| 214 | } |
| 215 | |
| 216 | OptionalStorage &operator=(T const &y) { |
| 217 | if (hasValue()) { |
| 218 | value = y; |
| 219 | } else { |
| 220 | ::new ((void *)std::addressof(value)) T(y); |
| 221 | hasVal = true; |
| 222 | } |
| 223 | return *this; |
| 224 | } |
| 225 | OptionalStorage &operator=(T &&y) { |
| 226 | if (hasValue()) { |
| 227 | value = std::move(y); |
| 228 | } else { |
| 229 | ::new ((void *)std::addressof(value)) T(std::move(y)); |
| 230 | hasVal = true; |
| 231 | } |
| 232 | return *this; |
| 233 | } |
| 234 | }; |
| 235 | |
| 236 | } // namespace optional_detail |
| 237 | |
| 238 | template <typename T> class Optional { |
| 239 | optional_detail::OptionalStorage<T> Storage; |
| 240 | |
| 241 | public: |
| 242 | using value_type = T; |
| 243 | |
| 244 | constexpr Optional() {} |
| 245 | constexpr Optional(NoneType) {} |
| 246 | |
| 247 | constexpr Optional(const T &y) : Storage(in_place, y) {} |
| 248 | constexpr Optional(const Optional &O) = default; |
| 249 | |
| 250 | constexpr Optional(T &&y) : Storage(in_place, std::move(y)) {} |
| 251 | constexpr Optional(Optional &&O) = default; |
| 252 | |
| 253 | template <typename... ArgTypes> |
| 254 | constexpr Optional(in_place_t, ArgTypes &&...Args) |
| 255 | : Storage(in_place, std::forward<ArgTypes>(Args)...) {} |
| 256 | |
| 257 | Optional &operator=(T &&y) { |
| 258 | Storage = std::move(y); |
| 259 | return *this; |
| 260 | } |
| 261 | Optional &operator=(Optional &&O) = default; |
| 262 | |
| 263 | /// Create a new object by constructing it in place with the given arguments. |
| 264 | template <typename... ArgTypes> void emplace(ArgTypes &&... Args) { |
| 265 | Storage.emplace(std::forward<ArgTypes>(Args)...); |
| 266 | } |
| 267 | |
| 268 | static constexpr Optional create(const T *y) { |
| 269 | return y ? Optional(*y) : Optional(); |
| 270 | } |
| 271 | |
| 272 | Optional &operator=(const T &y) { |
| 273 | Storage = y; |
| 274 | return *this; |
| 275 | } |
| 276 | Optional &operator=(const Optional &O) = default; |
| 277 | |
| 278 | void reset() { Storage.reset(); } |
| 279 | |
| 280 | constexpr const T *getPointer() const { return &Storage.getValue(); } |
| 281 | T *getPointer() { return &Storage.getValue(); } |
| 282 | constexpr const T &getValue() const LLVM_LVALUE_FUNCTION& { |
| 283 | return Storage.getValue(); |
| 284 | } |
| 285 | T &getValue() LLVM_LVALUE_FUNCTION& { return Storage.getValue(); } |
| 286 | |
| 287 | constexpr explicit operator bool() const { return hasValue(); } |
| 288 | constexpr bool hasValue() const { return Storage.hasValue(); } |
| 289 | constexpr const T *operator->() const { return getPointer(); } |
| 290 | T *operator->() { return getPointer(); } |
| 291 | constexpr const T &operator*() const LLVM_LVALUE_FUNCTION& { |
| 292 | return getValue(); |
| 293 | } |
| 294 | T &operator*() LLVM_LVALUE_FUNCTION& { return getValue(); } |
| 295 | |
| 296 | template <typename U> |
| 297 | constexpr T getValueOr(U &&value) const LLVM_LVALUE_FUNCTION& { |
| 298 | return hasValue() ? getValue() : std::forward<U>(value); |
| 299 | } |
| 300 | |
| 301 | /// Apply a function to the value if present; otherwise return None. |
| 302 | template <class Function> |
| 303 | auto map(const Function &F) const LLVM_LVALUE_FUNCTION& |
| 304 | -> Optional<decltype(F(getValue()))> { |
| 305 | if (*this) return F(getValue()); |
| 306 | return None; |
| 307 | } |
| 308 | |
| 309 | #if LLVM_HAS_RVALUE_REFERENCE_THIS1 |
| 310 | T &&getValue() && { return std::move(Storage.getValue()); } |
| 311 | T &&operator*() && { return std::move(Storage.getValue()); } |
| 312 | |
| 313 | template <typename U> |
| 314 | T getValueOr(U &&value) && { |
| 315 | return hasValue() ? std::move(getValue()) : std::forward<U>(value); |
| 316 | } |
| 317 | |
| 318 | /// Apply a function to the value if present; otherwise return None. |
| 319 | template <class Function> |
| 320 | auto map(const Function &F) && |
| 321 | -> Optional<decltype(F(std::move(*this).getValue()))> { |
| 322 | if (*this) return F(std::move(*this).getValue()); |
| 323 | return None; |
| 324 | } |
| 325 | #endif |
| 326 | }; |
| 327 | |
| 328 | template <class T> llvm::hash_code hash_value(const Optional<T> &O) { |
| 329 | return O ? hash_combine(true, *O) : hash_value(false); |
| 330 | } |
| 331 | |
| 332 | template <typename T, typename U> |
| 333 | constexpr bool operator==(const Optional<T> &X, const Optional<U> &Y) { |
| 334 | if (X && Y) |
| 335 | return *X == *Y; |
| 336 | return X.hasValue() == Y.hasValue(); |
| 337 | } |
| 338 | |
| 339 | template <typename T, typename U> |
| 340 | constexpr bool operator!=(const Optional<T> &X, const Optional<U> &Y) { |
| 341 | return !(X == Y); |
| 342 | } |
| 343 | |
| 344 | template <typename T, typename U> |
| 345 | constexpr bool operator<(const Optional<T> &X, const Optional<U> &Y) { |
| 346 | if (X && Y) |
| 347 | return *X < *Y; |
| 348 | return X.hasValue() < Y.hasValue(); |
| 349 | } |
| 350 | |
| 351 | template <typename T, typename U> |
| 352 | constexpr bool operator<=(const Optional<T> &X, const Optional<U> &Y) { |
| 353 | return !(Y < X); |
| 354 | } |
| 355 | |
| 356 | template <typename T, typename U> |
| 357 | constexpr bool operator>(const Optional<T> &X, const Optional<U> &Y) { |
| 358 | return Y < X; |
| 359 | } |
| 360 | |
| 361 | template <typename T, typename U> |
| 362 | constexpr bool operator>=(const Optional<T> &X, const Optional<U> &Y) { |
| 363 | return !(X < Y); |
| 364 | } |
| 365 | |
| 366 | template <typename T> |
| 367 | constexpr bool operator==(const Optional<T> &X, NoneType) { |
| 368 | return !X; |
| 369 | } |
| 370 | |
| 371 | template <typename T> |
| 372 | constexpr bool operator==(NoneType, const Optional<T> &X) { |
| 373 | return X == None; |
| 374 | } |
| 375 | |
| 376 | template <typename T> |
| 377 | constexpr bool operator!=(const Optional<T> &X, NoneType) { |
| 378 | return !(X == None); |
| 379 | } |
| 380 | |
| 381 | template <typename T> |
| 382 | constexpr bool operator!=(NoneType, const Optional<T> &X) { |
| 383 | return X != None; |
| 384 | } |
| 385 | |
| 386 | template <typename T> constexpr bool operator<(const Optional<T> &, NoneType) { |
| 387 | return false; |
| 388 | } |
| 389 | |
| 390 | template <typename T> constexpr bool operator<(NoneType, const Optional<T> &X) { |
| 391 | return X.hasValue(); |
| 392 | } |
| 393 | |
| 394 | template <typename T> |
| 395 | constexpr bool operator<=(const Optional<T> &X, NoneType) { |
| 396 | return !(None < X); |
| 397 | } |
| 398 | |
| 399 | template <typename T> |
| 400 | constexpr bool operator<=(NoneType, const Optional<T> &X) { |
| 401 | return !(X < None); |
| 402 | } |
| 403 | |
| 404 | template <typename T> constexpr bool operator>(const Optional<T> &X, NoneType) { |
| 405 | return None < X; |
| 406 | } |
| 407 | |
| 408 | template <typename T> constexpr bool operator>(NoneType, const Optional<T> &X) { |
| 409 | return X < None; |
| 410 | } |
| 411 | |
| 412 | template <typename T> |
| 413 | constexpr bool operator>=(const Optional<T> &X, NoneType) { |
| 414 | return None <= X; |
| 415 | } |
| 416 | |
| 417 | template <typename T> |
| 418 | constexpr bool operator>=(NoneType, const Optional<T> &X) { |
| 419 | return X <= None; |
| 420 | } |
| 421 | |
| 422 | template <typename T> |
| 423 | constexpr bool operator==(const Optional<T> &X, const T &Y) { |
| 424 | return X && *X == Y; |
| 425 | } |
| 426 | |
| 427 | template <typename T> |
| 428 | constexpr bool operator==(const T &X, const Optional<T> &Y) { |
| 429 | return Y && X == *Y; |
| 430 | } |
| 431 | |
| 432 | template <typename T> |
| 433 | constexpr bool operator!=(const Optional<T> &X, const T &Y) { |
| 434 | return !(X == Y); |
| 435 | } |
| 436 | |
| 437 | template <typename T> |
| 438 | constexpr bool operator!=(const T &X, const Optional<T> &Y) { |
| 439 | return !(X == Y); |
| 440 | } |
| 441 | |
| 442 | template <typename T> |
| 443 | constexpr bool operator<(const Optional<T> &X, const T &Y) { |
| 444 | return !X || *X < Y; |
| 445 | } |
| 446 | |
| 447 | template <typename T> |
| 448 | constexpr bool operator<(const T &X, const Optional<T> &Y) { |
| 449 | return Y && X < *Y; |
| 450 | } |
| 451 | |
| 452 | template <typename T> |
| 453 | constexpr bool operator<=(const Optional<T> &X, const T &Y) { |
| 454 | return !(Y < X); |
| 455 | } |
| 456 | |
| 457 | template <typename T> |
| 458 | constexpr bool operator<=(const T &X, const Optional<T> &Y) { |
| 459 | return !(Y < X); |
| 460 | } |
| 461 | |
| 462 | template <typename T> |
| 463 | constexpr bool operator>(const Optional<T> &X, const T &Y) { |
| 464 | return Y < X; |
| 465 | } |
| 466 | |
| 467 | template <typename T> |
| 468 | constexpr bool operator>(const T &X, const Optional<T> &Y) { |
| 469 | return Y < X; |
| 470 | } |
| 471 | |
| 472 | template <typename T> |
| 473 | constexpr bool operator>=(const Optional<T> &X, const T &Y) { |
| 474 | return !(X < Y); |
| 475 | } |
| 476 | |
| 477 | template <typename T> |
| 478 | constexpr bool operator>=(const T &X, const Optional<T> &Y) { |
| 479 | return !(X < Y); |
| 480 | } |
| 481 | |
| 482 | raw_ostream &operator<<(raw_ostream &OS, NoneType); |
| 483 | |
| 484 | template <typename T, typename = decltype(std::declval<raw_ostream &>() |
| 485 | << std::declval<const T &>())> |
| 486 | raw_ostream &operator<<(raw_ostream &OS, const Optional<T> &O) { |
| 487 | if (O) |
| 488 | OS << *O; |
| 489 | else |
| 490 | OS << None; |
| 491 | return OS; |
| 492 | } |
| 493 | |
| 494 | } // end namespace llvm |
| 495 | |
| 496 | #endif // LLVM_ADT_OPTIONAL_H |