This is an archive of the discontinued LLVM Phabricator instance.

[LiveDebugValues] Track transferring variable's value from one register to another
ClosedPublic

Authored by NikolaPrica on Mar 2 2018, 7:37 AM.

Details

Summary

During the execution of long functions or functions that have a lot of inlined code could come to the situation where variable's value could be transferred from one register to another. Also some variables values could be moved from subreg to reg by the ABI, like on the figure 1. In that situation we have variable's value in two registers. First location could be lost at some moment but second location will probably be used at some point and we could use that location to get this variable's value. This patch adds support for tracking such second location. The transfer is recognized only if destination register is callee saved register.

renamable $s4_64 = SLL64_32 renamable $s2, implicit killed $s2_64 
...                                                                                                
%s4_64<def> = or64 %s2_64<kill>, %zero_64                                
--------------------------------------------------------------------------------
Figure 1: Transferring register values from s2 to s4 with killing s2

Since I do not have small test example I will insert here part of MachineInstruction stream that I have been working on:

BB#3: derived from LLVM BB %if.end4
Live Ins: %GP_64 %S0_64 %S1_64 %S3_64 %S4_64 %S5_64 %S7_64
Predecessors according to CFG: BB#1 BB#2
    ...
    DBG_VALUE %S1_64, %noreg, !"tid", <!606>; line no:81
    %S6_64<def> = SLL64_32 %S1, %S1_64<imp-use,kill>; dbg:singlefunction.c:141:6 <-- copy like instruction
    ...
    %A0_64<def> = OR64 %S0_64, %ZERO_64; dbg:singlefunction.c:141:6
    %A1_64<def> = OR64 %S6_64, %ZERO_64; dbg:singlefunction.c:141:6 <- tid is indeed second argument of the following function call
    JALR64Pseudo %T9_64, <regmask ... %S1_64 %S2_64 %S3_64 %S4_64 %S5_64 %S6_64 %S7_64>, ... ; dbg:singlefunction.c:141:6
      * %A2_64<def> = OR64 %S7_64, %ZERO_64; dbg:singlefunction.c:141:6
    %S1_64<def> = OR64 %V0_64, %ZERO_64; dbg:singlefunction.c:141:6
    DBG_VALUE %S6_64, %noreg, !"tid", <!606>; line no:81  <-- This DBG_VALUE is feature of this patch
    DBG_VALUE %S1_64, %noreg, !"child_oid_cur", <!606>; line no:134
    %V0<def> = LW %FP_64, 8292; mem:LD4[%cur_local_err](tbaa=!616)(dereferenceable) dbg:singlefunction.c:144:6
    DBG_VALUE %V0, %noreg, !"cur_local_err", <!606>; line no:87
    BEQ %V0, %ZERO, <BB#6>, %AT<imp-def>; dbg:singlefunction.c:144:6
      * NOP; dbg:singlefunction.c:144:6
Successors according to CFG: BB#6 BB#4

Diff Detail

Event Timeline

NikolaPrica created this revision.Mar 2 2018, 7:37 AM
NikolaPrica edited the summary of this revision. (Show Details)Mar 2 2018, 7:39 AM
NikolaPrica edited the summary of this revision. (Show Details)Mar 2 2018, 7:50 AM

That's an interesting idea, thanks! The first thought that came to my mind is: why not implement this functionality in DbgValueHistoryCalculator or DwarfDebug::buildLocationList(), or much earlier in LiveDebugVariables? I suppose that by doing it in LiveDebugValues there is a faint chance that we might be able to propagate a backup DBG_VALUE beyond basic block boundaries, but I'm not convinced that that is worth it. I we can I would prefer to keep the mandate of LiveDebugValues well-defined, i.e.: perform cross-basic-block propagation. IIUC, this patch is doing something that is strictly local, so I would feel better about it in a context that also does only local scan of one basic block, like buildLocationList().

What do you think?

Some comments on the MIPS part of this patch inlined.

I believe we should extend the tablegen class Instruction to record if this instruction is a possible copy instruction, that we can just use TableGen to portions of the work.

