VerifyPass.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/VerifyPass.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:00:17
*    Last Modified: 17-07-2022 19:36:44
*/
#ifndef VerifyPass_H
#define VerifyPass_H
 
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/Analysis/LoopAnalysisManager.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/IR/DiagnosticInfo.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/PassManager.h"
#include "llvm/Passes/PassBuilder.h"
#include "llvm/Passes/PassPlugin.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
 
#include "CGRAOmpPass.hpp"
#include "DecoupledAnalysis.hpp"
#include "CGRAModel.hpp"
 
 
#include <map>
 
using namespace llvm;
 
 
namespace CGRAOmp {
    // Verification Kind
    enum class VerificationKind {
        FunctionSummary,
        KernelSummary,
        Decoupling,
        InstAvailability,
        MaxNestedLevel,
        MemoryAccess,
        InterLoopDep,
        NestedPerfectly,
        IterationSize,
        // Inside loop
        Conditional,
        FunctionCall,
    };
 
    class VerifyPass;
 
    class VerifyResultBase {
        public:
            explicit VerifyResultBase(VerificationKind kind) : kind(kind) {};
 
            VerifyResultBase() = delete;
 
            explicit operator bool() {
                return this->bool_operator_impl();
            }
 
 
            // interface to print messages
            virtual void print(raw_ostream &OS) const = 0;
            void dump() { this->print(dbgs()); }
            friend raw_ostream& operator<<(raw_ostream& OS, 
                                            const VerifyResultBase &v) {
                v.print(OS);
                return OS;
            }
 
            virtual StringRef getName() const = 0;
 
            void setVio() { isViolate = true; }
 
            virtual VerificationKind getKind() const {
                return kind;
            }
 
        protected:
            virtual bool bool_operator_impl() {
                return !isViolate;
            }
            bool isViolate = false;
 
 
        private:
            VerificationKind kind;
    };
 
 
    class LoopVerifyResult : public VerifyResultBase {
 
        public:
            using result_iterator = DenseMap<int, VerifyResultBase*>::iterator;
            
            LoopVerifyResult() : VerifyResultBase(VerificationKind::KernelSummary) {}
            void print(raw_ostream &OS) const override;
 
            static bool classof(const VerifyResultBase* R) {
                return R->getKind() == VerificationKind::KernelSummary;
            }
 
            void setResult(VerifyResultBase *R) {
                each_result[static_cast<int>(R->getKind())] = R;
            }
 
            BranchInst* getBackBranch(Loop* L) {
                if (back_branch_list.find(L) != back_branch_list.end()) {
                    return back_branch_list[L];
                } else {
                    return nullptr;
                }
            }
 
            CmpInst* getBackCondition(Loop *L) {
                if (auto back = getBackBranch(L)) {
                    return dyn_cast<CmpInst>(back->getCondition());
                } else {
                    return nullptr;
                }
            }
 
            void setBackBranch(Loop*L, BranchInst* B) {
                back_branch_list[L] = B;
            }
 
            result_iterator result_begin() {
                return each_result.begin();
            }
 
            result_iterator result_end() {
                return each_result.end();
            }
 
            iterator_range<result_iterator> results() {
                return make_range(result_begin(), result_end());
            }
 
            StringRef getName() const {
                return "Loop verify result summary";
            }
 
            VerifyResultBase* getResult(VerificationKind kind) {
                auto result = each_result.find(static_cast<int>(kind));
                if (result != each_result.end()) {
                    return result->second;
                } else {
                    return nullptr;
                }
            }
 
 
        private:
            DenseMap<int, VerifyResultBase*> each_result;
 
            bool bool_operator_impl() override;
 
            DenseMap<Loop*,BranchInst*> back_branch_list;
 
    };
 
    class VerifyResult : public VerifyResultBase {
        private:
            SmallVector<Loop*> valid_kernels;
 
        public:
            using KernelList = SmallVector<Loop*>;
            using kernel_iterator = KernelList::iterator;
 
            VerifyResult() : VerifyResultBase(VerificationKind::FunctionSummary) {}
            void print(raw_ostream &OS) const override;
 
            void registerKernel(Loop *L, LoopVerifyResult LVR) {
                valid_kernels.push_back(L);
                loop_verify_results[L] = LVR;
            }
 
            inline kernel_iterator kernel_begin() {
                return valid_kernels.begin();
            };
 
            inline kernel_iterator kernel_end() {
                return valid_kernels.end();
            }
            inline iterator_range<kernel_iterator> kernels() {
                return make_range(kernel_begin(), kernel_end());
            }
            static bool classof(const VerifyResultBase* R) {
                return R->getKind() == VerificationKind::FunctionSummary;
            }
 
            LoopVerifyResult* getLoopVerifyResult(Loop* L) {
                if (loop_verify_results.find(L) != loop_verify_results.end()) {
                    return &loop_verify_results[L];
                } else {
                    return nullptr;
                }
            }
 
            StringRef getName() const {
                return "Verify result summary";
            }
 
            int getNumKernels() {
                return valid_kernels.size();
            }
 
 
        private:
            std::map<Loop*, LoopVerifyResult> loop_verify_results;
    };
 
