Page MenuHomePhabricator

MachineScheduler/ScheduleDAG: Add support for GetSubGraph

Authored by axeldavy on Mar 5 2017, 2:04 PM.



GetSubGraph is a new ScheduleDAG function to get the
subgraph of nodes between two SUs.

Diff Detail


Event Timeline

axeldavy created this revision.Mar 5 2017, 2:04 PM

This patch is required for

I don't know who should be reviewer for this code. Anyone ?

axeldavy updated this revision to Diff 91058.Mar 8 2017, 11:20 AM

Rebased on master.

Can you please post this patch with full context? See for instructions.

atrick accepted this revision.Mar 14 2017, 1:59 PM

This seems reasonable to me. Hopefully the linker will strip utilities like this for build targets that don't need them.

This revision is now accepted and ready to land.Mar 14 2017, 1:59 PM
axeldavy updated this revision to Diff 91769.Mar 14 2017, 2:05 PM

Added full context

MatzeB added inline comments.Mar 14 2017, 2:15 PM
718 ↗(On Diff #91058)

Do not repeat the function name in the doxygen comment.

723–724 ↗(On Diff #91058)

Use references instead of pointers for things that cannot be nullptr.

579 ↗(On Diff #91058)

Better use SUnit::isBoundaryNode()

587 ↗(On Diff #91058)

Isn't there a mismatch here? I would assume you either test+set visited at the beginning of the loop or you do both when inserting into the worklist.

Testing before insertion but only setting the visited flag when pulling out of the worklist can lead to situations in which elements are pulled out multiple times.

611 ↗(On Diff #91058)

Better use SUnit::isBoundaryNode()

hfinkel accepted this revision.Mar 14 2017, 2:17 PM

Added full context

Small comment about the assert, but otherwise LGTM too.

624 ↗(On Diff #91769)

This assert should have a comment, but instead of tracking Found again, maybe it would be even better to do this:

assert(VisitedBack.size() == Visited.size() && "Did not collect all subgraph nodes?");
axeldavy added inline comments.Mar 14 2017, 2:47 PM
579 ↗(On Diff #91058)

Thanks, I update the diff with that.

587 ↗(On Diff #91058)

Right, it sounds better to set Visited directly there.

It may be possible without it items get added several times to the WorkList, though the second time the items would be pulled, the operation would be noop.

624 ↗(On Diff #91769)

Thanks, I add a comment in the assert.

However please note that VisitedBack and Visited likely don't have the same size.
Visited can contain more elements.

axeldavy updated this revision to Diff 91776.Mar 14 2017, 2:56 PM

Updated according to the review comments.

MatzeB accepted this revision.Mar 14 2017, 2:58 PM


axeldavy updated this revision to Diff 91778.Mar 14 2017, 3:05 PM

The Visited set was incorrectly set in the previous diff.

vpykhtin added inline comments.
723 ↗(On Diff #91778)

Isn't it enough to return empty vector on failure, without error flag?

axeldavy added inline comments.Mar 17 2017, 9:49 AM
723 ↗(On Diff #91778)

Empty vector currently means that TargetSU is a direct successor for StartSU.

If we don't have error flag and say that a failure return empty vector,
we have to check if TargetSU is in StartSU's Succs.

I think it's better having directly an error flag.

This revision was automatically updated to reflect the committed changes.