[CSSPGO][llvm-profgen] Ignore LBR records after interrupt transition

[hoy]

Summary

If we have seen an inwards transition from external code to internal code, but not a following outwards transition, the inwards transition is likely due to interrupt which is usually unpaired. Ignore current and subsequent entries since they are likely from an unrelated pre-interrupt context.

LBR records from different interrupt context are unrelated and they should not be mixed together. Currenlty the OS does this for task-scheduling interrupt but not for all interrupts.

[wenlei]

llvm/tools/llvm-profgen/PerfReader.cpp

457

What do you mean by unrelated pre-interrupt context? After interrupt is handled, execution is supposed to continue from the same spot. If we only missed one of the interrupt transition branch, the pre-interrupt IP should be right before the current IP. If that's not the case, then what's missing is more than a transition branch from the pair - it then sounds like the problem is LBR buffer is not being cleared on context switch.

[hoy]

llvm/tools/llvm-profgen/PerfReader.cpp

457

Yes, LBR buffer is not cleared for all interrupts but task-scheduling interrupt. Interrupt does not reflect a normal execution flow. Pre-interrupt code and post-resume code should have the same context. For task-scheduling interrupt, the OS knows how to regroup them so that we have consistent execution flow in LBR for a single thread. Looks like it doesn't do that for other type of interrupts. We are working around here to break the LBR trace at the interrupt point.

On the second thought, we should also break at the resume point.

[wenlei]

llvm/tools/llvm-profgen/PerfReader.cpp

457

Yes, LBR buffer is not cleared for all interrupts but task-scheduling interrupt.

I'm not sure if this is expected. My understanding of the expectation is that, since save/restore LBR states could be expensive, we don't need to do that for all interrupts and context switches. But the fall back is to clear LBR buffer, with that we shouldn't see inconsistent LBR entries. We never saw such inconsistent LBR on windows, and we also never saw that on linux until today. We need to follow up with kernel folks.

On the second thought, we should also break at the resume point.

As a workaround, yes we need to bail out for both case.

486–487

Would be clearer if we do this:

if (IsOutwards) {
 ...
}
else {
  // Not finding outward transition after seeing an inward transition ...
  if (PrevTrDst)
     break;
}

[hoy]

llvm/tools/llvm-profgen/PerfReader.cpp

486–487

Looks better, thanks.

[hoy]

Addressing back-from-interrupt case.

[wenlei]

lgtm, thanks.

[wlei]

LGTM, thanks!

llvm/test/tools/llvm-profgen/Inputs/cs-interrupt.perfscript

+PERF_RECORD_MMAP2 2854748/2854748: [0x400000(0x1000) @ 0 00:1d 123291722 526021]: r-xp /home/noinline-cs-noprobe.perfbin
+
+            4005dc
+            400634
+            400684
+      7f68c5788793
+ 0x4005c8/0x4005dc/P/-/-/0  0x40062f/0x4005b0/P/-/-/0  0x400645/0x4005ff/P/-/-/0  0x400637/0x400645/P/-/-/0  0x4005e9/0x400634/P/-/-/0  0x4005d7/0x4005e5/P/-/-/0  0x40062f/0x4005b0/P/-/-/0  0x400645/0x4005ff/P/-/-/0  0x400637/0x400645/P/-/-/0  0x4005e9/0x400634/P/-/-/0  0x4005d7/0x4005e5/P/-/-/0  0x40062f/0x4005b0/P/-/-/0  0x400645/0x4005ff/P/-/-/0  0x400637/0x400645/P/-/-/0  0xffffffff81c009d0/0x400634/P/-/-/0  0x40048a/0x40048e/P/-/-/0
+
+
+            4005dc
+            400634
+            400684
+      7f68c5788793
+ 0x4005c8/0x4005dc/P/-/-/0  0x40062f/0x4005b0/P/-/-/0  0x400645/0x4005ff/P/-/-/0  0x400637/0x400645/P/-/-/0  0x4005e9/0x400634/P/-/-/0  0x4005d7/0x4005e5/P/-/-/0  0x40062f/0x4005b0/P/-/-/0  0x400645/0x4005ff/P/-/-/0  0x400637/0x400645/P/-/-/0  0x4005e9/0x400634/P/-/-/0  0x4005d7/0x4005e5/P/-/-/0  0x400634/0xffffffff81c009d0/P/-/-/0 0x40062f/0x4005b0/P/-/-/0  0x400645/0x4005ff/P/-/-/0  0x400637/0x400645/P/-/-/0  0x40048a/0x40048e/P/-/-/0
+
+// Transition 0xffffffff81c009d0/0x400634 is due to interrupt. Records after it, i.e, 0x40048a/0x40048e, should be ignored to avoid bogus instruction ranges.

llvm/test/tools/llvm-profgen/cs-interrupt.test

+; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/cs-interrupt.perfscript --binary=%S/Inputs/noinline-cs-noprobe.perfbin --output=%t --show-unwinder-output --profile-summary-cold-count=0 | FileCheck %s --check-prefix=CHECK-UNWINDER
+; RUN: FileCheck %s --input-file %t
+
+; CHECK:[main:1 @ foo]:88:0
+; CHECK: 2: 5
+; CHECK: 3: 5 bar:5
+; CHECK:[main:1 @ foo:3 @ bar]:74:5
+; CHECK: 0: 5
+; CHECK: 1: 5
+; CHECK: 2: 3
+; CHECK: 5: 4
+
+; CHECK-UNWINDER: Binary(noinline-cs-noprobe.perfbin)'s Range Counter:
+; CHECK-UNWINDER: main:1 @ foo
+; CHECK-UNWINDER:   (5ff, 62f): 5
+; CHECK-UNWINDER:   (634, 637): 4
+; CHECK-UNWINDER:   (645, 645): 5
+; CHECK-UNWINDER: main:1 @ foo:3 @ bar
+; CHECK-UNWINDER:   (5b0, 5c8): 2
+; CHECK-UNWINDER:   (5b0, 5d7): 3
+; CHECK-UNWINDER:   (5e5, 5e9): 4
+
+; CHECK-UNWINDER: Binary(noinline-cs-noprobe.perfbin)'s Branch Counter:
+; CHECK-UNWINDER: main:1 @ foo
+; CHECK-UNWINDER:   (62f, 5b0): 5
+; CHECK-UNWINDER:   (637, 645): 5
+; CHECK-UNWINDER:   (645, 5ff): 5
+; CHECK-UNWINDER: main:1 @ foo:3 @ bar
+; CHECK-UNWINDER:   (5c8, 5dc): 2
+; CHECK-UNWINDER:   (5d7, 5e5): 4
+; CHECK-UNWINDER:   (5e9, 634): 4
+
+
+
+; original code:
+; clang -O0 -g test.c -o a.out
+#include <stdio.h>
+
+int bar(int x, int y) {
+  if (x % 3) {
+    return x - y;
+  }
+  return x + y;
+}
+
+void foo() {
+  int s, i = 0;
+  while (i++ < 4000 * 4000)
+    if (i % 91) s = bar(i, s); else s += 30;
+  printf("sum is %d\n", s);
+}
+
+int main() {
+  foo();
+  return 0;
+}

llvm/tools/llvm-profgen/PerfReader.cpp

while (Index < Records.size()) {
     Token.split(Addresses, "/");
     uint64_t Src;
     uint64_t Dst;
     Addresses[0].substr(2).getAsInteger(16, Src);
     Addresses[1].substr(2).getAsInteger(16, Dst);
 
     bool SrcIsInternal = Binary->addressIsCode(Src);
     bool DstIsInternal = Binary->addressIsCode(Dst);
+    bool IsExternal = !SrcIsInternal && !DstIsInternal;
+    bool IsIncoming = !SrcIsInternal && DstIsInternal;
+    bool IsOutgoing = SrcIsInternal && !DstIsInternal;
     bool IsArtificial = false;
+
     // Ignore branches outside the current binary.
-    if (!SrcIsInternal && !DstIsInternal)
+    if (IsExternal)
       continue;
-    if (!SrcIsInternal && DstIsInternal) {
+
+    if (IsOutgoing) {
+      if (!PrevTrDst) {
+        // This is unpaired outgoing jump which is likely due to interrupt or
+        // incomplete LBR trace. Ignore current and subsequent entries since
+        // they are likely in different contexts.
+        break;
+      }
+      // For transition to external code, group the Source with the next
+      // availabe transition target.
+      Dst = PrevTrDst;
+      PrevTrDst = 0;
+      IsArtificial = true;
+    } else {
+      if (PrevTrDst) {
+        // If we have seen an incoming transition from external code to internal
+        // code, but not a following outgoing transition, the incoming
+        // transition is likely due to interrupt which is usually unpaired.
+        // Ignore current and subsequent entries since they are likely in
+        // different contexts.
+        break;
+      }
+
+      if (IsIncoming) {
         // For transition from external code (such as dynamic libraries) to
         // the current binary, keep track of the branch target which will be
         // grouped with the Source of the last transition from the current
         // binary.
         PrevTrDst = Dst;
         continue;
       }
-    if (SrcIsInternal && !DstIsInternal) {
-      // For transition to external code, group the Source with the next
-      // availabe transition target.
-      if (!PrevTrDst)
-        continue;
-      Dst = PrevTrDst;
-      PrevTrDst = 0;
-      IsArtificial = true;
     }
+
     // TODO: filter out buggy duplicate branches on Skylake
 
     LBRStack.emplace_back(LBREntry(Src, Dst, IsArtificial));
   }
   TraceIt.advance();
   return !LBRStack.empty();
 }