LLVM 24.0.0git
InferAddressSpaces.cpp
Go to the documentation of this file.
1//===- InferAddressSpace.cpp - --------------------------------------------===//
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// CUDA C/C++ includes memory space designation as variable type qualifers (such
10// as __global__ and __shared__). Knowing the space of a memory access allows
11// CUDA compilers to emit faster PTX loads and stores. For example, a load from
12// shared memory can be translated to `ld.shared` which is roughly 10% faster
13// than a generic `ld` on an NVIDIA Tesla K40c.
14//
15// Unfortunately, type qualifiers only apply to variable declarations, so CUDA
16// compilers must infer the memory space of an address expression from
17// type-qualified variables.
18//
19// LLVM IR uses non-zero (so-called) specific address spaces to represent memory
20// spaces (e.g. addrspace(3) means shared memory). The Clang frontend
21// places only type-qualified variables in specific address spaces, and then
22// conservatively `addrspacecast`s each type-qualified variable to addrspace(0)
23// (so-called the generic address space) for other instructions to use.
24//
25// For example, the Clang translates the following CUDA code
26// __shared__ float a[10];
27// float v = a[i];
28// to
29// %0 = addrspacecast [10 x float] addrspace(3)* @a to [10 x float]*
30// %1 = gep [10 x float], [10 x float]* %0, i64 0, i64 %i
31// %v = load float, float* %1 ; emits ld.f32
32// @a is in addrspace(3) since it's type-qualified, but its use from %1 is
33// redirected to %0 (the generic version of @a).
34//
35// The optimization implemented in this file propagates specific address spaces
36// from type-qualified variable declarations to its users. For example, it
37// optimizes the above IR to
38// %1 = gep [10 x float] addrspace(3)* @a, i64 0, i64 %i
39// %v = load float addrspace(3)* %1 ; emits ld.shared.f32
40// propagating the addrspace(3) from @a to %1. As the result, the NVPTX
41// codegen is able to emit ld.shared.f32 for %v.
42//
43// Address space inference works in two steps. First, it uses a data-flow
44// analysis to infer as many generic pointers as possible to point to only one
45// specific address space. In the above example, it can prove that %1 only
46// points to addrspace(3). This algorithm was published in
47// CUDA: Compiling and optimizing for a GPU platform
48// Chakrabarti, Grover, Aarts, Kong, Kudlur, Lin, Marathe, Murphy, Wang
49// ICCS 2012
50//
51// Then, address space inference replaces all refinable generic pointers with
52// equivalent specific pointers.
53//
54// The major challenge of implementing this optimization is handling PHINodes,
55// which may create loops in the data flow graph. This brings two complications.
56//
57// First, the data flow analysis in Step 1 needs to be circular. For example,
58// %generic.input = addrspacecast float addrspace(3)* %input to float*
59// loop:
60// %y = phi [ %generic.input, %y2 ]
61// %y2 = getelementptr %y, 1
62// %v = load %y2
63// br ..., label %loop, ...
64// proving %y specific requires proving both %generic.input and %y2 specific,
65// but proving %y2 specific circles back to %y. To address this complication,
66// the data flow analysis operates on a lattice:
67// uninitialized > specific address spaces > generic.
68// All address expressions (our implementation only considers phi, bitcast,
69// addrspacecast, and getelementptr) start with the uninitialized address space.
70// The monotone transfer function moves the address space of a pointer down a
71// lattice path from uninitialized to specific and then to generic. A join
72// operation of two different specific address spaces pushes the expression down
73// to their common address space. The analysis completes once it reaches a fixed
74// point.
75//
76// Second, IR rewriting in Step 2 also needs to be circular. For example,
77// converting %y to addrspace(3) requires the compiler to know the converted
78// %y2, but converting %y2 needs the converted %y. To address this complication,
79// we break these cycles using "poison" placeholders. When converting an
80// instruction `I` to a new address space, if its operand `Op` is not converted
81// yet, we let `I` temporarily use `poison` and fix all the uses later.
82// For instance, our algorithm first converts %y to
83// %y' = phi float addrspace(3)* [ %input, poison ]
84// Then, it converts %y2 to
85// %y2' = getelementptr %y', 1
86// Finally, it fixes the poison in %y' so that
87// %y' = phi float addrspace(3)* [ %input, %y2' ]
88//
89//===----------------------------------------------------------------------===//
90
92#include "llvm/ADT/ArrayRef.h"
93#include "llvm/ADT/DenseMap.h"
94#include "llvm/ADT/DenseSet.h"
95#include "llvm/ADT/SetVector.h"
100#include "llvm/IR/Argument.h"
101#include "llvm/IR/BasicBlock.h"
102#include "llvm/IR/Constant.h"
103#include "llvm/IR/Constants.h"
104#include "llvm/IR/Dominators.h"
105#include "llvm/IR/Function.h"
106#include "llvm/IR/IRBuilder.h"
107#include "llvm/IR/InstIterator.h"
108#include "llvm/IR/Instruction.h"
109#include "llvm/IR/Instructions.h"
111#include "llvm/IR/Intrinsics.h"
112#include "llvm/IR/LLVMContext.h"
113#include "llvm/IR/Operator.h"
114#include "llvm/IR/PassManager.h"
115#include "llvm/IR/PatternMatch.h"
116#include "llvm/IR/Type.h"
117#include "llvm/IR/Use.h"
118#include "llvm/IR/User.h"
119#include "llvm/IR/Value.h"
120#include "llvm/IR/ValueHandle.h"
122#include "llvm/Pass.h"
123#include "llvm/Support/Casting.h"
124#include "llvm/Support/Debug.h"
131#include <cassert>
132#include <iterator>
133#include <limits>
134#include <optional>
135#include <utility>
136#include <vector>
137
138#define DEBUG_TYPE "infer-address-spaces"
139
140using namespace llvm;
141using namespace llvm::PatternMatch;
142
143static const unsigned UninitializedAddressSpace =
144 std::numeric_limits<unsigned>::max();
145
146namespace {
147
148using ValueToAddrSpaceMapTy = DenseMap<const Value *, unsigned>;
149// Different from ValueToAddrSpaceMapTy, where a new addrspace is inferred on
150// the *def* of a value, PredicatedAddrSpaceMapTy is map where a new
151// addrspace is inferred on the *use* of a pointer. This map is introduced to
152// infer addrspace from the addrspace predicate assumption built from assume
153// intrinsic. In that scenario, only specific uses (under valid assumption
154// context) could be inferred with a new addrspace.
155using PredicatedAddrSpaceMapTy =
157using PostorderStackTy = llvm::SmallVector<PointerIntPair<Value *, 1, bool>, 4>;
158
159class InferAddressSpaces : public FunctionPass {
160 unsigned FlatAddrSpace = 0;
161
162public:
163 static char ID;
164
165 InferAddressSpaces()
166 : FunctionPass(ID), FlatAddrSpace(UninitializedAddressSpace) {
168 }
169 InferAddressSpaces(unsigned AS) : FunctionPass(ID), FlatAddrSpace(AS) {
171 }
172
173 void getAnalysisUsage(AnalysisUsage &AU) const override {
174 AU.setPreservesCFG();
175 AU.addRequired<AssumptionCacheTracker>();
176 AU.addRequired<TargetTransformInfoWrapperPass>();
177 }
178
179 bool runOnFunction(Function &F) override;
180};
181
182class InferAddressSpacesImpl {
183 AssumptionCache &AC;
184 Function *F = nullptr;
185 const DominatorTree *DT = nullptr;
186 const TargetTransformInfo *TTI = nullptr;
187 const DataLayout *DL = nullptr;
188
189 /// Target specific address space which uses of should be replaced if
190 /// possible.
191 unsigned FlatAddrSpace = 0;
192
193 /// The default address space is assumed as the flat address space. This is
194 /// mainly for test purpose.
195 const bool AssumeDefaultIsFlatAddressSpace = false;
196
197 DenseMap<const Value *, Value *> PtrIntCastPairs;
198
199 // Tries to find if the inttoptr instruction is derived from an pointer have
200 // specific address space, and is safe to propagate the address space to the
201 // new pointer that inttoptr produces.
202 Value *getIntToPtrPointerOperand(const Operator *I2P) const;
203 // Tries to find if the inttoptr instruction is derived from an pointer have
204 // specific address space, and is safe to propagate the address space to the
205 // new pointer that inttoptr produces. If the old pointer is found, cache the
206 // <OldPtr, inttoptr> pairs to a map.
207 void collectIntToPtrPointerOperand();
208 // Check if an old pointer is found ahead of time. The safety has been checked
209 // when collecting the inttoptr original pointer and the result is cached in
210 // PtrIntCastPairs.
211 bool isSafeToCastIntToPtrAddrSpace(const Operator *I2P) const {
212 return PtrIntCastPairs.contains(I2P);
213 }
214 bool isAddressExpression(const Value &V, const DataLayout &DL,
215 const TargetTransformInfo *TTI) const;
216 Value *cloneConstantExprWithNewAddressSpace(
217 ConstantExpr *CE, unsigned NewAddrSpace,
218 const ValueToValueMapTy &ValueWithNewAddrSpace, const DataLayout *DL,
219 const TargetTransformInfo *TTI) const;
220
221 SmallVector<Value *, 2>
222 getPointerOperands(const Value &V, const DataLayout &DL,
223 const TargetTransformInfo *TTI) const;
224
225 // Try to update the address space of V. If V is updated, returns true and
226 // false otherwise.
227 bool updateAddressSpace(const Value &V,
228 ValueToAddrSpaceMapTy &InferredAddrSpace,
229 PredicatedAddrSpaceMapTy &PredicatedAS) const;
230
231 // Adds the users of V whose address space may still change to Worklist.
232 void enqueueUsers(Value &V, const ValueToAddrSpaceMapTy &InferredAddrSpace,
233 SetVector<Value *> &Worklist) const;
234
235 // Propagates address spaces out of Worklist until nothing changes.
236 void runToFixPoint(SetVector<Value *> &Worklist,
237 ValueToAddrSpaceMapTy &InferredAddrSpace,
238 PredicatedAddrSpaceMapTy &PredicatedAS) const;
239
240 // Tries to infer the specific address space of each address expression in
241 // Postorder.
242 void inferAddressSpaces(ArrayRef<WeakTrackingVH> Postorder,
243 ValueToAddrSpaceMapTy &InferredAddrSpace,
244 PredicatedAddrSpaceMapTy &PredicatedAS) const;
245
246 bool isSafeToCastConstAddrSpace(Constant *C, unsigned NewAS) const;
247
248 Value *clonePtrMaskWithNewAddressSpace(
249 IntrinsicInst *I, unsigned NewAddrSpace,
250 const ValueToValueMapTy &ValueWithNewAddrSpace,
251 const PredicatedAddrSpaceMapTy &PredicatedAS,
252 SmallVectorImpl<const Use *> *PoisonUsesToFix) const;
253
254 Value *cloneInstructionWithNewAddressSpace(
255 Instruction *I, unsigned NewAddrSpace,
256 const ValueToValueMapTy &ValueWithNewAddrSpace,
257 const PredicatedAddrSpaceMapTy &PredicatedAS,
258 SmallVectorImpl<const Use *> *PoisonUsesToFix) const;
259
260 void performPointerReplacement(
261 Value *V, Value *NewV, Use &U, ValueToValueMapTy &ValueWithNewAddrSpace,
262 SmallVectorImpl<Instruction *> &DeadInstructions) const;
263
264 // Changes the flat address expressions in function F to point to specific
265 // address spaces if InferredAddrSpace says so. Postorder is the postorder of
266 // all flat expressions in the use-def graph of function F.
267 bool rewriteWithNewAddressSpaces(
268 ArrayRef<WeakTrackingVH> Postorder,
269 const ValueToAddrSpaceMapTy &InferredAddrSpace,
270 const PredicatedAddrSpaceMapTy &PredicatedAS) const;
271
272 void appendsFlatAddressExpressionToPostorderStack(
273 Value *V, PostorderStackTy &PostorderStack,
274 DenseSet<Value *> &Visited) const;
275
276 bool rewriteIntrinsicOperands(IntrinsicInst *II, Value *OldV,
277 Value *NewV) const;
278 void collectRewritableIntrinsicOperands(IntrinsicInst *II,
279 PostorderStackTy &PostorderStack,
280 DenseSet<Value *> &Visited) const;
281
282 std::vector<WeakTrackingVH> collectFlatAddressExpressions(Function &F) const;
283
284 Value *cloneValueWithNewAddressSpace(
285 Value *V, unsigned NewAddrSpace,
286 const ValueToValueMapTy &ValueWithNewAddrSpace,
287 const PredicatedAddrSpaceMapTy &PredicatedAS,
288 SmallVectorImpl<const Use *> *PoisonUsesToFix) const;
289 unsigned joinAddressSpaces(unsigned AS1, unsigned AS2) const;
290
291 unsigned getPredicatedAddrSpace(const Value &PtrV,
292 const Value *UserCtx) const;
293
294public:
295 InferAddressSpacesImpl(AssumptionCache &AC, const DominatorTree *DT,
296 const TargetTransformInfo *TTI, unsigned FlatAddrSpace,
297 bool AssumeDefaultIsFlatAddressSpace)
298 : AC(AC), DT(DT), TTI(TTI), FlatAddrSpace(FlatAddrSpace),
299 AssumeDefaultIsFlatAddressSpace(AssumeDefaultIsFlatAddressSpace) {}
300 bool run(Function &F);
301};
302
303} // end anonymous namespace
304
305char InferAddressSpaces::ID = 0;
306
307INITIALIZE_PASS_BEGIN(InferAddressSpaces, DEBUG_TYPE, "Infer address spaces",
308 false, false)
311INITIALIZE_PASS_END(InferAddressSpaces, DEBUG_TYPE, "Infer address spaces",
313
314static Type *getPtrOrVecOfPtrsWithNewAS(Type *Ty, unsigned NewAddrSpace) {
315 assert(Ty->isPtrOrPtrVectorTy());
316 PointerType *NPT = PointerType::get(Ty->getContext(), NewAddrSpace);
317 return Ty->getWithNewType(NPT);
318}
319
320// Check whether that's no-op pointer bitcast using a pair of
321// `ptrtoint`/`inttoptr` due to the missing no-op pointer bitcast over
322// different address spaces.
323static bool isNoopPtrIntCastPair(const Operator *I2P, const DataLayout &DL,
324 const TargetTransformInfo *TTI) {
325 assert(I2P->getOpcode() == Instruction::IntToPtr);
326 auto *P2I = dyn_cast<Operator>(I2P->getOperand(0));
327 if (!P2I || P2I->getOpcode() != Instruction::PtrToInt)
328 return false;
329 // Check it's really safe to treat that pair of `ptrtoint`/`inttoptr` as a
330 // no-op cast. Besides checking both of them are no-op casts, as the
331 // reinterpreted pointer may be used in other pointer arithmetic, we also
332 // need to double-check that through the target-specific hook. That ensures
333 // the underlying target also agrees that's a no-op address space cast and
334 // pointer bits are preserved.
335 // The current IR spec doesn't have clear rules on address space casts,
336 // especially a clear definition for pointer bits in non-default address
337 // spaces. It would be undefined if that pointer is dereferenced after an
338 // invalid reinterpret cast. Also, due to the unclearness for the meaning of
339 // bits in non-default address spaces in the current spec, the pointer
340 // arithmetic may also be undefined after invalid pointer reinterpret cast.
341 // However, as we confirm through the target hooks that it's a no-op
342 // addrspacecast, it doesn't matter since the bits should be the same.
343 unsigned P2IOp0AS = P2I->getOperand(0)->getType()->getPointerAddressSpace();
344 unsigned I2PAS = I2P->getType()->getPointerAddressSpace();
346 I2P->getOperand(0)->getType(), I2P->getType(),
347 DL) &&
349 P2I->getOperand(0)->getType(), P2I->getType(),
350 DL) &&
351 (P2IOp0AS == I2PAS || TTI->isNoopAddrSpaceCast(P2IOp0AS, I2PAS));
352}
353
354// Returns true if V is an address expression.
355// TODO: Currently, we only consider:
356// - arguments
357// - phi, bitcast, addrspacecast, and getelementptr operators
358bool InferAddressSpacesImpl::isAddressExpression(
359 const Value &V, const DataLayout &DL,
360 const TargetTransformInfo *TTI) const {
361
362 if (const Argument *Arg = dyn_cast<Argument>(&V))
363 return Arg->getType()->isPointerTy() &&
365
366 const Operator *Op = dyn_cast<Operator>(&V);
367 if (!Op)
368 return false;
369
370 switch (Op->getOpcode()) {
371 case Instruction::PHI:
372 assert(Op->getType()->isPtrOrPtrVectorTy());
373 return true;
374 case Instruction::BitCast:
375 case Instruction::AddrSpaceCast:
376 case Instruction::GetElementPtr:
377 return true;
378 case Instruction::Select:
379 return Op->getType()->isPtrOrPtrVectorTy();
380 case Instruction::Call: {
381 const IntrinsicInst *II = dyn_cast<IntrinsicInst>(&V);
382 return II && II->getIntrinsicID() == Intrinsic::ptrmask;
383 }
384 case Instruction::IntToPtr:
385 return isNoopPtrIntCastPair(Op, DL, TTI) ||
386 isSafeToCastIntToPtrAddrSpace(Op);
387 default:
388 // That value is an address expression if it has an assumed address space.
390 }
391}
392
393// Returns the pointer operands of V.
394//
395// Precondition: V is an address expression.
396SmallVector<Value *, 2> InferAddressSpacesImpl::getPointerOperands(
397 const Value &V, const DataLayout &DL,
398 const TargetTransformInfo *TTI) const {
399 if (isa<Argument>(&V))
400 return {};
401
402 const Operator &Op = cast<Operator>(V);
403 switch (Op.getOpcode()) {
404 case Instruction::PHI: {
405 auto IncomingValues = cast<PHINode>(Op).incoming_values();
406 return {IncomingValues.begin(), IncomingValues.end()};
407 }
408 case Instruction::BitCast:
409 case Instruction::AddrSpaceCast:
410 case Instruction::GetElementPtr:
411 return {Op.getOperand(0)};
412 case Instruction::Select:
413 return {Op.getOperand(1), Op.getOperand(2)};
414 case Instruction::Call: {
415 const IntrinsicInst &II = cast<IntrinsicInst>(Op);
416 assert(II.getIntrinsicID() == Intrinsic::ptrmask &&
417 "unexpected intrinsic call");
418 return {II.getArgOperand(0)};
419 }
420 case Instruction::IntToPtr: {
421 if (isNoopPtrIntCastPair(&Op, DL, TTI)) {
422 auto *P2I = cast<Operator>(Op.getOperand(0));
423 return {P2I->getOperand(0)};
424 }
425 assert(isSafeToCastIntToPtrAddrSpace(&Op));
426 return {getIntToPtrPointerOperand(&Op)};
427 }
428 default:
429 llvm_unreachable("Unexpected instruction type.");
430 }
431}
432
433// Return mask. The 1 in mask indicate the bit is changed.
434// This helper function is to compute the max know changed bits for ptr1 and
435// ptr2 after the operation `ptr2 = ptr1 Op Mask`.
436static APInt computeMaxChangedPtrBits(const Operator *Op, const Value *Mask,
437 const DataLayout &DL, AssumptionCache *AC,
438 const DominatorTree *DT) {
439 KnownBits Known = computeKnownBits(Mask, DL, AC, nullptr, DT);
440 switch (Op->getOpcode()) {
441 case Instruction::Xor:
442 case Instruction::Or:
443 return ~Known.Zero;
444 case Instruction::And:
445 return ~Known.One;
446 default:
447 return APInt::getAllOnes(Known.getBitWidth());
448 }
449}
450
451Value *
452InferAddressSpacesImpl::getIntToPtrPointerOperand(const Operator *I2P) const {
453 assert(I2P->getOpcode() == Instruction::IntToPtr);
454 if (I2P->getType()->isVectorTy())
455 return nullptr;
456
457 // If I2P has been accessed and has the corresponding old pointer value, just
458 // return true.
459 if (auto *OldPtr = PtrIntCastPairs.lookup(I2P))
460 return OldPtr;
461
462 // Not m_c_BitwiseLogic: the binary-op matchers only match instructions, and
463 // a round trip over a compile-time address folds into a constant expression.
464 // m_PtrToInt below accepts either form.
465 auto *LogicalOp = dyn_cast<Operator>(I2P->getOperand(0));
466 if (!LogicalOp || !Instruction::isBitwiseLogicOp(LogicalOp->getOpcode()))
467 return nullptr;
468
469 // Either side can hold the pointer; the other is then the mask. Both sides
470 // being a pointer needs no special case: such a "mask" has no known bits, so
471 // its worst-case bit change is unbounded and the check below rejects it.
472 Value *LHS = LogicalOp->getOperand(0), *RHS = LogicalOp->getOperand(1);
473 Value *OldPtr, *Mask;
474 if (match(LHS, m_PtrToInt(m_Value(OldPtr))))
475 Mask = RHS;
476 else if (match(RHS, m_PtrToInt(m_Value(OldPtr))))
477 Mask = LHS;
478 else
479 return nullptr;
480
482 if (!AsCast)
483 return nullptr;
484
485 unsigned SrcAS = I2P->getType()->getPointerAddressSpace();
486 unsigned DstAS = AsCast->getOperand(0)->getType()->getPointerAddressSpace();
487 APInt PreservedPtrMask = TTI->getAddrSpaceCastPreservedPtrMask(SrcAS, DstAS);
488 if (PreservedPtrMask.isZero())
489 return nullptr;
490 APInt ChangedPtrBits =
491 computeMaxChangedPtrBits(LogicalOp, Mask, *DL, &AC, DT);
492 // Check if the address bits change is within the preserved mask. If the bits
493 // change is not preserved, it is not safe to perform address space cast.
494 // The following pattern is not safe to cast address space.
495 // %1 = ptrtoint ptr addrspace(3) %sp to i32
496 // %2 = zext i32 %1 to i64
497 // %gp = inttoptr i64 %2 to ptr
498 assert(ChangedPtrBits.getBitWidth() == PreservedPtrMask.getBitWidth());
499 if (ChangedPtrBits.isSubsetOf(PreservedPtrMask))
500 return OldPtr;
501
502 return nullptr;
503}
504
505void InferAddressSpacesImpl::collectIntToPtrPointerOperand() {
506 auto Collect = [&](const Operator *I2P) {
507 if (auto *OldPtr = getIntToPtrPointerOperand(I2P))
508 PtrIntCastPairs.insert({I2P, OldPtr});
509 };
510
511 // A compile-time address folds the whole round trip into a constant
512 // expression, which is not an instruction. Within a function it is reached
513 // as an operand of an instruction, possibly nested under further constant
514 // expressions as when a gep indexes it. Without walking those, every access
515 // to a fixed address stays flat. The rewrite side already handles them; see
516 // cloneConstantExprWithNewAddressSpace. Only constant expressions reachable
517 // from instruction operands are visited; the initializers of global values
518 // are not, and the originals are never modified, so those are unaffected.
519 DenseSet<ConstantExpr *> VisitedCE;
521 auto PushConstantExpr = [&](Value *V) {
522 if (auto *CE = dyn_cast<ConstantExpr>(V))
523 if (VisitedCE.insert(CE).second)
524 Worklist.push_back(CE);
525 };
526
527 for (Instruction &I : instructions(F)) {
528 if (isa<IntToPtrInst>(&I))
529 Collect(cast<Operator>(&I));
530 for (Value *Op : I.operands())
531 PushConstantExpr(Op);
532 }
533
534 while (!Worklist.empty()) {
535 ConstantExpr *CE = Worklist.pop_back_val();
536 if (CE->getOpcode() == Instruction::IntToPtr)
537 Collect(cast<Operator>(CE));
538 for (Value *Op : CE->operands())
539 PushConstantExpr(Op);
540 }
541}
542
543bool InferAddressSpacesImpl::rewriteIntrinsicOperands(IntrinsicInst *II,
544 Value *OldV,
545 Value *NewV) const {
546 Module *M = II->getParent()->getParent()->getParent();
547 Intrinsic::ID IID = II->getIntrinsicID();
548 switch (IID) {
549 case Intrinsic::objectsize:
550 case Intrinsic::masked_load: {
551 Type *DestTy = II->getType();
552 Type *SrcTy = NewV->getType();
553 Function *NewDecl =
554 Intrinsic::getOrInsertDeclaration(M, IID, {DestTy, SrcTy});
555 II->setArgOperand(0, NewV);
556 II->setCalledFunction(NewDecl);
557 return true;
558 }
559 case Intrinsic::ptrmask:
560 // This is handled as an address expression, not as a use memory operation.
561 return false;
562 case Intrinsic::masked_gather: {
563 Type *RetTy = II->getType();
564 Type *NewPtrTy = NewV->getType();
565 Function *NewDecl =
566 Intrinsic::getOrInsertDeclaration(M, IID, {RetTy, NewPtrTy});
567 II->setArgOperand(0, NewV);
568 II->setCalledFunction(NewDecl);
569 return true;
570 }
571 case Intrinsic::masked_store:
572 case Intrinsic::masked_scatter: {
573 Type *ValueTy = II->getOperand(0)->getType();
574 Type *NewPtrTy = NewV->getType();
576 M, II->getIntrinsicID(), {ValueTy, NewPtrTy});
577 II->setArgOperand(1, NewV);
578 II->setCalledFunction(NewDecl);
579 return true;
580 }
581 case Intrinsic::prefetch:
582 case Intrinsic::is_constant: {
584 M, II->getIntrinsicID(), {NewV->getType()});
585 II->setArgOperand(0, NewV);
586 II->setCalledFunction(NewDecl);
587 return true;
588 }
589 case Intrinsic::fake_use: {
590 II->replaceUsesOfWith(OldV, NewV);
591 return true;
592 }
593 case Intrinsic::lifetime_start:
594 case Intrinsic::lifetime_end: {
595 // Always force lifetime markers to work directly on the alloca.
596 NewV = NewV->stripPointerCasts();
598 M, II->getIntrinsicID(), {NewV->getType()});
599 II->setArgOperand(0, NewV);
600 II->setCalledFunction(NewDecl);
601 return true;
602 }
603 default: {
604 Value *Rewrite = TTI->rewriteIntrinsicWithAddressSpace(II, OldV, NewV);
605 if (!Rewrite)
606 return false;
607 if (Rewrite != II) {
608 II->replaceAllUsesWith(Rewrite);
609 II->eraseFromParent();
610 }
611 return true;
612 }
613 }
614}
615
616void InferAddressSpacesImpl::collectRewritableIntrinsicOperands(
617 IntrinsicInst *II, PostorderStackTy &PostorderStack,
618 DenseSet<Value *> &Visited) const {
619 auto IID = II->getIntrinsicID();
620 switch (IID) {
621 case Intrinsic::ptrmask:
622 case Intrinsic::objectsize:
623 appendsFlatAddressExpressionToPostorderStack(II->getArgOperand(0),
624 PostorderStack, Visited);
625 break;
626 case Intrinsic::is_constant: {
627 Value *Ptr = II->getArgOperand(0);
628 if (Ptr->getType()->isPtrOrPtrVectorTy()) {
629 appendsFlatAddressExpressionToPostorderStack(Ptr, PostorderStack,
630 Visited);
631 }
632
633 break;
634 }
635 case Intrinsic::masked_load:
636 case Intrinsic::masked_gather:
637 case Intrinsic::prefetch:
638 appendsFlatAddressExpressionToPostorderStack(II->getArgOperand(0),
639 PostorderStack, Visited);
640 break;
641 case Intrinsic::masked_store:
642 case Intrinsic::masked_scatter:
643 appendsFlatAddressExpressionToPostorderStack(II->getArgOperand(1),
644 PostorderStack, Visited);
645 break;
646 case Intrinsic::fake_use: {
647 for (Value *Op : II->operands()) {
648 if (Op->getType()->isPtrOrPtrVectorTy()) {
649 appendsFlatAddressExpressionToPostorderStack(Op, PostorderStack,
650 Visited);
651 }
652 }
653
654 break;
655 }
656 case Intrinsic::lifetime_start:
657 case Intrinsic::lifetime_end: {
658 appendsFlatAddressExpressionToPostorderStack(II->getArgOperand(0),
659 PostorderStack, Visited);
660 break;
661 }
662 default:
663 SmallVector<int, 2> OpIndexes;
664 if (TTI->collectFlatAddressOperands(OpIndexes, IID)) {
665 for (int Idx : OpIndexes) {
666 appendsFlatAddressExpressionToPostorderStack(II->getArgOperand(Idx),
667 PostorderStack, Visited);
668 }
669 }
670 break;
671 }
672}
673
674// Returns all flat address expressions in function F. The elements are
675// If V is an unvisited flat address expression, appends V to PostorderStack
676// and marks it as visited.
677void InferAddressSpacesImpl::appendsFlatAddressExpressionToPostorderStack(
678 Value *V, PostorderStackTy &PostorderStack,
679 DenseSet<Value *> &Visited) const {
680 assert(V->getType()->isPtrOrPtrVectorTy());
681
682 // Generic addressing expressions may be hidden in nested constant
683 // expressions.
684 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
685 // TODO: Look in non-address parts, like icmp operands.
686 if (isAddressExpression(*CE, *DL, TTI) && Visited.insert(CE).second)
687 PostorderStack.emplace_back(CE, false);
688
689 return;
690 }
691
692 if (V->getType()->getPointerAddressSpace() == FlatAddrSpace &&
693 isAddressExpression(*V, *DL, TTI)) {
694 if (Visited.insert(V).second) {
695 PostorderStack.emplace_back(V, false);
696
697 if (auto *Op = dyn_cast<Operator>(V))
698 for (auto &O : Op->operands())
699 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(O))
700 if (isAddressExpression(*CE, *DL, TTI) && Visited.insert(CE).second)
701 PostorderStack.emplace_back(CE, false);
702 }
703 }
704}
705
706// Returns all flat address expressions in function F. The elements are ordered
707// in postorder.
708std::vector<WeakTrackingVH>
709InferAddressSpacesImpl::collectFlatAddressExpressions(Function &F) const {
710 // This function implements a non-recursive postorder traversal of a partial
711 // use-def graph of function F.
712 PostorderStackTy PostorderStack;
713 // The set of visited expressions.
714 DenseSet<Value *> Visited;
715
716 auto PushPtrOperand = [&](Value *Ptr) {
717 appendsFlatAddressExpressionToPostorderStack(Ptr, PostorderStack, Visited);
718 };
719
720 // Constant expressions in instruction operands that were already checked for
721 // an addrspacecast from flat, see below.
722 DenseSet<ConstantExpr *> VisitedCE;
724 auto PushConstantExpr = [&](Value *V) {
725 if (auto *CE = dyn_cast<ConstantExpr>(V); CE && VisitedCE.insert(CE).second)
726 CEWorklist.push_back(CE);
727 };
728
729 // Look at operations that may be interesting accelerate by moving to a known
730 // address space. We aim at generating after loads and stores, but pure
731 // addressing calculations may also be faster.
732 for (Instruction &I : instructions(F)) {
733 if (auto *GEP = dyn_cast<GetElementPtrInst>(&I)) {
734 PushPtrOperand(GEP->getPointerOperand());
735 } else if (auto *LI = dyn_cast<LoadInst>(&I))
736 PushPtrOperand(LI->getPointerOperand());
737 else if (auto *SI = dyn_cast<StoreInst>(&I))
738 PushPtrOperand(SI->getPointerOperand());
739 else if (auto *RMW = dyn_cast<AtomicRMWInst>(&I))
740 PushPtrOperand(RMW->getPointerOperand());
741 else if (auto *CmpX = dyn_cast<AtomicCmpXchgInst>(&I))
742 PushPtrOperand(CmpX->getPointerOperand());
743 else if (auto *MI = dyn_cast<MemIntrinsic>(&I)) {
744 // For memset/memcpy/memmove, any pointer operand can be replaced.
745 PushPtrOperand(MI->getRawDest());
746
747 // Handle 2nd operand for memcpy/memmove.
748 if (auto *MTI = dyn_cast<MemTransferInst>(MI))
749 PushPtrOperand(MTI->getRawSource());
750 } else if (auto *II = dyn_cast<IntrinsicInst>(&I))
751 collectRewritableIntrinsicOperands(II, PostorderStack, Visited);
752 else if (ICmpInst *Cmp = dyn_cast<ICmpInst>(&I)) {
753 if (Cmp->getOperand(0)->getType()->isPtrOrPtrVectorTy()) {
754 PushPtrOperand(Cmp->getOperand(0));
755 PushPtrOperand(Cmp->getOperand(1));
756 }
757 } else if (auto *ASC = dyn_cast<AddrSpaceCastInst>(&I)) {
758 PushPtrOperand(ASC->getPointerOperand());
759 } else if (auto *I2P = dyn_cast<IntToPtrInst>(&I)) {
761 PushPtrOperand(cast<Operator>(I2P->getOperand(0))->getOperand(0));
762 else if (isSafeToCastIntToPtrAddrSpace(cast<Operator>(I2P)))
763 PushPtrOperand(getIntToPtrPointerOperand(cast<Operator>(I2P)));
764 } else if (auto *RI = dyn_cast<ReturnInst>(&I)) {
765 if (auto *RV = RI->getReturnValue();
766 RV && RV->getType()->isPtrOrPtrVectorTy())
767 PushPtrOperand(RV);
768 }
769
770 // An addrspacecast from flat folded into a constant expression, possibly
771 // nested, is not an AddrSpaceCastInst, so the checks above miss it, e.g. in
772 // a call operand. Use its pointer operand as a root in the same way. Other
773 // constant expressions only produce another flat pointer.
774 for (Value *Op : I.operands())
775 PushConstantExpr(Op);
776 while (!CEWorklist.empty()) {
777 ConstantExpr *CE = CEWorklist.pop_back_val();
778 if (auto *ASC = dyn_cast<AddrSpaceCastOperator>(CE);
779 ASC && ASC->getSrcAddressSpace() == FlatAddrSpace)
780 PushPtrOperand(ASC->getPointerOperand());
781 for (Value *Op : CE->operands())
782 PushConstantExpr(Op);
783 }
784 }
785
786 std::vector<WeakTrackingVH> Postorder; // The resultant postorder.
787 while (!PostorderStack.empty()) {
788 Value *TopVal = PostorderStack.back().getPointer();
789 // If the operands of the expression on the top are already explored,
790 // adds that expression to the resultant postorder.
791 if (PostorderStack.back().getInt()) {
792 if (TopVal->getType()->getPointerAddressSpace() == FlatAddrSpace)
793 Postorder.push_back(TopVal);
794 PostorderStack.pop_back();
795 continue;
796 }
797 // Otherwise, adds its operands to the stack and explores them.
798 PostorderStack.back().setInt(true);
799 // Skip values with an assumed address space.
801 for (Value *PtrOperand : getPointerOperands(*TopVal, *DL, TTI)) {
802 appendsFlatAddressExpressionToPostorderStack(PtrOperand, PostorderStack,
803 Visited);
804 }
805 }
806 }
807 return Postorder;
808}
809
810// Inserts an addrspacecast for a phi node operand, handling the proper
811// insertion position based on the operand type.
813 Value *Operand) {
814 auto InsertBefore = [NewI](auto It) {
815 NewI->insertBefore(It);
816 NewI->setDebugLoc(It->getDebugLoc());
817 return NewI;
818 };
819
820 if (auto *Arg = dyn_cast<Argument>(Operand)) {
821 // For arguments, insert the cast at the beginning of entry block.
822 // Consider inserting at the dominating block for better placement.
823 Function *F = Arg->getParent();
824 auto InsertI = F->getEntryBlock().getFirstNonPHIIt();
825 return InsertBefore(InsertI);
826 }
827
828 // No check for Constant here, as constants are already handled.
829 assert(isa<Instruction>(Operand));
830
831 Instruction *OpInst = cast<Instruction>(Operand);
832 if (LLVM_UNLIKELY(OpInst->getOpcode() == Instruction::PHI)) {
833 // If the operand is defined by another PHI node, insert after the first
834 // non-PHI instruction at the corresponding basic block.
835 auto InsertI = OpInst->getParent()->getFirstNonPHIIt();
836 return InsertBefore(InsertI);
837 }
838
839 // Otherwise, insert immediately after the operand definition.
840 NewI->insertAfter(OpInst->getIterator());
841 NewI->setDebugLoc(OpInst->getDebugLoc());
842 return NewI;
843}
844
845// A helper function for cloneInstructionWithNewAddressSpace. Returns the clone
846// of OperandUse.get() in the new address space. If the clone is not ready yet,
847// returns poison in the new address space as a placeholder.
849 const Use &OperandUse, unsigned NewAddrSpace,
850 const ValueToValueMapTy &ValueWithNewAddrSpace,
851 const PredicatedAddrSpaceMapTy &PredicatedAS,
852 SmallVectorImpl<const Use *> *PoisonUsesToFix) {
853 Value *Operand = OperandUse.get();
854
855 Type *NewPtrTy = getPtrOrVecOfPtrsWithNewAS(Operand->getType(), NewAddrSpace);
856
857 if (Constant *C = dyn_cast<Constant>(Operand))
858 return ConstantExpr::getAddrSpaceCast(C, NewPtrTy);
859
860 Instruction *Inst = cast<Instruction>(OperandUse.getUser());
861 if (Value *NewOperand = ValueWithNewAddrSpace.lookup(Operand)) {
862 Operand = NewOperand;
863 } else if (!PredicatedAS.contains(std::make_pair(Inst, Operand))) {
864 assert(PoisonUsesToFix && "missing inferred operand replacement");
865 PoisonUsesToFix->push_back(&OperandUse);
866 return PoisonValue::get(NewPtrTy);
867 }
868
869 if (Operand->getType() == NewPtrTy)
870 return Operand;
871
872 auto *NewI = new AddrSpaceCastInst(Operand, NewPtrTy);
873 if (LLVM_UNLIKELY(Inst->getOpcode() == Instruction::PHI))
874 return phiNodeOperandWithNewAddressSpace(NewI, OperandUse.get());
875
876 // During cloning phase, the cast is placed before the original flat
877 // instruction, as its clone in the new address space has not been inserted
878 // yet. During poison fixup phase, the clone already exists, thus make sure
879 // the cast is inserted before it.
880 Instruction *InsertPt = Inst;
881 if (Value *NewUser = ValueWithNewAddrSpace.lookup(Inst))
882 InsertPt = cast<Instruction>(NewUser);
883 NewI->insertBefore(InsertPt->getIterator());
884 NewI->setDebugLoc(Inst->getDebugLoc());
885 return NewI;
886}
887
888// A helper function for cloneInstructionWithNewAddressSpace. Handles the
889// conversion of a ptrmask intrinsic instruction.
890Value *InferAddressSpacesImpl::clonePtrMaskWithNewAddressSpace(
891 IntrinsicInst *I, unsigned NewAddrSpace,
892 const ValueToValueMapTy &ValueWithNewAddrSpace,
893 const PredicatedAddrSpaceMapTy &PredicatedAS,
894 SmallVectorImpl<const Use *> *PoisonUsesToFix) const {
895 const Use &PtrOpUse = I->getArgOperandUse(0);
896 unsigned OldAddrSpace = PtrOpUse->getType()->getPointerAddressSpace();
897 Value *MaskOp = I->getArgOperand(1);
898 Type *MaskTy = MaskOp->getType();
899
900 KnownBits OldPtrBits{DL->getPointerSizeInBits(OldAddrSpace)};
901 KnownBits NewPtrBits{DL->getPointerSizeInBits(NewAddrSpace)};
902 if (!TTI->isNoopAddrSpaceCast(OldAddrSpace, NewAddrSpace)) {
903 std::tie(OldPtrBits, NewPtrBits) =
904 TTI->computeKnownBitsAddrSpaceCast(NewAddrSpace, *PtrOpUse.get());
905 }
906
907 // If the pointers in both addrspaces have a bitwise representation and if the
908 // representation of the new pointer is smaller (fewer bits) than the old one,
909 // check if the mask is applicable to the ptr in the new addrspace. Any
910 // masking only clearing the low bits will also apply in the new addrspace
911 // Note: checking if the mask clears high bits is not sufficient as those
912 // might have already been 0 in the old ptr.
913 if (OldPtrBits.getBitWidth() > NewPtrBits.getBitWidth()) {
914 KnownBits MaskBits =
915 computeKnownBits(MaskOp, *DL, /*AssumptionCache=*/nullptr, I);
916 // Set all unknown bits of the old ptr to 1, so that we are conservative in
917 // checking which bits are cleared by the mask.
918 OldPtrBits.One |= ~OldPtrBits.Zero;
919 // Check which bits are cleared by the mask in the old ptr.
920 KnownBits ClearedBits = KnownBits::sub(OldPtrBits, OldPtrBits & MaskBits);
921
922 // If the mask isn't applicable to the new ptr, leave the ptrmask as-is and
923 // insert an addrspacecast after it.
924 if (ClearedBits.countMaxActiveBits() > NewPtrBits.countMaxActiveBits()) {
925 std::optional<BasicBlock::iterator> InsertPoint =
926 I->getInsertionPointAfterDef();
927 assert(InsertPoint && "insertion after ptrmask should be possible");
928 Type *NewPtrType = getPtrOrVecOfPtrsWithNewAS(I->getType(), NewAddrSpace);
929 Instruction *AddrSpaceCast =
930 new AddrSpaceCastInst(I, NewPtrType, "", *InsertPoint);
931 AddrSpaceCast->setDebugLoc(I->getDebugLoc());
932 return AddrSpaceCast;
933 }
934 }
935
936 IRBuilder<> B(I);
937 if (NewPtrBits.getBitWidth() < MaskTy->getScalarSizeInBits()) {
938 MaskTy = MaskTy->getWithNewBitWidth(NewPtrBits.getBitWidth());
939 MaskOp = B.CreateTrunc(MaskOp, MaskTy);
940 }
942 PtrOpUse, NewAddrSpace, ValueWithNewAddrSpace, PredicatedAS,
943 PoisonUsesToFix);
944 return B.CreateIntrinsic(Intrinsic::ptrmask, {NewPtr->getType(), MaskTy},
945 {NewPtr, MaskOp});
946}
947
948// Returns a clone of `I` with its operands converted to those specified in
949// ValueWithNewAddrSpace. Due to potential cycles in the data flow graph, an
950// operand whose address space needs to be modified might not exist in
951// ValueWithNewAddrSpace. In that case, uses poison as a placeholder operand and
952// adds that operand use to PoisonUsesToFix so that caller can fix them later.
953//
954// Note that we do not necessarily clone `I`, e.g., if it is an addrspacecast
955// from a pointer whose type already matches. Therefore, this function returns a
956// Value* instead of an Instruction*.
957Value *InferAddressSpacesImpl::cloneInstructionWithNewAddressSpace(
958 Instruction *I, unsigned NewAddrSpace,
959 const ValueToValueMapTy &ValueWithNewAddrSpace,
960 const PredicatedAddrSpaceMapTy &PredicatedAS,
961 SmallVectorImpl<const Use *> *PoisonUsesToFix) const {
962 Type *NewPtrType = getPtrOrVecOfPtrsWithNewAS(I->getType(), NewAddrSpace);
963
964 if (I->getOpcode() == Instruction::AddrSpaceCast) {
965 Value *Src = I->getOperand(0);
966 // Because `I` is flat, the source address space must be specific.
967 // Therefore, the inferred address space must be the source space, according
968 // to our algorithm.
969 assert(Src->getType()->getPointerAddressSpace() == NewAddrSpace);
970 return Src;
971 }
972
973 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
974 // Technically the intrinsic ID is a pointer typed argument, so specially
975 // handle calls early.
976 assert(II->getIntrinsicID() == Intrinsic::ptrmask);
977 return clonePtrMaskWithNewAddressSpace(
978 II, NewAddrSpace, ValueWithNewAddrSpace, PredicatedAS, PoisonUsesToFix);
979 }
980
981 unsigned AS = TTI->getAssumedAddrSpace(I);
982 if (AS != UninitializedAddressSpace) {
983 // For the assumed address space, insert an `addrspacecast` to make that
984 // explicit.
985 Type *NewPtrTy = getPtrOrVecOfPtrsWithNewAS(I->getType(), AS);
986 auto *NewI = new AddrSpaceCastInst(I, NewPtrTy);
987 NewI->insertAfter(I->getIterator());
988 NewI->setDebugLoc(I->getDebugLoc());
989 return NewI;
990 }
991
992 // Computes the converted pointer operands.
993 SmallVector<Value *, 4> NewPointerOperands;
994 for (const Use &OperandUse : I->operands()) {
995 if (!OperandUse.get()->getType()->isPtrOrPtrVectorTy())
996 NewPointerOperands.push_back(nullptr);
997 else
999 OperandUse, NewAddrSpace, ValueWithNewAddrSpace, PredicatedAS,
1000 PoisonUsesToFix));
1001 }
1002
1003 switch (I->getOpcode()) {
1004 case Instruction::BitCast:
1005 return new BitCastInst(NewPointerOperands[0], NewPtrType);
1006 case Instruction::PHI: {
1007 assert(I->getType()->isPtrOrPtrVectorTy());
1008 PHINode *PHI = cast<PHINode>(I);
1009 PHINode *NewPHI = PHINode::Create(NewPtrType, PHI->getNumIncomingValues());
1010 for (unsigned Index = 0; Index < PHI->getNumIncomingValues(); ++Index) {
1011 unsigned OperandNo = PHINode::getOperandNumForIncomingValue(Index);
1012 NewPHI->addIncoming(NewPointerOperands[OperandNo],
1013 PHI->getIncomingBlock(Index));
1014 }
1015 return NewPHI;
1016 }
1017 case Instruction::GetElementPtr: {
1018 GetElementPtrInst *GEP = cast<GetElementPtrInst>(I);
1019 GetElementPtrInst *NewGEP = GetElementPtrInst::Create(
1020 GEP->getSourceElementType(), NewPointerOperands[0],
1021 SmallVector<Value *, 4>(GEP->indices()));
1022 NewGEP->setIsInBounds(GEP->isInBounds());
1023 return NewGEP;
1024 }
1025 case Instruction::Select:
1026 assert(I->getType()->isPtrOrPtrVectorTy());
1027 return SelectInst::Create(I->getOperand(0), NewPointerOperands[1],
1028 NewPointerOperands[2], "", nullptr, I);
1029 case Instruction::IntToPtr: {
1031 Value *Src = cast<Operator>(I->getOperand(0))->getOperand(0);
1032 if (Src->getType() == NewPtrType)
1033 return Src;
1034
1035 // If we had a no-op inttoptr/ptrtoint pair, we may still have inferred a
1036 // source address space from a generic pointer source need to insert a
1037 // cast back.
1038 return new AddrSpaceCastInst(Src, NewPtrType);
1039 }
1040 assert(isSafeToCastIntToPtrAddrSpace(cast<Operator>(I)));
1041 AddrSpaceCastInst *AsCast = new AddrSpaceCastInst(I, NewPtrType);
1042 AsCast->insertAfter(I);
1043 return AsCast;
1044 }
1045 default:
1046 llvm_unreachable("Unexpected opcode");
1047 }
1048}
1049
1050// Similar to cloneInstructionWithNewAddressSpace, returns a clone of the
1051// constant expression `CE` with its operands replaced as specified in
1052// ValueWithNewAddrSpace.
1053Value *InferAddressSpacesImpl::cloneConstantExprWithNewAddressSpace(
1054 ConstantExpr *CE, unsigned NewAddrSpace,
1055 const ValueToValueMapTy &ValueWithNewAddrSpace, const DataLayout *DL,
1056 const TargetTransformInfo *TTI) const {
1057 Type *TargetType =
1058 CE->getType()->isPtrOrPtrVectorTy()
1059 ? getPtrOrVecOfPtrsWithNewAS(CE->getType(), NewAddrSpace)
1060 : CE->getType();
1061
1062 switch (CE->getOpcode()) {
1063 case Instruction::AddrSpaceCast:
1064 // Because CE is flat, the source address space must be specific.
1065 // Therefore, the inferred address space must be the source space according
1066 // to our algorithm.
1067 assert(CE->getOperand(0)->getType()->getPointerAddressSpace() ==
1068 NewAddrSpace);
1069 return CE->getOperand(0);
1070
1071 case Instruction::BitCast:
1072 if (Value *NewOperand = ValueWithNewAddrSpace.lookup(CE->getOperand(0)))
1073 return ConstantExpr::getBitCast(cast<Constant>(NewOperand), TargetType);
1074 return ConstantExpr::getAddrSpaceCast(CE, TargetType);
1075
1076 case Instruction::IntToPtr:
1077 if (isNoopPtrIntCastPair(cast<Operator>(CE), *DL, TTI)) {
1078 Constant *Src = cast<ConstantExpr>(CE->getOperand(0))->getOperand(0);
1079 // If we had a no-op inttoptr/ptrtoint pair, we may still have inferred a
1080 // source address space from a generic pointer source, so insert a cast
1081 // back. See cloneInstructionWithNewAddressSpace.
1082 if (Src->getType() == TargetType)
1083 return Src;
1084 return ConstantExpr::getAddrSpaceCast(Src, TargetType);
1085 }
1086 assert(isSafeToCastIntToPtrAddrSpace(cast<Operator>(CE)));
1087 return ConstantExpr::getAddrSpaceCast(CE, TargetType);
1088
1089 case Instruction::GetElementPtr: {
1090 // Only the pointer operand is rewritten: the indices are not related to
1091 // the pointer and NewAddrSpace may not be valid for them. The pointer
1092 // operand is an address expression, but it is not guaranteed to have been
1093 // cloned already, so clone it here if needed.
1094 Constant *Base = CE->getOperand(0);
1095 Value *NewBase = ValueWithNewAddrSpace.lookup(Base);
1096 if (!NewBase)
1097 NewBase = cloneConstantExprWithNewAddressSpace(
1098 cast<ConstantExpr>(Base), NewAddrSpace, ValueWithNewAddrSpace, DL,
1099 TTI);
1100 assert(NewBase && "pointer operand of a rewritten GEP was not rewritten");
1101
1102 SmallVector<Constant *, 4> NewOperands;
1103 NewOperands.push_back(cast<Constant>(NewBase));
1104 for (unsigned Index = 1; Index < CE->getNumOperands(); ++Index)
1105 NewOperands.push_back(CE->getOperand(Index));
1106 // Needs to specify the source type while constructing a getelementptr
1107 // constant expression.
1108 return CE->getWithOperands(NewOperands, TargetType, /*OnlyIfReduced=*/false,
1109 cast<GEPOperator>(CE)->getSourceElementType());
1110 }
1111
1112 default:
1113 llvm_unreachable("unexpected constant expression");
1114 }
1115}
1116
1117// Returns a clone of the value `V`, with its operands replaced as specified in
1118// ValueWithNewAddrSpace. This function is called on every flat address
1119// expression whose address space needs to be modified, in postorder.
1120//
1121// See cloneInstructionWithNewAddressSpace for the meaning of PoisonUsesToFix.
1122Value *InferAddressSpacesImpl::cloneValueWithNewAddressSpace(
1123 Value *V, unsigned NewAddrSpace,
1124 const ValueToValueMapTy &ValueWithNewAddrSpace,
1125 const PredicatedAddrSpaceMapTy &PredicatedAS,
1126 SmallVectorImpl<const Use *> *PoisonUsesToFix) const {
1127 // All values in Postorder are flat address expressions.
1128 assert(V->getType()->getPointerAddressSpace() == FlatAddrSpace &&
1129 isAddressExpression(*V, *DL, TTI));
1130
1131 if (auto *Arg = dyn_cast<Argument>(V)) {
1132 // Arguments are address space casted in the function body, as we do not
1133 // want to change the function signature.
1134 Function *F = Arg->getParent();
1135 BasicBlock::iterator Insert = F->getEntryBlock().getFirstNonPHIIt();
1136
1137 Type *NewPtrTy = PointerType::get(Arg->getContext(), NewAddrSpace);
1138 auto *NewI = new AddrSpaceCastInst(Arg, NewPtrTy);
1139 NewI->insertBefore(Insert);
1140 return NewI;
1141 }
1142
1143 if (Instruction *I = dyn_cast<Instruction>(V)) {
1144 Value *NewV = cloneInstructionWithNewAddressSpace(
1145 I, NewAddrSpace, ValueWithNewAddrSpace, PredicatedAS, PoisonUsesToFix);
1146 if (Instruction *NewI = dyn_cast_or_null<Instruction>(NewV)) {
1147 if (NewI->getParent() == nullptr) {
1148 NewI->insertBefore(I->getIterator());
1149 NewI->takeName(I);
1150 NewI->setDebugLoc(I->getDebugLoc());
1151 }
1152 }
1153 return NewV;
1154 }
1155
1156 return cloneConstantExprWithNewAddressSpace(
1157 cast<ConstantExpr>(V), NewAddrSpace, ValueWithNewAddrSpace, DL, TTI);
1158}
1159
1160// Defines the join operation on the address space lattice (see the file header
1161// comments).
1162unsigned InferAddressSpacesImpl::joinAddressSpaces(unsigned AS1,
1163 unsigned AS2) const {
1164 if (AS1 == AS2)
1165 return AS1;
1166
1167 if (AS1 == FlatAddrSpace || AS2 == FlatAddrSpace)
1168 return FlatAddrSpace;
1169
1170 if (AS1 == UninitializedAddressSpace)
1171 return AS2;
1172 if (AS2 == UninitializedAddressSpace)
1173 return AS1;
1174
1175 return TTI->getAddressSpaceJoin(AS1, AS2);
1176}
1177
1178bool InferAddressSpacesImpl::run(Function &CurFn) {
1179 F = &CurFn;
1180 DL = &F->getDataLayout();
1181 PtrIntCastPairs.clear();
1182
1183 if (AssumeDefaultIsFlatAddressSpace)
1184 FlatAddrSpace = 0;
1185
1186 if (FlatAddrSpace == UninitializedAddressSpace) {
1188 if (FlatAddrSpace == UninitializedAddressSpace)
1189 return false;
1190 }
1191
1192 collectIntToPtrPointerOperand();
1193 // Collects all flat address expressions in postorder.
1194 std::vector<WeakTrackingVH> Postorder = collectFlatAddressExpressions(*F);
1195
1196 // Runs a data-flow analysis to refine the address spaces of every expression
1197 // in Postorder.
1198 ValueToAddrSpaceMapTy InferredAddrSpace;
1199 PredicatedAddrSpaceMapTy PredicatedAS;
1200 inferAddressSpaces(Postorder, InferredAddrSpace, PredicatedAS);
1201
1202 // Changes the address spaces of the flat address expressions who are inferred
1203 // to point to a specific address space.
1204 return rewriteWithNewAddressSpaces(Postorder, InferredAddrSpace,
1205 PredicatedAS);
1206}
1207
1208void InferAddressSpacesImpl::enqueueUsers(
1209 Value &V, const ValueToAddrSpaceMapTy &InferredAddrSpace,
1210 SetVector<Value *> &Worklist) const {
1211 for (Value *User : V.users()) {
1212 // Skip if User is already in the worklist.
1213 if (Worklist.count(User))
1214 continue;
1215
1216 ValueToAddrSpaceMapTy::const_iterator Pos = InferredAddrSpace.find(User);
1217 // Our algorithm only updates the address spaces of flat address
1218 // expressions, which are those in InferredAddrSpace.
1219 if (Pos == InferredAddrSpace.end())
1220 continue;
1221
1222 // Function updateAddressSpace moves the address space down a lattice path.
1223 // Therefore, nothing to do if User is already inferred as flat (the bottom
1224 // element in the lattice).
1225 if (Pos->second == FlatAddrSpace)
1226 continue;
1227
1228 Worklist.insert(User);
1229 }
1230
1231 // An inttoptr that round-trips a pointer depends on that pointer, but the
1232 // chain between them runs through a ptrtoint, which is not an address
1233 // expression and so is absent from InferredAddrSpace. Requeue such
1234 // dependents directly; PtrIntCastPairs holds only round trips already proven
1235 // safe, so this scan is over a handful of entries rather than the function.
1236 for (auto &[I2P, OldPtr] : PtrIntCastPairs) {
1237 if (OldPtr != &V)
1238 continue;
1239 auto Pos = InferredAddrSpace.find(I2P);
1240 if (Pos == InferredAddrSpace.end() || Pos->second == FlatAddrSpace)
1241 continue;
1242 Worklist.insert(const_cast<Value *>(I2P));
1243 }
1244}
1245
1246void InferAddressSpacesImpl::runToFixPoint(
1247 SetVector<Value *> &Worklist, ValueToAddrSpaceMapTy &InferredAddrSpace,
1248 PredicatedAddrSpaceMapTy &PredicatedAS) const {
1249 while (!Worklist.empty()) {
1250 Value *V = Worklist.pop_back_val();
1251
1252 // Try to update the address space of the stack top according to the
1253 // address spaces of its operands.
1254 if (!updateAddressSpace(*V, InferredAddrSpace, PredicatedAS))
1255 continue;
1256
1257 enqueueUsers(*V, InferredAddrSpace, Worklist);
1258 }
1259}
1260
1261// Constants need to be tracked through RAUW to handle cases with nested
1262// constant expressions, so wrap values in WeakTrackingVH.
1263void InferAddressSpacesImpl::inferAddressSpaces(
1264 ArrayRef<WeakTrackingVH> Postorder,
1265 ValueToAddrSpaceMapTy &InferredAddrSpace,
1266 PredicatedAddrSpaceMapTy &PredicatedAS) const {
1267 SetVector<Value *> Worklist(llvm::from_range, Postorder);
1268 // Initially, all expressions are in the uninitialized address space.
1269 for (Value *V : Postorder)
1270 InferredAddrSpace[V] = UninitializedAddressSpace;
1271
1272 runToFixPoint(Worklist, InferredAddrSpace, PredicatedAS);
1273
1274 // A value still uninitialized here is stuck in a cycle of uninitialized
1275 // values and carries no address space information. Lower it to flat so its
1276 // users join to flat, instead of being rewritten to reference an operand
1277 // that rewriteWithNewAddressSpaces() never converts.
1278 SmallVector<Value *, 4> Lowered;
1279 for (Value *V : Postorder) {
1280 ValueToAddrSpaceMapTy::iterator I = InferredAddrSpace.find(V);
1281 if (I->second == UninitializedAddressSpace) {
1282 I->second = FlatAddrSpace;
1283 Lowered.push_back(V);
1284 }
1285 }
1286
1287 for (Value *V : Lowered)
1288 enqueueUsers(*V, InferredAddrSpace, Worklist);
1289
1290 runToFixPoint(Worklist, InferredAddrSpace, PredicatedAS);
1291}
1292
1293unsigned
1294InferAddressSpacesImpl::getPredicatedAddrSpace(const Value &Ptr,
1295 const Value *UserCtx) const {
1296 const Instruction *UserCtxI = dyn_cast<Instruction>(UserCtx);
1297 if (!UserCtxI)
1299
1300 const Value *StrippedPtr = Ptr.stripInBoundsOffsets();
1301 for (auto &AssumeVH : AC.assumptionsFor(StrippedPtr)) {
1302 if (!AssumeVH)
1303 continue;
1304 CallInst *CI = cast<CallInst>(AssumeVH);
1305 if (!isValidAssumeForContext(CI, UserCtxI, DT))
1306 continue;
1307
1308 const Value *Ptr;
1309 unsigned AS;
1310 std::tie(Ptr, AS) = TTI->getPredicatedAddrSpace(CI->getArgOperand(0));
1311 if (Ptr)
1312 return AS;
1313 }
1314
1316}
1317
1318bool InferAddressSpacesImpl::updateAddressSpace(
1319 const Value &V, ValueToAddrSpaceMapTy &InferredAddrSpace,
1320 PredicatedAddrSpaceMapTy &PredicatedAS) const {
1321 assert(InferredAddrSpace.count(&V));
1322
1323 LLVM_DEBUG(dbgs() << "Updating the address space of\n " << V << '\n');
1324
1325 // The new inferred address space equals the join of the address spaces
1326 // of all its pointer operands.
1327 unsigned NewAS = UninitializedAddressSpace;
1328
1329 // isAddressExpression should guarantee that V is an operator or an argument.
1331
1332 unsigned AS = TTI->getAssumedAddrSpace(&V);
1333 if (AS != UninitializedAddressSpace) {
1334 // Use the assumed address space directly.
1335 NewAS = AS;
1336 } else {
1337 // Otherwise, infer the address space from its pointer operands.
1338 SmallVector<Constant *, 2> ConstantPtrOps;
1339 SmallVector<Value *, 2> PtrOps = getPointerOperands(V, *DL, TTI);
1340 for (Value *PtrOperand : PtrOps) {
1341 auto I = InferredAddrSpace.find(PtrOperand);
1342 unsigned OperandAS;
1343 if (I == InferredAddrSpace.end()) {
1344 OperandAS = PtrOperand->getType()->getPointerAddressSpace();
1345 if (auto *C = dyn_cast<Constant>(PtrOperand);
1346 C && OperandAS == FlatAddrSpace) {
1347 // Defer joining the address space of constant pointer operands.
1348 ConstantPtrOps.push_back(C);
1349 continue;
1350 }
1351 if (OperandAS == FlatAddrSpace) {
1352 // Check AC for assumption dominating V.
1353 unsigned AS = getPredicatedAddrSpace(*PtrOperand, &V);
1354 if (AS != UninitializedAddressSpace) {
1356 << " deduce operand AS from the predicate addrspace "
1357 << AS << '\n');
1358 OperandAS = AS;
1359 // Record this use with the predicated AS.
1360 PredicatedAS[std::make_pair(&V, PtrOperand)] = OperandAS;
1361 }
1362 }
1363 } else
1364 OperandAS = I->second;
1365
1366 // join(flat, *) = flat. So we can break if NewAS is already flat.
1367 NewAS = joinAddressSpaces(NewAS, OperandAS);
1368 if (NewAS == FlatAddrSpace)
1369 break;
1370 }
1371
1372 if (NewAS != FlatAddrSpace && NewAS != UninitializedAddressSpace) {
1373 if (any_of(ConstantPtrOps, [=](Constant *C) {
1374 return !isSafeToCastConstAddrSpace(C, NewAS);
1375 }))
1376 NewAS = FlatAddrSpace;
1377 }
1378
1379 // operator(flat const, flat const, ...) -> flat
1380 if (NewAS == UninitializedAddressSpace &&
1381 PtrOps.size() == ConstantPtrOps.size())
1382 NewAS = FlatAddrSpace;
1383 }
1384
1385 unsigned OldAS = InferredAddrSpace.lookup(&V);
1386 assert(OldAS != FlatAddrSpace);
1387 if (OldAS == NewAS)
1388 return false;
1389
1390 // If any updates are made, grabs its users to the worklist because
1391 // their address spaces can also be possibly updated.
1392 LLVM_DEBUG(dbgs() << " to " << NewAS << '\n');
1393 InferredAddrSpace[&V] = NewAS;
1394 return true;
1395}
1396
1397/// Replace operand \p OpIdx in \p Inst, if the value is the same as \p OldVal
1398/// with \p NewVal.
1399static bool replaceOperandIfSame(Instruction *Inst, unsigned OpIdx,
1400 Value *OldVal, Value *NewVal) {
1401 Use &U = Inst->getOperandUse(OpIdx);
1402 if (U.get() == OldVal) {
1403 U.set(NewVal);
1404 return true;
1405 }
1406
1407 return false;
1408}
1409
1410template <typename InstrType>
1412 InstrType *MemInstr, Value *OldV,
1413 Value *NewV) {
1414 unsigned AddrSpace = NewV->getType()->getPointerAddressSpace();
1415 if (!MemInstr->isVolatile() || TTI.hasVolatileVariant(MemInstr, AddrSpace)) {
1416 return replaceOperandIfSame(MemInstr, InstrType::getPointerOperandIndex(),
1417 OldV, NewV);
1418 }
1419
1420 return false;
1421}
1422
1423/// If \p OldV is used as the pointer operand of a compatible memory operation
1424/// \p Inst, replaces the pointer operand with NewV.
1425///
1426/// This covers memory instructions with a single pointer operand that can have
1427/// its address space changed by simply mutating the use to a new value.
1428///
1429/// \p returns true the user replacement was made.
1431 User *Inst, Value *OldV, Value *NewV) {
1432 if (auto *LI = dyn_cast<LoadInst>(Inst))
1433 return replaceSimplePointerUse(TTI, LI, OldV, NewV);
1434
1435 if (auto *SI = dyn_cast<StoreInst>(Inst))
1436 return replaceSimplePointerUse(TTI, SI, OldV, NewV);
1437
1438 if (auto *RMW = dyn_cast<AtomicRMWInst>(Inst))
1439 return replaceSimplePointerUse(TTI, RMW, OldV, NewV);
1440
1441 if (auto *CmpX = dyn_cast<AtomicCmpXchgInst>(Inst))
1442 return replaceSimplePointerUse(TTI, CmpX, OldV, NewV);
1443
1444 return false;
1445}
1446
1447/// Update memory intrinsic uses that require more complex processing than
1448/// simple memory instructions. These require re-mangling and may have multiple
1449/// pointer operands.
1451 Value *NewV) {
1452 IRBuilder<> B(MI);
1453 if (auto *MSI = dyn_cast<MemSetInst>(MI)) {
1454 B.CreateMemSet(NewV, MSI->getValue(), MSI->getLength(), MSI->getDestAlign(),
1455 false, // isVolatile
1456 MI->getAAMetadata());
1457 } else if (auto *MTI = dyn_cast<MemTransferInst>(MI)) {
1458 Value *Src = MTI->getRawSource();
1459 Value *Dest = MTI->getRawDest();
1460
1461 // Be careful in case this is a self-to-self copy.
1462 if (Src == OldV)
1463 Src = NewV;
1464
1465 if (Dest == OldV)
1466 Dest = NewV;
1467
1468 if (auto *MCI = dyn_cast<MemCpyInst>(MTI)) {
1469 if (MCI->isForceInlined())
1470 B.CreateMemCpyInline(Dest, MTI->getDestAlign(), Src,
1471 MTI->getSourceAlign(), MTI->getLength(),
1472 false, // isVolatile
1473 MI->getAAMetadata());
1474 else
1475 B.CreateMemCpy(Dest, MTI->getDestAlign(), Src, MTI->getSourceAlign(),
1476 MTI->getLength(),
1477 false, // isVolatile
1478 MI->getAAMetadata());
1479 } else {
1481 B.CreateMemMove(Dest, MTI->getDestAlign(), Src, MTI->getSourceAlign(),
1482 MTI->getLength(),
1483 false, // isVolatile
1484 MI->getAAMetadata());
1485 }
1486 } else
1487 llvm_unreachable("unhandled MemIntrinsic");
1488
1489 MI->eraseFromParent();
1490 return true;
1491}
1492
1493// \p returns true if it is OK to change the address space of constant \p C with
1494// a ConstantExpr addrspacecast.
1495bool InferAddressSpacesImpl::isSafeToCastConstAddrSpace(Constant *C,
1496 unsigned NewAS) const {
1498
1499 unsigned SrcAS = C->getType()->getPointerAddressSpace();
1500 if (SrcAS == NewAS || isa<UndefValue>(C))
1501 return true;
1502
1503 // Prevent illegal casts between different non-flat address spaces.
1504 if (SrcAS != FlatAddrSpace && NewAS != FlatAddrSpace)
1505 return false;
1506
1508 return true;
1509
1510 if (auto *Op = dyn_cast<Operator>(C)) {
1511 // If we already have a constant addrspacecast, it should be safe to cast it
1512 // off.
1513 if (Op->getOpcode() == Instruction::AddrSpaceCast)
1514 return isSafeToCastConstAddrSpace(cast<Constant>(Op->getOperand(0)),
1515 NewAS);
1516
1517 if (Op->getOpcode() == Instruction::IntToPtr &&
1518 Op->getType()->getPointerAddressSpace() == FlatAddrSpace)
1519 return true;
1520 }
1521
1522 return false;
1523}
1524
1527 User *CurUser = I->getUser();
1528 ++I;
1529
1530 while (I != End && I->getUser() == CurUser)
1531 ++I;
1532
1533 return I;
1534}
1535
1536void InferAddressSpacesImpl::performPointerReplacement(
1537 Value *V, Value *NewV, Use &U, ValueToValueMapTy &ValueWithNewAddrSpace,
1538 SmallVectorImpl<Instruction *> &DeadInstructions) const {
1539
1540 User *CurUser = U.getUser();
1541
1542 // Skip if the current user is the new value itself.
1543 if (CurUser == NewV)
1544 return;
1545
1546 auto *CurUserI = dyn_cast<Instruction>(CurUser);
1547 if (!CurUserI || CurUserI->getFunction() != F)
1548 return;
1549
1550 if (replaceIfSimplePointerUse(*TTI, CurUser, V, NewV))
1551 return;
1552
1553 // Handle more complex cases like intrinsic that need to be remangled.
1554 if (auto *MI = dyn_cast<MemIntrinsic>(CurUser)) {
1555 if (!MI->isVolatile() && handleMemIntrinsicPtrUse(MI, V, NewV))
1556 return;
1557 }
1558
1559 if (auto *II = dyn_cast<IntrinsicInst>(CurUser)) {
1560 if (rewriteIntrinsicOperands(II, V, NewV))
1561 return;
1562 }
1563
1564 if (ICmpInst *Cmp = dyn_cast<ICmpInst>(CurUserI)) {
1565 // If we can infer that both pointers are in the same addrspace,
1566 // transform e.g.
1567 // %cmp = icmp eq float* %p, %q
1568 // into
1569 // %cmp = icmp eq float addrspace(3)* %new_p, %new_q
1570
1571 unsigned NewAS = NewV->getType()->getPointerAddressSpace();
1572 int SrcIdx = U.getOperandNo();
1573 int OtherIdx = (SrcIdx == 0) ? 1 : 0;
1574 Value *OtherSrc = Cmp->getOperand(OtherIdx);
1575
1576 if (Value *OtherNewV = ValueWithNewAddrSpace.lookup(OtherSrc)) {
1577 if (OtherNewV->getType()->getPointerAddressSpace() == NewAS) {
1578 Cmp->setOperand(OtherIdx, OtherNewV);
1579 Cmp->setOperand(SrcIdx, NewV);
1580 return;
1581 }
1582 }
1583
1584 // Even if the type mismatches, we can cast the constant.
1585 if (auto *KOtherSrc = dyn_cast<Constant>(OtherSrc)) {
1586 if (isSafeToCastConstAddrSpace(KOtherSrc, NewAS)) {
1587 Cmp->setOperand(SrcIdx, NewV);
1588 Cmp->setOperand(OtherIdx, ConstantExpr::getAddrSpaceCast(
1589 KOtherSrc, NewV->getType()));
1590 return;
1591 }
1592 }
1593 }
1594
1595 if (AddrSpaceCastInst *ASC = dyn_cast<AddrSpaceCastInst>(CurUserI)) {
1596 unsigned NewAS = NewV->getType()->getPointerAddressSpace();
1597 if (ASC->getDestAddressSpace() == NewAS) {
1598 ASC->replaceAllUsesWith(NewV);
1599 DeadInstructions.push_back(ASC);
1600 return;
1601 }
1602 }
1603
1604 // Otherwise, replaces the use with flat(NewV).
1605 if (isa<Instruction>(V) || isa<Instruction>(NewV)) {
1606 // Don't create a copy of the original addrspacecast.
1607 if (U == V && isa<AddrSpaceCastInst>(V))
1608 return;
1609
1610 // Insert the addrspacecast after NewV.
1611 BasicBlock::iterator InsertPos;
1612 if (Instruction *NewVInst = dyn_cast<Instruction>(NewV))
1613 InsertPos = std::next(NewVInst->getIterator());
1614 else
1615 InsertPos = std::next(cast<Instruction>(V)->getIterator());
1616
1617 while (isa<PHINode>(InsertPos))
1618 ++InsertPos;
1619 // This instruction may contain multiple uses of V, update them all.
1620 CurUser->replaceUsesOfWith(
1621 V, new AddrSpaceCastInst(NewV, V->getType(), "", InsertPos));
1622 } else {
1623 CurUserI->replaceUsesOfWith(
1624 V, ConstantExpr::getAddrSpaceCast(cast<Constant>(NewV), V->getType()));
1625 }
1626}
1627
1628bool InferAddressSpacesImpl::rewriteWithNewAddressSpaces(
1629 ArrayRef<WeakTrackingVH> Postorder,
1630 const ValueToAddrSpaceMapTy &InferredAddrSpace,
1631 const PredicatedAddrSpaceMapTy &PredicatedAS) const {
1632 // For each address expression to be modified, creates a clone of it with its
1633 // pointer operands converted to the new address space. Since the pointer
1634 // operands are converted, the clone is naturally in the new address space by
1635 // construction.
1636 ValueToValueMapTy ValueWithNewAddrSpace;
1637 SmallVector<const Use *, 32> PoisonUsesToFix;
1638 for (Value *V : Postorder) {
1639 unsigned NewAddrSpace = InferredAddrSpace.lookup(V);
1640
1641 // In some degenerate cases (e.g. invalid IR in unreachable code), we may
1642 // not even infer the value to have its original address space.
1643 if (NewAddrSpace == UninitializedAddressSpace)
1644 continue;
1645
1646 if (V->getType()->getPointerAddressSpace() != NewAddrSpace) {
1647 Value *New =
1648 cloneValueWithNewAddressSpace(V, NewAddrSpace, ValueWithNewAddrSpace,
1649 PredicatedAS, &PoisonUsesToFix);
1650 if (New)
1651 ValueWithNewAddrSpace[V] = New;
1652 }
1653 }
1654
1655 if (ValueWithNewAddrSpace.empty())
1656 return false;
1657
1658 // Fixes all the poison uses generated by cloneInstructionWithNewAddressSpace.
1659 for (const Use *PoisonUse : PoisonUsesToFix) {
1660 User *V = PoisonUse->getUser();
1661 User *NewV = cast_or_null<User>(ValueWithNewAddrSpace.lookup(V));
1662 if (!NewV)
1663 continue;
1664
1665 unsigned OperandNo = PoisonUse->getOperandNo();
1666 assert(isa<PoisonValue>(NewV->getOperand(OperandNo)));
1667 unsigned NewAS =
1668 NewV->getOperand(OperandNo)->getType()->getPointerAddressSpace();
1670 *PoisonUse, NewAS, ValueWithNewAddrSpace, PredicatedAS, nullptr);
1671 NewV->setOperand(OperandNo, NewOp);
1672 }
1673
1674 SmallVector<Instruction *, 16> DeadInstructions;
1675
1676 // Replaces the uses of the old address expressions with the new ones.
1677 for (const WeakTrackingVH &WVH : Postorder) {
1678 assert(WVH && "value was unexpectedly deleted");
1679 Value *V = WVH;
1680 Value *NewV = ValueWithNewAddrSpace.lookup(V);
1681 if (NewV == nullptr)
1682 continue;
1683
1684 LLVM_DEBUG(dbgs() << "Replacing the uses of " << *V << "\n with\n "
1685 << *NewV << '\n');
1686
1687 if (Constant *C = dyn_cast<Constant>(V)) {
1688 Constant *Replace =
1690 if (C != Replace) {
1691 LLVM_DEBUG(dbgs() << "Inserting replacement const cast: " << Replace
1692 << ": " << *Replace << '\n');
1693 SmallVector<User *, 16> WorkList;
1694 for (User *U : make_early_inc_range(C->users())) {
1695 if (auto *I = dyn_cast<Instruction>(U)) {
1696 if (I->getFunction() == F)
1697 I->replaceUsesOfWith(C, Replace);
1698 } else {
1699 WorkList.append(U->user_begin(), U->user_end());
1700 }
1701 }
1702 if (!WorkList.empty()) {
1703 // Use a new map for each constant. The mapper caches every constant
1704 // that it visits, so an entry from an earlier constant could stop
1705 // this remap, e.g. when one instruction uses two rewritten constants.
1706 ValueToValueMapTy VMap;
1707 VMap[C] = Replace;
1708 ValueMapper VMapper(VMap,
1710 DenseSet<User *> Visited{WorkList.begin(), WorkList.end()};
1711 while (!WorkList.empty()) {
1712 User *U = WorkList.pop_back_val();
1713 if (auto *I = dyn_cast<Instruction>(U)) {
1714 if (I->getFunction() == F)
1715 VMapper.remapInstruction(*I);
1716 continue;
1717 }
1718 for (User *U2 : U->users())
1719 if (Visited.insert(U2).second)
1720 WorkList.push_back(U2);
1721 }
1722 }
1723 V = Replace;
1724 }
1725 }
1726
1727 Value::use_iterator I, E, Next;
1728 for (I = V->use_begin(), E = V->use_end(); I != E;) {
1729 Use &U = *I;
1730
1731 // Some users may see the same pointer operand in multiple operands. Skip
1732 // to the next instruction.
1733 I = skipToNextUser(I, E);
1734
1735 performPointerReplacement(V, NewV, U, ValueWithNewAddrSpace,
1736 DeadInstructions);
1737 }
1738
1739 if (V->use_empty()) {
1740 if (Instruction *I = dyn_cast<Instruction>(V))
1741 DeadInstructions.push_back(I);
1742 }
1743 }
1744
1745 // Deleting one instruction may recursively delete another queued
1746 // instruction. Create handles before the first deletion so overlapping
1747 // entries are nulled instead of leaving dangling pointers.
1748 auto DeadInstructionHandles =
1749 to_vector_of<WeakTrackingVH, 16>(DeadInstructions);
1750 RecursivelyDeleteTriviallyDeadInstructions(DeadInstructionHandles);
1751
1752 return true;
1753}
1754
1755bool InferAddressSpaces::runOnFunction(Function &F) {
1756 if (skipFunction(F))
1757 return false;
1758
1759 auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
1760 DominatorTree *DT = DTWP ? &DTWP->getDomTree() : nullptr;
1761 return InferAddressSpacesImpl(
1762 getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F), DT,
1763 &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F),
1764 FlatAddrSpace, /*AssumeDefaultIsFlatAddressSpace=*/false)
1765 .run(F);
1766}
1767
1769 return new InferAddressSpaces(AddressSpace);
1770}
1771
1773 bool AssumeDefaultIsFlatAddressSpace)
1774 : FlatAddrSpace(UninitializedAddressSpace),
1775 AssumeDefaultIsFlatAddressSpace(AssumeDefaultIsFlatAddressSpace) {}
1777 unsigned AddressSpace, bool AssumeDefaultIsFlatAddressSpace)
1778 : FlatAddrSpace(AddressSpace),
1779 AssumeDefaultIsFlatAddressSpace(AssumeDefaultIsFlatAddressSpace) {}
1780
1783 bool Changed =
1784 InferAddressSpacesImpl(AM.getResult<AssumptionAnalysis>(F),
1786 &AM.getResult<TargetIRAnalysis>(F), FlatAddrSpace,
1787 AssumeDefaultIsFlatAddressSpace)
1788 .run(F);
1789 if (Changed) {
1792 return PA;
1793 }
1794 return PreservedAnalyses::all();
1795}
1796
1798 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
1799 static_cast<PassInfoMixin<InferAddressSpacesPass> *>(this)->printPipeline(
1800 OS, MapClassName2PassName);
1801 if (AssumeDefaultIsFlatAddressSpace)
1802 OS << "<assume-default-is-flat-addrspace>";
1803}
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
Rewrite undef for PHI
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Expand Atomic instructions
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define LLVM_UNLIKELY(EXPR)
Definition Compiler.h:348
This file contains the declarations for the subclasses of Constant, which represent the different fla...
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
static bool runOnFunction(Function &F, bool PostInlining)
#define DEBUG_TYPE
Hexagon Common GEP
IRTranslator LLVM IR MI
This header defines various interfaces for pass management in LLVM.
This defines the Use class.
static bool replaceOperandIfSame(Instruction *Inst, unsigned OpIdx, Value *OldVal, Value *NewVal)
Replace operand OpIdx in Inst, if the value is the same as OldVal with NewVal.
static bool isNoopPtrIntCastPair(const Operator *I2P, const DataLayout &DL, const TargetTransformInfo *TTI)
static bool replaceIfSimplePointerUse(const TargetTransformInfo &TTI, User *Inst, Value *OldV, Value *NewV)
If OldV is used as the pointer operand of a compatible memory operation Inst, replaces the pointer op...
static Value * phiNodeOperandWithNewAddressSpace(AddrSpaceCastInst *NewI, Value *Operand)
static bool handleMemIntrinsicPtrUse(MemIntrinsic *MI, Value *OldV, Value *NewV)
Update memory intrinsic uses that require more complex processing than simple memory instructions.
static Value * operandWithNewAddressSpaceOrCreatePoison(const Use &OperandUse, unsigned NewAddrSpace, const ValueToValueMapTy &ValueWithNewAddrSpace, const PredicatedAddrSpaceMapTy &PredicatedAS, SmallVectorImpl< const Use * > *PoisonUsesToFix)
static Value::use_iterator skipToNextUser(Value::use_iterator I, Value::use_iterator End)
Infer address static false Type * getPtrOrVecOfPtrsWithNewAS(Type *Ty, unsigned NewAddrSpace)
static bool replaceSimplePointerUse(const TargetTransformInfo &TTI, InstrType *MemInstr, Value *OldV, Value *NewV)
static APInt computeMaxChangedPtrBits(const Operator *Op, const Value *Mask, const DataLayout &DL, AssumptionCache *AC, const DominatorTree *DT)
static const unsigned UninitializedAddressSpace
#define F(x, y, z)
Definition MD5.cpp:54
#define I(x, y, z)
Definition MD5.cpp:57
Machine Check Debug Module
uint64_t IntrinsicInst * II
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition PassSupport.h:42
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition PassSupport.h:44
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition PassSupport.h:39
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallVector class.
#define LLVM_DEBUG(...)
Definition Debug.h:119
static SymbolRef::Type getType(const Symbol *Sym)
Definition TapiFile.cpp:39
This pass exposes codegen information to IR-level passes.
Value * RHS
Value * LHS
Class for arbitrary precision integers.
Definition APInt.h:78
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
Definition APInt.h:230
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
Definition APInt.h:376
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition APInt.h:1508
bool isSubsetOf(const APInt &RHS) const
This operation checks that all bits set in this APInt are also set in RHS.
Definition APInt.h:1261
This class represents a conversion between pointers from one address space to another.
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
AnalysisUsage & addRequired()
LLVM_ABI void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition Pass.cpp:280
A function analysis which provides an AssumptionCache.
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of @llvm.assume calls within a function.
MutableArrayRef< ResultElem > assumptionsFor(const Value *V)
Access the list of assumptions which affect this value.
InstListType::iterator iterator
Instruction iterators...
Definition BasicBlock.h:170
Represents analyses that only rely on functions' control flow.
Definition Analysis.h:73
Value * getArgOperand(unsigned i) const
static LLVM_ABI bool isNoopCast(Instruction::CastOps Opcode, Type *SrcTy, Type *DstTy, const DataLayout &DL)
A no-op cast is one that can be effected without changing any bits.
static LLVM_ABI Constant * getAddrSpaceCast(Constant *C, Type *Ty, bool OnlyIfReduced=false)
This is an important base class in LLVM.
Definition Constant.h:44
A parsed version of the target data layout string in and methods for querying it.
Definition DataLayout.h:64
ValueT lookup(const_arg_type_t< KeyT > Val) const
Return the entry for the specified key, or a default constructed value if no such entry exists.
Definition DenseMap.h:793
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition DenseMap.h:827
Analysis pass which computes a DominatorTree.
Definition Dominators.h:241
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition Dominators.h:122
FunctionPass class - This class is used to implement most global optimizations.
Definition Pass.h:312
static GetElementPtrInst * Create(Type *PointeeType, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
LLVM_ABI void setIsInBounds(bool b=true)
Set or clear the inbounds flag on this GEP instruction.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition IRBuilder.h:2987
LLVM_ABI InferAddressSpacesPass(bool AssumeDefaultIsFlatAddressSpace=false)
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
LLVM_ABI void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
LLVM_ABI void insertBefore(InstListType::iterator InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified position.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
bool isBitwiseLogicOp() const
Return true if this is and/or/xor.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
LLVM_ABI void insertAfter(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately after the specified instruction.
This is the common base class for memset/memcpy/memmove.
This is a utility class that provides an abstraction for the common functionality between Instruction...
Definition Operator.h:33
unsigned getOpcode() const
Return the opcode for this Instruction or ConstantExpr.
Definition Operator.h:43
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
static unsigned getOperandNumForIncomingValue(unsigned i)
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
static LLVM_ABI PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
static LLVM_ABI PointerType * get(LLVMContext &C, unsigned AddressSpace)
This constructs an opaque pointer to an object in a numbered address space.
Definition Type.cpp:887
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
A set of analyses that are preserved following a run of a transformation pass.
Definition Analysis.h:112
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition Analysis.h:118
PreservedAnalyses & preserveSet()
Mark an analysis set as preserved.
Definition Analysis.h:151
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", InsertPosition InsertBefore=nullptr, const Instruction *MDFrom=nullptr)
size_type count(const_arg_type key) const
Count the number of elements of a given key in the SetVector.
Definition SetVector.h:268
bool empty() const
Determine if the SetVector is empty or not.
Definition SetVector.h:100
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition SetVector.h:157
value_type pop_back_val()
Definition SetVector.h:285
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Represent a constant reference to a string, i.e.
Definition StringRef.h:56
Analysis pass providing the TargetTransformInfo.
Wrapper pass for TargetTransformInfo.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
LLVM_ABI unsigned getAssumedAddrSpace(const Value *V) const
LLVM_ABI std::pair< KnownBits, KnownBits > computeKnownBitsAddrSpaceCast(unsigned ToAS, const Value &PtrOp) const
LLVM_ABI bool isNoopAddrSpaceCast(unsigned FromAS, unsigned ToAS) const
LLVM_ABI std::pair< const Value *, unsigned > getPredicatedAddrSpace(const Value *V) const
LLVM_ABI unsigned getAddressSpaceJoin(unsigned AS1, unsigned AS2) const
Return the most specific common address space containing AS1 and AS2.
LLVM_ABI bool collectFlatAddressOperands(SmallVectorImpl< int > &OpIndexes, Intrinsic::ID IID) const
Return any intrinsic address operand indexes which may be rewritten if they use a flat address space ...
LLVM_ABI Value * rewriteIntrinsicWithAddressSpace(IntrinsicInst *II, Value *OldV, Value *NewV) const
Rewrite intrinsic call II such that OldV will be replaced with NewV, which has a different address sp...
LLVM_ABI unsigned getFlatAddressSpace() const
Returns the address space ID for a target's 'flat' address space.
LLVM_ABI APInt getAddrSpaceCastPreservedPtrMask(unsigned SrcAS, unsigned DstAS) const
Returns a mask indicating which bits of a pointer remain unchanged when casting between address space...
The instances of the Type class are immutable: once they are created, they are never changed.
Definition Type.h:46
bool isVectorTy() const
True if this is an instance of VectorType.
Definition Type.h:283
LLVM_ABI unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
LLVM_ABI Type * getWithNewBitWidth(unsigned NewBitWidth) const
Given an integer or vector type, change the lane bitwidth to NewBitwidth, whilst keeping the old numb...
LLVM_ABI unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
Definition Type.cpp:222
bool isPtrOrPtrVectorTy() const
Return true if this is a pointer type or a vector of pointer types.
Definition Type.h:280
A Use represents the edge between a Value definition and its users.
Definition Use.h:35
User * getUser() const
Returns the User that contains this Use.
Definition Use.h:61
Value * get() const
Definition Use.h:55
const Use & getOperandUse(unsigned i) const
Definition User.h:220
void setOperand(unsigned i, Value *Val)
Definition User.h:212
LLVM_ABI bool replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Definition User.cpp:25
Value * getOperand(unsigned i) const
Definition User.h:207
ValueT lookup(const KeyT &Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition ValueMap.h:167
bool empty() const
Definition ValueMap.h:143
LLVM Value Representation.
Definition Value.h:75
Type * getType() const
All values are typed, get the type of this value.
Definition Value.h:257
LLVM_ABI const Value * stripInBoundsOffsets(function_ref< void(const Value *)> Func=[](const Value *) {}) const
Strip off pointer casts and inbounds GEPs.
Definition Value.cpp:823
use_iterator_impl< Use > use_iterator
Definition Value.h:355
LLVM_ABI const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
Definition Value.cpp:707
std::pair< iterator, bool > insert(const ValueT &V)
Definition DenseSet.h:210
An efficient, type-erasing, non-owning reference to a callable.
const ParentTy * getParent() const
Definition ilist_node.h:34
self_iterator getIterator()
Definition ilist_node.h:123
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition raw_ostream.h:53
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
LLVM_ABI Function * getOrInsertDeclaration(Module *M, ID id, ArrayRef< Type * > OverloadTys={})
Look up the Function declaration of the intrinsic id in the Module M.
bool match(Val *V, const Pattern &P)
auto m_Value()
Match an arbitrary value and ignore it.
CastOperator_match< OpTy, Instruction::PtrToInt > m_PtrToInt(const OpTy &Op)
Matches PtrToInt.
@ CE
Windows NT (Windows on ARM)
Definition MCAsmInfo.h:51
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
@ User
could "use" a pointer
NodeAddr< UseNode * > Use
Definition RDFGraph.h:385
friend class Instruction
Iterator for Instructions in a `BasicBlock.
Definition BasicBlock.h:73
This is an optimization pass for GlobalISel generic memory operations.
LLVM_ABI bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
Definition Local.cpp:522
@ Known
Known to have no common set bits.
LLVM_ABI void initializeInferAddressSpacesPass(PassRegistry &)
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:643
constexpr from_range_t from_range
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition STLExtras.h:649
LLVM_ABI void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true, unsigned Depth=0)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
auto cast_or_null(const Y &Val)
Definition Casting.h:714
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
Definition InstrProf.h:143
LLVM_ABI bool isValidAssumeForContext(const Instruction *I, const Instruction *CtxI, const DominatorTree *DT=nullptr, bool AllowEphemerals=false)
Return true if it is valid to use the assumptions provided by an assume intrinsic,...
auto dyn_cast_or_null(const Y &Val)
Definition Casting.h:753
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1762
@ RF_IgnoreMissingLocals
If this flag is set, the remapper ignores missing function-local entries (Argument,...
Definition ValueMapper.h:98
@ RF_NoModuleLevelChanges
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
Definition ValueMapper.h:80
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:209
IRBuilder(LLVMContext &, FolderTy, InserterTy) -> IRBuilder< FolderTy, InserterTy >
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
Definition Casting.h:547
TargetTransformInfo TTI
DWARFExpression::Operation Op
ArrayRef(const T &OneElt) -> ArrayRef< T >
ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy
LLVM_ABI FunctionPass * createInferAddressSpacesPass(unsigned AddressSpace=~0u)
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:559
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Next
Definition InstrProf.h:147
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
@ End
Run the machine verifier once, at the end of the pipeline.
Definition CodeGen.h:320
SmallVector< Out, Size > to_vector_of(R &&Range)
unsigned getBitWidth() const
Get the bit width of this value.
Definition KnownBits.h:44
unsigned countMaxActiveBits() const
Returns the maximum number of bits needed to represent all possible unsigned values with these known ...
Definition KnownBits.h:310
static KnownBits sub(const KnownBits &LHS, const KnownBits &RHS, bool NSW=false, bool NUW=false)
Compute knownbits resulting from subtraction of LHS and RHS.
Definition KnownBits.h:376