CGRADataFlowGraph.hpp

Go to the documentation of this file.

/*
*    MIT License
*    
*    Copyright (c) 2021 Amano laboratory, Keio University & Processor Research Team, RIKEN Center for Computational Science
*    
*    Permission is hereby granted, free of charge, to any person obtaining a copy of
*    this software and associated documentation files (the "Software"), to deal in
*    the Software without restriction, including without limitation the rights to
*    use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
*    of the Software, and to permit persons to whom the Software is furnished to do
*    so, subject to the following conditions:
*    
*    The above copyright notice and this permission notice shall be included in all
*    copies or substantial portions of the Software.
*    
*    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
*    IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
*    FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
*    AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
*    LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
*    OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
*    SOFTWARE.
*    
*    File:          /include/CGRADataFlowGraph.hpp
*    Project:       CGRAOmp
*    Author:        Takuya Kojima in The University of Tokyo (tkojima@hal.ipc.i.u-tokyo.ac.jp)
*    Created Date:  27-08-2021 15:03:28
*    Last Modified: 20-07-2022 13:48:25
*/
#ifndef CGRADataFlowGraph_H
#define CGRADataFlowGraph_H
 
#include "llvm/Support/DOTGraphTraits.h"
#include "llvm/ADT/DirectedGraph.h"
#include "llvm/Support/FormatVariadic.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/ADT/StringMap.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/Instruction.h"
#include "llvm/ADT/APFloat.h"
#include "llvm/Support/JSON.h"
 
#include "CGRAInstMap.hpp"
#include "OptionPlugin.hpp"
#include "Utils.hpp"
 
#include <string>
#include <utility>
#include <stdint.h>
 
using namespace CGRAOmp;
using namespace std;
 
#define VROOT_NODE_ID (-1)
 
 
namespace llvm {
    class DFGNode;
    class DFGEdge;
    class CGRADFG;
    using DFGNodeBase = DGNode<DFGNode, DFGEdge>;
    using DFGEdgeBase = DGEdge<DFGNode, DFGEdge>;
    using CGRADFGBase = DirectedGraph<DFGNode, DFGEdge>;
 
    class DFGNode : public DFGNodeBase {
        public:
            friend CGRADFG;
            enum class NodeKind {
                Compute,
                MemLoad,
                MemStore,
                Compare,
                Constant,
                GlobalData,
                VirtualRoot,
            };
 
            DFGNode(int ID, NodeKind kind, Value *val) :
                DFGNodeBase(), ID(ID), kind(kind), val(val) {};
 
            DFGNode(NodeKind kind, Value* val) :
                DFGNode((std::uintptr_t)(val), kind, val) {}
 
            DFGNode(const DFGNode &N) {
                *this = N;
            }
            DFGNode(DFGNode &&N) {
                *this = std::move(N);
            }
 
            DFGNode &operator=(const DFGNode &N) {
                DGNode::operator=(N);
                return *this;
            }
 
            DFGNode &operator=(DFGNode &&N) {
                DGNode::operator=(std::move(N));
                return *this;
            }
 
            NodeKind getKind() const {
                return kind;
            }
 
            int getID() const { return ID; }
            
            Value* getValue() const { return val; }
 
            virtual string getUniqueName() const = 0;
            virtual string getNodeAttr() const = 0;
            virtual string getExtraAttr() const { return ""; };
 
            bool isEqualTo(const DFGNode &N) const {
                return this->ID == N.ID;
            }
 
            void setExtraInfo(StringRef key, json::Value V) {
                extra_info[key] = new json::Value(std::move(V));
            }
 
            bool hasExtraInfo() const {
                return !extra_info.empty();
            }
 
            json::Value getExtraInfoAsJSONObject() {
                if (!hasExtraInfo()) {
                    return json::Object({});
                } else {
                    json::Object json_obj;
                    for (auto &item : extra_info) {
                        json_obj[item.getKey()] = *(item.getValue());
                    }
                    return json::Value(std::move(json_obj));
                }
 
            }
 
        protected:
            NodeKind kind;
            int ID;
            Value *val;
            StringMap<json::Value*> extra_info;
 
    };
 
    class VirtualRootNode : public DFGNode {
        public:
            VirtualRootNode() :
                DFGNode(VROOT_NODE_ID, 
                    DFGNode::NodeKind::VirtualRoot, nullptr) {}
            string getUniqueName() const {
                return "__VROOT";
            }
            string getNodeAttr() const {
                return "";
            }
    };
 
