LLVM数据流分析的理论

LLVM数据流分析的理论

标量优化(scalar目录): 死代码消除(BDCE.cpp[code]ADCE.cpp[code]DCE.cpp[code]), 全局值编号(GVN.cpp[code]), 代码提升(ConstantHoisting.cpp[code]), 公共子表达式消除(EarlyCSE.cpp[code]), 代码下沉(Sink.cpp[code]), 以及各种循环优化等

过程间优化(IPO目录):无效参数消除(DeadArgumentElimination.cpp[code]) , 全局死代码消除(GlobalDCE.cpp[code]), 常量传播(IPConstantPropagation.cpp[code]), 循环外提(LoopExtractor.cpp[code]),稀疏条件常量传播(SCCP.cpp[code]),函数合并(MergeFunctions.cpp[code])等

介绍

本文档描述了构成 LLVM的内部软件,不是 LLVM 的外部使用。这里没有关于如何使用 LLVM 的说明,只有构成软件的 API。有关使用说明,请参阅程序员指南或参考手册。

警告

本文档直接从带有 doxygen 的源代码生成。由于 LLVM 一直在积极开发中,可能仍然有用,因为 LLVM 的某些部分非常稳定。

Transforms Directory Reference

 LLVM数据流分析的理论

 

 LLVM数据流分析的理论

 

 LLVM数据流分析的理论

 

 AggressiveInstCombine.cpp File Reference

#include "llvm/Transforms/AggressiveInstCombine/AggressiveInstCombine.h"
#include "AggressiveInstCombineInternal.h"
#include "llvm-c/Initialization.h"
#include "llvm-c/Transforms/AggressiveInstCombine.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/BasicAliasAnalysis.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/LegacyPassManager.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Transforms/Utils/Local.h"

 LLVM数据流分析的理论

 

 LLVM数据流分析的理论

 

 AggressiveInstCombineInternal.h File Reference

#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Support/KnownBits.h"

Include dependency graph for AggressiveInstCombineInternal.h:

CFGuard Directory Reference

Directory dependency graph for CFGuard:

 LLVM数据流分析的理论

CFGuard.cpp File Reference

#include "llvm/Transforms/CFGuard.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/Triple.h"
#include "llvm/IR/CallingConv.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Instruction.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"

Include dependency graph for CFGuard.cpp:

 LLVM数据流分析的理论

 

 /home/buildbot/as-worker-4/publish-doxygen-docs/llvm-project/llvm/include/llvm/ADT/ilist_node.h

侵入式列表节点。用于启用侵入式列表成员资格的基类,包括simple_ilistiplistilist。第一个模板参数是列表的value_type

可以使用编译时,选项配置 ilist 节点,更改行为和/或添加 API。

默认情况下,当且仅当 LLVM_ENABLE_ABI_BREAKING_CHECKS 时,ilist_node 才知道是否是列表监测(ilist_sentinel的实例)。函数isKnownSentinel()总是返回false跟踪关闭。Sentinel 跟踪从“prev”链接中窃取了一点,在递减迭代器时,添加了掩码操作,但在ilist_iterator 中启用了错误查找断言。

要始终打开监测跟踪,请传入 ilist_sentinel_tracking<true> 模板参数。这也启用了isSentinel()函数。必须将相同的选项传递给侵入式列表。( ilist_sentinel_tracking<false> 始终关闭监测跟踪。)

通过传入不同的ilist_tag选项,一个类型可以多次从 ilist_node 继承。这允许将单个实例同时插入到多个列表中,其中每个列表都被赋予相同的标签。

struct A {}; struct B {}; struct N : ilist_node<N, ilist_tag>, ilist_node<N, ilist_tag> {};

void foo() { simple_ilist<N, ilist_tag> ListA; simple_ilist<N, ilist_tag> ListB; N N1; ListA.push_back(N1); ListB.push_back(N1); } \endexample

See is_valid_option for steps on adding a new option.

//===- llvm/ADT/ilist_node.h - Intrusive Linked List Helper -----*- C++ -*-===//

//

// 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 defines the ilist_node class template, which is a convenient

// base class for creating classes that can be used with ilists.

//

//===----------------------------------------------------------------------===//

#ifndef LLVM_ADT_ILIST_NODE_H

#define LLVM_ADT_ILIST_NODE_H

#include "llvm/ADT/ilist_node_base.h"

#include "llvm/ADT/ilist_node_options.h"

