When factoring multiply expressions across adds, factor both
positive and negative forms of constants together.  This
allows us to compile:

int foo(int x, int y) {
    return (x-y) + (x-y) + (x-y);
}

into:

_foo:                                                       ## @foo
subl %esi, %edi
leal (%rdi,%rdi,2), %eax
ret

instead of (where the 3 and -3 were not factored):

_foo:
        imull   $-3, 8(%esp), %ecx
        imull   $3, 4(%esp), %eax
        addl    %ecx, %eax
        ret

this started out as:
    movl    12(%ebp), %ecx
    imull   $3, 8(%ebp), %eax
    subl    %ecx, %eax
    subl    %ecx, %eax
    subl    %ecx, %eax
    ret

This comes from PR5359.

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

test case we alredy get right.

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

Remove old header.

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

clean up some comments.

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

switch from std::map to DenseMap for rank data structures.

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

Remove derelict serialization code.

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

reuse negates where possible instead of always creating them from scratch.
This allows us to optimize test12 into:

define i32 @test12(i32 %X) {
  %factor = mul i32 %X, -3                        ; <i32> [#uses=1]
  %Z = add i32 %factor, 6                         ; <i32> [#uses=1]
  ret i32 %Z
}

instead of:

define i32 @test12(i32 %X) {
  %Y = sub i32 6, %X                              ; <i32> [#uses=1]
  %C = sub i32 %Y, %X                             ; <i32> [#uses=1]
  %Z = sub i32 %C, %X                             ; <i32> [#uses=1]
  ret i32 %Z
}

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

we don't need a smallptrset to detect duplicates, the values are
sorted, so we can just do a linear scan.

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

make reassociate more careful about not leaving around dead mul's

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

remove debug

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

teach reassociate to factor x+x+x -> x*3.  While I'm at it,
fix RemoveDeadBinaryOp to actually do something.

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

change reassociate to use SmallVector for its key datastructures
instead of std::vector.

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

change an if to an assert, fix comment.

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

move the rest of the add optimization code out to OptimizeAdd,
improve some comments, simplify a bit of code.

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

factor statistic updating better.

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

Silence compiler warning.

warning: comparison between signed and unsigned integer expressions

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

simple fix for an incorrect factoring which causes a
miscompilation, PR5458.

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

merge some more tests in.

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

filecheckize

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

fix refactoro

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

factor code out into helper functions.

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

switch some std::vector's to smallvector.  Reduce nesting.

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

use more modern datastructures.

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

clean up -debug output.

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

Document the edit-distance algorithm used in StringRef, switch it over
to SmallVector, and add a unit test.

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

this #include is ok.

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

fix Analysis/DebugInfo.h to not include Metadata.h.  Do this
by moving one method out of line and eliminating redundant checks
from other methods.

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

add some basic named MD tests.

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

use early exits to reduce indentation.

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

eliminate another copy of the mdnode printing logic, simplify the
one that remains.

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

random tidying for MDNode printing.

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

eliminate a bunch of useless forwarding functions with one caller.

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

make mdnMap type safe, rename accessors for consistency with the rest of llvm.

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

metadata can't be a global var initializer.

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

simplify mdnode printing logic.  Now N->dump() only
dumps one node instead of all of them.

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

don't unittest mdnode printing, we have disassembler tests for this.

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

unify two copies of the NamedMDNode printing code.

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

fix printing of function-local metadata to print all the operands of the
mdnode, not just operand 0 over and over.

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

simplify printing of mdstring and Argument.

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

simplify asmprinting of NamedMDNode

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

Remove #include of metadata.h from intrinsicinst.h.  The only
method that needs it (DbgValueInst::getValue) has been moved out
of line.

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

rename "elements" of metadata to "operands".  "Elements" are
things that occur in types.  "operands" are things that occur
in values.

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

Optimize MDNode to coallocate the operand list immediately
after the MDNode in memory.  This eliminates the operands
pointer and saves a new[] per node.

Note that the code in DIDerivedType::replaceAllUsesWith is wrong
and quite scary.  A MDNode should not be RAUW'd with something
else: this changes all uses of the mdnode, which may not be debug
info related!  Debug info should use something non-mdnode for
declarations.

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

tidy

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

do not bother reuniquing mdnodes whose operands drop to null.  Doing
so can be a huge performance issue when tearing down modules and mdnodes
are not guaranteed to be unique anyway.  This speeds up:
$ time ~/llvm/Release/bin/clang gcc.c -w -S -g

from 72 to 35s, where gcc.c is from:
http://people.csail.mit.edu/smcc/projects/single-file-programs/

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

remove some misleading comments.

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

Implement edit distance for StringRef

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

remove some fixme's

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

fix two bogus tests that the asmparser now rejects.

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

now that instruction metadata is only parsed in one place, eliminate the
parser-global MDsOnInst vector and make ParseInstructionMetadata return
its result by-ref through an argument like the entire rest of the parser.

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

reimplement ParseOptionalInfo as ParseOptionalCommaAlign, correctly
handle the comma case for metadata.

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

rename ParseOptionalCustomMetadata -> ParseInstructionMetadata,
and make it non-optional.  This fixes the bug where we'd accept
and ignore a spurious comma after some instructions.

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

convert 4 more instructions over.

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

add facilities to start factoring instruction metadata parsing
out of each opcode's handler.  Change ret over so far.

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

reimplement insertvalue/extractvalue metadata handling to not blindly
accept invalid input.  Actually add a testcase.

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

remove two bogus calls that accepted metadata in the middle of insert/extract value
*constant exprs*.

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

rename NamedOrCustomMD -> MetadataVar to follow conventions of all the rest of the code.

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

rename lltok::Metadata -> lltok::exclaim.  We name tokens
after their syntactic form, not their semantic form.

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

rename MetadataCache -> NumberedMetadata to follow the convention
used by other things.  Convert it to a vector since it is a dense
numbering.

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

rewrite ParseMDNodeVector to follow the normal patter used in the .ll parser.

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

rename ParseMDNode -> ParseMDNodeID, since it parses !42, not !{... } as you'd expect.

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

fix parsing of mdstring values.

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

remove the code added in r90497.  It has several major issues and no tests.

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

split t_Metadata into t_MDNode and t_MDString, eliminating some unsafe casting.

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

factor code even more.

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

simplify some code and unbreak the build by not consuming an
extra token.

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

remove a really wrong parenthesis.

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

clean up some really strange code.

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

change ParseMDString and ParseMDNode to take arguments of the right type.
This exposed a raft of other problems, which I'll deal with in subsequent
patches.

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

switch to TrackingVH instead of WeakVH, since these can never
be RAUW'd and go to null.  This also gets us some sorely lacking
type safety.

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

Each instruction is allowed to have *multiple* different
metadata objects on them.  Though the entire compiler supports this,
the asmparser didn't.

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

Do not crash when .ll printing metadata that smells like debug info, but isn't.

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

fix indentation, fit in 80 cols.

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

Replace a few more SmallVectors with arrays.

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

Use an array instead of a SmallVector.

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

remove a bunch of unneeded functions.

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

major cleanups, much of this file was incorrectly indented.

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

one pass of cleanup over DebugInfo.h.  Much more is still needed.

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

prune #includes.

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

Final step in the metadata API restructuring: move the
getMDKindID/getMDKindNames methods to LLVMContext (and add
convenience methods to Module), eliminating MetadataContext.
Move the state that it maintains out to LLVMContext.

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

just cleanup.

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

remove useless argument.

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

privatize another interface.

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

the only call to this function (from clang) has been removed, zap it.

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

remove some unneeded Metadata interfaces.

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

fix .cpp file to not wrap the entire file in namespace blocks.

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

tidy up debug info comments, use ->isVoidTy() where reasonable.

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

sink twine.h down out of Value.h.  It is annoying that you need
to #include Twine.h just to give a twine a default value.

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

Extern declaration for unordered.f32 libcall was not being emitted. Fixed that.

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

When doing v1->RAUW(v2), don't do anything to metadata.  We don't know
why one was replaced with the other.  Even in the specific case of
debug information, it doesn't make sense to transfer the location over,
this will just result in jumbled loc info.

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

sink the Instruction::HasMetadata bit into SubclassData.

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

add a layer of accessors around the Value::SubClassData member, and use
a convention (shadowing the setter with private forwarding function) to
prevent subclasses from accidentally using it.

This exposed some bogosity in ConstantExprs, which was propaging the
opcode of the constant expr into the NUW/NSW/Exact field in the
getWithOperands/getWithOperandReplaced methods.

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

This is a major cleanup of the instruction metadata interfaces that
I asked Devang to do back on Sep 27.  Instead of going through the
MetadataContext class with methods like getMD() and getMDs(), just
ask the instruction directly for its metadata with getMetadata()
and getAllMetadata().

This includes a variety of other fixes and improvements: previously
all Value*'s were bloated because the HasMetadata bit was thrown into
value, adding a 9th bit to a byte.  Now this is properly sunk down to
the Instruction class (the only place where it makes sense) and it
will be folded away somewhere soon.

This also fixes some confusion in getMDs and its clients about
whether the returned list is indexed by the MDID or densely packed.
This is now returned sorted and densely packed and the comments make
this clear.

This introduces a number of fixme's which I'll follow up on.

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

rearrange some code.

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

add IRBuilder.cpp to cmake

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

remove #include that comes in from ConstantFolder.h

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

remove #include of Function.h from IRBuilder

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

move debug info stuff out of line, allowing two #includes
to go away from IRBuilder.h

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

split code that doesn't need to be templated out of IRBuilder into a new
non-templated IRBuilderBase class.  Move that large CreateGlobalString
out of line, eliminating the need to #include GlobalVariable.h in IRBuilder.h

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

rename ivar to be more descriptive.

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