LLVM札记1: 架构

LLVM作者在文章(LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation)对LLVM做了全面的Review。 指出LLVM是对现在JVM和托管C++的高层虚拟机的补充。是指令级别的,在IR层面和架构设计上有创新设计的。具体表现在将前端,中端,后端区分开来,做到编译时,链接时,安装时,运行时的优化。 传统的GCC构建框架,前端和后端代码是强耦合的。而用LLVM实现的编译器在前端Parser翻译好AST后,直接转换成统一的LLVM IR。在编译优化阶段通过Operation抽象的具体实现对语言进行不同处理,很好的体现了面向对象和模块化思维。

  1. 比如:TensorFlow有很多后端支持,以适配不同硬件需要。如TPU下的XLA,移动设备下的TFLite。
  2. 适配硬件的过程中,很多编译优化手段是通用的。没必要重写一遍。
  3. 针对这个问题,LLVM祭出MLIR来解决这个问题。比如A语言实现了某个常量折叠的优化。那么B语言可以复用A语言的优化时用到的数据结构。具体表现在继承一个表结构,复用操作过程。为什么可以共用,因为共享一个统一的中间层表示。你可以在插入多个IR(也是Multiple Layer Intermediate Representation的来源)来表示复杂的处理过程。这就是万能的软件中间层。
  4. LLVM IR是最底层的IR表示,它的设计创新在与可以对指针以SSA指令的方式来做算数操作。
  5. LLVM的另一个创新在于,自带一个类型系统。这个类型系统是抽象的,与上层具体语言无关的。

MLIR大概过程如下,LLVM IR作为底层表示,MLIR中间由用户扩展表示,并可以使用LLVM IR的数据结构。

mlir architecture
摘自文章

如果要分,其实还有中端。以下引用知乎的一段话”中端是最讲算法的部分,图的连通性,深度和广度优先搜索,强连通分量,最短路,拓扑排序这些基本算法全都用得上。后端思维方式是硬件思维,代码需要嵌入大量硬件相关的信息,并且有很多后端相关的优化。后端的优化相对中端更局部一些。”

MLIR目前只是个DSL工厂,社区里有各行各业的人: 硬件从业者,学者,工程师。具体分为研究算法的,设计新硬件的,做verification的,做ML的。

LLVM IR指令集:

  • 通过SSA的形式表达数据流,可以很清楚的定位代码的数据走向。
  • 显式的表达控制流(包括异常)
  • 显式的表达语言无关的类型信息
对于C代码
for (i = 0;i < N; ++i)
    Sum(&A[i],&P);

用LLVM IR来表达的样子是:

loop:
  // phi 指令位于基本块的开头,第一组是初始值,后面的组可以是label。
  %i.1 = phi int [ 0, %bb0 ], [ %i.2, %loop ]
  // 拿到 A指针 往后 偏移 i 的指针 即&A[i]
  %AiAddr = getelementptr float* %A, int %i.1
  // 调用Sum函数,这里的表示虽然是SSA形式,但表现形式很High Level
  call void %Sum(float %AiAddr, %pair* %P)
  // i变量自增1
  %i.2 = add int %i.1, 1
  //  如果 i 小于 N,那么将结果给 tmp.4 
  %tmp.4 = setlt int %i.1, %N
  // 条件跳转,如果tmp.4 为真,跳转到loop,如果为假,跳出循环。
  br bool %tmp.4, label %loop, label %outloop

LLVM札记2:基本块

BasicBlock:是一个顺序执行的指令容器。BasicBlock是一个Value,被分支和SWITCH语句所引用。 BasicBlock的类型是Type::LabelTy,这个类型代表一个branch分支可以跳转到的标签Label。一个组织良好的基本块只有在结束时才会被中断指令停止。但组织异常的基本块也会出现在构造和修改程序的中间态中出现,验证者需要确保基本块是“组织良好的”。

class BasicBlock final :
         public Value, // Basic blocks are data objects also
         public ilist_node_with_parent<BasicBlock, Function> {
 public:
   using InstListType = SymbolTableList<Instruction>;
 
 private:
   friend class BlockAddress;
   friend class SymbolTableListTraits<BasicBlock>;
 
   InstListType InstList;
   Function *Parent;
}

那么对于下面这段程序,他有多少个基本块呢。

int main(int argc, char **argv) {
  int i, j, k, t = 0;
  for(i = 0; i < 10; i++) {
    for(j = 0; j < 10; j++) {
      for(k = 0; k < 10; k++) {
        t++;
      }
    }
    for(j = 0; j < 10; j++) {
      t++;
    }
  }
  for(i = 0; i < 20; i++) {
    for(j = 0; j < 20; j++) {
      t++;
    }
    for(j = 0; j < 20; j++) {
      t++;
    }
  }
  return t;
}

利用LLVM中的BlockFrequencyInfo类的来统计下基本块信息:

//runOnFunction 
bool BlockFrequencyInfoWrapperPass::runOnFunction(Function &F) {
  BranchProbabilityInfo &BPI =
      getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
  LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
  BFI.calculate(F, BPI, LI);
  return false;
}

以上代码会调用LoopInfo Pass来获取循环的信息,如果我们迭代的从这个对象里获取信息,我们可以拿到基本块信息:

unsigned num_Blocks = 0;
  Loop::block_iterator bb;
  for(bb = L->block_begin(); bb != L->block_end();++bb)
    num_Blocks++;
  errs() << "Loop level " << nest << " has " << num_Blocks
<< " blocks\n";

上面代码拿到的只是外层循环的基本块。为了获取内存循环的基本块信息,可以递归的调用 `getSubLoops`函数。

void countBlocksInLoop(Loop *L, unsigned nest) {
  unsigned num_Blocks = 0;
  Loop::block_iterator bb;
  for(bb = L->block_begin(); bb != L->block_end();++bb)
    num_Blocks++;
  errs() << "Loop level " << nest << " has " << num_Blocks
<< " blocks\n";
  std::vector<Loop*> subLoops = L->getSubLoops();
  Loop::iterator j, f;
  for (j = subLoops.begin(), f = subLoops.end(); j != f;
++j)
    countBlocksInLoop(*j, nest + 1);
}
 
virtual bool runOnFunction(Function &F) {
  LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
  errs() << "Function " << F.getName() + "\n";
  for (Loop *L : *LI)
    countBlocksInLoop(L, 0);
  return false;
}

通过用Opt优化ll代码,我们自定义的Pass会被执行

clang –O0 –S –emit-llvm sample.c –o sample.ll
opt  -load (path_to_.so_file)/FuncBlockCount.so  -funcblockcount sample.ll

输出:

Function main
Loop level 0 has 11 blocks
Loop level 1 has 3 blocks
Loop level 1 has 3 blocks
Loop level 0 has 15 blocks
Loop level 1 has 7 blocks
Loop level 2 has 3 blocks
Loop level 1 has 3 blocks

输出很不好理解,而且好像人工也算不出。看不出来基本块是怎么计算出来的。

理工男的打理

理工男准备写点购物备忘。想到的第一句话竟然是:电子商务冲击实体店。还有救吗?

言归正传,一直觉得自己不会穿衣服。最近在淘宝上买了几件衣服和裤子,都不太如意。主要原因呢是伊对自己的尺码不太清楚。也不会搭配再加之,再加上身体不太瘦。(发福就发福嘛,还不好意思承认。)

第一在网上看了很多七龙珠主题相关的动漫衣服。觉得到了这个年纪穿这种装嫩的衣服不太合适。但还是架不住童年的回忆,买了几件。第二买了几套工装的裤子和衣服。这些尺码不太让人满意,又做了一次更换。第三买了一些工装的靴子。可能比较符合理工男的气质。(终于不要,总是格子衬衫啦。)

好,开始总结一下。

