Page MenuHomePhabricator

BPF: add a SimplifyCFG IR pass during generic Scalar/IPO optimization

Authored by yonghong-song on Aug 6 2020, 8:17 AM.



The following bpf linux kernel selftest failed with latest

$ ./test_progs -n 7/10
The sequence of 8193 jumps is too complex.
verification time 126272 usec
stack depth 320
processed 114799 insns (limit 1000000)
libbpf: failed to load object 'pyperf600_nounroll.o'
#7/10 pyperf600_nounroll.o:FAIL
#7 bpf_verif_scale:FAIL

After some investigation, I found the following llvm patch

is responsible. The patch disabled hoisting common instructions
in SimplifyCFG by default. Later on, the code changes and a
SimplifyCFG phase with hoisting on cannot do the work any more.

A test is provided to demonstrate the problem.
The IR before simplifyCFG looks like:

  %i.0 = phi i32 [ 0, %entry ], [ %inc, ]
  %cmp = icmp ult i32 %i.0, 6
  br i1 %cmp, label %for.body, label %for.cond.cleanup

  %2 = load i8*, i8** %frame_ptr, align 8, !tbaa !2
  %cmp2 = icmp eq i8* %2, null
  %conv = zext i1 %cmp2 to i32
  call void @llvm.lifetime.end.p0i8(i64 8, i8* nonnull %1) #3
  call void @llvm.lifetime.end.p0i8(i64 8, i8* nonnull %0) #3
  ret i32 %conv

  %3 = load i8*, i8** %frame_ptr, align 8, !tbaa !2
  %tobool.not = icmp eq i8* %3, null
  br i1 %tobool.not, label, label %land.lhs.true

The first two insns of for.cond.cleanup and for.body, load and
icmp, can be hoisted to for.cond block. With Patch D84108, the
optimization is delayed. But unfortunately, later on loop rotation
added addition phi nodes to for.body and hoisting cannot
be done any more.

Note such a hoisting is beneficial to bpf programs as
bpf verifier does path sensitive analysis and verification.
The hoisting preverts reloading from stack which will assume
conservative value and increase exploited insns. In this case,
it caused verifier failure.

To fix this problem, I added an IR pass from bpf target
to performance additional simplifycfg with hoisting common inst

Diff Detail

Event Timeline

yonghong-song created this revision.Aug 6 2020, 8:17 AM
Herald added a project: Restricted Project. · View Herald TranscriptAug 6 2020, 8:17 AM
yonghong-song requested review of this revision.Aug 6 2020, 8:17 AM

Hi, @lebedev.ri Since this patch is to fix a bpf regression caused by ([SimplifyCFG][LoopRotate] SimplifyCFG: disable common instruction hoisting by default, enable late in pipeline), I added you as a reviewer as well just in case you have a better idea of how to fix this particular issue. Thanks!

lebedev.ri resigned from this revision.Aug 6 2020, 8:39 AM

If that's what's works for BPF..

ast accepted this revision.Aug 6 2020, 10:48 AM

thanks for detailed analysis.

This revision is now accepted and ready to land.Aug 6 2020, 10:48 AM
This revision was landed with ongoing or failed builds.Aug 6 2020, 1:17 PM
This revision was automatically updated to reflect the committed changes.
thopre added a subscriber: thopre.Aug 6 2020, 3:36 PM

FYI, I've had the following linker error on an incremental error which disappear if I revert this commit:

_+0x70): undefined reference to `llvm::createCFGSimplificationPass(llvm::SimplifyCFGOptions, std::function<bool (llvm::Function const&)>)'
collect2: error: ld returned 1 exit status