summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/ShrinkWrap.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Sink all InitializePasses.h includesReid Kleckner2019-11-131-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This file lists every pass in LLVM, and is included by Pass.h, which is very popular. Every time we add, remove, or rename a pass in LLVM, it caused lots of recompilation. I found this fact by looking at this table, which is sorted by the number of times a file was changed over the last 100,000 git commits multiplied by the number of object files that depend on it in the current checkout: recompiles touches affected_files header 342380 95 3604 llvm/include/llvm/ADT/STLExtras.h 314730 234 1345 llvm/include/llvm/InitializePasses.h 307036 118 2602 llvm/include/llvm/ADT/APInt.h 213049 59 3611 llvm/include/llvm/Support/MathExtras.h 170422 47 3626 llvm/include/llvm/Support/Compiler.h 162225 45 3605 llvm/include/llvm/ADT/Optional.h 158319 63 2513 llvm/include/llvm/ADT/Triple.h 140322 39 3598 llvm/include/llvm/ADT/StringRef.h 137647 59 2333 llvm/include/llvm/Support/Error.h 131619 73 1803 llvm/include/llvm/Support/FileSystem.h Before this change, touching InitializePasses.h would cause 1345 files to recompile. After this change, touching it only causes 550 compiles in an incremental rebuild. Reviewers: bkramer, asbirlea, bollu, jdoerfert Differential Revision: https://reviews.llvm.org/D70211
* Apply llvm-prefer-register-over-unsigned from clang-tidy to LLVMDaniel Sanders2019-08-151-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This clang-tidy check is looking for unsigned integer variables whose initializer starts with an implicit cast from llvm::Register and changes the type of the variable to llvm::Register (dropping the llvm:: where possible). Partial reverts in: X86FrameLowering.cpp - Some functions return unsigned and arguably should be MCRegister X86FixupLEAs.cpp - Some functions return unsigned and arguably should be MCRegister X86FrameLowering.cpp - Some functions return unsigned and arguably should be MCRegister HexagonBitSimplify.cpp - Function takes BitTracker::RegisterRef which appears to be unsigned& MachineVerifier.cpp - Ambiguous operator==() given MCRegister and const Register PPCFastISel.cpp - No Register::operator-=() PeepholeOptimizer.cpp - TargetInstrInfo::optimizeLoadInstr() takes an unsigned& MachineTraceMetrics.cpp - MachineTraceMetrics lacks a suitable constructor Manual fixups in: ARMFastISel.cpp - ARMEmitLoad() now takes a Register& instead of unsigned& HexagonSplitDouble.cpp - Ternary operator was ambiguous between unsigned/Register HexagonConstExtenders.cpp - Has a local class named Register, used llvm::Register instead of Register. PPCFastISel.cpp - PPCEmitLoad() now takes a Register& instead of unsigned& Depends on D65919 Reviewers: arsenm, bogner, craig.topper, RKSimon Reviewed By: arsenm Subscribers: RKSimon, craig.topper, lenary, aemerson, wuzish, jholewinski, MatzeB, qcolombet, dschuff, jyknight, dylanmckay, sdardis, nemanjai, jvesely, wdng, nhaehnle, sbc100, jgravelle-google, kristof.beyls, hiraditya, aheejin, kbarton, fedor.sergeev, javed.absar, asb, rbar, johnrusso, simoncook, apazos, sabuasal, niosHD, jrtc27, MaskRay, zzheng, edward-jones, atanasyan, rogfer01, MartinMosbeck, brucehoult, the_o, tpr, PkmX, jocewei, jsji, Petar.Avramovic, asbirlea, Jim, s.egerton, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D65962 llvm-svn: 369041
* Finish moving TargetRegisterInfo::isVirtualRegister() and friends to ↵Daniel Sanders2019-08-011-2/+1
| | | | | | llvm::Register as started by r367614. NFC llvm-svn: 367633
* [FIX] Forces shrink wrapping to consider any memory access as aliasing with ↵Diogo N. Sampaio2019-06-131-0/+9
| | | | | | | | | | | | | | | | | | | | | | | | | the stack Summary: Relate bug: https://bugs.llvm.org/show_bug.cgi?id=37472 The shrink wrapping pass prematurally restores the stack, at a point where the stack might still be accessed. Taking an exception can cause the stack to be corrupted. As a first approach, this patch is overly conservative, assuming that any instruction that may load or store could access the stack. Reviewers: dmgreen, qcolombet Reviewed By: qcolombet Subscribers: simpal01, efriedma, eli.friedman, javed.absar, llvm-commits, eugenis, chill, carwil, thegameg Tags: #llvm Differential Revision: https://reviews.llvm.org/D63152 llvm-svn: 363265
* Update the file headers across all of the LLVM projects in the monorepoChandler Carruth2019-01-191-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
* [ShrinkWrap] Add optimization remarks to the shrink-wrapping passFrancis Visoiu Mistrih2018-06-051-6/+27
| | | | | | | | Start by emitting remarks for very basic unsupported cases such as irreducible CFGs and EHFunclets. The end goal is to be able to cover all the cases where we give up with an explanation. llvm-svn: 333972
* Rename DEBUG macro to LLVM_DEBUG.Nicola Zaghen2018-05-141-24/+28
| | | | | | | | | | | | | | | | The DEBUG() macro is very generic so it might clash with other projects. The renaming was done as follows: - git grep -l 'DEBUG' | xargs sed -i 's/\bDEBUG\s\?(/LLVM_DEBUG(/g' - git diff -U0 master | ../clang/tools/clang-format/clang-format-diff.py -i -p1 -style LLVM - Manual change to APInt - Manually chage DOCS as regex doesn't match it. In the transition period the DEBUG() macro is still present and aliased to the LLVM_DEBUG() one. Differential Revision: https://reviews.llvm.org/D43624 llvm-svn: 332240
* Remove \brief commands from doxygen comments.Adrian Prantl2018-05-011-7/+7
| | | | | | | | | | | | | | | | We've been running doxygen with the autobrief option for a couple of years now. This makes the \brief markers into our comments redundant. Since they are a visual distraction and we don't want to encourage more \brief markers in new code either, this patch removes them all. Patch produced by for i in $(git grep -l '\\brief'); do perl -pi -e 's/\\brief //g' $i & done Differential Revision: https://reviews.llvm.org/D46290 llvm-svn: 331272
* Fix incorrect choice of callee-saved registers save/restore pointsMomchil Velikov2018-04-171-2/+14
| | | | | | | | Make the shrink wrapping pass pay attention to uses/defs of the stack pointer. Differential revision: https://reviews.llvm.org/D45524 llvm-svn: 330183
* [CodeGen]Add NoVRegs property on PostRASink and ShrinkWrapJun Bum Lim2018-04-031-0/+5
| | | | | | | | | | | | | | | | | Summary: This change declare that PostRAMachineSinking and ShrinkWrap require NoVRegs property, so now the MachineFunctionPass can enforce this check. These passes are disabled in NVPTX & WebAssembly. Reviewers: dschuff, jlebar, tra, jgravelle-google, MatzeB, sebpop, thegameg, mcrosier Reviewed By: dschuff, thegameg Subscribers: jholewinski, jfb, sbc100, aheejin, sunfish, llvm-commits Differential Revision: https://reviews.llvm.org/D45183 llvm-svn: 329095
* [ShrinkWrap] Take into account landing padQuentin Colombet2018-03-201-0/+16
| | | | | | | | | | | | | When scanning the function for CSRs uses and defs, also check if the basic block are landing pads. Consider that landing pads needs the CSRs to be properly set. That way we force the prologue/epilogue to always be pushed out of the problematic "throw" region. The "throw" region is problematic because the jumps are not properly modeled. Fixes PR36513 llvm-svn: 327942
* [LV][CFG] Add irreducible CFG detection for outer loopsFlorian Hahn2018-03-021-36/+3
| | | | | | | | | | | | | | | | This patch adds support for detecting outer loops with irreducible control flow in LV. Current detection uses SCCs and only works for innermost loops. This patch adds a utility function that works on any CFG, given its RPO traversal and its LoopInfoBase. This function is a generalization of isIrreducibleCFG from lib/CodeGen/ShrinkWrap.cpp. The code in lib/CodeGen/ShrinkWrap.cpp is also updated to use the new generic utility function. Patch by Diego Caballero <diego.caballero@intel.com> Differential Revision: https://reviews.llvm.org/D40874 llvm-svn: 326568
* [CodeGen] Skip some instructions that shouldn't affect shrink-wrappingFrancis Visoiu Mistrih2018-01-161-5/+5
| | | | | | | | | | | r320606 checked for MI.isMetaInstruction which skips all DBG_VALUEs. This also skips IMPLICIT_DEFs and other instructions that may def / read a register. Differential Revision: https://reviews.llvm.org/D42119 llvm-svn: 322584
* MachineFunction: Return reference from getFunction(); NFCMatthias Braun2017-12-151-5/+5
| | | | | | The Function can never be nullptr so we can return a reference. llvm-svn: 320884
* Ignore metainstructions during the shrink wrap analysisAdrian Prantl2017-12-131-0/+4
| | | | | | | | | | Shrink wrapping should ignore DBG_VALUEs referring to frame indices, since the presence of debug information must not affect code generation. Differential Revision: https://reviews.llvm.org/D41187 llvm-svn: 320606
* Hardware-assisted AddressSanitizer (llvm part).Evgeniy Stepanov2017-12-091-10/+11
| | | | | | | | | | | | | | | | | | | | | Summary: This is LLVM instrumentation for the new HWASan tool. It is basically a stripped down copy of ASan at this point, w/o stack or global support. Instrumenation adds a global constructor + runtime callbacks for every load and store. HWASan comes with its own IR attribute. A brief design document can be found in clang/docs/HardwareAssistedAddressSanitizerDesign.rst (submitted earlier). Reviewers: kcc, pcc, alekseyshl Subscribers: srhines, mehdi_amini, mgorny, javed.absar, eraman, llvm-commits, hiraditya Differential Revision: https://reviews.llvm.org/D40932 llvm-svn: 320217
* Fix a bunch more layering of CodeGen headers that are in TargetDavid Blaikie2017-11-171-2/+2
| | | | | | | | All these headers already depend on CodeGen headers so moving them into CodeGen fixes the layering (since CodeGen depends on Target, not the other way around). llvm-svn: 318490
* Target/TargetInstrInfo.h -> CodeGen/TargetInstrInfo.h to match layeringDavid Blaikie2017-11-081-3/+3
| | | | | | | | This header includes CodeGen headers, and is not, itself, included by any Target headers, so move it into CodeGen to match the layering of its implementation. llvm-svn: 317647
* Move TargetFrameLowering.h to CodeGen where it's implementedDavid Blaikie2017-11-031-1/+1
| | | | | | | | | | | This header already includes a CodeGen header and is implemented in lib/CodeGen, so move the header there to match. This fixes a link error with modular codegeneration builds - where a header and its implementation are circularly dependent and so need to be in the same library, not split between two like this. llvm-svn: 317379
* [CodeGen] Fix some Clang-tidy modernize and Include What You Use warnings; ↵Eugene Zelenko2017-10-101-17/+38
| | | | | | other minor fixes (NFC). llvm-svn: 315380
* CodeGen: Rename DEBUG_TYPE to match passnamesMatthias Braun2017-05-251-3/+2
| | | | | | | | Rename the DEBUG_TYPE to match the names of corresponding passes where it makes sense. Also establish the pattern of simply referencing DEBUG_TYPE instead of repeating the passname where possible. llvm-svn: 303921
* ShrinkWrap: Add skipFunction() callMatthias Braun2017-05-161-1/+1
| | | | | | | ShrinkWrapping is a performance optimization that can safely be skipped, so we can add `if (!skipFunction()) return;` llvm-svn: 303197
* [ShrinkWrapping] Handle restores on no-return pathsFrancis Visoiu Mistrih2017-05-151-2/+8
| | | | | | | | | | | | | | | | | | | Shrink-wrapping uses post-dominators to find a restore point that post-dominates all the uses of CSR / stack. The way dominator trees are modeled in LLVM today is that unreachable blocks are not present in a generic dominator tree, so, an unreachable node is dominated by anything: include/llvm/Support/GenericDomTree.h:467. Since for post-dominators, a no-return block is considered "unreachable", calling findNearestCommonDominator on an unreachable node A and a non-unreachable node B, will return B, which can be false. If we find such node, we bail out since there is no good restore point available. rdar://problem/30186931 llvm-svn: 303130
* Use StringRef in Pass/PassManager APIs (NFC)Mehdi Amini2016-10-011-3/+1
| | | | llvm-svn: 283004
* Move helpers into anonymous namespaces. NFC.Benjamin Kramer2016-08-061-2/+2
| | | | llvm-svn: 277916
* MachineFunction: Return reference for getFrameInfo(); NFCMatthias Braun2016-07-281-3/+3
| | | | | | | getFrameInfo() never returns nullptr so we should use a reference instead of a pointer. llvm-svn: 277017
* [ShrinkWrapping] Give up on irreducible CFGs.Quentin Colombet2016-01-071-0/+47
| | | | | | | | | | | We need to know whether or not a given basic block is in a loop for the analysis to be correct. Loop information may be incomplete on irreducible CFGs, therefore we may generate incorrect code if we use it in those situations. This fixes PR25988. llvm-svn: 257012
* [ShrinkWrap] Fix FindIDom to only have one kind of failure.Michael Kuperstein2016-01-061-6/+4
| | | | | | | | | | | | | FindIDom() can fail in two different ways - it can either return nullptr or the block itself, depending on the circumstances. Some users of FindIDom() check one error condition, while others check the other. Change it to always return nullptr on failure. This fixes PR26004. Differential Revision: http://reviews.llvm.org/D15847 llvm-svn: 256955
* Typo. NFC.Chad Rosier2015-12-221-1/+1
| | | | llvm-svn: 256242
* [ShrinkWrapping] Do not choose restore point inside loops.Quentin Colombet2015-12-151-5/+21
| | | | | | | | | | | | | | | | | | | | The post-dominance property is not sufficient to guarantee that a restore point inside a loop is safe. E.g., while(1) { Save Restore if (...) break; use/def CSRs } All the uses/defs of CSRs are dominated by Save and post-dominated by Restore. However, the CSRs uses are still reachable after Restore and before Save are executed. This fixes PR25824 llvm-svn: 255613
* [ShrinkWrap] Teach ShrinkWrap to handle targets requiring a register scavenger.Arnaud A. de Grandmaison2015-11-201-15/+22
| | | | | | | | The included test only checks for a compiler crash for now. Several people are facing this issue, so we first resolve the crash, and will increase shrinkwrap's coverage later in a follow-up patch. llvm-svn: 253718
* [ShrinkWrapping] Disable the optimization for functions with sanitize likeQuentin Colombet2015-11-141-1/+8
| | | | | | | | | | attribute. Even if the target supports shrink-wrapping, the prologue and epilogue must not move because a crash can happen anywhere and sanitizers need to be able to unwind from the PC of the crash. llvm-svn: 253116
* [ShrinkWrap] Fix a typo in a comment.Quentin Colombet2015-11-121-1/+1
| | | | llvm-svn: 252918
* [ShrinkWrap] Make sure we do not mess up with EH funclet lowering.Quentin Colombet2015-11-121-1/+11
| | | | | | | | ShrinkWrapping does not understand exception handling constraints for now, so make sure we do not mess with them by aborting on functions that use EH funclets. llvm-svn: 252917
* [ShrinkWrapping] Teach shrink-wrapping how to analyze RegMask.Quentin Colombet2015-11-061-8/+38
| | | | | | | Previously we were conservatively assuming that RegMask operands clobber callee saved registers. llvm-svn: 252341
* [ShrinkWrap] Refactor the handling of infinite loop in the analysis.Quentin Colombet2015-09-171-9/+11
| | | | | | | | | - Strenghten the logic to be sure we hoist the restore point out of the current loop. (The fixes a bug with infinite loop, added as part of the patch.) - Walk over the exit blocks of the current loop to conver to the desired restore point in one iteration of the update loop. llvm-svn: 247958
* [ShrinkWrapping] Fix an infinite loop while looking for restore point.Quentin Colombet2015-09-151-0/+8
| | | | | | | | | | | This may happen when the input program itself contains an infinite loop with no exit block. In that case, we would fail to find a block post-dominating the loop such that this block is outside of the loop. This fixes PR24823. Working on reducing the test case. llvm-svn: 247710
* Rework of the new interface for shrink wrappingKit Barton2015-08-311-1/+26
| | | | | | | | | | | | | | | Based on comments from Hal (http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20150810/292978.html), I've changed the interface to add a callback mechanism to the TargetFrameLowering class to query whether the specific target supports shrink wrapping. By default, shrink wrapping is disabled by default. Each target can override the default behaviour using the TargetFrameLowering::targetSupportsShrinkWrapping() method. Shrink wrapping can still be explicitly enabled or disabled from the command line, using the existing -enable-shrink-wrap=<true|false> option. Phabricator: http://reviews.llvm.org/D12293 llvm-svn: 246463
* Reverting patch r244235.Kit Barton2015-08-141-47/+1
| | | | | | | | This patch will be redone in a different way. See http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20150810/292978.html for more details. llvm-svn: 245071
* ShrinkWrap.cpp: Tweak r244235 for a non-functional member, PredicateFtor. ↵NAKAMURA Takumi2015-08-071-2/+2
| | | | | | [-Wdocumentation] llvm-svn: 244309
* Fix possible infinite loop in shrink wrapping when searching for save/restoreKit Barton2015-08-061-6/+24
| | | | | | | | | | | | | | | | | | | | points. There is an infinite loop that can occur in Shrink Wrapping while searching for the Save/Restore points. Part of this search checks whether the save/restore points are located in different loop nests and if so, uses the (post) dominator trees to find the immediate (post) dominator blocks. However, if the current block does not have any immediate (post) dominators then this search will result in an infinite loop. This can occur in code containing an infinite loop. The modification checks whether the immediate (post) dominator is different from the current save/restore block. If it is not, then the search terminates and the current location is not considered as a valid save/restore point for shrink wrapping. Phabricator: http://reviews.llvm.org/D11607 llvm-svn: 244247
* This patch changes the interface to enable the shrink wrapping optimization. Kit Barton2015-08-061-1/+47
| | | | | | | | | | | | | | | It adds a new constructor, which takes a std::function predicate function that is run at the beginning of shrink wrapping to determine whether the optimization should run on the given machine function. The std::function can be overridden by each target, allowing target-specific decisions to be made on each machine function. This is necessary for PowerPC, as the decision to run shrink wrapping is partially based on the ABI. Futhermore, this operates nicely with the GCC iFunc capability, which allows option overrides on a per-function basis. Phabricator: http://reviews.llvm.org/D11421 llvm-svn: 244235
* [ShrinkWrap] Add a target hook to check whether or notQuentin Colombet2015-05-271-5/+10
| | | | | | | | | the target can handle a given basic block as prologue or epilogue. Related to <rdar://problem/20821487> llvm-svn: 238292
* MachineInstr: Change return value of getOpcode() to unsigned.Matthias Braun2015-05-181-2/+2
| | | | | | | | | This was previously returning int. However there are no negative opcode numbers and more importantly this was needlessly different from MCInstrDesc::getOpcode() (which even is the value returned here) and SDValue::getOpcode()/SDNode::getOpcode(). llvm-svn: 237611
* [ShrinkWrap] Add (a simplified version) of shrink-wrapping.Quentin Colombet2015-05-051-0/+383
This patch introduces a new pass that computes the safe point to insert the prologue and epilogue of the function. The interest is to find safe points that are cheaper than the entry and exits blocks. As an example and to avoid regressions to be introduce, this patch also implements the required bits to enable the shrink-wrapping pass for AArch64. ** Context ** Currently we insert the prologue and epilogue of the method/function in the entry and exits blocks. Although this is correct, we can do a better job when those are not immediately required and insert them at less frequently executed places. The job of the shrink-wrapping pass is to identify such places. ** Motivating example ** Let us consider the following function that perform a call only in one branch of a if: define i32 @f(i32 %a, i32 %b) { %tmp = alloca i32, align 4 %tmp2 = icmp slt i32 %a, %b br i1 %tmp2, label %true, label %false true: store i32 %a, i32* %tmp, align 4 %tmp4 = call i32 @doSomething(i32 0, i32* %tmp) br label %false false: %tmp.0 = phi i32 [ %tmp4, %true ], [ %a, %0 ] ret i32 %tmp.0 } On AArch64 this code generates (removing the cfi directives to ease readabilities): _f: ; @f ; BB#0: stp x29, x30, [sp, #-16]! mov x29, sp sub sp, sp, #16 ; =16 cmp w0, w1 b.ge LBB0_2 ; BB#1: ; %true stur w0, [x29, #-4] sub x1, x29, #4 ; =4 mov w0, wzr bl _doSomething LBB0_2: ; %false mov sp, x29 ldp x29, x30, [sp], #16 ret With shrink-wrapping we could generate: _f: ; @f ; BB#0: cmp w0, w1 b.ge LBB0_2 ; BB#1: ; %true stp x29, x30, [sp, #-16]! mov x29, sp sub sp, sp, #16 ; =16 stur w0, [x29, #-4] sub x1, x29, #4 ; =4 mov w0, wzr bl _doSomething add sp, x29, #16 ; =16 ldp x29, x30, [sp], #16 LBB0_2: ; %false ret Therefore, we would pay the overhead of setting up/destroying the frame only if we actually do the call. ** Proposed Solution ** This patch introduces a new machine pass that perform the shrink-wrapping analysis (See the comments at the beginning of ShrinkWrap.cpp for more details). It then stores the safe save and restore point into the MachineFrameInfo attached to the MachineFunction. This information is then used by the PrologEpilogInserter (PEI) to place the related code at the right place. This pass runs right before the PEI. Unlike the original paper of Chow from PLDI’88, this implementation of shrink-wrapping does not use expensive data-flow analysis and does not need hack to properly avoid frequently executed point. Instead, it relies on dominance and loop properties. The pass is off by default and each target can opt-in by setting the EnableShrinkWrap boolean to true in their derived class of TargetPassConfig. This setting can also be overwritten on the command line by using -enable-shrink-wrap. Before you try out the pass for your target, make sure you properly fix your emitProlog/emitEpilog/adjustForXXX method to cope with basic blocks that are not necessarily the entry block. ** Design Decisions ** 1. ShrinkWrap is its own pass right now. It could frankly be merged into PEI but for debugging and clarity I thought it was best to have its own file. 2. Right now, we only support one save point and one restore point. At some point we can expand this to several save point and restore point, the impacted component would then be: - The pass itself: New algorithm needed. - MachineFrameInfo: Hold a list or set of Save/Restore point instead of one pointer. - PEI: Should loop over the save point and restore point. Anyhow, at least for this first iteration, I do not believe this is interesting to support the complex cases. We should revisit that when we motivating examples. Differential Revision: http://reviews.llvm.org/D9210 <rdar://problem/3201744> llvm-svn: 236507
OpenPOWER on IntegriCloud