Branch data     Line data    Source code

       1                 :            : // This file is a part of Julia. License is MIT: https://julialang.org/license
       2                 :            : 
       3                 :            : #ifndef LLVM_ALLOC_HELPERS_H
       4                 :            : #define LLVM_ALLOC_HELPERS_H
       5                 :            : #include <llvm-c/Types.h>
       6                 :            : 
       7                 :            : #include <llvm/ADT/SmallSet.h>
       8                 :            : #include <llvm/ADT/SmallVector.h>
       9                 :            : #include <llvm/IR/Instructions.h>
      10                 :            : 
      11                 :            : #include <utility>
      12                 :            : #include <map>
      13                 :            : 
      14                 :            : #include "llvm-pass-helpers.h"
      15                 :            : 
      16                 :            : namespace jl_alloc {
      17                 :            : 
      18                 :            :     struct CheckInst {
      19                 :            :         struct Frame {
      20                 :            :             llvm::Instruction *parent;
      21                 :            :             uint32_t offset;
      22                 :            :             llvm::Instruction::use_iterator use_it;
      23                 :            :             llvm::Instruction::use_iterator use_end;
      24                 :            :         };
      25                 :            :         typedef llvm::SmallVector<Frame,4> Stack;
      26                 :            :     };
      27                 :            : 
      28                 :            :     struct MemOp {
      29                 :            :         llvm::Instruction *inst;
      30                 :            :         uint64_t offset = 0;
      31                 :            :         unsigned opno;
      32                 :            :         uint32_t size = 0;
      33                 :            :         bool isobjref:1;
      34                 :            :         bool isaggr:1;
      35                 :         26 :         MemOp(llvm::Instruction *inst, unsigned opno)
      36                 :         26 :             : inst(inst),
      37                 :            :               opno(opno),
      38                 :            :               isobjref(false),
      39                 :         26 :               isaggr(false)
      40                 :         26 :         {}
      41                 :            :     };
      42                 :            :     struct Field {
      43                 :            :         uint32_t size;
      44                 :            :         bool hasobjref:1;
      45                 :            :         bool hasaggr:1;
      46                 :            :         bool multiloc:1;
      47                 :            :         bool hasload:1;
      48                 :            :         llvm::Type *elty;
      49                 :            :         llvm::SmallVector<MemOp,4> accesses;
      50                 :         26 :         Field(uint32_t size, llvm::Type *elty)
      51                 :         26 :             : size(size),
      52                 :            :               hasobjref(false),
      53                 :            :               hasaggr(false),
      54                 :            :               multiloc(false),
      55                 :            :               hasload(false),
      56                 :         26 :               elty(elty)
      57                 :            :         {
      58                 :         26 :         }
      59                 :            :     };
      60                 :            : 
      61                 :            :     struct AllocUseInfo {
      62                 :            :         llvm::SmallSet<llvm::Instruction*,16> uses;
      63                 :            :         llvm::SmallSet<llvm::CallInst*,4> preserves;
      64                 :            :         std::map<uint32_t,Field> memops;
      65                 :            :         // Completely unknown use
      66                 :            :         bool escaped:1;
      67                 :            :         // Address is leaked to functions that doesn't care where the object is allocated.
      68                 :            :         bool addrescaped:1;
      69                 :            :         // There are reader of the memory
      70                 :            :         bool hasload:1;
      71                 :            :         // There are uses in gc_preserve intrinsics or ccall roots
      72                 :            :         bool haspreserve:1;
      73                 :            :         // There are objects fields being loaded
      74                 :            :         bool refload:1;
      75                 :            :         // There are objects fields being stored
      76                 :            :         bool refstore:1;
      77                 :            :         // There are typeof call
      78                 :            :         // This can be optimized without optimizing out the allocation itself
      79                 :            :         bool hastypeof:1;
      80                 :            :         // There are store/load/memset on this object with offset or size (or value for memset)
      81                 :            :         // that cannot be statically computed.
      82                 :            :         // This is a weaker form of `addrescaped` since `hasload` can still be used
      83                 :            :         // to see if the memory is actually being used
      84                 :            :         bool hasunknownmem:1;
      85                 :            :         // The object is returned
      86                 :            :         bool returned:1;
      87                 :            :         // The object is used in an error function
      88                 :            :         bool haserror:1;
      89                 :            : 
      90                 :         32 :         void reset()
      91                 :            :         {
      92                 :         32 :             escaped = false;
      93                 :         32 :             addrescaped = false;
      94                 :         32 :             hasload = false;
      95                 :         32 :             haspreserve = false;
      96                 :         32 :             refload = false;
      97                 :         32 :             refstore = false;
      98                 :         32 :             hastypeof = false;
      99                 :         32 :             hasunknownmem = false;
     100                 :         32 :             returned = false;
     101                 :         32 :             haserror = false;
     102                 :         32 :             uses.clear();
     103                 :         32 :             preserves.clear();
     104                 :         32 :             memops.clear();
     105                 :         32 :         }
     106                 :            :         void dump();
     107                 :            :         bool addMemOp(llvm::Instruction *inst, unsigned opno, uint32_t offset, llvm::Type *elty,
     108                 :            :                       bool isstore, const llvm::DataLayout &DL);
     109                 :            :         std::pair<const uint32_t,Field> &getField(uint32_t offset, uint32_t size, llvm::Type *elty);
     110                 :         26 :         std::map<uint32_t,Field>::iterator findLowerField(uint32_t offset)
     111                 :            :         {
     112                 :            :             // Find the last field that starts no higher than `offset`.
     113                 :         26 :             auto it = memops.upper_bound(offset);
     114         [ -  + ]:         26 :             if (it != memops.begin())
     115                 :          0 :                 return --it;
     116                 :         26 :             return memops.end();
     117                 :            :         }
     118                 :            :     };
     119                 :            : 
     120                 :            :     struct EscapeAnalysisRequiredArgs {
     121                 :            :         AllocUseInfo &use_info; // The returned escape analysis data
     122                 :            :         CheckInst::Stack &check_stack; // A preallocated stack to be used for escape analysis
     123                 :            :         JuliaPassContext &pass; // The current optimization pass (for accessing intrinsic functions)
     124                 :            :         const llvm::DataLayout &DL; // The module's data layout (for handling GEPs/memory operations)
     125                 :            :     };
     126                 :            : 
     127                 :            :     struct EscapeAnalysisOptionalArgs {
     128                 :            :         //A set of basic blocks to run escape analysis over. Uses outside these basic blocks
     129                 :            :         //will not be considered. Defaults to nullptr, which means all uses of the allocation
     130                 :            :         //are considered
     131                 :            :         const llvm::SmallPtrSetImpl<const llvm::BasicBlock*> *valid_set;
     132                 :            : 
     133                 :            :         EscapeAnalysisOptionalArgs() = default;
     134                 :            : 
     135                 :          8 :         EscapeAnalysisOptionalArgs &with_valid_set(decltype(valid_set) valid_set) {
     136                 :          8 :             this->valid_set = valid_set;
     137                 :          8 :             return *this;
     138                 :            :         }
     139                 :            :     };
     140                 :            : 
     141                 :            :     void runEscapeAnalysis(llvm::Instruction *I, EscapeAnalysisRequiredArgs required, EscapeAnalysisOptionalArgs options=EscapeAnalysisOptionalArgs());
     142                 :            : }
     143                 :            : 
     144                 :            : 
     145                 :            : #endif