[LLVMdev] Bug in MachineInstr::isIdenticalTo

[Evan Cheng]

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>