summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/SelectionDAG
Commit message (Collapse)AuthorAgeFilesLines
...
* [InlineCost] Improve the cost heuristic for SwitchJun Bum Lim2017-04-282-110/+44
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: The motivation example is like below which has 13 cases but only 2 distinct targets ``` lor.lhs.false2: ; preds = %if.then switch i32 %Status, label %if.then27 [ i32 -7012, label %if.end35 i32 -10008, label %if.end35 i32 -10016, label %if.end35 i32 15000, label %if.end35 i32 14013, label %if.end35 i32 10114, label %if.end35 i32 10107, label %if.end35 i32 10105, label %if.end35 i32 10013, label %if.end35 i32 10011, label %if.end35 i32 7008, label %if.end35 i32 7007, label %if.end35 i32 5002, label %if.end35 ] ``` which is compiled into a balanced binary tree like this on AArch64 (similar on X86) ``` .LBB853_9: // %lor.lhs.false2 mov w8, #10012 cmp w19, w8 b.gt .LBB853_14 // BB#10: // %lor.lhs.false2 mov w8, #5001 cmp w19, w8 b.gt .LBB853_18 // BB#11: // %lor.lhs.false2 mov w8, #-10016 cmp w19, w8 b.eq .LBB853_23 // BB#12: // %lor.lhs.false2 mov w8, #-10008 cmp w19, w8 b.eq .LBB853_23 // BB#13: // %lor.lhs.false2 mov w8, #-7012 cmp w19, w8 b.eq .LBB853_23 b .LBB853_3 .LBB853_14: // %lor.lhs.false2 mov w8, #14012 cmp w19, w8 b.gt .LBB853_21 // BB#15: // %lor.lhs.false2 mov w8, #-10105 add w8, w19, w8 cmp w8, #9 // =9 b.hi .LBB853_17 // BB#16: // %lor.lhs.false2 orr w9, wzr, #0x1 lsl w8, w9, w8 mov w9, #517 and w8, w8, w9 cbnz w8, .LBB853_23 .LBB853_17: // %lor.lhs.false2 mov w8, #10013 cmp w19, w8 b.eq .LBB853_23 b .LBB853_3 .LBB853_18: // %lor.lhs.false2 mov w8, #-7007 add w8, w19, w8 cmp w8, #2 // =2 b.lo .LBB853_23 // BB#19: // %lor.lhs.false2 mov w8, #5002 cmp w19, w8 b.eq .LBB853_23 // BB#20: // %lor.lhs.false2 mov w8, #10011 cmp w19, w8 b.eq .LBB853_23 b .LBB853_3 .LBB853_21: // %lor.lhs.false2 mov w8, #14013 cmp w19, w8 b.eq .LBB853_23 // BB#22: // %lor.lhs.false2 mov w8, #15000 cmp w19, w8 b.ne .LBB853_3 ``` However, the inline cost model estimates the cost to be linear with the number of distinct targets and the cost of the above switch is just 2 InstrCosts. The function containing this switch is then inlined about 900 times. This change use the general way of switch lowering for the inline heuristic. It etimate the number of case clusters with the suitability check for a jump table or bit test. Considering the binary search tree built for the clusters, this change modifies the model to be linear with the size of the balanced binary tree. The model is off by default for now : -inline-generic-switch-cost=false This change was originally proposed by Haicheng in D29870. Reviewers: hans, bmakam, chandlerc, eraman, haicheng, mcrosier Reviewed By: hans Subscribers: joerg, aemerson, llvm-commits, rengolin Differential Revision: https://reviews.llvm.org/D31085 llvm-svn: 301649
* [DAGCombiner] Add ComputeNumSignBits vector demanded elements support to ↵Simon Pilgrim2017-04-281-1/+39
| | | | | | | | ASHR and INSERT_VECTOR_ELT (reapplied) Reapplied r299221 after fix for nondeterminism in ThinLTO builder (rL301599), with extra check for implicit truncation of inserted element. llvm-svn: 301644
* [ValueTracking] Convert computeKnownBitsFromRangeMetadata to use KnownBits ↵Craig Topper2017-04-281-1/+1
| | | | | | struct. llvm-svn: 301626
* [SelectionDAG] Use KnownBits struct in DAG's computeKnownBits and ↵Craig Topper2017-04-287-521/+461
| | | | | | | | | | | | simplifyDemandedBits This patch replaces the separate APInts for KnownZero/KnownOne with a single KnownBits struct. This is similar to what was done to ValueTracking's version recently. This is largely a mechanical transformation from KnownZero to Known.Zero. Differential Revision: https://reviews.llvm.org/D32569 llvm-svn: 301620
* [SelectionDAG] Use various APInt methods to reduce temporary APInt creationCraig Topper2017-04-285-38/+29
| | | | | | This patch uses various APInt methods to reduce the number of temporary APInts. These were all found while working through converting SelectionDAG's computeKnownBits to also use the KnownBits struct recently added to the ValueTracking version. llvm-svn: 301618
* [APInt] Use inplace shift methods where possible. NFCICraig Topper2017-04-284-7/+7
| | | | llvm-svn: 301612
* Use a pointer type for target frame indices during statepoint loweringSanjoy Das2017-04-272-7/+19
| | | | | | | | | | | | | | | | | Summary: The type of the target frame index is intptr, not the type of the value we're going to store into it. Without this change we crash in the attached test case when trying to type-legalize a TargetFrameIndex. Patchpoint lowering types the target frame index as intptr as well. Reviewers: reames, bogner, arsenm Subscribers: arsenm, mcrosier, llvm-commits Differential Revision: https://reviews.llvm.org/D32256 llvm-svn: 301566
* [DAGCombiner] add (sext i1 X), 1 --> zext (not i1 X)Sanjay Patel2017-04-261-6/+23
| | | | | | | | | | | | Besides better codegen, the motivation is to be able to canonicalize this pattern in IR (currently we don't) knowing that the backend is prepared for that. This may also allow removing code for special constant cases in DAGCombiner::foldSelectOfConstants() that was added in D30180. Differential Revision: https://reviews.llvm.org/D31944 llvm-svn: 301457
* [ValueTracking] Introduce a KnownBits struct to wrap the two APInts for ↵Craig Topper2017-04-261-3/+4
| | | | | | | | | | | | | | | | computeKnownBits This patch introduces a new KnownBits struct that wraps the two APInt used by computeKnownBits. This allows us to treat them as more of a unit. Initially I've just altered the signatures of computeKnownBits and InstCombine's simplifyDemandedBits to pass a KnownBits reference instead of two separate APInt references. I'll do similar to the SelectionDAG version of computeKnownBits/simplifyDemandedBits as a separate patch. I've added a constructor that allows initializing both APInts to the same bit width with a starting value of 0. This reduces the repeated pattern of initializing both APInts. Once place default constructed the APInts so I added a default constructor for those cases. Going forward I would like to add more methods that will work on the pairs. For example trunc, zext, and sext occur on both APInts together in several places. We should probably add a clear method that can be used to clear both pieces. Maybe a method to check for conflicting information. A method to return (Zero|One) so we don't write it out everywhere. Maybe a method for (Zero|One).isAllOnesValue() to determine if all bits are known. I'm sure there are many other methods we can come up with. Differential Revision: https://reviews.llvm.org/D32376 llvm-svn: 301432
* [TargetLowering] fix isConstTrueVal to account for build vector truncationSanjay Patel2017-04-261-13/+17
| | | | | | | | | | | | | | Build vectors have magical truncation powers, so we have things like this: v4i1 = BUILD_VECTOR Constant:i32<1>, Constant:i32<1>, Constant:i32<1>, Constant:i32<1> v4i16 = BUILD_VECTOR Constant:i32<1>, Constant:i32<1>, Constant:i32<1>, Constant:i32<1> If we don't truncate the splat node returned by getConstantSplatNode(), then we won't find truth when ZeroOrNegativeOneBooleanContent is the rule. Differential Revision: https://reviews.llvm.org/D32505 llvm-svn: 301408
* Fix signed multiplication with overflow fallback.Ranjeet Singh2017-04-261-2/+2
| | | | | | | | | | | | | | | | For targets that don't have ISD::MULHS or ISD::SMUL_LOHI for the type and the double width type is illegal, then the two operands are sign extended to twice their size then multiplied to check for overflow. The extended upper halves were mismatched causing an incorrect result. This fixes the mismatch. A test was added for ARM V6-M where the bug was detected. Patch by James Duley. Differential Revision: https://reviews.llvm.org/D31807 llvm-svn: 301404
* [DAG] add FIXME comments for splat detection; NFCSanjay Patel2017-04-262-0/+7
| | | | llvm-svn: 301403
* [DAG] fix formatting of isConstantSplat(); NFCSanjay Patel2017-04-251-27/+23
| | | | llvm-svn: 301366
* [DAGCombiner] Refactor to make it easy to add support for vectors in a ↵Simon Pilgrim2017-04-251-10/+10
| | | | | | future patch. NFCI. llvm-svn: 301320
* [SelectionDAG] Use getBuildVector helper where possible. NFCISimon Pilgrim2017-04-254-20/+17
| | | | llvm-svn: 301314
* [SelectionDAG] Pull out repeated getValueType calls. NFCI.Simon Pilgrim2017-04-252-16/+16
| | | | | | Noticed in D32391. llvm-svn: 301308
* [DAGCombiner] Add vector support for (srl (trunc (srl x, c1)), c2) combine.Simon Pilgrim2017-04-251-17/+18
| | | | llvm-svn: 301305
* [SelectionDAG] Recognise splat vector isKnownToBeAPowerOfTwo one/sign bit ↵Simon Pilgrim2017-04-251-2/+2
| | | | | | shift cases. llvm-svn: 301303
* [DAGCombiner] Use SDValue::getConstantOperandVal helper where possible. NFCI.Simon Pilgrim2017-04-251-7/+5
| | | | llvm-svn: 301300
* [DAGCombiner] Use APInt::intersects to avoid tmp variable. NFCI.Simon Pilgrim2017-04-241-1/+3
| | | | llvm-svn: 301258
* Move value type list from TargetRegisterClass to TargetRegisterInfoKrzysztof Parzyszek2017-04-243-12/+13
| | | | | | Differential Revision: https://reviews.llvm.org/D31937 llvm-svn: 301234
* Revert r301231: Accidentally committed stale filesKrzysztof Parzyszek2017-04-243-12/+11
| | | | | | I forgot to commit local changes before commit. llvm-svn: 301232
* Move value type list from TargetRegisterClass to TargetRegisterInfoKrzysztof Parzyszek2017-04-243-11/+12
| | | | | | Differential Revision: https://reviews.llvm.org/D31937 llvm-svn: 301231
* CodeGen: Add a hook for getFenceOperandTyYaxun Liu2017-04-241-2/+2
| | | | | | | | | | | | | | Currently the operand type for ATOMIC_FENCE assumes value type of a pointer in address space 0. This is fine for most targets. However for amdgcn target, the size of pointer in address space 0 depends on triple environment. For amdgiz environment, it is 64 bit but for other environment it is 32 bit. On the other hand, amdgcn target expects 32 bit fence operands independent of the target triple environment. Therefore a hook is need in target lowering for getting the fence operand type. This patch has no effect on targets other than amdgcn. Differential Revision: https://reviews.llvm.org/D32186 llvm-svn: 301215
* [DAGCombiner] Updated bswap byte offset variable names to be more ↵Simon Pilgrim2017-04-241-13/+15
| | | | | | | | descriptive. NFC As discussed on D32039, use MaskByteOffset to describe the variable and also pull out repeated getOpcode() calls. llvm-svn: 301193
* [SDAG] Teach Chain Analysis about BaseIndexOffset addressing.Nirav Dave2017-04-241-2/+13
| | | | | | | | | | | | | | | | | | While we use BaseIndexOffset in FindBetterNeighborChains to appropriately realize they're almost the same address and should be improved concurrently we do not use it in isAlias using the non-index understanding FindBaseOffset instead. Adding a BaseIndexOffset check in isAlias like should allow indexed stores to be merged. FindBaseOffset to be excised in subsequent patch. Reviewers: jyknight, aditya_nandakumar, bogner Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D31987 llvm-svn: 301187
* Revert "[APInt] Fix a few places that use APInt::getRawData to operate ↵Renato Golin2017-04-235-10/+12
| | | | | | | | | | | | | | | | within the normal API." This reverts commit r301105, 4, 3 and 1, as a follow up of the previous revert, which broke even more bots. For reference: Revert "[APInt] Use operator<<= where possible. NFC" Revert "[APInt] Use operator<<= instead of shl where possible. NFC" Revert "[APInt] Use ashInPlace where possible." PR32754. llvm-svn: 301111
* [ARM] ScheduleDAGRRList::DelayForLiveRegsBottomUp must consider OptionalDefsArtyom Skrobov2017-04-231-0/+12
| | | | | | | | | | | | | | | | | Summary: D30400 has enabled tADC and tSBC instructions to be unglued, thereby allowing CPSR to remain live between Thumb1 scheduling units. Most Thumb1 instructions have an OptionalDef for CPSR; but the scheduler ignored the OptionalDefs, and could unwittingly insert a flag-setting instruction in between an ADDS and the corresponding ADC. Reviewers: javed.absar, atrick, MatzeB, t.p.northover, jmolloy, rengolin Reviewed By: javed.absar Subscribers: rogfer01, efriedma, aemerson, rengolin, llvm-commits, MatzeB Differential Revision: https://reviews.llvm.org/D31081 llvm-svn: 301106
* [APInt] Fix a few places that use APInt::getRawData to operate within the ↵Craig Topper2017-04-231-5/+3
| | | | | | | | | | normal API. getRawData exposes the internal type of the APInt class directly to its users. Ideally we wouldn't expose such an implementation detail. This patch fixes a few of the easy cases by using truncate, extract, or a rotate. llvm-svn: 301105
* [APInt] Use operator<<= where possible. NFCCraig Topper2017-04-232-3/+3
| | | | llvm-svn: 301104
* [APInt] Use operator<<= instead of shl where possible. NFCCraig Topper2017-04-232-2/+2
| | | | llvm-svn: 301103
* [APInt] Use ashInPlace where possible.Craig Topper2017-04-232-2/+2
| | | | llvm-svn: 301101
* [AArch64] Improve code generation for logical instructions takingAkira Hatanaka2017-04-211-30/+36
| | | | | | | | | | | | | | | | | | | | | | | | | | | | immediate operands. This commit adds an AArch64 dag-combine that optimizes code generation for logical instructions taking immediate operands. The optimization uses demanded bits to change a logical instruction's immediate operand so that the immediate can be folded into the immediate field of the instruction. This recommits r300932 and r300930, which was causing dag-combine to loop forever. The problem was that optimizeLogicalImm was returning true even when there was no change to the immediate node (which happened when the immediate was all zeros or ones), which caused dag-combine to push and pop the same node to the work list over and over again without making any progress. This commit fixes the bug by returning false early in optimizeLogicalImm if the immediate is all zeros or ones. Also, it changes the code to compare the immediate with 0 or Mask rather than calling countPopulation. rdar://problem/18231627 Differential Revision: https://reviews.llvm.org/D5591 llvm-svn: 301019
* Revert r300932 and r300930.Akira Hatanaka2017-04-211-36/+30
| | | | | | | | | It seems that r300930 was creating an infinite loop in dag-combine when compling the following file: MultiSource/Benchmarks/MiBench/consumer-typeset/z21.c llvm-svn: 300940
* [AArch64] Improve code generation for logical instructions takingAkira Hatanaka2017-04-211-30/+36
| | | | | | | | | | | | | | | | | | | | immediate operands. This commit adds an AArch64 dag-combine that optimizes code generation for logical instructions taking immediate operands. The optimization uses demanded bits to change a logical instruction's immediate operand so that the immediate can be folded into the immediate field of the instruction. This recommits r300913, which broke bots because I didn't fix a call to ShrinkDemandedConstant in SIISelLowering.cpp after changing the APIs of TargetLoweringOpt and TargetLowering. rdar://problem/18231627 Differential Revision: https://reviews.llvm.org/D5591 llvm-svn: 300930
* Revert "[AArch64] Improve code generation for logical instructions taking"Akira Hatanaka2017-04-201-36/+30
| | | | | | | | This reverts r300913. This broke bots. llvm-svn: 300916
* [AArch64] Improve code generation for logical instructions takingAkira Hatanaka2017-04-201-30/+36
| | | | | | | | | | | | | | | | immediate operands. This commit adds an AArch64 dag-combine that optimizes code generation for logical instructions taking immediate operands. The optimization uses demanded bits to change a logical instruction's immediate operand so that the immediate can be folded into the immediate field of the instruction. rdar://problem/18231627 Differential Revision: https://reviews.llvm.org/D5591 llvm-svn: 300913
* [Recycler] Add asan/msan annotations.Benjamin Kramer2017-04-201-2/+5
| | | | | | | | | | This enables use after free and uninit memory checking for memory returned by a recycler. SelectionDAG currently relies on the opcode of a free'd node being ISD::DELETED_NODE, so poke a hole in the asan poison for SDNode opcodes. This means that we won't find some issues, but only in SDag. llvm-svn: 300868
* CodeGen: Let frame index value type match alloca addr spaceYaxun Liu2017-04-202-7/+7
| | | | | | | | | | | | | | | | | | | | | | Recently alloca address space has been added to data layout. Due to this change, pointer returned by alloca may have different size as pointer in address space 0. However, currently the value type of frame index is assumed to be of the same size as pointer in address space 0. This patch fixes that. Most targets assume alloca returning pointer in address space 0, which is the default alloca address space. Therefore it is NFC for them. AMDGCN target with amdgiz environment requires this change since it assumes alloca returning pointer to addr space 5 and its size is 32, which is different from the size of pointer in addr space 0 which is 64. Differential Revision: https://reviews.llvm.org/D32021 llvm-svn: 300864
* [DAGCombiner] use more local variables in isAlias(); NFCISanjay Patel2017-04-201-9/+11
| | | | llvm-svn: 300860
* [APInt] Rename getSignBit to getSignMaskCraig Topper2017-04-204-33/+33
| | | | | | | | getSignBit is a static function that creates an APInt with only the sign bit set. getSignMask seems like a better name to convey its functionality. In fact several places use it and then store in an APInt named SignMask. Differential Revision: https://reviews.llvm.org/D32108 llvm-svn: 300856
* [DAGCombiner] fix variable names in isAlias(); NFCISanjay Patel2017-04-201-27/+28
| | | | | | | We started with zero-based params and switched to one-based locals... Also, variables start with a capital and functions do not. llvm-svn: 300854
* [DAGCombiner] give names to repeated calcs in isAlias(); NFCISanjay Patel2017-04-201-13/+11
| | | | llvm-svn: 300850
* [MVT][SVE] Scalable vector MVTs (3/3)Amara Emerson2017-04-201-2/+2
| | | | | | | | | | | | Adds MVT::ElementCount to represent the length of a vector which may be scalable, then adds helper functions that work with it. Patch by Graham Hunter. Differential Revision: https://reviews.llvm.org/D32019 llvm-svn: 300842
* [MVT][SVE] Scalable vector MVTs (1/3)Amara Emerson2017-04-202-15/+9
| | | | | | | | | | | | | | | | This patch adds a few helper functions to obtain new vector value types based on existing ones without needing to care about whether they are scalable or not. I've confined their use to a few common locations right now, and targets that don't have scalable vectors should never need to care about these. Patch by Graham Hunter. Differential Revision: https://reviews.llvm.org/D32017 llvm-svn: 300838
* [SelectionDAG] Fix another place that was passing a large value to ↵Craig Topper2017-04-201-15/+17
| | | | | | APInt::lshrInPlace. llvm-svn: 300821
* [SelectionDAG] Use getActiveBits() and countTrailingZeros() to avoid ↵Craig Topper2017-04-201-4/+3
| | | | | | creating temporary APInts with lshr and trunc. NFCI llvm-svn: 300819
* Recommit "[APInt] Add back the asserts that check that the APInt shift ↵Craig Topper2017-04-201-2/+3
| | | | | | | | methods aren't called with values larger than BitWidth." This includes a fix to clamp a right shift of larger than BitWidth in DAG combining. llvm-svn: 300816
* Temporarily revert r299221 to fix nondeterminism in ThinLTO builder.Galina Kistanova2017-04-191-35/+1
| | | | llvm-svn: 300783
* [DAG] add splat vector support for 'or' in SimplifyDemandedBitsSanjay Patel2017-04-191-2/+1
| | | | | | | | | | | I've changed one of the tests to not fold away, but we didn't and still don't do the transform that the comment claims we do (and I don't know why we'd want to do that). Follow-up to: https://reviews.llvm.org/rL300725 https://reviews.llvm.org/rL300763 llvm-svn: 300772
OpenPOWER on IntegriCloud