Skip to content

Latest commit

 

History

History
387 lines (304 loc) · 14.5 KB

10. Codice intermedio.md

File metadata and controls

387 lines (304 loc) · 14.5 KB
Raw

LLVM basics

Il suffisso .ll è tipico del human-readable format della IR - Intermediate Representation - di LLVM.

llvm-as file.ll  // human readable IR
lc file.bc  // bitcode into assembly (file.s)

#Nota .bc è machine independent, mentre .s è machine dependent

Un compilatore è composto da:

  • front-end - quello fatto fin'ora
  • middle-end machine independent optimization
  • back-end - -machine dependent optimization, allocazione registri, etc.

Modello di calcolo

Modello URM - Unlimited Register Machine: il modello di calcolo per la IR è una macchina con numero illimitato di registri

I registri sono di tipo SSA - Single Static Assignment: staticamente ogni istruzione scrive su un registro differente; questo non vuol dire che avvenga una sola scrittura dinamicamente! Infatti a tempo di esecuzione su quel registro potranno avvenire più scritture.

Controllo di flusso

Il LLVM esiste un'istruzione phi:

phi tipo [val1, pred1], [val2, pred2], ...

Un programma in IR è composto da uno o più moduli -> ognuno è un file in formato assembly o bitcode.

Variabili locali: iniziano con % Variabili globali: iniziano con @

Un basic block è un blocco di istruzioni che non contiene istruzioni di salto, se non in fondo. Ogni block è identificato da una label. Quindi i BB sono terminati da un return o da un salto.

I BB formano un grafo detto grafo del flusso di esecuzione: Control Flow Graph - CFG

#Nota che può avere comunque una chiamata di funzione

Clang LLVM IR

Per compilare un file Cpp in IR human-readable possiamo usare:

clang++ -S -c -emit-llvm file.cpp -I/usr/lib/llvm-16/include

Compilando una funzione scritta in Cpp notiamo:

  • ha una @ come prefisso -> nome di funzione esportato globalmente
  • il codice human readable è ridondante #Nota che la corrispondenza tra istruzione e registro è biunivoca: quindi il numero di istruzione e quello di registro (se usato) coincidono

; preds = %1 definisce l'arco entrante del CFG

I registri virtuali sono anonimi. In caso di assenza di nome si progredisce nella numerazione. Il programmatore può definire i registri assegnando nomi simbolici.

I registri e e le operazioni sono tipizzati:

  • i32 -> intero a 32 bit
  • align 4 - > allinea a 4 byte

Se devo modificare una variabile in punti diversi dell'IR è necessario appoggiarsi allo stack. La memoria è riscrivibile senza vincoli, i registri solo dalla stessa istruzione.

Esempio: stampa da 1 a 10

@fmt = constant [4 x i8] c"%d\0A\00"  ; dichiara 32 bit costanti che contengono '%', 'd', '\n', terminatore_di_stringa
declare i32 @printf(i8*, i32)

define i32 @main(){
init:
	%counter = alloca i32
	store i32 0, i32* %counter
	br label %loop
loop:
	%currval = load i32, i32* %counter
	%nextval = add i32 %currval, 1
	%end = icmp eq i32 %nextval, 11  ; integer compare
	br i1 %end, label %exit, label cont
cont:
	sotre i32 %nextval, i32* %counter
	call i32(i8*, i32) @printf(i8*, getlementptr([4 x i8], [4 x i8]* @fmt, i32 0, i32 0), i32 &nextval)
exit:
	ret i32 0
}

Come eseguirlo? esiste un interprete JIT chiamato lli

Classi dell'infrastruttura LLVM

Scritta interamente in C++:

  • LLVMContext: classe opaca di cui non è necessario conoscere i dettagli implementativi. Mantiene lo stato. Istanziata una volta e passata in giro. Mantiene, per esempio, i tipi di dato definiti dinamicamente. #Nota che si possono allocare interi a N bit, con N arbitrario, potenzialmente molto grande.
  • Module: mantiene definizione di funzioni esterne. È composto da più funzioni. Corrisponde grezzamente a un file.
  • Function: si aggiungono funzioni che verranno infine emesse. È composto da più BasicBlock.
  • BasicBlock: contiene del codice intermedio dipendente dal costrutto da rappresentare
  • IRBuilder: contiene metodi builder per costruire basic blocks
  • Value: tipicamente risultato di IRBuilder.

