[SandboxVec][DAG] Fix interval check without Node

This patch moves the check of whether a node exists before the check of
whether it is contained in the interval.

[SandboxVec][DAG] Fix MemDGNode chain maintenance when move destination is non-mem (#124227)

This patch fixes a bug in the maintenance of the MemDGNode chain of the
DAG. Whenever we move a memory i

[SandboxVec][DAG] Fix MemDGNode chain maintenance when move destination is non-mem (#124227)

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.

show more ...

[SandboxVec][BottomUpVec] Disable crossing BBs (#124039)

Crossing BBs is not currently supported by the structures of the
vectorizer. This patch fixes instances where this was happening,
including

[SandboxVec][BottomUpVec] Disable crossing BBs (#124039)

Crossing BBs is not currently supported by the structures of the
vectorizer. This patch fixes instances where this was happening,
including:
- a walk of use-def operands that updates the UnscheduledSuccs counter,
- the dead instruction removal is now done per BB,
- the scheduler, which will reject bundles that cross BBs.

show more ...

[SandboxVec][DAG][NFC] Remove early return in notifyMoveInstr()

It used to early return when destination is same as origin. But it's redundant
because in that case the callback won't get called in t

[SandboxVec][DAG][NFC] Remove early return in notifyMoveInstr()

It used to early return when destination is same as origin. But it's redundant
because in that case the callback won't get called in the first place.

show more ...

[SandboxVec][DAG][NFC] Refactor setNextNode() and setPrevNode() (#122363)

This patch updates DAG's `setNextNode()` and `setPrevNode()` to update
both nodes of the link.

[SandboxVec][DAG] Register move instr callback (#120146)

This patch implements the move instruction notifier for the DAG.
Whenever an instruction moves the notifier will maintain the DAG.

[SandboxVec][DAG] Update MemDGNode chain upon instr deletion (#118921)

[SandboxVec][DAG] Update MemDGNode chain upon instr creation (#116896)

The DAG maintains a chain of MemDGNodes that links together all the
nodes that may touch memroy.
Whenever a new instruction g

[SandboxVec][DAG] Update MemDGNode chain upon instr creation (#116896)

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.

show more ...

[SandboxVec][DAG] Register callback for erase instr (#116742)

This patch adds the callback registration logic in the DAG's constructor
and the corresponding deregistration logic in the destructor.

[SandboxVec][DAG] Register callback for erase instr (#116742)

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.

show more ...

[SandboxVec][Scheduler] Boilerplate and initial implementation. (#112449)

This patch implements a ready-list-based scheduler that operates on
DependencyGraph.
It is used by the sandbox vectorizer

[SandboxVec][Scheduler] Boilerplate and initial implementation. (#112449)

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).

show more ...

[SandboxVec][DAG] Implement UnscheduledSuccs (#112255)

This patch implements the UnscheduledSuccs counter in DGNode. It counts
the number of unscheduled successors and is used by the scheduler to

[SandboxVec][DAG] Implement UnscheduledSuccs (#112255)

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.

show more ...

[SandboxVec][DAG] Avoid unnecessary dependency scan and improve description (#112057)

When NewInterval is below DAGInterval we used to revisit instructions
already visited. This patch fixes this by

[SandboxVec][DAG] Avoid unnecessary dependency scan and improve description (#112057)

When NewInterval is below DAGInterval we used to revisit instructions
already visited. This patch fixes this by separating the scan in two:
1. The full scan of the NewInterval, and
2. The cross-interval scan for DAGInterval.

This is further explained in the new description.

show more ...

[SandboxVec][Interval] Implement Interval::comesBefore() (#112026)

This patch implements `Interval::comesBefore(const Interval &Other)`
which returns true if this interval is strictly before Other

[SandboxVec][Interval] Implement Interval::comesBefore() (#112026)

This patch implements `Interval::comesBefore(const Interval &Other)`
which returns true if this interval is strictly before Other in program
order. The function asserts that the intervals are disjoint.

show more ...

[SandboxVec][DAG] Extend DAG (#111908)

This patch implements growing the DAG towards the top or bottom. This
does the necessary dependency checks and adds new mem dependencies.

[SandboxVec][DAG] Refactoring: Outline code that looks for mem nodes (#111750)

[SandboxVec][DAG] Refactoring: Move MemPreds from DGNode to MemDGNode (#111897)

[SandboxVec][DAG] Implement PredIterator (#111604)

This patch implements an iterator for iterating over both use-def and
mem dependencies of MemDGNodes.

[SandboxVec][DAG] Drop RAR and fix dependency scanning loop (#111715)

DependencyGraph.cpp - mix MSVC "not all control paths return a value" warning. NFC.

[SandboxVec][DAG][NFC] Rename enumerators

[SandboxVec][DAG] Build actual dependencies (#111094)

This patch implements actual dependencies checking using BatchAA. This
adds memory dep edges between MemDGNodes.

[SandboxVec][DAG][NFC] Rename isMemDepCandidate() to isMemDepNodeCandidate()

[SandboxVec][DAG] MemDGNode for memory-dependency candidate nodes (#109684)

This patch implements the MemDGNode class for DAG nodes that are
candidates
for memory dependencies. These nodes form a

[SandboxVec][DAG] MemDGNode for memory-dependency candidate nodes (#109684)

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.

show more ...

[SandboxVec][Interval] Convert InstrInterval class to a class template (#110021)

This patch converts InstrInterval class to a class template and renames
InstrInterval to Itnerval.

This change wi

[SandboxVec][Interval] Convert InstrInterval class to a class template (#110021)

This patch converts InstrInterval class to a class template and renames
InstrInterval to Itnerval.

This change will allow us to reuse the Interval for dependency graph
nodes.

show more ...

[SandboxVec][DAG] Implement extend(ArrayRef) (#109493)

This builds the DAG from an ArrayRef of Instructions.