This is an archive of the discontinued LLVM Phabricator instance.

Introduce DebugCounter into ConstProp pass
ClosedPublic

Authored by zhizhouy on Jul 31 2018, 11:29 AM.

Details

Summary

This patch introduces DebugCounter into ConstProp pass at per-transformation level.

It will provide an option to skip first n or stop after n transformations for the whole ConstProp pass.

This will make debug easier for the pass, also providing chance to do transformation level bisecting.

Diff Detail

Repository
rL LLVM

Event Timeline

zhizhouy created this revision.Jul 31 2018, 11:29 AM
lib/Transforms/Scalar/ConstantProp.cpp
82 ↗(On Diff #158349)

Looks like we make no attempt to traverse this function in a stable order (we're relying on the iteration order of a std::set<Instruction *>, and pointers don't have a guaranteed relative order from execution to execution), so I don't think this'll do what we want?

zhizhouy updated this revision to Diff 158440.Jul 31 2018, 6:28 PM
zhizhouy added a subscriber: llozano.

Use a vector to ensure worklist iterated in stable order.

lib/Transforms/Scalar/ConstantProp.cpp
73 ↗(On Diff #158440)

Can we also change this to a SmallPtrSet, please?

74 ↗(On Diff #158440)

Please also add "We use two containers rather than a SetVector, since remove is linear-time, and we don't care enough to remove from Vec"

77 ↗(On Diff #158440)

This should always be true.

87 ↗(On Diff #158440)

nit: Probably redundant comment, given the comment above

88 ↗(On Diff #158440)

We can't do a range for loop here: they expand to (roughly; I'm too lazy to bring up the standard, and the differences don't matter here :) )

for (auto Begin = WorkListVec.begin(), End = WorkListVec.end(); Begin != End; ++Begin) {
  Instruction *I = *Begin;
  {
    // Loop body
  }
}

This is problematic, since WorkListVec.push_back() invalidates iterators, but we're still using the now-invalid iterators.

Please either make this use indices, or a while (!vec.empty()) { auto *i = vec.pop_back_val(); }-like thing

100 ↗(On Diff #158440)

nit: I think it's preferred to use !set.count(x) instead of set.find(x) == set.end()

We could probably simplify this whole thing to set.insert(cast<Instruction>(U)).second, though (if insertion failed, it already existed)

zhizhouy updated this revision to Diff 158599.Aug 1 2018, 12:16 PM
zhizhouy marked 6 inline comments as done.

Comments fixed.

lib/Transforms/Scalar/ConstantProp.cpp
88 ↗(On Diff #158440)

I think there was a misunderstanding here. Please use an index instead of an iterator. The loop should look like

for (unsigned I = 0; I < WorkListVec.size(); ++I) {
  ...
}
zhizhouy updated this revision to Diff 158623.Aug 1 2018, 1:48 PM

Sorry for misunderstanding, comments fixed.

ping for reviewing... thanks!

davide added a reviewer: fhahn.Sep 5 2018, 2:00 PM
fhahn added a comment.Sep 7 2018, 2:42 AM

IIUC by always adding to the end of WorkListVec, we could end up using substantial more memory, depending on the input program. In practice it shouldn't be too bad, as I think an upper bound for the times an instruction is added to WorkListVec is the number of operands (it will only get added if one of its operands gets constant folded, and once an operand is constant folded, it won't get folded again). And usually most instructions have a small number of operands.

However, I think we might be able to construct programs where WorkListVec uses O(n*n) memory (where n is the number of instructions): say we have n/2 instructions where Inst_x can be constant folded after Inst_(x-1) got constant folded. The other n/2 instructions are PHI nodes with with all other n/2 instructions as incoming values. Now we process them in the most suboptimal order: first all the phi nodes, then Inst_(n/2).... Inst_0. We manage to constant fold Inst_0 and add n/2 phi nodes and Inst_1 to WorkListVec. We again process all phi nodes, constant fold Inst_1 and add all phi nodes and Inst_2. We continue doing until all n/2 non-phi instructions are constant folded and each time we add n/2 nodes to WorkListVec.

Not sure if it is worth it (as this is a legacy pass and not used any more AFAIK), but I think we could use 2 worklists to keep the memory usage linear, with keeping the same iteration order:

while (!WorkList.empty()) {
   SmallVector<Instruction*, 16> NewWorkListVec;
   for (auto *I : WorkListVec) {
     ......
         NewWorkListVec.push_back(U);
     .....
   }
   WorkListVec = std::move(NewWorkListVec);
}
lib/Transforms/Scalar/ConstantProp.cpp
109 ↗(On Diff #158623)

already erase at line 90?

zhizhouy updated this revision to Diff 166210.Sep 19 2018, 6:29 PM

Using another vector to deal with newly added instructions. Thanks!

fhahn accepted this revision.Sep 20 2018, 6:56 AM

LGTM thanks! It would be great if you could also add a simple test case.

This revision is now accepted and ready to land.Sep 20 2018, 6:56 AM
fhahn added a comment.Nov 9 2018, 3:59 AM

Do you need someone to commit this?

Thanks for the heads up. Sorry for the delay, I will commit it soon.

This revision was automatically updated to reflect the committed changes.