1//===-- BrainF.cpp - BrainF compiler example ------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This class compiles the BrainF language into LLVM assembly.
10//
11// The BrainF language has 8 commands:
12// Command Equivalent C Action
13// ------- ------------ ------
14// , *h=getchar(); Read a character from stdin, 255 on EOF
15// . putchar(*h); Write a character to stdout
16// - --*h; Decrement tape
17// + ++*h; Increment tape
18// < --h; Move head left
19// > ++h; Move head right
20// [ while(*h) { Start loop
21// ] } End loop
22//
23//===----------------------------------------------------------------------===//
24
25#include "BrainF.h"
26#include "llvm/ADT/APInt.h"
27#include "llvm/IR/BasicBlock.h"
28#include "llvm/IR/Constant.h"
29#include "llvm/IR/Constants.h"
30#include "llvm/IR/DerivedTypes.h"
31#include "llvm/IR/Function.h"
32#include "llvm/IR/GlobalValue.h"
33#include "llvm/IR/GlobalVariable.h"
34#include "llvm/IR/InstrTypes.h"
35#include "llvm/IR/Instruction.h"
36#include "llvm/IR/Instructions.h"
37#include "llvm/IR/Intrinsics.h"
38#include "llvm/IR/Module.h"
39#include "llvm/IR/Type.h"
40#include "llvm/Support/Casting.h"
41#include <cstdlib>
42#include <iostream>
43
44using namespace llvm;
45
46//Set the constants for naming
47const char *BrainF::tapereg = "tape";
48const char *BrainF::headreg = "head";
49const char *BrainF::label = "brainf";
50const char *BrainF::testreg = "test";
51
52Module *BrainF::parse(std::istream *in1, int mem, CompileFlags cf,
53 LLVMContext& Context) {
54 in = in1;
55 memtotal = mem;
56 comflag = cf;
57
58 header(C&: Context);
59 readloop(phi: nullptr, oldbb: nullptr, testbb: nullptr, Context);
60 delete builder;
61 return module;
62}
63
64void BrainF::header(LLVMContext& C) {
65 module = new Module("BrainF", C);
66
67 //Function prototypes
68
69 //declare void @llvm.memset.p0i8.i32(i8 *, i8, i32, i1)
70 Type *Tys[] = {PointerType::getUnqual(C), Type::getInt32Ty(C)};
71 Function *memset_func = Intrinsic::getDeclaration(M: module, Intrinsic::id: memset,
72 Tys);
73
74 //declare i32 @getchar()
75 getchar_func =
76 module->getOrInsertFunction(Name: "getchar", RetTy: IntegerType::getInt32Ty(C));
77
78 //declare i32 @putchar(i32)
79 putchar_func = module->getOrInsertFunction(
80 Name: "putchar", RetTy: IntegerType::getInt32Ty(C), Args: IntegerType::getInt32Ty(C));
81
82 //Function header
83
84 //define void @brainf()
85 brainf_func = Function::Create(Ty: FunctionType::get(Result: Type::getVoidTy(C), isVarArg: false),
86 Linkage: Function::ExternalLinkage, N: "brainf", M: module);
87
88 builder = new IRBuilder<>(BasicBlock::Create(Context&: C, Name: label, Parent: brainf_func));
89
90 //%arr = malloc i8, i32 %d
91 ConstantInt *val_mem = ConstantInt::get(Context&: C, V: APInt(32, memtotal));
92 Type* IntPtrTy = IntegerType::getInt32Ty(C);
93 Type* Int8Ty = IntegerType::getInt8Ty(C);
94 Constant* allocsize = ConstantExpr::getSizeOf(Ty: Int8Ty);
95 allocsize = ConstantExpr::getTruncOrBitCast(C: allocsize, Ty: IntPtrTy);
96 ptr_arr = builder->CreateMalloc(IntPtrTy, AllocTy: Int8Ty, AllocSize: allocsize, ArraySize: val_mem, MallocF: nullptr,
97 Name: "arr");
98
99 //call void @llvm.memset.p0i8.i32(i8 *%arr, i8 0, i32 %d, i1 0)
100 {
101 Value *memset_params[] = {
102 ptr_arr,
103 ConstantInt::get(Context&: C, V: APInt(8, 0)),
104 val_mem,
105 ConstantInt::get(Context&: C, V: APInt(1, 0))
106 };
107
108 CallInst *memset_call = builder->
109 CreateCall(Callee: memset_func, Args: memset_params);
110 memset_call->setTailCall(false);
111 }
112
113 //%arrmax = getelementptr i8 *%arr, i32 %d
114 if (comflag & flag_arraybounds) {
115 ptr_arrmax = builder->CreateGEP(
116 Ty: Int8Ty, Ptr: ptr_arr, IdxList: ConstantInt::get(Context&: C, V: APInt(32, memtotal)), Name: "arrmax");
117 }
118
119 //%head.%d = getelementptr i8 *%arr, i32 %d
120 curhead = builder->CreateGEP(
121 Ty: Int8Ty, Ptr: ptr_arr, IdxList: ConstantInt::get(Context&: C, V: APInt(32, memtotal / 2)), Name: headreg);
122
123 //Function footer
124
125 //brainf.end:
126 endbb = BasicBlock::Create(Context&: C, Name: label, Parent: brainf_func);
127
128 // call free(i8 *%arr)
129 builder->SetInsertPoint(endbb);
130 builder->CreateFree(Source: ptr_arr);
131
132 //ret void
133 ReturnInst::Create(C, InsertAtEnd: endbb);
134
135 //Error block for array out of bounds
136 if (comflag & flag_arraybounds)
137 {
138 //@aberrormsg = internal constant [%d x i8] c"\00"
139 Constant *msg_0 =
140 ConstantDataArray::getString(Context&: C, Initializer: "Error: The head has left the tape.",
141 AddNull: true);
142
143 GlobalVariable *aberrormsg = new GlobalVariable(
144 *module,
145 msg_0->getType(),
146 true,
147 GlobalValue::InternalLinkage,
148 msg_0,
149 "aberrormsg");
150
151 //declare i32 @puts(i8 *)
152 FunctionCallee puts_func = module->getOrInsertFunction(
153 Name: "puts", RetTy: IntegerType::getInt32Ty(C),
154 Args: PointerType::getUnqual(ElementType: IntegerType::getInt8Ty(C)));
155
156 //brainf.aberror:
157 aberrorbb = BasicBlock::Create(Context&: C, Name: label, Parent: brainf_func);
158
159 //call i32 @puts(i8 *getelementptr([%d x i8] *@aberrormsg, i32 0, i32 0))
160 {
161 Constant *zero_32 = Constant::getNullValue(Ty: IntegerType::getInt32Ty(C));
162
163 Constant *gep_params[] = {
164 zero_32,
165 zero_32
166 };
167
168 Constant *msgptr = ConstantExpr::
169 getGetElementPtr(Ty: aberrormsg->getValueType(), C: aberrormsg, IdxList: gep_params);
170
171 Value *puts_params[] = {
172 msgptr
173 };
174
175 CallInst *puts_call =
176 CallInst::Create(Func: puts_func,
177 Args: puts_params,
178 NameStr: "", InsertAtEnd: aberrorbb);
179 puts_call->setTailCall(false);
180 }
181
182 //br label %brainf.end
183 BranchInst::Create(IfTrue: endbb, InsertAtEnd: aberrorbb);
184 }
185}
186
187void BrainF::readloop(PHINode *phi, BasicBlock *oldbb, BasicBlock *testbb,
188 LLVMContext &C) {
189 Symbol cursym = SYM_NONE;
190 int curvalue = 0;
191 Symbol nextsym = SYM_NONE;
192 int nextvalue = 0;
193 char c;
194 int loop;
195 int direction;
196 Type *Int8Ty = IntegerType::getInt8Ty(C);
197
198 while(cursym != SYM_EOF && cursym != SYM_ENDLOOP) {
199 // Write out commands
200 switch(cursym) {
201 case SYM_NONE:
202 // Do nothing
203 break;
204
205 case SYM_READ:
206 {
207 //%tape.%d = call i32 @getchar()
208 CallInst *getchar_call =
209 builder->CreateCall(Callee: getchar_func, Args: {}, Name: tapereg);
210 getchar_call->setTailCall(false);
211 Value *tape_0 = getchar_call;
212
213 //%tape.%d = trunc i32 %tape.%d to i8
214 Value *tape_1 = builder->
215 CreateTrunc(V: tape_0, DestTy: IntegerType::getInt8Ty(C), Name: tapereg);
216
217 //store i8 %tape.%d, i8 *%head.%d
218 builder->CreateStore(Val: tape_1, Ptr: curhead);
219 }
220 break;
221
222 case SYM_WRITE:
223 {
224 //%tape.%d = load i8 *%head.%d
225 LoadInst *tape_0 = builder->CreateLoad(Ty: Int8Ty, Ptr: curhead, Name: tapereg);
226
227 //%tape.%d = sext i8 %tape.%d to i32
228 Value *tape_1 = builder->
229 CreateSExt(V: tape_0, DestTy: IntegerType::getInt32Ty(C), Name: tapereg);
230
231 //call i32 @putchar(i32 %tape.%d)
232 Value *putchar_params[] = {
233 tape_1
234 };
235 CallInst *putchar_call = builder->
236 CreateCall(Callee: putchar_func,
237 Args: putchar_params);
238 putchar_call->setTailCall(false);
239 }
240 break;
241
242 case SYM_MOVE:
243 {
244 //%head.%d = getelementptr i8 *%head.%d, i32 %d
245 curhead = builder->CreateGEP(Ty: Int8Ty, Ptr: curhead,
246 IdxList: ConstantInt::get(Context&: C, V: APInt(32, curvalue)),
247 Name: headreg);
248
249 //Error block for array out of bounds
250 if (comflag & flag_arraybounds)
251 {
252 //%test.%d = icmp uge i8 *%head.%d, %arrmax
253 Value *test_0 = builder->
254 CreateICmpUGE(LHS: curhead, RHS: ptr_arrmax, Name: testreg);
255
256 //%test.%d = icmp ult i8 *%head.%d, %arr
257 Value *test_1 = builder->
258 CreateICmpULT(LHS: curhead, RHS: ptr_arr, Name: testreg);
259
260 //%test.%d = or i1 %test.%d, %test.%d
261 Value *test_2 = builder->
262 CreateOr(LHS: test_0, RHS: test_1, Name: testreg);
263
264 //br i1 %test.%d, label %main.%d, label %main.%d
265 BasicBlock *nextbb = BasicBlock::Create(Context&: C, Name: label, Parent: brainf_func);
266 builder->CreateCondBr(Cond: test_2, True: aberrorbb, False: nextbb);
267
268 //main.%d:
269 builder->SetInsertPoint(nextbb);
270 }
271 }
272 break;
273
274 case SYM_CHANGE:
275 {
276 //%tape.%d = load i8 *%head.%d
277 LoadInst *tape_0 = builder->CreateLoad(Ty: Int8Ty, Ptr: curhead, Name: tapereg);
278
279 //%tape.%d = add i8 %tape.%d, %d
280 Value *tape_1 = builder->
281 CreateAdd(LHS: tape_0, RHS: ConstantInt::get(Context&: C, V: APInt(8, curvalue)), Name: tapereg);
282
283 //store i8 %tape.%d, i8 *%head.%d\n"
284 builder->CreateStore(Val: tape_1, Ptr: curhead);
285 }
286 break;
287
288 case SYM_LOOP:
289 {
290 //br label %main.%d
291 BasicBlock *testbb = BasicBlock::Create(Context&: C, Name: label, Parent: brainf_func);
292 builder->CreateBr(Dest: testbb);
293
294 //main.%d:
295 BasicBlock *bb_0 = builder->GetInsertBlock();
296 BasicBlock *bb_1 = BasicBlock::Create(Context&: C, Name: label, Parent: brainf_func);
297 builder->SetInsertPoint(bb_1);
298
299 // Make part of PHI instruction now, wait until end of loop to finish
300 PHINode *phi_0 = PHINode::Create(Ty: PointerType::getUnqual(ElementType: Int8Ty), NumReservedValues: 2,
301 NameStr: headreg, InsertAtEnd: testbb);
302 phi_0->addIncoming(V: curhead, BB: bb_0);
303 curhead = phi_0;
304
305 readloop(phi: phi_0, oldbb: bb_1, testbb, C);
306 }
307 break;
308
309 default:
310 std::cerr << "Error: Unknown symbol.\n";
311 abort();
312 break;
313 }
314
315 cursym = nextsym;
316 curvalue = nextvalue;
317 nextsym = SYM_NONE;
318
319 // Reading stdin loop
320 loop = (cursym == SYM_NONE)
321 || (cursym == SYM_MOVE)
322 || (cursym == SYM_CHANGE);
323 while(loop) {
324 *in>>c;
325 if (in->eof()) {
326 if (cursym == SYM_NONE) {
327 cursym = SYM_EOF;
328 } else {
329 nextsym = SYM_EOF;
330 }
331 loop = 0;
332 } else {
333 direction = 1;
334 switch(c) {
335 case '-':
336 direction = -1;
337 [[fallthrough]];
338
339 case '+':
340 if (cursym == SYM_CHANGE) {
341 curvalue += direction;
342 // loop = 1
343 } else {
344 if (cursym == SYM_NONE) {
345 cursym = SYM_CHANGE;
346 curvalue = direction;
347 // loop = 1
348 } else {
349 nextsym = SYM_CHANGE;
350 nextvalue = direction;
351 loop = 0;
352 }
353 }
354 break;
355
356 case '<':
357 direction = -1;
358 [[fallthrough]];
359
360 case '>':
361 if (cursym == SYM_MOVE) {
362 curvalue += direction;
363 // loop = 1
364 } else {
365 if (cursym == SYM_NONE) {
366 cursym = SYM_MOVE;
367 curvalue = direction;
368 // loop = 1
369 } else {
370 nextsym = SYM_MOVE;
371 nextvalue = direction;
372 loop = 0;
373 }
374 }
375 break;
376
377 case ',':
378 if (cursym == SYM_NONE) {
379 cursym = SYM_READ;
380 } else {
381 nextsym = SYM_READ;
382 }
383 loop = 0;
384 break;
385
386 case '.':
387 if (cursym == SYM_NONE) {
388 cursym = SYM_WRITE;
389 } else {
390 nextsym = SYM_WRITE;
391 }
392 loop = 0;
393 break;
394
395 case '[':
396 if (cursym == SYM_NONE) {
397 cursym = SYM_LOOP;
398 } else {
399 nextsym = SYM_LOOP;
400 }
401 loop = 0;
402 break;
403
404 case ']':
405 if (cursym == SYM_NONE) {
406 cursym = SYM_ENDLOOP;
407 } else {
408 nextsym = SYM_ENDLOOP;
409 }
410 loop = 0;
411 break;
412
413 // Ignore other characters
414 default:
415 break;
416 }
417 }
418 }
419 }
420
421 if (cursym == SYM_ENDLOOP) {
422 if (!phi) {
423 std::cerr << "Error: Extra ']'\n";
424 abort();
425 }
426
427 // Write loop test
428 {
429 //br label %main.%d
430 builder->CreateBr(Dest: testbb);
431
432 //main.%d:
433
434 //%head.%d = phi i8 *[%head.%d, %main.%d], [%head.%d, %main.%d]
435 //Finish phi made at beginning of loop
436 phi->addIncoming(V: curhead, BB: builder->GetInsertBlock());
437 Value *head_0 = phi;
438
439 //%tape.%d = load i8 *%head.%d
440 LoadInst *tape_0 = new LoadInst(Int8Ty, head_0, tapereg, testbb);
441
442 //%test.%d = icmp eq i8 %tape.%d, 0
443 ICmpInst *test_0 = new ICmpInst(*testbb, ICmpInst::ICMP_EQ, tape_0,
444 ConstantInt::get(Context&: C, V: APInt(8, 0)), testreg);
445
446 //br i1 %test.%d, label %main.%d, label %main.%d
447 BasicBlock *bb_0 = BasicBlock::Create(Context&: C, Name: label, Parent: brainf_func);
448 BranchInst::Create(IfTrue: bb_0, IfFalse: oldbb, Cond: test_0, InsertAtEnd: testbb);
449
450 //main.%d:
451 builder->SetInsertPoint(bb_0);
452
453 //%head.%d = phi i8 *[%head.%d, %main.%d]
454 PHINode *phi_1 =
455 builder->CreatePHI(Ty: PointerType::getUnqual(ElementType: Int8Ty), NumReservedValues: 1, Name: headreg);
456 phi_1->addIncoming(V: head_0, BB: testbb);
457 curhead = phi_1;
458 }
459
460 return;
461 }
462
463 //End of the program, so go to return block
464 builder->CreateBr(Dest: endbb);
465
466 if (phi) {
467 std::cerr << "Error: Missing ']'\n";
468 abort();
469 }
470}
471

source code of llvm/examples/BrainF/BrainF.cpp