1311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* 2311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Copyright (C) 2013 The Android Open Source Project 3311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * 4311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Licensed under the Apache License, Version 2.0 (the "License"); 5311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * you may not use this file except in compliance with the License. 6311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * You may obtain a copy of the License at 7311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * 8311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * http://www.apache.org/licenses/LICENSE-2.0 9311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * 10311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Unless required by applicable law or agreed to in writing, software 11311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * distributed under the License is distributed on an "AS IS" BASIS, 12311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * See the License for the specific language governing permissions and 14311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * limitations under the License. 15311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 16311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 17fc0e3219edc9a5bf81b166e82fd5db2796eb6a0dBrian Carlstrom#ifndef ART_COMPILER_DEX_DATAFLOW_ITERATOR_H_ 18fc0e3219edc9a5bf81b166e82fd5db2796eb6a0dBrian Carlstrom#define ART_COMPILER_DEX_DATAFLOW_ITERATOR_H_ 19311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 20311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee#include "compiler_ir.h" 21311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee#include "mir_graph.h" 22311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 23311ca169f4727d46a55bdc8dfa0059719fa72b65buzbeenamespace art { 24311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 250665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee /* 260665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee * This class supports iterating over lists of basic blocks in various 270665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee * interesting orders. Note that for efficiency, the visit orders have been pre-computed. 280665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee * The order itself will not change during the iteration. However, for some uses, 290665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee * auxiliary data associated with the basic blocks may be changed during the iteration, 3056c717860df2d71d66fb77aa77f29dd346e559d3buzbee * necessitating another pass over the list. If this behavior is required, use the 3156c717860df2d71d66fb77aa77f29dd346e559d3buzbee * "Repeating" variant. For the repeating variant, the caller must tell the iterator 3256c717860df2d71d66fb77aa77f29dd346e559d3buzbee * whether a change has been made that necessitates another pass. Note that calling Next(true) 3356c717860df2d71d66fb77aa77f29dd346e559d3buzbee * does not affect the iteration order or short-circuit the current pass - it simply tells 3456c717860df2d71d66fb77aa77f29dd346e559d3buzbee * the iterator that once it has finished walking through the block list it should reset and 3556c717860df2d71d66fb77aa77f29dd346e559d3buzbee * do another full pass through the list. 360665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee */ 376e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler /** 386e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @class DataflowIterator 396e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @brief The main iterator class, all other iterators derive of this one to define an iteration order. 406e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler */ 41311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee class DataflowIterator { 42311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee public: 432ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrom virtual ~DataflowIterator() {} 446e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler 456e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler /** 466e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @brief How many times have we repeated the iterator across the BasicBlocks? 476e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @return the number of iteration repetitions. 486e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler */ 491da1e2fceb0030b4b76b43510b1710a9613e0c2ebuzbee int32_t GetRepeatCount() { return repeats_; } 50311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 516e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler /** 526e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @brief Has the user of the iterator reported a change yet? 536e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @details Does not mean there was or not a change, it is only whether the user passed a true to the Next function call. 546e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @return whether the user of the iterator reported a change yet. 556e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler */ 566e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler int32_t GetChanged() { return changed_; } 576e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler 586e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler /** 596e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @brief Get the next BasicBlock depending on iteration order. 606e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @param had_change did the user of the iteration change the previous BasicBlock. 616e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @return the next BasicBlock following the iteration order, 0 if finished. 626e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler */ 636e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler virtual BasicBlock* Next(bool had_change = false) = 0; 646e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler 650665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee protected: 666e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler /** 676e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @param mir_graph the MIRGraph we are interested in. 686e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @param start_idx the first index we want to iterate across. 696e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @param end_idx the last index we want to iterate (not included). 706e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler */ 710d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DataflowIterator(MIRGraph* mir_graph, int32_t start_idx, int32_t end_idx) 720665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee : mir_graph_(mir_graph), 730665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee start_idx_(start_idx), 740665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee end_idx_(end_idx), 75e7a5b7d3fcc3af100fec13af057eecaff1037f2cIan Rogers block_id_list_(NULL), 76e7a5b7d3fcc3af100fec13af057eecaff1037f2cIan Rogers idx_(0), 771da1e2fceb0030b4b76b43510b1710a9613e0c2ebuzbee repeats_(0), 78e7a5b7d3fcc3af100fec13af057eecaff1037f2cIan Rogers changed_(false) {} 790665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee 806e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler /** 816e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @brief Get the next BasicBlock iterating forward. 826e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @return the next BasicBlock iterating forward. 836e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler */ 8456c717860df2d71d66fb77aa77f29dd346e559d3buzbee virtual BasicBlock* ForwardSingleNext() ALWAYS_INLINE; 856e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler 866e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler /** 876e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @brief Get the next BasicBlock iterating backward. 886e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @return the next BasicBlock iterating backward. 896e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler */ 9056c717860df2d71d66fb77aa77f29dd346e559d3buzbee virtual BasicBlock* ReverseSingleNext() ALWAYS_INLINE; 910665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee 926e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler /** 936e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @brief Get the next BasicBlock iterating forward, restart if a BasicBlock was reported changed during the last iteration. 946e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @return the next BasicBlock iterating forward, with chance of repeating the iteration. 956e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler */ 966e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler virtual BasicBlock* ForwardRepeatNext() ALWAYS_INLINE; 971da1e2fceb0030b4b76b43510b1710a9613e0c2ebuzbee 986e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler /** 996e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @brief Get the next BasicBlock iterating backward, restart if a BasicBlock was reported changed during the last iteration. 1006e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @return the next BasicBlock iterating backward, with chance of repeating the iteration. 1016e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler */ 1026e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler virtual BasicBlock* ReverseRepeatNext() ALWAYS_INLINE; 1036e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler 1046e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler MIRGraph* const mir_graph_; /**< @brief the MIRGraph */ 1056e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler const int32_t start_idx_; /**< @brief the start index for the iteration */ 1066e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler const int32_t end_idx_; /**< @brief the last index for the iteration */ 1076e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler GrowableArray<BasicBlockId>* block_id_list_; /**< @brief the list of BasicBlocks we want to iterate on */ 1086e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler int32_t idx_; /**< @brief Current index for the iterator */ 1096e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler int32_t repeats_; /**< @brief Number of repeats over the iteration */ 1106e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler bool changed_; /**< @brief Has something changed during the current iteration? */ 1117934ac288acfb2552bb0b06ec1f61e5820d924a4Brian Carlstrom }; // DataflowIterator 1120665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee 1136e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler /** 1146e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @class PreOrderDfsIterator 1156e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @brief Used to perform a Pre-order Depth-First-Search Iteration of a MIRGraph. 1166e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler */ 11756c717860df2d71d66fb77aa77f29dd346e559d3buzbee class PreOrderDfsIterator : public DataflowIterator { 1180665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee public: 1196e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler /** 1206e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @brief The constructor, using all of the reachable blocks of the MIRGraph. 1216e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @param mir_graph The MIRGraph considered. 1226e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler */ 12356c717860df2d71d66fb77aa77f29dd346e559d3buzbee explicit PreOrderDfsIterator(MIRGraph* mir_graph) 12456c717860df2d71d66fb77aa77f29dd346e559d3buzbee : DataflowIterator(mir_graph, 0, mir_graph->GetNumReachableBlocks()) { 1256e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler // Extra setup for the PreOrderDfsIterator. 1260665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee idx_ = start_idx_; 1270665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee block_id_list_ = mir_graph->GetDfsOrder(); 1280665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee } 12956c717860df2d71d66fb77aa77f29dd346e559d3buzbee 1306e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler /** 1316e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @brief Get the next BasicBlock depending on iteration order. 1326e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @param had_change did the user of the iteration change the previous BasicBlock. 1336e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @return the next BasicBlock following the iteration order, 0 if finished. 1346e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler */ 1356e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler virtual BasicBlock* Next(bool had_change = false) { 1366e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler // Update changed: if had_changed is true, we remember it for the whole iteration. 1376e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler changed_ |= had_change; 1386e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler 13956c717860df2d71d66fb77aa77f29dd346e559d3buzbee return ForwardSingleNext(); 14056c717860df2d71d66fb77aa77f29dd346e559d3buzbee } 1410665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee }; 1420665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee 1436e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler /** 1446e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @class RepeatingPreOrderDfsIterator 1456e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @brief Used to perform a Repeating Pre-order Depth-First-Search Iteration of a MIRGraph. 1466e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @details If there is a change during an iteration, the iteration starts over at the end of the iteration. 1476e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler */ 14856c717860df2d71d66fb77aa77f29dd346e559d3buzbee class RepeatingPreOrderDfsIterator : public DataflowIterator { 1490665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee public: 1506e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler /** 1516e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @brief The constructor, using all of the reachable blocks of the MIRGraph. 1526e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @param mir_graph The MIRGraph considered. 1536e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler */ 15456c717860df2d71d66fb77aa77f29dd346e559d3buzbee explicit RepeatingPreOrderDfsIterator(MIRGraph* mir_graph) 15556c717860df2d71d66fb77aa77f29dd346e559d3buzbee : DataflowIterator(mir_graph, 0, mir_graph->GetNumReachableBlocks()) { 1566e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler // Extra setup for the RepeatingPreOrderDfsIterator. 1570665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee idx_ = start_idx_; 1580665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee block_id_list_ = mir_graph->GetDfsOrder(); 1590665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee } 16056c717860df2d71d66fb77aa77f29dd346e559d3buzbee 1616e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler /** 1626e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @brief Get the next BasicBlock depending on iteration order. 1636e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @param had_change did the user of the iteration change the previous BasicBlock. 1646e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @return the next BasicBlock following the iteration order, 0 if finished. 1656e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler */ 1666e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler virtual BasicBlock* Next(bool had_change = false) { 1676e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler // Update changed: if had_changed is true, we remember it for the whole iteration. 1686e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler changed_ |= had_change; 1696e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler 1706e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler return ForwardRepeatNext(); 17156c717860df2d71d66fb77aa77f29dd346e559d3buzbee } 1720665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee }; 1730665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee 1746e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler /** 1756e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @class RepeatingPostOrderDfsIterator 1766e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @brief Used to perform a Repeating Post-order Depth-First-Search Iteration of a MIRGraph. 1776e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @details If there is a change during an iteration, the iteration starts over at the end of the iteration. 1786e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler */ 17956c717860df2d71d66fb77aa77f29dd346e559d3buzbee class RepeatingPostOrderDfsIterator : public DataflowIterator { 1800665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee public: 1816e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler /** 1826e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @brief The constructor, using all of the reachable blocks of the MIRGraph. 1836e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @param mir_graph The MIRGraph considered. 1846e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler */ 18556c717860df2d71d66fb77aa77f29dd346e559d3buzbee explicit RepeatingPostOrderDfsIterator(MIRGraph* mir_graph) 18656c717860df2d71d66fb77aa77f29dd346e559d3buzbee : DataflowIterator(mir_graph, 0, mir_graph->GetNumReachableBlocks()) { 1876e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler // Extra setup for the RepeatingPostOrderDfsIterator. 1880665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee idx_ = start_idx_; 1890665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee block_id_list_ = mir_graph->GetDfsPostOrder(); 1900665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee } 19156c717860df2d71d66fb77aa77f29dd346e559d3buzbee 1926e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler /** 1936e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @brief Get the next BasicBlock depending on iteration order. 1946e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @param had_change did the user of the iteration change the previous BasicBlock. 1956e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @return the next BasicBlock following the iteration order, 0 if finished. 1966e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler */ 1976e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler virtual BasicBlock* Next(bool had_change = false) { 1986e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler // Update changed: if had_changed is true, we remember it for the whole iteration. 1996e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler changed_ |= had_change; 2006e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler 2016e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler return ForwardRepeatNext(); 20256c717860df2d71d66fb77aa77f29dd346e559d3buzbee } 2030665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee }; 2040665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee 2056e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler /** 2066e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @class ReversePostOrderDfsIterator 2076e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @brief Used to perform a Reverse Post-order Depth-First-Search Iteration of a MIRGraph. 2086e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler */ 2090665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee class ReversePostOrderDfsIterator : public DataflowIterator { 2100665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee public: 2116e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler /** 2126e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @brief The constructor, using all of the reachable blocks of the MIRGraph. 2136e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @param mir_graph The MIRGraph considered. 2146e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler */ 21556c717860df2d71d66fb77aa77f29dd346e559d3buzbee explicit ReversePostOrderDfsIterator(MIRGraph* mir_graph) 21656c717860df2d71d66fb77aa77f29dd346e559d3buzbee : DataflowIterator(mir_graph, mir_graph->GetNumReachableBlocks() -1, 0) { 2176e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler // Extra setup for the ReversePostOrderDfsIterator. 21856c717860df2d71d66fb77aa77f29dd346e559d3buzbee idx_ = start_idx_; 21956c717860df2d71d66fb77aa77f29dd346e559d3buzbee block_id_list_ = mir_graph->GetDfsPostOrder(); 22056c717860df2d71d66fb77aa77f29dd346e559d3buzbee } 22156c717860df2d71d66fb77aa77f29dd346e559d3buzbee 2226e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler /** 2236e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @brief Get the next BasicBlock depending on iteration order. 2246e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @param had_change did the user of the iteration change the previous BasicBlock. 2256e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @return the next BasicBlock following the iteration order, 0 if finished. 2266e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler */ 2276e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler virtual BasicBlock* Next(bool had_change = false) { 2286e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler // Update changed: if had_changed is true, we remember it for the whole iteration. 2296e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler changed_ |= had_change; 2306e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler 23156c717860df2d71d66fb77aa77f29dd346e559d3buzbee return ReverseSingleNext(); 23256c717860df2d71d66fb77aa77f29dd346e559d3buzbee } 23356c717860df2d71d66fb77aa77f29dd346e559d3buzbee }; 23456c717860df2d71d66fb77aa77f29dd346e559d3buzbee 2356e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler /** 2366e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @class ReversePostOrderDfsIterator 2376e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @brief Used to perform a Repeating Reverse Post-order Depth-First-Search Iteration of a MIRGraph. 2386e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @details If there is a change during an iteration, the iteration starts over at the end of the iteration. 2396e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler */ 24056c717860df2d71d66fb77aa77f29dd346e559d3buzbee class RepeatingReversePostOrderDfsIterator : public DataflowIterator { 24156c717860df2d71d66fb77aa77f29dd346e559d3buzbee public: 2426e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler /** 2436e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @brief The constructor, using all of the reachable blocks of the MIRGraph. 2446e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @param mir_graph The MIRGraph considered. 2456e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler */ 24656c717860df2d71d66fb77aa77f29dd346e559d3buzbee explicit RepeatingReversePostOrderDfsIterator(MIRGraph* mir_graph) 24756c717860df2d71d66fb77aa77f29dd346e559d3buzbee : DataflowIterator(mir_graph, mir_graph->GetNumReachableBlocks() -1, 0) { 2486e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler // Extra setup for the RepeatingReversePostOrderDfsIterator 2490665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee idx_ = start_idx_; 2500665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee block_id_list_ = mir_graph->GetDfsPostOrder(); 2510665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee } 25256c717860df2d71d66fb77aa77f29dd346e559d3buzbee 2536e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler /** 2546e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @brief Get the next BasicBlock depending on iteration order. 2556e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @param had_change did the user of the iteration change the previous BasicBlock. 2566e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @return the next BasicBlock following the iteration order, 0 if finished. 2576e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler */ 2586e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler virtual BasicBlock* Next(bool had_change = false) { 2596e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler // Update changed: if had_changed is true, we remember it for the whole iteration. 2606e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler changed_ |= had_change; 2616e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler 2626e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler return ReverseRepeatNext(); 26356c717860df2d71d66fb77aa77f29dd346e559d3buzbee } 2640665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee }; 2650665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee 2666e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler /** 2676e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @class PostOrderDOMIterator 2686e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @brief Used to perform a Post-order Domination Iteration of a MIRGraph. 2696e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler */ 2700665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee class PostOrderDOMIterator : public DataflowIterator { 2710665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee public: 2726e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler /** 2736e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @brief The constructor, using all of the reachable blocks of the MIRGraph. 2746e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @param mir_graph The MIRGraph considered. 2756e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler */ 27656c717860df2d71d66fb77aa77f29dd346e559d3buzbee explicit PostOrderDOMIterator(MIRGraph* mir_graph) 27756c717860df2d71d66fb77aa77f29dd346e559d3buzbee : DataflowIterator(mir_graph, 0, mir_graph->GetNumReachableBlocks()) { 2786e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler // Extra setup for thePostOrderDOMIterator. 2790665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee idx_ = start_idx_; 2800665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee block_id_list_ = mir_graph->GetDomPostOrder(); 2810665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee } 28256c717860df2d71d66fb77aa77f29dd346e559d3buzbee 2836e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler /** 2846e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @brief Get the next BasicBlock depending on iteration order. 2856e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @param had_change did the user of the iteration change the previous BasicBlock. 2866e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @return the next BasicBlock following the iteration order, 0 if finished. 2876e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler */ 2886e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler virtual BasicBlock* Next(bool had_change = false) { 2896e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler // Update changed: if had_changed is true, we remember it for the whole iteration. 2906e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler changed_ |= had_change; 2916e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler 29256c717860df2d71d66fb77aa77f29dd346e559d3buzbee return ForwardSingleNext(); 29356c717860df2d71d66fb77aa77f29dd346e559d3buzbee } 2940665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee }; 2950665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee 2966e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler /** 2976e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @class AllNodesIterator 2986e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @brief Used to perform an iteration on all the BasicBlocks a MIRGraph. 2996e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler */ 3000665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee class AllNodesIterator : public DataflowIterator { 3010665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee public: 3026e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler /** 3036e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @brief The constructor, using all of the reachable blocks of the MIRGraph. 3046e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @param mir_graph The MIRGraph considered. 3056e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler */ 30656c717860df2d71d66fb77aa77f29dd346e559d3buzbee explicit AllNodesIterator(MIRGraph* mir_graph) 30775ba13f244098f42584637b8fd3f6d74d2fc291aVladimir Marko : DataflowIterator(mir_graph, 0, 0), 30875ba13f244098f42584637b8fd3f6d74d2fc291aVladimir Marko all_nodes_iterator_(mir_graph->GetBlockList()) { 309862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee } 310862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 3116e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler /** 3126e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @brief Resetting the iterator. 3136e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler */ 3148d3a117b374352a1853fae9b7306afeaaa9e3b91Ian Rogers void Reset() { 31575ba13f244098f42584637b8fd3f6d74d2fc291aVladimir Marko all_nodes_iterator_.Reset(); 3160665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee } 3170665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee 3186e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler /** 3196e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @brief Get the next BasicBlock depending on iteration order. 3206e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @param had_change did the user of the iteration change the previous BasicBlock. 3216e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler * @return the next BasicBlock following the iteration order, 0 if finished. 3226e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler */ 3236e3cb66b3885c5b9ed31bf55e2d2f8594c4f840dJean Christophe Beyler virtual BasicBlock* Next(bool had_change = false) ALWAYS_INLINE; 324862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 325862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee private: 32675ba13f244098f42584637b8fd3f6d74d2fc291aVladimir Marko GrowableArray<BasicBlock*>::Iterator all_nodes_iterator_; /**< @brief The list of all the nodes */ 3270665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee }; 3280665fe0966d9591c5378a5d598c6eb6cab67e74abuzbee 32944e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler /** 33044e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler * @class TopologicalSortIterator 33144e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler * @brief Used to perform a Topological Sort Iteration of a MIRGraph. 33244e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler */ 33344e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler class TopologicalSortIterator : public DataflowIterator { 33444e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler public: 33544e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler /** 33644e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler * @brief The constructor, using all of the reachable blocks of the MIRGraph. 33744e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler * @param mir_graph The MIRGraph considered. 33844e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler */ 33944e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler explicit TopologicalSortIterator(MIRGraph* mir_graph) 340622bdbe6c295b08d06dfaa8d896b9ca152aa899cVladimir Marko : DataflowIterator(mir_graph, 0, mir_graph->GetTopologicalSortOrder()->Size()) { 34144e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler // Extra setup for TopologicalSortIterator. 34244e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler idx_ = start_idx_; 34344e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler block_id_list_ = mir_graph->GetTopologicalSortOrder(); 34444e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler } 34544e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler 34644e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler /** 34744e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler * @brief Get the next BasicBlock depending on iteration order. 34844e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler * @param had_change did the user of the iteration change the previous BasicBlock. 34944e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler * @return the next BasicBlock following the iteration order, 0 if finished. 35044e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler */ 35144e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler virtual BasicBlock* Next(bool had_change = false) { 35244e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler // Update changed: if had_changed is true, we remember it for the whole iteration. 35344e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler changed_ |= had_change; 35444e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler 35544e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler return ForwardSingleNext(); 35644e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler } 35744e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler }; 35844e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler 35944e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler /** 36044e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler * @class RepeatingTopologicalSortIterator 36144e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler * @brief Used to perform a Topological Sort Iteration of a MIRGraph. 36244e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler * @details If there is a change during an iteration, the iteration starts over at the end of the 36344e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler * iteration. 36444e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler */ 36544e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler class RepeatingTopologicalSortIterator : public DataflowIterator { 36644e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler public: 36744e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler /** 36844e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler * @brief The constructor, using all of the reachable blocks of the MIRGraph. 36944e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler * @param mir_graph The MIRGraph considered. 37044e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler */ 37144e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler explicit RepeatingTopologicalSortIterator(MIRGraph* mir_graph) 372622bdbe6c295b08d06dfaa8d896b9ca152aa899cVladimir Marko : DataflowIterator(mir_graph, 0, mir_graph->GetTopologicalSortOrder()->Size()) { 37344e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler // Extra setup for RepeatingTopologicalSortIterator. 37444e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler idx_ = start_idx_; 37544e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler block_id_list_ = mir_graph->GetTopologicalSortOrder(); 37644e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler } 37744e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler 37844e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler /** 37944e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler * @brief Get the next BasicBlock depending on iteration order. 38044e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler * @param had_change did the user of the iteration change the previous BasicBlock. 38144e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler * @return the next BasicBlock following the iteration order, 0 if finished. 38244e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler */ 38344e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler virtual BasicBlock* Next(bool had_change = false) { 38444e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler // Update changed: if had_changed is true, we remember it for the whole iteration. 38544e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler changed_ |= had_change; 38644e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler 38744e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler return ForwardRepeatNext(); 38844e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler } 38944e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler }; 39044e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler 39155fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko /** 39255fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko * @class LoopRepeatingTopologicalSortIterator 39355fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko * @brief Used to perform a Topological Sort Iteration of a MIRGraph, repeating loops as needed. 39455fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko * @details The iterator uses the visited flags to keep track of the blocks that need 39555fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko * recalculation and keeps a stack of loop heads in the MIRGraph. At the end of the loop 39655fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko * it returns back to the loop head if it needs to be recalculated. Due to the use of 39755fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko * the visited flags and the loop head stack in the MIRGraph, it's not possible to use 39855fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko * two iterators at the same time or modify this data during iteration (though inspection 39955fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko * of this data is allowed and sometimes even expected). 40055fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko * 40155fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko * NOTE: This iterator is not suitable for passes that need to propagate changes to 40255fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko * predecessors, such as type inferrence. 40355fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko */ 40455fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko class LoopRepeatingTopologicalSortIterator : public DataflowIterator { 40555fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko public: 40655fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko /** 40755fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko * @brief The constructor, using all of the reachable blocks of the MIRGraph. 40855fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko * @param mir_graph The MIRGraph considered. 40955fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko */ 41055fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko explicit LoopRepeatingTopologicalSortIterator(MIRGraph* mir_graph) 41155fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko : DataflowIterator(mir_graph, 0, mir_graph->GetTopologicalSortOrder()->Size()), 41255fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko loop_ends_(mir_graph->GetTopologicalSortOrderLoopEnds()), 41355fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko loop_head_stack_(mir_graph_->GetTopologicalSortOrderLoopHeadStack()) { 41455fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko // Extra setup for RepeatingTopologicalSortIterator. 41555fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko idx_ = start_idx_; 41655fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko block_id_list_ = mir_graph->GetTopologicalSortOrder(); 41755fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko // Clear visited flags and check that the loop head stack is empty. 41855fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko mir_graph->ClearAllVisitedFlags(); 41955fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko DCHECK_EQ(loop_head_stack_->Size(), 0u); 42055fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko } 42155fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko 42255fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko ~LoopRepeatingTopologicalSortIterator() { 42355fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko DCHECK_EQ(loop_head_stack_->Size(), 0u); 42455fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko } 42555fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko 42655fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko /** 42755fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko * @brief Get the next BasicBlock depending on iteration order. 42855fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko * @param had_change did the user of the iteration change the previous BasicBlock. 42955fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko * @return the next BasicBlock following the iteration order, 0 if finished. 43055fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko */ 43155fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko virtual BasicBlock* Next(bool had_change = false) OVERRIDE; 43255fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko 43355fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko private: 43455fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko const GrowableArray<BasicBlockId>* const loop_ends_; 43555fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko GrowableArray<std::pair<uint16_t, bool>>* const loop_head_stack_; 43655fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko }; 43744e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler 438311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} // namespace art 439311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 440fc0e3219edc9a5bf81b166e82fd5db2796eb6a0dBrian Carlstrom#endif // ART_COMPILER_DEX_DATAFLOW_ITERATOR_H_ 441