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