bpf: remove unnecessary truncate operation

For networking-type bpf program, it often needs to access
packet data. A context data structure is provided to the bpf
programs with two fields:
        u32 data;
        u32 data_end;
User can access these two fields with ctx->data and ctx->data_end.
During program verification process, the kernel verifier modifies
the bpf program with loading of actual pointer value from kernel
data structure.
    r = ctx->data      ===> r = actual data start ptr
    r = ctx->data_end  ===> r = actual data end ptr

A typical program accessing ctx->data like
    char *data_ptr = (char *)(long)ctx->data
will result in a 32-bit load followed by a zero extension.
Such an operation is combined into a single LDW in DAG combiner
as bpf LDW does zero extension automatically.

In cases like the below (which can be a result of global value numbering
and partial redundancy elimination before insn selection):
B1:
   u32 a = load-32-bit &ctx->data
   u64 pa = zext a
   ...
B2:
   u32 b = load-32-bit &ctx->data
   u64 pb = zext b
   ...
B3:
   u32 m = PHI(a, b)
   u64 pm = zext m

In B3, "pm = zext m" cannot be removed, which although is legal
from compiler perspective, will generate incorrect code after
kernel verification.

This patch recognizes this pattern and traces through PHI node
to see whether the operand of "zext m" is defined with LDWs or not.
If it is, the "zext m" itself can be removed.

The patch also recognizes the pattern where the load and use of
the load value not in the same basic block, where truncate operation
may be removed as well.

The patch handles 1-byte, 2-byte and 4-byte truncation.

Two test cases are added to verify the transformation happens properly
for the above code pattern.

Signed-off-by: Yonghong Song <yhs@fb.com>

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@306685 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 152 insertions, 0 deletions