    template<VerificationKind Kind>
    class SimpleVerifyResult : public VerifyResultBase {
        public:
            SimpleVerifyResult() : SimpleVerifyResult(std::string()) {}
            SimpleVerifyResult(std::string msg) : VerifyResultBase(Kind),
                msg(msg) {};
 
            void setMessage(StringRef msg) {
                msg = msg.str();
            }
            void print(raw_ostream &OS) const {
                OS << msg;
            }
 
            StringRef getName() const {
                return name;
            }
 
        private:
            std::string msg;
            static const char *name;
    };
 
    using DecoupleAnalysisResult = SimpleVerifyResult<VerificationKind::Decoupling>;
    using InterLoopDependencyAnalysisResult = SimpleVerifyResult<VerificationKind::InterLoopDep>;
 
    template <typename DerivedT>
    class VerifyPassBase : public AnalysisInfoMixin<DerivedT> {
        public:
            using LoopList = SmallVector<Loop*>;
            // using InstList = SmallVector<Instruction*>;
        protected:
 
            LoopList findPerfectlyNestedLoop(Function &F,
                LoopStandardAnalysisResults &AR);
 
            void remarkEmitter(Function &F, Loop &L, LoopVerifyResult &R,
                                         FunctionAnalysisManager &AM);
        };
 
    class TimeMultiplexedVerifyPass : 
            public VerifyPassBase<TimeMultiplexedVerifyPass> {
        public:
            using Result = VerifyResult;
            Result run(Function &F, FunctionAnalysisManager &AM);
        private:
            friend AnalysisInfoMixin<TimeMultiplexedVerifyPass>;
            static AnalysisKey Key;
 
    };
 
 
    class DecoupledVerifyPass :
            public VerifyPassBase<DecoupledVerifyPass> {
        public:
            using Result = VerifyResult;
            Result run(Function &F, FunctionAnalysisManager &AM);
        private:
            friend AnalysisInfoMixin<DecoupledVerifyPass>;
            static AnalysisKey Key;
 
 
    };
 
    class InstAvailability : public VerifyResultBase {
        public:
            InstAvailability() : 
                VerifyResultBase(VerificationKind::InstAvailability) {}
 
            void filter(SmallVector<Instruction*> *list);
            void filter(SmallPtrSetImpl<Instruction*> *list);
 
            void print(raw_ostream &OS) const override;
 
            void add_unsupported(Instruction* I) {
                unsupported.insert(I);
            }
 
            StringRef getName() const {
                return "Instruction availability";
            }
 
        private:
            bool bool_operator_impl() override {
                return unsupported.size() == 0;
            }
 
            SmallPtrSet<Instruction*, 32> unsupported;
    };
 
    template <typename VerifyPassTy>
    class VerifyInstAvailabilityPass : 
                public AnalysisInfoMixin<VerifyInstAvailabilityPass<VerifyPassTy>> {
        public:
            using Result = InstAvailability;
 
            Result run(Loop &L, LoopAnalysisManager &AM,
                        LoopStandardAnalysisResults &AR) {
                
                #define DEBUG_TYPE "cgraomp"
                LLVM_DEBUG(dbgs() << INFO_DEBUG_PREFIX 
                    << "Verifying insturction compatibility: "
                    << L.getName() << "\n");
                #undef DEBUG_TYPE
 
                auto unsupported_insts = checkUnsupportedInst(L, AM, AR);
                Result result;
 
                if (unsupported_insts.hasValue()) {
                    // Invalid
                    for (auto inst : *unsupported_insts) {
                        result.add_unsupported(inst);
                    }
                }
                return result;
            };
 
        private:
            friend AnalysisInfoMixin<VerifyInstAvailabilityPass<VerifyPassTy>>;
            static AnalysisKey Key;
            using InstList = SmallVector<Instruction*>;
 
            Optional<InstList>
            checkUnsupportedInst(Loop& L, LoopAnalysisManager &AM,
                                LoopStandardAnalysisResults &AR)
            {
                auto LN = LoopNest::getLoopNest(L, AR.SE);
                auto innermost = LN->getInnermostLoop();
 
                auto &MM = AM.getResult<ModelManagerLoopProxy>(L, AR);
                auto *model = MM.getModel();
 
                InstList unsupported;
 
                for (auto &BB : innermost->getBlocks()) {
                    for (auto &I : *BB) {
                        auto *imap = model->isSupported(&I);
                        if (!imap) {
                            unsupported.emplace_back(&I);
                        }
                    }
                }
 
                if (unsupported.size() == 0) {
                    return None;
                } else {
                    return Optional<InstList>(std::move(unsupported));
                }
            }   
 
    };
 
    template <typename VerifyPassTy>
    AnalysisKey VerifyInstAvailabilityPass<VerifyPassTy>::Key;
 
 
    class VerifyModulePass : public PassInfoMixin<VerifyModulePass> {
        public:
            PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
        private:
            void remarkEmitter(Function &F, VerifyResult &R,
                                FunctionAnalysisManager &AM);
    };
 
}
 
#endif //VerifyPass_H