Type Based Alias Analysis giving incorrect aliasing information with enhanced TBAA format

IR & Optimizations
,
1

Type Based Alias Analysis emits metadata nodes in the frontend, and an analysis pass in the middle-end does access tag matching to determine if two pointers alias or not. TBAA metadata is only attached to Load and Store Instructions.

But with the enhanced struct path TBAA (enabled by -new-struct-path-tbaa), the TBAA nodes are also added to memory aggregates that might cause two pointers to aliase due to their semantics. So, memcpy is usually tagged with TBAA nodes. This happens here in the Clang frontend.

Even though memcpy is tagged with TBAA metadata nodes, the TypeBasedAliasAnalysis is not able to correctly find Alias Sets due to the TBAA node structure being slightly different. I have two testcases where AA returns NoAlias for a case with a Load and Memcpy when they actually are Alias/MayAlias. This leads to further downstream optimizations which are outright wrong. So, far I have observed this in InstCombine and GVN. I have attached the godbolt links to the same below.

  1. InstCombine: Compiler Explorer
  • Take a look at L15 in the IR windows, an Add %0, %1 is converted to a Add %0, %0, which in turn is converted to Shl %0, 1. As it thinks that %0 and %1 (Load which was eliminated) are the same data. But, since we have copied b into a, that’s not true.
  1. GVN: Compiler Explorer
  • GVN also messes up similarly and moves the Gep and Loads to it’s predecessor, and inserts a Phi in the current block. The incoming values of the Phi are undef for other branches, this causes a crash. This IR testcase is reduced form a benchmark, it was generated with the -Xclang -new-struct-path-tbaa option.

The common part here is that, this only happens when we enable the enhanced struct path TBAA (-new-struct-path-tbaa). Let’s look at the case (1) and see where it goes wrong.

tail call void @llvm.memcpy.p0.p0.i64(ptr noundef nonnull align 4 dereferenceable(12) %arrayidx, ptr noundef nonnull align 4 dereferenceable(12) %arrayidx3, i64 12, i1 false), !dbg !39

%arrayidx = getelementptr inbounds %struct.t, ptr %a, i64 %idxprom, !dbg !31
%b1 = getelementptr inbounds i8, ptr %arrayidx, i64 8, !dbg !32
%0 = load i32, ptr %b1, align 4, !dbg !32

Due to the memcpy, arrayidx and arrayidx3 alias, but the TBAA is not to able process that due to the structure of the TBAA nodes. For some reason godbolt is not preserving the tbaa tags, but on a local run you would see a structure like this.

<memcopy tbaa> = {struct_type, struct_type, 0, 12}
<load tbaa> = {struct_type, int, 8, 4}

So, in the source code

The least common type between these two comes to be a omnipotent char, and then inside mayBeAccessToSubobjectOf call, even though BaseType of both nodes is same, the Access type is not equal to the common type, and thus it goes to the next part where the offsets are compared, even here since the offsets are different it returns false to MayAlias.

This can be solved, if we can check if the Tag A is a member of Tag B, but we will have to change the algorithm a bit to account for cases where base type and access type are both for a structure. Currently, base type and access type can only be equal if the access is of a non structure type.

I have a hacky fix to this, but wanted to know if there are any plans by the community to implement this in other way, if not I would like to work on this. I would appreciate comments and direction to this issue.

1 Like