Changes due to code review and new implementation:
* Don't use std::string for the function names, const char* will suffice
* Allow each CallOptimizer to validate the function signature before
  doing anything
* Repeatedly loop over the functions until an iteration produces
  no more optimizations. This allows one optimization to insert a
  call that is optimized by another optimization.
* Implement the ConstantArray portion of the StrCatOptimization
* Provide a template for the MemCpyOptimization
* Make ExitInMainOptimization split the block, not delete everything
  after the return instruction.
(This covers revision 1.3 and 1.4, as the 1.3 comments were botched)

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21548 91177308-0d34-0410-b5e6-96231b3b80d8

implement some more logical compares with constants, so that:

int foo1(int x, int y) {
  int t1 = x >= 0;
  int t2 = y >= 0;
  return t1 & t2;
}
int foo2(int x, int y) {
  int t1 = x == -1;
  int t2 = y == -1;
  return t1 & t2;
}

produces:

_foo1:
        or r2, r4, r3
        srwi r2, r2, 31
        xori r3, r2, 1
        blr
_foo2:
        and r2, r4, r3
        addic r2, r2, 1
        li r2, 0
        addze r3, r2
        blr

instead of:

_foo1:
        srwi r2, r4, 31
        xori r2, r2, 1
        srwi r3, r3, 31
        xori r3, r3, 1
        and r3, r2, r3
        blr
_foo2:
        addic r2, r4, 1
        li r2, 0
        addze r2, r2
        addic r3, r3, 1
        li r3, 0
        addze r3, r3
        and r3, r2, r3
        blr

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21547 91177308-0d34-0410-b5e6-96231b3b80d8

Lots of changes based on review and new functionality:
* Use a \1a

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21546 91177308-0d34-0410-b5e6-96231b3b80d8

Update the test case to handle a few more (degenerate) cases and remove
the restriction that it is an XFAIL because it now passes.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21545 91177308-0d34-0410-b5e6-96231b3b80d8

Codegen x < 0 | y < 0 as (x|y) < 0.  This allows us to compile this to:

_foo:
        or r2, r4, r3
        srwi r3, r2, 31
        blr

instead of:

_foo:
        srwi r2, r4, 31
        srwi r3, r3, 31
        or r3, r2, r3
        blr

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21544 91177308-0d34-0410-b5e6-96231b3b80d8

Make dominates(A,B) work with post dominators.  Patch contributed by
Naveen Neelakantam, thanks!

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21543 91177308-0d34-0410-b5e6-96231b3b80d8

Added question about turning off all optimizations. I think this has been asked once or twice.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21542 91177308-0d34-0410-b5e6-96231b3b80d8

implement getelementptr.ll:test10

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21541 91177308-0d34-0410-b5e6-96231b3b80d8

rename fn

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21540 91177308-0d34-0410-b5e6-96231b3b80d8

new testcase

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21539 91177308-0d34-0410-b5e6-96231b3b80d8

Correctly handle global-argument aliases induced in main

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21537 91177308-0d34-0410-b5e6-96231b3b80d8

Don't mess up SCC traversal when a node has null edges out of it.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21536 91177308-0d34-0410-b5e6-96231b3b80d8

document 'opaque' types

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21535 91177308-0d34-0410-b5e6-96231b3b80d8

Add feedback from Vikram

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21534 91177308-0d34-0410-b5e6-96231b3b80d8

Make sure the target buffer is null terminated so we don't blow up
strcat when its called.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21533 91177308-0d34-0410-b5e6-96231b3b80d8

A test case for testing the StrCatOptimizer, currently XFAILed everywhere.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21532 91177308-0d34-0410-b5e6-96231b3b80d8

Post-Review Cleanup:
* Fix comments at top of file
* Change algorithm for running the call optimizations from n*n to something
  closer to n.
* Use a hash_map to store and lookup the optimizations since there will
  eventually (or potentially) be a large number of them. This gets lookup
  based on the name of the function to O(1). Each CallOptimizer now has a
  std::string member named func_name that tracks the name of the function
  that it applies to. It is this string that is entered into the hash_map
  for fast comparison against the function names encountered in the module.
* Cleanup some style issues pertaining to iterator invalidation
* Don't pass the Function pointer to the OptimizeCall function because if
  the optimization needs it, it can get it from the CallInst passed in.
* Add the skeleton for a new CallOptimizer, StrCatOptimizer which will
  eventually replace strcat's of constant strings with direct copies.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21526 91177308-0d34-0410-b5e6-96231b3b80d8

