Alexis Engelke
691a130e0f
Currently, po_iterator holds the traversal state. This makes copying and moving po_iterator fairly expensive and the code cannot be optimized away in several cases (most of it isn't even inlined in a default build). Therefore, refactor post-order traversal to hold the state in a wrapper class with cheap iterators. Additionally, replace po_storage base class with a CRTP implementation where users can provide their own storage. Benefits: - Performance in stage2-O3 improves by 0.19% instructions:u and even more substantially in cycles/wall-time. - Users that use a custom storage/iteration limitation can do so in a more clean way by subclassing PostIteratorTraversalBase. See e.g. LoopBlocksTraversal. - For graphs with block numbers, reserving can now be implemented reasonably easy (not done yet). Implications: - PostOrderTraversal::iterator is no longer a forward iterator. This property was never really used, though. - PostOrderTraversal must be live while iterators are live. For typical uses (for (X x : post_order(...))), this is no problem, but could end up being problematic if the iterator is wrapped (e.g. for (X x : make_filter_range(post_order(...), ...)) -- problematic, because make_filter_range doesn't preserve the range but only the two iterators, which become invalid as the for loop is entered). This is a limitation of the way LLVM implements ranges.
79 lines
3.0 KiB
C++
79 lines
3.0 KiB
C++
//===- PostOrderCFGView.cpp - Post order view of CFG blocks ---------------===//
|
|
//
|
|
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
|
|
// See https://llvm.org/LICENSE.txt for license information.
|
|
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
//
|
|
// This file implements post order view of the blocks in a CFG.
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
#include "clang/Analysis/Analyses/PostOrderCFGView.h"
|
|
#include "clang/Analysis/AnalysisDeclContext.h"
|
|
#include "clang/Analysis/CFG.h"
|
|
|
|
using namespace clang;
|
|
|
|
void PostOrderCFGView::anchor() {}
|
|
|
|
PostOrderCFGView::PostOrderCFGView(const CFG *cfg) {
|
|
Blocks.reserve(cfg->getNumBlockIDs());
|
|
|
|
// The CFG orders the blocks of loop bodies before those of loop successors
|
|
// (both numerically, and in the successor order of the loop condition
|
|
// block). So, RPO necessarily reverses that order, placing the loop successor
|
|
// *before* the loop body. For many analyses, particularly those that converge
|
|
// to a fixpoint, this results in potentially significant extra work because
|
|
// loop successors will necessarily need to be reconsidered once the algorithm
|
|
// has reached a fixpoint on the loop body.
|
|
//
|
|
// This definition of CFG graph traits reverses the order of children, so that
|
|
// loop bodies will come first in an RPO.
|
|
struct CFGLoopBodyFirstTraits {
|
|
using NodeRef = const ::clang::CFGBlock *;
|
|
using ChildIteratorType = ::clang::CFGBlock::const_succ_reverse_iterator;
|
|
|
|
static ChildIteratorType child_begin(NodeRef N) { return N->succ_rbegin(); }
|
|
static ChildIteratorType child_end(NodeRef N) { return N->succ_rend(); }
|
|
};
|
|
|
|
struct POTraversal
|
|
: llvm::PostOrderTraversalBase<POTraversal, CFGLoopBodyFirstTraits> {
|
|
CFGBlockSet BSet;
|
|
|
|
POTraversal(const CFG *cfg) : BSet(cfg) { this->init(&cfg->getEntry()); }
|
|
bool insertEdge(std::optional<const CFGBlock *>, const CFGBlock *To) {
|
|
if (!To)
|
|
return false;
|
|
return BSet.insert(To).second;
|
|
}
|
|
};
|
|
|
|
for (const CFGBlock *Block : POTraversal(cfg)) {
|
|
BlockOrder[Block] = Blocks.size() + 1;
|
|
Blocks.push_back(Block);
|
|
}
|
|
}
|
|
|
|
std::unique_ptr<PostOrderCFGView>
|
|
PostOrderCFGView::create(AnalysisDeclContext &ctx) {
|
|
const CFG *cfg = ctx.getCFG();
|
|
if (!cfg)
|
|
return nullptr;
|
|
return std::make_unique<PostOrderCFGView>(cfg);
|
|
}
|
|
|
|
const void *PostOrderCFGView::getTag() { static int x; return &x; }
|
|
|
|
bool PostOrderCFGView::BlockOrderCompare::operator()(const CFGBlock *b1,
|
|
const CFGBlock *b2) const {
|
|
PostOrderCFGView::BlockOrderTy::const_iterator b1It = POV.BlockOrder.find(b1);
|
|
PostOrderCFGView::BlockOrderTy::const_iterator b2It = POV.BlockOrder.find(b2);
|
|
|
|
unsigned b1V = (b1It == POV.BlockOrder.end()) ? 0 : b1It->second;
|
|
unsigned b2V = (b2It == POV.BlockOrder.end()) ? 0 : b2It->second;
|
|
return b1V > b2V;
|
|
}
|