search

Igalia / pflua

Packet filtering in Lua
Other
313 stars 39 forks source link

Fold associative binops more aggresively #220

Closed mpeterv closed 9 years ago

mpeterv commented 9 years ago

This change allows associative binop folding to always work if an expression tree contains at least two numbers. E.g. (A + C1) + (B + C2) now folds to (A + B) + (C1 + C2).

This improves code generated for #215: 517 lines -> 472 lines, 270 arithmetic ops (number of pluses) -> 187 ops.

local lshift = require("bit").lshift
local band = require("bit").band
local cast = require("ffi").cast
return function(P,length)
   if length < 14 then return false end
   local var1 = cast("uint16_t*", P+12)[0]
   if var1 == 8 then
      if length < 54 then return false end
      if P[23] ~= 6 then return false end
      if band(cast("uint16_t*", P+20)[0],65311) ~= 0 then return false end
      local var7 = lshift(band(P[14],15),2)
      if (var7 + 28) > length then return false end
      if band(P[(var7 + 27)],2) == 0 then return false end
      local var18 = (var7 + 35)
      if var18 > length then return false end
      local var23 = P[(var7 + 34)]
      if var23 == 3 then return true end
      if var23 == 1 then goto L21 end
      do
         if (var7 + 36) > length then return false end
         local var40 = P[var18]
         local var41 = (var7 + var40)
         local var42 = (var41 + 35)
         if var42 > length then return false end
         local var53 = P[(var41 + 34)]
         if var53 == 3 then return true end
         if var53 == 1 then goto L31 end
         do
            if (var41 + 36) > length then return false end
            local var94 = (var40 + P[var42])
            local var95 = (var7 + var94)
            local var96 = (var95 + 35)
            if var96 > length then return false end
            local var119 = P[(var95 + 34)]
            if var119 == 3 then return true end
            if var119 == 1 then goto L41 end
            do
               if (var95 + 36) > length then return false end
               local var208 = (var94 + P[var96])
               local var209 = (var7 + var208)
               local var210 = (var209 + 35)
               if var210 > length then return false end
               local var257 = P[(var209 + 34)]
               if var257 == 3 then return true end
               if var257 == 1 then goto L51 end
               do
                  if (var209 + 36) > length then return false end
                  local var442 = (var208 + P[var210])
                  local var443 = (var7 + var442)
                  local var444 = (var443 + 35)
                  if var444 > length then return false end
                  local var539 = P[(var443 + 34)]
                  if var539 == 3 then return true end
                  if var539 == 1 then goto L61 end
                  do
                     if (var443 + 36) > length then return false end
                     local var917 = (var7 + (var442 + P[var444]))
                     if (var917 + 35) > length then return false end
                     if P[(var917 + 34)] == 3 then return true end
                     goto L61
                  end
::L61::
                  if var539 ~= 1 then goto L51 end
                  if (var443 + 36) > length then return false end
                  if P[var444] == 3 then return true end
                  goto L51
               end
::L51::
               if var257 ~= 1 then goto L41 end
               local var1486 = (var209 + 36)
               if var1486 > length then return false end
               local var1533 = P[var210]
               if var1533 == 3 then return true end
               if var1533 == 1 then goto L79 end
               do
                  if (var209 + 37) > length then return false end
                  local var1719 = (var7 + (var208 + P[var1486]))
                  if (var1719 + 36) > length then return false end
                  if P[(var1719 + 35)] == 3 then return true end
                  goto L79
               end
::L79::
               if var1533 ~= 1 then goto L41 end
               if (var209 + 37) > length then return false end
               if P[var1486] == 3 then return true end
               goto L41
            end
::L41::
            if var119 ~= 1 then goto L31 end
            local var2000 = (var95 + 36)
            if var2000 > length then return false end
            local var2023 = P[var96]
            if var2023 == 3 then return true end
            if var2023 == 1 then goto L97 end
            do
               if (var95 + 37) > length then return false end
               local var2112 = (var94 + P[var2000])
               local var2113 = (var7 + var2112)
               local var2114 = (var2113 + 36)
               if var2114 > length then return false end
               local var2161 = P[(var2113 + 35)]
               if var2161 == 3 then return true end
               if var2161 == 1 then goto L107 end
               do
                  if (var2113 + 37) > length then return false end
                  local var2347 = (var7 + (var2112 + P[var2114]))
                  if (var2347 + 36) > length then return false end
                  if P[(var2347 + 35)] == 3 then return true end
                  goto L107
               end