include/llvm/CodeGen/TargetInstrInfo.h
825–826 ↗(On Diff #136748)

Nit: spellings. spcific -> specific, extra space after from, and othere -> another.

lib/CodeGen/LiveDebugValues.cpp
450

basci -> basic.

477

Space after the '//'

478

Sentence is a bit garbled.

649

incosiste -> inconsistent.

lib/Target/Mips/MipsSEInstrInfo.cpp
184 ↗(On Diff #136748)

Nit on the implementation here. Rather than recognising large amounts of instructions with a switch statement, instead extend the TableGen class Instruction in include/llvm/Target/Target.td to include the field, 'isPossibleCopy' like we have for isReturn, .. etc. Some other files would need to be touched as well to account for this new field.

The the generic interface can check that bit before dispatching to the target to handle cases such as MIPS' usage of OR. Other targets would probably just return true.

217–218 ↗(On Diff #136748)

Nit: this is incorrect. On MIPS64, a value that is smaller than 32 bits will be type legalized to i32 and assigned to the GPR32 register class, so copies of those values will use OR.

Instead test that the second operand is Mips::ZERO or Mips::ZERO_64 for those two 'or' cases if they're joined together. (Most uses of Subtarget.isGP64bit() are checking the wrong thing.)

sdardis added inline comments.Mar 5 2018, 7:26 AM
lib/Target/Mips/Mips16InstrInfo.cpp
102 ↗(On Diff #136748)

Missing Move32R16.

lib/Target/Mips/MipsSEInstrInfo.cpp
184 ↗(On Diff #136748)

Not a copy instruction.

185 ↗(On Diff #136748)

Not a copy instruction.

188–202 ↗(On Diff #136748)

Missing the microMIPS versions of these instructions (except the ones are microMIPS).

203 ↗(On Diff #136748)

Missing CFCMSA.

204 ↗(On Diff #136748)

Missing the microMIPS versions of this and the next instruction.

215 ↗(On Diff #136748)

Missing the microMIPS version of this instruction.

@sdardis @aprantl Thank you for your comments!

The first thought that came to my mind is: why not implement this functionality in DbgValueHistoryCalculator or DwarfDebug::buildLocationList(), or much earlier in LiveDebugVariables? I suppose that by doing it in LiveDebugValues there is a faint chance that we might be able to propagate a backup DBG_VALUE beyond basic block boundaries, but I'm not convinced that that is worth it.

It wouldn't work completely in DbgValueHistoryCalculator or DwarfDebug::buildLocationList() since newly added backup DBG_VALUE location would be inserted only in block where copy/move occurs. Such new DBG_VALUE could be also propagated to successive blocks as it is been done now in LiveDebugValues.

If we can I would prefer to keep the mandate of LiveDebugValues well-defined, i.e.: perform cross-basic-block propagation. IIUC, this patch is doing something that is strictly local, so I would feel better about it in a context that also does only local scan of one basic block, like buildLocationList().

I have an idea that could make this on local scan of one basic block. My original taught was to keep first location as long as it could be kept in case that backup location is some register that is clobbered by the reg mask, but if backup location could survive up to the end of basic block it could be propagated instead of original location? In that way scan would be performed only locally.

I will need some more time to look into LiveDebugVariables pass and see whether this could be done there.

bjope added a subscriber: bjope.Mar 11 2018, 3:43 PM

@aprantl > I've checked LiveDebugVariables pass and there is already such functionality but it performs only in blocks where DBG_VALUE is definded but copy instructions could occur in some further block. Maybe I should try to follow debuged value register location accros multiple blocks here and see whether it is copied to some other virtual register location?

lib/Target/Mips/MipsSEInstrInfo.cpp
184 ↗(On Diff #136748)

@sdardis > I've came across a lot of situations of using this instructions that seemed to be copy like instruction. As I followed movement from register to register and usage of such registers it looked to me that same variable is used. Is your concern that bits from 32-63 will be undefined when transferring value from 32bit reg to 64 reg or that this new 64bit value won't be used properly as it is differently represented or both? As I've seen it is used over functions parameter that is later used as another functions parameter. For example I had following situation:

DBG_VALUE %S1_64, %noreg, !"tid", <!606>; line no:81 <- "tid" has int32 type
%S6_64<def> = SLL64_32 %S1, %S1_64<imp-use,kill>; dbg:singlefunction.c:141:6
...
%A1_64<def> = OR64 %S6_64, %ZERO_64; dbg:singlefunction.c:141:6 <- tid is indeed second argument of the following function call
JALR64Pseudo %T9_64, <regmask ... %S1_64 %S2_64 %S3_64 %S4_64 %S5_64 %S6_64 %S7_64>, ... ; dbg:singlefunction.c:141:6

"tid" is defined in last instruction call as "i32 signext %tid" in function argument list. It is propagated in other function calls in same way.

If we can't consider this as copy/move like instruction, do you think that such situations should be modelled earlier in instruction selection phase?

@aprantl > I've checked LiveDebugVariables pass and there is already such functionality but it performs only in blocks where DBG_VALUE is definded but copy instructions could occur in some further block. Maybe I should try to follow debuged value register location accros multiple blocks here and see whether it is copied to some other virtual register location?

What "here" are you referring to? LiveDebugVariables should be strictly doing basic-block-local analysis. LiveDebugValues should be the only pass doing cross-bb data flow analysis. If you insist that the cross-bb part is important then the cross-bb part must be done in LiveDebugValues. I don't think that you will have a lot of situations where value is in the same register on all paths to a subsequent basic block where the variable isn't also described by a fresh DBG_VALUE. Have you collected any data that shows that supporting this would be worthwhile?

sdardis added inline comments.Mar 13 2018, 3:22 AM
lib/Target/Mips/MipsSEInstrInfo.cpp
184 ↗(On Diff #136748)

It's a sort of a move.

%S6_64<def> = SLL64_32 %S1, %S1_64<imp-use,kill>; dbg:singlefunction.c:141:6

This is a def of $s6 with the value of $s1 sign-extended from bit 31.

Instructions which define 32 bit results on MIPS64 almost always sign-extend their result to the wider register size. Although the MIPS64 backend in LLVM has 32bit registers and 64bit registers, that's an implementation detail as MIPS doesn't have sub-register addressing.

The N64 and N32 ABIs require that values smaller that i32s are promoted to i32s, and that i32s are sign-extended to i64s.

SLL64_32 is a quirk of the MIPS64 backend implementation in that it is an instruction that operates on 32 bit gprs and produces a 64bit gpr result.

So, I suppose you could consider SLL64_32 a move as such.

185 ↗(On Diff #136748)

You can ignore this comment given my new one above.

What "here" are you referring to?

Oh, sorry. I meant in LiveDebugVariables.

I don't think that you will have a lot of situations where value is in the same register on all paths to a subsequent basic block where the variable isn't also described by a fresh DBG_VALUE.

Yes. I agree with you. If that would be the case then the problem would be elsewhere. I will update patch then.

Have you collected any data that shows that supporting this would be worthwhile?

I have some examples but their MIR seems to big. I've also managed to produce test case for X86 but the example seems to big. In this cases idea of tracking copies/moves of variables register locations could work on basic block level. I will attach them just as an example. Would it be fine to produce MIR from smaller example and alter it so it could cover all code?



What "here" are you referring to?

Oh, sorry. I meant in LiveDebugVariables.

Okay. LiveDebugVariables definitely should not attempt to do anything non-local. That's LiveDebugValues' job.

I don't think that you will have a lot of situations where value is in the same register on all paths to a subsequent basic block where the variable isn't also described by a fresh DBG_VALUE.

Yes. I agree with you. If that would be the case then the problem would be elsewhere. I will update patch then.

Have you collected any data that shows that supporting this would be worthwhile?

I have some examples but their MIR seems to big. I've also managed to produce test case for X86 but the example seems to big. In this cases idea of tracking copies/moves of variables register locations could work on basic block level. I will attach them just as an example.

Sorry I should have been more specific, too :-) I meant, have you collected any data that the *cross-bb propagation* would be beneficial. I totally believe that the local part is worthwhile!

Would it be fine to produce MIR from smaller example and alter it so it could cover all code?

Sure! Yes, a smaller, handcrafted test is likely easier to understand and update than a large example generated from source.

  • adrian



NikolaPrica edited the summary of this revision. (Show Details)Mar 19 2018, 11:31 AM

I've changed patch to perform locally now by restricting copy instructions recognition to ones that copy to callee saved registers.
I've also added test for mips64 that I've managed to find without making any changes to MIR. Also I've extended this functionality for recognizing some of X86 and ARM instructions (I've marked some of instructions in copyPhysReg TII method). I suppose that this could be extended even more by labeling other instructions as isMoveReg but I'm not familiar with other architectures.

NikolaPrica retitled this revision from WIP: [LiveDebugValues] Track transferring variable's value from one register to another to [LiveDebugValues] Track transferring variable's value from one register to another.

Updated test to recognize metadata id number.

Some small nits inlined, I've mostly looked at the non debug related parts. A lot of my comments are the MIPS .td parts can be summarized as: where possible, modify the underlying *_DESC or MXC1 classes where possible rather than wrapping the definition of the instruction with a 'isRegMove = 1'. There are some cases where it can't be done as the instruction description class is shared multiple other instructions which are not moves.

Can you also provide some additional tests, e.g. tracking floating point values, and integer/floating point tests for X86 and ARM?

include/llvm/MC/MCInstrDesc.h
251 ↗(On Diff #139112)

Return true if the instruction is a register to register move.

lib/CodeGen/LiveDebugValues.cpp
546

If it is a copy instruction, return true along with @SrcReg

548

an instruction

555

Extra space between the which and we.

556

This sentence fragment is unclear.

568

if @MI is a register copy instruction that copies a previously tracked value

lib/Target/ARM/ARMInstrInfo.td
3355 ↗(On Diff #139112)

From looking further down this .td file, it appears the coding style would put the 'isMoveReg = 1' as an additional part of the let clause for this instruction.

lib/Target/Mips/MicroMipsDSPInstrInfo.td
528 ↗(On Diff #138969)

Modify WRDSP_MM_DESC rather than adding a '{ let isMoveReg = 1; } to the definition here.

lib/Target/Mips/MicroMipsInstrInfo.td
634–638 ↗(On Diff #139112)

Modify the MoveFromHILOMM, MoveMM16, MovePMM16 classes rather than wrapping the instruction definitions in an isMoveReg = 1 scope.

lib/Target/Mips/Mips64InstrInfo.td
294–301 ↗(On Diff #139112)

Modify the MoveToLOHI class instead of wrapping isMoveReg = 1 scope here.

lib/Target/Mips/MipsDSPInstrInfo.td
1167–1170 ↗(On Diff #139112)

Modify the M(F|T)(HI|LO)_DESC classes instead.

1226–1228 ↗(On Diff #139112)

Modify the (RD|WR)DSP_DESC classes instead.

lib/Target/Mips/MipsInstrFPU.td
478–512 ↗(On Diff #139112)

Modify the M(F|T)C1_FT class instead.

lib/Target/Mips/MipsMSAInstrInfo.td
2886 ↗(On Diff #139112)

Modify the CFCMSA_DESC class as well.

2940 ↗(On Diff #139112)

Modify the CTCMSA_DESC class instead.

3292 ↗(On Diff #139112)

Modify the MOVE_V_DESC class instead.

lib/Target/Mips/MipsSEInstrInfo.cpp
183 ↗(On Diff #139112)

Simplify the implementation here by switching over the opcode, and in the default case, directly returning the value of TargetInstrInfo::isCopyInstr(MI).

Add a comment stating we check for the common cases of 'or', as it's MIPS' preferred move instruction for GPRs but we have to check the operands to ensure that is the case. Other move instructions for MIPS are directly identifiable.

test/DebugInfo/MIR/Mips/live-debug-value-reg-copy.mir
1 ↗(On Diff #139112)

Can you also add a test case of floating point values?

3 ↗(On Diff #139112)

transferning -> transferring

4 ↗(On Diff #139112)

Missing the rest of the sentence.

aprantl added inline comments.Mar 20 2018, 9:07 AM
lib/CodeGen/LiveDebugValues.cpp
245

can you rename this to makeTransferDebugPair or perhaps make this into a constructor of TransferDebugPair?

I've added test case for MIPS integer/float point values and tests for tracking integer values for X86 and ARM. Because it is hard to find a small real example I produced test cases by manually altering the machine IR but I'm not quite sure about producing test case for floating points for X86 and ARM. Basically what I've done is add 'isMoveReg = 1' to the instructions that are mentioned in TargetInstrInfo::copyPhysReg. Maybe someone else who is more familiar with ARM/X86 could assist or take over if everything else is fine?

I'm afraid this is getting too broad in scope for me to comfortably review this. In order to make progress on this, would it be possible to split out the addition of isMoveReg to a separate patch get that reviewed by developers familiar with the backends? Once that is in, we should be able to move ahead with the debug info part quickly.

Sure. I will do so. Do you think that it would be better to provide 3 different patches for X86/ARM/MIPS separately or should I post it all in one?

I'm not sure. I think it's important to reach consensus first that the new attribute is the right way forward. So one large patch may be better initially.

Updated patch to match TII isCopyInstr instruction.

aprantl added inline comments.Jun 7 2018, 12:25 PM
lib/CodeGen/LiveDebugValues.cpp
380

we usually spell this \p Transfers

390

please clang-format the patch

548

typo

test/DebugInfo/MIR/ARM/live-debug-values-reg-copy.mir
6

below

8

Since you are only checking one variable, you could reduce the test case quite a bit by stripping out all debug info for the other variables.

21

... such as this.

Ka-Ka added a subscriber: Ka-Ka.Jun 7 2018, 1:20 PM
NikolaPrica marked 6 inline comments as done.Jun 13 2018, 8:17 AM

Ping.

@aprantl do you have any more concerns or is this ready for commit?

aprantl added inline comments.Jun 20 2018, 8:47 AM
lib/CodeGen/LiveDebugValues.cpp
243

Just double-checking: 0 is always an invalid register number?

381

These two lines sound confusing :-)
Are we inserting or not?

382

\p OldVarID for consistency?

383

Isn't it the other way round: when NewReg is non-zero it is the new location?

570

It would be even better if this comment would explain *why* we want to recognize them.

733

You could define an enum for improved readability:

enum : bool {
  dontTransferChanges = false;
  transferChanges = true;
};
819

I *think* that this block is equivalent to:
TFI->determineCalleeSaves(MF, CalleeSavedRegs, RegScavenger());

test/DebugInfo/MIR/X86/live-debug-values-reg-copy.mir
25

Can you strip out all the unnecessary metadata? I don't think we need the !tbaa stuff or the !dbg locations on most of the instructions.

Thanks, this is looking pretty good now. I just have a few more small details, mostly to make it easier to read and understand what's going on.

NikolaPrica marked 5 inline comments as done.Jun 21 2018, 3:03 PM

I thought that comments were submitted along with patch.

lib/CodeGen/LiveDebugValues.cpp
243

Yes. In printReg function there is :

if (!Reg)
  OS << "$noreg";

At this stage only valid physical registers should come into consideration. Also it is impossible to forward 0 from transferRegisterCopy since we have check if (!isCalleSavedReg(DestReg)) there.

819

determineCalleeSaves requires pointer as third argument. Is this solution with make_unique better?

aprantl added inline comments.Jul 2 2018, 8:45 AM
lib/CodeGen/LiveDebugValues.cpp
385

Actually, it is weird to have a function called make... that doesn't return anything. Should we call it insertTransferDebugPair instead?

773

Ugh. This is now really confusing: We are both calling the transfer function of the data flow analysis transfer, and the action of moving a value from one place to another a transfer.

I think we should either rename Transfers to Moves or transfer... to process...

test/DebugInfo/MIR/Mips/live-debug-values-reg-copy.mir
90

do you really need all these different DILocations?

I think we're almost there now!

uabelho added a subscriber: uabelho.Jul 6 2018, 2:38 AM

renamed makeTransferDebugPair -> insertTransferDebugPair
renamed transfer -> process
removed unnecessary DILocation metadata from tests

aprantl accepted this revision.Jul 11 2018, 11:14 PM

Thanks!

This revision is now accepted and ready to land.Jul 11 2018, 11:14 PM

Thank you for review!

This revision was automatically updated to reflect the committed changes.