summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/JumpThreading.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Disable most IR-level transform passes on functions marked 'optnone'.Paul Robinson2014-02-061-0/+3
| | | | | | | | | Ideally only those transform passes that run at -O0 remain enabled, in reality we get as close as we reasonably can. Passes are responsible for disabling themselves, it's not the job of the pass manager to do it for them. llvm-svn: 200892
* Don't eliminate a partially redundant load if it's in a landing pad.Bill Wendling2013-10-211-1/+6
| | | | | | | | | | | | A landing pad can be jumped to only by the unwind edge of an invoke instruction. If we eliminate a partially redundant load in a landing pad, it will create a basic block that violates this constraint. It then leads to other problems down the line if it tries to merge that basic block with the landing pad. Avoid this by not eliminating the load in a landing pad. PR17621 llvm-svn: 193064
* JumpThreading: Turn a select instruction into branching if it allows to ↵Benjamin Kramer2013-08-071-0/+83
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | thread one half of the select. This is a common pattern coming out of simplifycfg generating gross code. a: ; preds = %entry %sel = select i1 %cmp1, double %add, double 0.000000e+00 br label %b b: %cond5 = phi double [ %sel, %a ], [ %sub, %entry ] %cmp6 = fcmp oeq double %cond5, 0.000000e+00 br i1 %cmp6, label %if.then, label %if.end becomes a: br i1 %cmp1, label %b, label %if.then b: %cond5 = phi double [ %sub, %entry ], [ %add, %a ] %cmp6 = fcmp oeq double %cond5, 0.000000e+00 br i1 %cmp6, label %if.then, label %if.end Skipping block b completely if possible. llvm-svn: 187880
* Reimplement isPotentiallyReachable to make nocapture deduction much stronger.Nick Lewycky2013-07-271-2/+1
| | | | | | | | | | Adds unit tests for it too. Split BasicBlockUtils into an analysis-half and a transforms-half, and put the analysis bits into a new Analysis/CFG.{h,cpp}. Promote isPotentiallyReachable into llvm::isPotentiallyReachable and move it into Analysis/CFG. llvm-svn: 187283
* Move all of the header files which are involved in modelling the LLVM IRChandler Carruth2013-01-021-3/+3
| | | | | | | | | | | | | | | | | | | | | into their new header subdirectory: include/llvm/IR. This matches the directory structure of lib, and begins to correct a long standing point of file layout clutter in LLVM. There are still more header files to move here, but I wanted to handle them in separate commits to make tracking what files make sense at each layer easier. The only really questionable files here are the target intrinsic tablegen files. But that's a battle I'd rather not fight today. I've updated both CMake and Makefile build systems (I think, and my tests think, but I may have missed something). I've also re-sorted the includes throughout the project. I'll be committing updates to Clang, DragonEgg, and Polly momentarily. llvm-svn: 171366
* Add a new attribute, 'noduplicate'. If a function contains a noduplicate ↵James Molloy2012-12-201-1/+5
| | | | | | | | call, the call cannot be duplicated - Jump threading, loop unrolling, loop unswitching, and loop rotation are inhibited if they would duplicate the call. Similarly inlining of the function is inhibited, if that would duplicate the call (in particular inlining is still allowed when there is only one callsite and the function has internal linkage). llvm-svn: 170704
* Teach the jump threading optimization to stop scanning the basic block when ↵Nadav Rotem2012-12-031-5/+10
| | | | | | calculating the cost after passing the threshold. llvm-svn: 169135
* Use the new script to sort the includes of every file under lib.Chandler Carruth2012-12-031-13/+13
| | | | | | | | | | | | | | | | | Sooooo many of these had incorrect or strange main module includes. I have manually inspected all of these, and fixed the main module include to be the nearest plausible thing I could find. If you own or care about any of these source files, I encourage you to take some time and check that these edits were sensible. I can't have broken anything (I strictly added headers, and reordered them, never removed), but they may not be the headers you'd really like to identify as containing the API being implemented. Many forward declarations and missing includes were added to a header files to allow them to parse cleanly when included first. The main module rule does in fact have its merits. =] llvm-svn: 169131
* Move TargetData to DataLayout.Micah Villmow2012-10-081-3/+3
| | | | llvm-svn: 165402
* Make MemoryBuiltins aware of TargetLibraryInfo.Benjamin Kramer2012-08-291-1/+1
| | | | | | | | | | | | | | | | This disables malloc-specific optimization when -fno-builtin (or -ffreestanding) is specified. This has been a problem for a long time but became more severe with the recent memory builtin improvements. Since the memory builtin functions are used everywhere, this required passing TLI in many places. This means that functions that now have an optional TLI argument, like RecursivelyDeleteTriviallyDeadFunctions, won't remove dead mallocs anymore if the TLI argument is missing. I've updated most passes to do the right thing. Fixes PR13694 and probably others. llvm-svn: 162841
* Clean whitespaces.Nadav Rotem2012-07-241-3/+3
| | | | llvm-svn: 160668
* Fix assertion in jump threading (PR13405).Richard Osborne2012-07-201-0/+2
| | | | | | | | GetBestDestForJumpOnUndef() assumes there is at least 1 successor, which isn't true if the block ends in an indirect branch with no successors. Fix this by bailing out earlier in this case. llvm-svn: 160546
* enhance jump threading to preserve TBAA information when PRE'ing loads,Chris Lattner2012-03-131-1/+12
| | | | | | | fixing rdar://11039258, an issue that came up when inspecting clang's bootstrapped codegen. llvm-svn: 152635
* Taken into account Duncan's comments for r149481 dated by 2nd Feb 2012:Stepan Dyatkovskiy2012-03-081-2/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20120130/136146.html Implemented CaseIterator and it solves almost all described issues: we don't need to mix operand/case/successor indexing anymore. Base iterator class is implemented as a template since it may be initialized either from "const SwitchInst*" or from "SwitchInst*". ConstCaseIt is just a read-only iterator. CaseIt is read-write iterator; it allows to change case successor and case value. Usage of iterator allows totally remove resolveXXXX methods. All indexing convertions done automatically inside the iterator's getters. Main way of iterator usage looks like this: SwitchInst *SI = ... // intialize it somehow for (SwitchInst::CaseIt i = SI->caseBegin(), e = SI->caseEnd(); i != e; ++i) { BasicBlock *BB = i.getCaseSuccessor(); ConstantInt *V = i.getCaseValue(); // Do something. } If you want to convert case number to TerminatorInst successor index, just use getSuccessorIndex iterator's method. If you want initialize iterator from TerminatorInst successor index, use CaseIt::fromSuccessorIndex(...) method. There are also related changes in llvm-clients: klee and clang. llvm-svn: 152297
* SwitchInst refactoring.Stepan Dyatkovskiy2012-02-011-3/+4
| | | | | | | | | | | | | | | | | The purpose of refactoring is to hide operand roles from SwitchInst user (programmer). If you want to play with operands directly, probably you will need lower level methods than SwitchInst ones (TerminatorInst or may be User). After this patch we can reorganize SwitchInst operands and successors as we want. What was done: 1. Changed semantics of index inside the getCaseValue method: getCaseValue(0) means "get first case", not a condition. Use getCondition() if you want to resolve the condition. I propose don't mix SwitchInst case indexing with low level indexing (TI successors indexing, User's operands indexing), since it may be dangerous. 2. By the same reason findCaseValue(ConstantInt*) returns actual number of case value. 0 means first case, not default. If there is no case with given value, ErrorIndex will returned. 3. Added getCaseSuccessor method. I propose to avoid usage of TerminatorInst::getSuccessor if you want to resolve case successor BB. Use getCaseSuccessor instead, since internal SwitchInst organization of operands/successors is hidden and may be changed in any moment. 4. Added resolveSuccessorIndex and resolveCaseIndex. The main purpose of these methods is to see how case successors are really mapped in TerminatorInst. 4.1 "resolveSuccessorIndex" was created if you need to level down from SwitchInst to TerminatorInst. It returns TerminatorInst's successor index for given case successor. 4.2 "resolveCaseIndex" converts low level successors index to case index that curresponds to the given successor. Note: There are also related compatability fix patches for dragonegg, klee, llvm-gcc-4.0, llvm-gcc-4.2, safecode, clang. llvm-svn: 149481
* SplitBlockPredecessors uses ArrayRef instead of Data and Size.Jakub Staszak2011-12-091-6/+3
| | | | llvm-svn: 146277
* Fix a few more places where TargetData/TargetLibraryInfo is not being passed.Chad Rosier2011-12-021-1/+6
| | | | | | Add FIXMEs to places that are non-trivial to fix. llvm-svn: 145661
* Change a bunch of isVolatile() checks to check for atomic load/store as well.Eli Friedman2011-09-121-2/+2
| | | | | | | | No tests; these changes aren't really interesting in the sense that the logic is the same for volatile and atomic. I believe this completes all of the changes necessary for the optimizer to handle loads and stores correctly. I'm going to try and come up with some additional testing, though. llvm-svn: 139533
* Calculate GetBestDestForJumpOnUndef correctly.Jakub Staszak2011-06-271-1/+3
| | | | llvm-svn: 133946
* Add a parameter to ConstantFoldTerminator() that callers can use to ask it ↵Frits van Bommel2011-05-221-1/+1
| | | | | | | | to also clean up the condition of any conditional terminator it folds to be unconditional, if that turns the condition into dead code. This just means it calls RecursivelyDeleteTriviallyDeadInstructions() in strategic spots. It defaults to the old behavior. I also changed -simplifycfg, -jump-threading and -codegenprepare to use this to produce slightly better code without any extra cleanup passes (AFAICT this was the only place in -simplifycfg where now-dead conditions of replaced terminators weren't being cleaned up). The only other user of this function is -sccp, but I didn't read that thoroughly enough to figure out whether it might be holding pointers to instructions that could be deleted by this. llvm-svn: 131855
* Preserve line number information while threading jumps.Devang Patel2011-05-041-2/+5
| | | | llvm-svn: 130880
* Fix an infinite alternation in JumpThreading where two transforms would ↵Owen Anderson2011-04-141-3/+15
| | | | | | | | | | repeatedly undo each other. The solution is to perform more aggressive constant folding to make one of the edges just folded away rather than trying to thread it. Fixes <rdar://problem/9284786>. Discovered with CSmith. llvm-svn: 129538
* Remove PHINode::reserveOperandSpace(). Instead, add a parameter toJay Foad2011-03-301-2/+2
| | | | | | PHINode::Create() giving the (known or expected) number of operands. llvm-svn: 128537
* (Almost) always call reserveOperandSpace() on newly created PHINodes.Jay Foad2011-03-301-2/+3
| | | | llvm-svn: 128535
* prevent jump threading from merging blocks when their address isChris Lattner2011-02-181-1/+11
| | | | | | | | | | | | | | | | | taken (and used!). This prevents merging the blocks (invalidating the block addresses) in a case like this: #define _THIS_IP_ ({ __label__ __here; __here: (unsigned long)&&__here; }) void foo() { printf("%p\n", _THIS_IP_); printf("%p\n", _THIS_IP_); printf("%p\n", _THIS_IP_); } which fixes PR4151. llvm-svn: 125829
* Fix a bug in the loop in JumpThreading::ProcessThreadableEdges() where it ↵Frits van Bommel2010-12-161-2/+2
| | | | | | | | could falsely produce a MultipleDestSentinel value if the first predecessor ended with an 'indirectbr'. If that happened, it caused an unnecessary FindMostPopularDest() call. This wasn't a correctness problem, but it broke the fast path for single-predecessor blocks. llvm-svn: 121966
* Teach jump threading to "look through" a select when the branch direction of ↵Frits van Bommel2010-12-151-0/+34
| | | | | | | | a terminator depends on it. When it sees a promising select it now tries to figure out whether the condition of the select is known in any of the predecessors and if so it maps the operands appropriately. llvm-svn: 121859
* simplify code and reduce indentationChris Lattner2010-12-131-32/+30
| | | | llvm-svn: 121670
* Remove some dead code from the jump threading pass.Frits van Bommel2010-12-071-141/+0
| | | | | | The last uses of these functions were removed in r113852 when LazyValueInfo was permanently enabled and removed the need for them. llvm-svn: 121133
* Implement jump threading of 'indirectbr' by keeping track of whether we're ↵Frits van Bommel2010-12-061-46/+80
| | | | | | looking for ConstantInt*s or BlockAddress*s. llvm-svn: 121066
* Refactor jump threading.Frits van Bommel2010-12-051-69/+73
| | | | | | | Should have no functional change other than the order of two transformations that are mutually-exclusive and the exact formatting of debug output. Internally, it now stores the ConstantInt*s as Constant*s, and actual undef values instead of nulls. llvm-svn: 120946
* Remove trailing whitespace.Frits van Bommel2010-12-051-208/+208
| | | | llvm-svn: 120945
* Get rid of static constructors for pass registration. Instead, every pass ↵Owen Anderson2010-10-191-1/+3
| | | | | | | | | | | | | | | | | exposes an initializeMyPassFunction(), which must be called in the pass's constructor. This function uses static dependency declarations to recursively initialize the pass's dependencies. Clients that only create passes through the createFooPass() APIs will require no changes. Clients that want to use the CommandLine options for passes will need to manually call the appropriate initialization functions in PassInitialization.h before parsing commandline arguments. I have tested this with all standard configurations of clang and llvm-gcc on Darwin. It is possible that there are problems with the static dependencies that will only be visible with non-standard options. If you encounter any crash in pass registration/creation, please send the testcase to me directly. llvm-svn: 116820
* Begin adding static dependence information to passes, which will allow us toOwen Anderson2010-10-121-1/+4
| | | | | | | | | perform initialization without static constructors AND without explicit initialization by the client. For the moment, passes are required to initialize both their (potential) dependencies and any passes they preserve. I hope to be able to relax the latter requirement in the future. llvm-svn: 116334
* Now with fewer extraneous semicolons!Owen Anderson2010-10-071-1/+1
| | | | llvm-svn: 115996
* Fix PR8247: JumpThreading can cause a block to become unreachable while ↵Owen Anderson2010-09-291-4/+4
| | | | | | | | | | still having predecessor, if it is part of a self-loop. Because of this, we cannot use the Simplify* APIs, as they can assert-fail on unreachable code. Since it's not easy to determine if a given threading will cause a block to become unreachable, simply defer simplifying simplification to later InstCombine and/or DCE passes. llvm-svn: 115082
* Remove the option to disable LazyValueInfo in JumpThreading, as it is nowOwen Anderson2010-09-141-110/+37
| | | | | | on by default and has received significant testing. llvm-svn: 113852
* Change lower atomic pass to use IntrinsicInst to simplify it a bit.Chris Lattner2010-09-051-4/+3
| | | | llvm-svn: 113114
* eliminate some non-obvious casts. UndefValue isa Constant.Chris Lattner2010-09-051-4/+4
| | | | llvm-svn: 113113
* Reapply commit 112699, speculatively reverted by echristo, sinceDuncan Sands2010-09-021-2/+2
| | | | | | | | | I'm sure it is harmless. Original commit message: If PrototypeValue is erased in the middle of using the SSAUpdator then the SSAUpdator may access freed memory. Instead, simply pass in the type and name explicitly, which is all that was used anyway. llvm-svn: 112810
* JumpThreading keeps LazyValueInfo up to date, so we don't need to rerun itOwen Anderson2010-09-011-1/+3
| | | | | | if we schedule another LVI-using pass afterwards. llvm-svn: 112722
* Speculatively revert 112699 and 112702, they seem to be causingEric Christopher2010-09-011-2/+2
| | | | | | self host errors on clang-x86-64. llvm-svn: 112719
* If PrototypeValue is erased in the middle of using the SSAUpdatorDuncan Sands2010-09-011-2/+2
| | | | | | | then the SSAUpdator may access freed memory. Instead, simply pass in the type and name explicitly, which is all that was used anyway. llvm-svn: 112699
* More cleanups of my JumpThreading transforms, including extracting some ↵Owen Anderson2010-08-311-37/+26
| | | | | | duplicated code into a helper function. llvm-svn: 112634
* Add an RAII helper to make cleanup of the RecursionSet more fool-proof.Owen Anderson2010-08-311-18/+24
| | | | llvm-svn: 112628
* Refactor my fix for PR5652 to terminate the predecessor lookups after the ↵Owen Anderson2010-08-311-25/+24
| | | | | | first failure. llvm-svn: 112620
* More Chris-inspired JumpThreading fixes: use ConstantExpr to correctly ↵Owen Anderson2010-08-311-26/+64
| | | | | | | | | constant-fold undef, and be more careful with its return value. This actually exposed an infinite recursion bug in ComputeValueKnownInPredecessors which theoretically already existed (in JumpThreading's handling of and/or of i1's), but never manifested before. This patch adds a tracking set to prevent this case. llvm-svn: 112589
* Re-apply r112539, being more careful to respect the return values of the ↵Owen Anderson2010-08-301-22/+25
| | | | | | | | constant folding methods. Additionally, use the ConstantExpr::get*() methods to simplify some constant folding. llvm-svn: 112550
* Revert r112539. It accidentally introduced a miscompilation.Owen Anderson2010-08-301-20/+16
| | | | llvm-svn: 112543
* Fixes and cleanups pointed out by Chris. In general, be careful to handle 0 ↵Owen Anderson2010-08-301-16/+20
| | | | | | | | results from ComputeValueKnownInPredecessors (indicating undef), and re-use existing constant folding APIs. llvm-svn: 112539
OpenPOWER on IntegriCloud