This is an archive of the discontinued LLVM Phabricator instance.

Differential D31668

Fix PR30562
ClosedPublic

Authored by dtemirbulatov on Apr 4 2017, 6:08 AM.

Details

Reviewers
RKSimon
avt77
bogner
hfinkel
efriedma
Summary

Following code(IR test) produce an incorrect DAG with cycles by this command: llc s.ll

source_filename = "any.c"
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

define i32 @foo(i64* nocapture %perm, i32 %n) {
entry:

br label %body

body:

%vec.ind = phi <2 x i64> [ <i64 0, i64 1>, %entry ], [ <i64 2, i64 3>, %body ]
%l13 = extractelement <2 x i64> %vec.ind, i32 %n
%l14 = getelementptr inbounds i64, i64* %perm, i64 %l13
%l15 = bitcast i64* %l14 to <2 x i64>*
store <2 x i64> %vec.ind, <2 x i64>* %l15, align 8
%niter.ncmp.3 = icmp eq i64 %l13, 0
br i1 %niter.ncmp.3, label %exit, label %body

exit:

ret i32 %n

}

Here is DAG dump just before it was diagnosis with a cycle in checkForCyclesHelper:
(gdb) p DAG->dump()
SelectionDAG has 31 nodes:

t0: ch = EntryToken
  t8: i64,ch = CopyFromReg t0, Register:i64 %vreg1
  t10: i64 = shl t44, Constant:i8<3>
t11: i64 = add t8, t10
    t2: v2i64,ch = CopyFromReg t0, Register:v2i64 %vreg0
  t14: ch = store<ST16[%l15](align=8)> t0, t2, t11, undef:i64
          t4: i32,ch = CopyFromReg t0, Register:i32 %vreg2
        t49: i64 = any_extend t4
      t40: i64 = and t49, Constant:i64<1>
    t50: i64 = shl t40, Constant:i8<3>
  t43: i64 = add t50, t11
t44: i64,ch = load<LD8[<unknown>]> t14, t43, undef:i64
          t48: i64 = X86ISD::Wrapper TargetConstantPool:i64<<2 x i64> <i64 2, i64 3>> 0
        t46: v2i64,ch = load<LD16[ConstantPool]> t0, t48, undef:i64
      t20: ch = CopyToReg t0, Register:v2i64 %vreg7, t46
    t24: ch = TokenFactor t20, t44:1
    t34: i32 = X86ISD::CMP t44, Constant:i64<0>
  t37: ch = X86ISD::BRCOND t24, BasicBlock:ch<body 0x5fc2078>, Constant:i8<9>, t34
t27: ch = br t37, BasicBlock:ch<exit 0x5fc2188>

$2 = void

Note here t10 is dependent from t44 .

This patch is a simple fix for the problem, and adds an additional dependency test when searching for a store. And it avoids to reuse already existing STORE and creates new STORE on the stack in order to construct DAG without cycles.

Diff Detail

Event Timeline

dtemirbulatov created this revision.Apr 4 2017, 6:08 AM
RKSimon edited edge metadata.Apr 4 2017, 6:33 AM

I think you mean PR30562?

