Changes in BPFMIPeephole.cpp

437f9600 - [llvm] Call *set::insert without checking membership first (NFC)

Sat, 18 Jun 2022 17:22:05 +0000

[llvm] Call *set::insert without checking membership first (NFC) List of files: /llvm-project-15.0.7/llvm/lib/Target/BPF/BPFMIPeephole.cpp

989f1c72 - Cleanup codegen includes

Tue, 15 Mar 2022 09:54:19 +0000

Cleanup codegen includesThis is a (fixed) recommit of https://reviews.llvm.org/D121169after: 1061034926before: 1063332844Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-cleanupDifferential Revision: https://reviews.llvm.org/D121681 List of files: /llvm-project-15.0.7/llvm/lib/Target/BPF/BPFMIPeephole.cpp

a278250b - Revert "Cleanup codegen includes"

Thu, 10 Mar 2022 12:54:41 +0000

Revert "Cleanup codegen includes"This reverts commit 7f230feeeac8a67b335f52bd2e900a05c6098f20.Breaks CodeGenCUDA/link-device-bitcode.cu in check-clang,and many LLVM tests, see comments on https://reviews.llvm.org/D121169 List of files: /llvm-project-15.0.7/llvm/lib/Target/BPF/BPFMIPeephole.cpp

7f230fee - Cleanup codegen includes

Mon, 07 Mar 2022 23:25:52 +0000

Cleanup codegen includesafter: 1061034926before: 1063332844Differential Revision: https://reviews.llvm.org/D121169 List of files: /llvm-project-15.0.7/llvm/lib/Target/BPF/BPFMIPeephole.cpp

7e163afd - Remove redundant void arguments (NFC)

Sun, 02 Jan 2022 18:20:19 +0000

Remove redundant void arguments (NFC)Identified by modernize-redundant-void-arg. List of files: /llvm-project-15.0.7/llvm/lib/Target/BPF/BPFMIPeephole.cpp

51cdb780 - BPF: Fix a bug in peephole TRUNC elimination optimization

Tue, 02 Mar 2021 17:35:21 +0000

BPF: Fix a bug in peephole TRUNC elimination optimizationAndrei Matei reported a llvm11 core dump for his bpf program https://bugs.llvm.org/show_bug.cgi?id=48578The core dump happens in LiveVariables analysis phase. #4 0x00007fce54356bb0 __restore_rt #5 0x00007fce4d51785e llvm::LiveVariables::HandleVirtRegUse(unsigned int, llvm::MachineBasicBlock*, llvm::MachineInstr&) #6 0x00007fce4d519abe llvm::LiveVariables::runOnInstr(llvm::MachineInstr&, llvm::SmallVectorImpl&) #7 0x00007fce4d519ec6 llvm::LiveVariables::runOnBlock(llvm::MachineBasicBlock*, unsigned int) #8 0x00007fce4d51a4bf llvm::LiveVariables::runOnMachineFunction(llvm::MachineFunction&)The bug can be reproduced with llvm12 and latest trunk as well.Futher analysis shows that there is a bug in BPF peepholeTRUNC elimination optimization, which tries to removeunnecessary TRUNC operations (a <<= 32; a >>= 32).Specifically, the compiler did wrong transformation for thefollowing patterns: %1 = LDW ... %2 = SLL_ri %1, 32 %3 = SRL_ri %2, 32 ... %3 ... %4 = SRA_ri %2, 32 ... %4 ...The current transformation did not check how many uses of %2and did transformation like %1 = LDW ... ... %1 ... %4 = SRL_ri %2, 32 ... %4 ...and pseudo register %2 is used by not defined andcaused LiveVariables analysis core dump.To fix the issue, when traversing back from SRL_ri to SLL_ri,check to ensure SLL_ri has only one use. Otherwise, don'tdo transformation.Differential Revision: https://reviews.llvm.org/D97792 List of files: /llvm-project-15.0.7/llvm/lib/Target/BPF/BPFMIPeephole.cpp

3659559c - [BPF] Remove unnecessary MOV_32_64 instructions

Tue, 02 Jun 2020 07:47:18 +0000

