136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines//===- InstIterator.h - Classes for inst iteration --------------*- C++ -*-===// 263b3afa98460ce38a1c48d3c44ef6edfdaf37b77Misha Brukman// 36fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// The LLVM Compiler Infrastructure 46fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details. 763b3afa98460ce38a1c48d3c44ef6edfdaf37b77Misha Brukman// 86fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell//===----------------------------------------------------------------------===// 9428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner// 10428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner// This file contains definitions of two iterators for iterating over the 112fbfdcffd3e0cf41422aaa6c526c37cb02b81341Chris Lattner// instructions in a function. This is effectively a wrapper around a two level 12428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner// iterator that can probably be genericized later. 13428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner// 14428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner// Note that this iterator gets invalidated any time that basic blocks or 15428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner// instructions are moved around. 16428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner// 17428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner//===----------------------------------------------------------------------===// 18428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner 1936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#ifndef LLVM_IR_INSTITERATOR_H 2036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#define LLVM_IR_INSTITERATOR_H 21428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner 220b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/BasicBlock.h" 230b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Function.h" 24428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner 25d0fde30ce850b78371fd1386338350591f9ff494Brian Gaekenamespace llvm { 26d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 2702dea4b355f3262a52dd9df0d24e59beb1bc6ec4Brian Gaeke// This class implements inst_begin() & inst_end() for 28428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner// inst_iterator and const_inst_iterator's. 29428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner// 30428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattnertemplate <class _BB_t, class _BB_i_t, class _BI_t, class _II_t> 31428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattnerclass InstIterator { 32428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner typedef _BB_t BBty; 33428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner typedef _BB_i_t BBIty; 34428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner typedef _BI_t BIty; 35428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner typedef _II_t IIty; 366ffe551f657c948d6a473a198ecbd1188bf9ce45Chris Lattner _BB_t *BBs; // BasicBlocksType 37428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner _BB_i_t BB; // BasicBlocksType::iterator 38428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner _BI_t BI; // BasicBlock::iterator 39428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattnerpublic: 40428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner typedef std::bidirectional_iterator_tag iterator_category; 41428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner typedef IIty value_type; 426ffe551f657c948d6a473a198ecbd1188bf9ce45Chris Lattner typedef signed difference_type; 436ffe551f657c948d6a473a198ecbd1188bf9ce45Chris Lattner typedef IIty* pointer; 446ffe551f657c948d6a473a198ecbd1188bf9ce45Chris Lattner typedef IIty& reference; 456ffe551f657c948d6a473a198ecbd1188bf9ce45Chris Lattner 466ffe551f657c948d6a473a198ecbd1188bf9ce45Chris Lattner // Default constructor 476ffe551f657c948d6a473a198ecbd1188bf9ce45Chris Lattner InstIterator() {} 48c6a4bf1251f3dc44d2164c0847ce0b19ed7409a2Chris Lattner 49c6a4bf1251f3dc44d2164c0847ce0b19ed7409a2Chris Lattner // Copy constructor... 50c6a4bf1251f3dc44d2164c0847ce0b19ed7409a2Chris Lattner template<typename A, typename B, typename C, typename D> 51c6a4bf1251f3dc44d2164c0847ce0b19ed7409a2Chris Lattner InstIterator(const InstIterator<A,B,C,D> &II) 52c6a4bf1251f3dc44d2164c0847ce0b19ed7409a2Chris Lattner : BBs(II.BBs), BB(II.BB), BI(II.BI) {} 53c6a4bf1251f3dc44d2164c0847ce0b19ed7409a2Chris Lattner 54c6a4bf1251f3dc44d2164c0847ce0b19ed7409a2Chris Lattner template<typename A, typename B, typename C, typename D> 55c6a4bf1251f3dc44d2164c0847ce0b19ed7409a2Chris Lattner InstIterator(InstIterator<A,B,C,D> &II) 56c6a4bf1251f3dc44d2164c0847ce0b19ed7409a2Chris Lattner : BBs(II.BBs), BB(II.BB), BI(II.BI) {} 5763b3afa98460ce38a1c48d3c44ef6edfdaf37b77Misha Brukman 5863b3afa98460ce38a1c48d3c44ef6edfdaf37b77Misha Brukman template<class M> InstIterator(M &m) 596ffe551f657c948d6a473a198ecbd1188bf9ce45Chris Lattner : BBs(&m.getBasicBlockList()), BB(BBs->begin()) { // begin ctor 606ffe551f657c948d6a473a198ecbd1188bf9ce45Chris Lattner if (BB != BBs->end()) { 617e70829632f82de15db187845666aaca6e04b792Chris Lattner BI = BB->begin(); 62428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner advanceToNextBB(); 63428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner } 64428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner } 65428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner 6663b3afa98460ce38a1c48d3c44ef6edfdaf37b77Misha Brukman template<class M> InstIterator(M &m, bool) 676ffe551f657c948d6a473a198ecbd1188bf9ce45Chris Lattner : BBs(&m.getBasicBlockList()), BB(BBs->end()) { // end ctor 68428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner } 69428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner 70428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner // Accessors to get at the underlying iterators... 71428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner inline BBIty &getBasicBlockIterator() { return BB; } 72428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner inline BIty &getInstructionIterator() { return BI; } 7363b3afa98460ce38a1c48d3c44ef6edfdaf37b77Misha Brukman 746ffe551f657c948d6a473a198ecbd1188bf9ce45Chris Lattner inline reference operator*() const { return *BI; } 756ffe551f657c948d6a473a198ecbd1188bf9ce45Chris Lattner inline pointer operator->() const { return &operator*(); } 7663b3afa98460ce38a1c48d3c44ef6edfdaf37b77Misha Brukman 7763b3afa98460ce38a1c48d3c44ef6edfdaf37b77Misha Brukman inline bool operator==(const InstIterator &y) const { 786ffe551f657c948d6a473a198ecbd1188bf9ce45Chris Lattner return BB == y.BB && (BB == BBs->end() || BI == y.BI); 79428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner } 8063b3afa98460ce38a1c48d3c44ef6edfdaf37b77Misha Brukman inline bool operator!=(const InstIterator& y) const { 81428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner return !operator==(y); 82428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner } 83428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner 8463b3afa98460ce38a1c48d3c44ef6edfdaf37b77Misha Brukman InstIterator& operator++() { 85428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner ++BI; 86428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner advanceToNextBB(); 8763b3afa98460ce38a1c48d3c44ef6edfdaf37b77Misha Brukman return *this; 88428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner } 8963b3afa98460ce38a1c48d3c44ef6edfdaf37b77Misha Brukman inline InstIterator operator++(int) { 9063b3afa98460ce38a1c48d3c44ef6edfdaf37b77Misha Brukman InstIterator tmp = *this; ++*this; return tmp; 91428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner } 9263b3afa98460ce38a1c48d3c44ef6edfdaf37b77Misha Brukman 9363b3afa98460ce38a1c48d3c44ef6edfdaf37b77Misha Brukman InstIterator& operator--() { 946ffe551f657c948d6a473a198ecbd1188bf9ce45Chris Lattner while (BB == BBs->end() || BI == BB->begin()) { 95428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner --BB; 967e70829632f82de15db187845666aaca6e04b792Chris Lattner BI = BB->end(); 97428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner } 98428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner --BI; 9963b3afa98460ce38a1c48d3c44ef6edfdaf37b77Misha Brukman return *this; 100428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner } 10163b3afa98460ce38a1c48d3c44ef6edfdaf37b77Misha Brukman inline InstIterator operator--(int) { 10263b3afa98460ce38a1c48d3c44ef6edfdaf37b77Misha Brukman InstIterator tmp = *this; --*this; return tmp; 103428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner } 104428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner 1056ffe551f657c948d6a473a198ecbd1188bf9ce45Chris Lattner inline bool atEnd() const { return BB == BBs->end(); } 106428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner 107428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattnerprivate: 108428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner inline void advanceToNextBB() { 109428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner // The only way that the II could be broken is if it is now pointing to 110428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner // the end() of the current BasicBlock and there are successor BBs. 1117e70829632f82de15db187845666aaca6e04b792Chris Lattner while (BI == BB->end()) { 112428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner ++BB; 1136ffe551f657c948d6a473a198ecbd1188bf9ce45Chris Lattner if (BB == BBs->end()) break; 1147e70829632f82de15db187845666aaca6e04b792Chris Lattner BI = BB->begin(); 115428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner } 116428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner } 117428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner}; 118428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner 119428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner 1207e70829632f82de15db187845666aaca6e04b792Chris Lattnertypedef InstIterator<iplist<BasicBlock>, 1212fbfdcffd3e0cf41422aaa6c526c37cb02b81341Chris Lattner Function::iterator, BasicBlock::iterator, 1226ffe551f657c948d6a473a198ecbd1188bf9ce45Chris Lattner Instruction> inst_iterator; 1237e70829632f82de15db187845666aaca6e04b792Chris Lattnertypedef InstIterator<const iplist<BasicBlock>, 12463b3afa98460ce38a1c48d3c44ef6edfdaf37b77Misha Brukman Function::const_iterator, 125428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner BasicBlock::const_iterator, 1266ffe551f657c948d6a473a198ecbd1188bf9ce45Chris Lattner const Instruction> const_inst_iterator; 127428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner 1282fbfdcffd3e0cf41422aaa6c526c37cb02b81341Chris Lattnerinline inst_iterator inst_begin(Function *F) { return inst_iterator(*F); } 1292fbfdcffd3e0cf41422aaa6c526c37cb02b81341Chris Lattnerinline inst_iterator inst_end(Function *F) { return inst_iterator(*F, true); } 1302fbfdcffd3e0cf41422aaa6c526c37cb02b81341Chris Lattnerinline const_inst_iterator inst_begin(const Function *F) { 1312fbfdcffd3e0cf41422aaa6c526c37cb02b81341Chris Lattner return const_inst_iterator(*F); 132428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner} 1332fbfdcffd3e0cf41422aaa6c526c37cb02b81341Chris Lattnerinline const_inst_iterator inst_end(const Function *F) { 1342fbfdcffd3e0cf41422aaa6c526c37cb02b81341Chris Lattner return const_inst_iterator(*F, true); 135428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner} 1367e70829632f82de15db187845666aaca6e04b792Chris Lattnerinline inst_iterator inst_begin(Function &F) { return inst_iterator(F); } 1377e70829632f82de15db187845666aaca6e04b792Chris Lattnerinline inst_iterator inst_end(Function &F) { return inst_iterator(F, true); } 1387e70829632f82de15db187845666aaca6e04b792Chris Lattnerinline const_inst_iterator inst_begin(const Function &F) { 1397e70829632f82de15db187845666aaca6e04b792Chris Lattner return const_inst_iterator(F); 1407e70829632f82de15db187845666aaca6e04b792Chris Lattner} 1417e70829632f82de15db187845666aaca6e04b792Chris Lattnerinline const_inst_iterator inst_end(const Function &F) { 1427e70829632f82de15db187845666aaca6e04b792Chris Lattner return const_inst_iterator(F, true); 1437e70829632f82de15db187845666aaca6e04b792Chris Lattner} 144428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner 145d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke} // End llvm namespace 146d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 147428039a6e11efa85e82cc29675e1c9c54130f2d6Chris Lattner#endif 148