summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* 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
* [WinEH] Sink UnwindHelp completely out of IRDavid Majnemer2015-04-031-11/+0
| | | | | | | | We don't need to represent UnwindHelp in IR. Instead, we can use the knowledge that we are emitting the parent function to decide if we should create the UnwindHelp stack object. llvm-svn: 234061
* CodeGen: Assert that inlined-at locations agreeDuncan P. N. Exon Smith2015-04-031-8/+13
| | | | | | | | | | | | | | | | | As a follow-up to r234021, assert that a debug info intrinsic variable's `MDLocalVariable::getInlinedAt()` always matches the `MDLocation::getInlinedAt()` of its `!dbg` attachment. The goal here is to get rid of `MDLocalVariable::getInlinedAt()` entirely (PR22778), but I'll let these assertions bake for a while first. If you have an out-of-tree backend that just broke, you're probably attaching the wrong `DebugLoc` to a `DBG_VALUE` instruction. The one you want is the location that was attached to the corresponding `@llvm.dbg.declare` or `@llvm.dbg.value` call that you started with. llvm-svn: 234038
* SelectionDAG: Use specialized metadata nodes in EmitFuncArgumentDbgValue(), NFCDuncan P. N. Exon Smith2015-04-031-11/+9
| | | | | | | Use `MDLocalVariable` and `MDExpression` directly for the arguments of `EmitFuncArgumentDbgValue()` to simplify a follow-up patch. llvm-svn: 234026
* [WinEH] Generate .xdata for catch handlersDavid Majnemer2015-03-311-12/+0
| | | | | | | | | | | | | | This lets us catch exceptions in simple cases. N.B. Things that do not work include (but are not limited to): - Throwing from within a catch handler. - Catching an object with a named catch parameter. - 'CatchHigh' is fictitious, we aren't sure of its purpose. - We aren't entirely efficient with regards to the number of EH states that we generate. - IP-to-State tables are sensitive to the order of emission. llvm-svn: 233767
* [WinEH] Run cleanup handlers when an exception is thrownDavid Majnemer2015-03-301-4/+11
| | | | | | | | Generate tables in the .xdata section representing what actions to take when an exception is thrown. This currently fills in state for cleanups, catch handlers are still unfinished. llvm-svn: 233636
* [CodeGen] Don't attempt a tail-call with a non-forwarded explicit sret.Ahmed Bougacha2015-03-271-0/+5
| | | | | | | | | | | | Tailcalls are only OK with forwarded sret pointers. With explicit sret, one approximation is to check that the pointer isn't an Instruction, as in that case it might point into some local memory (alloca). That's not OK with tailcalls. Explicit sret counterpart to r233409. Differential Revison: http://reviews.llvm.org/D8510 llvm-svn: 233410
* [CodeGen] Don't attempt a tail-call with implicit sret.Ahmed Bougacha2015-03-271-0/+4
| | | | | | | | | Tailcalls are only OK with forwarded sret pointers. With sret demotion, they're not, as we'd have a pointer into a soon-to-be-dead stack frame. Differential Revison: http://reviews.llvm.org/D8510 llvm-svn: 233409
* WinEH: Create a parent frame alloca for HandlerType xdata tablesDavid Majnemer2015-03-271-1/+11
| | | | | | | | We don't have any logic to emit those tables yet, so the SDAG lowering of this intrinsic is just a stub. We can see the intrinsic in the prepared IR, though. llvm-svn: 233354
* WinEH: Create an unwind help alloca for __CxxFrameHandler3 xdata tablesReid Kleckner2015-03-251-0/+10
| | | | | | | | We don't have any logic to emit those tables yet, so the sdag lowering of this intrinsic is just a stub. We can see the intrinsic in the prepared IR, though. llvm-svn: 233209
* SelectionDAGBuilder: Rangeify a loop. NFC.Hans Wennborg2015-03-201-8/+6
| | | | llvm-svn: 232831
* SelectionDAGBuilder::handleJTSwitchCase, simplify loop; NFCHans Wennborg2015-03-201-9/+4
| | | | llvm-svn: 232830
* Rewrite SelectionDAGBuilder::Clusterify to run in linear time. NFC.Hans Wennborg2015-03-201-37/+34
| | | | | | | It was previously repeatedly erasing elements from the middle of a vector, causing O(n^2) worst-case run-time. llvm-svn: 232789
OpenPOWER on IntegriCloud