1//===- DXILFlattenArrays.cpp - Flattens DXIL 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/// \file This file contains a pass to flatten arrays for the DirectX Backend.
10///
11//===----------------------------------------------------------------------===//
12
13#include "DirectX.h"
14#include "llvm/ADT/PostOrderIterator.h"
15#include "llvm/ADT/STLExtras.h"
16#include "llvm/IR/BasicBlock.h"
17#include "llvm/IR/DerivedTypes.h"
18#include "llvm/IR/IRBuilder.h"
19#include "llvm/IR/InstVisitor.h"
20#include "llvm/IR/ReplaceConstant.h"
21#include "llvm/Support/Casting.h"
22#include "llvm/Support/MathExtras.h"
23#include "llvm/Transforms/Utils/Local.h"
24#include <cassert>
25#include <cstdint>
26#include <utility>
27
28#define DEBUG_TYPE "dxil-flatten-arrays"
29
30using namespace llvm;
31namespace {
32
33class DXILFlattenArraysLegacy : public ModulePass {
34
35public:
36 bool runOnModule(Module &M) override;
37 DXILFlattenArraysLegacy() : ModulePass(ID) {}
38
39 static char ID; // Pass identification.
40};
41
42struct GEPInfo {
43 ArrayType *RootFlattenedArrayType;
44 Value *RootPointerOperand;
45 SmallMapVector<Value *, APInt, 4> VariableOffsets;
46 APInt ConstantOffset;
47};
48
49class DXILFlattenArraysVisitor
50 : public InstVisitor<DXILFlattenArraysVisitor, bool> {
51public:
52 DXILFlattenArraysVisitor(
53 SmallDenseMap<GlobalVariable *, GlobalVariable *> &GlobalMap)
54 : GlobalMap(GlobalMap) {}
55 bool visit(Function &F);
56 // InstVisitor methods. They return true if the instruction was scalarized,
57 // false if nothing changed.
58 bool visitGetElementPtrInst(GetElementPtrInst &GEPI);
59 bool visitAllocaInst(AllocaInst &AI);
60 bool visitInstruction(Instruction &I) { return false; }
61 bool visitSelectInst(SelectInst &SI) { return false; }
62 bool visitICmpInst(ICmpInst &ICI) { return false; }
63 bool visitFCmpInst(FCmpInst &FCI) { return false; }
64 bool visitUnaryOperator(UnaryOperator &UO) { return false; }
65 bool visitBinaryOperator(BinaryOperator &BO) { return false; }
66 bool visitCastInst(CastInst &CI) { return false; }
67 bool visitBitCastInst(BitCastInst &BCI) { return false; }
68 bool visitInsertElementInst(InsertElementInst &IEI) { return false; }
69 bool visitExtractElementInst(ExtractElementInst &EEI) { return false; }
70 bool visitShuffleVectorInst(ShuffleVectorInst &SVI) { return false; }
71 bool visitPHINode(PHINode &PHI) { return false; }
72 bool visitLoadInst(LoadInst &LI);
73 bool visitStoreInst(StoreInst &SI);
74 bool visitCallInst(CallInst &ICI) { return false; }
75 bool visitFreezeInst(FreezeInst &FI) { return false; }
76 static bool isMultiDimensionalArray(Type *T);
77 static std::pair<unsigned, Type *> getElementCountAndType(Type *ArrayTy);
78
79private:
80 SmallVector<WeakTrackingVH> PotentiallyDeadInstrs;
81 SmallDenseMap<GEPOperator *, GEPInfo> GEPChainInfoMap;
82 SmallDenseMap<GlobalVariable *, GlobalVariable *> &GlobalMap;
83 bool finish();
84 ConstantInt *genConstFlattenIndices(ArrayRef<Value *> Indices,
85 ArrayRef<uint64_t> Dims,
86 IRBuilder<> &Builder);
87 Value *genInstructionFlattenIndices(ArrayRef<Value *> Indices,
88 ArrayRef<uint64_t> Dims,
89 IRBuilder<> &Builder);
90};
91} // namespace
92
93bool DXILFlattenArraysVisitor::finish() {
94 GEPChainInfoMap.clear();
95 RecursivelyDeleteTriviallyDeadInstructionsPermissive(DeadInsts&: PotentiallyDeadInstrs);
96 return true;
97}
98
99bool DXILFlattenArraysVisitor::isMultiDimensionalArray(Type *T) {
100 if (ArrayType *ArrType = dyn_cast<ArrayType>(Val: T))
101 return isa<ArrayType>(Val: ArrType->getElementType());
102 return false;
103}
104
105std::pair<unsigned, Type *>
106DXILFlattenArraysVisitor::getElementCountAndType(Type *ArrayTy) {
107 unsigned TotalElements = 1;
108 Type *CurrArrayTy = ArrayTy;
109 while (auto *InnerArrayTy = dyn_cast<ArrayType>(Val: CurrArrayTy)) {
110 TotalElements *= InnerArrayTy->getNumElements();
111 CurrArrayTy = InnerArrayTy->getElementType();
112 }
113 return std::make_pair(x&: TotalElements, y&: CurrArrayTy);
114}
115
116ConstantInt *DXILFlattenArraysVisitor::genConstFlattenIndices(
117 ArrayRef<Value *> Indices, ArrayRef<uint64_t> Dims, IRBuilder<> &Builder) {
118 assert(Indices.size() == Dims.size() &&
119 "Indicies and dimmensions should be the same");
120 unsigned FlatIndex = 0;
121 unsigned Multiplier = 1;
122
123 for (int I = Indices.size() - 1; I >= 0; --I) {
124 unsigned DimSize = Dims[I];
125 ConstantInt *CIndex = dyn_cast<ConstantInt>(Val: Indices[I]);
126 assert(CIndex && "This function expects all indicies to be ConstantInt");
127 FlatIndex += CIndex->getZExtValue() * Multiplier;
128 Multiplier *= DimSize;
129 }
130 return Builder.getInt32(C: FlatIndex);
131}
132
133Value *DXILFlattenArraysVisitor::genInstructionFlattenIndices(
134 ArrayRef<Value *> Indices, ArrayRef<uint64_t> Dims, IRBuilder<> &Builder) {
135 if (Indices.size() == 1)
136 return Indices[0];
137
138 Value *FlatIndex = Builder.getInt32(C: 0);
139 unsigned Multiplier = 1;
140
141 for (int I = Indices.size() - 1; I >= 0; --I) {
142 unsigned DimSize = Dims[I];
143 Value *VMultiplier = Builder.getInt32(C: Multiplier);
144 Value *ScaledIndex = Builder.CreateMul(LHS: Indices[I], RHS: VMultiplier);
145 FlatIndex = Builder.CreateAdd(LHS: FlatIndex, RHS: ScaledIndex);
146 Multiplier *= DimSize;
147 }
148 return FlatIndex;
149}
150
151bool DXILFlattenArraysVisitor::visitLoadInst(LoadInst &LI) {
152 unsigned NumOperands = LI.getNumOperands();
153 for (unsigned I = 0; I < NumOperands; ++I) {
154 Value *CurrOpperand = LI.getOperand(i_nocapture: I);
155 ConstantExpr *CE = dyn_cast<ConstantExpr>(Val: CurrOpperand);
156 if (CE && CE->getOpcode() == Instruction::GetElementPtr) {
157 GetElementPtrInst *OldGEP =
158 cast<GetElementPtrInst>(Val: CE->getAsInstruction());
159 OldGEP->insertBefore(InsertPos: LI.getIterator());
160
161 IRBuilder<> Builder(&LI);
162 LoadInst *NewLoad =
163 Builder.CreateLoad(Ty: LI.getType(), Ptr: OldGEP, Name: LI.getName());
164 NewLoad->setAlignment(LI.getAlign());
165 LI.replaceAllUsesWith(V: NewLoad);
166 LI.eraseFromParent();
167 visitGetElementPtrInst(GEPI&: *OldGEP);
168 return true;
169 }
170 }
171 return false;
172}
173
174bool DXILFlattenArraysVisitor::visitStoreInst(StoreInst &SI) {
175 unsigned NumOperands = SI.getNumOperands();
176 for (unsigned I = 0; I < NumOperands; ++I) {
177 Value *CurrOpperand = SI.getOperand(i_nocapture: I);
178 ConstantExpr *CE = dyn_cast<ConstantExpr>(Val: CurrOpperand);
179 if (CE && CE->getOpcode() == Instruction::GetElementPtr) {
180 GetElementPtrInst *OldGEP =
181 cast<GetElementPtrInst>(Val: CE->getAsInstruction());
182 OldGEP->insertBefore(InsertPos: SI.getIterator());
183
184 IRBuilder<> Builder(&SI);
185 StoreInst *NewStore = Builder.CreateStore(Val: SI.getValueOperand(), Ptr: OldGEP);
186 NewStore->setAlignment(SI.getAlign());
187 SI.replaceAllUsesWith(V: NewStore);
188 SI.eraseFromParent();
189 visitGetElementPtrInst(GEPI&: *OldGEP);
190 return true;
191 }
192 }
193 return false;
194}
195
196bool DXILFlattenArraysVisitor::visitAllocaInst(AllocaInst &AI) {
197 if (!isMultiDimensionalArray(T: AI.getAllocatedType()))
198 return false;
199
200 ArrayType *ArrType = cast<ArrayType>(Val: AI.getAllocatedType());
201 IRBuilder<> Builder(&AI);
202 auto [TotalElements, BaseType] = getElementCountAndType(ArrayTy: ArrType);
203
204 ArrayType *FattenedArrayType = ArrayType::get(ElementType: BaseType, NumElements: TotalElements);
205 AllocaInst *FlatAlloca =
206 Builder.CreateAlloca(Ty: FattenedArrayType, ArraySize: nullptr, Name: AI.getName() + ".1dim");
207 FlatAlloca->setAlignment(AI.getAlign());
208 AI.replaceAllUsesWith(V: FlatAlloca);
209 AI.eraseFromParent();
210 return true;
211}
212
213bool DXILFlattenArraysVisitor::visitGetElementPtrInst(GetElementPtrInst &GEP) {
214 // Do not visit GEPs more than once
215 if (GEPChainInfoMap.contains(Val: cast<GEPOperator>(Val: &GEP)))
216 return false;
217
218 Value *PtrOperand = GEP.getPointerOperand();
219 // It shouldn't(?) be possible for the pointer operand of a GEP to be a PHI
220 // node unless HLSL has pointers. If this assumption is incorrect or HLSL gets
221 // pointer types, then the handling of this case can be implemented later.
222 assert(!isa<PHINode>(PtrOperand) &&
223 "Pointer operand of GEP should not be a PHI Node");
224
225 // Replace a GEP ConstantExpr pointer operand with a GEP instruction so that
226 // it can be visited
227 if (auto *PtrOpGEPCE = dyn_cast<ConstantExpr>(Val: PtrOperand);
228 PtrOpGEPCE && PtrOpGEPCE->getOpcode() == Instruction::GetElementPtr) {
229 GetElementPtrInst *OldGEPI =
230 cast<GetElementPtrInst>(Val: PtrOpGEPCE->getAsInstruction());
231 OldGEPI->insertBefore(InsertPos: GEP.getIterator());
232
233 SmallVector<Value *> Indices(GEP.indices());
234 GetElementPtrInst *NewGEPI = GetElementPtrInst::Create(
235 PointeeType: GEP.getSourceElementType(), Ptr: OldGEPI, IdxList: Indices, NW: GEP.getNoWrapFlags(),
236 NameStr: GEP.getName(), InsertBefore: GEP.getIterator());
237
238 GEP.replaceAllUsesWith(V: NewGEPI);
239 GEP.eraseFromParent();
240 visitGetElementPtrInst(GEP&: *OldGEPI);
241 visitGetElementPtrInst(GEP&: *NewGEPI);
242 return true;
243 }
244
245 // Construct GEPInfo for this GEP
246 GEPInfo Info;
247
248 // Obtain the variable and constant byte offsets computed by this GEP
249 const DataLayout &DL = GEP.getDataLayout();
250 unsigned BitWidth = DL.getIndexTypeSizeInBits(Ty: GEP.getType());
251 Info.ConstantOffset = {BitWidth, 0};
252 [[maybe_unused]] bool Success = GEP.collectOffset(
253 DL, BitWidth, VariableOffsets&: Info.VariableOffsets, ConstantOffset&: Info.ConstantOffset);
254 assert(Success && "Failed to collect offsets for GEP");
255
256 // If there is a parent GEP, inherit the root array type and pointer, and
257 // merge the byte offsets. Otherwise, this GEP is itself the root of a GEP
258 // chain and we need to deterine the root array type
259 if (auto *PtrOpGEP = dyn_cast<GEPOperator>(Val: PtrOperand)) {
260
261 // If the parent GEP was not processed, then we do not want to process its
262 // descendants. This can happen if the GEP chain is for an unsupported type
263 // such as a struct -- we do not flatten structs nor GEP chains for structs
264 if (!GEPChainInfoMap.contains(Val: PtrOpGEP))
265 return false;
266
267 GEPInfo &PGEPInfo = GEPChainInfoMap[PtrOpGEP];
268 Info.RootFlattenedArrayType = PGEPInfo.RootFlattenedArrayType;
269 Info.RootPointerOperand = PGEPInfo.RootPointerOperand;
270 for (auto &VariableOffset : PGEPInfo.VariableOffsets)
271 Info.VariableOffsets.insert(KV: VariableOffset);
272 Info.ConstantOffset += PGEPInfo.ConstantOffset;
273 } else {
274 Info.RootPointerOperand = PtrOperand;
275
276 // We should try to determine the type of the root from the pointer rather
277 // than the GEP's source element type because this could be a scalar GEP
278 // into an array-typed pointer from an Alloca or Global Variable.
279 Type *RootTy = GEP.getSourceElementType();
280 if (auto *GlobalVar = dyn_cast<GlobalVariable>(Val: PtrOperand)) {
281 if (GlobalMap.contains(Val: GlobalVar))
282 GlobalVar = GlobalMap[GlobalVar];
283 Info.RootPointerOperand = GlobalVar;
284 RootTy = GlobalVar->getValueType();
285 } else if (auto *Alloca = dyn_cast<AllocaInst>(Val: PtrOperand))
286 RootTy = Alloca->getAllocatedType();
287 assert(!isMultiDimensionalArray(RootTy) &&
288 "Expected root array type to be flattened");
289
290 // If the root type is not an array, we don't need to do any flattening
291 if (!isa<ArrayType>(Val: RootTy))
292 return false;
293
294 Info.RootFlattenedArrayType = cast<ArrayType>(Val: RootTy);
295 }
296
297 // GEPs without users or GEPs with non-GEP users should be replaced such that
298 // the chain of GEPs they are a part of are collapsed to a single GEP into a
299 // flattened array.
300 bool ReplaceThisGEP = GEP.users().empty();
301 for (Value *User : GEP.users())
302 if (!isa<GetElementPtrInst>(Val: User))
303 ReplaceThisGEP = true;
304
305 if (ReplaceThisGEP) {
306 unsigned BytesPerElem =
307 DL.getTypeAllocSize(Ty: Info.RootFlattenedArrayType->getArrayElementType());
308 assert(isPowerOf2_32(BytesPerElem) &&
309 "Bytes per element should be a power of 2");
310
311 // Compute the 32-bit index for this flattened GEP from the constant and
312 // variable byte offsets in the GEPInfo
313 IRBuilder<> Builder(&GEP);
314 Value *ZeroIndex = Builder.getInt32(C: 0);
315 uint64_t ConstantOffset =
316 Info.ConstantOffset.udiv(RHS: BytesPerElem).getZExtValue();
317 assert(ConstantOffset < UINT32_MAX &&
318 "Constant byte offset for flat GEP index must fit within 32 bits");
319 Value *FlattenedIndex = Builder.getInt32(C: ConstantOffset);
320 for (auto [VarIndex, Multiplier] : Info.VariableOffsets) {
321 assert(Multiplier.getActiveBits() <= 32 &&
322 "The multiplier for a flat GEP index must fit within 32 bits");
323 assert(VarIndex->getType()->isIntegerTy(32) &&
324 "Expected i32-typed GEP indices");
325 Value *VI;
326 if (Multiplier.getZExtValue() % BytesPerElem != 0) {
327 // This can happen, e.g., with i8 GEPs. To handle this we just divide
328 // by BytesPerElem using an instruction after multiplying VarIndex by
329 // Multiplier.
330 VI = Builder.CreateMul(LHS: VarIndex,
331 RHS: Builder.getInt32(C: Multiplier.getZExtValue()));
332 VI = Builder.CreateLShr(LHS: VI, RHS: Builder.getInt32(C: Log2_32(Value: BytesPerElem)));
333 } else
334 VI = Builder.CreateMul(
335 LHS: VarIndex,
336 RHS: Builder.getInt32(C: Multiplier.getZExtValue() / BytesPerElem));
337 FlattenedIndex = Builder.CreateAdd(LHS: FlattenedIndex, RHS: VI);
338 }
339
340 // Construct a new GEP for the flattened array to replace the current GEP
341 GetElementPtrInst *NewGEP = GetElementPtrInst::Create(
342 PointeeType: Info.RootFlattenedArrayType, Ptr: Info.RootPointerOperand,
343 IdxList: {ZeroIndex, FlattenedIndex}, NW: GEP.getNoWrapFlags(), NameStr: GEP.getName(),
344 InsertBefore: Builder.GetInsertPoint());
345
346 // Replace the current GEP with the new GEP. Store GEPInfo into the map
347 // for later use in case this GEP was not the end of the chain
348 GEPChainInfoMap.insert(KV: {cast<GEPOperator>(Val: NewGEP), std::move(Info)});
349 GEP.replaceAllUsesWith(V: NewGEP);
350 GEP.eraseFromParent();
351 return true;
352 }
353
354 // This GEP is potentially dead at the end of the pass since it may not have
355 // any users anymore after GEP chains have been collapsed. We retain store
356 // GEPInfo for GEPs down the chain to use to compute their indices.
357 GEPChainInfoMap.insert(KV: {cast<GEPOperator>(Val: &GEP), std::move(Info)});
358 PotentiallyDeadInstrs.emplace_back(Args: &GEP);
359 return false;
360}
361
362bool DXILFlattenArraysVisitor::visit(Function &F) {
363 bool MadeChange = false;
364 ReversePostOrderTraversal<Function *> RPOT(&F);
365 for (BasicBlock *BB : make_early_inc_range(Range&: RPOT)) {
366 for (Instruction &I : make_early_inc_range(Range&: *BB))
367 MadeChange |= InstVisitor::visit(I);
368 }
369 finish();
370 return MadeChange;
371}
372
373static void collectElements(Constant *Init,
374 SmallVectorImpl<Constant *> &Elements) {
375 // Base case: If Init is not an array, add it directly to the vector.
376 auto *ArrayTy = dyn_cast<ArrayType>(Val: Init->getType());
377 if (!ArrayTy) {
378 Elements.push_back(Elt: Init);
379 return;
380 }
381 unsigned ArrSize = ArrayTy->getNumElements();
382 if (isa<ConstantAggregateZero>(Val: Init)) {
383 for (unsigned I = 0; I < ArrSize; ++I)
384 Elements.push_back(Elt: Constant::getNullValue(Ty: ArrayTy->getElementType()));
385 return;
386 }
387
388 // Recursive case: Process each element in the array.
389 if (auto *ArrayConstant = dyn_cast<ConstantArray>(Val: Init)) {
390 for (unsigned I = 0; I < ArrayConstant->getNumOperands(); ++I) {
391 collectElements(Init: ArrayConstant->getOperand(i_nocapture: I), Elements);
392 }
393 } else if (auto *DataArrayConstant = dyn_cast<ConstantDataArray>(Val: Init)) {
394 for (unsigned I = 0; I < DataArrayConstant->getNumElements(); ++I) {
395 collectElements(Init: DataArrayConstant->getElementAsConstant(i: I), Elements);
396 }
397 } else {
398 llvm_unreachable(
399 "Expected a ConstantArray or ConstantDataArray for array initializer!");
400 }
401}
402
403static Constant *transformInitializer(Constant *Init, Type *OrigType,
404 ArrayType *FlattenedType,
405 LLVMContext &Ctx) {
406 // Handle ConstantAggregateZero (zero-initialized constants)
407 if (isa<ConstantAggregateZero>(Val: Init))
408 return ConstantAggregateZero::get(Ty: FlattenedType);
409
410 // Handle UndefValue (undefined constants)
411 if (isa<UndefValue>(Val: Init))
412 return UndefValue::get(T: FlattenedType);
413
414 if (!isa<ArrayType>(Val: OrigType))
415 return Init;
416
417 SmallVector<Constant *> FlattenedElements;
418 collectElements(Init, Elements&: FlattenedElements);
419 assert(FlattenedType->getNumElements() == FlattenedElements.size() &&
420 "The number of collected elements should match the FlattenedType");
421 return ConstantArray::get(T: FlattenedType, V: FlattenedElements);
422}
423
424static void flattenGlobalArrays(
425 Module &M, SmallDenseMap<GlobalVariable *, GlobalVariable *> &GlobalMap) {
426 LLVMContext &Ctx = M.getContext();
427 for (GlobalVariable &G : M.globals()) {
428 Type *OrigType = G.getValueType();
429 if (!DXILFlattenArraysVisitor::isMultiDimensionalArray(T: OrigType))
430 continue;
431
432 ArrayType *ArrType = cast<ArrayType>(Val: OrigType);
433 auto [TotalElements, BaseType] =
434 DXILFlattenArraysVisitor::getElementCountAndType(ArrayTy: ArrType);
435 ArrayType *FattenedArrayType = ArrayType::get(ElementType: BaseType, NumElements: TotalElements);
436
437 // Create a new global variable with the updated type
438 // Note: Initializer is set via transformInitializer
439 GlobalVariable *NewGlobal =
440 new GlobalVariable(M, FattenedArrayType, G.isConstant(), G.getLinkage(),
441 /*Initializer=*/nullptr, G.getName() + ".1dim", &G,
442 G.getThreadLocalMode(), G.getAddressSpace(),
443 G.isExternallyInitialized());
444
445 // Copy relevant attributes
446 NewGlobal->setUnnamedAddr(G.getUnnamedAddr());
447 if (G.getAlign()) {
448 NewGlobal->setAlignment(G.getAlign());
449 }
450
451 if (G.hasInitializer()) {
452 Constant *Init = G.getInitializer();
453 Constant *NewInit =
454 transformInitializer(Init, OrigType, FlattenedType: FattenedArrayType, Ctx);
455 NewGlobal->setInitializer(NewInit);
456 }
457 GlobalMap[&G] = NewGlobal;
458 }
459}
460
461static bool flattenArrays(Module &M) {
462 bool MadeChange = false;
463 SmallDenseMap<GlobalVariable *, GlobalVariable *> GlobalMap;
464 flattenGlobalArrays(M, GlobalMap);
465 DXILFlattenArraysVisitor Impl(GlobalMap);
466 for (auto &F : make_early_inc_range(Range: M.functions())) {
467 if (F.isDeclaration())
468 continue;
469 MadeChange |= Impl.visit(F);
470 }
471 for (auto &[Old, New] : GlobalMap) {
472 Old->replaceAllUsesWith(V: New);
473 Old->eraseFromParent();
474 MadeChange = true;
475 }
476 return MadeChange;
477}
478
479PreservedAnalyses DXILFlattenArraysPass::run(Module &M,
480 ModuleAnalysisManager &) {
481 bool MadeChanges = flattenArrays(M);
482 if (!MadeChanges)
483 return PreservedAnalyses::all();
484 PreservedAnalyses PA;
485 return PA;
486}
487
488bool DXILFlattenArraysLegacy::runOnModule(Module &M) {
489 return flattenArrays(M);
490}
491
492char DXILFlattenArraysLegacy::ID = 0;
493
494INITIALIZE_PASS_BEGIN(DXILFlattenArraysLegacy, DEBUG_TYPE,
495 "DXIL Array Flattener", false, false)
496INITIALIZE_PASS_END(DXILFlattenArraysLegacy, DEBUG_TYPE, "DXIL Array Flattener",
497 false, false)
498
499ModulePass *llvm::createDXILFlattenArraysLegacyPass() {
500 return new DXILFlattenArraysLegacy();
501}
502