llvm-svn: 122726

llvm-svn: 122725

llvm-svn: 122724

allocator.  This speeds up early cse by about 20%

llvm-svn: 122723

llvm-svn: 122722

llvm-svn: 122721

llvm-svn: 122720

of instcombine that is currently in the middle of the loop pass pipeline. This
commit only checks in the pass; it will hopefully be enabled by default later.

llvm-svn: 122719

llvm-svn: 122718

Teach it to CSE the rest of the non-side-effecting instructions.

llvm-svn: 122716

Add a testcase.

llvm-svn: 122715

so that Dominators.h is *just* domtree.  Also prune #includes a bit.

llvm-svn: 122714

llvm-svn: 122713

sure that the loop we're promoting into a memcpy doesn't mutate the input
of the memcpy.  Before we were just checking that the dest of the memcpy
wasn't mod/ref'd by the loop.

llvm-svn: 122712

mess with it.  We'd rather peel/unroll it than convert all of its 
stores into memsets.

llvm-svn: 122711

This allows us to compile:
  void test(char *s, int a) {
    __builtin_memset(s, a, 15);
  }
into 1 mul + 3 stores instead of 3 muls + 3 stores.

llvm-svn: 122710

llvm-svn: 122709

llvm-svn: 122708

Lower the i8 extension in memset to a multiply instead of a potentially long series of shifts and ors.

We could implement a DAGCombine to turn x * 0x0101 back into logic operations
on targets that doesn't support the multiply or it is slow (p4) if someone cares
enough.

Example code:
  void test(char *s, int a) {
      __builtin_memset(s, a, 4);
  }
before:
  _test:                                  ## @test
    movzbl  8(%esp), %eax
    movl  %eax, %ecx
    shll  $8, %ecx
    orl %eax, %ecx
    movl  %ecx, %eax
    shll  $16, %eax
    orl %ecx, %eax
    movl  4(%esp), %ecx
    movl  %eax, 4(%ecx)
    movl  %eax, (%ecx)
    ret
after:
  _test:                                  ## @test
    movzbl  8(%esp), %eax
    imull $16843009, %eax, %eax   ## imm = 0x1010101
    movl  4(%esp), %ecx
    movl  %eax, 4(%ecx)
    movl  %eax, (%ecx)
    ret

llvm-svn: 122707

llvm-svn: 122706

another function.

llvm-svn: 122705

blocks in a loop, instead of just the header block.  This makes it more
aggressive, able to handle Duncan's Ada examples.

llvm-svn: 122704

llvm-svn: 122703

isExitBlockDominatedByBlockInLoop is a relic of the days when domtree was 
*just* a tree and didn't have DFS numbers.  Checking DFS numbers is faster
and easier than "limiting the search of the tree".

llvm-svn: 122702

llvm-svn: 122701

llvm-svn: 122700

in the PR, the pass could break LCSSA form when inserting preheaders.  It probably
would be easy enough to fix this, but since currently we always go into LCSSA form
after running this pass, doing so is not urgent.

llvm-svn: 122695

llvm-svn: 122693

llvm-svn: 122692

llvm-svn: 122691

llvm-svn: 122690

llvm-svn: 122689

llvm-svn: 122688

llvm-svn: 122687

llvm-svn: 122686

header for now for memset/memcpy opportunities.  It turns out that loop-rotate
is successfully rotating loops, but *DOESN'T MERGE THE BLOCKS*, turning "for 
loops" into 2 basic block loops that loop-idiom was ignoring.

With this fix, we form many *many* more memcpy and memsets than before, including
on the "history" loops in the viterbi benchmark, which look like this:

        for (j=0; j<MAX_history; ++j) {
          history_new[i][j+1] = history[2*i][j];
        }

Transforming these loops into memcpy's speeds up the viterbi benchmark from
11.98s to 3.55s on my machine.  Woo.

llvm-svn: 122685

compile, and everyone's tests have shown it to be slower in practice, even for
quite large graphs.

I also hope to do an optimization that is only correct with the simpler data
structure, which would break this even further.

llvm-svn: 122684

llvm-svn: 122683

llvm-svn: 122682

size of a loop header instead of its own code size estimator.
This allows it to handle bitcasts etc more precisely.

llvm-svn: 122681