| Issue |
202573
|
| Summary |
Fold `strlen` of Reachable Constant String Table Entries
|
| Labels |
new issue
|
| Assignees |
|
| Reporter |
ParkHanbum
|
## Fold `strlen(table[idx])` when `table[idx]` is a reachable constant string entry
LLVM can miss a small constant-string table idiom where a pointer is loaded from
a constant table, passed to `strlen`, and the resulting length is used as the
length argument of a string comparison.
There are already related LLVM transforms with the same general shape:
- `strlen(select ? "foo" : "bars")` can be folded to a select of constant
lengths.
- SimplifyCFG can turn a switch that selects among constant results into a
private constant lookup table, loading `table[idx]` instead of preserving the
original control flow.
This issue is similar in spirit. The selected result is not written directly in
a switch; it is derived from a constant string table entry through `strlen`.
When the index range proves that only constant string entries are reachable,
LLVM could materialize the derived length either as a small select/switch or as
an indexable constant length table.
Representative shape:
```llvm
@.str.high = private unnamed_addr constant [6 x i8] c",high\00"
@.str.low = private unnamed_addr constant [5 x i8] c",low\00"
@suffix_tbl = internal unnamed_addr constant [3 x ptr]
[ptr @.str.high, ptr @.str.low, ptr null]
loop:
%idx = phi i64 [ 0, %entry ], [ 1, %next ]
%slot = getelementptr [8 x i8], ptr @suffix_tbl, i64 %idx
%suffix = load ptr, ptr %slot
%len = call i64 @strlen(ptr %suffix)
%cmp = call i32 @strncmp(ptr %input, ptr %suffix, i64 %len)
```
In this example the table has a null sentinel, but the reachable index range is
only `0..1`. Both reachable entries are constant strings with known first-NUL
positions, so the runtime `strlen` can be replaced with a constant-length
selection:
```llvm
%slot = getelementptr [8 x i8], ptr @suffix_tbl, i64 %idx
%suffix = load ptr, ptr %slot
%is.low = icmp eq i64 %idx, 1
%len = select i1 %is.low, i64 4, i64 5
%cmp = call i32 @strncmp(ptr %input, ptr %suffix, i64 %len)
```
This is not a request for general dynamic `strlen` folding. The intended scope is
narrow:
- the table object is constant;
- the loaded entries are constant strings with statically known first-NUL
lengths;
- the reachable index range excludes null sentinel entries;
- the `strlen` result is used as a compare length, such as `strncmp`,
`strncasecmp`, or `bcmp`;
- all uses of the `strlen` result are replaced consistently.
A compact C source shape that can leave this kind of IR is:
```c
static const char *const suffix_tbl[] = {
",high",
",low",
NULL,
};
int f(const char *input, size_t idx) {
if (idx >= 2)
return -1;
const char *suffix = suffix_tbl[idx];
size_t len = strlen(suffix);
return strncmp(input, suffix, len) == 0 ? (int)idx : -1;
}
```
This is different from a fully unrolled source-level case. If the optimizer can
split each table entry into a separate path, it can produce direct calls such as
`strncmp(input, ",high", 5)`.
The missed residual case is when the selected string pointer remains dynamic:
```c
suffix = suffix_tbl[idx];
```
but the index is range-checked, so the length is still derivable from the same
index. LLVM does not need to know the loaded pointer as one constant value; it
only needs to preserve the correlation:
```text
idx == 0 -> strlen(suffix_tbl[idx]) == 5
idx == 1 -> strlen(suffix_tbl[idx]) == 4
```
That allows replacing the `strlen` call with a small select or switch on `idx`,
or with an index-based constant length lookup, while leaving the loaded string
pointer itself dynamic.
Observed benchmark-backed instances include:
- `linux/optimized/crash_core.ll:1130`: suffix table feeding `strncmp`
- `linux/optimized/libata-sata.ll:1894`: policy-name table feeding `strncmp`
- `linux/optimized/nf_conntrack_irc.ll:353`: protocol table feeding `bcmp`
- `linux/optimized/trace_events_filter.ll:2715`: operator table feeding
`strncmp`
- `linux/optimized/workqueue.ll:12409`: affinity-name table feeding
`strncasecmp`
- `linux/optimized/workqueue.ll:12934`: affinity-name table feeding
`strncasecmp`
One related instance uses the same constant table length idiom for allocation
size calculation rather than a string-compare length:
- `linux/optimized/hid-sony.ll:1872`
That allocation-size variant may be worth considering separately, but the
compare-length form is the clearer initial target.
Profitability should be guarded by a table-size and cost threshold. There are at
least two possible lowering choices:
- for very small reachable tables, use a compact select or switch on `idx`;
- for larger reachable tables, consider generating or reusing an indexable
constant length table, conceptually:
```llvm
@suffix_tbl_len = private unnamed_addr constant [2 x i64] [i64 5, i64 4]
%len.slot = getelementptr [8 x i8], ptr @suffix_tbl_len, i64 %idx
%len = load i64, ptr %len.slot
```
The length-table form can avoid a long compare/select chain for 5-7 entry
tables, which matches several observed instances. However, it has fixed
overhead: a new global constant, possible alignment/data-section growth, address
materialization, and a load. For two or three entries, that overhead may be worse
than a small select. For cold or size-optimized code, profitability should be
judged on combined code and data size, not only on IR instruction count.
![]()
_______________________________________________
llvm-bugs mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs
