1f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines//===- DefSymParser.cpp ---------------------------------------------------===// 2f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines// 3f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines// The MCLinker Project 4f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines// 5f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines// This file is distributed under the University of Illinois Open Source 6f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines// License. See LICENSE.TXT for details. 7f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines// 8f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines//===----------------------------------------------------------------------===// 9f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines#include <mcld/Support/DefSymParser.h> 10f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines#include <mcld/Support/MsgHandling.h> 11f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines#include <mcld/LD/LDSymbol.h> 12f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 13f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hinesusing namespace llvm; 14f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hinesusing namespace mcld; 15f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 16f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen HinesDefSymParser::DefSymParser(const Module& pModule) 17f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines : m_Module(pModule) { 18f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines} 19f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 20f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines// passing a valid operator will return a number whose quantity relative 21f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines// to other such obtained quantities will give the priority of the operator 22f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hinesstatic inline int precedence(const char* x) 23f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines{ 24f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines switch (*x) { 25f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines case '-' : 26f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines case '+' : return 0; 27f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines case '/' : 28f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines case '*' : return 1; 29f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines default : assert("Unsupported operator specified"); 30f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines } 31f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines return 0; 32f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines} 33f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 34f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hinesbool DefSymParser::parse(StringRef pExpr, uint64_t& pSymVal) 35f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines{ 36f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines std::stack<const char*> operatorStack; 37f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines std::stack<unsigned long> operandStack; 38f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines unsigned long operand1 = 0, 39f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines operand2 = 0, 40f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines result = 0; 41f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines std::string token; 42f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines std::vector<std::string> postfixString; 43f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines std::vector<std::string>::iterator it; 44f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines llvm::StringRef::iterator si = pExpr.begin(); 45f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 46f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // Implement a modified Shunting Yard algorithm to form a RPN of the 47f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // given expression 48f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines while (si != pExpr.end()) { 49f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines if (*si == '+' || *si == '-' || *si == '*' || *si == '/') { 50f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines if (token.empty() && (*si == '+' || *si == '-')) 51f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // we have a case such as a++b or a+-b or a-+b 52f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // pushing 0 when a token begins with a + or - operator 53f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // solves unary operator problem 54f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines token = "0"; 55f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // An operator encountered means a token ended, push it to 56f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // postfix string queue. 57f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines postfixString.push_back(token); 58f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines token.clear(); 59f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 60f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines if (operatorStack.empty()) { 61f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines operatorStack.push(si); 62f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines } 63f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines else { 64f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines if (precedence(si) <= precedence(operatorStack.top())) { 65f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // if the precedence of incoming operator is less or equal to 66f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // top of stack, we clear stack till top is lower precedence 67f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // or its empty 68f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines while (!operatorStack.empty()) { 69f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines if (precedence(si) <= precedence(operatorStack.top())) { 70f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines postfixString.push_back(std::string(operatorStack.top(),1)); 71f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines operatorStack.pop(); 72f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines } 73f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines else { 74f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines break; 75f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines } 76f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines } 77f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines } 78f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines operatorStack.push(si); 79f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines } 80f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines si++; 81f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines continue; 82f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines } 83f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // keep reading the token when there is no operator encountered 84f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines token += *si; 85f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines si++; 86f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines } 87f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines postfixString.push_back(token); 88f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // pop off any remaining operators from operator stack 89f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines while (!operatorStack.empty()) { 90f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines postfixString.push_back(std::string(operatorStack.top(),1)); 91f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines operatorStack.pop(); 92f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines } 93f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines //evaluate the postfix expression written above 94f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 95f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines for (it=postfixString.begin(); it != postfixString.end(); it++) { 96f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines switch (*((*it).c_str())) { 97f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines case '*': 98f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines case '-': 99f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines case '+': 100f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines case '/': 101f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // when postfix string has an operator, pop first two operands from 102f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // operand stack, use them in evaluate expression and push result 103f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // back to stack 104f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines assert(!operandStack.empty() && "Invalid expression: extra operand"); 105f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines operand2 = operandStack.top(); 106f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines operandStack.pop(); 107f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines operand1 = operandStack.top(); 108f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines operandStack.pop(); 109f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines if (*((*it).c_str()) == '*') 110f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines result = operand1 * operand2; 111f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines else if (*((*it).c_str()) == '/') 112f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines result = operand1 / operand2; 113f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines else if (*((*it).c_str()) == '-') 114f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines result = operand1 - operand2; 115f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines else 116f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines result = operand1 + operand2; 117f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines operandStack.push(result); 118f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines break; 119f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines default: 120f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // if the string encountered in postfix queue is a string 121f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // try converting it to integer. 122f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines llvm::StringRef stringOperand(*it); 123f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines if(stringOperand.getAsInteger(0,result)) { 124f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // the integer conversion failed means the token is a symbol 125f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // or its invalid if the NamePool has no such symbol; 126f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines const LDSymbol* symbol = 127f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines m_Module.getNamePool().findSymbol(stringOperand); 128f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines 129f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines if (!symbol) 130f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines fatal(diag::fail_sym_resolution) 131f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines << __FILE__ << __LINE__ 132f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines << "mclinker@googlegroups.com" ; 133f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines result = symbol->value(); 134f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines } 135f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines operandStack.push(result); 136f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines } 137f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines } 138f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines // once complete queue is processed, stack top is result 139f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines pSymVal = operandStack.top(); 140f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines return true; 141f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hines} 142