On 05.12.2016 17:40, Edward Cree wrote: > On 02/12/16 19:25, Hannes Frederic Sowa wrote: >> On 02.12.2016 19:39, Alexei Starovoitov wrote: >>> Hannes, >>> Not too long ago you proposed a very interesting idea to add >>> support for bounded loops without adding any new bpf instructions and >>> changing llvm (which was way better than my 'rep' like instructions >>> I was experimenting with). I thought systemtap guys also wanted bounded >>> loops and you were cooperating on the design, so I gave up on my work and >>> was expecting an imminent patch from you. I guess it sounds like you know >>> believe that bounded loops are impossible or I misunderstand your statement >>> ? >> Your argument was that it would need a new verifier as the current first >> pass checks that we indeed can lay out the basic blocks as a DAG which >> the second pass depends on. This would be violated. > I may be completely mistaken here, but can't the verifier unroll the loop 'for > verification' without it actually being unrolled in the program? > I.e., any "proof that the loop terminates" should translate into "rewrite of > the directed graph to make it a DAG, possibly duplicating a lot of insns", and > you feed the rewritten graph to the verifier, while using the original loopy > version as the actual program to store and later execute. > Then the verifier happily checks things like array indices being valid, > without > having to know about the bounded loops.
That is what is already happening. E.g. __builtin_memset is expanded up to 128 rounds (which is a lot) but at some point llvm doesn't do enoug unrolling of that. The BPF target configures that in http://llvm.org/docs/doxygen/html/BPFISelLowering_8cpp_source.html on line 166-169. Bye, Hannes
