[livevar] Live variables missed physical register use of aliased definition

[llvmbot]

Bugzilla Link	337
Resolution	FIXED
Resolved on	Nov 07, 2018 00:17
Version	1.0
OS	All
Attachments	Test Case Directory Including Makefile And Binary
Reporter	LLVM Bugzilla Contributor
CC	@lattner

Extended Description

The attached test case loads two longs from global constants (7 and 49), compares them with SetLE, casts them to int, and returns the value from main. This should give a program with a result value of 0 or 1. However, it always returns 0. It should return 1 because 7 <= 49.

Here's the test case:

%global_long_1 = linkonce global long 7 %global_long_2 = linkonce global long 49

implementation ; Functions:

declare void %exit(int)

int %main() { %long_1 = getelementptr long %global_long_1, long 0 %long_2 = getelementptr long %global_long_2, long 0

    %l1 = load long* %long_1
    %l2 = load long* %long_2

    %cond = setle long %l1, %l2
    %cast2 = cast bool %cond to int
    ret int %cast2

}

[llvmbot]

You're welcome. I wasn't really looking but I'm glad I stumbled across it. Looks like Stacker was finally useful for something :)

I've confirmed the fix in Stacker. All 52 tests now pass. Thanks for the quick fix.

[lattner]

Fixed. Testcase here: test/Regression/CodeGen/Generic/2004-05-09-LiveVarPartialRegister.llx

Patch here: http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20040510/014205.html

Thanks again for finding this Reid!

-Chris

[lattner]

Even better! I've touch tested the patch on the multisource benchmarks and povray, and it seems to work, so I committed it. If the nightly tester likes it, I will close this bug.

I checked the testcase in as: test/Regression/CodeGen/Generic/2004-05-09-LiveVarPartialRegister.llx

Patch here: http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20040510/014205.html

Thanks for distilling this testcase Reid: this is a nasty scary bug. I think it can only currently come up in cases involving 'long' comparisons (as you noted, not seteq or setne), and only when the register pressure is just right, but it could effect other targets worse in the future and it's good to stomp on it now. :)

-Chris

[llvmbot]

Linear scan is not affected by this because it works around it:

In LiveIntervals::handleRegisterDef() when it works on a physical register it marks a def as defining all its aliases:

        handlePhysicalRegisterDef(mbb, mi, getOrCreateInterval(reg));
        for (const unsigned* as = mri_->getAliasSet(reg); *as; ++as)
            handlePhysicalRegisterDef(mbb, mi, getOrCreateInterval(*as));

Now if we mark all uses of aliases as using the originally defined register this can save us from constructing quite a few live intervals :-)

[lattner]

Alkis, this is the patch that I'm considering:

=================================================================== RCS file: /home/vadve/shared/PublicCVS/llvm/lib/CodeGen/LiveVariables.cpp,v retrieving revision 1.30 diff -u -r1.30 LiveVariables.cpp --- LiveVariables.cpp 1 May 2004 21:24:24 -0000 1.30 +++ LiveVariables.cpp 10 May 2004 05:02:22 -0000 @@ -126,6 +126,12 @@ void LiveVariables::HandlePhysRegUse(unsigned Reg, MachineInstr *MI) { PhysRegInfo[Reg] = MI; PhysRegUsed[Reg] = true; +

• for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg);
• unsigned Alias = *AliasSet; ++AliasSet) {
• PhysRegInfo[Alias] = MI;
• PhysRegUsed[Alias] = true;

• } }

  void LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI) {

This fixes this bug, but I haven't run a full test run yet. I will do so tommorow assuming you don't see a problem with this.

-Chris

[lattner]

So... Alkis.

This bug gets back to that small issue that we talked about earlier w.r.t. live variable analysis and partial register uses. The problem is that we have code that looks like this:

AL = ... ... AH = ... ... = AX

The problem is that the LiveVariables::HandlePhysRegUse does not mark a use of AX as being a use of AL or AH (it only marks it as a use of AX. It considers both AL and AH to be defs of AX and the AH def was the last def of AX, so it considers the use of AX to only use the AH def, not the AL def). Because of this, LiveVar decides that AL is DEAD at its definition, causing the register allocator to insert the instruction clobbering EAX after the def of AL.

I think that this issue could very well effect linear scan as well as the local allocator, it's just easier to trigger it with the local allocator because it makes much worse allocation decisions.

I am basically thinking of changing LiveVariables::HandlePhysRegUse to mark all aliases as uses (which I could have sworn we used to do). Do you see a problem with doing this, specifically do you see an impact on linear scan?

-Chris

[llvmbot]

No worries. I'm not in a rush for it and I have a workaround.

[lattner]

More specifically, the local allocator is using using the EAX register to reload a stack slot, even though there is a value in the AL register that is live:

setbe %AL ; Def mov %EAX, DWORD PTR [%ESP + 8] ; clobber cmp %EAX, %EDX setle %BL cmove %BX, %AX ; Use

I probably won't get a chance to fix this until tommorow, but it's a great catch. :)

-Chris

[llvmbot]

Confirming that -regalloc=linearscan fixes the problem. Here's the assembly difference:

bash-2.05b$ diff setcond.s setcond.s1 11c11,12 < mov DWORD PTR [%ESP + 4], %ESI

  mov DWORD PTR [%ESP + 8], %ESI
  mov DWORD PTR [%ESP + 4], %EDI

15,18c16,19 < mov %EAX, DWORD PTR [%EAX + 4] < mov %EDX, OFFSET global_long_2 < mov %ESI, DWORD PTR [%EDX] < mov %EDX, DWORD PTR [%EDX + 4]

  mov %EDX, DWORD PTR [%EAX + 4]
  mov %EAX, OFFSET global_long_2
  mov %ESI, DWORD PTR [%EAX]
  mov %EDI, DWORD PTR [%EAX + 4]

20d20 < mov DWORD PTR [%ESP + 8], %EAX 22,23c22 < mov %EAX, DWORD PTR [%ESP + 8] < cmp %EAX, %EDX

  cmp %EDX, %EDI

28,29c27 < mov %AL, %BL < movsx %EAX, %AL

  movsx %EAX, %BL

32c30,31 < mov %ESI, DWORD PTR [%ESP + 4]

  mov %EDI, DWORD PTR [%ESP + 4]
  mov %ESI, DWORD PTR [%ESP + 8]

[lattner]

Actually, this looks like a really nasty bug in the local register allocator! I'll take a look into it (which may take some time), but in the meantime you should be able to pass -regalloc=linearscan into LLC or LLI as a workaround.

Thanks for finding this!

-Chris

[lattner]

This smells like a codegen bug. The test that you submitted works with -regalloc=linearscan but fails with the default allocator. I'll dig in.

-Chris

[llvmbot]

Please note, the bug occurs only when comparing loaded values. If you use direct constants (i.e. cast long 49 to long) then the correct result value is returned.

For this reason, I suspect the problem is not related to bool to int cast used to return the value from main().

[lattner]

Mine.

I'll take a look! Thanks Reid!

[llvmbot]

assigned to @lattner