namespace llvm {

namespace ilist_detail {

struct NodeAccess;

} // end namespace ilist_detail

template <class OptionsT, bool IsReverse, bool IsConst> class ilist_iterator;

template <class OptionsT> class ilist_sentinel;

/// Implementation for an ilist node.

///

/// Templated on an appropriate \a ilist_detail::node_options, usually computed

/// by \a ilist_detail::compute_node_options.

///

/// This is a wrapper around \a ilist_node_base whose main purpose is to

/// provide type safety: you can't insert nodes of \a ilist_node_impl into the

/// wrong \a simple_ilist or \a iplist.

template <class OptionsT> class ilist_node_impl : OptionsT::node_base_type {

using value_type = typename OptionsT::value_type;

using node_base_type = typename OptionsT::node_base_type;

using list_base_type = typename OptionsT::list_base_type;

friend typename OptionsT::list_base_type;

friend struct ilist_detail::NodeAccess;

friend class ilist_sentinel<OptionsT>;

friend class ilist_iterator<OptionsT, false, false>;

friend class ilist_iterator<OptionsT, false, true>;

friend class ilist_iterator<OptionsT, true, false>;

friend class ilist_iterator<OptionsT, true, true>;

protected:

using self_iterator = ilist_iterator<OptionsT, false, false>;

using const_self_iterator = ilist_iterator<OptionsT, false, true>;

using reverse_self_iterator = ilist_iterator<OptionsT, true, false>;

using const_reverse_self_iterator = ilist_iterator<OptionsT, true, true>;

ilist_node_impl() = default;

private:

ilist_node_impl *getPrev() {

return static_cast<ilist_node_impl *>(node_base_type::getPrev());

}

ilist_node_impl *getNext() {

return static_cast<ilist_node_impl *>(node_base_type::getNext());

}

const ilist_node_impl *getPrev() const {

return static_cast<ilist_node_impl *>(node_base_type::getPrev());

}

const ilist_node_impl *getNext() const {

return static_cast<ilist_node_impl *>(node_base_type::getNext());

}

void setPrev(ilist_node_impl *N) { node_base_type::setPrev(N); }

void setNext(ilist_node_impl *N) { node_base_type::setNext(N); }

public:

self_iterator getIterator() { return self_iterator(*this); }

const_self_iterator getIterator() const { return const_self_iterator(*this); }

reverse_self_iterator getReverseIterator() {

return reverse_self_iterator(*this);

}

const_reverse_self_iterator getReverseIterator() const {

return const_reverse_self_iterator(*this);

}

// Under-approximation, but always available for assertions.

using node_base_type::isKnownSentinel;

/// Check whether this is the sentinel node.

///

/// This requires sentinel tracking to be explicitly enabled. Use the

/// ilist_sentinel_tracking<true> option to get this API.

bool isSentinel() const {

static_assert(OptionsT::is_sentinel_tracking_explicit,

"Use ilist_sentinel_tracking<true> to enable isSentinel()");

return node_base_type::isSentinel();

}

};

/// An intrusive list node.

///

/// A base class to enable membership in intrusive lists, including \a

/// simple_ilist, \a iplist, and \a ilist. The first template parameter is the

/// \a value_type for the list.

///

/// An ilist node can be configured with compile-time options to change

/// behaviour and/or add API.

///

/// By default, an \a ilist_node knows whether it is the list sentinel (an

/// instance of \a ilist_sentinel) if and only if

/// LLVM_ENABLE_ABI_BREAKING_CHECKS. The function \a isKnownSentinel() always

/// returns \c false tracking is off. Sentinel tracking steals a bit from the

/// "prev" link, which adds a mask operation when decrementing an iterator, but

/// enables bug-finding assertions in \a ilist_iterator.

///

/// To turn sentinel tracking on all the time, pass in the

/// ilist_sentinel_tracking<true> template parameter. This also enables the \a

/// isSentinel() function. The same option must be passed to the intrusive

/// list. (ilist_sentinel_tracking<false> turns sentinel tracking off all the

/// time.)

///

/// A type can inherit from ilist_node multiple times by passing in different

/// \a ilist_tag options. This allows a single instance to be inserted into

/// multiple lists simultaneously, where each list is given the same tag.

///

/// \example

/// struct A {};

/// struct B {};

/// struct N : ilist_node<N, ilist_tag<A>>, ilist_node<N, ilist_tag<B>> {};

///

/// void foo() {

/// simple_ilist<N, ilist_tag<A>> ListA;

/// simple_ilist<N, ilist_tag<B>> ListB;

/// N N1;

/// ListA.push_back(N1);

/// ListB.push_back(N1);

/// }

/// \endexample

///

/// See \a is_valid_option for steps on adding a new option.

template <class T, class... Options>

class ilist_node

: public ilist_node_impl<

typename ilist_detail::compute_node_options<T, Options...>::type> {

static_assert(ilist_detail::check_options<Options...>::value,

"Unrecognized node option!");

};

namespace ilist_detail {

/// An access class for ilist_node private API.

///

/// This gives access to the private parts of ilist nodes. Nodes for an ilist

/// should friend this class if they inherit privately from ilist_node.

///

/// Using this class outside of the ilist implementation is unsupported.

struct NodeAccess {

protected:

template <class OptionsT>

static ilist_node_impl<OptionsT> *getNodePtr(typename OptionsT::pointer N) {

return N;

}

template <class OptionsT>

static const ilist_node_impl<OptionsT> *

getNodePtr(typename OptionsT::const_pointer N) {

return N;

}

template <class OptionsT>

static typename OptionsT::pointer getValuePtr(ilist_node_impl<OptionsT> *N) {

return static_cast<typename OptionsT::pointer>(N);

}

template <class OptionsT>

static typename OptionsT::const_pointer

getValuePtr(const ilist_node_impl<OptionsT> *N) {

return static_cast<typename OptionsT::const_pointer>(N);

}

template <class OptionsT>

static ilist_node_impl<OptionsT> *getPrev(ilist_node_impl<OptionsT> &N) {

return N.getPrev();

}

template <class OptionsT>

static ilist_node_impl<OptionsT> *getNext(ilist_node_impl<OptionsT> &N) {

return N.getNext();

}

template <class OptionsT>

static const ilist_node_impl<OptionsT> *

getPrev(const ilist_node_impl<OptionsT> &N) {

return N.getPrev();

}

template <class OptionsT>

static const ilist_node_impl<OptionsT> *

getNext(const ilist_node_impl<OptionsT> &N) {

return N.getNext();

}

};

template <class OptionsT> struct SpecificNodeAccess : NodeAccess {

protected:

using pointer = typename OptionsT::pointer;

using const_pointer = typename OptionsT::const_pointer;

using node_type = ilist_node_impl<OptionsT>;

static node_type *getNodePtr(pointer N) {

return NodeAccess::getNodePtr<OptionsT>(N);

}

static const node_type *getNodePtr(const_pointer N) {

return NodeAccess::getNodePtr<OptionsT>(N);

}

static pointer getValuePtr(node_type *N) {

return NodeAccess::getValuePtr<OptionsT>(N);

}

static const_pointer getValuePtr(const node_type *N) {

return NodeAccess::getValuePtr<OptionsT>(N);

}

};

} // end namespace ilist_detail

template <class OptionsT>

class ilist_sentinel : public ilist_node_impl<OptionsT> {

public:

ilist_sentinel() {

this->initializeSentinel();

reset();

}

void reset() {

this->setPrev(this);

this->setNext(this);

}

bool empty() const { return this == this->getPrev(); }

};

/// An ilist node that can access its parent list.

///

/// Requires \c NodeTy to have \a getParent() to find the parent node, and the

/// \c ParentTy to have \a getSublistAccess() to get a reference to the list.

template <typename NodeTy, typename ParentTy, class... Options>

class ilist_node_with_parent : public ilist_node<NodeTy, Options...> {

protected:

ilist_node_with_parent() = default;

private:

/// Forward to NodeTy::getParent().

///

/// Note: do not use the name "getParent()". We want a compile error

/// (instead of recursion) when the subclass fails to implement \a

/// getParent().

const ParentTy *getNodeParent() const {

return static_cast<const NodeTy *>(this)->getParent();

}

public:

/// @name Adjacent Node Accessors

/// @{

/// Get the previous node, or \c nullptr for the list head.

NodeTy *getPrevNode() {

// Should be separated to a reused function, but then we couldn't use auto

// (and would need the type of the list).

const auto &List =

getNodeParent()->*(ParentTy::getSublistAccess((NodeTy *)nullptr));

return List.getPrevNode(*static_cast<NodeTy *>(this));

}

/// Get the previous node, or \c nullptr for the list head.

const NodeTy *getPrevNode() const {

return const_cast<ilist_node_with_parent *>(this)->getPrevNode();

}

/// Get the next node, or \c nullptr for the list tail.

NodeTy *getNextNode() {

// Should be separated to a reused function, but then we couldn't use auto

// (and would need the type of the list).

const auto &List =

getNodeParent()->*(ParentTy::getSublistAccess((NodeTy *)nullptr));

return List.getNextNode(*static_cast<NodeTy *>(this));

}

/// Get the next node, or \c nullptr for the list tail.

const NodeTy *getNextNode() const {

return const_cast<ilist_node_with_parent *>(this)->getNextNode();

}

/// @}

};

} // end namespace llvm

#endif // LLVM_ADT_ILIST_NODE_H

 

参考链接:

https://www.zhihu.com/question/41123019

https://llvm.org/doxygen/index.html

 

 

 

上一篇:LLVM编译器基础架构与DragonEgg示例


下一篇:TensorFlow XLA优化原理与示例