Optimize pfmatch

[wingo]

Fixes #240.

[wingo]

The code that's being output still isn't hitting the optimizations that we need. Garr!

[wingo]

This is the IR coming out of the match expression from pfmatch.md:

{ "if",
  { "if",
    { ">=",
      "len",
      14 },
    { "=",
      { "[]",
        12,
        2 },
      8 },
    { "false" } },
  { "if",
    { "if",
      { ">=",
        "len",
        34 },
      { "if",
        { "=",
          { "[]",
            12,
            2 },
          8 },
        { "=",
          { "[]",
            26,
            4 },
          67305985 },
        { "false" } },
      { "false" } },
    { "call",
      "incoming_ip",
      14 },
    { "if",
      { "if",
        { ">=",
          "len",
          34 },
        { "if",
          { "=",
            { "[]",
              12,
              2 },
            8 },
          { "=",
            { "[]",
              30,
              4 },
            134678021 },
          { "false" } },
        { "false" } },
      { "call",
        "outgoing_ip",
        14 },
      { "call",
        "drop" } } },
  { "call",
    "forward" } }

[wingo]

I think the challenge is that we are restricting ourselves to shrinking optimizations -- we can duplicate "fail" expressions but not "call" expressions. That makes it hard for the algebraic optimizer to undo the nested "ifs". Not sure, but I would consider duplicating these calls -- it might even be the same number of traces, considering that branches cause trace duplication. Dunno.

[wingo]

Scratch, that what we need is this:

(if (if T A false) TAIL1 (if (if T B false) TAIL3 TAIL4))
-> (if T (if A TAIL1 (if B TAIL3)) TAIL4)

No code growth. I'll see what I can do.

[wingo]

The real transformation:

if (if T A false) B (if (if T C false) D E)
-> if T (if A B (if C D E)) E

As you can see E is duplicated. Hummm.

[wingo]

If I allow calls to duplicate, then I get this:

local cast = require("ffi").cast
return function(self,P,length)
   if length >= 14 then
      if cast("uint16_t*", P+12)[0] == 8 then
         if length >= 34 then
            if cast("uint32_t*", P+26)[0] == 67305985 then
               return self.incoming_ip(P, len, 14)
            else
               if cast("uint32_t*", P+30)[0] == 134678021 then
                  return self.outgoing_ip(P, len, 14)
               else
                  return self.drop(P, len)
               end
            end
         else
            return self.drop(P, len)
         end
      else
         return self.forward(P, len)
      end
   else
      return self.forward(P, len)
   end
end

There is a way to avoid the duplication though if B and D are tail expressions, will see what happens there.

[kbara]

Duplication of E is avoidable, starting from if T (if A B (if C D E)) E:

(if (T&A) B 
   (if (!T&!A&C) D E))

[wingo]

The way to avoid duplication goes like this:

if (if T A false) B (if (if T C false) D E)
-> if (if T (if A B (if C D false)) false) fail E

This works if B and D are tail expressions. The fail is unreachable. The results aren't great though:

local cast = require("ffi").cast
return function(self,P,length)
   if length < 14 then goto L5 end
   do
      if cast("uint16_t*", P+12)[0] ~= 8 then goto L5 end
      if length < 34 then goto L9 end
      do
         if cast("uint16_t*", P+12)[0] ~= 8 then goto L9 end
         if cast("uint32_t*", P+26)[0] == 67305985 then
            return self.incoming_ip(P, len, 14)
         end
         if cast("uint32_t*", P+30)[0] ~= 134678021 then goto L9 end
         return self.outgoing_ip(P, len, 14)
      end
::L9::
      return self.drop(P, len)
   end
::L5::
   return self.forward(P, len)
end

I expect we're bumping against the "scope tree is only a conservative approximation of a dominator tree" thing, so our CSE which runs over ANF isn't picking up things that it should. The AST looks like this:

{ "if",
  { "if",
    { ">=",
      "len",
      14 },
    { "=",
      { "[]",
        12,
        2 },
      8 },
    { "false" } },
  { "if",
    { "if",
      { ">=",
        "len",
        34 },
      { "if",
        { "=",
          { "[]",
            12,
            2 },
          8 },
        { "if",
          { "=",
            { "[]",
              26,
              4 },
            67305985 },
          { "call",
            "incoming_ip",
            14 },
          { "if",
            { "=",
              { "[]",
                30,
                4 },
              134678021 },
            { "call",
              "outgoing_ip",
              14 },
            { "false" } } },
        { "false" } },
      { "false" } },
    { "fail" },
    { "call",
      "drop" } },
  { "call",
    "forward" } }

[wingo]

kbara: as in many compiler ILs, we don't have "and" in this language, so unfortunately that transformation isn't valid. Also the point here is to get T dominating A, B, C, and D, to enable other optimizations and that transformation doesn't allow that.