X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FMachineBasicBlock.h;h=97c39458d93df5408ca99a2b0d2696972f0f0e7d;hb=881a05b46c28299046bd0dc3d0b8c6677e68a4d7;hp=5a20e952b9cc41cf25b595a91a6b5f641c6792de;hpb=fbf5f1b72b25de35452d89a4ccd7887f79880be8;p=oota-llvm.git diff --git a/include/llvm/CodeGen/MachineBasicBlock.h b/include/llvm/CodeGen/MachineBasicBlock.h index 5a20e952b9c..97c39458d93 100644 --- a/include/llvm/CodeGen/MachineBasicBlock.h +++ b/include/llvm/CodeGen/MachineBasicBlock.h @@ -77,6 +77,7 @@ class MachineBasicBlock : public ilist_node { /// (disable optimization). std::vector Weights; typedef std::vector::iterator weight_iterator; + typedef std::vector::const_iterator const_weight_iterator; /// LiveIns - Keep track of the physical registers that are livein of /// the basicblock. @@ -84,8 +85,9 @@ class MachineBasicBlock : public ilist_node { /// Alignment - Alignment of the basic block. Zero if the basic block does /// not need to be aligned. + /// The alignment is specified as log2(bytes). unsigned Alignment; - + /// IsLandingPad - Indicate that this basic block is entered via an /// exception handler. bool IsLandingPad; @@ -115,6 +117,10 @@ public: /// "(null)". StringRef getName() const; + /// getFullName - Return a formatted string to identify this block and its + /// parent function. + std::string getFullName() const; + /// hasAddressTaken - Test whether this block is potentially the target /// of an indirect branch. bool hasAddressTaken() const { return AddressTaken; } @@ -128,10 +134,84 @@ public: const MachineFunction *getParent() const { return xParent; } MachineFunction *getParent() { return xParent; } - typedef Instructions::iterator iterator; - typedef Instructions::const_iterator const_iterator; - typedef std::reverse_iterator const_reverse_iterator; - typedef std::reverse_iterator reverse_iterator; + + /// bundle_iterator - MachineBasicBlock iterator that automatically skips over + /// MIs that are inside bundles (i.e. walk top level MIs only). + template + class bundle_iterator + : public std::iterator { + IterTy MII; + + public: + bundle_iterator(IterTy mii) : MII(mii) {} + + bundle_iterator(Ty &mi) : MII(mi) { + assert(!mi.isInsideBundle() && + "It's not legal to initialize bundle_iterator with a bundled MI"); + } + bundle_iterator(Ty *mi) : MII(mi) { + assert((!mi || !mi->isInsideBundle()) && + "It's not legal to initialize bundle_iterator with a bundled MI"); + } + // Template allows conversion from const to nonconst. + template + bundle_iterator(const bundle_iterator &I) + : MII(I.getInstrIterator()) {} + bundle_iterator() : MII(0) {} + + Ty &operator*() const { return *MII; } + Ty *operator->() const { return &operator*(); } + + operator Ty*() const { return MII; } + + bool operator==(const bundle_iterator &x) const { + return MII == x.MII; + } + bool operator!=(const bundle_iterator &x) const { + return !operator==(x); + } + + // Increment and decrement operators... + bundle_iterator &operator--() { // predecrement - Back up + do --MII; + while (MII->isInsideBundle()); + return *this; + } + bundle_iterator &operator++() { // preincrement - Advance + IterTy E = MII->getParent()->instr_end(); + do ++MII; + while (MII != E && MII->isInsideBundle()); + return *this; + } + bundle_iterator operator--(int) { // postdecrement operators... + bundle_iterator tmp = *this; + --*this; + return tmp; + } + bundle_iterator operator++(int) { // postincrement operators... + bundle_iterator tmp = *this; + ++*this; + return tmp; + } + + IterTy getInstrIterator() const { + return MII; + } + }; + + typedef Instructions::iterator instr_iterator; + typedef Instructions::const_iterator const_instr_iterator; + typedef std::reverse_iterator reverse_instr_iterator; + typedef + std::reverse_iterator const_reverse_instr_iterator; + + typedef + bundle_iterator iterator; + typedef + bundle_iterator const_iterator; + typedef std::reverse_iterator const_reverse_iterator; + typedef std::reverse_iterator reverse_iterator; + unsigned size() const { return (unsigned)Insts.size(); } bool empty() const { return Insts.empty(); } @@ -141,14 +221,24 @@ public: const MachineInstr& front() const { return Insts.front(); } const MachineInstr& back() const { return Insts.back(); } - iterator begin() { return Insts.begin(); } - const_iterator begin() const { return Insts.begin(); } - iterator end() { return Insts.end(); } - const_iterator end() const { return Insts.end(); } - reverse_iterator rbegin() { return Insts.rbegin(); } - const_reverse_iterator rbegin() const { return Insts.rbegin(); } - reverse_iterator rend () { return Insts.rend(); } - const_reverse_iterator rend () const { return Insts.rend(); } + instr_iterator instr_begin() { return Insts.begin(); } + const_instr_iterator instr_begin() const { return Insts.begin(); } + instr_iterator instr_end() { return Insts.end(); } + const_instr_iterator instr_end() const { return Insts.end(); } + reverse_instr_iterator instr_rbegin() { return Insts.rbegin(); } + const_reverse_instr_iterator instr_rbegin() const { return Insts.rbegin(); } + reverse_instr_iterator instr_rend () { return Insts.rend(); } + const_reverse_instr_iterator instr_rend () const { return Insts.rend(); } + + iterator begin() { return instr_begin(); } + const_iterator begin() const { return instr_begin(); } + iterator end () { return instr_end(); } + const_iterator end () const { return instr_end(); } + reverse_iterator rbegin() { return instr_rbegin(); } + const_reverse_iterator rbegin() const { return instr_rbegin(); } + reverse_iterator rend () { return instr_rend(); } + const_reverse_iterator rend () const { return instr_rend(); } + // Machine-CFG iterators typedef std::vector::iterator pred_iterator; @@ -219,10 +309,12 @@ public: bool livein_empty() const { return LiveIns.empty(); } /// getAlignment - Return alignment of the basic block. + /// The alignment is specified as log2(bytes). /// unsigned getAlignment() const { return Alignment; } /// setAlignment - Set alignment of the basic block. + /// The alignment is specified as log2(bytes). /// void setAlignment(unsigned Align) { Alignment = Align; } @@ -239,7 +331,7 @@ public: const MachineBasicBlock *getLandingPadSuccessor() const; // Code Layout methods. - + /// moveBefore/moveAfter - move 'this' block before or after the specified /// block. This only moves the block, it does not modify the CFG or adjust /// potential fall-throughs at the end of the block. @@ -259,6 +351,8 @@ public: /// parameter is stored in Weights list and it may be used by /// MachineBranchProbabilityInfo analysis to calculate branch probability. /// + /// Note that duplicate Machine CFG edges are not allowed. + /// void addSuccessor(MachineBasicBlock *succ, uint32_t weight = 0); /// removeSuccessor - Remove successor from the successors list of this @@ -286,7 +380,11 @@ public: /// in transferSuccessors, and update PHI operands in the successor blocks /// which refer to fromMBB to refer to this. void transferSuccessorsAndUpdatePHIs(MachineBasicBlock *fromMBB); - + + /// isPredecessor - Return true if the specified MBB is a predecessor of this + /// block. + bool isPredecessor(const MachineBasicBlock *MBB) const; + /// isSuccessor - Return true if the specified MBB is a successor of this /// block. bool isSuccessor(const MachineBasicBlock *MBB) const; @@ -304,7 +402,7 @@ public: /// branch to do so (e.g., a table jump). True is a conservative answer. bool canFallThrough(); - /// Returns a pointer to the first instructon in this block that is not a + /// Returns a pointer to the first instructon in this block that is not a /// PHINode instruction. When adding instruction to the beginning of the /// basic block, they should be added before the returned value, not before /// the first instruction, which might be PHI. @@ -320,18 +418,16 @@ public: /// instruction of this basic block. If a terminator does not exist, /// it returns end() iterator getFirstTerminator(); + const_iterator getFirstTerminator() const; - const_iterator getFirstTerminator() const { - return const_cast(this)->getFirstTerminator(); - } + /// getFirstInstrTerminator - Same getFirstTerminator but it ignores bundles + /// and return an instr_iterator instead. + instr_iterator getFirstInstrTerminator(); /// getLastNonDebugInstr - returns an iterator to the last non-debug /// instruction in the basic block, or end() iterator getLastNonDebugInstr(); - - const_iterator getLastNonDebugInstr() const { - return const_cast(this)->getLastNonDebugInstr(); - } + const_iterator getLastNonDebugInstr() const; /// SplitCriticalEdge - Split the critical edge from this block to the /// given successor block, and return the newly created block, or null @@ -344,38 +440,88 @@ public: void pop_front() { Insts.pop_front(); } void pop_back() { Insts.pop_back(); } void push_back(MachineInstr *MI) { Insts.push_back(MI); } + template - void insert(iterator I, IT S, IT E) { Insts.insert(I, S, E); } - iterator insert(iterator I, MachineInstr *M) { return Insts.insert(I, M); } - iterator insertAfter(iterator I, MachineInstr *M) { - return Insts.insertAfter(I, M); + void insert(instr_iterator I, IT S, IT E) { + Insts.insert(I, S, E); + } + instr_iterator insert(instr_iterator I, MachineInstr *M) { + return Insts.insert(I, M); + } + instr_iterator insertAfter(instr_iterator I, MachineInstr *M) { + return Insts.insertAfter(I, M); } - // erase - Remove the specified element or range from the instruction list. - // These functions delete any instructions removed. - // - iterator erase(iterator I) { return Insts.erase(I); } - iterator erase(iterator I, iterator E) { return Insts.erase(I, E); } - MachineInstr *remove(MachineInstr *I) { return Insts.remove(I); } - void clear() { Insts.clear(); } + template + void insert(iterator I, IT S, IT E) { + Insts.insert(I.getInstrIterator(), S, E); + } + iterator insert(iterator I, MachineInstr *M) { + return Insts.insert(I.getInstrIterator(), M); + } + iterator insertAfter(iterator I, MachineInstr *M) { + return Insts.insertAfter(I.getInstrIterator(), M); + } + + /// erase - Remove the specified element or range from the instruction list. + /// These functions delete any instructions removed. + /// + instr_iterator erase(instr_iterator I) { + return Insts.erase(I); + } + instr_iterator erase(instr_iterator I, instr_iterator E) { + return Insts.erase(I, E); + } + instr_iterator erase_instr(MachineInstr *I) { + instr_iterator MII(I); + return erase(MII); + } + + iterator erase(iterator I); + iterator erase(iterator I, iterator E) { + return Insts.erase(I.getInstrIterator(), E.getInstrIterator()); + } + iterator erase(MachineInstr *I) { + iterator MII(I); + return erase(MII); + } + + /// remove - Remove the instruction from the instruction list. This function + /// does not delete the instruction. WARNING: Note, if the specified + /// instruction is a bundle this function will remove all the bundled + /// instructions as well. It is up to the caller to keep a list of the + /// bundled instructions and re-insert them if desired. This function is + /// *not recommended* for manipulating instructions with bundles. Use + /// splice instead. + MachineInstr *remove(MachineInstr *I); + void clear() { + Insts.clear(); + } /// splice - Take an instruction from MBB 'Other' at the position From, /// and insert it into this MBB right before 'where'. - void splice(iterator where, MachineBasicBlock *Other, iterator From) { + void splice(instr_iterator where, MachineBasicBlock *Other, + instr_iterator From) { Insts.splice(where, Other->Insts, From); } + void splice(iterator where, MachineBasicBlock *Other, iterator From); /// splice - Take a block of instructions from MBB 'Other' in the range [From, /// To), and insert them into this MBB right before 'where'. + void splice(instr_iterator where, MachineBasicBlock *Other, instr_iterator From, + instr_iterator To) { + Insts.splice(where, Other->Insts, From, To); + } void splice(iterator where, MachineBasicBlock *Other, iterator From, iterator To) { - Insts.splice(where, Other->Insts, From, To); + Insts.splice(where.getInstrIterator(), Other->Insts, + From.getInstrIterator(), To.getInstrIterator()); } /// removeFromParent - This method unlinks 'this' from the containing /// function, and returns it, but does not delete it. MachineBasicBlock *removeFromParent(); - + /// eraseFromParent - This method unlinks 'this' from the containing /// function and deletes it. void eraseFromParent(); @@ -396,7 +542,32 @@ public: /// findDebugLoc - find the next valid DebugLoc starting at MBBI, skipping /// any DBG_VALUE instructions. Return UnknownLoc if there is none. - DebugLoc findDebugLoc(MachineBasicBlock::iterator &MBBI); + DebugLoc findDebugLoc(instr_iterator MBBI); + DebugLoc findDebugLoc(iterator MBBI) { + return findDebugLoc(MBBI.getInstrIterator()); + } + + /// Possible outcome of a register liveness query to computeRegisterLiveness() + enum LivenessQueryResult { + LQR_Live, ///< Register is known to be live. + LQR_OverlappingLive, ///< Register itself is not live, but some overlapping + ///< register is. + LQR_Dead, ///< Register is known to be dead. + LQR_Unknown ///< Register liveness not decidable from local + ///< neighborhood. + }; + + /// computeRegisterLiveness - Return whether (physical) register \c Reg + /// has been ined and not ed as of just before \c MI. + /// + /// Search is localised to a neighborhood of + /// \c Neighborhood instructions before (searching for defs or kills) and + /// Neighborhood instructions after (searching just for defs) MI. + /// + /// \c Reg must be a physical register. + LivenessQueryResult computeRegisterLiveness(const TargetRegisterInfo *TRI, + unsigned Reg, MachineInstr *MI, + unsigned Neighborhood=10); // Debugging methods. void dump() const; @@ -418,13 +589,14 @@ private: /// getWeightIterator - Return weight iterator corresponding to the I /// successor iterator. weight_iterator getWeightIterator(succ_iterator I); + const_weight_iterator getWeightIterator(const_succ_iterator I) const; friend class MachineBranchProbabilityInfo; /// getSuccWeight - Return weight of the edge from this block to MBB. This /// method should NOT be called directly, but by using getEdgeWeight method /// from MachineBranchProbabilityInfo class. - uint32_t getSuccWeight(MachineBasicBlock *succ); + uint32_t getSuccWeight(const_succ_iterator Succ) const; // Methods used to maintain doubly linked list of blocks...