This patch fixes the update of the DAGNode UnscheduledSucc counter when
a use edge is modified. This is the result of a setOperand() or a RAUW
(and friends) operation.
Before this patch we would not check if the User (i.e., the consumer of
the use-def edge) is scheduled and we would update the definition's
UnscheduledSucc counter, resulting in counting errors.
For example, consider the following IR:
```
%A = ...
%B = ...
%U = %A ; scheduled
```
Note that %U's DAGNode is marked as "scheduled" while %A and %B are not.
If we change %U's operand from %A to %B then we should not attempt to
update %A's or %B's UnscheduledSuccs because %U is scheduled so it
should not get counted as an "unscheduled" successor.
DGNode::setScheduled() is only used to mark a nodes a scheduled, not the
reverse. The reverse should only happen with a call to
DGNode::resetScheduleState().
When a DAG node gets scheduled, it's UnscheduledSuccs variable becomes
invalid. Up until now we had no way in the code of expressing this.
This patch converts UnscheduledSuccs to an std::optional in order to
protect its use when not valid.
When we update use-def edges the DAG gets notified to update the
UnscheduledSuccs counters. However, if either edge node is already
scheduled we should not update UnscheduledSuccs because the
UnscheduledSuccs counter value should be treated as "undefined" after a
node has been scheduled, i.e., it's value has a meaning only before the
node gets scheduled.
Whenever an IR use-def edge gets updated, the DAG gets notified about
the change by having its `notifySetUse()` callback called. The
callback's job is to update the DAG node's `UnscheduledSuccs` counter
which is the number of successor nodes that are yet to be scheduled.
This update makes sense only if both ends of the use-def edge are in the
DAG. Up until now we would still update the counter even if the user was
outside the DAG. This patch fixes this, so from now on we skip updatinge
`UnscheduledSuccs` if the user is outside the DAG.
This patch fixes a bug in `DependencyGraph::extend()` when the old
interval contains no memory instructions. When this is the case we
should do a full dependency scan of the new interval.
This patch fixes a bug in the dependency node iterators that would
incorrectly not skip nodes that are not in the current DAG. This
resulted in iterators returning nullptr when dereferenced.
The fix is to update the existing "skip" function to not only skip
non-instruction values but also to skip instructions not in the DAG.
This patch fixes a bug in the maintenance of the MemDGNode chain of the
DAG. Whenever we move a memory instruction, the DAG gets notified about
the move and maintains the chain of memory nodes. The bug was that if
the destination of the move was not a memory instruction, then the
memory node's next node would end up pointing to itself.
The DAG maintains a chain of MemDGNodes that links together all the
nodes that may touch memroy.
Whenever a new instruction gets created we need to make sure that this
chain gets updated. If the new instruction touches memory then its
corresponding MemDGNode should be inserted into the chain.
This patch adds the callback registration logic in the DAG's constructor
and the corresponding deregistration logic in the destructor. It also
implements the code that makes sure that SchedBundle and DGNodes can be
safely destroyed in any order.
This is a refactoring patch that moves the callback registration for
getting notified about new instructions from the scheduler to the DAG.
This makes sense from a design and testing point of view:
- the DAG should not rely on the scheduler for getting notified
- the notifiers don't need to be public
- it's easier to test the notifiers directly from within the DAG unit
tests
This patch implements a ready-list-based scheduler that operates on
DependencyGraph.
It is used by the sandbox vectorizer to test the legality of vectorizing
a group of instrs.
SchedBundle is a helper container, containing all DGNodes that
correspond to the instructions that we are attempting to schedule with
trySchedule(Instrs).
This patch implements the UnscheduledSuccs counter in DGNode. It counts
the number of unscheduled successors and is used by the scheduler to
determine when a node is ready.
This patch moves:
- Utils::isStackSaveOrRestoreIntrinsic()
- Utils::isMemIntrinsic()
- Utils::isMemDepCandidate()
to DGNode because they no longer require LLVM IR access and are used
only by the DAG.
This patch implements the MemDGNode class for DAG nodes that are
candidates
for memory dependencies. These nodes form a chain that is accessible by
`getPrevNode()` and `getNextNode()`.
It also implements a builder class that creates MemDGNode intervals from
Instructions.
