aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/IR/BasicBlock.cpp
AgeCommit message (Collapse)AuthorFilesLines
2020-02-21[IR] Update BasicBlock::validateInstrOrdering comments, NFCReid Kleckner1-1/+1
Pointed out by Jay Foad.
2020-02-18[IR] Lazily number instructions for local dominance queriesReid Kleckner1-0/+32
Essentially, fold OrderedBasicBlock into BasicBlock, and make it auto-invalidate the instruction ordering when new instructions are added. Notably, we don't need to invalidate it when removing instructions, which is helpful when a pass mostly delete dead instructions rather than transforming them. The downside is that Instruction grows from 56 bytes to 64 bytes. The resulting LLVM code is substantially simpler and automatically handles invalidation, which makes me think that this is the right speed and size tradeoff. The important change is in SymbolTableTraitsImpl.h, where the numbering is invalidated. Everything else should be straightforward. We probably want to implement a fancier re-numbering scheme so that local updates don't invalidate the ordering, but I plan for that to be future work, maybe for someone else. Reviewed By: lattner, vsk, fhahn, dexonsmith Differential Revision: https://reviews.llvm.org/D51664
2020-01-17[BasicBlock] fix looping in getPostdominatingDeoptimizeCallFedor Sergeev1-2/+7
Blindly following unique-successors chain appeared to be a bad idea. In a degenerate case when block jumps to itself that goes into endless loop. Discovered this problem when playing with additional changes, managed to reproduce it on existing LoopPredication code. Fix by checking a "visited" set while iterating through unique successors. Reviewed By: skatkov Tags: #llvm Differential Revision: https://reviews.llvm.org/D72908
2020-01-16[BasicBlock] add helper getPostdominatingDeoptimizeCallFedor Sergeev1-0/+7
It appears to be rather useful when analyzing Loops with multiple deoptimizing exits, perhaps merged ones. For now it is used in LoopPredication, will be adding more uses in other loop passes. Reviewers: asbirlea, fhahn, skatkov, spatel, reames Reviewed By: reames Tags: #llvm Differential Revision: https://reviews.llvm.org/D72754
2019-09-20[FastISel] Fix insertion of unconditional branches during FastISelDavid Tellenbach1-0/+7
The insertion of an unconditional branch during FastISel can differ depending on building with or without debug information. This happens because FastISel::fastEmitBranch emits an unconditional branch depending on the size of the current basic block without distinguishing between debug and non-debug instructions. This patch fixes this issue by ignoring debug instructions when getting the size of the basic block. Reviewers: aprantl Reviewed By: aprantl Subscribers: ormris, aprantl, hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D67703 llvm-svn: 372389
2019-05-05[NFC] BasicBlock: generalize replaceSuccessorsPhiUsesWith(), take Old bbRoman Lebedev1-7/+10
Thus it does not assume that the old basic block is the basic block for which we are looking at successors. Not reviewed, but seems rather trivial, in line with the rest of previous few patches. llvm-svn: 359997
2019-05-05[NFC] BasicBlock: refactor changePhiUses() out of replacePhiUsesWith(), use itRoman Lebedev1-17/+17
Summary: It is a common thing to loop over every `PHINode` in some `BasicBlock` and change old `BasicBlock` incoming block to a new `BasicBlock` incoming block. `replaceSuccessorsPhiUsesWith()` already had code to do that, it just wasn't a function. So outline it into a new function, and use it. Reviewers: chandlerc, craig.topper, spatel, danielcdh Reviewed By: craig.topper Subscribers: llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D61013 llvm-svn: 359996
2019-05-05[NFC] PHINode: introduce replaceIncomingBlockWith() function, use itRoman Lebedev1-10/+3
Summary: There is `PHINode::getBasicBlockIndex()`, `PHINode::setIncomingBlock()` and `PHINode::getNumOperands()`, but no function to replace every specified `BasicBlock*` predecessor with some other specified `BasicBlock*`. Clearly, there are a lot of places that could use that functionality. Reviewers: chandlerc, craig.topper, spatel, danielcdh Reviewed By: craig.topper Subscribers: llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D61011 llvm-svn: 359995
2019-02-14Revert "[INLINER] allow inlining of address taken blocks"Nick Desaulniers1-8/+0
This reverts commit 19e95fe61182945b7b68ad15348f144fb996633f. llvm-svn: 354082
2019-02-14[INLINER] allow inlining of address taken blocksNick Desaulniers1-0/+8
as long as their uses does not contain calls to functions that capture the argument (potentially allowing the blockaddress to "escape" the lifetime of the caller). TODO: - add more tests - fix crash in llvm::updateCGAndAnalysisManagerForFunctionPass when invoking Transforms/Inline/blockaddress.ll llvm-svn: 354079
2019-02-12[NFC] Rename DontDeleteUselessPHIs --> KeepOneInputPHIsMax Kazantsev1-4/+4
llvm-svn: 353801
2019-01-19Update the file headers across all of the LLVM projects in the monorepoChandler Carruth1-4/+3
to reflect the new license. We understand that people may be surprised that we're moving the header entirely to discuss the new license. We checked this carefully with the Foundation's lawyer and we believe this is the correct approach. Essentially, all code in the project is now made available by the LLVM project under our new license, so you will see that the license headers include that license only. Some of our contributors have contributed code under our old license, and accordingly, we have retained a copy of our old license notice in the top-level files in each project and repository. llvm-svn: 351636
2018-12-21[IR] Add Instruction::isLifetimeStartOrEnd, NFCVedant Kumar1-4/+2
Instruction::isLifetimeStartOrEnd() checks whether an Instruction is an llvm.lifetime.start or an llvm.lifetime.end intrinsic. This was suggested as a cleanup in D55967. Differential Revision: https://reviews.llvm.org/D56019 llvm-svn: 349964
2018-11-19[IR] Add hasNPredecessors, hasNPredecessorsOrMore to BasicBlockVedant Kumar1-0/+8
Add methods to BasicBlock which make it easier to efficiently check whether a block has N (or more) predecessors. This can be more efficient than using pred_size(), which is a linear time operation. We might consider adding similar methods for successors. I haven't done so in this patch because succ_size() is already O(1). With this patch applied, I measured a 0.065% compile-time reduction in user time for running `opt -O3` on the sqlite3 amalgamation (30 trials). The change in mergeStoreIntoSuccessor alone saves 45 million linked list iterations in a stage2 Release build of llc. See llvm.org/PR39702 for a harder but more general way of achieving similar results. Differential Revision: https://reviews.llvm.org/D54686 llvm-svn: 347256
2018-10-15[TI removal] Make `getTerminator()` return a generic `Instruction`.Chandler Carruth1-3/+4
This removes the primary remaining API producing `TerminatorInst` which will reduce the rate at which code is introduced trying to use it and generally make it much easier to remove the remaining APIs across the codebase. Also clean up some of the stragglers that the previous mechanical update of variables missed. Users of LLVM and out-of-tree code generally will need to update any explicit variable types to handle this. Replacing `TerminatorInst` with `Instruction` (or `auto`) almost always works. Most of these edits were made in prior commits using the perl one-liner: ``` perl -i -ple 's/TerminatorInst(\b.* = .*getTerminator\(\))/Instruction\1/g' ``` This also my break some rare use cases where people overload for both `Instruction` and `TerminatorInst`, but these should be easily fixed by removing the `TerminatorInst` overload. llvm-svn: 344504
2018-10-15[TI removal] Make variables declared as `TerminatorInst` and initializedChandler Carruth1-2/+2
by `getTerminator()` calls instead be declared as `Instruction`. This is the biggest remaining chunk of the usage of `getTerminator()` that insists on the narrow type and so is an easy batch of updates. Several files saw more extensive updates where this would cascade to requiring API updates within the file to use `Instruction` instead of `TerminatorInst`. All of these were trivial in nature (pervasively using `Instruction` instead just worked). llvm-svn: 344502
2018-08-26[IR] Sink `isExceptional` predicate to `Instruction`, rename it toChandler Carruth1-1/+1
`isExceptionalTermiantor` and implement it for opcodes as well following the common pattern in `Instruction`. Part of removing `TerminatorInst` from the `Instruction` type hierarchy to make it easier to share logic and interfaces between instructions that are both terminators and not terminators. llvm-svn: 340699
2018-08-26[IR] Begin removal of TerminatorInst by removing successor manipulation.Chandler Carruth1-1/+1
The core get and set routines move to the `Instruction` class. These routines are only valid to call on instructions which are terminators. The iterator and *generic* range based access move to `CFG.h` where all the other generic successor and predecessor access lives. While moving the iterator here, simplify it using the iterator utilities LLVM provides and updates coding style as much as reasonable. The APIs remain pointer-heavy when they could better use references, and retain the odd behavior of `operator*` and `operator->` that is common in LLVM iterators. Adjusting this API, if desired, should be a follow-up step. Non-generic range iteration is added for the two instructions where there is an especially easy mechanism and where there was code attempting to use the range accessor from a specific subclass: `indirectbr` and `br`. In both cases, the successors are contiguous operands and can be easily iterated via the operand list. This is the first major patch in removing the `TerminatorInst` type from the IR's instruction type hierarchy. This change was discussed in an RFC here and was pretty clearly positive: http://lists.llvm.org/pipermail/llvm-dev/2018-May/123407.html There will be a series of much more mechanical changes following this one to complete this move. Differential Revision: https://reviews.llvm.org/D47467 llvm-svn: 340698
2018-06-26Rename skipDebugInfo -> skipDebugIntrinsics, NFCVedant Kumar1-1/+1
This addresses post-commit feedback about the name 'skipDebugInfo' being misleading. This name could be interpreted as meaning 'a function that skips instructions with debug locations'. The new name, 'skipDebugIntrinsics', makes it clear that this function only skips debug info intrinsics. Thanks to Adrian Prantl for pointing this out! llvm-svn: 335667
2018-06-19[IR] Introduce helpers to skip debug instructions (NFC)Vedant Kumar1-0/+6
This patch introduces two helpers to make it easier to ignore debug intrinsics: - Instruction::getNextNonDebugInstruction() This is just like Instruction::getNextNode(), except that it skips debug info. - skipDebugInfo(BasicBlock::iterator) A free function which advances a BasicBlock iterator past any debug info. This is a no-op when the iterator already points to a non-debug instruction. Part of: llvm.org/PR37728 Related to: https://reviews.llvm.org/D47874 Differential Revision: https://reviews.llvm.org/D48305 llvm-svn: 335083
2018-04-19[BasicBlock] Add instructionsWithoutDebug methods to skip debug insts.Florian Hahn1-0/+18
Reviewers: aprantl, vsk, mattd, chandlerc Reviewed By: aprantl, vsk Differential Revision: https://reviews.llvm.org/D45657 llvm-svn: 330316
2017-12-29IR: Fix BasicBlock::phis for empty blocksMatt Arsenault1-1/+2
llvm-svn: 321567
2017-11-02Irreducible loop metadata for more accurate block frequency under PGO.Hiroshi Yamauchi1-0/+13
Summary: Currently the block frequency analysis is an approximation for irreducible loops. The new irreducible loop metadata is used to annotate the irreducible loop headers with their header weights based on the PGO profile (currently this is approximated to be evenly weighted) and to help improve the accuracy of the block frequency analysis for irreducible loops. This patch is a basic support for this. Reviewers: davidxl Reviewed By: davidxl Subscribers: mehdi_amini, llvm-commits, eraman Differential Revision: https://reviews.llvm.org/D39028 llvm-svn: 317278
2017-06-22Restrict the definition of loop preheader to avoid EH blocksAndrew Kaylor1-0/+13
Differential Revision: https://reviews.llvm.org/D34487 llvm-svn: 306070
2017-05-26[IR] Add an iterator and range accessor for the PHI nodes of a basicChandler Carruth1-7/+9
block. This allows writing much more natural and readable range based for loops directly over the PHI nodes. It also takes advantage of the same tricks for terminating the sequence as the hand coded versions. I've replaced one example of this mostly to showcase the difference and I've added a unit test to make sure the facilities really work the way they're intended. I want to use this inside of SimpleLoopUnswitch but it seems generally nice. Differential Revision: https://reviews.llvm.org/D33533 llvm-svn: 303964
2017-03-27[IR] Share implementation for pairs of const and non-const methods using ↵Craig Topper1-3/+0
const_cast. NFCI llvm-svn: 298830
2017-03-27[IR] Share implementation of pairs of const and non-const methods in ↵Craig Topper1-27/+27
BasicBlock using the const version instead of the non-const version Summary: During post-commit review of a previous change I made it was pointed out that const casting 'this' is technically a bad practice. This patch re-implements all of the methods in BasicBlock that do this to use the const BasicBlock version and const_cast the return value instead. I think there are still many other classes that do similar things. I may look at more in the future. Reviewers: dblaikie Reviewed By: dblaikie Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D31377 llvm-svn: 298827
2017-01-22[IR] Use const_cast to reuse the const version of two BasicBlock methods ↵Craig Topper1-9/+0
that are duplicated for both const and non-const. NFC Similar is already done for other methods in BasicBlock. llvm-svn: 292753
2016-09-17Don't create a SymbolTable in Function when the LLVMContext discards value ↵Mehdi Amini1-1/+1
names (NFC) The ValueSymbolTable is used to detect name conflict and rename instructions automatically. This is not needed when the value names are automatically discarded by the LLVMContext. No functional change intended, just saving a little bit of memory. This is a recommit of r281806 after fixing the accessor to return a pointer instead of a reference and updating all the call-sites. llvm-svn: 281813
2016-06-26Apply clang-tidy's modernize-loop-convert to most of lib/IR.Benjamin Kramer1-2/+2
Only minor manual fixes. No functionality change intended. llvm-svn: 273813
2016-05-02Revert "[SimplifyCFG] Extend TryToSimplifyUncondBranchFromEmptyBlock for ↵Reid Kleckner1-24/+0
empty block including lifetime intrinsics" This reverts commit r268254. This change causes assertion failures while building Chromium. Reduced test case coming soon. llvm-svn: 268288
2016-05-02[SimplifyCFG] Extend TryToSimplifyUncondBranchFromEmptyBlock for empty block ↵Hans Wennborg1-0/+24
including lifetime intrinsics Make it possible that TryToSimplifyUncondBranchFromEmptyBlock merges empty basic block including lifetime intrinsics as well as phi nodes and unconditional branch into its successor or predecessor(s). If successor of empty block has single predecessor, all contents including lifetime intrinsics are sinked into the successor. Otherwise, they are hoisted into its predecessor(s) and then merged into the predecessor(s). Patch by Josh Yoon <josh.yoon@samsung.com>! Differential Revision: http://reviews.llvm.org/D19257 llvm-svn: 268254
2016-03-11Introduce @llvm.experimental.deoptimizeSanjoy Das1-0/+15
Summary: This intrinsic, together with deoptimization operand bundles, allow frontends to express transfer of control and frame-local state from one (typically more specialized, hence faster) version of a function into another (typically more generic, hence slower) version. In languages with a fully integrated managed runtime this intrinsic can be used to implement "uncommon trap" like functionality. In unmanaged languages like C and C++, this intrinsic can be used to represent the slow paths of specialized functions. Note: this change does not address how `@llvm.experimental_deoptimize` is lowered. That will be done in a later change. Reviewers: chandlerc, rnk, atrick, reames Subscribers: llvm-commits, kmod, mjacob, maksfb, mcrosier, JosephTremoulet Differential Revision: http://reviews.llvm.org/D17732 llvm-svn: 263281
2016-02-21ADT: Stop using getNodePtrUnchecked on end() iteratorsDuncan P. N. Exon Smith1-4/+2
Stop using `getNodePtrUnchecked()` when building IR. Eventually a dereference will be required to get at the downcast node, since the iterator will only store an `ilist_node_base` of some sort. This should have no functionality change for now, but is a path towards removing some more UB from ilist. llvm-svn: 261495
2015-10-08IR: Remove implicit iterator conversions from lib/IR, NFCDuncan P. N. Exon Smith1-9/+9
Stop converting implicitly between iterators and pointers/references in lib/IR. For convenience, I've added a `getIterator()` accessor to `ilist_node` so that callers don't need to know how to spell the iterator class (i.e., they can use `X.getIterator()` instead of `Function::iterator(X)`). I'll eventually disallow these implicit conversions entirely, but there's a lot of code, so it doesn't make sense to do it all in one patch. One library or so at a time. Why? To root out cases of `getNextNode()` and `getPrevNode()` being used in iterator logic. The design of `ilist` makes that invalid when the current node could be at the back of the list, but it happens to "work" right now because of a bug where those functions never return `nullptr` if you're using a half-node sentinel. Before I can fix the function, I have to remove uses of it that rely on it misbehaving. (Maybe the function should just be deleted anyway? But I don't want deleting it -- potentially a huge project -- to block fixing ilist/iplist.) llvm-svn: 249782
2015-10-07IR: Create SymbolTableList wrapper around iplist, NFCDuncan P. N. Exon Smith1-1/+1
Create `SymbolTableList`, a wrapper around `iplist` for lists that automatically manage a symbol table. This commit reduces a ton of code duplication between the six traits classes that were used previously. As a drive by, reduce the number of template parameters from 2 to 1 by using a SymbolTableListParentType metafunction (I originally had this as a separate commit, but it touched most of the same lines so I squashed them). I'm in the process of trying to remove the UB in `createSentinel()` (see the FIXMEs I added for `ilist_embedded_sentinel_traits` and `ilist_half_embedded_sentinel_traits`). My eventual goal is to separate the list logic into a base class layer that knows nothing about (and isn't templated on) the downcasted nodes -- removing the need to invoke UB -- but for now I'm just trying to get a handle on all the current use cases (and cleaning things up as I see them). Besides these six SymbolTable lists, there are two others that use the addNode/removeNode/transferNodes() hooks: the `MachineInstruction` and `MachineBasicBlock` lists. Ideally there'll be a way to factor these hooks out of the low-level API entirely, but I'm not quite there yet. llvm-svn: 249602
2015-10-06Fix Clang-tidy modernize-use-nullptr warnings in source directories and ↵Hans Wennborg1-3/+3
generated files; other minor cleanups. Patch by Eugene Zelenko! Differential Revision: http://reviews.llvm.org/D13321 llvm-svn: 249482
2015-08-06Convert a bunch of loops to foreach. NFC.Pete Cooper1-2/+1
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
2015-07-31New EH representation for MSVC compatibilityDavid Majnemer1-1/+12
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
2015-07-10Revert the new EH instructionsDavid Majnemer1-1/+1
This reverts commits r241888-r241891, I didn't mean to commit them. llvm-svn: 241893
2015-07-10New EH representation for MSVC compatibilityDavid Majnemer1-1/+1
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
2015-07-07Revert "Revert r241570, it caused PR24053"David Majnemer1-29/+22
This reverts commit r241602. We had a latent bug in SCCP where we would make a basic block empty and then proceed to ask questions about it's terminator. llvm-svn: 241616
2015-07-07Revert r241570, it caused PR24053Nico Weber1-22/+29
llvm-svn: 241602
2015-07-07[IR] Make getFirstNonPHI return null if the BB is emptyDavid Majnemer1-29/+22
getFirstNonPHI's documentation states that it returns null if there is no non-PHI instruction. However, it instead returns a pointer to the end iterator. The implementation of getFirstNonPHI claims that dereferencing the iterator will result in an assertion failure but this doesn't occur. Instead, machinery like getFirstInsertionPt will attempt to isa<> this invalid memory which results in unpredictable behavior. Instead, make getFirst* return null if no such instruction exists. llvm-svn: 241570
2015-06-11Set proper debug location for branch added in BasicBlock::splitBasicBlock().Alexey Samsonov1-1/+4
This improves debug locations in passes that do a lot of basic block transformations. Important case is LoopUnroll pass, the test for correct debug locations accompanies this change. Test Plan: regression test suite Reviewers: dblaikie, sanjoy Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D10367 llvm-svn: 239551
2015-05-26[PlaceSafepoints] Cleanup InsertSafepointPoll functionPhilip Reames1-0/+4
While working on another change, I noticed that the naming in this function was mildly deceptive. While fixing that, I took the oppurtunity to modernize some of the code. NFC intended. llvm-svn: 238252
2015-05-15Add a speculative execution passJingyue Wu1-0/+8
Summary: This is a pass for speculative execution of instructions for simple if-then (triangle) control flow. It's aimed at GPUs, but could perhaps be used in other contexts. Enabling this pass gives us a 1.0% geomean improvement on Google benchmark suites, with one benchmark improving 33%. Credit goes to Jingyue Wu for writing an earlier version of this pass. Patched by Bjarke Roune. Test Plan: This patch adds a set of tests in test/Transforms/SpeculativeExecution/spec.ll The pass is controlled by a flag which defaults to having the pass not run. Reviewers: eliben, dberlin, meheff, jingyue, hfinkel Reviewed By: jingyue, hfinkel Subscribers: majnemer, jholewinski, llvm-commits Differential Revision: http://reviews.llvm.org/D9360 llvm-svn: 237459
2015-04-03Return iterator from BasicBlock::eraseFromParentDaniel Berlin1-2/+2
Summary: Same as the last patch, but for BasicBlock (Requires same code movement) Reviewers: chandlerc Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D8801 llvm-svn: 233992
2015-03-03Remove getDataLayout() from Instruction/GlobalValue/BasicBlock/FunctionMehdi Amini1-4/+3
Summary: This does not conceptually belongs here. Instead provide a shortcut getModule() that provides access to the DataLayout. Reviewers: chandlerc, echristo Reviewed By: echristo Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D8027 From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 231147
2015-02-27remove function names from comments; NFCSanjay Patel1-9/+8
llvm-svn: 230771
generated by cgit v1.1 at 2025-10-16 18:11:19 +0000