thr3ads.net - llvm dev - [LLVMdev] Bug in MachineInstr::isIdenticalTo [Jan 2011]

If this information is useful, please help other people find it:
Share via:

Villmow, Micah

2011-Jan-04 19:08 UTC

[LLVMdev] Bug in MachineInstr::isIdenticalTo

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.

Thoughts?
Micah
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20110104/cf0f8d22/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: MI_isIdenticalTo.patch
Type: application/octet-stream
Size: 1253 bytes
Desc: MI_isIdenticalTo.patch
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20110104/cf0f8d22/attachment.obj>

Evan Cheng

2011-Jan-04 19:47 UTC

head link

[LLVMdev] Bug in MachineInstr::isIdenticalTo

On Jan 4, 2011, at 11:08 AM, Villmow, Micah wrote:
> 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
>  
> Thoughts?
> Micah
>
<MI_isIdenticalTo.patch>_______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20110104/019fb41c/attachment.html>

Villmow, Micah

2011-Jan-04 19:52 UTC

head link

[LLVMdev] Bug in MachineInstr::isIdenticalTo

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<kill>, %R257<kill>, 8; mem:ST1[%arrayidx]
mem:ST2[%arrayidx64]
GLOBALTRUNCSTORE_i32 %R258<kill>, %R257<kill>, 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

From: Evan Cheng [mailto:evan.cheng at apple.com]
Sent: Tuesday, January 04, 2011 11:48 AM
To: Villmow, Micah
Cc: llvmdev at cs.uiuc.edu
Subject: Re: [LLVMdev] Bug in MachineInstr::isIdenticalTo


On Jan 4, 2011, at 11:08 AM, Villmow, Micah wrote:


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



Thoughts?
Micah
<MI_isIdenticalTo.patch>_______________________________________________
LLVM Developers mailing list
LLVMdev at cs.uiuc.edu<mailto:LLVMdev at cs.uiuc.edu>        
http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20110104/6cbd8695/attachment.html>

Jakob Stoklund Olesen

2011-Jan-04 19:55 UTC

head link

[LLVMdev] Bug in MachineInstr::isIdenticalTo

On Jan 4, 2011, at 11:08 AM, Villmow, Micah wrote:
> 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.

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

/jakob

Villmow, Micah

2011-Jan-04 20:13 UTC

head link

[LLVMdev] Bug in MachineInstr::isIdenticalTo

> -----Original Message-----
> From: Jakob Stoklund Olesen [mailto:stoklund at 2pi.dk]
> Sent: Tuesday, January 04, 2011 11:55 AM
> To: Villmow, Micah
> Cc: llvmdev at cs.uiuc.edu
> Subject: Re: [LLVMdev] Bug in MachineInstr::isIdenticalTo
> 
> 
> On Jan 4, 2011, at 11:08 AM, Villmow, Micah wrote:
> 
> > 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.> /jakob
>

Possibly Parallel Threads

Search for more maybe matching threads

llvm dev - Jan 2011 - [LLVMdev] Bug in MachineInstr::isIdenticalTo

[LLVMdev] Bug in MachineInstr::isIdenticalTo

[LLVMdev] Bug in MachineInstr::isIdenticalTo

[LLVMdev] Bug in MachineInstr::isIdenticalTo

[LLVMdev] Bug in MachineInstr::isIdenticalTo

[LLVMdev] Bug in MachineInstr::isIdenticalTo

Possibly Parallel Threads