//===----------------------------------------------------------------------===//
8/16/2004 - Evaluating static constructors at compile-time 

Static constructors are annoying, but should be trivially easy to evaluate at
compile time in LLVM.

Two steps to doing so:
1. Change static ctors to make it trivial.
2. Implement the optimization.

Doing this optimization can substantially reduce the startup time of the
program, but it can also have other effects, by allowing other optimizations to
later mark more globals const (once stores to the globals are statically
evaluated).  It can also have the nice effect of nuking many of the silly "if
not initialized yet, initialize now" codes.


//===----------------------------------------------------------------------===//
// Reorganization of __main and the static ctor list.

First, we need to add new static ctor/dtor lists for ctor/dtors without
specified initializer priorities (by far the only case that matters!).  Given
this, we should have two lists like this:

%llvm.global_ctors = appending global [123 x { int, void ()* }] [ 
  { int, void ()* } { int 4123, void ()* %globalinitfn },
...
  { int, void ()* } { int 123, void ()* null } ]

and

%llvm.global_ctors_unordered = appending global [456 x void ()*] [ 
  void ()* %globalinitfn2,
...
  void ()* null ]


Given this, __main should looks something like this:

void __main(void) {
  /* Recursively calling main is not legal C, but lots of people do it for
   * testing stuff.  We might as well work for them.
   */
  static _Bool Initialized = 0;
  if (Initialized) return;
  Initialized = 1;

  /* Only register the global dtor handler if there is at least one global
   * dtor!
   */
  if (__llvm_getGlobalDtors()[0].FP)
    if (atexit(run_destructors))
      abort();  /* Should be able to install ONE atexit handler! */

  /* Loop over all of the constructor records, calling each function pointer. */
  TorRec *R = llvm.global_ctors;
  if (R->FP) {
    // Init order specified, not the common case, sort them by init order now.
    // FIXME: this should be a stable sort??  What about inits in the same file?
    qsort(...);

    // Run the initializers for priority less than the unordered ones.
    for (; R->FP && R->Priority < 65536; ++R) {
      R->FP();
  }

  // If there are unordered initializers, run them now.
  void (**FPP)() = llvm.global_ctors_unordered;
  if (*FPP) {
    for (; *FPP; ++FPP)
      (*FPP)();
  }

  if (R->FP) {
    // Run the rest of the ordered initializers.
    for (; R->FP; ++R)
      R->FP();
  }
}

Given this organization, in the case where the ordered ctor list is empty (by
far the common case), all of the code relating to it can be deleted trivially
by existing optimizers.  Given that this happens, the optimizer will get code
that looks like this as input (probably inlined into main):

void __main(void) {
  static _Bool Initialized = 0;
  if (Initialized) return;
  Initialized = 1;

#if there were global dtors, this would remain
  if (atexit(run_destructors))
    abort();  /* Should be able to install ONE atexit handler! */
#endif

  // If there are unordered initializers, run them now.
  void (**FPP)() = llvm.global_ctors_unordered;
  if (*FPP) {
    for (; *FPP; ++FPP)
      (*FPP)();
  }
}


//===----------------------------------------------------------------------===//
// Implementation of the optimization

Given the above reorganization and the optimization leading to the listed main,
we just have to do some pattern recognition of the code that is left over.  In
particular, we can statically evaluate the "if (Initialized)" condition to
false, and statically evaluate the store.

We have to have a special hack to preserve the atexit call if it still exists.
Finally, we recognize the loop over the recognized global
"llvm.global_ctors_unordered".  Because it has a name known to the system, we
can assume semantics about the list, in particular that the elements may be
run in any order.

Given that, we can write a trivial predicate "canStaticallyEvaluate" that
scans the init function, looking at it.  If it seems memory allocations,
function calls, loops with unknown bounds, or anything else scary, it can
just return false.  If all is cool, it returns true, and the optimizer driver
nukes the entry from the llvm.global_ctors_unordered list.

One technical detail with this approach is that we have to be careful to preserve
ordering of initializers defined in the same file.  In particular, this means
that we probably have to keep track of an ordinal for elements on the
llvm.global_ctors_unordered list, indicating the global ctor # that they are.
If global ctor N for a file cannot be statically evaluated, then we should not
permit global ctor >#N to be evaluated.