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 "llvm/ADT/MapVector.h"
25#include "llvm/Analysis/LoopInfo.h"
26#include "llvm/IR/Analysis.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/IntrinsicInst.h"
32#include "llvm/IR/IntrinsicsBPF.h"
33#include "llvm/IR/Module.h"
34#include "llvm/IR/PassManager.h"
35#include "llvm/IR/ProfDataUtils.h"
36#include "llvm/IR/Type.h"
37#include "llvm/IR/Value.h"
38#include "llvm/Pass.h"
39#include "llvm/Transforms/Utils/BasicBlockUtils.h"
40
41#define DEBUG_TYPE "bpf-check-and-opt-ir"
42
43using namespace llvm;
44
45namespace {
46
47class BPFCheckAndAdjustIRLegacy final : public ModulePass {
48 bool runOnModule(Module &F) override;
49
50public:
51 static char ID;
52 BPFCheckAndAdjustIRLegacy() : ModulePass(ID) {}
53 void getAnalysisUsage(AnalysisUsage &AU) const override;
54};
55} // End anonymous namespace
56
57char BPFCheckAndAdjustIRLegacy::ID = 0;
58INITIALIZE_PASS(BPFCheckAndAdjustIRLegacy, DEBUG_TYPE,
59 "BPF Check And Adjust IR", false, false)
60
61ModulePass *llvm::createBPFCheckAndAdjustIRLegacyPass() {
62 return new BPFCheckAndAdjustIRLegacy();
63}
64
65static void checkIR(Module &M) {
66 // Ensure relocation global won't appear in PHI node
67 // This may happen if the compiler generated the following code:
68 // B1:
69 // g1 = @llvm.skb_buff:0:1...
70 // ...
71 // goto B_COMMON
72 // B2:
73 // g2 = @llvm.skb_buff:0:2...
74 // ...
75 // goto B_COMMON
76 // B_COMMON:
77 // g = PHI(g1, g2)
78 // x = load g
79 // ...
80 // If anything likes the above "g = PHI(g1, g2)", issue a fatal error.
81 for (Function &F : M)
82 for (auto &BB : F)
83 for (auto &I : BB) {
84 PHINode *PN = dyn_cast<PHINode>(Val: &I);
85 if (!PN || PN->use_empty())
86 continue;
87 for (int i = 0, e = PN->getNumIncomingValues(); i < e; ++i) {
88 auto *GV = dyn_cast<GlobalVariable>(Val: PN->getIncomingValue(i));
89 if (!GV)
90 continue;
91 if (GV->hasAttribute(Kind: BPFCoreSharedInfo::AmaAttr) ||
92 GV->hasAttribute(Kind: BPFCoreSharedInfo::TypeIdAttr))
93 report_fatal_error(reason: "relocation global in PHI node");
94 }
95 }
96}
97
98static bool removePassThroughBuiltin(Module &M) {
99 // Remove __builtin_bpf_passthrough()'s which are used to prevent
100 // certain IR optimizations. Now major IR optimizations are done,
101 // remove them.
102 bool Changed = false;
103 CallInst *ToBeDeleted = nullptr;
104 for (Function &F : M)
105 for (auto &BB : F)
106 for (auto &I : BB) {
107 if (ToBeDeleted) {
108 ToBeDeleted->eraseFromParent();
109 ToBeDeleted = nullptr;
110 }
111
112 auto *Call = dyn_cast<CallInst>(Val: &I);
113 if (!Call)
114 continue;
115 auto *GV = dyn_cast<GlobalValue>(Val: Call->getCalledOperand());
116 if (!GV)
117 continue;
118 if (!GV->getName().starts_with(Prefix: "llvm.bpf.passthrough"))
119 continue;
120 Changed = true;
121 Value *Arg = Call->getArgOperand(i: 1);
122 Call->replaceAllUsesWith(V: Arg);
123 ToBeDeleted = Call;
124 }
125 return Changed;
126}
127
128static bool removeCompareBuiltin(Module &M) {
129 // Remove __builtin_bpf_compare()'s which are used to prevent
130 // certain IR optimizations. Now major IR optimizations are done,
131 // remove them.
132 bool Changed = false;
133 CallInst *ToBeDeleted = nullptr;
134 for (Function &F : M)
135 for (auto &BB : F)
136 for (auto &I : BB) {
137 if (ToBeDeleted) {
138 ToBeDeleted->eraseFromParent();
139 ToBeDeleted = nullptr;
140 }
141
142 auto *Call = dyn_cast<CallInst>(Val: &I);
143 if (!Call)
144 continue;
145 auto *GV = dyn_cast<GlobalValue>(Val: Call->getCalledOperand());
146 if (!GV)
147 continue;
148 if (!GV->getName().starts_with(Prefix: "llvm.bpf.compare"))
149 continue;
150
151 Changed = true;
152 Value *Arg0 = Call->getArgOperand(i: 0);
153 Value *Arg1 = Call->getArgOperand(i: 1);
154 Value *Arg2 = Call->getArgOperand(i: 2);
155
156 auto OpVal = cast<ConstantInt>(Val: Arg0)->getValue().getZExtValue();
157 CmpInst::Predicate Opcode = (CmpInst::Predicate)OpVal;
158
159 auto *ICmp = new ICmpInst(Opcode, Arg1, Arg2);
160 ICmp->insertBefore(InsertPos: Call->getIterator());
161
162 Call->replaceAllUsesWith(V: ICmp);
163 ToBeDeleted = Call;
164 }
165 return Changed;
166}
167
168struct MinMaxSinkInfo {
169 ICmpInst *ICmp;
170 Value *Other;
171 ICmpInst::Predicate Predicate;
172 CallInst *MinMax;
173 ZExtInst *ZExt;
174 SExtInst *SExt;
175
176 MinMaxSinkInfo(ICmpInst *ICmp, Value *Other, ICmpInst::Predicate Predicate)
177 : ICmp(ICmp), Other(Other), Predicate(Predicate), MinMax(nullptr),
178 ZExt(nullptr), SExt(nullptr) {}
179};
180
181static bool sinkMinMaxInBB(BasicBlock &BB,
182 const std::function<bool(Instruction *)> &Filter) {
183 // Check if V is:
184 // (fn %a %b) or (ext (fn %a %b))
185 // Where:
186 // ext := sext | zext
187 // fn := smin | umin | smax | umax
188 auto IsMinMaxCall = [=](Value *V, MinMaxSinkInfo &Info) {
189 if (auto *ZExt = dyn_cast<ZExtInst>(Val: V)) {
190 V = ZExt->getOperand(i_nocapture: 0);
191 Info.ZExt = ZExt;
192 } else if (auto *SExt = dyn_cast<SExtInst>(Val: V)) {
193 V = SExt->getOperand(i_nocapture: 0);
194 Info.SExt = SExt;
195 }
196
197 auto *Call = dyn_cast<CallInst>(Val: V);
198 if (!Call)
199 return false;
200
201 auto *Called = dyn_cast<Function>(Val: Call->getCalledOperand());
202 if (!Called)
203 return false;
204
205 switch (Called->getIntrinsicID()) {
206 case Intrinsic::smin:
207 case Intrinsic::umin:
208 case Intrinsic::smax:
209 case Intrinsic::umax:
210 break;
211 default:
212 return false;
213 }
214
215 if (!Filter(Call))
216 return false;
217
218 Info.MinMax = Call;
219
220 return true;
221 };
222
223 auto ZeroOrSignExtend = [](IRBuilder<> &Builder, Value *V,
224 MinMaxSinkInfo &Info) {
225 if (Info.SExt) {
226 if (Info.SExt->getType() == V->getType())
227 return V;
228 return Builder.CreateSExt(V, DestTy: Info.SExt->getType());
229 }
230 if (Info.ZExt) {
231 if (Info.ZExt->getType() == V->getType())
232 return V;
233 return Builder.CreateZExt(V, DestTy: Info.ZExt->getType());
234 }
235 return V;
236 };
237
238 bool Changed = false;
239 SmallVector<MinMaxSinkInfo, 2> SinkList;
240
241 // Check BB for instructions like:
242 // insn := (icmp %a (fn ...)) | (icmp (fn ...) %a)
243 //
244 // Where:
245 // fn := min | max | (sext (min ...)) | (sext (max ...))
246 //
247 // Put such instructions to SinkList.
248 for (Instruction &I : BB) {
249 ICmpInst *ICmp = dyn_cast<ICmpInst>(Val: &I);
250 if (!ICmp)
251 continue;
252 if (!ICmp->isRelational())
253 continue;
254 MinMaxSinkInfo First(ICmp, ICmp->getOperand(i_nocapture: 1),
255 ICmpInst::getSwappedPredicate(pred: ICmp->getPredicate()));
256 MinMaxSinkInfo Second(ICmp, ICmp->getOperand(i_nocapture: 0), ICmp->getPredicate());
257 bool FirstMinMax = IsMinMaxCall(ICmp->getOperand(i_nocapture: 0), First);
258 bool SecondMinMax = IsMinMaxCall(ICmp->getOperand(i_nocapture: 1), Second);
259 if (!(FirstMinMax ^ SecondMinMax))
260 continue;
261 SinkList.push_back(Elt: FirstMinMax ? First : Second);
262 }
263
264 // Iterate SinkList and replace each (icmp ...) with corresponding
265 // `x < a && x < b` or similar expression.
266 for (auto &Info : SinkList) {
267 ICmpInst *ICmp = Info.ICmp;
268 CallInst *MinMax = Info.MinMax;
269 Intrinsic::ID IID = MinMax->getCalledFunction()->getIntrinsicID();
270 ICmpInst::Predicate P = Info.Predicate;
271 if (ICmpInst::isSigned(Pred: P) && IID != Intrinsic::smin &&
272 IID != Intrinsic::smax)
273 continue;
274
275 IRBuilder<> Builder(ICmp);
276 Value *X = Info.Other;
277 Value *A = ZeroOrSignExtend(Builder, MinMax->getArgOperand(i: 0), Info);
278 Value *B = ZeroOrSignExtend(Builder, MinMax->getArgOperand(i: 1), Info);
279 bool IsMin = IID == Intrinsic::smin || IID == Intrinsic::umin;
280 bool IsMax = IID == Intrinsic::smax || IID == Intrinsic::umax;
281 bool IsLess = ICmpInst::isLE(P) || ICmpInst::isLT(P);
282 bool IsGreater = ICmpInst::isGE(P) || ICmpInst::isGT(P);
283 assert(IsMin ^ IsMax);
284 assert(IsLess ^ IsGreater);
285
286 Value *Replacement;
287 Value *LHS = Builder.CreateICmp(P, LHS: X, RHS: A);
288 Value *RHS = Builder.CreateICmp(P, LHS: X, RHS: B);
289 if ((IsLess && IsMin) || (IsGreater && IsMax))
290 // x < min(a, b) -> x < a && x < b
291 // x > max(a, b) -> x > a && x > b
292 Replacement = Builder.CreateLogicalAnd(Cond1: LHS, Cond2: RHS);
293 else
294 // x > min(a, b) -> x > a || x > b
295 // x < max(a, b) -> x < a || x < b
296 Replacement = Builder.CreateLogicalOr(Cond1: LHS, Cond2: RHS);
297
298 if (SelectInst *ReplacementInst = dyn_cast<SelectInst>(Val: Replacement))
299 setExplicitlyUnknownBranchWeightsIfProfiled(I&: *ReplacementInst, DEBUG_TYPE);
300
301 ICmp->replaceAllUsesWith(V: Replacement);
302
303 Instruction *ToRemove[] = {ICmp, Info.ZExt, Info.SExt, MinMax};
304 for (Instruction *I : ToRemove)
305 if (I && I->use_empty())
306 I->eraseFromParent();
307
308 Changed = true;
309 }
310
311 return Changed;
312}
313
314// Do the following transformation:
315//
316// x < min(a, b) -> x < a && x < b
317// x > min(a, b) -> x > a || x > b
318// x < max(a, b) -> x < a || x < b
319// x > max(a, b) -> x > a && x > b
320//
321// Such patterns are introduced by LICM.cpp:hoistMinMax()
322// transformation and might lead to BPF verification failures for
323// older kernels.
324//
325// To minimize "collateral" changes only do it for icmp + min/max
326// calls when icmp is inside a loop and min/max is outside of that
327// loop.
328//
329// Verification failure happens when:
330// - RHS operand of some `icmp LHS, RHS` is replaced by some RHS1;
331// - verifier can recognize RHS as a constant scalar in some context;
332// - verifier can't recognize RHS1 as a constant scalar in the same
333// context;
334//
335// The "constant scalar" is not a compile time constant, but a register
336// that holds a scalar value known to verifier at some point in time
337// during abstract interpretation.
338//
339// See also:
340// https://lore.kernel.org/bpf/20230406164505.1046801-1-yhs@fb.com/
341static bool sinkMinMax(Module &M,
342 function_ref<LoopInfo &(Function &)> GetLoopInfo) {
343 bool Changed = false;
344
345 for (Function &F : M) {
346 if (F.isDeclaration())
347 continue;
348
349 LoopInfo &LI = GetLoopInfo(F);
350 for (Loop *L : LI)
351 for (BasicBlock *BB : L->blocks()) {
352 // Filter out instructions coming from the same loop
353 Loop *BBLoop = LI.getLoopFor(BB);
354 auto OtherLoopFilter = [&](Instruction *I) {
355 return LI.getLoopFor(BB: I->getParent()) != BBLoop;
356 };
357 Changed |= sinkMinMaxInBB(BB&: *BB, Filter: OtherLoopFilter);
358 }
359 }
360
361 return Changed;
362}
363
364void BPFCheckAndAdjustIRLegacy::getAnalysisUsage(AnalysisUsage &AU) const {
365 AU.addRequired<LoopInfoWrapperPass>();
366}
367
368static void unrollGEPLoad(CallInst *Call) {
369 auto [GEP, Load] = BPFPreserveStaticOffsetPass::reconstructLoad(Call);
370 GEP->insertBefore(InsertPos: Call->getIterator());
371 Load->insertBefore(InsertPos: Call->getIterator());
372 Call->replaceAllUsesWith(V: Load);
373 Call->eraseFromParent();
374}
375
376static void unrollGEPStore(CallInst *Call) {
377 auto [GEP, Store] = BPFPreserveStaticOffsetPass::reconstructStore(Call);
378 GEP->insertBefore(InsertPos: Call->getIterator());
379 Store->insertBefore(InsertPos: Call->getIterator());
380 Call->eraseFromParent();
381}
382
383static bool removeGEPBuiltinsInFunc(Function &F) {
384 SmallVector<CallInst *> GEPLoads;
385 SmallVector<CallInst *> GEPStores;
386 for (auto &BB : F)
387 for (auto &Insn : BB)
388 if (auto *Call = dyn_cast<CallInst>(Val: &Insn))
389 if (auto *Called = Call->getCalledFunction())
390 switch (Called->getIntrinsicID()) {
391 case Intrinsic::bpf_getelementptr_and_load:
392 GEPLoads.push_back(Elt: Call);
393 break;
394 case Intrinsic::bpf_getelementptr_and_store:
395 GEPStores.push_back(Elt: Call);
396 break;
397 }
398
399 if (GEPLoads.empty() && GEPStores.empty())
400 return false;
401
402 for_each(Range&: GEPLoads, F: unrollGEPLoad);
403 for_each(Range&: GEPStores, F: unrollGEPStore);
404
405 return true;
406}
407
408// Rewrites the following builtins:
409// - llvm.bpf.getelementptr.and.load
410// - llvm.bpf.getelementptr.and.store
411// As (load (getelementptr ...)) or (store (getelementptr ...)).
412static bool removeGEPBuiltins(Module &M) {
413 bool Changed = false;
414 for (auto &F : M)
415 Changed = removeGEPBuiltinsInFunc(F) || Changed;
416 return Changed;
417}
418
419// Wrap ToWrap with cast to address space zero:
420// - if ToWrap is a getelementptr,
421// wrap it's base pointer instead and return a copy;
422// - if ToWrap is Instruction, insert address space cast
423// immediately after ToWrap;
424// - if ToWrap is not an Instruction (function parameter
425// or a global value), insert address space cast at the
426// beginning of the Function F;
427// - use Cache to avoid inserting too many casts;
428static Value *aspaceWrapValue(DenseMap<Value *, Value *> &Cache, Function *F,
429 Value *ToWrap) {
430 auto It = Cache.find(Val: ToWrap);
431 if (It != Cache.end())
432 return It->getSecond();
433
434 if (auto *GEP = dyn_cast<GetElementPtrInst>(Val: ToWrap)) {
435 Value *Ptr = GEP->getPointerOperand();
436 Value *WrappedPtr = aspaceWrapValue(Cache, F, ToWrap: Ptr);
437 auto *GEPTy = cast<PointerType>(Val: GEP->getType());
438 auto *NewGEP = GEP->clone();
439 NewGEP->insertAfter(InsertPos: GEP->getIterator());
440 NewGEP->mutateType(Ty: PointerType::getUnqual(C&: GEPTy->getContext()));
441 NewGEP->setOperand(i: GEP->getPointerOperandIndex(), Val: WrappedPtr);
442 NewGEP->setName(GEP->getName());
443 Cache[ToWrap] = NewGEP;
444 return NewGEP;
445 }
446
447 IRBuilder IB(*F->getParent());
448 if (Instruction *InsnPtr = dyn_cast<Instruction>(Val: ToWrap))
449 IB.SetInsertPoint(*InsnPtr->getInsertionPointAfterDef());
450 else
451 IB.SetInsertPoint(F->getEntryBlock().getFirstInsertionPt());
452 auto *ASZeroPtrTy = IB.getPtrTy(AddrSpace: 0);
453 auto *ACast = IB.CreateAddrSpaceCast(V: ToWrap, DestTy: ASZeroPtrTy, Name: ToWrap->getName());
454 Cache[ToWrap] = ACast;
455 return ACast;
456}
457
458// Wrap a pointer operand OpNum of instruction I
459// with cast to address space zero
460static void aspaceWrapOperand(DenseMap<Value *, Value *> &Cache, Instruction *I,
461 unsigned OpNum) {
462 Value *OldOp = I->getOperand(i: OpNum);
463 if (OldOp->getType()->getPointerAddressSpace() == 0)
464 return;
465
466 Value *NewOp = aspaceWrapValue(Cache, F: I->getFunction(), ToWrap: OldOp);
467 I->setOperand(i: OpNum, Val: NewOp);
468 // Check if there are any remaining users of old GEP,
469 // delete those w/o users
470 for (;;) {
471 auto *OldGEP = dyn_cast<GetElementPtrInst>(Val: OldOp);
472 if (!OldGEP)
473 break;
474 if (!OldGEP->use_empty())
475 break;
476 OldOp = OldGEP->getPointerOperand();
477 OldGEP->eraseFromParent();
478 }
479}
480
481static Value *wrapPtrIfASNotZero(DenseMap<Value *, Value *> &Cache,
482 CallInst *CI, Value *P) {
483 if (auto *PTy = dyn_cast<PointerType>(Val: P->getType())) {
484 if (PTy->getAddressSpace() == 0)
485 return P;
486 }
487 return aspaceWrapValue(Cache, F: CI->getFunction(), ToWrap: P);
488}
489
490static Instruction *aspaceMemSet(Intrinsic::ID ID,
491 DenseMap<Value *, Value *> &Cache,
492 CallInst *CI) {
493 auto *MI = cast<MemIntrinsic>(Val: CI);
494 IRBuilder<> B(CI);
495
496 Value *OldDst = CI->getArgOperand(i: 0);
497 Value *NewDst = wrapPtrIfASNotZero(Cache, CI, P: OldDst);
498 if (OldDst == NewDst)
499 return nullptr;
500
501 // memset(new_dst, val, len, align, isvolatile, md)
502 Value *Val = CI->getArgOperand(i: 1);
503 Value *Len = CI->getArgOperand(i: 2);
504
505 auto *MS = cast<MemSetInst>(Val: CI);
506 MaybeAlign Align = MS->getDestAlign();
507 bool IsVolatile = MS->isVolatile();
508
509 if (ID == Intrinsic::memset)
510 return B.CreateMemSet(Ptr: NewDst, Val, Size: Len, Align, isVolatile: IsVolatile,
511 AAInfo: MI->getAAMetadata());
512 else
513 return B.CreateMemSetInline(Dst: NewDst, DstAlign: Align, Val, Size: Len, IsVolatile,
514 AAInfo: MI->getAAMetadata());
515}
516
517static Instruction *aspaceMemCpy(Intrinsic::ID ID,
518 DenseMap<Value *, Value *> &Cache,
519 CallInst *CI) {
520 auto *MI = cast<MemIntrinsic>(Val: CI);
521 IRBuilder<> B(CI);
522
523 Value *OldDst = CI->getArgOperand(i: 0);
524 Value *OldSrc = CI->getArgOperand(i: 1);
525 Value *NewDst = wrapPtrIfASNotZero(Cache, CI, P: OldDst);
526 Value *NewSrc = wrapPtrIfASNotZero(Cache, CI, P: OldSrc);
527 if (OldDst == NewDst && OldSrc == NewSrc)
528 return nullptr;
529
530 // memcpy(new_dst, dst_align, new_src, src_align, len, isvolatile, md)
531 Value *Len = CI->getArgOperand(i: 2);
532
533 auto *MT = cast<MemTransferInst>(Val: CI);
534 MaybeAlign DstAlign = MT->getDestAlign();
535 MaybeAlign SrcAlign = MT->getSourceAlign();
536 bool IsVolatile = MT->isVolatile();
537
538 return B.CreateMemTransferInst(IntrID: ID, Dst: NewDst, DstAlign, Src: NewSrc, SrcAlign, Size: Len,
539 isVolatile: IsVolatile, AAInfo: MI->getAAMetadata());
540}
541
542static Instruction *aspaceMemMove(DenseMap<Value *, Value *> &Cache,
543 CallInst *CI) {
544 auto *MI = cast<MemIntrinsic>(Val: CI);
545 IRBuilder<> B(CI);
546
547 Value *OldDst = CI->getArgOperand(i: 0);
548 Value *OldSrc = CI->getArgOperand(i: 1);
549 Value *NewDst = wrapPtrIfASNotZero(Cache, CI, P: OldDst);
550 Value *NewSrc = wrapPtrIfASNotZero(Cache, CI, P: OldSrc);
551 if (OldDst == NewDst && OldSrc == NewSrc)
552 return nullptr;
553
554 // memmove(new_dst, dst_align, new_src, src_align, len, isvolatile, md)
555 Value *Len = CI->getArgOperand(i: 2);
556
557 auto *MT = cast<MemTransferInst>(Val: CI);
558 MaybeAlign DstAlign = MT->getDestAlign();
559 MaybeAlign SrcAlign = MT->getSourceAlign();
560 bool IsVolatile = MT->isVolatile();
561
562 return B.CreateMemMove(Dst: NewDst, DstAlign, Src: NewSrc, SrcAlign, Size: Len, isVolatile: IsVolatile,
563 AAInfo: MI->getAAMetadata());
564}
565
566// Support for BPF address spaces:
567// - for each function in the module M, update pointer operand of
568// each memory access instruction (load/store/cmpxchg/atomicrmw)
569// or intrinsic call insns (memset/memcpy/memmove)
570// by casting it from non-zero address space to zero address space, e.g:
571//
572// (load (ptr addrspace (N) %p) ...)
573// -> (load (addrspacecast ptr addrspace (N) %p to ptr))
574//
575// - assign section with name .addr_space.N for globals defined in
576// non-zero address space N
577static bool insertASpaceCasts(Module &M) {
578 bool Changed = false;
579 for (Function &F : M) {
580 DenseMap<Value *, Value *> CastsCache;
581 for (BasicBlock &BB : F) {
582 for (Instruction &I : llvm::make_early_inc_range(Range&: BB)) {
583 unsigned PtrOpNum;
584
585 if (auto *LD = dyn_cast<LoadInst>(Val: &I)) {
586 PtrOpNum = LD->getPointerOperandIndex();
587 aspaceWrapOperand(Cache&: CastsCache, I: &I, OpNum: PtrOpNum);
588 continue;
589 }
590 if (auto *ST = dyn_cast<StoreInst>(Val: &I)) {
591 PtrOpNum = ST->getPointerOperandIndex();
592 aspaceWrapOperand(Cache&: CastsCache, I: &I, OpNum: PtrOpNum);
593 continue;
594 }
595 if (auto *CmpXchg = dyn_cast<AtomicCmpXchgInst>(Val: &I)) {
596 PtrOpNum = CmpXchg->getPointerOperandIndex();
597 aspaceWrapOperand(Cache&: CastsCache, I: &I, OpNum: PtrOpNum);
598 continue;
599 }
600 if (auto *RMW = dyn_cast<AtomicRMWInst>(Val: &I)) {
601 PtrOpNum = RMW->getPointerOperandIndex();
602 aspaceWrapOperand(Cache&: CastsCache, I: &I, OpNum: PtrOpNum);
603 continue;
604 }
605
606 auto *CI = dyn_cast<CallInst>(Val: &I);
607 if (!CI)
608 continue;
609
610 Function *Callee = CI->getCalledFunction();
611 if (!Callee || !Callee->isIntrinsic())
612 continue;
613
614 // Check memset/memcpy/memmove
615 Intrinsic::ID ID = Callee->getIntrinsicID();
616 bool IsSet = ID == Intrinsic::memset || ID == Intrinsic::memset_inline;
617 bool IsCpy = ID == Intrinsic::memcpy || ID == Intrinsic::memcpy_inline;
618 bool IsMove = ID == Intrinsic::memmove;
619 if (!IsSet && !IsCpy && !IsMove)
620 continue;
621
622 Instruction *New;
623 if (IsSet)
624 New = aspaceMemSet(ID, Cache&: CastsCache, CI);
625 else if (IsCpy)
626 New = aspaceMemCpy(ID, Cache&: CastsCache, CI);
627 else
628 New = aspaceMemMove(Cache&: CastsCache, CI);
629
630 if (!New)
631 continue;
632
633 I.replaceAllUsesWith(V: New);
634 New->takeName(V: &I);
635 I.eraseFromParent();
636 }
637 }
638 Changed |= !CastsCache.empty();
639 }
640 // Merge all globals within same address space into single
641 // .addr_space.<addr space no> section
642 for (GlobalVariable &G : M.globals()) {
643 if (G.getAddressSpace() == 0 || G.hasSection())
644 continue;
645 SmallString<16> SecName;
646 raw_svector_ostream OS(SecName);
647 OS << ".addr_space." << G.getAddressSpace();
648 G.setSection(SecName);
649 // Prevent having separate section for constants
650 G.setConstant(false);
651 }
652 return Changed;
653}
654
655// There is no range check in front of a jump table when the default of the
656// switch is unreachable. The compiler knows that the value is one of the cases,
657// e.g. the discriminant of an enum that was loaded from memory. The verifier
658// doesn't and rejects the load from the table.
659//
660// Anything can be the default of such a switch. Take the destination that most
661// cases go to and drop these cases. A switch that becomes compares needs as
662// many of them as before.
663static bool giveSwitchesDefault(Module &M) {
664 bool Changed = false;
665
666 for (Function &F : M) {
667 for (BasicBlock &BB : F) {
668 auto *SI = dyn_cast<SwitchInst>(Val: BB.getTerminator());
669
670 if (!SI || !SI->getNumCases() ||
671 !isa<UnreachableInst>(Val: *SI->getDefaultDest()->getFirstNonPHIIt()))
672 continue;
673
674 MapVector<BasicBlock *, unsigned> Cnt;
675 for (auto &Case : SI->cases())
676 ++Cnt[Case.getCaseSuccessor()];
677 BasicBlock *Dest = max_element(Range&: Cnt, C: [](const auto &A, const auto &B) {
678 return A.second < B.second;
679 })->first;
680
681 for (PHINode &Phi : Dest->phis())
682 Phi.addIncoming(V: Phi.getIncomingValueForBlock(BB: &BB), BB: &BB);
683 SI->getDefaultDest()->removePredecessor(Pred: &BB);
684 SI->setDefaultDest(Dest);
685
686 SwitchInstProfUpdateWrapper SIW(*SI);
687 for (auto It = SIW->case_begin(); It != SIW->case_end();) {
688 if (It->getCaseSuccessor() != Dest) {
689 ++It;
690 continue;
691 }
692 Dest->removePredecessor(Pred: &BB);
693 It = SIW.removeCase(I: It);
694 }
695 Changed = true;
696 }
697 }
698 return Changed;
699}
700
701static bool adjustIR(Module &M,
702 function_ref<LoopInfo &(Function &)> GetLoopInfo) {
703 bool Changed = removePassThroughBuiltin(M);
704 Changed = removeCompareBuiltin(M) || Changed;
705 Changed = sinkMinMax(M, GetLoopInfo) || Changed;
706 Changed = removeGEPBuiltins(M) || Changed;
707 Changed = insertASpaceCasts(M) || Changed;
708 Changed = giveSwitchesDefault(M) || Changed;
709 return Changed;
710}
711
712bool BPFCheckAndAdjustIRLegacy::runOnModule(Module &M) {
713 checkIR(M);
714 return adjustIR(M, GetLoopInfo: [&](Function &F) -> LoopInfo & {
715 return getAnalysis<LoopInfoWrapperPass>(F).getLoopInfo();
716 });
717}
718
719PreservedAnalyses BPFCheckAndAdjustIRPass::run(Module &M,
720 ModuleAnalysisManager &MAM) {
721 checkIR(M);
722 bool Changed = adjustIR(M, GetLoopInfo: [&](Function &F) -> LoopInfo & {
723 return MAM.getResult<FunctionAnalysisManagerModuleProxy>(IR&: M)
724 .getManager()
725 .getResult<LoopAnalysis>(IR&: F);
726 });
727 return Changed ? PreservedAnalyses::none().preserveSet<CFGAnalyses>()
728 : PreservedAnalyses::all();
729}
730