aboutsummaryrefslogtreecommitdiff
path: root/lib/CodeGen/IfConversion.cpp
AgeCommit message (Collapse)Author
2013-05-05Teach if-converter to avoid removing BBs whose addresses are takne. ↵Evan Cheng
rdar://13782395 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@181160 91177308-0d34-0410-b5e6-96231b3b80d8
2013-04-10Manually remove successors in if conversion when CopyAndPredicateBlock is usedHal Finkel
In the simple and triangle if-conversion cases, when CopyAndPredicateBlock is used because the to-be-predicated block has other predecessors, we need to explicitly remove the old copied block from the successors list. Normally if conversion relies on TII->AnalyzeBranch combined with BB->CorrectExtraCFGEdges to cleanup the successors list, but if the predicated block contained an un-analyzable branch (such as a now-predicated return), then this will fail. These extra successors were causing a problem on PPC because it was causing later passes (such as PPCEarlyReturm) to leave dead return-only basic blocks in the code. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@179227 91177308-0d34-0410-b5e6-96231b3b80d8
2013-01-24Avoid creating duplicate CFG edges in the IfConversion pass.Jakob Stoklund Olesen
Patch by Stefan Hepp. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@173395 91177308-0d34-0410-b5e6-96231b3b80d8
2013-01-11Split TargetLowering into a CodeGen and a SelectionDAG part.Benjamin Kramer
This fixes some of the cycles between libCodeGen and libSelectionDAG. It's still a complete mess but as long as the edges consist of virtual call it doesn't cause breakage. BasicTTI did static calls and thus broke some build configurations. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@172246 91177308-0d34-0410-b5e6-96231b3b80d8
2012-12-20Use MachineInstrBuilder in a few CodeGen passes.Jakob Stoklund Olesen
This automatically passes a context pointer to MI->addOperand(). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@170711 91177308-0d34-0410-b5e6-96231b3b80d8
2012-12-03Use the new script to sort the includes of every file under lib.Chandler Carruth
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. =] git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169131 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-22Reduce duplicated hash map lookups.Benjamin Kramer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162362 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-22Add a getName function to MachineFunction. Use it in places that previously ↵Craig Topper
did getFunction()->getName(). Remove includes of Function.h that are no longer needed. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162347 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-08Start implementing pre-ra if-converter: using speculation and selects to ↵Evan Cheng
eliminate branches. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158234 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-01Switch all register list clients to the new MC*Iterator interface.Jakob Stoklund Olesen
No functional change intended. Sorry for the churn. The iterator classes are supposed to help avoid giant commits like this one in the future. The TableGen-produced register lists are getting quite large, and it may be necessary to change the table representation. This makes it possible to do so without changing all clients (again). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157854 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-30If-converter models predicated defs as read + write. The read should be ↵Evan Cheng
marked as 'undef' since it may not already be live. This appeases -verify-machineinstrs. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157662 91177308-0d34-0410-b5e6-96231b3b80d8
2012-03-05Convert more GenRegisterInfo tables from unsigned to uint16_t to reduce ↵Craig Topper
static data size. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152016 91177308-0d34-0410-b5e6-96231b3b80d8
2012-02-08Codegen pass definition cleanup. No functionality.Andrew Trick
Moving toward a uniform style of pass definition to allow easier target configuration. Globally declare Pass ID. Globally declare pass initializer. Use INITIALIZE_PASS consistently. Add a call to the initializer from CodeGen.cpp. Remove redundant "createPass" functions and "getPassName" methods. While cleaning up declarations, cleaned up comments (sorry for large diff). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@150100 91177308-0d34-0410-b5e6-96231b3b80d8
2012-02-05Convert assert(0) to llvm_unreachableCraig Topper
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@149816 91177308-0d34-0410-b5e6-96231b3b80d8
2011-12-19Add a if-conversion optimization that allows 'true' side of a diamond to beEvan Cheng
unpredicated. That is, turn subeq r0, r1, #1 addne r0, r1, #1 into sub r0, r1, #1 addne r0, r1, #1 For targets where conditional instructions are always executed, this may be beneficial. It may remove pseudo anti-dependency in out-of-order execution CPUs. e.g. op r1, ... str r1, [r10] ; end-of-life of r1 as div result cmp r0, #65 movne r1, #44 ; raw dependency on previous r1 moveq r1, #12 If movne is unpredicated, then op r1, ... str r1, [r10] cmp r0, #65 mov r1, #44 ; r1 written unconditionally moveq r1, #12 Both mov and moveq are no longer depdendent on the first instruction. This gives the out-of-order execution engine more freedom to reorder them. This has passed entire LLVM test suite. But it has not been enabled for any ARM variant pending more performance evaluation. rdar://8951196 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@146914 91177308-0d34-0410-b5e6-96231b3b80d8
2011-12-07Add bundle aware API for querying instruction properties and switch the codeEvan Cheng
generator to it. For non-bundle instructions, these behave exactly the same as the MC layer API. For properties like mayLoad / mayStore, look into the bundle and if any of the bundled instructions has the property it would return true. For properties like isPredicable, only return true if *all* of the bundled instructions have the property. For properties like canFoldAsLoad, isCompare, conservatively return false for bundles. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@146026 91177308-0d34-0410-b5e6-96231b3b80d8
2011-11-04Added missing &. Fixes <rdar://problem/10393723>Pete Cooper
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@143753 91177308-0d34-0410-b5e6-96231b3b80d8
2011-08-03Fix typo in #include which revealed in the case-sensitive filesystem.Jakub Staszak
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@136828 91177308-0d34-0410-b5e6-96231b3b80d8
2011-08-03Use MachineBranchProbabilityInfo in If-Conversion instead of its own heuristics.Jakub Staszak
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@136826 91177308-0d34-0410-b5e6-96231b3b80d8
2011-07-22Revert patch which broke some IfConversion tests.Jakub Staszak
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135738 91177308-0d34-0410-b5e6-96231b3b80d8
2011-07-22Fix typo in #include which revealed in the case-sensitive filesystem.Jakub Staszak
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135734 91177308-0d34-0410-b5e6-96231b3b80d8
2011-07-21Use MachineBranchProbabilityInfo instead of MachineLoopInfo in IfConversion.Jakub Staszak
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135724 91177308-0d34-0410-b5e6-96231b3b80d8
2011-07-10Use BranchProbability instead of floating points in IfConverter.Jakub Staszak
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@134858 91177308-0d34-0410-b5e6-96231b3b80d8
2011-07-10Don't analyze block if it's not considered for ifcvt anymore.Jakub Staszak
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@134856 91177308-0d34-0410-b5e6-96231b3b80d8
2011-06-29Sink SubtargetFeature and TargetInstrItineraries (renamed ↵Evan Cheng
MCInstrItineraries) into MC. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@134049 91177308-0d34-0410-b5e6-96231b3b80d8
2011-06-28- Rename TargetInstrDesc, TargetOperandInfo to MCInstrDesc and MCOperandInfo andEvan Cheng
sink them into MC layer. - Added MCInstrInfo, which captures the tablegen generated static data. Chang TargetInstrInfo so it's based off MCInstrInfo. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@134021 91177308-0d34-0410-b5e6-96231b3b80d8
2011-05-12Re-commit 131172 with fix. MachineInstr identity checks should check deadEvan Cheng
markers. In some cases a register def is dead on one path, but not on another. This is passing Clang self-hosting. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@131214 91177308-0d34-0410-b5e6-96231b3b80d8
2011-05-11Revert 131172 as it is causing clang to miscompile itself. I will tryRafael Espindola
to provide a reduced testcase. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@131176 91177308-0d34-0410-b5e6-96231b3b80d8
2011-05-11Add a late optimization to BranchFolding that hoist common instruction sequencesEvan Cheng
at the start of basic blocks to their common predecessor. It's actually quite common (e.g. about 50 times in JM/lencod) and has shown to be a nice code size benefit. e.g. pushq %rax testl %edi, %edi jne LBB0_2 ## BB#1: xorb %al, %al popq %rdx ret LBB0_2: xorb %al, %al callq _foo popq %rdx ret => pushq %rax xorb %al, %al testl %edi, %edi je LBB0_2 ## BB#1: callq _foo LBB0_2: popq %rdx ret rdar://9145558 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@131172 91177308-0d34-0410-b5e6-96231b3b80d8
2011-04-27If converter was being too cute. It look for root BBs (which don't haveEvan Cheng
successors) and use inverse depth first search to traverse the BBs. However that doesn't work when the CFG has infinite loops. Simply do a linear traversal of all BBs work just fine. rdar://9344645 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@130324 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-06Prune includes.Benjamin Kramer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@118342 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-03Two sets of changes. Sorry they are intermingled.Evan Cheng
1. Fix pre-ra scheduler so it doesn't try to push instructions above calls to "optimize for latency". Call instructions don't have the right latency and this is more likely to use introduce spills. 2. Fix if-converter cost function. For ARM, it should use instruction latencies, not # of micro-ops since multi-latency instructions is completely executed even when the predicate is false. Also, some instruction will be "slower" when they are predicated due to the register def becoming implicit input. rdar://8598427 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@118135 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-26When the "true" and "false" blocks of a diamond if-conversion are the same,Bob Wilson
do not double-count the duplicate instructions by counting once from the beginning and again from the end. Keep track of where the duplicates from the beginning ended and don't go past that point when counting duplicates at the end. Radar 8589805. This change causes one of the MC/ARM/simple-fp-encoding tests to produce different (better!) code without the vmovne instruction being tested. I changed the test to produce vmovne and vmoveq instructions but moving between register files in the opposite direction. That's not quite the same but predicated versions of those instructions weren't being tested before, so at least the test coverage is not any worse, just different. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@117333 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-26Change if-conversion to keep track of the extra cost due to microcodedBob Wilson
instructions separately from the count of non-predicated instructions. The instruction count is used in places to determine how many instructions to copy, predicate, etc. and things get confused if that count includes the extra cost for microcoded ops. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@117332 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-19Get rid of static constructors for pass registration. Instead, every pass ↵Owen Anderson
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@116820 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-12Begin adding static dependence information to passes, which will allow us toOwen Anderson
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@116334 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-07Now with fewer extraneous semicolons!Owen Anderson
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@115996 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-01Thread the determination of branch prediction hit rates back through the ↵Owen Anderson
if-conversion heuristic APIs. For now, stick with a constant estimate of 90% (branch predictors are good!), but we might find that we want to provide more nuanced estimates in the future. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@115364 91177308-0d34-0410-b5e6-96231b3b80d8
2010-09-29Silence msvc warnings.Benjamin Kramer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@115097 91177308-0d34-0410-b5e6-96231b3b80d8
2010-09-28Give the if-converter access to MachineLoopInfo, and use it to generate ↵Owen Anderson
plausible branch prediction estimates. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@114981 91177308-0d34-0410-b5e6-96231b3b80d8
2010-09-28Part one of switching to using a more sane heuristic for determining ↵Owen Anderson
if-conversion profitability. Rather than having arbitrary cutoffs, actually try to cost model the conversion. For now, the constants are tuned to more or less match our existing behavior, but these will be changed to reflect realistic values as this work proceeds. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@114973 91177308-0d34-0410-b5e6-96231b3b80d8
2010-09-10Teach if-converter to be more careful with predicating instructions that wouldEvan Cheng
take multiple cycles to decode. For the current if-converter clients (actually only ARM), the instructions that are predicated on false are not nops. They would still take machine cycles to decode. Micro-coded instructions such as LDM / STM can potentially take multiple cycles to decode. If-converter should take treat them as non-micro-coded simple instructions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@113570 91177308-0d34-0410-b5e6-96231b3b80d8
2010-08-06Reapply r110396, with fixes to appease the Linux buildbot gods.Owen Anderson
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@110460 91177308-0d34-0410-b5e6-96231b3b80d8
2010-08-06Revert r110396 to fix buildbots.Owen Anderson
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@110410 91177308-0d34-0410-b5e6-96231b3b80d8
2010-08-05Don't use PassInfo* as a type identifier for passes. Instead, use the ↵Owen Anderson
address of the static ID member as the sole unique type identifier. Clean up APIs related to this change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@110396 91177308-0d34-0410-b5e6-96231b3b80d8
2010-07-21Fix batch of converting RegisterPass<> to INTIALIZE_PASS().Owen Anderson
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@109045 91177308-0d34-0410-b5e6-96231b3b80d8
2010-06-29Reapply my if-conversion cleanup from svn r106939 with fixes.Bob Wilson
There are 2 changes relative to the previous version of the patch: 1) For the "simple" if-conversion case, there's no need to worry about RemoveExtraEdges not handling an unanalyzable branch. Predicated terminators are ignored in this context, so RemoveExtraEdges does the right thing. This might break someday if we ever treat indirect branches (BRIND) as predicable, but for now, I just removed this part of the patch, because in the case where we do not add an unconditional branch, we rely on keeping the fall-through edge to CvtBBI (which is empty after this transformation). The change relative to the previous patch is: @@ -1036,10 +1036,6 @@ IterIfcvt = false; } - // RemoveExtraEdges won't work if the block has an unanalyzable branch, - // which is typically the case for IfConvertSimple, so explicitly remove - // CvtBBI as a successor. - BBI.BB->removeSuccessor(CvtBBI->BB); RemoveExtraEdges(BBI); // Update block info. BB can be iteratively if-converted. 2) My patch exposed a bug in the code for merging the tail of a "diamond", which had previously never been exercised. The code was simply checking that the tail had a single predecessor, but there was a case in MultiSource/Benchmarks/VersaBench/dbms where that single predecessor was neither edge of the diamond. I added the following change to check for that: @@ -1276,7 +1276,18 @@ // tail, add a unconditional branch to it. if (TailBB) { BBInfo TailBBI = BBAnalysis[TailBB->getNumber()]; - if (TailBB->pred_size() == 1 && !TailBBI.HasFallThrough) { + bool CanMergeTail = !TailBBI.HasFallThrough; + // There may still be a fall-through edge from BBI1 or BBI2 to TailBB; + // check if there are any other predecessors besides those. + unsigned NumPreds = TailBB->pred_size(); + if (NumPreds > 1) + CanMergeTail = false; + else if (NumPreds == 1 && CanMergeTail) { + MachineBasicBlock::pred_iterator PI = TailBB->pred_begin(); + if (*PI != BBI1->BB && *PI != BBI2->BB) + CanMergeTail = false; + } + if (CanMergeTail) { MergeBlocks(BBI, TailBBI); TailBBI.IsDone = true; } else { With these fixes, I was able to run all the SingleSource and MultiSource tests successfully. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@107110 91177308-0d34-0410-b5e6-96231b3b80d8
2010-06-28new, no longer brain-dead, r106907Jim Grosbach
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@107060 91177308-0d34-0410-b5e6-96231b3b80d8
2010-06-28Revert r106907, "make sure to handle dbg_value instructions in the middle of theDaniel Dunbar
block, not...", it caused a bunch of nightly test regressions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@107009 91177308-0d34-0410-b5e6-96231b3b80d8
2010-06-26Revert my if-conversion cleanup since it caused a bunch of nightly testBob Wilson
regressions. --- Reverse-merging r106939 into '.': U test/CodeGen/Thumb2/thumb2-ifcvt3.ll U lib/CodeGen/IfConversion.cpp git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@106951 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-04-27 16:15:06 +0000