Page MenuHomePhabricator

[LiveDebugValues] End variable's range with multiple locations at block entry
AbandonedPublic

Authored by NikolaPrica on May 14 2019, 5:51 AM.

Details

Summary

Close variable's range when variable have multiple locations at block entry. Having BB1 that branches to BB2 and BB3, where BB2 falls through to BB3, variable can have different locations at BB1 and BB2. Since input locations at BB3 for same variable are different LiveDebugValues won’t generate DBG_VALUE for BB3. If last variable location at BB2 is non-changing register, DbgEntityHistoryCalculator will extend range of DBG_VALUE from BB2 to whole BB3 and thus producing incorrect range for case when we took branch BB3 from BB1.

Diff Detail

Event Timeline

NikolaPrica created this revision.May 14 2019, 5:51 AM
aprantl added inline comments.May 14 2019, 8:46 AM
lib/CodeGen/LiveDebugValues.cpp
767

Out of curiosity, did you empirically arrive at this number? I.e., is it above the median size of the set when compiling clang? I'm asking because LiveDebugValues is notoriously performance-sensitive.

768

Are you sure that using DIVariable alone as the index is the right thing to do here? Does this handle inlined DBG_VALUEs the way it's supposed to? I'm thinking about a function that is inlined twice in a row into the same basic block, for example.

789

multiple locations .. inside this BB?

795

It reads strange to unconditionally insert all incoming DBG_VALUES into a set called ConflictVars.

799

This looks like it could be really slow. Have you measured the performance impact? Would it be faster to have a map from Variable->Index and use a BitVector instead of a SmallPtrSet?

wolfgangp added inline comments.May 14 2019, 6:25 PM
lib/CodeGen/LiveDebugValues.cpp
789

Grammar nit: about->of

790

Grammar nit: theirs->their

test/DebugInfo/MIR/X86/dbg-stack-value-range.mir
1

Is this test case really necessary? It seems you are mainly testing that the DWARF ranges are generated correctly, which they should be, since there was no change to DbgEntityHistoryCalculator.

If you feel that it is necessary, perhaps it would be better to use assembly output so we don't check for exact code ranges? It may be easier to verify that the location list range does not extend all the way to the end of the function.

dstenb added inline comments.May 15 2019, 2:03 AM
test/DebugInfo/MIR/X86/dbg-live-debug-values-end-range.mir
20–21

It could be good to add CHECK(-LABEL)s for the basic block labels before each DBG_VALUE, e.g.:

CHECK-LABEL: bb.2.if.end:
CHECK: DBG_VALUE $noreg, $noreg, ![[LOCALVAR]]

(and perhaps also add a check for bb.1's DBG_VALUE?)

Hmmm, I get what the patch is doing, but I have the feeling that it might be the wrong place (or impossible) to fix in LiveDebugValues. Given the sample source in dbg-live-debug-values-end-range.mir, would I be right in thinking that this patch is to fix the ChangingRegs behaviour that David brought up in [0]?

Consider this example:

volatile int g, *x;

int baz(int p, int q) {
  int local;

  switch (g) {
  case 1:
    local = p;
    x[1] = local;
    break; 
  case 2:
    x[2] += p;
    break;
  default:
    local = q;
    g++;
    break;
  }

  return x[1] / q + g;
}

Compiling with llvm r359863 and this patch applied, the conflicting locations of "local" in the "case 1" and default blocks don't seem to be detected, and no DBG_VALUE $noreg is produced in the function exit block, which is what I anticipated this patch would do. I haven't dug into why. As a result, the "default" location of "local" flows into the exit block due to the ChangingRegs functionality (see below).

IMHO there's a bigger problem though, assuming this patch is about fixing the behaviour in [0]. LiveDebugValues only deals with the control flow predecessors / successors of blocks when calculating LiveIns / LiveOuts, wheras DbgEntityHistoryCalculator considers blocks only in the order that they're placed in. Thus, terminating a variable location in the control flow successor block won't stop DbgEntityHistoryCalculator extending a location into the next block in the placement order. If the next placed block isn't a control flow successor to the previously placed block, it won't get a DBG_VALUE $noreg. That can been seen in the example above: according to llvm-dwarfdump, the "case 2" block (0x1c -> 0x28) gets a location for the "local" variable despite it having no location in the source / pre-backend-IR:

$ clang-w-patch test2.c -o out.o -O2 -g -c
$ objdump -d out.o
  0000000000000000 <baz>:
     0:	8b 05 00 00 00 00    	mov    0x0(%rip),%eax        # 6 <baz+0x6>
     6:	83 f8 02             	cmp    $0x2,%eax
     9:	74 11                	je     1c <baz+0x1c>
     b:	83 f8 01             	cmp    $0x1,%eax
     e:	75 18                	jne    28 <baz+0x28>
    10:	48 8b 05 00 00 00 00 	mov    0x0(%rip),%rax        # 17 <baz+0x17>
    17:	89 78 04             	mov    %edi,0x4(%rax)
    1a:	eb 1a                	jmp    36 <baz+0x36>
    1c:	48 8b 05 00 00 00 00 	mov    0x0(%rip),%rax        # 23 <baz+0x23>
    23:	01 78 08             	add    %edi,0x8(%rax)
    26:	eb 0e                	jmp    36 <baz+0x36>
    28:	83 05 00 00 00 00 01 	addl   $0x1,0x0(%rip)        # 2f <baz+0x2f>
    2f:	48 8b 05 00 00 00 00 	mov    0x0(%rip),%rax        # 36 <baz+0x36>
    36:	8b 40 04             	mov    0x4(%rax),%eax
    39:	99                   	cltd   
    3a:	f7 fe                	idiv   %esi
    3c:	03 05 00 00 00 00    	add    0x0(%rip),%eax        # 42 <baz+0x42>
    42:	c3                   	retq   

$ llvm-dwarfdump-7 --name=local out.o

  0x00000098: DW_TAG_variable
            DW_AT_location	(0x00000000
               [0x0000000000000010,  0x0000000000000028): DW_OP_reg5 RDI
               [0x0000000000000028,  0x0000000000000043): DW_OP_reg4 RSI)
            DW_AT_name	("local")

I suspect the only way of fixing this in general is killing off the ChangingRegs functionality in the DbgEntityHistoryCalculator. I've given that an initial look and it raises some awkward questions; I'll upload the patch for discussion in a moment.

For the avoidance of doubt: I don't think fixing ChangingRegs is required for D61600 (it's just something that came up in discussion), I'll post a comment there to make that clear.

[0] https://reviews.llvm.org/D61600#1493393

@aprantl @wolfgangp Thanks for your comments! They are really useful for me regardless of this patch being accepted or not.
Before I start addressing them I would like to get to the same point whether this is the right place to address this problem that we try to solve in D61600, D61940 and here.

would I be right in thinking that this patch is to fix the ChangingRegs behaviour that David brought up in [0]?

Yes. You are right about this. I've took his example as a second test here.

Compiling with llvm r359863 and this patch applied, the conflicting locations of "local" in the "case 1" and default blocks don't seem to be detected, and no DBG_VALUE $noreg is produced in the function exit block, which is what I anticipated this patch would do. I haven't dug into why. As a result, the "default" location of "local" flows into the exit block due to the ChangingRegs functionality (see below).

The problem with your test case is that 2/3 incoming BB locations in the last basic block have DBG_VALUE for variable local and current code looks for intersection of all incoming blocks. With some better variables bitset operations(when this gets refactored by Adrian's suggestion) I suppose it could be handled. But nevertheless, as you mentioned, covering "case 2:" block can't be handled here.

The reason I offered this patch as a alternative to D61600 is that it degrades some ranges when it could leave them wider (test/DebugInfo/X86/fission-ranges.ll). My first attempt to solve this problem was just to make DbgEntityHistoryCalculator close all DBG_VALUES at the end of block. I tried to find other solution (as D61600 and this) but It seems inevitable.

The reason I offered this patch as a alternative to D61600 is that it degrades some ranges when it could leave them wider (test/DebugInfo/X86/fission-ranges.ll).

Hmn, that test difference is interesting -- I'm going to drop a little bit of analysis in D61600, but the tl;dr is that the test IR seems to be incorrect.

NikolaPrica abandoned this revision.May 20 2019, 3:55 AM

It seems that D61600 is the right way to solve this problem, so I'm abandoning this change.