    class ComputeNode : public DFGNode {
        public:
            ComputeNode(Instruction* inst, std::string opcode) : 
                DFGNode(DFGNode::NodeKind::Compute, inst), opcode(opcode) {}
 
            string getUniqueName() const {
                return opcode + "_" + to_string(getID());
            }
            string getNodeAttr() const {
                return formatv("type=op,{0}={1}", OptDFGOpKey, opcode);
            }
            static bool classof(const DFGNode* N) {
                return N->getKind() == NodeKind::Compute;
            }
            Instruction* getInst() const {
                return dyn_cast<Instruction>(val);
            }
        private:
            std::string opcode;
    };
 
    class MemAccessNode : public DFGNode {
        public:
            MemAccessNode(LoadInst *load) : 
                    DFGNode(DFGNode::NodeKind::MemLoad, load) {
                is_load = true;
                addr = load->getOperand(0);
            }
 
            MemAccessNode(StoreInst *store) :
                    DFGNode(DFGNode::NodeKind::MemStore, store) {
                is_load = false;
                addr = store->getOperand(1);
            }
 
            inline bool isLoad() { return is_load;}
 
            string getUniqueName() const {
                if (is_load) {
                    return  "Load_" + to_string(getID());
                } else {
                    return  "Store_" + to_string(getID());
                }
            }
            
            string getNodeAttr() const {
                string type = (is_load) ? "input" : "output";
                return formatv("type={0},data={1}", type, getSymbol());
            }
 
            string getSymbol() const {
                if (auto gep = dyn_cast<GetElementPtrInst>(addr)) {
                    auto *ptr = gep->getPointerOperand();
                    if (isa<Argument>(*ptr)) {
                        if (ptr->hasName()) {
                            return string(ptr->getName());
                        }
                    } else if (auto load = dyn_cast<LoadInst>(ptr)) {
                        auto child_ptr = load->getPointerOperand();
                        if (isa<Argument>(*child_ptr)) {
                            if (child_ptr->hasName()) {
                                return string(child_ptr->getName());
                            }
                        }
                    } else if (auto *alloc_inst = dyn_cast<AllocaInst>(ptr)) {
                        return string(alloc_inst->getName());
                    }
                    return "unknown";
                } else {
                    return "unknown";
                }
            }
 
            static bool classof(const DFGNode* N) {
                return N->getKind() == NodeKind::MemLoad ||
                        N->getKind() == NodeKind::MemStore;
            }
        private:
            bool is_load;
            Value *addr;
    };
 
    template <DFGNode::NodeKind DrivedKind>
    class DataNode : public DFGNode {
        public:
            using SkipSeq = SmallVector<Value*>;
            
            explicit DataNode(Value *v) :
                DataNode(v, nullptr) {};
 
            // constructor used if it has skipped nodes
            DataNode(Value *v, SkipSeq* seq) : 
                DFGNode(DrivedKind, v), skip_seq(seq) {};
 
            DataNode(Value *v, SkipSeq* seq, int ID) : 
                DFGNode(ID, DrivedKind, v), skip_seq(seq) {};
 
 
        protected:
 
            string getTypeName(Type* ty) const {
                Type *ele_ty = ty;
                string format_str = "{0}", type_str;
 
                while (ele_ty->isPointerTy()) {
                    ele_ty = ty->getPointerElementType();
                }
                while (ele_ty->isArrayTy()) {
                    int size = dyn_cast<ArrayType>(ele_ty)->getArrayNumElements();
                    format_str += formatv("[{0}]", size);
                    ele_ty = ele_ty->getArrayElementType();
                }
 
                if (ele_ty->isFloatingPointTy()) {
                    type_str = "float" + to_string(Utils::getDataWidth(ele_ty));
                } else if (ele_ty->isIntegerTy()) {
                    type_str = "int" + to_string(Utils::getDataWidth(ele_ty));
                } else {
                    type_str = "unknown";
                }
 
                return formatv(format_str.c_str(), type_str);
            }
 
