This is an archive of the discontinued LLVM Phabricator instance.

Random Number Generator Refactoring (removing from Module)
ClosedPublic

Authored by rinon on Jul 3 2014, 11:12 AM.

Details

Summary

This patch removes the RNG from Module. Passes should instead create a new RNG for their use as needed.

Diff Detail

Event Timeline

rinon updated this revision to Diff 11063.Jul 3 2014, 11:12 AM
rinon retitled this revision from to Random Number Generator Refactoring (removing from Module).
rinon updated this object.
rinon edited the test plan for this revision. (Show Details)
rinon added reviewers: jfb, ahomescu.
rinon set the repository for this revision to rL LLVM.
rinon added a project: deleted.
rinon added subscribers: Unknown Object (MLST), nlewycky, chandlerc and 2 others.
rinon added a comment.Jul 3 2014, 11:14 AM

Highlighting an issue for discussion:

The RNG is guaranteed to produce the same random stream only when the Module ID and thus the input filename is the same. This might be problematic if the input filename extension changes (e.g. from .c to .bc or .ll).

We could store this salt in NamedMetadata, but this would make the parameter non-const. This would unfortunately make this interface unusable by any Machine passes, since they only have a const reference to their IR Module. Alternatively we can always store salt metadata in the Module constructor, but this means overhead even when the RNG is never used.

jfb added inline comments.Jul 3 2014, 5:41 PM
include/llvm/Support/RandomNumberGenerator.h
35

Why the change to uint_fast64_t? Seems odd with the rest of the codebase not using it, but I guess there's no harm either.

38

I think you mean "instantiate its own RNG".

39

The pass uses a unique salt, not seed.

I'd also clarify that the random stream is per-pass, which means that different source versions of LLVM are likely to perform the same per-pass random choices.

41

As Alp pointed out this should probably not know about Module. You'll probably want some factory that knows about Module, Pass and RNG, and instantiate RNGs with salt, and make this class non-constructible otherwise.

What do you have in mind for the Pass salt? They usually have a Pass name that could be expected to stay the same, as well as a Pass argument (in PassInfo).

46

I'd drop the "should", since it's spec'd to generate the same random sequence when the seed is the same.

s/deterministicly/deterministically/

lib/Support/RandomNumberGenerator.cpp
40

I'm not sure that's actually a problem.

52

Mersenne

rinon added a comment.Jul 8 2014, 12:29 PM

Thanks for all the feedback on the comments. Was a bit rushed when I wrote those I guess, but I'll definitely fix those up now.

include/llvm/Support/RandomNumberGenerator.h
35

This was simply because that's what the MT RNG returns. It could probably be safely cast to something more common.

lib/Support/RandomNumberGenerator.cpp
40

Me either. I was hoping to get some feedback from anyone who thought it might be. @nlewycky, do you have an opinion?

rinon updated this revision to Diff 11172.Jul 8 2014, 2:38 PM
  • Moved RNG creation back to Module.
  • Updated comments
jfb added inline comments.Jul 9 2014, 9:22 AM
include/llvm/IR/Module.h
266

I think it would be more usable for LLVM developers, and lead to correct usage, if this took a Pass & instead of a StringRef.

include/llvm/Support/RandomNumberGenerator.h
37

I'm not sure how general we want this Support RNG to be, versus how paternalistic we want to be in preventing LLVM developers from misusing the RNG. Having a comment here may be the right balance (so people can reuse the RNG for something else if they want), but I'd at consider making the ctor private and adding friend class Module if we want to ensure that the RNG is only initialized the "right" way.

lib/IR/Module.cpp
72

I'd still like a clarification on this last sentence. I'm not sure it's a problem.

lib/Support/RandomNumberGenerator.cpp
41

Missing a period at the end.

48

Can you do away with I here, pass it straight to std::copy? Or use auto?

rinon added inline comments.Aug 19 2014, 2:46 PM
lib/Support/RandomNumberGenerator.cpp
48

Good catch. Was left over from having 2 salts.

rinon updated this revision to Diff 12684.Aug 19 2014, 2:46 PM
  • Make seeding private and Module friend.
rinon added a comment.Aug 19 2014, 2:52 PM

Here's a new revision which should resolve all outstanding comments. What does everyone think? I think we should go ahead and commit this, since it resolves the biggest issue and gets rid of the inverted dependency of Module on Support/RandomNumberGenerator.h. If further improvements to use randomness buffers or similar ideas are desired, this can be easily added to the new version by changing how instance generation works.

jfb edited edge metadata.Aug 20 2014, 1:40 PM

This looks good to me if nobody else has objections. I would like you to consider my comment below, let me know what you think.

include/llvm/IR/Module.h
266

I'm still wondering if it would be better for this API to take in a const Pass * and use P->getName() as the Pass salt. This makes it easier to use the RNG correctly, since Pass authors don't need to think about the Pass salt, the same way they don't need to think about the Module salt. LLVM's RegisterPass takes in a PassName argument, so all passes should already have a name (avoiding duplicate salt issues).

rinon added inline comments.Aug 20 2014, 4:28 PM
include/llvm/IR/Module.h
266

You make a great point. I wasn't aware that all passes actually set a PassName (I must confess I've written too many that hook in strangely and don't override getName...). I'll change this right now.

rinon updated this revision to Diff 12718.Aug 20 2014, 4:45 PM
rinon edited edge metadata.
  • Make RNG creation require only a Pass object instead of a string.
jfb accepted this revision.Aug 20 2014, 5:12 PM
jfb edited edge metadata.

Thanks, that looks good to me. I'd leave this open for a while longer to leave others some time to chime in.

This revision is now accepted and ready to land.Aug 20 2014, 5:12 PM
rinon added a comment.Dec 16 2014, 1:41 PM

Just wanted to ping this change and see if we can't get this committed if it's good to go?

jfb added a comment.Dec 16 2014, 1:47 PM
In D4377#102126, @rinon wrote:

Just wanted to ping this change and see if we can't get this committed if it's good to go?

Still looks good to me.

jfb added a comment.Dec 16 2014, 1:48 PM
In D4377#102130, @jfb wrote:
In D4377#102126, @rinon wrote:

Just wanted to ping this change and see if we can't get this committed if it's good to go?

Still looks good to me.

Actually, do you have commit access?

Also, you'll need to rebase the changes before committing. Can you please upload a rebased patch.

rinon updated this revision to Diff 17372.Dec 16 2014, 3:23 PM
rinon edited edge metadata.
  • Tiny whitespace fix
  • Merge remote-tracking branch 'llvm/master' into rng
rinon added a comment.Dec 16 2014, 3:25 PM

No, I don't have commit access (yet).

Here's the rebased (well, I merged, but in my understanding of phabricator it should work) patch.

This revision was automatically updated to reflect the committed changes.