::L107::
               if var2161 ~= 1 then goto L97 end
               if (var2113 + 37) > length then return false end
               if P[var2114] == 3 then return true end
               goto L97
            end
::L97::
            if var2023 ~= 1 then goto L31 end
            local var2628 = (var95 + 37)
            if var2628 > length then return false end
            local var2651 = P[var2000]
            if var2651 == 3 then return true end
            if var2651 == 1 then goto L125 end
            do
               if (var95 + 38) > length then return false end
               local var2741 = (var7 + (var94 + P[var2628]))
               if (var2741 + 37) > length then return false end
               if P[(var2741 + 36)] == 3 then return true end
               goto L125
            end
::L125::
            if var2651 ~= 1 then goto L31 end
            if (var95 + 38) > length then return false end
            if P[var2628] == 3 then return true end
            goto L31
         end
::L31::
         if var53 ~= 1 then goto L21 end
         local var2878 = (var41 + 36)
         if var2878 > length then return false end
         local var2889 = P[var42]
         if var2889 == 3 then return true end
         if var2889 == 1 then goto L143 end
         do
            if (var41 + 37) > length then return false end
            local var2930 = (var40 + P[var2878])
            local var2931 = (var7 + var2930)
            local var2932 = (var2931 + 36)
            if var2932 > length then return false end
            local var2955 = P[(var2931 + 35)]
            if var2955 == 3 then return true end
            if var2955 == 1 then goto L153 end
            do
               if (var2931 + 37) > length then return false end
               local var3044 = (var2930 + P[var2932])
               local var3045 = (var7 + var3044)
               local var3046 = (var3045 + 36)
               if var3046 > length then return false end
               local var3093 = P[(var3045 + 35)]
               if var3093 == 3 then return true end
               if var3093 == 1 then goto L163 end
               do
                  if (var3045 + 37) > length then return false end
                  local var3279 = (var7 + (var3044 + P[var3046]))
                  if (var3279 + 36) > length then return false end
                  if P[(var3279 + 35)] == 3 then return true end
                  goto L163
               end
::L163::
               if var3093 ~= 1 then goto L153 end
               if (var3045 + 37) > length then return false end
               if P[var3046] == 3 then return true end
               goto L153
            end
::L153::
            if var2955 ~= 1 then goto L143 end
            local var3560 = (var2931 + 37)
            if var3560 > length then return false end
            local var3583 = P[var2932]
            if var3583 == 3 then return true end
            if var3583 == 1 then goto L181 end
            do
               if (var2931 + 38) > length then return false end
               local var3673 = (var7 + (var2930 + P[var3560]))
               if (var3673 + 37) > length then return false end
               if P[(var3673 + 36)] == 3 then return true end
               goto L181
            end
::L181::
            if var3583 ~= 1 then goto L143 end
            if (var2931 + 38) > length then return false end
            if P[var3560] == 3 then return true end
            goto L143
         end
::L143::
         if var2889 ~= 1 then goto L21 end
         local var3810 = (var41 + 37)
         if var3810 > length then return false end
         local var3821 = P[var2878]
         if var3821 == 3 then return true end
         if var3821 == 1 then goto L199 end
         do
            if (var41 + 38) > length then return false end
            local var3862 = (var40 + P[var3810])
            local var3863 = (var7 + var3862)
            local var3864 = (var3863 + 37)
            if var3864 > length then return false end
            local var3887 = P[(var3863 + 36)]
            if var3887 == 3 then return true end
            if var3887 == 1 then goto L209 end
            do
               if (var3863 + 38) > length then return false end
               local var3977 = (var7 + (var3862 + P[var3864]))
               if (var3977 + 37) > length then return false end
               if P[(var3977 + 36)] == 3 then return true end
               goto L209
            end
::L209::
            if var3887 ~= 1 then goto L199 end
            if (var3863 + 38) > length then return false end
            if P[var3864] == 3 then return true end
            goto L199
         end
::L199::
         if var3821 ~= 1 then goto L21 end
         local var4114 = (var41 + 38)
         if var4114 > length then return false end
         local var4125 = P[var3810]
         if var4125 == 3 then return true end
         if var4125 == 1 then goto L227 end
         do
            if (var41 + 39) > length then return false end
            local var4167 = (var7 + (var40 + P[var4114]))
            if (var4167 + 38) > length then return false end
            if P[(var4167 + 37)] == 3 then return true end
            goto L227
         end