Function

I metodi della classe Function che useremo sono:

  • getEntryBlock() - puntatore al BB iniziale della funzione
  • insert() - inserisce BB in un determinato punto della funzione
  • end() - fine attuale del body della funzione
  • eraseFromParent()

IRBuilder

  • CrateFAdd()
  • CrateFNeg()
  • ...

Dove F - float - significa che il numero è rappresentato in virgola mobile, non da informazioni sulla precisione.

Note su Kaleidoscope 1.0

Le espressioni top-level, per come abbiamo definito la grammatica del linguaggio, non hanno valore semantico. A livello sintattico sono corrette.

Il motivo è il seguente:

  • non si possono definire variabili top-level, perché non gestiamo l'assegnamento della memoria
  • si può usare un identificatore senza valore, ma non porterà a nessun risultato
  • solo al momento del passaggio (parametri attuali) è consentito l'assegnamento

Vengono quindi compilate come espressioni anonime per non perderne il valore.

Modifica alla grammatica: rimuoviamo le espressioni top level perché senza assegnamenti sono momentaneamente utili.

#Nota noemit() chiamato su PrototypeAST

In RootAST scrive il parser, quando esegue la riduzione dell'assioma.

Aggiungiamo a driver il metodo "top-level" codegen per la generazione di codice, seguendo l'AST. Ogni foglia dell'AST genererà poco codice.

Generazione di codice

  • Module - avremo bisogno di un solo modulo, dato che scriveremo su un solo file
  • LLVMContext - è una classe opaca
  • IRBuilder - contiene i metodi che generano le istruzioni

#Nota l'inizializzazione della location significa importare riga e colonna a 0

Tutte le codegen ritornano un oggetto di tipo Value. Ricorda che LLVM usa un modello di calcolo SSA. Ogni blocco di codice lascia il risultato calcolato in un registro, ritornato proprio in Value.

Sequence

if (first) Vale *f = fist->codegen(driver);
if (continuation) Value *c = first->codegen(driver);
return nullptr;

Binary expression

Value *l = lhs->codegen(driver);
Value *r = rhs->codegen(driver);
if (!l || !r) return nullptr;
switch (op) {
	case '+': return builder->CreateFAdd(L, R, "addres");
	case '-': return builder->CreateFSub(L, R, "subres");
	case '*': return builder->CreateFMul(L, R, "mulres");
	case '/': return builder->CreateFDiv(L, R, "divres");
}

Number expression

return ConstantFp::get(*context, APFloat(Val));

Perché passiamo in contesto? perché le costanti devono essere uniche. Verranno rese unicamente nel file finale. Questo vale per costanti e tipi.

Quindi... la get è in realtà un metodo di accesso alla struttura associativa, con un valore di ritorno di default, che viene inserito pure nella struttura se non esiste.

Perché la chiamata a APFloat? perché altrimenti ci sarebbe una discordanza di tipo. Questa chiamata crea la rappresentazione accettata anche da parser.

Variable expression

Per il momento l'unico momento in cui usiamo variabili è per l'invocazione di funzioni. Il valore della varaibile diventa noto a tempo di esecuzione.

static AllocInst* CreateEntryBlockAlloca(Function *fun, StringRef varName) {
	IRBuilder<> TmpB(&fun->getEntryBlock(),);
	return TmpB.createAlloca(  // builder per l'istruzione di allocazione
		Type::getDoubleTy(*context),  // dimensione del tipo double, 8 byte
		nullptr,
		varName  // restitusce il puntatore a questa zona qui
	);
}

La tabella associa ad ogni variabile una istruzione. alloca alloca uno spazio sufficiente (per ora solo double, 8 byte) e restituisce lo spazio allocato mediante un registro SSA.