            string getSkipSeq() const {
                #define DEBUG_TYPE "cgraomp"
                string str = "";
                if (skip_seq) {
                    SmallVector<string> opcode_vec;
                    for (auto it = ++(skip_seq->rbegin()); it != skip_seq->rend(); it++) {
                        if (auto inst = dyn_cast<Instruction>(*it)) {
                            opcode_vec.emplace_back(inst->getOpcodeName());
                        } else {
                            LLVM_DEBUG(dbgs() << ERR_DEBUG_PREFIX
                                        << " Unexpected skip instruction: ";
                                        (*it)->print(dbgs());
                                        dbgs() << "\n"
                            );
                        }
                    }
                    str = formatv("skipped=\"({0})\",", make_range(opcode_vec.begin(), opcode_vec.end()));
                }
                return str;
                #undef DEBUG_TYPE
            }
 
            SkipSeq *skip_seq;
    };
 
    class ConstantNode : public DataNode<DFGNode::NodeKind::Constant> {
        public:
            explicit ConstantNode(Value *v) :
                ConstantNode(v, nullptr) {};
 
            ConstantNode(Value *v, int ID) :
                ConstantNode(v, nullptr, ID) {};
 
 
            // constructor used if it has skipped nodes
            ConstantNode(Value *v, SkipSeq* seq) : 
                DataNode<DFGNode::NodeKind::Constant>(v, seq)  {};
 
            ConstantNode(Value *v, SkipSeq* seq, int ID) : 
                DataNode<DFGNode::NodeKind::Constant>(v, seq, ID)  {};
 
            string getUniqueName() const {
                return "Const_" + to_string(getID());
            }
            virtual string getNodeAttr() const;
 
            virtual string getExtraAttr() const {
                return getConstStr();
            }
            static bool classof(const DFGNode *N) {
                return N->getKind() == NodeKind::Constant;
            }
        private:
            string getConstStr() const;
 
    };
 
    class GlobalDataNode : public DataNode<DFGNode::NodeKind::GlobalData> {
        public:
            explicit GlobalDataNode(Value *v) :
                GlobalDataNode(v, nullptr) {};
 
            // constructor used if it has skipped nodes
            GlobalDataNode(Value *v, SkipSeq* seq) : 
                DataNode<DFGNode::NodeKind::GlobalData>(v, seq)  {};
 
            string getUniqueName() const {
                return "GlobalData_" + to_string(getID());
            }
            string getNodeAttr() const;
 
            string getExtraAttr() const {
                return getDataStr();
            }
            static bool classof(const DFGNode *N) {
                return N->getKind() == NodeKind::GlobalData;
            }
        private:
            string getDataStr() const;
 
    };
 
 
    template<char const* OPCODE_STR>
    class GEPNode : public DFGNode {
        public:
            GEPNode(GetElementPtrInst *gep, int ID) : 
                DFGNode(ID, DFGNode::NodeKind::Compute, gep), opcode(OPCODE_STR) {}
 
            string getUniqueName() const {
                return opcode + "_" + to_string(getID());
            }
            string getNodeAttr() const {
                return formatv("type=op,{0}={1}", OptDFGOpKey, opcode);
            }
            static bool classof(const DFGNode* N) {
                return N->getKind() == NodeKind::Compute;
            }
            Instruction* getInst() const {
                return dyn_cast<Instruction>(val);
            }
        private:
            std::string opcode;
    };
 
    class GEPConstantNode : public ConstantNode {
        public:
            explicit GEPConstantNode(Value *v, int ID, int const_value) :
                ConstantNode(v, ID), const_value(const_value) {};
 
            virtual string getExtraAttr() const {
                return formatv("datatype=int,value={0}", const_value);
            }
            virtual string getNodeAttr() const {
                return formatv("type=const,{0}", getExtraAttr());
            }
 
        private:
            int const_value;
    };
 
 
    class DFGEdge : public DFGEdgeBase {
        public:
            enum class EdgeKind {
                Normal,
                LoopCarried,
                Init
            };
            DFGEdge(DFGNode &N, int operand = 0, EdgeKind Kind = EdgeKind::Normal) 
                : DFGEdgeBase(N), operand(operand), Kind(Kind) {}
                
            DFGEdge(const DFGEdge &E) : DFGEdgeBase(E) {
                *this = E;
            };
            DFGEdge(DFGEdge &&E) : DFGEdgeBase(std::move(E)) {
                *this = std::move(E);
            };
 