diff --git a/test/CodeGen/BPF/remove_truncate_1.ll b/test/CodeGen/BPF/remove_truncate_1.ll
new file mode 100644
index 00000000000..65433853b9d
--- /dev/null
+++ b/test/CodeGen/BPF/remove_truncate_1.ll
@@ -0,0 +1,87 @@
+; RUN: llc < %s -march=bpf -verify-machineinstrs | FileCheck %s
+
+; Source code:
+; struct xdp_md {
+;   unsigned data;
+;   unsigned data_end;
+; };
+;
+; int gbl;
+; int xdp_dummy(struct xdp_md *xdp)
+; {
+;   char tmp;
+;   long addr;
+;
+;   if (gbl) {
+;     long addr1 = (long)xdp->data;
+;     tmp = *(char *)addr1;
+;     if (tmp == 1)
+;       return 3;
+;   } else {
+;     tmp = *(volatile char *)(long)xdp->data_end;
+;     if (tmp == 1)
+;       return 2;
+;   }
+;   addr = (long)xdp->data;
+;   tmp = *(volatile char *)addr;
+;   if (tmp == 0)
+;     return 1;
+;   return 0;
+; }
+
+%struct.xdp_md = type { i32, i32 }
+
+@gbl = common local_unnamed_addr global i32 0, align 4
+
+; Function Attrs: norecurse nounwind
+define i32 @xdp_dummy(%struct.xdp_md* nocapture readonly %xdp) local_unnamed_addr #0 {
+entry:
+  %0 = load i32, i32* @gbl, align 4
+  %tobool = icmp eq i32 %0, 0
+  br i1 %tobool, label %if.else, label %if.then
+
+if.then:                                          ; preds = %entry
+  %data = getelementptr inbounds %struct.xdp_md, %struct.xdp_md* %xdp, i64 0, i32 0
+  %1 = load i32, i32* %data, align 4
+  %conv = zext i32 %1 to i64
+  %2 = inttoptr i64 %conv to i8*
+  %3 = load i8, i8* %2, align 1
+  %cmp = icmp eq i8 %3, 1
+  br i1 %cmp, label %cleanup20, label %if.end12
+; CHECK:  r1 = *(u32 *)(r1 + 0)
+; CHECK:  r2 = *(u8 *)(r1 + 0)
+
+if.else:                                          ; preds = %entry
+  %data_end = getelementptr inbounds %struct.xdp_md, %struct.xdp_md* %xdp, i64 0, i32 1
+  %4 = load i32, i32* %data_end, align 4
+  %conv6 = zext i32 %4 to i64
+; CHECK:  r2 = *(u32 *)(r1 + 4)
+  %5 = inttoptr i64 %conv6 to i8*
+  %6 = load volatile i8, i8* %5, align 1
+  %cmp8 = icmp eq i8 %6, 1
+  br i1 %cmp8, label %cleanup20, label %if.else.if.end12_crit_edge
+
+if.else.if.end12_crit_edge:                       ; preds = %if.else
+  %data13.phi.trans.insert = getelementptr inbounds %struct.xdp_md, %struct.xdp_md* %xdp, i64 0, i32 0
+  %.pre = load i32, i32* %data13.phi.trans.insert, align 4
+  br label %if.end12
+; CHECK: r1 = *(u32 *)(r1 + 0)
+
+if.end12:                                         ; preds = %if.else.if.end12_crit_edge, %if.then
+  %7 = phi i32 [ %.pre, %if.else.if.end12_crit_edge ], [ %1, %if.then ]
+  %conv14 = zext i32 %7 to i64
+; CHECK-NOT: r1 <<= 32
+; CHECK-NOT: r1 >>= 32
+  %8 = inttoptr i64 %conv14 to i8*
+  %9 = load volatile i8, i8* %8, align 1
+; CHECK:  r1 = *(u8 *)(r1 + 0)
+  %cmp16 = icmp eq i8 %9, 0
+  %.28 = zext i1 %cmp16 to i32
+  br label %cleanup20
+
+cleanup20:                                        ; preds = %if.then, %if.end12, %if.else
+  %retval.1 = phi i32 [ 3, %if.then ], [ 2, %if.else ], [ %.28, %if.end12 ]
+  ret i32 %retval.1
+}
+
+attributes #0 = { norecurse nounwind }
diff --git a/test/CodeGen/BPF/remove_truncate_2.ll b/test/CodeGen/BPF/remove_truncate_2.ll
new file mode 100644
index 00000000000..979d820dd85
--- /dev/null
+++ b/test/CodeGen/BPF/remove_truncate_2.ll
@@ -0,0 +1,65 @@
+; RUN: llc < %s -march=bpf -verify-machineinstrs | FileCheck %s
+
+; Source code:
+; struct xdp_md {
+;   unsigned data;
+;   unsigned data_end;
+; };
+;
+; int gbl;
+; int xdp_dummy(struct xdp_md *xdp)
+; {
+;   char addr = *(char *)(long)xdp->data;
+;   if (gbl) {
+;     if (gbl == 1)
+;       return 1;
+;     if (addr == 1)
+;       return 3;
+;   } else if (addr == 0)
+;     return 2;
+;   return 0;
+; }
+
+%struct.xdp_md = type { i32, i32 }
+
+@gbl = common local_unnamed_addr global i32 0, align 4
+
+; Function Attrs: norecurse nounwind readonly
+define i32 @xdp_dummy(%struct.xdp_md* nocapture readonly %xdp) local_unnamed_addr #0 {
+entry:
+  %data = getelementptr inbounds %struct.xdp_md, %struct.xdp_md* %xdp, i64 0, i32 0
+  %0 = load i32, i32* %data, align 4
+  %conv = zext i32 %0 to i64
+  %1 = inttoptr i64 %conv to i8*
+  %2 = load i8, i8* %1, align 1
+; CHECK:  r1 = *(u32 *)(r1 + 0)
+; CHECK:  r1 = *(u8 *)(r1 + 0)
+  %3 = load i32, i32* @gbl, align 4
+  switch i32 %3, label %if.end [
+    i32 0, label %if.else
+    i32 1, label %cleanup
+  ]
+
+if.end:                                           ; preds = %entry
+  %cmp4 = icmp eq i8 %2, 1
+; CHECK:  r0 = 3
+; CHECK-NOT:  r1 &= 255
+; CHECK:  if r1 == 1 goto
+  br i1 %cmp4, label %cleanup, label %if.end13
+
+if.else:                                          ; preds = %entry
+  %cmp9 = icmp eq i8 %2, 0
+; CHECK:  r0 = 2
+; CHECK-NOT:  r1 &= 255
+; CHECK:  if r1 == 0 goto
+  br i1 %cmp9, label %cleanup, label %if.end13
+
+if.end13:                                         ; preds = %if.else, %if.end
+  br label %cleanup
+
+cleanup:                                          ; preds = %if.else, %if.end, %entry, %if.end13
+  %retval.0 = phi i32 [ 0, %if.end13 ], [ 1, %entry ], [ 3, %if.end ], [ 2, %if.else ]
+  ret i32 %retval.0
+}
+
+attributes #0 = { norecurse nounwind readonly }