M-Labs/nac3
M-Labs
/
nac3
8
0
Fork 10
Code Issues 99 Pull Requests 20 Releases Wiki Activity

Use i8 for stack boolean variable allocation #321

Merged
sb10q merged 1 commits from issue-315 into master 2024-08-17 17:37:20 +08:00
Conversation 7 Commits 1 Files Changed 5 +68 -9
derppening commented 2023-09-20 17:24:51 +08:00
Collaborator
Copy Link

Copied from the relevant commit description:

In LLVM, i1 represents a 1-byte integer with a single valid bit; The
rest of the 7 upper bits are undefined. This causes problems when
using these variables in memory operations (e.g. memcpy/memmove as
needed by List slicing and assignment).

We fix this by treating all local boolean variables as i8 so that they
are well-defined for memory operations. Function ABIs will continue to
use i1, as memory operations cannot be directly performed on function
arguments or return types, instead they are always converted back into
local boolean variables (which are i8s anyways).

Additional Context:

The bug in #315 is manifested via the use of (1) i1 as the List element type, and (2) a pointer cast of i1* to i8* in codegen::irrt::list_slice_assignment. The i1* to i8* cast is to facilitate the use of __builtin_memcpy and __builtin_memmove for implementing assignment of list slices, but because i1 is represented as an i8 with 7 upper undefined bits, this cast effectively extends 0b{0,1} into 0b???????{0,1} (? are undefined bits). This erroneous cast is then propagated to the backend, where the upper 7 bits of the boolean is not masked (& 0x1), causing the output of 255.

The ABI remains unchanged after this change, i.e. function parameters and return types will still be i1 to remain consistent with LLVM IR generated by other compilers (e.g. Clang). To bridge the difference between i1 and i8, two conversion functions (bool_to_i1 and bool_to_i8) are added to convert between the types when necessary.

This bug cannot be reproduced using the New Pass Manager because as opposed to the Legacy PM, the New PM is implemented such that it executes loop analysis, CG-SCC (call graph strongly-connected components) analysis, and module analysis in addition to function analysis, causing the bug to be masked by aggressive optimizations. A future commit may be necessary to fully control the optimizations used for the entire compilation pipeline.

Other Information:

This PR also contains infrastructural improvements, including updated Rust dependencies, replacement of deprecated LLVM intrinsics, implementation of __nac3_raise in Standalone, C implementation of the demo library and lli support, and improved documentation. Moved to #322.

Fixes #315.

Copied from the relevant commit description: > In LLVM, `i1` represents a 1-byte integer with a single valid bit; The rest of the 7 upper bits are undefined. This causes problems when using these variables in memory operations (e.g. `memcpy`/`memmove` as needed by List slicing and assignment). > We fix this by treating all local boolean variables as `i8` so that they are well-defined for memory operations. Function ABIs will continue to use `i1`, as memory operations cannot be directly performed on function arguments or return types, instead they are always converted back into local boolean variables (which are `i8`s anyways). Additional Context: The bug in #315 is manifested via the use of (1) `i1` as the `List` element type, and (2) a pointer cast of `i1*` to `i8*` in `codegen::irrt::list_slice_assignment`. The `i1*` to `i8*` cast is to facilitate the use of `__builtin_memcpy` and `__builtin_memmove` for implementing assignment of list slices, but because `i1` is represented as an `i8` with 7 upper undefined bits, this cast effectively extends `0b{0,1}` into `0b???????{0,1}` (`?` are undefined bits). This erroneous cast is then propagated to the backend, where the upper 7 bits of the boolean is not masked (`& 0x1`), causing the output of 255. The ABI remains unchanged after this change, i.e. function parameters and return types will still be `i1` to remain consistent with LLVM IR generated by other compilers (e.g. Clang). To bridge the difference between `i1` and `i8`, two conversion functions (`bool_to_i1` and `bool_to_i8`) are added to convert between the types when necessary. This bug cannot be reproduced using the New Pass Manager because as opposed to the Legacy PM, the New PM is implemented such that it executes loop analysis, CG-SCC (call graph strongly-connected components) analysis, and module analysis *in addition to* function analysis, causing the bug to be masked by aggressive optimizations. A future commit may be necessary to fully control the optimizations used for the entire compilation pipeline. ~~Other Information:~~ ~~This PR also contains infrastructural improvements, including updated Rust dependencies, replacement of deprecated LLVM intrinsics, implementation of `__nac3_raise` in Standalone, C implementation of the `demo` library and `lli` support, and improved documentation.~~ Moved to #322. Fixes #315.
derppening self-assigned this 2023-09-20 17:24:51 +08:00
derppening requested review from sb10q 2023-09-20 17:24:58 +08:00
dpn commented 2023-09-20 21:59:46 +08:00
Contributor
Copy Link

