This is an archive of the discontinued LLVM Phabricator instance.

Handle value uses wrapped in metadata for the use-list order
ClosedPublic

Authored by dstenb on Oct 26 2018, 6:04 AM.

Details

Summary

When generating the use-list order, also consider value uses that are
operands which are wrapped in metadata; e.g. llvm.dbg.value operands.

This fixes PR36778. The test case is based on the reproducer from that
report.

Diff Detail

Event Timeline

dstenb created this revision.Oct 26 2018, 6:04 AM

I thought I had built up some confidence for this after a night of fuzz testing. However, first after creating this review I encountered a crash in the LL parser, which happened due to the use-list order containing too many elements with this patch.

For my off-tree target this happens for a i16* null, which have the following uses:

call void @llvm.dbg.value(metadata i16* null, metadata !16, metadata !DIExpression()), !dbg !17 
call void @llvm.dbg.value(metadata i16* null, metadata !16, metadata !DIExpression()), !dbg !17 
call void @llvm.dbg.value(metadata i16* null, metadata !16, metadata !DIExpression()), !dbg !17 
%_tmp4 = call i16 bitcast (i16 (...) addrspace(40)* @fn2 to i16 (i16*, i16*, i16*) addrspace(40)*)(i16* null, i16* null, i16* null), !dbg !18
error: wrong number of indexes, expected 3

Maybe you see something obviously bad with the approach in this patch? In the meanwhile, I'll investigate the crash.

I'm sorry for the inconvenience!

dstenb updated this revision to Diff 173153.Nov 8 2018, 6:18 AM
dstenb edited the summary of this revision. (Show Details)

In the previous revision I had overlooked two things in the writers:

  1. The code did not look for uses in metadata operands in predictUseListOrder(). This resulted in the use-list order being emitted too early (which caused the crash in my previous revision), or not at all if there were no non-metadata uses of the constant.
  2. For bitcode files, constants used in metadata are emitted as module-level constants. I have had to change the order in orderModule() to account for that.

I have updated the test case to reflect those changes.

Also, I had missed to look at metadata operands when changing use-lists in verify-uselistorder, meaning that we would not fuzz test the use-list order for constants where we only have uses in metadata operands.

Also, as a minor cleanup, I removed the comment shown below from AsmWriter's orderModule(). I don't think the comment is correct, as things are ordered differently in assembly and bitcode, and I suspect that it was simply copy-pasted from the BitcodeWriter's orderModule() implementation.

// This needs to match the order used by ValueEnumerator::ValueEnumerator()
// and ValueEnumerator::incorporateFunction().
dexonsmith added inline comments.Nov 8 2018, 10:41 AM
test/Assembler/metadata-use-uselistorder.ll
5–6

Does this only cause problems for constants (like i64 0), or also for use lists of locals and globals?

The reason I ask: we *should* make it impossible for most constants to rely on use-list order, and then stop storing use-lists for them (in either bitcode or textual IR). When we get there, should we delete this test and the new code you've added? Or will it still be relevant for other values?

dstenb added inline comments.Nov 12 2018, 1:18 AM
test/Assembler/metadata-use-uselistorder.ll
5–6

Oh, okay! Do you know if someone is actively working on that at the moment?

The metadata operands can affect the use lists of globals in cases where they contain constant expressions using globals.

For example, the following file:

typedef struct { int a; int b; int c; } S;

extern void work(int *);

S g;

void foo() {
  int *local1 = &g.a;
}

void bar() {
  int *local2 = &g.b;
  work(local2);
  S l = {1, 2, 3};
  g = l;
}

compiled using the following, slightly contrived, command line:

$ clang -O0 -Xclang -disable-O0-optnone -g -S -emit-llvm di.c -o - | opt -S -instcombine -o di.ll
$ grep '@g' di.ll
@g = common dso_local global %struct.S zeroinitializer, align 4, !dbg !0
  call void @llvm.dbg.value(metadata i32* getelementptr inbounds (%struct.S, %struct.S* @g, i32 0, i32 0), metadata !20, metadata !DIExpression()), !dbg !22
  call void @llvm.dbg.value(metadata i32* getelementptr inbounds (%struct.S, %struct.S* @g, i32 0, i32 1), metadata !25, metadata !DIExpression()), !dbg !26
  call void @llvm.dbg.value(metadata i32* getelementptr inbounds (%struct.S, %struct.S* @g, i64 0, i32 1), metadata !25, metadata !DIExpression()), !dbg !26
  call void @work(i32* getelementptr inbounds (%struct.S, %struct.S* @g, i64 0, i32 1)) #4, !dbg !27
  call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 4 bitcast (%struct.S* @g to i8*), i8* align 4 bitcast (%struct.S* @bar.l to i8*), i64 12, i1 false), !dbg !28

gives without this patch:

$ verify-uselistorder di.ll -debug 2>&1 | grep -A10 fail:
 - fail: user mismatch: ID = 0
 - LHS value = @g = common dso_local global %struct.S zeroinitializer, align 4, !dbg !0
   => use: op = 0, user-id = 0, user = i32* getelementptr inbounds (%struct.S, %struct.S* @g, i32 0, i32 0)
   => use: op = 0, user-id = 0, user = i32* getelementptr inbounds (%struct.S, %struct.S* @g, i32 0, i32 1)
   => use: op = 0, user-id = 27, user = i32* getelementptr inbounds (%struct.S, %struct.S* @g, i64 0, i32 1)
   => use: op = 0, user-id = 28, user = i8* bitcast (%struct.S* @g to i8*)
 - RHS value = @g = common dso_local global %struct.S zeroinitializer, align 4, !dbg !0
   => use: op = 0, user-id = 28, user = i8* bitcast (%struct.S* @g to i8*)
   => use: op = 0, user-id = 27, user = i32* getelementptr inbounds (%struct.S, %struct.S* @g, i64 0, i32 1)
   => use: op = 0, user-id = 0, user = i32* getelementptr inbounds (%struct.S, %struct.S* @g, i32 0, i32 1)
   => use: op = 0, user-id = 0, user = i32* getelementptr inbounds (%struct.S, %struct.S* @g, i32 0, i32 0)

So, unless I have misunderstood something, I assume that this will code be relevant even after that.

A run of verify-uselistorder on the attached test case does unfortunately not bail out for @global_arr (even if it were changed so that it does not trigger for i64 0), due to there only being one mapped user of the global (the GEP in the load). I can update the patch so that the verification fails for the global, and update the comment in the test case so that it just does not refer to the i64 0.

dstenb updated this revision to Diff 173646.Nov 12 2018, 3:31 AM

Add another non-metadata user of @global_arr to the test case so that the verification of the global's use-list order fails when running without this patch. Also generalize the comment in the test case.

dexonsmith accepted this revision.Oct 17 2020, 5:42 AM

I totally lost track of this :/.

The patch looks correct, thanks very much for tracking this down. This LGTM if you add an explanation to the testcase of exactly what it’s testing (I worry it’s not obvious for someone trying to update the test later).

This revision is now accepted and ready to land.Oct 17 2020, 5:42 AM
dstenb updated this revision to Diff 299405.Oct 20 2020, 10:27 AM

Rebase, and update comment in test case.

Herald added a project: Restricted Project. · View Herald TranscriptOct 20 2020, 10:27 AM
Herald added a subscriber: hiraditya. · View Herald Transcript

I totally lost track of this :/.

The patch looks correct, thanks very much for tracking this down. This LGTM if you add an explanation to the testcase of exactly what it’s testing (I worry it’s not obvious for someone trying to update the test later).

Me too! Thanks a lot for reviewing this!

I have added an explanation to the test case.