1//===------------ BPFCheckAndAdjustIR.cpp - Check and Adjust IR -----------===//
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// Check IR and adjust IR for verifier friendly codes.
10// The following are done for IR checking:
11// - no relocation globals in PHI node.
12// The following are done for IR adjustment:
13// - remove __builtin_bpf_passthrough builtins. Target independent IR
14// optimizations are done and those builtins can be removed.
15// - remove llvm.bpf.getelementptr.and.load builtins.
16// - remove llvm.bpf.getelementptr.and.store builtins.
17// - for loads and stores with base addresses from non-zero address space
18// cast base address to zero address space (support for BPF address spaces).
19//
20//===----------------------------------------------------------------------===//
21
22#include "BPF.h"
23#include "BPFCORE.h"
24#include "BPFTargetMachine.h"
25#include "llvm/Analysis/LoopInfo.h"
26#include "llvm/IR/DebugInfoMetadata.h"
27#include "llvm/IR/GlobalVariable.h"
28#include "llvm/IR/IRBuilder.h"
29#include "llvm/IR/Instruction.h"
30#include "llvm/IR/Instructions.h"
31#include "llvm/IR/IntrinsicsBPF.h"
32#include "llvm/IR/Module.h"
33#include "llvm/IR/Type.h"
34#include "llvm/IR/User.h"
35#include "llvm/IR/Value.h"
36#include "llvm/Pass.h"
37#include "llvm/Transforms/Utils/BasicBlockUtils.h"
38
39#define DEBUG_TYPE "bpf-check-and-opt-ir"
40
41using namespace llvm;
42
43namespace {
44
45class BPFCheckAndAdjustIR final : public ModulePass {
46 bool runOnModule(Module &F) override;
47
48public:
49 static char ID;
50 BPFCheckAndAdjustIR() : ModulePass(ID) {}
51 virtual void getAnalysisUsage(AnalysisUsage &AU) const override;
52
53private:
54 void checkIR(Module &M);
55 bool adjustIR(Module &M);
56 bool removePassThroughBuiltin(Module &M);
57 bool removeCompareBuiltin(Module &M);
58 bool sinkMinMax(Module &M);
59 bool removeGEPBuiltins(Module &M);
60 bool insertASpaceCasts(Module &M);
61};
62} // End anonymous namespace
63
64char BPFCheckAndAdjustIR::ID = 0;
65INITIALIZE_PASS(BPFCheckAndAdjustIR, DEBUG_TYPE, "BPF Check And Adjust IR",
66 false, false)
67
68ModulePass *llvm::createBPFCheckAndAdjustIR() {
69 return new BPFCheckAndAdjustIR();
70}
71
72void BPFCheckAndAdjustIR::checkIR(Module &M) {
73 // Ensure relocation global won't appear in PHI node
74 // This may happen if the compiler generated the following code:
75 // B1:
76 // g1 = @llvm.skb_buff:0:1...
77 // ...
78 // goto B_COMMON
79 // B2:
80 // g2 = @llvm.skb_buff:0:2...
81 // ...
82 // goto B_COMMON
83 // B_COMMON:
84 // g = PHI(g1, g2)
85 // x = load g
86 // ...
87 // If anything likes the above "g = PHI(g1, g2)", issue a fatal error.
88 for (Function &F : M)
89 for (auto &BB : F)
90 for (auto &I : BB) {
91 PHINode *PN = dyn_cast<PHINode>(Val: &I);
92 if (!PN || PN->use_empty())
93 continue;
94 for (int i = 0, e = PN->getNumIncomingValues(); i < e; ++i) {
95 auto *GV = dyn_cast<GlobalVariable>(Val: PN->getIncomingValue(i));
96 if (!GV)
97 continue;
98 if (GV->hasAttribute(Kind: BPFCoreSharedInfo::AmaAttr) ||
99 GV->hasAttribute(Kind: BPFCoreSharedInfo::TypeIdAttr))
100 report_fatal_error(reason: "relocation global in PHI node");
101 }
102 }
103}
104
105bool BPFCheckAndAdjustIR::removePassThroughBuiltin(Module &M) {
106 // Remove __builtin_bpf_passthrough()'s which are used to prevent
107 // certain IR optimizations. Now major IR optimizations are done,
108 // remove them.
109 bool Changed = false;
110 CallInst *ToBeDeleted = nullptr;
111 for (Function &F : M)
112 for (auto &BB : F)
113 for (auto &I : BB) {
114 if (ToBeDeleted) {
115 ToBeDeleted->eraseFromParent();
116 ToBeDeleted = nullptr;
117 }
118
119 auto *Call = dyn_cast<CallInst>(Val: &I);
120 if (!Call)
121 continue;
122 auto *GV = dyn_cast<GlobalValue>(Val: Call->getCalledOperand());
123 if (!GV)
124 continue;
125 if (!GV->getName().starts_with(Prefix: "llvm.bpf.passthrough"))
126 continue;
127 Changed = true;
128 Value *Arg = Call->getArgOperand(i: 1);
129 Call->replaceAllUsesWith(V: Arg);
130 ToBeDeleted = Call;
131 }
132 return Changed;
133}
134
135bool BPFCheckAndAdjustIR::removeCompareBuiltin(Module &M) {
136 // Remove __builtin_bpf_compare()'s which are used to prevent
137 // certain IR optimizations. Now major IR optimizations are done,
138 // remove them.
139 bool Changed = false;
140 CallInst *ToBeDeleted = nullptr;
141 for (Function &F : M)
142 for (auto &BB : F)
143 for (auto &I : BB) {
144 if (ToBeDeleted) {
145 ToBeDeleted->eraseFromParent();
146 ToBeDeleted = nullptr;
147 }
148
149 auto *Call = dyn_cast<CallInst>(Val: &I);
150 if (!Call)
151 continue;
152 auto *GV = dyn_cast<GlobalValue>(Val: Call->getCalledOperand());
153 if (!GV)
154 continue;
155 if (!GV->getName().starts_with(Prefix: "llvm.bpf.compare"))
156 continue;
157
158 Changed = true;
159 Value *Arg0 = Call->getArgOperand(i: 0);
160 Value *Arg1 = Call->getArgOperand(i: 1);
161 Value *Arg2 = Call->getArgOperand(i: 2);
162
163 auto OpVal = cast<ConstantInt>(Val: Arg0)->getValue().getZExtValue();
164 CmpInst::Predicate Opcode = (CmpInst::Predicate)OpVal;
165
166 auto *ICmp = new ICmpInst(Opcode, Arg1, Arg2);
167 ICmp->insertBefore(InsertPos: Call);
168
169 Call->replaceAllUsesWith(V: ICmp);
170 ToBeDeleted = Call;
171 }
172 return Changed;
173}
174
175struct MinMaxSinkInfo {
176 ICmpInst *ICmp;
177 Value *Other;
178 ICmpInst::Predicate Predicate;
179 CallInst *MinMax;
180 ZExtInst *ZExt;
181 SExtInst *SExt;
182
183 MinMaxSinkInfo(ICmpInst *ICmp, Value *Other, ICmpInst::Predicate Predicate)
184 : ICmp(ICmp), Other(Other), Predicate(Predicate), MinMax(nullptr),
185 ZExt(nullptr), SExt(nullptr) {}
186};
187
188static bool sinkMinMaxInBB(BasicBlock &BB,
189 const std::function<bool(Instruction *)> &Filter) {
190 // Check if V is:
191 // (fn %a %b) or (ext (fn %a %b))
192 // Where:
193 // ext := sext | zext
194 // fn := smin | umin | smax | umax
195 auto IsMinMaxCall = [=](Value *V, MinMaxSinkInfo &Info) {
196 if (auto *ZExt = dyn_cast<ZExtInst>(Val: V)) {
197 V = ZExt->getOperand(i_nocapture: 0);
198 Info.ZExt = ZExt;
199 } else if (auto *SExt = dyn_cast<SExtInst>(Val: V)) {
200 V = SExt->getOperand(i_nocapture: 0);
201 Info.SExt = SExt;
202 }
203
204 auto *Call = dyn_cast<CallInst>(Val: V);
205 if (!Call)
206 return false;
207
208 auto *Called = dyn_cast<Function>(Val: Call->getCalledOperand());
209 if (!Called)
210 return false;
211
212 switch (Called->getIntrinsicID()) {
213 case Intrinsic::smin:
214 case Intrinsic::umin:
215 case Intrinsic::smax:
216 case Intrinsic::umax:
217 break;
218 default:
219 return false;
220 }
221
222 if (!Filter(Call))
223 return false;
224
225 Info.MinMax = Call;
226
227 return true;
228 };
229
230 auto ZeroOrSignExtend = [](IRBuilder<> &Builder, Value *V,
231 MinMaxSinkInfo &Info) {
232 if (Info.SExt) {
233 if (Info.SExt->getType() == V->getType())
234 return V;
235 return Builder.CreateSExt(V, DestTy: Info.SExt->getType());
236 }
237 if (Info.ZExt) {
238 if (Info.ZExt->getType() == V->getType())
239 return V;
240 return Builder.CreateZExt(V, DestTy: Info.ZExt->getType());
241 }
242 return V;
243 };
244
245 bool Changed = false;
246 SmallVector<MinMaxSinkInfo, 2> SinkList;
247
248 // Check BB for instructions like:
249 // insn := (icmp %a (fn ...)) | (icmp (fn ...) %a)
250 //
251 // Where:
252 // fn := min | max | (sext (min ...)) | (sext (max ...))
253 //
254 // Put such instructions to SinkList.
255 for (Instruction &I : BB) {
256 ICmpInst *ICmp = dyn_cast<ICmpInst>(Val: &I);
257 if (!ICmp)
258 continue;
259 if (!ICmp->isRelational())
260 continue;
261 MinMaxSinkInfo First(ICmp, ICmp->getOperand(i_nocapture: 1),
262 ICmpInst::getSwappedPredicate(pred: ICmp->getPredicate()));
263 MinMaxSinkInfo Second(ICmp, ICmp->getOperand(i_nocapture: 0), ICmp->getPredicate());
264 bool FirstMinMax = IsMinMaxCall(ICmp->getOperand(i_nocapture: 0), First);
265 bool SecondMinMax = IsMinMaxCall(ICmp->getOperand(i_nocapture: 1), Second);
266 if (!(FirstMinMax ^ SecondMinMax))
267 continue;
268 SinkList.push_back(Elt: FirstMinMax ? First : Second);
269 }
270
271 // Iterate SinkList and replace each (icmp ...) with corresponding
272 // `x < a && x < b` or similar expression.
273 for (auto &Info : SinkList) {
274 ICmpInst *ICmp = Info.ICmp;
275 CallInst *MinMax = Info.MinMax;
276 Intrinsic::ID IID = MinMax->getCalledFunction()->getIntrinsicID();
277 ICmpInst::Predicate P = Info.Predicate;
278 if (ICmpInst::isSigned(predicate: P) && IID != Intrinsic::smin &&
279 IID != Intrinsic::smax)
280 continue;
281
282 IRBuilder<> Builder(ICmp);
283 Value *X = Info.Other;
284 Value *A = ZeroOrSignExtend(Builder, MinMax->getArgOperand(i: 0), Info);
285 Value *B = ZeroOrSignExtend(Builder, MinMax->getArgOperand(i: 1), Info);
286 bool IsMin = IID == Intrinsic::smin || IID == Intrinsic::umin;
287 bool IsMax = IID == Intrinsic::smax || IID == Intrinsic::umax;
288 bool IsLess = ICmpInst::isLE(P) || ICmpInst::isLT(P);
289 bool IsGreater = ICmpInst::isGE(P) || ICmpInst::isGT(P);
290 assert(IsMin ^ IsMax);
291 assert(IsLess ^ IsGreater);
292
293 Value *Replacement;
294 Value *LHS = Builder.CreateICmp(P, LHS: X, RHS: A);
295 Value *RHS = Builder.CreateICmp(P, LHS: X, RHS: B);
296 if ((IsLess && IsMin) || (IsGreater && IsMax))
297 // x < min(a, b) -> x < a && x < b
298 // x > max(a, b) -> x > a && x > b
299 Replacement = Builder.CreateLogicalAnd(Cond1: LHS, Cond2: RHS);
300 else
301 // x > min(a, b) -> x > a || x > b
302 // x < max(a, b) -> x < a || x < b
303 Replacement = Builder.CreateLogicalOr(Cond1: LHS, Cond2: RHS);
304
305 ICmp->replaceAllUsesWith(V: Replacement);
306
307 Instruction *ToRemove[] = {ICmp, Info.ZExt, Info.SExt, MinMax};
308 for (Instruction *I : ToRemove)
309 if (I && I->use_empty())
310 I->eraseFromParent();
311
312 Changed = true;
313 }
314
315 return Changed;
316}
317
318// Do the following transformation:
319//
320// x < min(a, b) -> x < a && x < b
321// x > min(a, b) -> x > a || x > b
322// x < max(a, b) -> x < a || x < b
323// x > max(a, b) -> x > a && x > b
324//
325// Such patterns are introduced by LICM.cpp:hoistMinMax()
326// transformation and might lead to BPF verification failures for
327// older kernels.
328//
329// To minimize "collateral" changes only do it for icmp + min/max
330// calls when icmp is inside a loop and min/max is outside of that
331// loop.
332//
333// Verification failure happens when:
334// - RHS operand of some `icmp LHS, RHS` is replaced by some RHS1;
335// - verifier can recognize RHS as a constant scalar in some context;
336// - verifier can't recognize RHS1 as a constant scalar in the same
337// context;
338//
339// The "constant scalar" is not a compile time constant, but a register
340// that holds a scalar value known to verifier at some point in time
341// during abstract interpretation.
342//
343// See also:
344// https://lore.kernel.org/bpf/20230406164505.1046801-1-yhs@fb.com/
345bool BPFCheckAndAdjustIR::sinkMinMax(Module &M) {
346 bool Changed = false;
347
348 for (Function &F : M) {
349 if (F.isDeclaration())
350 continue;
351
352 LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>(F).getLoopInfo();
353 for (Loop *L : LI)
354 for (BasicBlock *BB : L->blocks()) {
355 // Filter out instructions coming from the same loop
356 Loop *BBLoop = LI.getLoopFor(BB);
357 auto OtherLoopFilter = [&](Instruction *I) {
358 return LI.getLoopFor(BB: I->getParent()) != BBLoop;
359 };
360 Changed |= sinkMinMaxInBB(BB&: *BB, Filter: OtherLoopFilter);
361 }
362 }
363
364 return Changed;
365}
366
367void BPFCheckAndAdjustIR::getAnalysisUsage(AnalysisUsage &AU) const {
368 AU.addRequired<LoopInfoWrapperPass>();
369}
370
371static void unrollGEPLoad(CallInst *Call) {
372 auto [GEP, Load] = BPFPreserveStaticOffsetPass::reconstructLoad(Call);
373 GEP->insertBefore(InsertPos: Call);
374 Load->insertBefore(InsertPos: Call);
375 Call->replaceAllUsesWith(V: Load);
376 Call->eraseFromParent();
377}
378
379static void unrollGEPStore(CallInst *Call) {
380 auto [GEP, Store] = BPFPreserveStaticOffsetPass::reconstructStore(Call);
381 GEP->insertBefore(InsertPos: Call);
382 Store->insertBefore(InsertPos: Call);
383 Call->eraseFromParent();
384}
385
386static bool removeGEPBuiltinsInFunc(Function &F) {
387 SmallVector<CallInst *> GEPLoads;
388 SmallVector<CallInst *> GEPStores;
389 for (auto &BB : F)
390 for (auto &Insn : BB)
391 if (auto *Call = dyn_cast<CallInst>(Val: &Insn))
392 if (auto *Called = Call->getCalledFunction())
393 switch (Called->getIntrinsicID()) {
394 case Intrinsic::bpf_getelementptr_and_load:
395 GEPLoads.push_back(Elt: Call);
396 break;
397 case Intrinsic::bpf_getelementptr_and_store:
398 GEPStores.push_back(Elt: Call);
399 break;
400 }
401
402 if (GEPLoads.empty() && GEPStores.empty())
403 return false;
404
405 for_each(Range&: GEPLoads, F: unrollGEPLoad);
406 for_each(Range&: GEPStores, F: unrollGEPStore);
407
408 return true;
409}
410
411// Rewrites the following builtins:
412// - llvm.bpf.getelementptr.and.load
413// - llvm.bpf.getelementptr.and.store
414// As (load (getelementptr ...)) or (store (getelementptr ...)).
415bool BPFCheckAndAdjustIR::removeGEPBuiltins(Module &M) {
416 bool Changed = false;
417 for (auto &F : M)
418 Changed = removeGEPBuiltinsInFunc(F) || Changed;
419 return Changed;
420}
421
422// Wrap ToWrap with cast to address space zero:
423// - if ToWrap is a getelementptr,
424// wrap it's base pointer instead and return a copy;
425// - if ToWrap is Instruction, insert address space cast
426// immediately after ToWrap;
427// - if ToWrap is not an Instruction (function parameter
428// or a global value), insert address space cast at the
429// beginning of the Function F;
430// - use Cache to avoid inserting too many casts;
431static Value *aspaceWrapValue(DenseMap<Value *, Value *> &Cache, Function *F,
432 Value *ToWrap) {
433 auto It = Cache.find(Val: ToWrap);
434 if (It != Cache.end())
435 return It->getSecond();
436
437 if (auto *GEP = dyn_cast<GetElementPtrInst>(Val: ToWrap)) {
438 Value *Ptr = GEP->getPointerOperand();
439 Value *WrappedPtr = aspaceWrapValue(Cache, F, ToWrap: Ptr);
440 auto *GEPTy = cast<PointerType>(Val: GEP->getType());
441 auto *NewGEP = GEP->clone();
442 NewGEP->insertAfter(InsertPos: GEP);
443 NewGEP->mutateType(Ty: GEPTy->getPointerTo(AddrSpace: 0));
444 NewGEP->setOperand(i: GEP->getPointerOperandIndex(), Val: WrappedPtr);
445 NewGEP->setName(GEP->getName());
446 Cache[ToWrap] = NewGEP;
447 return NewGEP;
448 }
449
450 IRBuilder IB(F->getContext());
451 if (Instruction *InsnPtr = dyn_cast<Instruction>(Val: ToWrap))
452 IB.SetInsertPoint(*InsnPtr->getInsertionPointAfterDef());
453 else
454 IB.SetInsertPoint(F->getEntryBlock().getFirstInsertionPt());
455 auto *PtrTy = cast<PointerType>(Val: ToWrap->getType());
456 auto *ASZeroPtrTy = PtrTy->getPointerTo(AddrSpace: 0);
457 auto *ACast = IB.CreateAddrSpaceCast(V: ToWrap, DestTy: ASZeroPtrTy, Name: ToWrap->getName());
458 Cache[ToWrap] = ACast;
459 return ACast;
460}
461
462// Wrap a pointer operand OpNum of instruction I
463// with cast to address space zero
464static void aspaceWrapOperand(DenseMap<Value *, Value *> &Cache, Instruction *I,
465 unsigned OpNum) {
466 Value *OldOp = I->getOperand(i: OpNum);
467 if (OldOp->getType()->getPointerAddressSpace() == 0)
468 return;
469
470 Value *NewOp = aspaceWrapValue(Cache, F: I->getFunction(), ToWrap: OldOp);
471 I->setOperand(i: OpNum, Val: NewOp);
472 // Check if there are any remaining users of old GEP,
473 // delete those w/o users
474 for (;;) {
475 auto *OldGEP = dyn_cast<GetElementPtrInst>(Val: OldOp);
476 if (!OldGEP)
477 break;
478 if (!OldGEP->use_empty())
479 break;
480 OldOp = OldGEP->getPointerOperand();
481 OldGEP->eraseFromParent();
482 }
483}
484
485// Support for BPF address spaces:
486// - for each function in the module M, update pointer operand of
487// each memory access instruction (load/store/cmpxchg/atomicrmw)
488// by casting it from non-zero address space to zero address space, e.g:
489//
490// (load (ptr addrspace (N) %p) ...)
491// -> (load (addrspacecast ptr addrspace (N) %p to ptr))
492//
493// - assign section with name .addr_space.N for globals defined in
494// non-zero address space N
495bool BPFCheckAndAdjustIR::insertASpaceCasts(Module &M) {
496 bool Changed = false;
497 for (Function &F : M) {
498 DenseMap<Value *, Value *> CastsCache;
499 for (BasicBlock &BB : F) {
500 for (Instruction &I : BB) {
501 unsigned PtrOpNum;
502
503 if (auto *LD = dyn_cast<LoadInst>(Val: &I))
504 PtrOpNum = LD->getPointerOperandIndex();
505 else if (auto *ST = dyn_cast<StoreInst>(Val: &I))
506 PtrOpNum = ST->getPointerOperandIndex();
507 else if (auto *CmpXchg = dyn_cast<AtomicCmpXchgInst>(Val: &I))
508 PtrOpNum = CmpXchg->getPointerOperandIndex();
509 else if (auto *RMW = dyn_cast<AtomicRMWInst>(Val: &I))
510 PtrOpNum = RMW->getPointerOperandIndex();
511 else
512 continue;
513
514 aspaceWrapOperand(Cache&: CastsCache, I: &I, OpNum: PtrOpNum);
515 }
516 }
517 Changed |= !CastsCache.empty();
518 }
519 // Merge all globals within same address space into single
520 // .addr_space.<addr space no> section
521 for (GlobalVariable &G : M.globals()) {
522 if (G.getAddressSpace() == 0 || G.hasSection())
523 continue;
524 SmallString<16> SecName;
525 raw_svector_ostream OS(SecName);
526 OS << ".addr_space." << G.getAddressSpace();
527 G.setSection(SecName);
528 // Prevent having separate section for constants
529 G.setConstant(false);
530 }
531 return Changed;
532}
533
534bool BPFCheckAndAdjustIR::adjustIR(Module &M) {
535 bool Changed = removePassThroughBuiltin(M);
536 Changed = removeCompareBuiltin(M) || Changed;
537 Changed = sinkMinMax(M) || Changed;
538 Changed = removeGEPBuiltins(M) || Changed;
539 Changed = insertASpaceCasts(M) || Changed;
540 return Changed;
541}
542
543bool BPFCheckAndAdjustIR::runOnModule(Module &M) {
544 checkIR(M);
545 return adjustIR(M);
546}
547