Use the %name rather than the "name" format so those familiar with the
llvm-dis output don't go blind.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21525 91177308-0d34-0410-b5e6-96231b3b80d8

Shut GCC 4.0 up about classes that have virtual functions but a non-virtual
destructor. Just add the do-nothing virtual destructor.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21524 91177308-0d34-0410-b5e6-96231b3b80d8

Declare a function to create the SimplifyLibCalls pass.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21523 91177308-0d34-0410-b5e6-96231b3b80d8

A new pass to provide specific optimizations for certain well-known library
calls. The pass visits all external functions in the module and determines
if such function calls can be optimized. The optimizations are specific to
the library calls involved. This initial version only optimizes calls to
exit(3) when they occur in main(): it changes them to ret instructions.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21522 91177308-0d34-0410-b5e6-96231b3b80d8

A test case for the the ExitInMain libcall simplification.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21521 91177308-0d34-0410-b5e6-96231b3b80d8

Older compilers won't like the inline virtual destructor in the header file
so we put the destructor in Pass.cpp and make it non-inline.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21520 91177308-0d34-0410-b5e6-96231b3b80d8

fix some bugs

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21515 91177308-0d34-0410-b5e6-96231b3b80d8

Fix a thinko in the documentation of the splitBasicBlock method. The branch
instruction is added to the original block, not the new block.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21513 91177308-0d34-0410-b5e6-96231b3b80d8

Shut GCC 4.0 up about classes with virtual functions but no virtual
destructor.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21510 91177308-0d34-0410-b5e6-96231b3b80d8

Shut GCC 4.0 up when it complains about classes with virtual functions that
don't have virtual destructors.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21507 91177308-0d34-0410-b5e6-96231b3b80d8

Make this readable for newbies and those who can only understand one set of
grammar rules for the English language.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21503 91177308-0d34-0410-b5e6-96231b3b80d8

extract has been renamed to llvm-extract to avoid conflicting with another tool

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21501 91177308-0d34-0410-b5e6-96231b3b80d8

Eliminate cases where we could << by 64, which is undefined in C.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21500 91177308-0d34-0410-b5e6-96231b3b80d8

There are still uses for spaces in Makefiles -- to make text line up together,
regardless of the tab size/stop settings on the developer side

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21499 91177308-0d34-0410-b5e6-96231b3b80d8

extract has been renamed to llvm-extract to avoid conflicting with another tool

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21498 91177308-0d34-0410-b5e6-96231b3b80d8

elisp code to help with LLVM code standards compliance

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21497 91177308-0d34-0410-b5e6-96231b3b80d8

.vimrc file to aid in LLVM coding standards conformance

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21496 91177308-0d34-0410-b5e6-96231b3b80d8

Implement xor.ll:test21:  select (not C), A, B -> select C, B, A

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21495 91177308-0d34-0410-b5e6-96231b3b80d8

Test that xor/select are folded into a select with inverted operands.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21494 91177308-0d34-0410-b5e6-96231b3b80d8

Allow these methods to take a generic Value* to simplify clients.  Use
const_cast instead of c casts.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21493 91177308-0d34-0410-b5e6-96231b3b80d8

allow these to take a generic Value*

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21492 91177308-0d34-0410-b5e6-96231b3b80d8

Use getPrimitiveSizeInBits() instead of getPrimitiveSize()*8

Completely rework the 'setcc (cast x to larger), y' code.  This code has
the advantage of implementing setcc.ll:test19 (being more general than
the previous code) and being correct in all cases.

This allows us to unxfail 2004-11-27-SetCCForCastLargerAndConstant.ll,
and close PR454.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21491 91177308-0d34-0410-b5e6-96231b3b80d8

unxfail this.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21490 91177308-0d34-0410-b5e6-96231b3b80d8

add a new testcase which occurs in 181.mcf

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21489 91177308-0d34-0410-b5e6-96231b3b80d8

* The aesthetic police is on patrol!!...
* ... but it wasn't so busy as to not smell the roses and doxygenify comments

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21487 91177308-0d34-0410-b5e6-96231b3b80d8

Add a helper method

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21486 91177308-0d34-0410-b5e6-96231b3b80d8

Fix a bug in my previous checkin

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21485 91177308-0d34-0410-b5e6-96231b3b80d8

This file is never referenced

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21484 91177308-0d34-0410-b5e6-96231b3b80d8