::L227::
         if var4125 ~= 1 then goto L21 end
         if (var41 + 39) > length then return false end
         if P[var4114] == 3 then return true end
         goto L21
      end
::L21::
      if var23 ~= 1 then return false end
      local var4232 = (var7 + 36)
      if var4232 > length then return false end
      local var4237 = P[var18]
      if var4237 == 3 then return true end
      if var4237 == 1 then goto L245 end
      do
         if (var7 + 37) > length then return false end
         local var4254 = P[var4232]
         local var4255 = (var7 + var4254)
         local var4256 = (var4255 + 36)
         if var4256 > length then return false end
         local var4267 = P[(var4255 + 35)]
         if var4267 == 3 then return true end
         if var4267 == 1 then goto L255 end
         do
            if (var4255 + 37) > length then return false end
            local var4308 = (var4254 + P[var4256])
            local var4309 = (var7 + var4308)
            local var4310 = (var4309 + 36)
            if var4310 > length then return false end
            local var4333 = P[(var4309 + 35)]
            if var4333 == 3 then return true end
            if var4333 == 1 then goto L265 end
            do
               if (var4309 + 37) > length then return false end
               local var4422 = (var4308 + P[var4310])
               local var4423 = (var7 + var4422)
               local var4424 = (var4423 + 36)
               if var4424 > length then return false end
               local var4471 = P[(var4423 + 35)]
               if var4471 == 3 then return true end
               if var4471 == 1 then goto L275 end
               do
                  if (var4423 + 37) > length then return false end
                  local var4657 = (var7 + (var4422 + P[var4424]))
                  if (var4657 + 36) > length then return false end
                  if P[(var4657 + 35)] == 3 then return true end
                  goto L275
               end
::L275::
               if var4471 ~= 1 then goto L265 end
               if (var4423 + 37) > length then return false end
               if P[var4424] == 3 then return true end
               goto L265
            end
::L265::
            if var4333 ~= 1 then goto L255 end
            local var4938 = (var4309 + 37)
            if var4938 > length then return false end
            local var4961 = P[var4310]
            if var4961 == 3 then return true end
            if var4961 == 1 then goto L293 end
            do
               if (var4309 + 38) > length then return false end
               local var5051 = (var7 + (var4308 + P[var4938]))
               if (var5051 + 37) > length then return false end
               if P[(var5051 + 36)] == 3 then return true end
               goto L293
            end
::L293::
            if var4961 ~= 1 then goto L255 end
            if (var4309 + 38) > length then return false end
            if P[var4938] == 3 then return true end
            goto L255
         end
::L255::
         if var4267 ~= 1 then goto L245 end
         local var5188 = (var4255 + 37)
         if var5188 > length then return false end
         local var5199 = P[var4256]
         if var5199 == 3 then return true end
         if var5199 == 1 then goto L311 end
         do
            if (var4255 + 38) > length then return false end
            local var5240 = (var4254 + P[var5188])
            local var5241 = (var7 + var5240)
            local var5242 = (var5241 + 37)
            if var5242 > length then return false end
            local var5265 = P[(var5241 + 36)]
            if var5265 == 3 then return true end
            if var5265 == 1 then goto L321 end
            do
               if (var5241 + 38) > length then return false end
               local var5355 = (var7 + (var5240 + P[var5242]))
               if (var5355 + 37) > length then return false end
               if P[(var5355 + 36)] == 3 then return true end
               goto L321
            end
::L321::
            if var5265 ~= 1 then goto L311 end
            if (var5241 + 38) > length then return false end
            if P[var5242] == 3 then return true end
            goto L311
         end
::L311::
         if var5199 ~= 1 then goto L245 end
         local var5492 = (var4255 + 38)
         if var5492 > length then return false end
         local var5503 = P[var5188]
         if var5503 == 3 then return true end
         if var5503 == 1 then goto L339 end
         do
            if (var4255 + 39) > length then return false end
            local var5545 = (var7 + (var4254 + P[var5492]))
            if (var5545 + 38) > length then return false end
            if P[(var5545 + 37)] == 3 then return true end
            goto L339
         end