            DFGEdge &operator=(const DFGEdge &E) {
                DFGEdgeBase::operator=(E);
                return *this;
            };
 
            DFGEdge &operator=(DFGEdge &&E) {
                DFGEdgeBase::operator=(std::move(E));
                return *this;
            };
 
            virtual string getEdgeAttr() const {
                return formatv("operand={0}", operand);
            }
 
            EdgeKind getKind() const { return Kind; }
            
        protected:
            int operand;
            EdgeKind Kind;
    };
 
    class LoopDependencyEdge : public DFGEdge {
        public:
            LoopDependencyEdge(DFGNode &N, int operand, int distance) :
                DFGEdge(N, operand, EdgeKind::LoopCarried), distance(distance) {}
 
 
            virtual string getEdgeAttr() const {
                // add distance info
                return formatv("operand={0},dir=back,distance={1},label={1}", operand ,distance);
            }
 
            static bool classof(const DFGEdge* E) {
                return E->getKind() == EdgeKind::LoopCarried;
            }
 
        private:
            int distance;
    };
 
    class InitDataEdge : public DFGEdge {
        public:
            InitDataEdge(DFGNode &N, int operand) :
                DFGEdge(N, operand, EdgeKind::Init) {}
 
            virtual string getEdgeAttr() const {
                return formatv("operand={0},type=init,label=init", operand);
            }
 
            static bool classof(const DFGEdge* E) {
                return E->getKind() == EdgeKind::Init;
            }
        private:
 
    };
 
    class CGRADFG : public CGRADFGBase {
        public:
            using NodeType = DFGNode;
            using EdgeType = DFGEdge;
            using EdgeInfoType = std::pair<NodeType*, EdgeListTy>;
 
            CGRADFG() = delete;
            CGRADFG(Function *F, Loop *L) : CGRADFGBase(),
                F(F), L(L) {
                createVirtualRoot();
            };
            CGRADFG(const CGRADFG &G) = delete;
            CGRADFG(CGRADFG &&G) : CGRADFGBase(std::move(G)) {
                virtual_root = G.virtual_root;
                G.virtual_root = nullptr;
            };
 
            CGRADFG(NodeType &N) : CGRADFGBase(N) {
                createVirtualRoot();
                auto E = new DFGEdge(N);
                connect(getRoot(), N, *E);
            };
 
            ~CGRADFG() {
                delete virtual_root;
                Nodes.clear();
            }
 
            NodeType &getRoot() const {
                return *virtual_root;
            }
 
            NodeType* addNode(NodeType &N);
 
            bool connect(NodeType &Src, NodeType &Dst, EdgeType &E);
 
            bool findIncomingEdgesToNode(const NodeType &N,
                            SmallVectorImpl<EdgeInfoType> &EL,
                            bool ignore_vroot = false) const {
                assert(EL.empty() && "Expected the list of edges to be empty.");
                EdgeListTy TempList;
                for (auto *Node : Nodes) {
                    if (*Node == N)
                        continue;
                    if (ignore_vroot && *Node == getRoot()) continue;
                    if (Node->findEdgesTo(N, TempList)) {
                        EL.push_back(std::make_pair(Node,TempList));
                    }
                    TempList.clear();
                }
                return !EL.empty();
            }
 
            bool hasExtraInfo() const {
                bool find = false;
                for (auto *Node : Nodes) {
                    if (Node->hasExtraInfo()) {
                        find = true;
                        break;
                    }
                }
                return find;
            }
 
            string convertToReadableNodeName(const string dot_string) const;
 
            Error saveAsDotGraph(StringRef filepath);
 
            Error saveExtraInfo(StringRef filepath);
 
            void setName(const string graph_name) {
                name = graph_name;
            }
 
            string getName() const {
                return name;
            }
 
            void makeSequentialNodeID();
 
            Function* getFunction() {
                return F;
            }
 
            Loop* getLoop() {
                return L;
            }
            
        private:
 
            void createVirtualRoot() {
                virtual_root = new VirtualRootNode();
                CGRADFGBase::addNode(*virtual_root);
            }
            NodeType *virtual_root = nullptr;
 
            string name = "";
 
            Function *F;
            Loop *L;
    };
 
    template <>
    struct GraphTraits<DFGNode *> {
        using NodeRef = DFGNode *;
 
