summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
* Round 2 of dead private variable removal.Benjamin Kramer2012-06-062-5/+3
| | | | | | | | LLVM is now -Wunused-private-field clean except for - lib/MC/MCDisassembler/Disassembler.h. Not sure why it keeps all those unaccessible fields. - gtest. llvm-svn: 158096
* Fix typos found by http://github.com/lyda/misspell-checkBenjamin Kramer2012-06-023-3/+3
| | | | llvm-svn: 157885
* Add support for enum forward declarations.Eric Christopher2012-06-011-2/+2
| | | | | | Part of rdar://11570854 llvm-svn: 157786
* Make sure that we're dealing with a binary SCEVExpr when simplifying.Benjamin Kramer2012-05-301-1/+2
| | | | llvm-svn: 157704
* Teach SCEV's icmp simplification logic that a-b == 0 is equivalent to a == b.Benjamin Kramer2012-05-301-1/+20
| | | | | | | | | | | | | | | This also required making recursive simplifications until nothing changes or a hard limit (currently 3) is hit. With the simplification in place indvars can canonicalize loops of the form for (unsigned i = 0; i < a-b; ++i) into for (unsigned i = 0; i != a-b; ++i) which used to fail because SCEV created a weird umax expr for the backedge taken count. llvm-svn: 157701
* SCEV: Handle a corner case reducing AddRecExpr * AddRecExprAndrew Trick2012-05-301-1/+4
| | | | | | | | | If integer overflow causes one of the terms to reach zero, that can force the entire expression to zero. Fixes PR12929: cast<Ty>() argument of incompatible type llvm-svn: 157673
* Reformat the loop that does AddRecExpr * AddRecExpr reduction.Andrew Trick2012-05-301-55/+56
| | | | | | No functionality. llvm-svn: 157672
* Mark some static arrays as const.Craig Topper2012-05-241-2/+2
| | | | llvm-svn: 157377
* Add support for C++11 enum classes in llvm.Eric Christopher2012-05-231-2/+3
| | | | | | Part of rdar://11496790 llvm-svn: 157303
* LSR fix: add a missing phi check during IV hoisting.Andrew Trick2012-05-221-1/+2
| | | | | | Fixes PR12898: SCEVExpander crash. llvm-svn: 157263
* Actually support DW_TAG_rvalue_reference_type that we were tryingEric Christopher2012-05-192-9/+14
| | | | | | | | to generate out of the front end. rdar://11479676 llvm-svn: 157094
* SCEV: Add MarkPendingLoopPredicates to avoid recursive isImpliedCond.Andrew Trick2012-05-191-0/+24
| | | | | | | | | | getUDivExpr attempts to simplify by checking for overflow. isLoopEntryGuardedByCond then evaluates the loop predicate which may lead to the same getUDivExpr causing endless recursion. Fixes PR12868: clang 3.2 segmentation fault. llvm-svn: 157092
* allow LazyValueInfo::getEdgeValue() to reason about multiple edges from the ↵Nuno Lopes2012-05-181-11/+6
| | | | | | same switch instruction by doing union of ranges (which may still be conservative, but it's more aggressive than before) llvm-svn: 157071
* Clarify comment.Eric Christopher2012-05-181-1/+1
| | | | llvm-svn: 157033
* minor simplification in the call to ConstantRange constructorNuno Lopes2012-05-171-1/+1
| | | | llvm-svn: 157024
* Remove extraneous ';'.Bill Wendling2012-05-171-1/+1
| | | | llvm-svn: 157011
* reuse the result of some expensive computations in getSignExtendExpr() and ↵Nuno Lopes2012-05-151-18/+20
| | | | | | | | getZeroExtendExpr() this gives a speedup of > 80 in a debug build in the test case of PR12825 (php_sha512_crypt_r) llvm-svn: 156849
* minor simplification to code: Ty is already a SCEV type; don't need to run ↵Nuno Lopes2012-05-151-6/+3
| | | | | | getEffectiveSCEVType() twice llvm-svn: 156823
* Move the capture analysis from MemoryDependencyAnalysis to a more general placeChad Rosier2012-05-142-85/+88
| | | | | | | | | so that it can be reused in MemCpyOptimizer. This analysis is needed to remove an unnecessary memcpy when returning a struct into a local variable. rdar://11341081 PR12686 llvm-svn: 156776
* Hoist simpler checks above llvm::PointerMayBeCaptured. No functional change ↵Chad Rosier2012-05-121-4/+6
| | | | | | intended. llvm-svn: 156687
* Fix intendation.Chad Rosier2012-05-101-1/+1
| | | | llvm-svn: 156589
* Teach DeadStoreElimination to eliminate exit-block stores with phi addresses.Dan Gohman2012-05-101-0/+31
| | | | llvm-svn: 156558
* Rewrite ScalarEvolution::hasOperand to use an explicit worklist insteadDan Gohman2012-05-101-35/+50
| | | | | | of recursion, to avoid excessive stack usage on deep expressions. llvm-svn: 156554
* Rename the Region::block_iterator to Region::block_node_iterator, andChandler Carruth2012-05-043-12/+29
| | | | | | | | | | | | | | | | | | | | | | | | add a new Region::block_iterator which actually iterates over the basic blocks of the region. The old iterator, now call 'block_node_iterator' iterates over RegionNodes which contain a single basic block. This works well with the GraphTraits-based iterator design, however most users actually want an iterator over the BasicBlocks inside these RegionNodes. Now the 'block_iterator' is a wrapper which exposes exactly this interface. Internally it uses the block_node_iterator to walk all nodes which are single basic blocks, but transparently unwraps the basic block to make user code simpler. While this patch is a bit of a wash, most of the updates are to internal users, not external users of the RegionInfo. I have an accompanying patch to Polly that is a strict simplification of every user of this interface, and I'm working on a pass that also wants the same simplified interface. This patch alone should have no functional impact. llvm-svn: 156202
* A pile of long over-due refactorings here. There are some very, *very*Chandler Carruth2012-05-042-42/+34
| | | | | | | | | | | | | | | | | | | | | | | | | | minor behavior changes with this, but nothing I have seen evidence of in the wild or expect to be meaningful. The real goal is unifying our logic and simplifying the interfaces. A summary of the changes follows: - Make 'callIsSmall' actually accept a callsite so it can handle intrinsics, and simplify callers appropriately. - Nuke a completely bogus declaration of 'callIsSmall' that was still lurking in InlineCost.h... No idea how this got missed. - Teach the 'isInstructionFree' about the various more intelligent 'free' heuristics that got added to the inline cost analysis during review and testing. This mostly surrounds int->ptr and ptr->int casts. - Switch most of the interesting parts of the inline cost analysis that were essentially computing 'is this instruction free?' to use the code metrics routine instead. This way we won't keep duplicating logic. All of this is motivated by the desire to allow other passes to compute a roughly equivalent 'cost' metric for a particular basic block as the inline cost analysis. Sadly, re-using the same analysis for both is really messy because only the actual inline cost analysis is ever going to go to the contortions required for simplification, SROA analysis, etc. llvm-svn: 156140
* remove calls to calloc if the allocated memory is not used (it was already ↵Nuno Lopes2012-05-031-2/+2
| | | | | | | | being done for malloc) fix a few typos found by Chad in my previous commit llvm-svn: 156110
* add support for calloc to objectsize loweringNuno Lopes2012-05-031-0/+40
| | | | llvm-svn: 156102
* Just mark the sign bit as known zero, rather than any other irrelevant bitsDuncan Sands2012-04-301-1/+1
| | | | | | known zero in the LHS. Fixes PR12541. llvm-svn: 155818
* Reapply r155682, making constant folding more consistent, with a fix to workDan Gohman2012-04-271-7/+20
| | | | | | properly with how the code handles all-undef PHI nodes. llvm-svn: 155721
* Revert r155682, "Use ConstantExpr::getExtractElement when constant-folding ↵NAKAMURA Takumi2012-04-271-14/+4
| | | | | | | | vectors" It broke stage2 build. stage1/clang sometimes crashed. llvm-svn: 155699
* Use ConstantExpr::getExtractElement when constant-folding vectorsDan Gohman2012-04-271-4/+14
| | | | | | | | | | | | | | | | | | | | | instead of getAggregateElement. This has the advantage of being more consistent and allowing higher-level constant folding to procede even if an inner extract element cannot be folded. Make ConstantFoldInstruction call ConstantFoldConstantExpression on the instruction's operands, making it more consistent with ConstantFoldConstantExpression itself. This makes sure that ConstantExprs get TargetData-aware folding before being handed off as operands for further folding. This causes more expressions to be folded, but due to a known shortcoming in constant folding, this currently has the side effect of stripping a few more nuw and inbounds flags in the non-targetdata side of constant-fold-gep.ll. This is mostly harmless. This fixes rdar://11324230. llvm-svn: 155682
* Fix a crash on valid (if UB) bitcode that is produced for some globalChandler Carruth2012-04-241-3/+11
| | | | | | | | | | | | | | | | | | | | | constants in C++11 mode. I have no idea why it required such particular circumstances to get here, the code seems clearly to rely upon unchecked assumptions. Specifically, when we decide to form an index into a struct type, we may have gone through (at least one) zero-length array indexing round, which would have left the offset un-adjusted, and thus not necessarily valid for use when indexing the struct type. This is just an canonicalization step, so the correct thing is to refuse to canonicalize nonsensical GEPs of this form. Implemented, and test case added. Fixes PR12642. Pair debugged and coded with Richard Smith. =] I credit him with most of the debugging, and preventing me from writing the wrong code. llvm-svn: 155466
* Allow forward declarations to take a context. This helps the debuggerEric Christopher2012-04-231-7/+8
| | | | | | | | | find forward declarations in the context that the actual definition will occur. rdar://11291658 llvm-svn: 155380
* Revert "SCEV: When expanding a GEP the final addition to the base pointer ↵Benjamin Kramer2012-04-171-1/+1
| | | | | | | | has NUW but not NSW." This isn't right either, reverting for now. llvm-svn: 154910
* Add two statistics to help track how we are computing the inline cost.Chandler Carruth2012-04-111-0/+5
| | | | | | Yea, 'NumCallerCallersAnalyzed' isn't a great name, suggestions welcome. llvm-svn: 154492
* Fix 12513: Loop unrolling breaks with indirect branches.Andrew Trick2012-04-101-0/+11
| | | | | | | | Take this opportunity to generalize the indirectbr bailout logic for loop transformations. CFG transformations will never get indirectbr right, and there's no point trying. llvm-svn: 154386
* Fix ValueTracking to conclude that debug intrinsics are safe toChandler Carruth2012-04-071-0/+8
| | | | | | | | | | | | | | | | | | speculate. Without this, loop rotate (among many other places) would suddenly stop working in the presence of debug info. I found this looking at loop rotate, and have augmented its tests with a reduction out of a very hot loop in yacr2 where failing to do this rotation costs sometimes more than 10% in runtime performance, perturbing numerous downstream optimizations. This should have no impact on performance without debug info, but the change in performance when debug info is enabled can be extreme. As a consequence (and this how I got to this yak) any profiling of performance problems should be treated with deep suspicion -- they may have been wildly innacurate of debug info was enabled for profiling. =/ Just a heads up. llvm-svn: 154263
* SCEV: When expanding a GEP the final addition to the base pointer has NUW ↵Benjamin Kramer2012-04-071-1/+1
| | | | | | | | but not NSW. Found by inspection. llvm-svn: 154262
* Reintroduce InlineCostAnalyzer::getInlineCost() variant with explicit calleeDavid Chisnall2012-04-061-1/+4
| | | | | | | | parameter until we have a more sensible API for doing the same thing. Reviewed by Chandler. llvm-svn: 154180
* Always compute all the bits in ComputeMaskedBits.Rafael Espindola2012-04-043-162/+102
| | | | | | | | This allows us to keep passing reduced masks to SimplifyDemandedBits, but know about all the bits if SimplifyDemandedBits fails. This allows instcombine to simplify cases like the one in the included testcase. llvm-svn: 154011
* Add a line number for the scope of the function (starting at the firstEric Christopher2012-04-032-2/+10
| | | | | | | | | | brace) so that we get more accurate line number information about the declaration of a given function and the line where the function first starts. Part of rdar://11026482 llvm-svn: 153916
* Teach CodeGen's version of computeMaskedBits to understand the range metadata.Rafael Espindola2012-03-311-2/+2
| | | | | | | | This is the CodeGen equivalent of r153747. I tested that there is not noticeable performance difference with any combination of -O0/-O2 /-g when compiling gcc as a single compilation unit. llvm-svn: 153817
* Fix a typo reported in IRC by someone reviewing this code.Chandler Carruth2012-03-311-1/+1
| | | | llvm-svn: 153815
* Remove a bunch of empty, dead, and no-op methods from all of theseChandler Carruth2012-03-311-10/+0
| | | | | | | | | | interfaces. These methods were used in the old inline cost system where there was a persistent cache that had to be updated, invalidated, and cleared. We're now doing more direct computations that don't require this intricate dance. Even if we resume some level of caching, it would almost certainly have a simpler and more narrow interface than this. llvm-svn: 153813
* Initial commit for the rewrite of the inline cost analysis to operateChandler Carruth2012-03-312-583/+946
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | on a per-callsite walk of the called function's instructions, in breadth-first order over the potentially reachable set of basic blocks. This is a major shift in how inline cost analysis works to improve the accuracy and rationality of inlining decisions. A brief outline of the algorithm this moves to: - Build a simplification mapping based on the callsite arguments to the function arguments. - Push the entry block onto a worklist of potentially-live basic blocks. - Pop the first block off of the *front* of the worklist (for breadth-first ordering) and walk its instructions using a custom InstVisitor. - For each instruction's operands, re-map them based on the simplification mappings available for the given callsite. - Compute any simplification possible of the instruction after re-mapping, and store that back int othe simplification mapping. - Compute any bonuses, costs, or other impacts of the instruction on the cost metric. - When the terminator is reached, replace any conditional value in the terminator with any simplifications from the mapping we have, and add any successors which are not proven to be dead from these simplifications to the worklist. - Pop the next block off of the front of the worklist, and repeat. - As soon as the cost of inlining exceeds the threshold for the callsite, stop analyzing the function in order to bound cost. The primary goal of this algorithm is to perfectly handle dead code paths. We do not want any code in trivially dead code paths to impact inlining decisions. The previous metric was *extremely* flawed here, and would always subtract the average cost of two successors of a conditional branch when it was proven to become an unconditional branch at the callsite. There was no handling of wildly different costs between the two successors, which would cause inlining when the path actually taken was too large, and no inlining when the path actually taken was trivially simple. There was also no handling of the code *path*, only the immediate successors. These problems vanish completely now. See the added regression tests for the shiny new features -- we skip recursive function calls, SROA-killing instructions, and high cost complex CFG structures when dead at the callsite being analyzed. Switching to this algorithm required refactoring the inline cost interface to accept the actual threshold rather than simply returning a single cost. The resulting interface is pretty bad, and I'm planning to do lots of interface cleanup after this patch. Several other refactorings fell out of this, but I've tried to minimize them for this patch. =/ There is still more cleanup that can be done here. Please point out anything that you see in review. I've worked really hard to try to mirror at least the spirit of all of the previous heuristics in the new model. It's not clear that they are all correct any more, but I wanted to minimize the change in this single patch, it's already a bit ridiculous. One heuristic that is *not* yet mirrored is to allow inlining of functions with a dynamic alloca *if* the caller has a dynamic alloca. I will add this back, but I think the most reasonable way requires changes to the inliner itself rather than just the cost metric, and so I've deferred this for a subsequent patch. The test case is XFAIL-ed until then. As mentioned in the review mail, this seems to make Clang run about 1% to 2% faster in -O0, but makes its binary size grow by just under 4%. I've looked into the 4% growth, and it can be fixed, but requires changes to other parts of the inliner. llvm-svn: 153812
* Add computeMaskedBitsLoad back, as it was the change to instsimplify thatRafael Espindola2012-03-301-0/+26
| | | | | | caused the slowdown last time. llvm-svn: 153747
* Lowercase the tag name to match the rest of dwarf.Eric Christopher2012-03-292-3/+3
| | | | llvm-svn: 153691
* Add support for objc property decls according to the page at:Eric Christopher2012-03-292-3/+21
| | | | | | | | | | http://llvm.org/docs/SourceLevelDebugging.html#objcproperty including type and DECL. Expand the metadata needed accordingly. rdar://11144023 llvm-svn: 153639
* Handle intrinsics in GlobalsModRef. Fixes pr12351.Rafael Espindola2012-03-281-0/+6
| | | | llvm-svn: 153604
* Revert r153521 as it's causing large regressions on the nightly testers.Chad Rosier2012-03-282-41/+0
| | | | | | | | Original commit message for r153521 (aka r153423): Use the new range metadata in computeMaskedBits and add a new optimization to instruction simplify that lets us remove an and when loding a boolean value. llvm-svn: 153587
OpenPOWER on IntegriCloud