KhronosGroup / KhronosGroup/SPIRV-LLVM-Translator
Translator adds synthetic blocks that break the LCSSA property of input LLVM IR
- 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
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