1 // Package ircheck implements a checker for LLVM IR, that goes a bit further
2 // than the regular LLVM IR verifier. Note that it checks different things, so
3 // this is not a replacement for the LLVM verifier but does catch things that
4 // the LLVM verifier doesn't catch.
5 package ircheck
6 7 import (
8 "errors"
9 "fmt"
10 11 "tinygo.org/x/go-llvm"
12 )
13 14 type checker struct {
15 ctx llvm.Context
16 }
17 18 func (c *checker) checkType(t llvm.Type, checked map[llvm.Type]struct{}, specials map[llvm.TypeKind]llvm.Type) error {
19 // prevent infinite recursion for self-referential types
20 if _, ok := checked[t]; ok {
21 return nil
22 }
23 checked[t] = struct{}{}
24 25 // check for any context mismatches
26 switch {
27 case t.Context() == c.ctx:
28 // this is correct
29 case t.Context() == llvm.GlobalContext():
30 // somewhere we accidentally used the global context instead of a real context
31 return fmt.Errorf("type %q uses global context", t.String())
32 default:
33 // we used some other context by accident
34 return fmt.Errorf("type %q uses context %v instead of the main context %v", t.String(), t.Context(), c.ctx)
35 }
36 37 // if this is a composite type, check the components of the type
38 switch t.TypeKind() {
39 case llvm.VoidTypeKind, llvm.LabelTypeKind, llvm.TokenTypeKind, llvm.MetadataTypeKind:
40 // there should only be one of any of these
41 if s, ok := specials[t.TypeKind()]; !ok {
42 specials[t.TypeKind()] = t
43 } else if s != t {
44 return fmt.Errorf("duplicate special type %q: %v and %v", t.TypeKind().String(), t, s)
45 }
46 case llvm.FloatTypeKind, llvm.DoubleTypeKind, llvm.X86_FP80TypeKind, llvm.FP128TypeKind, llvm.PPC_FP128TypeKind:
47 // floating point numbers are primitives - nothing to recurse
48 case llvm.IntegerTypeKind:
49 // integers are primitives - nothing to recurse
50 case llvm.FunctionTypeKind:
51 // check arguments and return(s)
52 for i, v := range t.ParamTypes() {
53 if err := c.checkType(v, checked, specials); err != nil {
54 return fmt.Errorf("failed to verify argument %d of type %s: %s", i, t.String(), err.Error())
55 }
56 }
57 if err := c.checkType(t.ReturnType(), checked, specials); err != nil {
58 return fmt.Errorf("failed to verify return type of type %s: %s", t.String(), err.Error())
59 }
60 case llvm.StructTypeKind:
61 // check all elements
62 for i, v := range t.StructElementTypes() {
63 if err := c.checkType(v, checked, specials); err != nil {
64 return fmt.Errorf("failed to verify type of field %d of struct type %s: %s", i, t.String(), err.Error())
65 }
66 }
67 case llvm.ArrayTypeKind:
68 // check element type
69 if err := c.checkType(t.ElementType(), checked, specials); err != nil {
70 return fmt.Errorf("failed to verify element type of array type %s: %s", t.String(), err.Error())
71 }
72 case llvm.PointerTypeKind:
73 // Pointers can't be checked in an opaque pointer world.
74 case llvm.VectorTypeKind:
75 // check element type
76 if err := c.checkType(t.ElementType(), checked, specials); err != nil {
77 return fmt.Errorf("failed to verify element type of vector type %s: %s", t.String(), err.Error())
78 }
79 default:
80 return fmt.Errorf("unrecognized kind %q of type %s", t.TypeKind(), t.String())
81 }
82 83 return nil
84 }
85 86 func (c *checker) checkValue(v llvm.Value, types map[llvm.Type]struct{}, specials map[llvm.TypeKind]llvm.Type) error {
87 // check type
88 if err := c.checkType(v.Type(), types, specials); err != nil {
89 return fmt.Errorf("failed to verify type of value: %s", err.Error())
90 }
91 92 // check if this is an undefined void
93 if v.IsUndef() && v.Type().TypeKind() == llvm.VoidTypeKind {
94 return errors.New("encountered undefined void value")
95 }
96 97 return nil
98 }
99 100 func (c *checker) checkInstruction(inst llvm.Value, types map[llvm.Type]struct{}, specials map[llvm.TypeKind]llvm.Type) error {
101 // check value properties
102 if err := c.checkValue(inst, types, specials); err != nil {
103 return errorAt(inst, err.Error())
104 }
105 106 // The alloca instruction can be present in every basic block. However,
107 // allocas in basic blocks other than the entry basic block have a number of
108 // problems:
109 // * They are hard to optimize, leading to potential missed optimizations.
110 // * They may cause stack overflows in loops that would otherwise be
111 // innocent.
112 // * They cause extra code to be generated, because it requires the use of
113 // a frame pointer.
114 // * Perhaps most importantly, the coroutine lowering pass of LLVM (as of
115 // LLVM 9) cannot deal with these allocas:
116 // https://llvm.org/docs/Coroutines.html
117 // Therefore, alloca instructions should be limited to the entry block.
118 if !inst.IsAAllocaInst().IsNil() {
119 if inst.InstructionParent() != inst.InstructionParent().Parent().EntryBasicBlock() {
120 return errorAt(inst, "internal error: non-static alloca")
121 }
122 }
123 124 // check operands
125 for i := 0; i < inst.OperandsCount(); i++ {
126 if err := c.checkValue(inst.Operand(i), types, specials); err != nil {
127 return errorAt(inst, fmt.Sprintf("failed to validate operand %d of instruction %q: %s", i, inst.Name(), err.Error()))
128 }
129 }
130 131 return nil
132 }
133 134 func (c *checker) checkBasicBlock(bb llvm.BasicBlock, types map[llvm.Type]struct{}, specials map[llvm.TypeKind]llvm.Type) []error {
135 // check basic block value and type
136 var errs []error
137 if err := c.checkValue(bb.AsValue(), types, specials); err != nil {
138 errs = append(errs, errorAt(bb.Parent(), fmt.Sprintf("failed to validate value of basic block %s: %v", bb.AsValue().Name(), err)))
139 }
140 141 // check instructions
142 for inst := bb.FirstInstruction(); !inst.IsNil(); inst = llvm.NextInstruction(inst) {
143 if err := c.checkInstruction(inst, types, specials); err != nil {
144 errs = append(errs, err)
145 }
146 }
147 148 return errs
149 }
150 151 func (c *checker) checkFunction(fn llvm.Value, types map[llvm.Type]struct{}, specials map[llvm.TypeKind]llvm.Type) []error {
152 // check function value and type
153 var errs []error
154 if err := c.checkValue(fn, types, specials); err != nil {
155 errs = append(errs, fmt.Errorf("failed to validate value of function %s: %s", fn.Name(), err.Error()))
156 }
157 158 // check basic blocks
159 for bb := fn.FirstBasicBlock(); !bb.IsNil(); bb = llvm.NextBasicBlock(bb) {
160 errs = append(errs, c.checkBasicBlock(bb, types, specials)...)
161 }
162 163 return errs
164 }
165 166 // Module checks the given module and returns a slice of error, if there are
167 // any.
168 func Module(mod llvm.Module) []error {
169 // check for any context mismatches
170 var errs []error
171 c := checker{
172 ctx: mod.Context(),
173 }
174 if c.ctx == llvm.GlobalContext() {
175 // somewhere we accidentally used the global context instead of a real context
176 errs = append(errs, errors.New("module uses global context"))
177 }
178 179 types := map[llvm.Type]struct{}{}
180 specials := map[llvm.TypeKind]llvm.Type{}
181 for fn := mod.FirstFunction(); !fn.IsNil(); fn = llvm.NextFunction(fn) {
182 errs = append(errs, c.checkFunction(fn, types, specials)...)
183 }
184 for g := mod.FirstGlobal(); !g.IsNil(); g = llvm.NextGlobal(g) {
185 if err := c.checkValue(g, types, specials); err != nil {
186 errs = append(errs, fmt.Errorf("failed to verify global %s of module: %s", g.Name(), err.Error()))
187 }
188 }
189 190 return errs
191 }
192