compiler/optimizing/execution_subgraph.cc

/*
 * Copyright (C) 2020 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include "execution_subgraph.h"

#include <algorithm>
#include <unordered_set>

#include "android-base/macros.h"
#include "base/arena_allocator.h"
#include "base/arena_bit_vector.h"
#include "base/globals.h"
#include "base/scoped_arena_allocator.h"
#include "nodes.h"

namespace art {

ExecutionSubgraph::ExecutionSubgraph(HGraph* graph,
                                     bool analysis_possible,
                                     ScopedArenaAllocator* allocator)
    : graph_(graph),
      allocator_(allocator),
      allowed_successors_(analysis_possible ? graph_->GetBlocks().size() : 0,
                          ~(std::bitset<kMaxFilterableSuccessors> {}),
                          allocator_->Adapter(kArenaAllocLSA)),
      unreachable_blocks_(
          allocator_, analysis_possible ? graph_->GetBlocks().size() : 0, false, kArenaAllocLSA),
      valid_(analysis_possible),
      needs_prune_(false),
      finalized_(false) {
  if (valid_) {
    DCHECK(std::all_of(graph->GetBlocks().begin(), graph->GetBlocks().end(), [](HBasicBlock* it) {
      return it == nullptr || it->GetSuccessors().size() <= kMaxFilterableSuccessors;
    }));
  }
}

void ExecutionSubgraph::RemoveBlock(const HBasicBlock* to_remove) {
  if (!valid_) {
    return;
  }
  uint32_t id = to_remove->GetBlockId();
  if (unreachable_blocks_.IsBitSet(id)) {
    if (kIsDebugBuild) {
      // This isn't really needed but it's good to have this so it functions as
      // a DCHECK that we always call Prune after removing any block.
      needs_prune_ = true;
    }
    return;
  }
  unreachable_blocks_.SetBit(id);
  for (HBasicBlock* pred : to_remove->GetPredecessors()) {
    std::bitset<kMaxFilterableSuccessors> allowed_successors {};
    // ZipCount iterates over both the successors and the index of them at the same time.
    for (auto [succ, i] : ZipCount(MakeIterationRange(pred->GetSuccessors()))) {
      if (succ != to_remove) {
        allowed_successors.set(i);
      }
    }
    LimitBlockSuccessors(pred, allowed_successors);
  }
}

// Removes sink nodes.
void ExecutionSubgraph::Prune() {
  if (UNLIKELY(!valid_)) {
    return;
  }
  needs_prune_ = false;
  // This is the record of the edges that were both (1) explored and (2) reached
  // the exit node.
  {
    // Allocator for temporary values.
    ScopedArenaAllocator temporaries(graph_->GetArenaStack());
    ScopedArenaVector<std::bitset<kMaxFilterableSuccessors>> results(
        graph_->GetBlocks().size(), temporaries.Adapter(kArenaAllocLSA));
    unreachable_blocks_.ClearAllBits();
    // TODO We should support infinite loops as well.
    if (UNLIKELY(graph_->GetExitBlock() == nullptr)) {
      // Infinite loop
      valid_ = false;
      return;
    }
    // Fills up the 'results' map with what we need to add to update
    // allowed_successors in order to prune sink nodes.
    bool start_reaches_end = false;
    // This is basically a DFS of the graph with some edges skipped.
    {
      const size_t num_blocks = graph_->GetBlocks().size();
      constexpr ssize_t kUnvisitedSuccIdx = -1;
      ArenaBitVector visiting(&temporaries, num_blocks, false, kArenaAllocLSA);
      // How many of the successors of each block we have already examined. This
      // has three states.
      // (1) kUnvisitedSuccIdx: we have not examined any edges,
      // (2) 0 <= val < # of successors: we have examined 'val' successors/are
      // currently examining successors_[val],
      // (3) kMaxFilterableSuccessors: We have examined all of the successors of
      // the block (the 'result' is final).
      ScopedArenaVector<ssize_t> last_succ_seen(
          num_blocks, kUnvisitedSuccIdx, temporaries.Adapter(kArenaAllocLSA));
      // A stack of which blocks we are visiting in this DFS traversal. Does not
      // include the current-block. Used with last_succ_seen to figure out which
      // bits to set if we find a path to the end/loop.
      ScopedArenaVector<uint32_t> current_path(temporaries.Adapter(kArenaAllocLSA));
      // Just ensure we have enough space. The allocator will be cleared shortly
      // anyway so this is fast.
      current_path.reserve(num_blocks);
      // Current block we are examining. Modified only by 'push_block' and 'pop_block'
      const HBasicBlock* cur_block = graph_->GetEntryBlock();
      // Used to note a recur where we will start iterating on 'blk' and save
      // where we are. We must 'continue' immediately after this.
      auto push_block = [&](const HBasicBlock* blk) {
        DCHECK(std::find(current_path.cbegin(), current_path.cend(), cur_block->GetBlockId()) ==
               current_path.end());
        if (kIsDebugBuild) {
          std::for_each(current_path.cbegin(), current_path.cend(), [&](auto id) {
            DCHECK_GT(last_succ_seen[id], kUnvisitedSuccIdx) << id;
            DCHECK_LT(last_succ_seen[id], static_cast<ssize_t>(kMaxFilterableSuccessors)) << id;
          });
        }
        current_path.push_back(cur_block->GetBlockId());
        visiting.SetBit(cur_block->GetBlockId());
        cur_block = blk;
      };
      // Used to note that we have fully explored a block and should return back
      // up. Sets cur_block appropriately. We must 'continue' immediately after
      // calling this.
      auto pop_block = [&]() {
        if (UNLIKELY(current_path.empty())) {
          // Should only happen if entry-blocks successors are exhausted.
          DCHECK_GE(last_succ_seen[graph_->GetEntryBlock()->GetBlockId()],
                    static_cast<ssize_t>(graph_->GetEntryBlock()->GetSuccessors().size()));
          cur_block = nullptr;
        } else {
          const HBasicBlock* last = graph_->GetBlocks()[current_path.back()];
          visiting.ClearBit(current_path.back());
          current_path.pop_back();
          cur_block = last;
        }
      };
      // Mark the current path as a path to the end. This is in contrast to paths
      // that end in (eg) removed blocks.
      auto propagate_true = [&]() {
        for (uint32_t id : current_path) {
          DCHECK_GT(last_succ_seen[id], kUnvisitedSuccIdx);
          DCHECK_LT(last_succ_seen[id], static_cast<ssize_t>(kMaxFilterableSuccessors));
          results[id].set(last_succ_seen[id]);
        }
      };
      ssize_t num_entry_succ = graph_->GetEntryBlock()->GetSuccessors().size();
      // As long as the entry-block has not explored all successors we still have
      // work to do.
      const uint32_t entry_block_id = graph_->GetEntryBlock()->GetBlockId();
      while (num_entry_succ > last_succ_seen[entry_block_id]) {
        DCHECK(cur_block != nullptr);
        uint32_t id = cur_block->GetBlockId();
        DCHECK((current_path.empty() && cur_block == graph_->GetEntryBlock()) ||
               current_path.front() == graph_->GetEntryBlock()->GetBlockId())
            << "current path size: " << current_path.size()
            << " cur_block id: " << cur_block->GetBlockId() << " entry id "
            << graph_->GetEntryBlock()->GetBlockId();
        DCHECK(!visiting.IsBitSet(id))
            << "Somehow ended up in a loop! This should have been caught before now! " << id;
        std::bitset<kMaxFilterableSuccessors>& result = results[id];
        if (cur_block == graph_->GetExitBlock()) {
          start_reaches_end = true;
          propagate_true();
          pop_block();
          continue;
        } else if (last_succ_seen[id] == kMaxFilterableSuccessors) {
          // Already fully explored.
          if (result.any()) {
            propagate_true();
          }
          pop_block();
          continue;
        }
        // NB This is a pointer. Modifications modify the last_succ_seen.
        ssize_t* cur_succ = &last_succ_seen[id];
        std::bitset<kMaxFilterableSuccessors> succ_bitmap = GetAllowedSuccessors(cur_block);
        // Get next successor allowed.
        while (++(*cur_succ) < static_cast<ssize_t>(kMaxFilterableSuccessors) &&
               !succ_bitmap.test(*cur_succ)) {
          DCHECK_GE(*cur_succ, 0);
        }
        if (*cur_succ >= static_cast<ssize_t>(cur_block->GetSuccessors().size())) {
          // No more successors. Mark that we've checked everything. Later visits
          // to this node can use the existing data.
          DCHECK_LE(*cur_succ, static_cast<ssize_t>(kMaxFilterableSuccessors));
          *cur_succ = kMaxFilterableSuccessors;
          pop_block();
          continue;
        }
        const HBasicBlock* nxt = cur_block->GetSuccessors()[*cur_succ];
        DCHECK(nxt != nullptr) << "id: " << *cur_succ
                               << " max: " << cur_block->GetSuccessors().size();
        if (visiting.IsBitSet(nxt->GetBlockId())) {
          // This is a loop. Mark it and continue on. Mark allowed-successor on
          // this block's results as well.
          result.set(*cur_succ);
          propagate_true();
        } else {
          // Not a loop yet. Recur.
          push_block(nxt);
        }
      }
    }
    // If we can't reach the end then there is no path through the graph without
    // hitting excluded blocks
    if (UNLIKELY(!start_reaches_end)) {
      valid_ = false;
      return;
    }
    // Mark blocks we didn't see in the ReachesEnd flood-fill
    for (const HBasicBlock* blk : graph_->GetBlocks()) {
      if (blk != nullptr &&
          results[blk->GetBlockId()].none() &&
          blk != graph_->GetExitBlock() &&
          blk != graph_->GetEntryBlock()) {
        // We never visited this block, must be unreachable.
        unreachable_blocks_.SetBit(blk->GetBlockId());
      }
    }
    // write the new data.
    memcpy(allowed_successors_.data(),
           results.data(),
           results.size() * sizeof(std::bitset<kMaxFilterableSuccessors>));
  }
  RecalculateExcludedCohort();
}

void ExecutionSubgraph::RemoveConcavity() {
  if (UNLIKELY(!valid_)) {
    return;
  }
  DCHECK(!needs_prune_);
  for (const HBasicBlock* blk : graph_->GetBlocks()) {
    if (blk == nullptr || unreachable_blocks_.IsBitSet(blk->GetBlockId())) {
      continue;
    }
    uint32_t blkid = blk->GetBlockId();
    if (std::any_of(unreachable_blocks_.Indexes().begin(),
                    unreachable_blocks_.Indexes().end(),
                    [&](uint32_t skipped) { return graph_->PathBetween(skipped, blkid); }) &&
        std::any_of(unreachable_blocks_.Indexes().begin(),
                    unreachable_blocks_.Indexes().end(),
                    [&](uint32_t skipped) { return graph_->PathBetween(blkid, skipped); })) {
      RemoveBlock(blk);
    }
  }
  Prune();
}

void ExecutionSubgraph::RecalculateExcludedCohort() {
  DCHECK(!needs_prune_);
  excluded_list_.emplace(allocator_->Adapter(kArenaAllocLSA));
  ScopedArenaVector<ExcludedCohort>& res = excluded_list_.value();
  // Make a copy of unreachable_blocks_;
  ArenaBitVector unreachable(allocator_, graph_->GetBlocks().size(), false, kArenaAllocLSA);
  unreachable.Copy(&unreachable_blocks_);
  // Split cohorts with union-find
  while (unreachable.IsAnyBitSet()) {
    res.emplace_back(allocator_, graph_);
    ExcludedCohort& cohort = res.back();
    // We don't allocate except for the queue beyond here so create another arena to save memory.
    ScopedArenaAllocator alloc(graph_->GetArenaStack());
    ScopedArenaQueue<const HBasicBlock*> worklist(alloc.Adapter(kArenaAllocLSA));
    // Select an arbitrary node
    const HBasicBlock* first = graph_->GetBlocks()[unreachable.GetHighestBitSet()];
    worklist.push(first);
    do {
      // Flood-fill both forwards and backwards.
      const HBasicBlock* cur = worklist.front();
      worklist.pop();
      if (!unreachable.IsBitSet(cur->GetBlockId())) {
        // Already visited or reachable somewhere else.
        continue;
      }
      unreachable.ClearBit(cur->GetBlockId());
      cohort.blocks_.SetBit(cur->GetBlockId());
      // don't bother filtering here, it's done next go-around
      for (const HBasicBlock* pred : cur->GetPredecessors()) {
        worklist.push(pred);
      }
      for (const HBasicBlock* succ : cur->GetSuccessors()) {
        worklist.push(succ);
      }
    } while (!worklist.empty());
  }
  // Figure out entry & exit nodes.
  for (ExcludedCohort& cohort : res) {
    DCHECK(cohort.blocks_.IsAnyBitSet());
    auto is_external = [&](const HBasicBlock* ext) -> bool {
      return !cohort.blocks_.IsBitSet(ext->GetBlockId());
    };
    for (const HBasicBlock* blk : cohort.Blocks()) {
      const auto& preds = blk->GetPredecessors();
      const auto& succs = blk->GetSuccessors();
      if (std::any_of(preds.cbegin(), preds.cend(), is_external)) {
        cohort.entry_blocks_.SetBit(blk->GetBlockId());
      }
      if (std::any_of(succs.cbegin(), succs.cend(), is_external)) {
        cohort.exit_blocks_.SetBit(blk->GetBlockId());
      }
    }
  }
}

std::ostream& operator<<(std::ostream& os, const ExecutionSubgraph::ExcludedCohort& ex) {
  ex.Dump(os);
  return os;
}

void ExecutionSubgraph::ExcludedCohort::Dump(std::ostream& os) const {
  auto dump = [&](BitVecBlockRange arr) {
    os << "[";
    bool first = true;
    for (const HBasicBlock* b : arr) {
      if (!first) {
        os << ", ";
      }
      first = false;
      os << b->GetBlockId();
    }
    os << "]";
  };
  auto dump_blocks = [&]() {
    os << "[";
    bool first = true;
    for (const HBasicBlock* b : Blocks()) {
      if (!entry_blocks_.IsBitSet(b->GetBlockId()) && !exit_blocks_.IsBitSet(b->GetBlockId())) {
        if (!first) {
          os << ", ";
        }
        first = false;
        os << b->GetBlockId();
      }
    }
    os << "]";
  };

  os << "{ entry: ";
  dump(EntryBlocks());
  os << ", interior: ";
  dump_blocks();
  os << ", exit: ";
  dump(ExitBlocks());
  os << "}";
}

}  // namespace art