This is an archive of the discontinued LLVM Phabricator instance.

【TwoAddressInstructionPass】 Put all new instructions into DistanceMap
ClosedPublic

Authored by Carrot on Oct 14 2021, 5:41 PM.

Details

Summary

In function convertInstTo3Addr, after converting a two address instruction into three address instruction, only the last new instruction is inserted into DistanceMap. This is wrong, DistanceMap should track all instructions from the beginning of current MBB to the working instruction. When a two address instruction is converted to three address instruction, multiple instructions may be generated (usually an extra COPY is generated), all of them should be inserted into DistanceMap.

Similarly when unfolding memory operand in function tryInstructionTransform DistanceMap is not maintained correctly.

Diff Detail

Event Timeline

Carrot created this revision.Oct 14 2021, 5:41 PM
Carrot requested review of this revision.Oct 14 2021, 5:41 PM
Herald added a project: Restricted Project. · View Herald TranscriptOct 14 2021, 5:41 PM

The tests affected are all trivial. Is this patch a NFC or fixing some real problem. If it is the latter, can we add a test for that?

I encountered this problem when I was working on a different optimization. It causes real problem in my work, but I can't find a test case for current code base.

How about adding a mir test?

Carrot updated this revision to Diff 380832.Oct 19 2021, 5:43 PM

Add a mir test.

pengfei added inline comments.Oct 19 2021, 8:19 PM
llvm/test/CodeGen/X86/distancemap.mir
72

This does seem correct to me. The input in line 88 is
%10:gr16 = ADD16rr killed %3:gr16($di), killed %5:gr16, ...
But the output turns into add [[COPY4]]($esi)?

Carrot added inline comments.Oct 20 2021, 2:33 PM
llvm/test/CodeGen/X86/distancemap.mir
72

The operands are commuted. This is the exact difference caused by this patch.

Function isProfitableToCommute calls noUseAfterLastDef with argument [[COPY3]] when processing this ADD instruction, DistanceMap is used in noUseAfterLastDef to decide MI's position. When the LEA instruction was generated, several COPY and IMPLICIT_DEF instructions are generated. If they are not added to DistanceMap, noUseAfterLastDef misses the use of [[COPY3]] and returns wrong value. With this patch noUseAfterLastDef can correctly find the use of [[COPY3]] and returns correct value, causes isProfitableToCommute to return different commute decision.

pengfei added inline comments.Oct 20 2021, 11:37 PM
llvm/test/CodeGen/X86/distancemap.mir
72

Oh, I was misled by the name COPY6. The VR names are nonsense here. This should be bug for update script.
Unfortunately, this test doesn't reveal the intent of the patch either. The swapped COPY3 and COPY4 doesn't show the necessity, which is the same as other tests. I'd suggest to remove it due to the misleading output.
Besides, both COPY3 and COPY4 are used in LEA. The explanation here doesn't persuasive.
I'd like to keep the code as is until we see a functional failure. But I'm neutral :)

Carrot added inline comments.Oct 21 2021, 8:41 AM
llvm/test/CodeGen/X86/distancemap.mir
72

I have already commented in my previous reply that I can't find a test to show the problem in current code base, so this test just shows the difference, not a real problem.

But the usage of DistanceMap is not very complex. For every processed MI we insert it into DistanceMap, then we can easily find the position of an MI if it is already processed. In this case noUseAfterLastDef returns false for [[COPY3]] at the position of later ADD is obviously wrong since it is actually used in a COPY instruction. Luckily the wrong result of noUseAfterLastDef is only used to guide commuting, so it doesn't cause errors in generated code.

In my optimization, I also use DistanceMap to find if an MI has been processed. I want to change registers in unprocessed MIs. Because DistanceMap doesn't contains COPY instructions generated together with LEA, so my code thinks the COPY has not been processed and changed the COPY instruction, this time it causes wrong code generated.

So the conclusion is:

  1. There is a logic error in the usage of DistanceMap, it is not difficult to point out by analyzing the source code.
  2. We can see the difference of the bug fixing, but can't see anything wrong with this problem because it is only used to guide commuting in current code base. So you'll never see a functional failure.
  3. In my code I use DistanceMap to find if an MI need to be changed, this time the bug can cause wrong code generated.
pengfei added inline comments.Oct 23 2021, 7:45 PM
llvm/test/CodeGen/X86/distancemap.mir
72

I didn't dig deep into the code, just some general questions:

  1. The distances in DistanceMap seem to be the order of input. What's the mean with this change? I don't think you counted all new COPY MI. E.g. the one in line 56, right?
  2. DistanceMap uses insert and erase methods in other places, do you need to do the same thing for the insert and remove the inserted COPYs together when erase?
Carrot added inline comments.Oct 25 2021, 4:42 PM
llvm/test/CodeGen/X86/distancemap.mir
72

I didn't dig deep into the code, just some general questions:

  1. The distances in DistanceMap seem to be the order of input. What's the mean with this change? I don't think you counted all new COPY MI. E.g. the one in line 56, right?

Line 56 has been correctly inserted into DistanceMap in function processTiedPairs. Lines 59..63 are missed, only line 64 is added in function convertInstTo3Addr. It is fixed by this patch.

  1. DistanceMap uses insert and erase methods in other places, do you need to do the same thing for the insert and remove the inserted COPYs together when erase?

If there are missed entries in DistanceMap, they should be added, otherwise noUseAfterLastDef doesn't work correctly. If there are extra entries in DistanceMap, they may not hurt current code, they are just garbage, it's better to remove them to prevent unintended future use.

Carrot updated this revision to Diff 382497.Oct 26 2021, 5:51 PM
Carrot edited the summary of this revision. (Show Details)

Thank pengfei's question, I did find another case that DistanceMap is not maintained correctly when unfolding memory operand.

pengfei accepted this revision.Oct 28 2021, 6:01 AM

LGTM.

This revision is now accepted and ready to land.Oct 28 2021, 6:01 AM
This revision was landed with ongoing or failed builds.Oct 28 2021, 11:12 AM
This revision was automatically updated to reflect the committed changes.