[LLVMdev] [LLVMDev] Does LLVM have a random number generator?

[Jeff Kunkel]

I forgot to cc the list.

On Sat, Oct 9, 2010 at 10:47 AM, Jeff Kunkel <jdkunk3 at gmail.com> wrote:
> On Sat, Oct 9, 2010 at 10:37 AM, Michael Spencer <bigcheesegs at gmail.com> wrote:
>>> On Sat, Oct 9, 2010 at 1:10 AM, Jeff Kunkel <jdkunk3 at gmail.com> wrote:
>>>> Hello, does LLVM already have a Random Number Generator built into
>>>> it's library somewhere?
>>>>
>>>> I know code generation is suppose to be deterministic, but when
>>>> producing a random number can be deterministic if the random number
>>>> generator is also deterministic.
>>
>> What exactly is this for? Most heuristics in llvm passes are generated
>> by calculating an arbitrary "goodness" value by iterating over the
>> code in question and looking for indicators.
>
> I am using this is my register allocator. For phi elimination, I've
> created a simulated annealing like algorithm. I expect this to
> generate good results quickly, rather than using the integer linear
> programming approaches or the iterative approaches. Second, the
> problem instances going into this algorithm are fairly small. I have
> cut down the problem instances to a very few variables which are
> required for such hard algorithms.
>
>>
>> I have no opinion on using psudorandom numbers, but you have to be
>> careful to keep the results the same across platforms. Quite a few
>> stdlib algorithms don't say exactly how many times any given function
>> will be called.
>
> Hence, a register allocator class where the user can specify the seed
> would be preferred over the C-style srand(), rand() because at that
> point rand() would not be thread safe.
>
>>
>>> I am plugging this into my code. If someone wants to take it out and
>>> add it to the llvm library, it's a simple Linear Congruential
>>> Generator, but here it is:
>>>
>>>    typedef struct random_number_gen {
>>>      unsigned a, c, seed, m;
>>>      random_number_gen( unsigned seed, unsigned modulo ) :
>>> seed(seed), m(modulo) {
>>>        unsigned primes[] = { 2,   3,   5,   7,  11,  13,  17,  19,  23,  29 };
>>>        a = 1 + primes[ seed % ( sizeof(primes)/sizeof(primes[0]) ) ];
>>>        c = primes[ modulo % ( sizeof(primes)/sizeof(primes[0]) ) ];
>>>      }
>>>      unsigned rand() { return seed = (a*seed + c) % m; }
>>>    } random_number_gen;
>>>
>>> -Thanks
>>> -Jeff Kunkel
>>
>> If we do add a psudorandom number generator to the Support library, I
>> would rather we use the same interface as C++0x <random> and use the
>> Mersenne twister.
>
> I just needed something simple and stupid. I just whipped this up as
> fast as I could.
>
>>
>> - Michael Spencer
>>
>
> Thanks,
> Jeff Kunkel
>