| File: | src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ADT/APInt.h |
| Warning: | line 317, column 39 Assigned value is garbage or undefined |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
| 1 | //===- LazyValueInfo.cpp - Value constraint analysis ------------*- 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 defines the interface for lazy computation of value constraint | |||
| 10 | // information. | |||
| 11 | // | |||
| 12 | //===----------------------------------------------------------------------===// | |||
| 13 | ||||
| 14 | #include "llvm/Analysis/LazyValueInfo.h" | |||
| 15 | #include "llvm/ADT/DenseSet.h" | |||
| 16 | #include "llvm/ADT/Optional.h" | |||
| 17 | #include "llvm/ADT/STLExtras.h" | |||
| 18 | #include "llvm/Analysis/AssumptionCache.h" | |||
| 19 | #include "llvm/Analysis/ConstantFolding.h" | |||
| 20 | #include "llvm/Analysis/InstructionSimplify.h" | |||
| 21 | #include "llvm/Analysis/TargetLibraryInfo.h" | |||
| 22 | #include "llvm/Analysis/ValueLattice.h" | |||
| 23 | #include "llvm/Analysis/ValueTracking.h" | |||
| 24 | #include "llvm/IR/AssemblyAnnotationWriter.h" | |||
| 25 | #include "llvm/IR/CFG.h" | |||
| 26 | #include "llvm/IR/ConstantRange.h" | |||
| 27 | #include "llvm/IR/Constants.h" | |||
| 28 | #include "llvm/IR/DataLayout.h" | |||
| 29 | #include "llvm/IR/Dominators.h" | |||
| 30 | #include "llvm/IR/Instructions.h" | |||
| 31 | #include "llvm/IR/IntrinsicInst.h" | |||
| 32 | #include "llvm/IR/Intrinsics.h" | |||
| 33 | #include "llvm/IR/LLVMContext.h" | |||
| 34 | #include "llvm/IR/PatternMatch.h" | |||
| 35 | #include "llvm/IR/ValueHandle.h" | |||
| 36 | #include "llvm/InitializePasses.h" | |||
| 37 | #include "llvm/Support/Debug.h" | |||
| 38 | #include "llvm/Support/FormattedStream.h" | |||
| 39 | #include "llvm/Support/KnownBits.h" | |||
| 40 | #include "llvm/Support/raw_ostream.h" | |||
| 41 | #include <map> | |||
| 42 | using namespace llvm; | |||
| 43 | using namespace PatternMatch; | |||
| 44 | ||||
| 45 | #define DEBUG_TYPE"lazy-value-info" "lazy-value-info" | |||
| 46 | ||||
| 47 | // This is the number of worklist items we will process to try to discover an | |||
| 48 | // answer for a given value. | |||
| 49 | static const unsigned MaxProcessedPerValue = 500; | |||
| 50 | ||||
| 51 | char LazyValueInfoWrapperPass::ID = 0; | |||
| 52 | LazyValueInfoWrapperPass::LazyValueInfoWrapperPass() : FunctionPass(ID) { | |||
| 53 | initializeLazyValueInfoWrapperPassPass(*PassRegistry::getPassRegistry()); | |||
| 54 | } | |||
| 55 | INITIALIZE_PASS_BEGIN(LazyValueInfoWrapperPass, "lazy-value-info",static void *initializeLazyValueInfoWrapperPassPassOnce(PassRegistry &Registry) { | |||
| 56 | "Lazy Value Information Analysis", false, true)static void *initializeLazyValueInfoWrapperPassPassOnce(PassRegistry &Registry) { | |||
| 57 | INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)initializeAssumptionCacheTrackerPass(Registry); | |||
| 58 | INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)initializeTargetLibraryInfoWrapperPassPass(Registry); | |||
| 59 | INITIALIZE_PASS_END(LazyValueInfoWrapperPass, "lazy-value-info",PassInfo *PI = new PassInfo( "Lazy Value Information Analysis" , "lazy-value-info", &LazyValueInfoWrapperPass::ID, PassInfo ::NormalCtor_t(callDefaultCtor<LazyValueInfoWrapperPass> ), false, true); Registry.registerPass(*PI, true); return PI; } static llvm::once_flag InitializeLazyValueInfoWrapperPassPassFlag ; void llvm::initializeLazyValueInfoWrapperPassPass(PassRegistry &Registry) { llvm::call_once(InitializeLazyValueInfoWrapperPassPassFlag , initializeLazyValueInfoWrapperPassPassOnce, std::ref(Registry )); } | |||
| 60 | "Lazy Value Information Analysis", false, true)PassInfo *PI = new PassInfo( "Lazy Value Information Analysis" , "lazy-value-info", &LazyValueInfoWrapperPass::ID, PassInfo ::NormalCtor_t(callDefaultCtor<LazyValueInfoWrapperPass> ), false, true); Registry.registerPass(*PI, true); return PI; } static llvm::once_flag InitializeLazyValueInfoWrapperPassPassFlag ; void llvm::initializeLazyValueInfoWrapperPassPass(PassRegistry &Registry) { llvm::call_once(InitializeLazyValueInfoWrapperPassPassFlag , initializeLazyValueInfoWrapperPassPassOnce, std::ref(Registry )); } | |||
| 61 | ||||
| 62 | namespace llvm { | |||
| 63 | FunctionPass *createLazyValueInfoPass() { return new LazyValueInfoWrapperPass(); } | |||
| 64 | } | |||
| 65 | ||||
| 66 | AnalysisKey LazyValueAnalysis::Key; | |||
| 67 | ||||
| 68 | /// Returns true if this lattice value represents at most one possible value. | |||
| 69 | /// This is as precise as any lattice value can get while still representing | |||
| 70 | /// reachable code. | |||
| 71 | static bool hasSingleValue(const ValueLatticeElement &Val) { | |||
| 72 | if (Val.isConstantRange() && | |||
| 73 | Val.getConstantRange().isSingleElement()) | |||
| 74 | // Integer constants are single element ranges | |||
| 75 | return true; | |||
| 76 | if (Val.isConstant()) | |||
| 77 | // Non integer constants | |||
| 78 | return true; | |||
| 79 | return false; | |||
| 80 | } | |||
| 81 | ||||
| 82 | /// Combine two sets of facts about the same value into a single set of | |||
| 83 | /// facts. Note that this method is not suitable for merging facts along | |||
| 84 | /// different paths in a CFG; that's what the mergeIn function is for. This | |||
| 85 | /// is for merging facts gathered about the same value at the same location | |||
| 86 | /// through two independent means. | |||
| 87 | /// Notes: | |||
| 88 | /// * This method does not promise to return the most precise possible lattice | |||
| 89 | /// value implied by A and B. It is allowed to return any lattice element | |||
| 90 | /// which is at least as strong as *either* A or B (unless our facts | |||
| 91 | /// conflict, see below). | |||
| 92 | /// * Due to unreachable code, the intersection of two lattice values could be | |||
| 93 | /// contradictory. If this happens, we return some valid lattice value so as | |||
| 94 | /// not confuse the rest of LVI. Ideally, we'd always return Undefined, but | |||
| 95 | /// we do not make this guarantee. TODO: This would be a useful enhancement. | |||
| 96 | static ValueLatticeElement intersect(const ValueLatticeElement &A, | |||
| 97 | const ValueLatticeElement &B) { | |||
| 98 | // Undefined is the strongest state. It means the value is known to be along | |||
| 99 | // an unreachable path. | |||
| 100 | if (A.isUnknown()) | |||
| 101 | return A; | |||
| 102 | if (B.isUnknown()) | |||
| 103 | return B; | |||
| 104 | ||||
| 105 | // If we gave up for one, but got a useable fact from the other, use it. | |||
| 106 | if (A.isOverdefined()) | |||
| 107 | return B; | |||
| 108 | if (B.isOverdefined()) | |||
| 109 | return A; | |||
| 110 | ||||
| 111 | // Can't get any more precise than constants. | |||
| 112 | if (hasSingleValue(A)) | |||
| 113 | return A; | |||
| 114 | if (hasSingleValue(B)) | |||
| 115 | return B; | |||
| 116 | ||||
| 117 | // Could be either constant range or not constant here. | |||
| 118 | if (!A.isConstantRange() || !B.isConstantRange()) { | |||
| 119 | // TODO: Arbitrary choice, could be improved | |||
| 120 | return A; | |||
| 121 | } | |||
| 122 | ||||
| 123 | // Intersect two constant ranges | |||
| 124 | ConstantRange Range = | |||
| 125 | A.getConstantRange().intersectWith(B.getConstantRange()); | |||
| 126 | // Note: An empty range is implicitly converted to unknown or undef depending | |||
| 127 | // on MayIncludeUndef internally. | |||
| 128 | return ValueLatticeElement::getRange( | |||
| 129 | std::move(Range), /*MayIncludeUndef=*/A.isConstantRangeIncludingUndef() | | |||
| 130 | B.isConstantRangeIncludingUndef()); | |||
| 131 | } | |||
| 132 | ||||
| 133 | //===----------------------------------------------------------------------===// | |||
| 134 | // LazyValueInfoCache Decl | |||
| 135 | //===----------------------------------------------------------------------===// | |||
| 136 | ||||
| 137 | namespace { | |||
| 138 | /// A callback value handle updates the cache when values are erased. | |||
| 139 | class LazyValueInfoCache; | |||
| 140 | struct LVIValueHandle final : public CallbackVH { | |||
| 141 | LazyValueInfoCache *Parent; | |||
| 142 | ||||
| 143 | LVIValueHandle(Value *V, LazyValueInfoCache *P = nullptr) | |||
| 144 | : CallbackVH(V), Parent(P) { } | |||
| 145 | ||||
| 146 | void deleted() override; | |||
| 147 | void allUsesReplacedWith(Value *V) override { | |||
| 148 | deleted(); | |||
| 149 | } | |||
| 150 | }; | |||
| 151 | } // end anonymous namespace | |||
| 152 | ||||
| 153 | namespace { | |||
| 154 | using NonNullPointerSet = SmallDenseSet<AssertingVH<Value>, 2>; | |||
| 155 | ||||
| 156 | /// This is the cache kept by LazyValueInfo which | |||
| 157 | /// maintains information about queries across the clients' queries. | |||
| 158 | class LazyValueInfoCache { | |||
| 159 | /// This is all of the cached information for one basic block. It contains | |||
| 160 | /// the per-value lattice elements, as well as a separate set for | |||
| 161 | /// overdefined values to reduce memory usage. Additionally pointers | |||
| 162 | /// dereferenced in the block are cached for nullability queries. | |||
| 163 | struct BlockCacheEntry { | |||
| 164 | SmallDenseMap<AssertingVH<Value>, ValueLatticeElement, 4> LatticeElements; | |||
| 165 | SmallDenseSet<AssertingVH<Value>, 4> OverDefined; | |||
| 166 | // None indicates that the nonnull pointers for this basic block | |||
| 167 | // block have not been computed yet. | |||
| 168 | Optional<NonNullPointerSet> NonNullPointers; | |||
| 169 | }; | |||
| 170 | ||||
| 171 | /// Cached information per basic block. | |||
| 172 | DenseMap<PoisoningVH<BasicBlock>, std::unique_ptr<BlockCacheEntry>> | |||
| 173 | BlockCache; | |||
| 174 | /// Set of value handles used to erase values from the cache on deletion. | |||
| 175 | DenseSet<LVIValueHandle, DenseMapInfo<Value *>> ValueHandles; | |||
| 176 | ||||
| 177 | const BlockCacheEntry *getBlockEntry(BasicBlock *BB) const { | |||
| 178 | auto It = BlockCache.find_as(BB); | |||
| 179 | if (It == BlockCache.end()) | |||
| 180 | return nullptr; | |||
| 181 | return It->second.get(); | |||
| 182 | } | |||
| 183 | ||||
| 184 | BlockCacheEntry *getOrCreateBlockEntry(BasicBlock *BB) { | |||
| 185 | auto It = BlockCache.find_as(BB); | |||
| 186 | if (It == BlockCache.end()) | |||
| 187 | It = BlockCache.insert({ BB, std::make_unique<BlockCacheEntry>() }) | |||
| 188 | .first; | |||
| 189 | ||||
| 190 | return It->second.get(); | |||
| 191 | } | |||
| 192 | ||||
| 193 | void addValueHandle(Value *Val) { | |||
| 194 | auto HandleIt = ValueHandles.find_as(Val); | |||
| 195 | if (HandleIt == ValueHandles.end()) | |||
| 196 | ValueHandles.insert({ Val, this }); | |||
| 197 | } | |||
| 198 | ||||
| 199 | public: | |||
| 200 | void insertResult(Value *Val, BasicBlock *BB, | |||
| 201 | const ValueLatticeElement &Result) { | |||
| 202 | BlockCacheEntry *Entry = getOrCreateBlockEntry(BB); | |||
| 203 | ||||
| 204 | // Insert over-defined values into their own cache to reduce memory | |||
| 205 | // overhead. | |||
| 206 | if (Result.isOverdefined()) | |||
| 207 | Entry->OverDefined.insert(Val); | |||
| 208 | else | |||
| 209 | Entry->LatticeElements.insert({ Val, Result }); | |||
| 210 | ||||
| 211 | addValueHandle(Val); | |||
| 212 | } | |||
| 213 | ||||
| 214 | Optional<ValueLatticeElement> getCachedValueInfo(Value *V, | |||
| 215 | BasicBlock *BB) const { | |||
| 216 | const BlockCacheEntry *Entry = getBlockEntry(BB); | |||
| 217 | if (!Entry) | |||
| 218 | return None; | |||
| 219 | ||||
| 220 | if (Entry->OverDefined.count(V)) | |||
| 221 | return ValueLatticeElement::getOverdefined(); | |||
| 222 | ||||
| 223 | auto LatticeIt = Entry->LatticeElements.find_as(V); | |||
| 224 | if (LatticeIt == Entry->LatticeElements.end()) | |||
| 225 | return None; | |||
| 226 | ||||
| 227 | return LatticeIt->second; | |||
| 228 | } | |||
| 229 | ||||
| 230 | bool isNonNullAtEndOfBlock( | |||
| 231 | Value *V, BasicBlock *BB, | |||
| 232 | function_ref<NonNullPointerSet(BasicBlock *)> InitFn) { | |||
| 233 | BlockCacheEntry *Entry = getOrCreateBlockEntry(BB); | |||
| 234 | if (!Entry->NonNullPointers) { | |||
| 235 | Entry->NonNullPointers = InitFn(BB); | |||
| 236 | for (Value *V : *Entry->NonNullPointers) | |||
| 237 | addValueHandle(V); | |||
| 238 | } | |||
| 239 | ||||
| 240 | return Entry->NonNullPointers->count(V); | |||
| 241 | } | |||
| 242 | ||||
| 243 | /// clear - Empty the cache. | |||
| 244 | void clear() { | |||
| 245 | BlockCache.clear(); | |||
| 246 | ValueHandles.clear(); | |||
| 247 | } | |||
| 248 | ||||
| 249 | /// Inform the cache that a given value has been deleted. | |||
| 250 | void eraseValue(Value *V); | |||
| 251 | ||||
| 252 | /// This is part of the update interface to inform the cache | |||
| 253 | /// that a block has been deleted. | |||
| 254 | void eraseBlock(BasicBlock *BB); | |||
| 255 | ||||
| 256 | /// Updates the cache to remove any influence an overdefined value in | |||
| 257 | /// OldSucc might have (unless also overdefined in NewSucc). This just | |||
| 258 | /// flushes elements from the cache and does not add any. | |||
| 259 | void threadEdgeImpl(BasicBlock *OldSucc,BasicBlock *NewSucc); | |||
| 260 | }; | |||
| 261 | } | |||
| 262 | ||||
| 263 | void LazyValueInfoCache::eraseValue(Value *V) { | |||
| 264 | for (auto &Pair : BlockCache) { | |||
| 265 | Pair.second->LatticeElements.erase(V); | |||
| 266 | Pair.second->OverDefined.erase(V); | |||
| 267 | if (Pair.second->NonNullPointers) | |||
| 268 | Pair.second->NonNullPointers->erase(V); | |||
| 269 | } | |||
| 270 | ||||
| 271 | auto HandleIt = ValueHandles.find_as(V); | |||
| 272 | if (HandleIt != ValueHandles.end()) | |||
| 273 | ValueHandles.erase(HandleIt); | |||
| 274 | } | |||
| 275 | ||||
| 276 | void LVIValueHandle::deleted() { | |||
| 277 | // This erasure deallocates *this, so it MUST happen after we're done | |||
| 278 | // using any and all members of *this. | |||
| 279 | Parent->eraseValue(*this); | |||
| 280 | } | |||
| 281 | ||||
| 282 | void LazyValueInfoCache::eraseBlock(BasicBlock *BB) { | |||
| 283 | BlockCache.erase(BB); | |||
| 284 | } | |||
| 285 | ||||
| 286 | void LazyValueInfoCache::threadEdgeImpl(BasicBlock *OldSucc, | |||
| 287 | BasicBlock *NewSucc) { | |||
| 288 | // When an edge in the graph has been threaded, values that we could not | |||
| 289 | // determine a value for before (i.e. were marked overdefined) may be | |||
| 290 | // possible to solve now. We do NOT try to proactively update these values. | |||
| 291 | // Instead, we clear their entries from the cache, and allow lazy updating to | |||
| 292 | // recompute them when needed. | |||
| 293 | ||||
| 294 | // The updating process is fairly simple: we need to drop cached info | |||
| 295 | // for all values that were marked overdefined in OldSucc, and for those same | |||
| 296 | // values in any successor of OldSucc (except NewSucc) in which they were | |||
| 297 | // also marked overdefined. | |||
| 298 | std::vector<BasicBlock*> worklist; | |||
| 299 | worklist.push_back(OldSucc); | |||
| 300 | ||||
| 301 | const BlockCacheEntry *Entry = getBlockEntry(OldSucc); | |||
| 302 | if (!Entry || Entry->OverDefined.empty()) | |||
| 303 | return; // Nothing to process here. | |||
| 304 | SmallVector<Value *, 4> ValsToClear(Entry->OverDefined.begin(), | |||
| 305 | Entry->OverDefined.end()); | |||
| 306 | ||||
| 307 | // Use a worklist to perform a depth-first search of OldSucc's successors. | |||
| 308 | // NOTE: We do not need a visited list since any blocks we have already | |||
| 309 | // visited will have had their overdefined markers cleared already, and we | |||
| 310 | // thus won't loop to their successors. | |||
| 311 | while (!worklist.empty()) { | |||
| 312 | BasicBlock *ToUpdate = worklist.back(); | |||
| 313 | worklist.pop_back(); | |||
| 314 | ||||
| 315 | // Skip blocks only accessible through NewSucc. | |||
| 316 | if (ToUpdate == NewSucc) continue; | |||
| 317 | ||||
| 318 | // If a value was marked overdefined in OldSucc, and is here too... | |||
| 319 | auto OI = BlockCache.find_as(ToUpdate); | |||
| 320 | if (OI == BlockCache.end() || OI->second->OverDefined.empty()) | |||
| 321 | continue; | |||
| 322 | auto &ValueSet = OI->second->OverDefined; | |||
| 323 | ||||
| 324 | bool changed = false; | |||
| 325 | for (Value *V : ValsToClear) { | |||
| 326 | if (!ValueSet.erase(V)) | |||
| 327 | continue; | |||
| 328 | ||||
| 329 | // If we removed anything, then we potentially need to update | |||
| 330 | // blocks successors too. | |||
| 331 | changed = true; | |||
| 332 | } | |||
| 333 | ||||
| 334 | if (!changed) continue; | |||
| 335 | ||||
| 336 | llvm::append_range(worklist, successors(ToUpdate)); | |||
| 337 | } | |||
| 338 | } | |||
| 339 | ||||
| 340 | ||||
| 341 | namespace { | |||
| 342 | /// An assembly annotator class to print LazyValueCache information in | |||
| 343 | /// comments. | |||
| 344 | class LazyValueInfoImpl; | |||
| 345 | class LazyValueInfoAnnotatedWriter : public AssemblyAnnotationWriter { | |||
| 346 | LazyValueInfoImpl *LVIImpl; | |||
| 347 | // While analyzing which blocks we can solve values for, we need the dominator | |||
| 348 | // information. | |||
| 349 | DominatorTree &DT; | |||
| 350 | ||||
| 351 | public: | |||
| 352 | LazyValueInfoAnnotatedWriter(LazyValueInfoImpl *L, DominatorTree &DTree) | |||
| 353 | : LVIImpl(L), DT(DTree) {} | |||
| 354 | ||||
| 355 | void emitBasicBlockStartAnnot(const BasicBlock *BB, | |||
| 356 | formatted_raw_ostream &OS) override; | |||
| 357 | ||||
| 358 | void emitInstructionAnnot(const Instruction *I, | |||
| 359 | formatted_raw_ostream &OS) override; | |||
| 360 | }; | |||
| 361 | } | |||
| 362 | namespace { | |||
| 363 | // The actual implementation of the lazy analysis and update. Note that the | |||
| 364 | // inheritance from LazyValueInfoCache is intended to be temporary while | |||
| 365 | // splitting the code and then transitioning to a has-a relationship. | |||
| 366 | class LazyValueInfoImpl { | |||
| 367 | ||||
| 368 | /// Cached results from previous queries | |||
| 369 | LazyValueInfoCache TheCache; | |||
| 370 | ||||
| 371 | /// This stack holds the state of the value solver during a query. | |||
| 372 | /// It basically emulates the callstack of the naive | |||
| 373 | /// recursive value lookup process. | |||
| 374 | SmallVector<std::pair<BasicBlock*, Value*>, 8> BlockValueStack; | |||
| 375 | ||||
| 376 | /// Keeps track of which block-value pairs are in BlockValueStack. | |||
| 377 | DenseSet<std::pair<BasicBlock*, Value*> > BlockValueSet; | |||
| 378 | ||||
| 379 | /// Push BV onto BlockValueStack unless it's already in there. | |||
| 380 | /// Returns true on success. | |||
| 381 | bool pushBlockValue(const std::pair<BasicBlock *, Value *> &BV) { | |||
| 382 | if (!BlockValueSet.insert(BV).second) | |||
| 383 | return false; // It's already in the stack. | |||
| 384 | ||||
| 385 | LLVM_DEBUG(dbgs() << "PUSH: " << *BV.second << " in "do { } while (false) | |||
| 386 | << BV.first->getName() << "\n")do { } while (false); | |||
| 387 | BlockValueStack.push_back(BV); | |||
| 388 | return true; | |||
| 389 | } | |||
| 390 | ||||
| 391 | AssumptionCache *AC; ///< A pointer to the cache of @llvm.assume calls. | |||
| 392 | const DataLayout &DL; ///< A mandatory DataLayout | |||
| 393 | ||||
| 394 | /// Declaration of the llvm.experimental.guard() intrinsic, | |||
| 395 | /// if it exists in the module. | |||
| 396 | Function *GuardDecl; | |||
| 397 | ||||
| 398 | Optional<ValueLatticeElement> getBlockValue(Value *Val, BasicBlock *BB); | |||
| 399 | Optional<ValueLatticeElement> getEdgeValue(Value *V, BasicBlock *F, | |||
| 400 | BasicBlock *T, Instruction *CxtI = nullptr); | |||
| 401 | ||||
| 402 | // These methods process one work item and may add more. A false value | |||
| 403 | // returned means that the work item was not completely processed and must | |||
| 404 | // be revisited after going through the new items. | |||
| 405 | bool solveBlockValue(Value *Val, BasicBlock *BB); | |||
| 406 | Optional<ValueLatticeElement> solveBlockValueImpl(Value *Val, BasicBlock *BB); | |||
| 407 | Optional<ValueLatticeElement> solveBlockValueNonLocal(Value *Val, | |||
| 408 | BasicBlock *BB); | |||
| 409 | Optional<ValueLatticeElement> solveBlockValuePHINode(PHINode *PN, | |||
| 410 | BasicBlock *BB); | |||
| 411 | Optional<ValueLatticeElement> solveBlockValueSelect(SelectInst *S, | |||
| 412 | BasicBlock *BB); | |||
| 413 | Optional<ConstantRange> getRangeFor(Value *V, Instruction *CxtI, | |||
| 414 | BasicBlock *BB); | |||
| 415 | Optional<ValueLatticeElement> solveBlockValueBinaryOpImpl( | |||
| 416 | Instruction *I, BasicBlock *BB, | |||
| 417 | std::function<ConstantRange(const ConstantRange &, | |||
| 418 | const ConstantRange &)> OpFn); | |||
| 419 | Optional<ValueLatticeElement> solveBlockValueBinaryOp(BinaryOperator *BBI, | |||
| 420 | BasicBlock *BB); | |||
| 421 | Optional<ValueLatticeElement> solveBlockValueCast(CastInst *CI, | |||
| 422 | BasicBlock *BB); | |||
| 423 | Optional<ValueLatticeElement> solveBlockValueOverflowIntrinsic( | |||
| 424 | WithOverflowInst *WO, BasicBlock *BB); | |||
| 425 | Optional<ValueLatticeElement> solveBlockValueIntrinsic(IntrinsicInst *II, | |||
| 426 | BasicBlock *BB); | |||
| 427 | Optional<ValueLatticeElement> solveBlockValueExtractValue( | |||
| 428 | ExtractValueInst *EVI, BasicBlock *BB); | |||
| 429 | bool isNonNullAtEndOfBlock(Value *Val, BasicBlock *BB); | |||
| 430 | void intersectAssumeOrGuardBlockValueConstantRange(Value *Val, | |||
| 431 | ValueLatticeElement &BBLV, | |||
| 432 | Instruction *BBI); | |||
| 433 | ||||
| 434 | void solve(); | |||
| 435 | ||||
| 436 | public: | |||
| 437 | /// This is the query interface to determine the lattice value for the | |||
| 438 | /// specified Value* at the context instruction (if specified) or at the | |||
| 439 | /// start of the block. | |||
| 440 | ValueLatticeElement getValueInBlock(Value *V, BasicBlock *BB, | |||
| 441 | Instruction *CxtI = nullptr); | |||
| 442 | ||||
| 443 | /// This is the query interface to determine the lattice value for the | |||
| 444 | /// specified Value* at the specified instruction using only information | |||
| 445 | /// from assumes/guards and range metadata. Unlike getValueInBlock(), no | |||
| 446 | /// recursive query is performed. | |||
| 447 | ValueLatticeElement getValueAt(Value *V, Instruction *CxtI); | |||
| 448 | ||||
| 449 | /// This is the query interface to determine the lattice | |||
| 450 | /// value for the specified Value* that is true on the specified edge. | |||
| 451 | ValueLatticeElement getValueOnEdge(Value *V, BasicBlock *FromBB, | |||
| 452 | BasicBlock *ToBB, | |||
| 453 | Instruction *CxtI = nullptr); | |||
| 454 | ||||
| 455 | /// Complete flush all previously computed values | |||
| 456 | void clear() { | |||
| 457 | TheCache.clear(); | |||
| 458 | } | |||
| 459 | ||||
| 460 | /// Printing the LazyValueInfo Analysis. | |||
| 461 | void printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS) { | |||
| 462 | LazyValueInfoAnnotatedWriter Writer(this, DTree); | |||
| 463 | F.print(OS, &Writer); | |||
| 464 | } | |||
| 465 | ||||
| 466 | /// This is part of the update interface to inform the cache | |||
| 467 | /// that a block has been deleted. | |||
| 468 | void eraseBlock(BasicBlock *BB) { | |||
| 469 | TheCache.eraseBlock(BB); | |||
| 470 | } | |||
| 471 | ||||
| 472 | /// This is the update interface to inform the cache that an edge from | |||
| 473 | /// PredBB to OldSucc has been threaded to be from PredBB to NewSucc. | |||
| 474 | void threadEdge(BasicBlock *PredBB,BasicBlock *OldSucc,BasicBlock *NewSucc); | |||
| 475 | ||||
| 476 | LazyValueInfoImpl(AssumptionCache *AC, const DataLayout &DL, | |||
| 477 | Function *GuardDecl) | |||
| 478 | : AC(AC), DL(DL), GuardDecl(GuardDecl) {} | |||
| 479 | }; | |||
| 480 | } // end anonymous namespace | |||
| 481 | ||||
| 482 | ||||
| 483 | void LazyValueInfoImpl::solve() { | |||
| 484 | SmallVector<std::pair<BasicBlock *, Value *>, 8> StartingStack( | |||
| 485 | BlockValueStack.begin(), BlockValueStack.end()); | |||
| 486 | ||||
| 487 | unsigned processedCount = 0; | |||
| 488 | while (!BlockValueStack.empty()) { | |||
| 489 | processedCount++; | |||
| 490 | // Abort if we have to process too many values to get a result for this one. | |||
| 491 | // Because of the design of the overdefined cache currently being per-block | |||
| 492 | // to avoid naming-related issues (IE it wants to try to give different | |||
| 493 | // results for the same name in different blocks), overdefined results don't | |||
| 494 | // get cached globally, which in turn means we will often try to rediscover | |||
| 495 | // the same overdefined result again and again. Once something like | |||
| 496 | // PredicateInfo is used in LVI or CVP, we should be able to make the | |||
| 497 | // overdefined cache global, and remove this throttle. | |||
| 498 | if (processedCount > MaxProcessedPerValue) { | |||
| 499 | LLVM_DEBUG(do { } while (false) | |||
| 500 | dbgs() << "Giving up on stack because we are getting too deep\n")do { } while (false); | |||
| 501 | // Fill in the original values | |||
| 502 | while (!StartingStack.empty()) { | |||
| 503 | std::pair<BasicBlock *, Value *> &e = StartingStack.back(); | |||
| 504 | TheCache.insertResult(e.second, e.first, | |||
| 505 | ValueLatticeElement::getOverdefined()); | |||
| 506 | StartingStack.pop_back(); | |||
| 507 | } | |||
| 508 | BlockValueSet.clear(); | |||
| 509 | BlockValueStack.clear(); | |||
| 510 | return; | |||
| 511 | } | |||
| 512 | std::pair<BasicBlock *, Value *> e = BlockValueStack.back(); | |||
| 513 | assert(BlockValueSet.count(e) && "Stack value should be in BlockValueSet!")((void)0); | |||
| 514 | ||||
| 515 | if (solveBlockValue(e.second, e.first)) { | |||
| 516 | // The work item was completely processed. | |||
| 517 | assert(BlockValueStack.back() == e && "Nothing should have been pushed!")((void)0); | |||
| 518 | #ifndef NDEBUG1 | |||
| 519 | Optional<ValueLatticeElement> BBLV = | |||
| 520 | TheCache.getCachedValueInfo(e.second, e.first); | |||
| 521 | assert(BBLV && "Result should be in cache!")((void)0); | |||
| 522 | LLVM_DEBUG(do { } while (false) | |||
| 523 | dbgs() << "POP " << *e.second << " in " << e.first->getName() << " = "do { } while (false) | |||
| 524 | << *BBLV << "\n")do { } while (false); | |||
| 525 | #endif | |||
| 526 | ||||
| 527 | BlockValueStack.pop_back(); | |||
| 528 | BlockValueSet.erase(e); | |||
| 529 | } else { | |||
| 530 | // More work needs to be done before revisiting. | |||
| 531 | assert(BlockValueStack.back() != e && "Stack should have been pushed!")((void)0); | |||
| 532 | } | |||
| 533 | } | |||
| 534 | } | |||
| 535 | ||||
| 536 | Optional<ValueLatticeElement> LazyValueInfoImpl::getBlockValue(Value *Val, | |||
| 537 | BasicBlock *BB) { | |||
| 538 | // If already a constant, there is nothing to compute. | |||
| 539 | if (Constant *VC = dyn_cast<Constant>(Val)) | |||
| 540 | return ValueLatticeElement::get(VC); | |||
| 541 | ||||
| 542 | if (Optional<ValueLatticeElement> OptLatticeVal = | |||
| 543 | TheCache.getCachedValueInfo(Val, BB)) | |||
| 544 | return OptLatticeVal; | |||
| 545 | ||||
| 546 | // We have hit a cycle, assume overdefined. | |||
| 547 | if (!pushBlockValue({ BB, Val })) | |||
| 548 | return ValueLatticeElement::getOverdefined(); | |||
| 549 | ||||
| 550 | // Yet to be resolved. | |||
| 551 | return None; | |||
| 552 | } | |||
| 553 | ||||
| 554 | static ValueLatticeElement getFromRangeMetadata(Instruction *BBI) { | |||
| 555 | switch (BBI->getOpcode()) { | |||
| 556 | default: break; | |||
| 557 | case Instruction::Load: | |||
| 558 | case Instruction::Call: | |||
| 559 | case Instruction::Invoke: | |||
| 560 | if (MDNode *Ranges = BBI->getMetadata(LLVMContext::MD_range)) | |||
| 561 | if (isa<IntegerType>(BBI->getType())) { | |||
| 562 | return ValueLatticeElement::getRange( | |||
| 563 | getConstantRangeFromMetadata(*Ranges)); | |||
| 564 | } | |||
| 565 | break; | |||
| 566 | }; | |||
| 567 | // Nothing known - will be intersected with other facts | |||
| 568 | return ValueLatticeElement::getOverdefined(); | |||
| 569 | } | |||
| 570 | ||||
| 571 | bool LazyValueInfoImpl::solveBlockValue(Value *Val, BasicBlock *BB) { | |||
| 572 | assert(!isa<Constant>(Val) && "Value should not be constant")((void)0); | |||
| 573 | assert(!TheCache.getCachedValueInfo(Val, BB) &&((void)0) | |||
| 574 | "Value should not be in cache")((void)0); | |||
| 575 | ||||
| 576 | // Hold off inserting this value into the Cache in case we have to return | |||
| 577 | // false and come back later. | |||
| 578 | Optional<ValueLatticeElement> Res = solveBlockValueImpl(Val, BB); | |||
| 579 | if (!Res) | |||
| 580 | // Work pushed, will revisit | |||
| 581 | return false; | |||
| 582 | ||||
| 583 | TheCache.insertResult(Val, BB, *Res); | |||
| 584 | return true; | |||
| 585 | } | |||
| 586 | ||||
| 587 | Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueImpl( | |||
| 588 | Value *Val, BasicBlock *BB) { | |||
| 589 | Instruction *BBI = dyn_cast<Instruction>(Val); | |||
| 590 | if (!BBI || BBI->getParent() != BB) | |||
| 591 | return solveBlockValueNonLocal(Val, BB); | |||
| 592 | ||||
| 593 | if (PHINode *PN = dyn_cast<PHINode>(BBI)) | |||
| 594 | return solveBlockValuePHINode(PN, BB); | |||
| 595 | ||||
| 596 | if (auto *SI = dyn_cast<SelectInst>(BBI)) | |||
| 597 | return solveBlockValueSelect(SI, BB); | |||
| 598 | ||||
| 599 | // If this value is a nonnull pointer, record it's range and bailout. Note | |||
| 600 | // that for all other pointer typed values, we terminate the search at the | |||
| 601 | // definition. We could easily extend this to look through geps, bitcasts, | |||
| 602 | // and the like to prove non-nullness, but it's not clear that's worth it | |||
| 603 | // compile time wise. The context-insensitive value walk done inside | |||
| 604 | // isKnownNonZero gets most of the profitable cases at much less expense. | |||
| 605 | // This does mean that we have a sensitivity to where the defining | |||
| 606 | // instruction is placed, even if it could legally be hoisted much higher. | |||
| 607 | // That is unfortunate. | |||
| 608 | PointerType *PT = dyn_cast<PointerType>(BBI->getType()); | |||
| 609 | if (PT && isKnownNonZero(BBI, DL)) | |||
| 610 | return ValueLatticeElement::getNot(ConstantPointerNull::get(PT)); | |||
| 611 | ||||
| 612 | if (BBI->getType()->isIntegerTy()) { | |||
| 613 | if (auto *CI = dyn_cast<CastInst>(BBI)) | |||
| 614 | return solveBlockValueCast(CI, BB); | |||
| 615 | ||||
| 616 | if (BinaryOperator *BO = dyn_cast<BinaryOperator>(BBI)) | |||
| 617 | return solveBlockValueBinaryOp(BO, BB); | |||
| 618 | ||||
| 619 | if (auto *EVI = dyn_cast<ExtractValueInst>(BBI)) | |||
| 620 | return solveBlockValueExtractValue(EVI, BB); | |||
| 621 | ||||
| 622 | if (auto *II = dyn_cast<IntrinsicInst>(BBI)) | |||
| 623 | return solveBlockValueIntrinsic(II, BB); | |||
| 624 | } | |||
| 625 | ||||
| 626 | LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()do { } while (false) | |||
| 627 | << "' - unknown inst def found.\n")do { } while (false); | |||
| 628 | return getFromRangeMetadata(BBI); | |||
| 629 | } | |||
| 630 | ||||
| 631 | static void AddNonNullPointer(Value *Ptr, NonNullPointerSet &PtrSet) { | |||
| 632 | // TODO: Use NullPointerIsDefined instead. | |||
| 633 | if (Ptr->getType()->getPointerAddressSpace() == 0) | |||
| 634 | PtrSet.insert(getUnderlyingObject(Ptr)); | |||
| 635 | } | |||
| 636 | ||||
| 637 | static void AddNonNullPointersByInstruction( | |||
| 638 | Instruction *I, NonNullPointerSet &PtrSet) { | |||
| 639 | if (LoadInst *L = dyn_cast<LoadInst>(I)) { | |||
| 640 | AddNonNullPointer(L->getPointerOperand(), PtrSet); | |||
| 641 | } else if (StoreInst *S = dyn_cast<StoreInst>(I)) { | |||
| 642 | AddNonNullPointer(S->getPointerOperand(), PtrSet); | |||
| 643 | } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) { | |||
| 644 | if (MI->isVolatile()) return; | |||
| 645 | ||||
| 646 | // FIXME: check whether it has a valuerange that excludes zero? | |||
| 647 | ConstantInt *Len = dyn_cast<ConstantInt>(MI->getLength()); | |||
| 648 | if (!Len || Len->isZero()) return; | |||
| 649 | ||||
| 650 | AddNonNullPointer(MI->getRawDest(), PtrSet); | |||
| 651 | if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI)) | |||
| 652 | AddNonNullPointer(MTI->getRawSource(), PtrSet); | |||
| 653 | } | |||
| 654 | } | |||
| 655 | ||||
| 656 | bool LazyValueInfoImpl::isNonNullAtEndOfBlock(Value *Val, BasicBlock *BB) { | |||
| 657 | if (NullPointerIsDefined(BB->getParent(), | |||
| 658 | Val->getType()->getPointerAddressSpace())) | |||
| 659 | return false; | |||
| 660 | ||||
| 661 | Val = Val->stripInBoundsOffsets(); | |||
| 662 | return TheCache.isNonNullAtEndOfBlock(Val, BB, [](BasicBlock *BB) { | |||
| 663 | NonNullPointerSet NonNullPointers; | |||
| 664 | for (Instruction &I : *BB) | |||
| 665 | AddNonNullPointersByInstruction(&I, NonNullPointers); | |||
| 666 | return NonNullPointers; | |||
| 667 | }); | |||
| 668 | } | |||
| 669 | ||||
| 670 | Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueNonLocal( | |||
| 671 | Value *Val, BasicBlock *BB) { | |||
| 672 | ValueLatticeElement Result; // Start Undefined. | |||
| 673 | ||||
| 674 | // If this is the entry block, we must be asking about an argument. The | |||
| 675 | // value is overdefined. | |||
| 676 | if (BB->isEntryBlock()) { | |||
| 677 | assert(isa<Argument>(Val) && "Unknown live-in to the entry block")((void)0); | |||
| 678 | return ValueLatticeElement::getOverdefined(); | |||
| 679 | } | |||
| 680 | ||||
| 681 | // Loop over all of our predecessors, merging what we know from them into | |||
| 682 | // result. If we encounter an unexplored predecessor, we eagerly explore it | |||
| 683 | // in a depth first manner. In practice, this has the effect of discovering | |||
| 684 | // paths we can't analyze eagerly without spending compile times analyzing | |||
| 685 | // other paths. This heuristic benefits from the fact that predecessors are | |||
| 686 | // frequently arranged such that dominating ones come first and we quickly | |||
| 687 | // find a path to function entry. TODO: We should consider explicitly | |||
| 688 | // canonicalizing to make this true rather than relying on this happy | |||
| 689 | // accident. | |||
| 690 | for (BasicBlock *Pred : predecessors(BB)) { | |||
| 691 | Optional<ValueLatticeElement> EdgeResult = getEdgeValue(Val, Pred, BB); | |||
| 692 | if (!EdgeResult) | |||
| 693 | // Explore that input, then return here | |||
| 694 | return None; | |||
| 695 | ||||
| 696 | Result.mergeIn(*EdgeResult); | |||
| 697 | ||||
| 698 | // If we hit overdefined, exit early. The BlockVals entry is already set | |||
| 699 | // to overdefined. | |||
| 700 | if (Result.isOverdefined()) { | |||
| 701 | LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()do { } while (false) | |||
| 702 | << "' - overdefined because of pred (non local).\n")do { } while (false); | |||
| 703 | return Result; | |||
| 704 | } | |||
| 705 | } | |||
| 706 | ||||
| 707 | // Return the merged value, which is more precise than 'overdefined'. | |||
| 708 | assert(!Result.isOverdefined())((void)0); | |||
| 709 | return Result; | |||
| 710 | } | |||
| 711 | ||||
| 712 | Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValuePHINode( | |||
| 713 | PHINode *PN, BasicBlock *BB) { | |||
| 714 | ValueLatticeElement Result; // Start Undefined. | |||
| 715 | ||||
| 716 | // Loop over all of our predecessors, merging what we know from them into | |||
| 717 | // result. See the comment about the chosen traversal order in | |||
| 718 | // solveBlockValueNonLocal; the same reasoning applies here. | |||
| 719 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { | |||
| 720 | BasicBlock *PhiBB = PN->getIncomingBlock(i); | |||
| 721 | Value *PhiVal = PN->getIncomingValue(i); | |||
| 722 | // Note that we can provide PN as the context value to getEdgeValue, even | |||
| 723 | // though the results will be cached, because PN is the value being used as | |||
| 724 | // the cache key in the caller. | |||
| 725 | Optional<ValueLatticeElement> EdgeResult = | |||
| 726 | getEdgeValue(PhiVal, PhiBB, BB, PN); | |||
| 727 | if (!EdgeResult) | |||
| 728 | // Explore that input, then return here | |||
| 729 | return None; | |||
| 730 | ||||
| 731 | Result.mergeIn(*EdgeResult); | |||
| 732 | ||||
| 733 | // If we hit overdefined, exit early. The BlockVals entry is already set | |||
| 734 | // to overdefined. | |||
| 735 | if (Result.isOverdefined()) { | |||
| 736 | LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()do { } while (false) | |||
| 737 | << "' - overdefined because of pred (local).\n")do { } while (false); | |||
| 738 | ||||
| 739 | return Result; | |||
| 740 | } | |||
| 741 | } | |||
| 742 | ||||
| 743 | // Return the merged value, which is more precise than 'overdefined'. | |||
| 744 | assert(!Result.isOverdefined() && "Possible PHI in entry block?")((void)0); | |||
| 745 | return Result; | |||
| 746 | } | |||
| 747 | ||||
| 748 | static ValueLatticeElement getValueFromCondition(Value *Val, Value *Cond, | |||
| 749 | bool isTrueDest = true); | |||
| 750 | ||||
| 751 | // If we can determine a constraint on the value given conditions assumed by | |||
| 752 | // the program, intersect those constraints with BBLV | |||
| 753 | void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange( | |||
| 754 | Value *Val, ValueLatticeElement &BBLV, Instruction *BBI) { | |||
| 755 | BBI = BBI ? BBI : dyn_cast<Instruction>(Val); | |||
| 756 | if (!BBI) | |||
| 757 | return; | |||
| 758 | ||||
| 759 | BasicBlock *BB = BBI->getParent(); | |||
| 760 | for (auto &AssumeVH : AC->assumptionsFor(Val)) { | |||
| 761 | if (!AssumeVH) | |||
| 762 | continue; | |||
| 763 | ||||
| 764 | // Only check assumes in the block of the context instruction. Other | |||
| 765 | // assumes will have already been taken into account when the value was | |||
| 766 | // propagated from predecessor blocks. | |||
| 767 | auto *I = cast<CallInst>(AssumeVH); | |||
| 768 | if (I->getParent() != BB || !isValidAssumeForContext(I, BBI)) | |||
| 769 | continue; | |||
| 770 | ||||
| 771 | BBLV = intersect(BBLV, getValueFromCondition(Val, I->getArgOperand(0))); | |||
| 772 | } | |||
| 773 | ||||
| 774 | // If guards are not used in the module, don't spend time looking for them | |||
| 775 | if (GuardDecl && !GuardDecl->use_empty() && | |||
| 776 | BBI->getIterator() != BB->begin()) { | |||
| 777 | for (Instruction &I : make_range(std::next(BBI->getIterator().getReverse()), | |||
| 778 | BB->rend())) { | |||
| 779 | Value *Cond = nullptr; | |||
| 780 | if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>(m_Value(Cond)))) | |||
| 781 | BBLV = intersect(BBLV, getValueFromCondition(Val, Cond)); | |||
| 782 | } | |||
| 783 | } | |||
| 784 | ||||
| 785 | if (BBLV.isOverdefined()) { | |||
| 786 | // Check whether we're checking at the terminator, and the pointer has | |||
| 787 | // been dereferenced in this block. | |||
| 788 | PointerType *PTy = dyn_cast<PointerType>(Val->getType()); | |||
| 789 | if (PTy && BB->getTerminator() == BBI && | |||
| 790 | isNonNullAtEndOfBlock(Val, BB)) | |||
| 791 | BBLV = ValueLatticeElement::getNot(ConstantPointerNull::get(PTy)); | |||
| 792 | } | |||
| 793 | } | |||
| 794 | ||||
| 795 | Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueSelect( | |||
| 796 | SelectInst *SI, BasicBlock *BB) { | |||
| 797 | // Recurse on our inputs if needed | |||
| 798 | Optional<ValueLatticeElement> OptTrueVal = | |||
| 799 | getBlockValue(SI->getTrueValue(), BB); | |||
| 800 | if (!OptTrueVal) | |||
| 801 | return None; | |||
| 802 | ValueLatticeElement &TrueVal = *OptTrueVal; | |||
| 803 | ||||
| 804 | Optional<ValueLatticeElement> OptFalseVal = | |||
| 805 | getBlockValue(SI->getFalseValue(), BB); | |||
| 806 | if (!OptFalseVal) | |||
| 807 | return None; | |||
| 808 | ValueLatticeElement &FalseVal = *OptFalseVal; | |||
| 809 | ||||
| 810 | if (TrueVal.isConstantRange() && FalseVal.isConstantRange()) { | |||
| 811 | const ConstantRange &TrueCR = TrueVal.getConstantRange(); | |||
| 812 | const ConstantRange &FalseCR = FalseVal.getConstantRange(); | |||
| 813 | Value *LHS = nullptr; | |||
| 814 | Value *RHS = nullptr; | |||
| 815 | SelectPatternResult SPR = matchSelectPattern(SI, LHS, RHS); | |||
| 816 | // Is this a min specifically of our two inputs? (Avoid the risk of | |||
| 817 | // ValueTracking getting smarter looking back past our immediate inputs.) | |||
| 818 | if (SelectPatternResult::isMinOrMax(SPR.Flavor) && | |||
| 819 | LHS == SI->getTrueValue() && RHS == SI->getFalseValue()) { | |||
| 820 | ConstantRange ResultCR = [&]() { | |||
| 821 | switch (SPR.Flavor) { | |||
| 822 | default: | |||
| 823 | llvm_unreachable("unexpected minmax type!")__builtin_unreachable(); | |||
| 824 | case SPF_SMIN: /// Signed minimum | |||
| 825 | return TrueCR.smin(FalseCR); | |||
| 826 | case SPF_UMIN: /// Unsigned minimum | |||
| 827 | return TrueCR.umin(FalseCR); | |||
| 828 | case SPF_SMAX: /// Signed maximum | |||
| 829 | return TrueCR.smax(FalseCR); | |||
| 830 | case SPF_UMAX: /// Unsigned maximum | |||
| 831 | return TrueCR.umax(FalseCR); | |||
| 832 | }; | |||
| 833 | }(); | |||
| 834 | return ValueLatticeElement::getRange( | |||
| 835 | ResultCR, TrueVal.isConstantRangeIncludingUndef() | | |||
| 836 | FalseVal.isConstantRangeIncludingUndef()); | |||
| 837 | } | |||
| 838 | ||||
| 839 | if (SPR.Flavor == SPF_ABS) { | |||
| 840 | if (LHS == SI->getTrueValue()) | |||
| 841 | return ValueLatticeElement::getRange( | |||
| 842 | TrueCR.abs(), TrueVal.isConstantRangeIncludingUndef()); | |||
| 843 | if (LHS == SI->getFalseValue()) | |||
| 844 | return ValueLatticeElement::getRange( | |||
| 845 | FalseCR.abs(), FalseVal.isConstantRangeIncludingUndef()); | |||
| 846 | } | |||
| 847 | ||||
| 848 | if (SPR.Flavor == SPF_NABS) { | |||
| 849 | ConstantRange Zero(APInt::getNullValue(TrueCR.getBitWidth())); | |||
| 850 | if (LHS == SI->getTrueValue()) | |||
| 851 | return ValueLatticeElement::getRange( | |||
| 852 | Zero.sub(TrueCR.abs()), FalseVal.isConstantRangeIncludingUndef()); | |||
| 853 | if (LHS == SI->getFalseValue()) | |||
| 854 | return ValueLatticeElement::getRange( | |||
| 855 | Zero.sub(FalseCR.abs()), FalseVal.isConstantRangeIncludingUndef()); | |||
| 856 | } | |||
| 857 | } | |||
| 858 | ||||
| 859 | // Can we constrain the facts about the true and false values by using the | |||
| 860 | // condition itself? This shows up with idioms like e.g. select(a > 5, a, 5). | |||
| 861 | // TODO: We could potentially refine an overdefined true value above. | |||
| 862 | Value *Cond = SI->getCondition(); | |||
| 863 | TrueVal = intersect(TrueVal, | |||
| 864 | getValueFromCondition(SI->getTrueValue(), Cond, true)); | |||
| 865 | FalseVal = intersect(FalseVal, | |||
| 866 | getValueFromCondition(SI->getFalseValue(), Cond, false)); | |||
| 867 | ||||
| 868 | ValueLatticeElement Result = TrueVal; | |||
| 869 | Result.mergeIn(FalseVal); | |||
| 870 | return Result; | |||
| 871 | } | |||
| 872 | ||||
| 873 | Optional<ConstantRange> LazyValueInfoImpl::getRangeFor(Value *V, | |||
| 874 | Instruction *CxtI, | |||
| 875 | BasicBlock *BB) { | |||
| 876 | Optional<ValueLatticeElement> OptVal = getBlockValue(V, BB); | |||
| 877 | if (!OptVal) | |||
| 878 | return None; | |||
| 879 | ||||
| 880 | ValueLatticeElement &Val = *OptVal; | |||
| 881 | intersectAssumeOrGuardBlockValueConstantRange(V, Val, CxtI); | |||
| 882 | if (Val.isConstantRange()) | |||
| 883 | return Val.getConstantRange(); | |||
| 884 | ||||
| 885 | const unsigned OperandBitWidth = DL.getTypeSizeInBits(V->getType()); | |||
| 886 | return ConstantRange::getFull(OperandBitWidth); | |||
| 887 | } | |||
| 888 | ||||
| 889 | Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueCast( | |||
| 890 | CastInst *CI, BasicBlock *BB) { | |||
| 891 | // Without knowing how wide the input is, we can't analyze it in any useful | |||
| 892 | // way. | |||
| 893 | if (!CI->getOperand(0)->getType()->isSized()) | |||
| 894 | return ValueLatticeElement::getOverdefined(); | |||
| 895 | ||||
| 896 | // Filter out casts we don't know how to reason about before attempting to | |||
| 897 | // recurse on our operand. This can cut a long search short if we know we're | |||
| 898 | // not going to be able to get any useful information anways. | |||
| 899 | switch (CI->getOpcode()) { | |||
| 900 | case Instruction::Trunc: | |||
| 901 | case Instruction::SExt: | |||
| 902 | case Instruction::ZExt: | |||
| 903 | case Instruction::BitCast: | |||
| 904 | break; | |||
| 905 | default: | |||
| 906 | // Unhandled instructions are overdefined. | |||
| 907 | LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()do { } while (false) | |||
| 908 | << "' - overdefined (unknown cast).\n")do { } while (false); | |||
| 909 | return ValueLatticeElement::getOverdefined(); | |||
| 910 | } | |||
| 911 | ||||
| 912 | // Figure out the range of the LHS. If that fails, we still apply the | |||
| 913 | // transfer rule on the full set since we may be able to locally infer | |||
| 914 | // interesting facts. | |||
| 915 | Optional<ConstantRange> LHSRes = getRangeFor(CI->getOperand(0), CI, BB); | |||
| 916 | if (!LHSRes.hasValue()) | |||
| 917 | // More work to do before applying this transfer rule. | |||
| 918 | return None; | |||
| 919 | const ConstantRange &LHSRange = LHSRes.getValue(); | |||
| 920 | ||||
| 921 | const unsigned ResultBitWidth = CI->getType()->getIntegerBitWidth(); | |||
| 922 | ||||
| 923 | // NOTE: We're currently limited by the set of operations that ConstantRange | |||
| 924 | // can evaluate symbolically. Enhancing that set will allows us to analyze | |||
| 925 | // more definitions. | |||
| 926 | return ValueLatticeElement::getRange(LHSRange.castOp(CI->getOpcode(), | |||
| 927 | ResultBitWidth)); | |||
| 928 | } | |||
| 929 | ||||
| 930 | Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueBinaryOpImpl( | |||
| 931 | Instruction *I, BasicBlock *BB, | |||
| 932 | std::function<ConstantRange(const ConstantRange &, | |||
| 933 | const ConstantRange &)> OpFn) { | |||
| 934 | // Figure out the ranges of the operands. If that fails, use a | |||
| 935 | // conservative range, but apply the transfer rule anyways. This | |||
| 936 | // lets us pick up facts from expressions like "and i32 (call i32 | |||
| 937 | // @foo()), 32" | |||
| 938 | Optional<ConstantRange> LHSRes = getRangeFor(I->getOperand(0), I, BB); | |||
| 939 | Optional<ConstantRange> RHSRes = getRangeFor(I->getOperand(1), I, BB); | |||
| 940 | if (!LHSRes.hasValue() || !RHSRes.hasValue()) | |||
| 941 | // More work to do before applying this transfer rule. | |||
| 942 | return None; | |||
| 943 | ||||
| 944 | const ConstantRange &LHSRange = LHSRes.getValue(); | |||
| 945 | const ConstantRange &RHSRange = RHSRes.getValue(); | |||
| 946 | return ValueLatticeElement::getRange(OpFn(LHSRange, RHSRange)); | |||
| 947 | } | |||
| 948 | ||||
| 949 | Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueBinaryOp( | |||
| 950 | BinaryOperator *BO, BasicBlock *BB) { | |||
| 951 | assert(BO->getOperand(0)->getType()->isSized() &&((void)0) | |||
| 952 | "all operands to binary operators are sized")((void)0); | |||
| 953 | if (BO->getOpcode() == Instruction::Xor) { | |||
| 954 | // Xor is the only operation not supported by ConstantRange::binaryOp(). | |||
| 955 | LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()do { } while (false) | |||
| 956 | << "' - overdefined (unknown binary operator).\n")do { } while (false); | |||
| 957 | return ValueLatticeElement::getOverdefined(); | |||
| 958 | } | |||
| 959 | ||||
| 960 | if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(BO)) { | |||
| 961 | unsigned NoWrapKind = 0; | |||
| 962 | if (OBO->hasNoUnsignedWrap()) | |||
| 963 | NoWrapKind |= OverflowingBinaryOperator::NoUnsignedWrap; | |||
| 964 | if (OBO->hasNoSignedWrap()) | |||
| 965 | NoWrapKind |= OverflowingBinaryOperator::NoSignedWrap; | |||
| 966 | ||||
| 967 | return solveBlockValueBinaryOpImpl( | |||
| 968 | BO, BB, | |||
| 969 | [BO, NoWrapKind](const ConstantRange &CR1, const ConstantRange &CR2) { | |||
| 970 | return CR1.overflowingBinaryOp(BO->getOpcode(), CR2, NoWrapKind); | |||
| 971 | }); | |||
| 972 | } | |||
| 973 | ||||
| 974 | return solveBlockValueBinaryOpImpl( | |||
| 975 | BO, BB, [BO](const ConstantRange &CR1, const ConstantRange &CR2) { | |||
| 976 | return CR1.binaryOp(BO->getOpcode(), CR2); | |||
| 977 | }); | |||
| 978 | } | |||
| 979 | ||||
| 980 | Optional<ValueLatticeElement> | |||
| 981 | LazyValueInfoImpl::solveBlockValueOverflowIntrinsic(WithOverflowInst *WO, | |||
| 982 | BasicBlock *BB) { | |||
| 983 | return solveBlockValueBinaryOpImpl( | |||
| 984 | WO, BB, [WO](const ConstantRange &CR1, const ConstantRange &CR2) { | |||
| 985 | return CR1.binaryOp(WO->getBinaryOp(), CR2); | |||
| 986 | }); | |||
| 987 | } | |||
| 988 | ||||
| 989 | Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueIntrinsic( | |||
| 990 | IntrinsicInst *II, BasicBlock *BB) { | |||
| 991 | if (!ConstantRange::isIntrinsicSupported(II->getIntrinsicID())) { | |||
| 992 | LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()do { } while (false) | |||
| 993 | << "' - unknown intrinsic.\n")do { } while (false); | |||
| 994 | return getFromRangeMetadata(II); | |||
| 995 | } | |||
| 996 | ||||
| 997 | SmallVector<ConstantRange, 2> OpRanges; | |||
| 998 | for (Value *Op : II->args()) { | |||
| 999 | Optional<ConstantRange> Range = getRangeFor(Op, II, BB); | |||
| 1000 | if (!Range) | |||
| 1001 | return None; | |||
| 1002 | OpRanges.push_back(*Range); | |||
| 1003 | } | |||
| 1004 | ||||
| 1005 | return ValueLatticeElement::getRange( | |||
| 1006 | ConstantRange::intrinsic(II->getIntrinsicID(), OpRanges)); | |||
| 1007 | } | |||
| 1008 | ||||
| 1009 | Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueExtractValue( | |||
| 1010 | ExtractValueInst *EVI, BasicBlock *BB) { | |||
| 1011 | if (auto *WO = dyn_cast<WithOverflowInst>(EVI->getAggregateOperand())) | |||
| 1012 | if (EVI->getNumIndices() == 1 && *EVI->idx_begin() == 0) | |||
| 1013 | return solveBlockValueOverflowIntrinsic(WO, BB); | |||
| 1014 | ||||
| 1015 | // Handle extractvalue of insertvalue to allow further simplification | |||
| 1016 | // based on replaced with.overflow intrinsics. | |||
| 1017 | if (Value *V = SimplifyExtractValueInst( | |||
| 1018 | EVI->getAggregateOperand(), EVI->getIndices(), | |||
| 1019 | EVI->getModule()->getDataLayout())) | |||
| 1020 | return getBlockValue(V, BB); | |||
| 1021 | ||||
| 1022 | LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()do { } while (false) | |||
| 1023 | << "' - overdefined (unknown extractvalue).\n")do { } while (false); | |||
| 1024 | return ValueLatticeElement::getOverdefined(); | |||
| 1025 | } | |||
| 1026 | ||||
| 1027 | static bool matchICmpOperand(APInt &Offset, Value *LHS, Value *Val, | |||
| 1028 | ICmpInst::Predicate Pred) { | |||
| 1029 | if (LHS == Val) | |||
| 1030 | return true; | |||
| 1031 | ||||
| 1032 | // Handle range checking idiom produced by InstCombine. We will subtract the | |||
| 1033 | // offset from the allowed range for RHS in this case. | |||
| 1034 | const APInt *C; | |||
| 1035 | if (match(LHS, m_Add(m_Specific(Val), m_APInt(C)))) { | |||
| 1036 | Offset = *C; | |||
| 1037 | return true; | |||
| 1038 | } | |||
| 1039 | ||||
| 1040 | // Handle the symmetric case. This appears in saturation patterns like | |||
| 1041 | // (x == 16) ? 16 : (x + 1). | |||
| 1042 | if (match(Val, m_Add(m_Specific(LHS), m_APInt(C)))) { | |||
| 1043 | Offset = -*C; | |||
| 1044 | return true; | |||
| 1045 | } | |||
| 1046 | ||||
| 1047 | // If (x | y) < C, then (x < C) && (y < C). | |||
| 1048 | if (match(LHS, m_c_Or(m_Specific(Val), m_Value())) && | |||
| 1049 | (Pred == ICmpInst::ICMP_ULT || Pred == ICmpInst::ICMP_ULE)) | |||
| 1050 | return true; | |||
| 1051 | ||||
| 1052 | // If (x & y) > C, then (x > C) && (y > C). | |||
| 1053 | if (match(LHS, m_c_And(m_Specific(Val), m_Value())) && | |||
| 1054 | (Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_UGE)) | |||
| 1055 | return true; | |||
| 1056 | ||||
| 1057 | return false; | |||
| 1058 | } | |||
| 1059 | ||||
| 1060 | /// Get value range for a "(Val + Offset) Pred RHS" condition. | |||
| 1061 | static ValueLatticeElement getValueFromSimpleICmpCondition( | |||
| 1062 | CmpInst::Predicate Pred, Value *RHS, const APInt &Offset) { | |||
| 1063 | ConstantRange RHSRange(RHS->getType()->getIntegerBitWidth(), | |||
| 1064 | /*isFullSet=*/true); | |||
| 1065 | if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) | |||
| 1066 | RHSRange = ConstantRange(CI->getValue()); | |||
| 1067 | else if (Instruction *I = dyn_cast<Instruction>(RHS)) | |||
| 1068 | if (auto *Ranges = I->getMetadata(LLVMContext::MD_range)) | |||
| 1069 | RHSRange = getConstantRangeFromMetadata(*Ranges); | |||
| 1070 | ||||
| 1071 | ConstantRange TrueValues = | |||
| 1072 | ConstantRange::makeAllowedICmpRegion(Pred, RHSRange); | |||
| 1073 | return ValueLatticeElement::getRange(TrueValues.subtract(Offset)); | |||
| 1074 | } | |||
| 1075 | ||||
| 1076 | static ValueLatticeElement getValueFromICmpCondition(Value *Val, ICmpInst *ICI, | |||
| 1077 | bool isTrueDest) { | |||
| 1078 | Value *LHS = ICI->getOperand(0); | |||
| 1079 | Value *RHS = ICI->getOperand(1); | |||
| 1080 | ||||
| 1081 | // Get the predicate that must hold along the considered edge. | |||
| 1082 | CmpInst::Predicate EdgePred = | |||
| 1083 | isTrueDest ? ICI->getPredicate() : ICI->getInversePredicate(); | |||
| 1084 | ||||
| 1085 | if (isa<Constant>(RHS)) { | |||
| 1086 | if (ICI->isEquality() && LHS == Val) { | |||
| 1087 | if (EdgePred == ICmpInst::ICMP_EQ) | |||
| 1088 | return ValueLatticeElement::get(cast<Constant>(RHS)); | |||
| 1089 | else if (!isa<UndefValue>(RHS)) | |||
| 1090 | return ValueLatticeElement::getNot(cast<Constant>(RHS)); | |||
| 1091 | } | |||
| 1092 | } | |||
| 1093 | ||||
| 1094 | Type *Ty = Val->getType(); | |||
| 1095 | if (!Ty->isIntegerTy()) | |||
| 1096 | return ValueLatticeElement::getOverdefined(); | |||
| 1097 | ||||
| 1098 | APInt Offset(Ty->getScalarSizeInBits(), 0); | |||
| 1099 | if (matchICmpOperand(Offset, LHS, Val, EdgePred)) | |||
| 1100 | return getValueFromSimpleICmpCondition(EdgePred, RHS, Offset); | |||
| 1101 | ||||
| 1102 | CmpInst::Predicate SwappedPred = CmpInst::getSwappedPredicate(EdgePred); | |||
| 1103 | if (matchICmpOperand(Offset, RHS, Val, SwappedPred)) | |||
| 1104 | return getValueFromSimpleICmpCondition(SwappedPred, LHS, Offset); | |||
| 1105 | ||||
| 1106 | const APInt *Mask, *C; | |||
| 1107 | if (match(LHS, m_And(m_Specific(Val), m_APInt(Mask))) && | |||
| 1108 | match(RHS, m_APInt(C))) { | |||
| 1109 | // If (Val & Mask) == C then all the masked bits are known and we can | |||
| 1110 | // compute a value range based on that. | |||
| 1111 | if (EdgePred == ICmpInst::ICMP_EQ) { | |||
| 1112 | KnownBits Known; | |||
| 1113 | Known.Zero = ~*C & *Mask; | |||
| 1114 | Known.One = *C & *Mask; | |||
| 1115 | return ValueLatticeElement::getRange( | |||
| 1116 | ConstantRange::fromKnownBits(Known, /*IsSigned*/ false)); | |||
| 1117 | } | |||
| 1118 | // If (Val & Mask) != 0 then the value must be larger than the lowest set | |||
| 1119 | // bit of Mask. | |||
| 1120 | if (EdgePred == ICmpInst::ICMP_NE && !Mask->isNullValue() && | |||
| 1121 | C->isNullValue()) { | |||
| 1122 | unsigned BitWidth = Ty->getIntegerBitWidth(); | |||
| 1123 | return ValueLatticeElement::getRange(ConstantRange::getNonEmpty( | |||
| 1124 | APInt::getOneBitSet(BitWidth, Mask->countTrailingZeros()), | |||
| 1125 | APInt::getNullValue(BitWidth))); | |||
| 1126 | } | |||
| 1127 | } | |||
| 1128 | ||||
| 1129 | return ValueLatticeElement::getOverdefined(); | |||
| 1130 | } | |||
| 1131 | ||||
| 1132 | // Handle conditions of the form | |||
| 1133 | // extractvalue(op.with.overflow(%x, C), 1). | |||
| 1134 | static ValueLatticeElement getValueFromOverflowCondition( | |||
| 1135 | Value *Val, WithOverflowInst *WO, bool IsTrueDest) { | |||
| 1136 | // TODO: This only works with a constant RHS for now. We could also compute | |||
| 1137 | // the range of the RHS, but this doesn't fit into the current structure of | |||
| 1138 | // the edge value calculation. | |||
| 1139 | const APInt *C; | |||
| 1140 | if (WO->getLHS() != Val || !match(WO->getRHS(), m_APInt(C))) | |||
| 1141 | return ValueLatticeElement::getOverdefined(); | |||
| 1142 | ||||
| 1143 | // Calculate the possible values of %x for which no overflow occurs. | |||
| 1144 | ConstantRange NWR = ConstantRange::makeExactNoWrapRegion( | |||
| 1145 | WO->getBinaryOp(), *C, WO->getNoWrapKind()); | |||
| 1146 | ||||
| 1147 | // If overflow is false, %x is constrained to NWR. If overflow is true, %x is | |||
| 1148 | // constrained to it's inverse (all values that might cause overflow). | |||
| 1149 | if (IsTrueDest) | |||
| 1150 | NWR = NWR.inverse(); | |||
| 1151 | return ValueLatticeElement::getRange(NWR); | |||
| 1152 | } | |||
| 1153 | ||||
| 1154 | static Optional<ValueLatticeElement> | |||
| 1155 | getValueFromConditionImpl(Value *Val, Value *Cond, bool isTrueDest, | |||
| 1156 | bool isRevisit, | |||
| 1157 | SmallDenseMap<Value *, ValueLatticeElement> &Visited, | |||
| 1158 | SmallVectorImpl<Value *> &Worklist) { | |||
| 1159 | if (!isRevisit) { | |||
| 1160 | if (ICmpInst *ICI = dyn_cast<ICmpInst>(Cond)) | |||
| 1161 | return getValueFromICmpCondition(Val, ICI, isTrueDest); | |||
| 1162 | ||||
| 1163 | if (auto *EVI = dyn_cast<ExtractValueInst>(Cond)) | |||
| 1164 | if (auto *WO = dyn_cast<WithOverflowInst>(EVI->getAggregateOperand())) | |||
| 1165 | if (EVI->getNumIndices() == 1 && *EVI->idx_begin() == 1) | |||
| 1166 | return getValueFromOverflowCondition(Val, WO, isTrueDest); | |||
| 1167 | } | |||
| 1168 | ||||
| 1169 | Value *L, *R; | |||
| 1170 | bool IsAnd; | |||
| 1171 | if (match(Cond, m_LogicalAnd(m_Value(L), m_Value(R)))) | |||
| 1172 | IsAnd = true; | |||
| 1173 | else if (match(Cond, m_LogicalOr(m_Value(L), m_Value(R)))) | |||
| 1174 | IsAnd = false; | |||
| 1175 | else | |||
| 1176 | return ValueLatticeElement::getOverdefined(); | |||
| 1177 | ||||
| 1178 | auto LV = Visited.find(L); | |||
| 1179 | auto RV = Visited.find(R); | |||
| 1180 | ||||
| 1181 | // if (L && R) -> intersect L and R | |||
| 1182 | // if (!(L || R)) -> intersect L and R | |||
| 1183 | // if (L || R) -> union L and R | |||
| 1184 | // if (!(L && R)) -> union L and R | |||
| 1185 | if ((isTrueDest ^ IsAnd) && (LV != Visited.end())) { | |||
| 1186 | ValueLatticeElement V = LV->second; | |||
| 1187 | if (V.isOverdefined()) | |||
| 1188 | return V; | |||
| 1189 | if (RV != Visited.end()) { | |||
| 1190 | V.mergeIn(RV->second); | |||
| 1191 | return V; | |||
| 1192 | } | |||
| 1193 | } | |||
| 1194 | ||||
| 1195 | if (LV == Visited.end() || RV == Visited.end()) { | |||
| 1196 | assert(!isRevisit)((void)0); | |||
| 1197 | if (LV == Visited.end()) | |||
| 1198 | Worklist.push_back(L); | |||
| 1199 | if (RV == Visited.end()) | |||
| 1200 | Worklist.push_back(R); | |||
| 1201 | return None; | |||
| 1202 | } | |||
| 1203 | ||||
| 1204 | return intersect(LV->second, RV->second); | |||
| 1205 | } | |||
| 1206 | ||||
| 1207 | ValueLatticeElement getValueFromCondition(Value *Val, Value *Cond, | |||
| 1208 | bool isTrueDest) { | |||
| 1209 | assert(Cond && "precondition")((void)0); | |||
| 1210 | SmallDenseMap<Value*, ValueLatticeElement> Visited; | |||
| 1211 | SmallVector<Value *> Worklist; | |||
| 1212 | ||||
| 1213 | Worklist.push_back(Cond); | |||
| 1214 | do { | |||
| 1215 | Value *CurrentCond = Worklist.back(); | |||
| 1216 | // Insert an Overdefined placeholder into the set to prevent | |||
| 1217 | // infinite recursion if there exists IRs that use not | |||
| 1218 | // dominated by its def as in this example: | |||
| 1219 | // "%tmp3 = or i1 undef, %tmp4" | |||
| 1220 | // "%tmp4 = or i1 undef, %tmp3" | |||
| 1221 | auto Iter = | |||
| 1222 | Visited.try_emplace(CurrentCond, ValueLatticeElement::getOverdefined()); | |||
| 1223 | bool isRevisit = !Iter.second; | |||
| 1224 | Optional<ValueLatticeElement> Result = getValueFromConditionImpl( | |||
| 1225 | Val, CurrentCond, isTrueDest, isRevisit, Visited, Worklist); | |||
| 1226 | if (Result) { | |||
| 1227 | Visited[CurrentCond] = *Result; | |||
| 1228 | Worklist.pop_back(); | |||
| 1229 | } | |||
| 1230 | } while (!Worklist.empty()); | |||
| 1231 | ||||
| 1232 | auto Result = Visited.find(Cond); | |||
| 1233 | assert(Result != Visited.end())((void)0); | |||
| 1234 | return Result->second; | |||
| 1235 | } | |||
| 1236 | ||||
| 1237 | // Return true if Usr has Op as an operand, otherwise false. | |||
| 1238 | static bool usesOperand(User *Usr, Value *Op) { | |||
| 1239 | return is_contained(Usr->operands(), Op); | |||
| 1240 | } | |||
| 1241 | ||||
| 1242 | // Return true if the instruction type of Val is supported by | |||
| 1243 | // constantFoldUser(). Currently CastInst, BinaryOperator and FreezeInst only. | |||
| 1244 | // Call this before calling constantFoldUser() to find out if it's even worth | |||
| 1245 | // attempting to call it. | |||
| 1246 | static bool isOperationFoldable(User *Usr) { | |||
| 1247 | return isa<CastInst>(Usr) || isa<BinaryOperator>(Usr) || isa<FreezeInst>(Usr); | |||
| 1248 | } | |||
| 1249 | ||||
| 1250 | // Check if Usr can be simplified to an integer constant when the value of one | |||
| 1251 | // of its operands Op is an integer constant OpConstVal. If so, return it as an | |||
| 1252 | // lattice value range with a single element or otherwise return an overdefined | |||
| 1253 | // lattice value. | |||
| 1254 | static ValueLatticeElement constantFoldUser(User *Usr, Value *Op, | |||
| 1255 | const APInt &OpConstVal, | |||
| 1256 | const DataLayout &DL) { | |||
| 1257 | assert(isOperationFoldable(Usr) && "Precondition")((void)0); | |||
| 1258 | Constant* OpConst = Constant::getIntegerValue(Op->getType(), OpConstVal); | |||
| 1259 | // Check if Usr can be simplified to a constant. | |||
| 1260 | if (auto *CI = dyn_cast<CastInst>(Usr)) { | |||
| 1261 | assert(CI->getOperand(0) == Op && "Operand 0 isn't Op")((void)0); | |||
| 1262 | if (auto *C = dyn_cast_or_null<ConstantInt>( | |||
| 1263 | SimplifyCastInst(CI->getOpcode(), OpConst, | |||
| 1264 | CI->getDestTy(), DL))) { | |||
| 1265 | return ValueLatticeElement::getRange(ConstantRange(C->getValue())); | |||
| 1266 | } | |||
| 1267 | } else if (auto *BO = dyn_cast<BinaryOperator>(Usr)) { | |||
| 1268 | bool Op0Match = BO->getOperand(0) == Op; | |||
| 1269 | bool Op1Match = BO->getOperand(1) == Op; | |||
| 1270 | assert((Op0Match || Op1Match) &&((void)0) | |||
| 1271 | "Operand 0 nor Operand 1 isn't a match")((void)0); | |||
| 1272 | Value *LHS = Op0Match ? OpConst : BO->getOperand(0); | |||
| 1273 | Value *RHS = Op1Match ? OpConst : BO->getOperand(1); | |||
| 1274 | if (auto *C = dyn_cast_or_null<ConstantInt>( | |||
| 1275 | SimplifyBinOp(BO->getOpcode(), LHS, RHS, DL))) { | |||
| 1276 | return ValueLatticeElement::getRange(ConstantRange(C->getValue())); | |||
| 1277 | } | |||
| 1278 | } else if (isa<FreezeInst>(Usr)) { | |||
| 1279 | assert(cast<FreezeInst>(Usr)->getOperand(0) == Op && "Operand 0 isn't Op")((void)0); | |||
| 1280 | return ValueLatticeElement::getRange(ConstantRange(OpConstVal)); | |||
| 1281 | } | |||
| 1282 | return ValueLatticeElement::getOverdefined(); | |||
| 1283 | } | |||
| 1284 | ||||
| 1285 | /// Compute the value of Val on the edge BBFrom -> BBTo. Returns false if | |||
| 1286 | /// Val is not constrained on the edge. Result is unspecified if return value | |||
| 1287 | /// is false. | |||
| 1288 | static Optional<ValueLatticeElement> getEdgeValueLocal(Value *Val, | |||
| 1289 | BasicBlock *BBFrom, | |||
| 1290 | BasicBlock *BBTo) { | |||
| 1291 | // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we | |||
| 1292 | // know that v != 0. | |||
| 1293 | if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) { | |||
| 1294 | // If this is a conditional branch and only one successor goes to BBTo, then | |||
| 1295 | // we may be able to infer something from the condition. | |||
| 1296 | if (BI->isConditional() && | |||
| 1297 | BI->getSuccessor(0) != BI->getSuccessor(1)) { | |||
| 1298 | bool isTrueDest = BI->getSuccessor(0) == BBTo; | |||
| 1299 | assert(BI->getSuccessor(!isTrueDest) == BBTo &&((void)0) | |||
| 1300 | "BBTo isn't a successor of BBFrom")((void)0); | |||
| 1301 | Value *Condition = BI->getCondition(); | |||
| 1302 | ||||
| 1303 | // If V is the condition of the branch itself, then we know exactly what | |||
| 1304 | // it is. | |||
| 1305 | if (Condition == Val) | |||
| 1306 | return ValueLatticeElement::get(ConstantInt::get( | |||
| 1307 | Type::getInt1Ty(Val->getContext()), isTrueDest)); | |||
| 1308 | ||||
| 1309 | // If the condition of the branch is an equality comparison, we may be | |||
| 1310 | // able to infer the value. | |||
| 1311 | ValueLatticeElement Result = getValueFromCondition(Val, Condition, | |||
| 1312 | isTrueDest); | |||
| 1313 | if (!Result.isOverdefined()) | |||
| 1314 | return Result; | |||
| 1315 | ||||
| 1316 | if (User *Usr = dyn_cast<User>(Val)) { | |||
| 1317 | assert(Result.isOverdefined() && "Result isn't overdefined")((void)0); | |||
| 1318 | // Check with isOperationFoldable() first to avoid linearly iterating | |||
| 1319 | // over the operands unnecessarily which can be expensive for | |||
| 1320 | // instructions with many operands. | |||
| 1321 | if (isa<IntegerType>(Usr->getType()) && isOperationFoldable(Usr)) { | |||
| 1322 | const DataLayout &DL = BBTo->getModule()->getDataLayout(); | |||
| 1323 | if (usesOperand(Usr, Condition)) { | |||
| 1324 | // If Val has Condition as an operand and Val can be folded into a | |||
| 1325 | // constant with either Condition == true or Condition == false, | |||
| 1326 | // propagate the constant. | |||
| 1327 | // eg. | |||
| 1328 | // ; %Val is true on the edge to %then. | |||
| 1329 | // %Val = and i1 %Condition, true. | |||
| 1330 | // br %Condition, label %then, label %else | |||
| 1331 | APInt ConditionVal(1, isTrueDest ? 1 : 0); | |||
| 1332 | Result = constantFoldUser(Usr, Condition, ConditionVal, DL); | |||
| 1333 | } else { | |||
| 1334 | // If one of Val's operand has an inferred value, we may be able to | |||
| 1335 | // infer the value of Val. | |||
| 1336 | // eg. | |||
| 1337 | // ; %Val is 94 on the edge to %then. | |||
| 1338 | // %Val = add i8 %Op, 1 | |||
| 1339 | // %Condition = icmp eq i8 %Op, 93 | |||
| 1340 | // br i1 %Condition, label %then, label %else | |||
| 1341 | for (unsigned i = 0; i < Usr->getNumOperands(); ++i) { | |||
| 1342 | Value *Op = Usr->getOperand(i); | |||
| 1343 | ValueLatticeElement OpLatticeVal = | |||
| 1344 | getValueFromCondition(Op, Condition, isTrueDest); | |||
| 1345 | if (Optional<APInt> OpConst = OpLatticeVal.asConstantInteger()) { | |||
| 1346 | Result = constantFoldUser(Usr, Op, OpConst.getValue(), DL); | |||
| 1347 | break; | |||
| 1348 | } | |||
| 1349 | } | |||
| 1350 | } | |||
| 1351 | } | |||
| 1352 | } | |||
| 1353 | if (!Result.isOverdefined()) | |||
| 1354 | return Result; | |||
| 1355 | } | |||
| 1356 | } | |||
| 1357 | ||||
| 1358 | // If the edge was formed by a switch on the value, then we may know exactly | |||
| 1359 | // what it is. | |||
| 1360 | if (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) { | |||
| 1361 | Value *Condition = SI->getCondition(); | |||
| 1362 | if (!isa<IntegerType>(Val->getType())) | |||
| 1363 | return None; | |||
| 1364 | bool ValUsesConditionAndMayBeFoldable = false; | |||
| 1365 | if (Condition != Val) { | |||
| 1366 | // Check if Val has Condition as an operand. | |||
| 1367 | if (User *Usr = dyn_cast<User>(Val)) | |||
| 1368 | ValUsesConditionAndMayBeFoldable = isOperationFoldable(Usr) && | |||
| 1369 | usesOperand(Usr, Condition); | |||
| 1370 | if (!ValUsesConditionAndMayBeFoldable) | |||
| 1371 | return None; | |||
| 1372 | } | |||
| 1373 | assert((Condition == Val || ValUsesConditionAndMayBeFoldable) &&((void)0) | |||
| 1374 | "Condition != Val nor Val doesn't use Condition")((void)0); | |||
| 1375 | ||||
| 1376 | bool DefaultCase = SI->getDefaultDest() == BBTo; | |||
| 1377 | unsigned BitWidth = Val->getType()->getIntegerBitWidth(); | |||
| 1378 | ConstantRange EdgesVals(BitWidth, DefaultCase/*isFullSet*/); | |||
| 1379 | ||||
| 1380 | for (auto Case : SI->cases()) { | |||
| 1381 | APInt CaseValue = Case.getCaseValue()->getValue(); | |||
| 1382 | ConstantRange EdgeVal(CaseValue); | |||
| 1383 | if (ValUsesConditionAndMayBeFoldable) { | |||
| 1384 | User *Usr = cast<User>(Val); | |||
| 1385 | const DataLayout &DL = BBTo->getModule()->getDataLayout(); | |||
| 1386 | ValueLatticeElement EdgeLatticeVal = | |||
| 1387 | constantFoldUser(Usr, Condition, CaseValue, DL); | |||
| 1388 | if (EdgeLatticeVal.isOverdefined()) | |||
| 1389 | return None; | |||
| 1390 | EdgeVal = EdgeLatticeVal.getConstantRange(); | |||
| 1391 | } | |||
| 1392 | if (DefaultCase) { | |||
| 1393 | // It is possible that the default destination is the destination of | |||
| 1394 | // some cases. We cannot perform difference for those cases. | |||
| 1395 | // We know Condition != CaseValue in BBTo. In some cases we can use | |||
| 1396 | // this to infer Val == f(Condition) is != f(CaseValue). For now, we | |||
| 1397 | // only do this when f is identity (i.e. Val == Condition), but we | |||
| 1398 | // should be able to do this for any injective f. | |||
| 1399 | if (Case.getCaseSuccessor() != BBTo && Condition == Val) | |||
| 1400 | EdgesVals = EdgesVals.difference(EdgeVal); | |||
| 1401 | } else if (Case.getCaseSuccessor() == BBTo) | |||
| 1402 | EdgesVals = EdgesVals.unionWith(EdgeVal); | |||
| 1403 | } | |||
| 1404 | return ValueLatticeElement::getRange(std::move(EdgesVals)); | |||
| 1405 | } | |||
| 1406 | return None; | |||
| 1407 | } | |||
| 1408 | ||||
| 1409 | /// Compute the value of Val on the edge BBFrom -> BBTo or the value at | |||
| 1410 | /// the basic block if the edge does not constrain Val. | |||
| 1411 | Optional<ValueLatticeElement> LazyValueInfoImpl::getEdgeValue( | |||
| 1412 | Value *Val, BasicBlock *BBFrom, BasicBlock *BBTo, Instruction *CxtI) { | |||
| 1413 | // If already a constant, there is nothing to compute. | |||
| 1414 | if (Constant *VC = dyn_cast<Constant>(Val)) | |||
| 1415 | return ValueLatticeElement::get(VC); | |||
| 1416 | ||||
| 1417 | ValueLatticeElement LocalResult = getEdgeValueLocal(Val, BBFrom, BBTo) | |||
| 1418 | .getValueOr(ValueLatticeElement::getOverdefined()); | |||
| 1419 | if (hasSingleValue(LocalResult)) | |||
| 1420 | // Can't get any more precise here | |||
| 1421 | return LocalResult; | |||
| 1422 | ||||
| 1423 | Optional<ValueLatticeElement> OptInBlock = getBlockValue(Val, BBFrom); | |||
| 1424 | if (!OptInBlock) | |||
| 1425 | return None; | |||
| 1426 | ValueLatticeElement &InBlock = *OptInBlock; | |||
| 1427 | ||||
| 1428 | // Try to intersect ranges of the BB and the constraint on the edge. | |||
| 1429 | intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock, | |||
| 1430 | BBFrom->getTerminator()); | |||
| 1431 | // We can use the context instruction (generically the ultimate instruction | |||
| 1432 | // the calling pass is trying to simplify) here, even though the result of | |||
| 1433 | // this function is generally cached when called from the solve* functions | |||
| 1434 | // (and that cached result might be used with queries using a different | |||
| 1435 | // context instruction), because when this function is called from the solve* | |||
| 1436 | // functions, the context instruction is not provided. When called from | |||
| 1437 | // LazyValueInfoImpl::getValueOnEdge, the context instruction is provided, | |||
| 1438 | // but then the result is not cached. | |||
| 1439 | intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock, CxtI); | |||
| 1440 | ||||
| 1441 | return intersect(LocalResult, InBlock); | |||
| 1442 | } | |||
| 1443 | ||||
| 1444 | ValueLatticeElement LazyValueInfoImpl::getValueInBlock(Value *V, BasicBlock *BB, | |||
| 1445 | Instruction *CxtI) { | |||
| 1446 | LLVM_DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '"do { } while (false) | |||
| 1447 | << BB->getName() << "'\n")do { } while (false); | |||
| 1448 | ||||
| 1449 | assert(BlockValueStack.empty() && BlockValueSet.empty())((void)0); | |||
| 1450 | Optional<ValueLatticeElement> OptResult = getBlockValue(V, BB); | |||
| 1451 | if (!OptResult) { | |||
| 1452 | solve(); | |||
| 1453 | OptResult = getBlockValue(V, BB); | |||
| 1454 | assert(OptResult && "Value not available after solving")((void)0); | |||
| 1455 | } | |||
| 1456 | ValueLatticeElement Result = *OptResult; | |||
| 1457 | intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI); | |||
| 1458 | ||||
| 1459 | LLVM_DEBUG(dbgs() << " Result = " << Result << "\n")do { } while (false); | |||
| 1460 | return Result; | |||
| 1461 | } | |||
| 1462 | ||||
| 1463 | ValueLatticeElement LazyValueInfoImpl::getValueAt(Value *V, Instruction *CxtI) { | |||
| 1464 | LLVM_DEBUG(dbgs() << "LVI Getting value " << *V << " at '" << CxtI->getName()do { } while (false) | |||
| 1465 | << "'\n")do { } while (false); | |||
| 1466 | ||||
| 1467 | if (auto *C = dyn_cast<Constant>(V)) | |||
| 1468 | return ValueLatticeElement::get(C); | |||
| 1469 | ||||
| 1470 | ValueLatticeElement Result = ValueLatticeElement::getOverdefined(); | |||
| 1471 | if (auto *I = dyn_cast<Instruction>(V)) | |||
| 1472 | Result = getFromRangeMetadata(I); | |||
| 1473 | intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI); | |||
| 1474 | ||||
| 1475 | LLVM_DEBUG(dbgs() << " Result = " << Result << "\n")do { } while (false); | |||
| 1476 | return Result; | |||
| 1477 | } | |||
| 1478 | ||||
| 1479 | ValueLatticeElement LazyValueInfoImpl:: | |||
| 1480 | getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB, | |||
| 1481 | Instruction *CxtI) { | |||
| 1482 | LLVM_DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '"do { } while (false) | |||
| 1483 | << FromBB->getName() << "' to '" << ToBB->getName()do { } while (false) | |||
| 1484 | << "'\n")do { } while (false); | |||
| 1485 | ||||
| 1486 | Optional<ValueLatticeElement> Result = getEdgeValue(V, FromBB, ToBB, CxtI); | |||
| 1487 | if (!Result) { | |||
| 1488 | solve(); | |||
| 1489 | Result = getEdgeValue(V, FromBB, ToBB, CxtI); | |||
| 1490 | assert(Result && "More work to do after problem solved?")((void)0); | |||
| 1491 | } | |||
| 1492 | ||||
| 1493 | LLVM_DEBUG(dbgs() << " Result = " << *Result << "\n")do { } while (false); | |||
| 1494 | return *Result; | |||
| 1495 | } | |||
| 1496 | ||||
| 1497 | void LazyValueInfoImpl::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc, | |||
| 1498 | BasicBlock *NewSucc) { | |||
| 1499 | TheCache.threadEdgeImpl(OldSucc, NewSucc); | |||
| 1500 | } | |||
| 1501 | ||||
| 1502 | //===----------------------------------------------------------------------===// | |||
| 1503 | // LazyValueInfo Impl | |||
| 1504 | //===----------------------------------------------------------------------===// | |||
| 1505 | ||||
| 1506 | /// This lazily constructs the LazyValueInfoImpl. | |||
| 1507 | static LazyValueInfoImpl &getImpl(void *&PImpl, AssumptionCache *AC, | |||
| 1508 | const Module *M) { | |||
| 1509 | if (!PImpl) { | |||
| 1510 | assert(M && "getCache() called with a null Module")((void)0); | |||
| 1511 | const DataLayout &DL = M->getDataLayout(); | |||
| 1512 | Function *GuardDecl = M->getFunction( | |||
| 1513 | Intrinsic::getName(Intrinsic::experimental_guard)); | |||
| 1514 | PImpl = new LazyValueInfoImpl(AC, DL, GuardDecl); | |||
| 1515 | } | |||
| 1516 | return *static_cast<LazyValueInfoImpl*>(PImpl); | |||
| 1517 | } | |||
| 1518 | ||||
| 1519 | bool LazyValueInfoWrapperPass::runOnFunction(Function &F) { | |||
| 1520 | Info.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F); | |||
| 1521 | Info.TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F); | |||
| 1522 | ||||
| 1523 | if (Info.PImpl) | |||
| 1524 | getImpl(Info.PImpl, Info.AC, F.getParent()).clear(); | |||
| 1525 | ||||
| 1526 | // Fully lazy. | |||
| 1527 | return false; | |||
| 1528 | } | |||
| 1529 | ||||
| 1530 | void LazyValueInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { | |||
| 1531 | AU.setPreservesAll(); | |||
| 1532 | AU.addRequired<AssumptionCacheTracker>(); | |||
| 1533 | AU.addRequired<TargetLibraryInfoWrapperPass>(); | |||
| 1534 | } | |||
| 1535 | ||||
| 1536 | LazyValueInfo &LazyValueInfoWrapperPass::getLVI() { return Info; } | |||
| 1537 | ||||
| 1538 | LazyValueInfo::~LazyValueInfo() { releaseMemory(); } | |||
| 1539 | ||||
| 1540 | void LazyValueInfo::releaseMemory() { | |||
| 1541 | // If the cache was allocated, free it. | |||
| 1542 | if (PImpl) { | |||
| 1543 | delete &getImpl(PImpl, AC, nullptr); | |||
| 1544 | PImpl = nullptr; | |||
| 1545 | } | |||
| 1546 | } | |||
| 1547 | ||||
| 1548 | bool LazyValueInfo::invalidate(Function &F, const PreservedAnalyses &PA, | |||
| 1549 | FunctionAnalysisManager::Invalidator &Inv) { | |||
| 1550 | // We need to invalidate if we have either failed to preserve this analyses | |||
| 1551 | // result directly or if any of its dependencies have been invalidated. | |||
| 1552 | auto PAC = PA.getChecker<LazyValueAnalysis>(); | |||
| 1553 | if (!(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>())) | |||
| 1554 | return true; | |||
| 1555 | ||||
| 1556 | return false; | |||
| 1557 | } | |||
| 1558 | ||||
| 1559 | void LazyValueInfoWrapperPass::releaseMemory() { Info.releaseMemory(); } | |||
| 1560 | ||||
| 1561 | LazyValueInfo LazyValueAnalysis::run(Function &F, | |||
| 1562 | FunctionAnalysisManager &FAM) { | |||
| 1563 | auto &AC = FAM.getResult<AssumptionAnalysis>(F); | |||
| 1564 | auto &TLI = FAM.getResult<TargetLibraryAnalysis>(F); | |||
| 1565 | ||||
| 1566 | return LazyValueInfo(&AC, &F.getParent()->getDataLayout(), &TLI); | |||
| 1567 | } | |||
| 1568 | ||||
| 1569 | /// Returns true if we can statically tell that this value will never be a | |||
| 1570 | /// "useful" constant. In practice, this means we've got something like an | |||
| 1571 | /// alloca or a malloc call for which a comparison against a constant can | |||
| 1572 | /// only be guarding dead code. Note that we are potentially giving up some | |||
| 1573 | /// precision in dead code (a constant result) in favour of avoiding a | |||
| 1574 | /// expensive search for a easily answered common query. | |||
| 1575 | static bool isKnownNonConstant(Value *V) { | |||
| 1576 | V = V->stripPointerCasts(); | |||
| 1577 | // The return val of alloc cannot be a Constant. | |||
| 1578 | if (isa<AllocaInst>(V)) | |||
| 1579 | return true; | |||
| 1580 | return false; | |||
| 1581 | } | |||
| 1582 | ||||
| 1583 | Constant *LazyValueInfo::getConstant(Value *V, Instruction *CxtI) { | |||
| 1584 | // Bail out early if V is known not to be a Constant. | |||
| 1585 | if (isKnownNonConstant(V)) | |||
| 1586 | return nullptr; | |||
| 1587 | ||||
| 1588 | BasicBlock *BB = CxtI->getParent(); | |||
| 1589 | ValueLatticeElement Result = | |||
| 1590 | getImpl(PImpl, AC, BB->getModule()).getValueInBlock(V, BB, CxtI); | |||
| 1591 | ||||
| 1592 | if (Result.isConstant()) | |||
| 1593 | return Result.getConstant(); | |||
| 1594 | if (Result.isConstantRange()) { | |||
| 1595 | const ConstantRange &CR = Result.getConstantRange(); | |||
| 1596 | if (const APInt *SingleVal = CR.getSingleElement()) | |||
| 1597 | return ConstantInt::get(V->getContext(), *SingleVal); | |||
| 1598 | } | |||
| 1599 | return nullptr; | |||
| 1600 | } | |||
| 1601 | ||||
| 1602 | ConstantRange LazyValueInfo::getConstantRange(Value *V, Instruction *CxtI, | |||
| 1603 | bool UndefAllowed) { | |||
| 1604 | assert(V->getType()->isIntegerTy())((void)0); | |||
| 1605 | unsigned Width = V->getType()->getIntegerBitWidth(); | |||
| 1606 | BasicBlock *BB = CxtI->getParent(); | |||
| 1607 | ValueLatticeElement Result = | |||
| 1608 | getImpl(PImpl, AC, BB->getModule()).getValueInBlock(V, BB, CxtI); | |||
| 1609 | if (Result.isUnknown()) | |||
| 1610 | return ConstantRange::getEmpty(Width); | |||
| 1611 | if (Result.isConstantRange(UndefAllowed)) | |||
| 1612 | return Result.getConstantRange(UndefAllowed); | |||
| 1613 | // We represent ConstantInt constants as constant ranges but other kinds | |||
| 1614 | // of integer constants, i.e. ConstantExpr will be tagged as constants | |||
| 1615 | assert(!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) &&((void)0) | |||
| 1616 | "ConstantInt value must be represented as constantrange")((void)0); | |||
| 1617 | return ConstantRange::getFull(Width); | |||
| 1618 | } | |||
| 1619 | ||||
| 1620 | /// Determine whether the specified value is known to be a | |||
| 1621 | /// constant on the specified edge. Return null if not. | |||
| 1622 | Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB, | |||
| 1623 | BasicBlock *ToBB, | |||
| 1624 | Instruction *CxtI) { | |||
| 1625 | Module *M = FromBB->getModule(); | |||
| 1626 | ValueLatticeElement Result = | |||
| 1627 | getImpl(PImpl, AC, M).getValueOnEdge(V, FromBB, ToBB, CxtI); | |||
| 1628 | ||||
| 1629 | if (Result.isConstant()) | |||
| 1630 | return Result.getConstant(); | |||
| 1631 | if (Result.isConstantRange()) { | |||
| 1632 | const ConstantRange &CR = Result.getConstantRange(); | |||
| 1633 | if (const APInt *SingleVal = CR.getSingleElement()) | |||
| 1634 | return ConstantInt::get(V->getContext(), *SingleVal); | |||
| 1635 | } | |||
| 1636 | return nullptr; | |||
| 1637 | } | |||
| 1638 | ||||
| 1639 | ConstantRange LazyValueInfo::getConstantRangeOnEdge(Value *V, | |||
| 1640 | BasicBlock *FromBB, | |||
| 1641 | BasicBlock *ToBB, | |||
| 1642 | Instruction *CxtI) { | |||
| 1643 | unsigned Width = V->getType()->getIntegerBitWidth(); | |||
| 1644 | Module *M = FromBB->getModule(); | |||
| 1645 | ValueLatticeElement Result = | |||
| 1646 | getImpl(PImpl, AC, M).getValueOnEdge(V, FromBB, ToBB, CxtI); | |||
| 1647 | ||||
| 1648 | if (Result.isUnknown()) | |||
| ||||
| 1649 | return ConstantRange::getEmpty(Width); | |||
| 1650 | if (Result.isConstantRange()) | |||
| 1651 | return Result.getConstantRange(); | |||
| 1652 | // We represent ConstantInt constants as constant ranges but other kinds | |||
| 1653 | // of integer constants, i.e. ConstantExpr will be tagged as constants | |||
| 1654 | assert(!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) &&((void)0) | |||
| 1655 | "ConstantInt value must be represented as constantrange")((void)0); | |||
| 1656 | return ConstantRange::getFull(Width); | |||
| 1657 | } | |||
| 1658 | ||||
| 1659 | static LazyValueInfo::Tristate | |||
| 1660 | getPredicateResult(unsigned Pred, Constant *C, const ValueLatticeElement &Val, | |||
| 1661 | const DataLayout &DL, TargetLibraryInfo *TLI) { | |||
| 1662 | // If we know the value is a constant, evaluate the conditional. | |||
| 1663 | Constant *Res = nullptr; | |||
| 1664 | if (Val.isConstant()) { | |||
| 1665 | Res = ConstantFoldCompareInstOperands(Pred, Val.getConstant(), C, DL, TLI); | |||
| 1666 | if (ConstantInt *ResCI = dyn_cast<ConstantInt>(Res)) | |||
| 1667 | return ResCI->isZero() ? LazyValueInfo::False : LazyValueInfo::True; | |||
| 1668 | return LazyValueInfo::Unknown; | |||
| 1669 | } | |||
| 1670 | ||||
| 1671 | if (Val.isConstantRange()) { | |||
| 1672 | ConstantInt *CI = dyn_cast<ConstantInt>(C); | |||
| 1673 | if (!CI) return LazyValueInfo::Unknown; | |||
| 1674 | ||||
| 1675 | const ConstantRange &CR = Val.getConstantRange(); | |||
| 1676 | if (Pred == ICmpInst::ICMP_EQ) { | |||
| 1677 | if (!CR.contains(CI->getValue())) | |||
| 1678 | return LazyValueInfo::False; | |||
| 1679 | ||||
| 1680 | if (CR.isSingleElement()) | |||
| 1681 | return LazyValueInfo::True; | |||
| 1682 | } else if (Pred == ICmpInst::ICMP_NE) { | |||
| 1683 | if (!CR.contains(CI->getValue())) | |||
| 1684 | return LazyValueInfo::True; | |||
| 1685 | ||||
| 1686 | if (CR.isSingleElement()) | |||
| 1687 | return LazyValueInfo::False; | |||
| 1688 | } else { | |||
| 1689 | // Handle more complex predicates. | |||
| 1690 | ConstantRange TrueValues = ConstantRange::makeExactICmpRegion( | |||
| 1691 | (ICmpInst::Predicate)Pred, CI->getValue()); | |||
| 1692 | if (TrueValues.contains(CR)) | |||
| 1693 | return LazyValueInfo::True; | |||
| 1694 | if (TrueValues.inverse().contains(CR)) | |||
| 1695 | return LazyValueInfo::False; | |||
| 1696 | } | |||
| 1697 | return LazyValueInfo::Unknown; | |||
| 1698 | } | |||
| 1699 | ||||
| 1700 | if (Val.isNotConstant()) { | |||
| 1701 | // If this is an equality comparison, we can try to fold it knowing that | |||
| 1702 | // "V != C1". | |||
| 1703 | if (Pred == ICmpInst::ICMP_EQ) { | |||
| 1704 | // !C1 == C -> false iff C1 == C. | |||
| 1705 | Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE, | |||
| 1706 | Val.getNotConstant(), C, DL, | |||
| 1707 | TLI); | |||
| 1708 | if (Res->isNullValue()) | |||
| 1709 | return LazyValueInfo::False; | |||
| 1710 | } else if (Pred == ICmpInst::ICMP_NE) { | |||
| 1711 | // !C1 != C -> true iff C1 == C. | |||
| 1712 | Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE, | |||
| 1713 | Val.getNotConstant(), C, DL, | |||
| 1714 | TLI); | |||
| 1715 | if (Res->isNullValue()) | |||
| 1716 | return LazyValueInfo::True; | |||
| 1717 | } | |||
| 1718 | return LazyValueInfo::Unknown; | |||
| 1719 | } | |||
| 1720 | ||||
| 1721 | return LazyValueInfo::Unknown; | |||
| 1722 | } | |||
| 1723 | ||||
| 1724 | /// Determine whether the specified value comparison with a constant is known to | |||
| 1725 | /// be true or false on the specified CFG edge. Pred is a CmpInst predicate. | |||
| 1726 | LazyValueInfo::Tristate | |||
| 1727 | LazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, Constant *C, | |||
| 1728 | BasicBlock *FromBB, BasicBlock *ToBB, | |||
| 1729 | Instruction *CxtI) { | |||
| 1730 | Module *M = FromBB->getModule(); | |||
| 1731 | ValueLatticeElement Result = | |||
| 1732 | getImpl(PImpl, AC, M).getValueOnEdge(V, FromBB, ToBB, CxtI); | |||
| 1733 | ||||
| 1734 | return getPredicateResult(Pred, C, Result, M->getDataLayout(), TLI); | |||
| 1735 | } | |||
| 1736 | ||||
| 1737 | LazyValueInfo::Tristate | |||
| 1738 | LazyValueInfo::getPredicateAt(unsigned Pred, Value *V, Constant *C, | |||
| 1739 | Instruction *CxtI, bool UseBlockValue) { | |||
| 1740 | // Is or is not NonNull are common predicates being queried. If | |||
| 1741 | // isKnownNonZero can tell us the result of the predicate, we can | |||
| 1742 | // return it quickly. But this is only a fastpath, and falling | |||
| 1743 | // through would still be correct. | |||
| 1744 | Module *M = CxtI->getModule(); | |||
| 1745 | const DataLayout &DL = M->getDataLayout(); | |||
| 1746 | if (V->getType()->isPointerTy() && C->isNullValue() && | |||
| 1747 | isKnownNonZero(V->stripPointerCastsSameRepresentation(), DL)) { | |||
| 1748 | if (Pred == ICmpInst::ICMP_EQ) | |||
| 1749 | return LazyValueInfo::False; | |||
| 1750 | else if (Pred == ICmpInst::ICMP_NE) | |||
| 1751 | return LazyValueInfo::True; | |||
| 1752 | } | |||
| 1753 | ||||
| 1754 | ValueLatticeElement Result = UseBlockValue | |||
| 1755 | ? getImpl(PImpl, AC, M).getValueInBlock(V, CxtI->getParent(), CxtI) | |||
| 1756 | : getImpl(PImpl, AC, M).getValueAt(V, CxtI); | |||
| 1757 | Tristate Ret = getPredicateResult(Pred, C, Result, DL, TLI); | |||
| 1758 | if (Ret != Unknown) | |||
| 1759 | return Ret; | |||
| 1760 | ||||
| 1761 | // Note: The following bit of code is somewhat distinct from the rest of LVI; | |||
| 1762 | // LVI as a whole tries to compute a lattice value which is conservatively | |||
| 1763 | // correct at a given location. In this case, we have a predicate which we | |||
| 1764 | // weren't able to prove about the merged result, and we're pushing that | |||
| 1765 | // predicate back along each incoming edge to see if we can prove it | |||
| 1766 | // separately for each input. As a motivating example, consider: | |||
| 1767 | // bb1: | |||
| 1768 | // %v1 = ... ; constantrange<1, 5> | |||
| 1769 | // br label %merge | |||
| 1770 | // bb2: | |||
| 1771 | // %v2 = ... ; constantrange<10, 20> | |||
| 1772 | // br label %merge | |||
| 1773 | // merge: | |||
| 1774 | // %phi = phi [%v1, %v2] ; constantrange<1,20> | |||
| 1775 | // %pred = icmp eq i32 %phi, 8 | |||
| 1776 | // We can't tell from the lattice value for '%phi' that '%pred' is false | |||
| 1777 | // along each path, but by checking the predicate over each input separately, | |||
| 1778 | // we can. | |||
| 1779 | // We limit the search to one step backwards from the current BB and value. | |||
| 1780 | // We could consider extending this to search further backwards through the | |||
| 1781 | // CFG and/or value graph, but there are non-obvious compile time vs quality | |||
| 1782 | // tradeoffs. | |||
| 1783 | if (CxtI) { | |||
| 1784 | BasicBlock *BB = CxtI->getParent(); | |||
| 1785 | ||||
| 1786 | // Function entry or an unreachable block. Bail to avoid confusing | |||
| 1787 | // analysis below. | |||
| 1788 | pred_iterator PI = pred_begin(BB), PE = pred_end(BB); | |||
| 1789 | if (PI == PE) | |||
| 1790 | return Unknown; | |||
| 1791 | ||||
| 1792 | // If V is a PHI node in the same block as the context, we need to ask | |||
| 1793 | // questions about the predicate as applied to the incoming value along | |||
| 1794 | // each edge. This is useful for eliminating cases where the predicate is | |||
| 1795 | // known along all incoming edges. | |||
| 1796 | if (auto *PHI = dyn_cast<PHINode>(V)) | |||
| 1797 | if (PHI->getParent() == BB) { | |||
| 1798 | Tristate Baseline = Unknown; | |||
| 1799 | for (unsigned i = 0, e = PHI->getNumIncomingValues(); i < e; i++) { | |||
| 1800 | Value *Incoming = PHI->getIncomingValue(i); | |||
| 1801 | BasicBlock *PredBB = PHI->getIncomingBlock(i); | |||
| 1802 | // Note that PredBB may be BB itself. | |||
| 1803 | Tristate Result = getPredicateOnEdge(Pred, Incoming, C, PredBB, BB, | |||
| 1804 | CxtI); | |||
| 1805 | ||||
| 1806 | // Keep going as long as we've seen a consistent known result for | |||
| 1807 | // all inputs. | |||
| 1808 | Baseline = (i == 0) ? Result /* First iteration */ | |||
| 1809 | : (Baseline == Result ? Baseline : Unknown); /* All others */ | |||
| 1810 | if (Baseline == Unknown) | |||
| 1811 | break; | |||
| 1812 | } | |||
| 1813 | if (Baseline != Unknown) | |||
| 1814 | return Baseline; | |||
| 1815 | } | |||
| 1816 | ||||
| 1817 | // For a comparison where the V is outside this block, it's possible | |||
| 1818 | // that we've branched on it before. Look to see if the value is known | |||
| 1819 | // on all incoming edges. | |||
| 1820 | if (!isa<Instruction>(V) || | |||
| 1821 | cast<Instruction>(V)->getParent() != BB) { | |||
| 1822 | // For predecessor edge, determine if the comparison is true or false | |||
| 1823 | // on that edge. If they're all true or all false, we can conclude | |||
| 1824 | // the value of the comparison in this block. | |||
| 1825 | Tristate Baseline = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI); | |||
| 1826 | if (Baseline != Unknown) { | |||
| 1827 | // Check that all remaining incoming values match the first one. | |||
| 1828 | while (++PI != PE) { | |||
| 1829 | Tristate Ret = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI); | |||
| 1830 | if (Ret != Baseline) break; | |||
| 1831 | } | |||
| 1832 | // If we terminated early, then one of the values didn't match. | |||
| 1833 | if (PI == PE) { | |||
| 1834 | return Baseline; | |||
| 1835 | } | |||
| 1836 | } | |||
| 1837 | } | |||
| 1838 | } | |||
| 1839 | return Unknown; | |||
| 1840 | } | |||
| 1841 | ||||
| 1842 | LazyValueInfo::Tristate LazyValueInfo::getPredicateAt(unsigned P, Value *LHS, | |||
| 1843 | Value *RHS, | |||
| 1844 | Instruction *CxtI, | |||
| 1845 | bool UseBlockValue) { | |||
| 1846 | CmpInst::Predicate Pred = (CmpInst::Predicate)P; | |||
| 1847 | ||||
| 1848 | if (auto *C = dyn_cast<Constant>(RHS)) | |||
| 1849 | return getPredicateAt(P, LHS, C, CxtI, UseBlockValue); | |||
| 1850 | if (auto *C = dyn_cast<Constant>(LHS)) | |||
| 1851 | return getPredicateAt(CmpInst::getSwappedPredicate(Pred), RHS, C, CxtI, | |||
| 1852 | UseBlockValue); | |||
| 1853 | ||||
| 1854 | // Got two non-Constant values. While we could handle them somewhat, | |||
| 1855 | // by getting their constant ranges, and applying ConstantRange::icmp(), | |||
| 1856 | // so far it did not appear to be profitable. | |||
| 1857 | return LazyValueInfo::Unknown; | |||
| 1858 | } | |||
| 1859 | ||||
| 1860 | void LazyValueInfo::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc, | |||
| 1861 | BasicBlock *NewSucc) { | |||
| 1862 | if (PImpl) { | |||
| 1863 | getImpl(PImpl, AC, PredBB->getModule()) | |||
| 1864 | .threadEdge(PredBB, OldSucc, NewSucc); | |||
| 1865 | } | |||
| 1866 | } | |||
| 1867 | ||||
| 1868 | void LazyValueInfo::eraseBlock(BasicBlock *BB) { | |||
| 1869 | if (PImpl) { | |||
| 1870 | getImpl(PImpl, AC, BB->getModule()).eraseBlock(BB); | |||
| 1871 | } | |||
| 1872 | } | |||
| 1873 | ||||
| 1874 | ||||
| 1875 | void LazyValueInfo::printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS) { | |||
| 1876 | if (PImpl) { | |||
| 1877 | getImpl(PImpl, AC, F.getParent()).printLVI(F, DTree, OS); | |||
| 1878 | } | |||
| 1879 | } | |||
| 1880 | ||||
| 1881 | // Print the LVI for the function arguments at the start of each basic block. | |||
| 1882 | void LazyValueInfoAnnotatedWriter::emitBasicBlockStartAnnot( | |||
| 1883 | const BasicBlock *BB, formatted_raw_ostream &OS) { | |||
| 1884 | // Find if there are latticevalues defined for arguments of the function. | |||
| 1885 | auto *F = BB->getParent(); | |||
| 1886 | for (auto &Arg : F->args()) { | |||
| 1887 | ValueLatticeElement Result = LVIImpl->getValueInBlock( | |||
| 1888 | const_cast<Argument *>(&Arg), const_cast<BasicBlock *>(BB)); | |||
| 1889 | if (Result.isUnknown()) | |||
| 1890 | continue; | |||
| 1891 | OS << "; LatticeVal for: '" << Arg << "' is: " << Result << "\n"; | |||
| 1892 | } | |||
| 1893 | } | |||
| 1894 | ||||
| 1895 | // This function prints the LVI analysis for the instruction I at the beginning | |||
| 1896 | // of various basic blocks. It relies on calculated values that are stored in | |||
| 1897 | // the LazyValueInfoCache, and in the absence of cached values, recalculate the | |||
| 1898 | // LazyValueInfo for `I`, and print that info. | |||
| 1899 | void LazyValueInfoAnnotatedWriter::emitInstructionAnnot( | |||
| 1900 | const Instruction *I, formatted_raw_ostream &OS) { | |||
| 1901 | ||||
| 1902 | auto *ParentBB = I->getParent(); | |||
| 1903 | SmallPtrSet<const BasicBlock*, 16> BlocksContainingLVI; | |||
| 1904 | // We can generate (solve) LVI values only for blocks that are dominated by | |||
| 1905 | // the I's parent. However, to avoid generating LVI for all dominating blocks, | |||
| 1906 | // that contain redundant/uninteresting information, we print LVI for | |||
| 1907 | // blocks that may use this LVI information (such as immediate successor | |||
| 1908 | // blocks, and blocks that contain uses of `I`). | |||
| 1909 | auto printResult = [&](const BasicBlock *BB) { | |||
| 1910 | if (!BlocksContainingLVI.insert(BB).second) | |||
| 1911 | return; | |||
| 1912 | ValueLatticeElement Result = LVIImpl->getValueInBlock( | |||
| 1913 | const_cast<Instruction *>(I), const_cast<BasicBlock *>(BB)); | |||
| 1914 | OS << "; LatticeVal for: '" << *I << "' in BB: '"; | |||
| 1915 | BB->printAsOperand(OS, false); | |||
| 1916 | OS << "' is: " << Result << "\n"; | |||
| 1917 | }; | |||
| 1918 | ||||
| 1919 | printResult(ParentBB); | |||
| 1920 | // Print the LVI analysis results for the immediate successor blocks, that | |||
| 1921 | // are dominated by `ParentBB`. | |||
| 1922 | for (auto *BBSucc : successors(ParentBB)) | |||
| 1923 | if (DT.dominates(ParentBB, BBSucc)) | |||
| 1924 | printResult(BBSucc); | |||
| 1925 | ||||
| 1926 | // Print LVI in blocks where `I` is used. | |||
| 1927 | for (auto *U : I->users()) | |||
| 1928 | if (auto *UseI = dyn_cast<Instruction>(U)) | |||
| 1929 | if (!isa<PHINode>(UseI) || DT.dominates(ParentBB, UseI->getParent())) | |||
| 1930 | printResult(UseI->getParent()); | |||
| 1931 | ||||
| 1932 | } | |||
| 1933 | ||||
| 1934 | namespace { | |||
| 1935 | // Printer class for LazyValueInfo results. | |||
| 1936 | class LazyValueInfoPrinter : public FunctionPass { | |||
| 1937 | public: | |||
| 1938 | static char ID; // Pass identification, replacement for typeid | |||
| 1939 | LazyValueInfoPrinter() : FunctionPass(ID) { | |||
| 1940 | initializeLazyValueInfoPrinterPass(*PassRegistry::getPassRegistry()); | |||
| 1941 | } | |||
| 1942 | ||||
| 1943 | void getAnalysisUsage(AnalysisUsage &AU) const override { | |||
| 1944 | AU.setPreservesAll(); | |||
| 1945 | AU.addRequired<LazyValueInfoWrapperPass>(); | |||
| 1946 | AU.addRequired<DominatorTreeWrapperPass>(); | |||
| 1947 | } | |||
| 1948 | ||||
| 1949 | // Get the mandatory dominator tree analysis and pass this in to the | |||
| 1950 | // LVIPrinter. We cannot rely on the LVI's DT, since it's optional. | |||
| 1951 | bool runOnFunction(Function &F) override { | |||
| 1952 | dbgs() << "LVI for function '" << F.getName() << "':\n"; | |||
| 1953 | auto &LVI = getAnalysis<LazyValueInfoWrapperPass>().getLVI(); | |||
| 1954 | auto &DTree = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); | |||
| 1955 | LVI.printLVI(F, DTree, dbgs()); | |||
| 1956 | return false; | |||
| 1957 | } | |||
| 1958 | }; | |||
| 1959 | } | |||
| 1960 | ||||
| 1961 | char LazyValueInfoPrinter::ID = 0; | |||
| 1962 | INITIALIZE_PASS_BEGIN(LazyValueInfoPrinter, "print-lazy-value-info",static void *initializeLazyValueInfoPrinterPassOnce(PassRegistry &Registry) { | |||
| 1963 | "Lazy Value Info Printer Pass", false, false)static void *initializeLazyValueInfoPrinterPassOnce(PassRegistry &Registry) { | |||
| 1964 | INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass)initializeLazyValueInfoWrapperPassPass(Registry); | |||
| 1965 | INITIALIZE_PASS_END(LazyValueInfoPrinter, "print-lazy-value-info",PassInfo *PI = new PassInfo( "Lazy Value Info Printer Pass", "print-lazy-value-info" , &LazyValueInfoPrinter::ID, PassInfo::NormalCtor_t(callDefaultCtor <LazyValueInfoPrinter>), false, false); Registry.registerPass (*PI, true); return PI; } static llvm::once_flag InitializeLazyValueInfoPrinterPassFlag ; void llvm::initializeLazyValueInfoPrinterPass(PassRegistry & Registry) { llvm::call_once(InitializeLazyValueInfoPrinterPassFlag , initializeLazyValueInfoPrinterPassOnce, std::ref(Registry)) ; } | |||
| 1966 | "Lazy Value Info Printer Pass", false, false)PassInfo *PI = new PassInfo( "Lazy Value Info Printer Pass", "print-lazy-value-info" , &LazyValueInfoPrinter::ID, PassInfo::NormalCtor_t(callDefaultCtor <LazyValueInfoPrinter>), false, false); Registry.registerPass (*PI, true); return PI; } static llvm::once_flag InitializeLazyValueInfoPrinterPassFlag ; void llvm::initializeLazyValueInfoPrinterPass(PassRegistry & Registry) { llvm::call_once(InitializeLazyValueInfoPrinterPassFlag , initializeLazyValueInfoPrinterPassOnce, std::ref(Registry)) ; } |
| 1 | //===-- llvm/ADT/APInt.h - For Arbitrary Precision Integer -----*- 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 | /// \file | |||
| 10 | /// This file implements a class to represent arbitrary precision | |||
| 11 | /// integral constant values and operations on them. | |||
| 12 | /// | |||
| 13 | //===----------------------------------------------------------------------===// | |||
| 14 | ||||
| 15 | #ifndef LLVM_ADT_APINT_H | |||
| 16 | #define LLVM_ADT_APINT_H | |||
| 17 | ||||
| 18 | #include "llvm/Support/Compiler.h" | |||
| 19 | #include "llvm/Support/MathExtras.h" | |||
| 20 | #include <cassert> | |||
| 21 | #include <climits> | |||
| 22 | #include <cstring> | |||
| 23 | #include <utility> | |||
| 24 | ||||
| 25 | namespace llvm { | |||
| 26 | class FoldingSetNodeID; | |||
| 27 | class StringRef; | |||
| 28 | class hash_code; | |||
| 29 | class raw_ostream; | |||
| 30 | ||||
| 31 | template <typename T> class SmallVectorImpl; | |||
| 32 | template <typename T> class ArrayRef; | |||
| 33 | template <typename T> class Optional; | |||
| 34 | template <typename T> struct DenseMapInfo; | |||
| 35 | ||||
| 36 | class APInt; | |||
| 37 | ||||
| 38 | inline APInt operator-(APInt); | |||
| 39 | ||||
| 40 | //===----------------------------------------------------------------------===// | |||
| 41 | // APInt Class | |||
| 42 | //===----------------------------------------------------------------------===// | |||
| 43 | ||||
| 44 | /// Class for arbitrary precision integers. | |||
| 45 | /// | |||
| 46 | /// APInt is a functional replacement for common case unsigned integer type like | |||
| 47 | /// "unsigned", "unsigned long" or "uint64_t", but also allows non-byte-width | |||
| 48 | /// integer sizes and large integer value types such as 3-bits, 15-bits, or more | |||
| 49 | /// than 64-bits of precision. APInt provides a variety of arithmetic operators | |||
| 50 | /// and methods to manipulate integer values of any bit-width. It supports both | |||
| 51 | /// the typical integer arithmetic and comparison operations as well as bitwise | |||
| 52 | /// manipulation. | |||
| 53 | /// | |||
| 54 | /// The class has several invariants worth noting: | |||
| 55 | /// * All bit, byte, and word positions are zero-based. | |||
| 56 | /// * Once the bit width is set, it doesn't change except by the Truncate, | |||
| 57 | /// SignExtend, or ZeroExtend operations. | |||
| 58 | /// * All binary operators must be on APInt instances of the same bit width. | |||
| 59 | /// Attempting to use these operators on instances with different bit | |||
| 60 | /// widths will yield an assertion. | |||
| 61 | /// * The value is stored canonically as an unsigned value. For operations | |||
| 62 | /// where it makes a difference, there are both signed and unsigned variants | |||
| 63 | /// of the operation. For example, sdiv and udiv. However, because the bit | |||
| 64 | /// widths must be the same, operations such as Mul and Add produce the same | |||
| 65 | /// results regardless of whether the values are interpreted as signed or | |||
| 66 | /// not. | |||
| 67 | /// * In general, the class tries to follow the style of computation that LLVM | |||
| 68 | /// uses in its IR. This simplifies its use for LLVM. | |||
| 69 | /// | |||
| 70 | class LLVM_NODISCARD[[clang::warn_unused_result]] APInt { | |||
| 71 | public: | |||
| 72 | typedef uint64_t WordType; | |||
| 73 | ||||
| 74 | /// This enum is used to hold the constants we needed for APInt. | |||
| 75 | enum : unsigned { | |||
| 76 | /// Byte size of a word. | |||
| 77 | APINT_WORD_SIZE = sizeof(WordType), | |||
| 78 | /// Bits in a word. | |||
| 79 | APINT_BITS_PER_WORD = APINT_WORD_SIZE * CHAR_BIT8 | |||
| 80 | }; | |||
| 81 | ||||
| 82 | enum class Rounding { | |||
| 83 | DOWN, | |||
| 84 | TOWARD_ZERO, | |||
| 85 | UP, | |||
| 86 | }; | |||
| 87 | ||||
| 88 | static constexpr WordType WORDTYPE_MAX = ~WordType(0); | |||
| 89 | ||||
| 90 | private: | |||
| 91 | /// This union is used to store the integer value. When the | |||
| 92 | /// integer bit-width <= 64, it uses VAL, otherwise it uses pVal. | |||
| 93 | union { | |||
| 94 | uint64_t VAL; ///< Used to store the <= 64 bits integer value. | |||
| 95 | uint64_t *pVal; ///< Used to store the >64 bits integer value. | |||
| 96 | } U; | |||
| 97 | ||||
| 98 | unsigned BitWidth; ///< The number of bits in this APInt. | |||
| 99 | ||||
| 100 | friend struct DenseMapInfo<APInt>; | |||
| 101 | ||||
| 102 | friend class APSInt; | |||
| 103 | ||||
| 104 | /// Fast internal constructor | |||
| 105 | /// | |||
| 106 | /// This constructor is used only internally for speed of construction of | |||
| 107 | /// temporaries. It is unsafe for general use so it is not public. | |||
| 108 | APInt(uint64_t *val, unsigned bits) : BitWidth(bits) { | |||
| 109 | U.pVal = val; | |||
| 110 | } | |||
| 111 | ||||
| 112 | /// Determine which word a bit is in. | |||
| 113 | /// | |||
| 114 | /// \returns the word position for the specified bit position. | |||
| 115 | static unsigned whichWord(unsigned bitPosition) { | |||
| 116 | return bitPosition / APINT_BITS_PER_WORD; | |||
| 117 | } | |||
| 118 | ||||
| 119 | /// Determine which bit in a word a bit is in. | |||
| 120 | /// | |||
| 121 | /// \returns the bit position in a word for the specified bit position | |||
| 122 | /// in the APInt. | |||
| 123 | static unsigned whichBit(unsigned bitPosition) { | |||
| 124 | return bitPosition % APINT_BITS_PER_WORD; | |||
| 125 | } | |||
| 126 | ||||
| 127 | /// Get a single bit mask. | |||
| 128 | /// | |||
| 129 | /// \returns a uint64_t with only bit at "whichBit(bitPosition)" set | |||
| 130 | /// This method generates and returns a uint64_t (word) mask for a single | |||
| 131 | /// bit at a specific bit position. This is used to mask the bit in the | |||
| 132 | /// corresponding word. | |||
| 133 | static uint64_t maskBit(unsigned bitPosition) { | |||
| 134 | return 1ULL << whichBit(bitPosition); | |||
| 135 | } | |||
| 136 | ||||
| 137 | /// Clear unused high order bits | |||
| 138 | /// | |||
| 139 | /// This method is used internally to clear the top "N" bits in the high order | |||
| 140 | /// word that are not used by the APInt. This is needed after the most | |||
| 141 | /// significant word is assigned a value to ensure that those bits are | |||
| 142 | /// zero'd out. | |||
| 143 | APInt &clearUnusedBits() { | |||
| 144 | // Compute how many bits are used in the final word | |||
| 145 | unsigned WordBits = ((BitWidth-1) % APINT_BITS_PER_WORD) + 1; | |||
| 146 | ||||
| 147 | // Mask out the high bits. | |||
| 148 | uint64_t mask = WORDTYPE_MAX >> (APINT_BITS_PER_WORD - WordBits); | |||
| 149 | if (isSingleWord()) | |||
| 150 | U.VAL &= mask; | |||
| 151 | else | |||
| 152 | U.pVal[getNumWords() - 1] &= mask; | |||
| 153 | return *this; | |||
| 154 | } | |||
| 155 | ||||
| 156 | /// Get the word corresponding to a bit position | |||
| 157 | /// \returns the corresponding word for the specified bit position. | |||
| 158 | uint64_t getWord(unsigned bitPosition) const { | |||
| 159 | return isSingleWord() ? U.VAL : U.pVal[whichWord(bitPosition)]; | |||
| 160 | } | |||
| 161 | ||||
| 162 | /// Utility method to change the bit width of this APInt to new bit width, | |||
| 163 | /// allocating and/or deallocating as necessary. There is no guarantee on the | |||
| 164 | /// value of any bits upon return. Caller should populate the bits after. | |||
| 165 | void reallocate(unsigned NewBitWidth); | |||
| 166 | ||||
| 167 | /// Convert a char array into an APInt | |||
| 168 | /// | |||
| 169 | /// \param radix 2, 8, 10, 16, or 36 | |||
| 170 | /// Converts a string into a number. The string must be non-empty | |||
| 171 | /// and well-formed as a number of the given base. The bit-width | |||
| 172 | /// must be sufficient to hold the result. | |||
| 173 | /// | |||
| 174 | /// This is used by the constructors that take string arguments. | |||
| 175 | /// | |||
| 176 | /// StringRef::getAsInteger is superficially similar but (1) does | |||
| 177 | /// not assume that the string is well-formed and (2) grows the | |||
| 178 | /// result to hold the input. | |||
| 179 | void fromString(unsigned numBits, StringRef str, uint8_t radix); | |||
| 180 | ||||
| 181 | /// An internal division function for dividing APInts. | |||
| 182 | /// | |||
| 183 | /// This is used by the toString method to divide by the radix. It simply | |||
| 184 | /// provides a more convenient form of divide for internal use since KnuthDiv | |||
| 185 | /// has specific constraints on its inputs. If those constraints are not met | |||
| 186 | /// then it provides a simpler form of divide. | |||
| 187 | static void divide(const WordType *LHS, unsigned lhsWords, | |||
| 188 | const WordType *RHS, unsigned rhsWords, WordType *Quotient, | |||
| 189 | WordType *Remainder); | |||
| 190 | ||||
| 191 | /// out-of-line slow case for inline constructor | |||
| 192 | void initSlowCase(uint64_t val, bool isSigned); | |||
| 193 | ||||
| 194 | /// shared code between two array constructors | |||
| 195 | void initFromArray(ArrayRef<uint64_t> array); | |||
| 196 | ||||
| 197 | /// out-of-line slow case for inline copy constructor | |||
| 198 | void initSlowCase(const APInt &that); | |||
| 199 | ||||
| 200 | /// out-of-line slow case for shl | |||
| 201 | void shlSlowCase(unsigned ShiftAmt); | |||
| 202 | ||||
| 203 | /// out-of-line slow case for lshr. | |||
| 204 | void lshrSlowCase(unsigned ShiftAmt); | |||
| 205 | ||||
| 206 | /// out-of-line slow case for ashr. | |||
| 207 | void ashrSlowCase(unsigned ShiftAmt); | |||
| 208 | ||||
| 209 | /// out-of-line slow case for operator= | |||
| 210 | void AssignSlowCase(const APInt &RHS); | |||
| 211 | ||||
| 212 | /// out-of-line slow case for operator== | |||
| 213 | bool EqualSlowCase(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__)); | |||
| 214 | ||||
| 215 | /// out-of-line slow case for countLeadingZeros | |||
| 216 | unsigned countLeadingZerosSlowCase() const LLVM_READONLY__attribute__((__pure__)); | |||
| 217 | ||||
| 218 | /// out-of-line slow case for countLeadingOnes. | |||
| 219 | unsigned countLeadingOnesSlowCase() const LLVM_READONLY__attribute__((__pure__)); | |||
| 220 | ||||
| 221 | /// out-of-line slow case for countTrailingZeros. | |||
| 222 | unsigned countTrailingZerosSlowCase() const LLVM_READONLY__attribute__((__pure__)); | |||
| 223 | ||||
| 224 | /// out-of-line slow case for countTrailingOnes | |||
| 225 | unsigned countTrailingOnesSlowCase() const LLVM_READONLY__attribute__((__pure__)); | |||
| 226 | ||||
| 227 | /// out-of-line slow case for countPopulation | |||
| 228 | unsigned countPopulationSlowCase() const LLVM_READONLY__attribute__((__pure__)); | |||
| 229 | ||||
| 230 | /// out-of-line slow case for intersects. | |||
| 231 | bool intersectsSlowCase(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__)); | |||
| 232 | ||||
| 233 | /// out-of-line slow case for isSubsetOf. | |||
| 234 | bool isSubsetOfSlowCase(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__)); | |||
| 235 | ||||
| 236 | /// out-of-line slow case for setBits. | |||
| 237 | void setBitsSlowCase(unsigned loBit, unsigned hiBit); | |||
| 238 | ||||
| 239 | /// out-of-line slow case for flipAllBits. | |||
| 240 | void flipAllBitsSlowCase(); | |||
| 241 | ||||
| 242 | /// out-of-line slow case for operator&=. | |||
| 243 | void AndAssignSlowCase(const APInt& RHS); | |||
| 244 | ||||
| 245 | /// out-of-line slow case for operator|=. | |||
| 246 | void OrAssignSlowCase(const APInt& RHS); | |||
| 247 | ||||
| 248 | /// out-of-line slow case for operator^=. | |||
| 249 | void XorAssignSlowCase(const APInt& RHS); | |||
| 250 | ||||
| 251 | /// Unsigned comparison. Returns -1, 0, or 1 if this APInt is less than, equal | |||
| 252 | /// to, or greater than RHS. | |||
| 253 | int compare(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__)); | |||
| 254 | ||||
| 255 | /// Signed comparison. Returns -1, 0, or 1 if this APInt is less than, equal | |||
| 256 | /// to, or greater than RHS. | |||
| 257 | int compareSigned(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__)); | |||
| 258 | ||||
| 259 | public: | |||
| 260 | /// \name Constructors | |||
| 261 | /// @{ | |||
| 262 | ||||
| 263 | /// Create a new APInt of numBits width, initialized as val. | |||
| 264 | /// | |||
| 265 | /// If isSigned is true then val is treated as if it were a signed value | |||
| 266 | /// (i.e. as an int64_t) and the appropriate sign extension to the bit width | |||
| 267 | /// will be done. Otherwise, no sign extension occurs (high order bits beyond | |||
| 268 | /// the range of val are zero filled). | |||
| 269 | /// | |||
| 270 | /// \param numBits the bit width of the constructed APInt | |||
| 271 | /// \param val the initial value of the APInt | |||
| 272 | /// \param isSigned how to treat signedness of val | |||
| 273 | APInt(unsigned numBits, uint64_t val, bool isSigned = false) | |||
| 274 | : BitWidth(numBits) { | |||
| 275 | assert(BitWidth && "bitwidth too small")((void)0); | |||
| 276 | if (isSingleWord()) { | |||
| 277 | U.VAL = val; | |||
| 278 | clearUnusedBits(); | |||
| 279 | } else { | |||
| 280 | initSlowCase(val, isSigned); | |||
| 281 | } | |||
| 282 | } | |||
| 283 | ||||
| 284 | /// Construct an APInt of numBits width, initialized as bigVal[]. | |||
| 285 | /// | |||
| 286 | /// Note that bigVal.size() can be smaller or larger than the corresponding | |||
| 287 | /// bit width but any extraneous bits will be dropped. | |||
| 288 | /// | |||
| 289 | /// \param numBits the bit width of the constructed APInt | |||
| 290 | /// \param bigVal a sequence of words to form the initial value of the APInt | |||
| 291 | APInt(unsigned numBits, ArrayRef<uint64_t> bigVal); | |||
| 292 | ||||
| 293 | /// Equivalent to APInt(numBits, ArrayRef<uint64_t>(bigVal, numWords)), but | |||
| 294 | /// deprecated because this constructor is prone to ambiguity with the | |||
| 295 | /// APInt(unsigned, uint64_t, bool) constructor. | |||
| 296 | /// | |||
| 297 | /// If this overload is ever deleted, care should be taken to prevent calls | |||
| 298 | /// from being incorrectly captured by the APInt(unsigned, uint64_t, bool) | |||
| 299 | /// constructor. | |||
| 300 | APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[]); | |||
| 301 | ||||
| 302 | /// Construct an APInt from a string representation. | |||
| 303 | /// | |||
| 304 | /// This constructor interprets the string \p str in the given radix. The | |||
| 305 | /// interpretation stops when the first character that is not suitable for the | |||
| 306 | /// radix is encountered, or the end of the string. Acceptable radix values | |||
| 307 | /// are 2, 8, 10, 16, and 36. It is an error for the value implied by the | |||
| 308 | /// string to require more bits than numBits. | |||
| 309 | /// | |||
| 310 | /// \param numBits the bit width of the constructed APInt | |||
| 311 | /// \param str the string to be interpreted | |||
| 312 | /// \param radix the radix to use for the conversion | |||
| 313 | APInt(unsigned numBits, StringRef str, uint8_t radix); | |||
| 314 | ||||
| 315 | /// Simply makes *this a copy of that. | |||
| 316 | /// Copy Constructor. | |||
| 317 | APInt(const APInt &that) : BitWidth(that.BitWidth) { | |||
| ||||
| 318 | if (isSingleWord()) | |||
| 319 | U.VAL = that.U.VAL; | |||
| 320 | else | |||
| 321 | initSlowCase(that); | |||
| 322 | } | |||
| 323 | ||||
| 324 | /// Move Constructor. | |||
| 325 | APInt(APInt &&that) : BitWidth(that.BitWidth) { | |||
| 326 | memcpy(&U, &that.U, sizeof(U)); | |||
| 327 | that.BitWidth = 0; | |||
| 328 | } | |||
| 329 | ||||
| 330 | /// Destructor. | |||
| 331 | ~APInt() { | |||
| 332 | if (needsCleanup()) | |||
| 333 | delete[] U.pVal; | |||
| 334 | } | |||
| 335 | ||||
| 336 | /// Default constructor that creates an uninteresting APInt | |||
| 337 | /// representing a 1-bit zero value. | |||
| 338 | /// | |||
| 339 | /// This is useful for object deserialization (pair this with the static | |||
| 340 | /// method Read). | |||
| 341 | explicit APInt() : BitWidth(1) { U.VAL = 0; } | |||
| 342 | ||||
| 343 | /// Returns whether this instance allocated memory. | |||
| 344 | bool needsCleanup() const { return !isSingleWord(); } | |||
| 345 | ||||
| 346 | /// Used to insert APInt objects, or objects that contain APInt objects, into | |||
| 347 | /// FoldingSets. | |||
| 348 | void Profile(FoldingSetNodeID &id) const; | |||
| 349 | ||||
| 350 | /// @} | |||
| 351 | /// \name Value Tests | |||
| 352 | /// @{ | |||
| 353 | ||||
| 354 | /// Determine if this APInt just has one word to store value. | |||
| 355 | /// | |||
| 356 | /// \returns true if the number of bits <= 64, false otherwise. | |||
| 357 | bool isSingleWord() const { return BitWidth <= APINT_BITS_PER_WORD; } | |||
| 358 | ||||
| 359 | /// Determine sign of this APInt. | |||
| 360 | /// | |||
| 361 | /// This tests the high bit of this APInt to determine if it is set. | |||
| 362 | /// | |||
| 363 | /// \returns true if this APInt is negative, false otherwise | |||
| 364 | bool isNegative() const { return (*this)[BitWidth - 1]; } | |||
| 365 | ||||
| 366 | /// Determine if this APInt Value is non-negative (>= 0) | |||
| 367 | /// | |||
| 368 | /// This tests the high bit of the APInt to determine if it is unset. | |||
| 369 | bool isNonNegative() const { return !isNegative(); } | |||
| 370 | ||||
| 371 | /// Determine if sign bit of this APInt is set. | |||
| 372 | /// | |||
| 373 | /// This tests the high bit of this APInt to determine if it is set. | |||
| 374 | /// | |||
| 375 | /// \returns true if this APInt has its sign bit set, false otherwise. | |||
| 376 | bool isSignBitSet() const { return (*this)[BitWidth-1]; } | |||
| 377 | ||||
| 378 | /// Determine if sign bit of this APInt is clear. | |||
| 379 | /// | |||
| 380 | /// This tests the high bit of this APInt to determine if it is clear. | |||
| 381 | /// | |||
| 382 | /// \returns true if this APInt has its sign bit clear, false otherwise. | |||
| 383 | bool isSignBitClear() const { return !isSignBitSet(); } | |||
| 384 | ||||
| 385 | /// Determine if this APInt Value is positive. | |||
| 386 | /// | |||
| 387 | /// This tests if the value of this APInt is positive (> 0). Note | |||
| 388 | /// that 0 is not a positive value. | |||
| 389 | /// | |||
| 390 | /// \returns true if this APInt is positive. | |||
| 391 | bool isStrictlyPositive() const { return isNonNegative() && !isNullValue(); } | |||
| 392 | ||||
| 393 | /// Determine if this APInt Value is non-positive (<= 0). | |||
| 394 | /// | |||
| 395 | /// \returns true if this APInt is non-positive. | |||
| 396 | bool isNonPositive() const { return !isStrictlyPositive(); } | |||
| 397 | ||||
| 398 | /// Determine if all bits are set | |||
| 399 | /// | |||
| 400 | /// This checks to see if the value has all bits of the APInt are set or not. | |||
| 401 | bool isAllOnesValue() const { | |||
| 402 | if (isSingleWord()) | |||
| 403 | return U.VAL == WORDTYPE_MAX >> (APINT_BITS_PER_WORD - BitWidth); | |||
| 404 | return countTrailingOnesSlowCase() == BitWidth; | |||
| 405 | } | |||
| 406 | ||||
| 407 | /// Determine if all bits are clear | |||
| 408 | /// | |||
| 409 | /// This checks to see if the value has all bits of the APInt are clear or | |||
| 410 | /// not. | |||
| 411 | bool isNullValue() const { return !*this; } | |||
| 412 | ||||
| 413 | /// Determine if this is a value of 1. | |||
| 414 | /// | |||
| 415 | /// This checks to see if the value of this APInt is one. | |||
| 416 | bool isOneValue() const { | |||
| 417 | if (isSingleWord()) | |||
| 418 | return U.VAL == 1; | |||
| 419 | return countLeadingZerosSlowCase() == BitWidth - 1; | |||
| 420 | } | |||
| 421 | ||||
| 422 | /// Determine if this is the largest unsigned value. | |||
| 423 | /// | |||
| 424 | /// This checks to see if the value of this APInt is the maximum unsigned | |||
| 425 | /// value for the APInt's bit width. | |||
| 426 | bool isMaxValue() const { return isAllOnesValue(); } | |||
| 427 | ||||
| 428 | /// Determine if this is the largest signed value. | |||
| 429 | /// | |||
| 430 | /// This checks to see if the value of this APInt is the maximum signed | |||
| 431 | /// value for the APInt's bit width. | |||
| 432 | bool isMaxSignedValue() const { | |||
| 433 | if (isSingleWord()) | |||
| 434 | return U.VAL == ((WordType(1) << (BitWidth - 1)) - 1); | |||
| 435 | return !isNegative() && countTrailingOnesSlowCase() == BitWidth - 1; | |||
| 436 | } | |||
| 437 | ||||
| 438 | /// Determine if this is the smallest unsigned value. | |||
| 439 | /// | |||
| 440 | /// This checks to see if the value of this APInt is the minimum unsigned | |||
| 441 | /// value for the APInt's bit width. | |||
| 442 | bool isMinValue() const { return isNullValue(); } | |||
| 443 | ||||
| 444 | /// Determine if this is the smallest signed value. | |||
| 445 | /// | |||
| 446 | /// This checks to see if the value of this APInt is the minimum signed | |||
| 447 | /// value for the APInt's bit width. | |||
| 448 | bool isMinSignedValue() const { | |||
| 449 | if (isSingleWord()) | |||
| 450 | return U.VAL == (WordType(1) << (BitWidth - 1)); | |||
| 451 | return isNegative() && countTrailingZerosSlowCase() == BitWidth - 1; | |||
| 452 | } | |||
| 453 | ||||
| 454 | /// Check if this APInt has an N-bits unsigned integer value. | |||
| 455 | bool isIntN(unsigned N) const { | |||
| 456 | assert(N && "N == 0 ???")((void)0); | |||
| 457 | return getActiveBits() <= N; | |||
| 458 | } | |||
| 459 | ||||
| 460 | /// Check if this APInt has an N-bits signed integer value. | |||
| 461 | bool isSignedIntN(unsigned N) const { | |||
| 462 | assert(N && "N == 0 ???")((void)0); | |||
| 463 | return getMinSignedBits() <= N; | |||
| 464 | } | |||
| 465 | ||||
| 466 | /// Check if this APInt's value is a power of two greater than zero. | |||
| 467 | /// | |||
| 468 | /// \returns true if the argument APInt value is a power of two > 0. | |||
| 469 | bool isPowerOf2() const { | |||
| 470 | if (isSingleWord()) | |||
| 471 | return isPowerOf2_64(U.VAL); | |||
| 472 | return countPopulationSlowCase() == 1; | |||
| 473 | } | |||
| 474 | ||||
| 475 | /// Check if the APInt's value is returned by getSignMask. | |||
| 476 | /// | |||
| 477 | /// \returns true if this is the value returned by getSignMask. | |||
| 478 | bool isSignMask() const { return isMinSignedValue(); } | |||
| 479 | ||||
| 480 | /// Convert APInt to a boolean value. | |||
| 481 | /// | |||
| 482 | /// This converts the APInt to a boolean value as a test against zero. | |||
| 483 | bool getBoolValue() const { return !!*this; } | |||
| 484 | ||||
| 485 | /// If this value is smaller than the specified limit, return it, otherwise | |||
| 486 | /// return the limit value. This causes the value to saturate to the limit. | |||
| 487 | uint64_t getLimitedValue(uint64_t Limit = UINT64_MAX0xffffffffffffffffULL) const { | |||
| 488 | return ugt(Limit) ? Limit : getZExtValue(); | |||
| 489 | } | |||
| 490 | ||||
| 491 | /// Check if the APInt consists of a repeated bit pattern. | |||
| 492 | /// | |||
| 493 | /// e.g. 0x01010101 satisfies isSplat(8). | |||
| 494 | /// \param SplatSizeInBits The size of the pattern in bits. Must divide bit | |||
| 495 | /// width without remainder. | |||
| 496 | bool isSplat(unsigned SplatSizeInBits) const; | |||
| 497 | ||||
| 498 | /// \returns true if this APInt value is a sequence of \param numBits ones | |||
| 499 | /// starting at the least significant bit with the remainder zero. | |||
| 500 | bool isMask(unsigned numBits) const { | |||
| 501 | assert(numBits != 0 && "numBits must be non-zero")((void)0); | |||
| 502 | assert(numBits <= BitWidth && "numBits out of range")((void)0); | |||
| 503 | if (isSingleWord()) | |||
| 504 | return U.VAL == (WORDTYPE_MAX >> (APINT_BITS_PER_WORD - numBits)); | |||
| 505 | unsigned Ones = countTrailingOnesSlowCase(); | |||
| 506 | return (numBits == Ones) && | |||
| 507 | ((Ones + countLeadingZerosSlowCase()) == BitWidth); | |||
| 508 | } | |||
| 509 | ||||
| 510 | /// \returns true if this APInt is a non-empty sequence of ones starting at | |||
| 511 | /// the least significant bit with the remainder zero. | |||
| 512 | /// Ex. isMask(0x0000FFFFU) == true. | |||
| 513 | bool isMask() const { | |||
| 514 | if (isSingleWord()) | |||
| 515 | return isMask_64(U.VAL); | |||
| 516 | unsigned Ones = countTrailingOnesSlowCase(); | |||
| 517 | return (Ones > 0) && ((Ones + countLeadingZerosSlowCase()) == BitWidth); | |||
| 518 | } | |||
| 519 | ||||
| 520 | /// Return true if this APInt value contains a sequence of ones with | |||
| 521 | /// the remainder zero. | |||
| 522 | bool isShiftedMask() const { | |||
| 523 | if (isSingleWord()) | |||
| 524 | return isShiftedMask_64(U.VAL); | |||
| 525 | unsigned Ones = countPopulationSlowCase(); | |||
| 526 | unsigned LeadZ = countLeadingZerosSlowCase(); | |||
| 527 | return (Ones + LeadZ + countTrailingZeros()) == BitWidth; | |||
| 528 | } | |||
| 529 | ||||
| 530 | /// @} | |||
| 531 | /// \name Value Generators | |||
| 532 | /// @{ | |||
| 533 | ||||
| 534 | /// Gets maximum unsigned value of APInt for specific bit width. | |||
| 535 | static APInt getMaxValue(unsigned numBits) { | |||
| 536 | return getAllOnesValue(numBits); | |||
| 537 | } | |||
| 538 | ||||
| 539 | /// Gets maximum signed value of APInt for a specific bit width. | |||
| 540 | static APInt getSignedMaxValue(unsigned numBits) { | |||
| 541 | APInt API = getAllOnesValue(numBits); | |||
| 542 | API.clearBit(numBits - 1); | |||
| 543 | return API; | |||
| 544 | } | |||
| 545 | ||||
| 546 | /// Gets minimum unsigned value of APInt for a specific bit width. | |||
| 547 | static APInt getMinValue(unsigned numBits) { return APInt(numBits, 0); } | |||
| 548 | ||||
| 549 | /// Gets minimum signed value of APInt for a specific bit width. | |||
| 550 | static APInt getSignedMinValue(unsigned numBits) { | |||
| 551 | APInt API(numBits, 0); | |||
| 552 | API.setBit(numBits - 1); | |||
| 553 | return API; | |||
| 554 | } | |||
| 555 | ||||
| 556 | /// Get the SignMask for a specific bit width. | |||
| 557 | /// | |||
| 558 | /// This is just a wrapper function of getSignedMinValue(), and it helps code | |||
| 559 | /// readability when we want to get a SignMask. | |||
| 560 | static APInt getSignMask(unsigned BitWidth) { | |||
| 561 | return getSignedMinValue(BitWidth); | |||
| 562 | } | |||
| 563 | ||||
| 564 | /// Get the all-ones value. | |||
| 565 | /// | |||
| 566 | /// \returns the all-ones value for an APInt of the specified bit-width. | |||
| 567 | static APInt getAllOnesValue(unsigned numBits) { | |||
| 568 | return APInt(numBits, WORDTYPE_MAX, true); | |||
| 569 | } | |||
| 570 | ||||
| 571 | /// Get the '0' value. | |||
| 572 | /// | |||
| 573 | /// \returns the '0' value for an APInt of the specified bit-width. | |||
| 574 | static APInt getNullValue(unsigned numBits) { return APInt(numBits, 0); } | |||
| 575 | ||||
| 576 | /// Compute an APInt containing numBits highbits from this APInt. | |||
| 577 | /// | |||
| 578 | /// Get an APInt with the same BitWidth as this APInt, just zero mask | |||
| 579 | /// the low bits and right shift to the least significant bit. | |||
| 580 | /// | |||
| 581 | /// \returns the high "numBits" bits of this APInt. | |||
| 582 | APInt getHiBits(unsigned numBits) const; | |||
| 583 | ||||
| 584 | /// Compute an APInt containing numBits lowbits from this APInt. | |||
| 585 | /// | |||
| 586 | /// Get an APInt with the same BitWidth as this APInt, just zero mask | |||
| 587 | /// the high bits. | |||
| 588 | /// | |||
| 589 | /// \returns the low "numBits" bits of this APInt. | |||
| 590 | APInt getLoBits(unsigned numBits) const; | |||
| 591 | ||||
| 592 | /// Return an APInt with exactly one bit set in the result. | |||
| 593 | static APInt getOneBitSet(unsigned numBits, unsigned BitNo) { | |||
| 594 | APInt Res(numBits, 0); | |||
| 595 | Res.setBit(BitNo); | |||
| 596 | return Res; | |||
| 597 | } | |||
| 598 | ||||
| 599 | /// Get a value with a block of bits set. | |||
| 600 | /// | |||
| 601 | /// Constructs an APInt value that has a contiguous range of bits set. The | |||
| 602 | /// bits from loBit (inclusive) to hiBit (exclusive) will be set. All other | |||
| 603 | /// bits will be zero. For example, with parameters(32, 0, 16) you would get | |||
| 604 | /// 0x0000FFFF. Please call getBitsSetWithWrap if \p loBit may be greater than | |||
| 605 | /// \p hiBit. | |||
| 606 | /// | |||
| 607 | /// \param numBits the intended bit width of the result | |||
| 608 | /// \param loBit the index of the lowest bit set. | |||
| 609 | /// \param hiBit the index of the highest bit set. | |||
| 610 | /// | |||
| 611 | /// \returns An APInt value with the requested bits set. | |||
| 612 | static APInt getBitsSet(unsigned numBits, unsigned loBit, unsigned hiBit) { | |||
| 613 | assert(loBit <= hiBit && "loBit greater than hiBit")((void)0); | |||
| 614 | APInt Res(numBits, 0); | |||
| 615 | Res.setBits(loBit, hiBit); | |||
| 616 | return Res; | |||
| 617 | } | |||
| 618 | ||||
| 619 | /// Wrap version of getBitsSet. | |||
| 620 | /// If \p hiBit is bigger than \p loBit, this is same with getBitsSet. | |||
| 621 | /// If \p hiBit is not bigger than \p loBit, the set bits "wrap". For example, | |||
| 622 | /// with parameters (32, 28, 4), you would get 0xF000000F. | |||
| 623 | /// If \p hiBit is equal to \p loBit, you would get a result with all bits | |||
| 624 | /// set. | |||
| 625 | static APInt getBitsSetWithWrap(unsigned numBits, unsigned loBit, | |||
| 626 | unsigned hiBit) { | |||
| 627 | APInt Res(numBits, 0); | |||
| 628 | Res.setBitsWithWrap(loBit, hiBit); | |||
| 629 | return Res; | |||
| 630 | } | |||
| 631 | ||||
| 632 | /// Get a value with upper bits starting at loBit set. | |||
| 633 | /// | |||
| 634 | /// Constructs an APInt value that has a contiguous range of bits set. The | |||
| 635 | /// bits from loBit (inclusive) to numBits (exclusive) will be set. All other | |||
| 636 | /// bits will be zero. For example, with parameters(32, 12) you would get | |||
| 637 | /// 0xFFFFF000. | |||
| 638 | /// | |||
| 639 | /// \param numBits the intended bit width of the result | |||
| 640 | /// \param loBit the index of the lowest bit to set. | |||
| 641 | /// | |||
| 642 | /// \returns An APInt value with the requested bits set. | |||
| 643 | static APInt getBitsSetFrom(unsigned numBits, unsigned loBit) { | |||
| 644 | APInt Res(numBits, 0); | |||
| 645 | Res.setBitsFrom(loBit); | |||
| 646 | return Res; | |||
| 647 | } | |||
| 648 | ||||
| 649 | /// Get a value with high bits set | |||
| 650 | /// | |||
| 651 | /// Constructs an APInt value that has the top hiBitsSet bits set. | |||
| 652 | /// | |||
| 653 | /// \param numBits the bitwidth of the result | |||
| 654 | /// \param hiBitsSet the number of high-order bits set in the result. | |||
| 655 | static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet) { | |||
| 656 | APInt Res(numBits, 0); | |||
| 657 | Res.setHighBits(hiBitsSet); | |||
| 658 | return Res; | |||
| 659 | } | |||
| 660 | ||||
| 661 | /// Get a value with low bits set | |||
| 662 | /// | |||
| 663 | /// Constructs an APInt value that has the bottom loBitsSet bits set. | |||
| 664 | /// | |||
| 665 | /// \param numBits the bitwidth of the result | |||
| 666 | /// \param loBitsSet the number of low-order bits set in the result. | |||
| 667 | static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet) { | |||
| 668 | APInt Res(numBits, 0); | |||
| 669 | Res.setLowBits(loBitsSet); | |||
| 670 | return Res; | |||
| 671 | } | |||
| 672 | ||||
| 673 | /// Return a value containing V broadcasted over NewLen bits. | |||
| 674 | static APInt getSplat(unsigned NewLen, const APInt &V); | |||
| 675 | ||||
| 676 | /// Determine if two APInts have the same value, after zero-extending | |||
| 677 | /// one of them (if needed!) to ensure that the bit-widths match. | |||
| 678 | static bool isSameValue(const APInt &I1, const APInt &I2) { | |||
| 679 | if (I1.getBitWidth() == I2.getBitWidth()) | |||
| 680 | return I1 == I2; | |||
| 681 | ||||
| 682 | if (I1.getBitWidth() > I2.getBitWidth()) | |||
| 683 | return I1 == I2.zext(I1.getBitWidth()); | |||
| 684 | ||||
| 685 | return I1.zext(I2.getBitWidth()) == I2; | |||
| 686 | } | |||
| 687 | ||||
| 688 | /// Overload to compute a hash_code for an APInt value. | |||
| 689 | friend hash_code hash_value(const APInt &Arg); | |||
| 690 | ||||
| 691 | /// This function returns a pointer to the internal storage of the APInt. | |||
| 692 | /// This is useful for writing out the APInt in binary form without any | |||
| 693 | /// conversions. | |||
| 694 | const uint64_t *getRawData() const { | |||
| 695 | if (isSingleWord()) | |||
| 696 | return &U.VAL; | |||
| 697 | return &U.pVal[0]; | |||
| 698 | } | |||
| 699 | ||||
| 700 | /// @} | |||
| 701 | /// \name Unary Operators | |||
| 702 | /// @{ | |||
| 703 | ||||
| 704 | /// Postfix increment operator. | |||
| 705 | /// | |||
| 706 | /// Increments *this by 1. | |||
| 707 | /// | |||
| 708 | /// \returns a new APInt value representing the original value of *this. | |||
| 709 | const APInt operator++(int) { | |||
| 710 | APInt API(*this); | |||
| 711 | ++(*this); | |||
| 712 | return API; | |||
| 713 | } | |||
| 714 | ||||
| 715 | /// Prefix increment operator. | |||
| 716 | /// | |||
| 717 | /// \returns *this incremented by one | |||
| 718 | APInt &operator++(); | |||
| 719 | ||||
| 720 | /// Postfix decrement operator. | |||
| 721 | /// | |||
| 722 | /// Decrements *this by 1. | |||
| 723 | /// | |||
| 724 | /// \returns a new APInt value representing the original value of *this. | |||
| 725 | const APInt operator--(int) { | |||
| 726 | APInt API(*this); | |||
| 727 | --(*this); | |||
| 728 | return API; | |||
| 729 | } | |||
| 730 | ||||
| 731 | /// Prefix decrement operator. | |||
| 732 | /// | |||
| 733 | /// \returns *this decremented by one. | |||
| 734 | APInt &operator--(); | |||
| 735 | ||||
| 736 | /// Logical negation operator. | |||
| 737 | /// | |||
| 738 | /// Performs logical negation operation on this APInt. | |||
| 739 | /// | |||
| 740 | /// \returns true if *this is zero, false otherwise. | |||
| 741 | bool operator!() const { | |||
| 742 | if (isSingleWord()) | |||
| 743 | return U.VAL == 0; | |||
| 744 | return countLeadingZerosSlowCase() == BitWidth; | |||
| 745 | } | |||
| 746 | ||||
| 747 | /// @} | |||
| 748 | /// \name Assignment Operators | |||
| 749 | /// @{ | |||
| 750 | ||||
| 751 | /// Copy assignment operator. | |||
| 752 | /// | |||
| 753 | /// \returns *this after assignment of RHS. | |||
| 754 | APInt &operator=(const APInt &RHS) { | |||
| 755 | // If the bitwidths are the same, we can avoid mucking with memory | |||
| 756 | if (isSingleWord() && RHS.isSingleWord()) { | |||
| 757 | U.VAL = RHS.U.VAL; | |||
| 758 | BitWidth = RHS.BitWidth; | |||
| 759 | return clearUnusedBits(); | |||
| 760 | } | |||
| 761 | ||||
| 762 | AssignSlowCase(RHS); | |||
| 763 | return *this; | |||
| 764 | } | |||
| 765 | ||||
| 766 | /// Move assignment operator. | |||
| 767 | APInt &operator=(APInt &&that) { | |||
| 768 | #ifdef EXPENSIVE_CHECKS | |||
| 769 | // Some std::shuffle implementations still do self-assignment. | |||
| 770 | if (this == &that) | |||
| 771 | return *this; | |||
| 772 | #endif | |||
| 773 | assert(this != &that && "Self-move not supported")((void)0); | |||
| 774 | if (!isSingleWord()) | |||
| 775 | delete[] U.pVal; | |||
| 776 | ||||
| 777 | // Use memcpy so that type based alias analysis sees both VAL and pVal | |||
| 778 | // as modified. | |||
| 779 | memcpy(&U, &that.U, sizeof(U)); | |||
| 780 | ||||
| 781 | BitWidth = that.BitWidth; | |||
| 782 | that.BitWidth = 0; | |||
| 783 | ||||
| 784 | return *this; | |||
| 785 | } | |||
| 786 | ||||
| 787 | /// Assignment operator. | |||
| 788 | /// | |||
| 789 | /// The RHS value is assigned to *this. If the significant bits in RHS exceed | |||
| 790 | /// the bit width, the excess bits are truncated. If the bit width is larger | |||
| 791 | /// than 64, the value is zero filled in the unspecified high order bits. | |||
| 792 | /// | |||
| 793 | /// \returns *this after assignment of RHS value. | |||
| 794 | APInt &operator=(uint64_t RHS) { | |||
| 795 | if (isSingleWord()) { | |||
| 796 | U.VAL = RHS; | |||
| 797 | return clearUnusedBits(); | |||
| 798 | } | |||
| 799 | U.pVal[0] = RHS; | |||
| 800 | memset(U.pVal + 1, 0, (getNumWords() - 1) * APINT_WORD_SIZE); | |||
| 801 | return *this; | |||
| 802 | } | |||
| 803 | ||||
| 804 | /// Bitwise AND assignment operator. | |||
| 805 | /// | |||
| 806 | /// Performs a bitwise AND operation on this APInt and RHS. The result is | |||
| 807 | /// assigned to *this. | |||
| 808 | /// | |||
| 809 | /// \returns *this after ANDing with RHS. | |||
| 810 | APInt &operator&=(const APInt &RHS) { | |||
| 811 | assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")((void)0); | |||
| 812 | if (isSingleWord()) | |||
| 813 | U.VAL &= RHS.U.VAL; | |||
| 814 | else | |||
| 815 | AndAssignSlowCase(RHS); | |||
| 816 | return *this; | |||
| 817 | } | |||
| 818 | ||||
| 819 | /// Bitwise AND assignment operator. | |||
| 820 | /// | |||
| 821 | /// Performs a bitwise AND operation on this APInt and RHS. RHS is | |||
| 822 | /// logically zero-extended or truncated to match the bit-width of | |||
| 823 | /// the LHS. | |||
| 824 | APInt &operator&=(uint64_t RHS) { | |||
| 825 | if (isSingleWord()) { | |||
| 826 | U.VAL &= RHS; | |||
| 827 | return *this; | |||
| 828 | } | |||
| 829 | U.pVal[0] &= RHS; | |||
| 830 | memset(U.pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE); | |||
| 831 | return *this; | |||
| 832 | } | |||
| 833 | ||||
| 834 | /// Bitwise OR assignment operator. | |||
| 835 | /// | |||
| 836 | /// Performs a bitwise OR operation on this APInt and RHS. The result is | |||
| 837 | /// assigned *this; | |||
| 838 | /// | |||
| 839 | /// \returns *this after ORing with RHS. | |||
| 840 | APInt &operator|=(const APInt &RHS) { | |||
| 841 | assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")((void)0); | |||
| 842 | if (isSingleWord()) | |||
| 843 | U.VAL |= RHS.U.VAL; | |||
| 844 | else | |||
| 845 | OrAssignSlowCase(RHS); | |||
| 846 | return *this; | |||
| 847 | } | |||
| 848 | ||||
| 849 | /// Bitwise OR assignment operator. | |||
| 850 | /// | |||
| 851 | /// Performs a bitwise OR operation on this APInt and RHS. RHS is | |||
| 852 | /// logically zero-extended or truncated to match the bit-width of | |||
| 853 | /// the LHS. | |||
| 854 | APInt &operator|=(uint64_t RHS) { | |||
| 855 | if (isSingleWord()) { | |||
| 856 | U.VAL |= RHS; | |||
| 857 | return clearUnusedBits(); | |||
| 858 | } | |||
| 859 | U.pVal[0] |= RHS; | |||
| 860 | return *this; | |||
| 861 | } | |||
| 862 | ||||
| 863 | /// Bitwise XOR assignment operator. | |||
| 864 | /// | |||
| 865 | /// Performs a bitwise XOR operation on this APInt and RHS. The result is | |||
| 866 | /// assigned to *this. | |||
| 867 | /// | |||
| 868 | /// \returns *this after XORing with RHS. | |||
| 869 | APInt &operator^=(const APInt &RHS) { | |||
| 870 | assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")((void)0); | |||
| 871 | if (isSingleWord()) | |||
| 872 | U.VAL ^= RHS.U.VAL; | |||
| 873 | else | |||
| 874 | XorAssignSlowCase(RHS); | |||
| 875 | return *this; | |||
| 876 | } | |||
| 877 | ||||
| 878 | /// Bitwise XOR assignment operator. | |||
| 879 | /// | |||
| 880 | /// Performs a bitwise XOR operation on this APInt and RHS. RHS is | |||
| 881 | /// logically zero-extended or truncated to match the bit-width of | |||
| 882 | /// the LHS. | |||
| 883 | APInt &operator^=(uint64_t RHS) { | |||
| 884 | if (isSingleWord()) { | |||
| 885 | U.VAL ^= RHS; | |||
| 886 | return clearUnusedBits(); | |||
| 887 | } | |||
| 888 | U.pVal[0] ^= RHS; | |||
| 889 | return *this; | |||
| 890 | } | |||
| 891 | ||||
| 892 | /// Multiplication assignment operator. | |||
| 893 | /// | |||
| 894 | /// Multiplies this APInt by RHS and assigns the result to *this. | |||
| 895 | /// | |||
| 896 | /// \returns *this | |||
| 897 | APInt &operator*=(const APInt &RHS); | |||
| 898 | APInt &operator*=(uint64_t RHS); | |||
| 899 | ||||
| 900 | /// Addition assignment operator. | |||
| 901 | /// | |||
| 902 | /// Adds RHS to *this and assigns the result to *this. | |||
| 903 | /// | |||
| 904 | /// \returns *this | |||
| 905 | APInt &operator+=(const APInt &RHS); | |||
| 906 | APInt &operator+=(uint64_t RHS); | |||
| 907 | ||||
| 908 | /// Subtraction assignment operator. | |||
| 909 | /// | |||
| 910 | /// Subtracts RHS from *this and assigns the result to *this. | |||
| 911 | /// | |||
| 912 | /// \returns *this | |||
| 913 | APInt &operator-=(const APInt &RHS); | |||
| 914 | APInt &operator-=(uint64_t RHS); | |||
| 915 | ||||
| 916 | /// Left-shift assignment function. | |||
| 917 | /// | |||
| 918 | /// Shifts *this left by shiftAmt and assigns the result to *this. | |||
| 919 | /// | |||
| 920 | /// \returns *this after shifting left by ShiftAmt | |||
| 921 | APInt &operator<<=(unsigned ShiftAmt) { | |||
| 922 | assert(ShiftAmt <= BitWidth && "Invalid shift amount")((void)0); | |||
| 923 | if (isSingleWord()) { | |||
| 924 | if (ShiftAmt == BitWidth) | |||
| 925 | U.VAL = 0; | |||
| 926 | else | |||
| 927 | U.VAL <<= ShiftAmt; | |||
| 928 | return clearUnusedBits(); | |||
| 929 | } | |||
| 930 | shlSlowCase(ShiftAmt); | |||
| 931 | return *this; | |||
| 932 | } | |||
| 933 | ||||
| 934 | /// Left-shift assignment function. | |||
| 935 | /// | |||
| 936 | /// Shifts *this left by shiftAmt and assigns the result to *this. | |||
| 937 | /// | |||
| 938 | /// \returns *this after shifting left by ShiftAmt | |||
| 939 | APInt &operator<<=(const APInt &ShiftAmt); | |||
| 940 | ||||
| 941 | /// @} | |||
| 942 | /// \name Binary Operators | |||
| 943 | /// @{ | |||
| 944 | ||||
| 945 | /// Multiplication operator. | |||
| 946 | /// | |||
| 947 | /// Multiplies this APInt by RHS and returns the result. | |||
| 948 | APInt operator*(const APInt &RHS) const; | |||
| 949 | ||||
| 950 | /// Left logical shift operator. | |||
| 951 | /// | |||
| 952 | /// Shifts this APInt left by \p Bits and returns the result. | |||
| 953 | APInt operator<<(unsigned Bits) const { return shl(Bits); } | |||
| 954 | ||||
| 955 | /// Left logical shift operator. | |||
| 956 | /// | |||
| 957 | /// Shifts this APInt left by \p Bits and returns the result. | |||
| 958 | APInt operator<<(const APInt &Bits) const { return shl(Bits); } | |||
| 959 | ||||
| 960 | /// Arithmetic right-shift function. | |||
| 961 | /// | |||
| 962 | /// Arithmetic right-shift this APInt by shiftAmt. | |||
| 963 | APInt ashr(unsigned ShiftAmt) const { | |||
| 964 | APInt R(*this); | |||
| 965 | R.ashrInPlace(ShiftAmt); | |||
| 966 | return R; | |||
| 967 | } | |||
| 968 | ||||
| 969 | /// Arithmetic right-shift this APInt by ShiftAmt in place. | |||
| 970 | void ashrInPlace(unsigned ShiftAmt) { | |||
| 971 | assert(ShiftAmt <= BitWidth && "Invalid shift amount")((void)0); | |||
| 972 | if (isSingleWord()) { | |||
| 973 | int64_t SExtVAL = SignExtend64(U.VAL, BitWidth); | |||
| 974 | if (ShiftAmt == BitWidth) | |||
| 975 | U.VAL = SExtVAL >> (APINT_BITS_PER_WORD - 1); // Fill with sign bit. | |||
| 976 | else | |||
| 977 | U.VAL = SExtVAL >> ShiftAmt; | |||
| 978 | clearUnusedBits(); | |||
| 979 | return; | |||
| 980 | } | |||
| 981 | ashrSlowCase(ShiftAmt); | |||
| 982 | } | |||
| 983 | ||||
| 984 | /// Logical right-shift function. | |||
| 985 | /// | |||
| 986 | /// Logical right-shift this APInt by shiftAmt. | |||
| 987 | APInt lshr(unsigned shiftAmt) const { | |||
| 988 | APInt R(*this); | |||
| 989 | R.lshrInPlace(shiftAmt); | |||
| 990 | return R; | |||
| 991 | } | |||
| 992 | ||||
| 993 | /// Logical right-shift this APInt by ShiftAmt in place. | |||
| 994 | void lshrInPlace(unsigned ShiftAmt) { | |||
| 995 | assert(ShiftAmt <= BitWidth && "Invalid shift amount")((void)0); | |||
| 996 | if (isSingleWord()) { | |||
| 997 | if (ShiftAmt == BitWidth) | |||
| 998 | U.VAL = 0; | |||
| 999 | else | |||
| 1000 | U.VAL >>= ShiftAmt; | |||
| 1001 | return; | |||
| 1002 | } | |||
| 1003 | lshrSlowCase(ShiftAmt); | |||
| 1004 | } | |||
| 1005 | ||||
| 1006 | /// Left-shift function. | |||
| 1007 | /// | |||
| 1008 | /// Left-shift this APInt by shiftAmt. | |||
| 1009 | APInt shl(unsigned shiftAmt) const { | |||
| 1010 | APInt R(*this); | |||
| 1011 | R <<= shiftAmt; | |||
| 1012 | return R; | |||
| 1013 | } | |||
| 1014 | ||||
| 1015 | /// Rotate left by rotateAmt. | |||
| 1016 | APInt rotl(unsigned rotateAmt) const; | |||
| 1017 | ||||
| 1018 | /// Rotate right by rotateAmt. | |||
| 1019 | APInt rotr(unsigned rotateAmt) const; | |||
| 1020 | ||||
| 1021 | /// Arithmetic right-shift function. | |||
| 1022 | /// | |||
| 1023 | /// Arithmetic right-shift this APInt by shiftAmt. | |||
| 1024 | APInt ashr(const APInt &ShiftAmt) const { | |||
| 1025 | APInt R(*this); | |||
| 1026 | R.ashrInPlace(ShiftAmt); | |||
| 1027 | return R; | |||
| 1028 | } | |||
| 1029 | ||||
| 1030 | /// Arithmetic right-shift this APInt by shiftAmt in place. | |||
| 1031 | void ashrInPlace(const APInt &shiftAmt); | |||
| 1032 | ||||
| 1033 | /// Logical right-shift function. | |||
| 1034 | /// | |||
| 1035 | /// Logical right-shift this APInt by shiftAmt. | |||
| 1036 | APInt lshr(const APInt &ShiftAmt) const { | |||
| 1037 | APInt R(*this); | |||
| 1038 | R.lshrInPlace(ShiftAmt); | |||
| 1039 | return R; | |||
| 1040 | } | |||
| 1041 | ||||
| 1042 | /// Logical right-shift this APInt by ShiftAmt in place. | |||
| 1043 | void lshrInPlace(const APInt &ShiftAmt); | |||
| 1044 | ||||
| 1045 | /// Left-shift function. | |||
| 1046 | /// | |||
| 1047 | /// Left-shift this APInt by shiftAmt. | |||
| 1048 | APInt shl(const APInt &ShiftAmt) const { | |||
| 1049 | APInt R(*this); | |||
| 1050 | R <<= ShiftAmt; | |||
| 1051 | return R; | |||
| 1052 | } | |||
| 1053 | ||||
| 1054 | /// Rotate left by rotateAmt. | |||
| 1055 | APInt rotl(const APInt &rotateAmt) const; | |||
| 1056 | ||||
| 1057 | /// Rotate right by rotateAmt. | |||
| 1058 | APInt rotr(const APInt &rotateAmt) const; | |||
| 1059 | ||||
| 1060 | /// Unsigned division operation. | |||
| 1061 | /// | |||
| 1062 | /// Perform an unsigned divide operation on this APInt by RHS. Both this and | |||
| 1063 | /// RHS are treated as unsigned quantities for purposes of this division. | |||
| 1064 | /// | |||
| 1065 | /// \returns a new APInt value containing the division result, rounded towards | |||
| 1066 | /// zero. | |||
| 1067 | APInt udiv(const APInt &RHS) const; | |||
| 1068 | APInt udiv(uint64_t RHS) const; | |||
| 1069 | ||||
| 1070 | /// Signed division function for APInt. | |||
| 1071 | /// | |||
| 1072 | /// Signed divide this APInt by APInt RHS. | |||
| 1073 | /// | |||
| 1074 | /// The result is rounded towards zero. | |||
| 1075 | APInt sdiv(const APInt &RHS) const; | |||
| 1076 | APInt sdiv(int64_t RHS) const; | |||
| 1077 | ||||
| 1078 | /// Unsigned remainder operation. | |||
| 1079 | /// | |||
| 1080 | /// Perform an unsigned remainder operation on this APInt with RHS being the | |||
| 1081 | /// divisor. Both this and RHS are treated as unsigned quantities for purposes | |||
| 1082 | /// of this operation. Note that this is a true remainder operation and not a | |||
| 1083 | /// modulo operation because the sign follows the sign of the dividend which | |||
| 1084 | /// is *this. | |||
| 1085 | /// | |||
| 1086 | /// \returns a new APInt value containing the remainder result | |||
| 1087 | APInt urem(const APInt &RHS) const; | |||
| 1088 | uint64_t urem(uint64_t RHS) const; | |||
| 1089 | ||||
| 1090 | /// Function for signed remainder operation. | |||
| 1091 | /// | |||
| 1092 | /// Signed remainder operation on APInt. | |||
| 1093 | APInt srem(const APInt &RHS) const; | |||
| 1094 | int64_t srem(int64_t RHS) const; | |||
| 1095 | ||||
| 1096 | /// Dual division/remainder interface. | |||
| 1097 | /// | |||
| 1098 | /// Sometimes it is convenient to divide two APInt values and obtain both the | |||
| 1099 | /// quotient and remainder. This function does both operations in the same | |||
| 1100 | /// computation making it a little more efficient. The pair of input arguments | |||
| 1101 | /// may overlap with the pair of output arguments. It is safe to call | |||
| 1102 | /// udivrem(X, Y, X, Y), for example. | |||
| 1103 | static void udivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, | |||
| 1104 | APInt &Remainder); | |||
| 1105 | static void udivrem(const APInt &LHS, uint64_t RHS, APInt &Quotient, | |||
| 1106 | uint64_t &Remainder); | |||
| 1107 | ||||
| 1108 | static void sdivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, | |||
| 1109 | APInt &Remainder); | |||
| 1110 | static void sdivrem(const APInt &LHS, int64_t RHS, APInt &Quotient, | |||
| 1111 | int64_t &Remainder); | |||
| 1112 | ||||
| 1113 | // Operations that return overflow indicators. | |||
| 1114 | APInt sadd_ov(const APInt &RHS, bool &Overflow) const; | |||
| 1115 | APInt uadd_ov(const APInt &RHS, bool &Overflow) const; | |||
| 1116 | APInt ssub_ov(const APInt &RHS, bool &Overflow) const; | |||
| 1117 | APInt usub_ov(const APInt &RHS, bool &Overflow) const; | |||
| 1118 | APInt sdiv_ov(const APInt &RHS, bool &Overflow) const; | |||
| 1119 | APInt smul_ov(const APInt &RHS, bool &Overflow) const; | |||
| 1120 | APInt umul_ov(const APInt &RHS, bool &Overflow) const; | |||
| 1121 | APInt sshl_ov(const APInt &Amt, bool &Overflow) const; | |||
| 1122 | APInt ushl_ov(const APInt &Amt, bool &Overflow) const; | |||
| 1123 | ||||
| 1124 | // Operations that saturate | |||
| 1125 | APInt sadd_sat(const APInt &RHS) const; | |||
| 1126 | APInt uadd_sat(const APInt &RHS) const; | |||
| 1127 | APInt ssub_sat(const APInt &RHS) const; | |||
| 1128 | APInt usub_sat(const APInt &RHS) const; | |||
| 1129 | APInt smul_sat(const APInt &RHS) const; | |||
| 1130 | APInt umul_sat(const APInt &RHS) const; | |||
| 1131 | APInt sshl_sat(const APInt &RHS) const; | |||
| 1132 | APInt ushl_sat(const APInt &RHS) const; | |||
| 1133 | ||||
| 1134 | /// Array-indexing support. | |||
| 1135 | /// | |||
| 1136 | /// \returns the bit value at bitPosition | |||
| 1137 | bool operator[](unsigned bitPosition) const { | |||
| 1138 | assert(bitPosition < getBitWidth() && "Bit position out of bounds!")((void)0); | |||
| 1139 | return (maskBit(bitPosition) & getWord(bitPosition)) != 0; | |||
| 1140 | } | |||
| 1141 | ||||
| 1142 | /// @} | |||
| 1143 | /// \name Comparison Operators | |||
| 1144 | /// @{ | |||
| 1145 | ||||
| 1146 | /// Equality operator. | |||
| 1147 | /// | |||
| 1148 | /// Compares this APInt with RHS for the validity of the equality | |||
| 1149 | /// relationship. | |||
| 1150 | bool operator==(const APInt &RHS) const { | |||
| 1151 | assert(BitWidth == RHS.BitWidth && "Comparison requires equal bit widths")((void)0); | |||
| 1152 | if (isSingleWord()) | |||
| 1153 | return U.VAL == RHS.U.VAL; | |||
| 1154 | return EqualSlowCase(RHS); | |||
| 1155 | } | |||
| 1156 | ||||
| 1157 | /// Equality operator. | |||
| 1158 | /// | |||
| 1159 | /// Compares this APInt with a uint64_t for the validity of the equality | |||
| 1160 | /// relationship. | |||
| 1161 | /// | |||
| 1162 | /// \returns true if *this == Val | |||
| 1163 | bool operator==(uint64_t Val) const { | |||
| 1164 | return (isSingleWord() || getActiveBits() <= 64) && getZExtValue() == Val; | |||
| 1165 | } | |||
| 1166 | ||||
| 1167 | /// Equality comparison. | |||
| 1168 | /// | |||
| 1169 | /// Compares this APInt with RHS for the validity of the equality | |||
| 1170 | /// relationship. | |||
| 1171 | /// | |||
| 1172 | /// \returns true if *this == Val | |||
| 1173 | bool eq(const APInt &RHS) const { return (*this) == RHS; } | |||
| 1174 | ||||
| 1175 | /// Inequality operator. | |||
| 1176 | /// | |||
| 1177 | /// Compares this APInt with RHS for the validity of the inequality | |||
| 1178 | /// relationship. | |||
| 1179 | /// | |||
| 1180 | /// \returns true if *this != Val | |||
| 1181 | bool operator!=(const APInt &RHS) const { return !((*this) == RHS); } | |||
| 1182 | ||||
| 1183 | /// Inequality operator. | |||
| 1184 | /// | |||
| 1185 | /// Compares this APInt with a uint64_t for the validity of the inequality | |||
| 1186 | /// relationship. | |||
| 1187 | /// | |||
| 1188 | /// \returns true if *this != Val | |||
| 1189 | bool operator!=(uint64_t Val) const { return !((*this) == Val); } | |||
| 1190 | ||||
| 1191 | /// Inequality comparison | |||
| 1192 | /// | |||
| 1193 | /// Compares this APInt with RHS for the validity of the inequality | |||
| 1194 | /// relationship. | |||
| 1195 | /// | |||
| 1196 | /// \returns true if *this != Val | |||
| 1197 | bool ne(const APInt &RHS) const { return !((*this) == RHS); } | |||
| 1198 | ||||
| 1199 | /// Unsigned less than comparison | |||
| 1200 | /// | |||
| 1201 | /// Regards both *this and RHS as unsigned quantities and compares them for | |||
| 1202 | /// the validity of the less-than relationship. | |||
| 1203 | /// | |||
| 1204 | /// \returns true if *this < RHS when both are considered unsigned. | |||
| 1205 | bool ult(const APInt &RHS) const { return compare(RHS) < 0; } | |||
| 1206 | ||||
| 1207 | /// Unsigned less than comparison | |||
| 1208 | /// | |||
| 1209 | /// Regards both *this as an unsigned quantity and compares it with RHS for | |||
| 1210 | /// the validity of the less-than relationship. | |||
| 1211 | /// | |||
| 1212 | /// \returns true if *this < RHS when considered unsigned. | |||
| 1213 | bool ult(uint64_t RHS) const { | |||
| 1214 | // Only need to check active bits if not a single word. | |||
| 1215 | return (isSingleWord() || getActiveBits() <= 64) && getZExtValue() < RHS; | |||
| 1216 | } | |||
| 1217 | ||||
| 1218 | /// Signed less than comparison | |||
| 1219 | /// | |||
| 1220 | /// Regards both *this and RHS as signed quantities and compares them for | |||
| 1221 | /// validity of the less-than relationship. | |||
| 1222 | /// | |||
| 1223 | /// \returns true if *this < RHS when both are considered signed. | |||
| 1224 | bool slt(const APInt &RHS) const { return compareSigned(RHS) < 0; } | |||
| 1225 | ||||
| 1226 | /// Signed less than comparison | |||
| 1227 | /// | |||
| 1228 | /// Regards both *this as a signed quantity and compares it with RHS for | |||
| 1229 | /// the validity of the less-than relationship. | |||
| 1230 | /// | |||
| 1231 | /// \returns true if *this < RHS when considered signed. | |||
| 1232 | bool slt(int64_t RHS) const { | |||
| 1233 | return (!isSingleWord() && getMinSignedBits() > 64) ? isNegative() | |||
| 1234 | : getSExtValue() < RHS; | |||
| 1235 | } | |||
| 1236 | ||||
| 1237 | /// Unsigned less or equal comparison | |||
| 1238 | /// | |||
| 1239 | /// Regards both *this and RHS as unsigned quantities and compares them for | |||
| 1240 | /// validity of the less-or-equal relationship. | |||
| 1241 | /// | |||
| 1242 | /// \returns true if *this <= RHS when both are considered unsigned. | |||
| 1243 | bool ule(const APInt &RHS) const { return compare(RHS) <= 0; } | |||
| 1244 | ||||
| 1245 | /// Unsigned less or equal comparison | |||
| 1246 | /// | |||
| 1247 | /// Regards both *this as an unsigned quantity and compares it with RHS for | |||
| 1248 | /// the validity of the less-or-equal relationship. | |||
| 1249 | /// | |||
| 1250 | /// \returns true if *this <= RHS when considered unsigned. | |||
| 1251 | bool ule(uint64_t RHS) const { return !ugt(RHS); } | |||
| 1252 | ||||
| 1253 | /// Signed less or equal comparison | |||
| 1254 | /// | |||
| 1255 | /// Regards both *this and RHS as signed quantities and compares them for | |||
| 1256 | /// validity of the less-or-equal relationship. | |||
| 1257 | /// | |||
| 1258 | /// \returns true if *this <= RHS when both are considered signed. | |||
| 1259 | bool sle(const APInt &RHS) const { return compareSigned(RHS) <= 0; } | |||
| 1260 | ||||
| 1261 | /// Signed less or equal comparison | |||
| 1262 | /// | |||
| 1263 | /// Regards both *this as a signed quantity and compares it with RHS for the | |||
| 1264 | /// validity of the less-or-equal relationship. | |||
| 1265 | /// | |||
| 1266 | /// \returns true if *this <= RHS when considered signed. | |||
| 1267 | bool sle(uint64_t RHS) const { return !sgt(RHS); } | |||
| 1268 | ||||
| 1269 | /// Unsigned greater than comparison | |||
| 1270 | /// | |||
| 1271 | /// Regards both *this and RHS as unsigned quantities and compares them for | |||
| 1272 | /// the validity of the greater-than relationship. | |||
| 1273 | /// | |||
| 1274 | /// \returns true if *this > RHS when both are considered unsigned. | |||
| 1275 | bool ugt(const APInt &RHS) const { return !ule(RHS); } | |||
| 1276 | ||||
| 1277 | /// Unsigned greater than comparison | |||
| 1278 | /// | |||
| 1279 | /// Regards both *this as an unsigned quantity and compares it with RHS for | |||
| 1280 | /// the validity of the greater-than relationship. | |||
| 1281 | /// | |||
| 1282 | /// \returns true if *this > RHS when considered unsigned. | |||
| 1283 | bool ugt(uint64_t RHS) const { | |||
| 1284 | // Only need to check active bits if not a single word. | |||
| 1285 | return (!isSingleWord() && getActiveBits() > 64) || getZExtValue() > RHS; | |||
| 1286 | } | |||
| 1287 | ||||
| 1288 | /// Signed greater than comparison | |||
| 1289 | /// | |||
| 1290 | /// Regards both *this and RHS as signed quantities and compares them for the | |||
| 1291 | /// validity of the greater-than relationship. | |||
| 1292 | /// | |||
| 1293 | /// \returns true if *this > RHS when both are considered signed. | |||
| 1294 | bool sgt(const APInt &RHS) const { return !sle(RHS); } | |||
| 1295 | ||||
| 1296 | /// Signed greater than comparison | |||
| 1297 | /// | |||
| 1298 | /// Regards both *this as a signed quantity and compares it with RHS for | |||
| 1299 | /// the validity of the greater-than relationship. | |||
| 1300 | /// | |||
| 1301 | /// \returns true if *this > RHS when considered signed. | |||
| 1302 | bool sgt(int64_t RHS) const { | |||
| 1303 | return (!isSingleWord() && getMinSignedBits() > 64) ? !isNegative() | |||
| 1304 | : getSExtValue() > RHS; | |||
| 1305 | } | |||
| 1306 | ||||
| 1307 | /// Unsigned greater or equal comparison | |||
| 1308 | /// | |||
| 1309 | /// Regards both *this and RHS as unsigned quantities and compares them for | |||
| 1310 | /// validity of the greater-or-equal relationship. | |||
| 1311 | /// | |||
| 1312 | /// \returns true if *this >= RHS when both are considered unsigned. | |||
| 1313 | bool uge(const APInt &RHS) const { return !ult(RHS); } | |||
| 1314 | ||||
| 1315 | /// Unsigned greater or equal comparison | |||
| 1316 | /// | |||
| 1317 | /// Regards both *this as an unsigned quantity and compares it with RHS for | |||
| 1318 | /// the validity of the greater-or-equal relationship. | |||
| 1319 | /// | |||
| 1320 | /// \returns true if *this >= RHS when considered unsigned. | |||
| 1321 | bool uge(uint64_t RHS) const { return !ult(RHS); } | |||
| 1322 | ||||
| 1323 | /// Signed greater or equal comparison | |||
| 1324 | /// | |||
| 1325 | /// Regards both *this and RHS as signed quantities and compares them for | |||
| 1326 | /// validity of the greater-or-equal relationship. | |||
| 1327 | /// | |||
| 1328 | /// \returns true if *this >= RHS when both are considered signed. | |||
| 1329 | bool sge(const APInt &RHS) const { return !slt(RHS); } | |||
| 1330 | ||||
| 1331 | /// Signed greater or equal comparison | |||
| 1332 | /// | |||
| 1333 | /// Regards both *this as a signed quantity and compares it with RHS for | |||
| 1334 | /// the validity of the greater-or-equal relationship. | |||
| 1335 | /// | |||
| 1336 | /// \returns true if *this >= RHS when considered signed. | |||
| 1337 | bool sge(int64_t RHS) const { return !slt(RHS); } | |||
| 1338 | ||||
| 1339 | /// This operation tests if there are any pairs of corresponding bits | |||
| 1340 | /// between this APInt and RHS that are both set. | |||
| 1341 | bool intersects(const APInt &RHS) const { | |||
| 1342 | assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")((void)0); | |||
| 1343 | if (isSingleWord()) | |||
| 1344 | return (U.VAL & RHS.U.VAL) != 0; | |||
| 1345 | return intersectsSlowCase(RHS); | |||
| 1346 | } | |||
| 1347 | ||||
| 1348 | /// This operation checks that all bits set in this APInt are also set in RHS. | |||
| 1349 | bool isSubsetOf(const APInt &RHS) const { | |||
| 1350 | assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")((void)0); | |||
| 1351 | if (isSingleWord()) | |||
| 1352 | return (U.VAL & ~RHS.U.VAL) == 0; | |||
| 1353 | return isSubsetOfSlowCase(RHS); | |||
| 1354 | } | |||
| 1355 | ||||
| 1356 | /// @} | |||
| 1357 | /// \name Resizing Operators | |||
| 1358 | /// @{ | |||
| 1359 | ||||
| 1360 | /// Truncate to new width. | |||
| 1361 | /// | |||
| 1362 | /// Truncate the APInt to a specified width. It is an error to specify a width | |||
| 1363 | /// that is greater than or equal to the current width. | |||
| 1364 | APInt trunc(unsigned width) const; | |||
| 1365 | ||||
| 1366 | /// Truncate to new width with unsigned saturation. | |||
| 1367 | /// | |||
| 1368 | /// If the APInt, treated as unsigned integer, can be losslessly truncated to | |||
| 1369 | /// the new bitwidth, then return truncated APInt. Else, return max value. | |||
| 1370 | APInt truncUSat(unsigned width) const; | |||
| 1371 | ||||
| 1372 | /// Truncate to new width with signed saturation. | |||
| 1373 | /// | |||
| 1374 | /// If this APInt, treated as signed integer, can be losslessly truncated to | |||
| 1375 | /// the new bitwidth, then return truncated APInt. Else, return either | |||
| 1376 | /// signed min value if the APInt was negative, or signed max value. | |||
| 1377 | APInt truncSSat(unsigned width) const; | |||
| 1378 | ||||
| 1379 | /// Sign extend to a new width. | |||
| 1380 | /// | |||
| 1381 | /// This operation sign extends the APInt to a new width. If the high order | |||
| 1382 | /// bit is set, the fill on the left will be done with 1 bits, otherwise zero. | |||
| 1383 | /// It is an error to specify a width that is less than or equal to the | |||
| 1384 | /// current width. | |||
| 1385 | APInt sext(unsigned width) const; | |||
| 1386 | ||||
| 1387 | /// Zero extend to a new width. | |||
| 1388 | /// | |||
| 1389 | /// This operation zero extends the APInt to a new width. The high order bits | |||
| 1390 | /// are filled with 0 bits. It is an error to specify a width that is less | |||
| 1391 | /// than or equal to the current width. | |||
| 1392 | APInt zext(unsigned width) const; | |||
| 1393 | ||||
| 1394 | /// Sign extend or truncate to width | |||
| 1395 | /// | |||
| 1396 | /// Make this APInt have the bit width given by \p width. The value is sign | |||
| 1397 | /// extended, truncated, or left alone to make it that width. | |||
| 1398 | APInt sextOrTrunc(unsigned width) const; | |||
| 1399 | ||||
| 1400 | /// Zero extend or truncate to width | |||
| 1401 | /// | |||
| 1402 | /// Make this APInt have the bit width given by \p width. The value is zero | |||
| 1403 | /// extended, truncated, or left alone to make it that width. | |||
| 1404 | APInt zextOrTrunc(unsigned width) const; | |||
| 1405 | ||||
| 1406 | /// Truncate to width | |||
| 1407 | /// | |||
| 1408 | /// Make this APInt have the bit width given by \p width. The value is | |||
| 1409 | /// truncated or left alone to make it that width. | |||
| 1410 | APInt truncOrSelf(unsigned width) const; | |||
| 1411 | ||||
| 1412 | /// Sign extend or truncate to width | |||
| 1413 | /// | |||
| 1414 | /// Make this APInt have the bit width given by \p width. The value is sign | |||
| 1415 | /// extended, or left alone to make it that width. | |||
| 1416 | APInt sextOrSelf(unsigned width) const; | |||
| 1417 | ||||
| 1418 | /// Zero extend or truncate to width | |||
| 1419 | /// | |||
| 1420 | /// Make this APInt have the bit width given by \p width. The value is zero | |||
| 1421 | /// extended, or left alone to make it that width. | |||
| 1422 | APInt zextOrSelf(unsigned width) const; | |||
| 1423 | ||||
| 1424 | /// @} | |||
| 1425 | /// \name Bit Manipulation Operators | |||
| 1426 | /// @{ | |||
| 1427 | ||||
| 1428 | /// Set every bit to 1. | |||
| 1429 | void setAllBits() { | |||
| 1430 | if (isSingleWord()) | |||
| 1431 | U.VAL = WORDTYPE_MAX; | |||
| 1432 | else | |||
| 1433 | // Set all the bits in all the words. | |||
| 1434 | memset(U.pVal, -1, getNumWords() * APINT_WORD_SIZE); | |||
| 1435 | // Clear the unused ones | |||
| 1436 | clearUnusedBits(); | |||
| 1437 | } | |||
| 1438 | ||||
| 1439 | /// Set a given bit to 1. | |||
| 1440 | /// | |||
| 1441 | /// Set the given bit to 1 whose position is given as "bitPosition". | |||
| 1442 | void setBit(unsigned BitPosition) { | |||
| 1443 | assert(BitPosition < BitWidth && "BitPosition out of range")((void)0); | |||
| 1444 | WordType Mask = maskBit(BitPosition); | |||
| 1445 | if (isSingleWord()) | |||
| 1446 | U.VAL |= Mask; | |||
| 1447 | else | |||
| 1448 | U.pVal[whichWord(BitPosition)] |= Mask; | |||
| 1449 | } | |||
| 1450 | ||||
| 1451 | /// Set the sign bit to 1. | |||
| 1452 | void setSignBit() { | |||
| 1453 | setBit(BitWidth - 1); | |||
| 1454 | } | |||
| 1455 | ||||
| 1456 | /// Set a given bit to a given value. | |||
| 1457 | void setBitVal(unsigned BitPosition, bool BitValue) { | |||
| 1458 | if (BitValue) | |||
| 1459 | setBit(BitPosition); | |||
| 1460 | else | |||
| 1461 | clearBit(BitPosition); | |||
| 1462 | } | |||
| 1463 | ||||
| 1464 | /// Set the bits from loBit (inclusive) to hiBit (exclusive) to 1. | |||
| 1465 | /// This function handles "wrap" case when \p loBit >= \p hiBit, and calls | |||
| 1466 | /// setBits when \p loBit < \p hiBit. | |||
| 1467 | /// For \p loBit == \p hiBit wrap case, set every bit to 1. | |||
| 1468 | void setBitsWithWrap(unsigned loBit, unsigned hiBit) { | |||
| 1469 | assert(hiBit <= BitWidth && "hiBit out of range")((void)0); | |||
| 1470 | assert(loBit <= BitWidth && "loBit out of range")((void)0); | |||
| 1471 | if (loBit < hiBit) { | |||
| 1472 | setBits(loBit, hiBit); | |||
| 1473 | return; | |||
| 1474 | } | |||
| 1475 | setLowBits(hiBit); | |||
| 1476 | setHighBits(BitWidth - loBit); | |||
| 1477 | } | |||
| 1478 | ||||
| 1479 | /// Set the bits from loBit (inclusive) to hiBit (exclusive) to 1. | |||
| 1480 | /// This function handles case when \p loBit <= \p hiBit. | |||
| 1481 | void setBits(unsigned loBit, unsigned hiBit) { | |||
| 1482 | assert(hiBit <= BitWidth && "hiBit out of range")((void)0); | |||
| 1483 | assert(loBit <= BitWidth && "loBit out of range")((void)0); | |||
| 1484 | assert(loBit <= hiBit && "loBit greater than hiBit")((void)0); | |||
| 1485 | if (loBit == hiBit) | |||
| 1486 | return; | |||
| 1487 | if (loBit < APINT_BITS_PER_WORD && hiBit <= APINT_BITS_PER_WORD) { | |||
| 1488 | uint64_t mask = WORDTYPE_MAX >> (APINT_BITS_PER_WORD - (hiBit - loBit)); | |||
| 1489 | mask <<= loBit; | |||
| 1490 | if (isSingleWord()) | |||
| 1491 | U.VAL |= mask; | |||
| 1492 | else | |||
| 1493 | U.pVal[0] |= mask; | |||
| 1494 | } else { | |||
| 1495 | setBitsSlowCase(loBit, hiBit); | |||
| 1496 | } | |||
| 1497 | } | |||
| 1498 | ||||
| 1499 | /// Set the top bits starting from loBit. | |||
| 1500 | void setBitsFrom(unsigned loBit) { | |||
| 1501 | return setBits(loBit, BitWidth); | |||
| 1502 | } | |||
| 1503 | ||||
| 1504 | /// Set the bottom loBits bits. | |||
| 1505 | void setLowBits(unsigned loBits) { | |||
| 1506 | return setBits(0, loBits); | |||
| 1507 | } | |||
| 1508 | ||||
| 1509 | /// Set the top hiBits bits. | |||
| 1510 | void setHighBits(unsigned hiBits) { | |||
| 1511 | return setBits(BitWidth - hiBits, BitWidth); | |||
| 1512 | } | |||
| 1513 | ||||
| 1514 | /// Set every bit to 0. | |||
| 1515 | void clearAllBits() { | |||
| 1516 | if (isSingleWord()) | |||
| 1517 | U.VAL = 0; | |||
| 1518 | else | |||
| 1519 | memset(U.pVal, 0, getNumWords() * APINT_WORD_SIZE); | |||
| 1520 | } | |||
| 1521 | ||||
| 1522 | /// Set a given bit to 0. | |||
| 1523 | /// | |||
| 1524 | /// Set the given bit to 0 whose position is given as "bitPosition". | |||
| 1525 | void clearBit(unsigned BitPosition) { | |||
| 1526 | assert(BitPosition < BitWidth && "BitPosition out of range")((void)0); | |||
| 1527 | WordType Mask = ~maskBit(BitPosition); | |||
| 1528 | if (isSingleWord()) | |||
| 1529 | U.VAL &= Mask; | |||
| 1530 | else | |||
| 1531 | U.pVal[whichWord(BitPosition)] &= Mask; | |||
| 1532 | } | |||
| 1533 | ||||
| 1534 | /// Set bottom loBits bits to 0. | |||
| 1535 | void clearLowBits(unsigned loBits) { | |||
| 1536 | assert(loBits <= BitWidth && "More bits than bitwidth")((void)0); | |||
| 1537 | APInt Keep = getHighBitsSet(BitWidth, BitWidth - loBits); | |||
| 1538 | *this &= Keep; | |||
| 1539 | } | |||
| 1540 | ||||
| 1541 | /// Set the sign bit to 0. | |||
| 1542 | void clearSignBit() { | |||
| 1543 | clearBit(BitWidth - 1); | |||
| 1544 | } | |||
| 1545 | ||||
| 1546 | /// Toggle every bit to its opposite value. | |||
| 1547 | void flipAllBits() { | |||
| 1548 | if (isSingleWord()) { | |||
| 1549 | U.VAL ^= WORDTYPE_MAX; | |||
| 1550 | clearUnusedBits(); | |||
| 1551 | } else { | |||
| 1552 | flipAllBitsSlowCase(); | |||
| 1553 | } | |||
| 1554 | } | |||
| 1555 | ||||
| 1556 | /// Toggles a given bit to its opposite value. | |||
| 1557 | /// | |||
| 1558 | /// Toggle a given bit to its opposite value whose position is given | |||
| 1559 | /// as "bitPosition". | |||
| 1560 | void flipBit(unsigned bitPosition); | |||
| 1561 | ||||
| 1562 | /// Negate this APInt in place. | |||
| 1563 | void negate() { | |||
| 1564 | flipAllBits(); | |||
| 1565 | ++(*this); | |||
| 1566 | } | |||
| 1567 | ||||
| 1568 | /// Insert the bits from a smaller APInt starting at bitPosition. | |||
| 1569 | void insertBits(const APInt &SubBits, unsigned bitPosition); | |||
| 1570 | void insertBits(uint64_t SubBits, unsigned bitPosition, unsigned numBits); | |||
| 1571 | ||||
| 1572 | /// Return an APInt with the extracted bits [bitPosition,bitPosition+numBits). | |||
| 1573 | APInt extractBits(unsigned numBits, unsigned bitPosition) const; | |||
| 1574 | uint64_t extractBitsAsZExtValue(unsigned numBits, unsigned bitPosition) const; | |||
| 1575 | ||||
| 1576 | /// @} | |||
| 1577 | /// \name Value Characterization Functions | |||
| 1578 | /// @{ | |||
| 1579 | ||||
| 1580 | /// Return the number of bits in the APInt. | |||
| 1581 | unsigned getBitWidth() const { return BitWidth; } | |||
| 1582 | ||||
| 1583 | /// Get the number of words. | |||
| 1584 | /// | |||
| 1585 | /// Here one word's bitwidth equals to that of uint64_t. | |||
| 1586 | /// | |||
| 1587 | /// \returns the number of words to hold the integer value of this APInt. | |||
| 1588 | unsigned getNumWords() const { return getNumWords(BitWidth); } | |||
| 1589 | ||||
| 1590 | /// Get the number of words. | |||
| 1591 | /// | |||
| 1592 | /// *NOTE* Here one word's bitwidth equals to that of uint64_t. | |||
| 1593 | /// | |||
| 1594 | /// \returns the number of words to hold the integer value with a given bit | |||
| 1595 | /// width. | |||
| 1596 | static unsigned getNumWords(unsigned BitWidth) { | |||
| 1597 | return ((uint64_t)BitWidth + APINT_BITS_PER_WORD - 1) / APINT_BITS_PER_WORD; | |||
| 1598 | } | |||
| 1599 | ||||
| 1600 | /// Compute the number of active bits in the value | |||
| 1601 | /// | |||
| 1602 | /// This function returns the number of active bits which is defined as the | |||
| 1603 | /// bit width minus the number of leading zeros. This is used in several | |||
| 1604 | /// computations to see how "wide" the value is. | |||
| 1605 | unsigned getActiveBits() const { return BitWidth - countLeadingZeros(); } | |||
| 1606 | ||||
| 1607 | /// Compute the number of active words in the value of this APInt. | |||
| 1608 | /// | |||
| 1609 | /// This is used in conjunction with getActiveData to extract the raw value of | |||
| 1610 | /// the APInt. | |||
| 1611 | unsigned getActiveWords() const { | |||
| 1612 | unsigned numActiveBits = getActiveBits(); | |||
| 1613 | return numActiveBits ? whichWord(numActiveBits - 1) + 1 : 1; | |||
| 1614 | } | |||
| 1615 | ||||
| 1616 | /// Get the minimum bit size for this signed APInt | |||
| 1617 | /// | |||
| 1618 | /// Computes the minimum bit width for this APInt while considering it to be a | |||
| 1619 | /// signed (and probably negative) value. If the value is not negative, this | |||
| 1620 | /// function returns the same value as getActiveBits()+1. Otherwise, it | |||
| 1621 | /// returns the smallest bit width that will retain the negative value. For | |||
| 1622 | /// example, -1 can be written as 0b1 or 0xFFFFFFFFFF. 0b1 is shorter and so | |||
| 1623 | /// for -1, this function will always return 1. | |||
| 1624 | unsigned getMinSignedBits() const { return BitWidth - getNumSignBits() + 1; } | |||
| 1625 | ||||
| 1626 | /// Get zero extended value | |||
| 1627 | /// | |||
| 1628 | /// This method attempts to return the value of this APInt as a zero extended | |||
| 1629 | /// uint64_t. The bitwidth must be <= 64 or the value must fit within a | |||
| 1630 | /// uint64_t. Otherwise an assertion will result. | |||
| 1631 | uint64_t getZExtValue() const { | |||
| 1632 | if (isSingleWord()) | |||
| 1633 | return U.VAL; | |||
| 1634 | assert(getActiveBits() <= 64 && "Too many bits for uint64_t")((void)0); | |||
| 1635 | return U.pVal[0]; | |||
| 1636 | } | |||
| 1637 | ||||
| 1638 | /// Get sign extended value | |||
| 1639 | /// | |||
| 1640 | /// This method attempts to return the value of this APInt as a sign extended | |||
| 1641 | /// int64_t. The bit width must be <= 64 or the value must fit within an | |||
| 1642 | /// int64_t. Otherwise an assertion will result. | |||
| 1643 | int64_t getSExtValue() const { | |||
| 1644 | if (isSingleWord()) | |||
| 1645 | return SignExtend64(U.VAL, BitWidth); | |||
| 1646 | assert(getMinSignedBits() <= 64 && "Too many bits for int64_t")((void)0); | |||
| 1647 | return int64_t(U.pVal[0]); | |||
| 1648 | } | |||
| 1649 | ||||
| 1650 | /// Get bits required for string value. | |||
| 1651 | /// | |||
| 1652 | /// This method determines how many bits are required to hold the APInt | |||
| 1653 | /// equivalent of the string given by \p str. | |||
| 1654 | static unsigned getBitsNeeded(StringRef str, uint8_t radix); | |||
| 1655 | ||||
| 1656 | /// The APInt version of the countLeadingZeros functions in | |||
| 1657 | /// MathExtras.h. | |||
| 1658 | /// | |||
| 1659 | /// It counts the number of zeros from the most significant bit to the first | |||
| 1660 | /// one bit. | |||
| 1661 | /// | |||
| 1662 | /// \returns BitWidth if the value is zero, otherwise returns the number of | |||
| 1663 | /// zeros from the most significant bit to the first one bits. | |||
| 1664 | unsigned countLeadingZeros() const { | |||
| 1665 | if (isSingleWord()) { | |||
| 1666 | unsigned unusedBits = APINT_BITS_PER_WORD - BitWidth; | |||
| 1667 | return llvm::countLeadingZeros(U.VAL) - unusedBits; | |||
| 1668 | } | |||
| 1669 | return countLeadingZerosSlowCase(); | |||
| 1670 | } | |||
| 1671 | ||||
| 1672 | /// Count the number of leading one bits. | |||
| 1673 | /// | |||
| 1674 | /// This function is an APInt version of the countLeadingOnes | |||
| 1675 | /// functions in MathExtras.h. It counts the number of ones from the most | |||
| 1676 | /// significant bit to the first zero bit. | |||
| 1677 | /// | |||
| 1678 | /// \returns 0 if the high order bit is not set, otherwise returns the number | |||
| 1679 | /// of 1 bits from the most significant to the least | |||
| 1680 | unsigned countLeadingOnes() const { | |||
| 1681 | if (isSingleWord()) | |||
| 1682 | return llvm::countLeadingOnes(U.VAL << (APINT_BITS_PER_WORD - BitWidth)); | |||
| 1683 | return countLeadingOnesSlowCase(); | |||
| 1684 | } | |||
| 1685 | ||||
| 1686 | /// Computes the number of leading bits of this APInt that are equal to its | |||
| 1687 | /// sign bit. | |||
| 1688 | unsigned getNumSignBits() const { | |||
| 1689 | return isNegative() ? countLeadingOnes() : countLeadingZeros(); | |||
| 1690 | } | |||
| 1691 | ||||
| 1692 | /// Count the number of trailing zero bits. | |||
| 1693 | /// | |||
| 1694 | /// This function is an APInt version of the countTrailingZeros | |||
| 1695 | /// functions in MathExtras.h. It counts the number of zeros from the least | |||
| 1696 | /// significant bit to the first set bit. | |||
| 1697 | /// | |||
| 1698 | /// \returns BitWidth if the value is zero, otherwise returns the number of | |||
| 1699 | /// zeros from the least significant bit to the first one bit. | |||
| 1700 | unsigned countTrailingZeros() const { | |||
| 1701 | if (isSingleWord()) { | |||
| 1702 | unsigned TrailingZeros = llvm::countTrailingZeros(U.VAL); | |||
| 1703 | return (TrailingZeros > BitWidth ? BitWidth : TrailingZeros); | |||
| 1704 | } | |||
| 1705 | return countTrailingZerosSlowCase(); | |||
| 1706 | } | |||
| 1707 | ||||
| 1708 | /// Count the number of trailing one bits. | |||
| 1709 | /// | |||
| 1710 | /// This function is an APInt version of the countTrailingOnes | |||
| 1711 | /// functions in MathExtras.h. It counts the number of ones from the least | |||
| 1712 | /// significant bit to the first zero bit. | |||
| 1713 | /// | |||
| 1714 | /// \returns BitWidth if the value is all ones, otherwise returns the number | |||
| 1715 | /// of ones from the least significant bit to the first zero bit. | |||
| 1716 | unsigned countTrailingOnes() const { | |||
| 1717 | if (isSingleWord()) | |||
| 1718 | return llvm::countTrailingOnes(U.VAL); | |||
| 1719 | return countTrailingOnesSlowCase(); | |||
| 1720 | } | |||
| 1721 | ||||
| 1722 | /// Count the number of bits set. | |||
| 1723 | /// | |||
| 1724 | /// This function is an APInt version of the countPopulation functions | |||
| 1725 | /// in MathExtras.h. It counts the number of 1 bits in the APInt value. | |||
| 1726 | /// | |||
| 1727 | /// \returns 0 if the value is zero, otherwise returns the number of set bits. | |||
| 1728 | unsigned countPopulation() const { | |||
| 1729 | if (isSingleWord()) | |||
| 1730 | return llvm::countPopulation(U.VAL); | |||
| 1731 | return countPopulationSlowCase(); | |||
| 1732 | } | |||
| 1733 | ||||
| 1734 | /// @} | |||
| 1735 | /// \name Conversion Functions | |||
| 1736 | /// @{ | |||
| 1737 | void print(raw_ostream &OS, bool isSigned) const; | |||
| 1738 | ||||
| 1739 | /// Converts an APInt to a string and append it to Str. Str is commonly a | |||
| 1740 | /// SmallString. | |||
| 1741 | void toString(SmallVectorImpl<char> &Str, unsigned Radix, bool Signed, | |||
| 1742 | bool formatAsCLiteral = false) const; | |||
| 1743 | ||||
| 1744 | /// Considers the APInt to be unsigned and converts it into a string in the | |||
| 1745 | /// radix given. The radix can be 2, 8, 10 16, or 36. | |||
| 1746 | void toStringUnsigned(SmallVectorImpl<char> &Str, unsigned Radix = 10) const { | |||
| 1747 | toString(Str, Radix, false, false); | |||
| 1748 | } | |||
| 1749 | ||||
| 1750 | /// Considers the APInt to be signed and converts it into a string in the | |||
| 1751 | /// radix given. The radix can be 2, 8, 10, 16, or 36. | |||
| 1752 | void toStringSigned(SmallVectorImpl<char> &Str, unsigned Radix = 10) const { | |||
| 1753 | toString(Str, Radix, true, false); | |||
| 1754 | } | |||
| 1755 | ||||
| 1756 | /// \returns a byte-swapped representation of this APInt Value. | |||
| 1757 | APInt byteSwap() const; | |||
| 1758 | ||||
| 1759 | /// \returns the value with the bit representation reversed of this APInt | |||
| 1760 | /// Value. | |||
| 1761 | APInt reverseBits() const; | |||
| 1762 | ||||
| 1763 | /// Converts this APInt to a double value. | |||
| 1764 | double roundToDouble(bool isSigned) const; | |||
| 1765 | ||||
| 1766 | /// Converts this unsigned APInt to a double value. | |||
| 1767 | double roundToDouble() const { return roundToDouble(false); } | |||
| 1768 | ||||
| 1769 | /// Converts this signed APInt to a double value. | |||
| 1770 | double signedRoundToDouble() const { return roundToDouble(true); } | |||
| 1771 | ||||
| 1772 | /// Converts APInt bits to a double | |||
| 1773 | /// | |||
| 1774 | /// The conversion does not do a translation from integer to double, it just | |||
| 1775 | /// re-interprets the bits as a double. Note that it is valid to do this on | |||
| 1776 | /// any bit width. Exactly 64 bits will be translated. | |||
| 1777 | double bitsToDouble() const { | |||
| 1778 | return BitsToDouble(getWord(0)); | |||
| 1779 | } | |||
| 1780 | ||||
| 1781 | /// Converts APInt bits to a float | |||
| 1782 | /// | |||
| 1783 | /// The conversion does not do a translation from integer to float, it just | |||
| 1784 | /// re-interprets the bits as a float. Note that it is valid to do this on | |||
| 1785 | /// any bit width. Exactly 32 bits will be translated. | |||
| 1786 | float bitsToFloat() const { | |||
| 1787 | return BitsToFloat(static_cast<uint32_t>(getWord(0))); | |||
| 1788 | } | |||
| 1789 | ||||
| 1790 | /// Converts a double to APInt bits. | |||
| 1791 | /// | |||
| 1792 | /// The conversion does not do a translation from double to integer, it just | |||
| 1793 | /// re-interprets the bits of the double. | |||
| 1794 | static APInt doubleToBits(double V) { | |||
| 1795 | return APInt(sizeof(double) * CHAR_BIT8, DoubleToBits(V)); | |||
| 1796 | } | |||
| 1797 | ||||
| 1798 | /// Converts a float to APInt bits. | |||
| 1799 | /// | |||
| 1800 | /// The conversion does not do a translation from float to integer, it just | |||
| 1801 | /// re-interprets the bits of the float. | |||
| 1802 | static APInt floatToBits(float V) { | |||
| 1803 | return APInt(sizeof(float) * CHAR_BIT8, FloatToBits(V)); | |||
| 1804 | } | |||
| 1805 | ||||
| 1806 | /// @} | |||
| 1807 | /// \name Mathematics Operations | |||
| 1808 | /// @{ | |||
| 1809 | ||||
| 1810 | /// \returns the floor log base 2 of this APInt. | |||
| 1811 | unsigned logBase2() const { return getActiveBits() - 1; } | |||
| 1812 | ||||
| 1813 | /// \returns the ceil log base 2 of this APInt. | |||
| 1814 | unsigned ceilLogBase2() const { | |||
| 1815 | APInt temp(*this); | |||
| 1816 | --temp; | |||
| 1817 | return temp.getActiveBits(); | |||
| 1818 | } | |||
| 1819 | ||||
| 1820 | /// \returns the nearest log base 2 of this APInt. Ties round up. | |||
| 1821 | /// | |||
| 1822 | /// NOTE: When we have a BitWidth of 1, we define: | |||
| 1823 | /// | |||
| 1824 | /// log2(0) = UINT32_MAX | |||
| 1825 | /// log2(1) = 0 | |||
| 1826 | /// | |||
| 1827 | /// to get around any mathematical concerns resulting from | |||
| 1828 | /// referencing 2 in a space where 2 does no exist. | |||
| 1829 | unsigned nearestLogBase2() const { | |||
| 1830 | // Special case when we have a bitwidth of 1. If VAL is 1, then we | |||
| 1831 | // get 0. If VAL is 0, we get WORDTYPE_MAX which gets truncated to | |||
| 1832 | // UINT32_MAX. | |||
| 1833 | if (BitWidth == 1) | |||
| 1834 | return U.VAL - 1; | |||
| 1835 | ||||
| 1836 | // Handle the zero case. | |||
| 1837 | if (isNullValue()) | |||
| 1838 | return UINT32_MAX0xffffffffU; | |||
| 1839 | ||||
| 1840 | // The non-zero case is handled by computing: | |||
| 1841 | // | |||
| 1842 | // nearestLogBase2(x) = logBase2(x) + x[logBase2(x)-1]. | |||
| 1843 | // | |||
| 1844 | // where x[i] is referring to the value of the ith bit of x. | |||
| 1845 | unsigned lg = logBase2(); | |||
| 1846 | return lg + unsigned((*this)[lg - 1]); | |||
| 1847 | } | |||
| 1848 | ||||
| 1849 | /// \returns the log base 2 of this APInt if its an exact power of two, -1 | |||
| 1850 | /// otherwise | |||
| 1851 | int32_t exactLogBase2() const { | |||
| 1852 | if (!isPowerOf2()) | |||
| 1853 | return -1; | |||
| 1854 | return logBase2(); | |||
| 1855 | } | |||
| 1856 | ||||
| 1857 | /// Compute the square root | |||
| 1858 | APInt sqrt() const; | |||
| 1859 | ||||
| 1860 | /// Get the absolute value; | |||
| 1861 | /// | |||
| 1862 | /// If *this is < 0 then return -(*this), otherwise *this; | |||
| 1863 | APInt abs() const { | |||
| 1864 | if (isNegative()) | |||
| 1865 | return -(*this); | |||
| 1866 | return *this; | |||
| 1867 | } | |||
| 1868 | ||||
| 1869 | /// \returns the multiplicative inverse for a given modulo. | |||
| 1870 | APInt multiplicativeInverse(const APInt &modulo) const; | |||
| 1871 | ||||
| 1872 | /// @} | |||
| 1873 | /// \name Support for division by constant | |||
| 1874 | /// @{ | |||
| 1875 | ||||
| 1876 | /// Calculate the magic number for signed division by a constant. | |||
| 1877 | struct ms; | |||
| 1878 | ms magic() const; | |||
| 1879 | ||||
| 1880 | /// Calculate the magic number for unsigned division by a constant. | |||
| 1881 | struct mu; | |||
| 1882 | mu magicu(unsigned LeadingZeros = 0) const; | |||
| 1883 | ||||
| 1884 | /// @} | |||
| 1885 | /// \name Building-block Operations for APInt and APFloat | |||
| 1886 | /// @{ | |||
| 1887 | ||||
| 1888 | // These building block operations operate on a representation of arbitrary | |||
| 1889 | // precision, two's-complement, bignum integer values. They should be | |||
| 1890 | // sufficient to implement APInt and APFloat bignum requirements. Inputs are | |||
| 1891 | // generally a pointer to the base of an array of integer parts, representing | |||
| 1892 | // an unsigned bignum, and a count of how many parts there are. | |||
| 1893 | ||||
| 1894 | /// Sets the least significant part of a bignum to the input value, and zeroes | |||
| 1895 | /// out higher parts. | |||
| 1896 | static void tcSet(WordType *, WordType, unsigned); | |||
| 1897 | ||||
| 1898 | /// Assign one bignum to another. | |||
| 1899 | static void tcAssign(WordType *, const WordType *, unsigned); | |||
| 1900 | ||||
| 1901 | /// Returns true if a bignum is zero, false otherwise. | |||
| 1902 | static bool tcIsZero(const WordType *, unsigned); | |||
| 1903 | ||||
| 1904 | /// Extract the given bit of a bignum; returns 0 or 1. Zero-based. | |||
| 1905 | static int tcExtractBit(const WordType *, unsigned bit); | |||
| 1906 | ||||
| 1907 | /// Copy the bit vector of width srcBITS from SRC, starting at bit srcLSB, to | |||
| 1908 | /// DST, of dstCOUNT parts, such that the bit srcLSB becomes the least | |||
| 1909 | /// significant bit of DST. All high bits above srcBITS in DST are | |||
| 1910 | /// zero-filled. | |||
| 1911 | static void tcExtract(WordType *, unsigned dstCount, | |||
| 1912 | const WordType *, unsigned srcBits, | |||
| 1913 | unsigned srcLSB); | |||
| 1914 | ||||
| 1915 | /// Set the given bit of a bignum. Zero-based. | |||
| 1916 | static void tcSetBit(WordType *, unsigned bit); | |||
| 1917 | ||||
| 1918 | /// Clear the given bit of a bignum. Zero-based. | |||
| 1919 | static void tcClearBit(WordType *, unsigned bit); | |||
| 1920 | ||||
| 1921 | /// Returns the bit number of the least or most significant set bit of a | |||
| 1922 | /// number. If the input number has no bits set -1U is returned. | |||
| 1923 | static unsigned tcLSB(const WordType *, unsigned n); | |||
| 1924 | static unsigned tcMSB(const WordType *parts, unsigned n); | |||
| 1925 | ||||
| 1926 | /// Negate a bignum in-place. | |||
| 1927 | static void tcNegate(WordType *, unsigned); | |||
| 1928 | ||||
| 1929 | /// DST += RHS + CARRY where CARRY is zero or one. Returns the carry flag. | |||
| 1930 | static WordType tcAdd(WordType *, const WordType *, | |||
| 1931 | WordType carry, unsigned); | |||
| 1932 | /// DST += RHS. Returns the carry flag. | |||
| 1933 | static WordType tcAddPart(WordType *, WordType, unsigned); | |||
| 1934 | ||||
| 1935 | /// DST -= RHS + CARRY where CARRY is zero or one. Returns the carry flag. | |||
| 1936 | static WordType tcSubtract(WordType *, const WordType *, | |||
| 1937 | WordType carry, unsigned); | |||
| 1938 | /// DST -= RHS. Returns the carry flag. | |||
| 1939 | static WordType tcSubtractPart(WordType *, WordType, unsigned); | |||
| 1940 | ||||
| 1941 | /// DST += SRC * MULTIPLIER + PART if add is true | |||
| 1942 | /// DST = SRC * MULTIPLIER + PART if add is false | |||
| 1943 | /// | |||
| 1944 | /// Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC they must | |||
| 1945 | /// start at the same point, i.e. DST == SRC. | |||
| 1946 | /// | |||
| 1947 | /// If DSTPARTS == SRC_PARTS + 1 no overflow occurs and zero is returned. | |||
| 1948 | /// Otherwise DST is filled with the least significant DSTPARTS parts of the | |||
| 1949 | /// result, and if all of the omitted higher parts were zero return zero, | |||
| 1950 | /// otherwise overflow occurred and return one. | |||
| 1951 | static int tcMultiplyPart(WordType *dst, const WordType *src, | |||
| 1952 | WordType multiplier, WordType carry, | |||
| 1953 | unsigned srcParts, unsigned dstParts, | |||
| 1954 | bool add); | |||
| 1955 | ||||
| 1956 | /// DST = LHS * RHS, where DST has the same width as the operands and is | |||
| 1957 | /// filled with the least significant parts of the result. Returns one if | |||
| 1958 | /// overflow occurred, otherwise zero. DST must be disjoint from both | |||
| 1959 | /// operands. | |||
| 1960 | static int tcMultiply(WordType *, const WordType *, const WordType *, | |||
| 1961 | unsigned); | |||
| 1962 | ||||
| 1963 | /// DST = LHS * RHS, where DST has width the sum of the widths of the | |||
| 1964 | /// operands. No overflow occurs. DST must be disjoint from both operands. | |||
| 1965 | static void tcFullMultiply(WordType *, const WordType *, | |||
| 1966 | const WordType *, unsigned, unsigned); | |||
| 1967 | ||||
| 1968 | /// If RHS is zero LHS and REMAINDER are left unchanged, return one. | |||
| 1969 | /// Otherwise set LHS to LHS / RHS with the fractional part discarded, set | |||
| 1970 | /// REMAINDER to the remainder, return zero. i.e. | |||
| 1971 | /// | |||
| 1972 | /// OLD_LHS = RHS * LHS + REMAINDER | |||
| 1973 | /// | |||
| 1974 | /// SCRATCH is a bignum of the same size as the operands and result for use by | |||
| 1975 | /// the routine; its contents need not be initialized and are destroyed. LHS, | |||
| 1976 | /// REMAINDER and SCRATCH must be distinct. | |||
| 1977 | static int tcDivide(WordType *lhs, const WordType *rhs, | |||
| 1978 | WordType *remainder, WordType *scratch, | |||
| 1979 | unsigned parts); | |||
| 1980 | ||||
| 1981 | /// Shift a bignum left Count bits. Shifted in bits are zero. There are no | |||
| 1982 | /// restrictions on Count. | |||
| 1983 | static void tcShiftLeft(WordType *, unsigned Words, unsigned Count); | |||
| 1984 | ||||
| 1985 | /// Shift a bignum right Count bits. Shifted in bits are zero. There are no | |||
| 1986 | /// restrictions on Count. | |||
| 1987 | static void tcShiftRight(WordType *, unsigned Words, unsigned Count); | |||
| 1988 | ||||
| 1989 | /// The obvious AND, OR and XOR and complement operations. | |||
| 1990 | static void tcAnd(WordType *, const WordType *, unsigned); | |||
| 1991 | static void tcOr(WordType *, const WordType *, unsigned); | |||
| 1992 | static void tcXor(WordType *, const WordType *, unsigned); | |||
| 1993 | static void tcComplement(WordType *, unsigned); | |||
| 1994 | ||||
| 1995 | /// Comparison (unsigned) of two bignums. | |||
| 1996 | static int tcCompare(const WordType *, const WordType *, unsigned); | |||
| 1997 | ||||
| 1998 | /// Increment a bignum in-place. Return the carry flag. | |||
| 1999 | static WordType tcIncrement(WordType *dst, unsigned parts) { | |||
| 2000 | return tcAddPart(dst, 1, parts); | |||
| 2001 | } | |||
| 2002 | ||||
| 2003 | /// Decrement a bignum in-place. Return the borrow flag. | |||
| 2004 | static WordType tcDecrement(WordType *dst, unsigned parts) { | |||
| 2005 | return tcSubtractPart(dst, 1, parts); | |||
| 2006 | } | |||
| 2007 | ||||
| 2008 | /// Set the least significant BITS and clear the rest. | |||
| 2009 | static void tcSetLeastSignificantBits(WordType *, unsigned, unsigned bits); | |||
| 2010 | ||||
| 2011 | /// debug method | |||
| 2012 | void dump() const; | |||
| 2013 | ||||
| 2014 | /// @} | |||
| 2015 | }; | |||
| 2016 | ||||
| 2017 | /// Magic data for optimising signed division by a constant. | |||
| 2018 | struct APInt::ms { | |||
| 2019 | APInt m; ///< magic number | |||
| 2020 | unsigned s; ///< shift amount | |||
| 2021 | }; | |||
| 2022 | ||||
| 2023 | /// Magic data for optimising unsigned division by a constant. | |||
| 2024 | struct APInt::mu { | |||
| 2025 | APInt m; ///< magic number | |||
| 2026 | bool a; ///< add indicator | |||
| 2027 | unsigned s; ///< shift amount | |||
| 2028 | }; | |||
| 2029 | ||||
| 2030 | inline bool operator==(uint64_t V1, const APInt &V2) { return V2 == V1; } | |||
| 2031 | ||||
| 2032 | inline bool operator!=(uint64_t V1, const APInt &V2) { return V2 != V1; } | |||
| 2033 | ||||
| 2034 | /// Unary bitwise complement operator. | |||
| 2035 | /// | |||
| 2036 | /// \returns an APInt that is the bitwise complement of \p v. | |||
| 2037 | inline APInt operator~(APInt v) { | |||
| 2038 | v.flipAllBits(); | |||
| 2039 | return v; | |||
| 2040 | } | |||
| 2041 | ||||
| 2042 | inline APInt operator&(APInt a, const APInt &b) { | |||
| 2043 | a &= b; | |||
| 2044 | return a; | |||
| 2045 | } | |||
| 2046 | ||||
| 2047 | inline APInt operator&(const APInt &a, APInt &&b) { | |||
| 2048 | b &= a; | |||
| 2049 | return std::move(b); | |||
| 2050 | } | |||
| 2051 | ||||
| 2052 | inline APInt operator&(APInt a, uint64_t RHS) { | |||
| 2053 | a &= RHS; | |||
| 2054 | return a; | |||
| 2055 | } | |||
| 2056 | ||||
| 2057 | inline APInt operator&(uint64_t LHS, APInt b) { | |||
| 2058 | b &= LHS; | |||
| 2059 | return b; | |||
| 2060 | } | |||
| 2061 | ||||
| 2062 | inline APInt operator|(APInt a, const APInt &b) { | |||
| 2063 | a |= b; | |||
| 2064 | return a; | |||
| 2065 | } | |||
| 2066 | ||||
| 2067 | inline APInt operator|(const APInt &a, APInt &&b) { | |||
| 2068 | b |= a; | |||
| 2069 | return std::move(b); | |||
| 2070 | } | |||
| 2071 | ||||
| 2072 | inline APInt operator|(APInt a, uint64_t RHS) { | |||
| 2073 | a |= RHS; | |||
| 2074 | return a; | |||
| 2075 | } | |||
| 2076 | ||||
| 2077 | inline APInt operator|(uint64_t LHS, APInt b) { | |||
| 2078 | b |= LHS; | |||
| 2079 | return b; | |||
| 2080 | } | |||
| 2081 | ||||
| 2082 | inline APInt operator^(APInt a, const APInt &b) { | |||
| 2083 | a ^= b; | |||
| 2084 | return a; | |||
| 2085 | } | |||
| 2086 | ||||
| 2087 | inline APInt operator^(const APInt &a, APInt &&b) { | |||
| 2088 | b ^= a; | |||
| 2089 | return std::move(b); | |||
| 2090 | } | |||
| 2091 | ||||
| 2092 | inline APInt operator^(APInt a, uint64_t RHS) { | |||
| 2093 | a ^= RHS; | |||
| 2094 | return a; | |||
| 2095 | } | |||
| 2096 | ||||
| 2097 | inline APInt operator^(uint64_t LHS, APInt b) { | |||
| 2098 | b ^= LHS; | |||
| 2099 | return b; | |||
| 2100 | } | |||
| 2101 | ||||
| 2102 | inline raw_ostream &operator<<(raw_ostream &OS, const APInt &I) { | |||
| 2103 | I.print(OS, true); | |||
| 2104 | return OS; | |||
| 2105 | } | |||
| 2106 | ||||
| 2107 | inline APInt operator-(APInt v) { | |||
| 2108 | v.negate(); | |||
| 2109 | return v; | |||
| 2110 | } | |||
| 2111 | ||||
| 2112 | inline APInt operator+(APInt a, const APInt &b) { | |||
| 2113 | a += b; | |||
| 2114 | return a; | |||
| 2115 | } | |||
| 2116 | ||||
| 2117 | inline APInt operator+(const APInt &a, APInt &&b) { | |||
| 2118 | b += a; | |||
| 2119 | return std::move(b); | |||
| 2120 | } | |||
| 2121 | ||||
| 2122 | inline APInt operator+(APInt a, uint64_t RHS) { | |||
| 2123 | a += RHS; | |||
| 2124 | return a; | |||
| 2125 | } | |||
| 2126 | ||||
| 2127 | inline APInt operator+(uint64_t LHS, APInt b) { | |||
| 2128 | b += LHS; | |||
| 2129 | return b; | |||
| 2130 | } | |||
| 2131 | ||||
| 2132 | inline APInt operator-(APInt a, const APInt &b) { | |||
| 2133 | a -= b; | |||
| 2134 | return a; | |||
| 2135 | } | |||
| 2136 | ||||
| 2137 | inline APInt operator-(const APInt &a, APInt &&b) { | |||
| 2138 | b.negate(); | |||
| 2139 | b += a; | |||
| 2140 | return std::move(b); | |||
| 2141 | } | |||
| 2142 | ||||
| 2143 | inline APInt operator-(APInt a, uint64_t RHS) { | |||
| 2144 | a -= RHS; | |||
| 2145 | return a; | |||
| 2146 | } | |||
| 2147 | ||||
| 2148 | inline APInt operator-(uint64_t LHS, APInt b) { | |||
| 2149 | b.negate(); | |||
| 2150 | b += LHS; | |||
| 2151 | return b; | |||
| 2152 | } | |||
| 2153 | ||||
| 2154 | inline APInt operator*(APInt a, uint64_t RHS) { | |||
| 2155 | a *= RHS; | |||
| 2156 | return a; | |||
| 2157 | } | |||
| 2158 | ||||
| 2159 | inline APInt operator*(uint64_t LHS, APInt b) { | |||
| 2160 | b *= LHS; | |||
| 2161 | return b; | |||
| 2162 | } | |||
| 2163 | ||||
| 2164 | ||||
| 2165 | namespace APIntOps { | |||
| 2166 | ||||
| 2167 | /// Determine the smaller of two APInts considered to be signed. | |||
| 2168 | inline const APInt &smin(const APInt &A, const APInt &B) { | |||
| 2169 | return A.slt(B) ? A : B; | |||
| 2170 | } | |||
| 2171 | ||||
| 2172 | /// Determine the larger of two APInts considered to be signed. | |||
| 2173 | inline const APInt &smax(const APInt &A, const APInt &B) { | |||
| 2174 | return A.sgt(B) ? A : B; | |||
| 2175 | } | |||
| 2176 | ||||
| 2177 | /// Determine the smaller of two APInts considered to be unsigned. | |||
| 2178 | inline const APInt &umin(const APInt &A, const APInt &B) { | |||
| 2179 | return A.ult(B) ? A : B; | |||
| 2180 | } | |||
| 2181 | ||||
| 2182 | /// Determine the larger of two APInts considered to be unsigned. | |||
| 2183 | inline const APInt &umax(const APInt &A, const APInt &B) { | |||
| 2184 | return A.ugt(B) ? A : B; | |||
| 2185 | } | |||
| 2186 | ||||
| 2187 | /// Compute GCD of two unsigned APInt values. | |||
| 2188 | /// | |||
| 2189 | /// This function returns the greatest common divisor of the two APInt values | |||
| 2190 | /// using Stein's algorithm. | |||
| 2191 | /// | |||
| 2192 | /// \returns the greatest common divisor of A and B. | |||
| 2193 | APInt GreatestCommonDivisor(APInt A, APInt B); | |||
| 2194 | ||||
| 2195 | /// Converts the given APInt to a double value. | |||
| 2196 | /// | |||
| 2197 | /// Treats the APInt as an unsigned value for conversion purposes. | |||
| 2198 | inline double RoundAPIntToDouble(const APInt &APIVal) { | |||
| 2199 | return APIVal.roundToDouble(); | |||
| 2200 | } | |||
| 2201 | ||||
| 2202 | /// Converts the given APInt to a double value. | |||
| 2203 | /// | |||
| 2204 | /// Treats the APInt as a signed value for conversion purposes. | |||
| 2205 | inline double RoundSignedAPIntToDouble(const APInt &APIVal) { | |||
| 2206 | return APIVal.signedRoundToDouble(); | |||
| 2207 | } | |||
| 2208 | ||||
| 2209 | /// Converts the given APInt to a float value. | |||
| 2210 | inline float RoundAPIntToFloat(const APInt &APIVal) { | |||
| 2211 | return float(RoundAPIntToDouble(APIVal)); | |||
| 2212 | } | |||
| 2213 | ||||
| 2214 | /// Converts the given APInt to a float value. | |||
| 2215 | /// | |||
| 2216 | /// Treats the APInt as a signed value for conversion purposes. | |||
| 2217 | inline float RoundSignedAPIntToFloat(const APInt &APIVal) { | |||
| 2218 | return float(APIVal.signedRoundToDouble()); | |||
| 2219 | } | |||
| 2220 | ||||
| 2221 | /// Converts the given double value into a APInt. | |||
| 2222 | /// | |||
| 2223 | /// This function convert a double value to an APInt value. | |||
| 2224 | APInt RoundDoubleToAPInt(double Double, unsigned width); | |||
| 2225 | ||||
| 2226 | /// Converts a float value into a APInt. | |||
| 2227 | /// | |||
| 2228 | /// Converts a float value into an APInt value. | |||
| 2229 | inline APInt RoundFloatToAPInt(float Float, unsigned width) { | |||
| 2230 | return RoundDoubleToAPInt(double(Float), width); | |||
| 2231 | } | |||
| 2232 | ||||
| 2233 | /// Return A unsign-divided by B, rounded by the given rounding mode. | |||
| 2234 | APInt RoundingUDiv(const APInt &A, const APInt &B, APInt::Rounding RM); | |||
| 2235 | ||||
| 2236 | /// Return A sign-divided by B, rounded by the given rounding mode. | |||
| 2237 | APInt RoundingSDiv(const APInt &A, const APInt &B, APInt::Rounding RM); | |||
| 2238 | ||||
| 2239 | /// Let q(n) = An^2 + Bn + C, and BW = bit width of the value range | |||
| 2240 | /// (e.g. 32 for i32). | |||
| 2241 | /// This function finds the smallest number n, such that | |||
| 2242 | /// (a) n >= 0 and q(n) = 0, or | |||
| 2243 | /// (b) n >= 1 and q(n-1) and q(n), when evaluated in the set of all | |||
| 2244 | /// integers, belong to two different intervals [Rk, Rk+R), | |||
| 2245 | /// where R = 2^BW, and k is an integer. | |||
| 2246 | /// The idea here is to find when q(n) "overflows" 2^BW, while at the | |||
| 2247 | /// same time "allowing" subtraction. In unsigned modulo arithmetic a | |||
| 2248 | /// subtraction (treated as addition of negated numbers) would always | |||
| 2249 | /// count as an overflow, but here we want to allow values to decrease | |||
| 2250 | /// and increase as long as they are within the same interval. | |||
| 2251 | /// Specifically, adding of two negative numbers should not cause an | |||
| 2252 | /// overflow (as long as the magnitude does not exceed the bit width). | |||
| 2253 | /// On the other hand, given a positive number, adding a negative | |||
| 2254 | /// number to it can give a negative result, which would cause the | |||
| 2255 | /// value to go from [-2^BW, 0) to [0, 2^BW). In that sense, zero is | |||
| 2256 | /// treated as a special case of an overflow. | |||
| 2257 | /// | |||
| 2258 | /// This function returns None if after finding k that minimizes the | |||
| 2259 | /// positive solution to q(n) = kR, both solutions are contained between | |||
| 2260 | /// two consecutive integers. | |||
| 2261 | /// | |||
| 2262 | /// There are cases where q(n) > T, and q(n+1) < T (assuming evaluation | |||
| 2263 | /// in arithmetic modulo 2^BW, and treating the values as signed) by the | |||
| 2264 | /// virtue of *signed* overflow. This function will *not* find such an n, | |||
| 2265 | /// however it may find a value of n satisfying the inequalities due to | |||
| 2266 | /// an *unsigned* overflow (if the values are treated as unsigned). | |||
| 2267 | /// To find a solution for a signed overflow, treat it as a problem of | |||
| 2268 | /// finding an unsigned overflow with a range with of BW-1. | |||
| 2269 | /// | |||
| 2270 | /// The returned value may have a different bit width from the input | |||
| 2271 | /// coefficients. | |||
| 2272 | Optional<APInt> SolveQuadraticEquationWrap(APInt A, APInt B, APInt C, | |||
| 2273 | unsigned RangeWidth); | |||
| 2274 | ||||
| 2275 | /// Compare two values, and if they are different, return the position of the | |||
| 2276 | /// most significant bit that is different in the values. | |||
| 2277 | Optional<unsigned> GetMostSignificantDifferentBit(const APInt &A, | |||
| 2278 | const APInt &B); | |||
| 2279 | ||||
| 2280 | } // End of APIntOps namespace | |||
| 2281 | ||||
| 2282 | // See friend declaration above. This additional declaration is required in | |||
| 2283 | // order to compile LLVM with IBM xlC compiler. | |||
| 2284 | hash_code hash_value(const APInt &Arg); | |||
| 2285 | ||||
| 2286 | /// StoreIntToMemory - Fills the StoreBytes bytes of memory starting from Dst | |||
| 2287 | /// with the integer held in IntVal. | |||
| 2288 | void StoreIntToMemory(const APInt &IntVal, uint8_t *Dst, unsigned StoreBytes); | |||
| 2289 | ||||
| 2290 | /// LoadIntFromMemory - Loads the integer stored in the LoadBytes bytes starting | |||
| 2291 | /// from Src into IntVal, which is assumed to be wide enough and to hold zero. | |||
| 2292 | void LoadIntFromMemory(APInt &IntVal, const uint8_t *Src, unsigned LoadBytes); | |||
| 2293 | ||||
| 2294 | /// Provide DenseMapInfo for APInt. | |||
| 2295 | template <> struct DenseMapInfo<APInt> { | |||
| 2296 | static inline APInt getEmptyKey() { | |||
| 2297 | APInt V(nullptr, 0); | |||
| 2298 | V.U.VAL = 0; | |||
| 2299 | return V; | |||
| 2300 | } | |||
| 2301 | ||||
| 2302 | static inline APInt getTombstoneKey() { | |||
| 2303 | APInt V(nullptr, 0); | |||
| 2304 | V.U.VAL = 1; | |||
| 2305 | return V; | |||
| 2306 | } | |||
| 2307 | ||||
| 2308 | static unsigned getHashValue(const APInt &Key); | |||
| 2309 | ||||
| 2310 | static bool isEqual(const APInt &LHS, const APInt &RHS) { | |||
| 2311 | return LHS.getBitWidth() == RHS.getBitWidth() && LHS == RHS; | |||
| 2312 | } | |||
| 2313 | }; | |||
| 2314 | ||||
| 2315 | } // namespace llvm | |||
| 2316 | ||||
| 2317 | #endif |