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
91#include "llvm/Transforms/Scalar/InferAddressSpaces.h"
92#include "llvm/ADT/ArrayRef.h"
93#include "llvm/ADT/DenseMap.h"
94#include "llvm/ADT/DenseSet.h"
95#include "llvm/ADT/SetVector.h"
96#include "llvm/ADT/SmallVector.h"
97#include "llvm/Analysis/AssumptionCache.h"
98#include "llvm/Analysis/TargetTransformInfo.h"
99#include "llvm/Analysis/ValueTracking.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"
110#include "llvm/IR/IntrinsicInst.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"
121#include "llvm/InitializePasses.h"
122#include "llvm/Pass.h"
123#include "llvm/Support/Casting.h"
124#include "llvm/Support/Debug.h"
125#include "llvm/Support/ErrorHandling.h"
126#include "llvm/Support/KnownBits.h"
127#include "llvm/Support/raw_ostream.h"
128#include "llvm/Transforms/Scalar.h"
129#include "llvm/Transforms/Utils/Local.h"
130#include "llvm/Transforms/Utils/ValueMapper.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 =
156 DenseMap<std::pair<const Value *, const Value *>, unsigned>;
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) {
167 initializeInferAddressSpacesPass(*PassRegistry::getPassRegistry());
168 }
169 InferAddressSpaces(unsigned AS) : FunctionPass(ID), FlatAddrSpace(AS) {
170 initializeInferAddressSpacesPass(*PassRegistry::getPassRegistry());
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(Val: 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)
309INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
310INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
311INITIALIZE_PASS_END(InferAddressSpaces, DEBUG_TYPE, "Infer address spaces",
312 false, false)
313
314static Type *getPtrOrVecOfPtrsWithNewAS(Type *Ty, unsigned NewAddrSpace) {
315 assert(Ty->isPtrOrPtrVectorTy());
316 PointerType *NPT = PointerType::get(C&: Ty->getContext(), AddressSpace: NewAddrSpace);
317 return Ty->getWithNewType(EltTy: 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>(Val: I2P->getOperand(i: 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(i: 0)->getType()->getPointerAddressSpace();
344 unsigned I2PAS = I2P->getType()->getPointerAddressSpace();
345 return CastInst::isNoopCast(Opcode: Instruction::CastOps(I2P->getOpcode()),
346 SrcTy: I2P->getOperand(i: 0)->getType(), DstTy: I2P->getType(),
347 DL) &&
348 CastInst::isNoopCast(Opcode: Instruction::CastOps(P2I->getOpcode()),
349 SrcTy: P2I->getOperand(i: 0)->getType(), DstTy: P2I->getType(),
350 DL) &&
351 (P2IOp0AS == I2PAS || TTI->isNoopAddrSpaceCast(FromAS: P2IOp0AS, ToAS: 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>(Val: &V))
363 return Arg->getType()->isPointerTy() &&
364 TTI->getAssumedAddrSpace(V: &V) != UninitializedAddressSpace;
365
366 const Operator *Op = dyn_cast<Operator>(Val: &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>(Val: &V);
382 return II && II->getIntrinsicID() == Intrinsic::ptrmask;
383 }
384 case Instruction::IntToPtr:
385 return isNoopPtrIntCastPair(I2P: Op, DL, TTI) ||
386 isSafeToCastIntToPtrAddrSpace(I2P: Op);
387 default:
388 // That value is an address expression if it has an assumed address space.
389 return TTI->getAssumedAddrSpace(V: &V) != UninitializedAddressSpace;
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>(Val: &V))
400 return {};
401
402 const Operator &Op = cast<Operator>(Val: V);
403 switch (Op.getOpcode()) {
404 case Instruction::PHI: {
405 auto IncomingValues = cast<PHINode>(Val: 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(i: 0)};
412 case Instruction::Select:
413 return {Op.getOperand(i: 1), Op.getOperand(i: 2)};
414 case Instruction::Call: {
415 const IntrinsicInst &II = cast<IntrinsicInst>(Val: Op);
416 assert(II.getIntrinsicID() == Intrinsic::ptrmask &&
417 "unexpected intrinsic call");
418 return {II.getArgOperand(i: 0)};
419 }
420 case Instruction::IntToPtr: {
421 if (isNoopPtrIntCastPair(I2P: &Op, DL, TTI)) {
422 auto *P2I = cast<Operator>(Val: Op.getOperand(i: 0));
423 return {P2I->getOperand(i: 0)};
424 }
425 assert(isSafeToCastIntToPtrAddrSpace(&Op));
426 return {getIntToPtrPointerOperand(I2P: &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(V: Mask, DL, AC, CtxI: 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(numBits: 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(Val: 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>(Val: I2P->getOperand(i: 0));
466 if (!LogicalOp || !Instruction::isBitwiseLogicOp(Opcode: 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(i: 0), *RHS = LogicalOp->getOperand(i: 1);
473 Value *OldPtr, *Mask;
474 if (match(V: LHS, P: m_PtrToInt(Op: m_Value(V&: OldPtr))))
475 Mask = RHS;
476 else if (match(V: RHS, P: m_PtrToInt(Op: m_Value(V&: OldPtr))))
477 Mask = LHS;
478 else
479 return nullptr;
480
481 Operator *AsCast = dyn_cast<AddrSpaceCastOperator>(Val: OldPtr);
482 if (!AsCast)
483 return nullptr;
484
485 unsigned SrcAS = I2P->getType()->getPointerAddressSpace();
486 unsigned DstAS = AsCast->getOperand(i: 0)->getType()->getPointerAddressSpace();
487 APInt PreservedPtrMask = TTI->getAddrSpaceCastPreservedPtrMask(SrcAS, DstAS);
488 if (PreservedPtrMask.isZero())
489 return nullptr;
490 APInt ChangedPtrBits =
491 computeMaxChangedPtrBits(Op: LogicalOp, Mask, DL: *DL, AC: &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(RHS: 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(KV: {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;
520 SmallVector<ConstantExpr *, 8> Worklist;
521 auto PushConstantExpr = [&](Value *V) {
522 if (auto *CE = dyn_cast<ConstantExpr>(Val: V))
523 if (VisitedCE.insert(V: CE).second)
524 Worklist.push_back(Elt: CE);
525 };
526
527 for (Instruction &I : instructions(F)) {
528 if (isa<IntToPtrInst>(Val: &I))
529 Collect(cast<Operator>(Val: &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>(Val: 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, id: IID, OverloadTys: {DestTy, SrcTy});
555 II->setArgOperand(i: 0, v: 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, id: IID, OverloadTys: {RetTy, NewPtrTy});
567 II->setArgOperand(i: 0, v: NewV);
568 II->setCalledFunction(NewDecl);
569 return true;
570 }
571 case Intrinsic::masked_store:
572 case Intrinsic::masked_scatter: {
573 Type *ValueTy = II->getOperand(i_nocapture: 0)->getType();
574 Type *NewPtrTy = NewV->getType();
575 Function *NewDecl = Intrinsic::getOrInsertDeclaration(
576 M, id: II->getIntrinsicID(), OverloadTys: {ValueTy, NewPtrTy});
577 II->setArgOperand(i: 1, v: NewV);
578 II->setCalledFunction(NewDecl);
579 return true;
580 }
581 case Intrinsic::prefetch:
582 case Intrinsic::is_constant: {
583 Function *NewDecl = Intrinsic::getOrInsertDeclaration(
584 M, id: II->getIntrinsicID(), OverloadTys: {NewV->getType()});
585 II->setArgOperand(i: 0, v: NewV);
586 II->setCalledFunction(NewDecl);
587 return true;
588 }
589 case Intrinsic::fake_use: {
590 II->replaceUsesOfWith(From: OldV, To: 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();
597 Function *NewDecl = Intrinsic::getOrInsertDeclaration(
598 M, id: II->getIntrinsicID(), OverloadTys: {NewV->getType()});
599 II->setArgOperand(i: 0, v: 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(V: 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(V: II->getArgOperand(i: 0),
624 PostorderStack, Visited);
625 break;
626 case Intrinsic::is_constant: {
627 Value *Ptr = II->getArgOperand(i: 0);
628 if (Ptr->getType()->isPtrOrPtrVectorTy()) {
629 appendsFlatAddressExpressionToPostorderStack(V: 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(V: II->getArgOperand(i: 0),
639 PostorderStack, Visited);
640 break;
641 case Intrinsic::masked_store:
642 case Intrinsic::masked_scatter:
643 appendsFlatAddressExpressionToPostorderStack(V: II->getArgOperand(i: 1),
644 PostorderStack, Visited);
645 break;
646 case Intrinsic::fake_use: {
647 for (Value *Op : II->operands()) {
648 if (Op->getType()->isPtrOrPtrVectorTy()) {
649 appendsFlatAddressExpressionToPostorderStack(V: Op, PostorderStack,
650 Visited);
651 }
652 }
653
654 break;
655 }
656 case Intrinsic::lifetime_start:
657 case Intrinsic::lifetime_end: {
658 appendsFlatAddressExpressionToPostorderStack(V: II->getArgOperand(i: 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(V: II->getArgOperand(i: 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>(Val: V)) {
685 // TODO: Look in non-address parts, like icmp operands.
686 if (isAddressExpression(V: *CE, DL: *DL, TTI) && Visited.insert(V: CE).second)
687 PostorderStack.emplace_back(Args&: CE, Args: false);
688
689 return;
690 }
691
692 if (V->getType()->getPointerAddressSpace() == FlatAddrSpace &&
693 isAddressExpression(V: *V, DL: *DL, TTI)) {
694 if (Visited.insert(V).second) {
695 PostorderStack.emplace_back(Args&: V, Args: false);
696
697 if (auto *Op = dyn_cast<Operator>(Val: V))
698 for (auto &O : Op->operands())
699 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Val&: O))
700 if (isAddressExpression(V: *CE, DL: *DL, TTI) && Visited.insert(V: CE).second)
701 PostorderStack.emplace_back(Args&: CE, Args: 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(V: 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;
723 SmallVector<ConstantExpr *, 8> CEWorklist;
724 auto PushConstantExpr = [&](Value *V) {
725 if (auto *CE = dyn_cast<ConstantExpr>(Val: V); CE && VisitedCE.insert(V: CE).second)
726 CEWorklist.push_back(Elt: 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>(Val: &I)) {
734 PushPtrOperand(GEP->getPointerOperand());
735 } else if (auto *LI = dyn_cast<LoadInst>(Val: &I))
736 PushPtrOperand(LI->getPointerOperand());
737 else if (auto *SI = dyn_cast<StoreInst>(Val: &I))
738 PushPtrOperand(SI->getPointerOperand());
739 else if (auto *RMW = dyn_cast<AtomicRMWInst>(Val: &I))
740 PushPtrOperand(RMW->getPointerOperand());
741 else if (auto *CmpX = dyn_cast<AtomicCmpXchgInst>(Val: &I))
742 PushPtrOperand(CmpX->getPointerOperand());
743 else if (auto *MI = dyn_cast<MemIntrinsic>(Val: &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>(Val: MI))
749 PushPtrOperand(MTI->getRawSource());
750 } else if (auto *II = dyn_cast<IntrinsicInst>(Val: &I))
751 collectRewritableIntrinsicOperands(II, PostorderStack, Visited);
752 else if (ICmpInst *Cmp = dyn_cast<ICmpInst>(Val: &I)) {
753 if (Cmp->getOperand(i_nocapture: 0)->getType()->isPtrOrPtrVectorTy()) {
754 PushPtrOperand(Cmp->getOperand(i_nocapture: 0));
755 PushPtrOperand(Cmp->getOperand(i_nocapture: 1));
756 }
757 } else if (auto *ASC = dyn_cast<AddrSpaceCastInst>(Val: &I)) {
758 PushPtrOperand(ASC->getPointerOperand());
759 } else if (auto *I2P = dyn_cast<IntToPtrInst>(Val: &I)) {
760 if (isNoopPtrIntCastPair(I2P: cast<Operator>(Val: I2P), DL: *DL, TTI))
761 PushPtrOperand(cast<Operator>(Val: I2P->getOperand(i_nocapture: 0))->getOperand(i: 0));
762 else if (isSafeToCastIntToPtrAddrSpace(I2P: cast<Operator>(Val: I2P)))
763 PushPtrOperand(getIntToPtrPointerOperand(I2P: cast<Operator>(Val: I2P)));
764 } else if (auto *RI = dyn_cast<ReturnInst>(Val: &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>(Val: 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(x: 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.
800 if (TTI->getAssumedAddrSpace(V: TopVal) == UninitializedAddressSpace) {
801 for (Value *PtrOperand : getPointerOperands(V: *TopVal, DL: *DL, TTI)) {
802 appendsFlatAddressExpressionToPostorderStack(V: 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.
812static Value *phiNodeOperandWithNewAddressSpace(AddrSpaceCastInst *NewI,
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>(Val: 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>(Val: 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(InsertPos: 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.
848static Value *operandWithNewAddressSpaceOrCreatePoison(
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(Ty: Operand->getType(), NewAddrSpace);
856
857 if (Constant *C = dyn_cast<Constant>(Val: Operand))
858 return ConstantExpr::getAddrSpaceCast(C, Ty: NewPtrTy);
859
860 Instruction *Inst = cast<Instruction>(Val: OperandUse.getUser());
861 if (Value *NewOperand = ValueWithNewAddrSpace.lookup(Val: Operand)) {
862 Operand = NewOperand;
863 } else if (!PredicatedAS.contains(Val: std::make_pair(x&: Inst, y&: Operand))) {
864 assert(PoisonUsesToFix && "missing inferred operand replacement");
865 PoisonUsesToFix->push_back(Elt: &OperandUse);
866 return PoisonValue::get(T: 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, Operand: 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(Val: Inst))
882 InsertPt = cast<Instruction>(Val: NewUser);
883 NewI->insertBefore(InsertPos: 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(i: 0);
896 unsigned OldAddrSpace = PtrOpUse->getType()->getPointerAddressSpace();
897 Value *MaskOp = I->getArgOperand(i: 1);
898 Type *MaskTy = MaskOp->getType();
899
900 KnownBits OldPtrBits{DL->getPointerSizeInBits(AS: OldAddrSpace)};
901 KnownBits NewPtrBits{DL->getPointerSizeInBits(AS: NewAddrSpace)};
902 if (!TTI->isNoopAddrSpaceCast(FromAS: OldAddrSpace, ToAS: NewAddrSpace)) {
903 std::tie(args&: OldPtrBits, args&: NewPtrBits) =
904 TTI->computeKnownBitsAddrSpaceCast(ToAS: NewAddrSpace, PtrOp: *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(V: MaskOp, DL: *DL, /*AssumptionCache=*/AC: nullptr, CtxI: 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(LHS: OldPtrBits, RHS: 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(Ty: 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(NewBitWidth: NewPtrBits.getBitWidth());
939 MaskOp = B.CreateTrunc(V: MaskOp, DestTy: MaskTy);
940 }
941 Value *NewPtr = operandWithNewAddressSpaceOrCreatePoison(
942 OperandUse: PtrOpUse, NewAddrSpace, ValueWithNewAddrSpace, PredicatedAS,
943 PoisonUsesToFix);
944 return B.CreateIntrinsic(ID: Intrinsic::ptrmask, OverloadTypes: {NewPtr->getType(), MaskTy},
945 Args: {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(Ty: I->getType(), NewAddrSpace);
963
964 if (I->getOpcode() == Instruction::AddrSpaceCast) {
965 Value *Src = I->getOperand(i: 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>(Val: 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 I: II, NewAddrSpace, ValueWithNewAddrSpace, PredicatedAS, PoisonUsesToFix);
979 }
980
981 unsigned AS = TTI->getAssumedAddrSpace(V: I);
982 if (AS != UninitializedAddressSpace) {
983 // For the assumed address space, insert an `addrspacecast` to make that
984 // explicit.
985 Type *NewPtrTy = getPtrOrVecOfPtrsWithNewAS(Ty: I->getType(), NewAddrSpace: AS);
986 auto *NewI = new AddrSpaceCastInst(I, NewPtrTy);
987 NewI->insertAfter(InsertPos: 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(Elt: nullptr);
997 else
998 NewPointerOperands.push_back(Elt: operandWithNewAddressSpaceOrCreatePoison(
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>(Val: I);
1009 PHINode *NewPHI = PHINode::Create(Ty: NewPtrType, NumReservedValues: PHI->getNumIncomingValues());
1010 for (unsigned Index = 0; Index < PHI->getNumIncomingValues(); ++Index) {
1011 unsigned OperandNo = PHINode::getOperandNumForIncomingValue(i: Index);
1012 NewPHI->addIncoming(V: NewPointerOperands[OperandNo],
1013 BB: PHI->getIncomingBlock(i: Index));
1014 }
1015 return NewPHI;
1016 }
1017 case Instruction::GetElementPtr: {
1018 GetElementPtrInst *GEP = cast<GetElementPtrInst>(Val: I);
1019 GetElementPtrInst *NewGEP = GetElementPtrInst::Create(
1020 PointeeType: GEP->getSourceElementType(), Ptr: NewPointerOperands[0],
1021 IdxList: 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(C: I->getOperand(i: 0), S1: NewPointerOperands[1],
1028 S2: NewPointerOperands[2], NameStr: "", InsertBefore: nullptr, MDFrom: I);
1029 case Instruction::IntToPtr: {
1030 if (isNoopPtrIntCastPair(I2P: cast<Operator>(Val: I), DL: *DL, TTI)) {
1031 Value *Src = cast<Operator>(Val: I->getOperand(i: 0))->getOperand(i: 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(InsertPos: 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(Ty: 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(i_nocapture: 0);
1070
1071 case Instruction::BitCast:
1072 if (Value *NewOperand = ValueWithNewAddrSpace.lookup(Val: CE->getOperand(i_nocapture: 0)))
1073 return ConstantExpr::getBitCast(C: cast<Constant>(Val: NewOperand), Ty: TargetType);
1074 return ConstantExpr::getAddrSpaceCast(C: CE, Ty: TargetType);
1075
1076 case Instruction::IntToPtr:
1077 if (isNoopPtrIntCastPair(I2P: cast<Operator>(Val: CE), DL: *DL, TTI)) {
1078 Constant *Src = cast<ConstantExpr>(Val: CE->getOperand(i_nocapture: 0))->getOperand(i_nocapture: 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(C: Src, Ty: TargetType);
1085 }
1086 assert(isSafeToCastIntToPtrAddrSpace(cast<Operator>(CE)));
1087 return ConstantExpr::getAddrSpaceCast(C: CE, Ty: 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(i_nocapture: 0);
1095 Value *NewBase = ValueWithNewAddrSpace.lookup(Val: Base);
1096 if (!NewBase)
1097 NewBase = cloneConstantExprWithNewAddressSpace(
1098 CE: cast<ConstantExpr>(Val: 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(Elt: cast<Constant>(Val: NewBase));
1104 for (unsigned Index = 1; Index < CE->getNumOperands(); ++Index)
1105 NewOperands.push_back(Elt: CE->getOperand(i_nocapture: Index));
1106 // Needs to specify the source type while constructing a getelementptr
1107 // constant expression.
1108 return CE->getWithOperands(Ops: NewOperands, Ty: TargetType, /*OnlyIfReduced=*/false,
1109 SrcTy: cast<GEPOperator>(Val: 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>(Val: 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(C&: Arg->getContext(), AddressSpace: NewAddrSpace);
1138 auto *NewI = new AddrSpaceCastInst(Arg, NewPtrTy);
1139 NewI->insertBefore(InsertPos: Insert);
1140 return NewI;
1141 }
1142
1143 if (Instruction *I = dyn_cast<Instruction>(Val: V)) {
1144 Value *NewV = cloneInstructionWithNewAddressSpace(
1145 I, NewAddrSpace, ValueWithNewAddrSpace, PredicatedAS, PoisonUsesToFix);
1146 if (Instruction *NewI = dyn_cast_or_null<Instruction>(Val: NewV)) {
1147 if (NewI->getParent() == nullptr) {
1148 NewI->insertBefore(InsertPos: I->getIterator());
1149 NewI->takeName(V: I);
1150 NewI->setDebugLoc(I->getDebugLoc());
1151 }
1152 }
1153 return NewV;
1154 }
1155
1156 return cloneConstantExprWithNewAddressSpace(
1157 CE: cast<ConstantExpr>(Val: 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) {
1187 FlatAddrSpace = TTI->getFlatAddressSpace();
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&: *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(key: User))
1214 continue;
1215
1216 ValueToAddrSpaceMapTy::const_iterator Pos = InferredAddrSpace.find(Val: 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(X: 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(Val: I2P);
1240 if (Pos == InferredAddrSpace.end() || Pos->second == FlatAddrSpace)
1241 continue;
1242 Worklist.insert(X: 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: *V, InferredAddrSpace, PredicatedAS))
1255 continue;
1256
1257 enqueueUsers(V&: *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(Val: V);
1281 if (I->second == UninitializedAddressSpace) {
1282 I->second = FlatAddrSpace;
1283 Lowered.push_back(Elt: V);
1284 }
1285 }
1286
1287 for (Value *V : Lowered)
1288 enqueueUsers(V&: *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>(Val: UserCtx);
1297 if (!UserCtxI)
1298 return UninitializedAddressSpace;
1299
1300 const Value *StrippedPtr = Ptr.stripInBoundsOffsets();
1301 for (auto &AssumeVH : AC.assumptionsFor(V: StrippedPtr)) {
1302 if (!AssumeVH)
1303 continue;
1304 CallInst *CI = cast<CallInst>(Val&: AssumeVH);
1305 if (!isValidAssumeForContext(I: CI, CtxI: UserCtxI, DT))
1306 continue;
1307
1308 const Value *Ptr;
1309 unsigned AS;
1310 std::tie(args&: Ptr, args&: AS) = TTI->getPredicatedAddrSpace(V: CI->getArgOperand(i: 0));
1311 if (Ptr)
1312 return AS;
1313 }
1314
1315 return UninitializedAddressSpace;
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.
1330 assert(isa<Operator>(V) || isa<Argument>(V));
1331
1332 unsigned AS = TTI->getAssumedAddrSpace(V: &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: *DL, TTI);
1340 for (Value *PtrOperand : PtrOps) {
1341 auto I = InferredAddrSpace.find(Val: PtrOperand);
1342 unsigned OperandAS;
1343 if (I == InferredAddrSpace.end()) {
1344 OperandAS = PtrOperand->getType()->getPointerAddressSpace();
1345 if (auto *C = dyn_cast<Constant>(Val: PtrOperand);
1346 C && OperandAS == FlatAddrSpace) {
1347 // Defer joining the address space of constant pointer operands.
1348 ConstantPtrOps.push_back(Elt: C);
1349 continue;
1350 }
1351 if (OperandAS == FlatAddrSpace) {
1352 // Check AC for assumption dominating V.
1353 unsigned AS = getPredicatedAddrSpace(Ptr: *PtrOperand, UserCtx: &V);
1354 if (AS != UninitializedAddressSpace) {
1355 LLVM_DEBUG(dbgs()
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(x: &V, y&: 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(AS1: NewAS, AS2: OperandAS);
1368 if (NewAS == FlatAddrSpace)
1369 break;
1370 }
1371
1372 if (NewAS != FlatAddrSpace && NewAS != UninitializedAddressSpace) {
1373 if (any_of(Range&: ConstantPtrOps, P: [=](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(Val: &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(i: OpIdx);
1402 if (U.get() == OldVal) {
1403 U.set(NewVal);
1404 return true;
1405 }
1406
1407 return false;
1408}
1409
1410template <typename InstrType>
1411static bool replaceSimplePointerUse(const TargetTransformInfo &TTI,
1412 InstrType *MemInstr, Value *OldV,
1413 Value *NewV) {
1414 unsigned AddrSpace = NewV->getType()->getPointerAddressSpace();
1415 if (!MemInstr->isVolatile() || TTI.hasVolatileVariant(I: 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.
1430static bool replaceIfSimplePointerUse(const TargetTransformInfo &TTI,
1431 User *Inst, Value *OldV, Value *NewV) {
1432 if (auto *LI = dyn_cast<LoadInst>(Val: Inst))
1433 return replaceSimplePointerUse(TTI, MemInstr: LI, OldV, NewV);
1434
1435 if (auto *SI = dyn_cast<StoreInst>(Val: Inst))
1436 return replaceSimplePointerUse(TTI, MemInstr: SI, OldV, NewV);
1437
1438 if (auto *RMW = dyn_cast<AtomicRMWInst>(Val: Inst))
1439 return replaceSimplePointerUse(TTI, MemInstr: RMW, OldV, NewV);
1440
1441 if (auto *CmpX = dyn_cast<AtomicCmpXchgInst>(Val: Inst))
1442 return replaceSimplePointerUse(TTI, MemInstr: 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.
1450static bool handleMemIntrinsicPtrUse(MemIntrinsic *MI, Value *OldV,
1451 Value *NewV) {
1452 IRBuilder<> B(MI);
1453 if (auto *MSI = dyn_cast<MemSetInst>(Val: MI)) {
1454 B.CreateMemSet(Ptr: NewV, Val: MSI->getValue(), Size: MSI->getLength(), Align: MSI->getDestAlign(),
1455 isVolatile: false, // isVolatile
1456 AAInfo: MI->getAAMetadata());
1457 } else if (auto *MTI = dyn_cast<MemTransferInst>(Val: 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>(Val: MTI)) {
1469 if (MCI->isForceInlined())
1470 B.CreateMemCpyInline(Dst: Dest, DstAlign: MTI->getDestAlign(), Src,
1471 SrcAlign: MTI->getSourceAlign(), Size: MTI->getLength(),
1472 isVolatile: false, // isVolatile
1473 AAInfo: MI->getAAMetadata());
1474 else
1475 B.CreateMemCpy(Dst: Dest, DstAlign: MTI->getDestAlign(), Src, SrcAlign: MTI->getSourceAlign(),
1476 Size: MTI->getLength(),
1477 isVolatile: false, // isVolatile
1478 AAInfo: MI->getAAMetadata());
1479 } else {
1480 assert(isa<MemMoveInst>(MTI));
1481 B.CreateMemMove(Dst: Dest, DstAlign: MTI->getDestAlign(), Src, SrcAlign: MTI->getSourceAlign(),
1482 Size: MTI->getLength(),
1483 isVolatile: false, // isVolatile
1484 AAInfo: 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 {
1497 assert(NewAS != UninitializedAddressSpace);
1498
1499 unsigned SrcAS = C->getType()->getPointerAddressSpace();
1500 if (SrcAS == NewAS || isa<UndefValue>(Val: 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
1507 if (isa<ConstantPointerNull>(Val: C) || isa<ConstantAggregateZero>(Val: C))
1508 return true;
1509
1510 if (auto *Op = dyn_cast<Operator>(Val: 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(C: cast<Constant>(Val: Op->getOperand(i: 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
1525static Value::use_iterator skipToNextUser(Value::use_iterator I,
1526 Value::use_iterator End) {
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>(Val: CurUser);
1547 if (!CurUserI || CurUserI->getFunction() != F)
1548 return;
1549
1550 if (replaceIfSimplePointerUse(TTI: *TTI, Inst: CurUser, OldV: V, NewV))
1551 return;
1552
1553 // Handle more complex cases like intrinsic that need to be remangled.
1554 if (auto *MI = dyn_cast<MemIntrinsic>(Val: CurUser)) {
1555 if (!MI->isVolatile() && handleMemIntrinsicPtrUse(MI, OldV: V, NewV))
1556 return;
1557 }
1558
1559 if (auto *II = dyn_cast<IntrinsicInst>(Val: CurUser)) {
1560 if (rewriteIntrinsicOperands(II, OldV: V, NewV))
1561 return;
1562 }
1563
1564 if (ICmpInst *Cmp = dyn_cast<ICmpInst>(Val: 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(i_nocapture: OtherIdx);
1575
1576 if (Value *OtherNewV = ValueWithNewAddrSpace.lookup(Val: OtherSrc)) {
1577 if (OtherNewV->getType()->getPointerAddressSpace() == NewAS) {
1578 Cmp->setOperand(i_nocapture: OtherIdx, Val_nocapture: OtherNewV);
1579 Cmp->setOperand(i_nocapture: SrcIdx, Val_nocapture: NewV);
1580 return;
1581 }
1582 }
1583
1584 // Even if the type mismatches, we can cast the constant.
1585 if (auto *KOtherSrc = dyn_cast<Constant>(Val: OtherSrc)) {
1586 if (isSafeToCastConstAddrSpace(C: KOtherSrc, NewAS)) {
1587 Cmp->setOperand(i_nocapture: SrcIdx, Val_nocapture: NewV);
1588 Cmp->setOperand(i_nocapture: OtherIdx, Val_nocapture: ConstantExpr::getAddrSpaceCast(
1589 C: KOtherSrc, Ty: NewV->getType()));
1590 return;
1591 }
1592 }
1593 }
1594
1595 if (AddrSpaceCastInst *ASC = dyn_cast<AddrSpaceCastInst>(Val: CurUserI)) {
1596 unsigned NewAS = NewV->getType()->getPointerAddressSpace();
1597 if (ASC->getDestAddressSpace() == NewAS) {
1598 ASC->replaceAllUsesWith(V: NewV);
1599 DeadInstructions.push_back(Elt: ASC);
1600 return;
1601 }
1602 }
1603
1604 // Otherwise, replaces the use with flat(NewV).
1605 if (isa<Instruction>(Val: V) || isa<Instruction>(Val: NewV)) {
1606 // Don't create a copy of the original addrspacecast.
1607 if (U == V && isa<AddrSpaceCastInst>(Val: V))
1608 return;
1609
1610 // Insert the addrspacecast after NewV.
1611 BasicBlock::iterator InsertPos;
1612 if (Instruction *NewVInst = dyn_cast<Instruction>(Val: NewV))
1613 InsertPos = std::next(x: NewVInst->getIterator());
1614 else
1615 InsertPos = std::next(x: cast<Instruction>(Val: V)->getIterator());
1616
1617 while (isa<PHINode>(Val: InsertPos))
1618 ++InsertPos;
1619 // This instruction may contain multiple uses of V, update them all.
1620 CurUser->replaceUsesOfWith(
1621 From: V, To: new AddrSpaceCastInst(NewV, V->getType(), "", InsertPos));
1622 } else {
1623 CurUserI->replaceUsesOfWith(
1624 From: V, To: ConstantExpr::getAddrSpaceCast(C: cast<Constant>(Val: NewV), Ty: 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(Val: 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: &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>(Val: ValueWithNewAddrSpace.lookup(Val: 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(i: OperandNo)->getType()->getPointerAddressSpace();
1669 Value *NewOp = operandWithNewAddressSpaceOrCreatePoison(
1670 OperandUse: *PoisonUse, NewAddrSpace: NewAS, ValueWithNewAddrSpace, PredicatedAS, PoisonUsesToFix: nullptr);
1671 NewV->setOperand(i: OperandNo, Val: 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(Val: 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>(Val: V)) {
1688 Constant *Replace =
1689 ConstantExpr::getAddrSpaceCast(C: cast<Constant>(Val: NewV), Ty: C->getType());
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(Range: C->users())) {
1695 if (auto *I = dyn_cast<Instruction>(Val: U)) {
1696 if (I->getFunction() == F)
1697 I->replaceUsesOfWith(From: C, To: Replace);
1698 } else {
1699 WorkList.append(in_start: U->user_begin(), in_end: 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,
1709 RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);
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>(Val: U)) {
1714 if (I->getFunction() == F)
1715 VMapper.remapInstruction(I&: *I);
1716 continue;
1717 }
1718 for (User *U2 : U->users())
1719 if (Visited.insert(V: U2).second)
1720 WorkList.push_back(Elt: 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, End: E);
1734
1735 performPointerReplacement(V, NewV, U, ValueWithNewAddrSpace,
1736 DeadInstructions);
1737 }
1738
1739 if (V->use_empty()) {
1740 if (Instruction *I = dyn_cast<Instruction>(Val: V))
1741 DeadInstructions.push_back(Elt: 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>(Range&: DeadInstructions);
1750 RecursivelyDeleteTriviallyDeadInstructions(DeadInsts&: 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(CurFn&: F);
1766}
1767
1768FunctionPass *llvm::createInferAddressSpacesPass(unsigned AddressSpace) {
1769 return new InferAddressSpaces(AddressSpace);
1770}
1771
1772InferAddressSpacesPass::InferAddressSpacesPass(
1773 bool AssumeDefaultIsFlatAddressSpace)
1774 : FlatAddrSpace(UninitializedAddressSpace),
1775 AssumeDefaultIsFlatAddressSpace(AssumeDefaultIsFlatAddressSpace) {}
1776InferAddressSpacesPass::InferAddressSpacesPass(
1777 unsigned AddressSpace, bool AssumeDefaultIsFlatAddressSpace)
1778 : FlatAddrSpace(AddressSpace),
1779 AssumeDefaultIsFlatAddressSpace(AssumeDefaultIsFlatAddressSpace) {}
1780
1781PreservedAnalyses InferAddressSpacesPass::run(Function &F,
1782 FunctionAnalysisManager &AM) {
1783 bool Changed =
1784 InferAddressSpacesImpl(AM.getResult<AssumptionAnalysis>(IR&: F),
1785 AM.getCachedResult<DominatorTreeAnalysis>(IR&: F),
1786 &AM.getResult<TargetIRAnalysis>(IR&: F), FlatAddrSpace,
1787 AssumeDefaultIsFlatAddressSpace)
1788 .run(CurFn&: F);
1789 if (Changed) {
1790 PreservedAnalyses PA;
1791 PA.preserveSet<CFGAnalyses>();
1792 return PA;
1793 }
1794 return PreservedAnalyses::all();
1795}
1796
1797void InferAddressSpacesPass::printPipeline(
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}
1804