AllocaInst è il tipo di un'istruzione di allocazione in LLVM. Parametri:

  • fun è una funzione. Oggetto funzione LLVM
  • varName è il nome della variabile TmpB è un builder temporaneo, per non interferire con quello globale, in quanto tiene conto di quanto ha scritto finora.

Ad esempio: x+1 costruisce un AST binario con op + nel mezzo, x come LHS e 1 come RHS L'utilizzo di x implica l'accesso alla symbol table.

Value* VariableExprAST::godegen(driver &drv) {
	AllocaInst *a = drv.NamedValues[Name];
	if (!a) return LogErrorV("Variabile non definita");  // errore semantico: uso di variabile non definita
	return builder->CreateLoad(A->getAllocatedType(), A, Name.c_str());
	// L'istruzione di allocazione contiene il registro in cui sarà salvato il puntatore all'area di memoria allocata. Name.c_str() è il nome del registro. Passare A (istruzione) equivale a passare il registro, dato il paradigma SSA.
}

Usare una variabile si traduce nel caricare il valore in un registro.

Call expression

La funzione, per essere chiamata, deve essere stata definita.

Function *calleeF = module->getFunction(callee);  // callee è memorizzato dal nodo

if (!calleeF) return LogErrorV("Funzione non definita");

// Controllo semantico di corrispondenza tra il numero di parametri formali e attuali. Args è memorizzato nel nodo dell'AST e rappresenta i parametri attuali. calleeF->arg_size() corrisponde al numero di paratmetrformali.
if (calleeF->arg_size() != Args.size()) return LogErrorV("Numero di argomenti incompatibile")

// I parametri attuali possono essere espressioni arbitrariamente complesse
std::vector<Value*> argsV;

for (double arg : Args) {
	argsV.push_back(arg->codegen(driver));
	if (!argsV.back()) return nullptr
}

// "calltmp" è il nome di un registro contenente il valore di ritorno
return builder->CreateCall(CalleF, argsV, "calltmp");

Function Prototype

Tipo di una funzione = tipo del valore di ritorno + tipo dei parametri

Dati n parametri una funzione è identificata da n+1 tipi. Nel nostro caso tutti double.

// Passiamo per getDoubleTy per ottenere la rappresentazione unica del tipo
std::vector<Type*> Doubles(Args.size(), Type::getDoubleTy(*context));

// Vale la stessa regola di univocità per i tipi di funzione
FunctionType *FT = FunctionType::get(Type::getDoubleTy(*context), Doubles, false);

// ExternalLinkage -> funzione visibile all'esterno del modulo
Function *F = Function::Create(FT, Function::ExternalLinkage, Name, *module);

unsigned Idx = 0;
for (auto &Arg : F->args()) {
	Arg.setName(Args[Idx++]);  // copio i nomi degli argomenti nella rappr LLVM
}

if (emitcode) {
	// print on stderr F's representation
}

emitcode serve a attivare o disattivare la emissione di codice relativo alla funzione. Il codice viene emesso solo nel caso di dichiarazione external.

La emissione riduzione del prototipo viene fatta due volte -> avremmo un errore di ridefinizione della funzione, dato che il codice viene generato sia per def che per il singolo proto.

Function

// Si verifica che la funzione non sia duplicata
Function *f = module->getFunction(std::get<std::string>(Proto->getLexVal()));
if (!function) f = Proto->godegen(driver);
else return nullptr;

if (!function) return nullptr;  // In caso di errore durante la generazione

BasicBlock *BB = BasicBlock::Create(*context, 'entry', function);
builder->SetInsertPoint(BB);

for (auto &arg : function>args()) {
	AllocaInsta *a = BasicBlock::Alloca(function, arg.getName());
	// Nota che genera un'istruzione di allocazione che ritorna un puntatore alla memoria.
	builder->CreateStore(&arg, a);
	drv.NamedValues[std::string(arg.getName())] = a;
	// Quando userò la variabile recupererò ad esempio %x1 = alloca double, align 8; dalla symbol table recupero l'indirizzo contenuto in %x1
}