        static DFGNode *DDGGetTargetNode(DFGEdge *P) {
            return &P->getTargetNode();
        }
 
        using ChildIteratorType =
            mapped_iterator<DFGNode::iterator, decltype(&DDGGetTargetNode)>;
        using ChildEdgeIteratorType = DFGNode::iterator;
 
        static ChildIteratorType child_begin(NodeRef N) {
            return ChildIteratorType(N->begin(), &DDGGetTargetNode);
        }
        static ChildIteratorType child_end(NodeRef N) {
            return ChildIteratorType(N->end(), &DDGGetTargetNode);
        }
 
        static ChildEdgeIteratorType child_edge_begin(NodeRef N) {
            return N->begin();
        }
 
        static ChildEdgeIteratorType child_edge_end(NodeRef N) { 
            return N->end();
        }
    };
 
    template <>
    struct GraphTraits<CGRADFG *> : public GraphTraits<DFGNode*> {
        using nodes_iterator = CGRADFG::iterator;
        static NodeRef getEntryNode(CGRADFG *G) {
            return &G->getRoot();
        }
        static nodes_iterator nodes_begin(CGRADFG *G) {
            return G->begin();
        }
        static nodes_iterator nodes_end(CGRADFG *G) {
            return G->end();
        }
    };
 
    template <>
    struct GraphTraits<const DFGNode *> {
        using NodeRef = const DFGNode *;
 
        static const DFGNode *DDGGetTargetNode(const DFGEdge *P) {
            return &P->getTargetNode();
        }
 
        using ChildIteratorType =
            mapped_iterator<DFGNode::iterator, decltype(&DDGGetTargetNode)>;
        using ChildEdgeIteratorType = DFGNode::iterator;
 
        static ChildIteratorType child_begin(const NodeRef N) {
            return ChildIteratorType(N->begin(), &DDGGetTargetNode);
        }
        static ChildIteratorType child_end(const NodeRef N) {
            return ChildIteratorType(N->end(), &DDGGetTargetNode);
        }
 
        static ChildEdgeIteratorType child_edge_begin(const NodeRef N) {
            return N->begin();
        }
 
        static ChildEdgeIteratorType child_edge_end(const NodeRef N) { 
            return N->end();
        }
    };
 
    template <>
    struct GraphTraits<const CGRADFG *> : public GraphTraits<DFGNode*> {
        using nodes_iterator = CGRADFG::const_iterator;
        static NodeRef getEntryNode(const CGRADFG *G) {
            return &G->getRoot();
        }
        static nodes_iterator nodes_begin(const CGRADFG *G) {
            return G->begin();
        }
        static nodes_iterator nodes_end(const CGRADFG *G) {
            return G->end();
        }
    };
 
    template<>
    struct DOTGraphTraits<const CGRADFG *> : public DefaultDOTGraphTraits {
        public:
            DOTGraphTraits(bool isSimple) : DefaultDOTGraphTraits(isSimple) {};
            DOTGraphTraits() : DefaultDOTGraphTraits(false) {};
 
            string getGraphName(const CGRADFG *G) {
                return G->getName();
            }
 
            static string getGraphProperties(const CGRADFG *G);
 
            static bool isNodeHidden(const DFGNode *Node, 
                                const CGRADFG *G) {
                return *Node == G->getRoot();
            }
 
            static string getNodeLabel(const DFGNode *Node, 
                                const CGRADFG *G) {
                return Node->getUniqueName();
            }
 
            static string getNodeIdentifierLabel(const DFGNode *Node, 
                                const CGRADFG *G) {
                return Node->getExtraAttr();
            }
 
            static string getNodeDescription(const DFGNode *Node, 
                                const CGRADFG *G) {
                return "";
            }
 
            static string getNodeAttributes(const DFGNode *Node, 
                                const CGRADFG *G) {
                return Node->getNodeAttr();
            }
 
            static string getEdgeAttributes(const DFGNode *Node, 
                    GraphTraits<DFGNode *>::ChildIteratorType I,
                      const CGRADFG *G);
        private:
            static StringMap<StringRef> default_graph_prop;
            static StringMap<StringRef> default_node_prop;
            static StringMap<StringRef> default_edge_prop;
 
    };
 
    using CGRADFGDotGraphTraits = DOTGraphTraits<const CGRADFG *>;
 
};
 
#endif //CGRADataFlowGraph_H