summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
Commit message (Collapse)AuthorAgeFilesLines
* 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
* Switch lowering: extract NextBlock function. NFC.Hans Wennborg2015-03-191-54/+21
| | | | llvm-svn: 232759
* Switch lowering: remove unnecessary ConstantInt casts. NFC.Hans Wennborg2015-03-191-22/+20
| | | | llvm-svn: 232729
* SelectionDAGBuilder: update comment in HandlePHINodesInSuccessorBlocks.Hans Wennborg2015-03-191-2/+2
| | | | | | | From what I can tell, the code is checking for PHIs that expect any value from this block, not just constants. llvm-svn: 232697
* Recommit r232027 with PR22883 fixed: Add infrastructure for support of ↵Daniel Sanders2015-03-131-0/+13
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | multiple memory constraints. The operand flag word for ISD::INLINEASM nodes now contains a 15-bit memory constraint ID when the operand kind is Kind_Mem. This constraint ID is a numeric equivalent to the constraint code string and is converted with a target specific hook in TargetLowering. This patch maps all memory constraints to InlineAsm::Constraint_m so there is no functional change at this point. It just proves that using these previously unused bits in the encoding of the flag word doesn't break anything. The next patch will make each target preserve the current mapping of everything to Constraint_m for itself while changing the target independent implementation of the hook to return Constraint_Unknown appropriately. Each target will then be adapted in separate patches to use appropriate Constraint_* values. PR22883 was caused the matching operands copying the whole of the operand flags for the matched operand. This included the constraint id which needed to be replaced with the operand number. This has been fixed with a conversion function. Following on from this, matching operands also used the operand number as the constraint id. This has been fixed by looking up the matched operand and taking it from there. llvm-svn: 232165
* [X86, AVX2] Replace inserti128 and extracti128 intrinsics with generic shufflesSanjay Patel2015-03-121-22/+0
| | | | | | | | | | | | | | | | | This should complete the job started in r231794 and continued in r232045: We want to replace as much custom x86 shuffling via intrinsics as possible because pushing the code down the generic shuffle optimization path allows for better codegen and less complexity in LLVM. AVX2 introduced proper integer variants of the hacked integer insert/extract C intrinsics that were created for this same functionality with AVX1. This should complete the removal of insert/extract128 intrinsics. The Clang precursor patch for this change was checked in at r232109. llvm-svn: 232120
* Revert "r232027 - Add infrastructure for support of multiple memory constraints"Hal Finkel2015-03-121-12/+0
| | | | | | | | | | | | | | | | | | | | | | | | This (r232027) has caused PR22883; so it seems those bits might be used by something else after all. Reverting until we can figure out what else to do. Original commit message: The operand flag word for ISD::INLINEASM nodes now contains a 15-bit memory constraint ID when the operand kind is Kind_Mem. This constraint ID is a numeric equivalent to the constraint code string and is converted with a target specific hook in TargetLowering. This patch maps all memory constraints to InlineAsm::Constraint_m so there is no functional change at this point. It just proves that using these previously unused bits in the encoding of the flag word doesn't break anything. The next patch will make each target preserve the current mapping of everything to Constraint_m for itself while changing the target independent implementation of the hook to return Constraint_Unknown appropriately. Each target will then be adapted in separate patches to use appropriate Constraint_* values. llvm-svn: 232093
* [X86, AVX] replace vextractf128 intrinsics with generic shufflesSanjay Patel2015-03-121-3/+0
| | | | | | | | | | | | | | | | | Now that we've replaced the vinsertf128 intrinsics, do the same for their extract twins. This is very much like D8086 (checked in at r231794): We want to replace as much custom x86 shuffling via intrinsics as possible because pushing the code down the generic shuffle optimization path allows for better codegen and less complexity in LLVM. This is also the LLVM sibling to the cfe D8275 patch. Differential Revision: http://reviews.llvm.org/D8276 llvm-svn: 232045
* Add infrastructure for support of multiple memory constraints.Daniel Sanders2015-03-121-0/+12
| | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: The operand flag word for ISD::INLINEASM nodes now contains a 15-bit memory constraint ID when the operand kind is Kind_Mem. This constraint ID is a numeric equivalent to the constraint code string and is converted with a target specific hook in TargetLowering. This patch maps all memory constraints to InlineAsm::Constraint_m so there is no functional change at this point. It just proves that using these previously unused bits in the encoding of the flag word doesn't break anything. The next patch will make each target preserve the current mapping of everything to Constraint_m for itself while changing the target independent implementation of the hook to return Constraint_Unknown appropriately. Each target will then be adapted in separate patches to use appropriate Constraint_* values. Reviewers: hfinkel Reviewed By: hfinkel Subscribers: hfinkel, jholewinski, llvm-commits Differential Revision: http://reviews.llvm.org/D8171 llvm-svn: 232027
* Handle big index in getelementptr instructionReid Kleckner2015-03-111-18/+9
| | | | | | | | | | | | | | | CodeGen incorrectly ignores (assert from APInt) constant index bigger than 2^64 in getelementptr instruction. This is a test and fix for that. Patch by Paweł Bylica! Reviewed By: rnk Subscribers: majnemer, rnk, mcrosier, resistor, llvm-commits Differential Revision: http://reviews.llvm.org/D8219 llvm-svn: 231984
* Teach lowering to correctly handle invoke statepoint and gc results tied to ↵Igor Laevsky2015-03-101-10/+29
| | | | | | | | | | | them. Note that we still can not lower gc.relocates for invoke statepoints. Also it extracts getCopyFromRegs helper function in SelectionDAGBuilder as we need to be able to customize type of the register exported from basic block during lowering of the gc.result. (Resubmitting this change after not being able to reproduce buildbot failure) Differential Revision: http://reviews.llvm.org/D7760 llvm-svn: 231800
* [X86, AVX] replace vinsertf128 intrinsics with generic shufflesSanjay Patel2015-03-101-3/+0
| | | | | | | | | | | | | | We want to replace as much custom x86 shuffling via intrinsics as possible because pushing the code down the generic shuffle optimization path allows for better codegen and less complexity in LLVM. This is the sibling patch for the Clang half of this change: http://reviews.llvm.org/D8088 Differential Revision: http://reviews.llvm.org/D8086 llvm-svn: 231794
* The operand flag word used in ISD::INLINEASM is an i32 not a pointer. NFC.Daniel Sanders2015-03-101-4/+2
| | | | | | | | | | | | | | | | | | | Summary: This is part of the work to support memory constraints that behave differently to 'm'. The subsequent patches will expand on the existing encoding (which is a 32-bit int) and as a result in some flag words will no longer fit into an i16. This problem only affected the MSP430 target which appears to have 16-bit pointers. Reviewers: hfinkel Reviewed By: hfinkel Subscribers: hfinkel, llvm-commits Differential Revision: http://reviews.llvm.org/D8168 llvm-svn: 231783
* DataLayout is mandatory, update the API to reflect it with references.Mehdi Amini2015-03-101-4/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Now that the DataLayout is a mandatory part of the module, let's start cleaning the codebase. This patch is a first attempt at doing that. This patch is not exactly NFC as for instance some places were passing a nullptr instead of the DataLayout, possibly just because there was a default value on the DataLayout argument to many functions in the API. Even though it is not purely NFC, there is no change in the validation. I turned as many pointer to DataLayout to references, this helped figuring out all the places where a nullptr could come up. I had initially a local version of this patch broken into over 30 independant, commits but some later commit were cleaning the API and touching part of the code modified in the previous commits, so it seemed cleaner without the intermediate state. Test Plan: Reviewers: echristo Subscribers: llvm-commits From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 231740
* SelectionDAGBuilder: Merge 3 copies of the limited precision exp2 emission code.Benjamin Kramer2015-03-051-251/+93
| | | | | | NFC intended. llvm-svn: 231406
* Replace llvm.frameallocate with llvm.frameescapeReid Kleckner2015-03-051-22/+24
| | | | | | | | | | Turns out it's pretty straightforward and simplifies the implementation. Reviewers: andrew.w.kaylor Differential Revision: http://reviews.llvm.org/D8051 llvm-svn: 231386
* Revert change r231366 as it broke clang-native-arm-cortex-a9 ↵Igor Laevsky2015-03-051-29/+10
| | | | | | Analysis/properties.m test. llvm-svn: 231374
* Teach lowering to correctly handle invoke statepoint and gc results tied to ↵Igor Laevsky2015-03-051-10/+29
| | | | | | | | them. Note that we still can not lower gc.relocates for invoke statepoints. Also it extracts getCopyFromRegs helper function in SelectionDAGBuilder as we need to be able to customize type of the register exported from basic block during lowering of the gc.result. llvm-svn: 231366
* getRegForInlineAsmConstraint wants to use TargetRegisterInfo forEric Christopher2015-02-261-11/+13
| | | | | | | | | a lookup, pass that in rather than use a naked call to getSubtargetImpl. This involved passing down and around either a TargetMachine or TargetRegisterInfo. Update all callers/definitions around the targets and SelectionDAG. llvm-svn: 230699
* ARM: treat [N x i32] and [N x i64] as AAPCS composite typesTim Northover2015-02-241-8/+7
| | | | | | | | | | | The logic is almost there already, with our special homogeneous aggregate handling. Tweaking it like this allows front-ends to emit AAPCS compliant code without ever having to count registers or add discarded padding arguments. Only arrays of i32 and i64 are needed to model AAPCS rules, but I decided to apply the logic to all integer arrays for more consistency. llvm-svn: 230348
* X86: Call __main using the SelectionDAGDavid Majnemer2015-02-211-1/+0
| | | | | | | | Synthesizing a call directly using the MI layer would confuse the frame lowering code. This is problematic as frame lowering is highly sensitive the particularities of calls, etc. llvm-svn: 230129
* Prefer SmallVector::append/insert over push_back loops.Benjamin Kramer2015-02-171-2/+1
| | | | | | Same functionality, but hoists the vector growth out of the loop. llvm-svn: 229500
* AArch64: Safely handle the incoming sret call argument.Andrew Trick2015-02-161-1/+2
| | | | | | | | | | | | | | | | | | This adds a safe interface to the machine independent InputArg struct for accessing the index of the original (IR-level) argument. When a non-native return type is lowered, we generate the hidden machine-level sret argument on-the-fly. Before this fix, we were representing this argument as OrigArgIndex == 0, which is an outright lie. In particular this crashed in the AArch64 backend where we actually try to access the type of the original argument. Now we use a sentinel value for machine arguments that have no original argument index. AArch64, ARM, Mips, and PPC now check for this case before accessing the original argument. Fixes <rdar://19792160> Null pointer assertion in AArch64TargetLowering llvm-svn: 229413
* CodeGen: Canonicalize access to function attributes, NFCDuncan P. N. Exon Smith2015-02-141-2/+1
| | | | | | | | | | | | | | | | | Canonicalize access to function attributes to use the simpler API. getAttributes().getAttribute(AttributeSet::FunctionIndex, Kind) => getFnAttribute(Kind) getAttributes().hasAttribute(AttributeSet::FunctionIndex, Kind) => hasFnAttribute(Kind) Also, add `Function::getFnStackAlignment()`, and canonicalize: getAttributes().getStackAlignment(AttributeSet::FunctionIndex) => getFnStackAlignment() llvm-svn: 229208
* MathExtras: Bring Count(Trailing|Leading)Ones and CountPopulation in line ↵Benjamin Kramer2015-02-121-3/+3
| | | | | | | | with countTrailingZeros Update all callers. llvm-svn: 228930
* Adding support for llvm.eh.begincatch and llvm.eh.endcatch intrinsics and ↵Andrew Kaylor2015-02-101-0/+3
| | | | | | | | beginning the documentation of native Windows exception handling. Differential Revision: http://reviews.llvm.org/D7398 llvm-svn: 228733
* Add a FIXME in SelectionDAGBuilder before an assert that is valid only on X86.Manuel Jacob2015-01-271-0/+3
| | | | | | | | | When lowering memcpy, memset or memmove, this assert checks whether the pointer operands are in an address space < 256 which means "user defined address space" on X86. However, this notion of "user defined address space" does not exist for other targets. llvm-svn: 227191
OpenPOWER on IntegriCloud