summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [SDag switch lowering] Simplify code a bit. No functional change intended.Benjamin Kramer2015-06-041-10/+9
| | | | llvm-svn: 239056
* Switch lowering: fix assert in buildBitTests (PR23738)Hans Wennborg2015-06-041-1/+2
| | | | | | | | When checking (High - Low + 1).sle(BitWidth), BitWidth would be truncated to the size of the left-hand side. In the case of this PR, the left-hand side was i4, so BitWidth=64 got truncated to 0 and the assert failed. llvm-svn: 239048
* Don't create a MIN/MAX node if the underlying compare has more than one use.James Molloy2015-06-041-1/+5
| | | | | | | | | If the compare in a select pattern has another use then it can't be removed, so we'd just be creating repeated code if we created a min/max node. Spotted by Matt Arsenault! llvm-svn: 239037
* [SelectionDAG] Fix PR23603.Sanjoy Das2015-06-021-1/+11
| | | | | | | | | | | | | | | | | | | | | Summary: LLVM's MI level notion of invariant_load is different from LLVM's IR level notion of invariant_load with respect to dereferenceability. The IR notion of invariant_load only guarantees that all *non-faulting* invariant loads result in the same value. The MI notion of invariant load guarantees that the load can be legally moved to any location within its containing function. The MI notion of invariant_load is stronger than the IR notion of invariant_load -- an MI invariant_load is an IR invariant_load + a guarantee that the location being loaded from is dereferenceable throughout the function's lifetime. Reviewers: hfinkel, reames Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D10075 llvm-svn: 238881
* Replace push_back(Constructor(foo)) with emplace_back(foo) for non-trivial typesBenjamin Kramer2015-05-291-4/+4
| | | | | | | | | | | | | | | | | | | | If the type isn't trivially moveable emplace can skip a potentially expensive move. It also saves a couple of characters. Call sites were found with the ASTMatcher + some semi-automated cleanup. memberCallExpr( argumentCountIs(1), callee(methodDecl(hasName("push_back"))), on(hasType(recordDecl(has(namedDecl(hasName("emplace_back")))))), hasArgument(0, bindTemporaryExpr( hasType(recordDecl(hasNonTrivialDestructor())), has(constructExpr()))), unless(isInTemplateInstantiation())) No functional change intended. llvm-svn: 238602
* Change Function::getIntrinsicID() to return an Intrinsic::ID. NFC.Pete Cooper2015-05-201-1/+1
| | | | | | | | Now that Intrinsic::ID is a typed enum, we can forward declare it and so return it from this method. This updates all users which were either using an unsigned to store it, or had a now unnecessary cast. llvm-svn: 237810
* MC: Clean up method names in MCContext.Jim Grosbach2015-05-181-2/+2
| | | | | | | The naming was a mish-mash of old and new style. Update to be consistent with the new. NFC. llvm-svn: 237594
* Preserve the order of READ_REGISTER and WRITE_REGISTERHal Finkel2015-05-181-2/+6
| | | | | | | | | | | | | At the present time, we don't have a way to represent general dependency relationships, so everything is represented using memory dependency. In order to preserve the data dependency of a READ_REGISTER on WRITE_REGISTER, we need to model WRITE_REGISTER as writing (which we had been doing) and model READ_REGISTER as reading (which we had not been doing). Fix this, and also the way that the chain operands were generated at the SDAG level. Patch by Nicholas Paul Johnson, thanks! Test case by me. llvm-svn: 237584
* Revert r237579, as it broke windows buildbotsOliver Stannard2015-05-181-1/+2
| | | | llvm-svn: 237583
* [LLVM - ARM/AArch64] Add ACLE special register intrinsicsOliver Stannard2015-05-181-2/+1
| | | | | | | | | | | | | | | | | | | This patch implements LLVM support for the ACLE special register intrinsics in section 10.1, __arm_{w,r}sr{,p,64}. This patch is intended to lower the read/write_register instrinsics, used to implement the special register intrinsics in the clang patch for special register intrinsics (see http://reviews.llvm.org/D9697), to ARM specific instructions MRC,MCR,MSR etc. to allow reading an writing of coprocessor registers in AArch32 and AArch64. This is done by inspecting the register string passed to the intrinsic and then lowering to the appropriate instruction. Patch by Luke Cheeseman. Differential Revision: http://reviews.llvm.org/D9699 llvm-svn: 237579
* [SDAGBuilder] Make the AArch64 builder happier.James Molloy2015-05-151-4/+4
| | | | | | | | I intended this loop to only unwrap SplitVector actions, but it was more broad than that, such as unwrapping WidenVector actions, which makes operations seem legal when they're not. llvm-svn: 237457
* Add SDNodes for umin, umax, smin and smax.James Molloy2015-05-151-9/+37
| | | | | | | | | | | | | This adds new SDNodes for signed/unsigned min/max. These nodes are built from select/icmp pairs matched at SDAGBuilder stage. This patch adds the nodes, as well as legalization support and sets them to be "expand" for all targets. NFC for now; this will be tested when I switch AArch64 to using these new nodes. llvm-svn: 237423
* Revert r237046. See the testcase on the thread where r237046 was committed.Nick Lewycky2015-05-131-20/+4
| | | | llvm-svn: 237317
* propagate IR-level fast-math-flags to DAG nodes; 2nd try; NFCSanjay Patel2015-05-111-4/+20
| | | | | | | | | | | | | | | | | | | | | | | This is a less ambitious version of: http://reviews.llvm.org/rL236546 because that was reverted in: http://reviews.llvm.org/rL236600 because it caused memory corruption that wasn't related to FMF but was actually due to making nodes with 2 operands derive from a plain SDNode rather than a BinarySDNode. This patch adds the minimum plumbing necessary to use IR-level fast-math-flags (FMF) in the backend without actually using them for anything yet. This is a follow-on to: http://reviews.llvm.org/rL235997 ...which split the existing nsw / nuw / exact flags and FMF into their own struct. llvm-svn: 237046
* Switch lowering: cluster adjacent fall-through cases even at -O0Hans Wennborg2015-05-081-3/+5
| | | | | | | It's cheap to do, and codegen is much faster if cases can be merged into clusters. llvm-svn: 236905
* Fix coding standart based on post submit comments.Igor Laevsky2015-05-081-4/+4
| | | | | | Differential Revision: http://reviews.llvm.org/D7760 llvm-svn: 236849
* Switch lowering: handle zero-weight branch probabilitiesHans Wennborg2015-05-071-16/+7
| | | | | | | | | | After r236617, branch probabilities are no longer guaranteed to be >= 1. This patch makes the swich lowering code handle that correctly, without bumping the branch weights by 1 which might cause overflow and skews the probabilities. Covered by @zero_weight_tree in test/CodeGen/X86/switch.ll. llvm-svn: 236739
* Allow 0-weight branches in BranchProbabilityInfo.Diego Novillo2015-05-061-1/+5
| | | | | | | | | | | | | | | | | | | | | | | Summary: When computing branch weights in BPI, we used to disallow branches with weight 0. This is a minor nuisance, because a branch with weight 0 is different to "don't have information". In the context of instrumentation, it may mean "never executed", in the context of sampling, it means "never or seldom executed". In allowing 0 weight branches, I ran into issues with the switch expansion code in selection DAG. It is currently hardwired to not handle branches with weight 0. To maintain the current behaviour, I changed it to use 1 when it finds 0, but perhaps the algorithm needs changes to tolerate branches with weight zero. Reviewers: hansw Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D9533 llvm-svn: 236617
* Revert r236546, "propagate IR-level fast-math-flags to DAG nodes (NFC)"NAKAMURA Takumi2015-05-061-20/+2
| | | | | | It caused undefined behavior. llvm-svn: 236600
* [SelectionDAG] Move RegsForValue into SelectionDAGBuilder.h. NFC.Sanjoy Das2015-05-051-85/+16
| | | | | | | | | | | | | | | Summary: The exported class will be used in later change, in StatepointLowering.cpp. It is still internal to SelectionDAG (not exported via include/). Reviewers: reames, atrick Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D9478 llvm-svn: 236554
* [SelectionDAG] Pass explicit type to lowerCallOperands. NFC.Sanjoy Das2015-05-051-4/+5
| | | | | | | | | | | | | | Summary: Currently this does not change anything, but change will be used in a later change to StatepointLowering.cpp Reviewers: reames, atrick Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D9477 llvm-svn: 236553
* propagate IR-level fast-math-flags to DAG nodes (NFC)Sanjay Patel2015-05-051-2/+20
| | | | | | | | | | | | | | | | | | | | | | | | This patch adds the minimum plumbing necessary to use IR-level fast-math-flags (FMF) in the backend without actually using them for anything yet. This is a follow-on to: http://reviews.llvm.org/rL235997 ...which split the existing nsw / nuw / exact flags and FMF into their own struct. There are 2 structural changes here: 1. The main diff is that we're preparing to extend the optimization flags to affect more than just binary SDNodes. Eg, IR intrinsics ( https://llvm.org/bugs/show_bug.cgi?id=21290 ) or non-binop nodes that don't even exist in IR such as FMA, FNEG, etc. 2. The other change is that we're actually copying the FP fast-math-flags from the IR instructions to SDNodes. Differential Revision: http://reviews.llvm.org/D8900 llvm-svn: 236546
* Inline local variable to silence unused warning.Daniel Jasper2015-04-301-2/+1
| | | | llvm-svn: 236212
* Switch lowering: use profile info to build weight-balanced binary search treesHans Wennborg2015-04-301-7/+35
| | | | | | | | | | | | | | This will cause hot nodes to appear closer to the root. The literature says building the tree like this makes it a near-optimal (in terms of search time given key frequencies) binary search tree. In LLVM's case, we can do up to 3 comparisons in each leaf node, so it might be better to opt for lower tree height in some cases; that's something to look into in the future. Differential Revision: http://reviews.llvm.org/D9318 llvm-svn: 236192
* IR: Give 'DI' prefix to debug info metadataDuncan P. N. Exon Smith2015-04-291-8/+8
| | | | | | | | | | | | | | | | | | | | | | | | | | | | Finish off PR23080 by renaming the debug info IR constructs from `MD*` to `DI*`. The last of the `DIDescriptor` classes were deleted in r235356, and the last of the related typedefs removed in r235413, so this has all baked for about a week. Note: If you have out-of-tree code (like a frontend), I recommend that you get everything compiling and tests passing with the *previous* commit before updating to this one. It'll be easier to keep track of what code is using the `DIDescriptor` hierarchy and what you've already updated, and I think you're extremely unlikely to insert bugs. YMMV of course. Back to *this* commit: I did this using the rename-md-di-nodes.sh upgrade script I've attached to PR23080 (both code and testcases) and filtered through clang-format-diff.py. I edited the tests for test/Assembler/invalid-generic-debug-node-*.ll by hand since the columns were off-by-three. It should work on your out-of-tree testcases (and code, if you've followed the advice in the previous paragraph). Some of the tests are in badly named files now (e.g., test/Assembler/invalid-mdcompositetype-missing-tag.ll should be 'dicompositetype'); I'll come back and move the files in a follow-up commit. llvm-svn: 236120
* Fixed masked gather/scatter switch-caseElena Demikhovsky2015-04-291-0/+2
| | | | llvm-svn: 236092
* fixed comments, blanks, nullptr; NFCElena Demikhovsky2015-04-291-5/+4
| | | | llvm-svn: 236086
* Reapply r235977 "[DebugInfo] Add debug locations to constant SD nodes"Sergey Dmitrouk2015-04-281-233/+268
| | | | | | | | | | | | | | | | | | | | | | | | | [DebugInfo] Add debug locations to constant SD nodes This adds debug location to constant nodes of Selection DAG and updates all places that create constants to pass debug locations (see PR13269). Can't guarantee that all locations are correct, but in a lot of cases choice is obvious, so most of them should be. At least all tests pass. Tests for these changes do not cover everything, instead just check it for SDNodes, ARM and AArch64 where it's easy to get incorrect locations on constants. This is not complete fix as FastISel contains workaround for wrong debug locations, which drops locations from instructions on processing constants, but there isn't currently a way to use debug locations from constants there as llvm::Constant doesn't cache it (yet). Although this is a bit different issue, not directly related to these changes. Differential Revision: http://reviews.llvm.org/D9084 llvm-svn: 235989
* Revert "[DebugInfo] Add debug locations to constant SD nodes"Daniel Jasper2015-04-281-268/+233
| | | | | | | This breaks a test: http://bb.pgr.jp/builders/cmake-llvm-x86_64-linux/builds/23870 llvm-svn: 235987
* [DebugInfo] Add debug locations to constant SD nodesSergey Dmitrouk2015-04-281-233/+268
| | | | | | | | | | | | | | | | | | | | | | | This adds debug location to constant nodes of Selection DAG and updates all places that create constants to pass debug locations (see PR13269). Can't guarantee that all locations are correct, but in a lot of cases choice is obvious, so most of them should be. At least all tests pass. Tests for these changes do not cover everything, instead just check it for SDNodes, ARM and AArch64 where it's easy to get incorrect locations on constants. This is not complete fix as FastISel contains workaround for wrong debug locations, which drops locations from instructions on processing constants, but there isn't currently a way to use debug locations from constants there as llvm::Constant doesn't cache it (yet). Although this is a bit different issue, not directly related to these changes. Differential Revision: http://reviews.llvm.org/D9084 llvm-svn: 235977
* Masked gather and scatter: Added code for SelectionDAG.Elena Demikhovsky2015-04-281-0/+150
| | | | | | | | All other patches, including tests will follow. http://reviews.llvm.org/D7665 llvm-svn: 235970
* Switch lowering: use uint32_t for weights everywhereHans Wennborg2015-04-271-5/+11
| | | | | | | | | I previously thought switch clusters would need to use uint64_t in case the weights of multiple cases overflowed a 32-bit int. It turns out that the weights on a terminator instruction are capped to allow for being added together, so using a uint32_t should be safe. llvm-svn: 235945
* Switch lowering: Take branch weight into account when ordering for fall-throughHans Wennborg2015-04-271-3/+4
| | | | | | | | | | | Previously, the code would try to put a fall-through case last, even if that meant moving a case with much higher branch weight further down the chain. Ordering by branch weight is most important, putting a fall-through block last is secondary. llvm-svn: 235942
* Switch lowering: order bit tests by branch weight.Hans Wennborg2015-04-271-1/+4
| | | | llvm-svn: 235912
* [SEH] Implement GetExceptionCode in __except blocksReid Kleckner2015-04-241-0/+12
| | | | | | | | | This introduces an intrinsic called llvm.eh.exceptioncode. It is lowered by copying the EAX value live into whatever basic block it is called from. Obviously, this only works if you insert it late during codegen, because otherwise mid-level passes might reschedule it. llvm-svn: 235768
* Switch lowering: fix APInt overflow causing infinite loop / OOMHans Wennborg2015-04-241-1/+2
| | | | llvm-svn: 235729
* Re-commit r235560: Switch lowering: extract jump tables and bit tests before ↵Hans Wennborg2015-04-231-663/+781
| | | | | | | | | | | building binary tree (PR22262) Third time's the charm. The previous commit was reverted as a reverse for-loop in SelectionDAGBuilder::lowerWorkItem did 'I--' on an iterator at the beginning of a vector, causing asserts when using debugging iterators. This commit fixes that. llvm-svn: 235608
* Revert r235560; this commit was causing several failed assertions in Debug ↵Aaron Ballman2015-04-231-780/+663
| | | | | | builds using MSVC's STL. The iterator is being used outside of its valid range. llvm-svn: 235597
* Switch lowering: extract jump tables and bit tests before building binary ↵Hans Wennborg2015-04-221-663/+780
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | tree (PR22262) This is a re-commit of r235101, which also fixes the problems with the previous patch: - Switches with only a default case and non-fallthrough were handled incorrectly - The previous patch tickled a bug in PowerPC Early-Return Creation which is fixed here. > This is a major rewrite of the SelectionDAG switch lowering. The previous code > would lower switches as a binary tre, discovering clusters of cases > suitable for lowering by jump tables or bit tests as it went along. To increase > the likelihood of finding jump tables, the binary tree pivot was selected to > maximize case density on both sides of the pivot. > > By not selecting the pivot in the middle, the binary trees would not always > be balanced, leading to performance problems in the generated code. > > This patch rewrites the lowering to search for clusters of cases > suitable for jump tables or bit tests first, and then builds the binary > tree around those clusters. This way, the binary tree will always be balanced. > > This has the added benefit of decoupling the different aspects of the lowering: > tree building and jump table or bit tests finding are now easier to tweak > separately. > > For example, this will enable us to balance the tree based on profile info > in the future. > > The algorithm for finding jump tables is quadratic, whereas the previous algorithm > was O(n log n) for common cases, and quadratic only in the worst-case. This > doesn't seem to be major problem in practice, e.g. compiling a file consisting > of a 10k-case switch was only 30% slower, and such large switches should be rare > in practice. Compiling e.g. gcc.c showed no compile-time difference. If this > does turn out to be a problem, we could limit the search space of the algorithm. > > This commit also disables all optimizations during switch lowering in -O0. > > Differential Revision: http://reviews.llvm.org/D8649 llvm-svn: 235560
* [patchpoint] Add support for symbolic patchpoint targets to SelectionDAG and theLang Hames2015-04-221-6/+12
| | | | | | | | | | | | X86 backend. The code generated for symbolic targets is identical to the code generated for constant targets, except that a relocation is emitted to fix up the actual target address at link-time. This allows IR and object files containing patchpoints to be cached across JIT-invocations where the target address may change. llvm-svn: 235483
* DebugInfo: Drop rest of DIDescriptor subclassesDuncan P. N. Exon Smith2015-04-211-5/+3
| | | | | | | Delete the remaining subclasses of (the already deleted) `DIDescriptor`. Part of PR23080. llvm-svn: 235404
* DebugInfo: Assert dbg.declare/value insts are validDuncan P. N. Exon Smith2015-04-211-5/+3
| | | | | | | | | | Remove early returns for when `getVariable()` is null, and just assert that it never happens. The Verifier already confirms that there's a valid variable on these intrinsics, so we should assume the debug info isn't broken. I also updated a check for a `!dbg` attachment, which the Verifier similarly guarantees. llvm-svn: 235400
* Revert the switch lowering change (r235101, r235103, r235106)Hans Wennborg2015-04-161-780/+663
| | | | | | Looks like it broke the sanitizer-ppc64-linux1 build. Reverting for now. llvm-svn: 235108
* Switch lowering: extract jump tables and bit tests before building binary ↵Hans Wennborg2015-04-161-663/+780
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | tree (PR22262) This is a major rewrite of the SelectionDAG switch lowering. The previous code would lower switches as a binary tre, discovering clusters of cases suitable for lowering by jump tables or bit tests as it went along. To increase the likelihood of finding jump tables, the binary tree pivot was selected to maximize case density on both sides of the pivot. By not selecting the pivot in the middle, the binary trees would not always be balanced, leading to performance problems in the generated code. This patch rewrites the lowering to search for clusters of cases suitable for jump tables or bit tests first, and then builds the binary tree around those clusters. This way, the binary tree will always be balanced. This has the added benefit of decoupling the different aspects of the lowering: tree building and jump table or bit tests finding are now easier to tweak separately. For example, this will enable us to balance the tree based on profile info in the future. The algorithm for finding jump tables is O(n^2), whereas the previous algorithm was O(n log n) for common cases, and quadratic only in the worst-case. This doesn't seem to be major problem in practice, e.g. compiling a file consisting of a 10k-case switch was only 30% slower, and such large switches should be rare in practice. Compiling e.g. gcc.c showed no compile-time difference. If this does turn out to be a problem, we could limit the search space of the algorithm. This commit also disables all optimizations during switch lowering in -O0. Differential Revision: http://reviews.llvm.org/D8649 llvm-svn: 235101
* DebugInfo: Gut DIVariable and DIGlobalVariableDuncan P. N. Exon Smith2015-04-141-1/+1
| | | | | | | | | | Gut all the non-pointer API from the variable wrappers, except an implicit conversion from `DIGlobalVariable` to `DIDescriptor`. Note that if you're updating out-of-tree code, `DIVariable` wraps `MDLocalVariable` (`MDVariable` is a common base class shared with `MDGlobalVariable`). llvm-svn: 234840
* SelectionDAG: Stop using DIVariable::isInlinedFnArgument()Duncan P. N. Exon Smith2015-04-131-1/+3
| | | | | | | | | | | | | | | | | | Instead of calling the somewhat confusingly-named `DIVariable::isInlinedFnArgument()`, do the check directly here. There's possibly a small functionality change here: instead of `dyn_cast<>`'ing `DV->getScope()` to `MDSubprogram`, I'm looking up the scope chain for the actual subprogram. I suspect that this is a no-op for function arguments so in practise there isn't a real difference. I've also added a `FIXME` to check the `inlinedAt:` chain instead, since I wonder if that would be more reliable than the `MDSubprogram::describes()` function. Since this was the only user of `DIVariable::isInlinedFnArgument()`, delete it. llvm-svn: 234799
* Allow memory intrinsics to be tail callsKrzysztof Parzyszek2015-04-131-8/+29
| | | | llvm-svn: 234764
* CodeGen: Stop using DIDescriptor::is*() and auto-castingDuncan P. N. Exon Smith2015-04-061-6/+2
| | | | | | Same as r234255, but for lib/CodeGen and lib/Target. llvm-svn: 234258
* [WinEH] Don't sink allocas into child handlersReid Kleckner2015-04-061-2/+4
| | | | | | | | | | The uselist isn't enough to infer anything about the lifetime of such allocas. If we want to re-add this optimization, we will need to leverage lifetime markers to do it. Fixes PR23122. llvm-svn: 234196
* [WinEH] Fill out .xdata for catch objectsDavid Majnemer2015-04-031-4/+4
| | | | | | | This add support for catching an exception such that an exception object available to the catch handler will be initialized by the runtime. llvm-svn: 234062
OpenPOWER on IntegriCloud