summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Use phi ranges to simplify code. No functionality change intended.Benjamin Kramer2017-12-301-17/+9
| | | | llvm-svn: 321585
* Reverting [JumpThreading] Preservation of DT and LVI across the passBrian M. Rzycki2017-12-131-14/+4
| | | | | | | Stage 2 bootstrap failed: http://lab.llvm.org:8011/builders/clang-x86_64-linux-selfhost-modules-2/builds/14434 llvm-svn: 320641
* [JumpThreading] Preservation of DT and LVI across the passBrian M. Rzycki2017-12-131-4/+14
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: See D37528 for a previous (non-deferred) version of this patch and its description. Preserves dominance in a deferred manner using a new class DeferredDominance. This reduces the performance impact of updating the DominatorTree at every edge insertion and deletion. A user may call DDT->flush() within JumpThreading for an up-to-date DT. This patch currently has one flush() at the end of runImpl() to ensure DT is preserved across the pass. LVI is also preserved to help subsequent passes such as CorrelatedValuePropagation. LVI is simpler to maintain and is done immediately (not deferred). The code to perfom the preversation was minimally altered and was simply marked as preserved for the PassManager to be informed. This extends the analysis available to JumpThreading for future enhancements. One example is loop boundary threading. Reviewers: dberlin, kuhar, sebpop Reviewed By: kuhar, sebpop Subscribers: hiraditya, llvm-commits Differential Revision: https://reviews.llvm.org/D40146 llvm-svn: 320612
* loop-rotate: eliminate duplicate debug intrinsics after splicing.Adrian Prantl2017-11-011-1/+26
| | | | | | | | | Fixes part of PR35113. This reapplies r317105 with an additional check for isa<Instruction> as found by the bots. llvm-svn: 317120
* Revert r317105 to investigate bot breakage.Adrian Prantl2017-11-011-23/+1
| | | | llvm-svn: 317110
* loop-rotate: eliminate duplicate debug intrinsics after splicing.Adrian Prantl2017-11-011-1/+23
| | | | | | Fixes part of PR35113. llvm-svn: 317105
* [Transforms] Fix some Clang-tidy modernize and Include What You Use ↵Eugene Zelenko2017-10-271-10/+21
| | | | | | warnings; other minor fixes (NFC). llvm-svn: 316724
* Rename WeakVH to WeakTrackingVH; NFCSanjoy Das2017-05-011-2/+2
| | | | | | This relands r301424. llvm-svn: 301812
* Reverts commit r301424, r301425 and r301426Sanjoy Das2017-04-261-2/+2
| | | | | | | | | | | | Commits were: "Use WeakVH instead of WeakTrackingVH in AliasSetTracker's UnkownInsts" "Add a new WeakVH value handle; NFC" "Rename WeakVH to WeakTrackingVH; NFC" The changes assumed pointers are 8 byte aligned on all architectures. llvm-svn: 301429
* Rename WeakVH to WeakTrackingVH; NFCSanjoy Das2017-04-261-2/+2
| | | | | | | | | | | | | | | | Summary: I plan to use WeakVH to mean "nulls itself out on deletion, but does not track RAUW" in a subsequent commit. Reviewers: dblaikie, davide Reviewed By: davide Subscribers: arsenm, mehdi_amini, mcrosier, mzolotukhin, jfb, llvm-commits, nhaehnle Differential Revision: https://reviews.llvm.org/D32266 llvm-svn: 301424
* [BasicBlockUtils] Check for nullptr before updating LoopInfo.Michael Kruse2017-03-061-3/+4
| | | | | | | | | | | | | | | | LoopInfo::getLoopFor returns nullptr if a BB is not in a loop and only then can the loop be updated to contain the newly created BBs. Add the missing nullptr check to SplitBlockAndInsertIfThen. Within LLVM, the only user of this function that also passes a LoopInfo to be updated is InnerLoopVectorizer::predicateInstructions(). As the method's name implies, the BB operataten on will always be within a loop, but out-of-tree users may also use it differently (here: Polly). All other uses of LoopInfo::getLoopFor in the file properly check its return value for nullptr. llvm-svn: 297016
* [BasicBlockUtils] Use getFirstNonPHIOrDbg to set debugloc for instructions ↵Taewook Oh2017-02-141-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | created in SplitBlockPredecessors Summary: When setting debugloc for instructions created in SplitBlockPredecessors, current implementation copies debugloc from the first-non-phi instruction of the original basic block. However, if the first-non-phi instruction is a call for @llvm.dbg.value, the debugloc of the instruction may point the location outside of the block itself. For the example code of ``` 1 typedef struct _node_t { 2 struct _node_t *next; 3 } node_t; 4 5 extern node_t *root; 6 7 int foo() { 8 node_t *node, *tmp; 9 int ret = 0; 10 11 node = tmp = root->next; 12 while (node != root) { 13 while (node) { 14 tmp = node; 15 node = node->next; 16 ret++; 17 } 18 } 19 20 return ret; 21 } ``` , below is the basicblock corresponding to line 12 after Reassociate expressions pass: ``` while.cond: ; preds = %while.cond2, %entry %node.0 = phi %struct._node_t* [ %1, %entry ], [ null, %while.cond2 ] %ret.0 = phi i32 [ 0, %entry ], [ %ret.1, %while.cond2 ] tail call void @llvm.dbg.value(metadata i32 %ret.0, i64 0, metadata !19, metadata !20), !dbg !21 tail call void @llvm.dbg.value(metadata %struct._node_t* %node.0, i64 0, metadata !11, metadata !20), !dbg !31 %cmp = icmp eq %struct._node_t* %node.0, %0, !dbg !33 br i1 %cmp, label %while.end5, label %while.cond2, !dbg !35 ``` As you can see, the first-non-phi instruction is a call for @llvm.dbg.value, and the debugloc is ``` !21 = !DILocation(line: 9, column: 7, scope: !6) ``` , which is a definition of 'ret' variable and outside of the scope of the basicblock itself. However, current implementation picks up this debugloc for the instructions created in SplitBlockPredecessors. This patch addresses this problem by picking up debugloc from the first-non-phi-non-dbg instruction. Reviewers: dblaikie, samsonov, eugenis Reviewed By: eugenis Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D29867 llvm-svn: 295106
* Apply clang-tidy's modernize-loop-convert to most of lib/Transforms.Benjamin Kramer2016-06-261-24/+12
| | | | | | Only minor manual fixes. No functionality change intended. llvm-svn: 273808
* improve documentation comments; NFCSanjay Patel2016-04-231-111/+3
| | | | llvm-svn: 267292
* [LV] Preserve LoopInfo when store predication is usedAdam Nemet2016-03-151-5/+10
| | | | | | | | | | | | | | | | | This was a latent bug that got exposed by the change to add LoopSimplify as a dependence to LoopLoadElimination. Since LoopInfo was corrupted after LV, LoopSimplify mis-compiled nbench in the test-suite (more details in the PR). The problem was that when we create the blocks for predicated stores we didn't add those to any loops. The original testcase for store predication provides coverage for this assuming we verify LI on the way out of LV. Fixes PR26952. llvm-svn: 263565
* [PM] Port memdep to the new pass manager.Chandler Carruth2016-03-101-2/+2
| | | | | | | | | | | | | | | | | | | | | | | This is a fairly straightforward port to the new pass manager with one exception. It removes a very questionable use of releaseMemory() in the old pass to invalidate its caches between runs on a function. I don't think this is really guaranteed to be safe. I've just used the more direct port to the new PM to address this by nuking the results object each time the pass runs. While this could cause some minor malloc traffic increase, I don't expect the compile time performance hit to be noticable, and it makes the correctness and other aspects of the pass much easier to reason about. In some cases, it may make things faster by making the sets and maps smaller with better locality. Indeed, the measurements collected by Bruno (thanks!!!) show mostly compile time improvements. There is sadly very limited testing at this point as there are only two tests of memdep, and both rely on GVN. I'll be porting GVN next and that will exercise this heavily though. Differential Revision: http://reviews.llvm.org/D17962 llvm-svn: 263082
* [SplitLandingPadPredecessors] Create a PHINode for the original landingpad ↵Chen Li2016-01-061-5/+11
| | | | | | | | | | | | | | only if it has some uses Summary: This patch adds a check in SplitLandingPadPredecessors to see if the original landingpad instruction has any uses. If not, we don't need to create a PHINode for it in the joint block since it's gonna be a dead code anyway. The motivation for this patch is that we found a bug that SplitLandingPadPredecessors created a PHINode of token type landingpad, which failed the verifier since PHINode can not be token type. However, the created PHINode will never be used in our code pattern. This patch will workaround this bug, and we might add supports in SplitLandingPadPredecessors to handle token type landingpad with uses in the future. Reviewers: reames Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D15835 llvm-svn: 256972
* TransformUtils: Remove implicit ilist iterator conversions, NFCDuncan P. N. Exon Smith2015-10-131-5/+5
| | | | | | | | | | | Continuing the work from last week to remove implicit ilist iterator conversions. First related commit was probably r249767, with some more motivation in r249925. This edition gets LLVMTransformUtils compiling without the implicit conversions. No functional change intended. llvm-svn: 250142
* Convert a bunch of loops to foreach. NFC.Pete Cooper2015-08-061-2/+2
| | | | | | | | After r244074, we now have a successors() method to iterate over all the successors of a TerminatorInst. This commit changes a bunch of eligible loops to use it. llvm-svn: 244260
* New EH representation for MSVC compatibilityDavid Majnemer2015-07-311-3/+8
| | | | | | | | | | This introduces new instructions neccessary to implement MSVC-compatible exception handling support. Most of the middle-end and none of the back-end haven't been audited or updated to take them into account. Differential Revision: http://reviews.llvm.org/D11097 llvm-svn: 243766
* [PM/AA] Remove all of the dead AliasAnalysis pointers being threadedChandler Carruth2015-07-221-14/+13
| | | | | | | | | | through APIs that are no longer necessary now that the update API has been removed. This will make changes to the AA interfaces significantly less disruptive (I hope). Either way, it seems like a really nice cleanup. llvm-svn: 242882
* [PM/AA] Remove the last of the legacy update API from AliasAnalysis asChandler Carruth2015-07-221-2/+0
| | | | | | | | | | | | | part of simplifying its interface and usage in preparation for porting to work with the new pass manager. Note that this will likely expose that we have dead arguments, members, and maybe even pass requirements for AA. I'll be cleaning those up in seperate patches. This just zaps the actual update API. Differential Revision: http://reviews.llvm.org/D11325 llvm-svn: 242881
* [PM/AA] Completely remove the AliasAnalysis::copyValue interface.Chandler Carruth2015-07-111-2/+0
| | | | | | | | | | | | | | | | | | | | | No in-tree alias analysis used this facility, and it was not called in any particularly rigorous way, so it seems unlikely to be correct. Note that one of the only stateful AA implementations in-tree, GlobalsModRef is completely broken currently (and any AA passes like it are equally broken) because Module AA passes are not effectively invalidated when a function pass that fails to update the AA stack runs. Ultimately, it doesn't seem like we know how we want to build stateful AA, and until then trying to support and maintain correctness for an untested API is essentially impossible. To that end, I'm planning to rip out all of the update API. It can return if and when we need it and know how to build it on top of the new pass manager and as part of *tested* stateful AA implementations in the tree. Differential Revision: http://reviews.llvm.org/D10889 llvm-svn: 241975
* Revert the new EH instructionsDavid Majnemer2015-07-101-3/+2
| | | | | | This reverts commits r241888-r241891, I didn't mean to commit them. llvm-svn: 241893
* New EH representation for MSVC compatibilityDavid Majnemer2015-07-101-2/+3
| | | | | | | | | | | | | | | Summary: This introduces new instructions neccessary to implement MSVC-compatible exception handling support. Most of the middle-end and none of the back-end haven't been audited or updated to take them into account. Reviewers: rnk, JosephTremoulet, reames, nlewycky, rjmccall Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D11041 llvm-svn: 241888
* Let llvm::ReplaceInstWithInst copy debug location from old to new instruction.Alexey Samsonov2015-06-231-2/+5
| | | | | | | | | | | | | | Currently some users of this function do this explicitly, and all the rest forget to do this. ThreadSanitizer was one of such users, and had missing debug locations for calls into TSan runtime handling atomic operations, eventually leading to poorly symbolized stack traces and malfunctioning suppressions. This is another change relevant to PR23837. llvm-svn: 240460
* [BasicBlockUtils] Set debug locations for instructions created in ↵Alexey Samsonov2015-06-091-2/+5
| | | | | | | | | | | | | | SplitBlockPredecessors. Test Plan: regression test suite Reviewers: eugenis, dblaikie Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D10343 llvm-svn: 239438
* Convert PHI getIncomingValue() to foreach over incoming_values(). NFC.Pete Cooper2015-05-121-2/+2
| | | | | | | | We already had a method to iterate over all the incoming values of a PHI. This just changes all eligible code to use it. Ineligible code included anything which cared about the index, or was also trying to get the i'th incoming BB. llvm-svn: 237169
* Teach SplitBlockPredecessors how to handle landingpad blocks.Philip Reames2015-01-281-5/+20
| | | | | | | | | | Patch by: Igor Laevsky <igor@azulsystems.com> "Currently SplitBlockPredecessors generates incorrect code in case if basic block we are going to split has a landingpad. Also seems like it is fairly common case among it's users to conditionally call either SplitBlockPredecessors or SplitLandingPadPredecessors. Because of this I think it is reasonable to add this condition directly into SplitBlockPredecessors." Differential Revision: http://reviews.llvm.org/D7157 llvm-svn: 227390
* [PM] Replace the Pass argument to SplitEdge with specific analyses usedChandler Carruth2015-01-191-12/+4
| | | | | | | | | | | | | | | and updated. This may appear to remove handling for things like alias analysis when splitting critical edges here, but in fact no callers of SplitEdge relied on this. Similarly, all of them wanted to preserve LCSSA if there was any update of the loop info. That makes the interface much simpler. With this, all of BasicBlockUtils.h is free of Pass arguments and prepared for the new pass manager. This is tho majority of utilities that relied on pass arguments. llvm-svn: 226459
* [PM] Remove the Pass argument from all of the critical edge splittingChandler Carruth2015-01-191-7/+14
| | | | | | | | | | | | | | | | | | | APIs and replace it and numerous booleans with an option struct. The critical edge splitting API has a really large surface of flags and so it seems worth burning a small option struct / builder. This struct can be constructed with the various preserved analyses and then flags can be flipped in a builder style. The various users are now responsible for directly passing along their analysis information. This should be enough for the critical edge splitting to work cleanly with the new pass manager as well. This API is still pretty crufty and could be cleaned up a lot, but I've focused on this change just threading an option struct rather than a pass through the API. llvm-svn: 226456
* [PM] Lift the analyses into the interface forChandler Carruth2015-01-191-10/+4
| | | | | | | | | | SplitLandingPadPredecessors and remove the Pass argument from its interface. Another step to the utilities being usable with both old and new pass managers. llvm-svn: 226426
* [PM] Pull the analyses used for another utility routine into its APIChandler Carruth2015-01-181-43/+53
| | | | | | | | | | | rather than relying on the pass object. This one is a bit annoying, but will pay off. First, supporting this one will make the next one much easier, and for utilities like LoopSimplify, this is moving them (slowly) closer to not having to pass the pass object around throughout their APIs. llvm-svn: 226396
* [PM] Sink the specific analyses preserved by SplitBlock into itsChandler Carruth2015-01-181-15/+16
| | | | | | | | | interface, removing Pass from its interface. This also makes those analyses optional so that passes which don't even preserve these (or use them) can skip the logic entirely. llvm-svn: 226394
* [PM] Replace another Pass argument with specific analyses that areChandler Carruth2015-01-181-25/+19
| | | | | | | | | optionally updated by MergeBlockIntoPredecessors. No functionality changed, just refactoring to clear the way for the new pass manager. llvm-svn: 226392
* [PM] Lift the actual analyses used into the inferface rather thanChandler Carruth2015-01-181-10/+7
| | | | | | | | | | | | accepting a Pass and querying it for analyses. This is necessary to allow the utilities to work both with the old and new pass managers, and I also think this makes the interface much more clear and helps the reader know what analyses the utility can actually handle. I plan to repeat this process iteratively to clean up all the pass utilities. llvm-svn: 226386
* [PM] Now that LoopInfo isn't in the Pass type hierarchy, it is muchChandler Carruth2015-01-181-3/+3
| | | | | | | | | | | | cleaner to derive from the generic base. Thise removes a ton of boiler plate code and somewhat strange and pointless indirections. It also remove a bunch of the previously needed friend declarations. To fully remove these, I also lifted the verify logic into the generic LoopInfoBase, which seems good anyways -- it is generic and useful logic even for the machine side. llvm-svn: 226385
* [PM] Split the LoopInfo object apart from the legacy pass, creatingChandler Carruth2015-01-171-6/+9
| | | | | | | | | | a LoopInfoWrapperPass to wire the object up to the legacy pass manager. This switches all the clients of LoopInfo over and paves the way to port LoopInfo to the new pass manager. No functionality change is intended with this iteration. llvm-svn: 226373
* Introduce llvm::SplitAllCriticalEdgesKostya Serebryany2014-11-191-0/+12
| | | | | | | | | | | | | | | | | | | | Summary: move the code from BreakCriticalEdges::runOnFunction() into a separate utility function llvm::SplitAllCriticalEdges() so that it can be used independently. No functionality change intended. Test Plan: check-llvm Reviewers: nlewycky Reviewed By: nlewycky Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D6313 llvm-svn: 222288
* Revert "[C++11] Add predecessors(BasicBlock *) / successors(BasicBlock *) ↵Duncan P. N. Exon Smith2014-07-211-1/+4
| | | | | | | | | iterator ranges." This reverts commit r213474 (and r213475), which causes a miscompile on a stage2 LTO build. I'll reply on the list in a moment. llvm-svn: 213562
* [C++11] Add predecessors(BasicBlock *) / successors(BasicBlock *) iterator ↵Manuel Jacob2014-07-201-4/+1
| | | | | | | | | | | | | | | | | | ranges. Summary: This patch introduces two new iterator ranges and updates existing code to use it. No functional change intended. Test Plan: All tests (make check-all) still pass. Reviewers: dblaikie Reviewed By: dblaikie Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D4481 llvm-svn: 213474
* Give SplitBlockAndInsertIfThen the ability to update a domtree.Peter Collingbourne2014-07-151-1/+16
| | | | llvm-svn: 213045
* Fix rampant quadratic behavior in UpdatePHINodes. The operation ofChandler Carruth2014-04-281-23/+40
| | | | | | | | | | | | | | | | | | | | | | | mapping from a basic block to an incoming value, either for removal or just lookup, is linear in the number of predecessors, and we were doing this for every entry in the 'Preds' list which is in many cases almost all of them! Unfortunately, the fixes are quite ugly. PHI nodes just don't make this operation easy. The efficient way to fix this is to have a clever 'remove_if' operation on PHI nodes that lets us do a single pass over all the incoming values of the original PHI node, extracting the ones we care about. Then we could quickly construct the new phi node from this list. This would remove the remaining underlying quadratic movement of unrelated incoming values and the need for silly backwards looping to "minimize" how often we hit the quadratic case. This is the last obvious fix for PR19499. It shaves another 20% off the compile time for me, and while UpdatePHINodes remains in the profile, most of the time is now stemming from the well known inefficiencies of LVI and jump threading. llvm-svn: 207409
* [C++] Use 'nullptr'.Craig Topper2014-04-281-1/+1
| | | | llvm-svn: 207394
* [C++] Use 'nullptr'. Transforms edition.Craig Topper2014-04-251-26/+26
| | | | llvm-svn: 207196
* Set debug info for instructions inserted in SplitBlockAndInsertIfThen.Evgeniy Stepanov2014-03-191-0/+5
| | | | llvm-svn: 204230
* [Modules] Move ValueHandle into the IR library where Value itself lives.Chandler Carruth2014-03-041-1/+1
| | | | | | | | | | | Move the test for this class into the IR unittests as well. This uncovers that ValueMap too is in the IR library. Ironically, the unittest for ValueMap is useless in the Support library (honestly, so was the ValueHandle test) and so it already lives in the IR unittests. Mmmm, tasty layering. llvm-svn: 202821
* [PM] Split DominatorTree into a concrete analysis result object whichChandler Carruth2014-01-131-12/+16
| | | | | | | | | | | | | | | | | | | | | | | can be used by both the new pass manager and the old. This removes it from any of the virtual mess of the pass interfaces and lets it derive cleanly from the DominatorTreeBase<> template. In turn, tons of boilerplate interface can be nuked and it turns into a very straightforward extension of the base DominatorTree interface. The old analysis pass is now a simple wrapper. The names and style of this split should match the split between CallGraph and CallGraphWrapperPass. All of the users of DominatorTree have been updated to match using many of the same tricks as with CallGraph. The goal is that the common type remains the resulting DominatorTree rather than the pass. This will make subsequent work toward the new pass manager significantly easier. Also in numerous places things became cleaner because I switched from re-running the pass (!!! mid way through some other passes run!!!) to directly recomputing the domtree. llvm-svn: 199104
* [cleanup] Move the Dominators.h and Verifier.h headers into the IRChandler Carruth2014-01-131-1/+1
| | | | | | | | | | | | | | | | | | directory. These passes are already defined in the IR library, and it doesn't make any sense to have the headers in Analysis. Long term, I think there is going to be a much better way to divide these matters. The dominators code should be fully separated into the abstract graph algorithm and have that put in Support where it becomes obvious that evn Clang's CFGBlock's can use it. Then the verifier can manually construct dominance information from the Support-driven interface while the Analysis library can provide a pass which both caches, reconstructs, and supports a nice update API. But those are very long term, and so I don't want to leave the really confusing structure until that day arrives. llvm-svn: 199082
* [asan] don't unpoison redzones on function exit in use-after-return mode.Kostya Serebryany2013-12-231-0/+33
| | | | | | | | | | | | | | | | | | | | | | | | Summary: Before this change the instrumented code before Ret instructions looked like: <Unpoison Frame Redzones> if (Frame != OriginalFrame) // I.e. Frame is fake <Poison Complete Frame> Now the instrumented code looks like: if (Frame != OriginalFrame) // I.e. Frame is fake <Poison Complete Frame> else <Unpoison Frame Redzones> Reviewers: eugenis Reviewed By: eugenis CC: llvm-commits Differential Revision: http://llvm-reviews.chandlerc.com/D2458 llvm-svn: 197907
OpenPOWER on IntegriCloud