| File: | llvm/include/llvm/IR/DataLayout.h |
| Warning: | line 395, column 38 Called C++ object pointer is null |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
| 1 | //===- ScalarEvolutionExpander.cpp - Scalar Evolution Analysis ------------===// | ||||
| 2 | // | ||||
| 3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. | ||||
| 4 | // See https://llvm.org/LICENSE.txt for license information. | ||||
| 5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception | ||||
| 6 | // | ||||
| 7 | //===----------------------------------------------------------------------===// | ||||
| 8 | // | ||||
| 9 | // This file contains the implementation of the scalar evolution expander, | ||||
| 10 | // which is used to generate the code corresponding to a given scalar evolution | ||||
| 11 | // expression. | ||||
| 12 | // | ||||
| 13 | //===----------------------------------------------------------------------===// | ||||
| 14 | |||||
| 15 | #include "llvm/Transforms/Utils/ScalarEvolutionExpander.h" | ||||
| 16 | #include "llvm/ADT/STLExtras.h" | ||||
| 17 | #include "llvm/ADT/SmallSet.h" | ||||
| 18 | #include "llvm/Analysis/InstructionSimplify.h" | ||||
| 19 | #include "llvm/Analysis/LoopInfo.h" | ||||
| 20 | #include "llvm/Analysis/TargetTransformInfo.h" | ||||
| 21 | #include "llvm/IR/DataLayout.h" | ||||
| 22 | #include "llvm/IR/Dominators.h" | ||||
| 23 | #include "llvm/IR/IntrinsicInst.h" | ||||
| 24 | #include "llvm/IR/LLVMContext.h" | ||||
| 25 | #include "llvm/IR/Module.h" | ||||
| 26 | #include "llvm/IR/PatternMatch.h" | ||||
| 27 | #include "llvm/Support/CommandLine.h" | ||||
| 28 | #include "llvm/Support/Debug.h" | ||||
| 29 | #include "llvm/Support/raw_ostream.h" | ||||
| 30 | #include "llvm/Transforms/Utils/LoopUtils.h" | ||||
| 31 | |||||
| 32 | using namespace llvm; | ||||
| 33 | |||||
| 34 | cl::opt<unsigned> llvm::SCEVCheapExpansionBudget( | ||||
| 35 | "scev-cheap-expansion-budget", cl::Hidden, cl::init(4), | ||||
| 36 | cl::desc("When performing SCEV expansion only if it is cheap to do, this " | ||||
| 37 | "controls the budget that is considered cheap (default = 4)")); | ||||
| 38 | |||||
| 39 | using namespace PatternMatch; | ||||
| 40 | |||||
| 41 | /// ReuseOrCreateCast - Arrange for there to be a cast of V to Ty at IP, | ||||
| 42 | /// reusing an existing cast if a suitable one (= dominating IP) exists, or | ||||
| 43 | /// creating a new one. | ||||
| 44 | Value *SCEVExpander::ReuseOrCreateCast(Value *V, Type *Ty, | ||||
| 45 | Instruction::CastOps Op, | ||||
| 46 | BasicBlock::iterator IP) { | ||||
| 47 | // This function must be called with the builder having a valid insertion | ||||
| 48 | // point. It doesn't need to be the actual IP where the uses of the returned | ||||
| 49 | // cast will be added, but it must dominate such IP. | ||||
| 50 | // We use this precondition to produce a cast that will dominate all its | ||||
| 51 | // uses. In particular, this is crucial for the case where the builder's | ||||
| 52 | // insertion point *is* the point where we were asked to put the cast. | ||||
| 53 | // Since we don't know the builder's insertion point is actually | ||||
| 54 | // where the uses will be added (only that it dominates it), we are | ||||
| 55 | // not allowed to move it. | ||||
| 56 | BasicBlock::iterator BIP = Builder.GetInsertPoint(); | ||||
| 57 | |||||
| 58 | Instruction *Ret = nullptr; | ||||
| 59 | |||||
| 60 | // Check to see if there is already a cast! | ||||
| 61 | for (User *U : V->users()) { | ||||
| 62 | if (U->getType() != Ty) | ||||
| 63 | continue; | ||||
| 64 | CastInst *CI = dyn_cast<CastInst>(U); | ||||
| 65 | if (!CI || CI->getOpcode() != Op) | ||||
| 66 | continue; | ||||
| 67 | |||||
| 68 | // Found a suitable cast that is at IP or comes before IP. Use it. Note that | ||||
| 69 | // the cast must also properly dominate the Builder's insertion point. | ||||
| 70 | if (IP->getParent() == CI->getParent() && &*BIP != CI && | ||||
| 71 | (&*IP == CI || CI->comesBefore(&*IP))) { | ||||
| 72 | Ret = CI; | ||||
| 73 | break; | ||||
| 74 | } | ||||
| 75 | } | ||||
| 76 | |||||
| 77 | // Create a new cast. | ||||
| 78 | if (!Ret) { | ||||
| 79 | Ret = CastInst::Create(Op, V, Ty, V->getName(), &*IP); | ||||
| 80 | rememberInstruction(Ret); | ||||
| 81 | } | ||||
| 82 | |||||
| 83 | // We assert at the end of the function since IP might point to an | ||||
| 84 | // instruction with different dominance properties than a cast | ||||
| 85 | // (an invoke for example) and not dominate BIP (but the cast does). | ||||
| 86 | assert(SE.DT.dominates(Ret, &*BIP))((SE.DT.dominates(Ret, &*BIP)) ? static_cast<void> ( 0) : __assert_fail ("SE.DT.dominates(Ret, &*BIP)", "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 86, __PRETTY_FUNCTION__)); | ||||
| 87 | |||||
| 88 | return Ret; | ||||
| 89 | } | ||||
| 90 | |||||
| 91 | BasicBlock::iterator | ||||
| 92 | SCEVExpander::findInsertPointAfter(Instruction *I, Instruction *MustDominate) { | ||||
| 93 | BasicBlock::iterator IP = ++I->getIterator(); | ||||
| 94 | if (auto *II = dyn_cast<InvokeInst>(I)) | ||||
| 95 | IP = II->getNormalDest()->begin(); | ||||
| 96 | |||||
| 97 | while (isa<PHINode>(IP)) | ||||
| 98 | ++IP; | ||||
| 99 | |||||
| 100 | if (isa<FuncletPadInst>(IP) || isa<LandingPadInst>(IP)) { | ||||
| 101 | ++IP; | ||||
| 102 | } else if (isa<CatchSwitchInst>(IP)) { | ||||
| 103 | IP = MustDominate->getParent()->getFirstInsertionPt(); | ||||
| 104 | } else { | ||||
| 105 | assert(!IP->isEHPad() && "unexpected eh pad!")((!IP->isEHPad() && "unexpected eh pad!") ? static_cast <void> (0) : __assert_fail ("!IP->isEHPad() && \"unexpected eh pad!\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 105, __PRETTY_FUNCTION__)); | ||||
| 106 | } | ||||
| 107 | |||||
| 108 | // Adjust insert point to be after instructions inserted by the expander, so | ||||
| 109 | // we can re-use already inserted instructions. Avoid skipping past the | ||||
| 110 | // original \p MustDominate, in case it is an inserted instruction. | ||||
| 111 | while (isInsertedInstruction(&*IP) && &*IP != MustDominate) | ||||
| 112 | ++IP; | ||||
| 113 | |||||
| 114 | return IP; | ||||
| 115 | } | ||||
| 116 | |||||
| 117 | /// InsertNoopCastOfTo - Insert a cast of V to the specified type, | ||||
| 118 | /// which must be possible with a noop cast, doing what we can to share | ||||
| 119 | /// the casts. | ||||
| 120 | Value *SCEVExpander::InsertNoopCastOfTo(Value *V, Type *Ty) { | ||||
| 121 | Instruction::CastOps Op = CastInst::getCastOpcode(V, false, Ty, false); | ||||
| 122 | assert((Op == Instruction::BitCast ||(((Op == Instruction::BitCast || Op == Instruction::PtrToInt || Op == Instruction::IntToPtr) && "InsertNoopCastOfTo cannot perform non-noop casts!" ) ? static_cast<void> (0) : __assert_fail ("(Op == Instruction::BitCast || Op == Instruction::PtrToInt || Op == Instruction::IntToPtr) && \"InsertNoopCastOfTo cannot perform non-noop casts!\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 125, __PRETTY_FUNCTION__)) | ||||
| 123 | Op == Instruction::PtrToInt ||(((Op == Instruction::BitCast || Op == Instruction::PtrToInt || Op == Instruction::IntToPtr) && "InsertNoopCastOfTo cannot perform non-noop casts!" ) ? static_cast<void> (0) : __assert_fail ("(Op == Instruction::BitCast || Op == Instruction::PtrToInt || Op == Instruction::IntToPtr) && \"InsertNoopCastOfTo cannot perform non-noop casts!\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 125, __PRETTY_FUNCTION__)) | ||||
| 124 | Op == Instruction::IntToPtr) &&(((Op == Instruction::BitCast || Op == Instruction::PtrToInt || Op == Instruction::IntToPtr) && "InsertNoopCastOfTo cannot perform non-noop casts!" ) ? static_cast<void> (0) : __assert_fail ("(Op == Instruction::BitCast || Op == Instruction::PtrToInt || Op == Instruction::IntToPtr) && \"InsertNoopCastOfTo cannot perform non-noop casts!\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 125, __PRETTY_FUNCTION__)) | ||||
| 125 | "InsertNoopCastOfTo cannot perform non-noop casts!")(((Op == Instruction::BitCast || Op == Instruction::PtrToInt || Op == Instruction::IntToPtr) && "InsertNoopCastOfTo cannot perform non-noop casts!" ) ? static_cast<void> (0) : __assert_fail ("(Op == Instruction::BitCast || Op == Instruction::PtrToInt || Op == Instruction::IntToPtr) && \"InsertNoopCastOfTo cannot perform non-noop casts!\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 125, __PRETTY_FUNCTION__)); | ||||
| 126 | assert(SE.getTypeSizeInBits(V->getType()) == SE.getTypeSizeInBits(Ty) &&((SE.getTypeSizeInBits(V->getType()) == SE.getTypeSizeInBits (Ty) && "InsertNoopCastOfTo cannot change sizes!") ? static_cast <void> (0) : __assert_fail ("SE.getTypeSizeInBits(V->getType()) == SE.getTypeSizeInBits(Ty) && \"InsertNoopCastOfTo cannot change sizes!\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 127, __PRETTY_FUNCTION__)) | ||||
| 127 | "InsertNoopCastOfTo cannot change sizes!")((SE.getTypeSizeInBits(V->getType()) == SE.getTypeSizeInBits (Ty) && "InsertNoopCastOfTo cannot change sizes!") ? static_cast <void> (0) : __assert_fail ("SE.getTypeSizeInBits(V->getType()) == SE.getTypeSizeInBits(Ty) && \"InsertNoopCastOfTo cannot change sizes!\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 127, __PRETTY_FUNCTION__)); | ||||
| 128 | |||||
| 129 | auto *PtrTy = dyn_cast<PointerType>(Ty); | ||||
| 130 | // inttoptr only works for integral pointers. For non-integral pointers, we | ||||
| 131 | // can create a GEP on i8* null with the integral value as index. Note that | ||||
| 132 | // it is safe to use GEP of null instead of inttoptr here, because only | ||||
| 133 | // expressions already based on a GEP of null should be converted to pointers | ||||
| 134 | // during expansion. | ||||
| 135 | if (Op
| ||||
| 136 | auto *Int8PtrTy = Builder.getInt8PtrTy(PtrTy->getAddressSpace()); | ||||
| 137 | assert(DL.getTypeAllocSize(Int8PtrTy->getElementType()) == 1 &&((DL.getTypeAllocSize(Int8PtrTy->getElementType()) == 1 && "alloc size of i8 must by 1 byte for the GEP to be correct") ? static_cast<void> (0) : __assert_fail ("DL.getTypeAllocSize(Int8PtrTy->getElementType()) == 1 && \"alloc size of i8 must by 1 byte for the GEP to be correct\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 138, __PRETTY_FUNCTION__)) | ||||
| 138 | "alloc size of i8 must by 1 byte for the GEP to be correct")((DL.getTypeAllocSize(Int8PtrTy->getElementType()) == 1 && "alloc size of i8 must by 1 byte for the GEP to be correct") ? static_cast<void> (0) : __assert_fail ("DL.getTypeAllocSize(Int8PtrTy->getElementType()) == 1 && \"alloc size of i8 must by 1 byte for the GEP to be correct\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 138, __PRETTY_FUNCTION__)); | ||||
| 139 | auto *GEP = Builder.CreateGEP( | ||||
| 140 | Builder.getInt8Ty(), Constant::getNullValue(Int8PtrTy), V, "uglygep"); | ||||
| 141 | return Builder.CreateBitCast(GEP, Ty); | ||||
| 142 | } | ||||
| 143 | // Short-circuit unnecessary bitcasts. | ||||
| 144 | if (Op == Instruction::BitCast) { | ||||
| 145 | if (V->getType() == Ty) | ||||
| 146 | return V; | ||||
| 147 | if (CastInst *CI = dyn_cast<CastInst>(V)) { | ||||
| 148 | if (CI->getOperand(0)->getType() == Ty) | ||||
| 149 | return CI->getOperand(0); | ||||
| 150 | } | ||||
| 151 | } | ||||
| 152 | // Short-circuit unnecessary inttoptr<->ptrtoint casts. | ||||
| 153 | if ((Op == Instruction::PtrToInt || Op == Instruction::IntToPtr) && | ||||
| 154 | SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(V->getType())) { | ||||
| 155 | if (CastInst *CI = dyn_cast<CastInst>(V)) | ||||
| 156 | if ((CI->getOpcode() == Instruction::PtrToInt || | ||||
| 157 | CI->getOpcode() == Instruction::IntToPtr) && | ||||
| 158 | SE.getTypeSizeInBits(CI->getType()) == | ||||
| 159 | SE.getTypeSizeInBits(CI->getOperand(0)->getType())) | ||||
| 160 | return CI->getOperand(0); | ||||
| 161 | if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) | ||||
| 162 | if ((CE->getOpcode() == Instruction::PtrToInt || | ||||
| 163 | CE->getOpcode() == Instruction::IntToPtr) && | ||||
| 164 | SE.getTypeSizeInBits(CE->getType()) == | ||||
| 165 | SE.getTypeSizeInBits(CE->getOperand(0)->getType())) | ||||
| 166 | return CE->getOperand(0); | ||||
| 167 | } | ||||
| 168 | |||||
| 169 | // Fold a cast of a constant. | ||||
| 170 | if (Constant *C = dyn_cast<Constant>(V)) | ||||
| 171 | return ConstantExpr::getCast(Op, C, Ty); | ||||
| 172 | |||||
| 173 | // Cast the argument at the beginning of the entry block, after | ||||
| 174 | // any bitcasts of other arguments. | ||||
| 175 | if (Argument *A = dyn_cast<Argument>(V)) { | ||||
| 176 | BasicBlock::iterator IP = A->getParent()->getEntryBlock().begin(); | ||||
| 177 | while ((isa<BitCastInst>(IP) && | ||||
| 178 | isa<Argument>(cast<BitCastInst>(IP)->getOperand(0)) && | ||||
| 179 | cast<BitCastInst>(IP)->getOperand(0) != A) || | ||||
| 180 | isa<DbgInfoIntrinsic>(IP)) | ||||
| 181 | ++IP; | ||||
| 182 | return ReuseOrCreateCast(A, Ty, Op, IP); | ||||
| 183 | } | ||||
| 184 | |||||
| 185 | // Cast the instruction immediately after the instruction. | ||||
| 186 | Instruction *I = cast<Instruction>(V); | ||||
| 187 | BasicBlock::iterator IP = findInsertPointAfter(I, &*Builder.GetInsertPoint()); | ||||
| 188 | return ReuseOrCreateCast(I, Ty, Op, IP); | ||||
| 189 | } | ||||
| 190 | |||||
| 191 | /// InsertBinop - Insert the specified binary operator, doing a small amount | ||||
| 192 | /// of work to avoid inserting an obviously redundant operation, and hoisting | ||||
| 193 | /// to an outer loop when the opportunity is there and it is safe. | ||||
| 194 | Value *SCEVExpander::InsertBinop(Instruction::BinaryOps Opcode, | ||||
| 195 | Value *LHS, Value *RHS, | ||||
| 196 | SCEV::NoWrapFlags Flags, bool IsSafeToHoist) { | ||||
| 197 | // Fold a binop with constant operands. | ||||
| 198 | if (Constant *CLHS = dyn_cast<Constant>(LHS)) | ||||
| 199 | if (Constant *CRHS = dyn_cast<Constant>(RHS)) | ||||
| 200 | return ConstantExpr::get(Opcode, CLHS, CRHS); | ||||
| 201 | |||||
| 202 | // Do a quick scan to see if we have this binop nearby. If so, reuse it. | ||||
| 203 | unsigned ScanLimit = 6; | ||||
| 204 | BasicBlock::iterator BlockBegin = Builder.GetInsertBlock()->begin(); | ||||
| 205 | // Scanning starts from the last instruction before the insertion point. | ||||
| 206 | BasicBlock::iterator IP = Builder.GetInsertPoint(); | ||||
| 207 | if (IP != BlockBegin) { | ||||
| 208 | --IP; | ||||
| 209 | for (; ScanLimit; --IP, --ScanLimit) { | ||||
| 210 | // Don't count dbg.value against the ScanLimit, to avoid perturbing the | ||||
| 211 | // generated code. | ||||
| 212 | if (isa<DbgInfoIntrinsic>(IP)) | ||||
| 213 | ScanLimit++; | ||||
| 214 | |||||
| 215 | auto canGenerateIncompatiblePoison = [&Flags](Instruction *I) { | ||||
| 216 | // Ensure that no-wrap flags match. | ||||
| 217 | if (isa<OverflowingBinaryOperator>(I)) { | ||||
| 218 | if (I->hasNoSignedWrap() != (Flags & SCEV::FlagNSW)) | ||||
| 219 | return true; | ||||
| 220 | if (I->hasNoUnsignedWrap() != (Flags & SCEV::FlagNUW)) | ||||
| 221 | return true; | ||||
| 222 | } | ||||
| 223 | // Conservatively, do not use any instruction which has any of exact | ||||
| 224 | // flags installed. | ||||
| 225 | if (isa<PossiblyExactOperator>(I) && I->isExact()) | ||||
| 226 | return true; | ||||
| 227 | return false; | ||||
| 228 | }; | ||||
| 229 | if (IP->getOpcode() == (unsigned)Opcode && IP->getOperand(0) == LHS && | ||||
| 230 | IP->getOperand(1) == RHS && !canGenerateIncompatiblePoison(&*IP)) | ||||
| 231 | return &*IP; | ||||
| 232 | if (IP == BlockBegin) break; | ||||
| 233 | } | ||||
| 234 | } | ||||
| 235 | |||||
| 236 | // Save the original insertion point so we can restore it when we're done. | ||||
| 237 | DebugLoc Loc = Builder.GetInsertPoint()->getDebugLoc(); | ||||
| 238 | SCEVInsertPointGuard Guard(Builder, this); | ||||
| 239 | |||||
| 240 | if (IsSafeToHoist) { | ||||
| 241 | // Move the insertion point out of as many loops as we can. | ||||
| 242 | while (const Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock())) { | ||||
| 243 | if (!L->isLoopInvariant(LHS) || !L->isLoopInvariant(RHS)) break; | ||||
| 244 | BasicBlock *Preheader = L->getLoopPreheader(); | ||||
| 245 | if (!Preheader) break; | ||||
| 246 | |||||
| 247 | // Ok, move up a level. | ||||
| 248 | Builder.SetInsertPoint(Preheader->getTerminator()); | ||||
| 249 | } | ||||
| 250 | } | ||||
| 251 | |||||
| 252 | // If we haven't found this binop, insert it. | ||||
| 253 | Instruction *BO = cast<Instruction>(Builder.CreateBinOp(Opcode, LHS, RHS)); | ||||
| 254 | BO->setDebugLoc(Loc); | ||||
| 255 | if (Flags & SCEV::FlagNUW) | ||||
| 256 | BO->setHasNoUnsignedWrap(); | ||||
| 257 | if (Flags & SCEV::FlagNSW) | ||||
| 258 | BO->setHasNoSignedWrap(); | ||||
| 259 | |||||
| 260 | return BO; | ||||
| 261 | } | ||||
| 262 | |||||
| 263 | /// FactorOutConstant - Test if S is divisible by Factor, using signed | ||||
| 264 | /// division. If so, update S with Factor divided out and return true. | ||||
| 265 | /// S need not be evenly divisible if a reasonable remainder can be | ||||
| 266 | /// computed. | ||||
| 267 | static bool FactorOutConstant(const SCEV *&S, const SCEV *&Remainder, | ||||
| 268 | const SCEV *Factor, ScalarEvolution &SE, | ||||
| 269 | const DataLayout &DL) { | ||||
| 270 | // Everything is divisible by one. | ||||
| 271 | if (Factor->isOne()) | ||||
| 272 | return true; | ||||
| 273 | |||||
| 274 | // x/x == 1. | ||||
| 275 | if (S == Factor) { | ||||
| 276 | S = SE.getConstant(S->getType(), 1); | ||||
| 277 | return true; | ||||
| 278 | } | ||||
| 279 | |||||
| 280 | // For a Constant, check for a multiple of the given factor. | ||||
| 281 | if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S)) { | ||||
| 282 | // 0/x == 0. | ||||
| 283 | if (C->isZero()) | ||||
| 284 | return true; | ||||
| 285 | // Check for divisibility. | ||||
| 286 | if (const SCEVConstant *FC = dyn_cast<SCEVConstant>(Factor)) { | ||||
| 287 | ConstantInt *CI = | ||||
| 288 | ConstantInt::get(SE.getContext(), C->getAPInt().sdiv(FC->getAPInt())); | ||||
| 289 | // If the quotient is zero and the remainder is non-zero, reject | ||||
| 290 | // the value at this scale. It will be considered for subsequent | ||||
| 291 | // smaller scales. | ||||
| 292 | if (!CI->isZero()) { | ||||
| 293 | const SCEV *Div = SE.getConstant(CI); | ||||
| 294 | S = Div; | ||||
| 295 | Remainder = SE.getAddExpr( | ||||
| 296 | Remainder, SE.getConstant(C->getAPInt().srem(FC->getAPInt()))); | ||||
| 297 | return true; | ||||
| 298 | } | ||||
| 299 | } | ||||
| 300 | } | ||||
| 301 | |||||
| 302 | // In a Mul, check if there is a constant operand which is a multiple | ||||
| 303 | // of the given factor. | ||||
| 304 | if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(S)) { | ||||
| 305 | // Size is known, check if there is a constant operand which is a multiple | ||||
| 306 | // of the given factor. If so, we can factor it. | ||||
| 307 | if (const SCEVConstant *FC = dyn_cast<SCEVConstant>(Factor)) | ||||
| 308 | if (const SCEVConstant *C = dyn_cast<SCEVConstant>(M->getOperand(0))) | ||||
| 309 | if (!C->getAPInt().srem(FC->getAPInt())) { | ||||
| 310 | SmallVector<const SCEV *, 4> NewMulOps(M->op_begin(), M->op_end()); | ||||
| 311 | NewMulOps[0] = SE.getConstant(C->getAPInt().sdiv(FC->getAPInt())); | ||||
| 312 | S = SE.getMulExpr(NewMulOps); | ||||
| 313 | return true; | ||||
| 314 | } | ||||
| 315 | } | ||||
| 316 | |||||
| 317 | // In an AddRec, check if both start and step are divisible. | ||||
| 318 | if (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(S)) { | ||||
| 319 | const SCEV *Step = A->getStepRecurrence(SE); | ||||
| 320 | const SCEV *StepRem = SE.getConstant(Step->getType(), 0); | ||||
| 321 | if (!FactorOutConstant(Step, StepRem, Factor, SE, DL)) | ||||
| 322 | return false; | ||||
| 323 | if (!StepRem->isZero()) | ||||
| 324 | return false; | ||||
| 325 | const SCEV *Start = A->getStart(); | ||||
| 326 | if (!FactorOutConstant(Start, Remainder, Factor, SE, DL)) | ||||
| 327 | return false; | ||||
| 328 | S = SE.getAddRecExpr(Start, Step, A->getLoop(), | ||||
| 329 | A->getNoWrapFlags(SCEV::FlagNW)); | ||||
| 330 | return true; | ||||
| 331 | } | ||||
| 332 | |||||
| 333 | return false; | ||||
| 334 | } | ||||
| 335 | |||||
| 336 | /// SimplifyAddOperands - Sort and simplify a list of add operands. NumAddRecs | ||||
| 337 | /// is the number of SCEVAddRecExprs present, which are kept at the end of | ||||
| 338 | /// the list. | ||||
| 339 | /// | ||||
| 340 | static void SimplifyAddOperands(SmallVectorImpl<const SCEV *> &Ops, | ||||
| 341 | Type *Ty, | ||||
| 342 | ScalarEvolution &SE) { | ||||
| 343 | unsigned NumAddRecs = 0; | ||||
| 344 | for (unsigned i = Ops.size(); i > 0 && isa<SCEVAddRecExpr>(Ops[i-1]); --i) | ||||
| 345 | ++NumAddRecs; | ||||
| 346 | // Group Ops into non-addrecs and addrecs. | ||||
| 347 | SmallVector<const SCEV *, 8> NoAddRecs(Ops.begin(), Ops.end() - NumAddRecs); | ||||
| 348 | SmallVector<const SCEV *, 8> AddRecs(Ops.end() - NumAddRecs, Ops.end()); | ||||
| 349 | // Let ScalarEvolution sort and simplify the non-addrecs list. | ||||
| 350 | const SCEV *Sum = NoAddRecs.empty() ? | ||||
| 351 | SE.getConstant(Ty, 0) : | ||||
| 352 | SE.getAddExpr(NoAddRecs); | ||||
| 353 | // If it returned an add, use the operands. Otherwise it simplified | ||||
| 354 | // the sum into a single value, so just use that. | ||||
| 355 | Ops.clear(); | ||||
| 356 | if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Sum)) | ||||
| 357 | Ops.append(Add->op_begin(), Add->op_end()); | ||||
| 358 | else if (!Sum->isZero()) | ||||
| 359 | Ops.push_back(Sum); | ||||
| 360 | // Then append the addrecs. | ||||
| 361 | Ops.append(AddRecs.begin(), AddRecs.end()); | ||||
| 362 | } | ||||
| 363 | |||||
| 364 | /// SplitAddRecs - Flatten a list of add operands, moving addrec start values | ||||
| 365 | /// out to the top level. For example, convert {a + b,+,c} to a, b, {0,+,d}. | ||||
| 366 | /// This helps expose more opportunities for folding parts of the expressions | ||||
| 367 | /// into GEP indices. | ||||
| 368 | /// | ||||
| 369 | static void SplitAddRecs(SmallVectorImpl<const SCEV *> &Ops, | ||||
| 370 | Type *Ty, | ||||
| 371 | ScalarEvolution &SE) { | ||||
| 372 | // Find the addrecs. | ||||
| 373 | SmallVector<const SCEV *, 8> AddRecs; | ||||
| 374 | for (unsigned i = 0, e = Ops.size(); i != e; ++i) | ||||
| 375 | while (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(Ops[i])) { | ||||
| 376 | const SCEV *Start = A->getStart(); | ||||
| 377 | if (Start->isZero()) break; | ||||
| 378 | const SCEV *Zero = SE.getConstant(Ty, 0); | ||||
| 379 | AddRecs.push_back(SE.getAddRecExpr(Zero, | ||||
| 380 | A->getStepRecurrence(SE), | ||||
| 381 | A->getLoop(), | ||||
| 382 | A->getNoWrapFlags(SCEV::FlagNW))); | ||||
| 383 | if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Start)) { | ||||
| 384 | Ops[i] = Zero; | ||||
| 385 | Ops.append(Add->op_begin(), Add->op_end()); | ||||
| 386 | e += Add->getNumOperands(); | ||||
| 387 | } else { | ||||
| 388 | Ops[i] = Start; | ||||
| 389 | } | ||||
| 390 | } | ||||
| 391 | if (!AddRecs.empty()) { | ||||
| 392 | // Add the addrecs onto the end of the list. | ||||
| 393 | Ops.append(AddRecs.begin(), AddRecs.end()); | ||||
| 394 | // Resort the operand list, moving any constants to the front. | ||||
| 395 | SimplifyAddOperands(Ops, Ty, SE); | ||||
| 396 | } | ||||
| 397 | } | ||||
| 398 | |||||
| 399 | /// expandAddToGEP - Expand an addition expression with a pointer type into | ||||
| 400 | /// a GEP instead of using ptrtoint+arithmetic+inttoptr. This helps | ||||
| 401 | /// BasicAliasAnalysis and other passes analyze the result. See the rules | ||||
| 402 | /// for getelementptr vs. inttoptr in | ||||
| 403 | /// http://llvm.org/docs/LangRef.html#pointeraliasing | ||||
| 404 | /// for details. | ||||
| 405 | /// | ||||
| 406 | /// Design note: The correctness of using getelementptr here depends on | ||||
| 407 | /// ScalarEvolution not recognizing inttoptr and ptrtoint operators, as | ||||
| 408 | /// they may introduce pointer arithmetic which may not be safely converted | ||||
| 409 | /// into getelementptr. | ||||
| 410 | /// | ||||
| 411 | /// Design note: It might seem desirable for this function to be more | ||||
| 412 | /// loop-aware. If some of the indices are loop-invariant while others | ||||
| 413 | /// aren't, it might seem desirable to emit multiple GEPs, keeping the | ||||
| 414 | /// loop-invariant portions of the overall computation outside the loop. | ||||
| 415 | /// However, there are a few reasons this is not done here. Hoisting simple | ||||
| 416 | /// arithmetic is a low-level optimization that often isn't very | ||||
| 417 | /// important until late in the optimization process. In fact, passes | ||||
| 418 | /// like InstructionCombining will combine GEPs, even if it means | ||||
| 419 | /// pushing loop-invariant computation down into loops, so even if the | ||||
| 420 | /// GEPs were split here, the work would quickly be undone. The | ||||
| 421 | /// LoopStrengthReduction pass, which is usually run quite late (and | ||||
| 422 | /// after the last InstructionCombining pass), takes care of hoisting | ||||
| 423 | /// loop-invariant portions of expressions, after considering what | ||||
| 424 | /// can be folded using target addressing modes. | ||||
| 425 | /// | ||||
| 426 | Value *SCEVExpander::expandAddToGEP(const SCEV *const *op_begin, | ||||
| 427 | const SCEV *const *op_end, | ||||
| 428 | PointerType *PTy, | ||||
| 429 | Type *Ty, | ||||
| 430 | Value *V) { | ||||
| 431 | Type *OriginalElTy = PTy->getElementType(); | ||||
| 432 | Type *ElTy = OriginalElTy; | ||||
| 433 | SmallVector<Value *, 4> GepIndices; | ||||
| 434 | SmallVector<const SCEV *, 8> Ops(op_begin, op_end); | ||||
| 435 | bool AnyNonZeroIndices = false; | ||||
| 436 | |||||
| 437 | // Split AddRecs up into parts as either of the parts may be usable | ||||
| 438 | // without the other. | ||||
| 439 | SplitAddRecs(Ops, Ty, SE); | ||||
| 440 | |||||
| 441 | Type *IntIdxTy = DL.getIndexType(PTy); | ||||
| 442 | |||||
| 443 | // Descend down the pointer's type and attempt to convert the other | ||||
| 444 | // operands into GEP indices, at each level. The first index in a GEP | ||||
| 445 | // indexes into the array implied by the pointer operand; the rest of | ||||
| 446 | // the indices index into the element or field type selected by the | ||||
| 447 | // preceding index. | ||||
| 448 | for (;;) { | ||||
| |||||
| 449 | // If the scale size is not 0, attempt to factor out a scale for | ||||
| 450 | // array indexing. | ||||
| 451 | SmallVector<const SCEV *, 8> ScaledOps; | ||||
| 452 | if (ElTy->isSized()) { | ||||
| 453 | const SCEV *ElSize = SE.getSizeOfExpr(IntIdxTy, ElTy); | ||||
| 454 | if (!ElSize->isZero()) { | ||||
| 455 | SmallVector<const SCEV *, 8> NewOps; | ||||
| 456 | for (const SCEV *Op : Ops) { | ||||
| 457 | const SCEV *Remainder = SE.getConstant(Ty, 0); | ||||
| 458 | if (FactorOutConstant(Op, Remainder, ElSize, SE, DL)) { | ||||
| 459 | // Op now has ElSize factored out. | ||||
| 460 | ScaledOps.push_back(Op); | ||||
| 461 | if (!Remainder->isZero()) | ||||
| 462 | NewOps.push_back(Remainder); | ||||
| 463 | AnyNonZeroIndices = true; | ||||
| 464 | } else { | ||||
| 465 | // The operand was not divisible, so add it to the list of operands | ||||
| 466 | // we'll scan next iteration. | ||||
| 467 | NewOps.push_back(Op); | ||||
| 468 | } | ||||
| 469 | } | ||||
| 470 | // If we made any changes, update Ops. | ||||
| 471 | if (!ScaledOps.empty()) { | ||||
| 472 | Ops = NewOps; | ||||
| 473 | SimplifyAddOperands(Ops, Ty, SE); | ||||
| 474 | } | ||||
| 475 | } | ||||
| 476 | } | ||||
| 477 | |||||
| 478 | // Record the scaled array index for this level of the type. If | ||||
| 479 | // we didn't find any operands that could be factored, tentatively | ||||
| 480 | // assume that element zero was selected (since the zero offset | ||||
| 481 | // would obviously be folded away). | ||||
| 482 | Value *Scaled = | ||||
| 483 | ScaledOps.empty() | ||||
| 484 | ? Constant::getNullValue(Ty) | ||||
| 485 | : expandCodeForImpl(SE.getAddExpr(ScaledOps), Ty, false); | ||||
| 486 | GepIndices.push_back(Scaled); | ||||
| 487 | |||||
| 488 | // Collect struct field index operands. | ||||
| 489 | while (StructType *STy = dyn_cast<StructType>(ElTy)) { | ||||
| 490 | bool FoundFieldNo = false; | ||||
| 491 | // An empty struct has no fields. | ||||
| 492 | if (STy->getNumElements() == 0) break; | ||||
| 493 | // Field offsets are known. See if a constant offset falls within any of | ||||
| 494 | // the struct fields. | ||||
| 495 | if (Ops.empty()) | ||||
| 496 | break; | ||||
| 497 | if (const SCEVConstant *C = dyn_cast<SCEVConstant>(Ops[0])) | ||||
| 498 | if (SE.getTypeSizeInBits(C->getType()) <= 64) { | ||||
| 499 | const StructLayout &SL = *DL.getStructLayout(STy); | ||||
| 500 | uint64_t FullOffset = C->getValue()->getZExtValue(); | ||||
| 501 | if (FullOffset < SL.getSizeInBytes()) { | ||||
| 502 | unsigned ElIdx = SL.getElementContainingOffset(FullOffset); | ||||
| 503 | GepIndices.push_back( | ||||
| 504 | ConstantInt::get(Type::getInt32Ty(Ty->getContext()), ElIdx)); | ||||
| 505 | ElTy = STy->getTypeAtIndex(ElIdx); | ||||
| 506 | Ops[0] = | ||||
| 507 | SE.getConstant(Ty, FullOffset - SL.getElementOffset(ElIdx)); | ||||
| 508 | AnyNonZeroIndices = true; | ||||
| 509 | FoundFieldNo = true; | ||||
| 510 | } | ||||
| 511 | } | ||||
| 512 | // If no struct field offsets were found, tentatively assume that | ||||
| 513 | // field zero was selected (since the zero offset would obviously | ||||
| 514 | // be folded away). | ||||
| 515 | if (!FoundFieldNo) { | ||||
| 516 | ElTy = STy->getTypeAtIndex(0u); | ||||
| 517 | GepIndices.push_back( | ||||
| 518 | Constant::getNullValue(Type::getInt32Ty(Ty->getContext()))); | ||||
| 519 | } | ||||
| 520 | } | ||||
| 521 | |||||
| 522 | if (ArrayType *ATy
| ||||
| 523 | ElTy = ATy->getElementType(); | ||||
| 524 | else | ||||
| 525 | // FIXME: Handle VectorType. | ||||
| 526 | // E.g., If ElTy is scalable vector, then ElSize is not a compile-time | ||||
| 527 | // constant, therefore can not be factored out. The generated IR is less | ||||
| 528 | // ideal with base 'V' cast to i8* and do ugly getelementptr over that. | ||||
| 529 | break; | ||||
| 530 | } | ||||
| 531 | |||||
| 532 | // If none of the operands were convertible to proper GEP indices, cast | ||||
| 533 | // the base to i8* and do an ugly getelementptr with that. It's still | ||||
| 534 | // better than ptrtoint+arithmetic+inttoptr at least. | ||||
| 535 | if (!AnyNonZeroIndices
| ||||
| 536 | // Cast the base to i8*. | ||||
| 537 | V = InsertNoopCastOfTo(V, | ||||
| 538 | Type::getInt8PtrTy(Ty->getContext(), PTy->getAddressSpace())); | ||||
| 539 | |||||
| 540 | assert(!isa<Instruction>(V) ||((!isa<Instruction>(V) || SE.DT.dominates(cast<Instruction >(V), &*Builder.GetInsertPoint())) ? static_cast<void > (0) : __assert_fail ("!isa<Instruction>(V) || SE.DT.dominates(cast<Instruction>(V), &*Builder.GetInsertPoint())" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 541, __PRETTY_FUNCTION__)) | ||||
| 541 | SE.DT.dominates(cast<Instruction>(V), &*Builder.GetInsertPoint()))((!isa<Instruction>(V) || SE.DT.dominates(cast<Instruction >(V), &*Builder.GetInsertPoint())) ? static_cast<void > (0) : __assert_fail ("!isa<Instruction>(V) || SE.DT.dominates(cast<Instruction>(V), &*Builder.GetInsertPoint())" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 541, __PRETTY_FUNCTION__)); | ||||
| 542 | |||||
| 543 | // Expand the operands for a plain byte offset. | ||||
| 544 | Value *Idx = expandCodeForImpl(SE.getAddExpr(Ops), Ty, false); | ||||
| 545 | |||||
| 546 | // Fold a GEP with constant operands. | ||||
| 547 | if (Constant *CLHS = dyn_cast<Constant>(V)) | ||||
| 548 | if (Constant *CRHS = dyn_cast<Constant>(Idx)) | ||||
| 549 | return ConstantExpr::getGetElementPtr(Type::getInt8Ty(Ty->getContext()), | ||||
| 550 | CLHS, CRHS); | ||||
| 551 | |||||
| 552 | // Do a quick scan to see if we have this GEP nearby. If so, reuse it. | ||||
| 553 | unsigned ScanLimit = 6; | ||||
| 554 | BasicBlock::iterator BlockBegin = Builder.GetInsertBlock()->begin(); | ||||
| 555 | // Scanning starts from the last instruction before the insertion point. | ||||
| 556 | BasicBlock::iterator IP = Builder.GetInsertPoint(); | ||||
| 557 | if (IP != BlockBegin) { | ||||
| 558 | --IP; | ||||
| 559 | for (; ScanLimit; --IP, --ScanLimit) { | ||||
| 560 | // Don't count dbg.value against the ScanLimit, to avoid perturbing the | ||||
| 561 | // generated code. | ||||
| 562 | if (isa<DbgInfoIntrinsic>(IP)) | ||||
| 563 | ScanLimit++; | ||||
| 564 | if (IP->getOpcode() == Instruction::GetElementPtr && | ||||
| 565 | IP->getOperand(0) == V && IP->getOperand(1) == Idx) | ||||
| 566 | return &*IP; | ||||
| 567 | if (IP == BlockBegin) break; | ||||
| 568 | } | ||||
| 569 | } | ||||
| 570 | |||||
| 571 | // Save the original insertion point so we can restore it when we're done. | ||||
| 572 | SCEVInsertPointGuard Guard(Builder, this); | ||||
| 573 | |||||
| 574 | // Move the insertion point out of as many loops as we can. | ||||
| 575 | while (const Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock())) { | ||||
| 576 | if (!L->isLoopInvariant(V) || !L->isLoopInvariant(Idx)) break; | ||||
| 577 | BasicBlock *Preheader = L->getLoopPreheader(); | ||||
| 578 | if (!Preheader) break; | ||||
| 579 | |||||
| 580 | // Ok, move up a level. | ||||
| 581 | Builder.SetInsertPoint(Preheader->getTerminator()); | ||||
| 582 | } | ||||
| 583 | |||||
| 584 | // Emit a GEP. | ||||
| 585 | return Builder.CreateGEP(Builder.getInt8Ty(), V, Idx, "uglygep"); | ||||
| 586 | } | ||||
| 587 | |||||
| 588 | { | ||||
| 589 | SCEVInsertPointGuard Guard(Builder, this); | ||||
| 590 | |||||
| 591 | // Move the insertion point out of as many loops as we can. | ||||
| 592 | while (const Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock())) { | ||||
| 593 | if (!L->isLoopInvariant(V)) break; | ||||
| 594 | |||||
| 595 | bool AnyIndexNotLoopInvariant = any_of( | ||||
| 596 | GepIndices, [L](Value *Op) { return !L->isLoopInvariant(Op); }); | ||||
| 597 | |||||
| 598 | if (AnyIndexNotLoopInvariant) | ||||
| 599 | break; | ||||
| 600 | |||||
| 601 | BasicBlock *Preheader = L->getLoopPreheader(); | ||||
| 602 | if (!Preheader) break; | ||||
| 603 | |||||
| 604 | // Ok, move up a level. | ||||
| 605 | Builder.SetInsertPoint(Preheader->getTerminator()); | ||||
| 606 | } | ||||
| 607 | |||||
| 608 | // Insert a pretty getelementptr. Note that this GEP is not marked inbounds, | ||||
| 609 | // because ScalarEvolution may have changed the address arithmetic to | ||||
| 610 | // compute a value which is beyond the end of the allocated object. | ||||
| 611 | Value *Casted = V; | ||||
| 612 | if (V->getType() != PTy) | ||||
| 613 | Casted = InsertNoopCastOfTo(Casted, PTy); | ||||
| 614 | Value *GEP = Builder.CreateGEP(OriginalElTy, Casted, GepIndices, "scevgep"); | ||||
| 615 | Ops.push_back(SE.getUnknown(GEP)); | ||||
| 616 | } | ||||
| 617 | |||||
| 618 | return expand(SE.getAddExpr(Ops)); | ||||
| 619 | } | ||||
| 620 | |||||
| 621 | Value *SCEVExpander::expandAddToGEP(const SCEV *Op, PointerType *PTy, Type *Ty, | ||||
| 622 | Value *V) { | ||||
| 623 | const SCEV *const Ops[1] = {Op}; | ||||
| 624 | return expandAddToGEP(Ops, Ops + 1, PTy, Ty, V); | ||||
| 625 | } | ||||
| 626 | |||||
| 627 | /// PickMostRelevantLoop - Given two loops pick the one that's most relevant for | ||||
| 628 | /// SCEV expansion. If they are nested, this is the most nested. If they are | ||||
| 629 | /// neighboring, pick the later. | ||||
| 630 | static const Loop *PickMostRelevantLoop(const Loop *A, const Loop *B, | ||||
| 631 | DominatorTree &DT) { | ||||
| 632 | if (!A) return B; | ||||
| 633 | if (!B) return A; | ||||
| 634 | if (A->contains(B)) return B; | ||||
| 635 | if (B->contains(A)) return A; | ||||
| 636 | if (DT.dominates(A->getHeader(), B->getHeader())) return B; | ||||
| 637 | if (DT.dominates(B->getHeader(), A->getHeader())) return A; | ||||
| 638 | return A; // Arbitrarily break the tie. | ||||
| 639 | } | ||||
| 640 | |||||
| 641 | /// getRelevantLoop - Get the most relevant loop associated with the given | ||||
| 642 | /// expression, according to PickMostRelevantLoop. | ||||
| 643 | const Loop *SCEVExpander::getRelevantLoop(const SCEV *S) { | ||||
| 644 | // Test whether we've already computed the most relevant loop for this SCEV. | ||||
| 645 | auto Pair = RelevantLoops.insert(std::make_pair(S, nullptr)); | ||||
| 646 | if (!Pair.second) | ||||
| 647 | return Pair.first->second; | ||||
| 648 | |||||
| 649 | if (isa<SCEVConstant>(S)) | ||||
| 650 | // A constant has no relevant loops. | ||||
| 651 | return nullptr; | ||||
| 652 | if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) { | ||||
| 653 | if (const Instruction *I = dyn_cast<Instruction>(U->getValue())) | ||||
| 654 | return Pair.first->second = SE.LI.getLoopFor(I->getParent()); | ||||
| 655 | // A non-instruction has no relevant loops. | ||||
| 656 | return nullptr; | ||||
| 657 | } | ||||
| 658 | if (const SCEVNAryExpr *N = dyn_cast<SCEVNAryExpr>(S)) { | ||||
| 659 | const Loop *L = nullptr; | ||||
| 660 | if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) | ||||
| 661 | L = AR->getLoop(); | ||||
| 662 | for (const SCEV *Op : N->operands()) | ||||
| 663 | L = PickMostRelevantLoop(L, getRelevantLoop(Op), SE.DT); | ||||
| 664 | return RelevantLoops[N] = L; | ||||
| 665 | } | ||||
| 666 | if (const SCEVIntegralCastExpr *C = dyn_cast<SCEVIntegralCastExpr>(S)) { | ||||
| 667 | const Loop *Result = getRelevantLoop(C->getOperand()); | ||||
| 668 | return RelevantLoops[C] = Result; | ||||
| 669 | } | ||||
| 670 | if (const SCEVUDivExpr *D = dyn_cast<SCEVUDivExpr>(S)) { | ||||
| 671 | const Loop *Result = PickMostRelevantLoop( | ||||
| 672 | getRelevantLoop(D->getLHS()), getRelevantLoop(D->getRHS()), SE.DT); | ||||
| 673 | return RelevantLoops[D] = Result; | ||||
| 674 | } | ||||
| 675 | llvm_unreachable("Unexpected SCEV type!")::llvm::llvm_unreachable_internal("Unexpected SCEV type!", "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 675); | ||||
| 676 | } | ||||
| 677 | |||||
| 678 | namespace { | ||||
| 679 | |||||
| 680 | /// LoopCompare - Compare loops by PickMostRelevantLoop. | ||||
| 681 | class LoopCompare { | ||||
| 682 | DominatorTree &DT; | ||||
| 683 | public: | ||||
| 684 | explicit LoopCompare(DominatorTree &dt) : DT(dt) {} | ||||
| 685 | |||||
| 686 | bool operator()(std::pair<const Loop *, const SCEV *> LHS, | ||||
| 687 | std::pair<const Loop *, const SCEV *> RHS) const { | ||||
| 688 | // Keep pointer operands sorted at the end. | ||||
| 689 | if (LHS.second->getType()->isPointerTy() != | ||||
| 690 | RHS.second->getType()->isPointerTy()) | ||||
| 691 | return LHS.second->getType()->isPointerTy(); | ||||
| 692 | |||||
| 693 | // Compare loops with PickMostRelevantLoop. | ||||
| 694 | if (LHS.first != RHS.first) | ||||
| 695 | return PickMostRelevantLoop(LHS.first, RHS.first, DT) != LHS.first; | ||||
| 696 | |||||
| 697 | // If one operand is a non-constant negative and the other is not, | ||||
| 698 | // put the non-constant negative on the right so that a sub can | ||||
| 699 | // be used instead of a negate and add. | ||||
| 700 | if (LHS.second->isNonConstantNegative()) { | ||||
| 701 | if (!RHS.second->isNonConstantNegative()) | ||||
| 702 | return false; | ||||
| 703 | } else if (RHS.second->isNonConstantNegative()) | ||||
| 704 | return true; | ||||
| 705 | |||||
| 706 | // Otherwise they are equivalent according to this comparison. | ||||
| 707 | return false; | ||||
| 708 | } | ||||
| 709 | }; | ||||
| 710 | |||||
| 711 | } | ||||
| 712 | |||||
| 713 | Value *SCEVExpander::visitAddExpr(const SCEVAddExpr *S) { | ||||
| 714 | Type *Ty = SE.getEffectiveSCEVType(S->getType()); | ||||
| 715 | |||||
| 716 | // Collect all the add operands in a loop, along with their associated loops. | ||||
| 717 | // Iterate in reverse so that constants are emitted last, all else equal, and | ||||
| 718 | // so that pointer operands are inserted first, which the code below relies on | ||||
| 719 | // to form more involved GEPs. | ||||
| 720 | SmallVector<std::pair<const Loop *, const SCEV *>, 8> OpsAndLoops; | ||||
| 721 | for (std::reverse_iterator<SCEVAddExpr::op_iterator> I(S->op_end()), | ||||
| 722 | E(S->op_begin()); I != E; ++I) | ||||
| 723 | OpsAndLoops.push_back(std::make_pair(getRelevantLoop(*I), *I)); | ||||
| 724 | |||||
| 725 | // Sort by loop. Use a stable sort so that constants follow non-constants and | ||||
| 726 | // pointer operands precede non-pointer operands. | ||||
| 727 | llvm::stable_sort(OpsAndLoops, LoopCompare(SE.DT)); | ||||
| 728 | |||||
| 729 | // Emit instructions to add all the operands. Hoist as much as possible | ||||
| 730 | // out of loops, and form meaningful getelementptrs where possible. | ||||
| 731 | Value *Sum = nullptr; | ||||
| 732 | for (auto I = OpsAndLoops.begin(), E = OpsAndLoops.end(); I != E;) { | ||||
| 733 | const Loop *CurLoop = I->first; | ||||
| 734 | const SCEV *Op = I->second; | ||||
| 735 | if (!Sum) { | ||||
| 736 | // This is the first operand. Just expand it. | ||||
| 737 | Sum = expand(Op); | ||||
| 738 | ++I; | ||||
| 739 | } else if (PointerType *PTy = dyn_cast<PointerType>(Sum->getType())) { | ||||
| 740 | // The running sum expression is a pointer. Try to form a getelementptr | ||||
| 741 | // at this level with that as the base. | ||||
| 742 | SmallVector<const SCEV *, 4> NewOps; | ||||
| 743 | for (; I != E && I->first == CurLoop; ++I) { | ||||
| 744 | // If the operand is SCEVUnknown and not instructions, peek through | ||||
| 745 | // it, to enable more of it to be folded into the GEP. | ||||
| 746 | const SCEV *X = I->second; | ||||
| 747 | if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(X)) | ||||
| 748 | if (!isa<Instruction>(U->getValue())) | ||||
| 749 | X = SE.getSCEV(U->getValue()); | ||||
| 750 | NewOps.push_back(X); | ||||
| 751 | } | ||||
| 752 | Sum = expandAddToGEP(NewOps.begin(), NewOps.end(), PTy, Ty, Sum); | ||||
| 753 | } else if (PointerType *PTy = dyn_cast<PointerType>(Op->getType())) { | ||||
| 754 | // The running sum is an integer, and there's a pointer at this level. | ||||
| 755 | // Try to form a getelementptr. If the running sum is instructions, | ||||
| 756 | // use a SCEVUnknown to avoid re-analyzing them. | ||||
| 757 | SmallVector<const SCEV *, 4> NewOps; | ||||
| 758 | NewOps.push_back(isa<Instruction>(Sum) ? SE.getUnknown(Sum) : | ||||
| 759 | SE.getSCEV(Sum)); | ||||
| 760 | for (++I; I != E && I->first == CurLoop; ++I) | ||||
| 761 | NewOps.push_back(I->second); | ||||
| 762 | Sum = expandAddToGEP(NewOps.begin(), NewOps.end(), PTy, Ty, expand(Op)); | ||||
| 763 | } else if (Op->isNonConstantNegative()) { | ||||
| 764 | // Instead of doing a negate and add, just do a subtract. | ||||
| 765 | Value *W = expandCodeForImpl(SE.getNegativeSCEV(Op), Ty, false); | ||||
| 766 | Sum = InsertNoopCastOfTo(Sum, Ty); | ||||
| 767 | Sum = InsertBinop(Instruction::Sub, Sum, W, SCEV::FlagAnyWrap, | ||||
| 768 | /*IsSafeToHoist*/ true); | ||||
| 769 | ++I; | ||||
| 770 | } else { | ||||
| 771 | // A simple add. | ||||
| 772 | Value *W = expandCodeForImpl(Op, Ty, false); | ||||
| 773 | Sum = InsertNoopCastOfTo(Sum, Ty); | ||||
| 774 | // Canonicalize a constant to the RHS. | ||||
| 775 | if (isa<Constant>(Sum)) std::swap(Sum, W); | ||||
| 776 | Sum = InsertBinop(Instruction::Add, Sum, W, S->getNoWrapFlags(), | ||||
| 777 | /*IsSafeToHoist*/ true); | ||||
| 778 | ++I; | ||||
| 779 | } | ||||
| 780 | } | ||||
| 781 | |||||
| 782 | return Sum; | ||||
| 783 | } | ||||
| 784 | |||||
| 785 | Value *SCEVExpander::visitMulExpr(const SCEVMulExpr *S) { | ||||
| 786 | Type *Ty = SE.getEffectiveSCEVType(S->getType()); | ||||
| 787 | |||||
| 788 | // Collect all the mul operands in a loop, along with their associated loops. | ||||
| 789 | // Iterate in reverse so that constants are emitted last, all else equal. | ||||
| 790 | SmallVector<std::pair<const Loop *, const SCEV *>, 8> OpsAndLoops; | ||||
| 791 | for (std::reverse_iterator<SCEVMulExpr::op_iterator> I(S->op_end()), | ||||
| 792 | E(S->op_begin()); I != E; ++I) | ||||
| 793 | OpsAndLoops.push_back(std::make_pair(getRelevantLoop(*I), *I)); | ||||
| 794 | |||||
| 795 | // Sort by loop. Use a stable sort so that constants follow non-constants. | ||||
| 796 | llvm::stable_sort(OpsAndLoops, LoopCompare(SE.DT)); | ||||
| 797 | |||||
| 798 | // Emit instructions to mul all the operands. Hoist as much as possible | ||||
| 799 | // out of loops. | ||||
| 800 | Value *Prod = nullptr; | ||||
| 801 | auto I = OpsAndLoops.begin(); | ||||
| 802 | |||||
| 803 | // Expand the calculation of X pow N in the following manner: | ||||
| 804 | // Let N = P1 + P2 + ... + PK, where all P are powers of 2. Then: | ||||
| 805 | // X pow N = (X pow P1) * (X pow P2) * ... * (X pow PK). | ||||
| 806 | const auto ExpandOpBinPowN = [this, &I, &OpsAndLoops, &Ty]() { | ||||
| 807 | auto E = I; | ||||
| 808 | // Calculate how many times the same operand from the same loop is included | ||||
| 809 | // into this power. | ||||
| 810 | uint64_t Exponent = 0; | ||||
| 811 | const uint64_t MaxExponent = UINT64_MAX(18446744073709551615UL) >> 1; | ||||
| 812 | // No one sane will ever try to calculate such huge exponents, but if we | ||||
| 813 | // need this, we stop on UINT64_MAX / 2 because we need to exit the loop | ||||
| 814 | // below when the power of 2 exceeds our Exponent, and we want it to be | ||||
| 815 | // 1u << 31 at most to not deal with unsigned overflow. | ||||
| 816 | while (E != OpsAndLoops.end() && *I == *E && Exponent != MaxExponent) { | ||||
| 817 | ++Exponent; | ||||
| 818 | ++E; | ||||
| 819 | } | ||||
| 820 | assert(Exponent > 0 && "Trying to calculate a zeroth exponent of operand?")((Exponent > 0 && "Trying to calculate a zeroth exponent of operand?" ) ? static_cast<void> (0) : __assert_fail ("Exponent > 0 && \"Trying to calculate a zeroth exponent of operand?\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 820, __PRETTY_FUNCTION__)); | ||||
| 821 | |||||
| 822 | // Calculate powers with exponents 1, 2, 4, 8 etc. and include those of them | ||||
| 823 | // that are needed into the result. | ||||
| 824 | Value *P = expandCodeForImpl(I->second, Ty, false); | ||||
| 825 | Value *Result = nullptr; | ||||
| 826 | if (Exponent & 1) | ||||
| 827 | Result = P; | ||||
| 828 | for (uint64_t BinExp = 2; BinExp <= Exponent; BinExp <<= 1) { | ||||
| 829 | P = InsertBinop(Instruction::Mul, P, P, SCEV::FlagAnyWrap, | ||||
| 830 | /*IsSafeToHoist*/ true); | ||||
| 831 | if (Exponent & BinExp) | ||||
| 832 | Result = Result ? InsertBinop(Instruction::Mul, Result, P, | ||||
| 833 | SCEV::FlagAnyWrap, | ||||
| 834 | /*IsSafeToHoist*/ true) | ||||
| 835 | : P; | ||||
| 836 | } | ||||
| 837 | |||||
| 838 | I = E; | ||||
| 839 | assert(Result && "Nothing was expanded?")((Result && "Nothing was expanded?") ? static_cast< void> (0) : __assert_fail ("Result && \"Nothing was expanded?\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 839, __PRETTY_FUNCTION__)); | ||||
| 840 | return Result; | ||||
| 841 | }; | ||||
| 842 | |||||
| 843 | while (I != OpsAndLoops.end()) { | ||||
| 844 | if (!Prod) { | ||||
| 845 | // This is the first operand. Just expand it. | ||||
| 846 | Prod = ExpandOpBinPowN(); | ||||
| 847 | } else if (I->second->isAllOnesValue()) { | ||||
| 848 | // Instead of doing a multiply by negative one, just do a negate. | ||||
| 849 | Prod = InsertNoopCastOfTo(Prod, Ty); | ||||
| 850 | Prod = InsertBinop(Instruction::Sub, Constant::getNullValue(Ty), Prod, | ||||
| 851 | SCEV::FlagAnyWrap, /*IsSafeToHoist*/ true); | ||||
| 852 | ++I; | ||||
| 853 | } else { | ||||
| 854 | // A simple mul. | ||||
| 855 | Value *W = ExpandOpBinPowN(); | ||||
| 856 | Prod = InsertNoopCastOfTo(Prod, Ty); | ||||
| 857 | // Canonicalize a constant to the RHS. | ||||
| 858 | if (isa<Constant>(Prod)) std::swap(Prod, W); | ||||
| 859 | const APInt *RHS; | ||||
| 860 | if (match(W, m_Power2(RHS))) { | ||||
| 861 | // Canonicalize Prod*(1<<C) to Prod<<C. | ||||
| 862 | assert(!Ty->isVectorTy() && "vector types are not SCEVable")((!Ty->isVectorTy() && "vector types are not SCEVable" ) ? static_cast<void> (0) : __assert_fail ("!Ty->isVectorTy() && \"vector types are not SCEVable\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 862, __PRETTY_FUNCTION__)); | ||||
| 863 | auto NWFlags = S->getNoWrapFlags(); | ||||
| 864 | // clear nsw flag if shl will produce poison value. | ||||
| 865 | if (RHS->logBase2() == RHS->getBitWidth() - 1) | ||||
| 866 | NWFlags = ScalarEvolution::clearFlags(NWFlags, SCEV::FlagNSW); | ||||
| 867 | Prod = InsertBinop(Instruction::Shl, Prod, | ||||
| 868 | ConstantInt::get(Ty, RHS->logBase2()), NWFlags, | ||||
| 869 | /*IsSafeToHoist*/ true); | ||||
| 870 | } else { | ||||
| 871 | Prod = InsertBinop(Instruction::Mul, Prod, W, S->getNoWrapFlags(), | ||||
| 872 | /*IsSafeToHoist*/ true); | ||||
| 873 | } | ||||
| 874 | } | ||||
| 875 | } | ||||
| 876 | |||||
| 877 | return Prod; | ||||
| 878 | } | ||||
| 879 | |||||
| 880 | Value *SCEVExpander::visitUDivExpr(const SCEVUDivExpr *S) { | ||||
| 881 | Type *Ty = SE.getEffectiveSCEVType(S->getType()); | ||||
| 882 | |||||
| 883 | Value *LHS = expandCodeForImpl(S->getLHS(), Ty, false); | ||||
| 884 | if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getRHS())) { | ||||
| 885 | const APInt &RHS = SC->getAPInt(); | ||||
| 886 | if (RHS.isPowerOf2()) | ||||
| 887 | return InsertBinop(Instruction::LShr, LHS, | ||||
| 888 | ConstantInt::get(Ty, RHS.logBase2()), | ||||
| 889 | SCEV::FlagAnyWrap, /*IsSafeToHoist*/ true); | ||||
| 890 | } | ||||
| 891 | |||||
| 892 | Value *RHS = expandCodeForImpl(S->getRHS(), Ty, false); | ||||
| 893 | return InsertBinop(Instruction::UDiv, LHS, RHS, SCEV::FlagAnyWrap, | ||||
| 894 | /*IsSafeToHoist*/ SE.isKnownNonZero(S->getRHS())); | ||||
| 895 | } | ||||
| 896 | |||||
| 897 | /// Move parts of Base into Rest to leave Base with the minimal | ||||
| 898 | /// expression that provides a pointer operand suitable for a | ||||
| 899 | /// GEP expansion. | ||||
| 900 | static void ExposePointerBase(const SCEV *&Base, const SCEV *&Rest, | ||||
| 901 | ScalarEvolution &SE) { | ||||
| 902 | while (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(Base)) { | ||||
| 903 | Base = A->getStart(); | ||||
| 904 | Rest = SE.getAddExpr(Rest, | ||||
| 905 | SE.getAddRecExpr(SE.getConstant(A->getType(), 0), | ||||
| 906 | A->getStepRecurrence(SE), | ||||
| 907 | A->getLoop(), | ||||
| 908 | A->getNoWrapFlags(SCEV::FlagNW))); | ||||
| 909 | } | ||||
| 910 | if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(Base)) { | ||||
| 911 | Base = A->getOperand(A->getNumOperands()-1); | ||||
| 912 | SmallVector<const SCEV *, 8> NewAddOps(A->op_begin(), A->op_end()); | ||||
| 913 | NewAddOps.back() = Rest; | ||||
| 914 | Rest = SE.getAddExpr(NewAddOps); | ||||
| 915 | ExposePointerBase(Base, Rest, SE); | ||||
| 916 | } | ||||
| 917 | } | ||||
| 918 | |||||
| 919 | /// Determine if this is a well-behaved chain of instructions leading back to | ||||
| 920 | /// the PHI. If so, it may be reused by expanded expressions. | ||||
| 921 | bool SCEVExpander::isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV, | ||||
| 922 | const Loop *L) { | ||||
| 923 | if (IncV->getNumOperands() == 0 || isa<PHINode>(IncV) || | ||||
| 924 | (isa<CastInst>(IncV) && !isa<BitCastInst>(IncV))) | ||||
| 925 | return false; | ||||
| 926 | // If any of the operands don't dominate the insert position, bail. | ||||
| 927 | // Addrec operands are always loop-invariant, so this can only happen | ||||
| 928 | // if there are instructions which haven't been hoisted. | ||||
| 929 | if (L == IVIncInsertLoop) { | ||||
| 930 | for (User::op_iterator OI = IncV->op_begin()+1, | ||||
| 931 | OE = IncV->op_end(); OI != OE; ++OI) | ||||
| 932 | if (Instruction *OInst = dyn_cast<Instruction>(OI)) | ||||
| 933 | if (!SE.DT.dominates(OInst, IVIncInsertPos)) | ||||
| 934 | return false; | ||||
| 935 | } | ||||
| 936 | // Advance to the next instruction. | ||||
| 937 | IncV = dyn_cast<Instruction>(IncV->getOperand(0)); | ||||
| 938 | if (!IncV) | ||||
| 939 | return false; | ||||
| 940 | |||||
| 941 | if (IncV->mayHaveSideEffects()) | ||||
| 942 | return false; | ||||
| 943 | |||||
| 944 | if (IncV == PN) | ||||
| 945 | return true; | ||||
| 946 | |||||
| 947 | return isNormalAddRecExprPHI(PN, IncV, L); | ||||
| 948 | } | ||||
| 949 | |||||
| 950 | /// getIVIncOperand returns an induction variable increment's induction | ||||
| 951 | /// variable operand. | ||||
| 952 | /// | ||||
| 953 | /// If allowScale is set, any type of GEP is allowed as long as the nonIV | ||||
| 954 | /// operands dominate InsertPos. | ||||
| 955 | /// | ||||
| 956 | /// If allowScale is not set, ensure that a GEP increment conforms to one of the | ||||
| 957 | /// simple patterns generated by getAddRecExprPHILiterally and | ||||
| 958 | /// expandAddtoGEP. If the pattern isn't recognized, return NULL. | ||||
| 959 | Instruction *SCEVExpander::getIVIncOperand(Instruction *IncV, | ||||
| 960 | Instruction *InsertPos, | ||||
| 961 | bool allowScale) { | ||||
| 962 | if (IncV == InsertPos) | ||||
| 963 | return nullptr; | ||||
| 964 | |||||
| 965 | switch (IncV->getOpcode()) { | ||||
| 966 | default: | ||||
| 967 | return nullptr; | ||||
| 968 | // Check for a simple Add/Sub or GEP of a loop invariant step. | ||||
| 969 | case Instruction::Add: | ||||
| 970 | case Instruction::Sub: { | ||||
| 971 | Instruction *OInst = dyn_cast<Instruction>(IncV->getOperand(1)); | ||||
| 972 | if (!OInst || SE.DT.dominates(OInst, InsertPos)) | ||||
| 973 | return dyn_cast<Instruction>(IncV->getOperand(0)); | ||||
| 974 | return nullptr; | ||||
| 975 | } | ||||
| 976 | case Instruction::BitCast: | ||||
| 977 | return dyn_cast<Instruction>(IncV->getOperand(0)); | ||||
| 978 | case Instruction::GetElementPtr: | ||||
| 979 | for (auto I = IncV->op_begin() + 1, E = IncV->op_end(); I != E; ++I) { | ||||
| 980 | if (isa<Constant>(*I)) | ||||
| 981 | continue; | ||||
| 982 | if (Instruction *OInst = dyn_cast<Instruction>(*I)) { | ||||
| 983 | if (!SE.DT.dominates(OInst, InsertPos)) | ||||
| 984 | return nullptr; | ||||
| 985 | } | ||||
| 986 | if (allowScale) { | ||||
| 987 | // allow any kind of GEP as long as it can be hoisted. | ||||
| 988 | continue; | ||||
| 989 | } | ||||
| 990 | // This must be a pointer addition of constants (pretty), which is already | ||||
| 991 | // handled, or some number of address-size elements (ugly). Ugly geps | ||||
| 992 | // have 2 operands. i1* is used by the expander to represent an | ||||
| 993 | // address-size element. | ||||
| 994 | if (IncV->getNumOperands() != 2) | ||||
| 995 | return nullptr; | ||||
| 996 | unsigned AS = cast<PointerType>(IncV->getType())->getAddressSpace(); | ||||
| 997 | if (IncV->getType() != Type::getInt1PtrTy(SE.getContext(), AS) | ||||
| 998 | && IncV->getType() != Type::getInt8PtrTy(SE.getContext(), AS)) | ||||
| 999 | return nullptr; | ||||
| 1000 | break; | ||||
| 1001 | } | ||||
| 1002 | return dyn_cast<Instruction>(IncV->getOperand(0)); | ||||
| 1003 | } | ||||
| 1004 | } | ||||
| 1005 | |||||
| 1006 | /// If the insert point of the current builder or any of the builders on the | ||||
| 1007 | /// stack of saved builders has 'I' as its insert point, update it to point to | ||||
| 1008 | /// the instruction after 'I'. This is intended to be used when the instruction | ||||
| 1009 | /// 'I' is being moved. If this fixup is not done and 'I' is moved to a | ||||
| 1010 | /// different block, the inconsistent insert point (with a mismatched | ||||
| 1011 | /// Instruction and Block) can lead to an instruction being inserted in a block | ||||
| 1012 | /// other than its parent. | ||||
| 1013 | void SCEVExpander::fixupInsertPoints(Instruction *I) { | ||||
| 1014 | BasicBlock::iterator It(*I); | ||||
| 1015 | BasicBlock::iterator NewInsertPt = std::next(It); | ||||
| 1016 | if (Builder.GetInsertPoint() == It) | ||||
| 1017 | Builder.SetInsertPoint(&*NewInsertPt); | ||||
| 1018 | for (auto *InsertPtGuard : InsertPointGuards) | ||||
| 1019 | if (InsertPtGuard->GetInsertPoint() == It) | ||||
| 1020 | InsertPtGuard->SetInsertPoint(NewInsertPt); | ||||
| 1021 | } | ||||
| 1022 | |||||
| 1023 | /// hoistStep - Attempt to hoist a simple IV increment above InsertPos to make | ||||
| 1024 | /// it available to other uses in this loop. Recursively hoist any operands, | ||||
| 1025 | /// until we reach a value that dominates InsertPos. | ||||
| 1026 | bool SCEVExpander::hoistIVInc(Instruction *IncV, Instruction *InsertPos) { | ||||
| 1027 | if (SE.DT.dominates(IncV, InsertPos)) | ||||
| 1028 | return true; | ||||
| 1029 | |||||
| 1030 | // InsertPos must itself dominate IncV so that IncV's new position satisfies | ||||
| 1031 | // its existing users. | ||||
| 1032 | if (isa<PHINode>(InsertPos) || | ||||
| 1033 | !SE.DT.dominates(InsertPos->getParent(), IncV->getParent())) | ||||
| 1034 | return false; | ||||
| 1035 | |||||
| 1036 | if (!SE.LI.movementPreservesLCSSAForm(IncV, InsertPos)) | ||||
| 1037 | return false; | ||||
| 1038 | |||||
| 1039 | // Check that the chain of IV operands leading back to Phi can be hoisted. | ||||
| 1040 | SmallVector<Instruction*, 4> IVIncs; | ||||
| 1041 | for(;;) { | ||||
| 1042 | Instruction *Oper = getIVIncOperand(IncV, InsertPos, /*allowScale*/true); | ||||
| 1043 | if (!Oper) | ||||
| 1044 | return false; | ||||
| 1045 | // IncV is safe to hoist. | ||||
| 1046 | IVIncs.push_back(IncV); | ||||
| 1047 | IncV = Oper; | ||||
| 1048 | if (SE.DT.dominates(IncV, InsertPos)) | ||||
| 1049 | break; | ||||
| 1050 | } | ||||
| 1051 | for (auto I = IVIncs.rbegin(), E = IVIncs.rend(); I != E; ++I) { | ||||
| 1052 | fixupInsertPoints(*I); | ||||
| 1053 | (*I)->moveBefore(InsertPos); | ||||
| 1054 | } | ||||
| 1055 | return true; | ||||
| 1056 | } | ||||
| 1057 | |||||
| 1058 | /// Determine if this cyclic phi is in a form that would have been generated by | ||||
| 1059 | /// LSR. We don't care if the phi was actually expanded in this pass, as long | ||||
| 1060 | /// as it is in a low-cost form, for example, no implied multiplication. This | ||||
| 1061 | /// should match any patterns generated by getAddRecExprPHILiterally and | ||||
| 1062 | /// expandAddtoGEP. | ||||
| 1063 | bool SCEVExpander::isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV, | ||||
| 1064 | const Loop *L) { | ||||
| 1065 | for(Instruction *IVOper = IncV; | ||||
| 1066 | (IVOper = getIVIncOperand(IVOper, L->getLoopPreheader()->getTerminator(), | ||||
| 1067 | /*allowScale=*/false));) { | ||||
| 1068 | if (IVOper == PN) | ||||
| 1069 | return true; | ||||
| 1070 | } | ||||
| 1071 | return false; | ||||
| 1072 | } | ||||
| 1073 | |||||
| 1074 | /// expandIVInc - Expand an IV increment at Builder's current InsertPos. | ||||
| 1075 | /// Typically this is the LatchBlock terminator or IVIncInsertPos, but we may | ||||
| 1076 | /// need to materialize IV increments elsewhere to handle difficult situations. | ||||
| 1077 | Value *SCEVExpander::expandIVInc(PHINode *PN, Value *StepV, const Loop *L, | ||||
| 1078 | Type *ExpandTy, Type *IntTy, | ||||
| 1079 | bool useSubtract) { | ||||
| 1080 | Value *IncV; | ||||
| 1081 | // If the PHI is a pointer, use a GEP, otherwise use an add or sub. | ||||
| 1082 | if (ExpandTy->isPointerTy()) { | ||||
| 1083 | PointerType *GEPPtrTy = cast<PointerType>(ExpandTy); | ||||
| 1084 | // If the step isn't constant, don't use an implicitly scaled GEP, because | ||||
| 1085 | // that would require a multiply inside the loop. | ||||
| 1086 | if (!isa<ConstantInt>(StepV)) | ||||
| 1087 | GEPPtrTy = PointerType::get(Type::getInt1Ty(SE.getContext()), | ||||
| 1088 | GEPPtrTy->getAddressSpace()); | ||||
| 1089 | IncV = expandAddToGEP(SE.getSCEV(StepV), GEPPtrTy, IntTy, PN); | ||||
| 1090 | if (IncV->getType() != PN->getType()) | ||||
| 1091 | IncV = Builder.CreateBitCast(IncV, PN->getType()); | ||||
| 1092 | } else { | ||||
| 1093 | IncV = useSubtract ? | ||||
| 1094 | Builder.CreateSub(PN, StepV, Twine(IVName) + ".iv.next") : | ||||
| 1095 | Builder.CreateAdd(PN, StepV, Twine(IVName) + ".iv.next"); | ||||
| 1096 | } | ||||
| 1097 | return IncV; | ||||
| 1098 | } | ||||
| 1099 | |||||
| 1100 | /// Hoist the addrec instruction chain rooted in the loop phi above the | ||||
| 1101 | /// position. This routine assumes that this is possible (has been checked). | ||||
| 1102 | void SCEVExpander::hoistBeforePos(DominatorTree *DT, Instruction *InstToHoist, | ||||
| 1103 | Instruction *Pos, PHINode *LoopPhi) { | ||||
| 1104 | do { | ||||
| 1105 | if (DT->dominates(InstToHoist, Pos)) | ||||
| 1106 | break; | ||||
| 1107 | // Make sure the increment is where we want it. But don't move it | ||||
| 1108 | // down past a potential existing post-inc user. | ||||
| 1109 | fixupInsertPoints(InstToHoist); | ||||
| 1110 | InstToHoist->moveBefore(Pos); | ||||
| 1111 | Pos = InstToHoist; | ||||
| 1112 | InstToHoist = cast<Instruction>(InstToHoist->getOperand(0)); | ||||
| 1113 | } while (InstToHoist != LoopPhi); | ||||
| 1114 | } | ||||
| 1115 | |||||
| 1116 | /// Check whether we can cheaply express the requested SCEV in terms of | ||||
| 1117 | /// the available PHI SCEV by truncation and/or inversion of the step. | ||||
| 1118 | static bool canBeCheaplyTransformed(ScalarEvolution &SE, | ||||
| 1119 | const SCEVAddRecExpr *Phi, | ||||
| 1120 | const SCEVAddRecExpr *Requested, | ||||
| 1121 | bool &InvertStep) { | ||||
| 1122 | Type *PhiTy = SE.getEffectiveSCEVType(Phi->getType()); | ||||
| 1123 | Type *RequestedTy = SE.getEffectiveSCEVType(Requested->getType()); | ||||
| 1124 | |||||
| 1125 | if (RequestedTy->getIntegerBitWidth() > PhiTy->getIntegerBitWidth()) | ||||
| 1126 | return false; | ||||
| 1127 | |||||
| 1128 | // Try truncate it if necessary. | ||||
| 1129 | Phi = dyn_cast<SCEVAddRecExpr>(SE.getTruncateOrNoop(Phi, RequestedTy)); | ||||
| 1130 | if (!Phi) | ||||
| 1131 | return false; | ||||
| 1132 | |||||
| 1133 | // Check whether truncation will help. | ||||
| 1134 | if (Phi == Requested) { | ||||
| 1135 | InvertStep = false; | ||||
| 1136 | return true; | ||||
| 1137 | } | ||||
| 1138 | |||||
| 1139 | // Check whether inverting will help: {R,+,-1} == R - {0,+,1}. | ||||
| 1140 | if (SE.getAddExpr(Requested->getStart(), | ||||
| 1141 | SE.getNegativeSCEV(Requested)) == Phi) { | ||||
| 1142 | InvertStep = true; | ||||
| 1143 | return true; | ||||
| 1144 | } | ||||
| 1145 | |||||
| 1146 | return false; | ||||
| 1147 | } | ||||
| 1148 | |||||
| 1149 | static bool IsIncrementNSW(ScalarEvolution &SE, const SCEVAddRecExpr *AR) { | ||||
| 1150 | if (!isa<IntegerType>(AR->getType())) | ||||
| 1151 | return false; | ||||
| 1152 | |||||
| 1153 | unsigned BitWidth = cast<IntegerType>(AR->getType())->getBitWidth(); | ||||
| 1154 | Type *WideTy = IntegerType::get(AR->getType()->getContext(), BitWidth * 2); | ||||
| 1155 | const SCEV *Step = AR->getStepRecurrence(SE); | ||||
| 1156 | const SCEV *OpAfterExtend = SE.getAddExpr(SE.getSignExtendExpr(Step, WideTy), | ||||
| 1157 | SE.getSignExtendExpr(AR, WideTy)); | ||||
| 1158 | const SCEV *ExtendAfterOp = | ||||
| 1159 | SE.getSignExtendExpr(SE.getAddExpr(AR, Step), WideTy); | ||||
| 1160 | return ExtendAfterOp == OpAfterExtend; | ||||
| 1161 | } | ||||
| 1162 | |||||
| 1163 | static bool IsIncrementNUW(ScalarEvolution &SE, const SCEVAddRecExpr *AR) { | ||||
| 1164 | if (!isa<IntegerType>(AR->getType())) | ||||
| 1165 | return false; | ||||
| 1166 | |||||
| 1167 | unsigned BitWidth = cast<IntegerType>(AR->getType())->getBitWidth(); | ||||
| 1168 | Type *WideTy = IntegerType::get(AR->getType()->getContext(), BitWidth * 2); | ||||
| 1169 | const SCEV *Step = AR->getStepRecurrence(SE); | ||||
| 1170 | const SCEV *OpAfterExtend = SE.getAddExpr(SE.getZeroExtendExpr(Step, WideTy), | ||||
| 1171 | SE.getZeroExtendExpr(AR, WideTy)); | ||||
| 1172 | const SCEV *ExtendAfterOp = | ||||
| 1173 | SE.getZeroExtendExpr(SE.getAddExpr(AR, Step), WideTy); | ||||
| 1174 | return ExtendAfterOp == OpAfterExtend; | ||||
| 1175 | } | ||||
| 1176 | |||||
| 1177 | /// getAddRecExprPHILiterally - Helper for expandAddRecExprLiterally. Expand | ||||
| 1178 | /// the base addrec, which is the addrec without any non-loop-dominating | ||||
| 1179 | /// values, and return the PHI. | ||||
| 1180 | PHINode * | ||||
| 1181 | SCEVExpander::getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized, | ||||
| 1182 | const Loop *L, | ||||
| 1183 | Type *ExpandTy, | ||||
| 1184 | Type *IntTy, | ||||
| 1185 | Type *&TruncTy, | ||||
| 1186 | bool &InvertStep) { | ||||
| 1187 | assert((!IVIncInsertLoop||IVIncInsertPos) && "Uninitialized insert position")(((!IVIncInsertLoop||IVIncInsertPos) && "Uninitialized insert position" ) ? static_cast<void> (0) : __assert_fail ("(!IVIncInsertLoop||IVIncInsertPos) && \"Uninitialized insert position\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 1187, __PRETTY_FUNCTION__)); | ||||
| 1188 | |||||
| 1189 | // Reuse a previously-inserted PHI, if present. | ||||
| 1190 | BasicBlock *LatchBlock = L->getLoopLatch(); | ||||
| 1191 | if (LatchBlock) { | ||||
| 1192 | PHINode *AddRecPhiMatch = nullptr; | ||||
| 1193 | Instruction *IncV = nullptr; | ||||
| 1194 | TruncTy = nullptr; | ||||
| 1195 | InvertStep = false; | ||||
| 1196 | |||||
| 1197 | // Only try partially matching scevs that need truncation and/or | ||||
| 1198 | // step-inversion if we know this loop is outside the current loop. | ||||
| 1199 | bool TryNonMatchingSCEV = | ||||
| 1200 | IVIncInsertLoop && | ||||
| 1201 | SE.DT.properlyDominates(LatchBlock, IVIncInsertLoop->getHeader()); | ||||
| 1202 | |||||
| 1203 | for (PHINode &PN : L->getHeader()->phis()) { | ||||
| 1204 | if (!SE.isSCEVable(PN.getType())) | ||||
| 1205 | continue; | ||||
| 1206 | |||||
| 1207 | // We should not look for a incomplete PHI. Getting SCEV for a incomplete | ||||
| 1208 | // PHI has no meaning at all. | ||||
| 1209 | if (!PN.isComplete()) { | ||||
| 1210 | DEBUG_WITH_TYPE(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType (DebugType)) { dbgs() << "One incomplete PHI is found: " << PN << "\n"; } } while (false) | ||||
| 1211 | DebugType, dbgs() << "One incomplete PHI is found: " << PN << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType (DebugType)) { dbgs() << "One incomplete PHI is found: " << PN << "\n"; } } while (false); | ||||
| 1212 | continue; | ||||
| 1213 | } | ||||
| 1214 | |||||
| 1215 | const SCEVAddRecExpr *PhiSCEV = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(&PN)); | ||||
| 1216 | if (!PhiSCEV) | ||||
| 1217 | continue; | ||||
| 1218 | |||||
| 1219 | bool IsMatchingSCEV = PhiSCEV == Normalized; | ||||
| 1220 | // We only handle truncation and inversion of phi recurrences for the | ||||
| 1221 | // expanded expression if the expanded expression's loop dominates the | ||||
| 1222 | // loop we insert to. Check now, so we can bail out early. | ||||
| 1223 | if (!IsMatchingSCEV && !TryNonMatchingSCEV) | ||||
| 1224 | continue; | ||||
| 1225 | |||||
| 1226 | // TODO: this possibly can be reworked to avoid this cast at all. | ||||
| 1227 | Instruction *TempIncV = | ||||
| 1228 | dyn_cast<Instruction>(PN.getIncomingValueForBlock(LatchBlock)); | ||||
| 1229 | if (!TempIncV) | ||||
| 1230 | continue; | ||||
| 1231 | |||||
| 1232 | // Check whether we can reuse this PHI node. | ||||
| 1233 | if (LSRMode) { | ||||
| 1234 | if (!isExpandedAddRecExprPHI(&PN, TempIncV, L)) | ||||
| 1235 | continue; | ||||
| 1236 | if (L == IVIncInsertLoop && !hoistIVInc(TempIncV, IVIncInsertPos)) | ||||
| 1237 | continue; | ||||
| 1238 | } else { | ||||
| 1239 | if (!isNormalAddRecExprPHI(&PN, TempIncV, L)) | ||||
| 1240 | continue; | ||||
| 1241 | } | ||||
| 1242 | |||||
| 1243 | // Stop if we have found an exact match SCEV. | ||||
| 1244 | if (IsMatchingSCEV) { | ||||
| 1245 | IncV = TempIncV; | ||||
| 1246 | TruncTy = nullptr; | ||||
| 1247 | InvertStep = false; | ||||
| 1248 | AddRecPhiMatch = &PN; | ||||
| 1249 | break; | ||||
| 1250 | } | ||||
| 1251 | |||||
| 1252 | // Try whether the phi can be translated into the requested form | ||||
| 1253 | // (truncated and/or offset by a constant). | ||||
| 1254 | if ((!TruncTy || InvertStep) && | ||||
| 1255 | canBeCheaplyTransformed(SE, PhiSCEV, Normalized, InvertStep)) { | ||||
| 1256 | // Record the phi node. But don't stop we might find an exact match | ||||
| 1257 | // later. | ||||
| 1258 | AddRecPhiMatch = &PN; | ||||
| 1259 | IncV = TempIncV; | ||||
| 1260 | TruncTy = SE.getEffectiveSCEVType(Normalized->getType()); | ||||
| 1261 | } | ||||
| 1262 | } | ||||
| 1263 | |||||
| 1264 | if (AddRecPhiMatch) { | ||||
| 1265 | // Potentially, move the increment. We have made sure in | ||||
| 1266 | // isExpandedAddRecExprPHI or hoistIVInc that this is possible. | ||||
| 1267 | if (L == IVIncInsertLoop) | ||||
| 1268 | hoistBeforePos(&SE.DT, IncV, IVIncInsertPos, AddRecPhiMatch); | ||||
| 1269 | |||||
| 1270 | // Ok, the add recurrence looks usable. | ||||
| 1271 | // Remember this PHI, even in post-inc mode. | ||||
| 1272 | InsertedValues.insert(AddRecPhiMatch); | ||||
| 1273 | // Remember the increment. | ||||
| 1274 | rememberInstruction(IncV); | ||||
| 1275 | // Those values were not actually inserted but re-used. | ||||
| 1276 | ReusedValues.insert(AddRecPhiMatch); | ||||
| 1277 | ReusedValues.insert(IncV); | ||||
| 1278 | return AddRecPhiMatch; | ||||
| 1279 | } | ||||
| 1280 | } | ||||
| 1281 | |||||
| 1282 | // Save the original insertion point so we can restore it when we're done. | ||||
| 1283 | SCEVInsertPointGuard Guard(Builder, this); | ||||
| 1284 | |||||
| 1285 | // Another AddRec may need to be recursively expanded below. For example, if | ||||
| 1286 | // this AddRec is quadratic, the StepV may itself be an AddRec in this | ||||
| 1287 | // loop. Remove this loop from the PostIncLoops set before expanding such | ||||
| 1288 | // AddRecs. Otherwise, we cannot find a valid position for the step | ||||
| 1289 | // (i.e. StepV can never dominate its loop header). Ideally, we could do | ||||
| 1290 | // SavedIncLoops.swap(PostIncLoops), but we generally have a single element, | ||||
| 1291 | // so it's not worth implementing SmallPtrSet::swap. | ||||
| 1292 | PostIncLoopSet SavedPostIncLoops = PostIncLoops; | ||||
| 1293 | PostIncLoops.clear(); | ||||
| 1294 | |||||
| 1295 | // Expand code for the start value into the loop preheader. | ||||
| 1296 | assert(L->getLoopPreheader() &&((L->getLoopPreheader() && "Can't expand add recurrences without a loop preheader!" ) ? static_cast<void> (0) : __assert_fail ("L->getLoopPreheader() && \"Can't expand add recurrences without a loop preheader!\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 1297, __PRETTY_FUNCTION__)) | ||||
| 1297 | "Can't expand add recurrences without a loop preheader!")((L->getLoopPreheader() && "Can't expand add recurrences without a loop preheader!" ) ? static_cast<void> (0) : __assert_fail ("L->getLoopPreheader() && \"Can't expand add recurrences without a loop preheader!\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 1297, __PRETTY_FUNCTION__)); | ||||
| 1298 | Value *StartV = | ||||
| 1299 | expandCodeForImpl(Normalized->getStart(), ExpandTy, | ||||
| 1300 | L->getLoopPreheader()->getTerminator(), false); | ||||
| 1301 | |||||
| 1302 | // StartV must have been be inserted into L's preheader to dominate the new | ||||
| 1303 | // phi. | ||||
| 1304 | assert(!isa<Instruction>(StartV) ||((!isa<Instruction>(StartV) || SE.DT.properlyDominates( cast<Instruction>(StartV)->getParent(), L->getHeader ())) ? static_cast<void> (0) : __assert_fail ("!isa<Instruction>(StartV) || SE.DT.properlyDominates(cast<Instruction>(StartV)->getParent(), L->getHeader())" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 1306, __PRETTY_FUNCTION__)) | ||||
| 1305 | SE.DT.properlyDominates(cast<Instruction>(StartV)->getParent(),((!isa<Instruction>(StartV) || SE.DT.properlyDominates( cast<Instruction>(StartV)->getParent(), L->getHeader ())) ? static_cast<void> (0) : __assert_fail ("!isa<Instruction>(StartV) || SE.DT.properlyDominates(cast<Instruction>(StartV)->getParent(), L->getHeader())" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 1306, __PRETTY_FUNCTION__)) | ||||
| 1306 | L->getHeader()))((!isa<Instruction>(StartV) || SE.DT.properlyDominates( cast<Instruction>(StartV)->getParent(), L->getHeader ())) ? static_cast<void> (0) : __assert_fail ("!isa<Instruction>(StartV) || SE.DT.properlyDominates(cast<Instruction>(StartV)->getParent(), L->getHeader())" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 1306, __PRETTY_FUNCTION__)); | ||||
| 1307 | |||||
| 1308 | // Expand code for the step value. Do this before creating the PHI so that PHI | ||||
| 1309 | // reuse code doesn't see an incomplete PHI. | ||||
| 1310 | const SCEV *Step = Normalized->getStepRecurrence(SE); | ||||
| 1311 | // If the stride is negative, insert a sub instead of an add for the increment | ||||
| 1312 | // (unless it's a constant, because subtracts of constants are canonicalized | ||||
| 1313 | // to adds). | ||||
| 1314 | bool useSubtract = !ExpandTy->isPointerTy() && Step->isNonConstantNegative(); | ||||
| 1315 | if (useSubtract) | ||||
| 1316 | Step = SE.getNegativeSCEV(Step); | ||||
| 1317 | // Expand the step somewhere that dominates the loop header. | ||||
| 1318 | Value *StepV = expandCodeForImpl( | ||||
| 1319 | Step, IntTy, &*L->getHeader()->getFirstInsertionPt(), false); | ||||
| 1320 | |||||
| 1321 | // The no-wrap behavior proved by IsIncrement(NUW|NSW) is only applicable if | ||||
| 1322 | // we actually do emit an addition. It does not apply if we emit a | ||||
| 1323 | // subtraction. | ||||
| 1324 | bool IncrementIsNUW = !useSubtract && IsIncrementNUW(SE, Normalized); | ||||
| 1325 | bool IncrementIsNSW = !useSubtract && IsIncrementNSW(SE, Normalized); | ||||
| 1326 | |||||
| 1327 | // Create the PHI. | ||||
| 1328 | BasicBlock *Header = L->getHeader(); | ||||
| 1329 | Builder.SetInsertPoint(Header, Header->begin()); | ||||
| 1330 | pred_iterator HPB = pred_begin(Header), HPE = pred_end(Header); | ||||
| 1331 | PHINode *PN = Builder.CreatePHI(ExpandTy, std::distance(HPB, HPE), | ||||
| 1332 | Twine(IVName) + ".iv"); | ||||
| 1333 | |||||
| 1334 | // Create the step instructions and populate the PHI. | ||||
| 1335 | for (pred_iterator HPI = HPB; HPI != HPE; ++HPI) { | ||||
| 1336 | BasicBlock *Pred = *HPI; | ||||
| 1337 | |||||
| 1338 | // Add a start value. | ||||
| 1339 | if (!L->contains(Pred)) { | ||||
| 1340 | PN->addIncoming(StartV, Pred); | ||||
| 1341 | continue; | ||||
| 1342 | } | ||||
| 1343 | |||||
| 1344 | // Create a step value and add it to the PHI. | ||||
| 1345 | // If IVIncInsertLoop is non-null and equal to the addrec's loop, insert the | ||||
| 1346 | // instructions at IVIncInsertPos. | ||||
| 1347 | Instruction *InsertPos = L == IVIncInsertLoop ? | ||||
| 1348 | IVIncInsertPos : Pred->getTerminator(); | ||||
| 1349 | Builder.SetInsertPoint(InsertPos); | ||||
| 1350 | Value *IncV = expandIVInc(PN, StepV, L, ExpandTy, IntTy, useSubtract); | ||||
| 1351 | |||||
| 1352 | if (isa<OverflowingBinaryOperator>(IncV)) { | ||||
| 1353 | if (IncrementIsNUW) | ||||
| 1354 | cast<BinaryOperator>(IncV)->setHasNoUnsignedWrap(); | ||||
| 1355 | if (IncrementIsNSW) | ||||
| 1356 | cast<BinaryOperator>(IncV)->setHasNoSignedWrap(); | ||||
| 1357 | } | ||||
| 1358 | PN->addIncoming(IncV, Pred); | ||||
| 1359 | } | ||||
| 1360 | |||||
| 1361 | // After expanding subexpressions, restore the PostIncLoops set so the caller | ||||
| 1362 | // can ensure that IVIncrement dominates the current uses. | ||||
| 1363 | PostIncLoops = SavedPostIncLoops; | ||||
| 1364 | |||||
| 1365 | // Remember this PHI, even in post-inc mode. | ||||
| 1366 | InsertedValues.insert(PN); | ||||
| 1367 | |||||
| 1368 | return PN; | ||||
| 1369 | } | ||||
| 1370 | |||||
| 1371 | Value *SCEVExpander::expandAddRecExprLiterally(const SCEVAddRecExpr *S) { | ||||
| 1372 | Type *STy = S->getType(); | ||||
| 1373 | Type *IntTy = SE.getEffectiveSCEVType(STy); | ||||
| 1374 | const Loop *L = S->getLoop(); | ||||
| 1375 | |||||
| 1376 | // Determine a normalized form of this expression, which is the expression | ||||
| 1377 | // before any post-inc adjustment is made. | ||||
| 1378 | const SCEVAddRecExpr *Normalized = S; | ||||
| 1379 | if (PostIncLoops.count(L)) { | ||||
| 1380 | PostIncLoopSet Loops; | ||||
| 1381 | Loops.insert(L); | ||||
| 1382 | Normalized = cast<SCEVAddRecExpr>(normalizeForPostIncUse(S, Loops, SE)); | ||||
| 1383 | } | ||||
| 1384 | |||||
| 1385 | // Strip off any non-loop-dominating component from the addrec start. | ||||
| 1386 | const SCEV *Start = Normalized->getStart(); | ||||
| 1387 | const SCEV *PostLoopOffset = nullptr; | ||||
| 1388 | if (!SE.properlyDominates(Start, L->getHeader())) { | ||||
| 1389 | PostLoopOffset = Start; | ||||
| 1390 | Start = SE.getConstant(Normalized->getType(), 0); | ||||
| 1391 | Normalized = cast<SCEVAddRecExpr>( | ||||
| 1392 | SE.getAddRecExpr(Start, Normalized->getStepRecurrence(SE), | ||||
| 1393 | Normalized->getLoop(), | ||||
| 1394 | Normalized->getNoWrapFlags(SCEV::FlagNW))); | ||||
| 1395 | } | ||||
| 1396 | |||||
| 1397 | // Strip off any non-loop-dominating component from the addrec step. | ||||
| 1398 | const SCEV *Step = Normalized->getStepRecurrence(SE); | ||||
| 1399 | const SCEV *PostLoopScale = nullptr; | ||||
| 1400 | if (!SE.dominates(Step, L->getHeader())) { | ||||
| 1401 | PostLoopScale = Step; | ||||
| 1402 | Step = SE.getConstant(Normalized->getType(), 1); | ||||
| 1403 | if (!Start->isZero()) { | ||||
| 1404 | // The normalization below assumes that Start is constant zero, so if | ||||
| 1405 | // it isn't re-associate Start to PostLoopOffset. | ||||
| 1406 | assert(!PostLoopOffset && "Start not-null but PostLoopOffset set?")((!PostLoopOffset && "Start not-null but PostLoopOffset set?" ) ? static_cast<void> (0) : __assert_fail ("!PostLoopOffset && \"Start not-null but PostLoopOffset set?\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 1406, __PRETTY_FUNCTION__)); | ||||
| 1407 | PostLoopOffset = Start; | ||||
| 1408 | Start = SE.getConstant(Normalized->getType(), 0); | ||||
| 1409 | } | ||||
| 1410 | Normalized = | ||||
| 1411 | cast<SCEVAddRecExpr>(SE.getAddRecExpr( | ||||
| 1412 | Start, Step, Normalized->getLoop(), | ||||
| 1413 | Normalized->getNoWrapFlags(SCEV::FlagNW))); | ||||
| 1414 | } | ||||
| 1415 | |||||
| 1416 | // Expand the core addrec. If we need post-loop scaling, force it to | ||||
| 1417 | // expand to an integer type to avoid the need for additional casting. | ||||
| 1418 | Type *ExpandTy = PostLoopScale ? IntTy : STy; | ||||
| 1419 | // We can't use a pointer type for the addrec if the pointer type is | ||||
| 1420 | // non-integral. | ||||
| 1421 | Type *AddRecPHIExpandTy = | ||||
| 1422 | DL.isNonIntegralPointerType(STy) ? Normalized->getType() : ExpandTy; | ||||
| 1423 | |||||
| 1424 | // In some cases, we decide to reuse an existing phi node but need to truncate | ||||
| 1425 | // it and/or invert the step. | ||||
| 1426 | Type *TruncTy = nullptr; | ||||
| 1427 | bool InvertStep = false; | ||||
| 1428 | PHINode *PN = getAddRecExprPHILiterally(Normalized, L, AddRecPHIExpandTy, | ||||
| 1429 | IntTy, TruncTy, InvertStep); | ||||
| 1430 | |||||
| 1431 | // Accommodate post-inc mode, if necessary. | ||||
| 1432 | Value *Result; | ||||
| 1433 | if (!PostIncLoops.count(L)) | ||||
| 1434 | Result = PN; | ||||
| 1435 | else { | ||||
| 1436 | // In PostInc mode, use the post-incremented value. | ||||
| 1437 | BasicBlock *LatchBlock = L->getLoopLatch(); | ||||
| 1438 | assert(LatchBlock && "PostInc mode requires a unique loop latch!")((LatchBlock && "PostInc mode requires a unique loop latch!" ) ? static_cast<void> (0) : __assert_fail ("LatchBlock && \"PostInc mode requires a unique loop latch!\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 1438, __PRETTY_FUNCTION__)); | ||||
| 1439 | Result = PN->getIncomingValueForBlock(LatchBlock); | ||||
| 1440 | |||||
| 1441 | // For an expansion to use the postinc form, the client must call | ||||
| 1442 | // expandCodeFor with an InsertPoint that is either outside the PostIncLoop | ||||
| 1443 | // or dominated by IVIncInsertPos. | ||||
| 1444 | if (isa<Instruction>(Result) && | ||||
| 1445 | !SE.DT.dominates(cast<Instruction>(Result), | ||||
| 1446 | &*Builder.GetInsertPoint())) { | ||||
| 1447 | // The induction variable's postinc expansion does not dominate this use. | ||||
| 1448 | // IVUsers tries to prevent this case, so it is rare. However, it can | ||||
| 1449 | // happen when an IVUser outside the loop is not dominated by the latch | ||||
| 1450 | // block. Adjusting IVIncInsertPos before expansion begins cannot handle | ||||
| 1451 | // all cases. Consider a phi outside whose operand is replaced during | ||||
| 1452 | // expansion with the value of the postinc user. Without fundamentally | ||||
| 1453 | // changing the way postinc users are tracked, the only remedy is | ||||
| 1454 | // inserting an extra IV increment. StepV might fold into PostLoopOffset, | ||||
| 1455 | // but hopefully expandCodeFor handles that. | ||||
| 1456 | bool useSubtract = | ||||
| 1457 | !ExpandTy->isPointerTy() && Step->isNonConstantNegative(); | ||||
| 1458 | if (useSubtract) | ||||
| 1459 | Step = SE.getNegativeSCEV(Step); | ||||
| 1460 | Value *StepV; | ||||
| 1461 | { | ||||
| 1462 | // Expand the step somewhere that dominates the loop header. | ||||
| 1463 | SCEVInsertPointGuard Guard(Builder, this); | ||||
| 1464 | StepV = expandCodeForImpl( | ||||
| 1465 | Step, IntTy, &*L->getHeader()->getFirstInsertionPt(), false); | ||||
| 1466 | } | ||||
| 1467 | Result = expandIVInc(PN, StepV, L, ExpandTy, IntTy, useSubtract); | ||||
| 1468 | } | ||||
| 1469 | } | ||||
| 1470 | |||||
| 1471 | // We have decided to reuse an induction variable of a dominating loop. Apply | ||||
| 1472 | // truncation and/or inversion of the step. | ||||
| 1473 | if (TruncTy) { | ||||
| 1474 | Type *ResTy = Result->getType(); | ||||
| 1475 | // Normalize the result type. | ||||
| 1476 | if (ResTy != SE.getEffectiveSCEVType(ResTy)) | ||||
| 1477 | Result = InsertNoopCastOfTo(Result, SE.getEffectiveSCEVType(ResTy)); | ||||
| 1478 | // Truncate the result. | ||||
| 1479 | if (TruncTy != Result->getType()) | ||||
| 1480 | Result = Builder.CreateTrunc(Result, TruncTy); | ||||
| 1481 | |||||
| 1482 | // Invert the result. | ||||
| 1483 | if (InvertStep) | ||||
| 1484 | Result = Builder.CreateSub( | ||||
| 1485 | expandCodeForImpl(Normalized->getStart(), TruncTy, false), Result); | ||||
| 1486 | } | ||||
| 1487 | |||||
| 1488 | // Re-apply any non-loop-dominating scale. | ||||
| 1489 | if (PostLoopScale) { | ||||
| 1490 | assert(S->isAffine() && "Can't linearly scale non-affine recurrences.")((S->isAffine() && "Can't linearly scale non-affine recurrences." ) ? static_cast<void> (0) : __assert_fail ("S->isAffine() && \"Can't linearly scale non-affine recurrences.\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 1490, __PRETTY_FUNCTION__)); | ||||
| 1491 | Result = InsertNoopCastOfTo(Result, IntTy); | ||||
| 1492 | Result = Builder.CreateMul(Result, | ||||
| 1493 | expandCodeForImpl(PostLoopScale, IntTy, false)); | ||||
| 1494 | } | ||||
| 1495 | |||||
| 1496 | // Re-apply any non-loop-dominating offset. | ||||
| 1497 | if (PostLoopOffset) { | ||||
| 1498 | if (PointerType *PTy = dyn_cast<PointerType>(ExpandTy)) { | ||||
| 1499 | if (Result->getType()->isIntegerTy()) { | ||||
| 1500 | Value *Base = expandCodeForImpl(PostLoopOffset, ExpandTy, false); | ||||
| 1501 | Result = expandAddToGEP(SE.getUnknown(Result), PTy, IntTy, Base); | ||||
| 1502 | } else { | ||||
| 1503 | Result = expandAddToGEP(PostLoopOffset, PTy, IntTy, Result); | ||||
| 1504 | } | ||||
| 1505 | } else { | ||||
| 1506 | Result = InsertNoopCastOfTo(Result, IntTy); | ||||
| 1507 | Result = Builder.CreateAdd( | ||||
| 1508 | Result, expandCodeForImpl(PostLoopOffset, IntTy, false)); | ||||
| 1509 | } | ||||
| 1510 | } | ||||
| 1511 | |||||
| 1512 | return Result; | ||||
| 1513 | } | ||||
| 1514 | |||||
| 1515 | Value *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) { | ||||
| 1516 | // In canonical mode we compute the addrec as an expression of a canonical IV | ||||
| 1517 | // using evaluateAtIteration and expand the resulting SCEV expression. This | ||||
| 1518 | // way we avoid introducing new IVs to carry on the comutation of the addrec | ||||
| 1519 | // throughout the loop. | ||||
| 1520 | // | ||||
| 1521 | // For nested addrecs evaluateAtIteration might need a canonical IV of a | ||||
| 1522 | // type wider than the addrec itself. Emitting a canonical IV of the | ||||
| 1523 | // proper type might produce non-legal types, for example expanding an i64 | ||||
| 1524 | // {0,+,2,+,1} addrec would need an i65 canonical IV. To avoid this just fall | ||||
| 1525 | // back to non-canonical mode for nested addrecs. | ||||
| 1526 | if (!CanonicalMode || (S->getNumOperands() > 2)) | ||||
| 1527 | return expandAddRecExprLiterally(S); | ||||
| 1528 | |||||
| 1529 | Type *Ty = SE.getEffectiveSCEVType(S->getType()); | ||||
| 1530 | const Loop *L = S->getLoop(); | ||||
| 1531 | |||||
| 1532 | // First check for an existing canonical IV in a suitable type. | ||||
| 1533 | PHINode *CanonicalIV = nullptr; | ||||
| 1534 | if (PHINode *PN = L->getCanonicalInductionVariable()) | ||||
| 1535 | if (SE.getTypeSizeInBits(PN->getType()) >= SE.getTypeSizeInBits(Ty)) | ||||
| 1536 | CanonicalIV = PN; | ||||
| 1537 | |||||
| 1538 | // Rewrite an AddRec in terms of the canonical induction variable, if | ||||
| 1539 | // its type is more narrow. | ||||
| 1540 | if (CanonicalIV && | ||||
| 1541 | SE.getTypeSizeInBits(CanonicalIV->getType()) > | ||||
| 1542 | SE.getTypeSizeInBits(Ty)) { | ||||
| 1543 | SmallVector<const SCEV *, 4> NewOps(S->getNumOperands()); | ||||
| 1544 | for (unsigned i = 0, e = S->getNumOperands(); i != e; ++i) | ||||
| 1545 | NewOps[i] = SE.getAnyExtendExpr(S->op_begin()[i], CanonicalIV->getType()); | ||||
| 1546 | Value *V = expand(SE.getAddRecExpr(NewOps, S->getLoop(), | ||||
| 1547 | S->getNoWrapFlags(SCEV::FlagNW))); | ||||
| 1548 | BasicBlock::iterator NewInsertPt = | ||||
| 1549 | findInsertPointAfter(cast<Instruction>(V), &*Builder.GetInsertPoint()); | ||||
| 1550 | V = expandCodeForImpl(SE.getTruncateExpr(SE.getUnknown(V), Ty), nullptr, | ||||
| 1551 | &*NewInsertPt, false); | ||||
| 1552 | return V; | ||||
| 1553 | } | ||||
| 1554 | |||||
| 1555 | // {X,+,F} --> X + {0,+,F} | ||||
| 1556 | if (!S->getStart()->isZero()) { | ||||
| 1557 | SmallVector<const SCEV *, 4> NewOps(S->op_begin(), S->op_end()); | ||||
| 1558 | NewOps[0] = SE.getConstant(Ty, 0); | ||||
| 1559 | const SCEV *Rest = SE.getAddRecExpr(NewOps, L, | ||||
| 1560 | S->getNoWrapFlags(SCEV::FlagNW)); | ||||
| 1561 | |||||
| 1562 | // Turn things like ptrtoint+arithmetic+inttoptr into GEP. See the | ||||
| 1563 | // comments on expandAddToGEP for details. | ||||
| 1564 | const SCEV *Base = S->getStart(); | ||||
| 1565 | // Dig into the expression to find the pointer base for a GEP. | ||||
| 1566 | const SCEV *ExposedRest = Rest; | ||||
| 1567 | ExposePointerBase(Base, ExposedRest, SE); | ||||
| 1568 | // If we found a pointer, expand the AddRec with a GEP. | ||||
| 1569 | if (PointerType *PTy = dyn_cast<PointerType>(Base->getType())) { | ||||
| 1570 | // Make sure the Base isn't something exotic, such as a multiplied | ||||
| 1571 | // or divided pointer value. In those cases, the result type isn't | ||||
| 1572 | // actually a pointer type. | ||||
| 1573 | if (!isa<SCEVMulExpr>(Base) && !isa<SCEVUDivExpr>(Base)) { | ||||
| 1574 | Value *StartV = expand(Base); | ||||
| 1575 | assert(StartV->getType() == PTy && "Pointer type mismatch for GEP!")((StartV->getType() == PTy && "Pointer type mismatch for GEP!" ) ? static_cast<void> (0) : __assert_fail ("StartV->getType() == PTy && \"Pointer type mismatch for GEP!\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 1575, __PRETTY_FUNCTION__)); | ||||
| 1576 | return expandAddToGEP(ExposedRest, PTy, Ty, StartV); | ||||
| 1577 | } | ||||
| 1578 | } | ||||
| 1579 | |||||
| 1580 | // Just do a normal add. Pre-expand the operands to suppress folding. | ||||
| 1581 | // | ||||
| 1582 | // The LHS and RHS values are factored out of the expand call to make the | ||||
| 1583 | // output independent of the argument evaluation order. | ||||
| 1584 | const SCEV *AddExprLHS = SE.getUnknown(expand(S->getStart())); | ||||
| 1585 | const SCEV *AddExprRHS = SE.getUnknown(expand(Rest)); | ||||
| 1586 | return expand(SE.getAddExpr(AddExprLHS, AddExprRHS)); | ||||
| 1587 | } | ||||
| 1588 | |||||
| 1589 | // If we don't yet have a canonical IV, create one. | ||||
| 1590 | if (!CanonicalIV) { | ||||
| 1591 | // Create and insert the PHI node for the induction variable in the | ||||
| 1592 | // specified loop. | ||||
| 1593 | BasicBlock *Header = L->getHeader(); | ||||
| 1594 | pred_iterator HPB = pred_begin(Header), HPE = pred_end(Header); | ||||
| 1595 | CanonicalIV = PHINode::Create(Ty, std::distance(HPB, HPE), "indvar", | ||||
| 1596 | &Header->front()); | ||||
| 1597 | rememberInstruction(CanonicalIV); | ||||
| 1598 | |||||
| 1599 | SmallSet<BasicBlock *, 4> PredSeen; | ||||
| 1600 | Constant *One = ConstantInt::get(Ty, 1); | ||||
| 1601 | for (pred_iterator HPI = HPB; HPI != HPE; ++HPI) { | ||||
| 1602 | BasicBlock *HP = *HPI; | ||||
| 1603 | if (!PredSeen.insert(HP).second) { | ||||
| 1604 | // There must be an incoming value for each predecessor, even the | ||||
| 1605 | // duplicates! | ||||
| 1606 | CanonicalIV->addIncoming(CanonicalIV->getIncomingValueForBlock(HP), HP); | ||||
| 1607 | continue; | ||||
| 1608 | } | ||||
| 1609 | |||||
| 1610 | if (L->contains(HP)) { | ||||
| 1611 | // Insert a unit add instruction right before the terminator | ||||
| 1612 | // corresponding to the back-edge. | ||||
| 1613 | Instruction *Add = BinaryOperator::CreateAdd(CanonicalIV, One, | ||||
| 1614 | "indvar.next", | ||||
| 1615 | HP->getTerminator()); | ||||
| 1616 | Add->setDebugLoc(HP->getTerminator()->getDebugLoc()); | ||||
| 1617 | rememberInstruction(Add); | ||||
| 1618 | CanonicalIV->addIncoming(Add, HP); | ||||
| 1619 | } else { | ||||
| 1620 | CanonicalIV->addIncoming(Constant::getNullValue(Ty), HP); | ||||
| 1621 | } | ||||
| 1622 | } | ||||
| 1623 | } | ||||
| 1624 | |||||
| 1625 | // {0,+,1} --> Insert a canonical induction variable into the loop! | ||||
| 1626 | if (S->isAffine() && S->getOperand(1)->isOne()) { | ||||
| 1627 | assert(Ty == SE.getEffectiveSCEVType(CanonicalIV->getType()) &&((Ty == SE.getEffectiveSCEVType(CanonicalIV->getType()) && "IVs with types different from the canonical IV should " "already have been handled!" ) ? static_cast<void> (0) : __assert_fail ("Ty == SE.getEffectiveSCEVType(CanonicalIV->getType()) && \"IVs with types different from the canonical IV should \" \"already have been handled!\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 1629, __PRETTY_FUNCTION__)) | ||||
| 1628 | "IVs with types different from the canonical IV should "((Ty == SE.getEffectiveSCEVType(CanonicalIV->getType()) && "IVs with types different from the canonical IV should " "already have been handled!" ) ? static_cast<void> (0) : __assert_fail ("Ty == SE.getEffectiveSCEVType(CanonicalIV->getType()) && \"IVs with types different from the canonical IV should \" \"already have been handled!\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 1629, __PRETTY_FUNCTION__)) | ||||
| 1629 | "already have been handled!")((Ty == SE.getEffectiveSCEVType(CanonicalIV->getType()) && "IVs with types different from the canonical IV should " "already have been handled!" ) ? static_cast<void> (0) : __assert_fail ("Ty == SE.getEffectiveSCEVType(CanonicalIV->getType()) && \"IVs with types different from the canonical IV should \" \"already have been handled!\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 1629, __PRETTY_FUNCTION__)); | ||||
| 1630 | return CanonicalIV; | ||||
| 1631 | } | ||||
| 1632 | |||||
| 1633 | // {0,+,F} --> {0,+,1} * F | ||||
| 1634 | |||||
| 1635 | // If this is a simple linear addrec, emit it now as a special case. | ||||
| 1636 | if (S->isAffine()) // {0,+,F} --> i*F | ||||
| 1637 | return | ||||
| 1638 | expand(SE.getTruncateOrNoop( | ||||
| 1639 | SE.getMulExpr(SE.getUnknown(CanonicalIV), | ||||
| 1640 | SE.getNoopOrAnyExtend(S->getOperand(1), | ||||
| 1641 | CanonicalIV->getType())), | ||||
| 1642 | Ty)); | ||||
| 1643 | |||||
| 1644 | // If this is a chain of recurrences, turn it into a closed form, using the | ||||
| 1645 | // folders, then expandCodeFor the closed form. This allows the folders to | ||||
| 1646 | // simplify the expression without having to build a bunch of special code | ||||
| 1647 | // into this folder. | ||||
| 1648 | const SCEV *IH = SE.getUnknown(CanonicalIV); // Get I as a "symbolic" SCEV. | ||||
| 1649 | |||||
| 1650 | // Promote S up to the canonical IV type, if the cast is foldable. | ||||
| 1651 | const SCEV *NewS = S; | ||||
| 1652 | const SCEV *Ext = SE.getNoopOrAnyExtend(S, CanonicalIV->getType()); | ||||
| 1653 | if (isa<SCEVAddRecExpr>(Ext)) | ||||
| 1654 | NewS = Ext; | ||||
| 1655 | |||||
| 1656 | const SCEV *V = cast<SCEVAddRecExpr>(NewS)->evaluateAtIteration(IH, SE); | ||||
| 1657 | //cerr << "Evaluated: " << *this << "\n to: " << *V << "\n"; | ||||
| 1658 | |||||
| 1659 | // Truncate the result down to the original type, if needed. | ||||
| 1660 | const SCEV *T = SE.getTruncateOrNoop(V, Ty); | ||||
| 1661 | return expand(T); | ||||
| 1662 | } | ||||
| 1663 | |||||
| 1664 | Value *SCEVExpander::visitTruncateExpr(const SCEVTruncateExpr *S) { | ||||
| 1665 | Type *Ty = SE.getEffectiveSCEVType(S->getType()); | ||||
| 1666 | Value *V = expandCodeForImpl( | ||||
| 1667 | S->getOperand(), SE.getEffectiveSCEVType(S->getOperand()->getType()), | ||||
| 1668 | false); | ||||
| 1669 | return Builder.CreateTrunc(V, Ty); | ||||
| 1670 | } | ||||
| 1671 | |||||
| 1672 | Value *SCEVExpander::visitZeroExtendExpr(const SCEVZeroExtendExpr *S) { | ||||
| 1673 | Type *Ty = SE.getEffectiveSCEVType(S->getType()); | ||||
| 1674 | Value *V = expandCodeForImpl( | ||||
| 1675 | S->getOperand(), SE.getEffectiveSCEVType(S->getOperand()->getType()), | ||||
| 1676 | false); | ||||
| 1677 | return Builder.CreateZExt(V, Ty); | ||||
| 1678 | } | ||||
| 1679 | |||||
| 1680 | Value *SCEVExpander::visitSignExtendExpr(const SCEVSignExtendExpr *S) { | ||||
| 1681 | Type *Ty = SE.getEffectiveSCEVType(S->getType()); | ||||
| 1682 | Value *V = expandCodeForImpl( | ||||
| 1683 | S->getOperand(), SE.getEffectiveSCEVType(S->getOperand()->getType()), | ||||
| 1684 | false); | ||||
| 1685 | return Builder.CreateSExt(V, Ty); | ||||
| 1686 | } | ||||
| 1687 | |||||
| 1688 | Value *SCEVExpander::visitSMaxExpr(const SCEVSMaxExpr *S) { | ||||
| 1689 | Value *LHS = expand(S->getOperand(S->getNumOperands()-1)); | ||||
| 1690 | Type *Ty = LHS->getType(); | ||||
| 1691 | for (int i = S->getNumOperands()-2; i >= 0; --i) { | ||||
| 1692 | // In the case of mixed integer and pointer types, do the | ||||
| 1693 | // rest of the comparisons as integer. | ||||
| 1694 | Type *OpTy = S->getOperand(i)->getType(); | ||||
| 1695 | if (OpTy->isIntegerTy() != Ty->isIntegerTy()) { | ||||
| 1696 | Ty = SE.getEffectiveSCEVType(Ty); | ||||
| 1697 | LHS = InsertNoopCastOfTo(LHS, Ty); | ||||
| 1698 | } | ||||
| 1699 | Value *RHS = expandCodeForImpl(S->getOperand(i), Ty, false); | ||||
| 1700 | Value *ICmp = Builder.CreateICmpSGT(LHS, RHS); | ||||
| 1701 | Value *Sel = Builder.CreateSelect(ICmp, LHS, RHS, "smax"); | ||||
| 1702 | LHS = Sel; | ||||
| 1703 | } | ||||
| 1704 | // In the case of mixed integer and pointer types, cast the | ||||
| 1705 | // final result back to the pointer type. | ||||
| 1706 | if (LHS->getType() != S->getType()) | ||||
| 1707 | LHS = InsertNoopCastOfTo(LHS, S->getType()); | ||||
| 1708 | return LHS; | ||||
| 1709 | } | ||||
| 1710 | |||||
| 1711 | Value *SCEVExpander::visitUMaxExpr(const SCEVUMaxExpr *S) { | ||||
| 1712 | Value *LHS = expand(S->getOperand(S->getNumOperands()-1)); | ||||
| 1713 | Type *Ty = LHS->getType(); | ||||
| 1714 | for (int i = S->getNumOperands()-2; i >= 0; --i) { | ||||
| 1715 | // In the case of mixed integer and pointer types, do the | ||||
| 1716 | // rest of the comparisons as integer. | ||||
| 1717 | Type *OpTy = S->getOperand(i)->getType(); | ||||
| 1718 | if (OpTy->isIntegerTy() != Ty->isIntegerTy()) { | ||||
| 1719 | Ty = SE.getEffectiveSCEVType(Ty); | ||||
| 1720 | LHS = InsertNoopCastOfTo(LHS, Ty); | ||||
| 1721 | } | ||||
| 1722 | Value *RHS = expandCodeForImpl(S->getOperand(i), Ty, false); | ||||
| 1723 | Value *ICmp = Builder.CreateICmpUGT(LHS, RHS); | ||||
| 1724 | Value *Sel = Builder.CreateSelect(ICmp, LHS, RHS, "umax"); | ||||
| 1725 | LHS = Sel; | ||||
| 1726 | } | ||||
| 1727 | // In the case of mixed integer and pointer types, cast the | ||||
| 1728 | // final result back to the pointer type. | ||||
| 1729 | if (LHS->getType() != S->getType()) | ||||
| 1730 | LHS = InsertNoopCastOfTo(LHS, S->getType()); | ||||
| 1731 | return LHS; | ||||
| 1732 | } | ||||
| 1733 | |||||
| 1734 | Value *SCEVExpander::visitSMinExpr(const SCEVSMinExpr *S) { | ||||
| 1735 | Value *LHS = expand(S->getOperand(S->getNumOperands() - 1)); | ||||
| 1736 | Type *Ty = LHS->getType(); | ||||
| 1737 | for (int i = S->getNumOperands() - 2; i >= 0; --i) { | ||||
| 1738 | // In the case of mixed integer and pointer types, do the | ||||
| 1739 | // rest of the comparisons as integer. | ||||
| 1740 | Type *OpTy = S->getOperand(i)->getType(); | ||||
| 1741 | if (OpTy->isIntegerTy() != Ty->isIntegerTy()) { | ||||
| 1742 | Ty = SE.getEffectiveSCEVType(Ty); | ||||
| 1743 | LHS = InsertNoopCastOfTo(LHS, Ty); | ||||
| 1744 | } | ||||
| 1745 | Value *RHS = expandCodeForImpl(S->getOperand(i), Ty, false); | ||||
| 1746 | Value *ICmp = Builder.CreateICmpSLT(LHS, RHS); | ||||
| 1747 | Value *Sel = Builder.CreateSelect(ICmp, LHS, RHS, "smin"); | ||||
| 1748 | LHS = Sel; | ||||
| 1749 | } | ||||
| 1750 | // In the case of mixed integer and pointer types, cast the | ||||
| 1751 | // final result back to the pointer type. | ||||
| 1752 | if (LHS->getType() != S->getType()) | ||||
| 1753 | LHS = InsertNoopCastOfTo(LHS, S->getType()); | ||||
| 1754 | return LHS; | ||||
| 1755 | } | ||||
| 1756 | |||||
| 1757 | Value *SCEVExpander::visitUMinExpr(const SCEVUMinExpr *S) { | ||||
| 1758 | Value *LHS = expand(S->getOperand(S->getNumOperands() - 1)); | ||||
| 1759 | Type *Ty = LHS->getType(); | ||||
| 1760 | for (int i = S->getNumOperands() - 2; i >= 0; --i) { | ||||
| 1761 | // In the case of mixed integer and pointer types, do the | ||||
| 1762 | // rest of the comparisons as integer. | ||||
| 1763 | Type *OpTy = S->getOperand(i)->getType(); | ||||
| 1764 | if (OpTy->isIntegerTy() != Ty->isIntegerTy()) { | ||||
| 1765 | Ty = SE.getEffectiveSCEVType(Ty); | ||||
| 1766 | LHS = InsertNoopCastOfTo(LHS, Ty); | ||||
| 1767 | } | ||||
| 1768 | Value *RHS = expandCodeForImpl(S->getOperand(i), Ty, false); | ||||
| 1769 | Value *ICmp = Builder.CreateICmpULT(LHS, RHS); | ||||
| 1770 | Value *Sel = Builder.CreateSelect(ICmp, LHS, RHS, "umin"); | ||||
| 1771 | LHS = Sel; | ||||
| 1772 | } | ||||
| 1773 | // In the case of mixed integer and pointer types, cast the | ||||
| 1774 | // final result back to the pointer type. | ||||
| 1775 | if (LHS->getType() != S->getType()) | ||||
| 1776 | LHS = InsertNoopCastOfTo(LHS, S->getType()); | ||||
| 1777 | return LHS; | ||||
| 1778 | } | ||||
| 1779 | |||||
| 1780 | Value *SCEVExpander::expandCodeForImpl(const SCEV *SH, Type *Ty, | ||||
| 1781 | Instruction *IP, bool Root) { | ||||
| 1782 | setInsertPoint(IP); | ||||
| 1783 | Value *V = expandCodeForImpl(SH, Ty, Root); | ||||
| 1784 | return V; | ||||
| 1785 | } | ||||
| 1786 | |||||
| 1787 | Value *SCEVExpander::expandCodeForImpl(const SCEV *SH, Type *Ty, bool Root) { | ||||
| 1788 | // Expand the code for this SCEV. | ||||
| 1789 | Value *V = expand(SH); | ||||
| 1790 | |||||
| 1791 | if (PreserveLCSSA) { | ||||
| 1792 | if (auto *Inst = dyn_cast<Instruction>(V)) { | ||||
| 1793 | // Create a temporary instruction to at the current insertion point, so we | ||||
| 1794 | // can hand it off to the helper to create LCSSA PHIs if required for the | ||||
| 1795 | // new use. | ||||
| 1796 | // FIXME: Ideally formLCSSAForInstructions (used in fixupLCSSAFormFor) | ||||
| 1797 | // would accept a insertion point and return an LCSSA phi for that | ||||
| 1798 | // insertion point, so there is no need to insert & remove the temporary | ||||
| 1799 | // instruction. | ||||
| 1800 | Instruction *Tmp; | ||||
| 1801 | if (Inst->getType()->isIntegerTy()) | ||||
| 1802 | Tmp = | ||||
| 1803 | cast<Instruction>(Builder.CreateAdd(Inst, Inst, "tmp.lcssa.user")); | ||||
| 1804 | else { | ||||
| 1805 | assert(Inst->getType()->isPointerTy())((Inst->getType()->isPointerTy()) ? static_cast<void > (0) : __assert_fail ("Inst->getType()->isPointerTy()" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 1805, __PRETTY_FUNCTION__)); | ||||
| 1806 | Tmp = cast<Instruction>( | ||||
| 1807 | Builder.CreateGEP(Inst, Builder.getInt32(1), "tmp.lcssa.user")); | ||||
| 1808 | } | ||||
| 1809 | V = fixupLCSSAFormFor(Tmp, 0); | ||||
| 1810 | |||||
| 1811 | // Clean up temporary instruction. | ||||
| 1812 | InsertedValues.erase(Tmp); | ||||
| 1813 | InsertedPostIncValues.erase(Tmp); | ||||
| 1814 | Tmp->eraseFromParent(); | ||||
| 1815 | } | ||||
| 1816 | } | ||||
| 1817 | |||||
| 1818 | InsertedExpressions[std::make_pair(SH, &*Builder.GetInsertPoint())] = V; | ||||
| 1819 | if (Ty) { | ||||
| 1820 | assert(SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(SH->getType()) &&((SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(SH->getType ()) && "non-trivial casts should be done with the SCEVs directly!" ) ? static_cast<void> (0) : __assert_fail ("SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(SH->getType()) && \"non-trivial casts should be done with the SCEVs directly!\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 1821, __PRETTY_FUNCTION__)) | ||||
| 1821 | "non-trivial casts should be done with the SCEVs directly!")((SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(SH->getType ()) && "non-trivial casts should be done with the SCEVs directly!" ) ? static_cast<void> (0) : __assert_fail ("SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(SH->getType()) && \"non-trivial casts should be done with the SCEVs directly!\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 1821, __PRETTY_FUNCTION__)); | ||||
| 1822 | V = InsertNoopCastOfTo(V, Ty); | ||||
| 1823 | } | ||||
| 1824 | return V; | ||||
| 1825 | } | ||||
| 1826 | |||||
| 1827 | ScalarEvolution::ValueOffsetPair | ||||
| 1828 | SCEVExpander::FindValueInExprValueMap(const SCEV *S, | ||||
| 1829 | const Instruction *InsertPt) { | ||||
| 1830 | SetVector<ScalarEvolution::ValueOffsetPair> *Set = SE.getSCEVValues(S); | ||||
| 1831 | // If the expansion is not in CanonicalMode, and the SCEV contains any | ||||
| 1832 | // sub scAddRecExpr type SCEV, it is required to expand the SCEV literally. | ||||
| 1833 | if (CanonicalMode || !SE.containsAddRecurrence(S)) { | ||||
| 1834 | // If S is scConstant, it may be worse to reuse an existing Value. | ||||
| 1835 | if (S->getSCEVType() != scConstant && Set) { | ||||
| 1836 | // Choose a Value from the set which dominates the insertPt. | ||||
| 1837 | // insertPt should be inside the Value's parent loop so as not to break | ||||
| 1838 | // the LCSSA form. | ||||
| 1839 | for (auto const &VOPair : *Set) { | ||||
| 1840 | Value *V = VOPair.first; | ||||
| 1841 | ConstantInt *Offset = VOPair.second; | ||||
| 1842 | Instruction *EntInst = nullptr; | ||||
| 1843 | if (V && isa<Instruction>(V) && (EntInst = cast<Instruction>(V)) && | ||||
| 1844 | S->getType() == V->getType() && | ||||
| 1845 | EntInst->getFunction() == InsertPt->getFunction() && | ||||
| 1846 | SE.DT.dominates(EntInst, InsertPt) && | ||||
| 1847 | (SE.LI.getLoopFor(EntInst->getParent()) == nullptr || | ||||
| 1848 | SE.LI.getLoopFor(EntInst->getParent())->contains(InsertPt))) | ||||
| 1849 | return {V, Offset}; | ||||
| 1850 | } | ||||
| 1851 | } | ||||
| 1852 | } | ||||
| 1853 | return {nullptr, nullptr}; | ||||
| 1854 | } | ||||
| 1855 | |||||
| 1856 | // The expansion of SCEV will either reuse a previous Value in ExprValueMap, | ||||
| 1857 | // or expand the SCEV literally. Specifically, if the expansion is in LSRMode, | ||||
| 1858 | // and the SCEV contains any sub scAddRecExpr type SCEV, it will be expanded | ||||
| 1859 | // literally, to prevent LSR's transformed SCEV from being reverted. Otherwise, | ||||
| 1860 | // the expansion will try to reuse Value from ExprValueMap, and only when it | ||||
| 1861 | // fails, expand the SCEV literally. | ||||
| 1862 | Value *SCEVExpander::expand(const SCEV *S) { | ||||
| 1863 | // Compute an insertion point for this SCEV object. Hoist the instructions | ||||
| 1864 | // as far out in the loop nest as possible. | ||||
| 1865 | Instruction *InsertPt = &*Builder.GetInsertPoint(); | ||||
| 1866 | |||||
| 1867 | // We can move insertion point only if there is no div or rem operations | ||||
| 1868 | // otherwise we are risky to move it over the check for zero denominator. | ||||
| 1869 | auto SafeToHoist = [](const SCEV *S) { | ||||
| 1870 | return !SCEVExprContains(S, [](const SCEV *S) { | ||||
| 1871 | if (const auto *D = dyn_cast<SCEVUDivExpr>(S)) { | ||||
| 1872 | if (const auto *SC = dyn_cast<SCEVConstant>(D->getRHS())) | ||||
| 1873 | // Division by non-zero constants can be hoisted. | ||||
| 1874 | return SC->getValue()->isZero(); | ||||
| 1875 | // All other divisions should not be moved as they may be | ||||
| 1876 | // divisions by zero and should be kept within the | ||||
| 1877 | // conditions of the surrounding loops that guard their | ||||
| 1878 | // execution (see PR35406). | ||||
| 1879 | return true; | ||||
| 1880 | } | ||||
| 1881 | return false; | ||||
| 1882 | }); | ||||
| 1883 | }; | ||||
| 1884 | if (SafeToHoist(S)) { | ||||
| 1885 | for (Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock());; | ||||
| 1886 | L = L->getParentLoop()) { | ||||
| 1887 | if (SE.isLoopInvariant(S, L)) { | ||||
| 1888 | if (!L) break; | ||||
| 1889 | if (BasicBlock *Preheader = L->getLoopPreheader()) | ||||
| 1890 | InsertPt = Preheader->getTerminator(); | ||||
| 1891 | else | ||||
| 1892 | // LSR sets the insertion point for AddRec start/step values to the | ||||
| 1893 | // block start to simplify value reuse, even though it's an invalid | ||||
| 1894 | // position. SCEVExpander must correct for this in all cases. | ||||
| 1895 | InsertPt = &*L->getHeader()->getFirstInsertionPt(); | ||||
| 1896 | } else { | ||||
| 1897 | // If the SCEV is computable at this level, insert it into the header | ||||
| 1898 | // after the PHIs (and after any other instructions that we've inserted | ||||
| 1899 | // there) so that it is guaranteed to dominate any user inside the loop. | ||||
| 1900 | if (L && SE.hasComputableLoopEvolution(S, L) && !PostIncLoops.count(L)) | ||||
| 1901 | InsertPt = &*L->getHeader()->getFirstInsertionPt(); | ||||
| 1902 | |||||
| 1903 | while (InsertPt->getIterator() != Builder.GetInsertPoint() && | ||||
| 1904 | (isInsertedInstruction(InsertPt) || | ||||
| 1905 | isa<DbgInfoIntrinsic>(InsertPt))) { | ||||
| 1906 | InsertPt = &*std::next(InsertPt->getIterator()); | ||||
| 1907 | } | ||||
| 1908 | break; | ||||
| 1909 | } | ||||
| 1910 | } | ||||
| 1911 | } | ||||
| 1912 | |||||
| 1913 | // Check to see if we already expanded this here. | ||||
| 1914 | auto I = InsertedExpressions.find(std::make_pair(S, InsertPt)); | ||||
| 1915 | if (I != InsertedExpressions.end()) | ||||
| 1916 | return I->second; | ||||
| 1917 | |||||
| 1918 | SCEVInsertPointGuard Guard(Builder, this); | ||||
| 1919 | Builder.SetInsertPoint(InsertPt); | ||||
| 1920 | |||||
| 1921 | // Expand the expression into instructions. | ||||
| 1922 | ScalarEvolution::ValueOffsetPair VO = FindValueInExprValueMap(S, InsertPt); | ||||
| 1923 | Value *V = VO.first; | ||||
| 1924 | |||||
| 1925 | if (!V) | ||||
| 1926 | V = visit(S); | ||||
| 1927 | else if (VO.second) { | ||||
| 1928 | if (PointerType *Vty = dyn_cast<PointerType>(V->getType())) { | ||||
| 1929 | Type *Ety = Vty->getPointerElementType(); | ||||
| 1930 | int64_t Offset = VO.second->getSExtValue(); | ||||
| 1931 | int64_t ESize = SE.getTypeSizeInBits(Ety); | ||||
| 1932 | if ((Offset * 8) % ESize == 0) { | ||||
| 1933 | ConstantInt *Idx = | ||||
| 1934 | ConstantInt::getSigned(VO.second->getType(), -(Offset * 8) / ESize); | ||||
| 1935 | V = Builder.CreateGEP(Ety, V, Idx, "scevgep"); | ||||
| 1936 | } else { | ||||
| 1937 | ConstantInt *Idx = | ||||
| 1938 | ConstantInt::getSigned(VO.second->getType(), -Offset); | ||||
| 1939 | unsigned AS = Vty->getAddressSpace(); | ||||
| 1940 | V = Builder.CreateBitCast(V, Type::getInt8PtrTy(SE.getContext(), AS)); | ||||
| 1941 | V = Builder.CreateGEP(Type::getInt8Ty(SE.getContext()), V, Idx, | ||||
| 1942 | "uglygep"); | ||||
| 1943 | V = Builder.CreateBitCast(V, Vty); | ||||
| 1944 | } | ||||
| 1945 | } else { | ||||
| 1946 | V = Builder.CreateSub(V, VO.second); | ||||
| 1947 | } | ||||
| 1948 | } | ||||
| 1949 | // Remember the expanded value for this SCEV at this location. | ||||
| 1950 | // | ||||
| 1951 | // This is independent of PostIncLoops. The mapped value simply materializes | ||||
| 1952 | // the expression at this insertion point. If the mapped value happened to be | ||||
| 1953 | // a postinc expansion, it could be reused by a non-postinc user, but only if | ||||
| 1954 | // its insertion point was already at the head of the loop. | ||||
| 1955 | InsertedExpressions[std::make_pair(S, InsertPt)] = V; | ||||
| 1956 | return V; | ||||
| 1957 | } | ||||
| 1958 | |||||
| 1959 | void SCEVExpander::rememberInstruction(Value *I) { | ||||
| 1960 | auto DoInsert = [this](Value *V) { | ||||
| 1961 | if (!PostIncLoops.empty()) | ||||
| 1962 | InsertedPostIncValues.insert(V); | ||||
| 1963 | else | ||||
| 1964 | InsertedValues.insert(V); | ||||
| 1965 | }; | ||||
| 1966 | DoInsert(I); | ||||
| 1967 | |||||
| 1968 | if (!PreserveLCSSA) | ||||
| 1969 | return; | ||||
| 1970 | |||||
| 1971 | if (auto *Inst = dyn_cast<Instruction>(I)) { | ||||
| 1972 | // A new instruction has been added, which might introduce new uses outside | ||||
| 1973 | // a defining loop. Fix LCSSA from for each operand of the new instruction, | ||||
| 1974 | // if required. | ||||
| 1975 | for (unsigned OpIdx = 0, OpEnd = Inst->getNumOperands(); OpIdx != OpEnd; | ||||
| 1976 | OpIdx++) | ||||
| 1977 | fixupLCSSAFormFor(Inst, OpIdx); | ||||
| 1978 | } | ||||
| 1979 | } | ||||
| 1980 | |||||
| 1981 | /// getOrInsertCanonicalInductionVariable - This method returns the | ||||
| 1982 | /// canonical induction variable of the specified type for the specified | ||||
| 1983 | /// loop (inserting one if there is none). A canonical induction variable | ||||
| 1984 | /// starts at zero and steps by one on each iteration. | ||||
| 1985 | PHINode * | ||||
| 1986 | SCEVExpander::getOrInsertCanonicalInductionVariable(const Loop *L, | ||||
| 1987 | Type *Ty) { | ||||
| 1988 | assert(Ty->isIntegerTy() && "Can only insert integer induction variables!")((Ty->isIntegerTy() && "Can only insert integer induction variables!" ) ? static_cast<void> (0) : __assert_fail ("Ty->isIntegerTy() && \"Can only insert integer induction variables!\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 1988, __PRETTY_FUNCTION__)); | ||||
| 1989 | |||||
| 1990 | // Build a SCEV for {0,+,1}<L>. | ||||
| 1991 | // Conservatively use FlagAnyWrap for now. | ||||
| 1992 | const SCEV *H = SE.getAddRecExpr(SE.getConstant(Ty, 0), | ||||
| 1993 | SE.getConstant(Ty, 1), L, SCEV::FlagAnyWrap); | ||||
| 1994 | |||||
| 1995 | // Emit code for it. | ||||
| 1996 | SCEVInsertPointGuard Guard(Builder, this); | ||||
| 1997 | PHINode *V = cast<PHINode>(expandCodeForImpl( | ||||
| 1998 | H, nullptr, &*L->getHeader()->getFirstInsertionPt(), false)); | ||||
| 1999 | |||||
| 2000 | return V; | ||||
| 2001 | } | ||||
| 2002 | |||||
| 2003 | /// replaceCongruentIVs - Check for congruent phis in this loop header and | ||||
| 2004 | /// replace them with their most canonical representative. Return the number of | ||||
| 2005 | /// phis eliminated. | ||||
| 2006 | /// | ||||
| 2007 | /// This does not depend on any SCEVExpander state but should be used in | ||||
| 2008 | /// the same context that SCEVExpander is used. | ||||
| 2009 | unsigned | ||||
| 2010 | SCEVExpander::replaceCongruentIVs(Loop *L, const DominatorTree *DT, | ||||
| 2011 | SmallVectorImpl<WeakTrackingVH> &DeadInsts, | ||||
| 2012 | const TargetTransformInfo *TTI) { | ||||
| 2013 | // Find integer phis in order of increasing width. | ||||
| 2014 | SmallVector<PHINode*, 8> Phis; | ||||
| 2015 | for (PHINode &PN : L->getHeader()->phis()) | ||||
| 2016 | Phis.push_back(&PN); | ||||
| 2017 | |||||
| 2018 | if (TTI) | ||||
| 2019 | llvm::sort(Phis, [](Value *LHS, Value *RHS) { | ||||
| 2020 | // Put pointers at the back and make sure pointer < pointer = false. | ||||
| 2021 | if (!LHS->getType()->isIntegerTy() || !RHS->getType()->isIntegerTy()) | ||||
| 2022 | return RHS->getType()->isIntegerTy() && !LHS->getType()->isIntegerTy(); | ||||
| 2023 | return RHS->getType()->getPrimitiveSizeInBits().getFixedSize() < | ||||
| 2024 | LHS->getType()->getPrimitiveSizeInBits().getFixedSize(); | ||||
| 2025 | }); | ||||
| 2026 | |||||
| 2027 | unsigned NumElim = 0; | ||||
| 2028 | DenseMap<const SCEV *, PHINode *> ExprToIVMap; | ||||
| 2029 | // Process phis from wide to narrow. Map wide phis to their truncation | ||||
| 2030 | // so narrow phis can reuse them. | ||||
| 2031 | for (PHINode *Phi : Phis) { | ||||
| 2032 | auto SimplifyPHINode = [&](PHINode *PN) -> Value * { | ||||
| 2033 | if (Value *V = SimplifyInstruction(PN, {DL, &SE.TLI, &SE.DT, &SE.AC})) | ||||
| 2034 | return V; | ||||
| 2035 | if (!SE.isSCEVable(PN->getType())) | ||||
| 2036 | return nullptr; | ||||
| 2037 | auto *Const = dyn_cast<SCEVConstant>(SE.getSCEV(PN)); | ||||
| 2038 | if (!Const) | ||||
| 2039 | return nullptr; | ||||
| 2040 | return Const->getValue(); | ||||
| 2041 | }; | ||||
| 2042 | |||||
| 2043 | // Fold constant phis. They may be congruent to other constant phis and | ||||
| 2044 | // would confuse the logic below that expects proper IVs. | ||||
| 2045 | if (Value *V = SimplifyPHINode(Phi)) { | ||||
| 2046 | if (V->getType() != Phi->getType()) | ||||
| 2047 | continue; | ||||
| 2048 | Phi->replaceAllUsesWith(V); | ||||
| 2049 | DeadInsts.emplace_back(Phi); | ||||
| 2050 | ++NumElim; | ||||
| 2051 | DEBUG_WITH_TYPE(DebugType, dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType (DebugType)) { dbgs() << "INDVARS: Eliminated constant iv: " << *Phi << '\n'; } } while (false) | ||||
| 2052 | << "INDVARS: Eliminated constant iv: " << *Phi << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType (DebugType)) { dbgs() << "INDVARS: Eliminated constant iv: " << *Phi << '\n'; } } while (false); | ||||
| 2053 | continue; | ||||
| 2054 | } | ||||
| 2055 | |||||
| 2056 | if (!SE.isSCEVable(Phi->getType())) | ||||
| 2057 | continue; | ||||
| 2058 | |||||
| 2059 | PHINode *&OrigPhiRef = ExprToIVMap[SE.getSCEV(Phi)]; | ||||
| 2060 | if (!OrigPhiRef) { | ||||
| 2061 | OrigPhiRef = Phi; | ||||
| 2062 | if (Phi->getType()->isIntegerTy() && TTI && | ||||
| 2063 | TTI->isTruncateFree(Phi->getType(), Phis.back()->getType())) { | ||||
| 2064 | // This phi can be freely truncated to the narrowest phi type. Map the | ||||
| 2065 | // truncated expression to it so it will be reused for narrow types. | ||||
| 2066 | const SCEV *TruncExpr = | ||||
| 2067 | SE.getTruncateExpr(SE.getSCEV(Phi), Phis.back()->getType()); | ||||
| 2068 | ExprToIVMap[TruncExpr] = Phi; | ||||
| 2069 | } | ||||
| 2070 | continue; | ||||
| 2071 | } | ||||
| 2072 | |||||
| 2073 | // Replacing a pointer phi with an integer phi or vice-versa doesn't make | ||||
| 2074 | // sense. | ||||
| 2075 | if (OrigPhiRef->getType()->isPointerTy() != Phi->getType()->isPointerTy()) | ||||
| 2076 | continue; | ||||
| 2077 | |||||
| 2078 | if (BasicBlock *LatchBlock = L->getLoopLatch()) { | ||||
| 2079 | Instruction *OrigInc = dyn_cast<Instruction>( | ||||
| 2080 | OrigPhiRef->getIncomingValueForBlock(LatchBlock)); | ||||
| 2081 | Instruction *IsomorphicInc = | ||||
| 2082 | dyn_cast<Instruction>(Phi->getIncomingValueForBlock(LatchBlock)); | ||||
| 2083 | |||||
| 2084 | if (OrigInc && IsomorphicInc) { | ||||
| 2085 | // If this phi has the same width but is more canonical, replace the | ||||
| 2086 | // original with it. As part of the "more canonical" determination, | ||||
| 2087 | // respect a prior decision to use an IV chain. | ||||
| 2088 | if (OrigPhiRef->getType() == Phi->getType() && | ||||
| 2089 | !(ChainedPhis.count(Phi) || | ||||
| 2090 | isExpandedAddRecExprPHI(OrigPhiRef, OrigInc, L)) && | ||||
| 2091 | (ChainedPhis.count(Phi) || | ||||
| 2092 | isExpandedAddRecExprPHI(Phi, IsomorphicInc, L))) { | ||||
| 2093 | std::swap(OrigPhiRef, Phi); | ||||
| 2094 | std::swap(OrigInc, IsomorphicInc); | ||||
| 2095 | } | ||||
| 2096 | // Replacing the congruent phi is sufficient because acyclic | ||||
| 2097 | // redundancy elimination, CSE/GVN, should handle the | ||||
| 2098 | // rest. However, once SCEV proves that a phi is congruent, | ||||
| 2099 | // it's often the head of an IV user cycle that is isomorphic | ||||
| 2100 | // with the original phi. It's worth eagerly cleaning up the | ||||
| 2101 | // common case of a single IV increment so that DeleteDeadPHIs | ||||
| 2102 | // can remove cycles that had postinc uses. | ||||
| 2103 | const SCEV *TruncExpr = | ||||
| 2104 | SE.getTruncateOrNoop(SE.getSCEV(OrigInc), IsomorphicInc->getType()); | ||||
| 2105 | if (OrigInc != IsomorphicInc && | ||||
| 2106 | TruncExpr == SE.getSCEV(IsomorphicInc) && | ||||
| 2107 | SE.LI.replacementPreservesLCSSAForm(IsomorphicInc, OrigInc) && | ||||
| 2108 | hoistIVInc(OrigInc, IsomorphicInc)) { | ||||
| 2109 | DEBUG_WITH_TYPE(DebugType,do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType (DebugType)) { dbgs() << "INDVARS: Eliminated congruent iv.inc: " << *IsomorphicInc << '\n'; } } while (false) | ||||
| 2110 | dbgs() << "INDVARS: Eliminated congruent iv.inc: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType (DebugType)) { dbgs() << "INDVARS: Eliminated congruent iv.inc: " << *IsomorphicInc << '\n'; } } while (false) | ||||
| 2111 | << *IsomorphicInc << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType (DebugType)) { dbgs() << "INDVARS: Eliminated congruent iv.inc: " << *IsomorphicInc << '\n'; } } while (false); | ||||
| 2112 | Value *NewInc = OrigInc; | ||||
| 2113 | if (OrigInc->getType() != IsomorphicInc->getType()) { | ||||
| 2114 | Instruction *IP = nullptr; | ||||
| 2115 | if (PHINode *PN = dyn_cast<PHINode>(OrigInc)) | ||||
| 2116 | IP = &*PN->getParent()->getFirstInsertionPt(); | ||||
| 2117 | else | ||||
| 2118 | IP = OrigInc->getNextNode(); | ||||
| 2119 | |||||
| 2120 | IRBuilder<> Builder(IP); | ||||
| 2121 | Builder.SetCurrentDebugLocation(IsomorphicInc->getDebugLoc()); | ||||
| 2122 | NewInc = Builder.CreateTruncOrBitCast( | ||||
| 2123 | OrigInc, IsomorphicInc->getType(), IVName); | ||||
| 2124 | } | ||||
| 2125 | IsomorphicInc->replaceAllUsesWith(NewInc); | ||||
| 2126 | DeadInsts.emplace_back(IsomorphicInc); | ||||
| 2127 | } | ||||
| 2128 | } | ||||
| 2129 | } | ||||
| 2130 | DEBUG_WITH_TYPE(DebugType, dbgs() << "INDVARS: Eliminated congruent iv: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType (DebugType)) { dbgs() << "INDVARS: Eliminated congruent iv: " << *Phi << '\n'; } } while (false) | ||||
| 2131 | << *Phi << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType (DebugType)) { dbgs() << "INDVARS: Eliminated congruent iv: " << *Phi << '\n'; } } while (false); | ||||
| 2132 | DEBUG_WITH_TYPE(DebugType, dbgs() << "INDVARS: Original iv: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType (DebugType)) { dbgs() << "INDVARS: Original iv: " << *OrigPhiRef << '\n'; } } while (false) | ||||
| 2133 | << *OrigPhiRef << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType (DebugType)) { dbgs() << "INDVARS: Original iv: " << *OrigPhiRef << '\n'; } } while (false); | ||||
| 2134 | ++NumElim; | ||||
| 2135 | Value *NewIV = OrigPhiRef; | ||||
| 2136 | if (OrigPhiRef->getType() != Phi->getType()) { | ||||
| 2137 | IRBuilder<> Builder(&*L->getHeader()->getFirstInsertionPt()); | ||||
| 2138 | Builder.SetCurrentDebugLocation(Phi->getDebugLoc()); | ||||
| 2139 | NewIV = Builder.CreateTruncOrBitCast(OrigPhiRef, Phi->getType(), IVName); | ||||
| 2140 | } | ||||
| 2141 | Phi->replaceAllUsesWith(NewIV); | ||||
| 2142 | DeadInsts.emplace_back(Phi); | ||||
| 2143 | } | ||||
| 2144 | return NumElim; | ||||
| 2145 | } | ||||
| 2146 | |||||
| 2147 | Value *SCEVExpander::getExactExistingExpansion(const SCEV *S, | ||||
| 2148 | const Instruction *At, Loop *L) { | ||||
| 2149 | Optional<ScalarEvolution::ValueOffsetPair> VO = | ||||
| 2150 | getRelatedExistingExpansion(S, At, L); | ||||
| 2151 | if (VO && VO.getValue().second == nullptr) | ||||
| 2152 | return VO.getValue().first; | ||||
| 2153 | return nullptr; | ||||
| 2154 | } | ||||
| 2155 | |||||
| 2156 | Optional<ScalarEvolution::ValueOffsetPair> | ||||
| 2157 | SCEVExpander::getRelatedExistingExpansion(const SCEV *S, const Instruction *At, | ||||
| 2158 | Loop *L) { | ||||
| 2159 | using namespace llvm::PatternMatch; | ||||
| 2160 | |||||
| 2161 | SmallVector<BasicBlock *, 4> ExitingBlocks; | ||||
| 2162 | L->getExitingBlocks(ExitingBlocks); | ||||
| 2163 | |||||
| 2164 | // Look for suitable value in simple conditions at the loop exits. | ||||
| 2165 | for (BasicBlock *BB : ExitingBlocks) { | ||||
| 2166 | ICmpInst::Predicate Pred; | ||||
| 2167 | Instruction *LHS, *RHS; | ||||
| 2168 | |||||
| 2169 | if (!match(BB->getTerminator(), | ||||
| 2170 | m_Br(m_ICmp(Pred, m_Instruction(LHS), m_Instruction(RHS)), | ||||
| 2171 | m_BasicBlock(), m_BasicBlock()))) | ||||
| 2172 | continue; | ||||
| 2173 | |||||
| 2174 | if (SE.getSCEV(LHS) == S && SE.DT.dominates(LHS, At)) | ||||
| 2175 | return ScalarEvolution::ValueOffsetPair(LHS, nullptr); | ||||
| 2176 | |||||
| 2177 | if (SE.getSCEV(RHS) == S && SE.DT.dominates(RHS, At)) | ||||
| 2178 | return ScalarEvolution::ValueOffsetPair(RHS, nullptr); | ||||
| 2179 | } | ||||
| 2180 | |||||
| 2181 | // Use expand's logic which is used for reusing a previous Value in | ||||
| 2182 | // ExprValueMap. | ||||
| 2183 | ScalarEvolution::ValueOffsetPair VO = FindValueInExprValueMap(S, At); | ||||
| 2184 | if (VO.first) | ||||
| 2185 | return VO; | ||||
| 2186 | |||||
| 2187 | // There is potential to make this significantly smarter, but this simple | ||||
| 2188 | // heuristic already gets some interesting cases. | ||||
| 2189 | |||||
| 2190 | // Can not find suitable value. | ||||
| 2191 | return None; | ||||
| 2192 | } | ||||
| 2193 | |||||
| 2194 | template<typename T> static int costAndCollectOperands( | ||||
| 2195 | const SCEVOperand &WorkItem, const TargetTransformInfo &TTI, | ||||
| 2196 | TargetTransformInfo::TargetCostKind CostKind, | ||||
| 2197 | SmallVectorImpl<SCEVOperand> &Worklist) { | ||||
| 2198 | |||||
| 2199 | const T *S = cast<T>(WorkItem.S); | ||||
| 2200 | int Cost = 0; | ||||
| 2201 | // Object to help map SCEV operands to expanded IR instructions. | ||||
| 2202 | struct OperationIndices { | ||||
| 2203 | OperationIndices(unsigned Opc, size_t min, size_t max) : | ||||
| 2204 | Opcode(Opc), MinIdx(min), MaxIdx(max) { } | ||||
| 2205 | unsigned Opcode; | ||||
| 2206 | size_t MinIdx; | ||||
| 2207 | size_t MaxIdx; | ||||
| 2208 | }; | ||||
| 2209 | |||||
| 2210 | // Collect the operations of all the instructions that will be needed to | ||||
| 2211 | // expand the SCEVExpr. This is so that when we come to cost the operands, | ||||
| 2212 | // we know what the generated user(s) will be. | ||||
| 2213 | SmallVector<OperationIndices, 2> Operations; | ||||
| 2214 | |||||
| 2215 | auto CastCost = [&](unsigned Opcode) { | ||||
| 2216 | Operations.emplace_back(Opcode, 0, 0); | ||||
| 2217 | return TTI.getCastInstrCost(Opcode, S->getType(), | ||||
| 2218 | S->getOperand(0)->getType(), | ||||
| 2219 | TTI::CastContextHint::None, CostKind); | ||||
| 2220 | }; | ||||
| 2221 | |||||
| 2222 | auto ArithCost = [&](unsigned Opcode, unsigned NumRequired, | ||||
| 2223 | unsigned MinIdx = 0, unsigned MaxIdx = 1) { | ||||
| 2224 | Operations.emplace_back(Opcode, MinIdx, MaxIdx); | ||||
| 2225 | return NumRequired * | ||||
| 2226 | TTI.getArithmeticInstrCost(Opcode, S->getType(), CostKind); | ||||
| 2227 | }; | ||||
| 2228 | |||||
| 2229 | auto CmpSelCost = [&](unsigned Opcode, unsigned NumRequired, | ||||
| 2230 | unsigned MinIdx, unsigned MaxIdx) { | ||||
| 2231 | Operations.emplace_back(Opcode, MinIdx, MaxIdx); | ||||
| 2232 | Type *OpType = S->getOperand(0)->getType(); | ||||
| 2233 | return NumRequired * | ||||
| 2234 | TTI.getCmpSelInstrCost(Opcode, OpType, | ||||
| 2235 | CmpInst::makeCmpResultType(OpType), CostKind); | ||||
| 2236 | }; | ||||
| 2237 | |||||
| 2238 | switch (S->getSCEVType()) { | ||||
| 2239 | case scCouldNotCompute: | ||||
| 2240 | llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!")::llvm::llvm_unreachable_internal("Attempt to use a SCEVCouldNotCompute object!" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 2240); | ||||
| 2241 | case scUnknown: | ||||
| 2242 | case scConstant: | ||||
| 2243 | return 0; | ||||
| 2244 | case scTruncate: | ||||
| 2245 | Cost = CastCost(Instruction::Trunc); | ||||
| 2246 | break; | ||||
| 2247 | case scZeroExtend: | ||||
| 2248 | Cost = CastCost(Instruction::ZExt); | ||||
| 2249 | break; | ||||
| 2250 | case scSignExtend: | ||||
| 2251 | Cost = CastCost(Instruction::SExt); | ||||
| 2252 | break; | ||||
| 2253 | case scUDivExpr: { | ||||
| 2254 | unsigned Opcode = Instruction::UDiv; | ||||
| 2255 | if (auto *SC = dyn_cast<SCEVConstant>(S->getOperand(1))) | ||||
| 2256 | if (SC->getAPInt().isPowerOf2()) | ||||
| 2257 | Opcode = Instruction::LShr; | ||||
| 2258 | Cost = ArithCost(Opcode, 1); | ||||
| 2259 | break; | ||||
| 2260 | } | ||||
| 2261 | case scAddExpr: | ||||
| 2262 | Cost = ArithCost(Instruction::Add, S->getNumOperands() - 1); | ||||
| 2263 | break; | ||||
| 2264 | case scMulExpr: | ||||
| 2265 | // TODO: this is a very pessimistic cost modelling for Mul, | ||||
| 2266 | // because of Bin Pow algorithm actually used by the expander, | ||||
| 2267 | // see SCEVExpander::visitMulExpr(), ExpandOpBinPowN(). | ||||
| 2268 | Cost = ArithCost(Instruction::Mul, S->getNumOperands() - 1); | ||||
| 2269 | break; | ||||
| 2270 | case scSMaxExpr: | ||||
| 2271 | case scUMaxExpr: | ||||
| 2272 | case scSMinExpr: | ||||
| 2273 | case scUMinExpr: { | ||||
| 2274 | Cost += CmpSelCost(Instruction::ICmp, S->getNumOperands() - 1, 0, 1); | ||||
| 2275 | Cost += CmpSelCost(Instruction::Select, S->getNumOperands() - 1, 0, 2); | ||||
| 2276 | break; | ||||
| 2277 | } | ||||
| 2278 | case scAddRecExpr: { | ||||
| 2279 | // In this polynominal, we may have some zero operands, and we shouldn't | ||||
| 2280 | // really charge for those. So how many non-zero coeffients are there? | ||||
| 2281 | int NumTerms = llvm::count_if(S->operands(), [](const SCEV *Op) { | ||||
| 2282 | return !Op->isZero(); | ||||
| 2283 | }); | ||||
| 2284 | |||||
| 2285 | assert(NumTerms >= 1 && "Polynominal should have at least one term.")((NumTerms >= 1 && "Polynominal should have at least one term." ) ? static_cast<void> (0) : __assert_fail ("NumTerms >= 1 && \"Polynominal should have at least one term.\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 2285, __PRETTY_FUNCTION__)); | ||||
| 2286 | assert(!(*std::prev(S->operands().end()))->isZero() &&((!(*std::prev(S->operands().end()))->isZero() && "Last operand should not be zero") ? static_cast<void> (0) : __assert_fail ("!(*std::prev(S->operands().end()))->isZero() && \"Last operand should not be zero\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 2287, __PRETTY_FUNCTION__)) | ||||
| 2287 | "Last operand should not be zero")((!(*std::prev(S->operands().end()))->isZero() && "Last operand should not be zero") ? static_cast<void> (0) : __assert_fail ("!(*std::prev(S->operands().end()))->isZero() && \"Last operand should not be zero\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 2287, __PRETTY_FUNCTION__)); | ||||
| 2288 | |||||
| 2289 | // Ignoring constant term (operand 0), how many of the coeffients are u> 1? | ||||
| 2290 | int NumNonZeroDegreeNonOneTerms = | ||||
| 2291 | llvm::count_if(S->operands(), [](const SCEV *Op) { | ||||
| 2292 | auto *SConst = dyn_cast<SCEVConstant>(Op); | ||||
| 2293 | return !SConst || SConst->getAPInt().ugt(1); | ||||
| 2294 | }); | ||||
| 2295 | |||||
| 2296 | // Much like with normal add expr, the polynominal will require | ||||
| 2297 | // one less addition than the number of it's terms. | ||||
| 2298 | int AddCost = ArithCost(Instruction::Add, NumTerms - 1, | ||||
| 2299 | /*MinIdx*/1, /*MaxIdx*/1); | ||||
| 2300 | // Here, *each* one of those will require a multiplication. | ||||
| 2301 | int MulCost = ArithCost(Instruction::Mul, NumNonZeroDegreeNonOneTerms); | ||||
| 2302 | Cost = AddCost + MulCost; | ||||
| 2303 | |||||
| 2304 | // What is the degree of this polynominal? | ||||
| 2305 | int PolyDegree = S->getNumOperands() - 1; | ||||
| 2306 | assert(PolyDegree >= 1 && "Should be at least affine.")((PolyDegree >= 1 && "Should be at least affine.") ? static_cast<void> (0) : __assert_fail ("PolyDegree >= 1 && \"Should be at least affine.\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 2306, __PRETTY_FUNCTION__)); | ||||
| 2307 | |||||
| 2308 | // The final term will be: | ||||
| 2309 | // Op_{PolyDegree} * x ^ {PolyDegree} | ||||
| 2310 | // Where x ^ {PolyDegree} will again require PolyDegree-1 mul operations. | ||||
| 2311 | // Note that x ^ {PolyDegree} = x * x ^ {PolyDegree-1} so charging for | ||||
| 2312 | // x ^ {PolyDegree} will give us x ^ {2} .. x ^ {PolyDegree-1} for free. | ||||
| 2313 | // FIXME: this is conservatively correct, but might be overly pessimistic. | ||||
| 2314 | Cost += MulCost * (PolyDegree - 1); | ||||
| 2315 | break; | ||||
| 2316 | } | ||||
| 2317 | } | ||||
| 2318 | |||||
| 2319 | for (auto &CostOp : Operations) { | ||||
| 2320 | for (auto SCEVOp : enumerate(S->operands())) { | ||||
| 2321 | // Clamp the index to account for multiple IR operations being chained. | ||||
| 2322 | size_t MinIdx = std::max(SCEVOp.index(), CostOp.MinIdx); | ||||
| 2323 | size_t OpIdx = std::min(MinIdx, CostOp.MaxIdx); | ||||
| 2324 | Worklist.emplace_back(CostOp.Opcode, OpIdx, SCEVOp.value()); | ||||
| 2325 | } | ||||
| 2326 | } | ||||
| 2327 | return Cost; | ||||
| 2328 | } | ||||
| 2329 | |||||
| 2330 | bool SCEVExpander::isHighCostExpansionHelper( | ||||
| 2331 | const SCEVOperand &WorkItem, Loop *L, const Instruction &At, | ||||
| 2332 | int &BudgetRemaining, const TargetTransformInfo &TTI, | ||||
| 2333 | SmallPtrSetImpl<const SCEV *> &Processed, | ||||
| 2334 | SmallVectorImpl<SCEVOperand> &Worklist) { | ||||
| 2335 | if (BudgetRemaining < 0) | ||||
| 2336 | return true; // Already run out of budget, give up. | ||||
| 2337 | |||||
| 2338 | const SCEV *S = WorkItem.S; | ||||
| 2339 | // Was the cost of expansion of this expression already accounted for? | ||||
| 2340 | if (!isa<SCEVConstant>(S) && !Processed.insert(S).second) | ||||
| 2341 | return false; // We have already accounted for this expression. | ||||
| 2342 | |||||
| 2343 | // If we can find an existing value for this scev available at the point "At" | ||||
| 2344 | // then consider the expression cheap. | ||||
| 2345 | if (getRelatedExistingExpansion(S, &At, L)) | ||||
| 2346 | return false; // Consider the expression to be free. | ||||
| 2347 | |||||
| 2348 | TargetTransformInfo::TargetCostKind CostKind = | ||||
| 2349 | L->getHeader()->getParent()->hasMinSize() | ||||
| 2350 | ? TargetTransformInfo::TCK_CodeSize | ||||
| 2351 | : TargetTransformInfo::TCK_RecipThroughput; | ||||
| 2352 | |||||
| 2353 | switch (S->getSCEVType()) { | ||||
| 2354 | case scCouldNotCompute: | ||||
| 2355 | llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!")::llvm::llvm_unreachable_internal("Attempt to use a SCEVCouldNotCompute object!" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 2355); | ||||
| 2356 | case scUnknown: | ||||
| 2357 | // Assume to be zero-cost. | ||||
| 2358 | return false; | ||||
| 2359 | case scConstant: { | ||||
| 2360 | auto *Constant = dyn_cast<SCEVConstant>(S); | ||||
| 2361 | // Only evalulate the costs of constants when optimizing for size. | ||||
| 2362 | if (CostKind != TargetTransformInfo::TCK_CodeSize) | ||||
| 2363 | return 0; | ||||
| 2364 | const APInt &Imm = Constant->getAPInt(); | ||||
| 2365 | Type *Ty = S->getType(); | ||||
| 2366 | BudgetRemaining -= TTI.getIntImmCostInst( | ||||
| 2367 | WorkItem.ParentOpcode, WorkItem.OperandIdx, Imm, Ty, CostKind); | ||||
| 2368 | return BudgetRemaining < 0; | ||||
| 2369 | } | ||||
| 2370 | case scTruncate: | ||||
| 2371 | case scZeroExtend: | ||||
| 2372 | case scSignExtend: { | ||||
| 2373 | int Cost = costAndCollectOperands<SCEVIntegralCastExpr>(WorkItem, TTI, | ||||
| 2374 | CostKind, Worklist); | ||||
| 2375 | BudgetRemaining -= Cost; | ||||
| 2376 | return false; // Will answer upon next entry into this function. | ||||
| 2377 | } | ||||
| 2378 | case scUDivExpr: { | ||||
| 2379 | // UDivExpr is very likely a UDiv that ScalarEvolution's HowFarToZero or | ||||
| 2380 | // HowManyLessThans produced to compute a precise expression, rather than a | ||||
| 2381 | // UDiv from the user's code. If we can't find a UDiv in the code with some | ||||
| 2382 | // simple searching, we need to account for it's cost. | ||||
| 2383 | |||||
| 2384 | // At the beginning of this function we already tried to find existing | ||||
| 2385 | // value for plain 'S'. Now try to lookup 'S + 1' since it is common | ||||
| 2386 | // pattern involving division. This is just a simple search heuristic. | ||||
| 2387 | if (getRelatedExistingExpansion( | ||||
| 2388 | SE.getAddExpr(S, SE.getConstant(S->getType(), 1)), &At, L)) | ||||
| 2389 | return false; // Consider it to be free. | ||||
| 2390 | |||||
| 2391 | int Cost = | ||||
| 2392 | costAndCollectOperands<SCEVUDivExpr>(WorkItem, TTI, CostKind, Worklist); | ||||
| 2393 | // Need to count the cost of this UDiv. | ||||
| 2394 | BudgetRemaining -= Cost; | ||||
| 2395 | return false; // Will answer upon next entry into this function. | ||||
| 2396 | } | ||||
| 2397 | case scAddExpr: | ||||
| 2398 | case scMulExpr: | ||||
| 2399 | case scUMaxExpr: | ||||
| 2400 | case scSMaxExpr: | ||||
| 2401 | case scUMinExpr: | ||||
| 2402 | case scSMinExpr: { | ||||
| 2403 | assert(dyn_cast<SCEVNAryExpr>(S)->getNumOperands() > 1 &&((dyn_cast<SCEVNAryExpr>(S)->getNumOperands() > 1 && "Nary expr should have more than 1 operand.") ? static_cast <void> (0) : __assert_fail ("dyn_cast<SCEVNAryExpr>(S)->getNumOperands() > 1 && \"Nary expr should have more than 1 operand.\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 2404, __PRETTY_FUNCTION__)) | ||||
| 2404 | "Nary expr should have more than 1 operand.")((dyn_cast<SCEVNAryExpr>(S)->getNumOperands() > 1 && "Nary expr should have more than 1 operand.") ? static_cast <void> (0) : __assert_fail ("dyn_cast<SCEVNAryExpr>(S)->getNumOperands() > 1 && \"Nary expr should have more than 1 operand.\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 2404, __PRETTY_FUNCTION__)); | ||||
| 2405 | // The simple nary expr will require one less op (or pair of ops) | ||||
| 2406 | // than the number of it's terms. | ||||
| 2407 | int Cost = | ||||
| 2408 | costAndCollectOperands<SCEVNAryExpr>(WorkItem, TTI, CostKind, Worklist); | ||||
| 2409 | BudgetRemaining -= Cost; | ||||
| 2410 | return BudgetRemaining < 0; | ||||
| 2411 | } | ||||
| 2412 | case scAddRecExpr: { | ||||
| 2413 | assert(cast<SCEVAddRecExpr>(S)->getNumOperands() >= 2 &&((cast<SCEVAddRecExpr>(S)->getNumOperands() >= 2 && "Polynomial should be at least linear") ? static_cast<void > (0) : __assert_fail ("cast<SCEVAddRecExpr>(S)->getNumOperands() >= 2 && \"Polynomial should be at least linear\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 2414, __PRETTY_FUNCTION__)) | ||||
| 2414 | "Polynomial should be at least linear")((cast<SCEVAddRecExpr>(S)->getNumOperands() >= 2 && "Polynomial should be at least linear") ? static_cast<void > (0) : __assert_fail ("cast<SCEVAddRecExpr>(S)->getNumOperands() >= 2 && \"Polynomial should be at least linear\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 2414, __PRETTY_FUNCTION__)); | ||||
| 2415 | BudgetRemaining -= costAndCollectOperands<SCEVAddRecExpr>( | ||||
| 2416 | WorkItem, TTI, CostKind, Worklist); | ||||
| 2417 | return BudgetRemaining < 0; | ||||
| 2418 | } | ||||
| 2419 | } | ||||
| 2420 | llvm_unreachable("Unknown SCEV kind!")::llvm::llvm_unreachable_internal("Unknown SCEV kind!", "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 2420); | ||||
| 2421 | } | ||||
| 2422 | |||||
| 2423 | Value *SCEVExpander::expandCodeForPredicate(const SCEVPredicate *Pred, | ||||
| 2424 | Instruction *IP) { | ||||
| 2425 | assert(IP)((IP) ? static_cast<void> (0) : __assert_fail ("IP", "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 2425, __PRETTY_FUNCTION__)); | ||||
| 2426 | switch (Pred->getKind()) { | ||||
| 2427 | case SCEVPredicate::P_Union: | ||||
| 2428 | return expandUnionPredicate(cast<SCEVUnionPredicate>(Pred), IP); | ||||
| 2429 | case SCEVPredicate::P_Equal: | ||||
| 2430 | return expandEqualPredicate(cast<SCEVEqualPredicate>(Pred), IP); | ||||
| 2431 | case SCEVPredicate::P_Wrap: { | ||||
| 2432 | auto *AddRecPred = cast<SCEVWrapPredicate>(Pred); | ||||
| 2433 | return expandWrapPredicate(AddRecPred, IP); | ||||
| 2434 | } | ||||
| 2435 | } | ||||
| 2436 | llvm_unreachable("Unknown SCEV predicate type")::llvm::llvm_unreachable_internal("Unknown SCEV predicate type" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 2436); | ||||
| 2437 | } | ||||
| 2438 | |||||
| 2439 | Value *SCEVExpander::expandEqualPredicate(const SCEVEqualPredicate *Pred, | ||||
| 2440 | Instruction *IP) { | ||||
| 2441 | Value *Expr0 = | ||||
| 2442 | expandCodeForImpl(Pred->getLHS(), Pred->getLHS()->getType(), IP, false); | ||||
| 2443 | Value *Expr1 = | ||||
| 2444 | expandCodeForImpl(Pred->getRHS(), Pred->getRHS()->getType(), IP, false); | ||||
| 2445 | |||||
| 2446 | Builder.SetInsertPoint(IP); | ||||
| 2447 | auto *I = Builder.CreateICmpNE(Expr0, Expr1, "ident.check"); | ||||
| 2448 | return I; | ||||
| 2449 | } | ||||
| 2450 | |||||
| 2451 | Value *SCEVExpander::generateOverflowCheck(const SCEVAddRecExpr *AR, | ||||
| 2452 | Instruction *Loc, bool Signed) { | ||||
| 2453 | assert(AR->isAffine() && "Cannot generate RT check for "((AR->isAffine() && "Cannot generate RT check for " "non-affine expression") ? static_cast<void> (0) : __assert_fail ("AR->isAffine() && \"Cannot generate RT check for \" \"non-affine expression\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 2454, __PRETTY_FUNCTION__)) | ||||
| 2454 | "non-affine expression")((AR->isAffine() && "Cannot generate RT check for " "non-affine expression") ? static_cast<void> (0) : __assert_fail ("AR->isAffine() && \"Cannot generate RT check for \" \"non-affine expression\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 2454, __PRETTY_FUNCTION__)); | ||||
| 2455 | |||||
| 2456 | SCEVUnionPredicate Pred; | ||||
| 2457 | const SCEV *ExitCount = | ||||
| 2458 | SE.getPredicatedBackedgeTakenCount(AR->getLoop(), Pred); | ||||
| 2459 | |||||
| 2460 | assert(ExitCount != SE.getCouldNotCompute() && "Invalid loop count")((ExitCount != SE.getCouldNotCompute() && "Invalid loop count" ) ? static_cast<void> (0) : __assert_fail ("ExitCount != SE.getCouldNotCompute() && \"Invalid loop count\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 2460, __PRETTY_FUNCTION__)); | ||||
| 2461 | |||||
| 2462 | const SCEV *Step = AR->getStepRecurrence(SE); | ||||
| 2463 | const SCEV *Start = AR->getStart(); | ||||
| 2464 | |||||
| 2465 | Type *ARTy = AR->getType(); | ||||
| 2466 | unsigned SrcBits = SE.getTypeSizeInBits(ExitCount->getType()); | ||||
| 2467 | unsigned DstBits = SE.getTypeSizeInBits(ARTy); | ||||
| 2468 | |||||
| 2469 | // The expression {Start,+,Step} has nusw/nssw if | ||||
| 2470 | // Step < 0, Start - |Step| * Backedge <= Start | ||||
| 2471 | // Step >= 0, Start + |Step| * Backedge > Start | ||||
| 2472 | // and |Step| * Backedge doesn't unsigned overflow. | ||||
| 2473 | |||||
| 2474 | IntegerType *CountTy = IntegerType::get(Loc->getContext(), SrcBits); | ||||
| 2475 | Builder.SetInsertPoint(Loc); | ||||
| 2476 | Value *TripCountVal = expandCodeForImpl(ExitCount, CountTy, Loc, false); | ||||
| 2477 | |||||
| 2478 | IntegerType *Ty = | ||||
| 2479 | IntegerType::get(Loc->getContext(), SE.getTypeSizeInBits(ARTy)); | ||||
| 2480 | Type *ARExpandTy = DL.isNonIntegralPointerType(ARTy) ? ARTy : Ty; | ||||
| 2481 | |||||
| 2482 | Value *StepValue = expandCodeForImpl(Step, Ty, Loc, false); | ||||
| 2483 | Value *NegStepValue = | ||||
| 2484 | expandCodeForImpl(SE.getNegativeSCEV(Step), Ty, Loc, false); | ||||
| 2485 | Value *StartValue = expandCodeForImpl(Start, ARExpandTy, Loc, false); | ||||
| 2486 | |||||
| 2487 | ConstantInt *Zero = | ||||
| 2488 | ConstantInt::get(Loc->getContext(), APInt::getNullValue(DstBits)); | ||||
| 2489 | |||||
| 2490 | Builder.SetInsertPoint(Loc); | ||||
| 2491 | // Compute |Step| | ||||
| 2492 | Value *StepCompare = Builder.CreateICmp(ICmpInst::ICMP_SLT, StepValue, Zero); | ||||
| 2493 | Value *AbsStep = Builder.CreateSelect(StepCompare, NegStepValue, StepValue); | ||||
| 2494 | |||||
| 2495 | // Get the backedge taken count and truncate or extended to the AR type. | ||||
| 2496 | Value *TruncTripCount = Builder.CreateZExtOrTrunc(TripCountVal, Ty); | ||||
| 2497 | auto *MulF = Intrinsic::getDeclaration(Loc->getModule(), | ||||
| 2498 | Intrinsic::umul_with_overflow, Ty); | ||||
| 2499 | |||||
| 2500 | // Compute |Step| * Backedge | ||||
| 2501 | CallInst *Mul = Builder.CreateCall(MulF, {AbsStep, TruncTripCount}, "mul"); | ||||
| 2502 | Value *MulV = Builder.CreateExtractValue(Mul, 0, "mul.result"); | ||||
| 2503 | Value *OfMul = Builder.CreateExtractValue(Mul, 1, "mul.overflow"); | ||||
| 2504 | |||||
| 2505 | // Compute: | ||||
| 2506 | // Start + |Step| * Backedge < Start | ||||
| 2507 | // Start - |Step| * Backedge > Start | ||||
| 2508 | Value *Add = nullptr, *Sub = nullptr; | ||||
| 2509 | if (PointerType *ARPtrTy = dyn_cast<PointerType>(ARExpandTy)) { | ||||
| 2510 | const SCEV *MulS = SE.getSCEV(MulV); | ||||
| 2511 | const SCEV *NegMulS = SE.getNegativeSCEV(MulS); | ||||
| 2512 | Add = Builder.CreateBitCast(expandAddToGEP(MulS, ARPtrTy, Ty, StartValue), | ||||
| 2513 | ARPtrTy); | ||||
| 2514 | Sub = Builder.CreateBitCast( | ||||
| 2515 | expandAddToGEP(NegMulS, ARPtrTy, Ty, StartValue), ARPtrTy); | ||||
| 2516 | } else { | ||||
| 2517 | Add = Builder.CreateAdd(StartValue, MulV); | ||||
| 2518 | Sub = Builder.CreateSub(StartValue, MulV); | ||||
| 2519 | } | ||||
| 2520 | |||||
| 2521 | Value *EndCompareGT = Builder.CreateICmp( | ||||
| 2522 | Signed ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT, Sub, StartValue); | ||||
| 2523 | |||||
| 2524 | Value *EndCompareLT = Builder.CreateICmp( | ||||
| 2525 | Signed ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, Add, StartValue); | ||||
| 2526 | |||||
| 2527 | // Select the answer based on the sign of Step. | ||||
| 2528 | Value *EndCheck = | ||||
| 2529 | Builder.CreateSelect(StepCompare, EndCompareGT, EndCompareLT); | ||||
| 2530 | |||||
| 2531 | // If the backedge taken count type is larger than the AR type, | ||||
| 2532 | // check that we don't drop any bits by truncating it. If we are | ||||
| 2533 | // dropping bits, then we have overflow (unless the step is zero). | ||||
| 2534 | if (SE.getTypeSizeInBits(CountTy) > SE.getTypeSizeInBits(Ty)) { | ||||
| 2535 | auto MaxVal = APInt::getMaxValue(DstBits).zext(SrcBits); | ||||
| 2536 | auto *BackedgeCheck = | ||||
| 2537 | Builder.CreateICmp(ICmpInst::ICMP_UGT, TripCountVal, | ||||
| 2538 | ConstantInt::get(Loc->getContext(), MaxVal)); | ||||
| 2539 | BackedgeCheck = Builder.CreateAnd( | ||||
| 2540 | BackedgeCheck, Builder.CreateICmp(ICmpInst::ICMP_NE, StepValue, Zero)); | ||||
| 2541 | |||||
| 2542 | EndCheck = Builder.CreateOr(EndCheck, BackedgeCheck); | ||||
| 2543 | } | ||||
| 2544 | |||||
| 2545 | return Builder.CreateOr(EndCheck, OfMul); | ||||
| 2546 | } | ||||
| 2547 | |||||
| 2548 | Value *SCEVExpander::expandWrapPredicate(const SCEVWrapPredicate *Pred, | ||||
| 2549 | Instruction *IP) { | ||||
| 2550 | const auto *A = cast<SCEVAddRecExpr>(Pred->getExpr()); | ||||
| 2551 | Value *NSSWCheck = nullptr, *NUSWCheck = nullptr; | ||||
| 2552 | |||||
| 2553 | // Add a check for NUSW | ||||
| 2554 | if (Pred->getFlags() & SCEVWrapPredicate::IncrementNUSW) | ||||
| 2555 | NUSWCheck = generateOverflowCheck(A, IP, false); | ||||
| 2556 | |||||
| 2557 | // Add a check for NSSW | ||||
| 2558 | if (Pred->getFlags() & SCEVWrapPredicate::IncrementNSSW) | ||||
| 2559 | NSSWCheck = generateOverflowCheck(A, IP, true); | ||||
| 2560 | |||||
| 2561 | if (NUSWCheck && NSSWCheck) | ||||
| 2562 | return Builder.CreateOr(NUSWCheck, NSSWCheck); | ||||
| 2563 | |||||
| 2564 | if (NUSWCheck) | ||||
| 2565 | return NUSWCheck; | ||||
| 2566 | |||||
| 2567 | if (NSSWCheck) | ||||
| 2568 | return NSSWCheck; | ||||
| 2569 | |||||
| 2570 | return ConstantInt::getFalse(IP->getContext()); | ||||
| 2571 | } | ||||
| 2572 | |||||
| 2573 | Value *SCEVExpander::expandUnionPredicate(const SCEVUnionPredicate *Union, | ||||
| 2574 | Instruction *IP) { | ||||
| 2575 | auto *BoolType = IntegerType::get(IP->getContext(), 1); | ||||
| 2576 | Value *Check = ConstantInt::getNullValue(BoolType); | ||||
| 2577 | |||||
| 2578 | // Loop over all checks in this set. | ||||
| 2579 | for (auto Pred : Union->getPredicates()) { | ||||
| 2580 | auto *NextCheck = expandCodeForPredicate(Pred, IP); | ||||
| 2581 | Builder.SetInsertPoint(IP); | ||||
| 2582 | Check = Builder.CreateOr(Check, NextCheck); | ||||
| 2583 | } | ||||
| 2584 | |||||
| 2585 | return Check; | ||||
| 2586 | } | ||||
| 2587 | |||||
| 2588 | Value *SCEVExpander::fixupLCSSAFormFor(Instruction *User, unsigned OpIdx) { | ||||
| 2589 | assert(PreserveLCSSA)((PreserveLCSSA) ? static_cast<void> (0) : __assert_fail ("PreserveLCSSA", "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 2589, __PRETTY_FUNCTION__)); | ||||
| 2590 | SmallVector<Instruction *, 1> ToUpdate; | ||||
| 2591 | |||||
| 2592 | auto *OpV = User->getOperand(OpIdx); | ||||
| 2593 | auto *OpI = dyn_cast<Instruction>(OpV); | ||||
| 2594 | if (!OpI) | ||||
| 2595 | return OpV; | ||||
| 2596 | |||||
| 2597 | Loop *DefLoop = SE.LI.getLoopFor(OpI->getParent()); | ||||
| 2598 | Loop *UseLoop = SE.LI.getLoopFor(User->getParent()); | ||||
| 2599 | if (!DefLoop || UseLoop == DefLoop || DefLoop->contains(UseLoop)) | ||||
| 2600 | return OpV; | ||||
| 2601 | |||||
| 2602 | ToUpdate.push_back(OpI); | ||||
| 2603 | SmallVector<PHINode *, 16> PHIsToRemove; | ||||
| 2604 | formLCSSAForInstructions(ToUpdate, SE.DT, SE.LI, &SE, Builder, &PHIsToRemove); | ||||
| 2605 | for (PHINode *PN : PHIsToRemove) { | ||||
| 2606 | if (!PN->use_empty()) | ||||
| 2607 | continue; | ||||
| 2608 | InsertedValues.erase(PN); | ||||
| 2609 | InsertedPostIncValues.erase(PN); | ||||
| 2610 | PN->eraseFromParent(); | ||||
| 2611 | } | ||||
| 2612 | |||||
| 2613 | return User->getOperand(OpIdx); | ||||
| 2614 | } | ||||
| 2615 | |||||
| 2616 | namespace { | ||||
| 2617 | // Search for a SCEV subexpression that is not safe to expand. Any expression | ||||
| 2618 | // that may expand to a !isSafeToSpeculativelyExecute value is unsafe, namely | ||||
| 2619 | // UDiv expressions. We don't know if the UDiv is derived from an IR divide | ||||
| 2620 | // instruction, but the important thing is that we prove the denominator is | ||||
| 2621 | // nonzero before expansion. | ||||
| 2622 | // | ||||
| 2623 | // IVUsers already checks that IV-derived expressions are safe. So this check is | ||||
| 2624 | // only needed when the expression includes some subexpression that is not IV | ||||
| 2625 | // derived. | ||||
| 2626 | // | ||||
| 2627 | // Currently, we only allow division by a nonzero constant here. If this is | ||||
| 2628 | // inadequate, we could easily allow division by SCEVUnknown by using | ||||
| 2629 | // ValueTracking to check isKnownNonZero(). | ||||
| 2630 | // | ||||
| 2631 | // We cannot generally expand recurrences unless the step dominates the loop | ||||
| 2632 | // header. The expander handles the special case of affine recurrences by | ||||
| 2633 | // scaling the recurrence outside the loop, but this technique isn't generally | ||||
| 2634 | // applicable. Expanding a nested recurrence outside a loop requires computing | ||||
| 2635 | // binomial coefficients. This could be done, but the recurrence has to be in a | ||||
| 2636 | // perfectly reduced form, which can't be guaranteed. | ||||
| 2637 | struct SCEVFindUnsafe { | ||||
| 2638 | ScalarEvolution &SE; | ||||
| 2639 | bool IsUnsafe; | ||||
| 2640 | |||||
| 2641 | SCEVFindUnsafe(ScalarEvolution &se): SE(se), IsUnsafe(false) {} | ||||
| 2642 | |||||
| 2643 | bool follow(const SCEV *S) { | ||||
| 2644 | if (const SCEVUDivExpr *D = dyn_cast<SCEVUDivExpr>(S)) { | ||||
| 2645 | const SCEVConstant *SC = dyn_cast<SCEVConstant>(D->getRHS()); | ||||
| 2646 | if (!SC || SC->getValue()->isZero()) { | ||||
| 2647 | IsUnsafe = true; | ||||
| 2648 | return false; | ||||
| 2649 | } | ||||
| 2650 | } | ||||
| 2651 | if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { | ||||
| 2652 | const SCEV *Step = AR->getStepRecurrence(SE); | ||||
| 2653 | if (!AR->isAffine() && !SE.dominates(Step, AR->getLoop()->getHeader())) { | ||||
| 2654 | IsUnsafe = true; | ||||
| 2655 | return false; | ||||
| 2656 | } | ||||
| 2657 | } | ||||
| 2658 | return true; | ||||
| 2659 | } | ||||
| 2660 | bool isDone() const { return IsUnsafe; } | ||||
| 2661 | }; | ||||
| 2662 | } | ||||
| 2663 | |||||
| 2664 | namespace llvm { | ||||
| 2665 | bool isSafeToExpand(const SCEV *S, ScalarEvolution &SE) { | ||||
| 2666 | SCEVFindUnsafe Search(SE); | ||||
| 2667 | visitAll(S, Search); | ||||
| 2668 | return !Search.IsUnsafe; | ||||
| 2669 | } | ||||
| 2670 | |||||
| 2671 | bool isSafeToExpandAt(const SCEV *S, const Instruction *InsertionPoint, | ||||
| 2672 | ScalarEvolution &SE) { | ||||
| 2673 | if (!isSafeToExpand(S, SE)) | ||||
| 2674 | return false; | ||||
| 2675 | // We have to prove that the expanded site of S dominates InsertionPoint. | ||||
| 2676 | // This is easy when not in the same block, but hard when S is an instruction | ||||
| 2677 | // to be expanded somewhere inside the same block as our insertion point. | ||||
| 2678 | // What we really need here is something analogous to an OrderedBasicBlock, | ||||
| 2679 | // but for the moment, we paper over the problem by handling two common and | ||||
| 2680 | // cheap to check cases. | ||||
| 2681 | if (SE.properlyDominates(S, InsertionPoint->getParent())) | ||||
| 2682 | return true; | ||||
| 2683 | if (SE.dominates(S, InsertionPoint->getParent())) { | ||||
| 2684 | if (InsertionPoint->getParent()->getTerminator() == InsertionPoint) | ||||
| 2685 | return true; | ||||
| 2686 | if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) | ||||
| 2687 | for (const Value *V : InsertionPoint->operand_values()) | ||||
| 2688 | if (V == U->getValue()) | ||||
| 2689 | return true; | ||||
| 2690 | } | ||||
| 2691 | return false; | ||||
| 2692 | } | ||||
| 2693 | |||||
| 2694 | SCEVExpanderCleaner::~SCEVExpanderCleaner() { | ||||
| 2695 | // Result is used, nothing to remove. | ||||
| 2696 | if (ResultUsed) | ||||
| 2697 | return; | ||||
| 2698 | |||||
| 2699 | auto InsertedInstructions = Expander.getAllInsertedInstructions(); | ||||
| 2700 | #ifndef NDEBUG | ||||
| 2701 | SmallPtrSet<Instruction *, 8> InsertedSet(InsertedInstructions.begin(), | ||||
| 2702 | InsertedInstructions.end()); | ||||
| 2703 | (void)InsertedSet; | ||||
| 2704 | #endif | ||||
| 2705 | // Remove sets with value handles. | ||||
| 2706 | Expander.clear(); | ||||
| 2707 | |||||
| 2708 | // Sort so that earlier instructions do not dominate later instructions. | ||||
| 2709 | stable_sort(InsertedInstructions, [this](Instruction *A, Instruction *B) { | ||||
| 2710 | return DT.dominates(B, A); | ||||
| 2711 | }); | ||||
| 2712 | // Remove all inserted instructions. | ||||
| 2713 | for (Instruction *I : InsertedInstructions) { | ||||
| 2714 | |||||
| 2715 | #ifndef NDEBUG | ||||
| 2716 | assert(all_of(I->users(),((all_of(I->users(), [&InsertedSet](Value *U) { return InsertedSet.contains(cast<Instruction>(U)); }) && "removed instruction should only be used by instructions inserted " "during expansion") ? static_cast<void> (0) : __assert_fail ("all_of(I->users(), [&InsertedSet](Value *U) { return InsertedSet.contains(cast<Instruction>(U)); }) && \"removed instruction should only be used by instructions inserted \" \"during expansion\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 2721, __PRETTY_FUNCTION__)) | ||||
| 2717 | [&InsertedSet](Value *U) {((all_of(I->users(), [&InsertedSet](Value *U) { return InsertedSet.contains(cast<Instruction>(U)); }) && "removed instruction should only be used by instructions inserted " "during expansion") ? static_cast<void> (0) : __assert_fail ("all_of(I->users(), [&InsertedSet](Value *U) { return InsertedSet.contains(cast<Instruction>(U)); }) && \"removed instruction should only be used by instructions inserted \" \"during expansion\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 2721, __PRETTY_FUNCTION__)) | ||||
| 2718 | return InsertedSet.contains(cast<Instruction>(U));((all_of(I->users(), [&InsertedSet](Value *U) { return InsertedSet.contains(cast<Instruction>(U)); }) && "removed instruction should only be used by instructions inserted " "during expansion") ? static_cast<void> (0) : __assert_fail ("all_of(I->users(), [&InsertedSet](Value *U) { return InsertedSet.contains(cast<Instruction>(U)); }) && \"removed instruction should only be used by instructions inserted \" \"during expansion\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 2721, __PRETTY_FUNCTION__)) | ||||
| 2719 | }) &&((all_of(I->users(), [&InsertedSet](Value *U) { return InsertedSet.contains(cast<Instruction>(U)); }) && "removed instruction should only be used by instructions inserted " "during expansion") ? static_cast<void> (0) : __assert_fail ("all_of(I->users(), [&InsertedSet](Value *U) { return InsertedSet.contains(cast<Instruction>(U)); }) && \"removed instruction should only be used by instructions inserted \" \"during expansion\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 2721, __PRETTY_FUNCTION__)) | ||||
| 2720 | "removed instruction should only be used by instructions inserted "((all_of(I->users(), [&InsertedSet](Value *U) { return InsertedSet.contains(cast<Instruction>(U)); }) && "removed instruction should only be used by instructions inserted " "during expansion") ? static_cast<void> (0) : __assert_fail ("all_of(I->users(), [&InsertedSet](Value *U) { return InsertedSet.contains(cast<Instruction>(U)); }) && \"removed instruction should only be used by instructions inserted \" \"during expansion\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 2721, __PRETTY_FUNCTION__)) | ||||
| 2721 | "during expansion")((all_of(I->users(), [&InsertedSet](Value *U) { return InsertedSet.contains(cast<Instruction>(U)); }) && "removed instruction should only be used by instructions inserted " "during expansion") ? static_cast<void> (0) : __assert_fail ("all_of(I->users(), [&InsertedSet](Value *U) { return InsertedSet.contains(cast<Instruction>(U)); }) && \"removed instruction should only be used by instructions inserted \" \"during expansion\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 2721, __PRETTY_FUNCTION__)); | ||||
| 2722 | #endif | ||||
| 2723 | assert(!I->getType()->isVoidTy() &&((!I->getType()->isVoidTy() && "inserted instruction should have non-void types" ) ? static_cast<void> (0) : __assert_fail ("!I->getType()->isVoidTy() && \"inserted instruction should have non-void types\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 2724, __PRETTY_FUNCTION__)) | ||||
| 2724 | "inserted instruction should have non-void types")((!I->getType()->isVoidTy() && "inserted instruction should have non-void types" ) ? static_cast<void> (0) : __assert_fail ("!I->getType()->isVoidTy() && \"inserted instruction should have non-void types\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp" , 2724, __PRETTY_FUNCTION__)); | ||||
| 2725 | I->replaceAllUsesWith(UndefValue::get(I->getType())); | ||||
| 2726 | I->eraseFromParent(); | ||||
| 2727 | } | ||||
| 2728 | } | ||||
| 2729 | } |
| 1 | //===- llvm/DataLayout.h - Data size & alignment info -----------*- 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 layout properties related to datatype size/offset/alignment | |||
| 10 | // information. It uses lazy annotations to cache information about how | |||
| 11 | // structure types are laid out and used. | |||
| 12 | // | |||
| 13 | // This structure should be created once, filled in if the defaults are not | |||
| 14 | // correct and then passed around by const&. None of the members functions | |||
| 15 | // require modification to the object. | |||
| 16 | // | |||
| 17 | //===----------------------------------------------------------------------===// | |||
| 18 | ||||
| 19 | #ifndef LLVM_IR_DATALAYOUT_H | |||
| 20 | #define LLVM_IR_DATALAYOUT_H | |||
| 21 | ||||
| 22 | #include "llvm/ADT/ArrayRef.h" | |||
| 23 | #include "llvm/ADT/STLExtras.h" | |||
| 24 | #include "llvm/ADT/SmallVector.h" | |||
| 25 | #include "llvm/ADT/StringRef.h" | |||
| 26 | #include "llvm/IR/DerivedTypes.h" | |||
| 27 | #include "llvm/IR/Type.h" | |||
| 28 | #include "llvm/Support/Casting.h" | |||
| 29 | #include "llvm/Support/ErrorHandling.h" | |||
| 30 | #include "llvm/Support/MathExtras.h" | |||
| 31 | #include "llvm/Support/Alignment.h" | |||
| 32 | #include "llvm/Support/TypeSize.h" | |||
| 33 | #include <cassert> | |||
| 34 | #include <cstdint> | |||
| 35 | #include <string> | |||
| 36 | ||||
| 37 | // This needs to be outside of the namespace, to avoid conflict with llvm-c | |||
| 38 | // decl. | |||
| 39 | using LLVMTargetDataRef = struct LLVMOpaqueTargetData *; | |||
| 40 | ||||
| 41 | namespace llvm { | |||
| 42 | ||||
| 43 | class GlobalVariable; | |||
| 44 | class LLVMContext; | |||
| 45 | class Module; | |||
| 46 | class StructLayout; | |||
| 47 | class Triple; | |||
| 48 | class Value; | |||
| 49 | ||||
| 50 | /// Enum used to categorize the alignment types stored by LayoutAlignElem | |||
| 51 | enum AlignTypeEnum { | |||
| 52 | INVALID_ALIGN = 0, | |||
| 53 | INTEGER_ALIGN = 'i', | |||
| 54 | VECTOR_ALIGN = 'v', | |||
| 55 | FLOAT_ALIGN = 'f', | |||
| 56 | AGGREGATE_ALIGN = 'a' | |||
| 57 | }; | |||
| 58 | ||||
| 59 | // FIXME: Currently the DataLayout string carries a "preferred alignment" | |||
| 60 | // for types. As the DataLayout is module/global, this should likely be | |||
| 61 | // sunk down to an FTTI element that is queried rather than a global | |||
| 62 | // preference. | |||
| 63 | ||||
| 64 | /// Layout alignment element. | |||
| 65 | /// | |||
| 66 | /// Stores the alignment data associated with a given alignment type (integer, | |||
| 67 | /// vector, float) and type bit width. | |||
| 68 | /// | |||
| 69 | /// \note The unusual order of elements in the structure attempts to reduce | |||
| 70 | /// padding and make the structure slightly more cache friendly. | |||
| 71 | struct LayoutAlignElem { | |||
| 72 | /// Alignment type from \c AlignTypeEnum | |||
| 73 | unsigned AlignType : 8; | |||
| 74 | unsigned TypeBitWidth : 24; | |||
| 75 | Align ABIAlign; | |||
| 76 | Align PrefAlign; | |||
| 77 | ||||
| 78 | static LayoutAlignElem get(AlignTypeEnum align_type, Align abi_align, | |||
| 79 | Align pref_align, uint32_t bit_width); | |||
| 80 | ||||
| 81 | bool operator==(const LayoutAlignElem &rhs) const; | |||
| 82 | }; | |||
| 83 | ||||
| 84 | /// Layout pointer alignment element. | |||
| 85 | /// | |||
| 86 | /// Stores the alignment data associated with a given pointer and address space. | |||
| 87 | /// | |||
| 88 | /// \note The unusual order of elements in the structure attempts to reduce | |||
| 89 | /// padding and make the structure slightly more cache friendly. | |||
| 90 | struct PointerAlignElem { | |||
| 91 | Align ABIAlign; | |||
| 92 | Align PrefAlign; | |||
| 93 | uint32_t TypeByteWidth; | |||
| 94 | uint32_t AddressSpace; | |||
| 95 | uint32_t IndexWidth; | |||
| 96 | ||||
| 97 | /// Initializer | |||
| 98 | static PointerAlignElem get(uint32_t AddressSpace, Align ABIAlign, | |||
| 99 | Align PrefAlign, uint32_t TypeByteWidth, | |||
| 100 | uint32_t IndexWidth); | |||
| 101 | ||||
| 102 | bool operator==(const PointerAlignElem &rhs) const; | |||
| 103 | }; | |||
| 104 | ||||
| 105 | /// A parsed version of the target data layout string in and methods for | |||
| 106 | /// querying it. | |||
| 107 | /// | |||
| 108 | /// The target data layout string is specified *by the target* - a frontend | |||
| 109 | /// generating LLVM IR is required to generate the right target data for the | |||
| 110 | /// target being codegen'd to. | |||
| 111 | class DataLayout { | |||
| 112 | public: | |||
| 113 | enum class FunctionPtrAlignType { | |||
| 114 | /// The function pointer alignment is independent of the function alignment. | |||
| 115 | Independent, | |||
| 116 | /// The function pointer alignment is a multiple of the function alignment. | |||
| 117 | MultipleOfFunctionAlign, | |||
| 118 | }; | |||
| 119 | private: | |||
| 120 | /// Defaults to false. | |||
| 121 | bool BigEndian; | |||
| 122 | ||||
| 123 | unsigned AllocaAddrSpace; | |||
| 124 | MaybeAlign StackNaturalAlign; | |||
| 125 | unsigned ProgramAddrSpace; | |||
| 126 | ||||
| 127 | MaybeAlign FunctionPtrAlign; | |||
| 128 | FunctionPtrAlignType TheFunctionPtrAlignType; | |||
| 129 | ||||
| 130 | enum ManglingModeT { | |||
| 131 | MM_None, | |||
| 132 | MM_ELF, | |||
| 133 | MM_MachO, | |||
| 134 | MM_WinCOFF, | |||
| 135 | MM_WinCOFFX86, | |||
| 136 | MM_Mips, | |||
| 137 | MM_XCOFF | |||
| 138 | }; | |||
| 139 | ManglingModeT ManglingMode; | |||
| 140 | ||||
| 141 | SmallVector<unsigned char, 8> LegalIntWidths; | |||
| 142 | ||||
| 143 | /// Primitive type alignment data. This is sorted by type and bit | |||
| 144 | /// width during construction. | |||
| 145 | using AlignmentsTy = SmallVector<LayoutAlignElem, 16>; | |||
| 146 | AlignmentsTy Alignments; | |||
| 147 | ||||
| 148 | AlignmentsTy::const_iterator | |||
| 149 | findAlignmentLowerBound(AlignTypeEnum AlignType, uint32_t BitWidth) const { | |||
| 150 | return const_cast<DataLayout *>(this)->findAlignmentLowerBound(AlignType, | |||
| 151 | BitWidth); | |||
| 152 | } | |||
| 153 | ||||
| 154 | AlignmentsTy::iterator | |||
| 155 | findAlignmentLowerBound(AlignTypeEnum AlignType, uint32_t BitWidth); | |||
| 156 | ||||
| 157 | /// The string representation used to create this DataLayout | |||
| 158 | std::string StringRepresentation; | |||
| 159 | ||||
| 160 | using PointersTy = SmallVector<PointerAlignElem, 8>; | |||
| 161 | PointersTy Pointers; | |||
| 162 | ||||
| 163 | PointersTy::const_iterator | |||
| 164 | findPointerLowerBound(uint32_t AddressSpace) const { | |||
| 165 | return const_cast<DataLayout *>(this)->findPointerLowerBound(AddressSpace); | |||
| 166 | } | |||
| 167 | ||||
| 168 | PointersTy::iterator findPointerLowerBound(uint32_t AddressSpace); | |||
| 169 | ||||
| 170 | // The StructType -> StructLayout map. | |||
| 171 | mutable void *LayoutMap = nullptr; | |||
| 172 | ||||
| 173 | /// Pointers in these address spaces are non-integral, and don't have a | |||
| 174 | /// well-defined bitwise representation. | |||
| 175 | SmallVector<unsigned, 8> NonIntegralAddressSpaces; | |||
| 176 | ||||
| 177 | /// Attempts to set the alignment of the given type. Returns an error | |||
| 178 | /// description on failure. | |||
| 179 | Error setAlignment(AlignTypeEnum align_type, Align abi_align, | |||
| 180 | Align pref_align, uint32_t bit_width); | |||
| 181 | ||||
| 182 | Align getAlignmentInfo(AlignTypeEnum align_type, uint32_t bit_width, | |||
| 183 | bool ABIAlign, Type *Ty) const; | |||
| 184 | ||||
| 185 | /// Attempts to set the alignment of a pointer in the given address space. | |||
| 186 | /// Returns an error description on failure. | |||
| 187 | Error setPointerAlignment(uint32_t AddrSpace, Align ABIAlign, Align PrefAlign, | |||
| 188 | uint32_t TypeByteWidth, uint32_t IndexWidth); | |||
| 189 | ||||
| 190 | /// Internal helper method that returns requested alignment for type. | |||
| 191 | Align getAlignment(Type *Ty, bool abi_or_pref) const; | |||
| 192 | ||||
| 193 | /// Attempts to parse a target data specification string and reports an error | |||
| 194 | /// if the string is malformed. | |||
| 195 | Error parseSpecifier(StringRef Desc); | |||
| 196 | ||||
| 197 | // Free all internal data structures. | |||
| 198 | void clear(); | |||
| 199 | ||||
| 200 | public: | |||
| 201 | /// Constructs a DataLayout from a specification string. See reset(). | |||
| 202 | explicit DataLayout(StringRef LayoutDescription) { | |||
| 203 | reset(LayoutDescription); | |||
| 204 | } | |||
| 205 | ||||
| 206 | /// Initialize target data from properties stored in the module. | |||
| 207 | explicit DataLayout(const Module *M); | |||
| 208 | ||||
| 209 | DataLayout(const DataLayout &DL) { *this = DL; } | |||
| 210 | ||||
| 211 | ~DataLayout(); // Not virtual, do not subclass this class | |||
| 212 | ||||
| 213 | DataLayout &operator=(const DataLayout &DL) { | |||
| 214 | clear(); | |||
| 215 | StringRepresentation = DL.StringRepresentation; | |||
| 216 | BigEndian = DL.isBigEndian(); | |||
| 217 | AllocaAddrSpace = DL.AllocaAddrSpace; | |||
| 218 | StackNaturalAlign = DL.StackNaturalAlign; | |||
| 219 | FunctionPtrAlign = DL.FunctionPtrAlign; | |||
| 220 | TheFunctionPtrAlignType = DL.TheFunctionPtrAlignType; | |||
| 221 | ProgramAddrSpace = DL.ProgramAddrSpace; | |||
| 222 | ManglingMode = DL.ManglingMode; | |||
| 223 | LegalIntWidths = DL.LegalIntWidths; | |||
| 224 | Alignments = DL.Alignments; | |||
| 225 | Pointers = DL.Pointers; | |||
| 226 | NonIntegralAddressSpaces = DL.NonIntegralAddressSpaces; | |||
| 227 | return *this; | |||
| 228 | } | |||
| 229 | ||||
| 230 | bool operator==(const DataLayout &Other) const; | |||
| 231 | bool operator!=(const DataLayout &Other) const { return !(*this == Other); } | |||
| 232 | ||||
| 233 | void init(const Module *M); | |||
| 234 | ||||
| 235 | /// Parse a data layout string (with fallback to default values). | |||
| 236 | void reset(StringRef LayoutDescription); | |||
| 237 | ||||
| 238 | /// Parse a data layout string and return the layout. Return an error | |||
| 239 | /// description on failure. | |||
| 240 | static Expected<DataLayout> parse(StringRef LayoutDescription); | |||
| 241 | ||||
| 242 | /// Layout endianness... | |||
| 243 | bool isLittleEndian() const { return !BigEndian; } | |||
| 244 | bool isBigEndian() const { return BigEndian; } | |||
| 245 | ||||
| 246 | /// Returns the string representation of the DataLayout. | |||
| 247 | /// | |||
| 248 | /// This representation is in the same format accepted by the string | |||
| 249 | /// constructor above. This should not be used to compare two DataLayout as | |||
| 250 | /// different string can represent the same layout. | |||
| 251 | const std::string &getStringRepresentation() const { | |||
| 252 | return StringRepresentation; | |||
| 253 | } | |||
| 254 | ||||
| 255 | /// Test if the DataLayout was constructed from an empty string. | |||
| 256 | bool isDefault() const { return StringRepresentation.empty(); } | |||
| 257 | ||||
| 258 | /// Returns true if the specified type is known to be a native integer | |||
| 259 | /// type supported by the CPU. | |||
| 260 | /// | |||
| 261 | /// For example, i64 is not native on most 32-bit CPUs and i37 is not native | |||
| 262 | /// on any known one. This returns false if the integer width is not legal. | |||
| 263 | /// | |||
| 264 | /// The width is specified in bits. | |||
| 265 | bool isLegalInteger(uint64_t Width) const { | |||
| 266 | for (unsigned LegalIntWidth : LegalIntWidths) | |||
| 267 | if (LegalIntWidth == Width) | |||
| 268 | return true; | |||
| 269 | return false; | |||
| 270 | } | |||
| 271 | ||||
| 272 | bool isIllegalInteger(uint64_t Width) const { return !isLegalInteger(Width); } | |||
| 273 | ||||
| 274 | /// Returns true if the given alignment exceeds the natural stack alignment. | |||
| 275 | bool exceedsNaturalStackAlignment(Align Alignment) const { | |||
| 276 | return StackNaturalAlign && (Alignment > *StackNaturalAlign); | |||
| 277 | } | |||
| 278 | ||||
| 279 | Align getStackAlignment() const { | |||
| 280 | assert(StackNaturalAlign && "StackNaturalAlign must be defined")((StackNaturalAlign && "StackNaturalAlign must be defined" ) ? static_cast<void> (0) : __assert_fail ("StackNaturalAlign && \"StackNaturalAlign must be defined\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/include/llvm/IR/DataLayout.h" , 280, __PRETTY_FUNCTION__)); | |||
| 281 | return *StackNaturalAlign; | |||
| 282 | } | |||
| 283 | ||||
| 284 | unsigned getAllocaAddrSpace() const { return AllocaAddrSpace; } | |||
| 285 | ||||
| 286 | /// Returns the alignment of function pointers, which may or may not be | |||
| 287 | /// related to the alignment of functions. | |||
| 288 | /// \see getFunctionPtrAlignType | |||
| 289 | MaybeAlign getFunctionPtrAlign() const { return FunctionPtrAlign; } | |||
| 290 | ||||
| 291 | /// Return the type of function pointer alignment. | |||
| 292 | /// \see getFunctionPtrAlign | |||
| 293 | FunctionPtrAlignType getFunctionPtrAlignType() const { | |||
| 294 | return TheFunctionPtrAlignType; | |||
| 295 | } | |||
| 296 | ||||
| 297 | unsigned getProgramAddressSpace() const { return ProgramAddrSpace; } | |||
| 298 | ||||
| 299 | bool hasMicrosoftFastStdCallMangling() const { | |||
| 300 | return ManglingMode == MM_WinCOFFX86; | |||
| 301 | } | |||
| 302 | ||||
| 303 | /// Returns true if symbols with leading question marks should not receive IR | |||
| 304 | /// mangling. True for Windows mangling modes. | |||
| 305 | bool doNotMangleLeadingQuestionMark() const { | |||
| 306 | return ManglingMode == MM_WinCOFF || ManglingMode == MM_WinCOFFX86; | |||
| 307 | } | |||
| 308 | ||||
| 309 | bool hasLinkerPrivateGlobalPrefix() const { return ManglingMode == MM_MachO; } | |||
| 310 | ||||
| 311 | StringRef getLinkerPrivateGlobalPrefix() const { | |||
| 312 | if (ManglingMode == MM_MachO) | |||
| 313 | return "l"; | |||
| 314 | return ""; | |||
| 315 | } | |||
| 316 | ||||
| 317 | char getGlobalPrefix() const { | |||
| 318 | switch (ManglingMode) { | |||
| 319 | case MM_None: | |||
| 320 | case MM_ELF: | |||
| 321 | case MM_Mips: | |||
| 322 | case MM_WinCOFF: | |||
| 323 | case MM_XCOFF: | |||
| 324 | return '\0'; | |||
| 325 | case MM_MachO: | |||
| 326 | case MM_WinCOFFX86: | |||
| 327 | return '_'; | |||
| 328 | } | |||
| 329 | llvm_unreachable("invalid mangling mode")::llvm::llvm_unreachable_internal("invalid mangling mode", "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/include/llvm/IR/DataLayout.h" , 329); | |||
| 330 | } | |||
| 331 | ||||
| 332 | StringRef getPrivateGlobalPrefix() const { | |||
| 333 | switch (ManglingMode) { | |||
| 334 | case MM_None: | |||
| 335 | return ""; | |||
| 336 | case MM_ELF: | |||
| 337 | case MM_WinCOFF: | |||
| 338 | return ".L"; | |||
| 339 | case MM_Mips: | |||
| 340 | return "$"; | |||
| 341 | case MM_MachO: | |||
| 342 | case MM_WinCOFFX86: | |||
| 343 | return "L"; | |||
| 344 | case MM_XCOFF: | |||
| 345 | return "L.."; | |||
| 346 | } | |||
| 347 | llvm_unreachable("invalid mangling mode")::llvm::llvm_unreachable_internal("invalid mangling mode", "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/include/llvm/IR/DataLayout.h" , 347); | |||
| 348 | } | |||
| 349 | ||||
| 350 | static const char *getManglingComponent(const Triple &T); | |||
| 351 | ||||
| 352 | /// Returns true if the specified type fits in a native integer type | |||
| 353 | /// supported by the CPU. | |||
| 354 | /// | |||
| 355 | /// For example, if the CPU only supports i32 as a native integer type, then | |||
| 356 | /// i27 fits in a legal integer type but i45 does not. | |||
| 357 | bool fitsInLegalInteger(unsigned Width) const { | |||
| 358 | for (unsigned LegalIntWidth : LegalIntWidths) | |||
| 359 | if (Width <= LegalIntWidth) | |||
| 360 | return true; | |||
| 361 | return false; | |||
| 362 | } | |||
| 363 | ||||
| 364 | /// Layout pointer alignment | |||
| 365 | Align getPointerABIAlignment(unsigned AS) const; | |||
| 366 | ||||
| 367 | /// Return target's alignment for stack-based pointers | |||
| 368 | /// FIXME: The defaults need to be removed once all of | |||
| 369 | /// the backends/clients are updated. | |||
| 370 | Align getPointerPrefAlignment(unsigned AS = 0) const; | |||
| 371 | ||||
| 372 | /// Layout pointer size | |||
| 373 | /// FIXME: The defaults need to be removed once all of | |||
| 374 | /// the backends/clients are updated. | |||
| 375 | unsigned getPointerSize(unsigned AS = 0) const; | |||
| 376 | ||||
| 377 | /// Returns the maximum pointer size over all address spaces. | |||
| 378 | unsigned getMaxPointerSize() const; | |||
| 379 | ||||
| 380 | // Index size used for address calculation. | |||
| 381 | unsigned getIndexSize(unsigned AS) const; | |||
| 382 | ||||
| 383 | /// Return the address spaces containing non-integral pointers. Pointers in | |||
| 384 | /// this address space don't have a well-defined bitwise representation. | |||
| 385 | ArrayRef<unsigned> getNonIntegralAddressSpaces() const { | |||
| 386 | return NonIntegralAddressSpaces; | |||
| 387 | } | |||
| 388 | ||||
| 389 | bool isNonIntegralAddressSpace(unsigned AddrSpace) const { | |||
| 390 | ArrayRef<unsigned> NonIntegralSpaces = getNonIntegralAddressSpaces(); | |||
| 391 | return find(NonIntegralSpaces, AddrSpace) != NonIntegralSpaces.end(); | |||
| 392 | } | |||
| 393 | ||||
| 394 | bool isNonIntegralPointerType(PointerType *PT) const { | |||
| 395 | return isNonIntegralAddressSpace(PT->getAddressSpace()); | |||
| ||||
| 396 | } | |||
| 397 | ||||
| 398 | bool isNonIntegralPointerType(Type *Ty) const { | |||
| 399 | auto *PTy = dyn_cast<PointerType>(Ty); | |||
| 400 | return PTy && isNonIntegralPointerType(PTy); | |||
| 401 | } | |||
| 402 | ||||
| 403 | /// Layout pointer size, in bits | |||
| 404 | /// FIXME: The defaults need to be removed once all of | |||
| 405 | /// the backends/clients are updated. | |||
| 406 | unsigned getPointerSizeInBits(unsigned AS = 0) const { | |||
| 407 | return getPointerSize(AS) * 8; | |||
| 408 | } | |||
| 409 | ||||
| 410 | /// Returns the maximum pointer size over all address spaces. | |||
| 411 | unsigned getMaxPointerSizeInBits() const { | |||
| 412 | return getMaxPointerSize() * 8; | |||
| 413 | } | |||
| 414 | ||||
| 415 | /// Size in bits of index used for address calculation in getelementptr. | |||
| 416 | unsigned getIndexSizeInBits(unsigned AS) const { | |||
| 417 | return getIndexSize(AS) * 8; | |||
| 418 | } | |||
| 419 | ||||
| 420 | /// Layout pointer size, in bits, based on the type. If this function is | |||
| 421 | /// called with a pointer type, then the type size of the pointer is returned. | |||
| 422 | /// If this function is called with a vector of pointers, then the type size | |||
| 423 | /// of the pointer is returned. This should only be called with a pointer or | |||
| 424 | /// vector of pointers. | |||
| 425 | unsigned getPointerTypeSizeInBits(Type *) const; | |||
| 426 | ||||
| 427 | /// Layout size of the index used in GEP calculation. | |||
| 428 | /// The function should be called with pointer or vector of pointers type. | |||
| 429 | unsigned getIndexTypeSizeInBits(Type *Ty) const; | |||
| 430 | ||||
| 431 | unsigned getPointerTypeSize(Type *Ty) const { | |||
| 432 | return getPointerTypeSizeInBits(Ty) / 8; | |||
| 433 | } | |||
| 434 | ||||
| 435 | /// Size examples: | |||
| 436 | /// | |||
| 437 | /// Type SizeInBits StoreSizeInBits AllocSizeInBits[*] | |||
| 438 | /// ---- ---------- --------------- --------------- | |||
| 439 | /// i1 1 8 8 | |||
| 440 | /// i8 8 8 8 | |||
| 441 | /// i19 19 24 32 | |||
| 442 | /// i32 32 32 32 | |||
| 443 | /// i100 100 104 128 | |||
| 444 | /// i128 128 128 128 | |||
| 445 | /// Float 32 32 32 | |||
| 446 | /// Double 64 64 64 | |||
| 447 | /// X86_FP80 80 80 96 | |||
| 448 | /// | |||
| 449 | /// [*] The alloc size depends on the alignment, and thus on the target. | |||
| 450 | /// These values are for x86-32 linux. | |||
| 451 | ||||
| 452 | /// Returns the number of bits necessary to hold the specified type. | |||
| 453 | /// | |||
| 454 | /// If Ty is a scalable vector type, the scalable property will be set and | |||
| 455 | /// the runtime size will be a positive integer multiple of the base size. | |||
| 456 | /// | |||
| 457 | /// For example, returns 36 for i36 and 80 for x86_fp80. The type passed must | |||
| 458 | /// have a size (Type::isSized() must return true). | |||
| 459 | TypeSize getTypeSizeInBits(Type *Ty) const; | |||
| 460 | ||||
| 461 | /// Returns the maximum number of bytes that may be overwritten by | |||
| 462 | /// storing the specified type. | |||
| 463 | /// | |||
| 464 | /// If Ty is a scalable vector type, the scalable property will be set and | |||
| 465 | /// the runtime size will be a positive integer multiple of the base size. | |||
| 466 | /// | |||
| 467 | /// For example, returns 5 for i36 and 10 for x86_fp80. | |||
| 468 | TypeSize getTypeStoreSize(Type *Ty) const { | |||
| 469 | TypeSize BaseSize = getTypeSizeInBits(Ty); | |||
| 470 | return { (BaseSize.getKnownMinSize() + 7) / 8, BaseSize.isScalable() }; | |||
| 471 | } | |||
| 472 | ||||
| 473 | /// Returns the maximum number of bits that may be overwritten by | |||
| 474 | /// storing the specified type; always a multiple of 8. | |||
| 475 | /// | |||
| 476 | /// If Ty is a scalable vector type, the scalable property will be set and | |||
| 477 | /// the runtime size will be a positive integer multiple of the base size. | |||
| 478 | /// | |||
| 479 | /// For example, returns 40 for i36 and 80 for x86_fp80. | |||
| 480 | TypeSize getTypeStoreSizeInBits(Type *Ty) const { | |||
| 481 | return 8 * getTypeStoreSize(Ty); | |||
| 482 | } | |||
| 483 | ||||
| 484 | /// Returns true if no extra padding bits are needed when storing the | |||
| 485 | /// specified type. | |||
| 486 | /// | |||
| 487 | /// For example, returns false for i19 that has a 24-bit store size. | |||
| 488 | bool typeSizeEqualsStoreSize(Type *Ty) const { | |||
| 489 | return getTypeSizeInBits(Ty) == getTypeStoreSizeInBits(Ty); | |||
| 490 | } | |||
| 491 | ||||
| 492 | /// Returns the offset in bytes between successive objects of the | |||
| 493 | /// specified type, including alignment padding. | |||
| 494 | /// | |||
| 495 | /// If Ty is a scalable vector type, the scalable property will be set and | |||
| 496 | /// the runtime size will be a positive integer multiple of the base size. | |||
| 497 | /// | |||
| 498 | /// This is the amount that alloca reserves for this type. For example, | |||
| 499 | /// returns 12 or 16 for x86_fp80, depending on alignment. | |||
| 500 | TypeSize getTypeAllocSize(Type *Ty) const { | |||
| 501 | // Round up to the next alignment boundary. | |||
| 502 | return alignTo(getTypeStoreSize(Ty), getABITypeAlignment(Ty)); | |||
| 503 | } | |||
| 504 | ||||
| 505 | /// Returns the offset in bits between successive objects of the | |||
| 506 | /// specified type, including alignment padding; always a multiple of 8. | |||
| 507 | /// | |||
| 508 | /// If Ty is a scalable vector type, the scalable property will be set and | |||
| 509 | /// the runtime size will be a positive integer multiple of the base size. | |||
| 510 | /// | |||
| 511 | /// This is the amount that alloca reserves for this type. For example, | |||
| 512 | /// returns 96 or 128 for x86_fp80, depending on alignment. | |||
| 513 | TypeSize getTypeAllocSizeInBits(Type *Ty) const { | |||
| 514 | return 8 * getTypeAllocSize(Ty); | |||
| 515 | } | |||
| 516 | ||||
| 517 | /// Returns the minimum ABI-required alignment for the specified type. | |||
| 518 | /// FIXME: Deprecate this function once migration to Align is over. | |||
| 519 | unsigned getABITypeAlignment(Type *Ty) const; | |||
| 520 | ||||
| 521 | /// Returns the minimum ABI-required alignment for the specified type. | |||
| 522 | Align getABITypeAlign(Type *Ty) const; | |||
| 523 | ||||
| 524 | /// Helper function to return `Alignment` if it's set or the result of | |||
| 525 | /// `getABITypeAlignment(Ty)`, in any case the result is a valid alignment. | |||
| 526 | inline Align getValueOrABITypeAlignment(MaybeAlign Alignment, | |||
| 527 | Type *Ty) const { | |||
| 528 | return Alignment ? *Alignment : getABITypeAlign(Ty); | |||
| 529 | } | |||
| 530 | ||||
| 531 | /// Returns the minimum ABI-required alignment for an integer type of | |||
| 532 | /// the specified bitwidth. | |||
| 533 | Align getABIIntegerTypeAlignment(unsigned BitWidth) const; | |||
| 534 | ||||
| 535 | /// Returns the preferred stack/global alignment for the specified | |||
| 536 | /// type. | |||
| 537 | /// | |||
| 538 | /// This is always at least as good as the ABI alignment. | |||
| 539 | /// FIXME: Deprecate this function once migration to Align is over. | |||
| 540 | unsigned getPrefTypeAlignment(Type *Ty) const; | |||
| 541 | ||||
| 542 | /// Returns the preferred stack/global alignment for the specified | |||
| 543 | /// type. | |||
| 544 | /// | |||
| 545 | /// This is always at least as good as the ABI alignment. | |||
| 546 | Align getPrefTypeAlign(Type *Ty) const; | |||
| 547 | ||||
| 548 | /// Returns an integer type with size at least as big as that of a | |||
| 549 | /// pointer in the given address space. | |||
| 550 | IntegerType *getIntPtrType(LLVMContext &C, unsigned AddressSpace = 0) const; | |||
| 551 | ||||
| 552 | /// Returns an integer (vector of integer) type with size at least as | |||
| 553 | /// big as that of a pointer of the given pointer (vector of pointer) type. | |||
| 554 | Type *getIntPtrType(Type *) const; | |||
| 555 | ||||
| 556 | /// Returns the smallest integer type with size at least as big as | |||
| 557 | /// Width bits. | |||
| 558 | Type *getSmallestLegalIntType(LLVMContext &C, unsigned Width = 0) const; | |||
| 559 | ||||
| 560 | /// Returns the largest legal integer type, or null if none are set. | |||
| 561 | Type *getLargestLegalIntType(LLVMContext &C) const { | |||
| 562 | unsigned LargestSize = getLargestLegalIntTypeSizeInBits(); | |||
| 563 | return (LargestSize == 0) ? nullptr : Type::getIntNTy(C, LargestSize); | |||
| 564 | } | |||
| 565 | ||||
| 566 | /// Returns the size of largest legal integer type size, or 0 if none | |||
| 567 | /// are set. | |||
| 568 | unsigned getLargestLegalIntTypeSizeInBits() const; | |||
| 569 | ||||
| 570 | /// Returns the type of a GEP index. | |||
| 571 | /// If it was not specified explicitly, it will be the integer type of the | |||
| 572 | /// pointer width - IntPtrType. | |||
| 573 | Type *getIndexType(Type *PtrTy) const; | |||
| 574 | ||||
| 575 | /// Returns the offset from the beginning of the type for the specified | |||
| 576 | /// indices. | |||
| 577 | /// | |||
| 578 | /// Note that this takes the element type, not the pointer type. | |||
| 579 | /// This is used to implement getelementptr. | |||
| 580 | int64_t getIndexedOffsetInType(Type *ElemTy, ArrayRef<Value *> Indices) const; | |||
| 581 | ||||
| 582 | /// Returns a StructLayout object, indicating the alignment of the | |||
| 583 | /// struct, its size, and the offsets of its fields. | |||
| 584 | /// | |||
| 585 | /// Note that this information is lazily cached. | |||
| 586 | const StructLayout *getStructLayout(StructType *Ty) const; | |||
| 587 | ||||
| 588 | /// Returns the preferred alignment of the specified global. | |||
| 589 | /// | |||
| 590 | /// This includes an explicitly requested alignment (if the global has one). | |||
| 591 | Align getPreferredAlign(const GlobalVariable *GV) const; | |||
| 592 | ||||
| 593 | /// Returns the preferred alignment of the specified global. | |||
| 594 | /// | |||
| 595 | /// This includes an explicitly requested alignment (if the global has one). | |||
| 596 | LLVM_ATTRIBUTE_DEPRECATED(inline unsigned getPreferredAlignment(const GlobalVariable *GV ) const __attribute__((deprecated("Use getPreferredAlign instead" ))) | |||
| 597 | inline unsigned getPreferredAlignment(const GlobalVariable *GV) const,inline unsigned getPreferredAlignment(const GlobalVariable *GV ) const __attribute__((deprecated("Use getPreferredAlign instead" ))) | |||
| 598 | "Use getPreferredAlign instead")inline unsigned getPreferredAlignment(const GlobalVariable *GV ) const __attribute__((deprecated("Use getPreferredAlign instead" ))) { | |||
| 599 | return getPreferredAlign(GV).value(); | |||
| 600 | } | |||
| 601 | ||||
| 602 | /// Returns the preferred alignment of the specified global, returned | |||
| 603 | /// in log form. | |||
| 604 | /// | |||
| 605 | /// This includes an explicitly requested alignment (if the global has one). | |||
| 606 | LLVM_ATTRIBUTE_DEPRECATED(inline unsigned getPreferredAlignmentLog(const GlobalVariable *GV) const __attribute__((deprecated("Inline where needed")) ) | |||
| 607 | inline unsigned getPreferredAlignmentLog(const GlobalVariable *GV) const,inline unsigned getPreferredAlignmentLog(const GlobalVariable *GV) const __attribute__((deprecated("Inline where needed")) ) | |||
| 608 | "Inline where needed")inline unsigned getPreferredAlignmentLog(const GlobalVariable *GV) const __attribute__((deprecated("Inline where needed")) ) { | |||
| 609 | return Log2(getPreferredAlign(GV)); | |||
| 610 | } | |||
| 611 | }; | |||
| 612 | ||||
| 613 | inline DataLayout *unwrap(LLVMTargetDataRef P) { | |||
| 614 | return reinterpret_cast<DataLayout *>(P); | |||
| 615 | } | |||
| 616 | ||||
| 617 | inline LLVMTargetDataRef wrap(const DataLayout *P) { | |||
| 618 | return reinterpret_cast<LLVMTargetDataRef>(const_cast<DataLayout *>(P)); | |||
| 619 | } | |||
| 620 | ||||
| 621 | /// Used to lazily calculate structure layout information for a target machine, | |||
| 622 | /// based on the DataLayout structure. | |||
| 623 | class StructLayout { | |||
| 624 | uint64_t StructSize; | |||
| 625 | Align StructAlignment; | |||
| 626 | unsigned IsPadded : 1; | |||
| 627 | unsigned NumElements : 31; | |||
| 628 | uint64_t MemberOffsets[1]; // variable sized array! | |||
| 629 | ||||
| 630 | public: | |||
| 631 | uint64_t getSizeInBytes() const { return StructSize; } | |||
| 632 | ||||
| 633 | uint64_t getSizeInBits() const { return 8 * StructSize; } | |||
| 634 | ||||
| 635 | Align getAlignment() const { return StructAlignment; } | |||
| 636 | ||||
| 637 | /// Returns whether the struct has padding or not between its fields. | |||
| 638 | /// NB: Padding in nested element is not taken into account. | |||
| 639 | bool hasPadding() const { return IsPadded; } | |||
| 640 | ||||
| 641 | /// Given a valid byte offset into the structure, returns the structure | |||
| 642 | /// index that contains it. | |||
| 643 | unsigned getElementContainingOffset(uint64_t Offset) const; | |||
| 644 | ||||
| 645 | uint64_t getElementOffset(unsigned Idx) const { | |||
| 646 | assert(Idx < NumElements && "Invalid element idx!")((Idx < NumElements && "Invalid element idx!") ? static_cast <void> (0) : __assert_fail ("Idx < NumElements && \"Invalid element idx!\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/include/llvm/IR/DataLayout.h" , 646, __PRETTY_FUNCTION__)); | |||
| 647 | return MemberOffsets[Idx]; | |||
| 648 | } | |||
| 649 | ||||
| 650 | uint64_t getElementOffsetInBits(unsigned Idx) const { | |||
| 651 | return getElementOffset(Idx) * 8; | |||
| 652 | } | |||
| 653 | ||||
| 654 | private: | |||
| 655 | friend class DataLayout; // Only DataLayout can create this class | |||
| 656 | ||||
| 657 | StructLayout(StructType *ST, const DataLayout &DL); | |||
| 658 | }; | |||
| 659 | ||||
| 660 | // The implementation of this method is provided inline as it is particularly | |||
| 661 | // well suited to constant folding when called on a specific Type subclass. | |||
| 662 | inline TypeSize DataLayout::getTypeSizeInBits(Type *Ty) const { | |||
| 663 | assert(Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!")((Ty->isSized() && "Cannot getTypeInfo() on a type that is unsized!" ) ? static_cast<void> (0) : __assert_fail ("Ty->isSized() && \"Cannot getTypeInfo() on a type that is unsized!\"" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/include/llvm/IR/DataLayout.h" , 663, __PRETTY_FUNCTION__)); | |||
| 664 | switch (Ty->getTypeID()) { | |||
| 665 | case Type::LabelTyID: | |||
| 666 | return TypeSize::Fixed(getPointerSizeInBits(0)); | |||
| 667 | case Type::PointerTyID: | |||
| 668 | return TypeSize::Fixed(getPointerSizeInBits(Ty->getPointerAddressSpace())); | |||
| 669 | case Type::ArrayTyID: { | |||
| 670 | ArrayType *ATy = cast<ArrayType>(Ty); | |||
| 671 | return ATy->getNumElements() * | |||
| 672 | getTypeAllocSizeInBits(ATy->getElementType()); | |||
| 673 | } | |||
| 674 | case Type::StructTyID: | |||
| 675 | // Get the layout annotation... which is lazily created on demand. | |||
| 676 | return TypeSize::Fixed( | |||
| 677 | getStructLayout(cast<StructType>(Ty))->getSizeInBits()); | |||
| 678 | case Type::IntegerTyID: | |||
| 679 | return TypeSize::Fixed(Ty->getIntegerBitWidth()); | |||
| 680 | case Type::HalfTyID: | |||
| 681 | case Type::BFloatTyID: | |||
| 682 | return TypeSize::Fixed(16); | |||
| 683 | case Type::FloatTyID: | |||
| 684 | return TypeSize::Fixed(32); | |||
| 685 | case Type::DoubleTyID: | |||
| 686 | case Type::X86_MMXTyID: | |||
| 687 | return TypeSize::Fixed(64); | |||
| 688 | case Type::PPC_FP128TyID: | |||
| 689 | case Type::FP128TyID: | |||
| 690 | return TypeSize::Fixed(128); | |||
| 691 | // In memory objects this is always aligned to a higher boundary, but | |||
| 692 | // only 80 bits contain information. | |||
| 693 | case Type::X86_FP80TyID: | |||
| 694 | return TypeSize::Fixed(80); | |||
| 695 | case Type::FixedVectorTyID: | |||
| 696 | case Type::ScalableVectorTyID: { | |||
| 697 | VectorType *VTy = cast<VectorType>(Ty); | |||
| 698 | auto EltCnt = VTy->getElementCount(); | |||
| 699 | uint64_t MinBits = EltCnt.getKnownMinValue() * | |||
| 700 | getTypeSizeInBits(VTy->getElementType()).getFixedSize(); | |||
| 701 | return TypeSize(MinBits, EltCnt.isScalable()); | |||
| 702 | } | |||
| 703 | default: | |||
| 704 | llvm_unreachable("DataLayout::getTypeSizeInBits(): Unsupported type")::llvm::llvm_unreachable_internal("DataLayout::getTypeSizeInBits(): Unsupported type" , "/build/llvm-toolchain-snapshot-12~++20201029100616+6c2ad4cf875/llvm/include/llvm/IR/DataLayout.h" , 704); | |||
| 705 | } | |||
| 706 | } | |||
| 707 | ||||
| 708 | } // end namespace llvm | |||
| 709 | ||||
| 710 | #endif // LLVM_IR_DATALAYOUT_H |