aboutsummaryrefslogtreecommitdiff
path: root/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
AgeCommit message (Collapse)Author
2012-02-03The type-legalizer often scalarizes code. One of the common patterns is ↵Nadav Rotem
extract-and-truncate. In this patch we optimize this pattern and convert the sequence into extract op of a narrow type. This allows the BUILD_VECTOR dag optimizations to construct efficient shuffle operations in many cases. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@149692 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-17Transform: (EXTRACT_VECTOR_ELT( VECTOR_SHUFFLE )) -> EXTRACT_VECTOR_ELT.Nadav Rotem
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@148337 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-17Teach DAG combiner to turn a BUILD_VECTOR of UNDEFs into an UNDEF of vector ↵Craig Topper
type. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@148297 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-15DAGCombiner: Deduplicate code.Benjamin Kramer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@148217 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-13DAGCombine's logic for forming pre- and post- indexed loads / stores were beingEvan Cheng
overly conservative. It was concerned about cases where it would prohibit folding simple [r, c] addressing modes. e.g. ldr r0, [r2] ldr r1, [r2, #4] => ldr r0, [r2], #4 ldr r1, [r2] Change the logic to look for such cases which allows it to form indexed memory ops more aggressively. rdar://10674430 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@148086 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-11Teach the X86 instruction selection to do some heroic transforms toChandler Carruth
detect a pattern which can be implemented with a small 'shl' embedded in the addressing mode scale. This happens in real code as follows: unsigned x = my_accelerator_table[input >> 11]; Here we have some lookup table that we look into using the high bits of 'input'. Each entity in the table is 4-bytes, which means this implicitly gets turned into (once lowered out of a GEP): *(unsigned*)((char*)my_accelerator_table + ((input >> 11) << 2)); The shift right followed by a shift left is canonicalized to a smaller shift right and masking off the low bits. That hides the shift right which x86 has an addressing mode designed to support. We now detect masks of this form, and produce the longer shift right followed by the proper addressing mode. In addition to saving a (rather large) instruction, this also reduces stalls in Intel chips on benchmarks I've measured. In order for all of this to work, one part of the DAG needs to be canonicalized *still further* than it currently is. This involves removing pointless 'trunc' nodes between a zextload and a zext. Without that, we end up generating spurious masks and hiding the pattern. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147936 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-07Replace some uses of hasNUsesOfValue(0, X) with !hasAnyUseOfValue(X)Craig Topper
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147733 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-07Add some DAG combines for SUBC/SUBE. If nothing uses the carry/borrow out of ↵Craig Topper
subc, turn it into a sub. Turn (subc x, x) into 0 with no borrow. Turn (subc x, 0) into x with no borrow. Turn (subc -1, x) into (xor x, -1) with no borrow. Turn sube with no borrow in into subc. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147728 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-05Prevent a DAGCombine from firing where there are two uses ofChandler Carruth
a combined-away node and the result of the combine isn't substantially smaller than the input, it's just canonicalized. This is the first part of a significant (7%) performance gain for Snappy's hot decompression loop. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147604 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-04Implement VECTOR_SHUFFLE canonicalizations during DAG combine.Craig Topper
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147525 91177308-0d34-0410-b5e6-96231b3b80d8
2011-12-26Make sure DAGCombiner doesn't introduce multiple loads from the same memory ↵Eli Friedman
location. PR10747, part 2. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147283 91177308-0d34-0410-b5e6-96231b3b80d8
2011-12-13Initial CodeGen support for CTTZ/CTLZ where a zero input produces anChandler Carruth
undefined result. This adds new ISD nodes for the new semantics, selecting them when the LLVM intrinsic indicates that the undef behavior is desired. The new nodes expand trivially to the old nodes, so targets don't actually need to do anything to support these new nodes besides indicating that they should be expanded. I've done this for all the operand types that I could figure out for all the targets. Owners of various targets, please review and let me know if any of these are incorrect. Note that the expand behavior is *conservatively correct*, and exactly matches LLVM's current behavior with these operations. Ideally this patch will not change behavior in any way. For example the regtest suite finds the exact same instruction sequences coming out of the code generator. That's why there are no new tests here -- all of this is being exercised by the existing test suite. Thanks to Duncan Sands for reviewing the various bits of this patch and helping me get the wrinkles ironed out with expanding for each target. Also thanks to Chris for clarifying through all the discussions that this is indeed the approach he was looking for. That said, there are likely still rough spots. Further review much appreciated. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@146466 91177308-0d34-0410-b5e6-96231b3b80d8
2011-12-07Zap unnecessary isIntDivCheap() check. PR11485. No testcase because this ↵Eli Friedman
doesn't affect any in-tree target. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@146015 91177308-0d34-0410-b5e6-96231b3b80d8
2011-12-07Fix an optimization involving EXTRACT_SUBVECTOR in DAGCombine so it behaves ↵Eli Friedman
correctly. PR11494. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@145996 91177308-0d34-0410-b5e6-96231b3b80d8
2011-12-02Move global variables in TargetMachine into new TargetOptions class. As an APINick Lewycky
change, now you need a TargetOptions object to create a TargetMachine. Clang patch to follow. One small functionality change in PTX. PTX had commented out the machine verifier parts in their copy of printAndVerify. That now calls the version in LLVMTargetMachine. Users of PTX who need verification disabled should rely on not passing the command-line flag to enable it. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@145714 91177308-0d34-0410-b5e6-96231b3b80d8
2011-11-28Revert r145273 and fix in SelectionDAG::InferPtrAlignment() instead.Evan Cheng
Conservatively returns zero when the GV does not specify an alignment nor is it initialized. Previously it returns ABI alignment for type of the GV. However, if the type is a "packed" type, then the under-specified alignments is attached to the load / store instructions. In that case, the alignment of the type cannot be trusted. rdar://10464621 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@145300 91177308-0d34-0410-b5e6-96231b3b80d8
2011-11-28DAG combine should not increase alignment of loads / stores with alignment lessEvan Cheng
than ABI alignment. These are loads / stores from / to "packed" data structures. Their alignments are intentionally under-specified. rdar://10301431 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@145273 91177308-0d34-0410-b5e6-96231b3b80d8
2011-11-16Make sure to replace the chain properly when DAGCombining a ↵Eli Friedman
LOAD+EXTRACT_VECTOR_ELT into a single LOAD. Fixes PR10747/PR11393. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@144863 91177308-0d34-0410-b5e6-96231b3b80d8
2011-11-15Remove some unnecessary includes of PseudoSourceValue.h.Jay Foad
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@144634 91177308-0d34-0410-b5e6-96231b3b80d8
2011-11-12Don't try to form pre/post-indexed loads/stores until after LegalizeDAG ↵Eli Friedman
runs. Fixes PR11029. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@144438 91177308-0d34-0410-b5e6-96231b3b80d8
2011-11-08Lower mem-ops to unaligned i32/i16 load/stores on ARM where supported.Lang Hames
Add support for trimming constants to GetDemandedBits. This fixes some funky constant generation that occurs when stores are expanded for targets that don't support unaligned stores natively. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@144102 91177308-0d34-0410-b5e6-96231b3b80d8
2011-11-08Added invariant field to the DAG.getLoad method and changed all calls.Pete Cooper
When this field is true it means that the load is from constant (runt-time or compile-time) and so can be hoisted from loops or moved around other memory accesses git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@144100 91177308-0d34-0410-b5e6-96231b3b80d8
2011-11-07Don't introduce custom nodes after legalization in TargetLowering::BuildSDIV()Richard Osborne
and TargetLowering::BuildUDIV(). Fixes PR11283 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@143964 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-31Cleanup. Document. Make sure that this build_vector optimization only runs ↵Nadav Rotem
before the op legalizer and that the used type is legal. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@143358 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-30Silence compiler warning.Benjamin Kramer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@143308 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-29Add a new DAGCombine optimization for BUILD_VECTOR.Nadav Rotem
If all of the inputs are zero/any_extended, create a new simple BV which can be further optimized by other BV optimizations. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@143297 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-27Don't crash on 128-bit sdiv by constant. Found by inspection.Eli Friedman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@143095 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-25Remove a couple redundant checks.Eli Friedman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142959 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-18Fix a DAG combiner assertion failure when constant folding BUILD_VECTORS.Bob Wilson
svn r139159 caused SelectionDAG::getConstant() to promote BUILD_VECTOR operands with illegal types, even before type legalization. For this testcase, that led to one BUILD_VECTOR with i16 operands and another with promoted i32 operands, which triggered the assertion. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142370 91177308-0d34-0410-b5e6-96231b3b80d8
2011-09-22Fix SimplifySelectCC to add newly created nodes to the DAGCombinerDan Gohman
worklist, as it may be possible to perform further optimization on them. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@140349 91177308-0d34-0410-b5e6-96231b3b80d8
2011-09-20Add a DAGCombine for subvector extracts to remove useless chains ofBruno Cardoso Lopes
subvector inserts and extracts. Initial patch by Rackover, Zvi with some tweak done by me. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@140204 91177308-0d34-0410-b5e6-96231b3b80d8
2011-09-09Make the SelectionDAG verify that all the operands of BUILD_VECTOR have the ↵Eli Friedman
same type. Teach DAGCombiner::visitINSERT_VECTOR_ELT not to make invalid BUILD_VECTORs. Fixes PR10897. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139407 91177308-0d34-0410-b5e6-96231b3b80d8
2011-09-06Add codegen support for vector select (in the IR this means a selectDuncan Sands
with a vector condition); such selects become VSELECT codegen nodes. This patch also removes VSETCC codegen nodes, unifying them with SETCC nodes (codegen was actually often using SETCC for vector SETCC already). This ensures that various DAG combiner optimizations kick in for vector comparisons. Passes dragonegg bootstrap with no testsuite regressions (nightly testsuite as well as "make check-all"). Patch mostly by Nadav Rotem. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139159 91177308-0d34-0410-b5e6-96231b3b80d8
2011-08-19Roll back the rest of r126557. It's a hack that will break in some obscure ↵Benjamin Kramer
cases. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@138130 91177308-0d34-0410-b5e6-96231b3b80d8
2011-08-12Revert r137310 because it does not optimize any code on ToTNadav Rotem
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@137466 91177308-0d34-0410-b5e6-96231b3b80d8
2011-08-11[AVX] When joining two XMM registers into a YMM register, make sure that theNadav Rotem
lower XMM register gets in first. This will allow the SUBREG pattern to elliminate the first vector insertion. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@137310 91177308-0d34-0410-b5e6-96231b3b80d8
2011-07-25Make sure this DAGCombine actually returns an UNDEF of the correct type; ↵Eli Friedman
PR10476. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135993 91177308-0d34-0410-b5e6-96231b3b80d8
2011-07-18land David Blaikie's patch to de-constify Type, with a few tweaks.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135375 91177308-0d34-0410-b5e6-96231b3b80d8
2011-07-14Add a dag combine pattern for folding C2-(A+C1) -> (C2-C1)-AEric Christopher
Fixes rdar://9761830 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135123 91177308-0d34-0410-b5e6-96231b3b80d8
2011-07-07Add functions 'hasPredecessor' and 'hasPredecessorHelper' to SDNode. TheLang Hames
hasPredecessorHelper function allows predecessors to be cached to speed up repeated invocations. This fixes PR10186. X.isPredecessorOf(Y) now just calls Y.hasPredecessor(X) Y.hasPredecessor(X) calls Y.hasPredecessorHelper(X, Visited, Worklist) with empty Visited and Worklist sets (i.e. no caching over invocations). Y.hasPredecessorHelper(X, Visited, Worklist) caches search state in Visited and Worklist to speed up repeated calls. The Visited set is searched for X before going to the worklist to further search the DAG if necessary. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@134592 91177308-0d34-0410-b5e6-96231b3b80d8
2011-06-29Revert a part of r126557 which could create unschedulable DAGs.Benjamin Kramer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@134067 91177308-0d34-0410-b5e6-96231b3b80d8
2011-06-22Replace the existing forms of ConstantArray::get() with a single formJay Foad
that takes an ArrayRef. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@133615 91177308-0d34-0410-b5e6-96231b3b80d8
2011-06-21Teach dag combine to match halfword byteswap patterns.Evan Cheng
1. (((x) & 0xFF00) >> 8) | (((x) & 0x00FF) << 8) => (bswap x) >> 16 2. ((x&0xff)<<8)|((x&0xff00)>>8)|((x&0xff000000)>>8)|((x&0x00ff0000)<<8)) => (rotl (bswap x) 16) This allows us to eliminate most of the def : Pat patterns for ARM rev16 revsh instructions. It catches many more cases for ARM and x86. rdar://9609108 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@133503 91177308-0d34-0410-b5e6-96231b3b80d8
2011-06-16Add a DAGCombine for (ext (binop (load x), cst)).Nick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@133124 91177308-0d34-0410-b5e6-96231b3b80d8
2011-06-15Enable the simplification of truncating-store after fixing the usage ofNadav Rotem
GetDemandBits (which must operate on the vector element type). Fix the a usage of getZeroExtendInReg which must also be done on scalar types. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@133052 91177308-0d34-0410-b5e6-96231b3b80d8
2011-06-14When pattern matching during instruction selection make sure shl x,1 is notChad Rosier
converted to add x,x if x is a undef. add undef, undef does not guarantee that the resulting low order bit is zero. Fixes <rdar://problem/9453156> and <rdar://problem/9487392>. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@133022 91177308-0d34-0410-b5e6-96231b3b80d8
2011-06-14Disable trunc-store simplification on vectors.Nadav Rotem
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@132984 91177308-0d34-0410-b5e6-96231b3b80d8
2011-06-09Change this DAGCombine to build AND of SHR instead of SHR of AND; this ↵Eli Friedman
matches the ordering we prefer in instcombine. Part of rdar://9562809. The potential DAGCombine which enforces this more generally messes up some other very fragile patterns, so I'm leaving that alone, at least for now. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@132809 91177308-0d34-0410-b5e6-96231b3b80d8
2011-05-23Revert 121907 (it causes llc crash) and apply original patch from PR9817.Devang Patel
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@131926 91177308-0d34-0410-b5e6-96231b3b80d8
2011-05-21Implement mulo x, 2 -> addo x, x in DAGCombiner.Benjamin Kramer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@131800 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-04-29 15:45:02 +0000