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
173static bool runImpl(Function &F) {
174 runLowerI1Comparisons(F);
175 runLowerConstExpr(F);
176 return true;
177}
178
179PreservedAnalyses SPIRVRegularizerPass::run(Function &F,
180 FunctionAnalysisManager &AM) {
181 return runImpl(F) ? PreservedAnalyses::none() : PreservedAnalyses::all();
182}
183
184FunctionPass *llvm::createSPIRVRegularizerPass() {
185 return new SPIRVRegularizerLegacy();
186}
187