[BPF] Remove unnecessary MOV_32_64 instructionsCommit 13f6c81c5d9a ("[BPF] simplify zero extensionwith MOV_32_64") tried to use MOV_32_64 instructionsinstead of lshift/rshift instructions for zero extension.This has the benefit to remove the number of instructionsand may help verifier too.But the same commit also removed the old MOV_32_64pruning as it deems unsafe as MOV_32_64 does have theside effect, zeroing out the top 32bit in the register.This caused the following failure in kernel selftesttest_cls_redirect.o. In linux kernel, we have struct __sk_buff { __u32 data; __u32 data_end; };The compiler will generate 32bit load for __sk_buff->dataand __sk_buff->data_end. But kernel verifier will actuallyloads an address (64bit address on 64bit kernel) to theresult register. In this particular example, the explicit zextwas not optimized away and destroyed top 32bitaddress and the verifier rejected the program : w2 = *(u32 *)(r1 + 76) ... r2 = w2 /* MOV_32_64: this will clear top 32bit */Currently, if the load and the zext are next to each other, theinstruction pattern match can actually capture this toavoid MOV_32_64, e.g., in BPFInstrInfo.td, we have def : Pat<(i64 (zextloadi32 ADDRri:$src)), (SUBREG_TO_REG (i64 0), (LDW32 ADDRri:$src), sub_32)>;However, if they are not next to each other, LDW32 andMOV_32_64 are generated, which may cause the above mentionedproblem.BPF Backend already tried to optimize away pattern mov_32_64 + lshift + rshiftCommit 13f6c81c5d9a may generate mov_32_64 not followed by shifts.This patch added optimization for only mov_32_64 too.Differential Revision: https://reviews.llvm.org/D81048 List of files: /llvm-project-15.0.7/llvm/lib/Target/BPF/BPFMIPeephole.cpp

13f6c81c - [BPF] simplify zero extension with MOV_32_64

Wed, 27 May 2020 18:18:16 +0000

[BPF] simplify zero extension with MOV_32_64The current pattern matching for zext results in the following code snippetbeing produced, w1 = w0 r1 <<= 32 r1 >>= 32Because BPF implementations require zero extension on 32bit loads thisboth adds a few extra unneeded instructions but also makes it a bitharder for the verifier to track the r1 register bounds. For example inthis verifier trace we see at the end of the snippet R2 offset is unknown.However, if we track this correctly we see w1 should have the same boundsas r8. R8 smax is less than U32 max value so a zero extend load should keepthe same value. Adding a max value of 800 (R8=inv(id=0,smax_value=800)) toan off=0, as seen in R7 should create a max offset of 800. However at theend of the snippet we note the R2 max offset is 0xffffFFFF. R0=inv(id=0,smax_value=800) R1_w=inv(id=0,umax_value=2147483647,var_off=(0x0; 0x7fffffff)) R6=ctx(id=0,off=0,imm=0) R7=map_value(id=0,off=0,ks=4,vs=1600,imm=0) R8_w=inv(id=0,smax_value=800,umax_value=4294967295,var_off=(0x0; 0xffffffff)) R9=inv800 R10=fp0 fp-8=mmmm???? 58: (1c) w9 -= w8 59: (bc) w1 = w8 60: (67) r1 <<= 32 61: (77) r1 >>= 32 62: (bf) r2 = r7 63: (0f) r2 += r1 64: (bf) r1 = r6 65: (bc) w3 = w9 66: (b7) r4 = 0 67: (85) call bpf_get_stack#67 R0=inv(id=0,smax_value=800) R1_w=ctx(id=0,off=0,imm=0) R2_w=map_value(id=0,off=0,ks=4,vs=1600,umax_value=4294967295,var_off=(0x0; 0xffffffff)) R3_w=inv(id=0,umax_value=800,var_off=(0x0; 0x3ff)) R4_w=inv0 R6=ctx(id=0,off=0,imm=0) R7=map_value(id=0,off=0,ks=4,vs=1600,imm=0) R8_w=inv(id=0,smax_value=800,umax_value=4294967295,var_off=(0x0; 0xffffffff)) R9_w=inv(id=0,umax_value=800,var_off=(0x0; 0x3ff)) R10=fp0 fp-8=mmmm????After this patch R1 bounds are not smashed by the <<=32 >>=32 shift and weget correct bounds on R2 umax_value=800.Further it reduces 3 insns to 1.Signed-off-by: John Fastabend Differential Revision: https://reviews.llvm.org/D73985 List of files: /llvm-project-15.0.7/llvm/lib/Target/BPF/BPFMIPeephole.cpp

