runtime/vm/compiler/backend/loops.cc

// Copyright (c) 2018, the Dart project authors.  Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.

#if !defined(DART_PRECOMPILED_RUNTIME)

#include "vm/compiler/backend/loops.h"

#include "vm/bit_vector.h"
#include "vm/compiler/backend/il.h"

namespace dart {

LoopInfo::LoopInfo(intptr_t id, BlockEntryInstr* header, BitVector* blocks)
    : id_(id),
      header_(header),
      blocks_(blocks),
      outer_(nullptr),
      inner_(nullptr),
      next_(nullptr),
      prev_(nullptr) {}

void LoopInfo::AddBlocks(BitVector* blocks) {
  blocks_->AddAll(blocks);
}

bool LoopInfo::IsIn(LoopInfo* other) const {
  return other->blocks_->Contains(header_->preorder_number());
}

intptr_t LoopInfo::NestingDepth() const {
  intptr_t nesting_depth = 1;
  for (LoopInfo* o = outer_; o != nullptr; o = o->outer()) {
    nesting_depth++;
  }
  return nesting_depth;
}

const char* LoopInfo::ToCString() const {
  char buffer[1024];
  BufferFormatter f(buffer, sizeof(buffer));
  f.Print("%*c", static_cast<int>(2 * NestingDepth()), ' ');
  f.Print("loop%" Pd " B%" Pd " ", id_, header_->block_id());
  intptr_t num_blocks = 0;
  for (BitVector::Iterator it(blocks_); !it.Done(); it.Advance()) {
    num_blocks++;
  }
  f.Print("#blocks=%" Pd, num_blocks);
  if (outer_) f.Print(" outer=%" Pd, outer_->id_);
  if (inner_) f.Print(" inner=%" Pd, inner_->id_);
  if (next_) f.Print(" next=%" Pd, next_->id_);
  if (prev_) f.Print(" prev=%" Pd, prev_->id_);
  return Thread::Current()->zone()->MakeCopyOfString(buffer);
}

LoopHierarchy::LoopHierarchy(ZoneGrowableArray<BlockEntryInstr*>* headers)
    : headers_(headers), first_(nullptr), last_(nullptr) {
  Build();
}

void LoopHierarchy::AddLoop(LoopInfo* loop) {
  if (first_ == nullptr) {
    // First loop.
    ASSERT(last_ == nullptr);
    first_ = last_ = loop;
  } else if (loop->IsIn(last_)) {
    // First inner loop.
    loop->outer_ = last_;
    ASSERT(last_->inner_ == nullptr);
    last_ = last_->inner_ = loop;
  } else {
    // Subsequent loop.
    while (last_->outer_ != nullptr && !loop->IsIn(last_->outer_)) {
      last_ = last_->outer_;
    }
    loop->outer_ = last_->outer_;
    loop->prev_ = last_;
    ASSERT(last_->next_ == nullptr);
    last_ = last_->next_ = loop;
  }
}

void LoopHierarchy::Build() {
  for (intptr_t i = 0, n = headers_->length(); i < n; ++i) {
    LoopInfo* loop = (*headers_)[n - 1 - i]->loop_info();
    ASSERT(loop->id() == (n - 1 - i));
    AddLoop(loop);
  }
}

}  // namespace dart

#endif  // !defined(DART_PRECOMPILED_RUNTIME)