::L339::
         if var5503 ~= 1 then goto L245 end
         if (var4255 + 39) > length then return false end
         if P[var5492] == 3 then return true end
         goto L245
      end
::L245::
      if var4237 ~= 1 then return false end
      local var5610 = (var7 + 37)
      if var5610 > length then return false end
      local var5615 = P[var4232]
      if var5615 == 3 then return true end
      if var5615 == 1 then goto L357 end
      do
         if (var7 + 38) > length then return false end
         local var5632 = P[var5610]
         local var5633 = (var7 + var5632)
         local var5634 = (var5633 + 37)
         if var5634 > length then return false end
         local var5645 = P[(var5633 + 36)]
         if var5645 == 3 then return true end
         if var5645 == 1 then goto L367 end
         do
            if (var5633 + 38) > length then return false end
            local var5686 = (var5632 + P[var5634])
            local var5687 = (var7 + var5686)
            local var5688 = (var5687 + 37)
            if var5688 > length then return false end
            local var5711 = P[(var5687 + 36)]
            if var5711 == 3 then return true end
            if var5711 == 1 then goto L377 end
            do
               if (var5687 + 38) > length then return false end
               local var5801 = (var7 + (var5686 + P[var5688]))
               if (var5801 + 37) > length then return false end
               if P[(var5801 + 36)] == 3 then return true end
               goto L377
            end
::L377::
            if var5711 ~= 1 then goto L367 end
            if (var5687 + 38) > length then return false end
            if P[var5688] == 3 then return true end
            goto L367
         end
::L367::
         if var5645 ~= 1 then goto L357 end
         local var5938 = (var5633 + 38)
         if var5938 > length then return false end
         local var5949 = P[var5634]
         if var5949 == 3 then return true end
         if var5949 == 1 then goto L395 end
         do
            if (var5633 + 39) > length then return false end
            local var5991 = (var7 + (var5632 + P[var5938]))
            if (var5991 + 38) > length then return false end
            if P[(var5991 + 37)] == 3 then return true end
            goto L395
         end
::L395::
         if var5949 ~= 1 then goto L357 end
         if (var5633 + 39) > length then return false end
         if P[var5938] == 3 then return true end
         goto L357
      end
::L357::
      if var5615 ~= 1 then return false end
      local var6056 = (var7 + 38)
      if var6056 > length then return false end
      local var6061 = P[var5610]
      if var6061 == 3 then return true end
      if var6061 == 1 then goto L413 end
      do
         if (var7 + 39) > length then return false end
         local var6078 = P[var6056]
         local var6079 = (var7 + var6078)
         local var6080 = (var6079 + 38)
         if var6080 > length then return false end
         local var6091 = P[(var6079 + 37)]
         if var6091 == 3 then return true end
         if var6091 == 1 then goto L423 end
         do
            if (var6079 + 39) > length then return false end
            local var6133 = (var7 + (var6078 + P[var6080]))
            if (var6133 + 38) > length then return false end
            if P[(var6133 + 37)] == 3 then return true end
            goto L423
         end
::L423::
         if var6091 ~= 1 then goto L413 end
         if (var6079 + 39) > length then return false end
         if P[var6080] == 3 then return true end
         goto L413
      end
::L413::
      if var6061 ~= 1 then return false end
      local var6198 = (var7 + 39)
      if var6198 > length then return false end
      local var6203 = P[var6056]
      if var6203 == 3 then return true end
      if var6203 == 1 then goto L441 end
      do
         if (var7 + 40) > length then return false end
         local var6221 = (var7 + P[var6198])
         if (var6221 + 39) > length then return false end
         if P[(var6221 + 38)] == 3 then return true end
         goto L441
      end
::L441::
      if var6203 ~= 1 then return false end
      if (var7 + 40) > length then return false end
      return P[var6198] == 3
   else
      if var1 ~= 56710 then return false end
      if length < 54 then return false end
      local var6249 = P[20]
      return false
   end
end
kbara commented 9 years ago

LGTM. The associativity/commutativity logic seems sound, and it caused no problems for the automatically-generated tests. There were no changes under doc/ from this pull request ( @andywingo ). Waiting for a second review. Thank you, @mpeterv !

dpino commented 9 years ago

LGTM but I'd leave it to @andywingo for a final review. He knows this part of the code the most and I believe he would like to review it.