裤子呢,穿的太大了。像一个装修工人一样,不太修身也不太彰显气质。总之,买家秀和卖家秀的差别比较大,这真是一个令人头疼的问题啊。裤子呢穿XL可能会比较休闲,但是要注意腰身要提上。如果是L码的话呢,又怕私处受到挤压。(修身到底是个什么概念?我还没搞清楚!)。难道一定要去裁缝店量身定做?腰围到底有多少呢?腿长有多少呢?裤脚可不可以折起来呢?折起来好不好看呢?裤子的版型到底有多少种?理工男应该给他一个参数规格列表。到私处的长度是多少,应该再给个参数吧?这个大多数淘宝店是没有明确说明的,需要自己去尝试。(或者裁缝要知道)。

第二呢,买了一件工装的衬衫。衬衫挺不错的,条纹状,蓝白相间的竖条纹。选的型号是XL,淘宝的评论里面有人说这个穿起来像病号服(大笑😄)。但是穿在我身上感觉挺不错的。我想买衬衫以后就是XL吧,L的那肯定是不标准的尺码。第1次用心的买衣服,应该以后会更有经验,加油。

第三买了一些袜子,这些袜子大多数是有卡通主题的。也算是还了童年的一个愿望吧。据某人说袜子是消耗品,随便买买就可以了。可惜买东西上面我还真不是随随便便的人。

最后就是私人的内裤了,我毫不犹豫的买了一些CK的内裤。照道理,内裤应该也是消耗品,但是…我虚荣心作祟。我想,内裤以后可以买一些国产的品牌就不错了。

买完衣服后下个总结:最需要的是一个软尺,测量好胸围,腰围,臀围,腿长肩宽(🙃)。然后就是增强锻炼。让身体看起来更有版型,更有气质。摆脱理工男在人们心目中的形象。

