1349cc55cSDimitry Andric //===- CodeGenCommonISel.h - Common code between ISels ---------*- C++ -*--===// 2349cc55cSDimitry Andric // 3349cc55cSDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4349cc55cSDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 5349cc55cSDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6349cc55cSDimitry Andric // 7349cc55cSDimitry Andric //===----------------------------------------------------------------------===// 8349cc55cSDimitry Andric // 9349cc55cSDimitry Andric // This file declares common utilities that are shared between SelectionDAG and 10349cc55cSDimitry Andric // GlobalISel frameworks. 11349cc55cSDimitry Andric // 12349cc55cSDimitry Andric //===----------------------------------------------------------------------===// 13349cc55cSDimitry Andric 14349cc55cSDimitry Andric #ifndef LLVM_CODEGEN_CODEGENCOMMONISEL_H 15349cc55cSDimitry Andric #define LLVM_CODEGEN_CODEGENCOMMONISEL_H 16349cc55cSDimitry Andric 17349cc55cSDimitry Andric #include "llvm/CodeGen/MachineBasicBlock.h" 18349cc55cSDimitry Andric #include <cassert> 19349cc55cSDimitry Andric namespace llvm { 20349cc55cSDimitry Andric 21349cc55cSDimitry Andric class BasicBlock; 22*06c3fb27SDimitry Andric enum FPClassTest : unsigned; 23*06c3fb27SDimitry Andric 24349cc55cSDimitry Andric /// Encapsulates all of the information needed to generate a stack protector 25349cc55cSDimitry Andric /// check, and signals to isel when initialized that one needs to be generated. 26349cc55cSDimitry Andric /// 27349cc55cSDimitry Andric /// *NOTE* The following is a high level documentation of SelectionDAG Stack 28349cc55cSDimitry Andric /// Protector Generation. This is now also ported be shared with GlobalISel, 29349cc55cSDimitry Andric /// but without any significant changes. 30349cc55cSDimitry Andric /// 31349cc55cSDimitry Andric /// High Level Overview of ISel Stack Protector Generation: 32349cc55cSDimitry Andric /// 33349cc55cSDimitry Andric /// Previously, the "stack protector" IR pass handled stack protector 34349cc55cSDimitry Andric /// generation. This necessitated splitting basic blocks at the IR level to 35349cc55cSDimitry Andric /// create the success/failure basic blocks in the tail of the basic block in 36349cc55cSDimitry Andric /// question. As a result of this, calls that would have qualified for the 37349cc55cSDimitry Andric /// sibling call optimization were no longer eligible for optimization since 38349cc55cSDimitry Andric /// said calls were no longer right in the "tail position" (i.e. the immediate 39349cc55cSDimitry Andric /// predecessor of a ReturnInst instruction). 40349cc55cSDimitry Andric /// 41349cc55cSDimitry Andric /// Since the sibling call optimization causes the callee to reuse the caller's 42349cc55cSDimitry Andric /// stack, if we could delay the generation of the stack protector check until 43349cc55cSDimitry Andric /// later in CodeGen after the sibling call decision was made, we get both the 44349cc55cSDimitry Andric /// tail call optimization and the stack protector check! 45349cc55cSDimitry Andric /// 46349cc55cSDimitry Andric /// A few goals in solving this problem were: 47349cc55cSDimitry Andric /// 48349cc55cSDimitry Andric /// 1. Preserve the architecture independence of stack protector generation. 49349cc55cSDimitry Andric /// 50349cc55cSDimitry Andric /// 2. Preserve the normal IR level stack protector check for platforms like 51349cc55cSDimitry Andric /// OpenBSD for which we support platform-specific stack protector 52349cc55cSDimitry Andric /// generation. 53349cc55cSDimitry Andric /// 54349cc55cSDimitry Andric /// The main problem that guided the present solution is that one can not 55349cc55cSDimitry Andric /// solve this problem in an architecture independent manner at the IR level 56349cc55cSDimitry Andric /// only. This is because: 57349cc55cSDimitry Andric /// 58349cc55cSDimitry Andric /// 1. The decision on whether or not to perform a sibling call on certain 59349cc55cSDimitry Andric /// platforms (for instance i386) requires lower level information 60349cc55cSDimitry Andric /// related to available registers that can not be known at the IR level. 61349cc55cSDimitry Andric /// 62349cc55cSDimitry Andric /// 2. Even if the previous point were not true, the decision on whether to 63349cc55cSDimitry Andric /// perform a tail call is done in LowerCallTo in SelectionDAG (or 64349cc55cSDimitry Andric /// CallLowering in GlobalISel) which occurs after the Stack Protector 65349cc55cSDimitry Andric /// Pass. As a result, one would need to put the relevant callinst into the 66349cc55cSDimitry Andric /// stack protector check success basic block (where the return inst is 67349cc55cSDimitry Andric /// placed) and then move it back later at ISel/MI time before the 68349cc55cSDimitry Andric /// stack protector check if the tail call optimization failed. The MI 69349cc55cSDimitry Andric /// level option was nixed immediately since it would require 70349cc55cSDimitry Andric /// platform-specific pattern matching. The ISel level option was 71349cc55cSDimitry Andric /// nixed because SelectionDAG only processes one IR level basic block at a 72349cc55cSDimitry Andric /// time implying one could not create a DAG Combine to move the callinst. 73349cc55cSDimitry Andric /// 74349cc55cSDimitry Andric /// To get around this problem: 75349cc55cSDimitry Andric /// 76349cc55cSDimitry Andric /// 1. SelectionDAG can only process one block at a time, we can generate 77349cc55cSDimitry Andric /// multiple machine basic blocks for one IR level basic block. 78349cc55cSDimitry Andric /// This is how we handle bit tests and switches. 79349cc55cSDimitry Andric /// 80349cc55cSDimitry Andric /// 2. At the MI level, tail calls are represented via a special return 81349cc55cSDimitry Andric /// MIInst called "tcreturn". Thus if we know the basic block in which we 82349cc55cSDimitry Andric /// wish to insert the stack protector check, we get the correct behavior 83349cc55cSDimitry Andric /// by always inserting the stack protector check right before the return 84349cc55cSDimitry Andric /// statement. This is a "magical transformation" since no matter where 85349cc55cSDimitry Andric /// the stack protector check intrinsic is, we always insert the stack 86349cc55cSDimitry Andric /// protector check code at the end of the BB. 87349cc55cSDimitry Andric /// 88349cc55cSDimitry Andric /// Given the aforementioned constraints, the following solution was devised: 89349cc55cSDimitry Andric /// 90349cc55cSDimitry Andric /// 1. On platforms that do not support ISel stack protector check 91349cc55cSDimitry Andric /// generation, allow for the normal IR level stack protector check 92349cc55cSDimitry Andric /// generation to continue. 93349cc55cSDimitry Andric /// 94349cc55cSDimitry Andric /// 2. On platforms that do support ISel stack protector check 95349cc55cSDimitry Andric /// generation: 96349cc55cSDimitry Andric /// 97349cc55cSDimitry Andric /// a. Use the IR level stack protector pass to decide if a stack 98349cc55cSDimitry Andric /// protector is required/which BB we insert the stack protector check 99349cc55cSDimitry Andric /// in by reusing the logic already therein. 100349cc55cSDimitry Andric /// 101349cc55cSDimitry Andric /// b. After we finish selecting the basic block, we produce the validation 102349cc55cSDimitry Andric /// code with one of these techniques: 103349cc55cSDimitry Andric /// 1) with a call to a guard check function 104349cc55cSDimitry Andric /// 2) with inlined instrumentation 105349cc55cSDimitry Andric /// 106349cc55cSDimitry Andric /// 1) We insert a call to the check function before the terminator. 107349cc55cSDimitry Andric /// 108349cc55cSDimitry Andric /// 2) We first find a splice point in the parent basic block 109349cc55cSDimitry Andric /// before the terminator and then splice the terminator of said basic 110349cc55cSDimitry Andric /// block into the success basic block. Then we code-gen a new tail for 111349cc55cSDimitry Andric /// the parent basic block consisting of the two loads, the comparison, 112349cc55cSDimitry Andric /// and finally two branches to the success/failure basic blocks. We 113349cc55cSDimitry Andric /// conclude by code-gening the failure basic block if we have not 114349cc55cSDimitry Andric /// code-gened it already (all stack protector checks we generate in 115349cc55cSDimitry Andric /// the same function, use the same failure basic block). 116349cc55cSDimitry Andric class StackProtectorDescriptor { 117349cc55cSDimitry Andric public: 118349cc55cSDimitry Andric StackProtectorDescriptor() = default; 119349cc55cSDimitry Andric 120349cc55cSDimitry Andric /// Returns true if all fields of the stack protector descriptor are 121349cc55cSDimitry Andric /// initialized implying that we should/are ready to emit a stack protector. shouldEmitStackProtector()122349cc55cSDimitry Andric bool shouldEmitStackProtector() const { 123349cc55cSDimitry Andric return ParentMBB && SuccessMBB && FailureMBB; 124349cc55cSDimitry Andric } 125349cc55cSDimitry Andric shouldEmitFunctionBasedCheckStackProtector()126349cc55cSDimitry Andric bool shouldEmitFunctionBasedCheckStackProtector() const { 127349cc55cSDimitry Andric return ParentMBB && !SuccessMBB && !FailureMBB; 128349cc55cSDimitry Andric } 129349cc55cSDimitry Andric 130349cc55cSDimitry Andric /// Initialize the stack protector descriptor structure for a new basic 131349cc55cSDimitry Andric /// block. initialize(const BasicBlock * BB,MachineBasicBlock * MBB,bool FunctionBasedInstrumentation)132349cc55cSDimitry Andric void initialize(const BasicBlock *BB, MachineBasicBlock *MBB, 133349cc55cSDimitry Andric bool FunctionBasedInstrumentation) { 134349cc55cSDimitry Andric // Make sure we are not initialized yet. 135349cc55cSDimitry Andric assert(!shouldEmitStackProtector() && "Stack Protector Descriptor is " 136349cc55cSDimitry Andric "already initialized!"); 137349cc55cSDimitry Andric ParentMBB = MBB; 138349cc55cSDimitry Andric if (!FunctionBasedInstrumentation) { 139349cc55cSDimitry Andric SuccessMBB = addSuccessorMBB(BB, MBB, /* IsLikely */ true); 140349cc55cSDimitry Andric FailureMBB = addSuccessorMBB(BB, MBB, /* IsLikely */ false, FailureMBB); 141349cc55cSDimitry Andric } 142349cc55cSDimitry Andric } 143349cc55cSDimitry Andric 144349cc55cSDimitry Andric /// Reset state that changes when we handle different basic blocks. 145349cc55cSDimitry Andric /// 146349cc55cSDimitry Andric /// This currently includes: 147349cc55cSDimitry Andric /// 148349cc55cSDimitry Andric /// 1. The specific basic block we are generating a 149349cc55cSDimitry Andric /// stack protector for (ParentMBB). 150349cc55cSDimitry Andric /// 151349cc55cSDimitry Andric /// 2. The successor machine basic block that will contain the tail of 152349cc55cSDimitry Andric /// parent mbb after we create the stack protector check (SuccessMBB). This 153349cc55cSDimitry Andric /// BB is visited only on stack protector check success. resetPerBBState()154349cc55cSDimitry Andric void resetPerBBState() { 155349cc55cSDimitry Andric ParentMBB = nullptr; 156349cc55cSDimitry Andric SuccessMBB = nullptr; 157349cc55cSDimitry Andric } 158349cc55cSDimitry Andric 159349cc55cSDimitry Andric /// Reset state that only changes when we switch functions. 160349cc55cSDimitry Andric /// 161349cc55cSDimitry Andric /// This currently includes: 162349cc55cSDimitry Andric /// 163349cc55cSDimitry Andric /// 1. FailureMBB since we reuse the failure code path for all stack 164349cc55cSDimitry Andric /// protector checks created in an individual function. 165349cc55cSDimitry Andric /// 166349cc55cSDimitry Andric /// 2.The guard variable since the guard variable we are checking against is 167349cc55cSDimitry Andric /// always the same. resetPerFunctionState()168349cc55cSDimitry Andric void resetPerFunctionState() { FailureMBB = nullptr; } 169349cc55cSDimitry Andric getParentMBB()170349cc55cSDimitry Andric MachineBasicBlock *getParentMBB() { return ParentMBB; } getSuccessMBB()171349cc55cSDimitry Andric MachineBasicBlock *getSuccessMBB() { return SuccessMBB; } getFailureMBB()172349cc55cSDimitry Andric MachineBasicBlock *getFailureMBB() { return FailureMBB; } 173349cc55cSDimitry Andric 174349cc55cSDimitry Andric private: 175349cc55cSDimitry Andric /// The basic block for which we are generating the stack protector. 176349cc55cSDimitry Andric /// 177349cc55cSDimitry Andric /// As a result of stack protector generation, we will splice the 178349cc55cSDimitry Andric /// terminators of this basic block into the successor mbb SuccessMBB and 179349cc55cSDimitry Andric /// replace it with a compare/branch to the successor mbbs 180349cc55cSDimitry Andric /// SuccessMBB/FailureMBB depending on whether or not the stack protector 181349cc55cSDimitry Andric /// was violated. 182349cc55cSDimitry Andric MachineBasicBlock *ParentMBB = nullptr; 183349cc55cSDimitry Andric 184349cc55cSDimitry Andric /// A basic block visited on stack protector check success that contains the 185349cc55cSDimitry Andric /// terminators of ParentMBB. 186349cc55cSDimitry Andric MachineBasicBlock *SuccessMBB = nullptr; 187349cc55cSDimitry Andric 188349cc55cSDimitry Andric /// This basic block visited on stack protector check failure that will 189349cc55cSDimitry Andric /// contain a call to __stack_chk_fail(). 190349cc55cSDimitry Andric MachineBasicBlock *FailureMBB = nullptr; 191349cc55cSDimitry Andric 192349cc55cSDimitry Andric /// Add a successor machine basic block to ParentMBB. If the successor mbb 193349cc55cSDimitry Andric /// has not been created yet (i.e. if SuccMBB = 0), then the machine basic 194349cc55cSDimitry Andric /// block will be created. Assign a large weight if IsLikely is true. 195349cc55cSDimitry Andric MachineBasicBlock *addSuccessorMBB(const BasicBlock *BB, 196349cc55cSDimitry Andric MachineBasicBlock *ParentMBB, 197349cc55cSDimitry Andric bool IsLikely, 198349cc55cSDimitry Andric MachineBasicBlock *SuccMBB = nullptr); 199349cc55cSDimitry Andric }; 200349cc55cSDimitry Andric 201349cc55cSDimitry Andric /// Find the split point at which to splice the end of BB into its success stack 202349cc55cSDimitry Andric /// protector check machine basic block. 203349cc55cSDimitry Andric /// 204349cc55cSDimitry Andric /// On many platforms, due to ABI constraints, terminators, even before register 205349cc55cSDimitry Andric /// allocation, use physical registers. This creates an issue for us since 206349cc55cSDimitry Andric /// physical registers at this point can not travel across basic 207349cc55cSDimitry Andric /// blocks. Luckily, selectiondag always moves physical registers into vregs 208349cc55cSDimitry Andric /// when they enter functions and moves them through a sequence of copies back 209349cc55cSDimitry Andric /// into the physical registers right before the terminator creating a 210349cc55cSDimitry Andric /// ``Terminator Sequence''. This function is searching for the beginning of the 211349cc55cSDimitry Andric /// terminator sequence so that we can ensure that we splice off not just the 212349cc55cSDimitry Andric /// terminator, but additionally the copies that move the vregs into the 213349cc55cSDimitry Andric /// physical registers. 214349cc55cSDimitry Andric MachineBasicBlock::iterator 215349cc55cSDimitry Andric findSplitPointForStackProtector(MachineBasicBlock *BB, 216349cc55cSDimitry Andric const TargetInstrInfo &TII); 217*06c3fb27SDimitry Andric 218*06c3fb27SDimitry Andric /// Evaluates if the specified FP class test is better performed as the inverse 219*06c3fb27SDimitry Andric /// (i.e. fewer instructions should be required to lower it). An example is the 220*06c3fb27SDimitry Andric /// test "inf|normal|subnormal|zero", which is an inversion of "nan". 22181ad6265SDimitry Andric /// \param Test The test as specified in 'is_fpclass' intrinsic invocation. 222*06c3fb27SDimitry Andric /// \returns The inverted test, or fcNone, if inversion does not produce a 223*06c3fb27SDimitry Andric /// simpler test. 224*06c3fb27SDimitry Andric FPClassTest invertFPClassTestIfSimpler(FPClassTest Test); 225349cc55cSDimitry Andric 226bdd1243dSDimitry Andric /// Assuming the instruction \p MI is going to be deleted, attempt to salvage 227bdd1243dSDimitry Andric /// debug users of \p MI by writing the effect of \p MI in a DIExpression. 228bdd1243dSDimitry Andric void salvageDebugInfoForDbgValue(const MachineRegisterInfo &MRI, 229bdd1243dSDimitry Andric MachineInstr &MI, 230bdd1243dSDimitry Andric ArrayRef<MachineOperand *> DbgUsers); 231bdd1243dSDimitry Andric 232349cc55cSDimitry Andric } // namespace llvm 233349cc55cSDimitry Andric 234349cc55cSDimitry Andric #endif // LLVM_CODEGEN_CODEGENCOMMONISEL_H 235