llvm dev - Oct 2010 - [LLVMdev] [LLVMDev] Does LLVM have a random number generator?

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.

- Thanks
- Jeff Kunkel

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

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.
>
> - Thanks
> - Jeff Kunkel
>

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

- Michael Spencer

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
>