Bug in MachineInstr::isIdenticalTo

Project Infrastructure LLVM Dev List Archives
1

I have ran across a case where the function isIdenticalTo is return true for instructions that are not equivalent. The instructions in question are load/store instructions, and is causing a problem with MachineBranchFolding. The problem is this, I have two branches of a switch statement that are identical, except for the size of the store. Here is some cut-down LLVM-IR to showcase the issue:

switch.case: ; preds = %if.end

%tmp53 = extractelement <4 x i32> %format, i32 1 ; [#uses=1]

switch i32 %tmp53, label %if.then [

i32 1, label %switch.case55

i32 2, label %switch.case61

]

switch.case55: ; preds = %switch.case

%arrayidx = getelementptr i8 addrspace(1)* %conv3, i32 %tmp22 ; <i8 addrspace(1)*> [#uses=1]

%tmp59 = extractelement <4 x i32> %9, i32 0 ; [#uses=1]

%conv60 = trunc i32 %tmp59 to i8 ; [#uses=1]

store i8 %conv60, i8 addrspace(1)* %arrayidx

ret void

switch.case61: ; preds = %switch.case

%arrayidx64 = getelementptr i16 addrspace(1)* %conv, i32 %tmp22 ; <i16 addrspace(1)*> [#uses=1]

%tmp66 = extractelement <4 x i32> %9, i32 0 ; [#uses=1]

%conv67 = trunc i32 %tmp66 to i16 ; [#uses=1]

store i16 %conv67, i16 addrspace(1)* %arrayidx64

ret void

Notice how except for the sizes of the pointer, the sequence is the same. This translates into the following for my backend at the MI level.

BB#9: derived from LLVM BB %switch.case55

Live Ins: %R258 %R260 %R259

Predecessors according to CFG: BB#8

%R257 = CUSTOM_ADD_i32 %R260, %R258

%R258 = VEXTRACT_v4i32 %R259, 1

GLOBALTRUNCSTORE_i32 %R258, %R257, 8; mem:ST1[%arrayidx]

RETURN

BB#10: derived from LLVM BB %switch.case61

Live Ins: %R258 %R260 %R259

Predecessors according to CFG: BB#7

%R257 = LOADCONST_i32 1

%R257 = SHL_i32 %R258, %R257

%R257 = CUSTOM_ADD_i32 %R260, %R257

%R258 = VEXTRACT_v4i32 %R259, 1

GLOBALTRUNCSTORE_i32 %R258, %R257, 8; mem:ST2[%arrayidx64]

RETURN

Notice how except for the memory operand size on the truncating store, the last three instructions in BB#7 is the same as BB#8.

Now looking at isIdenticalTo, I don’t see any checks on the memory size. Since I don’t encode this information in the instruction, because it is encoded in the memory object, two different instructions can be considered identical for different memory sizes. I believe this is incorrect.

Here is my proposed patch for the issue:

Index: MachineInstr.cpp

MI_isIdenticalTo.patch (1.22 KB)

2

I have ran across a case where the function isIdenticalTo is return true for instructions that are not equivalent. The instructions in question are load/store instructions, and is causing a problem with MachineBranchFolding. The problem is this, I have two branches of a switch statement that are identical, except for the size of the store. Here is some cut-down LLVM-IR to showcase the issue:
switch.case: ; preds = %if.end
  %tmp53 = extractelement <4 x i32> %format, i32 1 ; <i32> [#uses=1]
  switch i32 %tmp53, label %if.then [
    i32 1, label %switch.case55
    i32 2, label %switch.case61
  ]
switch.case55: ; preds = %switch.case
  %arrayidx = getelementptr i8 addrspace(1)* %conv3, i32 %tmp22 ; <i8 addrspace(1)*> [#uses=1]
  %tmp59 = extractelement <4 x i32> %9, i32 0 ; <i32> [#uses=1]
  %conv60 = trunc i32 %tmp59 to i8 ; <i8> [#uses=1]
  store i8 %conv60, i8 addrspace(1)* %arrayidx
  ret void
switch.case61: ; preds = %switch.case
  %arrayidx64 = getelementptr i16 addrspace(1)* %conv, i32 %tmp22 ; <i16 addrspace(1)*> [#uses=1]
  %tmp66 = extractelement <4 x i32> %9, i32 0 ; <i32> [#uses=1]
  %conv67 = trunc i32 %tmp66 to i16 ; <i16> [#uses=1]
  store i16 %conv67, i16 addrspace(1)* %arrayidx64
  ret void

Notice how except for the sizes of the pointer, the sequence is the same. This translates into the following for my backend at the MI level.
BB#9: derived from LLVM BB %switch.case55
    Live Ins: %R258 %R260 %R259
    Predecessors according to CFG: BB#8
                        %R257<def> = CUSTOM_ADD_i32 %R260<kill>, %R258<kill>
                        %R258<def> = VEXTRACT_v4i32 %R259<kill>, 1
                        GLOBALTRUNCSTORE_i32 %R258<kill>, %R257<kill>, 8; mem:ST1[%arrayidx]
                        RETURN

BB#10: derived from LLVM BB %switch.case61
    Live Ins: %R258 %R260 %R259
    Predecessors according to CFG: BB#7
                        %R257<def> = LOADCONST_i32 1
                        %R257<def> = SHL_i32 %R258<kill>, %R257<kill>
                        %R257<def> = CUSTOM_ADD_i32 %R260<kill>, %R257<kill>
                        %R258<def> = VEXTRACT_v4i32 %R259<kill>, 1
                        GLOBALTRUNCSTORE_i32 %R258<kill>, %R257<kill>, 8; mem:ST2[%arrayidx64]
                        RETURN

Notice how except for the memory operand size on the truncating store, the last three instructions in BB#7 is the same as BB#8.

Now looking at isIdenticalTo, I don't see any checks on the memory size. Since I don't encode this information in the instruction, because it is encoded in the memory object, two different instructions can be considered identical for different memory sizes. I believe this is incorrect.

Here is my proposed patch for the issue:
Index: MachineInstr.cpp

--- MachineInstr.cpp (revision 122820)
+++ MachineInstr.cpp (working copy)
@@ -761,9 +761,23 @@
   // If opcodes or number of operands are not the same then the two
   // instructions are obviously not identical.
   if (Other->getOpcode() != getOpcode() ||
- Other->getNumOperands() != getNumOperands())
+ Other->getNumOperands() != getNumOperands() ||
+ Other->memoperands_empty() != memoperands_empty())
     return false;
+ if (!memoperands_empty()) {
+ // If we have mem operands, make sure that the sizes of the memoperands for each
+ // MI are the same. The values can be different, so lets only check the sizes.
+ // If the sizes between one of the memoperands differ, then the instructions are
+ // not identical.
+ for (MachineInstr::mmo_iterator mb1 = memoperands_begin(), mb2 = Other->memoperands_begin()
+ me = memoperands_end(); mb1 != me; ++mb1, ++mb2) {
+ if (mb1->getSize() != mb2->getSize() ||
+ mb1->getFlags() != mb2->getFlags() ||
+ mb1->getOffset() != mb2->getOffset()) {
+ return false;
+ }
+ }
+ }
+
   // Check operands to make sure they match.
   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
     const MachineOperand &MO = getOperand(i);

So, my question is, should isIdenticalTo take the memoperands into account? Is my patch correct? I almost feel like isIdenticalTo needs to be added to MachineMemOperand class.

You are right. It's not safe to return true if any pair of memoperands differ. Your patch looks fine to me.

Evan

3

Well, there are issues with the patch. I didn’t compile it when I wrote it up. Also, what about adding isIdenticalTo into the MachineMemOperand class instead of doing the check in MachineInstr. That would simplify this patch and allow the code to be used elsewhere.

My only other concern is the case where there is more than one machine mem operand and the ordering, if sorted, would be equivalent, but is unsorted. Could this case happen?

For example, using my instructions below, the following occurs.

GLOBALTRUNCSTORE_i32 %R258, %R257, 8; mem:ST1[%arrayidx] mem:ST2[%arrayidx64]

GLOBALTRUNCSTORE_i32 %R258, %R257, 8; mem:ST2[%arrayidx64] mem:ST1[%arrayidx]

Though I’ve never seen an instruction with two memory operands, the structure allows for it to occur. And the two instructions are technically equivalent, but the ordering is wrong. Is this a valid concern?

Micah

4

The MachineMemOperands are supposed to be used for optimizations only, your code should still be correct when stripping all memory operands.

I think you would be better off encoding the store size in the opcode.

/jakob

5

From: Jakob Stoklund Olesen [mailto:stoklund@2pi.dk]
Sent: Tuesday, January 04, 2011 11:55 AM
To: Villmow, Micah
Cc: llvmdev@cs.uiuc.edu
Subject: Re: [LLVMdev] Bug in MachineInstr::isIdenticalTo

> So, my question is, should isIdenticalTo take the memoperands into
account? Is my patch correct? I almost feel like isIdenticalTo needs to
be added to MachineMemOperand class.

The MachineMemOperands are supposed to be used for optimizations only,
your code should still be correct when stripping all memory operands.

[Villmow, Micah] I disagree with this as nothing in the documentation for the class states that it should be used for optimizations only. From the header file, " A description of a memory reference used in the backend ... This allows it to describe lowered loads and stores. " That is exactly what I am using it for.

I think you would be better off encoding the store size in the opcode.

[Villmow, Micah] While it might be nice, this would cause massive instruction opcode bloat. I already have over 500 load/store opcodes and storing the size in the instruction would probably triple or quadruple this amount. So not encoding it in the opcode is a decision to lower the amount of opcodes required.

6

Jakob is right in this instance. If you don't want to encode this in the *opcode* you can always add it as an imm operand to the instruction, avoiding bloat.

-Chris