KhronosGroup / KhronosGroup/SPIRV-LLVM-Translator

Translator adds synthetic blocks that break the LCSSA property of input LLVM IR

Open
#1,971 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
LLVM
Stars
625
Forks
279
Avg merge
3d 5h
Merged PRs (30d)
34

Description

Loop-closed SSA (LCSSA) is a form of IR where values defined inside a loop are only used inside the loop (in the loop tree sense, ie you're in a loop if you can reach the loop header block). LLVM [enforces](https://llvm.org/docs/LoopTerminology.html#loop-closed-ssa-lcssa) this property and I expected this translator to leave it alone and not perform any relevant transformation. Sadly it seems the translator adds additional basic blocks to the IR in a careless way that breaks the LCSSA property.

Consider the following example function:
```c
unsigned int FNVHash(char* str, unsigned int length) {
const unsigned int fnv_prime = 0x811C9DC5;
unsigned int hash = 0;
unsigned int i = 0;

for (i = 0; i < length; str++, i++)
{
hash *= fnv_prime;
hash ^= (*str);
}

return hash;
}
```

Compiled using Clang in "C++ for OpenCL" mode, we get the following:

```llvm
; Function Attrs: mustprogress nofree norecurse nosync nounwind readonly willreturn
define dso_local spir_func noundef i32 @_Z7FNVHashPU3AS4cj(i8 addrspace(4)* nocapture noundef readonly %0, i32 noundef %1) local_unnamed_addr #0 {
%3 = icmp eq i32 %1, 0
br i1 %3, label %15, label %4

4: ; preds = %2, %4
%5 = phi i32 [ %13, %4 ], [ 0, %2 ]
%6 = phi i32 [ %11, %4 ], [ 0, %2 ]
%7 = phi i8 addrspace(4)* [ %12, %4 ], [ %0, %2 ]
%8 = mul i32 %6, -2128831035
%9 = load i8, i8 addrspace(4)* %7, align 1, !tbaa !4
%10 = sext i8 %9 to i32
%11 = xor i32 %8, %10
%12 = getelementptr inbounds i8, i8 addrspace(4)* %7, i64 1
%13 = add nuw i32 %5, 1
%14 = icmp ult i32 %13, %1
br i1 %14, label %4, label %15, !llvm.loop !7

15: ; preds = %4, %2
%16 = phi i32 [ 0, %2 ], [ %11, %4 ]
ret i32 %16
}
```

We can see the `%16` variable is defined by a phi node and it consumes `%11`, the result of the xor operation computed inside the loop. By using this phi node, LLVM maintains LCSSA: outside of phi nodes immediately exiting the loop, loop variables do not get used outside of it. Now consider the output of the translator for this function:

```
%_Z7FNVHashPU3AS4cj = OpFunction %uint None %12
%14 = OpFunctionParameter %_ptr_Generic_uchar
%15 = OpFunctionParameter %uint
%16 = OpLabel
%23 = OpIEqual %bool %15 %uint_0
OpBranchConditional %23 %20 %_preheader
%_preheader = OpLabel
OpBranch %18
%18 = OpLabel
%25 = OpPhi %uint %24 %18 %uint_0 %_preheader
%27 = OpPhi %uint %26 %18 %uint_0 %_preheader
%29 = OpPhi %_ptr_Generic_uchar %28 %18 %14 %_preheader
%31 = OpIMul %uint %27 %uint_2166136261
%32 = OpLoad %uchar %29 Aligned 1
%33 = OpSConvert %uint %32
%26 = OpBitwiseXor %uint %31 %33
%28 = OpInBoundsPtrAccessChain %_ptr_Generic_uchar %29 %ulong_1
%24 = OpIAdd %uint %25 %uint_1
%39 = OpULessThan %bool %24 %15
OpBranchConditional %39 %18 %_loopexit
%_loopexit = OpLabel
OpBranch %20
%20 = OpLabel
%40 = OpPhi %uint %uint_0 %16 %26 %_loopexit
OpReturnValue %40
OpFunctionEnd
```

There are two new blocks inserted before the loop entry and after the loop exit. I'm not sure of their purpose - in this function they are just empty trampolines. However, simply by inserting them this IR is no longer in LCSSA form! This is because `_loopexit`, not `%20` is the loop exit node, but the phi node still lives in `%20` which means we're now using `%26` (the xor) outside the loop (specifically, in `_loopexit` as it's like we're passing `%26` to `%20` as an argument.

My desired fix here would be to simply not add those extra blocks, if it weren't for them, the 1:1 translation that would result would maintain the LCSSA property. It's unclear to me why those two blocks were added in the first place - this translator doesn't seem to perform IR structuring or any such legalization work.

Contributor guide

Open the contributing guide

Research direction

Reproduce the provided C++ for OpenCL example and compare the shown LLVM IR with the translator's SPIR-V output. Inspect why the _preheader and _loopexit trampoline blocks are inserted; done means the translated IR preserves LCSSA without unnecessary blocks or otherwise explains their required purpose.

Written by the indexing model from the issue text.

Assessment

Domain
compilers
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.