Optimize a common case in the Lengauer-Tarjan dominators algorithm. This gives a
9.7% speedup running domtree on test-suite.

Reviewed by Chris Lattner.

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

Revert functionality doug added in r98575 that was never
documented and only used by some clang stuff I just removed.

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

Reuse data fragments while lowering. Patch by David Meyer.

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

Fix formatting nits in the coding standards.  Reviewed by clattner.

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

fix this harder.

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

fix a bug I introduced on the other side of the #ifdef

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

reimplement SwapByteOrder.h in terms of overloading instead of
being in terms of excessively complex template logic.

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

Renaming ISD::BIT_CONVERT to ISD::BITCAST to better reflect the LLVM IR concept.

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

add a 'LLVMConstIntOfArbitraryPrecision' api to the C api,
patch by Greg Pfeil!

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

duncan's spider sense was right, I completely reversed the condition
on this instcombine xform.  This fixes a miscompilation of 403.gcc.

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

filecheckize

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

Fixed some style issues (no _, no spc after !)

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

Remove duplicated constants. Thanks to Jason for noticing it.

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

InstCombine: Implement X - A*-B -> X + A*B.

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

Make the <ARCH>ELFObjectWriter statics private

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

Fix misplaced statics.

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

Kill trailing whitespace

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

Refactor the ELFRelocationEntry (pull up) and move the arch-specific statics to inside the class where it belongs.

Next step is to rationally break apart the RecordRelocation()

Probably the step will be to have 1 member function for ech slot of the ELFRelocationEntry()

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

Fix epilogue codegen to avoid leaving the stack pointer in an invalid
state. Previously Thumb2 would restore sp from fp like this:
mov sp, r7
sub, sp, #4
If an interrupt is taken after the 'mov' but before the 'sub', callee-saved
registers might be clobbered by the interrupt handler. Instead, try
restoring directly from sp:
add sp, #4
Or, if necessary (with VLA, etc.) use a scratch register to compute sp and
then restore it:
sub.w r4, r7, #8
mov sp, r7
rdar://8465407

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

Add a newline.

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

llvmc: Make -march/-mcpu/-mtune behaviour more consistent with gcc.

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

If a GEP index simply advances by multiples of a type of zero size,
then replace the index with zero.

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

Fix a bug with extractelement on SPU.
In the attached testcase, the element was
never extracted (missing rotate).

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

Add basic CFI methods to the streamer interface.

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

Move the "gep undef" -> "undef" transform from instcombine to
InstructionSimplify.

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

Remove some #includes.

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

Implement the "if (X == 6 || X == 4)" -> "if ((X|2) == 6)" optimization.

This currently only catches the most basic case, a two-case switch, but can be
extended later.

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

Don't keep track of inserted phis in PromoteMemoryToRegister: the information
is never used.  Patch by Cameron Zwarich.

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

Fix a compiler warning about Kind being used uninitialized
when assertions are disabled.

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

Pseudos default to 4byte size, let the instruction size field notice
that branch tables are special.

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

Implement ELF object file writing support for the MBlaze backend. Its not perfect yet, but it works for many tests.

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

Implement branch analysis in the MBlaze backend.

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

Make it a little bit more explicit that the MBlaze backend only supports upto
32-bit immediate values.

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

Fix an error in the MBlaze delay slot filler where instructions that already
fill a delay slot are moved to fill a different delay slot.

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

fix comment

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

apparently tailcalls are better on darwin/x86-64 than on linux?

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

Initialize MemDep's TD member so buildbots don't trip over an uninitialized pointer (TD is passed to PHITransAddr).

I wonder why this didn't explode earlier.

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

Add a rather pointless InstructionSimplify transform, inspired by recent constant
folding improvements: if P points to a type of size zero, turn "gep P, N" into "P".
More generally, if a gep index type has size zero, instcombine could replace the
index with zero, but that is not done here.

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

Fix spelling.

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

More Thumb encodings.

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

Add encoding for ARM "trap" instruction.

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

The "trap" instruction is one of this which doesn't have a condition code. Hack
the code to not add a "condition code" if it's trap.

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

- Give "trap" the correct encoding, at least according to Darwin's assembler.
- Add comments saying where the encodings for other instructions came from.

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

apply Dan's fix for PR8268 which allows constant folding to handle indexes over
zero sized elements.  This allows us to compile:

  #include <string>
  void foo() { std::string s; }

into an empty function.

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

add some helper methods for asmprinter flags, from PR8417

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

implement PR8524, apparently mainline gas accepts movq as an alias for movd
when transfering between i64 gprs and mmx regs.

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

