1//===-- SPIRVRegularizer.cpp - regularize IR for SPIR-V ---------*- C++ -*-===//
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// This pass implements regularization of LLVM IR for SPIR-V. The prototype of
10// the pass was taken from SPIRV-LLVM translator.
11//
12//===----------------------------------------------------------------------===//
13
14#include "SPIRV.h"
15#include "llvm/ADT/STLExtras.h"
16#include "llvm/IR/Constants.h"
17#include "llvm/IR/IRBuilder.h"
18#include "llvm/IR/InstIterator.h"
19#include "llvm/IR/Instructions.h"
20#include "llvm/IR/PassManager.h"
21
22#include <list>
23
24#define DEBUG_TYPE "spirv-regularizer"
25
26using namespace llvm;
27
28static bool runImpl(Function &F);
29
30namespace {
31struct SPIRVRegularizerLegacy : public FunctionPass {
32public:
33 static char ID;
34 SPIRVRegularizerLegacy() : FunctionPass(ID) {}
35 bool runOnFunction(Function &F) override { return runImpl(F); }
36 StringRef getPassName() const override { return "SPIR-V Regularizer"; }
37
38 void getAnalysisUsage(AnalysisUsage &AU) const override {
39 FunctionPass::getAnalysisUsage(AU);
40 }
41};
42} // namespace
43
44char SPIRVRegularizerLegacy::ID = 0;
45
46INITIALIZE_PASS(SPIRVRegularizerLegacy, DEBUG_TYPE, "SPIR-V Regularizer", false,
47 false)
48
49// Since SPIR-V cannot represent constant expression, constant expressions
50// in LLVM IR need to be lowered to instructions. For each function,
51// the constant expressions used by instructions of the function are replaced
52// by instructions placed in the entry block since it dominates all other BBs.
53// Each constant expression only needs to be lowered once in each function
54// and all uses of it by instructions in that function are replaced by
55// one instruction.
56// TODO: remove redundant instructions for common subexpression.
57static void runLowerConstExpr(Function &F) {
58 LLVMContext &Ctx = F.getContext();
59 std::list<Instruction *> WorkList;
60 for (auto &II : instructions(F))
61 WorkList.push_back(x: &II);
62
63 auto FBegin = F.begin();
64 while (!WorkList.empty()) {
65 Instruction *II = WorkList.front();
66
67 auto LowerOp = [&II, &FBegin, &F](Value *V) -> Value * {
68 if (isa<Function>(Val: V))
69 return V;
70 auto *CE = cast<ConstantExpr>(Val: V);
71 LLVM_DEBUG(dbgs() << "[lowerConstantExpressions] " << *CE);
72 auto ReplInst = CE->getAsInstruction();
73 auto InsPoint = II->getParent() == &*FBegin ? II : &FBegin->back();
74 ReplInst->insertBefore(InsertPos: InsPoint->getIterator());
75 LLVM_DEBUG(dbgs() << " -> " << *ReplInst << '\n');
76 std::vector<Instruction *> Users;
77 // Do not replace use during iteration of use. Do it in another loop.
78 for (auto U : CE->users()) {
79 LLVM_DEBUG(dbgs() << "[lowerConstantExpressions] Use: " << *U << '\n');
80 auto InstUser = dyn_cast<Instruction>(Val: U);
81 // Only replace users in scope of current function.
82 if (InstUser && InstUser->getParent()->getParent() == &F)
83 Users.push_back(x: InstUser);
84 }
85 for (auto &User : Users) {
86 if (ReplInst->getParent() == User->getParent() &&
87 User->comesBefore(Other: ReplInst))
88 ReplInst->moveBefore(InsertPos: User->getIterator());
89 User->replaceUsesOfWith(From: CE, To: ReplInst);
90 }
91 return ReplInst;
92 };
93
94 WorkList.pop_front();
95 for (unsigned OI = 0, OE = II->getNumOperands(); OI != OE; ++OI) {
96 auto *Op = II->getOperand(i: OI);
97 if (auto CE = dyn_cast<ConstantExpr>(Val: Op)) {
98 WorkList.push_front(x: cast<Instruction>(Val: LowerOp(CE)));
99 } else if (auto MDAsVal = dyn_cast<MetadataAsValue>(Val: Op)) {
100 auto ConstMD = dyn_cast<ConstantAsMetadata>(Val: MDAsVal->getMetadata());
101 if (!ConstMD)
102 continue;
103 Constant *C = ConstMD->getValue();
104 auto *CE = dyn_cast<ConstantExpr>(Val: C);
105 if (!CE)
106 continue;
107 Value *ReplInst = LowerOp(CE);
108 Metadata *RepMD = ValueAsMetadata::get(V: ReplInst);
109 Value *RepMDVal = MetadataAsValue::get(Context&: Ctx, MD: RepMD);
110 II->setOperand(i: OI, Val: RepMDVal);
111 WorkList.push_front(x: cast<Instruction>(Val: ReplInst));
112 }
113 }
114 }
115}
116
117// Lower i1 comparisons with certain predicates to logical operations.
118// The backend treats i1 as boolean values, and SPIR-V only allows logical
119// operations for boolean values. This function lowers i1 comparisons with
120// certain predicates to logical operations to generate valid SPIR-V.
121static void runLowerI1Comparisons(Function &F) {
122 for (auto &I : make_early_inc_range(Range: instructions(F))) {
123 auto *Cmp = dyn_cast<ICmpInst>(Val: &I);
124 if (!Cmp)
125 continue;
126
127 bool IsI1 = Cmp->getOperand(i_nocapture: 0)->getType()->getScalarType()->isIntegerTy(BitWidth: 1);
128 if (!IsI1)
129 continue;
130
131 auto Pred = Cmp->getPredicate();
132 bool IsTargetPred =
133 Pred >= ICmpInst::ICMP_UGT && Pred <= ICmpInst::ICMP_SLE;
134 if (!IsTargetPred)
135 continue;
136
137 Value *P = Cmp->getOperand(i_nocapture: 0);
138 Value *Q = Cmp->getOperand(i_nocapture: 1);
139
140 IRBuilder<> Builder(Cmp);
141 Value *Result = nullptr;
142 switch (Pred) {
143 case ICmpInst::ICMP_UGT:
144 case ICmpInst::ICMP_SLT:
145 // Result = p & !q
146 Result = Builder.CreateAnd(LHS: P, RHS: Builder.CreateNot(V: Q));
147 break;
148 case ICmpInst::ICMP_ULT:
149 case ICmpInst::ICMP_SGT:
150 // Result = q & !p
151 Result = Builder.CreateAnd(LHS: Q, RHS: Builder.CreateNot(V: P));
152 break;
153 case ICmpInst::ICMP_ULE:
154 case ICmpInst::ICMP_SGE:
155 // Result = q | !p
156 Result = Builder.CreateOr(LHS: Q, RHS: Builder.CreateNot(V: P));
157 break;
158 case ICmpInst::ICMP_UGE:
159 case ICmpInst::ICMP_SLE:
160 // Result = p | !q
161 Result = Builder.CreateOr(LHS: P, RHS: Builder.CreateNot(V: Q));
162 break;
163 default:
164 llvm_unreachable("Unexpected predicate");
165 }
166
167 Result->takeName(V: Cmp);
168 Cmp->replaceAllUsesWith(V: Result);
169 Cmp->eraseFromParent();
170 }
171}
172
173// OpSwitch requires an integer selector, but i1 maps to OpTypeBool. Lower
174// boolean switches to branches. This runs before structurization, so that
175// merge instructions match the resulting CFG.
176static void runLowerI1Switches(Function &F) {
177 for (BasicBlock &BB : F) {
178 auto *SI = dyn_cast<SwitchInst>(Val: BB.getTerminator());
179 if (!SI || !SI->getCondition()->getType()->isIntegerTy(BitWidth: 1))
180 continue;
181 BasicBlock *Dests[2] = {SI->getDefaultDest(), SI->getDefaultDest()};
182 for (auto Case : SI->cases())
183 Dests[Case.getCaseValue()->isOne()] = Case.getCaseSuccessor();
184 // Both values have a case, so the default is unreachable.
185 if (SI->getNumCases() == 2)
186 SI->getDefaultDest()->removePredecessor(Pred: &BB);
187 Instruction *Br;
188 if (SI->getNumCases() == 0)
189 Br = UncondBrInst::Create(Target: Dests[0], InsertBefore: SI->getIterator());
190 else
191 Br = CondBrInst::Create(Cond: SI->getCondition(), IfTrue: Dests[1], IfFalse: Dests[0],
192 InsertBefore: SI->getIterator());
193 Br->copyMetadata(SrcInst: *SI, WL: {LLVMContext::MD_dbg, LLVMContext::MD_loop});
194 SI->eraseFromParent();
195 }
196}
197
198static bool runImpl(Function &F) {
199 runLowerI1Comparisons(F);
200 runLowerI1Switches(F);
201 runLowerConstExpr(F);
202 return true;
203}
204
205PreservedAnalyses SPIRVRegularizerPass::run(Function &F,
206 FunctionAnalysisManager &AM) {
207 return runImpl(F) ? PreservedAnalyses::none() : PreservedAnalyses::all();
208}
209
210FunctionPass *llvm::createSPIRVRegularizerPass() {
211 return new SPIRVRegularizerLegacy();
212}
213