if (Value *RetVal = Body->codegen(drv)) {
	builder->CreateRet(RetVal);
	verifyFunction(function);
	function->print(errs());
}

#Nota che l'incrementale per i registri è globale, non locale per ogni variabile

Linking esterno Cpp - Kaleidoscope

Linkage globale delle funzioni che voglio esportare dal modulo C++:

extern "C" {
	double x();
	double y();
	double printval(double);
}

double x() {
	double tmp;
	std::cout << "Immetti x: "; std::cin >> tmp;
	return tmp;
}

double y() {
	double tmp;
	std::cout << "Immetti y: "; std::cin >> tmp:
	return tmp;
}

double printval(double x) {
	std::cout << x << std::endl;
}

Estendiamo il linguaggio

Iniziamo aggiungendo l'operatore ternario e gli operatori di confronto.

  1. aggiungiamo QMARK, COLON, LT, EQ tra i simboli riconosciuti dal lexer
  2. aggiungiamo il codice per creare gli oggetti associati
  3. introduciamo una nuova categoria sintattica: expif
  4. l'oggetto costruito è: expif: condexp "?" exp ":" exp {$$ = new IfExprAST($1, $3, $5)}
  5. definiamo ricorsivamente condexp: exp "<" exp {$$ = new BinaryExprAST('<', $1, $3)}

#Esercizio implementa l'operatore ternario

-Wcounterexamples mostra comportamenti ambigui del parser

Implementazione operatore ternario

Abbiamo introdotto:

  • la classe IfExprAST
  • supporto da parte dalle espressioni a < e =

IfExprAST è caratterizzata da 3 figli:

  • test
  • true branch
  • false branch

Dovremo:

  1. scrivere valutazione dell'espressione
  2. test
  3. salto condizionato a true/false block
  4. true/false code
  5. jump incondizionato alla giunzione
  6. codice true/false
  7. jump incondizionato alla giunzione
  8. codice di giunzione
Value* IfExprAST::codegen(driver &drv) {
	Value *testVal = condExp->codegen(drv);
	if (!testVal) return nullptr;

	Function *parent = builder->GetInsertBlock()->getParent();
	BasicBlock *trueBB = BasicBlock::Create(*context, 'trueblock', parent);
	// BasicBlock *trueBB = BasicBlock::Create(*context, 'falseblock', fun);  Creare il blocco false sarebbe sbagliato, in quanto si accoderebbe al blocco false. Deve essere lasciato floating
	BasicBlock *falseBB = BasicBlock::Create(*context, 'falseblock');
	BasicBlock *mergeBB = BasicBlock::Create(*context, 'mergeblock');
	builer->createCondBr(testVal, trueBB, falseBB);

	builder->SetInsertPoint(trueBB);
	Value *trueVal = trueExp->codegen(drv);
	if (!trueVal) return nullptr;
	// dobbiamo inserire il salto incondizionato al merge block
	// il merge block avrà al suo interno un'istruzione phi
	// bisogna aggiornre il blocco dal quale si salta al merge block
	// con if annidati è l'ultimo merge block dell'if annidato
	trueBB = builder->getInsertBlock();
	buidler->CreateBr(mergeBB);

	parent->insert(parent->end, falseBB);
	builer->SetInsertPoint(falseBB);
	Value *falseVal = falseExp->codegen(drv);
	if (!falseVal) return nullptr;
	falseBB = builder->getInsertBlock();
	builder->createBr(mergeBB);

	fun->insert(parent->end, mergeBB);
	builder->SetInsertPoint(mergeBB);
	PHINode *p = builder->CreatePHI(Type::getDoubleTy(*context), 2);
	// l'istruzione phi è un'istruzione e come tale ha un registro SSA associato
	// questo registro sarà popolato con trueVal se il flusso viene da trueBB
	// sarà popolato con falseVal altrimenti
	p->addIncoming(trueVal, trueBB);
	p->addIncoming(falseVal, valseBB);
	return p;
}

Implementazione di un for

Sono 5 blocchi al posto che 3:

  • inizializzazione
  • condizione
  • aggionrnamento
  • corpo
  • merge

Molto simile all'if.