Page MenuHomePhabricator

[DAGCombiner] unwrap truncated subtraction operand for rol generation in matchRotateSub
Needs ReviewPublic

Authored by jianye.chen on Aug 18 2018, 6:05 PM.

Details

Summary

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

This patch addresses the issue where if the subtraction operand is ISD::TRUNCATE, it might not get matched for rotation instruction generation.
This issue reproduces if an truncation is generated before subtraction for its operand, while Pos is not truncated twice.
i8/i32/i64 does not generate truncates before subtraction (t10), which avoids this issue.

For actual demonstration of the issue, see, https://godbolt.org/g/vsM24w (commented by Simon Pilgrim)
Another issue in 15880 regarding i64 seems already fixed. "if you perform two back-to-back rotates to an expression, the 8 and 32 bit versions use back-to-back rol instructions, the 16 bit version uses two back-to-back shldw instructions, and the 64-bit version performs a shldq followed by a rolq"

define i16 @rol16_1(i16, i16) {
entry:

%2 = shl i16 %0, %1
%3 = sub i16 16, %1
%4 = lshr i16 %0, %3
%5 = or i16 %2, %4
ret i16 %5

}

Initial selection DAG: %bb.0 'rol16_1:entry'
SelectionDAG has 18 nodes:

t0: ch = EntryToken
  t2: i32,ch = CopyFromReg t0, Register:i32 %0
t3: i16 = truncate t2
t5: i32,ch = CopyFromReg t0, Register:i32 %1
      t7: i8 = truncate t5
    t8: i16 = shl t3, t7
          t6: i16 = truncate t5
        t10: i16 = sub Constant:i16<16>, t6
      t11: i8 = truncate t10
    t12: i16 = srl t3, t11
  t13: i16 = or t8, t12
t16: ch,glue = CopyToReg t0, Register:i16 $ax, t13
t17: ch = X86ISD::RET_FLAG t16, TargetConstant:i32<0>, Register:i16 $ax, t16:1

t7 and t11 gets unwrapped before matchRotateSub. t7->t5(Pos; llvm::ISD::NodeType::CopyFromReg); t11->t10.
When matching for rol, current approach verifies if t10 is an ADD or SUB, and if it is a SUB, then its operand(t6) must match Pos(t5), or Pos must be an ADD t6, xxx (not relevant here).

This patch adds an additional unwrap for t6 if t6 != t5 and t10 is a SUB. (which is the case here, llvm::ISD::TRUNCATE != llvm::ISD::NodeType::CopyFromReg)

Diff Detail

Repository
rL LLVM

Event Timeline

jianye.chen created this revision.Aug 18 2018, 6:05 PM
lebedev.ri retitled this revision from [CodeGen] unwrap truncated subtraction operand for rol generation in matchRotateSub to [DAGCombiner] unwrap truncated subtraction operand for rol generation in matchRotateSub.Aug 18 2018, 11:03 PM

@jianye.chen Are you still working on this?

spatel added a comment.Thu, Jan 3, 7:40 AM

The motivating cases seen in the regression tests here and PR15880 and PR32023 ( https://bugs.llvm.org/show_bug.cgi?id=32023 ) were fixed more generally with rL348706, so I think this can be abandoned.