Yep, using i8 as the "storage type" for bool is, unfortunately, the way to go; this is the standard approach in other compilers.

Yep, using `i8` as the "storage type" for bool is, unfortunately, the way to go; this is the standard approach in other compilers.
sb10q commented 2023-09-21 07:54:16 +08:00
Owner
Copy Link

Should we just use i8 everywhere then to avoid complexity/confusion and potentially other similar bugs?

Should we just use i8 everywhere then to avoid complexity/confusion and potentially other similar bugs?
dpn commented 2023-09-21 08:02:36 +08:00
Contributor
Copy Link

IIRC this just adds more complexity, as i1 is still used for IR-level boolean operations (comparisons, select, etc.). The clearest solution re complexity/confusion seems to be to just insist on a distinction between value type and memory/storage type.

IIRC this just adds more complexity, as `i1` is still used for IR-level boolean operations (comparisons, `select`, etc.). The clearest solution re complexity/confusion seems to be to just insist on a distinction between value type and memory/storage type.
derppening force-pushed issue-315 from 47d9f8d5c6 to 6a2da69317 2023-09-21 12:10:44 +08:00 Compare
derppening commented 2023-09-21 12:12:25 +08:00
Author
Collaborator
Copy Link

v2: Extracted other changes into #322. This PR is now dependent on it as it contains a test regression fix.

v2: Extracted other changes into #322. This PR is now dependent on it as it contains a test regression fix.
derppening added a new dependency 2023-09-21 12:14:11 +08:00
#322 Meta changes from #321
derppening force-pushed issue-315 from 6a2da69317 to 899c0d8cd3 2023-09-21 16:41:06 +08:00 Compare
derppening commented 2023-09-21 16:42:28 +08:00
Author
Collaborator
Copy Link

v3: Rebased against meta-changes-from-issue-315.

v3: Rebased against `meta-changes-from-issue-315`.
derppening force-pushed issue-315 from 899c0d8cd3 to 3c0b5eb1b6 2023-09-25 11:56:21 +08:00 Compare
derppening commented 2023-09-25 11:56:42 +08:00
Author
Collaborator
Copy Link

v4: Rebased against master.

v4: Rebased against `master`.
sb10q reviewed 2023-09-25 15:06:20 +08:00
nac3standalone/demo/demo.c Outdated
@ -0,0 +1,84 @@
#include <assert.h>
sb10q commented 2023-09-25 15:06:20 +08:00
Owner
Copy Link

This file does not belong in this PR.

This file does not belong in this PR.
derppening force-pushed issue-315 from 3c0b5eb1b6 to acdb1de6fe 2023-09-25 15:46:26 +08:00 Compare
derppening commented 2023-09-25 15:46:51 +08:00
Author
Collaborator
Copy Link

v5: Dropped irrelevant commits.

v5: Dropped irrelevant commits.
sb10q merged commit acdb1de6fe into master 2023-09-25 18:12:46 +08:00
Sign in to join this conversation.
Reviewers
No reviewers
sb10q
Labels
Clear labels   
future-extension

   
high-priority

   
low-priority

   
UROP0622
No Label
future-extension
high-priority
low-priority
UROP0622
Milestone
Clear milestone
No items
No Milestone
Assignees
Clear assignees
No Assignees
derppening
3 Participants
Notifications
Due Date
The due date is invalid or out of range. Please use the format 'yyyy-mm-dd'.

No due date set.

Depends on
#322 Meta changes from #321
M-Labs/nac3
Reference: M-Labs/nac3#321
No description provided.
Delete Branch "issue-315"

Deleting a branch is permanent. Although the deleted branch may continue to exist for a short time before it actually gets removed, it CANNOT be undone in most cases. Continue?