Add a method, remove last use of Type.def

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21483 91177308-0d34-0410-b5e6-96231b3b80d8

add a method, remove a dead #include

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21482 91177308-0d34-0410-b5e6-96231b3b80d8

Types.def is going away

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21481 91177308-0d34-0410-b5e6-96231b3b80d8

Eliminate tabs and trailing spaces

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21480 91177308-0d34-0410-b5e6-96231b3b80d8

Eliminate tabs and trailing spaces

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21479 91177308-0d34-0410-b5e6-96231b3b80d8

Propagate eq sets through the bu graphs to the cbu and eq graphs, fixing
a crash of the sfv on 188.ammp

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21478 91177308-0d34-0410-b5e6-96231b3b80d8

add a bunch of documentation about the LLVM type resolution machinery

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21475 91177308-0d34-0410-b5e6-96231b3b80d8

Make the CBackend actually get included in llc by using USEDLIBS instead of
USEDLIB as the variable to which "CBackend" is appended. The surrounding
if clause is safe because currently the configure script ensures that the
CBackend target is always added to TARGETS_TO_BUILD. By using a non-hard
coded construct in the makefile, we gain uniformity and the ability to
change the default set of targets by only changing the configure script.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21474 91177308-0d34-0410-b5e6-96231b3b80d8

make an advanced topics section, move symtab to it

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21473 91177308-0d34-0410-b5e6-96231b3b80d8

This is not needed

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21472 91177308-0d34-0410-b5e6-96231b3b80d8

add a search box for the documentation

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21471 91177308-0d34-0410-b5e6-96231b3b80d8

Generalize the setcc -> PHI and Select  folding optimizations to work with
any constant RHS, not just a constant integer RHS.  This implements
select.ll:test17

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21470 91177308-0d34-0410-b5e6-96231b3b80d8

add a new testcase

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21469 91177308-0d34-0410-b5e6-96231b3b80d8

Always enable the C backend.  This fixes a *vast* number of failures on the
testers last night, as llc was not getting the cbe linked in.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21468 91177308-0d34-0410-b5e6-96231b3b80d8

Add method to return the type this type will be promoted to if it is
passed through a variable argument function.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21462 91177308-0d34-0410-b5e6-96231b3b80d8

Mention the --enable-targets= option to configure.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21459 91177308-0d34-0410-b5e6-96231b3b80d8

* Order #includes as per style guide
* Combine multiple ``std::cerr <<'' statements into one for simplicity

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21458 91177308-0d34-0410-b5e6-96231b3b80d8

Convert tabs to spaces

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21457 91177308-0d34-0410-b5e6-96231b3b80d8

Hyphenate the adjective `n-bit' when used to describe values and processors

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21456 91177308-0d34-0410-b5e6-96231b3b80d8

Build the `Skeleton' target when building "all" targets

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21455 91177308-0d34-0410-b5e6-96231b3b80d8

Document the --enable-targets= feature of the configure script.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21454 91177308-0d34-0410-b5e6-96231b3b80d8

Silence gcc-4.0.0 warnings.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21453 91177308-0d34-0410-b5e6-96231b3b80d8

Convert tabs to spaces

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21452 91177308-0d34-0410-b5e6-96231b3b80d8

Don't always build CBackend and Skeleton. Make use of the TARGETS_TO_BUILD
parameter instead which will correctly list the set of targets to be built.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21451 91177308-0d34-0410-b5e6-96231b3b80d8

Implement the --enable-targets= feature of the configure script. The make
variable TARGETS_TO_BUILD is used to determine which targets in lib/Target
are built and which libraries are linked into llc. This effectively
implements the feature. One item remains: disabling targets in the dejagnu
test suite.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21450 91177308-0d34-0410-b5e6-96231b3b80d8

Two changes:
1. Get rid of TOOLLINKOPTS as it is a hold over from llvm-test and only
   used to communicate additional libraries to the linker. The *standard*
   way to do that is with the LIBS variable which this change supports.

2. Allow the TARGETS_TO_BUILD variable to be set from the configuration
   substitution. This is the result of the --enable-target= parameter to
   the configure script.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21449 91177308-0d34-0410-b5e6-96231b3b80d8

Make sure the CBackend is always a target that is built.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21448 91177308-0d34-0410-b5e6-96231b3b80d8

Consolidate the target selection options into a single option,
--enable-target which can take values "all", "host-only" or a comma
separated list of target names (alpha,ia64,powerpc,skeleton,sparc,x86)

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21447 91177308-0d34-0410-b5e6-96231b3b80d8

