This is an archive of the discontinued LLVM Phabricator instance.

Differential D42701

[DAG] Prevent NodeId pruning of TokenFactors in Instruction Selection.
ClosedPublic

Authored by niravd on Jan 30 2018, 12:09 PM.

Details

Reviewers
RKSimon
hfinkel
Commits
rGc3a1e16db1fe: [DAG] Prevent NodeId pruning of TokenFactors in Instruction Selection.
rL323880: [DAG] Prevent NodeId pruning of TokenFactors in Instruction Selection.
Summary

Instruction Selection preserves relative orders of all nodes save
TokenFactors which we treat specially. As a result Node Ids for
TokenFactors may violate the topological ordering and should not be
considered as valid pruning candidates in predecessor search.

Fixes PR35316.

Diff Detail

Repository
rL LLVM

Event Timeline

niravd created this revision.Jan 30 2018, 12:09 PM
Herald added a subscriber: hiraditya. · View Herald TranscriptJan 30 2018, 12:09 PM
RKSimon accepted this revision.Jan 30 2018, 12:59 PM

LGTM - thanks!

This revision is now accepted and ready to land.Jan 30 2018, 12:59 PM
Closed by commit rL323880: [DAG] Prevent NodeId pruning of TokenFactors in Instruction Selection. (authored by niravd). · Explain WhyJan 31 2018, 7:27 AM
This revision was automatically updated to reflect the committed changes.

Revision Contents

PathSize
llvm/
trunk/
lib/
CodeGen/
SelectionDAG/
4 lines
test/
CodeGen/
X86/
76 lines

Diff 132174

llvm/trunk/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp

