[LLVMdev] Bug in MachineInstr::isIdenticalTo

[Villmow, Micah]

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>