rework some DSE paths to use the newly-public "getPointerDependencyFrom"
method in MemDep instead of inserting an instruction, doing a query,
then removing it.  Neither operation is effectively cached.

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

the getLocationForSource/Dest methods can be static.

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

add "getLocation" method to AliasAnalysis for getting the source and
destination location of a memcpy/memmove.  I'm not clear about whether
TBAA works on these, so I'm leaving it out for now.  Dan, please revisit
this when convenient.

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

implement PR8576, deleting dead stores with intervening may-alias stores.

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

file checkize

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

add some random notes.

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

Use by-name rather than by-order operand matching for some NEON encodings.

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

optimize:
void a(int x) { if (((1<<x)&8)==0) b(); }

into "x != 3", which occurs over 100 times in 403.gcc but in no
other program in llvm-test.

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

tail calls on x86 are implemented.

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

BR_JTadd is ARM-only, so use the proper pseudo class to get the predicate.

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

Handle PCRel relocations with absolute values. Fixes PR8656.

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

Implement PR8644: forwarding a memcpy value to a byval,
allowing the memcpy to be eliminated.

Unfortunately, the requirements on byval's without explicit
alignment are really weak and impossible to predict in the
mid-level optimizer, so this doesn't kick in much with current
frontends.  The fix is to change clang to set alignment on all
byval arguments.

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

a byval argument without an align can have an arbitrary alignment
requirement on the input pointer.

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

A few more thumb instruction MC encodings.

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

Rewrite address handling to use a structure with all the possible address
mode variables. Handle frame indexes in load/store and allocas again.

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

STRH only needs the additional operand, not t2STRH. Also invert conditional
to match the one from the load emitter above.

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

Simplify code. No change in functionality.

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

Test commit: Fix two -Asserts mode warnings in StringMap.h.

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

Make this compile on case-sensitive file systemsw

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

Move some more hooks to TargetFrameInfo

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

Silence Release build warnings about unused functions.

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

Disable warning C4291 on MSVC. Caused because class AttributeList provides a non implemented operator delete without a corresponding new.

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

On X86, MEMBARRIER, MFENCE, SFENCE, LFENCE are not target memory intrinsics,
so don't claim they are.  They are allocated using DAG.getNode, so attempts
to access MemSDNode fields results in reading off the end of the allocated
memory.  This fixes crashes with "llc -debug" due to debug code trying to
print MemSDNode fields for these barrier nodes (since the crashes are not
deterministic, use valgrind to see this).  Add some nasty checking to try
to catch this kind of thing in the future.

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

Removing the useless test that I added recently. It was meant as an example, but not complicated enough to merit another test.

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

RABasic fix. Regalloc is responsible for updating block live ins.

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

Whitespace.

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

Fix old GCC build error.

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

Add more Thumb add instruction encodings.

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

Add Thumb encodings for some add instructions.

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

Add more encodings for Thumb instructions.

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

Detemplatize NodeRef.

It is now possible to navigate the B+-tree using NodeRef::subtree() and
NodeRef::size() without knowing the key and value template types used in the
tree.

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

Rename NodeBase::{key,val} as {first,second} and swap the BranchNode arrays such
that the noderefs are the first member in the object.

This is in preparation of detemplatization of tree navigation.

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

Have the getAddrMode3OpValue() function in ARMCodeEmitter.cpp produce the same
value that the one in ARMMCCodeEmitter.cpp does.

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

Check for _setjmp too, because it's also used.

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

Implement IntervalMap destructor.

Key and value objects may not be destructed instantly when they are erased from
the container, but they will be destructed eventually by the IntervalMap
destructor.

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

Implement IntervalMap::clear().

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

Support backwards iteration starting from end().

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

Add test for PR 8111.  By Frits van Bommel.

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

Fix ARM LDR* post-indexed operand encoding.

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

Encodings for the compare instructions.

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

The Vm and Vn register fields must be the same for a register-register vmov.

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

Fix a cut-n-paste-error.

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

Document the new GVN number table structure.

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

Operand names

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

trailing whitespace

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

Don't need to save piecemeal now.

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

Update comment.

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

Add encodings for some of the thumb ADD instructions. Tests will come once the
asm parser can handle them.

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

Update comment.

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

Clarify operand names.

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

Add a test for CodeGenPrepare's ability to look through PHI nodes when performing
addressing mode folding, introduced in r119853.

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

Refactor address mode handling into a single struct (ala x86), this
should give allow a wider range of addressing modes.

No functional change.

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

Fix encoding for ARM MLS instruction.

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

When folding addressing modes in CodeGenPrepare, attempt to look through PHI nodes
if all the operands of the PHI are equivalent.  This allows CodeGenPrepare to undo
unprofitable PRE transforms.

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