a88cc204 - ProfileSummaryInfo.h - remove unnecessary includes. NFC

Fri, 10 Apr 2020 15:23:55 +0000

ProfileSummaryInfo.h - remove unnecessary includes. NFCRemove a number of includes that aren't necessary (nor are we relying on the remaining includes to provide the declarations), we just needed a llvm::Instruction forward declaration.This exposed a couple of source files that were implicitly replying on the includes for their use of llvm::SmallSet or std::set, requiring local includes to be added there instead. List of files: /llvm-project-15.0.7/llvm/lib/Target/BPF/BPFMIPeephole.cpp

9e6aa815 - [BPF] Fix a recursion bug in BPF Peephole ZEXT optimization

Fri, 22 Nov 2019 08:20:10 +0000

[BPF] Fix a recursion bug in BPF Peephole ZEXT optimizationCommit a0841dfe8594 ("[BPF] Fix a bug in peephole optimization")fixed a bug in peephole optimization. Recursion is introducedto handle COPY and PHI instructions.Unfortunately, multiple PHI instructions may form a cycleand this will cause infinite recursion, eventual segfault.For Commit a0841dfe8594, I indeed tried a few loops to ensurethat I won't see the recursion, but I did not try withcomplex control flows, which, as demonstrated with the test casein this patch, may introduce PHI cycles.This patch fixed the issue by introducing a set to remembervisited PHI instructions. This way, cycles can be properlydetected and handled.Differential Revision: https://reviews.llvm.org/D70586 List of files: /llvm-project-15.0.7/llvm/lib/Target/BPF/BPFMIPeephole.cpp

a0841dfe - [BPF] Fix a bug in peephole optimization

Wed, 20 Nov 2019 17:52:29 +0000

[BPF] Fix a bug in peephole optimizationOne of current peephole optimiations is to remove SLL/SRL ifthe sub register has been zero extended. This phase has two bugsand one limitations.First, for the physical subregister used in pseudo insn COPYlike below, it permits incorrect optimization. %0:gpr32 = COPY $w0 ... %4:gpr = MOV_32_64 %0:gpr32 %5:gpr = SLL_ri %4:gpr(tied-def 0), 32 %6:gpr = SRA_ri %5:gpr(tied-def 0), 32The $w0 could be from the return value of a previous function calland its upper 32-bit value might contain some non-zero values.The same applies to function arguments.Second, the current code may permits removing SLL/SRA like below: %0:gpr32 = COPY $w0 %1:gpr32 = COPY %0:gpr32 ... %4:gpr = MOV_32_64 %1:gpr32 %5:gpr = SLL_ri %4:gpr(tied-def 0), 32 %6:gpr = SRA_ri %5:gpr(tied-def 0), 32The reason is that it did not follow def-use chain to skip allintermediate 32bit-to-32bit COPY instructions.The current implementation is also very conservative for PHIinstructions. If any PHI insn component is another PHI or COPY insn,it will just permit SLL/SRA.This patch fixed the issue as follows: - During def/use chain traversal, if any physical register is read, SLL/SRA will be preserved as these physical registers are mostly from function return values or current function arguments. - Recursively visit all COPY and PHI instructions. List of files: /llvm-project-15.0.7/llvm/lib/Target/BPF/BPFMIPeephole.cpp

904cd3e0 - Prune a LegacyDivergenceAnalysis and MachineLoopInfo include each

Sat, 19 Oct 2019 01:31:09 +0000

Prune a LegacyDivergenceAnalysis and MachineLoopInfo include eachNow X86ISelLowering doesn't depend on many IR analyses.llvm-svn: 375320 List of files: /llvm-project-15.0.7/llvm/lib/Target/BPF/BPFMIPeephole.cpp

ec518510 - bpf: fix wrong truncation elimination when there is back-edge/loop

Wed, 16 Oct 2019 15:27:59 +0000

