[llvm-bugs] [Bug 25431] New: SDNode::hasPredecessorHelper() has algorithm bug

[via llvm-bugs]

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

            Bug ID: 25431
           Summary: SDNode::hasPredecessorHelper() has algorithm bug
           Product: new-bugs
           Version: 3.7
          Hardware: PC
                OS: Windows NT
            Status: NEW
          Severity: normal
          Priority: P
         Component: new bugs
          Assignee: unassignedbugs at nondot.org
          Reporter: eric.schweitz at pgroup.com
                CC: llvm-bugs at lists.llvm.org
    Classification: Unclassified

There is an algorithm problem in this function when it is used to cache search
results and answer multiple queries.

Specifically, if we ask the algorithm if the SDNodes U_1 ... U_n are transitive
preds of the instruction S, we can get the wrong answer. 

This happens in the following scenario. Suppose there is an SDNode U_j that is
a pred of S. Say U_j is the k-th argument to its succ U_i, which has m > k
total arguments; we have U_j --> U_i ~~> S. When visiting U_i, we will find
U_j, stop, and return true. At this point we have effectively pruned the search
space of all the arguments k+1 .. m to U_i. The for loop is exited before these
children are placed on the worklist. On the next query, for U_k, if U_k lies
along one of the lost subgraph paths, the algorithm will return false even
though there does exist a path U_k ~~> U_i ~~> S.

This bug is masked when using the hasPredecessor() query because the entire
search space is reconstructed rather than cached.

-- 
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/20151106/9dad9b19/attachment-0001.html>