[llvm-bugs] [Bug 39277] New: Legalisation of smulo can end up oscillating between two legalisations infinitely

[via llvm-bugs]

https://bugs.llvm.org/show_bug.cgi?id=39277

            Bug ID: 39277
           Summary: Legalisation of smulo can end up oscillating between
                    two legalisations infinitely
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: Backend: ARM
          Assignee: unassignedbugs at nondot.org
          Reporter: simonas+llvm.org at kazlauskas.me
                CC: llvm-bugs at lists.llvm.org

Created attachment 21004
  --> https://bugs.llvm.org/attachment.cgi?id=21004&action=edit
Reproduction file

On the ARM backend, when the attached file is compiled with following command
(the file necessary to reproduce is attached):

    llc lib.ll -O0

It is possible for the SelectionDAG Combiner to keep oscillating between two
instructions infinitely. 

This is still reproducible at revision D53067.

---

Following is an explanation of what happens:

Everything begins with SelectionDAG attempting to leaglise `smulo`:

    Legalizing: t11: i32,i32 = smulo t2, Constant:i32<0>
    <...>
    Succesfully expanded node
     ... replacing: t11: i32,i32 = smulo t2, Constant:i32<0>
         with:      t12: i32 = mul t2, Constant:i32<0>
          and:      t17: i32 = setcc t13, t15, setne:ch

    Legalizing: t17: i32 = setcc t13, t15, setne:ch
    <...>
    Succesfully expanded node
     ... replacing: t17: i32 = setcc t13, t15, setne:ch
         with:      t19: i32 = select_cc t13, t15, Constant:i32<1>,
Constant:i32<0>, setne:ch

    Legalizing: t19: i32 = select_cc t13, t15, Constant:i32<1>,
Constant:i32<0>, setne:ch
    <...>
    Successfully custom legalized node
     ... replacing: t19: i32 = select_cc t13, t15, Constant:i32<1>,
Constant:i32<0>, setne:ch
         with:      t22: i32 = ARMISD::CMOV Constant:i32<0>, Constant:i32<1>,
Constant:i32<1>, Register:i32 $cpsr, t21

Ending up with the following DAG:

      t0: ch = EntryToken
      t2: i32,ch = CopyFromReg t0, Register:i32 %7
      t12: i32 = mul t2, Constant:i32<0>
        t7: ch = CopyToReg t0, Register:i32 %17, t12
              t13: i32 = mulhs t2, Constant:i32<0>
              t15: i32 = sra t12, Constant:i32<31>
            t21: glue = ARMISD::CMPZ t13, t15
          t22: i32 = ARMISD::CMOV Constant:i32<0>, Constant:i32<1>,
Constant:i32<1>, Register:i32 $cpsr, t21
        t9: ch = CopyToReg t0, Register:i32 %18, t22
      t10: ch = TokenFactor t7, t9

So far, so good. Then, LLVM "combines the CMOV into something else:

    Combining: t22: i32 = ARMISD::CMOV Constant:i32<0>, Constant:i32<1>,
Constant:i32<1>, Register:i32 $cpsr, t21
    Creating new node: t23: i32 = sub t13, t15
    Creating new node: t24: i32 = ARMISD::CMOV t23, Constant:i32<1>,
Constant:i32<1>, Register:i32 $cpsr, t21
    Creating new node: t26: i32 = AssertZext t24, ValueType:ch:i1
     ... into: t26: i32 = AssertZext t24, ValueType:ch:i1

Ending up with (I believe, constructed by hand)

      t0: ch = EntryToken
      t2: i32,ch = CopyFromReg t0, Register:i32 %7
      t12: i32 = mul t2, Constant:i32<0>
        t7: ch = CopyToReg t0, Register:i32 %17, t12
              t13: i32 = mulhs t2, Constant:i32<0>
              t15: i32 = sra t12, Constant:i32<31>
            t21: glue = ARMISD::CMPZ t13, t15
            t23: i32 = sub t13, t15
           t24: i32 = ARMISD::CMOV t23, Constant:i32<1>, Constant:i32<1>,
Register:i32 $cpsr, t21
          t26: i32 = AssertZext t24, ValueType:ch:i1
        t9: ch = CopyToReg t0, Register:i32 %18, t26
      t10: ch = TokenFactor t7, t9

Then:

    Combining: t15: i32 = sra t12, Constant:i32<31>
     ... into: t12: i32 = mul t2, Constant:i32<0>
    Combining: t13: i32 = mulhs t2, Constant:i32<0>
     ... into: t3: i32 = Constant<0>
    Combining: t23: i32 = sub Constant:i32<0>, t12
     ... into: t12: i32 = mul t2, Constant:i32<0>
    Combining: t24: i32 = ARMISD::CMOV t12, Constant:i32<1>, Constant:i32<1>,
Register:i32 $cpsr, t21
    Creating new node: t27: i32 = ARMISD::CMOV Constant:i32<0>,
Constant:i32<1>, Constant:i32<1>, Register:i32 $cpsr, t21
    Creating new node: t28: i32 = AssertZext t27, ValueType:ch:i1
     ... into: t28: i32 = AssertZext t27, ValueType:ch:i1

Going the full circle back to the original DAG, which it inspects again and...

    Combining: t27: i32 = ARMISD::CMOV Constant:i32<0>, Constant:i32<1>,
Constant:i32<1>, Register:i32 $cpsr, t21
    Creating new node: t29: i32 = sub Constant:i32<0>, t12
    Creating new node: t30: i32 = ARMISD::CMOV t29, Constant:i32<1>,
Constant:i32<1>, Register:i32 $cpsr, t21
    Creating new node: t31: i32 = AssertZext t30, ValueType:ch:i1
     ... into: t31: i32 = AssertZext t30, ValueType:ch:i1

ad nauseam.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20181013/20835270/attachment-0001.html>