bpf: fix wrong truncation elimination when there is back-edge/loopCurrently, BPF backend is doing truncation elimination. If one truncationis performed on a value defined by narrow loads, then it could be redundantgiven BPF loads zero extend the destination register implicitly.When the definition of the truncated value is a merging value (PHI node)that could come from different code paths, then checks need to be done onall possible code paths.Above described optimization was introduced as r306685, however it doesn'twork when there is back-edge, for example when loop is used inside BPFcode.For example for the following code, a zero-extended value should be storedinto b[i], but the "and reg, 0xffff" is wrongly eliminated which thengenerates corrupted data.void cal1(unsigned short *a, unsigned long *b, unsigned int k){ unsigned short e; e = *a; for (unsigned int i = 0; i < k; i++) { b[i] = e; e = ~e; }}The reason is r306685 was trying to do the PHI node checks inside iselDAG2DAG phase, and the checks are done on MachineInstr. This is actuallywrong, because MachineInstr is being built during isel phase and theassociated information is not completed yet. A quick search shows nonetarget other than BPF is access MachineInstr info during isel phase.For an PHI node, when you reached it during isel phase, it may have allpredecessors linked, but not successors. It seems successors are linked toPHI node only when doing SelectionDAGISel::FinishBasicBlock and thishappens later than PreprocessISelDAG hook.Previously, BPF program doesn't allow loop, there is probably the reasonwhy this bug was not exposed.This patch therefore fixes the bug by the following approach: - The existing truncation elimination code and the associated "load_to_vreg_" records are removed. - Instead, implement truncation elimination using MachineSSA pass, this is where all information are built, and keep the pass together with other similar peephole optimizations inside BPFMIPeephole.cpp. Redundant move elimination logic is updated accordingly. - Unit testcase included + no compilation errors for kernel BPF selftest.Patch Review===Patch was sent to and reviewed by BPF community at: https://lore.kernel.org/bpfReported-by: David Beckett Reviewed-by: Yonghong Song Signed-off-by: Jiong Wang llvm-svn: 375007 List of files: /llvm-project-15.0.7/llvm/lib/Target/BPF/BPFMIPeephole.cpp

0c476111 - Apply llvm-prefer-register-over-unsigned from clang-tidy to LLVM

Thu, 15 Aug 2019 19:22:08 +0000

Apply llvm-prefer-register-over-unsigned from clang-tidy to LLVMSummary:This clang-tidy check is looking for unsigned integer variables whose initializerstarts with an implicit cast from llvm::Register and changes the type of thevariable to llvm::Register (dropping the llvm:: where possible).Partial reverts in:X86FrameLowering.cpp - Some functions return unsigned and arguably should be MCRegisterX86FixupLEAs.cpp - Some functions return unsigned and arguably should be MCRegisterX86FrameLowering.cpp - Some functions return unsigned and arguably should be MCRegisterHexagonBitSimplify.cpp - Function takes BitTracker::RegisterRef which appears to be unsigned&MachineVerifier.cpp - Ambiguous operator==() given MCRegister and const RegisterPPCFastISel.cpp - No Register::operator-=()PeepholeOptimizer.cpp - TargetInstrInfo::optimizeLoadInstr() takes an unsigned&MachineTraceMetrics.cpp - MachineTraceMetrics lacks a suitable constructorManual fixups in:ARMFastISel.cpp - ARMEmitLoad() now takes a Register& instead of unsigned&HexagonSplitDouble.cpp - Ternary operator was ambiguous between unsigned/RegisterHexagonConstExtenders.cpp - Has a local class named Register, used llvm::Register instead of Register.PPCFastISel.cpp - PPCEmitLoad() now takes a Register& instead of unsigned&Depends on D65919Reviewers: arsenm, bogner, craig.topper, RKSimonReviewed By: arsenmSubscribers: RKSimon, craig.topper, lenary, aemerson, wuzish, jholewinski, MatzeB, qcolombet, dschuff, jyknight, dylanmckay, sdardis, nemanjai, jvesely, wdng, nhaehnle, sbc100, jgravelle-google, kristof.beyls, hiraditya, aheejin, kbarton, fedor.sergeev, javed.absar, asb, rbar, johnrusso, simoncook, apazos, sabuasal, niosHD, jrtc27, MaskRay, zzheng, edward-jones, atanasyan, rogfer01, MartinMosbeck, brucehoult, the_o, tpr, PkmX, jocewei, jsji, Petar.Avramovic, asbirlea, Jim, s.egerton, llvm-commitsTags: #llvmDifferential Revision: https://reviews.llvm.org/D65962llvm-svn: 369041 List of files: /llvm-project-15.0.7/llvm/lib/Target/BPF/BPFMIPeephole.cpp