补充:买了正版的350 V2的Sand Topae和 Nike 990元祖灰,同时买了莆田的350 V2, 虽然外观和做工都非常真了,但脚感还是稍有区别(退

把工位做了收纳,每天在工位至少8个小时。 几乎和床一样重要的东西了。

至此:床,鞋,衣服,袜子,工位,键盘。这几样和我相处最常的物件,我已经将你们打理好了。公司的椅子1000来块的这条件暂时不期望去改变了。在家里好好搞搞吧。

第三次拳击课

教练Artem是一个俄国大汉,嘟囔几句简单的英语。用形体语言给学员基本的示范。

前几次体能无法跟进。每次上完课,人处在一个万念俱空的状态。以至于过了好几天,走路时偶然的瑟瑟发抖。

通过有意识的对体能进行恢复(坚持每天跳绳15分钟+拉伸15分钟,直到出汗为止)。今天基本上能跟上节奏。对运动有了一些好感。

最大的感受是,拳击和网球一样,在入门时需要注重腰部力量。扭腰过程中,腿部发力,带动全身。网球是挥出球拍,拳击则是打中别人的脸 😄。

费曼阅读和記憶方法

這幾天看到 劉同學 的知乎。雖然口吻稍有誇張,但著實描述了自己的學習方法。記憶無非是大腦中按圖索驥,一點點的還原。

怎麼讓大腦的神經元關聯起來,快速的從記憶中獲取所需要的信息。

費曼的做法碰到不懂的地方就從頭來讀。

劉的做法是,按照順序,按照知識的相關性反覆記憶。

都是加強神經元的鏈接。方法很多,一定要找到適用自己的。

群组沟通的礼仪和技巧

网络几乎已经成为人们生活不可获取的部分。各行各业使用IM软件几乎都有一致的共同点。每个行业的背后沟通交流出发点是相同的:暴露问题和解决问题。

先看几个场景:

1, 客户将宠物放到宠物学校学习,宠物学校的教练会给宠物建一个微信群,实时沟通宠物的学习情况。

2,客户将房屋装修外包给装修公司,装修公司建群将装修进度和问题在群里反馈和沟通。

3,企业内部员工就某个问题或群体组建即时消息群。讨论工作问题。

在这几个群的背后,表面上最核心的动作就是:消息的组播。沟通变成了组播,组播结果驱动了事情的进展和方向。

实际是,消息的组播让工作有一个更好的交付界面。

在组播中,有以下礼仪需要注意:

  • 要及时赞美和鼓励。
  • 不要幻想对方都站在自己的立场想问题,要主谓宾描述完整。以免引起不恰当的误会。
  • 要多用 “请” , “多谢”,“辛苦你” 。因为对方看不到你的眼睛,这些词语让人处于合适的社交氛围中。

实践上述礼仪时,针对网络谩骂行为,造谣行为不在此礼仪的应用范围。应该特殊处理。不能姑息养奸,要及时给出“合适”的制止。

C++对象模型小探索

class base {
public:
    base():a(10),b(11){}
    virtual void fa(){ std::cout << "base a function...\n";}
    virtual void fb(){ std::cout << "base b function...\n";}
    
public:
    int a;
    int b;
    std::string c{"angel"};
};

class derived: public base {
public:
    void fa() override { std::cout << "derived a function ...\n";}
    void fb() override { std::cout << "derived b function...\n"; }
    void fc() { std::cout << "derived c function...\n";}
public:
    int c;
};



int main(int argc, char** argv)
{
    std::cout << "class base size : " << sizeof(base) << std::endl;
    std::cout << "class derived size: " << sizeof(derived) << std::endl;
    
    derived* pd = new derived();
    base* pb = new derived();
 
    using func= void(*)();
    
    long int vptr1 = reinterpret_cast<long int>(pb);
    long int vptr2 = reinterpret_cast<long int>(pd);
    
    long int* p = (long int*)vptr1;
    long int* p1 = (long int*)vptr2;
    std::cout << "p  " <<  p << std::endl;
    std::cout << "p1 " <<  p1 << std::endl;
    
    long int* vtaddr = (long int*)(*p);
    long int* vtaddr2 = (long int*)(*p1);
    std::cout << "vtaddr  " << vtaddr << std::endl;
    std::cout << "vtaddr2 " << vtaddr2 << std::endl;
    
    
    func* ptr = (func*)(vtaddr);
    (*ptr)();
    func* ptrb = (func*)(vtaddr+1);
    (*ptrb)();
    
    
    func* bptr = (func*)(vtaddr2);
    (*bptr)();
    func* bptrb = (func*)(vtaddr2+1);
    (*bptrb)();
    
    std::cout << *(int*)(long int*)(vptr1+8) << std::endl;
    std::cout << *(int*)(long int*)(vptr1+12) << std::endl;
    std::cout << std::string((char*)(long int*)(vptr1+16))<< std::endl;
    
    
    pd->fa();
    pb->fa();
    
    

    return 0;
}


以上代码强制调用vtable指向的函数,从安全性角度讲:可以替换虚表的任何函数。

结果是:

 class base size : 40
 class derived size: 48
 p  0x102a84240
 p1 0x102a84210
 vtaddr  0x10000b090
 vtaddr2 0x10000b090
 derived a function ...value is ...34
 derived b function...
 derived a function ...value is ...-1746446496
 derived b function...
 10
 11
 
 angel
 derived a function ...value is ...10
 derived a function ...value is ...10

强行使用裸指针调用,得到的成员值明显不对。推测是没有代入隐含的this指针。

下次谈谈如何基于本案列做C++的逆向工程。

我对C/C++语言运算规则另类小解

先看看无聊的C运算符优先级和结合性。看到表1的人可以分为三类:

  • C语言编译器的作者
  • 计算机入门者
  • 各种计算机基础能力考试应对者

比如要你计算: -Num++, +Num++, f( a(), b(), c()) ,int a= c,d,e; 之类的运算顺序。

大多数工程师为了避免记忆这繁琐的规则,使用()括号大法来解决大部分运算符优先级/结合性的问题。而且在大多数情况下,商业团队会通过统一的编程规范来避免程序语言的”坑”。

表1:运算符优先级和结合性

优先级 运算符 描述 结合性
1 ++ -- 后缀自增与自减 从左到右
() 函数调用
[] 数组下标
. 结构体与联合体成员访问
-> 结构体与联合体成员通过指针访问
(type){list} 复合字面量(C99)
2 ++ -- 前缀自增与自减[注 1] 从右到左
+ - 一元加与减
! ~ 逻辑非与逐位非
(type) 转型
* 间接(解引用)
& 取址
sizeof 取大小[注 2]
_Alignof 对齐要求(C11)
3 * / % 乘法、除法及余数 从左到右
4 + - 加法及减法
5 << >> 逐位左移及右移
6 < <= 分别为 < 与 ≤ 的关系运算符
> >= 分别为 > 与 ≥ 的关系运算符
7 == != 分别为 = 与 ≠ 关系
8 & 逐位与
9 ^ 逐位异或(排除或)
10 | 逐位或(包含或)
11 && 逻辑与
12 || 逻辑或
13 ?: 三元条件[注 3] 从右到左
14[注 4] = 简单赋值
+= -= 以和及差赋值
*= /= %= 以积、商及余数赋值
<<= >>= 以逐位左移及右移赋值
&= ^= |= 以逐位与、异或及或赋值
15 , 逗号 从左到右

去记忆这种表格明显是反直觉的,我们还是得理解编译器帮我们解释符号的意图。

C的符号可以归结为几类:

  1. 算术运算符。最普通的+ – * / % ~ & | ^ << >>
  2. 逻辑运算符。! && ||
  3. 赋值运算符。= &= <<=
  4. 比较运算符。< == >= <= > !=
  5. 成员访问。 [] () * -> .
  6. 其他 … , (type强转), sizeof, _Alignof

先是结合性,原则很简单,也很人类。

就是按照普通人的阅读顺序去记忆: 比如[], 它肯定是从左到右结合。因为 一个表达式 a[1], 先要知道a,才能知道相对寻址的 a[1]。 再比如算术运算a + b, 肯定是先move a到寄存器,在把a和b想加。因此也是从左向右结合。

那么,哪些是从右往左结合呢?

我们写代码 sizeof( SuperStruct ), 肯定是先想到SuperStruct的大小和地址在哪,然后再去取大小。这就是很直接的计算机思维

最有代表性的是: 前++,前– VS 后++, 后–

用他们来测试下这种规律的正确性:

a++ , 从左到右。因为先得知道a,才能++。

–a , 从右往左结合。 因为先得知道a,才能–。

看,这是不用记忆的。非常直接的计算机符号逻辑

优先级的记忆

优先级最高的: 除了后加/后减的优先级超高。 成员访问优先级高完全符合直觉。成员访问优先级高,可以理解为得先有数据才能做各种运算

优先级次高的: 几乎全部单目运算符优先级是次高的。单目运算符只需要一个操作数,和成员访问有相同的属性。

优先级第三/四高: 接下来是双目运算符, 乘/除/取余(优先级三) 比 加减(优先级四)优先级高,符合直觉。

优先级第五/六高: 算术运算比关系运算优先级高。 加减乘除移位比所有比较符号优先级高。移位这种算术运算 >>, << 比 >,< >=,<= 的符号优先级高。先算出来再比较。

优先级第六/七高: >=, <= 比 ==, !==优先级高。这个没有什么规则。就是C语言编译器的人自己定的规则。 先比较大小,再比较是否相等。

优先级第八/九/⑩高: 位运算自己的比较,依次是 & ^ |

优先级第十一/十二: 逻辑运算 && ||

第十三: 孤零零的一个 三目。

第十四:各种赋值

第十五:孤独的逗号。

所以,总结起来规则是:

  1. 成员运算优先级最高。成员运算符算是单目的一种,所以剩下的单目运算符次高。(单目优先原则,直觉)
  2. 算术运算符比关系比较运算符高。(先算[包括移位]出来再比较,直觉)
  3. 关系比较运算符比位运算符高。(比较完再来做位运算,非直觉)
  4. 位运算比逻辑运算符高。(有运算结果再来做逻辑与或)
  5. 逻辑运算比赋值运算符高。(做完算术,比较,位和逻辑运算再来赋值)
  6. 逗比排在最后。
  7. 结合规则完全从直觉去判断。