1//===- SPIRVLegalizeZeroSizeArrays.cpp - Legalize zero-size arrays -------===//
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// SPIR-V does not support zero-size arrays unless it is within a shader. This
10// pass legalizes zero-size arrays ([0 x T]) in unsupported cases.
11//
12//===----------------------------------------------------------------------===//
13
14#include "SPIRV.h"
15#include "SPIRVTargetMachine.h"
16#include "SPIRVUtils.h"
17#include "llvm/ADT/DenseMap.h"
18#include "llvm/ADT/SmallVector.h"
19#include "llvm/IR/IRBuilder.h"
20#include "llvm/IR/InstIterator.h"
21#include "llvm/IR/InstVisitor.h"
22#include "llvm/Pass.h"
23
24#define DEBUG_TYPE "spirv-legalize-zero-size-arrays"
25
26using namespace llvm;
27
28namespace {
29
30bool hasZeroSizeArray(const Type *Ty) {
31 if (const ArrayType *ArrTy = dyn_cast<ArrayType>(Val: Ty)) {
32 if (ArrTy->getNumElements() == 0)
33 return true;
34 return hasZeroSizeArray(Ty: ArrTy->getElementType());
35 }
36
37 if (const StructType *StructTy = dyn_cast<StructType>(Val: Ty)) {
38 for (Type *ElemTy : StructTy->elements()) {
39 if (hasZeroSizeArray(Ty: ElemTy))
40 return true;
41 }
42 }
43
44 return false;
45}
46
47bool shouldLegalizeInstType(const Type *Ty) {
48 // This recursive function will always terminate because we only look inside
49 // array types, and those can't be recursive.
50 if (const ArrayType *ArrTy = dyn_cast_if_present<ArrayType>(Val: Ty)) {
51 return ArrTy->getNumElements() == 0 ||
52 shouldLegalizeInstType(Ty: ArrTy->getElementType());
53 }
54 return false;
55}
56
57class SPIRVLegalizeZeroSizeArraysImpl
58 : public InstVisitor<SPIRVLegalizeZeroSizeArraysImpl> {
59 friend class InstVisitor<SPIRVLegalizeZeroSizeArraysImpl>;
60
61public:
62 SPIRVLegalizeZeroSizeArraysImpl(const SPIRVTargetMachine &TM)
63 : InstVisitor(), TM(TM) {}
64 bool runOnModule(Module &M);
65
66 // TODO: Handle GEP, PHI.
67 void visitAllocaInst(AllocaInst &AI);
68 void visitLoadInst(LoadInst &LI);
69 void visitStoreInst(StoreInst &SI);
70 void visitSelectInst(SelectInst &Sel);
71 void visitExtractValueInst(ExtractValueInst &EVI);
72 void visitInsertValueInst(InsertValueInst &IVI);
73
74private:
75 Type *legalizeType(Type *Ty);
76 Constant *legalizeConstant(Constant *C);
77
78 const SPIRVTargetMachine &TM;
79 DenseMap<Type *, Type *> TypeMap;
80 DenseMap<GlobalVariable *, GlobalVariable *> GlobalMap;
81 SmallVector<Instruction *, 16> ToErase;
82 bool Modified = false;
83};
84
85class SPIRVLegalizeZeroSizeArraysLegacy : public ModulePass {
86public:
87 static char ID;
88 SPIRVLegalizeZeroSizeArraysLegacy(const SPIRVTargetMachine &TM)
89 : ModulePass(ID), TM(TM) {}
90 StringRef getPassName() const override {
91 return "SPIRV Legalize Zero-Size Arrays";
92 }
93 bool runOnModule(Module &M) override {
94 SPIRVLegalizeZeroSizeArraysImpl Impl(TM);
95 return Impl.runOnModule(M);
96 }
97
98private:
99 const SPIRVTargetMachine &TM;
100};
101
102// Legalize a type. There are only two cases we need to care about:
103// arrays and structs.
104//
105// For arrays, we just replace the entire array type with a ptr.
106//
107// For structs, we create a new type with any members containing
108// nested arrays legalized.
109
110Type *SPIRVLegalizeZeroSizeArraysImpl::legalizeType(Type *Ty) {
111 auto It = TypeMap.find(Val: Ty);
112 if (It != TypeMap.end())
113 return It->second;
114
115 Type *LegalizedTy = Ty;
116
117 if (shouldLegalizeInstType(Ty)) {
118 LegalizedTy = PointerType::get(
119 C&: Ty->getContext(),
120 AddressSpace: storageClassToAddressSpace(SC: SPIRV::StorageClass::Generic));
121
122 } else if (StructType *StructTy = dyn_cast<StructType>(Val: Ty)) {
123 SmallVector<Type *, 8> ElemTypes;
124 bool Changed = false;
125 for (Type *ElemTy : StructTy->elements()) {
126 Type *LegalizedElemTy = legalizeType(Ty: ElemTy);
127 ElemTypes.push_back(Elt: LegalizedElemTy);
128 Changed |= LegalizedElemTy != ElemTy;
129 }
130 if (Changed) {
131 LegalizedTy =
132 StructTy->hasName()
133 ? StructType::create(Context&: StructTy->getContext(), Elements: ElemTypes,
134 Name: (StructTy->getName() + ".legalized").str(),
135 isPacked: StructTy->isPacked())
136 : StructType::get(Context&: StructTy->getContext(), Elements: ElemTypes,
137 isPacked: StructTy->isPacked());
138 }
139 }
140
141 TypeMap[Ty] = LegalizedTy;
142 return LegalizedTy;
143}
144
145Constant *SPIRVLegalizeZeroSizeArraysImpl::legalizeConstant(Constant *C) {
146 if (!C || !hasZeroSizeArray(Ty: C->getType()))
147 return C;
148
149 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Val: C)) {
150 if (GlobalVariable *NewGV = GlobalMap.lookup(Val: GV))
151 return NewGV;
152 return C;
153 }
154
155 Type *NewTy = legalizeType(Ty: C->getType());
156 if (isa<UndefValue>(Val: C))
157 return PoisonValue::get(T: NewTy);
158 if (isa<ConstantAggregateZero>(Val: C))
159 return Constant::getNullValue(Ty: NewTy);
160 if (ConstantArray *CA = dyn_cast<ConstantArray>(Val: C)) {
161 SmallVector<Constant *, 8> Elems;
162 for (Use &U : CA->operands())
163 Elems.push_back(Elt: legalizeConstant(C: cast<Constant>(Val&: U)));
164 return ConstantArray::get(T: cast<ArrayType>(Val: NewTy), V: Elems);
165 }
166
167 if (ConstantStruct *CS = dyn_cast<ConstantStruct>(Val: C)) {
168 SmallVector<Constant *, 8> Fields;
169 for (Use &U : CS->operands())
170 Fields.push_back(Elt: legalizeConstant(C: cast<Constant>(Val&: U)));
171 return ConstantStruct::get(T: cast<StructType>(Val: NewTy), V: Fields);
172 }
173
174 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Val: C)) {
175 // Don't legalize GEP constant expressions, the backend deals with them
176 // fine.
177 if (CE->getOpcode() == Instruction::GetElementPtr)
178 return CE;
179 SmallVector<Constant *, 4> Ops;
180 bool Changed = false;
181 for (Use &U : CE->operands()) {
182 Constant *LegalizedOp = legalizeConstant(C: cast<Constant>(Val&: U));
183 Ops.push_back(Elt: LegalizedOp);
184 Changed |= LegalizedOp != cast<Constant>(Val: U.get());
185 }
186 if (Changed)
187 return CE->getWithOperands(Ops);
188 }
189
190 return C;
191}
192
193void SPIRVLegalizeZeroSizeArraysImpl::visitAllocaInst(AllocaInst &AI) {
194 // Check if allocation size is known-zero
195 const DataLayout &DL = AI.getModule()->getDataLayout();
196 std::optional<TypeSize> Size = AI.getAllocationSize(DL);
197 if (!Size || !Size->isZero())
198 return;
199
200 // Allocate a byte instead of an empty alloca.
201 IRBuilder<> Builder(&AI);
202 AllocaInst *NewAI = Builder.CreateAlloca(Ty: Builder.getInt8Ty());
203 NewAI->takeName(V: &AI);
204 NewAI->setAlignment(AI.getAlign());
205 NewAI->setDebugLoc(AI.getDebugLoc());
206 AI.replaceAllUsesWith(V: NewAI);
207 ToErase.push_back(Elt: &AI);
208 Modified = true;
209}
210
211void SPIRVLegalizeZeroSizeArraysImpl::visitLoadInst(LoadInst &LI) {
212 if (!hasZeroSizeArray(Ty: LI.getType()))
213 return;
214
215 // TODO: Handle structs containing zero-size arrays.
216 ArrayType *ArrTy = dyn_cast<ArrayType>(Val: LI.getType());
217 if (shouldLegalizeInstType(Ty: ArrTy)) {
218 LI.replaceAllUsesWith(V: PoisonValue::get(T: LI.getType()));
219 ToErase.push_back(Elt: &LI);
220 Modified = true;
221 }
222}
223
224void SPIRVLegalizeZeroSizeArraysImpl::visitStoreInst(StoreInst &SI) {
225 Type *StoreTy = SI.getValueOperand()->getType();
226
227 // TODO: Handle structs containing zero-size arrays.
228 ArrayType *ArrTy = dyn_cast<ArrayType>(Val: StoreTy);
229 if (shouldLegalizeInstType(Ty: ArrTy)) {
230 ToErase.push_back(Elt: &SI);
231 Modified = true;
232 }
233}
234
235void SPIRVLegalizeZeroSizeArraysImpl::visitSelectInst(SelectInst &Sel) {
236 if (!hasZeroSizeArray(Ty: Sel.getType()))
237 return;
238
239 // TODO: Handle structs containing zero-size arrays.
240 ArrayType *ArrTy = dyn_cast<ArrayType>(Val: Sel.getType());
241 if (shouldLegalizeInstType(Ty: ArrTy)) {
242 Sel.replaceAllUsesWith(V: PoisonValue::get(T: Sel.getType()));
243 ToErase.push_back(Elt: &Sel);
244 Modified = true;
245 }
246}
247
248void SPIRVLegalizeZeroSizeArraysImpl::visitExtractValueInst(
249 ExtractValueInst &EVI) {
250 if (!hasZeroSizeArray(Ty: EVI.getAggregateOperand()->getType()))
251 return;
252
253 // TODO: Handle structs containing zero-size arrays.
254 ArrayType *ArrTy = dyn_cast<ArrayType>(Val: EVI.getType());
255 if (shouldLegalizeInstType(Ty: ArrTy)) {
256 EVI.replaceAllUsesWith(V: PoisonValue::get(T: EVI.getType()));
257 ToErase.push_back(Elt: &EVI);
258 Modified = true;
259 }
260}
261
262void SPIRVLegalizeZeroSizeArraysImpl::visitInsertValueInst(
263 InsertValueInst &IVI) {
264 if (!hasZeroSizeArray(Ty: IVI.getAggregateOperand()->getType()))
265 return;
266
267 // TODO: Handle structs containing zero-size arrays.
268 ArrayType *ArrTy =
269 dyn_cast<ArrayType>(Val: IVI.getInsertedValueOperand()->getType());
270 if (shouldLegalizeInstType(Ty: ArrTy)) {
271 IVI.replaceAllUsesWith(V: IVI.getAggregateOperand());
272 ToErase.push_back(Elt: &IVI);
273 Modified = true;
274 }
275}
276
277bool SPIRVLegalizeZeroSizeArraysImpl::runOnModule(Module &M) {
278 TypeMap.clear();
279 GlobalMap.clear();
280 ToErase.clear();
281 Modified = false;
282
283 // Runtime arrays are allowed for shaders, so we don't need to do anything.
284 if (TM.getSubtargetImpl()->isShader())
285 return false;
286 // 0-sized arrays are handled differently for AMDGCN flavoured SPIRV.
287 if (M.getTargetTriple().getVendor() == Triple::VendorType::AMD)
288 return false;
289
290 // First pass: create new globals (legalizing the initializer as needed) and
291 // track mapping (don't erase old ones yet).
292 SmallVector<GlobalVariable *, 8> OldGlobals;
293 for (GlobalVariable &GV : M.globals()) {
294 if (!hasZeroSizeArray(Ty: GV.getValueType()))
295 continue;
296
297 Type *NewTy = legalizeType(Ty: GV.getValueType());
298 Constant *LegalizedInitializer =
299 GV.hasInitializer() && !GV.hasAppendingLinkage()
300 ? legalizeConstant(C: GV.getInitializer())
301 : nullptr;
302
303 // The new global will have the same linkage type as the original,
304 // except in the case that it is an llvm intrinsic global such as
305 // llvm.global_ctors with appending linkage, in which case we need to change
306 // the linkage as appending linkage is only allowed for arrays.
307 GlobalValue::LinkageTypes NewLT =
308 GV.hasAppendingLinkage()
309 ? GlobalValue::LinkageTypes::ExternalWeakLinkage
310 : GV.getLinkage();
311
312 // Use an empty name for now, we will update it in the
313 // following step.
314 GlobalVariable *NewGV = new GlobalVariable(
315 M, NewTy, GV.isConstant(), NewLT, LegalizedInitializer,
316 /*Name=*/"", &GV, GV.getThreadLocalMode(), GV.getAddressSpace(),
317 GV.isExternallyInitialized());
318 NewGV->copyAttributesFrom(Src: &GV);
319 NewGV->copyMetadata(Src: &GV, Offset: 0);
320 NewGV->setComdat(GV.getComdat());
321 NewGV->setAlignment(GV.getAlign());
322 GlobalMap[&GV] = NewGV;
323 OldGlobals.push_back(Elt: &GV);
324 Modified = true;
325 }
326
327 // Second pass: replace uses, transfer names, and erase old globals.
328 for (GlobalVariable *GV : OldGlobals) {
329 GlobalVariable *NewGV = GlobalMap[GV];
330 GV->replaceAllUsesWith(V: ConstantExpr::getBitCast(C: NewGV, Ty: GV->getType()));
331 NewGV->takeName(V: GV);
332 GV->eraseFromParent();
333 }
334
335 for (Function &F : M)
336 for (Instruction &I : instructions(F))
337 visit(I);
338
339 for (Instruction *I : ToErase)
340 I->eraseFromParent();
341
342 return Modified;
343}
344
345} // namespace
346
347PreservedAnalyses
348SPIRVLegalizeZeroSizeArraysPass::run(Module &M, ModuleAnalysisManager &AM) {
349 SPIRVLegalizeZeroSizeArraysImpl Impl(TM);
350 if (Impl.runOnModule(M))
351 return PreservedAnalyses::none();
352 return PreservedAnalyses::all();
353}
354
355char SPIRVLegalizeZeroSizeArraysLegacy::ID = 0;
356
357INITIALIZE_PASS(SPIRVLegalizeZeroSizeArraysLegacy,
358 "spirv-legalize-zero-size-arrays",
359 "Legalize SPIR-V zero-size arrays", false, false)
360
361ModulePass *
362llvm::createSPIRVLegalizeZeroSizeArraysPass(const SPIRVTargetMachine &TM) {
363 return new SPIRVLegalizeZeroSizeArraysLegacy(TM);
364}
365