keep track of max depth stats

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21446 91177308-0d34-0410-b5e6-96231b3b80d8

First step in avoiding compilation/usage of non-relevant targets. New
options have been added to the configure script that control which targets
will be used. The options are:

--enable-target-this (default=disabled)
  This will specify that the target corresponding to the build host is
  the target that will be compiled/used. You can't use this with any of
  the other options (they'll be ignored). This is what most people want.

--disable-target-x86 (default=enabled)
  This will prevent the X86 target(s) from being compiled/used.

--disable-target-sparc (default=enabled)
  This will prevent both SparcV8 and SparcV9 from being compiled/used.

--disable-target-powerpc (default=enabled)
  This will prevent the PowerPC target from being compiled/used.

--disable-target-alpha (default=enabled)
  This will prevent the Alpha target from being compiled/used.

--disable-target-ia64 (default=enabled)
  This will prevent the IA64 target from being compiled/used.

Note that without any of these options, the default behavior is to build
all targets, as is the current practice.

All these options do is set up the substititution variable TARGETS_TO_BUILD
which contains the targets that should be compiled/used. The variable is
intended to be used in the makefiles. Those changes will come later.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21445 91177308-0d34-0410-b5e6-96231b3b80d8

Updated dependence analyzer. Fixed numerous bugs. Same stage scheduling, etc.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21444 91177308-0d34-0410-b5e6-96231b3b80d8

Malloc/Free have mod/ref effects.  Do not allow CSE of function calls that
call malloc/free.  This fixes PR555.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21443 91177308-0d34-0410-b5e6-96231b3b80d8

remove 'another common example', which doesn't work with VC++, and indent
another example properly

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21442 91177308-0d34-0410-b5e6-96231b3b80d8

Eliminate tabs and trailing spaces

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21441 91177308-0d34-0410-b5e6-96231b3b80d8

Convert tabs to spaces

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21440 91177308-0d34-0410-b5e6-96231b3b80d8

Convert tabs to spaces

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21439 91177308-0d34-0410-b5e6-96231b3b80d8

Convert tabs to spaces

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21438 91177308-0d34-0410-b5e6-96231b3b80d8

Convert tabs to spaces

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21437 91177308-0d34-0410-b5e6-96231b3b80d8

Convert tabs to spaces

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21436 91177308-0d34-0410-b5e6-96231b3b80d8

Convert tabs to spaces

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21433 91177308-0d34-0410-b5e6-96231b3b80d8

Add the RUN: prefix to the start of the run line so this test doesn't fail.
BTW .. isn't the date on this funky? We haven't reachec 2005-05-09 yet???

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21432 91177308-0d34-0410-b5e6-96231b3b80d8

Change some old-style casts to C++ style casts to avoid warnings in XPS
compilation. This change has been waiting in the wings for a long time but
since Misha just did a global change, I figured now was the time to commit
it.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21431 91177308-0d34-0410-b5e6-96231b3b80d8

There is no =head3. Convert to =head2.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21430 91177308-0d34-0410-b5e6-96231b3b80d8

Correct the documentation to match the program.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21429 91177308-0d34-0410-b5e6-96231b3b80d8

Remove trailing whitespace

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21428 91177308-0d34-0410-b5e6-96231b3b80d8

Remove trailing whitespace

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21427 91177308-0d34-0410-b5e6-96231b3b80d8

* Remove trailing whitespace
* Convert tabs to spaces

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21426 91177308-0d34-0410-b5e6-96231b3b80d8

Remove trailing whitespace

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21425 91177308-0d34-0410-b5e6-96231b3b80d8

Remove trailing whitespace

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21424 91177308-0d34-0410-b5e6-96231b3b80d8

Remove trailing whitespace

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21422 91177308-0d34-0410-b5e6-96231b3b80d8

* Remove trailing whitespace
* Convert tabs to spaces

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21421 91177308-0d34-0410-b5e6-96231b3b80d8

Remove trailing whitespace

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21420 91177308-0d34-0410-b5e6-96231b3b80d8

* Remove trailing whitespace
* Convert tabs to spaces

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21418 91177308-0d34-0410-b5e6-96231b3b80d8

Remove trailing whitespace

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21417 91177308-0d34-0410-b5e6-96231b3b80d8

Remove trailing whitespace

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21416 91177308-0d34-0410-b5e6-96231b3b80d8