aboutsummaryrefslogtreecommitdiff
path: root/lib/Analysis
AgeCommit message (Collapse)Author
2008-10-22Merge from mainline.Tanya Lattner
Disallow the construction of SCEVs with could-not-compute operands. Catch CNCs returned by BinomialCoefficient and don't try to operate with them. This replaces the previous fix for PR2857. git-svn-id: https://llvm.org/svn/llvm-project/llvm/branches/release_24@57958 91177308-0d34-0410-b5e6-96231b3b80d8
2008-10-04Allow the construction of SCEVs with SCEVCouldNotCompute operands, byNick Lewycky
implementing folding. Fixes PR2857. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@57049 91177308-0d34-0410-b5e6-96231b3b80d8
2008-10-03Teach internalize to preserve the callgraph.Duncan Sands
Why? Because it was there! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@56996 91177308-0d34-0410-b5e6-96231b3b80d8
2008-10-01Factorize code: remove variants of "strip offDuncan Sands
pointer bitcasts and GEP's", and centralize the logic in Value::getUnderlyingObject. The difference with stripPointerCasts is that stripPointerCasts only strips GEPs if all indices are zero, while getUnderlyingObject strips GEPs no matter what the indices are. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@56922 91177308-0d34-0410-b5e6-96231b3b80d8
2008-09-23s/ParameterAttributes/Attributes/gDevang Patel
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@56513 91177308-0d34-0410-b5e6-96231b3b80d8
2008-09-23Rationalize the names of passes that print information:Duncan Sands
-callgraph => print-callgraph -callscc => print-callgraph-sccs -cfgscc => print-cfg-sccs -externalfnconstants => print-externalfnconstants -print => print-function -print-alias-sets (no change) -print-callgraph => dot-callgraph -print-cfg => dot-cfg -print-cfg-only => dot-cfg-only -print-dom-info (no change) -printm => print-module -printusedtypes => print-used-types git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@56487 91177308-0d34-0410-b5e6-96231b3b80d8
2008-09-22Initial support for the CMake build system.Oscar Fuentes
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@56419 91177308-0d34-0410-b5e6-96231b3b80d8
2008-09-16Finally re-apply r46959. This is made feasible by the combinationDan Gohman
of r56230, r56232, and r56246. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@56247 91177308-0d34-0410-b5e6-96231b3b80d8
2008-09-16Improve instcombine's handling of integer min and max in two ways:Dan Gohman
- Recognize expressions like "x > -1 ? x : 0" as min/max and turn them into expressions like "x < 0 ? 0 : x", which is easily recognizable as a min/max operation. - Refrain from folding expression like "y/2 < 1" to "y < 2" when the comparison is being used as part of a min or max idiom, like "y/2 < 1 ? 1 : y/2". In that case, the division has another use, so folding doesn't eliminate it, and obfuscates the min/max, making it harder to recognize as a min/max operation. These benefit ScalarEvolution, CodeGen, and anything else that wants to recognize integer min and max. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@56246 91177308-0d34-0410-b5e6-96231b3b80d8
2008-09-15Teach ScalarEvolution to consider loop preheaders in the search forDan Gohman
an if statement that guards a loop, to allow indvars to avoid smax operations in more situations. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@56232 91177308-0d34-0410-b5e6-96231b3b80d8
2008-09-14Fix WriteAsOperand to not emit a leading space character. AdjustDan Gohman
its callers to emit a space character before calling it when a space is needed. This fixes several spurious whitespace issues in ScalarEvolution's debug dumps. See the test changes for examples. This also fixes odd space-after-tab indentation in the output for switch statements, and changes calls from being printed like this: call void @foo( i32 %x ) to this: call void @foo(i32 %x) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@56196 91177308-0d34-0410-b5e6-96231b3b80d8
2008-09-13Fix PR2792: treat volatile loads as writing memory somewhere.Duncan Sands
Treat stores as reading memory, just to play safe. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@56188 91177308-0d34-0410-b5e6-96231b3b80d8
2008-09-12Rather than marking all internal globals "Ref"Duncan Sands
when a readonly declaration is called, set a flag. This is faster and uses less memory. In theory it is less accurate, because before only those internal globals that were read by someone were being marked "Ref", but now all are. But in practice, thanks to other passes, all internal globals of the kind considered here will be both read and stored to: those only read will have been turned into constants, and those only stored to will have been deleted. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@56143 91177308-0d34-0410-b5e6-96231b3b80d8
2008-09-11Fix comment typo.Duncan Sands
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@56116 91177308-0d34-0410-b5e6-96231b3b80d8
2008-09-11Intrinsics don't touch internal global variablesDuncan Sands
(unless passed one via a parameter), even if they are IntrWriteMem. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@56115 91177308-0d34-0410-b5e6-96231b3b80d8
2008-09-11Intrinsics don't read these kinds of globalDuncan Sands
variables. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@56105 91177308-0d34-0410-b5e6-96231b3b80d8
2008-09-09Simplify this some more. No functionality change.Duncan Sands
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@56003 91177308-0d34-0410-b5e6-96231b3b80d8
2008-09-09Optimization suggested by Matthijs Kooijman.Duncan Sands
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@55988 91177308-0d34-0410-b5e6-96231b3b80d8
2008-09-09Correct callgraph construction. It has two problems:Duncan Sands
(1) code left over from the days of ConstantPointerRef: if a use of a function is a GlobalValue then that is not considered a reason to add an edge from the external node, even though the use may be as an initializer for an externally visible global! There might be some point to this behaviour when the use is by an alias (though the code predated aliases by some centuries), but I think PR2782 is a better way of handling that. (2) If function F calls function G, and also G is a parameter to the call, then an F->G edge is not added to the callgraph. While this doesn't seem to matter much, adding such an edge makes the callgraph more regular. In addition, the new code should be faster as well as simpler. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@55987 91177308-0d34-0410-b5e6-96231b3b80d8
2008-09-08Didn't mean to commit this change to how theDuncan Sands
callgraph is printed. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@55912 91177308-0d34-0410-b5e6-96231b3b80d8
2008-09-08Reapply 55859. This doesn't change anything asDuncan Sands
long as the callgraph is correct. It checks for wrong callgraphs more strictly. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@55894 91177308-0d34-0410-b5e6-96231b3b80d8
2008-09-06When PruneEH turned an invoke into an ordinaryDuncan Sands
call (thus changing the call site) it didn't inform the callgraph about this. But the call site does matter - as shown by the testcase, the callgraph become invalid after the inliner ran (with an edge between two functions simply missing), resulting in wrong deductions by GlobalsModRef. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@55872 91177308-0d34-0410-b5e6-96231b3b80d8
2008-09-05Revert r55859. This is breaking the build in the abscence of its companion ↵Owen Anderson
commit. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@55865 91177308-0d34-0410-b5e6-96231b3b80d8
2008-09-05Delete the removeCallEdgeTo callgraph method,Duncan Sands
because it does not maintain a correct list of callsites. I discovered (see following commit) that the inliner will create a wrong callgraph if it is fed a callgraph with correct edges but incorrect callsites. These were created by Prune-EH, and while it wasn't done via removeCallEdgeTo, it could have been done via removeCallEdgeTo, which is an accident waiting to happen. Use removeCallEdgeFor instead. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@55859 91177308-0d34-0410-b5e6-96231b3b80d8
2008-09-04Neaten this up a bit. No functionality change.Duncan Sands
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@55789 91177308-0d34-0410-b5e6-96231b3b80d8
2008-09-04Tidy up several unbeseeming casts from pointer to intptr_t.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@55779 91177308-0d34-0410-b5e6-96231b3b80d8
2008-09-03If a SCC has a node without a function, then the SCCDuncan Sands
analysis would bail out without removing function records for other members of the SCC (which may exist if those functions read or wrote global variables). Since these are initialized to "readnone", this resulted in incorrect alias analysis results. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@55714 91177308-0d34-0410-b5e6-96231b3b80d8
2008-09-03Fix maxo bado thinko.Duncan Sands
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@55700 91177308-0d34-0410-b5e6-96231b3b80d8
2008-09-03Since onlyReadsMemory returns true if in factDuncan Sands
doesNotAccessMemory, check doesNotAccessMemory first, since otherwise functions may be marked readonly rather than readnone. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@55697 91177308-0d34-0410-b5e6-96231b3b80d8
2008-09-03Cleanup GlobalsModRef a bit. When analysing theDuncan Sands
callgraph, when one member of a SCC calls another then the analysis would drop to mod-ref because there is (usually) no function info for the callee yet; fix this. Teach the analysis about function attributes, in particular the readonly attribute (which requires being careful about globals). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@55696 91177308-0d34-0410-b5e6-96231b3b80d8
2008-08-28rename destroy -> releaseMemory to properly hook into passmgr.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@55508 91177308-0d34-0410-b5e6-96231b3b80d8
2008-08-28Clear the intervals list in "destroy", patch by Chris Lattner
Prakash Prabhu! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@55458 91177308-0d34-0410-b5e6-96231b3b80d8
2008-08-23Switch the asmprinter (.ll) and all the stuff it requires over toChris Lattner
use raw_ostream instead of std::ostream. Among other goodness, this speeds up llvm-dis of kc++ with a release build from 0.85s to 0.49s (88% faster). Other interesting changes: 1) This makes Value::print be non-virtual. 2) AP[S]Int and ConstantRange can no longer print to ostream directly, use raw_ostream instead. 3) This fixes a bug in raw_os_ostream where it didn't flush itself when destroyed. 4) This adds a new SDNode::print method, instead of only allowing "dump". A lot of APIs have both std::ostream and raw_ostream versions, it would be useful to go through and systematically anihilate the std::ostream versions. This passes dejagnu, but there may be minor fallout, plz let me know if so and I'll fix it. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@55263 91177308-0d34-0410-b5e6-96231b3b80d8
2008-08-21Temporarily reverting r55137. This was causing the bootstrap to go into anBill Wendling
infinite loop. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@55149 91177308-0d34-0410-b5e6-96231b3b80d8
2008-08-21Fix ComputeMaskedBits to handle phis correctly. We need to take theDavid Greene
minimum of the known zeros. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@55137 91177308-0d34-0410-b5e6-96231b3b80d8
2008-08-19Don't use the result of WriteAsOperand or WriteTypeSymbolic.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@54977 91177308-0d34-0410-b5e6-96231b3b80d8
2008-08-15Remove GCSE, ValueNumbering, and LoadValueNumbering. These have been ↵Owen Anderson
deprecated for almost a year; it's finally time for them to go away. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@54822 91177308-0d34-0410-b5e6-96231b3b80d8
2008-08-13Fix a bogus srem rule - a negative value srem'd by a power-of-2Dan Gohman
can have a non-negative result; for example, -16%16 is 0. Also, clarify the related comments. This fixes PR2670. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@54767 91177308-0d34-0410-b5e6-96231b3b80d8
2008-08-13Teach constant folding that an inttoptr of aDuncan Sands
ptrtoint can be turned into a bitcast if the integer is at least as wide as a pointer. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@54752 91177308-0d34-0410-b5e6-96231b3b80d8
2008-08-12Extend ScalarEvolution's executesAtLeastOnce logic to be able toDan Gohman
continue past the first conditional branch when looking for a relevant test. This helps it avoid using MAX expressions in loop trip counts in more cases. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@54697 91177308-0d34-0410-b5e6-96231b3b80d8
2008-08-09"This patch adds a virtual call to AbstractLatticeFunction to derive a Chris Lattner
type lattice value for an Argument*, giving clients the opportunity to use something other than Top for it if they choose to." Patch by John McCall! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@54589 91177308-0d34-0410-b5e6-96231b3b80d8
2008-08-08Canonicalize nested AddRecs in by nesting them in order of loop depth.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@54545 91177308-0d34-0410-b5e6-96231b3b80d8
2008-08-08Don't call getAnalysisUsage unless -debug-pass is enabled. This speedsChris Lattner
up the passmgr by avoiding useless work. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@54528 91177308-0d34-0410-b5e6-96231b3b80d8
2008-08-04PR2621: Improvements to the SCEV AddRec binomial expansion. This Eli Friedman
version uses a new algorithm for evaluating the binomial coefficients which is significantly more efficient for AddRecs of more than 2 terms (see the comments in the code for details on how the algorithm works). It also fixes some bugs: it removes the arbitrary length restriction for AddRecs, it fixes the silent generation of incorrect code for AddRecs which require a wide calculation width, and it fixes an issue where we were incorrectly truncating the iteration count too far when evaluating an AddRec expression narrower than the induction variable. There are still a few related issues I know of: I think there's still an issue with the SCEVExpander expansion of AddRec in terms of the width of the induction variable used. The hack to avoid generating too-wide integers shouldn't be necessary; instead, the callers should be considering the cost of the expansion before expanding it (in addition to not expanding too-wide integers, we might not want to expand expressions that are really expensive, especially when optimizing for size; calculating an length-17 32-bit AddRec currently generates about 250 instructions of straight-line code on X86). Also, for long 32-bit AddRecs on X86, CodeGen really sucks at scheduling the code. I'm planning on filing follow-up PRs for these issues. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@54332 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-30Another SCEV issue from PR2607; essentially the same issue, but this Eli Friedman
time applying to the implicit comparison in smin expressions. The correct way to transform an inequality into the opposite inequality, either signed or unsigned, is with a not expression. I looked through the SCEV code, and I don't think there are any more occurrences of this issue. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@54194 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-30Fix for PR2607: SCEV miscomputing the loop count for loops with an Eli Friedman
SGT exit condition. Essentially, the correct way to flip an inequality in 2's complement is the not operator, not the negation operator. That said, the difference only affects cases involving INT_MIN. Also, enhance the pre-test search logic to be a bit smarter about inequalities flipped with a not operator, so it can eliminate the smax from the iteration count for simple loops. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@54184 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-28Fix a subtle bug when removing instructions from memdep. In very specific Owen Anderson
circumstances we could end up remapping a dependee to the same instruction that we're trying to remove. Handle this properly by just falling back to a conservative solution. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@54132 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-25Fix minor issues with VICmp/VFCmp constant expressionsNate Begeman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@54030 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-21Revert r53812 -- premature. LegalizeTypes isn't actually on yet!Nick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53816 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-21Switch on the use of arbitrary precision integers in scalar evolution. This willNick Lewycky
bail after 256-bits to avoid producing code that the backends can't handle. Previously, we capped it at 64-bits, preferring to miscompile in those cases. This change also reverts much of r52248 because the invariants the code was expecting are now being met. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53812 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2025-09-10 02:07:34 +0000