Please can you regenerate your diffs with full context (http://llvm.org/docs/Phabricator.html#requesting-a-review-via-the-web-interface)

lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
1200

Comments?

test/CodeGen/X86/30462.ll
1 ↗(On Diff #94060)

The file should be called pr30562.ll.

Please regenerate this with llvm\utils\update_llc_test_checks.py

dtemirbulatov retitled this revision from Fix PR30462 to Fix PR30562.Apr 4 2017, 8:20 AM
dtemirbulatov updated this revision to Diff 94081.Apr 4 2017, 8:48 AM

sorry for typos in an initial attempt.

dtemirbulatov updated this revision to Diff 94085.Apr 4 2017, 9:34 AM
avt77 edited edge metadata.Apr 4 2017, 11:46 PM

You should use the following command to generate diff:

svn diff --diff-cmd=diff -x -U999999 > patch.diff

dtemirbulatov updated this revision to Diff 94173.Apr 5 2017, 1:38 AM

updating diff

dtemirbulatov added a comment.Apr 5 2017, 4:22 AM

I found some issues in my change: actually I don't need to check StackPtr, rather ST. I am working on a new version.

RKSimon added a reviewer: bogner.Apr 5 2017, 6:07 AM
dtemirbulatov updated this revision to Diff 94223.Apr 5 2017, 7:34 AM
RKSimon added a reviewer: efriedma.Apr 6 2017, 4:32 AM
RKSimon added subscribers: efriedma, llvm-commits.

Please don't forget to include llvm-commits as a subscriber in all future patches at creation.

No more comments from me - @bogner @efriedma any thoughts?

efriedma added inline comments.Apr 6 2017, 12:06 PM
lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
1198

This doesn't look like it's checking for the right thing. The problem isn't that the store depends on Idx; if you change the GEP in your testcase to "getelementptr inbounds i64, i64* %perm, i64 %n", there is no cycle. The actual problem is that the store depends on Op (the extractelement itself).

dtemirbulatov updated this revision to Diff 94482.Apr 6 2017, 10:51 PM

here we are checking that the store depends on the extractelement operation.

efriedma accepted this revision.Apr 7 2017, 3:17 PM

LGTM.

This revision is now accepted and ready to land.Apr 7 2017, 3:17 PM
RKSimon closed this revision.Apr 19 2017, 3:07 AM

rL300314

Revision Contents

PathSize
lib/
CodeGen/
SelectionDAG/
7 lines
test/
CodeGen/
X86/
22 lines

Diff 94482

lib/CodeGen/SelectionDAG/LegalizeDAG.cpp

Show First 20 Lines • Show All 1,186 Lines • ▼ Show 20 Lines if (StoreSDNode *ST = dyn_cast<StoreSDNode>(User)) {
// Make sure that nothing else could have stored into the destination of // Make sure that nothing else could have stored into the destination of
// this store. // this store.
if (!ST->getChain().reachesChainWithoutSideEffects(DAG.getEntryNode())) if (!ST->getChain().reachesChainWithoutSideEffects(DAG.getEntryNode()))
continue; continue;
// If the index is dependent on the store we will introduce a cycle when // If the index is dependent on the store we will introduce a cycle when
// creating the load (the load uses the index, and by replacing the chain // creating the load (the load uses the index, and by replacing the chain
// we will make the index dependent on the load). // we will make the index dependent on the load). Also, the store might be
if (SDNode::hasPredecessorHelper(ST, Visited, Worklist)) // dependent on the extractelement and introduce a cycle when creating
// the load.
if (SDNode::hasPredecessorHelper(ST, Visited, Worklist) ||
efriedmaUnsubmitted
Not Done
ReplyInline Actions

This doesn't look like it's checking for the right thing. The problem isn't that the store depends on Idx; if you change the GEP in your testcase to "getelementptr inbounds i64, i64* %perm, i64 %n", there is no cycle. The actual problem is that the store depends on Op (the extractelement itself).

efriedma: This doesn't look like it's checking for the right thing. The problem isn't that the store…
ST->hasPredecessor(Op.getNode()))
continue; continue;
RKSimonUnsubmitted
Not Done
ReplyInline Actions

Comments?

RKSimon: Comments?
StackPtr = ST->getBasePtr(); StackPtr = ST->getBasePtr();
Ch = SDValue(ST, 0); Ch = SDValue(ST, 0);
break; break;
} }
} }
EVT VecVT = Vec.getValueType(); EVT VecVT = Vec.getValueType();
▲ Show 20 Lines • Show All 3,378 Lines • Show Last 20 Lines

test/CodeGen/X86/pr30562.ll

  • This file was added.
; RUN: llc < %s -mtriple=x86_64-unknown-unknown | FileCheck %s
define i32 @foo(i64* nocapture %perm, i32 %n) {
entry:
br label %body
body:
; CHECK-LABEL: foo:
; CHECK: pslldq $8, %xmm0
%vec.ind = phi <2 x i64> [ <i64 0, i64 1>, %entry ], [ <i64 2, i64 3>, %body ]
%l13 = extractelement <2 x i64> %vec.ind, i32 %n
%l14 = getelementptr inbounds i64, i64* %perm, i64 %l13
%l15 = bitcast i64* %l14 to <2 x i64>*
store <2 x i64> %vec.ind, <2 x i64>* %l15, align 8
%niter.ncmp.3 = icmp eq i64 %l13, 0
br i1 %niter.ncmp.3, label %exit, label %body
exit:
ret i32 %n
}