Show First 20 Lines • Show All 2,151 Lines • ▼ Show 20 Linesstatic bool findNonImmUse(SDNode *Use, SDNode* Def, SDNode *ImmedUse,
// happen because we scan down to newly selected nodes in the case of glue // happen because we scan down to newly selected nodes in the case of glue
// uses. // uses.
std::vector<SDNode *> WorkList; std::vector<SDNode *> WorkList;
WorkList.push_back(Use); WorkList.push_back(Use);
while (!WorkList.empty()) { while (!WorkList.empty()) {
Use = WorkList.back(); Use = WorkList.back();
WorkList.pop_back(); WorkList.pop_back();
if (Use->getNodeId() < Def->getNodeId() && Use->getNodeId() != -1) // NodeId topological order of TokenFactors is not guaranteed. Do not skip.
if (Use->getOpcode() != ISD::TokenFactor &&
Use->getNodeId() < Def->getNodeId() && Use->getNodeId() != -1)
continue; continue;
// Don't revisit nodes if we already scanned it and didn't fail, we know we // Don't revisit nodes if we already scanned it and didn't fail, we know we
// won't fail if we scan it again. // won't fail if we scan it again.
if (!Visited.insert(Use).second) if (!Visited.insert(Use).second)
continue; continue;
for (const SDValue &Op : Use->op_values()) { for (const SDValue &Op : Use->op_values()) {
▲ Show 20 Lines • Show All 1,654 Lines • Show Last 20 Lines

llvm/trunk/test/CodeGen/X86/pr35316.ll

; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
; RUN: llc < %s -mtriple=x86_64-linux | FileCheck %s --check-prefix=CHECK
; This tests for a cyclic dependencies in the generated DAG.
@c = external local_unnamed_addr global i32, align 4
@a = external local_unnamed_addr global i32, align 4
@b = external local_unnamed_addr global i32, align 4
define void @main() {
; CHECK-LABEL: main:
; CHECK: # %bb.0: # %entry
; CHECK-NEXT: movl -{{[0-9]+}}(%rsp), %eax
; CHECK-NEXT: movl -{{[0-9]+}}(%rsp), %eax
; CHECK-NEXT: movl -{{[0-9]+}}(%rsp), %eax
; CHECK-NEXT: movl -{{[0-9]+}}(%rsp), %eax
; CHECK-NEXT: movl -{{[0-9]+}}(%rsp), %eax
; CHECK-NEXT: movl -{{[0-9]+}}(%rsp), %eax
; CHECK-NEXT: movl -{{[0-9]+}}(%rsp), %eax
; CHECK-NEXT: movl -{{[0-9]+}}(%rsp), %eax
; CHECK-NEXT: movl -{{[0-9]+}}(%rsp), %eax
; CHECK-NEXT: movl -{{[0-9]+}}(%rsp), %eax
; CHECK-NEXT: movl -{{[0-9]+}}(%rsp), %eax
; CHECK-NEXT: movl -{{[0-9]+}}(%rsp), %eax
; CHECK-NEXT: movl -{{[0-9]+}}(%rsp), %eax
; CHECK-NEXT: movl -{{[0-9]+}}(%rsp), %eax
; CHECK-NEXT: movl -{{[0-9]+}}(%rsp), %eax
; CHECK-NEXT: movl $0, {{.*}}(%rip)
; CHECK-NEXT: movl -{{[0-9]+}}(%rsp), %r8d
; CHECK-NEXT: movl -{{[0-9]+}}(%rsp), %edi
; CHECK-NEXT: movl -{{[0-9]+}}(%rsp), %esi
; CHECK-NEXT: movl -{{[0-9]+}}(%rsp), %eax
; CHECK-NEXT: cltd
; CHECK-NEXT: idivl {{.*}}(%rip)
; CHECK-NEXT: movl %eax, %ecx
; CHECK-NEXT: movl {{.*}}(%rip), %eax
; CHECK-NEXT: cltd
; CHECK-NEXT: idivl %esi
; CHECK-NEXT: andl %edi, %eax
; CHECK-NEXT: addl %ecx, %eax
; CHECK-NEXT: andl %r8d, %eax
; CHECK-NEXT: movl %eax, (%rax)
; CHECK-NEXT: retq
entry:
%e = alloca i32, align 4
%e.0.e.0.24 = load volatile i32, i32* %e, align 4
%e.0.e.0.25 = load volatile i32, i32* %e, align 4
%e.0.e.0.26 = load volatile i32, i32* %e, align 4
%e.0.e.0.27 = load volatile i32, i32* %e, align 4
%e.0.e.0.28 = load volatile i32, i32* %e, align 4
%e.0.e.0.29 = load volatile i32, i32* %e, align 4
%e.0.e.0.30 = load volatile i32, i32* %e, align 4
%e.0.e.0.31 = load volatile i32, i32* %e, align 4
%e.0.e.0.32 = load volatile i32, i32* %e, align 4
%e.0.e.0.33 = load volatile i32, i32* %e, align 4
%e.0.e.0.34 = load volatile i32, i32* %e, align 4
%e.0.e.0.35 = load volatile i32, i32* %e, align 4
%e.0.e.0.36 = load volatile i32, i32* %e, align 4
%e.0.e.0.37 = load volatile i32, i32* %e, align 4
%e.0.e.0.39 = load volatile i32, i32* %e, align 4
%tmp = load i32, i32* @a, align 4
store i32 0, i32* @b, align 4
%e.0.e.0.41 = load volatile i32, i32* %e, align 4
%add17 = add nsw i32 %e.0.e.0.41, 0
%e.0.e.0.42 = load volatile i32, i32* %e, align 4
%tmp1 = load i32, i32* @c, align 4
%e.0.e.0.43 = load volatile i32, i32* %e, align 4
%div = sdiv i32 %tmp1, %e.0.e.0.43
%and18 = and i32 %div, %e.0.e.0.42
%e.0.e.0.44 = load volatile i32, i32* %e, align 4
%div19 = sdiv i32 %e.0.e.0.44, %tmp
%add20 = add nsw i32 %div19, %and18
%and21 = and i32 %add20, %add17
store volatile i32 %and21, i32* undef, align 4
ret void
}