New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Ordering of LLVM Add instructions can change HVX codegen semantics #3203

Closed
steven-johnson opened this Issue Aug 9, 2018 · 7 comments

Comments

Projects
None yet
2 participants
@steven-johnson
Contributor

steven-johnson commented Aug 9, 2018

It appears that changing the order of codegen for an Add node can alter the overall result of the pipeline when generating HVX code. My suspiction is a bug in LLVM (either in general or in the HVX backend), though I haven't entirely ruled out something in Halide's HVX-specific code.

To repeat:

  • sync to branch srj-hvx-codegen-bug
  • build and run on CPU and HVX-simulator:
    • HL_TARGET=host make bin/host/generator_aot_downsample && ./bin/host/generator_aot_downsample
    • HL_TARGET=host-hvx_128 make bin/host-hvx_128/generator_aot_downsample && HL_HEXAGON_SIM_REMOTE=/path/to/hexagon_sim_remote ./bin/host-hvx_128/generator_aot_downsample

Note that both output:

0 0 624
1 0 1264
2 0 1760
3 0 1792

Now, edit Codegen_LLVM.cpp by changing the #if 1 on line 1264 to #if 0 (swapping the codegen order for some Add operators) and repeat the above steps; notice that the CPU run is the same, but the HVX output is now:

0 0 624
1 0 1264
2 0 1764   <-- ooooops
3 0 1792

Note that the third value is different (1764 instead of 1760); needless to say, the order of arguments to integer addition shouldn't be affecting the result.

(Note that at top-of-tree, the order of codegen is unspecified and at the mercy of how the C++ compiler decides to evaluate the arguments to CreateAdd(); the edits in this issue/branch are there to ensure a reliable order.)

@steven-johnson

This comment has been minimized.

Show comment
Hide comment
@steven-johnson

steven-johnson Aug 9, 2018

Contributor

(Note that this is using recent LLVM trunk builds; I haven't tried older LLVM versions.)

Contributor

steven-johnson commented Aug 9, 2018

(Note that this is using recent LLVM trunk builds; I haven't tried older LLVM versions.)

@pranavb-ca

This comment has been minimized.

Show comment
Hide comment
@pranavb-ca

pranavb-ca Aug 9, 2018

Contributor

I am able to reproduce this now. BTW, when I built Halide on this branch test/internal.cpp - generator_test() failed. Did you also see that?

Contributor

pranavb-ca commented Aug 9, 2018

I am able to reproduce this now. BTW, when I built Halide on this branch test/internal.cpp - generator_test() failed. Did you also see that?

@steven-johnson

This comment has been minimized.

Show comment
Hide comment
@steven-johnson

steven-johnson Aug 9, 2018

Contributor

I did not try the other tests on this branch.

Contributor

steven-johnson commented Aug 9, 2018

I did not try the other tests on this branch.

steven-johnson added a commit that referenced this issue Aug 10, 2018

Ensure calls to codegen() are well-ordered
C++11 doesn't guarantee that function arguments are evaluated in a particular order, thus calls of the form `builder->CreateFoo(codegen(a), codegen(b))` might generate LLVM IR with either a-then-b or b-then-a; at best, this makes comparing IR between compilers a nuisance; at worst, it can trigger subtle bugs and make them harder to find (see #3203). This PR looks for all calls that evalutate codegen() more than once as a function arg and rearranges code to use temporaries to ensure a well-defined order.

(Note that a few with only a single call to codegen() were also pulled into temporaries where I thought it improved clarity or helped forestall reinsertion of the bad code pattern by future edits.)
@pranavb-ca

This comment has been minimized.

Show comment
Hide comment
@pranavb-ca

pranavb-ca Aug 14, 2018

Contributor

Update: I have been able to isolate this to about 9 adds where in if the order is changed from code generating 'a before b' to 'b before a' the ouput toggles from incorrect to correct. I am now going over the difference in IR between the two.

Contributor

pranavb-ca commented Aug 14, 2018

Update: I have been able to isolate this to about 9 adds where in if the order is changed from code generating 'a before b' to 'b before a' the ouput toggles from incorrect to correct. I am now going over the difference in IR between the two.

@pranavb-ca

This comment has been minimized.

Show comment
Hide comment
@pranavb-ca

pranavb-ca Aug 15, 2018

Contributor

Update: When I disable the the reassociate pass in LLVM, the test passes. This makes sense at least to the point that the reassociate pass would be sensitive to the order of instructions that it sees. Still digging...

Contributor

pranavb-ca commented Aug 15, 2018

Update: When I disable the the reassociate pass in LLVM, the test passes. This makes sense at least to the point that the reassociate pass would be sensitive to the order of instructions that it sees. Still digging...

@pranavb-ca

This comment has been minimized.

Show comment
Hide comment
@pranavb-ca

pranavb-ca Aug 23, 2018

Contributor

Narrowed this down to a bug in the software pipeliner in LLVM that was incorrectly fixing up the PHI nodes in the kernel of a software pipelined loop. A fix for this is in review here https://reviews.llvm.org/D51167
I have verified that this test passes with LLVM built with this fix. I will close this issue once this lands and @steven-johnson confirms.

Contributor

pranavb-ca commented Aug 23, 2018

Narrowed this down to a bug in the software pipeliner in LLVM that was incorrectly fixing up the PHI nodes in the kernel of a software pipelined loop. A fix for this is in review here https://reviews.llvm.org/D51167
I have verified that this test passes with LLVM built with this fix. I will close this issue once this lands and @steven-johnson confirms.

steven-johnson added a commit that referenced this issue Aug 27, 2018

Ensure calls to codegen() are well-ordered
C++11 doesn't guarantee that function arguments are evaluated in a particular order, thus calls of the form builder->CreateFoo(codegen(a), codegen(b)) might generate LLVM IR with either a-then-b or b-then-a; at best, this makes comparing IR between compilers a nuisance; at worst, it can trigger subtle bugs and make them harder to find (see #3203). This PR looks for all calls that evalutate codegen() more than once as a function arg and rearranges code to use temporaries to ensure a well-defined order.

(Note that a few with only a single call to codegen() were also pulled into temporaries where I thought it improved clarity or helped forestall reinsertion of the bad code pattern by future edits.)
@steven-johnson

This comment has been minimized.

Show comment
Hide comment
@steven-johnson

steven-johnson Aug 27, 2018

Contributor

The LLVM portion of this landed in llvm-trunk at r340782 llvm-mirror/llvm@6d962e3; once #3249 lands, this should be marked as fixed.

Contributor

steven-johnson commented Aug 27, 2018

The LLVM portion of this landed in llvm-trunk at r340782 llvm-mirror/llvm@6d962e3; once #3249 lands, this should be marked as fixed.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment