SimplifyCFG switch-to-lookup forgets about explicit section
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
Starting with the following IR:
```llvm
define hidden range(i32 200, 1101) i32 @get_value(i8 noundef zeroext %0) local_unnamed_addr #0 section "BOOTLOADER" {
switch i8 %0, label %6 [
i8 0, label %2
i8 1, label %3
i8 2, label %4
i8 3, label %5
]
2: ; preds = %1
br label %6
3: ; preds = %1
br label %6
4: ; preds = %1
br label %6
5: ; preds = %1
br label %6
6: ; preds = %5, %4, %3, %2, %1
%.0 = phi i32 [ 200, %1 ], [ 300, %2 ], [ 500, %3 ], [ 800, %4 ], [ 1100, %5 ]
ret i32 %.0
}
```
Running opt 22.1.0 with `-mtriple=arm-none-eabi -passes="simplifycfg"` returns:
```llvm
@switch.table.get_value = private unnamed_addr constant [4 x i32] [i32 300, i32 500, i32 800, i32 1100], align 4
define hidden range(i32 200, 1101) i32 @get_value(i8 noundef zeroext %0) local_unnamed_addr section "BOOTLOADER" {
%2 = icmp ult i8 %0, 4
br i1 %2, label %switch.lookup, label %4
switch.lookup:
%3 = zext nneg i8 %0 to i32
%switch.gep = getelementptr inbounds [4 x i32], ptr @switch.table.get_value, i32 0, i32 %3
%switch.load = load i32, ptr %switch.gep, align 4
br label %4
4:
%.0 = phi i32 [ 200, %1 ], [ %switch.load, %switch.lookup ]
ret i32 %.0
}
```
This makes the expected optimization, converting the switch to a lookup table. But the function had a section, and `@switch.table.get_value` does not.
In the real codebase I tracked this issue down in, this is a simple pure function, used in the bootloader so tagged as such. I would expect giving it a section means everything related to it gets placed within that section, especially since it doesn't reference anything external. However this transformation eventually lead to the lookup table getting placed back in the default section, so when the bootloader tried running the function, the table had yet to be loaded. I can't easily share a whole C replication, but I believe the root cause is this switch to lookup pass forgetting about the section.
If I rewrite the function to manually use a lookup table, where I can explicitly give it a section, we get the following.
```c
__attribute__((section("BOOTLOADER"))) int get_value_using_table(unsigned char idx)
{
static const int TABLE[] __attribute__((section("BOOTLOADER_DATA"))) = {
300, 500, 800, 1100
};
if (idx >= (sizeof(TABLE) / sizeof(*TABLE)))
{
return 200;
}
return TABLE[idx];
}
```
```llvm
@get_value_using_table.TABLE = internal unnamed_addr constant [4 x i32] [i32 300, i32 500, i32 800, i32 1100], section "BOOTLOADER_DATA", align 4, !dbg !0
define dso_local i32 @get_value_using_table(i8 noundef zeroext %idx) local_unnamed_addr #0 section "BOOTLOADER" !dbg !2 {
entry:
#dbg_value(i8 %idx, !12, !DIExpression(), !28)
%cmp = icmp ugt i8 %idx, 4, !dbg !29
br i1 %cmp, label %return, label %if.end, !dbg !31
if.end:
%conv = zext nneg i8 %idx to i32, !dbg !32
%arrayidx = getelementptr inbounds nuw [4 x i8], ptr @get_value_using_table.TABLE, i32 %conv, !dbg !33
%0 = load i32, ptr %arrayidx, align 4, !dbg !34
br label %return, !dbg !35
return:
%retval.0 = phi i32 [ %0, %if.end ], [ 200, %entry ], !dbg !28
ret i32 %retval.0, !dbg !36
}
attributes #0 = { mustprogress nofree norecurse nosync nounwind willreturn memory(none) "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="arm7tdmi" "target-features"="+armv4t,+strict-align,-aes,-bf16,-d32,-dotprod,-fp-armv8,-fp-armv8d16,-fp-armv8d16sp,-fp-armv8sp,-fp16,-fp16fml,-fp64,-fpregs,-fullfp16,-mve.fp,-neon,-sha2,-thumb-mode,-vfp2,-vfp2sp,-vfp3,-vfp3d16,-vfp3d16sp,-vfp3sp,-vfp4,-vfp4d16,-vfp4d16sp,-vfp4sp" }
```
[Compiler Explorer](https://godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(filename:'1',fontScale:14,fontUsePx:'0',j:1,lang:___c,selection:(endColumn:15,endLineNumber:6,positionColumn:15,positionLineNumber:6,selectionStartColumn:15,selectionStartLineNumber:6,startColumn:15,startLineNumber:6),source:'__attribute__((section(%22BOOTLOADER%22)))+int+get_value_using_table(unsigned+char+idx)%0A%7B%0A++++static+const+int+TABLE%5B%5D+__attribute__((section(%22BOOTLOADER_DATA%22)))+%3D+%7B%0A++++++++300,+500,+800,+1100%0A++++%7D%3B%0A++++if+(idx+%3E%3D+(sizeof(TABLE)+/+sizeof(*TABLE)))%0A++++%7B%0A++++++++return+200%3B%0A++++%7D%0A++++return+TABLE%5Bidx%5D%3B%0A%7D'),l:'5',n:'0',o:'C+source+%231',t:'0')),k:49.6872412065441,l:'4',n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:armv7-cclang2210,filters:(b:'0',binary:'1',binaryObject:'1',commentOnly:'0',debugCalls:'1',demangle:'0',directives:'0',execute:'1',intel:'0',libraryCode:'0',trim:'1',verboseDemangling:'0'),flagsViewOpen:'1',fontScale:14,fontUsePx:'0',j:1,lang:___c,libs:!(),options:'--target%3Darm-none-eabi+-O2+-emit-llvm',overrides:!(),selection:(endColumn:1,endLineNumber:1,positionColumn:1,positionLineNumber:1,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1),source:1),l:'5',n:'0',o:'+armv7-a+clang+22.1.0+(Editor+%231)',t:'0')),k:50.31275879345591,l:'4',m:100,n:'0',o:'',s:0,t:'0')),l:'2',n:'0',o:'',t:'0')),version:4)
As you might expect, this is essential identical. In fact, if you let it continue to compile to assembly, it is. But critically, the table in this case has a section. In the actual codebase, doing this placed both the function and table within the bootloader, with the exact same codegen as before otherwise, fixing the issue. This reinforced my belief that it's the lost section to blame.
Now I suspect you probably can't just copy the function's section to the lookup table, for similar reasons as to why I had to use a different section name for the manual lookup table. I can see there being weird memory architectures I don't know enough about where that doesn't work. But the current behavior of just dropping the section isn't exactly a safe transformation either.
Contributor guide
Research direction
Reproduce the issue with the provided IR and opt command using simplifycfg. Then inspect the switch-to-lookup implementation and existing SimplifyCFG tests to determine how explicit sections should be handled; done means the transformed lookup table has safe section placement and a regression test covers the case.
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
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 48/100