2bea69bf - Finish moving TargetRegisterInfo::isVirtualRegister() and friends to llvm::Register as started by r367614. NFC

Thu, 01 Aug 2019 23:27:28 +0000

Finish moving TargetRegisterInfo::isVirtualRegister() and friends to llvm::Register as started by r367614. NFCllvm-svn: 367633 List of files: /llvm-project-15.0.7/llvm/lib/Target/BPF/BPFMIPeephole.cpp

2946cd70 - Update the file headers across all of the LLVM projects in the monorepo

Sat, 19 Jan 2019 08:50:56 +0000

Update the file headers across all of the LLVM projects in the monorepoto reflect the new license.We understand that people may be surprised that we're moving the headerentirely to discuss the new license. We checked this carefully with theFoundation's lawyer and we believe this is the correct approach.Essentially, all code in the project is now made available by the LLVMproject under our new license, so you will see that the license headersinclude that license only. Some of our contributors have contributedcode under our old license, and accordingly, we have retained a copy ofour old license notice in the top-level files in each project andrepository.llvm-svn: 351636 List of files: /llvm-project-15.0.7/llvm/lib/Target/BPF/BPFMIPeephole.cpp

d34e60ca - Rename DEBUG macro to LLVM_DEBUG.

Mon, 14 May 2018 12:53:11 +0000

Rename DEBUG macro to LLVM_DEBUG. The DEBUG() macro is very generic so it might clash with other projects.The renaming was done as follows:- git grep -l 'DEBUG' | xargs sed -i 's/\bDEBUG\s\?(/LLVM_DEBUG(/g'- git diff -U0 master | ../clang/tools/clang-format/clang-format-diff.py -i -p1 -style LLVM- Manual change to APInt- Manually chage DOCS as regex doesn't match it.In the transition period the DEBUG() macro is still present and aliasedto the LLVM_DEBUG() one.Differential Revision: https://reviews.llvm.org/D43624llvm-svn: 332240 List of files: /llvm-project-15.0.7/llvm/lib/Target/BPF/BPFMIPeephole.cpp

82bf8bcb - bpf: Enhance debug information for peephole optimization passes

Tue, 13 Mar 2018 06:47:07 +0000

bpf: Enhance debug information for peephole optimization passesAdd more debug information for peephole optimization passes.These would only be enabled for debug version binary and could helpanalyzing why some optimization opportunities were missed.Signed-off-by: Jiong Wang Signed-off-by: Yonghong Song llvm-svn: 327371 List of files: /llvm-project-15.0.7/llvm/lib/Target/BPF/BPFMIPeephole.cpp

e91802f3 - bpf: New post-RA peephole optimization pass to eliminate bad RA codegen

Tue, 13 Mar 2018 06:47:06 +0000

bpf: New post-RA peephole optimization pass to eliminate bad RA codegenThis new pass eliminate identical move: MOV rA, rAThis is particularly possible to happen when sub-register supportenabled. The special type cast insn MOV_32_64 involves differentregister class on src (i32) and dst (i64), RA could generate uselessinstruction due to this.This pass also could serve as the bast for further post-RA optimization.Signed-off-by: Jiong Wang Signed-off-by: Yonghong Song llvm-svn: 327370 List of files: /llvm-project-15.0.7/llvm/lib/Target/BPF/BPFMIPeephole.cpp

1d28a759 - bpf: Support subregister definition check on PHI node

Tue, 13 Mar 2018 06:47:04 +0000

bpf: Support subregister definition check on PHI nodeThis patch relax the subregister definition check on Phi node.Previously, we just cancel the optimizatoin when the definition is Phinode while actually we could further check the definitions of incomingparameters of PHI node.This helps catch more elimination opportunities.Signed-off-by: Jiong Wang Signed-off-by: Yonghong Song llvm-svn: 327368 List of files: /llvm-project-15.0.7/llvm/lib/Target/BPF/BPFMIPeephole.cpp